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 language | English (US) |
|---|---|
| Pages (from-to) | 1702-1712 |
| Number of pages | 11 |
| Journal | Proceedings - IEEE INFOCOM |
| Volume | 3 |
| State | Published - 2003 |
| Event | 22nd Annual Joint Conference on the IEEE Computer and Communications Societies - San Francisco, CA, United States Duration: Mar 30 2003 → Apr 3 2003 |
ASJC Scopus subject areas
- Computer Science(all)
- Electrical and Electronic Engineering