鐘嬙

摘要：網(wǎng)絡(luò)編碼是指在網(wǎng)絡(luò)的中間節(jié)點(diǎn)對信息進(jìn)行恰當(dāng)?shù)鼐幋a處理，而非傳統(tǒng)的只對信息進(jìn)行存儲轉(zhuǎn)發(fā)的方案。該文主要介紹了網(wǎng)絡(luò)編碼的工作原理和實現(xiàn)方法，總結(jié)了網(wǎng)絡(luò)編碼的主要優(yōu)缺點(diǎn)，對現(xiàn)階段網(wǎng)絡(luò)編碼的一些主要應(yīng)用作了介紹和探討，并對以后的研究工作進(jìn)行了展望。

關(guān)鍵詞:網(wǎng)絡(luò)編碼;信息流;最大流最小割;組播;吞吐量

中圖分類號：TP393文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2012)16-3836-04

A Survey of Network Coding

ZHONG Qiang

(China Mobile Sichuan Branch,Chengdu 610041,China)

Abstract：Network Coding is employing proper coding at the intermediate nodes of a communicate network, rather than just simply repli cating and routing。In this paper, we study the problem with the principles and implements of network coding, and introduced its main advantages and disadvantages, research progress and main applications. In the end, the prospect and research directions of network coding are stated.

Key words: network coding; information flow; Max-flow Min-cut; multicast; throughput

在傳統(tǒng)的計算機(jī)通信網(wǎng)絡(luò)中，對數(shù)據(jù)的編碼，無論是壓縮還是加密，只發(fā)生在信源處，對數(shù)據(jù)的解碼只發(fā)生在接收端，中間節(jié)點(diǎn)只對數(shù)據(jù)進(jìn)行存儲轉(zhuǎn)發(fā)，不對其本身進(jìn)行加工處理。然而2000年，香港中文大學(xué)的Ahlswede等人提出的Network Coding的理論，徹底顛覆了傳統(tǒng)的數(shù)據(jù)傳輸方式。他們的研究表明，如果允許網(wǎng)絡(luò)中間節(jié)點(diǎn)對傳輸?shù)男畔⑦M(jìn)行恰當(dāng)?shù)鼐幋a處理，而非僅做存儲轉(zhuǎn)發(fā)，則基于該方式的網(wǎng)絡(luò)多播可以突破傳統(tǒng)的傳輸容量，達(dá)到理論上的最大值。相對于數(shù)據(jù)在信源節(jié)點(diǎn)處的編碼，我們把這種中間節(jié)點(diǎn)對數(shù)據(jù)信息進(jìn)行的編碼操作稱為網(wǎng)絡(luò)編碼。

3.4信息安全等領(lǐng)域

應(yīng)用網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)中傳輸?shù)男畔⒈旧硎墙?jīng)過編碼轉(zhuǎn)換的，因此即使不經(jīng)過復(fù)雜的額外的加密操作，攻擊者通過信息攫取來還原原始數(shù)據(jù)的可能性也大大降低。網(wǎng)絡(luò)編碼很應(yīng)用到信息安全領(lǐng)域，為新的加密算法提供了新的研究方案與思路。

現(xiàn)階段，在國外，麻省理工大學(xué)、普林斯頓大學(xué)等許多著名大學(xué)，以及微軟研究院和AT&T香農(nóng)信息實驗室等多家大型IT公司的科研中心都在積極地研究網(wǎng)絡(luò)編碼的理論及應(yīng)用；在國內(nèi)，香港中文大學(xué)、清華大學(xué)和西安電子科技大學(xué)等高等學(xué)府也在網(wǎng)絡(luò)編碼領(lǐng)域展開了深入的研究工作。網(wǎng)絡(luò)編碼已深入到編碼學(xué)、信息學(xué)、無線網(wǎng)絡(luò)、分布式存儲、網(wǎng)絡(luò)安全、通信系統(tǒng)和內(nèi)容傳輸?shù)阮I(lǐng)域中。

經(jīng)過十幾年的發(fā)展,網(wǎng)絡(luò)編碼在理論和應(yīng)用上都取得了一定的研究成果,但仍然存在一些尚未解決的問題和有待完善的地方：如何降低網(wǎng)絡(luò)編碼在設(shè)計和實現(xiàn)上的復(fù)雜性，提高實時處理速度；如何完善網(wǎng)絡(luò)編碼的安全問題；如何將目前的單源網(wǎng)絡(luò)編碼推廣到多源的一般性網(wǎng)絡(luò)中；如何實現(xiàn)有環(huán)網(wǎng)絡(luò)的編碼；如何更好地將網(wǎng)絡(luò)編碼與相關(guān)領(lǐng)域的技術(shù)融合等等都有待進(jìn)一步的研究。

在未來的發(fā)展中,網(wǎng)絡(luò)編碼的研究和應(yīng)用領(lǐng)域勢必繼續(xù)擴(kuò)大,必將更好地促進(jìn)通信網(wǎng)絡(luò)的發(fā)展，給信息論、編碼理論等相關(guān)領(lǐng)域帶來前所未有的深遠(yuǎn)影響。

[1] Rudolf Ahlswede,Ning Cai,Shuo-Yen Robert Li,et al. Network information flow[J].IEEE Trans.Inform.Theory,2000,46(4):1204-1216.

[2] Li S Y R,Yeung R W.Linear network coding[J].IEEE Trans Inform Theory,2003,49(2):371-381.

[3] Li Fan.The Principle and Application of Network Coding[J].Journal of Chendu Textile College,2012,29(1):9-12.

[4] Li S Y R, Cai N,Yeung R W.On Theory of Linear Network Coding[C]. Adelaide, Australia:2005 IEEE International Symposium on Infor? mation Theory (ISIT 2005),2005,1.

[5] Koetter R,Medard M.An algebraic approach to network coding[J].IEEE/ACM Tranm On Networking,2003,11(5):782-795.

[6] Sanders P,Egner S,Tolhuizen L.Polynomial time algorithms fornetwork information flow[J].Proceedings of the fifteenth annual ACM sympo? sium on Parallel algorithms and architectures,2003:286-294.

[7] Ho T,Medard M,Shi J,et al.On randomized network coding[C].41 st Annual Allerton Conference on Communication, Control and Comput? ing,2003.

[8] Koeter R, Medard M. An algevraic approach to network coding[J].IEEE ACM Trans Networking 2008,11(5):782-795.

[9] Sanders P, Egner S, Tolhuizen L. Polynomial time algorithms for network information folw[C]//proc 15th ACM Symposium on Parallel Al? gorithms and Architectures,2009.

[10] Medard M,Effros M,Ho T,et al.On coding for non-multicast networks[C]//41st Annual Allerton Conference on Communication Control and Computing, Monticello, IL, 2003.

[11] Dougherty R,Freiling C,Zeger K.Insufficiency of linear coding in network information flow[J].IEEE Trans Inf Theory 2005,51(8):772-783.

[12] Ho T, Medard M, Shi J, et al. On Randomized Network Coding[C]//41st Annual Allerton Conference on Communication Control and Com? puting,2010.