Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-054 | 5th May 2000 00:00

On the power assignment problem in radio networks



Given a finite set $S$ of points (i.e. the stations of a radio
network) on a $d$-dimensional Euclidean space and a positive integer
$1\le h \le |S|-1$, the \minrangeh{d} problem
consists of assigning transmission ranges to the stations so as
to minimize the total power consumption, provided that the transmission
ranges of the stations ensure the communication beween any pair
of stations in at most $h$ hops.

Two main issues related to this problem are considered in this paper:
the trade-off between the power consumption and the number of hops;
the computational complexity of the \minrangeh{d}\ problem.

As for the first question, we provide a lower bound on
the minimum power consumption of stations on the plane for constant
$h$. The lower bound is a function of $|S|$, $h$ and the minimum
distance over all the pairs of stations in $S$.
Then, we derive a constructive upper bound as a function of
$|S|$, $h$ and the maximum distance over all pairs of stations
in $S$ (i.e. the diameter of $S$).
It turns out that when the minimum distance between any two stations
is ``not too small'' (i.e. well spread instances) the upper bound
matches the lower bound.
Previous results for this problem were known only for very special
1-dimensional configurations (i.e., when points are arranged
on a line at unitary distance) [Kirousis, Kranakis, Krizanc, Pelc 1997].

As for the second question, we observe that the tightness of our upper
bound implies that \minrangeh{2} restricted to well spread instances
admits a polynomial time approximation algorithm.
Then, we also show that the same approximation result can be obtained
for random instances.
On the other hand, we prove that for $h=|S|-1$ (i.e. the
unbounded case) \minrangeh{2}\ is \np-hard and \minrangeh{3}
is $\apx$-complete.

ISSN 1433-8092 | Imprint