一種LEACH路由協議算法的改進與分析*

2015-03-25 05:16:25白永祥

通信技術 2015年9期

白永祥

(渭南職業技術學院,陜西渭南 714000)

白永祥

(渭南職業技術學院,陜西渭南 714000)

基于傳統的LEACH協議，提出了一種改進協議LEACH-CND。對無線傳感器網絡的簇頭選舉進行了優化，主要依據節點的剩余能量選舉簇頭，并求出網絡的最佳簇頭數。其次，基于橢圓曲線密碼體制的優勢，針對無線傳感器網絡節點輕量級身份密鑰加密算法進行了探討。最后，在MATLAB環境下對優化后的協議進行了仿真，證明了其可行性。達到了延長網絡生存時間的目的。

無線傳感器網絡；分層路由協議；LEACH協議算法；橢圓曲線密碼體制

0 引言

無線傳感器網絡(Wireless Sensor Network，WSN)是由部署在受監測區域內的大量低成本、低功耗、具有感知、數據存儲、數據處理和無線通信能力的傳感器節點通過自組網方式形成的一種網絡，其目的是協作的采集、處理和傳輸網絡覆蓋區域中被感知對象的信息[1]。目前，WSN應用領域非常廣泛，大量的研究成果主要集中在針對特定感知和監測應用等方面。因為傳感器節點能量有限，且大多數環境下更換電池根本不可能，所以如何降低無線傳感器網絡的能耗非常關鍵。研究證明無線傳感器網絡節點間的通信所需能耗占總電源能量的大多數，所以設計具有低能耗的WSN協議算法成了研究焦點。文章綜述了WSN中常見的幾種路由協議；詳細分析了LEACH路由協議算法及其優缺點；基于文獻[2]，對LEACH協議進行了改進，并在MATLAB環境下對改進協議進行了仿真；探討了基于ECC的WSN數據傳輸加密解密算法。

1 相關研究及分析

對于不同的傳感器網絡應用領域，研究人員提出了各種路由協議，根據網絡管理的邏輯結構可將路由協議分為平面路由和分層結構路由兩大類[3]， LEACH協議(Low Energy Adaptive Clustering Hierarchy)屬于分層結構路由協議。目前，常見的WSN路由協議有泛洪協議、SPIN、DD、SAR、GEAR、LEACH等協議，這些協議算法各有優缺點。LEACH是無線傳感器網絡中第一個層次型路由協議，多年來，基于它的改進協議層出不窮。文獻[4-5]描述了一種基于LEACH的改進型非均勻分簇協議，它根據節點到基站距離的遠近，構造出大小非均勻的簇，這種協議適合節點分布較均勻的網絡，對于分布不均勻的網絡則能量消耗更大，所以此協議的應用范圍十分有限；文獻[6]中的LEACH-C協議根據各節點的剩余能量和地理位置進行選舉簇頭，該算法雖然提高了簇的生成質量，魯棒性較好，但節點周期的向基站發送信息，增加了網絡流量和時間延遲，實時性較差；文獻[7]提出的TEEN協議具有很強的實時性，可以對突發事件產生快速反應，但由于硬、軟閾值的設置，不適合持續采集數據的應用環境；文獻[8]的LEACH-Z協議也是基于LEACH協議的改進，由基站根據能量高低對簇內每個節點進行排序并建立一個鏈表，然后選舉能量最高的節點為簇頭，減少了簇內成員選舉簇頭的能量消耗，但這種方法加大了基站的管理任務；文獻[9]提出了LEACH-M協議，它引入了遺傳模擬退火算法來保證簇的均勻分布，在很大程度上提高了簇的生成質量，同時還引入了多跳的路徑選擇算法，但也存在一些不足。典型的無線傳感器網絡體系結構如圖1所示。

圖1 典型的無線傳感器網絡體系結構

1.1 LEACH協議算法描述

LEACH協議算法是由MIT的Chandrakasan等專家設計的一種低功耗自適應集群分層路由算法。它首先將節點分成若干個簇，利用一定的算法選舉出各自的簇頭，由簇頭接收本簇內各節點的數據，再由簇頭節點對數據融合處理后發送給基站或者Sink節點。由于簇頭是隨機循環分配的，所以網絡能量損耗是平均分配的，可以延長網絡生存時間。LEACH算法具有三個特征[2]：第一，本地節點通過協調產生集群；第二，“簇頭”節點動態選舉；第三，采用數據融合技術。

LEACH協議整個過程需要以下兩個階段：形成階段和傳輸數據階段。

在形成階段，網絡中的節點能否在當前輪成為簇頭，取決于兩個因素：一個是網絡中事先假設成為簇頭的百分比，另一個是已擔任過簇頭的次數。在選舉前首先要設定一個閾值T(n)，節點在[0，1] 之間選擇一個隨機數，如果小于閾值T(n)，那么就當選為簇頭，計算公式如下[5]：

(1)

式中，n為網絡中的節點數；p為簇頭節點的百分比；r為選舉輪數；G為在1/p輪中未充當過簇頭的節點集。

當選為簇頭的節點使用CSMA/MAC協議向網絡中的其他節點發送一個廣播包，所有被當選為簇頭的節點都發送同功率的廣播包，非簇頭節點的接收器接收來自簇頭的廣播信息。在實際應用中，一些非簇頭節點可能會收到來自幾個不同簇頭的廣播信息，節點便根據信號的強弱，選擇加入信號最強的一個簇，并向該簇頭報告加入的消息，這個過程一般是通過CSMA/MAC協議完成的。當選為簇頭的節點接收到簇內成員發送的信息后，將根據簇頭節點的數量創建TDMA時刻表，并為簇內各個節點分配傳輸數據的工作時隙，以便用于發送感知數據。

簇形成后，將開始數據傳輸。簇頭節點收到來自成員的數據后將對數據進行融合和壓縮，然后再傳給基站，過一段時間后，下一輪循環重新開始，從復以上的工作過程。

1.2 LEACH算法分析

1.2.1 LEACH算法的優點

LEACH是第一個無線傳感器網絡分層式路由協議，它是后來大部分層次式協議的基礎，如TEEN協議，PEGASIS協議等。LEACH協議具有以下優點：

(1)采用層次結構，路由選擇和路由信息的存儲簡單，對節點性能要求不高，適合結構簡單的無線傳感器網絡；

(2)隨機選取簇頭，各節點機會均等，將能量負載均勻分布到網絡中的所有節點，有效避免了能量過損和單點故障問題；

(3)LEACH協議使用的技術具有很好的擴展性，簇頭的輪循增強了網絡的魯棒性。

1.2.2 LEACH算法的缺點

雖然LEACH協議通過隨機選擇簇頭的方法延長了WSN的生命周期，一般可以達到10%～20%，但它仍然存在以下缺點：

(1)每個節點都要與簇頭節點進行通信，并通過簇頭進行數據處理和傳輸，同時簇頭又要與基站或Sink進行通信，因此簇頭處于通信樞紐，簇頭節點的能量消耗會很大。如果簇頭節點出現故障，就會導致簇內數據不能有效傳輸，從而形成網絡覆蓋不全，整體監測性能降低；

(2)簇頭選舉時，各節點機會均等，沒有考慮節點之間的能量差異，造成某些能量很低的節點充當了簇頭，而不能完成整個簇內的數據高效傳送，如果能量耗盡，就成為死節點；

(3)簇頭隨機選舉法在數量和分布上往往呈現不穩定狀態，即簇頭個數偏離期望值和分布位置上不平均。如果簇頭個數很少，也就失去了分層的意義；如果簇頭個數多，又要消耗過多節點的能量。有時簇頭處于網絡邊緣，會造成與Sink通信距離增加，消耗能量較大。以上情況都使得網絡的負載平衡度降低，從而縮短WSN的壽命；

(4)最佳簇頭數的選取。簇頭個數過少，將導致各簇所覆蓋的面積過大，造成節點與簇頭節點的距離增大，節點之間傳輸數據的能耗增加，還會增加簇頭處理數據的工作量，所有這些都不利于延長網絡的生存時間。簇頭個數過多，簇頭消耗的能量比一般節點大，這樣過多的簇頭將會導致一輪中整個網絡的總能耗增大，且過多的簇頭也會降低數據的融合率，實踐證明每個WSN都存在一個最佳的簇數。

2 改進算法設計

通過以上對LEACH協議的優缺點分析，我們知道簇個數及其分布對整個無線傳感器網絡的性能有密切的關系，在簇個數及其分布算法方面進行優化十分必要。

2.1 改進方案

基于以上分析，提出一個基于簇頭數分布的LEACH協議改進算法：LEACH-CND，基本設計思路如下：

(1)對于每一個無線傳感器網絡，都存在一個最優的簇頭個數，通過算法求出這個最優個數值。并且還要保證簇頭輪換時間間隔達到一個合適的值，如果間隔時間過長，不利于數據實時傳輸，如果間隔時太短，網絡能耗會很大；

(2)在最優簇頭數確定的前提下，選舉簇頭時必須考慮了每個節點的剩余能量。對每個簇內的節點按照能量進行排序，選舉剩余能量最多的節點為簇頭，以延長網絡的生存時間；

(3)設定一個最小的簇頭距離D，保證所選舉簇頭距離每個節點的距離不能超過這個數值D，以便所選簇頭的分布比較合理，使整個網絡的簇頭處于一個合理的分布范圍內，完全合理的覆蓋整個監測區域；

(4)一般的無線傳感器網絡對安全性要求不高，但隨著無線傳感器網絡在軍事和一些重要領域的應用，保證傳輸數據的安全性非常重要，充分運用ECC短密鑰、安全性高、占用內存少等特點，設計一種數據加密解密的算法[3]。

2.2 算法實現過程

LEACH-CND算法分為兩個階段：簇建立階段和數據傳輸階段，其中數據傳輸階段使用了ECC加密解密等安全技術。下面主要關于簇最優個數、輪換時間間隔、簇頭選舉、數據傳輸安全性等方面進行設計。

2.2.1 最佳簇頭數

假定在a×a監測區域中，有N個節點組成的網絡，剛開始所有節點能量相同，并將網絡劃分成k個簇，現在要求出k的最優值，使整個網絡在某一輪通信中能耗最少。這里假設節點之間、節點到基站的通信遵守同一無線信號能耗衰減模型，即能耗與通信距離的平方成正比，這樣的假設不會影響研究結構的合理性和有效性[10]。

簇頭發送單位信息所需要的能量：

(2)

簇內成員節點發送單位信息所需要的能量：

(3)

整個簇在一輪中所需要的能量：

(4)

整個網絡在一輪中所需要的能量：

(5)

(6)

對上式求導，研究其函數特性，導數為0時，求得Etotal最小值為：

(7)

從上式可知，簇頭個數與網絡的基本參數a,N,LBS有關，所以在網絡節點初始化時就可以設定簇頭個數，從而達到最優化。

2.2.2 簇頭輪換時間間隔

在LEACH協議中，數據傳輸階段的時間要長于簇建立的時間，這樣可利于減小能耗。但數據傳輸階段的時間也不宜過長，否則會使得簇頭能量消耗過大，也應該對數據傳輸的時長進行優化，即輪換時間間隙有一個合理的值。

假設簇中的節點數為N/K，且數據l的發送時間為Ts=l/Rb，假設一個幀內的總時間為Tf=(N/k)(l/Rb)，這樣簇頭輪換的總時間為：

Tround=Nf/r×Tf=

(8)

通過以上的分析比較，即可得到理想狀態下簇頭輪換的最佳時間間隔。

2.2.3 簇頭選取及簇的形成

LEACH協議在簇頭選舉時沒有考慮節點的剩余能量，只是在每輪循環中隨機等概率地選舉簇頭，為了延長整個網絡的生存時間，在選舉簇頭時加入節點剩余能量參考值，使剩余能量較高的節點選為簇頭，從而延長網絡的壽命[10]。

改進的簇頭選舉算法流程如下：

(1)為每個節點設置定時時間，剩余能量越多，時間越短，相反則越長；

(2)所有節點定時時間確定后，節點便進入倒計時，剩余能量最多的節點時間必然最先結束，則當選為簇頭，并向簇內各節點廣播簇頭信息；

(3)各節點收到簇頭廣播信息后，計算其與簇頭的距離，如果距離小于間距D，則取消該節點的定時；

(4)網絡中的節點收到簇頭廣播的消息數量達到最佳簇頭數kopt，則停止簇頭選舉，本輪簇頭選舉結束；

(5)每個節點根據收到的簇頭廣播信息信號的強弱，決定自己加入的簇，并通知相應的簇頭，簇頭選舉及簇建立過程結束。

2.3 基于ECC的輕量級身份密鑰算法設計

由于節點資源受限，WSN的安全性問題比傳統網絡面臨更多的挑戰。近年來，基于對稱密碼算法的密鑰管理方案一直被認為是構建WSN安全的最佳選擇，比如128bitAES加密算法，已經被集成到ZigBee協議中[2]。但對稱加密算法密鑰管理相對困難，所以，一般使用對稱密碼算法對數據進行加密，而使用非對稱加密算法管理密鑰。目前，構建面向WSN應用的輕量級身份公鑰加密算法成為研究熱點。ECC是一種基于橢圓曲線的公鑰密碼算法，同其它加密算法相比較，相同長度密鑰下，ECC具有安全性高、占用內存空間小等特性，所以ECC更適合無線傳感器網絡密鑰管理。下面構造一個基于ECC的輕量級身份公鑰加密算法。

(2)密鑰組合

①計算節點散列值h=H(ID)，hi為散列值第ibit二進制值；

③節點向PKG請求私鑰；

(3)加密

(4)解密

m=c2⊕H2(c1XID)，因為：

c2⊕H2(c1XID)=(m⊕H2(rYID))⊕H2(r·PXID)=(m⊕H2(rYID))⊕H2(r·XID·P)=(m⊕H2(rYID))⊕H2(r·YID)=m

上述算法的安全性依賴于散列函數和ECC上的橢圓曲線離散對數難題，ECC的特性比較適用于無線傳感器網絡，在密鑰分發、安全認證協議等方面的應用已被證明可行。Peng N等人在TinyOS上研究ECC算法的最新成果TinyECC，進一步推進了ECC在WSN安全中的實用化進程。

3 仿真結果與分析

一個無線傳感器網絡的性能如何，主要看3個指標：首先是網絡的生存時間，其次是基站接收的數據總量，接收數據越多，說明無線傳感器網絡對所監測的區域測量越精確，協議性能也更好，最后還有負載平衡因子，它也是評價協議性能的重要指標。

3.1 仿真環境

(1)硬件環境：Intel(R)CoreTMi5-3230MCPU 2.60GHz；內存(RAM)4G，硬盤：500G；

(2)軟件環境：Windows 7旗艦版,32位操作系統，MATLAB 7。

3.2 結果與分析

3.2.1 仿真監測環境

圖2為仿真環境拓撲圖，監測節點隨機分布在100 m×100 m的區域內。

圖2 仿真環境拓撲

3.2.2 計算最佳簇頭數

無線傳感器網絡中簇頭數的多少直接影響分簇網絡的結構和特性，簇頭數的數量應以滿足系統要求和減少能耗為準則[10]。根據以上設計方案，在MATLAB下實現了仿真，圖3是簇頭數與網絡中每輪平均能耗的仿真圖，可以看出當k=5時總能耗最低，約為9 J。如果簇頭數小于5，那么網絡中的簇頭數過少，節點傳輸距離過大，消耗的能量較多；如果簇頭數大于5，網絡中簇頭數量過多，消耗的能量增加。所以在本文假設的環境下最佳簇頭數kopt=5。

圖3 簇頭節點數與能耗的關系

3.2.3 LEACH-CND協議性能分析

LEACH-CND協議是對LEACH協議的一種改進，仿真時主要與LEACH-C、LEACH協議進行了比較，還與平面型協議MTE進行了比較，意在顯示層次性協議的優越性[11]。從圖4仿真結果可以看出，LEACH-CND協議中網絡中存活的節點數量比較多，從而延長了WSN網絡的生命周期。

圖4 4種協議網絡生存時間仿真結果比較

3.2.4 接收數據總量比較

圖5是4種協議接收數據總量的仿真結果，該結果顯示了經典型LEACH協議、LEACH-C協議、平面型路由協議MTE[12]及改進的LEACH-CND協議數據接收數據總量的比較，可以看出在相同時間內，LEACH-CND協議接收數據總量大于其它幾種協議。

圖5 4種協議接收數據總量比較

4 結語

總之，采用什么樣的路由協議直接關系無線傳感器網絡的性能。為了減少節點能量的損耗，延長無線傳感器網絡的壽命，我們對LEACH協議進行了改進。改進后的協議對簇頭選舉進行了優化，主要體現在根據節點剩余能量及求出最佳簇頭數等方面，提高了WSN整體生存時間[13]。在MATLAB環境下實現了仿真，驗證了改進后LEACH-CND協議的可行性。當然，方案還存在一些不足，比如沒有實現LEACH-CND協議在網絡負載平衡方面的仿真結果，沒有全面深入地探討ECC在WSN安全方面的應用，因此，下一步還有大量工作需要開展。

[1] 張玉泉.網絡安全問題研究[M]. 濟南：山東人民出版社，2013：5-10. ZHANG Yu-quan. Research of Problems for Network Security [M]. Jinan: Shandong People′s Publishing House, 2013. 5-10.

[2] [美]Ian F. Akyidiz, Mehmet Can Vuran. 無線傳感器網絡[M]. 徐平平，劉昊，褚宏云等譯. 北京：電子工業出版社，2013：121-142. [US]Ian f. Akyidiz, Mehmet Vuran. Wireless Sensor Networks[M]. Translated by XU Ping-ping,LIU Hao,ZHU Hong-yun et al. Beijing:Electronic Industry Press,2013:121-142.

[3] 陶偉.基于HTc rf SQUID的通信傳感器技術[J].通信技術，2015，48(02)：130-134. TAO Wei. Communication Sensor Technology based on HTc rf SQUID[J].Communications Technology,2015,48(02):130-134.

[4] Soro S, Heinzelman W. Prolonging the Life of Wireless Sensor Networks via Unequal Clustering[M]. Proc. Of the 5thInternational Workshop in Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks, Denver, 2005：200-210.

[5] Changjiang J,Weiren S, Min X, Xianlun T.Energy-balanced Unequal Clustering Protocol for Wireless Sensor Networks[J]. The Journal of China Universities of Posts and Telecommunications,2010,17(4):94-99.

[6] Heinzelman, Chandrakasan, Balakrlshnan . An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communicatioans,2002,1(4)：660-670.

[7] Manjeshwar,Grawal. TEEN:A Protocol for Enhanced Efficiency in Wireless Sensor Networks[C]. Proc. Of the 1stInternational Workshop on Paralled and Distributed Computing Issues in Wireless Networks and Mobile Computing,2001,2009-2015.

[8] 王選政，李臘元，張偉華等.無線傳感器網絡路由協議研究[J].計算機應用研究，2009，26(04)：1453-1455. WANG Xuan-zheng,LI La-yuan,Zhang Wei-hua et al. Wireless Sensor Networks Routing Protocol Research[J]. Computer Application Research,2009,26(04):1453-1455.

[9] 佘靜濤，胡同森，鐘明霞.無線傳感器網絡路由協議LEACH的研究與改進[J]. 計算機系統應用，2009，18(02)：30-34. SHE Jing-tao, HU Tong-sen, ZHONG Ming-xia. Research and Improvement of the Wireless Sensor Networks Routing Protocol for LEACH [J]. Application of Computer System,2009,19(02):30-34.

[10] 李岳衡，王慧斌.無線傳感器網絡與監測應用[M].北京：國防工業出版社，2011:37-57. LI Yue-heng,WANG Hui-bin. Monitoring and Applications of the Wireless Sensor Networks[M]. Beijing: National Defence Industry Press, 2011 37-57.

[11] 畢嘉娜.無線傳感器網絡節能安全協議研究[M].沈陽：東北大學出版社，2013:65-77. BI Jia-na. Research of Energy-Saving Security Protocol for Wireless Sensor Networks [M]. Shenyang: Northeastern University Press, 2013:65-77.

[12] [美]胡飛(HU Fei)，曹小軍(CAO Xiao-jun).無線傳感器網絡原理與實踐[M]. 胡飛，曹小軍，牛曉光，宮繼兵等譯.北京：機械工業出版社，2015：69-95. [US] HU Fei, CAO Xiao-jun. The Wireless Sensor Networks Principles and Practice[M].Translated by HU Fei,CAO Xiao-jun,NIU Xiao-guang, GONG Ji-bing. Beijing: Mechanical Industry Press, 2015:69-95.

[13] 陳志德，許力.無線傳感器網絡節能、優化與可生存性[M].北京：電子工業出版社,2013：69-84. CHEN Zhi-de, XU Li. Wireless Sensor Networks Energy Saving, Optimizing and Survivability[M]. Beijing: Electronic Industry Press. 2013:69-84.

Improvement and Analysis of LEACH Routing Protocol Algorithm

BAI Yong-xiang

(Weinan Vocational Technical College, Weinan Shaanxi 714000,China)

Based on the traditional LEACH protocol, an improved LEACH-CND protocol is proposed. The cluster head election of WSN network is optimized and implemented on the basis of residual energy, and the best cluster numbers of the wireless sensor networks is thus calsulated. Meanwhile, based on the advantage of the elliptic curve cryptosystem, the lightweight identity key encryption algorithms for WSN node is explored. Finally, simulation on the optimized protocol in MATLAB environment indicates its feasibility, and that it could prolong survival time of WSN networks.

WSN(Wireless Sensor Network)；hierarchical routing protocol；LEACH protocol algorithm；elliptic curve cryptography

2015-04-01；

2015-07-29 Received date:2015-04-01；Revised date：2015-07-29

渭南市科技創新扶持資金(No.2013JCYJ-6)

Foundation Item:Weinan Supported Funding for Science and Technology Innovation (No.2013JCYJ-6)

TP393.06

1002-0802(2015)09-1062-06