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

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

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

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

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

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

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

1 節(jié)點(diǎn)模型

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

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

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

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

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

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

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

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

2 連通性指標(biāo)

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

txyz·opq=

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

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

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

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

3 覆蓋率指標(biāo)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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