基于随机游走的无线传感器网络覆盖洞修复

韩　蕊　张书奎,2　陈朋飞

1(苏州大学计算机科学与技术学院　江苏 苏州 215006)2(南京大学计算机软件新技术国家重点实验室　江苏 南京 210023)



基于随机游走的无线传感器网络覆盖洞修复

韩蕊1张书奎1,2陈朋飞1

1(苏州大学计算机科学与技术学院江苏 苏州 215006)2(南京大学计算机软件新技术国家重点实验室江苏 南京 210023)

近年来，无线传感器网络逐渐成为研究的热点。无线传感器网络中由于传感器节点能力的耗尽或失效导致原先被覆盖的区域变成无节点覆盖的区域，即覆盖空洞。针对覆盖空洞问题，提出基于随机游走的移动节点修复覆盖空洞算法。通过添加移动节点，运用融合了能量消耗和时延的随机游走方式指引移动节点寻找覆盖空洞，并进行填补。仿真实验的结果证明了此方法的有效性，移动节点寻找出的覆盖空洞的路径上在能量以及时延方面较优。

无线传感器网络覆盖洞随机游走移动节点修复

0　引　言

在传感器网络部署中，受自然环境或本身因素的影响，在检测区域形成部分覆盖空洞。覆盖空洞的存在极大地影响着无线传感器网络的性能。如何修复覆盖空洞引起了研究者的关注。

有的研究者提出了一些空洞修复方法，如：多重覆盖[1]，即通过部署较多的冗余节点，使网络达到k覆盖的状态，这样以减少覆盖空洞的存在。休眠轮值机制[2]将无线传感器网络中的节点分为活跃节点和非活跃节点。活跃节点周围出现空洞的时候，通过激活其感知范围内的非活跃节点，使得非活跃节点变为活跃节点，以修复存在的覆盖空洞，达到修复空洞的目的。二代节点[3]是当网络中存在覆盖空洞时再次散播节点以减少覆盖空洞。“虚拟力”[4]中假设节点之间存在吸引力以及排斥力，在这两种力之间寻找平衡点。基于几何图形的性质[5-10]，利用已知拓扑结构几何规则。通过相关的几何性质得出移动节点所要移动的“最佳”位置，并将节点移动到此“最佳”位置，以填补覆盖空洞。目前覆盖空洞的研究工作更多的关注于在已知覆盖空洞具体位置的情况下，利用空洞边缘节点的相关信息，通过添加节点或者是移动空洞边缘冗余节点至计算所得的最佳位置，以达到修复空洞的目的。本文针对用于填补空洞的节点对覆盖空洞的具体位置未知的情况下，提出基于随机游走的覆盖空洞修复方法，利用移动节点按照一定的规则在网络中寻找空洞边缘节点，并且路径上的能量消耗较少和时延较小。

1　相关工作

在无线传感器网络中，覆盖洞的存在极大地影响着网络的性能，如何探测出覆盖洞以及修复覆盖空洞成为研究的热点。

目前，覆盖洞探测的方法有：利用计算几何中图形[11,12]的相关性质进行覆盖洞的探测，利用数学中的统计概率来初步判断出覆盖洞的存在，利用探测点来监测空洞。

文献[13]中提出分布式无坐标洞检测的方法，每个节点保存其邻居节点的信息，通过判断其邻居节点是否能够围成一个环而判定该节点是否是覆盖洞边缘节点，进而判定覆盖洞的存在，此方法虽然能够探测出覆盖洞的存在，但却不能探测出细碎的洞。文献[14]中利用静态节点探测局部覆盖洞，即通过判定是否存在覆盖洞边缘交点来判定是否存在覆盖洞。

文献[15]中选取覆盖洞边缘的3个节点，将它们的感知区域抽象成一个以节点为圆心，感知半径为半径的圆。通过圆的相关性质计算出节点所需移至的最佳位置。

文献[16]的研究指出无线传感器网络中移动实体可使网络对于故障更灵活，简化数据采集，提高能源利用率，增强连通性，提高网络的生命周期以及网络的修复能力，增强网络的健壮性。如使用移动sink节点、移动簇头、移动继电器以及移动传感器节点[17]。随机游走的改进方法[18-21]，其中研究结果显示，有偏的随机游走可以在能耗和延迟方面很好地提高网络的性能。借鉴于以上的研究，将随机游走模型应用于无线传感器网络的覆盖洞修复过程中移动节点对覆盖洞的寻找。

2　问题描述

所谓覆盖空洞，即网络中未被任何节点覆盖的区域。如图1中所示，圆A、B、C、D、E、F所围成的中间区域，即为空洞。在无线传感器网络中，我们称之为覆盖空洞(简称覆盖洞)。

图1　空洞示意

定义1一系列邻接于覆盖洞的边缘节点组成了覆盖洞的边界。如图1所示，此覆盖空洞的边界即为{A,B,C,D,E,F,G,H}。

覆盖空洞会影响无线传感器网络的连通性，影响节点之间的通信，目标区域的信息不能被有效搜集到，严重影响无线传感器网络在应用中的性能。因此，修复覆盖洞具有非常重要的意义。

2.1网络环境

将无线传感器网络抽象成一个无向加权图G(E,V,ω)，其中V是节点的集合，节点个数为n。E为边集，每一条边赋予一定的权重值，包括能量消耗和时延DL,设能量集为E’={e1,e2,e3,…,en}。

网络中部署两类节点：静态节点和动态节点。静态节点利用文献[13]中的覆盖洞探测算法，通过判定自身是否是空洞边缘的节点，来断定是否存在覆盖洞，若该节点是空洞边缘节点，则表示覆盖洞存在。动态节点可在目标区域中任意移动，其作用是寻找覆盖洞，若找到了覆盖洞，则此移动节点就会依据相应的填补算法，填补覆盖洞。

网络中，每个传感器节点都能够对周围实行全方向的探测感知。传感器节点的覆盖(感知)范围是一个以节点为中心、感知半径为半径的圆，圆内的探测能力都是相同的。静态节点和动态节点都具备相同的感知半径和通信半径，节点的通信半径大于两倍的感知半径。目标区域内的所有传感器节点都位于同一个二维平面内，且节点的位置已知。

初始状态下，所有的静态节点随机地分布在二维空间。静态节点拥有一个邻居节点属性表，包括邻居节点的剩余能量，到该邻居节点所要消耗的能量，以及路径上的时延。同时，可将用来修复空洞的移动节点看成是一个粒子，这个粒子可以移动并可移至任意一个节点所在位置处。每个传感器节点的通信范围是一个半径为Rc的圆。在静态节点部署完毕后，将移动节点随机部署在目标区域内。初始阶段，移动节点拥有邻居节点的相关信息，包括到每个邻居节点的距离，以及到邻居节点所需要的能量消耗，以此来选择一个在寻找覆盖洞路径上的初始节点作为自己的源点。

2.2设计思想

首先，介绍图上的随机游走[22]：定义图G(V,E,ω)是一个有n个顶点，m条边的有权无向图，其中V是顶点集，E是边集，ω:V×V→R是连接权函数。进一步假设有一个粒子A，初始时在图G上的顶点V0处，Pij表示粒子A向它的一个邻居移动的转移概率，其计算公式[11]如下：

(1)

式中，ωi为邻居权重之和，即ωi=∑j∈Γ(i)ωij。

如果粒子A以概率Pij从顶点Vi游动到顶点Vj，并不断重复这一过程，那么被粒子A访问过的顶点就组成了一个随机序列Xn,n=0,1,2,…。

定义 2[22]有权无向图G(V,E,ω)上的随机游走为一随机序列：X0,X1,…,Xn,…,其中Xn表示粒子在n时刻的位置。并且，如果粒子在n时刻位于顶点Vi，那么下一时刻位于顶点Vj的概率为Pij。如图2所示，

图2　从Vi转至Vj的概率

在开始随机游走前，网络中的覆盖洞边缘节点都已确定。移动节点拥有一个邻居节点的信息表，并根据搜集到的邻居节点信息，判断其邻居节点集中是否存在覆盖洞边缘节点，若仅有一个，则无需执行随机游走的算法；若有多个，则计算转移概率，选出概率最大的那个节点。否则，选择一个距离其较近的邻居节点作为寻找覆盖洞的较优路径上的初始节点。移动节点首次移动的目标位置是此初始静态节点位置，初始静态节点根据相应的导航规则选择下一跳节点，并指导移动节点移至此下一跳节点处。同样下一跳节点根据相同的规则选择其下一跳节点，以此类推，直至移动节点寻找到覆盖洞。

3　算法设计

覆盖洞边缘节点用于确定覆盖洞，移动节点以找到此类节点为目的。覆盖洞边缘节点的判定可以通过判定其感知圆上是否存在空洞边缘交点。利用相关文献中提出的空洞边缘交点的算法，以下是该算法描述：

步骤1任意选择一个节点S。

步骤2创建节点S的邻居节点列表Ls。

步骤3计算出节点S与邻居列表中的邻居节点Si的交点Pi。

步骤4判断邻居列表Ls中除Si之外的节点能否覆盖交点Pi。

步骤5如果无其他邻居节点覆盖Pi，则Pi标志为空洞边缘交点。

步骤6重复此过程直至网络中所有空洞边缘交点标出。

网络中所有空洞边缘交点全部标出后，每个节点可以查看其感知圆上是否有空洞边缘交点。若有，则该节点为覆盖洞边缘节点；若无，该节点不是覆盖洞边缘节点。

3.1转移概率的计算

在覆盖洞的修复步骤中，其中需要移动节点根据一定的规则在网络中寻找存在的覆盖洞。规则最关键的是转移概率的计算。转移概率基于随机游动模型，相关文献中也给出了图上的随机游动模型的定义。

蚁群算法[23]是M.Dorigo提出的一种性能优良的启发式随机优化算法，采用正反馈机制实现分布式全局优化，通过信息素的不断更新达到最终收敛于最优路径上。文献[24]中研究者将蚁群算法用于无线传感器网络的路由设计，该算法能够较好地平衡了网络的能量消耗，能量消耗越少网络的生命周期越长。本文采用优化的蚁群算法[25]的转移概率思想，将节点中的能量消耗以及时延作为信息素矩阵。以下是本文的转移概率：

(2)

式中，E表示能量消耗的倒数矩阵，η=1/dl,dl为路径的时延矩阵,α[25]为控制相关的能量信息的可见性的参数，β[25]是控制路径上时延重要性的参数。Eij为节点i到邻居节点j的能量消耗的倒数，ηij为从节点i到节点j的路径上的时延的倒数。这样节点i会有较大的概率选择消耗能量少且延迟小的路径。

每个节点在选择下一跳节点时，计算邻居节点集中各个邻居节点的转移概率，从这些邻居节点中选出转移概率最大的节点。移动节点将移至静态节点通过计算转移概率而挑选出的下一跳邻居节点的位置作为自己的下一个时刻的位置。针对无线传感器网络中涉及到的信息因素，采用基于蚁群优化的转移概率，在本文的转移概率中添加相应的信息素[23]，用此转移概率选出较优的路径。因此，本文将路径上的时延，能量消耗作为蚁群算法中的信息素来形成转移概率，指导移动节点寻找出存在的覆盖洞时，所经过的路径在能量消耗和延时方面是较优的。

3.2移动节点修复位置的计算

移动节点在找到覆盖洞边缘节点后，将根据相应的位置计算方法来确定自己填补空洞的最终位置。以下是修复覆盖洞中确定移动节点位置的算法：

步骤1选择覆盖洞边缘节点B，以及它的周围邻居节点A并且A也是空洞节点。

图3　空洞边缘交点

步骤2计算AB的空洞边缘交点P(P只能被A，B覆盖，且不能被其他节点覆盖)且PA=PB。

如图3所示，A、B均为覆盖洞边缘节点，P为A和B的空洞边缘交点。

步骤3找出一点M使得，PM=R，并且AM=BM，则此点就是移动节点需要移动的位置。

步骤4算法结束。

图4　M点的位置

如图4所示。我们找出了空洞边缘交点P。在几何图形中，根据几何图形的性质得知PA的距离和PB的距离相等。在步骤3中，我们同样根据几何图形的性质，找出填补覆盖洞的移动节点最优位置M点处，M点距P点的长度为R(感知半径)，同时，保证M到A点的距离与M到B点的距离相等。根据几何图形性质，两个圆的圆心连线，取其中垂线上的点，这样中垂线上的点到两个圆心的距离相等。反之如果某个点到两个圆心的距离相等，这该点必定是在两圆心连线的中垂线上。步骤3中所取的点M到两圆的交点的距离为R，这表示M的感知圆和A、B的感知圆交于一点，三个圆的重叠区域最小。因此，M点填补的空洞的面积最大化，并且不会产生细碎的空洞。

3.3算法描述

利用覆盖空洞边缘节点算法找到覆盖洞节点，每个静态节点通过覆盖空洞交点算法查看自己是否是覆盖洞边缘节点。在网络中，每个节点都会设置一标志位flag，若该静态节点为覆盖洞节点，则将其flag标志设为1，否则设置为0。在此前提下，执行基于随机游走的移动节点修复覆盖洞算法，具体的步骤描述如下：

1. 任意选择一个移动节点M。

2. 移动节点M建立其邻居静态节点集L{L1，L2，…，Ln}。

3. 针对移动节点M的邻居静态节点集L{L1，L2，…，Li，…，Ln}中的所有节点，

1) 如果邻居集中有flag标志为1的节点，则说明此邻居节点为覆盖洞边缘节点，若有一个覆盖洞边缘节点，则转至步骤6。若有多个覆盖洞边缘节点，则计算这些覆盖洞边缘节点的转移概率Pij，即式(2)，并选择转移概率最大的节点，并转至步骤6。

2) 否则选取M的邻居静态节点集L{ L1，L2，…，Li，…，Ln}中距离M最小的节点i。

4. 判定节点i的邻居节点集中是否有flag标志为1的节点。只有一个覆盖洞边缘节点，则转至步骤6；若有多个覆盖洞边缘节点，则计算这些覆盖洞边缘节点的转移概率Pij，即式(2)，并选择转移概率最大的节点，并转至步骤6。

否则，计算节点i的邻居节点集Ni{Ni1，Ni2，…，Nij，…，Nin}中各个邻居节点的转移概率Pij，即式(2)。

5. 选择转移概率Pij最大的节点j，并且判定节点j；如果节点j是覆盖洞边缘节点，则转到步骤6，否则，转到步骤4 。

6. 算法结束。

在上述算法中，所有的覆盖洞边缘节点通过之前的覆盖洞边缘交点算法找出并作上标记。基于已找出的覆盖空洞节点，在步骤3中，节点在查看邻居节点的时候，首先根据flag标记位，优先判定邻居节点集中是否存在覆盖空洞边缘节点，若有，则算法结束，这样充分利用了覆盖空洞探测阶段的信息。否则，移动节点查看自己的邻居节点集中的每个邻居节点，选择距离M最近的静态节点，这样可以减少移动节点的移动时间，缩短整个修复过程的时延。在计算邻居节点集中每个邻居节点的转移概率时，能量消耗和时延作为参数。当所选择的邻居节点的能量消耗值越小，则此节点的转移概率值越大；当所选择的邻居节点的时延值dl越小时，ηij的值越大，则转移概率的值越大，选择该节点的概率也就越大。因此，在步骤4中节点会选出转移概率最大的邻居节点。

4　实　验

本文的关键点是在使用移动节点寻找存在的覆盖洞并且寻找过程中所产生的路径是一条在能量消耗和时延上都较优的修复路径。通过仿真实验，验证算法的有效性。

4.1实验的设置

本文使用Java平台进行仿真实验。首先，创建一个矩形区域，并在此区域中随机部署n个传感器节点，节点的感知半径为20m(其传输半径为50m)节点。

4.2仿真实验的分析

4.2.1参数调整

设置的目标区域为一个300×300 m2的二维正方形区域，在此区域内随机部署100个节点，部署后的初始状态如图5所示。

图5　部署初始状态

从图5中可以看出，部署后，目标区域中存在着不能被节点覆盖的地方，即前文所提及的覆盖空洞。为了便于描述，将这些覆盖空洞依次标记出。为了区分不同的节点，我们对区域中的部分节点进行标号。如图6所示。

图6　标号后的部署图

所标区域为H1，H2，H3，H4，H5，H6的目标区域均为空洞区域。在图6中，标出了部分节点, 部分覆盖空洞边缘节点有{15，18，40，11，28，64，35,73，20，17，3，12，46，54，22， 30，27，55，19，33，9 }。

在算法中，转移概率中参数的设计在导航中也起到了关键作用。α作为控制相关的能量信息的可见性的参数，β作为控制路径上时延重要性的参数。如图7所示，设置α=0.8，β=0.5，新添加移动节点最靠近节点10的位置处。

图7　α=0.8，β=0.5，目的节点为55

在实验结果中，移动节点根据算法选择的初始静态节点为10。根据本文的规则，移动节点所寻找出的覆盖空洞为H3，所形成的路径为10→19→55，能量消耗总和为47，总时延为19。

实验结果显示，本算法具有一定的可行性。根据初始条件，移动节点能够有效地选择距离自己较近的静态节点作为路径上的初始节点，并且在能量消耗以及时延的约束条件下，找到了覆盖空洞边缘节点55，相应的覆盖空洞是H3。

通过改变参数α和β，实验的结果会有所不同。设置α=0.8，β=0.2时，移动节点寻找出的空洞边缘节点20，而此时的路径为10→34→1→35→20，能量消耗总和为84，总时延为35。两种α、β的设置情况下，移动节点都同样的找出了覆盖空洞边缘节点，但在α=0.8，β=0.2的条件下，移动节点找到的覆盖空洞边缘节点是20，相应的找出覆盖空洞H5。从数据上可以看出，移动节点到节点55所经过的中间节点个数比到节点20所经过的中间节点数少，移动节点到节点55所消耗的能量比到节点20所消耗的能量少以及时延小。即到达覆盖洞H5的路径较到达覆盖洞H3的路径短(从节点个数来看)，且到覆盖洞H3的路径上的能量消耗以及时延较优。从图7中我们可以看出，与覆盖洞H5相比，移动节点的初始位置距覆盖洞H3较近，其中节点55相对于节点20距移动节点较近。当α=0.5，β=0.3时，移动节点的初始位置不变，所选取的起始静态节点为10，寻找到的覆盖空洞边缘节点为44，其为覆盖空洞H2的边缘节点，路径为10→34→44。能量消耗和为44，延时为16。

所以，合理的调整参数α、β的值，能够使得所找出的覆盖空洞在路径上的能量消耗以及时延方面较优。

4.2.2算法的有效性

本算法，在实际的实验中，能够得出和本文预期的结果相一致的实验结果。随机部署一个移动节点，移动节点在部署后，能够根据自身搜集到的信息，选择距离自身较近的静态节点，并且能够寻找到覆盖空洞边缘节点。经过不断的实验调试显示，α=0.5、β=0.3时，移动节点所找出的覆盖空洞节点的路径上能量消耗总和以及时延较优。因此，在α=0.5、β=0.3条件下，同样的，部署一个移动节点，比较此移动节点通往不同覆盖洞时，路径上能量消耗和时延。如表1中所示。

表1　到各个覆盖空洞能量消耗总和最

选择移动节点初始位置处为靠近节点10处，对比移动节点去往其他覆盖空洞的路径上所需要的能量总和以及时延总和。表1中，所选出的路径是指到达这个覆盖洞的所有路径中能量消耗和时延较优的一条路径。对比移动节点分别到达空洞H1,H2,H3,H4,H5,H6的路径，可以看出，根据文中的导航规则，移动节点到达覆盖洞H2的这一路径，所消耗的能量相对于到其他覆盖洞边缘节点所消耗的能量较少，时延较小。6条路径中，通往H2的路径最优，并且去往H2,H4,H5,H6的路径中，第二个节点都选择了34，这和最优路径上第二节点选择节点34所一致。

5　结　语

本文通过在随机部署的无线传感器网络中，提出了基于随机游走的覆盖洞修复算法。通过添加的移动节点，来寻找覆盖洞边缘节点，即覆盖洞。移动节点依据一定的判定规则寻找覆盖洞边缘节点，而本文的判定规则是根据计算出的转移概率来寻找下一个节点，转移概率综合考虑了能量消耗和时延这两个因素。在移动节点找到覆盖洞边缘节点，即找到覆盖洞后，又找出移动节点所需移至的最佳位置，更好地修复填补覆盖洞。如何在动态的网络中利用同样的随机游走的方式去修复覆盖洞是今后的研究方向。

[1] 刘明，曹建农，郑源,等.无线传感器网络多重覆盖问题分析[J]. 软件学报，2007，18(1)：127-136.

[2] 胥楚贵，邓晓衡，邹豪杰.无线传感器网络覆盖空洞修复策略[J].传感技术学报，2010，23(2)：256-259.

[3] Wang L，Guo Y，Zhan Y. Security topology control method for wireless sensor networks with node-failure tolerance based on self-regeneration [J]．Eurasip Journal of Wireless Communications and Networking，2014，16(10):1-11.

[4] Novella Bartolini，Annalisa Massini，Simone Silvestri. P&P:an asynchronous and distributed protocol for mobile sensor deployment[J].Wireless Network,2012，18(4) : 381-399.

[5] G Wang，G Cao，T La Porta. Movement-assisted Sensor Deployment[C]//IEEE Transactions on Mobile Computing． LOS ALAMITOS，USA:IEEE，June 2006.

[6] 徐鹏飞，陈志刚，邓晓衡．无线传感器网络中的分布式Voronoi覆盖控制算法 [J]． 通信学报，2010，31(8):16-25.

[7] 韩春延．基于距离的无线传感器网络覆盖洞修复方法[J]．传感器与微系统,2013，32(4):91-94.

[8] Prasan K, Jang Z T. Vector method based coverage hole recovery in wireless sensor[C]//Proceedings of the Communication Systems and Networks (COMSNETS)．Bangalore，2010.

[9] Hwa-Chun Ma， Prasan Kumar Sahoo，Yen-Wen Chen． Computational geometry based distributed coverage hole detection protocol for the wireless sensor network[J]．Journal of Network and Computer Applications， 2011，34:1743-1756.

[10] 杨凯，刘全，张书奎，等．利用移动内点来修复传感器网络空洞的算法[J] ．通信学报，2012，33(9)：116-124.

[11] Zhiping Kang，Honglin Yu，Qingyu Xiong．Detection and Recovery of Coverage Holes in Wireless Sensor Networks[J]． Journal of Networks， 2013，8(4)：822-828.

[12] 戴国勇，陈麓屹，周斌彬，等．基于Voronoi图的无线传感器网络覆盖空洞检测算法[J]．计算机应用,2015，35(3):620-623.

[13] Li L，Hunter D K，Yang K．Distributed Coordinate-Free Hole Recovery[C]//IEEE Conference: Global Telecommunications， USA: San Francisco，2008:189-194.

[14] 李红，宋顺林．WSN中基于分布式的覆盖洞修复算法[J]．计算机工程，2012，38(16): 85-88.

[15] Wang Liangmin, Li Fei, Qin Ying．Resilient method for recovering coverage holes of wireless sensor network by using mobile nodes [J] ．Journal on Communications,2011,32(4) :1-8.

[16] Regis W Anne， Elijah Blessing Rajsingh．Mobile entities in wireless sensor networks: theory and performance analysis [J]．Ictact JOurnal on Communication Technology， 2013， 4(1): 661-668.

[17] Nitin Kumar, Dimitrios Gunopulos, Vana Kalogeraki．Sensor network coverage restoration[C]//IEEE International Conference．Marina del Rey,CA,USA:DCOSS 2005,June 30-July 1,2005.

[18] Wang Yaqi, Yang Xiaoyuan． A random walk evolution model of wireless sensor networks and virus spreading[J]．Chinese Physics B, 2013, 22(1) :1-7.

[19] 李强，何衍，蒋静坪．一种基于随机游走的聚类算法[J]．电子与信息学报， 2009， 31(3):523-526.

[20] Agata Fronczak，Piotr Fronczak． Biased random walks on complex networks: the role of local navigation rules[J]．Phys Rev E Stat Nonlin Soft Matter Phys，2009，8(2): 75-89.

[21] Annibaldi S V，Hopcraft K I．Random walks with power-law fluctuation in the number of steps[J]．Journal of Physics A: Mathematical and General，2002，35(2): 8635-8645.

[22] Lovász L．Random walks on graphs: A survey[J]．Bolyai Society Mathematical Study，Combinatorics，1993，2(8):1-46.

[23] Bhanu Prakash Lohani， Monika Jena，Sanjay Kumar Dubey．Energy Efficient Routing Using Random Walk and Best Route Selection for Sensor Networks[J]．International Jounal of Scientific & Engineering Research，2013，4(6):81-93.

[24] Liu Guangcong，Wu Huanhuan,Zheng Huijun．Ant colony optimization-based Qos routing in wireless sensor networks[J]．Computer Engineering and Applications，2011，47(20):102-104.

[25] Dorigo M，Maniezzo V，Colomi A．The ant system:optimization by a colony of cooperating agents[C]//IEEE Transactions on Systems Man & Cybemetics，1996，26(1):29-41.

[26] Heinzelman W，Chandrakasan A，Balajrishnan H．Energy Efficient Communication Protocols for wireless Microsensor Networks[C]// Proceedings of the 3rdAnnual Hawaii International Conference on System Science，2000:926-935.

RANDOM WALK-BASED COVERAGE HOLES RECOVERY IN WSN

Han Rui1Zhang Shukui1,2Chen Pengfei1

1(SchoolofComputerScienceandTechnology,SoochowUniversity,Suzhou215006,Jiangsu,China)2(StateKeyLabforNovelSoftwareTechnology,NanjingUniversity,Nanjing210023,Jiangsu,China)

In recent years, wireless sensor network has gradually become the focus of research. Because of the energy depletion or failure of the sensor node in WSN, original covered area will not be covered by any nodes, which is known as the coverage hole. In view of the coverage hole problem, we proposed the random walk-based algorithm for recovering coverage hole by mobile nodes. Through adding mobile nodes in wireless sensor network, the algorithm uses the random walk means which integrates the energy consumption and delay to guide the mobile node to find coverage holes, and then fill the holes. Through simulation experiment the result proved the effectiveness of the algorithm, the path of coverage hole searched out by mobile node is optimal in terms of energy and delay.

Wireless sensor networkCoverage holeRandom walkMobile nodeRecovery

2015-04-20。国家自然科学基金项目(61070169)。韩蕊，硕士生，主研领域：无线传感器网络。张书奎，教授。陈朋飞，硕士生。

TP393

A

10.3969/j.issn.1000-386x.2016.08.031