Research On Routing Selection And Performance Evaluation In Mobile Opportunistic Networks

Mobile opportunistic networks (MONs) play an important role in implementing the intensive perception and ubiquitous interconnection in internet of things. Opportunistic routing is the theoretical basis for data communication in intermittently connected scenarios, it hence is worthy to be studied. However, opportunistic routing is very challenging because of node mobility, constrained resource and tempory topology in MONs. Existing works take a multi-copy scheme to forward packets, so as to speed the data forwarding process and improve the packet delivery ratio. This scheme simultaneously results in a heavy network cost and considerably impacts the system scalability. How to design a lightweight and distributed opportunistic routing algorithm to satisfy large-scale autonomous networking requirement, becomes one of the key scientific problems for MONs.In this thesis, based on the social information encoded in mobile portable devices, we study the aforementioned problem from two aspects:information diffusion model and data forwarding scheme, and propose a series of new models and methods. We summarize our main contributions as follows:(1) Spatial-temporal based information diffusion model. In mobile opportunsitc networks, node location distribution shows spatial-temporal correlation, due to node mobility. This feature makes different nodes have different infectivities. The existing evaluation model hence results in a bias understanding of the epidemic dynamics of mobile opportunistic networks. In this thesis, we first characterize node’s information transmission ablity by using heterogenous infectivity, we then exploit the Markov chain to model the information diffusion process and give a tight upper bound on the scaling law. Finally, we develop an evaluation model for opportunistic routing by analyzing the impact of the number of infected nodes on transmission delay and packet delivery ratio.(2) Social metrics-based opportunistic routing algorithm. In existing social metrics based data forwarding strategies, the evaluation methods for centrality and similarity have high spatio-temporal complexity, and hence can not be applied into large scale opportunistic scenarios because of their poor scalability. Considering these facts, we use node mobility pattern to evaluate nodes’ centrality and similarity, and integrate them into data forwarding process. The forwarding strategy includes three steps:a) extracting the mobility pattern; b) quantifying nodes’ social metrics; and c) selecting the relay nodes. For the feature extraction phase, we divide the sensing area into lots of small grids, and mine user’s frequent mobility pattern by aggregating the number of user’s staying points and duration in each grid. Furthermore, we exploit the information entropy theory to evaluate nodal centrality and similarity. For the node selection phase, we use the normalized method for the centrality and similarity to set up their utility functions. According to the utility functions, we map the problem of node selection to a multi-object optimization problem, we then develop an adaptive weighted method to satisfy their respective needs.(3) Social relationship-based opportunistic routing algorithm. Using the relatively stable social relationships can benefit the performance of opportunistic routing. After analyzing the roles of different social relationships in the optimal forwarding paths, we observe a) Strangers have two sides in data forwarding process. On the one hand, there exist a lot of strangers in the shortest paths of Epidemic. This means that strangers play a positive role in data forwarding process. On the other hand, the strangers have speeded up the dissemination process by infecting many other nodes, which increases the routing cost as well; b) The greedy scheme reduces the cost but increases the delivery delay; c) The importance of strangers shows a decreasing trend along the optimal paths. In contrast, the importance of community partners shows an increasing trend. Using these heuristic knowledge, we propose STRON, a distributed and lightweight forwarding scheme, to improve the transmission efficiency. These features make it very suitable for crowd sensing scenarios with pervasive participants and ad hoc management.(4) Community structure-based opportunistic routing algorithm. There exist temporal communities in mobile opportunistic networks. It is important to study the role of these communities in message diffusion, so that we can observe the epidemic dynamics from a higher level and deepen our understading of data forwarding process. To do so, we analyze the dissemination speed of data packets within different opportunistic scenarios. We observe that a) the message delivery delay is dominated by the transmission time from one community to another, and the delivery delay within one community is quite stable and short, and b) the nodes with high relative importance to the target community bear most weight on routing performance. Motivated by these observations, we propose a routing algorithm based on the network community. The algorithm includes two stages. Before data packets enter into the community of the destination, they are forwarded to nodes with higher relative importance so as to quicken their dissemination speed to the target nodes; After they enter into the community, they are delivered to the destination or community members with higher relative importance in that community, in order to refrain the dissemination range of data packets and reduce the forwarding cost.In summary, by integrating nodal sociality, this thesis studies the problem of opportunistic routing and proposes a series of models and methods from two aspects: information diffusion model and data forwarding scheme. Theoretical analysis and extensive experiments demonstrate the effectiveness of our models and methods. The proposed forwarding strategy is the foundation for efficient data collection in mobile opportunistic networks.