摘 要：分層路由算法是延長(zhǎng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)壽命的一個(gè)重要方法。然而現(xiàn)有的分簇算法大都存在著負(fù)載能量不均衡的問(wèn)題。本文主要針對(duì)經(jīng)典分簇算*EACH，對(duì)其基本思想、分簇機(jī)制和簇的通信方式等作了分析，同時(shí)對(duì)其負(fù)載能量不均衡的問(wèn)題作出改進(jìn)，并用MATLAB進(jìn)行仿真分析。仿真后的結(jié)果表明，改進(jìn)后的算法能夠均衡節(jié)點(diǎn)的能耗，使分簇更加合理，有效延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

　　0 引言

　無(wú)線(xiàn)傳感器網(wǎng)絡(luò)是近年來(lái)信息技術(shù)領(lǐng)域的一個(gè)研究熱點(diǎn)，它融合了傳感器、計(jì)算機(jī)科學(xué)、信號(hào)與信息處理、通信等多個(gè)領(lǐng)域的技術(shù)。作為一個(gè)新興的、正在發(fā)展的技術(shù)領(lǐng)域，業(yè)界對(duì)其研究正在不斷深入。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)為人類(lèi)與客觀物理世界的交互提供了一種新的有效手段，它的諸多特點(diǎn)使其應(yīng)用范圍涉及軍事應(yīng)用、工業(yè)監(jiān)視與控制、醫(yī)療監(jiān)護(hù)、智能家居、物流管理、消費(fèi)電子等諸多領(lǐng)域，具有廣闊的市場(chǎng)及產(chǎn)業(yè)前景。2003 年8 月，美國(guó)《商業(yè)周刊》的技術(shù)*論將無(wú)線(xiàn)傳感網(wǎng)絡(luò)定位成21 世紀(jì)高技術(shù)領(lǐng)域的四大支柱型產(chǎn)業(yè)之一。

　　在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，能量有效性是網(wǎng)絡(luò)性能的一個(gè)重要指標(biāo)。它對(duì)能源消耗有著很?chē)?yán)格的限制，應(yīng)盡可能少地消耗能量以達(dá)到延長(zhǎng)網(wǎng)絡(luò)生命周期的目的。因此，設(shè)計(jì)一種良好的路由協(xié)議，減少不必要的能源消耗是非常必要的。本文主要探討了低能量自適應(yīng)聚類(lèi)協(xié)議（LEACH），指出了LEACH 協(xié)議存在的缺陷，并給出相應(yīng)的解決方案加以?xún)?yōu)化。

　　1 經(jīng)典LEACH 協(xié)議分析

　　1.1 算法描述

　　LEAC(Low-Energy Adaptive CluSTering Hierarchy）協(xié)議是針對(duì)無(wú)線(xiàn)傳感網(wǎng)絡(luò)設(shè)計(jì)的一種低功耗自適應(yīng)分層路由算法，是最早提出的分簇路由協(xié)議。它的基本思想是以循環(huán)的方式隨機(jī)選擇簇頭節(jié)點(diǎn)，其他各節(jié)點(diǎn)根據(jù)接收到的來(lái)自簇頭的信號(hào)強(qiáng)度進(jìn)行集群分組，使得整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)中，從而降低網(wǎng)絡(luò)能源消耗，提高網(wǎng)絡(luò)整體生存時(shí)間。

　　LEACH 協(xié)議定義了“輪”的概念，每一輪由簇的建立和穩(wěn)定狀態(tài)階段組成。在簇的建立階段，首批簇頭的選取是隨機(jī)的。對(duì)于一個(gè)節(jié)點(diǎn)n 而言，為其隨機(jī)選取一個(gè)在0 到1 之間的隨機(jī)數(shù)，若這個(gè)數(shù)字小于一個(gè)門(mén)限值T(n)，則節(jié)點(diǎn)n 就成為本輪的簇頭節(jié)點(diǎn)。門(mén)限T(n)定義如下：

　　其中，P 是網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)目的百分比；r 是當(dāng)前的輪數(shù)；G 是在前1/P 輪中沒(méi)有擔(dān)當(dāng)過(guò)簇頭節(jié)點(diǎn)的節(jié)點(diǎn)集合；符號(hào)mod 是求模運(yùn)算符號(hào)。

　　簇頭節(jié)點(diǎn)選定后，向周?chē)鷱V播自己成為簇頭的信息（ADV），非簇頭節(jié)點(diǎn)根據(jù)接收到的信號(hào)強(qiáng)度來(lái)決定從屬的簇類(lèi)。當(dāng)簇頭收到反饋消息后，便為簇內(nèi)節(jié)點(diǎn)分配時(shí)隙（基于TDMA 方式）。在穩(wěn)定階段，簇內(nèi)節(jié)點(diǎn)在自己時(shí)隙到來(lái)時(shí)刻向簇頭發(fā)送檢測(cè)數(shù)據(jù)，簇頭節(jié)點(diǎn)則將接收到的數(shù)據(jù)后進(jìn)行必要的融合后傳送到基站或匯聚節(jié)點(diǎn)。經(jīng)過(guò)一段時(shí)間的數(shù)據(jù)傳送后，網(wǎng)絡(luò)重新進(jìn)行簇的建立階段，進(jìn)行下一輪的簇重建，如此循環(huán)。

　　1.2 LEACH 算法的局限性

　　LEACH 算法將負(fù)載均勻地分布在整個(gè)網(wǎng)絡(luò)上，大大節(jié)約了通信過(guò)程中的能量損耗。簇頭位置的輪換算法把遠(yuǎn)距離通信的負(fù)載輪流分配給網(wǎng)絡(luò)節(jié)點(diǎn)，可以延長(zhǎng)整個(gè)系統(tǒng)的生存時(shí)間。另外，簇頭節(jié)點(diǎn)在處理數(shù)據(jù)時(shí)用到了數(shù)據(jù)融合和數(shù)據(jù)壓縮技術(shù)，使得傳輸?shù)臄?shù)據(jù)量大大減小。但LEACH 算法同時(shí)也存在著許多不足之處：

　　(1)簇頭選擇問(wèn)題 。LEACH 協(xié)議的簇頭是隨機(jī)產(chǎn)生的，選擇機(jī)制中沒(méi)有考慮節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)已經(jīng)做過(guò)簇頭的次數(shù)。一旦所剩能量較少的節(jié)點(diǎn)成為簇頭，將會(huì)很快耗盡其能量，過(guò)早死亡。其簇內(nèi)成員也將因收不到已死簇頭發(fā)出的信息而不斷地發(fā)送請(qǐng)求信號(hào)，耗費(fèi)大量的能量而導(dǎo)致加速死亡，降低了整個(gè)網(wǎng)絡(luò)的生存時(shí)間。

　　(2)簇頭數(shù)量問(wèn)題。在 LEACH 協(xié)議隨機(jī)選擇簇頭的機(jī)制中，并沒(méi)有控制簇頭的數(shù)量。所以很有可能在某一輪中出現(xiàn)只產(chǎn)生一兩個(gè)簇頭，或產(chǎn)生很多簇頭的情況。若簇頭過(guò)少，則成員節(jié)點(diǎn)要經(jīng)過(guò)很長(zhǎng)的路徑與簇頭進(jìn)行通信，簇頭也將接收大量節(jié)點(diǎn)的信息并向基站進(jìn)行轉(zhuǎn)發(fā)。因此對(duì)每一個(gè)節(jié)點(diǎn)來(lái)說(shuō)都負(fù)擔(dān)過(guò)重；而若產(chǎn)生過(guò)多簇頭，則會(huì)有過(guò)多的節(jié)點(diǎn)與基站通信，降低了網(wǎng)絡(luò)能量的利用率。

　　(3)簇頭分布問(wèn)題。 LEACH 協(xié)議中，雖然在統(tǒng)計(jì)上簇頭是均勻分布的，但是由于簇頭產(chǎn)生的隨機(jī)性，可能會(huì)出現(xiàn)部分區(qū)域簇頭密度大，部分區(qū)域簇頭稀少的現(xiàn)象。

　　2 LEACH 算法的優(yōu)化

　　上述LEACH 算法中的不足，導(dǎo)致了無(wú)線(xiàn)傳感器網(wǎng)絡(luò)負(fù)載能量不均衡。本文主要通過(guò)改進(jìn)簇頭節(jié)點(diǎn)選舉算法來(lái)對(duì)LEACH 協(xié)議進(jìn)行優(yōu)化。主要目標(biāo)是避免能量低的節(jié)點(diǎn)成為簇頭，控制簇頭數(shù)量達(dá)到最優(yōu)，減少簇頭在每輪中分布不均的現(xiàn)象。從而達(dá)到降低系統(tǒng)能量消耗，延長(zhǎng)網(wǎng)絡(luò)生命周期的最終目的。

　　2.1 簇頭選舉機(jī)制的算法改進(jìn)

　　對(duì)于簇頭選舉的改進(jìn)協(xié)議，在文獻(xiàn)[6]中將其閾值作了改進(jìn)：

　　式中，是節(jié)點(diǎn)n 當(dāng)前的剩余能量，是節(jié)點(diǎn)n 的初始能量。

　　分析此式可以看出，由于節(jié)點(diǎn)的剩余能量總是小于其初始能量的，所以改進(jìn)后的門(mén)限值一定比原T(n)值要小。雖然降低了剩余能量少的節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)的可能性，但同時(shí)也減小了整個(gè)網(wǎng)絡(luò)中能夠擔(dān)當(dāng)簇頭節(jié)點(diǎn)的機(jī)會(huì)。針對(duì)這一現(xiàn)象，本文將節(jié)點(diǎn)當(dāng)前剩余能量和當(dāng)前網(wǎng)絡(luò)平均能量?jī)蓚€(gè)參數(shù)綜合考慮進(jìn)去。

　　式中，是節(jié)點(diǎn)當(dāng)前的剩余能量，是當(dāng)前網(wǎng)絡(luò)平均能量。這樣一來(lái)，即保證了節(jié)點(diǎn)被選為簇頭節(jié)點(diǎn)的可能性與其剩余能量的多少相關(guān)，又保證了一輪中選舉出來(lái)的簇頭節(jié)點(diǎn)數(shù)與期望數(shù)相同。

　　在許多文獻(xiàn)中已經(jīng)證實(shí)，網(wǎng)絡(luò)中簇頭的個(gè)數(shù)也是影響網(wǎng)絡(luò)壽命一個(gè)的重要因素，因此本文也將簇頭個(gè)數(shù)的優(yōu)化方案融入了改進(jìn)的協(xié)議。本文當(dāng)中的簇頭最優(yōu)個(gè)數(shù)是采用中的方法確定的，如式(4)所示。

　　式中，是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋區(qū)域面積， N 是區(qū)域內(nèi)節(jié)點(diǎn)數(shù)量， 是信號(hào)放大器的放大倍數(shù)， 是每發(fā)送或接收1比特?cái)?shù)據(jù)，電路自身消耗的能量， 是簇頭節(jié)點(diǎn)的最遠(yuǎn)覆蓋距離。

　　2.2 改進(jìn)算法的具體實(shí)現(xiàn)

　　算法進(jìn)行優(yōu)化后詳細(xì)描述如下。

　　1)在簇的建立階段，簇頭由所有節(jié)點(diǎn)自主決定，在每一輪中自行生成k 個(gè)簇。k 的值由（4）式?jīng)Q定。

　　2)將每個(gè)節(jié)點(diǎn)的剩余能量與上一輪中預(yù)計(jì)的當(dāng)前網(wǎng)絡(luò)平均能量進(jìn)行比較，若剩余能量大于網(wǎng)絡(luò)的當(dāng)前平均能量，則有資格成為簇頭候選節(jié)點(diǎn)；否則只能等待簇頭廣播簇類(lèi)信息。

　　3）能量大于當(dāng)前網(wǎng)絡(luò)平均能量的節(jié)點(diǎn)，判斷自己生成的隨機(jī)數(shù)是否小于門(mén)限值T(n)（即上文中已作改進(jìn)的（3）式），若小于則成為簇頭節(jié)點(diǎn)；若大于門(mén)限值則為成員節(jié)點(diǎn)，等待簇頭發(fā)送告知信息 。至此，簇頭的選舉階段完成。

　　4)成為簇頭的節(jié)點(diǎn)，要以一定的功率發(fā)送簇頭告知信息，但不是全網(wǎng)廣播。該消息只包括簇頭節(jié)點(diǎn)的ID 和消息標(biāo)識(shí)符。在此之后簇頭將等待簇成員的加入信息。

　　5)成員節(jié)點(diǎn)根據(jù)接收到的ADV 消息的信號(hào)強(qiáng)弱來(lái)選擇一個(gè)信號(hào)強(qiáng)的簇頭節(jié)點(diǎn)，并向其發(fā)送一個(gè)請(qǐng)求加入的消息，該消息只包括節(jié)點(diǎn)的ID 和簇頭節(jié)點(diǎn)的ID。

　　6)簇頭花費(fèi)一定時(shí)間來(lái)等待接收成員節(jié)點(diǎn)的加入簇信息，之后將停止接收并根據(jù)所收到的信息數(shù)量來(lái)安排簇內(nèi)節(jié)點(diǎn)發(fā)送消息的TDMA 時(shí)隙。簇頭將TDMA 時(shí)隙以最小功率發(fā)送給簇內(nèi)成員，以確保成員節(jié)點(diǎn)與簇頭節(jié)點(diǎn)通信時(shí)不會(huì)產(chǎn)生沖突。這樣網(wǎng)絡(luò)中某一輪的簇就已建立起來(lái)。圖1 為改進(jìn)后的簇建立階段算法流程圖。

　　7) 簇建立好后，開(kāi)始進(jìn)行數(shù)據(jù)的傳輸階段。每個(gè)節(jié)點(diǎn)按照既定規(guī)則在自己的 TDMA 時(shí)隙內(nèi)發(fā)送收集到的信息?；驹谑盏礁鱾€(gè)簇頭發(fā)送來(lái)的整合信息后，分析傳感到的數(shù)據(jù)并反應(yīng)到上層人機(jī)交流界面上。根據(jù)信息中包含的簇頭和節(jié)點(diǎn)的ID 以及其發(fā)送信息時(shí)的功率強(qiáng)度，估計(jì)下一輪發(fā)送消息時(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)的平均能量，并將此信息廣播到網(wǎng)絡(luò)，為下一輪循環(huán)做準(zhǔn)備。至此，本輪結(jié)束。

圖 1 改進(jìn)后的簇建立階段算法流程圖

　　3 算法仿真與性能分析

　　本文在MATLAB 環(huán)境中對(duì)改進(jìn)的算法進(jìn)行了仿真，通過(guò)對(duì)結(jié)果的分析，來(lái)*價(jià)該算法的性能。

圖 2 改進(jìn)算法的節(jié)點(diǎn)分簇狀態(tài)

圖3 改進(jìn)前后兩種算法的網(wǎng)絡(luò)節(jié)點(diǎn)壽命比較

　　設(shè)置環(huán)境為：傳感器節(jié)點(diǎn)總數(shù)為100，初始能量為0.5J，分布在100 m×l00 m 的正方形區(qū)域中,基站坐標(biāo)位于（x,y）=（50，50）位置。處理數(shù)據(jù)的單位能耗，發(fā)送數(shù)據(jù)的單位能耗，數(shù)據(jù)融合時(shí)的能耗為5nJ/Bit/message。

　　圖2 為改進(jìn)后算法的節(jié)點(diǎn)分簇狀態(tài)。圖中每一個(gè)分塊區(qū)域表示某一輪的一個(gè)簇，每個(gè)簇中都有一個(gè)小星號(hào)表示簇頭，其他的小圓圈表示成員節(jié)點(diǎn)?？梢钥闯鰣D中簇頭分布均勻，且每個(gè)簇頭所管轄的成員節(jié)點(diǎn)數(shù)目及分布狀態(tài)也是均勻穩(wěn)定的。

　　在相同環(huán)境下，將節(jié)點(diǎn)總數(shù)改為200，基站坐標(biāo)位于（x,y）=（50，175）位置，數(shù)據(jù)包長(zhǎng)度為500。圖3 為改進(jìn)前后兩種算法的網(wǎng)絡(luò)節(jié)點(diǎn)壽命比較。橫坐標(biāo)表示網(wǎng)絡(luò)工作的輪數(shù)，縱坐標(biāo)表示存活節(jié)點(diǎn)的數(shù)目。從圖中可以看出，改進(jìn)后的算法節(jié)點(diǎn)死亡率與原算法相比，有一定的延遲。這說(shuō)明本算法通過(guò)對(duì)簇頭選擇機(jī)制的優(yōu)化及簇頭數(shù)目的控制，減少了節(jié)點(diǎn)因能量消耗過(guò)大而過(guò)早死亡的現(xiàn)象，大大延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

　　4 結(jié)語(yǔ)

　　本文針對(duì)LEACH 協(xié)議存在的幾點(diǎn)問(wèn)題，提出了自己的優(yōu)化方案。新算法將當(dāng)前剩余能量和當(dāng)前網(wǎng)絡(luò)平均能量作為參數(shù)引入到簇頭選舉機(jī)制中去，并融入了簇頭最優(yōu)個(gè)數(shù)解決方案。在仿真實(shí)驗(yàn)中，將改進(jìn)前后的算法進(jìn)行對(duì)比分析，結(jié)果證明本優(yōu)化方案能使節(jié)點(diǎn)分布更加合理，較好地均衡網(wǎng)絡(luò)中的能量消耗，在一定程度上延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生命周期。