吳標，余劍，易仁杰

（電子工程學院，合肥230037）

基于節(jié)點剩余能量的分時分簇LEACH改進算法*

吳標，余劍，易仁杰

（電子工程學院，合肥230037）

針對無線傳感網(wǎng)絡中高效路由協(xié)議的設計問題，基于傳感器節(jié)點的剩余能量提出一種分時分簇的改進LEACH算法。算法通過分時分簇方式，有效克服了傳統(tǒng)LEACH算法中簇首數(shù)目不穩(wěn)定的缺陷，且不會額外增加網(wǎng)絡的能耗，使得簇首在整個網(wǎng)絡中的分布以及網(wǎng)絡的能量消耗更加均衡，有效延長了傳感器網(wǎng)絡的正常工作時間。仿真實驗驗證了改進算法的有效性。

無線傳感器網(wǎng)絡，分時分簇，LEACH，網(wǎng)絡正常工作時間

0　引言

無線傳感器網(wǎng)絡（Wireless Sensor NetWorks，WSN）［1］是由眾多傳感器節(jié)點組成并以自組織方式相互協(xié)同工作的分布式感知網(wǎng)絡，傳感器節(jié)點負責完成實時監(jiān)測、感知和采集各種環(huán)境或監(jiān)測對象的信息。每個傳感器節(jié)點由電池供電，其運算、存儲、通信能力有限，因此，如何高效使用能量來最大化網(wǎng)絡生命周期，成為路由協(xié)議設計時首先考慮的問題［2-3］。

傳感器網(wǎng)絡的路由協(xié)議主要分為平面路由協(xié)議和分層路由協(xié)議，由于平面路由協(xié)議需要維護很大的路由表，需要較大的存儲空間，網(wǎng)絡的擴展性差，不適于在大規(guī)模的傳感網(wǎng)絡中應用。分層路由協(xié)議就是將網(wǎng)絡劃分為若干個簇，每個簇通過一定的算法選擇一個簇首，其余為非簇首節(jié)點。非簇首節(jié)點負責收集其所感知的網(wǎng)絡消息并傳遞給簇首，簇首收集處理本簇成員的消息后傳遞給匯聚節(jié)點，較非簇首節(jié)點能耗較大。LEACH（LowEnergy AdaptiveClusteringHierarchy）［4］作為WSN網(wǎng)絡最先提出的高效能分簇路由協(xié)議，因其采用節(jié)點輪轉(zhuǎn)擔當簇首的方法使得整個網(wǎng)絡能耗更加均衡，從而達到延長網(wǎng)絡生命周期的目的。文獻［5-7］改進簇首選舉的策略，在選取簇首時將節(jié)點的能量、距離匯聚節(jié)點的距離等考慮進去，使簇首數(shù)目盡可能接近最佳比例。LEACH及其改進協(xié)議［5-8］較平面路由協(xié)議，網(wǎng)絡能耗更低、生命周期更長，但產(chǎn)生簇首的數(shù)目波動性較大，每輪中能達到最佳簇首的比例很小［9］，文獻［8］中雖然簇首比例更為接近最佳比例，卻增加網(wǎng)絡整體的能耗。另外，在很多對可靠性要求比較高的應用中要求網(wǎng)絡的所有節(jié)點均存活才能正常工作［10］。因此，網(wǎng)絡第一個節(jié)點死亡的時間是網(wǎng)絡正常工作的時間，是衡量算法有效性的重要指標。如何改進LEACH算法簇首選舉機制，穩(wěn)定的簇首數(shù)目、均衡化簇首分布和網(wǎng)絡負載成為延長網(wǎng)絡正常工作時間的關鍵。

本文針對LEACH算法產(chǎn)生簇首數(shù)目不穩(wěn)定的問題，提出一種基于節(jié)點剩余能量的分時分簇路由算法LEACH-RE（LEACH based on theResidual Energy），且在簇首選舉策略中采用自適應方式均衡化簇首分布，均衡了網(wǎng)絡的負載，延長了網(wǎng)絡正常工作時間，仿真實驗對結(jié)果進行了驗證。

1　LEACH算法概述

LEACH算法定義了“輪”（Round）的概念，網(wǎng)絡按“輪”運行，傳感網(wǎng)絡每個節(jié)點根據(jù)自身產(chǎn)生的隨機數(shù)決定是否成為簇首，每輪的工作過程分成兩個階段：簇建立階段和穩(wěn)定階段。

LEACH網(wǎng)絡結(jié)構(gòu)模型具有以下特點：①匯聚節(jié)點位于網(wǎng)絡之外，處理能力和能量不受限制。②所有的傳感器節(jié)點具有相同的有限初始化能量，且每個節(jié)點有唯一的ID號作為標識。③無線信道是對稱的，即節(jié)點A向節(jié)點B發(fā)送信息的能耗跟節(jié)點B向節(jié)點A發(fā)送相同長度信息的能耗是相同的。④簇內(nèi)和簇間均采用單跳通信。⑤節(jié)點擔當發(fā)送者時，可根據(jù)接收信號強度估算相對距離自動調(diào)整發(fā)射的功率以節(jié)省能量［11］。

1.1網(wǎng)絡能耗模型

圖1　網(wǎng)絡能量模型

網(wǎng)絡能耗模型的結(jié)構(gòu)如圖1所示［12］，網(wǎng)絡的能耗主要集中在信號發(fā)射、接收和路徑損耗上。信號在路徑中的衰減模型分為自由空間和多徑傳輸兩種，這里將在信道傳播損耗折合到發(fā)送端信號放大電路里。這樣發(fā)送端能耗主要由信號發(fā)射電路和信道折合放大電路組成。

發(fā)射端的能耗主要由信號發(fā)射電路和信道折合放大電路構(gòu)成，發(fā)送k bits信號的能耗由式（1）獲取：

其中，Eelec為節(jié)點電路損耗的能量，εfs為自由空間傳輸損耗，εmp為多徑衰減傳輸損耗，d0為自由空間傳輸模式與多徑衰減模式的切換閾值，可通過式（2）得到：

接收端接收k bits數(shù)據(jù)電路的能耗為：

1.2簇建立階段

簇建立階段主要完成簇首選舉和成簇兩個過程。簇首選舉過程中節(jié)點采取隨機輪轉(zhuǎn)的方式擔當簇首，將網(wǎng)絡的整體能耗分攤到每個節(jié)點。選舉過程中，根據(jù)式（4）每輪設定一個閾值T（n）。每個節(jié)點自主地產(chǎn)生一個［0，1］的隨機數(shù)，若該隨機數(shù)小于T（n），則此節(jié)點在本輪中擔當簇首，同時將該消息以廣播的形式告知到整個網(wǎng)絡；否則，此節(jié)點為非簇首節(jié)點，等待接收其他簇首的消息。節(jié)點一旦擔當簇首，在接下來的1/p-1輪中，不再擔當簇首。式中，p為簇首的比例，通常取5%［4］，r表示網(wǎng)絡當前運行的輪數(shù)，G表示在最后的1/p輪中還沒有成為簇首節(jié)點的集合。在r=0時每個節(jié)點都以p的概率成為簇首，經(jīng)過1/p-1輪之后閾值T值變?yōu)?。

簇首選舉過程完成后，成為簇首的節(jié)點廣播Be-Head消息到整個網(wǎng)絡，該消息主要包括簇首的ID、位置等信息。非簇首節(jié)點保持偵聽狀態(tài)，收到所有簇首Be-Head消息以后，根據(jù)接收到消息的強弱選擇強度最大的簇，并向?qū)拇厥追祷豃oin-Msg消息，確保加入距自身最近簇首。該消息比較短小，一般包含節(jié)點ID和簇首節(jié)點的ID。簇首節(jié)點收集完本簇的Join-Msg消息以后，根據(jù)成員數(shù)目按照TDMA方式為本簇的成員分配時隙，建立時隙表。然后將時隙表作為Response-Msg應答消息廣播給其成員，非簇首節(jié)點僅在其分配的時隙內(nèi)與其對應簇首進行通信，完成網(wǎng)絡的成簇過程。

1.3穩(wěn)定階段

網(wǎng)絡成簇以后，進入了穩(wěn)定的數(shù)據(jù)傳輸階段，該階段占每輪的大部分時間。簇內(nèi)通信中，非簇首節(jié)點根據(jù)Response-Msg消息明確被分配的時隙，在被分配的時隙內(nèi)將收集的數(shù)據(jù)發(fā)送到對應簇首，其他時隙內(nèi)該節(jié)點處于休眠狀態(tài)以節(jié)省能量，確保簇內(nèi)數(shù)據(jù)傳輸不會發(fā)生沖突。在整個過程中簇首始終處于開啟狀態(tài)，以接收本簇成員的數(shù)據(jù)。將本簇成員數(shù)據(jù)和自身采集數(shù)據(jù)融合以后，簇首采用載波偵聽同步CSMA的方式將融合后的數(shù)據(jù)發(fā)送到匯聚節(jié)點，避免了簇首同時向匯聚點發(fā)送數(shù)據(jù)時的阻塞現(xiàn)象。所有簇首完成數(shù)據(jù)傳送之后，新的一輪開始，網(wǎng)絡重新進入簇建立階段。

2　LEACH-RE算法描述

LEACH算法動態(tài)隨機選擇每輪的簇首，使所有節(jié)點輪轉(zhuǎn)擔當簇首。該算法動態(tài)周期性地重組網(wǎng)絡，很好地適應了網(wǎng)絡變化的要求，具有路由管理簡單、穩(wěn)定性強、易于網(wǎng)絡的拓展等優(yōu)點，很大程度上均衡了能量在所有節(jié)點的消耗。但是簇首選舉過于隨機，導致簇首數(shù)目波動較大，選出簇首在網(wǎng)絡中分布隨機，均不利于延長網(wǎng)絡的生命周期。

2.1網(wǎng)絡結(jié)構(gòu)模型

采用與LEACH算法相似的網(wǎng)絡模型。N個傳感器節(jié)點在網(wǎng)絡內(nèi)隨機均勻分布，網(wǎng)絡按“輪”周期性地運行。LEACH-RE網(wǎng)絡模型除了具備LEACH網(wǎng)絡5個特點以外，還要求各節(jié)點和匯聚節(jié)點之間時間是同步的。

網(wǎng)絡的能耗主要集中在數(shù)據(jù)傳輸中，本算法采用文獻［12］的網(wǎng)絡能量模型。LEACH-RE算法主要考慮節(jié)點發(fā)送數(shù)據(jù)、接收數(shù)據(jù)和簇首融合數(shù)據(jù)的能耗，網(wǎng)絡初始化、睡眠模式等耗能均較小，可忽略。

2.2LEACH-RE的工作過程

與LEACH算法類似，LEACH-RE算法將工作過程也分成2個階段：簇建立階段和穩(wěn)定階段。網(wǎng)絡布置完畢之后，匯聚節(jié)點以較大功率向整個網(wǎng)絡發(fā)射網(wǎng)絡消息，包含匯聚節(jié)點的位置信息、網(wǎng)絡簇首的比例、成簇半徑等信息。節(jié)點從該消息中獲悉自身與匯聚節(jié)點的距離，擔當簇首時根據(jù)這個距離選擇合適的功率檔與匯聚節(jié)點進行數(shù)據(jù)通信。成簇半徑由匯聚節(jié)點在網(wǎng)絡運行之前廣播告知，簇的平均半徑可由式（5）確定。簇首間距一定不小于2r，為保證簇首分布不過于密集，成簇半徑設定為2r。

簇建立階段主要完成簇首的選舉和網(wǎng)絡的組建。首輪中節(jié)點的初始能量是相同的，網(wǎng)絡采用LEACH的方法完成簇建立階段，2.2節(jié)已詳細敘述。非首輪采用LEACH-RE算法完成簇建立階段，具體過程見圖2虛線框的內(nèi)容。非首輪簇首選舉采用“能者多勞”的原則，即剩余能量越多擔當簇首次數(shù)越多，摒棄了LEACH簇首輪轉(zhuǎn)導致個別節(jié)點早衰的劣勢。每輪中剩余能量越多的節(jié)點延時越小，確保在簇首選舉過程中剩余能量較大的節(jié)點擔當簇首。節(jié)點根據(jù)自身剩余能量的情況由式（6）獲取本輪應當延遲的時間，剩余能量越多的節(jié)點時延越小，率先達到時延的節(jié)點成為簇首并在其成簇半徑2r內(nèi)廣播Be-Head消息；反之，時延越大。

其中，Tm表示網(wǎng)絡的最大時延，EnRe（i）表示節(jié)點當前剩余能量，EnIni（i）表示節(jié)點的初始化能量。

到達指定時延的節(jié)點向外發(fā)射Be-Head消息，該消息比較短小，包括：簇首ID和簇首標示（表明該消息為Be-Head消息）。簇首根據(jù)成簇半徑選擇合適的發(fā)射功率檔發(fā)射Be-Head消息，保證簇首不會過于密集分布在網(wǎng)絡的某個區(qū)域，等待其他節(jié)點的加入消息。簇首成簇半徑內(nèi)的其他尚未達到時延的節(jié)點收到該消息后自動放棄本輪成為簇首的競爭，同時打開接收器，等待接收其他簇首的Be-Head消息。

圖2　LEACH-RE工作過程

放棄競爭的節(jié)點在本輪中成為非簇首節(jié)點，在接收多個Be-Head消息后，根據(jù)接收信號的強弱決定加入到哪個簇，確保加入到距自身最近的簇首。在每個節(jié)點都確定加入到簇之后，所有節(jié)點均采用CSMA MAC協(xié)議發(fā)送Join-Msg消息，防止多個節(jié)點同時向簇首發(fā)送Join-Msg消息時發(fā)生消息阻塞。Join-Msg消息比較短小，一般包含節(jié)點ID和簇首節(jié)點的ID。簇首收集完本簇成員的所有Join-Msg消息后，基于簇內(nèi)成員的數(shù)目，采用TDMA的方式為每個節(jié)點分配數(shù)據(jù)傳輸?shù)臅r隙。時隙表構(gòu)建完成后，簇首將時隙表作為Response-Msg消息以廣播的方式告知本簇內(nèi)的所有成員，同意加入本簇的請求。簇內(nèi)成員節(jié)點僅在自身分配的時隙內(nèi)處于工作狀態(tài)，而在其他節(jié)點傳輸數(shù)據(jù)的時隙內(nèi)始終處于休眠狀態(tài)以節(jié)省能量。圖2是LECH-RE一輪的工作過程，每輪結(jié)束后按該流程循環(huán)往復。該算法在非首輪中將簇建立階段的簇首選擇與成簇過程合二為一，以“能者多勞”為原則，確保能量較高節(jié)點成為簇首，并利用簇首Be-Head消息均衡化成簇的大小，使整個網(wǎng)絡的能耗更為均勻。與LEACH相比，該算法實現(xiàn)了簇首數(shù)目的穩(wěn)定和簇大小的均勻化，且未增加網(wǎng)絡的能耗。

穩(wěn)定傳輸階段主要是完成本輪數(shù)據(jù)傳輸，采用與LEACH相同的工作方式，見1.3節(jié)。

3　仿真與結(jié)果分析

采用MATLAB R2013b作為實驗仿真平臺，對傳統(tǒng)LEACH分簇路由算法、LEACH-ED算法［5］以及本文提出的LEACH-RE算法的能量均衡性進行仿真和性能對比分析。為減小單次實驗的偶然性，進行100次蒙特卡羅實驗，實驗結(jié)果進行統(tǒng)計求平均。

本文的仿真環(huán)境設置如表1所示。對無線傳感器網(wǎng)絡的性能參數(shù)的分析有很多［13］，本文以輪為單位，針對網(wǎng)絡每輪生成簇首數(shù)目的分布情況、網(wǎng)絡能量的消耗情況和網(wǎng)絡存活節(jié)點數(shù)隨輪的變化情況對新算法的性能進行對比分析，這是網(wǎng)絡正常工作時間即第一個節(jié)點死亡時間作為衡量網(wǎng)絡節(jié)點存活狀況的重要指標。

表1　仿真參數(shù)設置

3.1簇首分布情況在傳感器網(wǎng)絡運行的過程中隨機選取100輪對LEACH算法、LEACH-ED［5］以及本文提出的LEACH-RE算法的簇首數(shù)目進行統(tǒng)計，網(wǎng)絡中簇首的比例為5%。3種算法在相同的仿真環(huán)境下進行，參數(shù)設置見表1。統(tǒng)計的結(jié)果如圖3～圖5所示，橫軸表示簇首的數(shù)目，縱軸表示輪數(shù)的統(tǒng)計。LEACH算法中節(jié)點是采用隨機數(shù)決定成為簇首與否，導致網(wǎng)絡產(chǎn)生的簇首數(shù)目具有很大的不確定性。從圖3可以看出，采用LEACH產(chǎn)生簇首的數(shù)目波動性很大，分布在1到10之間；LEACH-ED在簇首選舉中將能量考慮進去，使簇首過多或過少的情況明顯減少，見圖4；由圖5可知，LEACH-RE算法產(chǎn)生簇首的數(shù)目更為穩(wěn)定，較LEACH算法、LEACH-ED算法波動性明顯小，更有利于網(wǎng)絡總體能耗的減少。

圖3　LEACH簇首分布統(tǒng)計圖

圖4LEACH-ED簇首分布統(tǒng)計圖

3.2網(wǎng)絡能耗情況

圖6　每輪能量消耗

圖7　每輪能耗的方差

選取網(wǎng)絡運行的前100輪研究每輪網(wǎng)絡的能耗情況，圖6和圖7分別是每輪所有節(jié)點能耗和能耗方差隨輪數(shù)的變化情況，橫軸表示網(wǎng)絡運行的輪數(shù)，縱軸表示網(wǎng)絡每輪的能耗或者能耗的方差。本文的LEACH-RE算法實現(xiàn)了簇首在網(wǎng)絡中均勻分布，從圖6可知較LEACH算法、LEACH-ED算法LEACH-RE算法每輪的能耗更為均衡，波動性較小；圖7比較了3種算法在網(wǎng)絡運行中耗能方差的情況，更明顯地說明了LEACH-RE在每一輪的能耗更為均衡、穩(wěn)定，更有利于均衡化網(wǎng)絡的能耗，延長網(wǎng)絡的正常工作時間。

圖8　網(wǎng)絡節(jié)點存活數(shù)目隨輪數(shù)的變化

3.3網(wǎng)絡運行情況

相同的網(wǎng)絡仿真環(huán)境下，LEACH算法、LEACH-ED算法、LEACH-RE算法節(jié)點的存活數(shù)目隨仿真輪數(shù)的變化情況如圖8所示，橫軸表示仿真進行的輪數(shù)，縱軸表示網(wǎng)絡節(jié)點存活的數(shù)目。在對可靠性要求比較高的應用場景中要求所有節(jié)點均存活時傳感器網(wǎng)絡才能正常工作，一旦有節(jié)點死亡，網(wǎng)絡的工作就不再具有意義。因此，這里將第一個節(jié)點死亡時網(wǎng)絡進行到的輪數(shù)作為考量算法效能的重要指標。從圖中可看出LEACH算法第一個節(jié)點死亡的輪數(shù)為776，LEACH-ED算法第一個節(jié)點死亡的輪數(shù)為835，LEACH-RE算法第一節(jié)點死亡輪數(shù)為900。可知，LEACH-RE算法較LEACH算法和LEACH-ED算法網(wǎng)絡的正常工作時間分別延長了15.9%和7.8%。主要是改進了簇首的選舉策略，保證了高能節(jié)點被選為簇首且均衡化了簇首在網(wǎng)絡中的分布，放棄了簇首輪轉(zhuǎn)機制而采用“能者多勞”機制，從而達到均衡化網(wǎng)絡節(jié)點的能耗，延長網(wǎng)絡正常工作的時間。

LEACH-RE算法簇內(nèi)成員與簇首之間、簇首與匯聚節(jié)點之間均采用單跳的方式進行數(shù)據(jù)傳輸，由3.2節(jié)可獲取3種算法一輪能耗的平均值。網(wǎng)絡的總能量為50J，從而得到3種算法的理論最長輪數(shù)和實際達到輪數(shù)占理論最長輪數(shù)的百分比，具體數(shù)據(jù)如表2所示。由表2可知LEACH算法網(wǎng)絡正常工作的時間可達到理論最大值的79.2%，LEACH-ED算法網(wǎng)絡正常工作的時間可達到理論最大值的86.9%，而改進LEACH-RE算法的正常工作時間可達到理論最大值的91.0%，驗證了LEACH-RE算法對于提高網(wǎng)絡正常工作時間的有效性。

表2　算法比較

4　結(jié)論

本文主要針對可靠性要求比較高的應用場景，改進LEACH算法產(chǎn)生簇首不穩(wěn)定和成簇不均勻的問題，采用分時分簇方式使簇首在網(wǎng)絡中的均勻分布，且不額外增加網(wǎng)絡的能耗，均衡化網(wǎng)絡的負載。仿真表明LEACH-RE算法較LEACH算法在延長網(wǎng)絡正常工作時間和均衡網(wǎng)絡能量消耗有了很大的改進，驗證了其延長網(wǎng)絡正常工作時間的有效性。

［1］趙麗霞，紀松波.無線傳感器網(wǎng)絡在智能交通中的應用［J］.物聯(lián)網(wǎng)技術(shù)，2012，2（6）：25-27.

［2］李建洲，王海濤，陶安.一種能耗均衡的WSN分簇路由協(xié)議［J］.傳感技術(shù)學報，2013，26（3）：396-401.

［3］AKHTAR A M，NAKHAI M R.Power aware cooperative routing in wireless mesh networks［J］.Communications Letters，IEEE，2012，16（5）：670-673.

［4］HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks［C］//Systemsciences，2000. Proceedings of the 33rd annual Hawaii international conferenceon.IEEE，2000，2:10.

［5］顧相平，孫彥景，錢建生.一種改進的無線傳感器網(wǎng)絡LEACH-ED算法［J］.傳感技術(shù)學報，2008，21（10）：1770-1774.

［6］劉玉華，趙永鋒，許凱華，等.無線傳感器網(wǎng)絡LEACH協(xié)議的改進［J］.計算機工程與應用，2010，46（17）：117-120.

［7］唐甲東，蔡明.基于LEACH協(xié)議的能耗均衡路由算法［J］.計算機工程，2013，39（7）：134-136.

［8］HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNANH.Anapplication-specific protocol architecturefor wirelessmicrosensornetworks［J］.WirelessCommunications，IEEE Transactionson，2002，1（4）：660-670.

［9］陳樹，徐圓.基于分簇和覆蓋優(yōu)化的改進LEACH協(xié)議［J］.計算機工程，2014，40（11）：97-100.

［10］DIAMOND S M，CERUTI M G.Application of wireless sensor network to military information integration［C］//Industrial Informatics，2007 5th IEEE International Conferenceon.IEEE，2007，1：317-322.

［11］CHEN G，LI C F，YE M，et al.An unequal cluster-based routing strategy in wireless sensor networks［J］.Wireless Networks（JS），2009，15（2）：193?207.

［12］吳小兵，陳貴海.無線傳感器網(wǎng)絡中節(jié)點非均勻分布的能量空洞問題［J］.計算機學報，2008，31（2）：253-261.

［13］萬青苗，張浩平，王強，等.無線傳感器網(wǎng)絡LEACH協(xié)議的改進研究［J］.電腦知識與技術(shù)，2012，32（8）：7679-7701.

Atime-division and Clusteringalgorithm of LEACH Based on Residual Energyof Sensor Nodes

WU Biao，YU Jian，YI Ren-jie
（401 Laboratory，Electronic Engineering Institute，HeFei 230037，China）

For the problemof effective routing protocol in wireless sensor network，this paper puts forwardan time-division and clusteringalgorithm of LEACH based on the Residual Energy（LEACHRE）of sensor nodes.By time-cluster and clustering method，LEACH-RE solves the problem of unstable cluster-head number that exists in LEACH algorithm without increasing the energy consumption of the network.In addition，the distribution of clusters and energy consumption in the network are well balanced.The normal lifetime of the sensor network is effectively extended.Simulations improve the effectiveness of the algorithm.

wirelesssensornetworks，time-divisionandclustering，LEACH，network normal lifetime

E917

A

1002-0640（2016）10-0084-05

2015-08-13

2015-09-16

電子工程學院院控基金資助項目（KY13A206）

吳標（1991-），男，安徽亳州人，碩士研究生。研究方向：無線傳感器網(wǎng)絡節(jié)能路由協(xié)議。