無(wú)線傳感器網(wǎng)絡(luò)部署優(yōu)化仿真研究

郎健 孟晗

(北京市北京工業(yè)大學(xué)軟件學(xué)院,北京 100022)

無(wú)線傳感器網(wǎng)絡(luò)部署優(yōu)化仿真研究

郎健 孟晗

(北京市北京工業(yè)大學(xué)軟件學(xué)院,北京 100022)

目前,基于WSN節(jié)點(diǎn)部署仍然存在部署成本高,網(wǎng)絡(luò)覆蓋范圍低的問(wèn)題。本課題針對(duì)以上問(wèn)題,提出一種改進(jìn)的WSN節(jié)點(diǎn)部署優(yōu)化算法,在一定數(shù)量傳感器節(jié)點(diǎn)和一定監(jiān)測(cè)區(qū)域內(nèi),最大限度地提升網(wǎng)絡(luò)覆蓋率,降低部署成本,提高網(wǎng)絡(luò)QOS。本算法將微粒群算法和K-means算法應(yīng)用到無(wú)線傳感器部署問(wèn)題,并提出了KMPSO算法的改進(jìn)算法(TKMPSO)。

微粒群算法 K-means均值聚類算法 WSN

1 WSN節(jié)點(diǎn)部署算法國(guó)內(nèi)外研究現(xiàn)狀

無(wú)線傳感器網(wǎng)絡(luò)(WSN)是由大量具有通信和計(jì)算能力的傳感器節(jié)點(diǎn)以自組織和多跳的方式構(gòu)成的無(wú)線網(wǎng)絡(luò)，能夠協(xié)作地感知、采集、處理和傳輸網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)感知對(duì)象的監(jiān)測(cè)信息，并將其報(bào)告給用戶[1]。文獻(xiàn)[2]和文獻(xiàn)[3]都提出了一種基于微粒群算法的無(wú)線傳感網(wǎng)絡(luò)部署優(yōu)化方法，雖然證明微粒群算法能夠有效實(shí)現(xiàn)無(wú)線傳感網(wǎng)絡(luò)部署優(yōu)化，但是標(biāo)準(zhǔn)粒子群算法在空間搜索時(shí)，容易陷入“早熟”現(xiàn)象，達(dá)不到理想的覆蓋率。針對(duì)該問(wèn)題，有文獻(xiàn)提出一種基于改進(jìn)微粒群算法(KMPSO)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署優(yōu)化策略。在優(yōu)化的過(guò)程中，算法通過(guò)引入K-means聚類算法，將種群劃分為幾個(gè)子種群，使各子種群之間彼此進(jìn)行獨(dú)立優(yōu)化；與此同時(shí)，為了避免“早熟”發(fā)生，可以增強(qiáng)子種群間的信息交流，對(duì)子種群進(jìn)行動(dòng)態(tài)重組，減弱微粒對(duì)局部最優(yōu)點(diǎn)的追逐，避免標(biāo)準(zhǔn)PSO算法中的粒子“早熟”現(xiàn)象，但是該算法規(guī)定迭代若干代后，強(qiáng)制對(duì)子種群進(jìn)行動(dòng)態(tài)重組，具有一定的盲目性。

針對(duì)K-means微粒群算法存在的問(wèn)題，本文提出一種改進(jìn)TKMPSO算法。

2 改進(jìn)的KMPSO算法(TKMPSO算法)

鄭磊等人提出KMPSO算法能有效地避免“早熟”現(xiàn)象，但是仍然存在不少的問(wèn)題，為了解決這些問(wèn)題，本文提出KMPSO算法的改進(jìn)算法(TKMPSO)，同樣采用PSO和K-means算法結(jié)合的方式。算法中每一個(gè)微粒表示區(qū)域內(nèi)全部傳感器節(jié)點(diǎn)的一種部署方案。TKMPSO算法的基本思想：首先，引入K-means聚類算法將種群劃分成幾個(gè)子種群，每個(gè)子種群獨(dú)立進(jìn)化，假設(shè)T表示不合格的全局最優(yōu)值的連續(xù)累計(jì)次數(shù)，如果T達(dá)到閾值，對(duì)子種群進(jìn)行重新劃分，組成新的微粒群。再次，算法引入基于歐幾里得距離矯正算法，降低節(jié)點(diǎn)之間覆蓋重疊區(qū)域的面積。

2.1 基于歐氏距離的矯正算法

圖1 TKMPSO覆蓋率變化曲線

圖2 標(biāo)準(zhǔn)PSO算法部署圖

通過(guò)實(shí)驗(yàn)，作者發(fā)現(xiàn)在標(biāo)準(zhǔn)PSO算法進(jìn)入迭代后期(2/3倍最大迭代周期)，一些微粒中的節(jié)點(diǎn)之間存在扎堆的情況，造成了大量感知區(qū)域重疊，大大降低了全局覆蓋率。為了解決上述問(wèn)題，進(jìn)一步提高覆蓋率，本文引入了一個(gè)基于歐氏距離矯正算法。

本算法的中心思想是：遍歷微粒群中每一個(gè)微粒，從微粒j中頭節(jié)點(diǎn)i(1＜i＜n；n為節(jié)點(diǎn)總數(shù))開(kāi)始，直到遍歷所有節(jié)點(diǎn)結(jié)束。計(jì)算節(jié)點(diǎn)i到節(jié)點(diǎn)k(i＜k＜n)的歐氏距離，如果不滿足設(shè)置的閾值，則按照線性探測(cè)再部署的策略將節(jié)點(diǎn)k移動(dòng)到更靠近邊界的空曠位置。線性探測(cè)再部署的規(guī)則：

將區(qū)域按照直角坐標(biāo)系的規(guī)則劃分為4個(gè)面積相等的象限。根據(jù)節(jié)點(diǎn)的x、y坐標(biāo)定位到某個(gè)象限，如果是第一象限，將該節(jié)點(diǎn)向更靠近上邊界或者右邊界的方向移動(dòng)r/2的距離。

如果是二象限，將該節(jié)點(diǎn)向更靠近上邊界或者左邊界的方向移動(dòng)r/2的距離。如果是三象限，將該節(jié)點(diǎn)向更靠近下邊界或者左邊界的方向移動(dòng)r/2的距離。如果是四象限，將該節(jié)點(diǎn)向更靠近下邊界或者右邊界的方向移動(dòng)r/2的距離。然后，判斷節(jié)點(diǎn)k到第k1(1＜k1＜n；k1!=k)個(gè)節(jié)點(diǎn)的距離是否達(dá)到要求，如果滿足，接著判斷節(jié)點(diǎn)i到第k+1個(gè)節(jié)點(diǎn)的距離是否滿足要求。如果不滿足要求，繼續(xù)探測(cè)k節(jié)點(diǎn)的位置，直到滿足要求或者移動(dòng)次數(shù)達(dá)到閾值為止，結(jié)束算法。算法流程如下所示：

(1)在采用KMPSO算法對(duì)一個(gè)微粒優(yōu)化之后，判斷是否進(jìn)入后期迭代，100代以后成為進(jìn)入迭代后期。如果是迭代后期，進(jìn)入步驟2，開(kāi)始掃描微粒到其它粒子之間的距離。(2)判斷是否還有未遍歷的微粒節(jié)點(diǎn)，若是，進(jìn)入步驟3，開(kāi)始矯正當(dāng)前節(jié)點(diǎn)的位置。否，則已完成所有節(jié)點(diǎn)的遍歷，結(jié)束矯正算法。(3)判斷當(dāng)前微粒i到其它每一個(gè)微粒之間的距離是否滿足算法規(guī)則即大于R。是，則進(jìn)入步驟2。否則，進(jìn)入步驟4，對(duì)不滿足條件的一個(gè)節(jié)點(diǎn)j單獨(dú)變異。(4)采用PSO算法更新位置的策略對(duì)節(jié)點(diǎn)j進(jìn)行變異，讓其到每一個(gè)其它節(jié)點(diǎn)的距離小于R/2。采用while循環(huán)語(yǔ)句實(shí)現(xiàn)，若結(jié)束，則跳轉(zhuǎn)到步驟3。

2.2 網(wǎng)絡(luò)模型

為了進(jìn)一步介紹該算法的原理和實(shí)現(xiàn)該算法的仿真實(shí)驗(yàn)，我們先對(duì)算法建立網(wǎng)絡(luò)模型。

圖3 基于歐式距離的標(biāo)準(zhǔn)PSO算法部署圖

2.3 TKMPSO算法實(shí)現(xiàn)流程

(1)使用K-means算法將微粒群劃分為k個(gè)種群，并得到每個(gè)子種群的聚類中心。(2)初始化閾值和計(jì)數(shù)器變量，通過(guò)最有目標(biāo)函數(shù)計(jì)算微粒的最優(yōu)位置和最優(yōu)適應(yīng)值，并用聚類中心初始化全局最優(yōu)位置和全局最優(yōu)適應(yīng)值變量。(3)開(kāi)始一輪進(jìn)化，若進(jìn)化到迭代后期，則采用基于歐氏距離的矯正算法調(diào)整。否則，PSO算法更新微粒。然后，若微粒前適應(yīng)值大于其個(gè)體最優(yōu)值，則進(jìn)入4；否則，采用連續(xù)無(wú)變化變異算法對(duì)微粒進(jìn)行變異處理。(4)更新微粒的pbest_fit后，若大于gbest_fit，則更新gbest_fit，否則，將小于子種群中g(shù)best_fit的微粒數(shù)量gCount+1。(5)若所有的微粒結(jié)束一代進(jìn)化，則重復(fù)步驟3，進(jìn)行下一個(gè)微粒的進(jìn)化。否則，進(jìn)入6。(6)若gbest_fit無(wú)變化的節(jié)點(diǎn)總數(shù)大于微?？倲?shù)的2/3倍，則認(rèn)為這一代的gbest_fit不滿足進(jìn)化要求，將不合格次數(shù)thresCounter加1。進(jìn)入下一步。否則，thresCounter重置為0，進(jìn)入第8步。(7)若thresCounter≥gThres，K-means算法將微粒群重新劃分為k個(gè)種群，進(jìn)入第8步。(8)gCount=0。更新公式動(dòng)態(tài)更新慣性權(quán)重因子w和自適應(yīng)因子C1，C2。若達(dá)到進(jìn)化次數(shù)要求，則輸出最優(yōu)適應(yīng)值，結(jié)束算法。否則，進(jìn)入下一代進(jìn)化，執(zhí)行步驟3。

3 Matlab仿真

本文設(shè)計(jì)了2組模型對(duì)實(shí)驗(yàn)進(jìn)行測(cè)試。第1組反映了TKMPSO算法的覆蓋率變化曲線結(jié)果(見(jiàn)圖1)，第2組反映了歐氏距離的矯正算法處理以后傳感器節(jié)點(diǎn)結(jié)果(見(jiàn)圖2、3)。

圖1反映了TKMPSO算法的傳感器節(jié)點(diǎn)部署圖，覆蓋率提高到89.49%，與初始覆蓋率相比，網(wǎng)絡(luò)覆蓋率提高了76.51%。在前120次的迭代過(guò)程中，曲線的斜率較大，覆蓋率增長(zhǎng)較快；超過(guò)120次以后，曲線的斜率明顯變小，覆蓋率增長(zhǎng)緩慢，最終在147代左右趨于一個(gè)穩(wěn)定的常數(shù)。這是因?yàn)樵趹T性系數(shù)因子的作用下，算法在早期具有較強(qiáng)的全局收斂能力。隨著迭代次數(shù)的增加，微粒開(kāi)始在最優(yōu)位置附近振蕩。圖2，圖3反映了標(biāo)準(zhǔn)采用歐式距離矯正算法的優(yōu)化結(jié)果。覆蓋率從51.93%提升到67.26%。由此可見(jiàn)，基于歐式距離的矯正算法顯著地提高網(wǎng)絡(luò)覆蓋率，能夠有效地避免傳感器節(jié)點(diǎn)扎堆現(xiàn)象。

4 結(jié)語(yǔ)

在標(biāo)準(zhǔn)PSO算法的基礎(chǔ)上，鄭磊提出了基于KMPSO微粒群算法，本文在KMPSO的基礎(chǔ)上提出一種改進(jìn)算法(TKMPSO)。主要從如下幾方面提出改進(jìn)方案：首先，引入粒子群聚類閾值變量，科學(xué)的控制采用K-means算法動(dòng)態(tài)劃分微粒群粒子的時(shí)機(jī)。其次，為了解決感知區(qū)域重疊的問(wèn)題，本文引入基于歐幾里得距離矯正算法，對(duì)距離不符合要求的兩個(gè)節(jié)點(diǎn)使用PSO算法進(jìn)行變異。最后，通過(guò)matlab仿真實(shí)驗(yàn)證明，TKMPSO算法達(dá)到了預(yù)期的效果。

[1]AKYILIDIGIF,SU Wei-lian,SAN KARASUBRAMANIAMY,etal.A survey on sensor networks[J].IEEE Communications Magazine ,2002, 8:721-734.

[2]任彥,張思東,張宏科.無(wú)線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法.[J].軟件學(xué)報(bào),2006,17(3):422-433.

[3]BURNERA,BUCZAKAL,JIN Yao-chu.A self-organizing,cooperative sensor network for remo te surveillance:current result[C] / /Proceedings of SPIE Volume 3713.Bellingham ,WA : SPIE,1999 : 238-248.