網路編碼

出自 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)，向下游節點發送出去。