无线传感器网络典型路由协议分类比较
常清
摘 要：无线传感器网络是继因特网之后对人类生活产生重大影响的技术，它在逻辑上将虚
幻的信息和真实的物理世界联系起来。无线传感器网络是由大量无处不在的、具有通信与计 算能力的微小传感器节点密集地布设在无人值守的监控区域而构成的能够根据环境自主完 成指定任务的智能自治测控网络系统。它能为人类生活带来不可估量的好处，所以，传感器 网络的路由协议的设计也是对人类的一项挑战，需要利用节点有限的能量更好的为人类服 务。目前已有多种路由协议，但其分类方式不是很清晰，本文以节点的传播方式为出发点， 对几种典型的路由协议给予重新分类，并对其进行分析，最后选出相对好的类别。
1.引言
随着微电子技术、计算技术和无线通信技术的进步，多功能传感器快速发展，进而使无 线传感器网络（wirele sensor network, WSN）成为目前研究热点。WSN 是由部署在检测区域内的大量廉价微型传感器节点组成，形成一个多跳的自组织网络系统，使其在小体积内集成信息采集、数据处理和无线通信等功能，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并提供给终端用户。WSN 能够广泛应用于军事、环境检测和预报、健康护理、智能家居、建筑物状态监控、复杂机械监控、城市交通、空间探索、大型车间和仓库管理、以及机场、大型工业园区的安全检测和其他商业等领域，且将逐渐深入到人类生活的各个领域。本文首先简要说明衡量路由协议的四个标准，然后就WSN 中路由协议的几种路由协议提出新的分类方法并利用标准加以比较。
2.路由协议的衡量标准
无线传感器网络的路由协议不同于传统网络的协议，它具有能量优先、基于局部的拓扑 信息、以数据为中心和应用相关四个特点，因而，根据具体的应用设计路由机制时，从四个 方面衡量路由协议的优劣【1】： （1）能量高效
传统路由协议在选择最优路径时，很少考虑节点的能量问题。由于无线传感器网络 中节点的能量有限，传感器网络路由协议不仅要选择能量消耗小的消息传输路径，更要 能量均衡消耗，实现简单而且高效的传输，尽可能地延长整个网络的生存期。 （2）可扩展性
无线传感器网络的应用决定了它的网络规模不是一成不变的，而且很容易造成拓扑 结构动态发生变化，因而要求路由协议有可扩展性，能够适应结构的变化。具体体现在 传感器的数量、网络覆盖区域、网络生命周期、网络时间延迟和网络感知精度等方面。 （3）鲁棒性
无线传感器网络中，由于环境和节点的能量耗尽造成传感器的失效、通信质量的降 低使网络变得不可靠，所以在路由协议的设计过程中必须考虑软硬件的高容错性，保障 网络的健壮性。
4）快速收敛性
由于网络拓扑结构的动态变化，要求路由协议能够快速收敛，以适应拓扑的动态变 化，提高带宽和节点能量等有限资源的利用率和消息传输效率。
3.路由协议的分类
针对不同传感器网络的应用，研究人员提出了不同的路由协议，目前已有的分类方式主 要有两种：按网络结构可以分为平面路由协议、分级网络路由协议和基于位置路由协议；按 协议的应用特征可以分为基于多径路由协议、基于可靠路由协议、基于协商路由协议、基于 查询路由协议、基于位置路由协议和基于QoS 路由协议。但这种分类方式太过分散，没有 整体概念，本文就各个协议的不同侧重点提出一种新的分类方法，把现有的代表性路由协议 按节点的传播方式划分为广播式路由协议、坐标式路由协议和分簇式路由协议。下面进行详 细的介绍和分析。
4.广播式路由协议
4.1 扩散法（Flooding）
扩散法是一种传统的网络通信路由协议。它实现简单，不需要为保持网络拓扑信息和实 现复杂的路由算法消耗计算资源，适用于健壮性要求高的场合。但是，扩散发存在信息爆炸 问题，即能出现一个节点可能得到数据多个副本的情况，而且也会出现部分重叠的现象，此 外，扩散法没有考虑各节点的能量，无法作出相应的自适应路由选择，当一个节点能量耗尽， 网络就死去。
具体实现：节点 A 希望发送数据给节点B，节点A 首先通过网络将数据的副本传给其 每一个邻居节点，每一个邻居节点又将其传给除A 外的其他的邻居节点，直到将数据传到B 为止或者为该数据设定的生命期限变为零为止或者所有节点拥有此副本为止。
4.2 定向路由扩散DD（Directed Diffusion）
C.Intanagonwiwat【2】等人为传感器网络提出一种新的数据采集模型，即定向路由扩散。 它通过泛洪方式广播兴趣消息给所有的传感器节点，随着兴趣消息在整个网络中传播，协议 逐跳地在每个传感器节点上建立反向的从数据源节点到基站或者汇聚节点的传输梯度。该协 议通过将来自不同源节点的数据聚集再重新路由达到消除冗余和最大程度降低数据传输量 的目的，因而可以节约网络能量、延长系统生存期。然而，路径建立时的兴趣消息扩散要执 行一个泛洪广播操作，时间和能量开销大。
具体实现：首先是兴趣消息扩散，每个节点都在本地保存一个兴趣列表，其中专门存在 一个表项用来记录发送该兴趣消息的邻居节点、数据发送速率和时间戳等相关信息，之后建 立传输梯度。数据沿着建立好的梯度路径传输。
4.3 谣传路由（Rumor Routing）
D.Braginsky【3】等人提出的适用于数据传输量较小的无线传感器网络高效路由协议。其 基本思想是时间监测区域的感应节点产生代理消息，代理消息沿着随机路径向邻居节点扩散 传播。同时，基站或汇聚节点发送的查询消息也沿着随机路径在网络中传播。当查询消息和 代理消息的传播路径交叉在一起时就会形成一条基站或汇聚节点到时间监测区域的完整路 径。
具体实现：每个传感器节点维护一个邻居列表和一个事件列表，当传感器节点监测到一 个事件发生时，在事件列表中增加一个表项并根据概率产生一个代理消息，代理消息是一个 包含事件相关信息的分组，将事件传给经过的节点，收到代理消息的节点检查表项进行更新 和增加表项的操作。节点根据事件列表到达事件区域的路径，或者节点随机选择邻居转发查 询消息。
4.4 SPIN（Sensor Protocols for Information via Negotiation）
W.Heinzelman【4】等人提出的一种自适应的SPIN 路由协议。该协议假定网络中所有节 点都是Sink 节点，每一个节点都有用户需要的信息，而且相邻的节点拥有类似的数据，所 以只要发送其他节点没有的数据。SPIN 协议通过协商完成资源自适应算法，即在发送真正 数据之前，通过协商压缩重复的信息，避免了冗余数据的发送；此外，SPIN 协议有权访问
每个节点的当前能量水平，根据节点剩余能量水平调整协议，所以可以在一定程度上延长网 络的生存期。
具体实现：SPIN 采用了3 种数据包来通信：ADV 用于新数据的广播，当节点有数据 要发送时，利用该数据包向外广播；REQ 用于请求发送数据，当节点希望接收数据时，发 送该报文；DATA 包含带有Meta-data 头部数据的数据报文；
当一个传感器节点在发送一个 DATA 数据包之前，首先向其邻居节点广播式地发送ADV 数据包，如果一个邻居希望接收该DATA 数据包，则像该节点发送REQ 数据包，接着节点向其邻居节点发送DATA 数据包。
4.5 GEAR（Geographical and Energy Aware Routing）
Y.Yu 等人提出了GEAR 路由协议，即根据时间区域的地址位置，建立基站或者汇聚节 点到时间区域的优化路径。把GEAR 划分为广播式路由协议有点牵强，但是由于它是在利 用地理信息的基础上将数据发送到合适区域，而且又是基于DD 提出，这里仍然作为广播式 的一种。具体实现：首先向目标区域传递数据包，当节点收到数据包时，先检查是否有邻居比它更接近目标区域。如有就选择离目标区域最近的节点作数据传递的下一跳节点。如果数据包已经到达目标区域，利用递归的地理传递方式【3】和受限的扩散方式发布该数据。
5.坐标式路由协议
5.1 GEM（Graph Embedding）
J.Newsome 和D.Song 提出了建立一个虚拟极坐标系统（VPCS, Virtual Polar 的
Coordinate System）GEM 路由协议，用来代表实际的网络拓扑结构。整个网络节点形成一 个以基站或汇聚节点为根的带环树（Ringed Tree）。每个节点用距离树根的跳数距离和角度 范围两个参数表示。
具体实现：首先建立虚拟极坐标系统，主要有三个阶段：由跳数建立路由并扩展到整个 网络形成生成树型结构，再从叶节点开始反馈子树的大小，即树中包含的节点数目，最后确 定每个子节点的虚拟角度范围。建立好系统之后，利用虚拟极坐标算法发送消息，即节点收 到消息检查是否在自己的角度范围内，不在就向父节点传递，直到消息到达包含目的位置角 度的节点。另外，当实际网络拓扑结构发生变化时，需要及时更新，比如节点加入和节点失效
5.2 GRWLI（Geographic Routing Without Location Information）
A.Rao【3】等人提出了建立全局坐标系的路由协议，其前提是需要少数节点精确位置信 息。首先确定节点在坐标系中的位置，根据位置进行数据路由。关键是利用某些知道自己位 置信息的信标节点确定全局坐标系及其他节点在坐标系中的位置。
具体实现：A.Rao 等人提出了3 中策略确定信标节点。一是确定边界节点都为信标节 点，则非边界节点通过边界节点确定自己的位置信息。在平面情况下，节点通过邻居节点位 置的平均值计算。二是使用两个信标节点，则边界节点只知道自己处于网络边界不知道自己 的精确位置消息。引入两个信标节点，并通过边界节点交换信息建立全局坐标系。三是使用 一个信标节点，到信标节点最大的节点标记自己为边界节点。
6.分簇式路由协议
6.1 LEACH（Low Energy Adaptive Clustering Hierarchy）
MIT 的Chandrakasan【5】等人为无线传感器设计的一种分簇路由算法，其基本思想是以 循环的方式随机选择簇首节点，平均分配整个网络的能量到每个传感器节点，从而可以降低 网络能源消耗，延长网络生存时间。簇首的产生是簇形成的基础，簇首的选取一般基于节点 的剩余能量、簇首到基站或汇聚节点的距离、簇首的位置和簇内的通信代价。簇首的产生算
法可以被分为分布式和集中式两种【6】，这里不予介绍。
具体实现：LEACH 不断地循环执行簇的重构过程，可以分为两个阶段：一是簇的建立， 即包括簇首节点的选择、簇首节点的广播、簇首节点的建立和调度机制的生成。二是传输数 据的稳定阶段。每个节点随机选一个值，小于某阈值的节点就成为簇首节点，之后广播告知 整个网络，完成簇的建立。在稳定阶段中，节点将采集的数据送到簇首节点，簇首节点将信 息融合后送给汇聚点。一段时间后，重新建立簇，不断循环。
6.2 GAF（Geographic Adaptive Fidelity）
Y.Xu【3】等人提出的一种利用分簇进行通信的路由算法。它最初是为移动Ad Hoc 网络 应用设计的，也可以适用于无线传感器网络。其基本思想是网络区被分成固定区域，形成虚 拟网格，每个网格里选出一个簇首节点在某段时间内保持清醒，其他节点都进入睡眠状态， 但是簇首节点并不做任何数据汇聚或融合工作。GAF 算法即关掉网络中不必要的节点节省 能量，同样可以达到延长网络生存期的目的。
具体实现：当划分好固定的虚拟网格之后，网络中每个节点利用 GPS 接受卡指示的位 置信息将节点本身与虚拟网格中某个点关联映射起来。网格上同一个点关联的节点对分组路 由的代价是等价的，因而可以使某个特定网格区域的一些节点睡眠，且随着网络节点数目的 增加可以极大地提高网络的寿命，在可扩展性上有很好的表现。
7.比较与分析
经过上面的简单介绍，每个协议在其设计的时候都有各自的侧重点和最优的方面，按照 衡量标准可以把以上协议做简略的比较并找出相对较好的一类协议。其中，如何提供有效的 节能，即能量有效性是无线传感器网络路由协议最首要注重的方面，可扩展性和鲁棒性是路 由协议应该满足的基本要求，而快速收敛性和网络存在的时间有紧密的联系。依据上述四个 标准，对本文所列举的路由协议的比较见表1。
由上表可见，广播式总是存在一种矛盾，当具有好的扩展性时势必以差的鲁棒性和能量 高效为代价，即以牺牲鲁棒性换取扩展性和高能量，这同时也严重影响了节点的快速收敛性。 而坐标式弥补了广播式的不足，可以同时达到四个衡量标准。分簇式相对于前两种方式来说， 具备了较好的性能，可以满足人们对传感器网络的一般要求。所以，以能量高效、可扩展性、鲁棒性和快速收敛性四个基本标准来衡量路由协议，分簇式是最佳的选择。
8.总结
本文首先确定了四个衡量路由协议的标准，并按一种新的方法把现有一些协议分成三 类，之后进行比较，最后得出分簇式是相对来讲最优的路由协议类。但是，分簇式只是相对 较好的协议类别，由于分簇式总是依附簇首节点的能量，即使簇首在不断的更替选出，仍有 最后某个簇首节点能量耗尽的情况，因此势必影响整体网络的生存时间。再者，由于衡量标 准的局限性，本文未能考虑安全性等方面的要求，因此得出的结论仅仅是一定的范围内比较 结果。由此，一种尽可能考虑多方面要求的路由协议仍是被期望的。 参考文献
[1] 孙利民，李建中，陈渝，朱红松著.无线传感器网络[M].北京：清华大学出版社， 2006.[2] 周东清，葛午未，朱娜.基于QoS 的无线传感器网络路由[J].计算机工程与应用.2007，43（23）：157-160.[3] 宋文，王兵，周应宾等著.无线传感器网络技术与应用[M].北京：电子工业出版社，2007.[4] 范武，李力.无线传感器网络SPIN 路由协议改进的方法[J].计算机与现代化.2007，139：93-96.[5] 于海斌，曾鹏等著.智能无线传感器网络系统[M].北京：科学出版社，2006.[6] 沈波，张世永，钟亦平.无线传感器网络分簇路由协议[D].上海：复旦大学，2006.
