We propose an algorithm to determine stable connected dominating sets (CDS), based on node velocities, for mobile ad hoc networks (MANETs). The proposed minimum velocity-based CDS (MinV-CDS) algorithm prefers slow-moving nodes with lower velocity, rather than the usual approach of preferring nodes with a larger number of uncovered neighbors, i.e., larger density (referred to as MaxD-CDS). The construction of the MinV-CDS starts with the inclusion of the node having the lowest velocity, into the CDS. Once a node is added to the CDS, all its neighbors are said to be covered. The covered nodes are considered in the increasing order of their velocity, for inclusion in the CDS. If a node has lower velocity and is the next candidate node to be considered for inclusion in the CDS, it is added to the CDS if it has at least one neighbor that is yet to be covered. This procedure is repeated until all the nodes in the network are covered. Simulation results illustrate that the MinV-CDS has a significantly longer lifetime compared to MaxD-CDS. MinV-CDS also has a larger number of nodes and edges compared to MaxD-CDS and this helps to reduce the hop count as well as the end-to-end delay and improves the fairness of node usage.

1. Sinha, P., Sivakumar, R., and Bhargavan, V. 2001. Enhancing Ad hoc Routing with Dynamic Virtual Infrastructures. In Proceedings of the 20th IEEE INFOCOM Conference, 3, 1763-1772.
2. Wang, F., Min, M., Li, Y., and Du, D. 2005. On the Construction of Stable Virtual Backbones in Mobile Ad hoc Networks. In Proceedings of the IEEE International Performance Computing and Communications Conference.
3. Sakai, K., Sun, M.-T., and Ku, W.-S. 2008. Maintaining CDS in Mobile Ad hoc Networks. Lecture Notes in Computer Science. 5258 (Oct. 2008), 141-153.
4. Sheu, P.-R., Tsai, H.-Y., Lee, Y.-P., and Cheng, J. Y. 2009. On Calculating Stable Connected Dominating Sets Based on Link Stability for Mobile Ad hoc Networks. Tamkang Journal of Science and Engineering. 12, 4, 417-428.
5. Bao, L., and Garcia-Luna-Aceves, J. J. 2010. Stable Energy-aware Topology Management in Ad hoc Networks. Ad hoc Networks. 8, 3 (May 2010), 313-327.
6. Kuhn, F., Moscibroda, T., and Wattenhofer, R. 2004. Unit Disk Graph Approximation. In Proceedings of the ACM DIALM-POMC Joint Workshop on the Foundations of Mobile Computing, 17-23.
7. Alzoubi, K. M., Wan, P.-J., and Frieder, O. Distributed Heuristics for Connected Dominating Set in Wireless Ad hoc Networks. 2002. IEEE / KICS Journal on Communication Networks. 4, 1, 22-29.
8. Butenko, S., Cheng, X., Du, D.-Z., and Paradlos, P. M. 2002. On the Construction of Virtual Backbone for Ad hoc Wireless Networks. Cooperative Control: Models, Applications and Algorithms, 43-54.
9. Butenko, S., Cheng, X., Oliviera, C., and Paradlos, P. M. 2004. A New Heuristic for the Minimum Connected Dominating Set Problem on Ad hoc Wireless Networks. Recent Developments in Co-operative Control and Optimization, 61-73.
10. Meghanathan, N. 2006. An Algorithm to Determine the Sequence of Stable Connected Dominating Sets in Mobile Ad hoc Networks. In Proceedings of the 2nd Advanced International Conference on Telecommunications.
11. Meghanathan, N., and Farago, A. 2008. On the Stability of Paths, Steiner Trees and Connected Dominating Sets in Mobile Ad hoc Networks. Ad hoc Networks. 6, 5 (Jul. 2008), 744-769.
12. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms. 2nd Edition, MIT Press.
13. Meghanathan, N., and Sugumar, M. 2010. A Beaconless Minimum Interference Based Routing Protocol to Minimize End-to-End Delay per Packet for Mobile Ad hoc Networks. International Journal of Interdisciplinary Telecommunications and Networking. 2, 1 (Mar. 2010), 12-26.
14. Meghanathan, N., and Odunsi, A. 2010. Investigating the Scalability of the Fish-eye State Routing Protocol for Ad hoc Networks. Journal of Theoretical and Applied Information Technology. 12, 1 (Feb. 2010), 60-70.
15. Meghanathan, N. 2009. Multicast Extensions to the Location Prediction Based Routing Protocol for Mobile Ad hoc Networks. Lecture Notes of Computer Science, 5682, 190-199.
16. Bettstetter, C., Hartenstein, H., and Perez-Costa, X. 2004. Stochastic Properties of the Random-Way Point Mobility Model. Wireless Networks. 10, 5 (Sep. 2004), 555-567.

Connected Dominating Set Mobile Ad hoc Network Node Velocity Density