Design and analysis of an MST-based topology control algorithm

Ning Li, Jennifer C. Hou, Lui Sha

Research output: Contribution to journalArticlepeer-review


In this paper, we present a minimum spanning tree (MST)-based algorithm, called local minimum spanning tree (LMST), for topology control in wireless multihop networks. In this algorithm, each node builds its LMST 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 bidirectional links (without impairing the network connectivity) after removal of all unidirectional links. Simulation results show that LMST can increase the network capacity as well as reduce the energy consumption.

Original languageEnglish (US)
Pages (from-to)1195-1206
Number of pages12
JournalIEEE Transactions on Wireless Communications
Issue number3
StatePublished - May 2005


  • Graph theory
  • Spatial reuse
  • Topology control

ASJC Scopus subject areas

  • Computer Science Applications
  • Electrical and Electronic Engineering
  • Applied Mathematics


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

Cite this