Improved algorithm for minimum cost range assignment problem for linear radio networks
作者： Gautam K. Das , Sasthi C. Ghosh , Subhas C. Nandy
DOI: 10.1007/978-3-540-30536-1_46
关键词:
摘要: The unbounded version of the 1D range assignment problem for radio-stations is studied. Here a set n radio stations are placed arbitrarily on line. objective to assign ranges these such that total power consumption minimum. A simple incremental algorithm proposed which produces optimum solution in O(n3) time and O(n2) space. This improves running best known existing by factor n.
springer.com
sci-hub.st 参考文章(13)
D. Krizanc, A. Pelc, E. Kranakis, Fault-tolerant broadcasting in radio networks Lecture Notes in Computer Science. pp. 283- 294 ,(1998)
Allen Pahlavan, K, and Levesque, Wireless Information Networks ,(1995)
Krzysztof Diks, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, The Impact of Knowledge on Broadcasting Time in Radio Networks european symposium on algorithms. pp. 41- 52 ,(1999) , 10.1007/3-540-48481-7_5
Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri, The Power Range Assignment Problem in Radio Networks on the Plane symposium on theoretical aspects of computer science. ,vol. 1770, pp. 651- 660 ,(2000) , 10.1007/3-540-46541-3_54
Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Fault-Tolerant Broadcasting in Radio Networks (Extended Abstract) european symposium on algorithms. pp. 283- 294 ,(1998) , 10.1007/3-540-68530-8_24
I. Chlamtac, A. Farago, Making transmission schedules immune to topology changes in multi-hop packet radio networks IEEE ACM Transactions on Networking. ,vol. 2, pp. 23- 29 ,(1994) , 10.1109/90.282605
Leszek Gąsieniec, Wojciech Rytter, Bogdan S. Chlebus, Andrzej Pelc, Alan Gibbons, Deterministic broadcasting in unknown radio networks symposium on discrete algorithms. pp. 861- 870 ,(2000) , 10.5555/338219.338652
Mostafa A. Bassiouni, Chun-Chin Fang, Dynamic channel allocation for linear macrocellular topology acm symposium on applied computing. pp. 382- 388 ,(1999) , 10.1145/298151.298391
Rudolf Mathar, J�rgen Mattfeldt, Optimal transmission ranges for mobile communication in linear multihop packet radio networks Wireless Networks. ,vol. 2, pp. 329- 342 ,(1996) , 10.1007/BF01262051
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Power consumption in packet radio networks Theoretical Computer Science. ,vol. 243, pp. 289- 305 ,(2000) , 10.1016/S0304-3975(98)00223-0