基于二进制入侵杂草算法的无线传感网络覆盖研究

解放军61112部队，黑龙江牡丹江 157011

一、引言

在许多目标覆盖的应用中，比如导航、目标定位等，每个被监测目标通常需要被多个无线传感器节点所覆盖。由于传感器感知范围、通信能力和数据处理能力的限制，通常每个传感器节点所能感知的目标数量是有限的。在无线传感器网络目标覆盖中，如何在监测能力和传感器节点数量有限的前提下提高监测区域的目标覆盖率，是影响网络性能的重要因素，进而也会影响网络的生命周期。在无线传感器网络中，使用较少的节点工作可以减少通信跳数，降低数据冗余和通信干扰，降低能耗，从而提高网络的生命周期。可以考虑采用节点轮值的方法优化无线传感器网络的目标覆盖。采用节点轮值方法时，选择合适的节点工作和休眠是一个关键问题。

入侵杂草算法（Invasive Weed Optimization，IWO）是C. Lucas和A. R. Mehrabian在2006年通过模拟自然界中杂草扩散入侵过程的随机搜索仿生优化算法[1]。该算法是一种很强大的智能优化算法，具有易于理解、收敛性好、鲁棒性强、易于实现、结构简单等优点，目前，IWO算法已成功应用于DNA序列计算[1]、线性天线设计、电力线通信系统资源分配、图像识别、图像聚类、约束工程设计、压电激励器放置等。

IWO算法主要解决连续空间的浮点数问题，在离散空间中无法直接运用。然而在实际应用中，有许多问题，比如生物科学及计算机科学中的组合问题、背包问题等，只能在离散空间中才能解决。

为了在离散空间应用入侵杂草算法，将其进行改进，提出了一个二进制的入侵杂草算法，即BIWO（Binary Invasive Weed Optimization algorithm，BIWO）算法。本文用改进的二进制入侵杂草算法解决无线传感器网络的覆盖问题，采用了自适应标准差，能保证较快地收敛于全局最优解，能够选择合适节点进行休眠及激活，能够提高网络的覆盖率，延长网络的生命周期。

二、入侵杂草算法

1、入侵杂草算法的基本步骤

入侵杂草算法的实现通常也需要四个步骤，包括初始化杂草种群、繁殖、空间扩散分布、竞争性排斥规则[2]。

（1）初始化种群

设置入侵杂草算法的相关参数，设定最大种群规模Pmax，初始化种群数N0，所求问题维数d，最大迭代次数itermax，繁殖的种子数的上下限Smax和Smin，非线性调和因子n。

（2）繁殖

杂草在进化过程中所产生的种子数目与杂草的适应度值是呈线性相关的关系[3]。每个杂草产生的种子数的表达式为：

其中：f—当前杂草的适应度值；

fmin—当前种群中杂草的最小适应值；

fmax—当前种群中杂草的最大适应值；

Smin—一个杂草所能生成种子的最小数量；

Smax—一个杂草所能生成种子的最大数量。

当前种群中杂草适应度值范围为[fmin,fmax]，一颗杂草所能繁殖种子的数量范围为[Smin,Smax]。

（3）空间分布

杂草产生的种子在父代个体的周围形成正态分布，其均值为零，标准差为σcur。随着进化次数的增加，标准差可按下式计算：

其中，σcur—当前标准差；

itermax—最大进化迭代次数；

iter—当前进化迭代次数；

σinit和σ fi nal—标准差的初始值和最终值；

n—非线性调和因子。

每轮进化对应的标准差并不一样，随着进化的进行，标准差从σinit一直变化到σ fi nal；一般情况下设置为n=3。

（4）竞争性排斥规则

竞争性排斥规则是经过多次进化之后，当种群规模达到Pmax，按照适应度值大小对所有的个体进行排序，淘汰适应度较差的个体，保留其余个体。

重复以上四步直至达到最大迭代次数。

2、入侵杂草算法的收敛性

对智能优化算法我们要考虑它的收敛性，根据C.Lucas和A. R. Mehrabian的研究，要提高入侵杂草算法的搜索到最优解成功率，把杂草种群的规模扩大并不能起明显作用，而非线性调和因子n对入侵杂草算法的收敛起着至关重要的作用[2]。入侵杂草算法在不断迭代的过程中，适应度值优的个体，将繁殖许多相类似的个体，同时适应度值较差的个体也会有产生子代的机会，且与子代个体一起执行竞争性排斥规则[4]。繁殖的子代个体是随机地散布在父代个体周围呈现正态分布的方式，根据正态分布的特点，这种方法产生的子代大多在上一代适应度值较优的个体附近集中，为了实现种群多样性，同时对上一代适应度值较优的个体附近以外的区域也能兼顾。

三、杂草入侵算法离散化

1、入侵杂草算法离散化算法流程

BIWO算法的实现步骤和IWO算法类似，也分为四个步骤：

（1）初始化二进制种群

对实际问题采用适当的编码方法，每个杂草均为由随机函数产生一个二进制编码序列。单个杂草使用序列(x1,x2,...,xi,...xn-1,xn)来表示，其中xi为杂草的比特位，其值只能取1或0。

（2）产生种子

与IWO产生种子的方法一样，即利用式（1）计算杂草的繁殖的种子数目。

（3）二进制空间扩散

在取值连续的入侵杂草算法中，杂草种子个体仅在其父代个体周围以0为均值，标准差为σ随机的正态扩散分布。但是这种扩散方法并不能直接在BIWO算法中应用，我们使用变异机制去产生和扩散种子。在BIWO算法中，在整个的迭代过程中，标准差σ也将采用和IWO算法类似的变化过程。产生的扩散值通过特定的映射产生变异概率后作用于父代杂草的比特位，并不是直接作用于杂草个体。种群在当进化进行到第k轮时，对于当前种群中某个杂草的某个比特位xik，当前正态分布标准差为σk，Dik是根据正态分布随机函数N(0,σk2)得到的其对应扩散值，设计的映射函数为式（3）。父代种子的每一位可以通过式（3）计算变异概率。式（3）所对应的映射函数曲线见图1。

当杂草二进制序列每位变异概率计算后，当计算杂草所代表的每一位的变异率时，一个相同的在[0, 1]上的随机分布数值会产生，从而可以通过公式（4）计算具体的变异的位：

其中，ρ—[0, 1]之间的随机数。

（4）竞争排斥规则

采用与入侵杂草算法一样的方式，每轮迭代后种群按适应度大小排序，种群规模保持不变。

2、开拓能力和开发能力

为了保证算法较快收敛到全局最优解，我们必须考虑算法的开发能力和开拓能力。算法在某个较小的区域里进行彻底搜索能力称为开发能力，算法在整个搜索空间中开拓新区域能力称为开拓能力。入侵杂草算法同时具有这两种能力。在迭代初期，设置较大的σi值，使种子个体散布到距离父代很远的地方，此时算法很强的扩散能力，种群有较大的多样性，即开拓能力较强；当种子进化到后期时，逐渐减小σi值，从而种子的扩散范围也相应地缩小，原先的优势群体会繁殖产生更多的后代，因为种群的规模是不变的，σi值减小会造成优势个体的后代由于扩散半径较小，生存能力更强，从而可以在适应度值较好的局部区域搜索，从具有较强的开拓能力逐渐变成有较强的开发能力[3]，搜索范围从全局也能逐渐变化到局部区域。

3、标准差取值

在入侵杂草算法中，σi会直接影响杂草个体的扩散范围。若σ fi n较大，将导致后期的σi较大，增大了种群的多样性，但是会使算法不能有效地进行局部开发，较长时间停留在全局开拓阶段，从而增大了搜索全局最优解的难度；若σini较小，将导致初期的σi较小，表现为初始搜索范围较小，使种群的多样性小，同样使搜索全局最优解存在较大的困难。不同的实际问题往往千差万别，故必须依据实际问题预估σini和σ fi n，来确定其对开发精度和开拓范围的要求，以便更好地搜索到全局最优解，更加恰当地解决实际问题。

从上面我们知道，σcur定义了算法的开发和开拓能力，对最终的结果有极大的影响，很好的多样性能使算法搜索到全局最优解，算法通过该参数能够确定全局最优解的位置，适当的集中能够使算法开拓有潜在最优解的区域而得到全局最优解。它会增加算法的收敛速度和找到更优的最终解。因此，保持算法的多样性和集中的平衡是很重要的。但是若使用了固定的σcur去产生每个杂草的种子导致缺乏在开发性和开拓性之间的平衡。

为了克服以上的缺点，我们采用自适应的分散机制。保证σcur在当前一代线性分布，最大的适应值获得最小的σcur，最小的适应值获得最大的σcur。j是根据他们适应值大小分类的杂草的编号。σcur能够通过公式（2）计算，Psum是当前这一代的杂草的数量，σj是第j个杂草的σcur。因此，较低适应度的杂草能够在当前这一代产生较好的种子，另外，这样增加了算法的多样性，因此算法能够更有效地搜索空间。

改进的BIWO算法的伪代码如下：

1. 用二进制序列随机产生杂草P0；

2. Foriter〈itermax执行下一步；

3.通过公式（9）计算每个杂草的适应度；

4. 对这些适应度进行分类；

5. 记录最大的和最小的适应度值；

6. 计算种子的数目Num；

7. 通过公式（2）和（5）计算每个种子的标准差；

8. 通过公式（4）产生种子；

9. 把种子加入种群；

10. If(Num〉Pmax)，执行下一步；

11. 对种群依据适应度值进行分类；

12. 保存适应度值最好的杂草直到Num=Pmax；

13. End if；

14. End for。

四、基于BIWO算法的WSN目标覆盖优化

1、无线传感器网络节点部署模型

现在假定在Fx×Fy的二维平面区域内开始随机布置N个传感器节点，同时有M个随机或者通过某种特定的方式选出来的需要监视的目标点，同时有一个Sink节点。同时，有一些独立的需要监视的目标点POI（points of interest），在整个网络的生存期内，这些目标点必须被至少一个的传感器节点监视。采用二进制编码表示节点的状态，节点休眠时，用“0”表示；节点处于激活状态时,用“1”表示。整个无线传感器网络节点的工作状态用一个二进制串表示。这种表示方法简洁易懂。

（1）能量消耗模型

我们要考虑无线传输的能量消耗，其他比如接收数据、访问内存的能量消耗在此忽略不计。

其中，ETx和ERx—传送和接收一个H位的数据包的能量消耗；

Eelec—发送和接收一位数据的能量消耗；

Eamp—每位数据进行功率放大的损失；

β—路径能量损耗的指数。

（2）无线传感器的二进制模型

我们使用一个变量γi,j代表一个传感器节点i能否覆盖某个为j的POI。若一个POI位于一个传感器节点的感知范围γs内，γi,j为1，否则取0。可以定义为：

其中，(xi,yi)和(yi,yj)—传感器节点i和目标j。

2、适应度评价函数

我们设定两个相关的参数εx和γx,分别代表在当前杂草X覆盖比例和可用的节点数，因此适应度函数可以表示如下：

其中，α1和α2—权重系数；

β1和β2—指数因子。

通过调整权重系数和指数因子，可以确定相应的适应度。Ai代表杂草二进制序列的每一位，其取值是0或者1。我们可以通过下列公式计算ρx和εx：

如果杂草x有较大的适应度，表明此时能监视更多的目标区域。ρx越大，适应度越大；而εx越小，适应度越大。在搜索的过程中，每个杂草都需要按照适应度值大小进行排序。

五、仿真实验

为了检验该算法的性能，采用Matlab对算法应用于无线传感器网络的目标覆盖问题进行仿真实验。

1、参数设置

我们需要在大小不同规模的无线传感器网络评价入侵杂草算法的收敛性。我们可以设置目标点m=64随机地分布在100m×100m的监控区域内，随机分布的传感器节点数目为50～500，节点的感知半径rs为17.675m。数据包的大小为H位。

Eelec—发送和接收一位数据的能量消耗；

Eamp—每位数据进行功率放大的损失；

β—路径能量损耗的指数；

α1、α2—适应度函数权重系数；

β1、β2—适应度函数指数因子。

主要参数设置如表1。

表1 实验参数设置

2、与遗传算法比较收敛性

图2清晰的表明入侵杂草算法优于遗传算法（Genetic Algorithm，GA），因为二进制入侵杂草算法BIWO能够更好地布置节点，在散布500个节点的情况下，平均的适应度比GA提高了52.8%，同时杂草入侵算法比GA需要更短的收敛时间。但是随着需要散布的节点数目增加，平均的收敛时间也随之增加。这是因为节点数目和目标点的增加，增大了问题的复杂度。这个现象在应用GA时更加明显。

3、覆盖保持和网络生存时间的延长

延长无线传感器网络的生存时间，提高它的覆盖度一直是无线传感器网络研究的重要目标。在图3中可以看到，随着无线传感器网络节点数目的增多，对目标点的完全覆盖能够持续更长的时间。因为当出现死亡节点时，能够唤醒合适节点的概率更大。若所有的节点在一开始全部激活，覆盖比率下降的很快。很多节点很快就耗尽了能量。通过采用改进的二进制杂草入侵杂草算法，网络的寿命得到了显著的提高。同样表明，杂草入侵算法适用于不同的网络规模。

六、结束语

无线传感器网络覆盖控制问题是当前学者们研究的一个热点问题。本文研究在无线传感器的目标覆盖中如何提高覆盖的质量和效果，延长网络的生命周期。在入侵杂草算法的基础上，把入侵杂草算法二进制化，并在生成种子时采用自适应的扩散机制。仿真结果表明，相比GA，此算法在收敛性和延长网络的寿命上具有明显的优势，且能够提高目标的覆盖度。