Constructing minimum-energy broadcast trees in wireless ad hoc networks

Abstract

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 consider two fundamental problems related to power consumption in this kind of network. One is the minimum-energy broadcast tree problem, which broadcast 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 minimized; 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 summation of the transmission powers at all involved nodes is minimized. We first show the minimum-energy broadcast tree problem is NP-complete. We then present an approximate algorithm for the problem in a general setting, which delivers an approximate solution with a bounded performance guarantee. The algorithm takes O((k + 1)1/εn3/ε) time, where n is the number of nodes in the wireless network, κ 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 propose an approximate algorithm which has a better performance 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 paper is to reduce the minimum-energy broadcast (multicast) tree problem on a wireless ad hoc network to an optimization 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.