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

宋倩倩，王宏剛，盧光躍

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

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

宋倩倩，王宏剛，盧光躍

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

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

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

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

1 Leach算法

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

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

圖1 Leach算法工作流程圖

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

(1)

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

2 改進(jìn)的Leach算法gcLeach

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

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

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

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

根據(jù)以上步驟計(jì)算得到的每個(gè)區(qū)域的簇首比例為：區(qū)域1為0；區(qū)域2為0(固定1個(gè)簇頭)；區(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ū)域進(jìn)行處理，最近的兩個(gè)區(qū)域由于離基站較近，因此簇頭數(shù)目得到嚴(yán)格控制，避免了不合理的簇頭分布。

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

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

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

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

(2)

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

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

(3)

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

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

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

(4)

這樣D→C矩陣為

(5)

3)計(jì)算綜合評(píng)判結(jié)果

(6)

(7)

(8)

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

(9)

3 算法仿真與分析

3.1 仿真場(chǎng)景

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

表1 場(chǎng)景參數(shù)

3.2 仿真結(jié)果分析

仿真主要是從網(wǎng)絡(luò)生存周期和節(jié)點(diǎn)的剩余能量?jī)蓚€(gè)性能指標(biāo)進(jìn)行比較。

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

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

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

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

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

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

4 結(jié)論

Leach算法是在WSN中應(yīng)用比較廣泛的一種分簇路由算法，本文在Leach算法的基礎(chǔ)上，從簇頭選舉的方法上做了改進(jìn)，提出了一種改進(jìn)的gcLeach算法。從仿真結(jié)果可以看出，改進(jìn)后的算法可以顯著提高網(wǎng)絡(luò)的能源利用率，延長(zhǎng)網(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ú)線傳感器網(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— )，碩士生，主研寬帶無(wú)線通信技術(shù)。

王宏剛(1977— )，講師，主要研究方向?yàn)闊o(wú)線通信、射頻識(shí)別、無(wú)線傳感器網(wǎng)絡(luò)等。

盧光躍(1971— )，碩士生導(dǎo)師，主要研究方向?yàn)橥ㄐ判盘?hà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

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

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

TN929

A

10.16280/j.videoe.2015.03.036

2014-06-10