On the power assignment problem in radio networks
Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri · 2000
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 h jSj \\Gamma 1, the Min dd h-Range Assignment 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 Min dd h-Range Assignment 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 jSj, h and the minimum distance over all the pairs of stations in S. Then, we derive a constructive upper bound as a function of jSj, h and the maximum distance over all pairs of stations in S (i.e. the d...