CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

A Survey of Connected Dominating Set Algorithms for Virtual Backbone Construction in Ad Hoc Networks

by P. S. Vinayagam
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 143 - Number 9
Year of Publication: 2016
Authors: P. S. Vinayagam
10.5120/ijca2016910349

P. S. Vinayagam . A Survey of Connected Dominating Set Algorithms for Virtual Backbone Construction in Ad Hoc Networks. International Journal of Computer Applications. 143, 9 ( Jun 2016), 30-36. DOI=10.5120/ijca2016910349

@article{ 10.5120/ijca2016910349,
author = { P. S. Vinayagam },
title = { A Survey of Connected Dominating Set Algorithms for Virtual Backbone Construction in Ad Hoc Networks },
journal = { International Journal of Computer Applications },
issue_date = { Jun 2016 },
volume = { 143 },
number = { 9 },
month = { Jun },
year = { 2016 },
issn = { 0975-8887 },
pages = { 30-36 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume143/number9/25107-2016910349/ },
doi = { 10.5120/ijca2016910349 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:45:55.164814+05:30
%A P. S. Vinayagam
%T A Survey of Connected Dominating Set Algorithms for Virtual Backbone Construction in Ad Hoc Networks
%J International Journal of Computer Applications
%@ 0975-8887
%V 143
%N 9
%P 30-36
%D 2016
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Ad hoc networks lack pre-designated routers and physical infrastructure, which makes routing in these networks a challenging task. To overcome the problems associated with this, virtual backbone has been proposed as the routing infrastructure of ad hoc networks. A well-known and well researched approach for constructing virtual backbone is Connected Dominating Set (CDS). It overcomes the broadcast storm problem and facilitates routing. In this paper, the focus is on the various CDS construction algorithms that have been put forth in the literature. A comparison of the major works relating to CDS construction is provided, emphasizing the type of algorithm, technique employed, performance metric used and the outcome achieved.

References
  1. Prasad, R., & Mihovska, A. (2009). New Horizons in Mobile and Wireless Communications, Volume 4: Ad Hoc Networks and Pans. Boston, London: Artech House.
  2. Wu, J., & Li, H. (2001). A dominating-set-based routing scheme in ad hoc wireless networks. Telecommunication Systems, 18(1-3), 13-36.
  3. Ephremides, A., Wieselthier, J. E., & Baker, D. J. (1987). A design concept for reliable mobile radio networks with frequency hopping signaling. Proceedings of the IEEE, 75(1), 56-73.
  4. Kim, D., Wu, Y., Li, Y., Zou, F., & Du, D. (2009). Constructing minimum connected dominating sets with bounded diameters in wireless networks. IEEE Transactions on Parallel and Distributed Systems, 20(2), 147-157.
  5. Kim, D., Gao, X., Zou, F., & Wu, W. (2011). Construction of fault-tolerant virtual backbones in wireless networks. In Y. Xiao, F. H. Li & H. Chen (Eds.), Handbook of Security and Networks (pp. 465-486). Singapore: World Scientific.
  6. Wang, W., Kim, D., An, M. K., Gao, W., Li, X., Zhang, Z., & Wu, W. (2013). On construction of quality fault-tolerant virtual backbone in wireless networks. IEEE/ACM Transactions on Networking, 21(5), 1499-1510.
  7. Li, Y., Wu, Y., Ai, C., & Beyah, R. (2012). On the construction of k-connected m-dominating sets in wireless networks. Journal of Combinatorial Optimization, 23(1), 118-139.
  8. Zhang, N., Shin, I., Zou, F., Wu, W., & Thai, M. T. (2008). Trade-off scheme for fault tolerant connected dominating sets on size and diameter. Proceedings of the 1st ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing (FOWANC’08). Hong Kong SAR, China (pp. 1-8).
  9. Sheu, P., Tsai, H., Lee, Y., & Cheng, J. (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.
  10. Han, B., Zhang, L., & Jia, W. (2010). Connected dominating set for topology control in ad hoc networks. In L. T. Yang, A. B. Waluyo, J. Ma, L. Tan, & B. Srinivasan (Eds.), Mobile Intelligence (pp. 26-42). New Jersey: Wiley.
  11. Cheng, X., Ding, M., Du, D. H., & Jia, X. (2006). Virtual backbone construction in multihop ad hoc wireless networks. Wireless Communications and Mobile Computing, 6(2), 183-190.
  12. Yu, J., Wang, N., Wang, G., & Yu, D. (2013). Connected dominating sets in wireless ad hoc and sensor networks – A comprehensive survey. Computer Communications, 36(2), 121-134.
  13. Li, Y., Zhu, S., Thai, M., & Du, D. (2004). Localized construction of connected dominating set in wireless networks. Proceedings of US National Science Foundation International workshop on Theoretical Aspects of Wireless Ad Hoc, Sensor and Peer-to-Peer Networks (TAWN’04). Chicago, USA.
  14. Kamei, S., & Kakugawa, H. (2007). A self-stabilizing distributed approximation algorithm for the minimum connected dominating set. IEEE International Parallel and Distributed Processing Symposium (IPDPS 2007). Rome (pp. 1 – 8).
  15. Gao, B., Ma, H., & Yang, Y. (2005). A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks. In J. Cao, L. T. Yang, M. Guo, & F. Lau (Eds.), Parallel and Distributed Processing and Applications (pp. 352–356). Berlin Heidelberg: Springer.
  16. Blum, J., Ding, M., Thaeler, A., & Cheng, X. (2004). Connected dominating set in sensor networks and MANETs. In D. Z. Du & P. Pardalos (Eds.), Handbook of Combinatorial Optimization (pp. 329 – 369). US: Springer.
  17. Cardei, M., Cheng, X., Cheng, X., & Du, D. (2002). Connected domination in multihop ad hoc wireless networks. Proceedings of the 6th Joint Conference on Information Science (JCIS). North Carolina (pp. 251-255).
  18. Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A guide to the theory of NP-completeness New York: W. H. Freeman & Co.
  19. Wu, J. (2002). Dominating-set-based routing in ad hoc wireless networks. In I. Stojmenovic´ (Ed.), Handbook of Wireless Networks and Mobile Computing (pp. 425-450). New York: Wiley.
  20. Kim, B., Yang, J., Zhou, D., & Sun, M. (2005). Energy-aware connected dominating set construction in mobile ad hoc networks. Proceedings of 14th International Conference on Computer Communications and Networks (ICCCN 2005). San Diego, CA, USA (pp. 229-234).
  21. Sakai, K., Huang, S. C. H., Ku, W., Sun, M., & Cheng, X. (2011). Timer-based CDS construction in wireless ad hoc networks. IEEE Transactions on Mobile Computing, 10(10), 1388-1402.
  22. Zhou, D., Sun, M., & Lai, T. (2005). A timer-based protocol for connected dominating set construction in IEEE 802.11 multihop mobile ad hoc networks. Proceedings of the 2005 Symposium on Applications and the Internet (SAINT’05). Trento, Italy (pp. 2-8).
  23. Guha, S., & Khuller S. (1998). Approximation algorithms for connected dominating sets. Algorithmica, 20(4), 374-387.
  24. Sivakumar, R., Das, B., & Bharghavan, V. (1998). The clade vertebrata: spines and routing in ad hoc networks. Proceedings of Third IEEE Symposium on Computers and Communications (ISCC '98). Athens (pp. 599-605).
  25. Stojmenovic, I., Seddigh, M., & Zunic, J. (2002). Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks. IEEE Transactions on Parallel And Distributed Systems, 13(1), 14-25.
  26. Alzoubi, K. M., Wan, P., & Frieder, O. (2002). Distributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications and Networks, 4(1), 22-29.
  27. Wu, J., Dai, F., Gao, M., & Stojmenovic, I. (2002). On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks. Journal of Communications and Networks, 4(1), 59-70.
  28. Alzoubi, K. M., Wan, P., & Frieder, O. (2002). Message-optimal connected dominating sets in mobile ad hoc networks. Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc'02). EPFL Lausanne, Switzerland (pp. 157 – 164).
  29. Wan, P., Alzoubi, K. M., & Frieder, O. (2004). Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Networks and Applications, 9(2), 141-149.
  30. Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., & Ko, K. (2004). A greedy approximation for minimum connected dominating sets. Theoretical Computer Science, 329(1-3), 325-330.
  31. Mohammed, K., Gewali, L., & Muthukumar, V. (2005). Generating quality dominating sets for sensor network. Proceedings of the Sixth International Conference on Computational Intelligence and Multimedia Applications (ICCIMA’05). Las Vegas, Nevada (pp. 204 – 211).
  32. Funke, S., Kesselman, A., Meyer, U., & Segal, M. (2005). A simple improved distributed algorithm for minimum CDS in unit disk graphs. IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob'2005). Canada (pp. 220 – 223).
  33. Zongkai, Y., Dasheng, Z., Yuming, W., & Jianhua, H. (2005). An efficient distributed algorithm for connected dominating set construction in wireless sensor networks. Journal of Electronics(China), 22(6), 671-675.
  34. Kassaei, H., Mehrandish, M., Narayanan, L., & Opatrny, J. (2009). A new local algorithm for backbone formation in ad hoc networks. Proceedings of the 6th ACM Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN'09). Tenerife, Canary Islands, Spain (pp. 49-57).
  35. Yin, B., Shi, H., & Shang, Y. (2011). An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks. Journal of Parallel and Distributed Computing, 71(1), 27-39.
  36. Chakradhar, P., & Yogesh, P. (2013). Energy efficient minimum connected dominating set algorithm for MANETs. 2013 International Conference on Recent Trends in Information Technology (ICRTIT). Chennai (pp. 270 – 276).
  37. Ting-jun, S., Xu, S., & Xu-ming, F. (2014). A virtual backbone construction algorithm based on connected dominating set in wireless sensor networks. International Conference on Computer, Communications and Information Technology (CCIT 2014). Beijing, China (pp. 156-159).
  38. Fu, D., Han, L., Liu, L., Gao, Q., & Feng, Z. (2015). An efficient centralized algorithm for connected dominating set on wireless networks. Procedia Computer Science, 56, 162-167.
Index Terms

Computer Science
Information Sciences

Keywords

Ad hoc network Connected Dominating Set Virtual backbone

Powered by PhDFocusTM