Connected Dominating Sets (CDS) are very useful in improving the routing for Mobile Ad Hoc Networks (MANETs). A CDS will act as a virtual backbone for communication in the ad hoc networks. Due to the importance of the CDS in routing, formation and selection of the CDS will have significance impact on routing and performance of the network. In the literature number of metrics was proposed to select and form a CDS in a network. In this paper, we studied and analyzed algorithms to construct CDS based on different metrics. The algorithms examined include Minimum Velocity-based CDS (MinV-CDS), Maximum Density CDS (MaxD-CDS), Node ID-based CDS (ID-CDS), Node Stability Index-based (NSI-CDS) and Strong-Neighborhood based CDS (SN-CDS). The performance metrics for the CDS are its Node size, Edge size, Lifetime, Hop count per path, Diameter and Energy index.

1. Charles E. Perkins, Ad Hoc Networking, Addison-Wesley, 2001.
2. C. K. Toh, Ad Hoc Mobile Wireless Networks: Protocols and Systems, Prentice Hall, 2001.
3. R. Bhaskar, J. Herranz, and F. Laguillaumie, "Efficient authentication for reactive routing protocols," in AINA '06: Proceedings of the 20th International Conference on Advanced Information Networking and Applications - Volume 2 (AINA'06). Washington, DC, USA: IEEE Computer Society, 2006, pp. 57–61.
4. C. Perkins and P. Bhagwat, "Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computer," ACM Sigcomm'94, August 1994.
5. K. U. R. Khan, R. U. Zaman, A. V. Reddy, K. A. Reddy, and T. S. Harsha, "An efficient dsdv routing protocol for wireless mobile ad hoc networks and its performance comparison," in EMS '08: Proceedings of the 2008 Second UKSIM European Symposium on Computer Modeling and Simulation. Washington, DC, USA: IEEE Computer Society, 2008, pp. 506–511.
6. A. Baayer, N. Enneya, and M. E. Koutbi, "A new criterion for mpr selection in olsr," in EATIS 07: Proceedings of the 2007 Euro American conference on Telematics and information systems. New York, NY, USA: ACM, 2007, pp. 1–6.
7. D. B. Johnson, D. A. Maltz, and J. Broch, "Dsr: the dynamic source routing protocol for multihop wireless ad hoc networks," Ad hoc networking, pp. 139–172, 2001.
8. M. Alilou and M. Dehghan, "Upgrading performance of dsr routing protocol in mobile ad hoc networks," in WEC (5), 2005, pp. 38–40.
9. C. Perkins and E. Royer, "Ad hoc on-demand distance vector routing," Mobile Computing System and Applications, February 1999.
10. S. Xu, Y. Mu, and W. Susilo, "Authenticated aodv routing protocol using one-time signature and transitive signature schemes," JNW, vol. 1, no. 1, pp. 47–53, 2006.
11. B. Karp and H. T. Kung, "Gpsr: greedy perimeter stateless routing for wireless networks," in MobiCom'00: Proceedings of the 6th annual international conference on Mobile computing and networking. New York, NY, USA: ACM Press, 2000, pp. 243–254.
12. R. Fonseca, S. Ratnasamy, J. Zhao, C. Ee, D. Culler, S. Shenker, and I. Stoica, "Beacon vector routing: Scalable point-to-point routing in wireless sensornets," in In NSDI, 2005.
13. A. Ward, A. Jones, and A. Hopper, "A new location technique for the active office," Personal Communications, IEEE, vol. 4, no. 5, pp. 42–47, 1997.
14. JH Lin, CR Dow, and SF Hwang. A distributed virtual backbone development scheme for ad-hoc wireless networks. Wireless Personal Communications, 27(3):215–233, 2003.
15. S Basagni, M Mastrogiovanni, A Panconesi, and C Petrioli. Localized protocols for ad hoc clustering and backbone formation: a performance comparison. Parallel and Distributed Systems, IEEE Transactions on DOI - 10. 1109/TPDS. 2006. 52, 17(4):292– 306, 2006.
16. J. Wu, Extended Dominating-Set-Based Routing in Ad Hoc Wireless Networks with Undirectional Links, IEEE Trans. on Parallel and Distributed Systems, pp. 866-881, Sept. 2002.
17. S. Ni, Y. Tseng, Y. Chen and J. Sheu: The Broadcast Storm Problem in a Mobile Ad Hoc Network, Proceedings of the 5th ACM International Conference on Mobile Computing and Networking, pp. 151-162, 1999.
18. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd Edition, MIT Press, September 2009.
19. A. Ephremides, J. Wieselthier, and D. Baker, A design concept for reliable mobile radio networks with frequency hopping signaling, Proceedings of the IEEE, 75, pp. 56-73, 1987.
20. Bevan Das and Vaduvur Bharghavan, Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets, International Conference on Communications, Montreal, Canada, June 1997.
21. Bevan Das, Raghupathy Sivakumar and Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a virtual backbone, IC3N'97, pp. 1-20, 1997.
22. Bevan Das, Raghupathy Sivakumar and Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, International Conference on Computers and Communications Networks, Las Vegas, NV. Sept. 1997.
23. S. Datta and I. Stojmenovic, Internal Node and Shortcut Based Routing with Guaranteed Delivery in Wireless Networks, Cluster Computing, 5(2), pp. 169-178, 2002.
24. X. Cheng, M. Ding, D. H. Du, and X. Jia, On The Construction of Connected Dominating Set in Ad Hoc Wireless Networks, to appear in Special Issue on Ad Hoc Networks of Wireless Communications and Mobile Computing, 2004.
25. J. Wu and B. Wu, A Transmission Range Reduction Scheme for Power-Aware Broadcasting in Ad Hoc Networks Using Connected Dominating Sets, Proc. of 2003 IEEE Semiannual Vehicular Technology Conference (VTC2003-fall), Oct. 2003.
26. J. Wu, B. Wu, and I. Stojmenovic, Power-Aware Broadcasting and Activity Scheduling in Ad Hoc Wireless Networks Using Connected Dominating Sets, Proc. of IASTED International Conference on Wireless and Optical Communication (WOC 2002), 2002.
27. J. Wu, B. Wu, and I. Stojmenovic, Power-Aware Broadcasting and Activity Scheduling in Ad Hoc Wireless Networks Using Connected Dominating Sets, Wireless Communications and Mobile Computing, a special issue on Research in Ad Hoc Networking, Smart Sensing, and Pervasive Computing, Vol. 3, No. 4, June 2003.
28. S. Y. Ni, Y. -C. Tseng, Y. -S. Chen and J. -P. Sheu, The broadcast storm problem in a mobile ad hoc network, Proc. MOBICOM, Seattle, Aug. 1999, pp. 151-162.
29. B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Wireless Networks, 8, pp. 481-494, 2002.
30. M. Ding, X. Cheng, and G. Xue, Aggregation tree construction in sensor networks, Proc. of IEEE VTC, 2003.
31. S. Guha and S. Khuller, Approximation algorithms for connected dominating sets. Algorithmica 1998; 20(4): 374–387
32. B. Das, R. Sivakumar and V. Bharghavan, Routing in ad-hoc networks using a spine, in: Proc. of International Conference on Computers and Communications Networks '97, Las Vegas, NV (September 1997).
33. K. M. Alzoubi, P. J. Wan and O. Frieder, Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks, MOBIHOC, EPFL Lausanne, Switzerland, 2002.
34. C. Adjih, P. Jacquet, and L. Viennot, "Computing connected dominated sets with multipoint relays," Ad Hoc & Sensor Wireless Networks, vol. 1, pp. 27–39, 2005.
35. J. Wu and H. Li, "On Calculating Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks," Proc. Third Int'l Workshop Discrete Algorithms and Methods for Mobile Computing and Comm. , pp. 7-14, 1999.
36. I. Stojmenovic, M. Seddigh and J. Zunic, Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks, in: Proc. of IEEE Hawaii Int. Conf. on System Sciences (January 2001).
37. V. Bharghavan and B. Das, Routing in ad hoc networks using minimum connected dominating sets, in: Proc. of International Conference on Communications'97, Montreal, Canada (June 1997) pp. 376–380.
38. Y. Li, M. T. Thai, F. Wang, C. W. Yi, P. J. Wang, and D. Z. Du, "On greedy construction of connected dominating sets in wireless networks," Special issue of Wireless Communications and Mobile Computing (WCMC), vol. 5, pp. 927–932, January 2005.
39. Rajiv Misra, Chittaranjan Mandal, Minimum Connected Dominating Set using a Collaborative Cover Heuristic for Adhoc Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, pp 292-302, vol. 21, March 2010.
40. N. Meghanathan, "Use of Minimum Node Velocity Based Stable Connected Dominating Sets for Mobile Ad hoc Networks," International Journal of Computer Applications: Special Issue on Recent Advancements in Mobile Ad hoc Networks, vol. 2, September 2010.
41. N. Meghanathan, "A Node Stability Index-based Connected Dominating Set Algorithm for Mobile Ad hoc Networks," The 3rd International Conference on Wireless & Mobile Networks, LNICST 84, p253-262, January 2012.
42. N. Meghanathan, "An Algorithm to Determine the Sequence of Stable Connected Dominating Sets in Mobile Ad hoc Networks," Proceedings of the 2nd Advanced International Conference on Telecommunications, Guadeloupe, French Caribbean, February 2006.
43. K. M. Alzoubi, P. -J Wan and O. Frieder, "Distributed Heuristics for Connected Dominating Set in Wireless Ad Hoc Networks," IEEE / KICS Journal on Communication Networks, Vol. 4, No. 1, pp. 22-29, 2002.
44. S. Butenko, X. Cheng, C. Oliviera and P. M. Paradlos, "A New Heuristic for the Minimum Connected Dominating Set Problem on Ad Hoc Wireless Networks," Recent Developments in Cooperative Control and Optimization, pp. 61-73, Kluwer Academic Publishers, 2004.
45. N. Meghanathan, "On the Stability of Paths, Steiner Trees and Connected Dominating Sets in Mobile Ad hoc Networks," Ad hoc Networks, Vol. 6, No. 5, pp. 744-769, July 2008.
46. N. Velummylum and N. Meghanathan, "On the Utilization of ID-based Connected Dominating Sets for Mobile Ad hoc Networks," International Journal of Advanced Research in Computer Science, vol. 1, no. 3, pp. 36-43, September-October 2010.
47. W. Su, S-J. Lee and M. Gerla, "Mobility Prediction and Routing in Ad hoc Wireless Networks," International Journal of Network Management, vol. 11, no. 1, 2001.

Connected Dominating Sets Mobile Ad Hoc Networks Routing Stability Density Strong Neighborhood