（通信与信息系统专业论文）基于蚁群思想的ad+hoc路由协议研究及实现.pdf

西南科技大学硕士研究生学位论文第1 页 摘要 a dh o e 是由一组具有路由功能节点组成的分布式无线多跳网络，其动态 变化的网络结构和有限的网络资源给路由协议提出了极大的挑战。然而传统 的a dh o e 路由协议由于缺乏有效的拥塞响应机制，致使网络拥塞时，仅简单 地对数据包进行排队或丢弃处理，而不是寻找其它较好的路径分流负载，因 此无法对网络资源进行合理充分的利用，进而极大地影响网络性能。 本文分析研究了现有两种典型的a dh o e 路由协议，并针对该协议在拥塞 管理和最优路径定位方面的不足，提出了一种新的多路径路由协议基于 蚁群思想的自适应a d a r 路由协议。协议中，通过拥塞规避机制的引入，改 进了路由优先级在路由发现及数据传输过程中的确立，实现规避拥塞链路， 完成负载分流，并最大限度地降低网络拥塞，提高网络吞吐量，降低端到端 传输时延。同时，为加速路径最优解的收敛过程，a d a r 协议在基本蚁群算 法基础上提出了信息决策优化，通过蚂蚁信息的正反馈机制实现路径搜索更 快集中在最优解附近，“缩小”搜索范围。 然后根据a d a r 算法描述，设计了基于l i n u x 平台的路由框架结构，提 出了路由实现方案及实现技术。最后通过大量的现场实验表明，该算法有效 地规避了网络拥塞，提高了网络性能，验证了a d a r 路由协议的有效性和可 行性。 关键词：a dh o c 网络拥塞a d a rl i n u x 西南科技大学硕士研究生学位论文 第1 i 页 a b s t r a c t a dh o cw h i c ha r ec o m p o s e do fn u m b e r so fn o d e sw i t hr o u t i n gf u n c t i o na r e w i r e l e s sa n dd i s t r i b u t e dm u l t i h o pn e t w o r k s b e c a u s eo ft h el i m i t e db a n d w i d t h a n dt h ed y n a m i ct o p o l o g y , t h er o u t i n gi na dh o cf a c e sw i t he n o r m o u sc h a l l e n g e s f o rl a c k i n go fe f f e c t i v ec o n g e s t i o nc o n t r o lm e c h a n i s m ，t h et r a d i t i o n a lr o u t i n g p r o t o c o l si na dh o co n l yq u e u eu po rd i s c a r dp a c k e t sa st h en e t w o r kb e c o m e s c o n g e s t e dr a t h e rt h a nl o o kf o ro t h e rg o o dl i n k st os h u n tt r a f f i c s oi td o e s n tf u l l y u t i l i z et h en e t w o r kr e s o u r c e sa n de v e ng r e a t l yr e d u c et h en e t w o r kp e r f o r m a n c e i no r d e rt oo v e r c o m et h ed e f i c i e n c i e so ft h ec o n g e s t i o nm a n a g e m e n ta n dt h e e s t a b l i s h m e n to fo p t i m a ll i n ki ne x i s t i n gt y p i c a la dh o cr o u t i n gp r o t o c o l s ，an e w m u l t i - p a t ha d a p t i v ea d a rr o u t i n gp r o t o c o lb a s e do na n tc o l o n ya l g o r i t h mi d e a f o ra dh o cn e t w o r k si sp r o p o s e d i nt h ep r o t o c o l ，t h r o u g ht h ei n t r o d u c t i o no f m e c h a n i s m sf o ra v o i d i n gn e t w o r kc o n g e s t i o n ，t h i sp a p e rm e n d st h ee s t a b l i s h m e n t o fr o u t ep r i o r i t yi nr o u t ed i s c o v e r ya n dd a t at r a n s m i s s i o np r o c e s st oi m p r o v e n e t w o r kp e r f o r m a n c es u c ha s d i v e r t i n g t h et r a f f i c ，m i n i m i z i n gn e t w o r k c o n g e s t i o n ，i m p r o v i n gn e t w o r kt h r o u g h p u t ，r e d u c i n gt h ee n d - t o e n dt r a n s m i s s i o n d e l a ya n ds 0o n a tt h es a m et i m e ，f o ra c c e l e r a t i n go p t i m a ls o l u t i o nr e s t r a i n i n g p r o c e s s ，w ep r e s e n tt h ei n f o r m a t i o nd e c i s i o n - m a k i n go p t i m i z a t i o na tt h eb a s i so f t h eb a s i ca n tc o l o n ya l g o r i t h mt os h r i n kt h er o u t es e a r c hz o n ea n dq u i c k l y c o n c e n t r a t en e a r b yt h eo p t i m a ll i n k t h e n ，a c c o r d i n gt ot h ea d a ra l g o r i t h md e s c r i p t i o n ，t h i sp a p e rd e s i g n sa r o u t i n gf r a m e w o r kb a s e d0 nl i n u xp l a t f o r ma n dp r o p o s e st h ea c h i e v e m e n to f p l a na n dt h et e c h n o l o g y f i n a l l y , t h em a s s i v ee x p e r i m e n tr e s u l t ss h o wt h a tt h e a l g o r i t h m c a n e f f e c t i v e l y a v o i dn e t w o r kc o n g e s t i o n ，e n h a n c en e t w o r k p e r f o r m a n c ea n dt h e nc o n f i r mt h ea d a r r o u t ep r o t o c o lv a l i d i t ya n df e a s i b i l i t y k e yw o r d s ：a dh o c ；n e t w o r kc o n g e s t i o n ；a d a r ；l i n u x 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得西南科技大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己 在论文中作了明确的说明并表示了谢意。 签名：弧辫 日期：炒7 r 一“如 关于论文使用和授权的说明 本人完全了解西南科技大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文的复印件，允许该论文被查阅和借阅；学校可以公布该论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：戢脚 导师签名：i2 ，l 扇乙 日期： 炒7 。，髟 西南科技大学硕士研究生学位论文第1 页 1绪论 11 研究背景 日前无线网络正在快速发展与普及，其通常可以分为有中心网络和无中 心网络。有中心网络需要固定基础设施的支持，例如，蜂窝移动通信系统要 有基站的支持；无线局域网般也工作在有a p 接入点和有线骨干网的模式 下。但对于有些特殊场合来说，如战场上部队快速展开和推进，地震或灾害 后的营救，野外科考作业，以及f 临时性组织的大型会议等场合的通信不能依 赖于任何预先部署的网络设施( 或者预先部署的设施己经因灾害损毁而失去 效用1 ，而是需要一种能够临时快速自动组网的移动通信技术。因此，一种新 的网络技术a dh o c 网络技术应运而生。 “a dh o c 词来源于拉丁语，是“特别地，专门地”的意思。“a dh o c 技术” 所标称的是一种特殊的无线移动网络构架技术，强调多跳、白组织、无中心 的概念，所以a d h o c 网络也被称为“多跳无线网( m u l t i h o p w i r e l e s s n e t w o r k ) ” 或者“无线自组网( w i r e l e s ss e l f - o r g a n i z e dn e t w o r k ) ”。a dh o c 无线嘲络 的一个例子如图1 一l 所示。 图卜1 a dh o c 无线网络 - ig1 1 dh o cw ir e le s sn e t w o r k 罔中，由于没有中心控制器，如其它无线网络中管理路由决策的固定路 由器，因此在无线a dh o c 网络中的所有移动节点通过分布式相互协作来进行 路由决策，即a dh o c 网络中每个节点兼备主机和路出器的功能。 西南科技大学硕士研究生学位论文第2 页 在a dh o c 网络中节点间的关系是对等的，一个节点瘫痪后，依赖它通信 的节点可以选择其它节点进行中继，因此a dh o c 网络的结构十分健壮。由于 无需固定基础设施支持，a dh o c 网络具有很大的灵活性，可以用于无法或不 便预先架设网络设施、需要快速自动组网的场合，如：军事战备、紧急救援、 临时会议等多种领域，具有广阔的应用前景。 a dh o c 网络灵活机动、组网迅速、适应性及鲁棒性强等特点使其成为近 年来网络研究的热点。然而，目前无线自组网仍然面临许多挑战，如无线传 输带宽有限、移动节点能源有限、网络拓扑结构动态变化等特点，使得自组 织网络路由成为组织网的关键和难点之一。 1 2研究目的及意义 路由是网络控制中最关键环节之一，它涉及建立和使用路由表来指导数 据通信量在网络范围内的分配活动，因此它在很大程度上决定了网络的性能。 在同等条件下，一个好的路由协议能够极大地提高网络的吞吐量并降低数据 包的传输时延。现在常用的a dh o c 路由协议主要有两种：按需路由协议和主 动路由协议心。但是，这两种路由协议都没有足够的能力来处理日益复杂的 网络问题。在网络发生拥塞时，由于协议没有较好的拥塞处理响应机制，仅 简单地对数据包进行排队或丢弃处理，而不是寻找其它较好的路由，因此无 法对网络资源进行合理充分地利用。 蚁群算法是近年来提出的一种源于大自然的仿生类算法，它主要通过蚂 蚁在寻路过程中与环境之间的信息交换实现蚂蚁群体间的信息传递，并最终 达到寻找最优路径的目的。蚁群算法的原理是一种正反馈机制，通过信息素 的不断更新最终达到收敛于最优路径，同时具有随机性、自适应性和分布式 等特点，适合并行计算和求精确解。对于解决组合优化问题和通信网络问题 有很好的应用前景。 因此，本文沿用了蚁群算法思想，并将其融入a dh o e 网络路由设计方案， 以更好的解决a dh o c 网络路由问题，提高网络的吞吐量、降低数据包的传输 时延、延缓网络拥塞，最终实现合理有效利用网络资源的目的。 西南科技大学硕士研究生学位论文第3 页 1 3国内外研究现状 1 3 1a dh o c 网络的研究现状 9 0 年代以来，移动a dh o c 网络的研究在世界范围内方兴未艾，已经从 无线通信领域中的一个小分支逐渐扩大到相对较独立的领域。目前，无论在 国际上，还是在区域上( 欧洲和亚洲等地区) ，周期性的a dh o c 网络学术会 议日益增多。总结国内外研究现状，移动自组织网络成果主要在以下几个方 面： ( 1 ) 提出新的路由协议。a dh o c 路由协议面临的主要挑战是传统的保 存在节点中的分布式路由数据库如何适应网络拓扑的动态变化。新协议一般 以广播或组播方式建立网络路由，核心是减少广播风暴。目前，一般普遍得 到认可的代表性成果有a o d v 、d s r 、o l s r 等。源头性的创新性研究主要 集中在2 0 0 1 年以前，后续的成果多为这些协议的改进。目前，路由协议的研 究仍然是a dh o c 网络成果最集中的部分。不过，从实现的难度来看，这些协 议离适用性还有一定的距离。 ( 2 ) 提出基于a dh o c 网络的媒体接入控制( m a c ) 协议幢，。主要是解 决隐藏终端和暴露终端问题，影响比较大的有m a c a 协议，即r t s c t s a c k 方案，控制信道和数据信道分裂的双信道方案和基于定向天线的m a c 协议， 以及一些改进的m a c 协议。有一些研究则是侧重于将i e e e8 0 2 1 l 的m a c 协议移植到a dh o c 网络中。基于定向天线的m a c 协议在理论上性能较为优 越，但在技术上实现难度较大。 ( 3 ) 基于a dh o c 网络的多播组播协议、t c p 协议、地址分配、功率( 节 能) 控制、安全性问题、分布式算法、q o s 等方面有些研究成果，但各部 分的数量相对较少。 1 3 2蚁群算法研究现状 蚁群算法凭借着较强的鲁棒性、优良的分布式计算机制、易于与其他方 法结合等优点，在解决许多复杂优化问题方面已经展现出其优异的性能和巨 大的发展潜力，已经吸引了国内外许多学者对其进行了多方面的研究工作。 目前国内外的许多研究者和研究机构都开展了对蚁群算法的理论和应用 研究，比如比利时布鲁塞尔自由大学的i r i d i a 实验室，瑞士的i d s i a 等都 是目前在蚁群算法研究领域较为活跃的机构。在通信网络路由问题上主要包 括如下三个方面的蚁群算法研究： 西南科技大学硕士研究生学位论文第4 页 ( 1 ) 蚁群控制系统( a n t b a s e dc o n t r o l ，a b c ) 及其衍生算法n ，； ( 2 ) 集合遗传算法的蚁群系统( a n ts y s t e mw i t hg e n e t i ca l g o r i t h m ， a s g a ) 嵋】，及s y n t h e c a 系统1 ； ( 3 ) 蚁群网络( a n t n e t ) 1 及其衍生n 儿”。 其中，前两种方法都主要应用于基于连接的电路网络，但并不适合于一 般的数据网络，且没有考虑电路交换网络的负载平衡问题。与其他算法相比， d ic a r o 等针对数据网络提出的a n t n e t ，在同等条件下使网络获得了更高的 吞吐量和更小的时延。b a r a n 和s o s a 在文献中提出了a n t n e t 的变形，并取得 了较好的结果。但上述算法存在一个所谓粘滞现象的缺陷。这是由于每个节 点都优先选择信息素高的下一个节点，若链路较长时间保持较好状态，那么 这条链路就会因为其过高的信息素导致大量的数据业务都选择这条链路，从 而造成拥塞。 国内学者所发表的蚁群算法的研究成果较少。从2 0 0 4 年起，开始有少量 成果发表，主要的成果基本上集中在协议的一些改进，包括参数设置优化研 究n 町n “、q o s n 2 h ，等，但与国外学者研究类似，多数研究还停留在理论或仿真 研究阶段“”。 1 4论文的主要工作 a dh o c 网络路由技术发展迅速、应用广泛，针对当前a dh o c 网络路由 技术发展中所遇到的难题，结合目前高效的蚁群算法，并对蚁群算法进行了 优化改进，使其适用于在无线网络中的应用。本文主要进行了以下三个方面 的工作： ( 1 ) 对蚁群算法的优化研究。蚁群算法是一种具有快速收敛性、分布式 计算等优良特性的群集智能算法，该算法在求解旅行商t s p 问题上具有很好 的表现引”，并且在求解多种优化组合问题上有着广泛的应用，如调度、二 次组合、网络路由n 等。本文在基于蚁群算法思想基础上提出了信息决策优 化机制，实现快速收敛最优路径，同时通过备份其它较优路径，以备网络拥 塞时实现负载分流。 ( 2 ) 提出了一种基于蚁群思想的拥塞规避的设计理念。目前设计的a d h o c 无线网络路由算法的方案基本都集中在同一条端到端链路中进行数据传 输，在网络负载较小的情况下路由性能不会受到太大影响，但是当网络中存 在过多的数据包时，网络的性能就会因为拥塞现象而急剧下降。所以，本文 西南科技大学硕士研究生学位论文第5 页 在吸纳了蚁群算法的思想后，类比常用无线路由协议中路由探测机制，在已 有端到端路由的前提下，监控网络链路拥塞状况，修改路由优先级以平衡网 络负载，进而以最大限度地降低网络拥塞，提高网络吞吐量。 ( 3 ) 提出了一种基于l i n u x 平台的路由框架结构。将本文提出的基于蚁 群思想的多路径自适应a d a r ( a d a p t i v ed y n a m i c a n tr o u t i n g ) 协议与l i n u x 系统平台有机融合，实现路由功能，并通过现场实验证明该路由的可行性。 本文余下章节的内容如下： 第二章对路由技术进行了简要介绍，同时阐述了两种基本的路由算法 ( d v 算法和l s 算法) ，分析讨论了当今主流的两种a dh o c 路由协议，并结 合现场实验提出其不足之处； 第三章从蚂蚁觅食现象介绍了人工蚁群算法的原理，阐述了蚁群算法模 型，并在结合第二章实验结果及吸纳蚁群算法思想基础上，提出了基于蚁群 思想的多路径自适应a d a r 路由协议，同时对算法进行了详细描述； 第四章主要论述了基于l i n u x 系统平台下的a d a r 路由协议实现。在第 三章a d a r 路由协议算法基础上，设计了基于l i n u x 平台下的a d a r 路由框 架结构，将路由功能分解在内核态和用户态下完成，实现a d a r 路由机制； 第五章对路由性能指标做现场实验测试，通过与传统a dh o c 路由协议结 果比较，证实方案的可行性； 最后对本文的工作做了总结，同时也指出本文的不足之处以及下一步还 需要做的工作。 西南科技大学硕士研究生学位论文第6 页 2a dh o e 网络路由技术 当今，a dh o c 网络路由选择问题成为当前a dh o e 技术发展所面临的一 个巨大挑战，研究高效的路由协议是必然发展的趋势。 本章针对已有的a dh o e 网络中的路由选择问题，主要进行了以下几方面 的工作：首先对a dh o c 网络路由技术进行了详细介绍；其次，简述了两种基 本路由算法( d v 算法和l s 算法) ，并就两类传统路由协议a o d v 和o l s r 进行了分析和总结；最后通过现场实验分析传统路由协议的性能指标，并对 现存路由算法的优缺点进行研究，引出本文设计目标。 2 1路由技术 路由是通信网络中的一套将业务数据从源节点引向目的节点的机制。在 传输的过程中，至少经过一个中间节点。路由与桥接的主要区别在于桥接发 生在o s i 参考协议的第二层( 链路层) ，而路由发生在第三层( 网络层) “”。 路由包含两个基本的动作：确定最佳路径和通过网络传输信息。在路由 的过程中，后者也称为数据交换。交换相对来说比较简单，而选择路径相对 复杂。 ( 1 ) 路径选择 开销( m e t r i c ) n 盯心”是路由算法用以确定到达目的地的最佳路径计量标准。 路径长度即路由跳数( h o p ) 是最常用的m e t r i c 。为帮助选路，路由算法初始 化并维护包含路径信息的路由表，路径信息根据使用路由算法不同而不同。 常用的路径信息包括：目的地址、下一跳地址、链路质量、状态标志、路由 时间等。其中目的下一跳地址对数据转发起到决定性作用，当路由器收到一 个分组，首先查询目的地址，将该分组转发给与其目的地相关联的下一跳地 址。对于存在多条路径情况，路径选择算法以选取m e t r i c 值小的为最优路径。 ( 2 ) 数据交换 交换算法相对简单，对大多数路由协议而言是相同的。多数情况下，某 主机决定向另一个主机发送数据，通过某些方法获得路由器的地址后，源主 机发送指向该路由器物理地址( m a c ) 的数据包，其协议地址是指向目的主 机的路由器查看了数据包的目的协议地址后，确定是否知道如何转发该数据 包。如果路由器不知道如何转发，通常做法是丢弃；否则，把目的地址转换 西南科技大学硕士研究生学位论文第7 页 成下一跳地址并发送。 2 2 主要关键技术 由于a dh o e 网络中节点的移动，网络拓扑结构的不断变化，无线传输带 宽有限等，传统的用于因特网的路由协议( 如r i p 、o s p f 等) 无法适应a dh o e 网络的实际需要，同时由于移动节点的计算能力和存储容量较低并且能源受 限，要求路由协议应尽量简单，这又增加了a dh o e 网络中路由协议设计的难 度。因此，在自组网的路由协议设计中采用了许多特有的技术和方法，用以 解决自组网路由的关键技术。这些关键技术乜m 1 主要包括：路由环路避免问题， 控制开销问题以及对网络动态性的适应问题。 ( 1 ) 路由环路避免问题 无论在有线网络还是无线网络，提供无环路由都是对路由协议的一项基 本要求。路由环路避免是自组网路由协议首要解决的问题。根据基本算法的 不同，对环路问题的避免也有不同的方案，目前比较成熟的路由协议有以下 几种：源路由( s r ) 协议，反向链路( l r ) 协议，基于链路状态( l s ) 的 路由协议，基于距离矢量( d v ) 的路由协议。 源路由协议和基于距离矢量的路由协议，因数据分组与路由控制分组的 头部标记有路由信息，所以其本身就具有环路避免的特征；反向路由协议， 由于有向无环图具有无环路特征，所以不会出现路由环路；基于链路状态的 路由协议在计算路由时已经获得了全部网络的拓扑信息，故也不会产生环路 问题。 所以，如果路由算法本身即具有环路避免的功能，将是更好的一种解决 此问题的方式。 ( 2 ) 控制开销的问题 自组网中无线传输带宽有限，传输控制管理分组不可避免地会消耗掉一 部分带宽资源。为了更有效地利用宝贵的带宽资源，需要尽可能地减小控制 开销。目前主要有以下几种典型的技术： 多点中继技术 在许多路由协议中，都基本上采用或部分采用了洪泛技术。减少洪泛的 开销是优化网络路由的主要方法，而按照网络最小生成树进行有选择的广播 是减少洪泛的最优方式。但是要计算网络最小生成树必须要首先知道整个网 西南科技大学硕士研究生学位论文第8 页 络的拓扑结构，这在多数情况下是不符合实际的。因此，可以通过局部链路 状态信息交换得到局部网络的拓扑结构，从而计算出局部生成树。链路状态 分组将局部生成树进行分组广播，最终扩散到全网，这样的路由开销比洪泛 方式小。 多范围技术 当自组网的规模较大时，由于传输时延和节点移动性等问题，距离节点 越远的链路状态信息准确性越差，对路由计算的意义就越小。所以采用多范 围技术来区别对待不同距离的链路状态信息。针对某个节点而言，距离自己 越远的节点，了解到关于它的路由信息越迷糊，反之，了解越清楚。根据此 原理，采用多范围技术，如f s r 中的“鱼眼”技术幢，可以达到降低路由协议 控制开销的目的。 增量消息技术 在节点间交互拓扑等信息时，可以只包含信息中变化的部分，以减少数 据分组长度，进而达到降低开销的目的。 ( 3 ) 动态性适应问题 网络拓扑的动态性是a dh o c 网络与固定网络的重要区别。网络的高度动 态性非常容易导致路由丢失。但在网络拓扑变化不是很剧烈的情况下，可以 采用一些方法来维护路由，如备份路由、路由失效节点修复及重新计算路由 等方法。在不同的路由协议中，采用了不同的路由维护方法，但主要以局部 处理为主。 2 3 基本路由算法 路由算法是通信网络的一个重要组成部分，在路由协议中起着至关重要 的作用。路由算法在很大程度上决定了网络的性能，采用何种路由算法往往 决定了最终的寻径结果。在其他条件都相同的情况下，一个好的路由算法能 够提高网络的吞吐量，降低数据的平均时延。传统的路由算法主要包括距离 向量( d v ) 路由算法及链路状态( l s ) 路由算法n “。 2 3 1d v 路由算法 距离矢量( d i s t a n c ev e c t o r ，d v ) 路由算法是一种应用广泛的动态路由 算法，曾被早期的a r p a n e t 、d e c n e t 和n o v e l l 的i p x 采纳作为路由算法， 西南科技大学硕士研究生学位论文第9 页 目前因特网中的r i p 协议和b g p 协议使用的也是这个算法。 路由问题本质上是图论中的一个问题。以节点代表路由器，边代表路由 器之间的链路，权代表链路的代价，路由的基本问题是找出任意两个节点之 间代价最小的路径。路径的代价等于组成这条路径的所有边的代价之和。 距离矢量算法解决这个问题的基本思想是：假设源节点知道自己到每个 邻居节点的链路代价( 即距离) ，以及每个邻居节点到目的节点的最小代价， 则最小代价路径问题就是求源节点的一个邻居节点，使得通过该邻居节点到 达目的节点的代价最小。可用数学语言描述： 以( y ) = m i n p c ( x ，p ) + d p c y ) p ( x ) ( 2 1 ) 其中x 和y 分别为源节点和目的节点，n ( x ) 为z 的直接邻居集合，d x ( y ) 为从x 到y 的最小代价路径的代价，e ( x ，p ) 为x 到其直接邻居p 的链路代价。 该方程称为b e l l m a n 。f o r d 方程，因此d v 算法也称为分布式b e l l m a n f o r d 算 法。 为求解此问题，d v 算法要求每个节点知道自己到所有邻居节点的距离 ( 即e ( x ，p ) ) ，这是完全可以做到的。这里的距离是一个广义的概念，可以指 到目的节点的跳数、到目的节点所需的时间、到目的节点的分组队列长度等。 若按跳数计算距离，则相邻节点间的距离等于1 ；若以延迟计算距离，则每 个节点只需和各个邻居节点交换特殊的“回声”分组，根据发送和接收到分组 的时间差就可以推算出到各个邻居节点的延迟时间；若以分组队列长度计算 距离，则只需统计去往该节点的分组数量即可。对于非相邻的节点，初始时 可假设距离为无穷大。 其次，d v 算法要求每个节点知道其邻居节点到目的节点的最小距离， 这需要通过邻居节点之间的消息交换来实现。d v 算法要求每个节点( 设为x ) 维护一张路由表，网络中每个节点在此表中占有一个表项，并以节点作为路 由表的索引。每个表项包含两部分内容：去往该目的节点( 设为y ) 的最佳 输出线路( 用下一跳节点p 进行标识) 以及估计到达该目的节点的最短距离 ( 即d ，( y ) ) 。每个节点定期地和它的所有邻居节点交换路由表中的距离列表 ( 即距离矢量) ，通报从本节点到其它各个节点的估算距离。每个节点利用从 邻居节点收到的距离矢量，使用b e l l m a n f o r d 方程更新自己的距离矢量，并 计算新的路由表。 若某个节点x 与邻居p 的距离为m ( 即e ( x ，p ) ) ，p 发布的距离矢量中p ， 表示节点p 与y 之间的距离( 即d p ( y ) ) ，则z 判断自己通过p 到达y 的距离为 西南科技大学硕士研究生学位论文第1 0 页 m + p y ；利用每个邻居节点发来的距离矢量进行同样计算，x 可以找到到达y 的最佳输出线路；同样可以找到到达所有其它节点的最佳输出线路，更新路 由表。 距离矢量路由算法简单扼要，使它在早期小规模的网络中应用广泛。在 网络拓扑相对简单且链路极少发生故障时，这种算法的效果可以令人满意； 然而，对于庞大而复杂的网络，该算法计算新路由的收敛速度极慢，即在它 进行计算过程中，网络处于一种过渡状态。再者，当网络底层链路技术多样 化时，带宽各不相同，而距离矢量算法对此规则视而不见。人们一直在努力 解决这个问题，但至今为止仍然没有一个理想的解决方案。 2 3 2l s 路由算法 l s 算法的基本思想是，每个节点利用可靠的方法获知其邻居节点以及到 各邻居节点的链路的代价，通过与网络内其它节点交换这些信息来获得关于 全网的拓扑信息，即网络中所有的节点、链路和链路的代价，将这些拓扑信 息抽象成一张带权图，然后用图论的方法计算出到各个目的节点的最短路径。 一个路由器在使用链路状态路由时，它将会向网络上所有其它的路由器 分发它到邻居路由器的距离。这就使每个路由器不用知道从某一源节点到目 的节点的开销，该路由器就可以产生一张路由表。同时，环路的问题不会出 现，因为每个路由器都拥有整个网络的拓扑。 链路状态算法，也称为s p f ( s h o r t e s tp a t hf i r s t ) 算法，其算法思路如下： ( 1 ) 发现该路由器的邻居，获取它们的网络地址，建立相邻关系，并测 量到每个相邻路由器的开销或延迟； ( 2 ) 收集将用于交换的信息，构造包含这些信息的链路状态分组。创建 链路状态分组的时机分两种，一为定期创建，另为当有事件发生时创建； ( 3 ) 通过洪泛算法，向所有的其它路由器发送该分组。如何可靠地发布 链路状态分组在链路状态路由选择算法中占用相当大的比重，链路状态算法 实现的好坏取决于洪泛算法的优劣； ( 4 ) 根据收集到的链路状态信息，通过d i j k s t r a 算法，计算本路由器到 全网其它路由器或网络的最短距离。 链路状态路由算法的优点是：迅速、无环路的收敛性，支持精确的度量 值，而且能区分内部路由与外部路由。 但是，在传统的路由算法被设计出来的时候，当时的网络规模还比较小， 路由算法的设计者可能根本没有想象到现在网络规模是如此庞大。另外，网 西南科技大学硕士研究生学位论文第1 1 页 络拓扑结构变化的频繁性和不可预测性，以及网络流量的随机性和突发性， 使得上述的这两种路由算法都不能很好地适应现在的网络，它们都没有较好 的拥塞处理响应机制，在网络发生拥塞时，该路由算法只是简单地对数据包 进行丢弃处理，而不是寻找较好的路由路径，进而造成网络吞吐量急剧下降， 因而也就无法对网络资源进行充分地利用。 2 4 传统a dh o e 网络路由协议 依据不同的标准，a dh o c 网络的路由协议有不同的分类方式。这些标准 包括基本路由算法、路由建立方式、网络逻辑结构、网络规模等。本节将以 基本路由算法为准则对a dh o e 网络路由协议分类。 依据基本路由算法的不同，自组网路由协议可分为基于链路状态( l s ) 的路由协议、基于距离矢量( d v ) 的路由协议、源路由( s r ) 协议和反向 路由( l r ) 协议n ”。 下面主要介绍两种具有代表性的路由协议，包括基于d v 路由算法的 a o d v 路由协议以及基于l s 路由算法的o l s r 路由协议，并对该传统的路 由协议进行了分析，提出了其不足之处。 2 4 1按需距离矢量路由协议 a o d v t 2 】【2 钉【2 盯( a dh o co nd e m a n dd i s t a n c ev e c t o r ) 是一种按需的距离矢量 路由协议，它根据业务需求建立和维护路由。 在a o d v 协议中，为了找到通往目的节点的路由，源节点将广播一个路 由请求分组( r r e q ) ，收到r r e q 的中间节点根据r r e q 中的信息，建立到 源节点的反向路由，反向路由条目的目的节点是广播r r e q 的源节点，下一 跳节点是将r r e q 发送给本节点的邻居节点。然后，邻居节点向周围节点继 续广播此分组直至被送到一个知道目的节点路由信息的中间节点或目的节点 本身。收到r r e q 后，中间节点如果拥有到达目的节点的有效路由，或是该 节点正是目的节点，节点会产生一个路由应答分组( r r e p ) ，沿着先前建立的 反向路由返回源节点，并建立正向的从源节点到目的节点的路由。当源节点 移动时，它会重新发起路由发现；如果中间节点移动，那么与其相邻的节点 会发现链路失效并向其上游节点发送链路失效消息并一直传到源节点，而后 源节点根据情况重新发起路由发现过程。 a o d v 路由协议是d s r 和d s d v 的结合。它借用了路由发现的基本的 西南科技大学硕士研究生学位论文第1 2 页 按需机制和d s r 中的路由维护，再加上逐条路由、序列号和d s d v 中的周 期性的信标。因此，a o d v 的优点是它可以利用多播的优势，这正是所有其 它协议所缺少的。 但是作为一种传统路由协议，在源节点处并没有存储其它备选路由，当 因链路拥塞导致网络异常时，源节点只能通过触发新轮的路由寻路过程以 建立端到端通信路由，极大地降低了网络性能。同时，路由建立也存在欠妥 之处，当且一个r r e q 控制分组到达目的节点后立即通过反馈r r e p 控制分 子建立此正向路由，对于随后的r r e q 控制分组则丢弃，这样有可能遗漏最 佳路径。 2 4 2 最佳链路状态路由协议 最佳链路状态路由( o p t i m a ll i n ks t a t er o u t i n g ) o l s r 他 【嘲1 2 町协议是专为移 动a dh o c 网络设计的。它是一个表驱动、预设式路由协议，即网络中的节点 周期性的与其它节点交换拓扑消息。o l s r 是对常规表驱动协议的改进，主 要目的是为了有效的限制a dh o c 网络中的广播。o l s r 的工作原理可简单描 述为：网络中的每个节点只选择自己邻居节点的一个子集，作为多点中继站 ( m u l t i p o i n tr e l a y , m p r ) ，只有作为m p r 的节点才能产生链路状态信息。通 过节点不断选择自己的m p r 或该节点作为其他节点的m p r 对广播信息进行 转发，并根据这些信息计算通过的最短路径，最终到达目的节点。 o l s r 路由协议是对纯链路状态算法进行优化而形成的，适用于使用“时 刻维护信息”较多并且路由请求频繁的a dh o e 网络。o l s r 路由协议中采用 多点中继思想，通过减少同一区域内相同控制分组的重复转发次数，显著减 小了自组网中广播分组数量，适用于网络规模大、节点密集、节点间通信频 繁的自组网。而且该协议还有寻路时间短的特点，并且支持扩展如睡眠模式 和多播路由等。 但o l s r 路由协议算法是适用于大型的多节点网络的，对于通信不是很 频繁的自组织网络，维护网络路由的信息相对过多，占用了较多的系统资源， 因而，设计资源占用更少，分布式计算的路由协议是目前所需。同时，同a o d v 协议一样，该协议仍然缺少有效拥塞响应机制，对于网络拥塞只是默默接受， 直至网络异常。 西南科技大学硕士研究生学位论文第1 3 页 2 5 传统路由性能指标分析 为了完成对传统路由协议的定量分析和评价，本节通过对a o d v 及 o l s r 传统协议进行性能指标测试，以近一步认识传统路由协议对网络性能 的影响。 2 5 1 路由协议测试方法 对于无线网络路由协议的测试和评定现主要有两种方式：网络模拟和真 实环境运行。 网络模拟虽具有操作可重复性、可以模拟大规模的网络等优点，在a d h o e 网络移动性测试和协议的评价中应用较广，但正确的模拟结果依赖于模 型质量。通常情况下，模拟器建立的模型都较简单，很难正确地反映真实现 象。例如，物理层的无线传播模型在模拟时，两节点间的传播强度是平缓的。 而实际上，在真实环境中，如障碍物或者多路径等无线传播现象小的变更都 会引起较大的信号强度的变化。模拟的另一个缺点是模拟器不随着最新路由 协议的发展而更新。例如，在n s 2 模拟器他叫丁仅提供了i e e e 8 0 2 1 1 的模型， 没有对i e e e 8 0 2 1 1 协议族中其它模型的支持，如i e e e 8 0 2 1 1 b 等。 而真实环境测试可以真实反映网络现象，但也有其不足之处，测试难重 复性和结果较难重演。 综合考虑上述两种方式优缺点，本文选用真实环境测试的方式来评定路 由协议性能。 2 5 2性能指标 评定一种路由协议的性能有许多标准，通常包括定性指标和定量指标两 个方面。定性指标从整体上对网络某个方面的性能进行描述，如安全性、分 布运行性、提供无环路由、是否对单信道支持等；定量指标则可以更细致的 刻画网络某方面的性能，对此可以参见r f c 2 5 0 1n ”，该文档提出了许多评价 标准。 结合实际条件，本文将测试以下三个性能指标：吞吐量、数据包成功递 交率及往返时延。 ( 1 ) 吞吐量 单位时间内在信道上成功传输的信息量定义为吞吐量，即指单位时间内 成功传送的无差错通信量。 西南科技大学硕士研究生学位论文第1 4 页 ( 2 ) 数据包成功递交率 其值为应用层源节点发送的分组数目与目的节点接收分组数目之比。描 述的是通过应用层观察到的数据报文的丢失率，反映了网络所支持的最大吞 吐量，它是路由协议完成性和正确性的指标。 数据报成功接收率= 成功接收分组数发送分组数一丢弃分组数 夏萄疆两_ 5 1 殛蕊 ( 3 ) 往返时延r t t ( r o u n d - t r i pt j 功e ) “” 表示从发送端发送数据开始，到发送端接收到来自接收端的确认( 接收 端收到数据后便立即发送确认) ，总共经历的时延。一般通过p i n g 指令完成 网络往返时延测试。 2 53 实验环境 ( 1 ) 硬件平台 实验巾，各节点由h p 笔记本电脑、d e l l 笔记本电脑、移动智能小车及 p c i 0 4 ( 台湾研华p c m 3 3 8 6 ) 组成，并配有可支持i e e e 8 0 21 l b 协议的c i s e o a i r p c m 3 5 0 无线网卡( 物理带宽1 i m ) ，网卡有效通信半径约为2 0 0 m 2 5 0 m 。 圈2 - 2 所示为移动智能小车。其中，智能小车内配有p c i 0 4 硬件平台( 如 图2 - 1 所示) 且小车移动速率可控，最大速率约为2 m s 。图2 - 3 所示为模拟 移动智能体由笔记本电脑充当。 冒2 - ip ol 0 4 耍验硬件平台 f i g2 、1 p c i0 4 h ar d w a r ed la t f o r m 图2 - 2移动智能小车 f i g2 - 2 t h e i r i t e | | i g e n tm o b io v e h lc i e 西南科技大学硕士研究生学位论文第1 5 页 图2 - 3模拟移动智雒体 f i g2 - 3 t h oi m t a t io no fm o b ii ea g e n t ( 2 ) 软件平台 分别采用由瑞典u p p s a l a 大学研制的a o d v u u “及u n i k * u n i v e r s i t y g r a d u a t ec e n t e r 研发的o l s r c l ”作为a dh o e 路i = f 实验平台，除此之外还需其 它软件辅助实骑，包括自t 研发的s e n d u d p 恒速发包软件及e t h e r e a l ( a n e t w o r kp a c k e ts n i f f i n gt 0 0 1 ) 数据包嗅探软件”“。 e t h e r e a l 鉴于真实环境测试方式，本文选用当前较流行的e t h e r e a l 数据包嗅探软 件实现对a dh o e 网络路由性能的实验分析。e t h e r c a i 是一个宵g u i 的网络嗅 探器支持l i n u x 及w i n d o w s 操作平台，能够完成与t c p d u m p 相同的功能， 并具有友好的操作界面，如图2 - 4 所示。 图2 - 4 e t h e r e ai 软件操作界面 f i g2 - 4 t h en t e r f a e eo fe t h e r b a ls o f t w a r e 西南科技大学硕士研究生学位论文第1 6 页 e t h e r e a l 和t c p d u m p 因都依赖p c a p 库( 1 i b p c a p ) ，因此两者在许多方面 有相似之处，如都使用相同的过滤规则和关键字等。通过e t h e r e a l 调制网卡 参数为混合模式，即可捕捉网络中所有数据分组同时借助过滤规则可毗 进行协议及数据包相关数据分析，如数据包大小、数据