Research On Key Technologies Of Opportunistic Routing In Mobile Ad Hoc Network

MANET (Mobile Ad Hoc network) is distributed, self-organized, autonomous, fast deployable and mobile in nature. It can be flexibly and quickly deployed for many applications such as decision making in the battlefield, emergency search-and-rescue operations, and data acquisition operations in inhospitable terrain, etc. The emergence of wireless ad hoc networks has arised great interest of military departments, industrial communities and academic institutions in the world. In particular, routing protocol design is a very important and challenging task in this research area.The opportunistic routing paradigm has opened a new avenue for designing routing protocols in multi-hop wireless networks. Unlike traditional routing wireless protocols such as DSR, AODV which rely on a (pre-selected) single fixed path for delivering packets from a source to a destination, opportunistic routing explicitly takes advantage of the broadcast nature of wireless communications to allow multiple (pre-selected) forwarders to opportunistically deliver packets from a source to a destination. The path a packet takes depends on which forwarders happen to receive it, and is thus non-deterministic. As a result, opportunistic routing can better cope with the lossy, unreliable and varying link qualities that are typical of wireless networks.Therefore the opportunistic routing problems are investigated in depth with the support of the Programs from National Science Fundation of China and etc., and the research results have been published in proceedings of IEEE Wireless Communications and Networking Conference and etc. The main innovative results are listed as follows.Firstly, a novel routing metric (EN) is specially designed for the opportunistic routing (OR) perspective. The author utilizes the random walk theory modeling the opportunistic routing problem, and mathematically prove the EN metric is essentially the exact measure for the expected number of transmissions in OR. Moreover, extensive simulation results show that it can more precisely capture the characteristic of the OR than ETX or any other traditional single path routing metric.Secondly, in this thesis, the author establishes a general theory for analyzing the forwarder list selection problem, and developed an optimal forwarder selection algorithm-the minimum transmission selection (MTS) algorithm-which minimizes the expected number of transmissions under the perfect ACK assumption. The author shows how this assumption can be relaxed in practice to account for unreliable and asymmetric link qualities. MTS theory and algorithm can also be generalized to other routing objectives such as minimizing the expected transmission time or energy consumption in opportunistic routing. Through extensive simulations using the MIT Roofnet dataset, the author demonstrates that in more than 90% cases the MTS algorithm outperforms the forwarder selection scheme used in ETX based opportunistic routing protocols such ExOR and MORE, with performance gains up to 82% in terms of the number of transmissions, and up to 322% in terms of throughput.Thirdly, we design a wireless topology partitioning scheme, namely, spectral graph partitioning (SGP) algorithm, which can minimize the total cuts among all sub-topologies. It judiciously transfers the total min-cut problem to a standard matrix trace minimization problem, and utilizes the k-means algorithm to obtain the optimal graph partitions. SGP algorithm essentially provides us a way to partition the wireless topology, in which the connectivities within each sub-graph are maximized. This in fact makes it possible to realize the local opportunistic routing in large-scale wireless network.Finally, as the wireless network scales up in size and complexity, the need to study the scalability and behavior of these networks and theirs protocols becomes essential. Opportunistic routing utilizes broadcast nature of wireless network, and significantly increases the unicast throughput. However, the global scheduling scheme it adopts restricts its application in large-scale wireless network, due to the big waste of the end-to-end transmission latency and the computation cost. So, how to schedule the transmissions of different forwarders is essentially an important issue of the opportunistic routing scheme design. We propose GPLS (graph partitioning based lacal scheduling) protocol which employs the SGP algorithm to partition the wireless topology into several subgraphs with minimum cuts among them. GPLS essentially realizes the local forwarding in each sub-graph, and traditional forwarding across the sub-graphs. Simulation results show that our local forwarding scheme can significantly improve the network performances in large-scale network over existing opportunistic routing schemes, in terms of the end-to-end delay and the life time of the wireless node.