基于網絡編碼技術的水聲網絡路由協議研究

祝　琳，江志浩，李　迅

(中國人民解放軍91635部隊,北京 102249)

?

基于網絡編碼技術的水聲網絡路由協議研究

祝琳，江志浩，李迅

(中國人民解放軍91635部隊,北京 102249)

摘要：針對水聲通信傳輸速率低、時延大的缺點，提出在水聲環境下將隨機網絡編碼方法應用于節點之間廣播通信，利用NS-2仿真軟件對網絡編碼路由協議NCR(Network Coding Routing)進行仿真，并分別從投遞率、投遞時延、協議開銷和沖突率4個網絡性能評價指標進行了分析。發現在節點數量為50的隨機網絡拓撲結構中，與傳統的泛洪(Flooding)方式相比，NCR協議的數據包投遞率大約提高了20%～50%，網絡時延降低了大約50%～60%，NCR協議改善了水聲通信網絡傳輸效率，提高投遞率，提高能量利用效率和傳輸可靠性，時延和數據沖突率有效降低，網絡性能獲得明顯改善。

關鍵詞：水聲通信；網絡編碼；協議；投遞率

0引言

隨著人類對海洋的探索、開發和利用程度越來越深入，無論是軍用還是民用領域，都對海洋環境下的信息傳遞有著巨大的需求。建立可靠、安全的水下通信網絡，是實現海洋國土安全、海下科學研究、海洋勘探開采各種工作的關鍵問題。聲信號在水下的傳播有擴散損耗、吸收損耗和邊界損耗，且傳播距離越大、信號頻率越高，傳播損失也越大[1]。由于水下設備多采用電池供電，能夠利用的能量十分有限，因此需要設計一個具有高可靠性、大吞吐量、低功率消耗和短傳輸時延的水聲通信網絡[2]。傳統的路由算法只對數據存儲和轉發[3]，不對傳輸的信息進行處理，最終導致多播通信可以實現的傳輸容量遠遠小于最大流最小割定理(Max-Flow Min-Cut Theorem)所確定的容量上限，不能實現吞吐量的最大化[4]。網絡編碼技術不同于傳統路由算法，該技術能夠使網絡中間節點對信息進行融合處理，即中間節點不僅僅是簡單的存儲轉發，還可以對信息進行一定處理，增加單次傳輸的信息量，提高網絡的性能[5]。大量研究顯示網絡編碼技術可以提升多播、單播和廣播等方式的網絡吞吐量，可明顯提高傳輸效率[6]，該技術已經在P2P網絡中、分布式存儲、無線網狀網、無線自組織網絡、無線傳感網絡以及網絡安全中得到有效應用[7-9]。

傳統水聲通信廣播信息一般采用泛洪法，泛洪方式是一種節點廣播數據方式[10，11]，這種方法主要特點是算法簡單，尤其在網絡拓撲結構時常發生變化時適合使用該方法，但是由于眾多非目的節點都接收到數據包并參與了數據包的轉發，導致網絡開銷太大，數據傳輸率低，甚至造成廣播風暴[12]。

1NCR協議算法原理

NCR協議將隨機網絡編碼算法應用于網絡中除源節點以外的所有中間節點。編碼系數均在有限域GF(q)[13]上隨機選取，且對節點數據包進行線性組合[14]，因此該算法也稱隨機線性網絡編碼算法。解碼時采用高斯消元法，通過求解編碼系數組成的線性方程組來恢復原始消息，文獻[14]已經證明只要有限域GF(q)足夠大，就可以使目的節點的全局編碼矩陣滿秩，從而能夠以較高概率完成解碼操作。

在隨機線性網絡編碼算法中，各中間節點先將要發送的數據包進行編碼，形成新的組合再發送出去，所有其他節點收到足夠的已編碼數據包進行再編碼并轉發出去，當目的節點收到足夠多的編碼包后，就可以解碼得出原始數據包。因此各節點輸入端收到的一定數量的已編碼數據包，是原始數據包的線性組合。

用理論模型描述如下：在有向無環網絡G=(V,E)中，源節點S∈V，接收節點T∈V，具有單位容量的鏈路e∈E，廣播容量h是發送節點和接收節點間所有割的容量中的最小值，x1,...,xh為源符號，g(e1),...,g(eh)為有限域GF(q)上全局編碼向量，數據包中的每個元素編碼后得到的線性組合y和帶有隨機系數的向量g(e)(編碼向量)，線性組合y可以表示為：

(1)

通常取q=2n，局部編碼向量的元素在有限域GF(2n)上隨機選擇，所以只要全局編碼向量g(e1),...,g(eh)的矩陣Gt秩為h，接收節點T就可以恢復出源符號x1,...,xh。

假設數據包能夠攜帶N個符號，每條鏈路上的符號y(e)流可以被分組成向量y(e)=[y1(e),y2(e),....,yN(e)]，源符號xi流被分組成向量xi=[xi,1,xi,2,...,xi,N]，則任何接收端可以從接收的數據包中恢復出h個源向量x1,...,xh，如式(2)：

(2)

解碼方案采用漸進式譯碼方法[15]，每收到一個編碼數據包，對由系數和線性組合組成的增廣矩陣使用行初等變換化簡一次，使增廣矩陣變為行最簡型階梯矩陣，收到第h個線性分組經過化簡后，原來的增廣矩陣的左側為h階單位矩陣右側為化簡后得到的原始數據分塊，如式(3)所示，以h=4為例，如圖1說明解碼過程。

(3)

圖1　解碼化簡結果

NCR協議流程如圖2所示。

圖2　協議流程圖

2協議仿真結果分析

采用NS-2仿真軟件對NCR協議進行仿真，應用層為CBR數據流。建立50個節點的隨機網絡拓撲結構，如圖3所示，各節點服從[0,1]均勻分布，隨機分布在1 km×1 km的矩形區域內。

由于NS-2仿真軟件提供的無線電環境的傳輸模型不適用于水聲傳輸模型，需對其修改。式(4)是無方向性發射聲源，W為平均輻射聲功率。參考基準聲壓pref一般取1 μPa，對應的水中基準聲強式(5)代入式(4)可以得到距離為r處的輻射聲功率式(6)：

(4)

(5)

(6)

式中，發送因子ρ為每個節點發送數據包數量與接收的新數據包數量的比[16]。ρ決定了節點的轉發概率每個節點能發送數據包的數量，對于NCR協議而言，若ρ值較大節點的解碼率越高，若ρ值較小可能使節點不能收到足夠數量的編碼包用于解碼。因此，仿真部分給出各協議發送因子ρ在[0,1]范圍內不同取值下的仿真結果。

圖3　隨機拓撲結構

以下是在節點數為50的隨機網絡拓撲結構對數據包投遞率、數據包投遞平均時延、協議開銷和沖突率的仿真結果。曲線“NC”表示NCR協議的仿真結果，曲線“Flooding”表示泛洪協議的仿真結果。

圖4是數據包投遞率的仿真結果，可以看出NCR協議投遞率一直高于泛洪協議，大約提高了20%~50%，投遞率隨發送因子的增長快速增長，且在發送因子較小時就可以得到很高的數據包投遞率，圖5是數據包投遞平均時延的仿真結果。

圖4　數據包投遞率　　　圖5　數據包投遞平均時延　仿真結果　仿真結果

從圖5可以看出NCR協議傳輸時延遠低于泛洪協議，隨著發送因子的增長時延相對平穩，沒有明顯增加。因此在節點數量較多的網絡中，NCR協議能夠顯著提高數據包傳輸率，從而降低傳輸時延。

圖6是協議開銷的仿真結果，可以看出，在相同發送因子的條件下NCR協議開銷始終比泛洪協議的協議開銷大。主要原因是節點對數據包編碼后，將每個數據包的編碼向量作為頭部信息添加到數據頭部，從而有大量攜帶編碼向量的數據包進行轉發，使協議開銷相對增大；而泛洪協議的網絡開銷主要是大量重復數據包發送造成的。

圖7是數據包沖突率的仿真結果，可以看出，在節點數為50的隨機網絡拓撲結構中，接收到的數據包數量較小時NCR協議和泛洪協議的沖突率相當；但當網絡節點傳輸數據增大時，NCR協議的沖突率明顯低于泛洪協議。因此，NCR協議通過數據包編碼，提高了數據包轉發機會，減少了數據包碰撞，降低了沖突率，有效降低了數據丟包，具有較高的可靠性。

圖6　協議開銷仿真結果　　圖7　沖突率仿真結果

3結束語

將隨機網絡編碼方法應用于節點廣播數據包中，采用NS-2仿真工具模擬仿真了水聲網絡環境中隨機拓撲結構中的對NCR協議網絡數據傳輸。在節點數量為50的隨機網絡拓撲結構中，與傳統的泛洪協議相比，NCR協議的數據包投遞率大約提高了20%~50%，時延降低了大約50%~60%，同時數據包的沖突率也減小。網絡編碼方法使網絡性能獲得改善。

仿真結果表明，NCR協議比傳統泛洪方法，明顯提升了數據包投遞率，減小了投遞平均時延，降低數據包的沖突率，從而提高了傳輸可靠性以及傳輸效率，雖然在協議開銷方面有所增加，但提高了數據傳輸效率，減小了數據包發生沖突的可能性，總體網絡性能獲得明顯改善。

參考文獻

[1]Yang Xiao.水下聲傳感器網絡[M].北京：國防工業出版社，2012:1-3.

[2]郭忠文，羅漢江，洪 鋒，等.水下無線傳感器網絡的研究進展[J].計算機研究與進展，2010：377-389.

[3]鄭少仁，王海濤，趙志峰，等.Ad Hoc網絡技術[M].北京：人民郵電出版社，2002：20-30.

[4]盧開澄，盧華明.圖論及其應用(第2版)[M].北京：清華大學出版社，1995.

[5]Ahlswede R， Cai N，Li S Y R，et al.Network information flow[J].IEEE Transactions on Information Theory，2000：1204-1216.

[6]Lucani D E，Milica Stojanovic.Underwater Acoustic Networks :Channel Models and Network Coding based Lower Bound to Transmission Power for Multicast[J].IEEE Journal of Selected Areas in Communications，2008,26(9):1708 - 1719，December.

[7]徐明.水聲傳感器網中基于網絡編碼的多徑路由協議[J].傳感器與微系統,2013,32(1)：58-61.

[8]徐明，劉廣鐘.三維水聲傳感器網絡中基于網絡編碼的地理位置路由協議[J].傳感技術學報,2012,25(11):45-48.

[9]Guo Zheng，Wang Bing，Xie Peng，et al.Efficient Error Recovery with Network Coding in Underwater Sensor Networks [J].Ad Hoc Networks，2009，7(4):791-802.

[10]樊昌信.通信原理[M].北京：國防工業出版社，2006.

[11]柯志亨，程榮祥，鄧德雋. NS2仿真實驗-多媒體和無線網絡通信[M].北京：電子工業出版社，2009.

[12]劉磊，李 宇，張春華，等.水聲通信網競爭式介質訪問控制協議的研究[J].應用聲學,2014,33(3):19-22.

[13]黃佳慶，Li Zong-peng.網絡編碼原理[M].北京：國防工業出版社,2012.

[14]Neubauer A，Freudenberger J，Kuhn V.編碼理論——算法、結構和應用[M].北京：人民郵電出版社，2009.

[15]Katti S，Rahul H S，Hu Wen-jun，et al.XORs in the Air: Practical Wireless Network Coding[J].IEEE/ACM Transactions on Networking，2008: 497-510.

[16]Fasolo E，Rossi M，Widmer J，et al.On MAC Scheduling and Packet Combination Strategies for Practical Random Network Coding，In Communications[C]∥ ICC’07.IEEE international conference on，IEEE，2007：3582-3589.

Research on Routing Protocol of Underwater Acoustic Network
Based on Network Coding Technique

ZHU Lin，JIANG Zhi-hao，LI Xun

(Unit 91635，PLA，Beijing 102249,China)

Abstract：Duo to some disadvantages of underwater acoustical communication，such as low transmission speed，long delay and etc.，this paper proposes a random network coding technique in underwater acoustical environment，and simulate NCR(Network Coding Routing) protocol with NS-2.The results show that not only the packet delivery ratio is increased by 20% through 50%，but also the packet delivery average delay is reduced by 50% through 60%.The network performance has been improved.

Key words：underwater acoustic communication；network coding；protocol；delivery ratio

作者簡介：祝琳(1987—)，女，助理工程師，主要研究方向：通信工程。江志浩(1981—)，男，工程師，主要研究方向：無線電通信。

收稿日期：2015-07-16

中圖分類號：TN929.3

文獻標識碼：A

文章編號：1003-3114(2016)01-24-4

doi:10.3969/j.issn.1003-3114.2016.01.06

引用格式：祝琳,江志浩，李迅.基于網絡編碼技術的水聲網絡路由協議研究[J].無線電通信技術,2016,42(1):24-27.