Design and analysis of connected dominating set formation for topology control in wireless ad hoc networks

Author

Han, Bo ; Jia, Weijia

Author_Institution

Dept. of Comput. Sci., City Univ. of Hong Kong, Kowloon, China

fYear

2005

fDate

17-19 Oct. 2005

Firstpage

7

Lastpage

12

Abstract

To efficiently manage ad hoc networks, this paper proposes a novel distributed algorithm for connected dominating set (CDS) formation in wireless ad hoc networks with time and message complexity O(n). This Area algorithm partitions the nodes into different areas and selectively connects two dominators that are two or three hops away. Compared with previous well-known algorithms, we confirm the effectiveness of this algorithm through analysis and comprehensive simulation study. The number of nodes in the CDS formed by this Area algorithm is up to around 55% less than that constructed by others.

Keywords

ad hoc networks; distributed algorithms; mobility management (mobile radio); telecommunication control; telecommunication network topology; CDS; ad hoc network management; area algorithm; connected dominating set formation; distributed algorithm; topology control; wireless network; Ad hoc networks; Algorithm design and analysis; Clustering algorithms; Communication system control; Distributed algorithms; Intelligent networks; Mobile ad hoc networks; Network topology; Partitioning algorithms; Radio control;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Communications and Networks, 2005. ICCCN 2005. Proceedings. 14th International Conference on

ISSN

1095-2055

Print_ISBN

0-7803-9428-3

Type

conf

DOI

10.1109/ICCCN.2005.1523797

Filename

1523797