信息论-网络编码.ppt

,网络编码,组员：代亮亮 徐杰 郭鑫 李文杰 胡怡 刘慧芳 张晓宇,目录,原理,目录,原理,1、概念,网络编码：通信网络中信息处理和传输理论研究上的重大突破。,网络编码：融合了编码和路由转发的信息交换技术，在传统存储转发的路由方法基础上，通过允许对接收的多个数据包进行编码(如模二加、有限域 上的运算等)信息融合，增加单次传输的信息量，以提高网络信息传输效率和整体性能核心：允许网络节点对传输信息进行编码处理,经典信息论中的信息传输：单纯共享网络和链路资源，彼此独立。,网络编码的起源与发展,概念诞生：1998论文“Network Information Flow Theory”1999 Yeung和Zhang发表的关于卫星通信的论文正式发表：2000网络编码理论的奠基之作：先锋论文“NetworkInformationFlow”里程碑（2003）：香港中文大学讯息工程系的李硕彦教授、杨伟豪教授、蔡宁教授发表了论文“LinearNetworkCoding”指出线性网络编码可以达到多播方式下的网络容量。Koetter和Medard提出网络编码的代数学(Algebra)框架，即用抽象代数来解决线性网络编码的问题，为研究网络编码提供了一个用力的数学工具 Sanders等提出具有多项式复杂度的线性信息流算法，该算法属于集中式的码构造算法。Ho等提出随机网络编码(RandomNetworkCoding,RNC)，属于分布式的码构造方法。,基础知识：最大流最小割定理1/5,割:网络中定点的一个划分，把网络中所有的顶点划分为两个顶点的集合S和T，其中源点s属于S，汇点t属于T，记为CUT（S，T）,顶点集:S=1,2,3,T=4,5构成一个割框外是容量，框内是流量,注：源点和汇点不能属于同一个顶点集合：如下就不能构成一个割,基础知识：最大流最小割定理2/5,s-t图：a 一个源点和一个汇点b 有向边，是从i到jc 每条边都有一个非负的权值d 容量cap（i，j）等于0，说明不存在边,基础知识：最大流最小割定理3/5,割边：如果一条弧的两个顶点分别属于顶点集S和T（一个在S，另一个在T），这条弧成为CUT（S，T）的一条割边。割的容量：割CUT（S,T）中所有正向割边的容量和，称为CUT（S，T）的容量，不同割的容量不同。最小割：所有割中权重和最小的一个割。,eg.左图中：割的容量为4+4=8 正向流量：4+2=6 逆向流量：1,定理一：如果f是网络中的一个流，CUT（S,T）是任意一个割，那么f的值等于正向割边的流量与负向割边的流量之差。推论一：如果f是网络中的一个流，CUT（S，T）是一个割，那么f的值不超过割CUT（S,T）的容量推论二：网络中的最大流不超过任何割的容量。定理二：在网络中，如果f是一个流，CUT（S,T）是一个割，且f的值等于割CUT（S，T）的容量，那么f是一个最大流，CUT（S,T）是一个最小割。,基础知识：最大流最小割定理4/5,最大流最小割定理：任何网络中，最大流等于最小割的容量,形象的比喻：水流管道的最大流量由最细的管子容量决定。网络的最大流量由最小割决定。,基础知识：最大流最小割定理5/5,目录,原理,网络编码基本原理蝴蝶网络”（Butterfly Network）,左图为“单信源二信宿”蝴蝶网络设各链路容量为1S：信源节点。Y,Z：信宿节点。其余为中间节点。由最大流最小割定理，该多播的最大理论传输容量为2。即理论上信宿Y和Z能够同时收到信源S发出的2个单位的信息,，也就是说能同时收到b1和b2。,图(a),图(b),网络编码基本原理,网络编码基本原理,网络编码的核心思想具备编码条件的网络节点A对接收到的信息进行一定方式的处理(编码)，然后传输给下一级的网络节点BB再编码，然后传输给C。如此反复，直到所有经过处理后的信息都汇聚到信宿节点为止。在信宿节点，通过逆过程的操作(译码)，即可译出信源发送的原始信息。,目的：A和 B 希望分别向对方发送数据块 x 和 y,传统方法：需要 4 个时隙1)2)3)4),网络编码方法：需要的时隙数减为 3 个1)2)3)R对X，Y执行异或操作并向A,B 广播，A，B各自有X，Y的信息，可以通过译码得到X，和Y,网络编码基本原理,目录,原理,协作通信通过网络节点协作的方式接收转发其他伙伴的信息到目的端，以获得系统的分集增益，从而对抗无线信道的各种衰落。网络编码借助于融合了编码和路由的新思想，通过允许中间节点对来自不同链路的信息进行解码组合，利用数据包之间的相关性来解码，从而提升整个网络的性能。,网络编码在无线协作通信中的应用,背景与意义,协作通信系统模型,结合网路编码思想与协作通信技术，以能更好的充分发挥网络编码技术在无线协作通信系统中的应用优势，进一步提高基于网络编码的无线协作系统性能.,协作通信的分类,放大转发（AF,Amplify and Forward）在信道质量较差的情况下，AF会将噪声放大。解码转发（DF,Decode and Forward）在信道质量较差的情况下，DF中继无法正确解码。两者都是信息的重复传输，信道利用率不高，造成资源浪费。编码协作（CC，Cooperation Coded）提供比重复编码更高效的编码方式，从而带来更多的编码增益。但是中继点复杂度高，中继点信号处理时延增大，降低了时效性。,编码协作（CC）,CC协议是解码转发协作（DF）的进一步延伸，它改变DF策略的重复编码方式，通过两条不同的，相互独立的衰落信道来发送每个用户的信息码字的不同部分，从而提供更多的编码增益。,无线网络编码分类,1.网络层网络编码2.物理层网络编码,网络层网络编码,针对网络层编码技术，目前的一个研究重点是在实际的网络条件下，采样网络编码后的网络容量以及可以达到的网络容量的传输策略,物理层网络编码,物理层网络编码提高了无线频谱的利用率，物理层网络编码技术目前的研究重点是怎样有效的从混合信号中分离出需要的信号。,S1,R,S2,D,时隙1,时隙2,时隙3,网络编码在分布式存储中的应用,分布式存储由来及优越性,传统的存储模型中,大多为直连式存储系统,其存储设备直接与服务器 相连。此类存储模型可扩展性极差,数据共享能力弱。1986年,著名学者李凯针对大数据存储困难的现状提出了分布式存储 的概念,该思想源于虚拟存储系统。分布式存储就是将源文件分散的存储到网络中的相互独立的空闲节点中。优越性(1)高可靠性(2)修复功能(3)可扩展性(4)高性能(5)透明性,网络编码理论在数据安全领域的应用,网络纠错码 网络编码的初衷在于提高网络的吞吐量,但是随着进一步研究发现它也是一种安全网络传输的好方式。然而在抗击拜占庭攻击时,我们不仅要能够检测出敌手对信息的恶意攻击,还要尽量能够做到对这些信息的恢复,这就是网络纠错码.传统的密码学方法存在一定的局限性 计算复杂度较大、数据传输速率较低、消息冗余较大,分布式存储的维护,最常用冗余数据的维护技术是复制和纠删码。当我们在利用纠删码对失效节点进行修复的时候，首先要将原始数据重建，然后将其用网络编码的方法进行编码，但是这样修复时数据的下载量远远多于节点的存储，即修复带宽远大于存储量。,再生码,两种常用的冗余数据维护技术在对数据节点进行修复时，需要消耗很大的下载带宽，于是产生了一种新型的技术再生码。实现了存储量与修复下载带宽的良好折中，部分还巧妙地结合了复制与纠删码的各自优点，保证了具有极高的节点成功修复的可能性。,信息流图,他们把节点修复的问题刻画为网络系统中普遍的单源多播问题，然后把对分布式存储系统的分析化成对信息流图的分析,再生码的一个定理,对于任意，分布式存储系统中的点是可行的，它可以通过线性网络编码来实现。当 时，在信息理论上是不可能实现的。其理论界函数如下：其中对于给定的n，k，d，最小修复带宽的值为,MSR和MBR,网络编码理论在数据安全领域的应用,网络编码理论在数据安全领域的应用,传统的密码学方法存在一定的局限性(1)计算复杂度较大(2)数据传输速率较低(3)消息冗余较大网络纠错码 网络编码的初衷在于提高网络的吞吐量,但是随着进一步研究发现它也是一种安全网络传输的好方式。然而在抗击拜占庭攻击时,我们不仅要能够检测出敌手对信息的恶意攻击,还要尽量能够做到对这些信息的恢复,这就是网络纠错码.,搭载窃听网络通信的模型网络通信的模型,m:是消息本身k:是为了达到安全的随机数右图中红线是窃听集，但是一个时间内只允许敌手窃听其中的一条，这样接收节点T和T能够安全接收到信源传来的消息。,网络编码理论在数据安全领域的应用,图3 Alice、Bob 和Eve的数据包,X:表示Alice发出的原始消息块Z:表示攻击者Eve注入的错误消息块Y:表示经过篡改被Bob接收的消息块矩阵I、L和T分别表示数据包X、Y和Z的编码向量。,图3是有线和无线网络的带有拜占庭攻击者的攻击模型，为了简化符号，只考虑单信源单信宿的通信问题。相似于许多网络编码的算法，这里每个体制都可以从单个接收方的情形推广到多播通信。,网络编码理论在数据安全领域的应用,3种主要攻击模型,(1)秘密共享模型 此模型假定Alice和Bob有一个低速率的秘密信道，Eve不知道秘密信道上的传输消息。考虑将消息经过网络编码后在网络上传输，Eve可以观察到所有除秘密信道之外的所有传输，也可以选择是否在他所控制的节点处在要传输的数据包中注入一些恶意数据到从而达到阻止Alice和Bob通信的目的。(2)万能攻击者模型 此模型中Eve除了在控制链接数目上受到一定限制外，是万能的、无所不知的，Alice和Bob之间没有独立于Eve的秘密信道。(3)有限的窃听模型 在这个模型中，Eve 的窃听能力是有限制的，只能观察到至多 Z I 个传送的包。,网络编码在p2p网络系统中的应用,网络编码在p2p网络系统中的应用p2p系统简介,p2p网络系统：P2P全称为：Peer-to-Peer，即对等网络或对等计算。主要采用非集中式的拓扑结构，可以应对集中式拓扑结构出现的过量存储负载、DOS（Denial of Service，拒绝服务）攻击，网络带宽限制等一些难以解决的问题。P2p网络系统发展的四种拓扑结构:中心化拓扑、全分布式非结构化拓扑、全分布结构式拓扑、半分布式拓扑,网络编码在p2p网络系统中的应用p2p系统简介,p2p网络系统四种技术优势：非中心化：资源和服务分散在对等结点上，信息的交付直接在结点之间进行，无需服务器介入，避免了可能的瓶颈。可扩展性：系统的资源和服务能力可以随着新用户的加入和服务需求的增加而提高。鲁棒性：即系统的健壮性，在抗异常和突发危险情况的能力。服务是分散在各对等结点上的，没有中心节点和特殊节点，某些节点出现异常或遭受攻击时，整个网络的影响很小，具有很强的自组织性和自愈性。负载均衡：每个节点既是服务器又是客户机，同时因资源分布在多个节点，能更好实现整个网络的负载均衡。,网络编码在p2p网络系统中的应用文件下载,三种文件下载方式：无分代随机网络编码技术：优点是分块随机组合后，整个网络的分块分布均衡化，而且能够适应P2P系统的动态变化。缺点是编码解码过程是在一个文件的所有分块之间进行的，计算量大，系统开销过大，尤其是大文件分发时。分代网络编码方法：优点是解决无分代网络编码的问题。缺点是节点的退出使得网络中已经不存在足够多线性无关的编码组合以解码得出某一代的原始分块，从而导致无法解除完整的文件；源节点不知如何从本代信息传输切换到下一代信息传输等。代间网络编码方法：优点：当本代集中的某一代没有足够多线性无关的编码块时，可以由本代集其他代的线性无关编码块来弥补。缺点：无法单独成功解出某一代的原始数据。,网络编码在p2p网络系统中的应用文件下载,假设服务器需要传输文件给对等节点A，首先将服务器上的文件分解成n个文件块，B1Bk，然后应用随机网络编码，随机选择系数C1Cn，将线性网络编码后的组合块E1=c1B1+c2B2cnBk传送给对等节点A，同理得出E2=C1B1+C2B2CnBk，该组合块来自其它对等节点或者服务器。然后对等节点A再随机选择编码系数C1、C2，对E1和E2进行线性操作，将操作的结果E3=C1E1+C2E2发送给对等节点B，对等节点B又传送给其它的对等节点。只要每一个对等节点收到足够多的线性无关组合，就可以通过解线性方程组译出原始文件块。,无分代随机网络编码技术,网络编码在p2p网络系统中的应用文件下载,把传输的文件先分成多个代，每个代再分成一定数目的块，并且每代拥有的分块数目是固定的。网络编码和解码的过程只在同一代内进行，代与代之间编码过程是独立的。如图所示，首先将文件分成m（m2）个代，每个代内再分成n（n2，nm）个文件分块。编码过程在代内进行，而且代与代之间的编码过程是彼此独立的。源节点首先对第一代内的文件执行无分代网络编码直到信宿可以正确译出第一代的所有信息，然后再在第二代内执行无分代网络编码信息传输，以此类推，直到传输完整个文件。,分代网络编码方法,网络编码在p2p网络系统中的应用文件下载,首先把文件分代，代内再分组，然后把本代及其之前所有的代组合成一个代集，在代集内进行编码。代集之间编码过程是独立的。如图所示：首先把要发送的源文件分成m代，每代再分成k个块，本代及其之前所有的代构成代集，编码过程和解码过程都在代集内进行，并且代集之间彼此独立。,代间网络编码方法,流媒体与文件下载的最大区别是前者要求边下载边播，而后者没有这个要求。目前基于p2p的实时流媒体系统中，根据覆盖网节点所构成的拓扑规划，分为单组播树拓扑、多组播树拓扑和网状拓扑三类。如上图所示现有p2p流媒体传输系统很多是基于分层编码实现的，其系统主要由两个模块组成：资源发现模块和资源传输模块。,网络编码在p2p网络系统中的应用流媒体,空间分层编码 实现不同大小图像的服务兼容性。先在原始图像中采样的方法得到一帧空间上低频分辨率的图像。从原始图像减去经过内插的抽样图像得到的差值图像，对差值图像再进行编码得到增强层。时间分层编码 为实现不同频率的视频服务兼容。其基本层和增强层具有相同的空间分辨率和SNR。基本层图像进行运动估计时只能在基本层中选取，同理增强层也是。视频的精细分层 为支持信道特性多变的包交换网上多媒体应用和服务而提出,网络编码在p2p网络系统中的应用流媒体,分层编码,网络编码在p2p网络系统中的应用流媒体,资源发现模块,主要任务是协助新的节点找到自己感兴趣的流媒体文件的所在位置。节点接入机制每一个节点有一个在整个系统中的全局唯一的标识，如IP地址，超级节点维护一个系统中其他节点的标识缓存。当新的节点A接入时，首先通过资源查找获得所需文件的伙伴节点列表。对于列表中的节点，A通过“三次握手”的机制与对方建立连接，并测试对方的可用带宽，A从所有的备选节点中选择合适的节点作为自己的上游节点，则此建立连接的过程得以完成，新节点获得稳定的伙伴节点，开始进行流媒体下载缓冲，进入稳定的播放阶段,网络编码在p2p网络系统中的应用流媒体,资源传输模块,目的是完成资源传输的任务分配，任务调度以及任务控制等内容。在P2P文件传输系统中，流媒体被划分数据块，数据块中的数据又被分为多个数据包，并且使用可用度向量的概念来标识一个节点拥有数据块中的哪些数据包。P2P流媒体传输系统的资源传输模块分为请求数据、发送数据和接收数据三个相关联的部分。,接收数据部分：接收部分的主要任务是接收到数据后，按照一定的结构将数据存放在本地，并且修改本地的数据可用度向量。如果接收到重复数据，则直接丢弃。,网络编码在p2p网络系统中的应用流媒体,资源传输模块,请求数据部分：首先向发送节点询问当前期望传输文件块的可用度向量，得到以后，根据请求与其他提供资源节点之间的带宽情况，计算出对应于每个提供资源节点的队列长度，然后将其发送的请求放入各自的队列中，各队列独立的向对应节点发送请求。,网络编码在p2p网络系统中的应用流媒体,资源传输模块,发送数据部分：先判断接收到的请求类型连接请求：检查是否达到最大连接数，达到则发送拒绝消息，反之发送接收消息。数据请求：从本地寻找对应数据，找到则发送，未找到不发送,目录,原理,4.1 总结,网络编码提出的初衷是为使多播传输达到理论上的最大传输容量,从而能取得较路由多播更好的网络吞吐量。通过以上介绍，网络编码的优点也体现出来了。提升网络吞吐量 无论是均匀链路还是非均匀链路,网络编码均能够获得更高的多播容量,而且对于节点平均度数越大,网络编码在网络吞吐量上的优势越明显。均衡网络负载 网络编码多播可有效利用除多播树路径外其它的网络链路,可将网络流量分布于更广泛的网络上,从而均衡网络负载。这样就有助于解决网络拥塞等问题。提高带宽利用率 虽然传输链路增多了，但是每条链路上的信息减少了（均衡了），总体是减少了网络带宽，提高了网络带宽利用率。,虽然网络编码优点突出,但是缺点也很明显。运用网络编码增加了计算的复杂性,而且网路节点需要缓存足够的输入信息,因此编码操作增加了传输时延和节点额外的I/O、CPU消耗。应用网络编码还存在同步问题,主要是由于信宿节点必须等待收到足够的编码信息,才能开始译码。同步问题给在实时系统中应用网络编码提出了挑战。,Thank you！,