An Effective Algorithm for Computing Energy-Efficient Broadcasting Trees in All-Wireless Networks
Doina Bein and S.Q. Zheng
Given a wireless network in which node positions are fixed and a specific source node r in the network, the minimum energy broadcasting problem (MEB) asks each node to adjust its transmission range to create a spanning tree rooted at r with minimum total energy. This problem is NP-complete for both general graphs and Euclidean space graphs.We propose a heuristic algorithm called Greedy Tradeoff (GT) for the MEB problem.We compare the broadcasting trees computed by our GT algorithm with the broadcasting trees computed by two previously proposed algorithms, BIP and IMBM, in terms of total power, tree height, and the number of leave nodes. Our results show that the performance of our GT algorithm is better than the performances of BIP and IMBM.
Keywords: broadcast algorithm, energy efficiency, minimum-energy broadcast, performance analysis, spanning tree, wireless ad hoc network