摘  要： 根據(jù)LEACH協(xié)議的特點和局限性對其進行了改進,，提出了一種LEACH_EH（LEACH EAHANCE）算法,。它使用K_MEANS算法對簇進行一次性分簇，之后結合節(jié)點到簇內質心距離與節(jié)點自身剩余能量選舉出簇頭,。它將簇形成的順序由先簇頭后成簇變?yōu)橄瘸纱睾蟠仡^,，形成一次分簇多次選舉簇頭的模式。通過MATLAB進行仿真,，實驗結果表明,，改進后的算法比原來的協(xié)議在節(jié)點能量均衡方面有了較大的提升，延長了網(wǎng)絡生存周期,。

　　關鍵詞： WSN路由協(xié)議,；LEACH；K_MEANS算法,；MATLAB仿真

　　當前,，無線傳感器由于技術的發(fā)展得到更加廣泛的應用，針對無線傳感器網(wǎng)絡（WSN）[1]的研究也越來越多,，無線傳感器網(wǎng)絡路由協(xié)議[2]成為了一個重點研究對象,。按照時間先出現(xiàn)了Flooding算法、SPIN算法,、SAR算法和定向擴散（Directed Diffusion）等平面路由算法,，其后又研究出了LEACH算法、TEEN算法,、HEED算法[3]及PEGASIS算法等層次路由算法,。LEACH算法由于其不同于以往路由算法的指導思想成為以后層次路由算法設計時的參考標準,，針對LEACH算法的自身局限性進行改進也成為了一個研究熱點。參考文獻[4]提出了一種休眠簇頭的算法,，它一次性選出所需要的工作簇頭和休眠簇頭,，并且只分一次簇，減少了LEACH協(xié)議中多次選舉簇頭和分簇帶來的能量耗損,。參考文獻[5]提出了LEACH-C算法,，它提出各個節(jié)點把自身的剩余能量和位置信息發(fā)送給Sink節(jié)點，由Sink節(jié)點進行分簇,。參考文獻[6]在簇頭選取中加入剩余能量,，并且結合平面拓撲、層次拓撲和基于位置拓撲的優(yōu)點形成混合型拓撲類型,，修改LEACH協(xié)議中單輪成簇為雙輪成簇,。參考文獻[7]提出了一種名為LEACH_SD（LELACH_Sensoring Denomina-tion）的協(xié)議，它提出了基于網(wǎng)絡覆蓋的路由生成思想,。參考文獻[8]基于節(jié)點的剩余能量和位置對LEACH協(xié)議進行了改進,，將選簇過程分為臨時簇頭選擇和正式簇頭，把傳感器節(jié)點的節(jié)點剩余能量值和幾何平均位置作為選簇的重要因素,，在此基礎上選出區(qū)域內最佳簇頭,。參考文獻[9]提出根據(jù)節(jié)點剩余能量進行篩選，剩余節(jié)點能量較低的暫時不進行采樣,，以此減少參加采樣節(jié)點數(shù)量,，其次對簇形成階段不正常的節(jié)點進行放棄處理。以上改進方法在特定情況下都能夠延長網(wǎng)絡的生命周期,。

　　本文結合LEACH協(xié)議的特點,，提出改變原來LEACH協(xié)議先選擇簇頭后進行分簇的順序，而是先進行均勻分簇,，而后進行簇頭選舉的過程,。

　　1 LEACH協(xié)議

　　1.1 算法介紹

　　LEACH算法是由MIT的Chandrakasan等人為無線傳感器網(wǎng)絡專門設計的低功耗自適應聚類路由算法（Low Energy Adaptive Clustering Hierachy）。它的基本思想是：將協(xié)議的運行過程分成一個個輪（round）,，每一輪由簇形成階段和簇的穩(wěn)定工作階段組成[8],。在簇的形成階段，每一個節(jié)點都會生成一個隨機數(shù),，然后與一閾值T（n）進行比較,，閾值T（n）計算式為：

　　T（n）=，n∈G0             ,，n?埸G（1）

　　其中,，P為期望的簇頭節(jié)點的百分比，即每個節(jié)點成為簇頭節(jié)點的概率；r為當前輪數(shù),；G是最近1/P輪為當選簇頭的節(jié)點集合,。

　　如果該節(jié)點的隨機數(shù)小于閾值T（n）,，則該節(jié)點就當選為簇頭節(jié)點,，同時廣播自己成為節(jié)點的控制幀，所有當選簇頭的節(jié)點廣播完控制幀后,，未當選的普通節(jié)點根據(jù)收到的控制幀信號強度選擇加入到相應的簇頭,，發(fā)送給該簇頭加入控制幀。該過程結束后,，簇頭節(jié)點整理自己接收到的加入控制幀,，采用TDMA的方式為相應的簇內節(jié)點分配發(fā)送時隙，簇就形成了,。

　　在簇穩(wěn)定工作階段,，簇內節(jié)點將收集到的數(shù)據(jù)在自己的時隙內發(fā)送給簇頭節(jié)點，簇頭節(jié)點將收集到簇內節(jié)點的數(shù)據(jù)進行處理,、融合,，然后將融合后的數(shù)據(jù)發(fā)送給Sink節(jié)點，由Sink節(jié)點再發(fā)送給遠程數(shù)據(jù)處理中心進行處理,。這個過程重復進行數(shù)次,，之后，再進行簇的形成,，以此往復,，不斷循環(huán)。

　　LEACH協(xié)議在簇形成階段,，每個節(jié)點都會輪流地成為簇頭節(jié)點,，前面幾輪已經(jīng)當選為簇頭的節(jié)點，在后面的若干輪都無法再擔任簇頭,，這就使得所有節(jié)點都能夠作為簇頭來分擔作為簇頭時能量消耗較大的問題,。使得能量消耗能夠均衡地分攤到各個節(jié)點，各個節(jié)點的能量消耗就能夠更加一致,，有效延長了網(wǎng)絡的生存周期,。

　　1.2 LEACH算法的不足

　　由于在簇頭節(jié)點形成過程中，節(jié)點當選為簇頭的概率是一樣的,。這樣,，可能會出現(xiàn)節(jié)點剩余能量較多的節(jié)點每次都在比較靠后的輪次當選簇頭節(jié)點，而節(jié)點剩余能量較少的節(jié)點在比較靠前的輪次當選簇頭,，一些節(jié)點的能量消耗就會過大,。同時，如果一輪中選舉出的簇頭節(jié)點距離不合適，勢必會造成簇頭節(jié)點內的簇內節(jié)點數(shù)目不均衡,；或者是簇內節(jié)點到簇頭節(jié)點的距離過大,，或者是簇頭節(jié)點過多或者過少。

　　上述幾種情況都會加重個別簇頭節(jié)點的負擔,，不利于均衡節(jié)點能耗,。本文提出了一種基于K_MEANS算法的先分簇，再選舉簇頭的改進算法,。該算法首先隨機選取幾個簇頭,，然后使用K_MEANS算法進行迭代，找出最優(yōu)或者部分最優(yōu)的分簇形式,，接著根據(jù)節(jié)點剩余能量和距離該簇質心的距離選舉出簇頭,，之后進入簇的穩(wěn)定工作階段。

　　LEACH算法是先選舉簇頭再形成簇,，這種成簇過程帶有很大的隨機性,，直接導致簇頭距離不合適，各個簇內節(jié)點數(shù)目不均衡,。改進算法則使用與之完全相反的方式生成簇,。首先通過K_MEANS算法進行分簇，它通過幾次迭代過程即可把拓撲區(qū)域內的節(jié)點盡可能地均分成不同的簇,。各個簇內節(jié)點距離近,，簇間較遠。這樣簇內節(jié)點到選舉出的簇頭節(jié)點的距離自然就大大縮短,，之后,，選擇簇頭節(jié)點，簇頭節(jié)點的選擇兼顧到了節(jié)點的剩余能量和到簇內質心的距離,。能量較大同時到簇內質心的距離較小的節(jié)點優(yōu)先當選為簇頭節(jié)點,，這樣可以保證簇頭節(jié)點在本輪數(shù)據(jù)傳輸完成之后屬于能量與其他簇內節(jié)點剩余能量不至于有過大差距。改進算法之后同樣進入到穩(wěn)定的數(shù)據(jù)傳輸階段,。傳輸一段時間后,，重新進行簇頭的選擇，如此循環(huán)下去,。

　　2 LEACH_EH算法

　　2.1 K_MEANS算法

　　K-MEANS算法,，也稱為K-平均或K-均值算法，它是一種得到廣泛使用的聚類算法,。其主要思想是通過迭代過程把數(shù)據(jù)集劃為不同的類別,，使得評價聚類性能的準則函數(shù)達到最優(yōu)，從而使生成的每個聚類類內緊湊,，類間獨立,。

　　K_MEANS算法是很典型的基于距離的聚類算法,，采用距離作為相似性的評價指標，即認為兩個對象的距離越近,，其相識度越大,。該算法認為簇是由距離靠近的對象組成的，因此把得到緊湊且獨立的簇作為最終目標,。

　　本實驗中K_MEANS算法先是隨機的選取任意k個節(jié)點作為初始簇頭,，每個簇頭代表一個簇。剩余的每個節(jié)點,，根據(jù)其到各個簇頭的距離加入到最近的簇頭,。各個簇進行質心計算，接著所有節(jié)點根據(jù)到k個質心的距離選擇加入到最近的質心,，之后進行新簇質心的計算。如果新的質心相對于原來的質心位置不變或者變化足夠小,，認為分簇已經(jīng)收斂,，分簇結束；否則繼續(xù)迭代,。

　　2.2 具體步驟

　　2.2.1 簇的形成

　?。?）從普通節(jié)點中選擇出幾個節(jié)點作為臨時簇頭（進行分簇用），簇頭數(shù)目根據(jù)參考文獻[9]中可知,，最優(yōu)簇頭數(shù)為節(jié)點總數(shù)的3%~7%,，這里選擇5%。

　?。?）其他節(jié)點依據(jù)到各個臨時簇頭節(jié)點的距離選擇加入距離最短的臨時簇頭,，形成初始簇。

　?。?）計算各個簇質心坐標（按簇內節(jié)點坐標平均值計算）,，公式為：

　　xk=，yk=（2）

　　其中,，k為質心編號,，sk為編號k的質心擁有的節(jié)點數(shù)目。

　?。?）各個節(jié)點根據(jù)到各個質心的距離選擇最近的質心加入其簇,，若形成的各個簇已經(jīng)收斂，跳到步驟（5）,；否則跳到步驟（3）,，進行迭代計算。公式為：

　　其中,，i為節(jié)點的編號,，k為質心的編號,。

　　（5）最終的分簇結果形成,。

　　結果實驗驗證,，該分簇方法能夠在把隨機生成的節(jié)點很好地分配在不同的簇內，圖1為兩組不同的實驗場景生成的分簇結果,，左邊是生成的初始簇,，右邊是使用K_MEANS算法得出的簇。

　　2.2.2 簇頭選舉

　　分簇形成以后,，接著進行簇的簇頭選擇,。由于簇頭節(jié)點的能量消耗較大，同時能量消耗與傳輸距離也有很大的關系,。因此,，對于每個節(jié)點產(chǎn)生一個判斷值C（n）。其計算式為：

　　C（n）=?琢×+（1-?琢）×（4）

　　其中,，E（n）表示節(jié)點的剩余能量,，Eaver是節(jié)點n所屬簇內節(jié)點剩余能量的均值，D（n）是節(jié)點n到簇質心的距離,，使用歐式距離,，Daver是簇內所有節(jié)點到該簇質心距離的均值，?琢是影響因子,，用來權衡節(jié)點剩余能量與節(jié)點到簇質心的距離對簇頭選舉的影響,。各個簇內C（n）值最大的節(jié)點當選為簇頭節(jié)點，每一輪選擇一次簇頭,。

　　2.2.3 數(shù)據(jù)傳輸

　　數(shù)據(jù)傳輸階段與LEACH協(xié)議一樣,，簇內節(jié)點按照分配的時隙在相應時間內發(fā)送采集到的數(shù)據(jù)給簇頭節(jié)點，簇內節(jié)點發(fā)送完成后,，簇頭節(jié)點對收到的數(shù)據(jù)進行數(shù)據(jù)融合,，然后發(fā)送給Sink節(jié)點，這個過程進行數(shù)次,，之后再進行簇頭選舉,。

　　LEACH_ED算法的分簇和選舉簇頭流程圖如圖2所示。

　　3 實驗仿真以及結果

　　本文采用的無線通信模型為一階無線通信模型,。根據(jù)這種模型,，傳感器節(jié)點傳輸k bit數(shù)據(jù)所消耗的能量為：

　　En（k，d）=k×Eelec+k×εamp×d2,，d≤d0k×Eelec+k×famp×d4,，d>d0（5）

　　節(jié)點接收k bit數(shù)據(jù)所消耗的能量為：

　　En（k）=k×Eelec（6）

　　其中，d0=,，節(jié)點發(fā)送數(shù)據(jù)時根據(jù)距離選擇不同的傳輸方式,。當傳輸距離小于等于d0時,，使用自由傳輸模式，能夠有效地節(jié)省能耗,；當傳輸距離大于d0時,，使用多路徑衰減模式進行數(shù)據(jù)傳輸。節(jié)點接收數(shù)據(jù)的能耗只與包的大小有關,。

　　本文使用MATLAB進行仿真實驗,，設置節(jié)點數(shù)目為100個，拓撲的區(qū)域大小為100 m×100 m,，Sink節(jié)點位于拓撲的中心（50,，50）。節(jié)點完全隨機地分布在區(qū)域內,，節(jié)點位置固定,。節(jié)點的初始能量為1 J，其他主要參數(shù)如表1所示,。

　　定義當節(jié)點能耗小于0時節(jié)點死亡,，死亡節(jié)點不再發(fā)送信息，也不再接收任何消息,，與外界失去聯(lián)系。

　　假定整個網(wǎng)絡的絕對有效時間定義為從仿真開始到第一個節(jié)點死亡經(jīng)歷的時間,，因為此時網(wǎng)絡處于完全正常的工作狀態(tài)下,，各個傳感器節(jié)點都能夠發(fā)送采集到的數(shù)據(jù)給Sink節(jié)點。

　　相對有效時間定義為仿真開始到死亡節(jié)點為20%時經(jīng)歷的時間,。此時,，一部分節(jié)點已經(jīng)死亡，但是,，由于死亡的節(jié)點分布較為分散,，仍然能夠采集到死亡節(jié)點管轄區(qū)域的信息附近的其他節(jié)點，所以整個網(wǎng)絡的信息采集仍然能夠覆蓋到全部區(qū)域的可能性還是比較大,。

　　定義當節(jié)點死亡達到50%的時候,，從開始到現(xiàn)在經(jīng)歷的時間為可信有效時間。此時,，節(jié)點死亡過半,，對于死亡節(jié)點所處的具體區(qū)域也不從得知，因為此時無法判斷剩余活著的節(jié)點是否仍然能夠覆蓋全部區(qū)域,?？尚庞行r間僅作為參考使用。

　　圖3為本實驗采用的實驗場景,。圖4是LEACH-ED算法與LEACH算法的各輪次下剩余節(jié)點的存活數(shù)對比圖,。

　　圖4中,，LEACH算法的絕對有效時間為265輪，而LEACH_ED算法的絕對有效時間為350輪,，絕對有效時間提高了32%,。LEACH算法的相對有效時間大約為330輪，LEACH_ED算法的相對有效時間大約為370輪,，相對有效時間提高了12%,。LEACH算法的參考有效時間大致與新協(xié)議相同。從圖4中還能發(fā)現(xiàn),，LEACH算法的絕對有效時間和相對有效時間的間距較大,，大概經(jīng)歷了110輪，而改進后的LEACH_ED算法卻只有20輪,。這20輪中,，節(jié)點大量死亡，死亡的頻度遠大于同期的LEACH協(xié)議,。

　　是到各輪次時所有節(jié)點消耗的總能量圖,。改進后的協(xié)議每一輪所消耗的總能量與LEACH協(xié)議基本相同。但是結合圖4可知,，節(jié)點性能方面上卻有很大的提高,，原因在于改進后的協(xié)議主要是在均衡節(jié)點能耗上有較大性能提升。各個節(jié)點的能量損耗大致相同,，所以節(jié)點的剩余能量也就基本一致,。圖4中的LEACH_ED協(xié)議從絕對有效時間到相對有效時間的間隔輪數(shù)較小，就是因為此時節(jié)點剩余能量都比較小同時大致相同,，一個節(jié)點死亡同時表明其他節(jié)點的剩余能量也快耗盡,，所以才會出現(xiàn)節(jié)點集中死亡的現(xiàn)象。

　　節(jié)點的剩余能量均衡程度可以用信息熵來表示,。信息熵是一個數(shù)學上頗為抽象的概念,，在這里不妨把信息熵理解成某種特定信息的出現(xiàn)概率（離散隨機事件的出現(xiàn)概率）。一個系統(tǒng)越是有序,，信息熵就越低,；反之，一個系統(tǒng)越是混亂,，信息熵就越高,。信息熵也可以說是系統(tǒng)有序化程度的一個度量。信息熵可以用來衡量一模型中各種事件出現(xiàn)概率的均衡程度,，信息熵越大,，節(jié)點剩余能量越均衡，節(jié)點的能量消耗越平均,。信息熵的計算式為：

　　H（x）=E[l（xi）]=E[log（2,，1/p（xi））]=-p（xi）log（2,，p（xi）（i=1，2,，…,，n）（7）

　　信息熵越大，表明模型中各個事件的概率越接近相同,，當每個事件的概率均相同時,，信息熵達到最大。

　　本實驗中,，p（xi）抽象為各輪次后節(jié)點剩余能量與總剩余能量的比值,，即：

　　p（xi）=（8）

　　實驗選取第50、100,、150,、200、250,、300,、350輪來比較兩種協(xié)議不同輪次下的信息熵。圖為對比圖,。

　　從圖中可以看出LEACH_ED和LEACH在前4個輪次中信息熵都趨于相同,，不過可以明顯看出LEACH_ED協(xié)議在前4個輪次中信息熵要比LEACH協(xié)議略大；同時隨著輪次的增加,，LEACH_ED協(xié)議和LEACH協(xié)議的信息熵的差值越來越大,。LEACH協(xié)議信息熵的變化趨勢非常明顯。這說明開始時新協(xié)議和LEACH協(xié)議剩余能量都較為平均,；隨著輪數(shù)的增加，LEACH協(xié)議中各節(jié)點的能耗就有所偏差,，一些節(jié)點的剩余能耗明顯要比其他的節(jié)點少,。這導致LEACH協(xié)議中絕對有效時間時的輪次要比改進后協(xié)議的早大約85輪，相對有效時間早大約50輪,，均衡節(jié)點能量消耗起到了至關重要的作用,。

　　本文從LEACH協(xié)議的特點入手，分析了LEACH協(xié)議的優(yōu)缺點,。然后從均衡節(jié)點能耗上對LEACH協(xié)議進行了改進,。改進后的LEACH_ED算法采用先分簇，再選舉簇頭節(jié)點,，最后進行數(shù)據(jù)傳輸?shù)捻樞?。使用聚類算法K_MEANS對節(jié)點進行一次性分簇，得到比較好的分簇效果,，然后結合節(jié)點的剩余能量和到簇質心的位置選出簇頭節(jié)點,，之后進行數(shù)據(jù)傳輸,。實驗結果驗證了改進算法的效果，在每輪總能耗與LEACH協(xié)議大致相同的情況下取得了很好的能耗均衡,，且能在很長一段時間上保持同等的均衡效果,。

　　參考文獻

　　[1] AKYILDIZ I F， SU W,， SANKARASUBRAMANIAM Y,， et al. Wireless sensor networks： a survey[J]. Computer networks， 2002,，38（4）：393-422.

　　[2] YOUNIS O,， FAHMY S. A hybrid， energy efficient,， distributed clustering approach for ad-hoc sensor networks[J].IEEE Transactions On Mibile Computing,， 2004，3（4）：660-669.

　　[3] AL-KARAKI J N,， KAMAL A E. Routing techniques in wireless sensor networks： a survey[J]. Wireless Communications,，IEEE，2004,，11（6）：6-28.

　　[4] 蘭慎,，彭剛，李發(fā)飛.基于休眠簇頭的LEACH算法研究[J].微型機與應用,，2012,，31（21）：65-70.

　　[5] Fan Xiangning， Song Yulin. Improvement on LEACH protocol of wireless sensor Network[C]. Internal Conference on Sensor Technologies and Applitcations,，2007：260-264.

　　[6] 陳慶章,，趙小敏，陳曉瑩.提高無線傳感器網(wǎng)絡能效的雙輪成簇協(xié)議設計[J].軟件學報,，2010,，21（11）：2933-2943.

　　[7] Lu Jun， SUDA T. Coverage-aware self-scheduling in sensor networks[C]. 2003 IEEE 18th Annual Workshop on Computer Communications,， 2003,， CCW 2003，2003：117-123.

　　[8] 李年瓊,，黃宏光,，李鵬.基于剩余能量和位置的LEACH改進算法[J].計算機工程.2012，38（24）：70-73.

　　[9] 王慧斌,，俞弦,，徐立中，等.無線傳感器網(wǎng)路LEACH協(xié)議的改進[C].無線傳感器網(wǎng)及網(wǎng)絡信息處理技術-2006年通信與信號處理年會論文集，2006.

　　[10] HEINZELMAN W R,， CHANDRAKASAN A,， BALAKRISHNAN H. An application_specific protocol architecture for wireless microsensor network[J]. IEEE Transactions on Wireless Com-munication，2002,，1（4）：660-670.

　　[11] 郭前崗,，周德詳，周西峰.LEACH路由協(xié)議最優(yōu)簇頭數(shù)計算方法[J].微型機與應用,，2012,，32（3）：61-66.