Weighted broadcast in linear radio networks

The weighted version of the broadcast range assignment problem in ad hoc wireless network is studied. Efficient algorithms are presented for the unbounded and bounded-hop broadcast problems for the linear radio network, where radio stations are placed on a straight line. For the unbounded case of the problem, the proposed algorithm runs in O(n2) time and using O(n) space, where n is the number of radio stations in the network. For the h-hop broadcast problem, the time and space complexities of our algorithm are O(hn2logn) and O(hn), respectively. This improves time complexity of the existing results for the same two problems by a factor of n and , respectively [C. Ambuhl, A.E.F. Clementi, M.D. Ianni, G. Rossi, A. Monti, R. Silvestri, The range assignment problem in non-homogeneous static ad hoc networks, in: Proc. 18th Int. Parallel and Distributed Precessing Symposium, 2004].