On the approximation ratio of the MST based heuristic for the energy-efficient broadcast problem in static ad-hoc radio networks
作者： A.K. Clementi , G. Huiban , G. Rossi , Y.C. Verhoeven , P. Penna
DOI: 10.1109/IPDPS.2003.1213407
关键词:
摘要: We present a technique to evaluate the approximation ratio on random instances of minimum energy broadcast problem in ad-hoc radio networks which is known be NP-hard and approximable within 12. Our relies polynomial-time computable lower bound optimal cost any instance. The main result this paper that has never achieved value greater than 6.4. Furthermore, worst values are for small network sizes. also provide clear geometrical motivation such good results.
sci-hub.se 参考文章(35)
Reuven Bar-Yehuda, Amos Israeli, Alon Itai, Multiple Communication in Multihop Radio Networks SIAM Journal on Computing. ,vol. 22, pp. 875- 887 ,(1993) , 10.1137/0222055
Gregory S. Lauer, Packet-radio routing Routing in communications networks. pp. 351- 396 ,(1995)
Allen Pahlavan, K, and Levesque, Wireless Information Networks ,(1995)
Mario Gerla, Mineo Takai, Rajive Bagrodia, Ken Tang, Rajat Ahuja, Lokesh Bajaj, GloMoSim: A Scalable Network Simulation Environment ,(2002)
Enrico Nardelli, Guido Proietti, Peter Widmayer, Maintaining a Minimum Spanning Tree Under Transient Node Failures european symposium on algorithms. pp. 346- 355 ,(2000) , 10.1007/3-540-45253-2_32
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
J.E. Yukich, Asymptotics for weighted minimal spanning trees on random points Stochastic Processes and their Applications. ,vol. 85, pp. 123- 138 ,(2000) , 10.1016/S0304-4149(99)00068-X
Brandon Dixon, Monika Rauch, Robert E. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time SIAM Journal on Computing. ,vol. 21, pp. 1184- 1192 ,(1992) , 10.1137/0221070
David Aldous, J. Michael Steele, Asymptotics for Euclidean minimal spanning trees on random points Probability Theory and Related Fields. ,vol. 92, pp. 247- 258 ,(1992) , 10.1007/BF01194923
J. Michael Steele, Growth Rates of Euclidean Minimal Spanning Trees With Power Weighted Edges Annals of Probability. ,vol. 16, pp. 1767- 1787 ,(1988) , 10.1214/AOP/1176991596