Back to Search Start Over

A Pure Localized Algorithm for Finding Connected Dominating Set in MANETs by Classification of Neighbors.

A Pure Localized Algorithm for Finding Connected Dominating Set in MANETs by Classification of Neighbors.

Authors :
Xiuzhen Cheng
Wei Li
Znati, Taieb
Hui Liu
Yi Pan
Stojmenovic, Ivan
Source :
Wireless Algorithms, Systems & Applications; 2006, p371-381, 11p
Publication Year :
2006

Abstract

An important problem in wireless ad hoc networks is to select a few nodes to form a virtual backbone that supports routing and other tasks such as area monitoring. Connected dominating set (CDS) has been proposed to approximate the virtual backbone. Although computing minimum CDS is known to be NP-hard, many distributed protocols have been presented to construct small CDS. However, these protocols are either too complicated, need non-local information or have slow convergence speed, are not adaptive to topology changes. In this paper, we propose a new pure localized algorithm for computing the approximate solution to the minimum CDS problem. The algorithm starts with a feasible and near-optimal CDS solution via marking process based on classification of neighbors, and removes vertices from this solution by redundancy elimination, until an approximate CDS is found. Both analytical and experimental results demonstrate that our algorithm has better performance than other distributed algorithms. Keywords: connected dominating set, distributed algorithm, pure localized algorithm, routing, wireless ad hoc networks. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISBNs :
9783540371892
Database :
Complementary Index
Journal :
Wireless Algorithms, Systems & Applications
Publication Type :
Book
Accession number :
32912332
Full Text :
https://doi.org/10.1007/11814856_36