基于改进粒子群算法和特征点集的无线传感器网络覆盖问题研究

doi:10.3969/j.issn.0372-2112.2016.04.030

电子学报 ›› 2016, Vol. 44 ›› Issue (4): 967-973.DOI: 10.3969/j.issn.0372-2112.2016.04.030

基于改进粒子群算法和特征点集的无线传感器网络覆盖问题研究

丁旭, 吴晓蓓, 黄成

南京理工大学自动化学院, 江苏南京 210094

收稿日期:2014-10-13 修回日期:2015-04-28 出版日期:2016-04-25
- 通讯作者:
- 吴晓蓓
- 作者简介:
- 丁旭 男,1991年2月生于江苏盐城.博士研究生,研究方向为无线传感器网络覆盖优化、动态博弈网络编码及数据处理. E-mail:xdnjust@163.com;黄成 男,1975年7月生于江苏南通.博士研究生,讲师.研究方向为无线传感器网络、自动化检测技术. E-mail:hearthc@163.com
- 基金资助:
- 教育部博士点专项基金 (No.20113219110028); 江苏省自然科学基金 (No.BK2012803)

Area Coverage Problem Based on Improved PSO Algorithm and Feature Point Set in Wireless Sensor Networks

DING Xu, WU Xiao-bei, HUANG Cheng

Institute of Automation, Nanjing University of Science and Technology, Nanjing, Jiangsu 210094, China

Received:2014-10-13 Revised:2015-04-28 Online:2016-04-25 Published:2016-04-25

摘要/Abstract

摘要：

本文针对基于网格点的区域覆盖算法未考虑网络的固有特征,导致算法存在近似及复杂度偏高等问题,通过研究区域覆盖的特征,结合概率感知模型,对区域内两点的覆盖率关系进行分析,定义了特征点集的概念;对特征点集进行建模,将区域覆盖转化为基于特征点集的优化问题.利用改进粒子群算法解算此优化问题,通过惯性权重及局部增强因子扰动项,避免其陷入早熟状态;同时,针对集中式PSO算法不适用于无线传感网的问题,本文提出了一种并行分区式策略.仿真分析验证了所提算法的优越性和特征点距上界的存在性,该方法为区域覆盖问题的研究提供了新的思路.

关键词: 无线传感器网络, 覆盖约束优化, 概率感知模型, 特征点集, 惯性权重, 并行分区式粒子群算法

Abstract:

Traditional grid point-based area coverage methods are committed to algorithm optimization,causing coarse approximation and high complexity problems.In order to solve these problems,based on the probabilistic sensing model,we first study the sensing probabilities of two adjacent points and obtain the fundamental mathematical relationship between them.According to this relationship,we define the concept of feature point set (FPS) to character the area.Then,we transform the probabilistic area coverage into optimization problem of FPS.Further,we design an improved particle swarm optimization (IWPSO) algorithm to solve this optimization problem,which can effectively avoid the premature problems in the convergence of PSO algorithm.Finally,through extensive simulations,we demonstrate that our algorithm outperforms the proposed solutions significantly,and provides a new train of thought for area coverage problem.

Key words: wireless sensor networks, coverage optimization problem, probabilistic sensing model, feature point set, inertia weight, parallel local particle swarm optimization

中图分类号:

TP393.02

丁旭, 吴晓蓓, 黄成. 基于改进粒子群算法和特征点集的无线传感器网络覆盖问题研究[J]. 电子学报, 2016, 44(4): 967-973.

DING Xu, WU Xiao-bei, HUANG Cheng. Area Coverage Problem Based on Improved PSO Algorithm and Feature Point Set in Wireless Sensor Networks[J]. Acta Electronica Sinica, 2016, 44(4): 967-973.

参考文献

[1] 李劲,岳昆,等.基于融合的无线传感器网络k-集覆盖的分布式算法[J].电子学报,2013,41(4):659-665. LI Jin,YUE Kun,et al.Distributed set k-cover algorithms for fusion-based coverage in wireless sensor networks[J].Acta Electronica Sinica,2013,41(4):659-665.(in Chinese)
[2] WANG Xue-qing,ZHANG Shu-qin.Research on efficient coverage problem of node in wireless sensor networks[A].Proceedings of International Conference on Industrial Mechatronics and Automation[C].Chengdu,China:IEEE,2009.9-13.
[3] 陆克中,等.有向传感器网络覆盖增强问题的贪婪迭代算法[J].电子学报,2012,40(4):688-694. LU Ke-zhong,et al.A greedy iterative algorithm of coverage enhancing problem in direction sensor network[J].Acta Electronica Sinica,2012,40(4):688-694.(in Chinese)
[4] J Li,J Chen,T H Lai.Energy-efficient intrusion detection with a barrier of probabilistic sensors[A].Proceedings of IEEE Infocom[C].Orlando:IEEE,2012.118-126.
[5] M T XIANG,et al.Condition for the coverage and connectivity of wireless sensor network[A].Proceedings of Advanced Materials Research[C].Switzerland:TTP,2012.2589-2592.
[6] LI Hui,ZHANG Xiao-guang,et al.A hybrid deployment algorithm based on clonal selection and artificial physics optimization for wireless sensor network[J].Information Technology Journal,2013,12(5):917-925.
[7] Shen,et al.Grid scan:a simple and effective approach for coverage issue in wireless sensor networks[A].Proceedings of IEEE International Conference Communications[C].Istanbul:IEEE,2006.3480-3484.
[8] M HEFEEDA,H AHMADI.Energy-efficient protocol for deterministic and probabilistic coverage in sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2010,21(5):579-593.
[9] KUMLACHEW M W,GARY G Y.Vaccine-enhanced artificial immune system for multimodal function optimization[J].IEEE Transactions on System,Man,and Cybernetics-Part B:Cybernetics,2010,40(1):218-228.
[10] Y YOON,Y H KIM.An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks[J].IEEE Transactions on Cybernetics,2013,43(5):2168-2267.
[11] Hu X M,Zhang J,et al.Hybrid genetic algorithm using a forward encoding scheme for lifetime maximization of wireless sensor networks[J].IEEE Trans Evol Comput,2010,14(5):766-781.
[12] Yang Q,He S,et al.Energy-efficient probabilistic full coverage in wireless sensor networks[A].Proceedings of IEEE GlobeCom[C].Anaheim:IEEE,2012.591-596.
[13] B ANAND,I AAKASH.Improvisation of particle swarm optimization algorithm[A].Proceedings of International Conference on Signal Processing and Integrated Networks[C].Noida:IEEE,2014.20-24.
[14] 刘维亭,范洲远.基于混沌粒子群算法的无线传感器网络覆盖优化[J].计算机应用,2011,31(2):338-341. LIU Wei-ting,FAN Zhou-yuan.Coverage optimization of wireless sensor network based on chaos particle swarm optimization algorithm[J].Journal of Computer Applications,2011,31(2):338-341.(in Chinese)
[15] W Z W,et al.Study on coverage in wireless sensor network using grid based strategy and particle swarm optimization[A].Proceedings of IEEE Asia Pacific Conference on Circuits and Systems[C].Kuala Lumpur:IEEE,2010.1175-1178.
[16] S Y H,et al.Empirical study of particle swarm optimization[A].Proceedings of the IEEE Congress on Evolutionary Computation[C].Washington DC:IEEE,1999.1945 -1950.
[17] KULKARNI R V,et al.Particle swarm optimization in wireless sensor networks:a brief survey[J].IEEE Trans on Systems,Man and Cybernetics,2010,41(2):262-267.
[18] 王雪,等.无线传感网络布局的虚拟力导向微粒群优化策略[J].电子学报,2007,35(11):2039-2042. WANG Xue,et al.Dynamic sensor deployment strategy based on virtual force-directed particle swarm optimization in wireless sensor networks[J].Acta Electronica Sinica,2007,35(11):2039-2042.(in Chinese)

基于改进粒子群算法和特征点集的无线传感器网络覆盖问题研究

Area Coverage Problem Based on Improved PSO Algorithm and Feature Point Set in Wireless Sensor Networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈嘉兴, 程杰, 董云玲, 刘志华. 基于弯曲声线和测距修正的水下节点定位算法[J]. 电子学报, 2022, 50(7): 1567-1572.
[2]	王义君, 陈忠野, 缪瑞新, 宋忠炎. 基于三角剖分的WSNs元胞感知覆盖算法[J]. 电子学报, 2022, 50(10): 2443-2451.
[3]	汪成亮, 赵凯, 刘嘉敏. 智能环境下基于边缘设备规则推理的数据预部署研究[J]. 电子学报, 2022, 50(10): 2347-2360.
[4]	刘景森, 马义想, 李煜. 改进蝴蝶算法求解多维复杂函数优化问题[J]. 电子学报, 2021, 49(6): 1068-1076.
[5]	苏志刚, 武瑞, 郝敬堂. 面向无源定位的直达波传感器识别算法[J]. 电子学报, 2021, 49(6): 1178-1186.
[6]	王海东, 刘云敬, 康琳, 武迎春. 射频能量捕获传感网移动能量源的布置策略研究[J]. 电子学报, 2020, 48(12): 2367-2375.
[7]	程杰, 董云玲, 陈嘉兴, 刘志华. 一种具有连续跳数值的三维DV-Hop改进算法[J]. 电子学报, 2020, 48(11): 2122-2130.
[8]	黄美根, 郁滨. 软件定义WSN规则一致更新研究[J]. 电子学报, 2019, 47(9): 1965-1971.
[9]	王頲, 白桦, 唐晓铭, 黄庆卿. 分布式全局精确时钟同步状态追踪:能观测性观测器分析[J]. 电子学报, 2019, 47(9): 1855-1862.
[10]	丁旭, 吴晓蓓, 王力立, 张新宇, 夏昕. 无线传感器网络中基于最优转发集的协作式编码传输协议[J]. 电子学报, 2019, 47(7): 1584-1590.
[11]	邱树伟, 石海燕, 池凯凯, 程珍, 朱艺华. 射频供能无线传感器网络高能效数据收集方案[J]. 电子学报, 2018, 46(9): 2238-2244.
[12]	田文飚, 芮国胜, 董道广, 康健. 基于盲自适应KLT的蒸发波导压缩感知方法[J]. 电子学报, 2018, 46(9): 2068-2074.
[13]	房卫东, 张武雄, 杨旸, 张传雷, 陈伟. 基于生物特征标识的无线传感器网络三因素用户认证协议[J]. 电子学报, 2018, 46(3): 702-713.
[14]	李国瑞, 王颖, 王聪. 一种基于矩阵补全的无线传感网数据收集方案[J]. 电子学报, 2018, 46(12): 2950-2956.
[15]	田贤忠, 祝驿楠, 何佳存, 郭敏, 刘高. 一种射频能量捕获网络移动能量源均衡化充电策略[J]. 电子学报, 2018, 46(12): 2985-2992.