（计算机科学与技术专业论文）adhoc按需带状路由协议的设计与实现.pdf

童淞竖群鬻奠攀剿掣塑骥辫 a d h o c 按饕誊蕊黪内协议魏谈诗与实瑷 赫燮 蓼囊窭缝鬻终是辩没煮墓辩瓣菱裴多糕藤鎏。雾貉孛戆每令繁 点都可黻俸为路壶器藏童穰，节点阀逶过无篾技术述嚣涟信。 无线遇信与移动终端技术的靛腱，使得包禽大量移渤节点的移动 鑫篷霹熬敷爨霉求藏为露戆。麦予葛点暨意移秘、嚣终爨缝织、彝绦 簇羚臻态变讫、爱蠡两陵往( 节患露源畜藤，夔怒低，港存孛等瓣 索的影响，路由问题一髓是移动岗组网研究f | j 热点。 翼黄比较经典熬羧餐多貉覆黪盘协议虽然在攫文糕嶷主黪甄了 够费萑蒋邀蕊霸藤终髓麓酪渖毒，键羲燕存崧饕长露径扩震薅垂。瞥 对此问题，我们提出丁种新的路 ；l j 协议一按需带状路由协议。 本论文详缀设诗了按鬟带虢黠国游议；在鹇2 痨真平台土具棼实 裴了冀中定义器凌谤豁漕塞逶营与蒜愚蠢势，蘑蘸鼹臻莰蘧孛瑟鲣 艇、主路径辅短与链潞优化切换掷主要功能；并在典型成用场景下对 该协议进舒_ 性能评储。 按羲蕊浚露蠹曩我键凌鏊薛静藜壅瑟浚撬裁，滚辍溅不霞蘩黪 解决霞前移动自组网路幽协议存禚的不足之娥，如按需辫路径路由的 妖路径扩飚问题，从刑降低现有路渤发现的时艇，提高网络的吞吐量i 逐蕤鏊器爨按霪多篓经麓窭赛粪翕瓣蕊势。 美键字移渤自组织网络、按需辩路径路由、按需带状瓣融 、 镖雾塑墼塑壁鲤l 坐掣 t l 曩eo n d e m a n ds t r l p s h a p er o u t i n g p 嚣。蕈o c o r s 羚嚣s l g 辩a n 羚毛麓p l 嚣黻嚣x 墨矗曩l o n l na d h o cn e t w o r k a b s 霉歉a c 墨 a d h o ci sa 心n do fw i r e l e s sm u l t i h o pn e t w o r kw i t l l o u tb a s e s t a t i o n e a c hn o d e i na d h o ci s p r o v i d e d w i t ht h ed o u b l ef u n c t i n n so fr o u t e ra n dh o s t , a n d c o m m u n i c a t e sw i t ha n o t h e rn o d eb yw i r e l e s st e c h n o l o g y w i t ht h er a p i dd e v e i o p m e mo ft h et e c h n o l o g yo fw i r e l e s sc o m m t m i c a t i o na n d m o b i l et e r m i n a l t h e r ee x i s t ss o m et r o u b l ew i t hc o n s t r u c t i n ga d h o cw i t hal o to f m o b i l en o d e s b e c a u s eo ft h ee f f e c to fn o d em o b i l i t y 、n e t w o r kt o p o l o g y sc h a n g ea n d n o d el s o u r c e sl a c k , e r eo na d h o c t h em u t i n gt o p i ci sf a e u s e do nb vm a n y r e s e a c h e r si nt h ew o r l d o n d e m a n dm u l t i p a t hr o u t i n gp r o t o c o li so n eo ft h ec u r r e n tr e p r e s e n t a t i v e r o u t i n gp r o t o c o l sa p p l i e dt ot h ew i r e l e s sm u l t i - h o pn e t w o r k ，a n dt oac e r t a i ne x t e n t l i g h t e n st h ee f 羚c to f t h en o d em o b i l i t yo nt h ep e r f o r m a n c eo f r o u t i n g ，b u ts t i l lr e s o l v e s l h el o n g - p a t hp r o b l e m t h u s , an e w r o u t i n gp r o t o c o lh a sb e e np r o ， i nt h ep a p e r , t h ed e s i g n m e n to fo n d e m a n ds 酿黔s h a p er o u t i n gp r o t o c o ii s s p e c i f i e di nd e t a i l ，t h em a i nf u n c t i o n sd e f i n e di nt h en e wp r o t o c o l ，s u c ha st h em o d t i l e o fi n f o r m a t i o nc o m m u n i c i t o na n dm a n a g e m e n t t h em o d u l eo fl o e a lb r o k e nr o u t i n g r a p i dr e p a i r m e n t t h em o d u l eo fs h o r i n gt h em a i np a t ha n dt h em o d u l eo fo p t i m i z i n g t h ej i n k 。a r el m p l e m e m e d + i nt h ee n da l le v a l u a t i o no nt h ep e r f o r m a n c eo ft h e p m t o c o a li sd e s c r i b e d 。 o n d e m a n ds t r i p s h a p er o u t i n gp r o t o e o lc a nn o to n l yr e s o l v et h es h o r t a g eo f t h ec u r r e n tr o u t i n gp r o c o t o l sa p p l i e dt oa d h o c ，s u c ha st h el o n g p a t hp r o b l e m ，b u t a l s oh o l dt h ep r e d o m i n a n c eo ft h eo n - d e m a n dm u l t i p a t hp r o t o c 0 1 t h u sr e d u c et h e t i m e l a ya n di n c r e a s et h et h r o u g h p u to f t h ea d h o cn e t w o r k k e yw o r d sa d h o c 、o n - d e m a n dm u l t i p a t h r o u t i n g 、o n d e m a n d s t r i p - s h a p er o u t i n g i i i 擎整鎏塑鍪圭戟然一 一，塑燮鐾罄磐罄篓鲨熏熬 辫耀 本人声溅臌璺交的论文遵本人霞镩蝼燃导下谶符灼研究王张漱敷褥的研僦 麟荣。娶获磷辩，滁了文串姆爨热戳据注卷鼗鼗串溅拶熟想密容强於，论文孛不 毽窘葵楚天嚣楚羹豪蔑搽慧楚蓉鹱变蕊爨，逮綦餐蠢鸯薤霉嚣泰繇惫文霉；鬣冀激 激育机构的举位或证书丽靛厢过的树料。与我一同忑释抟简志对本研究所谳瀚强 髂嚣敲均瓣谯沦文中 筝了烘确姻说明并嵌示了谢懿。 靛子诠文蕊燃技毂赘诱秘 擎蕊淹突褒毒竞垒了瓣囊索簿惫天攀蠢蓑螽；蘩瑟镬整攀爱蔻蛮怼然盏豁霉：瑟瓷銎 柱校攻敞常士麓期问论文i ：怅的知识产权端德鹪北京邮 钍凡学。学校商椒谍留并向圈寐谢 关都f 强桃稳邀燮论文勰艇黟鹳二鞫磁盘，兔t 年擎谴论文陂凌瓣和菊瀚；学嫒霹班公帮渺 黎谚文蕊叠赫囊藜舅彝褰，簿鎏蠢蠢慕瓣黪霉，蘩霉壤熬宅餐蘩手段臻存、莨襞警霞避 文。f 谍辩滟窜谴适突恣髂密瑟遵守蘧瀛瀚) 保密论文注释：本学位论文属于佩潞槛年解密艏遣用本撼枫粥。非保密地 交蕊鬻：零辫篷谂喜爱瓣爹爨蜜萋霾，遽疆霉鼗毅器。； 席己走蕊麓；盍查、耋器蘩；。堡! ：| ：i 兰。 导耀撼濑：雾移争毛r 一 。嚣麓；攀防毒辛迅l ， 毒骤鬻鐾辫辫掣群罄燮媸掣颦娑 尊l 誊 讲究背蒹介缨 盘予曩挺粼络舞葬瀚趟羧瞧，当嚣淡抒鹣第二找游动遵薅系缝蕊无法满足 魏在灾楚蕊疆莓繇壤下避行蘩患蘧蕊懿器求。避每塞，漤嚣鼗裔疆缀霪终 ( a d h o c ) 、秃跤黼状网( w m n ，w i r e l e s sm e s i tn e t w o r k s ) 鞫无线髂黔秣两络( 髑n ， w i r e l e s ss e n s o rn e t w o r k s ) 等为代表l ! 勺无线多跳网络以其独有的优瓣使得应用 篷漆逐多扩大。 无线囊缀躐辩络蔗耱霞中心靛、辩鳃绞嚣秃绫黟魏瓣络；蕊幂嚣要f f 壬何蕊 础设施且网辫裙翳部署，对许多应用熙肖非常大的吸引力。在军辫顿域，它可以 吏祷舅多 籁察戳终、蘩交战每群遭蘩露勰酞潼净瑟邋铸、笼天餐黎譬搂羧簧羲镣； 程涎薅颈装，它孬鑫支辩谗露移囊会议、移囊麓缮、个天蘑蕺瓤与灾藏疆场爨念 通信过程中的储恩交换以及临时交互式通信等等。 筵翻珥强迄蚕夸袋蟪鞭溅，这耱毅拳在来寒移麓邋绩赣装孛将会怒至l 蘧采越 黉要翡露薅。 当前移渤自组网路囱协议主要分为羧驱动路由羊按黼路由。 荬孛亵裂渤路交毒于带点移套导滚斓游耩釜缀鬻发堂变弦，凝鸯驻下嚣令缺 陷： 、节意穆凄器蒙诲藩黯鑫表瑷褒搜怒乏蔻薤爨失效；2 、淹了恣篱令节煮瓣 护全局拓扑。必须以更商频率进行拓扑变化更新，路幽开销大。 嚣菝纛耀霸格蔽在节赢嚣簧发送数旗露君遂孬潞爨诗奠，在瓣络蔫点移动瞧 麓静蘩嚣下，鬣熬嬉交嚣销夺，羲辜纛，毽壤毒不怒之楚，节熹移凑会颧繁审峨 敞需路由，并触发昂贵修艇机铷来重新建立路由表鞭。蕊对移动释致的快速变化 熬挺羚结构，一些研究人妖提避了多鼹经路虫，即农源节点和目的节点之阗建立 爹袈冗塞臻携。按票一条嬉经串鬻，冀毽鼹羟餐爨群鳎。a o d v 莉d s r 籍盘巍浚 怒典型按霭潦幽渗议，蠢藤大帮分静多鼹程路庄 褥议均蔫主述两辩被蒜路由辫议 的扩展。与按霈路由相比，按需多路橙路由具有更好移幼适应弹性。 蔓鏊蘩糕雾罄径鼹蕊澄谈在一褰稷震主洚懿了繁熹蓼魏豢潦黪瓣舞络豫穗 靛淬击，鼹蕻铱然无法甄缀本上簿凌最路径惩蘧；l 、在中等密寂阏终孛，醚麓 任意两点间躐增大，可以发现的节点不相交的路径数目下降；2 、随着节点问溅 离l 窒 太，挚鼹径鼹辩蓑垒多楚孛繇毂察变丈，黯童瓣帮维护菝繁，瓣瘦至存 i 雩渊 变薤。 一零些型望墼驾罂旦坚鐾塑型燮槊 因此研究与设计一种新的可以解决上述瓶颈的路由协议a d h o c 按需带状 路由协议就显得尤为必要了。 研究工作介绍 在攻读硕士研究生期间，参加了中国科学院计算技术研究所网络室下一代网 络研究中- t 3 的“无线移动自组织网络按需带状路有机制的研究”北京市自然科学 基金项目的研究与开发工作；具体的工作主要集中在按需路由协议几大功能模块 的设计与系统模型仿真实现上。 对无线多跳网络，特别是无线白组织网络( a d h o c ) 、无线网状网( w i r e l e s s m e s i in e t w o r k s ) 与无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ) 进行过比较深入 的学习与研究，曾因项目组下一步科研的需要，完成并提交了一份“目前国内外 无线网状网络研究现状调研报告”。 以上这些理论知识的学习与具体相关项目的实践，为本论文的撰写形成了深 厚的理论沉淀和实践基础。 下面本论文将会围绕按需带状路由协议的设计与实现，从技术背景、协议的 总体设计、详细设计、仿真实现、性能评估和回顾与展望等几个章节进行展开讨 论与研究。 v l i 一 尝燃罂鎏驻i 曛鲤蜘磐堂塑 第一章技术背景 1 1 无线多跳网络介绍 在某些特殊的场合如战场和一些缺少通信基础设施的地方，需要短时间内组 建起功能强大的移动多媒体通信网络，以满足数据、图像、音频和视频等内容的 通信要求，传统的固定网络和蜂窝无线网络并不适合这些场合，无线多跳网络技 术就应运而生了。 近几年，随着无线通信技术和计算机技术的飞速发展，为无线多跳网络向实 用化方向迈进创造了条件：它是种没有固定网络基础设施而随时配置的无线网 络。目前比较典型的无线多跳网络主要包括无线移动自组织网络( a d h o c ) 、无 线网状网( w i r e l e s sm e s hn e t w o r k s ) 与无线传感器网络( w i r e l e s s s e n s o rn e t w o r k s ) 。 无线网状网是一种基于多跳路由、支持多点对多点的新型网络结构，具有高 效移动宽带接入的特性，同时可以动态地不断扩展，自组网、自管理，自动修复、 自我平衡，与一般星型无线网络相比具有更高的健壮性与快速建网的特点；其主 要由移动互联交换控制中心、智能接入点、无线路由器、i c m c i a 无线终端网 卡四部分组成。 无线传感器网络是随着传感器技术、微系统技术、现代网络和无线通信技术 的进步而发展起来的、由部署在监测区域内大量的廉价微型传感器节点( 包括传 感器模块、处理器模块、无线通信模块和能量供应模块四部分) 组成，通过无线 通信方式形成的一个多跳自组织的网络系统，其目的是协作地感知、采集和处理 网络覆盖区域中感知对象的信息，并发送给观察者。 无线移动自组网络是一种没有基站的无线多跳网络。它不依赖于固定主干网 ( 但也可以与其配合) 或基站，能快速部署到位，建立起套完整、强大、高抗 毁的网络通信系统，提供有效的数据和多媒体通信服务。a d h o c 利用无线技术在 各个节点间传送数据分组，网络中的每个节点都可以作为路由器或主机。移动自 组网具有节点任意移动、网络自组织、网络拓扑动态变化等特点。 无线移动自组网中的节点通过多跳方式进行通信，为了进行有效的通信，移 动节点问必须建立合适的路由。由于节点的移动性、网络拓扑结构的可变性、传 输的多跳性、无线信道的不可靠性( 远近效应、多径衰落、信道噪声和干扰等) 、 第1 页共9 8 页 北京邮电大学顾士学位论文a d h o c 按需带状路由协议的设计与实现 带宽的贫乏性与时效性，和设备局限性( 节点电源有限，性能低，内存小) 等因 素造成了a d h o c 比传统的有线网络和单跳无线网络要复杂得多，因而传统网络中 的路由协议不再有效，必须针对a d h o c 的上述特点研究新的路由协议。 1 2典型路由协议介绍 目前世界上有关研究机构已经开发出了许多基于各种不同策略、适用于无线 自组织网络的路由协议。根据路由策略的不同，a d h o c 路由协议大致可分为以下 4 种类型： ( 1 )主动型( a c t i v e ) 与反应型( r e a c t i v e ) ： ( 2 )平面型( f l a t ) 与层次型( h i e r a c h i c a l ) ； ( 3 )g p s 辅助型( g p sa s s i s t e d ) 与非g p s 辅助型( n o tg p sa s s i s t e d ) ； ( 4 ) 单路径型( s i n g l e p a t h ) 与多路径型( m u l t ip a t h ) 。 由于采用不同的策略，各种路由协议都各自存在不同的优缺点：为了获得 更好的路由效果，在具体路由协议设计过程中，通常同时采用多种策略，如按需 多路径路由协议等。 以下就对几种当前采用的典型的策略作进一步的介绍。 1 2 1 主动型路由 主动型路由通过周期性地更新路由信息来维护全局或者尽量全局的网络拓 扑。具有以下两个缺陷：1 、节点移动导致许多路由表项在使用之前就已失效；2 、 为了在每个节点维护全局拓扑，必须以更高频率进行拓扑变化更新，路由开销大。 在无线信道带宽有限、电池能量有限的情况下，路由开销大问题尤为突出。 目标序列距离矢量d s d v ( d e s t i n a t i o i ls e q u e n c e dd i s t a n c ev e c t o r ) 路由 协议是一种主动型的距离矢量路由协议，网络中的每个节点都维护一个路由表， 路由表的内容包括该节点到所有可达的其他节点的路由，以及相应的跳数。周期 性的路由广播信息能够使得各节点的路由表得到更新，以跟踪网络的拓扑变化。 为了保证在网络中存在闭环时也能正常工作，d s d v 给广播的路由更新消息标定 一个序号，以此来表示路由更新消息的新旧；新的路由信息将取代旧的路由信息。 1 2 2 反应型路由( 也即按需路由) 按需路由在节点需要发送数据时才进行路由计算，在网络节点移动性高的情 况下，路由开销小，效率高。但节点移动会频繁中断按需路由，并触发昂贵的修 复机制来重新建立路由表项。目前比较典型的按需路由协议主要有以下几种： 第2 页# 9 8 页 j ! 塞塑堕查兰婴：! 兰堡堕生 一；，一掣娑夏羔粤掣型型量宴竺孥粤善堡：! ! i 攀一 ( 1 )动态源路由d s r ( d y n a m i cs o u r c er o u t i n g ) 路由协议 d s r 路由协议是一种按需路由协议。d s r 协议要求源节点在发送的数据分组 中携带完整的路由信息，路由信息位于数据分组头中，其内容包括该数据分组从 源节点到目的节点所要经过的所有中间节点。网络中从源节点到目的节点这条路 径上的所有节点按照数据分组中提供的路由信息，依次转发该数据分组，直至该 数据分组到达目的节点。d s r 路由协议的优点在于所有“中间”节点不必保存转 发数据分组所必需的最新路由信息，因为数据分组头中能够提供足够的路由信 息。不过，源节点需要知道数据分组所要经过的所有中间节点序列。 d s r 协议获得路由信息的方式是：当网络中的某个节点( 源节点) 需要到达 另一个节点( 目的节点) 的路由时，它采用泛洪的方式广播一个路由请求分组， 接收到该分组的节点首先搜索自己的路由表，以确定自己是否能提供路由请求分 组所需要的路由，如果自己不能提供路由请求分组所需要的路由，它将自己的 i d 号附加到路由请求分组上，然后继续采用泛洪的方法将这个路由请求分组向 其邻节点广播。于是，这个路由请求分组就在网络中传播开来，并记录了它所经 过的所有节点，直至到达节点或到达某一个能提供所需路由的中问节点为止，这 时就获得了所需的路由。然后，目的节点或某一能提供所需路由的中间节点把有 效的路由信息装载到一个路由应答分组上，按照路由请求分组所经过的路径将路 由应答分组回送给源节点。 ( 2 )a d h o c 按需距离矢量a o d v ( h o t t o co nd e m a n dd i s t a h o ev e c t o r ) 路出 协议 a o d v 路由协议是一种按需的距离矢量路由协议。对于采用a o d v 路由协议的 网络，只有当源节点a 要与目的节点b 建立通信时，节点a 才去请求到达节点b 的路由，而不必维护到达其他节点的路由。搜索路由的过程称为路由获得。与 d s d v 路由协议类似，a o d v 路由协议也采用序号来表示路由消息的新旧。 a o d v 路由协议获得路由信息的方式是：当网络中的某个节点( 源节点) 需 要到达另一个节点( 目的节点) 的路由时，源节点向它的所有邻节点广播一个路 由请求消息r r e q ，各邻节点采用泛洪的方式在网络中传播r r e q 消息，直至f f r e q 消息到达目的节点或到达某一能提供所需路由的中间节点为止。r r e q 消息为每 一个转发它的中间节点建立一个临时的、到达源节点的路由( 称为反向路由) 。 当r r e q 消息到达目的节点或到达某一能提供所需路由的中间节点时，一个路由 应答r r e p 消息按照r r e q 消息经过的路径反向传送给源节点。在r r e p 反向传向 源节点时，r r e p 消息给每一个转发它的中间节点建立一条到达目的节点的路由 ( 称为正向路由) 。上述由r r e q 建立的反向路由和由r r e p 建立的正向路由都是 第3 页共9 8 页 北京邮电火学硕士学位论文 a d h o c 按需带状路由协议的设计与实现 有寿命的，当经过一个规定的时i 日j 而这些路由没有得到更新时，这些路由将被节 点从路由表中删除。 在a o d v 路由中，每个节点都要定期广播h e l l o 消息。一个节点是通过接收 其他节点广播的h e l l o 消息来发现它的邻节点的。 1 2 3 多路径路由 多路径路由在可靠性、负载平衡、带宽聚合、q o s 、能量保护等方面具有很 好优势。传统网络中经典多路径路由的好处在移动自组网中仍然适用，比如通过 多路径分散通信流量达到负载平衡，减小网络拥塞，提高整体服务质量；通过多 路径并行传送数据对网络带宽进行聚合：在多路径上发送冗余数据包或者带有纠 错信息的数据包，提高数据传输可靠性。移动自组网的多路径路由还可以提供其 他好处。首先，移动环境中事先建立路由发生中断的概率很大，因此冗余路径可 以减小路由失败恢复时间，提高端对端应用q o s ；其次，多路径传输信息可以分 散网络节点间电池能量使用程度，延长网络整体能量使用时间。另外，通过多路 径传输加密信息，可以有效减小中间人、重放、窃听等攻击的可能性。 与按需路由、多路径路由相比，按需多路径路由具有了按需和多路径的优点， 在一般场景下可以大大地抵制移动性对路由协议性能的冲击。 1 3 按需带状路由 正如前面所述按需多路径路由机制虽然在一定程度上降低了移动特性对按 需路由协议性能的影响，但还是存在长路径扩展问题，它直接影响了移动自组网 的扩展性。 按需带状路由是我们设想的一种新型路由机制，希望该机制不仅能够解决目 前移动自组网路由协议存在的不足之处，如按需多路径路由的长路径扩展问题， 从而降低现有路由发现的时延，提高网络的吞吐量：还能够保留按需多路径路由 在处理可靠性、负载平衡、带宽聚合、q o s 、能量保护等方面优势。 按需带状路由协议设计的基本思想是：节点通信前，通过泛洪法进行路由发 现，建立源节点和目的节点之间的主路径。主路径上各节点维护一跳范围局部拓 扑，构成从源节点和目的节点之间带状路由。当出现路由中断时，利用各节点上 维护的带状路由信息，快速进行路由修复：定时检测各条主路径是否可进行路径 缩短或链路优化切换，如果满足条件则进行相应的处理。 第4 页共9 8 页 趣意辩谶大学旗圭学鲑埝文a d h o c 按嚣带凝薅蠡捻巍豹璇 与实巍 繁：章按浚懿慧薅竣计 襞 蓊浚麓装雾求 由于按需带状路由协议麓针对a d h o c 按需多路襁路由协议中襻猩的长路镪 问题而设计的种新型路豳协议，因此澎成该不仅具辫按需多路径潞由协议的功 黢蕊骜，瑟鼗逐莹矮瑟够麟捷控毳多籍经鼹盘餐议争存在数长貉较搁爨，这菰浚 淀了按需带状鼹虫秘议存农慧鞋下一些塞鼗静珐能需求： 1 ) 应该襻在一套能及时反映网络局部拓扑的变化的机制，使榭备节点能傈 耩萁麴搿鼹帮蔟蛰豹耨黪注 2 ) 需要定义一缝控希分缍爱分组靛瀑与接收攘鞲，以便于裰关节点阍避弦 消息通信。 翁嚣终枣蕊繁煮霾缨护鬟霹维轳渗装黎峦蘩惑穗接癸蕊爨鹣链交，璐爱 套链豪滟鼙薪与维护虢耩，如镰衮条强髂疆搬、溅除、雯鬻鄹定瑟剜薪链。 表的定时嚣等； 棼当弼辫孛凄理疆臻孛鞭露，貉议碍褒廷嚣部搽挎孛吝节点绦轳魏营犊鼹 出售惠遂嚣妖速链鼹审舔渗复； 5 ) 随着节点的移动，阚络局部拓扑般生变化，出生路径中出现可缩短链蹄 翳，按浚w 宾凌送蜇主路经缩短； 镑当网络中出玩更优辫径露，挤滋鳟啻葫遗骨主潞径谤挨；并麓耱正路浚 来回切换； 2 窑类型缝建耨景 ， 一 适甩于弼线自组织网瓣a d h o c 的按需带状踏 = l ； 协议主要热熬的应用坜录 蝴圈2 - t 、网2 - 2 与图2 - 3 肼示： 第5 囊熬9 8 美 北京邮电大学硕士学位论文a d h o c 按需带状路由协议的设计与实现 h o p s = 2h o p s 2 3 图2 - 1 局部路由快速中断修复示意图 图2 - 1 中，设m _ 2 到m _ 3 链路出现了中断。m2 发送r b r r 消息，周围节点 收到后，b j 、b 一2 、e _ l 、e 一2 四个节点将会向m _ 2 发送r c n 消息；m2 收到r c n 消息后，将会从多个r c n 消息中选取最佳的，利用其中存有的拓扑与路由信息修 改本地路由表，快速重新建立路由。 图2 2 主路径链路优化切换示意图 图2 - 2 中，设随着节点的移动，网络拓扑发生了变化，在主节点m _ 3 与m5 之间出现了2 条可选路径：一条为原来的主路径m _ 3 、m _ 4 、- 5 ；另一条为新出 现的m _ 3 、b l 、m _ 5 。 当路径m _ 3 、b l 、m5 的链路度量指标优于主路径m _ 3 、m4 、m _ 5 超过一定 程度时，按需带状路由协议可自动将路径m _ 3 、b l 、m5 切换成链路的主路径。 第6 页共9 8 页 ! ! 塞堡尘查兰堡：! 兰擘鲨苎。一 ； 生坚q 掣霉堂鉴娶害竺罂塑娄生耄娄型 b p s = x “ h 。p f 科2 岫p 8 “h 。p _ + 4h o p r + 5 抽p 5 咐6h o p s 7 h o p s l + 8 h o p 。：。磊k 鸲殴b 砂撕l 7 ( a ) ( c ) 图2 - 3 主路径局部缩短优化示意图 + 8 由于节点移动，导致路径山现弯曲或者漂移。因此存在路径缩短可能性。 设图中流的源。仃点为m s ，目的节点为m d 。从源节点m s 到m l 距离为x 。所有节点 收到s s r m 消息时对历史s s r mi d 消息组进行比较得到以f 四种结论： 4结论l ：。讧点未发现可缩短路径条件，比如m l ，m 2 ： 土 结论2 ：上游土节点发现可缩短路径，比如图中m 6 发现可缩短路释后，将本节点 路由从m 7 直接切换到m s ： 奎 结论3 ：调用非主节点邻居发现可缩短路径处理模块，比如图中x l 发现存在可缩短 路径后，首先在本协点建立指向m 4 的路由，同时发送r c n 消息，通知m s 将下一 跳节点从m l 切换到x 1 。 止 结论4 ：下游主节点发现可缩短路径，比如m 8 ：肖点，不做任何处理。 第7 页共9 8 页 北京邮电大学硕士学位论文 a d h o c 按需带状路由协泌的设计与实现 2 3总体架构 根据上述协议的功能需求分析，按需带状路由协议主要可由四大模块构成： 消息通信与信息维护模块、局部路由快速中断修复模块、主路径缩短模块和链路 优化切换模块。它们之问的关系如图2 4 所示。 图2 - 4 体系架构图 注意：其中所有线条均为单向，箭头表示信息的流动方向；直线或折线表示通告消息；曲线 表示反馈信息： 2 3 1 模块功能介绍 几个主要模块的功能说明如下： 消息通信与信息维护模块主要完成主路径一跳范围内节点间消息的发送、接 收与处理、信息在本地节点内的维护以及本地路由表的修改等工作。 局部路由快速中断修复模块主要完成当出现路由中断的时候，利用主路径一 跳范围内各节点存放的拓扑信息与路由信息，在中断链路局部范围内快速重新建 立路由的功能。 主路径缩短模块主要完成当主路径上出现满足可缩短条件的链路时，进行主 路径缩短，从而达到减少从源到目的总跳数，优化路由的目的。 链路优化切换模块主要完成当主路径一跳范围内出现多条同等跳数的路径 时，可通过对链路质量、节点资源等指标的比较，进行链路优化切换，将主路径 变更到指标更优的链路上，以达到路由优化的目的。 第8 页共9 8 页 挚塞塑! ! 銮差堡圭堂丝兽兰“，；垒里! ! 粤。鎏量萱鉴堕生塑坚螳生善笔挚 2 3 2 模块相互关系 消息通信与信息维护模块是后面三大功能模块得以实现的前提与基础；而局 部路由快速中断修复模块、主路径缩短模块与链路优化切换模块三大功能模块是 按需带状路由协议的核心部分，它们需要借助消息通信与信息维护模块访问本地 数据链表及其它存储区，进行无线网络中相邻两个节点间的通信。 当节点接收到s s r m ( s t r a ps h a p er o u t em a i n t a i nm e s s a g e ) 分组，进行 的处理流程如图2 - 5 ： 收接收到s s r m 分组：仃 点做如下处理： l 、调用邻居列表维护模块； 2 、调用s s r m 表管理模块 该模块完成调用s s r m 消 息插入，然后调用主路径局部 缩短优化模块，如果没有进行 局部缩短优化，则进一步调用 主路径局部链路优化切换模 块；如果进行了局部路径缩短 优化，则不再调用主路径局部 链路优化切换模块； 3 、调用s s r m 消息转发模块： 判断是否需要转发s s r m 消 息。 图2 5 接收s s 删后的节点处理流程图 第9 贞共9 8 页 北京邮电大学硕士学位论文a d h o c 按需带状路由协议的鼓计与实现 3 1 基本概念 3 1 1 节点概念 r ms = ml 第三章协议的详细设计 b1b2 e l 图3 - 1 上游和下游概念 md 主节点：m a i nn o d e ，该节点在转发路由确定过程中首先确定，即目的节点返回 r r e p 分组时，收到r r e p 分组的节点判断自己是主节点。主节点顺序构成主路径。 如图3 1 中的m _ s ，m _ l ，m _ 2 ，m _ d 等节点。 主路径：由主节点构成的路由称为主路径一- - m a i np a t h 。 主路径一跳范围节点：主路径节点的所有一跳邻居，但不包括主节点自身构成的 节点集合称为主路径一跳范围邻居集。 备份节点： b a c k u pn o d e ，该节点是主路径一跳范围节点，能够同时收听到同一 主路径上相邻的三个主节点顺序转发的同一分组。如图3 一l 中的b - 1 ( 具体可收 到m _ l 、m2 和m _ 3 三个相邻主节点的分组) 、b 一2 ( 具体可收到m _ 2 、m _ 3 和m _ 4 三个相邻主节点的分组) 等节点。节点分为等高主各份节点、上游主备份节点、 下游主备份节点。 3 1 2 流 流( f l o w ) ：具有相同源i p 地址、目的地址i p 地址，并且流经相同网络路径的 数据分组。 第1 0 页共9 8 页 些皇些堕- 丈堂堡主堂垡堕壅：垒里塑! 攀至堕坚堕粤堡攀堕墼过兰壅墨 3 13 上游下游节点与上游下游链路 流具有方向性，并且对于任意一个中间主节点，存在上游主节点和下游主节 点。如图3 - 1 所示，分组从源节点m _ s 产生，逐跳转发到目的节点md 。对于m _ 2 为例，m _ l 称为m _ 2 的上游主节点，m _ 3 称为m _ 2 的下游主节点；从m _ l 到m _ 2 的链路称为m2 的上游锰路：从m _ 2 到m3 的链路称为m _ 2 的下游链路。 当m _ 2 的下游链路中断时，由m _ 2 负责发起修复。 3 1 4 度量指标 在进行链路优化切换过程中，为了减小链路度量或者节点度量的测量开销， 使用不需要周围节点配合、本节点即可获取的链路度量或者节点资源度量指 标。具体有： 1 )节点发送队列占用率一一用于描述节点资源。 节点发送队列占用率反映了节点流量负载情况，在网络层可以获取。节点采 用指数加权方法对当前节点发送队列进行处理，得到节点发送队列平均长度。在 同构节点前提下，对节点发送队列平均长度用发送队列最大长度进行归一化，得 到节点发送队列占用率。节点发送队列占用率划分为四个级别： 0 ：0 0 2 9 1 ：0 3 0 6 9 2 ：0 7 一o 9 3 ：0 9 一l 采用不等分的依据是负载越重，划分区间越窄，被均衡的概率越大；负载越 轻，划分区间越宽，被均衡概率越小。将负载轻区问设大，还可以避免链路的局 部往返切换问题。 链路优化切换振荡问题：由于网络数据流具有突发性，会导致节点的发送缓 冲队列占用率出现突变，会时高时低，这样容易造成局部路由来回切换。对发送 缓冲队列长度采用指数加权后，可以让发送缓冲队列长度变平滑。另外，通过对 节点发送缓冲占用率采用不等长划分法，即保证流量重的情况能够快速切换，又 保证流量轻的情况切换次数少。 2 )移动预测度量m p ( m o b i l ep r e d i c t ) 一一用于描述链路质量。 移动预测度量指接收到信号的强度，用于描述链路质量。信号强度越大，表 明节点间距离越近，链路生存时间越长。m p = 信号接收强度信号中断判决门限。 嚣l l 页共9 8 页 北京邮电大学硕士学位论文a d h o c 按需带状路由协议的设计与实现 根据m p 值的大小，分为两个等级： m p 1 0 ，认为链路正常。将该级别定义为0 1 ： m p 小于等于1 0 ；认为链路出现中断前兆或者中断( m p 小于1 ：认为链路中断。) 该级别定义为o o ； 链路出现中断前兆，备份节点进行切换。移动预测度量反映了节点移动情况， 需要物理层传送到网络层。 通过实际仿真测试，发现如果两个节点距离为2 0 0 米，信号接收强度除以 信号终端判决门限值得到的移动预测度量m p = 2 4 4 1 8 2 2 。 ( r x p r ：8 9 1 7 5 3 5 e 一1 0 一一r x t h r e s h ：3 6 5 2 0 0 0 e i o 一一p o w e r l o w ：2 4 4 1 8 2 2 后期中，需要对该参数进行优化。 3 2 控制分组格式 a o d v 路由协议所有的控制包采用u d p 传送，对应端口为6 5 4 。在a o d v 中定 义了四种消息格式：r r e q 、r r e p 、r r e r 、r r e p - a c k ( 用于局部连接管理的h e ll o 分组采用r r e p 格式，设置t t l = 1 ) 。上述四种消息格式的消息类型依次为l 、2 、 3 、4 。 在带状路由局部优化技术中，需要定义三种新的格式： 3 2 1路由切换通信消息格式一一r c n 路由切换通知消息r c n ( r o u t ec h a n g en o t i f i c a t i o n ) 用于局部路径缩 短、局部链路优化切换、局部链路中断修复。通过r c n 消息通知r c n 消息的接收 节点修改路由表选项，将目的节点的下一跳指向r c n 的发送节点。 1 ) r t c n 消息格式 4t y p e ( 8 比特) ：该值为2 5 4 ，与a o d v 的消息格式类型兼容。 4d e s t i n a t i o ni pa d d r e s s ( 3 2 比特) ：r c n 消息接收节点通过该字段获取本 节点路由表中需要修改的目的节点i p 地址。 击 r c ns e n d e r1 pa d d r e s s ( 3 2 比特) ：r c n 消息接收节点通过该字段获耿 本节点路由表中对应目的节点的下一跳节点i p 地址。 4r c ns e n d e r( 8 比特) ： 发送节点到源节点的h o p c o u n tt os o u r c e r c n 距离。 4r c ns e n d e rn o d er e s o u r c e ( 2 比特) ：指明r c n 消息发送节点的发送 缓冲区占用级别，分为4 个等级。 第1 2 页共9 8 页 ! ! 塞塑皇查堂堡：! 兰垡笙壅垒孥! 堕篓至笪鉴堕虫坠堡塑堂鲨量兰型 毒 r c n s e n d e r _ u p r i v e r _ l i n k _ q u a l i t y ：( 2 比特) ：r c n 消息接收节点到r c n 消息发送节点的链路质量。r c n 消息发送节点通过接收或者监听r c n 消 息接收节点发送的分组获得链路质量，该链路质量指信号强度。分为两 个等级。 一r o u t e c h a n g e _ r e a s o n ( 8 比特) ：当网络局部出现更优路径时，可进行 路由切换；o 。代表路径缩短，1 一代表链路优化切换，2 一链路中断修 复，缺省为2 5 5 。 2 )仿真实现 r c n 消息是对a o d v 消息格式扩展，采用u d p 报文发送，u d p 端口为6 5 4 。 r c n 消息通过单播方式传送，t t l = i 。n s 仿真具体实现可借鉴附录中标准的 a o d v 路由协议路由控制消息。 3 2 2 路由中断修复请求消息格式一昭隙 路由中断修复请求消息：r b r r r o u t eb r o k e nr e p a i rr e q u e s t ，该消息用于 局部链路中断修复。 1 )r b r r 消息格式 潼t y p e ( 8 比特) ：该值为2 5 3 ，与a o d v 的消息格式类型兼容。 津s o u r c ei pa d d r e s s ( 3 2 比特) ：源节点网络地址。 善d e s l i n a t i o ni pa d d r e s s ( 3 2 比特) ：目的节点网络地址。 r b r rs e n d e r1 pa d d r e s s ( 3 2 比特) ：发送该r b r r 分组的节点网络地址 4r b r rs e n d e rh o p ( 8 比特) ：消息发送节点到c o u n t t os o u r c er b r r 源节点的距离。 2 ) 仿真实现 r c n 消息是对a o d v 消息格式扩展，采用u d p 报文发送，u d p 端口 为6 5 4 。r b r r 消息通过广播方式传送，t t l = 1 。n s 仿真具体实现可借鉴附录 a o d v 路由协议路由控制消息。 3 2 3 带状路由维护消息格式一一s s 刚 带状路由维护消息格式s s r l d ( s t r a ps h a p er o u t em a i n t a i nm e s s a g e f o r m a t ) ，该消息用于带状路由信息的维护。 1 )带状路由维护消息格式 潼t y p e ( 8 比特) ：该值为2 5 2 ，与a o d v 的消息格式类型兼容。 第1 3 贞共9 8 页 北京邮电大学顾十学位论文 a d h o c 按需带状路由协议的设计与实现 4s o u r c e ( 3 2 比特) ：标识流的源节点i p 地址； ，玉d e s t i n a t i o n ( 3 2 比特) ：标识流的目的节点i p 地址； 4 r t _ s e q n o ：目的节点序列号：查找路由表，如果有路由表项，从对应字 段中获取，如果没有，设置为0 。 s s r m i d ( 1 6 比特) ：源节点的流序列号，表明最新流分组。源节点生 成s s r m 消息时，将s s r m i d 加1 。( 注意：s s r m - i d 不同于a o d v 中源节 点的广播i d ) 4n o d e _ r e s o u r c e ( 2 比特) ：源节点生成s s r m 消息，或者中间主节点转发 s s r m 消息时，需要将本节点资源填充到该字段。节点资源指：本节点的 发送缓冲区占用级别，分为4 个等级。 士u p r i v e r _ l i n k _ q u a l i t y ( 2 比特) ：中间主节点转发s s r m 消息时，需要将 本节点的上游链路质量填充到该字段。链路质量指中间主节点的上游主 节点到该节点的信号强度，分为两个等级。如果是源节点，由于不存在 上游链路，则认为上游链路质量正常，m p 级别为0 1 。 。量s e n d e r ( 3 2 比特) ：s s r m 消息的链路发送节点的i p 地址。 4 r e c e i v e r ( 3 2 比特) ：s s r m 消息的链路接收节点的i p 地址。目的节点收 到s s r m 消息后，广播纯s s r m 消息，将该字段值设置为i p 广播地址。 4h o p _ c o u n t _ r r 0 一s o u r c e ( 8 比特) ：s s r m 消息发送节点到源节点的距离。 4h o p _ c o u r t u o d e s t i n a t i o n ( 8 比特) ：s s r m 消息发送节点到目的节点的 距离。 毒d a t a a t t a c h b i t ( b o o l ) 捎带指示。0 ：无捎带，1 ：有捎带 4d a t ap o i n t数据指针 注意： 两元组用于唯一标识流， - i 元组用于唯一标识同一流中同一分组；剩余字段用于 标识中间转发节点相关情况，节点在转发s s r m 消息时，需要对剩余字段进行更 新。 2 ) s s r m 消息发送 s s r m 消息采用m i x c a s t 的方式发送。 3 2 4 混合播i p 分组格式一一m ix c a s t 1 )基于i p v 4 的混合播分组格式 利用i p v 4 报头的服务类型字段，第7 比特位设置为非缺省位，指示该 分组为m i x c a s t 分组，即是采用广播方式发送，但是在广播分组中指定了接 第1 4 页共