（通信与信息系统专业论文）基于业务的无线网络路由算法研究.pdf

t 北京邮电大学硕士论文 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 王矗筮盔臼 日期：型壁，l 。! 里 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。 本学位论文不属于保密范围，适用本授权书。 本人签名： 王哑垄鱼 日期： 导师签名：日期： 2 7 d i 、7 0 ? 、 争t 。“ j 0 9 ，扎觏， 0二j“， 、r、豢、 6 # 基于业务的无线网络路由算法研究 摘要 随着人们对通信的需求，近几年来，无线通信网络无论在技术上、 还是在商业上都获得了飞速的发展，并且已经在世界范围内广泛使 用。网络多媒体业务的快速增长和多样化对网络提出了更高的要求。 随着多媒体应用日益普及，现有的“尽力而为 的服务显然是不够的， 因此在移动无线网络中提供q o s 已经成为无线网络发展的必然趋势。 本论文的主要研究目标是根据国内外现有的相关研究成果，对如 何在无线网络中提供q o s 保证进行研究工作。本文首先介绍了a dh o e 网络的两类主要单播路由协议：表驱动路由协议和按需驱动路由协 议。随着a dh o c 网络的不断发展，一些应用需要提供服务质量保证。 a dh o c 网络q o s 保障的研究正是为了解决这样的问题，而q o s 路由 协议则是其中的关键因素。本文对a dh o e 网络的o o s 路由协议作了 详细介绍，深入研究分析了一些典型的q o s 路由协议。 本文针对移动网络中节点能量受限的特点结合表征业务的特征 参数，提出了一种基于业务的路由算法，为了支持该算法的运行，文 章提出了新的报文格式和路由表格式；该路由算法根据业务类型，选 择表征业务的参数计算权重，在中间节点，更新路径的权重值和剩余 能量值，路由请求消息到目的节点或者有路径到中间节点后，根据该 路径上的节点剩余能量和权重值，判断是否采用该路径作为最佳路 径，该算法可以延长了网络的生存时间。最后通过仿真和分析，验证 了该算法和a o d v 相比，该算法可以提供更好的服务质量保证。 关键词：q o s 路由a h p 业务能量 ， ij一 w i r e l e s sn e t w o r kr o u t i n g a l g o r i t h mb a s e do ns e r v i c e a b s t r a c t i nr e c e n ty e a r s ，w i t ht h ei n c r e a s ei nc o m m u n i c a t i o nd e m a n d ，w i r e l e s s c o m m u n i c a t i o nh a sa c h i e v e dr a p i dd e v e l o p m e n tb o t hi n t e c h n o l o g y a n d c o m m e r c i a lb u s i n e s s a n da l s oh a sb e e nw i d e l yu s e da r o u n dt h ew o r l d a n a d v a n c e dr e q u i r e m e n to fn e t w o r ka b i l i t yi sr a i s e df o rt h er a p i dg r o w t ho f m u l t i m e d i as e r v i c e sa n dd i v e r s i f i c a t i o no ft h en e t w o r k w i t ht h ep r e v a l e n c eo f m u l t i m e d i aa p p l i c a t i o n ，t h ec u r r e n t ”b e s te f f o r t s e r v i c ei sn o te n o u g h ，i th a s g r a d u a l l yb e c o m ea ni m p o r t a n tr e s e a r c hf i e l dp r o v i d eq o si nm o b i l ew i r e l e s s n e t w o r k s t h i st h e s i si st h ee x t e n s i v er e s e a r c ho nh o wt op r o v i d er o u t i n gp r o t o c o l s w i t hq o sg u a r a n t e ei nw i r e l e s sn e t w o r k sb yr e f e r r i n gt oc u r r e n tr e l e v a n t r e s e a r c hc o n t r i b u t i o n s f i r s t y , t h i st h e s i si n t r o d u c e st h et w ok i n d so fr o u t i n g p r o t o c o l so fa dh o cn e t w o r k si n c l u d i n gt h et a b l ed r i v e np r o t o c o l sa n d o n - d e m a n dd r i v e np r o t o c o l s 。”翟绩a dh o en e t w o r k sd e v e l o p i n gf a s t , s o m e a p p l i c a t i o n sn e e dg u a r a n t e eo ft h es e r v i c eq u a l i t y t h er e s e a r c hi nt h eq o s s u p p o r ti sj u s tt os o l v et h ep r o b l e ma m o n gw h i c ht h eq o sr o u t i n gp r o t o c o l sa r e t h ei m p o r t a n tf a c t o r s t h i st h e s i si n t r o d u c e st h eq o sr o u t i n gp r o t o c o l sa n d r e s e a r c h e sd e e p l yi ns o m et y p i c a lq o s r o u t i n gp r o t o c o l s c o n s i d e r i n g t h ec h a r a c t e r i s t i c so f e n e r g y - c o n s t r a i n e d a n dd i f f e r e n t p a r a m e t e r so fs e r v i c e ，t h i st h e s i sp r o p o s e dan e wr o u t ea l g o r i t h mb a s e do n d i f f e r e n ts e r v i c e s ；i no r d e rt or u n n i n gt h ea l g o r i t h mt h i st h e s i sp r o p o s e dt h en e w f o r m a to ft h em e s s a g ep a c k e ta n dr o u t i n gt a b l e b a s e do nt h eb u s i n e s st y p e ，t h e r o u t i n ga l g o r i t h mc h o o s ec h a r a c t e r i s t i cp a r a m e t e rs e tt oc a l c u l a t ec o s to fl i n k , i n t h ei n t e r m e d i a t en o d e ，u p d a t et h ep a t hc o s ta n dt h er e s i d u a le n e r g yv a l u e ，a f t e r t h er o u t i n gr e q u e s tm e s s a g ea r r i v ea tt h ed e s t i n a t i o nn o d eo ri n t e r m e d i a t en o d e w h i c hh a st h er o u t et ot h ed e s t i n a t i o nn o d e 。t h en o d ed e t e r m i n ew h e t h e rt oa d o p t t h ep a t ha st h ef o r w a r dp a t ha c c o r d i n gt ot h er e s i d u a le n e r g ya n dc o s to ft h e p a t h t h ea l g o r i t h mi s t oe x t e n d 也en e t w o r kl i f e t i m e t h r o u g hs i m u l a t e d e x p e r i m e n ti ti l l u s t r a t e st h a tt h ea l g o r i t h mc a np r o v i d eb e t t e rq o s o fs e r v i c e s t h a na o d v k e y w o r d s ：q o sr o u t e ；a h p ；s e r v i c e ；e n e r g y i 气 卜 、 _ 目录 第一章绪论1 1 1 研究意义l 1 2 无线网络的特点2 1 3 研究现状3 1 4 论文结构及创新点5 1 4 1 论文结构5 1 4 2 论文主要创新点6 第二章a dh o c 网络中典型路由协议和o o s 路由7 2 1 移动a dh o c 网络及其关键技术7 2 2a dh o c 网络典型路由协议研究8 2 2 1a dh o c 路由协议概述。8 2 2 2a dh o c 路由协议9 2 2 2 1 表驱动路由协议1 0 2 2 2 2 按需驱动路由协议1 l 2 3 现有a dh o c 的o o s 路由协议描述1 4 2 3 1o o s 概述1 4 2 3 2o o s 的保障机制1 4 2 3 3o o s 路由策略1 6 2 3 4 现有o o s 路由协议1 6 第三章业务分类及业务参数2 0 3 1 业务分类2 0 3 1 13 g p p 的业务分类2 0 3 1 2wim a x 业务分类2 l 3 2 参数选择研究2 2 3 2 1 端到端o o s 需求研究2 2 3 2 2 业务参数选择结论2 3 3 3 参数权重确定2 4 第四章基于业务的路由算法2 7 4 1 链路代价计算算法一2 7 i l i 4 2 路径选择算法2 9 第五章算法仿真分析3 3 5 1 仿真网络模型3 3 5 2 仿真参数设置。3 3 5 2 1 基本参数设定3 3 5 2 2 网络变化参数设置3 4 5 2 3 仿真程序流程图3 6 5 3 仿真结果及分析3 7 第六章总结与展望4 7 6 1 论文总结4 7 6 2 论文展望4 7 参考文献4 9 致谢5 2 攻读硕士期间发表论文情况5 3 i v 第一章绪论 第一章绪论 随着人们对通信的需求，近几年来，无线通信网络无论在技术上、还是在商 业上都获得了飞速的发展，并且已经在世界范围内广泛使用。无线通信网络由于 可以支持用户的移动性而使它成为个人通信和i n t e r n e t 发展的方向，而且只有 通过无线网络才能实现“任何人在任何时间、任何地点与任何人进行任何种类的 信息交换( 5 w ) 的理想通信目标。 目前主要的无线通信网络可分为两大类：一类是由目前的第2 代数字蜂窝移 动通信系统( 2 g ，包括g s m 、c d m a ) 发展而来的第2 5 代( 2 5 g ，包括g p r s 、c d m a i x ) 和第3 代( 3 g ，包括t d - s c d m a 、w c d m a 、c d m a 2 0 0 0 ) 移动通信系统。另一类是 采用i e e e ( i n s t i t u t eo fe l e c t r i c a la n de l e c t r o n i ce n g i n e e r s ) 开发的8 0 2 系列无线协议的无线通信系统，根据覆盖范围不同，这些系统分为无线个人网 ( w p a n ：w i r e l e s sp e r s o n a la r e an e t w o r k ) 、无线局域网( w l a n ：w i r e l e s sl o c a l a r e an e t w o r k ) 和无线城域网( w m a n ：w i r e l e s sm e t r o p o l i t a na r e an e t w o r k ) 。 通过使用无线通信网络，极大方便了人民的生活，同时也推动了无线通信技术的 迸一步发展。 随着人们对网络要求的不断提高，无线网络技术越来越受到人们的重视。网 络多媒体业务的快速增长和多样化对网络提出了更高的要求，对那些有带宽、延 迟、抖动等特殊要求的应用来说，现有的“尽力而为”的服务显然是不够的【， 因此在移动无线网络中提供q o s 已经成为无线网络发展的必然趋势。 同时在无 线网络中提供q o s 路由已成为研究的热点。文中的无线网络以a dh o c 网络为主 进行研究。 1 1 研究意义 现有的移动网络一般都是有中心的，需要基站或接入点这样的中心才能通 信，需要提前建设网络基础设施才能运行。但对于一些特殊场合，这样的网络并 不能胜任。0 8 年的南方雪灾和0 9 年的汶川地震，使得网络基础设施全部瘫痪， 通信成了最大的问题，在短期内根本不能恢复之前的通信，也给救灾带来了不便。 因此需要建立一个能够临时快速自动组网的无线网络。 目前在移动网络中提供q o s 成为新的研究热点。q o s 的研究目标是有效地为 用户提供端到端的服务质量控制或保证【2 】。q o s 意味着网络单元例如应用程序， 第一章绪论 主机或路由器能够在一定级别上确保它的业务流和服务要求得到满足。o o s 并没 有创造带宽，只是根据应用程序的需求以及网络状况来管理带宽。 q o s ( q u a l i t yo fs e r v i c e ) 是网络在传输数据时，数据对网络需求的集合。 也就是说，q o s 是业务对网络传输服务时提供的一组可度量的要求，主要包括： 延迟、带宽、丢包率、延时抖动、花费等。网络在传输相应的业务数据时，必须 满足这些要求。o o s 保证体系是一个全局性问题，它要求网络中的各个节点以及 节点上的各个协议层次相互协作，共同完成。在无线网络中实现o o s 保证除了面 临有线网络中存在的问题，还要面对节点能量有限、链路质量难以预测、链路带 宽资源难以确定、分布式控制机制和网络的动态性使得o o s 保证难以实现等新挑 战。所以相对于有线网络，无线网络的o o s 保证体系实现起来要困难得多。因此， 对网络o o s 保证体系的研究既有挑战性，又有重大的应用价值和实际意义。 目前网络中的路由对于所有的数据都是采用相同的路径进行数据传输。q o s 路由的实现主要包括以下两个方面：一是找到满足q o s 需求的路由，在保持连接 的过程中维护路由，并及时更新网络拓扑和链路状态信息：二是尽量减小复杂的 o o s 路由的开销，优化网络资源的分配，以提高资源利用率和网络吞吐量。因此， 理想的o o s 路由协议应具有开销小、鲁棒性好、可扩展性好、能快速响应无线信 道和网络拓扑的变化等特点。 以往的路由算法只是考虑将条数作为路由选择的依据，近年来也有研究关于 多约束o o s 的路由问题，但当加性约束或者乘性约束多于一个时，多约束q o s 路 由问题是n p c ( n pc o m p l e t e ) 的【3 】。n p c 问题的解决，只有将解域中所有可能值都 穷举了之后才能得出答案。但是这样穷举之后，算法的复杂程度是指数关系。因 此计算的时间随着问题的复杂程度呈指数增长，很快就变得不可计算了。目前的 保证业务q o s 的路由算法考虑的因素有时延、带宽、功耗、以及频率切换。但大 多都是只考虑其中的一两个，没有把它们结合在一起考虑。 基于上述问题，本文提出了基于业务的考虑多种参数的路由算法，即基于业 务的无线网络路由算法研究。文章中的网络以自组织网络( a dh o c ) 为研究的目 标网络。 1 2 无线网络的特点 无线网络的特性如下所示： ( 1 ) 动态的拓扑结构：网络节点可以任意的速度沿任意方向自由地移动。因 此，网络必须适应动态变化的拓扑结构，特别是在多跳情况下的拓扑结构变化。 ( 2 ) 带宽受限：无线信道会引起带宽受限，比如多路访问、多径、噪声、信 道衰落和有限的频谱引起的信道问题。在移动无线网络中，媒体接入控制协议被 2 第一章绪论 用于处理这些信道接入问题，并尽量使每个节点的吞吐量小于信道的最大数据传 输率。 ( 3 ) 安全性低：无线网本质上具有安全隐患，传输的信息非常容易受到监听、 重发、篡改、伪造、拒绝服务等各种攻击。如果路由协议受到上述恶意攻击，整 个网络将无法正常工作。 1 3 研究现状 由于无线网络是为用户提供了方便的多跳无线接入i n t e r n e t 的方案，因此， 在设计无线网络的q o s 保证时，需要考虑两个主要因素 4 1 ：一是无线网络自身的 特点；二是与i n t e r n e t 的无缝连接。 目前在i n t e r n e t 上支持q o s 的体系结构主要有两种i s ：i n t s e r v 和d i f f s e r v 。 i n t s e r v 是一种资源预留机制( r s c p ) ，它引入了虚电路的概念，由r s c p 作为建 立和维护虚电路的信令协议。d i f f s e r v 是一种基于类的q o s 体系结构【6 】，它提供 定性的o o s 支持。 在传统的网络中，保证q o s 通常有三种方法：第一类是通过设计性能更强大 的网络避免竞争，该方案的前提是资源丰富，代价和花费也比较高；第二类是沿 着数据流经过的路径保留端到端的资源，如r s v p ；第三类是不必为具体的业务 在网络中保留端到端的资源，但是需要对分组做标记并在节点中做特殊处理，如 区分服务d i f f s e r v ( d i f f e r e n t i a t e ds e r v i c e s ) 。第一类方法肯定不适合移动 网络，移动网络的资源都是有限的，而后两类的服务模型并没有考虑无线的网络 环境。同时现存的大部分无线网络中提供的q o s 保障都是基于蜂窝模型，不适应 于多跳、拓扑动态变化的网络。在无线网络内部提供q o s 路由存在着很多难点， 主要体现在以下几个方面： ( 1 ) 网络资源受限 无线网络由于采用无线通信，一般信道带宽比较窄，无线信道质量不稳定， 而且容易受到其他干扰，虽然可以通过使用编码方法、提高信号发射功率、或选 择其他路径解决。但信道质量问题的解决通常会造成网络中的进一步拥塞，更强 的编码会导致占用过多的带宽，选择其他路径会增加节点负载，增大功率会对其 他用户形成干扰，同时会增加分组碰撞的概率，这些都会造成网络的拥塞。 ( 2 ) 节点特性 由于随机移动、节点内存受限等因素，移动网络中的路由选择算法不能太复 杂。因此在拓扑结构变化频繁的移动网络中，o o s 路由要兼顾考虑如何提供q o s 支持和资源受限等问题1 7 】。 ( 3 ) 信道访问机制隅j 第一章绪论 无线信道是广播共享形式，无线信道访问机制基本是随机访问形式。因此， 通过引入大量控制分组的方案是不可行的，这样为带来碰撞的增加，获得信道访 问机会的概率就会变小，会降低系统整体效率。 ( 4 ) q o s 路由的不准确性 主要由四种情况造成：网络动态变化，包括拓扑结构和网络参数的变化；路 由信息汇聚引入的不准确性 9 】；处于安全考虑或其它因素而存在隐藏的路由信 息；测量得到的网络参数值都是近似值。 拓扑结构的变化给q o s 支持带来了巨大的困难，要消除或减轻网络拓扑结构 变化对服务质量的影响需要m a c 层的支持，以及路由协议能够快速生成新的路 径。所以在拓扑变化频繁的无线网络环境中，q o s 路由要兼顾如何提供o o s 支持 和资源受限的问题，在算法效率和自适应性间做出折衷【l u j 。 当前无线网络q o s 支持的研究中比较成熟的有： ( 1 ) q o s 路由 首先通过带有q o s 信息的路由，实施有效的允许控制来防止网络负载过重， 寻找满足o o s 需求的路由在无线网络中实施负载均衡【l 。可以基于现有的路由算 法来构造q o s 路由协议，每个节点在路由表中增加相应的q o s 信息，计算最短路 径的同时计算各种q o s 信息，每个节点根据q o s 信息来决定是否接受新的连接请 求。然而，计算满足多个约束条件的路由是一个n p 完全问题，因此需要借助启 发式算法来计算一个满足多目标的次优化路由【9 j 。 ( 2 ) 具有q o s 能力的中间适配机制 通过采用带有中间适配件的网络框架来动态地适应网络性能的变化，这种方 法考虑了网的性能和端到端的资源状况，可以向应用提供有用的信息用于重构， 从而使整个系统获最优的q o s 保障等裂忆j 。 ( 3 ) 支持q o s 的m a c 协议 其目标是在移动a dh o c 网络中使共享介质的各个节点能在尽可能不影响其 它节点的提下实现自身的q o s 要求。其中，组分配多址接入协议g a m a 是一种用 于提供q o s 证的m a c 协议，协议中一个竞争阶段通过使用r t s 和c t s 对话，为随 后的无竞争阶预留带宽，多址接入分组预留协议姒c a p a 可以在无冲突阶段发 送一个确认消息来知相邻的节点是否需要预留带宽，每个节点可以基于分组中携 带的预约请求来获得信道状态。 ( 4 ) 动态服务质量保证机制 动态q o s 保证机制是一种基于资源预留的服从综合服务模型的方法。资源预 留请求定了一个预约请求范围，网络实体通过对此请求范围进行检测，从而可以 灵活地提供服。预约请求范围从能接受的最小服务级别到最大服务质量等级，各 4 第一章绪论 种网络实体在此范围根据网络的资源状况进行动态的自适应调整，从而提供一种 在动态环境下灵活的o o s 保障机制。 对q o s 业务的支持通常分为以下几种：满足业务时延、满足业务带宽和业 务优先级等。满足业务时延是指用户的数据传输时延必须小于一定的值，要求路 由算法找出满足最大时延( d e l a yc o n s t r a i n t ) 的路由；满足业务带宽是指用户的 数据传输所需的带宽必须大于一定的值，要求路由算法找出满足业务传输要求最 小带宽( b a n dc o n s t r a i n t ) 的路由：对于业务优先级的支持则是指根据预约业务 的优先等级分配给相应的网络资源q o s 路由( q o s b a s e dr o u t i n g ) 是根据网络上 可利用资源和流( f l o w ) 的o o s 需求决定流的路由的机制。q o s 路由应能达到以 下目标：( 1 ) 动态确定可行路径；( 2 ) 优化资源利用；( 3 ) 对性能影响尽可能小。通 过阅读现有的文章和资料，现有的路由可以归纳为以下三种 基于动态频谱分配的路由方法：从频谱分配的角度切入，着重探讨了采用基 于频谱感知的路由协议对网络延迟带来的改善。 基于功率的路由方法：在网络层，路由算法要选择最小化分组传输所需要的 功率，使每个节点的生存寿命最大。 将上述两种结合起来考虑的路由算法。 无线网络的应用要求保证o o s ，但网络的特点使得无线网络中保证q o s 面临 挑战。尽管目前己有较多的文献从不同的角度研究无线网络的q o s 问题，但目前 的路由算法对于所有的业务都采用相同的路径来转发数据，文章提出基于不同的 业务类型来选择不同的路径发送数据。 1 4 论文结构及创新点 1 4 1 论文结构 本文总共6 章： 第一章简单介绍课题研究的意义和q o s 路由的研究现状； 第二章介绍了现有的无线自组织网络( a dh o c ) 中的路由算法； 第三章介绍了与本文算法相关的业务分类与特征参数选择调研结果、参数 权重确定方法，为第四章算法的提出打下基础； 第四章基于业务的路径选择算法详述； 第五章所提算法的仿真与结果分析： 第六章总结与展望 5 第一章绪论 1 4 2 论文主要创新点 本文主要创新点如下： 1 ) 基于业务的路径算法，按照用户所运行的业务需求去选择路径，旨在为 用户提供更好的q o s 。 2 ) 为了实现文中提出的路由算法，提出用于该算法的报文格式。 3 ) 算法在选择最佳路径时考虑了节点的能量，将数据分散到不同的节点转 发，可以延长网络的生存时间。 仿真结果表明，本算法能提高整体q o s 性能。 6 第一二章a dh o e 网络中典型路由协议和q o s 路由 第二章h dh o e 网络中典型路由协议和o o $ 路由 2 1 移动a dh o e 网络及其关键技术 a dh o e 网络是一种没有有线同时也没有中心的移动网络，网络中的节点均 由移动主机构成【l 引。每个主机既是路由器也是发送设备，在a dh o c 网络中，当 两个移动主机在彼此的通信覆盖范围内时，它们可以直接通信。如果两个相距较 远的主机即没有在彼此的覆盖范围内) 要进行通信，则需要通过它们之间的其他 主机的转发才能实现通信。因此在a dh o e 网络中，主机同时担负着寻找路由和 转发报文的工作。a dh o e 网络中，每个主机的通信范围有限，所以路由一般都 由多跳组成，数据通过多个主机的转发才能到达目的地。故a dh o e 网络也被称 为多跳无线网络。 a dh o e 网络不同于目前因特网环境中的移动i p 网络。在移动i p 网络中， 移动主机可以通过固定有线网络、无线链路和拨号线路等方式接入网络，而在 a dh o c 网络中只存在无线链路一种连接方式。在移动i p 网络中，移动主机通过 相邻的基站等有线设施的支持才能通信，在基站和基站( 代理和代理) 之间均为有 线网络，仍然使用因特网的传统路由协议。而a dh o c 网络没有这些设施的支持。 此外，在移动i p 网络移动主机不具备路由功能，只是一个普通的通信终端。当 移动主机从一个区移动到另一个区时并不改变网络拓扑结构，而a dh o e 网络中 移动主机的移动将会导致拓扑结构的改变。 根据移动a dh o e 网络的特点，参照o s i 参考模型，移动a dh o c 网络构如图 2 1 所示【1 4 】。 在这个体系结构中，物理层主要使用完成无线信号的发送和接收：数据链路 层主要完成无线信道的共享访问、流量控制等功能，同时要考虑到物理层使用的 技术对协议设计带来的影响，留下相应的控制接口；网络层中，i p v 4 协议、i p v 6 协议或其它网络层协议提供网络层数据服务；网络层的单目标路由协议维护路由 表，使其与当前的移动a dh o c 网络拓扑结构保持一致；多目标路由协议提供对 群组通信的支持；网间互联支持移动a dh o c 网络与其它现有网络的互联互通； o o s 支持提供可保证的q o s 服务；由安全提供对路由协议的安全保障。传输层仍 然主要使用u d p 和t c p 协议，但是针对移动a dh o c 网络的无线运行环境，这两 7 第二章a dh o e 网络中典型路由协议和q o s 路由 种协议要进行相应的修改。上层应用指的是面向用户的各种服务。目前，移动 a dh o c 网络技术的研究热点有网络拓扑结构、路由协议、m a c 协议、节能设计、 安全问题和网络管理等等。 上层应用协议 应用层 u d p t c p 表示层 多目标路网间互联o o s 支持路由安全 会话层 传输层 由协议 。? 、。- l “- - k 一一_ 一。j 。j 。 网络层 单目标路由协议 i p v 4 、i p v 6其他网络层协议 链路媒体接入控制 天线控功率控 无线控制接口 数据链路层 制接口制接口 天线功率控制 调制解调信号处理 物理层 技术技术技术技术 图2 - 1 移动a d h o c 网络的体系结构 2 2a dh o c 网络典型路由协议研究 2 2 1a dh o c 路由协议概述 路由协议是a dh o e 网络中研究的热点问题之一。路由是所有数据网络的核 心所在，它的用途是通过网络将信息从源传送到目的地。路由器是负责将数据包 从一个网络传送到另一个网络的设备。路由协议的主要目标是：满足应用需求的 同时，降低网络所需的开销，使资源的整体有效性最高，扩大网络的吞吐量。 常用的路由协议分为两种：一种是静态的路由协议，通过网络管理员手动配 置，静态路由的开销小于动态路由协议，但如果拓扑结构经常发生变化或不稳定， 则静态路由将需要更多的维护工作。一种是动态路由协议，动态路由协议能够自 动调整以适应网络变化，无需网络管理员干预。动态路由协议要求更多的c p u 处 第二章a dh o e 网络中典型路由协议和q o s 路由 理工作，并且还需要使用一定量的链路资源用于路由更新和通信。在许多情况中， 路由表同时包含静态和动态路由。 动态路由协议也分为两种：一种是基于距离矢量的路由协议，如r i p ，由于 该协议的生存时间( t t l ) 只为1 5 跳，即源节点和目的节的之间经过的路由器的 个数不能超过1 5 ，因此r i p 只适应于小规模的网络；一种是基于链路状态的路 由协议，如o s p f ，0 s p f 采用最短路径优先算法计算路径，适合于大规模的网络， 目前i n t e r n e t 的大多数路由器采用o s p f 路由。这两类路由协议是针对有线网络 设计的，有线网络不会出现大的网络拓扑变化，同时有线网络的带宽比较充足。 在a dh o c 网络中，网络拓扑结构变化比较频繁，需要大量的控制信息来获得新 的路径，在路由发现和维护时，会占用大量的网络资源，使信息不能正确的传输。 另外，还有其他的因素使得平常的路由协议不能被a d i o c 网络采用：a dh o c 网 络中无线信道中的大量干扰导致单向信道的存在；无线信道的广播特性使得常规 路由的网络选路过程产生许多冗余链路；周期性广播路由更新消耗大量的网络带 宽和节点能源，但是a dh o c 节点的带宽和能量均有限；某些常规路由协议需要 的复杂计算使得c p u 始终处于很高的负载之下，这同样消耗了大量的能源。因此， 传统的有线路由协议无法适应a dh o c 网络。 根据以上的分析可知：理想的a dh o c 网络路由协议应该具有下面的特征：1 ) q o s ( q u a l i t yo fs e r v i c e 服务质量) ：由于拓扑结构的变化，在a dh o c 网络中 保证q o s 存在较大困难；2 ) 分布式路由：路由协议的实现应该是分布式的，不 依赖于控制中心；3 ) 支持单向性；4 ) 有效的利用带宽：无线网络的带宽资源有 限，因此需要减少控制信息；5 ) 迅速收敛：a dh o c 网络的拓扑变化频繁，要求 路由协议的收敛性比较快，可以及时获得有效的路由；6 ) 节能：a dh o c 路由协 议应尽可能的节省能量，否则节点由于能量被耗尽失效，会导致路径失效；7 ) 安全性：无线网络容易受到安全攻击，比如窃听、伪造、拒绝服务等攻击。 2 2 2a dh o d 路由协议 在a dh o c 网络中建立路由始终是a dh o c 网络研究的首要问题，目前a dh o c 网络路由协议一般按驱动方式进行分类：已有的a dt t o c 路由协议分为两类：表 驱动( t a b l ed r i v e n ) 路由协议和源发起按需驱动( s o u r c e i n i t i a t e do n d e m a n d d r i v e n ) 路由协议。前者的优点是查找路由时比较快，缺点是协议需要大量的路 由控制报文，加大网络的负担；后者则相反，只有在分组发送时才会进行路由查 找，节省了带宽及其他资源。除此之外，还有一类称为分层路由协议，它结合了 表驱动路由和按需路由的优点。 9 第二章a dh o c 网络中典型路由协议和q o s 路由 2 2 2 1 表驱动路由协议 表驱动路由协议又称为先验式路由协议，表驱动路由协议是在有线网络路由 协议的基础上改进的。无论是否有数据需要发送，每个节点周期性的广播路由分 组，交换路由信息，维持一张或多张表格来存储其它节点的路由信息。当网络拓 扑结构变化时，通过广播更新信息来保持路由表信息与网络拓扑的变化之间的一 致性。源节点一旦要发送分组，通过查本节点的路由表，可以立即获得指向木得 节点的路由。 表驱动路由协议包括邻居发现和路由广播两个过程。节点通过周期性地发送 “h e l l o ”分组，来发现邻居。路由广播采用泛洪方式向全网扩散。在表驱动路 由协议中，表驱动路由协议虽然可以很快地获得到其它所有节点的路由，但节点 需要实时地维护路由信息，这样在网络规模较大，拓扑变化较快的环境中，会存 在大量的拓扑更新消息，开销比较大，不可避免地存在信号拥塞和能量过度消耗 的问题，使得系统效率下降。典型的表驱动路由协议包括：d s d v ( d e s t i n a t i o n s e q u e n c e d d is t a n c ev e c t o r ) 【1 5 ，1 6 ，1 川、c g s r ( c l u s t e r h e a dg a t e w a ys w i t c h r o u t i n g ) 【1 8 1 、w r p ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) 1 9 】。 ( 1 ) d s d v ( 目的节点序列距离矢量协议) 【” l 6 1 刀 d s d v ( d e s t i n a t i o n s e q u e n c e dd i s t a n c e v e c t o r ) 路由算法是一种平面的、 表驱动路由，是对传统的b e l l m a n - f o r d 路由算法进行了改进。在d s d v 中，每个 移动节点都需要维护一个路由表。路由表中包含有所有可到达的目的节点、到达 目的节点的跳数和有目的节点指定的序列号( s e q u e n c en u m b e r ) 。其中目的序列 号由目的节点分配，主要用于判别路由是否过时，并可防止路由环路的产生。每 个节点周期性和在拓扑发生变化时向邻居节点发送当前路由表。接收节点将收到 的到每个目的节点的序列号与自己路由表中到该目的节点的序列号进行比较，如 果收到的路由信息中的序列号较高，则接收节点更新自己的路由表，同时将发送 者作为下一跳；如果收到的路由信息的序列号和自己的序列号相同，但路由度量 小，接收节点也更新自己的路由表。d s d v 路由协议的开销随着节点数的增加而 增加，当网络拓扑变化频繁时，路由更新也会经常进行，因此d s d v 路由协议适 用于规模较小且网络拓扑比较稳定的网络。d s d v 不支持单信道。 ( 2 ) c g s r ( 群首网关交换路由协议) 【l 8 】 c g s r ( c l u s t e r h e a dg a t e w a ys w i t c hr o u t i n g ) 与d s d v 类似，但是c g s r 并不 是一个大的平面网络而是分层网络。虽然c g s r 用d s d v 作为其底层的协议，但是 由于在c g s r 中寻路是通过群首节点和网关节点来完成的，所以它比d s d v 更有效， 且有一定的可扩展性。c g s r 分配指定了群首节点和网关节点，其中群首节点用 i o 第一二章a dh o e 网络中典型路由协议和o o s 路由 来控制一组节点和网关节点，而网关节点是两个群之间的节点。当一个节点要发 送分组时，这个分组首先到达该发送节点的群首结点，然后群首节点把这个分组 通过网关节点转发给另一个群首节点。不断重复这个过程直到分组到达目的节 点。因此，每个节点都必须有其群成员的路由表。当一个节点不在任何群的范围 内时或是两个或多个群首节点在彼此的范围内时，就产生一个新的群首节点。在 c g s r 中还采用启发式的方法如优先级令牌的调度、网关编码调度和通路预约来 改善其性能。 ( 3 ) w r p ( 无线路由协议) l l 州 w r p ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) 是一种距离一矢量路由协议。每个节点保 存在路由表中的信息如下：距离、路由、链路开销和重传消息的列表( m r l ) 。m r l 记录关于消息序列号、重传计数器、每一个相邻节点正确应答所需的标识和更新 消息的更新列表等信息。这就使得节点可以决定何时发送更新消息以及发送给哪 个节点。更新消息包括目的节点的地址、到目的节点的距离和目的节点的上游节 点。然后相邻节点就修改自己的路由表并试图通过预备的节点建立新的路由。当 网络路由表没有任何变化时，接收节点需回传一个空闲报文以示连接，否则，修 改距离表，寻找更优路径。w r p 的特点是党检测到任意相邻节点变化时，则检查 所有相邻节点的坚固性以消除回路，具有较快的收敛性。 2 2 2 2 按需驱动路由协议 按需路由协议又称为反应式路由，包括路由发现和路由维护两个过程，按需 路由不像表驱动路由协议那样实时地维持每个节点的路由信息，而只在需要发送 数据时才发起路由查找过程，从而降低了对网络带宽和能量的过度消耗，但是数 据报传送的时延较大，不适合实时性的应用。源节点发送数据前，广播一个路由 请求消息，附近节点收到后再次广播，直到请求消息到达目的节点或到达知道目 的节点路由的中间节点，目的节点或中间节点沿原来路径返回相应消息，源节点 收到响应后就知道到达目的节点的路由，路由建立之后，会由一个路由维护程序 进行维护，直到每条路径都断裂或不再需要路由为止。常用的按需路由协议包括： a o d v ( a dh o c0 n d e m a n dd i s t a n c ev e c