Title :
Design and analysis of an MST-based topology control algorithm
Author :
Li, Ning ; Hou, Jennifer C. ; Sha, Lui
Author_Institution :
Dept. of Comput. Sci., Illinois Univ., Urbana, IL, USA
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 bidirectional links (without impairing the network connectivity) after removal of all uni-directional links. These results are corroborated in the simulation study.
Keywords :
network topology; radio networks; telecommunication control; telecommunication network management; LMST; MST based topology control algorithm; bi-directional link; local minimum spanning tree; minimum spanning tree; network connectivity; node degree; on-tree node; topology management; wireless multihop network; Algorithm design and analysis; Bidirectional control; Communication system control; Computer science; Energy management; Interference; Network topology; Power control; Spread spectrum communication; Wireless networks;
Conference_Titel :
INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies
Print_ISBN :
0-7803-7752-4
DOI :
10.1109/INFCOM.2003.1209193
