Wireless Multi-hop Network Routing Technology Research

Recently, wireless communication technology and wireless networks have become more and more popular. As the new network architecture in the wireless communication technology industry, the multi-hop wireless network is gathering interest and has become a hotspot. The multi-hop wireless network, which has no infrastructure support, typically embodies the wireless mobile ad hoc network (ad hoc network for short) and the Low earth orbit (LEO)/Medium Earth Orbit (MEO) satellite constellation network (satellite network for short). The ad hoc network contains a collection of mobile wireless nodes which cooperate to maintain network connectivity without communication infrastructures for routing. Ad hoc networks are used more and more widely in military and civilian applications due to their rapid network deployment and the outstanding ability of destruction-resistance and self-recovery. Characterized by the lower propagation delay and power loss comparing with the geostationary earth orbit (GEO) communication and the ability of employing the inter-satellite links (ISL) for networking, the satellite networks are becoming an important trend for the future satellite mobile communication systems and will be able to supply multiple quality of service (QoS) to the users regardless of their geographic location. The satellite network has the advantages of wide transmission range as well as broad coverage, hence plays the indispensable role for navigation, remote users and those without infrastructures. Even if in the areas with dense wired networks, the satellite network can still serve as an alternative to the existed wired networks, providing the network access and/or the backbone relaying.By analyzing these two networks, this thesis recognizes that besides their similarities like multi-hop, wireless and node' s mobility, ad hoc network and satellite network have their unique characteristics respectively. Based on this, it argues that not only the routing technology in the existed wired networks cannot directly apply to the two networks, but deep research on routing should be made for these two typical multi-hop wireless networks respectively according to their own unique characters.The primary contributions on the routing technology in the satellite network are as follows:After presenting the network trend of satellite communication and the framework of the mobile satellite communication system, the thesis extracts the satellite constellation network from the mobile satellite communication system, takes it as one form of the multi-hop wireless networks, and names it satellite network. Based on the detailed analysis of the current routing technology in satellite networks, a routing protocol called the Satellite network Adaptive Routing Protocol (SARP) is proposed. Furthermore, other two QoS routing strategies with regard to connection handover issues are proposed for the LEO satellite network.In SAPR, the dynamics of satellite network topology are analyzed in detail and classified into two types: the periodical, regular and predictive network topology dynamics and the unpredictable burst dynamics. The corresponding strategies are adopted to deal with these two types of network topology changes. Base on the Discrete Time Dynamic Virtual Topology Routing (DT-DVTR), SARP uses a series of static network topology models to simplify the periodical, regular and predictive network topology dynamics. At the same time it utilizes the multiple routes to adapt to the burst changes. The routing loop issues caused from the multi-route scheme and the probing of the status of the adjacent ISLs are stressed in SARP. We briefly analyzed the routing overhead of SARP, including the storage overhead, the bandwidth overhead and the overhead for processing. We also used NS2 to simulate SARP, evaluating its end-to-end delay and the packet loss ratio performance. The conclusion is: compared with DT-DVTR, SARP has certain degree of robustness at the cost of slight routing overhead. It alleviates the temporary ISL failures resulted from the network congestion or other causes, and thus has a higher utilization of the satellite network resources.As the LEO satellite moves highly along its orbit, the connection handover becomes an unavoidable issue in the LEO satellite networks. The QoS routing in the LEO satellite networks should consider this problem while achieving the QoS path for the request of the QoS calls and making an efficient use of the network resources. Based on this, two QoS routing strategies are proposed in this thesis for the LEO satellite networks: the QoS routing strategy with the connection handover restricted and the QoS routing strategy with rerouting mechanism.Being a tradeoff between maximum path lifetime (in order to decrease the timesof the connection handover as possible) and minimum hops (to maximum the network resource utilization), the QoS routing strategy with the connection handover restricted aims to reduce the probability of the connection handover while effectively utilizing the LEO satellite network resources. Given the probability distribution of the duration of the connections, the strategy selects a proper maximum probability of the connection handover to compute the connection lifetime (duration), and further to achieve the QoS path with the path lifetime no less than the inferred connection lifetime. We use NS2 to simulate and evaluate the proposed QoS strategy. Simulation results illustrate that by choosing the proper maximum probability of the connection handover, the strategy decreases the average frequency of the connection handover while achieving an efficient utilization of the LEO satellite network resources under the circumstances that the network load is slightly high or the connection lifetime is not too long.To improve the utilization of the network resources and satisfy the low blocking probability requirements of some applications, we propose to use the rerouting scheme in the QoS routing in the LEO satellite networks. Here rerouting means to select an already accepted flow and replace its established path with some other path in order to accept a newly arriving transmission request which can not be accepted without doing so. In this proposed strategy, the QoS traffic is divided into two types in terms of required quality: higher-priority traffic with needs of low blocking probability and low-priority one without that. The rerouting scheme is used if the newly arriving high-priority request can not be accepted. Through simulations, the conclusion is made that although the rerouting avails to improve the performance in terms of blocking probability of the high-priority connections, it brings the overhead and also causes a higher connection handover frequency. For solving this problem, two methods are adopted and proved by the simulation results, namely limiting the ratio of high-priority connections and designing a new approach to select the accepted flow for rerouting according to the characteristics of LEO constellation network topology.The primary contributions on the routing technology in the ad hoc networks are presented as follows:Based on a comprehensive investigation of the ad hoc network and its classical routing algorithms, we argue that besides adapting to the dynamic network topologyand avoiding the routing loop, another two aspects should be considered in designing the routing protocol for the ad hoc networks: the limited energy of the network nodes and the limited bandwidth resources of the shared channel, Based on these two issues, two routing algorithms called the Energy-Aware Probability Routing (EAPR) and the Bandwidth-Efficient Cross Layer Probability Routing (BECLPR) respectively are proposed for the ad hoc networks in the thesis.Energy efficiency becomes an important issue to be considered in the ad hoc networks. In order to prolong the network lifetime, the energy consumption of the nodes in the network should be balanced. The proposed EAPR in this thesis is a new simple and efficient routing. EAPR introduces a probability model in the DSR (Dynamic Source Routing) route discovery procedure, implicitly balances the communication traffic and further achieves balanced energy consumption among all the nodes in the network. We analyze the coefficient a in the probability model and illustrate its effect on EAPR through simulations. Also simulations illustrate that EAPR outperforms LEAR (Local Energy-Aware Routing) in terms of the routing overhead and the balanced energy consumption distribution among the nodes in the network.Bandwidth efficiency is also an important issue for routing due to the limited bandwidth resources of the shared channel and the dynamics in ad hoc networks. The proposed BECLPR in the thesis differentiates between the send bandwidth and the receive bandwidth of the node which are used for sending data and receiving data respectively. Based on the available send/receive bandwidth range provided by the MAC layer, a probability model is defined in BECLPR called Available-Bandwidth-Aware Probability Model of the Node (ABAPMN). By that each node processes the route request message with a given probability on its ABAPMN in the route discovery procedure, BECLPR probabilistically distributes the loads among the nodes according to the available send/receive bandwidth resources in the network, and is able to achieve a path with relative adequate network resources for the route request. The output queue length of the node on the path is also considered in searching for a path as well. Simulation results show that BECLPR outperforms AODV (Ad hoc On-demand Distance Vector routing) in terms of the packet delivery ratio and routing overhead. BECLPR has lower end-to-end delay compared with AODV when the network load is not too high.Finally, the conclusion is given in the last part of the thesis, which contains the shortcomings of the proposed routing algorithms, the improvements needed, and the prospect for the future work.