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

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

0 引 言

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

1 LEACH協(xié)議運(yùn)行機(jī)制的分析

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

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

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

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

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

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

2 LEACH_PZ協(xié)議

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

2.1 PSO算法描述

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

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

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

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

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

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

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

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

（1）簇頭能量因子

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

式中：E（mi）為存活節(jié)點(diǎn)能量；E（Ck）為所選簇頭能量。當(dāng)存活節(jié)點(diǎn)一致時(shí)，所選節(jié)點(diǎn)能量越高越有機(jī)會(huì)成為簇頭。

（2）簇間位置因子

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

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

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

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

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

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

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

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

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

圖1 LEACH_PZ每輪算法流程圖

3 仿真與實(shí)驗(yàn)分析

3.1 成簇仿真與分析

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

3.1.1 傳統(tǒng)LEACH成簇

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

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

3.1.2 LEACH_PZ成簇

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

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

3.2 簇間耗能仿真與分析

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

圖4 Sink節(jié)點(diǎn)不同時(shí)首節(jié)點(diǎn)死亡時(shí)間

3.3 單個(gè)節(jié)點(diǎn)能耗仿真與分析

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

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

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

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

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

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

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

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

4 結(jié) 語

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