一种均衡网络传输功率的移动控制算法

doi:10.3969/j.issn.1001-2400.2011.03.009

J4 ›› 2011, Vol. 38 ›› Issue (3): 48-54.doi: 10.3969/j.issn.1001-2400.2011.03.009

一种均衡网络传输功率的移动控制算法

闫中江；沈中；常义林；杨家玮

(西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071)

收稿日期:2010-05-16 出版日期:2011-06-20 发布日期:2011-07-14
通讯作者: 闫中江
作者简介:闫中江(1983-)，男，西安电子科技大学博士研究生，E-mail: zhjyan@xidian.edu.cn．
基金资助:
高等学校学科创新引智计划基金资助项目(B08038);国家自然科学基金资助项目(60972047)

Movement control algorithm for balancing transmission power

YAN Zhongjiang；SHEN Zhong；CHANG Yilin；YANG Jiawei

(State Key Lab. of Integrated Service Networks, Xidian Univ., Xi'an 710071， China)

Received:2010-05-16 Online:2011-06-20 Published:2011-07-14
Contact: YAN Zhongjiang

摘要/Abstract

摘要：

针对均衡网络传输功率时节点移动开销大，算法迭代次数多的问题，提出了一种基于最小连通支配集和Steiner树的移动控制算法．首先计算网络拓扑的骨干节点集，然后根据骨干节点集和临界传输半径建立Steiner树，树中的Steiner点作为节点移动的目的点，最后匹配并移动非骨干节点到Steiner点，实现节点传输功率的均衡．仿真结果表明，与基于最小生成树的PMST-UV算法相比，在相同的网络场景下，本算法节点移动开销小，算法迭代次数少，节点总移动距离降低13%~34%，算法迭代次数减少17%~68%．

关键词: 无线Ad Hoc网络, 移动控制, 传输功率均衡, 最小连通支配集

Abstract:

To decrease the movement cost and the algorithm's iteration number in balancing the transmission power of nodes, a novel movement control algorithm is proposed, which is based on the minimum connected dominating set and Steiner tree. Firstly, a node set, which acts as the backbone of the network, is computed. Then a Steiner tree is constructed with the input of the backbone node set and the critical transmission radius, where the Steiner points are set as the moving candidates' destination points. Finally, the nodes which are not in the backbone node set are matched with and moved to the Steiner points to balance the transmission power. Simulation results show that, compared to the MST-based PMST-UV, the proposed algorithm reduces the movement cost and the iteration number, with the total movement distance decreased 13%~34%, and the iteration number reduced 17%~68%.

Key words: wireless ad hoc network, movement control, balanced transmission power, minimum connected dominating set

中图分类号:

TP393

闫中江；沈中；常义林；杨家玮. 一种均衡网络传输功率的移动控制算法[J]. J4, 2011, 38(3): 48-54.

YAN Zhongjiang；SHEN Zhong；CHANG Yilin；YANG Jiawei. Movement control algorithm for balancing transmission power[J]. J4, 2011, 38(3): 48-54.

参考文献

［1］ Sesay S, Yang Z, He J. A Survey on Mobile Ad Hoc Wireless Network ［J］. Information Technology Journal, 2004, 3(2): 168-175.
［2］ Li N, Hou J C, Sha L. Design and Analysis of an MST-based Topology Control Algorithm ［J］. IEEE Trans on Wireless Communications, 2005, 4(3): 1195-1206.
［3］沈中, 常义林, 崔灿. 无线Ad Hoc网络中保留最小能量路径的拓扑控制算法［J］. 西安电子科技大学学报, 2006, 33(3): 341-346.
Shen Zhong, Chang Yilin, Cui Can. Study of the Minimum-energy Path-preserving Topology Control Algorithm for Wireless Ad Hoc Networks ［J］. Journal of Xidian University, 2006, 33(3): 341-346.
［4］公维宾, 常义林, 沈中. 传感器网络中实现传输功率均衡的移动控制算法［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.
［5］ Younis M, Akkaya K. Strategies and Techniques for Node Placement in Wireless Sensor Networks: a Survey ［J］. Elsevier Ad Hoc Network Journal, 2008, 6(4): 621-655.
［6］ 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.
［7］ Diestel R. Graph Theory ［M］. 3rd. Heidelberg: Springer-Verlag, 2006.
［8］路纲, 周明天, 牛新征, 等. 无线网络邻近图综述［J］. 软件学报, 2008, 19(4): 888-911.
Lu Gang, Zhou Mingtian, Niu Xinzheng, et al. A Survey of Proximity Graphs in Wireless Networks ［J］. Journal of Software, 2008, 19(4): 888-911.
［9］ Cheng X, Du D Z, Wang L, et al. Relay Sensor Placement in Wireless Sensor Networks ［J］. Wireless Networks, 2008, 14(3): 347-355.
［10］ Chen D H, Du D Z, Hu X D, et al. Approximations for Steiner Trees with Minimum Number of Steiner Points ［J］. Elsevier Theoretical Computer Science, 2001, 262(2001): 83-99.
［11］ Guha S, Khuller S. Approximation Algorithms for Connected Dominating Sets ［J］. Algorithmica, 1998, 20(4): 374-387.
［12］ Gilbert E N, Pollak H O. Steiner Minimal Trees ［J］. SIAM Journal on Applied Mathematics, 1968, 16(1): 1-29.
［13］ Sedgewick R. Graph Algorithms ［M］. 北京: 中国电力出版社, 2003.
［14］ Penrose M D. The Longest Edge of the Random Minimal Spanning Tree ［J］. The Annals of Applied Probability, 1997, 7(2): 340-361.

[1]	公维宾;沈中;常义林. 传感器网络中实现传输功率均衡的移动控制算法 [J]. J4, 2008, 35(5): 816-822.
[2]	沈中;常义林;崔灿;张新. 无线Ad Hoc网络中保留最小能量路径的拓扑控制算法[J]. J4, 2006, 33(3): 341-346.
[3]	贺鹏;李建东;陈彦辉. 一种新型的基于地理位置信息的Ad Hoc路由算法[J]. J4, 2006, 33(2): 218-222.
[4]	张光辉;李建东;周雷;刘静. 运动对无线Ad Hoc网络中保持连通的临界传输半径的影响[J]. J4, 2005, 32(6): 881-884.

一种均衡网络传输功率的移动控制算法

Movement control algorithm for balancing transmission power

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

Metrics

本文评价

推荐阅读 10