張 晶，魏 淼

(1.昆明理工大學信息工程與自動化學院，云南 昆明 650500;2.云南梟潤科技服務有限公司，云南 昆明 650500;3.昆明理工大學云南省人工智能重點實驗室，云南 昆明 650500;4.昆明理工大學云南省計算機技術(shù)應用重點實驗室，云南 昆明 650500)

1 引言

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

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

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

2 傳感器覆蓋模型

2.1 概率感知模型

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

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

(1)

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

2.2 區(qū)域覆蓋率

假設(shè)被監(jiān)測區(qū)域為一個m×n的二維方形區(qū)域，目標監(jiān)測點的個數(shù)為M，無線傳感器節(jié)點個數(shù)為N。

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

(2)

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

(3)

3 相關(guān)算法

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

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

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

Step2計算粒子的適應度值。

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

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

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

(4)

(5)

3.2 人工蜂群算法

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

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

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

(6)

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

4 DPSO算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1.3 確定Delaunay三角形形心

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

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

(7)

(8)

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

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

4.2.1 個體粒子搜索能力增強

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

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

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

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

本文所提出的改進PSO算法流程如下所示：

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

Step2計算粒子的適應度值。

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

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

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

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

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

4.3 DPSO算法流程

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

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

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

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

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

Step5計算粒子的適應度值。

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

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

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

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

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

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

5 仿真實驗

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

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

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

(9)

5.2 實驗及結(jié)果分析

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

Table 1 Experiment results of different algorithms表1 不同算法實驗結(jié)果對比 %