In this paper we study the problem of assigning transmission ranges to the
nodes of a multihop packet radio network so as to minimize the total power
consumed under the constraint that adequate power is provided to the nodes
to ensure that the network is strongly connected (i.e., each node can commu
nicate along some path in the network to every other node). Such assignment
of transmission ranges is called complete. We also consider the problem of
achieving strongly connected bounded diameter networks.
For the case of n + 1 colinear points at unit distance apart (the unit chai
n) we give a tight asymptotic bound for the minimum cost of a range assignm
ent of diameter h when h is a fixed constant and when h greater than or equ
al to(1 + epsilon) log n, for some constant epsilon > 0. When the distances
between the colinear points are arbitrary, we give an O(n(4)) time dynamic
programming algorithm for finding a minimum cost complete range assignment
. For points in three dimensions we show that the problem of deciding wheth
er a complete range assignment of a given cost exists, is NP-hard.
For the same problem we give an O(n(2)) time approximation algorithm which
provides a complete range assignment with cost within a factor of two of th
e minimum. The complexity of this problem in two dimensions remains open, w
hile the approximation algorithm works in this case as well. (C) 2000 Elsev
ier Science B.V. All rights reserved.