Minimum Total Communication Power Connected Dominating Set in Wireless Networks
作者： Deying Li , Donghyun Kim , Qinghua Zhu , Lin Liu , Weili Wu
DOI: 10.1007/978-3-642-31869-6_11
关键词:
摘要: A virtual backbone of a wireless network is connected subset nodes responsible for routing messages in the network. node likely to be exhausted much faster than others due its heavy duties. This situation can more aggravated if uses higher communication power form backbone. In this paper, we introduce minimum total dominating set (MTCPCDS) problem, whose goal compute with power. We show problem NP-hard and propose two distributed algorithms. Especially, first algorithm, MST-MTCPCDS, has worst case performance guarantee. simulations conducted evaluate our
springer.com
springerlink.com
utdallas.edu 参考文章(28)
Feifeng Zheng, Stanley P. Y. Fung, Wun-Tat Chan, Francis Y. L. Chin, Chung Keung Poon, Prudence W. H. Wong, Improved on-line broadcast scheduling with deadlines computing and combinatorics conference. pp. 320- 329 ,(2006) , 10.1007/11809678_34
Xianyue Li, Xiaofeng Gao, Weili Wu, A Better Theoretical Bound to Approximate Connected Dominating Set in Unit Disk Graph wireless algorithms systems and applications. pp. 162- 175 ,(2008) , 10.1007/978-3-540-88582-5_18
Xiaofeng Gao, Yaochun Huang, Zhao Zhang, Weili Wu, (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs Lecture Notes in Computer Science. pp. 551- 557 ,(2008) , 10.1007/978-3-540-69733-6_54
Matthew Hennessy, Robin Milner, On Observing Nondeterminism and Concurrency international colloquium on automata, languages and programming. pp. 299- 309 ,(1980) , 10.1007/3-540-10003-2_79
Christoph Ambühl, An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks Automata, Languages and Programming. pp. 1139- 1150 ,(2005) , 10.1007/11523468_92
Donghyun Kim, Yiwei Wu, Yingshu Li, Feng Zou, Ding-Zhu Du, Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks IEEE Transactions on Parallel and Distributed Systems. ,vol. 20, pp. 147- 157 ,(2009) , 10.1109/TPDS.2008.74
Stefan Funke, Alexander Kesselman, Ulrich Meyer, Michael Segal, A simple improved distributed algorithm for minimum CDS in unit disk graphs ACM Transactions on Sensor Networks. ,vol. 2, pp. 444- 453 ,(2006) , 10.1145/1167935.1167941
Xiuzhen Cheng, Xiao Huang, Deying Li, Weili Wu, Ding-Zhu Du, A Polynomial-Time Approximation Scheme for the Minimum-Connected Dominating Set in Ad Hoc Wireless Networks Networks. ,vol. 42, pp. 202- 208 ,(2003) , 10.1002/NET.10097
Michele Flammini, Alfredo Navarra, Ralf Klasing, Stéphane Pérennes, Improved approximation results for the minimum energy broadcasting problem Proceedings of the 2004 joint workshop on Foundations of mobile computing - DIALM-POMC '04. ,vol. 49, pp. 85- 91 ,(2004) , 10.1145/1022630.1022644
Peng-Jun Wan, Khaled M. Alzoubi, Ophir Frieder, Distributed construction of connected dominating set in wireless ad hoc networks Mobile Networks and Applications. ,vol. 9, pp. 141- 149 ,(2004) , 10.1023/B:MONE.0000013625.87793.13