A Inter-Cluster Multi-Hop Routing Protocol Improved Based on LEACH Protocol*

CHEN Bingcai，YAO Huazhuo，YANG Mingchuan，LI Baojun，HE Lingchao

(1.Dalian University of Technology，College of Computer Science and Technology，Dalian Liaoning 116024，China; 2.Harbin Engineering University，College of Information And Communication Engineering，Harbin 150001，China; 3.School of Electronic and Information Engineering HIT，Harbin 150006，China)

A Inter-Cluster Multi-Hop Routing Protocol Improved Based on LEACH Protocol*

CHEN Bingcai1*，YAO Huazhuo2，YANG Mingchuan3，LI Baojun2，HE Lingchao2

(1.Dalian University of Technology，College of Computer Science and Technology，Dalian Liaoning 116024，China; 2.Harbin Engineering University，College of Information And Communication Engineering，Harbin 150001，China; 3.School of Electronic and Information Engineering HIT，Harbin 150006，China)

In order to balance energy consumption of wireless sensor networks，and prolong survival time of the networks，this paper studies several routing protocol based on uniform clustering and non-uniform clustering，and propose an inter-cluster multi-hop routing protocol improved based on LEACH protocol.The protocol introduces energy factor and distance factor to correct threshold function for LEACH protocol.In inter-cluster communication process，cluster head nodes communicate with Sink node by multi-hop，which forms an optimal path leads to Sink node among cluster head nodes.The result of experiment shows that，compared to LEACH protocol and EEUC protocol，the new protocol this paper proposed can balance effectively energy consumption of the networks，and prolong the life of wireless sensor networks.

wireless sensor networks;LEACH protocol;non-uniform clustering;multi-hops

作為新興技術之一，無線傳感器網絡具有廣闊的應用前景，對人們的社會生活產生極大的影響，已經引起世界范圍的廣泛關注［1］。然而，部署在監測區域內的傳感器節點體積小、能量有限且在應用過程中不易更換電池，因此，節能問題一直是無線傳感器網絡的研究熱點。如何均衡網絡能量損耗，最大限度地延長網絡生命周期亦成為無線傳感器網絡路由協議的評價標準。從網絡拓撲結構來看，路由協議可以劃分為平面路由協議和層次路由協議。研究表明，平面路由協議在工作過程中需要維護大量的路由表信息，不太適合大規模無線傳感器網絡，在某種程度上，層次路由協議解決了這個問題。LEACH協議是最具有代表性的一種層次路由協議，目前，許多層次路由協議都是基于LEACH協議的研究和改進，例如，Heinzelman等人在文獻［2］中提出的集中式的簇構造算法LEACH-C以及考慮節點能量的算法LEACH-F［2］。文獻［3］提出一種基于粒子群算法(PSO)的LEACHPSOC路由算法，主要思想是利用粒子群算法良好的收斂性和全局優化能力將整個網絡區域的分割成多個子區域，然后考慮區域內節點剩余能量的因素進而選舉出簇首［3］。文獻［4］提出一種基于LEACH的助理簇頭分簇算法，該算法根據簇頭節點在無線傳感器網絡中所處的地理位置、剩余能量及簇內成員節點數目，動態決定是否需要在簇內產生助理簇頭，這種方法在某種程度上降低了網絡中節點的能量消耗，延長了網絡的生存時間，但其無法彌補單跳通信所造成的能耗不均衡性問題［4］。上述這些協議都是基于均勻分簇的思想來均衡簇內成員節點的能量消耗問題，忽略了簇間的能量消耗均衡性問題。近年來，有許多學者對非均勻分簇路由協議進行了深入研究，文獻［5］中提出一種非均勻分簇的無線傳感器網絡路由協議——EEUC協議，該協議考慮到靠近Sink節點的簇頭由于轉發大量數據而負載過重，從而過早耗盡能量而失效的問題，隨機選取網絡區域內能量較高的節點成為候選簇頭，然后，利用非均勻的競爭范圍來構造大小不等的簇，使靠近Sink節點的簇的規模小于遠離Sink節點的簇，因此，靠近Sink節點的簇頭可以為簇間的數據轉發預留能量，但是，該協議的簇頭選舉過程比較繁瑣，耗能較大［5］。文獻［6］和文獻［7］也提出類似于EEUC的非均勻分簇，但這兩種算法的簇間通信策略仍有很大的改進的空間［6-7］。本文通過對以上幾種協議的優缺點的詳細分析，設計了一種基于LEACH協議改進的簇頭多跳路由協議—CMRAOL (A Cluster Head Multi-hops Rout-ing Algorithm Improved Based on LEACH Algorithm)。

1 LEACH協議

LEACH協議是低功耗自適應聚類路由協議，主要包含以下三部分:動態地選舉簇頭、本地協調產生簇群、數據融合技術。LEACH協議定義了“輪”(Round)的概念，每輪包括兩個階段:簇頭建立階段和數據傳輸階段［8-9］。簇頭建立階段負責簇頭的產生、網絡的分簇管理、簇內節點的組織等。數據傳輸階段負責對數據的傳輸，數據融合等。

LEACH協議選擇簇頭的具體方法如下:在簇頭選擇過程中，對于一個節點來說，為其選取一個在0到1之間的隨機數。如果節點的這個隨機數小于這一輪所設定的門限值T(n)，節點n就充當本輪的簇頭節點。門限值T(n)定義如式(1):

其中，p是節點成為簇頭的期望百分比，r作為當前的輪數，G作為剩1/p輪中未成為簇頭的節點集合，符號mod是求模運算符號。由此可知，當選過簇頭的節點在接下來的(1/p-r)輪中不可能再被選作簇頭，T(n)的值越大，節點當選簇頭的概率越大，隨著輪數的進行，未充當過簇頭的節點被選作簇頭的概率就會越來越大。

當節點被選作簇頭以后，向外發送簇頭廣播信息。非簇頭節點根據收到的簇頭廣播信息的信號大小決定要加入哪個簇，然后向決定要加入的簇的簇頭發送入簇請求。簇頭在收到請求后將該節點加入自己的路由表，并為每個節點設定一個TDMA定時消息，而后通知該簇中所有節點。在數據傳輸過程中，這些節點按照該TDMA時間表進行數據傳輸。每隔一個周期，整個網絡重新進入簇形成階段，開始新一輪的簇頭選舉過程。

2 新協議

LEACH協議是假設所有節點都可以直接與Sink節點通信，采用連續數據發送的模式及單跳路徑選擇的模式，在大范圍監測應用中是不適合的，即使是在小規模網絡中，距離Sink節點遠的節點由于大功率通信，也會導致生存時間比較短;分布在離Sink節點較遠區域的簇頭節點與Sink節點進行通信時，將消耗過多能量，簇頭可能會快速死亡，將影響傳感器網絡的生命周期。另外，協議中簇頭節點的選擇沒有考慮節點的剩余能量和節點到Sink節點的距離等因素，有可能導致某些剩余能量小又距離Sink節點較遠的節點的能量提早的耗盡;網絡的負載平衡度隨之下降。由此，本文提出了基于LEACH協議改進的簇頭多跳路由協議

2.1 網絡模型

所有傳感器節點被隨機部署在一個正方形區域內，對該傳感器網絡假設如下:①網絡中的所有節點都具有位置感知能力;②節點具有唯一的標識ID，并且均勻地分布在監測區域內;③節點位置固定，能量有限，基站位置固定，能量不受限;④節點可以根據距離的遠近來調整發射功率的大小;⑤當傳輸功率已知，節點可根據接收到的信號強度計算兩節點間的距離;⑥每一個節點能與網絡中其他任一個節點通信，也能與Sink節點直接通信。

2.2 成簇過程

與LEACH協議相似，網絡中的所有節點隨機產生一個0～1之間的隨機數，如果這個隨機數小于閾值T(n)，則會被選作簇頭。其中，T(n)的計算方法如式(2):

其中，p為簇頭節點數目占總節點數目的比率，為保證協議性能，我們參照LEACH協議中的最優簇頭數取值，r作為當前的工作輪數，G表示網絡中未成為正式簇頭的節點集合，Wb=，A，B為控制因子;Emax(r)為第r輪全網節點剩余能量的最大值，Ei(r)為第r輪節點的當前剩余能量?？梢钥吹?，在條件相同的情況下，第r輪節點的當前剩余能量越大，閾值T(n)將會增大，該節點當選為簇頭的概率也隨之增大;反之，閾值T(n)將會較小，節點被選作簇頭的概率隨之減小，新協議增大了能量較高的節點被選作簇頭的概率。davg為簇頭節點到Sink節點的平均距離，。di為當前節點到Sink節點的距離。在相同條件時，di的值越大，當前節點距離Sink節點越遠，閾值T(n)將會減小，節點被選作簇頭的概率隨之減小;di的值越小，當前節點距離Sink節點越近，閾值T(n)將會增大，節點被選作簇頭的概率也就隨之增大。這樣，靠近Sink節點的簇頭數會多余遠離Sink節點的簇頭數目，靠近Sink節點的簇的規模也就小于遠離Sink節點的簇的規模，因此，靠近Sink節點的簇頭就可以為簇間的數據轉發預留能量。

2.3 簇間通信

CMRAOL協議采用與LEACH協議相同的一階無線電模型，當發送距離較近時(d≤d0)，采用自由空間信道模型;當發送距離較遠時(d＞d0)，采用多路徑衰減模型［10］。因此，當兩個距離為d的節點之間發送l比特數據時，發送端消耗的能量為:

接收端消耗的能量為:

其中，lEelec指信號處理所需的能量，單位為J/bit，εfs與εmp分別指自由空間模型以及多徑衰落模型下的能量損耗，單位分別為J/(bit·m2)和J/(bit·m4)。本文中，我們取距離閾值d0為87.7 m。

用圖G=(V，E)表示無線傳感器網絡，其中V= {v1，v2，…，vN}表示傳感器節點的集合，則N=|V|表示傳感器節點的個數。對任意兩個傳感器節點vI和vJ，如果vI位于vJ的通信范圍內，并且vJ位于vI的通信范圍內，則稱傳感器節點vI和vJ互為鄰居節點，用坐標(xI，yI)和(xJ，yJ)分別表示傳感器節點vI和vJ的地理位置，用下列式(7)計算傳感器節點vI和vJ之間的距離dI，J:

本文假設每個傳感器節點的通信半徑為R，網絡中只有一個Sink節點。則對任意傳感器節點vI，其鄰居節點集合為:

假設vI選擇vJ作為其數據轉發節點。為了簡化問題分析，假設通信采用自由空間模型，并假設vJ將數據直接傳輸至Sink節點。則為了傳輸l比特的數據至Sink節點，vI和vJ消耗的能量如式(8):

由上式可知，d2(vI，vJ)+d2(vJ，DS)決定了網絡能量消耗的高低。

在CMRAOL協議中，當節點vJ被選作簇頭以后，以較高的發射功率在網絡中廣播包含其ID、節點的剩余能量Ere和到基站的距離dJ的“CH-State”消息。簇頭vI收到來自其他簇頭vJ的“CH-State”消息時，則計算兩簇頭節點間的距離d(vI，vJ)，如果d(vI，vJ)小于傳感器節點的通信半徑R，則把節點vJ的信息保存在鄰居節點集合N(vI)中。如圖所示:表1為簇頭節點vI的鄰居簇頭節點vJ的路由信息表。

表1 鄰居簇頭路由信息表

當傳感器節點vI需要將數據發送或轉發給下一跳簇頭節點時，則下一跳簇頭節點只能從vI的鄰居節點集合N(vI)內選擇。如果d(vI，DS)＞TD_ MAX時(其中，d(vI，DS)為簇頭節點vI到Sink節點的距離，TD_MAX為引入的閾值，設置為87.7 m)，則應該使用多跳路由的方式將數據傳送給Sink節點。即在N(vI)中選擇Wh最大的節點作為下一跳簇頭節點。其中，為N(vI)中被選為中繼節點vJ的剩余能量，d(vI，vJ)為簇頭節點vI與中繼簇頭節點vJ的距離，d(vJ，DS)為中繼節點vJ與Sink節點間的距離，以此類推，當簇頭vJ接收到由簇頭vI發來的數據后，繼續從其鄰居列表中選擇Wh值最大的簇頭節點充當下一跳簇頭節點。由Wh權值計算公式可知:d2(vI，vJ)+d2(vJ，DS)的值越小，Ere的值越大，Wh的值就會越大。即簇頭節點vI在鄰居節點集合N(vI)中搜索距離Sink節點距離小、剩余能量大的鄰居簇頭節點作為下一跳節點。當d(vI，DS)≤TD_MAX或者鄰居節點集合N (vI)為空時，則節點vI直接發送數據到Sink節點。

3 仿真實驗及性能分析

3.1 參數設置

仿真參數如下:400個節點隨機部署在200 m× 200 m的區域中，Sink節點的坐標為(100，250)，LEACH協議和CMRAOL協議的簇頭選擇概率p=0.1，而EEUC協議的候選簇頭選擇概率為p=0.4。節點的初始能量E0=0.5 J，電路能耗Eelec=50 nJ/bit，自由空間信道模型的能耗參數εfs=10pJ/bit/m2，多路衰減信道模型的能耗參數εmp=0.0013 pJ/(bit·m4)，數據融合能耗EDA=5 nJ/bit，控制因子A=0.2，B=0.8，數據包長度l=4 000 bit，控制包長度l1=100 bit［11-13］。

3.2 結果分析

實驗采用MATLAB進行仿真，模擬實現了LEACH協議、EEUC協議和CMRAOL協議的性能比較。圖1給出了LEACH協議、EEUC協議與CMRAOL協議網絡生存周期的比較，以仿真輪數代表時間。LEACH協議、EEUC協議與CMRAOL協議的第1個節點死亡出現的輪數分別為156、164和731，最后一個節點死亡的輪數分別為765、843和951。從圖1可以看出，CMRAOL協議相對于EEUC協議和LEACH協議，第1個節點死亡輪數和最后一個節點死亡輪數都相對延長，明顯提高了網絡生存周期。由于CMRAOL協議采用了優化的簇頭選擇方法和簇間多跳路由機制，有效地平衡了靠近基站的簇和遠離基站的簇之間的數據傳輸能耗。

圖1 網絡生存周期比較

LEACH協議、EEUC協議與CMRAOL協議在相同的環境中進行仿真實驗，Sink節點最終能夠通過傳感器網絡獲取的環境數據多少能夠表現出協議性能的優劣。如圖2所示，從LEACH協議、EEUC協議與CMRAOL協議仿真結果可知，Sink節點接收到的檢測數據包數量分別是:15566、20838和34336。其中CMRAOL協議比LEACH協議高出120.5%，比EEUC協議高出64.7%。這說明CMRAOL協議在相同的檢測環境條件下能夠采集更多的環境數據，網絡的能量利用效率較高。

圖2網絡發送的總數據

圖3 和圖4顯示了3種協議在能量均衡方面的性能［14-15］。

圖3網絡節點剩余能量均值的變化曲線

圖3 中，CMRAOL協議的網絡節點能量均值一直都比LEACH或者EEUC的高，表明CMRAOL協議能夠更有效地節約節點的能量。

圖4網絡節點剩余能量方差的變化曲線

圖4 給出了3種協議能量方差隨時間變化的比較，相對于EEUC協議和LEACH協議，CMRAOL協議的網絡節點能量方差一直很低且變化不大，表明CMRAOL協議能夠有效地均衡網絡節點能量。從圖3和圖4可以看出，CMRAOL協議的能量均衡性能最好。

4 結束語

本文在研究LEACH協議基礎上，對LEACH協議做了兩點改進:①在選擇簇頭節點時，綜合考慮了節點的剩余能量以及節點到Sink節點的距離兩方面因素，使得剩余能量大且距離Sink節點較近的節點容易當選為簇頭節點，這樣有利于均衡整個網絡的能耗。②在簇間通信過程中，對簇頭節點采用了多跳傳輸技術，保證了數據盡快的傳輸到Sink節點，彌補了LEACH協議單跳的不足，從而使網絡壽命得到了相應的延長。

本文分別對“網絡生存時間”、“網絡發送的數據”、“網絡節點剩余能量均值”、“網絡節點剩余能量方差”四項指標進行了仿真分析。仿真結果表明，相比于LEACH協議和EEUC協議，CMRAOL協議能夠提高網絡能量利用效率，有效平衡網絡負載，延長了網絡的生命周期。

［1］馬祖長，孫怡寧，梅濤.無線傳感器網絡綜述［J］.通信學報，2004，25(4):114-124.

［2］Heinzelman W R，Chandrakasan A，balakrishnan H.An Application-Specific Protocol Architecture for Wireless Micro-Sensor Networks［J］.IEEE Transaction on Wireless Communications，2002，1(14):660 -670.

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

［4］龍際珍，陳沅濤，鄧冬梅，等.基于LEACH協議的助理簇頭分簇算法［J］.計算機工程，2011，37(7):103-105.

［5］Li CF，Ye M，Chen GH，et al.An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks［C］//Proc of the IEEE Int’l Conf on Mobile Ad Hoc and Sensor Systems.Washington，2005:597-604.

［6］洪薇，胡健，龔代圣，等.一種基于層次的無線傳感器網絡非均勻分簇路由協議［J］.計算機與現代化，2012:80-84.

［7］薛曉亮.基于LEACH協議的WSN多跳非均勻分簇路由算法研究［D］.華東理工大學信息學院，2010.

［8］孫利民，葉馳，廖勇.傳感器網絡的路由機制［J］.計算機科學，2004，31(1):54-57.

［9］莫宵雁.無線傳感器網絡分簇式路由協議的研究和設計［D］.浙江大學信息學院，2006.

［10］鄭希，基于LEACH的無線傳感器網絡路由協議能耗性能的研究及優化［D］.上海:上海交通大學計算機科學與工程系，2009.

［11］劉鐵流，巫詠群.基于能量優化的無線傳感器網絡分簇路由算法研究［J］.傳感技術學報，2011，24(5):764-770.

［12］李巖，張曦煌，李彥中.基于LEACH協議的簇頭多跳(LEACHM)算法［J］.計算機工程與設計，2007，28(17):4158-4160.

［13］余勇昌，韋崗.無線傳感器網絡中基于PEGASIS協議的改進算法［J］.電子學報，2008，36(7):1309-1313.

［14］劉園莉，李臘元，盧迪.節能的無線傳感器網絡分簇路由協議的研究［J］.傳感技術學報，2010，23(12):1792-1797.

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

陳炳才(1978-)，男，福建漳平人，工學博士，副教授，研究生導師，主要研究方向為無線傳感器網絡、衛星通信網絡，cbc9@qq.com;

么華卓(1987-)，女，黑龍江哈爾濱人，碩士研究生，主要研究方向為無線傳感器網絡路由協議。

一種基于LEACH協議改進的簇間多跳路由協議*

陳炳才1*，么華卓2，楊明川3，李寶君2，赫凌超2
(1.大連理工大學計算機科學與技術學院，大連116024;2.哈爾濱工程大學信息與通信工程學院，哈爾濱150001; 3.哈爾濱工業大學電子與信息工程學院，哈爾濱150006)

為了均衡無線傳感器網絡的能量消耗，延長網絡的生存時間，在研究幾種基于均勻分簇和非均勻分簇的路由協議基礎上，提出一種基于LEACH協議改進的簇間多跳路由協議。該協議引入能量因子和距離因子修正了LEACH協議的閾值函數。在簇間通信過程，簇頭節點與Sink節點之間采用多跳通信方式，簇頭與簇頭之間形成一條通向Sink節點的優化路徑。實驗結果表明，相比于LEACH協議和EEUC協議，本文提出的新協議能夠有效的均衡網絡的能量消耗，延長無線傳感器網絡的壽命。

無線傳感器網絡;LEACH協議;非均勻分簇;多跳

TP393

A

1004－1699(2014)03－0373－05

2013-10-21修改日期:2014-02-28

C:6150P

10.3969/j.issn.1004－1699.2014.03.019

項目來源:國家自然科學基金項目(60902014);國家自然科學基金項目(61101126)