书签 分享 收藏 举报 版权申诉 / 55
上传文档赚钱

类型信息论-网络编码(课堂PPT)课件.ppt

  • 上传人(卖家):三亚风情
  • 文档编号:2557075
  • 上传时间:2022-05-04
  • 格式:PPT
  • 页数:55
  • 大小:1.51MB
  • 【下载声明】
    1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
    2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
    3. 本页资料《信息论-网络编码(课堂PPT)课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
    4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
    5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
    配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    信息论 网络 编码 课堂 PPT 课件
    资源描述:

    1、网络编码网络编码组员:代亮亮 徐杰 郭鑫 李文杰 胡怡 刘慧芳 张晓宇概念概念12应用应用3总结总结4原理原理概念概念12应用应用3总结总结4原理原理网络编码:通信网络中信息处理和传输理论研究上的重大突破。网络编码:融合了编码和路由转发的信息交换技术, 在传统存储转发的路由方法基础上, 通过允许对接收的多个数据包进行编码(如模二加、有限域 上的运算等)信息融合,增加单次传输的信息量, 以提高网络信息传输效率和整体性能核心核心:允许网络节点对传输信息进行编码处理经典信息论中的信息传输:单纯共享网络和链路资源,彼此独立。1998论文“ Network Information Flow Theory

    2、”1999 Yeung和Zhang发表的关于卫星通信的论文2000网络编码理论的奠基之作:先锋论文“ NetworkInformationFlow” 香港中文大学讯息工程系的李硕彦教授、 杨伟豪教授、 蔡宁教授发表了论文“LinearNetworkCoding” 指出线性网络编码可以达到多播方式下的网络容量。 Koetter和Medard提出网络编码的代数学(Algebra)框架, 即用抽象代数来解决线性网络编码的问题, 为研究网络编码提供了一个用力的数学工具 Sanders等提出具有多项式复杂度的线性信息流算法, 该算法属于集中式的码构造算法。 Ho等提出随机网络编码(RandomNetwo

    3、rkCoding,RNC), 属于分布式的码构造方法。割:网络中定点的一个划分,把网络中所有的顶点划分为两个顶点的集合S和T,其中源点s属于S,汇点t属于T,记为CUT(S,T)顶点集: S=1,2,3, T=4,5构成一个割框外是容量,框内是流量注:源点和汇点不能属于同一个顶点集合:如下就不能构成一个割s-t图:a 一个源点和一个汇点b 有向边,是从i到jc 每条边都有一个非负的权值d 容量cap(i,j)等于0,说明不存在边割边:如果一条弧的两个顶点分别属于顶点集S和T(一个在S,另一个在T),这条弧成为CUT(S,T)的一条割边。割的容量:割CUT(S,T)中所有正向割边正向割边的容量和

    4、,称为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)是一个最小割。最大流最小割定理

    5、:最大流最小割定理:任何网络中,最大流等于最小割的容量形象的比喻:水流管道的最大流量由最细的管子容量决定。网络的最大流量由最小割决定。概念概念12应用应用3总结总结4原理原理蝴蝶网络”(Butterfly Network)左图为“单信源二信宿”蝴蝶网络设各链路容量为1S:信源节点。 Y,Z:信宿节点。 其余为中间节点。由最大流最小割定理,该多播的最大理论传输容量为2。即理论上信宿Y和Z能够同时收到信源S发出的2个单位的信息,,也就是说能同时收到b1和b2。图(a)图(b) 具备编码条件的网络节点A对接收到的信息进行一定方式的处理(编码) ,然后传输给下一级的网络节点B B再编码,然后传输给C。

    6、如此反复,直到所有经过处理后的信息都汇聚到信宿节点为止。 在信宿节点,通过逆过程的操作(译码) ,即可译出信源发送的原始信息。目的: A和 B 希望分别向对方发送数据块 x 和 y BS BS SSA R BXY 简单网络编码示例基站中继站用户站BRYRBXARXRAY传统方法:需要 4 个时隙1) 2)3) 4) 网络编码方法:需要的时隙数减为 3 个1)2)3) R对X,Y执行异或操作并向A,B 广播,A,B各自有X,Y的信息,可以通过译码得到X,和YARXBRY概念12应用3总结4原理 协作通信通过网络节点协作的方式接收转发其他伙伴的信息到目的端,以获得系统的分集增益,从而对抗无线信道的

    7、各种衰落。 网络编码借助于融合了编码和路由的新思想,通过允许中间节点对来自不同链路的信息进行解码组合,利用数据包之间的相关性来解码,从而提升整个网络的性能。网络编码在无线协作通信中的应用网络编码在无线协作通信中的应用背景与意义背景与意义协作通信系统模型 结合网路编码思想与协作通信技术,以能更好的充分发挥网络编码技术在无线协作通信系统中的应用优势,进一步提高基于网络编码的无线协作系统性能.协作通信的分类协作通信的分类放大转发(放大转发(AF, Amplify and Forward) 在信道质量较差的情况下,AF会将噪声放大。解码转发解码转发 (DF,Decode and Forward) 在信

    8、道质量较差的情况下,DF中继无法正确解码。 两者都是信息的重复传输,信道利用率不高,造成资源浪费。编码协作(编码协作(CC,Cooperation Coded) 提供比重复编码更高效的编码方式,从而带来更多的编码增益。但是中继点复杂度高,中继点信号处理时延增大,降低了时效性。编码协作(编码协作(CCCC) CC协议是解码转发协作(DF)的进一步延伸,它改变DF策略的重复编码方式,通过两条不同的,相互独立的衰落信道来发送每个用户的信息码字的不同部分,从而提供更多的编码增益。无线网络编码分类无线网络编码分类1.网络层网络编码2.物理层网络编码 针对网络层编码技术,目前的一个研究重点是在实际的网络条

    9、件下,采样网络编码后的网络容量以及可以达到的网络容量的传输策略 物理层网络编码提高了无线频谱的利用率,物理层网络编码技术目前的研究重点是怎样有效的从混合信号中分离出需要的信号。S1RS2D1x1x2x2x21xx 传输时隙传输时隙信息传输方向信息传输方向传输信息传输信息简要说明简要说明时隙1(直传)S1(R,D)X1S1传送信息X1到R和D时隙2(直传)S2(R,D)X2S2传送信息X2到R和D时隙3(协作)R(D)X1 X2R将收到的信息进行编码后转发给D时隙1时隙2时隙3网络编码在分布式存储中的应用 传统的存储模型中,大多为直连式存储系统,其存储设备直接与服务器 相连。此类存储模型可扩展性

    10、极差,数据共享能力弱。 1986年,著名学者李凯针对大数据存储困难的现状提出了分布式存储 的概念,该思想源于虚拟存储系统。 分布式存储就是将源文件分散的存储到网络中的相互独立的空闲节点中。 优越性 (1)高可靠性高可靠性 (2)修复功能修复功能 (3)可扩展性可扩展性 (4)高性能高性能 (5)透明性透明性网络纠错码 网络编码的初衷在于提高网络的吞吐量,但是随着进一步研究发现它也是一种安全网络传输的好方式。然而在抗击拜占庭攻击时,我们不仅要能够检测出敌手对信息的恶意攻击,还要尽量能够做到对这些信息的恢复,这就是网络纠错码.传统的密码学方法存在一定的局限性 计算复杂度较大、 数据传输速率较低、

    11、消息冗余较大 最常用冗余数据的维护技术是复制和纠删码。 当我们在利用纠删码纠删码对失效节点进行修复的时候,首先要将原始数据重建,然后将其用网络编码的方法进行编码,但是这样修复时数据的下载量远远多于节点的存储,即修复带宽远大于存储量。两种常用的冗余数据维护技术在对数据节点进行修复时,需要消耗很大的下载带宽,于是产生了一种新型的技术再生码。实现了存储量与修复下载带宽的良好折中,部分还巧妙地结合了复制与纠删码的各自优点,保证了具有极高的节点成功修复的可能性。他们把节点修复的问题刻画为网络系统中普遍的单源多播问题,然后把对分布式存储系统的分析化成对信息流图的分析ddknG),(对于任意 , 分布式存储

    12、系统中的点是可行的,它可以通过线性网络编码来实现。当 时,在信息理论上是不可能实现的。其理论界函数如下:其中对于给定的n,k,d,最小修复带宽的值为),(*dkn),(dkn),(*dkn网络编码理论在数据安全领域的应用传统的密码学方法存在一定的局限性 (1)计算复杂度较大 (2)数据传输速率较低 (3)消息冗余较大网络纠错码 网络编码的初衷在于提高网络的吞吐量,但是随着进一步研究发现它也是一种安全网络传输的好方式。然而在抗击拜占庭攻击时,我们不仅要能够检测出敌手对信息的恶意攻击,还要尽量能够做到对这些信息的恢复,这就是网络纠错码.搭载窃听网络通信的模型网络通信的模型m:是消息本身k:是为了达

    13、到安全的随机数右图中红线是窃听集, 但是一个时间内只允许敌手窃听其中的一条, 这样接收节点T和T能够安全接收到信源传来的消息。 图3 Alice、Bob 和Eve的数据包X:表示Alice发出的原始消息块Z:表示攻击者Eve注入的错误消息块Y:表示经过篡改被Bob接收的消息块矩阵I、 L和T分别表示数据包X、 Y和Z的编码向量。图3是有线和无线网络的带有拜占庭攻击者的攻击模型, 为了简化符号,只考虑单信源单信宿的通信问题。相似于许多网络编码的算法, 这里每个体制都可以从单个接收方的情形推广到多播通信。(1)秘密共享模型秘密共享模型 此模型假定Alice和Bob有一个低速率的秘密信道, Eve不

    14、知道秘密信道上的传输消息。考虑将消息经过网络编码后在网络上传输, Eve可以观察到所有除秘密信道之外的所有传输,也可以选择是否在他所控制的节点处在要传输的数据包中注入一些恶意数据到从而达到阻止Alice和Bob通信的目的。(2)万能攻击者模型万能攻击者模型 此模型中Eve除了在控制链接数目上受到一定限制外,是万能的、 无所不知的, Alice和Bob之间没有独立于Eve的秘密信道。(3)有限的窃听模型有限的窃听模型 在这个模型中, Eve 的窃听能力是有限制的, 只能观察到至多 Z I 个传送的包。网络编码在p2p网络系统中的应用p2p网络系统: P2P全称为:Peer-to-Peer,即对等

    15、网络或对等计算。主要采用非集中式的拓扑结构非集中式的拓扑结构,可以应对集中式拓扑结构出现的过量存储负载、DOS(Denial of Service,拒绝服务)攻击,网络带宽限制等一些难以解决的问题。P2p网络系统发展的四种拓扑结构: 中心化拓扑、全分布式非结构化拓扑、全分布结构式拓扑、半分布式拓扑p2p网络系统四种技术优势: 非中心化:资源和服务分散在对等结点上,信息的交付直接在结点之间进行,无需服务器介入,避免避免了可能的瓶颈瓶颈。 可扩展性:系统的资源和服务能力可以随着新用户的加入和服务需求的增加而提高。 鲁棒性:即系统的健壮性健壮性,在抗异常和突发危险情况的能力。服务是分散在各对等结点上

    16、的,没有中心节点和特殊节点,某些节点出现异常或遭受攻击时,整个网络的影响很小,具有很强的自组织性和自愈自组织性和自愈性性。 负载均衡:每个节点既是服务器又是客户机,同时因资源分布在多个节点,能更好实现整个网络的负载均衡。三种文件下载方式: 无分代随机网络编码技术:优点优点是分块随机组合后,整个网络的分块分布均衡化,而且能够适应P2P系统的动态变化。 缺点缺点是编码解码过程是在一个文件的所有分块之间进行的,计算量大,系统开销过大,尤其是大文件分发时。 分代网络编码方法:优点优点是解决无分代网络编码的问题。 缺点缺点是节点的退出使得网络中已经不存在足够多线性无关的编码组合以解码得出某一代的原始分块

    17、,从而导致无法解除完整的文件;源节点不知如何从本代信息传输切换到下一代信息传输等。 代间网络编码方法:优点优点:当本代集中的某一代没有足够多线性无关的编码块时,可以由本代集其他代的线性无关编码块来弥补。 缺点缺点:无法单独成功解出某一代的原始数据。假设服务器需要传输文件给对等节点A,首先将服务器上的文件分解成n个文件块,B1Bk,然后应用随机网络编码,随机选择系数C1Cn,将线性网络编码后的组合块E1=c1B1+c2B2cnBk传送给对等节点A,同理得出E2=C1B1+C2B2CnBk,该组合块来自其它对等节点或者服务器。然后对等节点A再随机选择编码系数C1、C2 ,对E1和E2进行线性操作,

    18、将操作的结果E3= C1E1+ C2 E2 发送给对等节点B,对等节点B又传送给其它的对等节点。只要每一个对等节点收到足够多的线性无关组合,就可以通过解线性方程组译出原始文件块。把传输的文件先分成多个代,每个代再分成一定数目的块,并且每代拥有的分块数目是固定的。网络编码和解码的过程只在同一代内进行,代与代之间编码过程是独立的。如图所示,首先将文件分成m(m2)个代,每个代内再分成n(n2,nm)个文件分块。编码过程在代内进行,而且代与代之间的编码过程是彼此独立的。源节点首先对第一代内的文件执行无分代网络编码直到信宿可以正确译出第一代的所有信息,然后再在第二代内执行无分代网络编码信息传输,以此类

    19、推,直到传输完整个文件。首先把文件分代,代内再分组,然后把本代及其之前所有的代组合成一个代集,在代集内进行编码。代集之间编码过程是独立的。如图所示:首先把要发送的源文件分成m代,每代再分成k个块,本代及其之前所有的代构成代集,编码过程和解码过程都在代集内进行,并且代集之间彼此独立。流媒体与文件下载的最大区别是前者要求边下载边播,而后者没有这个要求。目前基于p2p的实时流媒体系统中,根据覆盖网节点所构成的拓扑规划,分为单组播树拓扑、多组播树拓扑和网状拓扑三类。如上图所示现有p2p流媒体传输系统很多是基于分层编码实现的,其系统主要由两个模块组成:资源发现模块和资源传输模块。空间分层编码 实现不同大

    20、小图像的服务兼容性。先在原始图像中采样的方法得到一帧空间上低频分辨率的图像。从原始图像减去经过内插的抽样图像得到的差值图像,对差值图像再进行编码得到增强层。时间分层编码 为实现不同频率的视频服务兼容。其基本层和增强层具有相同的空间分辨率和SNR。基本层图像进行运动估计时只能在基本层中选取,同理增强层也是。视频的精细分层 为支持信道特性多变的包交换网上多媒体应用和服务而提出 主要任务是协助新的节点找到自己感兴趣的流媒体文件的所在位置。 节点接入机制节点接入机制每一个节点有一个在整个系统中的全局唯一的标识,如IP地址,超级节点维护一个系统中其他节点的标识缓存。当新的节点A接入时,首先通过资源查找获

    21、得所需文件的伙伴节点列表。对于列表中的节点,A通过“三次握手”的机制与对方建立连接,并测试对方的可用带宽,A从所有的备选节点中选择合适的节点作为自己的上游节点,则此建立连接的过程得以完成,新节点获得稳定的伙伴节点,开始进行流媒体下载缓冲,进入稳定的播放阶段 目的是完成资源传输的任务分配,任务调度以及任务控制等内容。 在P2P文件传输系统中,流媒体被划分数据块,数据块中的数据又被分为多个数据包,并且使用可用度向量的概念来标识一个节点拥有数据块中的哪些数据包。P2P流媒体传输系统的资源传输模块分为请求数据、发送数据和接收数据三个相关联的部分。接收数据部分: 接收部分的主要任务是接收到数据后,按照一

    22、定的结构将数据存放在本地,并且修改本地的数据可用度向量。如果接收到重复数据,则直接丢弃。请求数据部分: 首先向发送节点询问当前期望传输文件块的可用度向量,得到以后,根据请求与其他提供资源节点之间的带宽情况,计算出对应于每个提供资源节点的队列长度,然后将其发送的请求放入各自的队列中,各队列独立的向对应节点发送请求。发送数据部分:先判断接收到的请求类型连接请求:检查是否达到最大连接数,达到则发送拒绝消息,反之发送接收消息。数据请求:从本地寻找对应数据,找到则发送,未找到不发送概念12应用3总结4原理 网络编码提出的初衷是为使多播传输达到理论上的最大传输容量,从而能取得较路由多播更好的网络吞吐量。通

    23、过以上介绍,网络编码的优点也体现出来了。 提升网络吞吐量提升网络吞吐量 无论是均匀链路还是非均匀链路,网络编码均能够获得更高的多播容量,而且对于节点平均度数越大,网络编码在网络吞吐量上的优势越明显。 均衡网络负载均衡网络负载 网络编码多播可有效利用除多播树路径外其它的网络链路,可将网络流量分布于更广泛的网络上,从而均衡网络负载。这样就有助于解决网络拥塞等问题。 提高带宽利用率提高带宽利用率 虽然传输链路增多了,但是每条链路上的信息减少了(均衡了),总体是减少了网络带宽,提高了网络带宽利用率。虽然网络编码优点突出,但是也很明显。 运用网络编码增加了计算的复杂性,而且网路节点需要缓存足够的输入信息,因此编码操作增加了传输时延和节点额外的I/O、CPU消耗。 应用网络编码还存在同步问题,主要是由于信宿节点必须等待收到足够的编码信息,才能开始译码。同步问题给在实时系统中应用网络编码提出了挑战。Thank you!

    展开阅读全文
    提示  163文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:信息论-网络编码(课堂PPT)课件.ppt
    链接地址:https://www.163wenku.com/p-2557075.html

    Copyright@ 2017-2037 Www.163WenKu.Com  网站版权所有  |  资源地图   
    IPC备案号:蜀ICP备2021032737号  | 川公网安备 51099002000191号


    侵权投诉QQ:3464097650  资料上传QQ:3464097650
       


    【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。

    163文库