The minimum broadcast range assignment problem on linear multi-hop wireless networks

Given a set N of radio stations located on an Euclidean space, a source station s and an integer h (1 less than or equal to h less than or equal to N - 1), the minimum bounded-hop broadcast range assignment problem consists in finding a range assignment for N of minimum total power consumption that allows broadcast operations from s to every station in N in at most h hops. The problem is known to be NP-hard on d-dimensional spaces for any d greater than or equal to 2 (18th Annual Symp. on Theoretical Aspects of Computer Science (STACS'01), Lecture Notes in Computer Science, Vol. 1770, 2000, pp. 651-660.) and some efficient approximation algorithms have been given in Clementi et al. and Wann et al. (18th Annual Symp. on Theoretical Aspects of Computer Science (STACS'01), Lecture Notes in Computer Science, Vol. 1770, 2000, pp. 651-660, IEEE INFOCOM'01, 2001). In this paper, we address the case in which the stations are arbitrarily located along a line (i.e., the linear case). We provide the first polynomial-time algorithm that returns an optimal solution for any instance of the linear case. The algorithm works in O(hN(2)) time. (C) 2002 Published by Elsevier Science B.V.