一種改進(jìn)的lech協(xié)議能量?jī)?yōu)化算法

一種改進(jìn)的lech協(xié)議能量?jī)?yōu)化算法

1wsn的能量平衡由于無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的能量有限，網(wǎng)絡(luò)中的協(xié)議應(yīng)注意使用具有有限能量的網(wǎng)絡(luò)節(jié)點(diǎn)，確保整個(gè)網(wǎng)絡(luò)的生存期。經(jīng)典的解決方案是，節(jié)點(diǎn)應(yīng)盡量以較高的發(fā)射功率為代價(jià)直接發(fā)送數(shù)據(jù)，并使用多個(gè)跳轉(zhuǎn)來(lái)發(fā)送數(shù)據(jù)。作為無(wú)線傳感器網(wǎng)絡(luò)的經(jīng)典代表，lech仍然具有很高的參考價(jià)值。在此基礎(chǔ)上，我們發(fā)展并發(fā)展了許多相關(guān)協(xié)議，如epec、heed、deec等。為使WSN能耗最小化,近年來(lái)研究人員提出了高效的MAC協(xié)議和高效的路由協(xié)議.WSN中的能量消耗主要包括通信能耗、感知能耗和計(jì)算能耗.其中,通信能耗所占比重最大.因此,減少通信能耗是延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的有效手段.大量研究表明,通信過(guò)程中主要能量浪費(fèi)存在于:沖突導(dǎo)致重傳和等待重傳;非目的節(jié)點(diǎn)接收并處理數(shù)據(jù)形成串音;發(fā)射/接收不同步導(dǎo)致分組空傳;控制分組本身開(kāi)銷;無(wú)通信任務(wù)節(jié)點(diǎn)對(duì)信道的空閑偵聽(tīng)等.本文從能量角度分析了LEACH中存在的不足,在考慮了節(jié)點(diǎn)能量浪費(fèi)的情況下,分析和總結(jié)了LEACH單簇各個(gè)階段的能量損耗,提出通過(guò)控制簇成員數(shù)和合并極小簇的方法使WSN中的各個(gè)分簇的能量平衡;通過(guò)對(duì)穩(wěn)定階段的節(jié)點(diǎn)能量預(yù)測(cè)來(lái)改進(jìn)簇頭的選擇,減少節(jié)點(diǎn)的能量浪費(fèi).通過(guò)實(shí)驗(yàn)仿真結(jié)果證明,改進(jìn)后的算法在延長(zhǎng)網(wǎng)絡(luò)生存期和平衡各個(gè)分簇能量方面具有更好的性能.2問(wèn)題描述2.1分簇不平衡影響能量消耗LEACH采用隨機(jī)選擇輪流成為簇頭的算法,其參考指標(biāo)是節(jié)點(diǎn)成為簇頭的次數(shù);而節(jié)點(diǎn)的加入是以接收信號(hào)的強(qiáng)弱為依據(jù),因此在成簇過(guò)程中會(huì)出現(xiàn)簇內(nèi)節(jié)點(diǎn)過(guò)多的簇(極大簇)和簇內(nèi)節(jié)點(diǎn)過(guò)少的簇(極小簇).在LEACH穩(wěn)定階段,每個(gè)簇內(nèi)節(jié)點(diǎn)根據(jù)簇頭分配的時(shí)間片采集并發(fā)送數(shù)據(jù),采用TDMA機(jī)制可以很好的保證節(jié)點(diǎn)在時(shí)間片內(nèi)完成工作并不會(huì)造成沖突.簇頭等待簇內(nèi)所有節(jié)點(diǎn)采集一次數(shù)據(jù)并發(fā)送,即一幀(OneFrame),將簇內(nèi)數(shù)據(jù)進(jìn)行融合,最后發(fā)送給BS.由于在建立階段和穩(wěn)定階段,各個(gè)簇頭采用CSMA機(jī)制向BS發(fā)送數(shù)據(jù),那么簇頭向BS發(fā)送數(shù)據(jù)的頻率就取決于簇內(nèi)的節(jié)點(diǎn)總數(shù).極小簇由于簇成員少,因此完成數(shù)據(jù)采集和發(fā)送的時(shí)間更短,會(huì)比極大簇更頻繁將數(shù)據(jù)發(fā)送給基站.通過(guò)統(tǒng)計(jì)發(fā)現(xiàn)極小簇的簇頭節(jié)點(diǎn)和簇成員節(jié)點(diǎn)能量消耗分別要高出極大簇20%左右.所以,在沒(méi)有相應(yīng)機(jī)制的保證下,分簇不平衡會(huì)導(dǎo)致極小簇的整體能量消耗嚴(yán)重.2.2ack傳輸機(jī)制在點(diǎn)到點(diǎn)網(wǎng)絡(luò)傳輸模型中,從發(fā)送方到接收方的傳輸模式可分為可靠傳輸(基于ACK)和非可靠傳輸兩種.文獻(xiàn)的研究表明,基于ACK的可靠傳輸能耗比非可靠傳輸能耗大一倍以上,即采用ACK的傳輸機(jī)制能耗是較高的,而非可靠傳輸機(jī)制能耗開(kāi)銷則較低.LEACH使用的是能耗較低的非可靠傳輸.如果在穩(wěn)定階段某個(gè)簇頭因?yàn)槟芰亢谋M猝死,而該簇內(nèi)的節(jié)點(diǎn)并不知道簇頭已經(jīng)死亡,會(huì)繼續(xù)按照事先分配好的時(shí)間片采集和發(fā)送數(shù)據(jù)直到本輪結(jié)束,造成該簇內(nèi)成員的能量無(wú)謂損耗.使用ACK的可靠傳輸可以很容易解決該問(wèn)題,節(jié)點(diǎn)發(fā)送數(shù)據(jù)后會(huì)等待簇頭的ACK消息,超時(shí)等待后選擇重發(fā)數(shù)據(jù)或直接認(rèn)定簇頭已經(jīng)死亡,從而轉(zhuǎn)入休眠狀態(tài),等待下一輪重新開(kāi)始.但ACK機(jī)制會(huì)增加節(jié)點(diǎn)和簇頭的能量損耗,同時(shí)增加了整個(gè)網(wǎng)絡(luò)的延時(shí).3能量平衡的改善協(xié)議3.1節(jié)點(diǎn)發(fā)送數(shù)據(jù)假設(shè)在任一時(shí)間片,網(wǎng)絡(luò)中存在n個(gè)節(jié)點(diǎn),有m個(gè)節(jié)點(diǎn)期望發(fā)送數(shù)據(jù),每個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)的概率是q,將節(jié)點(diǎn)狀態(tài)定義為(n,m),其中0≤m≤n.于是有P(n,m)=(nm)qm(1?q)n?mΡ(n,m)=(nm)qm(1-q)n-m,∑m=0n∑m=0nP(n,m)=1(1)(n,0)表示沒(méi)有節(jié)點(diǎn)發(fā)送數(shù)據(jù),網(wǎng)絡(luò)為空閑狀態(tài);(n,1)表示某一個(gè)節(jié)點(diǎn)成功發(fā)送了信息;當(dāng)m>1時(shí)表示多個(gè)節(jié)點(diǎn)爭(zhēng)用信道,網(wǎng)絡(luò)有沖突發(fā)生.由此可得到n個(gè)節(jié)點(diǎn)中某一個(gè)節(jié)點(diǎn)發(fā)送成功的概率為Ps=P(n,1)=nq(1-q)n-1(2)n個(gè)節(jié)點(diǎn)均為空閑狀態(tài)的概率為Pi=P(n,0)=(1-q)n(3)若一個(gè)爭(zhēng)用期出現(xiàn)的概率為1-Ps-Pi,則n個(gè)節(jié)點(diǎn)中出現(xiàn)m個(gè)爭(zhēng)用期的概率為Pm=(1-Ps-Pi)mPs(4)由此求出在狀態(tài)(n,m)下?tīng)?zhēng)用期的期望值為E[(n,m)]=∑m=0∞∑m=0∞mPm≈1?PsPs(5)mΡm≈1-ΡsΡs(5)為了簡(jiǎn)化推導(dǎo),假定網(wǎng)絡(luò)中沒(méi)有干擾信號(hào),設(shè)一個(gè)爭(zhēng)用期長(zhǎng)度為2τ.從一個(gè)數(shù)據(jù)包開(kāi)始發(fā)送,經(jīng)沖突重發(fā)數(shù)次,到發(fā)送成功且信道轉(zhuǎn)為空閑時(shí)為止,共需的平均發(fā)送時(shí)間為Tavg.若信道占用期由發(fā)送成功時(shí)間T和端到端的延遲τ組成,那么網(wǎng)絡(luò)中n個(gè)節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)包的平均發(fā)送時(shí)間為Tavg(n)=2τ1?PsPs+T+τ(6)Τavg(n)=2τ1-ΡsΡs+Τ+τ(6)其中T=l/s,l為數(shù)據(jù)包長(zhǎng)度,s為信道速率.3.2letche-lec信號(hào)模型假設(shè)發(fā)送的能量包括信號(hào)處理與功率放大兩部分,接收的能量?jī)H用于信號(hào)處理,使用接近中心的距離d0作為參考,并且假設(shè)兩節(jié)點(diǎn)之間的距離d小于d0時(shí)采用自由空間模型,大于等于d0時(shí)采用多徑衰減模型.因此,當(dāng)兩個(gè)距離為d的節(jié)點(diǎn)之間發(fā)送l比特?cái)?shù)據(jù)時(shí),發(fā)送和接收所消耗的能量分別為:ETx(l,d)=ETx?elec(l)+ETx?amp(l,d)={lEelec+lεfsd2,d<d0lEelec+lεmpd4,d≥d0(7)EΤx(l,d)=EΤx-elec(l)+EΤx-amp(l,d)={lEelec+lεfsd2,d<d0lEelec+lεmpd4,d≥d0(7)ERx(l)=ERx-elec(l)=lEelec(8)其中Eelec是信號(hào)處理所需能量,由數(shù)字編碼、調(diào)制、濾波和擴(kuò)展信號(hào)等因素決定.放大器功耗εfs和εmp由發(fā)射距離和接收誤碼率等決定.LEACH在建立階段分為三步完成:簇頭發(fā)布;節(jié)點(diǎn)加入;簇頭計(jì)算TDMA并發(fā)布.3.2.1節(jié)點(diǎn)idsqp設(shè)區(qū)域M內(nèi)共有N個(gè)節(jié)點(diǎn),假設(shè)每個(gè)簇的成員數(shù)為k,共選舉產(chǎn)生簇頭數(shù)為Nch=「N/k?,Nch個(gè)簇頭廣播自己的節(jié)點(diǎn)ID,此時(shí)全網(wǎng)節(jié)點(diǎn)除簇頭外均接收該簇頭廣播信息.單簇能量損耗為Es1=ETx(lmsg,d)+kNchERx(lmsg)+(k+1)Tavg(Nch)Eidle(9)其中簇頭為Ech1=ETx(lmsg,d)+Tavg(Nch)Eidle(10)延時(shí)為Ts1=Tavg(Nch)(11)3.2.2單簇能量損耗節(jié)點(diǎn)根據(jù)接收的簇頭ID以及接收信號(hào)的強(qiáng)弱判斷加入到那一個(gè)簇中,在該階段由于節(jié)點(diǎn)采用CSMA方式通信,所以k個(gè)節(jié)點(diǎn)都試圖在同一時(shí)間發(fā)送自己的加入信息.單簇能量損耗為Es2=kETx(lmsg,d)+kERx(lmsg)+(k+1)Tavg(k)Eidle(12)其中簇頭為Ech2=kERx(lmsg)+Tavg(k)Eidle(13)延時(shí)為Ts2=Tavg(k)(14)3.2.3tags+k+1eidleEs3=klmsgEeda+ETx(lmsg,d)+kERx(lmsg)+(k+1)Tavg(Nch)Eidle(15)其中簇頭為Ech3=klmsgEeda+ETx(lmsg,d)+Tavg(Nch)Eidle(16)延時(shí)為Ts3=Tavg(Nch)(17)3.2.4單簇能量消耗仿真假設(shè)每個(gè)節(jié)點(diǎn)在各自的時(shí)間片t內(nèi)可以完成數(shù)據(jù)采集和發(fā)送的任務(wù),當(dāng)自己的時(shí)間片用完即進(jìn)入休眠狀態(tài).單簇能量損耗為Ef=ktEsleep+kETx(ldata,d)+kERx(ldata)+kldataEeda+ETx(ldata,dBS)+Tavg(Nch)Eidle(18)其中簇頭為Ech-f=kldataEeda+kERx(ldata)+ETx(ldata,dBS)+Tavg(Nch)Eidle(19)延時(shí)為Tf=kt+Tavg(Nch)(20)設(shè)每輪持續(xù)時(shí)間S,則一輪中該簇的能量消耗是Etotal=Es+「(S-Ts)/Tf?Ef(21)其中Es=Es1+Es2+Es3,Ts=Ts1+Ts2+Ts3.簇頭能量消耗為Etotal-ch=Ech-s+「(S-Ts)/Tf?Ech-f(22)其中Ech-s=Ech1+Ech2+Ech3.仿真參數(shù)設(shè)置如表1所示,通過(guò)仿真得到單簇一輪的簇頭能量損耗和簇成員能量損耗與k的關(guān)系.如圖1所示,當(dāng)簇成員數(shù)k≤7時(shí),簇頭的能量消耗明顯上升;當(dāng)k≥20,簇頭的能量損耗趨于穩(wěn)定.因此在后面的實(shí)驗(yàn)中,設(shè)定簇成員數(shù)的門限為7,即當(dāng)k≤7時(shí)認(rèn)為該簇是一個(gè)極小簇.3.3打造節(jié)點(diǎn)在缺少能量的情況下運(yùn)行通過(guò)3.2節(jié)能量計(jì)算可知,一個(gè)簇當(dāng)k值確定后,簇頭可以估算出下本輪穩(wěn)定階段消耗的能量,并檢查是否有足夠的能量完成該輪的操作,若沒(méi)有,則應(yīng)根據(jù)能量耗盡的時(shí)間點(diǎn)來(lái)計(jì)算TDMA并發(fā)布給所屬的節(jié)點(diǎn),避免因?yàn)榇仡^死亡而造成節(jié)點(diǎn)的能量無(wú)謂損耗.由于簇頭在穩(wěn)定階段的能耗遠(yuǎn)大于建立階段,將簇頭在穩(wěn)定階段的能量估計(jì)簡(jiǎn)化為:Esteady-ch=「S/Tf?Ech-f(23)由此可以估計(jì)簇頭在進(jìn)入穩(wěn)定階段過(guò)后,它的能量可以維持多少幀的工作時(shí)間,以此作為成員停止工作進(jìn)入休眠的依據(jù).在選舉簇頭的時(shí)候,將簇頭經(jīng)過(guò)本輪后的剩余能量作為選舉簇頭的標(biāo)準(zhǔn),由于選舉時(shí)并不知道該簇頭會(huì)有多少成員,因此使用簇成員數(shù)的門限值7,則修改后節(jié)點(diǎn)成為簇頭的計(jì)算公式為:Pch=???????1,EPEinit,0,ENP≥0ENP<0,EP>ETEP≤ET(24)Ρch={1,EΝΡ≥0EΡEinit,EΝΡ<0,EΡ>EΤ0,EΡ≤EΤ(24)其中ENP=EP-Esteady-ch,ET=EP-Ech-f.ENP是節(jié)點(diǎn)經(jīng)過(guò)本輪過(guò)后的剩余能量,EP是節(jié)點(diǎn)當(dāng)前的剩余能量,Einit是節(jié)點(diǎn)的初始能量,ET是節(jié)點(diǎn)的一個(gè)閥值能量,它的能量已不足以完成簇內(nèi)一幀的運(yùn)行.在網(wǎng)絡(luò)運(yùn)行初期,由于各個(gè)節(jié)點(diǎn)均有充足的能量來(lái)保證下一輪的網(wǎng)絡(luò)運(yùn)行,因此成為簇頭的概率為1,此時(shí)通過(guò)0-1隨機(jī)數(shù)來(lái)決定誰(shuí)將成為簇頭;當(dāng)節(jié)點(diǎn)ENP小于0時(shí),意味著該節(jié)點(diǎn)能量已不足以完成一輪的運(yùn)行,則成為簇頭的概率由當(dāng)前剩余能量和初始能量的比值決定;當(dāng)能量小于閥值后,節(jié)點(diǎn)能量已不足以完成一幀的運(yùn)行,則不適宜作簇頭,此時(shí)概率為0.3.4用居簇頭作為輔簇頭簇頭在建立階段廣播自己的簇頭消息(CHMessage),其后簇頭接收到節(jié)點(diǎn)的加入信息(JoinMessage),判斷自己是否是極小簇.如果判定自己為極小簇,就應(yīng)向鄰居簇發(fā)送合并信息(MergeMessage),若得到鄰居簇的響應(yīng),那么就將自己和所屬節(jié)點(diǎn)信息發(fā)送給鄰居簇頭,自己則成為輔簇頭;若沒(méi)有得到響應(yīng),則表示附近沒(méi)有鄰居簇或者鄰居簇也是極小簇,正在等待響應(yīng),則按照優(yōu)化結(jié)果k值計(jì)算節(jié)點(diǎn)的時(shí)間表.設(shè)節(jié)點(diǎn)工作時(shí)間為t,一個(gè)簇成員數(shù)為k的極小簇中的節(jié)點(diǎn)工作間隔時(shí)間是(k+1)t,(1≤k≤7),將其修正為20t(成員數(shù)大于20時(shí)簇頭能耗趨于穩(wěn)定),那么簇頭可以在每個(gè)間隔期間休眠(20t-kt)/k時(shí)間.通過(guò)這種方式,在建立階段避免網(wǎng)絡(luò)中出現(xiàn)多次合并的情況.關(guān)于輔簇頭的作用,主要是收集該簇中的節(jié)點(diǎn)數(shù)據(jù),并發(fā)送給簇頭.簇頭在分配時(shí)間片時(shí),根據(jù)輔簇頭的節(jié)點(diǎn)數(shù)分配,若存在m個(gè)節(jié)點(diǎn),則分配m+1個(gè)時(shí)間片,其中m個(gè)時(shí)間片用于節(jié)點(diǎn)采集數(shù)據(jù),1個(gè)時(shí)間片用于輔簇頭發(fā)送數(shù)據(jù)給簇頭.4實(shí)驗(yàn)?zāi)M4.1基于letch-c的輪能量消耗比較為了分析改進(jìn)后的算法有效性,使用的仿真環(huán)境為隨機(jī)分布在100m*100m范圍內(nèi)的100個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)的初始能量為2J.并在該環(huán)境中對(duì)LEACH、LEACH-C算法的存活節(jié)點(diǎn)數(shù)、平均每輪能量消耗進(jìn)行比較.其中LEACH-C是LEACH的一種改進(jìn)算法,它采用集中式算法,在成簇階段各個(gè)節(jié)點(diǎn)將自身位置信息和剩余能量匯報(bào)給BS,由BS根據(jù)各節(jié)點(diǎn)剩余能量占網(wǎng)絡(luò)總能量的比例作為簇首概率的基準(zhǔn)進(jìn)行優(yōu)化運(yùn)算,選出合適的簇首,再向全網(wǎng)廣播.LEACH-C雖然可以改善簇首的分布,但是它需要知道節(jié)點(diǎn)的位置(對(duì)于廉價(jià)的節(jié)點(diǎn),不容易實(shí)現(xiàn)),并且要求每次選舉的時(shí)候,BS需要知道全網(wǎng)的總剩余能量,并進(jìn)行集中的運(yùn)算,不能分布式實(shí)現(xiàn),影響了網(wǎng)絡(luò)的擴(kuò)展性.所有試驗(yàn)仿真參數(shù)在3.2.4節(jié)表1中已列出.為了對(duì)算法進(jìn)行比較,所有算法均采用相同的節(jié)點(diǎn)分布.4.2節(jié)點(diǎn)全生存時(shí)間圖3顯示了仿真時(shí)間內(nèi)各算法存活節(jié)點(diǎn)的總數(shù).存活節(jié)點(diǎn)為0的時(shí)刻定義為網(wǎng)絡(luò)的最大生存時(shí)間.由圖中可以看出,改進(jìn)后的算法與LEACH和LEACH-C相比,出現(xiàn)節(jié)點(diǎn)死亡的時(shí)間和節(jié)點(diǎn)全部死亡的時(shí)間都晚得多,體現(xiàn)了改進(jìn)算法網(wǎng)絡(luò)中的節(jié)點(diǎn)不僅能耗低而且均