WSN中覆盖空洞修复研究介绍.pdf

W S N中覆盖空洞修复研究介绍李嘉欣,薛亮,凌兴宏(苏州城市学院计算科学与人工智能学院,江苏 苏州 )摘要:在无线传感器网络中,节点分布不均匀,节点在采集和传输数据时能耗不均衡,以及节点在运行过程中出现故障等原因,均会导致网络覆盖率降低,造成覆盖空洞,从而产生异常的网络数据.为了提高网络覆盖率并延长网络寿命,需要对覆盖空洞进行测试与修补.为此,对现有网络覆盖方法进行分类整理,同时罗列出覆盖评价的重要性能指标,以供该领域参考.关键词:WS N;覆盖空洞;网络覆盖;覆盖算法中图分类号:T P D O I:/j c n k i d g j s I n t r o d u c t i o nt o t h eS t u d yo fC o v e r a g eH o l eR e p a i r i nW S NL I J i a x i n,XU EL i a n g,L I N GX i n g h o n g(C o m p u t i n gS c i e n c ea n dA r t i f i c i a l I n t e l l i g e n c eC o l l e g e,S u z h o uC i t yU n i v e r s i t y,S u z h o u ,C h i n a)A b s t r a c t:I nw i r e l e s s s e n s o rn e t w o r k s,t h eu n e v e nd i s t r i b u t i o no f n o d e s,t h eu n e v e ne n e r g yc o n s u m p t i o no f n o d e s i nd a t ac o l l e c t i o na n dt r a n s m i s s i o n,a n d t h e f a i l u r eo f n o d e s i n t h eo p e r a t i o np r o c e s s a l l l e a d t o t h e r e d u c t i o no f n e t w o r kc o v e r a g e,r e s u l t i n g i n t h e c o v e r a g eo f h o l e s a n da b n o r m a l n e t w o r kd a t a T o i m p r o v en e t w o r kc o v e r a g ea n de x t e n dn e t w o r k l i f e t i m e,i t i sn e c e s s a r y t o t e s t a n d r e p a i r t h e c o v e r a g ev o i d s T o t h i s e n d,t h e e x i s t i n gn e t w o r kc o v e r a g em e t h o d s a r e c l a s s i f i e da n do r g a n i z e d,a n dt h e i m p o r t a n tp e r f o r m a n c e i n d i c a t o r so f c o v e r a g ee v a l u a t i o na r e l i s t e df o r r e f e r e n c e i nt h i s f i e l d K e yw o r d s:WS N;c o v e r a g ev o i d s;n e t w o r kc o v e r a g e;c o v e r a g ea l g o r i t h m s基金项目:年校级大学生课外学术科研基金项目收稿日期:作者简 介:李 嘉 欣(),研 究 方 向 为 物 联 网 应 用;薛 亮(),通信作者,硕士,研究方向为数据挖掘、物联网应用;凌兴宏(),副教授,研究方向为机器学习、强化学习.引言无线传感器网络(W i r e l e s sS e n s o rN e t w o r k,WS N)是一种有感知性的无线网络,具有规模大、功耗低、随机部署、能量有限、资源不可再生、网络组织方式多样化的特点.WS N是一种集成的、智能化的信息网络,它的各个节点都具有信息采集、传递与处理的能力,即集三部分于一身.随着嵌入式技术、传感器技术、现代网络技术、分布式信息处理技术和无线技术的不断发展,形成了一种交叉学科和知识高度集成的新技术.WS N在生物诊疗、环境监测、救灾、国防、军事等方面发挥着重要作用,美国商业周刊B u s i n e s sW e e k将其列入 世纪最具影响力的新技术,同时也分别被M I TT e c h n o l o g yR e v i e w、M I TB u s i n e s sW e e k评为人类未来十大现今科技第一名和人类未来四大高新技术产品之一.随着研发的推进和应用的普及,传感器网络逐渐渗透到人民的生活中,并广泛应用于智能家居、医学卫生、智慧交通、制造业、环境军事等领域.覆盖率作为传感器系统质量主要的衡量标准,它反映了WS N在空间数据最佳分配、环境感知、数据收集和快速传输等方面的感知技术能力.通常情形下,网络覆盖率的高低会对监控区域的服务品质产生重要影响,即覆盖的质量与监控区域的服务品质有着直接的关联.WS N的覆盖问题,是指WS N中的传感器节点能够在其所部署的空间范围内感知到的区域.覆盖问题是研究WS N覆盖空洞的基础,只有合理的覆盖方式才能使WS N覆盖空洞的个数和出现概率相应降低.W S N覆盖空洞问题定义和优化意义覆盖度是WS N的最基本的问题,它直接关系到WS N的感知性能、监测、数据采集等方面的性能.覆盖度作为衡量WS N性能的重要指标,通过对覆盖空洞的修复,可以确保WS N的节点部署实现对目标和区域的探测.W S N目标布设环境严酷,由于电池提供的感测节点能量有限,因此节点损耗和外部攻击等都容易造成传感器节点失效,从而产生覆盖空洞(C o v e r a g eH o l e s).由于覆盖空洞的存在,节点获得的有效信息不完整,即网络不能采集到完整有用的数据资料,而且由于空洞的阻隔,网络不能将所采集的数据进一步传送给S i n k节点,甚至无法收集到完整的数据,导致后续网络用户得到的数据不准确,这种现象的发生无法避免.由于网络生命周期已过,许多人工智能与传感技术电工技术能源资源没有得到充分利用,降低了网络的覆盖率和连通性,并造成了资源的浪费,因此影响到网络的服务品质,甚至造成无法使用,所以必须及时发现网络中的漏洞.覆盖空洞的修复问题是有关WS N覆盖问题的一个探究热点.空洞修复的目标是将检测到的覆盖空洞填补上,重新收归在WS N覆盖范围内.当前,正在研究如何在混合WS N中克服空洞问题:确定实际应用中的覆盖要求,根据节点特征选取或设计有效的节点覆盖模型,并在此基础上设计相应的节点分配和移动路径,提供一个高效合理的空洞修复算法,充分利用WS N中的硬件资源,以期提高网络覆盖质量和延长网络寿命.覆盖空洞问题产生的原因覆盖空洞产生的主要原因有三个方面:一方面,由于传感器节点的能量有限,因此会出现节点能源枯竭等问题;另一方面,部署节点的环境常常十分恶劣,存在气候变化、外界干预等因素,亦会导致节点失效,让传感器网络的覆盖区域逐渐出现覆盖空洞;不仅如此,动物入侵还会导致节点的死亡,使得网络中的所有节点都无法察觉到这一点,从而形成覆盖的空洞.覆盖空洞的存在会加速空洞周围节点的死亡,从而降低网络的覆盖率和互联性,导致网络连接中断或传输数据信息的丢失,从而降低了WS N提供的服务质量.WS N在紧急救援、太空探索、军事应用等领域得到了广泛的应用.传感器节点在特定的应用环境下,经常会在一个特定的区域内随机分布,组成一个自组织的网络.恶劣的环境条件下,节点的能源枯竭甚至是野兽的侵袭都有可能造成节点的死亡,这就导致了网络中的一些区域没有被节点察觉,从而产生了一个覆盖空洞范围.如图所示,传感器节点S发生故障,其感知半径内的数据不能被探测到,产生了一个覆盖空洞,而阴影部分则表示形成的空洞区域.图覆盖空洞产生示意图覆盖空洞修复算法分析覆盖缺陷的存在不仅会造成节点通信中断、数据信息丢失等问题,甚至会导致网络瘫痪,从而影响WS N的服务质量.文献 针对WS N中不同类型的覆盖空洞的特征进行了讨论,并对修复WS N中覆盖空洞的解决方案的相对优势和缺点进行了阐述.不仅如此,D a h i y a 等人提出了一种新的M S C O L E R(基于M S的覆盖优化和链路稳定性估计路由)协议,用于优化覆盖恢复和链路稳定性估计.所提出的协议可以解决覆盖恢复的问题,减少覆盖能量消耗和延长网络寿命.为了确保网络覆盖率,提高服务质量,必须对覆盖的孔隙进行探测与修复.覆盖问题是W S N建设的基础,可以从多个方面对其进行分类.根据覆盖目标的不同,覆盖问题可以分为目标覆盖、栅栏覆盖、局部覆盖,如图所示.图覆盖问题分类 目标覆盖目标覆盖指的是监控范围内的某一具体目标,也就是所谓的点覆盖,如图所示.为了确保覆盖的质量,要求每个监控对象都有一个以上的传感器节点.在保证覆盖范围的同时,要对网络中的节点进行优化,以达到有效覆盖.图目标覆盖示意图文献 针对网络中的多目标节点的覆盖问题,以最小化节点移动距离和保持网络的连通性为目标,提出了移动传感器部署(M S D)问题的挑战,并研究了如何以最小的移动量部署移动传感器,以形成一个同时提供目标覆盖和网络连接的WS N.该方法针对目标覆盖(T C OV)的一种特殊情况,即目标之间的距离超过覆盖半径的倍,提出了一种基于匈牙利方法的精确算法来寻找最优解;针对T C OV的一般情况,提出了种启发式算法,即基于群体分割的基础算法和以V o r o n o i为基础的T V贪婪算法,目的是 减 少 整 个 传 感 器 的 移 动 距 离;对 于 网 络 连 接(N C ON),提出了一种基于边长受限的S t e i n e r最小树的有效求解方法.以上问题的解决平衡了不同传感器的负载,从而延长了网络寿命.文献 提出了一种基于权重的贪心算法(WG A),该算法将传感器组织成多个子集,并将传感器节点分成若干组,确保各组都能满足完整的覆盖率.该算法的目的是将一个初始传感器集合划分成最大可能数目的传感器集合覆盖(S S C s),这样就可以在一定范围内对一个目标进行全面电工技术人工智能与传感技术 监控,从而延长整个网络的生命周期,但在分区选取上存在一定的困难,扩展性不够好,并且时间复杂度较高.文献 提出了一种基于移动节点的覆盖空洞联合修复算法 联合补丁法,一旦捕捉到覆盖空洞,这种算法就会按照预先设定的缝制方案,将需要的活动节点“缝制”为一大片“布”,并根据其外形直接修补空洞.该算法能够根据实际情况,灵活地选择修复方案,且所需移动节点数目较少,具有较高的节点覆盖率和较低的冗余度.文献 提出了一种新的节能启发式算法,可以在不同时间段调度传感器进行覆盖,不同非相交传感器节点集合帮助网络的使用寿命最大化.该文献中的启发式算法可以识别出所有关键目标(最少覆盖)和关键节点,被最少数目的传感器节点所覆盖的关键目标会是第一个被探测到的,高效地使用关键节点将帮助延长网络的使用寿命.该文献还尝试在每一个传感器覆盖中选取最少的几个关键感应器来覆盖迷宫集合,从而使关键目标能够被覆盖更长的时间.因为该算法使用的是不相交的数据,所以与使用可能出现重叠的传感器集合相比,所得到的集合数目更少.栅栏覆盖栅栏覆盖是一种监控无线传感网路上任意路径的一种方式,如图所示.根据目标穿越传感器网络的具体情况,栅栏覆盖又分为“最佳与最坏情况覆盖”和“暴露穿越”,总体上不同于区域覆盖的是其监控对象的活