A novel energy-efficient backbone for sensor networks

Hekang Chen, Shuigeng Zhou, Bin Xiao, Jihong Guan, Bo Huang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)


The construction of backbone is a fundamental problem in sensor networks. As being critical to routing, data fusion and query broadcasting, the backbone should contain as fewer nodes as possible. Meanwhile, it also should be power-efficient in order to prolong its lifetime. In this paper, we propose a novel design of backbone for sensor networks by minimizing its total transmission cost. We term this kind of backbone Minimum-Weight Backbone (simply MWB). The construction of MWB is proved to be NP-Complete. Two heuristic algorithms (one is centralized and the other is distributed) are developed for constructing such backbone. The centralized algorithm, executed at the base station, is to find an optimal backbone by using the information of all nodes and links in the network. The distributed algorithm run at each node, however, uses the information of its neighbors and two-hop neighbors to determine whether it should be included in the backbone. Simulated experiments are conducted to evaluate the novel backbone, and performance comparisons are also done with the existing schemes.
Original languageEnglish
Title of host publicationMobile Ad-Hoc and Sensor Networks - 2nd International Conference, MSN 2006, Proceedings
Number of pages12
Publication statusPublished - 1 Dec 2006
Event2nd International Conference on Mobile Ad-Hoc and Sensor Networks, MSN 2006 - Hong Kong, Hong Kong
Duration: 13 Dec 200615 Dec 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4325 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference2nd International Conference on Mobile Ad-Hoc and Sensor Networks, MSN 2006
Country/TerritoryHong Kong
CityHong Kong

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A novel energy-efficient backbone for sensor networks'. Together they form a unique fingerprint.

Cite this