Path Optimization In Opportunistic Networks

Opportunistic networks are special evolutions of mobile ad hoc networks, where most of the time there does not exist a connected path from the sender to the receiver. To route messages in such networks is a challenged task due to the lack of information about the real time evolution of global network topology, which is affected by nodes’ mobility patterns and the variance of wireless environment. Generally speaking, the more knowledge of network topology we collect, the more effective routing scheme we are likely to find. However, such useful information is not easily accessible, because the dynamic pattern of network topology is statistically complicated to learn.In this thesis, we try to statistically establish contact topology by introducing connecting rate among nodes, and apply such concept to form effective routing path from source nodes to destination nodes. The main ideas of proposed algorithms are to seek and forward messages to the intermediate nodes who are potential to have higher connecting rates with destination nodes. The main contributions of this thesis include:(1) mathematically modeling nodes’ contacts with connecting rates,(2) studying the application of connecting rates in single copy routing schemes as well as multiple copies approaches to improve routing performances,(3) designation of a buffer management scheme based on connecting rates in opportunistic network, and(4) evaluation of the proposed routing algorithms by computer simulation. Simulation results show that our algorithms outperform classic routing schemes in the aspect of delivery probability and overhead ratio.