网络编码只是概述.ppt
CN 1,网络编码知识概述,报告人：后学知 导师：张大方 何施茗,大纲,一 研究背景二 问题阐述三 我的工作四 具体算法五 仿真结果六 参考文献,CN 2,研究背景,近年来，随着对无线网络的逐渐普及，对于无线网络的性能的研究也越来越频繁。,CN 3,研究背景,网络编码(Network Coding)是进入21 世纪后通信领域的一项重大突破,它融合了编码和路由的概念,通过允许对来自不同链路的信息进行编码组合,使得网络节点既实现路由功能又实现编码功能。在这种全新的体系结构下,网络性能可以达到最大流传输的理论极限。下面是几种很经典的网络编码算法,CN 4,具体算法,copesc,CN 5,具体算法,COPE主要包括3种主要技术(a)Opportunistic Listening 1 无线网络是广播信道 2 每个节点都有机会偷听到包并在一个有限的时间内进行保存 3 保存包后，每个节点广播接收报告给它邻居节点,CN 6,具体算法,CN 7,CN 7,(b)Opportunistic Coding,具体算法,ANC（Analog Network Coding）,CN 8,具体算法,CN 9,(b)Opportunistic Coding多重单播流在一起编码，但是解码时会分成不同流算法保证所有编码得包的下一跳节点能够解码相对的原始包设有n个包p1,.,pn到n个下一跳r1,.,rn，一个节点能够XORn个包前提是每个下一跳ri有n 1 个包pj 且 j=i,具体算法,CN 10,(c)Learning Neighbor State由于网络拥塞，接收报告可能丢失或者延时，当接收报告到达时也许节点已经做出了非最佳选择我们改变无线路由协议来采用猜测的方法来估计对方节点有什么包当节点计算错误而无法解码包时则相关的未编码包重新发送。,具体算法,CN 11,Coding Gain定义 不用COPE传送的次数与用COPE传送的次数的比值。理论上最大值为2实际因为机会编码，传输丢失，过大的头使实际值小于2,具体算法,CN 12,CN 12,具体算法,CN 13,CN 13,Coding+MAC Gain带宽平均分配，因此瓶颈链路的包被丢弃。Coding+MAC的最大值无限。,具体算法,CN 14,Packet Coding Algorithm(1)我们遵循包从不延时的理论，在节点队列头的包检测是否有可以异或的包有则异或，没有也不等待这样的包到来。(2)COPE优先选择异或长度相近的包(3)COPE不会把具有相同下一跳的包编码在一起，因此我们只要考虑具有不同下一跳的包。,具体算法,CN 15,保证找到合适的包关键在于维持一大一小两个虚拟队列。从虚拟队列的头开始找以免乱序 乱序问题需要减少。主要有两个原因1 我们编码要找合适的包。这个影响其实很小。2包丢失导致重传，这个为主要原因。我们解决这个问题在接收端。最后要保证邻居节点能够解码出他的未编码的包。,具体算法,CN 16,每个节点维持以下的数据结构1 每个节点输出队列按照先入先出转发数据。2 对于每个邻居，每个节点维持两个虚拟电路，一个为大包，一个为小包3每个节点维持一个哈希表，表明每个节点拥有包的可能性。,具体算法,CN 17,Packet Decoding每个每个节点维持一个包池，用来保存每个未编码包的复制件。当一个节点收到一个由N各未编码的包组成的编码包，然后一个一个检查ID，然后再包池了检查相应的包。最后进行异或运算得到原始包。,具体算法,CN 18,Pseudo-broadcastCOPE不用broadcast模式因为可靠性差并且缺少回退机制我们选用pseudo-broadcast来解决这个问题，它借用了单播的可靠性和回退机制。这个方法根据目的节点MAC地址和XOR头来鉴定包的下一跳是否是本节点，如果不是并且没收到源节点会重发直至确认或者超时,具体算法,CN 19,Hop-by-hop ACKs and Retransmissions(a)Why hop-by-hop acks1包有几个下一跳在其中一些下一跳可能丢失2 COPE没有足够的信息来获取下一跳的信息来解码,具体算法,CN 20,(b)Asynchronous Acks and Retransmissions同步确认对于编码得包来说效率低下COPE对于编码包采用异步确认。一旦确认丢失进行重传。,具体算法,CN 21,Preventing TCP Packet Reordering异步确认会导致包乱序，使被TCP认为是拥塞的信号。COPE采用一个顺序代理来解决乱序问题代理检查序号如果是连续的则让包进入传输层，如果序号有裂缝则保留这个区域直到重发的包把序号填满，直到延时,具体算法,CN 22,CN 22,Packet Format,CN 23,CN 23,Control Flow,CN 24,具体算法,ZigZag Decoding,24,AP,Alice,Bob,Pa,1,3,Pa,1,3,Pb,2,4,Pb,4,2,1st collision,2nd collision,0,Can reconstruct both packets Pa and Pb!,CN 25,Collision!,Alice,Bob,CN 26,Alice,Bob,More Collisions!,Retransmissions,Cant get any useful connections,CN 27,发生碰撞时，ZIGZAG能达到鱼不碰撞时相同的性能，而没有碰撞时ZIGZAG表现像经典的802.11的接收者。802.111协议中用户在没收到确认或超时的前提下重新发送数据包很可能再次碰撞。2用户每次发送经历个随机时间，因此碰撞在开始于一个随机的bit位。,CN 28,CN 29,Pa,Pb,Pa,Pb,CN 30,1,1 2,1,CN 31,1,2,1,1 2,CN 32,1,2,2,3,1 2,CN 33,1,2,4,3,3,1 2,CN 34,1,2,4,4,3,5,1 2,CN 35,1,6,3,5,5,2,4,1 2,CN 36,1,6,6,2,4,3,5,7,1 2,CN 37,1,6,8,2,4,3,5,7,7,CN 38,ZIGZAG用一种新颖的方法解决了干涉问题。,CN 39,但是zigzag却可以在最佳发送速率下发送包。经过试验证明采用ZIGZAG的算法，在部分或全部发生隐藏终端的情况下丢包率从72.6%下降到0.7%。,CN 40,CN 41,CN 42,1 如何发现发生碰撞？,Packets start with known preamble,AP correlates known preamble with signal,Correlation,Time,Preamble Correlation Detect collision and the value of Works despite interference because correlation with an independent signal is zero,CN 43,CN 44,1 先解码出1段。即D1 D那一段。2在1段中重新编码得到1段，再减去第二个冲突，从而得到2段反复执行这个操作从而解码出两段,CN 45,AP采用后向解码和前向解码相结合，估计出两个值，来减少整体错误。AP在每个字节取具有更高可信度的值,CN 46,向后兼容性,CN 47,也可解码三个碰撞的包,CN 48,研究背景,Chorus,Pa,b,c,Pb,b,a,a,Head packetP1,tail packet P2,S=A+B,谢谢！,CN 49,
