Wireless sensor deployment optimization based on improved IHACA-CpSPIEL algorithm

doi:10.11772/j.issn.1001-9081.2019071201

Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (3): 793-798.DOI: 10.11772/j.issn.1001-9081.2019071201

• Network and communications • Previous Articles Next Articles

Wireless sensor deployment optimization based on improved IHACA-CpSPIEL algorithm

DUAN Yujun¹, WANG Yaoli¹, CHANG Qing¹, LIU Xing²

1. College of Information and Computer, Taiyuan University of Technology, Taiyuan Shanxi 030024, China;
2. Network Center, 32152 Troops, Shijiazhuang Hebei 050000, China

Received:2019-07-10 Revised:2019-10-11 Online:2020-03-10 Published:2019-10-25
Supported by:
This work is partially supported by the National Natural Science Foundation of China(61828601), the Natural Science Foundation of Shanxi Province(201801D121141).

改进型蚁群算法融合混沌优化的pSPIEL算法的无线传感器布局优化

段宇君¹, 王耀力¹, 常青¹, 刘鑫²

1. 太原理工大学信息与计算机学院, 太原 030024;
2. 32152部队网络中心, 石家庄 050000

通讯作者: 常青
作者简介:段宇君(1993-),女,山西太原人,硕士研究生,主要研究方向:无线传感器布局;王耀力(1965-),男,山西太原人,副教授,博士,主要研究方向:智能感知与架构、人机视觉处理与分析;常青(1975-),男,河南洛阳人,副教授,博士,主要研究方向:人机视觉处理与分析、嵌入式电路设计;刘鑫(1988-),男,山东淄博人,硕士,主要研究方向:无线通信。
基金资助:
国家自然科学基金资助项目（61828601）；山西省自然科学基金资助项目（201801D121141）。

Abstract

Abstract: Aiming at the problems of low coverage and high communication cost for wireless sensor deployment, an Improved Heuristic Ant Colony Algorithm (IHACA) merging Chaos optimization of padded Sensor Placements at Informative and cost-Effective Locations algorithm (IHACA-CpSPIEL) method for sensor deployment was proposed. Firstly, the correlation between observation points and unobserved points was established by mutual information, and the communication cost was described in the form of graph theory to establish the mathematical model with submodularity. Secondly, chaos operator was introduced to improve the global searching ability of pSPIEL (padded Sensor Placements at Informative and cost-Effective Locations) algorithm for local parameters, and then the optimal number of clusters was found. Then, the factors of the colony distance heuristic function and the pheromone updating mechanism were changed to jump out of the local solution of communication cost. Finally, Chaos optimization of pSPIEL algorithm (CpSPIEL) was integrated with the IHACA to determine the shortest path, so as to achieve the purpose of low-cost deployment. The experimental results show that the proposed algorithm can jump out of the local optimal solution well, and the communication cost is reduced by 6.5% to 24.0% compared with the pSPIEL algorithm, and has a faster search speed.

Key words: wireless sensor, sensor deployment, communication cost, padded Sensor Placements at Informative and cost-Effective Locations （pSPIEL）, chaotic operator, Ant Colony Algorithm

摘要： 针对无线传感器布局存在覆盖率低、通信成本高等问题，提出一种基于改进蚁群算法（IHACA）的融合混沌优化pSPIEL算法（IHACA-CpSPIEL）的传感器布局方法。首先，采用互信息量建立观测点与未观测点间相关性，并以图论形式对通信成本进行描述，建立具有子模性的数学模型；其次，引入混沌算子以提高pSPIEL算法局部性参数的整体搜索能力，进而找到最优分簇个数；然后，更改蚁群距离启发函数因子及信息素更新机制以跳出通信成本局部解；最后，将基于混沌优化的pSPIEL （CpSPIEL）与IHACA融合以确定出最短路径，从而实现低成本部署的目的。实验结果表明，该算法能够较好地跳出局部最优解，且通信成本比pSPIEL算法减少了6.5%~24.0%，具有更快的搜索速度。

关键词: 无线传感器, 传感器布局, 通信成本, pSPIEL, 混沌算子, 蚁群算法

CLC Number:

TP212.9

DUAN Yujun, WANG Yaoli, CHANG Qing, LIU Xing. Wireless sensor deployment optimization based on improved IHACA-CpSPIEL algorithm[J]. Journal of Computer Applications, 2020, 40(3): 793-798.

段宇君, 王耀力, 常青, 刘鑫. 改进型蚁群算法融合混沌优化的pSPIEL算法的无线传感器布局优化[J]. 计算机应用, 2020, 40(3): 793-798.

References

[1] SUGIURA K. SuMo-SS:submodular optimization sensor scattering for deploying sensor networks by drones[J]. IEEE Robotics and Automation Letters,2018,3(4):2963-2970.
[2] SUN C,YU Y,LI V,et al. Multi-type sensor placements in Gaussian spatial fields for environmental monitoring[J]. Sensors,2019, 19(1):No. 189.
[3] GUESTRIN C,KRAUSE A,SINGH A P. Near-optimal sensor placements in Gaussian processes[C]//Proceedings of the 22nd International Conference on Machine Learning. New York:ACM, 2005:265-272.
[4] KRAUSE A. Optimizing sensing:theory and applications[D]. Pittsburgh,PA:Carnegie Mellon University,2008.
[5] KRAUSE A. SFO:a toolbox for submodular function optimization[J]. Journal of Machine Learning Research,2010,11:1141-1144.
[6] WU X,LIU M,WU Y. In-situ soil moisture sensing:optimal sensor placement and field estimation[J]. ACM Transactions on Sensor Networks,2012,8(4):No. 33.
[7] COUTINO M,CHEPURI S P,LEUS G. Submodular sparse sensing for Gaussian detection with correlated observations[J]. IEEE Transactions on Signal Processing,2018,66(15):4025-4039.
[8] SUN C,LI V O K,LAM J C K. Optimal citizen-centric sensor placement for citywide environmental monitoring-a submodular approach[C]//Proceedings of the 2018 IEEE International Conference on Sensing,Communication and Networking. Piscataway:IEEE,2018:1-4.
[9] 王振东, 陈峨霖, 胡中栋. 基于混沌优化细菌觅食算法的传感器节点部署策略[J]. 传感技术学报,2018,31(1):110-118. (WANG Z D,CHEN E L,HU Z D. Sensor node deployment strategy of chaotic optimization of bacterial foraging algorithm[J]. Chinese Journal of Sensors and Actuators,2018,31(1):110-118.)
[10] 郑延斌, 王林林, 席鹏雪, 等. 基于蚁群算法及博弈论的多Agent路径规划算法[J]. 计算机应用,2019,39(3):681-687. (ZHENG Y B,WANG L L,XI P X,et al. Multi-Agent path planning algorithm based on ant colony algorithm and game theory[J]. Journal of Computer Applications,2019,39(3):681-687.)
[11] QASIM T,ZIA M,MINHAS Q A,et al. An ant colony optimization based approach for minimum cost coverage on 3-D grid in wireless sensor networks[J]. IEEE Communications Letters,2018,22(6):1140-1143.
[12] CASELTON W F,ZIDEK J V. Optimal monitoring network designs[J]. Statistics and Probability Letters, 1984, 2(4):223-227.
[13] NIAZADEH R,ROUGHGARDEN T,WANG J R. Optimal algorithms for continuous non-monotone submodular and DR-submodular maximization[C]//Proceedings of the 32nd International Conference on Neural Information Processing Systems. New York:Curran Associates Inc.,2018:9617-9627.
[14] ILVES K,HARNEFORS L,NORRGA S,et al. Predictive sorting algorithm for modular multilevel converters minimizing the spread in the submodule capacitor voltages[J]. IEEE Transactions on Power Electronics,2015,30(1):440-449.
[15] 李娟, 游晓明, 刘升, 等. 动态混沌蚁群系统及其在机器人路径规划中的应用[J]. 计算机应用,2018,38(1):126-131.(LI J, YOU X M,LIU S,et al. Dynamic chaotic ant colony system and its application in robot path planning[J]. Journal of Computer Applications,2018,38(1):126-131.)
[16] BACH F. Submodular functions:from discrete to continuous domains[J]. Mathematical Programming, 2019, 175(1/2):419-459.

Wireless sensor deployment optimization based on improved IHACA-CpSPIEL algorithm

改进型蚁群算法融合混沌优化的pSPIEL算法的无线传感器布局优化

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	TANG Andi, HAN Tong, XU Dengwu, XIE lei. Chaotic elite Harris hawks optimization algorithm [J]. Journal of Computer Applications, 2021, 41(8): 2265-2272.
[2]	SUN Huan, CHEN Hongbin. Node redeployment strategy based on firefly algorithm for wireless sensor network [J]. Journal of Computer Applications, 2021, 41(2): 492-497.
[3]	HAN Yulao, FANG Dingyi. Lightweight coverage hole detection algorithm based on relative position of link intersections [J]. Journal of Computer Applications, 2020, 40(9): 2698-2705.
[4]	HU Runyan, LI Cuiran. Clustering algorithm of energy harvesting wireless sensor network based on fuzzy control [J]. Journal of Computer Applications, 2020, 40(9): 2691-2697.
[5]	CHENG Xiaohui, NIU Tong, WANG Yanjun. Wireless sensor network intrusion detection system based on sequence model [J]. Journal of Computer Applications, 2020, 40(6): 1680-1684.
[6]	HAN Yulao, FANG Dingyi. Multi-objective path planning algorithm for mobile charging devices jointing wireless charging and data collection [J]. Journal of Computer Applications, 2020, 40(6): 1745-1750.
[7]	LU Guangyue, ZHOU Liang, LYU Shaoqing, SHI Cong, SU Keke. Outlier node detection algorithm in wireless sensor networks based ongraph signal processing [J]. Journal of Computer Applications, 2020, 40(3): 783-787.
[8]	ZHANG Zhengwan, ZHANG Chunjiong, LI Hongbing, XIE Tao. Multipath transmission selection algorithm based on immune connectivity model [J]. Journal of Computer Applications, 2020, 40(12): 3571-3577.
[9]	QU Licheng, LYU Jiao, ZHAO Ming, WANG Haifei, QU Yihua. Multi-robot path planning algorithm based on 3D spatiotemporal maps and motion decomposition [J]. Journal of Computer Applications, 2020, 40(12): 3499-3507.
[10]	LIU Yuliang, CHEN Huaili. Distribution path planning and charging strategy for pure electric vehicles with load constraint [J]. Journal of Computer Applications, 2020, 40(10): 2831-2837.
[11]	WU Sanzhu, LI Peng, WU Sanbin. Virus propagation suppression model in mobile wireless sensor networks [J]. Journal of Computer Applications, 2020, 40(1): 129-135.
[12]	REN Xiuli, CHEN Yang. Routing protocol optimized for data transmission delay in wireless sensor networks [J]. Journal of Computer Applications, 2020, 40(1): 196-201.
[13]	LI Zhuo, LI Yinzhen, LI Wenxia. Multi-objective optimization model and solution algorithm for emergency material transportation path [J]. Journal of Computer Applications, 2019, 39(9): 2765-2771.
[14]	WANG Dongxian, MENG Xuelei, QIAO Jun, TANG Lin, JIAO Zhizhen. Railway crew routing plan based on improved ant colony algorithm [J]. Journal of Computer Applications, 2019, 39(9): 2749-2756.
[15]	DONG Fazhi, DING Hongwei, YANG Zhijun, XIONG Chengbiao, ZHANG Yingjie. WSN clustering routing algorithm based on genetic algorithm and fuzzy C-means clustering [J]. Journal of Computer Applications, 2019, 39(8): 2359-2365.