基于遺傳算法的水下傳感器網絡節點部署算法研究*

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

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

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

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

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

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

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

1 節點模型

通常,UWSN由基站節點與普通傳感器節點兩種類型的節點構成[12]。其中,基站節點(Sink)負責接收來自普通傳感器節點傳來的監測海域的數據信息;普通傳感器節點負責采集覆蓋海域內的信息并將其以多跳傳輸的形式傳送到Sink節點。為方便討論問題,假設UWSN每個傳感器節點具有固定的覆蓋半徑Rc和傳輸半徑Rn,其結構如圖2和圖3所示。通常,Sink節點的傳輸半徑要遠大于普通節點的傳輸半徑。

圖2 水下傳感器網絡結構示意圖

圖3 節點通信半徑與覆蓋半徑說明示意圖

每一個普通傳感器節點都可以采集覆蓋半徑內的數據信息,并將采集獲得的數據信息轉發給距離其傳輸半徑內的其他節點。

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

因此,最優節點部署問題可以歸結為求解最優決策矩陣G。

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

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

2 連通性指標

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

txyz·opq=

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

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

由于UWSN中所有的傳感器節點都能夠將采集的信息傳輸到基站Sink,應該符合如下約束條件:

上式表明與Sink節點連通的傳感器節點數量等于UWSN網絡部署的節點總數。此約束條件可確保網絡中的每個節點都可以將信息傳輸至Sink。

3 覆蓋率指標

為了改善“覆蓋空洞”問題,本文將網絡覆蓋問題轉化為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}}。因此,每一個正方體都可以用一個頂點集合唯一標識,如Sijh。

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

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

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

因此,以部署傳感器節點數量最小化,要求網絡覆蓋率達到α以上,優化模型可以表達如下:

4 算法設計與數值仿真

Step1設定網絡初始參數,如網絡區域范圍、Sink節點位置、離散化格點邊長、初始種群數量、迭代最大代數、GA算法交叉概率、GA算法變異概率等基本參數。

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

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

Step4檢查是否到達最大代數或者滿足算法結束條件。如果滿足結束條件,則輸出網絡最少節點數量Mopt。如果不滿足結束條件,則跳轉至Step 2。

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

首先,討論針對不同的網絡覆蓋率要求,在不同的覆蓋半徑下,網絡最優解點數量算法收斂如圖4、圖5所示。

圖4 網絡覆蓋率90%下,遺傳算法收斂圖

圖5 網絡覆蓋率100%要求下,遺傳算法收斂圖

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

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

從圖6可以發現:隨著覆蓋半徑增加,所需部署節點的最少數量呈現較為明顯的下降趨勢。由于覆蓋半徑增加,擴大單節點的覆蓋范圍,從而降低網絡節點數量。

圖6 不同覆蓋半徑下,最少部署節點數量變化趨勢圖

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

圖7 網絡中瓶頸節點能量變化趨勢圖

從圖7可以發現,相較于傳統的感知覆蓋部署方案,本文提出的部署方案可以降低網絡瓶頸節點能耗,從而提高網絡生存時間。

5 結束語

本文從UWSN節點數量最小化角度出發,同時考慮網絡連通性與覆蓋性兩項指標建立優化模型,提出了一種基于遺傳算法的節點優化部署方案。相比與傳統覆蓋算法,本文算法能夠有效地降低覆蓋空洞,提高網絡覆蓋率,提高網絡生存時間。