Abstract:

For problem of power and fault tolerance in wireless ad hoc networks, a greedy randomized adaptive search procedure (GRASP) heuristic algorithm based on the path re-linking was proposed. The algorithm sets up communication path between two communicating nodes is two at least by constructing two dual-connected graphs, so as to improve the ability of fault tolerance. On the basis of dual-network connectivity, the optimal value of power distribution can be obtained by controlling power to conduct local search operation. Therefore, the purpose to optimize energy consumption of the entire network can be realized. Simulations on the asymmetrical test randomly generated problems show that the proposed algorithm has reduced the total energy consumption with 37.85%, 5.39% respectively on Euclidean instance and 74.63%, 3.15% respectively on random instance comparing with MST-aug algorithm and greedy algorithm. It reduces edges interference and nodes interference, which indicates that it is suitable to be applied into wireless ad hoc networks with high requirements of fault tolerance.

Key words: wireless ad hoc networks, fault tolerance, optimizing the energy consumption, heuristics algorithm, path relink