1.3.4 路由协议

网络通信协议中的路由协议负责将数据分组从源节点通过网络转发到目标节点，主要包括两个方面的功能：其一是寻找源节点和目标节点间的优化路径；其二是将数据分组沿着优化路径正确转发[25-27]。

Ad hoc、无线局域网等传统无线网络的首要目标是，提供高服务质量和公平高效地利用网络带宽，同时提高整个网络的利用率，避免产生通信拥塞，并均衡网络流量等，而能量消耗问题不是这类网络的重点[28-32]。在无线传感器网络中，节点的能量一般有限，而且一般没有能量补充机制，因此路由协议需要高效利用能量。传感器网络具有能量优先、基于局部拓扑信息、以数据为中心、应用相关等特点[33，34]。

针对不同的传感器应用，研究人员提出了不同的路由协议。本书以各种路由协议的特点和发展历程为依据，将路由协议分成以下几种。

1.传统平面拓扑路由协议

基于平面网络的路由是最简单的路由形式，其中每一个点都具有对等的功能。最有代表性的算法是泛洪算法。

泛洪（Flooding）算法的主要思想是：由槽节点发起数据广播，然后任意一个收到广播的节点都无条件将该数据副本广播出去，每一个节点都重复这样的过程直到数据遍历全网或达到规定的最大跳数。泛洪算法不用维护网络拓扑结构和路由计算，实现简单，但是也会带来一些问题，最主要的是内爆、重叠及资源盲点等，如图1-3和图1-4所示。Gossiping算法[35]是泛洪算法的改进，与泛洪算法不同，每一个节点并不是向所有的邻居节点发送数据包的副本，而是随机选择一个或几个邻居节点来转发数据包。由于一般无线传感器网络的链路冗余度较大，适当选择转发的邻居节点数量，可以保证几乎所有节点都能接收到数据包。

图1-3 泛洪算法的消息内爆问题

图1-4 泛洪算法的消息重叠问题

2.新型层次拓扑路由协议

这是与平面路由相对的概念，主要特点是出现了分簇结构。相对于平面结构中每一个点都是对等的，具有分簇结构的层次拓扑路由将节点分成若干个集合（簇），每一个簇都有一个节点充当簇头节点，簇头节点负责管理簇内事务及与其他簇进行数据交换。簇内其他节点仅与簇头节点进行数据交换，而与其他簇成员不发生联系。这样，簇内成员组成一个低层次的节点集合，通过相应算法进行数据交换；所有簇头节点组成一个高层次的节点集合，各个簇头节点之间再通过相应算法进行数据交换。其最有代表性的算法是LEACH算法[36]。

3.以数据为中心的路由协议

最有代表性的是SPIN算法和定向扩散（Directed Diffusion，DD）算法[37]。以数据为中心的路由协议与传统网络路由协议最大的区别表现在：

（1）以数据为中心，网络中的任务是在对数据进行命名的基础上进行的。

（2）以DD算法为例，数据是在相邻的节点之间进行扩散的，DD算法中每一个节点都是一个端，都可能是数据的目标节点，都能进行数据处理。DD算法中没有固定的路由路径。

（3）以DD算法为例，节点遵循本地交换的原则，节点只需要与邻居节点进行数据交换，而不需要对整个网络的拓扑了解。

定向扩散算法是以数据为中心的路由协议发展过程中的里程碑。Estrin等提出了定向扩散模型来进行数据分发，它与已有的路由算法的实现机制不同，节点用一组属性值来命名它所生成的数据。槽节点向所有传感器发送对任务描述的“兴趣”（Interest），即一个任务描述数据包，它是用属性值对来描述的。兴趣会通过全网逐渐扩散，最终找到匹配请求条件的数据源，与此同时，也建立起从数据源到槽节点的“梯度”。节点会在它的缓存中存储兴趣入口，兴趣入口包含时间戳和梯度场，数据源节点会沿梯度最大的方向将数据传回槽节点。图1-5展示了兴趣扩散、梯度建立及数据按照加强的梯度路径传送的三个步骤。

图1-5 DD算法示意图

4.基于连通支配集的路由协议

支配集的概念来自图论理论，其定义为：D包含于V（G），称为图G的一个支配集，若任何顶点u∈V（G），则要么u∈D，要么u与D内任意一个顶点相邻。在支配集概念的基础上又有连通支配集与最小连通支配集，连通支配集要求保证支配集中的节点满足连通的条件，最小连通支配集又要保证连通支配集节点数量最少，寻找最小连通支配集为NP完全问题[38]。基于连通支配集的算法将节点分成两类：支配节点和非支配节点。支配节点作为骨干节点负责日常事务处理，非支配节点在有数据要传输的时候将数据传给支配节点，不需要的时候可以进入休眠状态，节省能量。代表性算法有WULI[39]、SPAN[40]等。