低功耗自適應分群分層LEACH協議的研究

韓春霞，王琳杰

(1.銅仁學院數學與計算機科學系,554300；2.銅仁學院計算機應用技術研究所，貴州銅仁,554300)

目前，無線傳感器網絡的路由協議是國內研究的熱點。一個路由協議往往對能量有效性、可擴展性、數據傳輸可靠性、實現復雜度、穩健性等很多因素進行綜合考慮而折中得到的。根據節點在路由過程中是否有層次結構、作用是否有差異，可分為平面路由協議和層次路由協議。平面路由協議簡單、健壯性好，但建立、維護路由的開銷大，可以用于中小規模的網絡；層次路由則能夠提高協議的可擴展性，同時還能方便地支持數據聚合，適用于大規模網絡，成為當前重點研究的路由技術。

無線傳感器網絡低能量自適應分群分層LEACH（Low Energy Adaptive Clustering Hierarchy）是一個協議體系，進行本地計算以減少發送數據量，采用本地控制進行網絡配置和網絡操作。LEACH將能量高效分群路由協議和MAC協議與應用特定數據累積綜合在一起，共同達到良好的系統壽命、時延、應用感覺到的服務質量。LEACH是能夠組織大量節點的分布式分群技術，實現均勻分布所有節點間能量的自適應算法和群首位置循環算法。

LEACH協議有更優于其他的路由協議的特性，但也存在著許多的不足之處有待研究改進，本文就LEACH協議的改進方案作為研究的主要目標。

1 LEACH協議概述

低功耗自適應分群算法(LEACH)并不是一個單純的路由協議，它提供了一個包括分群、路由、MAC和物理層的完整的無線傳感器網絡的協議框架。LEACH把網絡的工作過程分成輪，每一輪包括建立期和穩定期。在建立期執行分群協議，把網絡分成若干個群；穩定期分成若干幀，在每一幀，成員節點向群首發送數據，群首合并后發送給遠端的BS。

在LEACH協議中，群首是本地控制中心，協調其群內的數據傳輸。其中，主要是分群建立階段、數據穩定傳輸階段。在分群建立階段，傳感器節點隨機生成一個0-1之間的隨機數，如果選定的值小于某一域值T(n)，那么這個節點成為群首節點。在數據穩定傳輸階段，傳感器節點在自己的時隙中將采集的數據傳送到群首節點，群首節點經過數據融合再將數據傳送到BS基站。每個群采用不同的CDMA代碼進行通信減少其他群內節點的干擾，詳細的LEACH協議工作流程可參見文獻資料。

2 LEACH的改進策略

2.1 LEACH協議的優缺點

相比于其他路由協議，雖然LEACH協議擁有許多優點。比如動態分配群首算法、分層簇型結構等。盡管如此，LEACH也存在著許多不足，在LEACH協議中，群首的選擇由隨機數產生，很少考慮當前節點剩余能量及當前節點與Sink節點的位置關系，導致WSN中節點間的能量不均衡及位置分布不均勻。在每次建立分群的過程中，每個非群首節點也要參與其中，這就增加了分群的復雜程度。在數據傳輸階段，由于群首節點與Sink節點直接通信，導致遠離Sink節點的群首消耗更多的能量，致使該節點迅速死亡，出現監控盲區。

2.2 LEACH的改進策略

LEACH算法的改進是多種多樣的，近年來，國內外許多研究學者提出了很多改進算法。在LEACH協議改進中，很多人一直是把改進群首選擇算法作為研究的重點，比如在早期的改進算法中有DCHS，它的改進是在選取群首概率公式中加入了能量比例因子，使剩余能量較高的節點有更多的機會當選為群道節點，但這并沒有考慮這個節點是否曾當選過群首節點。

LEACH-C和LEACH-F采用的都是中心分群算法，它們在數據穩定傳輸階段與LEACH協議相同。在分群建立階段，是通過每個節點發送其當前位置信息和能量信息給BS進行信息交互，為此，BS根據所得的每個節點的信息，結合全局信息尋找最佳群首。但是這兩種算法，每次通信每個節點都要與BS進行交互信息，增加了不少的能量消耗。

王萬良等人提出了一種基于LEACH的改進算法，改進思想是在分群的建立階段，所有候選節點必須是曾從未當選過群首的節點，并且該侯選節點的能量必須大于前r輪中群首節點的平均能量，防止個別節點快速死亡。該算法的缺點是每個參與競爭群首的節點必須知道前r輪群首節點的平均能量，需要多次與BS進行信息交互，增加了一定的能量消耗。

顧相平等人提出了LEACH-ED算法，該分群算法結合了剩余能量和群首間距離約束。在選擇群首時，如果生成的隨機數小于加入能量因素的閥值，就計算該節點與群首間的距離，當大于某一距離時，該節點才能成為群首。由于每次都需要計算競選群首節點與現有群首節點間的距離，這不僅增加了算法的復雜度，還增加了節點的能量消耗。

李天池提出了LEACH-IMP算法，該算法主要針對群首選擇提出的改進策略。LEACH-IMP將LEACH群首選擇分為了全網群首選擇，半網群首選擇，群內群首選擇。在改進算法中，先設置了一個能量閥值，每個分群周期開始時，計算平均群能量和群內平均能量，判斷現有群中的平均群能量是否小于能量閥值，如果是，啟動半網群首選擇號召，這時其他的群根據自己群的情況決定是否要響應半網群首選擇號召，所有響應半網群首選擇號召的群將在下一輪中按照全網選擇規則進行重選。否則，每個群首再判斷自己的剩余能量是否小于群內平均能量，如果比群內平均能量小，則在本群內響應群首選擇，否則，不進行任何群首選擇。此算法的改進，可以避免每輪群首選擇時，都要進行全網群首選擇。設置每隔一定輪數后，強制進行全網選擇，可以平衡半網選擇導致的能量不均衡。在全網選擇機制和半網選擇機制中，改進算法均考慮了能量因子和距離因子，使距離近的節點能更大的機會當選為群首，以更好地均衡能量消耗。但在半網選擇中，每一輪，都要計算群內平均能量，一定程度上，又增加了能量消耗，從改進算法的流程看，又增加算法的復雜度。

柳麗娜提出的LEACH-L算法針對LEACH算法中群首選擇的不均以及能耗較大等問題進行改進。在群首選舉階段，改進主要通過引入時間延遲Twait ，使剩余能量越大的節點以更大的可能性成為群首，這就使整個網絡系統的能耗更為均衡，同時從覆蓋面積的角度進行考量，使群首的分布更加均勻。在數據傳輸階段，LEACH-L采用的是單跳和多跳相結合的方式。最開始選取群首的時候所有節點都向基站發送了信息，基站對每個群首的地理位置和剩余能量等信息都了如指掌，并且因為基站的位置是固定不變的，所以每個群首到基站的距離都是可以知道的，于是把群首剩余能量和他們與基站的距離作為判斷的標準來確定是選擇單跳還是多跳的方式進行數據通信。

劉長江提出了一種加權的最優閥值路由算法LEACH-M，LEACH-M算法在群首選擇時，改進重點是提出新的節點閥值計算公式T（n），該公式考慮了能量和節點未當選群首的的輪數。在群的建立時，LEACH-M引入權重因子F，該公式綜合考慮了節點與群首、群首與BS間距離、群首剩余能量等因素。這樣引入F，在群的建立階段，盡可能使群首分布均勻，而且減少網絡中能量的消耗，達到節能。

李成岳等人提出的LEACH-T算法的改進主要針對群首的選擇過程。在群首選擇時，引入一個隨機時間間隔，為每個節點設置一個計時器T，T的計算綜合考慮節點的剩余能量、節點距離BS的位置、節點曾經當選群首的次數，當到達計時時間后，具有最短時間間隔的節點有更大機會成為群首節點。與原有的LEACH算法相比，LEACH-T具有更好的性能，它不僅保留了分布式群首產生的優點，還避免了每輪產生群首個數的不確定性，更能均勻分布群首節點，使群首節點的選擇趨于合理，從而達到網絡能耗均衡，節省能量，最大化生命周期的目的。

3 總結

LEACH算法的改進是多種多樣的，在上述的改進方案中，有的提出了一套完整的從群首選擇到數據傳輸的新的算法，而有的改進算法只是針對其中一個階段提出了新的想法。以上關于LEACH協議算法的改進仍然保留著原有的LEACH協議算法思想，都是以如何節省能量和延長網絡生命周期作為改進考慮的核心問題。對以上算法的改進，仿真實驗表明，相比于傳統的LEACH在延長網絡生存時間、節省能量和平衡節點能量消耗等方面有更優的性能。

[1]陳林星編著.無線傳感器網絡技術與應用[M].電子工業出版社.2009.3:151-156

[2]Handy M J,Haase M,Timmermann D.Low Energy Adaptive Clustering Hierarchy W it h Deter ministic C luster-head Selection[C]//Proceedings of the 4th I EEE Conference on Mobile and Wireless Communications Networks.I EEE Communications Society,2002:368-372.

[3]Heinzelman W B.Application-Specific Prot ocol Architect u res for Wireless Network s[D].Ph.D Dissertation.Boston:Massachusetts Institute of Technology,2000.

[4]王萬良,陳陪俊,鄭建煒.一種基于 LEACH的無線傳感器路由算法及其仿真[J].系統仿真技術,2008,4(2):75-79

[5]顧相平,孫彥景,錢建生.一種改進的無線傳感器網絡 LEACH-ED 算法[J].傳感技術學報,2008,21(10):1770-1774

[6]李天池.無線傳感器網絡LEACH協議的算法改進[D],山東大學.2012.3

[7]柳麗娜.無線傳感器網絡中LEACH算法的研究和改進[D],吉林大學.2012.5

[8]劉長江.基于能耗優化的無線傳感器網絡LEACH協議研究與改進[D].廣西大學.2012.6

[9]李成岳,申鉉京,陳海鵬,孫恩巖.無線傳感器網絡中LEACH路由算法的研究與改進[J].傳感技術學報.2010年8月第23卷第8期:1163-1167