# 综述无线传感器网络路由算法A Survey on Routing Algorithms in Wireless Sensor Networks

DOI: 10.12677/HJWC.2019.93015, PDF, HTML, XML, 下载: 497  浏览: 1,316

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. 引言

2. 相关工作

3. 网络拓扑控制算法

3.1. 扁平拓扑结构

Figure 1. Single-hop and Multi-hop networks

Figure 2. Hierarchy and flat structure

3.2. 层次型结构

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

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

$\frac{{E}_{n_current}}{{E}_{n_\mathrm{max}}}$$\left({r}_{s}div\frac{1}{P}\right)\left(1-\frac{{E}_{n_current}}{{E}_{n_\mathrm{max}}}\right)$ [12] 。

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

$T\left(n\right)=\left\{\begin{array}{l}\frac{P}{1-P×\mathrm{mod}\left(r,1/P\right)}•\left[\frac{{E}_{n_current}}{{E}_{n_\mathrm{max}}}+\left({r}_{s}div\frac{1}{P}\right)\left(1-\frac{{E}_{n_current}}{{E}_{n_\mathrm{max}}}\right)\right],\text{}n\in G\\ 0,\text{}Otherwise\end{array}$ (3)

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

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

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

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. 服务质量为衡量准则的算法

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)的多跳无线网络。

6. 结束语