一種基于LEACH的異構WSN能量均衡成簇協議*

葉繼華，王 文，江愛文

（江西師范大學計算機信息工程學院，南昌330022）

無線傳感網絡WSN（Wireless Sensor Network）是一種自組織、多跳路由、動態、以數據為中心的大規模網絡［1］。無線傳感器網絡路由技術是當今國內外研究的重點和熱點，其設計的首要目標是提高能量有效性，延長網絡生命周期［2］。WSN低功耗路由協議負責在Sink點和其余節點間可靠地傳輸數據［3］。LEACH［4］協議是層次型無線低功耗路由協議的典型代表。現今的很多經典都是受LEACH協議的成簇思想啟發而來，比較有代表性的主要有HEED［5］、EECS［6］、PEGASIS［7］、EEUC［8］、TEEN［9］等。HEED是一種在LEACH協議基礎上的改進協議，利用迭代的方式改進了簇頭選舉方法。但是，HEED算法在簇頭選舉階段采取迭代的方式，增加了能量消耗，在采用單跳數據傳輸的假設下，其性能尚不如LEACH。EECS協議具有控制消息開銷小，聚類在空間上分布近似均勻，網絡能量有效利用率高等特點。但是，EECS也存在容易造成簇頭分布漏洞、節點加入簇首未考慮節點剩余能量等問題。PEGA?SIS算法繼承了LEACH的動態選舉方法并加以改進，減少了因經常選舉簇頭而產生的能量浪費，并采用鏈式路由。TEEN協議采用與LEACH協議相同的分簇算法，但是在數據傳輸階段使用不同的策略，通過設置軟、硬兩個閾值來減少數據的發送次數。EEUC是一種非均勻分簇的路由協議，考慮到靠近基站的簇頭需要轉發其他簇頭的信息從而造成更多的能量消耗，通過競爭半徑的計算，使得距離基站遠的簇頭具有更大的競爭半徑形成更大的簇，但是EEUC對于節點與基站之間的距離等全局信息有很高的要求，這限制了其應用尤其是大規模應用的意義。Kodali R K等人針對LEACH協議不適合大規模網絡問題，提出了多層次機構的LEACH協議，一定程度上解決了LEACH協議在超大范圍網絡 的 應 用［10］。Sapna Gambhir等 人 提 出 了 Op-LEACH［11］協議，這是一種針對穩定期的改進，讓高信息量的節點占用其他不傳輸數據的節點的時間槽進行額外通信，可以有效降低數據傳輸延遲，提高數據傳輸效率。馬建樂等人提出了基于位置與剩余能量的LEACH-LC［12］算法，與LEACH-C算法類似并在向BS提交的信息中增加剩余能量及與BS的距離等信。針對無線傳感器網絡中網絡能量損耗不均的問題，陳曉娟等人提出了一種基于LEACH的改進節能路由協議 LEACH-PSOC［13］。

本文針對感知異構的傳感器網絡，以LEACH協議為基礎，提出了基于簇內可變通信周期的能量均衡改進協議—ACPSEB-LEACH協議，在收集實際數據的基礎上進行的仿真結果表明，改進后的協議在延長網絡生存周期、平衡全局能量上有更好的效果。

1 改進的協議ACPSEB-LEACH

1.1 LEACH協議分析

LEACH協議的全稱為低功耗自適應集簇分層型協議，為層次路由協議的典型代表。該算法基本思想是：以循環的方式隨機選擇簇頭節點，將整個網絡的能量負載平均分配到每個傳感器節點中，從而達到降低網絡能源消耗、提高網絡整體生存時間的目的。

LEACH算法分為三個部分：①簇頭選舉；②簇成員加入成簇；③簇的路由。選舉時，每個節點產生一個介于0和1之間的隨機數，如果這個數小于閾值T（n），該節點成為簇頭。

式中為T（n）的計算方法，其中p表示網絡中的簇頭比例，r表示輪數，集合G表示前1/p輪沒有當選簇頭的節點集合。但LEACH算法存在如下不足：①LEACH算法的隨機簇頭選舉會造成簇分布不合理，全局能耗不均，特別是離基站遠的節點更容易過早死亡。②擴展性差。由于簇頭與基站采取的是單跳的通信方式，使其不適合大規模網絡的應用。③適應性差。無線傳感器網絡的應用場合多樣，每種應用的要求可能完全不同。全網幾乎統一的采樣、傳輸周期使其不能適應現場應用的復雜環境，降低了算法的實際應用意義。

1.2 ACPSEB-LEACH協議

ACPSEB-LEACH協議節能思想是：依據實際感知信息特點，抑制節點數據發送量，從而造成各類節點之間以及較遠地區的同種節點之間的能耗差異，以此差異來進行簇頭、成簇優化。實現網絡能量均衡，延長網絡生存時間。

在ACPSEB-LEACH協議中：在每一個簇頭選舉開始階段，所有節點都是普通節點。這里，對于所有節點引入節點活躍度L（i）表示節點i的前一段時間的總體活躍程度、引入AL（i，r）∈（0，1］表示節點第r輪當輪的活躍度。當AL（i，r）為1時表示節點處于最活躍階段，每一次屬于自己的時隙該節點都上交數據包；該值越小表示節點越不活躍，有部分屬于自己的時隙該節點并未選擇與簇頭進行通信，從而節約了能耗；0表示節點完全不活動，即代表節點已經死亡。

ACPSEB-LEACH協議同樣分三個部分：①簇頭選舉；②簇的形成；③數據傳輸。

1.2.1 簇頭選舉

ACPSEB-LEACH的簇頭選舉分為兩階段：第一階段是臨時簇頭選舉；第二階段是最終簇頭選出。

階段一：臨時簇頭選舉。

選舉時，每個存活節點產生一個介于0和1之間的隨機數，如果這個數小于閾值T（n），該節點成為簇頭。這里，我們使用上文中提到的節點活躍度L（i）作為參數，構建一個修正函數G（n，r）對T（n）進行修正，如式（2）所示。

其中G(n,r)計算方法如式（3）所示。

其中Lavg表示全局節點平均活躍度，a、b均為可調整變量。引入G（n，r）的目的是使得高活躍度節點當選簇頭大大降低，低活躍度度階段當選簇頭節點概率大大增加，從而平均能量消耗，延長網絡存活時間，使得第一個死亡節點的時間得到延后。對于節點活躍度有兩種設定方法：①在網絡的初始部署階段，依據各種節點采集數據的現實需求與相關設計規范，可以對各類節點的采樣、發送周期進行區分設計，依據設定好的發送周期計算出固定的節點活躍度。②無法明確各類采集數據的具體要求時，也可以全網采用統一的最小采樣、通信周期，即全部節點初始活躍度為1，依據本文中的算法進行自我調整。

階段二：最終簇頭選出

由于引入了修正函數，可能會出現簇頭過密集的現象，前期低活躍度節可能會集體當選簇頭、后期前幾輪未當選的高活躍度節點也會出現同時當選的情況，因此在臨時簇頭選舉之后引進競爭半徑Rc（i）來進行簇頭調整，以確定最終簇頭，只有在競爭半徑Rc（i）以內的節點才能接收到該臨時簇頭的當選信息。Rc（i）的計算［4］如式（4）所示：

其中，S為該區域的面積，kopt為最佳簇頭數目，Lavg表示全局節點平均活躍度。

節點i當選為臨時簇頭后，按如下步驟進行調整：①依據公式（4）計算自身競爭半徑Rc（i）。②若臨時簇頭i收到臨時簇頭j的當選消息，判斷兩者之間的距離d（i，j）與自身競爭半徑Rc（i）之間的關系。若Rc（i）＜d（i，j）臨時簇頭i將退出競選，發送退出競選消息。③調整之后，未退出的臨時簇頭當選為正式簇頭，向以自己為圓心，競爭半徑為Rc（i）的圓形區域廣播當選消息，接收其他節點的加入請求。

通過以上方法，在出現簇頭競爭區域相沖突時可以保證高活躍度臨時節點總是收到低活躍度節點的當選消息，那么高活躍度節點將向外發送退出競選消息，自動成為普通節點，就大大降低了高活躍度節點的能量消耗。

1.2.2 簇形成階段

高活躍度節點當選簇頭后，其能量消耗非常快，為了平衡全局能耗，延長網絡存活時間，要盡量延長高活躍度節點的存活時間，因此普通節點接收到正式簇頭后，綜合考慮距離、活躍度、剩余能量等因素選擇最佳的簇頭加入。對于節點i，接到正式簇頭j的當選通知后，計算自己加入該簇的成本C（i，j），選擇成本最小的簇頭加入。C（i，j）計算方法如式（5）所示：

其中w為可調節權重值，d（i，j）表示節點i到節點j之間的距離，d（j，Base）表示節點j到基站的距離。由公式可以看到，這樣的選擇方法可以降低遠離基站且高活躍度節點的簇成員數進而降低其能耗延長其存活時間；同時又考慮到節點i與簇頭j之間的距離，使得簇成員得到合理的分配。

所有簇成員加入后，簇頭為所有簇成員分配TDMA時隙并以廣播的方式通知各成員。

1.2.3 穩定階段

簇形成之后，協議運行進入穩定階段。在該階段，普通節點按一定的周期采集信息發送給簇頭節點，簇頭節點將數據壓縮、融合后傳送給基站。采集、傳輸這兩步驟都是以周期為間隔的，即信息采集周期Ts以及信息發送周期Tc。為了保證數據的實時性，采集到的數據應該保證能在下一個時隙發送出去，在LEACH協議中，Ts與Tc是相等的。

在本文所提出的ACPSEB-LEACH協議中，提出了簇內可變通信周期策略即Ts與Tc不一定相等。節點并不是每個時隙都與簇頭進行通信，以減少數據的發送量。對于簇成員節點i，Ts（i）與Tc（i）的確定方式如下：

令Tc(i)=k×Ts(i),k=1,2,3…kmax

①節點每發送一次數據，k自動增加1，若節點兩次采集的數據不相同，k復位為1。

②節點發送數據的條件：節點兩次采集的數據不相同或者Tc（i）超時。

③每次變更通信周期Tc，簇成員都應該在新的通信周期生效前及時通知簇頭節點。簇頭節點在接到其成員節點i的數據后將其保存。在Tc的持續時間內，如果節點i不發送新的數據，簇頭默認使用節點i上次傳遞過來的數據；如果節點i發來新的數據，則更新數據及對應的簇內通信周期。依據這樣的策略，可以依據情況決定是否發送數據、多長時間發送一次，節約了節點能量。由于每個節點都知道自己在當輪的各個簇內通信周期及持續時間，那么在每次發送數據包大小都相同的情況下，很容易得到當輪的數據發送總量。最活躍的節點每次數據采集后都執行數據發送，假設它的數據發送量為D，對于其他次活躍節點來說，在每一輪結束階段，自己的數據發送量D（i，r-1）與D之間存在以下關系：

AL（i，r-1）表示節點i在第r-1輪的活躍度。因為節點的能量消耗是和相對長時間的節點活躍度相關的，所以對AL（i，r-1）進行算術平均，得到反映前一段時間的節點活躍度L（i），計算公式如下：

依據得到的L（i）即可在下一輪開始時，將其帶入式（3）中，以達到優化簇頭選舉，平衡能量消耗的目的。

2 實驗測試與分析

2.1 應用場景假設

由于傳感器網絡具有很強的應用相關性，不同應用中的路由協議可能差別很大，沒有一個通用的路由協議［14］。研究無線傳感器網絡路由協議不可忽略其應用場景。無線傳感器網絡的應用場合多樣，每種應用的要求不盡相同。在多種傳感器同時采集的情況下，除了要解決網絡能耗等傳統問題還要要面對更為復雜的情況：①為了延長網絡生存時間，盡可能地保證采樣精度的情況下應盡量延長采樣周期［15］，每一種數據的要求可能不同，LEACH等協議難以滿足這種多樣需求。②傳感器采集的同一種信息數據在一段時間內可能是完全相同的，重復的傳輸浪費系統資源。③對于一個多類型信息采集系統，任何一種信息的缺失都會給用戶帶來巨大的麻煩。

本實驗參照實際采集數據的結果，在此基礎上進行模擬。依據實驗室現有物聯網設備，完成了實際數據的采集。使用了實驗室中的三種傳感器，采集了光照、溫度及濕度三種信息。本次采集所使用的無線傳感器節點是CC2530節點，在TinyOS系統環境下，實現數據采集功能及數據轉發功能。光照、溫度及濕度數據的采集如圖1、圖2所示。

可以看到，實際采集到的數據都有浮動期和穩定期。在實際采集時發現，在一段時間內，采集到大量的相同數據。所以，依據數據采集的經驗，對于本文實驗，假設監測區域內需要采集的物理量在每一輪內隨采集次數count變化示意圖如圖3所示。模擬數據1、3代表部分變化部分恒定的物理量，數據2代表一直變化的物理量，數據4代表絕大部分時間恒定數值偶爾波動的物理量。由于節點活躍度L（i）衡量標準是數據的變化，所以以上四種情況基本可以涵蓋大部分情況。

圖1 光照數據采集

圖2 溫度及濕度數據采集

圖3 信號模擬示意圖

仿真實驗設定對一個邊長為200 m的正方形區域內的4種物理信號進行周期性同時采集。設采集周期為t，每一輪的采集次數為count，則每一輪的總時長為Tr=t*count。基站位于區域中心位置，如圖4所示。

圖4 應用場景示意圖

因此，我們布置4種傳感器節點分別采集以上四種模擬信息。假設每種節點的覆蓋度相同，每一種傳感器個數為200，網絡總的傳感器節點個數N=800。所有節點初始活躍度都設為1。

2.2 網絡通信模型

根據WSN研究中的常見假設，本文中的網絡模型作如下假設［16-17］：①每個節點都具有相同的計算能力、通信能力，均具備數據聚合的能力。②若已知發送方的發射功率，接收方可以根據信號的強度計算二者間距離的近似值。③節點的最大發射功率是有限的，節點可以自由調節發射功率。④節點間的鏈路是對稱的，他們以相同的傳輸功率進行通信。⑤傳感網絡各節點的時間是同步的，有可靠的時間同步機制。⑥基站可以能夠和所有節點進行通信。簇頭與基站之間進行單跳或多跳方式進行通信。本文統一采用單跳形式。

2.3 能耗模型及參數選擇

無線傳感網絡中，節點的能耗大部分來自于數據的發送接收，少部分來自于發射電路損耗和功放損耗。本文采用與文獻［16］相同的的無線通信能耗模型：

式（8）表示節點發送l比特數據到距離d的接收者的能量消耗，式（9）表示接收l比特數據的能量消耗。Eelec表示發射電路的能量損耗，當傳輸距離d小于閾值d0時，采用自由空間模型，εfs表示功放所需的能量。當傳輸距離d大于等于閾值d0時，采用多路徑衰減模型，εmp表示在該模型下功率放大所需能量。

本次實驗中采用的各參數值如下［4］：所有節點統一初始能量，節點初始能量E0=0，Eelec=50 nJ/bit，εfs=10 pJ/（bit/m2），d0=87.7，εmp=0.001 3 Pj/（bit/m4），p=0.05。

數據融合的能耗為：

對于本文中的場景，M=200。文中提到的w，a，b依據經驗值設定：w=0.8，a=2.8，b=5。

2.4 性能分析與比較比較

本文采用Matlab仿真軟件對LEACH，EECS，ACPSEB-LEACH在上述的環境下進行仿真比較。由于采用簇內通信周期可變策略，使得實際發送數據的減少，從而節省能量，所以對所有協議都采取這樣的發送策略進行比較。

實驗比較主要依據以下幾點性能：①網絡生存周期；②節點平均剩余能量，該參數表征全局能量利用效率；③簇頭數據發送量，簇頭發給基站的數據越多，監測到的信息越全面；④死亡節點構成，參與傳感的不同類型網絡是否基本同時開始死亡。

2.4.1 網絡生存周期及死亡節點實驗

網絡的生存周期是本最重要的一個指標，三種算法的實驗結果如圖5所示。

從圖5可見，ACPSEB-LEACH協議的網絡生存周期最長，EECS其次，LEACH最差。

圖5 網絡生存周期示意圖

LEACH協議由于沒有依據節點活躍度來采取相應的節能措施，同時隨機選取簇頭的方式使得簇頭分布不合理不可控，使得高活躍節點過早死亡，曲線橫向跨度非常大，實際上是不同活躍度的依次死亡造成的，網絡拓撲在高活躍度節點死亡后已經不完整，后期采集上的數據意義已經不大。LEACH協議的節點死亡細節如圖6所示。

圖6 LEACH中各組節點死亡示意圖

EECS比LEACH略有提高，雖然采取了一些能量平衡的措施，但是在本文的實驗環境中并沒有太好的效果，也存在與LEACH類似的問題。

對于ACPSEB-LEACH協議，從圖5可見，首個死亡節點大幅度延后，1600輪以后節點死亡曲線上升很快，表明網絡中的節點在快速死亡，整個網絡的能耗非常平均，ACPSEB-LEACH中各組節點死亡示意圖如圖7所示。

圖7 ACPSEB-LEACH各組節點死亡示意圖

實驗結果說明，ACPSEB-LEACH協議的網絡生存時長效果最好，各組節點死亡時間基本一致，各類型節點之間能量消耗比較均衡。

2.4.2 節點平均剩余能量實驗

節點平均剩余能量是衡量網絡中節點能量利用效率的一個標準，剩余能量越多，說明每一輪節點的消耗越少，這樣也就能夠更好的延長傳感網絡的生命周期。圖8表示的是三種算法的節點平均剩余能量。

從圖8中可以看出。EECS與本文提出的ACPSEB-LEACH算法有一個交叉點。本文提出的ACPSEB-LEACH協議的平均剩余能量在交叉點以前都要好于LEACH及EECS的效果，在交叉點以后低于EECS。出現這種情況是因為在交叉點附近，EECS與LEACH協議中的高活躍節點基本已全部死亡，留下的低活躍節點能量消耗非常少。這說明ACPSEB-LEACH協議的能量均衡，利用率高，算法收斂性快的特點。

圖8 節點平均剩余能量

可見，在有效的網絡生存周期內，本文提出的ACPSEB-LEACH協議的平均剩余能量要高于其他兩種。

2.4.3 簇頭數據發送量實驗

考慮到傳感網絡的應用環境，簇頭向基站發送的數據量也是一個重要的指標，對比三種協議的基站數據接收量，如圖9所示。

圖9 簇頭發送數據量

由圖9可以看到，在采用簇內可變周期數據發送策略的情況下，ACPSEB-LEACH協議依然可以傳送大量數據包到達基站，同時保證了采集的數據量和能量的節約。

綜上所述，ACPSEB-LEACH協議在網絡生存周期，節點平均剩余能量，發送數據量上都有一個很好的效果，對比LEACH及EECS有很大的提高。

3 總結

本文考慮了一種接近真實的多種數據同時采集的網絡環境，提出一種適用于周期性、長期性信號采集應用的低功耗路由協議ACPSEB-LEACH。該協議從LEACH協議的穩定階段及成簇階段對LEACH協議進行改進，運行過程中能夠自我調整節點數據發送周期，從而滿足低功耗與信息感知的雙方面要求。仿真表明，改進后的協議在延長網絡生存周期、平衡全局能量上有很好的效果。更為重要的是，本文思路為以后進一步對無線傳感網絡低功耗路進行研究提供了一個科學地、可供參考的方法，此策略在多跳傳輸及大規模網絡擴展方面依然有極大的改進空間。

［1］李建中，高宏.無線傳感器網絡的研究進展［M］.計算機研究與發展，2008，45（1）：1-15.

［2］李芳芳，王靖.一種基于LEACH協議的無線傳感器網絡路由算法［J］.傳感技術學報，2012，25（10）：1445-1452.

［3］唐勇，周明天，張欣.無線傳感器網絡路由協議研究進展［J］.軟件學報，2006.3：410-412.

［4］Heinzelman W B，Anantha P Chandrakasan，Hari Balakrishnan.An Application-Specific Protocol Architecture for Wireless Micro?sensor Networks［C］//Proc of the 33rd Hawaii International Con?ference on System Sciences，2000：3005-1130.

［5］Younis O，Fahmy S.HeeD：A Hybrid，Energy-Efficient Distribut?ed Clustering Approach for Ad-Hoc Sensor Networks［J］.IEEE Trans on Mobile Computing，2004，3（4）：660-669.

［6］陳貴海，李成法，葉懋，等.EECS：一種無線傳感器網絡中節能的聚類方案［J］.Journal of Frontiers of Computer Science and Technology，2007，1（2）：1673-9418.

［7］Lindsey S，Raghavendra C.PEGASIS：Power-Efficient Gathering?in Sensor Information Systems.IEEE Aerospace ConferencePro?ceedings，2002.

［8］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網絡路由協議［J］.計算機學報，2007（1）：28-36.

［9］Manjeshwar A，Agrawal D P.TEEN：A Routing Protocol for En?hanced Efficiency in Wireless Sensor Networks.Proceedings of the 15th Parallel and Distributed Processing Symposium，2001.

［10］Ravi Kishore Kodali，Naveen Kumar Aravapalli.Multi-Level LEACH Protocol Model Using NS-3［A］.2014 IEEE International Advance Computing Conference（IACC），2014：375-380.

［11］Sapna Gambhir，Nida Fatima.Op-LEACH：An Optimized LEACH Method for Busty Traffic in WSNs［A］.2014 Fourth International Conference on Advanced Computing&Communication Technolo?gies，2014：222-2229.

［12］馬建樂，楊軍.基于位置和剩余能量的局部集中式LEACH算法研究［J］.傳感技術學報，2013，26（8）：1147-1151.

［13］陳曉娟，王搖卓，吳搖潔.一種基于LEACH的改進WSN路由算法［J］.傳感技術學報，2013，26（1）：116-121.

［14］余成波，李洪兵，陶紅艷.無線傳感網絡實用教程［M］.北京：清華大學出版社，2012.4.

［15］洪鋒，褚紅偉，金宗科，等.無線傳感器網絡應用系統最新進展綜述［J］.計算機研究與發展，2010，47（Suppl）：81-87.

［16］Intanagonwiwat C，Govindan R，Estrin D.Directed Diffusion：A Scalable and Robust Communication Paradigm for Sensor Net?works.In Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking（MOBICOM），August，2000：56-67.

［17］蘇金樹，郭文忠，余朝龍，等.負載均衡感知的無線傳感網絡容錯分簇算法［J］.計算機學報，2014，37（2）：445-456.