重采樣和天牛須協(xié)同演化粒子群的WSN覆蓋控制算法

王明華，姜開武，鄧賢君

(1.南華大學(xué) 超快微納技術(shù)與激光先進(jìn)制造湖南省重點(diǎn)實(shí)驗(yàn)室，湖南 衡陽(yáng) 421001；2.華中科技大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，武漢 430074；3.南華大學(xué) 核燃料循環(huán)技術(shù)與裝備湖南省協(xié)同創(chuàng)新中心，湖南 衡陽(yáng) 421001)

0 引 言

近年來，隨著無(wú)線通信技術(shù)和智能傳感器技術(shù)的發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks, WSN)引起了研究界和行業(yè)的極大關(guān)注[1-2]。WSN作為物聯(lián)網(wǎng)的支撐技術(shù)之一，負(fù)責(zé)信息感知和網(wǎng)絡(luò)終端傳輸[3]。傳感器節(jié)點(diǎn)具有感知環(huán)境、與鄰近節(jié)點(diǎn)通信和對(duì)所收集的數(shù)據(jù)進(jìn)行基本計(jì)算的特性，使WSN能在復(fù)雜或?qū)θ松碛泻Φ沫h(huán)境中運(yùn)行[4]。WSN得到廣泛應(yīng)用，包括健康監(jiān)控、污染處理、目標(biāo)跟蹤、數(shù)據(jù)保護(hù)和公共安全保障等[5-9]。與此同時(shí)，WSN在網(wǎng)絡(luò)連通性、節(jié)點(diǎn)利用率、網(wǎng)絡(luò)覆蓋率等方面也存在問題有待解決。不適合固定部署的復(fù)雜場(chǎng)景通常使用飛機(jī)空投或者其他隨機(jī)方法進(jìn)行部署，導(dǎo)致因節(jié)點(diǎn)分布不均而產(chǎn)生冗余覆蓋和覆蓋空洞[10]。這種隨機(jī)方式將導(dǎo)致節(jié)點(diǎn)密度過高，增大節(jié)點(diǎn)接收、處理和轉(zhuǎn)發(fā)的數(shù)據(jù)量，生成大量冗余數(shù)據(jù)，這些數(shù)據(jù)會(huì)阻塞通道并造成數(shù)據(jù)干擾，直接影響網(wǎng)絡(luò)的可靠性[11]。同樣，覆蓋空洞直接影響監(jiān)視的質(zhì)量。為了提高WSN監(jiān)控質(zhì)量并提高網(wǎng)絡(luò)可靠性、延長(zhǎng)網(wǎng)絡(luò)壽命，有必要確保節(jié)點(diǎn)部署能夠有效覆蓋目標(biāo)區(qū)域并降低網(wǎng)絡(luò)中節(jié)點(diǎn)的使用率。

文獻(xiàn)[12]提出基于改進(jìn)的人工魚群算法，在最大程度擴(kuò)大網(wǎng)絡(luò)覆蓋范圍的同時(shí)降低節(jié)點(diǎn)利用率，解決WSN覆蓋問題。文獻(xiàn)[13]提出基于遺傳算法(genetic algorithm, GA)的元啟發(fā)式方法來解決最大網(wǎng)絡(luò)生存期問題(maximum network lifetime problem, MLP)，但是沒有考慮網(wǎng)絡(luò)中冗余節(jié)點(diǎn)的情況。文獻(xiàn)[14]將WSN覆蓋問題歸納為整數(shù)的線性問題，提出3種近似算法解決該問題，分別為貪婪圓形節(jié)點(diǎn)放置(greedy round node placement, GRNP)、目標(biāo)保護(hù)節(jié)點(diǎn)放置(target protection node placement, TPNP)和節(jié)能節(jié)點(diǎn)放置(energy efficient node placement, EENP)。但是，在具有較大規(guī)模的目標(biāo)點(diǎn)時(shí)，問題會(huì)復(fù)雜得多，不能描述為整數(shù)的線性問題。文獻(xiàn)[15]提出并行分區(qū)式粒子群算法(improved particle swarm optimization, IWPSO)解決具有特征點(diǎn)集的優(yōu)化問題，但是也僅考慮了網(wǎng)絡(luò)中覆蓋率單一因素。文獻(xiàn)[16]將粒子濾波中的重采樣概念引入到粒子群算法(particle swarm optimization, PSO)中提出重采樣粒子群算法(resampling PSO, RPSO)，該算法在優(yōu)化WSN覆蓋控制問題有良好的效果，但忽視了單個(gè)粒子的搜索能力。文獻(xiàn)[17]提出天牛須粒子群算法(beetle antennae search PSO, BASPSO)解決WSN覆蓋問題，但是該算法僅考慮了覆蓋率因素，沒有進(jìn)行基準(zhǔn)函數(shù)測(cè)試。

為提高隨機(jī)部署方式下WSN的覆蓋率和網(wǎng)絡(luò)節(jié)點(diǎn)休眠率，降低WSN在運(yùn)行時(shí)的能耗，在粒子濾波中的重采樣技術(shù)和天牛須搜索的啟發(fā)下，本文將重采樣過程和天牛須搜索的協(xié)同演化融入粒子群優(yōu)化中，提出了一種新的優(yōu)化算法，稱為重采樣和天牛須協(xié)同演化的粒子群算法(resampling BASPSO, RBASPSO)。重采樣過程與天牛須策略的協(xié)同演化既提升了搜索過程中粒子群整體多樣性，也加強(qiáng)了粒子群中單個(gè)粒子搜索鄰域的能力。在測(cè)試該算法收斂性時(shí)，使用了10個(gè)CE2005優(yōu)化基準(zhǔn)函數(shù)來進(jìn)行評(píng)估，同時(shí)將該算法應(yīng)用于WSN覆蓋優(yōu)化。WSN覆蓋控制建模由網(wǎng)絡(luò)覆蓋率和節(jié)點(diǎn)休眠率的加權(quán)和函數(shù)構(gòu)成，利用所提算法可尋求最佳節(jié)點(diǎn)部署方案。

1 覆蓋問題描述

無(wú)線傳感器網(wǎng)絡(luò)的典型應(yīng)用之一是在危險(xiǎn)或人類不可接近的區(qū)域進(jìn)行監(jiān)視和收集信息，在這類情況下只能選擇飛機(jī)空投等隨機(jī)方式進(jìn)行無(wú)線傳感器的部署[18]。傳感器節(jié)點(diǎn)部署在二維檢測(cè)區(qū)域中，并且有以下特性。

1)節(jié)點(diǎn)的密度足夠大。如果所有節(jié)點(diǎn)都工作，不僅可以保證覆蓋的質(zhì)量要求，而且具有大量的休眠節(jié)點(diǎn)。

2)網(wǎng)絡(luò)中節(jié)點(diǎn)都具有相同的感知半徑rs。

3)檢測(cè)區(qū)域遠(yuǎn)大于節(jié)點(diǎn)覆蓋范圍，以致于可忽略邊界效應(yīng)。

1.1 傳感器覆蓋模型

在本文的研究中，傳感器節(jié)點(diǎn)部署于二維檢測(cè)區(qū)域，傳感器覆蓋模型選擇經(jīng)典布爾感知模型。布爾感知模型的機(jī)理如下：在節(jié)點(diǎn)Si的覆蓋圓中，所有目標(biāo)點(diǎn)的監(jiān)視概率為1，而圓外點(diǎn)監(jiān)視概率為0。設(shè)節(jié)點(diǎn)Si的坐標(biāo)為(xi,yi)，傳感器感測(cè)半徑是rs，網(wǎng)絡(luò)任意目標(biāo)點(diǎn)(x,y)被感知的概率為

(1)

(1)式中：x和y為網(wǎng)絡(luò)中目標(biāo)點(diǎn)位置坐標(biāo)。

1.2 網(wǎng)絡(luò)覆蓋模型

為有效評(píng)估WSN的覆蓋，將感興趣區(qū)域分為網(wǎng)格形式，表示為G(c,r)，其中c和r分別代表網(wǎng)格行和列的數(shù)量。在評(píng)估覆蓋率時(shí)，網(wǎng)格被轉(zhuǎn)換成點(diǎn)。如果某個(gè)節(jié)點(diǎn)沒有覆蓋任務(wù)，則設(shè)置為睡眠狀態(tài)，以減少能量消耗，直到該節(jié)點(diǎn)有覆蓋任務(wù)為止。只有當(dāng)節(jié)點(diǎn)有覆蓋任務(wù)時(shí)，才將其設(shè)置為活動(dòng)狀態(tài)。無(wú)線傳感器網(wǎng)絡(luò)覆蓋模型描述如下：以網(wǎng)格中心點(diǎn)為目標(biāo)點(diǎn)，將監(jiān)測(cè)區(qū)域分散到c×rm*n網(wǎng)格中。

定義節(jié)點(diǎn)Si覆蓋點(diǎn)的概率為Pi，這個(gè)概率只有1或者0兩種情況。網(wǎng)絡(luò)中目標(biāo)點(diǎn)(x,y)(x,y)被節(jié)點(diǎn)集S覆蓋的公式為

(2)

WSN覆蓋示意圖如圖1所示。

圖1中，“1”表示該網(wǎng)格被覆蓋，“0”則意味是覆蓋空洞。圖1中標(biāo)記為1的數(shù)量有13個(gè)，則覆蓋率為52%。

將感興趣區(qū)域目標(biāo)點(diǎn)進(jìn)行編號(hào)，假設(shè)有10 000個(gè)目標(biāo)點(diǎn)，則每個(gè)點(diǎn)被覆蓋的概率為

(3)

此時(shí)，傳感器網(wǎng)絡(luò)的覆蓋率FCOV也可表示為

(4)

休眠傳感器的函數(shù)可以表示為

(5)

(5)式中：na是有覆蓋任務(wù)的節(jié)點(diǎn)數(shù)；n是部署的節(jié)點(diǎn)總數(shù)。

本文優(yōu)化目標(biāo)是在最大限度擴(kuò)大網(wǎng)絡(luò)覆蓋范圍的同時(shí)增大網(wǎng)絡(luò)節(jié)點(diǎn)休眠率，以達(dá)到延長(zhǎng)網(wǎng)絡(luò)生命周期和減少能量消耗的目的，目標(biāo)函數(shù)采用線性加權(quán)法將函數(shù)FCOV與節(jié)點(diǎn)休眠率FRE結(jié)合[16]。

Ffit=αFCOV+βFRE

(6)

(6)式中，α和β是函數(shù)FCOV和FRE的權(quán)重，且α+β=1，其默認(rèn)取值為α=0.8，β=0.2。

2 重采樣和天牛須協(xié)同演化粒子群算法

2.1 PSO的原始版本

PSO是一種群體智能優(yōu)化算法。單個(gè)粒子i由當(dāng)前位置xi、先前的最佳位置pi和速度vi等3個(gè)D維變量組成，其中D是搜索空間的維數(shù)[19]。在每次迭代中，可以將當(dāng)前位置xi視為當(dāng)前問題的解決方案，并且到目前為止的最佳解決方案存儲(chǔ)在pi中。該算法通過調(diào)整vi來更新粒子速度和位置。

vi(t+1)=wvi(t)+c1r1[pi-xi(t)]+

c2r2[pg-xi(t)]

(7)

xi(t+1)=xi(t)+vi(t+1)

(8)

(7)—(8)式中：w是慣性權(quán)重；r1和r2是生成的獨(dú)立隨機(jī)數(shù)；c1和c2為加速度系數(shù)，決定個(gè)人最佳pi和鄰域最佳pg方向上的隨機(jī)力的大小。

使PSO搜索更加穩(wěn)定的方式有兩種：1)選擇適當(dāng)?shù)膚以及c1和c2；2)設(shè)置一個(gè)較大的vmax值約束粒子速度。然而慣性權(quán)重w不能平衡全局勘探和局部開采，而且求解一個(gè)最佳vmax比較困難。因此，為更好地平衡全局勘探和局部開采的愿望并降低vmax的重要性，本文采用Clerc收縮因子γ對(duì)速度更新公式改寫為[20]

vi(t+1)=γ{vi(t)+c1r1[pi-xi(t)]+

c2r2[pg-xi(t)]}

(9)

(10)

(10)式中，ρ=c1+c2>4。當(dāng)采用Clerc收縮法時(shí)，通常將設(shè)ρ為4.1，c1=c2=2.05，收縮因子γ約為0.729 84。采用Clerc收縮后的粒子能在不使用vmax的情況下收斂，其效果類似于慣性權(quán)重的效果，導(dǎo)致群體行為最終被限制在包含最知名解的可行搜索空間的小區(qū)域內(nèi)。

PSO搜索性能較差，主要表現(xiàn)在兩個(gè)方面：①在迭代計(jì)算中粒子會(huì)朝著一個(gè)局部最優(yōu)值附近聚集，如果沒有外界干擾，粒子將陷入一個(gè)較差質(zhì)量的谷底始終不能逃逸；②粒子位置更新導(dǎo)致粒子一直在最優(yōu)解附近搜索，無(wú)法搜索到它的鄰域。本文所提RBASPSO算法的重采樣與天牛須協(xié)同演化過程主要解決這兩個(gè)問題。

2.2 重采樣過程

為有效解決粒子群算法在迭代過程中粒子多樣性問題，在引入粒子濾波的重采樣時(shí)將權(quán)重值極低的粒子重采樣為高質(zhì)量的新粒子，以提高算法搜索精度，同時(shí)消除不必要的搜索時(shí)間。如果在迭代過程中滿足重采樣的標(biāo)準(zhǔn)，則執(zhí)行重采樣過程，引入重采樣的標(biāo)準(zhǔn)是粒子聚集度(particle aggregation degree, PAD)是否大于臨界值。

(11)

(12)

(11)—(12)式中：N是粒子數(shù)；D是問題的維數(shù)；DISi表示粒子i到中心坐標(biāo)的距離；xij表示第i粒子的第j維位置；yj是中心點(diǎn)j維的中心坐標(biāo)值，在搜索空間中隨機(jī)生成。PAD表征了粒子種群多樣性。PAD值越低，粒子分布越分散，種群多樣性越好。

當(dāng)粒子聚集度大于臨界值，即PAD>PADt時(shí)，需要對(duì)粒子群進(jìn)行重采樣。假定優(yōu)化問題的函數(shù)滿足高斯分布，此時(shí)粒子i的權(quán)重值為

(13)

(13)式中：qi是i賦予粒子的權(quán)重值；F(x)是適應(yīng)度函數(shù)；pg代表當(dāng)前的全局最優(yōu)值；σ是F(xi)-pg的樣本方差。

然后歸一化qi, 粒子i的單位權(quán)重值為

(14)

粒子權(quán)重值qt的門限值qt為

(15)

對(duì)每個(gè)粒子，如果qi

(16)

(17)

xi(t+1)=xi(t)*+λ

(18)

(19)

(18)—(19)式中：x(i)*表示當(dāng)前的最優(yōu)解；norm(u,μ)是具有均值u和方差μ的高斯隨機(jī)數(shù)。

2.3 天牛須搜索過程

為了提高粒子群中單個(gè)粒子的鄰域搜索能力從而提高整體搜索能力，引入天牛須搜索。對(duì)于一個(gè)D維空間的優(yōu)化問題，用xl表示左邊須坐標(biāo)值，xr表示右邊須坐標(biāo)值，x表示天牛質(zhì)心坐標(biāo)，d0表示觸角間距。天牛質(zhì)心朝向是問題D維中的任意方向，因而天牛兩觸角的朝向也是在D維中任意的，可以產(chǎn)生一個(gè)隨機(jī)向量dir=rands(D,1)來表示它。

計(jì)算左右兩觸角的適應(yīng)度值為

Fleft=f(xl)

(20)

Fright=f(xr)

(21)

x=x-step×dir×sign(Fleft-Fright)

(22)

(22)式中：步長(zhǎng)step的初始值為step=c×d0,c是常數(shù)；step隨算法運(yùn)行輪數(shù)更新，step=step×τ，τ為天牛須步長(zhǎng)的收斂因子。

天牛須策略使粒子在移動(dòng)過程中，會(huì)對(duì)下一步的左右方向進(jìn)行預(yù)判，加強(qiáng)粒子鄰域搜索能力，從而有效避免粒子陷入局部最優(yōu)解。

2.4 算法執(zhí)行過程

重采樣技術(shù)和BAS過程的協(xié)同演化中，首先，對(duì)粒子群進(jìn)行聚集度檢測(cè)。在聚集度過高時(shí)采用重采樣技術(shù)與BAS的協(xié)同演化，將當(dāng)前粒子權(quán)重值過小的粒子重采樣并使用天牛須搜索確定當(dāng)前粒子的最優(yōu)位置。其次，為了減少不必要的計(jì)算量，在PAD滿足要求時(shí)僅需采用天牛須搜索確定天牛(粒子)的更新。需注意的是，采用BAS更新粒子位置的前提是所更新的位置優(yōu)于原來的位置。最后，依據(jù)粒子群的速度和位置的更新完成迭代工作。

由于RBASPSO中每個(gè)粒子都是WSN覆蓋問題的一個(gè)解決方案，而每個(gè)粒子攜帶有N個(gè)節(jié)點(diǎn)信息。用xi(t)表示粒子i在第t次迭代時(shí)的節(jié)點(diǎn)位置信息的集合，即xi=(xi1,yi1,xi2,yi2,…,xiN,yiN)。xi(t)中各元素依次代表節(jié)點(diǎn)1到N的橫縱坐標(biāo)，它所經(jīng)歷的最好位置為pbest=max(pi1,pi2,…,piN)，而所有粒子經(jīng)歷的最好位置為gbest。

算法在執(zhí)行時(shí)，每輪都將選擇具有最大目標(biāo)函數(shù)值的覆蓋方案，通過該方案來收集節(jié)點(diǎn)位置信息，將網(wǎng)絡(luò)中有覆蓋任務(wù)的節(jié)點(diǎn)設(shè)置為工作狀態(tài)，沒有任務(wù)的節(jié)點(diǎn)設(shè)置為睡眠狀態(tài)。RBASPSO算法尋求最佳部署方案的過程如下。

步驟1參數(shù)設(shè)置。如種群規(guī)模、問題維度、天牛須長(zhǎng)度等，初始化種群位置和速度。

步驟2計(jì)算當(dāng)前粒子群聚集度PAD。如果PAD大于閾值PADt，則進(jìn)入下一步；反之進(jìn)入步驟6。

步驟3計(jì)算每個(gè)粒子的權(quán)重值qi并歸一化為Qi與權(quán)重值的平均值qt進(jìn)行比較，如果Qi

步驟4根據(jù)(16)—(17)式重采樣該粒子，賦予新的位置量和速度信息。

步驟5將每個(gè)粒子看作天牛，按(22)式進(jìn)行天牛須搜索。如果搜索位置優(yōu)于之前位置，則保留；反之，不更新粒子位置信息。

步驟6根據(jù)(8)—(9)式更新粒子的速度和位置信息。

步驟7計(jì)算當(dāng)前粒子適應(yīng)度值，更新pbest和gbest。

步驟8判斷是否滿足終止條件。不滿足，返回步驟2；否則，結(jié)束并輸出最大值和gbest。

2.5 收斂性測(cè)試和算法時(shí)間復(fù)雜度分析

2.5.1 收斂性測(cè)試

將求解的問題分為單峰問題和復(fù)雜多峰問題，從有效性和效率的角度來檢驗(yàn)RBASPSO算法的性能，基準(zhǔn)函數(shù)如表1所示。表1中f1和f2是簡(jiǎn)單單峰問題；f3和f4是低維多峰問題；f5-f10是具有大量復(fù)雜極小值的復(fù)雜多峰問題?；鶞?zhǔn)函數(shù)的最優(yōu)值、可行范圍和設(shè)置的初始范圍如表2所示，基準(zhǔn)函數(shù)測(cè)試結(jié)果如表3所示。

表1 基準(zhǔn)函數(shù)列表Tab.1 Benchmark functions

表2 基準(zhǔn)函數(shù)參數(shù)Tab.2 Parameters of the benchmark function

表3的數(shù)據(jù)為各算法在迭代尋優(yōu)10 000次所得。在處理f1和f2這樣的簡(jiǎn)單單峰問題時(shí)，不會(huì)有被困在低質(zhì)量峰值的潛在威脅，所提算法的收斂性比PSO提高了1～8個(gè)數(shù)量級(jí)不等，比只使用單個(gè)策略的RPSO和BASPSO算法提高了1～5個(gè)數(shù)量級(jí)，如圖2所示。由于函數(shù)f3和f4只有兩個(gè)變量，且搜索空間相對(duì)較小，各算法都能快速搜索到最優(yōu)值，算法沒有改進(jìn)空間，故這里不展示函數(shù)f3和f4的搜索過程。

圖2 函數(shù)f1和f2收斂性Fig.2 Convergence of f1and f2

對(duì)于多峰問題，從表3中f5-f10的結(jié)果可以看出，在處理多峰優(yōu)化問題時(shí)，RBASPSO算法的收斂精度有明顯的優(yōu)勢(shì)；在處理復(fù)雜多峰優(yōu)化問題時(shí)，RBASPSO算法比BASPSO、RPSO和PSO算法的收斂速度和精度均有明顯提升，其中搜索精度提升1～8個(gè)數(shù)量級(jí)不等，如圖3所示。以函數(shù)f9為例，RBASPSO算法比RPSO和BASPSO算法搜索精度分別提升1個(gè)和4個(gè)數(shù)量級(jí)。這是由于搜索空間存在一些狹窄的間隙，粒子容易陷入質(zhì)量低的谷底不能逃出，而重采樣技術(shù)和天牛須搜索都提高了粒子逃逸谷底的能力。

圖3 函數(shù)f5-f10的收斂性Fig.3 Convergence of f5-f10

表3 收斂性測(cè)試結(jié)果Tab.3 Results of convergence test

通過對(duì)這兩類問題的測(cè)試和分析可得出這樣的結(jié)論：RBASPSO算法能提高處理簡(jiǎn)單單峰問題的能力，在處理復(fù)雜而且高維的多峰優(yōu)化問題上優(yōu)于RPSO和BASPSO算法。

2.5.2 算法時(shí)間復(fù)雜度分析

顯而易見，PSO的時(shí)間復(fù)雜度最低，但是收斂精度和速度的性能最差；RBASPSO算法引入重采樣技術(shù)和天牛須搜索，增加了算法時(shí)間復(fù)雜度，但是極大增強(qiáng)了算法的收斂速度和收斂精度。

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

將監(jiān)測(cè)區(qū)域設(shè)置為100×100 m，節(jié)點(diǎn)感知半徑rs為9 m；分析不同節(jié)點(diǎn)數(shù)量下，適應(yīng)度函數(shù)Ffit、覆蓋率FCOV和休眠率FRE的變化情況。隨機(jī)部署40個(gè)靜態(tài)傳感器節(jié)點(diǎn)，然后持續(xù)遞增20個(gè)傳感器，一直增加到120，分析不同節(jié)點(diǎn)數(shù)量下優(yōu)化結(jié)果的差異性。先對(duì)優(yōu)化過程中傳感器的狀態(tài)進(jìn)行分析，再對(duì)適應(yīng)度函數(shù)以及網(wǎng)絡(luò)覆蓋率和節(jié)點(diǎn)休眠率進(jìn)行對(duì)比。

3.1 傳感器節(jié)點(diǎn)的狀態(tài)

網(wǎng)絡(luò)中傳感器的狀態(tài)在具有最佳節(jié)點(diǎn)部署方案中求得。隨著迭代次數(shù)增加，傳感器節(jié)點(diǎn)的重合次數(shù)減少而覆蓋率逐漸增加，最終收斂到最大值。圖4展示了RBASPSO算法在不同迭代次數(shù)時(shí)傳感器節(jié)點(diǎn)的狀態(tài)。圖4中，傳感器數(shù)量為60，t為迭代次數(shù)。圖5展示了不同算法在迭代100次時(shí)傳感器節(jié)點(diǎn)的狀態(tài)，也就是算法所搜索到的最大目標(biāo)函數(shù)值時(shí)對(duì)應(yīng)的節(jié)點(diǎn)狀態(tài)以及覆蓋率情況，圖5中傳感器數(shù)量為100。

圖4 RBASPSO算法在不同迭代次數(shù)時(shí)傳感器節(jié)點(diǎn)的狀態(tài)Fig.4 State of the sensor node at different iterations of RBASPSO algorithm

圖5 不同算法在迭代100次時(shí)傳感器節(jié)點(diǎn)的狀態(tài)Fig.5 State of sensor nodes when different algorithms are iterated 100 times

由圖4可見，在迭代100次時(shí)，網(wǎng)絡(luò)覆蓋率對(duì)比迭代1次、30次和50次分別提升了約9.423%、2.153%和0.858%。同時(shí)也可以發(fā)現(xiàn)，算法在迭代1～30次時(shí)，收斂速度很快；而在迭代到30～50次時(shí)，收斂速度有所減少；到50～100次時(shí)，收斂速度明顯減緩。

由圖5可見，迭代100次時(shí)，RBASPSO算法在覆蓋率方面比PSO、RPSO和BASPSO算法分別提升了約3.33%、3.232%和2.474%；覆蓋率更大，節(jié)點(diǎn)分布更均勻，網(wǎng)絡(luò)布局也更合理。

3.2 適應(yīng)度函數(shù)的變化

圖6展示了目標(biāo)函數(shù)Ffit的最大值隨節(jié)點(diǎn)數(shù)量變化的關(guān)系。由圖6可見，RBASPSO算法在節(jié)點(diǎn)數(shù)為40時(shí)Ffit值約為0.59，隨著節(jié)點(diǎn)數(shù)目的增加，F(xiàn)fit的最大值也隨之增加；在節(jié)點(diǎn)數(shù)目為120時(shí)，F(xiàn)fit的最大值增加到約為0.889。顯然，在不同節(jié)點(diǎn)數(shù)量下本文方法均優(yōu)于其他算法。

圖6 適應(yīng)度函數(shù)與節(jié)點(diǎn)數(shù)的關(guān)系Fig.6 Relationship between fitness function and the number of nodes

圖7展示了4種不同節(jié)點(diǎn)數(shù)時(shí)不同算法的收斂性能。從圖7可以看出，RBASPSO算法在提升目標(biāo)函數(shù)值上明顯更優(yōu)，在節(jié)點(diǎn)數(shù)為80時(shí)尤其如此。對(duì)比其它3個(gè)算法，RBASPSO算法目標(biāo)函數(shù)值提升了3.256%以上。收斂速度方面，各算法都是在迭代計(jì)算1～40時(shí)搜索性能更好；RPSO和BASPSO算法在迭代40之后收斂速度趨于平緩，甚至停滯不前。顯然，重采樣和天牛須協(xié)同演化增強(qiáng)了RBASPSO算法的搜索性能，使得該算法在迭代1～40次時(shí)具有更高的收斂精度；在迭代40次之后依然有往更優(yōu)值搜索的趨勢(shì)。

圖7 不同節(jié)點(diǎn)數(shù)的收斂情況Fig.7 Convergence of fitness function at different numbers of nodes

3.3 WSN覆蓋指標(biāo)分析

3.3.1 網(wǎng)絡(luò)覆蓋率

評(píng)估網(wǎng)絡(luò)性能時(shí)，最重要的指標(biāo)是覆蓋率。網(wǎng)絡(luò)覆蓋率和節(jié)點(diǎn)休眠率都在最大目標(biāo)函數(shù)值求得。

圖8展示了網(wǎng)絡(luò)覆蓋率與節(jié)點(diǎn)數(shù)的關(guān)系。從圖8可見，RBASPSO算法在各個(gè)節(jié)點(diǎn)數(shù)量下的最大覆蓋率都更高。在節(jié)點(diǎn)數(shù)為40時(shí)覆蓋率比BASPSO、RPSO和PSO分別提升了4.2%、6.7%和7.1%。隨著傳感器數(shù)量的增加，該算法覆蓋率比次優(yōu)的BASPSO算法在節(jié)點(diǎn)數(shù)為60、80、100和120時(shí)分別提升了2.6%、2.9%、2.2%和1.1%。由此可知，在節(jié)點(diǎn)密度較小時(shí)，覆蓋率提升較快；在節(jié)點(diǎn)密度很大時(shí)，覆蓋率的提升逐漸趨緩。

圖8 覆蓋率與節(jié)點(diǎn)數(shù)的關(guān)系Fig.8 Relationship between coverage and number of nodes

圖9展示了不同節(jié)點(diǎn)數(shù)量下函數(shù)FCOV隨迭代次數(shù)增加的收斂情況。圖9列舉了4種不同節(jié)點(diǎn)數(shù)的覆蓋率收斂情況。由圖9可見，RBASPSO算法的收斂速度和精度明顯更優(yōu)。

圖9 不同節(jié)點(diǎn)數(shù)時(shí)覆蓋率的收斂情況Fig.9 Convergence of coverage rate under different number of nodes

以節(jié)點(diǎn)數(shù)40為例，4個(gè)算法中，RBASPSO算法收斂速度和精度最優(yōu)，BASPSO算法次優(yōu)。對(duì)比BASPSO和RPSO算法，RBASPSO算法在覆蓋率方面提升了約3.27%和6.67%。

3.3.2 節(jié)點(diǎn)休眠率

WSN在滿足覆蓋率要求的同時(shí)，也要保證網(wǎng)絡(luò)中有休眠節(jié)點(diǎn)以供隨時(shí)替換失效的節(jié)點(diǎn)。圖10展示了節(jié)點(diǎn)休眠率與節(jié)點(diǎn)數(shù)的關(guān)系。

圖10 休眠率與節(jié)點(diǎn)數(shù)的關(guān)系Fig.10 Relationship between sleep rate and number of nodes

由圖10可見，節(jié)點(diǎn)數(shù)量為60和70時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)休眠率比較低并且所提算法比其它3個(gè)算法稍差一點(diǎn)。這是由于區(qū)域中傳感器數(shù)量較少，RBASPSO算法在完成高覆蓋率時(shí)犧牲了部分傳感器數(shù)量。隨著節(jié)點(diǎn)數(shù)量的增加，RBASPSO算法下的節(jié)點(diǎn)休眠率隨之增加并且優(yōu)于BASPSO和RPSO。在節(jié)點(diǎn)數(shù)量為80時(shí)，本文算法比這兩個(gè)算法在休眠率方面提升了0.84%到4.42%。

4 結(jié) 論

本文圍繞WSN的覆蓋率和節(jié)點(diǎn)休眠率兩個(gè)關(guān)鍵問題，提出基于重采樣技術(shù)和天牛須協(xié)同演化的粒子群算法。該算法解決了PSO在搜索過程中粒子多樣性不足和個(gè)體的搜索能力較差的問題，有效提升了算法搜索性能。基準(zhǔn)函數(shù)測(cè)試和WSN實(shí)驗(yàn)結(jié)果證明，本文算法能有效處理單峰和復(fù)雜多峰優(yōu)化問題，提高網(wǎng)絡(luò)覆蓋率和節(jié)點(diǎn)休眠率，延長(zhǎng)網(wǎng)絡(luò)生命周期，從而獲得更優(yōu)的節(jié)點(diǎn)部署方案。