Multi Initiator Connected Dominating Set Construction for Mobile Ad Hoc Networks

Abstract

Connected dominating set (CDS) has been extensively used for routing and broadcast in mobile ad hoc networks. While existing CDS protocols are successful in constructing CDS of competitive size with localized information, they either lack the mechanism to properly handle nodal mobility or require lengthy period of time to recover when CDS becomes corrupted. In this thesis, a novel protocol, namely Multi-Initiator Connected Dominating Set protocol (MI-CDS), is proposed that constructs and maintains CDS of competitive size efficiently without introducing much communication overhead. The simulation results demonstrate that MI-CDS permits CDS to be available for the highest percentage of time in mobile network scenario compared with the other CDS protocols. Analytical model of the convergence time of MI-CDS as well as the number of messages it requires to construct CDS is built and validated by the simulation results.