（通信与信息系统专业论文）多播环境下的网络编码研究.pdf

重庆邮电大学硕士论文 摘要 摘要 近年来，无线网络的迅速发展促进了如应急通信、移动视频会议、多方游戏、 数据分发等多播技术的应用，这些应用对多播业务的需求越来越大。2 0 0 0 年， a h l s w e d e 等人提出网络编码，它能达到通信网络最大传输容量，有效提高多播网 络性能。目前基于网络编码改进多播性能的研究尽管有很多算法和模型提出，但 是实用性较差，其原因一方面在于用到的编码算法需要在全网络洪泛，即网络中 除信源节点和多播组成员节点外的所有其他节点均参与编码，造成网络编码代价 增大；另一方面在于现有的模型不适合无线多播网络节点的动态移动特性。 本文通过研究无线多播网络引入网络编码产生的问题，考虑多播组成员节点 的动态加入和离开对网络编码的影响，在最大流算法基础上提出一种改进的多播 网络编码路由算法，该算法能有效减小网络编码代价：考虑到节点的移动性可导 致局部链路的突然中断，影响网络编码正常工作，本文提出局部链路稳定预测机 制，它能提前预测链路是否将断开并无缝切换到新路由，保证链路的稳定性。本 文将改进的多播网络编码路由算法与局部链路稳定预测机制相结合提出动态多播 网络编码路由( d m n c ) 算法，同时给出该算法的详细流程设计、算法复杂度分 析和可行性证明，该算法结合随机网络编码算法能构成完整的网络编码多播路由 解决方案。 针对目前n s 2 仿真软件还没有网络编码模块，本文对n s 2 进行了以下扩展： l 、增加编解码模块，支持在有限域上的编解码运算；2 、扩展节点结构，使之支 持随机编解码功能。在n s 2 扩展模块基础上，本文将d m n c 算法结合m a o d v 协议实现改进的多播路由协议d m n c - m a o d v 。 本文设计了三种仿真场景，分别是通过增加信源节点数据流发送速率、增加 多播组接收节点的数量和增加节点的移动速度来对d m n c m a o d v 和m a o d v 两 种算法进行仿真对比，给出了平均吞吐量、分组投递率和平均端到端时延等参数 的仿真图。仿真结果表明，d m n c m a o d v 算法在一定的环境中应用，有助于提 高平均吞吐量和分组投递率，证明改进的d m n c m a o d v 算法具有有效性。 关键字：m a o d v ，网络编码，多播，动态，预测 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，t h er a p i dd e v e l o p m e n to fw i r e l e s sn e t w o r k , p r o m o t e dt h e s e a p p l i c a t i o n s s u c ha s e m e r g e n c yc o m m u n i c a t i o n s ，m o b i l e v i d e o c o n f e r e n c i n g ， m u l t i g a m e s ，a n dd a t ad i s t r i b u t i o n sd e v e l o p m e n t ，t h e s ea p p l i c a t i o n si n c r e a s i n g t h e d e m a n do fm u l t i c a s ts e r v i c e s i n2 0 0 0 ，a h l s w e d ee ta lp r o p o s e dn e t w o r kc o d i n g ，w h i c h c a i la c h i e v et h em a x i m u mt r a n s m i s s i o nc a p a c i t yo fc o m m u n i c a t i o nn e t w o r k sa n d e f f e c t i v e l yi m p r o v et h ep e r f o r m a n c eo f m u l t i c a s tn e t w o r k s c u r r e n t l yb a s e do nn e t w o r k c o d i n gt oi m p r o v et h ep e r f o r m a n c eo fm u l t i c a s ta l t h o u g ht h e r ea r em a n ya l g o r i t h m sa n d m o d e l sp r o p o s e d ，b u tl e s sp r a c t i c a l ，t h er e a s o no n eh a n di st h en e e df o rc o d i n g a l g o r i t h mu s e di nt h ew h o l en e t w o r kf l o o d i n g ，w h i c hi na d d i t i o nt ot h en e t w o r kn o d e a n dm u l t i s o u r c em u l t i c a s tg r o u pm e m b e rn o d e sa t eo u t s i d eo fa l lo t h e rn o d e si n v o l v e d i nc o d i n g ，n e t w o r kc o d i n gb r i n g sc o s t l y ；t h eo t h e rh a n d ，t h em o d e li sn o ts u i t a b l ef o rt h e e x i s t i n gw i r e l e s sn e t w o r kn o d em u l t i c a s td y n a m i cm o v e m e n tc h a r a c t e r i s t i c s t h i sp a p e rs t u d i e st h ei n t r o d u c t i o no ft h ew i r e l e s sn e t w o r km u l t i c a s tn e t w o r k c o d i n gp r o b l e m sa r i s i n gf r o mt h em u l t i c a s tg r o u pm e m b e r st oc o n s i d e rt h ed y n a m i c j o i n i n ga n dl e a v i n gt h en o d eo nt h ei m p a c to fn e t w o r kr o u t i n g ，i nt h em a x i m u mf l o w a l g o r i t h mb a s e do na ni m p r o v e dn e t w o r kc o d i n gf o rm u l t i c a s tr o u t i n ga l g o r i t h mt h e a l g o r i t h mc a ne f f e c t i v e l yr e d u c et h ec o s to fn e t w o r kc o d i n g ；c o n s i d e rn o d em o b i l i t yc a l l l e a dt oas u d d e ni n t e r r u p t i o no fl o c a ll i n k s ，a f f e c t i n gn o r m a ln e t w o r kc o d i n g ，w e p r o p o s et h e l o c a ll i n ks t a b i l i t yp r e d i c t i o nm e c h a n i s mt h a tc a np r e d i c ti na d v a n c e w h e t h e rt od i s c o n n e c tt h el i n ka n ds e a m l e s s l ys w i t c ht ot h en e wr o u t e ，t oe n s u r et h e s t a b i l i t yo ft h el i n k t h i sw i l li m p r o v et h er o u t i n gm u l t i c a s tn e t w o r kc o d i n ga l g o r i t h m a n dt h el o c a l l i n ks t a b i l i t yp r e d i c t i o nm e c h a n i s mc o m b i n i n gad y n a m i cr o u t i n g m u l t i c a s tn e t w o r kc o d i n g ( d m n c ) a l g o r i t h m ，t h ea l g o r i t h mi sg i v e nd e t a i l e dp r o c e s s d e s i g n ，a l g o r i t h mc o m p l e x i t ya n a l y s i sa n df e a s i b i l i t ys h o w st h a tt h ea l g o r i t h mw i t h r a n d o mn e t w o r kc o d i n ga l g o r i t h mc o u l df o r mt h em u l t i c a s tr o u t i n gn e t w o r kc o d i n g s o l u t i o n b e c a u s eo ft h ec u r r e n tn s 2s i m u l a t i o ns o f t w a r ed o e s n th a v en e t w o r kc o d i n g m o d u l e ，s ot h ep a p e re x p a n s i o nn s 2a b o u t ：1 ，i n c r e a s et h ee n c o d i n ga n dd e c o d i n g m o d u l e st os u p p o r tal i m i t e dd o m a i ni nt h ec o d i n ga n dd e c o d i n go p e r a t i o n s ；2 ，t h e e x p a n s i o no fn o d es t r u c t u r e ，s ot h a ts u p p o r tr a n d o mc o d e c s b a s e do nt h ee x p a n s i o n 重庆邮电大学硕士论文 a b s t r a c t m o d u l ei nn s 2 ，d m n ca l g o r i t h mc o m b i n e d 谢t l lm a o d v p r o t o c o lf o r m e dt h en e w m u l t i c a s tr o u t i n gp r o t o c o ld m n c - m a o d v t h i sp a p e rd e s i g n st h r e es i m u l a t i o nm o d e l s ，w h i c ha r ed a t af l o wb yi n c r e a s i n gt h e s e n d i n gr a t eo fs o u r c en o d e ，r e c e i v i n gn o d em u l t i c a s tg r o u pt oi n c r e a s et h en u m b e ro f m o b i l en o d e sa n di n c r e a s et h es p e e do fd m n c m a o d va n dm a o d vs i m u l a t i o n c o m p a r i s o no f t w oa l g o r i t h m s ，g i v e nt h ea v e r a g et h r o u g h p u t ，p a c k e td e l i v e r yr a t i oa n d a v e r a g ee n dt o e n dd e l a yo ft h es i m u l a t i o nm a p s i m u l a t i o nr e s u l t ss h o wt h a t , d m n c - m a o d va g r e e m e n tr e f e r e n c e di nac e r t a i n e n v i r o n m e n t ，h e l pt oi m p r o v e n e t w o r kt h r o u g h p u ta n dp a c k e td e l i v e r yr a t e ，w i t he f f e c t i v e n e s s k e y w o r d s ：m a o d v , n e t w o r kc o d i n g ，m u l t i c a s t , d y n a m i c ，p r e d i c t i o n i i i 重庆邮电大学硕士论文 第一章绪论 1 1 研究背景 第一章绪论 2 l 世纪是信息迅速发展的时代，无线网络( 如无特殊说明，本文中无线网络 是指无线自组织网络、无线m e s h 网络和无线传感器网络) 的快速发展越来越紧密 地联系着人们的工作和生活。在无线网络中，各节点既可以作为信息的终端节点， 又可以作为中继节点。由于无线链路具有动态、时变和丢失等特性，导致无线链 路质量较差且稳定性较低，这需要无线网络具有更高的传输可靠性和吞吐量。无 线网络经过长期研究，在网络路由方面已经出现新的研究分支，可以分为间歇性 连接和任意时刻总是连通两种情况。间歇性连接网络【l 】常常利用节点的移动来携带 信息、创造新的通信机会，最终期望以较高的成功率实现端到端通信，这类通信 网络的分组投递延迟很大( 如几分钟乃至几小时) ，这样的网络被称为机会网络。 本文研究面向任意时刻总是连通的无线网络，针对的是应用延时要求较小( 如几 百m s 到1 - 2 s ) 的无线网络。 近年来，随着各种多媒体应用在无线网络中的出现，促进了如应急通信、移 动视频会议、多方游戏、数据分发等一对多或多对多的多播技术应用。这些应用 对多播业务的需求越来越大，对现有的无线网络承载能力提出了极大挑战。多播 技术是希望把信息同时传递给一组具有相同组地址的多播组成员，传统的方式是 在网络中寻找一棵有效的多播树，此种多播方式下，网络中的中继节点只对数据 分组进行简单的存储和转发，难以达到“最大流最小割 定理确定的最大传输容 量1 2 , 3 一。如何优化提升多播通信中的网络资源利用率，已是当今网络通信研究的主 要领域之一。 r u d o l fa h l s w e d e 、n i n gc a i 等人于2 0 0 0 年提出网络编码l 引( n e t w o r kc o d i n g ， n c ) 概念，同时证明了在理论情况下，网络编码可以达到通信网络的最大传输容 量，节省网络资源。网络编码打破传统多播通信中的节点仅对数据的存储和转发 能力，赋予节点对数据进行操作和处理的能力，允许网络节点在转发数据前对接 收到的数据进行编码操作。网络编码彻底改变了通信网络中信息处理和信息传输 的方式，被认为是进入2 l 世纪后信息处理和信息传输研究领域上最重要的理论成 果之一。它作为一项新兴技术，从理论到实际应用都还处在不断完善和丰富的阶 段，需要展开全方位的研究。 重庆邮电大学硕士论文 第一章绪论 1 2 无线网络编码国内外研究现状 自网络编码提出以来，就引起了国际学术界在理论和应用方面的关注和重视。 几年前，国外许多著名大学和研究机构就已经展开网络编码在理论和应用方面的 研究，如麻省理工大学【6 1 、瑞士e p f l 学院阴、普林斯顿大学嘲、微软研究院【9 1 、 a t & t 的香农信息实验室【l o 】、贝尔实验室【l l 】等等。近年来，网络编码在国内的研 究也已经逐渐引起重视，比如我国的清华大学1 2 1 、西安电子科技大学【1 3 】、南京大 学【1 4 1 等高校都在积极开展对网络编码的研究。 网络编码的优越性包括均衡网络负载、提高带宽利用率、增强网络鲁棒性等， 可应用在a dh o c 网络、p 2 p 文件分发、无线m e s h 网络、传感器网络、网络安全 等领域。经过前期的不断发展，网络编码已经取得一定进展，目前网络编码在各 个领域的研究正在全方位展开。 近年来，无线环境下的网络编码研究已经成为一个重要的研究方向。无线网 络具有信道不可靠、数据传输速率低和物理层广播等特性，尝试运用网络编码提 高其性能已经显得非常必要。根据网络间节点的通信方式，可以简单的将无线网 络中的网络编码分为无线单播和无线多播两类进行研究。本节分别对无线单播网 络编码和无线多播网络编码研究现状进行分析。 1 2 1 无线单播网络编码 2 0 0 5 年，s k a t t i 等人【b j 在无线单播网络中提出基于机会主义的网络编码机制 c o p e ，并研究了网络编码在实际无线环境中的实现问题。c o p e 机制利用无线网 络广播特性，通过节点的机会侦听和机会编码来减少数据包在网络中的传送量， 在无线节点能量、提高吞吐量方面提高了无线网络的性能。 s k a t t i 等人指出运用网络编码能在无线单播传输中提高网络吞吐量，但是吞 吐量的上限是多少? l i uj 等人【1 6 j 7 】在随机拓扑上加入网络元素，讨论在无线环境 下多条单播数据流产生的吞吐量上限。证明了在物理通信模型和协议通信模型的 无线网络编码，多条单播数据流提高吞吐量上限都为常数因子。因此，在无线网 络中引入网络编码或未引入网络编码，吞吐量的上限均为常数因子。 确定了无线网络中网络吞吐量为常数因子后，新的问题浮现出来：在实际无 线网络中运用网络编码，网络吞吐量能够提高多少? 是否能够达到网络容量? s e n g u p t as 等人【1 8 j 首先注意此问题，在已知全局拓扑和单播传输的理想情况下，给 出了单播传输最大吞吐量。c h a p o r k a rp 等人【1 9 】在s e n g u p t as 的研究基础上，通过 两个实例证明在某些情况下，无线网络中引入网络编码会导致网络吞吐量下降。 此种现象反映了一个确定性事实，网络对吞吐量的提高需要有相应的数据分组调 2 重庆邮电大学硕士论文第一章绪论 度算法对其支持，c h a p o r k a rp 等人同时给出了一个编码框架，将编码方案和数据 分组调度相结合。 在c h a p o r k a rp 和s e n g u p t as 研究的基础上，大多数研究者开始设计有效的编 码方案提高无线网络中单播传输的吞吐量。s c h e u e r m a n nb 等人【2 0 】研究怎样创造编 码机会，并给出一个跨层编码方案。c h ik 等人【2 l 】改进对c o p e 机制的数据编码策 略，进而有效地提高网络吞吐量。o m i w a d es 等人l 2 2 j 对无线网络中节点功能进行 扩展，给出了新的编码机制。c u i t 等人【2 3 】提出一种高效的无线网络编码方案，综 合考虑了数据流内编码和数据流间编码。k o u t s o n i k o l a sd 等人【2 4 】对一中等规模的 无线m e s h 网络进行研究，表明在实际环境下通过网络编码带来的收益是极为有 限。 无线单播网络编码的研究还包括物理层的网络编码以及基于网络编码感知的 无线路由网络路由机制等。由于本文主要研究无线多播环境下的网络编码，因此 对无线单播的描述到此为止。 1 2 2 无线多播网络编码 网络编码起源于有线网络多播传输，主要解决多播传输最大流问题，随着研 究的不断深入，发展到在无线多播网络中形成新的研究分支无线多播网络编码。 在无线网络中，初期对网络编码的研究主要是对如何提高a dh o c 网络多播吞吐量 和节省节点能量消耗问题。w u 等人【2 5 】期望通过网络编码的应用来解决a dh o c 网 络的多播最小能量问题，将此问题转化为线性规划问题。l 吼等人1 2 6 j 通过研究减 少节点的能量消耗方面，给出最小费用多播概念。 y u a nj 等人【2 7 】希望采用跨层优化策略，提高了无线a dh o e 网络中网络编码的 多播吞吐量，但是此方法增加了在实际应用中的复杂性。w h y 等人瞄】证明了只要 在进入转发节点的链路上实施网络编码就可以达到无线a dh o e 网络多播吞吐量上 限，此方法降低了网络编码带来的算法复杂度。t a n gs k 等人【2 9 j 采用多重分离路 径算法计算信源节点到信宿节点的分离路径数量，给出了使用线性编码提高a d h o e 网络多播吞吐量的编码方案。l i ny f 等人【3 0 】通过研究网络编码在实际无线网 络中应用时存在的问题，提出了将网络编码与多路径路由相结合的编码方案来提 高多播吞吐量。陶等人【3 l 】研究基于最大流的多播网络编码，并证明了该算法能够 有效提高多播性能。李姗姗等人1 3 2 】研究了网络编码在无线传感器网络中多路径传 输方法。 重庆邮电大学硕士论文 第一章绪论 1 3 研究内容 作者查阅了近十年相关文献后，对网络编码国内外研究现状进行分析，目前 基于网络编码改进多播性能的研究尽管有很多算法和模型提出，但是实用性较差， 其原因一方面在于用到的编码算法需要在全网络洪泛，即网络中除信源节点和多 播组成员节点外的所有其他节点均参与编码，造成网络编码代价增大；其次，现 有的模型不适合无线多播网络节点的动态移动特性。本文考虑研究动态多播环境 下的网络编码路由算法。论文研究内容包括： l 、改进最大流算法：采用标号算法，计算信源到所有接收者的最大流值和最 大流路径，再通过网络编码，使多播组的吞吐量达到多播的最大流值，即该多播 组中信源到所有接收者的最大流的最小值。 2 、局部链路稳定预测机制：在无线多播网络中，针对节点移动导致的链路断 开，该机制可在链路即将断开之前无缝切换到新路由，保证链路的稳定。 3 、动态多播网络编码( d m n c ) 路由算法：该算法支持多播组成员的动态加 入和退出，并且该多播组的吞吐量能达到信源到各个接收者的最大流集合中的最 小值。 4 、仿真及性能评估：在l i n u x 环境下的n s 2 平台上实现该算法，并进行性能 评估。性能评估的参数有平均吞吐量、分组投递率和平均端到端时延。 1 4 论文组织结构 本文共分六章，各章的内容安排如下： 第一章介绍了本文的研究背景，无线网络编码的国内外研究现状和研究内容。 第二章分析总结无线网络中多播路由协议，并对网络编码技术的基本原理、 数学模型、优缺点及应用进行了分析。 第三章研究了无线多播网络中引入网络编码产生的问题，并给出解决方法。 第四章给出动态多播网络编码路由算法和局部链路稳定预测机制，以及 d m n c m a o d v 协议。 第五章介绍仿真环境，以及修改d m n c 。m a o d v 协议的地方，并将改进后的 路由协议d m n c m a o d v 与m a o d v 进行仿真比较分析。 第六章总结本文所做工作，并探讨下一步的研究方向。 4 重庆邮电大学硕士论文第二章关键技术研究 第二章关键技术研究 网络编码在无线网络中更能够发挥其优越性，应用网络编码，可解决跨层设 计、传统路由等技术不能解决的问题。d e bs 等人1 3 3 1 对网络编码在无线自组织网络 ( w i r e l e s sa dh o en e t w o r k s ) 的应用进行了探讨，a 1h a m r aa 等人【3 4 j 对网络编码在 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ) 中的应用进行了探讨，y u n n a nw u 等人 1 3 5 j 对网络编码在无线n j 状n ( w i r e l e s sm e s hn e t w o r k s ) 中的应用进行了探讨。在无线 网络中应用网络编码可提高网络吞吐量，特别是多播网络吞吐量。本文在无线多 播网络中研究网络编码，涉及到无线网络技术和网络编码技术，因此对这两种技 术进行研究很有必要。 2 1 无线网络技术 近年来，随着网络通信技术的快速发展，各种无线网络技术也得到普及和应 用，无线自组织网络、无线传感器网络以及无线网状网更是越来越多的得到关注 与研究。 无线自组织网络由一组无线移动节点组成，不需要固定基础设施并能够迅速 展开使用的网络。它是没有任何中心实体、自组织、自愈的网络，节点间相互协 作完成信息交换和服务共享，而且节点可以动态、频繁、随意加入和离开网络。 图2 1 是典型的无线自组织网络，它具有以下特性：l 、网络自组织；2 、网络拓扑 结构动态变化；3 、分布式控制；4 、采用无线信道传输，带宽有限；5 、网络安全 性较差。 图2 1 无线自组织网 无线传感器网络是当前国际上涉及学科高度交叉，备受关注的前沿研究领域。 无线传感器网络虽然与无线自组织网络有相似之处，但同时也存在差别，大多数 重庆邮电大学硕士论文 第二章关键技术研究 情况下，无线传感器网络节点是固定不动的，并且节点能量和处理能力有限。因 此对于无线传感器网络来说，节省能量，保证能量高效利用是研究重点。 感知现场 用户 。 传感节点 图2 2 无线传感器网 无线m e s h 网络与无线自组织网络存在一定的差异，无线m e s h 网络一般由客 户端节点、m e s h 路由器节点和网关节点组成。它是从移动a dh o c 网络分离出来 的技术，并承袭了部分w l a n 技术的新网络技术。它具有以下特点：1 、无线多 跳网络；2 、具有自组织、自管理、自愈合能力；3 、多种类型网络接入；4 、移动 性和能耗与节点有关；5 、具有无线基础设施骨干网；6 、拓扑结构相对稳定；7 、 功耗限制较少。 图2 3 无线m e s h 网络 通过对以上3 种网络的简单分析，可以总结出他们的共同特性如下：1 、节点 具有移动性；2 、采用无线信道传输，链路具有不可靠性；3 、拓扑结构有可能变 动；4 、节点能量有限。 6 重庆邮电大学硕士论文第二章关键技术研究 2 1 1 无线多播概念 多播技术的出现有效解决了单点发送多点接收和多点发送多点接收的问题， 实现了网络中数据同时发送到多点的高效传送，能降低网络负载和节省带宽。在 通信网中通过建立多播树来实现多播，图2 4 展示了单播网络与多播网络的区别， 其中s 为源节点，t 1 、t 2 、t 3 为多播组节点，n 为普通节点，a - g 为路由节点。 ( a ) 单播( b ) 多播 图2 4 典型单播与多播拓扑图 定义2 1 ( 无线多播网络) ：给定无线网络g = ( 矿，e ) ，其中矿表示网络节点的 集合，e 表示传输链路的集合，信源节点的集合用s 表示，信宿节点的集合用r 表 示。无线多播网络信息发送可表示为： s t 0 f 訇丁i ，丁y 式( 2 1 ) 2 1 2 无线网络多播路由协议 目前许多研究者对无线传感器网络、无线m e s h 网络的多播路由协议研究，都 是通过深入研究a dh o e 网络多播路由之后，通过与a dh o e 网络特性的对比，结 合无线传感器网络、无线m e s h 网络的特点，设计出相应的多播路由协议，因此， 对无线网络多播路由协议研究的基础是深入研究a dh o e 网络多播协议。a dh o e 网络多播路由协议可根据路由建立和维护时机分为先验式路由和按需路由，也可 根据网络拓扑结构不同，分为：基于树的多播路由协议，基于网格的多播路由协 议，以及混合多播路由协议。下面根据网络的拓扑结构分类对多播路由协议进行 介绍。 1 、基于树的多播路由协议 在基于树的多播协议中，多播组成员之间是通过一棵由所有多播组成员构成 的最小代价生成树进行连接，该结构需要建立和维护这棵最小生成树，用于多播 数据转发。基于树的多播路由协议又可分为基于共享树和基于源树两种，基于树 的协议存储需要的开销小，扩展性好，但信源节点改变反应慢，可导致路径非最 7 重庆邮电大学硕士论文 第二章关键技术研究 优。基于源的协议，每个节点都有一棵以自己为根的多播树，它能连接该多播组 所有成员，它的优点是信源节点到多播组成员节点的路径是最短路径，通信量比 较分散，但是它开销太大，不易扩展。 基于树的多播路由协议具有路由决策简单、传输效率高等优点，但由于无线 网络拓扑结构的动态变化影响，导致网络鲁棒性不好，多播树中只要有一段链路 出现故障就需要重构多播树，树的维护开销也比较大，协议健壮性不强。典型的 基于树的多播路由协议有a m r i s 、m a o d v 等。 w 对s 也是一种基于共享树的按需多播路由协议，该协议采用了m s m i d 概 念，该协议动态为每一次会话的所有节点分配一个m s m i d 。a r m i s 利用m s m - i d 决定多播数据的传输方向，与相邻节点的m s m i d 值有隔离，方便新节点的加入和 链路修复。当链路中断时，a r m i s 采用信息标机制维护链路信息，m s m i d 较大的 节点执行b r 算法来修复链路。a r m i s 具有链路修复快速、局部化的特点，并且 不需要底层单播协议支持。在节点移动性增强、网络负载变大时，a r m i s 协议中 控制分组数量和信标消息大小都会增加，这就可能引起冲突，导致a r m i s 协议的 性能变差。 m a o d v 多播路由协议是在a o d v 单播路由协议的基础上进行的扩展，增加 了一条新消息多目标激活( m a c t ) 消息。m a o d v 是一种基于共享树的按需 多播路由协议，在有数据分组需要交付给多播组成员节点的时候才寻找路由。 y u f a n gz h u 等人1 3 6 1 对m a o d v 路由协议进行了详细介绍。 2 、基于网格的多播路由协议 根据前面对基于树的多播路由协议描述，可看出虽然具有较高的传输效率， 但它的可扩展性和鲁棒性都较差。在基于网格的多播路由协议中，多播组节点构 成的拓扑结构为格状，并存在源节点到目的节点冗余路径，因此某一条链路的失 效可能并不会受到影响，提高了网络的鲁棒性。基于网格的多播路由协议健壮性 较好，典型的协议有：o d m r p 、c a m p 等。 o d m r p 多播路由协议能在节点移动以及拓扑结构变化的情况下，建立网格和 提供多跳路由，将多目标信息交互给信宿节点。它的优点是健壮性强，存储开销 小，维护和使用多跳冗余路径，从而提高数据转发的成功率，但是o d m r p 多播 路由协议的可扩展性较差。在多播网格规模变大的情况下，在网格内洪泛的方法 会使分组数据包数量剧增，同时增加了更多的控制开销，导致其性能严重下降。 c a m p 是核心辅助的网格协议，它依赖于单播路由协议，通过创建一个共享 网格来维护每个多播组成员之间的连接。因为c a m p 依赖单播路由协议，所以要 维护一个路由表，路由表包括到所有目的节点的下一条信息和距离。c 蝴p 多播 路由协议把节点分为了双向模式、单向模式以及非成员节点三种模式。 8 重庆邮电大学硕士论文第二章关键技术研究 3 、混合多播路由协议 通过对基于树和基于网格的多播路由协议进行了简单分析，基于树的多播路 由协议分组转发有效性可能较高，但是它的鲁棒性较差，而基于网格的多播路由 协议虽然鲁棒性较好，但它是以牺牲有效性为代价。因此，许多学者试图将两类 多播路由协议的优点进行结合，从而提高总体性能。目前基于混合的多播路由协 议主要有a m r o u t e 和m c e a d r 。 2 1 3a dh o c 多播路由协议比较 根据以上分析，a dh o c 网络多播路由协议以为分组成员建立一条路径，且冗 余最小为基本思想，前面的各种多播路由协议都是用不同的机制来试图达到这个 目标。在多播路由协议的设计中，需要考虑以下问题：节点的移动性，选择的路 径和节点稳定性，有无可能产生环路，控制分组的传输方式，路由信息的更新， 是否按需创建路由等。表2 1 对部分经典多播路由协议进行了比较【3 7 1 。 表2 1a dh o e 网络多播路由协议比较 m a o d va m r i so d m r p c a 咿a m r o u t e 多播结构共享树结构共享树结构格网格网混合 无环路性是是是 是否 是否依赖单播 是否是否是 按需主动式按需主动式按需主动式主动式 周期性消息是是是 是 是 控制分组是否 是是否是是 洪泛 最新和最短路最长生存时间的 路由量值最短路径最短路径最短路径 径 路径和链路 2 2 网络编码技术 网络编码的概念起源于多播问题，r u d o l fa h l s w e d e 、n i n gc a i 等人【5 j 于2 0 0 0 年根据信息流的概念提出网络编码，指出对来自不同链路的数据包进行组合发送， 能够得到网络多播的最大流限，此极限在多种情况下是无法根据传统的多播机制 实现，这就体现了网络编码的优点。在r u d o l fa h l s w e d e 等人f 5 j 发表的文章中，以 蝴蝶网络来说明网络编码是如何达到最大流限。图2 5 对传统的多播方式和使用网 络编码后的多播方式进行了对比。 9 重庆邮电大学硕士论文 第二章关键技术研究 ( a ) 传统多播 ( b ) 基于网络编码的多播 图2 5 两种多播方式对比 2 2 1 网络编码基本原理 初期的网络编码是在无环有向图上提出的，后来才扩展到有环、有延时、以 及实际的网络等复杂情况。网络可抽象为由顶点和连接顶点的边组成的图，图可 以是无向或者有向的，可表示为g = ( y ，e ) ，其中v 为顶点集，e 为边集。而一个 实际的通信网络是一个规模有限的每条边有一个容量值的有向图，表示在单位时 间内可传输的最大信息流。在通信网络中，将边称为信道，顶点称为节点，在单 位时间内，信道上传输的信息流不能大于信道容量。在通信网络中定义源节点是 没有信息输入信道，信宿节点是没有信息输出信道，中继节点仅是信息的存储转 发。整个通信网络的信息流量是守恒的。 定义2 2 ( 割集) ：在通信网络g = ( y ，e ) 中，如果移去信源节点s 与信宿节 点t 之间的边集，使得s 和t 失去连通性，割的大小是割集中边的容量的总和。 当割的值小于其他任何割值，则称为最小割，最小割值是唯一的，但在一个通信 网络中可能存在多个最小割。 f o r d 和f u l k e r s o n 研究在一个给定的网络上寻求两点间的最大运输量问题时， 证明了最大流最小割定理，表明两点间的最大信息传输速率等于两点间的最小割， 最大流最小割定理如下： 定理2 1 ( 最大流最小割) ：考虑图g = ( y ，e ) ，图g 中边都是单位容量，s 为源节点，t 为接收节点。如果s 与t 之间最小割为h ，那么从s 发送信息到t 的最大速率为h 。也表示s 与t 之间有h 条不相交的路径。 图2 6 是在一个单位网络中的最小割示例，在该网络中有两个最小割，如图 2 6 a 虚线所示。该网络的最小割值为3 ，说明源节点到目的节点之间有3 条不相交 的路径，如2 6 b 所示。 1 0 重庆邮电大学硕士论文 第二章关键技术研究 ( a ) 最小割 ( b ) 不相交路径 图2 6 最小割示例 网络编码的核心思想是允许中间节点对信息进行处理，r u d o l fa h l s w e d e 等人 给出了网络编码的基定理，并证明在允许网络的中间节点编码的条件下，就能够 达到最大流最小割定义的多播容量。 2 2 2 线性网络编码模型 在信息经过网络节点时对其进行线性操作，那么称为线性网络编码，否则为 非线性网络编码。如果节点对编码操作的系数是随机选取的，那么称为随机网络 编码；如果系统是通过确定性算法来选取的，那么称为确定性网络编码。l is y 等人【3 8 】指出，在足够大的有限域尼中采用适合的线性网络编码，总是能实现多播 传输的最大流限，本节对多播网络中的线性网络编码模型进行描述。 线性网络编码模型根据信源节点不同可分为单源和多源线性网络编码模型， 他们的区别在于多源网络编码模型具有多个源节点。图2 7 展示了单源和多源两种 模型，2 0 0 6 年r w y e u n g 等人f 3 9 j 证明了在多源网络模型中引入一个虚拟节点可等 效为单源网络模型，证明过程详见其文章，本文主要研究单源线性网络编码模型。 ? i 。： 图2 7 单源和多源网络编码模型 定义2 3 ( 线性编码多播) 1 4 0 1 ：线性编码多播( l i n e a rc o d em u l t i c a s t ，l c m ) 就是给无环有向网络g = ( y ，e ) 中每个节点m v 赋予一个空间向量v ( m ) 。给每条 链路e ( x ，y ) e 赋予一个编码向量，使得： 1 、v ( s ) q ，q 为信源发表的足够大的域c 上h 维符号向量空间； 2 、对于每条链路a y ，均有v ( x y ) ，( x ) ； 重庆邮电大学硕士论文 第二章关键技术研究 3 、对于任何非源节点集合： q = 矿 s ： = ，其中 表示向量张 成的空间。 l c m 给出了用信息流描述网络中信息编码和传输的统一方式。 假设l c m 理论最大传输容量为h ，信源节点s 发出的信息向量为 b = 6 l ，b 2 ，】，那么在单位容量网络中，信源s 与每个信宿f ，t 之间都能建立办 条互不相交的路径，标记路径簇为( s ，f ，) 。用口= 【口i ，a ；，a ：】r 表示( s ，) 路径簇 上各条路径的最后一条链路上信息传送的集合。假设第f 条链路上的编码向量为 【聊j ，聊乏，埘二】7 。 那么这条链路上传输的信息可表示为 口? = 聊擒+ m 是6 2 + + ，以玩。对于信宿节点f 的h 条输入链路，传输的信息流向量 为： a i ， a ； a ： a 6 2 - 钆 = 鸠b 7 式( 2 2 ) 则信源发出的符号向量为6 r = 何1 a 。 如果鸠满秩，则当收到路径簇( s ，) 上 个信息流向量a = a i ，口! ，口：】r 后， 信宿节点f j 就能通过6 r = 何1 a 译出信源发出的原始信息【6 l ，6 2 ，瓦】。 定理2 - 2 ( 可行网络编码) 4 0 i ：使所有信宿节点对应的转移矩阵m 满秩( f u l l r a n k ) 的网络编码称为可行网络编码( f e a s i b l en e t w o r kc o d i n g ) 。 2 2 3 网络编码的优缺点 初期网络编码的提出是希望使多播传输能达到网络最大流限，从而提高多播 网络吞吐量。但是随着研究者们对网络编码不断深入的研究，网络编码在其他方 面的优点也逐渐开始体现出来，如提升带宽利用率、网络负载均衡等。 l 、提高网络吞吐量 提升网络吞吐量是r u d o l f a h l s w e d e 等人提出网络编码的主要优点，w uy u n n a 等人【4 1 】说明了网络编码在均匀或者非均匀链路上都可以提高多播容量，并且节点 密度越大，吞吐量表现出来的优势越明显。h ot 等人【4 2 】从理论上证明：在单位容 量的通信网络中，用q 表示信源节点的符合空间，用iyi 表示通信网络中的节点数 目，则采用网络编码的多播吞吐量是传统多播的q l o givi 倍。 2 、网络负载均衡 利用多播树以外的路径，网络编码可以将网络中的信息流更广泛的进行分布， 可以达到均衡网络负载的目的。在图2 8 中，假设每条链路的链路容量为2 ，图2 8 b 重庆邮电大学硕士论文 第二章关键技术研究 是表示传统多播网络，该多播网络一共使用s a ，a t t ，a t 2 ，s c 和c t 3 等5 条链 路，并且每条链路上传输的信息流都为2 。 图2 8 c 表示应用网络编码的多播，假设信源节点s 发送到链路s t 2 的信息进 行模二操作，那么在链路s a ，b t l 和b t 3 上传输的信息为a + b ，在信宿节点t l ， t 2 和t 3 都可以同时收到信息a 和b 。从图2 8 c 可看出，采用网络编码多播使用的 传输链路一共9 条，与图2 8 b 中多播树传输相比多了4 条链路，说明网络编码使 用了更广泛的通信链路，从而均衡网络负载。网络编码在此方面的优点，非常有 助于解决网络拥塞等类似的问题。 a , ba , ba , ba ，a + b如ba + b ，b ( a ) ( b )( c ) 图2 8 均衡网络负载 3 、提升带宽利用率 网络编码的进一步研究表明，它可以提高网络的带宽利用率。从图2 8 b 可看 出，要满足信宿节点t l ，t 2 和t 3 能够同一时间接收到2 个单位的信息，需要5 条 链路，消耗的总带宽为：5 2 = 1 0 ：而图2 8 c 表明，基于网络编码的多播中，需 要9 条链路，消耗总带宽为：9 x l = 9 。由此可见，基于网络编码的带宽消耗节省 了1 0 ，提高了网络带宽利用率。 网络编码的优点不仅仅是以上三点，它还可以减小网络管理的开销、提高网