網(wǎng)絡(luò)分層的水下傳感器網(wǎng)絡(luò)覆蓋保持路由算法

蔣　鵬,王興民

(杭州電子科技大學(xué)自動(dòng)化學(xué)院,浙江杭州,310018)

?

網(wǎng)絡(luò)分層的水下傳感器網(wǎng)絡(luò)覆蓋保持路由算法

蔣鵬,王興民

(杭州電子科技大學(xué)自動(dòng)化學(xué)院,浙江杭州,310018)

在以監(jiān)測(cè)為目的的水下傳感器網(wǎng)絡(luò)中,較好的網(wǎng)絡(luò)覆蓋率和連通率是完成監(jiān)測(cè)任務(wù)的重要保證.以改善覆蓋效果為目標(biāo)的水下覆蓋保持路由算法NCPR算法相對(duì)比LEACH-Coverage-U算法有效的延長了網(wǎng)絡(luò)覆蓋時(shí)間,但是該算法連通性表現(xiàn)較差,同時(shí)存在靠近SINK節(jié)點(diǎn)的簇首由于需要轉(zhuǎn)發(fā)大量數(shù)據(jù)而過早死亡的問題.本文提出一種分布式的網(wǎng)絡(luò)不均勻分層的覆蓋保持路由(NetworkUnevenlyLayeredCoveragePreservingRouting,NULCPR)算法,由SINK節(jié)點(diǎn)開始逐層向下建立網(wǎng)絡(luò),同時(shí)每層網(wǎng)絡(luò)節(jié)點(diǎn)通信半徑也隨層號(hào)增加而逐漸增大.每層網(wǎng)絡(luò)獨(dú)立運(yùn)行NCPR算法以使該層節(jié)點(diǎn)成簇,并通過簇首向上建立連通鏈路以保證網(wǎng)絡(luò)連通.仿真結(jié)果表明,與NCPR算法相比,NULCPR算法提高了網(wǎng)絡(luò)連通率以及覆蓋率,并且降低了網(wǎng)絡(luò)能耗,證明了該算法的有效性.

水下傳感器網(wǎng)絡(luò);覆蓋保持路由;網(wǎng)絡(luò)分層

1　引言

水下傳感器網(wǎng)絡(luò)(UnderwaterSensorNetworks,UWSNs)是由具有聲學(xué)通信與計(jì)算能力的傳感器節(jié)點(diǎn)構(gòu)成的水下監(jiān)測(cè)網(wǎng)絡(luò)系統(tǒng),可應(yīng)用于水環(huán)境監(jiān)測(cè)、資源勘測(cè)、輔助導(dǎo)航和戰(zhàn)術(shù)監(jiān)視等領(lǐng)域[1，2],目前UWSNs已引起了各國政府和研究機(jī)構(gòu)的關(guān)注,成為當(dāng)前研究熱點(diǎn)之一.UWSNs的研究主要涉及水下通信技術(shù)、網(wǎng)絡(luò)協(xié)議、覆蓋控制、定位跟蹤、時(shí)間同步[3～5]等方面.其中,網(wǎng)絡(luò)覆蓋控制作為一項(xiàng)基礎(chǔ)性工作,直接影響到網(wǎng)絡(luò)對(duì)目標(biāo)的覆蓋效果,網(wǎng)絡(luò)生存時(shí)間以及傳感器管理等各種服務(wù)質(zhì)量.因此,如何設(shè)計(jì)覆蓋控制方法是一個(gè)關(guān)鍵問題.

根據(jù)關(guān)注階段的不同,可將現(xiàn)有水下傳感器網(wǎng)絡(luò)覆蓋控制方法分為如何部署傳感器節(jié)點(diǎn)和節(jié)點(diǎn)部署完成后如何設(shè)計(jì)相關(guān)協(xié)議以保持網(wǎng)絡(luò)覆蓋.其中,如何部署傳感節(jié)點(diǎn)是指通過人工或者節(jié)點(diǎn)自組織的方式移動(dòng)節(jié)點(diǎn)到某個(gè)具體位置,最終形成具有一定特性的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[6～9].針對(duì)網(wǎng)絡(luò)覆蓋保持,多是通過設(shè)計(jì)某種路由算法或者節(jié)點(diǎn)調(diào)度策略以延長網(wǎng)絡(luò)覆蓋時(shí)間.在陸地傳感器網(wǎng)絡(luò)的路由算法中,已經(jīng)有一些相關(guān)研究[10～15],如Meng等人[13]設(shè)計(jì)了一個(gè)選取最小工作節(jié)點(diǎn)保證網(wǎng)絡(luò)覆蓋質(zhì)量和網(wǎng)絡(luò)連通性的調(diào)度控制算法.Fan等人[14]設(shè)計(jì)了基于容忍覆蓋區(qū)域的節(jié)點(diǎn)調(diào)度算法,以緩解在傳統(tǒng)節(jié)點(diǎn)調(diào)度算法中出現(xiàn)的邊界區(qū)域節(jié)點(diǎn)過早死亡問題.但是在水下傳感器網(wǎng)絡(luò)路由算法設(shè)計(jì)中,大都以“能量”為度量選舉簇首或者根據(jù)水下特性設(shè)計(jì)分簇算法,未將“覆蓋”作為考慮因素,忽略了簇首因能量耗盡對(duì)監(jiān)測(cè)區(qū)域覆蓋效果的影響,網(wǎng)絡(luò)運(yùn)行期間很難保證網(wǎng)絡(luò)覆蓋率.Jiang等人[19]在研究陸地傳感器網(wǎng)絡(luò)覆蓋保持路由算法的基礎(chǔ)上針對(duì)水下傳感器網(wǎng)絡(luò)提出一種覆蓋保持路由算法NCPR算法.相對(duì)比LEACH-Coverage-U[18]算法,該算法提高了網(wǎng)絡(luò)覆蓋率,延長了網(wǎng)絡(luò)生命周期.但是該算法在使用時(shí)有局限性:當(dāng)節(jié)點(diǎn)通信半徑受限時(shí),該算法網(wǎng)絡(luò)連通性表現(xiàn)較差,同時(shí)存在靠近SINK節(jié)點(diǎn)的簇首由于需要轉(zhuǎn)發(fā)大量的數(shù)據(jù)而過早死亡的問題.針對(duì)上述問題,本文提出一種分布式網(wǎng)絡(luò)不均勻分層的覆蓋保持路由算法(NetworkUnevenlyLayeredCoveragePreservingRouting,NULCPR),空間上從SINK節(jié)點(diǎn)開始向外逐級(jí)建立網(wǎng)絡(luò),構(gòu)建一個(gè)邏輯上以SINK節(jié)點(diǎn)為根向下的樹形拓?fù)浣Y(jié)構(gòu).節(jié)點(diǎn)離SINK越遠(yuǎn),則在這個(gè)樹形拓?fù)浣Y(jié)構(gòu)中所處的層級(jí)也越靠下.每層獨(dú)立運(yùn)行NCPR算法完成簇首選舉,每層簇首與上層的節(jié)點(diǎn)建立連通鏈路以保證網(wǎng)絡(luò)連通.同時(shí)每層節(jié)點(diǎn)的通信半徑隨著網(wǎng)絡(luò)層數(shù)的增加而逐漸增大.這樣使得靠近SINK節(jié)點(diǎn)的區(qū)域節(jié)點(diǎn)通信半徑小,簇密度大,距離SINK節(jié)點(diǎn)較遠(yuǎn)的區(qū)域,節(jié)點(diǎn)通信半徑大,簇密度小,通過這樣的方式均衡網(wǎng)絡(luò)能耗,延長網(wǎng)絡(luò)生存時(shí)間.仿真結(jié)果表明,與NCPR算法相比,NULCPR算法提高了網(wǎng)絡(luò)連通率以及網(wǎng)絡(luò)覆蓋率,并且降低了網(wǎng)絡(luò)能耗.

2　相關(guān)模型與定義

2.1網(wǎng)絡(luò)模型

假設(shè)所有傳感器節(jié)點(diǎn)隨機(jī)均勻的部署在水下監(jiān)測(cè)區(qū)域內(nèi),SINK節(jié)點(diǎn)隨機(jī)部署在監(jiān)測(cè)區(qū)域水面上,節(jié)點(diǎn)一入水就拋錨固定自身的位置.節(jié)點(diǎn)之間使用聲學(xué)方式通信.SINK節(jié)點(diǎn)和地面監(jiān)測(cè)站之間采用無線電波通信.同時(shí)網(wǎng)絡(luò)還存在以下假設(shè):

(1)節(jié)點(diǎn)采用布爾感知模型,即若任意節(jié)點(diǎn)i的感知半徑為Rs,則節(jié)點(diǎn)i的感知區(qū)域是以該節(jié)點(diǎn)所在位置為圓心、Rs為半徑的球體;

(2)除SINK節(jié)點(diǎn)外所有節(jié)點(diǎn)都是同構(gòu)的,具備數(shù)據(jù)融合的功能且每個(gè)節(jié)點(diǎn)都有唯一的標(biāo)識(shí)(ID);

(3)節(jié)點(diǎn)可調(diào)節(jié)其發(fā)射功率.

2.2能耗模型

本文采用以聲波為媒介的水下傳感器網(wǎng)絡(luò)數(shù)據(jù)通信能耗模型[20],首先給出水下聲信號(hào)衰減模型A(d):

A(d)=dλαd

(1)

其中,λ為能量擴(kuò)散因子(圓柱形擴(kuò)散為1,實(shí)際情況為1.5,球形擴(kuò)散為2),參數(shù)α=10a(f)/10,由吸收系數(shù)[13]α(f)決定,f為載波頻率,單位為kHz,吸收系數(shù)的單位為dB/m.

10logα(f)

(2)

節(jié)點(diǎn)消耗的能量為:

E=Esend+Erec+Eintg

(3)

Esend=lP0A(d),Erec=lPr,Eintg=lEda

(4)

其中,Esend為發(fā)送數(shù)據(jù)能耗,Erec為接收數(shù)據(jù)能耗,Eintg為數(shù)據(jù)融合能耗,d為發(fā)送節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的距離,Pr是常數(shù),表示節(jié)點(diǎn)接受1bit數(shù)據(jù)消耗的能量,l表示數(shù)據(jù)包大小.P0為節(jié)點(diǎn)可以接收到單位數(shù)據(jù)包需要的最小功率[21].

2.3覆蓋冗余度(CR)

節(jié)點(diǎn)i的覆蓋冗余度定義為它的一跳通信范圍內(nèi)節(jié)點(diǎn)(neighbour(i))的感知區(qū)域與該節(jié)點(diǎn)感知區(qū)域重疊部分的體積占其感知區(qū)域體積的比值.表示為:

(5)

其中,ai表示節(jié)點(diǎn)i的感知區(qū)域.計(jì)算如下式所示:

(6)

其中,n為節(jié)點(diǎn)i鄰居節(jié)點(diǎn)個(gè)數(shù),Rs為節(jié)點(diǎn)感知半徑.dit為鄰居節(jié)點(diǎn)t與節(jié)點(diǎn)i之間的距離.

3　問題描述與算法描述

3.1問題描述

基于分簇的傳感器網(wǎng)絡(luò)中,當(dāng)簇首以單跳或者多跳的通信方式將數(shù)據(jù)傳輸?shù)絊INK節(jié)點(diǎn)時(shí),由于簇首轉(zhuǎn)發(fā)大量數(shù)據(jù)而負(fù)載過重,容易過早耗盡能量而死亡,這將導(dǎo)致提前出現(xiàn)覆蓋盲區(qū).針對(duì)該問題,Jiang等人[19]在Tsai等人[18]的基礎(chǔ)上針對(duì)水下傳感器網(wǎng)絡(luò)提出一種覆蓋保持路由算法NCPR,文中首先定義了三維空間中節(jié)點(diǎn)的覆蓋冗余度,該指標(biāo)表征了節(jié)點(diǎn)的感知區(qū)域被鄰居節(jié)點(diǎn)覆蓋的程度,覆蓋冗余越大的節(jié)點(diǎn)死亡后對(duì)網(wǎng)絡(luò)覆蓋率的影響越小,然后文章提出一種覆蓋保持路由算法,主要步驟歸納如下:

(1)初始化階段

網(wǎng)絡(luò)初始時(shí),每個(gè)節(jié)點(diǎn)根據(jù)其與鄰居節(jié)點(diǎn)的距離計(jì)算CR,與鄰居節(jié)點(diǎn)的距離可通過RSSI或者TOA方式獲得,然后每個(gè)節(jié)點(diǎn)根據(jù)CR設(shè)定自身等待時(shí)間

Ti=(1-r(i))+rand(0,a)

(7)

其中,a為一隨機(jī)數(shù).由式(7)可以看出,CR大的節(jié)點(diǎn)將率先聲明為簇首,同時(shí)其他節(jié)點(diǎn)加入距離自身最近的簇首以減少通信能耗,然后進(jìn)入穩(wěn)定工作階段.

(2)穩(wěn)定工作階段

初始化階段結(jié)束后,簇首為簇內(nèi)成員分配各自的TDMA時(shí)隙,簇內(nèi)成員在各自分配的時(shí)隙內(nèi)以單跳的方式將采集到的數(shù)據(jù)發(fā)送至簇首,簇首對(duì)數(shù)據(jù)進(jìn)行融合處理后將數(shù)據(jù)發(fā)送至SINK節(jié)點(diǎn).當(dāng)一輪數(shù)據(jù)傳輸工作完成后,若未出現(xiàn)死亡節(jié)點(diǎn),則繼續(xù)以上一輪選舉的簇首進(jìn)行數(shù)據(jù)傳輸.如出現(xiàn)死亡節(jié)點(diǎn)則重新選舉簇首.

相比于LEACH-Coverage-U[18]算法,該算法降低了網(wǎng)絡(luò)能耗,提高了網(wǎng)絡(luò)覆蓋率,延長了網(wǎng)絡(luò)生命周期.但是當(dāng)節(jié)點(diǎn)通信半徑受限時(shí),該算法網(wǎng)絡(luò)連通性較差,簇與簇之間,以及簇與SINK節(jié)點(diǎn)之間有可能不能連通,導(dǎo)致局部網(wǎng)絡(luò)中斷,嚴(yán)重時(shí),整個(gè)網(wǎng)絡(luò)都將中斷.同時(shí)由于靠近SINK節(jié)點(diǎn)的節(jié)點(diǎn)要轉(zhuǎn)發(fā)大量的數(shù)據(jù),很容易過早死亡.這同樣會(huì)造成網(wǎng)路中斷導(dǎo)致網(wǎng)絡(luò)壽命縮短.

針對(duì)上述問題,本文提出一種分布式的網(wǎng)絡(luò)不均勻分層的覆蓋保持路由算法,空間上從SINK節(jié)點(diǎn)開始向外逐級(jí)建立網(wǎng)絡(luò),構(gòu)建一個(gè)邏輯上以SINK節(jié)點(diǎn)為根向下的樹形拓?fù)浣Y(jié)構(gòu).節(jié)點(diǎn)離SINK越遠(yuǎn),則在這個(gè)樹形拓?fù)浣Y(jié)構(gòu)中所處的層級(jí)也越靠下.每層獨(dú)立運(yùn)行NCPR算法完成該層簇首選舉,然后簇首與上層網(wǎng)絡(luò)節(jié)點(diǎn)建立連通鏈路維持層與層之間的連通.同時(shí)每層節(jié)點(diǎn)的通信半徑隨著網(wǎng)絡(luò)層數(shù)的增加而增大.這樣使得靠近SINK節(jié)點(diǎn)的區(qū)域節(jié)點(diǎn)通信半徑小,簇密度大,距離SINK節(jié)點(diǎn)較遠(yuǎn)的區(qū)域,節(jié)點(diǎn)通信半徑大,簇密度小.通過這樣的方式均衡網(wǎng)絡(luò)能耗,延長網(wǎng)絡(luò)生存時(shí)間.

3.2算法描述

NULCPR算法分為兩個(gè)階段,網(wǎng)絡(luò)建立階段和穩(wěn)定工作階段.初始時(shí),所有節(jié)點(diǎn)層號(hào)設(shè)置為總節(jié)點(diǎn)數(shù)加一.

(1)網(wǎng)絡(luò)建立階段

(a)SINK節(jié)點(diǎn)以最大廣播半徑(max-br)廣播消息(節(jié)點(diǎn)號(hào),所屬層號(hào)),如節(jié)點(diǎn)能夠接收到消息,說明該節(jié)點(diǎn)在SINK節(jié)點(diǎn)的一跳通信范圍內(nèi),那么該節(jié)點(diǎn)將SINK節(jié)點(diǎn)設(shè)置為自身的簇首節(jié)點(diǎn),同時(shí)設(shè)置自身層號(hào)為1(node(i).level=1),廣播半徑(node(i).br)為initial-range(初始半徑,仿真時(shí)設(shè)定),如圖1(a)所示.設(shè)置完成后,進(jìn)行下一步.

(b)步驟(a)中設(shè)置完成的節(jié)點(diǎn)i以廣播半徑廣播消息,接收到該消息的節(jié)點(diǎn)j,檢查自身層號(hào),若大于節(jié)點(diǎn)i的層號(hào),即(node(j).level>node(i).level),則將自身所屬層號(hào)設(shè)置為node(i).level+1,廣播半徑以及所屬層半徑(range(node(j).level))大小設(shè)置為node(i).br.等待一段時(shí)間后,新一層網(wǎng)絡(luò)的節(jié)點(diǎn)選擇完成,然后該層的節(jié)點(diǎn)開始運(yùn)行NCPR算法進(jìn)行簇首選舉,簇首選舉完成后(如圖1(b)所示),該層所有節(jié)點(diǎn)更新廣播半徑為node(j).br=range(node(j).level)+initial-range,接著進(jìn)行下一步,簇首向上建立連通鏈路.

(c)步驟(b)中選出的簇首節(jié)點(diǎn)k以廣播半徑廣播消息,接收到消息的節(jié)點(diǎn),檢查自身的層號(hào),若層號(hào)等于node(k).level-1,則應(yīng)答此消息.簇首節(jié)點(diǎn)接收到反饋信息后,選擇其中覆蓋冗余度值最大的節(jié)點(diǎn)作為下跳節(jié)點(diǎn)(稱該節(jié)點(diǎn)為連通節(jié)點(diǎn)),如圖1(c)所示.若沒有任何消息返回,并且此時(shí)node(k).br

(2)穩(wěn)定工作階段

網(wǎng)絡(luò)建立階段結(jié)束后,節(jié)點(diǎn)開始進(jìn)入穩(wěn)定工作階段.當(dāng)節(jié)點(diǎn)能量值低于閾值E0,說明該節(jié)點(diǎn)死亡,這時(shí)進(jìn)入網(wǎng)絡(luò)重建階段,根據(jù)死亡節(jié)點(diǎn)類型分為四種情況處理:

(a)如死亡的節(jié)點(diǎn)是普通簇內(nèi)節(jié)點(diǎn),鄰居節(jié)點(diǎn)將該節(jié)點(diǎn)從鄰居鏈表中刪除并且簇首節(jié)點(diǎn)將該節(jié)點(diǎn)從簇內(nèi)集合中刪除.

(b)如果死亡節(jié)點(diǎn)是簇首節(jié)點(diǎn)并且不是連通節(jié)點(diǎn),則其簇內(nèi)節(jié)點(diǎn)恢復(fù)離散狀態(tài),加入距離自己最近的簇首,若一跳通信范圍內(nèi)沒有簇首,則運(yùn)行NCPR算法選擇簇首,并執(zhí)行網(wǎng)絡(luò)建立階段步驟(c)向上建立連通鏈路.

(c)如果死亡的節(jié)點(diǎn)是連通節(jié)點(diǎn)且為簇內(nèi)節(jié)點(diǎn),則首先執(zhí)行穩(wěn)定工作階段中步驟(a),然后通知以該節(jié)點(diǎn)為下跳節(jié)點(diǎn)的簇首節(jié)點(diǎn)重新選擇下跳節(jié)點(diǎn).

(d)如死亡的節(jié)點(diǎn)是連通節(jié)點(diǎn)且為簇首節(jié)點(diǎn),則首先按照死亡節(jié)點(diǎn)是普通簇首節(jié)點(diǎn)處理,然后按照死亡節(jié)點(diǎn)是連通節(jié)點(diǎn)處理.

4　算法復(fù)雜度分析

在這一小節(jié),我們從時(shí)間復(fù)雜度和消息復(fù)雜度兩個(gè)方面對(duì)本文算法進(jìn)行復(fù)雜度分析,相關(guān)符號(hào)說明如表1所示.

表1　相關(guān)符號(hào)說明

4.1時(shí)間復(fù)雜度分析

因?yàn)镹ULCPR算法是從上往下逐層建立網(wǎng)絡(luò),所以網(wǎng)絡(luò)建立完成時(shí)間取決于每層網(wǎng)絡(luò)建立所需要時(shí)間和網(wǎng)絡(luò)總層數(shù).

每層網(wǎng)絡(luò)的建立主要由以下幾步組成:

(1)確定屬于該層網(wǎng)絡(luò)的節(jié)點(diǎn),這最長需要時(shí)間max-br/v.

(2)節(jié)點(diǎn)等待時(shí)間,為確保該層網(wǎng)絡(luò)中所有節(jié)點(diǎn)都確認(rèn)完畢,時(shí)間設(shè)置為max-br/v.

(3)節(jié)點(diǎn)確認(rèn)并等待一段時(shí)間后,開始運(yùn)行NCPR算法進(jìn)行該層網(wǎng)絡(luò)成簇.節(jié)點(diǎn)首先廣播自身信息,節(jié)點(diǎn)根據(jù)接收到的信息選擇出簇首,并廣播信息申請(qǐng)加入.簇首節(jié)點(diǎn)接收申請(qǐng)加入信息后發(fā)送應(yīng)答消息.這一過程需要三次通信.因此最多需要時(shí)間max-br/v*3.

(4)每層網(wǎng)絡(luò)成簇后,由簇首向上建立連通鏈路.這同樣需要三次通信,最多需要時(shí)間max-br/v*3.因此每層網(wǎng)絡(luò)建立最多需要時(shí)間(max-br/v+max-br/v+max-br/v*3+max-br/v*3)=max-br/v*8.網(wǎng)絡(luò)中總層數(shù)最多為depth/max-br-1+max-br/initial-range,若我們?nèi)nitial-range=1/m*max-br,那么網(wǎng)絡(luò)總層數(shù)最多為depth/max-br-1+m.因此,完成整個(gè)網(wǎng)絡(luò)建設(shè)最多需要時(shí)間(depth/max-br-1+m)*(max-br/v*8)=8*(depth/v-max-br/v+m*max-br/v),復(fù)雜度為O((depth+(m-1)max-br)/v).

4.2消息復(fù)雜度分析

由于發(fā)送消息能耗遠(yuǎn)遠(yuǎn)大于接收消息能耗.因此,這里只討論發(fā)送消息的復(fù)雜度.

在NULCPR算法中,消息發(fā)送主要涉及三個(gè)部分.

(1)上層網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)送消息已確定下層網(wǎng)絡(luò)節(jié)點(diǎn).該部分整個(gè)網(wǎng)絡(luò)需要發(fā)送total-node個(gè)消息.

(2)每層網(wǎng)絡(luò)節(jié)點(diǎn)運(yùn)行NCPR算法,使得本層網(wǎng)絡(luò)成簇.因?yàn)楣?jié)點(diǎn)間需要三次通信,因此總共需要發(fā)送消息數(shù)total-node*3.

(3)由每層簇首向上建立連通鏈路,這需要發(fā)送消息數(shù)total-cluster+total-node+total-cluster+total-cluster=total-node+total-cluster*3.因此建立網(wǎng)絡(luò)總的發(fā)送數(shù)目為total-node+total-node*3+total-node+total-cluster*4,而total-cluster

5　仿真算例與性能分析

5.1仿真場(chǎng)景以及參數(shù)設(shè)置

為了分析NULCPR算法的有效性.對(duì)NULCPR算法以及NCPR算法的網(wǎng)絡(luò)剩余能量,網(wǎng)絡(luò)覆蓋率,網(wǎng)絡(luò)連通率等指標(biāo)進(jìn)行仿真對(duì)比和分析.覆蓋率和連通率定義如下.

覆蓋率:處于活躍狀態(tài)的節(jié)點(diǎn)的感知區(qū)域與監(jiān)測(cè)區(qū)域體積的比值.

連通率:至少擁有一條到SINK節(jié)點(diǎn)的鏈路的節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)的比值.

仿真時(shí),將200個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署在100m*100m*100m的水下三維監(jiān)測(cè)區(qū)域M中,SINK節(jié)點(diǎn)隨機(jī)放置在水面某一點(diǎn).同時(shí)為計(jì)算網(wǎng)絡(luò)覆蓋率,將區(qū)域M劃分為100*100*100個(gè)立方格,每個(gè)立方格的大小為1m*1m*1m,仿真結(jié)果是100次實(shí)驗(yàn)的平均值,其他參數(shù)如表2所示.

表2　仿真參數(shù)

5.2仿真算例

我們首先在節(jié)點(diǎn)最大通信半徑受限的情況下,對(duì)NULCPR算法和NCPR算法的網(wǎng)絡(luò)連通率進(jìn)行對(duì)比.

圖2是最大節(jié)點(diǎn)通信半徑分別為20m,30m,40m時(shí),NCPR算法和NULCPR算法的網(wǎng)絡(luò)連通率的對(duì)比圖.從圖中可以看出,NCPR算法和NULCPR算法的網(wǎng)絡(luò)連通率均隨網(wǎng)絡(luò)運(yùn)行輪數(shù)的增加而減小,但是在不同的節(jié)點(diǎn)通信半徑下NCPR算法的網(wǎng)絡(luò)連通率始終處于一個(gè)較低的位置,并且當(dāng)節(jié)點(diǎn)通信半徑為20m時(shí),網(wǎng)絡(luò)處于完全斷開的狀態(tài).這是因?yàn)樵贜CPR算法中,簇首的分布具有隨機(jī)性,在節(jié)點(diǎn)通信半徑受限的情況下,當(dāng)簇首之間的距離小于節(jié)點(diǎn)通信半徑時(shí),簇與簇可以連通,而當(dāng)簇首之間距離大于節(jié)點(diǎn)通信半徑時(shí),則簇與簇?cái)嚅_,造成網(wǎng)絡(luò)中斷.在NULCPR算法中,網(wǎng)絡(luò)建立時(shí),每層節(jié)點(diǎn)成簇后,由簇首向上建立連通鏈路保證網(wǎng)絡(luò)連通,當(dāng)節(jié)點(diǎn)死亡后,根據(jù)死亡節(jié)點(diǎn)的類型采用不同的方式重新建立連通鏈路以維持網(wǎng)絡(luò)的連通,因而NULCPR算法的網(wǎng)絡(luò)連通率高于NCPR算法.

因?yàn)樵贜CPR算法中假設(shè)簇首始終可與SINK節(jié)點(diǎn)通信,因此,為了對(duì)比NCPR與NULCPR算法的網(wǎng)絡(luò)能耗與網(wǎng)絡(luò)覆蓋率,我們同樣假設(shè)簇首始終可與SINK節(jié)點(diǎn)連通,初始節(jié)點(diǎn)通信半徑設(shè)為30m.

圖3是NCPR算法和NULCPR算法的網(wǎng)絡(luò)剩余能量對(duì)比圖.圖4為NULCPR算法和NCPR算法的網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)對(duì)比圖.從圖3可以看出,NCPR算法和NULCPR算法的網(wǎng)絡(luò)剩余能量均隨網(wǎng)絡(luò)的運(yùn)行而逐漸降低,但是NULCPR算法的剩余能量始終高于NCPR算法.這是因?yàn)樵贜ULCPR算法中,節(jié)點(diǎn)通信半徑隨著距離SINK節(jié)點(diǎn)越來越遠(yuǎn)而逐漸增大.這樣距離SINK節(jié)點(diǎn)較遠(yuǎn)的區(qū)域中節(jié)點(diǎn)通信半徑大,簇密度小,距離SINK節(jié)點(diǎn)近的區(qū)域簇密度大,節(jié)點(diǎn)通信半徑小,但是節(jié)點(diǎn)需要轉(zhuǎn)發(fā)的數(shù)據(jù)包大.通過這樣的方式,減少了網(wǎng)絡(luò)能耗.在NCPR算法中,由于簇半徑比較大,因此簇首和簇邊緣的節(jié)點(diǎn)較容易死亡,導(dǎo)致簇更新頻繁,造成網(wǎng)絡(luò)能量消耗過快,從圖4中也可以看出這點(diǎn).

圖5是NULCPR算法和NCPR算法的網(wǎng)絡(luò)覆蓋率隨網(wǎng)絡(luò)運(yùn)行輪數(shù)變化對(duì)比圖.從圖中可以看出,NULCPR算法和NCPR算法的網(wǎng)絡(luò)覆蓋率均隨網(wǎng)絡(luò)運(yùn)行輪數(shù)的增加而減小,但是在網(wǎng)絡(luò)運(yùn)行的中間階段,NULCPR算法的網(wǎng)絡(luò)覆蓋率要好于NCPR算法.這主要是因?yàn)镹ULCPR算法中節(jié)點(diǎn)死亡速度較慢,網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)目較多,因而網(wǎng)絡(luò)覆蓋率較好,從圖4中我們可以看出這點(diǎn).圖6為NULCPR算法和NCPR算法的網(wǎng)絡(luò)覆蓋率隨死亡節(jié)點(diǎn)數(shù)變化對(duì)比圖.從圖中可以看出,當(dāng)死亡相同的節(jié)點(diǎn)數(shù)時(shí),NCPR算法的網(wǎng)絡(luò)覆蓋率要高于NULCPR算法.這是因?yàn)樵贜ULCPR算法中,每層獨(dú)立的運(yùn)行NCPR算法,這時(shí)每層選出的簇首相對(duì)于在整個(gè)網(wǎng)絡(luò)中運(yùn)行NCPR算法選擇簇首來說是局部最優(yōu),當(dāng)網(wǎng)絡(luò)中死亡相同的節(jié)點(diǎn)數(shù)時(shí),對(duì)NULCPR算法的網(wǎng)絡(luò)覆蓋率的影響要大于對(duì)NCPR算法網(wǎng)絡(luò)覆蓋率的影響.因此,在死亡相同節(jié)點(diǎn)數(shù)下,NCPR算法的網(wǎng)絡(luò)覆蓋率要優(yōu)于NULCPR算法.

6　總結(jié)

在以監(jiān)測(cè)為目的的水下傳感器網(wǎng)絡(luò)中,較高的網(wǎng)絡(luò)覆蓋率和網(wǎng)絡(luò)連通率是完成監(jiān)測(cè)任務(wù)的重要保證.本文在水下傳感器網(wǎng)絡(luò)覆蓋保持路由算法NCPR算法的基礎(chǔ)上提出一種網(wǎng)絡(luò)不均勻分層的覆蓋保持路由算法(NULCPR),由SINK節(jié)點(diǎn)開始逐層建立網(wǎng)絡(luò),每一層節(jié)點(diǎn)的通信半徑隨著網(wǎng)絡(luò)層數(shù)的增加而增加,每層網(wǎng)絡(luò)獨(dú)立的運(yùn)行NCPR算法使該層節(jié)點(diǎn)成簇,并由簇首向上建立連通鏈路以保證網(wǎng)絡(luò)連通.仿真結(jié)果表明,與NCPR算法相比,NULCPR算法提高了網(wǎng)絡(luò)連通率以及網(wǎng)絡(luò)覆蓋率,并且降低了網(wǎng)絡(luò)能耗.

[1]AkyildizIF,PompiliD,MelodiaT.Underwateracousticsensornetworks:researchchallenges[J].AdHocNetworks,2005,3(3):257-279.

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

GuoZhongwen,LuoHanjiang,HongFeng,etal.Currentprogressandresearchissuesinunderwatersensornetworks[J].JournalofComputreResearchandDevelopment,2010,47(3):377-389.(inChinese)

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

HongFeng,ZhangYuliang,YangBozhen,etal.Reviewontimesynchronizationtechniquesinunderwateracousticsensornetworks[J].ActaElectronicaSinica,2013,41(5):960-965.(inChinese)

[4]GuerraF,CasariP,ZorziM.WorldOceanSimulationSystem(WOSS):asimulationtoolforunderwaternetworkswithrealisticpropagationmodeling[A].ProceedingsoftheFourthACMInternationalWorkshoponUnderwaterNetworks[C].NewYork:ACM,2009.1-4,8.

[5]TanHP,DiamantR,SeahWKG,etal.Asurveyoftechniquesandchallengesinunderwaterlocalization[J].OceanEngineering,2011,38(14):1663-1676.

[6]PompiliD,MelodiaT,AkyildizIF.Deploymentanalysisinunderwateracousticwirelesssensornetworks[A].Proceedingsofthe1stACMinternationalworkshoponUnderwaternetworks[C].NewYork:ACM,2006.48-55.

[7]AkkayaK,NewellA.Self-deploymentofsensorsformaximizedcoverageinunderwateracousticsensornetworks[J].ComputerCommunications,2009,32(7):1233-1244.

[8]夏娜,王長生,鄭榕,等.魚群?jiǎn)l(fā)的水下傳感器節(jié)點(diǎn)布置[J].自動(dòng)化學(xué)報(bào),2012,38(2):295-302.

XiaNa,WangChangsheng,ZhengRong,etal.Fishswarminspiredunderwatersensordeployment[J].ActaAutomaticaSinica,2012,38(2):295-302.(inChinese)

[9]ZouY,ChakrabartyK.Sensordeploymentandtargetlocalizationbasedonvirtualforces[A].Proceedingsofthe22thAnnualJointConference[C].SanFrancisco,CA:IEEE,2003:1293-1303.

[10]HwangSF,SuYY,LinYY,etal.Acluster-basedcoverage-preservednodeschedulingschemeinwirelesssensornetworks[A].Proceedingsofthe3rdAnnualInternationalConferenceonMobileandUbiquitousSystems-Workshops[C].SanJose,CA:IEEE,2006.1-7.

[11]ChamamA,PierreS.Ontheplanningofwirelesssensornetworks:Energy-efficientclusteringunderthejointroutingandcoverageconstraint[J].IEEETransactionsonMobileComputing,2009,8(8):1077-1086.

[12]SoroS,HeinzelmanWB.Clusterheadelectiontechniquesforcoveragepreservationinwirelesssensornetworks[J].AdHocNetworks,2009,7(5):955-972.

[13]孟凡治,王換招,何暉.基于聯(lián)合感知模型的無線傳感器網(wǎng)絡(luò)連通性覆蓋協(xié)議[J].電子學(xué)報(bào),2011,39(4):772-779.

MengFanzhi,WangHuanzhao,HeHui.Connectedcoverageprotocolusingcooperativesensingmodelforwirelesssensornetworks[J].ActaElectronicaSinica,2011,39(4):772-779.(inChinese)

[14]凡高娟,王汝傳,黃海平,等.基于容忍覆蓋區(qū)域的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度算法[J].電子學(xué)報(bào),2011,39(1):89-94.

FanGaojuan,WangRuchuan,HuangHaiping,etal.Tolerablecoverageareabasednodeschedulingalgorithminwirelesssensornetworks[J].ActaElectronicaSinica,2011,39(1):89-94.(inChinese)

[15]MaoY,GongH,LiuM,etal.Energyefficientandlocation-independentQoSprotocolforwirelesssensornetworks[J].ComputerResearchandDevelopment,2006,43(6):1019-1026.

[16]LiuC,WuK,XiaoY,etal.Randomcoveragewithguaranteedconnectivity:jointschedulingforwirelesssensornetworks[J].IEEETransactionsonParallelandDistributedSystems,2006,17(6):562-575.

[17]王換招,孟凡治,李增智.高效節(jié)能的無線傳感器網(wǎng)絡(luò)覆蓋保持協(xié)議[J].軟件學(xué)報(bào),2010,21(12):3124-3137.

WangHuanzhao,MengFanzhi,LiZengzhi.Energyefficientcoverageconservingprotocolforwirelesssensornetworks[J].JournalofSoftware,2010,21(12):3124-3137.(inChinese)

[18]TsaiYR.Coverage-preservingroutingprotocolsforrandomlydistributedwirelesssensornetworks[J].IEEETransactionsonWirelessCommunications,2007,6(4):1240-1245.

[19]蔣鵬,阮斌峰.基于分簇的水下傳感器網(wǎng)絡(luò)覆蓋保持路由算法[J].電子學(xué)報(bào),2013,41(10):2067-2073.

JiangPeng,RuanBinfeng.Cluster-basedcoveragepreservingroutingalgorithmforunderwatersensornetworks[J].ActaElectronicaSinica,2013,41(10):2067-2073.(inChinese)

[20]LiuG,WeiC.Anewmulti-pathroutingprotocolbasedonclusterforunderwateracousticsensornetworks[A].Proceedingsofthe2011InternationalConferenceonMultimediaTechnology[C].Hangzhou:IEEE,2011.91-94.

[21]SozerEM,StojanovicM,ProakisJG.Underwateracousticnetworks[J].IEEEJournalofOceanicEngineering,2000,25(1):72-83.

蔣鵬男,1975年生于浙江衢州.杭州電子科技大學(xué)教授、博士生導(dǎo)師,主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、嵌入式系統(tǒng)及其應(yīng)用、智能儀表.

E-mail:pjiang@hdu.edu.cn

王興民男,1989年生于甘肅景泰.杭州電子科技大學(xué)碩士研究生,研究方向?yàn)闊o線傳感器網(wǎng)絡(luò).

Network Layered Coverage Preserving Routing Algorithm for Underwater Sensor Networks

JIANG Peng,WANG Xing-min

(College of Automation,Hangzhou Dianzi University,Hangzhou,Zhejiang 310018,China)

Intheunderwatersensornetworksforunderwaterenvironmentmonitoringapplication,anetworkwithsufficientlyhighcoverageandconnectivityrateistheguaranteeofaccomplishingthemonitoringtask.TheNCPRalgorithm,whichisaunderwatercoveragepreservingroutingalgorithmandorientedtoimprovethecoverageperformance,caneffectivelyprolongthecoveragetimeofthenetworkscomparedtotheLEACH-Coverage-Ualgorithm.However,theconnectivityperformanceofNCPRisdefective,andinthealgorithmthereexistsuchaproblemthattheclusterheadsclosetotheSINKnodemaydiefasterthanothernodesbecauseofthefrequentlyforwardingofdata.Inthispaper,weproposeadistributednetworkunevenlylayeredcoveragepreservingroutingalgorithm(NULCPR)toimprovetheperformanceofNCPR.ThenetworkisestablishedfromSINKlayerbylayer,andthecommunicationrangeofnodesincreasewiththelayerdeparturesformSINK.EachlayerexecutestheNCPRalgorithmindependentlytoclusterthenodesinthislayer,andtheclusternodeisusedtoestablishaconnectivelinktomaintaintheconnectivityofthenetworks.ThesimulationresultsshowthatcomparingwithNCPR,NULCPRimprovestheconnectivityandcoveragerateofthenetworks,andmakestheenergyefficiencybetter.

underwatersensornetwork;coveragepreservingrouting;networklayering

2014-09-23;

2015-01-13；責(zé)任編輯：藍(lán)紅杰

國家自然科學(xué)基金(No.61273072);浙江省環(huán)?？萍加?jì)劃(No.2013A034);浙江省安全生產(chǎn)科技計(jì)劃(No.2013A1006)

TP393

A

0372-2112 (2016)05-1240-07

電子學(xué)報(bào)URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.033