无线传感器网络节点调度算法综述

姜威

摘 要： 无线传感器网络以其自组织、低功耗、传输稳定等特点，被应用于监测平台、预警系统、高度危险无人区域的监控系统。由于无线传感器网络中传感器节点由电池供电，电池能量有限，因此能耗问题成为无线传感器网络发展和应用的阻碍，而节点调度是减少网络能耗、延长网络生存时间的重要机制之一。文章详细描述了几种节点调度算法，并对算法做出分析。

关键词： 无线传感器网络； 能耗； 节点调度； 算法

中图分类号：TP393 文献标志码：A 文章编号：1006-8228（2017）04-47-03

Abstract： Wireless sensor networks have been applied to the detection platform， early warning systems and highly dangerous no man's land monitoring system because of their characteristics like self-organization， low power consumption， transmission stability. For the sensor nodes in the wireless sensor network are powered by batteries， and battery energy is limited， the problem of energy consumption hinders the development and application of wireless sensor networks， and the node scheduling is one of the important mechanisms to reduce network energy consumption and extend the lifetime of network. This article describes several node scheduling algorithms and analyzes the algorithms.

Key words： wireless sensor networks； energy consumption； node scheduling； algorithm

0 引言

无线传感器网络（Wireless Sensor Networks，WSN）是可以感知和检查外部世界的传感器，是一种分布式传感器网络[1]，它是21世纪最具有影响力的科学技术之一；无线传感器网络具有规模大、成本低、资源高度受限、节点数目多和自组织等显著的特点。WSN已经广泛应用于环境监控、目标检测、军事民用、等多个领域。在这些应用中，网络生存时间是无线传感器网络监测服务质量的评价标准之一。

在无线传感器网络中，传感器节点是体积微小的嵌入式设备，一般靠电池供电。一方面由于节点体积及资源的受限，导致其能量极其有限；另一方面传感器节点在恶劣的环境下工作，有可能使节点通信受到强烈的干扰甚至遭到破坏，造成能量消耗，无法及时进行能量补充，导致无线传感器网络无法维持正常的工作状态。因此，在保证满足网络通信要求的情况下，如何做到尽可能的降低节点能耗以延长网络的生命周期，就成为研究的重点和难点。对于这样的问题，目前比较合理有效的方法是节点调度策略。

研究人员在节点调度这一领域开展了大量工作并取得一定的进展。本文综述了近年来在该领域取得的一些研究成果。

1 节点调度算法的含义和设计目标

节点调度是指在不影响网络服务质量（如网络覆盖、节点间的连通性）的前提下，将传感器网络中的冗余节点进入休眠状态，使一部分节点保持活动状态而另一部分节点进入休眠状态，降低活动节点的密度，从而降低整个网络能量消耗，延长网络生存时间。

网络寿命是节点调度方法的主要评价指标。但是，传感器网络的最终目的是完成应用相关的感知和传输任务。因此，完成任务的质量也是需要考虑的。除此之外，设计者还需要考虑算法的健壮性、可擴展性和简单性等性能层次的目标[2]。

⑴ 网络寿命。网络寿命有多种不同的定义。最简单的一种是：所有节点都保持正常的时间长度，亦或者定义为正常节点数目高于一定比例的时间。在实际应用中，WSN的网络寿命定义往往需要结合考虑其他设计目标，主要包括下面列出的感知质量和通信质量。

⑵ 感知质量。感知信息是WSN的基本任务，感知质量是评价WSN性能重要指标。感知覆盖率是一项基本的感知质量指标。不同类型的WSN任务对感知质量有不同的要求。例如，目标探测任务的感知质量又称为探测质量，一般被定义为探测到入侵目标的概率和时间长度等；而环境监测任务的感知质量又称为感知精度，一般被定义为收集到的环境信息的准确度。

⑶ 通信质量。通信能力是WSN的基本功能，通信质量也是评价WSN性能的重要指标。类似于感知覆盖率，网络连通度是一项基本的通信指标，用于衡量传感器网络维持节点间多跳联通的能力。此外，对于实时采集任务来说，通信质量一般被定义为有效数据传送比率以及传送时间长度等。

⑷ 能耗均衡性。假如部分节点的能量消耗快于其他节点，那么一旦这些节点提前失效，很容易造成感知覆盖的空洞和网络的分块。

⑸ 健壮性。节点失效在WSN中是常见的现象。例如，部署在灾害现场的节点可能被爆炸损坏，处于休眠状态的节点可能无法被唤醒，算法必须充分考虑各种无法预料的失效造成的后果，保证网络在意外发生的情况下保持正常工作。

⑹ 可扩展性。WSN节点数量巨大，通信开销随邻居数目呈线性或者更快的速度增长。因此，不具有扩展性的算法是不能被接受的。

⑺ 简单性。目前传感器的计算能力相当有限，只有低开销的算法才适合传感器节点。

2 典型的节点调度算法分析

基于节点均匀分布的假设，Wu等[3]人提出了一种基于部署特征的轻量级节点调度算法（Lightweight Deployment-Aware Scheduling，LDAS）。该算法假设节点无法获取准确的位置信息，而是通过获取邻居节点的数量来实现概率覆盖。如果邻居节点数目超过某个阈值（根据应用对于感知覆盖的需求来确定），该节点将从邻居中随机选择部分节点，并发送关闭它们的通知。当一个节点接收到的关闭通知达到一定数量后，它将在一个随机的退避时间间隔后进入休眠状态。该算法不需要准确的位置信息和时间同步支持，保证概率覆盖度，关闭通知的累积可以在一定程度上实现能耗的均衡分布。但是该算法假定节点均匀分布，需要维护邻居节点的数量信息。

Berman等[4]人将节点调度问题视为具有电池寿命和网络覆盖度两重约束的网络寿命最大化问题（Maximization of Sensor Network Life，MSNL），给出了在保持K度覆盖的前提下使网络寿命最大化的分布式算法。节点可以处于活动、休眠和过渡状态。过渡状态下的节点通过判断自己的感应区域能否被其他活动节点或者过渡节点所覆盖，以决定转换到活动状态或休眠状态。该算法通常能保证K度覆盖。但是算法需要精确的位置信息，需要交换状态的状态信息、能量信息，并且没有考虑并发问题，多个邻居节点可能同时进入休眠状态而产生覆盖漏洞。

Yan等[5]人提出参考时间调度方法（Reference Time-based Scheduling Scheme，RTSS）算法，是一种基于时间序列的节点调度方法。整个监测区域被划分为网格，设计目的是减少活动节点的数目，同时保证在连续时间内覆盖所有的网格节点。RTSS把算法过程划分为轮。在初始阶段，每个节点会在[0，T]内随机产生一个候选时刻（T是每轮调度的时间长度），然后广播给位于两倍传感半径范围内的所有邻居节点。对于自己覆盖半径内的每个节点位置，节点对所有覆盖该位置的邻居節点的参考时刻进行排序。对每个网格节点，节点活动状态的起始时刻选择在自己的候选时刻和前一个节点的参考时间的中间点。同样，活动状态的结束时刻选择在自己的候选时刻和后一个节点的候选时刻的中间点。把所有被覆盖的网格节点相关的时间表合并，就得到这个节点最终的调度时间表。为了提高健壮性，这种方法可以支持对制定位置的多重覆盖。该算法实现简单，维护了时间上连续的网络覆盖，基于时间序列的方式实现了负载均衡。但是算法需要精确地节点位置信息和时间的同步支持。

Liu等[5]提出了一种保证连通和局部覆盖的随机节点划分调度方法（Random Coverage with Guaranteed Connectivity，RCGC）。该方法首先使用随机调度方法为每个节点确定组号，然后每组节点工作时再调度其他组的节点进入活动状态来保证连通性。该算法可以保证网络连通和一定的覆盖，将节点调度方法与能源有效的路由算法结合进行了讨论，不需要位置信息，随机调度方法实现简单。但是，算法无法保证目标区域的完全覆盖，随机节点划分方法没有考虑节点能量差异。

Kumar[6]使用的是随机独立调度模式RIS（Random Independent Scheduling）。这种模式通过将时间分段成各个时隙来使各个时隙中的不同节点间的状态相互不受到干扰，节点进入活动状态或者进入休眠状态由数值P来决定，P是一个概率值，从而可以使网络生命周期延长1/P倍。该模式具有简单易行、方便操作、消耗节点能量较少等优点。但是这种模式仅仅适用于节点分布稀疏的网络中，而且受到节点失效问题的影响。

Slijepcevic等[7]根据延长无线传感器网络生命周期、大规模随机抛洒节点产生的节点冗余等网络特性，通过将所有传感器节点的覆盖范围划分成若干个覆盖子集，这些子集互不相交，同一时刻只有一个子集节点处于工作状态，各个子集通过一定的调度机制轮流对监测区域进行监控，从而达到优化网络能量消耗并对整个监测区域形成完全覆盖的目的。但是，该算法在如何划分子集，划分子集的数目才能达到最优是一个NP难问题，很难找到最优解。

3 结束语

本文从节点调度算法的必要性出发，对经典的节点调度算法进行了分析探讨。如何在节点能量有限、生存时间较短还要保证网络服务质量的情况下，利用节点部署的内在冗余特性，延长网络生存时间，是无线传感器网络设计中的一个重要挑战，也是要研究的一个重要内容。

目前的节点调度算法还存在许多待解决的问题，如：现有的无线传感器网络大多假设节点和sink节点位置固定，但在一些特殊的应用场景中节点和sink节点可以连续移动，如何合理的设计算法应对这种变化，同时保证算法的节能高效是一个非常值得研究的问题。此外，文中的算法大多是通过Matlab仿真软件进行模拟，没有在试剂的无线传感器网络应用环境中进行真实的实验，真实的环境中，节点可能会受到温度、湿度等各种因素干扰，如何将这些影响因素考虑进算法中也是值得研究的问题。总而言之，无线传感器网络节点调度算法是延长网络生存时间的一种非常重要的思路，值得进一步深入研究。

参考文献（References）：

[1] Akyildiz I， Su W， Sankarasubdam Y. Wireless sensor

networks： a survey[J]. Computer Networks，2002.38（4）：393-422

[2] 胡湘华，杨学军.传感网节点调度方法综述[J].计算机工程与

科学，2008.30（3）：93-96

[3] Wu K， Gao Y， Li F， et al. Lightweight deployment-aware

scheduling for wireless sensor networks[J]. Mobile Networks & Applications，2005.10（6）：837-852

[4] Berman P， Calinescu G， Shah C， et al. Power efficient

monitoring management in sensor networks[J]. Proceedings of 2004 IEEE Wireless Communications and Networking Conference. Atlanta： IEEE Press，2004.4：2329-2334

[5] Yan T， He T， Stankovic J A. Differentiated surveillance for

sensor networks[C]// International Conference on Embedded Networked Sensor Systems，2003：51-62

[6] Kumar S， Lai T H， Balogh J. On k-coverage in a mostly

sleeping sensor network[J]. Wireless Networks，2008.14（3）：277-294

[7] Slijepcevic S， Potkonjak M. Power efficient organization of

wireless sensor networks[C]//IEEE International Conference on Communications. IEEE，2001.2：472-476

[8] Kumar D. Performance analysis of energy efficient

clustering protocols for maximising lifetime of wireless sensor networks[J]. Iet Wireless Sensor Systems，2014.4（1）：9-16

[9] 金巖，王玲，杨孝宗等.无线传感器网络节点调度算法及研究

进展[J].宇航学报，2007.28（5）：1086-1093

[10] Hai Mo， Zhang Yan-mei， Zhang Yue-jin. Survey on

clustering protocols in wireless sensor network[J].Computer Science，2015.42（1）：6-11