UWSNs中基于深度的抑制空洞路由優(yōu)化算法*

潘永東

(南京理工大學(xué) 計(jì)算機(jī)工程學(xué)院，江蘇 南京 211169)

UWSNs中基于深度的抑制空洞路由優(yōu)化算法*

潘永東

(南京理工大學(xué)計(jì)算機(jī)工程學(xué)院，江蘇南京211169)

針對(duì)傳統(tǒng)的水下無(wú)線傳感器網(wǎng)絡(luò)(UWSNs)的位置路由存在路由空洞問(wèn)題，提出了基于深度的抑制空洞路由(DSVR)的UWSNs路由協(xié)議。DSVR協(xié)議通過(guò)融合跳數(shù)、物理距離和鄰居數(shù)多個(gè)指標(biāo)決策路由。為了提高通信可靠和緩解路由空洞，DSVR協(xié)議選擇具有最小跳數(shù)路徑、最少鄰居數(shù)的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。同時(shí)，DSVR協(xié)議利用定時(shí)器抑制冗余數(shù)據(jù)包。仿真結(jié)果表明：提出的DSVR協(xié)議能有效地提高數(shù)據(jù)包傳遞率，并降低端到端傳輸時(shí)延以及能耗。

水下無(wú)線傳感器網(wǎng)絡(luò)； 路由； 空洞路由； 能耗； 深度

0 引 言

近期，水下無(wú)線傳感器網(wǎng)絡(luò)(underwater wireless sensor networks，UWSNs)的相關(guān)研究得到廣泛關(guān)注，UWSNs也已廣泛應(yīng)用于軍事勘察、海域環(huán)境監(jiān)測(cè)、港口監(jiān)控等[1～5]。與陸地WSNs不同， 在UWSNs中，傳感節(jié)點(diǎn)實(shí)時(shí)監(jiān)測(cè)水域環(huán)境，并將感測(cè)數(shù)據(jù)傳輸至水面的信宿節(jié)點(diǎn)，即聲納浮標(biāo)[6，7]，水下傳感節(jié)點(diǎn)以聲通信方式向信宿傳輸數(shù)據(jù)，而信宿節(jié)點(diǎn)收集數(shù)據(jù)后，再以無(wú)線通信將數(shù)據(jù)傳輸至控制中心，進(jìn)而完成水域數(shù)據(jù)的采集。

典型的UWSNs路由協(xié)議有VAPR(void-aware pressure routing)[8]和HydroCast(hydraulic pressure based anycast)[9]。VAPR路由利用序列號(hào)、跳數(shù)以及深度信息選擇路由。而HydroCast屬混合組播路由。HydroCast路由結(jié)合了地理位置路由和機(jī)會(huì)路由特性，依據(jù)節(jié)點(diǎn)深度調(diào)整，進(jìn)而最大化地理位置路由的優(yōu)勢(shì)。兩種路由均需對(duì)節(jié)點(diǎn)進(jìn)行定位，在估計(jì)節(jié)點(diǎn)位置過(guò)程中必然增加了控制開(kāi)銷。

為此，本文提出了基于深度的抑制空洞路由(depth-based suppressing void routing,DSVR)的路由協(xié)議。DSVR協(xié)議先利用節(jié)點(diǎn)深度篩選候選轉(zhuǎn)發(fā)節(jié)點(diǎn)，并計(jì)算節(jié)點(diǎn)的權(quán)值，依據(jù)權(quán)值擇優(yōu)選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。實(shí)驗(yàn)數(shù)據(jù)表明：提出的DSVR協(xié)議有效解決了路由空洞問(wèn)題，并提高了數(shù)據(jù)包傳輸率。

1 網(wǎng)絡(luò)模型和問(wèn)題描述

假定整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)集為N，每個(gè)節(jié)點(diǎn)的通信半徑為rc，其中傳感節(jié)點(diǎn)集表示為Nn={n1,n2,…,n|Nn|}、聲納浮標(biāo)集表示為Ns={s1,s2,…,s|Ns|}，即N=Nn∪Ns。

考慮一個(gè)多信宿節(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)，如圖1所示。整個(gè)網(wǎng)絡(luò)由信宿、傳感節(jié)點(diǎn)組成。信宿節(jié)點(diǎn)浮于水面，一旦部署，位置不變。信宿節(jié)點(diǎn)也是目的節(jié)點(diǎn)，具有聲通信和無(wú)線通信兩種模式。其中，信宿節(jié)點(diǎn)利用聲通信收集傳感節(jié)點(diǎn)的數(shù)據(jù)，而無(wú)線通信用于連接其他信宿節(jié)點(diǎn)。

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

此外，由于信宿節(jié)點(diǎn)具有大的通信范圍，一個(gè)信宿節(jié)點(diǎn)所接收的數(shù)據(jù)包可認(rèn)為所有信宿節(jié)點(diǎn)均接收了該數(shù)據(jù)包。本文UWSNs協(xié)議中定義了兩類節(jié)點(diǎn)：錨節(jié)點(diǎn)和轉(zhuǎn)發(fā)節(jié)點(diǎn)。錨節(jié)點(diǎn)固定在水域中，而轉(zhuǎn)發(fā)節(jié)點(diǎn)隨機(jī)分布于水域中。錨節(jié)點(diǎn)感測(cè)數(shù)據(jù)，通過(guò)轉(zhuǎn)發(fā)節(jié)點(diǎn)將數(shù)據(jù)傳輸?shù)叫潘?。一旦信宿?jié)點(diǎn)接收了數(shù)據(jù)包，即將數(shù)據(jù)傳輸至控制中心。

多數(shù)UWSNs路由協(xié)議均存在路由空洞問(wèn)題。這些協(xié)議通常引用兩個(gè)指標(biāo)決策路由：當(dāng)前節(jié)點(diǎn)的深度和下一跳候選轉(zhuǎn)發(fā)節(jié)點(diǎn)的深度。在決策路由時(shí)，先分別計(jì)算源節(jié)點(diǎn)距離當(dāng)前節(jié)點(diǎn)的深度差和當(dāng)前節(jié)點(diǎn)距離下一跳候選轉(zhuǎn)發(fā)節(jié)點(diǎn)的深度差，再計(jì)算兩個(gè)深度差之和，和越大，轉(zhuǎn)發(fā)數(shù)據(jù)包的優(yōu)先權(quán)就越大。這種決策路由方式容易遭遇路由空洞。

如圖2所示，節(jié)點(diǎn)S為源節(jié)點(diǎn)，而節(jié)點(diǎn)N1/N2/N3/N4均在其傳輸范圍內(nèi)。當(dāng)節(jié)點(diǎn)S向其傳輸范圍內(nèi)的節(jié)點(diǎn)傳輸了數(shù)據(jù)包后，這些節(jié)點(diǎn)均會(huì)接收到該數(shù)據(jù)包。由于節(jié)點(diǎn)N1/N2位于源節(jié)點(diǎn)S下面，其深度大于源節(jié)點(diǎn)S的深度。因此，節(jié)點(diǎn)丟失從源節(jié)點(diǎn)S處接收的數(shù)據(jù)包。而節(jié)點(diǎn)N3/N4深度低于源節(jié)點(diǎn)S，成為潛在轉(zhuǎn)發(fā)節(jié)點(diǎn)(potential forwar-der nodes,PFNs)。

圖2 路由空洞示例

然而，當(dāng)節(jié)點(diǎn)N4接收了數(shù)據(jù)包后，向其傳輸范圍內(nèi)的節(jié)點(diǎn)廣播數(shù)據(jù)包，由于節(jié)點(diǎn)N6的深度低于節(jié)點(diǎn)N5，因此，節(jié)點(diǎn)N6將成為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。但是，當(dāng)節(jié)點(diǎn)N6接收了數(shù)據(jù)包后，其傳輸范圍內(nèi)無(wú)節(jié)點(diǎn)的深度低于其深度，出現(xiàn)無(wú)轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇的困境，即出現(xiàn)了路由空洞問(wèn)題。 從圖2可知，實(shí)際上是存在從源節(jié)點(diǎn)S至信宿的傳輸路徑。然而，由于決策路由方式的原因，并沒(méi)有考慮此條路徑。為此，本文針對(duì)此類路由空洞問(wèn)題，提出了新的路由協(xié)議。

2 DSVR協(xié)議

DSVR協(xié)議主要分為初始階段、數(shù)據(jù)轉(zhuǎn)發(fā)階段和信息更新階段，如圖3所示。網(wǎng)絡(luò)建立階段用于構(gòu)建候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集，并計(jì)算物理距離和跳數(shù)；數(shù)據(jù)轉(zhuǎn)發(fā)階段用于產(chǎn)生下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，并轉(zhuǎn)發(fā)數(shù)據(jù)包；而信息更新階段用于實(shí)時(shí)更新物理距離和跳數(shù)信息。

圖3 DSVR協(xié)議框架

2.1 初始階段

每個(gè)節(jié)點(diǎn)先識(shí)別自己的一跳鄰居集，并通過(guò)HELLO包，計(jì)算其距信宿節(jié)點(diǎn)的跳數(shù)和物理距離。HELLO包的具體格式如圖4所示。

圖4 HELLO包格式

圖中，ID表示節(jié)點(diǎn)的唯一標(biāo)識(shí)號(hào)；鄰居節(jié)點(diǎn)數(shù)表示節(jié)點(diǎn)的鄰居數(shù)；物理距離和跳數(shù)分別表示節(jié)點(diǎn)離信宿的物理距離和跳數(shù)。

圖5 物理距離和跳數(shù)計(jì)算示例

以圖5為例,具體過(guò)程如下：1)每個(gè)信宿節(jié)點(diǎn)廣播HELLO包，接收節(jié)點(diǎn)就計(jì)算離信宿節(jié)點(diǎn)的跳數(shù)，并依據(jù)到達(dá)時(shí)間差(time difference of arrival,TDOA)估計(jì)離信宿的物理距離。一旦獲取了這些信息，節(jié)點(diǎn)就將這些信息加載到HELLO包；2)再重播,類似地，一旦接收了重播HELLO包，節(jié)點(diǎn)就計(jì)算距廣播節(jié)點(diǎn)的距離以及跳數(shù)，然后再將信息載入HELLO包；3)重播，直到網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)均獲取了其離信宿節(jié)點(diǎn)的物理距離和跳數(shù)。

2.2 數(shù)據(jù)轉(zhuǎn)發(fā)階段

一旦接收了數(shù)據(jù)包，判斷是否屬于集Γi內(nèi)節(jié)點(diǎn)。若不是，則丟棄;否則，攜帶數(shù)據(jù)包，并計(jì)算其權(quán)值。權(quán)值隱含了離信宿節(jié)點(diǎn)的跳數(shù)、節(jié)點(diǎn)度以及距離。假定節(jié)點(diǎn)j為數(shù)據(jù)包接收節(jié)點(diǎn)，而節(jié)點(diǎn)i為數(shù)據(jù)包發(fā)送節(jié)點(diǎn)。那么節(jié)點(diǎn)j的權(quán)值Wj如式(1)所示

(1)

式中Dist(i,j)為節(jié)點(diǎn)i距節(jié)點(diǎn)j的距離;Hop(j)為節(jié)點(diǎn)j距信宿節(jié)點(diǎn)的跳數(shù);Neighor(j)為節(jié)點(diǎn)j的一跳鄰居數(shù)。

計(jì)算Γi集內(nèi)的每一個(gè)節(jié)點(diǎn)權(quán)值后，并按權(quán)值從高到低排序，形成集i?Γi。權(quán)值最高的節(jié)點(diǎn)最先轉(zhuǎn)發(fā)數(shù)據(jù)包，即成為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。權(quán)值最高的節(jié)點(diǎn)的排序值p為零。為了抑制冗余包，采用定時(shí)器定時(shí)方式轉(zhuǎn)發(fā)數(shù)據(jù)包。

2.3 定時(shí)器設(shè)置

Tk=pk(rmax-Dist(k,i))

(2)

式中rmax為節(jié)點(diǎn)的最大傳輸距離；pk為參數(shù)。

2.4DSVR協(xié)議的數(shù)據(jù)包轉(zhuǎn)發(fā)流程

當(dāng)節(jié)點(diǎn)i需要傳輸數(shù)據(jù)包，首先計(jì)算候選轉(zhuǎn)發(fā)集Γi，再計(jì)算集內(nèi)節(jié)點(diǎn)的權(quán)值，再進(jìn)行排序，構(gòu)建有序的i，然后節(jié)點(diǎn)i將i信息嵌入數(shù)據(jù)包，再?gòu)V播。接收了該數(shù)據(jù)包，節(jié)點(diǎn)首先判斷本身是否是i內(nèi)節(jié)點(diǎn)，如果不是，丟棄;否則，依據(jù)本身的權(quán)值，設(shè)置定時(shí)器，進(jìn)行計(jì)時(shí)，并監(jiān)聽(tīng)是否有其他節(jié)點(diǎn)轉(zhuǎn)發(fā)該數(shù)據(jù)包，若有，則放棄競(jìng)爭(zhēng)本次轉(zhuǎn)發(fā)數(shù)據(jù)包的機(jī)會(huì)；反之，待計(jì)時(shí)完畢，立即轉(zhuǎn)發(fā)數(shù)據(jù)包，具體流程如圖6所示。

圖6 DSVR協(xié)議數(shù)據(jù)包轉(zhuǎn)發(fā)流程

3 性能分析

3.1 仿真參數(shù)

利用Matlab R2012b建立仿真平臺(tái)[10]?？紤]10 km×10 km×10 km網(wǎng)絡(luò)區(qū)域內(nèi)，傳感節(jié)點(diǎn)|Nn|=100～500，且最大傳輸范圍為2 km。信宿節(jié)點(diǎn)數(shù)|Ns|=9均勻分布于水域。此外，數(shù)據(jù)率為16 kbps，聲傳輸速率為1 500 m/s。同時(shí)，一旦部署信宿節(jié)點(diǎn)，其不再移動(dòng)。而傳感節(jié)點(diǎn)沿著垂直二維方向移動(dòng)，節(jié)點(diǎn)的移動(dòng)速度從1～3 m/s變化。每次實(shí)驗(yàn)重復(fù)50次，取平均值作為最終數(shù)據(jù)。運(yùn)行時(shí)間為3 600 s。

為了更充分地分析DSVR路由性能，選擇(weighting depth and forwarding area division-depth based routing,WDFAD-DBR)作為參照[11]。同時(shí)考慮數(shù)據(jù)包傳輸率(packet delivery ratio,PDR)、單個(gè)數(shù)據(jù)包的能耗(energy tax)以及端到端傳輸時(shí)延(average end-to-end delay,E2ED)作為性能指標(biāo)。其中PDR等于信宿節(jié)點(diǎn)成功接收的數(shù)據(jù)包數(shù)與源節(jié)點(diǎn)所發(fā)送的數(shù)據(jù)包數(shù)之比；而單一數(shù)據(jù)包的能耗等于將數(shù)據(jù)包從源節(jié)點(diǎn)傳輸至信宿所消耗的平均能量，其定義如式(3)所示

(3)

式中Etotal為網(wǎng)絡(luò)總能量；NPackets為平均每個(gè)節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)包數(shù)。

3.2 數(shù)值分析

3.2.1 數(shù)據(jù)包傳遞率

圖7給出了兩個(gè)協(xié)議的數(shù)據(jù)包傳遞率隨節(jié)點(diǎn)數(shù)的變化情況,可知:數(shù)據(jù)包傳遞率隨節(jié)點(diǎn)數(shù)的增加呈增長(zhǎng)趨勢(shì)。這主要是因?yàn)椋汗?jié)點(diǎn)數(shù)的增加，提高了傳輸范圍內(nèi)的節(jié)點(diǎn)數(shù)，進(jìn)而提升了選擇更優(yōu)的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的概率，提高了數(shù)據(jù)包傳輸成功率。然而當(dāng)節(jié)點(diǎn)數(shù)大于300后，數(shù)據(jù)包傳遞率隨節(jié)點(diǎn)數(shù)增加的幅度逐漸變緩。說(shuō)明，僅增加節(jié)點(diǎn)數(shù)，并不能大幅度地提高數(shù)據(jù)包傳遞率。原因在于：節(jié)點(diǎn)數(shù)越多，節(jié)點(diǎn)間的傳輸干擾越大，影響了數(shù)據(jù)包傳遞率。此外，與WDFAD-DBR協(xié)議相比，提出的DSVR協(xié)議的數(shù)據(jù)包傳遞率得到有效地提高，平均提高了近2 %。這也充分說(shuō)明DSVR協(xié)議通過(guò)深度、節(jié)點(diǎn)權(quán)值決策路由，提高了數(shù)據(jù)傳輸性能。

圖7 數(shù)據(jù)包傳遞率

3.2.2 單個(gè)數(shù)據(jù)包的能耗

圖8分析了能耗隨節(jié)點(diǎn)數(shù)的變化情況,可知，在節(jié)點(diǎn)數(shù)較少時(shí)，即稀疏網(wǎng)絡(luò)時(shí)，DSVR協(xié)議的能耗遠(yuǎn)低于WDFAD-DBR協(xié)議。WDFAD-DBR協(xié)議在稀疏網(wǎng)絡(luò)內(nèi)消耗了大量的能量，存在高的數(shù)據(jù)包丟失率。而DSVR協(xié)議具有穩(wěn)定的、短的傳輸路徑。在節(jié)點(diǎn)從250增加至500時(shí)，兩個(gè)協(xié)議的能耗相近。原因在于：節(jié)點(diǎn)數(shù)的增加，加大了傳輸干擾，最終加大能耗。

圖8 單一數(shù)據(jù)包的能耗

3.2.3 端到端傳輸時(shí)延

分析節(jié)點(diǎn)數(shù)對(duì)端到端傳輸時(shí)延的影響，如圖9所示,可知，DSVR協(xié)議的端到端傳輸時(shí)延遠(yuǎn)低于WDFAD-DBR協(xié)議。在WDFAD-DBR協(xié)議中，每個(gè)候選轉(zhuǎn)發(fā)節(jié)點(diǎn)均需要維持一定的時(shí)延，因此，產(chǎn)生了較大的傳輸時(shí)延。相反，DSVR協(xié)議將最優(yōu)的轉(zhuǎn)發(fā)節(jié)點(diǎn)的定時(shí)時(shí)延設(shè)為零。換而言之，最優(yōu)的節(jié)點(diǎn)一旦接收了數(shù)據(jù)包，即轉(zhuǎn)發(fā)數(shù)據(jù)，縮減了傳輸時(shí)延。

圖9 端到端傳輸時(shí)延

4 結(jié)束語(yǔ)

針對(duì)水下傳感網(wǎng)絡(luò)的路由問(wèn)題，提出了基于深度的抑制路由空洞的水下傳感網(wǎng)路由DSVR協(xié)議。DSVR協(xié)議利用節(jié)點(diǎn)深度緩解路由空洞問(wèn)題。DSVR協(xié)議計(jì)算深度信息構(gòu)建候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集，再計(jì)算這些節(jié)點(diǎn)的權(quán)值，其包含物理距離和跳數(shù)以及鄰居數(shù)。實(shí)驗(yàn)數(shù)據(jù)表明：DSVR協(xié)議有效地降低能耗，并提高了數(shù)據(jù)包傳遞率，緩解了路由空洞問(wèn)題。

[1] Akyildiz I F,Pompili D,Melodia T.Melodia underwater acoustic sensor networks:Research challenge-s[J].Ad Hoc Network,2015,3(3):257-279.

[2] Kong J,Cui J H,Wu D,et al.Building underwater Ad-Hoc networks and sensor networks for large scale real-time aquatic applications[C]∥Proc of IEEE MILCOM,2015:1535-1541.

[3] 徐 琨，劉宏立.室內(nèi)環(huán)境下無(wú)線傳感網(wǎng)絡(luò)路徑衰減特性[J].傳感器與微系統(tǒng),2016,35(21):11-15.

[4] 王華東，王大羽.能量均衡的無(wú)線傳感器網(wǎng)絡(luò)均勻分簇策略[J].激光雜志,2015,36(6):158-162.

[5] 王 驥,林杰華，謝仕義.基于無(wú)線傳感網(wǎng)絡(luò)的環(huán)境監(jiān)測(cè)系統(tǒng)[J].傳感技術(shù)學(xué)報(bào)，2015，28(1):1732-740.

[6] 周 凱,孟利民，華驚宇.基于Grover路由策略的無(wú)線傳感網(wǎng)絡(luò)剩余容量構(gòu)造與研究[J].傳感技術(shù)學(xué)報(bào)，2015，28(2):249-253.

[7] Ayaz M,Baig I, Azween A,et al.A survey on routing techniques in underwater wireless sensor networks[J].J Network Computing Application,2011,34(6):1908-1927.

[8] Noh Y,Lee U,Wang P,et al.VAPR:Void-aware pressure routing for underwater sensor networks[J].IEEE Transactions on Mobile Computing,2013,12(5):895-908.

[9] Yougtae N,Uichin L,Saewoom L HydroCast:Pressure routing for underwater sensor networks [J].IEEE Transactions on Vehi-cular Technology,2016,65(1):333-334.

[10] Yu H,Yao N,Wang T.WDFAD-DBR:Weighting depth-and forwarding area division DBR routing protocol for UASNs[J].Ad Hoc Networks,2016,27(3):2048-2062.

[11] Zuba Z S M,Fagan M,Cui J.A resilient pressure routing scheme for underwater acoustic networks[C]∥The 57th IEEE Global Telecommunication Conference,2014:637-642.

Depth-basedsuppressingvoidroutingoptimalalgorithminUWSNs*

PAN Yong-dong

(SchoolofComputerEngineering,JinlingInstituteofTechnology,Nanjing211169,China)

Aiming at problem that in underwater wireless sensor networks(UWSNs),traditional geographic routing exists routing void,depth-based suppressing void routing(DSVR)for UWSNs is proposed.DSVR protocol makes a routing decision by taking into account multiple metrics including hop-count,physical distance and number of neighbors.In order to improve the reliability of communication and eliminate routing void,DSVR protocol selects the nodes with the minimum hop count and the minimum number of neighbors as the next hop forwarding node.At the same time,the DSVR protocol uses timers to suppress redundant data packets.Simulation results show that proposed DSVR protocol improves packet delivery ratio reduce end-to-end delay and energy consumption.

underwater wireless sensor networks(UWSNs); routing; void routing; energy consumption; depth

10.13873/J.1000—9787(2017)11—0139—04

TN 914

A

1000—9787(2017)11—0139—04

2017—08—28

江蘇省軟科學(xué)研究計(jì)劃資助項(xiàng)目(142400410179)

潘永東(1975-)，男，碩士，高級(jí)工程師，主要從事云計(jì)算、大數(shù)據(jù)相關(guān)研究工作。