Article

Virtual backbone based on MCDS for topology control in wireless ad hoc networks

Authors:

PE-WASUN '05: Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks

Pages 230 - 233

https://doi.org/10.1145/1089803.1089991

Published: 10 October 2005 Publication History

Get Access

Abstract

This paper proposes to utilize virtual backbone to handle control messages in ad hoc networks. The virtual backbone is built by using the Minimum Connected Dominating Set (MCDS) on a graph. The first part of this paper presents a new algorithm to construct the MCDS. The construction of the MCDS is formulated using the linear programming approach. We compared the performance of this procedure with those other previous approaches, and we find that our approach is less complex and gives the nearest solution to the optimal one. The second part of this paper presents different techniques of diffusion in ad hoc networks such as flooding, clustering, MP relay, and backbone based on MCDS, etc. The flooding technique is simple and efficient, but it is expensive in term of bandwidth, and causes excessive flows of message etc. Simulation results show that the approach of virtual backbone based MCDS outperforms flooding and MP relay.

References

[1]

NIST, "Mobile Ad Hoc Networks (MANETs)" http://www.antd.nist.gov/wahn_mahn.shtml.

Google Scholar

[2]

S. Guha and S. Khuller, "Approximation Algorithms for Connected Dominating Sets," Algorithmica, vol. 20, pp. 374--387, 1998.

Digital Library

Google Scholar

[3]

A. Qayyum, L. Viennot, and A. Laouiti, "Multipoint relaying for flooding broadcast messages in mobile wireless networks," in Proc. of the 35th Annual Hawaii International, pp. 3866--3875, 2002.

Digital Library

Google Scholar

[4]

J. Wu and H. Li, "On Calculating Connected Dominating Set for Efficient Routing in Ad hoc Wireless Networks," in Proc. of the 3rd Inter. WDAM for MOBILE Comp. and Comm. Seattle, WA, USA, 1999, pp. 7--14.

Digital Library

Google Scholar

[5]

K. Mnif, B. Rong and M. Kadoch "A Distributed Approach for Computing the Minimum Connected Dominating Set", CCEC'05, Saskatoon, SK, Canada. pp. 2011--2014. 1-4 May 2005.

Google Scholar

[6]

N. Megiddo, "On the complexity of linear programming," in Advances in economic theory: Fifth world congress. T. Bewley. ed. Cambridge University Press, 1987, pp. 225--268.

Google Scholar

[7]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. New Jersey: Prentice-Hall, Inc., 1993.

Digital Library

Google Scholar

[8]

J. P. Jarvis and D. E. White, "Computational experience with minimum spanning tree algorithms," Operations Research Letters, vol. 2, pp. 36--41, 1983.

Digital Library

Google Scholar

[9]

Basagni, S. "Distributed Clustering for Ad Hoc Networks." Proc. of the 1999 Inter. Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99) pp. 310--315, 1999.

Digital Library

Google Scholar

[10]

Vamsi S. Paruchuri, Arjan Durresi, Durga S. Dash, and Raj Jain. Optimal flooding protocol for routing in ad-hoc networks. Technical report, Ohio State University, CS Department, 2002.

Google Scholar

[11]

Stojemenovic, I., M. Seddigh and J. Zunic (2001). "Internal nodes based broadcasting algorithms in wireless networks." Proceedings of the 34th Annual Hawaii International conference on system sciences HICSS 2001.

Digital Library

Google Scholar

Cited By

View all

Hedar AAbdulaziz SMabrouk EEl-Sayed G(2020)Wireless Sensor Networks Fault-Tolerance Based on Graph Domination with Parallel Scatter SearchSensors10.3390/s2012350920:12(3509)Online publication date: 21-Jun-2020
https://doi.org/10.3390/s20123509
Duraisamy PEsakkimuthu S(2020)Linear programming approach for various domination parametersDiscrete Mathematics, Algorithms and Applications10.1142/S1793830920500962(2050096)Online publication date: 15-Sep-2020
https://doi.org/10.1142/S1793830920500962
Yahiatene YRachedi ARiahla MMenacer DNait‐Abdesselam F(2019)A blockchain‐based framework to secure vehicular social networksTransactions on Emerging Telecommunications Technologies10.1002/ett.365030:8Online publication date: 14-Aug-2019
https://dl.acm.org/doi/10.1002/ett.3650
Show More Cited By

Index Terms

Virtual backbone based on MCDS for topology control in wireless ad hoc networks
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

Zone-based virtual backbone formation in wireless ad hoc networks

Efficient protocol for clustering and backbone formation is one of the most important issues in wireless ad hoc networks. Connected dominating set (CDS) formation is a promising approach for constructing virtual backbone. However, finding the minimum ...
Mobility-Based Backbone Formation in Wireless Mobile Ad-hoc Networks

In this paper, the well-known network backbone formation problem is modeled as the stochastic min-degree constrained minimum spanning tree (md-MST) problem, where the link duration is associated with the edge weight. Then, a decentralized learning ...
A Distributed Virtual Backbone Development Scheme for Ad-Hoc Wireless Networks

The virtual backbone is an approach for solving routing problems in ad-hoc wireless networks. The virtual backbone approach features low latency, moderate routing overhead and is a hybrid scheme that uses the table-driven and on-demand routing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PE-WASUN '05: Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks

October 2005

292 pages

ISBN:1595931821

DOI:10.1145/1089803

Program Chairs:
Mohamed Ould-Khaoua
University of Glasgow, UK
,
Mineo Takai
University of California, Los Angeles, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 October 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MSWiM05

Sponsor:

MSWiM05: 8th International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems 2005

October 10 - 13, 2005

Quebec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 70 of 240 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
326
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hedar AAbdulaziz SMabrouk EEl-Sayed G(2020)Wireless Sensor Networks Fault-Tolerance Based on Graph Domination with Parallel Scatter SearchSensors10.3390/s2012350920:12(3509)Online publication date: 21-Jun-2020
https://doi.org/10.3390/s20123509
Duraisamy PEsakkimuthu S(2020)Linear programming approach for various domination parametersDiscrete Mathematics, Algorithms and Applications10.1142/S1793830920500962(2050096)Online publication date: 15-Sep-2020
https://doi.org/10.1142/S1793830920500962
Yahiatene YRachedi ARiahla MMenacer DNait‐Abdesselam F(2019)A blockchain‐based framework to secure vehicular social networksTransactions on Emerging Telecommunications Technologies10.1002/ett.365030:8Online publication date: 14-Aug-2019
https://dl.acm.org/doi/10.1002/ett.3650
Hedar AEl-Sayed GAbuarqoub AAdebisi BHammoudeh MMurad SArioua M(2018)Parallel genetic algorithm with elite and diverse cores for solving the minimum connected dominating set problem in wireless networks topology controlProceedings of the 2nd International Conference on Future Networks and Distributed Systems10.1145/3231053.3231080(1-9)Online publication date: 26-Jun-2018
https://dl.acm.org/doi/10.1145/3231053.3231080
Yahiatene YRachedi A(2018)Towards a Blockchain and Software-Defined Vehicular Networks Approaches to Secure Vehicular Social Network2018 IEEE Conference on Standards for Communications and Networking (CSCN)10.1109/CSCN.2018.8581756(1-7)Online publication date: Oct-2018
https://doi.org/10.1109/CSCN.2018.8581756
Zhang JTang YJun ZWang W(2015)A layer-based algorithm for the construction of connected dominating set in WSNsInternational Journal of Autonomous and Adaptive Communications Systems10.1504/IJAACS.2015.0695688:2/3(320-331)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1504/IJAACS.2015.069568
Fan NWatson J(2012)Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer ProgrammingCombinatorial Optimization and Applications10.1007/978-3-642-31770-5_33(371-383)Online publication date: 2012
https://doi.org/10.1007/978-3-642-31770-5_33
Yin BShi HShang Y(2011)An efficient algorithm for constructing a connected dominating set in mobile ad hoc networksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2010.05.00871:1(27-39)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1016/j.jpdc.2010.05.008
Wightman PFabregasy ALabradorz M(2010)An optimal solution to the MCDS problem for topology construction in wireless sensor networks2010 IEEE Latin-American Conference on Communications10.1109/LATINCOM.2010.5641018(1-6)Online publication date: Sep-2010
https://doi.org/10.1109/LATINCOM.2010.5641018
Vahdatpour ADabiri FMoazeni MSarrafzadeh M(2008)Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor NetworksDistributed Computing10.1007/978-3-540-87779-0_33(481-495)Online publication date: 2008
https://doi.org/10.1007/978-3-540-87779-0_33
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Zone-based virtual backbone formation in wireless ad hoc networks

Mobility-Based Backbone Formation in Wireless Mobile Ad-hoc Networks

A Distributed Virtual Backbone Development Scheme for Ad-Hoc Wireless Networks