基于網(wǎng)絡(luò)編碼技術(shù)的水聲網(wǎng)絡(luò)路由協(xié)議研究

?！×眨竞?，李　迅

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

?

基于網(wǎng)絡(luò)編碼技術(shù)的水聲網(wǎng)絡(luò)路由協(xié)議研究

祝琳，江志浩，李迅

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

摘要：針對(duì)水聲通信傳輸速率低、時(shí)延大的缺點(diǎn)，提出在水聲環(huán)境下將隨機(jī)網(wǎng)絡(luò)編碼方法應(yīng)用于節(jié)點(diǎn)之間廣播通信，利用NS-2仿真軟件對(duì)網(wǎng)絡(luò)編碼路由協(xié)議NCR(Network Coding Routing)進(jìn)行仿真，并分別從投遞率、投遞時(shí)延、協(xié)議開銷和沖突率4個(gè)網(wǎng)絡(luò)性能評(píng)價(jià)指標(biāo)進(jìn)行了分析。發(fā)現(xiàn)在節(jié)點(diǎn)數(shù)量為50的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，與傳統(tǒng)的泛洪(Flooding)方式相比，NCR協(xié)議的數(shù)據(jù)包投遞率大約提高了20%～50%，網(wǎng)絡(luò)時(shí)延降低了大約50%～60%，NCR協(xié)議改善了水聲通信網(wǎng)絡(luò)傳輸效率，提高投遞率，提高能量利用效率和傳輸可靠性，時(shí)延和數(shù)據(jù)沖突率有效降低，網(wǎng)絡(luò)性能獲得明顯改善。

關(guān)鍵詞：水聲通信；網(wǎng)絡(luò)編碼；協(xié)議；投遞率

0引言

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

傳統(tǒng)水聲通信廣播信息一般采用泛洪法，泛洪方式是一種節(jié)點(diǎn)廣播數(shù)據(jù)方式[10，11]，這種方法主要特點(diǎn)是算法簡(jiǎn)單，尤其在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時(shí)常發(fā)生變化時(shí)適合使用該方法，但是由于眾多非目的節(jié)點(diǎn)都接收到數(shù)據(jù)包并參與了數(shù)據(jù)包的轉(zhuǎn)發(fā)，導(dǎo)致網(wǎng)絡(luò)開銷太大，數(shù)據(jù)傳輸率低，甚至造成廣播風(fēng)暴[12]。

1NCR協(xié)議算法原理

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

在隨機(jī)線性網(wǎng)絡(luò)編碼算法中，各中間節(jié)點(diǎn)先將要發(fā)送的數(shù)據(jù)包進(jìn)行編碼，形成新的組合再發(fā)送出去，所有其他節(jié)點(diǎn)收到足夠的已編碼數(shù)據(jù)包進(jìn)行再編碼并轉(zhuǎn)發(fā)出去，當(dāng)目的節(jié)點(diǎn)收到足夠多的編碼包后，就可以解碼得出原始數(shù)據(jù)包。因此各節(jié)點(diǎn)輸入端收到的一定數(shù)量的已編碼數(shù)據(jù)包，是原始數(shù)據(jù)包的線性組合。

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

(1)

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

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

(2)

解碼方案采用漸進(jìn)式譯碼方法[15]，每收到一個(gè)編碼數(shù)據(jù)包，對(duì)由系數(shù)和線性組合組成的增廣矩陣使用行初等變換化簡(jiǎn)一次，使增廣矩陣變?yōu)樾凶詈?jiǎn)型階梯矩陣，收到第h個(gè)線性分組經(jīng)過化簡(jiǎn)后，原來的增廣矩陣的左側(cè)為h階單位矩陣右側(cè)為化簡(jiǎn)后得到的原始數(shù)據(jù)分塊，如式(3)所示，以h=4為例，如圖1說明解碼過程。

(3)

圖1　解碼化簡(jiǎn)結(jié)果

NCR協(xié)議流程如圖2所示。

圖2　協(xié)議流程圖

2協(xié)議仿真結(jié)果分析

采用NS-2仿真軟件對(duì)NCR協(xié)議進(jìn)行仿真，應(yīng)用層為CBR數(shù)據(jù)流。建立50個(gè)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如圖3所示，各節(jié)點(diǎn)服從[0,1]均勻分布，隨機(jī)分布在1 km×1 km的矩形區(qū)域內(nèi)。

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

(4)

(5)

(6)

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

圖3　隨機(jī)拓?fù)浣Y(jié)構(gòu)

以下是在節(jié)點(diǎn)數(shù)為50的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)數(shù)據(jù)包投遞率、數(shù)據(jù)包投遞平均時(shí)延、協(xié)議開銷和沖突率的仿真結(jié)果。曲線“NC”表示NCR協(xié)議的仿真結(jié)果，曲線“Flooding”表示泛洪協(xié)議的仿真結(jié)果。

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

圖4　數(shù)據(jù)包投遞率　　　圖5　數(shù)據(jù)包投遞平均時(shí)延　仿真結(jié)果　仿真結(jié)果

從圖5可以看出NCR協(xié)議傳輸時(shí)延遠(yuǎn)低于泛洪協(xié)議，隨著發(fā)送因子的增長(zhǎng)時(shí)延相對(duì)平穩(wěn)，沒有明顯增加。因此在節(jié)點(diǎn)數(shù)量較多的網(wǎng)絡(luò)中，NCR協(xié)議能夠顯著提高數(shù)據(jù)包傳輸率，從而降低傳輸時(shí)延。

圖6是協(xié)議開銷的仿真結(jié)果，可以看出，在相同發(fā)送因子的條件下NCR協(xié)議開銷始終比泛洪協(xié)議的協(xié)議開銷大。主要原因是節(jié)點(diǎn)對(duì)數(shù)據(jù)包編碼后，將每個(gè)數(shù)據(jù)包的編碼向量作為頭部信息添加到數(shù)據(jù)頭部，從而有大量攜帶編碼向量的數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，使協(xié)議開銷相對(duì)增大；而泛洪協(xié)議的網(wǎng)絡(luò)開銷主要是大量重復(fù)數(shù)據(jù)包發(fā)送造成的。

圖7是數(shù)據(jù)包沖突率的仿真結(jié)果，可以看出，在節(jié)點(diǎn)數(shù)為50的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，接收到的數(shù)據(jù)包數(shù)量較小時(shí)NCR協(xié)議和泛洪協(xié)議的沖突率相當(dāng)；但當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)傳輸數(shù)據(jù)增大時(shí)，NCR協(xié)議的沖突率明顯低于泛洪協(xié)議。因此，NCR協(xié)議通過數(shù)據(jù)包編碼，提高了數(shù)據(jù)包轉(zhuǎn)發(fā)機(jī)會(huì)，減少了數(shù)據(jù)包碰撞，降低了沖突率，有效降低了數(shù)據(jù)丟包，具有較高的可靠性。

圖6　協(xié)議開銷仿真結(jié)果　　圖7　沖突率仿真結(jié)果

3結(jié)束語

將隨機(jī)網(wǎng)絡(luò)編碼方法應(yīng)用于節(jié)點(diǎn)廣播數(shù)據(jù)包中，采用NS-2仿真工具模擬仿真了水聲網(wǎng)絡(luò)環(huán)境中隨機(jī)拓?fù)浣Y(jié)構(gòu)中的對(duì)NCR協(xié)議網(wǎng)絡(luò)數(shù)據(jù)傳輸。在節(jié)點(diǎn)數(shù)量為50的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，與傳統(tǒng)的泛洪協(xié)議相比，NCR協(xié)議的數(shù)據(jù)包投遞率大約提高了20%~50%，時(shí)延降低了大約50%~60%，同時(shí)數(shù)據(jù)包的沖突率也減小。網(wǎng)絡(luò)編碼方法使網(wǎng)絡(luò)性能獲得改善。

仿真結(jié)果表明，NCR協(xié)議比傳統(tǒng)泛洪方法，明顯提升了數(shù)據(jù)包投遞率，減小了投遞平均時(shí)延，降低數(shù)據(jù)包的沖突率，從而提高了傳輸可靠性以及傳輸效率，雖然在協(xié)議開銷方面有所增加，但提高了數(shù)據(jù)傳輸效率，減小了數(shù)據(jù)包發(fā)生沖突的可能性，總體網(wǎng)絡(luò)性能獲得明顯改善。

參考文獻(xiàn)

[1]Yang Xiao.水下聲傳感器網(wǎng)絡(luò)[M].北京：國(guó)防工業(yè)出版社，2012:1-3.

[2]郭忠文，羅漢江，洪 鋒，等.水下無線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計(jì)算機(jī)研究與進(jìn)展，2010：377-389.

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

[4]盧開澄，盧華明.圖論及其應(yīng)用(第2版)[M].北京：清華大學(xué)出版社，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]徐明.水聲傳感器網(wǎng)中基于網(wǎng)絡(luò)編碼的多徑路由協(xié)議[J].傳感器與微系統(tǒng),2013,32(1)：58-61.

[8]徐明，劉廣鐘.三維水聲傳感器網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的地理位置路由協(xié)議[J].傳感技術(shù)學(xué)報(bào),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].北京：國(guó)防工業(yè)出版社，2006.

[11]柯志亨，程榮祥，鄧德雋. NS2仿真實(shí)驗(yàn)-多媒體和無線網(wǎng)絡(luò)通信[M].北京：電子工業(yè)出版社，2009.

[12]劉磊，李 宇，張春華，等.水聲通信網(wǎng)競(jìng)爭(zhēng)式介質(zhì)訪問控制協(xié)議的研究[J].應(yīng)用聲學(xué),2014,33(3):19-22.

[13]黃佳慶，Li Zong-peng.網(wǎng)絡(luò)編碼原理[M].北京：國(guó)防工業(yè)出版社,2012.

[14]Neubauer A，F(xiàn)reudenberger J，Kuhn V.編碼理論——算法、結(jié)構(gòu)和應(yīng)用[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

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

收稿日期：2015-07-16

中圖分類號(hào)：TN929.3

文獻(xiàn)標(biāo)識(shí)碼：A

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

doi:10.3969/j.issn.1003-3114.2016.01.06

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