Steiner Tree Movement Control Algorithm for Topology Recovery

您当前的位置：

首页 >

文章列表页 >

Steiner Tree Movement Control Algorithm for Topology Recovery

更新时间：2025-07-09

- Steiner Tree Movement Control Algorithm for Topology Recovery
- Vol. 45, Issue 2, Pages: 39-43(2011)
- 作者机构：
  
  西安电子科技大学综合业务网理论及关键技术国家重点实验室,西安,710071
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP393
- Online First：10 February 2011，
  
  Published：2011
- 稿件说明：
移动端阅览
Steiner Tree Movement Control Algorithm for Topology Recovery[J]. 2011, 45(2): 39-43.
DOI：

Steiner Tree Movement Control Algorithm for Topology Recovery[J]. 2011, 45(2): 39-43. DOI：

摘要

针对无线Ad Hoc网络中拓扑修复成功率低、节点移动开销大的问题

提出了一种Steiner树移动控制算法(SMC).采用三近似最少Steiner点算法建立一棵包含网络节点和Steiner点的Steiner树

然后将引入的Steiner点作为节点移动的目的点

选择并调度一些节点移动到这些Steiner点上

最后更新网络拓扑

迭代执行算法直到建立一个连通的网络拓扑.仿真结果表明

与基于分区最小生成树的移动控制算法相比

SMC算法不仅修复网络拓扑的成功率可达到100%

而且还显著降低了节点移动开销

其中节点移动总距离减小了37%～45%

节点移动总数减少了9%～29%.

Abstract

A Steiner tree movement control algorithm(SMC)is proposed to improve low success rate and large movement cost in wireless ad hoc network topology recovery. The SMC computes a Steiner tree by calling 3STP-MSP algorithm

where the vertices contain all the nodes in the network and the introduced Steiner points. Then the Steiner points are regarded as movement destinations

and some nodes are selected and scheduled to move to these Steiner points. SMC runs iteratively until the network is connected. Simulation results show that the SMC not only reconnects the network with a success rate 100%

but also decreases the movement cost significantly

compared with the MST-based PMST-UV algorithm

and that the total movement distance is reduced by 37% to 45% and the number of total movement nodes is reduced by 9% to 29%.

关键词

Keywords

references

SESAY S, YANG Zongkai, HE Jianhua. A survey on mobile ad hoc wireless network [J]. Information Technology Journal, 2004, 3(2): 168-175.

ABBASI A A, AKKAYA K, YOUNIS M. A distributed connectivity restoration algorithm in wireless sensor and actor networks [C]∥Proceedings of 32nd IEEE Conference on LCN. Piscataway, NJ, USA: IEEE, 2007: 496-503.

AKKAYA K, SENEL F. Detecting and connecting disjoint sub-networks in wireless sensor and actor networks [J]. Elsevier Ad Hoc Networks, 2009, 7(7): 1330-1346.

公维宾, 常义林, 沈中. 传感器网络中实现传输功率均衡的移动控制算法 [J]. 西安电子科技大学学报, 2008, 35(3): 816-822.

GONG Weibing, CHANG Yilin, SHEN Zhong. Movement control algorithms for realizing the balance of transmission power for sensor networks [J]. Journal of Xidian University, 2008, 35(3): 816-822.

公维宾. 无线Ad Hoc网络节点移动技术研究 [D]. 西安: 西安电子科技大学通信工程学院, 2009.

DIESTEL R. Graph theory [M]. 3rded. Heidelberg, Germany: Springer-Verlag, 2006.

GILBERT E N, POLLAK H O. Steiner minimal trees [J]. SIAM Journal on Applied Mathematics, 1968, 16(1): 1-29.

CHENG Xiuzhen, DU Dingzhu, WANG Lusheng, et al. Relay sensor placement in wireless sensor networks [J]. Wireless Networks, 2008, 14(3): 347-355.

CHEN Donghui, DU Dingzhu, HU Xiaodong, et al. Approximations for Steiner trees with minimum number of Steiner points [J]. Elsevier Theoretical Computer Science, 2001, 262(1/2): 83-99.

BETTSTETTER C. On the minimum node degree and connectivity of a wireless multihop network [C]∥Proceeding of 3rd ACM International Symposium on Mobile Ad Hoc Networking Computing. New York, NY, USA: ACM Press, 2002: 80-91.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

An Advanced Algorithm for Delay-Constrained Steiner Tree

Study on the Thermodynamic Properties in the Anomalous Region of Supercritical Water

Turbulent Kinetic Energy Dissipation Mechanism of Supercritical Carbon Dioxide Leakage Flow in a Scallop Bionic Seal Cavity

Integrated and Joint Design Optimization of Centrifugal Compressor Impeller and Casing Treatment at Multiple Working Points

Energy Efficiency Optimization of the Cryogenic Air Separation Process for Electronic-Grade Ultra Pure Nitrogen

Related Author

徐剑 1

倪宏 2

邓浩江 2

刘磊 2

Related Institution

University of Chinese Academy of Sciences

National Network New Media Engineering Research Center, Institute of Acoustics, Chinese Academy of Sciences

⁰