宋 娜 馮夢清

(鄭州工業(yè)應(yīng)用技術(shù)學(xué)院信息工程學(xué)院 河南 鄭州 451150)

0 引 言

目前，無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)使用越來越廣泛，如環(huán)境檢測、智能家居和現(xiàn)代農(nóng)業(yè)等，這些場合需要無線傳感器網(wǎng)絡(luò)覆蓋的完整性[1-2]。但是傳感器在初始化階段往往隨機(jī)布放在所監(jiān)控區(qū)域中、節(jié)點(diǎn)能量消耗不均勻，最終漏洞出現(xiàn)使得覆蓋范圍有限，導(dǎo)致整個(gè)網(wǎng)絡(luò)失效。當(dāng)前對于無線傳感器網(wǎng)絡(luò)覆蓋漏洞檢測方法主要有：① 跳數(shù)算法(Hop Algorithm,HA)，主要是通過節(jié)點(diǎn)到鄰居的通信鏈路是否連通來判斷漏洞邊界節(jié)點(diǎn)，對跳數(shù)較大的節(jié)點(diǎn)效果比較好[3]，但是由于跳數(shù)需要遍歷性，所以時(shí)間開銷較大；② 鄰域拓?fù)渌惴?Neighborhood Topological Algorithm, NTA)是指如果某個(gè)節(jié)點(diǎn)的密度低于所有鄰居節(jié)點(diǎn)密度的平均值，則表示該節(jié)點(diǎn)為覆蓋漏洞邊界節(jié)點(diǎn)[4]，但是這種方法對于密集型網(wǎng)絡(luò)的效果并不理想，會出現(xiàn)誤判現(xiàn)象；③ 幾何分布式算法(Geometry Distributed Algorithm,GDA)，該算法首先需要計(jì)算傳感器節(jié)點(diǎn)及其相鄰兩節(jié)點(diǎn)形成的三角形的外接圓的半徑和圓心，然后根據(jù)計(jì)算幾何理論判斷節(jié)點(diǎn)是否為覆蓋漏洞的邊界節(jié)點(diǎn)[5]；④ Voronoi圖算法(Voronoi Graph Algorithms,VGA)是指若節(jié)點(diǎn)的監(jiān)測范圍與當(dāng)前節(jié)點(diǎn)到Voronoi圖頂點(diǎn)的長度小于設(shè)置的閾值，判斷當(dāng)前節(jié)點(diǎn)在覆蓋漏洞邊界上[6]；⑤ 循環(huán)分布式算法(Circular Distributed Algorithms,CDA)主要是根據(jù)循環(huán)覆蓋和相鄰節(jié)點(diǎn)的信息構(gòu)建關(guān)系表，然后通過查詢此表來檢測覆蓋漏洞的位置[7]；⑥ 粒子群算法(Particle Swarm Optimization,PSO)，該算法在進(jìn)行無線傳感器網(wǎng)絡(luò)覆蓋漏洞檢測時(shí)，由于后期處理容易陷入局部最優(yōu)，無法獲得真正的覆蓋漏洞邊界[8]。上述算法在檢測覆蓋漏洞的位置信息時(shí)，對覆蓋漏洞的面積僅僅通過近似三角形進(jìn)行計(jì)算，這導(dǎo)致了計(jì)算精度比較低的問題。為此，本文給出一種無線傳感器網(wǎng)絡(luò)基于改進(jìn)粒子群算法的覆蓋漏洞檢測方法(后文簡稱為IPSO)，該方法對覆蓋區(qū)域進(jìn)行單元格劃分，通過比較單元格的坐標(biāo)位置和放置在該單元中的每個(gè)傳感器節(jié)點(diǎn)位置來分析是否有覆蓋漏洞以及覆蓋漏洞邊界，改進(jìn)粒子群主要進(jìn)行粒子的適應(yīng)度函數(shù)值與自身當(dāng)前最佳值比較，以便獲得最優(yōu)檢測效果，最后對覆蓋漏洞檢測相關(guān)內(nèi)容進(jìn)行仿真，驗(yàn)證了所給方案的合理性。

1 無線傳感器網(wǎng)絡(luò)覆蓋漏洞判定

1.1 覆蓋漏洞檢測

無線傳感器網(wǎng)絡(luò)監(jiān)測區(qū)域中若有未被任何傳感器節(jié)點(diǎn)所覆蓋的范圍，則該范圍稱為覆蓋漏洞。覆蓋漏洞檢測需要對覆蓋區(qū)域劃分成若干個(gè)單元格，對每個(gè)單元格進(jìn)行相同的統(tǒng)計(jì)操作，每個(gè)單元格中包含若干傳感器節(jié)點(diǎn)，如圖1所示采取了4個(gè)單元格。

圖1 單元格

對于每4個(gè)單元格共用頂點(diǎn)采用Delaunay三角剖分法，由于Delaunay三角形的外接圓內(nèi)不包含其他節(jié)點(diǎn)[9]，每一個(gè)Delaunay三角形的外接圓被稱為其對應(yīng)的空外接圓，三角形頂點(diǎn)分別選擇離共用頂點(diǎn)較近的三個(gè)傳感器節(jié)點(diǎn)，這樣構(gòu)成的Delaunay三角形邊長分別為a、b和c，此三角形的空外接圓半徑rc計(jì)算式表示為：

(1)

當(dāng)形成的一個(gè)三角形的空外接圓半徑rc大于傳感器節(jié)點(diǎn)的感知半徑r，該三角形空外接圓圓心Oc到該三角形的三個(gè)頂點(diǎn)的距離大于r，此時(shí)該三角形空外接圓圓心Oc都沒有被三個(gè)傳感器節(jié)點(diǎn)所覆蓋，則說明無線傳感器網(wǎng)絡(luò)可能產(chǎn)生覆蓋漏洞。

1.2 覆蓋漏洞位置

利用無線傳感器網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)都能夠收、發(fā)信息特性，這樣每個(gè)節(jié)點(diǎn)都能獲得周圍鄰居節(jié)點(diǎn)的位置信息，利用位置信息構(gòu)建Delaunay三角外接圓圓心位置，圓心坐標(biāo)(x,y)表示為：

(2)

式中：x和y為外接圓圓心的坐標(biāo)，xi和yi為構(gòu)成該傳感器網(wǎng)絡(luò)中三個(gè)節(jié)點(diǎn)的位置坐標(biāo)，i=1,2,3。當(dāng)外接圓圓心到Delaunay三角形任何一個(gè)節(jié)點(diǎn)的距離大于傳感器的感知半徑時(shí)，即得出覆蓋漏洞的中心位置在(x,y)處。

1.3 覆蓋漏洞面積計(jì)算

覆蓋漏洞檢測方案通過選擇最近的傳感器節(jié)點(diǎn)到單元格頂點(diǎn)的坐標(biāo)來計(jì)算漏洞面積，選擇策略是通過比較單元格的坐標(biāo)位置和放置在該單元中的每個(gè)傳感器節(jié)點(diǎn)位置完成。在選擇所需的傳感器節(jié)點(diǎn)數(shù)后，覆蓋漏洞檢測算法選擇最近的傳感器節(jié)點(diǎn)作為單元格的頭節(jié)點(diǎn)。頭節(jié)點(diǎn)有兩個(gè)功能：從其他節(jié)點(diǎn)收集數(shù)據(jù)，并根據(jù)選定的路由協(xié)議對其進(jìn)行分類；使用三角測量法計(jì)算漏洞面積[10-11]。

覆蓋漏洞檢測方案是通過比較選擇的傳感器節(jié)點(diǎn)與每個(gè)單元邊緣位置點(diǎn)的最大傳輸范圍，如果所選傳感器節(jié)點(diǎn)的傳輸范圍在單元格的邊緣內(nèi)，則沒有覆蓋漏洞；反之，如果在單元格的邊緣之外，則肯定存在覆蓋漏洞。如圖2所示。

(a) 大區(qū)域覆蓋漏洞

(b) 小區(qū)域覆蓋漏洞圖2 單元格中的覆蓋漏洞

在選擇的傳感器節(jié)點(diǎn)和單元格邊緣之間通過應(yīng)用三角形方法測量來計(jì)算漏洞面積，將傳感器節(jié)點(diǎn)連接到最近的單元邊緣直線坐標(biāo)上，然后我們得到若干個(gè)三角形，如圖3所示。在圖3(a)大區(qū)域漏洞劃分4個(gè)三角形，圖3(b)小區(qū)域漏洞劃3個(gè)三角形，也可能存在漏洞區(qū)域劃分2個(gè)三角形和1個(gè)三角形。

(a) 大區(qū)域覆蓋漏洞劃分4個(gè)三角形

(b) 小區(qū)域覆蓋漏洞劃分3個(gè)三角形圖3 覆蓋漏洞劃分為多個(gè)三角形

根據(jù)三角測量理論，計(jì)算出劃分成多個(gè)小三角形的面積之和即可獲得漏洞面積，例如對圖3(a)大區(qū)域漏洞劃分4個(gè)三角形及其中某個(gè)三角形標(biāo)注如圖4所示。

(a) 劃分多個(gè)三角形標(biāo)注

(b) 三角形以及弓形標(biāo)注圖4 劃分為三角形

依據(jù)海倫公式，計(jì)算圖4(b)三個(gè)點(diǎn)(X0,Y0)、(Xa,Ya)和(Xb,Yb)所圍成三角形的面積S0計(jì)算式表示為：

(3)

式中：r是傳感器感知半徑；Z是三角形半周長。但是按三角形計(jì)算，將減少或者增加覆蓋漏洞面積，因此需要計(jì)算傳感器感知半徑與邊L3所對弧長包圍的弓形面積S1，其計(jì)算式表示為：

(4)

最終獲得邊L1、L2與覆蓋漏洞區(qū)域所圍成的面積Sholes表示為：

Sholes=S0-S1

(5)

因此通過增加弓形面積的計(jì)算，可以精確獲得覆蓋漏洞區(qū)域的面積。在單元格中到某個(gè)頂點(diǎn)的覆蓋漏洞面積可以通過求所劃分單個(gè)三角形以及弓形的面積之差獲得；重復(fù)計(jì)算單元格的覆蓋漏洞到同一單元的四個(gè)邊緣，即可獲得整個(gè)單元格中的任何覆蓋漏洞區(qū)域面積Sall。

2 方向感知粒子群算法

2.1 基本粒子群算法

基本粒子群算法[12]在搜索空間中更新速度和位置公式表示為：

(6)

式中：r1∈(0,1)和r2∈(0,1)為相互獨(dú)立的隨機(jī)函數(shù)；vi,j(t)為第i個(gè)粒子在第t次迭代的第j維速度；xi,j(t)為第i個(gè)粒子在第t次迭代的第j維位置；t為迭代次數(shù)；pi,j為當(dāng)前最佳解；gg,j為歷史最佳解；ω為權(quán)重；c1和c2分別為調(diào)節(jié)pi,j和gg,j的加速參數(shù)。

2.2 對比策略

在基本粒子群算法中，任何粒子都使用自身認(rèn)知項(xiàng)c1r1[pi,j-xi,j(t)]和群體認(rèn)知項(xiàng)c2r2[gg,j-xi,j(t)]來移動，當(dāng)粒子的適應(yīng)度值提高時(shí)[13]，跟蹤具有導(dǎo)向性的粒子更新pi,j?；玖Ｗ尤核惴ù嬖趦蓚€(gè)缺點(diǎn)：① 如果具有導(dǎo)向的粒子陷入當(dāng)前最優(yōu)狀態(tài)，則粒子的往復(fù)運(yùn)動完全浪費(fèi)，增加處理時(shí)間；② 粒子趨于過早收斂。

在對比策略中，主要進(jìn)行粒子的適應(yīng)度函數(shù)值Fi(t)與自身當(dāng)前最佳值pi比較：粒子i當(dāng)前處于個(gè)體自身當(dāng)前最佳值pi，若Fi(t)≥pi，則粒子處于極好狀態(tài)，飛行速度vnew極小范圍內(nèi)更新即可；若Fi(t)≤Fi(t-1)且Fi(t)≥pi，粒子處于較好狀態(tài)，飛行速度vnew更新較小范圍即可；若Fi(t)≥Fi(t-1)，粒子處于收縮狀態(tài)，飛行速度vnew需要較大范圍更新。下面給出不同情況下的不同更新策略，其中rand是(0,1)中的隨機(jī)數(shù)。

(1) 當(dāng)Fi(t)≥pi時(shí)，則更新策略表示為：

(7)

(2) 當(dāng)Fi(t)≤Fi(t-1)且Fi(t)≥pi時(shí)，則更新策略表示為：

(8)

(3) 當(dāng)Fi(t)≥Fi(t-1)時(shí)，則更新策略表示為：

(9)

2.3 粒子群適應(yīng)度函數(shù)

覆蓋漏洞面積檢測率是覆蓋區(qū)域中漏洞的面積與覆蓋總面積Sall的比值，是評價(jià)無線傳感器網(wǎng)絡(luò)覆蓋漏洞檢測的重要指標(biāo)[14-15]。所給方案將覆區(qū)域分解為L×H個(gè)單元格，按照式(3)、式(4)和式(5)計(jì)算每個(gè)單元格的覆蓋漏洞面積SL×H，獲得覆蓋漏洞面積檢測率η為：

(10)

所給方案把η轉(zhuǎn)化為求解Fi(t)最大值問題，在粒子群在迭代過程中，當(dāng)η越小時(shí)，網(wǎng)絡(luò)存在的覆蓋漏洞越小，此時(shí)Fi(t)越大：

Fi(t)=1-ηi(t)

(11)

IPSO的主要步驟如下所示：

第1步：粒子群參數(shù)初始化；

第2步：無線傳感器網(wǎng)絡(luò)隨機(jī)化，覆蓋區(qū)域劃分若干單元格；

第3步：粒子群按照式(6)、式(7)、式(8)和式(9)更新位置以及速度；

第4步：達(dá)到最大迭代次數(shù)，或η≤3%，則進(jìn)行第5步，否則轉(zhuǎn)第3步；

第5步：輸出檢測結(jié)果。

3 實(shí)驗(yàn)仿真分析

利用MATLAB 7.0軟件進(jìn)行仿真，傳感器節(jié)點(diǎn)數(shù)量為150個(gè)，部署矩形區(qū)域?yàn)?00 m×200 m，每個(gè)節(jié)點(diǎn)的通信半徑為20 m，感知半徑為10 m，在部署區(qū)域中隨機(jī)設(shè)置19個(gè)大小不同的覆蓋漏洞，所有覆蓋漏洞的面積之和占部署區(qū)域總面積的3%。其中，粒子群參數(shù)為：c1=c2=1.4，ω=0.9-(tmax-t)/(0.5×tmax)，最大迭代次數(shù)為tmax=200，粒子總數(shù)量為300個(gè)。

3.1 單元格與漏洞個(gè)數(shù)、面積關(guān)系

在固定的監(jiān)測區(qū)域內(nèi)，劃分單元格邊長L和H的大小不同，其覆蓋漏洞個(gè)數(shù)和面積也呈現(xiàn)出一定的變化規(guī)律。L和H設(shè)置分別為：①L=2 m，H=2 m；②L=7 m，H=7 m；③L=10 mm，H=10 m；④L=13 m，H=13 m；⑤L=15 m，H=15 m；⑥L=20 m，H=20 m。通過50次蒙特卡羅隨機(jī)部署節(jié)點(diǎn)仿真實(shí)驗(yàn)，檢測得到的覆蓋漏洞個(gè)數(shù)和面積結(jié)果如圖5所示。

(a) 單元格與檢測漏洞個(gè)數(shù)關(guān)系

(b) 單元格與漏洞面積檢測率η關(guān)系圖5 單元格與檢測漏洞個(gè)數(shù)、面積關(guān)系

由圖5(a)可以看出，隨著劃分單元格邊長為L和H逐漸變大，檢測漏洞個(gè)數(shù)在增加，邊長越靠近感知半徑時(shí)，檢測漏洞個(gè)數(shù)逐漸趨于真實(shí)值；由圖5(b)可以看出，隨著劃分單元格邊長為L和H逐漸變大接近感知半徑，漏洞面積檢測率η在減少，邊長越離感知半徑越大時(shí)，則檢測η越偏離實(shí)際值。單元格邊長越接近感知半徑時(shí)，則越有利于漏洞個(gè)數(shù)、面積檢測。

3.2 粒子數(shù)量、迭代次數(shù)與漏洞數(shù)量檢測比

在單元格邊長為L=H=10 m條件下，漏洞數(shù)量分別設(shè)置為4、6、8、10和12個(gè)，則粒子數(shù)量、迭代次數(shù)與漏洞數(shù)量檢測比如圖6所示。

(a) 粒子數(shù)量與漏洞數(shù)量檢測比

(b) 粒子迭代次數(shù)與漏洞數(shù)量檢測比圖6 粒子數(shù)量、迭代次數(shù)與漏洞數(shù)量檢測比

由圖6(a)可以看出，隨著粒子數(shù)量的增加，漏洞數(shù)量檢測比在逐漸提高，在相同粒子數(shù)量條件下，漏洞數(shù)量越多，則檢測比越差，在漏洞數(shù)量為4個(gè)時(shí)、粒子180個(gè)時(shí)，檢測比即可達(dá)到100%，在漏洞數(shù)量為12個(gè)時(shí)，需要粒子260個(gè)時(shí)，檢測比才能達(dá)到100%；由圖6(b)可以看出，在漏洞數(shù)量為4個(gè)時(shí)，粒子迭代次數(shù)為95次左右時(shí)，檢測比即可達(dá)到100%，在漏洞數(shù)量為12個(gè)時(shí)，粒子迭代次數(shù)為190次左右時(shí)，檢測比才能達(dá)到100%。這是因?yàn)楫?dāng)粒子群的數(shù)量增加時(shí)，越有利于發(fā)現(xiàn)無線傳感器網(wǎng)絡(luò)中的漏洞，同時(shí)漏洞數(shù)量越多，則需要迭代次數(shù)也隨之增加。

3.3 檢測指標(biāo)對比分析

檢測指標(biāo)分析主要包括漏洞面積檢測率和處理時(shí)間，用于對比分析的相關(guān)算法主要有HA、NTA、GDA、VGA、CDA、PSO和IPSO，每種算法各進(jìn)行40次蒙特卡羅仿真實(shí)驗(yàn)，結(jié)果如圖7所示。

(a) 漏洞面積檢測率

(b) 處理時(shí)間圖7 檢測指標(biāo)對比分析

可以看出，IPSO對覆蓋漏洞面積檢測、處理時(shí)間相比其他算法具有優(yōu)勢，這主要是由于IPSO考慮了單元格中弓形面積對覆蓋漏洞面積的影響，使得覆蓋漏洞面積檢測率更加符合真實(shí)值，粒子群在進(jìn)行粒子的適應(yīng)度函數(shù)值與自身當(dāng)前最佳值比較過程中，采取不同的更新策略，防止了粒子尋優(yōu)的盲目性。下面通過分析漏洞檢測率與檢測時(shí)間的關(guān)系來驗(yàn)證所給方案更新策略的有效性，如圖8所示。可以看出，IPSO所需的監(jiān)測時(shí)間最少，而且隨著漏洞檢測率的提高，IPSO的檢測時(shí)間增加也最少，這主要是由于IPSO采用新的更新策略，通過比較粒子的適應(yīng)度函數(shù)值和自身當(dāng)前最佳值，及時(shí)調(diào)整粒子的飛行速度和位置，能夠更快速地檢測出漏洞。由此說明，IPSO的更新策略是有效的。

圖8 IPSO更新策略的有效性分析

4 結(jié) 語

為提高無線傳感器網(wǎng)絡(luò)覆蓋漏洞的監(jiān)測效果，采用改進(jìn)粒子群算法對無線傳感器網(wǎng)絡(luò)漏洞檢測。所給方案首先對覆蓋區(qū)域劃分不同單元格，單元格頂點(diǎn)劃分成多個(gè)小三角形的面積與弓形的面積之差獲得漏洞面積，然后利用改進(jìn)粒子群算法進(jìn)行粒子的適應(yīng)度函數(shù)值與自身當(dāng)前最佳值比較，獲得不同的更新速度與位置。實(shí)驗(yàn)仿真得出單元格邊長越接近感知半徑越有利于漏洞個(gè)數(shù)、面積檢測。而且相比于其他算法，所給方案在漏洞面積檢測上處理時(shí)間也具有優(yōu)勢。