The minimum-energy broadcast problem: A case study in symmetric wireless ad hoc networks

Minimizing energy consumption in communication is a crucial problem in wireless ad hoc networks, as in most cases the nodes are powered by battery only. The minimum-energy broadcast problem is studied in this paper, for which it is well known that the broadcast nature of the radio transmission can be exploited to optimize energy consumption. This problem has been studied in a lot of literature on different models. In this paper a symmetric network is considered. First we propose an approximation algorithm, which takes O(mnα(m,n)) time, where m is the number of links, n is the number of nodes and α is the inverse of Ackerman's function. The algorithm delivers a broadcast tree with energy consumption being at most 2H_n-1 times of the optimal solution, where H_n-1 is the (n-1)^st harmonic number. Since it has been proved that the minimum energy broadcast problem in general graph case (including symmetric case) cannot be approximated within a sub-logarithmic factor (unless P=NP), so the algorithm is almost optimal. For a special case where each node is equipped with the same type of battery it improves the known O(log³ n)-approximation algorithm. Moreover for some asymmetric but nearly symmetric network, the algorithm can also be applied with O(In n) performance guarantee. Finally a special case is studied, where the degree of network is bounded by a constant Δ and the ratio of the maximum transmission energy to the minimum transmission energy is bounded by another constant C. For the case we devise a 2(C + H_Δ-1)-approximation algorithm.