一种修复网络拓扑的Steiner树移动控制算法

闫中江; 沈中; 常义林; 张颖; 代亮

您当前的位置：

首页 >

文章列表页 >

一种修复网络拓扑的Steiner树移动控制算法

更新时间：2025-07-09

- 一种修复网络拓扑的Steiner树移动控制算法
- Steiner Tree Movement Control Algorithm for Topology Recovery
- 西安交通大学学报 2011年45卷第2期页码：39-43
- 作者机构：
  
  西安电子科技大学综合业务网理论及关键技术国家重点实验室,西安,710071
- 作者简介：
- 基金信息：
  
  : 2010-05-26. 作者简介: 闫中江(1983-),男,博士生;常义林(联系人),男,教授,博士生导师. 基金项目:高等学校学科创新引智计划资助项目(B08038);国家自然科学基金资助项目(60972047)
- DOI：
  中图分类号： TP393
- 网络首发：2011-02-10，
  
  纸质出版：2011
- 稿件说明：
移动端阅览
闫中江, 沈中, 常义林, 等. 一种修复网络拓扑的Steiner树移动控制算法[J]. 西安交通大学学报, 2011,45(2):39-43.

Steiner Tree Movement Control Algorithm for Topology Recovery[J]. 2011, 45(2): 39-43.
闫中江, 沈中, 常义林, 等. 一种修复网络拓扑的Steiner树移动控制算法[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.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

改进的时延约束Steiner树算法

扇贝仿生密封腔室内超临界二氧化碳泄漏流湍动能耗散机理研究

EBSILON软件在热电联产系统优化中的应用综述

不同板叠材料热声热机能量转换过程数值模拟研究

多工况下离心压气机叶轮-机匣一体联合设计优化