基于改进的微粒群算法的WSN节点部署策略

广西师范大学学报（自然科学版） ›› 2011, Vol. 29 ›› Issue (4): 56-62.

基于改进的微粒群算法的WSN节点部署策略

郑磊¹, 朱正礼^1,2, 侯迎坤^2,3

1.南京林业大学信息科学技术学院,江苏南京210037;
2.南京理工大学计算机科学与技术学院,江苏南京210094;
3.泰山学院信息科学技术学院,山东泰安271021

收稿日期:2011-09-25 发布日期:2018-11-16
通讯作者: 朱正礼(1966—),男,江苏南京人,南京林业大学副教授。E-mail:haitian2001@163.com
基金资助:
国家自然科学基金资助项目(61072148);南京林业大学科研创新基金资助项目(163070037)

Deployment Strategy of Wireless Sensor Network Nodes Based on Improved Particle Swarm Optimization

ZHENG Lei¹, ZHU Zheng-li^1,2, HOU Ying-kun^2,3

1.College of Information Science and Technology,Nanjing Forestry University,Nanjing Jiangsu 210037,China;
2.College of Computer Science and Technology,Nanjing University of Scienceand Technology,Nanjing Jiangsu 210094,China;
3.Department of Information Science and Technology,Taishan University,Tai'an Shandong 271021,China

Received:2011-09-25 Published:2018-11-16

摘要/Abstract

摘要： 在无线传感网络部署中,必须保证无线传感器节点能够有效地覆盖被监测区域。为了减少节点部署时产生覆盖盲区,提高网络的覆盖率,本文提出了一种基于改进微粒群算法的无线传感器网络节点部署优化策略,以网络的覆盖率为适应值函数,将传感器节点的部署问题转化为目标优化问题,通过采用k-means聚类算法划分子种群,并且对子种群进行动态重组,减弱微粒对局部最优点的追逐,实现对基本PSO算法的改进,有效地解决了标准PSO算法中的粒子“早熟”问题,同时也加快了算法收敛速度。实验结果表明,该部署策略最大可能地减少了网络中的覆盖盲区,有效提高了网络覆盖率。与基本微粒群算法、传统遗传算法和蜂群算法的优化效果相比较,其覆盖率分别提高了4.11%、9.75%和5.25%。

关键词: 无线传感器网络, 微粒群算法, k-means聚类, 子种群

Abstract: In wireless sensor networks,thewireless sensornodes have to cover the area to be monitored effectively.In order to reduce the coverage holes and improve the coverage rate in wireless sensor networks,this paperproposed a new deployment strategy of wireless sensor network nodes based on improved particle swarm optimization.Taken network coverage as the fitness function,thedeployment of sensor nodes would be formalized as an objective optimization problem.By employing the k-means clustering algorithm,the population was divided into several sub-populations.In addition,the population was re-dividedinto new sub-populations dynamically,which could weaken particles on the pursuit of local optima,realize the improvement of basic PSO algorithm,effectively solve the “premature” problem of basic PSO algorithm,and accelerate the convergence ofthe algorithm.Experimental results show that this deployment strategy can reduce the coverage holes in wireless sensor networks as much as possible and effectively improve the network coverage rate.Compared with the results of elementary particle swarm optimization,the conventional genetic algorithm and swarm optimization algorithm,its coverage rate was increased by 4.11%,9.75% and 5.25%.

Key words: wireless sensor networks, PSO, k-means clustering, sub-population

中图分类号:

TP393

郑磊, 朱正礼, 侯迎坤. 基于改进的微粒群算法的WSN节点部署策略[J]. 广西师范大学学报（自然科学版）, 2011, 29(4): 56-62.

ZHENG Lei, ZHU Zheng-li, HOU Ying-kun. Deployment Strategy of Wireless Sensor Network Nodes Based on Improved Particle Swarm Optimization[J]. Journal of Guangxi Normal University(Natural Science Edition), 2011, 29(4): 56-62.

参考文献

[1] AKYILIDIG I F,SU Wei-lian,SANKARASUBRAMANIAM Y,et al.A survey onsensor networks[J].IEEE Communications Magazine,2002,8:721-734.
[2] 任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,2003,14(7):1282-1291.
[3] 王殊.无线传感器网络的理论及应用[M].北京:北京航空航天大学出版社,2005:225-229.
[4] 任彦,张思东,张宏科.无线传感器网络中覆盖控制理论与算法[J].软件学报,2006,17(3):422-433.
[5] 周利民,杨科华,周攀.基于鱼群算法的无线传感网络覆盖优化策略[J].计算机应用研究,2010,27(6):2276-2280.
[6] ZOU Yi,CHAKRABARTY K.Sensor deployment and target localization based on virtual forces[C]//Proceedings of the 22nd Annual Joint Conference of theIEEE Computer and Communications Societies.San Francisco,USA:IEEE,2003:1293-1303.
[7] 汪学清,杨永田.一种基于虚拟菱形网格的传感器节点布置算法[J].计算机应用,2006,26(7):1554-1556.
[8] BURNE R A,BUCZAK A L,JIN Yao-chu.A self-organizing,cooperative sensor network for remote surveillance:current result[C]//Proceedings of SPIE Volume 3713.Bellingham,WA:SPIE,1999:238-248.
[9] 王雪,王晟,马俊杰.无线传感器网络移动节点位置并行微粒群优化策略[J].计算机学报,2007,30(4):563-568.
[10] 张文爱,刘丽芳,李孝荣.基于粒子进化的多粒子群优化算法[J].计算机工程与应用,2008,44(7):51-53.
[11] 林祝亮,冯远静.基于多粒子群算法的WSNs覆盖优化策略研究[J].计算机应用研究,2009,26(12):4701-4703.
[12] ZHANG Hong-hai,HOU J C.Maintaining sensing coverage and connectivity inlarge sensor networks[J].Wireless Ad Hoc and Sensor Networks,2005,1(1):89-124.
[13] 刘玉英,史旺旺.一种基于遗传算法的无线传感器网络节点优化方法[J].传感器学报,2009,22(6):869-872.
[14] 袁浩.基于改进蜂群算法无线传感器感知节点部署优化[J].计算机应用研究,2010,27(7):2704-2705.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed