資源描述:
《網(wǎng)絡(luò)編碼研究綜述new》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、小型微型計算機系統(tǒng)2008年4月第4期JournalofChineseComputerSystemsVol129No.42008網(wǎng)絡(luò)編碼研究綜述陶少國,黃佳慶,楊宗凱,喬文博,熊志強(華中科技大學(xué)電子與信息工程系智能互聯(lián)網(wǎng)技術(shù)湖北省重點實驗室,湖北武漢430074)E2mail:taoshaoguo@gmail.com摘要:網(wǎng)絡(luò)編碼是通信網(wǎng)絡(luò)中信息處理和傳輸理論研究上的重大突破,其核心思想是允許網(wǎng)絡(luò)節(jié)點對傳輸信息進行編碼處理.運用網(wǎng)絡(luò)編碼能夠提升網(wǎng)絡(luò)吞吐量、均衡網(wǎng)絡(luò)負載和提高網(wǎng)絡(luò)帶寬利用率等.本文介紹網(wǎng)絡(luò)編碼的基本原理以及主要
2、優(yōu)缺點,歸納了網(wǎng)絡(luò)編碼的主要實現(xiàn)算法和機制,總結(jié)了網(wǎng)絡(luò)編碼的幾種典型應(yīng)用,最后討論了網(wǎng)絡(luò)編碼進一步的研究方向.關(guān)鍵詞:網(wǎng)絡(luò)編碼;隨機網(wǎng)絡(luò)編碼;信息流;多播中圖分類號:TP393文獻標識碼:A文章編號:100021220(2008)0420583210SurveyofNetworkCodingTAOShao2guo,HUANGJia2qing,YANGZong2kai,QIAOWen2bo,XIONGZhi2qiang(HubeiKeyLaboratoryofIntelligentNetworkTechnology,TheDep
3、artmentofElectronicsandInformation,HuaZhongUniversityofScienceandTechnology,Wuhan430074,China)Abstract:Networkcoding,knownasoneofthemostimportantbreakthroughsonthetheoryofinformationprocessingandtransmission,isbasedonthemainideathatencodinganddecodingoperationsareap
4、pliedontheincomingmessagesofaninter2mediatenodetoproducecodedoutgoingonesbeforeforwarding.Networkcodinghasmanyadvantagesoverconventionalrout2ing,suchasprovidinghighernetworkthroughput,usingbandwidthefficientlyandbalancingthetraffic,etc.Inthispaper,wepresentthebasict
5、heoryandmainadvantagesanddisadvantagesofnetworkcoding,andthendescribethekeyalgorithmsaswellasgivingageneralreviewofsometypicalimplementationsofnetworkcodingindetail.Intheend,thedirectionsandfu2tureworksaresummarized.Keywords:networkcoding;randomnetworkcoding;informa
6、tionflow;multicast[6][7][8]1引言大學(xué),如普林斯頓大學(xué)、麻省理工大學(xué)、瑞士EPFL學(xué)院[9]等以及多家IT公司的研究中心,包括微軟研究院、貝爾實傳統(tǒng)的多播傳輸是通過構(gòu)造多播樹實現(xiàn)的.典型的多播[10][11]驗室、AT&T的香農(nóng)信息實驗室等都在積極開展對網(wǎng)絡(luò)樹,如最小費的Steiner樹,其構(gòu)造過程一般是個NP完全問編碼理論和應(yīng)用的研究;網(wǎng)絡(luò)編碼也逐漸引起了國內(nèi)學(xué)術(shù)界[1][123]題,因此大多數(shù)的近似算法,均不能使多播傳輸達到“最[12][13]的關(guān)注和重視,我國的清華大學(xué)、南京大學(xué)、西安電子科[4
7、]大流最小割”(MAX2FLOWMIN2CUT)定理確定的最大理[14]技大學(xué)等對網(wǎng)絡(luò)編碼進行了探索.論傳輸容量.這主要是因為:現(xiàn)有通信網(wǎng)絡(luò)中使用的路由機制本文將全面綜述網(wǎng)絡(luò)編碼的研究現(xiàn)狀,以期能更進一步認為網(wǎng)絡(luò)中傳輸?shù)男畔⑹遣荒墀B加的,只能進行存儲和轉(zhuǎn)發(fā).推動國內(nèi)對網(wǎng)絡(luò)編碼這一新興網(wǎng)絡(luò)技術(shù)的關(guān)注與研究.文章然而,香港中文大學(xué)R.Alshwede等在2000年的IEEE信息按如下方式組織:第2節(jié)介紹網(wǎng)絡(luò)編碼的基本概念與優(yōu)缺點;[5]論會刊上發(fā)表的一篇著名論文,徹底推翻了這一結(jié)論.該文第3節(jié)建立網(wǎng)絡(luò)編碼的原理模型,給出線性網(wǎng)絡(luò)編
8、碼的數(shù)學(xué)首次提出了網(wǎng)絡(luò)編碼(NetworkCoding)的概念并從理論上證描述;第4節(jié)歸納幾種主要的線性網(wǎng)絡(luò)編碼構(gòu)造算法,其中重明:如果允許網(wǎng)絡(luò)節(jié)點對傳輸?shù)男畔凑蘸线m的方式進行編點介紹多項式時間算法;一種實用的分布式網(wǎng)絡(luò)編碼方法:隨碼處理(如模二加、有限域上的運算等),而非