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

　　關鍵詞： WSN路由協議；LEACH；K_MEANS算法；MATLAB仿真

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

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

　　1 LEACH協議

　　1.1 算法介紹

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

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

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

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

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

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

　　1.2 LEACH算法的不足

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

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

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

　　2 LEACH_EH算法

　　2.1 K_MEANS算法

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

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

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

　　2.2 具體步驟

　　2.2.1 簇的形成

　　（1）從普通節點中選擇出幾個節點作為臨時簇頭（進行分簇用），簇頭數目根據參考文獻[9]中可知，最優簇頭數為節點總數的3%~7%，這里選擇5%。

　　（2）其他節點依據到各個臨時簇頭節點的距離選擇加入距離最短的臨時簇頭，形成初始簇。

　　（3）計算各個簇質心坐標（按簇內節點坐標平均值計算），公式為：

　　xk=，yk=（2）

　　其中，k為質心編號，sk為編號k的質心擁有的節點數目。

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

　　其中，i為節點的編號，k為質心的編號。

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

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

　　2.2.2 簇頭選舉

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

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

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

　　2.2.3 數據傳輸

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

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

　　3 實驗仿真以及結果

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

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

　　節點接收k bit數據所消耗的能量為：

　　En（k）=k×Eelec（6）

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

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

　　定義當節點能耗小于0時節點死亡，死亡節點不再發送信息，也不再接收任何消息，與外界失去聯系。

　　假定整個網絡的絕對有效時間定義為從仿真開始到第一個節點死亡經歷的時間，因為此時網絡處于完全正常的工作狀態下，各個傳感器節點都能夠發送采集到的數據給Sink節點。

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

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

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

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

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

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

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

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

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

　　p（xi）=（8）

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

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

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

　　參考文獻

　　[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] 蘭慎，彭剛，李發飛.基于休眠簇頭的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] 陳慶章，趙小敏，陳曉瑩.提高無線傳感器網絡能效的雙輪成簇協議設計[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] 王慧斌，俞弦，徐立中，等.無線傳感器網路LEACH協議的改進[C].無線傳感器網及網絡信息處理技術-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路由協議最優簇頭數計算方法[J].微型機與應用，2012，32（3）：61-66.