基于局部更新策略的DBR路由協議改進算法*

石亞男，劉廣鐘

（上海海事大學 信息工程學院，上海 201306）

無線傳感器網絡是由密集型、低成本、隨機分布的集成有傳感器、數據處理單元和短程無線通信模塊的微小節點通過自組織方式構成的網絡[1]。借助節點中內置、形式多樣的傳感器可以實現對生活環境全方位地監測與控制，這也是下一代互聯網遠景規劃中較為重要的組成部分。無線傳感器網絡的自組織性和密集節點提供的容錯能力，使其不會因為某些節點的異常而導致整個系統的崩潰，非常適合在特殊時刻、特殊環境中快速構建信息基礎設施，因此有廣闊的應用前景[2-3]。

水聲傳感器網絡是無線傳感器網絡在水下一個重要應用[4]。水聲傳感器網絡是指將耗能低、具有一定通信距離的水下傳感器節點部署到指定海域中，利用節點的自組織能力自動建立起網絡[5]。水下傳感器網絡在海洋管理、資源保護、災害監測、海洋工程、海上生產作業和海洋軍事活動中起到促進作用，因此近年來在世界上得到了廣泛關注。

由于水聲傳感器網絡采用水聲信道通信，它與傳統的陸上傳感器網絡相比存在路徑失效、噪聲、多途干擾、傳輸延時和多普勒效應等一系列問題。此外，由于在水聲環境中節點的位置會不停地移動以及在水聲環境中節點不便于更換，因此節點部署、定位和低功耗設計等問題是水聲傳感器網絡研究的熱點問題?，F存的陸上傳感器網絡路由協議不能直接應用到水下傳感器網絡中，需要找到針對水聲通信特點的有效而又可行的路由協議。

DBR（Depth Based Routing）[6]協議是水下傳感器網絡中的一個基于深度信息的路由協議，網絡中所有節點的決定都取決于節點的深度信息。相對于其他基于地理位置信息的水下傳感器網絡路由協議，DBR不需要知道節點三維位置信息，只需要知道節點的局部深度信息。同時，DBR采用的是多Sink節點網絡結構，繼承了此網絡節點的特點并且未帶來額外的網絡成本。但是它采用洪泛傳播機制，多次計算深度信息會消耗網絡能耗；其次，DBR中如果節點之間的密度太小，可能出現路由空洞等問題。

本文主要在DBR協議的基礎上展開研究，提出一種基于局部更新策略的協議改進機制，并通過實驗證明了采用局部更新策略可以大大降低整個傳感器網絡的能量消耗。

1 DBR簡介

DBR采用的是多Sink節點水下無線傳感器網絡結構[7]，它由水面上的無線傳感器網絡和水下無線傳感器網絡兩部分組成，二者結合為一個整體網絡。

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

DBR在能量控制方面主要存在以下缺陷：(1)在DBR中，所有的節點都要時刻保持工作狀態，隨時準備好接收數據包并且做出相應的處理工作，在節點密度較大的情況下，這使得能量白白消耗，縮短了網絡的生存周期；(2)數據包轉發采用的是洪泛機制，如果每個節點都參與數據的轉發，將增加網絡的復雜度，產生大量的冗余數據，導致過多的節點能量消耗，并且降低了網絡的寬帶利用率。同時，所有接到數據包的節點每次都計算自己的深度信息，同樣耗能。

2 引入局部更新后的改進算法

在傳統的DBR協議傳感器網絡中，滿足深度小于當前節點條件的鄰居節點都會參與到數據包的轉發工作中，這不可避免地造成多個節點同時轉發相同數據包，造成數據冗余和能耗。本文針對DBR協議提出一種局部更新策略來減少DBR的能量消耗。

2.1 網絡體系結構

基于局部更新策略的DBR改進機制采用多Sink節點體系結構，如圖1所示。水面上的為Sink節點，水下的為一般的傳感器節點，以三維立體結構部署在需要監測的區域內。Sink節點彼此之間采用RF調制解調器通信，包括將數據傳到基站；同時，應用水聲調制解調器將接收到的水下節點的信息傳送至基站。每個水下節點都配備深度傳感器，可以隨時確定自己的深度信息。水下節點主要負責數據的采集，同時通過多次轉發最終將數據傳送至海面上任意一個Sink節點即可。通過RF調制解調器，Sink節點可以高速、準確地將數據包傳送給靠近基站的Sink節點，最終成功將數據傳至基站。本文中設定將數據傳至任意一個Sink節點即認為數據成功到達目的節點。

圖1 水下傳感器網絡數據轉發示意圖

2.2 改進算法工作機制

在網絡部署初期，初始節點轉發數據時，通過簡單的洪泛廣播來轉發，所有節點深度比它小的節點可以進行轉發，并且通知前一節點自己進行了轉發；上一級節點將返回的信息存儲在一個消息隊列中，每隔一段時間t處理一次，具體為隨機選取隊列中的部分節點并發送關閉消息來使其關閉休眠，其余節點繼續參與整個網絡的轉發工作。這樣，在經過幾輪的轉發過程之后，網絡中會有相當一部分節點處在睡眠狀態，整個網絡的能量消耗減少。當網絡中的某一節點能量快要耗盡時，它將發送警告信息通知它的上一跳節點，上一跳節點將會洪泛一個消息喚醒它睡眠的鄰居節點再次參與到網絡數據傳送工作中來。節點處理數據具體流程如圖2所示。

對于水下網絡中的節點而言，可以大致分為3類，如圖3所示。圖中實線表示傳送數據包轉發路徑，虛線為返回上級信息包路徑。源節點向外洪泛數據包后，只有深度比該節點小的鄰居節點會將數據轉發出去并向上級發送確認信息；而源節點處理消息隊列后隨機產生的睡眠節點將不再參與此次數據包的轉發工作。

由于水下無線傳感器網絡處在水聲環境中，因此每個節點的位置不是固定不變的。因為本文的算法會關閉部分節點來達到節能的目的，所以不可避免地會遇到路由空洞的問題。在此提出一個解決方法：由于存在多個節點轉發數據，當某一節點數據無法再轉發出去時不能說明整個網絡環境一定存在路由空洞。解決思路為：將數據包回退至第一個轉發超過2個節點的節點，并保留一段時間t，如在時間t內沒有接收到另外幾路分支的回退數據，則說明其中有一條分支是可以走通，將空洞分支中的所有節點關閉并將回退數據舍棄；如果同樣收到其余分支的回退數據，說明此節點不通，將所有下游節點全部關閉并將數據回退到上一節點再繼續檢測，依次往復。如果數據回退到最下層節點，則說明整個水下傳感器網絡存在路由空洞，這時可以簡單地洪泛一條消息來將所有節點喚醒，并開始重新生成優化網絡。

圖2 節點處理數據流程示意圖

圖3 節點傳輸圖

3 仿真結果

本文采用MATLAB來仿真分析傳統DBR路由協議和基于局部更新的改進后協議的性能，通過在相同環境下比較二者性能來驗證改進算法的有效性，重點觀察整個網絡在正常工作一段時間后，整個網絡中的傳感器的平均剩余能量。

節點隨機部署在500 m×500 m×500 m的三維區域中，水面Sink節點數量為5，假設節點在所有場景中都是靜止的，MAC層采用802.11算法，信道帶寬設為1 Mb/s，數據分組的大小為4 KB，節點的初始能量為 1 000 J，傳送和接收數據分組消耗1 J。

能耗比較示意圖如圖4所示。可以看出，隨著節點數目的增多，由于采用了局部更新算法，非必要傳輸節點會關閉節點以減小能耗，改進DBR算法平均耗能明顯小于傳統DBR。

傳輸率比較示意圖如圖5所示。隨著網絡中節點數量的增加，出現路由空洞機率減小，改進前DBR與改進后協議的傳輸正確率均有提高；而在相同情況下，改進后協議比傳統DBR有明顯優勢。

圖4 能耗示意圖

圖5 傳輸率比較圖

本文研究了一個基于深度信息的路由協議DBR，在此基礎上提出了一個新的局部更新策略，并將兩者結合運用于水聲傳感器網絡。實驗表明，改進后的算法大大降低了整個網絡的能量消耗，并且提高了傳輸率，達到了比較良好的性能。

[1]金軍，縱芳，梁妙元，等.水下傳感器網絡路由協議研究[J].電信科學，2012(2)：123-127.

[2]孫亭，楊永田，李立宏.無線傳感器網絡技術發展現狀[J].電子技術應用，2006，32(6)：1-5，11.

[3]梁玉芬，高德云，牛延超，等.無線傳感器網絡應用系統綜述[J].電子技術應用，2007，33(9)：3-5，9.

[4]竇麗娜.水聲傳感器網絡研究[D].哈爾濱：哈爾濱工程大學，2008.

[5]AKYILDIZ I F，POMPILI D，MELODIA T.State of the art in protocol research for underwater acoustic sensor networks[C].Proceedings of the First Workshop on Under Water Network，2006.

[6]Yan Hai，Shi Zhijie，Cui Junhong.DBR：depth-based routing for underwater sensor networks[C].Network 2008，7th International IFIP-7C6，2008：16-1221.

[7]SEAGH W K G，TAN H X.Multipath virtual sink architecture for underwater sensor networks[C].Proceedings of Oceans 2006-Asia Pacific，IEEE Press，2006：1-6.

[8]黃芬，陳名松.水下無線傳感器網絡DBR路由協議研究[J].電視技術，2012，36(13)：74-77.