網(wǎng)絡(luò)編碼理論研究綜述

弋改珍

摘 ? 要：文章通過對部分網(wǎng)絡(luò)編碼理論相關(guān)文獻的調(diào)查，以網(wǎng)絡(luò)編碼技術(shù)的提出、線性網(wǎng)絡(luò)編碼、隨機網(wǎng)絡(luò)編碼、卷積碼為主線，研究了網(wǎng)絡(luò)編碼理論的發(fā)展和研究成果。在前期理論研究的基礎(chǔ)上，根據(jù)現(xiàn)有的研究資料，總結(jié)了網(wǎng)絡(luò)編碼理論未來可能的研究方向。

關(guān)鍵詞：網(wǎng)絡(luò)編碼;線性網(wǎng)絡(luò)編碼;隨機線性網(wǎng)絡(luò)編碼;卷積網(wǎng)絡(luò)碼

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

十多年來，人們對網(wǎng)絡(luò)編碼理論及其應(yīng)用越來越感興趣。該領(lǐng)域的研究還激勵了數(shù)學(xué)工具（編碼輪、代數(shù)、擬陣論、幾何、圖論、組合學(xué)等）的綜合應(yīng)用，產(chǎn)生了今天的網(wǎng)絡(luò)編碼。

1 ? ?網(wǎng)絡(luò)編碼理論研究線路

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

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

在研究有向無環(huán)網(wǎng)絡(luò)環(huán)境中網(wǎng)絡(luò)編碼的基礎(chǔ)上，Li等[5]分析了網(wǎng)絡(luò)編碼應(yīng)用于無向網(wǎng)絡(luò)中的行為和優(yōu)勢;同時提出在有向有環(huán)圖中，卷積網(wǎng)絡(luò)編碼是更好的解決方案。

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

2 ? ?網(wǎng)絡(luò)編碼理論的發(fā)展

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

2.1 ?線性網(wǎng)絡(luò)編碼

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

不同于Cai和Yeung的研究思路，2001年，Koetter等推導(dǎo)出驗證多播問題可行性的一個代數(shù)框架，新框架完全是代數(shù)的，使得將代數(shù)的數(shù)學(xué)定理應(yīng)用到網(wǎng)絡(luò)編碼中成為可能。目標(biāo)是解決最普遍的網(wǎng)絡(luò)編碼問題。

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

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

2004年，Koetter等發(fā)現(xiàn)了線性網(wǎng)絡(luò)編碼與線性系統(tǒng)理論之間的聯(lián)系，特別是與圖上編碼理論的聯(lián)系。

2.2 ?隨機線性網(wǎng)絡(luò)編碼

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

2.3 ?卷積網(wǎng)絡(luò)碼和有環(huán)網(wǎng)

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

2005年，Erez提出了一種能夠在多項式時間內(nèi)實現(xiàn)有環(huán)網(wǎng)絡(luò)上最優(yōu)網(wǎng)絡(luò)碼多播算法，并對該算法進行了完整的描述。2010年，對前期結(jié)果進行了增強和充分解釋。

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

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

3 ? ?可能的未來方向

網(wǎng)絡(luò)編碼是一個新的研究領(lǐng)域，涉及許多不同的領(lǐng)域，這一事實已經(jīng)引起了研究領(lǐng)域的廣泛關(guān)注?？赡艿臐摿蜕婕皬V泛的研究領(lǐng)域，使得網(wǎng)絡(luò)編碼的未來不可估量，也很難預(yù)測。另外，網(wǎng)絡(luò)編碼技術(shù)研究涉及其他領(lǐng)域。在最新研究成果的基礎(chǔ)上，未來可能的研究方向有以下幾個。

（1）需要進一步簡化網(wǎng)絡(luò)編碼算法的復(fù)雜性，分析系數(shù)選取的域的大小。

（2）網(wǎng)絡(luò)編碼的理論框架還需進一步的更新和完善。

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

（4）有環(huán)網(wǎng)絡(luò)中的卷積網(wǎng)絡(luò)編碼有待進一步完善。

（5）利用信息論幾何框架和擬陣?yán)碚?，在研究網(wǎng)絡(luò)編碼容量域和網(wǎng)絡(luò)編碼極限的過程中，仍存在一些未解決的問題。

（6）網(wǎng)絡(luò)編碼技術(shù)付諸實施，還需要一個領(lǐng)域的研究與完善，即網(wǎng)絡(luò)編碼的安全領(lǐng)域研究。

4 ? ?結(jié)語

首先，本文通過對部分網(wǎng)絡(luò)編碼理論相關(guān)文獻的調(diào)查，以網(wǎng)絡(luò)編碼技術(shù)的提出、線性網(wǎng)絡(luò)編碼、隨機網(wǎng)絡(luò)編碼、卷積碼為主線研究了網(wǎng)絡(luò)編碼理論的發(fā)展和研究成果。目的是解釋網(wǎng)絡(luò)編碼理論及其應(yīng)用，使感興趣的讀者參與網(wǎng)絡(luò)編碼技術(shù)的研究。其次，討論網(wǎng)絡(luò)編碼技術(shù)涉及的數(shù)學(xué)基礎(chǔ)，為歷屆網(wǎng)絡(luò)編碼理論奠定了基礎(chǔ)。最后，在前期理論研究的基礎(chǔ)上，建議了網(wǎng)絡(luò)編碼理論未來可能的研究方向。

[參考文獻]

[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.