基于网络编码的应用层组波路由优化方案研究毕业论文.docx
《基于网络编码的应用层组波路由优化方案研究毕业论文.docx》由会员分享，可在线阅读，更多相关《基于网络编码的应用层组波路由优化方案研究毕业论文.docx（48页珍藏版）》请在冰点文库上搜索。
基于网络编码的应用层组波路由优化方案研究毕业论文
摘要
随着通信网络技术的发展和多媒体技术的广泛运用，网络资源紧张和分配不合理的问题越来越突出。
在P组播无法被全网范围内部署利用的情况下，基于端系统的应用层组播应运而生。
与传统路由节点只能对数据进行复制和转发不同，应用层组播中的端系统可以对接收到的数据进行运算操作（如线性运算）。
利用网络编码，端系统对收到的数据进行组合编码，从而有效地利用网络带宽，增加网络容量。
关键词：
应用层组播、网络编码、分布式算法、最大效用、凸优化
Abstract
Withthedevelopmentofcommunicationnetworkandmultimediatechnology,therequirementofsupportinglargescaledatadistributionsuchasvideostreaminghascomeintobeingandsoongathersagreatresearchinterest．Whilecurrentlythelimitationofnetworkresourcesaswellastheinefficientnetworkresourceutilizationrendersagreatchallengetowardsitsfurtherdevelopment．WiththeconsiderationoffailingtoimplementIPmulticastwithinawiderangeofnetwork,theendsystembasedapplicationlayermulticast（ALM）hasbeenproposed．Besidesequippedwitha11thefunctionoftraditionalroutingnodesuchasdataforwarding,dataduplicating，themightyendsysteminALMCanalsocarryoutsomeoperation（e．g．1inearcombination）uponthetrafficreceived．Specifically,weemploynetworkcoding，abrandnewmulticasttechnologyinsomeendsystemswiththepurposeofbetterutilizingbandwidthresourcesandimprovingnetworkthroughput．
Keywords：
ApplicationlevelMulticast，NetworkCoding,Distributed
Algorithms，Maxutility,Convexoptimize
毕业论文（设计）原创性声明
本人所呈交的毕业论文（设计）是我在导师的指导下进行的研究工作及取得的研究成果。
据我所知，除文中已经注明引用的内容外，本论文（设计）不包含其他个人已经发表或撰写过的研究成果。
对本论文（设计）的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。
作者签名：
日期：
毕业论文（设计）授权使用说明
本论文（设计）作者完全了解**学院有关保留、使用毕业论文（设计）的规定，学校有权保留论文（设计）并向相关部门送交论文（设计）的电子版和纸质版。
有权将论文（设计）用于非赢利目的的少量复制并允许论文（设计）进入学校图书馆被查阅。
学校可以公布论文（设计）的全部或部分内容。
保密的论文（设计）在解密后适用本规定。
作者签名：
指导教师签名：
日期：
日期：
注意事项
1.设计（论文）的内容包括：
1）封面（按教务处制定的标准封面格式制作）
2）原创性声明
3）中文摘要（300字左右）、关键词
4）外文摘要、关键词
5）目次页（附件不统一编入）
6）论文主体部分：
引言（或绪论）、正文、结论
7）参考文献
8）致谢
9）附录（对论文支持必要时）
2.论文字数要求：
理工类设计（论文）正文字数不少于1万字（不包括图纸、程序清单等），文科类论文正文字数不少于1.2万字。
3.附件包括：
任务书、开题报告、外文译文、译文原文（复印件）。
4.文字、图表要求：
1）文字通顺，语言流畅，书写字迹工整，打印字体及大小符合要求，无错别字，不准请他人代写
2）工程设计类题目的图纸，要求部分用尺规绘制，部分用计算机绘制，所有图纸应符合国家技术标准规范。
图表整洁，布局合理，文字注释必须使用工程字书写，不准用徒手画
3）毕业论文须用A4单面打印，论文50页以上的双面打印
4）图表应绘制于无格子的页面上
5）软件工程类课题应有程序清单，并提供电子文档
5.装订顺序
1）设计（论文）
2）附件：
按照任务书、开题报告、外文译文、译文原文（复印件）次序装订
3）其它
第一章绪论
第一节课题来源
本课题来源于国家高技术研究发展计划（863计划）（2006AA012322）：
视频媒体基于信息可重用的分布式网络化编码及传输。
第二节课题研究的目的和意义
随着宽带多媒体网络的不断发展，各种宽带网络应用层出不穷，例如：
数字电视、视频会议、数据和资料分发、网络音频应用、网络视频应用、多媒体远程教育等。
这些宽带多媒体应用都对现有宽带多媒体网络的承载能力提出了挑战。
采用单播技术构建的传统网络已经无法满足新兴宽带网络应用在带宽和网络服务质量方面的要求，随之而来的是网络延时增加、数据丢失等等问题。
于是，组播通信方式被提出，旨在改善现有网络中存在的一些网络资源紧张问题，提高网络的服务质量QoS[11。
组播是现在网络研究中的一个重要课题。
组播通信的基本出发点是：
在同时存在多个接收者时，通过合并重复信息的传输来达到减少带宽浪费和降低服务器处理负担的目的。
其发展之一的IP组播模型是对Internct基本的“单播、尽力发送’’模型的一个重要扩充，它把组播的主要功能都放在路由器上实现。
而由于口组播在传输技术和管理上存在严重的问题，主要是口组播需要路由器维护组播通信的状态信息，增加了网络的复杂性并严重约束网络组播的扩展，其次网络的可靠性、拥塞控制、流量控制、安全性无法得到保障，另外由于P地址空间有限，无法满足众多应用的需求，因此目前IP组播没有在Internet中得到普遍采用[21。
研究人员反思口层组播体系存在的问题后，在2000年提出了应用层组播。
它的主要思想是：
保持Intemet原有的模型，尽量不改变原来网络的体系结构，而主要通过增加端系统的功能来实现组播的功能。
由于对网络本身的改变很少，应用层组播具有很好的灵活性。
随着Peel'-m．PeerNetwork和OverlayNetwork等技术的提出和发展对应用层组播的研究也有很大的促进作用。
但是，上海大学硕士学位论文端系统的稳定性一般不如专用网络设备，并且应用层组播在带宽利用效率及网络延迟方面也无法和P组播相比。
另外，应用层组播中的系统框架和很多细节技术也还在研究当中。
这些问题的存在为应用层组播的研究提供了广阔的空间。
网络编码的思想在2000年由R．Ahlswede首次提出，我们发现网络编码可以大大提高网络的传输能力和传输可靠，其理论创新具有普遍意义，应用前景十分广阔。
考虑到应用层组播是基于应用层端系统之上的，端系统比传统的IP路由器功能更为强大，可以在端系统上引入网络编码，将接受到的信息进行解码和编码可以提高网络传输的效率。
第三节论文的主要研究内容
本论文是作者攻读硕士学位期间承担课题的工作总结。
第一章中阐述了课题来源、研究目的和意义以及国内外本课题研究的现状。
第二章阐述了课题研究的基本理论——网络编码的概念和基本原理，包括如何进行编码和解码，以及网络编码的优点和使用范围。
第三章在对比其它传统组播路由算法的基础上，结合网络编码提出了新的基于网络编码的分布式应用层组播路由算法。
第四章中，考虑到第三章中提出启发式算法本身作为NP．complete问题不能得到网络最优解的局限性，从凸优化角度分布式考虑如何使得整个网络的效用最大及网络传输开销最小，利用拉格朗日对偶和次梯度算法来求解，使得网络源节点效用最大和链路中流量分配合理。
最后第五章总结了全文以及硕士期间的研究工作，并以后工作提出了设想。
第二章网络编码
第一节网络编码原理
在现有的通信网络中，信息传输都是由源节点经过中间节点，以存储转发的方式传送到目的节点的。
除了数据复制以外，一般来说在网络的中间节点并不需要做任何数据处理。
在许多实际应用中，人们为了信息分析、信息安全以及交换的目的，总是要在中间节点进行某种形式的数据处理。
但是人们普遍认为，中间节点所进行的数据处理对数据传输过程本身并不会带来任何好处。
2000年，R．Ahlswcde首次提出了对信息进行网络编码的思想。
所谓网络编码，就是指节点对输入的多路信息流进行代数组合运算，生成一路或多路新的输出信息流。
在传统的网络中，大量存在的中间节点只能对接收到的数据进行路由、复制和转发，这对于有限的网络资源是严重浪费。
由于网络中被传递的信息本质上就是连续的比特流，是一系列抽象的代数符号，因此信息除了可以被转发和复制之外，应该还可以进行代数运算，网络编码技术打破了中间节点不对数据处理的限制。
它允许中间节点对接收到的信息进行编码，并将接收到的多个数据包按照某种特定算法重新组合再发送出去。
网络编码是在有限域中进行的，主要分为线性和非线性两种方式。
但相比非线性编码，线性网络编码的编码和解码都相对简单，这里以目前被普遍采用
的随机线性网络编码为例，来说明网络编码的原理。
假定流入节点的每个数据包的包长度均为￡比特（较短的数据包位数不够，在末尾添零补齐），如果把这工比特中每连续的s比特映射为有限域聪中的一个元素，那么就可以把这个数据包看成一个包含∥个元素的向量。
于是，从代数学的角度来看，数据包之间的编码运算就等同于一系列向量的线性组合，而线性组合所用到的加法和乘法遵循有限域的运算法则。
这里需要指出的是，选择有限域是缘于它的两条性质，其一是有限域中的元素个数是有限的，其二是有限域中的元素对于该有限域所定义的两种运算（an法和乘法）是封闭的。
这不仅极大增强了线性组合的灵活性，同时保证了运算所得的结果不会占据额外的存储空间，即新组合的包的长度和原始数据包长度一致。
一、编码过程
假设一个或多个原始信源所发送的信息由疗个数据包M1，．．．，M^组成，中间节点可以对流入其中的n个数据包进行网络编码，生成1个新的数据包x=Σ：
。
g，M’。
其中毋就是有限域巧中的元素，它由节点随机产生。
由于编码运算在有限域中进行，因而x所占据的存储空间大小与膨7所占大小完全相同。
组合运算的系数g=（gl，．．．，gn）称为编码向量，石称为信息向量。
编码完成后，节点将编码向量和信息向量（g'x）同时转发出去，用于目的节点对信息向
量进行解码，恢复原始信源。
网络编码可以对编码的数据包重复进行编码，换言之，节点可以对收到的已编码的信息向量进行再次编码。
假定节点收到了m个信息向量
它对聊个信息向量再次编码，生成新的信息向量
。
这里
代表与
相对应的编码向量，二者满足
二、解码过程
在线性编码下，运用乘法和加法运算，使得从节点发送出来的数据为一系列线性组合，便于解码。
当一个节点收到ra个编码后的数据包
后，为了恢复出万个原始数据包
，只需求解以下
方程组：
这是一个含有刀个未知数，m个方程的线性方程组。
我们知道，只有当线性方程组的方程个数大于或等于未知数个数（即m≥n）时线性方程组才有唯一解。
当然m≥刀并不是充分条件，因为方程之间有可能出现线性相关的现象，即编码向量之间线性相关。
虽然编码向量之间的线性相关程度取决于所选取的有限域的大小，但实验证明即使选择比较小的有限域，比如S=8的有限域，编码向量之间出现线性相关的概率也是非常小的。
因此，节点的解码过程是非常简单的，节点不需要接收指定内容的数据包，只要接收到足够数量的线性无关的编码数据包，就可以成功恢复原始数据。
第二节网络编码的优点
一、最大流最小割原理
在分析网络编码技术及其应用之前，首先来介绍图论的相关背景知识。
对于包含一个源节点s和￡个汇节点，V代表顶点（Vcrticc）集合，E代表有向边（Edge）集合，用嘞表示边（f，j）∈E的容量,，F表示流经边（的流量，显然对所有，。
而且，对有向图G上任意节点即流入中间节点f的数据总量等于流出节点f的数据总量。
根据最大流最小割定理：
任何带发送节点和接收节点的网络中都存在最大流和最小割，并且最大流的流值等于最小割的容量。
如果用max表示从源点s到汇点f，的最大流值。
二、网络编码的优势
在传统的组播通信中，网络中的节点只能存储转发所收的数据包，当信源s到不同信宿厶之间的最大流经过的路径可能在G的某些链路上形成交叉共享链路，进而影响共享链路之间节点的数据传输率，因此采用传统的存储转发模式一般是不可能达到最大流最小割定理规定的组播信息容量上限的。
2003年，R．Li证明了在单个源节点向多个目的节点发送数据的情况下，应用线性网络编码理论，一定能够达到网络组播容量的上限。
除了能使得网络传输达到组播容量的上限，网络编码的应用还可以为系统带来以下几方面的益处：
1．提高组播速率，实现组播最大容量。
图2．1（a）给出了网络拓扑结构及不同链路的容量，其中S是信源，墨、恐和恐是三个不同的信宿。
显然，从S到RO=l，2，3）的最大流均为4，所以将信息从S同时发送给羁、岛和马时的最大组播容量也是4。
然而从图2．1（b）可以看出，存储转发模式下的单组播最大速率仅为2，图2．1（c）显示在部分节点上进行网
络编码能够提高组播速率至4，实现组播最大容量。
（a）网络拓补和链接容量（b）传统传输方式（c）网络编码实现最大流（d）负载平衡
图2.1存储转发方式与网络编码方式的比较
三、节约系统带宽，并有利于负载平衡。
采用图2的存储转发方式，同时传输2bR信息占有的链路带宽总量为10；而采用图21（d）的网络编码方式，同时传输2bit信息所占有的链路带宽总量为9。
相比之下，后者可以节约10％的系统带宽。
而且，前者集中使用了系统中的5条链路，闲置了另外4条链路，导致节点上的带宽资源占用情况非常不平衡；而后者均衡地利用了系统中的全部9条链路，很好地平衡了网络负载。
四、提高系统的鲁棒性和白适应性。
如图2．2所示，图中每个节点都存储了一组固定长度的数据。
图2．2（a）中的每个节点均以原始格式对数据进行存储，图2．2∞中的每个节点均以网络编码后的格式对数据进行存储，可以看出，图2.2（a）中只能容忍节点2或3中一个失效或离开，否则系统中的其它节点就不能剩余节点中完整地获取数据a、b、c、d；而圈2．2（b）中允许任一节点失效或离开，其它节点都能够自适应地做出调整，重新路由，从剩余的三个节点完整地获取数据a、b、“d。
图2.2节点失效或离开的影响失效
第三节络编码的应用
网络编码将原先分立于物理层和网络层的两个核心概念——编码和路由有机的融为一体，彻底改变了路由器只能对信息进行存储转发的传统模式，建立起一种全新的网络体系结构及信息编码和传输模式。
网络编码代表了一种协同工作的理念，这使得它的应用不仅局限于改进组播增加网络容量，与其它技术相结合已经应用于分布式内容存储与分发应用层组播无线传感器网络数据采集网络管理信息安全等众多领域。
1）分布式内容存储与分发。
传统的分布式内容分发或P2P对等通信时，Peer之间传送的是未编码的原始数据块（block），诸如Peer节点的搜索定位方法、资源分发与调度算法优化、网络负载平衡以及数据分发路由设计等问题都是目前P2P内容分发所面临的难题。
而在Peer之间传输经过网络编码的数据块能够有效解决甚至避免这些问题。
2）应用层组播。
P2P技术与覆盖网络（overlaynetwork）的发展，将组播功能从P层扩展到了应用层，在P2P应用层组播系统中，Peer节点对流经的数据除了进行存储转发外，如果还可以进行额外的网络编码处理，将可以在很大程度上改善应用层组播性能，提高覆盖网络数据吞吐能力。
3）无线传感器网络数据获取。
在无线传感器网络中，传感器节点的数据存储能力十分有限，如何将这些节点采集的信息在最小代价、最小能耗、最大容量等约束下发送给存储节点是当前网络编码在无线通信领域的一个新课题。
4）网络管理。
对于链路被截断等物理故障，传统的解决办法是启用备份链路进行重新路由，而对于采用网络编码的节点，改变编码规则就可以改变其传递给其它节点的信息内容，这同样起到了重新路由的作用，而且这种网络管理
方式的开销非常小。
5）信息安全。
攻击者恶意篡改网络上传输的数据内容将直接影响接收端的信息接收，这是目前计算机通信网的一个潜在隐患。
采用随机网络编码技术，攻击者对接收端收到的其它编码数据无法进行预知和控制，数据篡改的影响可以降至最低。
第三章一种基于网络编码的应用层组播路由算法
第一节应用层组播
一、应用层组播的提出
互联网上的大规模媒体存储与发布普遍是基于传统的客户机／服务器（C／S）系统架构，这种集中式的分发模型容易造成中央服务器的过量负载，直接导致网络吞吐量的下降，并且一旦中央服务器出现故障将直接导致整个传输体系瘫痪。
随着视频点播、网络电视、远程教育等多媒体服务飞速发展，中央服务器的带宽瓶颈问题日益凸显，以致集中式的分发模型逐步向基于P2P覆盖网络（overlaynetwork）架构的分布式结构过渡。
IP层组播是面向组通信应用的，被认为是大规模数据分发的最佳方法。
然而口组播增加了网络层的复杂性，而且需要对现有网络的底层设备进行巨大改动，因此至今口层组播仍然无法广泛部署。
叠加网（OverlayNetworks）是一个位于一个或多个己知网络上的独立的虚拟网络。
它的主要优点在于它的架构，它不需要改变底层网络的结构，可以快速部署所需的网络功能。
如果在叠加网的基础上实现组播，可以把组播实现提高到应用层。
端系统实现组播业务的思想是将组播作为一种叠加的业务，实现为应用层的服务，由此构成了应用层组播（applicationlayermulticast）
应用层组播是在叠加在m层之上的用于实现组播业务逻辑的功能性网络，应用层组播网络中的节点是由组播中的成员主机构成的，并由它们完成数据路由、复制和转发功能。
因为不再依靠网络层路由器来实现，所以不需要任何网络底层架构的改变，只需改变端系统，便于实现和推广。
图3．1对m组播和应用层组播的数据传输方式进行了比较：
图3．1m组播和应用层组播的数据传输方式比较
图3．1中假设A、B、C、D为四个端系统主机，R1，R2为路由器，箭头方向代表数据包的发送方向。
图3．1（a）为IP组播，A为网络中的源节点，数据包从A发到R1，再由R1转发给B和R2，R2再将收到的数据包转发给C和D。
图3．1（b）为应用层组播，A发送两份相同的数据包分别给B和C，再由C复制一份给D。
从图3．1（b）可以看到应用层组播有以下一些优点：
1．所有数据包都是通过单播传输的，无需路由器的支持，节点只需安装应用层软件即可，操作方便、易于广泛部署；
2.底层物理网络无需保存状态信息，而节点仅需要保存该组少量其它邻近成员的信息，可扩展性好；
3．利用单播，可以有效地采取适合流媒体应用特点的错误恢复、流量控制、拥塞控制等策略，提供端到端的服务质量保证；
4．不但能跨越空间维，还能跨越时间维进行数据传输，可牺牲同步性能来获得更好的服务质量保证；
5．地址可采用层次结构，可有效地扩大地址空间。
但从图3．1中可以看出应用层组播存在的一些固有问题，如效率不高，多条覆盖网络上的逻辑链路可能经过物理网络的同一链路；延迟大，两个节点之间的通讯可能要通过其它节点：
同步性能差，所有节点之间很难同步接收数据；可能跨越多个节点，丢包概率增大。
应用层组播的效率比P组播的效率要低，因为不可避免的会有组播路径重复的经过同一条底层链路，也就必然带来冗余的流量，例如在图3．1（b）中（A，R1）和（R2，C）这两条链路上有两个相同的数据包重复经过同一条底层链路，而图3．1（a）的口组播则只有一次。
另外，两个端系统之间的通信，可能要通过中间其他端系统的转发来实现，这也不可避免的造成两个通信节点之间延时的增加。
二应用层组播路由协议
应用层组播协议通常都按照两个拓扑结构组织组成员，一个是控制拓扑，一个是数据拓扑，控制拓扑的组成员周期性地交互刷新消息以相互标识身份并从节点失效中恢复。
而数据拓扑通常是控制拓扑的子集，它用于标识组播转发时使用的数据路径。
数据拓扑作为应用层组播协议的重要组成部分，即组播中文件数据的如何路由是本文讨论的重点。
一般来说，组播组用于标识组播转发时用的数据路径通常是一棵组播树。
其中在组播中最基本两种数据转发方式是：
建立最短路径树和最小生成树，常见的路由算法为：
Bellman—Ford最短路径树算法、Dijstra
最短路径树算法和Prim最小生成树算法。
最短路径树是从源节点到所有接收节点的每条路径上链路权值之和最小的组播树。
如果所有的链路的权值都表1，则为最小跳树。
如果权值代表链路延时，则为最小时延树。
最小生成树是指覆盖所有组成员且权值最小的组播树。
此外，还有基于Steiner树的问题致力于使组播树的总代价最小，这已经证明了是图论中一个NP．complete问题。
如果组播树包含了树中所有节点，Stoner树问题转化为最小生成树问题。
一般通过启发式算法求解，典型的启发式算法有：
MST、RS、KMB[31，321。
Steiner树问题可以扩展到包括其它的链路约束。
例如延时、延时抖动或者它们的组合。
通常这些问题是NP．Complete的，所以也需要采用启发式算法解决。
第二节基于网络编码的应用层组播路由算法
在日常生活中，我们经常要使用到比较大规模的通信网络，我们都希望通信网络能为我们提供更为安全、快速的网络服务。
于是我们提出了实现在已有通信网络中达到最大数据流的目标。
由前一章可知，网络编码可以实现网络的最大流传输。
网络信息理论的研究指出：
在组播通信中，每个接收节点可以以网络拓扑中信源发送点与信宿接收点之间的最大流容量进行信息传递。
然而，从信源到不同信宿之间的最大流经过的传输路径可能在网络拓扑的链路上形成交叉共享链路，因此采用传统的存储转发模式即P组播的方式，无法达到最大流最小割的理论上限。
网络编码，作为一种协同工作的理念，将原先分立于物理层和网络层的两个核心概念——编码和路由有机地融为一体，通过在中间节点中进行传递信息的编码组合运算，建立起一种异于传统存储转发的全新网络信息传输模式。
应用层组播是以端系统为基础的逻辑覆盖网（overlaynetwork），不同与以往m层组播中的路由器节点，端系统可以提供更为强大的功能，如能够对数据进行编码组合运算，这为网络编码在覆盖网络上的应用提供了技术支撑。
本节的主要内容就是建立一种基于网络编码的启发式应用层组播路由算法，目的在于利用网络编码技术在分布式网络中建立数据分发拓扑使得网络传输容量趋于组播容量上限。
在分布式拓扑中运用随机线性网络编码技术，即中间节点对发往不同目的节点的组播数据进行编码组合后再转发，以避开数据流对链路的竞争冲突，提高组播通信的吞吐量。
一、冗余路径
考虑到网络编码在提高网络的吞吐量方面的优点，为了进一步改善应用层组播的性能，从而我们引入了网络编码技术。
但是网络编码不是万能的，不是所有的网络组播拓扑都能使用。
应用层组播要结合网络编码技术，
升级会员 