潘永東

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

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

潘永東

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

圖2 路由空洞示例

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

2 DSVR協(xié)議

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

圖3 DSVR協(xié)議框架

2.1 初始階段

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

圖4 HELLO包格式

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

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

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

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

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

(1)

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

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

2.3 定時器設(shè)置

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

(2)

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

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

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

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

3 性能分析

3.1 仿真參數(shù)

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

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

(3)

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

3.2 數(shù)值分析

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

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

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

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

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

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

3.2.3 端到端傳輸時延

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

圖9 端到端傳輸時延

4 結(jié)束語

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

[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ǎng)絡(luò)路徑衰減特性[J].傳感器與微系統(tǒng),2016,35(21):11-15.

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

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

[6] 周 凱,孟利民，華驚宇.基于Grover路由策略的無線傳感網(wǎng)絡(luò)剩余容量構(gòu)造與研究[J].傳感技術(shù)學(xué)報，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é)研究計劃資助項目(142400410179)

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