文章目录

Challenges for RoutingEnergy EfficiencyScalabilityAddressingRobustnessTopologyApplicationRouting MetricsQuality-of-Service (QoS)Minimum HopEnergyMinimum energy consumed per packetMaximum time to network partitionMaximum average energy capacityMaximum minimum energy capacityRouting ProtocolsData-Centric RoutingFloodingGossipingSPINDirected DiffusionHierarchical ProtocolsLow energy adaptive clustering hierarchy (LEACH)Power efficient gathering in sensor information systems (PEGASIS)Threshold sensitive energy efficient sensor network (TEEN)Adaptive threshold sensitive energy efficient sensor network (APTEEN)Geographical RoutingMECN (Minimum Energy Communication Network)Geographical ForwardingGreedy forwardingDistance based blacklistingReception based blacklistingBest PRR × distancePRADAQoS-Based RoutingSAR: Sequential Assignment RoutingMinimum Cost Path ForwardingCost field establishment phaseCost path forwarding phaseSPEEDReferences

WSN 中的传感器节点收集的数据通常向基站(也叫网关 gateway 或者 sink) 传播。网关将 WSN 与其他网络连接起来，在那里可以对数据进行分析和利用。路由（routing）是网络层非常关键的任务。我们知道一个节点既可以作为一个对话的发起者来产生并传播它自己的数据，也可以作为中间节点（relay nodes）来转发其它节点的数据。而路由就是指通过一个或多个中间节点建立从源头到 sink 的路径的过程。

Challenges for Routing

由于无线通信的影响以及传感器网络的部署特点，WSNs 中的高效路由面临许多挑战。节点之间需要互相合作来判断自己所处的位置以及它们邻居的位置，从而寻找到到达网关的路径。下面我们介绍几个主要面对的挑战。

Energy Efficiency

因为传感器节点的有限能量资源，在为 WSN 开发任何路由协议时，能量消耗都是主要的关注点。WSN 中路由耗能的两个主要来源：

Neighborhood discovery： 许多路由协议要求每个节点和其邻居节点之间交换信息。节点在通过无线介质交换这些信息时消耗了能量，这增加了协议的开销。为了提高路由协议的能量效率，在不影响路由准确性的前提下，应尽量减少局部信息交换。communication vs. computation：就能量消耗而言，通信比计算处理要消耗更多的能量。此外，在 WSN 中，关注的是提供节点的整体信息而不是某个数据包。因此，我们可以将来自多个节点的数据包聚合到一个数据包中，以减少网络流量且不影响信息内容。此外，我们可以将节点的计算、处理功能整合到路由之中来提升能量效率。例如，在每个节点，我们可以通过计算处理，来消除节点的一些冗余信息。

传统的一些路由算法，如最短路径算法，从能源角度看可能并不适合 WSN。

Scalability

WSN 通常由大量的节点组成。为了能详细观察到某种物理现象，我们可能需要高密度地部署这些节点。大量的节点使每个节点难以获得对网络拓扑结构的全局认识。因此，需要开发在对拓扑结构了解有限的情况下运行的全分布式协议，以提供可扩展性。此外，由于网络中的节点密度很高，局部信息交换也应尽量受到限制，以提高网络的能源效率。

Addressing

网络中大量的传感器节点让我们不可能为每个节点分配唯一的地址。虽然局部的寻址机制仍可用于相邻节点之间的通信，但基于唯一地址的路由协议是不可行的，因为每次通信都需要使用唯一的地址，开销很大。因此，大多数 ad hoc 的路由协议不能被 WSN 采用，因为这些协议需要网络中的每个节点都有唯一的地址。 此外，我们刚刚也提到了，在 WSN 中，关注的是提供节点的整体信息而不是某个数据包。因此，需要新的寻址机制或新的路由技术，使得我们不需要为每个节点赋一个唯一 ID。

Robustness

WSN 依靠网络内的节点以多跳的方式传递数据。WSN 的路由协议依赖于这些传感器节点而不是专门的路由器。因为传感器节点都尽可能地减少成本，因此节点常常会出状况。所以协议的设计一定要避免单点失效（不太恰当地比喻，一只老鼠坏了一锅汤）。此外在数据包传输时，无线通信的环境也有可能造成丢包，协议的设计也要避免依赖于单个数据包的情况。

总之，即使在信道经常出错的恶劣条件下，路由协议也应在传感器和 sink 之间提供有效的传输。

Topology

WSN 的部署可以是预先确定的，也可以是随机部署。虽然可以利用预先确定的拓扑结构来设计更有效的路由协议，但 WSN 中通常采用的是随机部署。因此，某个节点通常不知道网络的初始拓扑结构。然而，网络中节点的相对位置会显著影响路由性能。因此，路由协议应该提供某种机制，以便发现每个节点的邻居节点，并据此做出路由决策。

此外，网络拓扑结构是在动态变化的。由于能源效率至关重要，节点可能会暂时关闭收发电路，这实际上会导致从拓扑结构中暂时删去这一个节点。每当该节点再次满血复活时，它就会再连接入网络，拓扑结构也随之再次改变。节点或者 sink 的移动当然也会改变网络拓扑结构。

Application

应用的类型与路由协议的设计直接相关联。在监测应用中，节点通常以周期性的方式将他们的观测结果传递给网关。因此，静态路由可以用来在网络的整个生命周期内，以保持观察结果的有效传递。

然而，在基于事件的应用中，传感器网络大部分时间处于睡眠状态。每当特定事件发生时，它会立即路由传递此信息。此外，事件的位置不是固定的，它与事件直接相关，因此，每个事件都可能会产生新的路由。

Routing Metrics

Quality-of-Service (QoS)

服务质量用来衡量网络的性能，如端到端时延以及吞吐量。QoS 的选择也和特定的应用类型有关。例如，目标检测和追踪需要较低的端到端传输延迟，而数据密集型网络（如多媒体传感器网络）可能要求较高的吞吐量。

Minimum Hop

用来衡量从源到目的地所需的最少中间节点数量。这个指标的想法是，使用最短路径将会有较低的端到端延迟和较少的资源消耗。

但这个指标本身并没有考虑每个节点的实际可用资源以及节点之间的传输时间，因此，就时延和能耗来说，找到的路径可能不是最优的。

Energy

能耗当然是 WSN 中非常重要的一个指标。具体来说，我们可以用下面的几种方式来对能耗进行说明。在对这几种方式的介绍中，我们都考虑下面这个简化场景：

其中，链路上的数字表示数据包在这条链路上传播的能量“成本”，节点底部的括号数字则是节点的剩余“血量”（能量）。

Minimum energy consumed per packet

目标是使单个数据包从源头到目的地的传播所使用的能量总量最小。也就是说，我们会使用链路上的数字来进行计算。

Source - C - E - H - Destination: 2+2+2+2=8

Source - C - E - G - Destination: 2+2+1+1=6

Source - B - G - Destination: 3+2+1=6

Source - A - D - G - Destination: 1+2+1+1=5

因此会选择 Source - A - D - G - Destination 这条路径。

Maximum time to network partition

network partition 意思是如果网络中的某个节点失效了，那么我们的网络会分割为两个子网络，其中一个子网络的所有节点都到达不了目的地节点。

上图中的 D 就是这样一个节点。如果 D 失效，那么 D、F、I、J 构成的这个子网络的每一个节点都到达不了目的地了。

因此这个指标会尽量避开要经过 D 才能到达目的地的路径，减少对它的消耗。

Maximum average energy capacity

重点是节点的血量，而不是数据包传播的能量成本。也就是说，我们计算的是每条路径节点底部数字的均值，且选择均值最大的路径。

Source - C - E - H - Destination: (5+1+3)/3=3

Source - C - E - G - Destination: (5+1+2)/3=83\frac{8}{3}38​

Source - B - G - Destination: (2+2)/2=2

Source - A - D - G - Destination: (1+2+2)/3=53\frac{5}{3}35​

Source - A - D - F - J - I - D - G - Destination: (1+2+2+1+3+2+2)/7=137\frac{13}{7}713​

因此我们最终会选择 Source - C - E - H - Destination 这条路径。

Maximum minimum energy capacity

和 Maximum average energy capacity 类似，但我们计算的是每条路径每个节点（注意这里不是求和求最小值）底部数字的最小值，且选一个最小值最大的路径。这个指标倾向于具有较大能量储备的路线，以保护低容量节点过早失效。

Source - C - E - H - Destination: 1

Source - C - E - G - Destination: 1

Source - B - G - Destination: 2

Source - A - D - G - Destination: 1

Source - A - D - F - J - I - D - G - Destination: 1

因此我们最终会选择 Source - B - G - Destination 这条路径

Routing Protocols

我们可以大致将 WSN 中的路由协议分为以下 4 类：

Data-Centric Routing

我们前面提到过，WSN 需要设计一种不需要全局唯一标识的协议来进行路由。以数据为中心的路由就满足这样的条件。我们对比一下 Data-Centric 和 Address-Centric 路由：

大体上，Data-Centric 根据数据内容来进行路由，我们关心的是一些事件属性或内容属性，而不是某个节点上的感知值，像下面这个例子。

现在 sink 想要知道温度高于 70 ∘^{\circ}∘F 的区域，因此，只有满足这个属性的节点才会响应。最后根据这些响应的节点来生成路由。

以数据为中心的路由协议包括：泛洪（flooding）、闲聊（gossiping）、SPIN（Sensor

Protocols for Information via Negotiation）以及定向扩展（Directed Diffusion）路由协议。

Flooding

泛洪可以说是最为简单的路由协议。一个节点会将它接收到的包广播给它的所有邻居节点，这个过程会一直持续，直到网络中的所有节点都接收到了包，或者达到了限定的最大跳数。下图是一个泛洪的示意图：

泛洪的优点有：

简易性，不需要知道邻居节点的信息；简单自然也就便宜，不需要拓扑结构维护以及复杂的路由算法如果源和目的地之间存在可达路径，那么泛化可以保证到达（假设无错发生）

泛洪的问题：

implosion：泛洪机制没有限制多个节点不断向目的地广播相同的数据包这一行为，可能会导致一个节点收到多个重复的数据包，这会造成大量的资源浪费overlap：节点向周围广播的范围取决于它们的探测范围（sensing regions）。如果两个节点的探测范围有重叠，那么就会造成重叠区域的节点收到同一个数据包，也会造成资源的大量浪费。Resource Blindness：泛洪机制不会考虑节点的可用能量，也就是说，它不会考虑我们上面所说的 Maximum time to network partition 或者 Maximum minimum energy capacity 的指标，某个节点即使快要回到复活点了，还是会被压榨。

Gossiping

当一个节点收到一个数据包时，它不会像泛洪那样广播数据包，而是在其邻居节点中随机选择一个节点，并将数据包转发给该特定节点。因此，闲聊路由可以避免泛洪中的 implosion 问题，但它也相应增加了将信息传播到 sink 的延迟。

尽管泛洪和闲聊看起来很简单，但它们在某些场合下还是有用武之地的。例如，在网络的部署阶段，sink 可以使用泛洪或者闲聊来看看哪一个节点是活跃的。

SPIN

SPIN 指的是一系列路由协议，旨在通过协商（negotiation）和资源自适应（Resource adaptation）来解决泛洪的不足之处。

negotiation：节点不会将数据包广播给所有节点，而是会先与节点通过一个描述数据的包来进行协商，如果某个节点对此数据感兴趣，才会将数据包传给这个节点。Resource adaptation：每个节点都时刻关注着自己的能量资源，并根据能量资源的多少来相应的做出决策。

SPIN 的协商过程主要是通过三种消息格式来实现的：ADV（Advertisement）、REQ（Request）以及DATA。具体过程如下：

在发送DATA之前，节点会先广播一个ADV包，其中含有对DATA的描述，比DATA也小很多；如果某个邻居节点通过ADV中的描述对DATA感兴趣之后，会回复一个REQ包；DATA包随后被发往发送REQ的节点

上述过程被称为点到点的 SPIN（SPIN-PP），它虽然通过协商机制解决了泛洪的 implosion 和 overlap 问题，但它还有以下几个问题：

协商有了，但还没有资源适应，因此还是没能解决泛洪和闲聊的 resource blindness 问题如果有多个节点传回了REQ包，那么DATA包只能分批单独发给它们（unicast），这浪费了一定的资源当有多个REQ包时，SPIN-PP 没有提供相应的机制来避免冲突

SPIN 也有另外几个变种来解决 SPIN-PP 的上述问题：

SPIN with energy consumption awareness (SPIN EC)：每当一个节点的剩余能量低于某个阈值时，该节点就不参与协议的进程了。因此，如果节点有充盈的能量，SPIN EC 和 SPIN-PP 表现是完全一样的。SPIN for broadcast networks (SPIN BC)：在传输REQ包之前节点有一个随机退避机制。如果一个节点对某一数据包感兴趣，但已经监听到与该特定数据包相关的REQ包，它就不会再传输自己的REQ了，而是直接等DATA数据包进到碗里来。如果发送器节点收到了REQ包，那么它会将DATA包广播出去，对其感兴趣的节点自然会接收。SPIN BC 减少了由多个感兴趣的邻居节点而引起的能量消耗和开销。也减小了冲突的可能性。SPIN with reliability (SPIN RL)：在 SPIN BC 基础上进一步增添了可靠性机制。如果一个节点收到了ADV包，但没有收到紧随其后的DATA数据包（由于无线信道错误等原因），它就会向已经收到DATA数据包的邻居节点来“索要”这个数据包。SPIN RL 限制了节点的重传时间，使其在指定时间内不会重传数据包。

由于在传数据包之前的“握手”环节，SPIN 可能会比泛洪的延迟高一些，但能耗大为减少。

Directed Diffusion

在 SPIN 里，网络的流量始于传感器终于网关。但如果网关想要从传感器获取信息，SPIN 可能就不太合适了。因此有了定向扩展协议，主要有以下 4 个阶段：

Interest propagation

sink 首先会发送一个 interest 消息，这个消息被泛洪到网络的每一个节点，来为特定任务寻找具有相匹配数据的节点。

而收到 interest 消息的节点则会将之存储到一个叫作interest cache的地方，这个 interest cache 包含三个字段：

Timestamp：interest 消息到达的时间Gradient：表明 interest 消息是哪个节点发过来的，用于形成回到 sink 的反向路径Duration：表明 interest 消息在缓存中存储的时间

Gradient setup

当 interest 消息在网络中传播时，根据我们上面提到的Gradient字段，从源到 sink 的 gradients 也建立起来了。但因为是泛洪机制，一个节点可能收到多个 interest 消息，所以我们可以设计一些机制来指导 gradients 的选择（也就是下面的强化阶段）。例如，我们可以选择将Gradient定为第一个给该节点传递 interest 消息的节点，也可以选择这当中具有最高剩余能量的节点。

当某个节点发现自己的数据和 interest 消息匹配时，此时它就会作为源来沿着建立好的 gradients 将它的数据发回给 sink。

Reinforcement

因为上一阶段并没有限制一个节点可能拥有的Gradient数量，数据可以通过多条路径发回到 sink。sink 可以通过某个路径中的指定节点（specified node(s)）重新发送 interest 消息来“加强”该特定路径。这个路径可以根据一些规则来选择，如最佳的链路质量，收到的数据包数量，或最低的延迟。一旦选择了一个指定的节点，就只向该节点发送 interest 消息，以加强与该节点相关的路径。

我们也可以反向强化（Negative reinforcement），即“弱化”现有的路径，从而构建一条新的路径，如下图所示：

Data delivery

总之，一个源和 sink 之间的路径已经建立好了，源可以沿着路径开始传播数据了。定向扩散的基本操作会导致单路径传递。然而，在强化阶段，sink 可以选择多个路径，就好像在使用多路径传播一样。

全过程如下图所示：

以数据为中心的路由协议都是平面式路由算法，我们之后还会介绍到分层式路由算法。这里先对这两种路由方法做个大致的对比：

Hierarchical Protocols

在分层协议中，节点被分成一群 clusters，不同 cluster 的节点成员通过各自的cluster head进行交互。cluster head 会聚合所有节点的数据，节约能量。在将信息传到 sink 之前，cluster head 之间也可以形成另一层 cluster。

我们下面会介绍 4 种分层式协议。

Low energy adaptive clustering hierarchy (LEACH)

LEACH 会动态的选择不同的节点作为 cluster head 并据此形成网络的 clusters，作为cluster head 的节点是非常耗能的，因此动态的改变 cluster head 可以将能耗平均到网络的每个节点上。cluster 内部的通信信息最后都会被聚合到 cluster head， cluster head 然后再直接与 sink 进行通信。

LEACH 协议的运转是通过rounds来控制的。每个 round 又分为两个阶段：

Setup phase

Advertisement

节点会广播一个 cluster head 消息，收到消息的节点首先会在 0 到 1 之间选择一个随机数，如果这个数小于某个阈值 T(n)T(n)T(n)，那么这个节点就成为 cluster head。阈值按如下公式计算：

T(n)={P1−P[rmod1/P]ifn∈G0otherwiseT(n)=\left\{ \begin{aligned} &\frac{P}{1-P[r \ {\rm mod}\ 1/P]}\quad &{\rm if}\ n\in G \\ &0 \quad &{\rm otherwise} \end{aligned} \right. T(n)=⎩⎪⎨⎪⎧​​1−P[rmod1/P]P​0​ifn∈Gotherwise​

其中，PPP 为 cluster head 的占比，rrr 是现在的轮次（round），GGG 代表在前 1/P1/P1/P 轮次还没有成为过 cluster head 的节点集合。

某个节点成为 cluster head 之后，它会向邻居节点广而告之，其它节点也就知道自己属于哪个 cluster 了。但如果某个节点收到了来自多个 cluster head 的外交企图，那么它会选择外交企图最强烈的那个 cluster head（信号强度最高，说明信道质量高）。同时 LEACH 也会使用基于 CSMA 的方法来减少冲突。

cluster setup

在这之后，节点也会向 cluster head 报告一声儿，你选择了我，我选择了你，这是我们的选择~~~

Schedule creation

cluster head 会根据 TDMA 机制来为每个节点分配传输数据的时间段。

Steady state phase：cluster 成员与 cluster head 进行通信

传感器节点可以开始向 cluster head 传输数据，cluster head 将数据聚合之后再传向 sink。只有 cluster head 全程保持活跃状态，而 cluster member 只会在给它分配的时间段内保持活跃。因此这些节点的能耗会显著减少。在 Steady state phase 结束之后，网络进入下一轮次，重新开始 Setup phase。

Power efficient gathering in sensor information systems (PEGASIS)

PEGASIS 目的是对 LEACH 进行改进。为了减少 LEACH 中形成 clusters 时的负载能耗，PEGASIS 使用链式的节点来构造 cluster 而不是 LEACH 中的一簇节点，如下图所示：

链的构建是根据贪心算法进行的，其中节点选择其最近的邻居节点作为链中的下一跳。这就需要节点拥有网络的全局知识，链的构建从离 sink 最远的节点开始。

PEGASIS 不像 LEACH 那样构建 cluster member 到 cluster head 之间的从属关系，每个节点只知道链中它的上一跳以及下一跳节点是谁。因此链式的通信是序列化的，每个节点都向它链中的邻居节点传输数据，每个节点都在聚合前面节点的数据，直到最后所有数据都聚合到 chain leader。chain leader 通过在链节点中传递token来控制节点通信的顺序。例如上图中，chain leader 节点 2 首先可能会把 token 传给节点 0，让它开始传输数据，节点 0 和节点 1 的数据聚合到节点 2 之后，节点 2 再把 token 传给节点 6.

这种链式通信比 LEACH 中的 cluster 形成过程耗能少得多，但却有更大的时延，因为数据是逐步聚合到 chain leader 的。而且在聚合过程中，所有的信息都几乎被聚合在一个数据包中，一旦这个数据包出错，最后向 sink 传输的信息也可能会出错。

Threshold sensitive energy efficient sensor network (TEEN)

LEACH 和 PEGASIS 协议支持来自传感器节点的信息周期性地传输到 sink 的应用。因此，来自多个节点的信息内容可能会因为聚合技术的使用而减少，所以这两个协议可能不太适合基于事件（event-based）的应用。TEEN 协议就是为了基于事件的应用而设计的。多跳路由是根据与数据有关的阈值生成的，该阈值由应用程序设置。

如图所示，TEEN 协议将传感器节点组织成多个层次的结构分布：

数据先由节点传给 cluster head，cluster head 聚合数据之后，再由 cluster head 传给更高层级的 cluster head，直到数据到达 sink。cluster head 会在一个 cluster 内部周期性的改变。

TEEN 有两个阈值，硬阈值（hard threshold）HTH_THT​ 和软阈值（soft threshold）STS_TST​。传感器节点被设计为只对特定的事件属性发生响应，例如温度。它会比较检测到的值和 HTH_THT​，如果监测值超过了硬阈值，传感器节点就会向 cluster head 发送数据。也就是说，只有感兴趣的数据才会被聚合。但是事件的发生会持续一段时间，这可能会造成数据的重复传输，为了减少信息冗余，我们需要使用软阈值STS_TST​。

如果接下来的观测值和一开始的观测值的差值没有超过 STS_TST​，那么节点就不再继续传输数据了。总体来说，硬阈值将传输限制在 sink 感兴趣的范围，而软阈值则进一步限制观测值没有变化或变化很小时传输的信息。

Adaptive threshold sensitive energy efficient sensor network (APTEEN)

APTEEN 既可以提供像 LEACH 和 PEGASIS 那样周期性的信息传输，也支持 TEEN 的基于事件传输。APTEEN 在每个集群上都采用了基于 TDMA 的机制。硬阈值和软阈值用来控制节点传输数据的时间以及频率。

总结，Hierarchical routing 的优点：

集群通信，只有 cluster head 可以与网络通信 → 提供更高的可扩展性动态的集群创建 →比 flat 的拓扑结构的能量效率要高在基于事件的 WSN 中，节点可在大部分时间处于休眠状态，大大减少了能耗网络的智能部分大都汇聚在了少数 cluster heads 上，剩下的节点只需执行相对简单的任务 →延长了网络的整体可用时间

缺点：

非常依赖于 cluster heads，cluster heads 失效了怎么办？集群的形成以及动态改变开销很大要在能量效率以及集群的创建之间找到平衡对于许多分层式协议来说，集群间通信仍然是一个很大的挑战，cluster heads 一般都假设直接与 sink 进行通信，这需要很高的传输能量

Geographical Routing

在某些应用中，将传感器的观测值与传感器节点的位置联系起来是很重要的。GPS 可以集成到节点的嵌入式板上，但GPS 主要用于含有大量能量的固定节点，对于有限能量的节点，使用 GPS 可能难以承受。事实上，一些协议可以给我们提供准确的位置信息而不借助于 GPS 设备，这里不做详细介绍。

既然位置信息很重要，一个很自然的想法是利用它来进行路由。基于位置的协议或地理路由协议（Geographical Routing）利用每个节点的位置信息来提供高效和可扩展的路由。由于目的地位置在 WSN 中通常是固定的，目的地的位置可以用来制定局部路由规则，使数据更接近于该位置。地理路由协议提供了几种技术来路由该数据以提高能源效率或降低延时。

MECN (Minimum Energy Communication Network)

先上图：

我们原先有一个网络 G′G 'G′，MECN 做的就是从 G′G 'G′ 中形成了一个子网络 GGG，这个子网络和原网络相比有相同的节点数，但边数明显变少了，也就是说节点之间的路径变少了，这样做的目的是为了让任意两个节点之间的通信消耗最少的能量。这是因为节点之间通信消耗的能量与距离的 nnn 次方（n≥2n\ge2n≥2）成比例关系，通过几个短距离的中间节点过渡一下，可能比直接一跳传给目的节点消耗的能量少得多。从上图来说，A 通过 C 传给 E、D、或者 B 比 A 直接传给它们可以消耗更少的能量。

具体来说，任意两个相邻节点 A 和 B 传输数据的能量消耗可以建模为

p(A,B)=td(A,B)np(A,B)=td(A,B)^n p(A,B)=td(A,B)n

其中 ttt 是常数，ddd 是两个节点之间的距离。

进一步，节点 A（A0A_0A0​）和节点 B （AkA_kAk​） 之间的路径我们用 r=(A0,A1,…,Ak)r=(A_0, A_1,\dots,A_k)r=(A0​,A1​,…,Ak​) 来表示，那么传输过程中消耗的总能量为

C(r)=∑i=0k−1(p(Ai,Ai+1)+c)C(r)=\sum_{i=0}^{k-1}(p(A_i, A_{i+1})+c) C(r)=i=0∑k−1​(p(Ai​,Ai+1​)+c)

其中 ccc 为接收数据需要的能量。因此，节点 A0A_0A0​ 和节点 AkA_kAk​ 之间的最小能量路径 r′r'r′ 就满足

C(r)≥C(r′)C(r)\ge C(r') C(r)≥C(r′)

子网络 GGG 中的路径就是我们从 G′G'G′ 中找到的最小能量路径 r′r'r′。

在 MECN 的基础上还发展出了 small MECN（SMECN），它进一步考虑了节点之间存在的障碍物，使子网络的边数更少。

Geographical Forwarding

因为无线信道容易出错，且某个节点的突然失效，MECN 形成的网络图可能会动态改变，这就需要节点之间来频繁的交换信息以重构网络图。

因此我们不使用这种构建网络图的方式，而是定义一个局部化的规则，节点直接根据这个规则来对数据进行路由。

考虑如下场景，节点 A 想要通过它的邻居节点来给 sink 发送数据，在基于地理位置的路由算法中，节点 A 的周边区域都可以分为两种：

Infeasible region：其中的节点离 sink 的距离比 A 离 sink 的距离远Feasible region：其中的节点离 sink 的距离比 A 离 sink 的距离近

接下来需要做的就是在 Feasible region 中选择一个节点，选择方法就有很多了。

Greedy forwarding

Most forward within radius (MFR) metric：每次都选择在当前节点和 sink 的连线上具有最大分量的节点，如下图中的 MThe nearest forward progress metric：每次都选择与当前节点最近的节点，如下图中的 NGreedy routing scheme (GRS)：每次都选择最靠近 sink 的节点，如下图中的 GCompass metric：每次都选择最靠近当前节点和 sink 的连线的节点，如下图中的 C

这几种选择方法各有优劣。但需要注意的是，虽然每次选择最靠近 sink 的节点意味着更少的跳数，但随着节点之间距离的提升，信道质量也会衰减，因此可能会导致很多重传。

Distance based blacklisting

为了避免我们刚刚说到的这个问题，我们可以将离节点比较远的节点拉入“黑名单”。例如，如果某个节点的传输范围为 100 m，我们将 20% 的节点拉入黑名单，即相当于这个节点的传输范围缩减为 80 m。

Reception based blacklisting

信道的质量也不仅仅是和距离直接相关，因此仅仅根据距离来拉黑可能并不能完全避免出现信道质量差的情况。基于接收的黑名单协议将那些数据包接收率低于某个阈值的邻居节点列入黑名单。每个节点都会追踪每个邻居节点的数据包接收率（packet reception rate，PRR），然后与这些邻居交换此信息。当某个节点有数据要发送时，它在 feasible region 里选择一个 PRR 高于阈值的节点作为下一跳。

上述过程称为Absolute reception based blacklisting，如果没有节点的 PRR 高于阈值，可能会造成网络暂时失去连接。

所以通常我们更喜欢使用Relative reception based blacklisting，它会对邻居节点的 PRR 做个排名，PRR 值较低的会被拉黑。

Absolute reception based blacklisting 的一个特例是Best reception based blacklisting，即每次都选择 PRR 最高的邻居。

Best PRR × distance

基于接收的黑名单协议会造成更多延时，因为它倾向于选择离节点距离较近的邻居，跳数也就变多了。所以我们干脆来碗二合一，同时考虑距离和 PRR。

例如我们要选节点 B 当作下一跳，那么就要使节点 B 的 PRR 和以下物理量的乘积最大化：

1−d(B,S)d(A,S)1-\frac{d(B,S)}{d(A,S)} 1−d(A,S)d(B,S)​

节点 B 与 sink 的距离越近，以上物理量就越大，乘积结果也就越大。

基于位置的路由协议实质上是在用网络的部分信息（邻居节点）来做出路由决策，但仅仅是收集邻居信息也已经非常昂贵了。虽然知道全局信息能找到最佳路由路径，但在实际的 WSN 中几乎是不可能实现的。因此我们说，路由决策的准确性和掌握网络全局拓扑结构的多少有直接关系。

PRADA

如果节点想知道更多拓扑结构，那么就必须消耗更多传输能量来提升它的传输范围。但更多的拓扑知识意味着更优的路径能够被找到，那么数据的传送就会消耗更少的能量。PRADA（Probe-based distributed protocol for knowledge range adjustment）就在探索这二者之间的 trade-off。

PRADA 是基于一个集中式的转发机制，partial topology knowledge forwarding(PTKF)。PTKF 是为了最小化数据通信的能耗以及拓扑信息的成本。每个节点都会根据加权最短路径算法构建一条路线。

QoS-Based Routing

尽管 WSN 中能耗很重要，之前的很多协议也主要是在考虑能耗因素，但能耗并不是唯一一个值得着重看重的因素。例如在多媒体通信中，吞吐量、时延等也是非常重要的指标。除了 WSN的能源效率外，这些应用的服务质量也需要得到保证。

SAR: Sequential Assignment Routing

SAR 协议提供了一种表驱动的多路径方法，它考虑了 WSN 的 QoS 要求。SAR 的主要目标是创建多个树，这些树从根节点出发，根节点是 sink 的单跳邻居节点之一。每棵树从 sink 向外延伸，同时避开低 QoS（即低吞吐量/高延迟）和低能量储备的节点。

Minimum Cost Path Forwarding

综合考虑吞吐量、时延以及能耗因素，通过一个损失函数（cost function）来给每个节点确定一个 cost 字段，cost 表示每个节点与 sink 之间的最小 cost，我们根据 cost 的大小来选择下一跳的节点。

总共分为两个阶段：

cost field establishmentcost path forwarding

Cost field establishment phase

sink 首先会发送一个ADV广播包，并且初始 cost 为 0.

节点 jjj，从节点 iii 收到ADV广播包，那么它的 cost 如下计算：

Lj=Li+Cj,iL_j=L_i+C_{j,i} Lj​=Li​+Cj,i​

其中 LiL_iLi​ 是节点 iii 的 cost，Cj,iC_{j,i}Cj,i​ 是节点 jjj 和节点 iii 之间的链路 cost。之后节点会设置一个退避时钟，且倒计时时间为 γCj,i\gamma C_{j,i}γCj,i​，γ\gammaγ 为常数，倒计时结束之后，这个节点再将ADV广播出去。我们看一个具体例子：

我们假设节点 A 与 sink 的最小 cost 为 0.5，节点 A 会向 B 和 C 广播ADV包，B 和 C 收到

ADV包后，会根据上面给出的公式更新自己与 sink 的最小 cost：

B：0.5 + 1。5 = 2C：0.5 + 4 = 4.5

随后节点 B 随机退避 γLB,A\gamma L_{B,A}γLB,A​，节点 C 随机退避 γLC,A\gamma L_{C,A}γLC,A​，因为 LB,A<LC,AL_{B,A}<L_{C,A}LB,A​<LC,A​，节点 B 首先退避结束，它会开始广播ADV包，节点 C 收到后，发现自己通过节点 B 与 sink 通信比通过节点 A 与 sink 通信 cost 小，就更新自己的 cost（2+1=3）。随机退避 γLC,B\gamma L_{C,B}γLC,B​ 之后，节点 C 广播ADV包 …

Cost path forwarding phase

源节点将数据信息广播给其邻近节点，这个消息包含了源节点的 cost 字段。还是上面的例子，假设节点 C 要给 sink 发送数据包，它会将数据包连同自己的 cost（3）广播出去，当节点 A 收到这个消息后，它发现自己的 cost 加上 A、C 的链路 cost 比 3 大，A 就不会继续转发这个数据包了。

SPEED

传统网络中的 QoS 需求通常与端到端的延迟和吞吐量有关。而数据包的端到端延迟与源和目的地之间的距离成正比。所以距离也是另一个保证 QoS 的因素。SPEED 协议在一定程度上实现了端到端的传输速率保证。

一个叫作 neighbour beacon exchange 的协议周期性的运转来交换节点之间的位置信息，每个节点构建一个邻居表，并通过以下字段存储其邻居的信息：NeighborID，Position，SendToDelay和ExpireTime。

SendToDelay表示到这个邻居节点的时延，如果在ExpireTime内这条邻居信息没有更新的话，就把它从邻居表中删去。

SPEED 协议首先交换节点的传输延迟，以得到网络负载情况，然后用 SNGF （stateless nondeterministic geographic forwarding）算法来选择满足传输速率的下一跳节点。

References

[1] Chapter 7,Wireless Sensor Networksby Ian F Akyildizand Mehmet C Vuran.

[2] Chapter 7,Fundamentals of Wireless Sensor Networks: Theory and Practiceby W. Dragieand C. Poellabauer.