基于PSO的無線傳感器網絡分簇路由協議

賈艷楓，孫恩巖，王傳云，鄭志軍，尹中康

（沈陽航空航天大學 計算機學院，遼寧 沈陽 110136）

0 引 言

經典的LEACH協議[1-4]一直以來都是人們的研究熱點，有研究表明，與一般的平面多跳路由協議和靜態分層算法相比，LEACH可以將網絡生命周期延長15%。但LEACH協議中并沒有明確簇首節點如何均勻分布，且由于每個成為蔟首的節點都消耗了大致相同的能量，所以協議不適合節點能量不均衡的網絡。為此，本文通過在PSO算法中加入對節點位置和剩余能量、簇內成員節點數的考量，著力改善簇頭選舉機制，并通過仿真驗證改進后的LEACH_PZ路由協議性能。

1 LEACH協議運行機制的分析

傳統LEACH協議將網絡中所有存活的傳感器節點采用單層模式劃分；LEACH協議將網絡內非死亡傳感器節點劃分為成員節點和簇頭節點；成員節點和簇頭節點進行簇內通信，簇頭節點和Sink節點進行簇間通信。LEACH協議按輪循環周而復始直至節點全部死亡或者達到預設的結束條件。每一輪包括兩個階段，即建立階段和穩定階段，對應簇頭選舉、簇的劃分和數據傳輸階段。

LEACH協議將網絡劃分層次，可在一定程度上均分能耗，提高網絡生存周期。同時，LEACH協議減少了信息傳輸的時耗，且簇的劃分也在一定程度上維系了拓撲結構，使得網絡更健壯。隨著對LEACH的深入研究，研究人員發現LEACH協議存在如下不足：

（1）LEACH協議在簇頭選舉階段時傳感器節點等概率成簇，使得能量小的節點可能被選為簇頭并導致其提前死亡；

（2）LEACH協議在選舉簇頭時未考慮節點在監測區域內的位置，使得選出的簇頭可能分布于網絡邊緣或聚集在一起，加劇了能耗；

（3）LEACH協議每一輪中產生的簇頭數是隨機的，選出的簇頭數可能大于最優簇頭數或小于最優簇頭數，從而降低網絡內節點的生命周期；

（4）LEACH協議中，不論是簇內通信還是簇間通信都是單跳，導致開銷增大，降低了節點的生存周期。

2 LEACH_PZ協議

為改進LEACH協議存在的不足，本文提出了一種新的路由協議——LEACH_PZ。LEACH_PZ采用集中式控制策略，每輪各階段與LEACH協議相同，LEACH_PZ相較于LEACH協議的改進之處在于利用PSO算法優化分簇過程，采用PSO算法分簇的LEACH_PZ在簇頭選舉過程中會根據節點的能量和位置以及簇內成員節點數等信息選擇簇頭。

2.1 PSO算法描述

PSO算法[5-7]將種群中的個體抽象為一個只具備速度和位置信息但沒有質量和體積的粒子。搜索區域內每個粒子的位置都有可能是最優解，而粒子還在不斷迭代過程中改變位置，因此需設計一個適應值函數，通過適應值函數從眾多位置中選出最優解。每個粒子的迭代過程都需要跟蹤粒子本身能找到最優解和粒子群所能找到的最優解。假設在N維空間內，存在一個規模為m的粒子種群，每個粒子都有自己的速度Vj=（vj1，vj2，…，vjN）和位置 Wj=（wj1，wj2，…，wjN），且在每次迭代過程中都會更新位置和速度。每次迭代粒子都會通過適應值函數計算出自己的適應值fitness，并判斷是否修改自己的最好位置Pjb=（pjb1，pjb2，…，pjbN）和粒子群的歷史最優位置Gjb=（gjb1，gjb2，…，gjbN）。粒子第i+1次迭代過程中速度和位置的更新公式如下：

式中：w為慣性權重；c1，c2為加速常量；r1，r2為0～1之間的隨機數。將式（1）看做如下三部分：

（1）第一部分是wVj（i），稱為“慣性”部分，代表粒子維持上一次速度的程度；

（2）第二部分是c1r1（Pjb（i）-Wj（i）），稱為“自我認知”部分，代表向自我最好位置的逼近程度；

（3）第三部分是c2r2（Gjb（i）-Wj（i））代表對群體最好位置的逼近趨勢，屬于“社會認知”部分。

這三部分共同決定了粒子群的搜索能力。粒子群在搜索空間內的速度不宜太大或太小，太大會跳出最優解空間，太小則陷入局部最優。故粒子在限定最大值速度Vmax的同時也要防止速度過小。

2.2 對選舉簇頭的PSO算法的設計

集中式控制策略要求所有節點在首輪初期向Sink節點匯報自己的基本信息，之后Sink節點不再接收基本信息。每次運行PSO算法考察粒子的能量[8]、位置以及簇內成員節點數等綜合信息選出簇頭。假設在監測區域內隨機分布了M個節點，預定義分為K（100個節點最優簇頭數可以為5）個簇，Sink節點將能量大于閾值的N（M＜N＜K）個節點挑出，作為后備簇頭節點。簇頭節點將從后備簇頭節點中選出，可能的選擇有CNK種。這時定義的每個粒子都是一種分簇，即一個粒子代表K個簇頭。為了判斷這組簇頭的好壞需用適應值函數衡量其性能。本文設計的適應度函數主要考察以下幾個要素：

（1）簇頭能量因子

選簇時應該給予剩余能量多的節點更多成為簇頭的機會，現考慮節點剩余能量和網絡中所有節點的能量關系，將簇頭能量因子引入適應值函數中，如式（3）：

式中：E（mi）為存活節點能量；E（Ck）為所選簇頭能量。當存活節點一致時，所選節點能量越高越有機會成為簇頭。

（2）簇間位置因子

選簇算法應該給予位置較優的節點更多成為簇頭的機會，現考慮節點所處位置在整個簇內的情況，將簇間分布因子引入適應值函數中，如式（4）：

式中：d（mi，Ck）為簇內節點到簇頭的距離；|Ck|為本簇內節點的個數。當所選節點在簇內幾何位置越優時，節點成為簇頭的機會就越大。

（3）簇內成員節點數因子

選簇算法應該給予簇內節點數均勻的節點更多成為簇頭的機會，現考慮簇內成員個數，將簇內成員個數引入適應值函數中，如式（5）：

式中：|Ck|為本簇內節點的個數；|Cp|表示平均簇內成員數。簇內成員節點數越均勻，節點越有機會成為簇頭。綜上，適應值函數如式（6）：

式中，α，β，λ分別表示簇頭能量因子、簇間位置因子、簇內成員節點數因子在適應值函數中所占比重。

2.3 LEACH_PZ協議算法流程

LEACH_PZ協議每輪的算法流程如圖1所示。

場景設置：在100 m×l00 m的監測區域內，有100個節點隨機分布在二維平面xOy（-50≤x≤50，-50≤y≤50）內，Sink節點位于（0，75）[9-11]。因涉及傳統LEACH，LEACH-C，LEACH_PZ協議的比較，為使結果更具有真實性，隨機生成的100個節點坐標會被存儲在mat文件中供三者調用。

圖1 LEACH_PZ每輪算法流程圖

3 仿真與實驗分析

3.1 成簇仿真與分析

首先對傳統LEACH和LEACH_PZ協議的成簇過程進行仿真，以直觀展示傳統LEACH協議的不足和LEACH_PZ協議的提升；之后針對LEACH_PZ協議以及LEACH-C協議和傳統LEACH就Sink節點位置、節點生存時間、單個節點能耗、數據傳輸量進行仿真，具體展現LEACH_PZ對網絡性能的提升。

3.1.1 傳統LEACH成簇

在仿真過程中每個存活的傳感器節點會自主生成隨機數與閾值進行比較，若比閾值小則成為簇頭。圖2反映了各節點的成簇情況。圖中簇頭節點均小于最優簇頭數，同時簇內節點數不均勻，且簇頭位于監測區域邊沿而非簇的幾何中心，其原因在于成簇過程中簇頭節點的個數和位置以及簇成員個數無法控制。

圖2 傳統LEACH協議成簇示意圖

3.1.2 LEACH_PZ成簇

圖3所示為LEACH_PZ的成簇效果。LEACH_PZ的簇頭分布修正了傳統LEACH協議簇頭分布的不足，簇頭數目更優，節點位置更接近簇的幾何中心，且簇內成員數更加均勻。

圖3 LEACH_PZ協議成簇示意圖

3.2 簇間耗能仿真與分析

Sink節點的位置可以分為兩種，即部署在檢測區域內或檢測區域外。Sink節點位置的不同對網絡生存周期亦有影響。圖4所示為Sink節點不同時首節點死亡時間。由圖4可知，Sink節點不論部署在何處，LEACH_PZ協議的第一個節點死亡時間都比LEACH和LEACH_C晚，且Sink節點位于檢測區域內（Sink在（0，0）點）的性能比Sink節點位于檢測區域外的（Sink在（0，75）點）性能好。

圖4 Sink節點不同時首節點死亡時間

3.3 單個節點能耗仿真與分析

圖5所示為采用LEACH協議、LEACH_PZ協議以及LEACH_C協議的網絡單節點能耗比較，顯示了運行75次后各節點的能量。由圖5可知，LEACH_PZ協議可以平均能量，而LEACH和LEACH_C的性能則較差，以致能耗不均衡，導致一些節點過早死亡。

圖5 網絡各節點能耗圖

3.4 網絡節點生命周期仿真與分析

圖6所示為采用LEACH協議、LEACH_PZ協議、LEACH_C協議的網絡節點存活數比較。由圖6可知，LEACH節點在54輪時就已經出現了死亡節點，而LEACH_PZ協議要到87輪時才出現，且LEACH_PZ協議比LEACH_C協議節點的存活時間長12%。實驗證明，采用PSO算法并綜合考慮簇頭的節點和能量來選擇簇頭，雖然增大了Sink節點的負擔，但會延長節點的生命周期。

圖6 網絡節點生存時間圖

3.5 基站接收數據量仿真與分析

圖7所示為采用LEACH協議、LEACH_PZ協議以及LEACH-C協議接收數據的比較。圖中展示了4次運行后的結果，圖像顯示LEACH_PZ協議在第一個節點死亡時收到的數據量比LEACH協議提高了90%，比LEACH_C協議提高了10%，充分展示了LEACH_PZ的優越性能。

圖7 基站在首節點死亡時接收的數據量圖

4 結 語

本文系統性地分析了LEACH協議的原理運行機制，并指出了LEACH協議在簇頭選舉過程中存在的不足，在詳述了PSO算法的運行機制后重新設計了PSO算法，在適應值函數中加入簇內成員節點數因子并形成LEACH_PZ協議；最后論證LEACH_PZ協議優化成簇效果，節省Sink節點耗能，平衡各節點能量，提高網絡的生命周期和網絡數據傳輸量，使WSN得到更廣泛的應用。后續的研究方向可以聚焦兩方面：一是繼續優化PSO算法的參數，合理的參數可幫助PSO算法更快地選出最優解，同時降低Sink節點運算過程中帶來的時間延遲；二是優化簇間通信，簇頭節點處匯聚了大量簇內成員節點數發送的信息，如果直接將這些信息采用單跳的形式發送給Sink節點，則會消耗大量簇頭節點的能量，因此選擇最短路徑，找到若干節點多跳傳輸不失為一個好的研究方向。