基于Delaunay三角劃分策略的WSN區(qū)域覆蓋優(yōu)化研究*

張 晶，魏 淼

(1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，云南 昆明 650500;2.云南梟潤(rùn)科技服務(wù)有限公司，云南 昆明 650500;3.昆明理工大學(xué)云南省人工智能重點(diǎn)實(shí)驗(yàn)室，云南 昆明 650500;4.昆明理工大學(xué)云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，云南 昆明 650500)

1 引言

近年來無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)在各個(gè)專業(yè)領(lǐng)域的應(yīng)用之中都有良好的表現(xiàn)，而構(gòu)建一個(gè)完備的無線傳感器網(wǎng)絡(luò)的首要問題便是如何對(duì)傳感器節(jié)點(diǎn)進(jìn)行部署。由于在如山林、荒漠、高樓等具有特殊性的環(huán)境之中對(duì)傳感器網(wǎng)絡(luò)進(jìn)行部署時(shí)，人工部署節(jié)點(diǎn)的工作具有很大的難度，而傳感器節(jié)點(diǎn)在通過飛行器拋灑的過程中，由于環(huán)境和拋灑方式的影響必然無法一次性將節(jié)點(diǎn)布署在合適的位置，從而在監(jiān)測(cè)區(qū)域中產(chǎn)生覆蓋漏洞[1]。所以，如何通過無線傳感器網(wǎng)絡(luò)中的移動(dòng)節(jié)點(diǎn)對(duì)在監(jiān)測(cè)區(qū)域內(nèi)存在的大量覆蓋漏洞進(jìn)行修補(bǔ)，以提高監(jiān)測(cè)區(qū)域的覆蓋率，是當(dāng)下無線傳感器網(wǎng)絡(luò)的相關(guān)研究領(lǐng)域亟需解決的一大問題。

無線傳感器網(wǎng)絡(luò)的覆蓋問題根據(jù)監(jiān)測(cè)效果的不同，可以分為點(diǎn)覆蓋問題、區(qū)域覆蓋問題和柵欄覆蓋問題[2]。目前針對(duì)無線傳感器網(wǎng)絡(luò)在平面區(qū)域的覆蓋優(yōu)化問題，國(guó)內(nèi)外的學(xué)者進(jìn)行了大量的研究，且取得了優(yōu)越的成果。近些年來計(jì)算幾何學(xué)在區(qū)域覆蓋優(yōu)化問題上得到了很好的應(yīng)用。文獻(xiàn)[3]提出了一種基于泰森多邊形形心的部署策略，雖然在一定程度上降低了算法的復(fù)雜度，但是在最終的覆蓋效果方面還可以進(jìn)一步提高。方偉等人[4]提出了一種基于Voronoi圖的WSN覆蓋部署策略，通過Voronoi圖對(duì)監(jiān)測(cè)區(qū)域內(nèi)的節(jié)點(diǎn)進(jìn)行劃分得到泰森多邊形，從而進(jìn)一步分析得出覆蓋漏洞，再通過傳感器網(wǎng)絡(luò)動(dòng)態(tài)節(jié)點(diǎn)移動(dòng)到盲區(qū)多邊形形心位置的方式來達(dá)到提高覆蓋率的目的。但是，該部署策略計(jì)算較為復(fù)雜，算法復(fù)雜度較高。雖然計(jì)算幾何學(xué)在區(qū)域覆蓋優(yōu)化上應(yīng)用甚廣，但是由于計(jì)算復(fù)雜，絕大多數(shù)研究都是在節(jié)點(diǎn)的布爾感知模型下進(jìn)行的，這就造成了優(yōu)化結(jié)果的理想化。而群優(yōu)化智能算法在覆蓋優(yōu)化問題中的應(yīng)用，雖然避免了復(fù)雜的幾何推導(dǎo)及計(jì)算，如基于粒子群優(yōu)化PSO(Particle Swarm Optimization)算法的覆蓋優(yōu)化方法或者基于人工蜂群算法的覆蓋優(yōu)化方法，但是群優(yōu)化智能算法往往存在種群粒子難以跳出局部最優(yōu)、算法收斂速度欠佳等缺點(diǎn)[5]。如文獻(xiàn)[6]提出了一種基于灰狼算法的覆蓋優(yōu)化方案，雖然提高了覆蓋率，但較之其他算法仍有不足；文獻(xiàn)[7]提出了一種改進(jìn)蟻獅算法的WSN覆蓋優(yōu)化方案，能夠極大程度提高無線傳感器網(wǎng)絡(luò)的性能，但其收斂速度還有進(jìn)一步優(yōu)化的空間。

本文針對(duì)無線傳感器網(wǎng)絡(luò)在對(duì)初次拋灑節(jié)點(diǎn)形成的覆蓋漏洞進(jìn)行二次部署的過程中，傳統(tǒng)的計(jì)算幾何學(xué)方法難以應(yīng)用于概率感知模型的問題，提出概率感知模型下監(jiān)測(cè)區(qū)域內(nèi)節(jié)點(diǎn)完全未覆蓋區(qū)域的概念，首先對(duì)監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)拋灑的靜態(tài)節(jié)點(diǎn)進(jìn)行Delaunay三角劃分，以得到靜態(tài)節(jié)點(diǎn)三角網(wǎng)；并通過三角網(wǎng)邊緣頂點(diǎn)構(gòu)建監(jiān)測(cè)區(qū)域內(nèi)完整的三角網(wǎng)，證明三角形內(nèi)部存在完全未覆蓋區(qū)域，并將求取的三角形形心集合作為粒子群優(yōu)化算法的初始解集；最后通過個(gè)體搜索能力增強(qiáng)的改進(jìn)粒子群優(yōu)化算法完成無線傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化。通過仿真實(shí)驗(yàn)與其他算法進(jìn)行對(duì)比，本文所提出的基于Delaunay三角劃分結(jié)合粒子群優(yōu)化算法的區(qū)域覆蓋優(yōu)化算法——DPSO(Delaunay triangulation improved Particle Swarm Optimization)算法具有更好的收斂速度，并且能夠修復(fù)無線傳感器網(wǎng)絡(luò)初次拋灑產(chǎn)生的漏洞，使區(qū)域覆蓋率得到顯著提高。

2 傳感器覆蓋模型

2.1 概率感知模型

由于無線傳感器網(wǎng)絡(luò)對(duì)環(huán)境的監(jiān)測(cè)是需要通過每個(gè)節(jié)點(diǎn)之間的合作共同完成的，故而研究無線傳感器的覆蓋就需要先建立單個(gè)傳感器節(jié)點(diǎn)的感知模型。在近些年對(duì)無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化的研究中，國(guó)內(nèi)外的大多數(shù)學(xué)者使用布爾感知模型來表示單個(gè)節(jié)點(diǎn)的感知能力。在該模型中，在傳感器節(jié)點(diǎn)感知半徑范圍內(nèi)的區(qū)域可以被節(jié)點(diǎn)準(zhǔn)確地感知，即感知概率為1；而在感知半徑距離外的區(qū)域皆不可被此節(jié)點(diǎn)所感知，即感知概率為0。布爾模型忽略了周圍環(huán)境以及信號(hào)隨距離衰減等因素的影響，因具有模型簡(jiǎn)單、易于實(shí)驗(yàn)等特性而被廣泛地應(yīng)用。但是，在傳感器網(wǎng)絡(luò)的實(shí)際監(jiān)測(cè)過程中，傳感器節(jié)點(diǎn)的感知概率通常會(huì)受到環(huán)境、信號(hào)傳輸距離等因素的影響?；诖?，研究人員進(jìn)一步提出了一種概率感知模型，該模型可以有效地反映出傳感器節(jié)點(diǎn)的感知能力隨感知距離變化的特性[8]。

記監(jiān)測(cè)區(qū)域中所有的無線傳感器節(jié)點(diǎn)為(S1,S2,…Si,…,SN)，所有的目標(biāo)監(jiān)測(cè)點(diǎn)為(T1,T2,…Tj,…,TM)，則傳感器節(jié)點(diǎn)Si對(duì)目標(biāo)監(jiān)測(cè)點(diǎn)Tj的感知概率模型如式(1)所示：

(1)

其中，P(Si,Tj)表示網(wǎng)絡(luò)中任一節(jié)點(diǎn)Si可以感知到目標(biāo)Tj的概率，d(Si,Tj)表示節(jié)點(diǎn)Si到Tj的距離，RSi表示節(jié)點(diǎn)Si可以感知目標(biāo)點(diǎn)的最遠(yuǎn)距離，r表示在此距離內(nèi)目標(biāo)可以被該傳感器節(jié)點(diǎn)完全感知，α=d(Si,Tj)-r，λ和β是用來表示單個(gè)傳感器節(jié)點(diǎn)感知能力的可調(diào)參數(shù)值，使用DSi表示傳感器節(jié)點(diǎn)Si的通信半徑并且有DSi≥2RSi。

2.2 區(qū)域覆蓋率

假設(shè)被監(jiān)測(cè)區(qū)域?yàn)橐粋€(gè)m×n的二維方形區(qū)域，目標(biāo)監(jiān)測(cè)點(diǎn)的個(gè)數(shù)為M，無線傳感器節(jié)點(diǎn)個(gè)數(shù)為N。

在傳感器網(wǎng)絡(luò)需要監(jiān)測(cè)的區(qū)域內(nèi)的目標(biāo)點(diǎn)Tj可能會(huì)位于多個(gè)節(jié)點(diǎn)感知范圍所交叉的區(qū)域，則該目標(biāo)監(jiān)測(cè)點(diǎn)Tj的聯(lián)合感知概率如式(2)所示：

(2)

無線傳感器網(wǎng)絡(luò)對(duì)需要監(jiān)測(cè)的區(qū)域的覆蓋率通過傳感器網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)可以有效監(jiān)測(cè)到的范圍與該區(qū)域的面積之比表示，則區(qū)域覆蓋率Pcov可表示如式(3)所示：

(3)

3 相關(guān)算法

3.1 基本粒子群優(yōu)化算法

基本粒子群優(yōu)化算法PSO屬于智能優(yōu)化算法的一種，該算法的核心思想是模仿自然界中禽類尋找食物的行為，在解決傳感器網(wǎng)絡(luò)覆蓋優(yōu)化的問題時(shí)，先從隨機(jī)產(chǎn)生的解集出發(fā)，通過粒子不斷對(duì)自身位置進(jìn)行更新，指導(dǎo)傳感器網(wǎng)絡(luò)中的動(dòng)態(tài)節(jié)點(diǎn)移動(dòng)，經(jīng)過多次迭代最終尋找到可以使傳感器網(wǎng)絡(luò)覆蓋率得以提高的解。粒子群優(yōu)化算法因其參數(shù)少、便于實(shí)現(xiàn)的特性而被廣泛應(yīng)用，但是其依然存在易收斂于局部最優(yōu)等缺陷[9]。PSO算法流程如下所示：

Step1初始化算法的相關(guān)參數(shù)。

Step2計(jì)算粒子的適應(yīng)度值。

Step3更新個(gè)體和全局的最優(yōu)解。

Step4若算法已經(jīng)達(dá)到所設(shè)置的最大迭代次數(shù)，則停止迭代，算法結(jié)束；否則根據(jù)式(4)和式(5)計(jì)算更新粒子下一時(shí)刻的速度和位置，并跳回到Step 2計(jì)算新一輪的適應(yīng)度值并繼續(xù)執(zhí)行，直到算法達(dá)到所設(shè)置的最大迭代次數(shù)。

根據(jù)上述算法流程，在迭代過程中粒子需要對(duì)自身的位置與速度進(jìn)行不斷更新，粒子每次對(duì)速度與位置更新的公式如式(4)和式(5)所示：

(4)

(5)

3.2 人工蜂群算法

人工蜂群ABC(Artificial Bee Colony)算法模仿自然界中蜜蜂的采蜜行為[10]，蜂群中包含的采蜜蜂、觀察蜂和偵查蜂會(huì)根據(jù)從蜂群獲得的信息進(jìn)行自身位置的移動(dòng)，從而達(dá)到尋找最大蜜量蜜源的目的。

在基本的人工蜂群算法中，采蜜蜂通過蜜源信息來更新自身位置，以尋找新的蜜源。蜂群中第i個(gè)采蜜蜂位置更新的依據(jù)如式(6)所示[11]：

x′i=xi+φi(xi-xk)

(6)

其中，xi和x′i分別表示舊的蜜源和采蜜蜂所尋找的新蜜源的位置，φi表示在[-1,1] 內(nèi)的隨機(jī)數(shù)，k≠i。算法將新找到的蜜源x′i與舊蜜源xi作比較，并采取貪婪策略的思想保留較好的蜜源。

4 DPSO算法

4.1 Delaunay三角形形心確定初始解集

4.1.1 區(qū)域Delaunay三角形劃分

由于本文采用的傳感器節(jié)點(diǎn)概率感知模型具有感知能力隨距離減弱，超出最大感知半徑則不能感知的特性，故而本文提出一種監(jiān)測(cè)區(qū)域內(nèi)絕對(duì)未覆蓋區(qū)域的概念。

定義1若監(jiān)測(cè)區(qū)域內(nèi)存在某一塊區(qū)域不能被任何傳感器節(jié)點(diǎn)所感知，即在所有節(jié)點(diǎn)的最大感知半徑之外，則稱此區(qū)域?yàn)閭鞲衅骶W(wǎng)絡(luò)的絕對(duì)未覆蓋區(qū)域。

Delaunay三角劃分是一種特殊的離散點(diǎn)三角網(wǎng)的構(gòu)成方法，由俄國(guó)的數(shù)學(xué)家Delaunay提出[12]。其特征包括：以最接近的3個(gè)頂點(diǎn)連接形成三角形，所構(gòu)成的三角網(wǎng)的邊緣必然為一個(gè)凸多邊形。

對(duì)監(jiān)測(cè)區(qū)域內(nèi)的所有傳感器節(jié)點(diǎn)進(jìn)行Delaunay三角劃分并構(gòu)建三角網(wǎng)，通過對(duì)比各傳感器節(jié)點(diǎn)與監(jiān)測(cè)區(qū)域邊界之間所構(gòu)建成的三角形的邊長(zhǎng)與節(jié)點(diǎn)覆蓋半徑的大小，可以判斷三角形內(nèi)部是否存在絕對(duì)未覆蓋區(qū)域。

對(duì)區(qū)域內(nèi)所有的點(diǎn)進(jìn)行Delaunay三角劃分，可以得到如圖1所示的三角網(wǎng)。

Figure 1 Delaunay triangulation of nodes圖1 節(jié)點(diǎn)的Delaunay三角網(wǎng)

除此之外，Delaunay三角網(wǎng)的邊緣與監(jiān)測(cè)區(qū)域邊界之間也存在大量的未覆蓋區(qū)域，本文將對(duì)此邊緣區(qū)域進(jìn)行進(jìn)一步劃分。

首先獲取所有位于Delaunay三角網(wǎng)邊緣的傳感器節(jié)點(diǎn)，并與監(jiān)測(cè)區(qū)域的邊界構(gòu)成新的多邊形，然后對(duì)此多邊形進(jìn)一步進(jìn)行Delaunay三角劃分，從而完成整個(gè)監(jiān)測(cè)區(qū)域內(nèi)的三角劃分。

判斷被劃分的多邊形是否全為凸多邊形，若存在非凸多邊形，則使用Delaunay三角劃分對(duì)該多邊形進(jìn)行進(jìn)一步剖分，直到監(jiān)測(cè)區(qū)域被完全劃分成Delaunay三角形。經(jīng)過本文上述劃分過程的監(jiān)測(cè)區(qū)域如圖2所示。

Figure 2 Regional Delaunay triangulation圖2 區(qū)域Delaunay三角劃分

4.1.2 根據(jù)Delaunay三角形判斷絕對(duì)無覆蓋區(qū)域

本文通過Delaunay三角形的最長(zhǎng)邊與節(jié)點(diǎn)的最大感知半徑的長(zhǎng)度關(guān)系，證明三角形內(nèi)出現(xiàn)絕對(duì)未覆蓋區(qū)域的規(guī)律如下所示：

假設(shè)傳感器節(jié)點(diǎn)A,B,C擁有完全相同的屬性，記以此3個(gè)節(jié)點(diǎn)為頂點(diǎn)所構(gòu)成的三角形為ΔABC，用R表示3個(gè)節(jié)點(diǎn)的最大感知半徑，用d(,)表示2個(gè)傳感器節(jié)點(diǎn)之間的距離。則經(jīng)過Delaunay三角劃分的三角形與絕對(duì)未覆蓋區(qū)域有以下關(guān)系：

(1)如圖3a所示，當(dāng)三角形的3條邊長(zhǎng)皆小于傳感器節(jié)點(diǎn)最大感知半徑的2倍，即max(d(A,B),d(A,C),d(B,C))<2R時(shí)，三角形內(nèi)部必然不存在完全未覆蓋區(qū)域。

(2)如圖3b所示，當(dāng)三角形中的最大邊長(zhǎng)恰好與節(jié)點(diǎn)最大感知半徑的2倍相等，即max(d(A,B),d(A,C),d(B,C))=2R時(shí)，當(dāng)且僅當(dāng)此三角形為銳角三角形時(shí)，三角形內(nèi)部出現(xiàn)絕對(duì)未覆蓋區(qū)域且完全位于三角形內(nèi)部。

(3)如圖3c所示，當(dāng)三角形的最大邊長(zhǎng)超過節(jié)點(diǎn)最大感知半徑的2倍，即max(d(A,B),d(A,C),d(B,C))>2R時(shí)，若此三角形為銳角三角形或直角三角形，則三角形內(nèi)部必然存在完全未覆蓋區(qū)域，若此三角形為鈍角三角形，若點(diǎn)C到AB的垂直距離大于傳感器最大感知半徑，則三角形內(nèi)部出現(xiàn)絕對(duì)未覆蓋區(qū)域。

Figure 3 Relationship between Delaunay triangle and absolutely uncovered area圖3 Delaunay三角形與絕對(duì)未覆蓋區(qū)域關(guān)系

4.1.3 確定Delaunay三角形形心

根據(jù)4.1.2節(jié)可知，傳感器節(jié)點(diǎn)感知的絕對(duì)未覆蓋區(qū)域出現(xiàn)在三角形的內(nèi)部，故可以求出已經(jīng)剖分完畢的Delaunay三角形的形心位置，并從三角形的形心集合中產(chǎn)生PSO算法的初始解集，迅速定位出粒子在整個(gè)目標(biāo)區(qū)域?qū)?yōu)的大概位置，有利于全局尋優(yōu)并加快算法的收斂速度。

將一個(gè)由節(jié)點(diǎn)A、B、C所構(gòu)成的三角形的頂點(diǎn)坐標(biāo)按照順時(shí)針的方向記為(X1,Y1),(X2,Y2),(X3,Y3)，將此三角形的形心坐標(biāo)記為(Cx,Cy)，則形心計(jì)算公式如式(7)和式(8)所示：

(7)

(8)

4.2 改進(jìn)粒子群優(yōu)化算法

在基本粒子群優(yōu)化算法及其相關(guān)的改進(jìn)算法中，通常用以評(píng)價(jià)算法性能的準(zhǔn)則是種群和粒子的搜索能力，而兩者則主要通過算法的收斂速度和解的準(zhǔn)確程度來評(píng)價(jià)。然而，由于PSO算法缺乏嚴(yán)密的數(shù)學(xué)推導(dǎo)過程，盡管一些方法能夠提高算法的全局探索能力，但是從單個(gè)粒子的角度出發(fā)，依然存在陷于局部最優(yōu)的缺點(diǎn)。所以，本文從粒子局部探索能力的角度著手，設(shè)計(jì)一種方案以提高粒子個(gè)體的探索能力，從而達(dá)到加快算法收斂速度的目的[13]。

4.2.1 個(gè)體粒子搜索能力增強(qiáng)

考慮到無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化領(lǐng)域中使用粒子群優(yōu)化算法容易陷入局部最優(yōu)的缺陷，本文結(jié)合人工蜂群算法的采蜜蜂行為設(shè)計(jì)一種增強(qiáng)單個(gè)粒子尋優(yōu)能力的改進(jìn)粒子群優(yōu)化算法。其主要思想如下所示：

使用傳感器網(wǎng)絡(luò)區(qū)域覆蓋率的求解公式作為算法的適應(yīng)度函數(shù)，算法每次迭代粒子產(chǎn)生新的速度和位置后選取當(dāng)前適應(yīng)度值最優(yōu)的粒子隨機(jī)產(chǎn)生若干個(gè)虛擬粒子，并模仿人工蜂群算法蜜蜂的行為模式按照式(6)向隨機(jī)方向進(jìn)行試探性搜索并更新自己的位置，若所產(chǎn)生的若干個(gè)虛擬粒子中的某個(gè)粒子試探性搜索得到的結(jié)果優(yōu)于當(dāng)前粒子，則用該虛擬粒子代替當(dāng)前粒子。

從式(6)中可以看出，由于φi的取值介于[-1,1]，從而可以使虛擬粒子的移動(dòng)方向更具有隨機(jī)性，粒子的搜索能力得到提高并且免于陷入局部最優(yōu)。而本文在算法的每次迭代過程中只選取了當(dāng)前適應(yīng)度值最優(yōu)的粒子產(chǎn)生虛擬粒子，從而避免了大量計(jì)算。

4.2.2 改進(jìn)粒子群優(yōu)化算法流程

本文所提出的改進(jìn)PSO算法流程如下所示：

Step1初始化算法的相關(guān)參數(shù)。

Step2計(jì)算粒子的適應(yīng)度值。

Step3選取當(dāng)前適應(yīng)度值最優(yōu)的粒子，并隨機(jī)產(chǎn)生若干個(gè)虛擬粒子，按照3.3節(jié)式(6)更新每個(gè)虛擬粒子的位置，并與當(dāng)前粒子對(duì)比，若某個(gè)虛擬粒子的適應(yīng)度值更優(yōu)，則由此虛擬粒子代替當(dāng)前粒子。

Step4更新個(gè)體和全局的最優(yōu)解。

Step5若算法已經(jīng)達(dá)到所設(shè)置的最大迭代次數(shù)，則停止迭代，算法結(jié)束；否則根據(jù)式(4)和式(5)計(jì)算更新粒子下一時(shí)刻的速度和位置，并跳回到Step 2繼續(xù)執(zhí)行，直到迭代結(jié)束。

Figure 4 Comparison of convergence between two algorithms圖4 2種算法收斂性對(duì)比

通過圖4可以看出，經(jīng)過不同的迭代次數(shù)，標(biāo)準(zhǔn)PSO算法和本文所提出的改進(jìn)PSO算法都能夠達(dá)到Sphere函數(shù)的最小函數(shù)值0，但相較于標(biāo)準(zhǔn)的PSO算法迭代40次，本文所提出的改進(jìn)PSO算法在迭代12次之后，粒子群收斂于最優(yōu)值0，擁有更好的收斂速度。

4.3 DPSO算法流程

DPSO算法具體執(zhí)行過程描述如下：

Step1無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)部署，獲取所有節(jié)點(diǎn)的坐標(biāo)值并根據(jù)2.2節(jié)中的式(3)計(jì)算出初始覆蓋率。

Step2根據(jù)靜態(tài)節(jié)點(diǎn)坐標(biāo)，使用Delaunay三角網(wǎng)進(jìn)行劃分，再將劃分完的Delaunay三角網(wǎng)與傳感器網(wǎng)絡(luò)區(qū)域邊界作進(jìn)一步的Delaunay三角劃分，構(gòu)建完整的監(jiān)測(cè)區(qū)域Delaunay三角網(wǎng)。

Step3根據(jù)4.1.2節(jié)選取所有存在絕對(duì)未覆蓋區(qū)域的三角形，并根據(jù)式(7)和式(8)計(jì)算三角形的形心位置。

Step4對(duì)算法中的相關(guān)參數(shù)進(jìn)行初始化，其中種群的初始位置從三角形的形心位置集合中選取產(chǎn)生。

Step5計(jì)算粒子的適應(yīng)度值。

Step6選取適應(yīng)度值最優(yōu)的粒子，產(chǎn)生5個(gè)虛擬粒子，按照3.3節(jié)的式(6)更新每個(gè)虛擬粒子的位置，并與原粒子對(duì)比，若其中某個(gè)虛擬粒子的適應(yīng)度值更優(yōu)，則用此虛擬粒子代替原粒子。

Step7更新個(gè)體和全局的最優(yōu)解。

Step8若算法達(dá)到最大迭代次數(shù)，則停止迭代，算法結(jié)束；否則根據(jù)3.2節(jié)中式(4)和式(5)計(jì)算更新粒子的速度和位置，并跳回Step 5繼續(xù)執(zhí)行，直到迭代次數(shù)達(dá)到初始設(shè)置的迭代最大值。

Step9輸出最優(yōu)的動(dòng)態(tài)節(jié)點(diǎn)移動(dòng)位置，計(jì)算當(dāng)前的覆蓋率并生成監(jiān)測(cè)區(qū)域的覆蓋圖。

本文算法的流程圖如圖5所示。

Figure 5 Flow chart of DPSO圖5 DPSO算法流程

5 仿真實(shí)驗(yàn)

5.1 相關(guān)參數(shù)

假設(shè)實(shí)驗(yàn)過程中需要監(jiān)測(cè)的區(qū)域面積為100 m×100 m。實(shí)驗(yàn)中計(jì)算網(wǎng)絡(luò)覆蓋率所使用的概率感知模型的相關(guān)參數(shù)為：RAi=10 m，r=6 m，λ=β=0.5。

在實(shí)驗(yàn)過程中，本文直接采用區(qū)域覆蓋率的計(jì)算公式作為算法的適應(yīng)度函數(shù)，如式(9)所示：

(9)

5.2 實(shí)驗(yàn)及結(jié)果分析

本文以Matlab 2016a為實(shí)驗(yàn)環(huán)境對(duì)無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問題的求解方法進(jìn)行了仿真，其相關(guān)參數(shù)設(shè)置如5.1節(jié)所述。

首先取50個(gè)傳感器節(jié)點(diǎn)，其中靜態(tài)節(jié)點(diǎn)30個(gè)，動(dòng)態(tài)節(jié)點(diǎn)20個(gè)。通過初始的隨機(jī)部署所形成的覆蓋效果如圖6所示，其中淺色代表靜態(tài)節(jié)點(diǎn)，深色代表動(dòng)態(tài)節(jié)點(diǎn)。通過計(jì)算可以得出監(jiān)測(cè)區(qū)域內(nèi)網(wǎng)絡(luò)的初始覆蓋率為58.18%。經(jīng)過DPSO算法優(yōu)化后，監(jiān)測(cè)區(qū)域內(nèi)的節(jié)點(diǎn)分布如圖7所示，可以看出，動(dòng)態(tài)節(jié)點(diǎn)較好地移動(dòng)到了網(wǎng)絡(luò)的絕對(duì)未覆蓋區(qū)域，并且覆蓋均勻，經(jīng)過計(jì)算，覆蓋率達(dá)到74.47%，本文提出的DPSO算法達(dá)到了很好的優(yōu)化效果。

Figure 6 Initial node deployment of WSN圖6 傳感器網(wǎng)絡(luò)初始節(jié)點(diǎn)部署

Figure 7 Node deployment after DPSO algorithm optimization圖7 DPSO算法優(yōu)化后的節(jié)點(diǎn)部署

為了進(jìn)一步分析DPSO算法的性能和覆蓋效果，本文選取了基本PSO算法和標(biāo)準(zhǔn)ABC算法與DPSO算法通過10次蒙特卡羅實(shí)驗(yàn)進(jìn)行對(duì)比。圖8是單次實(shí)驗(yàn)中使用PSO、ABC、DPSO算法對(duì)監(jiān)測(cè)區(qū)域進(jìn)行覆蓋優(yōu)化的過程對(duì)比。從圖8中可以看出，相比于PSO算法和ABC算法，本文所提出的DPSO算法能夠最快收斂，并且在迭代80次之后覆蓋率迅速提高。這歸功于對(duì)區(qū)域的Delaunay三角劃分能夠迅速鎖定傳感器網(wǎng)絡(luò)的絕對(duì)未覆蓋區(qū)域，并且在算法過程中產(chǎn)生的虛擬粒子同樣加快了DPSO算法的收斂速度，使得算法在迭代306次之后收斂且傳感器網(wǎng)絡(luò)最終的覆蓋率達(dá)到了74.47%。

Figure 8 Comparison of coverage among three algorithms圖8 3種算法覆蓋率對(duì)比

通過10次蒙特卡羅實(shí)驗(yàn)對(duì)比，從表1中可以看出，DPSO算法優(yōu)化得到的結(jié)果穩(wěn)定，10次實(shí)驗(yàn)覆蓋率的平均值可達(dá)75%以上，且覆蓋率相比于PSO和ABC分別提高了14.59%和4.13%，優(yōu)化效果優(yōu)于PSO算法和ABC算法。

除此之外，本文還在靜態(tài)節(jié)點(diǎn)數(shù)為30，動(dòng)態(tài)節(jié)點(diǎn)數(shù)不同的情況下對(duì)算法進(jìn)行了對(duì)比。從圖9中可以看出，當(dāng)動(dòng)態(tài)節(jié)點(diǎn)數(shù)為10時(shí)，PSO算法的覆蓋率為55.71%,DPSO算法的覆蓋率為61.21%；當(dāng)動(dòng)態(tài)節(jié)點(diǎn)數(shù)為20時(shí)，PSO算法的覆蓋率為62.59%,而DPSO算法的覆蓋率迅速上升到77.48%；當(dāng)動(dòng)態(tài)節(jié)點(diǎn)數(shù)為30時(shí)，PSO算法的覆蓋率為73.68%，而DPSO算法的覆蓋率為84.59%；當(dāng)動(dòng)態(tài)節(jié)點(diǎn)數(shù)為40時(shí)，PSO算法的覆蓋率為77.98%，而DPSO算法的覆蓋率超過90%達(dá)到90.64%；當(dāng)動(dòng)態(tài)節(jié)點(diǎn)數(shù)為50時(shí)，PSO算法的覆蓋率為83.35%,DPSO算法的覆蓋率為94.37%。由此可知，當(dāng)動(dòng)態(tài)節(jié)點(diǎn)的數(shù)目小于50時(shí)，相比于PSO算法，本文的DPSO算法擁有明顯較好的優(yōu)化效果；而當(dāng)動(dòng)態(tài)節(jié)點(diǎn)數(shù)目超過50時(shí)，算法之間的差異開始減小，覆蓋率皆可以達(dá)到85%以上。

Figure 9 Comparison of algorithm coverage with different dynamic node numbers圖9 動(dòng)態(tài)節(jié)點(diǎn)數(shù)不同時(shí)算法覆蓋率對(duì)比

6 結(jié)束語

在無線傳感器網(wǎng)絡(luò)的區(qū)域覆蓋優(yōu)化問題中，本文提出了一種基于Delaunay三角劃分策略的區(qū)域覆蓋優(yōu)化算法DPSO，解決了常規(guī)的計(jì)算幾何學(xué)難以應(yīng)用于概率感知模型的問題。仿真實(shí)驗(yàn)分析表明，本文提出的DPSO算法能夠快速定位傳感器網(wǎng)絡(luò)初始部署所存在的絕對(duì)未覆蓋區(qū)域，能夠修復(fù)區(qū)域中存在的漏洞使覆蓋率得以有效提高的同時(shí)保持節(jié)點(diǎn)間的良好通信。算法產(chǎn)生的虛擬粒子有效地加快了算法收斂速度，并且使得算法具有良好的穩(wěn)定性。但是，本文所提出的區(qū)域覆蓋優(yōu)化算法目前僅可以運(yùn)用于二維平面的場(chǎng)景，其使用范圍具有局限性。下一步將致力于研究算法在三維空間內(nèi)區(qū)域覆蓋優(yōu)化的運(yùn)用，使其擁有更多的應(yīng)用場(chǎng)景。

Table 1 Experiment results of different algorithms表1 不同算法實(shí)驗(yàn)結(jié)果對(duì)比 %