无线传感器网络路由协议研究进展

余 恒,王刚亮

三峡大学计算机与信息学院,湖北宜昌 443002

无线传感器网络路由协议研究进展

余 恒,王刚亮

三峡大学计算机与信息学院,湖北宜昌 443002

在无线传感器网络体系结构中，网络层的路由技术至关重要。在介绍无线传感器网络的特点后，对现有的无线传感器网络路由协议进行了分类，然后着重分析了一些有代表性的路由协议的路由机制，并指出了这些协议的优缺点和应用范围。最后结合该领域当前研究现状，指出了路由协议未来的研究策略与发展趋势。

无线传感器网路；路由协议；路由分类；路由机制

0 引言

随着微电子技术，无线通讯与传感技术的发展，无线传感器网络[1]（Wireless Sensor Networks， WSNs）引起了人们广泛的关注。WSNs是由部署在监测区域内的大量廉价微型传感器节点组成，通过无线通讯方式形成的一个多跳的自组织的网络系统。WSNs不需要固定网络支持，在军事国防，生物医疗，环境监测及智能家居等领域具有广阔的应用前景[2]。

作为一种新型的无线自组网络，无线传感器网络与传统的移动自组织网络（mobile Ad Hoc networks，MANET）有着明显的差异，主要体现在：1）WSNs节点不移动或很少移动，而MANET节点移动性强；2）WSNs络旨在收集信息，而MANET则倾向于分布式计算和端到端通信；3）WSNs节点的能量、存储空间和计算能力有限；4）WSNs节点通讯高能耗，数据计算低能耗，节点会因能量耗尽而失效；5）WSNs节点数量更大，分布范围更广，节点没有统一编址，节点之间通过广播、多跳通信方式进行数据交换；6）WSNs节点产生的数据具有较大的冗余度；这些差异使得MANETs路由协议不适合直接运用到WSNs中，需要结合WSNs的特点对其进行改进，提出新的路由协议。本文对当前较为典型的路由协议进行了分类和总结，指出了路由协议将来发展的趋势，目的在于为路由协议的进一步研究作参考。

1 传感器网络路由协议分类研究

近几年，人们提出多种基于不同应用目标的路由协议，并根据不同的应用对路由进行了分类研究与比较[3，4]。无线传感器网络路由协议的研究最早从Flooding开始，逐渐得到关注。到目前为止，针对WSNs提出的具有代表性的路由协议有MDR、SAR、TBF、TEEN等。

为揭示协议特点，我们根据路由协议采用的路由结构、路由建立时机、数据传输模式等不同标准对其进行了分类。由于路由协议的研究人员组合多种策略来实现路由机制，故同一路由协议可分属不同类别。

1.1 平面路由协议和层次路由协议

根据传感器节点在路由过程中作用是否有差异、是否有层次结构，可以将路由协议分为平面路由协议和层次路由协议。

平面路由协议的优点是网络中没有特殊的节点，所有节点的地位是平等的，不存在等级和层次的差异。它们通过局部操作和信息反馈来生成路由，原则上不存在瓶颈问题。网络流量均匀地分散在网络中，路由算法易于实现，健壮性好。缺点是建立、维护路由的开销大，数据传输跳数多，可扩展性小，在一定程度上限制了网络的规模。

层次路由协议采用簇的概念对传感器节点进行层次划分。若干个相邻节点构成一个簇，每一个簇有一个簇首。簇内通信由簇头结点来完成。簇头结点进行数据聚集和融合以减少传输的信息量，最后簇头结点把融合的数据传送给汇聚结点。层次路由扩展性好，适合大规模网络，但簇的维护开销大，且簇头是路由的关键节点，其失效将导致路由失败。

1.2 主动路由协议和被动路由协议

根据路由建立时机与数据发送的关系，可分为主动路由协议和被动路由协议。

主动路由协议，又称表驱动的（table-driven）路由协议，它的路由发现策略与传统路由协议类似，节点通过周期性地广播路由信息分组，交换路由信息，主动发现路由。这一类的路由协议试图在所有的网络移动节点中维护一组到其他所有移动节点的一致的、实时的路由信息表。它的优点是当节点需要发送数据分组时，只要去往目的节点的路由存在，所需的延时很小。缺点是主动路由需要花费较大开销，尽可能使得路由更新能够紧随当前拓扑结构的变化，浪费了一些资源来建立和重建那些根本没有被使用的路由。而且，动态变化的拓扑结构可能使得这些路由更新变成过时信息，路由协议始终处于不收敛状态。

被动路由协议也称为按需（On Demand）路由协议。这种路由协议并不要求移动节点一直维护网络的路由信息表，只有在节点需要某条路由时才动态的创建它。被动路由协议根据网络分组的传输请求，被动地搜索从源节点到目的节点的路由。当没有分组传递请求时，路由器处于静默状态，并不需要交换路由信息。拓扑结构和路由表内容按需建立，它可能仅仅是整个拓扑结构信息的一部分。它的优点是不需要周期性的路由信息广播，节省了一定的网络资源。缺点是发送数据分组时，如果没有去往目的节点的路由，数据分组需要等待因路由发现引起的延时。

1.3 单路径路由协议和多路径路由协议

从路径的表现形式上角度考虑，可分为单路径路由协议和多路径路由协议[5]。 单路径路由节约存储空间，数据通信量少；多路径路由容错性强，健壮性好，且可从众多路由中选择一条最优路由。

1.4 基于位置的路由协议和非基于位置的路由协议

根据是否以地理位置来标识目的地、路由计算中是否利用地理位置信息，可分为基于位置的路由协议和非基于位置的路由协议。有大量WSNs应用需要知道突发事件的地理位置，这是基于位置的路由协议的应用基础，但需要GPS定位系统或者其他定位方法协助节点计算位置信息。

2 无线传感器网络路由协议分析

1）Flooding[6]：它是一个经典的传统网络路由协议，不要求维护网络的拓扑结构和进行路由计算。在Flooding协议中，接收到数据的节点以广播的方式向转发分组，数据包直到过期或到达目的节点才停止传播。该协议本身算法简单，不需要维护路由信息，容易实现，但消息的“内爆”（implosion）和“重叠”（overlap）是其固有的缺陷。对此，S·hedetniemi等人提出了Gossiping策略，节点将产生或收到的数据随机转发，避免了内爆，但同时也增加了时延。

2）DD（Directed Diffusion）[7]：它是由加州大学洛杉矶分校计算机科学系的Deborah Estrin等人在DARPA的1997-98ISAT项目完成后提出的。这是一个基于数据的、查询驱动的路由协议。DD路由机制分为周期性的兴趣（Interest）扩散、梯度（gradient）建立和路径加强三个阶段。在兴趣扩散阶段，sink节点通过广播兴趣消息来寻找数据源。梯度建立阶段，网络中各节点对兴趣消息进行缓存与合并，并创建包含上报率、下一条等信息的梯度，从而建立多条指向sink节点的路径。路径加强阶段，sink节点会对最先收到消息的邻节点发送路径加强信息。接收到该信息的节点做路径加强工作，源节点沿这个较高梯度的路径发送数据。当主路径失效时，其他发送梯度较小的路径作为备用路径，这种机制增强了路由的稳定性。然而，梯度建立的开销很大，不适合多sink点网络；数据聚合过程采用时间同步技术，会带来较大开销和时延。

3）MDR（Multi-path on-Demand Routing）：它是一种按需路由的多径路由协议，仅在源节点和sink节点间有数据包传输才进行路由发现，建立新路径，从而减少了通讯流量和能量损耗。MDR协议的路由机制包括路由请求和路由答复两个过程。数据源先发送路由请求，向邻居节点flooding短信息。当sink节点收到该信息后，马上向转发该路由请求消息的邻节点返回路由答复信息，并且在数据包域中增加了一个跳数项，用来指示到目前为止它传播的跳数。每个节点收到路由答复后增加一跳，继续转发给相应邻节点直至到达数据源。它的建立过程如图1所示。该协议健壮性好，即使网络拓扑频繁发生变化，数据依然能可靠地传输到目的地。由于发送端将源数据分裂成有冗余的子数据包后传输，这相对于发送相同的数据包副本减少了网络数据流量，因而平衡了网络的数据流量和可靠性，相应也提高了网络的安全性。

图1 MDR 路由建立过程

4）SAR（Sequential Assignment Routing）[8]： 它 是 1999年Katayoun Sohrabi等人在DARPA支持的一个研究中提出的一种保证QoS的路由协议。协议中sink节点的所有一跳邻节点都以自己为根建立生成树，其余各节点根据时延、丢包率等QoS参数来反向建立到sink节点的多条路径。在选择路径时， SAR协议充分考虑了功耗和分组优先权等特殊要求，采用局部路径恢复和多路径备份策略，避免由于节点或链路失败而引起的重新计算路由的开销。

5）TinyOS Beaconing[9]：该协议路由算法较为简单，路由建立前先对网络中的所有节点进行编址。sink节点对其信号覆盖范围内的所有节点周期性广播路由更新消息，接收到消息的节点将该sink点作为父节点保存到路由表中，然后在物理信道上广播该消息。该路由机制适合小规模网络，在较大网络中将导致节点和sink点间跳数增加；广播式路由更新消息消耗网络能量；路径建立只与接收到beaconing的时序有关，不进行任何优化，扩展性差；sink点周围的节点由于过多地参与数据传输，耗能较多，容易失效。

6）SPIN（Sensor Protocols for Information via Negotiation）[10]：它是第一个基于数据协商的路由协议。SPIN路由建立基于三次握手过程：ADV→REQ→DATA。路由建立过程如图2所示。节点产生或收到数据后，为避免盲目传播，用包含元数据的ADV消息向邻节点通告，需要数据的邻节点用REQ消息提出请求，数据通过DATA消息发送到请求节点。该协议通过ADV消息和数据命名机制解决了Flooding协议中的内爆和重叠问题。与Flooding和Gossiping协议相比，该协议有效地节约了能量。但是它也有缺点：当产生或接收数据节点的所有邻节点均不需要该数据时，将导致数据不能继续转发，会使较远节点无法得到数据。当网络中大多节点都是潜在sink点时，问题并不严重，但当sink点较少时，则是一个很严重的问题；而且当某sink点对任何数据都需要时，其周围节点的能量容易耗尽。

图2 SPIN路由建立过程

7）TBF（Trajectory Based Forwarding）：它是基于源站和位置的路由协议。与通常的源站路由协议不同，TBF协议在数据包头中指定连续的传输轨道参数，中间各节点根据参数按贪心算法，计算出轨道最近的下一跳节点。通过指定不同的轨道参数，很容易实现多路径传播和广播。由于是源站路由协议，数据包头的路由信息开销不会随着网络变大而增加，从而避免了传统源站路由协议的缺点。但随着网络规模变大，路径加长，网络中节点进行计算的开销也相应增加。

8）LEACH（Low Energy Adaptive Clustering Hierarchy）[11]：它是2000年麻省理工学院电子工程和计算机科学系的Wendi Heizelman等人为无线传感器网络专门设计的分簇路由协议。LEACH的基本思想：通过等概率地随机循环选择簇头，将整个网络的能量负载平均分配到每个传感器节点，从而达到降低网络能量耗费、延长网络生命周期的目的。簇头是周期性按轮随机选举的，每轮选举方法是：在簇的建立阶段，每个节点选取一个介于0和1之间的随机数，如果这个数小于某个阈值，该节点成为簇头；然后，簇头向所有节点广播自己成为簇头的消息；每个节点根据接收到广播信号的强弱来决定加入哪个簇，并回复该簇头。在数据传输阶段， 簇内的所有节点按照TDMA（时分复用）时隙向簇头发送数据，簇头将数据融合之后把结果发给基站。该协议采用随机选举簇头的方式避免簇头过分消耗能量，提高了网络生存时间。簇间路由采用一跳通讯，虽然传输时延小，但节点的通讯能耗较高且扩展性差。

9）TEEN（Threshold Sensitive Energy Efficient Sensor Network Protocol）：它利用过滤方式来减少数据传输量。该协议采用与LEACH协议相同的聚簇方式，但簇头根据与sink点距离的不同形成层次结构。TEEN定义了硬、软两个门限来过滤发送数据。只有满足如下两个条件的时候才能发送数据：当前数据的属性值大于硬门限；当前数据的属性值与上一次发送数据的属性值之间的差距大于软门限。该协议通过利用软、硬门限减少了数据传输量。其缺点是：如果数据的属性值一直达不到门限，节点不会发送数据，用户将接收不到网络的任何数据，并且不能得知所有节点是否死亡。

3 结论与展望

在无线传感器网络路由协议中，单路径路由协议算法简单，数据通信量少，有利于节省节点能量，但是其容错性和健壮性差。多路径路由协议在路由发现过程中得到多条不相关路径，减少了路由发现次数，并增强了路由的稳定性。

平面路由协议健壮性好，但建立和维护路由的开销大，数据传输跳数多，适合小规模网络。层次路由协议扩展性好，其能量消耗比较均衡，但簇的维护开销大。由于簇头是路由的关键节点，其失效将导致路由失败。

主动型路由协议需要定期更新路由，而响应性路由协议只有当网络中有数据传输时才会建立和更新路由。如果网络的数据传输量很大，主动型路由协议的路由开销一般要比响应型路由协议小。

无线传感器网络由于能量限制、拓扑变化及带宽限制，对路由算法要求非常高。目前传感器网络路由协议的研究重点主要集中在能量效率上，高效利用能量几乎是设计的第一策略。设计兼有平面结构和分簇结构优点的新型数据传输模式，是目前研究的一个热点。在某些基于簇的路由协议中，并没有簇头的概念，每个节点知道它将转发的下一个节点，我们把这类协议叫做基于虚拟簇的平面路由协议。这类协议既能有效地管理网络拓扑结构，又能有效地利用能量传输数据。此外，如何在簇内和簇间进行数据融合和处理，也很值得探索。

未来的研究中可能还需要解决由视频和图像传感以及实时应用引起的QoS问题。能量感知的QoS分簇路由越来越受到重视，它将在目标的实时追踪等方面得到应用，这就对带宽保证和能量高效路径的有效利用提出了严格要求。

[1]REN Fengyuan，HUANG Haining， LIN Chuang。 Wireless sensor networks[J].Journal of Software，2003，14(2)：1148-1157.

[2]MA Zuchang，SUN Yining， MEI Tao。 Survey on wireless sensors network[J].Journal of China Institute of Communications，2004(4)：114-124.

[3]FAN Xinyun，WANG Fubao，REN Fengyuan.Routing protocol for wireless sensor networks.Computer Automated Measurement & Control，2005(9)：1010-1013.

[4]CHEN Yuequan，GUO Xiaofeng，ZENG Qingka，iet al.Multipath routing research in mobile ad hoc networks[J].Computer Science，2005，32(6)：33-36.

[5]TANG Yong，ZHOU Mingtian，ZHANG Xin.Overview of routing protocols in wireless sensor networks[J].Journal of Software，2006，17(3)：410-421.

[6]Haas ZJ，Halpern JY，Li L.Gossip-Based ad hoc routing.In：Proc。of the IEEE INFOCOM。New York：IEEE Communications Society，2002：1707-1716.

[7]Intanagonwiwat C，Govindan R，Estrin D，iet al。 Directed diffusion for wireless sensor networking。IEEE/ACM Trans.on Networking，2003，11(1)：2-16.

[8]Sohrabi K，Gao J，Ailawadhi V，iet al。 Protocols for self-organization of a wireless sensor network.IEEE Personal Communications，2000，7(5)：16-27.

[9]Karlof C，Wagner D.Secure routing in sensor networks：attacks and countermeasures.Ad Hoc Networks，2003，1(1)：293-315.

[10]Kulik J，Heinzelman WR， Balakrishnan H. Negotiation based protocols for disseminating information in wireless sensor networks。Wireless Networks，2002，8(2-3)：169-185.

[11]Hu Junping，Jin Yuhui，Dou Liang.A Time-based Cluster-Head Selection Algorithm for LEACH.IEEE Symposium on Computers and Communications，2008：1172-1176.

TN8

A

1674-6708（2011）35-0173-03