本期推荐
本栏目责任编辑：唐一东
曹娜娜，谢智峰，穆莉，王汐存
（江西科技学院信息工程学院，江西南昌330098）
摘要：为解决WSN 随机部署方法导致覆盖率低的问题，提出了一种基于萤火虫算法的WSN 自适应部署方法。该方法融合
概率感知模型和萤火虫算法两种技术，建立网格覆盖模型，实现WSN 节点优化部署。设计了3组仿真测试，实验结果表明，新方法相较于随机部署方法，其测覆盖率有所提升。关键词：WSN ；随机部署；萤火虫算法；概率感知模型；网格覆盖模型中图分类号：TP301、TP391
文献标识码:A
文章编号：1009-3044(2021)03-0005-03
开放科学（资源服务）标识码（OSID ）:
Application of Firefly Algorithm in WSN Node Deployment CAO Na-na,XIE Zhi-feng,MU Li,WANG Xi-cun
(School of Information Engineering,Jiangxi University of Technology,Nanchang 330098,China)Abstract:In order to solve the problem of low coverage caused by the random deployment method of WSN,a WSN adaptive deploy⁃ment method based on the Firefly algorithm is proposed.This method fuses two technologies,the probability perception model and the firefly algorithm,to establish a grid coverage model to achieve optimal deployment of WSN nodes.Three sets of simulation tests are designed,and the experimental results show that compared with the random deployment method,the new method has improved test coverage.
Key words:WSN;random deployment;firefly algorithm;probabilistic perception model;grid coverage model
1前言
无线传感器网络(Wireless Sensor Network,WSN)[1]是基于微处理、嵌入式及无线通信等技术的一种具有低功耗、低成本、自组织等特点的分布式信息感知、传输和处理系统。它通过网络技术，实时感知、采集、处理和发布网络覆盖区域内检测对象的信息。目前，WSN 被广泛应用于军事[2]、灾害预警[3]、空间探测[4]和环境监测[5]等领域。在应用过程中，WSN 面临的首要问题是节点部署，其直接影响整个网络的覆盖能力。随机部署是最简单的节点部署方式，但该方式易使众多节点聚集，节点无法均匀部署，导致监测区域盲区较多，从而影响整个WSN 监测性能。为了克服随机部署方式存在的缺点，因此，需要设计一种自适应调整的WSN 部署方法。该方法可以根据监测区域的变化，动态地调整传感器的位置，减少区域覆盖盲点，提高WSN 覆盖率。
体智能算法(Swarm Intelligence Algorithm,SIA)是一种仿生优化技术，可用于解决各种具有高维、多模和不可微等特性的复杂问题。典型的算法有粒子算法(Particle Swarm Optimi⁃zation,PSO)[6-7]、蜂算法(Artificial Bee Colony,ABC)[8-9]和萤火虫算法(Firefly Algorithm,FA)[10-12]等。受自然界萤火虫的生物
社交行为影响，杨新社教授[13]于2008年提出萤火虫算法。该算法采用全吸引方式更新萤火虫的位置，即每只萤火虫依次地向其它所有更亮的萤火虫移动，随着种的进化，萤火虫逐渐地聚集于最亮的萤火虫附近，完成寻优任务。
由于FA 概念简单、参数少，具有较强寻优能力，本文将其应用于基于概率感知模型的WSN 节点部署，实现WSN 高覆盖率。仿真实验结果表明，基于萤火虫算法的WSN 节点部署方式具备更佳的监测效果。
2WSN 节点覆盖模型
2.1问题分析
WSN 中的每个节点覆盖范围是以自身为中心，以感知距离为半径的圆内，在覆盖范围内的所有信息均可被节点采集并存储。WSN 中的节点均是以圆面的形式对监测局域进行覆盖，每个节点之间会出现覆盖重叠情况，为计算WSN 总覆盖率带来极大困难。为此，本文借助网格覆盖模型来统计WSN 覆盖率。网格覆盖模型将监测区域进行网格化，即将面积为S 区域划分成M ∗N 的网格，若所有网格点均被监测，则WSN 总覆盖率为100%；若只有部分网格点C 被监测，则WSN 覆盖率为(C /M ∗N )*
收稿日期：2020-10-12
基金项目：江西科技学院自然科学项目（ZR1906）；2020年江西省大学生创新创业训练计划项目(2020
10846001)作者简介：曹娜娜（1998—），女，在读本科，计算机科学与技术专业，研究方向为智能计算；通讯作者：谢智峰（1993—），男，助教，硕
士，研究方向为智能计算；穆莉，女，学士，研究方向为智能计算；王汐存（1997—），女，在读本科，研究方向为智能计算。
5
本栏目责任编辑：唐一东
本期推荐
Computer Knowledge and Technology 电脑知识与技术第17卷第3期(2021年1月)
100%。
2.2模型建立
基于网格覆盖模型，将面积为S 的WSN 监测区域网格化为
具有M ∗N 个网格点的二维区域。在该区域内，网格点即为检测点，检测点集合为p ={p 1,p 2,⋅⋅⋅,p M *N
}，其坐标为p i ={a i ,b i }(i =1,2,⋅⋅⋅M *N )；随机部署感知半径为R s 的Z 个同构传感器，节点
集合为z ={z 1,z 2,⋅⋅⋅,z n }，其坐标为z j ={x j ,y j }(j =1,2,⋅⋅⋅,Z )。基于坐标信息，，根据公式(1)计算任意节点到检测点z j 之间的欧氏距离d ij ：
d ij =
p i -z j =
(a i -x j )*(b i -y j )（1）
WSN 对检测点检测一般有布尔感知模型和概率感知模型。
在布尔感知模型中[14]，当检测点位于传感器节点覆盖圆内时，目标被检测到的概率即为1，反之，目标被检测到的概率即为0；在概率感知模型中[15]，对布尔感知模型进行优化，当检测点位于传感器节点较近或较远时，目标被检测到的概率为1或0，当检测点位于传感器节点某区间段时，目标被检测到的概率则由与距离及传感器可测量参数的关系函数来确定。由于布尔感知模型没有考虑信号强度对目标检测概率的影响，而概率感知模型反映了传感器节点的感知能力与被检测目标到节点间的距离变化规律，更符合实际监测要求，因此选择概率感知模型计算WSN 覆盖率。因此，根据公式（2）计算传感器节点p i 对检测点z j 的感知概率计算C z (p i ,z j )：
C z (p i ,z j )=ìíîïïïï
1,
d ij ≤R s -R
e exp(-λ1αβ
1αβ2+λ2),R s -R e d ij ≤R s +R
e
0,
其它（2）其中，
R e 、λ1、λ2、α1、α2均为与传感器节点测量相关的性能参数，且关系满足：
0<R e <R s 、α1=R e -R s +d ij 、α2=R e +R s -d ij 。
根据公式（2）可以计算WSN 中每个传感器节点对检测点z j
的感知概率，然后根据公式（3）可以计算所有传感器节点对检测点z j 的联合感知概率C all ：
C all =1-∏i =M *N
(C z (p i ,z j ))（3）
其中，当检测点z j 的联合感知概率C all 大于设置的阈值
C threshold 时，则检测点z j 被检测到，即C all 为1，反之，未被监测到，即C all 为0。
基于以上描述，可以根据公式（4）计算具有Z 个同构传感器的WSN 对网格化为M ∗N 的面积为S 的二维监测区域的覆盖率C rate ：
C rate =
∑u =1
M
∑v =1
N
C
all
M *N
（4）
3萤火虫算法
在标准萤火虫中，主要有两个关键参数：光亮强度和吸引
度。光亮强度一般由被优化问题的目标函数值确定，决定萤火虫移动的方向。吸引度与萤火虫之间的距离成反比，决定萤火虫移动的距离。萤火虫不断地向比自身更亮的萤火虫移动，直至达到移动终止条件，萤火虫种停止移动，寻优过程结束。
萤火虫的相对光亮强度由公式（5）决定：
I =I 0e -γr (5)
其中，
r ij 代表萤火虫i 和萤火虫j 之间的欧式距离，I 0代表萤火虫在r ij =0时的光亮强度，
γ是光吸收系数。萤火虫的相对吸引度由公式（6）决定：
β=β0e
-γr
(6)
其中，β0代表萤火虫在r ij =0时的吸引度，是常量。
熊乃瑾个人资料对于任意两只萤火虫，它们之间的欧式距离由公式（7）决定：
r ij =
x i -x j =
∑d =1
D ()
x
id
-x jd 2
(7)
其中，
D 代表求解问题的维度。萤火虫i 向萤火虫j 的更新由公式（8）决定：
x id (t +1)=x id (t )+β0e -γr (x jd (t )-x id (t ))+α(t )ε(8)
其中，
x id 和x jd 分别是萤火虫i 和萤火虫j 在第d 个维度的位置，参数ε是随机函数，服从[-0.5,05]之间的均匀分布，α(t )参数是步长因子，取值范围是[0,1]，
t 代表种迭代次数。4实例应用
4.1WSN 与FA 融合
WSN 与FA 融合关键在于待求解和目标函数的确定。在
WSN 中，其解为传感器的部署方案，即每个节点坐标；其部署方案的优劣由WSN 覆盖率来确定。因此，可将萤火虫的维度定位所有节点坐标集合，即一只萤火虫代表一个部署方案；可将WSN 未覆盖率作为算法的目标函数，如公式（9）：
fitness =1-C rate =1-
∑u =1
M
∑v =1
N
C
all
M *N
（9）
确定待求解和目标函数后，FA 寻优的步骤如下：1）初始化种数量N 、步长因子α、初始吸引度β0、光吸收
系数γ；
2）设定搜索范围，初始化位置，将传感器节点坐标与萤火虫的位置关联；
3）萤火虫根据式(8)更新位置，结合式(9)计算萤火虫的适应值。若FA 达到终止条件，则跳转至步骤5)，否则，重复执行步骤4)；
4）输出最优萤火虫位置信息和适应值。4.2实验分组及参数设置
为了比较随机部署和基于萤火虫算法部署的性能差异，设
计了3组实验，具体信息见表1。传感器其他参数R e =0.5R s 、
λ1为1，λ2为0；FA 种大小N 为40，步长因子α为0.2，初始吸引
度β0为1.0，光吸收系数γ=1/Γ2
（Γ为搜索域的区间值），评估次数MAX _FEs 为1000；WSN 传感器联合感知概率阈值C threshold
为0.8。
表1实验分组及部分参数设置
组别123
监测区域S (m 2)
50x5050x50100x100
网格数M *N （个）
51x5151x51101x101
感知半径R s （m
）5513
节点个数Z （个）
405030
4.3仿真结果
为了消除随机性影响，对两种部署方案分别进行了20次
仿真测试，表2统计了两种部署方案在不同实验分组的平均覆
6
本期推荐
本栏目责任编辑：唐一东Computer Knowledge and Technology 电脑知识与技术
第17卷第3期(2021年1月)
盖率情况。基于萤火虫算法部署的平均覆盖率均高于随机部署，分别高出5.65%，15.73%，8.81%；由组1和2数据可知，在只增加节点个数的情况下，平均覆盖率提高了8.73%，说明增加节点可覆盖率，但与此同时，增加了部署成本；组3在增大监测面积和节点感知半径的同时，减少了节点个数，平均覆盖率最高，说明节点感知半径是影响覆盖率的重要因素之一。
表2随机部署和基于萤火虫算法部署的覆盖率对比
组别
123
随机部署Random deployment
58.52%57.17%73.39%
基于萤火虫算法部署Deployment based on firefly algorithm
64.17%72.90%82.20%
为了更加直观的比较两种部署方法对监测区域的部署情
况，图1展示了传感器节点位置分布情况。由组别1节点分布图可知，基于萤火虫算法部署节点分布图更均匀，未被覆盖区域较少；由组别2节点分布图可知，随机部署节点分布图未被覆盖区域较多；由组别3节点分布图可知，基于萤火虫算法部署节点分布图重叠区域相对较少；总体而言，基于萤火虫算法部署节点分布图覆盖面更广，节点感知重叠现象较少。
(a)组别1：随机部署(b)组别1：萤火虫算法部署
(c)组别2：随机部署(d)组别2：萤火虫算法部署
(e)组别3：随机部署(f)组别3：萤火虫算法部署
图1随机部署和基于萤火虫算法部署的节点分布图
5结论
萤火虫算法相较于随机部署方法，更有助于WSN 覆盖率
的提高，说明该算法具备一定的优化性能。观察表2可知，WSN 覆盖率有很大的提升空间。因此，下一步的研究重点工作是对萤火虫算法优化性能进行深入研究，通过对算法性能的优化，提高WSN 覆盖率。
参考文献：
[1]刘建英，张仲良.水环境监测方法标准技术体系探讨[J].科技与创新,2017(7):54-54.
[2]李志刚，屈玉贵，蔺智挺，等.基于无线传感器网络的战场目标跟踪[J].传感器与微系统,2007,26(7):11
8-120.
[3]夏梁斌.基于无线传感网络的公路边坡监测及临滑预警研究[J].公路与汽运,2017(1):125-128.
[4]龙吟，陈淞，齐鑫，等.应用无线传感器网络的月表环境长期无人监测系统构想[J].航天器工程,2017,26(3):9-16.
[5]胡坚，胡峰俊，张红，等.基于改进布谷鸟搜索算法对水质监测无线传感器部署的优化[J].浙江农业学报,2020,32(5):897-903.
[6]ZHAO J,LV L,WANG H,SUN H,et al.Particle Swarm Opti⁃mization based on Vector Gaussian Learning[J].KSII Transac⁃tionson Internet and Information Systems,2017,11(4):2038-2057.
[7]SUN H,SHI X L,ZHAO J,et al.Hybrid algorithm of particle swarm optimization and artificial bee colony with its applica⁃tion in wireless sensor networks[J].Sensor Letters,2014,12(2):392-397.
[8]孙辉，谢海华，赵嘉，等.加权中心人工蜂算法[J].控制与决策,2019,34(10):2115-2124.
[9]GAO W F,HUANG L L,WANG J,et al.Enhanced artificial bee colony algorithm through differ-renttial evolution[J].Ap⁃plied Soft Computing,2016,48:137-150.
[10]YU S H,SU S B,LU Q P,et al.A novel wise step strategy for firefly algorithm[J].International Journal of Computer Math⁃ematics,2014,91(12):2507-2513.
[11]FISTER J I,YANG X S,FISTER I,et al,Fister Iztok,Brest Janez.Memetic firefly algorithm for combinatorial optimiza⁃tion:Proceedings of International Conference on Bioinspired Optimization Methods and their Application[C].Piscataway:IEEEPress,2012,76-86．
[12]WANG H,WANG W J,SUN H,et al.Firefly algorithm with random attraction[J].International Journal of Bio-Inspired Com⁃putation,2016,8(1):33–41.
[13]YANG X S.Nature-Inspired Metaheuristic Algorithms[M].Luniver Press,2008.
[14]何欣，桂小林，安健.面向目标覆盖的无线传感器网络确定性部署方法[J].西安交通大学学报,2010,44(6):6-9.
[15]张云洲，吴成东，程龙，等.确定性空间的无线传感器网络节点部署策略研究[J].控制与决策,2010,25(11):1625-1629.
【通联编辑：梁书】
7
发布评论