Call for Paper - July 2022 Edition
IJCA solicits original research papers for the July 2022 Edition. Last date of manuscript submission is June 20, 2022. Read More

An Articulation Point based Approach to Create Virtual Backbone in Mobile Ad Hoc Networks

International Journal of Computer Applications
© 2011 by IJCA Journal
Volume 33 - Number 2
Year of Publication: 2011
Rajendra Singh Kushwah
Anand Swaroop Saxena

Rajendra Singh Kushwah and Anand Swaroop Saxena. Article: An Articulation Point based Approach to Create Virtual Backbone in Mobile Ad Hoc Networks. International Journal of Computer Applications 33(2):1-5, November 2011. Full text available. BibTeX

	author = {Rajendra Singh Kushwah and Anand Swaroop Saxena},
	title = {Article: An Articulation Point based Approach to Create Virtual Backbone in Mobile Ad Hoc Networks},
	journal = {International Journal of Computer Applications},
	year = {2011},
	volume = {33},
	number = {2},
	pages = {1-5},
	month = {November},
	note = {Full text available}


Connected Dominating Set is used for constructing virtual backbones in mobile ad hoc network. Virtual Backbone works as is a core group of mobile nodes. All the communication in MANET held with the help of Virtual Backbone. Mobile Ad hoc Network use undirected graph as more suitable model. In this paper we have proposed an algorithm to find Virtual Back Bone in Undirected Graph for MANET. Proposed algorithm is based on the computation of articulation point (AP) in Undirected Graph. Constructing a virtual backbone in MANET is an important issue because it reduces unnecessary message transmission or flooding in the network. It helps in to reduces channel bandwidth consumption, the Energy consumption and provide better resource management.


  • M. Abolhasan, T. Wysocki and E. Dutkiewicz, “A Review of Routing Protocols for Mobile Ad hoc Networks,” Ad hoc Networks, vol. 2, no. 1, pp. 1-22, January 2004.
  • N. Meghanathan, “Survey and Taxonomy of Unicast Routing Protocols for Mobile Ad hoc Networks,” The International Journal on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks, vol. 1, no. 1, pp. 1-21, December 2009.
  • K. M. Alzoubi, P. J. Wan and O. Frieder, “New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks,” Proceedings of the 35th Hawaii International Conference on System Sciences, pp. 3849-3855, 2002.
  • F. Kuhn, T. Moscibroda and R. Wattenhofer, “Unit Disk Graph Approximation,” Proceedings of the ACM DIALM-POMC Joint Workshop on the Foundations of Mobile Computing, pp. 17-23, Philadelphia, October 2004.
  • Y. P. Chen and A. L. Liestman, “Approximating Minimum Size Weakly-Connected Dominating Sets for Clustering Mobile Ad Hoc Networks,” Proceedings of the ACM International Symposium on Mobile Ad hoc Networking and Computing, Lausanne, Switzerland, June 9-11, 2002.
  • 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. International Journal of Wireless & Mobile Networks (IJWMN) Vol. 3, No. , April 2011
  • 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.
  • S. Butenko, X. Cheng, D.-Z. Du and P. M. Paradlos, “On the Construction of Virtual Backbone for Ad Hoc Wireless Networks,” Cooperative Control: Models, Applications and Algorithms, pp. 43-54, Kluwer Academic Publishers, 2002.
  • 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.
  • 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.
  • Online. Available:
  • 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.
  • A. Ward, A. Jones, and A. Hopper, “A new location technique for the active office,” Personal Communications, IEEE
  • see also IEEE Wireless Communications, vol. 4, no. 5, pp. 42–47, 1997.
  • Online. Available: all.jsp?arnumber=626982
  • 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.
  • C.Perkins and P.Bhagwat, “Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computer,” ACM Sigcomm’94, August 1994.
  • 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.
  • 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.
  • 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.
  • M. Alilou and M. Dehghan, “Upgrading performance of dsr routing protocol in mobile ad hoc networks,” in WEC (5), 2005, pp. 38–40.
  • C.Perkins and E.Royer, “Ad hoc on-demand distance vector routing,” Mobile Computing System and Applications, February 1999.
  • 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.
  • B. N. Clark, C. J. Colbourn and D. S. Johnson, “Unit disk graphs”, Discrete Math, Vol. 86, pages 165–177, 1990
  • G. N. Purohit, S. Verma and U. Sharma, “Powers of a Graph and Associated Graph Labeling”, (IJCNS) International Journal of Computer and Network Security, Vol. 2, No. 4, pages 45-49, April 2010
  • K. Alzoubi, P.-J. Wan and O. Frieder, “New distributed algorithm for connected dominating set in wireless ad hoc networks” in Proc. IEEE HICSS35, January 2002
  • K. Islam, S. G. Akl and H. Meijer, “A Constant Factor Distributed Algorithm for computing Connected Dominating Sets in Wireless sensor Networks”
  • S. Guha and S. Khuller, “Approximation algorithms for connected dominating sets” Algorithmica, pages 374–387, 1998
  • S. Guha and S. Khuller, ‘ Approximation Algorithms for Connected Dominating Sets, “ Proc. European Symp. On Algorithm, 1996, pp. 179-193.
  • B. Das and V. Bhargavan, “ Routing in ad-hoc networks using minimum, connected dominating sets, ‘Proc. IEEE International Conference on Communications, June1997, pp. 376-380.