An Algorithm to Determine Stable Connected Dominating Sets for Mobile Ad hoc Networks using Strong Neighborhoods

We propose an algorithm to determine stable connected dominating sets (CDS) for mobile ad hoc networks using the notion of strong neighborhood (SN). The SN-CDS algorithm takes an input parameter called the Threshold Neighborhood Distance Ratio (TNDR); for an edge to be part of a strong neighborhood-based topology, the ratio of the physical Euclidean distance between the end nodes of the edge to that of the transmission range per node has to be less than or equal to the TNDR. The algorithm prefers to include nodes (into the SN-CDS) in the decreasing order of the number of uncovered strong neighbors until all nodes in the network are covered. We observe the SN-CDS (TNDR < 1) to have a significantly longer lifetime than a maximum density-based CDS (MaxD-CDS with TNDR = 1.0); the tradeoff being a slightly larger CDS Node Size and hop count per path.