王春梅

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

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

關鍵詞：無線傳感器網(wǎng)絡；分簇協(xié)議；能量有效；網(wǎng)絡壽命

doi:10.3969/j.issn.1002-0802.2015.06.016

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

王春梅

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

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

關鍵詞：無線傳感器網(wǎng)絡；分簇協(xié)議；能量有效；網(wǎng)絡壽命

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引言

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

1IEECH協(xié)議

1.1網(wǎng)絡模型

對網(wǎng)絡模型進行較通用的假設：

(1)基站位于正方形監(jiān)測區(qū)域外部;

(2)每個傳感器節(jié)點都有全網(wǎng)內(nèi)唯一的id標志;

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

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

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

1.2能量模型

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

(1)

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

1.3IEECH協(xié)議細節(jié)

IEECH協(xié)議是一個優(yōu)化的集中式分簇算法，分簇過程被劃分為兩個部分：成簇階段和發(fā)送節(jié)點的循環(huán)階段。

(1)成簇階段

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

1)劃分簇階段

每個傳感器節(jié)點在本階段會將位置和能量信息發(fā)送到基站?；臼盏剿泄?jié)點的數(shù)據(jù)信息后，分簇過程如下：

①由基站計算網(wǎng)絡中所有節(jié)點的平均剩余能量Eave和最佳的簇頭數(shù)目Kopt。

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

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

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

此階段結束后，網(wǎng)絡中會存在兩類節(jié)點：簇頭和簇成員節(jié)點。在下一階段，將會通過一定的規(guī)則選出每個簇中的發(fā)送節(jié)點。

2)發(fā)送節(jié)點的選擇階段

在本階段，每個簇頭都負責從本簇內(nèi)選出一個節(jié)點來充當本輪的發(fā)送節(jié)點。選擇過程如下。

算法2:發(fā)送節(jié)點的選擇及成員節(jié)點調(diào)度算法：

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

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

③簇頭將第②步選出的候選發(fā)送節(jié)點按照節(jié)點和自己的距離對其按照非遞減方式排序，并從這些節(jié)點中選出距離簇頭最近的節(jié)點充當發(fā)送節(jié)點。其余候選節(jié)點重新變?yōu)槠胀ǔ蓡T節(jié)點。

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

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

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

(2)

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

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

Ej-cur≥Ei-ave,j∈SSi

(3)

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

本階段結束時，網(wǎng)絡中存在3種節(jié)點：簇頭節(jié)點，發(fā)送節(jié)點和普通成員節(jié)點。

簇頭節(jié)點：負責本簇內(nèi)發(fā)送節(jié)點的選擇以及調(diào)度簇內(nèi)普通成員節(jié)點的發(fā)送時隙。

發(fā)送節(jié)點：負責收集成員節(jié)點發(fā)送的數(shù)據(jù)，并將其經(jīng)過融合處理后發(fā)送到基站。

普通成員節(jié)點：負責感知收集數(shù)據(jù)，并將數(shù)據(jù)按照調(diào)度時隙發(fā)送給發(fā)送節(jié)點。

(2)循環(huán)階段

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

2IEECH協(xié)議分析

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

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

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

3IEECH協(xié)議仿真

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

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

(2)數(shù)據(jù)量：此指標是指監(jiān)測網(wǎng)絡中能夠成功傳送到基站的數(shù)據(jù)量的多少。

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

圖1　仿真場景

具體仿真參數(shù)設置如表1所示。

表1　仿真參數(shù)設置

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

圖2　網(wǎng)絡壽命

圖3　數(shù)據(jù)傳輸量的對比

4結語

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

參考文獻：

[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的無線傳感器網(wǎng)絡距離修正定位算法[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—)，女，碩士，講師，主要研究方向為互聯(lián)網(wǎng)技術。