无线传感器网络中节点调度覆盖空洞的避免方法

摘要

本发明公开了一种用于无线传感器网络节点调度中覆盖空洞的避免方法，该方法在保证监测区域覆盖的前提下，根据节点的能量消耗情况，对节点状态进行合理分配：若剩余能量大于给定的阈值让其进入能量节约的休眠状态；若剩余能量小于给定的阈值，且该节点自身符合休眠条件，则该节点进入休眠时间更长的沉睡状态；若不符合休眠条件，则该节点向邻居节点发出求救信息，邻居节点进行自我检查是否符合支援条件进而对该节点进行支援。本发明主要用于解决节点调度机制中部分节点能量消耗过快，造成这些节点失效进而引起该节点所在区域的覆盖空洞问题，从而达到节约网络能量，有效延长整个网络的生存时间。

说明书

技术领域

本发明涉及无线传感器网络拓扑控制应用领域，尤其涉及一种无线传感器网络中节点调度覆盖空洞的避免方法。

背景技术

无线传感器网络是由大量密集部署在监测区域的传感器节点组成的一种网络监测系统，其主要任务是准确获取客观物理世界有价值的信息，自动实时监测目标和事件发生，并及时报告和处理事件，它拓展了人类对客观物理世界的感知范围,帮助人们更好了解并实时感知周围的客观环境。在环境监测、医疗护理、工业环境、交通及军事等领域具有较广泛的应用前景。

目前,在传感器网络的应用中，传感器节点是体积微小的嵌入式设备，采用能量有限的电池供电，且计算能力和通信能力都十分有限。节点调度机制充分利用了无线传感器网络应用的高覆盖冗余部署特性，通过节点间的相互协作合理组织节点间的工作状态，让满足覆盖冗余的节点轮流进入低功耗的休眠状态，达到节约能量，延长网络生存时间的目的。

但是受实际部署条件限制、节点覆盖冗余判别方法的不同、算法实施策略的不同和应用环境的多样性，使得节点调度机制执行后，存在某些节点由于休眠机会的不均等性引起能量过早耗尽或遭受到破坏而死亡，部分节点的提前失效必然会造成感知覆盖的空洞和通信网络的分块，从而影响监测信息获取的完整性，缩短网络的寿命，与节点调度延长网络生存时间的目标相违背。

发明内容

本发明的目的是提供一种无线传感器网络中节点调度覆盖空洞的避免方法，能够根据节点剩余能量和覆盖要求对节点状态进行调度，达到在节点调度机制中尽可能避免或延缓覆盖空洞问题的产生，从而达到延长网络生存时间的目的。

本发明采用下述技术方案：一种无线传感器网络中节点调度覆盖空洞的避免方法，包括以下步骤：

（1）、设节点的初始态为空闲态，首先判断该节点是否有数据包需要处理：如果有数据需要处理，则节点进入活动态，处理数据后进入步骤（2）；若无数据包需要处理，则进入步骤（2）；

（2）、计算该节点被邻居节点覆盖的覆盖冗余率δ，进入步骤（3）；

（3）、判断该节点当前剩余能量值E_i是否大于设定的能量阈值E_{th_fsleep}，若是，则进入步骤（4）；若否，则进入步骤（6）；

（4）、判断该节点是否符合休眠条件：若该节点符合休眠条件，则该节点向邻居节点发送预休眠消息，进入预休眠状态，同时启动一个延迟计时器T_backoff，进入步骤（5）；若不符合休眠条件，返回步骤（1）；

（5）、该节点如果在T_backoff内收到邻居节点发送的预休眠消息，返回步骤（1）；如果在T_backoff内未收到预休眠消息，节点进入休眠状态，休眠时间T_s结束后返回步骤（1）；

（6）、判断该节点是否符合沉睡条件：若节点符合沉睡条件，则进入沉睡状态，沉睡时间T_deepsleep结束，返回步骤（1）；若不符合沉睡条件，则向邻居节点发出求救消息等待支援，进入步骤（7）；

（7）、判断该节点是否收到邻居节点的求救消息：若收到邻居节点的求救消息，并把求救节点发来的信息存放到邻居列表中，并从邻居列表中选择d/E_r最小的节点作为该节点的求救节点，并进入沉睡状态，沉睡时间T_deepsleep结束，返回步骤（1）；若没收到邻居节点的求救消息，进入步骤（8）；

（8）、判断节点的当前能量值E_i是否等于0：若当前能量值E_i不等于0，则返回步骤（1）；若当前能量值E_i等于0，本节点的调度过程结束；

（9）、返回步骤（1），进行其它节点的调度过程。

所述的步骤（7）的收到求救消息的流程具体如下：

步骤1：判断节点是否收到求救消息：若节点没有收到求救消息，返回继续判断；若节点收到求救消息，求出节点离求救节点之间的距离，记为d，进入步骤2；

步骤2：估算节点进行救援后剩余的能量值，记为E_r，进入步骤3；

步骤3：判断节点剩余能量值E_r是否大于阈值E_th：若节点剩余能量值E_r小于阈值E_th，返回步骤1；若节点剩余能量值E_r大于阈值E_th，进入步骤4；

步骤4：求出d/E_r的值，把节点的d/E_r值发送给求救节点，并求救节点等待发出确认是否支援；若收到求救节点发来的确认消息，则进行支援；若没有收到求救节点的确认消息，返回步骤1。

所述的步骤（2）中计算该节点被邻居节点覆盖的覆盖冗余率δ=（节点被各个邻居节点覆盖的面积之和）/节点本身面积。

所述的步骤（4）中的休眠条件是：该节点的覆盖冗余率δ是否大于或等于给定的阈值δ_th-sleep，若覆盖冗余率δ大于或等于给定的阈值δ_th-sleep，则该节点符合休眠条件；若覆盖冗余率δ小于给定的阈值δ_th-sleep，则该节点不符合休眠条件。

本发明所提供的用于无线传感器网络节点调度的覆盖空洞避免的方法，主要用于解决节点调度机制中部分节点能量消耗过快，造成这些节点失效进而引起该节点所在区域的覆盖空洞问题，从而造成网络生存时间缩短的问题。

本发明能够根据节点剩余能量和覆盖要求对节点状态进行调度，采用分轮的方式，每轮包括四个阶段：邻居发现阶段、覆盖冗余判别阶段、节点求救阶段和节点状态转换阶段。在保证监测区域覆盖的前提下，根据节点的能量消耗情况，对节点状态进行合理分配：若剩余能量大于给定的阈值让其进入能量节约的休眠状态；若剩余能量小于给定的阈值，且该节点自身符合休眠条件，则该节点进入休眠时间更长的沉睡状态；若不符合休眠条件，则该节点向邻居节点发出求救信息，邻居节点进行自我检查是否符合支援条件进而对该节点进行支援。该机制可以提高监测信息采集的可靠性，有效的避免覆盖空洞的产生及扩散，从而达到节约网络能量，从而达到延长网络生存时间的目的。具体有如下优点：

1. 提高整个网络的生存时间

通过对网络中节点进行状态进行控制，节点进入与能量相对应的状态，可以高效合理的使用网络能量，延长整个网络的生存时间。

2. 定位灵活

节点不进行移动时，关闭定位系统；只有节点满足移动的条件时，才会开启定位系统。

附图说明

图1是两节点的相交图(r<d(S₁, S₂)<2r)；

图2 是两节点相交时圆C₂弧上的点到圆C₁的圆心S₁的距离(r<d(S₁,S₂)<2r)的示意图；

图3是两节点的相交图(d(S₁,S₂) r)；

图4是两节点相交时圆C₂弧上的点到圆C₁的圆心S₁的距离(d(S₁,S₂)r) 的示意图；

图5(a)是以节点S₁为中心，邻居节点对其覆盖面积图；

图5(b)是以节点S₁为圆心，以θ为x坐标，以为y坐标的极坐标系中，邻居节点在坐标系中的二维映射图；

图6是支援节点进行支援时的矢量图；

图7是节点状态转换图；

图8是本发明的方法流程图；

图9是邻居节点接收到预休眠消息时的流程图；

图10是邻居节点接收到求救消息时的流程图；

图11是节点S₀和它的邻居节点的示意图。

具体实施方式

本发明提供了一种用于无线传感器网络节点调度的覆盖空洞避免方法，可以在已有的进行无线传感器网络仿真的软件上设计并实现。通过网络中节点的覆盖和剩余能量情况，设置相应的节点状态，并根据网络运行情况对节点状态进行调度，其目标是在网络监测性能保证的同时，避免或延缓覆盖空洞问题的产生，达到节约网络能量，延长网络生存时间的目的。

如图7所示，本发明将无线传感器网络中节点设定为五种状态：空闲态、数据处理态、预休眠态、休眠态和沉睡态。空闲态是节点的初始化状态；节点有数据需要处理时，节点会进入数据处理态；为了避免节点和其邻居节点同时进入休眠态的情况，设置了预休眠态。休眠态是为了节省节点不必要的能量浪费而设置的。针对能量较小或需要被支援的节点设置了沉睡态，处于该状态的节点比处于休眠态节点的休眠时间稍长一些。这五种状态详细介绍如下：

（1）空闲态

处于空闲态的节点用于监听网络中是否有数据需要进行处理。若有数据需要处理，节点进入活动态，并对数据进行接收、发送、融合等处理工作；否则，该节点仍然保持空闲态。

（2）数据处理态

节点主要是对数据进行处理，包括接收邻居节点发来的数据、向邻居节点发送数据、对数据进行融合、压缩等工作。同时，在该状态下，对邻居节点的信息进行统计工作：邻居节点的ID、剩余能量和邻居节点的状态等。

（3）预休眠态

节点进入休眠态之前先向邻居节点发送预休眠消息，同时监听邻居节点是否向该节点发送预休眠消息，若在设定的避让时间内未收到其邻居节点发来的预休眠消息，该节点关闭通信模块进入节约能量的休眠状态，设定该状态的目的是为了避免该节点与邻居节点同时进行休眠状态造成覆盖空洞。

（4）休眠态

处于休眠状态的节点关闭通信模块，待预设的休眠时间到后打开通信模块。

（5）沉睡态

沉睡态的节点与休眠态的节点类似，不同在于沉睡时间比休眠时间稍长。

本发明采用分轮方式首先对节点剩余能量进行检查。节点发送一个广播消息，根据收到消息的情况来判断邻居节点的个数或距离等信息来计算自身的冗余覆盖率；同时得知邻居节点的状态、能量、冗余覆盖率等情况；然后根据自身的能量状况及冗余覆盖率节点进入相应的状态。下面对邻居发现阶段、覆盖冗余判别阶段、节点求救阶段和节点状态转换阶段详细介绍如下：

（1）邻居发现阶段

邻居发现阶段主要采集该节点的邻居节点的个数或本节点到邻居节点的距离信息。任意节点S_i的邻居节点是指与该节点的距离小于2r的所有空闲或活动节点集合N(S_i)={ S_j| d(S_i, S_j)<2r}，其中d(S_i, S_j)表示节点S_i与S_j之间的欧氏距离。

邻居发现阶段的步骤为：1) 节点S_i发送广播消息；2) 接收邻居节点的回复信息；3) 统计邻居节点个数或距离信息。 

（2）覆盖冗余判别阶段

覆盖冗余判别阶段是为判断节点是否是覆盖冗余节点进行服务的，提供节点覆盖冗余计算方法；该阶段分为两种情况：第一种情况是两节点间的距离大于感知半径小于通信半径，即r<d(S₁,S₂)<2r，即图1、图2所示情况。第二种情况是两节点间的距离小于感知半径，即d(S₁,S₂)<r，即图3、图4所示情况。对两种情况详细描述以下：

情况1：两节点间的距离大于感知半径小于通信半径，即r<d(S₁,S₂)<2r。

图1中假设有两个感知半径均为r的节点S₁和S₂，节点S₁、S₂的坐标分别记为（x₁, y₁）、（x₂, y₂），d(S₁,S₂)=d，它们的覆盖范围分别为C₁和C₂，两个节点的感知范围相交于A、B两点；线段AB是线段S₁S₂的垂直平分线。线段S₁S₂与线段S₁A的夹角设为，以节点S₁为坐标原点，线段S₁S₂与x轴（黑色虚线部分）的夹角记为，图2中圆C₂与圆C₁相交的弧记为L，弧L上的点到坐标原点S₁的距离记为，弧L上的点与x轴的夹角设为θ。

夹角可表示为：

                                                                        (1)

                                                           (2)

                                                                 (3)

角可表示为：

                                                           (4)

                                                                      (5)

由图2可知：

                                                         (6)

                                             (7)

                                                                  (8)

把公式(7)和(8)代入公式(6)得：

                                            (9)

从而解得：

                                         (10)

当θ=0时，只有是正确的，所以的公式为：

                                                      (11)

以S₁为坐标原点的坐标系上，弧L上点可表示为：

          (12)

情况2 ：两节点间的距离小于感知半径，即d(S₁,S₂)r

图3和图4是两个节点间的距离小于感知半径的情况。

从图3中可以看出，当d(S_1, S₂)r时，d、d₁、d₂ 三者间的关系式不同于r<d(S₁,S₂)<2r中的公式(8)：

                                                (13)

同样把公式(7)和(13)代入公式(6)得：

                             (14)

从而解得：

                        (15)

当θ=0时，只有是正确的，求得的公式为：

                           (16)

以S₁为坐标原点的极坐标系上，弧L上点则表示为：

          (17)

结合公式(12)和(17)得的公式：

  (18)

用上面介绍的覆盖冗余计算方法把S₁的邻居节点映射到以节点S₁为圆心的极坐标系中。如图5(a)所示，S₁的邻居节点有四个，I代表一重覆盖，II代表二重覆盖，III代表三重覆盖；图5(b)中，角度θ作为极坐标系中的x轴，弧长上的点到S₁的距离作为极坐标系中的y轴。

在进行覆盖冗余计算时，从、开始进行对S₁的弧长从-π到π进行扫描，利用公式(19)从而计算出节点S₁被其各个邻居节点覆盖的面积。

覆盖冗余率δ=（节点被其各个邻居节点覆盖的面积）/节点本身面积，例如图5(a)中节点S1的覆盖冗余率δ=（四个II的面积+两个III的面积）/ 。而四个II的面积+两个III的面积可通过公式（19）计算出来，只需将起点所对应的横纵坐标的值和终点多对应的横纵坐标的值带入至公式（19）的积分范围即可。

根据该节点与邻居节点的距离大小，采用上述方法计算出该节点的覆盖冗余情况。并根据用户需要设定的覆盖冗余率阈值δ_th-sleep来判别该节点是否是覆盖冗余节点：若该节点的覆盖冗余率δ大于阈值δ_th-sleep，是该节点是覆盖冗余节点，否则不是。

（3）节点求救阶段

当节点的剩余能量值小于设定的阈值时，节点首先判别自己是否符合沉睡条件，若符合，节点进入沉睡状态。若不符合，则向邻居节点发送求救消息，让邻居节点协助自己完成监测任务。

在节点求救阶段，根据监测应用需要，设置如下四个参数阈值，第一个是沉睡的能量阈值E_{th_fsleep}，第二个是邻居节点估计移动后剩余的能量阈值E_th，第三个是节点进入休眠条件的覆盖冗余率δ_th-sleep，最后是节点进入沉睡条件的覆盖冗余率δ_{th_fsleep}。

节点进入休眠状态需满足两个条件：1）节点i的当前能量值E_i>E_{th_fsleep。}2)节点的冗余率不小于δ_th-sleep。

节点进入沉睡状态需满足两个条件：1）节点i的当前能量值E_i<E_{th_fsleep。}2)节点的冗余率不小于δ_{th_fsleep}。

邻居节点收到求救信息后，首先对自己进行救助后的剩余能量E_r进行估计，以此值来决定是否采取救助。

当一个节点的当前能量值小于设定的阈值且未能达到沉睡条件时，向邻居节点发出求救消息。收到求救消息的邻居节点在采取救助行动前，先估计救助后的剩余能量值E_r，然后根据该值决定是否采取救助行动。其估计方法主要依赖于对节点救助时节点移动消耗的能量和节点接收、发送数据消耗的能量。其剩余能量估计方法如下：

在正常的信噪比的条件下，节点在传输距离为d时，发送k位数据消耗的能量E_T(k,d)：

                    (20)

其中，E_e是无线电电子学能量消耗的系数，和是在不同的距离条件下为功率放大能量消耗的系数。

接收k位数据时消耗的能量E_R：

                                                                                       (21)

节点在移动时消耗的能量是E_m，节点在移动距离为d时消耗的能量E_c:

                                                                                    (22)

那么，邻居节点在救助后，其剩余能量估计值E_r为：

                                              (23)

邻居节点符合支援的条件：

1）该节点与待求救节点的距离d较近；

2）节点移动后剩余能量的值E_r大于阈值E_th；

3）节点d/E_r的值是邻居节点中最小值。

图6中节点S₀的感知半径是r，通信半径是2r，其邻居节点是S₁、S₂、S₃、S ₄。S₀的能量小于阈值E_{th_ fsleep}，覆盖冗余率小于δ_{th_fsleep}，需要向邻居节点发出求救信息。在S₀的邻居节点中，节点S₁通过上述计算，符合支援的条件，节点S₁会沿着S₁S₀的方向向S₀移动；移动后的位置记为S'，节点S₀、S₁的坐标分别记为（x₀, y₀）、（x₁, y₁）。则S'的坐标：

                                             (24)

                                             (24)

（4）节点状态转换阶段

节点共有5种状态：空闲状态、数据处理状态、预休眠状态，休眠状态和沉睡状态。节点会结合自身的剩余能量值、状态和覆盖冗余率等状况进行对应状态间的转换。节点的初始状态是空闲态；数据处理状态、预休眠状态和休眠状态出现在节点的能量大于设定阈值E_{th_fsleep}的情况下，当节点接收或发送数据时，会进入数据处理态，数据处理完后会重置为空闲态；当节点满足休眠条件时，节点会进入预休眠态，同时向邻居节点发送一个预休眠消息，并启动一个避让时间T_backoff，若在T_backoff时间内收到了邻居节点发来的预休眠消息，节点会重置为空闲态，若未收到邻居节点的预休眠消息，节点会进入休眠状态，休眠时间结束后，节点同样会重置为空闲态；沉睡态只会出现在节点的能量小于设定阈值的情况下；当节点的能量小于设定的阈值E_{th_fsleep}时，节点的覆盖冗余率不小于设定的阈值δ_{th_fsleep}时，节点会进入沉睡状态，沉睡时间结束后，节点也会重置为空闲态。

无线传感器网络节点调度覆盖空洞避免方法首先对网络进行初始化，并根据网络运行情况执行上述四个阶段，最终实现尽可能延长网络生存时间的目的。初始化网络的主要作用是对无线传感器网络中所有节点进行相关信息的收集工作，建立该节点的邻居列表，邻居列表信息主要包括：该节点的ID、该节点的状态、该节点剩余能量、邻居的覆盖冗余率等。

由于每个节点调度分轮进行，在下面的描述中，仅对某一轮内一个当前节点的节点调度覆盖空洞避免方法进行描述：以图11中的节点S₀为例，节点S₀共有S_1、S_2、S_3、S_4、S₅五个邻居节点，如图8所示，具体包括以下步骤：

（1）、设节点S₀的初始态为空闲态，首先判断该节点S₀是否有数据包需要处理：如果有数据需要处理，则节点S₀进入活动态，且处理数据后进入步骤（2）；若无数据包需要处理，则进入步骤（2）；

（2）、计算该节点S₀被邻居节点S_1、S_2、S_3、S_4、S₅覆盖的覆盖冗余率δ，进入步骤（3）；

（3）、判断该节点S₀当前能量值E_i是否大于设定的能量阈值E_{th_fsleep}，若是，则进入步骤（4）；若否，则进入步骤（6）；

（4）、判断该节点S₀是否符合休眠条件：若该节点S₀符合休眠条件，则该节点S₀向邻居节点S_1、 S_2、 S_3、 S_4、 S₅发送一个预休眠消息(Pre-Sleep message)，进入预休眠状态，同时启动一个延迟计时器T_backoff，进入步骤（5）；若不符合休眠条件，返回步骤（1）；休眠条件是：该节点的覆盖冗余率δ是否大于或等于给定的阈值δ_th-sleep。

（5）、该节点S₀如果在T_backoff内收到任意一个邻居节点发送的预休眠消息，返回步骤（1）；如果在T_backoff内未收到预休眠消息，节点S₀进入休眠状态，休眠时间T_s结束后返回步骤（1）；

（6）、判断当前节点S₀是否符合沉睡条件：若节点符合沉睡条件，则进入沉睡状态，沉睡时间T_deepsleep结束，返回步骤（1）；若不符合沉睡条件，则向邻居节点S_1、S_2、S_3、S_4、S₅发出求救消息等待支援，进入步骤（7）；

（7）、判断节点S₀是否收到邻居节点的支援消息：若收到邻居节点S₅的支援消息，并把支援节点S₅发来的d/E_r信息存放到邻居列表中，如果同时收到多个邻居节点发来的支援消息，都存放在S₀的邻居列表中，并从邻居列表中选择d/E_r最小的节点作为该节点的支援节点并进入沉睡状态（假设S₅的d/E_r是

最小的，则S₀通知S₅进行支援随后进入沉睡状态），沉睡时间T_deepsleep结束，返回步骤（1）；若没收到邻居节点的求救消息，进入步骤（8）；

（8）、判断节点的当前能量值E_i是否等于0：若当前能量值E_i不等于0，则返回步骤（1）；若当前能量值E_i等于0，本节点的调度过程结束。

针对邻居节点可能会收到预休眠消息的流程，如图9所示，详细过程如下（以节点S₁为例）：

步骤1：判断节点S₁是否收到预休眠消息：若节点S₁收到预休眠消息，返回步骤1；若节点S₁没有收到预休眠消息，求出节点S₁覆盖冗余率δ；然后进入步骤2；

步骤2：判断节点S₁是否符合休眠条件；若节点S₁不符合休眠条件，返回步骤1；若节点S₁符合休眠条件，节点S₁发送一个预休眠消息，进入步骤3；

步骤3：判断节点S₁是否收到预休眠消息，若没有收到预休眠消息，节点S₁进入休眠状态，休眠时间T_s结束，返回步骤1；若节点S₁收到预休眠消息，返回步骤1。

利用邻居发现阶段中的邻居集合N(S_i)，当邻居节点集中的某一节点收到节点S_i的求救信息时，首先估计救援后的剩余能量E_r，检查是否有资格进行救援。但对于节点S_i来说，仅仅依据邻居节点的剩余能量，并不一定能找到合适的邻居节点来进行救援。在本方法中，同时还考虑到节点S_i与邻居节点的距离信息。根据公式（26）计算邻居节点的距离与剩余能量估计后值的比值。

                                              (26)

其中，，表示节点估计后的剩余能量值。

定理1：由公式(26)中求出邻居节点的λ集合中最小值是最优值。

证明：当相同时移动距离越小越好，说明距离越小λ的值越小；

当距离相同时移动后剩余的能量值越大越好，说明越大λ的值越小；即λ集合中最小值是最优值。

所以，从邻居节点的中选择值最小的节点作为救援的节点，即。

针对步骤（7）中邻居节点收到求救消息的流程，如图10所示，详细过程如下（以节点S₅为例）：

步骤1：判断节点S₅是否收到求救消息：若节点S₅没有收到求救消息，返回判断；若节点S₅收到求救消息，求出节点S₅离求救节点S₀之间的距离，记为d，进入步骤2；

步骤2：估算节点S₅进行救援后剩余的能量值，记为E_r，进入步骤3；

步骤3：判断节点S₅救援后剩余能量值E_r是否大于阈值E_th：若节点S₅救援后剩余能量值E_r小于阈值E_th，返回步骤1；若节点S₅救援后剩余能量值E_r大于阈值E_th，进入步骤4；

步骤4：求出d/E_r的值，把节点S₅的d/E_r值发送给求救节点S₀，并等待S₀发出确认是否支援：若收到S₀发来的确认消息，则进行支援；若没有收到确认消息，返回步骤1。

其中选取方法是：从邻居列表中找出d/E_r的最小值，假如是S₂，获取其对应的ID=2，就由邻居节点S₂对节点S₀进行支援。