弋改珍

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

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

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

十多年來(lái)，人們對(duì)網(wǎng)絡(luò)編碼理論及其應(yīng)用越來(lái)越感興趣。該領(lǐng)域的研究還激勵(lì)了數(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ò)編碼”。通過(guò)研究多播場(chǎng)景編碼速率區(qū)域的特征化問(wèn)題，建立了最大流最小割定理，限制了網(wǎng)絡(luò)的最大容量，并提出了簡(jiǎn)化信息理論問(wèn)題求解的幾何框架和集合理論框架。

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

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

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

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

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

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

早在1998年，Li和Yeung首次定義了在網(wǎng)絡(luò)中多播信息的線性碼，該線性碼在節(jié)點(diǎn)處引入了信息守恒定律。因此，在線性編碼的特殊情況下，指派給網(wǎng)絡(luò)節(jié)點(diǎn)輸出信道的向量是指派給同一節(jié)點(diǎn)輸入信道向量的線性組合。此外，作者闡明最大流是每個(gè)非源節(jié)點(diǎn)收到的信息速率的上界，他們給出如何實(shí)現(xiàn)這個(gè)邊界和使用通用線性碼多播（Linear Code Multicast，LCM）實(shí)現(xiàn)多播的最優(yōu)解。對(duì)于有環(huán)網(wǎng)絡(luò)中的信息傳送問(wèn)題，作者建議由節(jié)點(diǎn)處的時(shí)隙編碼操作和時(shí)隙傳送信道組成的解決方案。解有環(huán)問(wèn)題的另一種方法是LCM的實(shí)現(xiàn)。在無(wú)環(huán)場(chǎng)景中，將一般LCM和擬陣論聯(lián)系在一起，證明了基本結(jié)果：如果向量空間足夠大，每個(gè)無(wú)環(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)出驗(yàn)證多播問(wèn)題可行性的一個(gè)代數(shù)框架，新框架完全是代數(shù)的，使得將代數(shù)的數(shù)學(xué)定理應(yīng)用到網(wǎng)絡(luò)編碼中成為可能。目標(biāo)是解決最普遍的網(wǎng)絡(luò)編碼問(wèn)題。

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

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

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

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

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

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

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

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

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

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

3 ? ?可能的未來(lái)方向

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

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

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

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

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

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

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

4 ? ?結(jié)語(yǔ)

首先，本文通過(guò)對(duì)部分網(wǎng)絡(luò)編碼理論相關(guān)文獻(xiàn)的調(diào)查，以網(wǎng)絡(luò)編碼技術(shù)的提出、線性網(wǎng)絡(luò)編碼、隨機(jī)網(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ò)編碼理論未來(lái)可能的研究方向。

[參考文獻(xiàn)]

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