基于VF-CS的移动传感器网络覆盖优化算法

doi:10.11959/j.issn.1000-436x.2018039

通信学报 ›› 2018, Vol. 39 ›› Issue (3): 95-107.doi: 10.11959/j.issn.1000-436x.2018039

• 论文Ⅰ：物联网与安全 • 上一篇下一篇

基于VF-CS的移动传感器网络覆盖优化算法

李光辉^1,^2,³,胡世红^1,³

¹ 江南大学物联网工程学院，江苏无锡 214122
² 江苏省无线传感网高技术研究重点实验室，江苏南京 210003
³ 物联网技术应用教育部工程技术研究中心，江苏无锡 214122

修回日期:2018-02-14 出版日期:2018-03-01 发布日期:2018-04-02
作者简介:李光辉（1970-），男，湖南郴州人，博士，江南大学教授、博士生导师，主要研究方向为无线传感器网络、容错计算、无损检测技术。|胡世红（1993-），女，江苏连云港人，江南大学硕士生，主要研究方向为无线传感器网络覆盖优化。
基金资助:
国家自然科学基金资助项目(61472368);国家自然科学基金资助项目(61174023);江苏省重点研发计划基金资助项目(BE2016627);中央高校基本科研业务费专项资金基金资助项目(RP51635B);无锡市国际科技研发合作基金资助项目(CZE02H1706)

Coverage optimization algorithm based on VF-CS in mobile sensor network

Guanghui LI^1,^2,³,Shihong HU^1,³

¹ School of Computer Technology,Jiangnan University,Wuxi 214122,China
² Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks,Nanjing 210003,China
³ Research Center of IoT Technology Application Engineering (MOE),Wuxi 214122,China

Revised:2018-02-14 Online:2018-03-01 Published:2018-04-02
Supported by:
The National Natural Science Foundation of China(61472368);The National Natural Science Foundation of China(61174023);The Key Project of the Jiangsu Provincial Research and Development(BE2016627);The Fundamental Research Funds for the Central Universities(RP51635B);International Scientific and Technological Cooperation Projects of Wuxi(CZE02H1706)

摘要/Abstract

摘要：

在野外环境部署大规模传感器网络时，往往采用随机部署方式，导致覆盖率不高。为此提出一种基于虚拟力（virtual force）扰动和布谷鸟搜索（CS,Cuckoo search）的移动传感器网络覆盖优化算法（VF-CS）。首先，对传感器节点进行Voronoi图划分，形成独立的泰森多边形（Thiessen polygon）。其次，对泰森多边形内的节点进行虚拟力的分析，将多边形顶点和邻居节点的作用力作为布谷鸟搜索位置更新的扰动因子。最后，通过布谷鸟搜索引导节点移动实现覆盖优化。仿真实验结果表明，与以往基于Voronoi图的覆盖优化算法相比，VF-CS算法提高了覆盖率，减少了节点平均移动距离。

关键词: 移动传感网络, 虚拟力, 布谷鸟搜索, 覆盖率, 优化

Abstract:

A random placement of large-scale sensor network in the outdoor environment often causes low coverage.An area coverage optimization algorithm of mobile sensor network (MSN) based on virtual force perturbation and Cuckoo search (VF-CS) was proposed.Firstly,the virtual force of the sensor nodes within the Thiessen polygon was analyzed based on the partitioning of Voronoi diagram of the monitoring area.Secondly,the force of polygon vertices and neighbor nodes was taken as the perturbation factor for updating the node’s location of the Cuckoo search (CS).Finally,the VF-CS guided the node to move so as to achieve the optimal coverage.The simulation results demonstrate that the proposed algorithm has higher coverage and shorter average moving distance of nodes than the Voronoi diagram based algorithms in literatures.

Key words: mobile sensor network, virtual force, Cuckoo search, coverage, optimization

中图分类号:

TP393

李光辉,胡世红. 基于VF-CS的移动传感器网络覆盖优化算法[J]. 通信学报, 2018, 39(3): 95-107.

Guanghui LI,Shihong HU. Coverage optimization algorithm based on VF-CS in mobile sensor network[J]. Journal on Communications, 2018, 39(3): 95-107.

图/表 15

图1

图2

图3

图4

图5

图6

图7

表1

图8

表2

图9

图10

图11

表3

表4

参考文献 28

[1]	ISBITIREN G , AKAN O B . Three-dimensional underwater target tracking with acoustic sensor networks[J]. IEEE Transactions on Vehicular Technology, 2011,60(8): 3897-3906.
[2]	SHAIMAA M,MOHAMED , HAITHAM S ,et al. Coverage in mobile wireless sensor networks (M-WSN):a survey[J]. Computer Communications, 2017,1(66): 133-150.
[3]	ZHU C , SHU L , HARA T ,et al. Research issues on mobile sensor networks[C]// International ICST Conference on Communications and NETWORKING . 2010: 1-6.
[4]	MUNIR S A , REN B , JIAO W ,et al. Mobile wireless sensor network:architecture and enabling technologies for ubiquitous computing[C]// International Conference on Advanced Information NETWORKING and Applications Workshops. 2007: 113-120.
[5]	刘惠, 柴志杰, 杜军朝 ,等. 基于组合虚拟力的传感器网络三维空间重部署算法研究[J]. 自动化学报, 2011,37(6): 713-723.
	LIU H , CHAI Z J , DU J C ,et al. Sensor redeployment algorithm based on combined virtual forces in three dimensional space[J]. Acta Automatica Sinica, 2011,37(6): 713-723.
[6]	石为人, 袁久银, 雷璐宁 . 无线传感器网络覆盖控制算法研究[J]. 自动化学报, 2009,35(5): 540-545.
	SHI W R , YUAN J Y , LEI L N . Research on wireless sensor network coverage control algorithm[J]. Acta Automatica Sinica, 2009,35(5): 540-545.
[7]	AHMAD P A , MAHMUDDIN M , OMAR M H . Virtual force algorithm and cuckoo search algorithm for node placement technique in wireless sensor network[C]// The 4th International Conference on Computing and Informatics. 2013: 28-30.
[8]	JIN L , CHANG G , JIA J . Mobile sensor networks node distribution optimization based on minimum redundant coverage[C]// Chinese Control Conference. 2010: 4851-4856.
[9]	丁旭, 吴晓蓓, 黄成 . 基于改进粒子群算法和特征点集的无线传感器网络覆盖问题研究[J]. 电子学报, 2016,44(4): 967-973.
	DING X , WU X B , HUANG C . Area coverage problem based on improved PSO algorithm and feature point set in wireless sensor net-works[J]. Acta Electronica Sinica, 2016,44(4): 967-973.
[10]	李劲, 岳昆, 刘惟一 . 基于融合的无线传感器网络 k-集覆盖的分布式算法[J]. 电子学报, 2013,41(4): 659-665.
	LI J , YUE K , LIU W Y . Distributed set k-cover algorithms for fu-sion-based coverage in wireless sensor networks[J]. Acta Electronica Sinica, 2013,41(4): 659-665.
[11]	庄曜铭, 吴成东, 张云洲 ,等. 无线传感器网络中复合事件栅栏覆盖问题[J]. 通信学报, 2017,38(6): 75-84.
	ZHUANG Z M , WU C D , ZHANG Y Z ,et al. Compound event barri-er coverage in wireless sensor network[J]. Journal on Communications, 2017,38(6): 75-84.
[12]	ADULYASAS A , SUN Z , WANG N . Connected coverage optimization for sensor scheduling in wireless sensor networks[J]. IEEE Sensors Journal, 2015,15(7): 3877-3892.
[13]	ALDURAIBI F , LASLA N , YOUNIS M . Coverage-based node placement optimization in wireless sensor network with linear topology[C]// IEEE International Conference on Communications. 2016: 107-124.
[14]	XIA J , . Coverage optimization strategy of wireless sensor network based on swarm intelligence algorithm[C]// International Conference on Smart City and Systems Engineering. 2017: 179-182.
[15]	DAOUDI A , DETIENNE B , AZOUZI R E ,et al. Robust coverage optimization approach in wireless sensor networks[C]// International Conference on Wireless Networks and Mobile Communications. 2017: 1-7.
[16]	SHEN Z , CHANG Y , JIANG H ,et al. A generic framework for optimal mobile sensor redeployment[J]. IEEE Transactions on Vehicular Technology, 2010,59(8): 4043-4057.
[17]	涂志亮, 王强, 沈毅 . 移动传感器网络中目标跟踪与监测的同步优化[J]. 自动化学报, 2012,38(3): 452-461.
	TU Z L , WANG Q , SHEN Y . A distributed simultaneous optimization algorithm for tracking and monitoring of moving target in mobile sen-sor networks[J]. Acta Automatica Sinica, 2012,38(3): 452-461.
[18]	BOUKERCHE A , XIN F . A voronoi approach for coverage protocols in wireless sensor networks[C]// Global Telecommunications Conference. 2007: 5190-5194.
[19]	LEE H J , KIM Y H , HAN Y H ,et al. Centroid-based movement assisted sensor deployment schemes in wireless sensor networks[C]// Vehicular Technology Conference Fall. 2009: 1-5.
[20]	方伟, 宋鑫宏 . 基于Voronoi图盲区的无线传感器网络覆盖控制部署策略[J]. 物理学报, 2014,63(22): 128-137.
	FANG W , SONG X H . A deployment strategy for coverage control in wireless sensor networks based on the blind-zone of voronoi dia-gram[J]. Acta Physica Sinica, 2014,63(22): 128-137.
[21]	ABO-ZAHHAD M , SABOR N , SASAKI S ,et al. A centralized immune-Voronoi deployment algorithm for coverage maximization and energy conservation in mobile wireless sensor networks[J]. Information Fusion, 2016,30(C): 36-51.
[22]	周彤, 洪炳镕, 朴松昊 . 基于虚拟力的混合感知网节点部署[J]. 计算机研究与发展, 2007,44(6): 965-972.
	ZHOU T , HONG B R , PU S H . Hybrid sensor networks deployment based on virtual force[J]. Journal of Computer Research and Development, 2007,44(6): 965-972.
[23]	MAHBOUBI H , AGHDAM A G . Distributed deployment algorithms for coverage improvement in a network of wireless mobile sensors:relocation by virtual force[J]. IEEE Transactions on Control of Network Systems, 2016,PP(99): 1-14.
[24]	MAHBOUBI H , AGHDAM A G . An energy-efficient strategy to improve coverage in a network of wireless mobile sensors with nonidentical sensing ranges[J]. Vehicular Technology Conference (VTC Spring), 2013,14(2382): 1-5.
[25]	DEB S , YANG X S . Cuckoo search via levy flights[C]// World Congress on Nature ＆ Biologically Inspired Computing. 2009: 210-214.
[26]	LIU C , CHUNMING Y E . Cuckoo search algorithm for the problem of permutation flow shop scheduling[J]. Journal of University of Shanghai for Science ＆ Technology, 2013,35(1): 17-20.
[27]	YANG X S , DEB S . Multiobjective cuckoo search for design optimization[J]. Computers ＆ Operations Research, 2013,40(6): 1616-1624.
[28]	AMMARI H M , DAS S K . Coverage,connectivity,and fault tolerance measures of wireless sensor networks[M]. Stabilization,Safety,and Security of Distributed Systems. Heidelberg: Springer, 2006: 35-49.

仿真	区域大小	节点个数（N）
	100 m×100 m	90、80、70、60、50、40
实验1	200 m×200 m	340、320、300、280、260、240
	350 m×350 m	1 000、900、800、700、600、500
	100 m×100 m	90
实验2	200 m×200 m	340
	350 m×350 m	1 000

区域大小	节点个数（N）	VF-CS算法覆盖率	BCBS算法覆盖率	CBS算法覆盖率	CIVDA算法覆盖率
	90	0.989 9	0.989 8	0.972 0	0.928 3
	80	0.965 5	0.957 0	0.947 6	0.872 6
100 m×100 m	70	0.933 9	0.919 3	0.920 6	0.844 0
	60	0.858 6	0.849 5	0.830 9	0.783 8
	50	0.809 0	0.773 2	0.754 4	0.698 6
	40	0.702 0	0.700 3	0.683 2	0.612 7
	340	0.987 2	0.978 6	0.978 8	0.907 7
	320	0.965 1	0.955 4	0.952 3	0.884 5
200 m×200 m	300	0.959 7	0.942 9	0.943 3	0.845 6
	280	0.939 0	0.922 1	0.917 2	0.808 0
	260	0.904 3	0.891 3	0.883 7	0.799 3
	240	0.882 1	0.856 5	0.845 9	0.776 8
	1 000	0.983 6	0.974 6	0.968 7	0.879 9
	900	0.969 9	0.949 2	0.932 3	0.833 2
350 m×350 m	800	0.931 2	0.905 1	0.894 4	0.775 9
	700	0.853 7	0.835 1	0.827 4	0.646 3
	600	0.776 8	0.746 4	0.714 4	0.597 6
	500	0.659 3	0.628 7	0.606 5	0.553 6

区域大小	节点个数（N）	算法
区域大小	节点个数（N）	VF-CS耗时/s	BCBS耗时/s	CBS耗时/s	CIVDA耗时/s
	90	59.046 2	251.723 7	52.758 0	16.911 0
	80	57.353 8	178.180 0	47.789 2	14.983 1
100 m×100 m	70	39.680 0	118.417 4	50.691 6	15.829 2
	60	44.431 9	131.474 0	39.778 4	14.601 2
	50	43.961 0	124.783 5	36.496 7	12.962 3
	40	33.454 0	108.393 2	33.846 3	11.335 9
	340	742.342 0	1 936.584 3	1 256.473 3	287.458 1
	320	704.561 0	1 843.874 0	1 189.490 0	260.569 0
200 m×200 m	300	650.460 0	1 729.332 0	1 054.730 0	252.650 0
	280	639.212 0	1 696.370 0	998.543 0	238.791 0
	260	611.851 0	1 509.321 0	943.560 0	227.650 0
	240	598.443 0	1 393.428 0	885.430 0	216.314 0
	1 000	4 228.239 0	11 507.883 0	6 826.560 0	628.381 0
	900	3 832.467 0	10 458.660 0	6 243.489 0	537.246 0
350 m×350 m	800	2 548.260 0	6 644.470 0	4 573.630 0	483.620 0
	700	2 003.724 0	5 075.567 0	3 229.692 0	448.493 0
	600	1 337.370 0	3 911.877 0	2 866.482 0	403.720 0
	500	1 072.951 0	3 407.689 0	2 247.266 0	377.633 0

算法	覆盖效率（100 m×100 m）			覆盖效率（200 m×200 m）			覆盖效率（350 m×350 m）
算法	N=90	N=70	N=50	N=340	N=300	N=260	N=1 000	N=800	N=600
VF-CS	0.678 1	0.789 2	0.800 2	0.667 8	0.797 7	0.849 6	0.703 4	0.776 5	0.825 3
BCBS	0.659 9	0.748 7	0.799 8	0.655 5	0.786 1	0.832 1	0.684 5	0.749 3	0.812 6

基于VF-CS的移动传感器网络覆盖优化算法

Coverage optimization algorithm based on VF-CS in mobile sensor network

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 28

相关文章 15

Metrics

推荐阅读 0

[1]	李竟博, 马礼, 李阳, 傅颖勋, 马东超. 感传算协同工业互联网优化设计[J]. 通信学报, 2023, 44(6): 12-22.
[2]	张平, 戴金晟, 张育铭, 王思贤, 秦晓琦, 牛凯. 面向语义通信的非线性变换编码[J]. 通信学报, 2023, 44(4): 1-14.
[3]	蒋丽, 谢胜利, 田辉. 面向数字孪生边缘网络的区块链分片及资源自适应优化机制[J]. 通信学报, 2023, 44(3): 12-23.
[4]	余雪勇, 邱礼翔, 宋家宁, 朱洪波. 无人机辅助边缘计算中安全通信与能效优化策略[J]. 通信学报, 2023, 44(3): 45-54.
[5]	张雷, 王玉, 田建杰, 张琳, 章天骄. 基于IRS辅助的MIMO车联网系统联合波束成形设计[J]. 通信学报, 2023, 44(2): 59-69.
[6]	赵庶旭, 韦萍, 王小龙. 多任务并发边缘计算环境中最优联盟结构生成策略[J]. 通信学报, 2023, 44(2): 172-184.
[7]	王彬, 任露, 王晓帆, 曹雅娟. 基于协方差分析的合作协同进化差分进化算法[J]. 通信学报, 2023, 44(1): 189-199.
[8]	胡强, 田雨晴, 綦浩泉, 吴鹏, 刘庆雪. 基于改进人工蜂群算法的云制造服务组合优化方法[J]. 通信学报, 2023, 44(1): 200-210.
[9]	聂宏蕊, 李绍胜, 刘勇. 时间敏感网络中基于IEEE 802.1Qch标准的优化调度机制[J]. 通信学报, 2022, 43(9): 12-26.
[10]	杨震, 冯璇, 吕斌. 智能反射面辅助的两跳中继无线供电通信网络吞吐量最大化研究[J]. 通信学报, 2022, 43(9): 90-99.
[11]	许文俊, 吴思雷, 王凤玉, 林兰, 李国军, 张治. 基于多智能体强化学习的大规模灾后用户分布式覆盖优化[J]. 通信学报, 2022, 43(8): 1-16.
[12]	郭海燕, 杨震, 邹玉龙, 吕斌, 冯蕴天, 赵玉娟. 基于主被动波束成形联合优化的双RIS辅助抗干扰通信方法[J]. 通信学报, 2022, 43(7): 21-30.
[13]	何世文, 袁军, 安振宇, 张敏, 黄永明, 张尧学. 基于图神经网络的联合用户调度与波束成形优化算法[J]. 通信学报, 2022, 43(7): 73-84.
[14]	朱思峰, 蔡江昊, 柴争义, 孙恩林. 车联网云边协同计算场景下的多目标优化卸载决策[J]. 通信学报, 2022, 43(6): 223-234.
[15]	李翠然, 王雪洁, 谢健骊, 吕安琪. 基于改进PSO的铁路监测线性无线传感器网络路由算法[J]. 通信学报, 2022, 43(5): 155-165.