李亞男，徐夫田，陳金鑫(.山東師范大學信息科學與工程學院，濟南25004;2.山東省地方稅務局信息中心，濟南25004)

基于LEACH的WSNs分簇優(yōu)化策略

李亞男1，徐夫田2*，陳金鑫1
(1.山東師范大學信息科學與工程學院，濟南250014;2.山東省地方稅務局信息中心，濟南250014)

針對LEACH算法中能量消耗不均勻的缺陷，本文提出了一種改進的路由協(xié)議來提高無線傳感器網(wǎng)絡的能量效率。在簇首選擇階段，引入節(jié)點剩余能量和初始能量來調(diào)節(jié)傳感器節(jié)點隨機數(shù)的大小;在成簇階段，該算法將節(jié)點的剩余能量和距離匯聚節(jié)點的遠近作為成簇的依據(jù)，使簇首的分布更加合理;在數(shù)據(jù)傳輸階段，將節(jié)點與匯聚節(jié)點之間的距離及節(jié)點的剩余能量相結合，提出一種單跳與多跳相結合的傳輸方式，從而減少了能量消耗。仿真實驗表明，改進后的算法能夠更好的減少能耗，延長無線傳感器網(wǎng)絡的生命周期。

無線傳感器網(wǎng)絡;LEACH算法;隨機數(shù);剩余能量

無線傳感器網(wǎng)絡是由大量低成本、低能量的無線傳感器節(jié)點組成的，它們被部署在指定的區(qū)域，動態(tài)的收集環(huán)境信息、相互協(xié)作，不斷的將重要數(shù)據(jù)信息傳到匯聚節(jié)點，達到無人值守、自動檢測環(huán)境的目的［1-2］。作為一種新興的信息獲取方式和處理模式，WSNs在很多領域得到了廣泛的應用。在軍事方面的應用主要是實現(xiàn)對敵軍兵力和裝備的監(jiān)控、對戰(zhàn)場的實時監(jiān)控、目標的定位、戰(zhàn)場評估、化學攻擊等，在環(huán)境科學中的應用是為野外隨機性的研究數(shù)據(jù)獲取提供方便［3］。由于無線傳感器節(jié)點大多采用能量有限的電池供電，且節(jié)點數(shù)目多、分布廣、所處環(huán)境復雜，很難對節(jié)點充電以及受成本和體積的限制，節(jié)能是WSN需要高度重視的問題［4-5］。因此設計無線傳感器網(wǎng)絡的首要目標就是盡可能的減少能量消耗，延長網(wǎng)絡的生命周期。在WSNs體系中，路由協(xié)議是一個非常重要的研究領域，網(wǎng)絡層路由技術的設計對WSNs中的能量效率有重要影響。因此設計優(yōu)化網(wǎng)絡的整體能耗效率、延長網(wǎng)絡壽命的路由協(xié)議是無線傳感器網(wǎng)絡的一項重要研究內(nèi)容［6］。

LEACH(Low-Energy Adaptive Clustering Hierar-chy)［7］協(xié)議是最早的WSNs分簇路由協(xié)議，但是沒有考慮到節(jié)點的能量因素，從而造成某些節(jié)點過早死亡，整個網(wǎng)絡能量消耗不均，縮短了網(wǎng)絡的生命周期。目前對LEACH協(xié)議的改進主要是針對簇首的選擇，成簇的過程及數(shù)據(jù)傳輸進行改進的，文獻［8］的S-LEACH(Specifically-LEACH)中在成簇階段采用分布式自協(xié)商和集中式相結合的算法以及設計了局部路由維護機制，此算法的優(yōu)點是在能量耗盡導致的節(jié)點失效后，不會產(chǎn)生路由斷點，缺點是集中式成簇開銷較大，不利于網(wǎng)絡的擴展。文獻［9］在路由機制上采用單挑與多跳相結合的方式，采用MTE機制，優(yōu)點是在簇首選擇時考慮的節(jié)點的能量狀態(tài)，缺點是在路由機制上只考慮的距離因素而未考慮節(jié)點的剩余能量因素。文獻［10］的LEACH-PSOC算法利用粒子群算法的收斂性和全局優(yōu)化能力將整個網(wǎng)絡區(qū)域分割成多個字區(qū)域并考慮節(jié)點的剩余能量，此算法使簇頭分布均勻，減少了能量消耗，但增加了網(wǎng)絡延遲。文獻［11］通過對網(wǎng)絡中信息素濃度的建立和更新，達到降低簇頭節(jié)點能量消耗過快的問題，此算法簇頭分布均衡，優(yōu)化了路由選擇路徑，但在數(shù)據(jù)傳輸階段由于對網(wǎng)絡進行搜索遍歷，造成能量的消耗。

本文在借鑒上述改進算法的優(yōu)點后提出一種新的改進算法，在簇首選擇階段，根據(jù)節(jié)點剩余能量和初始能量調(diào)節(jié)傳感器節(jié)點生成隨機數(shù)的大小，在成簇階段，將節(jié)點的剩余能量和距離匯聚節(jié)點的遠近作為成簇的依據(jù);在數(shù)據(jù)傳輸階段，根據(jù)節(jié)點與匯聚節(jié)點的距離及其剩余能量采用單跳與多跳相結合的方式傳輸，從而減少了能量消耗，優(yōu)化了數(shù)據(jù)傳輸路徑，延長網(wǎng)絡的生存周期。

1 LEACH協(xié)議簡介

LEACH協(xié)議的執(zhí)行過程按輪周期性的運行，節(jié)點根據(jù)某個閾值等概率的成為簇首。LEACH協(xié)議使用的網(wǎng)絡模型具有以下特點［12］:①所有的傳感器網(wǎng)絡節(jié)點都是同構的，初始能量相同，都使用全向天線;②傳感器網(wǎng)絡節(jié)點都是靜止的，不具有移動性;③所有傳感器節(jié)點都可以和匯聚節(jié)點直接通信;④信道采用對稱信道。

LEACH協(xié)議的執(zhí)行過程分為2個階段:成簇階段和數(shù)據(jù)傳輸階段。數(shù)據(jù)傳輸階段的時間比成簇時間長。一個成簇階段和一個數(shù)據(jù)傳輸階段就構成了一輪。在成簇階段，每個節(jié)點生成0～1之間的隨機數(shù)，如果生成的隨機數(shù)小于閾值T(n)，那么該節(jié)點被當選為簇頭，并向周圍節(jié)點廣播其成為簇頭的消息。閾值T(n)計算式(1)為:

其中:P是網(wǎng)絡中簇頭占所有節(jié)點比例，即節(jié)點當選簇頭的概率;r是目前循環(huán)進行的回合數(shù)，G是在最后1/p輪中還未當選過簇頭的節(jié)點集合。通過這個閾值當選為簇頭的節(jié)點向外發(fā)送廣播消息，周圍節(jié)點根據(jù)接收到的信號強度決定要加入的簇并通知簇首要加入該簇。簇頭收到加入請求后將節(jié)點加入自己的路由表并為每個節(jié)點設定一個TDMA時間表，再將該表發(fā)送給所有簇內(nèi)節(jié)點。此后的簇穩(wěn)定階段，節(jié)點按照該表進行數(shù)據(jù)傳輸。每隔一定時間整個網(wǎng)絡重新進入簇形成階段開始新一輪的簇頭選舉過程［13-14］。

LEACH算法雖然是比較經(jīng)典的分簇協(xié)議，但是該算法的簇首分布不合理，網(wǎng)絡中的能量消耗不均勻，從而造成某些節(jié)點過早死亡，整個網(wǎng)絡能量消耗不均，縮短了網(wǎng)絡的生命周期。

2 基于LEACH協(xié)議的改進算法

2.1 改進后的系統(tǒng)模型

2.1.1 網(wǎng)絡模型

①網(wǎng)絡中的所有節(jié)點具有相同的初始能量，隨機分布并且部署后不再移動;②匯聚節(jié)點位置固定，能量無限;③網(wǎng)絡中所有節(jié)點的位置未知，無需定位系統(tǒng)或定位算法求解節(jié)點的位置;④所有網(wǎng)絡節(jié)點的發(fā)射功率固定，每個節(jié)點可以通過接收到信息的信號強度(RSSI)判斷自身距離發(fā)送者的近似距離;⑤網(wǎng)絡中所有節(jié)點可以計算出自己當前的剩余能量。

2.1.2 能量模型

本算法的能量模型采用文獻［15］，能耗的計算公式如下:

數(shù)據(jù)發(fā)送消耗的能量公式為(2):

數(shù)據(jù)接收消耗的能量公式為(3):

數(shù)據(jù)融合消耗的能量公式為(4):

其中ET(k，d)為發(fā)送數(shù)據(jù)消耗的能量，Eelec為發(fā)射電路消耗的能量，當d≤d0時，采用自由傳輸模型，消耗的能量為εfs，當d＞d0時采用多徑衰減模型，消耗的能量為εmp，ER(k)為接收數(shù)據(jù)消耗的能量，Eg(k)為數(shù)據(jù)融合及融合后發(fā)送數(shù)據(jù)消耗的能量。

根據(jù)文獻［16］，可以得出信號強度和接收節(jié)點距離發(fā)送節(jié)點的距離d的關系，式(5)如下:

其中:r是接收節(jié)點和發(fā)送節(jié)點之間的距離，PR是無線信號的接收功率，n是傳播因子。

2.2 改進后的工作過程

本文在考慮了節(jié)點剩余能量和節(jié)點接收到信號的強弱程度選擇加入簇的基礎上，對LEACH協(xié)議進行了改進，和LEACH算法一樣，改進算法依然分為輪，每一輪分為簇首的選擇、簇的形成和數(shù)據(jù)傳輸3個階段。

2.2.1 簇頭選舉階段

在簇頭選舉階段，通過對LEACH中每個節(jié)點產(chǎn)生的隨機數(shù)進行改進，從而完成簇首的選擇。閾值T (n)不變，比較節(jié)點產(chǎn)生的隨機數(shù)與閾值T(n)的大小，若生成的隨機數(shù)小于閾值T(n)，那么該節(jié)點被當選為簇頭，并向周圍節(jié)點廣播其成為簇頭的消息。改進后每個節(jié)點產(chǎn)生(0，1)之間的隨機數(shù)為:

其中r(i)為節(jié)點i在(0，1)之間產(chǎn)生的隨機數(shù)，Ei-residual為節(jié)點的剩余能量，Ei-init為網(wǎng)絡中所有節(jié)點的初始能量，Ri為調(diào)整后的最終隨機數(shù)。這樣剩余能量大的節(jié)點產(chǎn)生的隨機數(shù)越小，就越容易成為簇首。

此階段，除了節(jié)點產(chǎn)生的隨機數(shù)不同外，簇首選舉過程與LEACH算法相同。

2.2.2 簇的建立階段

①簇頭選舉完后，每個簇頭節(jié)點向網(wǎng)絡中的所有剩余節(jié)點廣播自己成為簇首的消息，假設節(jié)點的傳輸范圍為r=50 m，簇頭則僅對傳輸范圍內(nèi)的節(jié)點發(fā)送廣播信號，剩余節(jié)點根據(jù)接收到的信號強度來決定加入哪個簇。這是由于在無障礙物的情況下，節(jié)點接收到的信號強度越大，說明距離發(fā)送節(jié)點的距離越近，節(jié)點接收到簇頭發(fā)送的信號強度用str(head)表示;②同時Sink節(jié)點向所有非簇頭節(jié)點發(fā)送信號，信號強度用str(Sink)表示;③節(jié)點比較從Sink節(jié)點和從簇頭節(jié)點接收的信號強度。若從Sink節(jié)點接收的信號強度較大，即str(head)＜str(Sink)，則此節(jié)點不加入任何簇，而是與Sink節(jié)點直接通信，將其收集的數(shù)據(jù)直接發(fā)送給Sink節(jié)點，這也降低了簇頭節(jié)點的能量負載，使得簇頭節(jié)點的能量消耗減少。若從簇首節(jié)點接收的信號強度較大，即str(head)＞str(Sink)，則該節(jié)點加入該簇頭所在的簇。

2.2.3 中繼節(jié)點選舉階段

中繼節(jié)點的選舉以節(jié)點的剩余能量為依據(jù)，每個簇首節(jié)點以半徑2r廣播自身ID和剩余能量消息，以此更新其鄰居表。然后將鄰居表中的各簇首節(jié)點的剩余能量進行比較，選取值最大的作為其中繼節(jié)點。

2.2.4 多跳路由策略

在該階段，Sink節(jié)點再次向各簇頭節(jié)點發(fā)送信號，各簇頭節(jié)點根據(jù)接收到的信號強度和自身的剩余能量選擇單跳路由或者多跳路由。首先，若簇頭節(jié)點接收到的信號強度大，說明此簇頭節(jié)點距離Sink節(jié)點較近;其次，各簇頭節(jié)點將自身的剩余能量與網(wǎng)絡中所有節(jié)點的平均能量進行比較，若Ei-residual≥Eaverage，則此簇頭節(jié)點與Sink節(jié)點直接通信;若Ei-residual＜Eaverage，則此簇頭節(jié)點與Sink節(jié)點以多跳方式通信，多跳方式通信的中繼節(jié)點選擇距離此簇頭節(jié)點最近且能量較大的簇頭節(jié)點。若簇頭節(jié)點接收到的信號強度小，則都以多跳方式與Sink節(jié)點通信。

2.2.5 數(shù)據(jù)傳輸階段

該階段主要分為3個階段:①對于直接與Sink節(jié)點通信的節(jié)點將收集的數(shù)據(jù)傳送給Sink節(jié)點;②簇內(nèi)成員節(jié)點到簇首節(jié)點。根據(jù)簇首為各成員節(jié)點分配的TDMA時隙表，簇內(nèi)成員節(jié)點將收集到的數(shù)據(jù)在自己的時隙內(nèi)發(fā)給簇首，非時隙時間休眠以節(jié)省能量;③簇首節(jié)點到中繼節(jié)點。各成員節(jié)點將數(shù)據(jù)發(fā)送給簇首后，簇首進行數(shù)據(jù)融合后將數(shù)據(jù)發(fā)給中繼節(jié)點;④中繼節(jié)點到Sink節(jié)點。中繼節(jié)點將數(shù)據(jù)進行數(shù)據(jù)融合后將數(shù)據(jù)發(fā)給Sink節(jié)點。

2.3 改進后的網(wǎng)絡拓撲結構

改進后的拓撲結構如圖1所示。距離Sink節(jié)點近的節(jié)點直接將數(shù)據(jù)傳給基站，距離基站較遠且能量不足的節(jié)點先將數(shù)據(jù)融合后傳給中繼節(jié)點，中繼節(jié)點再將數(shù)據(jù)傳給基站，其他剩余能量大的簇頭則直接將數(shù)據(jù)傳給基站。

圖1 拓撲結構

3 仿真及結果分析

本文使用MATLAB仿真LEACH算法和改進后的算法，主要參數(shù)的設置參考文獻［17］，如表1所示。分別從網(wǎng)絡生存時間、節(jié)點數(shù)與能量消耗關系、網(wǎng)絡吞吐量三方面進行仿真比較。

表1 仿真參數(shù)

3.1 網(wǎng)絡生存時間比較分析

分別在大小為100 m×200 m和300 m×400 m的區(qū)域內(nèi)，比較兩者節(jié)點的存活數(shù)量隨時間變化的情況，如圖2所示。

圖2 生存時間曲線

從圖2可得出:改進后的算法比LEACH算法性能高。在300 m×400 m區(qū)域里，第1個節(jié)點死亡時，改進后的算法比LEACH算法性能提高了300%。因為考慮了節(jié)點的剩余能量因素，所以均衡了網(wǎng)絡的能量消耗，減少了第1個節(jié)點的死亡時間，延長了網(wǎng)絡的生存時間，提高了網(wǎng)絡的壽命。

3.2 節(jié)點數(shù)與能耗關系的比較分析

圖3是節(jié)點數(shù)目與平均能量消耗之間的關系仿真結果。從圖3可以看出，在節(jié)點數(shù)目小于175時，兩者都是隨著節(jié)點數(shù)目的增加而增加，節(jié)點數(shù)目超過175后，LEACH算法的平均能量消耗成上升趨勢，而改進后的算法平均能耗成下降趨勢。因此，在節(jié)點數(shù)目超過175后，改進后的算法能量消耗少，從而延長網(wǎng)絡的生命周期。

圖3 節(jié)點數(shù)與平均能耗曲線

3.3 網(wǎng)絡吞吐量比較分析

如圖4所示，隨著網(wǎng)絡運行時間的增加，Sink節(jié)點接收到的數(shù)據(jù)總量的變化情況。隨著網(wǎng)絡運行時間的延長，改進后算法Sink節(jié)點接收到的數(shù)據(jù)總量在一個生命周期內(nèi)比LEACH算法多近1.3倍。因此改進后的算法在網(wǎng)絡吞吐量性能上要優(yōu)于LEACH算法。

圖4 網(wǎng)絡吞吐量曲線

4 結束語

本文針對LEACH協(xié)議的不足，對其進行了改進。主要在簇首選擇階段，將節(jié)點的剩余能量和初始能量考慮進來作為隨機數(shù)的調(diào)整因素，其次在成簇的過程中，將節(jié)點的剩余能量和距離匯聚節(jié)點的距離考慮進來，優(yōu)化了整個網(wǎng)絡的成簇結構，減少了能量消耗，最后在數(shù)據(jù)傳輸階段，采用單跳與多跳相結合的方式進行數(shù)據(jù)傳輸，優(yōu)化了數(shù)據(jù)傳輸路徑，使簇首負載均衡，延長了整個無線傳感器網(wǎng)絡的生命周期。

［1］鄧亞平，鄧利軍.無線傳感器網(wǎng)絡的能量有效加權分簇算法［J］.計算機工程與設計，2011(4):1216-1219.

［2］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Micro Sensor Networks［C］//Proceedings of the Hawaii Conference on System Sciences，2000.

［3］劉東江，賈卓生.基于分簇的無線傳感器網(wǎng)絡路由協(xié)議的研究［J］.計算機科學，2012，39(10):23-25.

［4］王海濤.無線傳感網(wǎng)絡中的分簇協(xié)議綜述［J］.傳感器世界，2011(4):6-10.

［5］劉群，白全煒，曾憲華，等.能量感知的WSN節(jié)點分類控制路由算法［J］.傳感技術學報，2011，24(7):1053-1059.

［6］李建奇，曹斌芳，王搖立，等.一種結合LEACH和PAGASIS協(xié)議的WSN的路由協(xié)議研究［J］.傳感技術學報，2012，25(2): 263-267.

［7］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocolfor Wireless Microsensor Networks［C］//Proc of the 33rd An-Nual Hawaii Int’l Conf.on System Sciences.Maui: IEEE Computer Society，2000:3005-3014.

［8］李芳芳，王靖.一種基于LEACH協(xié)議的無線傳感器網(wǎng)絡路由算法［J］.傳感技術學報，2012，25(10):1445-1451.

［9］胡鋼，謝冬梅，吳元忠.無線傳感器網(wǎng)絡路由協(xié)議LEACH的研究與改進［J］.傳感技術學報，2007，20(6):1391-1396.

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

［11］胡彧，王靜.基于蟻群算法的LEACH協(xié)議研究［J］.傳感技術學報，2011，24(5):747-751.

［12］張怡，李云，劉占軍，等.無線傳感器網(wǎng)絡中基于能量的簇首選擇改進算法［J］.重慶郵電大學學報(自然科學版)，2007，19 (5):613-616.

［13］楊冕，秦前清.基于無線傳感器網(wǎng)絡的路由協(xié)議［J］.計算機工程與應用，2004，32:130-131.

［14］黃少昱，曹陽，王悅偉.無線傳感器網(wǎng)絡中的路由技術［J］.計算機工程與應用，2004，19:123-126.

［15］Heinzelman W R.An Application Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Trans on Wireless Communications，2002，1(4):660-670.

［16］方震，趙湛，郭鵬，等.基于RSSI測距分析［J］.傳感技術學報，2007，20(11):2526-2530.

［17］Huang Wenwen，Peng Yali，Wen Jian，et al An Energy-Efficientmultihop Hierarch Routing Protocol for Wireless Sensor Networks［C］//Proceeding of the 2009 Intermational Conference on Networks Security，Wireless Communications and Trusted Computing Washington DC，USA，2009:469-472.

李亞男(1988-)，女，碩士研究生，主要研究方向為無線傳感器網(wǎng)絡，lynwu. di@163.com;

徐夫田(1965-)，男，博士，山東省地方稅務局信息中心主任，主要研究方向為電子政務、數(shù)據(jù)庫，670793991@qq.com;

陳金鑫(1988-)，男，碩士研究生，主要研究方向為無線傳感器網(wǎng)絡，728839869 @qq.com。

Clustering Optimization Strategy for WSNs Based on LEACH

LI Yanan1，XU Futian2*，CHEN Jinxin1

(1.Department of Information Science and Engineering，Shandong Normal University，Jinan 250014，China; 2.Information Center，Local Tax Bureau of Shandong Province，Jinan 250014，China)

To solve the unevenness of energy consumption in LEACH，We propose an improved routing protocol to improve the energy efficiency of the wireless sensor networks.In the cluster heads selection stage，this paper introduces residual energy and initial energy of the sensor nodes as two important components to adjusts the values of random numbers.In clustering stage，the algorithm uses the residual energy and the distance between sensor nodes and the Sink node as the basis for clustering to make the distribution of the cluster heads more reasonable.In the stage of data transmission，a route method，which combines single hop route with multi-hop route according to the distance between sensor nodes and the Sink node and the residual energy，is proposed to reduce energy consumption.Simulation results demonstrate that the improved algorithm is more efficient in reducing energy consumption and prolonging the life cycle of wireless sensor networks.

wireless sensor networks;LEACH algorithm;random numbers;residual energy

TP393

A

1004－1699(2014)05－0670－05

10.3969/j.issn.1004－1699.2014.05.019

2014-01-16

2014-04-09