一種基于LEACH-C改進的能量有效分簇協議

王春梅

(濱州學院 信息工程系,山東 濱州 256603)

摘　要：針對LEACH-C協議周期性地簇重構會造成額外開銷以及簇頭節點和普通節點間能耗不均的缺陷，提出了改進的能量有效分簇協議(Improved Energy-Efficient Clustering Hierarchy,IEECH)。在IEECH中，由簇中所選出的發送節點分擔簇頭節點的高能量負載，因此不再需要進行全局的簇重構。網絡節點的能耗由于發送節點的輪轉進一步得到了均衡。因此，該算法和LEACH以及LEACH-C相比，可以有效地延長網絡的壽命。最后，通過NS2仿真實驗也得到了驗證。

關鍵詞：無線傳感器網絡；分簇協議；能量有效；網絡壽命

doi:10.3969/j.issn.1002-0802.2015.06.016

一種基于LEACH-C改進的能量有效分簇協議

王春梅

(濱州學院 信息工程系,山東 濱州 256603)

摘要：針對LEACH-C協議周期性地簇重構會造成額外開銷以及簇頭節點和普通節點間能耗不均的缺陷，提出了改進的能量有效分簇協議(Improved Energy-Efficient Clustering Hierarchy,IEECH)。在IEECH中，由簇中所選出的發送節點分擔簇頭節點的高能量負載，因此不再需要進行全局的簇重構。網絡節點的能耗由于發送節點的輪轉進一步得到了均衡。因此，該算法和LEACH以及LEACH-C相比，可以有效地延長網絡的壽命。最后，通過NS2仿真實驗也得到了驗證。

關鍵詞：無線傳感器網絡；分簇協議；能量有效；網絡壽命

doi:10.3969/j.issn.1002-0802.2015.06.016

收稿日期：2015-01-01；修回日期：2015-04-01Received date:2015-01-01；Revised date：2015-04-01

基金項目：山東省自然科學基金(No.2014ZRB019)Foundation Item:Research on the Fractional Chaos Characteristics and Synchronization(No.2014ZRB019)

中圖分類號：TP393

文獻標志碼：碼：A

文章編號：號：1002-0802(2015)06-0710-04

Abstract：Aiming at LEACH-C for its extra overhead in cluster reconstruction and imbalanced energy consumption between cluster heads and common nodes, IEECH (Improved Energy-Efficient Clustering Hierarchy Protocol) is proposed. In this protocol the sending nodes selected from clusters share the high load of cluster heads, thus it is unnecessary for these nodes to implement the re-clustering of global network. The energy consumption of each cluster member can be balanced via rotation of sending nodes. Therefore, IEECH can prolong the network life-time significantly as compared with LEACH and LEACH-C. Finally, NS2 simulation indicates this result.

作者簡介：

An Energy-Efficient Clustering Protocol based on LEACH-C

WANG Chun-mei

(Information Engineering Department, Binzhou University, Binzhou Shandong 256603, China)

Key words：wireless sensor networks; clustering protocol; energy effectiveness; WSN lifetime

0引言

路由協議是無線傳感器網絡(WSN)的關鍵技術之一[1-2]。目前，無線傳感器網絡中主導的路由協議是低功耗自適應分簇協議(Low Energy Adaptive Clustering Hierarchy,LEACH)為代表的層次化路由[3-4]。LEACH-C協議由Heinzelman等人在LEACH協議的基礎上加以改進提出的基于基站控制的協議[1]。但是該算法需要構造一個組織數據發送的環結構，提高了算法的復雜度。針對LEACH-C協議的缺陷，本文提出了改進的能量有效分簇協議 (the Improved Energy-Efficient Clustering Hierarchy,IEECH)，主要目標是網絡系統的能量消耗被大大降低，網絡的生命周期有效地延長，并對該方案進行了理論分析和實驗仿真，仿真結果也驗證了該協議的有效性。

1IEECH協議

1.1網絡模型

對網絡模型進行較通用的假設：

(1)基站位于正方形監測區域外部;

(2)每個傳感器節點都有全網內唯一的id標志;

(3)每個傳感器節點的發射功率可控，其可以將數據發送給任意其他節點或者可以直接發送到基站;

(4)節點一旦部署不再移動;

(5)傳感器節點可感知其位置，即為每個節點配備GPS等定位系統。

1.2能量模型

采用的能量模型同LEACH[5-6]。若傳輸l-bit的信息經過距離d，此時發送端的能量消耗為：

(1)

式中，Eelec表示的是發射電路所要消耗的能量。如果數據的傳輸距離小于閾值d0，那么功率放大消耗就采用自由空間模型；但當數據的傳輸距離大于等于閾值d0時，就應采用多路徑衰減模型。εfs、εmp分別是這兩種模型中放大功率所需的能量。同時，假設傳感器節點進行監測的能耗為：Esen，簇頭融合數據的能耗為：Ecom,Eelec表示的是發射電路所要消耗的能量。

1.3IEECH協議細節

IEECH協議是一個優化的集中式分簇算法，分簇過程被劃分為兩個部分：成簇階段和發送節點的循環階段。

(1)成簇階段

該成簇過程包括兩個部分：劃分簇階段和發送節點的選擇階段。

1)劃分簇階段

每個傳感器節點在本階段會將位置和能量信息發送到基站。基站收到所有節點的數據信息后，分簇過程如下：

①由基站計算網絡中所有節點的平均剩余能量Eave和最佳的簇頭數目Kopt。

②若節點的剩余能量≥平均剩余能量Eave，則該節點被選擇為簇頭節點，否則節點則為非簇頭節點。

③基站對選出的簇頭集合能量和執行模擬退火算法[7]，對網絡進行分簇。

④簇頭找出后，基站將選出的簇頭和簇成員節點的信息向網絡中所有節點廣播，根據此廣播信息，每個節點確定自己的角色，每個簇由被選出來的簇頭來管理。

此階段結束后，網絡中會存在兩類節點：簇頭和簇成員節點。在下一階段，將會通過一定的規則選出每個簇中的發送節點。

2)發送節點的選擇階段

在本階段，每個簇頭都負責從本簇內選出一個節點來充當本輪的發送節點。選擇過程如下。

算法2:發送節點的選擇及成員節點調度算法：

①每個簇頭統計成員節點的信息，按照式(1)計算出本簇中所有成員節點的平均剩余能量。

②簇頭負責從這些節點中選出所有剩余能量高于此平均剩余能量的節點，作為候選發送節點。

③簇頭將第②步選出的候選發送節點按照節點和自己的距離對其按照非遞減方式排序，并從這些節點中選出距離簇頭最近的節點充當發送節點。其余候選節點重新變為普通成員節點。

④簇頭為簇內成員節點計算出TDMA調度表，調度原則是：剩余能量越低的節點發送數據的時隙安排地越靠前，因而可以避免能量較低的節點在等待時隙到來的過程中又耗費掉一部分能量。

簇頭將當選的發送節點的id標識和生成的成員節點調度表在簇范圍內進行廣播，成員節點在收到此消息后確定本簇內發送節點的位置，并只在自己所屬的發送時隙內將收集的數據傳送至發送節點，發送節點將收到的數據進行融合處理，然后傳送至基站。

為了選出發送節點，每個簇頭需要計算每個節點會被當選的能量閾值，即所有成員節點的平均剩余能量。計算公式如下：

(2)

式中，n是簇i內的成員節點數目。Ej-cur是指節點j當前剩余能量。高于此平均能量且距離簇頭最近的節點更容易被選為發送節點。

如果節點j的當前剩余能量Ej-cur是不小于簇內節點平均能量Ei-ave的，則節點j被選入候選發送節點集合SSi：

Ej-cur≥Ei-ave,j∈SSi

(3)

集合SSi確定后，簇頭節點就根據自己和節點的距離，從該集合中選出本簇內這一輪的發送節點，即平均剩余能量較多，且距離簇頭的距離越小的節點被選為發送節點的概率越大。

本階段結束時，網絡中存在3種節點：簇頭節點，發送節點和普通成員節點。

簇頭節點：負責本簇內發送節點的選擇以及調度簇內普通成員節點的發送時隙。

發送節點：負責收集成員節點發送的數據，并將其經過融合處理后發送到基站。

普通成員節點：負責感知收集數據，并將數據按照調度時隙發送給發送節點。

(2)循環階段

在本階段，簇頭根據掌握的成員節點信息創建TDMA調度表，為每個成員節點分配一個發送時隙，節點只在這個時隙內發送數據，其余時間就可以進入休眠狀態，由此來節省能量。簇頭將此調度表和本輪選出的發送節點的id標識和地理位置信息一起廣播發送給成員節點。成員節點確定本簇內的發送節點，并在自己的發送時隙內將數據傳送至發送節點，由發送節點發送至基站。為了均衡發送節點和成員節點間的能耗，每個成員節點輪流擔任發送節點。即一輪完成以后，簇頭會按照發送節點的選擇規則從成員節點中選出下一輪要擔任發送節點的節點，此時前一輪的發送節點又重新變成了普通成員節點。簇頭將本輪重新建立的TDMA調度表和本輪選出的發送節點的相關信息廣播發送給簇內成員節點，由此開始下一輪的數據傳輸。發送節點在簇內輪轉可以有效均衡簇內節點間的能耗。

2IEECH協議分析

(1)IEECH協議不再在網絡全局內頻繁的簇重構，避免了簇重構帶來的大量額外開銷。

(2)IEECH協議在成簇階段按照一定規則生成了最優的簇頭數目和分簇拓撲，在之后的過程中，維持這個最優的拓撲，由簇頭在本簇中選出本輪中用來融合和發送數據的發送節點，從而分擔簇頭的能耗，使簇頭能量緩慢消耗。由于發送節點的負擔仍然較重，因此算法只是在每個局部簇中進行發送節點的輪轉來均衡簇中每個成員節點的能耗，充分利用每個節點的能量，避免浪費。

(3)在簇頭生成TDMA調度時，同樣考慮了節點的剩余能量，使能量較少的節點發送數據的時隙排在調度表的前面，避免節點在等待過程中能量的進一步消耗。因為盡管在這個等待過程中節點是處于休眠狀態，但是仍然會有能量消耗。

3IEECH協議仿真

通過仿真實驗對LEACH，LEACH-C和IEECH的算法性能進行對比分析。要比較的性能指標有：

(1)網絡壽命：此指標是指隨著算法的運行時間網絡中存活節點的數目變化。

(2)數據量：此指標是指監測網絡中能夠成功傳送到基站的數據量的多少。

設置了如下仿真場景對IEECH進行仿真實驗：將100個節點隨機地分布在100 m×100 m的矩形區域內?；疚挥诰匦螀^域外，將其坐標設置為(50,175)。仿真場景圖如圖1所示。

圖1　仿真場景

具體仿真參數設置如表1所示。

表1　仿真參數設置

使用所設置的參數，在上面的仿真場景下分別運行LEACH，LEACH-C和IEECH。圖2顯示了對3種協議的網絡壽命的仿真比較。如圖2所示，作為LEACH的改進協議，運行LEACH-C協議的網絡中第一個節點死亡的時間是遠遠緩慢于LEACH協議的。因為在LEACH中，簇頭是隨機選取的，而在LEACH-C中簇頭是事先計算好的最優簇頭分布，網絡中的節點的能量的消耗比LEACH中要均衡地多，因此可以獲得較長的網絡壽命。在提出的IEECH協議中，算法除了具備LEACH-C協議的優點外，即在全網范圍內計算出最優的簇頭分布，針對LEACH-C協議的每個簇內簇頭負擔過重會過早死亡和需要在全網內進行帶來額外開銷的簇重構過程，IEECH協議為每個簇挑選了專門用來收集，匯聚和發送數據的發送節點，可以大量分擔簇頭的能耗，并且為了均衡簇內每個節點的能耗，在每個簇中輪轉發送節點的角色，而不需要在全網內進行簇重構。因此，運行IEECH的網絡中第一個節點死亡的時間是長于LEACH和LEACH-C的，并且IEECH網絡中第一個節點死亡之后，網絡很快就死亡了，即絕大多數節點的能量都得到了充分的利用。為了進一步體現IEECH協議性能的優越性，提取的三種協議中網絡中數據傳輸量，結果對比如圖3所示。在運行時間內，LEACH-C及IEECH發送的數據包比LEACH多，并且在LEACH所有節點全部死亡后，LEACH-C和IEEC仍有發包成功，也就是說，在相同的環境下，LEACH-C和IEECH采集和傳輸的數據包更多，并且網絡中傳輸的數據量更加穩定。

圖2　網絡壽命

圖3　數據傳輸量的對比

4結語

提出了一種能量有效的分簇協議，簇頭節點的高能量負載被每個簇中選出的發送節點所分擔。簇頭節點和發送節點的選擇分別基于網絡中節點的平均剩余能量和每個簇中成員節點的平均能量以及相對距離。由于簇頭的能量負載被大大降低，因此不需要進行全局的簇重構，避免了大量能量的額外開銷。并且發送節點在簇內的輪轉又進一步均衡了每個節點的能耗。因此，算法既可以均衡簇頭和普通節點的能耗，又可避免全局簇重構帶來的巨大額外開銷。理論與仿真實驗證明，和LEACH以及LEACH-C相比，IEECH可以延長網絡的壽命。

參考文獻：

[1]Heinzelman W R. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Trans, on Wireless Communications, 2002, 1(4): 660-670.

[2]陳昌祥，達維，周潔. 基于RSSI的無線傳感器網絡距離修正定位算法[J]. 通信技術, 2011, 44(02): 65-69.

CHEN Chang-xiang, DA Wei, ZHOU Jie. RSSI-based Range Collation Localization Algorithm in WSN[J]. Communications Technology, 2011, 44(02): 65-69.

[3]Soro S, Heinzelman W. Prolonging the Lifetime of Wireless Sensor Networks via Unequal Clustering[C]. In Proceeding of the 19th IEEE International Parallel and Distributed Processing Symposium, Colorado, USA, 2013(13): 236-243.

[4]Muruganathan S D, Ma DCF, Bhasin PI,et al. A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks[J], IEEE Communications Magazine, 2005, 43 (3): 8-13.

[5]Heinzelman W R, Chandrakasan A, Balkarishnan H. Energy-Efficient Communication Protocol for Wireless Sensor Networks[C]. Proeeedings of the 33rd Annual Hawaii International Conference on System Sciences, Hawaii, USA, 2000:1-10.

[6]Fuad Bajaber. Irfan Awan. EECPL: Energy Effcient Clustering Protocol to Enhance Lifetime of Wireless Sensor Network[J]. J Ambient Intell Human Comput, 2010(1): 239-248.

[7]Kirkpatrick S, Gelati C, Vecchi M. Simulated Annealing. Science, 1983, 220: 671-680.

王春梅(1982—)，女，碩士，講師，主要研究方向為互聯網技術。