（通信与信息系统专业论文）linux系统下olsr路由协议研究及实现.pdf

摘要 摘要 最优化链路状态路由协议( o l s r ，o p t i m a ll i n ks t a t er o u t i n g ) 是a dh o c 网 络的经典主动路由协议，它简单、实用且性能优越。本文深入研究o l s r 协议的 工作原理，在l i n u x 系统下实现了o l s r 协议，进而针对o l s r 协议的路由选择 算法，提出一种有效的协议改进方案。 本文首先阐述o l s r 路由协议在l i n u x 系统下的实现方案。在深入剖析o l s r 路由协议的工作原理的基础上，结合l i n u x 操作系统的特点提出实现o l s r 路由 协议的总体设计方案。围绕总体设计方案，针对实现过程中遇到的具体困难，本 文介绍了解决问题的关键技术。实验证明o l s r 协议的实现方案是正确可行的， 它遵循o l s r 协议基本的工作原理，自动适应网络拓扑结构的动态变化，支持节 点的添加、删除和移动，并能准确而快速的传输i p v 4 和i p v 6 编址方式的数据。 在o l s r 路由协议实现基础上，本文利用多路径机制和带宽感知改进o l s r 协议，提出s r m s b o l s r 方案。s r m s b o l s r 同时提供多路径带宽感知路由和 单路径带宽感知路由。单路径带宽感知路由算法以跳数为选路的主要依据，同时 考虑带宽因素的影响，在最短可达路径集中选择带宽最宽的路径作为最优路由。 同o l s r 协议类似，s r m s b o l s r 通过单路径带宽感知路由算法计算去往全网所 有节点的单条最优路由。多路径路由算法在单路径带宽感知路由算法的基础上引 入多路径机制，为业务流提供多条通往目的地的不相交路径。s r m s b o l s r 还借 助源路由机制和加权分配的循环调度算法，保证业务流按比值精确地分配到多条 路径上并行传输。实验证明，与o l s r 协议相比，在网络业务负载较重的情况下， s r m s b o l s r 提供的单路径带宽感知路由能感知相同跳数下负载较轻的路径，避 免新的数据流仍然通过负载重的路径传输，从而降低数据包的丢包率，减少传输 延时；多路径带宽感知路由不仅降低了数据传输的丢包率，还有效均衡了网络负 载。 关键词：o l s r 协议，带宽感知，多路径路由，源路由机制 a b s t r a c t a b s t r a c t t h eo p t i m a ll i n ks t a t er o u t i n gp r o t o c o l ( o l s r ) i sd e v e l o p e df o rm o b i l ea dh o c n e t w o r k s ( m a n e t ) i to p e r a t e sa sat a b l ed r i v e na n dp r o a c t i v ep r o t o c 0 1 o l s ri s s i m p l eb u tp e r f o r m sw e l li nm a n e t t h i sm a s t e rt h e s i sd e a l sw i t l lt h ei m p l e m e n t a t i o n o fb a s i co l s ra n di m p r o v e ds r m s b o l s ru n d e rl i n u xo s c o n s i d e r i n gt h eb a c k g r o u n do fm o b i l ea dh o cn e t w o r ka n dp r i n c i p l e s o fo l s r r o u t i n gp r o t o c o l ，ac o n c r e t es c h e m ea b o u to l s ri m p l e m e n t a t i o nu n d e rl i n u xo sw a s p r e s e n t e d i na d d i t i o n ，s e v e r a lk e yt e c h n o l o g i e st os o l v ed i f f i c u l t i e se n c o u n t e r e dd u r i n g t h ei m p l e m e n t a t i o no fo l s rw e r ed e t a i l e d t h e nw eb u i l tt e s tb e d sa r o u n do u r l a b o r a t o r y a n dt e s t e do l s ri m p l e m e n t a t i o n t h er e s u l t sp r o v e dt h a to l s r i m p l e m e n t a t i o n , w h i c hs u p p o r t sb o t hi p v 4a n di p v 6 ，i sf e a s i b l ea n de f f i c i e n t c o n s i s t e n t w i t ht h e b a s i cp r i n c i p l e so fo l s i lt h ei m p l e m e n t a t i o np r o p o s e dc a na d a p td y n a m i c n e t w o r kt o p o l o g yc h a n g e sd u et oa p p e a r a n c e ，d i s a p p e a r a n c eo rm o b i l i t yo ft h en o d e si n t h en e t w o r k b a s e do nt h eo l s ri m p l e m e n t a t i o na n dq o s - a w a r em u l t i p a t hr o u t i n gs c h e m e sa t h o m ea n da b r o a d ，a l li m p r o v e ds r m s b - o l s rs o l u t i o nw h i c hi n t e g r a t e sm u l t i p a t ha n d b a n d w i d t h a w a r em e c h a n i s m sw a sp r o p o s e d s r m s b - o l s rs o l u t i o no f f e r sb o t h s i n g l e p a t ha n dm u l t i - p a t hb a n d w i d t h a w a r er o u t i n gs e r v i c e s i m i l a rt oo l s rp r o t o c o l ， t h er o u t i n gt a b l e sa r eb u i l tb yt h es i n g l e - - p a t hb a n d w i d t h - a w a r er o u t i n ga l g o r i t h mw i t h t h eo b je c t i v eo fm i n i m i z i n gt h eh o p sa n db a n d w i d t hb o t t l e n e c ko fe a c hp a t h a n dt h e m u l t i - p a t hb a n d w i d t h a w a r er o u t i n g ，i m p r o v e do ns i g n a l - p a t hb a n d w i d t h a w a r er o u t i n g a l g o r i t h m ，c o u l df i n dm u l t i p l ed i s j o i n t - p a t h st ot h es a m ed e s t i n a t i o n t h u s ，c o m b i n i n g w i t hs o u r c er o u t i n ga n dw e i g h tr o u n d r o b i na l g o r i t h m ，n e t w o r kt r a f f i cc a nt a k em u l t i p l e d i s jo i n t - p a t h st or e a c hi t sd e s t i n a t i o n a f t e ri m p l e m e n t a t i o n ，w et e s t e db o t hs o l u t i o n si n r e a lm a n e te n v i r o n m e n t t h er e s u l t sd e m o n s t r a t e dt h a ts r m s b o l s rs o l u t i o nc a n i m p r o v et h ep e r f o r m a n c eo fn e t w o r k t r a f f i ct r a n s m i s s i o na n dl o a db a l a n c e k e y w o r d s ：o l s rp r o t o c o l ，b a n d w i d t ha w a r e ，m u l t i p a t hr o u t i n g ，s o u r c er o u t i n g 缩略词 a n s n a o d v a p b d m b g p b m u c b q d b - d i j k s t r a d p s p d s r f s r g p s m a c e t ： m b d i i k s t r a m i r o m p l s m p r n d m r o l s r q o s s d m s r s r m p o l s r s r m s b o l s r t c t c p 缩略词 a d v e r t i s e dn e i g h b o rs e q u e n c e n u m b e r a dh o co nd e m a n dd i s t a n c ev e c t o r a c c e s sp o i n t b a n d w i d t h c o n s t r a i n e dd e l a y o p t i m i z e d m u l t i p a t h b o r d e rg a t e w a yp r o t o c o l b a n d w i d t h - a w a r em u l t i p a t h _ u s i n g 1 y a 伍c c l a s s b a s e dq u e u i n g d i s t a n c eb a n d w i d t ha w a r ed i j k s t r a d i s j o i n tp a t h s e ts e l e c t i o np r o t o c o l d y n a m i cr o u t i n gp r o t o c o l f i s h e y es t a t er o u t i n g g l o b a lp o s i t i o ns y s t e m m e d i aa c c e s sc o n t r o l m o b i l ea dh o cn e t w o r k m u l t i p a t hb a n d w i d t ha w a r ed i j k s t r a m u l t i p a t hi n t e r - d o m a i nr o u t i n g m u l t i - p r o t o c o ll a b e ls w i t c h i n g m u l t i p o i n tr e l a y n o d e - d i s j o i n tm u l t i p a t hr o u t i n g o p t i m a ll i n ks t a t er o u t i n g q u a l i t yo fs e r v i c e s e c u r e ，d i s j o i n t ，m u l t i p a t hs o u r c e r o u t i n gp r o t o c o l s o u r c er o u t i n gb a s e dm u l t i p a t h o l s r s o u r c er o u t i n gb a s e dm u l t i p a t h s e l e c t e db a n d w i d t h a w a r e0 l s r t o p o l o g yc o n t r o l t r a n s m i s s i o nc o n t r o lp r o t o c o l v i 广播邻居节点序列号 按需距离矢量路由 接入点 带宽受限、延时最小的多 路径 边界网关协议 使用多路径带宽感知的 业务流 基于类队列 距离带宽感知最短路算 法 独立路径集选择协议 动态路由协议) 等协议 鱼眼状态路由 全球定位系统 媒体访问控制 移动a dh o c 网络 多路径带宽感知最短路 算法 域间多路径路由 多协议标签交换 多点中继节点 节点独立的多路径路由 最优化链路状态路由协 议 服务质量 安全、不相交的多路径源 路由协议 基于源路由和多路径的 o l s r 协议 基于源路由的、可选多路 径带宽感知o l s r 拓扑控制 传输控制协议 缩略词 t o r a w r p t e m p o r a l l y o r d e r e dr o u t i n g a l g o r i t h m w i r e l e s sr o u t i n gp r o t o c o l v i i 暂时有序的路由算法 无线路由协议 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：至童 日期：年月日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：i 虹导师签名： 日期：年月日 第一章绪论 1 1 研究背景和课题意义 第一章绪论 人们对随时、随地通信的追求使得无线网络技术在近几年迅速发展。无中心 网络，又称a dh o e 网络【l j ( m a n e t ：m o b i l ea dh o cn e t w o r k ) ，是没有任何固定基 础设施可依赖的无线网络。a dh o e 网络常常用于灾难救助、偏远或不发达地区通 信或临时通信等。例如，在发生洪水、地震后，有线通信设施因遭受破坏而无法 使用，这时借助a dh o c 网络，可以快速地建立应急通信，保证救援工作顺利进行， 完成紧急通信任务。又如在商务会议中，参会人员之间需要通信交流，在有线通 信系统不能满足通信需求的情况下，a dh o e 网络可以帮忙完成通信任务。 a dh o e 网络中没有固定设备，移动节点既扮演着通信终端的角色，同时又承 担着路由任务。节点间的通信需要中间节点的多跳转发，无线信道的不规则变化、 节点的移动、加入和退出等操作都会会引起网络拓扑结构的动态变化，因此需要 专门的无线路由协议来保证网络的连通。a dh o c 网络无线路由协议的作用就是在 这种环境中，监控网络拓扑结构的变化，创建和维护到达目的节点的路由，保障 端到端的正常通信。 目前，大量研究从理论和仿真上证明了已有的无线路由协议具备为a dh o e 网 络提供路由功能的能力。如何在实际的a dh o c 网络中实现这些无线路由协议具有 非常重要的现实意义。另外，随着网络技术的不断发展，用户对网络的要求从单 一的连通性需要向数据、语音和视频综合服务需要转化。近年来，关于q o s 约束 路由、多路径路由、能量感知路由、负载均衡及网络安全性等方面的研究逐渐增 多。研究如何利用网络现有的资源，改进已有的无线路由协议，使之为用户提供 更优秀的通信质量，对网络的进一步发展具有深远的意义。 1 2 主要工作 为了正确、成功地将o l s r 协议用于实际的a dh o c 网络，本文结合o l s r 协 议的工作原理和l i n u x 操作系统的网络体系结构，提出了一套在l i n u x 系统下实现 o l s r 协议的新方案。为了进一步提高网络的传输性能、提升网络的服务质量、均 电子科技大学硕士学位论文 衡网络的负载，本文设计了一种o l s r 协议的多路径带宽感知改进方案。本文主 要对以下几方面进行了研究。 研究无线移动a dh o e 网络，掌握无线移动a dh o e 网的定义和网络的特 点。 论述a dh o e 网络无线路由协议，比较和分析了平面路由协议和分级路由 协议、先验式路由协议和反应式路由协议的特点及优缺点。 深入研究和分析了o l s r 路由协议的工作原理，提出在l i n u x 系统下实现 o l s r 协议的一种新方案。根据l i n u x 操作系统路由体系结构的特点，设 计o l s r 协议实现的整体框架，描述实现o l s r 协议的程序架构，介绍了 在这种架构中实现协议的关键技术。 在o l s r 路由协议实现基础上，利用多路径机制和带宽感知改进o l s r 协 议，提出s r m s b o l s r 方案。在提供基于目的地址、逐跳转发策略的单 路径路由的同时，还能提供多路径带宽感知路由，并且在源路由机制和加 权分配的循环调度算法的协助下，实现在多条路径上并行传输数据。 搭建实验平台，对o l s r 实现及o l s r 协议的改进方案( s r m s b o l s r ) 进行一系列的测试。分析实验结果，证明o l s r 协议的设计方案是可行的 和正确的；验证s r m s b o l s r 有效地均衡了网络负载，提高了网络资源 利用率，改善了网络性能。 1 3 论文组织 论文的内容安排如下： 第一章介绍本文的研究背景和研究价值，同时概述本文的主要内容和章节安 排。 第二章概述无线移动a dh o e 网络；介绍a dh o e 网络主要的路由协议分类情 况。 第三章集中阐述o l s r 路由协议的工作原理和实现方案，对o l s r 路由协议 的原理、实现框架及关键技术等做了详细说明。 第四章探索基于o l s r 协议的多路径路带宽感知路由选择算法，结合o l s r 路由协议、多路径机制和带宽感知，提出o l s r 多路径改进方案( s i 洲s b o l s r 方案) 。从而有效地均衡了网络负载，提高了网络资源利用率，改善了网络性能。 第五章搭建实验平台做测试。先对o l s r 实现进行功能测试和性能测试，证 2 第一章绪论 明o l s r 实现方案的正确性和可行性。然后，对比测试了o l s r 协议的改进方案 ( s r m s b o l s r ) 和o l s r 协议组网下的网络传输性能和负载均衡情况，对比并 分析实验结果，得出结论。 第六章全面总结本文所做工作，展望未来的研究方向。 电子科技大学硕士学位论文 第二章无线自组织网络路由协议 本章将研究无线移动a dh o e 网络及其路由协议。首先阐述a dh o c 网络的定 义和特点，然后描述典型的a dh o c 网络路由协议，最后说明实验平台使用的通信 协议体系及编址方案。 2 1a dh o e 网络概述 a dh o e 网络【l 】是移动终端通过无线链路组成的自治系统，是没有任何固定基 础设施可依赖的无线网络，又称为多跳移动无线网( m u l t i - h o pm o b i l ew i r e l e s s n e t w o r k ) 、移动节点能自由移动，可以装配在个人、卡车、小汽车中。a dh o e 网 络常常用于灾难救助、偏远或不发达地区通信或临时通信等。与普通的移动网络 和固定网络相比，a dh o e 网络中的移动节点既是主机又是路由器，节点在处理本 节点通信的同时，还需要为网络中的其他节点中继数据。 与普通的移动网络和传统固定网络相比，a dh o e 网络具有抗毁能力强、能量 和处理能力有限、拓扑动态变化、带宽资源稀有和数据丢失率高、链路不可靠等 特点【3 j 。由于这些特点，a dh o e 网络的无线路由协议设计比普通的移动网络和传 统的固定网络面临更多的挑战。 抗毁能力强。a dh o c 网络不依赖任何现有有线和无线网络设施。a dh o e 网络具有对等性。网络中的节点地位平等，没有严格的a p 节点来控制网 络通信。网络支持移动通信网络的自主构建、自主组织和自主管理，不需 要任何现有有线和无线网络设施的支持。通过分层协议和分布式算法的协 调，节点开机后能自动地探测邻居信息，进而迅速的建立网络。正是由于 a dh o e 网络无中心、自组织的特点，单个节点的故障对于全网络的稳定 性不会产生大的影响。因此，a dh o e 网络具有很强的抗毁性能。 能量和处理能力有限。在a dh o c 网络中，节点的电池能量、c p u 资源和 存储能力均有限。在设计路由协议和服务的时候，需要考虑这些限制条件。 a dh o e 网络节点除了具有终端功能外还要具备路由功能，正在转发其它 节点通信的节点由于没有电量而导致通信的中断，因此，能量和处理能力 的限制对a dh o e 网络的影响远远大于蜂窝网络的手机和无线局域网络。 4 第二章无线自组织网络路由协议 拓扑动态变化。节点的移动性使得a dh o e 网络具有动态拓扑性。网络节 点任意移动，随时开机或关机，网络的拓扑结构也随之发生变化。在动态 变化的拓扑上建立端到端的连接具有巨大的挑战性 带宽资源稀有。与现在具有丰富带宽资源和可靠链路的有线网络不同， a dh o e 网络无线带宽资源有限。因此，无线路由协议的一个关键考虑因 素就是节省协议开销。尽管蜂窝网络和无线局域网也存在带宽稀缺的问 题，但是它们的带宽限制问题仅限于数据链路的“接入”部分。例如从手 机到蜂窝基站或者是从便携电脑和其他8 0 2 1 1 设备到无线接入点的网络 带宽有限问题。而a dh o e 网络中的所有链路都存在着这个问题。 数据丢失率高、链路不可靠。与传统固定网络不同，数据丢失率高和链路 质量不可靠是a dh o e 网络的常态而不是偶然事件。这使得现有固定网络 协议的很多基础假设条件都不再成立。例如，t c p 协议最初设计时的一个 假设是任何报文丢失都是由网络拥塞引起的。因此，当报文丢失的时候， t c p 就会依据拥塞控制机制来减少发送窗口。但是，这对于a dh o e 网络 却不再适用。 2 2a dh o c 网络典型路由协议 图2 - 1a dh o e 网络典型路由协议分类 设计适用于a dh o e 网络环境特点的路由协议【5 】是建立a dh o e 网络的关键， 也是国内外研究的热点问题。支持i n t e m e t 网络的传统路由算法，如距离矢量路由 选择算法和链路状态路由选择算法，无法适应a dh o c 网络的需要。a dh o e 路由 协议需要具备感知网络动态拓扑、维护网络连接、高度自适应的能力。近几年， 国内外学者相继提出各具特色的无线路由协议，其中经典的有o l s r e 6 1 、f s r ( f i s h e y es t a t er o u t i n g ，鱼眼状态路由) 和w r p ( w i r e l e s sr o u t i n gp r o t o c o l ，无线 5 电子科技大学硕士学位论文 路由协议) a o d v ( a dh o co nd e m a n dd i s t a n c ev e c t o r ，按需距离矢量路由) 、d s r ( d y n a m i cr o u t i n gp r o t o c o l ，动态路由协议) 等协议。图2 1 对现有的无线a dh o c 网路由协议进行分类：根据是否使用g p s 系统( g l o b a lp o s i t i o ns y s t e m ，全球定位 系统) 作为路由辅助条件，分为地理定位辅助路由协议和非地理定位辅助路由协 议；根据网络逻辑结构，分为平面路由协议和分级路由协议；根据发现路由的策 略，又可分为先验式路由协议和反应式路由协议。 2 2 1 平面路由协议和分级路由协议 根据网络逻辑结构，分为平面路由协议和分级路由协议。如图2 2 中，图a 展 示的是平面路由协议组建的a dh o c 网络，而图b 则是在相同情况下的分级路由协 议组建的a dh o c 网络。 图a 为根据平面路由协议组建的a dh o c 网络，可以看到，该网络具有平面结 构。平面结构的a dh o c 网络最大的特点是各个节点功能相同，地位相等。正是由 于节点的对等性，平面路由协议的优点为在理论上不存在瓶颈。组建的网络较为 健壮，鲁棒性好，也不需要移动性管理。平面路由协议的最大缺点是可扩展性较 差，网络规模受限。随着网络规模的不断扩大，平面路由协议用于路由维护的开 销将会变得很大。当网络规模达到一定程度后，有限的网络带宽资源可能支持最 基本的路由协议开销都十分困难。 o a dh o c 网络节点 表示节点间链路 a 平面结构网络 簇头。 簇成员 表示簇头间链路表示簇成员间链路 b 二级结构网络 图2 2 平面结构v s 分级结构 与平面路由协议相对的是分级路由协议。对于分级路由协议，网络节点按照 某种分群算法将网络划分为多个簇，图b 中的一个虚线圈代表一个簇。每个簇包 含一个簇头( c l u s t e r - h e a d e r ) 和多个簇成员( c l u s t e r - m e m b e r ) 。簇头相对稳定、性 6 第二章无线自组织网络路由协议 能较好，他们又组成高一级的网络( 图b 中粗线连接构成的网络) 。任意两个位于 不同簇的簇成员之间要进行通信，需要簇头帮忙转发报文。而同一簇内的簇成员 通信则由簇成员独立完成。分级路由协议的优点是可扩展性好，适合大规模节点 组网的情况。当需要扩展网络容量时，可以通过增加簇的个数和提升簇的级数来 实现。这种组网方式的缺点是簇头是网络的枢纽，它们的可靠性和稳定性将决定 网络的整体性能，因此分级路由协议的抗毁性能不如平面路由协议。并且为支持 节点在不同分群之间漫游，分级路由协议会产生一定的移动性管理。 2 2 2 先验式路由协议和反应式路由协议 本节将从路由发现策略角度讨论无线路由协议。根据数据发送需要路由时， 是否已经存在到达目的地的路由，路由协议分为先验式和反应式两种协议。 先验式( p r o a c t i v e ) 路由协议是基于路由表的路由协议，故又称为表驱动路由 协议( t a b l e d r i v e nr o u t i n gp r o t o c 0 1 ) 。其特点为各个节点周期性交互拓扑信息，维 护一张或多张信息表，获知去往全网所有节点的路由。移动节点掌握到达全网所 有节点的路由，但是并不关心是否需要这些路由进行通信。这一特点使得先验式 路由具有传输延时小的优点，当需要向某目的节点发送数据分组时，只要路由表 中存在去往该目的节点的路由，就能立即传输数据。它的缺点是为了使路由更新 准确及时的反映当前网络拓扑，路由协议开销较大。严重的时候，路由将始终处 于不收敛状态。典型的先验式路由协议有：o l s r 6 1 、f s r 和w r p 。 反应式( r e a c t i v e ) 路由协议，是当且仅当需要路由时，源节点才创建到达目 的地的路由，故又称为按需路由协议( o n d e m a n dr o u t i n gp r o t o c 0 1 ) 。反应式路由 协议的连接和路由表内容是按照分组传输需要建立的，节点仅仅掌握通信需要的 那部分网络拓扑和路由信息。因此，从发起通信到结束通信的过程中，路由协议 需要完成路由发现、路由维护和路由拆除三部分工作。这样的发现和维护路由的 优点是不需要周期性地广播拓扑信息，从而大大节省了有限的网络带宽资源。然 而与先验式路由相比，数据分组的发送延时因路由发现过程而增长。典型的反应 式无线移动路由协议有：a o d v 、d s r 和t o r a 。 2 3 通信协议体系与编址 本节介绍本文中使用的通信协议体系及编址方案。为了保证搭建的a dh o c 网 络的通用性和可扩展性，o l s r 协议及其改进在实现上均采用标准的t c p i p 协议 7 电子科技大学硕士学位论文 体系和i p 编址方式。 2 3 1 通信协议体系 为了实现移动a dh o c 网络与i n t e m e t 网络的互联互通，本文选定标准的t c p i p 协议体系作为无线a dh o e 网的通信协议体系。本文中，无线a dh o e 网的通信协 议体系如图2 3 。移动节点均采用支持8 0 2 1 l b 协议7 1 的无线网卡来进行通信，竞 争共享物理信道。虽然o l s r 路由协议控制信息的交互需要借助于u d p 端口完成， 但是o l s r 路由协议选出的路由却作用于网络层，直接影响数据的发送和转发。 另外，移动节点数据的发送和接收等应用程序都是在应用层实现。 移动节点移动节点 应用层 传输层 网络层 链路层 物理层 2 3 2i p 编址 应用服务应用服务 t c p 厂l m p 协议 t c p u d p 协议 a dh o c 路由 卜 a d h o c 路由 i p 协议 i p 协议 8 0 2 1 l b 协议 8 0 2 11 b 协议 无线信道 卜 无线信道 图2 3 移动a dh o e 网络的通信协议体系 本文规定，a dh o c 网络中的移动节点均采用叫8 】编址方式，使用不同的i p 地 址来标识不同的节点。为了适应网络的发展，o l s r 协议的实现同时支持i p v 4 地 址和i p v 6 地址。 2 3 2 1i p v 4 编址 i p v 4 地址的长度是3 2 位，它唯一、普遍地定义在i n t e m e t 上的主机或路由器。 i p v 4 地址有二进制和点分十进制两种表示形式。i p v 4 地址的二进制表示由3 2 位1 和0 构成。点分十进制表示则使用圆点来分隔4 个十进制数( 0 2 5 5 ) ，每个十进 制数为一个8 位组，代表二进制表示形式中的8 位。相比之下，点分十进制表述 简单，易于记忆。因此，通常习惯使用p v 4 地址的点分十进制表示形式，如 1 9 2 1 6 8 8 1 2 。在分类编址中，i p v 4 的地址空间分为a 、b 、c 、d 和e 五个类。无 论是二进制还是点分十进制表示形式，可以通过i p v 4 地址的前几个比特或第一个 8 第二章无线自组织网络路由协议 字节的数值立即确定该地址的类。在分类编址的a 类、b 类和c 类地址中，i p v 4 地址可以划分为子网号( n e t i d ) 和主机号( h o s t i d ) 。i p v 4 地址支持单播通信、多 播通信和广播通信。单播通信为一个端点向另一个端点发送分组，多播通信为一 个端点向多个端点同时发送分组，广播通信是一个端点向其所在的网络中的所有 节点发送分组。 2 3 2 2i p v 6 编址 和i p v 4 相比，p v 6 具有更大的地址空间。i p v 6 的地址长度是1 2 8 位，是i p v 4 地址长度的4 倍，而地址空间则增大2 9 6 倍。i p v 6 地址采用冒号十六进制表式，1 2 8 位地址按每1 6 位为1 段，每段四个十六进制数，段与段之间以“：”隔开，例如： f e c o ：0 1 0 6 ：2 5 0 0 ：0 0 0 0 ：0 0 0 0 ：0 0 0 0 ：o o o o ：0 0 0 1 。i p v 6 地址很长，在实际使用时，往往对 上述地址进行缩短。每个段中开始的零可以删除，多个为零的段可以缩写为双冒 号“：；一个地址只能使用一个“：”，否则无法确定每个“：”代表多少位零；通 常在为零的段最多的地方使用“： ，如果包含相同长度的两个零段，则将左边的 零段表示为“： 。例如前面的i p v 6 地址就可以表示为f e e 0 ：1 0 6 ：2 5 0 0 ：1 。 i p v 6 定义了三种类型的地址，即单播地址、多播地址和任播地址。单播地址标 识单个主机或路由器；多播地址和任播地址都标识一组计算机，不同的是多播通 信为一个端点向组中的所有端点发送分组，而任播通信为一个端点向组中离它最 近或最容易到达的一个端点发送分组。 2 4 本章小结 本章研究了无线移动a dh o c 网络及其路由协议。在概述了a dh o c 网的定义 和特点的基础上，介绍了a dh o c 网络无线路由协议，比较和分析了平面路由协议 和分级路由协议、先验式路由协议和反应式路由协议的特点及优缺点。最后，说 明本文中无线路由协议的通信协议体系及编址方案。 9 电子科技大学硕士学位论文 第三章o l s r 协议的实现 本章设计了一套在l i n u x 操作系统下实现o l s r t 9 加】协议的方案。本章将阐述 o l s r t 6 】协议原理，详细介绍o l s r 实现方案的设计思想、整体框架及关键技术。 3 1o l s r 协议描述 o l s r 6 】协议，即最优化链路状态路由协议，是由i e t fm a n e t 工作组提出的 典型的先验式路由协议，其路由发现策略与传统路由协议类似。通过在全网范围 内周期性地交换网络拓扑信息和链路状态信息，o l s r 协议的每个节点都掌握了全 网拓扑图的最新信息。移动节点运用d i j k s t r a 算法，在已有的网络拓扑图的基础上， 主动发现去往网络中其它节点的路由。链路状态信息洪泛将会引起路由开销， 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 协议的邻居发现和 拓扑扩散这两个主要功能做进一步描述。 3 1 1 邻居发现 为了检测本节点与周围邻居的链路情况，o l s r 协议规定各个节点周期性地发 送h e l l o 消息。每隔“h e l l oi n t e r v e l ”周期，移动节点就会广播一次h e l l o 消 息，来更新网络拓扑信息。h e l l o 消息包含着本节点的邻居及其链路状态信息。 通过h e l l o 消息的周期性地交互，各个节点不仅知道自己的邻居信息，还能知道 两跳邻居。拥有邻居和两跳邻居信息后，移动节点独立选择本节点的m p r 。m p r 为邻居节点集中，能覆盖所有两跳邻居节点的个数最少的那些节点。h e l l o 消息 只在一跳范围内广播，邻居节点收到h e l l o 消息处理后立即丢弃，不再进行转发。 3 1 1 1 邻居表表项状态转移图 o l s r 协议中，移动节点及其邻居节点的无线链路状态主要包括有：非对称链 1 0 第三章o l s r 协议的实现 路( a s y mn e i g h ) 、对称链路( s 讧n e i g h ) 、m p r 链路( m p rn e i g h ) 和 失效链路( l o s tn e i g h ) 。邻居表表项状态转换情况如图3 1 ，对于邻居表，除 了上面描述的邻居无线链路状态外，还有一种状态为不存在该表项( n o n e i g h ) 。 1 代表收至j j h e l l o 帧并且h e l l o 帧中有本节点且本节点的链路质量为 s y m n e i g h 、a s y m n e i g h 或者m p r _ n e i g h 2 代表收至i j h e l l o 帧& & h e l l o 帧中没有本节点 3 代表收至u h e l l o 帧& & h e l l o 帧中有本节点，但本节点为l o s t _ n e i g h 图3 1 移动节点邻居表表项状态转移图 从图3 1 中可以看出：o l s r 协议周期性交互h e l l o 消息主要是侦听邻居节 点无线链路的对称性；m p r 选举算法则负责将一部分对称链路( s y mn e i g h ) 选择成为连接m p r 的链路( m p rn e i g h ) ，用以扩散全网拓扑信息；而a s y m 定时器、s y m 定时器和n 定时器主要用于邻居表项的过期。a s y m 定时器、s y m 定时器和n 定时器都是邻居表表项的定时器，一个表项设置三个定时器是邻居表 项独特之处，具体功能为： s y m 定时器：s y m 定时器到时后，该表项的状态设置为l o s tn e i g h ， 更新本节点的两跳邻居表、m p r 表、m p rs e l e c t o r 表、拓扑表。 a s y m 定时器：a s y m 定时器到时之后，则将该表项的状态设置为 l o s tn e i g h 。从图3 1 中可以看到之前该表项的状态为a s y mn e i g h ， 没有参与到路由选择，故此处不需要更新其他相关表项。 电子科技大学硕士学位论文 n 定时器：该定时器到时后，则删除该表项，表项状态回归为n o n e i g h 。 3 1 1 2 两跳邻居表表项状态转移图 h e l l o 消息不仅使得各个节点知道自己的邻居信息，还知道两跳邻居信息。 两跳邻居表表项的状态转换情况如图3 2 。从图中可以看到，与邻居表相比，两跳 邻居表表项的状态转换简单明了。这是由于在邻居表中，不仅仅记录对称链路的 情况，还记录了非对称和失效等链路状态；而两跳邻居表只包含了对称链路的两 跳邻居情况。o l s r 协议只关心对称链路，而忽略其他状态的链路，从而避免单向 路由的情况。 收至i j h e l l o 帧& & 邻居为双向链路& & 邻居的邻居为双向链路 l 收到h l 三l l o 帧& & 邻居为双向链路& & 邻居的邻居为双向链路 ( 如果其中有一部份邻居有变化，更新该表项两跳邻居的内 容，如果没有变化，仅仅延长表项的生存时间) 图3 2 移动节点两跳邻居表表项状态转移图 3 1 1 3 多点中继站m p r 的选举 表3 1m p r 算法中的符号定义 符号定义 n ( m )节点m 的邻居集合，对称邻居节点集合。 节点m 的两跳邻居集合，除去仅能通过转发意愿n _ w i l l i n g n e s s 等于 n 2 ( m ) w i l ln e v e r 的邻居节点到达的两跳邻居，除去节点自己，除去对称邻居节点 后剩下的两跳邻居构成2 ( 仇) 集。 节点m 的m p r 集合，n ( m ) 中转发意愿n _ w i l l i n g n e s s 不等于w i l ln e v e r 的 m p r ( m ) 一个子集，通过m p r ( m ) 节点，所有严格对称二跳邻居节点是可达的。 o l s r 路由协议与传统的链路状态路由算法最显著的区别在于m p r 1 1 1 的弓 1 2 第三章o l s r 协议的实现 入。m p r 选举机制在全网有效地扩散拓扑信息的同时，大大降低了路由控制消息 的洪泛规模。m p r 的选举原则是m p r 为对称邻居节点，通过选出的m p r 可以到 达所有的两跳邻居节点，并且选出的m p r 个数尽可能少。在描述m p r 算法之前， 做如下定义，如表3 1 。 点m 的两跳邻居节点 节点m 的邻居节点 图3 3m p r 选举 在定义了符号后，m p r 的选举算法具体描述如下： 第一步：获得n ( m ) ，2 ( m ) ；m p r ( m ) = 矽，开始计算m p r 。 第二步：从n ( m ) 中选择意愿nw i l l i n g n e s s 等于w i l la l w a y s 的所有节点 作为m p r 节点。 第三步：计算u ( m ) 的连接度：邻居节点和n 2 ( m ) 中节点相连的个数。在u ( m ) 中 选择满足条件的节点n 本节点必须通过节点才能到达某两跳邻居节点( 条 件) ，m p r ( m ) = m p r ( m ) + 节点册；同时将能够通过节点到达的两跳邻居节点 从2 ( m ) 集中移除。重复选择直到没有满足条件的情况。 第四步：如果此时在n 2