沈阳理工大学学士学位论文
3.WSN路由协议算法分析
3.1 WSN路由协议的分类方法
WSNs路由协议负责在sink点和其余节点间可靠地传输数据。由于WSNs与应用高度相关，单一的路由协议不能满足各种应用需求，因而人们研究了众多的路由协议。为揭示协议特点，我们根据一些路由协议采用的通信模式、路由结构、路由建立时机、状态维护、节点标识和投递方式等策略，运用多种分类方法对其进行了分类。由于研究人员组合多种策略来实现路由机制，故同一路由协议可分属不同类别。
（1）根据传输过程中采用路径的多少，可分为单路径路由协议和多路径路由协议。单路径路由节约存储空间,数据通信量少；多路径路由容错性强,健壮性好,且可从众多路由中选择一条最优路由。
（2）根据节点在路由过程中是否有层次结构、作用是否有差异，可分为平面路由协议和层次路由协议。平面路由简单,健壮性好,但建立、维护路由的开销大，数据传输跳数多，适合小规模网络；层次路由扩展性好，适合大规模网络，但簇的维护开销大，且簇头是路由的关键节点，其失效将导致路由失败。
（3）根据路由建立时机与数据发送的关系，可分为主动路由协议、按需路由协议和混合路由协议。主动路由建立、维护路由的开销大，资源要求高；按需路由在传输前需计算路由，时延大；混合路由则综合利用这两种方式。
（4）根据是否以地理位置来标识目的地、路由计算中是否利用地理位置信息，可分为基于位置的路由协议和非基于位置的路由协议。有大量WSNs应用需要知道突发事件的地理位置，这是基于位置的路由协议的应用基础，但需要GPS定位系统或者其他定位方法协助节点计算位置信息。
（5）根据是否以数据来标识目的地，可分为基于数据的路由协议和非基于数据的路由协议。有大量WSNs应用要求查询或上报具有某种类型的数据，这是基于数据的路由协议的应用基础，但需要分类机制对数据类型进行命名。
（6）根据节点是否编址、是否以地址标识目的地，可分为基于地址的路由协议和非基于地址的路由协议。基于地址的路由在传统路由协议中较常见，,而在WSNs中一般不单独使用而与其他策略结合使用。
17
沈阳理工大学学士学位论文
（7）根据路由选择是否考虑QoS约束，可分为保证QoS的路由协议和不保证QoS的路由协议。保证QoS的路由协议是指在路由建立时，考虑时延、丢包率等QoS参数，从众多可行路由中选择一条最适合QoS应用要求的路由。
（8）根据数据在传输过程中是否进行聚合处理，可分为数据聚合的路由协议和非数据聚合的路由协议。数据聚合能减少通信量，但需要时间同步技术的支持，并使传输时延增加。
（9）根据路由是否由源节点指定，可分为源站路由协议和非源站路由协议。源站路由协议节点无须建立、维护路由信息，从而节约存储空间，减少通信开销。但如果网络规模较大，数据包头的路由信息开销也大，而且如果网络拓扑变化频繁，将导致路由失败。 （10）根据路由建立时机是否与查询有关，可分为查询驱动的路由协议和非查询驱动的路由协议。查询驱动的路由协议能够节约节点存储空间，但数据时延较大，且不适合环境监测等需紧急上报的应用。
3.2 几种典型路由协议的分析
3.2.1 平面路由协议
平面路由协议主要特点有：所需的信息域较小，一般仅需一跳（1 hop）内的信 息；无需进行周期性的路由信息维护；复杂度较低。 (1) Flooding
泛洪是一种传统的路由技术，不要求维护网络的拓扑结构，并进行路由计算，接收到消息的节点以广播形式转发分组。对于自组织的传感器网络，泛洪路由是一种较直接的实现方法，但消息的“内爆”(implosion)和“重叠”(overlap)是其固有的缺陷。为了克服这些缺陷，S.hedetniemi等人提出了Gossiping策略，节点随机选取一个相邻节点转发它接收到的分组，而不是采用广播形式。这种方法避免了消息的“内爆”现象，但有可能增加端到端的传输延时。
18
沈阳理工大学学士学位论文
图3.1 Flooding路由协议中的内爆和重叠问题
(2) SPIN (sensor protocol for information via negotiation)
SPIN是以数据为中心的自适应路由协议，通过协商机制来解决泛洪算法中的“内爆”和“重叠”问题。传感器节点仅广播采集数据的描述信息，当有相应的请求时，才有目的地发送数据信息。SPIN协议中有3种类型的消息，即ADV，REQ和DATA。
ADV—用于新数据广播。当一个节点有数据可共享时，它以广播方式向外发送DATA数据包中的元数据。
REQ—用于请求发送数据。当一个节点希望接收DATA数据包时，发送REQ数据包。 DATA—包含附上元数据头(meta一header)的实际数据包。 SPIN协议有4种不同的形式:
? SPIN-PP：采用点到点的通信模式，并假定两节点间的通信不受其他节点的干扰，分组不会丢失，功率没有任何限制。要发送数据的节点通过ADV向它的相邻节点广播消息，感兴趣的节点通过REQ发送请求，数据源向请求者发送数据。接收到数据的节点再向它的相邻节点广播ADV消息，如此重复，使所有节点都有机会接收到任何数据。 ? SPIN-EC：在SPIN-PP的基础上考虑了节点的功耗，只有能够顺利完成所有任务且能量不低于设定阈值的节点才可参与数据交换。
? SPIN-BC：设计了广播信道，使所有在有效半径内的节点可以同时完成数据交换。为了防止产生重复的REQ请求，节点在听到ADV消息以后，设定一个随机定时器来控制REQ请求的发送，其他节点听到该请求，主动放弃请求权利。
? SPIN-RL：它是对SPIN-BC的完善，主要考虑如何恢复无线链路引入的分组差错与丢失。记录ADV消息的相关状态，如果在确定时间间隔内接收不到请求数据，则发送重传请求，重传请求的次数有一定的限制。图3.2表明了SPIN协议的路由建立与数据传送。
19
沈阳理工大学学士学位论文
图3.2 SPIN协议的路由建立与数据传送
基于数据描述的协商机制和能量自适应机制的SP创协议能够很好地解决传统的Flooding协议所带来的信息爆炸、信息重复和资源浪费等问题。此外，由于协议中每个节点只需知道其单跳邻居节点的信息，拓扑改变呈现本地化特征。SP州协议的缺点是数据广告机制不能保证数据的可靠传递，如果对数据感兴趣的节点远离源节点或者在源节点和目的节点中间的节点对数据不感兴趣，那么数据就不可能被传递到目的地。因此，对于入侵发现等需要在定期间隔内可靠传递数据的应用系统来说，SP州并不是一个很 好的选择。
(3) SAR (sequential assignment routing)
在选择路径时，有序分配路由(SAR)策略充分考虑了功耗、QoS和分组优先权等特殊要求，采用局部路径恢复和多路经备份策略，避免节点或链路失败时进行路由重计算需要的过量计算开销。为了在每个节点与sink节点间生成多条路经，需要维护多个树结构，每个树以落在sink节点有效传输半径内的节点为根向外生长，枝干的选择需满足一定QOS要求并要有一定的能量储备。这一处理使大多数传感器节点可能同时属于多个树，可任选其一将采集数据回传到sink节点。 (4) 定向扩散(directed diffusion)
DD是以数据为中心的路由协议发展过程的里程碑，其突出特点是引入了梯度来描述网络中间节点对该方向继续搜索获得匹配数据的可能性。这是一个重要的基于数据的、查询驱动的路由协议。该协议用属性/值对命名数据。为建立路由，sink点flooding包含属性列表、上报间隔、持续时间、地理区域等信息的查询请求Interest (该过程本质上是设置一个监测任务)。沿途节点按需对各Interest进行缓存与合并，并根据Interest计算、创建包含数据上报率、下一跳等信息的梯度(gradient),从而建立多条指向sink点的路径。Interest中的地理区域内节点则按要求启动监测任务，并周期性地上报数据，途中各节点可对数据进行缓存与聚合。sink点可在数据传输过程中通过对某条路径发送上
20
沈阳理工大学学士学位论文
报间隔更小或更大的Interest，以增强或减弱数据上报率。该协议采用多路径，健壮性好；使用数据聚合能减少数据通信量；sink点根据实际情况采取增强或减弱方式能有效利用能量；使用查询驱动机制按需建立路由，避免了保存全网信息，但不适合环境监测等应用。而且，Gradient的建立开销很大，不适合多sink点网络；数据聚合过程采用时间同步技术，会带来较大开销和时延。图3.3描述了定向扩散模型的工作原理。
图3.3 定向扩散模型的工作原理
DD路由是一种经典的以数据为中心的路由机制。Sink节点根据不同的应用需求定义不同的任务类型、目标区域等参数的兴趣消息，通过向网络中广播兴趣消息启动路由建立过程。中间传感器节点通过兴趣表建立从数据源到Sink节点的数据传输梯度，自动形成数据传输的多条路径。DD采用相邻节点间通信的方式来避免维护全局拓扑，采用查询驱动数据传送模式和局部数据聚集而减少网络数据流，因此是一种高能源有效性的协议。它的缺点是，在需要连续数据传送的应用中(环境监测等)不能很好的应用；数据命名只能针对于特定的应用预先进行；初始查询的扩散开销大。
(5) 基于最小代价场的路由算法：算法开始之前，所有的节点都将自己的代价设为无穷大。网关广播一个代价为0的广告报文，其他节点接收到广告报文后，如果报文中所表示的代价小于节点自己的代价，则使用这个新的代价作为自己的代价，并将新的代价广播出去；反之，则丢弃该信息。最终每个节点都获得了自己距离网关的最小代价，由此建立代价场，报文沿着最小代价路径向网关发送。当报文被发送的时候它将附带源节点的最小代价，及从源节点到当前节点所消耗的代价，一个邻居节点接收到报文，只有该报文已消耗的代价和自己的代价之和等于源节点代价的时候，才转发这个报文。采用这种方法，节点不需要维持任何的路径信息，就可以实现报文的最短路径发送。
21