Maintaining approximate minimum steiner tree and k-center for mobile agents in a sensor network

Dengpan Zhou, Jie Gao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations


We study the problem of maintaining group communication between m mobile agents, tracked and helped by n static networked sensors. We develop algorithms to maintain a O(lg n)-approximation to the minimum Steiner tree of the mobile agents such that the maintenance message cost is on average O(lg n) per each hop an agent moves. The key idea is to extract a 'hierarchical well-separated tree (HST)' on the sensor nodes such that the tree distance approximates the sensor network hop distance by a factor of O(lg n). We then prove that maintaining the subtree of the mobile agents on the HST uses logarithmic messages per hop movement. With the HST we can also maintain O(lg n) approximate k-center for the mobile agents with the same message cost. Both the minimum Steiner tree and the k-center problems are NP-hard and our algorithms are the first efficient algorithms for maintaining approximate solutions in a distributed setting.

Original languageEnglish (US)
Title of host publication2010 Proceedings IEEE INFOCOM
StatePublished - 2010
Externally publishedYes
EventIEEE INFOCOM 2010 - San Diego, CA, United States
Duration: Mar 14 2010Mar 19 2010

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Country/TerritoryUnited States
CitySan Diego, CA

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Maintaining approximate minimum steiner tree and k-center for mobile agents in a sensor network'. Together they form a unique fingerprint.

Cite this