自组网路由协议综述

2(X) l年 11 月 第 2 2 卷 第 11 期 通 信 学 报 JO U R N A L O F CH IN A IN ST I ~ fU T E O F C OMMU N IC A I , IO N S V 0 I2 2 N O . II N o v Z《刃 l )、叭 、、、、、.、叭叭、玲 { 综 述 ;乡卜 , 入 , 卜 , 、 , 、 , 卜 , 、 , 之 自组网路由协议综述 史美林 , 英 春 (清华大学 计算机科学与技术系 . 北京 l州X〕8 4) 摘 要 : ·自组网路由协议用于监控网络拓扑结构变化 , 交换路由信息 , 定位 目的节点位置 , 产 生 、 维护和选择路由 , 并根据选择的路由转发数据 。 本文综述了自组网路由协议研究方面的一 些最新工作 , 描述了设计 自组网路由协议所面临的问题 , 并着重对该研究开展以来所提出的各 种主要路由协议进行了对比 、 分析和分类阐述 , 为进一步的研究提出了新的课题 。 关键词 : 自组网 ; 路由协议 ; 移动计算 中图分类号 : 即393 .4 文献标识码 : A 文章编号 : 10 00 一4 36 X (2 00 1) 11 一00 93 一 11 R o u tin g p r o to e o ls fo r a d h o e n etw o rk s : a s u rv e y SH IM e i 一 L in , Y IN G C hu n (D ePart m e n t o f C o m Pu te r s e ie n e e a n d Te c h n o lo g y , Ts in g h u a U n iv ers ity 、 B eij in g l《M刃 84 . C hin a) A b st ra e t: Th e ro u tin g Pro to e o ls in a d hoc n e tw o rk s a re u se d to mo n ito r n e tw o rk to Po lo g y , d istri bu te th is in fo rma tio n fo r u s e in ro u te e o n stru e tio n , lo ca te se s sio n e n dPo in ts , e o n s tru e t an d se le e t ro u te s , an d fo rw a rd tr a ffi c ac eo rd in g to th e s el e ct ed ro u te s . Th i s Pap e r m ak e s a su rv ey of th e re ee nt w o rk s ab o u t ro u tin g Pro to e o ls fo r ad h o c n e tw o rk s . Firs t , th is Pap e r Pre se n ts a u n iqu e se t o f c h a lle n g e s th a t d iffe r fro m tra d iti o n a l w ire le ss syste m s a n d w ired n e tw o rk s . Th e n , it d e seri be s th e Pri n eiPle s an d e o mP are s th e 51而 lari ti e s an d di ffe re n e e s o f s o m e m a in ro u tin g Pro to c o ls th a tar e Pro Po se d in th e lite ratu re · A t th e e n d of th is Pa Pe r, re searc h d ire e tio n s a n d op e n Pro b le m s in th e are a are a ls o d is e u s se d · 心y仙r ds : a d ho e n etw o rk s ; ro u ti n g Pro to e o ls ; m o b ile c o m Pu tin g 1 引言 自组网 (ad hoc ne tw or k) 是指一组带有无线收发装置的移动节点组成的一个多跳的临 时性的自治系统 【’一 , l。 在这种环境中 , 由于节点的无线通信覆盖范围有限 , 两个无法直接通 信的移动节点可以借助其他节点进行分组转发实现数据通信 。 与其他移动通信网络相 比 , 它 收稿日期 : 2 00 1 一0 2 一26 ; 修订日期 : 2 (X) l一0 6 一3 0 作者简介 : 史美林 (1 9 38一 ) , 男 , 浙江余姚人 , 清华大学教授 , 博士生导师 , 主要从事计算机网络及其应 用 、 计算机支持的协同工作 C SCW 等方面的研究工作 : 英春 ( 1973 一 ) , 男 , 四川成都人 , 博士 , 主要从 事移动计算、 计算机网络路由协议等方面的研究工作。 通 信 学 报 200 1年 不需要固定基站支持 , 具有网络自组性 、 动态变化的网络拓扑结构 、 存在单向的无线信道等 特点 , 主要用于军事战术通信 、 应急通信 、 协同移动通信 、 无线接入系统和传感器网络 。 与单跳的无线网络不同 , 自组 网节点之间是通过多跳数据转发机制进行数据交换 , 需 要路由协议进行分组转发决策 。 无线信道变化的不规则性 、 节点的移动 、 加入 、 退出等也会 引起网络拓扑结构的动态变化 。 路由协议的作用就是在这种环境中 , 监控网络拓扑结构变化 , 交换路由信息 , 定位目的节点位置 , 产生 、 维护和选择路由 , 并根据选择的路由转发数据 , 提供网络的连通性 。 它是移动节点互相通信的基础 , 因此成为当前自组网体系结构中的研究 热点 。 IE TF 于 19 % 年成立了自组网工作小组 (MA N E T w G ) , 其 目前的核心任务就是研究 自组网环境下基于 IP 协议的路由协议和接口设计川 。 本文将对当前自组 网路由协议研究进行分析和综述 , 第 2 节描述设计 自组 网路 由协议 所面临的问题 , 第 3 节着重分类阐述各种主要路由协议的设计思路和特点 , 第 4 节通过对比 和分析指出新的研究方向 , 最后是本文的结束语 。 2 面临的问题和挑战 常规路 由协议主 要采用 两种形式的路 由思想 : 距离 一 向量算法 (di sta nc e a lgori th m , D v^ ) 14 , 5 ]和链路一状态算法 (lin k stat e al g o ri th m , L S^ ) 161。 但是 , LsA 和 n v^ 都不适合在 自组网环境中运行 。 这是因为自组网的特性为路 由协议的设计提出了新的问题和 挑战 , 主要有以下几点 : 动态变化的网络拓扑结构 动态变化的拓扑结构是 自组 网最显著特点 。 在自组 网中直 接运行常规路由协议 , 当拓扑结构变化后 , 常规路由协议需要花费很长的时间和较大的代价 才能到达收敛状态 。 单向信道的存在 常规路由协议通常认为底层 的通信信道是双 向的 。 但是在采用无线 通信的 自组 网环境中 , 由于发射功率或地理位置等因素的影响 , 可能存在单向信道 。 它为常 规路由协议带来三个严重的影响 : 认知的单向性 、 路由单向性和汇点不可达 171 。 有限的无线传输带宽 由于无线信道本身的物理特性 , 它所能提供的网络带宽相对有 线信道要低得多 。 此外 , 考虑到竞争共享无线信道产生的碰撞 、 信号衰减 、 噪音干扰 、 信道 间干扰等多种因素 , 节点可得到的实际带宽是远远小于理论上的最大带宽值 。 无线移动终端的局限性 移动终端在带来移动性 、 灵巧 、 轻便等好处的同时 , 其 固有 的特性 , 例如采用电池一类可耗尽能源提供电源 , 内存较小 , CPU 性能较低等 , 要求路由 算法简单有效 , 实现的程序代码短小精悍 , 需要考虑如何节省能源等 。 而常规路由协议通常 基于高性能路由器作为运行的硬件平台 , 没有上述的限制 。 3 协议分类和过程描述 目前 MA NE T W G 己经提出了许多协议草案 , 比如 D S R 、 A O D V 、 TO R A 、 ZRP 等 。 此 外 , 研究人员还发表了许多关于自组网路由协议的学术论文 , 比如 D sD v 、 w R p 、 sTA R A 等 。 这些自组网路由协议根据不同的角度可以进行不同的分类 。 根据路由发现策略的角度 , 可分为主动路由和按需路 由两种类型 。 1 1 主动路由 主动路 由的路由发现策略与传统路由协议类似 , 节点通过周期性地广播路由信息分组 , 交换路由信息 , 主动发现路由 。 同时 , 节点必须维护去往全网所有节点的路由 。 它的优点是 第 n 期 史美林等: 自组网路由协议综述 当节点需要发送数据分组时 , 只要去往 目的节点的路由存在 , 所需的延时很小 。 缺点是主动 路由需要花费较大开销 , 尽可能使得路由更新能够紧随当前拓扑结构的变化 。 然而 , 动态变 化的拓扑结构可能使得这些路由更新变成过时信息 , 路由协议始终处于不收敛状态 。 在自组网路由协议的研究初期 , 主要 思路是修改有线网络的路由协议以适应在自组网 环境中运行 。 这些路由协议大多属于主动路由 。 在下面的各种主动路由协议的过程描述中 , 将着重说明如何对传统路由协议的改进以适应自组网环境中运行 。 3 . 1 . 1 D S D V D so v I8 1 (d es ti n ati o n 一se q u e n e e d d ista n ee 一 v ee to r ) 协议是在 n VA 基础上进行改进设计的 。 它被认为是最早的自组网路由协议 。 D S D V 的特点是采用 了序列号机制用于区分路由的新 旧 程度 , 防止 D VA 可能产生的路由环路 。 它的缺点是不适应变化速度快的自组网 , 不支持单 向信道 。 3 。 l 。 2 百V R P w即[9 ] (w ire le ss r o u tin g p ro to eo l) 协议是在路径发现算法 l“,I p EA (pat h fi n d in g a lg o rith m ) 基础上改进设计的 。 PEA 与 D V A 不同 , 它利用去往目标节点的路径长度和相应路径的倒数 第二跳节点信息加速路 由协议收敛速度 , 改善 D V A 中路由环路问题 。 W RP 对 PFA 的改进 之处在于当节点 i 监测到与邻居节点 j 的链路发生变化时 , i 会检查所有邻居节点关于倒数 第二跳节点信息的一致性 , 而 P队 只会检查节点 j 关于倒数第二跳节点信息的一致性 。 这 种方式可 以进一步地减少出现路由环路的次数 , 加快算法的收敛速度 。 3 . 1 . 3 S T A R A s认R A t” l (sy ste m an d tr affi e d e p en d en t ad即tiv e r o u tin g alg o r ithm ) 协议采用最短路径算 法计算路径 , 但 “最短 ”路 由度量采用了平均延时时间 , 而不是常用的跳数 , 也就是说 STA R A 在进行分组路 由时 , 考虑了无线链路的容量和排队延时等因素 。 每个节点 i采用改进的端到 端确认协议为每一对源和 目的节点 (i, d) 计算平均延时 D气(t) , 方法如式 (l) 所示 。 其中 , 又 任田, l] , 为遗忘因子 , 用于调整历史延迟值和当前延迟值的权重关系 : k任 N , N 表示节点 i 一跳可以到达的所有邻居节点的集合 。 然后根据式 (2) 所示 , 将经过的交通流量分配给 不 同的邻居节点 , 目标是使得所有可用的路径具有相同的延时 。 需要特别指出的是 , 这种路 径平均延时估测机制并不需要双向信道和节点间的时钟同步的支持 。 D是(, )二 几‘ . D是(卜 l) (l) 尸昆(, ) = 夕段(, 一)+ a (r)· (D尸(; )一 D显(, )) (2) 3. 2 按需路由 与主动路由相反 , 按需路 由认为在动 态变化的 自组网环境中 , 没有必要维护去往其他 所有节点的路由 。 它仅在没有去往 目的节点路由的时候才 “按需 ” 进行路由发现t’2 ! 。 因此 , 拓扑结构和路由表内容是按需建立的 , 它可能仅仅是整个拓扑结构信息的一部分 。 它的优点 是不需要周期性的路由信息广播 , 节省了一定的网络资源 。 缺点是发送数据分组时 , 如果没 有去往 目的节点的路由 , 数据分组需要等待因路由发现引起的延时 。 按需路 由协议通常由路由发现和维护 两个过程组成 。 当源节点发现没有去往 目的节点 的路由时 , 触发路由发现过程 。 这个过程类似于有线网络 中建立电路连接的协商过程 。 图 1 通 信 学 报 2 00 1 年 是一个典型的路由请求过程 。 源节点 A 在 自组网中广播路由请求分组 , 邻居节点 B 和 F 收 到路由请求分组后 , 记录分组经过了该节点 , 然后继续转发 , 直到到达了 目的节点 E 。 节点 E 将会收到来 自两条不同路径的路由请求分组 , 每个路由请求分组中包含有相应的路径信 息 。 节点 E 根据一定的选择原则选取一条从源节点到目标节点的最优路径 , 并将该信息附 在向源节点 A 发送的路由回答分组中 , 作为对路由请求的响应 。 源节点 A 根据收到的路由 回答分组更新路由信息 , 从而获得去往 目的节点 E 的路由 。 当拓扑结构发生变化时 , 通过 路由维护过程删除失效路由 , 重新发起路由请求过程 。 路由维护通常依靠底层提供的链路失 效机制进行触发 。 路径 l : {^ 卫 ,c , D ,E ) 路径 2 {A. B , C , D } {A. B , C } {A. B } 图 l 按需路由请求示例 3 . 2 . 1 D S R D sRI ” l (dyn a而c so ur ee ro u ti n g ) 协议是最早采用按需路由思想的路由协议 。 它包括路 由发现和维护两个过程 , 协议操作与上节描述的过程基本一样 。 它的主要特点是使用 了源路 由机制进行分组转发 。 这种机制最初是 正E E 8 0 2. 5 协议用于在网桥互连的多个令牌环网中 节点寻找路由 。 D SR 协议借鉴了这种机制 , 并加入了按需思想而形成 。 D S R 的优点是中间节点不用维护去往全网所有节点的路由信息 , 而且可以避免出现路 由环路 。 它的缺点是每个数据分组都携带了路径信息 , 造成协议开销较大 。 而且也不适合网 络直径大的自组网 , 网络可扩展性不强 。 3 . 2 . 2 AO D V A o D V 泛’4 ] (ad ho c o n d e m an d d istan ee v e eto r ) 协议是在 D so v 协议基础上结合类似 o sR 中的按需路由机制进行改进后提出的 。 不同之处在于 A O D V 采用了逐跳转发分组方式 , 而 D S R 是源路由方式 。 因此 , A O D v 在每个中间节点隐式保存了路由请求和回答的结果 , 而 D S R 将结果显式保存在路由请求和路由回答分组中 。 此外 , A O D V 的另一个显著特点是它 加入 了组播路由协议扩展 , 并支持 Qo S 。 它的缺点是不支持单向信道 , 原因是 A O D v 协议 基于双向信道的假设工作 , 路由回答分组直接沿着路由请求的反方向回到源节点 。 3 一 2 一 3 T O R A To RA I”l(temP o ra lly 一 o rd e r ed ro u ti n g alg o ri thm )协议是在有向无环图 D A G (d ir ec ted ac yelie gr 叩hi 。 ) 算法l’“」的基础上提出的一种按需路由协议 。 它分为路由发现 、 路由维护和路由消 除三个过程 。 TO R A 的路由发现与其他按需路由协议一样 , 首先在网中扩散路由请求分组 。 但在路由回答中 , 采纳了 D A G 算法 。 其主要思想是 : 将每个节点分配一个相对于源节点的 “ 高度值 ” , 其中目的节点的 “ 高度值 ” 最低 , 并根据相邻节 点之间的 “ 高度值 ” 的比较从 而形成一条或多条的有向路径 , 方向是从 “高度值 ” 大的节点指向小的节点 。 从图论的角度 第 11 期 史美林等 : 自组网路由协议综述 来看 , 即为一棵根为目的节点的有向无环图 。 算法的具体实现是通过路由回答分组 (在 T O R A 协议中正式名称为更新分组 ) 在回到源节点的过程中完成的 。 为了在拓扑结构发生变化时能 够迅速重新生成路由 , 并将产生的协议分组限制只在受到影响的节点中扩散 , TO R A 协议仍 然采用上述算法重新构造失效的 D A G 。 T O R A 协议的缺点主要有 : 一是协议的有效运行依赖于网络的高连通度提供路由维护所 需的多条备选路径 ; 二是 T o RA 协议需要依靠 IME p l” ] (In te m e tM ANE T e n eaP su lat io n pr o to c o l) 协议提供邻居节点信息和底层可靠有序传输等功能 , CMU Mon are h 小组的仿真研究结果I’“} 表明 T O R A 协议开销 比其他按需路由协议大的主要原因在于使用 了 IME P 协议 ; 三是它也 不支持单向信道 。 3 . 2 . 4 LA R L A RI ’0l( fo cati on ai de d ro ut in g) 协议是一个基于预测节点当前位置算法的按需路由协议 。 它的目标是如何有效提高路由请求的效率 , 限制路由请求过程中被影响的节点数 目。 类似的 思想也已出现在移动蜂窝电话系统中选呼机制 (se lec tive p ag ing ) 中。 L A R 假设节点采用 G PS 系统获得位置信息 , 且每个节点都知道其他节点的平均运动速 度 。 路由请求时 , 源节点根据 目的节点历史位置和移动速度指定一个地理区域 : 请求范围 , 并将此信息附在路由请求分组中 。 LA R 规定只有位于请求范围内的中间节点才允许进行路 由请求分组的转发操作 , 从而减少了路由请求的影响范围。 当路 由请求失败时 , 源节点将扩 大请求范围 , 重新进行路由请求 。 LA R 的缺点是它必须依靠 G PS 系统才能正常工作 , 限制 了其应用范围。 1 3 集群路由 路由协议的设计思想和网络逻辑结构密切相关 。 从网络逻辑视图这个角度 , 路由协议 又可以分为平面结构和集群结构两种 。 平面路由协议中 , 逻辑视图是平面结构 , 节点的地位是平等的 。 优点是不存在特殊节 点 , 路由协议的鲁棒性较好 , 交通流量平均地分散在网络中 。 路由协议没有节点移动性管理 任务 。 缺点是缺乏可扩展性 , 限制了网络的规模 。 集群路由协议中 , 网络由多个集群组成 , 节点分为两种类型 : 普通和群首节点 。 处于 同一集群的群首节点和普通节点共同维护所在集群内部的路由信息 , 群首节点负责所管辖集 群的拓扑信息的压缩和摘要处理 , 并与其他群首节点交换处理过后的拓扑信息 。 层次结构就 是一种典型的集群方式 。 采用集群路 由主要有两个目的 。 一是通过减少参与路由计算的节点 数目 , 减小路由表尺寸 , 降低交换路由信息所需的通信开销和维护路由表所需的内存开销 , 这与有线网络中层次思想的 目标是一致的 。 二是基于某种集群形成策略 、 选举产生一个较为 稳定的子网络 , 减少拓扑结构变化对路由协议带来的影响 。 集群路由的优点是适合大规模的 自组网环境 , 可扩展性较好 。 缺点是群首节点的可靠性和稳定性对全网性能影响较大 , 并且 为支持节点在不 同集群之间漫游所进行的移动管理将产生一定的协议开销 。 已提出的自组网 路由协议大多数是基于平面路由思想 , 比如 3 . 1 和 3 . 2 节所描述的路由协议 。 其主要原因是 , 自组网 目前主要 以一种末端网络形式存在 , 应用规模都较小 , 使用集群思想 的作用不明显 。 这在一定程度上抑制了集群思想在自组网中的研究 。 下面将介绍三种典型的集群路由协议 , 并着重分析集群形成策略 。 3 . 3 。 1 CG S R C G S R I, 0 1 (e lu ste th e a d g a tew ay sw ite h ro u tin g ) 协议是在 D so v 协议基础上结合集群路 通 信 学 报 200 1 年 由机制设计的 。 e G sR 采用 Le e (le a st e lu ster e ha n g e ) 算法形成集群结构 。 为了尽量避免群 首节点的频繁更替 , 保障群首节点身份的稳定性 , LCC 规定 : 只在两个群首节点相互靠近 或一个节点离开所有群首节点的通信范围的两种情况下才会发生群首节点身份的变化 。 除了 群首节点外 , C G S R 还规定了其他两种类型的节点 。 一个群首的内部节点是指位于该群首的 无线通信范围内的节点。 网关节点则是指同时位于多个群首的无线通信范围之内的节点 。 当节点移动导致集群结构被破坏时 , CG S R 通过集群维护算法重新构造集群结构 。 在这 个过程中 , 一些节点会从当前集群转移到邻居集群 。 为了尽量减少转移节点的个数 , 它将具 有最多邻居数的节点和它的邻居保留在当前集群中。 节 点维护两种数据结构 : 集群成员表和路由表 , 前者描述了每个 目标节点所在集群的 群首 。 节点使用 D S D V 协议周期性地与邻居节点交换集群成员表 , 更新表项内容 。 当节点 需要发送一个分组时 , 首先在集群成员表中查找距离目的节点最近的群首 , 然后根据路由表 查找去往此群首的下一跳节点 。 3 . 3 . 2 CE D A R e E D ^ R I, ‘] (eo re e x tr ac 丘o n d istri b u te d 祖 h o e ro u ti n g ) 协议 目标是在自组网环境中构建一 个稳定的虚拟核心结构用于可靠有效地扩散路由信息 。 为了降低虚拟核心的变化程度 , 有必 要使得加入核心 的节 点数 目尽量 的少 。 图论中的 最小覆盖算法 MC D S1 2 2之 4] (而ni mu m co nn ec te d do 而n ati ng se ts) 可以满足这个要求 。 但是可以证明 MC D S 算法是一个 N 一P 完全 问题 , 只能基于确定性图灵机模型采用多项式时间近似算法得到 1221 。 C E D A R 采用 M C D S 近似算法将网络分为不同的域 , 每个域中仅包含一个属于 MC D S 的主域节点 , 其他节点都是主域节点的邻居节 点且不在 MC D S 中。 主域节点收集网络路由 信息 , 在 M C D S 中扩散 , 从而计算各个节点间的最短路由 。 采用 MC D S 的优点是当连接非主域节点之间的链路失效时 , MC D S 可 以立即充当备份 路由的作用 。 此外 MC D S 这种结构有利于支持广播和组播功能 。 缺点是随着网络规模增大 , 路由更新带来的协议开销急剧增加 , 可扩展性不好 。 3 一 3 一 3 Z R P z即[25 」 (z on e : ou ti ng Pr ot oc of ) 是第一个利用集群结构混合使用按需和主动路由策略的 自组网路由协议 。 Z R P 中 , 集群被称作域 (zo ne )。 域形成算法较为简单 , 它是通过一个重 要的协议参数一区域半径 (以跳数为单位 ) , 指定每个节点维护的区域大小 , 即所有距离不 超过区域半径的节点都属于该区域 。 一个节点可能同时从属于多个区域石 为了综合利用按需路由和主动路由的各自优点 , Z R P 规定每个节点采用 D V A 主动路由 协议维护去往区域内节点的路由 , 采用类似 D SR 协议中的按需路由机制寻找去往区域外节 点的路由 。 Z R P 协议的性能很大程度上 由区域半径参数值决定 。 通常 , 小的区域半径适合在移动 速度较快的节点组成的密集网络中使用 ; 大的区域半径适合在移动速度慢的节点组成的稀疏 网络中使用 。 目前 ZRP 采用预置固定区域半径值的做法 , 这无疑限制了它的可适应性 。 4 特点 比较分析 一个理想的自组 网的路由协议应 当满足以下七个方面的要求 : 分布式运行 、 提供无环 路由 、 按需进行协议操作 、 对单向信道的支持 、 提供节能策略 、 可扩展性 、 安全性 。 表 l 是根据上述要求对本文描述的 9 种自组网路由协议的特点进行的比较 。 其中 , 由 第 11 期 史美林等 : 自组网路由协议综述 于 Z RP 协议的主要贡献不在路由策略上 , 因此没有选择它 。 主动和按需 、 平面和集群 、 支 持单向信道 、 周期性路由更新以及分组转发机制等方面 己经分别在第 2 和第 3 节中进行了讨 论 , 此处不再赘述 。 表 1 自组网路由协议比较 分布式操作 是 是 是 是 无环路由 是 是 是 主动按播 主动 主动 主动 按需 按需 发送 H E LL O 分组 按需 按需 主动 按需 周期性 路由更新 维护 多条路由 是 是 支持 单囱链路 基于节省 能碑的策略 平面集群 平面 平面 平面 平面 平面 平面 平面 集群 集群 分组转发 逐跳 逐跳 逐跳 源路由 逐跳 逐跳 逐跳 逐跳 逐跳 安奎机制 路由度t 选择 最短 路径 最短 路径 平均延 时最小 的路径 最短 路径 最短 路径 最短 路径 最短 路径 最短 路径 最短 路径 存在 二 二 、 二 、 二 、 天 二特殊节点 泊 劝 一自 泊 一自 钧 一自 劝 一自 特殊硬件 否 双信道 G PS G PS 支特 否 组拱功能 加S 支持 否 分布式操作 对于集中式路由协议 , 通常存在一个中心节点 , 收集整个网络拓扑结构 , 计算全网的最短路由 , 并将结果分发到其他节点 。 这种机制难于适应动态变化的自组网 , 且 开销过大 。 其次 , 作为自组网的重要应用背景 , 军事通信系统要求很高的鲁棒性 , 所以上述 路由协议都采用了分布式运行方式 。 提供无环路由 它是路由协议应当具备的基本特征 。 路由协议主要通过 以下机制保证 通 信 学 报 2 00 1 年 这一点 : ¹ 使用由目的节点产生的路由序号机制 , 反映路由状态的新旧程度 , 例如 D S D V 、 AO D V ; º 使用路径发现算法 , 例如 W R P ; » 使用源路由机制 , 例如 D SR ; ¼使用面向目 标的 D A G 算法 , 例如 TO R A 。 维护多条路由 这种机制是指节点同时维护去往同一 目的节点的多条路由 , 只有当所 有路由都失效时 , 才按需发起路由请求过程 , 从而降低了路由请求频率 、 分组等待延时和协 议开销 。 它本质上是用高的内存复杂度换取低的通信复杂度 。 提供节省能源策略 大多数情况下 , 移动节点采用电池一类的可耗尽能源提供电源 。 然而要在几年内将 目前的电池可供电时间提高 30 %都是很困难的[26 l 。 上述路由协议都没有 提供节能策略 , 比如设备 “睡眠 ” 机制 。 这种策略的实现需要底层设备提供功能支持 。 此外 , 进入 “ 睡眠 ” 状态不能对路由协议的正常运行产生负作用 。 提供安全机制 路由协议是通过交换拓扑信息建立去往网中各个节点的路由。 攻击者 对这些没有受到保护的路由信息可进行各种形式的攻击 。 上述路由协议都没有考虑这个问题 的解决 。 可采用数据安全中各种加密机制 ( 比如数字签名 ) 防止来 自网络外部的攻击 。 但由 于 自组网内部节点可能被攻击者占领 , 并使用合法的私有密钥进行路由信息的数字签名 , 因 此必须对常规的安全机制进行改进以适应自组网的要求 。 路由度 t 选择 路由协议大多基于跳数作为度量尺度计算最短路由 。 只有 ST A R A 协议 是基于路径的平均延时进行路由选择 。 但是最短路由并不一定是最优路由 。 目前自组网的研 究中也提出了许多新的度量尺度 , 比如剩余电量最多的路由127 ! 、 位置最稳定的路由l28] 、 信 号强度最大的路由129 1等等 。 存在特殊节点 上述协议都假设所有的移动节点具有相 同的特性 , 如传输能力 、 电源 供给 。 尽管这在多数情形下的确如此 , 可也存在含有 “特殊 ” 节点的自组网环境 。 “特殊 ” 主要是指 : 节点具备充足的电源保障 、 无线高速收发设备 、 高性能的 CPU 等 。 特殊节点在 转发分组 、 收集路由信息等方面相对普通节点具有明显的优势 。 比如在由卫星节点和地面移 动节点组成的一个自组网中 , 卫星节点很容易获取地面节点的地理位置和移动轨迹 , 计算路 由表 , 并将结果发送到地面节点。 路由协议可以根据实际情况考虑如何有效利用特殊节点。 特殊硬件需求 某些路由协议需要特殊的硬件提供支持〔’5,J 9, 30] 。 比如 , TO R A 协议需要 G PS 设备提供全网节点的时间同步功能 , 并需要数据和控制两个独立无线信道 。 LA R 协议 要求 G PS 设备提供地理位置信息 。 在这些协议有效利用特殊硬件带来好处的同时 , 也限制 了它们 的应用范围 。 如在不具备 G PS 的环境中 , 或 G PS 功能失效时 , 这些协议都将无法正 常工作 。 支持组播功能 对 自组网的组播支持有着重要的意义 。 这是因为自组网的用户通常是 一个协同工作的群组 , 一对多的群组通信模式较为常见 。 此外组播分组传送过程中 , 发送节 点只需一次发送 , 可 以有效地利用无线信道带宽 。 然而现有的组播协议无法直接在自组网中 正常工作 。 这是因为: ¹ 大多数组播协议是依靠底层单播协议提供距离一 向量信息 , 采用逆 向路径转发机制建立和更新组播分发树 , 而拓扑结构的变化速度通常比底层的单播协议计算 路由的速度快 , 自然也比上层的组播协议的反应速度快 ; º 分发树通常需要一个全局的路由 结构 , 诸如链路状态或距离向量 , 节点的移动使得分发树结构更容易被破坏 , 并因此引发协 议进行节点间路由向量或链路状态表的频繁交换 , 产生额外的信道和处理开销 : » 大多数组 播协议是依靠超时和周期性发送 H ELL O 报文对底层链路连接状态进行监视 , 这与自组 网底 层协议完成的功能重复 , 效率不高 。 第 11 期 史美林等 : 自组网路由协议综述 Q OS 支持 自组网中的 QoS 支持问题是考虑如何动态地配置网络资源 , 使数据传输效 率更高 , 以及如何保障多媒体业务传输服务质量的问题 。 与单跳 、 蜂窝无线网络模型不同 , 自组网中节点之间需要多跳的无线连接 。 不仅要考虑单跳情况下的 Qos 保证 , 还要保证整 个无线多跳路径上的 Qo s 。 它面临着以下主要问题 : ¹ 网络资源受限 。 无线信道带宽较窄 , 信道质量不稳定且易受到干扰 , 后者可以通过使用更强的编码方法 、 提高信号发射功率 、 或 选择其它路径等方法解决 ; 然而 , 信道质量问题的解决通常会造成网络中的进一步拥塞 , 更 强的编码会导致带宽减少 , 选择其他路径会增加其他节点的负载 , 增大功率会增加分组碰撞 的概率 , 这些都会造成网络进一步拥塞 ; º 基于竞争机制的共享信道访问 , 存在 “ 隐藏终端 ” 、 “暴露终端 ” 和 “ 侵入终端 ” 13 ’一 3 3}等问题 ; 引入大量控制分组 的解决也不被 自组网所 接受 , 因为这会带来碰撞的增加 , 降低系统的整体效率 ; » 拓扑结构的动态变化给 QoS 支 持带来了很大困难 , 要消除或减轻拓扑结构变化对 Q o s 的影响需要 MA c 层的相应支持以 及底层路由协议能够快速生成新的路径 ; ¼移动节点不适宜像高速网络中骨干节点那样传输 大量的数据流 。 当传输的数据流都有 Q o S 需求时 , 无线信道带宽将很快饱和 。 从上述分析可看出 , 如何快速有效地适应拓扑结构的变化是自组网路由协议解决的主 要问题 。 提供无环路由和分布式运行是设计协议的基本要求 , 按需操作是多数协议的基本特 性 。 在满足了基本要求和特性的基础上 , 并能提供以下扩展特性的路由协议将有良好的发展 前景 : 节能策略 、 可扩展性 、 安全性 、 组播功能 、 QoS 支持 。 此外 , 建立模拟环境和实际 自组网试验床定量比较协议性能也是一个值得重视的问题 。 目前除了少数文献 L’“.34l 有路由协 议之间的性能比较 , 多数都是 同一个协议在不同网络条件下的自身比较 , 而且采用的模拟平 台软件也各不相同 , 因此其测试数据不具备横向可比较性 。 此外 , 网络场景的选择对协议的 性能影响也很大。 这里网络场景包括网络模拟范围、 节点个数 、 节点无线传输范围、 网络拓 扑结构变化速度 、 网络连通度 、 节点通信模式等参数 。 由于 CM U Mon arc hls sl,J 、组在 N S 模 拟平台l36] 基础上进行了扩展 , 支持四种主要自组 网路由协议 , 因此 目前 自组网工作小组推 荐采用 N S Z 作为路由协议测试的公共平台 , 并将设计一系列典型的网络场景用于评估协议 性能使用1371 。 这对我国深入研究自组网有着重要的作用 。 5 结论 本文综述了自组 网体系结构中占有重要地位的路由协议的研究 。 由于 自组 网的动态变 化的网络拓扑结构 、 单向信道的存在 以及有限的无线传输带宽等特点为 自组网路由协议的设 计带来了新的问题 。 文中列举了十种典型的 自组网路由协议 , 详细地描述了主要协议过程 , 分析比较了各自设计思路和解决策略 , 并在此基础上提出了一个理想的自组网路由协议应当 满足的七个要求 。 目前 , 自组网路由协议 的研究中还存在着许多堕待解决的问题 , 有待于进 一步深入研究 。 参考文献 : [l] [21 IE TE M o b ile a d h o e n e t w o rk s e h art e r 〔EB /0 L I . h ttP: // w w w je tr o rg/h tm l . e h art e rs / m a n e t 一e h a rt e 卜h tlnl . 19 9 9 一 0 7 一 31 . CO R S (〕N S , M A C K ER J . MOb ile a d h o e n e tw o rk i n g : ro u t in g Prot o e o l Pe rfo r m a n e e is s u e s a n d e v alu a tio n e o n sid e ra tio n s [E B jO L ] . h ttP: l/ w w w je tf o l创rfc /rfc 250 1. tx t , Ja n 199 9 . 英春 , 史美林 . 自组网体系结构研究 [J] . 通信学报 . 19 99 , 20 ( 9) : 47一54 . B EL LM A N R . D yn a m ie P ro g ram m in g 【M ]. p ri n e e to n , N J : p ri n e e to n U n iv e rs it y Pre s s , 19 5 7 · [3]l4] 102 通 信 学 报 2(X) 1 年 15 1 FO R D , FU LKE RS O N D . R o w s in Ne 扭w o rk s【M I . 而n ce ton , NJ :川 n c d o n U n i~ ty P碑 5 5 , 196 2 . [6 ] MCQ U ILL AN J , RI CH ER I , R O SE N E . Th e n e w ro u 石ng al g o ri th m fo r the A RJ 阶LN ET IJ] . IE EE T口口5 o n Co n lln u n , l9 8() , C OM - 2剐5 ):7 11一 7 19 . [7 1 PR A KA SH R . U面山ree tio n a l lin ks Pr o ve e o stly in w lre坛55 ad . hoc n etw o rk s【Al. D IM AC S 认IO r ksh印 o n M比ile N et w o rk s an d C o m Pu ter s [C ] . Se at d e , A ug 199 9 . 15 一 2 2 . [ 8] PE R EJ N S C . B H A G 认, 汀 P 任gh ly d yn幽 c 业st in at 沁n ~ s阅u e nc 目 di sta n c e 一v eetor ro 西n g (D SD V )for m o bil e eo lnP ute 招【A ] , A CM SIG C OMM ’ 94 [C I . Lo n d on , S eP 199 4 ; 2 3 4 一 2 44 . [9 ] MU R T H Y S , G A R C IA 一 L U N ES _ A C E V E S J . A n effi eie n t ro u ti n g Prot oc ol fo r w流le s s n e卿o rk s [J]. A CM B al z e r Mob ile N etw o rks 即d A PPlieat io n s fo u m a l, Spe e i川 Issu e o n R o u ti吃 in Mo 肠le C o m m u 址c a tio n s N e tw o rk s , 199 6 , l(2): 18 3 一 19 7 . [10 1 G A R C IA 一 L U N E S 一 A C EV ES J , MU RT HY 5 . A Pa th 一 6 n di n g al g o ri th m for loo P 一吮e . u ti n g [J] . IEEE A CM T ra n sac tion s on N etw o rki n g , 19 9 7 , 5 (l): 14 8 一 l6() . [川 G U门rA P. K UMA R n A sys te m 朋d tr a断 c de沐一de n t a da Ptive ro u血9 al g o ri血 n fo r ad l取沁 n e rwo 比 s〔A ] . Th e 3 6 . Co “fe re n e e on De e isio n an d Co n tro l[C ] . San 断eg o , C alifo rn ia , 氏e 19 9 7 , 2 37 5 ·2 3 80 . [ 12 ] M A L江Z D , B R O( H J, 」ET C H Ev A J, e r a l . Th e e ffe e ts o f o n 一山湘助d be ha v I0 r in 阴t i叱 讲。toc o ls for m ultih0 P w ire le s s a d hoc n erw o rk s [JI . IEE E Jo u rr . 】o n se l即佬 d 灿 ea s in CO m 「。“n ieatio n s . 19 9 9 . 17(8 ): 14 39 一 14 5 3 . [13 ] JO H N SON J , M A IJ Z D . D yn a n u c s o urc e r o uti n g in ad hoc w ire less n etw o r ks [M ] , Kluw er A ea de 而e : MOb ile C o lnP u tin g , 199 6 . [ 一4 ] PE R KI N S c , R O YE R E . A d 一 hoc o n d ema n d d istan e e v cc to r 阴tin g [A ] . Tb O Z“ IE EE 从陌 rt sho p o n M幽le c o m p u ti n g syste ms a n d A PPlie a ti o n s [C ] . N ew o r le a n s , L A , Fe b l99 9 . 9() 一 l(X) - [ 15 ] PA R K V, CO R SON M . A hig hly ad a Pti ve d istri bu te d rou tin g al g o ri th m for m o bile w i传le弘 n etw o 比 s【A ] . IEE E In阮o m , 9 7 [C ] . K o be . Ja p a n , A声 199 7 , l4() 5 一14 13 . [ 16 ] G A FN IE , B E R TSE K A S D . D is trib u ted al g o ri th ms for g e n e r a tin g l仪军币l e rou te s in n etw 留k s w i出 台e quen tly ehan g in g to PO lo gy lJ] . IE EE T ra nsac d on s o n Com m u n ieat io n , 198 1 . C 一 29 (l) : 11 一 18 . 「17 ] C O R SO N M . PA P八D EM E TR IO U S , PA P八D O POU LO S 只 e r a l . A n ln 仍服t M叭N ET en c a Psu lati o n 详1 】toc o l (IME P) spe e ifi e at ion 【E B /O L ]. htt P:l/ w w w. ie tf o 电IP心 e城n g习卯m ar 几一侧山叭 一ie tf- “口 n七t一ilr 比P- s少e一 1 . 认‘ 199 弘0 8一7 . [ 18 1 B R O C H J , MA] 汀Z D , JOH N SO N D , e t a l. A pe 西叮m 明c e e o n 坏旧 n so n of m 日d ~ ho P w此卜ss 目 hoc oe 呻or k ro u血g 详1】toc o ls [A ] . Th e fo u rth An n ual A CMllE EE I心m ati o nal Co n fe 化n c e o n M o悦le C o m Putin g 朗d N etw 以由In g lCI. 〔. 1她 , Oc t 199 8 , 85 一9 7 . [ 19 ] K O 丫 V A ID YA N . Loc at io n ai 山d ro u 石n g (LA R ) in m o b ile 叨 hoc n e tw o rb [A ] . 丁h e fo . rt h A n . u al A C州的E E E In te rn a tlo n al C o n fe re n e e o n M o b ile Co m Pu tin g an d Ne tw o r k in g【C I. D 习la s , Oc t 199 8 , 66 一 75 . [ 20 ] C H IA N G C , W U H . L IU W. e r a l . RO u t运9 in c lu ste re d mu ltih oP mo b ile w ire le ss n e tw o rk . w ith fa d ing cha n n el[A ] . IEE E S ln g a户万e In te m a tio n al C on fe re n e e o n N e rw o lt s【C ] . Sin g a卯碑, 199 7 , 19 7 一2 11 . 12 1] SIN H A P , SIV A K UMA R R , B H A R G H川伪 N V. C e dar : a eore 一ex tr ae ti叩 di stri b u扭 d ad hoc rou tin g al g o ri 山m lA I . 正E E IN FCK二OM ’ 99 [C ] . N e w YO rk , l卯9 , 202 一209 . [ 22 ] D A S B , B H A R G H AV A N V. R o . ti n g in ad 一hoc n e tw o rk s u 滋n g 而n im u m e o朋ec ted d创拍n at in g 哭tS IA ], IE EE In 比rna tio n al C o n fe re n ee o n o 扣lm u咏ati on sICI. M o ntre ai , Can ad a . 199 7 , 3 76- 38 0 . [ 23 ] D A S B . SIVA K UM A R R , B HAR A G H冉习AN 从 RO u ting in ad · hoc n etw o rks u s哪 a sp咏[Al. IE EE In tern a如n a lC o nfe re n e e o n C o m Pu ters an d C o m m u ni eati o n s N etw o rk s【C ] . L as Ve gas , 199 7 , 3 7吞 38 0 . 【24 ] D A S B , SIVA KUM A R R . B HA R A G H AV A N V Th e ela de ve血b ra ta : sPin e a司 ro uti n g 认 时~ 】长沁 net wo rk sIA ] . IE EE Sym PO siu m o n C o m Pu te r a nd C o m m u n ie丽 o n s[C ]. A th e n s , 〔扮ee ee , 199 8 . 125 ] H A S S