An efficient algorithm for constructing maximum lifetime tree for data gathering without aggregation in wireless sensor networks

Junbin Liang, Jianxin Wang, Jiannong Cao, Jianer Chen, Mingming Lu

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

56 Citations (Scopus)


Data gathering is a broad research area in wireless sensor networks. The basic operation in sensor networks is the systematic gathering and transmission of sensed data to a sink for further processing. The lifetime of the network is defined as the time until the first node depletes its energy. A key challenge in data gathering without aggregation is to conserve the energy consumption among nodes so as to maximize the network lifetime. We formalize the problem of tackling the challenge as to construct a min-max-weight spanning tree, in which the bottleneck nodes have the least number of descendants according to their energy. However, the problem is NP-complete. A Ω(log n/ log log n)-approximation algorithm MITT is proposed to solve the problem without location information. Simulation results show that MITT can achieve longer network lifetime than existing algorithms.
Original languageEnglish
Title of host publication2010 Proceedings IEEE INFOCOM
Publication statusPublished - 15 Jun 2010
EventIEEE INFOCOM 2010 - San Diego, CA, United States
Duration: 14 Mar 201019 Mar 2010


ConferenceIEEE INFOCOM 2010
Country/TerritoryUnited States
CitySan Diego, CA


  • Data gathering
  • Maximum lifetime
  • Spanning tree
  • Wireless sensor networks

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Cite this