A Generic Algorithm to Determine Connected Dominating Sets for Mobile Ad Hoc Networks and Performance Evaluation Under Different Mobility Models

The high-level contributions of this paper are: (1)\ud A generic algorithm to determine connected \uddominating sets (CDS) for mobile ad hoc networks an\udd its use to find CDS of different \udcategories: maximum density-based (MaxD-CDS), node \udID-based (ID-CDS) and stability-based \ud(minimum velocity-based, MinV-CDS); (2) Performance\ud comparison of the above three \udcategories of CDS algorithms with respect to two ca\udtegories of mobility models: random node \udmobility models (Random Waypoint model) and the gri\udd-based vehicular ad hoc network \ud(VANET) mobility models (City Section and Manhattan\ud mobility models), with respect to the \udCDS Node Size and Lifetime. The performance of a CD\udS is observed to depend on the criteria \udused to form the CDS (i.e., the node selection crit\uderia of the underlying algorithm) and the \udmobility model driving the topological changes. For\ud each category of CDS, we identify the \udmobility model under which one can simultaneously m\udaximize the lifetime and node size, with \udminimal tradeoff. For the two VANET mobility models\ud, we also evaluate the impact of the grid \udblock length on the CDS lifetime and node size