Minimal connected dominating set algorithms and application for a MANET routing protocol

Author

Lin, Tao ; Midkiff, Scott F. ; Park, Jahng S.

Author_Institution

Bradley Dept. of Electr. & Comput. Eng., Virginia Polytech. Inst. & State Univ., Blacksburg, VA, USA

fYear

2003

fDate

9-11 April 2003

Firstpage

157

Lastpage

164

Abstract

Blind broadcast in a wireless ad hoc network means any mobile node will rebroadcast all received broadcast messages. One node may receive the same copy of a message from more than one neighbor, so unnecessary overhead is introduced. A connected dominating set (CDS) can be used to reduce broadcast overhead. We propose a proactive link state routing protocol, integrated with CDS discovery algorithms, as a promising approach for routing in wireless ad hoc networks. This paper presents approximation algorithms to find a minimal CDS for a given network. A prototype of a proactive link state routing protocol integrated with CDS algorithms is introduced. Both simulation and analytical results indicate better performance than other algorithms.

Keywords

ad hoc networks; approximation theory; land mobile radio; radio links; routing protocols; set theory; CDS discovery algorithms; MANET routing protocol; approximation algorithms; blind broadcast; broadcast messages; broadcast overhead reduction; connected dominating set; connected dominating set algorithms; mobile ad hoc networks; mobile node; proactive link state routing protocol; simulation results; wireless ad hoc networks; Algorithm design and analysis; Analytical models; Application software; Approximation algorithms; Bandwidth; Broadcasting; Mobile ad hoc networks; Mobile computing; Prototypes; Routing protocols;

fLanguage

English

Publisher

ieee

Conference_Titel

Performance, Computing, and Communications Conference, 2003. Conference Proceedings of the 2003 IEEE International

ISSN

1097-2641

Print_ISBN

0-7803-7893-8

Type

conf

DOI

10.1109/PCCC.2003.1203695

Filename

1203695