Study On The Graph Theory And Matching Theory Based Resource Allocation Methods In Social Internet Of Things

As an extended application of the Internet,the Internet of Things(IoT)expands the current form of interactions to people,people and things,and things and things.The theoretical framework and technical route about IoT requires collaborative innovation from multiple fields and disciplines.In recent years,with the development of intelligent technology,the devices that people use every day have gradually become intelligent,and they have been transformed into intelligent devices that can perform situation sensing and data analysis.When the device is endowed with sufficient intelligence,things can interact with each other to establish the social relationship,thereby forming a social network between intelligent objects-the Social Internet of Things(SIoT).In the SIoT scenario,the design of resource allocation schemes driven by social intent is crucial.Compared to the traditional centralized optimization scheme,the distributed resource allocation scheme based on graph theory and matching theory has become a popular research direction in the field of wireless communications and networks due to its performance advantages on computational complexity and signaling overhead,which is more applicable to the current highly dynamic network topologies.Based on this,this thesis uses graph theory and matching theory to study a series of resource allocation issues such as content sharing,user pairing,and task allocation in SIoT application scenarios.By integrating the SIoT with Flying IoT(FIoT),the concept of the social Internet of Flying Things(SIoFT)is proposed and then a series of works are carried out in this scenario.The main contributions are as follows:1.Stable Matching on Hierarchical Bipartite Graph for Spectrum Allocation in SIoTAiming at solving the problem of excessive Base Station(BS)load caused by users repeatedly downloading the same content under the limitation of spectrum resources in SIoT,the driving role of user's social attributes on content sharing is studied,that is,those adjacent users with higher interest similarity and trust can reduce the load on the BS by establishing direct links for content sharing.At the same time,the direct link established should also consider the allocation of spectrum resources.This threedimensional matching relationship can be represented by a hierarchical bipartite graph.By abstracting the entire caching mechanism into a hierarchical bipartite graph,the optimization problem is transformed into two sub-problems.The first sub-problem is the matching between the content providers and the content requesters.The second problem is the user pairing between device-to-device(D2D)users and cellular users with peer effects.This problem cannot be effectively solved by the deferred acceptance algorithm due to the dynamic changing of the preference lists.Therefore,a selforganized rotation-swap algorithm is proposed that enables users to exchange matching partners in a self-organizing manner from the initial unstable matching state,and finally reaches a stable state.The distributed cache scheme designed in this section can achieve a trade-off between transmission reliability,downloading delay,complexity,and stability.2.Stable Matching on Tripartite Graph for Content Sharing in SIoTTo solve the problem of limited storage space and energy of IoT devices,the research on the pre-cache scheme design,user scheduling design,reward mechanism design is conducted,and how to achieve the goal of benefiting multiple users by manipulating one position in one user's preference list is explored.First of all,due to the limitation of the storage capacity and transmission range of the content providers,fully caching a single content may cause the utilization of the storage capacity and the cache hit rate to be too low.Therefore,assuming that the user equipment gets around this problem by caching incomplete content,the content diversity can be improved.When a content is requested,the content helper can act as a relay node to send the remaining content to the content requester using the buffering capability.Therefore,this thesis focuses on how to achieve a trade-off between quality of experience(QoE)and energy consumption by rationally allocating the ratio of buffer to cache when the storage capacity is limited.Specifically,the user scheduling scheme is abstracted into a tripartite graph,and a distributed three-dimensional stable matching algorithm is proposed to achieve the stable matching among small base stations(SBSs),content helpers and content requesters.Finally,a manipulation mechanism with domino effects is proposed to further enhance the overall effectiveness,and verifies the chain effect of the manipulation mechanism with detailed theoretical proof.3.Dynamic Stable Matching on Bipartite Graph for Task Assignment in SIoFTBased on the SIoFT scenario,the impact of social attributes on the drone mission coordination in disaster relief networks is studied.First of all,for the problem of data collection in emergency rescue scenarios,an unmanned aerial vehicle(UAV)-assisted mobile crowded sensing(MCS)system is proposed,and the sensing task assignment scheme design under a dynamic and stochastic environment is studied.In this thesis,the optimization problem is transformed into a dynamic matching problem,and multiple-waitlist based task assignment(MWTA)algorithm is proposed to obtain stable matching under the conditions that the tasks arrive periodically and the drones arrive stochastically,shifting from the static stability that focuses on the short-term utility to the dynamic stability that focused on the long-term utility.Simulation results demonstrate the performance improvement of our proposed scheme compared with the traditional matching algorithm applied to deterministic matching model in stochastic setting.The proposed algorithm has certain guiding significance for other dynamic resource allocation problems in wireless communication and networks.4.Popular Matching on Bipartite Graph for Security-Enhanced Resource Allocation in SIoFTIn SIoFT scenario,the broadcast nature of air-to-ground(A2G)channels are vulnerable to eavesdropping by terrestrial malicious users due to their strong line-ofsight(LoS)links.Hence,this thesis investigates to ensure the security of air-to-ground communications while the location information of multiple potential eavesdroppers cannot be perfectly estimated.Following the “no pain no gain” principle,the terrestrial users who reuse the UAV cellular spectrum will act as friendly jammers to realize “winwin” situation.Hence,joint trajectory design,power control,and channel allocation optimization problem is formulated to maximize the average secrecy rate of UAVs in worst case.In the first stage,the block coordinate descent method and successive convex optimization method to are utilized to solve the trajectory design and power control problems in an iterative manner.In the second stage,the user pairing problem is converted to a popular matching problem.Two distributed algorithms are proposed to maintain the popular matching under the dynamics.Moreover,detailed analysis of the popularity,convergence,and computational complexity is provided.Simulation results demonstrate that our proposed method can achieve approximately 67.5% increment in secrecy rate with approximately 33% loss in achievable rate.