Hierarchical Routing Issues For Wireless Ad Hoc Networks

Wireless Ad hoc networking possesses the character of acentric, self-organized, autonomous, fast deployable and mobile. 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 arisen great interest of military departments, industrial communities and academic institutions in the world.Unlike wired networks or cellular networks, no physical bakebone infrastructure is installed in wireless ad hoc networks. Therefore, hierarchical routing mechanism with a virtual backbone is becoming research hotspot. Because of moving, the present hierarchical routing make demands on high update and maintenance of a virtual backbone. With the result that high control packets overhead and energy waste would be arisen. To solve this problem, based on the concept of graph theory we give a few models and arithmetic designs of virtual backbone in the environment of different application, and propose the corresponding routing mechanism with these virtual backbones. The major achievements are outlined as follows:The state of host's power or the time of host's online plays an important role in keeping stability of a virtual backbone. With a view to this feature, the paper introduces a simple and efficient heuristic algorithm for calculating the virtual backbone by seeking a minimum connected dominating set with maximal weight. The maximality of the weight-based choice of backbone nodes guarantees that the most suitable nodes have been chosen for the role of backbone nodes so that they can properly coordinate all the other nodes and keep stability of the virtual backbone in the network. The minimality of the virtual backbone is assured by designing optimization algorithm. As a result, it can effectively decrease the overhead of control packets dissemination. Simulation resluts show the correctness and the ability of self- renew.Considering the characteristic of fast-moving in wireless ad hoc networks, we construct a virtual backbone with a independent dominating set. This method can avoid sustaining connectivity between backbone nodes and the bakebone network can be rapidly reconstructed as topology change. By adopting the mechanism of dynamic on-demand routing, the backbone nodes are prevented from keeping routing table.The minimal independent dominating set is settled by calculating maximal independent set.In view of trait of only transmitting data in wireless ad hoc sensor systems, we create a virtual backbone with a spanning root tree of relay set with maximal weight and propose a energy- aware multilevel cluster tree algorithm(EAMCT). By optimum seeking method, the nodes with high residual energy and low communication cost are given first priority to clusterheads. And by utilizing periodical rotation of local clusterheads and motion of base station to evenly distribute the energy load among the sensors in the network and prolong network lifetime. Simulation results demonstrate that our approach would significantly increase the lifetime of the sensor network and be applied to the design of several types of sensor network protocols that require energy efficiency, scalability, low delay.For the sake of solving the problem of energy waste as distance increased among clustering heads, based on EAMCT we give a routing mechanism with EAMCT-G (Energy- Aware Multilevel Cluster Tree with Gateway). By introducing some gateway nodes as relay transmission into clustering heads, network lifetime is furthermore prolonged. Simulation results demonstrate validity of EAMCT-G.