基于改进人工蜂群算法的WSNs覆盖优化

王 鑫， 谭华忠, 蒋 华

(桂林电子科技大学 计算机科学与工程学院，广西 桂林 541004)

0 引 言

人工蜂群(artificial bee colony，ABC)算法是Karaboga D[1]在2005年提出的一种用于解决数值优化问题的新型群智能算法，算法是仿照蜜蜂的觅食行为而提出的，具有操作简单、参数少和随机优化性等优点，相比于差分进化算法和粒子群算法也具有更强的灵活性与适应性[2]。作为一种新型多目标优化算法，ABC算法被应用于调度问题[3]、图像分割[4]、运动目标检测[5]等多个领域中。

无线传感器网络(wireless sensor networks,WSNs)现在被广泛应用到健康检测、生态环境监测、军事监控等领域[6]。WSNs的覆盖控制问题,可以看作是在WSNs节点能量、无线网络通信带宽、网络计算处理能力等资源普遍受限情况下,通过网络传感器节点放置和路由选择等手段,最终使WSNs的各种资源得到优化分配,进而使感知、监视、传感、通信等各种服务质量得到改善[7]。文献[8]基于粒子群算法提出一种覆盖优化方法，在一定程度上提高了覆盖率，但方法容易收敛到局部最优解。文献[9]提出了基于带精英策略的非支配排序遗传算法的节点部署方案，获得了很好的网络覆盖率，但算法复杂度过大。随着网络的运行，节点的能量会不断下降，上述文献并没根据节点能量的变化而动态地对网络进行覆盖优化。

本文针对基本ABC算法的不足，引入自适应混沌优化改进算法，并把改进ABC(IABC)算法应用到WSNs的覆盖优化问题中，从而实现传感器节点的动态最优部署。仿真实验证明:该算法不仅克服了基本ABC算法收敛速度慢和“早熟”的缺点，提高了网络覆盖率，而且能有效地延长网络寿命，确保了良好网络服务质量。

1 ABC算法与改进算法

1.1 基本ABC算法

在ABC算法中，待优化问题的可能解由食物源的位置Xi={xi1,xi2,…,xid}表示，相应解的质量与食物源的花蜜数量有关。ABC有3种类型蜜蜂：侦查蜂、观察蜂和雇佣蜂。

侦查蜂负责新食物源的随机搜索，观察蜂在舞蹈区等待选择一个食物源，而雇佣蜂则与一个已知食物源位置相关。观察蜂是根据与食物源相关的概率pi对食物源进行选择的，这个概率pi的计算如下

(1)

其中，SN为食物源数量，与雇佣蜂的数量相等。fiti为由式(2)给出的解的适应度，可以看出它与目标函数值fi呈反比

(2)

观察蜂和雇佣蜂用式(3)从旧的食物源位置产生新候选位置，并把新位置和旧位置进行比较保留较优者

newij=xij+φij(xij-xkj).

(3)

其中，k∈{1,2,…，SN}为一个不等于i的随机数，SN为解(种群)的总数，j∈{1,2,…,d}(d为维数)，φij为[-1,1]间的随机数，控制着xij邻近食物源产生。

如果食物源位置在超过预先定义的次数还没得到进一步改进，则放弃该食物源并且这个食物对应的雇佣蜂成为侦查蜂。然后，由侦查蜂生成的新食物源代替原来的食物源，新食物源的计算如下

(4)

1.2 改进算法

在基本ABC算法中，雇佣蜂和观察蜂是进行随机性的位置更新，得到好食物源和不好食物源位置的可能性是一样的，容易使算法出现收敛速度慢、早熟等问题。为克服上述问题，本文引入了文献[10]中的自适应混沌优化算法，通过用改进的Tent映射产生混沌变量，然后映射到优化变量的取值空间，优化变量的搜索空间通过混沌遍历性得到细化，最后根据蜂群迭代状态自适应地调整搜索精度。改进的Tent映射

ifxk=0,0.25,0.5,0.75 orxk=xk-m,

xk+1=T′(xk)=T(xk)+0.1rand(0,1);

else then

xk+1=T′(xk)=T(xk).

(5)

其中

根据式(5)生成混沌向量α(i,j)，则混沌优化后的食物源位置为

(6)

(7)

式中c为当前迭代次数，C为最大迭代次数。

从式(6)可以看出：混沌向量α(i,j)的遍历性避免了算法“早熟”，自适应因子μ随着迭代的进行而自适应调整搜索范围，克服了收敛过慢。

2 基于IABC算法的WSNs覆盖优化方法

2.1 相关假设

假设在待监测区域内随机部署n个节点，用si代表WSNs中的第i个节点，则传感器节点集合为S={s1,s2,…,sn}。针对WSNs特性，对网络作如下假设：

1)网络中的各节点具有相同的感知半径Rs和通信半径Rc，且有Rc=2Rs;

2)各节点能够获取自身和其邻居节点的位置信息;

3)移动节点能量较充足，能够支持移动节点完成位置迁移过程。

2.2 感知模型

事实上，感知器节点是通过测量接收到的能量来得知目标的出现，而这个能量会随着目标与传感器节点的距离变化。不同于布尔感知模型，概率感知模型考虑了信号检测过程的不确定性，同时假设相应的感知概率函数值与距离呈反比。可见，概率感知模型比布尔感知模型更适合应用于实际中传感器节点对目标事件的推断。本文采用文献[11]中的概率感知模型，pi为传感器节点si检测到目标事件j的概率

(8)

其中，re为对传感器不确定性的一种估量，a=dij-(rs-re),k和m为目标事件落入不确定区域时概率的衰变因子。容易看出，这个概率随着传感器节点与目标位置之间距离的增加，而呈现出指数型的下降。

如文献[12]所描述，目标事件j能被传感器网线检测到是指目标事件的联合感知概率p(j)大于一定的阈值ε，这个阈值ε的大小视具体的应用而定

(9)

在给定一个监测区域R，包含了目标事件集T={tj|j=1,2,…,m}和传感器节点集S={si|i=1,2,…,n}，每个si都有一个相应的权值wi，这个权值与节点剩余能量相关，WSNs覆盖优化问题指的就是寻找能覆盖区域R中T的具有最小权值和的S的子集C，即使式(10)的值最小化

(10)

所求得子集C满足式(11)，aij和δ分别为关于pi(j)和ε的函数

(11)

其中

(12)

2.3 基于IABC的WSNs覆盖优化

在ABC算法中，群体中雇佣蜂或观察蜂的数量等于待优化问题解(食物源)的数量。假设SN表示解的数量，每只蜜蜂的位置代表着一种传感器节点的分机，即

xi=(xi1,yi1,xi2,yi2,…,xik,yik,…,xin,yin).

基于IABC算法的WSNs覆盖优化问题就是求解使式(10)取得最小值的最佳位置xbest，其具体实现步骤为：

1)初始化蜂群，随机生成SN个可行解fi;

2)根据式(10)计算解的适应度fiti;

3)对于每只雇佣蜂根据式(6)产生新的解newi，计算相应的适度fiti，应用贪婪规则选择旧解与新解之间较优者;

4)根据式(1)计算每个解fi的选择概率pi;

5)对于每只观察蜂根据概率pi选择解fi，并重复步骤(3)的操作;

6)超过阈值limit没有改进的蜜蜂变为侦查蜂，以式(4)随机产生的新解替代原来的解；

7)记录当前最优位置xbest，如果已经达到最大循环次数，则输出找到的最优位置;否则,返回步骤(2)。

由于被激活传感器节点的能量是不断减少的，其权值也应该是随着动态变化的，所以,算法中设置了一个当前覆盖子集的门限权值wth和一个限定时间tmax，当前覆盖子集的权值和超过门限权值wth，或运行时间超过限定时间tmax，则重新运行上述算法步骤选择新的最优覆盖子集。

3 仿真实验

3.1 参数设置

假设WSNs的监测区域为40 m×40 m的方形区域，在区域内随机部署120个传感器节点，设置WSNs概率感知模型参数，rs=1 m，re=0.5rs，k=0.5，m=0.5，ε=0.7。

3.2 实验结果与分析

如图1所示，对比分析了IABC算法相对基本ABC算法性能的提升。网络的初始覆盖率为55.36 %，IABC算法经过大约160次迭代循环后收敛到稳定值88.23 %；而在基本ABC算法中，此时的网络覆盖率为78.66 %，并在220次循环之后才达到稳定值81.52 %。这表明，IABC算法相对基本ABC算法提高收敛速度，增强了全局寻优能力，有效地提高了网络覆盖率。

图1 网络覆盖曲线

在相同时间内激活的传感器节点越少，网络能量的消耗也越少，这样整个网络的生存时间就更长。为了评价本文算法的有效性，图2描述了文献[12]中贪婪算法与IABC算法随着时间变化而激活的传感器节点数。可以看出，IABC算法随着时间增加，激活的传感器节点的数目并没有出现过快地增加，因此，可以更加有效地延长网络生存时间。

图2 激活传感器节点数

4 结 论

本文针对基本ABC算法不足，提出了一种IABC算法，并用于WSNs的覆盖优化问题中，并通过最优覆盖子集的动态更新实现网络生存时间最大化。由于IABC算法克服了原算法收敛速度慢、“早熟”等缺点，因此,更有利于得到全局最优解。仿真实验结果表明:本文提出的IABC算法明显提高了网络覆盖率，有效地延长了网络的寿命。

参考文献:

[1] Karaboga D,Ozturk C.A novel clustering approach: Artificial bee colony(ABC) algorithm[J].Applied Soft Computing,2011,11:652-657.

[2] Karabago D,Basturk B.A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm[J].Journal of Global Optimization,2007,39(3):459-471.

[3] 赵良辉,王天擎.蜂群算法解决集聚约束调度问题[J].计算机工程与科学,2011,33(11):84-88.

[4] 梁建慧,马 苗.人工蜂群算法在图像分割中的应用研究[J].计算机工程与应用,2012,48(8):194-196,229.

[5] 陈 雷,张立毅,郭艳菊,等.基于人工蜂群算法的运动目标检测方法[J].计算机工程与应用,2012,48(21):178-181,221.

[6] Ammari H M,Das S K.Centralized and clustered k-coverage protocols for wireless sensor networks[J].IEEE Transactions on Computers,2012,61(1):118-133.

[7] 任 彦,张思东,张宏科.无线传感器网络中覆盖控制理论与算法[J].软件学报,2006,17(3):422-433.

[8] 林祝亮,冯远静.基于粒子群算法的无线传感器网络覆盖优化策略[J].计算机仿真,2009,26(4):190-193.

[9] 李燕君,潘 建.无线传感器网络的节点智能部署方法研究[J].计算机科学,2012,39(8):115-118,135.

[10] 王瑞琪,张承慧,李 珂.基于改进混沌优化的多目标遗传算法[J].控制与决策,2011,26(9):1391-1397.

[11] Zou Y,Chakraharty K.Sensor deployment and target localization in distributed sensor networks[J].ACM Transaction on Embe-dded Computing System,2004,3(1):61-91.

[12] Altinel I,Aras N,Gney E.Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor network[J].Computer Network,2008,52(12):2419-2431.