Study Of The Topology Management In Wireless Ad Hoc Networks

A wireless ad hoc network is a collection of wireless mobile nodes thatself-configure to form a network without the aid of any established infrastructure. Thetopology of a wireless ad hoc network, which is determined by positions andtransmission ranges of nodes, has a significant effect on the network performance.Topology management deals with how to optimize the network topology, improve thenetwork performance, enhance the network survivability and realize quick deploymentand self-configuration of the network. In this thesis, we discuss the problem of topologymanagement from three aspects: the hierarchical network management architecture,topology control and energy-efficient broadcast. The main contributions of this thesisare listed as follows:1. Forming and maintaining clusters are very important in a hierarchical networkmanagement system. By alalyzing the random ad hoc mobility model, we first introducethe notion of cluster availability which provides a quantitative measurement of clusterstability. Furthermore, a cluster maintenance algorithm based on cluster availability isproposed. In this algorithm, a node should continue to function as a cluster head as longas its degree of stability is maintained within a safe boundary. If a node running thecluster head service is on the verge of some degree of instability, then it should stepdown and make arrangements for management service migration, so a more stable nodewithin the cluster can take over as the cluster head. A unique feature of our algorithm isthat it can alleviate the influence caused by mobility, enhance the cluster stability,improve the continuity of management, and make the network management moreefficient.2. A topology maintenance algorithm based on the shortest path tree is proposed. Inthis algorithm, the neighbors of a faulty node are first triggered to respond (i.e., rerunthe topology control algorithm). Without extra communication overhead, eachresponding node determines the network connectivity by the contents of Hello messagessent by its neighbors. If the responding nodes couldn't ensure that the network isconnected, the other reachable nodes from the fault node are further triggered. Theproposed scheme can efficiently maintain the network connectivity with low overheadand achieve acceptable performance in terms of both power efficiency and powerstretch factor.3. We propose a topology control algorithm for constructing a minimum-energypath-preserving spanning subgraph for a wireless ad hoc network. Not only does theconstructed topology preserve a minimum-energy path between every pair of nodes, butthe entire network connectivity and the global minimum-energy path property can beefficiently maintained in a responsive manner as the network changes dynamically. Thatis, only those nodes that detect network changes may need to rerun the topology controlalgorithm, and the maintained topology preserves the global minimum-energy pathproperty.4. A fault-tolerant topology control algorithm for constructing an energy-efficientspanning subgraph is proposed. The constructed topology has the following properties:(1) it preserves a minimum-energy path between every pair of nodes;(2) it isbiconnected, i.e., it can tolerate any one node failure and avoid network partition.Furthermore, the biconnectivity and the global minimum-energy path property can beefficiently maintained in a responsive manner as the network changes dynamically.5. Broadcast in wireless ad hoc networks is another challenging problem. We firstintroduce the notion of power efficiency which reflects the ratio of the effective oruseful output to the total input for a potential broadcasting node. More specifically, theless power a node use and the more uncovered neighbors it covers, the higher powerefficiency it has. Based on the power efficiency, a localized broadcast algorithm isproposed. Our algorithm uses the dynamic broadcasting information and always selectsthe node which has the highest power efficiency within its 2-hops neighbors to forwardthe broadcasting message, and finally construct a broadcast tree rooted at the source.The proposed algorithm has performances comparable to the centralized broadcastalgorithm based on incremental power and significantly outperforms other existingdistributed broadcast algorithms.