k重覆盖设置算法的百分比覆盖研究*

费 娟,刘桂英,刘 瑶

(岭南师范学院信息工程学院,广东 湛江 524048)

无线传感器网络WSN(Wireless Sensor Network)由大量的传感器节点自组织网络而构成,已广泛应用于军事应用,环境科学,医疗健康,空间探索,家庭安保等领域[1]。由于节点的电源能量受限,在网络覆盖质量得到保障的前提下,如何高效地利用有限的能量资源,最大化地延长网络的生命期一直是无线传感器网络的一个重要研究方向。延长无线传感器网络的生命期主要有以下几种办法:①优化网络工作方式[2];②对通信数据进行压缩聚合等处理[3];③优化拓扑结构和网络路由[4];④优化汇聚节点(Sink node)部署[5];⑤移动充电等新技术[6]。k重覆盖设置(SETk-cover)通过优化网络工作方式,对无线传感器网络的覆盖集进行睡眠调度,来达到降低网络干扰,提升网络生命期的目的。

针对无线传感器网络高密度随机节点部署所带来的冗余性问题,研究人员提出以节点覆盖集轮流工作休眠的方式来实现节能、抗干扰的目的。SETk-cover 算法从部署节点集合中找出k组互不相关的节点子集,每个子集均可独立完成对网络的通信覆盖,子集间轮流工作,其他子集处于低功耗的睡眠状态,通过这样的方式可将网络的生命期延长至大约k倍。当前SETk-cover问题的研究大多基于子集对网络的区域覆盖,要求目标区域中的每一点要被节点完全覆盖,而完全覆盖在实际应用中有时是不可实现或者不必要的:一方面,SETk-cover适用于随机高密度节点部署场景,而随机部署很难保证投掷出去的节点能够覆盖到目标区域的每一寸角落,同时网络工作过程中会不断的出现故障节点以及能量耗尽的节点,这进一步增加了完全覆盖的难度;另一方面,某些应用场景并不需要完全覆盖,如环境监测、天气预报、智慧农业等。有学者提出部分覆盖[7](partial coverage)和百分比覆盖[8](percentage coverage)的概念,其目的是在满足监测百分比精度要求的情况下,令更多的节点进入休眠状态,从而保存能量,延长网络的生命期。

针对SETk-cover的研究始于本世纪初,文献[9]提出了一种基于贪婪算法的启发式算法MCMCC,用于解决高密度随机部署中冗余节点的覆盖集轮流调度问题,SETk-cover的概念首次被提出。此后,学者们陆续提出用不同的算法来解决SETk-cover问题,如整数规划算法[10]、Memetic算法[11]、遗传算法[12]、蚁群算法[13]、N人纸牌游戏算法[14]、时变对数线性学习算法[15]等,研究者们在SETk-cover问题上给予了持续的关注,但是研究成果多针对算法本身,对于实际应用中可能会遇到的一些实际问题缺少后续跟踪研究。部分覆盖、百分比覆盖的概念提出后,有不少研究者致力于通过研究部分覆盖来进一步提升网络的生命期,但是这种研究一般只是针对一个子集覆盖的研究,鲜有将部分覆盖应用于SETk-cover中的研究。SETk-cover的研究文献[9-15]均基于区域覆盖的全覆盖,覆盖的判定通常采用传感区域划分法和网格法,若采用传感区域划分法进行百分比覆盖研究,将会给网络建模带来很大的困难,而对于网格法,对目标区域的百分比覆盖可以转化为网格顶点被覆盖的百分比,覆盖的分析建模将比较方便。文献[12]采用了网格法进行网络的覆盖,本文对文献[12]的算法进行改进,提出一种以覆盖和生命期为目标的SETk-cover算法,以网络子集的连通度作为约束条件,要求节点子集在保证连通度的前提下,满足给定的百分比覆盖目标。

1 系统模型及问题描述

1.1 感知模型

节点的感知模型是研究无线传感器网络覆盖性问题的基础,通常分为确定型和概率型两类,最常见的布尔模型(Boolean sensing model)属于确定型感知模型,概率型感知模型则包含了考虑障碍物等地理面貌的Shadow-fading模型,以及考虑目标探测点和节点传感器间距离长度影响的Elfes sensing模型[16]。

不同的感知模型决定了覆盖度的不同算法,式(1)是布尔模型感知能力的计算公式:

(1)

式(1)表明:布尔模型中,若探测点落在节点感知半径范围内,则感知能力为1;若探测点落在节点感知半径范围外,则感知能力为0。布尔模型定义简洁、易于建模且应用广泛,本文算法的感知模型采用了布尔模型。

1.2 覆盖模型

SETk-cover问题中,覆盖判断常通过子区域判断的方式进行,目前常见的子区域划分方式有传感区域划分和网格划分两种,本算法采用了网格法来进行覆盖情况的判断。

如图1所示,目标区域是一个L×W的矩形区域,网格法将目标区域用平行于x轴和平行于y轴的一系列等间距直线划分成一个个的网格,网格间的距离称为粒度d,由期望的覆盖判断精度所决定。

图1 粒度为d的网格判断网络覆盖的实例

网格法的覆盖判定规则是:以网格为单位对覆盖进行判断,当一个网格的4个顶点均处于被覆盖范围时,判定该网格属于被覆盖区域。当目标区域以及网格的粒度d确定后,可以求得网格的各个顶点坐标,通过计算网格顶点和各传感器之间的距离可以判断出各顶点被覆盖的情况,进而计算出被覆盖的网格数。SETk-cover的百分比覆盖模型中,节点子集所覆盖的网格数量与总网格数之比即覆盖的百分比。以图1为例,被覆盖的网格数为阴影区域的网格数目141,总的网格数为25×16=400,则覆盖的百分比为p=141/400=35.25%。显然计算出的p值和实际的覆盖情况之间存在误差,可通过减小网格粒度d来达到误差要求,代价是算法运行时间的增加。

覆盖和连通度是无线传感器网络最基本的两个问题。如图2(a)所示,当满足全覆盖时,任意节点和相邻节点之间的最短距离一定小于等于2Rs,只要节点的通信半径Rc大于每个节点的最短通信距离,即满足Rc≥2Rs,就可以构成连通的网络,不需单独考虑连通度的问题[17]。图2(b)所示的百分比覆盖场景中,节点间的距离不再受限于2Rs,因此必须单独考虑网络的连通度问题。

图2 全覆盖和百分比覆盖的节点连通性实例

根据无线传感器网络自组网络的特性可知,对于覆盖集Ci中的任意一个节点Si,若网络连通,则需满足Si和其他节点的最短距离min(Di,j)应小于等于节点的通信半径Rc,即满足式(2)。

min(Di,j)≤Rc,

(2)

SETk-cover问题中研究百分百覆盖,要将式(2)所对应的连通度条件作为一个约束条件在算法中实现,从而保证网络的连通度。

1.3 问题描述

N个感知半径为Rs的传感器节点S1,S2,…,SN随机部署在长为L,宽为W的矩形区域内,假设该无线传感器网络具有以下性质:①所有传感器节点随机部署后为静止状态;②可以通过定位技术确定每个节点的位置;③相对于节点的感知覆盖范围,目标区域的面积足够大,边界效应可以忽略;④节点采用布尔感知模型,网络采用网格覆盖模型;⑤无线传感器网络为同构网络,所有节点(不包括Sink节点)具有相同的参数和初始条件,节点的最大通信半径Rc和感知半径Rs无特定关系;⑥网络无时钟同步的要求。

无线传感器网络满足上述条件时,本文研究的问题表述如下:目标区域中,给定覆盖百分比的目标概率p,要求将N个节点安排在k个互不相交的子集内(k值要尽可能大),使得每个子集都能够对目标区域进行p百分比覆盖并保证网络连通可用。

2 算法实现

2.1 算法思想

XM HU和J Zhang等人提出的STHGA算法[12]是一种基于全覆盖的SETk-cover算法,在简单遗传算法的基础上引入了前向编码和冗余调度,实验结果表明该算法是目前串行算法中求解成功率和求解效率都非常高的一种算法,且算法在不同网络规模下的表现稳定。本文对文献[12]的算法进行改进,将全覆盖模型改为百分比覆盖,同时将网络的连通度作为约束条件在算法中实现。

2.2 算法步骤

为了更好地说明算法的实现过程,将算法的步骤做如下说明:

Step 1 群体初始化

算法的染色体长度对应节点的个数,基因取值对应于覆盖子集编号,染色体的初始化过程使用了前向编码方案,对于染色体ci=(gi1,gi2,…,giN),gimax=max(gi1,gi2,…,giN),前向编码方案要求互不相交的子集C1,C2,…,Cgimax-1中每个子集都能够对网络实现给定指标p的百分比覆盖,而Cgimax对网络的覆盖要求满足与否是不确定的。举例来说,染色体ci=(1,2,1,1,3,2,1,2,2,3)表示当前有10个节点,节点子集C1={S1,S3,S4,S7},C2={S2,S6,S8,S9}可分别对网络进行百分比覆盖,C3={S5,S10}对网络的覆盖情况仅从染色体ci无法判断。初始化时,染色体c1=(1,1,1,…,1),基因取值全部置1。染色体c1的基因取值全部置1表示所有节点全部激活,此时若网络不能满足覆盖要求,算法结束;若此时网络可以满足覆盖要求,则在染色体c1中随机选取K1个基因,若对应的节点是冗余节点,则基因取值自增1构成其他染色体,进而形成初始化群体。

Step 2 适应值评价,保存最优染色体

文献[12]的适应度函数定义为:

fi=ω1(gimax-1)+ω2Pgimax

(3)

式中:ω1,ω2是定义的权重参数,gimax-1表示满足覆盖条件的子集数目,Pgimax表示不能满足覆盖条件的子集的网络覆盖率。显然,算法寻找最大适应度函数的过程就是不断增加覆盖子集的过程。

在百分比覆盖环境下,为了在算法中提供连通度的保障,本算法提出可变参的适应值函数,当染色体所对应的节点子集C1,C2,…,Cgimax-1满足连通条件式(2)时,则ω1=1,ω2=1否则ω1=0,ω2=1,即本算法的适应值函数定义为式(4)

(4)

将连通条件加入到适应值函数中,所保存的最优染色体不仅能满足最大覆盖集个数下的覆盖条件,而且还可以保证网络的连通度。

Step 3 重组/选择

重组实际上就是适应前向编码方案的交配过程,它和选择过程组合在一起期望通过染色体的互动产生更好的种群。

Step 4 变异

变异操作仅对未能满足覆盖条件的子集所对应的基因进行,由于可能会降低适应度函数,因此每隔Gm代才执行一次。

Step 5 冗余调度

为了加速收敛,文献[12]提供了混合调度、前向调度和关键区调度3个冗余调度模块。百分比覆盖模型下覆盖子集的上限已经不受关键区的约束,因此本算法仅保留了混合调度和前向调度模块。其中,混合调度将节点子集中的冗余节点调往其他子集;前向调度将节点子集中的冗余节点调往不满足覆盖条件的子集,以提高其覆盖率。

Step 6 算法迭代运行,直至结束

算法此后的流程步骤都要遵照前向编码方案的要求,随着算法流程的不断迭代,染色体逼近最优解。通过最佳染色体可以看到求解的各个覆盖子集的情况。

百分比覆盖中,k值的上限不再受限于关键区所覆盖的节点数,因此算法的结束条件也不再受限于关键区覆盖的节点数,本算法的结束条件为最佳染色体400代内没有变化。

4 实验分析

为了评估算法,在Intel(R)Core(TM)i7-7700 CPU @ 3.60GHz,8GB内存,Ubuntu 16.04 LTS 64位操作系统的环境下进行了实验测试。测试的目标区域是50×50的正方形区域,算法的参数设置为popsize=3,pm=0.5,Gm=100,K1=5,K2=5。对节点数量N,节点感知半径Rs,节点通信半径Rc,网络的覆盖百分比p在不同取值情况下进行了多次实验,每一个实验用例测试30次,测试结果取平均值。

测试关注网络参数N,节点参数Rs,Rc,以及覆盖百分比p对无线传感器生命期的影响,即关注在上述参数取值不同的情况下,节点所求得的覆盖集情况以及算法的性能表现。

图3 覆盖子集数量k随节点数目N的变化

当Rs=5,Rc=8以及Rs=5,Rc=20时,算法在满足不同的覆盖百分比的情况下,覆盖子集的数量随节点数N的变化情况如图3所示。从图3(a)、图3(b)可以看出:在同样的覆盖百分比情况下,覆盖集的数量k随网络节点N的增加而增加,这意味着随着网络中节点数目的不断增多,冗余节点增多,构成更多的覆盖子集,网络的生命期增加。图3(a)中,在同样的节点数量下,当0.7≤p≤1.0时,覆盖集的数量随百分比p的降低而增加,但是当p取值小于0.5时,随着覆盖百分比的降低,出现了覆盖集数量减少的情况,这主要是因为受限于连通度的约束条件;同时,覆盖百分比p=0.8时,k值相比于全覆盖的k值增加了近5倍。图3(b)中,在同样的节点数量下,当0.4≤p≤1.0时,覆盖集的数量随百分比p的降低而增加,但是当p取值小于0.3时,随着覆盖百分比的降低,出现了覆盖集数量减少的情况,这主要是因为受限于连通度的约束条件;同时,覆盖百分比p=0.4时候的k值相比于全覆盖的k值增加了十余倍。综上表明,Rc和Rs比值不同的情况下,约束度的影响不同,比值越大,能带来生命期最大化的百分比的最佳值越低,不同场景下根据实际的覆盖要求设定理想的覆盖百分比值,可以显著地延长网络的生命期。

当Rs=5,N=1 000时,算法在满足不同的覆盖百分比的情况下,覆盖子集的数量随节点的通信半径Rc的变化情况如图4所示。从图4可以看出:在通信半径确定不变的情况下,覆盖集的数量随百分比p的降低而增加,受限于连通度的约束条件,当p取值较小时,覆盖集的增速变缓甚至出现下降;同样的测试条件下,k值会伴随Rc的增大而增大,这意味着随着Rc取值的增大,连通性所带来的约束效应减小。

图4 覆盖子集数量k随节点通信半径Rc的变化

当Rc=15,N=1 000时,算法在满足不同的覆盖百分比的情况下,覆盖子集的数量随节点的通信半径Rs的变化情况如图5所示。从图5可以看出:当0.8≤p时,k值会伴随Rs的增大而增大,这是由于Rs的增大使得节点的覆盖面积增大,冗余节点增多,从而可以构成更多的覆盖集;当p≤0.8时,k值和Rs的取值关系不明显,这是由于受约束性条件影响,传感器感知半径增大所造成的覆盖面积增大所带来的覆盖集增加的效应降低。

图5 覆盖子集数量k随节点感知半径Rs的变化

从图6可以看出,算法的FEs曲线虽然在局部会有一些小的震荡,但是总体上FEs的取值随N,Rc,Rs的取值增大而增大。同时,由于算法是概率型算法,因此虽然总体上算法的FEs会随着N值的增加而提升,但是并没有严格遵守这一规律。结合图3～图6来看,当网络的覆盖集数量k增大时,算法的FEs也会随之增大,但是增幅并不成倍。以图6(a)为例,可以看到当覆盖百分比p为0.8时的FEs值相比于全覆盖的FEs值增加了仅约1%,但是覆盖集数量k却增加了近5倍,这说明生命期延长需要的计算资源多,但是生命期延长的效应更明显。同时,受限于连通度的约束条件,当覆盖百分比值非常低的时候,生命期的延长效应会降低,因此在进行覆盖比率选择的时候并非越低越好。

图6 适应值评估度随各参数的变化

5 结束语

通过SETk-cover算法找出多个对网络独立覆盖的集合并进行睡眠调度,可以有效地提升网络的生命期,当前的SETk-cover算法多针对完全覆盖展开研究,本文提出了一种针对百分比覆盖的SETk-cover算法,将连通度作为约束条件,以覆盖和生命期为目标,百分比覆盖下可以让更多的节点进入休眠状态,从而达到节能、抗干扰的目的。实验结果表明,算法在保证网络覆盖质量时能够有效地减少活跃节点的数量,使得覆盖集数量增大,延长了网络的生存时间。受限于连通度的约束,覆盖百分比的生命期延长效应在覆盖比率较低的情况下有抑制现象,算法可为需要进行覆盖比选择的应用场景提供理论最佳数值的参考依据。