Constructing minimum-energy broadcast trees in wireless ad hoc networks

In this paper we assume that a multihop wireless network (also called a wireless ad hoc network) consists of nodes whose transmitting powers are finitely adjustable. We con-sider two fundamental problems related to power consump-tion in this kind of network. One is the minimum-energy broadcast tree problem, which broadcasts a message from a source node to all the other nodes in the network such that the summation of transmission powers at all nodes is min-imized; and another is the minimum-energy multicast tree problem, which multicasts a message from a source node to the nodes in a given subset of nodes such that the sum-mation of the transmission powers at all involved nodes is minimized. We first show the minimum-energy broadcast tree prob-lem is NP-complete. We then present an approximate al-gorithm for the problem in a general setting, which delivers an approximate solution with a bounded performance guar-antee. The algorithm takes O((k + 1)1/n3/) time, where n is the number of nodes in the wireless network, k is the number of power levels at each node, and is constant with 0 < ≤ 1. For a special case of the problem where every node is equipped with the same type of battery, we pro-pose an approximate algorithm which has a better perfor-mance ratio than that in the general case setting, and the algorithm takes O(kn2 log n) time. We finally extend the technique for the minimum-energy broadcast tree problem to solve the minimum-energy multicast tree problem, which leads to a similar result. The technique adopted in this pa-per is to reduce the minimum-energy broadcast (multicast) tree problem on a wireless ad hoc network to an optimiza-tion problem on an auxiliary weighted graph, and solve the optimization problem on the auxiliary graph which in turn gives an approximate solution for the original problem.