網絡編碼淺析

山東省招遠市阜山鎮廣播電視站 李寶杰

一、什么是網絡編碼

網絡編碼，是網絡中的節點將接收到的信息進行編碼后再轉發出去的多點傳送技術，是一種融合了路由和編碼的信息交換技術，它的核心思想是在網絡中的各個節點上對各條信道上收到的信息進行線性或者非線性的處理，然后轉發給下游節點，中間節點扮演著編碼器或信號處理器的角色。根據圖論中的最大流-最小割定理，數據的發送方和接收方通信的最大速率不能超過雙方之間的最大流值(或最小割值)，如果采用傳統多播路由的方法，一般不能達到該上界。R Ahlswede等人以蝴蝶網絡的研究為例，指出通過網絡編碼，可以達到多播路由傳輸的最大流界，提高了信息的傳輸效率，從而奠定了網絡編碼在現代網絡通信研究領域的重要地位。

二、網絡編碼方案

網絡編碼方案可分為線性和非線性兩種，其中線性方法的編碼和解碼都相對簡單，因此，一般都傾向于采用線性方法。Li指出在有向網絡中，如果一個網絡編碼問題有解，則一定有線性解。從理論上保證了線性算法的有效性。線性組合要求網絡節點具有更高的計算能力，然而根據摩爾定律，隨著處理成本的降低，網絡的“瓶頸”逐漸轉向業務所需的更高的帶寬支持和服務質量(QoS)保證。網絡編碼實際上是用節點處理能力換取更高的網絡效率。

（一）編碼過程

線性網絡編碼是將節點傳送信息線性映射到一個有限域內，利用線性關系實現編譯碼過程。假設每個信息數據包為L比特，當它與要組合的數據包長度不同較短的信息附加額外一串“0”，將包中的s個連續比特組成域上的一個符號，則一個包中包含L/s個符號。在線性編碼下，運用乘法和加法運算，使從節點發出去的數據為該節點接受到信息的線性組合。假設一個源或多個源產生的原始數據包含信息為M1.......Mn，則在線性網絡編碼中傳輸的數據可表示為線性網絡編碼是將節點傳送信息線性映射到一個有限域內，利用線性關系實現編譯碼過程。假設每個信息數據包為L比特，當它與要組合的數據包長度不同時，較短的信息附加額外一串“0”，將包中的s個連續比特組成域上的一個符號，則一個包中包含L/s個符號。在線性編碼下，運用乘法和加法運算，使從節點發出去的數據為該節點接收到信息的線性組合。

（二）解碼過程

解碼需要求解一組線性方程。實際中，可以應用高斯消去的方法：節點存貯編碼向量以及編碼之后的結果，以行向量的形式，存儲在所謂解碼矩陣中。最初，解碼矩陣中只包含未經該節點編碼的包以及與之相對應的編碼向量(如果有的話)，否則為空。當接收到一個已編碼包后，會從中抽取它的編碼向量以及編碼結果，放入到解碼矩陣中。解碼矩陣會經過等價變換變成行階梯型，最終變成行最簡型。所收到的某一個包如果可以增加矩陣的秩，則稱之為更新包，如果所收到的包是非更新的，它可以通過等價變換變為全零，從而可以忽略。當解碼矩陣變換成最簡型后，方程組得解。這種情況發生在當接收到n個線性獨立的編碼向量之后。

三、總結

網絡編碼(Network Coding)是進入21世紀后通信領域的一項重大突破，它融合了編碼和路由的概念，通過允許對來自不同鏈路的信息進行編碼組合，使得網絡節點既實現路由功能又實現編碼功能.網絡編碼的應用可以改善網絡性能，甚至可以改變網絡結構、改變網絡協議設計方法，可以說網絡編碼正在給現有的網絡帶來革命性的變化。

[1]無線網絡編碼綜述[D].復旦大學計算機科學技術學院.

[2]網絡編碼中的優化問題研究[D].華中科技大學電子與信息工程系.

[3]無線自組織網絡的編碼技術[D].北京郵電大學電信工程學院.