郎健 孟晗

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

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

郎健 孟晗

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

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

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

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

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

針對K-means微粒群算法存在的問題，本文提出一種改進TKMPSO算法。

2 改進的KMPSO算法(TKMPSO算法)

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

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

圖1 TKMPSO覆蓋率變化曲線

圖2 標準PSO算法部署圖

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

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

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

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

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

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

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

圖3 基于歐式距離的標準PSO算法部署圖

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

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

3 Matlab仿真

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

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

4 結(jié)語

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

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

[2]任彥,張思東,張宏科.無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法.[J].軟件學(xué)報,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.