一种高效强K-栅栏覆盖构建算法*

王 超,范兴刚,王 恒,杨静静

(浙江工业大学计算机科学与技术学院,杭州 310023)



一种高效强K-栅栏覆盖构建算法*

王 超,范兴刚*,王 恒,杨静静

(浙江工业大学计算机科学与技术学院,杭州 310023)

K-栅栏覆盖是无线传感器网络覆盖控制的研究热点之一。本文构建了强栅栏覆盖模型,提出了分区强K-栅栏覆盖构建算法PMNSB,用最少的节点形成强栅栏。首先把监控区域分成多个子区域,通过匈牙利算法选用移动距离之和最少的网格集合为基准1-栅栏覆盖,缺少移动节点的子区域,选择附近区域的剩余移动节点修补形成1-栅栏覆盖。水平相邻的两个子区域之间构建竖直栅栏,这些1-栅栏合起来构成强K-栅栏覆盖。仿真结果证明了该方法的有效性,本文的研究对提升无线传感器网络的性能具有重要的理论与实际意义。

无线传感器网络;PMNSB;基准1-栅栏覆盖;竖直栅栏;匈牙利算法;修补策略;最小移动距离

无线传感器网络在诸多领域有着广泛的应用,如将可将无线传感器节点部署在污染源周围检测致命化学物的扩散,将无线传感器节点布撒在森林边缘以监测火灾发生和火情蔓延情况或放置在重要管道沿线以监视针对管道的破坏活动,以及在敌营周边布设无线传感器节点来监视敌方的兵力部署和武器配备情况等。在上述列举的应用中,传感器节点被部署于宽度小于感知半径的狭长的带状区域内,对监控区域的移动目标进行检测,这种技术被称为栅栏覆盖,是无线传感器网络领域的一个研究热点[1]。

栅栏覆盖目前已有一些研究工作[2-14]。Kumar定义了强栅栏,弱栅栏[2]。曹莹莹将影响栅栏覆盖生命期的因素描述为一个多目标优化问题[3]。杨涛研究了栅栏构筑算法DPA,构筑多条栅栏,实现多栅栏覆盖[4]。罗卿采用概率性感知模型,提出一种栅栏覆盖控制算法,调度传感器使冗余节点睡眠,达到减少能耗和延长网络寿命的目的[5]。Li L研究了无线传感器网络(WSN)一维K-覆盖问题,分析k-coverage比例、全k-coverage概率和部分k-coverage概率[6]。秦宁宁提出了一种兼顾安全和时效两种性能的启发式轨迹算法,对划分轨迹的准确性进行了研究[7]。孙继忠解决无线传感器网络中栅栏覆盖最佳路径的问题[8]。班冬松研究了全移动传感器网络K-栅栏覆盖问题,提出了一种能量高效的栅栏覆盖构建算法CBIGB[9]。Jie Tian研究了两维的栅栏覆盖[10],Zhibo Wang研究了有向网络的栅栏覆盖[11]。郭新明研究了保证传感栅栏贯通的前提下,尽可能降低栅栏整体的能耗方法[12]。张美燕研究了最大K有向覆盖问题,设计了一种分布式启发式算法,在一跳邻居范围内对传感器节点的感知方向进行协同调度,使得目标集合被有向K覆盖的时间最大[13]。针对井下无线传感器网络k(k=2)重覆盖问题,胡照鹏提出一种基于矩形分区覆盖的节点确定部署策略。在只给出网络规模和节点感应半径的条件下,求出网络所需最少节点个数和节点间距[14]。

移动节点重新部署形成栅栏的过程中,节点移动将消耗大量能量,如何设计具有较小通信和计算开销的K-栅栏构建算法仍是一个难点。借鉴上述文献中的分区策略,本文主要研究如何用尽量少的节点形成强K-栅栏覆盖,贡献如下:①确定强K-栅栏基准,采用的匈牙利算法最佳匹配移动节点与每一行。选用移动距离之和最少的行为基准1-栅栏。②为了形成强栅栏覆盖,水平相邻的两个子区域之间纵向形成竖直栅栏。③缺少移动节点的子区域,调动附近区域的移动节点修补形成1-栅栏。

本文余下章节安排如下:第1节描述网络模型,定义MNSB问题。第2节详细介绍分区强栅栏构建方法。第3节通过仿真实验对提出的两种算法进行性能评估。第4节总结全文并介绍下一步工作。

1 强栅栏覆盖模型

假设在长度为L,宽度为W区域中,随机部署N个节点。节点具有移动能力,节点能够获知自身地理位置信息。节点的感知半径为R。需要在这个区域中形成K-强栅栏。

定义1 最少节点的强栅栏MNSB(Minimum Node Strong Barrier) 如果监控区域A中存在一个从左到右传感器节点集合:

S={s1,s2,…,sm},m≤N

(1)

x1≤x2≤…≤xm-1≤xm

(2)

形成一条水平强栅栏,每个节点的最大感知半径在水平方向,则水平方向形成1条MNSB。

定义2 节点的最大感知半径 节点的最大感知半径为节点的感知区域内存在的两点间的最大距离。

定义3 节点密度 节点的数量与区域面积的比值为节点密度。节点密度对栅栏的形成有重要的影响,后面的仿真会进一步分析节点密度对栅栏的影响。

定理 在没有障碍物的前提下,如果存在一个节点集合Asz,水平相邻两个节点的感知区域有且仅有一个相切点,相切点的连线与K-栅栏的方向重合,则这个集合构成一条MNSB。

证明 由于全向节点的最大感知半径为2R,相邻的两个相切点的距离也为2R,即相邻的两个节点对栅栏的贡献最大,由于所有的节点都是依次相切,对栅栏的贡献都是最大,形成的栅栏需要的节点数最少。即集合S满足下列条件:

d(i-1,i)=d(i,i+1)=2R

(3)

其中d(·)表示两个节点间的欧式距离,R表示节点的感知半径。所以集合S构成一条MNSB。

如图1所示,有4个节点集合,集合一、三是强栅栏,节点集合四是弱栅栏。节点集合二不是强栅栏,也不是弱栅栏。栅栏一由13个节点构成,栅栏三用了10个节点,弱栅栏四也是由13个节点构成。由此可见,节点集合三节点之间的距离正好是2R,构成强栅栏。如果集合2的节点进行有限的移动也可以形成MNSB。

图1 栅栏覆盖

我们研究的问题就是:在区域A中,移动节点密度不同的情况下,如何高效构建强K-栅栏,使每个节点对栅栏的贡献最大。

2 强K-栅栏覆盖构建算法

要构建K-栅栏覆盖,以节点为顶点,节点的最近距离为权值,构建有向图,选择两个端点,运用Dijkstra算法[15]求两点间的最短路径。这个最短路径上的节点就是栅栏基准位置。大于节点的最大感知半径的两个节点之间需要移动节点修补,从而构成栅栏。我们称这种方法为RVSB算法,这种方法可以形成栅栏,但会消耗大量的通信资源。要减少通信和计算开销,可以把这个区域构造K-栅栏这个复杂的问题分成小问题,先在小的子区域构造1MNSB,这些1-栅栏合起来就是强K-栅栏,从而减少通信和计算开销。班冬松提出的基于CBIGB算法的强K-栅栏覆盖构建算法[9]就是分区的栅栏构建方法,但是CBIGB算法在相邻的子区域之间选择整个竖直列为基准,需要较多节点,消耗更多能量。而且这个算法没有提到节点修补,如果子区域的节点数不够,而相邻的子区域有相邻的节点的情况下,就不能形成强栅栏。

结合两个方法的优缺点,我们进一步提出PMNSB算法(PartitioningConstructionofStrongBarrierofMinimumNode)。

2.1 算法的基本思想

将传感器节点按照不同密度随机部署在监控区域。要形成K-栅栏,先将监控区域进行划分,垂直方向为K,水平方向为V共K·V个相同大小的子矩形区域。再对监控区域网格划分,网格的内切圆半径为节点的感知半径,即节点的最大感知半径的一半。如果子区域内,某一行网格上,每一个网格有且仅有一个节点,则节点两两相切。根据第2节的定理,这一行上的节点形成一条MNSB。运用这个思想,强K-栅栏覆盖构建算法PMNSB在每一个子区域,利用匈牙利算法[15]对目标点和移动节点进行最佳匹配,选择基准1-栅栏;对于缺少移动节点的子区域,利用附近区域的移动节点进行修补;水平相邻的子区域之间通过竖直栅栏连接起来,形成强K-栅栏覆盖。我们称这个算法为PMNSB算法。

2.2 算法具体过程

PMNSB算法的伪代码如图2。参数的定义如表1所示。

PMNSB算法具体步骤为:

步骤1 初始化。对区域网格化,进行子区域划分,得到子区域的节点集合Nsz,以网格为单位的子区域的长度l,宽度w。

步骤2 选择每一行的目标网格。如果子区域Asz左侧区域存在栅栏覆盖,且栅栏所在的行为rs(z-1),对于第t行网格,p=|rs(z-1)-t|,则选取相应的竖直栅栏目标网格VGt(见图3),t行的目标网格为Gt=(gt1,…,gtl,…,gttm),其中tm=l+p。如果子区域中移动节点数目小于基准栅栏需求,直接选取与左边子区域一样的基准栅栏行rsz=rs(z-1)。

步骤3 确定基准栅栏,选择节点构建栅栏。对于区域Asz的第t行的Gt按照式(4)进行矩阵赋值操作。运用匈牙利算法,得出节点最小总移动距离Dt。选取Dt最小的行作为子区域的基准网格栅栏行rsz(如图3),对应的可移动节点移动到目标位置构建栅栏。

图2 PMNSB伪代码

图3 竖直栅栏网格的选取

表1 参数定义

步骤4 栅栏修补。如果子区域中移动节点数目小于基准栅栏需求,移动节点先移动到相应的基准栅栏位置,移动节点加到集合MS中,移动距离加到TMov,没有移动的节点集合保存到一个集合RS中。RS和未部署的网格RG进行匹配修补(修补效果见图4)。移动节点加到集合MS中,移动距离加到TMov。并计算平均移动距离AMov。

步骤5 输出栅栏,总移动距离,平均移动距离。

参数进一步解释如图3,l=6,w=5,子区域Asz左侧区域的基准栅栏行rs(z-1)=3,针对t=1,竖直栅栏目标列VG1=(vg1,vg2),p=2,l+p=8。对于区域Asz的第t行的目标网格与移动节点进行距离计算公式如下:

(4)

式中,(xi,yi)表示第t行目标网格中的第i个网格gi(0≤i≤tm)的位置信息,(xj,yj)表示节点sj的位置信息。

2.3 算法的复杂性分析

在子区域Asz中,传感器节点的个数为Nsz。在这个区域中,可能形成1-栅栏的目标位置最大个数为l+w-1,只要Nsz≥l+w-1,子区域就能形成MNSB。整个区域要形成K-栅栏,目标位置的最大个数为(l+w-1)·K·V,也就是说在修补策略下,只要节点总个数N≥(l+w-1)·K·V,PMNSB就一定能形成强K-栅栏。

(5)

由于算法的复杂度主要和节点数N,栅栏数K,V有关。如果没有进行子区域划分,每一个网格与每一个节点都要进行匹配对比,算法复杂度算法总的复杂度为:

(6)

由于每个节点都要与中心节点通信,这是的通信开销为O(N),中心节点把结果通知给移动节点,通信开销最多为O(N),总的通信开销为O(N)。分区域以后,节点只需要与分区域的中心节点通信,假设节点均匀分布,这时候,通信开销仅为O(N/K×V)。很显然分区以后,计算和通信开销都大大降低。

3 仿真结果

本文运用MATLAB7.0对此算法进行仿真,如果没有特别指明,实验的默认参数如表2所示。为了体现PMNSB算法在传感器节点的使用数量和移动距离上的优势,我们对3种算法PMNSB、CBIGB,RVSB进行性能比较。在保证能形成栅栏的前提下,相对较少的节点分布更能体现出各算法的优劣性,因为0.005的节点密度不能使CBIGB形成6栅栏覆盖,因此此处我们选择0.006作为节点分布的密度。

表2 实验参数

图4为传感器节点的初始分布图,以及运行CBIGB算法、RVSB算法、PMNSB算法后2-栅栏覆盖节点分布图,它们分别用78,87,52个节点形成了2-栅栏覆盖,可见PMNSB算法用最少的节点形成了栅栏。

在节点较少的情况下,如果没有修补,就可能形不成栅栏,如图5所示,在密度为0.003的情况下,如果没有修补就不能形成3-栅栏,而用附近的节点修补以后,就可以形成3-栅栏。可见修补策略是非常有必要的。

影响栅栏构建的主要参数是节点数N,栅栏数K,参数V。我们进一步详细分析这些参数对栅栏形成的影响,所有的实验结果都是50次实验的平均值。评价指标是形成K-栅栏的节点数,总移动距离和平均移动距离3个指标。形成K-栅栏节点数越少,说明算法的效率越高,由于移动会消耗能量,总移动距离越少,整个网络的耗能就越少,网络的工作时间就越长。平均移动距离越小,节点的能耗越均匀。

图4 随机部署VS栅栏部署的节点分布

图5 栅栏修补对比图

3.1 节点密度的影响

图6 节点密度VS总移动距离

节点密度影响如图6～图8所示。由图可以看出随着密度的增加,3种算法总移动距离,平均移动距离都在降低,PMNSB算法的节点平均移动距离明显低于其他两种算法,也就是说PMNSB算法节点能耗更加均匀。PMNSB算法和CBIGB算法形成栅栏的节点数基本不变,RVSB算法节点数随着密度的增加而增加。3个指标都是PMNSB算法最低,在低密度下,总移动距离PMNSB算法比CBIGB算法、RVSB算法低40%多,50%。平均移动距离低30%,50%。节点数分别相差60%,50%～70%。

图7 节点密度VS平均移动距离

图8 节点密度VS形成栅栏所需节点数

3.2 不同栅栏数的影响

栅栏数K值影响如图9～图11所示。由图9和图10可以看出,随着栅栏数的增加,3种算法的3个指标都增加。如图9所示,形成1-栅栏,6-栅栏,PMNSB算法分别需要总移动距离150 m,1 400 m,平均距离为6 m,9 m;CBIGB算法分别需要总移动距离400 m,1 800 m,平均距离为8 m,12 m。K的增大导致相应子区域内的可选择的传感器节点数量减少,使得平均移动距离和总移动距离变大。

图9 K值VS移动总距离

图10 K值VS平均移动距离

PMNSB算法用最少的节点生成的K-栅栏。如图11所示,形成1-栅栏,6-栅栏,PMNSB算法分别需要30,140,CBIGB算法分别需要60,160个。所以同样的节点数,PMNSB算法形成的栅栏数最多。RVSB形成的栅栏数最少,当K增加到4时,RVSB算法形成4-栅栏覆盖的几率小于1,当K增加到5时,基本无法再形成栅栏覆盖,说明RVSB算法对区域内的传感器节点数量要求比较高。

图11 K值VS形成栅栏所需节点

3.3 不同栅栏基准的影响

不同的栅栏基准,效果是不一样的,我们把本算法和文献[9]的BGBS2,BGBS3比较,结果如图12～图15所示。

图12 节点密度VS总移动距离

图13 节点密度VS平均移动距离

图14 K值VS总移动距离

图15 K值VS平均移动距离

由图可知,在节点密度0.004时,PMNSB,BGBS2,BGBS3算法形成2-栅栏需要的总移动距离为420 m、480 m、430 m,平均移动距离为8.5 m、9.5 m、8.8 m。无论在密度一样的情况下还是K值一样的情况下,PMNSB性能都优于BGBS2和BGBS3算法,不过PMNSB的计算复杂度高于BGBS2和BGBS3,但是由于使用PMNSB能有效减少传感器节点移动距离,因此PMNSB策略更优。BGBS2和BGBS3是人为指定的目标位置,而PMNSB是采用匈牙利匹配算法选择节点形成K-栅栏。尽管3种算法需要的节点数一样,但PMNSB算法移动距离最小。

3.4 不同V值对结果的影响

我们进一步分析了不同的V值对PMNSB算法的仿真结果影响,如图16、图17所示。当V值为2,3,4时,形成2-栅栏需要的总移动距离为830 m、880 m、880 m,平均移动距离为17 m、18 m、18 m。V越大子区域越小,子区域内的节点数目就越少,使得节点的选择变少,有可能会增加总移动距离和平均移动距离;另一方面,V越大导致水平方向上的子区域增多,因此一整条栅栏中基准栅栏位置的选择增大,能一定程度降低总移动距离和平均移动距离。但当节点密度较少时,不同的V的取值对于移动距离的影响很小。

图16 V值VS平均移动距离

图17 V值VS总移动距离

4 结论

本文主要研究强K-栅栏覆盖构建方法PMNSB。先在子区域选择移动距离之和最少的基准1-栅栏覆盖位置。移动节点移动到此位置。缺少移动节点的子区域,附近区域的移动节点修补形成1-栅栏覆盖。水平相邻的两个子区域之间形成隔离栅栏。这些子区域合拼,构成强K-栅栏覆盖。

仿真结果证明,PMNSB可以用最少的节点,高效节能的构建K-栅栏。栅栏形成以后,如何节能高效的工作是下一步要研究的内容。

[1] 任彦,张思东,张宏科.无线传感器网络中覆盖控制理论与算法[J].软件学报,2006,17(3):422-433.

[2]Kumar S,Lai T H,Arora A.Barrier Coverage with Wireless Sensors[C]//Proc of the 11th Annual International Conference on Mobile Computing and Networking,2005:284-298.

[3]曹莹莹,黄刘生,朱立才,等.一种协作的异构传感器最优栅栏覆盖模型[J].小型微型计算机系统,2012,33(11):2457-2462.

[4]杨涛,慕德俊.无线传感器网络多栅栏覆盖构建算法研究[J].弹箭与制导学报,2012,32(2):173-176.

[5]罗卿,林亚平,王雷,等.传感器网络中基于数据融合的栅栏覆盖控制研究[J].电子与信息学报,2012,34(4):825-831.

[6]Li L,Zhang B,Zheng J.A Study on One-Dimensional K-Coverage Problem in Wireless Sensor Networks[J].Wireless Communica-tions and Mobile Computing,2013,13(1):1-11.

[7]秦宁宁,张林,山秀明,等.无线传感器网络启发式移动轨迹策略的研究[J].电子与信息学报,2008,30(3):707-711.

[8]孙继忠,马永强,胡艳,等.分布式Delaunay三角剖分在栅栏覆盖中的应用[J].计算机工程与应用,2010,46(26):76-79.

[9]班冬松,温俊,蒋杰,等.移动无线传感器网络K-栅栏覆盖的构建算法[J].软件学报,2011,22(9):2089-2103.

[10]Tian Jie,Zhang Wensheng,Wang Guiling,et al.2D K-Barrier Duty-Cycle Scheduling for Intruder Detection in Wireless Sensor Networks[J].Computer communications,2014,4(3):31-42.

[11]Wang Zhibo,Liao Jilong,Cao Qing,et al.Achieving K-Barrier Coverage in Hybrid Directional Sensor Networks[J].IEEE Transactions on Mobile Computing,2014,13(7):1443-1455.

[12]郭新明.高效无线传感器网络强k-栅栏覆盖节能算法[J].计算机应用,2013,33(8):2104-2107.

[13]张美燕,蔡文郁.无线视频传感器网络有向感知K覆盖控制算法研究[J].传感技术学报,2013,26(5):728-733.

[14]胡照鹏,张长森.基于矩形分区覆盖的节点确定部署策略[J].传感技术学,2013,26(3):411-413.

[15]王海英,黄强,李传涛.图论算法及其MATLAB实现[M].北京:北京航空航天大学出版社,2010.

An Effective Realization Scheme for Strong K-Barrier Coverage in WSN*

WANGChao,FANXinggang*,WANGHeng,YANGJingjing

(College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)

K-barrier coverage is one of the hot spot in the wireless sensor network.This paper mainly proposes PMNSB(partitioning construction of strong barrier of minimum node).First,it divides the interested area into several subareas,1-barrier coverage benchmark are determined by Hungary algorithm in each subarea.Second,according to this benchmark,mobile nodes in this subarea move to its destination to build 1-barrier coverage.If it is lack of mobile node in one subarea,the residual mobile node near this subarea repair the hole of barrier benchmark.Third,there is vertical barrier between two horizontal adjacent subarea.Finally,these 1-barriers are merged into strong K-barrier coverage.Simulation results show our method could effectively constitute K-barrier coverage,and enhance the coverage performance of WSN.This research has important theoretical and practical significance.

WSN;PMNSB;1-barrier coverage benchmark;vertical barrier;Hungary algorithm;Repairing scheme;Minimum sum of moving distance

王 超(1993-),男,本科生,主要研究领域为无线传感器网络;

范兴刚(1974-),男,浙江工业大学计算机科学与技术学院副教授,工学博士,研究领域为传感器网络,网络通信、实时通信,分布式实时系统的设计,xgfan@zjut.edu.cn;

杨静静(1990-),男,硕士生,主要研究领域为无线传感器网络。

项目来源:“十二五”国家科技支撑计划项目(2012BAD10B01);浙江省大学生科技创新活动计划(新苗人才计划)

2014-10-06 修改日期:2014-11-24

C:6150P;6210;7230

10.3969/j.issn.1004-1699.2015.02.014

TP273

A

1004-1699(2015)02-0227-07