异构WSNs中节点稳定匹配的覆盖空洞修复优化算法*

苟平章,毛 刚,李凤珍,贾向东

(西北师范大学计算机科学与工程学院,兰州 730070)

覆盖空洞修复是衡量异构无线传感器网络HWSNs(Heterogeneous Wireless Sensor Networks)性能的重要指标之一,反映了一个区域被“感知”程度的优劣[1-3]。在实际应用中,由于网络初始节点随机部署,节点能耗不均或受周围复杂情况影响,造成节点失效,目标无法被有效监测,网络出现覆盖空洞,导致感知信息的不完整,造成网络通信不顺畅,影响整个网络的性能。因此,如何对覆盖空洞进行及时有效的感知并修复,是异构无线传感器网络亟待解决的基本问题。

许多中外文献对WSNs覆盖空洞修复方法进行了研究,文献[4]提出基于Voronoi图分布式本地DHD(Deployment Algorithm for Hole Detection and Healing)算法发现覆盖空洞,当两个移动节点距离太靠近时相互排斥,距离太远则相互吸引,移动节点整体的合力确定移动的方向和距离。文献[5]提出基于Voronoi覆盖空洞修复算法EECHS(Estimation and Enhancing of Coverage Holes Strategy),随机部署的节点将监测区域划分为若干Voronoi,再分割为若干三角形并结合相邻节点生成的Voronoi找到覆盖空洞位置,连接节点与相邻公共边两端点形成一个夹角,在夹角平分线上找到最优空洞修复点,但算法复杂程度较高且修复后节点冗余较大。文献[6]提出一种三角形网格空洞修复方法,利用ATN(Advanced Triangle Net)算法检测节点与其邻居节点构成的三角形网格是否被完全覆盖,若没有完全覆盖则利用TNR(Triangle Net Recovery)算法通过向三角形网格特定位置添加节点使三角形网格达到完全覆盖,该算法无需地理信息支持,但修复精度不够,需要填补大量节点。文献[7]提出一种基于极坐标的最小能耗覆盖空洞修复算法,虽然算法有效减少移动修复节点个数,延长网络生存周期,但空洞模型过于理想化,不适用于复杂节点分布环境。文献[8]提出了最短k覆盖区段和最长的k未覆盖区段,但计算和交通量非常大。文献[9]基于Voronoi图划分无线传感器网络高覆盖度和节点移动最小化的问题,引入贪心算法和匈牙利算法求解最优解,不同传感器节点负载更加均衡,网络生存周期增长。文献[10]提出一种基于泰森多边形形心的覆盖策略BCBS(Blind-zone Centroid-based Scheme),将多边形的几何中心作为节点移动的候选目标位置,移动节点移动到候选目标位置,进行空洞修复。文献[11]提出的 VABC(Voronoi Artificial Bee Colony)算法通过Voronoi多边形确定覆盖盲区,盲区产生蜜源指导引领蜂搜寻,最优蜜源处即为移动节点最优部署位置,该方法收敛速度慢,容易造成局部最优解。文献[12]提出一种基于树和图论的方法探测和修复覆盖空洞,将大的空洞分为若干小的空洞逐个修复。文献[13]提出一种基于全向传感器栅栏分区构建算法FCOIS(Fence Construction for Omnidirectional Isomorphism Sensor Based on Subarea),根据节点初始随机分布情况划分子区域,采用贪婪算法对每个子区域内按序构建栅栏形成的空隙进行填充。文献[14]对节点执行若干次迭代,以实现满足初始随机分布的覆盖范围的最终均匀分布,但收敛时间相应地更长。文献[15]提出MNCO(Mobile Node’s Optimization Strategy)算法,在混合传感器网络中,采用基于误警率的概率探测模型,计算节点的联合探测概率寻找覆盖空洞,但未对节点具体的移动方向进行优化。文献[16]提出一种改进的C-V(Chan-Vese)模型计算出覆盖空洞的数量和大小,改进粒子群算法的适应值函数达到网络覆盖优化的目的。

本文提出一种节点稳定匹配的覆盖空洞修复优化算法ROA-NSM(Repair Optimization Algorithm for Node Stable Matching),该算法采用延迟匹配策略建立基于优先级的移动节点与虚拟修复节点之间的对应关系,并给出具体的节点优先级计算方法,通过对初始的匹配结果进行预剪枝加快算法收敛速度。首先,对目标监测区域随机分布的静态节点进行Voronoi多边形划分,采用联合感知模型判断多边形区域中是否存在覆盖空洞;其次,计算空洞节点形成Delaunay三角形的形心,利用形心与节点距离确定虚拟修复节点位置;最后,建立基于优先级的节点稳定匹配关系,根据匹配结果完成空洞修复。仿真结果表明,ROA-NSM算法加快节点匹配收敛速度,减少了匹配次数,在保证网络覆盖率的同时降低了移动节点的移动距离,验证了该算法在空洞修复上的可行性。

1 系统模型

1.1 异构网络模型假设

无线传感器网络中,异构节点被随机部署到目标区域执行监测任务,为保证后续工作的开展。本文假设采用如下网络模型:

假设1利用定位技术,网络中所有节点具有自定位能力,静态传感器节点部署后不再移动。

假设2所有节点有相同的计算能力、通信能力、相同且有限的初始能量和自身唯一标识ID。

假设3节点通信半径Rc为感知半径Rs的两倍,节点感知范围和通信范围都是以节点位置为圆心,以Rs、Rc为半径的圆形区域。

假设4某监测区域内一点至少被一个节点有效监测,则该监测点被有效覆盖。

1.2 异构节点感知模型

覆盖空洞问题中,一个区域发生的事件通常会被多个传感器节点同时感测,本文采用Neyman-Pearson模型感知多个节点对目标的联合探测概率[7,16]。假设部署在目标监测区域的所有节点表示为{Si,i=1,2,3,…,n},该感知模型以传感器节点为圆心,感知半径为Rs的圆。考虑目标可能同时被多个节点感知,采用联合感知模型来计算节点感知概率。感知圆监测区域内,任意节点∀j与传感器节点i的欧氏距离为:

(1)

节点i从目标接收到的能量Eri如下:

(2)

式中,Erj为j处发生事件释放的能量,ni表示均值为0,方差为σ2的高斯噪声,γ为感应信号衰减指数,通常取值为2或4,T0、T1分别表示目标存在和目标缺失的情况,β定义为:

(3)

式(3)中,Einit表示节点初始能量。

在T0状态下,Eri的探测概率为:

(4)

在T1状态下,Eri的探测概率为:

采用Neyman-Pearson模型,传感器节点的探测概率PD可表示为[16]:

(6)

式中,α表示误警率,φ(·)为标准正态分布累积分布函数,PD表示在可接受最小误警率α的情况下,目标的最大探测概率。

当点j处于K个传感器节点的感知圆覆盖范围内时,目标点区域内的联合感知概率为:

(7)

网络节点集S的覆盖率定义如下:

(8)

式中,A表示区域面积,S[C(Pn]表示区域节点的覆盖面积,假设S(Pcov)>0.9时,整个监测区域被有效覆盖。

1.3 空洞模型

本文主要研究有界区域内,异构无线传感器网络节点随机部署造成的覆盖空洞问题。网络中20个初始节点随机分布形成的Voronoi多边形如图1所示,各节点区域是距离各个节点距离最近的凸区域,该区域内任一点与任何其他节点之间的距离都大于该点与节点S的距离,相邻区域边上的点到两区域节点的距离相等,图1中点K到节点S1与节点S2距离相等。由于节点随机分布,很容易造成覆盖空洞情况发生,导致区域监测效果达不到预期效果,由20个节点随机分布造成的覆盖空洞如图2所示,仅感知圆区域被有效覆盖,其他区域为覆盖空洞区域,静态传感器节点与Voronoi多边形的距离为:

(9)

V表示Voronoi多边形顶点,S表示静态传感器节点,如果d(s,v)>Rs,则节点S所在的Voronoi多边形区域出现覆盖空洞,多个节点连接在一起,构成一个覆盖空洞区域。

图1 有界Voronoi划分

图2 覆盖空洞模型

2 覆盖空洞修复优化算法ROA-NSM

盖尔-沙普利算法(Gale-Shapley Algorithm)是基于稳定匹配策略而设计的贪心算法,但其双向匹配关系造成算法收敛速度过慢,ROA-NSM算法通过距离阈值函数和能量阈值函数确定节点优先级,对移动节点与虚拟修复节点建立稳定匹配关系,加快算法收敛速度,提高覆盖空洞修复效率。

2.1 虚拟修复节点位置坐标的计算

与Voronoi多边形互为偶图的Delaunay三角形,是与该多边形共享一条边的相关点连接而成的三角形。图3中小黑点为传感器节点,任意3个距离最近的节点构成一个Delaunay三角形,图3中节点{S1,S8,S3,S2,S10}构成一个覆盖空洞区域。图4为空洞修复模型,其中Si为静态节点,Vi为虚拟修复节点,P是三角形S1S2S3的形心。

图3 Delaunay三角形

图4 Delaunay三角形修复模型

Delaunay三角形空洞修复步骤如下:

Step1根据静态节点构成覆盖空洞多边形,找出空洞节点集Sh;

Step2遍历覆盖空洞区域节点集Shi,从任意一个节点出发,以最近的三点构成一个三角形;

Step3计算该三角形形心坐标P(x0,y0),(x0,y0)为三角形顶点的横、纵坐标,点P的计算公式为:

(10)

(11)

Step5顺时针旋转移动到静态节点S2,S3,重复Step 4,完成该三角形区域覆盖;

Step6继续移动到覆盖空洞另一个三角形,重复Step 3～Step 5,完成该覆盖空洞区域覆盖;

Step7继续遍历余下覆盖空洞区域,重复Step 3～Step 6,完成整个网络空洞修复。

2.2 节点优先级排序

通过Delaunay三角剖分计算虚拟修复节点位置坐标,虚拟修复节点与移动节点基于阈值函数f进行优先级排序,f1表示基于移动节点能量的优先级函数,f2表示基于距离的优先级函数,距离越短,优先级越高。阈值函数的大小决定了节点排序的优先级,f越大,节点优先级越高,排序越靠前。

f=f1n1-f2n2

(12)

(13)

(14)

2.3 基于节点优先级排序结果的预剪枝处理

如果网络中存在的虚拟修复节点过多,移动节点与虚拟修复节点邀约匹配时,一个虚拟修复节点的邀约常会被多个移动节点拒绝,为减少邀约过程中节点匹配收敛速度慢的特性,考虑节点能量有限,多次匹配易使节点能耗过多消耗,对节点优先级排序后结果进行预剪枝处理,剪去匹配关系中排名后1/4匹配结果,以加快ROA-NSM算法收敛速度。

2.4 稳定匹配算法执行过程

ROA-NSM算法开始执行时,虚拟修复节点vi向移动节点mi按优先级顺序发出邀约匹配请求,如移动节点mi还未与其他节点匹配,则该虚拟修复节点与该移动节点进行匹配,一旦移动节点处于匹配状态,则一直处于匹配状态,但与其配对的虚拟修复节点是可变的,当收到更好的邀约匹配时,比较这两个虚拟修复节点优先级,选择优先级较大的节点相匹配,另一个虚拟修复节点恢复为未匹配状态。

假设网络中移动节点数mn大于虚拟修复节点数vn,根据vn确定mn的个数,具体步骤如下:

Step1唤醒覆盖空洞周围的移动节点,加入移动节点集T(m,n),式(12)计算每个移动节点与虚拟节点之间的阈值函数f,按f进行优先级排序存入表T(Sm,i);

Step2将虚拟修复节点vi附近移动节点同样按照式(12)进行优先级排序保存至各自的待匹配列表T(Sv,i),f越大,优先级越高,在T(Sv,i)中排序越靠前;

Step3虚拟修复节点向移动节点发出匹配邀约,在其表T(Sv,i)从前往后开始,依次向优先级高的移动节点发出匹配邀约;

采用二分图G=(M,Δ,V)为移动节点与虚拟修复节点的匹配关系建立数学模型。移动节点M={m1,m2…,mn},虚拟节点V={v1,v2,…,vn},Δ表示所有可能边的集合。引入优先秩评定矩阵表示节点的优先级关系[17],该矩阵为n阶方阵,i行、j列元素是数对(p,q),p表示vi对mi的排名优先级,q表示mi对vi排名优先级。稳定节点匹配对应矩阵不同行、列所有位置的集合。一个4阶的优先秩评定矩阵节点优先级匹配关系如图5(a)所示,图5(b)为节点按优先级邀约匹配得到的匹配结果。v1对m1的排名优先级为1,m1对v1的排名优先级为2。

图5 ROA-NSM节点匹配

Step4根据得到的稳定匹配结果,移动节点移动到虚拟修复节点处进行覆盖空洞修复。

基于四个节点的ROA-NSM算法执行步骤为:

Step1v1向m1、v2向m2、v3向m4发出匹配邀约,m4对v3的优先级排名靠后1/4,剪去该匹配关系;

Step2v3向m1发出匹配邀约,m1拒绝v1;

Step3v1向m2发出邀约,m2拒绝v2;

Step4v2向m3,v4向m1发出邀约,m1拒绝v4;

Step5v4向m4发出邀约,匹配完成。

通过ROA-NSM算法完成该优先秩评定矩阵邀约匹配后,稳定匹配结果为:

v1↔m2,v2↔m3,v3↔m1,v4↔m4

因此,虚拟修复节点v1用移动节点m2修复,v2用m3修复,v3用m1修复,v4用m4修复,得到的结果与Gale-Shapley算法相同,但步骤更为精简。

图6(a)是使用ROA-NSM算法,修复由静态节点S={S1,S8,S3,S2,S10}构成一个覆盖空洞第一轮和最后一轮匹配过程。图6(b)表示具体节点修复匹配,图中实线表示虚拟修复节点向移动节点发出匹配邀约,而实际修复关系如图中虚线所示。

图6 节点匹配修复

图7 基于稳定匹配的覆盖空洞修复流程图

2.5 ROA-NSM算法流程及时间复杂度分析

ROA-NSM算法从最理想的角度来说,每个虚拟修复节点刚好与优先级最高移动节点匹配成功,则整个算法只需遍历一次,复杂度为O(n);从最坏的情况来说,每个匹配过的虚拟修复节点后来又被拒绝,匹配了最多n次后才成功匹配,考虑“预剪枝”对算法的影响,时间复杂度不会超过O(n2)。

3 仿真与结果分析

本文采用MATLAB2014a对算法进行验证,假设在200 m×200 m的异构WSNs环境中随机部署100个静止节点和50个移动节点,具体实验参数设置如表1所示。

表1 网络环境与参数设置

图8 覆盖空洞修复前后传感器节点位置分布图

图8为异构WSNs中覆盖空洞修复前后节点分布图。静态节点随机部署完成后,节点位置不再改变,通过移动节点的移动对覆盖空洞进行修复。

图9为ROA-NSM算法节点优先级匹配对应关系,通过距离阈值函数和能量阈值函数对节点进行优先级排序,优先级数值越小,级别越高,ROA-NSM算法对排序结果采用预剪枝剪去优先级列表中后1/4的节点。图9(a)中星号为虚拟修复节点,小圈为移动节点,虚拟修复节点对移动节点发出匹配邀约,星号的纵坐标表示最终接受邀约的移动节点在优先级列表中的排名,小圈的纵坐标表示最终匹配的虚拟修复节点在优先级列表中的排名。从图9(a)中可得,ROA-NSM算法最终匹配结果都是各自列表排名前3/4节点,且小圈总是处于星号的上方;图9(b)横坐标为节点匹配的轮数,纵坐标表示该轮匹配结束后,节点匹配对象在优先级列表中平均优先级,ROA-NSM算法匹配了69次。

图9 ROA-NSM算法节点优先级匹配对应关系

图10为Gale-Shapley算法的节点优先级匹配图,Gale-Shapley算法匹配90次,ROA-NSM算法节点的匹配次数比Gale-Shapley算法减少了23.3%。由虚拟修复节点向移动节点发出邀约得到对虚拟修复节点更有利的匹配结果,虚拟修复节点匹配对象的平均优先级总高于移动节点匹配对象的平均优先级。

为验证ROA-NSM算法的空洞覆盖度,与BCBS和VABC算法进行对比。图11是3种算法迭代次数与覆盖率对比图,随着迭代次数的增加,3种算法网络覆盖率都上升,移动节点移动到最优的位置进行空洞修复。ROA-NSM算法覆盖率总是优于VABC算法,直到18次迭代,ROA-NSM算法网络覆盖度超过BCBS算法,覆盖度达到94.2%,优于其他2种算法。

图10 Gale-Shapley算法节点优先级匹配对应关系

图11 迭代次数与网络覆盖率比较

图12 平均移动距离与网络覆盖率对比图

图12(a)为移动节点数与平均移动距离对比图,将ROA-NSM算法与MNCO算法、C-V算法进行对比,验证提出算法的有效性。3种算法的平均移动距离都随着移动节点数目的增加而减少。ROA-NSM算法采用延迟匹配策略,考虑距离和能量因素,从每个虚拟修复节点的优先级列表中,查找一个最优节点用于匹配修复。图12(b)为移动节点数与网络覆盖率对比图,随着移动节点数目的增加,网络覆盖率增强,当移动节点超过23时,覆盖率超过90%,与C-V,MNCO算法相比,ROA-NSM算法移动节点移动距离分别减少20%和23.1%,覆盖率分别提高1.35%和3.25%。

4 结束语

针对异构无线传感器网络中节点随便部署造成覆盖空洞问题,本文将图论中Voronoi多边形、Delaunay三角形与Gale-Shapley延迟匹配算法相结合,考虑Gale-Shapley在匹配数据量大时算法的低收敛性,对节点距离和能量阈值函数进行加权排序,引入“预剪枝策略”剪去优先级较低的节点,提出异构WSNs覆盖空洞稳定匹配修复优化算法ROA-NSM,建立移动节点与虚拟修复节点的稳定匹配关系修复覆盖空洞。在算法匹配次数、网络覆盖率、节点移动距离等方面进行仿真实验分析,ROA-NSM算法移动节点的平均移动距离短并且保证了网络的高覆盖率,验证了算法的有效性。