韓 濤，李訓(xùn)銘

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

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由大量無處不在的、具有通信與計(jì)算能力的微小傳感器節(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ù)、家居自動(dòng)化以及交通控制等。由于WSN的網(wǎng)絡(luò)節(jié)點(diǎn)多是由電池供電，所以其路由算法要考慮高效節(jié)能，才能夠使整個(gè)網(wǎng)絡(luò)有著良好的生存能力。

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

在眾多的無線傳感器網(wǎng)絡(luò)的路由協(xié)議中，LEACH協(xié)議是最為典型的一種分層路由協(xié)議，本文主要針對(duì)LEACH協(xié)議進(jìn)行優(yōu)化，優(yōu)化的中會(huì)借鑒其他路由協(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ò)存活時(shí)間，所以在該算法提出之后不斷的有其他路由協(xié)議引入或者借鑒其分簇思想。而LEACH算法作為經(jīng)典算法，對(duì)它的優(yōu)化和改進(jìn)也在不斷的進(jìn)行。

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

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

式中：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)度決定加入哪個(gè)簇，并告知相應(yīng)的簇頭，完成簇的建立過程。然后，簇頭節(jié)點(diǎn)采用TDMA的方式，為簇內(nèi)成員分配傳送數(shù)據(jù)的時(shí)隙。在穩(wěn)定階段，傳感器節(jié)點(diǎn)將采集的數(shù)據(jù)傳送到簇頭節(jié)點(diǎn)。簇頭節(jié)點(diǎn)對(duì)采集的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合后再將信息傳送給匯聚節(jié)點(diǎn)，匯聚節(jié)點(diǎn)將數(shù)據(jù)傳送給監(jiān)控中心來進(jìn)行數(shù)據(jù)的處理。穩(wěn)定階段持續(xù)一段時(shí)間后，網(wǎng)絡(luò)重新進(jìn)入簇的建立階段，進(jìn)行下一輪的簇重建，不斷循環(huán)。

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

2 歷史改進(jìn)

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

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

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

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

根據(jù)LEACH算法的特點(diǎn)和不足，學(xué)習(xí)了歷來其他研究者的改進(jìn)思想，本文將在以下幾個(gè)方面進(jìn)行改進(jìn)：首先基站根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)分布情況，將節(jié)點(diǎn)按照最優(yōu)簇個(gè)數(shù)分成占節(jié)點(diǎn)總數(shù)4%-6%（仿真中選擇5%）的簇，簇按照地理空間分布，接著根據(jù)簇內(nèi)節(jié)點(diǎn)信息來選擇簇首，首輪簇首選擇之后，簇內(nèi)節(jié)點(diǎn)會(huì)根據(jù)自己的信息來形成一個(gè)（0~1）之間的隨機(jī)數(shù)，在下一輪簇首選擇時(shí)，最大的會(huì)自動(dòng)升級(jí)為簇首。在通信過程中采用單跳與多跳相結(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)的類型相同，具有相同的初始能量，并且能量是有限的，每個(gè)節(jié)點(diǎn)具有一個(gè)獨(dú)一無二的ID。

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

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

3.1.2 能量模型

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

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

無線通訊中信號(hào)傳輸增益為

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

3.3 簇首選取和輪換

在分簇完成之后，由于節(jié)點(diǎn)同構(gòu)且具有相同的初始能量，所以每個(gè)節(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時(shí)隙，子節(jié)點(diǎn)在自己的時(shí)隙內(nèi)進(jìn)行數(shù)據(jù)傳輸，其余時(shí)間通訊模塊則進(jìn)入sleep狀態(tài)，等待下次被喚醒。普通節(jié)點(diǎn)發(fā)送信息包含自己的ID和剩余能量，簇首節(jié)點(diǎn)將接受到的數(shù)據(jù)進(jìn)行融合后發(fā)送給基站。基站接收到信息之后，根據(jù)剩余能量和位置信息來生成一個(gè)輪換因子μ，它由下式?jīng)Q定：

式中ke和ks是常數(shù)，由能量消耗決定。Elast表示節(jié)點(diǎn)的剩余能量，d是節(jié)點(diǎn)到基站的距離。在下一輪的簇首選取中，簇內(nèi)輪換因子最大的可以直接升級(jí)成為簇首節(jié)點(diǎn)。輪換因子的確定并不介意某個(gè)節(jié)點(diǎn)在上一輪中已經(jīng)擔(dān)任過簇首節(jié)點(diǎn)，因?yàn)榭紤]了剩余能量，如果一個(gè)節(jié)點(diǎn)的剩余能量遠(yuǎn)多于簇內(nèi)的其他節(jié)點(diǎn)，在擔(dān)任一次簇首之后，仍然是所在簇內(nèi)剩余能量最大的，會(huì)繼續(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í)，能量消耗會(huì)急劇增加，并且超過了數(shù)據(jù)接收，因此，雖然數(shù)據(jù)接收也是一筆不小的消耗，但是在進(jìn)行超遠(yuǎn)距離通訊時(shí)選擇多跳接力通訊仍能減少數(shù)據(jù)傳輸?shù)哪芰肯?。本文?duì)LEACH算法的數(shù)據(jù)傳輸模式進(jìn)行兩方面的改進(jìn)：第一個(gè)方面是多跳與單跳結(jié)合的數(shù)據(jù)傳輸方式，這個(gè)在以前的LEACH算法改進(jìn)中也有見到，本文與以前有所不同的是，并不會(huì)總是選擇距離基站較近的簇首擔(dān)任下一跳的節(jié)點(diǎn)，而是在較近的區(qū)域選擇一批具有較大剩余能量的節(jié)點(diǎn)進(jìn)行多跳，并且會(huì)計(jì)算成本，只有接力通訊方式總成本比直接通訊消耗減少超過一定比例時(shí)才選擇多跳，這個(gè)比例是與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ù)傳輸時(shí)，距離較遠(yuǎn)簇能量消耗要比距離較近簇大。多跳接力時(shí)，距離基站較近的節(jié)點(diǎn)會(huì)被選為下一跳的節(jié)點(diǎn)，則會(huì)增加距離基站較近的節(jié)點(diǎn)的能耗。因此，在數(shù)據(jù)通訊時(shí)，基站將根據(jù)剩余能量進(jìn)行對(duì)比，在降低系統(tǒng)級(jí)能耗與平衡各個(gè)節(jié)點(diǎn)能耗之間選擇一個(gè)平衡，則可以最大限度延長網(wǎng)絡(luò)整體的壽命。

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

4 算法仿真及分析

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

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

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

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

5 結(jié)束語

文中對(duì)LEACH的改進(jìn)相對(duì)于原算法性能更優(yōu)，通過動(dòng)態(tài)和靜態(tài)簇頭選取相結(jié)合的方式，降低了簇首選取過程中的能量消耗，參考節(jié)點(diǎn)分布信息來設(shè)置每個(gè)簇的位置和簇內(nèi)節(jié)點(diǎn)數(shù)，并且根據(jù)距基站的距離和剩余能量來選取簇頭，使得簇首分布較傳統(tǒng)分布更為均勻，并且平衡了能量負(fù)載，不僅有效避免個(gè)別節(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é)報(bào)，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é)報(bào)，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ì)算機(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ì)算機(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ì)算機(jī)工程與設(shè)計(jì)，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.