一种基于改进蚁群算法的三维K-栅栏覆盖算法

党小超,李月霞,郝占军,张 彤

(1.西北师范大学 计算机科学与工程学院,兰州 730070; 2.甘肃省物联网工程研究中心,兰州 730070)

0 概述

无线传感器网络(Wireless Sensor Network，WSN)中的栅栏覆盖(Barrier Coverage，BC)问题是该领域的研究热点。栅栏覆盖问题是指在特定区(一般为狭长的带状区域)的边界部署若干个传感器节点构建的传感器网络，在入侵监测方面,主要关注入侵目标运动路径的覆盖情况,即考察入侵目标穿越传感器网络时被监测的情况[1]。目前关于栅栏覆盖的研究工作多数基于理想环境下的二维平面,而现实应用场景,比如森林防护方面的火势蔓延的动态监测、水域中对外来物种侵入的监测、化工业方面对污染物扩散程度的监测等,都涉及到复杂地形的三维环境,因此,在三维环境下构建栅栏覆盖具有重要的意义。

目前,栅栏覆盖的研究主要针对构建栅栏、修补栅栏间隙以及在栅栏覆盖中提高节点利用率和降低能耗3个方面。

关于构建栅栏覆盖的相关研究较多。文献[2]通过移动最少数量的传感器,并以最小的能量成本构建K-栅栏覆盖。文献[3]利用匈牙利算法移动节点完成弱栅栏的构建,并对水面栅栏覆盖进行研究,但是弱栅栏容易造成监测事件的丢失。文献[4]利用具有转动能力的移动传感器节点构建强栅栏,但有向传感器节点检测范围有限,不适合全方位监测事件。文献[5]通过构建有向栅栏图对目标栅栏区域进行强栅栏的构建。文献[6]针对具有有限移动能力的传感器节点构建K-栅栏覆盖问题进行了相应研究。文献[7]利用移动节点对已存在的栅栏间隙进行填补,提出基于节点重部署的三维栅栏构建算法。文献[8]提出一种分布式算法,通过分区技术在不规则形状的长条区域中构建栅栏。文献[9]提出针对WSN中存在位置误差时的栅栏覆盖构建方法。

在传感器最初随机部署以及节点工作一段时间后,可能会出现栅栏间隙,这将导致重要事件数据的漏失。为了避免这种情况的发生,有必要进行栅栏间隙的修补。文献[10]研究了有向传感器网络的间隙问题,通过确定性部署提出了SRA和CRA 2种间隙修复算法。文献[11]提出一种协调传感器巡逻算法CSP,通过移动节点监视网络中的各个节点以发现栅栏间隙,从而实现存在栅栏间隙时的最优修补。文献[12]提出一种覆盖间隙修复算法CGR,通过检测网络中的低能量节点,移动该节点周围的可移动节点进行栅栏修复。文献[13]通过移动动态传感器节点来填补栅栏间隙,并与已部署静态无线传感器节点形成强栅栏,从而有效地实现混合WSN中的栅栏覆盖,但所提算法的节点移动能耗并未明显降低。

栅栏覆盖构建算法的性能和栅栏间隙修补的质量可以从节点使用数量和总能耗两方面进行评价。文献[14]通过引入多唤醒的调度机制对节点进行唤醒来降低能耗,进而实现无线传感器网络覆盖性能的优化。文献[4]研究了移动传感器能量消耗与节点感知半径的关系。文献[15]提出随机化部署节点的非线性栅栏,通过减少可移动节点的移动距离,降低整个网络的能量消耗。文献[16]提出一种冗余传感器睡眠调度的分布式协议,该协议无需事先知道节点的物理位置信息,可以减少移动传感器数量。文献[17]通过仿生智能算法布谷鸟搜索进行网络覆盖方面的优化。文献[18]提出当部署的传感器节点密度较大时,在原有节点连通部分的基础上,用贪婪算法和最优匹配算法完成对栅栏间隙的填补,减少使用节点数量,进而实施栅栏的再优化。然而,上述文献研究的是在二维理想环境下的栅栏覆盖,并不适用于复杂的三维环境。文献[19]将三维平面二维化,利用贪婪算法对目标区域进行覆盖,但该研究是针对区域覆盖方面的研究,并不适用三维环境下的入侵监测研究。文献[20]通过随机部署节点,利用差分进化算法对其进行优化,实现对监测区域的覆盖,但该方法是对三维区域进行覆盖,并不能实现栅栏覆盖相对应的入侵监测。

为更好地实现对实际三维环境下的入侵监测,本文提出一种三维蚁群优化(Three Dimensional Ant Colony Optimization,3D-ACO)算法,用以构建三维栅栏覆盖。将三维区域二维网格化,计算网格梯度并引入空间权重和部署方向角,采用3D-ACO算法构建栅栏,利用移动节点进行栅栏间隙填补,进而提高节点的利用率并降低网络能耗。本文使用混合无线传感器网络,并且所用的传感器均为全向感知传感器。

1 全向强栅栏覆盖模型

1.1 节点感知模型

本文所用的传感器节点感知模型为全向感知模型,如图1所示。图1(a)为节点p在三维环境下的感知模型,以三元数组表示,其中传感器节点的位置坐标用pi(xi,yi,zi)表示,r为节点的感知半径,θ为节点的部署方向角,q为入侵对象,q在p节点感知范围内。图1(b)为节点在二维下的感知模型。

图1 全向感知模型

受物理地貌因素影响,三维环境相对较为复杂,存在比较陡峭的坡峰,随机部署会造成一定数量节点的浪费,致使节点利用率不高。蚁群算法在复杂路线中能够寻找最优路径,但传统的蚁群算法不适用于在三维环境下构建栅栏覆盖,且存在容易陷入局部最优解的问题。本文在待部署区域D中随机抛撒节点,将部署区域进行网格划分并引入网格梯度,通过空间权重和部署方向角来改进传统的蚁群算法,从而减少部署节点数量,并降低其部署难度。本文假设WSN中传感器节点为同构节点,即所有节点的移动能耗、感知半径、感知范围均相同。在对全向无线传感器网络强1-栅栏构建问题分析之前做出如下定义:

定义2(节点感知范围) 节点的感知模型为概率感知模型,即节点感知入侵者的概率随着入侵者和节点之间的距离增加而减小,如图1(b)中节点感知范围内任意一点q,节点p能感知到点q的概率Pq为:

其中,c为常数。

定义3(节点运动能耗) 节点的移动距离和单位移动能耗的乘积。

定义4(环形强栅栏覆盖) 如果监测区域是理想的平坦地面,则构建的栅栏近似于直线,如图2(a)所示。当监测区域为三维环境,且存在陡峭坡峰(图2(b)中阴影部分)时,构建的栅栏如图2(b)所示,称为环形强栅栏。平坦地面上的K-栅栏构建是三维环境下环形K-栅栏构建的一种特殊情形。

图2 强1-栅栏覆盖示意图

1.2 网格梯度划分模型

假设需要部署栅栏覆盖的三维复杂环境是长为L、宽为W的丘陵地带,受地物地貌因素影响,若存在较陡峭的坡峰,随机部署会造成节点浪费。针对上述问题,本文通过网格梯度来限制蚂蚁走向。网格梯度用来表示映射在二维平面方格上三维环境的陡峭程度。该方法对部署节点不再是强行部署,而是采用划分网格,并计算其梯度大小来选择部署路径的走向。在混合WSN中构建强1-栅栏时,本文将部署区域划分成若干个网格,不同网格的三维高度存在差别,使用沿坡面上任一方向上高度变化的程度表示网格梯度,其中一个网格的坡度与方向梯度如图3所示。

图3 坡度与方向梯度示意图

本文定义φ为沿ψ方向的方向梯度角,阴影部分为传感器节点p的感知范围,h表示坡面的垂直高度,l表示水平距离,两者之比为坡度,用i表示。ϑ为坡面与水平面的夹角。

(1)

传感器节点p所在网格坡面沿ψ方向的网格方向梯度g为:

(2)

其中,h(x,y)为坐标(x,y)处的高程,ψ表示与坡向的夹角。当ψ=0时,梯度和坡度相等。

计算出划分后的每个网格的网格梯度,放入网格梯度集合G中,据此引入空间权重。

如图4所示,地形高低由颜色从浅到深表示,白色节点为不可移动的静态节点,黑色节点为可移动的动态节点。假设已经获知节点pi位置坐标为(xi,yi,zi),随机抛撒节点,执行3D-ACO进行栅栏覆盖的构建,如图4(a)所示。之后通过移动节点填补栅栏间隙,如图4(b)中箭头所示,方格表示蚂蚁在构建栅栏时,栅栏间隙处的待填补节点位置。改进的蚁群算法在构建栅栏的过程中根据已经加入的空间权重和部署方向角选择下一跳传感器节点。当部署区域内不存在满足条件的节点时,算法会寻找最优的网格作为待填补虚拟节点位置,该位置将被标记,下一条栅栏构建不会重复选取该网格作为部署路径。

图4 栅栏构建示意图

2 3D-ACO算法

传统的蚁群算法通过蚂蚁个体间信息的传递,多个蚂蚁共同协作,从而寻找蚁穴到食物的最短路径。本文提出一种适用于三维环境下的蚁群算法3D-ACO,通过引入空间权重和部署方向角度,限制蚂蚁的活动方向,使其适用于三维环境下的栅栏构建。将三维待部署区域二维网格化,计算出各个网格梯度,根据网格梯度大小由小到大排序,从当前节点遍历所有节点,随后随机抛撒m个节点,执行3D-ACO算法。考虑到构建栅栏为强栅栏和节点的感知范围可能受环境影响,节点的真实半径有所不同,所以,该算法限制蚂蚁的移动能力,并在无合适节点的位置留下虚拟节点位置,再通过移动节点填补栅栏间隙,以确保构建强栅栏。3D-ACO算法框架如图5所示。

图5 3D-ACO 算法框架

2.1 蚂蚁移动能力的限制

为了构建三维环境下的强栅栏覆盖,需要对蚂蚁的移动能力进行一定程度上的限制。这是因为WSN的强栅栏覆盖为防止不丢失事件监测,要求相邻节点间无间隙存在,即2个节点感知范围内一定存在重叠部分。若节点A和节点B为构建的栅栏覆盖中两相邻节点,则d(A,B)<2r。又因本文部署环境是三维山丘陵,所以传感器部署后的理想感知范围与实际感知到的范围定会存在差距。已知理想探测半径r,设Rr为节点实际感知半径,为保证3D-ACO算法构建的是强栅栏,则有以下定义:

定义5蚂蚁移动距离小于等于2Rr。Rr=rcos[arctan(icosψ)]。

假设传感器节点所在网格范围可近似看作坡度和坡向近似相同的理想坡面,如图3所示,g表示沿ψ方向上的网格梯度,计算公式为:

g=tanφ

(3)

由式(1)和式(3)可知:

g=icosψ

(4)

由于地形影响,Rr和r在ψ方向的存在以下关系:

Rr=rcosφ

(5)

将式(3)、式(4)代入式(5),得:

Rr=rcos(arctang)=rcos[arctan(icosψ)]

(6)

当ψ=0时,φ=ϑ,则Rr=rcos ϑ,即:

Rr=rcos[arctan(icosψ)]

(7)

为构建强栅栏,相邻节点感知范围一定存在重叠部分。为了保证所构建栅栏为强栅栏,本文限制蚂蚁的移动能力为2Rr,当没有合适节点时,则选定相应填补节点位置,继续选择下一跳节点。

2.2 启发因子优化

本文通过引入空间权重和选择方向角来改进蚁群算法。在监测区域内随机抛撒传感器节点,蚂蚁首先从左边界开始出发寻找最优路径,通过选择方向角和空间权重来优化蚂蚁寻找路径。下面给出空间权重和部署方向角的相关定义,以及优化函数的详细介绍。

定义6(空间权重) 以起始节点为水平面,给待选择路径上的网格赋予不同的权值,称为空间权重。

定义7(部署方向角) 在部署区域D的二维平面内,当前节点与下一步要选择的节点之间的连线和水平方向的夹角。

下面给出空间权重和部署方向角的优化步骤。

1)空间权重

本文利用网格方向梯度引入的空间权重来作为蚁群算法的另外一个启发信息。将集合G中各个网格上的节点求出权重,空间权重用κij表示,蚂蚁选择下一路径时的选择概率将会受到空间权重的影响,即空间权重值κij越大,状态转移概率就越小。

(8)

其中,gmax表示最大梯度值,即梯度阈值。当节点所在网格梯度比梯度阈值大时,则重新选择节点。如图6所示,节点A与节点B的坡度夹角为为ϑ1,节点A和节点C的坡度夹角为ϑ2,节点A和节点C的网格梯度分别为g1和g2。当gmax>g1>g2时,κ1>κ2。将空间权重转化为启发因子以改进传统蚁群算法,对于蚂蚁选择路径而言,空间权重越大,则该条路径的选择概率也相应地变大,即当从节点A选择下一步路径时将选择坡度较平缓的节点B作为下一步选择。

图6 基于空间权重的节点选择

2)部署方向角

引入空间权重启发因子是为了使ACO算法适用于三维环境下构建栅栏。由于蚂蚁选择路径时所依赖的只有当前节点的pi选择下一节点pj的期望程度和路径的信息量强度,但这可能使得算法陷入局部最优解,因此本文引入传感器节点的选择方向角作为蚁群算法的另外一个启发信息。当θ越小时,θij越大,状态转移概率也越大。

(9)

如图7所示,0≤θ≤π表示节点的部署方向。当θ=0且所选下一跳节点所在网格的竖直方向梯度均相同时,节点部署方向为水平方向是最佳的下一跳节点位置。节点A与节点B在二维环境下的夹角为θ2,节点A和节点C在二维环境下的夹角为θ1,由式(9)可知,当节点A选择下一步路径时将选择节点B作为下一步选择。

图7 基于部署方向角的节点选择

根据式(8)和式(9),状态转移概率做如下更改:

(10)

式(10)代表在t时刻蚂蚁k由城市i转移到节点j的转移概率。

2.3 间隙填补

在有向节点模型中,节点不仅需要移动,还有可能需要转动,因此,节点的能量消耗由转动和移动能量消耗组成。在本文中,节点采用全向感知模型,所消耗能量仅为移动节点的消耗。如图8所示,在节点移动至待填补位置的过程中,希望总能耗最小,故而选择与待填补位置的距离最小的节点进行移动。

图8 栅栏间隙填补示意图

由节点位置以及待填补位置的坐标和网格梯度,可以求得移动节点的移动距离。对于所有的传感器节点,可以根据距离目标位置的远近选择节点进行移动填补。关于能耗部分将在实验仿真进行详细分析。

2.4 栅栏构建过程

在传统蚁群算法中,蚂蚁选择下一节点仅依赖τij和ηij2个因素,这可能会使节点陷入局部最优解。因此,本文引入节点的空间权重和部署方向角来限制信息素浓度和选择下一跳节点路径的期望程度对蚂蚁选择概率的影响,并利用移动节点填补栅栏间隙确保构建强栅栏。随机抛撒节点之后,划分网格,不同的节点所在位置高低不同,即空间权重不同,蚂蚁从左边界开始寻找最优路径,当遇到不同的路径时,通过改进的蚁群算法选择最优路径。当没有可选择节点时,记录待填补间隙位置,之后进行移动填补。假设蚂蚁从头出发,根据优化后的信息寻找最优路径,以构建强栅栏,具体步骤如下:

步骤1在待部署区域D中随机抛撒n个节点,划分网格,并记录节点位置和所在网格。

步骤2计算节点所在网格的网格梯度将其作为节点的空间权重κij,计算节点间的夹角引入部署方向角θij。

步骤3将上述2个因子加入蚁群算法,执行3D-ACO算法,开始遍历传感器节点。

步骤4遍历所有节点,更新信息素,并记录间隙位置。

步骤5算法迭代,输出节点使用数量最少的栅栏以及各节点位置。

步骤6判断节点间距离d<2Rr,若是,继续遍历下一节点;否则,执行步骤7。

步骤7选择距离间隙最短移动距离的节点,进行节点填补。若未到达终点,执行步骤6;若到达终点边界,结束栅栏构建。

2.5 3D-ACO算法性能分析

1)能耗分析

本文构建栅栏所用节点需要消耗能量主要分为:节点发射信息的能量消耗es,接收信息后处理信息的能量消耗eb,节点发射信息到节点接收信息之间的能量消耗el,移动节点所需要的能耗Jt,其中,el和Jt主要由节点间距离决定。全部能量消耗计算公式为:

Et=es+eb+el+Jt

(11)

传统蚁群算法、本文3D-ACO算法的总能耗分别用式(12)和式(13)表示。

(12)

(13)

同理,当节点与之前节点高度差不同(空间权重κij不同),其他条件相同时,在蚂蚁选择下一跳节点趋于直线的概率方面,两算法相比有:

因此,本文算法所构建更趋向直线且平缓的栅栏覆盖,也即两蚁群算法中选择下一跳节点总距离有:

∑d1ij>∑dij

用式(12)减去式(13)得到:

EACO-E3D-ACO=(N1-N)es+(Q1-Q)eb+

(14)

在节点发射信息方面,传统的蚁群算法与3D-ACO算法都是由节点自身广播信息,所以,3D-ACO算法相较于传统的蚁群算法并未增加能耗。同理,节点接收信息并处理信息时也未增加能耗,故可以忽略这两部分能耗。现在只考虑节点移动能耗,以及节点发射信息到节点接收信息之间的能量消耗el,而这两部分能耗主要与节点移动距离有关系。由于传统的蚁群算法中∑d1ij要大于3D-ACO算法中的∑dij,因此式(14)大于0。所以,3D-ACO算法要比传统蚁群算法能耗低。

2)收敛速度和局部最优问题

传统的蚁群算法前期由于信息匮乏,收敛速度较慢,而且其选择下一跳节点时倾向于选择距离最近的节点,容易陷入局部最优解。本文算法通过网格划分,引入空间权重和部署方向角,提前排除不适用下一跳节点选择的节点,以减少迭代次数,提高收敛速度,并且结合空间权重和部署方向角选择更适合构建栅栏覆盖的下一跳节点,避免陷入局部最优问题。因此,在三维环境下,本文3D-ACO算法性能更优。

3 仿真实验

本文仿真实验部署区域为300 m×200 m的矩形区域。随机抛撒传感器节点数量n,传感器节点感知范围均为球体,且节点具备移动能力,本文对监测区域进行强2-栅栏构建的仿真实验。若无特别说明,实验参数值均以表1所示参数为准,仿真实验结果均取100次随机实验平均值,迭代次数定为300。

表1 实验参数

本文从节点的自身因素出发根据节点感知半径的不同进行比较,此外,选取strong optimal和strong greedy 2种算法进行仿真实验比较,并参考其实验数据。在下文实验中,节点数量为原抛撒节点数量,所用节点数量是构成栅栏的节点数量,节点总能耗为全部节点消耗能量,节点平均能耗为总能耗与所有节点数量的比值。

3.1 感知半径对结果的影响

传感器节点的感知范围随着其感知半径变化而变化,本文选取了不同感知半径的传感器节点进行仿真实验,并对引入空间权重和部署方向角的3D-ACO算法进行性能分析,结果如图9～图11所示。

图9 节点感知半径对节点总能耗的影响

图10 节点感知半径对节点平均能耗的影响

图11 节点感知半径对所用节点数量的影响

从图9可以看出,节点总的能量消耗随着节点感知半径的增加而减小。这是由于随着节点感知半径的增加,节点相应的感知范围也增加,移动节点移动距离相应减少,进而使得传感器节点总能耗降低。

从图10可以看出,随着传感器节点感知半径的增加,传感器节点平均能耗逐渐降低,随后趋于平缓。这是因为总能耗降低,而总节点数量不变,进而使得节点的平均消耗能量降低。

从图11可以看出,随着传感器节点感知半径的增加,传感器节点使用的数量降低。这是因为传感器节点半径的逐渐增大,缩小了节点之间的部署方向角,此外,由于空间权重优化因子的优化,栅栏构建更为平缓的栅栏覆盖,构建栅栏使用节点个数减少。

3.2 节点数量对结果的影响

在保证强栅栏可以构建的前提下,尽可能地减少节点的使用数量以对比相关算法的优劣。strong optimal和strong greedy算法对于节点数量有一定的要求,因此本文实验节点数从100开始,以20为梯度值增加,直至200。节点总能耗、平均能耗以及构建栅栏节点使用数量的结果如图12～图14所示。

图12 节点数量对节点总能耗的影响

图13 节点数量对节点平均能耗的影响

图14 节点数量对形成栅栏所需节点个数的影响

从图12和图13可以发现,3种算法的总能耗与传感器节点的平均能耗均随着抛撒节点数量的增加而明显减少,在同样的节点数量情况下,3D-ACO算法的总能耗和节点平均能耗则明显地低于其他2种算法。这是因为随着部署区域内传感器节点密度变大,节点空间距离缩小,所以构建栅栏时节点移动距离减少,故而使得总能耗降低。随着总能耗的降低,而节点数量增加,平均能耗也降低。从图14可以看出,在构建栅栏过程中,3种算法使用传感器的数量随抛撒节点的增加而变多,最终趋于平缓。这是因为随着节点数量的增多,算法会选择更加平缓的路径,但随着迭代次数的增加,最优的路径将会被确定。同时还可以看出,3D-ACO算法使用节点数量明显低于其他2种算法的节点数量,且增加趋势更为平缓。这是因为3D-ACO算法通过空间权重和部署方向角对蚂蚁寻找节点的限制,所以在构建栅栏覆盖时,更倾向于选择空间距离小、署方向角度小的栅栏覆盖路径。

3.3 栅栏数量对结果的影响

本文在同一部署区域的不同栅栏数量K的情况下,对节点总能耗、平均能耗、需求的总节点数进行比较,结果分别如图15～图17所示。

图15 栅栏数量对节点总能耗的影响

图16 栅栏数量对节点平均能耗的影响

图17 栅栏数量对形成栅栏所需节点个数的影响

从图15和图16可以看出,随着构建栅栏数的增加,所需传感器节点变多,因此移动节点消耗总能耗变大,其平均能耗也在增长。但3D-ACO算法的总能耗和平均能耗相较于其他2种算法越来越小。

从图17可以看出,在构建相同数量的栅栏情况下,3D-ACO算法所需的节点数远低于其他2种算法,例如当栅栏数K=6时,3D-ACO算法仅需要90个节点左右,其他2种算法则需要120个节点左右。这是因为3D-ACO算法栅栏的构建存在栅栏重叠的可能,这种情况在第2节中就已经介绍。所以栅栏覆盖构建过程中随着栅栏条数的增多,栅栏交叉的几率增大,节点使用数量减少。

4 结束语

本文提出一种基于改进蚁群算法的三维K-栅栏覆盖算法。引入空间权重改进蚁群算法使其适用于三维栅栏构建,利用部署方向角防止蚁群算法陷入局部最优,同时通过限制蚁群的移动能力以及移动节点填补栅栏间隙以确保强栅栏的形成。仿真实验结果表明,3D-ACO算法在三维环境下部署栅栏时,可有效提高节点使用率,并且所构建的栅栏具有较强的自适应性。由于本文算法基于全向感知节点,下一步将针对在三维环境中有向无线传感器网络的栅栏覆盖问题进行研究。