Study On Topology Control Technology In Wireless Ad Hoc Networks

Wireless Ad Hoc network is formed by a collection of mobile, wireless devices that cooperatively route packets for each other without any aid of fixed infrastructure or centralized administration, and is a self-organizing and self-configuring multi-hop wireless communication system. In such a type of network, topology structure which is determined by the node position and transmission range has significant effect on network performance. Therefore, how to optimize network structure and enhance network survivability so as to provide underlying topology with desired property for upper layer communication protocol is major concern of topology control technology. In this dissertation, the topology control technology for wireless Ad Hoc networks is studied in three aspects: energy-based distributed topology control, critical transmitting range and topology partition detection. Meanwhile, MAC address assignment problem for wireless sensor networks is also discussed. The main achievements and results of this dissertation are listed as follows:1. To address the problem that most of existing algorithms can not balance energy consumption and extend network lifetime efficiently, a lightweight dynamic topology control algorithm EDTC (Energy-aware Dynamic Topology Control) is proposed. Based on the link metric reflecting both the energy consumption rates and residual energy levels at the two end nodes, EDTC generates a dynamic network topology that changes with the variation of node energy. In addition, without the aid of location information, each node determines its transmission power according to local network information, which reduces the complexity and overhead greatly.2. Based on EDTC, a localized distributed topology control algorithm called ESATC (Energy-aware Self-Adjusted Topology Control) is proposed for heterogeneous wireless Ad Hoc networks. It extends the idea of dynamic optimization into hybrid wireless networks and becomes more generalized. Theoretic analysis and experiment results show that just like EDTC, ESATC algorithm preserves network connectivity and minimum-cost property and it can extend network lifetime remarkably. 3. Biconnectivity is the baseline graph theoretic metric of fault tolerance to node failures which can keep network connectivity while allowing unexpected node failures. In this dissertation this property for one-dimensional wireless Ad Hoc networks with finite nodes is analyzed. With common adopted assumption of uniform node distribution for static networks, the formula for the critical transmitting range that realizes network biconnectivity with certain probability is derived via proposed independency approximation assumptions. Simulation results validate the accuracy of our conclusion and confirm its efficiency in practical network design.4. As the failure of a critical node will directly partition a network, a theorem for critical node identification is proved, which indicates that node degree Ni and elementary loop degree Mi of node i are two decisive factors for the existence of a critical node and shows that Ni-Mi≥2 is the necessary and sufficient condition for node i being critical. Based on the theorem, a distributed topology partition detection algorithm called DPDP (Distributed Partition Detection Protocol) is presented for large scale networks, which achieves the goal of partition detection efficiently by detecting critical nodes in a local area. Theoretic analysis and experiment results show that DPDP has the advantages of low complexity, high accuracy, low cost as well as good scalability, and is superior to other algorithms.5. Compared with the small overhead of data payload in wireless sensor network, the overhead of MAC address is significant in terms of energy-saving. In this dissertation, a novel distributed MAC address assignment algorithm named VGSR (Virtual Grid Spatial Reusing) is proposed, which reduces the size of the MAC address efficiently based on both the spatial reuse of MAC addresses and the mapping of geographical position. By adjusting the communication range of sensor nodes, VGSR can minimize the size of MAC address and meanwhile guarantee the connectivity of sensor network. The theoretic analysis and experiment result show that VGSR is low energy cost, but also it scales well with the network size. Its performance is superior to other existing algorithm.