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

　　摘要

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

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

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

　　1 網絡編碼理論及相關研究應用背景

　　1.1網絡編碼理論產生背景和基本概念

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

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

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

　　網絡編碼最簡單的概念來自‘蝴蝶網’，如圖1.1-1所示：

　　圖1.1-1 網絡編碼的基本原理

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

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

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

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

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

　　下面給出一個不僅NC提高多播網絡吞吐量，而且顯著改善網絡負載均衡的例子。圖1.1-2(a)顯示了網絡的容量，所有的邊的容量都是2。在這個例子中，最大流是4。圖2(b), (c)和(d)分別顯示了單會話IP組播，多會話IP組播和基于網絡編碼的組播的分配樹。在圖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]。

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

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

　　[!--empirenews.page--]

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

　　(c)多會話的IP組播 (d)網絡編碼組播

　　圖1.1-2 網絡編碼提高網絡容量，同時均衡了網絡流量

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

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

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

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

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