郎健 孟晗

【摘 要】目前，基于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）。

【關(guān)鍵詞】微粒群算法 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 基于歐氏距離的矯正算法

通過(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

將區(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

（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ò)模型。

每一個(gè)傳感器節(jié)點(diǎn)采用 表示（0

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

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覆蓋率變化曲線 圖 2標(biāo)準(zhǔn)PSO算法部署圖 圖3基于歐式距離的標(biāo)準(zhǔn)PSO算法部署圖

圖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ù)期的效果。

參考文獻(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ú)線傳感器網(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.