基于遺傳算法的lech協(xié)議能量?jī)?yōu)化路由算法

由于無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)是隨機(jī)分布的，節(jié)點(diǎn)通常位于惡劣的工作環(huán)境中，因此節(jié)點(diǎn)配置后很難更換電池。節(jié)點(diǎn)能量受限制是無(wú)線傳感器網(wǎng)絡(luò)的基本功能。為了延長(zhǎng)網(wǎng)絡(luò)的生命周期，應(yīng)考慮網(wǎng)絡(luò)的節(jié)能。無(wú)線傳感器網(wǎng)絡(luò)路徑協(xié)議的設(shè)計(jì)可以選擇在數(shù)據(jù)傳輸過程中選擇最佳路徑，以降低網(wǎng)絡(luò)的能耗，延長(zhǎng)網(wǎng)絡(luò)的使用壽命。為了降低節(jié)點(diǎn)的能耗，提高網(wǎng)絡(luò)生命周期已成為無(wú)線傳感器網(wǎng)絡(luò)研究的熱點(diǎn)之一。從拓?fù)浣Y(jié)構(gòu)來看,無(wú)線傳感器網(wǎng)絡(luò)的路由協(xié)議可分為平面型和層次型,由于平面型路由協(xié)議需要維持較大的路由表,占據(jù)較多的存儲(chǔ)空間,因而并不適合在大規(guī)模網(wǎng)絡(luò)中應(yīng)用,層次型路由算法可以在一定程度上解決這個(gè)問題.LEACH算法就是比較成熟和常用的分層路由算法.LEACH是一種基于簇的協(xié)議,針對(duì)無(wú)線傳感器網(wǎng)絡(luò)提出了分布式簇算法.其基本思想是減少與基站直接通信的節(jié)點(diǎn)數(shù)目,并通過數(shù)據(jù)融合技術(shù)減少通信量,采用節(jié)點(diǎn)輪流隨機(jī)擔(dān)任簇頭的方式均衡網(wǎng)絡(luò)的能耗.研究表明,LEACH協(xié)議可以將網(wǎng)絡(luò)的生存期較之前的平面多跳路由協(xié)議和靜態(tài)分簇算法延長(zhǎng)15%左右.雖然LEACH協(xié)議具有許多優(yōu)點(diǎn),但其在選舉簇頭時(shí)采用隨機(jī)的方式,沒有考慮節(jié)點(diǎn)的剩余能量、位置和節(jié)點(diǎn)的密集度等問題,還存在需要改進(jìn)的地方.本文在分析LEACH協(xié)議的運(yùn)行機(jī)制、優(yōu)勢(shì)和存在問題的基礎(chǔ)上,提出了LEACH協(xié)議的改進(jìn)方案,采用改進(jìn)的遺傳算法結(jié)合最優(yōu)簇?cái)?shù)目的方法進(jìn)行分簇,待分簇完成后再利用節(jié)點(diǎn)剩余能量,距簇內(nèi)質(zhì)心的距離、節(jié)點(diǎn)覆蓋度和密鑰數(shù)目等約束條件選擇簇首.仿真結(jié)果表明,該方法較LEACH協(xié)議能夠更有效地延長(zhǎng)網(wǎng)絡(luò)的生存期.1le未來網(wǎng)絡(luò)優(yōu)化中的節(jié)點(diǎn)分簇LEACH(lowenergyadaptiveclusteringhierarchy)是一種基于概率的低功耗自適應(yīng)分簇協(xié)議,其定義了“輪”的概念,一輪由初始化階段和穩(wěn)定工作階段組成,為了避免額外的處理開銷,穩(wěn)定階段一般持續(xù)相對(duì)較長(zhǎng)的時(shí)間.初始化階段即簇的形成階段,在此階段中要決定由哪些傳感器節(jié)點(diǎn)來充當(dāng)簇首,簇首節(jié)點(diǎn)必須從那些沒有當(dāng)選過的節(jié)點(diǎn)中選擇,直到所有節(jié)點(diǎn)都充當(dāng)過簇首節(jié)點(diǎn)后,選舉重新開始,所有節(jié)點(diǎn)獲得重新當(dāng)選簇首的機(jī)會(huì).簇頭節(jié)點(diǎn)的選擇方法為,網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)生成0～1之間的隨機(jī)數(shù),如果該隨機(jī)數(shù)小于閾值T(n),則該節(jié)點(diǎn)當(dāng)選為簇首.T(n)的計(jì)算公式如式(1)所示:其中,p是網(wǎng)絡(luò)中簇首節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)目的百分比,r為當(dāng)前的輪數(shù),G是最近1/p輪中還未當(dāng)選過簇頭的節(jié)點(diǎn)集合.使用這個(gè)門限,可以保證每個(gè)節(jié)點(diǎn)在1/p操作中充當(dāng)一次簇首.簇頭節(jié)點(diǎn)產(chǎn)生后,主動(dòng)向網(wǎng)絡(luò)中所有節(jié)點(diǎn)廣播這一信息,沒有成為簇首的節(jié)點(diǎn)接收到分簇消息后,根據(jù)信號(hào)強(qiáng)度來選擇要加入的簇,并通知相應(yīng)的簇首.各簇中的節(jié)點(diǎn)采用TDMA的方式與簇首進(jìn)行通信.在穩(wěn)定階段,節(jié)點(diǎn)持續(xù)采集監(jiān)測(cè)數(shù)據(jù)并傳給簇首,簇首在將數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn)以前,先將接收到的信息進(jìn)行數(shù)據(jù)融合,減少冗余數(shù)據(jù),以節(jié)省通信的能量消耗.持續(xù)一段時(shí)間之后,整個(gè)網(wǎng)絡(luò)重新進(jìn)入簇形成階段開始新一輪的簇首選舉過程,重新選擇簇首進(jìn)行分簇,循環(huán)進(jìn)行上述過程,直至網(wǎng)絡(luò)能量消耗完為止.LEACH協(xié)議可保證每個(gè)節(jié)點(diǎn)在一個(gè)監(jiān)測(cè)周期內(nèi)有且僅有一次機(jī)會(huì)成為簇頭節(jié)點(diǎn),達(dá)到均衡網(wǎng)絡(luò)節(jié)點(diǎn)能耗的目的,另外由于采用層次型網(wǎng)絡(luò)結(jié)構(gòu),節(jié)點(diǎn)不需要存儲(chǔ)大量的路由信息.基于以上兩個(gè)方面,LEACH協(xié)議可以延長(zhǎng)15%左右的網(wǎng)絡(luò)生存期,具有一定的優(yōu)勢(shì).但是其也存在不足之處,已有的研究表明LEACH協(xié)議主要存在以下幾個(gè)問題:1)產(chǎn)生的簇首數(shù)目與總能耗最小時(shí)的最優(yōu)簇?cái)?shù)目不一致,只有在不到20%的情況下兩者吻合;2)單純以概率的方式產(chǎn)生簇頭,未考慮節(jié)點(diǎn)剩余能量對(duì)節(jié)點(diǎn)地位的影響,剩余能量低的節(jié)點(diǎn)也可以當(dāng)選為簇頭,會(huì)加速能量低的節(jié)點(diǎn)的死亡;3)沒有考慮節(jié)點(diǎn)的位置和節(jié)點(diǎn)密集度,對(duì)于整個(gè)網(wǎng)絡(luò)的能量消耗不能達(dá)到最優(yōu).在目前已有的一些相關(guān)研究中,對(duì)LEACH協(xié)議進(jìn)行了一定的改進(jìn),文獻(xiàn)中利用剩余能量和簇首間距離的約束提出了一種新的分簇算法LEACH-ED,有效延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間,文獻(xiàn)提出的算法首先根據(jù)節(jié)點(diǎn)的剩余能量概率性地選取一些候選簇頭,然后以簇內(nèi)通信代價(jià)的高低來競(jìng)爭(zhēng)產(chǎn)生最終的簇首.文獻(xiàn)提出的算法在簇首選擇中分兩個(gè)階段,首先采用LEACH中的算法初步選取簇頭,然后通過考慮節(jié)點(diǎn)的剩余能量和平均能量的大小關(guān)系在初步選取的簇頭中重新選取出新的簇頭,以達(dá)到延長(zhǎng)網(wǎng)絡(luò)生存周期的目的.2遺傳算法二式分簇協(xié)議基于以上對(duì)LEACH協(xié)議分析和針對(duì)其存在的問題,通過對(duì)其的改進(jìn),提出了改進(jìn)的路由協(xié)議LEACH-GEC,該協(xié)議也采用“輪”的概念,每輪分為簇的建立和穩(wěn)定傳輸兩個(gè)階段.簇的建立階段又分為兩個(gè)步驟,首先將最優(yōu)簇?cái)?shù)目與遺傳算法相結(jié)合,對(duì)網(wǎng)絡(luò)進(jìn)行分簇;然后再利用節(jié)點(diǎn)剩余能量,節(jié)點(diǎn)距簇質(zhì)心的距離和節(jié)點(diǎn)密度等約束條件來確定簇頭.分簇完成后,即進(jìn)入穩(wěn)定傳輸階段,該階段網(wǎng)絡(luò)的工作方式與LEACH協(xié)議沒有區(qū)別,這里不再贅述.2.1傳感節(jié)點(diǎn)發(fā)送包氣能耗模型對(duì)WSN網(wǎng)絡(luò)模型定義如下:基站位置固定,且有無(wú)限能量供應(yīng).節(jié)點(diǎn)能量有限,具有定位功能且能夠感知自身剩余能量,所有節(jié)點(diǎn)都不移動(dòng)位置.節(jié)點(diǎn)發(fā)送與接收數(shù)據(jù)包的能量消耗采用如圖1所示的能耗模型,節(jié)點(diǎn)能耗包括發(fā)送數(shù)據(jù)包能耗ETx(l,d)、接收數(shù)據(jù)包能耗ERx(l)、簇頭數(shù)據(jù)聚集能耗Eaggregation(n,l)和傳感節(jié)點(diǎn)感知能耗Esense(l).根據(jù)發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)的距離d與閾值距離d0的關(guān)系,節(jié)點(diǎn)發(fā)送數(shù)據(jù)包能耗模型有自由空間模式和多徑衰減模式兩種:當(dāng)d<d0時(shí),選擇自由空間模式;當(dāng)d≥d0時(shí),采用多徑衰減模式.因此,節(jié)點(diǎn)將長(zhǎng)度為l-bit的數(shù)據(jù)包發(fā)送至距離為d處節(jié)點(diǎn)的能耗為式(2)中,Eelec,εfs和εamp為常數(shù),由實(shí)際節(jié)點(diǎn)性能決定.節(jié)點(diǎn)接收數(shù)據(jù)包時(shí),只有接收電路工作,因此節(jié)點(diǎn)接收長(zhǎng)度為l-bit的數(shù)據(jù)包能耗為ERx(l)=ERx-elec(l)=lEelec.(3)簇頭將n個(gè)長(zhǎng)度為l-bit的成員節(jié)點(diǎn)數(shù)據(jù)包聚集為一個(gè)長(zhǎng)度為l-bit的數(shù)據(jù)包時(shí)簇頭數(shù)據(jù)聚集能耗為Eaggregation(n,l)=nlEDA,(4)式(3)中,EDA為聚集1b數(shù)據(jù)包的能耗.節(jié)點(diǎn)中的傳感器模塊、ADC和MCU共同采集長(zhǎng)度為l-bit感知數(shù)據(jù)能耗為Esense(l)=lEsense.(5)式(4)中,Esense為采集和處理1b感知數(shù)據(jù)包的能耗.2.2基于遺傳算法的分簇算法最優(yōu)簇?cái)?shù)目的計(jì)算需要考慮簇頭節(jié)點(diǎn)數(shù)據(jù)聚集能力受限和不受限兩種情況.考慮WSN網(wǎng)絡(luò)的一般實(shí)際情況,按照節(jié)點(diǎn)數(shù)據(jù)聚集能力受限的情況來計(jì)算最優(yōu)簇?cái)?shù)目.當(dāng)簇頭處理能力有限、一次只能聚集m個(gè)(m≤Νk,m(m≤Nk,m稱為壓縮比)長(zhǎng)度為l-bit的感知數(shù)據(jù)時(shí),簇頭需經(jīng)ΝkmNkm次才能將自身和成員節(jié)點(diǎn)的感知數(shù)據(jù)轉(zhuǎn)發(fā)至Sink.此時(shí),網(wǎng)絡(luò)總能耗Etotal為Etotal=l[(2Ν-k)Eelec+Μ22kπΝεfs+EDAΝ+Νm(Eelec+εampd4toBS)].(6)Etotal=l[(2N?k)Eelec+M22kπNεfs+EDAN+Nm(Eelec+εampd4toBS)].(6)對(duì)式(6)關(guān)于k求一階導(dǎo)數(shù),得:dEtotal(k)dk=-l(Eelec+εfsΜ22k2πΝ)<0dEtotal(k)dk=?l(Eelec+εfsM22k2πN)<0.(7)由式(7)可知,在簇頭數(shù)據(jù)聚集能力受限時(shí),總能耗Etotal(k)為k的單調(diào)遞減函數(shù).顯然,當(dāng)k或m增大時(shí),總能耗減小.又因?yàn)榇財(cái)?shù)目k需滿足k≤Νmk≤Nm,所以最優(yōu)簇?cái)?shù)目Κ=ΝmK=Nm,此時(shí)網(wǎng)絡(luò)總能耗最小.計(jì)算出最優(yōu)簇?cái)?shù)目后,可以將其與遺傳算法相結(jié)合來對(duì)網(wǎng)絡(luò)進(jìn)行分簇.遺傳算法是效法基于自然選擇的生物進(jìn)化,利用選擇、交叉、變異、遷移等方法來對(duì)問題進(jìn)行優(yōu)化,以找到問題的最優(yōu)解.為了使遺傳算法適應(yīng)網(wǎng)絡(luò)分簇的要求,對(duì)其進(jìn)行改進(jìn),將網(wǎng)絡(luò)中的節(jié)點(diǎn)按照最優(yōu)簇?cái)?shù)目K從1～K隨機(jī)編號(hào),以此取代染色體的0,1編碼.染色體的長(zhǎng)度即是網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目,取種群數(shù)目為B.網(wǎng)絡(luò)的分簇就是將眾多的網(wǎng)絡(luò)節(jié)點(diǎn)按照其所處的位置進(jìn)行區(qū)域劃分,為了使分簇更加均勻,取適應(yīng)度函數(shù)為F(s)=a1∑i1<j1√(xi1-xj1)2+(yi1-yj1)2+a2∑i2<j2√(xi2-xj2)2+(yi2-yj2)2+?+aΚ∑iΚ<jΚ√(xiΚ-xjΚ)2+(yiΚ-yjΚ)2?i1∈C1,i2∈C2,?,iΚ∈CΚ?(8)F(s)=∑i1<j1a1(xi1?xj1)2+(yi1?yj1)2????????????????????√+∑i2<j2a2(xi2?xj2)2+(yi2?yj2)2????????????????????√+?+∑iK<jKaK(xiK?xjK)2+(yiK?yjK)2?????????????????????√?i1∈C1,i2∈C2,?,iK∈CK?(8)其中K是網(wǎng)絡(luò)的最優(yōu)簇?cái)?shù)目,C1,C2,…,CK是簇的編號(hào),a1,a2,…,aK分別是簇C1,C2,…,CK中節(jié)點(diǎn)的數(shù)目.該適應(yīng)度函數(shù)的含義是對(duì)網(wǎng)絡(luò)中所有簇的兩個(gè)簇內(nèi)節(jié)點(diǎn)的距離進(jìn)行求和,為了進(jìn)行均勻的分簇,取適應(yīng)度函數(shù)值最小時(shí)的分簇方法為最優(yōu)解.經(jīng)過多代的交叉和變異進(jìn)行隨機(jī)搜索,可以求出網(wǎng)絡(luò)的分簇方法.需要指出的是,由于染色體編碼的改進(jìn),對(duì)于遺傳算法的交叉和變異操作也需要進(jìn)行改進(jìn).由于定義的染色體編碼代表的就是網(wǎng)絡(luò)中的節(jié)點(diǎn),屬于對(duì)離散的信息進(jìn)行編碼,所以在執(zhí)行交叉操作時(shí),采用單點(diǎn)交叉的方式來進(jìn)行,這樣更符合問題的本質(zhì).而在進(jìn)行變異操作時(shí),由于染色體的編碼并非0,1模式,所以變異的方式并不是在0,1之間進(jìn)行轉(zhuǎn)換,而是在除了本染色體編碼數(shù)字的剩下的K-1個(gè)數(shù)字中進(jìn)行隨機(jī)選擇.分簇算法步驟如圖2所示:2.3節(jié)點(diǎn)覆蓋度及質(zhì)心分簇結(jié)束后,再根據(jù)節(jié)點(diǎn)剩余能量,距簇內(nèi)質(zhì)心的距離和節(jié)點(diǎn)覆蓋度等約束條件找到合適的節(jié)點(diǎn)擔(dān)任簇首.選擇簇首的過程如下:1)計(jì)算簇內(nèi)節(jié)點(diǎn)剩余能量的均值Eaverage,其計(jì)算公式為Eaverage=Ν∑i=1Ei/ΝEaverage=∑i=1NEi/N,(9)其中Ei為節(jié)點(diǎn)i的剩余能量,N為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù).將簇內(nèi)節(jié)點(diǎn)的剩余能量逐一與Eaverage進(jìn)行比較,選其中大于Eaverage的節(jié)點(diǎn)存入集合EH.2)計(jì)算集合EH中節(jié)點(diǎn)的覆蓋度Li,其計(jì)算公式為L(zhǎng)i=Ci1+Ci22+?+CiΝΝA=Ν∑j=1CijjALi=Ci1+Ci22+?+CiNNA=∑j=1NCijjA,(10)其中,Cij是第i個(gè)節(jié)點(diǎn)與j-1個(gè)節(jié)點(diǎn)共同覆蓋的區(qū)域值,即j重覆蓋值,A是整個(gè)傳感區(qū)域的面積.根據(jù)直觀可以知道,節(jié)點(diǎn)越是密集的地方,其中節(jié)點(diǎn)的覆蓋度就會(huì)越小,根據(jù)節(jié)點(diǎn)的覆蓋度可以知道節(jié)點(diǎn)的密集度,將節(jié)點(diǎn)的覆蓋度與集合EH的節(jié)點(diǎn)平均覆蓋度Laverage=∑iLi/1+2+…+i進(jìn)行比較,選其中小于Eaverage的節(jié)點(diǎn)放入集合Ll中.3)計(jì)算簇內(nèi)質(zhì)心(Xc,Yc),計(jì)算公式如下:Xc=X1+X2+?+XΜΜ=Μ∑i=1XiΜ;(11)Yc=Y1+Y2+?+YΜΜ=Μ∑i=1YiΜ,(12)其中(Xi,Yi)是節(jié)點(diǎn)i的坐標(biāo),M是簇內(nèi)存活的節(jié)點(diǎn)數(shù).計(jì)算集合Ll中的節(jié)點(diǎn)距質(zhì)心的距離D(i)為D(i)=√(Xc-Xi)2+(Yc-Yi)2i∈Ll,(13)取其中D(i)最小的節(jié)點(diǎn)作為簇首,簇首選擇結(jié)束.4)根據(jù)預(yù)先存儲(chǔ)在節(jié)點(diǎn)上的密鑰進(jìn)行分析,當(dāng)候選簇頭節(jié)點(diǎn)在剩余能量、覆蓋度和質(zhì)心距離相近的情況下,優(yōu)先選擇與簇內(nèi)節(jié)點(diǎn)有共同密鑰的節(jié)點(diǎn)當(dāng)選簇頭,這樣即保證了簇頭選擇的合理性,又確保了整個(gè)簇內(nèi)通信的安全性.3基于letch-gec的分簇算法仿真場(chǎng)景如下:假設(shè)普通節(jié)點(diǎn)的初始能量為0.5J或1J,在100m×100m的目標(biāo)區(qū)域內(nèi)隨機(jī)部署100個(gè)節(jié)點(diǎn),基站位置為(50,50).設(shè)定發(fā)送/接收的單元能耗Eelec為50nJ/b,εfs為10pJ/b/m2,放大器能耗εamp為100pJ/b/m2,簇頭節(jié)點(diǎn)的數(shù)據(jù)聚集能力m取為20.在MATLAB環(huán)境下進(jìn)行編程仿真.圖3和圖4是100個(gè)節(jié)點(diǎn),均勻分布在100m×100m的被測(cè)區(qū)域中,基站位于區(qū)域中心時(shí),分別利用LEACH-GEC和LEACH算法進(jìn)行分簇并選舉簇頭的結(jié)果.從圖中可以看出,利用LEACH-GEC進(jìn)行分簇,其簇?cái)?shù)目和簇內(nèi)成員節(jié)點(diǎn)數(shù)目的均勻性均優(yōu)于LEACH算法,并且選舉出來的簇頭較接近簇內(nèi)質(zhì)心位置且能夠確保簇內(nèi)的安全通信,較好地克服了LEACH協(xié)議的弱點(diǎn).本文提出的算法運(yùn)用遺傳算法對(duì)其進(jìn)行分簇,并綜合考慮節(jié)點(diǎn)剩余能量、覆蓋度、與質(zhì)心距離和共享密鑰數(shù)綜合選擇簇頭.由于上述過程是在基站完成的,減輕了節(jié)點(diǎn)在運(yùn)算上的負(fù)擔(dān),可以較好地滿足WSN中輕量級(jí)處理的要求.表1給出了添加本方案的LEACH協(xié)議和原有協(xié)議中第1個(gè)節(jié)點(diǎn)死亡和最后一個(gè)節(jié)點(diǎn)死亡的輪數(shù):可以看出考慮安全加/解密帶來的能耗,更加有利于平衡節(jié)點(diǎn)的能量負(fù)載,延長(zhǎng)網(wǎng)絡(luò)的整體壽命,并進(jìn)一步提高網(wǎng)絡(luò)中傳輸信息的安全性,從而證明將密鑰管理方案應(yīng)用在分簇算法上是可行的.相比LEACH協(xié)議而言,這樣做的目的可以避免簇頭因隨機(jī)選取帶來的通信能耗,雖然