An Effective Distributed Approximation Algorithm for Constructing Minimum Connected Dominating Set in Wireless Ad Hoc Networks

CC
CIT
2004
Fourth International Conference on Computer and Information Technology (CIT'04)
Abstract - An Effective Distributed Approximation Algorithm for Constructing Minimum Connected Dominating Set in Wireless Ad Hoc Networks

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Bo Gao Articles by Yuhang Yang Articles by Huiye Ma

Fourth International Conference on Computer and Information Technology (CIT'04)

Wuhan, China

September 14-September 16

ISBN: 0-7695-2216-5

	ASCII Text	x
	Bo Gao, Yuhang Yang, Huiye Ma, "An Effective Distributed Approximation Algorithm for Constructing Minimum Connected Dominating Set in Wireless Ad Hoc Networks," Computer and Information Technology, International Conference on, pp. 658-663, Fourth International Conference on Computer and Information Technology (CIT'04), 2004.

	BibTex	x
	@article{ 10.1109/CIT.2004.1357270, author = {Bo Gao and Yuhang Yang and Huiye Ma}, title = {An Effective Distributed Approximation Algorithm for Constructing Minimum Connected Dominating Set in Wireless Ad Hoc Networks}, journal ={Computer and Information Technology, International Conference on}, volume = {0}, year = {2004}, isbn = {0-7695-2216-5}, pages = {658-663}, doi = {http://doi.ieeecomputersociety.org/10.1109/CIT.2004.1357270}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computer and Information Technology, International Conference on TI - An Effective Distributed Approximation Algorithm for Constructing Minimum Connected Dominating Set in Wireless Ad Hoc Networks SN - 0-7695-2216-5 SP658 EP663 A1 - Bo Gao, A1 - Yuhang Yang, A1 - Huiye Ma, PY - 2004 KW - null VL - 0 JA - Computer and Information Technology, International Conference on ER -

Bo Gao, Shanghai Jiao Tong University

Yuhang Yang, Shanghai Jiao Tong University

Huiye Ma, Chinese University of Hong Kong

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CIT.2004.1357270

In this paper, we present a new distributed approximation algorithm that constructs a minimum connected dominating set (MCDS) for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm each node only requires the knowledge of its one-hop neighbors and there is only one shortest path connecting two dominators that are at most three hops away. Compared with other MCDS approximation algorithms, our algorithm shows better efficiency and performance than them.

Citation:

Bo Gao, Yuhang Yang, Huiye Ma, "An Effective Distributed Approximation Algorithm for Constructing Minimum Connected Dominating Set in Wireless Ad Hoc Networks," cit, pp.658-663, Fourth International Conference on Computer and Information Technology (CIT'04), 2004

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.