一種基于改進蟻群算法的三維K-柵欄覆蓋算法

黨小超,李月霞,郝占軍,張 彤

(1.西北師范大學(xué) 計算機科學(xué)與工程學(xué)院,蘭州 730070; 2.甘肅省物聯(lián)網(wǎng)工程研究中心,蘭州 730070)

0 概述

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)中的柵欄覆蓋(Barrier Coverage，BC)問題是該領(lǐng)域的研究熱點。柵欄覆蓋問題是指在特定區(qū)(一般為狹長的帶狀區(qū)域)的邊界部署若干個傳感器節(jié)點構(gòu)建的傳感器網(wǎng)絡(luò)，在入侵監(jiān)測方面,主要關(guān)注入侵目標(biāo)運動路徑的覆蓋情況,即考察入侵目標(biāo)穿越傳感器網(wǎng)絡(luò)時被監(jiān)測的情況[1]。目前關(guān)于柵欄覆蓋的研究工作多數(shù)基于理想環(huán)境下的二維平面,而現(xiàn)實應(yīng)用場景,比如森林防護方面的火勢蔓延的動態(tài)監(jiān)測、水域中對外來物種侵入的監(jiān)測、化工業(yè)方面對污染物擴散程度的監(jiān)測等,都涉及到復(fù)雜地形的三維環(huán)境,因此,在三維環(huán)境下構(gòu)建柵欄覆蓋具有重要的意義。

目前,柵欄覆蓋的研究主要針對構(gòu)建柵欄、修補柵欄間隙以及在柵欄覆蓋中提高節(jié)點利用率和降低能耗3個方面。

關(guān)于構(gòu)建柵欄覆蓋的相關(guān)研究較多。文獻[2]通過移動最少數(shù)量的傳感器,并以最小的能量成本構(gòu)建K-柵欄覆蓋。文獻[3]利用匈牙利算法移動節(jié)點完成弱柵欄的構(gòu)建,并對水面柵欄覆蓋進行研究,但是弱柵欄容易造成監(jiān)測事件的丟失。文獻[4]利用具有轉(zhuǎn)動能力的移動傳感器節(jié)點構(gòu)建強柵欄,但有向傳感器節(jié)點檢測范圍有限,不適合全方位監(jiān)測事件。文獻[5]通過構(gòu)建有向柵欄圖對目標(biāo)柵欄區(qū)域進行強柵欄的構(gòu)建。文獻[6]針對具有有限移動能力的傳感器節(jié)點構(gòu)建K-柵欄覆蓋問題進行了相應(yīng)研究。文獻[7]利用移動節(jié)點對已存在的柵欄間隙進行填補,提出基于節(jié)點重部署的三維柵欄構(gòu)建算法。文獻[8]提出一種分布式算法,通過分區(qū)技術(shù)在不規(guī)則形狀的長條區(qū)域中構(gòu)建柵欄。文獻[9]提出針對WSN中存在位置誤差時的柵欄覆蓋構(gòu)建方法。

在傳感器最初隨機部署以及節(jié)點工作一段時間后,可能會出現(xiàn)柵欄間隙,這將導(dǎo)致重要事件數(shù)據(jù)的漏失。為了避免這種情況的發(fā)生,有必要進行柵欄間隙的修補。文獻[10]研究了有向傳感器網(wǎng)絡(luò)的間隙問題,通過確定性部署提出了SRA和CRA 2種間隙修復(fù)算法。文獻[11]提出一種協(xié)調(diào)傳感器巡邏算法CSP,通過移動節(jié)點監(jiān)視網(wǎng)絡(luò)中的各個節(jié)點以發(fā)現(xiàn)柵欄間隙,從而實現(xiàn)存在柵欄間隙時的最優(yōu)修補。文獻[12]提出一種覆蓋間隙修復(fù)算法CGR,通過檢測網(wǎng)絡(luò)中的低能量節(jié)點,移動該節(jié)點周圍的可移動節(jié)點進行柵欄修復(fù)。文獻[13]通過移動動態(tài)傳感器節(jié)點來填補柵欄間隙,并與已部署靜態(tài)無線傳感器節(jié)點形成強柵欄,從而有效地實現(xiàn)混合WSN中的柵欄覆蓋,但所提算法的節(jié)點移動能耗并未明顯降低。

柵欄覆蓋構(gòu)建算法的性能和柵欄間隙修補的質(zhì)量可以從節(jié)點使用數(shù)量和總能耗兩方面進行評價。文獻[14]通過引入多喚醒的調(diào)度機制對節(jié)點進行喚醒來降低能耗,進而實現(xiàn)無線傳感器網(wǎng)絡(luò)覆蓋性能的優(yōu)化。文獻[4]研究了移動傳感器能量消耗與節(jié)點感知半徑的關(guān)系。文獻[15]提出隨機化部署節(jié)點的非線性柵欄,通過減少可移動節(jié)點的移動距離,降低整個網(wǎng)絡(luò)的能量消耗。文獻[16]提出一種冗余傳感器睡眠調(diào)度的分布式協(xié)議,該協(xié)議無需事先知道節(jié)點的物理位置信息,可以減少移動傳感器數(shù)量。文獻[17]通過仿生智能算法布谷鳥搜索進行網(wǎng)絡(luò)覆蓋方面的優(yōu)化。文獻[18]提出當(dāng)部署的傳感器節(jié)點密度較大時,在原有節(jié)點連通部分的基礎(chǔ)上,用貪婪算法和最優(yōu)匹配算法完成對柵欄間隙的填補,減少使用節(jié)點數(shù)量,進而實施柵欄的再優(yōu)化。然而,上述文獻研究的是在二維理想環(huán)境下的柵欄覆蓋,并不適用于復(fù)雜的三維環(huán)境。文獻[19]將三維平面二維化,利用貪婪算法對目標(biāo)區(qū)域進行覆蓋,但該研究是針對區(qū)域覆蓋方面的研究,并不適用三維環(huán)境下的入侵監(jiān)測研究。文獻[20]通過隨機部署節(jié)點,利用差分進化算法對其進行優(yōu)化,實現(xiàn)對監(jiān)測區(qū)域的覆蓋,但該方法是對三維區(qū)域進行覆蓋,并不能實現(xiàn)柵欄覆蓋相對應(yīng)的入侵監(jiān)測。

為更好地實現(xiàn)對實際三維環(huán)境下的入侵監(jiān)測,本文提出一種三維蟻群優(yōu)化(Three Dimensional Ant Colony Optimization,3D-ACO)算法,用以構(gòu)建三維柵欄覆蓋。將三維區(qū)域二維網(wǎng)格化,計算網(wǎng)格梯度并引入空間權(quán)重和部署方向角,采用3D-ACO算法構(gòu)建柵欄,利用移動節(jié)點進行柵欄間隙填補,進而提高節(jié)點的利用率并降低網(wǎng)絡(luò)能耗。本文使用混合無線傳感器網(wǎng)絡(luò),并且所用的傳感器均為全向感知傳感器。

1 全向強柵欄覆蓋模型

1.1 節(jié)點感知模型

本文所用的傳感器節(jié)點感知模型為全向感知模型,如圖1所示。圖1(a)為節(jié)點p在三維環(huán)境下的感知模型,以三元數(shù)組表示,其中傳感器節(jié)點的位置坐標(biāo)用pi(xi,yi,zi)表示,r為節(jié)點的感知半徑,θ為節(jié)點的部署方向角,q為入侵對象,q在p節(jié)點感知范圍內(nèi)。圖1(b)為節(jié)點在二維下的感知模型。

圖1 全向感知模型

受物理地貌因素影響,三維環(huán)境相對較為復(fù)雜,存在比較陡峭的坡峰,隨機部署會造成一定數(shù)量節(jié)點的浪費,致使節(jié)點利用率不高。蟻群算法在復(fù)雜路線中能夠?qū)ふ易顑?yōu)路徑,但傳統(tǒng)的蟻群算法不適用于在三維環(huán)境下構(gòu)建柵欄覆蓋,且存在容易陷入局部最優(yōu)解的問題。本文在待部署區(qū)域D中隨機拋撒節(jié)點,將部署區(qū)域進行網(wǎng)格劃分并引入網(wǎng)格梯度,通過空間權(quán)重和部署方向角來改進傳統(tǒng)的蟻群算法,從而減少部署節(jié)點數(shù)量,并降低其部署難度。本文假設(shè)WSN中傳感器節(jié)點為同構(gòu)節(jié)點,即所有節(jié)點的移動能耗、感知半徑、感知范圍均相同。在對全向無線傳感器網(wǎng)絡(luò)強1-柵欄構(gòu)建問題分析之前做出如下定義:

定義2(節(jié)點感知范圍) 節(jié)點的感知模型為概率感知模型,即節(jié)點感知入侵者的概率隨著入侵者和節(jié)點之間的距離增加而減小,如圖1(b)中節(jié)點感知范圍內(nèi)任意一點q,節(jié)點p能感知到點q的概率Pq為:

其中,c為常數(shù)。

定義3(節(jié)點運動能耗) 節(jié)點的移動距離和單位移動能耗的乘積。

定義4(環(huán)形強柵欄覆蓋) 如果監(jiān)測區(qū)域是理想的平坦地面,則構(gòu)建的柵欄近似于直線,如圖2(a)所示。當(dāng)監(jiān)測區(qū)域為三維環(huán)境,且存在陡峭坡峰(圖2(b)中陰影部分)時,構(gòu)建的柵欄如圖2(b)所示,稱為環(huán)形強柵欄。平坦地面上的K-柵欄構(gòu)建是三維環(huán)境下環(huán)形K-柵欄構(gòu)建的一種特殊情形。

圖2 強1-柵欄覆蓋示意圖

1.2 網(wǎng)格梯度劃分模型

假設(shè)需要部署柵欄覆蓋的三維復(fù)雜環(huán)境是長為L、寬為W的丘陵地帶,受地物地貌因素影響,若存在較陡峭的坡峰,隨機部署會造成節(jié)點浪費。針對上述問題,本文通過網(wǎng)格梯度來限制螞蟻走向。網(wǎng)格梯度用來表示映射在二維平面方格上三維環(huán)境的陡峭程度。該方法對部署節(jié)點不再是強行部署,而是采用劃分網(wǎng)格,并計算其梯度大小來選擇部署路徑的走向。在混合WSN中構(gòu)建強1-柵欄時,本文將部署區(qū)域劃分成若干個網(wǎng)格,不同網(wǎng)格的三維高度存在差別,使用沿坡面上任一方向上高度變化的程度表示網(wǎng)格梯度,其中一個網(wǎng)格的坡度與方向梯度如圖3所示。

圖3 坡度與方向梯度示意圖

本文定義φ為沿ψ方向的方向梯度角,陰影部分為傳感器節(jié)點p的感知范圍,h表示坡面的垂直高度,l表示水平距離,兩者之比為坡度,用i表示。?為坡面與水平面的夾角。

(1)

傳感器節(jié)點p所在網(wǎng)格坡面沿ψ方向的網(wǎng)格方向梯度g為:

(2)

其中,h(x,y)為坐標(biāo)(x,y)處的高程,ψ表示與坡向的夾角。當(dāng)ψ=0時,梯度和坡度相等。

計算出劃分后的每個網(wǎng)格的網(wǎng)格梯度,放入網(wǎng)格梯度集合G中,據(jù)此引入空間權(quán)重。

如圖4所示,地形高低由顏色從淺到深表示,白色節(jié)點為不可移動的靜態(tài)節(jié)點,黑色節(jié)點為可移動的動態(tài)節(jié)點。假設(shè)已經(jīng)獲知節(jié)點pi位置坐標(biāo)為(xi,yi,zi),隨機拋撒節(jié)點,執(zhí)行3D-ACO進行柵欄覆蓋的構(gòu)建,如圖4(a)所示。之后通過移動節(jié)點填補柵欄間隙,如圖4(b)中箭頭所示,方格表示螞蟻在構(gòu)建柵欄時,柵欄間隙處的待填補節(jié)點位置。改進的蟻群算法在構(gòu)建柵欄的過程中根據(jù)已經(jīng)加入的空間權(quán)重和部署方向角選擇下一跳傳感器節(jié)點。當(dāng)部署區(qū)域內(nèi)不存在滿足條件的節(jié)點時,算法會尋找最優(yōu)的網(wǎng)格作為待填補虛擬節(jié)點位置,該位置將被標(biāo)記,下一條柵欄構(gòu)建不會重復(fù)選取該網(wǎng)格作為部署路徑。

圖4 柵欄構(gòu)建示意圖

2 3D-ACO算法

傳統(tǒng)的蟻群算法通過螞蟻個體間信息的傳遞,多個螞蟻共同協(xié)作,從而尋找蟻穴到食物的最短路徑。本文提出一種適用于三維環(huán)境下的蟻群算法3D-ACO,通過引入空間權(quán)重和部署方向角度,限制螞蟻的活動方向,使其適用于三維環(huán)境下的柵欄構(gòu)建。將三維待部署區(qū)域二維網(wǎng)格化,計算出各個網(wǎng)格梯度,根據(jù)網(wǎng)格梯度大小由小到大排序,從當(dāng)前節(jié)點遍歷所有節(jié)點,隨后隨機拋撒m個節(jié)點,執(zhí)行3D-ACO算法。考慮到構(gòu)建柵欄為強柵欄和節(jié)點的感知范圍可能受環(huán)境影響,節(jié)點的真實半徑有所不同,所以,該算法限制螞蟻的移動能力,并在無合適節(jié)點的位置留下虛擬節(jié)點位置,再通過移動節(jié)點填補柵欄間隙,以確保構(gòu)建強柵欄。3D-ACO算法框架如圖5所示。

圖5 3D-ACO 算法框架

2.1 螞蟻移動能力的限制

為了構(gòu)建三維環(huán)境下的強柵欄覆蓋,需要對螞蟻的移動能力進行一定程度上的限制。這是因為WSN的強柵欄覆蓋為防止不丟失事件監(jiān)測,要求相鄰節(jié)點間無間隙存在,即2個節(jié)點感知范圍內(nèi)一定存在重疊部分。若節(jié)點A和節(jié)點B為構(gòu)建的柵欄覆蓋中兩相鄰節(jié)點,則d(A,B)<2r。又因本文部署環(huán)境是三維山丘陵,所以傳感器部署后的理想感知范圍與實際感知到的范圍定會存在差距。已知理想探測半徑r,設(shè)Rr為節(jié)點實際感知半徑,為保證3D-ACO算法構(gòu)建的是強柵欄,則有以下定義:

定義5螞蟻移動距離小于等于2Rr。Rr=rcos[arctan(icosψ)]。

假設(shè)傳感器節(jié)點所在網(wǎng)格范圍可近似看作坡度和坡向近似相同的理想坡面,如圖3所示,g表示沿ψ方向上的網(wǎng)格梯度,計算公式為:

g=tanφ

(3)

由式(1)和式(3)可知:

g=icosψ

(4)

由于地形影響,Rr和r在ψ方向的存在以下關(guān)系:

Rr=rcosφ

(5)

將式(3)、式(4)代入式(5),得:

Rr=rcos(arctang)=rcos[arctan(icosψ)]

(6)

當(dāng)ψ=0時,φ=?,則Rr=rcos ?,即:

Rr=rcos[arctan(icosψ)]

(7)

為構(gòu)建強柵欄,相鄰節(jié)點感知范圍一定存在重疊部分。為了保證所構(gòu)建柵欄為強柵欄,本文限制螞蟻的移動能力為2Rr,當(dāng)沒有合適節(jié)點時,則選定相應(yīng)填補節(jié)點位置,繼續(xù)選擇下一跳節(jié)點。

2.2 啟發(fā)因子優(yōu)化

本文通過引入空間權(quán)重和選擇方向角來改進蟻群算法。在監(jiān)測區(qū)域內(nèi)隨機拋撒傳感器節(jié)點,螞蟻首先從左邊界開始出發(fā)尋找最優(yōu)路徑,通過選擇方向角和空間權(quán)重來優(yōu)化螞蟻尋找路徑。下面給出空間權(quán)重和部署方向角的相關(guān)定義,以及優(yōu)化函數(shù)的詳細介紹。

定義6(空間權(quán)重) 以起始節(jié)點為水平面,給待選擇路徑上的網(wǎng)格賦予不同的權(quán)值,稱為空間權(quán)重。

定義7(部署方向角) 在部署區(qū)域D的二維平面內(nèi),當(dāng)前節(jié)點與下一步要選擇的節(jié)點之間的連線和水平方向的夾角。

下面給出空間權(quán)重和部署方向角的優(yōu)化步驟。

1)空間權(quán)重

本文利用網(wǎng)格方向梯度引入的空間權(quán)重來作為蟻群算法的另外一個啟發(fā)信息。將集合G中各個網(wǎng)格上的節(jié)點求出權(quán)重,空間權(quán)重用κij表示,螞蟻選擇下一路徑時的選擇概率將會受到空間權(quán)重的影響,即空間權(quán)重值κij越大,狀態(tài)轉(zhuǎn)移概率就越小。

(8)

其中,gmax表示最大梯度值,即梯度閾值。當(dāng)節(jié)點所在網(wǎng)格梯度比梯度閾值大時,則重新選擇節(jié)點。如圖6所示,節(jié)點A與節(jié)點B的坡度夾角為為?1,節(jié)點A和節(jié)點C的坡度夾角為?2,節(jié)點A和節(jié)點C的網(wǎng)格梯度分別為g1和g2。當(dāng)gmax>g1>g2時,κ1>κ2。將空間權(quán)重轉(zhuǎn)化為啟發(fā)因子以改進傳統(tǒng)蟻群算法,對于螞蟻選擇路徑而言,空間權(quán)重越大,則該條路徑的選擇概率也相應(yīng)地變大,即當(dāng)從節(jié)點A選擇下一步路徑時將選擇坡度較平緩的節(jié)點B作為下一步選擇。

圖6 基于空間權(quán)重的節(jié)點選擇

2)部署方向角

引入空間權(quán)重啟發(fā)因子是為了使ACO算法適用于三維環(huán)境下構(gòu)建柵欄。由于螞蟻選擇路徑時所依賴的只有當(dāng)前節(jié)點的pi選擇下一節(jié)點pj的期望程度和路徑的信息量強度,但這可能使得算法陷入局部最優(yōu)解,因此本文引入傳感器節(jié)點的選擇方向角作為蟻群算法的另外一個啟發(fā)信息。當(dāng)θ越小時,θij越大,狀態(tài)轉(zhuǎn)移概率也越大。

(9)

如圖7所示,0≤θ≤π表示節(jié)點的部署方向。當(dāng)θ=0且所選下一跳節(jié)點所在網(wǎng)格的豎直方向梯度均相同時,節(jié)點部署方向為水平方向是最佳的下一跳節(jié)點位置。節(jié)點A與節(jié)點B在二維環(huán)境下的夾角為θ2,節(jié)點A和節(jié)點C在二維環(huán)境下的夾角為θ1,由式(9)可知,當(dāng)節(jié)點A選擇下一步路徑時將選擇節(jié)點B作為下一步選擇。

圖7 基于部署方向角的節(jié)點選擇

根據(jù)式(8)和式(9),狀態(tài)轉(zhuǎn)移概率做如下更改:

(10)

式(10)代表在t時刻螞蟻k由城市i轉(zhuǎn)移到節(jié)點j的轉(zhuǎn)移概率。

2.3 間隙填補

在有向節(jié)點模型中,節(jié)點不僅需要移動,還有可能需要轉(zhuǎn)動,因此,節(jié)點的能量消耗由轉(zhuǎn)動和移動能量消耗組成。在本文中,節(jié)點采用全向感知模型,所消耗能量僅為移動節(jié)點的消耗。如圖8所示,在節(jié)點移動至待填補位置的過程中,希望總能耗最小,故而選擇與待填補位置的距離最小的節(jié)點進行移動。

圖8 柵欄間隙填補示意圖

由節(jié)點位置以及待填補位置的坐標(biāo)和網(wǎng)格梯度,可以求得移動節(jié)點的移動距離。對于所有的傳感器節(jié)點,可以根據(jù)距離目標(biāo)位置的遠近選擇節(jié)點進行移動填補。關(guān)于能耗部分將在實驗仿真進行詳細分析。

2.4 柵欄構(gòu)建過程

在傳統(tǒng)蟻群算法中,螞蟻選擇下一節(jié)點僅依賴τij和ηij2個因素,這可能會使節(jié)點陷入局部最優(yōu)解。因此,本文引入節(jié)點的空間權(quán)重和部署方向角來限制信息素濃度和選擇下一跳節(jié)點路徑的期望程度對螞蟻選擇概率的影響,并利用移動節(jié)點填補柵欄間隙確保構(gòu)建強柵欄。隨機拋撒節(jié)點之后,劃分網(wǎng)格,不同的節(jié)點所在位置高低不同,即空間權(quán)重不同,螞蟻從左邊界開始尋找最優(yōu)路徑,當(dāng)遇到不同的路徑時,通過改進的蟻群算法選擇最優(yōu)路徑。當(dāng)沒有可選擇節(jié)點時,記錄待填補間隙位置,之后進行移動填補。假設(shè)螞蟻從頭出發(fā),根據(jù)優(yōu)化后的信息尋找最優(yōu)路徑,以構(gòu)建強柵欄,具體步驟如下:

步驟1在待部署區(qū)域D中隨機拋撒n個節(jié)點,劃分網(wǎng)格,并記錄節(jié)點位置和所在網(wǎng)格。

步驟2計算節(jié)點所在網(wǎng)格的網(wǎng)格梯度將其作為節(jié)點的空間權(quán)重κij,計算節(jié)點間的夾角引入部署方向角θij。

步驟3將上述2個因子加入蟻群算法,執(zhí)行3D-ACO算法,開始遍歷傳感器節(jié)點。

步驟4遍歷所有節(jié)點,更新信息素,并記錄間隙位置。

步驟5算法迭代,輸出節(jié)點使用數(shù)量最少的柵欄以及各節(jié)點位置。

步驟6判斷節(jié)點間距離d<2Rr,若是,繼續(xù)遍歷下一節(jié)點;否則,執(zhí)行步驟7。

步驟7選擇距離間隙最短移動距離的節(jié)點,進行節(jié)點填補。若未到達終點,執(zhí)行步驟6;若到達終點邊界,結(jié)束柵欄構(gòu)建。

2.5 3D-ACO算法性能分析

1)能耗分析

本文構(gòu)建柵欄所用節(jié)點需要消耗能量主要分為:節(jié)點發(fā)射信息的能量消耗es,接收信息后處理信息的能量消耗eb,節(jié)點發(fā)射信息到節(jié)點接收信息之間的能量消耗el,移動節(jié)點所需要的能耗Jt,其中,el和Jt主要由節(jié)點間距離決定。全部能量消耗計算公式為:

Et=es+eb+el+Jt

(11)

傳統(tǒng)蟻群算法、本文3D-ACO算法的總能耗分別用式(12)和式(13)表示。

(12)

(13)

同理,當(dāng)節(jié)點與之前節(jié)點高度差不同(空間權(quán)重κij不同),其他條件相同時,在螞蟻選擇下一跳節(jié)點趨于直線的概率方面,兩算法相比有:

因此,本文算法所構(gòu)建更趨向直線且平緩的柵欄覆蓋,也即兩蟻群算法中選擇下一跳節(jié)點總距離有:

∑d1ij>∑dij

用式(12)減去式(13)得到:

EACO-E3D-ACO=(N1-N)es+(Q1-Q)eb+

(14)

在節(jié)點發(fā)射信息方面,傳統(tǒng)的蟻群算法與3D-ACO算法都是由節(jié)點自身廣播信息,所以,3D-ACO算法相較于傳統(tǒng)的蟻群算法并未增加能耗。同理,節(jié)點接收信息并處理信息時也未增加能耗,故可以忽略這兩部分能耗?，F(xiàn)在只考慮節(jié)點移動能耗,以及節(jié)點發(fā)射信息到節(jié)點接收信息之間的能量消耗el,而這兩部分能耗主要與節(jié)點移動距離有關(guān)系。由于傳統(tǒng)的蟻群算法中∑d1ij要大于3D-ACO算法中的∑dij,因此式(14)大于0。所以,3D-ACO算法要比傳統(tǒng)蟻群算法能耗低。

2)收斂速度和局部最優(yōu)問題

傳統(tǒng)的蟻群算法前期由于信息匱乏,收斂速度較慢,而且其選擇下一跳節(jié)點時傾向于選擇距離最近的節(jié)點,容易陷入局部最優(yōu)解。本文算法通過網(wǎng)格劃分,引入空間權(quán)重和部署方向角,提前排除不適用下一跳節(jié)點選擇的節(jié)點,以減少迭代次數(shù),提高收斂速度,并且結(jié)合空間權(quán)重和部署方向角選擇更適合構(gòu)建柵欄覆蓋的下一跳節(jié)點,避免陷入局部最優(yōu)問題。因此,在三維環(huán)境下,本文3D-ACO算法性能更優(yōu)。

3 仿真實驗

本文仿真實驗部署區(qū)域為300 m×200 m的矩形區(qū)域。隨機拋撒傳感器節(jié)點數(shù)量n,傳感器節(jié)點感知范圍均為球體,且節(jié)點具備移動能力,本文對監(jiān)測區(qū)域進行強2-柵欄構(gòu)建的仿真實驗。若無特別說明,實驗參數(shù)值均以表1所示參數(shù)為準(zhǔn),仿真實驗結(jié)果均取100次隨機實驗平均值,迭代次數(shù)定為300。

表1 實驗參數(shù)

本文從節(jié)點的自身因素出發(fā)根據(jù)節(jié)點感知半徑的不同進行比較,此外,選取strong optimal和strong greedy 2種算法進行仿真實驗比較,并參考其實驗數(shù)據(jù)。在下文實驗中,節(jié)點數(shù)量為原拋撒節(jié)點數(shù)量,所用節(jié)點數(shù)量是構(gòu)成柵欄的節(jié)點數(shù)量,節(jié)點總能耗為全部節(jié)點消耗能量,節(jié)點平均能耗為總能耗與所有節(jié)點數(shù)量的比值。

3.1 感知半徑對結(jié)果的影響

傳感器節(jié)點的感知范圍隨著其感知半徑變化而變化,本文選取了不同感知半徑的傳感器節(jié)點進行仿真實驗,并對引入空間權(quán)重和部署方向角的3D-ACO算法進行性能分析,結(jié)果如圖9～圖11所示。

圖9 節(jié)點感知半徑對節(jié)點總能耗的影響

圖10 節(jié)點感知半徑對節(jié)點平均能耗的影響

圖11 節(jié)點感知半徑對所用節(jié)點數(shù)量的影響

從圖9可以看出,節(jié)點總的能量消耗隨著節(jié)點感知半徑的增加而減小。這是由于隨著節(jié)點感知半徑的增加,節(jié)點相應(yīng)的感知范圍也增加,移動節(jié)點移動距離相應(yīng)減少,進而使得傳感器節(jié)點總能耗降低。

從圖10可以看出,隨著傳感器節(jié)點感知半徑的增加,傳感器節(jié)點平均能耗逐漸降低,隨后趨于平緩。這是因為總能耗降低,而總節(jié)點數(shù)量不變,進而使得節(jié)點的平均消耗能量降低。

從圖11可以看出,隨著傳感器節(jié)點感知半徑的增加,傳感器節(jié)點使用的數(shù)量降低。這是因為傳感器節(jié)點半徑的逐漸增大,縮小了節(jié)點之間的部署方向角,此外,由于空間權(quán)重優(yōu)化因子的優(yōu)化,柵欄構(gòu)建更為平緩的柵欄覆蓋,構(gòu)建柵欄使用節(jié)點個數(shù)減少。

3.2 節(jié)點數(shù)量對結(jié)果的影響

在保證強柵欄可以構(gòu)建的前提下,盡可能地減少節(jié)點的使用數(shù)量以對比相關(guān)算法的優(yōu)劣。strong optimal和strong greedy算法對于節(jié)點數(shù)量有一定的要求,因此本文實驗節(jié)點數(shù)從100開始,以20為梯度值增加,直至200。節(jié)點總能耗、平均能耗以及構(gòu)建柵欄節(jié)點使用數(shù)量的結(jié)果如圖12～圖14所示。

圖12 節(jié)點數(shù)量對節(jié)點總能耗的影響

圖13 節(jié)點數(shù)量對節(jié)點平均能耗的影響

圖14 節(jié)點數(shù)量對形成柵欄所需節(jié)點個數(shù)的影響

從圖12和圖13可以發(fā)現(xiàn),3種算法的總能耗與傳感器節(jié)點的平均能耗均隨著拋撒節(jié)點數(shù)量的增加而明顯減少,在同樣的節(jié)點數(shù)量情況下,3D-ACO算法的總能耗和節(jié)點平均能耗則明顯地低于其他2種算法。這是因為隨著部署區(qū)域內(nèi)傳感器節(jié)點密度變大,節(jié)點空間距離縮小,所以構(gòu)建柵欄時節(jié)點移動距離減少,故而使得總能耗降低。隨著總能耗的降低,而節(jié)點數(shù)量增加,平均能耗也降低。從圖14可以看出,在構(gòu)建柵欄過程中,3種算法使用傳感器的數(shù)量隨拋撒節(jié)點的增加而變多,最終趨于平緩。這是因為隨著節(jié)點數(shù)量的增多,算法會選擇更加平緩的路徑,但隨著迭代次數(shù)的增加,最優(yōu)的路徑將會被確定。同時還可以看出,3D-ACO算法使用節(jié)點數(shù)量明顯低于其他2種算法的節(jié)點數(shù)量,且增加趨勢更為平緩。這是因為3D-ACO算法通過空間權(quán)重和部署方向角對螞蟻尋找節(jié)點的限制,所以在構(gòu)建柵欄覆蓋時,更傾向于選擇空間距離小、署方向角度小的柵欄覆蓋路徑。

3.3 柵欄數(shù)量對結(jié)果的影響

本文在同一部署區(qū)域的不同柵欄數(shù)量K的情況下,對節(jié)點總能耗、平均能耗、需求的總節(jié)點數(shù)進行比較,結(jié)果分別如圖15～圖17所示。

圖15 柵欄數(shù)量對節(jié)點總能耗的影響

圖16 柵欄數(shù)量對節(jié)點平均能耗的影響

圖17 柵欄數(shù)量對形成柵欄所需節(jié)點個數(shù)的影響

從圖15和圖16可以看出,隨著構(gòu)建柵欄數(shù)的增加,所需傳感器節(jié)點變多,因此移動節(jié)點消耗總能耗變大,其平均能耗也在增長。但3D-ACO算法的總能耗和平均能耗相較于其他2種算法越來越小。

從圖17可以看出,在構(gòu)建相同數(shù)量的柵欄情況下,3D-ACO算法所需的節(jié)點數(shù)遠低于其他2種算法,例如當(dāng)柵欄數(shù)K=6時,3D-ACO算法僅需要90個節(jié)點左右,其他2種算法則需要120個節(jié)點左右。這是因為3D-ACO算法柵欄的構(gòu)建存在柵欄重疊的可能,這種情況在第2節(jié)中就已經(jīng)介紹。所以柵欄覆蓋構(gòu)建過程中隨著柵欄條數(shù)的增多,柵欄交叉的幾率增大,節(jié)點使用數(shù)量減少。

4 結(jié)束語

本文提出一種基于改進蟻群算法的三維K-柵欄覆蓋算法。引入空間權(quán)重改進蟻群算法使其適用于三維柵欄構(gòu)建,利用部署方向角防止蟻群算法陷入局部最優(yōu),同時通過限制蟻群的移動能力以及移動節(jié)點填補柵欄間隙以確保強柵欄的形成。仿真實驗結(jié)果表明,3D-ACO算法在三維環(huán)境下部署柵欄時,可有效提高節(jié)點使用率,并且所構(gòu)建的柵欄具有較強的自適應(yīng)性。由于本文算法基于全向感知節(jié)點,下一步將針對在三維環(huán)境中有向無線傳感器網(wǎng)絡(luò)的柵欄覆蓋問題進行研究。