




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、网络编码组员:代亮亮 徐杰 郭鑫 李文杰 胡怡 刘慧芳 张晓宇概念12应用3总结4目录原理概念12应用3总结4目录原理1、概念网络编码:通信网络中信息处理和传输理论研究上的重大突破。网络编码:融合了编码和路由转发的信息交换技术, 在传统存储转发的路由方法基础上, 通过允许对接收的多个数据包进行编码(如模二加、有限域 上的运算等)信息融合,增加单次传输的信息量, 以提高网络信息传输效率和整体性能核心:允许网络节点对传输信息进行编码处理经典信息论中的信息传输:单纯共享网络和链路资源,彼此独立。网络编码的起源与发展概念诞生:1998论文“ Network Information Flow Theor
2、y”1999 Yeung和Zhang发表的关于卫星通信的论文正式发表:2000网络编码理论的奠基之作:先锋论文“ NetworkInformationFlow”里程碑(2003): 香港中文大学讯息工程系的李硕彦教授、 杨伟豪教授、 蔡宁教授发表了论文“LinearNetworkCoding” 指出线性网络编码可以达到多播方式下的网络容量。Koetter和Medard提出网络编码的代数学(Algebra)框架, 即用抽象代数来解决线性网络编码的问题, 为研究网络编码提供了一个用力的数学工具 Sanders等提出具有多项式复杂度的线性信息流算法, 该算法属于集中式的码构造算法。Ho等提出随机网络
3、编码(RandomNetworkCoding,RNC), 属于分布式的码构造方法。基础知识:最大流最小割定理1/5割:网络中定点的一个划分,把网络中所有的顶点划分为两个顶点的集合S和T,其中源点s属于S,汇点t属于T,记为CUT(S,T)顶点集: S=1,2,3, T=4,5构成一个割框外是容量,框内是流量注:源点和汇点不能属于同一个顶点集合:如下就不能构成一个割基础知识:最大流最小割定理2/5s-t图:a 一个源点和一个汇点b 有向边,是从i到jc 每条边都有一个非负的权值d 容量cap(i,j)等于0,说明不存在边基础知识:最大流最小割定理3/5割边:如果一条弧的两个顶点分别属于顶点集S和
4、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的值等于割
5、CUT(S,T)的容量,那么f是一个最大流,CUT(S,T)是一个最小割。基础知识:最大流最小割定理4/5最大流最小割定理:任何网络中,最大流等于最小割的容量形象的比喻:水流管道的最大流量由最细的管子容量决定。网络的最大流量由最小割决定。基础知识:最大流最小割定理5/5概念12应用3总结4目录原理网络编码基本原理蝴蝶网络”(Butterfly Network)左图为“单信源二信宿”蝴蝶网络设各链路容量为1S:信源节点。 Y,Z:信宿节点。 其余为中间节点。由最大流最小割定理,该多播的最大理论传输容量为2。即理论上信宿Y和Z能够同时收到信源S发出的2个单位的信息,,也就是说能同时收到b1和b2。
6、图(a)图(b)网络编码基本原理网络编码基本原理网络编码的核心思想具备编码条件的网络节点A对接收到的信息进行一定方式的处理(编码) ,然后传输给下一级的网络节点BB再编码,然后传输给C。如此反复,直到所有经过处理后的信息都汇聚到信宿节点为止。在信宿节点,通过逆过程的操作(译码) ,即可译出信源发送的原始信息。目的: 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
7、各自有X,Y的信息,可以通过译码得到X,和YARXBRY网络编码基本原理概念12应用3总结4目录原理 协作通信通过网络节点协作的方式接收转发其他伙伴的信息到目的端,以获得系统的分集增益,从而对抗无线信道的各种衰落。 网络编码借助于融合了编码和路由的新思想,通过允许中间节点对来自不同链路的信息进行解码组合,利用数据包之间的相关性来解码,从而提升整个网络的性能。网络编码在无线协作通信中的应用背景与意义协作通信系统模型 结合网路编码思想与协作通信技术,以能更好的充分发挥网络编码技术在无线协作通信系统中的应用优势,进一步提高基于网络编码的无线协作系统性能.协作通信的分类放大转发(AF, Amplify
8、 and Forward) 在信道质量较差的情况下,AF会将噪声放大。解码转发 (DF,Decode and Forward) 在信道质量较差的情况下,DF中继无法正确解码。 两者都是信息的重复传输,信道利用率不高,造成资源浪费。编码协作(CC,Cooperation Coded) 提供比重复编码更高效的编码方式,从而带来更多的编码增益。但是中继点复杂度高,中继点信号处理时延增大,降低了时效性。编码协作(CC) CC协议是解码转发协作(DF)的进一步延伸,它改变DF策略的重复编码方式,通过两条不同的,相互独立的衰落信道来发送每个用户的信息码字的不同部分,从而提供更多的编码增益。无线网络编码分类
9、1.网络层网络编码2.物理层网络编码网络层网络编码 针对网络层编码技术,目前的一个研究重点是在实际的网络条件下,采样网络编码后的网络容量以及可以达到的网络容量的传输策略物理层网络编码 物理层网络编码提高了无线频谱的利用率,物理层网络编码技术目前的研究重点是怎样有效的从混合信号中分离出需要的信号。S1RS2D 传输时隙信息传输方向传输信息简要说明时隙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、码学方法存在一定的局限性 计算复杂度较大、 数据传输速率较低、 消息冗余较大分布式存储的维护最常用冗余数据的维护技术是复制和纠删码。当我们在利用纠删码对失效节点进行修复的时候,首先要将原始数据重建,然后将其用网络编码的方法进行编码,但是这样修复时数据的下载量远远多于节点的存储,即修复带宽远大于存储量。再生码两种常用的冗余数据维护技术在对数据节点进行修复时,需要消耗很大的下载带宽,于是产生了一种新型的技术再生码。实现了存储量与修复下载带宽的良好折中,部分还巧妙地结合了复制与纠删码的各自优点,保证了具有极高的节点成功修复的可能性。信息流图他们把节点修复的问题刻画为网络系统中普遍的单源多播问题,然后
12、把对分布式存储系统的分析化成对信息流图的分析再生码的一个定理对于任意 , 分布式存储系统中的点是可行的,它可以通过线性网络编码来实现。当 时,在信息理论上是不可能实现的。其理论界函数如下:其中对于给定的n,k,d,最小修复带宽的值为MSR和MBR网络编码理论在数据安全领域的应用网络编码理论在数据安全领域的应用传统的密码学方法存在一定的局限性 (1)计算复杂度较大 (2)数据传输速率较低 (3)消息冗余较大网络纠错码 网络编码的初衷在于提高网络的吞吐量,但是随着进一步研究发现它也是一种安全网络传输的好方式。然而在抗击拜占庭攻击时,我们不仅要能够检测出敌手对信息的恶意攻击,还要尽量能够做到对这些信
13、息的恢复,这就是网络纠错码.搭载窃听网络通信的模型网络通信的模型m:是消息本身k:是为了达到安全的随机数右图中红线是窃听集, 但是一个时间内只允许敌手窃听其中的一条, 这样接收节点T和T能够安全接收到信源传来的消息。网络编码理论在数据安全领域的应用 图3 Alice、Bob 和Eve的数据包X:表示Alice发出的原始消息块Z:表示攻击者Eve注入的错误消息块Y:表示经过篡改被Bob接收的消息块矩阵I、 L和T分别表示数据包X、 Y和Z的编码向量。图3是有线和无线网络的带有拜占庭攻击者的攻击模型, 为了简化符号,只考虑单信源单信宿的通信问题。相似于许多网络编码的算法, 这里每个体制都可以从单个
14、接收方的情形推广到多播通信。网络编码理论在数据安全领域的应用3种主要攻击模型(1)秘密共享模型 此模型假定Alice和Bob有一个低速率的秘密信道, Eve不知道秘密信道上的传输消息。考虑将消息经过网络编码后在网络上传输, Eve可以观察到所有除秘密信道之外的所有传输,也可以选择是否在他所控制的节点处在要传输的数据包中注入一些恶意数据到从而达到阻止Alice和Bob通信的目的。(2)万能攻击者模型 此模型中Eve除了在控制链接数目上受到一定限制外,是万能的、 无所不知的, Alice和Bob之间没有独立于Eve的秘密信道。(3)有限的窃听模型 在这个模型中, Eve 的窃听能力是有限制的, 只
15、能观察到至多 Z I 个传送的包。网络编码在p2p网络系统中的应用网络编码在p2p网络系统中的应用p2p系统简介p2p网络系统: P2P全称为:Peer-to-Peer,即对等网络或对等计算。主要采用非集中式的拓扑结构,可以应对集中式拓扑结构出现的过量存储负载、DOS(Denial of Service,拒绝服务)攻击,网络带宽限制等一些难以解决的问题。P2p网络系统发展的四种拓扑结构: 中心化拓扑、全分布式非结构化拓扑、全分布结构式拓扑、半分布式拓扑网络编码在p2p网络系统中的应用p2p系统简介p2p网络系统四种技术优势:非中心化:资源和服务分散在对等结点上,信息的交付直接在结点之间进行,无
16、需服务器介入,避免了可能的瓶颈。可扩展性:系统的资源和服务能力可以随着新用户的加入和服务需求的增加而提高。鲁棒性:即系统的健壮性,在抗异常和突发危险情况的能力。服务是分散在各对等结点上的,没有中心节点和特殊节点,某些节点出现异常或遭受攻击时,整个网络的影响很小,具有很强的自组织性和自愈性。 负载均衡:每个节点既是服务器又是客户机,同时因资源分布在多个节点,能更好实现整个网络的负载均衡。网络编码在p2p网络系统中的应用文件下载三种文件下载方式:无分代随机网络编码技术:优点是分块随机组合后,整个网络的分块分布均衡化,而且能够适应P2P系统的动态变化。 缺点是编码解码过程是在一个文件的所有分块之间进
17、行的,计算量大,系统开销过大,尤其是大文件分发时。分代网络编码方法:优点是解决无分代网络编码的问题。 缺点是节点的退出使得网络中已经不存在足够多线性无关的编码组合以解码得出某一代的原始分块,从而导致无法解除完整的文件;源节点不知如何从本代信息传输切换到下一代信息传输等。代间网络编码方法:优点:当本代集中的某一代没有足够多线性无关的编码块时,可以由本代集其他代的线性无关编码块来弥补。 缺点:无法单独成功解出某一代的原始数据。网络编码在p2p网络系统中的应用文件下载假设服务器需要传输文件给对等节点A,首先将服务器上的文件分解成n个文件块,B1Bk,然后应用随机网络编码,随机选择系数C1Cn,将线性
18、网络编码后的组合块E1=c1B1+c2B2cnBk传送给对等节点A,同理得出E2=C1B1+C2B2CnBk,该组合块来自其它对等节点或者服务器。然后对等节点A再随机选择编码系数C1、C2,对E1和E2进行线性操作,将操作的结果E3=C1E1+C2E2发送给对等节点B,对等节点B又传送给其它的对等节点。只要每一个对等节点收到足够多的线性无关组合,就可以通过解线性方程组译出原始文件块。无分代随机网络编码技术网络编码在p2p网络系统中的应用文件下载把传输的文件先分成多个代,每个代再分成一定数目的块,并且每代拥有的分块数目是固定的。网络编码和解码的过程只在同一代内进行,代与代之间编码过程是独立的。如
19、图所示,首先将文件分成m(m2)个代,每个代内再分成n(n2,nm)个文件分块。编码过程在代内进行,而且代与代之间的编码过程是彼此独立的。源节点首先对第一代内的文件执行无分代网络编码直到信宿可以正确译出第一代的所有信息,然后再在第二代内执行无分代网络编码信息传输,以此类推,直到传输完整个文件。分代网络编码方法网络编码在p2p网络系统中的应用文件下载首先把文件分代,代内再分组,然后把本代及其之前所有的代组合成一个代集,在代集内进行编码。代集之间编码过程是独立的。如图所示:首先把要发送的源文件分成m代,每代再分成k个块,本代及其之前所有的代构成代集,编码过程和解码过程都在代集内进行,并且代集之间彼
20、此独立。代间网络编码方法流媒体与文件下载的最大区别是前者要求边下载边播,而后者没有这个要求。目前基于p2p的实时流媒体系统中,根据覆盖网节点所构成的拓扑规划,分为单组播树拓扑、多组播树拓扑和网状拓扑三类。如上图所示现有p2p流媒体传输系统很多是基于分层编码实现的,其系统主要由两个模块组成:资源发现模块和资源传输模块。网络编码在p2p网络系统中的应用流媒体空间分层编码 实现不同大小图像的服务兼容性。先在原始图像中采样的方法得到一帧空间上低频分辨率的图像。从原始图像减去经过内插的抽样图像得到的差值图像,对差值图像再进行编码得到增强层。时间分层编码 为实现不同频率的视频服务兼容。其基本层和增强层具有
21、相同的空间分辨率和SNR。基本层图像进行运动估计时只能在基本层中选取,同理增强层也是。视频的精细分层 为支持信道特性多变的包交换网上多媒体应用和服务而提出网络编码在p2p网络系统中的应用流媒体分层编码网络编码在p2p网络系统中的应用流媒体资源发现模块 主要任务是协助新的节点找到自己感兴趣的流媒体文件的所在位置。 节点接入机制每一个节点有一个在整个系统中的全局唯一的标识,如IP地址,超级节点维护一个系统中其他节点的标识缓存。当新的节点A接入时,首先通过资源查找获得所需文件的伙伴节点列表。对于列表中的节点,A通过“三次握手”的机制与对方建立连接,并测试对方的可用带宽,A从所有的备选节点中选择合适的节点作为自己的上游节点,则此建立连接的过程得以完成,新节点获得稳定的伙伴节点,开始进行流媒体下载缓冲,进入稳定的播放阶段网络编码在p2p网络系统中的应用流媒体资源传输模块 目的是完成资源传输的任务分配,任务调度以及任务控制等内容。 在P2P文件传输系统中,流媒体被划分数据块,数据块中的数据又被分为多个数据包,并且使用可用度向量的概念来标识一个节点拥有数据块中的哪些数据包。P2P流媒体传输系统的资源传输模块分为请求数据、发送数据和接收数据三个相关联的部分。接收数据部分: 接收部分的主要任务是接收到数据后,按照一定的结构将数据存放在本地,并且
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 有色金属行业资源循环利用产业链产业链协同创新驱动因素分析报告
- 2025年婴幼儿配方食品中特殊维生素D配比研究与应用对儿童注意力集中效果研究报告
- 柔性制造系统2025年工业机器人应用成本效益分析与优化措施报告
- 消防水泵房课件素材图片
- 消防服务培训课件图片素材
- 2024-2025学年辽宁省锦州市高一(下)期末数学试卷(含答案)
- 2024-2025学年浙江省嘉兴市高二(下)期末数学试卷(含解析)
- 消防救援队伍作战安全课件
- 中国现代官职与古代官职
- 2025年佳木斯市抚远县中考数学对点突破模拟试卷含解析
- 浅析图书发行企业在新形势下的财务管理策略
- GB/T 6478-2015冷镦和冷挤压用钢
- GB/T 4604.1-2012滚动轴承游隙第1部分:向心轴承的径向游隙
- 2016众泰t600运动版原厂维修手册与电路图-使用说明
- 2023年卸油安全技术操作规程
- 武汉理工大学2023年349药学综合考研真题(回忆版)
- 干式工法楼地面(地暖+铺贴)施工工艺简介课件
- 白术栽培技术课件
- 实用而简洁的临终助念开示词
- ISO-IEC 27002-2022中文版完整详细
- C.0.3火灾自动报警系统施工过程检查记录
评论
0/150
提交评论