Design and analysis of an MST-based topology control algorithm

Ning Li, Jennifer C. Hou, Lui Sha

Research output: Contribution to journalConference articlepeer-review


In this paper, we present a Minimum Spanning Tree (MST) based topology control algorithm, called Local Minimum Spanning Tree (LMST), for wireless multi-hop networks. In this algorithm, each node builds its local minimum spanning tree independently and only keeps on-tree nodes that are one-hop away as its neighbors in the final topology. We analytically prove several important properties of LMST: (1) the topology derived under LMST preserves the network connectivity; (2) the node degree of any node in the resulting topology is bounded by 6; and (3) the topology can be transformed into one with bi-directional links (without impairing the network connectivity) after removal of all uni-directional links. These results are corroborated in the simulation study.

Original languageEnglish (US)
Pages (from-to)1702-1712
Number of pages11
JournalProceedings - IEEE INFOCOM
StatePublished - 2003
Event22nd Annual Joint Conference on the IEEE Computer and Communications Societies - San Francisco, CA, United States
Duration: Mar 30 2003Apr 3 2003

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Design and analysis of an MST-based topology control algorithm'. Together they form a unique fingerprint.

Cite this