Regular PapersNo Access

IMPROVED ALGORITHM FOR MINIMUM COST RANGE ASSIGNMENT PROBLEM FOR LINEAR RADIO NETWORKS

GAUTAM K. DAS

Indian Statistical Institute, Kolkata - 700 108, India

Search for more papers by this author

SASTHI C. GHOSH

Dept. of Electrical and Computer Engineering, McMaster University, Ontario, Canada - L8S4K1, Canada

Search for more papers by this author

, and

SUBHAS C. NANDY

Indian Statistical Institute, Kolkata - 700 108, India

Search for more papers by this author

https://doi.org/10.1142/S0129054107004863Cited by:3 (Source: Crossref)

Abstract

In the unbounded version of the range assignment problem for all-to-all communication in 1D, a set of n radio-stations are placed arbitrarily on a line; the objective is to assign ranges to these radio-stations such that each of them can communicate with the others (using at most n - 1 hops) and the total power consumption is minimum. A simple incremental algorithm for this problem is proposed which produces optimum solution in O(n³) time and O(n²) space. This is an improvement in the running time by a factor of n over the best known existing algorithm for the same problem.

A preliminary version of this work appeared in Proc. 6th. Int. Workshop on Distributed Computing (IWDC 2004), LNCS 3326, pp. 412-423, 2004.

Keywords:

References

I. Chlamtac and A. Farago, IEEE/ACM Trans. on Networking 2, 23 (1994), DOI: 10.1109/90.282605. Crossref, Web of Science, Google Scholar
B. S. Chlebuset al., Deterministic broadcasting in unknown radio networks, Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms (2000) pp. 861–870. Google Scholar
A. E. F. Clementi, P. Penna and R. Silvestri, The power range assignment problem in radio networks on the plane, Proc. Symposium on Theoretical Aspects of Computer Science, LNCS 1770 (2000) pp. 651–660. Google Scholar
K. Pahlavan and A. Levesque , Wireless Information Networks ( John Wiley , New York , 1995 ) . Google Scholar
S. Ulukus and R. D. Yates, IEEE Trans. Communications 46, 784 (1996), DOI: 10.1109/26.681417. Crossref, Web of Science, Google Scholar
L. Kirousiset al., Theoretical Computer Science 243, 289 (2000), DOI: 10.1016/S0304-3975(98)00223-0. Crossref, Web of Science, Google Scholar
R. Mathar and J. Mattfeldt, Wireless Networks 2, 329 (1996), DOI: 10.1007/BF01262051. Crossref, Web of Science, Google Scholar
A. E. F. Clementiet al., Algorithmica 35, 95 (2003), DOI: 10.1007/s00453-002-0985-2. Crossref, Web of Science, Google Scholar
A. E. F. Clementi, M. Di Ianni and R. Silvestri, Theoretical Computer Science 299, 751 (2003), DOI: 10.1016/S0304-3975(02)00538-8. Crossref, Web of Science, Google Scholar
G. K. Das, S. Das and S. C. Nandy, Theoretical Computer Science 352, 332 (2006), DOI: 10.1016/j.tcs.2005.11.046. Crossref, Web of Science, Google Scholar
M. A. Bassiouni and C. Fang, Dynamic channel allocation for linear macrocellular topology, Proc. ACM Symposium on Applied Computing (1998) pp. 382–388. Google Scholar
K. Dikset al., The impact of knowledge on broadcasting time in radio networks, Proc. Annual European Symposium on Algorithms, LNCS 1643 (1999) pp. 41–52. Google Scholar
E. Kranakis, D. Krizanc and A. Pelc, Fault-tolerant broadcasting in radio networks, Proc. Annual European Symposium on Algorithms, LNCS 1461 (1998) pp. 283–294. Google Scholar