On the construction of energy-efficient maximum residual battery capacity broadcast trees in static ad hoc wireless networks

This work considers the problem of broadcast routing in a wireless ad hoc network from the viewpoint of energy efficiency. Each node in a wireless ad hoc network runs on a local energy source which has a limited energy life span. Thus, energy conservation is a critical issue in such networks. In this paper, we address the problem of finding a broadcast tree for a given network that maximizes the minimum residual battery capacity available among all nodes in the network. We call this problem the Maximum Residual Battery Capacity Broadcast Routing Problem (RBBP). We propose a new algorithm for RBBP and prove that RBBP is optimally solvable in polynomial time using the proposed algorithm. In addition, we show that the problem of finding a maximum residual battery capacity broadcast tree with minimum total energy consumption is NP-complete and we propose a new heuristic algorithm for this problem.