RCDS: A Ranking-Based Algorithm to Compute the CDS of the Ad Hoc Networks

Author

Shi, Dong ; Zhang, Xinming ; Zhu, Wenbo ; Wang, Enbo

Author_Institution

Dept. of Comput. Sci. & Technol., Univ. of Sci. & Technol. of China, Hefei

Volume

1

fYear

2008

fDate

2-4 Sept. 2008

Firstpage

591

Lastpage

596

Abstract

Construction of CDS (connected dominating set) is the foundation to build virtual backbone subnet or deploy layered routing in ad hoc or wireless sensor networks where packet flooding is extensively used. Current algorithm generally falls into two types: (1) cluster-based and (2) direct algorithm. This paper proposes a direct algorithm with linear time and message complexity. Our algorithm RCDS partitions the network nodes into dominators and dominatees. RCDS is a greedy algorithm which always chooses the farther and steadier node as future dominators. The experiment result shows that RCDS can construct smaller CDS than other algorithms.

Keywords

ad hoc networks; communication complexity; greedy algorithms; wireless sensor networks; ad hoc networks; cluster-based algorithm; connected dominating set; direct algorithm; greedy algorithm; linear time; message complexity; packet flooding; ranking-based algorithm; virtual backbone subnet; wireless sensor networks; Ad hoc networks; Bandwidth; Broadcasting; Clustering algorithms; Computer networks; Data structures; Information management; Partitioning algorithms; Peer to peer computing; Spine; ad hoc networks; backtrace; broadcast; connected dominating set;

fLanguage

English

Publisher

ieee

Conference_Titel

Networked Computing and Advanced Information Management, 2008. NCM '08. Fourth International Conference on

Conference_Location

Gyeongju

Print_ISBN

978-0-7695-3322-3

Type

conf

DOI

10.1109/NCM.2008.26

Filename

4624075