Study On The Protection Routing And Its Key Techniques For Ad Hoc Wireless Networks

An ad hoc wireless network is a complete autonomous system that consists ofdevices with transmitter and receiver. Recently, Ad hoc wireless networks have beenextensively applied in battle field communication, emergency communication and ve-hicle communication etc. However, nodal mobility lead to that the network topologychanges rapidly and unpredictably over time, and which has became an essential fea-ture considered for designing an efcient network. On the other hand, nodes lack suf-cient power restricts their ability to obtain and maintain sufcient network information.Therefore study on mechanisms to enhance network performance with limited networkinformation becomes one of the hottest direction in this field.Without information about the destination, a route discovery involving expensivenetwork-wide flooding is typically used by reactive routing protocols. Through in-depth studying routing protocols in ad hoc wireless networks, we determine criticalreasons causing broadcast storm when finding routes to the destination and prove thatthe diameter of the network is one of the most fundamental factors. In this article, wepropose a search model of determine the value of network diameter and obtain severaloptimal algorithms. To enhance robustness of routing, we introduce protection routingfor ad hoc wireless networks and obtain a distributed protection routing protocol, sayMKRP (Multiple Key-Routes Protection routing). In detail, the main contributionsinclude the follows.(1) We conclude several critical problems for designing routing protocols. Therouting protocols are modeled with search processes, we model routing protocol withsearch processes and classify information it used as position, direction and distance etc.Through comparing these information's roles in protocols, we sort their importance andfilters the most critical factors.(2) We propose a method to search the upper boundary of the network diame-ter. With the group testing model, we obtain a method to determine exact value of a network's diameter. To fit the limitation of resource of nodes, we propose a modelof search with small sets through restricting the above model with limited query vol-ume, and design an algorithm with minimum average queries and prove its optimalitytheoretically.(3) We propose a method to determine the exact value of network diameter eventhough there exists at most feedback fault during whole search process. To fit the un-reliability of wireless channel, based on the general search with small sets, we presenta search with lies and small sets model to design fault tolerant strategies of computingthe networks'diameter. For the case of allowing at most one lie is allowed, we obtaina worst-case optimal algorithm and prove it theoretically.(4) We propose a distributed protection routing MKRP (Multiple Key Routesbased Protection routing). All nodes are classified into primary active nodes, activenodes, backup nodes and normal nodes, according to the information stored in them,and their transfer relationship is defined. Based on the above techniques we obtain andistributed protection routing including node-disjoint key paths discovery, secondarypaths selection, failure maintenance and routing table discard, say MKRP, and its cor-rectness and performance is verified theoretically and experimentally.Besides, we develop a comprehensive performance evaluation test-bed Qos WADN with commercial routing devices, embedded boards and computer servers andverify our designed algorithms such as MKRP in this dissertation.