Natarajan Meghanathan and Ilin S. Dasari, Jackson State University, USA

The high-level contributions of this paper are: (1) A generic algorithm to determine connected dominating sets (CDS) for mobile ad hoc networks and its use to find CDS of different categories: maximum density-based (MaxD-CDS), node ID-based (ID-CDS) and stability-based (minimum velocity-based, MinV-CDS); (2) Performance comparison of the above three categories of CDS algorithms with respect to two categories of mobility models: random node mobility models (Random Waypoint model) and the grid-based vehicular ad hoc network (VANET) mobility models (City Section and Manhattan mobility models), with respect to the CDS Node Size and Lifetime. The performance of a CDS is observed to depend on the criteria used to form the CDS (i.e., the node selection criteria of the underlying algorithm) and the mobility model driving the topological changes. For each category of CDS, we identify the mobility model under which one can simultaneously maximize the lifetime and node size, with minimal tradeoff. For the two VANET mobility models, we also evaluate the impact of the grid block length on the CDS lifetime and node size.

Connected Dominating Sets, Mobile Ad hoc Networks, Algorithms, Mobility Models, Stability, Simulations