基于粒子群算法的混合無線傳感網(wǎng)覆蓋優(yōu)化

摘 要:為優(yōu)化混合傳感網(wǎng)絡(luò)覆蓋性能，基于粒子群算法提出一種優(yōu)化策略，并通過引進(jìn)擾動(dòng)因子，有效地避免了算法陷入早熟陷阱，加速了算法收斂。通過仿真實(shí)驗(yàn)，驗(yàn)證了該優(yōu)化算法能夠有效地提高網(wǎng)絡(luò)覆蓋性能，并與最新的算法進(jìn)行了比較。

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò); 混合傳感網(wǎng); 多目標(biāo)優(yōu)化; 粒子群算法; 移動(dòng)節(jié)點(diǎn); 覆蓋

中圖分類號:TP393文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2010)06-2273-03

doi:10.3969/j.issn.10013695.2010.06.079

Hybrid sensor networks coverageenhancing approach based on particle swarm optimization

XIANG Xixi， HUANG Hongguang， LI Yudong

(School of Electrical Engineering Information， Sichuan University， Chengdu 610065， China)

Abstract:To optimizing the coverage performannce， this paper proposed a strategy which was based on PSO. Introcing disturbing gene into the PSO， the strategey could avoid the trap of premature and accelerate astringent of the algotithm. The results of simulation show that the algorithm is able to improve the coverage of the networks. And the performances of this algorithm are compared with other two latest algorithms.

Key words:wireless sensor networks (WSN); hybrid sensor networks; multiobjective optimization; particle swarm algorithm(PSO); mobile node; coverge

無線傳感器網(wǎng)絡(luò)(WSN)由多個(gè)單節(jié)點(diǎn)組成，各節(jié)點(diǎn)通過傳感或控制參數(shù)實(shí)現(xiàn)與環(huán)境的交互。節(jié)點(diǎn)分為靜止節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)。人工部署可全部使用靜態(tài)節(jié)點(diǎn)，根據(jù)現(xiàn)場對節(jié)點(diǎn)位置進(jìn)行調(diào)整，就可達(dá)到非常高的覆蓋率。對于比較危險(xiǎn)的監(jiān)測環(huán)境，如火山、放射區(qū)、有毒化工區(qū)等，是不適合進(jìn)行人工部署的，只能用隨機(jī)拋撒的方式進(jìn)行，如空投方式。但是隨機(jī)部署方式很容易形成感知覆蓋盲區(qū)和重疊區(qū)，很難將眾多節(jié)點(diǎn)放置到合適的位置。如果全部使用動(dòng)態(tài)節(jié)點(diǎn)，如履帶機(jī)器人，成本將非常高。為了使傳感網(wǎng)有一定的自部署和自修復(fù)能力，且節(jié)約成本，文獻(xiàn)[1，2]提出了混合無線傳感器網(wǎng)絡(luò)的部署策略:將一定比例的移動(dòng)節(jié)點(diǎn)混合在靜態(tài)節(jié)點(diǎn)中，一起進(jìn)行隨機(jī)部署，然后通過移動(dòng)節(jié)點(diǎn)的移動(dòng)特性來增強(qiáng)網(wǎng)絡(luò)的覆蓋率，加大感知范圍，減少感知盲區(qū)和重疊區(qū)。

目前對于WSN覆蓋問題已有一些研究成果，如張晉等人[3]提出的WSN關(guān)鍵區(qū)域覆蓋啟發(fā)式算法;劉永生等人[4]用隨機(jī)調(diào)度子集劃分最優(yōu)解的方法優(yōu)化覆蓋率。混合感知網(wǎng)部署也已提出一些策略:Wang、Gao等人[1，2]提出了兩種移動(dòng)節(jié)點(diǎn)的部署方法;周彤等人[5]中提出了基于虛擬力的混合感知網(wǎng)絡(luò)節(jié)點(diǎn)部署方法;曾映蘭等人[6]提出了一種用遺傳算法優(yōu)化WSN混合節(jié)點(diǎn)的覆蓋策略;鄒學(xué)玉等人[7]對單個(gè)移動(dòng)節(jié)點(diǎn)的檢測模式進(jìn)行了研究等。

本文所提出的基于粒子群多目標(biāo)優(yōu)化方法，在混合感知網(wǎng)絡(luò)中，利用全局信息調(diào)整移動(dòng)節(jié)點(diǎn)，重新部署網(wǎng)絡(luò)，使得整個(gè)網(wǎng)絡(luò)的感知覆蓋性能得到優(yōu)化，并通過引入擾動(dòng)因子解決PSO早熟缺陷，加速了算法收斂性。通過仿真，與文獻(xiàn)[5，6]的方法進(jìn)行對比，結(jié)果表明，在覆蓋率優(yōu)化方面優(yōu)于文獻(xiàn)[5]，在收斂速度方面優(yōu)于文獻(xiàn)[6]。

1 問題描述

為了簡化網(wǎng)絡(luò)模型，本文假定混合網(wǎng)絡(luò)所在區(qū)域是一個(gè)二維矩形平面A內(nèi)。網(wǎng)絡(luò)由N個(gè)固定節(jié)點(diǎn)和M個(gè)移動(dòng)節(jié)點(diǎn)構(gòu)成。移動(dòng)節(jié)點(diǎn)具有文獻(xiàn)[5]所描述的能力:a)移動(dòng)能力;b)自定位能力;c)感知環(huán)境能力;d)無線通信能力;e)信息融合能力。初始部署過程，采用隨機(jī)拋撒方式，并且不存在任何一點(diǎn)有兩個(gè)或兩個(gè)以上節(jié)點(diǎn)。

假設(shè)所有節(jié)點(diǎn)的感知能力r和通信能力R都是理想的，即在能力范圍內(nèi)，所有的感知和通信都能夠準(zhǔn)確完成。那么A內(nèi)任一點(diǎn)k，如果與節(jié)點(diǎn)i的距離D(i，k)≤r，那么k點(diǎn)被i感知到的概率Pk=1;否則，Pk=0。

根據(jù)上面的假設(shè)，將混合無線傳感器網(wǎng)絡(luò)的覆蓋問題作如下描述[6]:對于隨機(jī)部署在目標(biāo)區(qū)域K內(nèi)的N個(gè)靜止節(jié)點(diǎn)和M個(gè)移動(dòng)節(jié)點(diǎn)，如何通過優(yōu)化重部署移動(dòng)節(jié)點(diǎn)的位置，使得目標(biāo)區(qū)域被節(jié)點(diǎn)覆蓋感知的面積達(dá)到最大。數(shù)學(xué)表示為

max∪Ni=1SCd(xi，yi)+∪Mj=1MCd(xj，yj)S(K)(1)

其中:SCd(xi，yi)表示位于坐標(biāo)(x，y)處的固定節(jié)點(diǎn)的感知覆蓋面積;MCd(xj，yj)表示坐標(biāo)(x，y)處移動(dòng)節(jié)點(diǎn)的感知覆蓋面積;U表示并集。該模型實(shí)際上是一個(gè)多目標(biāo)優(yōu)化問題模型。

2 基于粒子群移動(dòng)節(jié)點(diǎn)優(yōu)化算法

最優(yōu)化問題是工程實(shí)踐和科學(xué)研究中的主要問題形式之一[8]，目標(biāo)函數(shù)超過一個(gè)并且需要同時(shí)處理的最優(yōu)化問題稱為多目標(biāo)優(yōu)化問題(multiobjective optimization problems， MOPs)。對于多目標(biāo)優(yōu)化問題， 一個(gè)解對于某個(gè)目標(biāo)來說可能是比較好的， 而對于其他目標(biāo)來講可能是較差的， 因此， 存在一個(gè)折中解的集合， 稱為Pareto最優(yōu)解集(Paretooptimal set)或者非支配解集(nondominated set)。解決最優(yōu)化問題，目前比較著名的算法有爬山法、遺傳算法、粒子群算法等，主要解決的問題有兩個(gè):a)尋找全局最小點(diǎn);b)加快收斂速度。由于爬山法易陷入局部極小解，遺傳算法的編程實(shí)現(xiàn)復(fù)雜且收斂速度慢，本文采用粒子群算法解決混合無線傳感網(wǎng)的覆蓋優(yōu)化問題。

2.1 粒子群算法的基本思想

粒子群算法(PSO)是目前普遍應(yīng)用的用于解決多目標(biāo)優(yōu)化問題的經(jīng)典算法之一。其基本思想[9]是將每個(gè)個(gè)體看做是D維搜索空間中的一個(gè)沒有體積和質(zhì)量的粒子，在搜索空間中以一定的速度飛行，并根據(jù)對個(gè)體和群體的飛行經(jīng)驗(yàn)綜合分析來動(dòng)態(tài)調(diào)整這個(gè)速度。設(shè)群體中第i個(gè)粒子為Xi=(xi1，xi2，…，xin)，它經(jīng)歷過的位置為Pi=(pi1，pi2，…，pin)。其中:最佳位置記為Pbest，當(dāng)前所組成群體的所有粒子經(jīng)歷過的最佳位置記為Pgbest，粒子i的速度用Vi=(vi1，vi2，…，vin)表示。對第t次迭代，粒子i在d維空間(1≤d≤D)的運(yùn)動(dòng)遵循如下方程[10]:

vid(t+1)=w×vid(t)+c1rand()×(pbest-xid(t))+c2rand()×(pgbest-xid(t))(2)

xid(t+1)=xid(t)+vid(t+1)(3)

其中:w表示慣性權(quán)重，它使粒子保持運(yùn)動(dòng)的慣性，使其有能力探索新的區(qū)域;c1、c2為常數(shù);rand()為[0，1]的隨機(jī)數(shù)。為了使粒子在搜索過程中，加大全局搜索能力，并避免粒子在全局最優(yōu)解附近出現(xiàn)振蕩現(xiàn)象，按照文獻(xiàn)[10]中的參數(shù)改進(jìn)方法，將慣性權(quán)重因子計(jì)算為

w=wmax-wmax-wminT×t(4)

其中:t表示當(dāng)前迭代次數(shù)，T表示總的迭代次數(shù)。

2.2 擾動(dòng)因子的引入

PSO算法容易出現(xiàn)所謂早熟問題，即在迭代過程中容易陷入局部最優(yōu)，過早地停止搜索。為了避免這種情況的出現(xiàn)，本文在標(biāo)準(zhǔn)算法中加入了擾動(dòng)因子的概念。當(dāng)算法在迭代過程中陷入局部最優(yōu)發(fā)生早熟現(xiàn)象時(shí)，粒子的速度V總是在局部最優(yōu)附近小范圍振蕩，這就使得粒子失去了空間搜索最優(yōu)解的能力。這時(shí)需要對粒子速度V進(jìn)行擾動(dòng)。對于標(biāo)準(zhǔn)PSO算法，作如下改進(jìn):在標(biāo)準(zhǔn)算法的第五步完成后，加入一個(gè)判斷，若當(dāng)前的覆蓋率與最近一次的全局最佳覆蓋率的差小于判定值K，那么就對當(dāng)前的粒子速度V進(jìn)行擾動(dòng)，V=V+Δv。其中:Δv=c3×rand()，rand()表示(0，1)的一個(gè)隨機(jī)數(shù);c3表示擾動(dòng)系數(shù)，通常取c3=1。在下文的仿真中可以驗(yàn)證，加入擾動(dòng)因子后，能有效地避免PSO陷入早熟陷阱，過早地停止搜索最優(yōu)解。

2.3 算法設(shè)計(jì)

將第1章中式(1)作為目標(biāo)函數(shù)，以M個(gè)移動(dòng)節(jié)點(diǎn)作為粒子，設(shè)計(jì)算法步驟如下:

a)初始化M個(gè)粒子的位置Xi和速度Vi，設(shè)定擾動(dòng)判定值K，計(jì)算初始覆蓋率。

b)按照2.1節(jié)中式(2)(3)更新各個(gè)粒子的位置和速度。

c)計(jì)算出新的移動(dòng)節(jié)點(diǎn)和靜止節(jié)點(diǎn)的聯(lián)合覆蓋率Pnew。

d)將當(dāng)前覆蓋率與粒子自身最佳位置的覆蓋率Pbest進(jìn)行比較。如果Pnew>Pbest，Pbest=Pnew;否則，Pbest不變。

e)將子群體每個(gè)粒子位置與該群體最好位置的Pgbest比較，如果較好，則重新設(shè)置Pgbest。

f)判定當(dāng)前覆蓋率Pnew與最近一次全局最佳覆蓋率Pbest的差。如果|Pnew-Pbest|

g)如果達(dá)到預(yù)設(shè)最大代數(shù)或足夠好的覆蓋率則停止，返回群體最佳個(gè)體位置Xi為運(yùn)行結(jié)果;否則，返回b)繼續(xù)。

3 仿真評價(jià)

3.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)定

本文用MATLAB對混合傳感網(wǎng)進(jìn)行仿真。在100 m×100 m的區(qū)域內(nèi)隨機(jī)拋撒60個(gè)節(jié)點(diǎn)，移動(dòng)節(jié)點(diǎn)數(shù)量為20個(gè)，節(jié)點(diǎn)感知半徑r=10 m，通信半徑R=20 m，移動(dòng)節(jié)點(diǎn)的移動(dòng)速度為2m/步，種群規(guī)模為30，參數(shù)c1=c2=1，最大慣性系數(shù)為wmax=0.9，最小慣性系數(shù)為wmin=0.4，最大迭代次數(shù)T=80。

圖1表示區(qū)域A內(nèi)隨機(jī)拋撒節(jié)點(diǎn)的初始位置，方塊形代表靜止節(jié)點(diǎn)，三角形代表移動(dòng)節(jié)點(diǎn)。根據(jù)式(1)可以計(jì)算，最初拋撒后，網(wǎng)絡(luò)覆蓋率為65.65%。

3.2 算法有效性驗(yàn)證

圖2中空心三角形表示移動(dòng)節(jié)點(diǎn)的初始位置，短線近似表示移動(dòng)軌跡。對比圖1可以明顯看出，經(jīng)過80次迭代，移動(dòng)節(jié)點(diǎn)從傳感器密集的區(qū)域移動(dòng)到了相對空曠的區(qū)域，整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的分布更加均勻，而節(jié)點(diǎn)的感知覆蓋范圍也明顯加大。這說明本文算法有效。

圖3顯示了節(jié)點(diǎn)的感知覆蓋率變化曲線。從圖中可以看出，經(jīng)過80次的迭代計(jì)算，節(jié)點(diǎn)的感知覆蓋率明顯提高。從曲線的增幅斜率可以看出，在前10次的迭代過程中，曲線斜率較大，覆蓋率快速增加;到了第30次以后，曲線斜率變得很小，覆蓋率的增幅放緩，逐漸穩(wěn)定于某一個(gè)常數(shù)。這說明，粒子在慣性因子w的作用下，在初期較容易搜索到空間中的更佳位置，所取得的支配集也較容易比前一支配集好。隨著迭代的進(jìn)行，粒子開始在最佳位置附近振蕩，所得的結(jié)果也穩(wěn)定于最佳結(jié)果。最終所得的優(yōu)化覆蓋率為77.99%，比原始覆蓋率提高了約12.34%，顯然，該算法對提升網(wǎng)絡(luò)覆蓋性能效果顯著。

3.3 擾動(dòng)因子的作用

為了驗(yàn)證本文所提出的擾動(dòng)因子對PSO算法改進(jìn)是可行的，采用上述參數(shù)進(jìn)行兩次單獨(dú)的仿真。一次加入擾動(dòng)因子，一次采用標(biāo)準(zhǔn)的PSO算法，仍然用覆蓋率對比的參數(shù)。具體比較結(jié)果如圖4所示。

從圖4中的對比曲線可以看出，標(biāo)準(zhǔn)的PSO很容易陷入早熟問題，特別是當(dāng)參數(shù)選取不當(dāng)時(shí)，優(yōu)化結(jié)果可能非常不理想。引入擾動(dòng)因子以后，當(dāng)PSO陷入早熟陷阱時(shí)，能夠?qū)αＷ铀俣萔進(jìn)行擾動(dòng)，加大其在搜索空間搜索到最佳位置的能力。這樣就能夠有效地避免標(biāo)準(zhǔn)PSO算法中的早熟問題。但是，擾動(dòng)因子不能過大，否則粒子容易在最佳位置附近大范圍振蕩，甚至可能造成優(yōu)化結(jié)果的下降。

3.4 與其他算法的比較

為了進(jìn)一步驗(yàn)證算法的性能，將本文所提出的算法與文獻(xiàn)[5，6]的算法在覆蓋率、RD指標(biāo)和迭代次數(shù)方面進(jìn)行比較。

覆蓋率對比如圖5所示。

三條曲線表示移動(dòng)節(jié)點(diǎn)分別占總節(jié)點(diǎn)比例為10%、20%、30%時(shí)三種算法的覆蓋率優(yōu)化結(jié)果。結(jié)果顯示:三種優(yōu)化方式均有很高的覆蓋率。其中，遺傳算法和本文算法很接近，HSDA算法略低一些。這是因?yàn)?，HSDA是一種基于行為的啟發(fā)式算法，沒有使用全局信息，可能造成部分節(jié)點(diǎn)陷入局部極小的陷阱，從而過早地停止移動(dòng)，影響覆蓋效果。而GA算法和本文算法都是基于全局信息進(jìn)行優(yōu)化處理，避免了HSDA的缺點(diǎn)，可以達(dá)到更好的覆蓋率。RD指標(biāo)對比如表1所示。

表1 三種算法的RD指標(biāo)對比

移動(dòng)節(jié)點(diǎn)比例/%HSDAGA本文算法

102.0972.1792.181

202.3862.4982.534

302.7322.8122.876

平均RD指標(biāo)2.4052.4962.53

RD指標(biāo)是曾映蘭等人[6]提出的:RD=覆蓋率/平均移動(dòng)距離。RD越大，表明在相同平均移動(dòng)距離下，網(wǎng)絡(luò)覆蓋率越高，網(wǎng)絡(luò)性能改善越好。當(dāng)移動(dòng)節(jié)點(diǎn)分別占總節(jié)點(diǎn)數(shù)10%、20%、30%時(shí)，三種算法的RD指標(biāo)和平均值如表1所示。從表中可以看出，本文算法的RD指標(biāo)要優(yōu)于HSDA和GA算法。雖然本文算法和GA算法在實(shí)際移動(dòng)距離上比HSDA要大，但是由于提高了覆蓋率，RD的值反而要大于HSDA。

迭代次數(shù)對比如表2所示。

表2 三種算法迭代次數(shù)比較

移動(dòng)節(jié)點(diǎn)數(shù)算法覆蓋率/%迭代次數(shù)/次

20

HSDA

GA

本文算法

75.48

77.19

77.99

40

89

56

迭代次數(shù)可以反映算法的優(yōu)化性能，迭代次數(shù)少也意味著移動(dòng)節(jié)點(diǎn)可以較少地進(jìn)行移動(dòng)，節(jié)省能量，提高網(wǎng)絡(luò)生存時(shí)間。以網(wǎng)絡(luò)含有20個(gè)移動(dòng)節(jié)點(diǎn)，達(dá)到最佳優(yōu)化結(jié)果時(shí)的迭代次數(shù)作為對比，如表2所示。結(jié)果顯示，本文算法的迭代次數(shù)與HSDA相比并不是最好的，要多出16次。這是因?yàn)椋琍SO算法是利用全局信息進(jìn)行優(yōu)化的，節(jié)點(diǎn)調(diào)整次數(shù)相對較多，但是卻將覆蓋率提高了2.51%。相對于GA算法，在覆蓋率相當(dāng)?shù)那闆r下，本文算法的迭代次數(shù)少了33次，收斂性明顯提高。

3.5 仿真評價(jià)結(jié)論

從3.2和3.3節(jié)的仿真結(jié)果可以看出，本文算法在理論上是可行的，擾動(dòng)因子對算法收斂性有明顯的提高，并且從3.4節(jié)的對比結(jié)論可以看出，該方法優(yōu)于HSDA和GA算法。雖然在平均移動(dòng)距離方面，本文方法比HSDA算法要差，但是卻不需要精確的參數(shù)控制，而且能夠避免陷入局部極小陷阱，總體的性能優(yōu)于HSDA。而同樣作為進(jìn)化算法，GA算法的種群是比較均勻地向最優(yōu)區(qū)域移動(dòng)，而PSO只有Pbest(或Pgbest)傳遞信息給其他粒子，信息流動(dòng)是單向的，整個(gè)搜索更新過程是跟隨當(dāng)前最優(yōu)解的過程，因此比GA算法具有更快的收斂性。另外，GA算法本身的實(shí)現(xiàn)過程也比較復(fù)雜，不利于某些特定環(huán)境中的快速實(shí)現(xiàn)。

4 結(jié)束語

本文基于粒子群算法，提出了一種混合傳感網(wǎng)覆蓋的優(yōu)化策略。通過仿真，與其他算法對比，說明了該方法的有效性和優(yōu)越性。混合傳感網(wǎng)絡(luò)由于其低成本和自部署能力，對于一些特殊的場景有很高的應(yīng)用價(jià)值。如何進(jìn)一步提高節(jié)點(diǎn)的覆蓋率，減少移動(dòng)距離，減少移動(dòng)節(jié)點(diǎn)的數(shù)量，對于實(shí)際的應(yīng)用有非常重要的意義。

參考文獻(xiàn):

[1]WANG Guiling， CAO Guohong， PORTAL T L. A bidding protocol for deploying mobile sensors [C]//Proc of the 11th IEEE International Conference on Network Protocols. Washington DC:IEEE Computer Society， 2003:565.

[2]WANG Guiling， CAO Guohong， PORTA T L. Proxybased sensor deployment for mobile sensor networks [C]//Proc of the 1st IEEE International Conference on Mobile Ad hoc and Sensor Systems. Fort Lauderdale， Florida:[s.n.]， 2004:493-562.

[3]張晉，劉大昕，徐悅竹，等. WSN關(guān)鍵區(qū)域覆蓋啟發(fā)式優(yōu)化算法[J].計(jì)算機(jī)工程，2009，35(14):16-19.

[4]劉永生，周顥，趙保華. WSN隨機(jī)調(diào)度覆蓋算法的子集劃分最優(yōu)解[J]. 中國科學(xué)技術(shù)大學(xué)學(xué)報(bào)， 2008， 35(3):225-229.

[5]周彤，洪炳镕，樸松昊.基于虛擬力的混合感知網(wǎng)節(jié)點(diǎn)部署[J].計(jì)算機(jī)研究與發(fā)展，2007，44(6):965-972.

[6]曾映蘭，陳靜，鄭金華. 基于遺傳算法的WSN覆蓋優(yōu)化方法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(11):89-91，98.

[7]鄒學(xué)玉，曹陽，劉徐迅，等. 面向移動(dòng)目標(biāo)的WSN單個(gè)檢測模式覆蓋問題[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版，2008，36(4):24-28.

[8]公茂果，焦李成，楊咚咚，等. 進(jìn)化多目標(biāo)優(yōu)化算法研究[J].軟件學(xué)報(bào)，2009，20(2):271-289.

[9]張文愛，劉麗芳，李孝榮.基于粒子進(jìn)化的多粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44(7):51-53.

[10]王曉樂，徐家品.基于粒子群優(yōu)化算法的WSNs節(jié)點(diǎn)定位研究[J]. 計(jì)算機(jī)應(yīng)用，2009，29(2):494-495，499.

[11]林祝亮，馮遠(yuǎn)靜，俞立.無線傳感網(wǎng)絡(luò)覆蓋的粒子進(jìn)化優(yōu)化策略研究[J].傳感技術(shù)學(xué)報(bào)，2009，22(6):873-877.