Design and analysis of an MST-based topology control algorithm

Ning Li, Jennifer C. Hou, Lui Raymond Sha

Research output: Contribution to journalConference article

Abstract

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
Volume3
StatePublished - Sep 1 2003
Event22nd Annual Joint Conference on the IEEE Computer and Communications Societies - San Francisco, CA, United States
Duration: Mar 30 2003Apr 3 2003

Fingerprint

Trees (mathematics)
Topology

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Cite this

Design and analysis of an MST-based topology control algorithm. / Li, Ning; Hou, Jennifer C.; Sha, Lui Raymond.

In: Proceedings - IEEE INFOCOM, Vol. 3, 01.09.2003, p. 1702-1712.

Research output: Contribution to journalConference article

@article{d937add2141d49ccbe1b588e13d1bd69,
title = "Design and analysis of an MST-based topology control algorithm",
abstract = "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.",
author = "Ning Li and Hou, {Jennifer C.} and Sha, {Lui Raymond}",
year = "2003",
month = "9",
day = "1",
language = "English (US)",
volume = "3",
pages = "1702--1712",
journal = "Proceedings - IEEE INFOCOM",
issn = "0743-166X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Design and analysis of an MST-based topology control algorithm

AU - Li, Ning

AU - Hou, Jennifer C.

AU - Sha, Lui Raymond

PY - 2003/9/1

Y1 - 2003/9/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0041973675&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0041973675&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0041973675

VL - 3

SP - 1702

EP - 1712

JO - Proceedings - IEEE INFOCOM

JF - Proceedings - IEEE INFOCOM

SN - 0743-166X

ER -