Bounded-distance multi-coverage backbones in wireless sensor networks

P. S. Sausen, M. A. Spohn, A. M.N. Lima, A. Perkusich

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations


Topology control can improve the performance of Wireless Sensor Network (WSN) by allowing only a subset of nodes to be active at any time with guaranteed network coverage. We present the first centralized and distributed solutions for computing Bounded-Distance Multi-Coverage Backbones in WSNs. The solutions are based on the (k, r)-CDS problem from graph theory for computing backbones in which any regular node is covered by at least k backbone members within distance r, offering a variable degree of redundancy and reliability. Applications that require reliable data gathering with bounded-delays are the intended targets for such structures. Given that the centralized solution is unsuitable for WSNs, because of the incurred control overhead, it is used as a lower bound for evaluating the performance of the distributed solution. The distributed solution is source-based in the sense that usually the base-station (or sink) is the focus of attention in a WSN. The two approaches are evaluated through extensive simulations, and it is shown that even though the distributed solution builds larger backbones, it does not incur on much control overhead.

Original languageEnglish
Title of host publicationProceedings of the 2007 ACM Symposium on Applied Computing
PublisherAssociation for Computing Machinery
Number of pages6
ISBN (Print)1595934804, 9781595934802
StatePublished - 2007
Externally publishedYes
Event2007 ACM Symposium on Applied Computing - Seoul, Korea, Republic of
Duration: 11 Mar 200715 Mar 2007

Publication series

NameProceedings of the ACM Symposium on Applied Computing


Conference2007 ACM Symposium on Applied Computing
Country/TerritoryKorea, Republic of


  • Backbone
  • Connected dominating sets
  • Domination in graphs
  • Wireless sensor networks


Dive into the research topics of 'Bounded-distance multi-coverage backbones in wireless sensor networks'. Together they form a unique fingerprint.

Cite this