WSN中基于改进粒子群算法的覆盖漏洞检测

宋 娜 冯梦清

(郑州工业应用技术学院信息工程学院 河南 郑州 451150)

0 引 言

目前，无线传感器网络(Wireless Sensor Network,WSN)使用越来越广泛，如环境检测、智能家居和现代农业等，这些场合需要无线传感器网络覆盖的完整性[1-2]。但是传感器在初始化阶段往往随机布放在所监控区域中、节点能量消耗不均匀，最终漏洞出现使得覆盖范围有限，导致整个网络失效。当前对于无线传感器网络覆盖漏洞检测方法主要有：① 跳数算法(Hop Algorithm,HA)，主要是通过节点到邻居的通信链路是否连通来判断漏洞边界节点，对跳数较大的节点效果比较好[3]，但是由于跳数需要遍历性，所以时间开销较大；② 邻域拓扑算法(Neighborhood Topological Algorithm, NTA)是指如果某个节点的密度低于所有邻居节点密度的平均值，则表示该节点为覆盖漏洞边界节点[4]，但是这种方法对于密集型网络的效果并不理想，会出现误判现象；③ 几何分布式算法(Geometry Distributed Algorithm,GDA)，该算法首先需要计算传感器节点及其相邻两节点形成的三角形的外接圆的半径和圆心，然后根据计算几何理论判断节点是否为覆盖漏洞的边界节点[5]；④ Voronoi图算法(Voronoi Graph Algorithms,VGA)是指若节点的监测范围与当前节点到Voronoi图顶点的长度小于设置的阈值，判断当前节点在覆盖漏洞边界上[6]；⑤ 循环分布式算法(Circular Distributed Algorithms,CDA)主要是根据循环覆盖和相邻节点的信息构建关系表，然后通过查询此表来检测覆盖漏洞的位置[7]；⑥ 粒子群算法(Particle Swarm Optimization,PSO)，该算法在进行无线传感器网络覆盖漏洞检测时，由于后期处理容易陷入局部最优，无法获得真正的覆盖漏洞边界[8]。上述算法在检测覆盖漏洞的位置信息时，对覆盖漏洞的面积仅仅通过近似三角形进行计算，这导致了计算精度比较低的问题。为此，本文给出一种无线传感器网络基于改进粒子群算法的覆盖漏洞检测方法(后文简称为IPSO)，该方法对覆盖区域进行单元格划分，通过比较单元格的坐标位置和放置在该单元中的每个传感器节点位置来分析是否有覆盖漏洞以及覆盖漏洞边界，改进粒子群主要进行粒子的适应度函数值与自身当前最佳值比较，以便获得最优检测效果，最后对覆盖漏洞检测相关内容进行仿真，验证了所给方案的合理性。

1 无线传感器网络覆盖漏洞判定

1.1 覆盖漏洞检测

无线传感器网络监测区域中若有未被任何传感器节点所覆盖的范围，则该范围称为覆盖漏洞。覆盖漏洞检测需要对覆盖区域划分成若干个单元格，对每个单元格进行相同的统计操作，每个单元格中包含若干传感器节点，如图1所示采取了4个单元格。

图1 单元格

对于每4个单元格共用顶点采用Delaunay三角剖分法，由于Delaunay三角形的外接圆内不包含其他节点[9]，每一个Delaunay三角形的外接圆被称为其对应的空外接圆，三角形顶点分别选择离共用顶点较近的三个传感器节点，这样构成的Delaunay三角形边长分别为a、b和c，此三角形的空外接圆半径rc计算式表示为：

(1)

当形成的一个三角形的空外接圆半径rc大于传感器节点的感知半径r，该三角形空外接圆圆心Oc到该三角形的三个顶点的距离大于r，此时该三角形空外接圆圆心Oc都没有被三个传感器节点所覆盖，则说明无线传感器网络可能产生覆盖漏洞。

1.2 覆盖漏洞位置

利用无线传感器网络每个节点都能够收、发信息特性，这样每个节点都能获得周围邻居节点的位置信息，利用位置信息构建Delaunay三角外接圆圆心位置，圆心坐标(x,y)表示为：

(2)

式中：x和y为外接圆圆心的坐标，xi和yi为构成该传感器网络中三个节点的位置坐标，i=1,2,3。当外接圆圆心到Delaunay三角形任何一个节点的距离大于传感器的感知半径时，即得出覆盖漏洞的中心位置在(x,y)处。

1.3 覆盖漏洞面积计算

覆盖漏洞检测方案通过选择最近的传感器节点到单元格顶点的坐标来计算漏洞面积，选择策略是通过比较单元格的坐标位置和放置在该单元中的每个传感器节点位置完成。在选择所需的传感器节点数后，覆盖漏洞检测算法选择最近的传感器节点作为单元格的头节点。头节点有两个功能：从其他节点收集数据，并根据选定的路由协议对其进行分类；使用三角测量法计算漏洞面积[10-11]。

覆盖漏洞检测方案是通过比较选择的传感器节点与每个单元边缘位置点的最大传输范围，如果所选传感器节点的传输范围在单元格的边缘内，则没有覆盖漏洞；反之，如果在单元格的边缘之外，则肯定存在覆盖漏洞。如图2所示。

(a) 大区域覆盖漏洞

(b) 小区域覆盖漏洞图2 单元格中的覆盖漏洞

在选择的传感器节点和单元格边缘之间通过应用三角形方法测量来计算漏洞面积，将传感器节点连接到最近的单元边缘直线坐标上，然后我们得到若干个三角形，如图3所示。在图3(a)大区域漏洞划分4个三角形，图3(b)小区域漏洞划3个三角形，也可能存在漏洞区域划分2个三角形和1个三角形。

(a) 大区域覆盖漏洞划分4个三角形

(b) 小区域覆盖漏洞划分3个三角形图3 覆盖漏洞划分为多个三角形

根据三角测量理论，计算出划分成多个小三角形的面积之和即可获得漏洞面积，例如对图3(a)大区域漏洞划分4个三角形及其中某个三角形标注如图4所示。

(a) 划分多个三角形标注

(b) 三角形以及弓形标注图4 划分为三角形

依据海伦公式，计算图4(b)三个点(X0,Y0)、(Xa,Ya)和(Xb,Yb)所围成三角形的面积S0计算式表示为：

(3)

式中：r是传感器感知半径；Z是三角形半周长。但是按三角形计算，将减少或者增加覆盖漏洞面积，因此需要计算传感器感知半径与边L3所对弧长包围的弓形面积S1，其计算式表示为：

(4)

最终获得边L1、L2与覆盖漏洞区域所围成的面积Sholes表示为：

Sholes=S0-S1

(5)

因此通过增加弓形面积的计算，可以精确获得覆盖漏洞区域的面积。在单元格中到某个顶点的覆盖漏洞面积可以通过求所划分单个三角形以及弓形的面积之差获得；重复计算单元格的覆盖漏洞到同一单元的四个边缘，即可获得整个单元格中的任何覆盖漏洞区域面积Sall。

2 方向感知粒子群算法

2.1 基本粒子群算法

基本粒子群算法[12]在搜索空间中更新速度和位置公式表示为：

(6)

式中：r1∈(0,1)和r2∈(0,1)为相互独立的随机函数；vi,j(t)为第i个粒子在第t次迭代的第j维速度；xi,j(t)为第i个粒子在第t次迭代的第j维位置；t为迭代次数；pi,j为当前最佳解；gg,j为历史最佳解；ω为权重；c1和c2分别为调节pi,j和gg,j的加速参数。

2.2 对比策略

在基本粒子群算法中，任何粒子都使用自身认知项c1r1[pi,j-xi,j(t)]和群体认知项c2r2[gg,j-xi,j(t)]来移动，当粒子的适应度值提高时[13]，跟踪具有导向性的粒子更新pi,j。基本粒子群算法存在两个缺点：① 如果具有导向的粒子陷入当前最优状态，则粒子的往复运动完全浪费，增加处理时间；② 粒子趋于过早收敛。

在对比策略中，主要进行粒子的适应度函数值Fi(t)与自身当前最佳值pi比较：粒子i当前处于个体自身当前最佳值pi，若Fi(t)≥pi，则粒子处于极好状态，飞行速度vnew极小范围内更新即可；若Fi(t)≤Fi(t-1)且Fi(t)≥pi，粒子处于较好状态，飞行速度vnew更新较小范围即可；若Fi(t)≥Fi(t-1)，粒子处于收缩状态，飞行速度vnew需要较大范围更新。下面给出不同情况下的不同更新策略，其中rand是(0,1)中的随机数。

(1) 当Fi(t)≥pi时，则更新策略表示为：

(7)

(2) 当Fi(t)≤Fi(t-1)且Fi(t)≥pi时，则更新策略表示为：

(8)

(3) 当Fi(t)≥Fi(t-1)时，则更新策略表示为：

(9)

2.3 粒子群适应度函数

覆盖漏洞面积检测率是覆盖区域中漏洞的面积与覆盖总面积Sall的比值，是评价无线传感器网络覆盖漏洞检测的重要指标[14-15]。所给方案将覆区域分解为L×H个单元格，按照式(3)、式(4)和式(5)计算每个单元格的覆盖漏洞面积SL×H，获得覆盖漏洞面积检测率η为：

(10)

所给方案把η转化为求解Fi(t)最大值问题，在粒子群在迭代过程中，当η越小时，网络存在的覆盖漏洞越小，此时Fi(t)越大：

Fi(t)=1-ηi(t)

(11)

IPSO的主要步骤如下所示：

第1步：粒子群参数初始化；

第2步：无线传感器网络随机化，覆盖区域划分若干单元格；

第3步：粒子群按照式(6)、式(7)、式(8)和式(9)更新位置以及速度；

第4步：达到最大迭代次数，或η≤3%，则进行第5步，否则转第3步；

第5步：输出检测结果。

3 实验仿真分析

利用MATLAB 7.0软件进行仿真，传感器节点数量为150个，部署矩形区域为200 m×200 m，每个节点的通信半径为20 m，感知半径为10 m，在部署区域中随机设置19个大小不同的覆盖漏洞，所有覆盖漏洞的面积之和占部署区域总面积的3%。其中，粒子群参数为：c1=c2=1.4，ω=0.9-(tmax-t)/(0.5×tmax)，最大迭代次数为tmax=200，粒子总数量为300个。

3.1 单元格与漏洞个数、面积关系

在固定的监测区域内，划分单元格边长L和H的大小不同，其覆盖漏洞个数和面积也呈现出一定的变化规律。L和H设置分别为：①L=2 m，H=2 m；②L=7 m，H=7 m；③L=10 mm，H=10 m；④L=13 m，H=13 m；⑤L=15 m，H=15 m；⑥L=20 m，H=20 m。通过50次蒙特卡罗随机部署节点仿真实验，检测得到的覆盖漏洞个数和面积结果如图5所示。

(a) 单元格与检测漏洞个数关系

(b) 单元格与漏洞面积检测率η关系图5 单元格与检测漏洞个数、面积关系

由图5(a)可以看出，随着划分单元格边长为L和H逐渐变大，检测漏洞个数在增加，边长越靠近感知半径时，检测漏洞个数逐渐趋于真实值；由图5(b)可以看出，随着划分单元格边长为L和H逐渐变大接近感知半径，漏洞面积检测率η在减少，边长越离感知半径越大时，则检测η越偏离实际值。单元格边长越接近感知半径时，则越有利于漏洞个数、面积检测。

3.2 粒子数量、迭代次数与漏洞数量检测比

在单元格边长为L=H=10 m条件下，漏洞数量分别设置为4、6、8、10和12个，则粒子数量、迭代次数与漏洞数量检测比如图6所示。

(a) 粒子数量与漏洞数量检测比

(b) 粒子迭代次数与漏洞数量检测比图6 粒子数量、迭代次数与漏洞数量检测比

由图6(a)可以看出，随着粒子数量的增加，漏洞数量检测比在逐渐提高，在相同粒子数量条件下，漏洞数量越多，则检测比越差，在漏洞数量为4个时、粒子180个时，检测比即可达到100%，在漏洞数量为12个时，需要粒子260个时，检测比才能达到100%；由图6(b)可以看出，在漏洞数量为4个时，粒子迭代次数为95次左右时，检测比即可达到100%，在漏洞数量为12个时，粒子迭代次数为190次左右时，检测比才能达到100%。这是因为当粒子群的数量增加时，越有利于发现无线传感器网络中的漏洞，同时漏洞数量越多，则需要迭代次数也随之增加。

3.3 检测指标对比分析

检测指标分析主要包括漏洞面积检测率和处理时间，用于对比分析的相关算法主要有HA、NTA、GDA、VGA、CDA、PSO和IPSO，每种算法各进行40次蒙特卡罗仿真实验，结果如图7所示。

(a) 漏洞面积检测率

(b) 处理时间图7 检测指标对比分析

可以看出，IPSO对覆盖漏洞面积检测、处理时间相比其他算法具有优势，这主要是由于IPSO考虑了单元格中弓形面积对覆盖漏洞面积的影响，使得覆盖漏洞面积检测率更加符合真实值，粒子群在进行粒子的适应度函数值与自身当前最佳值比较过程中，采取不同的更新策略，防止了粒子寻优的盲目性。下面通过分析漏洞检测率与检测时间的关系来验证所给方案更新策略的有效性，如图8所示。可以看出，IPSO所需的监测时间最少，而且随着漏洞检测率的提高，IPSO的检测时间增加也最少，这主要是由于IPSO采用新的更新策略，通过比较粒子的适应度函数值和自身当前最佳值，及时调整粒子的飞行速度和位置，能够更快速地检测出漏洞。由此说明，IPSO的更新策略是有效的。

图8 IPSO更新策略的有效性分析

4 结 语

为提高无线传感器网络覆盖漏洞的监测效果，采用改进粒子群算法对无线传感器网络漏洞检测。所给方案首先对覆盖区域划分不同单元格，单元格顶点划分成多个小三角形的面积与弓形的面积之差获得漏洞面积，然后利用改进粒子群算法进行粒子的适应度函数值与自身当前最佳值比较，获得不同的更新速度与位置。实验仿真得出单元格边长越接近感知半径越有利于漏洞个数、面积检测。而且相比于其他算法，所给方案在漏洞面积检测上处理时间也具有优势。