（计算机应用技术专业论文）基于网络编码的ad+hoc网puma协议研究.pdf

摘要 a dh o e 网络是一种不依赖于固定基础设施的、自组织的无线移动网络。移 动终端具有路由功能，可通过无线连接动态地构成任意的网络拓扑。a dh o c 网 络非常适合于军事、商业、个人通信及自然灾害应急处理等领域。多播在a dh o c 网络中的应用非常广泛，而路由协议是a dh o e 网络的关键组成部分，因此a dh o e 网多播路由是当前网络研究的热点之一。 本文首先研究了基于树的和基于网格的a dh o c 网络多播路由协议各自的特 点，详细分析了基于网格的a dh o e 多播路由协议p u m a 的运作方式、建立和维 护网格的算法、报文转发方式，并分析了p u m a 协议的优点及可待改进的地方， 并指出可使用网络编码来对p u m a 协议进行改进。随机网络编码采用分布式的 算法，不需要节点了解整个网络的全局拓扑信息，所需编码参数从一个足够大 的有限域中随机产生，能适应网络拓扑的动态变化，这些特点使随机网络编码 非常适于a dh o c 网络环境。 基于以上工作，本文作者将随机网络编码算法应用于p u m a 协议，首次提 出了基于网络编码的p u m a 协议n c p u m a ( n e t w o r kc o d i n g p u m a ) ，给出了 n c p u m a 的报文格式，并详细描述了n c p u m a 的协议流程。 然后，作者将n c p u m a 协议添加进国际权威网络仿真平台n s 2 中，并在 n s 2 仿真平台上对协议进行了仿真。仿真的结果表明，相对于原p u m a 协议， n c p u m a 可有效的降低网络带宽的占用，减少节点的能量消耗，提高了路由协 议的性能。本文的创新点如下： ( 1 ) 分析了p u m a 协议，找出其可待改进的缺陷。 ( 2 ) 针对p u m a 协议的缺点，采用随机网络编码算法对其进行改进，首次 提出了基于网络编码的p u m a 协议n c p u m a 。 ( 3 ) 在l i n u x 系统下，采用国际权威的网络仿真软件n s 2 对n c p u m a 进 行了网络仿真。首先对n s 2 仿真软件进行扩展，在其协议族中加入n c p u m a 协议。然后用扩展后的n s 2 仿真平台对n c p u m a 协议进行不同网络环境的仿 真，仿真结果表明，n c p u m a 协议可以有效地节省网络带宽，而且n c p u m a 比p u m a 协议能更好的节省能量。 关键字：a dh o c ，多播路由，仿真，p u m a ，网络编码 a b s t r a c t a dh o cm o b i l en e t w o r k ( m o b i l ea dh o cn e t w o r k ，m a n e t ) i sak i n do fw i r e l e s s m o b i l en e t w o r k s ，w h i c hi si n d e p e n d e n to ff i x e de q u i p m e n t sa n dc a np e r f o r m s e l f - o r g a n i z i n g m o b i l et e r m i n a l sc a nf u n c t i o na sr o u t e r sa n dc a nf o r ma n yd y n a m i c n e t w o r kt o p o l o g i e st h r o u g hw i r e l e s sc o n n e c t i o n s m u l t i c a s ti sw i d e l yu s e di na dh o c n e t w o r k s ，a n dm u l t i c a s tr o u t i n gp r o t o c o li sak e yp a r to fa dh o cn e t w o r k s ，s ot h e m u l t i c a s tr o u t i n gp r o t o c o li st h eh o ts p o to nt h es t u d i e so fa dh o cn e t w o r k s i nt h i st h e s i s ，t h ef e a t u r e so ft h em u l t i c a s tr o u t i n gp r o t o c o lb a s e db o t ho nt r e e a n do nm e s ha r ei n t r o d u c e df i r s t t h e np r o t o c o lp r o c e s s ，t h ea l g o r i t h mo fe s t a b l i s h i n g a n dm a i n t a i n i n gt h em e s ha n dt h ew a yt h em e s s a g ef o r w a r d e do fp u m aa r ea n a l y s e d d e t a i l e d l y a n dp u m a ss h o r t c o m i n gi s s h o w na n dt h em e t h o do fu s i n gn e t w o r k c o d i n gt oi m p r o v ep u m ai sp r o p o s e d t h er a n d o mn e t w o r kc o d i n gu s e sad i s t r i b u t e d a l g o r i t h m ，w h i c hd o e sn o tn e e dt h en o d e st ok n o wt h et o p o l o g yi n f o r m a t i o no ft h e e n t i r en e t w o r k ，a n dt h ep a r a m e t e r sn e e d e dt op e r f o r mc o d i n gc a nb eg e n e r a t e di na g a l o i sf i e l db i ge n o u g h a l lo ft h e s ef e a t u r e sm a k et h er a n d o mn e t w o r kc o d i n gv e r y s u i t a b l ef o ra dh o cn e t w o r k s b a s e do nw o r km e n t i o n e da b o v e ，w ea p p l yt h er a n d o mn e t w o r kc o d i n g a l g o r i t h mo n t op u m a ，a n dp r o p o s et h en c p u m a ，n e t w o r kc o d i n g p u m a ，f o r t h ef i r s tt i m e t h e nt h em e s s a g es t r u c t u r ea n dt h ep r o t o c o lp r o c e s sa r es h o w ni n d e t a i l f i n a l l y ，n c p u m ai sa d d e di n t ot h ea u t h o r i t a t i v en e t w o r ks i m u l a t o rn s 2 a n d s i m u l a t e d t h er e s u l t so ft h es i m u l a t i o ns h o w e st h a t ，c o m p a r e dw i t hp u m a ，t h en e w p r o t o c o ln c p u m ac o s t sl e s sn e t w o r kb a n d w i d t ha n dl e s se n e r g yc o n s u m p t i o n t h e i n n o v a t i o n si nt h i st h e s i sa r e1 i s t e db e l o w ： ( 1 ) p u m a i sa n a l y s e da n dt h ef l a wi ss h o w n ( 2 ) n c - p u m ap r o t o c o li sp r o p o s e df o rt h ef i r s t t i m ew h i c hu s e st h er a n d o m n e t w o r kc o d i n ga lg o r i t h mt oi m p r o v ep u m a ( 3 1i n t e m a t i o n a la u t h o r i t a t i v es i m u l a t o rn s 2i s u s e dt os i m u l a t en c p u m i i u n d e rl i n u xo p e r a t i n gs y s t e me n v i r o n m e n t f i r s tn s 2i se x t e n d e da n dn c p u m ai s i n t e g r a t e di n t on s 2 t h e nn c p u m ai ss i m u l a t e di nd i f f e r e n ts c e n e so fn e t w o r k s a n dt h er e s u l t ss h o wt h a tn c p u m ac o s t sl e s sn e t w o r kb a n d w i d t ha n dl e s se n e r g y c o n s u m p t i o n k e yw o r d s ：a dh o c ，m u l t i c a s tr o u t i n g ，s i m u l a t i o n ，p u m a ，n e t w o r kc o d i n g 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 研究生( 签名) ：4 童：丝 日期：乏! 丝笸：z 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时 授权经武汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：焦遣导师( 签名) ：塑班k 日期艘 武汉理t 大学硕士学位论文 1 1 前言 第1 章绪论 在当今时代，信息技术飞速发展，以i n t e m e t 为代表的网络给人们的生活带 来了巨大的变化。通过国际互联网i n t e r n e t ，人们能够快速了解世界各地的新闻， 方便地获得许多有用信息，还可以参与网上的交易与娱乐活动等。可以说网络 已经成为人们日常生活不可缺少的一部分。 随着微电子，计算机、无线通信技术的进步和现代网络技术日新月异的发 展，相应的人们的需求也越来越趋于便捷化、即时化，3 g 手机、笔记本以及上 网本的普及更把网络的无线化进程推向一个前所未有的高峰。在学术界，对无 线网研究的关注越来越多，学者们纷纷投身于这个领域的研究工作，而其中， a dh o e 无线自组织网络的研究更是目前的热点和焦点。 1 2 网络编码概述 随着信息时代的不断发展，网络与人们工作生活的各个方面结合越来越紧 密。与此同时，用户数量的不断增加，网络服务的同趋多样以及对于网络传输 质量需求水平的不断增加，如何提高现有网络资源的利用率，对网络进行优化， 已成为现今网络通信研究的重要课题之一。 著名的香农最大流最小割定理指出：“网络的最大信息流，是由网络有向图 的最小割决定”，但传统网络的存储转发模式根本不可能达到香农最大流最小割 定理的上界。在现有的计算机通信网络中，信息传输都是从始发源节点经过中间 转发节点，以存储转发的方式最终传送到目标节点。人们普遍认为，中间节点所 进行的数据处理对数据传输过程本身并不会带来任何好处。然而，2 0 0 0 年 r a h l s w e d e 掣l j 提出的网络编码彻底推翻了这一结论。 r a h l s w e d e 等人提出了一类由计算机网络应用而产生的新的理论网 络信息流。他们发现在多播网络中可以通过网络编码的方法节约网络带宽，提 高网络流量。中继节点从输入链路获得信息，对接收到的符合编码条件的多个 武汉理工大学硕十学位论文 信息进行编码得到编码后的信息，然后把经过编码信息发送到输出链路【2 1 从而有 效地节约了网络带宽，增大网络吞吐量。 考虑如图1 1 的网络： t a 图1 1 网络编码示意图 源节点s 要经由节点1 ，和节点u 发送a ，b 两个报文到接收节点x 和y 。在 图1 1a 所示的传统接收转发网络中，报文a 必须经由节点1 4 , 和节点z 才能到达 接收节点y ；节点b 也必须经由节点w 和节点z 才能到达接收节点x 。在这个过 程中，中继节点w 和节点z 均转发报文2 次。现在考虑如图1 1 b 所示情况，中 继节点w 接到报文后并不是立即转发，而是对接收到的报文a 和b 进行编码操 作a o b ，并将a ( 9 b 转发给中继节点z ，中继节点z 再将a o b 转发给接收节点 x 和y ，节点x 可通过解码得到报文b ，而节点y 亦可通过解码得到报文a 。在这 个过程中，中继节点w 和节点z 均只需转发一次即可。对比图1 1 a 和图1 1 b 两种情况，我们可以看到，中继节点w 和节点z 的转发次数从4 次降低到了2 次，效率提高了5 0 l i 等人证明了使用线性网络编码方法可以使多播能够达到网络多播的最大 容量p j ，使网络的利用效率大幅提高。随着网络编码理论的提出，网络编码相关 的研究逐渐成为了学术界的热点。 2 武汉理丁大学硕七学位论文 1 3 研究背景及意义 1 3 1 研究背景 随着网络技术的发展以及人们对移动通信要求的增强，蜂窝移动通信系统 得到了迅速普及。但蜂窝移动通信系统很多时候并不能满足人们的需求。例如， 在战场上部队快速展开和推进、发生自然灾害后的营救。这些场合的通信不能 依赖于预先架设的网络设施，基于健壮性考虑也不能采取有中心的控制方式。 此时，需要一种特殊的通信系统，这种通信系统的运行不能基于任何预先架设 好的网络设施，要能实现临时快速自动组网，节点要能移动【4 1 。a dh o e 网络的出 现满足了这些要求。 a dh o e 网络是对等式网络，网络节点之间无主次之分；进行无线通信时， 网络节点可同时充当主机和路由器的功能，节点之间既可以直接进行通信，也 可以借用中间节点的转发功能间接通信。所以，它又被称为多跳无线网或自组 织网络。 无线传输环境和节点的自由移动为a dh o c 路由协议提出了一系列新的问题 和挑战一j ：首先，无线信道所能提供的吞吐率低、误码率高，这就要求路由协议 的路由开销要尽量小，并且还有具有较强的容错能力。其次，无线节点多数以 电池为电源，因此节点的能量受到严重限制。 多播对a dh o c 网路由协议十分重要，一方面，a dh o c 网络的用户常常需要 组成工作组相互协同工作；另一方面，多播可以充分的利用无线通信信道的广 播特性，是有效利用无线网络信道资源的重要手段。同样的，a dh o c 多播路由 协议也要求协议的开销尽可能的小，用于路由的建立和维护以及多播数据转发 的能量尽可能的低。目前，国内外许多学者投入了很大的精力致力于a dh o c 网 络的多播路由协议，并取得了很多成果，例如基于树形转发结构的a dh o e 多播 路由协议m a o d v 和a m r i s ，基于m e s h 网格转发结构的多播路由协议o d m r p 和n s m p 等。但是目前a dh o c 网络的多播路由协议都隐式或显式的使用了洪泛 技术，这样增加了路由协议的丌销和网络负担，降低了协议的性能。 1 3 2 研究意义 多跳性是a dh o c 网络的主要特征，要实现报文的多跳转发，必须有路由协议 武汉理l = 人学硕f ：学位论文 的支持。而a dh o c 网络使用带宽较窄的无线信道，且由于主机的移动造成拓扑变 化比较频繁，传统的i n t e r n e t 路由协议并不适用于a dh o c 网络必须为它设计专门 的路由协议。 多播是a dh o e 使用较多的一种应用。目前比较成熟的a dh o c 网络多播路由 协议按照路由策略可分为两大类型：基于树( t r e e ) 的协议，比如m a d o v 和基 于网格( m e s h ) 的协议，比如o d m r p 。这两种类型的路由协议均有自己的适用 的情况和场合，但人们普遍认为基于m e s h 的多播协议性能更好( 这两大类多播 协议间性能比较参见【5 】【6 】) 。然而，无论是基于树( t r e e ) 还是基于网格( m e s h ) 的a dh o c 多播路由协议，在建立和维护路由时路由报文的传送以及数据的转发 均采用广播的方式进行，这样不仅严重阻塞网络，浪费了移动自组织网络节点 有限的能量，而且减少了数据发送成功率，降低路由算法的性能。由此可见， 如何引入新的机制，a dh o c 多播路由协议的丌销成为了一个重要的课题。本文 通过将网络编码机制引入a dh o c 多播路由协议之中，研究如何利用网络编码技 术来减少网络中报文的传输次数和节点的能量消耗，降低网络带宽的占用和提 高a dh o c 多播路由协议的性能。 1 4 本文主要工作及论文结构 本文将网络编码理论引入a dh o c 网多播路由协议中，利用随机网络编码算 法对基于m e s h 的a dh o c 多播路由协议p u m a 进行了改进，提出了基于网络编 码的p u m a i 1 ( p r o t o c o lf o ru n i f i e dm u l t i c a s t i n gt h r o u g ha n n o u n c e m e n t s ) 协议 n c - p u m a ( n e t w o rc o d i n g - p u m a ) ，并在国际权威网络仿真软件平台n e t w o r k s i m u l a t o r2 上进行了仿真，并对仿真的结果进行了分析。 本文共分为5 个章节，其中第3 章和第4 章是本人所做的主要研究工作。 第l 章简单介绍了网络编码概念和a dh o c 路由协议的知识，对a dh o c 路由 协议的种类做了简单的阐述，介绍了a dh o c 路由协议的特点及其工作原理，阐 述了研究的背景及意义。 第2 章主要是背景知识。介绍了网络编码理论相关知识，对其理论基础、基 本原理、通过使用网络编码可得到的收益和常见网络编码算法进行了介绍。之 后介绍了a dh o c 网络相关知识，阐明了a dh o c 网络多播路由协议研究的重要性， 对现有的a dh o c 网络多播路由协议进行了分类对比并介绍了各自的特点。在2 7 4 武汉理r 大学硕十学位论文 节对基于网格( m e s h ) 的a dh o e 路由协议p u m a 进行了详细的介绍。讨论了 p u m a 协议的路由机制及工作流程。并对本文所用仿真工具n s 2 ( n e t w o r k s i m u l a t o r2 ) 及研究所用到的相关工具进行了介绍。 第3 章首先对p u m a 协议进行了分析，指出该协议的优缺点，并指出可通过 网络编码对其进行改善。之后作者对当前主要的网络编码算法进行了比较，根 据随机网络编码算法的特点编码节点不需要了解整个网络拓扑和其他编码 节点的编码操作，非常适用于拓扑结构动态变化的无线网络选择随机网络 编码算法对p u m a 协议进行改进，提出了基于网络编码的p u m a 协议 n c p u m a 协议，并给出了n c p u m a 协议的具体流程步骤。 第4 章本文作者使用在学术界具有公信力的权威网络仿真软件n s 2 对 n c p u m a 协议进行了网络仿真。首先对n s 2 仿真平台进行扩展，将n c p u m a 加入其协议族中。然后用扩展后的n s 2 仿真平台对n c p u m a 协议进行了不同 场景的仿真。并将使用了网络编码的n c p u m a 与原p u m a 协议进行了对比， 画出了对比图，分析其性能。 第5 章对整个论文的工作作出了总结，并且对后续的工作进行了简要的描 述。 武汉理丁大学硕士学位论文 第2 章背景知识 在这一章中首先介绍了与网络编码有关的图论中基本知识，接着介绍了网 络编码的概念，并分析了网络编码带来的益处。然后介绍了当前常见的网络编 码算法。 2 1 前言 传统的通信网络传送数据的方式是存储转发，即除了数据的发送节点和接收 节点以外的节点只负责路由，而不对数据内容做任何处理，中间节点扮演着转 发器的角色。长期以来，人们普遍认为在中间节点上对传输的数据进行处理不 会有任何收益，然而网络编码理论的提出彻底推翻了这种传统观点。 在2 0 0 0 年，香港中文大学的r a h l s w e d e 等人提出了网络编码理论，并提出 可通过网络编码显著地节约网络带宽，提高网络流量。网络编码是一种编码算 法，有研究者称通过网络编码可以将现有的网络吞吐量提高一倍，同时还能改 善网络的可靠性和防范攻击的能力，网络编码技术将会引发网络的下一代革命。 本章对网络编码理论的背景知识及原理进行了详细的介绍。 2 2 网络编码的概念 2 2 1 网络编码的基本概念 一个通信网络( n e 似o k r ) 包含许多通信链路【引，这些链路连接着发送端、交换 器和接收端。如果把发送端、交换器和接收端看成是图论中的节点，我们就可 以将通信网络用有向图g = ( 矿，e ) 表示，其中矿是节点的集合，e 是有向边的 集合。另外，每条链路均有一个对应的链路容量。 传统的网络节点只是将收到的数据进行路由和转发。网络编码理论的出现 改变了人们对于网络的这种认识，其核心思想是在中继节点可采用编码算法对 待转发报文进行编码之后在转发，而不仅仅是转发。该理论打破了人们所习惯 的数据传输的传统模式，为进一步提高网络传输速率奠定了基础。在文献中， 6 武汉理t 大学硕士学位论文 作者给出了一个采用网络编码的多播网络的例子，在该例子中网络传输速率达 到了最大流最小割定理的理论上限。李硕彦【3 j 等人随后证明采用线性的网络编码 可使网络传输速率达到理论上限。本文第一章第二节就给出了一个简单的应用 了网络编码的网络。 这种网络中的节点对待转发信息进行一定的编码操作，而不是简单地进行 复制转发的方法就称为网络编码。 2 2 2 网络编码的收益 网络编码理论在提出时就有明确的针对目标可以大大提高多播网络中 的的多播容量，使其达到最大流最小割理论的多播容量理论上限。但是随着网 络编码理论研究的不断深入，人们发现，网络编码带给网络的好处并不仅仅局 限于提高网络多播容量，除了提高网络中的多播容量之外，还有如下文【l o 】所述 的其他的好处。 在当前的无线网络中，无线节点一般都使用电池来进行节点所需电能的供 应。但是受到当前科技水平和工艺水平的制约，电池的电量不可能无限大，都 会出现电量耗尽的情况。在一个无线a dh o c 网络中，节点的电池能量限制，即 节点工作的时间是无线a dh o c 网络的一个重要的指标。如何合理高效的利用节 点的电能，如何尽可能的延长节点电池的续航时间是一个很实际、很重要的课 题。网络编码理论通过对待转发的信息进行编码，可实现只需要一次转发就可 以将多个信息转发出去，从而有效地减少a dh o c 网络中各个报文的传输次数。 而通过对于无线a dh o c 网络中节点能量消耗的研究我们可以发现，节点绝大部 分的能量消耗都是用于无线通信模块。无线节点传输信息时要比执行计算时更 消耗电能，传输l 比特信息1 0 0 米距离需要的能量大约相当于执行3 0 0 0 条计算指 令消耗的能量【l 引。因此，通过将网络编码理论应用于无线a dh o c 网络，可以有 效地降低网络中节点的能量消耗，延长节点电池的续航时间，增加节点的使用 寿命。 在现有的多播通讯网络中，多播路由协议采用的多是基于信源的和基于核 心的路由算法。基于信源的路由协议经常会由于在处理多个多播组时，由于对 不同的多播组建立多个多播树，从而造成在某一条链路上产生多个多播树的叠 加，继而使某一条链路的流量严重过载，极大的影响了网络的服务质量和效率。 基于核心的多播路由算法也经常会造成网络流量过分的集中于某一个节点，使 7 武汉理工大学硕十学位论文 网络的负载极度不均衡。而网络编码理论通过使用多条链路来进行数据的转发 传输，将网络中的信息均衡的分配到各条链路中，从而可使网络的链路负载处 于较均衡的状态，有效地避免了传统多播路由算法的缺陷。 随着网络的发展，网络的应用范围越来越广。然而，随着网络的大面积使 用，用户的数量的急剧增加，虽然网络带宽相比以前已经有了巨大的提升，但 是依然显得无法满足人们的需要。因此，如何高效的利用现有的网络带宽资源， 而不是一味的通过技术手段提高网络的带宽，成为了网络研究的焦点。由于无 线信道相比有线信道带宽较小且易受干扰， a dh o c 网络的这个问题更加重要。 网络编码理论的由于它先天的优势，对于提高网络带宽的利用率有着巨大的作 用。通过使用合适的编码算法，节点将接收到的信息编码后一次性的发送出去， 将多次发送变为一次发送从而有效地减少了网络中报文的转发次数，降低了无 线信道的占用，大大的节约了网络的带宽资源。 总的来说通过使用网络编码可带来如下几方面的收益i l ： ( 一) 多播网络容量的改善 r a h l s w e d e 等人提出网络编码理论的时候，就是以如何提高网络中多播通 信的容量为目标进行研究的，并通过网络编码理论阐述了通过网络编码的方式， 网络的多播容量能够达到最大流最小割理论所界定的上界。可见，网络编码理 论对于多播网络的容量的改善有着其他方法所无可比拟的优势【l 。 在本文第一章第二节给出了一个典型的例子来描述网络编码对于多播网络 的改善。这种性能的提高，传统的采用存储转发方式进行信息传播的多播网络 是无法实现的，只有通过网络编码方法才能获得。当然，a dh o c 网络的网络情 况干差万别，仅仅这些并不足以说明网络编码对于网络容量的提高及相对于传 统网络转发方式的优势。因为网络编码的对于容量的提高是同网络节点的连接 情况以及网络中每一条链路容量的变化情况紧密相关的。所以在评价网络编码 对于多播容量的改善时，必须要考虑到各种网络拓扑结构以及各种链路的容量。 8 武汉理t 大学硕士学位论文 4 0 3 5 3 0 2 5 嘲 鎏2 0 瓣 1 5 l o 5 0 2 345678 平均节点度 图2 2 多播容量性能比较【l l 】 文献 i 3 1 对网络编码的多播和传统的多播方式的多播容量以及性能进行了研 究对比。在网络节点个数为5 0 的随机生成的网络拓扑中，任意选择1 0 个节点作 为多播数据的接收节点。采用2 种网络链路容量模型做对比：一是在区间 1 ，1 0 内随机选取链路容量的非均匀模型( h e t e r o g e n e o u sm o d e l ) ，第二种是网络的 链路容量为固定值5 的均匀的网络链路容量模型( h o m o g e n e o u sm o d e l ) 。并将网 络编码的多播和多会话i p 多播( m u l t i - s e s s i o ni pm u l t i c a s t ) 的容量进行了 比较。图2 2 i 1 1 即为所得出的多播容量和节点度数之间关系的仿真结果。通过图 2 2 我们可以看出，在这两种链路容量模型之下，基于网络编码的多播比多会话 i p 多播的网络多播容量更高。并且，二者之间的差异随着网络节点的平均度数 的增加而增加。 ( 二) 链路负载的均衡 在现有的多播通讯网络中，多播路由协议采用的多是基于核心的和基于信 源的路由算法。基于核心的多播路由算法经常会造成网络流量过分的集中于某 一个节点，使网络的负载极度不均衡。基于信源的路由协议经常会由于在处理 多个多播组时，由于对不同的多播组建立多个多播树，从而造成在某一条链路 上产生多个多播树的叠加，继而使某一条链路的流量严重过载，极大的影响了 9 武汉理工大学硕士学位论文 网络的服务质量和传输效率。而网络编码理论通过使用多条链路来进行数据的 转发传输，将网络中的信息均衡的分配到各条链路中，从而可使网络的链路负 载处于较均衡的状态，有效地避免了传统多播路由算法的缺吲1 1 1 。 ( b ) 图2 3 传统路由与网络编码网络负载对比示意图 将多播网络抽象为图2 3 所示网络，网络中各条链路的容量均为2 。源节点 s 发送多播报文a 、b 到多播接收节点4 、5 、6 。当采用传统路由方式时，最佳 情况如图2 3 ( a ) 所示，中继节点l 将数据转发给4 和5 ，节点3 将数据转发给 6 ，节点2 不参与转发。可以看到这种方式下参与传输的链路有5 条，而网络中 的另外5 条链路处于闲置状态，并且参与传输的链路都传输了2 个报文。现在 考虑如图2 3 ( b ) 所示的网络编码的多播传输方式。从图中我们可以看出，所 有链路都参与了传输，且每条链路都只传输一个报文大小的数据即可实现将报 文a 、b 多播到接收节点4 、5 、6 。相比传统的存储转发多播方式，网络编码将 负载平均的分配到了所有链路上，实现了网络链路负载的均衡。 ( 三) 网络带宽消耗的降低 随着网络的发展，网络的应用越来越广泛，网络已经深入到了人们每天的 生活工作活动之中。然而，随着网络的大面积使用，用户数量的急剧增加，各 种p 2 p 应用的大面积流行，网络中的带宽资源虽然随着技术的进步相比以前已经 有了巨大的提升，但是依然无法满足人们日渐增长的需要。因此，在当前技术 l o p 卜厂q 武汉理丁大学硕士学位论文 条件的限制下。如何高效的利用现有的网络带宽资源，成为了学术界研究的热 点问题之一。网络编码理论的由于它先天的优势，对于提高网络带宽的利用率 有着别的方法难以企及的便利。 仍然考虑如图2 3 所示的网络。在使用传统存储转发方式的多播环境中( 图 2 3 ( a ) ) ，源节点多播报文a 、b 到接收节点4 、5 、6 。参加传输的链路有5 条， 并且由于传统多播路由方式只是对报文进行转发而不进行编码，所以，每条链 路均需传送2 次报文，总的传输次数为5 x 2 = 1 0 次。现在考虑突入2 3 ( b ) 所示的 网络编码的多播。由于采用了网络编码，网络中的转发节点对待转发的报文进 行编码之后再转发，因此，每条链路上都只需要传输一个报文，参与传输的链 路数目为9 ，从而网络中总的传输次数为9 x 1 ：9 。我们可以看到，相比传统的多 播方式的1 0 次，采用了网络编码的网络中总的带宽消耗降低了1 0 。 ( 四) 节点能量消耗的减少 在当自仃的无线网络中，节点一般都使用电池来供电。a dh o c 网络中，节点 的电池可以使用的时间关系至0 节点的工作时长，是a dh o c 网络的一个重要的指 标。因此如何合理高效的利用无线移动节点的电能，如何尽可能的延长节点电 池的续航时间是一个很实际、很重要的课题【1 4 1 。 图2 4 i h 给出了传统的多播方式和网络编码的多播方式下，网络中节点能量 消耗的对比。假设节点每传送一个报文所消耗的能量为1 焦耳。在途2 4 ( a ) 所 示的传统存储转发多播方式中，节点s 发送报文a n 多播接收节点r 1 和r 2 共需5 次 传输，同理，发送报文b 到接收节点r 1 、r 2 也需要5 次，总的传输次数是1 0 次， 能量消耗为1 0 焦耳。现在考虑图2 4 ( b ) 所示的网络编码多播方式。源节点s 将 报文a 发送给接收节点r 1 ，将报文b 发送给接收节点r 2 。r 1 和r 2 将报文a 、b 发送 给中间节点m ，中间节点m 对报文进行编码处理aob ，之后再将编码后的报文转 武汉理工大学硕士学位论文 ( a ) 传统多播方式( b ) 网络编码多播方式 图2 4a dh o c 网络能量消耗比较示意图【i l 】 发给r 1 和r 2 。r 1 和r 2 通过解码的得到所需报文b s n a 。这个过程中，总的传输次 数为9 次，能量消耗为9 焦耳。并且而通过对于无线网络中节点能量消耗的研究 发现，节点绝大部分的能量消耗都是用于无线通信模块。无线节点传输信息时 要比执行计算时更消耗电能，传输1 比特信息1 0 0 米距离需要的能量大约相当于 执行3 0 0 0 条计算指令消耗的能量【l2 1 。因此我们可以看出，通过将网络编码理论 应用于无线a dh o c 网络，可以有效地降低无线a dh o c 网络中节点的能量消耗， 延长移动节点电池的使用时间，延长网络的寿命。 2 2 3 常见网络编码方法简介 网络编码理论虽然刚刚兴起，但是由于它对于传统网络模式的颠覆以及对 于提高网络性能的光明前景，网络编码已经成为了学术界的研究重点，学者们 已经提出了很多有效的网络编码方法【1 5 2 刚，并且网络编码的适用范围也从有线 网发展到了动态的无线网络1 2 m 4 。 当前常见的网络编码方法主要是线性网络编码和随机网络编码。在2 0 0 0 年 r a h l s w e d e 等刚提出网络编码理论的时候，他们所使用的主要是线性网络编码( l i n e a rn e t w o r kc o d i n g ) 。这种编码方式在转发信息时，中继节点使用线性运算对 待转发进行编码操作，在解码时也是使用线性方式。他们证明了采用线性网络 编码可以使多播达到网络的最大容量。但这种编码方式需要节点对网络的拓扑 有全面的了解，并且需要节点了解网络中每个节点的编码操作，只有这样才能 保证选择的编码向量线性无关，接收节点才能够解码。可见线性网络编码方式 并不适用于拓扑结构经常改变的网络。随着网络编码研究的逐渐深入，h o ， m e d a r d 等人提出了随机网络编码【l5 1 ，这种编码方式在选择编码向量时采用随机 产生的策略：对于除了信宿节点外的所有中间节点，只要在一个足够大的有限 域f 。上随机选择它们输入链路到输出链路的映射，而且各节点映射关系的选取是 相互独立的，就能以较高概率使各个信宿节点对应的系统转移矩阵m 。满秩，即 各信宿节点能以较高的概率成功进行解码。这种方式避免了编码节点对于整个 网络拓扑和其他编码节点的编码操作的了解，将网络编码的适用范围拓展到了 a dh o c 网络。 1 2 武汉理t 大学硕十学位论文 2 3a dh o c 网络概述 a dh o c 网络是一种特殊的无线移动通信网络。在a dh o c 网络中，所有节点 的地位是平等的，网络中没有也不需要设置中心控制节点，因此网络的健壮性 很强，不会因为中心节点的破坏而使网络瘫痪【9 j 。a d h o e 网络中的每个节点同时 在网络中扮演2 种角色：普通的移动终端，以及网络中的路由器。当通信的源 节点和目的节点处在彼此的电波范围之外，无法直接通信的时候，他们可以通 过中间节点进行通信。有时节点间的通信可能要经过多个中间节点才能完成， 这是a dh o e 网络相比其他移动通信网络的特点。 ( 一) a dh o e 网络的定义 a dh o e 网络是由移动节点组成的多跳的临时性自治系统。网络中的移动节 点同时具有路由和报文转发功能，可以通过无线信道连接组成任意的拓扑结构。 a dh o c 网络既可以作为单独的网络进行工作，也可接入i n t e m e t 网从而与世界各 地进行互联。由于a dh o c 网络使用无线信道以及功率的限制，虽然a dh o e 可提 供路由功能，但在接入互联网时，a dh o e 网络通常是以末端子网的形式接入网 络，而不适于作为中介媒体。并且它只允许产生于或目的地是网络内部节点的 信息进出，而不让其他信息穿越本网络，从而大大减少了与i n t e m e t 网络互操作 的路由丌销【2 5 1 。 a dh o c 网络中，每个移动节点同时具备路由器和主机两种功能，既有完备 的本地处理及服务功能，又可以对网络中的其它节点提供路由服务。由于a dh o e 网络自身的特性，节点间的路由通常由多跳组成。由于移动节点的无线传输范 围有限，因此无法直接通信的移动节点只能通过多个中间节点的转发来实现通 信。所以，a dh o c 网络又被称为多跳无线网、无线自组织网络。a dh o c 网络同 时具备移动通信网络和计算机网络的特点，可以看做是一种特殊的移动计算机 网络。 ( 二) a dh o c 网络的特点 a dh o e 网络具有以下特点【2 5 】： ( 1 ) 单独组网：a dh o c 网络具有独立的组网能力，节点开机后就可以快速、 自动地组成一个独立的网络。 ( 2 ) 没有中心节点：a dh o c 网络没有中心节点，所有节点的地位平等，网 络中任一节点的失效不会导致整个网络瘫痪，因此，相比具有有中心的网络结 武汉理工大学硕+ 学位论文 构，a dh o c 具有很强健壮性。 ( 3 ) 可自组织：在a dh o c 网络中并不存在网络的中心节点，所有节点既可 以独立完成自己的应用需求，也可与网络中的其他节点协同工作。 ( 4 ) 多跳性：由于移动节点的电波发射功率限制，节点发射的电波的可达 距离是有限的。当要与其覆盖范围以外的节点进行通信时，必须经由中间节点 完成，也就是所谓的多跳性。 ( 5 ) 拓扑动态变化：a dh o c 网络中，移动终端能够以任意移动，且受各种 因素影响，因此网络拓扑随时可能发生变。因此需要专门开发专门的路由协议， 以适应这种动态拓扑网络的需要。 ( 6 ) 节点能量有限：移动终端具有携带方便、轻便灵巧等优点，但节点依 靠电池提供有限的电能，电池用尽节点也就不能工作。因此，如何高效的使用 节点的电能延长节点的工作时间是一个非常重要的问题。 ( 7 ) 安全性差：a dh o c 网络由于采用无线信道、分布式控制等技术，它更 加容易受到被动窃听、主动入侵、剥夺“睡眠” 2 6 】等网络攻击。另外，由于a d h o c 网络节点的双重角色，及不存在网络边界的概念，使得a dh o c 网络安全问 题非常复杂。 2 4a dh o c 网络路由协议 a dh o c 网络是由一组具有路由功能的节点组成的分布式无线多跳网络，它 不依靠任何预设的网络基础设施【2 7 1 。因为a dh o c 网络中节点发射电波的覆盖范 围有限，源节点在向目的节点发送数据时，常常需要经由中间节点到达目的节 点，因此路由协议是a dh o c 网络中的难点，也是不可缺少的重要组成部分2 8 3 。 然而传统的路由协议并不适应a dh o c 网。因此路由协议一直是a dh o c 网络研究 的热点问题。 一个优秀的a dh o c 网络路由协议应该具有以下特点【3 2 】： ( 1 ) 采用分布式路由算法。 ( 2 ) 自适应能力强，可适应网络拓扑的快速变化。 ( 3 ) 无环路。 ( 4 ) 协议开销较少。 ( 5 ) 可扩展，以适应规模较大的网络。 1 4 武汉理工大学硕十学位论文 a dh o c 网络没有特定的中心节点，所以分布式算法更适合于a dh o c 网。【2 6 】a d h o c 网中，节点可以任意移动，加上无线发射功率的变化、无线信道间的干扰以 及地形天气等综合因素的影响，移动节点间通过无线信道组成的网络拓扑结构 随时可能发生变化，所以路由协议必须具有自适应能力，可适应快速变化的网 络拓扑结构。无环路是保证路由协议正确性的一个基本要求。环路将导致路由 错误，造成大量的带宽资源浪费，严重影响整个网络的性能。由于a dh o c 网通 过无线信道进行连接，因此a dh o c 网所能提供的带宽资源相比有线网络来说要 低得多。因此必须控制路由协议的开销，提高网络的整体性能。现在a dh o c 网 络的应用范围越来越广，所应用到的网络的规模也越来越大。而且可以预料， 随着人们对于无线应用的要求越来越高，a dh o c 网的规模还将进一步加大，因 此如何很好的适应庞大的网络规模，如何使网络具有扩展性是a dh o c 路由协议 必须要面对的问题。 洪泛( f l o o d i n g ) 1 2 6 j 技术在a dh o c 网络路由协议中具有广泛应用。在许多 路由协议中采用了洪泛技术。甚至，在网络动态变化十分剧烈的情况下，路由 只能通过洪泛实现。该技术不需要已知任何网络拓扑信息，即可进行报文的传 递。但不加限制的广播会导致分组在全网范围内重传。洪泛使分组像辐射波一 样从源节点以波浪形式向外传播，最终到达目的节点( 如果目的节点是可达的) 。 采用洪泛方式传递分组，具有很大盲目性，消耗大量带宽。因此如何对洪泛进 行改进降低对于带宽的占用是现在的研究热点和难点。 2 5a dh o c 网络多播路由协议 多播( m u l t i c a s t ) ，又称为组播【26 。，是一种一点到多点或多点到多