一种异构WSN复合型栅栏覆盖方法研究

王 涌,黄留信,纪专凯,沈鹏飞,朱涛涛

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

1 引 言

无线传感器网络栅栏覆盖在入侵检测等诸多领域都有着广泛的用途,如可将传感器网络部署在工厂周围,利用栅栏感知环境从而发现污染物的扩散;在现代化军事领域,将栅栏部署在敌我阵地前沿,检测敌人入侵从而避免造成重大损失[1,2].将无线传感器节点随机或有规律的部署到带状区域内,利用相关算法形成一条感知范围重叠的栅栏,该栅栏将区域一分为二,从而能够有效发现是否有入侵目标从区域的一侧穿越到另外一侧,该技术被称为WSN栅栏覆盖[3,4].目前大部分普通传感器节点仅能在干燥的环境下工作,而在水中则会失效,从而导致栅栏失去功能,因此研究一种晴雨天都适用的栅栏覆盖方法具有重要意义[5].

目前国内外学者在WSN栅栏覆盖领域做了大量的研究工作,其中在栅栏构建算法方面的研究如参考文献[6]采用异构传感器节点并利用基于簇的方向栅栏图理论实现栅栏构建,针对栅栏构建过程中存在间隙问题,通过派遣可移动节点修复,使得修复能耗最低.参考文献[7]针对栅栏不能自适应各种部署环境问题,提出了一种强k-栅栏自主覆盖方法,利用协同感知方法让传感器节点间能够协同起来,实现栅栏自我部署的目的.在构建栅栏过程中大量的算法首先需要获得传感器节点自身的位置,常见的技术包括GPS定位、WSN定位算法等,但栅栏一般部署在遮挡物较多的环境中,定位信号受到遮挡导致定位结果不准确,最终会导致栅栏构建存在间隙.针对该问题参考文献[8]研究了一种传感器节点位置容错的栅栏构建方法,利用容错加权栅栏图方法解决节点位置飘移从而导致栅栏构建不完善问题.在栅栏间隙修复方面的研究如参考文献[9]提出栅栏间隙的寻找方法,并利用最大流算法和二分法对栅栏间隙进行修复,使修复代价最小.参考文献[10]针对间隙修复复杂度高等问题,利用邻居可移动节点集合降低了 修复算法的复杂度.参考文献[11]通过建立入侵轨迹模型预测入侵者穿越栅栏时的位置,并将可移动节点移动到频繁穿越位置强化栅栏,防止出现栅栏间隙.参考文献[12]研究了一种混合传感器网络栅栏间隙修复方法,假设传感器节点的感知范围可调,利用移动节点修复栅栏使得移动距离最短.参考文献[13]根据节点间距离查找栅栏间隙,并通过旋转栅栏中关键传感器节点或一段栅栏修复栅栏间隙.

虽然传统的栅栏覆盖方法能够满足多种条件下的应用要求,但未充分考虑晴天和雨天场景下栅栏适用问题.本文根据节点在不同天气下的特性,研究了一种适用于晴天和雨天两种场景自由切换的栅栏覆盖方法,且在构建栅栏过程中基于能耗优先原则从而使得构建的栅栏具有较好的鲁棒性.

2 相关模型

a)普通传感器节点为静态节点,且仅能在晴天状况下正常工作,当节点被打湿后功能失效,节点干燥后恢复正常功能.增强传感器节点可同时在雨天和晴天状态下工作且可移动,具有较强的移动能力.两种传感器节点都能根据Gps技术或定位算法获得自身位置.

b)本文节点采用二元感知模型,该模型以传感器节点位置为圆心,以半径r的圆形区域为感知范围,感知概率如公式(1)所示.

(1)

公式(1)中o为传感器节点位置,s为入侵目标位置,d(o,s)为传感器节点和入侵目标的欧氏距离,Po,s表示节点感知到入侵目标的概率.

c)增强传感器节点在移动时消耗的能量远远高于感知消耗的能量,因此其感知过程消耗的能量忽略不计,且移动过程消耗的能量与移动距离呈正比,移动1m消耗的能量为3.6J[14,15].

3 栅栏构建

本章主要介绍一种k-栅栏构建方法,通过该方法构建的栅栏能够在晴天和雨天状况下正常工作.首先根据需要构建栅栏的数量将监测区域均匀划分为k个子区域,然后在每个子区域内构建1条晴雨天都适用的复合型栅栏.

3.1 区域划分

在初始时刻,将普通传感器节点和增强传感器节点按一定比例混合后随机均匀的部署到监测区域中,并对监测区域进行划分,理论上每个子区域内包含的传感器节点数量接近,然后在子区域内构建栅栏,且子区域内的节点仅供该区域栅栏构建使用,如图1所示.

图1 区域分割图Fig.1 Area segmentation diagram

在子区域内如何构建栅栏使得代价最小是重点研究问题.在构建栅栏过程中应尽可能降低栅栏间隙的数量和长度,从而提高栅栏构建的成功率.本文研究的栅栏构建方法主要分为三个步骤:1)传感器节点簇查找;2)最优栅栏构建路径选择;3)增强节点派遣;具体方法如下所示.

3.2 节点簇查找

在监测区域中,随机部署一定数量的传感器节点,如果两个传感器节点的感知范围存在重叠的情况,则认为这两个传感器节点组成一个簇.在该阶段利用深度优先搜索算法查找每个子区域中所有的传感器节点簇.搜索过程如图2所示.

图2 子区域成簇过程图Fig.2 Sub-region clustering process diagram

从子区域的最左侧开始搜索,首先被查找到的是节点a,将a压入栈中,然后判断是否存在传感器节点与a的感知范围存在重叠,经遍历发现与a感知重叠的节点为b,依次用同样的方法直到搜索到d后发现没有其他节点与其存在感知重叠,则第一个簇查找结束,由{a、b、c、d}组成,簇头为a节点,簇尾为d节点.接着从节点d开始查找,搜索距离子区域左边界最近的节点,搜索结果为k,且没有任何节点与它存在感知重叠,因此第二个簇由一个节点{k}组成,则该簇的簇头和簇尾都为节点k.第三个簇从节点e开始,按深度搜索方法,遍历的步骤为e→f→g→h,其中h作为其中一个簇尾,然后算法返回到f节点,继续遍历到节点i和节点j,节点j作为另一个簇尾.

3.3 最优构建路径

在子区域内完成簇的遍历后,应尽可能利用已经形成的簇来构建栅栏,通过在簇之间填充增强型节点,实现子区域内的栅栏构建,如图3所示,将增强节点1、2、3、4派遣到簇1、2、3之间,将簇连接起来完成整个栅栏的构建.

图3 簇构建栅栏过程图Fig.3 Cluster construction barrier process diagram

但在子区域内簇的数量较大,如何选择最合适的簇来构建栅栏使得需要增强节点(可移动)的数量最少是难点.需要增强节点的数量越少,理论上完成栅栏构建的概率越高.本文提出一种基于增强节点需求拓扑结构图和最短路径方法实现最优栅栏构建路径的选择.根据簇构建拓扑结构的过程如下:首先添加2个虚拟节点,start和end,分别位于监测区域的左右边界中心位置,然后将子区域内不同簇的簇头和簇尾相互之间两两连接,完成拓扑图的构建.拓扑图中边的权重为连接两个簇所需要的增强节点数量numi,j,如公式(2)所示.

numi,j=0,d(i,j)-2r≤0d(i,j)-2r2r,d(i,j)-2r>0 (2)

公式(2)中d(i,j)表示两个簇之间的欧氏距离,r为节点感知半径.

假设子区域内建立的增强节点需求拓扑图如图4所示,完成拓扑结构建立后即可进行最优栅栏构建路径的选择.利用最短路径算法(如Dijkstra算法)选择图4中从start节点到end节点的最短路径即为最优栅栏构建路径,且路径长度为构建栅栏需要的增强节点数量.选择该拓扑图中最短路径上的簇构建栅栏需要的增强节点数量最少.

图4 增强节点需求拓扑图Fig.4 Enhanced node requirements topology

3.4 复合型栅栏构建

本文3.3小节介绍了最优栅栏构建路径的选择,本文介绍构建复合型的栅栏,能够同时满足晴天和雨天状况下的正常工作要求.在晴天状况下,构建栅栏比较简单,仅需要派遣增强节点到3.3小节选择出的最优栅栏构建路径间隙处即可完成栅栏的构建.但雨天栅栏的构建涉及到增强节点的派遣.本文提出一种栅栏分割的方法,如图5所示,假设晴天栅栏已构建完成, 如果将晴天栅栏中的普通传感器节点替换为增强节点,则该栅栏即可在雨天正常工作.首先从左到右扫描栅栏,如果是增强节点,则作为一个分界线,按上述方法将栅栏进行划分,划分后每个区域内的传感器节点都为普通传感器节点,然后计算每个区域内普通传感器节点的数量.如区域a中的栅栏有1个普通传感器节点和1个空闲的增强传感器节点,则该增强节点可移动到普通传感器节点位置完成该段栅栏的复合化.区域b中的栅栏共有2个普通节点,但只有一个空闲的增强节点,无法完全栅栏复合化,因此将区域b和区域c进行合并,合并后变成区域e,如图5(b)所示,区域e中的栅栏共有5个普通节点,且区域中刚好有5个增强节点,因此能够完成区域e中的栅栏普通节点的复合化.按上述方法对栅栏进行切分,然后派遣增强节点到普通节点位置,即可构建一条雨天状况下适用的栅栏.

图5 区域合并图Fig.5 Area merge diagram

4 最优派遣

匈牙利算法是一种最优指派算法,假设派遣n个工人去做n个工作,每个工人可同时能做若干种任务,但每个任务只能派遣1个工人,而每个工人对不同任务的熟练程度不同,即完成时间不同.匈牙利算法能够最优的指派人员去做相应的工作,使完成所有工作花费的时间总和最短.将增强节点的派遣问题类比到人员指派问题,上文中晴天和雨天栅栏的构建过程中都涉及到增强节点的派遣,为尽可能降低栅栏构建过程中的能量消耗,因尽可能降低增强节点的移动距离.假设派遣x个增强节点到y个指定位置,但x与y的值不一定相等,因此利用“加边补零法”对传统的匈牙利算法进行改进,使之适用于不完全指派问题[16,17],如图6所示.假设实际有2个位置需要分配增强节点,但增强节点的数量为3,分别为v1、v2、v3,由于位置数量少于增强节点的数量,因此虚拟出一个位置o,所有增强节点到虚拟位置o的欧式距离都为0,增强节点与实际位置的距离可用di,j表示,i表示增强节点的编号,j表示位置编号.根据“加边补零法”构建匈牙利算法代价矩阵,如公式(3)所示.

图6 匈牙利最优派遣图Fig.6 Hungary′s best dispatch map

(3)

构建相应的代价矩阵后,根据传统的匈牙利算法步骤即可最优的派遣增强节点到指定的位置,使得整个派遣过程中增强节点的移动距离总和最短,从而实现总能耗最低的目的.

在构建晴天栅栏时,主要派遣增强节点到簇的间隙处,将不同簇连接起来,实现栅栏的构建,如图7所示.首先将簇1和簇2的间隙用直线连接, 然后根据公式(2)计算连接2个簇需要的增强节点数量num,接着在间隙处均匀确定num个位置,最后基于匈牙利派遣方法将增强节点派遣到相应位置.利用该方法可完成晴天栅栏的构建.

图7 簇连接图Fig.7 Cluster connection diagram

晴天栅栏构建完成后,只需利用3.4小节的栅栏划分方法分段派遣增强节点到普通节点位置即可完成雨天栅栏的构建.

5 实验分析

本文采用MATLAB软件进行仿真实验,并采用i7的处理器和8G内存的电脑作为硬件支撑.在一个长、宽分别为300m和1000m的矩形带状区域内随机均匀地部署普通传感器节点和增强传感器节点,传感器节点的感知半径r=30m.在监测区域中构建3条复合型栅栏(能满足晴雨天工作的栅栏),通过对比参考文献[18]和文献[19]结合的栅栏构建方法Flow和贪婪算法Greedy,验证本文算法(HCBC)的性能.Flow方法和Greedy方法利用普通传感器节点完成基础栅栏的构建,并派遣增强节点修复栅栏间隙,实现栅栏构建.

5.1 栅栏覆盖率

栅栏构建算法的主要目的是尽可能完整的构建栅栏,因此栅栏覆盖率是栅栏构建算法的重要指标之一.栅栏覆盖率是指完成构建的栅栏在矩形监测区域水平方向上的投影与监测区域水平方向长度的比值.如果构建的栅栏没有间隙,能够完全覆盖监测区域,则栅栏覆盖率为100%.实验中在监测区域中部署250个传感器节点,其中普通节点和增强节点按一定比例混合,实验验证不同混合比例情况对栅栏覆盖率的影响.针对Flow栅栏覆盖算法和贪婪算法Greedy,增强节点视为可移动节点,普通节点视为静态节点,实验结果如图8、图9所示,图8为构建晴天栅栏的覆盖率,图9为构建雨天栅栏的覆盖率,横坐标为普通节点与增强节点的混合比例,纵坐标为栅栏总体覆盖率.

图8 晴天栅栏构建覆盖率Fig.8 Sunny barrier construction coverage

实验结果表明构建晴天栅栏时,随着增强节点比例的提高,栅栏平均覆盖率也随之提高.且本文提出的HCBC方法覆盖率高于Flow方法,Greedy的覆盖率最低,且当节点比例为1∶1时,HCBC方法的栅栏覆盖率比Greedy方法提高了59.1%,因为随着增强节点比例提高,可被派遣的增强节点数量增加,能修复栅栏间隙的概率也会提高,所以覆盖率逐渐增加.HCBC方法在构建栅栏过程中能够利用增强节点,且利用匈牙利算法能够实现最优派遣,而Flow和Greedy方法在构建栅栏时仅用到静态节点(普通节点),只有在间隙修复是用到了移动节点(增强节点),因此构建的栅栏覆盖率低于HCBC方法.在构建雨天栅栏时,HCBC方法构建的栅栏覆盖率高于Flow和Greedy,且当节点比例为1∶1时,HCBC方法的栅栏覆盖率比Greedy方法提高了51.6%.因为Flow方法采用二分法派遣移动节点(增强节点),只能算是逼近最优派遣,Greedy方法仅派遣最近节点,容易陷入局部最优问题,而本文提出的HCBC方法能够实现最优派遣.综上所述,本文方法在构建晴雨天栅栏时,平均覆盖率比Greedy提高了55.35%.

图9 雨天栅栏构建覆盖率Fig.9 Rainy day barrier construction coverage

5.2 平均移动距离

在构建栅栏过程中往往需要利用增强节点对间隙进行修复才能够构建强k-栅栏.理论上构建栅栏的平均移动距离越短,则消耗的能量越少,越有利于栅栏后期的长期生存.本实验在监测区域内随机均匀部署300个传感器节点,通过调整普通节点和增强节点的混合比例验证栅栏构建时增强节点的平均移动距离.实验结果如图10、图11所示,图10为构建晴天栅栏的实验结果,图11为构建雨天栅栏的实验结果,横坐标为普通节点和增强节点的比例,纵坐标为增强节点的平均移动距离.

图10 晴天栅栏平均移动距离Fig.10 Average moving distance of sunny barrier

实验结果表明随着增强节点比例的逐渐提高,晴天和雨天栅栏构建时增强节点的平均移动距离逐渐降低,因为增强节点数量增加,则栅栏间隙位置附近有更大概率存在增强节点,而无需去更远的地方派遣.在晴天栅栏构建时,当增强节点比例低于1∶3时,Flow的平均移动距离低于HCBC方法,而HCBC方法的平均移动距离高于Greedy方法,因为在增强节点比例不高时,HCBC方法构建栅栏是使用了部分增强节点,导致空闲的增强节点密度低于Flow方法,因此平均移动距离会略高于Flow方法,而Greedy每次都派遣最近的节点构建栅栏,在增强节点密度不高时,容易陷入局部最优问题.当增强节点的比例提高时,HCBC方法的平均移动距离低于Flow和Greedy方法,因为当增强节点密度提高,栅栏间隙附近有足够的增强节点可用于构建栅栏,而HCBC方法实现了最优派遣.在构建雨天栅栏时,随着增强节点比例的提高,三种方法的平均移动距离都降低.其中Flow方法的平均移动距离最低,其次是HCBC方法,平均移动距离最高的是Greedy方法,因为Flow在构建栅栏过程中仅用了静态节点(普通节点),而HCBC方法使用了部分增强节点,因此Flow方法构建栅栏后空闲的增强节点密度要略高于HCBC,因此平均移动距离低于HCBC方法.

图11 雨天栅栏平均移动距离Fig.11 Average distance of rain barrier

5.3 栅栏构建总能耗

栅栏构建消耗的能量不仅与节点的平均移动距离有关,还与节点的移动数量有关.本文设计HCBC方法的主要目的是尽可能低的降低栅栏构建能耗.本实验在监测区域内部署300个传感器节点,其中普通节点和增强节点按一定比例混合,验证在栅栏构建过程中的总能耗.实验结果如图12、图13所示,其中图12为晴天栅栏构建过程中的总能耗,图13为雨天栅栏构建过程中的总能耗.横坐标为普通节点与增强节点的比例,纵坐标为总能耗.节点移动过程消耗的能量可参考本文第2章节的移动能耗模型.

图12 晴天栅栏构建总能耗Fig.12 Energy consumption of the sunny barrier construction

实验结果表明随着增强节点比例的提高,本文提出的HCBC方法消耗的总能量逐渐减低,而Flow和Greedy方法消耗的能量逐渐提高.因为HCBC方法在初始构建晴天栅栏时能够利用增强节点,因此增强节点混合比例的提高不影响栅栏构建,但随着增强节点比例增加,平均移动距离会逐渐减低,因为总能耗逐渐降低,而Flow和Greedy方法构建栅栏时仅利用静态节点(普通节点),当增强节点的比例提高时,普通节点比例会降低,初步构建栅栏后有大量的间隙需要派遣可移动节点去修复,因此部署区域中增强节点的比例提高,消耗的能量越大.雨天栅栏构建过程中随着增强节点比例的提升,三种方法的栅栏构建总能耗逐渐降低,因为增强节点比例提高,增强节点派遣到栅栏中普通节点位置的距离会逐渐减小,因此总能耗逐渐降低,且能耗最低的是Flow方法,其次是HCBC方法,能耗最高的是Greedy方法.

图13 雨天栅栏构建总能耗Fig.13 Energy consumption of rainy day barrier construction

5.4 实物实验

栅栏覆盖可应用于军事领域,能有效监测敌人入侵.在阵地前沿部署无线传感器网络栅栏,当敌人试图穿越栅栏时能被发现并发出警报.本实验以竹林为实际场景部署300m长的栅栏,用于监测入侵者,采用的传感器节点如图14(a)所示,该节点为CrossBow公司的Telosb节点,可通过设置节点功率来控制节点的通讯半径.实验中节点的通讯半径为15m,利用10个传感器节点组建长为300m的强栅栏,从栅栏左端开始分别编号为1～10,并随机的从10个节点中选择5个节点进行休眠,模拟节点死亡,形成栅栏间隙.在距离栅栏左右2侧垂直距离1.5m的带状区域内随机均匀部署10个节点作为可移动节点,其移动过程通过人工搬运实现,栅栏部署如图14(b)所示.实验中入侵者(人)携带一个传感器节点(目标节点)从任意位置穿越栅栏,且目标节点一直在向外发出Beacon帧,而栅栏中的传感器节点一直处于监听状态,当目标节点距离栅栏中某个传感器节点的距离小于等于15m时,栅栏中的监听节点收到Beacon帧,则认为栅栏监测到了入侵者(目标节点).实验对比贪婪算法(Greedy)和最大流算法(Flow),10次实验的平均结果如表1所示.

图14 栅栏实物部署图Fig.14 Barrier physical deployment map

表1 实物实验结果表
Table 1 Physical experiment results table

HCBCGreedyFlow修复节点数量(个)平均移动距离(米)50次穿越监测率(%)4.423.1699.33.433.0790.44.133.2498.6

实验结果表明基于本文提出的HCBC方法成功修复栅栏中间隙(死亡节点处)的平均数量最多,为4.42个,其次是Flow方法,修复栅栏间隙平均数量最低的是Greedy.因此HCBC方法构建栅栏的成功率是最高的.Greedy方法的平均移动距离最短,因为该方法总是派遣最近节点替换死亡节点(到栅栏间隙处),因此平均移动距离最短,而HCBC和Flow方法首先会尽最大可能修复间隙,其次再考虑修复代价,即平均移动距离,平均移动距离略高于Greedy方法,但HCBC考虑最优派遣,因此平均移动距离略低于Flow方法.构建栅栏够,进行50次独立重复的随机穿越栅栏实验,其中HCBC方法成功检测到入侵目标的概率最高,其次是Flow方法,最后是Greedy方法,因为HCBC方法构建的栅栏最完善,间隙长度最短.

6 总 结

本文研究了一种异构WSN复合型栅栏覆盖方法,能够适用于晴天和雨水天气.该方法首先根据构建栅栏的需求,将监测区域划分为k个子区域,然后在每个子区域内构建一条复合型栅栏,在构建过程中充分考虑了节点移动能耗,以及增强节点的数量.实验结果表明该方法能够有效解决栅栏在晴天和雨天场景下的适用性问题.后续工作希望进一步研究多场景下栅栏的调度问题,延长传感器网络的生存时间.