基于粒子群算法的WSN非均勻分簇路由協議

基于粒子群算法的WSN非均勻分簇路由協議

無線傳感器網絡（Wireless Sensor Network，WSN）是傳感器節點自治組成的網絡。WSN分簇路由協議包含簇的形成及簇首選擇，其關鍵問題在網絡運行節點能量消耗的過程中如何選擇簇首使整個網絡簇內能耗均衡。這是一個NP難問題。基于群體智能算法，能夠避免陷入局部最優解，找到全局最優解，適合于解決這個NP難問題。目前許多研究者采用粒子群算法解決WSN優化分簇問題，文獻主要是在LEACH算法的基礎上采用PSO算法優化選擇簇首，簇頭需要完成收集數據和傳遞數據的功能，很容易消耗能量導致節點死亡。文獻主要采用PSO算法分簇，使用最小距離法，但采用單跳路由，容易導致距離基站較遠的簇頭死亡。

本文針對文獻分簇策略中存在的問題，提出采用粒子群算法的非均勻分簇雙層路由協議。該協議先用LEACH算法進行非均勻以及次簇頭的選擇，然后采用粒子群算法進行主簇頭的選擇，主要收集普通節點數據并進行融合，然后將融合的數據傳給次簇頭，接著次簇頭傳給匯聚節點，以平衡簇內的能耗。

系統模型

網絡模型及假定

本文是假設N個傳感器節點隨機分布在一個M*M的正方形區域內，假設該無線傳感器網絡具有以下性質：（1）每個節點具有唯一ID，節點和匯聚節點的位置都固定不動；（2）每個節點的初始能量都相同；（3）每個節點的都具有相似的能力，并且地位相等，都有機會成為簇頭；（4）每個節點都可以根據節點間的距離來調整其發射功率的大小；（5）節點具有位置感知能力。

無線通信能耗模型

本文采用通用的無線通信模型，如下圖1所示。在該無線通信模型中，發送數據的能耗主要在發送電路和功率放大電路上，接受數據的能耗則在接收電路上。

在保證合理信噪比的條件下，傳感器節點每發送數據時所消耗的能量為：

傳感器節點接收數據時消耗的能量為：

圖1　無線通信能耗模型

圖2　PSO-CP算法原理

基于粒子群算法的非均勻分簇路由協議（PSOCP）

PSO-CP協議采用雙簇頭方式，可以避免由于簇內簇頭能耗消耗過大而快速消亡，影響網絡生命周期。這種多層次的數據傳輸方式以及結合蝙蝠算法對主簇頭的選取都有助于節點間能耗的平衡。原理如圖2所示。

非均勻分簇的建立及次簇頭的產生

在每“輪”中，通過LEACH算法產生次簇頭，并且網絡中的其余節點根據與選擇出來的次簇頭進行距離的比較。節點根據與所有次簇頭中距離最近的選擇加入該簇。這樣就形成了非均勻分簇路由協議。

在每“輪”中，都有一個閾值，每個節點生成一個隨機數，如果該節點的隨機數小于這“輪”的閾值那么這個節點就被選擇為次簇頭。閾值的計算公式如下：

當次簇頭選出來后，然后網絡中剩余的每個節點都與剛剛生成的次簇頭進行距離比較。當節點的距離離該次簇頭的距離最小時，則該節點就加入這個簇。也就是非均勻分簇就形成了。

主簇頭的產生

成非均勻分簇后，在每一個簇內進行蝙蝠優化算法選舉最優的節點作為主簇頭。為了使之前介紹的PSO算法更好的應用到這里，我們需要對原來的簇進行改進。

假設n 個節點分布在平面內，則粒子i 的位置xid（t ）由x分量和y 分量決定，如下所示：

同時，粒子i 的速度vid（t ）也應該由x 分量和y分量決定，即：

由于網絡中傳感器節點的位置并不一定會和隨機生成的粒子一一對應，所以粒子的位置位置需要調整，使得其中Pxi和Pyi為簇內節點位置的x 和y 分量。設Dpxi為xidx（t ）與i 節點x 分量差的絕對值，設Dpyi為xidy（t ）與i 節點y 分量差的絕對值，即：

則可知k 節點位置和粒子xid（t ）最接近，把粒子的位置用相應節點的位置替代，即：

然后將粒子群算法引入進來選取主簇頭，由于適應度函數的設定直接影響到選取出來的簇頭是否最優。在本論文中，我們將節點剩余能量情況和節點距離其它節點遠近情況最為適應度函數。構造適應度函數如下所示：

其中，f1為該簇內節點與簇內其余節點距離平均值的最小值。這樣是為了減少數據在傳輸中能量的消耗。f2為計算該該簇內總能量與該節點能量的比值。a ，b為［0，1］的數，并且a+b=1，在仿真中，就是找到使該適應度函數最小的值所對應的那個粒子，并找出在網絡中離該粒子最近的節點，把該節點選擇為主簇頭。具體步驟如下：

第一步：初始化粒子，隨機初始化粒子的速度和位置；

第二步：根據適應度函數，計算每個粒子的適應度函數值；

第三步：更新粒子的個體極值；即將第i個粒子的當前適應值與該粒子的個體極值進行比較，如果大于個體極值，則將其替換，否則不變。

第四步：更新種群的全局極值；對每個粒子，將其適應值與全局極值進行比較，如果大于全局極值，則將其替換，否則不變。

第五步：根據公式更新速度和位置；

第六步：檢查是否到了迭代條件，如果到了，則退出，沒到，返回第二步，直到達到最大循環代數。

圖3為主簇頭選取的流程圖。

仿真及結果分析

在100個傳感器節點隨機分布在100m*100m的范圍內，匯聚節點坐標（50，50），位于網絡內部。數據包長度為所有節點的初始能量都為0.1J。對本文提出的PSO-CP路由協議，在Core i5和2G內存計算機上，采用MATLAB2012B軟件平臺進行仿真訓練，并把它同LEACH和DEEC路由協議進行性能比較。

由圖4可知，同一種顏色代表一個簇，每種簇中有兩個簇頭，一個是主簇頭，一個是次簇頭。帶有十字星的為簇內的主簇頭，空圓點的是次簇頭。上圖中，每個簇內都有主次簇頭，其他為普通節點。中間為匯聚節點。

圖3　主簇頭選取的流程

網絡性能評價指標：

（1） 網絡生命周期：指網絡能更維持多久的時間，持續的時間越長，則網絡生命周期越長。通過節點存活的輪數來評價網絡生命周期。

（2） 平均剩余能量消耗：指網絡中某一輪所有節點的平均剩余能量情況。

在仿真中，運行250輪。仿真結果如圖5所示。

由圖5可以清晰的知道， LEACH算法在150輪附近時開始出現了節點死亡的情況，DEEC算法在165輪附近時開始出現了節點死亡的情況，PSO-CP算法在185輪附近時開始出現了節點死亡的情況。在250輪數中，LEACH算法節點死亡接近90個，DEEC算法節點死亡20個，PSO-CP算法節點死亡8個。通過比較可知，本文算法在節約節點能量方面有一定的優勢。

圖6為三種算法節點剩余平均能量的對比，由圖可知，相比于LEACH算法、DEEC算法，PSO-CP算法代表的線條幾乎總是在它們兩個之上。也即是說，在同一輪中，PSO-CP算法的能量剩余總比其他兩種算法要多。在250輪附近，LEACH算法的剩余能量幾乎為0，DEEC算法的剩余能量也接近0.01，而在PSO-CP算法中，節點剩余的平均能量為0.03。這就說明，PSO-CP協議能更好的均衡網絡中節點能量消耗，避免個別節點因過度消耗能量而死亡，有效的延長了網絡的生存周期。

圖4　PSO-CP路由協議非均勻分簇

圖5　三種算法死亡節點數

圖6　三種算法節點剩余平均能量

結語

有效解決簇頭選舉不合理、節點能量消耗不均衡，本文提出了基于粒子群算法的非均勻分簇路由協議。在構造非均勻分簇模型時，根據LEACH算法來進行分簇，選取出次簇頭，然后引入粒子群算法，選取出主簇頭。仿真結果表明，雙簇頭的方式有利于節點間能量的均衡，有效的延長了網絡生存期。

10.3969/j.issn.1001- 8972.2016.15.028