Proc. IASTED International Conference
on Parallel and Distributed Computing and Systems (PDCS 2001),
Anaheim, CA, August 2001, pp. 334--338.
Ömer Egecioglu and Teofilo F. Gonzalez
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.
omer@cs.ucsb.edu