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

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.