宋倩倩，王宏剛，盧光躍

(西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

基于灰色關(guān)聯(lián)度的Leach算法的改進

宋倩倩，王宏剛，盧光躍

(西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

Leach算法是無線傳感器網(wǎng)絡(luò)中應(yīng)用最為廣泛的分簇路由協(xié)議之一，但是該算法的簇頭是隨機產(chǎn)生的，有可能導(dǎo)致節(jié)點過早死亡，從而使整個網(wǎng)絡(luò)崩潰。針對這一問題，提出一種基于優(yōu)選簇頭的改進Leach算法——gcLeach算法。改進算法引入灰色關(guān)聯(lián)度思想對簇頭進行分區(qū)選舉，兼顧考慮了簇頭的剩余能量以及位置分布，有效地避免了簇頭分布不合理，以及簇頭剩余能量過低導(dǎo)致的節(jié)點過早死亡的情況。仿真結(jié)果表明，改進后的gcLeach算法能夠有效地降低網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)生命周期。

無線傳感器網(wǎng)絡(luò)；Leach算法；灰色關(guān)聯(lián)度；簇頭

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)是由部署在監(jiān)測區(qū)域內(nèi)大量的廉價微型傳感器節(jié)點組成，并通過無線通信方式形成的一個多跳的自組織網(wǎng)絡(luò)系統(tǒng)，其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對象的信息，并發(fā)送給用戶[1]。它在軍事、醫(yī)療、家庭智能和其他社會生活及生產(chǎn)活動領(lǐng)域有著廣泛的應(yīng)用前景。然而無線傳感器網(wǎng)絡(luò)也受到一些限制，其中能量限制是最主要的限制[2]。因為網(wǎng)絡(luò)大多部署在人跡罕至或者環(huán)境惡劣的地方，更換單個節(jié)點的電池是不可取的，也是不現(xiàn)實的，所以如何使網(wǎng)絡(luò)的生命周期最大化是要解決的問題[3]。針對這個問題，目前已有一些研究。文獻[4]提出一個新算法LEACH-NEW，它考慮節(jié)點的能量和位置來獲取能量和定位功能。文獻[5]是在Leach路由算法基于能耗和應(yīng)用規(guī)模的不足之處，引入“層”的概念，并建立新的簇頭選擇機制來改進原來的Leach。文獻[6]是根據(jù)接收和發(fā)送作者參考的一種機制，動態(tài)地開啟或關(guān)閉不同的組件，調(diào)整傳送傳感器節(jié)點的功率和調(diào)制電平，同時保持所需的性能，通過引入動態(tài)電源管理(DPM)技術(shù)，修改和為一個平均獲取馬爾可夫決策過程(AR-MDP)建模，最后結(jié)合模擬退火算法(SA)、Q學(xué)習(xí)算法來解決與平均績效標(biāo)準的節(jié)能優(yōu)化問題。文獻[7]是基于傳感器通道節(jié)點因素的地理位置，剩余能量和鄰居的數(shù)目提出一個簇路由算法，并通過管理傳感器節(jié)點和簇來降低無線傳感器網(wǎng)絡(luò)中的能量消耗，增加無線傳感器網(wǎng)絡(luò)的壽命。文獻[8]提出了一種改進的Leach協(xié)議(Leach-C)算法，稱為基于分區(qū)的Leach(pLeach)，首先使用集中式計算將網(wǎng)絡(luò)劃分為最佳數(shù)量的扇區(qū)，然后選擇具有最高能量的節(jié)點為每個扇區(qū)的頭。文獻[9]基于能量的限制，設(shè)計了一個雙簇頭的非均勻分簇路由協(xié)議來降低能源消耗。文獻[10]根據(jù)簇頭預(yù)期的頻率評估的理念，提出了改進的LEACH-HEFA(LEACH主管預(yù)期頻率評估)算法，可以平衡無線傳感器網(wǎng)絡(luò)節(jié)點的能量消耗，理順聚類過程，有效地延長網(wǎng)絡(luò)的壽命，該算法適用于水情監(jiān)測系統(tǒng)。文獻[11]使用OPNET構(gòu)造仿真模型和性能進行對比研究，改進后的路由算法I-Leach(改進-Leach)比原來的Leach算法擴展了網(wǎng)絡(luò)的生命周期，從而降低了整個系統(tǒng)的能耗，提高了網(wǎng)絡(luò)的可擴展性。

1 Leach算法

Leach算法是由Wendi Rabiner等人提出的以“輪”來實現(xiàn)的低功耗自適應(yīng)集簇分層型協(xié)議。該算法的基本思想是：以循環(huán)的方式隨機選擇簇頭節(jié)點，從而達到能量均衡以降低網(wǎng)絡(luò)能源消耗、提高生命周期的目的。在Leach每一輪被分為簇的建立階段和穩(wěn)定數(shù)據(jù)傳輸階段，為了節(jié)省能源，穩(wěn)定階段的持續(xù)時間要長于建立階段。

Leach算法的工作流程如圖1所示。

圖1 Leach算法工作流程圖

在簇建立階段，傳感器節(jié)點從0到1隨機選擇一個數(shù)值，并與設(shè)定的閾值T(n)相比較，若當(dāng)前輪中該值小于T(n)，則該節(jié)點成為簇頭，反之則為非簇頭節(jié)點。每一輪循環(huán)中，若節(jié)點已被選為簇頭，則T(n)設(shè)置為零，來避免此節(jié)點再次當(dāng)選為簇頭，閾值T(n)定義為

(1)

在數(shù)據(jù)穩(wěn)定傳輸階段，節(jié)點將采集到的數(shù)據(jù)發(fā)送到簇頭，簇頭對數(shù)據(jù)進行融合后再將信息發(fā)送到匯聚節(jié)點，匯聚節(jié)點將數(shù)據(jù)發(fā)送給監(jiān)控中心來進行數(shù)據(jù)處理。數(shù)據(jù)穩(wěn)定傳輸階段持續(xù)一定的時間之后，網(wǎng)絡(luò)將重新進入簇的建立階段，開始下一輪的簇重建，不斷地周期循環(huán)。

2 改進的Leach算法gcLeach

與靜態(tài)分層算法和平面多跳路由協(xié)議相比，Leach算法可以將網(wǎng)絡(luò)的生命周期延長15%，但是簇頭選舉的過程中Leach算法仍然存在著不足。本文著重在簇頭選舉上進行改進。

2.1 傳感器節(jié)點分區(qū)算法研究

由于Leach算法是隨機的選舉簇頭，可能使簇頭集中分布不合理，從而使能量分布不均衡。本文首先按照網(wǎng)絡(luò)的大小、節(jié)點的傳輸范圍和節(jié)點的分布密度把網(wǎng)絡(luò)分為6個區(qū)域，在分區(qū)的基礎(chǔ)上固定每個區(qū)域內(nèi)的簇頭比例，其中區(qū)域1由于包括基站位置，設(shè)定不需要簇頭，區(qū)域2固定一個簇頭，其他區(qū)域的簇頭比例按照以下步驟：

2)統(tǒng)計出該區(qū)域中的節(jié)點數(shù)目Qnum。

根據(jù)以上步驟計算得到的每個區(qū)域的簇首比例為：區(qū)域1為0；區(qū)域2為0(固定1個簇頭)；區(qū)域3為0.065574；區(qū)域4為0.069 307；區(qū)域5為0.081 818；區(qū)域6為0.066667，如圖2所示。

圖2 網(wǎng)絡(luò)區(qū)域劃分和簇頭比例圖

由于采用區(qū)域進行處理，最近的兩個區(qū)域由于離基站較近，因此簇頭數(shù)目得到嚴格控制，避免了不合理的簇頭分布。

2.2 基于灰色關(guān)聯(lián)度思想的簇頭選舉算法研究

對網(wǎng)絡(luò)規(guī)劃分區(qū)后，使網(wǎng)絡(luò)中的簇頭能夠分布均勻合理，但是沒有考慮到節(jié)點與基站的距離以及自身的剩余能量，這樣就有可能使剩余能量少或者距離基站距離較遠的節(jié)點當(dāng)選為簇頭,從而造成網(wǎng)絡(luò)生命周期減少或者能耗較大。因此，本文又在分區(qū)的基礎(chǔ)上引入灰色關(guān)聯(lián)度的思想，根據(jù)節(jié)點剩余能量、通信距離等因素采用灰色關(guān)聯(lián)度分析法推選簇頭序列，形成無線網(wǎng)絡(luò)的層次結(jié)構(gòu)。選舉簇頭節(jié)點時考慮節(jié)點剩余能力、通信距離等因素，克服Leach協(xié)議中簇頭選舉的隨機性、節(jié)點能耗分布不平均等缺點，同時減少網(wǎng)絡(luò)在不斷選舉簇頭時的能量消耗，延長無線傳感器網(wǎng)絡(luò)的生命周期。

灰色系統(tǒng)理論是由鄧聚龍首創(chuàng)的一種系統(tǒng)科學(xué)理論，其中的灰色關(guān)聯(lián)度分析[12]是根據(jù)各個因素之間發(fā)展趨勢的相似或相異程度來作為衡量因素之間的關(guān)聯(lián)程度的方法。

1)確定最優(yōu)指標(biāo)集F

(2)

式中：jk為第k個指標(biāo)的最優(yōu)值。此最優(yōu)值是在方案中最優(yōu)的值(若某一指標(biāo)取大值為好,則取該指標(biāo)在各個方案中的最大值;若取小值為好, 則取各個方案中的最小值),也可以是評估者普遍認為的最優(yōu)值。不過在定最優(yōu)值時,不僅要考慮到先進性,還要考慮到可行性。若最優(yōu)值標(biāo)志得過高,則不現(xiàn)實,不能實現(xiàn),評價的結(jié)果也就不可能準確。

選定最優(yōu)指標(biāo)集后,構(gòu)造矩陣

(3)

式中：dn和En分別表示節(jié)點到基站的距離和剩余能量的原始數(shù)值。

2)指標(biāo)值的規(guī)范化處理

由于指標(biāo)間通常是有不同的量綱和數(shù)量級,所以不能直接進行比較,為了保證結(jié)果的可靠性,因此要對原始的數(shù)值進行規(guī)范化處理。本文采用式(4)將式(3)中的原始數(shù)值變換成無量綱的值，Ci是轉(zhuǎn)化后的無量綱值

(4)

這樣D→C矩陣為

(5)

3)計算綜合評判結(jié)果

(6)

(7)

(8)

式中：R為M個被評價對象的綜合評價結(jié)果向量；W為N個評價指標(biāo)的權(quán)重向量；E為各指標(biāo)的評價矩陣。

(9)

3 算法仿真與分析

3.1 仿真場景

本文是在MATLAB環(huán)境下進行的仿真，仿真實現(xiàn)了Leach算法和改進的gcLeach算法，并對兩種算法的性能指標(biāo)進行了比較。仿真場景的參數(shù)設(shè)置如表1所示。

表1 場景參數(shù)

3.2 仿真結(jié)果分析

仿真主要是從網(wǎng)絡(luò)生存周期和節(jié)點的剩余能量兩個性能指標(biāo)進行比較。

圖3是Leach算法和改進后的gcLeach算法的生存周期的比較，從圖中可以看出，gcLeach算法的性能明顯要優(yōu)于Leach算法，生命周期要比Leach算法延長2.8倍左右。形成這個結(jié)果的原因有：

1)劃分區(qū)域使節(jié)點分布均勻，在每一輪中使gcLeach算法選擇最佳比例的節(jié)點作為簇頭。在選舉過程中保證了簇頭的最佳數(shù)目。

2)固定簇頭比例后，在簇頭選舉中，gcLeach算法又選擇較高的剩余能量和距離基站較近的節(jié)點作為簇頭。這保證了簇頭節(jié)點的能量和傳輸距離。

圖3 網(wǎng)絡(luò)生存周期比較圖

圖4 節(jié)點剩余總能量比較圖

圖4所示為Leach算法和gcLeach算法的能量消耗比較圖。通過上述的優(yōu)選簇頭選舉的機制，同時使網(wǎng)絡(luò)的能量分布和負載均衡，達到總能量消耗最優(yōu)化管理。從圖中可以看出，gcLeach算法的能量消耗要低于Leach算法。

4 結(jié)論

Leach算法是在WSN中應(yīng)用比較廣泛的一種分簇路由算法，本文在Leach算法的基礎(chǔ)上，從簇頭選舉的方法上做了改進，提出了一種改進的gcLeach算法。從仿真結(jié)果可以看出，改進后的算法可以顯著提高網(wǎng)絡(luò)的能源利用率，延長網(wǎng)絡(luò)的生命周期。

[1]HEINZELMANWR，CHANDRAKASANA，BALAKRISHNANH.Energy-efficientcommunicationprotocolforwirelessmicrosensornetworks[C]∥Proc.33rdHawaiiInternationalConferenceonSystemSciences.LosAlamitos：IEEEPress，2000：3005-3014.

[2]WANGH，AGOULMINEN，MAM，etal.Networklifetimeoptimizationinwirelesssensornetworks[J].IEEEJournalonSelectedAreasinCommunication，2010，9(28)：1127-1137.

[3]孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[4]SHUJIANGLD，LIXINKK.Improvementandsimulationofclusteringroutingalgorithminwirelesssensornetwork[C]//Proc.2011 6thIEEEConferenceonIndustrialElectronicsandApplications(ICIEA).Beijing：IEEEPress，2011：1068-1073.

[5]JINKY，ZHANGY，TIANDR.BasedontheimprovementofLEACHprotocolforwirelesssensornetworkroutingalgorithm[C]//Proc.2012SecondInternationalConferenceonIntelligentSystemDesignandEngineeringApplication(ISDEA).Sanya：IEEEPress，2012：1525-1528.

[6]MAOS，TANGH，ZHOUL，etal.AnenergyconservationoptimizationstrategyforwirelesssensornetworknodebasedonQ-learning[C]//Proc.2011 8thAsianControlConference(ASCC).Kaohsiung：IEEEPress，2011：938-943.

[7]BEIRANVANDZ，PATOOGHYA，F(xiàn)AZELIM.I-LEACH:anefficientroutingalgorithmtoimproveperformance&toreduceenergyconsumptioninwirelesssensornetworks[C]//Proc.20135thConferenceonInformationandKnowledgeTechnology(IKT).Shiraz：IEEEPress，2013：13-18.

[8]HAOSONGG，YOUNGHWANY.AnenergybalancingLEACHalgorithmforwirelesssensornetworks[C]//Proc.2010SeventhInternationalConferenceonInformationTechnology:NewGenerations(ITNG).LasVegas：IEEEPress，2010：822-827.

[9]LIUZJ，LILY.BasedonenergybalanceLEACH-DCprotocoldesign[C]//Proc.2011 6thIEEEJointInternationalInformationTechnologyandArtificialIntelligenceConference(ITAIC).Chongqing：IEEEPress，2011:291-294.

[10]LICM，TANGP，WUJY，etal.Analyzingcluster-headselectionmechanismsandimprovingtheLEACH[C]//Proc.2011InternationalConferenceonElectronics，CommunicationsandControl(ICECC).Zhejiang：IEEEPress，2011：747-750.[11]SONGXY.ModelingandsimulationofWSNroutingprotocols[C]//Proc.2011IEEE3rdInternationalConferenceonCommunicationSoftwareandNetworks(ICCSN).Xi'an：IEEEPress，2011：586-590.

[12]ZHAOGS，WANGHQ，WANGJ.Anovelquantitativeanalysismethodfornetworksurvivability[C]//Proc.FirstInternationalMulti-SymposiumsonComputerandComputationalSciences.Hangzhou：IEEEPress，2006：30-33.

[13]ZHANGWY，LIANGZZ，HOUZG，etal.Apowerefficientroutingprotocolforwirelesssensornetwork[C]//Proc.Networking,SensingandControl,IEEEInternationalConference.London：IEEEPress，2007：20-25.

宋倩倩(1987— )，碩士生，主研寬帶無線通信技術(shù)。

王宏剛(1977— )，講師，主要研究方向為無線通信、射頻識別、無線傳感器網(wǎng)絡(luò)等。

盧光躍(1971— )，碩士生導(dǎo)師，主要研究方向為通信信號處理等。

責(zé)任編輯：許 盈

Improved Leach Algorithms Based on Gray Correlation Degree

SONG Qianqian,WANG Honggang,LU Guangyue

(SchoolofCommunicationandInformationEngineering,Xi’anUniversityofPostsandTelecommunication,Xi’an710121,China)

Leach algorithms is one of the most used widely clustering routing protocol in wireless sensor networks, but the cluster head of Leach algorithm is randomly generated, it may lead nodes to premature deaths and then collapse of the entire network.To solve this problem, an improved algorithm is proposed based on Leach--gcLeach algorithm based on optimal cluster head.Improved algorithm for the introduction of gray correlation degree to partition the cluster head election, both considering the remaining energy of the cluster heads and the location of the distribution, effectively, avoid the situation of the irrational distribution of cluster head,as well as the low remaining energy of cluster head leads nodes to premature death.Simulation results show that, improved gcLeach algorithm can effectively reduce energy consumption, and prolong the network lifetime.

wireless sensor networks; Leach algorithm; gray correlation degree; cluster head

【本文獻信息】宋倩倩，王宏剛，盧光躍.基于灰色關(guān)聯(lián)度的Leach算法的改進[J].電視技術(shù),2015，39(3).

陜西省科學(xué)技術(shù)研究發(fā)展計劃項目(2013KW01-03)

TN929

A

10.16280/j.videoe.2015.03.036

2014-06-10