（通信与信息系统专业论文）移动多跳多链路多媒体网络的路由优化技术研究.pdf

沈阳理工大学硕士学位论文 摘要 移动自组织网络的特点是组网灵活、支持移动性、系统成本低，移动自组织 网络几乎涉及到军用和民用各方面。随着信息技术的不断发展，人们已经不满足 于数据传输服务，而是希望越来越多的音频、视频等多媒体技术的发布和传播， 这就对网络技术提出了q o s 的要求。虽然a dh o c 的研究人员也开发出几种基于 a d h o c 网络的q o s 体系，但由于a d h o c 网络本身技术的局限性，使得其q o s 性 能并不能满足需要。为此，建立了移动多跳多链路多媒体网络( m o b i l em u l t i - h o p m u l t i 1 i n k m u l t i m e d i a n e t w o r k ，m 4 n e t ) 的拓扑模型，同时综合资源预留协议、路 由优化技术等的最新发展，提出了一种基于资源预留的m 4 n e t 的q o s 机制，即在 源端计算8 条优化路由并进行资源临时预留，由目的端确定最优路由并j 下式预留 资源，从而保证多媒体传输的q o s 功能。 对于最多包含2 0 4 8 个节点的复杂网络来说，路由优化将会是一件很困难的事 情。作为研究内容的重要组成部分，本课题首先给出了q o s 路由的度量原则，然 后分析了移动自组织网络的路由协议，在对比常用的路由搜索算法的基础上，根 据m 4 n e t 的网络特征，确定了基于遗传算法的路由优化算法。本课题实现了m 4 n e t 中源节点与目的节点之间的路由优化，即以跳数为度量，在源节点和目的节点之 间的若干条可达路由中选择8 条相对较短的路由，为资源预留提供方案评价和选 择的依据。 本课题设计了适应于m 4 n e t q o s 机制的路由优化算法的全部程序流程，在 v c + + 6 0 环境下进行了仿真设计与实现。仿真结果表明，本课题设计的m 4 n e t 的 路由优化算法路由无环路，具有j 下确性；达到收敛状态的平均进化代数为1 8 ，收 敛速度较快，各算子设计合理，使进化结果具有良好的总体性能。 关键字：m 4 n e t ：遗传算法：q o s ；路由优化 沈阳理工大学硕士学位论文 a b s t r a c t t h ec h a r a c t e r i s t i co fm o b i l es e l f - o r g a n i z e dn e t w o r ki s f l e x i b l e ，m o b i l ea n d l o w - c o s t m o b i l es e l f - o r g a n i z e dn e t w o r kh a sa l m o s tc o m ed o w nt ot h ef i e l d so fm i l i t a r y i k s ea n dc i v i l i a nu w 瓶t h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n i q u e s p e o p l ew i l ln o t b es a t i s f i e dw i t hd a t at r a n s m i s s i o ns e r v i c e b u tl o o kf o r w a r dt ot h ep r o m u l g a t eo fm o r e a n dm o r em u l t i m e d i at e c h n i q u e si n c l u d i n ga u d i oa n dv i d e o s ot h ed e m a n do fq o sf o r t h en e t w o r kt e c h n i q u ei s p u tf o r w a r d a l t h o u g ht h er e s e a r c h e r so fa dh o ch a s d e v e l o p e ds e v e r a lq o s a r c h i t e c t u r e sb a s e do na dh o c n e t w o r k ，t h eq o sc a p a b i l i t yc a n t m e e tt h er e q u i r e m e n tb e c a u s eo ft e c h n i c a li n s u f f i c i e n c yo fa dh o e t h e r e f o r e ，t h e t o p o l o g yo f m o b i l em u l t i - h o pm u l t i - l i n km u l t i m e d i an e t w o r k ( m 4 n e t ) i ss e tu p a tt h e s a m et i m e ，aq o sm e c h a n i s mo fm 4 n e tb a s e do nr e s o u r c er e s e r v a t i o ni sp u tf o r w a r d a c c o r d i n gt o t h en e wa d v a n c e m e n to fr e s o u r c er e s e r v a t i o n p r o t o c o la n dr o u t i n g o p t i m i z i n gt e c h n i q u e s t h eq o sm e c h a n i s mi s t h a tt h es o u r c en o d ec o m p u t e se i g h t o p t i m i z e dr o u t i n g sa n dr e s e r v e s r e s o u r c et e m p o r a r i l y , t h e nt h ed e s t i n a t i o nn o d e c o n f i r m st h em o s to p t i m i z e dr o u t i n ga n dr e s e r v e sr e s o u r c ef o r m a l l y , s ot h a tt h eq o so f m u l t i m e d i ai sc o n f i r m e d r o u t i n go p t i m i z i n gi sd i f f i c u l tf o rac o m p l e xn e t w o r kc o n t a i n i n ga sm o r ea s2 0 4 8 n o d e s a sa ni m p o r t a n tp o r t i o no ft h ep r o j e c t ，t h et h e s i sp r e s e n t st h em e a s u r e m e n t p r i n c i p l eo fq o sr o u t i n g ，t h e na n a l y s e ss o m er o u t i n gp r o t o c o l so f m o b i l es e l f - o r g a n i z e d n e t w o r k ，a tl a s tc o n f i r m sr o u t i n go p t i m i z i n ga l g o r i t h mb a s e do ng e n e t i ca l g o r i t h m a c c o r d i n gt o t h e c h a r a c t e r i s t i co fm 4 n e tb yc o m p a r i n gc o m m o nr o u t i n gs e a r c h e d a l g o r i t h m s t h et h e s i sr e a l i z e sr o u t i n go p t i m i z i n gb e t w e e ns o u r c en o d ea n dd e s t i n a t i o n n o d ei nm 4 n e t t a k i n gh o pa sm e a s u r e m e n t e i g h ts h o r t e rr o u t i n g sa r es e l e c t e db e t w e e n s o u r c en o d ea n dd e s t i n a t i o nn o d e ，w h i c hp r o v i d e st h ef o u n d a t i o nf o rr e s o u r c e r e s e r v a t i o n t h et h e s i sd e s i g n sa l lp r o g r a mf l o w so f r o u t i n go p t i m i z i n ga l g o r i t h mw h i c hi sf i tf o r t h eq o sm e c h a n i s mo fm 4 n e ta n ds e t su ps i m u l a t i o ns y s t e mu n d e rt h ee n v i r o n m e n to f v c + + 6 0 t h es i m u l a t i o nr e s u l t ss h o wt h a tt h em u t i n go p t i m i z i n ga l g o r i t h mo f m 4 n e t i sc o r r e c tb e c a u s et h e r e sn or i n gr o u t i n g ，t h e a v e r a g ee v o l u t i o n t i m e si s18 ， 沈阳理工大学硕士学位论文 c o n v e r g e n c ev e l o c i t yi sq u i c k e ra n dt h ea r i t h m e t i co p e r a t o r sa r er e a s o n a b l et h a tm a k e t h ep e r f o r m a n c eo f e v o l u t i o n a lr e s u l t sf a v o r a b l e k a yw o r d s ：m 4 n e t ，g e n e t i ca l g o r i t h m ，q o s ，r o u t i n go p t i m i z i n g 沈阳理工大学 硕士学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由作者 本人独立完成的。有关观点、方法、数据和文献的引用已在文中指出， 并与参考文献相对应。除文中已注明引用的内容外，本论文不包含任 何其他个人或集体已经公开发表的作品成果。对本文的研究做出重要 贡献的个人和集体，均己在文中以明确方式标明。本人完全意识到本 声明的法律结果由本人承担。 作者( 签字) ：影) 一、螽 日期 ：2 - 痂年1 月字日 学位论文版权使用授权书 本学位论文作者完全了解沈阳理工大学有关保留、使用学位论文 的规定，即：沈阳理工大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权沈阳理工 大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：拗 2 、篙指导教师签名： ，l 日期：沁以、g日期： 渤彬 2 即7 ，、8 第1 章引言 1 1 课题的提出 第1 章引言 移动计算与通信装置的迅速增长正在推动信息社会的变革。移动装置不仅体 积小、价格便宜、使用方便、功能强大，而且运行的应用和网络服务越来越多， 从而推动移动计算设备市场的爆炸性增长。 在移动装置的所有应用和服务中，网络连接和相应的数据服务毫无疑问是移 动用户最迫切需要的服务。当前，这些无线装置之间的大多数连接通过固定基础 设施服务提供方或者专用网络束实现。而基础设施网络提供了许多方法给移动装 置获取网络服务，这可能会花费大量的时间和很高的代价去建立必要的基础设施。 而军事作战的动态特性意味着战场军事通信不能依靠访问固定的、预先建立好的 通信设施。纯无线通信也存在局限性，无线信号易受干扰，高于1 0 0 m h z 的射频 几乎不能进行超视距的传输l 。 这些问题首先涉及到移动问题；第二涉及到不需要基础设施支持的问题：第 三涉及到动态自组织的问题；第四涉及到网络必须能够快速展开的问题。为此， 研究人员提出了不需要基础设施支持的移动a dh o c 解决方案。即通过自动配置使 移动装置相互连接，建立既灵活功能又强的移动a dh o c 网络。这样，移动节点不 仅能够相互通信，而且还能够通过网关节点接收其他异构网络的服务，有效地完 成异构网络之间的互连互通。 随着对信息的需求不断提高，人们已经不再满足于文本和话音信息，越来越 多的音频、视频等多媒体技术应用于信息的发布和传播，人们期望通能够实时地 获取保证质量的数据、音频和视频等多媒体信息，这就对网络技术提出了q o s 的 要求。虽然a dh o c 的研究人员也开发出几种基于a dh o c 网络的q o s 体系，但由 于a dh o e 网络本身技术的局限性，使得q o s 性能并不能满足需要。 针对上述需求，同时综合i p v 6 、资源预留协议、w i m a x 以及o f d m 等技术的 最新发展，提出了一种基于资源预留协议r s v p 的移动多跳多链路多媒体网络 ( m 4 n e t ) 的q o s 机制。m 4 n e t 是一种移动、多跳、具有自组织和自愈特点的无线 沈阳理工大学硕士学位论文 网络结构。 为实现m 4 n e t 中多媒体传输的q o s 功能，采用基于源节点计算的路由选择机 制，即在源节点和目的节点之日j 的若干条可达路径中选择8 条相对较短的路径， 为资源预留工作提供方案评价和选择的依据。 。 本课题的主要研究内容是分析q o s 路由的度量原则和移动自组织网络的路由 协议，在对比常用的路由搜索算法的基础上，根据m 4 n e t 的网络特征，采用基于 遗传算法的路由优化算法，以跳数为度量，实现m 4 n e t 的路由优化，并使用v c + + 6 0 建立软件仿真系统。 本研究出国家8 6 3 计划“空天信息传输与智能适配异构网络技术”资助。 1 2 国内外发展现状 ( 1 ) 移动自组织网络发展现状 a d h o c 技术起源于2 0 世纪7 0 年代，它是在美国国防部高级研究计划局 ( d a r p a ) 资助研究的“战地无线分组数据网( p 时姬t ) 1 2 l ”项目中产生的种 新型网络技术。d a r p a 当时所提出的是一种军用无线分组数据通信网络。后来， d a l i p a 又于1 9 8 3 年和1 9 9 4 年分别资助进行了抗毁自适应网络( s u r v i v a b l ea d a p t i v e n e t w o r k ，s u r a n ) 和全球移动信息系统( g l o b a li n f o r m a t i o ns y s t e m s ，g l o m o ) 0 1 两个项目的研究，以便能够建立某些特殊环境或紧急情况下的无线通信网络。a d h o c 技术就是吸取了p r n e t 、s u r a n 以及o l o m o 等项目的组网思想而产生的一种 新型的网络结构技术。美国军方一直在研究军方的a dh o e 网络技术。 随着移动通信和移动终端技术的高速发展，a dh o e 技术不仅在军事领域中得 到了充分的发展。而且也在民用移动通信中得到了应用。因特网任务工作组( i e t f ) 于1 9 9 6 年成立了m a n e t ( m o b i l e a d h o e n e t w o r k s ) 工作组，专门研究a d h o e 网络环境下基于i p 协议的路由协议规范和接口设计。这使得a d h o e 网络的设计思 路也由传统的单一技术体系过渡到基于i p 的多技术体系，从而导致该网络更具有开 放性、适应性、灵活性，提高了开发速度。随着配备有无线收发设备的高性能移 动终端的降价和将要随之而来的普及性，加上人们对于个人通信需求的日益增长。 使得无线a dh o e 网络的研究重新开始得到国内外研究人员的重视。特别是1 9 9 8 年 以来，无论是国内还是国外，各科研团体对无线a dh o e 网络的研究不断升温，尤 2 第1 章引言 其是在网络层的路由协议方面，其研究工作已经取得了很大的进展 4 1 。 无线m e s h 网( w i r e l e s sm e s hn e t w o r k ，w m n ) 可以看成是一种特殊的w l a n ， 除移动性较低外，w m n 本质上是一种a dh o c 网络。目前主要观点认为，w m n 是 一种由无线链路连接路由器和终端设备的静态无线网络，是i n t e m e t 的无线版本。 作为一种新型网络结构形态，m e s h 结构已被纳入至u 8 0 2 1 6 - 2 0 0 4 、8 0 2 1 6 e 和即将制 定的8 0 2 1l s 标准中【5 j 。 美国m e s h n e t w o r k s 公司己经开发了相关的无线硬件和智能路由软件，其构建 的无线m e s h i 网络支持诸如手机和笔记本等移动终端，这些终端可以自由接入或退 出网络，当两个或更多终端离开网络范围时，还可以组成自己的微型网。 由于新颁布的i e e e8 0 2 1 6 a 标准中己经明确提出把无线m e s h 技术应用于宽带 无线接入领域，无线m e s h n 络作为一种新的宽带无线接入方式己经引起了业界的 关注，它会对目前用于驻地用户宽带接入网络的d s l 技术和电缆技术带来很大的竞 争压力。很多公司已经开始将无线m e s h 技术用于宽带网络接入，并且相关的无线 路由器等产品也已开始商用，如诺基亚公司推出的无线路由器可以安装在屋顶上， 其产品目前已经获得超过5 0 家运营商的青睐，他们将借此建立以用户为基础的高 速无线网络。另外，无线m e s h 、智能天线和超宽带技术的融合更将深刻影响无线 宽带接入的未来1 6 1 。 ( 2 ) 移动自组网络路由协议研究现状 目前，国内外对移动a d h o c 网络的自组织算法和路由算法有非常多的研究。 但在移动a dh o c 网络和w m n 上，还没有路由协议正式标准。 针对a dh o c 网络，国外学者重点研究了单播路由的问题，即在网络拓扑变化 的动态环境中，针对“b e s t e f f o r t ”流量，如何获得高度可用的最短路径，已有的 单播路由协议分两类：表驱动路由协议( t a b l ed r i v e nr o u t i n gp r o t o c o l s ) 和需求路 由协议( o n - d e m a n dr o u t i n gp r o t o c o l s ) ，前者每个节点都保留着整个网络的最新 路由信息，后者则在网络节点有分组发送时，才在信源生成信源到信宿的路由。 c h e n 和g e r l a 提出一种满足带宽限制的a dh o c 网络单播路由算法，采用距离矢量法 收集端到端的q o s 信息，克服了以往a d h o c l i 目络路由算法只能支持“尽力而为”流 量传送的问题，但它是基于全局网络状态模型，并没有考虑网络信息的非精确性， 而且选路时只考虑最短路径，没有采用多路径路由策略，不能适用于a dh o c 网络 沈阳理工大学硕士学位论文 的q o s 。 m e s h 路由协议基本同a d h o c 网络路由协议，但需要针对w m n 的特点设计专门 适用于w m n 的高效路由协议。目前几种典型的路由协议有：d s d v ( 目的序列距 离矢量路由协议) 、d s r ( 动态源路由协议) 、t o r a ( 临时按序路由算法) 和a o d v ( a dh o c 按需距离矢量路由协议) 等。微软公司最近提出了一种多r f 收发器、多 跳无线网络的路由协议m r - l q s r ( m u l t i r a d i ol i n k q u a l i t ys o u r c er o u t i n g ) ，在 d s r 协议的基础上采用最大吞吐量准则。 虽然国际上已研究了多种无线移动自组网路由技术，但研究成果还仅适用于 “尽力”( b e s t e f f o r t ) 传输，不能为多媒体业务提供q o s 保证。有关a dh o c 网络 的q o s 保证的研究才h o h i j 开始，支持a dh o c 网络q o s 路由的论文还很少。研究健壮 有效的移动自组织网络的q o s 路由技术，实现用户的“无缝”漫游是当前路由技术 研究领域的难点和方向之一【 i 。 1 3 论文结构 第二章，通过分析移动a dh o c 和无线m e s h 网络特性，提出m 4 n e t 网络结构， 并对基于此网络的q o s 机制进行了研究。 第三章，介绍了后续算法所要考虑的q o s 度量，对移动a dh o e 和无线m e s h 网络常用的路由协议进行了分析，通过对比常用的路由搜索算法，确定了基于遗 传算法的m 4 n e t 的路由优化算法。 第四章，介绍了遗传算法基本原理，通过设计遗传算法各个运行阶段常用的实 施方案，完成了m 4 n e t 路由优化算法的整体设计与处理流程。 第五章，在v c + + 6 0 环境下对m 4 n e t 的路由优化算法进行了仿真设计与实现， 验证了算法性能，并分析了仿真结果。 最后是本文的总结，并提出了今后的研究思路。 第2 章m 4 n c t 总体设计 第2 章m 4 n e t 总体设计 m 4 n e t 的结构形式跟移动a dh o c 网络和w m n 都具有一定的相似性，都是没 有任何中心实体的自组织网络，依靠节点间的相互协作( 在事先设计好的各种协 议的支持下) ，在移动、复杂多变的无线环境中自行成网，借助于多跳转发技术来 弥补无线设备的有限传输距离，从而拓宽网络的覆盖范围，为用户提供各种服务， 传输各种业务。 2 1 移动a d h o e 网络概述 移动a dh o c 网络是由一组带有无线收发装置的移动终端组成的一个多跳临时 性自治系统。与传统无线网络不同的是，移动a d h o e 网络既不需要固定的网络结 构，也没有专用的固定的基站或路由器作为网络的管理中心，网络中每个节点具 有路由器功能，负责发现和维护到其它节点的路由，向邻居节点发射或转发分组。 在移动a d h o e 网络中，由于终端的无线传输范围有限，两个无法直接通信的终端 节点往往要通过多个中间节点的转发来实现通信，节点间的路由通常由多个网段 ( 跳) 组成，所以移动a dh o c 网络是一个多跳的系统。 ( 1 ) 移动a d h o c 网络的特点 夺无中心和自主性。a d h o e 网络中没有绝对的控制中心，网络中的节点通过 分布式算法来协调彼此的行为，无需人工干预和任何其他预先设置的网络 设施，可以在任何时刻任何地方快速展开并自动组网。 动态变化的网络拓扑。在a dh o e 网络中，移动节点可以任意速度和方式 在网络中移动，加上无线发送装置发送功率的变化、无线信道徊j 的相互干 扰、地形因素等的影响，节点间通过无线信道形成的网络拓扑结构随时会 发生变化。 受限的无线传输带宽。a dh o e 网络采用无线传输技术作为底层通信手段， 由于无线信道本身的物理特性，它所能提供的网络带宽相对于有线信道要 低得多，并且无线信道的质量较差。 夺移动终端的局限性。移动终端具有携带方便、轻便灵巧等优点，但同时也 沈阳理工大学硕十学位论文 面： 具有能源受限、内存小、c p u 处理能力低和成本高等缺点。 夺有限的安全性。a dh o e 网络是一种特殊的无线移动网络，由于采用无线信 道、有限电源、分布式控制等技术，它更加容易受到被动窃听、主动入侵、 拒绝服务等网络攻击。 夺无线多跳路由。由于发射功率的限制，节点的覆盖范围有限，当它要与覆 盖范围之外的节点通信时，需要借助中间节点的转发来实现 s l 。 ( 2 ) 移动a d h o e 网络的q o s 问题 在移动a dh o e 网络环境下支持q o s 具有独特的问题和难处，主要包括如下方 隐含终端问题。多跳分组中继传输引入了隐含终端问题。当两个节点的信 号相互不在其对方的电波传播的直接覆盖范围之内时，隐含终端问题就会 在这两个节点之间的某个公共中间节点上发生。 夺节点移动。节点移动导致动态的网络拓扑。当两个节点移动而相互直接进 入其对方的电波传播覆盖范围之内的时候，就动态地形成这两个节点之间 的链路；当两个节点移动而相互不在其对方的直接覆盖范围之内时，就动 态地拆除这两个节点之间的链路。 夺路由维护。网络拓扑的动态特性和通信媒介的变化特性使得精确维护网络 状态信息非常困难。因此，移动a dh o e 网络中的路由算法必须依靠本来 就不精确的信息来工作。此外，在移动a dh o e 网络环境中，节点可以在 任何时候进入网络，也可以在任何时候离开网络，已建立起来的路由即使 在数据传输过程中也可能中断，从而导致需要以最低开销和最小时延来维 护和重建路由。具有q o s 意识的路由应当要求在中间节点上预留资源。但 是，随着网络拓扑的变化，中间节点也随着变化，结果产生新的路径。所 以，使用路由中的更新进行资源预留维护变得很困难。 安全。安全可以看成q o s 的一个属性。没有足够的安全，未授权的访问和 使用会干扰q o s 协商。 2 2 无线m e s h 网络概述 无线m e s h 网络( w m n ) 是移动a dh o e 网络的一种特殊形态，它的早期研究源 - 6 第2 章m 4 n e 总体设计 于移动a dh o e 网络的研究与开发。是一种新型的宽带无线网络结构，即一种高容 量、高速率的分布式网络。 ( 1 ) w m n 与移动a dh o c 网络的区别 虽然w m n 与移动a dh o e 网络均是点对点的自组织的多跳网络，但从根本 上说，w m n 由无线路由器构成的无线骨干网组成。该无线骨干网提供了 大范围的信号覆盖与节点连接。然而，移动a dh o c 网络的节点都兼有独立 路由和主机功能，节点地位平等，接通性是依赖端节点的平等合作实现的， 健壮性比w m n 差。 夺w m n 节点移动性低于移动a dh o e 网络中的节点，所以w m n 注重的是“无 线”，而移动a dh o c 更强调的是“移动”。 夺从网络结构来看，w m n 多为静态或弱移动的拓扑，而移动a dh o c 多为随 意移动( 包括高速移动) 的网络拓扑。 w m n 与移动a dh o e 网络的业务模式不同，w m n 节点的主要业务是来往于 因特网的业务；移动a dh o e 节点的主要业务是任意一对节点之间的业务 流。 夺从应用来看，w m n 主要是因特网或宽带多媒体通信业务的接入，而移动 a dh o e 主要用于军事或其他专业通信1 9 l 。 ( 2 ) 目前w m n 存在的问题 在w m n 路由准则和选择算法方面，目前提出的特别是用于w m n 的路由协 议寥寥无几，m i c r o s o f t r e s e a r c h 虽提出了一种线性组合优化路由准nc , o l ， 但被优化变量的物理意义并非十分明显和直观，且引入的非线性运算使计 算复杂度大大增加。另外，也没有考虑全网带宽( 有效吞吐量) 开销，路 由算法没有对多媒体应用最敏感的o o s 因素给予足够的重视。 在w m n 连接性和多路支持方面，每个节点链路连接度也是一个至关重要 的问题，并非使用射频信道数越多，网络性能越好，射频信道数增加会带 来设备开销和成本上升，同时会带来更多的干扰问题。 在w m n 带宽利用和资源分配算法方面，目前还没有提出非常有效的可用 算法和协议，相关问题还有待研究 i l l 。 沈阳理1 大学硕十学位论文 2 3m 4 n e t 及q o s 机制 2 3 1m 4 n e t 网络拓扑 m 4 n e t 与移动a dh o e 和w m n 具有一定的相似性，都是不需要固定基础设施 支持，移动节点之间能够自动连接并能够互相通信，没有专用的固定的基站或路 由器作为网络的管理中心。由于终端的无线传输范围有限，两个无法直接通信的 终端节点往往要通过多个中间节点的转发来实现通信，是一个多跳的系统。但是 m 4 n e t 相对于移动a dh o c 网络和w m n 的特点就是在无线快速移动的自组织网络 中传输高质量的多媒体信息，也就是要实现话音、数据、图像及视频传输的q o s 功能。 m 4 n e t 是一个平面网络，节点可以自主移动，并能动态添加或删除。全网最 多包含2 0 4 8 个节点，由1 6 个链组组成，每个链组包含8 个边缘节点，每个链组 约由4 条相互平行且互通的链路组成，每条链路最多包含3 2 个节点，节点之间的 距离为5 1 0 k m 。1 2 8 个边缘节点为功能强大的计算机，具有信息存储和路由计算 功能；中间节点为小型的嵌入式芯片，不能进行路由计算，只具有存储转发功能。 网络中的每一个节点均维护一个全局的网络拓扑及其状态参数数据库。采用 w i m a x 技术实现网络节点之间的通信，其智能天线的平均覆盖范围约为3 0 k m ，节 点最大移动速度为3 0 k m h 。图2 1 为m 4 n e t 全网拓扑结构示意图。 图2 2 为前1 2 8 个节点的拓扑结构图，其中实线圆圈表示网络中已连接的节点， 虚线圆圈表示未连接的节点。 第2 章m 4 n n 总体设计 图2 1m 4 n e t 全网拓扑结构图 一一，+ 一i 一一 一一_ 一一 图2 2m 4 n e t 部分节点拓扑结构图 采用o s p f 技术进行网络析构，得到全局网络拓扑和状态参数的数据库。网络 中的每一个节点均维护这样的一个数据库。在此数据库中，网络中每个节点对应 9 沈阳理工大学硕士学位论文 一个邻接表，邻接表由本节点的所有邻居节点和邻居节点对应的邻接表编号组成， 数据库中共有2 0 4 8 个邻接表。如果节点1 的邻居节点为节点0 、节点2 5 6 、节点 2 5 7 、节点2 、节点2 6 0 和节点2 6 1 。则邻接表t 1 的格式如表2 1 所示。 表2 1 邻接表t l 示例 邻居节点 邻接表 节点0 邻接表t 0 节点2 5 6邻接表t 2 5 6 节点2 5 7 邻接表t 2 5 7 节点2邻接表t 2 节点2 6 0邻接表t 2 6 0 节点2 6 1邻接表t 2 6 l 图2 3 为数据库中l 号节点对应的邻接表t l ，图中，第一列为邻居节点，第二 列为各邻居节点对应的邻接表编号。 2 3 。2m 4 n e t 的q o s 机制 图2 3 邻接表t l 针对m 4 n e t 的网络特征，同时综合i p v 6 、资源预留协议、w i m a x 、路由优化 技术以及o f d m 等技术的最新发展，提出了一种基于资源预留协议r s v p 的移动 无线多跳多链路多媒体网络的q o s 机制，即在m 4 n e t 中，保证多媒体信息的可靠 传输，实现其q o s 功能。为实现多媒体传输的q o s 功能，采用基于源路由的路由 选择机制，在源端计算并选择8 条最短路由，沿这8 条路由进行资源检查和临时 预留，由目的端确定最优路由，并沿此最优路由正式预留资源、建立虚电路，从 而保证被选路由的q o s 在整个会话过程中得到维持。 采用o s p f 技术进行网络析构，得到全局网络拓扑和状态参数的数据库。由于 第2 章m 4 n e t 总体设计 智能天线的平均覆盖范围约为3 0 k i n ，节点最大移动速度为3 0 k m h ，可以每隔3 0 分钟需要进行一次全网的重构，为保证网络的可靠传输，将重构时间定为2 分钟。 在网络析构之后，利用深度优先搜索算法，在源节点的网络数据库中，选择 3 2 条可能的路径，以此作为遗传算法的初始种群。以跳数( h o p ) 为度量，使用遗 传算法计算源节点到目的节点的8 条优选路由。源节点分别向这8 条路径发送探 路包，探路包中包含一个单播请求，它由源节点s 、目的节点d ，以及q o s 请求 组成，q o s 请求包括带宽需求b 、包延迟要求d u 、包丢失率l u 和抖动j u 。每一 个中间节点在收到探路包后，若能向下转发，就把节点自身度量( 时延、费用、 延时抖动、包丢失率) 和前一段链路的度量( 时延、费用、链路带宽、延时抖动) 加入探路包中，根据q o s 请求为这条路径预留带宽，并开启一个计时器。 这样目的节点会收到来自源节点的，经过8 条不同路由发送过来的探路包。 探路包中包含特定路由的传输性能( 时延、费用、带宽、延时抖动、包丢失率) 。 路径的延时，等于该路径上所有路由器和链路的延时之和；路径可提供带宽，等 于路径上链路带宽的最小值；路径的延时抖动，等于路径上路由器和链路的延时 抖动之和；路径的包丢失率，等于路径上路由器的包丢失率之积：路径的费用， 等于路径上路由器和链路的费用之和。 目的节点分析比较这8 条路由的性能，选择一条最优路由，并沿此路由发送一 个应答包到源节点。源节点收到来自目的节点的应答包后，再沿此路径发送一个 申请包，申请包中也包含一个单播请求。收到申请包的中间节点正式预留带宽， 以后传输数据，将此路由作为最优路由，不需再迸行路由选择。只收到探路包， 未收到申请包的中间节点，在计时器超时后，取消其预留的带宽。资源预留原理 图如图2 4 所示。 侏鼯乜象跆田， 一 源 应答包( 最优路由) 目 节 的 点 节 点 申请包( 最优路由) 图2 4 资源预留原理图 综合以上分析，m 4 n e t 的单播q o s 机制实现步骤如下： 沈阳理工人学硕士学位论文 1 ) 源节点搜索数据库，找到3 2 条可达目的节点的路由。 2 ) 源节点使用遗传算法，以跳数为度量，计算其中8 条优选路由。 3 ) 源节点沿这8 条优选路由发送探路包，中间节点进行资源临时预留。 4 ) 目的节点分析这8 条路由的性能，选择一条最优路由。 5 ) 目的节点沿最优路由发送应答包到源节点。 6 ) 源节点沿此路由发送申请包，中间节点正式预留资源。 7 ) 其他7 条优选路由计时器超时，取消预留。 第3 章m 4 n e t 的路由优化技术 第3 章m 4 n e t 的路由优化技术 作为研究m 4 n e t 路由的基础，本章确定了课题后续算法所要考虑的度量，并对 移动自组织网络常用的路由协议进行了分析和比较，为m 4 n e t 采用的路由优化技术 提供了借鉴的依据。 3 1q o s 路由的度量选择 q o s 请求是涉及到多个方面的，如时延、带宽等。q o s 路由协议需要使用多个 度量参数来刻画网络特性。 3 1 1 常用网络性能度量 不同的性能度量反映网络不同方面的性能，常用的网络性能的度量2 l 如下： ( 1 ) 带宽：描述给定介质或连接的额定吞吐量，一般指应用程序在网络通信过 程中所需要的管道大小。如果路径的带宽小于数据传输所需要的带宽，则 路径不可用。 ( 2 ) 分组延迟和抖动：在分组转发的每一个中继段中，分组延迟包括串行化延 迟、传播延迟和交换延迟。如果发生网络拥塞，交换延迟将影响端到端延 迟并导致通过同一连接传输的分组延迟各不相同。分组延迟的变化程度称 为分组抖动，通过分组抖动可以估算接受方分组的最大延迟。 ( 3 ) 分组丢失率：在特定时问段内丢失的分组占传输的分组总数的比例。 ( 4 ) 费用：数据传输会占用一定的资源，就会有一些费用的消耗。费用可以是 管理成本、路由节点数等一些信息。 ( 5 ) 分组转发能力：各个路由器的分组转发能力并不相同，某个路由器可能并 非拥有同时向与其相连接的每条链路转发分组的能力。 3 1 2 路由的度量选择原则 度量选择是路由算法实现的基础，在选择度量时需要考虑几个方面，l 沈阳理工大学硕士学位论文 ( 1 ) 度量的选择必须要保证计算路径的有效算法存在。很明显，如果考虑因素 太多，导致路由算法实现复杂，不能在规定时间内完成，则所选度量是无 效的。 ( 2 ) 度量所包含的信息应能满足基本的q o s 需求。度量选择确定网络所能支持 的q o s 类型，如将费用和带宽作为网络度量，则路由算法不能保证支持对 时延有限制的q o s 请求。 ( 3 ) 度量必须正交，即任一度量不能是其它度量的函数。用混合度量难以客观 真实地反映网络特性，讨论q o s 路由需要分别考虑多个独立度量与q o s 请求的关系，从而判断路径是否满足q o s 约束。 3 1 3q o s 路由的度量选择思想 已有的路由算法是基于单一度量的。在研究q o s 路由时，首先想到的是原有的 采用单一度量的路由算法是否能在考虑多度量的情况下有效工作。一个典型的思 想就是以多个度量构建一个函数作为新的单一度量，则原有的路由算法可按照该 函数值进行路由计算，同时又体现了各个参数对网络性能的影响。例如，一个由 带宽b a n d w i d t h ，时延d e l a y 和丢失率l o s t r a t i o 组合的混合度量，其函数表达式为 m ) = 丽b 丽a n d 瓦w i d 历t h ( p 而) ( 3 1 ) 其中p 代表一条路由路径。可以看出：路径的带宽越大、时延和丢失率越小，贝u f ( p ) 越大，路径也越易于满足q o s 请求。看上去路由算法似乎可基 氓功这个单一度量 进行路径选择，但实际情况并非如此。假设b a n d w i d t h ( p ) 并不满足q o s 要求，而 d e l a y l o s t r a t i o ( p ) 小于某一阀值的话，如) 也可能得到一个较大值，但实际上由 于带宽因素，该路径不满足q o s 要求。因此，用混合度量难以客观真实地反映网络 特性。讨论q o s 路由，需要分别考虑多个独立度量与q o s 请求的关系，从而判断路 径是否满足q o s 约束胛】。 。 由于本课题采用基于资源预留的q o s 机制，而路由优化的目的是要从源节点和 目的节点之间选择最短的8 条路径，带宽、延迟、等参数在资源预留阶段的q o s 请 求中指明，采用遗传算法进行路由优化时，认为各节点之间的带宽、时延、费用 第3 章m 4 n e t 的路由优化技术 等为固定值。因此，路由优化阶段不考虑带宽、时延、费用等因素，仅以跳数( h o p ) 作为唯一的度量标准。 3 2 移动自组织网络常用的路由协议 3 2 1 移动a dh o e 网络的路由协议 移动a dh o c 网络的路由协议较多，可以分为两大类：前向表驱动 ( p r o a c t i v e t a b l e d r i v e n ) 协议和后向按需( r e a c t i v e o nd e m a n d ) 协议 15 1 。 ( 1 ) 前向路由协议 前向路由协议中，每个节点维护一张包含到达其它节点的路由信息的路由表。 当检测到网络拓扑结构发生变化时，节点在网络中发送更新消息，收到更新消息 的节点将更新自己的路由表，以保证能够一致、及时、准确的维护路由信息。节 点的路由表可以准确地反映网络的拓扑结构。源节点一旦要发送报文，可以立即 获得到达目的节点的路由。因此这种路由协议的时延较小，但是路由协议的开销 较大。现在已经提出了许多有效的可用于大型网络的前向路由协议。例如d s d v ( d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e c t o r ) 协议。 在d s d v 中，每个移动节点都需要维护一个路由表。路由表表项中包括目的节 点地址、跳数和目的节点序号，其中目的节点序号由目的节点分配，主要用于判 断路由是否过期，另外也可以防止路由环路的产生。每个节点必须周期性地与相 邻节点交换路由信息，同时也可以根据网络拓扑结构的变化来触发路由更新。节 点路由表的更新主要有两种方式：一种是全部更新，即拓扑更新消息中将包括整 个路由表，它主要应用于网络变化较快的情况；另一种方式是部分更新，即路由 表更新消息中仅包含变化的路由部分，通常适用于网络变化较慢的情况。在d s d v 中每次只使用序列号最高的路由，如果两个路由具有相同的序列号，那么将选择 最优的路由( 如根据跳数最短) 。在a d h o c 网络中使用d s d v 协议，当一个没有找 到路由的数据报文到达某个节点后首先被缓存，节点发送路由请求消息，直到接 收到来自目的节点的路由响应消息。当缓存溢出时，新到达的数据报文将被丢弃。 ( 2 ) 后向路由协议 后向路由协议是一种当需要发送数据时才查找路由的路由算法。在这种路由 1 5 沈阳理工大学硕士学位论文 协议中，节点不需要维护及时准确的路由信息，当需要向目的节点发送报文时， 源节点才在网络中起动路由查找过程，找到相应的路由。与前向路由协议相比， 后向路由协议的开销较小，但是数据报传送的时延较大。 后向路出协议在移动a d h o e 网络中也很常用。这类协议为了减少节点问路由 开销而只在需要通信时才发送路由报文。这类协议包括a o d v ( a d h o co n d e m a n d d i s t a n c e v e c t o r r o u t i n g ) 、d s r ( d y n a m i es o u r c e r o