Construction of low weighted and fault-tolerant topology for wireless ad hoc and sensor network

To preserve network connectivity is an important issue especially in wireless ad hoc and sensor networks (WASN), where wireless links are easy to be disturbed and tiny sensors are very easy to fail accidently. Therefore, it is necessary to design a fault-tolerant network. A feasible method is to construct a k-connected (k-vertex connected) topology. In this paper, we consider k-connectivity of wireless network and propose a simple global algorithm (GAFT(k)) which preserves the network k-connectivity and reduces the maximal transmission power (TP). The average degree expectation of the topology generated by GAFT(k) is O ((k + 3)(2)) and the expected weight is O ((k+3)(2)/12 root pi nn(e)) Based on GAFT(k), we further propose an efficient localised algorithm (LAFT(k)) which preserves k-vertex connectivity while maintaining bi-directionality of the network. In addition, both algorithms achieve significant reductions in energy consumption. Our simulation results show that GAFT/LAFT have better performance than some other current fault-tolerant protocols.