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

郎健 孟晗

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

【關(guān)鍵詞】微粒群算法 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]。文獻(xiàn)[2]和文獻(xiàn)[3]都提出了一種基于微粒群算法的無線傳感網(wǎng)絡(luò)部署優(yōu)化方法，雖然證明微粒群算法能夠有效實現(xiàn)無線傳感網(wǎng)絡(luò)部署優(yōu)化，但是標(biāo)準(zhǔn)粒子群算法在空間搜索時，容易陷入“早熟”現(xiàn)象，達(dá)不到理想的覆蓋率。針對該問題，有文獻(xiàn)提出一種基于改進(jìn)微粒群算法（KMPSO）的無線傳感器網(wǎng)絡(luò)節(jié)點部署優(yōu)化策略。在優(yōu)化的過程中，算法通過引入K-means聚類算法，將種群劃分為幾個子種群，使各子種群之間彼此進(jìn)行獨立優(yōu)化；與此同時，為了避免“早熟”發(fā)生，可以增強(qiáng)子種群間的信息交流，對子種群進(jìn)行動態(tài)重組，減弱微粒對局部最優(yōu)點的追逐，避免標(biāo)準(zhǔn)PSO算法中的粒子“早熟”現(xiàn)象，但是該算法規(guī)定迭代若干代后，強(qiáng)制對子種群進(jìn)行動態(tài)重組，具有一定的盲目性。

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

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

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

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

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

本算法的中心思想是：遍歷微粒群中每一個微粒，從微粒j中頭節(jié)點i（1

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

如果是二象限，將該節(jié)點向更靠近上邊界或者左邊界的方向移動r/2的距離。如果是三象限，將該節(jié)點向更靠近下邊界或者左邊界的方向移動r/2的距離。如果是四象限，將該節(jié)點向更靠近下邊界或者右邊界的方向移動r/2的距離。然后，判斷節(jié)點k到第k1（1

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

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

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

每一個傳感器節(jié)點采用 表示（0

因此，傳感器節(jié)點集C所覆蓋的像素面積之和就是該節(jié)點集中所有節(jié)點覆蓋像素點的并集，記為Sarea，則 。無線傳感網(wǎng)絡(luò)節(jié)點部署的優(yōu)化目標(biāo)是使網(wǎng)絡(luò)的覆蓋率最大，即 。定義適應(yīng)值函數(shù)如下： 。當(dāng) 取得最大值時的節(jié)點位置信息就是無線傳感器網(wǎng)絡(luò)中節(jié)點的最佳部署位置。

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

（1）使用K-means算法將微粒群劃分為k個種群，并得到每個子種群的聚類中心。（2）初始化閾值和計數(shù)器變量，通過最有目標(biāo)函數(shù)計算微粒的最優(yōu)位置和最優(yōu)適應(yīng)值，并用聚

類中心初始化全局最優(yōu)位置和全局最優(yōu)適應(yīng)值變量。（3）開始一輪進(jìn)化，若進(jìn)化到迭代后期，則采用基于歐氏距離的矯正算法調(diào)整。否則，PSO算法更新微粒。然后，若微粒前適應(yīng)值大于其個體最優(yōu)值，則進(jìn)入4；否則，采用連續(xù)無變化變異算法對微粒進(jìn)行變異處理。

（4）更新微粒的pbest_fit后，若大于gbest_fit，則更新gbest_fit，否則，將小于子種群中g(shù)best_fit的微粒數(shù)量gCount+1。（5）若所有的微粒結(jié)束一代進(jìn)化，則重復(fù)步驟3，進(jìn)行下一個微粒的進(jìn)化。否則，進(jìn)入6。（6）若gbest_fit無變化的節(jié)點總數(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個種群，進(jìn)入第8步。（8）gCount=0。更新公式動態(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è)計了2組模型對實驗進(jìn)行測試。第1組反映了TKMPSO算法的覆蓋率變化曲線結(jié)果（見圖1），第2組反映了歐氏距離的矯正算法處理以后傳感器節(jié)點結(jié)果（見圖2、3）。

圖1 TKMPSO覆蓋率變化曲線 圖 2標(biāo)準(zhǔn)PSO算法部署圖 圖3基于歐式距離的標(biāo)準(zhǔn)PSO算法部署圖

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

4 結(jié)語

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

參考文獻(xiàn)：

[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.