Strong minimum energy topology in wireless sensor networks: NP-Completeness and heuristics

Xiuzhen Cheng, Bhagirath Narahari, Rahul Simha, Maggie Xiaoyan Cheng, Dan Liu

Research output: Contribution to journalArticlepeer-review

166 Scopus citations


Wireless sensor networks have recently attracted lots of research effort due to its wide range of applications. These networks must operate for months or years. However, the sensors are powered by battery, which may not be possible to be recharged after they are deployed. Thus, energy-aware network management is extremely important. In this paper, we study the following problem: Given a set of sensors in the plane, assign transmit power to each sensor such that the induced topology containing only bidirectional links is strongly connected. This problem is significant in both theory and application. We prove its NP-Completeness and propose two heuristics: power assignment based on minimum spanning tree (denoted by MST) and incremental power. We also show that MST heuristic has a performance ratio of 2. Simulation study indicates that the performance of these two heuristics does not differ very much, but, in average, the incremental power heuristic is always better than MST.

Original languageEnglish (US)
Pages (from-to)248-256
Number of pages9
JournalIEEE Transactions on Mobile Computing
Issue number3
StatePublished - Jul 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


  • Incremental power heuristic
  • Minimum energy topology
  • NP-Completeness
  • Power control
  • Wireless sensor networks


Dive into the research topics of 'Strong minimum energy topology in wireless sensor networks: NP-Completeness and heuristics'. Together they form a unique fingerprint.

Cite this