Range assignment for energy efficient broadcasting in linear radio networks

Given a set S of n radio-stations located on a d-dimensional space, a source node s (∈S) and an integer h (1⩽h⩽n-1), the h-hop broadcast range assignment problem deals with assigning ranges to the members in S so that s can communicate with all other members in S in at most h-hops, and the total power consumption is minimum. The problem is known to be NP-hard for d⩾2. We propose an O(n2) time algorithm for the one dimensional version (d=1) of the problem. This is an improvement over the existing result on this problem by a factor of h [A.E.F. Clementi et al. The minimum broadcast range assignment problem on linear multi-hop wireless networks, Theoret. Comput. Sci. 299 (2003) 751–761].