無線傳感器網絡部署優化仿真研究

郎健 孟晗

(北京市北京工業大學軟件學院,北京 100022)

無線傳感器網絡部署優化仿真研究

郎健 孟晗

(北京市北京工業大學軟件學院,北京 100022)

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

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

1 WSN節點部署算法國內外研究現狀

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

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

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

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

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

圖1 TKMPSO覆蓋率變化曲線

圖2 標準PSO算法部署圖

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

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

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

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

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

2.2 網絡模型

為了進一步介紹該算法的原理和實現該算法的仿真實驗，我們先對算法建立網絡模型。

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

2.3 TKMPSO算法實現流程

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

3 Matlab仿真

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

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

4 結語

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

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

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