Design and analysis of an MST-based topology control algorithm

Top Cited Papers

9 May 2005

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Wireless Communications

Vol. 4 (3) , 1195-1206
https://doi.org/10.1109/twc.2005.846971

Abstract

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.

Keywords

This publication has 16 references indexed in Scilit:

Range-free localization schemes for large scale sensor networks
Published by Association for Computing Machinery (ACM) ,2003
Mobility-adaptive protocols for managing large ad hoc networks
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
An optimal minimum spanning tree algorithm
Journal of the ACM, 2002
On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2001
The capacity of wireless networks
IEEE Transactions on Information Theory, 2000
Minimum energy mobile wireless networks
IEEE Journal on Selected Areas in Communications, 1999
An optimal topology-transparent scheduling method in multihop packet radio networks
IEEE/ACM Transactions on Networking, 1998
Making transmission schedules immune to topology changes in multi-hop packet radio networks
IEEE/ACM Transactions on Networking, 1994
Transitions in geometric minimum spanning trees
Discrete & Computational Geometry, 1992
Shortest Connection Networks And Some Generalizations
Bell System Technical Journal, 1957