一種基于改進蟻群算法的三維K-柵欄覆蓋算法
2020-02-19 11:26:56黨小超李月霞郝占軍
計算機工程 2020年2期
黨小超,李月霞,郝占軍,張 彤
(1.西北師范大學 計算機科學與工程學院,蘭州 730070; 2.甘肅省物聯網工程研究中心,蘭州 730070)
0 概述
無線傳感器網絡(Wireless Sensor Network，WSN)中的柵欄覆蓋(Barrier Coverage，BC)問題是該領域的研究熱點。柵欄覆蓋問題是指在特定區(一般為狹長的帶狀區域)的邊界部署若干個傳感器節點構建的傳感器網絡，在入侵監測方面,主要關注入侵目標運動路徑的覆蓋情況,即考察入侵目標穿越傳感器網絡時被監測的情況[1]。目前關于柵欄覆蓋的研究工作多數基于理想環境下的二維平面,而現實應用場景,比如森林防護方面的火勢蔓延的動態監測、水域中對外來物種侵入的監測、化工業方面對污染物擴散程度的監測等,都涉及到復雜地形的三維環境,因此,在三維環境下構建柵欄覆蓋具有重要的意義。
目前,柵欄覆蓋的研究主要針對構建柵欄、修補柵欄間隙以及在柵欄覆蓋中提高節點利用率和降低能耗3個方面。
關于構建柵欄覆蓋的相關研究較多。文獻[2]通過移動最少數量的傳感器,并以最小的能量成本構建K-柵欄覆蓋。文獻[3]利用匈牙利算法移動節點完成弱柵欄的構建,并對水面柵欄覆蓋進行研究,但是弱柵欄容易造成監測事件的丟失。文獻[4]利用具有轉動能力的移動傳感器節點構建強柵欄,但有向傳感器節點檢測范圍有限,不適合全方位監測事件。文獻[5]通過構建有向柵欄圖對目標柵欄區域進行強柵欄的構建。文獻[6]針對具有有限移動能力的傳感器節點構建K-柵欄覆蓋問題進行了相應研究。文獻[7]利用移動節點對已存在的柵欄間隙進行填補,提出基于節點重部署的三維柵欄構建算法。文獻[8]提出一種分布式算法,通過分區技術在不規則形狀的長條區域中構建柵欄。文獻[9]提出針對WSN中存在位置誤差時的柵欄覆蓋構建方法。
在傳感器最初隨機部署以及節點工作一段時間后,可能會出現柵欄間隙,這將導致重要事件數據的漏失。為了避免這種情況的發生,有必要進行柵欄間隙的修補。文獻[10]研究了有向傳感器網絡的間隙問題,通過確定性部署提出了SRA和CRA 2種間隙修復算法。文獻[11]提出一種協調傳感器巡邏算法CSP,通過移動節點監視網絡中的各個節點以發現柵欄間隙,從而實現存在柵欄間隙時的最優修補。文獻[12]提出一種覆蓋間隙修復算法CGR,通過檢測網絡中的低能量節點,移動該節點周圍的可移動節點進行柵欄修復。文獻[13]通過移動動態傳感器節點來填補柵欄間隙,并與已部署靜態無線傳感器節點形成強柵欄,從而有效地實現混合WSN中的柵欄覆蓋,但所提算法的節點移動能耗并未明顯降低。
柵欄覆蓋構建算法的性能和柵欄間隙修補的質量可以從節點使用數量和總能耗兩方面進行評價。文獻[14]通過引入多喚醒的調度機制對節點進行喚醒來降低能耗,進而實現無線傳感器網絡覆蓋性能的優化。文獻[4]研究了移動傳感器能量消耗與節點感知半徑的關系。文獻[15]提出隨機化部署節點的非線性柵欄,通過減少可移動節點的移動距離,降低整個網絡的能量消耗。文獻[16]提出一種冗余傳感器睡眠調度的分布式協議,該協議無需事先知道節點的物理位置信息,可以減少移動傳感器數量。文獻[17]通過仿生智能算法布谷鳥搜索進行網絡覆蓋方面的優化。文獻[18]提出當部署的傳感器節點密度較大時,在原有節點連通部分的基礎上,用貪婪算法和最優匹配算法完成對柵欄間隙的填補,減少使用節點數量,進而實施柵欄的再優化。然而,上述文獻研究的是在二維理想環境下的柵欄覆蓋,并不適用于復雜的三維環境。文獻[19]將三維平面二維化,利用貪婪算法對目標區域進行覆蓋,但該研究是針對區域覆蓋方面的研究,并不適用三維環境下的入侵監測研究。文獻[20]通過隨機部署節點,利用差分進化算法對其進行優化,實現對監測區域的覆蓋,但該方法是對三維區域進行覆蓋,并不能實現柵欄覆蓋相對應的入侵監測。
為更好地實現對實際三維環境下的入侵監測,本文提出一種三維蟻群優化(Three Dimensional Ant Colony Optimization,3D-ACO)算法,用以構建三維柵欄覆蓋。將三維區域二維網格化,計算網格梯度并引入空間權重和部署方向角,采用3D-ACO算法構建柵欄,利用移動節點進行柵欄間隙填補,進而提高節點的利用率并降低網絡能耗。本文使用混合無線傳感器網絡,并且所用的傳感器均為全向感知傳感器。
1 全向強柵欄覆蓋模型
1.1 節點感知模型
本文所用的傳感器節點感知模型為全向感知模型,如圖1所示。圖1(a)為節點p在三維環境下的感知模型,以三元數組
圖1 全向感知模型
受物理地貌因素影響,三維環境相對較為復雜,存在比較陡峭的坡峰,隨機部署會造成一定數量節點的浪費,致使節點利用率不高。蟻群算法在復雜路線中能夠尋找最優路徑,但傳統的蟻群算法不適用于在三維環境下構建柵欄覆蓋,且存在容易陷入局部最優解的問題。本文在待部署區域D中隨機拋撒節點,將部署區域進行網格劃分并引入網格梯度,通過空間權重和部署方向角來改進傳統的蟻群算法,從而減少部署節點數量,并降低其部署難度。本文假設WSN中傳感器節點為同構節點,即所有節點的移動能耗、感知半徑、感知范圍均相同。在對全向無線傳感器網絡強1-柵欄構建問題分析之前做出如下定義:
定義2(節點感知范圍) 節點的感知模型為概率感知模型,即節點感知入侵者的概率隨著入侵者和節點之間的距離增加而減小,如圖1(b)中節點感知范圍內任意一點q,節點p能感知到點q的概率Pq為:
其中,c為常數。
定義3(節點運動能耗) 節點的移動距離和單位移動能耗的乘積。
定義4(環形強柵欄覆蓋) 如果監測區域是理想的平坦地面,則構建的柵欄近似于直線,如圖2(a)所示。當監測區域為三維環境,且存在陡峭坡峰(圖2(b)中陰影部分)時,構建的柵欄如圖2(b)所示,稱為環形強柵欄。平坦地面上的K-柵欄構建是三維環境下環形K-柵欄構建的一種特殊情形。
圖2 強1-柵欄覆蓋示意圖
1.2 網格梯度劃分模型
假設需要部署柵欄覆蓋的三維復雜環境是長為L、寬為W的丘陵地帶,受地物地貌因素影響,若存在較陡峭的坡峰,隨機部署會造成節點浪費。針對上述問題,本文通過網格梯度來限制螞蟻走向。網格梯度用來表示映射在二維平面方格上三維環境的陡峭程度。該方法對部署節點不再是強行部署,而是采用劃分網格,并計算其梯度大小來選擇部署路徑的走向。在混合WSN中構建強1-柵欄時,本文將部署區域劃分成若干個網格,不同網格的三維高度存在差別,使用沿坡面上任一方向上高度變化的程度表示網格梯度,其中一個網格的坡度與方向梯度如圖3所示。
圖3 坡度與方向梯度示意圖
本文定義φ為沿ψ方向的方向梯度角,陰影部分為傳感器節點p的感知范圍,h表示坡面的垂直高度,l表示水平距離,兩者之比為坡度,用i表示。?為坡面與水平面的夾角。
(1)
傳感器節點p所在網格坡面沿ψ方向的網格方向梯度g為:
(2)
其中,h(x,y)為坐標(x,y)處的高程,ψ表示與坡向的夾角。當ψ=0時,梯度和坡度相等。
計算出劃分后的每個網格的網格梯度,放入網格梯度集合G中,據此引入空間權重。
如圖4所示,地形高低由顏色從淺到深表示,白色節點為不可移動的靜態節點,黑色節點為可移動的動態節點。假設已經獲知節點pi位置坐標為(xi,yi,zi),隨機拋撒節點,執行3D-ACO進行柵欄覆蓋的構建,如圖4(a)所示。之后通過移動節點填補柵欄間隙,如圖4(b)中箭頭所示,方格表示螞蟻在構建柵欄時,柵欄間隙處的待填補節點位置。改進的蟻群算法在構建柵欄的過程中根據已經加入的空間權重和部署方向角選擇下一跳傳感器節點。當部署區域內不存在滿足條件的節點時,算法會尋找最優的網格作為待填補虛擬節點位置,該位置將被標記,下一條柵欄構建不會重復選取該網格作為部署路徑。
圖4 柵欄構建示意圖
2 3D-ACO算法
傳統的蟻群算法通過螞蟻個體間信息的傳遞,多個螞蟻共同協作,從而尋找蟻穴到食物的最短路徑。本文提出一種適用于三維環境下的蟻群算法3D-ACO,通過引入空間權重和部署方向角度,限制螞蟻的活動方向,使其適用于三維環境下的柵欄構建。將三維待部署區域二維網格化,計算出各個網格梯度,根據網格梯度大小由小到大排序,從當前節點遍歷所有節點,隨后隨機拋撒m個節點,執行3D-ACO算法。考慮到構建柵欄為強柵欄和節點的感知范圍可能受環境影響,節點的真實半徑有所不同,所以,該算法限制螞蟻的移動能力,并在無合適節點的位置留下虛擬節點位置,再通過移動節點填補柵欄間隙,以確保構建強柵欄。3D-ACO算法框架如圖5所示。
圖5 3D-ACO 算法框架
2.1 螞蟻移動能力的限制
為了構建三維環境下的強柵欄覆蓋,需要對螞蟻的移動能力進行一定程度上的限制。這是因為WSN的強柵欄覆蓋為防止不丟失事件監測,要求相鄰節點間無間隙存在,即2個節點感知范圍內一定存在重疊部分。若節點A和節點B為構建的柵欄覆蓋中兩相鄰節點,則d(A,B)<2r。又因本文部署環境是三維山丘陵,所以傳感器部署后的理想感知范圍與實際感知到的范圍定會存在差距。已知理想探測半徑r,設Rr為節點實際感知半徑,為保證3D-ACO算法構建的是強柵欄,則有以下定義:
定義5螞蟻移動距離小于等于2Rr。Rr=rcos[arctan(icosψ)]。
假設傳感器節點所在網格范圍可近似看作坡度和坡向近似相同的理想坡面,如圖3所示,g表示沿ψ方向上的網格梯度,計算公式為:
g=tanφ
(3)
由式(1)和式(3)可知:
g=icosψ
(4)
由于地形影響,Rr和r在ψ方向的存在以下關系:
Rr=rcosφ
(5)
將式(3)、式(4)代入式(5),得:
Rr=rcos(arctang)=rcos[arctan(icosψ)]
(6)
當ψ=0時,φ=?,則Rr=rcos ?,即:
Rr=rcos[arctan(icosψ)]
(7)
為構建強柵欄,相鄰節點感知范圍一定存在重疊部分。為了保證所構建柵欄為強柵欄,本文限制螞蟻的移動能力為2Rr,當沒有合適節點時,則選定相應填補節點位置,繼續選擇下一跳節點。
2.2 啟發因子優化
本文通過引入空間權重和選擇方向角來改進蟻群算法。在監測區域內隨機拋撒傳感器節點,螞蟻首先從左邊界開始出發尋找最優路徑,通過選擇方向角和空間權重來優化螞蟻尋找路徑。下面給出空間權重和部署方向角的相關定義,以及優化函數的詳細介紹。
定義6(空間權重) 以起始節點為水平面,給待選擇路徑上的網格賦予不同的權值,稱為空間權重。
定義7(部署方向角) 在部署區域D的二維平面內,當前節點與下一步要選擇的節點之間的連線和水平方向的夾角。
下面給出空間權重和部署方向角的優化步驟。
1)空間權重
本文利用網格方向梯度引入的空間權重來作為蟻群算法的另外一個啟發信息。將集合G中各個網格上的節點求出權重,空間權重用κij表示,螞蟻選擇下一路徑時的選擇概率將會受到空間權重的影響,即空間權重值κij越大,狀態轉移概率就越小。
(8)
其中,gmax表示最大梯度值,即梯度閾值。當節點所在網格梯度比梯度閾值大時,則重新選擇節點。如圖6所示,節點A與節點B的坡度夾角為為?1,節點A和節點C的坡度夾角為?2,節點A和節點C的網格梯度分別為g1和g2。當gmax>g1>g2時,κ1>κ2。將空間權重轉化為啟發因子以改進傳統蟻群算法,對于螞蟻選擇路徑而言,空間權重越大,則該條路徑的選擇概率也相應地變大,即當從節點A選擇下一步路徑時將選擇坡度較平緩的節點B作為下一步選擇。
圖6 基于空間權重的節點選擇
2)部署方向角
引入空間權重啟發因子是為了使ACO算法適用于三維環境下構建柵欄。由于螞蟻選擇路徑時所依賴的只有當前節點的pi選擇下一節點pj的期望程度和路徑的信息量強度,但這可能使得算法陷入局部最優解,因此本文引入傳感器節點的選擇方向角作為蟻群算法的另外一個啟發信息。當θ越小時,θij越大,狀態轉移概率也越大。
(9)
如圖7所示,0≤θ≤π表示節點的部署方向。當θ=0且所選下一跳節點所在網格的豎直方向梯度均相同時,節點部署方向為水平方向是最佳的下一跳節點位置。節點A與節點B在二維環境下的夾角為θ2,節點A和節點C在二維環境下的夾角為θ1,由式(9)可知,當節點A選擇下一步路徑時將選擇節點B作為下一步選擇。
圖7 基于部署方向角的節點選擇
根據式(8)和式(9),狀態轉移概率做如下更改:
(10)
式(10)代表在t時刻螞蟻k由城市i轉移到節點j的轉移概率。
2.3 間隙填補
在有向節點模型中,節點不僅需要移動,還有可能需要轉動,因此,節點的能量消耗由轉動和移動能量消耗組成。在本文中,節點采用全向感知模型,所消耗能量僅為移動節點的消耗。如圖8所示,在節點移動至待填補位置的過程中,希望總能耗最小,故而選擇與待填補位置的距離最小的節點進行移動。
圖8 柵欄間隙填補示意圖
由節點位置以及待填補位置的坐標和網格梯度,可以求得移動節點的移動距離。對于所有的傳感器節點,可以根據距離目標位置的遠近選擇節點進行移動填補。關于能耗部分將在實驗仿真進行詳細分析。
2.4 柵欄構建過程
在傳統蟻群算法中,螞蟻選擇下一節點僅依賴τij和ηij2個因素,這可能會使節點陷入局部最優解。因此,本文引入節點的空間權重和部署方向角來限制信息素濃度和選擇下一跳節點路徑的期望程度對螞蟻選擇概率的影響,并利用移動節點填補柵欄間隙確保構建強柵欄。隨機拋撒節點之后,劃分網格,不同的節點所在位置高低不同,即空間權重不同,螞蟻從左邊界開始尋找最優路徑,當遇到不同的路徑時,通過改進的蟻群算法選擇最優路徑。當沒有可選擇節點時,記錄待填補間隙位置,之后進行移動填補。假設螞蟻從頭出發,根據優化后的信息尋找最優路徑,以構建強柵欄,具體步驟如下:
步驟1在待部署區域D中隨機拋撒n個節點,劃分網格,并記錄節點位置和所在網格。
步驟2計算節點所在網格的網格梯度將其作為節點的空間權重κij,計算節點間的夾角引入部署方向角θij。
步驟3將上述2個因子加入蟻群算法,執行3D-ACO算法,開始遍歷傳感器節點。
步驟4遍歷所有節點,更新信息素,并記錄間隙位置。
步驟5算法迭代,輸出節點使用數量最少的柵欄以及各節點位置。
步驟6判斷節點間距離d<2Rr,若是,繼續遍歷下一節點;否則,執行步驟7。
步驟7選擇距離間隙最短移動距離的節點,進行節點填補。若未到達終點,執行步驟6;若到達終點邊界,結束柵欄構建。
2.5 3D-ACO算法性能分析
1)能耗分析
本文構建柵欄所用節點需要消耗能量主要分為:節點發射信息的能量消耗es,接收信息后處理信息的能量消耗eb,節點發射信息到節點接收信息之間的能量消耗el,移動節點所需要的能耗Jt,其中,el和Jt主要由節點間距離決定。全部能量消耗計算公式為:
Et=es+eb+el+Jt
(11)
傳統蟻群算法、本文3D-ACO算法的總能耗分別用式(12)和式(13)表示。
(12)
(13)
同理,當節點與之前節點高度差不同(空間權重κij不同),其他條件相同時,在螞蟻選擇下一跳節點趨于直線的概率方面,兩算法相比有:
因此,本文算法所構建更趨向直線且平緩的柵欄覆蓋,也即兩蟻群算法中選擇下一跳節點總距離有:
∑d1ij>∑dij
用式(12)減去式(13)得到:
EACO-E3D-ACO=(N1-N)es+(Q1-Q)eb+
(14)
在節點發射信息方面,傳統的蟻群算法與3D-ACO算法都是由節點自身廣播信息,所以,3D-ACO算法相較于傳統的蟻群算法并未增加能耗。同理,節點接收信息并處理信息時也未增加能耗,故可以忽略這兩部分能耗。現在只考慮節點移動能耗,以及節點發射信息到節點接收信息之間的能量消耗el,而這兩部分能耗主要與節點移動距離有關系。由于傳統的蟻群算法中∑d1ij要大于3D-ACO算法中的∑dij,因此式(14)大于0。所以,3D-ACO算法要比傳統蟻群算法能耗低。
2)收斂速度和局部最優問題
傳統的蟻群算法前期由于信息匱乏,收斂速度較慢,而且其選擇下一跳節點時傾向于選擇距離最近的節點,容易陷入局部最優解。本文算法通過網格劃分,引入空間權重和部署方向角,提前排除不適用下一跳節點選擇的節點,以減少迭代次數,提高收斂速度,并且結合空間權重和部署方向角選擇更適合構建柵欄覆蓋的下一跳節點,避免陷入局部最優問題。因此,在三維環境下,本文3D-ACO算法性能更優。
3 仿真實驗
本文仿真實驗部署區域為300 m×200 m的矩形區域。隨機拋撒傳感器節點數量n,傳感器節點感知范圍均為球體,且節點具備移動能力,本文對監測區域進行強2-柵欄構建的仿真實驗。若無特別說明,實驗參數值均以表1所示參數為準,仿真實驗結果均取100次隨機實驗平均值,迭代次數定為300。
表1 實驗參數
本文從節點的自身因素出發根據節點感知半徑的不同進行比較,此外,選取strong optimal和strong greedy 2種算法進行仿真實驗比較,并參考其實驗數據。在下文實驗中,節點數量為原拋撒節點數量,所用節點數量是構成柵欄的節點數量,節點總能耗為全部節點消耗能量,節點平均能耗為總能耗與所有節點數量的比值。
3.1 感知半徑對結果的影響
傳感器節點的感知范圍隨著其感知半徑變化而變化,本文選取了不同感知半徑的傳感器節點進行仿真實驗,并對引入空間權重和部署方向角的3D-ACO算法進行性能分析,結果如圖9～圖11所示。
圖9 節點感知半徑對節點總能耗的影響
圖10 節點感知半徑對節點平均能耗的影響
圖11 節點感知半徑對所用節點數量的影響
從圖9可以看出,節點總的能量消耗隨著節點感知半徑的增加而減小。這是由于隨著節點感知半徑的增加,節點相應的感知范圍也增加,移動節點移動距離相應減少,進而使得傳感器節點總能耗降低。
從圖10可以看出,隨著傳感器節點感知半徑的增加,傳感器節點平均能耗逐漸降低,隨后趨于平緩。這是因為總能耗降低,而總節點數量不變,進而使得節點的平均消耗能量降低。
從圖11可以看出,隨著傳感器節點感知半徑的增加,傳感器節點使用的數量降低。這是因為傳感器節點半徑的逐漸增大,縮小了節點之間的部署方向角,此外,由于空間權重優化因子的優化,柵欄構建更為平緩的柵欄覆蓋,構建柵欄使用節點個數減少。
3.2 節點數量對結果的影響
在保證強柵欄可以構建的前提下,盡可能地減少節點的使用數量以對比相關算法的優劣。strong optimal和strong greedy算法對于節點數量有一定的要求,因此本文實驗節點數從100開始,以20為梯度值增加,直至200。節點總能耗、平均能耗以及構建柵欄節點使用數量的結果如圖12～圖14所示。
圖12 節點數量對節點總能耗的影響
圖13 節點數量對節點平均能耗的影響
圖14 節點數量對形成柵欄所需節點個數的影響
從圖12和圖13可以發現,3種算法的總能耗與傳感器節點的平均能耗均隨著拋撒節點數量的增加而明顯減少,在同樣的節點數量情況下,3D-ACO算法的總能耗和節點平均能耗則明顯地低于其他2種算法。這是因為隨著部署區域內傳感器節點密度變大,節點空間距離縮小,所以構建柵欄時節點移動距離減少,故而使得總能耗降低。隨著總能耗的降低,而節點數量增加,平均能耗也降低。從圖14可以看出,在構建柵欄過程中,3種算法使用傳感器的數量隨拋撒節點的增加而變多,最終趨于平緩。這是因為隨著節點數量的增多,算法會選擇更加平緩的路徑,但隨著迭代次數的增加,最優的路徑將會被確定。同時還可以看出,3D-ACO算法使用節點數量明顯低于其他2種算法的節點數量,且增加趨勢更為平緩。這是因為3D-ACO算法通過空間權重和部署方向角對螞蟻尋找節點的限制,所以在構建柵欄覆蓋時,更傾向于選擇空間距離小、署方向角度小的柵欄覆蓋路徑。
3.3 柵欄數量對結果的影響
本文在同一部署區域的不同柵欄數量K的情況下,對節點總能耗、平均能耗、需求的總節點數進行比較,結果分別如圖15～圖17所示。
圖15 柵欄數量對節點總能耗的影響
圖16 柵欄數量對節點平均能耗的影響
圖17 柵欄數量對形成柵欄所需節點個數的影響
從圖15和圖16可以看出,隨著構建柵欄數的增加,所需傳感器節點變多,因此移動節點消耗總能耗變大,其平均能耗也在增長。但3D-ACO算法的總能耗和平均能耗相較于其他2種算法越來越小。
從圖17可以看出,在構建相同數量的柵欄情況下,3D-ACO算法所需的節點數遠低于其他2種算法,例如當柵欄數K=6時,3D-ACO算法僅需要90個節點左右,其他2種算法則需要120個節點左右。這是因為3D-ACO算法柵欄的構建存在柵欄重疊的可能,這種情況在第2節中就已經介紹。所以柵欄覆蓋構建過程中隨著柵欄條數的增多,柵欄交叉的幾率增大,節點使用數量減少。
4 結束語
本文提出一種基于改進蟻群算法的三維K-柵欄覆蓋算法。引入空間權重改進蟻群算法使其適用于三維柵欄構建,利用部署方向角防止蟻群算法陷入局部最優,同時通過限制蟻群的移動能力以及移動節點填補柵欄間隙以確保強柵欄的形成。仿真實驗結果表明,3D-ACO算法在三維環境下部署柵欄時,可有效提高節點使用率,并且所構建的柵欄具有較強的自適應性。由于本文算法基于全向感知節點,下一步將針對在三維環境中有向無線傳感器網絡的柵欄覆蓋問題進行研究。
