skip to main content
10.1145/1641776.1641791acmconferencesArticle/Chapter ViewAbstractPublication PagesmobicomConference Proceedingsconference-collections
research-article

Blackbone2, an efficient deterministic algorithm for creating 2-connected m-dominating set-based backbones in ad hoc networks

Published: 26 October 2009 Publication History

Abstract

This paper introduces Blackbone2, a novel fully decentralized algorithm that aims at creating a robust backbone in ad hoc networks. Backbone robustness is supported by a 2-Connected m-dominating Set, 2,m-CDS, and decentralization relies on the usage of two rules that only require two-hop knowledge in order to reduce the use of bandwidth. Blackbone2 deterministic approach guarantees a density-indpendent valid solution and is proved correct. The algorithm is also characterized by its efficient theoretical computation time, Ο(Δ2) with Δ the average number of neighbors, which outperforms known solutions. The domination parameter, m, can be increased without changing the theoretical computation time. Efficiency of the Blackbone2 algorithm compared to the equivalent literature solutions is illustrated through simulations of a large panel of networks with a wide density range.

References

[1]
K. M. Alzoubi, P.-J. Wan, and O. Frieder. New distributed algorithm for connected dominating set in wireless ad hoc networks. Proc. IEEE Hawaii Intl. Conf. System Sciences, 2002.
[2]
S. Basagni, M. Mastrogiovanni, A. Panconesi, and C. Petrioli. Localized protocols for ad hoc clustering and backbone formation: A performance comparison. IEEE Transactions on Parallel and Distributed Systems, 17(4):292--306, 4 2006.
[3]
F. Dai and J. Wu. An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans. Parallel and Distributed Systems, 15(10):908--920, 10 2004.
[4]
F. Dai and J. Wu. On constructing k-connected k-dominating set in wireless network. IEEE International Parallel and Distributed Processing Symposium, 2005.
[5]
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.
[6]
P. Gupta and P. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, IT-46(3):388--404, 2000.
[7]
D. Kim, Y. Wu, Y. Li, F. Zou, and D.-Z. Du. Constructing energy efficient connected dominating sets with bounded diameters in wireless networks. IEEE Transactions on Parallel and Distributed Systems, 2007.
[8]
Y. Li, S. Zhu, M. T. Thai, and D.-Z. Du. Localized construction of connected dominatinf set in wireless networks. IEEE INFOCOM, 2002.
[9]
J. Schleich, P. Bouvry, and L. T. H. An. Decentralized fault-tolerant connected dominating set algorithm for mobile ad hoc networks. In International Conference on Wireless Networks, 2009.
[10]
W. Shang, F. Yao, P. Wan, and X. Hu. Algorithms for minimum m-connected k-dominating set problem. COCOA 2007, LNCS 4616, pages 182--190, 2007.
[11]
M. T. Thai, N. Zhang, R. Tiwari, and X. Xu. On approximation algorithms of k-connected m-dominating set in disk graphs. Accepted by Theoretical Computer Science, 2007.
[12]
P.-J. Wan, K. M. Alzoubi, and O. Frieder. Distributed construction of connected dominating set in wireless ad hoc networks. NFS International Workshop on Theoretical Aspects of Wireless Ad hoc, Sensor and Peer-to-Peer Networks, 6 2004.
[13]
F. Wang, M. T. Thai, and D.-Z. Du. 2-connected virtual backbone in wireless network. Accepted by IEEE Transactions on Wireless Communication, 2007.
[14]
Y. Wang, W. Wang, and W. yang Li. Efficient distributed low-cost backbone formation for wireless networks. IEEE Transactions on Parallel and Distributed Systems, 17(7):681--693, 7 2006.
[15]
J. Wu. An enhanced approach to determine a small forward node set based on multi-point relay. Proc. 58th IEEE Semiann. Vehicular Technology Conf, 4:2774--2777, 10 2003.
[16]
J. Wu and H. Li. On calculating connected dominating sets for efficient routing in ad hoc wireless networks. Proc. Third ACM Int'l Workshop Discrete Algorithms and Methods for Mobile Computing and Comm., Dial M 1999:7--17, 8 1999.
[17]
Y. Wu and Y. Li. Construction algorithms for k-connected m-dominating sets in wireless sensor networks. Mobihoc;08, pages 83--90, 5 2008.
[18]
Y. Wu, F. Wang, M. T. Thai, and Y. Li. Constructing k-connected m-dominating sets in wireless sensor networks. Military Communication Conference, 10 2007.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
MobiWAC '09: Proceedings of the 7th ACM international symposium on Mobility management and wireless access
October 2009
168 pages
ISBN:9781605586175
DOI:10.1145/1641776
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 October 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. k-connected m-dominating set
  2. localized algorithm
  3. wireless sensor networks

Qualifiers

  • Research-article

Conference

MSWiM '09
Sponsor:

Acceptance Rates

Overall Acceptance Rate 83 of 272 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2015)Load-Balanced Virtual Backbones in Wireless Sensor NetworksHandbook of Sensor Networking10.1201/b18001-28(369-406)Online publication date: 14-Jan-2015
  • (2013)ReferencesWireless Ad Hoc and Sensor Networks10.1201/b15325-17(321-341)Online publication date: 22-Jul-2013
  • (2012)Information dissemination in VANETs based upon a tree topologyAd Hoc Networks10.1016/j.adhoc.2011.06.00510:1(111-127)Online publication date: Jan-2012
  • (2012)Greedy construction of load-balanced virtual backbones in wireless sensor networksWireless Communications and Mobile Computing10.1002/wcm.221814:7(673-688)Online publication date: 26-Mar-2012
  • (2010)On quantifying the quality of CDS-based virtual backbones in mobile ad hoc networksProceedings of the 8th ACM international workshop on Mobility management and wireless access10.1145/1868497.1868501(21-28)Online publication date: 17-Oct-2010

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media