无线传感器网络路由协议性能研究

李海雁，钱开国，解永刚，戴祖诚

（1.昆明学院 信息技术学院，云南 昆明 650214；2.昆明学院 物理科学与技术系，云南 昆明 650214；3.昆明学院 现代教育技术中心，云南 昆明 650214；）

无线传感器网络[1-2]（Wireless Sensor Networks，WSN）由具备一定的运算、存储和无线通信能力的体积较小、资源极端受限的，制作成本要求较低的传感器节点构成。无需通信基础设施，自组织的随机部署和通过集成传感器实时采集周围环境因子并通过无线通讯方式传回终端用户，从而在环境监测、国防军事、智能交通管理、空间探索等领域具有潜在的用途，近年来成为国内外研究的热点领域。但还存在大量挑战性的研究课题，路由协议的研究和设计就是其中之一。

无线传感器网络的路由技术[3]担负着为采集到的数据寻找路由和将其传送到基站节点的任务，是无线传感器网络组网的关键技术，而路由算法和协议则是路由技术的核心内容，直接关系到节点能耗、时延、吞吐率和成功率等无线传感器网络性能的优劣。

由于无线传感器网络节点携带有限电源供电，节点的高效率使得网络拓扑实时变化，同时节点的计算能力、通讯能力和存储能力有限，给路由算法和协议的设计带来了很大的挑战，传统的计算机网络路由协议和自组织网络路由协议均不适用于无线传感器网络，为此，需要根据无线传感器网络特点设计专门的路由算法和协议。这是无线传感器网络研究和设计的主要技术难点之一。

网络仿真模拟环境NS-2对Ad hoc网络路由协议的研究提供了更为便捷的手段。目前国内外各研究机构根据自己的特定应用，推出了适用于特定应用场景的无线传感器网络路由协议，文中对无线传感器网络的路由协议进行了分类研究，讨论了其性能评价指标。设计了典型平面和簇结构的路由协议在NS-2环境下进行仿真，对性能进行比较分析，对Ad hoc路由协议的研究具有参考意义。

1 无线传感器网络路由协议

路由协议解决的是把信息从源经过中间网络节点穿过网络传递到目的节点的行为，无线传感器网络中间节点不同于Ad hoc网络，其既完成采集任务，还要完成路由的两个基本动作：最佳路径选择和转发数据。转发数据相对来说比较简单，而路径选择较为复杂。

1.1 无线传感器网络路由协议的研究分类

从功能上讲，无线传感器网络路由协议是一种将数据从源节点传输到基站节点的机制。而通常情况下，无线传感器网络的节点地位是平等的，各节点通过分布式算法来相互协调。由于无线传感器节点的电源、计算、存储和通信等能力的限制以及无线传感器网络应用背景相差极大，如传统的计算机网络或者Ad hoc网络一样设计通用的网络协议不利于资源的充分利用，因此无线传感器网络路由协议的设计应根据特定应用进行设计，满足应用需求的同时尽量降低网络传输代价，扩大网络容量和提高网络吞吐量。

近年来研究人员根据特定应用提出了上百种路由协议，可以根据不同的划分原则进行分类研究：

1）根据传输过程中间节点的数量，可以分为单跳路由（Single-hop）和多跳路由（Muit-hop）。 单跳路由实现简单，但是在保证网络覆盖范围条件不变，就要增大节点的有效传输半径，必然增大节点的发射功率，进而增大节点能耗，缩短了网络的生命周期。而多跳路由有效减小节点的传输半径，节约能量。

2）根据路由组网的拓扑控制结构分为平面（flat）路由协议和分簇层次（Clustering Hierarchy）路由结构。平面路由协议需要节点维护全网信息，节点失效和新节点的加入等网络扩展性差，节点建立和维护路由耗费资源，尤其是能耗开销大，不适合大规模的网络。而分簇的层次路由只需要节点维护局部信息，有效利用了有限的传感器节点资源。扩展性好，适合规模大的网络。其关键技术在于簇头节点的选择算法和簇建立和维护算法，实现较为复杂。

3）根据路由建立过程中是否应用节点位置信息参数分为地理位置信息路由和非地理位置信息路由。地理位置信息路由协议研究时均假定传感器节点根据GPS或者定位算法等计算出自身的位置信息，将位置信息作为辅助条件，用来改善已有路由协议的性能，例如泛洪（Flooding）协议中指定数据传送的方向从而减少传送的数据量。用于分簇层次结构中用于优化分簇结构，是簇头节点均匀分布到整个网络中。

4）根据在数据传输过程中是否需要数据融合处理分为以数据为中心的路由和以数据采转发为中心的路由。以数据为中心的路由协议对感知到的数据进行属性标识，对相关数据进行融合处理，从而减少冗余数据的传输。而以数据转发为中心的路由多记成与Ad hoc路由协议。

5）根据在数据传输过程中是否考虑服务质量的要求可以分为基于QOS的路由协议和非QOS的路由协议。基于QOS的路由协议在路由实现和维护时，力求满足网络QOS需求，考虑数据包优先级、端到端时延、数据融合精度等。

1.2 典型的路由协议分析

对目前已有的路由协议从基本思想、关键问题和扩展分析几个方面进行分析。

1）泛洪（Flooding）、谣传（Gossiping）路由协议

泛洪（Flooding）协议[4]、谣传（Gossiping）[5]和定向扩散（Directed Diffusion）路由协议是最为经典和简单的平面路由协议。泛洪（Flooding）路由协议的基本思想是每个节点收到其他节点的数据就以广播的方式转发给邻居节点，一直重复下去，直到数据传送到目的节点为止，该路由协议的关键问题是信息经过全网的复制，产生大量的冗余信息，同时出现同一个数据包多次发送给同一个节点的信息内爆和信息重叠，谣传（Gossiping）针对这一问题进行改进，其在就行下一跳数据转发时，是随机的选择一个邻居节点尽心转发，获得数据包的邻居节点以同样的方式进行数据的传递。这种方式会出现增大数据包传递到目的节点的时间。

2）定向扩散（Directed Diffusion）路由协议

定向扩散路由协议[6]是一种基于梯度场和数据相关的路由协议，基本思想是基站节点周期性的以泛洪方式广播一种“兴趣”包，告诉网络中的节点需要的信息，在“兴趣”消息传播过程中，协议逐渐在每个传感器节点上建立反向的从数据源到基站节点的梯度场，梯度场参考从源节点到基站节点通信代价最低和能量信息建立。兴趣广播完后，梯度场也建立完成，数据源产生数据包后就向感兴趣的邻居节点传递数据，不是基站节点就以同样的方式转发该数据，基站节点将收到从不同路径传送过来的数据，同时基站节点参照时延、能量自适应性，通信代价等信息选择一条路径并强化，以后的数据就沿着这条路径传送。DD路由协议要求节点发起路由建立过程，而且兴趣需扩散至全网，因此不太适合大规模的网络。

3）SPIN路由协议

SPIN[7]路由协议是一种基于协商机制和以数据为中心的路由协议，引入了数据融合的思想。协议的基本思想是采用3次握手协议来实现数据的交互，在数据转发过程中使用3种数据报文：ADV、REQ和DATA。当一个节点采集的数据后，将广播ADV报文给其邻居节点，如果邻居节点希望接收该数据，则返回REQ报文，数据源节点将发送DATA报文给该节点。该协议关键问题在于多个节点会返回REQ给同一个节点，会引起信息冲突。

4）LEACH及其改进路由协议

LEACH[8]路由协议是分簇层次路由协议，协议的基本思想是引入分簇层次型网络拓扑控制结构，网络自适应的周期性的选择簇头节点，其他节点就近加入相应的簇头，形成虚拟簇，个簇内成员节点以TDMA的方式将采集的数据发送给簇头，簇头融合处理后在转发给基站节点。关键问题在于簇头节点要求和基站能直接通信，则不适用于大规模网络，同时簇头的选择算法会带来簇头分布不均等问题，后产生LEACH-C[9]，LEACH-F等改进路由协议，均在簇头选择算法上进行改进，尽量使簇头分布均匀。

5）静态成簇协议（Static Clustering）

在LEACH协议中，当簇形成后，簇头节点和相应簇不在变化，该机制使得簇头节点容易能量耗尽。

6）LAR基于地理位置信息的算法

LAR路由协议[10]的基本思想是利用地理位置信息来限制泛洪协议广播数据包的范围，既该协议根据节点的位置信息，给出一个泛洪协议广播数据包的期望域，只有在期望域的节点才能收到该数据包，从而减少参与泛洪的传感器节点数量，降低网络的开消。该算法收敛速度快，但是网络中维护全网的地理位置信息也需要很大的开销。

7）GAF基于地理位置信息的算法

GAF[11]路由算法的基本思想是引入节点的动态睡眠调度机制，使传感器节点尽量处于睡眠状态，从而降低网络的能耗。该协议首先通过划分虚拟网格的方式确定数据转发的等价节点，然后在在虚拟网格中只需要一个节点处于活动状态，其他节点睡眠来节约全网的整体能耗。

8）GPSR路由算法和MTE路由协议

GPSR[12]路由算法是基于地理位置信息的路由算法，在数据转发时采用了贪婪策略选择下一跳网络节点，即数据源节点在自己的邻居节点中选择距离最近的一个节点作为下一跳节点。MTE路由协议最小化能量传输协议，在数据转发时在邻居节点中选择通往基站节点的能耗最小的节点作为下一跳路由。

2 路由协议的性能分析

无线传感器网络路由协议设计时，要考虑出传统Ad hoc网络需要的快速收敛、低延时、适应网络动态拓扑等要求外，更多的要考虑无线传感器网络本身的资源稀缺的特点，更应考虑能耗等性能指标。现将设计约束分为定性和定量两种进行分析。

2.1 定性指标

定性指标是从网络某个方面的性质出发来评价无线传感器网络路由协议的适应性和现实性的需求，如安全性、是否是分发式路由协议，有无环路、扩展性、是否支持数据融合等。

无线传感器网络路由协议评价定性属性包括:

1）适应动态拓扑 无线传感器网络拓扑极不稳定、节点移动或者由于能源耗尽使得节点失效，当网络规模较大时，这些因素引起网络拓扑变化频繁，因此要求无线传感器网络路由协议要适应动态拓扑的变化。

2）减少控制开销 无线传感器网络节点资源极端有限，路由协议的设计要节约资源，控制、建立和维护开销要小。

3）分布式操作 无线传感器网络本身属性，其要求无线传感器网络路由协议本身是一个分布式算法。

4）无环路 虽然按照某些定量标准（例如，性能标准）来说，不是必须的，但却可以避免诸如最坏情况现象。

5）基于需求的操作 在网络中，让路由算法适应基于按需流量模式，而不是假设一种不变的流量分布（在任何时刻在所有节点之间维护路由），是一种更好的方法。如果能智能地做到这一点，可以更加有效的利用网络能源和带宽资源，代价是增加了路由发现的延时。

6）先应操作 基于需求操作比较不重要的方面。在某些情况下，基于需求操作增加的延时是不可接受的。如果带宽和能源允许，在这种情况下，就需要先应式的操作。

7）“睡眠”周期操作 基于能量保存，或其他某种非活动的需要，无线传感器网络节点在某段时间内可能会停止发送和/或接收。路由协议应该能适应这种睡眠周期，而不产生非常不利的后果。

8）路由方式和路由更新方式 不同的路由方式和路由更新方式对协议的影响是巨大的，所有路由协议都必须路由方式的效率和路由更新方式的效率。

9）数据融合需求 无线传感器网络邻居节点间探测的数据可能类似，或者在协议设计策略中会产生冗余数据，因此要求无线传感器网络路由协议应支持数据融合处理，以减少传输数据量进而降低网络开销。

10）扩展性 通常任务无线传感器网络规模巨大，节点容易失效，要求路由协议具有高可扩展性。

典型协议定性分析如表1所示。

表1 典型协议性能的定性分析Tab.1 The perform ance qualitative analysis of typical protocol

2.2 定量指标

定量指标对网络性能评价指标进行量化，细致精确的刻画网络某个方面的性能：

1）能耗和生命周期 无线传感器网络节点携带有限的电池供电，部署出去难以回收更换电池，而电池耗尽，节点失效，因此无线传感器网络能耗和生命周期成为评价路由协议的关键性指标之一。

2）路由协议收敛速度 无线传感器网络规模大，路由协议一般是一种按需操作，当有数据传送要求时才进行路由建立，因此路由协议收敛速度是一个评价指标，在实际考察中可以用第一个数据包成功收发时间进行衡量。

3）数据包成功接收率 数据包成功接收率是目的节点收到的数据包数目与数据源节点发送的数据包数目之比，描述了无线传感器网络的丢包率，刻画了路由协议的正确性和完整性指标。

数据包成功接收率=成功接数据包数/发送数据包数

4）平均延时 平均延时刻画了数据分组从发送，经过路径缓冲、节点转发、MAC层重传等后送达目的节点的时间。用式（1）进行计算:

其中N表示成功送到的数据分组数，rti是分组送达目的节点的时间，sti表示分组被发送的时间。

3 基于NS-2仿真环境的路由协议性能分析

3.1 NS-2简介和仿真场景建立

NS（Network Simulator）[13]网络仿真器是研究大规模网络和未来网络协议行为特性的软件，是一款开放的网络仿真平台，研究人员可以在已有研究的基础上重构协议源码和重新编译，仿真自己设计的网络特性行为和协议。

文中设计了部分无线传感器网路路由协议的仿真实验，仿真实验参数设置如下：仿真场景在1 000×1 000，基站节点位于（50，175），随机部署100个节点，节点的初始能量设置为2 J，数据包长度为500 byte，发送接受1 bit的数据电路消耗50 nJ。

3.2 仿真结果及其分析

3.2.1 生命周期实验分析

实验中节点能量耗尽认为节点死亡，分析仿真后的trace文件，将存活节点数随仿真时间统计下来，结果如图1所示。MTE路由协议应用贪懒策略选择下一跳节点进行数据转发，在开始时间能没有路由建立数据包进行转发，因此其在初始阶段能量消耗低，节点死亡数较少，leach路由协议第一个节点死亡时间较leach-c晚，但是总体网络生命周期没有LEACH-C长。而static-cluster路由协议由于簇头死亡后，剩余节点就失去和基站的联系而不在收发数据，因此一直有节点存活。

图1 存活节点数对比图Fig.1 The contrast graph of active nodes number for protocol

3.2.2 能量消耗实验分析

能量消耗实验结果如图2所示，MTE路由协议采用贪婪策略选择下一跳转发节点，能量消耗低，到时很难将数据包送到基站节点，也就是数据包的延时大，在大规模的网络中难以送达。static-cluster路由协议由于簇头死亡后不在工作，因此后期剩下的存活节点没有工作而使得能量较低。开始时，LEACH协议较LEACH-C协议有相对优越的能耗，随着仿真时间向后推移，能耗增大较快，使得网络生命周期整体缩短。

图2 能耗结果对比图Fig.2 The comparing graph of energy consumption for protocol

3.2.3 收达数据包实验

验证路由协议的收敛时间和有效性，我们统计的前300 s的数据包送达情况，MTE由于一直出现数据包冲突碰撞，在前300 s内没有送达到基站的数据包，static-cluster路由协议随着簇头节点死亡而剩下的存活节点和基站失去联系，后期也没有送达基站的数据包。LEACH-C送到的数据包较LEACH优越。

从图1、2和3可以看出，无线传感器网络路由设计是一个综合考虑多方面约束条件的关键技术。如MTE节约了能量，延长了网络生命周期，但是数据包延时太大而不适用，静态成簇路由协议简单但是簇头节点负担太重而造成簇头节点过早死亡，LEACH协议引入簇头轮换机制但是簇头分布不均，利用LEACH-C进行一定个改进获得了较好的性能表现。

4 结束语

作为物联网的数据感知部分的无线传感器网络已成为当今社会各界的研究热点，路由协议的设计面临着网络规模大、节点无法编址、节点资源节点受限都很多约束条件成为既有挑战性的研究课题。文中对已提出的无线传感器网络进行分类研究，给出性能评价指标体系，设计了典型的平面、分簇的路由协议在网络仿真器中进行仿真研究分析方法，为相关的研究提供参考。

[1]Estrin D，Govindan R，Heidemann J，et al.Next century challenges:Scalable coordination in sensor networks[J].Proceedings of ACM International Conference on Mobile and Computing Networks，1999：263-270.

[2]Hill J.System architecture for wireless sensor networks[D].Berkeley:University of California，2003.

[3]唐勇，周明天，张欣.无线传感器网络路由协议研究进展.软件学报[J].2006，3（17）:410-421.TANG Yong，ZHOU Ming-tian，ZHANG Xin.Overview of routing protocols in wireless sensor networks[J].Joural of Software，2006，3（17）：410-421.

[4]Vamsi K，Arjan D，Durga S，et al.Optimal flooding protocol for routing in adhoc networks[C]//IEEE Wireless Communication and Networking Conference，2002:1-10.

[5]Sandra M，Stephen T，Arthur L，et al.A survey of gossiping and broadcasting in communication networks[J].IEEE Networks，1998，18（4）:319-349.

[6]IntanagonwiwatC，Govindan R，Estrin D，etal.Directed diffusion for wireless sensor networking[J].IEEE/ACM Transactions.2003，4（11）:2-16.

[7]Heinzelman W，Kulik J，Balakrishnan H.Adaptive protocols for information dissemination in wireless sensor networks[C]//Proc.5th ACM/IEEE Mobicom Conference （MobiCom’99）Seattle，WA，1999，174-185.

[8]Heinze L，Wendi B，Anantha P ，et al.Energy-efficient communication protocols for wireless microsensor networks[C]//The Proceedings of the Hawaii.International Conference on System Sciences，2000：1-10.

[9]Heinze L，Wendi B，Anantha P，et al.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications，2002，1（4）:660-670.

[10]Yong B，Nitin H.Vai D.Location-Aided Routing （LAR）in mobile ad hoc networks[J].ACM/Baltzer Wireless Networks（WINET）Journal，2000，6（4）:307-321.

[11]Xu Y，Heideman J，Estrin D.Geography-informed energy conservation for ad hoc routing[C]//Proceedings of ACM MobiCom’2001，2001:16-21.

[12]Brad K，Kung H T.GPRS:Greedy perimeter stateless routing for wireless networks[C]//ACM/IEEE International Conference on Mobile Computing and Networking，2000:243-254.

[13]The VINT Project.The ns Manual[EB/OL].（2010-5-9）[2011-7-20]http://www.isi.edu/nsnam/ns/doc-stable/ns_doc.pdf.