2018, Vol. 39
2. 东北大学 机器人科学与工程学院, 辽宁 沈阳 110819
2. School of Robot Science and Engineering, Northeastern University, Shenyang 110819, China
无线多媒体传感器网络(wireless multimedia sensor networks, WMSNs)在战场、火山森林和工业监测中得到了广泛的应用[1].WMSNs具有更加丰富的感知能力, 如图像、视频和温度等信息[2], 并具有更强的信息处理能力, 如图像处理、目标识别和定位跟踪等高级功能[3].
对目标的有效覆盖是WMSNs执行后续任务的基础, 良好的覆盖效果可以保证对目标区域内进行有效的数据收集.覆盖率通常是衡量WMSNs覆盖质量的重要指标之一[4].一般情况下, 网络覆盖的范围越广, 覆盖的目标越多并且覆盖重叠越小则认为网络的覆盖能力越强.
现有的覆盖增强算法多是针对普通的无线传感器网络(wireless sensor networks, WSNs)[5-6].WSNs采集的数据比较简单并且是全向感知模型, 而WMSNs采集的数据相对复杂, 并且由于摄像头视角的约束, WMSNs多为有向感知模型.目前对于多媒体传感器网络的覆盖研究大多集中在二维平面[7], 对于三维多媒体传感器网络的研究较少, 但在实际环境中, WMSNs多处于三维环境中[8], 如对于丘陵和水下传感器网络的监测等, 因此本文针对三维空间的覆盖问题提出了基于三维感知模型的覆盖增强算法.同时, 传统的覆盖增强算法由于计算量大, 容易早熟并陷入局部最优解[9-12], 因此本文提出的改进布谷鸟搜索算法通过引入Levy flight策略, 可以有效跳出局部最优解, 以获得全局最优解.
1 引入精英机制的布谷鸟搜索覆盖增强算法 1.1 布谷鸟算法布谷鸟搜索算法是基于Levy flight的一种智能优化方法, Yang等[13]于2009年提出了该方法.可利用的寄生巢穴数量是固定的, 一个寄生巢穴的主人能发现一个外来鸟蛋的概率为Pf(即新的优化方案的概率为Pf), Pf的取值范围在[0, 1].s为Levy flight的步长.
|
(1) |
布谷鸟的连续跳跃形成了一个随机游走的过程.同时, 另外一部分差的鸟巢以Pf的概率被发现.在新的位置上, 鸟巢通过随机游走的方式建立.在位置信息更新之后, 以随机数s(s∈[0, 1])与发现概率Pf进行对比, 若随机数较大, 则对新位置进行随机更改, 否则不变.最后将最好的位置进行保留.
Levy分布的步长计算公式为
|
(2) |
μ和v均服从正态分布,
|
(3) |
|
(4) |
式中,
|
(5) |
Levy稳定分布的尺度为σ, 特征值为α, 位移为μ, 偏差系数为β, Γ是标准的Gamma函数.
1.2 精英机制在布谷鸟算法中, 通常利用Levy fight来产生随机解, 以此对网络进行局部和全局的搜索, 最终找到适应度最好的个体, 作为网络的最优解.但是Levy fight产生的解空间是随机的, 优质的解也会被随机地抛弃, 尽管布谷鸟算法具有速度快的特点, 但还是可以通过优化产生解的方式来进一步加快算法的速度, 提高算法的质量.因此, 提出引入精英机制的改进布谷鸟覆盖增强算法, 通过将精英机制引入布谷鸟算法来保留较优质的巢穴到优质巢集合中, 既可以产生较多的个体, 同时还可以保障优质的解不被破坏, 加快算法的收敛速度.
精英保留(maintain the best solution found over time before selection)策略是针对遗传算法提出来的.在遗传算法中的基因, 并不一定真实地反映了待求解问题的本质, 因此各个基因之间未必就相互独立, 如果只是简单地进行杂交, 很可能将好的组合给破坏了, 这样就没有达到累积较好基因的目的, 反而把原本很好的基因给破坏了.精英保留策略可以避免最优个体不会因为杂交操作而被破坏.
设到第t代时, 群体中a(t)为最优个体.又设A(t+1)为新一代群体, 若A(t+1)中不存在最优个体, 则把a(t)加入到A(t+1)中作为A(t+1)的第(n+1)个个体, 这里n为群体的大小.
为了保持群体的规模不变, 如果将新产生的精英个体加入到新一代群体中, 则可以将新一代群体中适应度值最小的个体淘汰掉.
1.3 多维度优化策略多维度优化策略指的是对两个或者两个以上维度进行优化的策略, 同时, 这些维度往往是互相制约的.
定义1 Pareto支配关系, 对于多维度优化问题的两个解空间K1和K2, 满足:
1) 对任意k∈{1, 2, …, K}, 都满足fk(K1)≤fk(K2);
2) 至少存在一个k∈{1, 2, …, K}, 使得fk(K1)＜fk(K2).
若空间中没有支配K1的解, 则解K1被称为非支配解, 即Pareto最优解.
定义2 所有Pareto最优解所组成的解空间为Pareto最优解集.
在Pareto最优解空间中的每个解互相独立, 没有支配关系.因此在目标空间中, 所有的Pareto最优解构成了Pareto前沿.
首先对解空间进行Pareto分层, 确定解空间Kn={K1, K2, …, KK}中所有解的支配关系, 将独立的解标记层数K=1;然后将这些独立的解从解空间中删除, 确定剩下解的支配关系, 接着找出剩下解空间中的独立解, 并标记层数K=2;以此类推, 将所有解一一进行标记, 计算出适应度为
|
(6) |
接下来进行适应度的增强, 目的是使解空间变得均匀和多样.通过引入小生境技术对网络中分布不均匀的独立解进行适应度的增强[14].
小生境技术指的是如果空间中两个目标的距离小于预先给定的阈值时, 则需要对其中适应度比较小的个体进行惩罚, 接着利用共享函数对网络的拥挤程度进行衡量.小生境数越大, 解的附近越拥挤, 因此适应度的值就越小.
增强后的适应度值为
|
(7) |
式中, I(sn)为示性函数, 表示支配层数1的解, 即对第一层进行适应度增强.
|
(8) |
Cn(Niche)代表解为Kn的小生境数:
|
(9) |
式中dij为第j个解和第i个解之间的距离, 该距离为欧氏距离. s(d)为共享函数, 共享函数可以表示为
|
(10) |
式中σshare为小生境的阈值.
通过多维度优化策略进一步地对网络的适应度, 即摄像头的旋转角度进行优化, 可以使网络的覆盖更加均匀, 覆盖率得到进一步提升.
1.4 学习反馈策略在布谷鸟算法中, 步长因子α非常重要, 因为其关系着种群的改善率和算法的稳定性与高效性.因此, 利用算法的学习机制, 动态地调整步长因子, 可以提高算法的搜索性能, 同时加快算法的搜索速度.在布谷鸟算法中, ait=[ai1t, ai2t, ai3t, …, aint]表示第i个鸟巢在第t代的位置, n为优化问题的维数.新的鸟巢位置由Levy fight产生, 因此布谷鸟鸟巢的更新公式为
|
(11) |
式中:⊕代表点对点的乘法; L(λ)代表服从参数λ(1＜λ＜3)的Levy fight产生的随机搜索向量.其中,
|
(12) |
abestt代表当前时刻t所保留的最优的鸟巢位置.
接着评估备选鸟巢的好坏, 用式(13)决定是否替换鸟巢原先的位置.
|
(13) |
步长因子的更新规则为
|
(14) |
式中:rn为[0, 1]之间的随机数; Pi为步长因子α的更新概率.更新概率的规则为
如果鸟巢的位置是优质解, 则
|
(15) |
否则,
|
(16) |
式中, ω1和ω2∈(0, 1).式(15)和式(16)的物理意义在于如果目前的步长因子可以得到鸟巢位置的优质解, 则保留当前的步长因子的概率变大; 否则, 更新当前步长因子.
可以看出, 步长因子α具有闭环控制中的反馈特性, 可以对输出的解进行修正, 来使种群稳定地向优质解输出, 对整体的优化过程进行监控.
1.5 算法流程引入精英机制的目的在于在Levy fight产生的解被抛弃前与所设定的精英阈值进行对比, 满足阈值条件的解将会和优质解一同被保留到π/3优质解集群中.优质解集群设有上限, 当集群达到上限后, 网络将会抛弃优质解集群中适应度最小的个体, 最终网络的最优解也将从该优质解集群中产生.
引入精英机制的改进布谷鸟覆盖增强算法流程:
步骤1 初始化布谷鸟算法相关系数, 确定节点数目N, 种群数m, 定义初始发现概率Pf, 步长因子α, 布谷鸟算法学习因子β, 随机生成初始序列A={a1, a2, a3, …, an}, 并计算适应度fitness.
步骤2 进行迭代寻优, 不断迭代出更优的解.
步骤3 进行判断, 是否为精英集合中的最优值, 若是不进行任何改变, 直接复制到下一代, 然后跳到步骤8;否则将产生的个体并入种群, 计算本代的适应度.
步骤4 进行多维度优化操作, 增强本代的适应度.
步骤5 判断本代适应度值是否优于当前种群最优适应度, 若是则将本代的适应度替换为当前最优适应度; 否则保留当前最优适应度.
步骤6 计算本代进化率和步长因子.
步骤7 判断进化率是否大于进化阈值, 若是则更新步长因子; 否则保留当前步长因子.
步骤8 判断是否满足迭代终止条件, 若是则结束过程; 否则返回步骤3.
以上算法每一次迭代过程都会向着优化目标函数增大的方向靠近, 算法的最终目的是计算出目标函数的全局最优值, 使覆盖效果达到最优, 网络的性能达到最佳状态.
2 仿真实验与结果分析 2.1 实验环境设置对60 m×60 m的区域进行初始部署, 摄像头被放在高度为3 m的位置, 水平视野θsp为π/3, 垂直视野θcz为π/3.摄像机的有效识别距离定义为10 m.接着进行迭代优化, 分别呈现了初始部署, 50代迭代, 100代迭代和最终的迭代效果, 以及覆盖率的进化曲线, 如图 1所示.实验参数如表 1所示.
|
图 1 网络优化效果图 Fig.1 Diagram of the network optimization (a)—初始部署; (b)—50次迭代后; (c)—100次迭代后; (d)—最终节点. |
|
表 1 算法仿真参数 Table 1 Simulation parameters |
为了有效地计算覆盖率, 将目标区域进行网格化, 单位网格的面积为2 m×2 m, 由图可知网络的初始覆盖率较低, 同时覆盖存在大量的重叠区域, 由灰度权重图可以直观地看出, 黑色区域表示被有效覆盖的位置, 空白位置表示未被覆盖的位置, 而灰色的区域表示覆盖重叠相对严重的位置; 在迭代50次后, 网络的覆盖情况得到了明显的改善, 覆盖重叠区域开始减少; 在迭代100次后覆盖情况达到较优水准, 覆盖重叠得到明显改善, 未被覆盖的区域也明显减少, 覆盖率提升近18%;在迭代结束后, 覆盖情况得到显著改善, 覆盖率最终提升达到22%, 同时花费时间较短, 证明算法的效率非常高.
2.2 性能对比实验在同模拟退火算法(simulated annealing, SA)进行对比时, 使用同一初始部署来保障效果对比的有效性.由图 2可以看出, 引入精英机制的改进布谷鸟覆盖增强算法的效果要明显好于模拟退火算法, 这是由网络的进化方式和优化策略共同决定的.精英机制可以很好地保留优秀个体, Levy flight可以有效地跳出局部最优解, 多维度优化策略可以有效地增强目标函数的适应度, 学习反馈策略可以动态地调整步长因子, 有效地增强网络的搜索能力.因此, 引入精英机制的改进布谷鸟覆盖增强算法在每一代的优化效果都要优于模拟退火算法.
|
图 2 覆盖率增长图 Fig.2 Growth figure of the coverage ratio |
本文研究了三维多媒体传感器网络覆盖增强算法, 通过将精英机制、多维度优化和学习反馈策略引入布谷鸟算法来优化多媒体传感器节点的旋转角度以降低覆盖重叠, 优化网络覆盖.仿真结果表明该算法可以有效降低覆盖重叠, 提高网络的覆盖率.
| [1] |
Akyildiz I F, Melodia T, Chowdhury K R.
A survey on wireless multimedia sensor networks[J]. Computer Networks, 2007, 51(4): 921–960.
DOI:10.1016/j.comnet.2006.10.002 |
| [2] |
He S B, Shin D H, Zhang J S, et al.
Full-view area coverage in camera sensor networks:dimension reduction and near-optimal solutions[J]. IEEE Transactions on Vehicular Technology, 2016, 65(9): 7448–7461.
DOI:10.1109/TVT.2015.2498281 |
| [3] |
Rehman Y A U, Tariq M, Sato T.
A novel energy efficient object detection and image transmission approach for wireless multimedia sensor networks[J]. IEEE Sensors Journal, 2016, 16(15): 5942–5949.
DOI:10.1109/JSEN.2016.2574989 |
| [4] |
Alanazi A, Elleithy K.
An optimized hidden node detection paradigm for improving the coverage and network efficiency in wireless multimedia sensor network[J]. Sensors, 2016, 16(9): 1–19.
DOI:10.1109/JSEN.2016.2532218 |
| [5] |
Chenait M, Zebbane B, Benzaid C, et al.
Energy-efficient coverage protocol based on stable and predictive scheduling in wireless sensor networks[J]. Computer Networks, 2017, 127(9): 1–12.
|
| [6] |
Boudali M, Senouci M R, Aissani M, et al.
Activities scheduling algorithms based on probabilistic coverage models for wireless sensor networks[J]. Annals of Telecommunications, 2017, 72(3/4): 221–232.
|
| [7] |
Nene M J, Deodhar R S, Patnaik L M.
Algorithm for autonomous reorganization of mobile wireless camera sensor networks to improve coverage[J]. IEEE Sensors Journal, 2015, 15(8): 4428–4441.
DOI:10.1109/JSEN.2015.2389268 |
| [8] |
Yang X, Wen Y, Yuan D, et al.
3-D application-oriented visual correlation model in wireless multimedia sensor networks[J]. IEEE Sensors Journal, 2017, 17(8): 2583–2595.
|
| [9] |
Gupta S K, Kuila P, Jana P K.
Genetic algorithm approach for k-coverage and m-connected node placement in target based wireless sensor networks[J]. Computers & Electrical Engineering, 2016, 56(1): 544–556.
|
| [10] |
Wang C, Sun E, Tian F.
Optimal coverage algorithm of wireless sensor networks based on particle swarm optimization with coherent velocity[J]. International Journal of Grid and Distributed Computing, 2016, 9(9): 293–306.
DOI:10.14257/ijgdc |
| [11] |
Zhang K, Duan C, Jia H.
Genetic simulated annealing-based coverage-enhancing algorithm for multimedia directional sensor networks[J]. International Journal of Communication Systems, 2015, 28(9): 1598–1609.
DOI:10.1002/dac.v28.9 |
| [12] |
Chen C P, Mukhopadhyay S C, Chuang C L, et al.
A hybrid memetic framework for coverage optimization in wireless sensor networks[J]. IEEE Transactions on Cybernetics, 2015, 45(10): 2309–2322.
DOI:10.1109/TCYB.2014.2371139 |
| [13] |
Yang X S, Deb S. Cuckoo search via lévy flights[C]// Nature & Biologically Inspired Computing. Coimbatore: IEEE, 2010: 210-214.
|
| [14] |
Ye F, Qi W, Xiao J.
Research of niching genetic algorithms for optimization in electromagnetics[J]. Procedia Engineering, 2011, 16(1): 383–389.
|