Minimum-energy Broadcast in Simple Graphs with Limited Node Power

Abstract

The minimum-energy broadcasting problem in wireless networks consists of finding a transmission radius vector for all stations in such a way that the total transmission power of the whole network is least possible. The minimum-energy broadcast problem may by modeled by an edge weighted complete graph in which each vertex in the graph represents a station and the weight of the edge is distance between the two nodes it joins. This is the weighted graph version of the minimum-energy broadcast problem. Wan, Calinescu, Li and Frieder showed that for arbitrary weights, this problem is NP-hard, and also hard to approximate. In this paper we show that the weighted graph minimum-energy broadcast problem is NP-hard in metric space when transmissions are restricted to a given set of power levels by means of an upper bound d on the allowed transmission radius. This restriction is justified because it is unrealistic to expect transmissions with unbounded power which may be needed in an optimal solution for large diameter networks. We also show that our problem can be solved in polynomial time when there is an optimal solution with a fixed number of transmitter nodes.