网络编码

出自 MBA智库百科(https://wiki.mbalib.com/)

　　网络编码是一种通过中继节点对接收到的信息进行编码来达到提高多播网络容量的技术。Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, Raymond W. Yeung在2000年首次提出网络编码的概念。

　　在传统的数据传输技术中，中继节点只负责数据的存储转发，而基于网络编码技术的网络的中继节点在具备传统中继功能的基础上，会根据网络编码规则将接收到的信息进行线性或非线性处理再进行传播，这种做法最直观的优势是减少了传输次数。利用图论中最大流最小割原理论证了网络编码可以达到网络最大信息流。

　　线性网络编码假设网络是有向的，执行线性网络编码时每个节点收到所有连入线路的数据后，再执行编码，然后把数据从连出线路发出。新的数据包括执行线性编码所用的系数以及合成后的数据。

　　随机线性网络编码可以取得更好的组播传输速率，较为实用。在实际网络中，节点会将来自连入线路的封包缓存起来，当节点需要发送封包时再将缓存的封包执行网络编码，然后发出。

　　例如节点A有2个上游节点X,Y，X向A发送了封包 {\displaystyle ((2,2,1),2x_{1}+2x_{2}+x_{3})} {\displaystyle ((2,2,1),2x_{1}+2x_{2}+x_{3})}( {\displaystyle 2x_{1}+2x_{2}+x_{3}} {\displaystyle 2x_{1}+2x_{2}+x_{3}}是数据体，（2,2,1）是对数据体执行线性编码时所用的系数）,Y向A发送了封包 {\displaystyle ((1,5,4),x_{1}+5x_{2}+4x_{3})} {\displaystyle ((1,5,4),x_{1}+5x_{2}+4x_{3})}。当A需要发送数据时，便把缓存的这两个封包取出来，随机选择2个系数（如2和1），获得新的数据体 {\displaystyle (2x_{1}+2x_{2}+x_{3})\times 2+(x_{1}+5x_{2}+4x_{3})\times 1=5x_{1}+9x_{2}+6x_{3}} {\displaystyle (2x_{1}+2x_{2}+x_{3})\times 2+(x_{1}+5x_{2}+4x_{3})\times 1=5x_{1}+9x_{2}+6x_{3}}和新的合成系数 {\displaystyle (2,2,1)\times 2+(1,5,4)\times 1=(5,9,6)} {\displaystyle (2,2,1)\times 2+(1,5,4)\times 1=(5,9,6)}。所以A就把合成后的数据体 {\displaystyle 5x_{1}+9x_{2}+6x_{3}} {\displaystyle 5x_{1}+9x_{2}+6x_{3}}连同合成系数(5,9,6)，向下游节点发送出去。