-
Ad Hoc<
/p>
网络及
QOS
支持
2.2 Ad
Hoc
网络的路由协议
2.2.1
现有的
Ad
Hoc
网络路由协议分类
由上可知，由于
Ad
Hoc
网络具有节点节电、减少带宽消耗、拓扑快速更新、
<
/p>
适应单向信道环境等这些特殊要求，现有的
IP
< br>路由协议，如
RIP(
路由选择信
息协议
)
和
OSPF(
开放最短路径优先协议
)
等基于固定设备的协议设计思想不
能满足以上要求，
Ad Ho
。网络路
由协议的设计具有很大难度。
IETF
的
MANET
工作组重点研究
Ad Hoc
< br>网络中的路由协议
flgl
。目前工作组已经提出了许多
协议
草案，比如
DSDV(
目标序列距离路由矢量算法
)
、
DSR(
动态源路由协议
)
、
AODV (Ad Hoc
网络的距
离矢量路由算法
)
、
TORA(
临时顺序路由算法
)
等。此
< br>
外，研究人员还发表了许多关于
Ad
Hoc
网络路由协议的学术论文，比如
wRp[191.
LAR[zol, ZHLS[21]
等。这些路由协议根据不
同的标准可以进行不同的分类，弄清
协议的分类对掌握协议的优缺点有重要意义。
从协议中节点的逻辑角度和节点在协议过程中的地位作用划分，可以分为
平面路由协议和分级路由协议。
1.
平面
(flat)
路由协议
:
在平面路由协议中，网络中的所有节点在形成和
维护路由享有对等的权利和义务，即路由协议中节点的逻辑视
图是平面结构，
结点的地位是平等的，不存在某些节点具有特
殊用途。这类协议的优点是不存
在特殊节点，路由协议的鲁棒
性较好，通信流量以及路由负载较为均衡的分布
在网络中。其
缺点是缺乏可扩展性，只适用于节点规模较小的
Ad
Ho
。网络。
2.<
/p>
分级
(hierarchical)
路由
协议
:
分级路由协议中，网络由多个簇组成，
< br>
因而节点分为普通节点和簇头节点。处于同一簇的簇头节点和普通节点共同维<
/p>
护所在簇内部的路由信息，簇头节点负责所管辖簇的拓扑信息的
摘要处理，并
与其他簇头节点互换处理后的拓扑信息【
’“]
。采用分簇思想主要有两个目的
:
一
是通过减少参与路由计算的节点数目，
缩小路由交换的范围，从而减小节点维
护路由表的大小，降低
交换路由信息所需的通信开销和维护路由表所需的内存
开销，
这与有线网络中层次思想的目标是一致的
;
二是基于某种簇形式
策略，
选举形成一个较为稳定的子网络，减少拓扑结构变化对
路由协议带来的冲击。
此类路由的优点是可扩展性较好，适用
组建规模较大的网络
;
缺点是簇头节点
的选举算法的收敛性、可靠性和稳定性对协议性能影响较大。
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
的主要设计思想包括两个方面
:
一是路由表
的维护更新，每个节点需要维护更新的表项内容包括信宿地址、路
由度量值和
序列号
;
二是信息通告机制采用周期性向邻居节点通告路由表的方法，减小了
路由通告的范围，从一定程度上避免了路由广播风暴
;
< br>三是链路断开度量值计
数为无穷
;
四是路由选择以序列号最新和度量值最小为标准。为了进一步减少
< br>
路由开销，
DSDV
中使用了
两类更新分组
:“
完全转存
”(ful
l damp)
分组和
“
递
增更新
”(incremental
update)
分组。前者包括了节点当前路由表表项的所有内
容，一般需要多个分组进行传输，消耗大，适用于移动频繁的
A
d Hoc
网络
;
后
< br>
者仅仅包括上一次
“
完全转存
”
分组交换后发生了变化的表项内容，一般要求一个
分组传输，其发送的依据为度量值的变化，适用于移动较为平静的
Ad Hoc
网络。
就
QOS
而言，由于
DSDV
的协议较早，根本没有加入对
QOS
的考虑。
2.
DSR
动态源路由协议
(Dynamic
Source Routing,
DSR)
是一种源路由的按需驱动
路
由协议，它使用源路由算法。信源节点送往信宿节点的数据包包头都显式包
含该数据包途径的中间节点序列信息，故称为源路由算法。网络中每一个节点
需要维护一个到已知信宿节点的路由表，并当发现新的路由时就更新该路由表。
DSR
的优点在于中间节点不需要保留路
由信息，不适用周期性的路由通告，协
议开销较小
;
同时信源节点使用路由缓存技术减少了路由发现的开销。
DSR
是
一种典型的被动式
路山算法，主要包含两个过程
:
路由发现和路由维护。路由
2 Ad Hoc
网络及
QOS
支持
发现过程，使用
了
ID
唯一的路由请求分组
(RREQ
)
来发起路由请求，响应请
求的中间
节点把自己的节点信息加入路由记录选项，而完整的路径信息则使用
< br>路由回复分组
(RREP)
来通告给信源节点。路由维护
过程的过程也是按需的，
即只有节点之间有数据通信时才进行
检测路径是否可用，检测通常采用点到点
和端到端的双保险机
制。
DSR
的缺点在于
:
由于每个数据包的头部都需要携带
路由信息，数据
包的额外开销较大
;RREQ
消息采用泛洪方式，广播风暴和重
复
广播从一定程度上增加了网络的负担
;
由于缓存路由会导致路由过期失效从而
< br>影响路由选择的准确性。另外，对
QOS
支持上，
DSR
只是提供一种尽力而为的
服务，没有加入对服务质量的考虑。
kn-AODV
< br>协议的
NS-2
仿真
5 kn-AODV
协议的
NS-2<
/p>
仿真
为了验证改进后算法的有效性，本
章将利用网络仿真软件
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<
/p>
句
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
等
;
路由协议