Design and analysis of an MST-based topology control algorithm
Design and analysis of an MST-based topology control algorithm
复制标题
DOI：
10.1109/infcom.2003.1209193
复制
发表时间：
2003-07
期刊：
影响因子：
--
通讯作者：
Ning Li;J. Hou;L. Sha
中科院分区：
文献类型：
--
作者：
Ning Li;J. Hou;L. Sha
本文提出了一种基于最小生成树（MST）的无线多跳网络拓扑控制算法，称为本地最小生成树（LMST）。在该算法中，每个节点独立构建自己的局部最小生成树，并且在最终拓扑中只保留距离为一跳的树上节点作为自己的邻居。我们分析证明了LMST的几个重要性质：(1)在LMST下导出的拓扑结构保持了网络的连通性；(2)所得拓扑中任意节点的节点度以6为界；(3)去除所有单向链路后，可以将拓扑转换为具有双向链路的拓扑（不影响网络连通性）。这些结果在模拟研究中得到了证实。
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.