混合无线传感器网络覆盖空洞修复策略

第３３卷第５期２０２０年５月传感技术学报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＳＥＮＳＯＲＳＡＮＤＡＣＴＵＡＴＯＲＳＶｏｌ ３３㊀Ｎｏ ５Ｍａｙ２０２０项目来源:衢州市科技计划项目(２０１９Ｋ１７)ꎻ浙江省基础公益研究计划项目(ＬＧＦ２０Ｆ０３００３)ꎻ浙江省十三五教改项目(ｊｇ２０１８０３１０)收稿日期:２０２０－０３－２０㊀㊀修改日期:２０２０－０５－２０ＳｅａｒｃｈａｎｄＲｅｐａｉｒＭｅｔｈｏｄｏｆＰｅｒｃｅｐｔｉｏｎＣｏｖｅｒｇｅＨｏｌｅｉｎＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋ∗ＹＡＮＧＭｉｎｇｘｉａ１ꎬＦＡＮＧＫａｉ１ꎬＷＡＮＧＸｉａｏｄｏｎｇ２ꎬＰＥＮＧｆｅｎｇ３ꎬＺＨＯＵＸｉａｏｌｏｎｇ１∗(１.ＣｏｌｌｅｇｅｏｆＥｌｅｃｔｒｉｃａｌａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇꎬＱｕＺｈｏｕＵｎｉｖｅｒｓｉｔｙꎬＱｕｚｈｏｕ３２４０００ꎬＣｈｉｎａꎻ２.ＺｈｅＪｉａｎｇＪｉｕｚｈｏｕＷａｔｅｒ￣ＣｏｎｔｒｏｌＴｅｃｈｎｏｌｏｇｙＣｏ.ꎬＬｔｄꎬＱｕｚｈｏｕ３２４０００ꎬＣｈｉｎａꎻ３.ＱｕＺｈｏｕＷａｓｕＲａｄｉｏａｎｄＴｅｌｅｖｉｓｉｏｎＮｅｔｗｏｒｋＣｏｍｐａｎｙＬｉｍｉｔｅｄꎬＱｕＺｈｏｕ３２４０００ꎬＣｈｉｎａ)Ａｂｓｔｒａｃｔ:Ｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｉｓｄｅｐｌｏｙｅｄｉｎｔｈｅｔａｒｇｅｔａｒｅａｔｏｓｅｎｓｅａｎｄｍｏｎｉｔｏｒｒｅｌｅｖａｎｔｉｎｆｏｒｍａｔｉｏｎ.Ｄｕｅｔｏｔｈｅｉｎｆｌｕｅｎｃｅｏｆｕｎｂａｌａｎｃｅｄｎｅｔｗｏｒｋｅｎｅｒｇｙｃｏｎｓｕｍｐｔｉｏｎａｎｄｅｎｖｉｒｏｎｍｅｎｔａｌｉｎｔｅｒｆｅｒｅｎｃｅꎬｉｔｉｓｅａｓｙｔｏｍａｋｅｓｏｍｅｎｏｄｅｓｆａｉｌｅａｒｌｙꎬｔｈｕｓｆｏｒｍｉｎｇａｃｏｖｅｒａｇｅｈｏｌｅｉｎｔｈｅｎｅｔｗｏｒｋ.Ｔｈｅｅｘｉｓｔｅｎｃｅｏｆｈｏｌｅｓｗｉｌｌｓｅｒｉｏｕｓｌｙａｆｆｅｃｔｔｈｅｏｒｉｇｉｎａｌｆｕｎｃｔｉｏｎａｎｄｐｅｒｆｏｒｍａｎｃｅｏｆｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓꎬｓｏａｍｅｔｈｏｄｏｆｓｅａｒｃｈｉｎｇａｎｄｒｅｐａｉｒｉｎｇｔｈｅｈｏｌｅｓｃｏｖｅｒｅｄｂｙｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓｉｓｐｒｏｐｏｓｅｄｔｏｓｏｌｖｅｔｈｅａｂｏｖｅｐｒｏｂｌｅｍｓ.Ｆｉｒｓｔｌｙꎬｔｈｅｃｈｏｒｄｏｆｔｈｅｉｎｔｅｒｓｅｃｔｉｎｇｎｏｄｅｓｉｓｕｓｅｄｔｏｃｏｎｓｔｒｕｃｔａｎｄｓｅａｒｃｈｔｈｅｃｏｖｅｒｅｄｃａｖｉｔｉｅｓꎬａｎｄｔｈｅｐｒｏｂｌｅｍｏｆｃａｖｉｔｙｒｅｐａｉｒｉｓｔｒａｎｓｆｏｒｍｅｄｉｎｔｏｔｈｅｕｎｄｉｒｅｃｔｅｄｇｒａｐｈｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｏｆｍａｘｉｍｕｍｃｌｉｑｕｅꎬｓｏａｓｔｏｒｅａｌｉｚｅｔｈｅｒｅｐａｉｒｏｆｔｈｅｃａｖｉｔｉｅｓｗｉｔｈｔｈｅｌｅａｓｔｍｏｖｉｎｇｎｏｄｅｓａｎｄｔｈｅｌｏｗｅｓｔｏｖｅｒｌａｐｐｉｎｇｃｏｖｅｒａｇｅ.Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｃａｎｅｆｆｅｃｔｉｖｅｌｙｓｅａｒｃｈｆｏｒｔｈｅｃｏｖｅｒｅｄｃａｖｉｔｙａｎｄｃｏｍｐｌｅｔｅｔｈｅｒｅｐａｉｒꎬａｎｄｔｈｅｔｉｍｅｃｏｍｐｌｅｘｉｔｙａｎｄｅｎｅｒｇｙｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅａｌｇｏｒｉｔｈｍａｒｅｈｉｇｈｅｒｔｈａｎｏｔｈｅｒｍｅｔｈｏｄｓ.Ｋｅｙｗｏｒｄｓ:ｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓꎻｃｏｖｅｒａｇｅｈｏｌｅꎻｓｅａｒｃｈａｎｄｒｅｐａｉｒꎻｅｎｅｒｇｙｃｏｎｓｕｍｐｔｉｏｎＥＥＡＣＣ:７２３０㊀㊀㊀㊀ｄｏｉ:１０.３９６９/ｊ.ｉｓｓｎ.１００４－１６９９.２０２０.０５.０２１一种无线传感器网络感知覆盖空洞搜寻与修复方法∗杨明霞１ꎬ方㊀凯１ꎬ汪小东２ꎬ彭㊀丰３ꎬ周小龙１∗(１.衢州学院电气与信息工程学院ꎬ衢州３２４０００ꎻ２.浙江九州治水科技股份有限公司ꎬ衢州３２４０００ꎻ３.衢州华数广电网络有限公司ꎬ衢州３２４０００)摘㊀要:无线传感器网络部署在目标区域中用于感知和监测相关信息ꎬ由于网络能耗不均衡㊁环境干扰等影响ꎬ容易使某些节点提早失效ꎬ从而在网络中形成覆盖空洞ꎮ空洞的存在会严重影响无线传感器网络原本的功能和性能ꎬ因此提出一种无线传感器网络覆盖空洞的搜寻与修复方法以解决上述问题ꎮ首先利用相交节点的弦来构建和搜寻覆盖空洞ꎬ并将空洞修复问题转换为无向图求解最大团问题ꎬ从而实现以最少移动节点和最低重叠覆盖完成对空洞的修复ꎮ实验结果表明提出的方法能够高效地搜寻到覆盖空洞并完成修复ꎬ且算法的时间复杂度和能量效率都高于其他方法ꎮ关键词:无线传感器网络ꎻ覆盖空洞ꎻ搜寻和修复ꎻ能耗中图分类号:ＴＮ３９３㊀㊀㊀㊀文献标识码:Ａ㊀㊀㊀㊀文章编号:１００４－１６９９(２０２０)０５－０７５０－０７㊀㊀无线传感器网络由大量传感器节点组成ꎬ节点之间通过自组织的方式构成一个传感网络ꎮ将传感网络部署在目标区域中能够有效的监测该区域中发生的事件ꎮ但由于网络内部能耗不均衡以及节点被物理破坏等因素的影响ꎬ使得传感网中的节点很难保持一致的生存时间ꎬ而某些节点提早死亡(能量耗尽或被破坏)会形成网络覆盖空洞ꎬ这些空洞位置的信息和事件则无法进行监测ꎬ某些覆盖空洞甚至会导致部署的无线传感器网络失去价值ꎮ因此研究网络空洞的发现和修复方法具有重要的意义ꎮ现有的空洞修复研究主要利用可移动传感器节点或改变节点感知半径实现修复ꎬ如ＫｈａｌｉｆａＢ通过计算空洞面积来获取修复空洞所需的移动节点数量ꎬ并充分考虑覆盖冗余度㊁节点剩余能量和移动距离实现对空洞的修复[１]ꎮＺｈａｎｇＹ在随机部署的无线网络中利用节点剩余能量预测节点的寿命ꎬ然后选取适当比例的短寿命节点ꎬ最后通过计算覆盖率和相关评估标准来评估空洞的位置[２]ꎮＫｈａｌｉｆａＢ为降低移动节点的使用数量ꎬ首先通过调节节点的感知范围来修复空洞ꎬ如果仍无法实现对空洞的完全覆盖ꎬ则继续采用少量的第５期杨明霞ꎬ方㊀凯等:一种无线传感器网络感知覆盖空洞搜寻与修复方法㊀㊀移动节点[３]ꎮＫｈｅｄｒＡＭ针对异构无线传感器网络提出一种分布式空洞监测和预测方法ꎬ并提出一种修复方案ꎬ有效利用节点移动性来优化平均覆盖率和平均移动距离[４]ꎮＥｌＫｈａｍｌｉｃｈｉＹ针对网络随机部署导致的覆盖空洞问题ꎬ提出一种基于梯度算法和聚类技术的恢复方法ꎬ以检测整个ＷＳＮ中的冗余传感器节点ꎬ并将其重新定位以修复已识别的网络空洞[５]ꎮＫａｎｇＨ提出一种ＡＯＡ的无线传感器网络空洞修复方法ꎬ利用移动节点修复目标空洞ꎬ通过多次迭代完成对空洞的全面覆盖[６]ꎮＦｅｎｇＸ通过分析传感器网络的最大简单子网拓扑结构确定空洞边界ꎬ然后计算空洞边界的多边形ꎬ最后激活空洞内待激活的静态节点实现对空洞的修复[７]ꎮＴｉａｎＹ提出了一种基于合作概率覆盖模型的新型覆盖漏洞检测算法ꎮ利用该方法可以将监测区域的覆盖问题转化为距离关系问题ꎮ根据Ｖｏｒｏｎｏｉ划分方法可以将高密度和随机分散的传感器网络划分为多个Ｖｏｒｏｎｏｉ区域ꎬ然后通过分析节点之间的距离关系来判断监视区域的覆盖范围是否出现空洞ꎮ然后通过唤醒覆盖空洞内的一些睡眠节点完成修复[８]ꎮＬｕＸ提出一种具有优先级机制的空洞修复算法ꎬ该算法根据异构混合网络的空洞大小确定优先级进行空洞修补ꎬ并提高了覆盖率ꎬ有利于海洋环境中无线传感器网络(ＷＳＮ)的空洞修补[９]ꎮＫｈａｌｉｆａＢ采用模糊推理机制来选择移动节点以修复空洞区域ꎮ所有相邻的传感器相互通信以估计覆盖空洞的大小和位置ꎮ每个传感器考虑其自身的剩余能量㊁与空洞的距离及其冗余度来评估其用于修复的可行性ꎬ然后选择最合格的传感器来修补网络空洞[１０]ꎮ目前在ＷＳＮ覆盖空洞的查找和修复方面的研究已取得了较多优秀的成果ꎬ但仍然存在两方面的问题:①空洞查找准确性不足ꎻ②空洞修复的代价偏高(能耗㊁节点数量㊁修复时间)ꎮ因此本文提出一种新型的覆盖空洞搜寻与修复方法ꎬ试图以低代价㊁高修复率来完成对覆盖空洞的修复ꎮ１㊀相关模型与假设１.１㊀相关模型本文以同构无线传感器网络为研究对象ꎬ在监测区域中部署Ｎ个传感器节点ꎬ其中包含若干可移动节点ꎬ每个节点能够获取其感知范围内发生的事件(感知范围为以节点为中心ꎬ半径为ｒ的圆盘)ꎮ节点的通讯半径为Ｒꎬ且Ｒȡ２ｒ[１１－１３]ꎮ网络在部署后已利用ＧＰＳ或定位技术获得节点的位置坐标ꎮ如果两节点间的距离小于等于通讯半径Ｒꎬ则这两个节点被称为互相邻居节点ꎬ我们以表示节点Ｖ的邻居节点集合ꎮ本文由感知范围相互重叠的一系列传感器节点实现对目标区域的覆盖ꎮ１.２㊀相关定义①空洞边界㊀由一系列相互连接的传感器节点构成的圈ꎬ且圈内区域未被传感器节点的感知范围完全覆盖ꎬ如图１所示ꎬ图中传感器节点ｎ１－ｎ２－ｎ３－ｎ４－ｎ５－ｎ６构成了一个圈ꎬ但该圈内的区域未被感知区域完全覆盖ꎬ所以ｎ１－ｎ２－ｎ３－ｎ４－ｎ５－ｎ６即为一个空洞边界ꎮ图１㊀覆盖空洞示意图②关键弦㊀如果传感器节点ｖ与其邻居节点集合中的若干个节点存在感知范围重叠的情况ꎬ则节点ｖ对应的感知范围边界上会存在交点ꎬ按顺时针方向搜索交点ꎬ然后将该感知范围边界上相邻的交点以直线方式进行连接得到若干条弦ꎬ同时如果弦的两个端点属于两个不同的传感器节点ꎬ则该段弦被定义为关键弦ꎮ如图１中节点ｎ１与邻居节点ｎ２和ｎ６之间共存在４个交点ꎬ那么该节点就存在３条弦ꎬ而只有弦的两个端点ｐ１和ｐ６分别属于两个不同的邻居节点ｎ２和ｎ６ꎬ因此该弦被称为关键弦ꎬ而弦的端点ａ和ｐ１都由同一个节点ｎ２和ｎ１相交产生ꎬ因此该弦不是关键弦ꎬ同理弦也非关键弦ꎮ③空洞弦㊀如果某个节点的关键弦的任何部位都不在其邻居节点的感知范围内ꎬ则该弦被称为空洞弦ꎬ如图１中表示一条空洞弦ꎮ④空洞顶点㊀空洞弦对应的两个端点都称为空洞顶点ꎬ如图１中交点ｎ１㊁ｎ２㊁ｎ３㊁ｎ４㊁ｎ５㊁ｎ６都为该空洞的顶点ꎮ⑤邻居空洞顶点㊀若一系列空洞顶点属于同一个空洞ꎬ且顶点之间的距离小于等于２ˑｒꎬ则这两个顶点就称为邻居空洞顶点ꎬ如图１中ｐ６与ｐ１为相互邻居节点ꎬｐ６和ｐ２也为相互邻居顶点ꎮ⑥空洞修复位置㊀该位置处于覆盖空洞内ꎬ如果将一个节点放置在该位置上ꎬ则能够完成部分空洞的修复ꎮ１５７传㊀感㊀技㊀术㊀学㊀报ｃｈｉｎａｔｒａｎｓｄｕｃｅｒｓ.ｓｅｕ.ｅｄｕ.ｃｎ第３３卷２㊀空洞搜寻方法本文根据１.２小节的相关定义来搜寻传感网络中存在的空洞ꎬ查找空洞分为两个步骤ꎬ如下所示:步骤１㊀搜索传感器网络Ｎ中所有的关键弦ꎬ假设为节点ｖ的邻居节点集合ꎬ从中查找所有与节点ｖ相交的节点ｕɪꎬ由于Ｒȡ２ｒꎬ因此节点ｖ只可能和其邻居节点相交ꎮ按顺时针方向查找与节点ｖ感知边界的交点ꎬ并查找到所有关键弦ꎮ然后从这些关键弦中查找出空洞弦ꎬ具体算法如表１所示ꎮ表１㊀空洞弦查找方法空洞弦查找算法Ｒｅｌａｔｅｄｓｙｍｂｏｌｓ:Ｓｎ:ＮｏｄｅｓｅｔｉｎｓｅｎｓｏｒｎｅｔｗｏｒｋＮꎻＥｈｃ:ＳｅｔｏｆｈｏｌｅｃｈｏｒｄｓꎻＳｎｇｂｖ:ＮｅｉｇｈｂｏｒｓｅｔｏｆｎｏｄｅｖꎻＳｃｃｖ:ＫｅｙｃｈｏｒｄｓｏｆｎｏｄｅｖꎻＳｉｔｓｖ:ｓｅｔｏｆｓｅｎｓｉｎｇｄｉｓｋｉｎｔｅｒｓｅｃｔｉｏｎｐｏｉｎｔｓｏｆｎｏｄｅｖｗｉｔｈｉｔｓｎｅｉｇｈｂｏｒｎｏｄｅｕꎻ(ｊꎬｋ):ＴｈｅｔｗｏｉｎｔｅｒｓｅｃｔｉｏｎｓｊａｎｄｋｔｈａｔｍａｋｅｕｐｔｈｅｃｈｏｒｄｓꎻＩｎｐｕｔ:ＳｎａｎｄＳｎｇｂｖＡｌｇｏｒｉｔｈｍ:１:Ｅｈｃѳ⌀２:ｆｏｒｖｉｎＳｎ３:㊀ｆｏｒｕｉｎＳｎｇｂｖ４:㊀㊀Ｓｉｔｓｖѳｓｅｎｓｉｎｇｄｉｓｋｉｎｔｅｒｓｅｃｔｉｏｎｏｆｎｏｄｅｕａｎｄｎｏｄｅｖ５:㊀ｅｎｄｆｏｒ６:㊀ＳｉｔｓｖＳｏｒｔｃｌｏｃｋｗｉｓｅ７:㊀ｆｏｒｊｉｎＳｉｔｓｖ８:㊀㊀ｋѳｎｅｘｔｉｎｔｅｒｓｅｃｔｉｏｎｐｏｉｎｔｏｆｊ９:㊀㊀ｉｆ(ｉｎｔｅｒｓｅｃｔｉｏｎｊａｎｄｉｎｔｅｒｓｅｃｔｉｏｎｋｂｅｌｏｎｇｔｏｄｉｆ￣ｆｅｒｅｎｔｎｅｉｇｈｂｏｒｎｏｄｅｓ)１０:㊀㊀㊀ＳｃｃｖѳＳｃｃｖɣｊｋ１１:㊀㊀ｅｎｄｉｆ１２:㊀ｅｎｄｆｏｒ１３:㊀ｆｏｒｃｖｉｎＳｃｃｖ１４:㊀㊀ｆｏｒｕｉｎＳｎｇｂｖ１５:㊀㊀㊀ｉｆ(ｃｖｉｓｎｏｔｗｉｔｈｉｎｔｈｅｓｅｎｓｉｎｇｒａｎｇｅｏｆａｎｙｎｅｉｇｈｂｏｒｎｏｄｅｓ)１６:㊀㊀㊀㊀ＥｈｃѳＥｈｃɣｃｖ１７:㊀㊀㊀ｅｎｄｉｆ１８:㊀㊀ｅｎｄｆｏｒ１９:㊀ｅｎｄｆｏｒ２０:ｅｎｄｆｏｒ步骤２㊀从步骤一中筛选得到的空洞弦ꎬ在这个步骤中我们利用空洞弦集合Ｅｈｃ来确定真正需要修复的空洞ꎮ需要说明的是在空洞弦集合Ｅｈｃ中并非所有的弦都是空洞的边界ꎬ也存在某些空洞弦是无效边界ꎬ如图２所示ꎮ图２㊀空洞弦与覆盖空洞查找图２(ａ)中存在一个真实的覆盖空洞ꎬ该空洞的边界由弦组成ꎬ这种空洞是真实存在的ꎬ是需要修复的ꎮ图２(ｂ)三个节点之间不存在空洞ꎬ但根据步骤１ꎬ仍然能够搜索到三条空洞弦ꎬ分别是㊁和ꎬ但很明显这三条弦无法组合成一个空洞ꎮ因此需要根据空洞弦确定网络中真实存在的空洞ꎮ图２(ａ)和图２(ｂ)分别代表真实存在的空洞和无空洞两种情况ꎬ但我们如果将空洞弦所有的顶点进行连接会发现差异ꎮ如图２(ａ)中将所有弦的顶点两两连接得两个三角形Δｐ１ｐ２ｐ３和Δｐ４ｐ５ｐ６ꎬ三角形Δｐ１ｐ２ｐ３位于节点ｎ１ꎬｎ２和ｎ３组成的区域Δｎ１ｎ２ｎ３内部ꎬ那么Δｐ１ｐ２ｐ３即为一个真实的覆盖空洞ꎮ三角形Δｐ４ｐ５ｐ６不包含在Δｎ１ｎ２ｎ３中ꎬ因此Δｐ４ｐ５ｐ６不是一个真实的覆盖空洞ꎮ图２(ｂ)中将空洞弦的端点两两相连ꎬ得到三角形Δｐ１ｐ２ｐ３ꎬ同样将三个节点ｎ１ꎬｎ２和ｎ３连接得到的三角形Δｎ１ｎ２ｎ３ꎬ而Δｐ１ｐ２ｐ３并不在三角形Δｎ１ｎ２ｎ３内ꎬ两个图形是相交的情况ꎬ因此Δｐ１ｐ２ｐ３不是真实的覆盖空洞ꎮ综上所述ꎬ可以根据弦顶点构成的图形是否在相应节点构成的图形内部来确定覆盖空洞是否存在ꎮ覆盖空洞确定的具体方法如表２所示ꎬ在该步骤弦顶点之间的连接需要知道弦顶点的实际坐标ꎬ而弦的顶点实际是由两个相邻节点感知边界相交得到ꎬ因此可根据节点的坐标计算弦顶点的坐标ꎮ假设两个相邻节点的坐标分别为(ｘｉꎬｙｉ)和(ｘｊꎬｙｊ)ꎬ那么对应弦顶点的坐标(ｘ１ꎬｙ１)和(ｘ２ꎬｙ３)如式(１)㊁式(２)所示ꎮｘ１＝ｘｊ＋ｘｉ２＋ｙｊ－ｙｉ２ｄˑ４ｒ２－ｄ２ｙ１＝ｙｊ＋ｙｉ２＋ｘｊ－ｘｉ２ｄˑ４ｒ２－ｄ２ìîíïïïï(１)ｘ２＝ｘｊ＋ｘｉ２＋ｙｊ－ｙｉ２ｄˑ４ｒ２－ｄ２ｙ２＝ｙｊ＋ｙｉ２＋ｘｊ－ｘｉ２ｄˑ４ｒ２－ｄ２ìîíïïïï(２)２５７第５期杨明霞ꎬ方㊀凯等:一种无线传感器网络感知覆盖空洞搜寻与修复方法㊀㊀表２㊀覆盖空洞搜索方法覆盖空洞所搜算法Ｒｅｌａｔｅｄｓｙｍｂｏｌｓ:Ｓｇ:ＳｅｔｏｆｇｒａｐｈｓｏｂｔａｉｎｅｄｂｙｃｈｏｒｄｓｖｅｒｔｅｘｃｏｎｎｅｃｔｉｏｎꎻＥｈｃ:ＳｅｔｏｆｈｏｌｅｃｈｏｒｄｓꎻＳｈｏｌｅ:ＳｅｔｏｆＮｅｔｗｏｒｋｃｏｖｅｒａｇｅｈｏｌｅꎻＩｎｐｕｔ:ＥｈｃＡｌｇｏｒｉｔｈｍ:１:Ｓｈｏｌｅѳ⌀２:Ｓｇѳ⌀３:ｆｏｒｃｉｎＳｇ４:㊀ｂѳＮｏｄｅｇｒａｐｈｃｏｒｒｅｓｐｏｎｄｉｎｇｔｏｇｒａｐｈｃ５:㊀ｉｆ(ｇｒａｐｈｉｃｂｃｏｎｔａｉｎｓｇｒａｐｈｉｃｃ)６:㊀㊀ＳｈｏｌｅѳＳｈｏｌｅɣｂ７:㊀ｅｎｄｉｆ８:ｅｎｄｆｏｒ基于上述空洞搜寻方法ꎬ搜寻到了网络中的覆盖空洞ꎬ并确定了空洞的边界ꎬ如图３所示ꎬ图中存在两个封闭的多边形ａ和ｂꎬ其中图形ａ包含在ｂ内ꎬ且不相交ꎬ可以确定图形ａ为网络真实空洞ꎬ而图形ｂ不是网络空洞ꎮ组成空洞的传感器节点为４㊁２㊁５㊁７㊁６ꎬ空洞的边界由点集{ｈ５ꎬｈ４ꎬｈ３ꎬｈ２ꎬｈ１}构成ꎮ图３㊀空洞搜寻结果示意图３㊀空洞修复方法根据论文１~２章节ꎬ可以确定传感器网络中的覆盖空洞ꎬ在本章节中计划利用空洞附近的可移动节点实现对网络空洞的修复ꎮ如果使用少量的可移动节点即可完成空洞修复ꎬ那么对提高覆盖率和降低修复代价是非常有利的ꎮ本文通过将空洞修复问题转换为求解无向图最大团问题ꎬ从而以低代价完成网络空洞的修复ꎮ在介绍空洞修复方法前ꎬ我们先给出一个基础的理论知识ꎮ假设存在两个点分别为ｐ和ｑꎮ根据这两个点ꎬ可以确定两个半径为ｒ的圆ꎬ使得这两个点也位于圆上ꎬ如图３(ａ)中存在两个点ｐ１和ｐ２ꎬ根据这两个点ꎬ可以确定两个以ｎ１和ｎａ为圆心㊁半径为ｒ的圆ꎬ点ｐ１和ｐ２都位于这两个圆上ꎮ那么圆ｎ１和ｎａ的坐标可通过式(３)㊁式(４)计算得到ꎮｘ１＝ｘｍ＋ｒ２－(ｄ/２)２ˑ(ｙｐ－ｙｑ)ｄｙ１＝ｙｍ＋ｒ２－(ｄ/２)２ˑ(ｘｐ－ｘｑ)ｄìîíïïïïïï(３)ｘａ＝ｘｍ－ｒ２－(ｄ/２)２ˑ(ｙｐ－ｙｑ)ｄｙａ＝ｙｍ－ｒ２－(ｄ/２)２ˑ(ｘｐ－ｘｑ)ｄìîíïïïïïï(４)式(３)㊁式(４)中(ｘｐꎬｙｐ)表示点ｐ的坐标ꎬ(ｘｑꎬｙｑ)表示点ｑ的坐标ꎬ这两个坐标值可根据式(１)㊁式(２)计算得到ꎻｘｍ＝(ｘｐ＋ｘｑ)/２ꎬｙｍ＝(ｙｐ＋ｙｑ)/２ꎮ图４㊀空洞覆盖图我们根据第２章节获得了覆盖空洞集合Ｓｈｏｌｅꎬ即已经确定了空洞和相应的空洞弦ꎮ我们根据邻居空洞顶点的定义(见１.２小节)构建无向图Ｇ(ＶꎬＥ)ꎬ其中Ｖ表示空洞顶点ꎬ如图４(ａ)中ｐ１－ｐ７ꎻＥ表示空洞顶点之间的边ꎬ如果两空洞顶点之间的距离小于等于２倍感知半径ｒꎬ则这两个顶点之间连接一条边ꎬ否则这两个顶点之间不存在边ꎮ构建了覆盖空洞顶点的无向图Ｇ后ꎬ利用文献[１４]提出的方法求得无向图中所有的子团ꎮ每个子团即代表空洞中的一个修复位置(其定义见１.２小节)ꎮ为使用最少可移动节点完成对空洞的修复ꎬ本文每次仅选择最大子团对应的位置修复ꎬ如图４(ａ)中网络空洞构建的无向图Ｇ的最大子团仅包含两个点ꎬ分别是ｐ１和ｐ２ꎬ那么基于式(３)㊁式(４)和点ｐ１和ｐ２确定待修复位置ꎬ这个修复然后将可移动节点ｎａ移动到该修复位置上ꎮ图４(ｂ)中网络空洞构建的无向图Ｇ的最大子团包含４个顶点ꎬ分别是ｐ８㊁ｐ７㊁ｐ６㊁ｐ３ꎬ那么根据这四个点确定一个修复位置ꎬ并将可移动节点ｎａ移动到修复位置上ꎬ完成对空洞的部分修复ꎮ到此就完成了空洞修复的一次迭代ꎬ然后接着迭代修复方法ꎬ直到网络覆盖面积不再增加为止ꎬ空洞修复算法结束ꎮ３５７传㊀感㊀技㊀术㊀学㊀报ｃｈｉｎａｔｒａｎｓｄｕｃｅｒｓ.ｓｅｕ.ｅｄｕ.ｃｎ第３３卷４㊀实验分析实验采用ＭＡＴＬＡＢＲ２０１８ｂ平台进行仿真ꎬ传感器节点的最大感知半径为２０ｍꎬ最大通讯半径为４０ｍꎬ部署区域为一个５００ｍˑ４００ｍ的矩形区域ꎮ为验证本文提出的空洞搜寻与修复方法的性能ꎬ实验构建了两种形状的网络空洞ꎬ如图５所示ꎬ实验中部署不同数量的静态节点和可移动节点ꎮ实验验证本文提出的方法和文献[１５－１７]提出的空洞发现与修复方法进行对比分析ꎮ图５㊀网络空洞形状４.１㊀网络空洞搜寻时间分析在监测区域中部署两种形状的传感器网络(如图５所示)ꎬ验证不同节点密度情况下空洞搜寻方法的相关性能ꎬ实验结果分别如图６和图７所示ꎬ图６为在部署不同数量的传感器节点情况下ꎬ搜寻网络空洞所消耗的时间ꎬ横坐标表示部署节点的数量ꎬ纵坐标表示空洞平均搜寻时间ꎮ图６㊀空洞搜寻平均时间图７㊀组成空洞的节点数量实验结果表明随着网络中部署节点数量的增加ꎬ本文提出的方法和其他三种方法的空洞搜寻时间都会近似呈线性增加ꎮ这种现象主要是由于网络节点数量增加ꎬ网络拓扑结构变得更加复杂ꎬ而四种空洞搜寻方法都需为针对网络中每个节点进行计算ꎬ因此导致空洞搜寻时间会增加ꎮ同时本文方法搜寻空洞的时间低于其他三种方法ꎬ因为本文提出的方法是利用节点覆盖范围的重叠交点的弦和简单的集合方法判断定位空洞ꎬ在空洞的构建和确定上计算复杂度较低ꎬ因此其搜寻空洞的时间最短ꎮ文献[１６]采用分布式的空洞定位方法ꎬ该过程需要节点间密切且大量的信号交互ꎬ该过程需要消耗大量的时间ꎮ文献[１７]采用网络拓扑最大子团和聚类策略来确定网络空洞ꎬ而最大子团的计算和聚类策略相对耗时ꎬ因此消耗的时间高于本文提出的方法ꎮ实验结果表明随着网络中部署节点数量的增加ꎬ４种方法构成网络空洞的平均节点数量会降低ꎬ因为监测区域确定的情况下ꎬ部署的节点数量越多ꎬ空洞也会逐渐变小ꎬ则空洞边缘的节点数量降低ꎮ本文提出的方法低于文献[１５－１６]所提出的方法且与文献[１７]的空洞搜寻方法确定的空洞边缘节点数量基本相同ꎮ表明本文提出的方法和文献[１７]提出的方法能够更准确地确定覆盖空洞边界ꎮ４.２㊀空洞修复性能分析本文算法包括空洞定位和空洞修复两个部分ꎬ通过派遣可移动节点到覆盖空洞的某些位置来实现对空洞的感知覆盖ꎮ实验中通过部署一定数量的传感器节点ꎬ形成网络覆盖ꎬ但仍然存在一些空洞ꎬ其中可移动节点的比例占４０％ꎬ实验结果如图８所示ꎮ图８㊀修复空洞所需要移动节点数量图８结果表明随着部署区域中传感器节点的增加ꎬ四种修复方法修复网络空洞所需要的可移动节点数量逐渐降低ꎬ这是因为节点数量增加ꎬ空洞的规模会降低ꎬ需要更少的可移动节点即可完成空洞的修复ꎮ同时本文提出的方法需要的可移动节点数量远低于文献[１５－１７]所提出的方法ꎬ因为本文方法通过空洞定点邻居集合构建无向图Ｇꎬ并根据该无向图Ｇ的最大子团来确定修复位置ꎬ使得每个可移动节点能够在有限覆盖范围的情况下合理安排修复位置且本文提出的方法能够精准地确定空洞边界４５７第５期杨明霞ꎬ方㊀凯等:一种无线传感器网络感知覆盖空洞搜寻与修复方法㊀㊀(见图７)ꎬ因此它需要的可移动节点数量最少ꎮ文献[１７]在修复覆盖空洞时ꎬ虽然一定程度考虑了空洞修复所需的节点数量ꎬ但仅从空洞面积和每个节点覆盖范围上考虑ꎬ未充分考虑可移动节点的修复位置是否最合理ꎮ文献[１５－１６]的空洞边界确定准确率精度不高ꎬ导致修复空洞需要的可移动节点数量多于本文方法和文献[１７]提出的空洞修复方法ꎮ利用不同的空洞边界搜寻和修复方法得到的修复效果是不同的ꎬ本次实验验证四种方法在修复网络覆盖空洞时的性能ꎬ实验结果如图９所示ꎮ表示派遣可移动节点到覆盖空洞后ꎬ对网络的修复率ꎮ图９㊀可移动节点空洞覆盖率实验结果表明在空洞规模确定的情况下ꎬ随着派遣的可移动节点数量增加ꎬ四种方法对空洞的修复率都会提升ꎬ其中本文提出的修复方法在派遣相同数量的可移动节点时ꎬ空洞覆盖率最高ꎬ其次是文献[１７]提出的空洞修复方法ꎮ当派遣的可移动节点数量为１４个时ꎬ本文提出的修复方法使得空洞的覆盖率接近１００％ꎮ图１０㊀空洞平均修复时间四种方法的网络空洞平均修复时间如图１０所示ꎬ其中修复时间最长的是文献[１５]提出的方法ꎬ因为该方法能准确地确定空洞边界ꎬ导致空洞的规模比其他方法更大ꎬ需要派遣的可移动节点数量更多ꎬ因此其运算量最大ꎬ导致平均修复时间最长ꎮ本文提出的方法平均修复时间最短ꎬ因为利用空洞的邻居顶点无向图能够快速求取修复位置ꎬ这段时间远低于文献[１６－１７]提出的修复位置确定方法ꎬ因此修复空洞消耗的时间最短ꎮ５㊀总结本文针对目前无线传感器网络覆盖空洞存在空洞边界搜寻不准确ꎬ空洞修复代价偏高问题ꎬ提出一种低复杂度和高覆盖率的空洞搜寻与修复方案ꎬ该方案通过节点感知范围相交确定关键弦ꎬ然后从关键弦中确定空洞弦ꎬ接着根据节点连接得到的图形和覆盖区域之间的关系确定空洞是否真实存在ꎬ最后将空洞弦邻居顶点转换为无向图的最大团求解问题ꎬ计算最佳修复位置ꎬ并派遣可移动节点完成对网络空洞的覆盖ꎮ实验验证了本文方法具有较好的性能ꎮ后续工作希望进一步考虑可移动节点的能耗问题ꎬ将移动能耗纳入到空洞修复问题中ꎮ参考文献:[１]㊀ＫｈａｌｉｆａＢꎬＡｌＡｇｈｂａｒｉＺꎬＫｈｅｄｒＡＭꎬｅｔａｌ.ＣｏｖｅｒａｇｅＨｏｌｅＲｅｐａｉｒｉｎＷＳＮｓＵｓｉｎｇＣａｓｃａｄｅｄＮｅｉｇｈｂｏｒＩｎｔｅｒｖｅｎｔｉｏｎ[Ｊ].ＩＥＥＥＳｅｎｓｏｒｓＪｏｕｒｎａｌꎬ２０１７ꎬ１７(２１):７２０９－７２１６.[２]ＺｈａｎｇＹꎬＺｈａｎｇＸꎬＦｕＷꎬｅｔａｌ.ＨＤＲＥ:ＣｏｖｅｒａｇｅＨｏｌｅＤｅｔｅｃｔｉｏｎｗｉｔｈＲｅｓｉｄｕａｌＥｎｅｒｇｙｉｎＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋｓ[Ｊ].ｊｏｕｒｎａｌｏｆＣｏｍｍｕｎｉｃａｔｉｏｎｓａｎｄＮｅｔｗｏｒｋｓꎬ２０１４ꎬ１６(５):４９３－５０１.[３]ＫｈａｌｉｆａＢꎬＫｈｅｄｒＡＭꎬＡｌＡｇｈｂａｒｉＺ.ＡＣｏｖｅｒａｇｅＭａｉｎｔｅｎａｎｃｅＡｌ￣ｇｏｒｉｔｈｍｆｏｒＭｏｂｉｌｅＷＳＮｓｗｉｔｈＡｄｊｕｓｔａｂｌｅＳｅｎｓｉｎｇＲａｎｇｅ[Ｊ].ＩＥＥＥＳｅｎｓｏｒｓＪｏｕｒｎａｌꎬ２０１９ꎬ１０(１１):１５８２－１５９１.[４]ＫｈｅｄｒＡＭꎬＯｓａｍｙＷꎬＳａｌｉｍＡ.ＤｉｓｔｒｉｂｕｔｅｄＣｏｖｅｒａｇｅＨｏｌｅＤｅｔｅｃ￣ｔｉｏｎａｎｄＲｅｃｏｖｅｒｙＳｃｈｅｍｅｆｏｒＨｅｔｅｒｏｇｅｎｅｏｕｓＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔ￣ｗｏｒｋｓ[Ｊ].ＣｏｍｐｕｔｅｒＣｏｍｍｕｎｉｃａｔｉｏｎｓꎬ２０１８ꎬ１２４(２２):６１－７５.[５]ＥｌＫｈａｍｌｉｃｈｉＹꎬＭｅｓｍｏｕｄｉＹꎬＴａｈｉｒｉＡꎬｅｔａｌ.ＡＲｅｃｏｖｅｒｙＡｌｇｏｒｉｔｈｍｔｏＤｅｔｅｃｔａｎｄＲｅｐａｉｒＣｏｖｅｒａｇｅＨｏｌｅｓｉｎＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋＳｙｓｔｅｍｓ[Ｊ].ＪｏｕｒｎａｌｏｆＣｏｍｍｕｎｉｃａｔｉｏｎｓꎬ２０１８ꎬ１３(２):２５８－２６４.[６]ＫａｎｇＨꎬＤｏｎｇＹꎬＹａｎＦꎬｅｔａｌ.ＡＨｏｍｏｌｏｇｙａｎｄＡＯＡＢａｓｅｄＨｏｌｅＨｅａｌｉｎｇＳｔｒａｔｅｇｙｉｎＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋｓ[Ｃ]//２０１７３ｒｄＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＣｏｍｐｕｔｅｒａｎｄＣｏｍｍｕｎｉｃａｔｉｏｎｓ(ＩＣＣＣ).ＩＥＥＥꎬ２０１７:３３６－３４１.[７]ＦｅｎｇＸꎬＺｈａｎｇＸꎬＺｈａｎｇＪꎬｅｔａｌ.ＡＣｏｖｅｒａｇｅＨｏｌｅＤｅｔｅｃｔｉｏｎａｎｄＲｅｐａｉｒＡｌｇｏｒｉｔｈｍｉｎＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋｓ[Ｊ].ＣｌｕｓｔｅｒＣｏｍｐｕ￣ｔｉｎｇꎬ２０１９ꎬ２２(５):１２４７３－１２４８０.[８]ＴｉａｎＹꎬＣｈａｎｇＸꎬＯｕＹꎬｅｔａｌ.ＣｏｖｅｒａｇｅＨｏｌｅＤｅｔｅｃｔｉｏｎＡｌｇｏｒｉｔｈｍＢａｓｅｄｏｎＣｏｏｐｅｒａｔｉｖｅＰｒｏｂａｂｉｌｉｔｙＣｏｖｅｒａｇｅｉｎＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔ￣ｗｏｒｋｓ[Ｃ]//２０１８５ｔｈＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＣｌｏｕｄＣｏｍｐｕｔｉｎｇａｎｄＩｎｔｅｌｌｉｇｅｎｃｅＳｙｓｔｅｍｓ(ＣＣＩＳ).ＩＥＥＥꎬ２０１８:８３５－８４０.㊀[９]ＬｕＸꎬＷｕＱ.ＣｏｖｅｒａｇｅＨｏｌｅＰａｔｃｈｉｎｇｏｆＨｙｂｒｉｄＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋｉｎＭａｒｉｎｅＥｎｖｉｒｏｎｍｅｎｔ[Ｊ].ＪｏｕｒｎａｌｏｆＣｏａｓｔａｌＲｅｓｅａｒｃｈꎬ２０１９ꎬ９４(ｓｐ１):２９６－３００.[１０]ＫｈａｌｉｆａＢꎬＫｈｅｄｒＡꎬＡｌＡｇｈｂａｒｉＺꎬｅｔａｌ.ＦｕｚｚｙＬｏｇｉｃＡｐｐｒｏａｃｈｔｏＲｅｐａｉｒＣｏｖｅｒａｇｅＨｏｌｅｓｉｎＩｎｔｅｒｎｅｔｏｆＴｈｉｎｇｓＭｏｎｉｔｏｒｉｎｇＡｐｐｌｉｃａｔｉｏｎｓ[Ｊ].ＩＥＴＷｉｒｅｌｅｓｓＳｅｎｓｏｒＳｙｓｔｅｍｓꎬ２０１９ꎬ９(４):２２７－２３５.㊀[１１]陶建林ꎬ苗春雨ꎬ戴国勇.一种低能耗的无线传感器网络强栅５５７传㊀感㊀技㊀术㊀学㊀报ｃｈｉｎａｔｒａｎｓｄｕｃｅｒｓ.ｓｅｕ.ｅｄｕ.ｃｎ第３３卷栏重建方法研究[Ｊ].传感技术学报ꎬ２０１９ꎬ３２(２):１４１－１４７. [１２]戴光麟ꎬ杨志凯ꎬ周贤年ꎬ等.ＷＳＮ中一种流水式栅栏调度算法的研究[Ｊ].传感技术学报ꎬ２０１９ꎬ３２(４):１２２－１２６.[１３]赵小敏ꎬ方丁ꎬ毛科技.一种ＷＳＮ栅栏间隙修复优化方法[Ｊ].传感技术学报ꎬ２０１８ꎬ３１(１０):１１０－１１６.[１４]ＴｏｍｉｔａＥꎬＴａｎａｋａＡꎬＴａｋａｈａｓｈｉＨ.ＴｈｅＷｏｒｓｔ￣ＣａｓｅＴｉｍｅＣｏｍｐｌｅｘｉｔｙｆｏｒＧｅｎｅｒａｔｉｎｇＡｌｌＭａｘｉｍａｌＣｌｉｑｕｅｓａｎｄＣｏｍｐｕｔａｔｉｏｎａｌＥｘｐｅｒｉｍｅｎｔｓ[Ｊ].Ｔｈｅｏｒｅｔｉｃａｌｃｏｍｐｕｔｅｒｓｃｉｅｎｃｅꎬ２００６ꎬ３６３(１):２８－４２.[１５]ＡｎＷꎬＱｕＮꎬＳｈａｏＦＭꎬｅｔａｌ.ＣｏｖｅｒａｇｅＨｏｌｅＰｒｏｂｌｅｍｕｎｄｅｒＳｅｎｓ￣ｉｎｇＴｏｐｏｌｏｇｙｉｎＦｌａｔＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋｓ[Ｊ].ＷｉｒｅｌｅｓｓＣｏｍ￣ｍｕｎｉｃａｔｉｏｎｓａｎｄＭｏｂｉｌｅＣｏｍｐｕｔｉｎｇꎬ２０１６ꎬ１６(５):５７８－５８９. [１６]Ｓｏ￣ＩｎＣꎬＮｇｕｙｅｎＴＧꎬＮｇｕｙｅｎＮＧ.ＡｎＥｆｆｉｃｉｅｎｔＣｏｖｅｒａｇｅＨｏｌｅ￣ＨｅａｌｉｎｇＡｌｇｏｒｉｔｈｍｆｏｒＡｒｅａ￣ＣｏｖｅｒａｇｅＩｍｐｒｏｖｅｍｅｎｔｓｉｎＭｏｂｉｌｅＳｅｎｓｏｒＮｅｔｗｏｒｋｓ[Ｊ].Ｐｅｅｒ￣ｔｏ￣ＰｅｅｒＮｅｔｗｏｒｋｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓꎬ２０１９ꎬ１２(３):５４１－５５２.[１７]ＦｅｎｇＸꎬＺｈａｎｇＸꎬＺｈａｎｇＪꎬｅｔａｌ.ＡＣｏｖｅｒａｇｅＨｏｌｅＤｅｔｅｃｔｉｏｎａｎｄＲｅｐａｉｒＡｌｇｏｒｉｔｈｍｉｎＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋｓ[Ｊ].ＣｌｕｓｔｅｒＣｏｍｐｕ￣ｔｉｎｇꎬ２０１９ꎬ２２(５):１２４７３－１２４８０.杨明霞(１９７９ )ꎬ女ꎬ副教授ꎬ主要研究方向为无线传感器网络㊁深度学习等ꎻ方㊀凯(１９９２ )ꎬ男ꎬ硕士㊁助教ꎬ主要研究方向为无线传感器网络㊁深度学习等ꎻ㊀周小龙(１９８６ )ꎬ男ꎬ副教授㊁硕士生导师ꎬ主要研究方向为计算机视觉㊁无线传感网络㊁模式识别ꎮ６５７。

无线传感器网络中覆盖问题的解决方案比较与优化概述无线传感器网络（Wireless Sensor Network，WSN）是由许多分布在广泛区域内的无线传感器节点组成的网络。

这些传感器节点能够自主地感知环境中的各种物理和环境条件，并将收集到的信息通过网络传输给基站或其他节点。

覆盖问题是WSN中一个关键的挑战，它指的是如何保证网络中的每个位置都能够被足够数量的传感器节点覆盖到。

基本概念在讨论覆盖问题之前，我们应该了解一些基本概念。

无线传感器网络通常由三个不同的要素组成：传感器节点、目标区域和覆盖范围。

传感器节点：是WSN中的基本构建单元，它负责感知和传输数据。

目标区域：是指需要覆盖的区域。

覆盖范围：是指传感器节点的感知范围，即节点能够覆盖的最大距离。

解决方案比较针对无线传感器网络中的覆盖问题，研究人员提出了许多不同的解决方案。

下面我们将比较一些常见的解决方案。

1. 基于贪心算法的解决方案贪心算法是一种常见的解决覆盖问题的方法。

该算法通过选择覆盖范围内拥有最高能量的节点来进行部署。

通过这种方法，可以减少节点之间的重叠区域，提高整个网络的能量效率。

然而，贪心算法容易产生局部最优解，导致覆盖不均匀或覆盖区域较小的问题。

2. 基于优化算法的解决方案由于贪心算法的局限性，研究人员提出了基于优化算法的解决方案。

这些算法通过设计合适的目标函数和约束条件来最小化无线传感器网络的总能量消耗，并同时保证节点的覆盖范围。

常见的优化算法有遗传算法、粒子群优化和蚁群算法等。

这些算法能够找到全局最优解，但计算复杂度较高。

3. 基于机器学习的解决方案近年来，随着机器学习技术的快速发展，研究人员将其应用于无线传感器网络中的覆盖问题。

通过收集大量的训练数据和使用适当的机器学习算法，可以建立模型来预测传感器节点的最佳位置和覆盖范围，从而优化网络的覆盖性能。

机器学习方法在一定程度上解决了问题的复杂性和计算效率的问题，但对于大规模网络仍面临一定的挑战。

计算机时代2018年第4期0引言无线传感器网络（WirelessSensor Networks,WSN ）对人类的生活和生产方式带来巨大的变革，被认为是21世纪最重要的技术之一。

无线传感器网络由微机电系统的支持发展而来，是一种分布式传感网络，其具有大规模、动态性、自组织、以数据为中心等特点，被广泛应用于军事国防、医疗健康、智能家居等各个方面[1]。

覆盖质量是无线传感器网络应用中最重要的问题。

评价传感器网络覆盖质量的一个重要指标是节点覆盖率[2]，如果节点覆盖率过低会导致网络中出现覆盖空洞，造成数据监测不准确，更为严重的可能会导致对目标区域监测数据错误。

无线传感器网络常被用于紧急救援、空间探索、军事应用等特殊环境。

由于应用环境特殊，传感器节点常被随机布撒于目标区域，并通过自组织形成网络。

因此恶劣的环境、节点能量耗尽以及动物入侵等因素的影响都有可能造成节点死亡，从而导致网络中会出现某些区域未被任何节点感知，形成覆盖空洞。

若不及时修复就可能引起节点通讯受阻、网络数据监测不准确等问题[3]，严重的还有可能引起网络瘫痪。

为了保证网络正常运行，需要对网络中出现的覆盖空洞采取合适的修复策略，以保证网络覆盖质量，维持网络正常运行。

1无线传感器网络特点相比于一般网络，无线传感器网络一般都应用于人类无法到达甚至危险的区域。

无线传感器网络节点的位置一般是固定不变的，只有极少数节点需要移动。

一般情况下通过随机部署节点，利用节点自组织DOI:10.16644/33-1094/tp.2018.04.007无线传感器网络覆盖空洞修复算法综述田晓光(河南大学计算机与信息工程学院，河南开封475000)摘要：无线传感器网络因具有自组织、可靠性、动态性等特点已被广泛应用到医疗、军事、智能家居等各方面。

在网络运行过程中，节点能量不足、外界环境等因素的影响使传感器节点死亡，造成节点对网络覆盖率降低，致使无线传感器网络出现覆盖空洞。

为了保证节点覆盖率，需要对覆盖空洞进行修复，文章详细介绍了几种网络覆盖空洞修复算法，并对算法做出分析。

如何应对无线传感器网络的节点失效与恢复无线传感器网络（Wireless Sensor Network，WSN）是一种由大量分布式无线传感器节点组成的网络系统，用于收集、处理和传输环境中的信息。

然而，由于节点的物理损坏、能量耗尽或通信故障等原因，节点失效成为无线传感器网络中常见的问题。

本文将探讨如何应对无线传感器网络的节点失效与恢复，以提高网络的可靠性和稳定性。

首先，对于节点失效的预测和检测是应对节点失效的关键。

通过监测节点的能量消耗、通信质量和硬件状态等指标，可以预测节点失效的可能性。

同时，定期检测节点的活跃性和可用性，及时发现并标记失效节点，有助于及时采取措施进行恢复。

其次，节点失效后的恢复策略也是至关重要的。

一种常见的恢复策略是通过节点的自愈能力进行恢复。

例如，当一个节点失效时，周围的节点可以自动接管其任务，维持网络的正常运行。

这种策略可以减少网络的中断时间和能量消耗，提高整个网络的可靠性。

另一种恢复策略是通过节点的替换进行恢复。

当一个节点失效时，可以将其替换为一个新的节点，以保持网络的完整性。

为了实现节点的替换，需要事先准备一些备用节点，并确保它们具备与原节点相同的功能和性能。

当一个节点失效时，可以将备用节点部署到相应位置，并重新配置网络，使其能够继续正常工作。

此外，还可以通过网络拓扑的优化来提高网络的容错性和恢复能力。

通过合理设计网络的拓扑结构，可以减少节点之间的依赖关系，降低节点失效对整个网络的影响。

例如，采用分层结构或多路径传输等技术，可以实现节点之间的冗余和多样性，从而提高网络的鲁棒性和可靠性。

另外，及时更新和维护节点的固件和软件也是应对节点失效的重要手段。

通过定期检查和更新节点的固件和软件，可以修复潜在的漏洞和故障，提高节点的稳定性和可靠性。

同时，及时修复网络中的漏洞和故障，可以减少节点失效的可能性，保持网络的正常运行。

最后，建立有效的监控和管理系统是应对节点失效的关键。

通过实时监测和记录节点的状态和性能，可以及时发现和处理节点失效的问题。

面向节点失效的无线传感器网络覆盖空洞修复算法包旭;巨永锋【期刊名称】《计算机测量与控制》【年(卷),期】2011(19)6【摘要】In order to preserve the coverage and ensure the efficiency of Wireless Sensor Networks (WSNs), a coverage - hole repair algorithm towards nodes failure is proposed in this paper. After clustering and redundant nodes scheduling, every node has a energy threshold, if node' s energy is lower than its threshold, it sends a failure message to its cluster head, the cluster head consideres all the neighbors of the failure node are preparatory boundary nodes at first, then judges every preparatory boundary nodes whether be a non - boundary node through the intersection angle with the failure node. In the last, the cluster head activates the redundant node within the sensing range of failure node which has the most boundary nodes as neighbor nodes. Analyzes and simulation on Matlab platform indicate that for one thing, this algorithm has a low time complexity; for another thing, the rounds of maintaining a certain coverage can increase 19% than in no repair condition, and the coverage efficiency has a grate relation with node density and node sensing radius.%为了保持无线传感器网络的覆盖率,保证网络有效性,提出了一种面向节点失效的无线传感器网络覆盖空洞修复算法;在网络分簇与簇内冗余节点调度已经完成的基础上,算法首先为每个节点设置一个能量阈值,当节点能量低于该阈值时立即向簇首发送失效信息,簇首收到信息后首先默认该失效节点的所有邻居节点都是空洞边界节点,然后通过计算失效节点与所有邻居节点的交点角来判断是否有邻居节点为非边界节点,最后在失效节点的感知半径内选择邻居节点(同时也是边界节点)个数最多的冗余节点激活;分析以及matl8b仿真表明,算法的复杂度较低,网络保持一定覆盖率的情况下运行轮数比采用算法之前增加了19%,同时算法的修复效率与网络节点密度以及节点监测半径也有密切关系.【总页数】4页(P1516-1518,1522)【作者】包旭;巨永锋【作者单位】长安大学,电子与控制工程学院,陕西,西安,710064;长安大学,电子与控制工程学院,陕西,西安,710064【正文语种】中文【中图分类】TP393【相关文献】1.基于移动节点的无线传感器网络覆盖空洞修复方法 [J], 王珊;王庆生;樊茂森2.无线传感器网络覆盖空洞修复算法综述 [J], 田晓光3.面向节点失效问题的无线传感器网络拓扑自愈算法 [J], 刘林峰;吴家皋;邹志强;陈行;钮麟4.混合型无线传感器网络覆盖空洞修复算法研究分析 [J], 高亚玲5.混合型无线传感器网络覆盖空洞修复算法 [J], 刘洲洲;张雷雷因版权原因，仅展示原文概要，查看原文内容请购买。

物联网环境中的无线传感器网络覆盖问题研究一、引言随着物联网技术的快速发展和广泛应用，无线传感器网络（Wireless Sensor Network，WSN）作为其重要组成部分，逐渐成为了物联网环境中的重要技术支撑。

WSN通过将大量分布在物理空间中的无线传感器节点相互连接，实现环境信息的采集、处理和传输，从而为物联网环境提供了大规模数据获取的能力。

然而，在实际应用中，WSN的覆盖问题成为了亟待解决的核心问题之一。

本文将重点研究物联网环境中的无线传感器网络覆盖问题，并提出一些解决方案和优化策略。

二、无线传感器网络组网及覆盖问题分析1. 无线传感器网络组网方式无线传感器网络的组网方式可以分为扁平型、层次型和混合型等多种。

扁平型网络采用相同的通信功率和网络拓扑结构，节点之间直接进行通信；层次型网络将所有节点分为多个层次，实现节点的聚合和管理；而混合型网络则是扁平型和层次型的综合应用。

不同的组网方式会直接影响无线传感器网络覆盖效果和性能。

2. 无线传感器网络覆盖问题无线传感器网络的覆盖问题主要包括区域覆盖、目标覆盖和覆盖率等方面。

区域覆盖是指无线传感器网络中的所有目标区域都能够被感知到，目标覆盖是指网络中的所有目标能够被至少一个节点感知到，而覆盖率则是指网络中被覆盖的目标数量与总体目标数量之比。

在物联网环境中，无线传感器网络必须保证高效的覆盖能力，以有效地监测和获取环境中的信息。

三、无线传感器网络覆盖优化策略1. 良好的节点部署节点部署是影响无线传感器网络覆盖效果的关键因素之一。

合理地部署节点可以提高整个网络的覆盖率和监测效果。

可以采用等距离、随机化或者优化算法等方式进行节点的部署。

例如，通过遗传算法、蚁群算法等优化算法可以优化节点部署方案，提高传感器节点的覆盖效果。

2. 多通道的利用无线传感器网络可以利用多通道技术来提高网络的覆盖能力。

多通道技术可以避免信道冲突和干扰，提高网络的通信质量和传输效率。

通过合理分配通道资源，可以避免频频发生的信号冲突，从而提高整个网络的覆盖效果。