基于改进粒子群的无线传感器网络覆盖优化算法

林威建　郝泳涛

摘要：针对基于移动节点的无线传感器网络覆盖优化问题。该文根据传感器以及感知区域的特性建立了不规则的感知模型，并以覆盖率最大、节点移动距离最小为目标建立了无线传感器网络覆盖优化模型。同时结合虚拟力算法，设计并实现了基于虚拟力的动态调整线性加速因子的粒子群算法，弥补虚拟力算法在局部搜索方面的不足。

关键词： 无线传感器网络；覆盖优化；粒子群算法；虚拟力算法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）28-0036-04

Research on Coverage Optimization Algorithm of Wireless Sensor Network Based on Particle Swarm Optimization

LIN Wei-jian，HAO Yon-tao

（CAD Resaerch Center of Tongji University， Shanghai 201804， China）

Abstract：The main research of works in the paper is the coverage optimization problem of wireless sensor network based on the mobile node. Firstly， establish irregular sense model according to the characteristics of sensors and sensing region， and establish a wireless sensor network coverage optimization model based on and maximum coverage with minimum node moving distance. Combined the particle swarm optimization （PSO） with the virtual force algorithm， we proposed particle swarm algorithm based on changing acceleration factor particle swarm optimization based on virtual force（VFCAPSO）. Comparison and analysis the results of the algorithm， we found the algorithm changing acceleration factor particle swarm optimization based on virtual force （VFCAPSO） is best.

Key words：WSN； coverage control； particle swarm optimization； virtual force

无线传感器网络（wireless sensor network，WSN）是由一组小功率受限且具备传感和通信功能的节点组成。在无线传感器网络的各种应用中，网络覆盖是一个重要的衡量标准，它决定了传感器网络对覆盖区域的监测效果。合理的节点部署策略，不仅能够提高对目标区域的覆盖效果，也能有效利用传感器网络的资源，提高能量利用率，延长网络寿命。

在实际的应用过程中，可以通过部署可移动的节点来应对地形环境、部署方式等限制。当检测到网络未达到预定的覆盖效果时，计算一个新的位置并将节点移动到该位置，弥补覆盖漏洞从而提高覆盖率。同时，考虑到传感器节点一旦部署，往往很难获得可靠连续的能量供应，如何通过优化部署策略，减少移动过程中的能量消耗也是重要的一个方面。本文针对包含移动节点的无线传感器网络，设计一种优化的部署策略，使得无线传感器网络在多种因素的制约之下，能够合理的部署无线传感器节点的位置。这对于优化资源分配，最大限度的覆盖目标区域，保障网络正常高效工作，延长网络的使用寿命具有非常重要的意义。

1 研究现状

国内外许多学者相继提出了针对移动传感器网络的覆盖优化问题算法：Howard， Zhou等人首度将势场理论应用于传感器网络的覆盖控制，通过假设虚拟势场和虚拟受力，利用物理学定律指导网络的布局优化过程[1]。在传感器经过最初的随机放置之后，使用虚拟力算法（VFA）作为传感器部署策略，可以以提高覆盖面。文献[2]提出了一种用于无线传感网络布局优化的粒子群优化策略。该策略采用概率测量模型评价网络测量性能，以网络有效覆盖率为优化目标，通过粒子群算法搜索全局最优布局方法。文献[3]将粒子群算法和混沌算法相结合，求解以移动传感节点位置为输入参数网络覆盖面积为目标的无线传感器网络覆盖优化问题。文献[4]提出了一种基于遗传算法的移动无线传感器网络中节点再部署方法，利用多目标优化对网络的覆盖率和节点的移动距离进行优化，从而延长了网络的生命周期。

2 无线传感器网络模型

2.1无线传感器网络节点感知模型

常用的节点感知模型包括以下三种：二元感知模型、概率感知模型[5]和不规则感知模型 [6]。针对基于移动节点的传感器网络优化部署，为了更加贴近无线传感器网络的实际工作情况，本文采用文献[6]提出的不规则感知模型，采用如下定义计算传感器节点的感测概率：

[Ss，p=0，dsi，p>Rpe-ξds，p-Rc，Rc≤dsi，p≤Rp1，dsi，p

式中[ξ]表示衰减因子，视具体的部署场景以及传感器功率和类型而定。[Rc]表示可信半径，在此半径内能够100%地监测到物理事件。[ai]为节点在第[i]方向上可变半径系数。[Rp]表示最大半径，大于[Rp]则无法感测到物理事件。[dsi，p]表示[Si]和[P]之间的欧几里得距离，即传感器[Si]部署在点[xi，yi]上，[x，y]中的任意点[P]，[dSi，P=xi-x2+yi-y2]。

不规则感知模型在某些特殊情况下可以转换为二元感知模型和概率感知模型。当[Ri=Rp]时，不规则感知模型退化成了二元感知模型，检测半径[x=Ri=Rp]。而当设置所有感测方向上的不规则感知半径为理论最大感测半径，即上述[ai=1，i=1，2，3…n]时，不规则感知模型退化成了简单的概率感知模型。

2.2无线传感器网络覆盖优化模型

2.2.1度量标准

1） 覆盖率度量

覆盖率定义为受到检测的区域大小与整个目标区域大小的比值。关于覆盖率的计算，我们通过网格来实现：将受检测区域划分为大小相等的网格，计算每个网格点受到检测的概率，统计检测概率大于某一值的网格数量进而计算出目标区域的覆盖率。

对于某个网格，我们将它被整个监测区域中的所有传感器节点检测到得概率定义为联合检测概率[13，15]，网格P的联合检测概率如下公式所示：

[CpSall，p=1-i=n1-CpSi，p]

式中[Sall]表示测量目标点的传感器节点集合，[CpSi，p]为传感器[Si]对目标点[p]的感知概率。

令[Cth]为目标点能够被检测到的概率阈值，则目标点能被有效检测到的条件为：

[minxpypCpSall，p≥Cth]

若网格点i被覆盖，则令标志位[Cov_flagi=1]，否则[Cov_flagi=0]。则算法覆盖率定义如下：

[Cov=i=1NGCov_flagi/NG]

NG 为在感兴趣区域划分的网格总数[7]。

2）节点移动距离度量

在移动过程中需要考虑目标区域中所有节点的移动总能耗。假设节点变换位置时都按照直线方式移动，而移动能耗与移动距离成正比，因此该问题转化成了节点的移动距离之和。可以将度量标准表示如下[3]：

[Dis=i=1kdi]

其中[di]表示传感器节点[Si]从初始部署位置移动到最终位置的距离。

2.2.2优化目标函数

本文提出的综合考虑覆盖率和移动距离的目标函数如下：

[E=maxf1?Cov+f2?1DisNL+1]

其中，Cov表示覆盖率计算公式，Dis表示传感器节点移距离，N表示目标区域部署的传感器节点数量，L 表示目标区域为L*L的矩形区域的边长，F1表示覆盖率优化目标所占的权重，F2表示移动距离优化目标所占的权重。

实验证明，该公式能够适应覆盖范围以及节点数目的变化，在目标范围变化后不需要调整权重就能达到预先设置的优化目标。

3 粒子群算法解决无线传感器网络覆盖优化问题

3.1粒子群算法介绍

粒子群算法（particle swarm optimization， PSO）是由Kennedy和 Eberhart于1995 年提出的一种优化算法[8，9]。PSO算法中每个粒子代表了解空间中的一个解，粒子依据同伴及自己的搜索经验来动态调整自己的搜索位置和速度。

在一个规模为N的粒子群中，粒子i（i=1，2，…，N）将根据下面的公式来更新自己的速度和位置[10]：

[Vi=ω*Vi+c1*rand（）*（pBest[i]-Xi）+c2*Rand（）*（pBest[g]-Xi），Xi=Xi+Vi，]

式中[xi]表示第[ii=1，2，3…N]个粒子的当前位置，[Vi]表示第[ii=1，2，3…N]个粒子的当前速度，pBest[i]表示粒子i所经历过的历史最优位置，pBest[g]表示网络中所有粒子经历过的最优位置，rand（）、Rand（）表示[0，1]上的随机数，[ω]表示惯性权重（inertia weight），取值为0.8，c1、c2是个两个常数，称为学习因子。本文设置c1=c2=1，使得粒子具有相同的全局和局部搜索能力。

3.2粒子编码

在实际应用当中，粒子的编码分为两部分，一部分是粒子的位置，一部分是粒子的速度。假设传感器网络中有N个节点，每个节点都有X、Y两个位置坐标，网络对目标区域的覆盖率作为决策变量，也就是说传感器节点最优部署位置的维数空间为2N，所以将粒子编码设计成一个大小为2N的向量。向量中的每一个分量表示某个传感器节点的X或Y方向的位置。

单个粒子位置的编码设计为：

[X=X1，Y1，X2，Y2……Xn，Yn]

那么单个粒子在空间中的飞行速度编码的设计为：

[V=VX1，VY1，VX2，VY2，……VXn，VYn]

整个粒子群中所有粒子采用相同的位置和速度编码，并且每个粒子的位置和速度向量单独计算。

3.3适应度函数

以覆盖率最大并且节点移动距离最小为目标函数的优化方案，其适应度函数为：

[fitness=f1?Cov+f2?1DisNL+1]

3.4算法流程

第一步 初始化各个参数

根据配置初始化算法参数、模型参数以及传感器节点属性。

第二步 初始化粒子群

初始化粒子群的方法：目标区域的范围[posMin，posMax]内，选取2N随机数构成N个传感器节点的初始位置（x，y），并以这个初始位置构成的向量初始化整个粒子群中所有粒子的位置向量。粒子群中所有粒子的位置向量均为[X=X1，Y1，X2，Y2……Xn，Yn]。对于粒子的速度来说，粒子速度的初始化值均为0。粒子群中所有粒子的速度向量均为[V=VX1，VY1，VX2，VY2，……VXn，VYn]。

第三步 根据粒子适应度函数计算各粒子的适应度值

使用上文提到的适应度计算方法计算某个粒子的适应度函数值。

第四步 迭代更新粒子的速度和位置

当算法运行到第n次迭代时，比较所有粒子搜索到的历史最优位置pBest[i]，i=1，2，…N，并取最好位置来更新全局最优位置gBest。在第k+1次迭代，所有粒子的位置和速度按照位置更新方程和速度更新方程进行更新。在更新的过程中，粒子在每一维上的飞行速度的上下限为Vmax和Vmin；粒子在每一维上的位置的上下限位posMax和posMin。

第五步 循环迭代，判断是否满足终止条件

满足终止条件时，停止迭代，输出全局最优位置；否则，循环迭代，转入第三步。一般设置最大迭代次数作为算法的终止条件。

4 改进的粒子群算法解决无线传感器网络覆盖优化问题

文献[11]通过类比的手法，引入物理学中的库伦力和万有引力的模型，提出了一种基于虚拟力的覆盖优化方法。但是此算法并不适合于网格模型：当网格面积过小且数量很多，即感知精度较高的时候，往往会使得某块未覆盖的区域内包含过多的小网格，每个网格都对附近的节点产生引力，从而使得传感器节点收到的引力过大导致过快的运动，错过了需要覆盖的区域。

本文针对不规则感知模型的复杂性，在上述虚拟力算法的基础上进行了改进，避免了因网格面积过小而网格数量过大产生的引力叠加问题，并成功与粒子群算法相结合，提出了一种基于虚拟力的粒子群算法来求解无线传感器网络覆盖优化问题。

4.1改进虚拟力模型

首先，目标区域被分成许多个面积相等的小网格，将目标区域的覆盖转化为对小网格的覆盖，未覆盖的小网格对附近的传感器节点具有吸引力，使算法能够将节点移到未覆盖的区域，增加覆盖率。将未覆盖点对传感器的吸引力定义为：

[Fik=riskdik2，ri

其中，[Fik]为第K个未覆盖的网格对传感器节点i产生的引力，[dik]为两者之间的距离，[ri]定义为传感器节点的可靠感知半径，[Ri]为传感器节点的通信半径，而[Sk]为第K个未覆盖的网格的面积。

为避免多个传感器节点的覆盖区域产生重合，定义了两个节点之间具有斥力。将两个传感器节点之间的虚拟力定义为：

[Fij=rirjdij2，dij

其中[dij]为传感器节点之间的距离，[Ri，Rj]为两个传感器的通信半径，[ri，rj]为两个传感器的感知半径，两个传感器收到大小相等方向相反的作用力与反作用力。

4.2结合粒子群算法

粒子编码同标准粒子群算法一致，唯一不同的是为每个传感器增加了虚拟力。通过将粒子群算法中单个粒子的速度和位置更新公式改进如下，使得粒子群算法和虚拟力算法相结合：

[Vi=ω*Vi+c1*rand（）*（pBest[i]-Xi）+c2*Rand（）*（pBest[g]-Xi）+c3*Fi，Xi=Xi+Vi，]

速度更新公式的前半段和标准粒子群一样，主要不同是增加了虚拟力部分c3*Fi，可以理解为使用粒子受力产生的加速度来更新粒子的运动速度。其中c3为虚拟力加速因子，与c1、c2的值比较接近，c3过大很有可能导致粒子受力过大飞过未覆盖点，Fi为节点i受到的X或Y方向上的合力，Vi为该粒子的第i维速度。本文中c3取值为0.4。

由于虚拟力对粒子更新位置有积极的指导作用，所以算法收敛速度较快，但是在算法后期由于虚拟力的存在，粒子在进行局部搜索的时候会被虚拟力阻碍，往往无法搜索到更优的解。因此本文对上述虚拟力加速因子c3进行动态调整，在算法初期保持c3具有较大的一个值，并随着迭代次数的增加，c3逐渐减小。其更新公式为：

[c3=c3begin+g×c3end-c3begingmax]

c3在开始的时候取值为0.5，在结束的时候取值为0.2。在算法前期主要发挥虚拟力算法的优势，使得算法尽快地进行收敛，粒子单独搜索整个解空间，在算法后期减小虚拟力的影响，发挥粒子群算法的优势，重点对全局最优解附近的解空间进行精确搜索，找到更优解。

仿真结果显示，结合虚拟力的动态线性调整惯性权值和加速因子的粒子群算法（VFCAPSO）迭代速度以及最大覆盖率均优于标准粒子群算法，取得了比较好的效果。

5 算法仿真和测试

本节使用的不规则感知模型参数设置如下：

传感器节点可靠感知半径为18，最大可感区域为30，通信半径为40，节点一共有180个方向，每个方向上在可靠感知半径和最大可感区域内被分成10块区段，衰减因子为0.05。

相关设置以及节点的效果图具体如图1所示：

算法的运行结果如图3，分别为适应度每代最大，以及每代适应度最大所对应的节点移动距离，每代适应度最大所对应的覆盖率。

6 结束语

本文采用了文献[6]中提出的不规则感知模型，并建立了综合考虑覆盖率和移动距离为目标的数学模型，验证了以覆盖率和移动距离为目标的数学模型能够在保证覆盖率的前提下有效减少节点的移动距离。将粒子群算法应用到无线传感器网络覆盖优化问题中去，并对已有的算法进行了改进，成功地将自适应调整惯性因子的粒子群算法（APSO）、混沌粒子群算法（CPSO）、线性调整加速因子的粒子群算法（CAPSO）应用到无线传感器网络覆盖优化中去，并结合虚拟力算法提出了基于虚拟力的动态调整线性加速因子的粒子群算法（VFCAPSO）、基于虚拟力的粒子群算法（VFPSO）和基于虚拟力的遗传算法（VFGA）算法，经过仿真实验验证了新算法的有效性。通过比较分析，有效的验证了虚拟力算法对算法性能的提升，同时验证了本文提出的三种结合虚拟力算法中VFCAPSO性能最好，同时适用于覆盖率最大为目标和综合考虑覆盖率和移动距离为目标的优化模型。

参考文献：

[1] Zou Y， Chakrabarty K. Sensor deployment and target localization based on virtual forces[J].IEEE societies，2003，2（1）：293-303.

[2] 林祝亮，冯远静.基于粒子群算法的无线传感网络覆盖优化策略[J].计算机仿真，2009，26（4）：190-193.

[3] 刘维亭，范洲远.基于混沌粒子群算法的无线传感器网络覆盖优化[J].计算机应用，2011，31（2）：338-340.

[4] 南国芳，陈忠楠.基于进化优化的移动感知节点部署算法[J].电子学报，2012，40（5）：1017-1022.

[5] 刘维亭，范洲远.基于混沌粒子群算法的无线传感器网络覆盖优化[J].计算机应用，2011，31（2）：338-340.

[6] 赵小敏，毛科技，何文秀，等.感测范围不规则情况下无线传感器网络节点部署算法[J].软件学报，2012，23（1）：59-68.

[7] 王伟，林锋，周激流.无线传感器网络覆盖问题的研究进展[J].计算机应用研究，2010，27（1）：32-35.

[8] Shi Y， Eberhart R. A modified particle swarm optimizer[C]. In： IEEE World Congress on Computational Intelligence，1998：69-73.

[9] 冯翔，陈国龙，郭文忠.粒子群优化算法中加速因子的设置与试验分析[J].集美大学学报：自然科学版，2006，11（2）：146-150.

[10] SEAPAHN MEGERIAN， FARINAZ KOUSHANFAR， GANG QU， GIACOMINO VELTRI， MIODRAG POTKONJAK. Exposure in Wireless Sensor Networks： Theory and Practical Solutions[J].Wireless Networks，2002（8）：443-454.

[11] 田一鸣，陆阳，魏臻，吴其林.无线传感器网络虚拟力覆盖控制及节能优化研究[J].电子测量与仪器学报，2009，23（11）：65-71.