大规模无线传感器网络覆盖优化算法*

2014-09-20仲元昌李发传

传感器与微系统 2014年11期

仲元昌，陈锋，李发传，孟普

(重庆大学通信工程学院，重庆 400030)

0 引言

近年来，无线传感器网络(WSNs)在国防军事、环境监测、智能家居、建筑物结构监控、机场安全检测等众多领域中得到越来越广泛的应用[1,2]，其网络覆盖率是WSNs服务质量的重要衡量标准[3]。

传统覆盖优化算法一般是基于探测和图论[4]，这些算法存在不足之处，探测算法不能完全保证网络的完全覆盖，只适合较小规模的WSNs，图论的基本思想在监测区域内任何一点都可找到一个传感器节点，这与实际情况不符。文献[5]采用蚁群算法，虽然具有局部搜索能力强、较强的鲁棒性和可扩充性，但在求解初期速度较慢，容易出现停滞,收敛速度也较慢，影响网络优化的实时性。文献[6]采用遗传算法，需要重新确定操作，在最优解附近收敛较慢，求解过程比较复杂。文献[7]分析了完全覆盖策略下的节点数目和不完全覆盖策略中的节点数目，提出了用不完全覆盖方法来取代完全覆盖算法，并提出了一种基于节点位置的信息和Voronoi 区域划分的分布式覆盖的解决方案。

本文针对WSNs覆盖问题采用了一种改进的人工鱼群算法(ASFA)，并结合了三峡库区水质监测实际应用环境，提出采用大规模WSNs构建三峡库区水环境监测系统的解决方案[8]。由于三峡库区面积大、分布广，涉及26个区县(其中22个在重庆市辖区内)，有些地方至今还是人迹罕至之处，构成了长江三峡这个特殊的区域，库区呈现出蜿蜒的树状结构[9]。

1 WSNs覆盖优化模型

1.1 覆盖模型

(1)

传感器节点集C区域覆盖面积为所覆盖的监测点面积之和，记作Aarea(c)

(2)

网络有效覆盖率为

(3)

式中A为待监测区域总面积。

(4)

1.2 网络覆盖优化问题

WSNs优化覆盖主要考察2个目标：网络覆盖率和网络节点利用率，在节点之间保持连通的情况下，使用最少的节点获得最大的网络覆盖率，降低节点覆盖区域之间的重复，节点分布更加均匀，节约成本。覆盖问题描述如下：

1)利用式(3)计算各个传感器节点的覆盖率。

2)利用式(4)计算该像素点对传感器节点的利用率。

通过对网络覆盖目标函数和网络节点利用率目标函数进行加权，将其作为算法求解问题的适应度函数，具体定义如下

fobj(l)=w1f1(l)+w2(1-f2(l)),

(5)

式中l=a1,a2,…,aN;w1,w2为子目标函数的权值，且w1+w2=1。

为了找到最优WSNs覆盖方案，本文采用人工鱼群算法对式(5)进行求解

2 覆盖优化算法

2.1 基本人工鱼群算法

人工鱼群算法是一种模仿鱼类行为方式的优化方法，该算法是由李晓磊等人[10]在2002年提出的一种新型的智能优化算法，算法通过鱼群游弋觅食，通过集体协作达到寻优目的。

2.1.1 人工鱼的行为描述

人工鱼的个体状态可表示为Xi=(x1,x2,…,xm)，其中xi(i=1,2,…,m)为欲寻优的变量，F(Xi)为人工鱼Xi的当前食物浓度，人工鱼个体之间的距离可表示为di,j=‖Xi-Xj‖，将WSNs覆盖优化问题抽象为若干条人工鱼探索最大食物浓度的过程，设定人工鱼的步长为step,在其视野visual内游动，且1≤step≤visual，δ(0<δ<1)表示拥挤因子，其值越大，表示越拥挤,δ用来限制人工鱼聚群的规模。

1)觅食行为:设人工鱼当前状态为Xi，在其视野范围内随机选择一个状态Xj，若此状态下的食物浓度大于当前状态，则向该方向前进一步；反之,重新选择状态Xj，判断食物浓度是否大于当前状态，这样反复尝试try_number次后，如仍不满足前进条件，则随机移动一步，即

(6)

式中i=1,2,…,k;xi,xj和xi_net分别为人工鱼状态向量Xi，Xj和人工鱼下一步状态向量Xi/next的第k个分量；Rand()为(0,1)之间的一个随机数。

2)聚群行为:人工鱼探测当前邻域内(即di,j≤visual)的伙伴数目nf和其中心位置Xc，若邻域中心位置Xc食物浓度较大且不太拥挤，即满足F(Xc)>F(Xi)和nf/NF<δ(NF为人工鱼总数)，则邻领域中心方向前进一步，即按式(7)执行

(7)

否则,执行觅食行为。

3)追尾行为:人工鱼在其可视范围内寻找食物浓度最大的伙伴Xi〗max，如周围不太拥挤，则向该人工鱼的方向前进一步，即按式(8)执行

ifFmax>δFi,

(8)

否则,执行觅食行为。

4)公告板:公告板用于记录人工鱼最优状态。人工鱼行动后，如果人工鱼自身状态由于公告板的状态，就将公告板的状态改成自身状态。

5)随机行为:人工鱼在其视野范围内随机选择下一状态，然后向该方向移动。

2.2 改进的人工鱼群算法

2.2.1 混沌系统

为了提高人工鱼群算法的搜索效率，本文引入了混沌系统。混沌具有丰富的时空动态，系统的动态演变可导致吸引因子的转移，在人工鱼群算法中引入混沌，能够有效地避免算法长时间位于局部极值附近，提高算法的全局收敛性和搜索效率。本文采用的混沌系统是由经常用到的Logistic映射产生的，其迭代式如下

Zk+1=f(μZk)=μZk(1-Zk),

Zk∈(0,1),k=0,1,2,….

(9)

式中 μ为系统的扰动参数，Zk为变量Z在k次迭代得到的数值；研究表明，当μ=4是“单片”混沌，即系统处于完全混沌状态，此时系统可以无重复。Zk几乎遍历(0,1)之间的所有状态。

2.2.2 混沌人工鱼群优化算法

基本人工鱼群算法较其他算法有诸多的自身优越性，但其自身不足仍可导致陷入局部值，收敛效率低，由于初始化过程是随机的，虽然大多数情况下人工鱼可保证分布均匀，但对于个体质量不能保证，解群有一部分远离最优解。如果能得到较好的初始解群，将有利于求解效率和解的质量，采用混沌初始化能得到较好的初始化解群。具体实现如下：

为了验证此改进的鱼群算法的有效性和可行性，Sinc函数作为优化目标函数，用Matlab编程进行试验，具体如下:Sinc函数如下

x1≥-10,x2≤10.

(10)

此函数为一多峰函数，在其搜索范围x1≥-10,x2≤10内的(0,0)处有最大值1。

设定人工鱼群规模Np=50，最大迭代次数为300，算法运行50次，拥挤因子δ=0.618，平均步长step=0.3，Try_number=20。以20次实验中的最好值、最差值、平均值为参考量来对2种算法进行比较，如表1所示。

表1 仿真试验结果

通过表1中实验数据可以看出本文提出的算法，在设定相同迭代次数下最差值、最好值及其平均值远远优于基本鱼群算法，在其寻优精度上也优于基本人工鱼群算法。

2.3 覆盖优化策略

1)产生初始化群体：在控制变量可行域内混沌产生N条人工鱼，从中选出Np(NP>N)条较优个体作为初始化鱼群，设置初始迭代次数。

2)公告板赋初值：计算初始化鱼群中个体当前的食物浓度，并比较大小，将其最大食物浓度和这个人工鱼记入公告板。

4)公告板:每条人工鱼在在执行一次行为后，都将检查自身的食物浓度是否优于公告板的食物浓度，若优于公告板，则用自身取代公告板上的值。

5)结束条件判断:判断迭代次数是否达到最大值Gmax或最优解是否在误差范围内，如满足条件，则转向步骤(6);否则,G=G+1，转向步骤(3)，进行下一次优化过程。

6)算法结束，输出结果。

3 仿真与分析

为了对改进的鱼群算法覆盖优化性能进行测试，算法通过Matlab软件进行仿真。假设WSNs监测区域为100 m×100 m范围内，首先随机抛撒60个智能传感器节点分布在监测区域，在随机播散20个传感器节点，如图1(a)。设定节点感知半径Rs=10 m，通信半径Rc=10 m，人工鱼个数为100，人工鱼视野为5 m，拥挤因子δ=0.6，步长为5 m，重复次数try_number=3，最大迭代次数300。

为了该算法的有效性，利用Matlab进行2种模式下的仿真实验，即基本鱼群算法和本文改进的算法。在相同的仿真环境下，分别进行30组实验，2种算法的覆盖优化仿真结果分别如图1(b)和图1(c)。

图1 随机分布的节点和两种算法的仿真结果

由仿真结果图分析可得:基本鱼群算法对监测区域进行覆盖优化平均使用47个节点，节点利用率为58.75 %，平均覆盖率为78.9 %；而利用改进的鱼群算法平均使用43个节点，节点利用率为53.75 %，平均覆盖率为94.22 %，达到了覆盖优化的目地，而且使用了更少的节点，节约了成本，提高了网络的生存时间；同时，改进的算法优化后的网络节点更加均匀地分布满了整个监测区域，能在更短的时间内使用更少的网络节点来达到网络的覆盖要求，减少了节点的冗余，具有更高效的求解近似最优覆盖。