综述无线传感器网络路由算法

A Survey on Routing Algorithms in Wireless Sensor Networks

摘要: 传感器网络是由能量有限的传感器通过自组织形成的自助网络，其拓扑结构由作为构成元素的传感器依据发射信号的强弱构建而成。研究工作者从不同的角度，侧重不同的性能指标，设计了大量的传感器网络的路由算法。依据相应的路由算法，让数据信息在网络收集与存储转发，完成数据从源点送到汇聚点的任务。传感器网络的路由算法各异，对已有路由算法的总结分类，有助于设计出新的算法。我们从拓扑控制、能量优化与传输耗能控制、网络的服务质量等角度，综述路由算法，将路由算法归纳分类。认为路由算法的最终目的，在于让无线传感器网络的性能指标达到预定的要求，延长网络寿命，同时使网络具有好的健壮性。

Abstract: Wireless sensor networks are self-organized and consist of sensors with limited energy whose topological structures are constructed according to the strength of the signal transmitted by sen-sors as constituent elements. The researchers have designed a large number of routing algorithms from different perspectives and focusing on the performances of wireless sensor networks. Data are sent from the source to the sink in the wireless sensor networks by the means of the collection, storage and forwarding of data signals. We review and classify heterogeneous routing algorithms on wireless sensor networks. Those issues are considered in the points of topology control, energy optimization, transmission energy consumption control and the quality of the network service, etc. We think the ultimate purpose of the routing algorithms is to prolong network lifetime while making the network robust. In the meantime, let the performances of wireless sensor networks meet the predetermined requirement.

1. 引言

无线传感器网络(WSNs: Wireless Sensor Networks)通过无线通信技术，让大量的具有感应、计算、存储和无线通信能力的微型传感器建成一个自组织、自适应、多跳的无线传感器网络。无线传感器网络在多数时间必须保持低能耗，对带宽的要求不高。传感器网络在军事上和民用方面均有广泛的应用，其实用性非常强。行军作战中，由于机构与人员的移动性强，使用固定的接入点不能满足要求，而且固定的设施易为敌方发现和毁坏，各类信息的传递可以使用移动设备(如：车辆、坦克、舰艇、飞机等)安装有发射与接收功能的设备(如传感器)完成。无线传感器网络是无线(移动)自组网的一个子集。民用方面，大量手机、笔记本、车载系统等设备，在移动过程访问互联网，通过移动自组网络完成。在一些不方便安装固定设施的地方：如抗洪救灾现场、野外动物生活习性等的监控、病患的实时监控，以及不方便使用固定装置的各种情况，均可以通过移动自组网络达到监控的目的。从处理方式和数据角色地位的不同，研究传感器网络的应用主要侧重于三个方面：以数据为中心、层次型拓扑结构和基于局部性。从应用领域来分类，传感器网络体现为各种各样的物联网IoT (Internet of Things)，如：环境保护与监测，战争中对敌情的侦查和对兵力、装备、物资的监控，医疗中对患者的护理和对病房的监测，在危险工作环境中的安全监测，城市交通管理、建筑物内部的温度/照明/安全控制 [1] [2] [3] 。无线传感器网络中每个传感器所携带的能量有限，在一些危险或特殊的环境中安置传感器作为网络设备，节约传感器自身携带的能量，延长传感器网络的生命周期显得尤其重要。近年来，无线传感器网络是计算机领域的研究热点。

无线传感器网络是一种任务型网络，其基本功能是进行数据收集与发送传输、数据融合，无控制中心、自组织、资源有限、动态拓扑是其主要的特点。无线传感器网络自组建网的构成方式，涉及多方情况的规划与决策。考虑到组成网络的微型传感器的能量及存储量受限，传感器网络的各种任务必须协同合作与协同控制。在研究无线传感器网络的路由协议、网络安全等方面，引入博弈的方法，建立可选的策略域并设计合适的效用函数，综合考虑各方面的影响因素，得到最佳的解决方案 [4] [5] ，使传感器网络的通信功能可以顺利实现。

2. 相关工作

组成无线传感器网络的微型传感器的能量、计算能力和存储容量均有限，无线传感器网络的生存时间成为设计路由协议考虑的主要因素之一 [6] - [22] 。如果注重数据的安全性，需要考虑传输信道的利用率，同时兼顾数据的传输服务质量，设计网络协议时较注重快速恢复能力、延迟性功能 [5] [9] [23] - [28] 。数据在任何网络中传送，丢包情况在所难免，设计具有容错性的协议非常重要 [23] 。布局合理的无线传感器网络，均已经将网络的覆盖范围设定好。正常情况下，在指定范围内的数据均能够被送达汇聚结点(通常也称之为基站)，但是实际使用过程中每个微型传感器接受数据的不均匀性，可能导致实际覆盖范围与设计的理论上的覆盖范围的不一致性情况出现。某些传感器结点在无线传感器网络失效之前能量耗尽，导致某些数据不能送达汇聚结点，针对这种情况，我们需要有填补出现的空洞的解决方案 [7] [27] [29] [30] 。

传感器网络能量的消耗涉及到多个方面，数据存储转发作为无线传感器主要功能之一，涉及数据存储和数据的转发两个方面的能耗。从数据的传播来考虑，传感器又分为发出信号的结点与接收信号的结点。数据接收过程中，分为接收数据消耗的能量与排队等候转发的存储数据所耗费的能量；数据的转发需要能量，包括数据转发前信号放大需要的能量，传播数据需要的能量。

从减少能量消费、提高网络服务质量与拓扑结构考虑，路由选择协议可以分成四类，虽然这四类有交叉性。第一类是控制每个结点的数据传送的能量消耗级次 [29] [31] [32] [33] ；第二类是以主要能量消耗优化为目标的路由选择 [4] [23] [31] [34] ；第三类是控制网络的拓扑结构 [7] [8] [9] - [22] [24] ，拓扑控制或功率控制通常指的是通过网络的拓扑结构，调整每个节点的传输范围的发射功率；换句话说，拓扑控制确定了在每个节点的发射功率。数据在无线传感器网络中转发时，确定结点是否参与数据的传递、参与数据融合，结点的参与方式形成了网络的拓扑结构。第四类是以服务质量为衡量目标 [25] [26] [27] [28] ，主要涉及可靠性方面的特征，例如安全、正确且时延较少地将数据传送到目的结点，确保服务质量，减少或扼止丢包与连接失败的情况发生，使网络具有快速恢复的功能，同时在可靠性有保障的前提下尽量增加网络的吞吐量。此外，无线传感器网络的研究，依据传输内容的分布情况设计路由选择算法 [10] ，采用单播或组播方式传送数据。无线传感器网络的组成单元是微型传感器，合理布局无线传感器网络的设备，微型传感器安放时尽量做到减少发射信号间的干扰，提高传播质量；传感器进行通讯时使用一定的发射频率，拓宽供选择的无线射频范围，有利于数据的传送与网络性能的提高 [35] 。

下文中，我们分别从不同的角度阐述无线传感器网络的研究。首先，从网络拓扑控制方面着眼；接着，概述以能量优化为目标的而设计出的算法，分析能量控制的策略；然后叙述以服务质量为衡量准则的情况；最后，简要说明我们对路由算法的出发点和目的的理解。

3. 网络拓扑控制算法

无线传感器局域网络是自组形成的，每个微型传感器通过定时发射无线信号探知邻近的传感器，建立邻接关系。传感器之间的拓扑形式有多种：扁平(flat)拓扑结构 [4] [24] [29] [31] [32] ，层次型结构 [7] - [22] [30] [35] ，块状结构。扁平拓扑结构中，除了网络汇聚结点外其余的每个结点同属一个等级，彼此自由地依据地理位置及其发射功率的建立邻接关系。层次型结构中，除了网络汇聚结点外其余的结点之间有隶属关系，可能属于不同的层次，结点只将数据传送给自己的上层结点，同一个结点的所在层次可能动态变化。块状结构中，传感器按它们所处的地理位置，分成不同的区域(类似于有线网络中的自治系统)，相邻区域的传感器之间的信息传递类似于有线网络中选择的BGP (Border Gateway Protocol)发言人(BGP发言人往往就是BGP边界路由器)，隶属于扁平拓扑结构，参见图1，图2。

3.1. 扁平拓扑结构

在非层次型拓扑结构的无线传感器局域网中，每个结点处于同等的地位，针对不同的待优化特性，数据传送时选取路由的方式不同。

Figure 1. Single-hop and Multi-hop networks

图1. 单跳与多跳网络

Figure 2. Hierarchy and flat structure

图2. 层次与扁平结构

考虑到传感器网络中传感器结点的能量一直处于动态变化之中，以网络寿命极大化、能耗极小化为准绳，蔡钊等 [4] 用博弈论的思想提出了一种WSN拓扑控制算法。构建了势博弈的拓扑控制PGTC (Potential Game Topology Control)模型(N, P, u(x))，其中结点域N、策略域P、效用函数u(x)。定义最短潜在寿命、结点度值各为主要与次要效用函数，并且以最短潜在寿命为博弈的势函数。在策略域P中，主要与次要效用函数协作下设计出能效最佳的算法。理论分析得出纳什均衡点为势函数取得最大值的点，也是优化问题的最优解，即帕累托最优解。传感器的控制过程与转发过程具有可分离性，让传感器结点具有一定的计算功能(让簇头携带其中的调度模块，进行路径的分配)，宛考等 [6] 对于软件定义网络系统中的调度算法设计了新的算法，使得调度算法与网络实体的运行状态的信息收集和评价体系的权值选择相分离，达到网络中过程控制与数据收集、整理、融合相分离。传感器结点执行传输数据的之前，利用其控制过程，将结点的状态信息添加到待转发的数据中，对数据流进行融合、分类，传感器结点依据网络中的状态信息参数选择最短路径进行数据转发，达到减少能耗的目标。Miguel Sepulcre等 [24] 针对无线传感器网络中各结点处于同一层次的情况进行研究。设计多路径路由协议，采用具有自适用的、随机线性的路径编码的方法选择最佳路由。每个结点的窗口大小为某固定值，为确保服务质量，任何一对结点之间均有两条以上的路径信息。杨訸等 [29] 讨论了WSNs结点调度算法，从感知覆盖与通信覆盖两者权衡考虑，尽量减少冗余的传感器结点。设计了在蜂窝式拓扑结构的网络中，添加桥梁“结点”去填补“空洞”现象，使得整个网络达到全“通信覆盖”和全“感知覆盖”。信俊昌等 [31] 依据过滤思想设计了一种滑动窗口轮廓的查询(数据丢弃原则，丢弃数据减少传输的数据量，达到延长生存时间)算法，负载较高且剩余能量较低的结点构成轮廓。轮廓中的结点是影响网络生命活力的关键因此，算法持续地维护滑动窗口的轮廓查询，有选择地从轮廓中选择支配结点得到支配集和覆盖集，建立完整的网络拓扑结构。滑动窗口中存储一定数量的待传递的数据，这些数据经过滤后传送，分布式地、自适用地选择轮廓中的结点及传输路径，进而执行结点的存储转发功能。彭颖等 [34] 分析了移动网络中基于最优停止理论的数据传输能耗优化策略，考虑了单信道中数据生成速率与传输延时已知的情况下，信道质量随着时间变化。信道质量的变化依据信道增益函数周期性服从某种规律(如Rayleigh分布、Rician分布)，在给定数据传输率情况下，以数据传输能耗最小为目标考虑了数据的发送与停止的时间，选择最佳的发送与停止时间。

3.2. 层次型结构

在层次型网络拓扑结构的无线传感器局域网中，隶属不同的层次的结点有：汇聚结点(基站)、簇头结点、普通结点等，不同的簇区域将整个网络划分成若干部分，每个簇中的数据传给汇聚结点之前，由簇头收集。

在静态的传感器网络(即：传感器一旦布置好，就不再发生位置改变)中，簇头结点百分比的期望值确定，首先通过自适用算法选择簇头，然后网络中其余的结点自适用地加入某一个簇区域，形成非簇头结点、簇头结点、汇聚结点这样三个层次的拓扑结构。W.R. Heinzelman [9] 等针对第一通信模型，提出了基于簇分层的LEACH (Low energy adaptive clustering hierarchy)算法。算法分成二步完成：第一步建簇阶段，第二步稳定阶段，数据在网络中依次进行存储与转发；之后重复第一、第二步的动作，直至网络生命终结。建簇阶段：簇头选择与簇成员确定过程。簇头的生存时间动态变化，每个结点独立地、分布式地参与竞选簇头。竞选簇头时，给结点n (n代表任意一个结点)定义一个阈值T(n)，同时为结点n分配一个(0, 1)范围的随机数p；若p小于T(n)，则结点n成为簇头；被选上为簇头的结点n将自己为簇头的信息广播通知其他结点，同时重置T(n) = 0，在后续选择中结点n不再被选为簇头。簇成员确定过程：非簇头结点根据信号的强弱选择一个簇头，并加入该簇。重复这种方式，直到有足够的簇头，所有簇区域能够将整个无线传感器网络覆盖为止。

T(n)定义为簇头结点百分比的期望值P、当前轮次、非簇头结点的百分比的函数，具体如下：

$T\left(n\right)=\{\begin{array}{l}\frac{P}{1-P\times \mathrm{mod}\left(r,1/P\right)},n\in G\\ 0,Otherwise\end{array}$ (1)

其中，r是当前轮次，G是在的1/P轮中非簇头结点的集合。若每轮产生一个簇头结点，mod (r, 1/P)则代表在第r次重复中成为簇头的结点数目，G是在最后的1/P轮中非簇头结点的集合。

结点n的初始能量为E_{n_max}、剩余能量(也称为当前能量)为E_{n_current}。E_{n_current}的值与结点n选为簇头呈

正相关，故在T(n)的计算中加入E_{n_current}的影响因子 $\frac{E_{n\_current}}{E_{n\_\max }}$ ；经过多次选择簇头后，E_{n_current}变得很小时

重置T(n)，认为结点的剩余能量多或未成为簇头的结点成为簇头的可能性更大，T(n)的计算增加影响因子

$\frac{E_{n\_current}}{E_{n\_\max }}$ 、 $\left(r_{s}div\frac{1}{P}\right)\left(1-\frac{E_{n\_current}}{E_{n\_\max }}\right)$ [12] 。

调整了T(n)为：

$T\left(n\right)=\{\begin{array}{l}\frac{P}{1-P\times \mathrm{mod}\left(r,1/P\right)}\cdot \frac{E_{n\_current}}{E_{n\_\max }},n\in G\\ 0,Otherwise\end{array}$ (2)

或 $T\left(n\right)=\{\begin{array}{l}\frac{P}{1-P\times \mathrm{mod}\left(r,1/P\right)}•\left[\frac{E_{n\_current}}{E_{n\_\max }}+\left(r_{s}div\frac{1}{P}\right)\left(1-\frac{E_{n\_current}}{E_{n\_\max }}\right)\right],n\in G\\ 0,Otherwise\end{array}$ (3)

其中：G为在P轮未成为簇头的结点集合，r_s为结点n没有成为簇头的连续循环次数，当r_s接近于或等

于 $\frac{1}{P}$ 时，将重置阈值为初始阈值。当节点n成为簇头，将r_s重置为0。

LEACH算法确实比非层次结构的平面多跳路由算法更优，仿真实验表明，它延长了的网络生命周期 [9] 。LEACH算法只考虑了各传感器具有相同能量和性能的网络，没有考虑微型传感器能量有差异的情况；LEACH算法选取簇头结点具有随机性，导致簇头分布在网络中可能不均匀；LEACH算法是基于单跳的路由算法，即簇头直接将信息传递给汇聚结点，没有考虑通信的代价。针对这些情况，研究工作者改进了LEACH算法，改进的LEACH的算法有C-LEACH (Centralized LEACH) [12] 、 MODLEACH (Modified LEACH) [13] 、Stable Election LEACH [14] 、MH-LEACH (Multi hop LEACH) [15] 、Two Level-LEACH (Two levels LEACH) [16] [17] [18] 、V-LEACH (Vice-LEACH) [19] [20] [21] ，仿真实验比较了LEACH算法及相关算法的性能，进行了相应的参数分析 [10] [11] 。

C-LEACH [12] 算法中引入了中心结点，中心结点(汇聚结点充当)收集了所有结点的地理位置、剩余能量等信息，确定簇头结点。C-LEACH得到了均匀分布的簇头，但是只支持簇头结点到汇聚结点的单跳路由方式。

MODLEACH [13] 算法对更换簇头的方式进行了改进，不需要在每个轮次中进行簇头的更换，只在其能量小于阈值时才进行换新；Stable Election (heterogeneous) LEACH [14] 算法，依据结点的初始能量分为两类：正常结点和高级结点，高级结点有更多机会成为簇头；MH-LEACH (Multi hop LEACH) [15] 算法在处理数据转发时，设计簇头不是直接将数据发送给基站，而是将它交付给位于到BS (Base Station)的路径上的传感器结点，然后再传给基站。M. Usha1等 [16] 综述LEACH算法的优点与不足，比较了改进算法与LEACH算法，Z. Fui等 [17] 从能量均衡角度改进了LEACH算法，在部分簇区域引入了第二簇头负责数据接收与数据融合，簇头负责发送数据，达到平衡能量消耗，延长网络寿命。增加第二簇头的簇区，簇头或者离汇聚结点较远，或者剩余能量在本簇中较少。Two Level-LEACH [18] 算法设计了两个簇头：第一簇头和第二簇头，将任务划分为两个组成部分：数据收集与数据传输，第一簇头用于传送数据，而第二簇头用于收集数据。改进的算法V-LEACH [19] [20] [21] 进行簇头选择时，选出了簇头和副簇头，副簇头在簇头失效时充当簇头，完成簇头的任务。Nigam, G. K.等 [30] 研究了用粒子群PSO (particle swarm optimization)优化LEACH的PSO-LEACH算法。

无线传感器网络的HEED (A Hybrid, Energy-Efficient Distributed clustering approach)算法 [22] 着眼于分层思想，认为无线传感器网络中的簇头结点与汇聚结点以一跳的形式进行数据传输不可取，将分散无线传感器网络中的结点划分成若干个簇，每个簇选取一个簇头，簇头负责与汇聚结点的数据通信。分层次、多侧面的方式选取簇头，选择时考虑主次两个因素：主要因素是结点当前的剩余能量与初始能量的百分比，次要因素是簇内的结点之间的通信耗能，以平均最小可达能量为衡量准则。

HEED算法中剩余能量较多的结点具有较大的当选概率，在结点分布相对密集的区域，结点成为簇头的概率较大。HEED算法可以有效控制簇头的分布，使其分布尽量均勾，也让能耗尽可能均匀地在网络区域内进行，避免局部结点失效影响网络寿命。算法选取簇头时，既利用了剩余能量信息，也利用了网络结点通信开销信息。HEED要消耗能量进行每次的簇头选择；此外，在进行数据通信时，先将数据从源点传到本簇区域的簇头，簇头利用路由路径传到汇聚结点。路由路径从源点到汇点，除两端的端结点外，其余的中间结点(也称为中继结点)均为簇头。路径的选择时忽视了中继结点的情况，没有考虑由于每个簇中的内部结点相对固定可能引起的“能量洞”问题。

匡哲君 [7] 对于静态布局的无线传感器网络，从消除“能量洞”的角度出发，提出了对HEED算法的改进，即基于角色成员关系的分簇算法(A role, energy-efficient, membership clustering, 简称REEM)。考虑角色、关系两个方面：从簇关系考虑，有成员结点与非成员结点两种；从结构层次来划分：有汇聚点，中继点和源点三种角色，同一层次与同簇不同层次的结点角色有着内在联系的。簇的内结点有中继点和源点两种角色，不同角色凭借自身拥有的能量来进行转换(汇聚结点剩余能量 > 中继结点剩余能量 > 源点剩余能量)，路由选择时未被选中的中继点处于休眠状态，所以中继点在休眠状态与工作状态之间转换。

Xu [36] 等研究了GAF (Geographical adaptive fidelity)算法，以结点的地理分布为依据进行簇划分，簇是由地理分布上的某一正方形区域中的结点所组成；每一个簇随机选择出一个结点作为簇头，相邻区域的两个簇之间的结点通过簇头可以相互通信。GAF算法不能使能量在网络中均匀消耗。Gulnaz Ahmed [37] 等依据能量的多少将簇区域区分为：正常能量簇区域、高能量簇区域和超高能量簇区域，相应的簇头也分成三类，设计了基于层次的簇算法SEED (Sleep-awake Energy Efficient Distributed)。不过，簇头与汇聚点之间的信息传递是单跳到达的。表1给出了一些有代表性的算法及其特性，跳数指簇头到汇聚点的跳数，n是网络中的结点数量。

Table 1. Several typical algorithms and their features

表1. 一些典型算法与其特性

4. 能量优化为目标的算法及传输耗能的控制

要设计无线传感器网络路由算法或网络拓扑结构，既要满足感知覆盖，使通信质量符合要求，又要尽可能延长整个网络的生命周期，确保数据均能传送成功且尽可能节约传输能量。无线传感器网络运行中，传感器网络主要能量消耗是数据在信道中传播所消耗的能量。有众多研究工作者以能量优化为首要因素设计路由算法时，以达到控制数据信息在网络中收发过程的能量消耗为目标 [8] [29] [32] [33] [34] [38] [39] [40] [41] 。

在无线传感器网络中，结点的能耗主要包括三个方面的能量消耗：数据发射(或接收)时的能量消耗，数据在通信线路中传播时的通信能耗，以及数据发射前在路由器中增强无线信号所消耗的能量。

以能量控制为终极目的的算法，可能基于层次型结构拓扑网络，如：尚小溥 [8] 设计静止的传感器网络中M-CEA (Mutex Cluster Establishment Algorithm)和H-CEA (Hypergraph Cluster Establishment Algorithm)算法，遵循LEACH算法选取簇头的规则，依据产生的(0 1)区间的随机数与给定的阈值比较选取候选簇头。M-CEA算法可以控制距离汇聚结点远近的簇头结点的数量。M-CEA和H-CEA算法可以让能耗具有一定的均衡性。杨訸等 [29] 同时考虑了网络的蜂窝拓扑结与LEACH算法，设计了基于层次型拓扑结构的RCSC (Communication and Sensing Coverage in the Randomly deployed WSNs)算法。算法RCSC，依照地理位置的正六边形中心安放传感器(即蜂窝式)；考虑到可能有失效结点或有障碍物，选取出桥梁结点填补能量空洞，以传播过程消耗的能量优化为目标，兼顾无线传感器网络的覆盖区域极大。蜂窝式拓扑结构的调度，达到整个网络耗能极小、感知覆盖及通信覆盖区域极大化，延长了网络的生存时间。

在无线网络环境中，数据传播存在信道竞争，无线终端通过载波侦听多路访问/冲突避免机制访问信道。如果能够在信道处于最佳状态时进行数据信号发射，冲突可能会避免。彭颖 [34] 等研究了移动网络中传输能耗优化策略，在给定数据生成率、容许延时状态下，就分布式机会调度中单信道、单设备场景应用最优停止理论，选择最佳信道。无线链路信道增益函数g周期性地服从某种变化(如Rayleigh分布、Rician分布)，且在周期T内保持不变，选择最优时刻和最佳信道，进行数据传送，以达到节约传输能量目的。

Vikas Kawadia [32] 等讨论了无线自助网络中能量控制与建簇。研究了结点非均匀地分散在空间中的场景。每个包的能量控制依赖于源点与终点，在进行能量控制的同时考虑簇的建立。文中给出了3个解决方法。首先提出了称为CLUSTERPOW的方法，由于地理位置的远近不同而导致传播能量的不同，得到不同的路由表。依据地理上的距离的不同，采用不同的路由表选择实现的路径，距离长的需要的传输能量更多，但是可以减少了在路由器中存储数据需要的能量。算法依据这种地理位置上的不同而产生了不同的路由表的策略，实现了在网络层空间复用技术，从而使得信道的传输容量极大化。如果源点与目的地址在地理上的距离达到一定值，使用封装技术，对于发送的数据包采用第二个称之为隧道的CLUSTERPOW (Tunnelled CLUSTERPOW)的协议完成。文中最后设计的一个方法是，MINPOW (Minimum Power)，这个协议运行在网络层，基本思想是让每个结点各自在通信中总的能量消耗上均提供一个最优的路由解法(optimal routing solution)。Swetha Narayanaswamy [34] 等设计并实现了COMPOW (Common Power)协议，利用了地理位置的远近设计路由，极大化整个网络的传输运载传输容量通过提供低能耗路由延长寿命，减少在ＭＡＣ层的竞争。协议有即插即用的特征，它能够与任何能主动地维持路由表的路由协议联合使用。由Linux内核实现了所设计的路由选择，且可以嵌入到任何一个常用的路由协议中。Prasenjit Chanakt [39] 等直接利用能耗的公式估计能耗，通过估计的值来设计各自的算法。通过详细的簇头能耗、成员能耗等计算公式，依据计算结果选择簇头、源点到汇点的路径等，减缓“空洞”现象出现。

另一种着眼于减少能耗的算法设计是基于连通支配集的思路。网络中的每个结点均能够通过连通支配集中的结点进行数据的传播或接收数据。

Wu [40] 提出了寻找连通支配集来实现网络能耗均匀分布的ECDS (Efficient distributed algorithm for calculating Connected Dominating Set in ad hoc)算法从而延长网络寿命。ECDS算法在选择连通支配集时使用能量作为边的权值。算法有两个主要的步骤：一是建立最大独立集，由着色技术来完成该过程；另一个是选取网关结点，通过贪婪算法完成，而且网关结点不属于最大独立集。网关结点用于连通独立集中的结点，进行信息通信。ECDS算法强调拓扑优化，有大量的管理控制消息产生。Chen [41] 利用连通支配集得到网络的动态拓扑结构，设计了SPAN算法完成分布式拓扑结构的搭建。SPAN算法与传统算法最主要的区别在于MAC (Media Access Control)层特点，它采取了协议实现路由吞吐量的增加和延迟的减小，网络拓扑结构中的骨干结点可以自适应、周期性地进入睡眠状态。

5. 服务质量为衡量准则的算法

以服务质量为衡量目标 [23] [24] [25] [26] ，综合考虑网络的时延、容错性、安全性，确保服务质量。出现丢包情况时，相应的结点重新传递被丢弃的数据(利用所在时间间隙的不同，或者利用不同的时间维度完成)，充分利用不同任务的时间维度不同、时间间隙的差异，使得无效网络路径的信息反馈之前就已经利用网络快速恢复功能保证了网络的正常通信。保证网络的服务质量，减少或扼止丢包率，减少连接失败的情况发生。这类研究问题以服务质量为主要因素，能量优化为次要因素。另一种防止因网络结点失效而导致不能确保服务质量思路是，定期给无线传感器结点供给能量，让网络不会因为结点失效而导致网络失去传播信息的功能；在供给能量时，以供给工具停下以供给能量的次数最小作为能量优化目标。

Lakshmi, N. V. S. S. R.等 [23] 就分布式无线传感器网络提出了一种基于QoS (Quality of Service)的层次型路由协议CQRP (Clustered QoS Routing Protocol)，提出了一种方案解决分布式引起的结点移动、连接失败、传递数据的恢复、路由开销与降低丢包率问题。CQRP协议将网络划分为若干簇，每个簇的簇头位于簇的几何中心，所有簇头连接成一条相互可达的路径。在进行信息传递时，簇成员将信息交于簇头，由簇头传递给目的结点。Miguel Sepulcre等 [24] 就严酷恶劣的传播条件下数据传输具有可靠性和满足服务质量，提出了多路径策略。协议类似于有线网络的协议，对可靠性(Reliability)、延时(Delay)、确认(Validation)机制都加以考虑并设置应对方案。任何一对结点之间均构建了多条冗余路径，以确保网络数据传播的可靠性和满足具有容忍延时的服务质量要求。协议适合于其他的基于时分多路访(Time Division Multiple Access based, TDMA-based)的多跳无线网络。

传感器自身携带能量是有限的，在考虑如何有效地给关键结点(如汇聚结点，簇头结点)增加能量，L. Khelladi等 [25] 考虑了这个问题，提出了一种移动充电模式，以最小的路径长度达到访问最多的结点，以给更多的结点充电。通过定期充电，结点不会因为能量的耗尽而失效，协议设计了一种路径方式。

6. 结束语

数据采集与数据的存储转发是无线传感器网络的主要功能。无线传感器网络有6个基本性能指标：能效、生存时间、时延、可扩展性、容错性、安全性，通常侧重于某个或某几个基本性能指标来衡量或评估无线传感器网络。通过对各具特色的无线传感器网络的路由算法的比较，我们了解到这些算法的设计侧重无线传感器网络的某些性能指标。通过从不同的角度和方面研究无线传感器网络，已经设计和实现了诸多的路由算法，它们应用在不同的场景中，如在物联网的底端无线网络的应用实现。路由算法的最终目标在于让无线传感器网络的性能指标达到预定的要求，使网络稳健而且具有尽可能长的寿命。