UWSNs中基于深度的抑制空洞路由優化算法*

潘永東

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

UWSNs中基于深度的抑制空洞路由優化算法*

潘永東

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

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

水下無線傳感器網絡； 路由； 空洞路由； 能耗； 深度

0 引 言

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

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

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

1 網絡模型和問題描述

假定整個網絡的節點集為N，每個節點的通信半徑為rc，其中傳感節點集表示為Nn={n1,n2,…,n|Nn|}、聲納浮標集表示為Ns={s1,s2,…,s|Ns|}，即N=Nn∪Ns。

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

圖1 網絡模型

此外，由于信宿節點具有大的通信范圍，一個信宿節點所接收的數據包可認為所有信宿節點均接收了該數據包。本文UWSNs協議中定義了兩類節點：錨節點和轉發節點。錨節點固定在水域中，而轉發節點隨機分布于水域中。錨節點感測數據，通過轉發節點將數據傳輸到信宿。一旦信宿節點接收了數據包，即將數據傳輸至控制中心。

多數UWSNs路由協議均存在路由空洞問題。這些協議通常引用兩個指標決策路由：當前節點的深度和下一跳候選轉發節點的深度。在決策路由時，先分別計算源節點距離當前節點的深度差和當前節點距離下一跳候選轉發節點的深度差，再計算兩個深度差之和，和越大，轉發數據包的優先權就越大。這種決策路由方式容易遭遇路由空洞。

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

圖2 路由空洞示例

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

2 DSVR協議

DSVR協議主要分為初始階段、數據轉發階段和信息更新階段，如圖3所示。網絡建立階段用于構建候選轉發節點集，并計算物理距離和跳數；數據轉發階段用于產生下一跳轉發節點，并轉發數據包；而信息更新階段用于實時更新物理距離和跳數信息。

圖3 DSVR協議框架

2.1 初始階段

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

圖4 HELLO包格式

圖中，ID表示節點的唯一標識號；鄰居節點數表示節點的鄰居數；物理距離和跳數分別表示節點離信宿的物理距離和跳數。

圖5 物理距離和跳數計算示例

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

2.2 數據轉發階段

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

(1)

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

計算Γi集內的每一個節點權值后，并按權值從高到低排序，形成集i?Γi。權值最高的節點最先轉發數據包，即成為下一跳轉發節點。權值最高的節點的排序值p為零。為了抑制冗余包，采用定時器定時方式轉發數據包。

2.3 定時器設置

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

(2)

式中rmax為節點的最大傳輸距離；pk為參數。

2.4DSVR協議的數據包轉發流程

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

圖6 DSVR協議數據包轉發流程

3 性能分析

3.1 仿真參數

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

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

(3)

式中Etotal為網絡總能量；NPackets為平均每個節點產生的數據包數。

3.2 數值分析

3.2.1 數據包傳遞率

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

圖7 數據包傳遞率

3.2.2 單個數據包的能耗

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

圖8 單一數據包的能耗

3.2.3 端到端傳輸時延

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

圖9 端到端傳輸時延

4 結束語

針對水下傳感網絡的路由問題，提出了基于深度的抑制路由空洞的水下傳感網路由DSVR協議。DSVR協議利用節點深度緩解路由空洞問題。DSVR協議計算深度信息構建候選轉發節點集，再計算這些節點的權值，其包含物理距離和跳數以及鄰居數。實驗數據表明：DSVR協議有效地降低能耗，并提高了數據包傳遞率，緩解了路由空洞問題。

[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] 徐 琨，劉宏立.室內環境下無線傳感網絡路徑衰減特性[J].傳感器與微系統,2016,35(21):11-15.

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

[5] 王 驥,林杰華，謝仕義.基于無線傳感網絡的環境監測系統[J].傳感技術學報，2015，28(1):1732-740.

[6] 周 凱,孟利民，華驚宇.基于Grover路由策略的無線傳感網絡剩余容量構造與研究[J].傳感技術學報，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

江蘇省軟科學研究計劃資助項目(142400410179)

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