无线传感网中基于优先级的节点休眠调度机制*

王海涛

(南京审计大学金审学院 信息科学与工程学院，江苏 南京 210023)

作为物联网和智慧城市的关键支撑技术之一，无线传感网(Wireless Sensor Networks，WSNs)已得到了广泛应用[1]。无线传感网是由部署在目标监测区域内的大量传感器节点构成的一种自组织网络，对覆盖区域内的相关信息进行有效感知、采集和处理[2]。随着网络规模和业务量的增加，能耗已成为制约无线传感网功效充分发挥的重要瓶颈之一[3]，能耗不仅直接影响无线传感网的生存时间，而且与环境保护息息相关。迄今，国内外学者针对无线传感网的节能问题展开了诸多研究，主要采取了网络分簇组织、协作中继、节点休眠调度、数据聚集和负载平衡等措施来减低网络运行能耗。其中，节点休眠调度作为一种行之有效的降低网络能耗的机制，备受业内学者关注[4]。

无线传感网中节点的状态一般可分为“发送”、“接收”、“空闲”和“休眠”四种模式，其中发送模式下节点能耗最大，接收和空闲模式下只需侦听信号，节点能耗相对较少，而休眠模式下节点仅保留定时器工作，能耗最少。简单起见，也可将节点的状态分为工作(包括发送、接收和空闲)和休眠两种模式。因此，通过合理调度节点由工作模式转入休眠模式来降低网络能耗一直是业界研究和关注的焦点。节点休眠调度机制是指在保持网络正常服务性能的前提下，通过合理组织和安排分布在网络中的各个节点的工作/休眠状态，以便有效均衡网络节点负载并显著降低网络能耗，从而达到增强网络效能和延长网络生存时间的目标[5]。实际上，网络服务性能需求视具体应用场景而大相径庭，常用的评价指标包括覆盖度、连通性、吞吐量和时延等[6]。为了保证对目标监测区域的完全覆盖，通常传感器节点的部署密度较高，距离较近的邻居节点往往存在覆盖冗余，并且许多节点处于空闲监听模式而造成不必要的能量消耗。因此，无线传感网中可行的节点休眠调度策略一般是指在确保一定网络覆盖度和连通性的基础上，由节点自主决策选择适当的时机轮流在休眠和工作两种模式间切换的策略。

本文主要针对目标检测类应用场景，研究适合无线传感网的高能效节点休眠调度策略。首先，比较分析国内外相关研究工作；然后，探讨有效度量休眠调度策略优劣的性能指标。在此基础上，通过综合考量节点的剩余能量及其邻居节点的覆盖情况，设计了一种基于休眠决策优先级的分布式节点休眠调度机制 (Priority Based Distributed Sleep Scheduling，PBDSS)，在满足网络服务性能的前提下能够有效平衡节点负载，提高节点能量效率和延长网络寿命。

1 相关工作

无线传感网中节点有限的能量限制了其计算、存储和通信能力，这些限制成为设计网络协议不得不考虑的约束条件[3]。因此，设计节点休眠调度策略时也必须在考虑这些约束条件的基础上尽量优化关键的网络服务性能指标[7]。现有的大多数节点休眠调度方法都以提高节点能量效率和延长网络寿命为首要目标。

按调度计算方式，节点休眠调度可采用集中式或分布式策略[8]。集中式方法通常需要由一个计算中心负责收集全网状态信息，然后根据既定的调度算法生成调度策略/规则，并广播给全网节点。集中式调度方法的性能通常优于分布式调度方法，但资源耗费高、扩展性差且实现困难。相比而言，分布式调度方法允许节点根据自身或周围节点状况，对自身工作状态进行主动调度，实现相对简单且可扩展性较好。鉴于无线传感网缺乏统一的调度中心，加之传感器节点资源非常受限，无线传感网更适合采用分布式的节点休眠调度方法。

由于节点休眠调度机制主要通过延长节点休眠时间或增加休眠节点的数量来节省网络能量，设计节点休眠调度机制务必要考虑网络的覆盖度和连通性等指标，并可能需要在多个指标之间进行合理折中[9]。文献[10]提出了一种考虑了感知区域覆盖度的节点休眠调度方法，节点在进入休眠前先随机延迟一段时间，有效避免了由于多个节点同时休眠造成的覆盖盲区/覆盖空洞(即没有被任何节点覆盖的网络区域)。文献[11]提出了根据邻居节点位置来消除网络冗余覆盖的节点休眠策略，若一个节点的覆盖区域被其邻居节点完全覆盖，则该节点进入体眠模式。文献[12]对上述机制进行了优化，提出了基于覆盖概率的节点休眠调度机制，如果某节点的覆盖区域能以超出预定的概率被其他节点覆盖，则该节点可以休眠。与此类似，文献[13]提出了面向部分网络覆盖的节点休眠唤醒机制，通过唤醒部分节点构成主干网，然后再按需唤醒这些节点的邻居节点来满足网络覆盖要求。文献[14]主要研究基于休眠的中继选择策略，能够实现网络覆盖度、连通性与总能耗之间的合理折中。此外，文献[15]设计了一种简单有效的分布式节点休眠调度算法，节点采用基于异步定期休眠唤醒的任播转发策略，在保证不增加能耗的基础上期望最小化端到端的时延。

上述研究工作基于不同需求和度量指标设计了多种用于无线传感网的节点休眠调度机制，并且大都采用表现更好的分布式休眠调度策略。但是，上述休眠调度研究工作仍未合理地平衡网络覆盖度和节点能耗，并且在实施休眠调度过程中没有充分利用网络整体拓扑结构和考虑网络各节点的状态信息。

2 系统模型

2.1 网络模型

将无线传感网的目标监测区域设定为二维矩形区域A，并且传感器节点随机分布在目标区域内，节点感知的信息可通过多跳中继的方式传送到位于监测区域中心的汇聚节点(基站)，如图1 所示。初始部署时，所有传感器节点都处于工作状态并可以对目标区域实施完全覆盖，并假设所有传感器节点是同构的，即具有相同的初始能量、感知范围和通信范围，同时所有节点一经部署便不再移动。此外，假设节点可以通过某种方式(GPS 或其他定位技术)获悉自身地理位置，并且可以计算自身的能耗以估计其剩余能量。

专业课教师只重视技能，思政老师只注重课堂教学，这都是长期以来人们对于大学生思想政治教育存在一个误区，认为这只是思政老师的事。 实际上，在专业课教学中有许多思政教育资源，如本专业的历史渊源和文化传统，从事本专业应具备的科学研究精神和人文素养， 这些与专业相关的问题都与思政内容有关，教师在教学中还可以通过自己的操作示范以及学生的动手实践，引导学生亲身体验专业规范和要求，为学生树立良好的榜样。

图1 目标区域监测的无线传感网网络模型

感知范围是指节点能有效感知环境信息的区域，而通信范围是节点一跳传输所能达到的区域，一般分别将它们设定为以传感器节点为中心，以某个值r和R为半径的圆形区域，并且节点的感知范围一般小于通信范围(参看图1)。假定目标监测区域中部署的传感器节点集合为S＝{s1，s2，…，sn}，令某目标点p的位置坐标是(x，y)，如果p与传感器节点si之间的欧氏距离小于或等于节点si的感知半径，即d(p，si)≤r，则点p被节点si覆盖。据此，可得出节点si的感知(覆盖)范围集合为:SC(si)＝{p∈A｜d(p，si)≤r}。如果节点sj与si之间的欧氏距离满足d(si，sj)≤R，则sj是si的通信邻居(Communication Neighbor，CN)。由此，得出节点si的通信邻居节点集合为:CN(si)＝{sj∈S｜d(sj，si)≤R}。类似的，如果sk与si之间的感知范围存在交叠区域，即满足d(sk，si)＜2r，则称节点sk是si的感知邻居节点(Sensing Neighbor，SN)。由此，可以得到si的感知邻居节点集合为:SN(si)＝{sk∈S｜d(sk，si)＜2r}。为了确保网络节点间的连通性，使传感器节点感知的数据信息能够有效通过多跳中继转发传输到汇聚节点，要求节点的通信范围至少是感知范围的两倍[16]。

值得注意的是，无线传感网中基于全覆盖策略的休眠调度机制对于靠近目标监测区域边界的节点来说显然不太合理。举例来说，图1 中的节点A、B、C 均是靠近网络区域边界的节点(它们的感知区域超出目标监测区域)，由于这些邻近边界的节点覆盖的是目标监测区域的边界部分，加之其邻居节点相对较少，很难满足完全被覆盖的条件而进入休眠状态。显然，长时间的工作会造成这些邻近边界的节点过早耗尽能量，进而使得边界区域成为覆盖盲区。长此以往，节点覆盖的监控区域将会逐步向目标监测区域的中心收缩，这种现象被称为“边界效应”[17]。边界效应会显著影响网络的覆盖度，降低网络的可用性。因此，为了尽可能避免无线传感网出现边界效应问题，节点休眠调度机制应允许部分邻近边界的节点在满足相对较低覆盖度的条件下转入休眠模式以均衡节点的能耗，从而有效消除覆盖盲区和延长网络寿命。

2.2 能耗模型

无线信号传播时会发生衰减，通常采用如下的自由空间模型来计算传播损耗[18]:

式中:Lp为路径损耗，d为传播距离，λ为信号波长。一般情况下，无线通信传输的能量消耗与通信距离的关系如下:

式中:k是一个常量系数，参数n一般需满足2≤n≤4。n的取值与很多因素有关，如天线信道质量、障碍物和噪声干扰等。

节点接收数据的能耗计算公式如下:

式中:L表示接收的数据包长度，Eelec表示无线收发电路处理单位数据所消耗的能量。

在无线传感网中，节点发送数据的能耗通常根据节点传送数据的距离d，分别采用自由空间模型和多径衰落模型，如式(4)所示:

3 休眠调度机制描述

3.1 假设条件

本文设计的分布式休眠调度机制命名为基于优先级的分布式调度(Priority Based Distributed Sleep Scheduling，PBDSS)。PBDSS 主要针对目标区域监测的无线传感网应用场景，并且遵循第2 节描述的网络模型和能耗模型。节点可以根据自身获取的感知邻居节点的信息，计算其感知区域被感知邻居节点覆盖的比率(简称覆盖度)，并且可以根据初始能量和能耗使用情况计算出自己的剩余能量，进而能够根据剩余能量和覆盖度自主决定是否进行休眠调度。此外，简单起见，暂不考虑信道条件恶化或分组传输冲突等原因引起的消息丢失情况。

3.2 设计目标和原则

本文提出的PBDSS 的设计目标是，在满足对目标监测区域预定的覆盖度和节点连通性需求的基础上，最小化处于工作状态的节点数量，以便尽可能降低全网能耗，延长网络寿命。如前所述，节点休眠调度机制需要合理权衡网络能耗和覆盖度两个指标，优化目标是在满足既定覆盖度的条件下最小化网络能量消耗，或在网络能量消耗一定的条件下最大化监测区域的覆盖度。

PBDSS 的设计遵循两条基本原则:一是在保证目标监测区域一定程度覆盖(允许个别覆盖盲区的出现，但网络整体覆盖度必须达到阈值)的前提下，使处于工作状态的节点数量尽量少，从而节省网络能耗；二是要尽量均衡节点间的能耗，允许相邻节点尽可能轮流休眠和工作，从而既能够尽量避免某些节点提前耗尽能量，同时一定程度上可防止两个或多个互为邻居的节点同时进入休眠状态而出现不可预测的覆盖盲区。具体而言，如果节点的覆盖度满足预设门限则可以自主决定转入休眠状态，并且尽可能使剩余能量较少的节点优先(以较大的概率)转入休眠状态。此外，为了减少节点休眠调度机制引入的控制开销，还应尽量减少节点之间的信息交互。

3.3 性能评价指标

当前，评价无线传感网性能常用的指标包括网络寿命、能量效率、覆盖度和连通性等。网络寿命能较好反映系统整体可用性，是度量休眠调度机制优劣最常用的一项评判指标，也是评估无线传感网整体性能最有效的指标之一。根据实际应用场景，网络寿命有不同的定义标准，如可以基于有效节点数、目标区域覆盖度、连通性等指标来定义网络寿命[7]。相比而言，基于有效节点数的网络寿命定义较为简单，通常采用网络从工作开始到第一个节点失效的时间作为网络寿命。另外，也可以综合考虑覆盖度和连通性来确定网络寿命，覆盖度能保证节点对目标监测区域的有效覆盖，同时连通性能保证节点采集到的信息能可靠传输到汇聚节点。

能量效率通常定义为单位能量可以发送的有效信息量，也可定义为单位能量可维持的网络运行时间，后者等效于网络寿命。覆盖度是指在目标监测区域内，某一目标区域能被多少节点有效感知或被节点有效感知的百分比，如k度覆盖和全覆盖等[19]。休眠调度机制在保证一定覆盖度的前提下，通过让部分工作节点转入休眠，可以降低节点能耗和延长网络寿命。当网络内所有节点都可相互连通时，称网络是连通的。部分节点休眠可能会影响网络连通性，因此节点休眠调度有时还需保证网络连通性以便使节点感知的数据能够可靠传输到汇聚节点。

3.4 工作流程

类似于无线传感网中经典的LEACH 协议[20]，PBDSS 调度策略下节点也按轮次执行休眠调度。每个轮次开始时，节点进行自主调度并且转入三种运行状态之一:未决策状态、工作状态和休眠状态，并且在本轮次内节点所处状态将保持不变，直到下一个轮次节点基于定时器重新执行休眠调度。每个轮次开始，所有节点都置于未决策状态，每个节点将定期向所有邻居节点发送包含自身位置和ID 信息的Hello 消息，定期发送Hello 消息的周期TS需根据网络规模、节点密度和应用需求来合理设置。节点根据获取的邻居节点信息和自身状况计算其在本轮次的调度优先级，并将优先级消息广播给邻居节点，优先级高的节点可优先做出是否进入休眠状态的决策。为了消除覆盖冗余和均衡节点能耗，那些自身感知区域被邻居节点覆盖比率高且剩余能量相对少的节点应该获得更高的休眠调度优先级。基于上述分析，可以将任意节点si的调度优先级P(si)设置为:P(si)＝CA(si)/RE(si)。其中，CA(si)为节点si的覆盖度，RE(si)为节点si的剩余能量。如果节点的调度优先级相同，则规定ID 号较小的节点优先进行休眠调度。节点的覆盖度可以根据文献[13]中基于邻居节点的位置和感知范围信息计算得出，节点的剩余能量可以根据前述的能耗模型计算得到。

基于对邻近节点广播的优先级消息的接收和比对，节点si可以将邻居节点分为两组:一组是比si调度优先级低的邻居节点的集合，记为LSN(si)；另一组是优先级比si高的邻居节点的集合(即si的优先级低于该邻居集合)，记为HSN(si)。然后，节点si按照如图2 所示的休眠调度工作流程来决策自身是否进入休眠状态。

图2 PBDSS 调度策略下节点的工作流程

首先，节点si仅考虑LSN(si)组内的节点对自身感知区域的覆盖程度，若能满足预先设定的覆盖度要求，则节点si选择进入休眠状态；否则，节点si并不会立刻选择进入工作状态而是随机等待一定时长tr，tr取0 到TS之间的随机值，即tr＝Random(0，TS)。这样做的原因在于，如果HSN(si)组内已有节点确定进入工作状态(发送active message)，那么节点si需要同时考虑HSN(si)和LSN(si)组内的工作节点对自身感知区域的覆盖，然后再进行决策。若在tr时间内能够满足覆盖阂值要求，则si即可进入休眠状态，否则，si进入工作状态，并发送active massage。所有节点执行完休眠调度策略后，均会进入休眠状态或者工作状态，并保持这一状态直到这一轮次结束，而下一轮次开始后又会进入新的决策阶段(轮次周期时长需要基于节点的分布状况进行合理确定)。

上述PBDSS 调度策略的计算量主要在于计算邻居节点对其感知区域的覆盖度，根据已有文献的分析，较好的覆盖度计算方法的复杂度为O(dlg(d))，其中d为无线传感网的平均节点度[15]。

4 仿真实验和结果分析

4.1 仿真实验环境

仿真实验基于OMNet++(Objective Modular Network TestBed in C++)仿真软件，OMNet++是一款开源的基于组件的模块化离散事件仿真器，主要用于通信网络和分布式系统的仿真，具有完善的图形界面接口和嵌入式仿真内核[21]。本仿真实验使用的模拟软件版本是OMNeT++5.6。仿真过程中，设定无线传感网的目标监测区域为500 m×500 m 的正方形区域，在该区域内随机部署1000 个传感节点，传感节点的感知半径为10 m，通信半径为20 m。在区域中心设置一个汇聚节点且其能量不受限。在每一个轮次，节点将感知到的环境信息通过多跳转发方式传送到位于区域中心的汇聚节点。为了便于计算网络寿命，假定每一个轮次的时间均为一个单位时间，网络寿命则可以通过执行的轮次数来量化。每个传感节点的能量有限，初始能量设为50 个单位能量，假设每一个轮次中节点处于工作状态消耗1个单位能量，处于休眠状态则不消耗能量，并且当能量耗尽时该节点即失效。

4.2 比较对象和评价指标

仿真实验主要比较提出的PBDSS 调度策略与具有代表性的无线传感网休眠调度策略在覆盖度、网络寿命和能量效率三项性能指标上的优劣。PBDSS 调度策略的覆盖度阈值θ 设定为0.8，作为比较对象的休眠调度机制选择Zairi 等[5]提出的经典的基于剩余能量的贪心调度策略(Energy Remaining Greedy Scheduling，ERGS)，ERGS 的主要思想是在保证网络完全覆盖的前提下允许不必要的冗余节点进入休眠状态以节省能量，并且ERGS 休眠调度策略仅考虑了节点剩余能量一个因素。简便起见，网络寿命采取前述较为简单的定义，即当第一个节点因能量耗尽失效时网络寿命即终止。此外，仿真实验中给出的仿真数据均为进行20 次仿真实验取平均值后得到的结果。

4.3 仿真结果分析

首先，观察不同休眠调度策略下目标监测区域覆盖度随网络寿命(第一个节点失效前执行的轮次数)的变化情况，如图3 所示。从图3 中可以看出，本文提出的PBDSS 策略下的网络寿命可持续90 个轮次，而ERGS 策略下的网络寿命仅能维持50 个轮次。造成ERGS 策略下网络寿命较短的主要原因在于ERGS 要求网络全覆盖而导致明显的网络边界效应，某些监测边界区域可能只被少量节点(甚至一个节点)覆盖，该节点在每个轮次都无法进入休眠状态而过快耗尽能量，进而导致监测空洞的出现，网络寿命(以第一个节点耗尽能量的时刻来衡量)终止。从覆盖度来看，ERGS 策略下网络始终保持完全覆盖，而PBDSS 策略下的覆盖度随着时间推移不断减少，但整个生命周期内均可确保目标区域的覆盖度不低于85%(大于设定的阈值θ)。因此，某种意义上也可以说PBDSS 策略以牺牲适当的覆盖度显著延长了网络寿命。

图3 网络寿命随网络覆盖度的变化情况

图4 给出了两种休眠调度策略下平均休眠节点数随网络工作轮次的变化情况。PBDSS 策略在前50 轮次中每轮次平均大概有550 个节点休眠，剩余的约450 个工作节点覆盖了85%以上的目标监测区域。ERGS 策略每轮次平均大概有380 个节点休眠，剩余的约620 个工作节点覆盖了100%的目标监测区域。也就是说，与ERGS 策略相比，PBDSS 策略下每个轮次的休眠节点增加了40%以上。此外，PBDSS 策略在随后的40 个轮次中休眠节点的数量不断减少，但依然保持在平均300 个节点以上。

图4 平均休眠节点数随网络工作轮次的变化情况

图5 对比了网络寿命终止时两种休眠调度策略下所有节点剩余能量的均值和标准差。可以明显看出，PBDSS 策略下的剩余能量均值和标准差都远小于ERGS。究其原因在于，PBDSS 策略能够充分利用并均衡节点的能耗，使网络寿命得以延长；而ERGS 策略要求对目标监测区域完全覆盖，导致网络寿命终止时，节点剩余能量偏大且分布很不均衡，造成能量的极大浪费。

图5 所有节点剩余能量的均值和标准差

最后，对比分析两种休眠调度策略下的节点能量效率，如图6 所示。在此将节点能量效率定义为覆盖度与工作节点数量的比值，显然覆盖度越大且工作节点数越少得到的节点能量效率越高。从图6可以看出，在有效对比轮次中(前50 轮次)，PBDSS策略的能量效率总是高于ERGS 策略，并且两者均随着轮次数的增加逐渐降低。这是因为网络运行开始时节点有更多机会选择进入休眠状态，而随着部分节点的失效，转入休眠状态的节点数量将持续减少。

图6 能量效率随网络工作轮次的变化情况

5 结论

本文主要针对无线传感网目标区域监测场景，提出了一种高能效的分布式节点休眠调度策略。首先，对现有休眠调度策略的相关工作进行了调研分析，指出了其中存在的边界效应问题，并说明了休眠调度策略需要综合考虑网络寿命、覆盖度、能量效率和连通性等指标。然后，给出了无线传感网的网络模型和能耗模型，并设计了基于节点调度优先级的分布式休眠调度策略——PBDSS，让剩余能量较低的冗余节点能够以更大概率进入休眠以节省能量。PBDSS 不仅能够降低信息交互带来的能量开销，而且可以较为有效地解决边界效应问题。仿真结果表明，PBDSS 可以在满足预定网络覆盖度的条件下显著提高能量效率，通过平衡节点能耗有效延长了网络寿命。需要指出的是，PBDSS 主要考虑了网络覆盖度和能量效率指标，较少关注不同应用场景的特定服务需求，如环境监测应用较为关心数据传输时延和误码率。因此，今后将进一步考虑在休眠调度策略中引入QoS 需求约束，在满足网络覆盖度和连通性的基础上，通过合理调度节点的工作状态更好满足无线传感网特定应用场景的服务需求。