水下無線傳感器網絡DBR路由協(xié)議研究

黃 芬，陳名松

(桂林電子科技大學 信息與通信學院，廣西 桂林541004)

隨著世界各國海洋開發(fā)和海洋軍事領域的飛速發(fā)展，水下無線傳感器網絡及其應用成為新的研究熱點［1］。其路由協(xié)議的研究必不可少。由于水下無線傳感器網絡的特性，提供一種可靠的、可擴展的有效路由協(xié)議是非常大的挑戰(zhàn)。近年來，學者們針對水下無線傳感器網絡具有動態(tài)拓撲結構、通信帶寬低、傳播時延大、誤碼率高等特點，提出了許多路由協(xié)議，尤其是基于地理位置的路由協(xié)議成為研究重點，但是它們大部分都需要借助昂貴的GPS定位。而這是水下無線傳感器網絡的另一大難題。

1 DBR網絡模型

DBR(Depth Based Routing)［2］采用的是多Sink節(jié)點水下無線傳感器網絡結構［3］，見圖1。在網絡中有兩種傳感器節(jié)點:一種是Sink節(jié)點，部署在水面上;另一種是普通傳感器節(jié)點(UW_sensor node)，部署在感興趣的水下3D區(qū)域內。Sink節(jié)點配備了RF調制解調器和水聲調制解調器。前者用于Sink節(jié)點之間以及Sink節(jié)點和接收站之間的通信;后者用于Sink節(jié)點與UW_sensor node之間的通信。UW_sensor node只有水聲調制解調器，并且每個UW_sensor node都配備有深度傳感器，它不僅可以將探測到的數(shù)據發(fā)送給鄰節(jié)點，還可以將鄰節(jié)點發(fā)送過來的數(shù)據轉發(fā)出去。DBR路由協(xié)議只考慮Sink節(jié)點和UW_sensor node之間的通信，不考慮Sink節(jié)點之間的通信。由于所有Sink節(jié)點都配有RF調制解調器，如果任何一個Sink節(jié)點成功接收到數(shù)據包，都可以通過無線電傳播很快地將數(shù)據包轉發(fā)給其他Sink節(jié)點和接收站。因此只要數(shù)據包成功到達任何一個Sink節(jié)點，則認為其成功到達目的節(jié)點。

圖1 多Sink節(jié)點水下傳感器網絡拓撲結構

2 DBR路由算法

2.1 基本思想

DBR路由算法是一種簡單的基于節(jié)點深度信息的水下傳感器網絡路由協(xié)議，網絡中所有節(jié)點的決定都取決于節(jié)點深度信息。不同于其他基于地理位置的路由協(xié)議，如VBF［4］，HH-VBF［5］，F(xiàn)BR［6］，DFR［7］等，DBR不需要知道節(jié)點的全三維位置信息，只需要知道節(jié)點的局部深度信息。節(jié)點深度信息可以很容易通過安裝在節(jié)點中的深度傳感器獲得。

DBR采用貪婪轉發(fā)策略將數(shù)據包發(fā)送給水面Sink節(jié)點。試圖選擇離目的節(jié)點最近的節(jié)點，即深度最小的節(jié)點為下一跳轉發(fā)節(jié)點;同時防止其他鄰節(jié)點轉發(fā)同樣的數(shù)據包來減小能耗。在這個過程中，數(shù)據包越接近目的節(jié)點，轉發(fā)節(jié)點的深度越小。在空洞不存在的情況下，如果減小每一跳轉發(fā)節(jié)點的深度，數(shù)據包可以到達水面Sink節(jié)點。當某個節(jié)點有數(shù)據要發(fā)送時，簡單地通過廣播洪泛的形式將數(shù)據發(fā)送出去。其他節(jié)點接收到數(shù)據之后，借助于深度傳感器計算它們的深度并與發(fā)送節(jié)點的深度做比較。如果其深度小于發(fā)送節(jié)點的深度，則具有轉發(fā)數(shù)據的資格;對收到的數(shù)據進行相應的處理，并同樣通過廣播的形式將數(shù)據轉發(fā)出去，否則將簡單丟棄數(shù)據包。

2.2 路由表的維護

DBR中數(shù)據分組包括4個域，具體如圖2所示。

圖2 數(shù)據包格式

包序列號是由源節(jié)點分配給每個包的特殊序列號，和源節(jié)點ID一起組成數(shù)據包的Unique packet ID，用于區(qū)別不同的數(shù)據包。節(jié)點深度Depth是最近一次發(fā)送某個數(shù)據包的節(jié)點深度。Depth值逐跳更新，即數(shù)據包每被轉發(fā)一次，Depth值更新一次。

在DBR中，為了減小轉發(fā)節(jié)點的數(shù)量和控制數(shù)據包的重復發(fā)送，每個節(jié)點必須維護priority queue Q1和packet history buffer Q2兩張路由表。節(jié)點通過維護Q1和Q2這兩個序列，可以減少轉發(fā)節(jié)點數(shù)目，控制轉發(fā)路徑，保證節(jié)點在一段時間內對相同的數(shù)據包只發(fā)送一次。網絡初始化時，每個節(jié)點的Q1和Q2序列都為空。Q1是臨時路由表，用來設置數(shù)據包轉發(fā)優(yōu)先級的，當數(shù)據包成功發(fā)送出去之后釋放;Q2用來記錄節(jié)點最近發(fā)送數(shù)據包的情況。每當節(jié)點成功發(fā)送一個數(shù)據包后，則將此數(shù)據包的Unique packet ID寫入Q2中。當Q2已滿，最近最少被訪問的Unique packet ID將被最新的Unique packet ID取代。路由表Q1和Q2的路由條目如圖3所示。

圖3 由表Q1，Q2路由條目

節(jié)點接收到數(shù)據包之后，如果之前沒有發(fā)送過這個數(shù)據包(即Q2中無此包的記錄)，將此數(shù)據包寫入Q1中，并在holding time時間之后，將數(shù)據包轉發(fā)給深度更小的節(jié)點。若在holding time時間內，此數(shù)據包再次被接收到有兩種情況:第一，從深度更大的節(jié)點或同樣深度的節(jié)點再次接收到此包，丟棄此包并釋放Q1;第二，從深度更小的節(jié)點再次接收到此包，更新數(shù)據包，預計發(fā)送時間ST，ST值也是逐跳更新。節(jié)點將此數(shù)據包發(fā)送出去后，釋放Q1并將此包的Unique packet ID寫入Q2中。

2.3 轉發(fā)節(jié)點集的選擇

為了更好地控制轉發(fā)節(jié)點的數(shù)量，引進深度閾值dth參數(shù)。只有當上一跳節(jié)點與當前節(jié)點的深度差Δd(Δd=dp-dc)大于dth時，當前節(jié)點才具有轉發(fā)資格。dth的取值范圍為［-R，R)。當dth=0時，說明比當前節(jié)點深度低的節(jié)點都具有轉發(fā)資格;當dth=-R時，相當于全局洪泛協(xié)議。dth值是數(shù)據包成功傳遞率與網絡平均能耗之間的一個權衡，當dth值小時，數(shù)據包成功傳遞率高，能耗也大;dth值大時，數(shù)據包成功傳遞率低，能耗也低。所以需要合理地選擇dth值，保證數(shù)據包成功傳遞率高，能耗也低，以滿足網絡需求。

2.4 數(shù)據包轉發(fā)優(yōu)先級

DBR采用數(shù)據包轉發(fā)優(yōu)先級的方法來抑制冗余數(shù)據報的傳輸。數(shù)據包轉發(fā)優(yōu)先級是通過Q1中的數(shù)據包預計轉發(fā)時間ST來體現(xiàn)的。節(jié)點的ST越早，其優(yōu)先級越高。每個接收到數(shù)據包的節(jié)點，首先計算數(shù)據包的預計發(fā)送時間ST，并寫入到優(yōu)先序列Q1中。包預計發(fā)送時間ST與Holding Time(HT)和接收到數(shù)據包的時刻有關(ST=接收到數(shù)據包的時間+HT)。即當某個節(jié)點接收到一個數(shù)據包時，不是立即將數(shù)據包發(fā)送出去，而是先保持HT時間再發(fā)送。HT和上一跳節(jié)點與當前接收節(jié)點的距離Δd有關。HT的計算式如

式中:τ=R/c;R為節(jié)點最大傳輸距離;c為水聲傳播速度，約等于1 500 m/s;Δd為上一跳節(jié)點與當前節(jié)點的深度差。當δ取值較小時，節(jié)點HT較長，參與數(shù)據包轉發(fā)的節(jié)點較少，能耗減少，但是端到端延時會變長。

2.5 數(shù)據轉發(fā)策略

在DBR中，每個節(jié)點在數(shù)據包中增加了一個深度信息。接收到數(shù)據包的節(jié)點，只有其深度小于發(fā)送節(jié)點的深度時，才具備轉發(fā)數(shù)據的資格。DBR試圖選擇Depth值最小的鄰節(jié)點作為轉發(fā)節(jié)點，同時防止其他鄰節(jié)點轉發(fā)同樣的數(shù)據包來減小能耗。

DBR中數(shù)據包轉發(fā)算法總結如下:當某個節(jié)點接收到數(shù)據包時，它首先根據上一跳節(jié)點和當前節(jié)點的深度信息與深度閾值判斷自己是否具有數(shù)據轉發(fā)資格，如果沒有轉發(fā)資格，則查詢Q1中是否存在數(shù)據包，若不存在，丟棄收到的數(shù)據包;否則，丟棄數(shù)據包并刪除Q1中數(shù)據包。如果具有轉發(fā)資格，在查詢Q2中是否存在這個數(shù)據包，若Q2中已存在這個數(shù)據包，則丟棄;否則查詢Q1中是否存在數(shù)據包，若不存在，則更新數(shù)據包中Depth域為當前節(jié)點深度dc，及根據當前系統(tǒng)時間(即接收到數(shù)據包p的時間)及HT計算出數(shù)據包預計發(fā)送時間，然后將數(shù)據包及其預計發(fā)送時間ST寫入到Q1中。否則，從Q1中的數(shù)據包中提取出此數(shù)據包先前的預計發(fā)送時間STp，用min{ST，STp}更新Q1中的包預計發(fā)送時間域。如某節(jié)點接收到數(shù)據包P，其轉發(fā)流程圖如圖4所示。

圖4數(shù)據包轉發(fā)流程圖

圖5 說明了數(shù)據包轉發(fā)情況。節(jié)點S是發(fā)送節(jié)點，節(jié)點n1，n2，n3，n4和n5是S的所有一跳鄰節(jié)點。當節(jié)點S有數(shù)據包要發(fā)送時，將數(shù)據包廣播發(fā)送出去，所有鄰節(jié)點都能接收到這個數(shù)據包。節(jié)點n4和n5在節(jié)點S下面(ds-dni＜dth，i=4，5)，dth=0，不具備轉發(fā)資格，丟棄此數(shù)據包。盡管n1，n2和n3都具備轉發(fā)資格，但是根據節(jié)點轉發(fā)優(yōu)先級策略，可知n1的優(yōu)先級高于n2和n3，更適合轉發(fā)數(shù)據。n1將最先將數(shù)據包轉發(fā)出去，n2和n3在它們的數(shù)據包預計發(fā)送時間內將接收到節(jié)點n1發(fā)送的數(shù)據包，通過檢查Q2可以抑制數(shù)據包的發(fā)送。

圖5 轉發(fā)節(jié)點的選擇

3 擴展分析

DBR協(xié)議的關鍵思想是網絡中所有節(jié)點轉發(fā)數(shù)據包的決定取決于節(jié)點深度信息。在采用貪婪轉發(fā)算法的時候，節(jié)點依據一定的標準選擇一個鄰節(jié)點作為數(shù)據包的下一跳節(jié)點。DBR相對于其他基于地理位置信息的水下傳感器網絡路由協(xié)議，不需要知道節(jié)點全三維位置信息，只需要知道節(jié)點的局部深度信息。同時，DBR采用的是多Sink節(jié)點網絡結構，繼承了此網絡節(jié)點的特點并未帶來額外的網絡成本。但是DBR仍然存在一些問題，這些問題會影響網絡的性能。

第一，DBR采用洪泛傳播機制，如果每個節(jié)點都參與數(shù)據的轉發(fā)，將增加網絡的復雜度，產生大量的冗余數(shù)據，導致過多的能量消耗，且降低了網絡帶寬利用率。同時所有接收到數(shù)據包的節(jié)點每次都要計算他們的深度信息，同樣會消耗網絡能量。第二，DBR網絡的性能與網絡密度有關。比如在某些區(qū)域節(jié)點部署稀疏，可能由于候選節(jié)點的深度都比發(fā)送節(jié)點大，導致發(fā)送節(jié)點找不到轉發(fā)節(jié)點，從而進入到不斷尋找候選節(jié)點的死循環(huán)中，即存在局部路由空洞現(xiàn)象。即使有些比發(fā)送節(jié)點深度大的節(jié)點可以成功轉發(fā)數(shù)據到目的節(jié)點，但是DBR中并沒用提出處理局部路由空洞現(xiàn)象的機制。第三，網絡中每個節(jié)點必須配置深度傳感器，增加網絡成本，同時深度傳感器也要消耗一部分能量，會降低網絡壽命。

Uichin Lee等人針對DBR路由協(xié)議存在隱藏終端和局部路由空洞現(xiàn)象，提出了Hydrocast協(xié)議［8］。在轉發(fā)節(jié)點集的選擇策略中考慮了如何避免隱藏終端現(xiàn)象，并提出了局部更低深度節(jié)點優(yōu)先路由恢復機制。但是Hydrocast協(xié)議同樣會出現(xiàn)多個轉發(fā)節(jié)點傳遞同一個數(shù)據包的現(xiàn)象，造成信息的冗余發(fā)送和節(jié)點能量的浪費。

Hydrocast協(xié)議利用局部拓撲信息，采用簡單的貪婪算法選擇最優(yōu)候選節(jié)點集，且不存在隱藏終端問題。具體工作如下:節(jié)點根據數(shù)據包到目的節(jié)點的最大期望(EPA)來選擇轉發(fā)節(jié)點集。EPA的大小與數(shù)據包傳遞率和節(jié)點到目的節(jié)點的距離有關。源節(jié)點選擇EPA值最大的節(jié)點ni作為轉發(fā)節(jié)點，如果ni的鄰節(jié)點通信范圍覆蓋了ni通信范圍的一半，這些鄰節(jié)點和ni便形成了一個轉發(fā)節(jié)點集。轉發(fā)節(jié)點集中的節(jié)點可以互相偵聽對方，因為它們之間的距離都小于最大傳輸距離R，這樣就保證不會出現(xiàn)隱藏終端現(xiàn)象。Hydrocast協(xié)議同樣采用數(shù)據包轉發(fā)優(yōu)先級的方法來抑制冗余數(shù)據包的傳輸。節(jié)點EPA值越大優(yōu)先級越高，EPA值最大的節(jié)點ni優(yōu)先級最高，即節(jié)點ni等待發(fā)送時間最短。轉發(fā)節(jié)點集中的節(jié)點在偵聽到高優(yōu)先級的節(jié)點時，將抑制自己的傳輸。

在Hydrocast協(xié)議中，當某節(jié)點所有一跳鄰節(jié)點的深度都比它的大時，此節(jié)點為局部極值點。每個局部極值點都維持著到比其深度更低的節(jié)點的恢復路徑，用于避免發(fā)生路由空洞。當數(shù)據包在局部極值點的一條路徑或多條路徑中斷時，可以通過路由恢復路徑走出空洞區(qū)域，回到貪婪轉發(fā)模式。局部更低深度節(jié)點優(yōu)先恢復機制(local lower-depth-first recovery)將抑制節(jié)點的洪泛，只有表面節(jié)點參加洪泛轉發(fā)。被鄰節(jié)點包圍的節(jié)點不是表面節(jié)點，否則就是表面節(jié)點。采用四面體的方法決定一個節(jié)點是否為表面節(jié)點，通過這種方法找到表面節(jié)點后，數(shù)據包將從一個表面節(jié)點傳輸?shù)搅硪粋€表面節(jié)點。經過幾次傳輸后，回到貪婪轉發(fā)模式。

VAPR協(xié)議［9］采用基于地理位置的路由協(xié)議中固有的信標機制(beaconing mechanism)來避免路由空洞現(xiàn)象。在每個信標數(shù)據包中嵌入節(jié)點的位置信息(在這是節(jié)點深度信息)，節(jié)點通過比較鄰節(jié)點與自己的深度，可以很容易地確定自己是否為局部極值點。當某節(jié)點為局部極值點時，廣播告知其一跳鄰節(jié)點。具體如下:每個節(jié)點都周期性地向其一跳鄰節(jié)點發(fā)送信標數(shù)據包，信標數(shù)據包中包括5個域:節(jié)點ID、節(jié)點深度、局部極值點標志位、節(jié)點界限、超時間隔。VAPR協(xié)議中信標數(shù)據包只需存儲一跳鄰節(jié)點的信息，所以每個信標數(shù)據包中只包括廣播這個信標數(shù)據包的信息。

DBMR協(xié)議［10］也是一種基于深度的路由協(xié)議，但不是采用洪泛傳播機制，所以不會像DBR協(xié)議一樣產生大量的冗余數(shù)據，導致過多的能量消耗，可以平衡網絡能耗，但是同樣存在路由空洞現(xiàn)象。它分為路由發(fā)現(xiàn)和數(shù)據轉發(fā)兩個過程。所有節(jié)點部署完后，就開始探測它們的深度，啟動路由發(fā)現(xiàn)過程選擇它們的下一跳節(jié)點，并存入路由表中。當某節(jié)點有數(shù)據包要發(fā)送時，將通過多跳的方式把數(shù)據包發(fā)送給Sink節(jié)點。具體做法如下:首先查詢路由表中是否有下一跳節(jié)點，若沒有則發(fā)送失敗，觸發(fā)路由發(fā)現(xiàn)過程找到下一跳節(jié)點，然后發(fā)送數(shù)據包。當鄰節(jié)點接收到數(shù)據包之后，首先檢查自己是否是Sink節(jié)點，如果是Sink節(jié)點，數(shù)據包成功接收;否則，繼續(xù)轉發(fā)數(shù)據包直到數(shù)據包被Sink節(jié)點成功接收。

4 小結

本文詳細描述了水下無線傳感器網絡基于深度信息路由協(xié)議DBR的特性。DBR協(xié)議是水下無線傳感器網絡中第一個基于深度信息的路由協(xié)議，采用貪婪轉發(fā)策略將數(shù)據包發(fā)送給水面Sink節(jié)點。雖然相對于其他基于地理位置的路由協(xié)議具有許多優(yōu)點，但還是存在很多不足，有待改進。在擴展分析中，詳細闡述了DBR路由協(xié)議的優(yōu)缺點及幾種DBR路由協(xié)議的改進算法。隨著該協(xié)議的不斷改進，可達到很好地節(jié)省節(jié)點能量的目的，延長整個網絡的壽命。

［1］朱昌平，韓慶邦.水聲通信基本原理與應用［M］.北京:電子工業(yè)出版社，2009:252-320.

［2］YAN Hai，SHI Zhijie，CUI Junhong.DBR:depth based routing for underwater sensor networks［C］//Proc.NETWORKING＇08.［S.l.］:Springer-Verlag Berlin，2008:16-1221.

［3］SEACH W K G，TAN H X.Multipath virtual sink architecture for underwater sensor networks［C］//Proc.OCEANS 2006-Asia Pacific.［S.l.］:IEEE Press，2006:1-6.

［4］XIE P，CUI J H，LAO L.VBF:vector-based forwarding protocol for Underwater Sensor Networks［EB/OL］.［2012-01-01］.http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.4529＆rep=rep1＆type=pdf.

［5］NICOLAOU N，ANDREW S，XIE P.Improving the robustness of location-based routing for Underwater Sensor networks［C］//Proc.IEEE OCEANS.［S.l.］:IEEE Press，2007:1-6.

［6］JORNET M，STOJANOVIC M，ZORZI M.Focused beam routing protocol for underwater acoustic networks［C］//Proc.WuWNeT＇08.New York，NY，USA:ACM，2008:75-82.

［7］HWANG D，KIM D.DFR:directional flooding-based routing protocol for underwater sensor networks［C］//Proc.IEEE OCEANS.［S.l.］:IEEE Press，2008:1-7.

［8］LEE U，WANG P，NOH Y，et al.Pressure routing for underwater sensor networks［C］//Proc.IEEE INFOCOM.［S.l.］:IEEE Press，2010:1-9.

［9］NOH Y，WANG P，LEE U，et al.VAPR:void aware pressure routing protocol［EB/OL］.［2011-09-30］.http://cs.ucla.edu/～ytnoh/publication/WuWNet10_VAPR.pdf.

［10］LIU Guangzhong，LI Zhibin.Depth-based multi-hop routing protocol for underwater sensor network［C］//Proc.2nd International Conference on Industrial Mechatronics and Automation.［S.l.］:IEEE Press，2010:268-270.