水聲傳感器網(wǎng)中基于網(wǎng)絡(luò)編碼的多徑路由協(xié)議*

徐 明

(1.上海海事大學(xué) 信息工程學(xué)院，上海201306;2.復(fù)旦大學(xué) 上海市智能信息處理重點(diǎn)實(shí)驗(yàn)室，上海200433)

0 引 言

水聲傳感器網(wǎng)是一門新興的網(wǎng)絡(luò)技術(shù)，在海洋環(huán)境監(jiān)測(cè)、水下導(dǎo)航和水下預(yù)警等領(lǐng)域有著廣泛的應(yīng)用［1，2］。路由協(xié)議的效率是水聲傳感器網(wǎng)研究的一個(gè)重要課題。由于聲波在水中的傳播速度比無線電波在空氣中的傳播速度小5 個(gè)數(shù)量級(jí)，并且水聲信道的帶寬非常有限，水聲傳感器網(wǎng)實(shí)際可獲得的鏈路容量比無線傳感網(wǎng)低很多［3］，這將嚴(yán)重影響水聲傳感器網(wǎng)的網(wǎng)絡(luò)吞吐量。此外，由于傳感器節(jié)點(diǎn)部署在無人值守的惡劣水下環(huán)境，造成更換電池非常困難。這對(duì)路由協(xié)議的能量有效性提出很高的要求。

多徑路由是一種提高無線傳感器網(wǎng)傳輸帶寬的有效手段，并已成為自組織網(wǎng)絡(luò)路由的研究熱點(diǎn)。按需多徑路由(on－demand multi－path routing，ODMR)協(xié)議［4］的仿真實(shí)驗(yàn)結(jié)果表明:進(jìn)行多徑路由時(shí)，采用2 條路由路徑的效果最優(yōu)。在定向泛洪路由(directional flooding－based routing，DFR)協(xié)議［5］中，源節(jié)點(diǎn)將根據(jù)鄰居節(jié)點(diǎn)到自身和目標(biāo)節(jié)點(diǎn)方向的夾角以及鏈路質(zhì)量來選擇路由轉(zhuǎn)發(fā)的中繼節(jié)點(diǎn)，這樣可以在一定程度上減少網(wǎng)絡(luò)中冗余數(shù)據(jù)包的數(shù)量，從而減輕網(wǎng)絡(luò)負(fù)擔(dān)。但是，當(dāng)鏈路質(zhì)量不好時(shí)，會(huì)有多個(gè)鄰居節(jié)點(diǎn)參與同一數(shù)據(jù)包的轉(zhuǎn)發(fā)，造成DFR 的性能急劇下降。多徑虛擬匯聚(multipath virtual sink，MVS)節(jié)點(diǎn)［6］技術(shù)將水聲傳感器網(wǎng)分為多個(gè)簇，每個(gè)簇?fù)碛幸粋€(gè)或多個(gè)聚合點(diǎn)，這些聚合點(diǎn)形成了一個(gè)小型的網(wǎng)狀網(wǎng)絡(luò)，并連接到本地匯聚節(jié)點(diǎn)，各個(gè)本地匯聚節(jié)點(diǎn)組成了一個(gè)虛擬的匯聚節(jié)點(diǎn)，本地匯聚節(jié)點(diǎn)之間通過高速射頻通信的方式鏈接到一起。MVS通過將冗余數(shù)據(jù)包沿著多條路徑轉(zhuǎn)發(fā)到多個(gè)本地匯聚節(jié)點(diǎn)的方式提高網(wǎng)絡(luò)的可靠性和吞吐量，因此，冗余數(shù)據(jù)包重傳造成的能量消耗問題較為突出。

針對(duì)傳統(tǒng)多徑路由存在的問題，本文提出一種基于網(wǎng)絡(luò)編碼的多徑路由協(xié)議(multi－path routing protocol using network coding，MRNC)。MRNC 在路由過程中通過在主鏈路和后備鏈路之間動(dòng)態(tài)切換創(chuàng)造更多的網(wǎng)絡(luò)編碼機(jī)會(huì)進(jìn)行數(shù)據(jù)傳輸，從而優(yōu)化網(wǎng)絡(luò)帶寬利用率，并降低冗余數(shù)據(jù)包重傳造成的能量消耗。

1 網(wǎng)絡(luò)模型

考慮一個(gè)由n 個(gè)分布在監(jiān)測(cè)區(qū)域的水聲傳感器節(jié)點(diǎn)組成的水聲傳感器網(wǎng) G(V，E)，其中，V 是節(jié)點(diǎn)集，E 是邊集。這些水聲傳感器節(jié)點(diǎn)相對(duì)于水聲信號(hào)傳播速度而言具有較低的移動(dòng)性。每個(gè)水聲傳感器節(jié)點(diǎn)都被分配一個(gè)三維坐標(biāo)(x，y，z)，并且這些節(jié)點(diǎn)都具有相同大小的水聲通信半徑r。假設(shè)所有的水聲傳感器節(jié)點(diǎn)都配備傳感設(shè)備，能夠從外部環(huán)境中采集數(shù)據(jù)，并且可以通過一跳或者多跳傳輸?shù)姆绞綄⒉杉降臄?shù)據(jù)聚集到匯聚節(jié)點(diǎn)上。匯聚節(jié)點(diǎn)是生成數(shù)據(jù)聚集結(jié)果的節(jié)點(diǎn)，也是數(shù)據(jù)傳輸?shù)哪繕?biāo)位置。一條由m 個(gè)節(jié)點(diǎn)組成的路徑 p 表示為 p ={n1，n2，…，nm}，其中，(ni，ni+1)∈E，i∈［1，…，m －1］，路徑 p 的長(zhǎng)度表示為 L(p)。節(jié)點(diǎn)之間的通信是雙向的，即如果(ni，nj)∈E，則(nj，ni)∈E。如果從源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)之間存在l 條路徑p1，p2，…，pl，那么這 l 條路徑表示為 χ = {p1，p2，…，pl}，其長(zhǎng)度為L(zhǎng)(χ)=∑L(pi)。

定義1 三維歐拉空間中任意2 個(gè)節(jié)點(diǎn)nu和nv之間的距離由函數(shù) δ(u，v)給出

當(dāng)nu和nv之間的歐拉距離小于r 時(shí)，則nu和nv成為鄰居節(jié)點(diǎn)，并且nu和nv之間存在一條鏈路。

考慮2 個(gè)最小跳數(shù)距離h 上的節(jié)點(diǎn)nu和nv，存在閾值u(h)和v(h)使得u(h)≤δ(u，v)≤v(h)。其中，閾值的大小依賴于水聲傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)密度ρ，并且對(duì)任意h ＞0存在

為了建立水聲傳感器網(wǎng)中節(jié)點(diǎn)的狀態(tài)模型，本文用隨機(jī)變量X(u)來表示節(jié)點(diǎn)nu的狀態(tài)，X(u)服從如下的Bernoulli 分布

定義2 節(jié)點(diǎn) nu將一個(gè)數(shù)據(jù)包正確轉(zhuǎn)發(fā)的概率Pr(X(u)=1)稱為節(jié)點(diǎn)nu的數(shù)據(jù)轉(zhuǎn)發(fā)率，用γ(nu)來表示。

路由路徑p={n1，n2，…，nm}的狀態(tài)模型用Y(p)來表示，Y(p)服從如下分布

定義3 給定源節(jié)點(diǎn)nu和目標(biāo)節(jié)點(diǎn)nv，則水聲傳感器模型定義為

其中，λ ＞0，并且 ε ＞0;λ 為水聲信號(hào)幅值;k 為水聲傳感器參數(shù);ε 為一個(gè)預(yù)定義參數(shù)，用來處理源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)位置相同的情況。

2 路由協(xié)議

針對(duì)水聲傳感器網(wǎng)絡(luò)的路由協(xié)議具有自身的特殊性。首先，水聲傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的計(jì)算、存儲(chǔ)和通信能力相對(duì)較弱，因此，在其上不能實(shí)現(xiàn)復(fù)雜的路由協(xié)議;其次，水聲傳感器網(wǎng)絡(luò)以數(shù)據(jù)為中心，這與傳統(tǒng)網(wǎng)絡(luò)根據(jù)節(jié)點(diǎn)編址選擇路徑不同。

本文提出的MRNC 協(xié)議包含2 個(gè)階段:路由發(fā)現(xiàn)階段和數(shù)據(jù)包傳輸階段。在路由發(fā)現(xiàn)階段，源節(jié)點(diǎn)發(fā)出的數(shù)據(jù)包到達(dá)匯聚節(jié)點(diǎn)后，在返回的過程中會(huì)為主鏈路建立相應(yīng)的后備鏈路。在數(shù)據(jù)包傳輸階段，為了最大限度地降低數(shù)據(jù)傳輸帶寬消耗，MRNC 采用COPE(coding opportunistically)［7］協(xié)議的異或(XOR)編碼方式對(duì)數(shù)據(jù)進(jìn)行網(wǎng)絡(luò)編碼，通過在主鏈路和后備鏈路之間動(dòng)態(tài)切換創(chuàng)造更多的網(wǎng)絡(luò)編碼機(jī)會(huì)進(jìn)行數(shù)據(jù)傳輸。

假設(shè)鏈路丟包率為e，則鏈路的可靠性為1 －e，那么，將一個(gè)編碼包從源節(jié)點(diǎn)經(jīng)過一條h 跳的路徑成功轉(zhuǎn)發(fā)到匯聚節(jié)點(diǎn)的概率為(1 －e)h，而成功發(fā)送一組數(shù)據(jù)包的概率rs可用公式(7)計(jì)算得到

這組包中每個(gè)原始數(shù)據(jù)包在路徑中被轉(zhuǎn)發(fā)的次數(shù)N 由公式(8)計(jì)算得到

因?yàn)橐粋€(gè)編碼包的包頭要攜帶編碼系數(shù)，所以，一個(gè)編碼包的長(zhǎng)度是原始數(shù)據(jù)包的長(zhǎng)度與全局編碼向量域的長(zhǎng)度之和。假設(shè)全局編碼向量占b 個(gè)字節(jié)，則全局編碼向量域的長(zhǎng)度為bK;若一個(gè)數(shù)據(jù)包的長(zhǎng)度為lp，那么一個(gè)數(shù)據(jù)包與一個(gè)編碼包的長(zhǎng)度之比為lp/(lp+bK)。

由于節(jié)點(diǎn)在路由的過程中實(shí)際消耗的能量與數(shù)據(jù)包轉(zhuǎn)發(fā)的次數(shù)呈正比關(guān)系，對(duì)于任一數(shù)據(jù)包，令Ti代表該數(shù)據(jù)包從第i－1 個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)到第i 個(gè)節(jié)點(diǎn)的平均次數(shù)，則數(shù)據(jù)包轉(zhuǎn)發(fā)的總平均次數(shù)T 可由公式(9)計(jì)算得到

圖1 描繪了基于網(wǎng)絡(luò)編碼的多徑路由協(xié)議中數(shù)據(jù)包編碼和傳輸?shù)倪^程。其中，ns為源節(jié)點(diǎn)，nd為匯聚節(jié)點(diǎn)。節(jié)點(diǎn)np對(duì)主鏈路上的數(shù)據(jù)包A 和后備鏈路上的數(shù)據(jù)包B 進(jìn)行異或編碼。傳輸完成后用各自偵聽到的數(shù)據(jù)包進(jìn)行解碼操作來恢復(fù)相應(yīng)的數(shù)據(jù)包。

圖1 基于網(wǎng)絡(luò)編碼的多徑路由示意圖Fig 1 Diagram of MRNC

聲波信號(hào)在淺海(水深小于100 m 的水域)和深海(水深大于100 m 的水域)的傳播方式并不相同。在淺海中，聲波信號(hào)的傳輸被限制在海面和海底構(gòu)成的圓柱體中，其傳播過程中能量消耗可表示為

其中，δ(u，v)為發(fā)送方和接收方之間的距離，m;α 為吸收系數(shù)，dB/km;εt為能耗，dB。

在深海中，聲波主要以球狀擴(kuò)散為主，傳播過程中能量消耗主要由球面擴(kuò)散和吸收損失兩部分造成，可表示為

從公式(10)和公式(11)中可以看出:在淺海和深海中聲波傳播的能量消耗主要由與距離相關(guān)的傳輸衰減以及與頻率相關(guān)的吸收損失造成。

3 仿真實(shí)驗(yàn)與分析

本文采用Aqua－Sim［8］作為評(píng)測(cè)水聲傳感器網(wǎng)中多源異質(zhì)數(shù)據(jù)流突發(fā)檢測(cè)性能的模擬器。

表1 給出了仿真實(shí)驗(yàn)的參數(shù)與默認(rèn)值。此外，本文將根據(jù)以下指標(biāo)來評(píng)價(jià)3 種路由協(xié)議DFR，MVS 和MRNC 的性能。

表1 實(shí)驗(yàn)參數(shù)與默認(rèn)值Tab 1 Experimental parameters and default values

在第1 組實(shí)驗(yàn)中，本文比較了不同路由協(xié)議中網(wǎng)絡(luò)吞吐量與節(jié)點(diǎn)數(shù)量之間的關(guān)系。如圖2 所示，3 種路由協(xié)議的網(wǎng)絡(luò)吞吐量都與節(jié)點(diǎn)數(shù)量呈正比。其中，MRNC 的網(wǎng)絡(luò)吞吐量在節(jié)點(diǎn)數(shù)量相同的情況下超過其他2 種路由協(xié)議。MVS 的網(wǎng)絡(luò)吞吐量比DFR 平均高出5.6%，而MRNC 的網(wǎng)絡(luò)吞吐量比MVS 平均高出25.7%。

圖2 網(wǎng)絡(luò)吞吐量與節(jié)點(diǎn)數(shù)量的關(guān)系Fig 2 Relation between network throughput and number of nodes

在第2 組實(shí)驗(yàn)中，本文比較了不同路由協(xié)議中網(wǎng)絡(luò)吞吐量與平均數(shù)據(jù)傳送率之間的關(guān)系。如圖3 所示，3 種路由協(xié)議的網(wǎng)絡(luò)吞吐量均與平均數(shù)據(jù)傳送率呈正比。其中，MRNC 的網(wǎng)絡(luò)吞吐量在平均數(shù)據(jù)傳送率相同的情況下明顯超過其他兩種路由協(xié)議。此外，在平均數(shù)據(jù)傳送率較小時(shí)，MVS 的網(wǎng)絡(luò)吞吐量略高于DFR，而MRNC 的網(wǎng)絡(luò)吞吐量比DFR 和MVS 平均分別高出31.7%和11.8%。

圖3 網(wǎng)絡(luò)吞吐量與數(shù)據(jù)傳送率的關(guān)系Fig 3 Relation between network throughput and data transfer rate

在第3 組實(shí)驗(yàn)中，本文比較了不同路由協(xié)議中能量消耗與節(jié)點(diǎn)數(shù)量之間的關(guān)系。如圖4 所示，3 種路由協(xié)議的能量消耗都與節(jié)點(diǎn)數(shù)量呈正比。其中，MRNC 的能量消耗在節(jié)點(diǎn)數(shù)量相同的情況下低于其他兩種路由協(xié)議，并且增長(zhǎng)的速率也更為緩和。MVS 的能量消耗比 DFR 平均低10.7%，而MRNC 的能量消耗比MVS 平均低28.9%。

圖4 能量消耗與節(jié)點(diǎn)數(shù)量的關(guān)系Fig 4 Relation between energy consumption and number of nodes

在第4 組實(shí)驗(yàn)中，本文比較了不同路由協(xié)議中能量消耗與平均跳步距離(hops)之間的關(guān)系。如圖5 所示，3 種路由協(xié)議的能量消耗都與平均跳步距離呈正比。其中，MRNC的能量消耗在平均跳步距離相同的情況下低于其他2 種路由協(xié)議。MVS 的能量消耗比DFR 平均低17.8%，而MRNC的能量消耗比MVS 平均低21.3%。

圖5 能量消耗與平均跳步距離的關(guān)系Fig 5 Relation between of energy consumption and average hop distances

4 結(jié) 論

針對(duì)水聲傳感器網(wǎng)通信帶寬低、節(jié)點(diǎn)能耗高的特點(diǎn)，提出一種基于網(wǎng)絡(luò)編碼的多徑路由協(xié)議。該協(xié)議在路由過程中通過在主鏈路和后備鏈路之間動(dòng)態(tài)切換創(chuàng)造更多的網(wǎng)絡(luò)編碼機(jī)會(huì)進(jìn)行數(shù)據(jù)傳輸，從而優(yōu)化網(wǎng)絡(luò)帶寬利用率，并降低冗余數(shù)據(jù)包重傳造成的能量消耗。仿真結(jié)果表明:基于網(wǎng)絡(luò)編碼的多徑路由協(xié)議可以在提高水聲傳感器網(wǎng)吞吐量的同時(shí)，有效降低網(wǎng)絡(luò)能量消耗。

［1］ 鐘永信，黃建國(guó)，韓 晶.基于空間喚醒的水聲傳感器網(wǎng)絡(luò)節(jié)能路由協(xié)議［J］.電子與信息學(xué)報(bào)，2011，33(6):1326 －1331.

［2］ Manjula R，Sunilkumar S.Issues in underwater acoustic sensor networks［J］.International Journal of Computer and Electrical Engineering，2011，3(1):101 －110.

［3］ Jornet J，Stojanovic M，Zorzi M.On joint frequency and power allocation in a cross－layer protocol for underwater acoustic networks［J］.IEEE Journal of Oceanic Engineering，2010，35(4):936 －947.

［4］ Nasipuri A，Castaneda R，Das S R.Performance of multipath routing for on－demand protocols in mobile Ad Hoc networks［J］.Mobile Networks and Applications，2001，6(4):339 － 349.

［5］ Hwang D Y.DFR:Directional flooding－based routing protocol for underwater sensor networks［C］∥Proceedings of OCEANS 2008，Kobe，Japan，IEEE，2008.

［6］ Seah W G，Tan H X.Multipath virtual Sink architecture for underwater sensor networks［C］∥Proceedings of OCEANS 2006，Boston，USA，IEEE，2006.

［7］ Katti S，Rahul H，Hu W J，et al.Xors in the air:Practical wireless network coding［J］.IEEE/ACM Transaction on Networking，2008，16(3):497 －510.

［8］ Xie P，Zhou Z，Peng Z，et al.Aqua－sim:An NS－2 based simulator for underwater ssensor networks［C］∥Proceedings of OCEANS 2009，Biloxi，USA，IEEE，2009.