一种多目标的覆盖优化策略在WSNs中的应用*

陈 树，钱 成

(江南大学 物联网工程学院，江苏 无锡 214122)

应用技术

一种多目标的覆盖优化策略在WSNs中的应用*

陈 树，钱 成

(江南大学 物联网工程学院，江苏 无锡 214122)

针对目前无线传感器网络(WSNs)能量均衡覆盖策略大都基于节点静态感知能耗的不足，提出一种基于节点的动态能耗和网络覆盖率的多目标覆盖优化策略。该优化覆盖策略将动态路由协议引入到覆盖控制优化中，计算覆盖区域在不同节点分布下的动态通信能耗和网络的剩余能量，再结合区域覆盖率构成对覆盖和能量综合指数评价的优化函数。最后利用改进差分进化算法和差分进化算法对优化函数进行仿真，并利用覆盖结果验证策略的有效性。仿真结果表明：提出的覆盖优化策略既能使网络达到较高覆盖率，同时又能保证网络的能耗动态均衡，并将改进差分进化算法与常规差分进化算法比较，结果表明：前者克服了早熟现象，覆盖和能量的综合优化函数值更高，达到了6.184。

无线传感器网络; 能量均衡; 动态路由协议; 网络覆盖; 差分进化算法

0 引 言

在无线传感器网络(WSNs)覆盖优化控制算法中，网络覆盖率和节点能耗均衡是热点研究问题。文献[1]采用混沌粒子群算法，以网络覆盖率为优化目标，由算法迭代出覆盖率最优传感器节点集，从而实现对网络的覆盖控制。文献[2]针对异构传感网络节点初始随机部署时产生覆盖盲区和覆盖冗余的问题，以降低节点成本和提高网络覆盖率为目标，引入ε目标约束法，提出一种基于粒子群算法和鱼群算法的群混合算法，实现网络覆盖率和成本之间的平衡和优化。在 WSNs网络传输层，受限于传感器节点自身的电池能量，节点间采用自组织和多跳的方式进行通信和数据传输，而网络簇头的频繁更换和发送成簇信息，将消耗大量节点能量。因此，网络能耗均衡也是一个重要的指标。文献[1,2]均利用改进迭代算法，对网络节点的位置进行寻优，即在网络的拓扑层，对网络节点进行最优部署，实现覆盖率最大化目标，但文献[1,2]都没有考虑能量均衡对网络性能的影响。文献[3]建立以网络覆盖率和网络能量均衡作为优化目标函数，将节点的静态感知能量损耗作为能量均衡指标，在每次算法迭代中，计算每个区域的剩余能量，并结合覆盖率得到综合优化指数。文献[4]提出一种基于WSNs能耗、能耗均衡和覆盖率多目标优化覆盖控制策略。在构建网络模型的基础上，以覆盖率、能耗和网络能耗均衡为优化目标，实现网络性能的综合优化。文献[3,4]将能量均衡引入到覆盖率控制中，实现了多目标覆盖优化，但文中的能量是基于节点的感知能耗，没有考虑节点的动态通信能耗。

本文提出了一种基于节点的动态通信能耗结合网络覆盖率的多目标覆盖优化策略。该策略将LEACH[5](low energy adaptive clustering hierarchy)路由协议引入到覆盖控制优化中，计算由节点的动态通信能耗得到网络的剩余能量，并结合网络覆盖率建立优化目标，实现对网络的动态能耗均衡和覆盖率优化的双重目标。

1 覆盖优化策略

1.1 网络覆盖率

假定区域为二维平面，拟在区域上投放n个传感器节点。设ci=(xi,yi)为传感器节点的坐标，则节点ci对网格点qj=(xj,yj)的感知概率[3]为

式中d(ci,qj)为节点ci与qj的实际距离，Re为节点测量的可靠性参数，b为节点的感知概率阈值，a为网格点被传感器监测到的概率随距离增大而减小的速率。由于目标点qj的感知概率是传感器节点协同监测的结果，设Call为传感器节点的集合，则Call对目标点qj的感知概率[6,7]为

设目标区域被离散化为M×N个网格，每个网格的面积表示为1，则可得Call对整个监测区域的覆盖率

(1)

由上可知，式(1)的最大值就是网络的最大覆盖率。但对一个能量有限的WSNs，仅以最大覆盖率为优化目标是片面的。覆盖率高的网络和能量消耗均衡的网络并没有对应关系。为此，要充分优化网络的覆盖性能，一个好的优化方案必须同时兼顾覆盖率和动态通信能耗两方面的要求。

1.2 网络节点通信能耗

运用LEACH协议对网络节点间的通信进行模拟，得到节点的通信能耗和网络的剩余能量。LEACH是一种自组织自适应的路由协议，簇内成员节点将数据发送给簇首，簇首对数据融合后将数据发送给Sink节点。因为簇首的能耗较大，可以通过每轮随机的选取簇首来平均节点的能量消耗，达到能耗均衡的目的。

若设传感器节点数为N，每轮的簇头数为K，则每轮各簇的能耗[8]为

每轮的簇群总能耗为

Etotal=K·E[ECluster].

设传感节点的初始能量为E0，传感器网络LEACH协议下模拟运行了r轮，则第r轮后，网络的剩余能量为

Eres=N·E0-r·Etotal.

当节点的当前剩余能量小于0，则表示该节点已经死亡。

1.3 覆盖率和能量综合指数

本文综合考虑网络覆盖率和网络通信能耗参数，采用线性加权和法得到覆盖率和能量综合指数为

f=w1·Cov(Call)+w2·Eres.

(2)

其中，w1,w2为各子优化目标的权值且w1+w2=1。在对实际场景进行覆盖控制优化时，可以通过改变子目标的权重因子，实现不同的优化要求。例如:当权重因子w1>w2时，表示网络覆盖率在综合覆盖优化中成为主要因素；反之，当w1

2 改进差分进化算法

差分进化(DE)算法[9]是随机搜索算法，旨在从某一随机产生的初始种群开始，按照变异、交叉和选择三种操作规则下不断迭代，保留优良个体，淘汰劣质个体，引导搜索过程向最优解逼近。DE算法也可以融合其他智能算法，提高算法的寻优特性。例如:文献[10]提出的基于DE的鱼群算法，该算法通过引入DE策略，克服人工鱼群算法存在的收敛速度慢，精度差等不足。

算法的操作过程如下：

1)反学习方法初始化种群[11,12]

在种群初始化时采用反学习方法，可以增加初始种群解的多样性，加快算法的全局收敛速度。设解向量的维数为D，种群数为NP，r为进化代数，则每代的解向量可表示为

Xi,r=(X1i,r,X2i,r,…,XDi,r),i=1,2,…,NP.

设解向量的搜索空间为

种群初始解向量可表示为

初始解向量产生对应的反向解可表示为

将初始解和方向解带入式(2)，选取适应度值较大的个体作为初始种群的解向量。

2)种群变异

种群变异策略是从父代种群中根据变异算子生成新个体。新个体解向量由下式产生

Vi,r+1=Xa,r+F·(Xb,r-Xc,r).

(3)

其中，整数a,b,c∈[1,NP]且和当前个体i互不相同。本文采用文献[13]提出的变异因子F的自适应调整策略，有利于始终保持种群的多样性，加强局部搜索能力和收敛速度。

3)种群交叉

种群交叉策略是新旧个体按照交叉概率交换部分元素，形成新的个体。新个体解向量可由下式产生

Ui,r+1=(U1i,r+1,U2i,r+1,…,UDi,r+1),i=1,2,…,NP,

(4)

其中，CR为交叉概率。

4)种群选择

将经过变异，交叉操作得到Ui,r和父代Xi,r，运用最优保存策略选择适应度值较大的个体，进而成为r+1的父代

(5)

5)人工蜂群搜索策略

DE算法在进化中后期, 由于种群多样性的降低, 当优化复杂的多峰问题时, 如果有个体陷入局部最优跳不出去, 则它会将附近的个体向局部最优区域引导;当很多个体陷入局部最优区域时,容易出现早熟现象。针对上述DE算法的缺陷，本文引入文献[11]提出的人工蜂群搜索策略。在该策略中，新的候选解向种群中随机选择的个体移动,由于选择的随机性, 适应值好的个体和适应值差的个体被选择的概率是相同的，从而使种群中的个体尽快跳出局部最优点,达到避免早熟的目的。

3 实验仿真

为了验证本文提出的覆盖优化策略的有效性，设计了Matlab仿真程序，并将DE和改进DE算法对优化策略的仿真结果进行对比。各项实验参数如下：算法迭代次数rmax为900；目标区域范围为20 m×20 m；传感器节点数为60个；交叉概率为40 %；节点检测概率减小速率为50 %；节点感知概率阈值为30 %；节点检测可靠范围Re为1 m；LEACH协议模拟通信轮数为400;节点初始能量E0为0.3 J;Sink节点的坐标为(10,10)m;覆盖率优化系数w1为0.3;网络剩余能量优化系数w2为0.7。

图1为运用DE和改进DE算法对覆盖率和能量综合指数的仿真结果对比图。由图1可知，DE算法在290代时陷入了早熟收敛，最优值维持在6.109直到迭代结束。改进DE算法相较于DE算法最优值搜索速率更快，在迭代期间没有陷入早熟，迭代结束时最优值为6.184。

图1 改进DE与DE算法迭代过程Fig 1 Iterative process of improved DE algorithm and conventional DE algorithm

图2、图3分别为经过DE算法和改进DE算法对优化目标迭代得到的最优节点分布在LEACH仿真下区域剩余能量和仿真轮数的关系。由图2、图3可知，经DE算法得到的最优节点分布在LEACH仿真轮数为400时区域能量为8.4 J，而经改进DE算法得到的最优节点分布对应的区域能量则为8.6 J，可见改进DE算法的仿真结果优于DE算法。若假设投放到区域的节点数量增多，节点的能耗参数加大，由上二种算法得到的区域能量差值则会更大。图4、图5分别为经DE算法和改进经DE算法得到的最优节点在区域中的分布。由图4、图5可知，经改进DE算法得到的节点在区域中分布地更加均匀，节点相互重叠区域更少，有利于覆盖率增加和网络的能量均衡。

图2 LEACH仿真下DE算法区域剩余能量和轮数关系Fig 2 Relation between regional residual energy and round number of conventional DE algorithm simulated by LEACH

图3 LEACH仿真下改进DE算法区域剩余能量和轮数关系Fig 3 Relation between regional residual energy and round number of improved DE algorithm simulated by LEACH

图4 DE算法最优节点分布Fig 4 The optimal distribution of nodes of conventional DE algorithm

图5 改进DE算法最优节点分布Fig 5 The optimal distribution of nodes of improved DE algorithm

4 结 论

本文提出了一种基于节点的动态通信能耗和网络覆盖率的多目标覆盖优化策略。该优化策略既能使网络达到较高覆盖率，又能保证网络的能耗动态均衡,覆盖和能量的综合优化函数值达到了6.184,有效克服了早熟现象，实现了网络动态能耗均衡和覆盖优化的双重目标。

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

[2] 张 斌,毛剑琳,李海平,等.群混合算法应用于异构传感器网络节点的优化部署[J].计算机应用,2012,32(5):1228-1231.

[3] 黄瑜岳,李克清.基于人工鱼群算法的无线传感器网络覆盖

优化[J].计算机应用研究,2013,30(2):554-556.

[4] 梁 天,周 晖,谢 静,等.无线传感器网络的多目标覆盖控制策略[J].传感技术学报,2010,23(7):994-999.

[5] Heinzelman W R,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications,2002,1(4):660-670.

[6] 张云洲,吴成东,程 龙,等.确定性空间的无线传感器网络节点部署策略研究[J].控制与决策，2010,25(11):1625-1629.

[7] 靳立忠,常桂然,贾 杰,等.基于差分进化算法的移动传感器网络节点的分布优化[J].控制与决策,2010,25(12):1857-1860.

[8] Gamwarige S,Kulasekere C.Performance analysis of the EDCR algorithm in a distributed wireless sensor networks[C]∥2006 IFIP International Conference on Wireless and Optical Communications Networks,2006:1-5.

[9] Stron R,Price K.Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization,1997,11(4):341-359.

[10] 张大斌，杨添柔，温 梅.基于差分进化的鱼群算法及其函数优化应用[J].计算机工程,2013,39(5):18-22.

[11] 黄玲玲,刘三阳,高卫峰.具有人工蜂群搜索策略的差分进化算法[J].控制与决策,2012,27(11):1644-1648.

[12] 高卫峰,刘三阳,黄玲玲.受启发的人工蜂群算法在全局优化问题中的应用[J].电子学报,2012,40(12):2309-2316.

[13] 余 兵.差分进化算法及其应用[D].西安：西安工程大学,2007.

Application of a multi-objective coverage optimization strategy in WSNs*

CHEN Shu, QIAN Cheng

(School of IoT Engineering,Jiangnan University,Wuxi 214122,China)

Aiming at most energy equilibrium coverage strategy is based on insufficiency of energy consumption of static perception of node mostly in WSNs,a multi-target coverage optimization strategy is brought forward based on dynamic energy consumption and network coverage rate based on node.The strategy introduces dynamic routing protocol to coverage control optimization compute the dynamic energy consumption and the residual energy of the network,establish optimal function which evaiuate on coverage and energy comprehensive index combined with area coverage rate.Improved differential evolution algorithm and differential evolution algorithm are used for simulation and use result of coverage result to verify effectiveness of strategy.Simulation result shows that the coverage optimization strategy can achieve high coverage rate and guarantee dynamic balance of network energy consumption at the same time.In addition,in comparison with the improved differential evolution algorithm and the conventional differential evolution algorithm,the improved differential evolution algorithm overcomes prematurity value of comprehensive optimization of coverage and energy is more higher,which reaches 6.184 function.

wireless sensor networks(WSNs); energy balance; dynamic routing protocol; network coverage; differential evolution algorithm

10.13873/J.1000—9787(2014)10—0151—04

2014—01—10

江苏省六大人才高峰资助项目(2012—WLW—006)；国家自然科学基金资助项目(21206053)

TP 273

A

1000—9787(2014)10—0151—04

陈 树(1969-)，男，江苏淮安人，副教授，主要从事过程控制与优化、现场总线与控制技术、无线传感器网络与通信等研究工作。