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

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

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

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

　　1 LEACH協(xié)議

　　1.1 算法介紹

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

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

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

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

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

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

　　1.2 LEACH算法的不足

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

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

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

　　2 LEACH_EH算法

　　2.1 K_MEANS算法

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

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

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

　　2.2 具體步驟

　　2.2.1 簇的形成

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

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

　　（3）計算各個簇質(zhì)心坐標(biāo)（按簇內(nèi)節(jié)點坐標(biāo)平均值計算），公式為：

　　xk=，yk=（2）

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

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

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

　　（5）最終的分簇結(jié)果形成。

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

　　2.2.2 簇頭選舉

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

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

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

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

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

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

　　3 實驗仿真以及結(jié)果

　　本文采用的無線通信模型為一階無線通信模型。根據(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ù)距離選擇不同的傳輸方式。當(dāng)傳輸距離小于等于d0時，使用自由傳輸模式，能夠有效地節(jié)省能耗；當(dāng)傳輸距離大于d0時，使用多路徑衰減模式進(jìn)行數(shù)據(jù)傳輸。節(jié)點接收數(shù)據(jù)的能耗只與包的大小有關(guān)。

　　本文使用MATLAB進(jìn)行仿真實驗，設(shè)置節(jié)點數(shù)目為100個，拓?fù)涞膮^(qū)域大小為100 m×100 m，Sink節(jié)點位于拓?fù)涞闹行模?0，50）。節(jié)點完全隨機地分布在區(qū)域內(nèi)，節(jié)點位置固定。節(jié)點的初始能量為1 J，其他主要參數(shù)如表1所示。

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

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

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

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

　　圖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輪，而改進(jìn)后的LEACH_ED算法卻只有20輪。這20輪中，節(jié)點大量死亡，死亡的頻度遠(yuǎn)大于同期的LEACH協(xié)議。

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

　　節(jié)點的剩余能量均衡程度可以用信息熵來表示。信息熵是一個數(shù)學(xué)上頗為抽象的概念，在這里不妨把信息熵理解成某種特定信息的出現(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）

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

　　本實驗中，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é)點少。這導(dǎo)致LEACH協(xié)議中絕對有效時間時的輪次要比改進(jìn)后協(xié)議的早大約85輪，相對有效時間早大約50輪，均衡節(jié)點能量消耗起到了至關(guān)重要的作用。

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

　　參考文獻(xiàn)

　　[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].微型機與應(yīng)用，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)絡(luò)能效的雙輪成簇協(xié)議設(shè)計[J].軟件學(xué)報，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ìn)算法[J].計算機工程.2012，38（24）：70-73.

　　[9] 王慧斌，俞弦，徐立中，等.無線傳感器網(wǎng)路LEACH協(xié)議的改進(jìn)[C].無線傳感器網(wǎng)及網(wǎng)絡(luò)信息處理技術(shù)-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].微型機與應(yīng)用，2012，32（3）：61-66.