張 亮， 黃 郡

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

0 引 言

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

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

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

1 問題建模

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

式中P′(aj)為截斷化概率，計算公式為

(7)

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

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

(8)

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

(9)

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

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

2.1 符號定義

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

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

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

2.2 模糊粒子表示

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

(10)

2.3 算法流程

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

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

算法流程：

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

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

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

for iter=1:mIter

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

fori=1∶P

forj=1∶N

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

基于Sj和式(9)計算此時Xi對應(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 ∥計算最優(yōu)結(jié)果對應(yīng)傳感器數(shù)量和覆蓋率

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

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

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

3 實驗與結(jié)果分析

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

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

3.2 結(jié)果及分析

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

圖1 實驗結(jié)果

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

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

表1 本文方法與其它方法的對比

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

4 結(jié)束語

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