網絡編碼理論研究綜述

弋改珍

摘 ? 要：文章通過對部分網絡編碼理論相關文獻的調查，以網絡編碼技術的提出、線性網絡編碼、隨機網絡編碼、卷積碼為主線，研究了網絡編碼理論的發展和研究成果。在前期理論研究的基礎上，根據現有的研究資料，總結了網絡編碼理論未來可能的研究方向。

關鍵詞：網絡編碼;線性網絡編碼;隨機線性網絡編碼;卷積網絡碼

Shannon[1]《通信的數學理論》一文的發表，使信息論科學誕生，開始了數字通信，通過網絡傳遞信息。2000年，開創性文章《Network information flow》通過介紹信息流概念，證明信息的組合可以提高網絡的容量，優于路由所能達到的容量，并將現有網絡中的路由機制—存儲轉發，作為一個特例，誕生了一種新的研究領域，即網絡編碼。它允許網絡中間節點對輸入信息執行編碼操作，接收節點采用編碼理論進行解碼，以此提高網絡吞吐量。

十多年來，人們對網絡編碼理論及其應用越來越感興趣。該領域的研究還激勵了數學工具（編碼輪、代數、擬陣論、幾何、圖論、組合學等）的綜合應用，產生了今天的網絡編碼。

1 ? ?網絡編碼理論研究線路

Ahlswede等[2]首次提出提高網絡吞吐量的新的研究領域—“網絡編碼”。通過研究多播場景編碼速率區域的特征化問題，建立了最大流最小割定理，限制了網絡的最大容量，并提出了簡化信息理論問題求解的幾何框架和集合理論框架。

對于網絡編碼框架的研究，Li等[3]利用有限域中選取的系數對信息進行線性組合，采用線性碼組播，得到最優的網絡碼，從而提出了有向無環圖的最大流最小割的最優解，開始了確定性網絡編碼的理論框架的概念。Koetter等[4]通過將代數幾何與矩陣論連接起來，為構建確定性網絡編碼理論框架，開發了一種完整的代數框架。該代數框架為隨機線性網絡編碼奠定了堅實的基礎。

在研究有向無環網絡環境中網絡編碼的基礎上，Li等[5]分析了網絡編碼應用于無向網絡中的行為和優勢;同時提出在有向有環圖中，卷積網絡編碼是更好的解決方案。

網絡編碼的算法實現是使網絡編碼理論應用與實際的重要前提。算法的復雜度受網絡編碼所需的有限域大小的影響，并依賴于通信中接收者的數量。影響復雜度的其他因素還有邊數和源的傳送速率。組合學和圖論中的許多工具的應用有助于降低復雜性算法的設計。

2 ? ?網絡編碼理論的發展

在網絡編碼概念和框架的基礎上，研究者進一步在編碼實現算法、有限域大小、隨機線性網絡編碼、卷積碼和多播問題可解性等方面進行了研究，取得了豐碩成果，進一步完善了網絡編碼在實際中應用的理論基礎。

2.1 ?線性網絡編碼

早在1998年，Li和Yeung首次定義了在網絡中多播信息的線性碼，該線性碼在節點處引入了信息守恒定律。因此，在線性編碼的特殊情況下，指派給網絡節點輸出信道的向量是指派給同一節點輸入信道向量的線性組合。此外，作者闡明最大流是每個非源節點收到的信息速率的上界，他們給出如何實現這個邊界和使用通用線性碼多播（Linear Code Multicast，LCM）實現多播的最優解。對于有環網絡中的信息傳送問題，作者建議由節點處的時隙編碼操作和時隙傳送信道組成的解決方案。解有環問題的另一種方法是LCM的實現。在無環場景中，將一般LCM和擬陣論聯系在一起，證明了基本結果：如果向量空間足夠大，每個無環網絡上存在通用LCM。隨后，在2003年，Yeung和Cai提供了描述的結果，并首次描述了線性網絡編碼的理論框架，幾年之后，他們定義了一般線性網絡碼的線性多播、線性廣播和線性分散的概念。隨后，Yeung又解釋了線性分散和一般網絡編碼之間的關系，也找到與碼的基域大小的關系。2008年，Yeung給出網絡編碼理論基礎的完整定義。

不同于Cai和Yeung的研究思路，2001年，Koetter等推導出驗證多播問題可行性的一個代數框架，新框架完全是代數的，使得將代數的數學定理應用到網絡編碼中成為可能。目標是解決最普遍的網絡編碼問題。

2003年，Ho等人提出解決線性網絡編碼場景中多播問題的兩種方法：（1）關于網絡流的方法。（2）使用Edmonds矩陣行列式價差二部圖是否完美匹配，在計算中沒有涉及矩陣的乘積和逆變換，簡化了計算復雜度。Koetter等利用之前的結果開始了關于網絡編碼的隨機化方法的研究，并提出了一個更好的、新的上界。

在實現方面，Jaggi等對首次提出的構造通用LCM的算法進行了獨立修改和開發，使新的LCM在計算上更加高效。此外，新算法對基域大小的閾值比前一種算法更低，最初提出該算法用于構建線性多播，但也適用于線性廣播。后來，他們實現了多播網絡碼構造的多項式時間算法，為有向無環圖中的線性網絡編碼提供了確定性多項式時間算法和隨機算法。

2004年，Koetter等發現了線性網絡編碼與線性系統理論之間的聯系，特別是與圖上編碼理論的聯系。

2.2 ?隨機線性網絡編碼

2003年，Ho定義了一種多播的隨機網絡編碼方法，其中節點使用獨立、隨機選自某有限域的編碼系數，在輸出信道上傳送輸入信息的線性組合。然而，在接收端，解碼器需要源信息的全部線性組合。在這種新的方法中，作者允許網絡編碼適用于拓撲未知或變化的網絡。此外，通過隨機化方法，可以得到一個失效概率，通過增加有限域的維數來任意減小該概率。并計算了編碼成功概率的一個下界。2004年，Ho又證明了分布式隨機網絡碼的錯誤概率取決于某些錯誤成分，并且提供了隨機網絡編碼理論的完整描述。這些文章描述了與二部匹配和隨機網絡編碼的聯系，推廣了任意相關源情況下的Slepian-Wolf錯誤指數，并展示了應用隨機網絡編碼的好處。隨機線性網絡編碼的提出為網絡編碼的實現、應用與發展提供了堅實的基礎。

2.3 ?卷積網絡碼和有環網

Fragouli使用子樹分解的方法，建議以分散形式實現網絡編碼的確定性算法，并將圖論中的著色問題與網絡編碼相結合，利用圖的著色算法設計了網絡編碼算法。這些成果，為尋找網絡編碼與卷積碼之間的聯系提供了基礎。在此基礎上，作者設計了網絡編碼的信息流分解算法。在2006年，Fragouli通過信息流分解技術，找到了一種降低網絡編碼問題維數的方法，提出了一種基于源和接收者數量實現子樹圖設計的算法。最后，分析了網絡編碼和卷積碼之間的聯系。此外，Fragouli深入研究了網絡編碼與卷積碼的關系，提出了一種簡化的循環網絡處理方法。Erez提出了一種與分組網絡碼相似的卷積碼算法，并對其開銷和解碼復雜度進行了分析，該算法將網絡編碼推廣到有環網絡。

2005年，Erez提出了一種能夠在多項式時間內實現有環網絡上最優網絡碼多播算法，并對該算法進行了完整的描述。2010年，對前期結果進行了增強和充分解釋。

2006年，Li和Yeung分別使用與局部編碼核和全局編碼核相關的有限域上的有理冪級數和向量有理冪級數定義了卷積網絡編碼。此外，還定義了卷積多播問題，并解釋了編碼和解碼算法。

針對多源多播情況，Barbero等提出了有環網絡中網絡編碼算法。事實上，這種算法可以在任何類型的網絡上運行，比如無環網絡和有環網絡，作者證明它可以在多項式時間內運行。

3 ? ?可能的未來方向

網絡編碼是一個新的研究領域，涉及許多不同的領域，這一事實已經引起了研究領域的廣泛關注。可能的潛力和涉及廣泛的研究領域，使得網絡編碼的未來不可估量，也很難預測。另外，網絡編碼技術研究涉及其他領域。在最新研究成果的基礎上，未來可能的研究方向有以下幾個。

（1）需要進一步簡化網絡編碼算法的復雜性，分析系數選取的域的大小。

（2）網絡編碼的理論框架還需進一步的更新和完善。

（3）可變速率網絡編碼有許多潛力，也是值得深入研究的課題。

（4）有環網絡中的卷積網絡編碼有待進一步完善。

（5）利用信息論幾何框架和擬陣理論，在研究網絡編碼容量域和網絡編碼極限的過程中，仍存在一些未解決的問題。

（6）網絡編碼技術付諸實施，還需要一個領域的研究與完善，即網絡編碼的安全領域研究。

4 ? ?結語

首先，本文通過對部分網絡編碼理論相關文獻的調查，以網絡編碼技術的提出、線性網絡編碼、隨機網絡編碼、卷積碼為主線研究了網絡編碼理論的發展和研究成果。目的是解釋網絡編碼理論及其應用，使感興趣的讀者參與網絡編碼技術的研究。其次，討論網絡編碼技術涉及的數學基礎，為歷屆網絡編碼理論奠定了基礎。最后，在前期理論研究的基礎上，建議了網絡編碼理論未來可能的研究方向。

[參考文獻]

[1]SHANNON C E.A mathematical theory of communication[J].Bell Labs Technical Journal，1948（4）：379-423.

[2]AHLSWEDE R，CAI N，LI S Y R，et al.Network information flow[J].IEEE Transactions on Information Theory，2000（4）：1204-1216.

[3]LI S Y R，YEUNG R W，CAI N.Linear network coding[J].IEEE Transactions Information Theory，2003（2）：371-381.

[4]KOETTER R，MEDARD M.An algebraic approach to network coding[J].IEEE/ACM Transactions on Networking，2003（5）：782-795.

[5]LI Z，LI B.Network coding in undirected networks[C].Princeton：Conference on Information Sciences & Systems，2004.