基于模糊粒子群優(yōu)化算法的無(wú)線傳感器網(wǎng)絡(luò)部署優(yōu)化研究

張 亮， 黃 郡

(國(guó)防科技大學(xué) 電子對(duì)抗學(xué)院，安徽 合肥 230037)

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)目前已經(jīng)被廣泛應(yīng)用到煤礦安全監(jiān)測(cè)、生態(tài)環(huán)境監(jiān)測(cè)、戰(zhàn)場(chǎng)態(tài)勢(shì)感知等眾多領(lǐng)域[1]。網(wǎng)絡(luò)一般由多個(gè)無(wú)線傳感器節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)配備有相應(yīng)的感知單元、通信單元和能量單元。如何利用這些節(jié)點(diǎn)構(gòu)建一個(gè)結(jié)構(gòu)合理、性能優(yōu)良的網(wǎng)絡(luò)，也即無(wú)線傳感器網(wǎng)絡(luò)的優(yōu)化部署問(wèn)題是目前的一個(gè)研究熱點(diǎn)。無(wú)線傳感器網(wǎng)絡(luò)的部署方法可以分為靜態(tài)部署和動(dòng)態(tài)部署[2]。靜態(tài)部署指的是在傳感器網(wǎng)絡(luò)運(yùn)行之前就已經(jīng)確定各個(gè)節(jié)點(diǎn)的位置，動(dòng)態(tài)部署則是在傳感器網(wǎng)絡(luò)運(yùn)行之后還可根據(jù)實(shí)際情況進(jìn)行節(jié)點(diǎn)移動(dòng)等位置調(diào)整。靜態(tài)部署又可分為確定性部署和隨機(jī)性部署。確定性部署指的是通過(guò)最優(yōu)化模型確定傳感器節(jié)點(diǎn)的最優(yōu)部署位置，然后將節(jié)點(diǎn)部署到指定位置。隨機(jī)性部署則是將傳感器節(jié)點(diǎn)隨機(jī)拋灑到目標(biāo)區(qū)域，然后運(yùn)用一定的優(yōu)化算法選擇部分節(jié)點(diǎn)參與構(gòu)建網(wǎng)絡(luò)。與確定性部署相比，隨機(jī)性部署能夠適應(yīng)目標(biāo)區(qū)域環(huán)境惡劣，難以人工到達(dá)的場(chǎng)合。

目前針對(duì)無(wú)線傳感器網(wǎng)絡(luò)的部署問(wèn)題，研究人員提出了多種解決方法。劉雨博等人利用人工魚(yú)群算法對(duì)光纖應(yīng)變傳感網(wǎng)絡(luò)的優(yōu)化部署進(jìn)行了研究，證明優(yōu)化部署后的結(jié)果網(wǎng)絡(luò)能夠比人工隨機(jī)部署更接近真實(shí)值[3]。朱明基于正六邊形網(wǎng)格劃分，提出了一種變步長(zhǎng)節(jié)點(diǎn)動(dòng)態(tài)部署方法，可有效延長(zhǎng)網(wǎng)絡(luò)的存活時(shí)間[4]。Kulkarni N等人借鑒了確定性部署和隨機(jī)性部署的思想，提出了一種類隨機(jī)序列的方法，并對(duì)網(wǎng)絡(luò)的丟包率、平均耗能量、時(shí)延等指標(biāo)在不同的部署方法下的影響情況進(jìn)行了分析[5]。Fang W等人基于有效克服部署區(qū)域空洞的思想，利用空洞維諾圖，分別提出了基于空洞中心的部署方法和基于擾動(dòng)中心的部署方法，取得了較好的目標(biāo)區(qū)域覆蓋率[6]。

本文研究隨機(jī)性部署方法，在標(biāo)準(zhǔn)粒子群優(yōu)化算法的基礎(chǔ)上，通過(guò)引入模糊數(shù)學(xué)的基本思想，并構(gòu)造調(diào)和覆蓋率和節(jié)點(diǎn)數(shù)量之間的目標(biāo)函數(shù)，可實(shí)現(xiàn)在使用較少節(jié)點(diǎn)數(shù)的同時(shí)，達(dá)到較高的區(qū)域覆蓋率。

1 問(wèn)題建模

假定需要覆蓋的區(qū)域是A，依據(jù)網(wǎng)格法，可以將區(qū)域A劃為m×n個(gè)網(wǎng)格，A={a1,a2,…,amn}，劃分網(wǎng)格的寬度取決于傳感器節(jié)點(diǎn)的感知半徑r以及所需要達(dá)到的計(jì)算精度。傳感器節(jié)點(diǎn)的通信半徑為R，參照大部分文獻(xiàn)[2]，設(shè)定R≥2r。現(xiàn)在有N個(gè)傳感器節(jié)點(diǎn)(S1,S2,…,SN)被拋撒到目標(biāo)區(qū)域A，第i(1≤i≤N)個(gè)傳感器節(jié)點(diǎn)的位置是(xi,yi)。第j(1≤j≤N)個(gè)網(wǎng)格的中心為(xj,yj)，則第i個(gè)傳感器Si到第j個(gè)網(wǎng)格aj的距離d(Si,aj)是

(1)

此時(shí)，傳感器Si對(duì)網(wǎng)格aj的感知概率是

(2)

如果考慮噪聲干擾、傳感器特性等因素，可以取感知概率為[4]

(3)

式中re為傳感器節(jié)點(diǎn)可測(cè)得的不確定度，α1，α2，β1，β2為節(jié)點(diǎn)的特異性參數(shù)。λ1，λ2的計(jì)算公式為

(4)

考慮到所有可能的傳感器節(jié)點(diǎn)，網(wǎng)格aj被感知的聯(lián)合概率P(aj)為

(5)

由于目標(biāo)區(qū)域A被劃分為m×n個(gè)網(wǎng)格，因此區(qū)域A的覆蓋率P(A)可以計(jì)算為

(6)

式中P′(aj)為截?cái)嗷怕?，?jì)算公式為

(7)

在本文中，Pth取值為1，P(Si,aj)的計(jì)算使用式(2)。

設(shè)計(jì)網(wǎng)絡(luò)優(yōu)化部署的目標(biāo)函數(shù)為

(8)

式中Seli為第i個(gè)傳感器節(jié)點(diǎn)是否被選中構(gòu)建網(wǎng)絡(luò)。當(dāng)其為1時(shí)，表示選中；為0，表示沒(méi)有被選中。式(8)表示在盡量求得較高網(wǎng)絡(luò)覆蓋率的同時(shí)，保證所需傳感器數(shù)量較少。為了消除P(A)取值為0對(duì)除法的影響，并且保證式(8)上下兩部分處在一個(gè)數(shù)量范圍內(nèi)，將其變換為

(9)

此時(shí)問(wèn)題轉(zhuǎn)換為：如何決定哪些傳感器參與構(gòu)建網(wǎng)絡(luò)，從而使得f取得最小值，下面描述該問(wèn)題的求解算法。

2 基于模糊粒子群優(yōu)化算法的問(wèn)題求解

2.1 符號(hào)定義

所有傳感器的集合使用S集合進(jìn)行表示，S={S1,S2,…,SN}。其中：Si=(x,y,sel)，(x,y)代表第i個(gè)傳感器節(jié)點(diǎn)的坐標(biāo)，sel代表該節(jié)點(diǎn)是否被選中參與構(gòu)建網(wǎng)絡(luò)。

所有的粒子集合使用X表示，X={X1,X2,…,XP}，P表示候選的粒子數(shù)量。每個(gè)粒子X(jué)i表示問(wèn)題的一個(gè)可能解，它是一個(gè)N維變量，Xi=Xi1Xi2…XiN。Xij表示第i個(gè)粒子中第j個(gè)傳感器是否參與構(gòu)建傳感器網(wǎng)絡(luò)。

粒子集合對(duì)應(yīng)的速度集合為V，V={V1,V2,…,VP}，Vi=Vi1Vi2…ViN，代表第i個(gè)粒子在各個(gè)維度上的速度。

2.2 模糊粒子表示

模糊理論目前已經(jīng)被應(yīng)用于降水粒子分類[7]、SAR影像變化檢測(cè)[8]等眾多領(lǐng)域，取得了較好的應(yīng)用效果。傳統(tǒng)的集合使用硬規(guī)則描述某個(gè)元素a與集合U的關(guān)系，即a要么屬于U，要么不屬于。在模糊集理論中，存在一個(gè)隸屬度函數(shù)μ。該函數(shù)將每個(gè)元素a對(duì)應(yīng)到一個(gè)隸屬度值μa(U)。該值取值范圍為[0,1]，用于描述a歸屬于U的概率。對(duì)應(yīng)于本文所設(shè)計(jì)的算法中，粒子X(jué)i的每個(gè)分量在迭代更新過(guò)程中，也用于描述對(duì)應(yīng)位置的傳感器參與構(gòu)建網(wǎng)絡(luò)的隸屬程度。但為了滿足粒子能夠在較大的空間范圍內(nèi)搜索，避免陷入局部最優(yōu)值，本文在更新粒子位置的過(guò)程中，并沒(méi)有限定Xi在[0,1]內(nèi)，而是在利用該粒子計(jì)算適應(yīng)度函數(shù)值時(shí)，采用矩形隸屬函數(shù)[9]將其轉(zhuǎn)換為隸屬度，即

(10)

2.3 算法流程

算法輸入：目標(biāo)區(qū)域的大小長(zhǎng)×寬，粒子數(shù)量P，粒子群算法最大迭代次數(shù)mIter，傳感器的感知半徑r，候選的傳感器集合S。

算法輸出：最佳傳感器集合對(duì)應(yīng)的粒子p_best、最佳適應(yīng)度f(wàn)it_best，所使用的傳感器數(shù)量Amount_best。

算法流程：

Step 1 ∥隨機(jī)生成候選粒子群

生成X和V集合，每個(gè)Xi、Vi的各個(gè)分量隨機(jī)取值為[0,1]之間的值。

Step 2 ∥進(jìn)行迭代尋優(yōu)

for iter=1:mIter

∥計(jì)算當(dāng)前粒子群各個(gè)粒子的適應(yīng)度

fori=1∶P

forj=1∶N

Sj2等于依據(jù)式(10)計(jì)算的Xij的隸屬度；

基于Sj和式(9)計(jì)算此時(shí)Xi對(duì)應(yīng)的適應(yīng)度值fit_temp；

If fit_temp

fit_locali=fit_temp；

p_locali=Xi；

If fit_temp

fit_best=fit_temp

p_best=Xi；

∥更新X和V

fori=1∶P

Vi=w*Vi+c1*r1*(p_locali-Xi)+c2*r2*(p_best-Xi);

Xi=Xi+Vi;

Step 3 ∥計(jì)算最優(yōu)結(jié)果對(duì)應(yīng)傳感器數(shù)量和覆蓋率

Amount_best=p_best去模糊化后對(duì)應(yīng)的傳感器數(shù)量;

Covered_best=(1+Amount_best/N)/fit_best-1。

該算法首先隨機(jī)生成P個(gè)粒子，然后計(jì)算每個(gè)粒子對(duì)應(yīng)的適應(yīng)度函數(shù)值，并根據(jù)該值更新局部和全局最優(yōu)粒子位置，隨后按照粒子群位置更新算法更新粒子的速度和位置，最后輸出最優(yōu)結(jié)果。算法中w是粒子群優(yōu)化算法的慣性權(quán)值，c1,c2是對(duì)應(yīng)的學(xué)習(xí)因子，r1,r2是兩個(gè)[0,1]之間的隨機(jī)數(shù)。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 參數(shù)設(shè)置

設(shè)定區(qū)域的大小是200 m×200 m，初始隨機(jī)拋灑的無(wú)線傳感器數(shù)量是200個(gè)，無(wú)線傳感器的感知半徑r為20 m。初始生成100個(gè)隨機(jī)粒子，最大迭代周期數(shù)是50代。慣性權(quán)值w取值為0.6，學(xué)習(xí)因子c1，c2均取值為2，r1，r2分別取值為0.6，0.3。

3.2 結(jié)果及分析

圖1是本文方法在求解過(guò)程中適應(yīng)度函數(shù)值、覆蓋率、所用傳感器數(shù)量與迭代次數(shù)的關(guān)系圖。

圖1 實(shí)驗(yàn)結(jié)果

從圖1(a)可以看出，隨著迭代次數(shù)的增加，適應(yīng)度函數(shù)值逐漸變優(yōu)，一直達(dá)到一個(gè)穩(wěn)定值，證明本文提出的算法能夠解決無(wú)線傳感器網(wǎng)絡(luò)的優(yōu)化部署問(wèn)題。結(jié)合圖1(b)和圖1(c)可以看出，在初始情況下，大部分傳感器節(jié)點(diǎn)(95個(gè))都被加入到構(gòu)建網(wǎng)絡(luò)中，此時(shí)網(wǎng)絡(luò)的覆蓋率也較高(95 %)。但是由于優(yōu)化部署的目的是在覆蓋率和節(jié)點(diǎn)數(shù)量之間取得一個(gè)較好的平衡，此時(shí)參與網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量過(guò)多將會(huì)導(dǎo)致網(wǎng)絡(luò)和節(jié)點(diǎn)的耗電量和通信量增加、降低網(wǎng)絡(luò)總體通信效率和存活時(shí)間，因此此時(shí)適應(yīng)度函數(shù)值比較低(0.756)。隨著粒子群優(yōu)化算法的迭代尋優(yōu)，覆蓋率和傳感器數(shù)量都經(jīng)歷一個(gè)由高到低再到適中的過(guò)程，最后取得一個(gè)穩(wěn)定的最優(yōu)適應(yīng)度函數(shù)值(0.638)，此時(shí)傳感器數(shù)量?jī)H為36個(gè)，但是達(dá)到了85 %的覆蓋率。

表1是本文方法與傳感器節(jié)點(diǎn)全部加入、隨機(jī)加入等方法的對(duì)比。從表中可以看出：與全部加入、隨機(jī)加入等方法相比，本文方法的適應(yīng)度函數(shù)值最優(yōu)，傳感器數(shù)量?jī)H分別相當(dāng)于全部加入和隨機(jī)加入的18 %，37 %，但覆蓋率卻相當(dāng)于它們的87 %，89 %，在使用較少節(jié)點(diǎn)取得較高的覆蓋率方面具有明顯的優(yōu)勢(shì)。

表1 本文方法與其它方法的對(duì)比

在本文中，使用除法式表示式(9)，相當(dāng)于對(duì)覆蓋率和節(jié)點(diǎn)數(shù)量賦予了相同的權(quán)重。在實(shí)際運(yùn)用過(guò)程中，還可以根據(jù)需要將其轉(zhuǎn)換為加法式，并增加相應(yīng)的權(quán)重系數(shù)，以決定是傾向于取得較高的覆蓋率還是取得較少的節(jié)點(diǎn)數(shù)量。

4 結(jié)束語(yǔ)

本文提出了一種基于模糊粒子群優(yōu)化算法的無(wú)線傳感器網(wǎng)絡(luò)部署優(yōu)化方法，該方法能夠綜合考慮網(wǎng)絡(luò)使用的節(jié)點(diǎn)數(shù)量和對(duì)應(yīng)的目標(biāo)區(qū)域覆蓋率，并通過(guò)隸屬度函數(shù)將連續(xù)值轉(zhuǎn)換為01值，從而決定對(duì)應(yīng)的傳感器節(jié)點(diǎn)是否參與構(gòu)建網(wǎng)絡(luò)。實(shí)驗(yàn)結(jié)果表明：通過(guò)多次迭代，該方法的目標(biāo)函數(shù)值能夠得到逐步優(yōu)化。相對(duì)于全部加入和隨機(jī)加入兩種方法，該方法在保持較高覆蓋率的同時(shí)，使用的傳感器數(shù)量較少。