隨機網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸?shù)姆卢F(xiàn)

1、隨機網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸?shù)姆抡鎸崿F(xiàn)羅星星，蒲保興*，趙穎，鄧青(邵陽學(xué)院 信息工程系 湖南邵陽 422001)摘要: 基于隨機網(wǎng)絡(luò)編碼方法，構(gòu)造了在實驗室內(nèi)實現(xiàn)單源組播網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)姆抡婺Ｐ停河镁钟蚓W(wǎng)內(nèi)的網(wǎng)絡(luò)終端 代表單源組播網(wǎng)絡(luò)的節(jié)點，以 IP 地址和端口號代表有向信道，采用 UDP 網(wǎng)絡(luò)通信實現(xiàn)數(shù)據(jù)傳輸，從而對單源組播網(wǎng)絡(luò)進 行了仿真。運用 Java 編程實現(xiàn)了有限域的算術(shù)運算，根據(jù)隨機網(wǎng)絡(luò)編碼的編碼規(guī)則，分別編寫了單源組播網(wǎng)絡(luò)的源節(jié)點、 中間節(jié)點和宿點的工作程序，形成了一個完整的軟件系統(tǒng),該仿真模型可以適合于任意單源組播網(wǎng)絡(luò)。關(guān)鍵詞: 隨機網(wǎng)絡(luò)編碼；有限域的算術(shù)運算；Java 套接字編程；仿

2、真實現(xiàn)中圖分類號: TP393.09文獻標(biāo)識碼: ADOI：10.3969/j.issn.1003-6970.2014.08.007本文著錄格式：1羅星星，蒲保興，趙穎，等. 隨機網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸?shù)姆抡鎸崿F(xiàn)J. 軟件，2014，35(8)：32-37Simulation and Implementation of Data Transmission Based on Random Linear Network CodingLUO Xing-xing, PU Bao-xing*, ZHAO ying, DENG qing(Department of Information Engineering

3、, Shaoyang College, Shaoyang 422001, Hunan, China)【Abstract】: Based on random network coding, a simulation model is created, which can implement data transmission for single-source multicast network in laboratory. In a single-source multicast network; a node is represented by a terminal in a local n

4、etwork, a directed channel is represented by a socket(an IP address and a port number), and an UDP network com- munication denotes data transmission in directed channel, which can simulate a single-source multicast network. With Java programming, we implement the arithmetic operation of limited fiel

5、ds, and write respective program for source node, inter- val node and rank node based on coding rule of random network coding method. These programs form a whole software system. The presented simulation model can be fit for general single-source multicast network .【Key words】: random network coding

6、; arithmetic operation of limited fields; Java socket programming; simulation im-plementation0 引言網(wǎng)絡(luò)編碼技術(shù)1-2是由路由傳輸技術(shù)擴展而來的，就路由傳輸技術(shù)來說，中間節(jié)點只負責(zé)復(fù)制和轉(zhuǎn)發(fā)接收到 的信息，而對于網(wǎng)絡(luò)編碼技術(shù)而言，中間節(jié)點不僅具有直接復(fù)制和轉(zhuǎn)發(fā)信息的功能，還可以對接收到的信息進 行編碼后再進行轉(zhuǎn)發(fā)。采用網(wǎng)絡(luò)編碼技術(shù)實現(xiàn)數(shù)據(jù)傳輸?shù)年P(guān)鍵是構(gòu)造網(wǎng)絡(luò)編碼方案。隨機網(wǎng)絡(luò)編碼構(gòu)造算法3由于事先不需要獲 知網(wǎng)絡(luò)的全局拓撲知識，也不需要事先確定節(jié)點各鏈路的編碼向量,從而具有較好的可擴展性和可實施性，備

7、受 人們青睞。在對網(wǎng)絡(luò)編碼進行教學(xué)與科研的過程中，常常需要有實驗環(huán)節(jié)或仿真計算，可以采用自編模擬程序的方式4， 但這種方式需要編制大量的程序，同時存在不直觀、不利于對實驗結(jié)果進行分析和比較的缺點；文獻5提出了 一種基于 Window 套接字編程的網(wǎng)絡(luò)編碼仿真實現(xiàn)方法，但只涉及最簡單的有限域的異或運算，也只能適應(yīng)于 最簡單的“蝴蝶網(wǎng)絡(luò)”；還有一些學(xué)者選擇 NS 和 OPNET 等仿真軟件來實現(xiàn)6，但這些軟件的優(yōu)勢在于對高層 協(xié)議的支持，而要實現(xiàn)網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸?shù)哪M，必須對其進行擴展，由于這些軟件使用起來較為復(fù)雜，擴展基金項目: 湖南省大學(xué)生研究性學(xué)習(xí)與創(chuàng)新性計劃項目“隨機線性網(wǎng)絡(luò)編碼的仿真實現(xiàn)

8、研究”;湖南省教育廳重點科研項目(11A111); 湖南 省科技廳計劃項目(2012FJ3108)作者簡介: 羅星星(1993-), 男, 湖南張家界人, 主要從事網(wǎng)絡(luò)編碼研究; 蒲保興(1965-), 男, 湖南邵陽人, 教授, 博士, 主要從事網(wǎng)絡(luò)編碼、 進化計算等方面的研究具有一定的難度；此外，還可以采用硬件的方法構(gòu)造實驗平臺 7，8，但必須采用特殊的硬件，實現(xiàn)起來較麻煩。 本文提出了一種簡便的隨機網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸?shù)姆抡鎸崿F(xiàn)方法，它不需要特定的軟、硬件支持，在一般的實驗 室內(nèi)就可以實現(xiàn)，同時又不同于軟件仿真，具有一定的直觀性。在局域網(wǎng)內(nèi)選取相互連接的若干終端來模擬網(wǎng) 絡(luò)節(jié)點，以套接字(I

9、P 地址+端口號)代表節(jié)點間的有向鏈路，采用 UDP 數(shù)據(jù)傳輸來模擬有向鏈路的數(shù)據(jù)流動， 從而實現(xiàn)了對單源組播網(wǎng)絡(luò)的模擬。在節(jié)點上運用 Java 編程9實現(xiàn)了有限域的算術(shù)運算，根據(jù)網(wǎng)絡(luò)編碼數(shù)據(jù)傳 輸策略，各節(jié)點采用 Java 套接字編程方法實現(xiàn)數(shù)據(jù)的接收與發(fā)送，中間節(jié)點調(diào)用有限域的算術(shù)運算方法對輸出 信道進行編碼，形成了編碼數(shù)據(jù)包，宿點接收數(shù)據(jù)包，調(diào)用有限域的算術(shù)運算方法，對接收的數(shù)據(jù)進行解碼而 恢復(fù)出源點播出的信息。采用 Java 編程實現(xiàn)各部分的功能，形成了一個完整的軟件系統(tǒng)，各節(jié)點只需要依次運 行該系統(tǒng)并輸入相關(guān)的信息便可以工作，各節(jié)點的相互作用便實現(xiàn)隨機網(wǎng)絡(luò)編碼的數(shù)據(jù)傳輸。仿真結(jié)果表明

10、提 出的方法是有效的，且該方法具有軟硬件要求低、操作方便的特點，并易于掌握和實現(xiàn)。提出的方法適用于在 一般的單源組播網(wǎng)絡(luò)上實現(xiàn)隨機網(wǎng)絡(luò)編碼的數(shù)據(jù)傳輸仿真，為網(wǎng)絡(luò)編碼的實驗環(huán)節(jié)與仿真計算提供了有效的方法。1 隨機網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸策略一個單源組播網(wǎng)絡(luò)可以用一個有向無環(huán)圖表示，其中有一個源點、若干宿點以及若干中間節(jié)點，節(jié)點間存 在有向鏈路，為了描述方便，各鏈路的容量均為 1 個單位，稱之為信道。源點產(chǎn)生數(shù)據(jù)，各節(jié)點采用網(wǎng)絡(luò)編碼 技術(shù)進行數(shù)據(jù)傳輸，宿點接收信息后通過解碼恢復(fù)出源點產(chǎn)生的信息。對于一個節(jié)點 v，記 In(v)為輸入信道集，Out(v)為輸出信道集。 在一個單源組播網(wǎng)絡(luò)上采用隨機網(wǎng)絡(luò)編碼方

11、法實現(xiàn)數(shù)據(jù)傳輸，設(shè)源點至宿點集的組播容量為 C，選定正整數(shù) n(nC)作為組播率，則在每一代(或稱每一輪)，源點產(chǎn)生 n 個數(shù)據(jù)包，記為(X1, X2, ,Xn)，每一個數(shù)據(jù)包對 應(yīng)一個全局編碼向量。源點產(chǎn)生的數(shù)據(jù)包對應(yīng)的全局編碼向量是一個 n 維向量，每一個分量是有限域上的一個字符，記第 i 個數(shù)據(jù)包對應(yīng)的全局編碼向量為 Vi，Vi 為單位向量，它除了第 i 個分量為 1 外，其余分量全為 0。 一般來說，對于源點或中間節(jié)點，設(shè)其接收到(若為中間節(jié)點)或產(chǎn)生(若為源點)的數(shù)據(jù)包為 Y1, Y2, , Yp，當(dāng)節(jié)點為源點時，則 p=n，當(dāng)節(jié)點為中間節(jié)點 v 時，p=| In(v)|。各個數(shù)據(jù)包

12、對應(yīng)的全局編碼向量為(T1, T2, , Tp)， 每個全局編碼向量也是 n 維的。若該節(jié)點需要傳輸信息至 m(m=| Out(v)|)條輸出信道，則對于第 i(1im)條輸出 信道，節(jié)點在有限域 F 上分別隨機產(chǎn)生 p 個隨機數(shù) (xi,1,xi,2 ,.,xi, p ) ，分別與(Y1, Y2, Yp)相對應(yīng)。節(jié)點為第 i 條pp輸出信道進行編碼，產(chǎn)生輸出數(shù)據(jù)包為 Zi = åxi, jYj ，該數(shù)據(jù)包對應(yīng)的全局編碼向量為 TOi = åxi, jTj 。j =1節(jié)點向第 i 條輸出信道發(fā)送全局編碼向量 Ti 和數(shù)據(jù)包 Zi，記為 Ti|Zi。j =1對于宿點，至少需要

13、從 n 條輸入信道中接收數(shù)據(jù)包和相應(yīng)的全局編碼向量，利用全局編碼向量和數(shù)據(jù)包構(gòu) 成一個 n 維線性方程組，采用高斯消元法求解線性方程組就可以恢復(fù)出源點播出的數(shù)據(jù)包(X1,X2,Xn)。2有限域的算術(shù)運算網(wǎng)絡(luò)編碼操作在有限域上,在編碼過程中,涉及到有限域字符之間的加、乘運算，在解碼過程中，涉及到有 限域字符之間的加、減(有限域的字符的相減運算與相加運算一致)、乘、除運算，因此，在實現(xiàn)隨機網(wǎng)絡(luò)編碼 數(shù)據(jù)傳輸過程，節(jié)點必須能實現(xiàn)有限域的算術(shù)運算10。選定有限域的階和相應(yīng)的本源多項式，本文選定有限域為 GF(28)，相應(yīng)的本原多項式為 x8+x4+x3+x+1，從 而本文中有限域中的字符為 8 位二進

14、制數(shù)，可以用一個字節(jié)(byte)表示。根據(jù)有限域的運算規(guī)則，兩個字符的算 術(shù)運算的結(jié)果仍為 8 位二進制數(shù)。運用 Java 編程構(gòu)造一個類，記為 GF.class，類中以靜態(tài)方法給出了有限域 GF(28) 中兩個字符的加、乘、除運算，三個主要方法如下：public static void add(byte operation1, byte operation2, byte result)/有限域加public static void multiplication(byte operation1, byte operation2, byte result)/有限域乘 public static

15、void division(byte operation1,byte operation2, byte result)/除節(jié)點在進行編碼或解碼時，如要實現(xiàn)有限域的運算，只需把 GF.class 類包含進來，同時在需要實現(xiàn)相應(yīng)運算的地方調(diào)用該類中相應(yīng)的靜態(tài)方法即可。3隨機網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸技術(shù)的仿真實現(xiàn)本文以一個典型的單源組播網(wǎng)絡(luò)為例(如圖 1 所示)來說明如何在實驗室構(gòu)造隨機網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸?shù)姆抡?實現(xiàn)模型，只要根據(jù)單源組播網(wǎng)絡(luò)拓撲的節(jié)點和鏈路情況對模型的參數(shù)進行修改，構(gòu)造出的模型也適合一般的 單源組播網(wǎng)絡(luò)。3.1單源組播網(wǎng)絡(luò)的仿真在圖 1 所示的單源組播網(wǎng)絡(luò)中,節(jié)點 S 是數(shù)據(jù)源點,節(jié)點 1、

16、 節(jié)點 2、節(jié)點 3、節(jié)點 4、節(jié)點 5 均為中間節(jié)點，節(jié)點 T1 和 T2 為 宿點，源點產(chǎn)生信息經(jīng)過網(wǎng)絡(luò)編碼后由輸出信道傳輸至網(wǎng)絡(luò)，中 間結(jié)點把接收到信息進行網(wǎng)絡(luò)編碼后再由其輸出信道進行轉(zhuǎn)發(fā)， 宿點通過輸入信道接收數(shù)據(jù)包后，由各輸入信道的全局編碼向量 和數(shù)據(jù)包的內(nèi)容構(gòu)造線性方程組，通過求解線性方程組恢復(fù)出源 點產(chǎn)生的信息。為了對圖 1 的網(wǎng)絡(luò)拓撲進行模擬，在局域網(wǎng)內(nèi)選擇 8 個網(wǎng)絡(luò) 終端，它們同處在一個 C 類地址(172.16.101)的網(wǎng)段內(nèi)，各網(wǎng)絡(luò) 終端采用集線器或交換機相連接，其 IP 地址的分配如圖 2 所示。 用網(wǎng)絡(luò)終端來代表單源組播網(wǎng)絡(luò)的節(jié)點，用網(wǎng)絡(luò)套接字(IP地址+端口號)

17、來代表節(jié)點間的有向信道，采用 UDP 數(shù)據(jù)通信來 表示有向信道上的數(shù)據(jù)傳輸，并運用 Java 套接字編程來實現(xiàn)。由圖 1一個單源組播網(wǎng)絡(luò)的邏輯圖圖 1 可以看出，源點 S 至宿點集的組播容量為 3，因此選定整數(shù) 3 為組播率，源點每一代產(chǎn)生 3 個數(shù)據(jù)包，相 當(dāng)于源點分別從 3 條虛擬單位信道中接收到 3 個數(shù)據(jù)包。圖 2網(wǎng)絡(luò)節(jié)點的 IP 地址分配有向信道與套接字的對應(yīng)關(guān)系如圖 3 所示。在圖 3 中，單源組播網(wǎng)絡(luò)的每一條有向信道對應(yīng)一個套接字，例如：源點至節(jié)點 1 的單位有向信道與套接字(172.16.101.11：10011)對應(yīng)，從而源點向節(jié)點 1 傳輸數(shù)據(jù)相當(dāng)于 源點向該套接字發(fā)送一個

18、 UDP 數(shù)據(jù)包；同理，節(jié)點 2 至節(jié)點 5 的有向信道與套接字(172.16.101.15:1022)對應(yīng)， 節(jié)點 2 向節(jié)點 5 發(fā)送數(shù)據(jù)相當(dāng)于節(jié)點 2 向該套接字發(fā)送一個 UDP 數(shù)據(jù)包。因此，采用套接字來模擬有向信道，就可以在局域網(wǎng)內(nèi)實現(xiàn)對圖 1 的單源組播網(wǎng)絡(luò)的仿真。圖 3有向信道與套接字的對應(yīng)關(guān)系3.2源點 S 的工作流程源點需要確定每代產(chǎn)生的數(shù)據(jù)包個數(shù) n，也稱之為組播率；同時需要確定輸出信道數(shù)，每一個輸出數(shù)據(jù)包 對應(yīng)一條輸出信道，而每一條輸出信道與一個套接字相聯(lián)系，因此需要確定每個輸出數(shù)據(jù)包送往的 IP 地址和端 口號。當(dāng)以上工作完成后，把每代傳輸?shù)臄?shù)據(jù)等成 n 等分，每一等分

19、構(gòu)成一個輸入數(shù)據(jù)包，本文中采用人工的 辦法，為每一個數(shù)據(jù)包輸入等長的數(shù)據(jù)內(nèi)容。然后為每一個輸出數(shù)據(jù)包產(chǎn)生一個局部編碼向量，并求出全局編 碼向量和編碼后的數(shù)據(jù)包，再通過 Java 套接字編程把編碼后的數(shù)據(jù)包傳輸至指定的套接字。源點的工作主要包括以下 5 個部分內(nèi)容： 鍵入組播率和輸出信道數(shù)； 鍵入輸出信道對應(yīng)的套接字； 輸入每一代要傳輸?shù)臄?shù)據(jù)； 為每一輸出信道運用隨機網(wǎng)絡(luò)編碼方法生成數(shù)據(jù)編碼并生成相應(yīng)的全局網(wǎng)絡(luò)編碼向量，形成數(shù)據(jù)包； 根據(jù)給定的套接字發(fā)送 UDP 數(shù)據(jù)包。運行我們開發(fā)的系統(tǒng)，源點的運行界面如圖 4 和圖 5 所示，通過圖 4 的界面，可以輸入源點的組播率(輸入信道數(shù))，源點的輸出

20、信道數(shù)以及各輸出信道對應(yīng)的套接字；通過圖 5 的界面輸入每一代發(fā)送的數(shù)據(jù)包內(nèi)容，在 本例中，源點每一代發(fā)送 3 個數(shù)據(jù)包，3 個數(shù)據(jù)包應(yīng)等長。3.3中間節(jié)點的工作流程中間節(jié)點分別從上游節(jié)點接收數(shù)據(jù)，然后分別轉(zhuǎn)發(fā)至下游節(jié)點，根據(jù)網(wǎng)絡(luò)拓撲確定輸入信道數(shù)，以及每一輸入信道對應(yīng)的端口號；還需要確定輸出信道數(shù)，以及每輸出信道對應(yīng)的套接字。例如，對于節(jié)點 5 來說，其 輸入信道數(shù)為 4，對應(yīng)的端口號分別為 10021,10022,10023,10024。而輸出信道數(shù)為 2，對應(yīng)的套接字分別為 (172.16.101.10033)和(172.16.101.17:10041)。圖 4源點的運行界面 1圖 5源

21、點的運行界面 2中間節(jié)點的工作流程如下: 鍵入輸入信道數(shù)以及各信道對應(yīng)的端口號； 鍵入輸出信道數(shù)及各信道對應(yīng)的套接字； 從各輸入信道對應(yīng)的端口中接收數(shù)據(jù)包； 根據(jù)接收到的數(shù)據(jù)包, 采用隨機網(wǎng)絡(luò)編碼方法為每一輸出信道產(chǎn)生輸出數(shù)據(jù)包； 根據(jù)給定的套接字發(fā)送 UDP 數(shù)據(jù)包。 中間節(jié)點的運行界面如圖 6 所示，通過這一界面，可以輸入中間節(jié)點的輸入信道數(shù)以及每條輸入信道對應(yīng)的套接 字，由于每條輸入信道的 IP 地址均為本機地址，故只需輸 入相應(yīng)的端口號；通過這一界面，還需鍵入輸出信道數(shù)以及 每條輸出信道對應(yīng)的套接字。圖 6 是節(jié)點 5 的運行界面，從中可以看出，節(jié)點的輸入信道有 4 條，對應(yīng)的端口號分

22、別為：10021、10022、10023、10024；而輸出信道有 2 條，對應(yīng)的 套接字為：(172.16.101.16:10033)、(172.16.101.17:10041)。3.4 宿點的工作流程宿點需要從輸入信道接收數(shù)據(jù),然后進行解碼運算,再恢復(fù)出源點播出的信息,宿點的工作過程如下: 鍵入輸入信道數(shù)以及各信道對應(yīng)的端口號； 從各輸入信道對應(yīng)的端口中接收數(shù)據(jù)包；圖 6中間節(jié)點的運行界面 根據(jù)接收到的數(shù)據(jù)包, 析出每一數(shù)據(jù)包的全局編碼向量,形成一個 n 維線性方程組,通過高斯消元法,求解 該線性方程組,恢復(fù)出源點播出的信息。宿點的運行界面如圖 7 和圖 8 所示，其中通過圖 7 的界面輸

23、入宿點的輸入信道的信息，而圖 8 的界面顯示 宿點恢復(fù)出源點產(chǎn)生的信息。3.5程序的執(zhí)行當(dāng)上述各節(jié)的程序錄入后，則必須按一定的順序運行各節(jié)點的程序，即按 T1,T2,5,4,3,2,1,S 的順序啟動程序 運行，當(dāng)節(jié)點 S 的程序運行后，每一代輸入三個數(shù)據(jù)包的數(shù)據(jù)內(nèi)容，見圖 5，然后點擊“發(fā)送數(shù)據(jù)”按鈕，于是 宿點 T1 和 T2 收到源點 S 播出的信息，見圖 8。4結(jié)論在實驗室內(nèi)構(gòu)造出了一個隨機網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸?shù)姆抡鎸崿F(xiàn)模型，在局域網(wǎng)內(nèi)選擇若干相互連接的網(wǎng)絡(luò)終圖 7宿點的運行界面 1圖 8宿點的運行界面 2端代表網(wǎng)絡(luò)節(jié)點，以套接字代表節(jié)點間的有向信道，以 UDP 數(shù)據(jù)通信表示有向信道的數(shù)據(jù)

24、傳輸，從而對單源 組播網(wǎng)絡(luò)進行了仿真，采用 Java 編程實現(xiàn)了有限域的算術(shù)運算，根據(jù)隨機網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸?shù)乃惴ǚ謩e編寫源 點、中間節(jié)點、宿點的編碼和解碼程序，形成了一個完整的軟件系統(tǒng)，每一節(jié)點運行該系統(tǒng)并輸入相應(yīng)的信息， 各節(jié)點相互作用便可以實現(xiàn)隨機線性網(wǎng)絡(luò)編碼的數(shù)據(jù)傳輸。本文給出了一個實例，仿真結(jié)果表明了方法的有效性，只要根據(jù)單源組播網(wǎng)絡(luò)的鏈路情況修改本模型的參 數(shù)，模型可以應(yīng)用于一般的單源組播網(wǎng)絡(luò)，給出的方法具有軟硬件要求低、操作方便的特點，并易于掌握和實 現(xiàn)。提出的方法為網(wǎng)絡(luò)編碼的實驗環(huán)節(jié)與仿真計算提供了有效的方法。參考文獻1陶少國, 黃佳慶, 楊宗凱等. 網(wǎng)絡(luò)編碼研究綜述J. 小型微型計算機系統(tǒng), 2008, 29(4): 583592.2范宇. 基于RS碼的網(wǎng)絡(luò)編碼層設(shè)計J. 軟件, 2013, 34(5): 9295.3Ho T, Medard M, Koe