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

石亞男，劉廣鐘

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

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

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

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

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

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

1 DBR簡介

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

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

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

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

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

2.1 網(wǎng)絡體系結構

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

圖1 水下傳感器網(wǎng)絡數(shù)據(jù)轉發(fā)示意圖

2.2 改進算法工作機制

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

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

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

圖2 節(jié)點處理數(shù)據(jù)流程示意圖

圖3 節(jié)點傳輸圖

3 仿真結果

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

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

能耗比較示意圖如圖4所示?？梢钥闯觯S著節(jié)點數(shù)目的增多，由于采用了局部更新算法，非必要傳輸節(jié)點會關閉節(jié)點以減小能耗，改進DBR算法平均耗能明顯小于傳統(tǒng)DBR。

傳輸率比較示意圖如圖5所示。隨著網(wǎng)絡中節(jié)點數(shù)量的增加，出現(xiàn)路由空洞機率減小，改進前DBR與改進后協(xié)議的傳輸正確率均有提高；而在相同情況下，改進后協(xié)議比傳統(tǒng)DBR有明顯優(yōu)勢。

圖4 能耗示意圖

圖5 傳輸率比較圖

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

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

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

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

[4]竇麗娜.水聲傳感器網(wǎng)絡研究[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]黃芬，陳名松.水下無線傳感器網(wǎng)絡DBR路由協(xié)議研究[J].電視技術，2012，36(13)：74-77.