Stability of Connected Dominating Sets in the Presence of Static Nodes in a Mobile Ad hoc Network

Abstract

The topology of mobile ad hoc networks (MANETs) change dynamically with time. Connected dominating sets (CDS) are considered to be an effective topology for network-wide broadcasts in MANETs as only the nodes that are part of the CDS need to broadcast the message and the rest of the nodes merely receive the message. However, with node mobility, a CDS does not exist for the entire duration of the network session and has to be regularly refreshed (CDS transition). In an earlier work, we had proposed a benchmarking algorithm to determine a sequence of CDSs (Maximum Stable CDS) such that the number of transitions is the global minimum. In this research, we study the performance (CDS Lifetime and CDS Node Size) of the Maximum Stable CDS when a certain fraction of the nodes in the network are static and compare the performance with that of the degree-based CDSs. We observe the lifetime of the Maximum Stable CDS to only moderately increase (by a factor of 2.3) as we increase the percentage of the static nodes in the network; on the other hand, the lifetime of the degree-based CDS increases significantly (as large as 13 times) as we increase the percentage of static nodes from 0 to 80.