Lifetime optimization for reliable broadcast and multicast in wireless ad hoc networks

In this paper, we consider the reliable broadcast and multicast lifetime maximization problems in energy-constrained wireless ad hoc networks, such as wireless sensor networks for environment monitoring and wireless ad hoc networks consisting of laptops or PDAs with limited battery capacities. In packet loss-free networks, the optimal solution of lifetime maximization problem can be easily obtained by tree-based algorithms. In unreliable networks, we formulate them as min-max tree problems and prove them NP-complete by a reduction from a well-known minimum degree spanning tree problem. A link quality-aware heuristic algorithm called Maximum Lifetime Reliable Broadcast Tree (MLRBT) is proposed to build a broadcast tree that maximizes the network lifetime. The reliable multicast lifetime maximization problem can be solved as well by pruning the broadcast tree produced by the MLRBT algorithm. The time complexity analysis of both algorithms is also provided. Simulation results show that the proposed algorithms can significantly increase the network lifetime compared with the traditional algorithms under various distributions of error probability on lossy wireless links.