洪昌建吳偉杰 唐平鵬

(武漢第二船舶設(shè)計研究所 武漢 430064)

動態(tài)分層的水下傳感器網(wǎng)絡(luò)分簇路由算法

洪昌建*吳偉杰 唐平鵬

(武漢第二船舶設(shè)計研究所 武漢 430064)

針對平面路由難以適應(yīng)較大規(guī)模水下傳感器網(wǎng)絡(luò)的局限，該文提出一種能更好地適用于較大規(guī)模網(wǎng)絡(luò)的分簇路由算法DLCR(Dynamic Layered Clustering Routing)。該算法將網(wǎng)絡(luò)自上向下劃分為多層，并選擇層內(nèi)與sink節(jié)點距離較近、剩余能量較高的節(jié)點作為簇頭節(jié)點，從而降低簇頭節(jié)點的通信能耗。為了避免同一節(jié)點連續(xù)被選舉為簇頭節(jié)點，提出一種動態(tài)分層機制，每一輪數(shù)據(jù)采集周期都將網(wǎng)絡(luò)重新劃分為多層。實驗證明DLCR不僅具有良好的穩(wěn)定性，還降低了網(wǎng)絡(luò)的能耗，延長了網(wǎng)絡(luò)的壽命。

水下傳感器網(wǎng)絡(luò)；動態(tài)分層機制；分簇路由

1 引言

隨著世界各國對海洋權(quán)益的日益重視、發(fā)展海洋經(jīng)濟熱潮的興起和陸地?zé)o線傳感器網(wǎng)絡(luò)研究的迅速發(fā)展，水下傳感器網(wǎng)絡(luò)(Underwater Sensor Networks, USN)已經(jīng)成為新的研究熱點[1,2]。水下傳感器網(wǎng)絡(luò)將采集到的水下環(huán)境數(shù)據(jù)發(fā)送給用戶來輔助決策，在環(huán)境監(jiān)測、資源勘探、災(zāi)難預(yù)警和潛艇探測等民用和軍用領(lǐng)域均具有廣闊的應(yīng)用前景[3,4]。

在實際應(yīng)用中，由于水下傳感器網(wǎng)絡(luò)的特殊網(wǎng)絡(luò)環(huán)境，無線電波在水中衰減迅速，不適合作長距離的數(shù)據(jù)傳輸，因而通常采用水聲通信；由于GPS在水中無法使用，節(jié)點的位置信息未知；同時節(jié)點受水流的影響在一定范圍內(nèi)移動，造成了網(wǎng)絡(luò)的間歇連通性。以上均為水下傳感器網(wǎng)絡(luò)的路由帶來了極大的挑戰(zhàn)。

關(guān)于水下傳感器網(wǎng)絡(luò)的路由策略已有大量研究。以DBR[5]算法為代表的平面路由算法為水下傳感器網(wǎng)絡(luò)的組網(wǎng)提供了良好的解決方案。然而平面路由算法常用于較小規(guī)模的網(wǎng)絡(luò)，如果網(wǎng)絡(luò)規(guī)模較大，靠近sink的節(jié)點會承擔(dān)過多的數(shù)據(jù)轉(zhuǎn)發(fā)而消耗大量的能量，導(dǎo)致這一部分節(jié)點提前死亡而形成能量空洞，這些節(jié)點死亡后又會加劇其周圍節(jié)點的死亡，故延緩能量空洞的出現(xiàn)有助于延長網(wǎng)絡(luò)的壽命。相對于平面路由算法，分簇路由能夠使網(wǎng)絡(luò)的能量負(fù)載更加均衡，因此為了適應(yīng)大規(guī)模的網(wǎng)絡(luò)環(huán)境，采用分簇路由算法則能夠在一定程度上延緩能量空洞的出現(xiàn)，有效地延長網(wǎng)絡(luò)的壽命。

目前，研究者對于分簇路由算法的研究主要集中在傳統(tǒng)地面無線傳感器網(wǎng)絡(luò)上，其網(wǎng)絡(luò)形態(tài)為2維平面網(wǎng)絡(luò)，此類算法不能直接應(yīng)用于3維水下傳感器網(wǎng)絡(luò)環(huán)境中。關(guān)于3維水下傳感器網(wǎng)絡(luò)分簇路由算法，國內(nèi)外研究者也做了相應(yīng)的理論研究，但大多數(shù)算法都建立在2維地面?zhèn)鞲衅骶W(wǎng)絡(luò)分簇路由算法的基礎(chǔ)上，將2維地面?zhèn)鞲衅骶W(wǎng)絡(luò)的分簇路由算法移植到3維水下傳感器網(wǎng)絡(luò)環(huán)境中，沒有考慮水下傳感器網(wǎng)絡(luò)節(jié)點的移動性、位置信息未知等特點，并不能真正地解決水下傳感器網(wǎng)絡(luò)的分簇路由問題。主要存在以下幾點不足：(1)基于地理位置信息的分簇算法，如LCAD[6], MCCP[7]等。此類算法的簇頭選舉代價函數(shù)通常涉及到節(jié)點間距、位置等信息，采用水聲通信的水下傳感器網(wǎng)絡(luò)無法利用GPS來定位。采用無線測距的方式則存在較大的誤差，而且水下測距和節(jié)點定位已成為另一個研究的熱點問題；(2)未充分考慮節(jié)點移動性給網(wǎng)絡(luò)帶來的影響，此類算法如UDA[8], E-PULRP[9]等多采用靜態(tài)3維網(wǎng)絡(luò)模型，忽略了節(jié)點移動給網(wǎng)絡(luò)拓?fù)鋷淼挠绊懀?3)引入其他移動數(shù)據(jù)采集裝置或者引入特殊節(jié)點解決水下傳感器網(wǎng)絡(luò)特殊性帶來的問題，此類算法如TCBR[10], UW-HSNs[11]等雖然能被很好應(yīng)用，但額外的設(shè)備也增加了網(wǎng)絡(luò)的成本；(4)其他分簇算法如DUCS[12], DEAR[13]等雖然為水下傳感器網(wǎng)絡(luò)分簇路由提供了解決方案并能夠較好適應(yīng)水下環(huán)境，但隨著網(wǎng)絡(luò)的運行，該算法最終會退化為隨機成簇算法，因而其網(wǎng)絡(luò)能量的利用率仍有較大的提升空間。在不依賴節(jié)點位置信息和考慮節(jié)點移動性的基礎(chǔ)上，本文網(wǎng)絡(luò)節(jié)點通信半徑可以在數(shù)據(jù)采集周期的不同階段進行自調(diào)整，從而保證網(wǎng)絡(luò)的可靠性；并對網(wǎng)絡(luò)進行初始分層，使簇頭盡可能地位于層內(nèi)偏上方，即與sink節(jié)點的距離較近，從而減少簇頭節(jié)點的能耗。并且，每次數(shù)據(jù)采集周期開始前都要動態(tài)地調(diào)整網(wǎng)絡(luò)分層，使簇頭節(jié)點始終盡可能存在層內(nèi)的偏上方，同時可以降低同一節(jié)點連續(xù)被選為簇頭節(jié)點的概率。分層的引入不僅簡化了網(wǎng)絡(luò)模型，還能夠使簇頭分布得更加均勻，有助于均衡網(wǎng)絡(luò)的負(fù)載。

2 相關(guān)模型和假定

2.1 網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>

本文的研究對象為3維水下傳感器網(wǎng)絡(luò)，該網(wǎng)絡(luò)是由固定在水底的靜態(tài)節(jié)點、懸浮在水中的動態(tài)節(jié)點、和浮在水面的sink節(jié)點構(gòu)成。

如圖1所示，在網(wǎng)絡(luò)的初始階段，若干個水下傳感器節(jié)點隨機地部署在一個長方體監(jiān)控區(qū)域內(nèi)，若干個sink節(jié)點隨機地分布在監(jiān)控領(lǐng)域的水面上方。本文對水下傳感器網(wǎng)絡(luò)做了如下的假設(shè)：

(1)假定sink節(jié)點的數(shù)量足夠多使sink節(jié)點的間距始終小于一個固定值ds；

圖1 水下傳感器網(wǎng)絡(luò)模型

(2)所有節(jié)點均具有唯一的標(biāo)志，節(jié)點采用水聲通信的方式進行消息傳遞，消息被發(fā)送到任意的sink節(jié)點均表示被成功地接收；

(3)所有非sink節(jié)點具有可調(diào)的處理/通信能力，但無法通過水聲信號來感知節(jié)點間距離；

(4)節(jié)點受水流的影響在一定范圍內(nèi)移動，假定具有最大的偏移距離r；

(5)節(jié)點周期性地進行數(shù)據(jù)采集，且始終有數(shù)據(jù)傳送至sink；

(6)分別采用第1個節(jié)點死亡和10%節(jié)點死亡的時間[14]作為網(wǎng)絡(luò)壽命的衡量參數(shù)。

2.2 水聲通信能耗模型

本文算法采用與文獻(xiàn)[15]相同的水聲通信能耗模型。對于水下傳感器節(jié)點，消息發(fā)送產(chǎn)生的能耗大約為消息接收和空閑偵聽所消耗能量的幾十倍，因而消息發(fā)送產(chǎn)生的能耗占據(jù)了網(wǎng)絡(luò)總能耗的極大比例，降低消息發(fā)送產(chǎn)生的能耗就意味著降低了整個網(wǎng)絡(luò)的總能耗[16]。本文算法將消息發(fā)送產(chǎn)生的能耗作為衡量整個網(wǎng)絡(luò)總能耗的主要參數(shù)，即不考慮消息接收產(chǎn)生的能耗。

假定Po為節(jié)點能夠正常接收消息所需的最低功率，若功率對傳播距離x的衰減函數(shù)為A(x)，那么節(jié)點的發(fā)送功率至少應(yīng)達(dá)到PoA(x)才能保證節(jié)點能接收到該消息。設(shè)節(jié)點發(fā)送l bit數(shù)據(jù)的發(fā)送時延為TP，則發(fā)送l bit數(shù)據(jù)消耗的能量Etr(l,x)為

其中A(x)是與水聲傳播模型和發(fā)送頻率有關(guān)的函數(shù)變量，可表示為

其中k為水聲傳播模型的相關(guān)參數(shù)，k取1時為柱形傳播模型，k取2時為球形傳播模型，通常k取1.5代表實際水聲傳播模型。a與頻率f有關(guān)，可由能量吸收系數(shù)?(f)獲得其中能量吸收系數(shù)為

2.3 節(jié)點運動模型

為了能夠較為準(zhǔn)確地模擬水中節(jié)點的運動狀態(tài)，建立節(jié)點運動模型時需要考慮如下情況：首先由于節(jié)點被拋錨固定在水底，節(jié)點的深度可以通過調(diào)整錨鏈的長度來改變。這種狀態(tài)下的節(jié)點受到水流的影響和錨鏈的牽引力作用，會在一定的范圍內(nèi)做受限的運動[17]。圖2給出了水下環(huán)境中的節(jié)點受力圖。

圖2 節(jié)點受力圖

如圖2所示，對節(jié)點受力分析，節(jié)點受到水流的橫向沖擊力F、浮力f及錨鏈對節(jié)點的拉力T (忽略節(jié)點的自身重力)，這3種力構(gòu)成了一組平衡力，并設(shè)錨鏈和垂直方向的最大夾角為β，其中tanβ =F/f 。本文不做流體力學(xué)相關(guān)研究，在實驗仿真中做了定量處理，僅給出節(jié)點移動的最大偏移距離，在該偏移距離內(nèi)節(jié)點做Random Waypoint運動[18]。

3 動態(tài)分層的分簇路由算法

3.1 問題描述

在網(wǎng)絡(luò)分簇階段，節(jié)點受水流的影響在一定范圍內(nèi)運動，節(jié)點與簇頭的間距在不斷地變化，且節(jié)點無法感知與簇頭的間距。為了保證網(wǎng)絡(luò)的可靠性，本文節(jié)點通信半徑初始化為固定值。這樣，在簇內(nèi)成員節(jié)點通信半徑都相同的情況下，不同簇形態(tài)具有相同的能耗nEtr, n為簇內(nèi)成員節(jié)點的總數(shù)，Etr為成員節(jié)點與簇頭節(jié)點通信的能耗，在不能改變成員節(jié)點能耗的情況下，如果能減少簇頭節(jié)點的能耗，則減少網(wǎng)絡(luò)的總能耗。然而如果始終選擇距離sink節(jié)點較近的節(jié)點成為簇頭，會導(dǎo)致這類節(jié)點能量消耗過大而提前死亡，形成能量空洞。本文引入了動態(tài)分層機制，每一輪數(shù)據(jù)采集周期網(wǎng)絡(luò)分層都自動向下調(diào)整，動態(tài)分層避免了同一節(jié)點連續(xù)被選舉為簇頭節(jié)點，起到了平衡網(wǎng)絡(luò)能耗的作用。圖3和圖4分別給出了網(wǎng)絡(luò)簇頭選取方法和動態(tài)分層機制的示意圖。

3.2 節(jié)點通信半徑

對式(2)求導(dǎo)處理后，當(dāng)在最小接收功率為3 mW、消息發(fā)送頻率為10 kHz的條件下，節(jié)點的通信距離小于540 m時，節(jié)點傳輸功耗增長率小于1，表明在540 m范圍內(nèi)，隨著通信距離的增加，節(jié)點發(fā)送消息產(chǎn)生的能量增加得較緩慢。相反，當(dāng)節(jié)點的通信距離大于540 m時，隨著通信距離的增加，節(jié)點發(fā)送消息產(chǎn)生的能量增加得較快。因而，DLCR算法要求節(jié)點的通信半徑不能超過540 m過多。

為了適應(yīng)節(jié)點的移動性，保證網(wǎng)絡(luò)的可靠性，本文算法要求節(jié)點的通信功率可調(diào)。在簇頭選舉階段，被選為簇頭的節(jié)點以通信半徑R廣播自己成為簇頭的消息，成員節(jié)點選擇加入最佳的簇。數(shù)據(jù)采集階段，成員節(jié)點以通信半徑R+2r就能保證消息能夠發(fā)送給簇頭節(jié)點，r為節(jié)點受水流影響的最大偏移距離。最后簇頭節(jié)點采用多跳的方式將消息發(fā)送給sink節(jié)點。

3.3 動態(tài)分層機制

圖3 簇頭選取方法

圖4 動態(tài)分層圖

網(wǎng)絡(luò)分層的目的是為了簡化網(wǎng)絡(luò)模型，分層又能夠保證簇頭節(jié)點更加均勻地分布在整個傳感器網(wǎng)絡(luò)中，有助于均衡網(wǎng)絡(luò)的能耗。分層后的網(wǎng)絡(luò)只有同一層內(nèi)的節(jié)點進行成簇。DLCR算法的核心思想是為了讓簇頭節(jié)點更靠近網(wǎng)絡(luò)的上方，即與sink節(jié)點的距離較近。因而為了保證分層邊界上的節(jié)點能與正上方最遠(yuǎn)的簇頭節(jié)點通信，要求簇頭選舉階段節(jié)點的通信半徑R不小于層間距Δd。DLCR算法取分層間距等于通信半徑R。

DLCR算法要求在每一輪數(shù)據(jù)采集周期內(nèi)，簇頭節(jié)點位于網(wǎng)絡(luò)層內(nèi)的偏上方，每一輪數(shù)據(jù)采集周期結(jié)束后，相較于普通節(jié)點，簇頭節(jié)點消耗較大的能耗。為了避免同一節(jié)點多次被選為簇頭節(jié)點，又能保證所有的簇頭都在層內(nèi)的偏上方，因而要引入動態(tài)的網(wǎng)絡(luò)分層。動態(tài)網(wǎng)絡(luò)分層的核心思想為：每一輪數(shù)據(jù)采集結(jié)束之后，各網(wǎng)絡(luò)分層都向下移動一個固定距離值d，這樣經(jīng)過R/d 輪后，網(wǎng)絡(luò)又重新恢復(fù)到最初的分層狀態(tài)。

假設(shè)網(wǎng)絡(luò)被均勻的劃分為多層，節(jié)點x的當(dāng)前深度信息為hx,D為網(wǎng)絡(luò)的最大深度。網(wǎng)絡(luò)在初始階段被劃分為D/R層，之后由于動態(tài)分層機制，網(wǎng)絡(luò)將被劃分為D/R+1層，經(jīng)過R/d輪后，網(wǎng)絡(luò)又重新恢復(fù)到初始的分層網(wǎng)絡(luò)。設(shè)網(wǎng)絡(luò)分層編號從0開始采用自上而下遞增的方式進行編號，網(wǎng)絡(luò)初始階段第0層是不存在的，網(wǎng)絡(luò)編號從1開始。之后網(wǎng)絡(luò)的第0層距離sink節(jié)點在通信范圍內(nèi)，所以要求第0層節(jié)點不成簇，直接將數(shù)據(jù)發(fā)送給sink節(jié)點。節(jié)點第1輪所在初始層次為L1x：

由于每一輪簇頭都盡可能地位于層內(nèi)偏上方，為了平衡網(wǎng)絡(luò)的能耗，每一輪分簇結(jié)束之后，在上一輪分層的基礎(chǔ)之上，各網(wǎng)絡(luò)分層都向下調(diào)整距離d，節(jié)點x第n輪的所在網(wǎng)絡(luò)層次為Lnx：

式(6)給出動態(tài)分層的計算方式，只要每一輪數(shù)據(jù)采集周期結(jié)束之后，節(jié)點都要重新計算自己所在的網(wǎng)絡(luò)層次。這樣，在動態(tài)分層機制的基礎(chǔ)上，只要能給出合適的簇頭選舉機制，始終選擇距離sink節(jié)點較近的節(jié)點作為簇頭節(jié)點，就能夠保證網(wǎng)絡(luò)的能量均衡，延緩網(wǎng)絡(luò)能量空洞的出現(xiàn)，有效地延長網(wǎng)絡(luò)的壽命。

3.4 簇頭的選舉和路由

簇頭選舉的核心思想是建立在動態(tài)分層的基礎(chǔ)之上，其中第0層距離sink節(jié)點較近，節(jié)點直接將消息發(fā)送給sink，而其他層內(nèi)的簇頭節(jié)點盡可能位于層內(nèi)的偏上方。針對在同一深度的節(jié)點，簇頭的選取還需要綜合節(jié)點能耗因數(shù)，始終考慮能量較大的節(jié)點擔(dān)任簇頭節(jié)點。本算法要求簇頭選舉的代價函數(shù)依賴于深度因子和能量因子兩個參數(shù)。由于簇頭的選舉在同一層內(nèi)進行，深度因子H(x)的計算方式為當(dāng)前節(jié)點位于層內(nèi)的相對高度與層間距的比值，式(7)給出了深度因子的求解：

由于每一輪數(shù)據(jù)采集周期內(nèi)，普通節(jié)點都要以通信半徑R+2r將數(shù)據(jù)發(fā)送給簇頭節(jié)點，因而節(jié)點每一輪都將至少消耗Etr(l,R+2r)的能量(若為擔(dān)任簇頭節(jié)點，則能耗較高)。第n輪時，節(jié)點最大剩余能量約為Eo?(n?1)×Etr(l,R+2r )，能量因子E(x)的計算方式為節(jié)點剩余能量與節(jié)點的最大剩余能量的比值，式(8)給出了能量因子的求解：

其中Eo為節(jié)點初始能量，Ex為節(jié)點剩余能量，n表示輪數(shù)，r為節(jié)點最大偏移距離。

在簇頭選舉過程中，簇頭首先要計算深度因子H(x)，能量因子E(x)和簇頭代價值T(x)；首先需要給出一個深度閾值Ho，只有深度因子H(x)大于深度閾值Ho的節(jié)點被選為候選簇頭。要找出深度閾值Ho就得找出哪些節(jié)點被選為候選簇頭。

根據(jù)動態(tài)分層機制，在新一輪簇頭選舉時，網(wǎng)絡(luò)分層進行相應(yīng)的調(diào)整，各層向下調(diào)整的距離為d 。其理論為：位于層內(nèi)偏上方深度區(qū)間d內(nèi)的那段區(qū)域的節(jié)點被當(dāng)選為候選簇頭。式(10)給出閾值Ho的計算方式：

簇頭選舉的代價函數(shù)T(x)可由深度因子與能量因子之積求得，式(9)給出了簇頭選舉的代價函數(shù)的求解：

簇頭選舉和路由的過程如下：

第1步 候選簇頭選舉階段，每個節(jié)點計算自身的深度因子H(x)和成為簇頭的權(quán)值T(x), H(x)若大于閾值Ho，則該節(jié)點成為候選簇頭。

第2步 簇頭選舉階段，每個候選簇頭進行消息廣播。候選簇頭i收到來自其他候選簇頭節(jié)點的廣播消息后，將其他的簇頭節(jié)點加入自己的競選隊列Qi。

第3步 如果競選隊列Qi內(nèi)所有來自其他節(jié)點的簇頭權(quán)值T(x)均小于自身權(quán)值，則宣布自己成為簇頭，并廣播自己成為簇頭的消息。其他候選簇頭節(jié)點收到該消息后就加入該簇，并廣播退選消息，其他節(jié)點收到退選消息后，將該節(jié)點從自己的競選隊列里去除。然后重復(fù)第3步過程，經(jīng)過多次迭代，直到所有簇頭均被選舉出來。

第4步 分簇階段中，非簇頭節(jié)點存在以下3種情況：

(1)第1類節(jié)點收到多個本層簇頭節(jié)點的廣播消息或同時收到若干來自下層簇頭的廣播消息，選擇本層簇頭節(jié)點中權(quán)值T(x)較大的加入；

(2)第2類節(jié)點只收到來自下層簇頭節(jié)點的廣播消息，隨機選擇簇頭權(quán)值T(x)最大的簇頭加入；

(3)第3類節(jié)點未收到任何簇頭廣播信息，自己成為一個簇頭，并廣播簇頭消息，其他類似節(jié)點通過這種方式自主選擇分簇。

第5步 數(shù)據(jù)收集階段：簇頭將成員節(jié)點的消息融合成一條消息后，通過多跳的方式發(fā)送給sink節(jié)點。

(1)每個簇頭以半徑R廣播一個路由發(fā)現(xiàn)消息，選擇來自上層的T(x)閾值最大的簇頭節(jié)點作為下一跳節(jié)點；

(2)若通信范圍內(nèi)沒找到簇頭節(jié)點，則在通信半徑增大R后，再廣播路由發(fā)現(xiàn)消息，直到發(fā)現(xiàn)下一跳簇頭節(jié)點。重復(fù)次，直到確定下一跳節(jié)點。否則直接將消息發(fā)送給sink節(jié)點。

4 實驗與仿真

在matlab平臺下，本文與采用相同網(wǎng)絡(luò)模型的DUCS, DEAR算法以及LEACH經(jīng)典成簇算法進行了對比實驗。實驗結(jié)果證明，DLCR算法的穩(wěn)定性以及在控制網(wǎng)絡(luò)負(fù)載均衡、延長網(wǎng)絡(luò)壽命等方面都要優(yōu)于DUCS, DEAR, LEACH等算法。表1給出了默認(rèn)的仿真參數(shù)。

4.1 動態(tài)網(wǎng)絡(luò)分層對網(wǎng)絡(luò)壽命的影響

在500×500×600網(wǎng)絡(luò)環(huán)境下部署1000個節(jié)點，節(jié)點初始能量為0.5 J，通信半徑R為200 m，動態(tài)分層調(diào)整間距d分別取R, R/2, R/3, R/4, R/5；從圖5可以看出在不同動態(tài)分層機制下，當(dāng)調(diào)整值d為R時，即沒有引入網(wǎng)絡(luò)動態(tài)分層機制時，網(wǎng)絡(luò)第1個節(jié)點的死亡時間最早，而且隨著網(wǎng)絡(luò)的運行，節(jié)點的死亡速率最高；當(dāng)引入分層機制后，節(jié)點的死亡時間得到延遲，并且當(dāng)調(diào)整間距為R/2時，網(wǎng)絡(luò)最晚出現(xiàn)死亡節(jié)點。從圖6可以看出，當(dāng)調(diào)整值d取R值時，即在沒有引入網(wǎng)絡(luò)動態(tài)分層機制的情況下，網(wǎng)絡(luò)的總能耗要高于引入動態(tài)分層機制后的網(wǎng)絡(luò)。而引入動態(tài)分層機制后，網(wǎng)絡(luò)總能耗均得到良好的控制，表明動態(tài)分層有助于提高網(wǎng)絡(luò)能量的利用率。由于第1個節(jié)點死亡時，網(wǎng)絡(luò)將開始變得不穩(wěn)定，因而結(jié)合圖5和圖6的實驗結(jié)果，當(dāng)分層調(diào)整值d取R/2時，網(wǎng)絡(luò)的性能較優(yōu)。

表1 仿真參數(shù)

在保持網(wǎng)絡(luò)節(jié)點密度、通信半徑不變的情況下，通過改變網(wǎng)絡(luò)的規(guī)模，進行多次實驗后從圖7可以看出最優(yōu)網(wǎng)絡(luò)壽命下的分層調(diào)整值d并沒有隨著網(wǎng)絡(luò)的規(guī)模而改變。保持網(wǎng)絡(luò)規(guī)模不變的情況下，通過改變節(jié)點的數(shù)量，進行多次實驗后從圖8可以看出當(dāng)網(wǎng)絡(luò)部署節(jié)點的增加嚴(yán)重影響了網(wǎng)絡(luò)節(jié)點密度時，節(jié)點重復(fù)覆蓋面積增大，此時分層調(diào)整間距減小更有利于均衡網(wǎng)絡(luò)的能耗。

4.2 網(wǎng)絡(luò)簇頭的分布

在500×500×600網(wǎng)絡(luò)環(huán)境下部署1000個節(jié)點，節(jié)點初始能量為1 J，通信半徑為200 m。從圖9可以看出相較于其他算法，DLCR簇頭分布更接近正態(tài)分布，說明該算法下的簇頭分布相對集中，算法的穩(wěn)定性和穩(wěn)健性較好。

4.3 不同算法的網(wǎng)絡(luò)性能對比

在500×500×600的網(wǎng)絡(luò)環(huán)境下，隨機部署1000個節(jié)點，節(jié)點初始能量為1 J，通信半徑為200 m。從圖10可以看出，采用隨機分簇且沒有合理簇間路由的LEACH算法其簇頭節(jié)點能耗較大，最早出現(xiàn)死亡節(jié)點；DUCS算法根據(jù)節(jié)點剩余能量選舉簇頭，而DEAR算法考慮了簇內(nèi)節(jié)點的平均能量，但當(dāng)節(jié)點能量較低時，DUCS和DEAR算法都會退化成隨機成簇算法；本文DLCR算法考慮節(jié)點的相對剩余能量和相對深度，是更優(yōu)的分簇算法，同時動態(tài)分層均衡了網(wǎng)絡(luò)能耗，進一步延長了網(wǎng)絡(luò)壽命。對比圖11可以看出采用了動態(tài)分層的DLCR算法，由于網(wǎng)絡(luò)簇頭更加均勻，且距離sink較近，因而其網(wǎng)絡(luò)能量的衰減最為緩慢。

5 結(jié)論

圖5 動態(tài)網(wǎng)絡(luò)分層對節(jié)點存亡的影響

圖6 動態(tài)網(wǎng)絡(luò)分層對網(wǎng)絡(luò)能量的影響

圖7 最優(yōu)網(wǎng)絡(luò)壽命下網(wǎng)絡(luò)規(guī)模對應(yīng)的調(diào)整值

圖8 最優(yōu)網(wǎng)絡(luò)壽命下網(wǎng)絡(luò)密度對應(yīng)的調(diào)整值

圖9 簇頭分布

圖10 節(jié)點死亡時間對比

圖11 網(wǎng)絡(luò)剩余能量

本文提出了一種動態(tài)分層的水下傳感器網(wǎng)絡(luò)分簇路由算法，該算法通過減少簇頭節(jié)點與sink節(jié)點的距離來減少簇頭的通信能耗，并通過建立動態(tài)的分層機制來平衡網(wǎng)絡(luò)的能耗，實驗證明該算法具有較好的穩(wěn)定性，能夠有效地均衡網(wǎng)絡(luò)能量、延長網(wǎng)絡(luò)壽命。

[1] 郭忠文, 羅漢江, 洪峰, 等. 水下傳感器網(wǎng)絡(luò)的研究進展[J].計算機研究與發(fā)展, 2010, 47(3): 377-389.

Guo Zhong-wen, Luo Han-jiang, Hong Feng, et al.. Current progress and research issues in underwater sensor networks[J]. Journal of Computer of Computer Research and Development, 2010, 47(3): 377-389.

[2] 洪峰, 張玉亮, 楊博真, 等. 水下傳感器網(wǎng)絡(luò)時間同步技術(shù)綜述[J]. 電子學(xué)報, 2013, 41(5): 960-965.

Hong Feng, Zhang Yu-liang, Yang Bo-zhen, et al.. Review on time synchronization techniques in underwater acoustic sensor networks[J]. Acta Electronica Sinica, 2013, 41(5): 960-965.

[3] 郭瑛, 張震. 大規(guī)模水下傳感器網(wǎng)絡(luò)時間同步研究[J]. 電子與信息學(xué)報, 2014, 36(6): 1498-1503.

Guo Ying and Zhang Zhen. Clock synchronization study for large scale underwater sensor networks[J]. Journal of Electronics & Information Technology, 2014, 36(6): 1498-1503.

[4] 金志剛, 蘇毅珊, 劉自鑫, 等. 基于運動預(yù)測的水下傳感器網(wǎng)絡(luò)MAC協(xié)議[J]. 電子與信息學(xué)報, 2013, 35(3): 728-734.

Jin Zhi-gang, Su Yi-shan, Liu Zi-xin, et al.. Prediction based MAC for underwater wireless sensor networks[J]. Journal of Electronics & Information Technology, 2013, 35(3): 728-734.

[5] Yan H and Cui J H. DBR: depth-based routing for underwater sensor networks[C]. Proceedings of the 7th International IFIP-TC6 Networking Conference, Singapore, 2008: 72-86.

[6] Anupama K R, Sasidharan A, and Vadlamani S. A location-based clustering algorithm for data gathering in 3D underwater wireless sensor networks[C]. Proceedings of the 2008 International Symposium on Telecommunications, Tehran, Iran, 2008: 343-348.

[7] Pu W, Cheng L, and Jun Z. Distributed minimum-cost clustering protocol for underwater sensor networks (UWSNs) [C]. Proceedings of the IEEE International Conference on Communications, Glasgow, UK, 2007: 3510-3515.

[8] Liu L F. A deployment algorithm for underwater sensor networks in ocean environment[J]. Journal of Circuits, Systems and Computers, 2011, 20(6): 1051-1066.

[9] Gopi S, Kannan G, Chander D, et al.. PULRP: path unawarelayer routing protocol for underwater sensor networks[C]. Proceedings of the IEEE International Conference on Communications, Beijing, China, 2008: 3141-3145.

[10] Ayaz M, Abdullah A, and Low Tang Jung. Temporary cluster based routing for underwater wireless sensor networks[C]. Proceedings of the International Symposium in Information Technology, Kuala Lumpur, Malaysia, 2010: 1009-1014.

[11] Ali K and Hassanein H. Underwater wireless hybrid sensor network[C]. Proceedings of the IEEE Symposium on Computers and Communications, Marrakech, Marocko, 2008: 1166-1171.

[12] Domingo M C and Prior R. A distributed clustering scheme for underwater wireless sensor networks in personal, indoor and mobile radio communications[C]. Proceedings of the IEEE 18th International Symposium on PIMRC, Athens, Greece, 2007: 1-5.

[13] Domingo M C. A distributed energy-aware routing protocol for underwater wireless sensor networks[J]. Wireless Personal Communications, 2011, 57(4): 607-627.

[14] 卿利, 朱清新, 王明文. 異構(gòu)傳感器網(wǎng)絡(luò)的分布式能量有效分簇算法[J]. 軟件學(xué)報, 2006, 17(3): 481-489.

Qing Li, Zhu Qing-xin, and Wang Ming-wen. A distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J]. Journal of Software, 2006, 17(3): 481-489.

[15] Sozer E M, Stojanovic M, and Proakis J G. Underwater acoustic networks[J]. IEEE Journal of Oceanic Engineering, 2000, 25(1): 72-83.

[16] 彭艦, 洪昌建, 劉唐, 等. 基于分層的水下傳感器網(wǎng)絡(luò)路由策略[J]. 通信學(xué)報, 2014, 35(6): 25-31.

Peng Jian, Hong Chang-jian, Liu Tang, et al.. Strategy of routing based on layered for underwater wireless sensor networks[J]. Journal on Communications, 2014, 35(6): 25-31.

[17] Guo Y and Liu Y T. Localization for anchor-free underwater sensor networks[J]. Computers and Electrical Engineering, 2013, 39(6): 1812-1821.

[18] 劉唐, 彭艦, 楊進. 異構(gòu)延遲容忍移動傳感器網(wǎng)絡(luò)中基于轉(zhuǎn)發(fā)概率的數(shù)據(jù)傳輸[J]. 軟件學(xué)報, 2013, 24(2): 215-229.

Liu Tang, Peng Jian, and Yang Jin. Data delivery for heterogeneous delay tolerant mobile sensor networks based on forwarding probability[J]. Journal of Software, 2013, 24(2): 215-229.

洪昌建： 男，1988年生，碩士，助理工程師，研究方向為無線傳感器網(wǎng)絡(luò).

吳偉杰： 男，1980年生，碩士，高級工程師，研究方向為計算機網(wǎng)絡(luò).

唐平鵬： 男，1985年生，博士，工程師，研究方向為計算機網(wǎng)絡(luò).

Dynamic Layered Clustering Routing Algorithm in Underwater Sensor Networks

Hong Chang-jian Wu Wei-jie Tang Ping-peng
(Wuhan Second Ship Design and Research Institute, Wuhan 430064, China)

To deal with the limitation that flat routing can hardly be accustomed to large scale Underwater Sensor Networks (USN), a new clustering routing algorithm Dynamic Layered Clustering Routing (DLCR) is proposed, which can be accustomed to larger scale networks. This algorithm divides the networks into several layers from top to bottom, and selects the nodes which have more remaining energy and shorter distance to sink as the cluster head nodes, thus, clusters' communication energy consumption are reduced. In order to avoid the same nodes being elected to be cluster head nodes continuously, a dynamic layered mechanism that the networks are divided into different layers in each circle of data gathering is proposed. The experiment shows that DLCR not only has a better stability, but also reduces the energy consumption and prolongs the lifetime of the whole networks.

Underwater Sensor Networks (USN); Dynamic layered mechanism; Clustering routing

TP393

： A

：1009-5896(2015)06-1291-07

10.11999/JEIT141182

2014-09-10 收到，2014-12-23改回

*通信作者：洪昌建 hongcj@yeah.net