基于PSO的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議

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

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

0 引 言

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

1 LEACH協(xié)議運行機制的分析

傳統(tǒng)LEACH協(xié)議將網(wǎng)絡(luò)中所有存活的傳感器節(jié)點采用單層模式劃分；LEACH協(xié)議將網(wǎng)絡(luò)內(nèi)非死亡傳感器節(jié)點劃分為成員節(jié)點和簇頭節(jié)點；成員節(jié)點和簇頭節(jié)點進行簇內(nèi)通信，簇頭節(jié)點和Sink節(jié)點進行簇間通信。LEACH協(xié)議按輪循環(huán)周而復(fù)始直至節(jié)點全部死亡或者達到預(yù)設(shè)的結(jié)束條件。每一輪包括兩個階段，即建立階段和穩(wěn)定階段，對應(yīng)簇頭選舉、簇的劃分和數(shù)據(jù)傳輸階段。

LEACH協(xié)議將網(wǎng)絡(luò)劃分層次，可在一定程度上均分能耗，提高網(wǎng)絡(luò)生存周期。同時，LEACH協(xié)議減少了信息傳輸?shù)臅r耗，且簇的劃分也在一定程度上維系了拓撲結(jié)構(gòu)，使得網(wǎng)絡(luò)更健壯。隨著對LEACH的深入研究，研究人員發(fā)現(xiàn)LEACH協(xié)議存在如下不足：

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

（2）LEACH協(xié)議在選舉簇頭時未考慮節(jié)點在監(jiān)測區(qū)域內(nèi)的位置，使得選出的簇頭可能分布于網(wǎng)絡(luò)邊緣或聚集在一起，加劇了能耗；

（3）LEACH協(xié)議每一輪中產(chǎn)生的簇頭數(shù)是隨機的，選出的簇頭數(shù)可能大于最優(yōu)簇頭數(shù)或小于最優(yōu)簇頭數(shù)，從而降低網(wǎng)絡(luò)內(nèi)節(jié)點的生命周期；

（4）LEACH協(xié)議中，不論是簇內(nèi)通信還是簇間通信都是單跳，導(dǎo)致開銷增大，降低了節(jié)點的生存周期。

2 LEACH_PZ協(xié)議

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

2.1 PSO算法描述

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

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

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

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

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

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

2.2 對選舉簇頭的PSO算法的設(shè)計

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

（1）簇頭能量因子

選簇時應(yīng)該給予剩余能量多的節(jié)點更多成為簇頭的機會，現(xiàn)考慮節(jié)點剩余能量和網(wǎng)絡(luò)中所有節(jié)點的能量關(guān)系，將簇頭能量因子引入適應(yīng)值函數(shù)中，如式（3）：

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

（2）簇間位置因子

選簇算法應(yīng)該給予位置較優(yōu)的節(jié)點更多成為簇頭的機會，現(xiàn)考慮節(jié)點所處位置在整個簇內(nèi)的情況，將簇間分布因子引入適應(yīng)值函數(shù)中，如式（4）：

式中：d（mi，Ck）為簇內(nèi)節(jié)點到簇頭的距離；|Ck|為本簇內(nèi)節(jié)點的個數(shù)。當所選節(jié)點在簇內(nèi)幾何位置越優(yōu)時，節(jié)點成為簇頭的機會就越大。

（3）簇內(nèi)成員節(jié)點數(shù)因子

選簇算法應(yīng)該給予簇內(nèi)節(jié)點數(shù)均勻的節(jié)點更多成為簇頭的機會，現(xiàn)考慮簇內(nèi)成員個數(shù)，將簇內(nèi)成員個數(shù)引入適應(yīng)值函數(shù)中，如式（5）：

式中：|Ck|為本簇內(nèi)節(jié)點的個數(shù)；|Cp|表示平均簇內(nèi)成員數(shù)。簇內(nèi)成員節(jié)點數(shù)越均勻，節(jié)點越有機會成為簇頭。綜上，適應(yīng)值函數(shù)如式（6）：

式中，α，β，λ分別表示簇頭能量因子、簇間位置因子、簇內(nèi)成員節(jié)點數(shù)因子在適應(yīng)值函數(shù)中所占比重。

2.3 LEACH_PZ協(xié)議算法流程

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

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

圖1 LEACH_PZ每輪算法流程圖

3 仿真與實驗分析

3.1 成簇仿真與分析

首先對傳統(tǒng)LEACH和LEACH_PZ協(xié)議的成簇過程進行仿真，以直觀展示傳統(tǒng)LEACH協(xié)議的不足和LEACH_PZ協(xié)議的提升；之后針對LEACH_PZ協(xié)議以及LEACH-C協(xié)議和傳統(tǒng)LEACH就Sink節(jié)點位置、節(jié)點生存時間、單個節(jié)點能耗、數(shù)據(jù)傳輸量進行仿真，具體展現(xiàn)LEACH_PZ對網(wǎng)絡(luò)性能的提升。

3.1.1 傳統(tǒng)LEACH成簇

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

圖2 傳統(tǒng)LEACH協(xié)議成簇示意圖

3.1.2 LEACH_PZ成簇

圖3所示為LEACH_PZ的成簇效果。LEACH_PZ的簇頭分布修正了傳統(tǒng)LEACH協(xié)議簇頭分布的不足，簇頭數(shù)目更優(yōu)，節(jié)點位置更接近簇的幾何中心，且簇內(nèi)成員數(shù)更加均勻。

圖3 LEACH_PZ協(xié)議成簇示意圖

3.2 簇間耗能仿真與分析

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

圖4 Sink節(jié)點不同時首節(jié)點死亡時間

3.3 單個節(jié)點能耗仿真與分析

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

圖5 網(wǎng)絡(luò)各節(jié)點能耗圖

3.4 網(wǎng)絡(luò)節(jié)點生命周期仿真與分析

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

圖6 網(wǎng)絡(luò)節(jié)點生存時間圖

3.5 基站接收數(shù)據(jù)量仿真與分析

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

圖7 基站在首節(jié)點死亡時接收的數(shù)據(jù)量圖

4 結(jié) 語

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