监测无线传感器网络休眠调度算法

毛建兵，田永春，姜永广

（中国电子科技集团公司第三十研究所，四川 成都 610041）

0 引言

无线传感器网络[1]是一种携带多种类型的微型传感器元件，通过在监测区域内大量密集部署构成一个自组织网络完成感知信息收集并分析处理的应用型网络。传感器网络低成本、低功耗、无人值守、网络化信息感知等优点使得其在民用和军用上均体现出极高的应用价值，被誉为21世纪改变世界的十大新技术之一[2]。受限于工作环境条件，传感器网络节点能量供应通常依赖于电池，并且在使用过程中难以更换或是进行充电补充。能量的限制是影响传感器网络广泛应用的关键问题之一[3]。

提高能量利用效率和延长网络寿命是无线传感器网络设计的首要目标。相对于传感器网络节点其它功能模块，通信模块是能量消耗的主要部分[4]。因此，通信节能措施成为一直以来研究的重点。通信节能可以从2个方面进行考虑[5-6]：①功率控制，通过为节点选择合适的发射功率避免无谓的功率消耗；②休眠调度，通过控制传感器网络节点在活跃状态和休眠状态之间合理切换，降低网络整体能耗。

面向长时间监测应用的任务需求，无线传感器网络休眠控制技术提出了如下要求：

1）在满足应用要求的条件下，应该尽可能多地让冗余节点进入休眠状态，减少区域能量消耗。

2）在适当的时机，休眠节点唤醒并接替活跃节点的任务，避免节点之间能量消耗水平的不均衡性，延长系统任务执行的生命时间。

3）在任意时间，网络所覆盖的区域保持一个连通的网络，避免网络出现区域分割而丧失完整系统的监测能力。

4）在目标事件发生时，传感器网络节点获得的感知信息应该能够保证及时、快速地向sink节点报告并处理，保证时效性。

5）休眠调度对所采用的无线传输技术体制、路由算法、平台硬件特性等没有特殊的依赖性和约束限制，适应性良好。

6）集中式算法难以保证应用系统的可靠性和安全性，因此调度算法要求采用分布式设计。

针对上述应用要求，提出了一种分布式自适应休眠调度算法。算法运用了构建极大独立集的思想，通过各个网络节点的本地邻居信息交互和启发式算法执行，动态自适应地调度决定节点的休眠与活跃工作状态，在保证网络连通的条件下使得活跃节点数量尽可能小，提高节点能量的利用效率。

1 系统模型

考虑一个区域监测覆盖随机部署的无线传感器网络，网络中包含一个sink节点和若干个相同配置的传感器节点。网络随机部署后，各节点相互连接构成一个全局连通的网络，其中sink节点为网络的信息汇聚中心，传感器节点采集的各类感知数据均向sink节点进行递交上报。面向目标监测应用，传感器节点感知数据的获取通常以目标事件为驱动，并在事件发生的整个过程中持续采集上报信息。

传感器网络节点部署工作之后，sink节点首先采用广度优先搜索方法进行网络发现和初始化，向网中广播发送probe报文。报文中携带一个level计数器，各网络节点收到probe报文后将level计数加1然后转发。为了避免广播冗余转发，节点只转发level值小于当前已收到的最小level的probe报文。这样，通过sink节点的probe报文搜索，每个传感器节点将获得所处位置到 sink节点的通信层次距离，称为层次级别。

2 节能休眠调度策略

由于大量节点密集部署的随机性，无线传感器网络不可避免地存在很大一部分冗余节点。冗余节点在监测过程中被认为是能力过剩的多余节点。因此，如果整个网络所有节点同时进行工作，不仅造成不必要的资源浪费，还会使得监测数据收集存在严重的高度相关性和冗余性，增加通信传输的冲突和开销。

为了有效利用冗余节点资源，延长网络使用时间，在不影响系统效能的条件下，自适应地对网络节点进行有规律地休眠和唤醒调度操作，使得节点之间以轮替的方式交互进行工作，降低能量消耗速率，平衡各个节点的剩余能量水平，避免某些节点过早地能量耗尽而失效，致使整个传感器网络丧失应有的效能。

为了实现节点之间的轮替交互工作，休眠调度采用周期性调度方式。如图1所示，网络节点工作时间按周期T进行划分，在每个周期T开始，所有网络节点执行休眠调度算法。根据调度结果，各个网络节点在周期T剩余时间内进行休眠或是保持活跃状态。

图1 休眠调度控制

监测应用中，由于事先并不知道目标事件何时何地发生，因此传感器网络节点需要时刻保持感知“警惕”。在节点休眠过程中，可能因为目标事件的突然发生，节点收集获得的数据需要立即向sink节点递交上报，因此休眠节点周围需要至少存在一个一跳可见的邻居活跃节点，并且邻居活跃节点能够通过其它活跃节点完成向 sink节点的多跳中继转发，即活跃节点要形成网络的连通骨干。为了更多地节能，调度算法还需要使得网络中活跃节点数量尽可能少。

从数学模型角度分析，上述休眠调度问题可以视为求解最小连通支配集问题。在任意图中求解最小连通支配集是NP（Non-deterministic Polynomial）问题[7]，因此在实际应用中通常采用启发式算法来近似求解。传感器网络节点数量非常多，采用集中式算法依赖于网络全局拓扑信息的获取，实现上比较困难[8]。本文采用分布式算法设计，节点只需要知道邻居信息。

3 算法设计

3.1 邻居信息交互

在调度算法执行时间开始，每个节点首先广播hello-1报文，表明自己的状态。报文中包含节点的身份 ID，初始总能量信息tE，当前剩余能量信息Er，能量消耗速率 Ri（前一调度周期能量消耗量），节点层次级别 Li。这样，每个节点在hello-1报文信息交互之后，可以收集获得其所有1跳邻居完整的状态信息。

连通度反应了节点的通信覆盖能力。为了使得每个节点能够进一步掌握邻居节点的连通度信息，节点发送第2轮hello-2报文。报文中携带节点连通度iC、身份ID等内容。

3.2 休眠调度控制

节点在获得邻居信息之后，采用启发式机制在本地决定自身的休眠/活跃工作状态。支配集节点的选取运用了构建极大独立集的思想。初始时刻，节点状态state均置0，执行算法设计如下：

1）节点比较自己的层次级别 Li和所有邻居的层次级别 Lj，找出所有 Li= Lj的节点构成集合A，集合大小|A | = m 。

2）集合A中，将节点的连通度 Ci进行大小排列，即 C1≥ C2≥ … Cm，并分别计算各个节点的能量水平Ei= ErEt。

3）节点根据下列条件判断是否成为支配节点：

条件1 如果节点是其中连通度最大的节点，并且能量水平满足ErEt＞Eth（Eth为一门限参数）以及Ri＜（为集合A中平均能量消耗速率），则节点将其自身状态state变更为1。

条件 2 如果 A中不存在满足上述条件 1的节点，则从 C1至 Cm依次查看各连通度大小的节点。如果连通度为 Ck的节点 k，其能量水平满足Ek＞&Ek＞（为集合A中节点平均能量水平），则节点将其自身状态state变更为1。

条件3 如果A中不存在满足上述条件2的节点，则集合 A中能量水平最大的节点 i，即有 Ei=max ｛ E1, E2,… ,Em｝，将其自身状态state变更为1。

4）状态state = 1的节点成为新的支配节点，并发送dominating消息通告周围邻居，消息中包括节点ID和状态state。

5）状态state = 0的节点接收到dominating消息后，变更自身状态为state = 2，成为被支配节点。节点记录消息发送的支配节点的ID和state，然后发送dominated消息，向自己的邻居通告自身状态的改变。收到 dominated消息的节点相应地修改邻居节点的state状态记录。

6）如果邻居节点中仍有state = 0的节点存在，则节点剔除state≠0节点后再次重复执行算法1~6。

利用上述算法，网络中所有节点被分为2类：支配节点和被支配节点。支配节点将在接下来的剩余周期时间内一直处于活跃工作状态，执行数据的收集和转发任务。由于支配节点的选取始终围绕节点的一跳范围邻居开展，因此支配节点集合能够有效保证任一节点至多经过三跳通信可达另一个支配节点。

为了进一步构造一个连通的支配集，需要选择部分被支配节点作为连通节点将分散的支配节点相互连通。为了减少活跃节点数量，增加的连通节点数量应该尽可能地少，从而保证整个连通支配集网络具有较小的能量消耗。

由于算法在支配节点的选取过程中，已经充分考虑了节点的层次级别，并且考虑到传感器网络数据传输以sink节点为中心的汇聚特性，连通节点的选取只需要在能够连接相邻层次级别支配节点的被支配节点中产生。

连通节点的选取算法设计如下：

1）对于state = 2的被支配节点，若其邻居节点中同时存在属于相邻2个不同层次级别的state = 1的节点，则节点广播发送connector消息，其中包括自身的ID和相邻支配节点的ID。

2）支配节点收到 connector消息后，由层次级别更小的支配节点决定选择哪个connector发送节点作为连通节点。选择的依据为当前剩余能量最大的connector发送节点。

3）支配节点将选择结果通告给 connector发送节点。

4）收到通告的 connector发送节点确认自己的连通节点身份，修改状态为state = 3，并广播通告周围邻居节点。收到通告的节点将其记录为一个新的支配节点进行使用。

通过上述算法执行，节点state = 1&3的节点成为网络的连通支配集，在接下来的调度周期时间内一直工作，构成网络数据传输的主干。其余state = 2的节点则可以进入休眠状态，根据自身需要或在异常事件发生时唤醒，通过邻居支配节点向sink节点发送数据。

为了保证节点将能量消耗的平衡性，算法设计节点周期性地调度决定自身的工作状态。在一个周期时间结束之后，所有休眠节点通过定时器唤醒，再次执行调度算法，决定下一个周期的工作状态。

4 算法性能分析

通过仿真技术对算法进行比较分析。场景设定如下：在1 000 m×1 000 m大小的区域内，采取随机方式布设一定数量为n的传感器节点，sink节点位于区域的中心。节点初始能量2J，在每个周期时间T=600 s内将有 10个节点随机产生业务量128 byte的事件通告数据向sink节点传输。采用与文献[9]相同的经典能耗模型，假设节点发送和接收的能耗为 5 0 nJ/bit，传输能耗为 1 00pJ/bit/m2。网络中节点采用最短路径优先算法确定向sink节点转发的选路。此外，节点在活跃状态下单位时间能耗为10 uJ/s，在休眠状态下单位时间能耗为100 nJ/s。节点失效的能量阈值为0.05 J。

仿真试验将提出的算法与文献[10]基于节点 ID的调度算法扩展多点中继（EMPR，Extended Multipoint Relays）进行比较，分别对比分析了在不同网络节点数量条件下的活跃节点数量和网络生命周期大小，算法中thE 门限参数设置为 0.5。如图 2所示，分析结果表明，在一定的网络覆盖区域大小内，良好的调度算法设计使得节点数量的增加并不会导致最终活跃节点数量的大幅增加，新的调度算法也保持了较小的活跃节点数量。

网络生命周期以第1个节点“失效”前网络持续的有效工作时间为准。如图3所示，与EMPR算法相比，新设计的算法由于考虑了冗余节点能量的利用，因此使得网络获得了更长的生命周期。并且可以看到，随着网络节点数量的增加，冗余节点也不断增加，更多节点通过调度算法参与轮替交互工作，使得网络的生命周期越来越长。

图2 网络活跃节点数量分析

图3 网络生命周期分析

5 结语

面向监测应用的无线传感器网络，冗余节点大量存在。研究提出了一种休眠调度算法，通过分布式算法执行，综合考虑节点层次级别、实时的能量消耗、连通度等因素进行休眠控制，使得节点之间轮替交互工作，提高能量利用效率。仿真分析结果表明，算法能够很好地控制网络中活跃节点数量，提升网络生命周期时间性能。

[1] 夏少波, 许娥.无线传感器网络WSN探究[J].通信技术,2010,43(08):18-19.

[2] 李建中, 高宏. 无线传感器网络的研究进展[J]. 计算机研究与发展, 2008, 45(01): 1-15.

[3] 王彦明, 朱怡安, 龚彬. 基于 Mobile Agent的无线传感器网络管理框架[J].信息安全与通信保密, 2008(06):98-101.

[4] ANASTASI G, CONTI M, FRANCESCO M D, et al. Energy Conservation in Wireless Sensor Networks: A Survey[J]. Ad Hoc Networks, 2009, 7(03): 537-568.

[5] PODURI S, PATTEM S, KRISHNAMACHARI B, et al. A Unifying Framework for Tunable Topology Control in Sensor Networks[R].USA:University of Southern California, 2005:1-15.

[6] 吴雪, 马兴凯. 无线传感器网络拓扑控制策略研究[J].通信技术, 2009, 42(03): 161-163.

[7] 唐勇, 周明天. 基于极大独立集的最小连通支配集的分布式算法[J]. 电子学报, 2007, 35(05): 868-874.

[8] 曾曦. 论无线自组织网络的基本原理与操作[J]. 信息安全与通信保密, 2009(05): 106-108.

[9] HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002,1(04): 660-670.

[10] WU J, WEI L, DAI F. Extended Multipoint Relays to Determine Connected Dominating Sets in MANETs[J]. IEEE Transactions on Computers, 2006,55(03): 334-347.