Adhoc无线路由协议

《Adhoc无线路由协议》由会员分享，可在线阅读，更多相关《Adhoc无线路由协议（11页珍藏版）》请在装配图网上搜索。

1、Ad hoc 无线路由协议摘要：无线Ad hoc网络在现代社会越来越多的应用于各个领域， 如军事、 医学、空间探测等。网络拓扑经常性地改变需要有效的动态路由协议。 在本文中， 我们概括介绍了目的节点序列号距离矢量（DSDV）协议、无线路由（WRP）协议、最优链路状态路由（OLSR）协议、源树自适应路由（STAR）协议和基于逆向路 径转发的拓扑分发（TBRPF）协议5种先应式路由协议，动态源路由（DSR）协 议、自组网按需距离矢量（AODV ）协议、基于联合稳定性路由（ABR）协议和 临时排序路由算法（TORA）协议4种按需路由协议。两种基本的协议 DSR和 AODV 协议在实际中应用广泛，我们

2、在本文中做重点比较，并通过仿真来将两 种协议的性能差异形象的展示出来。关键词：Ad hoc网络 路由协议 网络性能OPNET仿真Abstract: Wireless Ad hoc network has many extensive applications in the field of military affairs 、 medicine and explorations in deep space etc in modern times. We briefly present 5 types of table-driven routing protocols ,which are De

3、stination-Sequenced Distance-Vector protocol 、 Wireless Routing Protocol 、 Optimized Link State Routing protocol 、 Source Tree Adaptive Routing protocol 、 Topology Dissemination Based on Reverse-Path Forwarding ， and 4 types of on-demand routing protocols, which are Dynamic Source Routing protocol 、

4、 Ad-hoc On-Demand Distance Vector Routing protocol 、 Associativity Based Routing Protocol 、 Temporally Ordered Routing Algorithm protocol. We compare the performance of two on-demand routing protocols DSR protocol and AODV protocol because they are used widely in practice. And we show the different

5、performances between them. by simulation.Keywords: Ad hoc network、 Routing protocol、 Performance of the network、 OPNET simulation1. 介绍无线自组网即我们所说的无线 Ad hoc 网络，它是由一组具有路由功能的节 点组成的分布式无线多跳网络， 它不依靠任何预设的网络基础设施。 在源节点和 目标节点间采用多跳而不是一跳的方式来传输数据可以增加网络容量和降低传 输能量的消耗， 但是也会带来新的挑战， 如：如何在源节点和目标节点间寻找一 条或者多条最优的路径。因此路由协议

6、在多跳 Ad hoc 网络中起着举足轻重的作 用。随着研究人员的大量工作， 现有的路由协议有很多， 路由协议的主要设计目 标是：满足应用需求的同时尽量降低网络开销， 取得资源利用的整体有效性， 扩 大网络吞吐量。 其中，根据源端何时获取路由， 自组网路由协议可分为先应式 （表 驱动）路由协议、按需（反应式）路由协议和混合路由协议。本文主要介绍前两 种。先应式路由协议又称为表驱动路由协议， 在这种路由协议中， 无论是否有通 信需求，每个节点采用周期性的路由分组广播， 交换路由信息， 维护一张包含到 达其他节点的路由信息的路由表。 当检测到网络拓扑改变时， 节点也会在网络中 广播更新分组。 收到更

7、新分组的节点则更新自己的路由表， 以保证准确的路由信 息。路由广播通常采用泛洪方式， DSDV、FSR、LANMAR 、OLSR、TBRPF 等 属于这类路由协议 1 。因为带宽资源非常有限并且宝贵，自组网的重要特征是网络拓扑不断的变 化，所以用以上方法为每个节点维护到全网的路由是没有必要的， 按需路由协议 根据网络分组的传输请求， 被动地搜索从源节点到目的节点的路由。 当没有数据 分组要求发送时， 节点处于静默状态， 并不交换路由信息。 这使得路由开销大大 降低，提高了网络的吞吐量。 但是，每条激活路由建立的平均开销要远远高于先 应式路由协议的平均开销。 只有在少数节点之间需要通信时， 才比

8、先应式的路由 开销小。这种协议包括： DSR、AODV、TORA、ABR、MSR 等1。根据每个节点获得的状态信息和 /或节点之间交换的状态信息不同，可以将 路由协议分为基于拓扑的协议（topology-based protocol）和基于目的端的协议（destination-based protocol） 0对于前者，节点维护整个网络的拓扑信息（如 DSDV ） ，在固定的 Internet 网络中非常有效；而在资源有限、高度动态的 Ad hoc 网络中，大量和频繁地交换路由信息对网络性能显然不利。 对于后者， 节点仅仅 维护局部（如一跳或两跳）的拓扑信息（如 OLSR）,在动态网络中易于出

9、现路由环路，且算法收敛速度慢自组网路由协议可以根据节点更新路由的方法不同，分为最佳算法（ORA）和最小开销算法（LORA） 2。ORA旨在尽可能快的更新路由表，建立和维护 满足某个优化目标的最佳路由；而 LORA 则在协议能够正常运行的前提下时空 之分组的开销大道最小。在无线网络的先应式路由协议中采用 ORA 的结果是， 如果网络拓扑经常变化， 路由更新分组数量将急剧增加， 消耗大量的带宽。 而按 需的路由协议如 DSR、AODV 等则是采用 LORA 原则，协议按照一定的优化目 标建立路由， 此路由一旦建立就一直使用， 即使最佳路由发生变化也并不试图重 建路由，知道由于拓扑变化导致路由失败时

10、，才进行维护。2. 协议的算法描述2.1 先应式路由协议2.1.1 DSDV 协议DSDV 协议是先应式路由协议， 是由传统的 Bellman-Ford 路由协议改进得到 的，其特点是利用目的节点序列号解决了 DBF 算法中的路由环路和计数至无穷 问题3。DSDV 要求每个节点保存路由表， 表中列出了所有可达的目的节点及到达该 目的节点的跳数。每个路由条目包含目的节点产生的序列号， 用来区分新旧路由。 节点间通过周期性地发布路由更新分组来交互路由信息，以保证路由表的正确 性。当有重要的新信息是也广播路由更新分组。 移动节点收到新的路由信息分组 时，路由的更新遵循以下两个原则：比较该更新分组中携

11、带的路由信息和节点保存的路由条目。 如果节点收到 的路由的目的节点序列号大于路由表中相应的目的节点的序列号， 则采用有更新 序列号的路由而丢弃原有的旧序列号的路由。如果更新分组中目的节点序列号与现存的序列号相同， 则选择具有较好度 量的路由条目，若新路由有较好度量， 则丢弃现存的路由或将其存储为次之路由。为了减轻网络的负担，路由更新分组采用两种形式：第一种为“full dump” 它携带节点所有的路由表信息；另一种为“增长（In creme ntal）”型数据分组， 它携带的信息是自上次发送 full dump 以后节点的路由表中发生变化的哪些路由 条目的信息。移动节点还保存一个附加表来存储已

12、经在增长型路由信息数据内传 送的数据。当网络中拓扑结构改变时， DSDV 算法采用以下两种方法来检测链路的中 断：链路层检测到某条链路中断时，向路由层报告。 通过时间推断，即节点在过了一段时间后仍没有收到某个节点发送的分组， 就自动认为本节点到该节点的链路中断， 将相应的路由条目设置为无穷大 （实际 中，若链路度量为跳数，则经常设置为 N+1，N 为网络的节点数）来描述断开的 链路。检测出链路中断的节点会发送一个更新分组， 该分组有一个新的序列号， 跳 数为无穷大。 这会引起网络中路由表的更新， 只有当再次收到丢失节点的信息后 新的路由才会重新建立起来。虽然在网络拓扑变化频繁的情况下， DSD

13、V 协议的收敛性能不好， 但在一般 情况下，收敛还是相当快的。但是，当加入网络的节点越来越多，路由表容量及 开销和带宽也相应的增加。 节点不一定用到至所有目的节点的路由条目， 多余的 路由条目也会造成资源的浪费。 DSDV 协议仅支持双向链路， 这就限制了其在无 线网络中的使用。最后， 当节点的移动率较高时， DSDV 协议的性能将急剧恶化 2。2.1.2 WRP 协议WRP 协议中，节点保存的信息表包括距离表、路由表、链路开销表、分组 重传列表 4 个部分。节点通过获得邻节点的状态变化信息来维护自己的信息表， 并通知邻节点； 收到来自邻节点的信息后， 要更改保存的信息表， 节点需要发送 一个

14、回复分组（ ACK ）说明已经收到并处理了某个更新消息。若节点没有转发 数据分组或是更新消息，则要定期发送 HELLO 分组，以确保节点间的联通性， 节点在一段时间内没收到邻节点发送的任何分组， 就认为和该邻节点间的链路失 败。节点就要重新计算到受影响的目的节点的距离和对应的前驱节点， 并且向其 邻节点发送更新分组通知哪些目的节点的距离和前驱节点发生变化 2 。由于该协议有先驱节点的记录，可以有效地避免路由环路。 WRP 要求节点 维护 4 张路由表，这会给节点带来负担，特别是节点较多的时候。由于利用 HELLO 分组保持连通性， WRP 不允许节点处于睡眠状态，这会耗费电池电量 网络的带宽也

15、会被更新分组大量占用。2.1.3 OLSR 协议OLSR 协议2是对纯链路状态算法进行优化而形成的。 协议的核心是多点中 继：通过减少同一区域内相同控制分组的重传转发次数来减少网络中广播分组的 数量。网络中的每一个节点选取其邻节点的一个子集用于转发该节点发送的控制 分组。这些被选择的节点就成为该节点的 MPR，而该节点就成为这些MPR的多 点中继选择节点（MPR Selector）。协议根据选择的MPR集来计算到所有目的节 点的路由。网络中的每个节点周期地广播它的MPR Selector的信息，每个节点收到这一消息后， 计算并更新自己到达每个一致的目的节点的路由。 因此，路由 就是通过从源到目

16、的节点的 MPR 的逐跳节点序列。该协议适用于使用时刻维护的信息较多且到新目的节点的路由请求较频繁 的网络、OLSR通过减少同一区域内相同控制分组的重复转发次数，显著减少了 网络中广播分组的数量， 特别适用于网络规模大、 节点分布密集、 节点间通信频 繁的网络。该协议还具有找路时延小的优点。2.1.4 STAR 协议前述的几种协议算法， 都是遵守 ORA（Optimum Routing Approach 最佳算法） 原则的，而 STAR 协议是第一个遵守 LPRA（Least-Overhead Routing Approach最小 开销算法）原则的先应式路由协议。STAR协议建立路由后，并不是

17、图维护最佳路 由，它使用以源节点为根的路由树存储路由信息， 当路径可能产生环路时主动向 相应的节点发信号，不需要用周期更新来验证路径的有效性，大大降低了开销。STAR协议的控制开销较小，它允许采用次最佳的路由。 STAR协议只传播 通往目的节点必须的链路状态信息来减少带宽的消耗， 利用这些信息来决定发更 新分组的实际、检测新的目的节点、不可达目的节点和路由环路。2.1.5 TBRPF 协议TBRPF 协议是一种先应式的链路状态路由协议，提供逐跳的最短路径 2 。 每个节点根据缓存在拓扑表中的局部拓扑信息，利用 Dijkstra 算法，计算到目的 节点（网络中的其他节点）的路由。 TBRPF 协

18、议包括两个模块：路由模块：TBRPF使用周期性的更新消息和增量的更新消息保证邻节点 获得计算路由所需的状态信息节点源树的一部分。 为了减少开销。 每个节点 只向邻节点报告自己的部分源树成为源树的报告部分。 为了改善协议的鲁棒 性。让节点获得更多的拓扑信息从而计算出多条路径， 并且使得中继优先级高的 节点更大可能地为其他节点转发分组， 每个节点可以独立地选择报告除源树的报 告部分之外的拓扑信息。邻居发现模块：通过“增量 HELLO” 分组，节点可以实现邻居发现功能。 节点周期性发送的增量 HELLO 分组，只报告发生变化的邻节点的状态信息，而 不是报告所有的邻节点的状态信息， 所以其分组长度比其

19、它链路状态路由协议的 分组要小得多。该协议是 R.Ogier 等人在 1999 年提出的一种应用于多条网络中的广播路由 协议，该协议考虑如何向网络中所有节点广播拓扑信息 （包括链路费用信息和链 路通/断状态信息），后来，改协议经修改后，变成了一种有本质差别的路由协议 基于逆向路径转发的拓扑分发路由协议，也成为 TDRPF协议。2.2按需路由协议2.2.1 DSR 协议DSR 协议的特别之处是它运用了源路由算法，即只有发送节点知道完整的 到目的节点的多跳路由。这些路由被储存在cache内4。被发送的数据分组在其 分组头内携带源路由信息。一个 Ad hoc 网络中的节点欲发送数据到目的节点，但是当

20、它检查自己缓存 的中没有到目的节点的路由时， 它将启动路由发现过程。 源节点用泛洪的方式给 网络中的其他节点发送路由请求分组（RREQ）。每一个收到该分组的节点向它 的邻节点转发该分组，除非它就是目的节点或者在它的cache中存有到目的节点 的有效路由。这样的节点将会回复一个路由应答分组 （RREP）给源节点。RREQ 和 RREP 分组也是服从源路由算法的。由 RREQ 分组建立了一条到目的节点的 穿越网络的路径， RREP 分组利用该路径反转路由而到源节点。源节点则将收到的RREP分组所携带的路由信息储存到它的 cache内以备后用。如果源路由中的任何一段链路由于一些原因而中断了， 则会有

21、一个路由出错 分组（RRER）通知源节点。源节点会将它的cache内的包含那一跳的路由删除。 并且源节点将会启动新的路由建立过程。 协议作者还提出了一些优化措施来使协 议更有效，优化措施如下所述 4 ：抢修：当分组传送过程遇到链路断开时可由中间节点根据自己的cache来选择另一条路由。在发送 RERR 分组之后，节点可能试图抢修遇到路由出错的 数据分组而不是丢弃它。 它首先搜索自己的路由缓存， 若查找到到目的节点的路 由，则通过用自己缓存中的路由替换分组中的源路由来抢修数据分组。无确认路由修复：源节点在收到 RERR分组时，可把它包含在下次发送 的RREQ中，这样可以帮助网络中其他节点获得 R

22、ERR信息，刷新cacha混合侦听：当节点侦听到并不是发给自己的分组时，它检查存储器，如果 有通过自己的更好的路由，就发送RREP给源节点。这样可以让节点不需要直接 参与路由过程也获得路由信息。在另一方面，如果听到的是RREP分组，对方就 停止RREP的传送，可以在一定程度上避免 RREP分组泛滥。随机延迟2:为了防止RREQ在泛洪过程产生冲突，每个节点在收到RREQ 分组时，转发前随机延迟一段时间。 节点为某个路由请求启动路由建立过程， 在 收到 RREP 分组之前， 如果还没有超过最小时间限制， 节点不为该请求再次启动 路由建立。路由建立过程稍带数据分组：在业务产生而节点没有路由可用时，启

23、动路 由建立机制，在等待路由应答的这段时间内，数据分组或者被缓存或者被丢弃。 如果在RREQ中捎带数据分组，可以从一定程度上减少分组传输的时延。但是， 数据分组不能太大。 当然，如果中间节点收到路由请求分组并根据它的路由缓存 发送分组，就会丢弃捎带的数据分组。 为了避免这种情况， 中间节点在丢弃 RREP 分组之前， 必须重新构造数据分组。 而且数据分组的路由分为两段： 前一段来自 RREQ分组的路由记录部分，后一段来自路由缓存，而且，该数据分组的源节点 为启动路由建立的节点。2.2.2 AODV 协议同 DSR 协议一样， AODV 协议也是一种按需路由协议，它根据业务需求建 立和维护路由。

24、 AODV 协议是由 DSDV 协议算法发展而来，它应用传统的路由 表。 AODV 路由协议的路由发现和维护过程与 DSR 路由类似。不同的是 AODV 路由协议中，路由中的每个节点都必须维护路由表。 AODV 在每个中间节点中 隐式保存了路由请求和回答的结果，而 DSR 将结果显式保存在路由请求和路由 回答分组中。 AODV 路由的分组无需包含完整的路径信息，采用逐跳转发的方 式，从而减小了分组开销 4 。为了找到通往目的节点的路由，源节点将广播一个RREQ分组，收到RREQ 分组的中间节点根据RREQ中的信息，建立到源节点的路由，称为“反向路由”。 反向路由条目的目的节点是广播 RREQ

25、的源节点，下一跳节点是将 RREQ 发送 给本节点的邻节点，然后它向周围节点广播次分组。如果目的节点收到 RREQ 则向源节点回复RREP。RREP沿着刚建立的反向路由向源节点传送，在此过程 中，收到RREP的节点建立到目的节点的路由，称为“正向路由”。正向路由条 目的目的节点是RREP分组的源节点，下一跳是将RREP发送给本节点的邻节点。 路由协议只维护那些正在使用的路由， 而不在激活路由上的节点的移动并不影响 该路由。 AODV 协议设计了两种路由维护方式：源节点路由重建和本地修复。AODV 协议的一个重要特征是在每个节点中的每个路由条目包含了一个计时器，如果一段时间一条路由条目没有使用，

26、则路由条目过期4。 AODV 协议是 DSDV 协议和 DSR 协议的结合，它使用 DSDV 协议中的“目的节点序列号” 防止缓存的路由信息过期以及环路的产生，路由建立是基于 DSR 协议中所采用 的方法，不同点在于 AODV 协议是逐跳路由而不是源路由。2.2.3 ABR 协议ABR 协议是从路由的有效时间的角度来设计， 采用路径有效时间的长短 （稳 定性）而不是路径长短，作为选路的标准。该协议由以下 3个部分组成：路由建立阶段、路由重建阶段和路由删除阶段。 它明确提出使用邻节点空间、 时间、连接和功率特点来构建一条生存时间长的路 由。如果在下一时刻由于节点的移动或电量缺乏而使路径中断， 那

27、么即使路由条 数少，也意义不大。因此，在自组网中，应当要求路由可以持续较长一段时间， 最好持续到一个连接结束。另外， ABR 协议是源始发协议，意味着不需要周期 的路由更新，也不需等待路由收敛，自然地克服了表驱动协议的暂时环路现象。 ABR 协议不使用路由缓存，因为维护这些缓存信息的有效性将占用大量的控制 开销。2.2.4 TORA 协议TORA 协议是基于“逆向链路”算法的路由协议，是具有高度的自适应性的 分布式路由算法。 它既不是距离矢量路由算法， 也不是链路状态路由算法。 它能 提供原节点到目的节点的多条路由， 当拓扑发生变化时， 它可以把控制信息限制 在拓扑变化点的一个很小范围内，从而

28、降低开销 5。TORA 协议具有 3 个阶段：路由建立阶段、路由维护阶段和路由消除阶段。 路由建立和维护采用“高度”作为度量标准来建立有向无回图（ DAG ），路由创 建由QRY （查询）和UPD（更新）两个控制分组完成。路由维护是在节点检测到 链路失败时，采用部分链路翻转算法，保证路由正确性维护以目的节点为根的 DAG的过程。在路由清除过程中节点广播 CLR命令，清除无效路由。该算法的 缺点在于会产生类似于距离矢量算法中计数之无穷的问题， 有在网络中产生振荡 的隐患。3. DSR 协议与 AODV 协议的比较这两种按需路由协议拥有显著的共同点， 他们都是只有当数据分组缺少到目 的节点的路由时

29、才启动路由发现过程， 这个过程中都是采用问询与应答机制， 并 且路由所经的节点都保存路由信息只是一个在路由表中（AODV）另一个保存在cache中（DSR）。然而，两者还有很大的区别，这些区别使得两者的性能有很大 的不同，下面简述两者的主要区别：第一，借助于源路由， DSR 需要存储比 AODV 多许多的路由信息 4。在 DSR 中，应用这种简单的请求 -应答机制，源节点可以得到去目的节点的路径中 的每一个中间节点的路由， 每一个中间节点也可以得到这条路径上到其他节点的 路由。允许侦听传输数据分组也使 DSR协议获得大量的路由信息。特别是，它 可以获得数据分组所携带的源路由上的到所有节点的路由

30、 。因为没有源路由与 允许侦听机制， AODV 协议只能获得有限的路由信息。特别是，因为路由发现 的方法有限，这使得 AODV 与 DSR 相比更依赖泛洪法，这造成了网络负荷的增 加。第二，为了更有效地运用路由隐藏，通过简单的问询机制， DSR 会应答所 有到目的节点的问询。 因此，源路由得到了许多不同的到目的节点的路由， 在最 短路由失效时，这些后备路由是很有用的。缓存的很多次佳路由使得 DSR 不容 易产生请求泛滥， 而这恰恰是协议性能中的一个瓶颈， 然而，这有可能造成应答 分组泛滥。另一方面，在 AODV 协议中，目的节点只对首先到达的请求分组予 以应答而忽略而后到达的请求分组。 存储的

31、路由表中至多一个目的节点有一个下 一跳节点。第三，现在的 DSR 协议没有包含任何详尽的机制来解决 cache 中的过期路 由问题，或是当有多种路由选择时如何选择更新的路由问题。 一旦使用了陈旧的 路由，将会是其他节点的cache中也存在过期路由。虽然一些过期路由会被路由 错误分组所清除， 但是由于允许侦听机制及节点的移动性， 会有比之被清除的路 由更多的cache中保存过期路由。相对而言，AODV有一个更加保守的方法。当 有两种路由选择时， 基于目的节点序列号的更新的路由会被启用。 而且，若一个 路由条目在一段时间内没有使用， 则该条目过期， 会被删除。 但这第二种方法不 是没有问题的，因为

32、一个有效路由可能因为一段时间没有被使用而超时被删除。 因为源节点的发送速率大不相同， 节点的移动性不确定并常动态改变， 如何决定 一个合适的过期时间是很困难的。第四，在AODV中，运用RRER分组来删除路由也是较保守的。经由之前 建立的路径，一个 RRER 分组会到达所有包含此中断链路的目的节点。然而， 在DSR中，一个RRER分组简单地沿着数据分组的路径原路返回，但是那些虽 然也应用该失败链路作为路径但不在数据分组路由中的节点将不能被迅速通知 4。我们做以下仿真的目的就是想确定用更积极的源路由和 DSR 中的 caching 还是采用更保守一些的路由表和 AODV 中的序列号驱动方法。我们想

33、找出两者 彼此相对的优势。4. 仿真部分OPNET 最早是在 1986 年由麻省理工大学的两个博士创建的， 并发现网 络模拟非常有价值，因此于1987年建立了商业化的OPNET。OPNET近几年赢 得的大量奖项是对其在网络仿真中所采用的精确模拟方式及其呈现结果的充分 肯定。在 OPNET 各种产品中， Modeler 几乎包含其他产品的功能，针对不同的 领域，它表现出不同的用途。我们应用 OPNET 软件配置一个如下图所示的 50 节点的网络。利用配 置不同的节点属性，得到在同样的网络拓扑下两种不同的按需路由协议 DSR 和 AODV 的不同的协议性能。这是一个典型的网络模型，在仿真路由协议时，如 果要了解封包是否到达， 不必要每隔很短时间去周期性地查看一次， 而是收到封 包，事件到达才去看。每一时刻， FSM 将停留在特定状态，之后收到事件，完 成事件并跳转状态。 路由协议要做的事有获取周边节点地址， 建立拓扑信息， 之 后路由表稳定下来， 在收到封包将其转发到下一个节点， 这些事件中断将引起相 应的状态转移。我们仿真时间 1 小时，随机数种子 128，其他参数不变。