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

洪昌建吳偉杰 唐平鵬

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

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

洪昌建*吳偉杰 唐平鵬

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

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

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

1 引言

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

在實(shí)際應(yīng)用中，由于水下傳感器網(wǎng)絡(luò)的特殊網(wǎng)絡(luò)環(huán)境，無線電波在水中衰減迅速，不適合作長距離的數(shù)據(jù)傳輸，因而通常采用水聲通信；由于GPS在水中無法使用，節(jié)點(diǎn)的位置信息未知；同時(shí)節(jié)點(diǎn)受水流的影響在一定范圍內(nèi)移動(dòng)，造成了網(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é)點(diǎn)會(huì)承擔(dān)過多的數(shù)據(jù)轉(zhuǎn)發(fā)而消耗大量的能量，導(dǎo)致這一部分節(jié)點(diǎn)提前死亡而形成能量空洞，這些節(jié)點(diǎn)死亡后又會(huì)加劇其周圍節(jié)點(diǎn)的死亡，故延緩能量空洞的出現(xiàn)有助于延長網(wǎng)絡(luò)的壽命。相對(duì)于平面路由算法，分簇路由能夠使網(wǎng)絡(luò)的能量負(fù)載更加均衡，因此為了適應(yīng)大規(guī)模的網(wǎng)絡(luò)環(huán)境，采用分簇路由算法則能夠在一定程度上延緩能量空洞的出現(xiàn)，有效地延長網(wǎng)絡(luò)的壽命。

目前，研究者對(duì)于分簇路由算法的研究主要集中在傳統(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é)點(diǎn)的移動(dòng)性、位置信息未知等特點(diǎn)，并不能真正地解決水下傳感器網(wǎng)絡(luò)的分簇路由問題。主要存在以下幾點(diǎn)不足：(1)基于地理位置信息的分簇算法，如LCAD[6], MCCP[7]等。此類算法的簇頭選舉代價(jià)函數(shù)通常涉及到節(jié)點(diǎn)間距、位置等信息，采用水聲通信的水下傳感器網(wǎng)絡(luò)無法利用GPS來定位。采用無線測(cè)距的方式則存在較大的誤差，而且水下測(cè)距和節(jié)點(diǎn)定位已成為另一個(gè)研究的熱點(diǎn)問題；(2)未充分考慮節(jié)點(diǎn)移動(dòng)性給網(wǎng)絡(luò)帶來的影響，此類算法如UDA[8], E-PULRP[9]等多采用靜態(tài)3維網(wǎng)絡(luò)模型，忽略了節(jié)點(diǎn)移動(dòng)給網(wǎng)絡(luò)拓?fù)鋷淼挠绊懀?3)引入其他移動(dòng)數(shù)據(jù)采集裝置或者引入特殊節(jié)點(diǎn)解決水下傳感器網(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ò)的運(yùn)行，該算法最終會(huì)退化為隨機(jī)成簇算法，因而其網(wǎng)絡(luò)能量的利用率仍有較大的提升空間。在不依賴節(jié)點(diǎn)位置信息和考慮節(jié)點(diǎn)移動(dòng)性的基礎(chǔ)上，本文網(wǎng)絡(luò)節(jié)點(diǎn)通信半徑可以在數(shù)據(jù)采集周期的不同階段進(jìn)行自調(diào)整，從而保證網(wǎng)絡(luò)的可靠性；并對(duì)網(wǎng)絡(luò)進(jìn)行初始分層，使簇頭盡可能地位于層內(nèi)偏上方，即與sink節(jié)點(diǎn)的距離較近，從而減少簇頭節(jié)點(diǎn)的能耗。并且，每次數(shù)據(jù)采集周期開始前都要?jiǎng)討B(tài)地調(diào)整網(wǎng)絡(luò)分層，使簇頭節(jié)點(diǎn)始終盡可能存在層內(nèi)的偏上方，同時(shí)可以降低同一節(jié)點(diǎn)連續(xù)被選為簇頭節(jié)點(diǎn)的概率。分層的引入不僅簡化了網(wǎng)絡(luò)模型，還能夠使簇頭分布得更加均勻，有助于均衡網(wǎng)絡(luò)的負(fù)載。

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

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

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

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

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

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

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

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

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

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

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

2.2 水聲通信能耗模型

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

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

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

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

2.3 節(jié)點(diǎn)運(yùn)動(dòng)模型

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

圖2 節(jié)點(diǎn)受力圖

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

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

3.1 問題描述

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

3.2 節(jié)點(diǎn)通信半徑

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

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

3.3 動(dòng)態(tài)分層機(jī)制

圖3 簇頭選取方法

圖4 動(dòng)態(tài)分層圖

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

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

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

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

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

3.4 簇頭的選舉和路由

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與仿真

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

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

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

表1 仿真參數(shù)

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

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

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

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

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

5 結(jié)論

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

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

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

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

圖9 簇頭分布

圖10 節(jié)點(diǎn)死亡時(shí)間對(duì)比

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

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

[1] 郭忠文, 羅漢江, 洪峰, 等. 水下傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計(jì)算機(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í)間同步技術(shù)綜述[J]. 電子學(xué)報(bào), 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ò)時(shí)間同步研究[J]. 電子與信息學(xué)報(bào), 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ùn)動(dòng)預(yù)測(cè)的水下傳感器網(wǎng)絡(luò)MAC協(xié)議[J]. 電子與信息學(xué)報(bào), 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é)報(bào), 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é)報(bào), 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] 劉唐, 彭艦, 楊進(jìn). 異構(gòu)延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)中基于轉(zhuǎn)發(fā)概率的數(shù)據(jù)傳輸[J]. 軟件學(xué)報(bào), 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年生，碩士，助理工程師，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò).

吳偉杰： 男，1980年生，碩士，高級(jí)工程師，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò).

唐平鵬： 男，1985年生，博士，工程師，研究方向?yàn)橛?jì)算機(jī)網(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