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

Steiner Tree Movement Control Algorithm for Topology Recovery

作　　者：闫中江[1] 沈中[1] 常义林[1] 张颖[1] 代亮[1] 

机构地区：[1]西安电子科技大学综合业务网理论及关键技术国家重点实验室,西安710071

出　　处：《西安交通大学学报》2011年第2期39-43,共5页Journal of Xi'an Jiaotong University

基　　金：高等学校学科创新引智计划资助项目(B08038);国家自然科学基金资助项目(60972047)

摘　　要：针对无线AdHOC网络中拓扑修复成功率低、节点移动开销大的问题，提出了一种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 it- eratively 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%.

关 键 词：无线AD HOC网络 拓扑修复 移动控制 STEINER树 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]