基于網(wǎng)絡(luò)編碼的多信源組播通信系統(tǒng)，包括源代碼，原理圖等(一)

　　摘要

　　網(wǎng)絡(luò)編碼改變了傳統(tǒng)網(wǎng)絡(luò)節(jié)點上路由器交換和交換機對信息流“存儲—轉(zhuǎn)發(fā)”的模式，提出網(wǎng)絡(luò)路由交換節(jié)點對輸入的信息流編碼后再發(fā)送，并在接收器上進行解碼，從而還原信息。隨著網(wǎng)絡(luò)編碼理論的日益發(fā)展和完善，其應(yīng)用的研究也越來越受到重視。

　　本文首先介紹網(wǎng)絡(luò)編碼理論的基本概念，回顧了近年來網(wǎng)絡(luò)編碼的研究動態(tài)。接著指出研究多信源網(wǎng)絡(luò)編碼組播通信的重要性，在使用NetFPGA開發(fā)平臺的基礎(chǔ)上，提出網(wǎng)絡(luò)編碼組播通信系統(tǒng)及其整體設(shè)計方案。在方案中重點介紹了硬件系統(tǒng)中采用的編碼策略—隨機線性編碼，解碼策略、算法以及通信協(xié)議，同時介紹了系統(tǒng)的軟硬件接口和軟件作用。最后，給出了編碼路由器、轉(zhuǎn)發(fā)路由器以及解碼路由器三個系統(tǒng)的詳細設(shè)計方案，方案中主要包括單元模塊圖，每個模塊的主要功能與結(jié)構(gòu)，數(shù)據(jù)處理流程及算法說明，輸入輸出信號及說明、關(guān)鍵時序或狀態(tài)。

　　由于本系統(tǒng)的主要功能是由硬件實現(xiàn)，所以和傳統(tǒng)組播通信網(wǎng)絡(luò)相比，具有時延小，沒有了調(diào)度和排隊時間，使得網(wǎng)絡(luò)中鏈路負(fù)載更均衡，體現(xiàn)出了網(wǎng)絡(luò)編碼的優(yōu)勢。

　　1 網(wǎng)絡(luò)編碼理論及相關(guān)研究應(yīng)用背景

　　1.1網(wǎng)絡(luò)編碼理論產(chǎn)生背景和基本概念

　　60年前C.E.Shannon發(fā)表“通信數(shù)學(xué)原理“解決了信道容量極限問題。2000年誕生的網(wǎng)絡(luò)編碼(Network Coding:NC)是繼此后的一個全新突破，它解決了網(wǎng)絡(luò)通信中單/多源對多接收點組/廣播如何達到網(wǎng)絡(luò)容量極限的問題。傳統(tǒng)網(wǎng)絡(luò)通信節(jié)點上的路由交換機只完成存儲轉(zhuǎn)發(fā)功能。NC指出如果允許路由交換機對輸入信息流進行編碼再發(fā)送，使得網(wǎng)絡(luò)節(jié)點既實現(xiàn)路由功能又實現(xiàn)編碼功能。在這種全新的體系結(jié)構(gòu)下,網(wǎng)絡(luò)性能可以達到最大流傳輸?shù)睦碚摌O限[1][2]。

　　2000年，以香港中文大學(xué)信息工程系為主的研究人員針對通訊網(wǎng)絡(luò)的瓶頸問題，提出了一種看似瘋狂的想法，這種具有革命潛力的方法名為網(wǎng)絡(luò)編碼，以網(wǎng)絡(luò)編碼器取代路由器;原本只是單純的傳送信息的路由器，換成編碼器之后，傳送的卻是有關(guān)信息的證據(jù)，而不是信息本身;當(dāng)接收器收到證據(jù)時，即可結(jié)合各項線索，推導(dǎo)出原始信息。[3]

　　《科學(xué)美國人》雜志(Scientific American Magazine)2007年6月，以“Breaking Network Logjams”(打破網(wǎng)絡(luò)僵局)為題刊登了MIT科學(xué)家詳細介紹了7年前誕生于香港中文大學(xué)的網(wǎng)絡(luò)編碼理論[4]。其中指出，網(wǎng)絡(luò)編碼是繼60年前C.E.Shannon發(fā)表“通信的數(shù)學(xué)原理”后，網(wǎng)絡(luò)通信理論的一個全新突破。C.E.Shannon解決了點對點信道的容量極限問題，而NC解決了如何達到單源對多點及多源對多點的網(wǎng)絡(luò)通信容量極限的問題[4]。傳統(tǒng)網(wǎng)絡(luò)通信理論把信息流當(dāng)成管道中流動的水，是不可壓縮的;故傳統(tǒng)網(wǎng)絡(luò)節(jié)點上的路由交換機只是完成存儲轉(zhuǎn)發(fā)功能。NC理論的劃時代意義在于：提出網(wǎng)絡(luò)路由交換節(jié)點對輸入的信息流進行編碼再發(fā)送，可進一步提升網(wǎng)絡(luò)吞吐量!從而改變了比特不能再被壓縮的經(jīng)典結(jié)論，指出網(wǎng)絡(luò)信息流可以被壓縮。

　　網(wǎng)絡(luò)編碼最簡單的概念來自‘蝴蝶網(wǎng)’，如圖1.1-1所示：

　　圖1.1-1 網(wǎng)絡(luò)編碼的基本原理

　　上圖所示的網(wǎng)絡(luò)中，源節(jié)點S1想把信息流ai傳送給R1和R2。另一方面，源節(jié)點S2也希望在相同時間、以相同速度，把信息流bi傳送給同樣的接收節(jié)點R1和R2。假設(shè)每個路徑每秒可攜帶一個位元，而且只能順著箭號所指的方向前進。如果路由器只傳輸其所接收到的信息，那么中間鏈路將是個瓶頸，因為每秒總共接收到二位元的資料，但其容量只有一位元，路由器每秒只能傳送一位元資料給中間鏈路，這種瓶頸會造成可怕的塞車。相反，如果把一般的路由器換成編碼器，它可以把兩個信息通過異或或者線性組合運算成單一位元輸送給中間鏈路，并且發(fā)送ai+bi (或者ai和bi的任意線性組合)，這樣就輕而易舉地解決了塞車問題[3][5]。

　　網(wǎng)絡(luò)編碼另一個與路由系統(tǒng)不同之處在于，充分利用網(wǎng)絡(luò)資源。圖1中，S1透過路徑S1R1把ai傳給R1，S2透過路徑S2R2把bi傳給R2，這在路由系統(tǒng)中是不會使用到的。節(jié)點R1接收到ai，并且根據(jù)每次編碼器運算結(jié)果，輸入到與編碼器使用的相同函數(shù)(異或或者線性組合)內(nèi)，推導(dǎo)出bi。節(jié)點R2解出ai也是同樣的道理。重復(fù)對每個位元字串進行相同的流程，最后就能得出兩個原始信息。

　　可見，有了網(wǎng)絡(luò)編碼，網(wǎng)絡(luò)的運作可望變得更有效率(不需要增加硬件設(shè)備或頻寬，就可以提高網(wǎng)絡(luò)吞吐量)，可以改善網(wǎng)絡(luò)的負(fù)載均衡，節(jié)省網(wǎng)絡(luò)帶寬消耗，節(jié)省無線網(wǎng)絡(luò)的能量消耗，提高了網(wǎng)絡(luò)的魯棒性，同時對于具有鏈路時延的網(wǎng)絡(luò)，相對于路由方式，通過網(wǎng)絡(luò)編碼進行多播傳輸時可以獲得較小的傳播時延[6][7]。

　　隨后，李碩彥等在證明了在足夠大的有限域內(nèi)，通過節(jié)點內(nèi)進行線性網(wǎng)絡(luò)編碼(Linear Network Coding： LNC)就可以達到網(wǎng)絡(luò)組播，廣播等的理論上限[8]。在線性范圍內(nèi)解決達到理論上界的問題為NC進入實際應(yīng)用奠定了堅實的基礎(chǔ)。隨后，Yueng，李碩彥[9]等出版了國際上第一本網(wǎng)絡(luò)編碼理論專著“Network Coding Theory”。

　　Koetter等[10]于2003年提出將NC問題與多項式方程建立數(shù)學(xué)聯(lián)系，使得討論NC問題又多了一種有力的數(shù)學(xué)工具代數(shù)理論;LNC針對于已經(jīng)了解整個網(wǎng)絡(luò)拓?fù)錉顩r的情況下，經(jīng)過網(wǎng)絡(luò)路由設(shè)定，通過確定的矩陣計算公式對報文進行編解碼，實現(xiàn)簡單，但適應(yīng)性和容錯性較差。論文[11]中提出隨機網(wǎng)絡(luò)編碼概念(Random Network Coding：RNC)，與線性編碼結(jié)合在一起，使得分布式的、簡單實用的網(wǎng)絡(luò)編碼體系形成。隨機線性網(wǎng)絡(luò)編碼是一種分布式算法，編碼在有限域上進行，系數(shù)隨機選取，其靈活性遠大于LNC。

　　下面給出一個不僅NC提高多播網(wǎng)絡(luò)吞吐量，而且顯著改善網(wǎng)絡(luò)負(fù)載均衡的例子。圖1.1-2(a)顯示了網(wǎng)絡(luò)的容量，所有的邊的容量都是2。在這個例子中，最大流是4。圖2(b), (c)和(d)分別顯示了單會話IP組播，多會話IP組播和基于網(wǎng)絡(luò)編碼的組播的分配樹。在圖2(b)中，發(fā)送端通過一個組播分配樹同時向接收端R1, R2和R3發(fā)送了兩個比特a，b。在圖2(c)中，組播會話1，2和3分別向接收者發(fā)送了比特a，b和c。需要指出的是多會話IP組播所有的會話不是擁有同一個分配樹。在圖2(d)中，發(fā)送端同時向接收端R1, R2和R3發(fā)送了四個比特a，b，c和d[12]。

　　所有的組播技術(shù)中網(wǎng)絡(luò)編碼可以達到最高的吞吐量，因為它可以最大流發(fā)送信息。我們看到在圖2(b), (c)和(d)中在單位時間內(nèi)接收端分別接收到2，3和4比特。因此在這個例子中，基于網(wǎng)絡(luò)編碼的組播的吞吐量是單會話IP組播的2倍，多會話IP組播的1.3倍。

　　通過比較基于網(wǎng)絡(luò)編碼的組播和現(xiàn)在的組播來研究負(fù)載均衡的影響。假定基于網(wǎng)絡(luò)編碼的組播使用圖2(d)例子中的容量的一半。在這種情況下，單會話IP組播和網(wǎng)絡(luò)編碼都在單位時間內(nèi)向所有的接收端發(fā)送了2比特。在圖2(b)中，通過了網(wǎng)絡(luò)中9條鏈路(總共發(fā)送10比特)中的5條來傳輸2比特，另外4條沒有使用。另一方面，當(dāng)網(wǎng)絡(luò)編碼使用時，2( d) 通過了9條鏈路(總共發(fā)送9比特)來傳輸2比特。于是通過應(yīng)用網(wǎng)絡(luò)編碼，流量負(fù)載可以分散在整個網(wǎng)絡(luò)上。

　　[!--empirenews.page--]

　　(a)鏈接容量 (b)單會話的IP組播

　　(c)多會話的IP組播 (d)網(wǎng)絡(luò)編碼組播

　　圖1.1-2 網(wǎng)絡(luò)編碼提高網(wǎng)絡(luò)容量，同時均衡了網(wǎng)絡(luò)流量

　　1.2國內(nèi)外研究動態(tài)與現(xiàn)狀

　　網(wǎng)絡(luò)編碼自誕生以來，普及性的急速增長就連其奠基者也始料未及。從2005年開始每年一次的NetCod workshop 得到了Microsoft, Qualcomm等機構(gòu)的資助。短短幾年，發(fā)表了幾百篇學(xué)術(shù)論文。這個嶄新的領(lǐng)域?qū)υS多相關(guān)學(xué)科產(chǎn)生了深遠的影響，NC的理論研究范圍包括信息論及通信的幾乎每個領(lǐng)域，如線性編碼，非線性編碼，隨機編碼，靜態(tài)碼，卷積碼，群碼，Alphabet碼，碼構(gòu)建，算法協(xié)議，有環(huán)網(wǎng)絡(luò)，無向網(wǎng)絡(luò)，鏈路失效及其網(wǎng)絡(luò)管理，分離理論，錯誤檢測和糾錯碼，密碼學(xué)，多信源編碼，多-單播編碼, Cost Criteria, 非均勻需求,關(guān)聯(lián)信源編碼，最大流/刮集界，疊加編碼，網(wǎng)絡(luò)互連，路由尋找，無線及衛(wèi)星網(wǎng)絡(luò)，Ad hoc網(wǎng)絡(luò)，傳感網(wǎng)絡(luò)，數(shù)據(jù)存儲及分布，矩陣?yán)碚?，?fù)雜性理論，圖論，隨機圖論，樹裝箱(Tree Packing)，多種物流(Multicommodity flow)，游戲理論，矩陣胚理論(Matriod theory)，信息論不等式，排隊論分析，率失真(rate-distortion)可逆網(wǎng)絡(luò)，多用戶信道，聯(lián)合網(wǎng)絡(luò)信道編碼，P2P網(wǎng)絡(luò)等[13]。

　　國外多所著名大學(xué)如普林斯頓大學(xué)、麻省理工、瑞士EPFL 學(xué)院等和多家IT 公司的研究中心,包括微軟研究院、貝爾實驗室、AT &T 的香農(nóng)信息實驗室等都在積極開展對網(wǎng)絡(luò)編碼理論和應(yīng)用的研究。與此同時，網(wǎng)絡(luò)編碼的實際應(yīng)用問題被提到技術(shù)研究的前線。從2005年第一屆Net Cod國際會議上就明確將NC在現(xiàn)實通信中的應(yīng)用作為研究的重點。微軟公司是最早開展網(wǎng)絡(luò)編碼應(yīng)用研究的公司[14]，Microsoft公司已經(jīng)采用網(wǎng)絡(luò)編碼作為其下一代網(wǎng)絡(luò)內(nèi)容發(fā)布平臺Avalanche的核心技術(shù)。

　　不僅國外，近兩年來國內(nèi)學(xué)者也開始研究網(wǎng)絡(luò)編碼。清華大學(xué)[15]，西安電子科大、及電子科技大學(xué)[16]，北京郵電大學(xué)[17]均投入了NC與無線網(wǎng)絡(luò)方面的研究。NC在P2P網(wǎng)絡(luò)傳輸，流媒體廣播及內(nèi)容分發(fā)方面的應(yīng)用方面，上海大學(xué)[18]、湖南大學(xué)[19]和并行與分布處理國家重點實驗室[20]，中國科學(xué)技術(shù)大學(xué)[21]等都進行了研究。最近幾年中，網(wǎng)絡(luò)編碼在組播通信方面的應(yīng)用成為了研究的熱點，復(fù)旦大學(xué)研究了單信源組播并提出了一項關(guān)于在目前internet路由器上實現(xiàn)網(wǎng)絡(luò)編碼的專利[23]，西安電子科技大學(xué)提出了一種基于網(wǎng)絡(luò)編碼的組播路由算法，能夠大大降低網(wǎng)絡(luò)資源消耗，同時能改善負(fù)載均衡[24]。

　　以上網(wǎng)絡(luò)編碼在通信中的應(yīng)用研究基本上都是處于理論和計算機軟件仿真階段，在用硬件平臺搭建實際的組播網(wǎng)絡(luò)，并在真實的網(wǎng)絡(luò)環(huán)境中應(yīng)用網(wǎng)絡(luò)編碼，進行其實現(xiàn)的復(fù)雜度和網(wǎng)絡(luò)性能的評估等方面的研究尚處于起步階段。