基于靜態(tài)分簇的LEACH算法改進(jìn)研究

韓 濤，李訓(xùn)銘

（河海大學(xué) 能源與電氣學(xué)院，江蘇 南京 210000）

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由大量無處不在的、具有通信與計算能力的微小傳感器節(jié)點(diǎn)密集布設(shè)在無人值守的監(jiān)控區(qū)域而構(gòu)成的能夠根據(jù)環(huán)境自主完成指定任務(wù)的“智能”自治測控網(wǎng)絡(luò)系統(tǒng)。無線傳感器網(wǎng)絡(luò)的發(fā)展最初起源于戰(zhàn)場監(jiān)測等軍事應(yīng)用。而現(xiàn)今無線傳感器網(wǎng)絡(luò)被應(yīng)用于很多民用領(lǐng)域，如環(huán)境與生態(tài)監(jiān)測、健康監(jiān)護(hù)、家居自動化以及交通控制等。由于WSN的網(wǎng)絡(luò)節(jié)點(diǎn)多是由電池供電，所以其路由算法要考慮高效節(jié)能，才能夠使整個網(wǎng)絡(luò)有著良好的生存能力。

路由是WSN的核心技術(shù)之一，好的WSN路由協(xié)議需要滿足以下四個要求：能量高效，可擴(kuò)展性強(qiáng)，魯棒性，快速收斂性。目前WSN的路由協(xié)議按照發(fā)現(xiàn)策略分為主動路由和被動路由。按照網(wǎng)絡(luò)管理的邏輯結(jié)構(gòu)劃分分為：平面結(jié)構(gòu)路由，如 Gossiping[1]；分層路由，如 LEACH[2]，地理信息路由協(xié)議，如 GPSR[3]。

在眾多的無線傳感器網(wǎng)絡(luò)的路由協(xié)議中，LEACH協(xié)議是最為典型的一種分層路由協(xié)議，本文主要針對LEACH協(xié)議進(jìn)行優(yōu)化，優(yōu)化的中會借鑒其他路由協(xié)議的思想。使得改進(jìn)后的LEACH協(xié)議能夠更好的提高WSN的性能和適用范圍。

1 LEACH簡介及其優(yōu)化

LEACH（Low Energy Adaptive Clustering Hierarchy，低功耗自適應(yīng)集簇分層型協(xié)議）是由MIT的Heinzelman等人在2000年提出的最早在WSN中涉及分簇思想的路由協(xié)議算法。分簇思想相比于之前的平面路由傳輸，在高效節(jié)能方面有了很大的進(jìn)步，提高了網(wǎng)絡(luò)存活時間，所以在該算法提出之后不斷的有其他路由協(xié)議引入或者借鑒其分簇思想。而LEACH算法作為經(jīng)典算法，對它的優(yōu)化和改進(jìn)也在不斷的進(jìn)行。

LEACH算法的基本思想是：提出“輪”（round）的概念，每一輪即是一個循環(huán)，每個循環(huán)以隨機(jī)的方式選擇簇首節(jié)點(diǎn)（head node），普通的節(jié)點(diǎn)將數(shù)據(jù)傳輸?shù)酱厥坠?jié)點(diǎn)上，簇首節(jié)點(diǎn)和基站（base station）通信，分層式的設(shè)計降低了網(wǎng)絡(luò)能源消耗、提高了網(wǎng)絡(luò)整體生存時間，同時由于簇首節(jié)點(diǎn)是會在每一輪都會被重新選定，平衡了整個網(wǎng)絡(luò)的能量負(fù)載。

LEACH協(xié)議在工作的時候每輪主要分為兩個階段：周期性簇的建立階段和穩(wěn)定的數(shù)據(jù)通信階段。為了減少協(xié)議開銷，穩(wěn)定階段的持續(xù)時間要長于簇的建立階段。簇的建立階段主要分為4步：簇頭節(jié)點(diǎn)的選擇，簇頭節(jié)點(diǎn)的廣播，簇頭節(jié)點(diǎn)的建立和調(diào)度機(jī)制的生成。在此階段，傳感器節(jié)點(diǎn)隨機(jī)生成一個0~1之間的隨機(jī)數(shù)，并且與閾值T（n）做比較，如果小于該閾值，則該節(jié)點(diǎn)就會當(dāng)選為簇頭。T（n）按照下列公式計算：

式中：P為節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)的百分?jǐn)?shù)，r為當(dāng)前輪數(shù)，G為在最近的1/p輪中未當(dāng)選簇頭的節(jié)點(diǎn)集合。簇頭節(jié)點(diǎn)選定后，廣播自己成為簇頭的消息，節(jié)點(diǎn)根據(jù)接收到的消息的強(qiáng)度決定加入哪個簇，并告知相應(yīng)的簇頭，完成簇的建立過程。然后，簇頭節(jié)點(diǎn)采用TDMA的方式，為簇內(nèi)成員分配傳送數(shù)據(jù)的時隙。在穩(wěn)定階段，傳感器節(jié)點(diǎn)將采集的數(shù)據(jù)傳送到簇頭節(jié)點(diǎn)。簇頭節(jié)點(diǎn)對采集的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合后再將信息傳送給匯聚節(jié)點(diǎn)，匯聚節(jié)點(diǎn)將數(shù)據(jù)傳送給監(jiān)控中心來進(jìn)行數(shù)據(jù)的處理。穩(wěn)定階段持續(xù)一段時間后，網(wǎng)絡(luò)重新進(jìn)入簇的建立階段，進(jìn)行下一輪的簇重建，不斷循環(huán)。

LEACH協(xié)議中采取分簇的分層設(shè)計思想，同時簇首節(jié)點(diǎn)在接收到普通節(jié)點(diǎn)的數(shù)據(jù)后會對數(shù)據(jù)信息進(jìn)行融合，減少了數(shù)據(jù)量同時也節(jié)約了能量。簇首節(jié)點(diǎn)隨機(jī)選取，平衡了能量負(fù)載，延長了整個網(wǎng)絡(luò)的生命周期。LEACH算法本身也存在很多問題，首先由于簇首節(jié)點(diǎn)選取的隨機(jī)性會導(dǎo)致在整個區(qū)域內(nèi)簇首節(jié)點(diǎn)分布不均勻，普通節(jié)點(diǎn)在選取所要加入簇的時候按照就近原則，會出現(xiàn)極大簇和極小簇的情況，能量消耗不平衡；其次選取簇首節(jié)點(diǎn)的時候并未考慮剩余能量，會導(dǎo)致部分剩余能量少的節(jié)點(diǎn)被選為簇首節(jié)點(diǎn)而過早死去，最后簇首節(jié)點(diǎn)每輪都要重新選取，普通節(jié)點(diǎn)也要再次選擇要加入的簇，過于頻繁會造成相當(dāng)大的能量損耗。

2 歷史改進(jìn)

LEACH算法是層次型路由協(xié)議中最經(jīng)典的代表，是無線傳感器網(wǎng)絡(luò)中提出的最早基于分簇的路由協(xié)議，對其后的路由設(shè)計和改進(jìn)有很大的影響，對它的改進(jìn)也一直沒有間斷。對LEACH算法改進(jìn)的本質(zhì)在于3點(diǎn)：一個是平衡能量負(fù)載，因為LEACH算法的前提條件是每個節(jié)點(diǎn)擁有的能量是相同的，因此平衡能量負(fù)載能使得整個網(wǎng)絡(luò)中的能量合理配置，提高系統(tǒng)級能量使用率；另一個盡量減小數(shù)據(jù)傳輸過程中的能量消耗，按照能量消耗模型，參考能量消耗和距離以及數(shù)據(jù)量之間的關(guān)系，采用單跳和多跳結(jié)合多種傳輸方式；第3個就是數(shù)據(jù)融合，由于相近的傳感器節(jié)點(diǎn)獲取的數(shù)據(jù)有一部分或者大部分重復(fù)的，因此在傳播的簇首時進(jìn)行數(shù)據(jù)融合，減小數(shù)據(jù)傳輸量，也可以有效減小傳感器網(wǎng)絡(luò)中能量消耗，從而延長網(wǎng)絡(luò)壽命，也在一定程度上提高了整個網(wǎng)絡(luò)的質(zhì)量。由以上3點(diǎn)我們可以看到，對LEACH算法的改進(jìn)是基于能量模型來進(jìn)行的。自LEACH提出以來，對其改進(jìn)主要有以下幾個方面。

簇首選取方面的優(yōu)化：加入剩余能量的考慮，使得部分剩余能量較小的節(jié)點(diǎn)免于或者減小被選為簇首節(jié)點(diǎn)的概率[4]。改進(jìn)選取簇首節(jié)點(diǎn)的方式，加入時間因子[5]；使簇首節(jié)點(diǎn)分布均勻，如HEED[6]算法。重新計算最優(yōu)簇首個數(shù)[7]；靜態(tài)分配簇首節(jié)點(diǎn)[8]等。

平衡簇首負(fù)載的優(yōu)化：平衡簇中普通節(jié)點(diǎn)個數(shù)，避免過多的節(jié)點(diǎn)同時選擇一個簇首[9]等。

3 改進(jìn)后的LEACH算法

根據(jù)LEACH算法的特點(diǎn)和不足，學(xué)習(xí)了歷來其他研究者的改進(jìn)思想，本文將在以下幾個方面進(jìn)行改進(jìn)：首先基站根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)分布情況，將節(jié)點(diǎn)按照最優(yōu)簇個數(shù)分成占節(jié)點(diǎn)總數(shù)4%-6%（仿真中選擇5%）的簇，簇按照地理空間分布，接著根據(jù)簇內(nèi)節(jié)點(diǎn)信息來選擇簇首，首輪簇首選擇之后，簇內(nèi)節(jié)點(diǎn)會根據(jù)自己的信息來形成一個（0~1）之間的隨機(jī)數(shù)，在下一輪簇首選擇時，最大的會自動升級為簇首。在通信過程中采用單跳與多跳相結(jié)合接力通訊思想，根據(jù)節(jié)點(diǎn)的位置和剩余能量來選擇接力節(jié)點(diǎn)，接力通訊分為簇間接力以及簇和基站中間加入中轉(zhuǎn)的接力。

3.1 網(wǎng)絡(luò)模型與能量模型

3.1.1 網(wǎng)絡(luò)模型

改進(jìn)算法的網(wǎng)絡(luò)模型和LEACH算法基本類似：

1）網(wǎng)絡(luò)中有固定的基站，并且遠(yuǎn)離傳感器節(jié)點(diǎn)，能夠足夠大，不需要考慮其能量消耗。

2）傳感器節(jié)點(diǎn)的類型相同，具有相同的初始能量，并且能量是有限的，每個節(jié)點(diǎn)具有一個獨(dú)一無二的ID。

3）傳感器節(jié)點(diǎn)隨機(jī)分布，但是位置固定，并且基站知道每個節(jié)點(diǎn)的位置和ID。

4）節(jié)點(diǎn)可以感知自己的剩余能量，并且能夠改變發(fā)射功率。

3.1.2 能量模型

改進(jìn)算法的能量模型采用LEACH算法的能量模型:

1） 無線通訊中發(fā)送（ETx-elec）和接收（ERx-elec）相同大小的數(shù)據(jù)所消耗的能量是相同的。即為：

無線通訊中信號傳輸增益為

2）發(fā)送一個k位數(shù)據(jù)到距離為d的地方，接收和發(fā)送的能量如下：

接收：

根據(jù)d和接近中心的距離 d0的關(guān)系，ERx-amp（k，d）分為自由空間模型（Free Space，fs）和多徑衰減模型（Multipath， mp）[10]：

其中εfs和εmp是常數(shù)，由發(fā)射距離和接收誤碼率等因素決定。d0是決定何種模型的閾值：

其中，L是系統(tǒng)功耗因子，ht是發(fā)送天線高度，hr是接收天線高度，λ是載波波長。

3.2 簇的形成

本文改進(jìn)與LEACH算法及以往算法相比，在簇的周期性建立階段順序有所改動，會在簇首選取之前就先確定簇的大小及簇內(nèi)節(jié)點(diǎn)，然后在改簇內(nèi)再選擇簇首節(jié)點(diǎn)。改進(jìn)后簇形成過程是：首先，基站獲取每個節(jié)點(diǎn)的位置信息，根據(jù)節(jié)點(diǎn)的密度和位置將整個網(wǎng)絡(luò)分成節(jié)點(diǎn)總數(shù)4%~6%的區(qū)域 （仿真中采用5%），每個區(qū)域內(nèi)擁有網(wǎng)絡(luò)節(jié)點(diǎn)18~22個。簇分好之后在一段時間內(nèi)將不再重新分簇，直到某個簇內(nèi)的擁有最大剩余能量的節(jié)點(diǎn)的能量低于整個網(wǎng)絡(luò)中平均節(jié)點(diǎn)能量，將進(jìn)行新一輪的簇區(qū)域選取，保證每個簇內(nèi)都有可以承擔(dān)數(shù)據(jù)傳輸?shù)交镜墓?jié)點(diǎn)。

3.3 簇首選取和輪換

在分簇完成之后，由于節(jié)點(diǎn)同構(gòu)且具有相同的初始能量，所以每個節(jié)點(diǎn)當(dāng)選為簇首節(jié)點(diǎn)的概率相同，在簇內(nèi)采用隨機(jī)方式選取簇首節(jié)點(diǎn)，通過基站來確定該簇內(nèi)的簇首節(jié)點(diǎn)，然后發(fā)送廣播給簇內(nèi)的普通節(jié)點(diǎn)，普通節(jié)點(diǎn)根據(jù)接收到的信息來和簇首節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸。數(shù)據(jù)傳輸方式和LEACH算法相同，簇首節(jié)點(diǎn)為子節(jié)點(diǎn)分配TDMA時隙，子節(jié)點(diǎn)在自己的時隙內(nèi)進(jìn)行數(shù)據(jù)傳輸，其余時間通訊模塊則進(jìn)入sleep狀態(tài)，等待下次被喚醒。普通節(jié)點(diǎn)發(fā)送信息包含自己的ID和剩余能量，簇首節(jié)點(diǎn)將接受到的數(shù)據(jù)進(jìn)行融合后發(fā)送給基站。基站接收到信息之后，根據(jù)剩余能量和位置信息來生成一個輪換因子μ，它由下式?jīng)Q定：

式中ke和ks是常數(shù)，由能量消耗決定。Elast表示節(jié)點(diǎn)的剩余能量，d是節(jié)點(diǎn)到基站的距離。在下一輪的簇首選取中，簇內(nèi)輪換因子最大的可以直接升級成為簇首節(jié)點(diǎn)。輪換因子的確定并不介意某個節(jié)點(diǎn)在上一輪中已經(jīng)擔(dān)任過簇首節(jié)點(diǎn)，因為考慮了剩余能量，如果一個節(jié)點(diǎn)的剩余能量遠(yuǎn)多于簇內(nèi)的其他節(jié)點(diǎn)，在擔(dān)任一次簇首之后，仍然是所在簇內(nèi)剩余能量最大的，會繼續(xù)擔(dān)任簇首節(jié)點(diǎn)。從而達(dá)到簇內(nèi)能量負(fù)載的平衡。避免一些雖然沒有擔(dān)任過簇首節(jié)點(diǎn)，但是本身剩余能量較低的節(jié)點(diǎn)擔(dān)任簇首節(jié)點(diǎn)。

3.4 簇間通訊與多跳接力通信

從能量模型中我們可以看到，當(dāng)數(shù)據(jù)傳輸距離過大時，能量消耗會急劇增加，并且超過了數(shù)據(jù)接收，因此，雖然數(shù)據(jù)接收也是一筆不小的消耗，但是在進(jìn)行超遠(yuǎn)距離通訊時選擇多跳接力通訊仍能減少數(shù)據(jù)傳輸?shù)哪芰肯摹１疚膶EACH算法的數(shù)據(jù)傳輸模式進(jìn)行兩方面的改進(jìn)：第一個方面是多跳與單跳結(jié)合的數(shù)據(jù)傳輸方式，這個在以前的LEACH算法改進(jìn)中也有見到，本文與以前有所不同的是，并不會總是選擇距離基站較近的簇首擔(dān)任下一跳的節(jié)點(diǎn)，而是在較近的區(qū)域選擇一批具有較大剩余能量的節(jié)點(diǎn)進(jìn)行多跳，并且會計算成本，只有接力通訊方式總成本比直接通訊消耗減少超過一定比例時才選擇多跳，這個比例是與K的有關(guān)，K由下面的式子決定：

其中，Ef-last是備選多跳點(diǎn)區(qū)域內(nèi)的的平均剩余能量，Eb-last是距離節(jié)點(diǎn)較遠(yuǎn)的節(jié)點(diǎn)平均剩余能量。由于簇分布選擇的固定簇大小一樣，因此簇首直接與基站進(jìn)行數(shù)據(jù)傳輸時，距離較遠(yuǎn)簇能量消耗要比距離較近簇大。多跳接力時，距離基站較近的節(jié)點(diǎn)會被選為下一跳的節(jié)點(diǎn)，則會增加距離基站較近的節(jié)點(diǎn)的能耗。因此，在數(shù)據(jù)通訊時，基站將根據(jù)剩余能量進(jìn)行對比，在降低系統(tǒng)級能耗與平衡各個節(jié)點(diǎn)能耗之間選擇一個平衡，則可以最大限度延長網(wǎng)絡(luò)整體的壽命。

除了上述改進(jìn)，為了進(jìn)一步拓展網(wǎng)絡(luò)的適用范圍，考慮到無線傳感器網(wǎng)絡(luò)可能安裝在距離基站較遠(yuǎn)的地方，可以在進(jìn)行超遠(yuǎn)距離數(shù)據(jù)傳輸時，在基站與網(wǎng)絡(luò)間設(shè)置中轉(zhuǎn)，中轉(zhuǎn)采用外接電源供電，負(fù)責(zé)基站與傳感器網(wǎng)絡(luò)之間的數(shù)據(jù)轉(zhuǎn)傳。根據(jù)具體的情況，還可以使用多級接力通訊。

4 算法仿真及分析

本文仿真選擇NS2來對LEACH極其改進(jìn)進(jìn)行仿真對比。文中的仿真環(huán)境是WindowsXP+cygwin+NS-2.27。

表1 實(shí)驗仿真參數(shù)Tab.1 Simulation parameters

圖1 兩種算法存活點(diǎn)比較Fig.1 The comparison of survival point between two algorithms

在NS2平臺上對兩種算法進(jìn)行仿真，使用gnuplot繪制兩種算法的節(jié)點(diǎn)存活情況，從圖中可以看出，改進(jìn)后的算法（leach-zj）第一個死亡節(jié)點(diǎn)時間大約是在 350s，而leach第一個死亡節(jié)點(diǎn)是在130s，改進(jìn)后的第一個死亡節(jié)點(diǎn)時間是leach算法的2.7倍。整個網(wǎng)絡(luò)的存活時間是leach算法的一倍左右。所以優(yōu)化后的算法與leach算法相比，具有更好的網(wǎng)絡(luò)性能，延長了網(wǎng)絡(luò)的生命周期。

5 結(jié)束語

文中對LEACH的改進(jìn)相對于原算法性能更優(yōu)，通過動態(tài)和靜態(tài)簇頭選取相結(jié)合的方式，降低了簇首選取過程中的能量消耗，參考節(jié)點(diǎn)分布信息來設(shè)置每個簇的位置和簇內(nèi)節(jié)點(diǎn)數(shù)，并且根據(jù)距基站的距離和剩余能量來選取簇頭，使得簇首分布較傳統(tǒng)分布更為均勻，并且平衡了能量負(fù)載，不僅有效避免個別節(jié)點(diǎn)提前死亡，也使得整體能量消耗有了一定程度的減少，提高了網(wǎng)絡(luò)的生存能力。

[1]Haas Z，Halpen J， Li L.Gossip-Based ad hoc routing.IEEE/ACM Transactions on Networking，Piscataway [J].IEEE Press，2006:479-491.

[2]Heinzelman W，Chandrakasam A，Balakrishnan H.Energy efficient communication protocol for wireless microsenser[C]//Proceeding of the 33rd Hawaii International Conference on System Sciences，2000.

[3]Karp B，Kung H.GPSR:Greedy Perimeter Stateless Routing for Wireless Networks.Proceedings of the 6th Annual International Conference on Mobile Computing and Networking[C].Boston，USA，2000:243-254

[4]呂濤，朱清新，張路橋.一種基于LEACH協(xié)議的改進(jìn)算法[J].電子學(xué)報，2011，39（6）：1045-1049.LV Tao，ZHU Qing-xin，ZHANG Lu-qiao，et al.An improved LEACH algorithm in wireless sensor network[J].Acta Electronica sinica，2011，39（6）：1045-1049.

[5]李成岳，申鉉京，陳海鵬，等.無線傳感器網(wǎng)絡(luò)中LEACH路由算法的研究與改進(jìn)[J].傳感技術(shù)學(xué)報，2010，23（8）：1163-1167.LI Cheng-yue，SHEN Xuan-jing，CHEN Hai-peng，et al.Research and improvement of LEACH routing algorithm for wireless sensor networks[J].Chinese Journal of Sensors and Actuators，2010，23（8）：1163-1167.

[6]Younis，S Fahamy.Distributed clustering in ad-hoc sensor networks:A hybrid.energy-efficient approach[J].IEEE Infocom，2004（1）:629-640.

[7]蔣陽，孫柳林，敖文鈞，等.WSN中LEACH路由協(xié)議簇頭數(shù)優(yōu)化研究[J].計算機(jī)應(yīng)用研究，2010，27（11），4251-4253 JANG Yang，SUN Liu-lin，AO Wen-jun，et al.Research on optimal cluster-head number of LEACH routing protocol for WSN[J].Application Research of Computers.2010，27（11），4251-4253.

[8]趙秀蘭，許秀蘭，李克清.基于LEACH協(xié)議的差異化分簇路由算法[J].計算機(jī)應(yīng)用研究，2013，30（3）：866-868.ZHAO Xiu-lan，XU Xiu-lan，LI Ke-qing.LEACH-based protocol difference of cluster-based routing algorithm[J].Application Research of Computers，2013，30（3）：866-868.

[9]張強(qiáng)，盧瀟，崔曉臣.基于能量高效的無線傳感器網(wǎng)絡(luò)LEACH協(xié)議改進(jìn)[J].計算機(jī)工程與設(shè)計，2011，32（2）：427-429.ZHANG Qiang，LU Xiao，CUI Xiao-chen.Improvement of low energy adaptive clustering hierarchy routing protocol based on energy-efficient for wireless sensor network[J].Computer Engineering and Design，2011，32（2）：427-429.

[10]Heinzelman W B，et al.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications，2002，1（4）:660-670.