徐 明

(1.上海海事大學 信息工程學院，上海201306;2.復旦大學 上海市智能信息處理重點實驗室，上海200433)

0 引 言

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

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

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

1 網(wǎng)絡模型

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

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

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

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

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

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

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

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

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

2 路由協(xié)議

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實驗與分析

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

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

表1 實驗參數(shù)與默認值Tab 1 Experimental parameters and default values

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

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

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

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

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

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

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

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

4 結(jié) 論

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

［1］ 鐘永信，黃建國，韓 晶.基于空間喚醒的水聲傳感器網(wǎng)絡節(jié)能路由協(xié)議［J］.電子與信息學報，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.