基于遺傳算法的水下傳感器網(wǎng)絡(luò)節(jié)點部署算法研究*

金合麗,劉半藤,陳 唯,凌家順

(浙江樹人大學(xué)信息工程學(xué)院,杭州 310015)

水下無線傳感網(wǎng)絡(luò)UWSN(Underwater Wireless Sensor Networks)是將低能耗、通信距離受限的節(jié)點部署在指定水域中,利用節(jié)點的自組織能力自動組網(wǎng),對指定區(qū)域內(nèi)的信息進行采集并完成相應(yīng)的數(shù)據(jù)收集和整理[1]。UWSN在海洋資源勘探、海洋環(huán)境監(jiān)測以及海洋軍事領(lǐng)域有廣泛且重要的用途,已經(jīng)引起工業(yè)界、學(xué)術(shù)界以及軍事界的極大關(guān)注。近年來,隨著各國發(fā)展海洋經(jīng)濟熱潮興起,UWSN已經(jīng)成為無線傳感器網(wǎng)絡(luò)的熱點新興研究領(lǐng)域之一。

區(qū)別于傳統(tǒng)二維無線傳感網(wǎng)絡(luò)2D-WSN(Wireless Sensor Networks),UWSN需要監(jiān)測三維水域環(huán)境。由于水下環(huán)境復(fù)雜多變且僅能依靠衰落較快的聲波信號傳輸信息、節(jié)點成本高、網(wǎng)絡(luò)能耗大等原因,許多2D-WSN的方法并不適用于UWSN[2]。由于水下節(jié)點部署研究直接關(guān)系到網(wǎng)絡(luò)的節(jié)點能量、通信帶寬、監(jiān)測信息的準確性,成為UWSN眾多研究方向的首要待解決問題。

近年來,有不少學(xué)者針對UWSN節(jié)點部署開展廣泛而深入的研究。由于水下傳感器節(jié)點成本高,節(jié)點數(shù)量優(yōu)化往往成為UWSN節(jié)點部署的首要考慮目標(biāo)[3]。目前,對于UWSN節(jié)點部署方案可以歸納為以下兩類:在滿足一定條件的情況下,使得網(wǎng)絡(luò)所需節(jié)點數(shù)量最小化;或者在網(wǎng)絡(luò)節(jié)點數(shù)量不超過某定量時,使得網(wǎng)絡(luò)性能達到最優(yōu)化。網(wǎng)絡(luò)整體覆蓋率與節(jié)點間連通率也是網(wǎng)絡(luò)構(gòu)建的重要指標(biāo)[4-5]。例如,趙敏華等人提出了一種非均勻簡單立方格節(jié)點部署算法。該算法在確保網(wǎng)絡(luò)覆蓋率的情況下,考慮水聲網(wǎng)絡(luò)能耗特點,可有效降低網(wǎng)絡(luò)能耗,提高網(wǎng)絡(luò)壽命[6]。田祥宏以網(wǎng)絡(luò)覆蓋率和節(jié)點分布均勻度為目標(biāo)函數(shù),提出了一種基于黏性流體算法的優(yōu)化部署方案,并運用魚群優(yōu)化算法進行求解[7]。李世偉等人提出一種基于潛艇深度的節(jié)點部署算法,通過潛艇深度信息的概率模型設(shè)計節(jié)點的活動狀態(tài),提高覆蓋率[8]。胡照鵬等人提出一種基于矩形分區(qū)覆蓋的節(jié)點確定部署策略,采用矩形分區(qū)覆蓋部署方式減少部署節(jié)點的數(shù)量并減少路由跳數(shù)[9]。郭秀明等人提出一種基于網(wǎng)格掃面實現(xiàn)確定性目標(biāo)點覆蓋的節(jié)點部署方法,為了選擇合適的位置放置節(jié)點將目標(biāo)區(qū)域劃分成若干正方形網(wǎng)格并提出一種評價標(biāo)準,實現(xiàn)最少的節(jié)點對目標(biāo)覆蓋[10]。高德民等人對無線傳感器網(wǎng)絡(luò)隨機分布模型的覆蓋問題進行研究,提出數(shù)學(xué)模型來量化節(jié)點密度、感知半徑和面積覆蓋率的關(guān)系,有效增加覆蓋面積并減少重覆蓋[11]。通過文獻綜述,可以發(fā)現(xiàn)大部分UWSN的節(jié)點部署方案在計算覆蓋率指標(biāo)時采用感知模型,將網(wǎng)絡(luò)離散成格點,以被感知格點數(shù)量所占格點總數(shù)比例記為網(wǎng)絡(luò)覆蓋率。這樣的計算方法雖然簡單,但容易出現(xiàn)覆蓋空洞,如圖1所示。

圖1 覆蓋算法中的覆蓋空洞示意圖

圖1中,雖然正方形區(qū)域的四個格點被兩個傳感器節(jié)點所覆蓋,但顯然傳感器節(jié)點并不能覆蓋整個正方形區(qū)域,存在“覆蓋空洞”。這也是很多文獻關(guān)于UWSN覆蓋率算法存在的不足之處。很多文獻在網(wǎng)絡(luò)連通性指標(biāo)上并沒有討論,沒有給出連通性的計算方法。本文從UWSN部署節(jié)點數(shù)量最小化角度出發(fā),對傳統(tǒng)的覆蓋算法進行修正,以整體網(wǎng)絡(luò)覆蓋率和節(jié)點連通率兩項指標(biāo)作為約束條件,建立整數(shù)非線性模型求解節(jié)點優(yōu)化部署方案。

1 節(jié)點模型

通常,UWSN由基站節(jié)點與普通傳感器節(jié)點兩種類型的節(jié)點構(gòu)成[12]。其中,基站節(jié)點(Sink)負責(zé)接收來自普通傳感器節(jié)點傳來的監(jiān)測海域的數(shù)據(jù)信息;普通傳感器節(jié)點負責(zé)采集覆蓋海域內(nèi)的信息并將其以多跳傳輸?shù)男问絺魉偷絊ink節(jié)點。為方便討論問題,假設(shè)UWSN每個傳感器節(jié)點具有固定的覆蓋半徑Rc和傳輸半徑Rn,其結(jié)構(gòu)如圖2和圖3所示。通常,Sink節(jié)點的傳輸半徑要遠大于普通節(jié)點的傳輸半徑。

圖2 水下傳感器網(wǎng)絡(luò)結(jié)構(gòu)示意圖

圖3 節(jié)點通信半徑與覆蓋半徑說明示意圖

每一個普通傳感器節(jié)點都可以采集覆蓋半徑內(nèi)的數(shù)據(jù)信息,并將采集獲得的數(shù)據(jù)信息轉(zhuǎn)發(fā)給距離其傳輸半徑內(nèi)的其他節(jié)點。

由于UWSN所需探測的三維環(huán)境復(fù)雜多變,為便于討論節(jié)點部署問題可將所探測的長方體區(qū)域劃分成較小規(guī)格的網(wǎng)格。例如,一個規(guī)格為K×M×L的長方體網(wǎng)絡(luò),以“1”為步長進行離散化處理將會形成N=(K+1)×(M+1)×(L+1)個格點,{K,M,L}∈Z+。網(wǎng)絡(luò)中的每一個格點位置都可以用三維坐標(biāo)(x,y,z)(x=1,2,…,K+1;y=1,2,…,M+1;z=1,2,…,L+1)進行唯一標(biāo)識。假設(shè)在文中討論最優(yōu)化網(wǎng)絡(luò)節(jié)點部署時,傳感器節(jié)點只能部署在格點。對于一個由N個格點構(gòu)成的UWSN,可以引入一個0-1決策矩陣G=(gxyz)(K+1)×(M+1)×(L+1)以表示是否在格點位置(x,y,z)放置傳感器節(jié)點,矩陣元素含義如下:

因此,最優(yōu)節(jié)點部署問題可以歸結(jié)為求解最優(yōu)決策矩陣G。

UWSN中的節(jié)點采用聲納方式相互通信。UWSN環(huán)境中,節(jié)點的能耗可以參考以聲波為媒介的UWSN數(shù)據(jù)通信能耗模型[13-14]。節(jié)點發(fā)送數(shù)據(jù)能耗Esend、節(jié)點接收數(shù)據(jù)能耗Erec、數(shù)據(jù)融合的能耗Eintg計算方式如下所示:

其中,l表示數(shù)據(jù)包的長度,Ps表示節(jié)點可以接收到單位數(shù)據(jù)所需的最小功率,d表示發(fā)送節(jié)點和目的節(jié)點之間的距離,Pr是常數(shù),Edate表示數(shù)據(jù)融合能耗,λ為能量擴散因子。由于水中信號呈現(xiàn)球形擴散,通常取λ=2[15]。α表示吸收參數(shù),由載波頻率f決定。

2 連通性指標(biāo)

當(dāng)傳感器節(jié)點采集區(qū)域信息后,將以節(jié)點間多跳傳輸?shù)男问絺鬟f到水面的Sink節(jié)點?？梢砸胍粋€六維的連通矩陣T=(txyz·opq)[(K+1)×(M+1)×(L+1)]×[(K+1)×(M+1)×(L+1)]表示位于(x,y,z)與(o,p,q)的兩個傳感器節(jié)點之間的連通狀況。由于每個傳感器的位置可以由一個三維坐標(biāo)確定,故連通矩陣是六維矩陣。在指定的某種節(jié)點部署方案G=(gxyz)(K+1)×(M+1)×(L+1)下,位于(x,y,z)與(o,p,q)的兩個傳感器節(jié)點間的一跳連通狀況計算方法如下:

txyz·opq=

當(dāng)位置(x,y,z)與位置(o,p,q)都放置傳感器節(jié)點(即gxyz=gopq=1),且兩點之間的距離小于傳輸半徑Rn時,說明兩個傳感器節(jié)點間可以相互傳輸信息,即認為此兩個傳感器節(jié)點是連通的。

假設(shè)UWSN網(wǎng)絡(luò)中Sink節(jié)點標(biāo)號為(sx,sy,sz)。由于海域中的任意一個普通傳感器節(jié)點都需要將監(jiān)測獲得的信息傳送到Sink節(jié)點。因此,對于位置(x,y,z)的傳感器節(jié)點而言,是否與Sink節(jié)點連通可以由下式計算獲得:

由于UWSN中所有的傳感器節(jié)點都能夠?qū)⒉杉男畔鬏數(shù)交維ink,應(yīng)該符合如下約束條件:

上式表明與Sink節(jié)點連通的傳感器節(jié)點數(shù)量等于UWSN網(wǎng)絡(luò)部署的節(jié)點總數(shù)。此約束條件可確保網(wǎng)絡(luò)中的每個節(jié)點都可以將信息傳輸至Sink。

3 覆蓋率指標(biāo)

為了改善“覆蓋空洞”問題,本文將網(wǎng)絡(luò)覆蓋問題轉(zhuǎn)化為KML個正方體的覆蓋問題。某個正方體的左下頂點(i,j,h),i=1,…,K;j=1,…,M;h=1,…,L,該正方體的頂點集合可以表示為:Sijh={(i,j,h),{i,j,h+1},{i,j+1,h},{i,j+1,h+1},(i+1,j,h),{i+1,j,h+1},{i+1,j+1,h},{i+1,j+1,h+1}}。因此,每一個正方體都可以用一個頂點集合唯一標(biāo)識,如Sijh。

如果存在一個傳感器節(jié)點距離UWSN中某正方體八個頂點的距離都小于覆蓋半徑Rc,則可以認為該正方體可以被傳感器節(jié)點有效覆蓋。傳感器節(jié)點覆蓋小正方體的情況可以用一個0-1覆蓋矩陣F=(fxyz·ijh)((K+1)×(M+1)×(L+1))×(K×M×L)表示。位于格點(x,y,z)的傳感器節(jié)點是否能夠覆蓋正方體Sijh可以計算如下:

若UWSN中的正方體Sijh可以被至少一個傳感器節(jié)點完整覆蓋,則認為該正方體可以被覆蓋。在覆蓋矩陣F的基礎(chǔ)上,某個正方體被覆蓋的情況可以用一個新的0-1覆蓋矩陣FF=(ffijh)(K×M×L)表示。

因此,在某種節(jié)點部署方案(G)下,網(wǎng)絡(luò)的覆蓋率Cov(G)可以用被覆蓋正方體體積占整體網(wǎng)絡(luò)體積百分比進行表示,計算方法如下:

因此,以部署傳感器節(jié)點數(shù)量最小化,要求網(wǎng)絡(luò)覆蓋率達到α以上,優(yōu)化模型可以表達如下:

4 算法設(shè)計與數(shù)值仿真

Step1設(shè)定網(wǎng)絡(luò)初始參數(shù),如網(wǎng)絡(luò)區(qū)域范圍、Sink節(jié)點位置、離散化格點邊長、初始種群數(shù)量、迭代最大代數(shù)、GA算法交叉概率、GA算法變異概率等基本參數(shù)。

Step2計算并判斷種群內(nèi)個體是否符合覆蓋范圍約束要求、連通度約束要求。如果種群內(nèi)個體不符合此兩項約束條件,隨機生成個體并重新判斷,直至使得種群內(nèi)個體數(shù)量等于初始種群數(shù)量。

Step3計算種群內(nèi)各個體的適應(yīng)度函數(shù)Fitness1(Ri),將種群個體按照適應(yīng)度函數(shù)值從大到小排序,選擇前10%的種群個體直接復(fù)制到下一代的種群。根據(jù)交叉準則,從原始種群中按照適應(yīng)度大小順序進行兩兩交叉,并將交叉后的結(jié)果放至下一代種群。根據(jù)變異準則,從原始種群中按照適應(yīng)度大小順序進行變異,并將變異后的結(jié)果放至下一代種群,直至使得下一代種群數(shù)量等于初始種群數(shù)量。檢查下一代種群數(shù)量是否等于初始種群數(shù)量。如果不足,則隨機生成個體加入下一代種群。

Step4檢查是否到達最大代數(shù)或者滿足算法結(jié)束條件。如果滿足結(jié)束條件,則輸出網(wǎng)絡(luò)最少節(jié)點數(shù)量Mopt。如果不滿足結(jié)束條件,則跳轉(zhuǎn)至Step 2。

為評價本文所提出的算法效果,本文采用MATLAB軟件進行數(shù)值仿真。針對一個60 m×60 m×60 m海域部署傳感器節(jié)點。以5 m為步長離散為13×13×13的格點。在GA中,設(shè)定迭代代數(shù)最多為30,初始種群大小為80,交叉概率為80%,變異概率為50%。

首先,討論針對不同的網(wǎng)絡(luò)覆蓋率要求,在不同的覆蓋半徑下,網(wǎng)絡(luò)最優(yōu)解點數(shù)量算法收斂如圖4、圖5所示。

圖4 網(wǎng)絡(luò)覆蓋率90%下,遺傳算法收斂圖

圖5 網(wǎng)絡(luò)覆蓋率100%要求下,遺傳算法收斂圖

對比不同的覆蓋率要求,可見在100%覆蓋率要求下需要部署的網(wǎng)絡(luò)節(jié)點數(shù)量要遠大于在90%覆蓋率要求下部署的網(wǎng)絡(luò)節(jié)點數(shù)量。例如,在覆蓋半徑為16 m時,實現(xiàn)網(wǎng)絡(luò)100%覆蓋需要的節(jié)點數(shù)量為75個,而實現(xiàn)網(wǎng)絡(luò)90%覆蓋僅需要的節(jié)點數(shù)量為47個。而在現(xiàn)實情況下,傳感器節(jié)點成本昂貴,而100%覆蓋并不是必須的。

討論不同覆蓋半徑下,不同覆蓋率要求所需部署最少節(jié)點數(shù)量如圖6所示。

從圖6可以發(fā)現(xiàn):隨著覆蓋半徑增加,所需部署節(jié)點的最少數(shù)量呈現(xiàn)較為明顯的下降趨勢。由于覆蓋半徑增加,擴大單節(jié)點的覆蓋范圍,從而降低網(wǎng)絡(luò)節(jié)點數(shù)量。

圖6 不同覆蓋半徑下,最少部署節(jié)點數(shù)量變化趨勢圖

假設(shè)每個節(jié)點的初始能量為10 J,對比本文采用的正方體覆蓋方法與傳統(tǒng)的感知覆蓋算法得到的節(jié)點部署方案。定義網(wǎng)絡(luò)中節(jié)點能量最低的節(jié)點為瓶頸節(jié)點,瓶頸節(jié)點能量隨傳播輪數(shù)的變化趨勢如圖7所示。

圖7 網(wǎng)絡(luò)中瓶頸節(jié)點能量變化趨勢圖

從圖7可以發(fā)現(xiàn),相較于傳統(tǒng)的感知覆蓋部署方案,本文提出的部署方案可以降低網(wǎng)絡(luò)瓶頸節(jié)點能耗,從而提高網(wǎng)絡(luò)生存時間。

5 結(jié)束語

本文從UWSN節(jié)點數(shù)量最小化角度出發(fā),同時考慮網(wǎng)絡(luò)連通性與覆蓋性兩項指標(biāo)建立優(yōu)化模型,提出了一種基于遺傳算法的節(jié)點優(yōu)化部署方案。相比與傳統(tǒng)覆蓋算法,本文算法能夠有效地降低覆蓋空洞,提高網(wǎng)絡(luò)覆蓋率,提高網(wǎng)絡(luò)生存時間。