发布时间 : 星期日 文章Ad Hoc网络及QOS支持更新完毕开始阅读ea14505e3169a4517723a3c4
Ad Hoc网络及QOS支持 2.2 Ad Hoc网络的路由协议
2.2.1现有的Ad Hoc网络路由协议分类
由上可知，由于Ad Hoc网络具有节点节电、减少带宽消耗、拓扑快速更新、 适应单向信道环境等这些特殊要求，现有的IP路由协议，如RIP(路由选择信 息协议)和OSPF(开放最短路径优先协议)等基于固定设备的协议设计思想不
能满足以上要求，Ad Ho。网络路由协议的设计具有很大难度。IETF的MANET 工作组重点研究Ad Hoc网络中的路由协议flgl。目前工作组已经提出了许多协议 草案，比如DSDV(目标序列距离路由矢量算法)、DSR(动态源路由协议)、 AODV (Ad Hoc网络的距离矢量路由算法)、TORA(临时顺序路由算法)等。此
外，研究人员还发表了许多关于Ad Hoc网络路由协议的学术论文，比如wRp[191. LAR[zol, ZHLS[21]等。这些路由协议根据不同的标准可以进行不同的分类，弄清 协议的分类对掌握协议的优缺点有重要意义。
从协议中节点的逻辑角度和节点在协议过程中的地位作用划分，可以分为 平面路由协议和分级路由协议。
1.平面(flat)路由协议:在平面路由协议中，网络中的所有节点在形成和 维护路由享有对等的权利和义务，即路由协议中节点的逻辑视图是平面结构， 结点的地位是平等的，不存在某些节点具有特殊用途。这类协议的优点是不存 在特殊节点，路由协议的鲁棒性较好，通信流量以及路由负载较为均衡的分布 在网络中。其缺点是缺乏可扩展性，只适用于节点规模较小的Ad Ho。网络。 2.分级(hierarchical)路由协议:分级路由协议中，网络由多个簇组成，
因而节点分为普通节点和簇头节点。处于同一簇的簇头节点和普通节点共同维 护所在簇内部的路由信息，簇头节点负责所管辖簇的拓扑信息的摘要处理，并 与其他簇头节点互换处理后的拓扑信息【’“]。采用分簇思想主要有两个目的:一 是通过减少参与路由计算的节点数目，缩小路由交换的范围，从而减小节点维 护路由表的大小，降低交换路由信息所需的通信开销和维护路由表所需的内存 开销，这与有线网络中层次思想的目标是一致的;二是基于某种簇形式策略， 选举形成一个较为稳定的子网络，减少拓扑结构变化对路由协议带来的冲击。 此类路由的优点是可扩展性较好，适用组建规模较大的网络;缺点是簇头节点 的选举算法的收敛性、可靠性和稳定性对协议性能影响较大。
2 Ad Ho。网络及QOS支持
国内外学者的关注点都放在平面路由协议研究上，己经被IETF公布的协议 草案也大多数属于平面路由协议，一是因为大多数的协议只是停留在实验模拟 阶段，往往实验对象的网络规模较小;二是平面路由协议无需考虑加入额外的 算法，可以使研究者更多关注于协议算法本身的实现。
从另一个方面，按协议的工作方式(主要是指路由发现的策略)划分，可 将相关协议分为主动路由协议、被动路由协议和混合路由协议。 1.主动(proactive)路由协议
主动路由的路由发现策略与有线网络中RIP路由协议类似，各节点通过周 期性地广播路由信息分组，主动交换路由信息，维护更新路由。同样的，节点 必须维护去往全网所有结点的路由。它的优点是当信源节点有发送数据分组请 求时，只需从本地维护的路由表项中查找出到信宿节点的路由信息，所需的路 由延时很小;缺点是主动路由协议路由花销开销很大，节点广播路由信息对网 络的带宽资源浪费较大;此外该类协议不能及时动态反应网络拓扑结构的变化， 存在无效路由。常见的主动式路由协议有WRP, DSDV, STARA[22]等。 2.被动(reactive)路由协议
被动路由协议的设计思想借鉴了有线局域网网桥设计思路。与主动路由相 反，被动路由既不需要定时地全网广播路由信息，也不需要维护全网所有节点 的路由信息，仅在信源结点有分组要发送但没有相应节点路由时，才进行路由 查找发现更新。它的优点是不需要周期性的路由信息广播，节省了宝贵的带宽 资源;缺点是数据分组因为路由发现而引起的等待时延较大。此类路由协议通 常分为路由发现和维护两个过程。当信源结点发现没有去往目的结点的路由时， 从信源节点开始触发路由发现过程，而在数据分组发送过程中节点只是保持一 种路由维护的过程，直至数据发送完毕或者路由失效而触发新的路由发现过程。 常见的被动式路由协议有AODV, DSR, TORAo 3.混合(h沙rid)路由协议
混合路由协议是一类混合使用以上两种路由发现策略的协议，从一定意义 上讲是两类路由发现策略的折中。此类协议在网络小范围内采用主动路由协议 以维护局部准确的路由消息，而在范围之外采用被动路由协议以减少路由开销。 比较著名的协议有ZRP[23], CEDAR[\等。
Ad Hoc网络设计之初，考虑到网络规模小，通信数据少，学者最早关注于 主动路由协议，随着Ad Hoc网络的应用深入，网络规模扩大，通信数据猛增， 2 Ad Hoc网络及QOS支持
从尽可能的见地路由开销角度考虑，大多数学者关于被动式路由协议。而混合 路由协议则更多适用于超大型的Ad Ho。网络。 2.2.2经典的Ad Hoc网络路由协议
Ad Hoc网络从产生发展到现在，国内外学者可谓各显神通，其中不乏涌现 一些经典的路由协议，成为其他研究者竞相研究的对象: 1 .DSDV
目标距离矢量算法(destination sequenced distance vector, DSDV)是一种基 于路由表项驱动的主动路由协议，核心算法借鉴了Bellman-Ford算法并做了相 应的改进。它被认为是最早的Ad Hoc网络路由协议。它的主要特点是采用了序 列号作为路由新旧与否的标志，避免了路由环路和跳计数无穷的问题。它的缺 点是不适应拓扑变化快的Ad Hoc网络，并且不支持单向信道。作为随后出现的 AODV继承了它的优缺点。DSDV的主要设计思想包括两个方面:一是路由表 的维护更新，每个节点需要维护更新的表项内容包括信宿地址、路由度量值和 序列号;二是信息通告机制采用周期性向邻居节点通告路由表的方法，减小了 路由通告的范围，从一定程度上避免了路由广播风暴;三是链路断开度量值计 数为无穷;四是路由选择以序列号最新和度量值最小为标准。为了进一步减少 路由开销，DSDV中使用了两类更新分组:“完全转存”(full damp)分组和“递 增更新”(incremental update)分组。前者包括了节点当前路由表表项的所有内 容，一般需要多个分组进行传输，消耗大，适用于移动频繁的Ad Hoc网络;后
者仅仅包括上一次“完全转存”分组交换后发生了变化的表项内容，一般要求一个 分组传输，其发送的依据为度量值的变化，适用于移动较为平静的Ad Hoc网络。 就QOS而言，由于DSDV的协议较早，根本没有加入对QOS的考虑。 2. DSR
动态源路由协议(Dynamic Source Routing, DSR)是一种源路由的按需驱动 路由协议，它使用源路由算法。信源节点送往信宿节点的数据包包头都显式包 含该数据包途径的中间节点序列信息，故称为源路由算法。网络中每一个节点 需要维护一个到已知信宿节点的路由表，并当发现新的路由时就更新该路由表。 DSR的优点在于中间节点不需要保留路由信息，不适用周期性的路由通告，协 议开销较小;同时信源节点使用路由缓存技术减少了路由发现的开销。DSR是 一种典型的被动式路山算法，主要包含两个过程:路由发现和路由维护。路由 2 Ad Hoc网络及QOS支持
发现过程，使用了ID唯一的路由请求分组(RREQ)来发起路由请求，响应请 求的中间节点把自己的节点信息加入路由记录选项，而完整的路径信息则使用 路由回复分组(RREP)来通告给信源节点。路由维护过程的过程也是按需的， 即只有节点之间有数据通信时才进行检测路径是否可用，检测通常采用点到点 和端到端的双保险机制。DSR的缺点在于:由于每个数据包的头部都需要携带 路由信息，数据包的额外开销较大;RREQ消息采用泛洪方式，广播风暴和重复 广播从一定程度上增加了网络的负担;由于缓存路由会导致路由过期失效从而 影响路由选择的准确性。另外，对QOS支持上，DSR只是提供一种尽力而为的 服务，没有加入对服务质量的考虑。
kn-AODV协议的NS-2仿真 5 kn-AODV协议的NS-2仿真
为了验证改进后算法的有效性，本章将利用网络仿真软件NS-2对改进的关 节点AODV (kn-AODV)的协议性能展开分析，并从实验结果角度与原协议 AODV做了对比分析。 5.1 NS-2仿真软件概述 5.1.1 NS-2仿真软件介绍
本文使用NS-2 (network simulator version 2) E41]作为对协议的仿真实验的工 具。它是面向对象的、离散事件驱动的网络仿真器，由UC Berkeley研发底层的 C++核心构架，同时结合了麻省理工学院发明的对象工具语言(O句ect Tool Command Language OTcI)作为仿真程序的命令与配置接口。而OTcl语言是 Tcl语言(Tool Command Language)的面向对象的版本，真正实现协议仿真的 场景则需要编写Tcl脚本文件。Tcl语言具有通俗易懂的特点，使NS-2的初学 者能够顺利入门，因此为国内外许多研究学者所青睐。NS-2实现的网络结构模 型功能有:传输层协议模型，如TCP, UDP等;业务源模型，如FTP, Telnet, Web, CBR及VBR等;路由器队列管理机制，如DorpTail, RED等;路由协议
算法，如OSFP, RIP等。此外，NS-2还能加入了对无线网络模型的模拟仿真。 总体来说，使用NS-2仿真的基本步骤如下:
1.开始编写TCL (*.tcl )脚本文件，主要完成仿真网络的有关参数的设置。 文件中参数配置包含:仿真网络拓扑结构，节点数目，业务源的类型及其相关 参数，协议代理机制等。
2.设置Trace对象，这个过程也被程序化包含进TCL脚本文件中，主要设 置相关研究感兴趣的数据跟踪对象。NS通过Trace文件((*.tr文件)来保存整个 仿真过程中有用的数据，这是研究分析数据的直接材料来源。
3.编写其它的辅助过程，主要是TCL的主程序模块及相关子函数的调用设 定，包括设定仿真结束时间，并且调用跟踪对象。至此TCL脚本文件编写完成。 kn-AODV协议的NS一仿真
4.用NS解释执行刚才编写的TCL脚本文件。
5.借鉴NS已有的分析工具或者用shell命令自行编写分析文件进行实验结 果数据筛选、处理、分析，得出有用的或者定量的数据。
6.调整配置节点拓扑结构和业务量模型，一般通过修改TCL文件中的相关 参数完成。重新进行上述仿真过程。 5.1.2 NS-2无线移动仿真模型介绍
无线移动模型最初是卡内基一梅隆大学(CMU)的Monarch小组开发的对 NS-2的移动扩展模型[E123. CMU小组扩展了仿真平台的物理层、链路层和网络 层，如物理层的无线信号传输模型(radio propagation model )、全向天线 ( Omni-directional antenna)、共享媒介的网络接口(shared media network
interface);数据链路层的IEEE 802.系列中基于分布式协调功能DCF (Distributed Coordination Function)的MAC协议及其扩展、无线地址解析协议ARP (Address Resolution Protocol);网络层的无线路由协议DSDV, DSR等。此外还有附带 专门用于生成随机场景的软件工具包，场景生成文件规定了场景范围、移动节 点的数量、移动或静止时间、移动速度和移动方向等。使用这些扩展功能可以 对无线LAN、移动IP以及 Ad Hoc网络进行细致精确的仿真。
对于无线仿真模型，实现一次成功的仿真实验，可以从以下四个方面入手: 1.节点模型
节点模型如图5.1所示[[16]。在仿真环境中，无线网络的每个节点都是一个独 立的对象实体，这就是从实际网络构建抽象出来的节点模型。节点模型框架有 助于研究者弄清楚关注点所在的网络模型的层次及其关联模块。移动节点模型 由一系列网络构件组成，这些构件包括逻辑链路层LL、地址解析协议模块ARP, 接口队列I匆、媒介接入控制层MAC、网络接口Net IF.
当然作为本文的研究重点可能更多关注于路由协议，那么就要关注路由代 理模块。事实上在NS-2中路由代理RTagent类是继生上层的agent类而来，因 此在修改子类代码的时候要考虑父类代码的一致性。另外这个节点模型也指出 了路由代理模型与逻辑链路层LL的依赖关系，这在研究跨层次的协议设计时需 要做考虑。 2.运动模型
节点的运动采用‘`Random Waypoint”模型[[43]，它的两个特征参数是停顿时间