基于lech協(xié)議的無線傳感器網(wǎng)絡(luò)路由算法研究

基于lech協(xié)議的無線傳感器網(wǎng)絡(luò)路由算法研究

根據(jù)最終形成的拓?fù)浣Y(jié)構(gòu)，worm網(wǎng)絡(luò)的路徑協(xié)議分為平面路徑協(xié)議和水平路徑協(xié)議。由于平面路徑協(xié)議中節(jié)點(diǎn)必須維護(hù)路的大信息，因此更多的空間需要進(jìn)行自組織的協(xié)調(diào)操作。此外，由于它無法與傳感器信息融合，因此不適合大型網(wǎng)絡(luò)。層次路由協(xié)議在很大程度上解決了這個(gè)問題,低能量自適應(yīng)分簇路由協(xié)議(LEACH)是比較成熟且常用的層次路由協(xié)議,所以選擇LEACH協(xié)議作為主要的研究對(duì)象具有很好的代表性。目前已經(jīng)有多種關(guān)于LEACH的改進(jìn)算法,國內(nèi)外不少研究人員提出了許多優(yōu)秀的算法和協(xié)議,其中有些協(xié)議設(shè)計(jì)了一套從簇頭選擇到數(shù)據(jù)傳輸?shù)耐暾惴?而有些協(xié)議只是針對(duì)其中一個(gè)階段提出了新的想法,但如何節(jié)省能量和延長網(wǎng)絡(luò)生命周期都是必須考慮的核心問題,也是設(shè)計(jì)更優(yōu)算法的目標(biāo)和準(zhǔn)則。簇頭的產(chǎn)生是簇形成的基礎(chǔ),也是簇結(jié)構(gòu)形成的前提條件,合理地選擇簇頭能形成性能更優(yōu)的簇結(jié)構(gòu),因而能在以后的過程中節(jié)省更多的能量,所以對(duì)簇頭的產(chǎn)生過程進(jìn)行改進(jìn)能更好地提高網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)分布的合理性,更好地延長網(wǎng)絡(luò)的生命周期。網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)的產(chǎn)生方式一直是人們研究路由協(xié)議改進(jìn)的重點(diǎn),早期改進(jìn)算法中比較經(jīng)典的有DCHS,它在閾值的計(jì)算公式中加入了能量比例因子,使能量剩余較高的節(jié)點(diǎn)有更大的機(jī)會(huì)當(dāng)選簇頭節(jié)點(diǎn),但是并沒有考慮曾經(jīng)當(dāng)選過簇頭節(jié)點(diǎn)的因素;LEACH-C和LEACH-F都是集中式的算法,其基本思想是基站通過與每個(gè)節(jié)點(diǎn)的信息交互,根據(jù)得到的各個(gè)節(jié)點(diǎn)信息,再結(jié)合全局信息來選擇最優(yōu)的節(jié)點(diǎn)做簇頭,但是這兩種算法由于每次都與基站進(jìn)行交互,增加了不少的能量消耗;文獻(xiàn)提出了一種基于方法論的模糊規(guī)則控制節(jié)點(diǎn)能量消耗的改進(jìn)LEACH算法,仿真實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的算法取得了較好的效果。近年來國內(nèi)不少研究人員也進(jìn)行了相應(yīng)的研究,提出了許多改進(jìn)算法。文獻(xiàn)通過調(diào)節(jié)閾值函數(shù)改進(jìn)了簇頭的產(chǎn)生方式,尤其當(dāng)簇頭節(jié)點(diǎn)距離感知區(qū)域較遠(yuǎn)時(shí)會(huì)取得更優(yōu)的效果;王萬良等人提出的改進(jìn)算法要求在簇的形成階段參與簇頭競爭的節(jié)點(diǎn)必須是從未當(dāng)選過簇頭的,并且能量大于前r輪中簇頭的平均能量消耗,以防止個(gè)別節(jié)點(diǎn)過快死亡,但是該算法每個(gè)候選節(jié)點(diǎn)必需知道前r輪的簇頭平均能量消耗,需要多次與基站進(jìn)行交互,增加了不必要的能量消耗;顧相平等人提出了一種結(jié)合剩余能量和簇頭間距離約束的一種新的分簇算法LEACH-ED,如果產(chǎn)生的隨機(jī)數(shù)小于考慮了能量因素的閾值,就需要計(jì)算該節(jié)點(diǎn)與現(xiàn)有簇頭間的距離,只有大于某一距離時(shí),才能成為簇頭,但是由于每次都需要計(jì)算候選簇頭與產(chǎn)生簇頭之間的距離,不僅增加了能量消耗,也增加了算法復(fù)雜度。1新的改進(jìn)算法1.1基于時(shí)間的letch-t設(shè)計(jì)傳統(tǒng)的LEACH算法的改進(jìn)大多都保留了LEACH的核心思想:通過閾值和隨機(jī)數(shù)的方式來確定簇頭的產(chǎn)生?？梢钥闯鯨EACH這種分層的思想雖然實(shí)現(xiàn)起來比較簡單,操作比較靈活,也達(dá)到了減少數(shù)據(jù)傳輸量、節(jié)省能量的目的,但不難發(fā)現(xiàn)由于產(chǎn)生隨機(jī)數(shù)的不確定性,導(dǎo)致了簇頭產(chǎn)生個(gè)數(shù)、位置、當(dāng)選次數(shù)等都是以一定概率隨機(jī)產(chǎn)生的,不一定是理想情況下的個(gè)數(shù),所以不會(huì)達(dá)到最優(yōu)的效果。本文提出了一種基于時(shí)間的LEACH改進(jìn)算法LEACH-T(LEACH-Time),改進(jìn)算法不再通過產(chǎn)生隨機(jī)數(shù)和閾值的方式來確定簇頭的產(chǎn)生過程,而是引入時(shí)間的概念,不僅能每次得到確定數(shù)量的簇頭個(gè)數(shù),也能通過考慮了節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)地理位置和曾經(jīng)當(dāng)選過簇頭的次數(shù)等信息更加合理的選擇節(jié)點(diǎn)作為簇頭,有效地提升了網(wǎng)絡(luò)的性能。改進(jìn)算法采用與LEACH協(xié)議相同的無線通信模型,基于最普通的情況,改進(jìn)算法考慮的環(huán)境是傳感節(jié)點(diǎn)隨機(jī)分布在已知區(qū)域內(nèi),傳感節(jié)點(diǎn)感知數(shù)據(jù)并由簇頭節(jié)點(diǎn)發(fā)送給基站,基站位于傳感節(jié)點(diǎn)分布區(qū)域之外,同時(shí)有以下假設(shè):(1)網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)是平等的,并且都是能量受限的;(2)傳感器節(jié)點(diǎn)與基站的位置一旦確定,在以后的網(wǎng)絡(luò)周期中是固定不變的;(3)傳感器節(jié)點(diǎn)擁有足夠的發(fā)送功率向基站發(fā)送數(shù)據(jù),可以通過功率控制實(shí)現(xiàn)不同距離的數(shù)據(jù)傳送。1.2節(jié)點(diǎn)防波劑產(chǎn)維護(hù)網(wǎng)絡(luò)生命周期LEACH-T是基于LEACH基本思想提出的改進(jìn)算法,在簇的建立階段和穩(wěn)定數(shù)據(jù)傳輸階段與傳統(tǒng)LEACH算法的過程大致相同,主要的思想體現(xiàn)在簇頭的選擇過程:簇頭的產(chǎn)生不再依靠一個(gè)隨機(jī)數(shù)和閾值,取而代之的是一個(gè)隨機(jī)時(shí)間間隔,擁有最短時(shí)間間隔的節(jié)點(diǎn)將最大可能的成為簇頭節(jié)點(diǎn)。為了時(shí)間間隔的計(jì)時(shí)實(shí)現(xiàn),我們?yōu)槊總€(gè)節(jié)點(diǎn)設(shè)置一個(gè)計(jì)時(shí)器,當(dāng)達(dá)到計(jì)時(shí)時(shí)間后判斷是否可以成為簇頭。算法的具體過程如下:(1)首先,在第一輪開始前,每個(gè)節(jié)點(diǎn)發(fā)送廣播消息到基站,基站收到每個(gè)節(jié)點(diǎn)的信息,并根據(jù)收到信息的強(qiáng)度計(jì)算每個(gè)節(jié)點(diǎn)距離基站的距離,然后基站將節(jié)點(diǎn)與基站的距離信息及其最大距離信息發(fā)送到每個(gè)節(jié)點(diǎn),這樣,開始階段每個(gè)節(jié)點(diǎn)通過一次與基站的交互后獲得了與基站的距離,這個(gè)距離在以后的過程中不會(huì)再發(fā)生變化,整個(gè)過程也只在網(wǎng)絡(luò)生命周期開始的時(shí)候執(zhí)行一次。(2)仍然保留“輪”的概念,每輪開始后每個(gè)節(jié)點(diǎn)不再產(chǎn)生一個(gè)隨機(jī)數(shù),而是產(chǎn)生一個(gè)隨機(jī)時(shí)間t。隨機(jī)時(shí)間t并不會(huì)直接作為節(jié)點(diǎn)計(jì)時(shí)器的計(jì)時(shí)時(shí)間,還需要考慮以下參數(shù)因子:1)節(jié)點(diǎn)的剩余能量信息因子(Einit-Ecurrent)/Einit;2)節(jié)點(diǎn)距離基站的位置信息因子Dcurrent/Dmax;3)節(jié)點(diǎn)曾經(jīng)當(dāng)選過簇頭的次數(shù)因子CH_t。綜合以上信息我們設(shè)定計(jì)時(shí)器的計(jì)時(shí)時(shí)間為:T=t×((Einit-Ecurrent)/Einit+Dcurrent/Dmax)×(CH_t+1),其中Einit為節(jié)點(diǎn)的初始能量,Ecurrent為節(jié)點(diǎn)的當(dāng)前剩余能量,Dcurrent為當(dāng)前節(jié)點(diǎn)與基站之間的距離,Dmax為所有節(jié)點(diǎn)中與基站的最大距離,CH_t的初始值為0。(3)節(jié)點(diǎn)計(jì)時(shí)器達(dá)到計(jì)時(shí)時(shí)間后,判斷當(dāng)前收到的簇頭廣播消息(ADV_CH)個(gè)數(shù)是否小于k個(gè)(其中k為當(dāng)前情況下的最優(yōu)簇頭個(gè)數(shù)),如果小于k個(gè),則節(jié)點(diǎn)成為簇頭節(jié)點(diǎn),廣播成為簇頭的消息,等待其他普通節(jié)點(diǎn)的加入。如果大于等于k個(gè),則節(jié)點(diǎn)不再參與簇頭節(jié)點(diǎn)的競爭,節(jié)點(diǎn)自動(dòng)成為普通節(jié)點(diǎn)并發(fā)送消息,準(zhǔn)備加入到相應(yīng)的簇中。(4)當(dāng)網(wǎng)絡(luò)中簇形成后,節(jié)點(diǎn)開始進(jìn)入正常的工作狀態(tài),同時(shí)需要簇頭節(jié)點(diǎn)在將感知數(shù)據(jù)發(fā)送到基站的過程中將本簇內(nèi)存活節(jié)點(diǎn)的個(gè)數(shù)也發(fā)送到基站,基站在收到所有簇頭節(jié)點(diǎn)的信息后,向網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)發(fā)送廣播消息,通知節(jié)點(diǎn)當(dāng)前網(wǎng)絡(luò)中存活節(jié)點(diǎn)的個(gè)數(shù),使得節(jié)點(diǎn)在下一次的簇的建立過程中選擇合適的簇頭個(gè)數(shù),其它的網(wǎng)絡(luò)過程與LEACH基本相同。從以上的過程可以看出:通過隨機(jī)時(shí)間的計(jì)時(shí)器方式產(chǎn)生的簇頭,每輪的個(gè)數(shù)是固定的,都是當(dāng)前情況下的理想個(gè)數(shù),而不像LEACH中每次都是不確定的。在產(chǎn)生的隨機(jī)時(shí)間上通過考慮以下的這些因子能更好的保證產(chǎn)生簇頭的合理性:節(jié)點(diǎn)的剩余能量因子保證了擁有更多能量的節(jié)點(diǎn)有更多的機(jī)會(huì)成為簇頭節(jié)點(diǎn);節(jié)點(diǎn)的位置因子的考慮保證了距離基站越近的節(jié)點(diǎn)具有更大的機(jī)會(huì)成為簇頭,這樣可以使得在傳送數(shù)據(jù)的過程中消耗更少的能量;曾經(jīng)做過簇頭的節(jié)點(diǎn)一般會(huì)比普通的節(jié)點(diǎn)消耗更多的能量,所以將這一因子考慮到計(jì)時(shí)器計(jì)時(shí)時(shí)間中更能選擇那些有更少次數(shù)做過簇頭的節(jié)點(diǎn)作為新的簇頭;隨機(jī)時(shí)間t的設(shè)計(jì)保證了產(chǎn)生的簇頭節(jié)點(diǎn)能更均勻的分布在網(wǎng)絡(luò)中,避免了當(dāng)節(jié)點(diǎn)能量相近時(shí)產(chǎn)生的簇頭節(jié)點(diǎn)過于集中的情況,因?yàn)橐坏┊a(chǎn)生的簇頭節(jié)點(diǎn)過于集中,將會(huì)形成不同大小的簇,且簇頭與簇內(nèi)成員距離也相對(duì)較遠(yuǎn),會(huì)消耗更多的能量。2第一個(gè)節(jié)點(diǎn)的死亡時(shí)間本文利用NS2軟件對(duì)傳統(tǒng)LEACH算法和改進(jìn)的算法LEACH-T進(jìn)行了大量的仿真實(shí)驗(yàn),仿真實(shí)驗(yàn)環(huán)境參數(shù)設(shè)置如表1所示。文獻(xiàn)指出:當(dāng)簇頭節(jié)點(diǎn)個(gè)數(shù)比例為3%到5%時(shí),網(wǎng)絡(luò)可以達(dá)到能量最優(yōu)的使用情況。這里我們選擇動(dòng)態(tài)確定的簇頭節(jié)點(diǎn)個(gè)數(shù),規(guī)定每輪循環(huán)中簇頭節(jié)點(diǎn)的個(gè)數(shù)為當(dāng)前存活節(jié)點(diǎn)個(gè)數(shù)的4%。圖1是關(guān)于網(wǎng)絡(luò)生命周期的8次仿真實(shí)驗(yàn)結(jié)果對(duì)比圖。由圖中數(shù)據(jù)可知,LEACH-T的平均網(wǎng)絡(luò)生命周期是867.5,LEACH的平均網(wǎng)絡(luò)生命周期是612.5,LEACH-T的平均網(wǎng)絡(luò)生命周期較LEACH提高了大約近1.42倍,而8次實(shí)驗(yàn)LEACH-T的各個(gè)結(jié)果變化幅度是90次,對(duì)比于LEACH的各個(gè)結(jié)果變化幅度210次,明顯在穩(wěn)定性上有了較大的提高。圖2是8次仿真實(shí)驗(yàn)得到的第一個(gè)節(jié)點(diǎn)死亡時(shí)間結(jié)果對(duì)比圖,從圖中分析可知,LEACH-T算法的第一個(gè)節(jié)點(diǎn)平均死亡時(shí)間為577.5,較LEACH的278.5有了很大的提高,同樣,在第一個(gè)節(jié)點(diǎn)死亡時(shí)間穩(wěn)定性上也有了相當(dāng)?shù)母倪M(jìn)。選取近似平均結(jié)果的第四次實(shí)驗(yàn)結(jié)果進(jìn)行詳細(xì)的對(duì)比分析。本文主要比較三個(gè)數(shù)據(jù)信息,分別是每輪簇頭節(jié)點(diǎn)的數(shù)目、網(wǎng)絡(luò)中存活節(jié)點(diǎn)的個(gè)數(shù)和網(wǎng)絡(luò)中節(jié)點(diǎn)的總能量消耗。從圖3中可以看出,傳統(tǒng)LEACH算法的簇頭選擇過程是以理想個(gè)數(shù)為中心隨機(jī)產(chǎn)生的,簇頭的產(chǎn)生個(gè)數(shù)不穩(wěn)定,而且簇頭的個(gè)數(shù)變化幅度也較大,這樣如果當(dāng)前產(chǎn)生的簇頭節(jié)點(diǎn)個(gè)數(shù)過少,則在本輪擔(dān)當(dāng)簇頭的節(jié)點(diǎn)就會(huì)由于負(fù)載過大而消耗過多的能量,從而造成節(jié)點(diǎn)的過早死亡;如果當(dāng)前產(chǎn)生的簇頭節(jié)點(diǎn)個(gè)數(shù)過多,則產(chǎn)生的分簇個(gè)數(shù)也過多,使得簇頭整體的能量消耗過大,不利于節(jié)約能量,而改進(jìn)后的LEACH-T則很好的解決了這個(gè)問題,在各段時(shí)間內(nèi)都會(huì)產(chǎn)生固定個(gè)數(shù)的簇頭,都是理想情況下最優(yōu)的簇頭個(gè)數(shù),動(dòng)態(tài)的簇頭保證了當(dāng)部分節(jié)點(diǎn)死亡后也是當(dāng)前情況下的最優(yōu)簇頭個(gè)數(shù),一方面減少了不必要的能量消耗,另一方面保證了每輪成簇個(gè)數(shù)的合理性。由圖4知,LEACH網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)的死亡時(shí)間是在230次時(shí),網(wǎng)絡(luò)的生命周期為620次;而LEACH-T網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)的死亡時(shí)間在560次時(shí),網(wǎng)絡(luò)生命周期為870,所以從第一個(gè)節(jié)點(diǎn)死亡時(shí)間考慮,LEACH-T較LEACH提高了近2.43倍,從整個(gè)網(wǎng)絡(luò)的生命周期角度考慮LEACH-T相對(duì)于傳統(tǒng)LEACH提高了也近1.4倍。由圖5可知,在相同的條件下LEACH-T能夠有效地節(jié)約更多的能量,網(wǎng)絡(luò)生存時(shí)間更長。同時(shí),改進(jìn)后算法得到的存活節(jié)點(diǎn)曲線和總能量消耗曲線相對(duì)于傳統(tǒng)LEACH算法都更加的平滑,說明了改進(jìn)算法在整個(gè)網(wǎng)絡(luò)生命周期中相對(duì)更穩(wěn)定、能量消耗更平均,而傳統(tǒng)LEACH算法由于隨機(jī)選取的不確定性,每次產(chǎn)生的簇頭節(jié)點(diǎn)個(gè)數(shù)不固定,每次消耗的能量差距也比較大,曲線表現(xiàn)得也相對(duì)不平滑。在相同的前提假設(shè)下,相比于近年來一些改進(jìn)算法,本文提出的改進(jìn)算法有自身的特點(diǎn)和優(yōu)越性,相比于文獻(xiàn)、文獻(xiàn),本算法在擁有最小能量消耗的情況下可以獲得更長的網(wǎng)絡(luò)生命周期;相比于文獻(xiàn),雖然在延長網(wǎng)絡(luò)生命周期方面取得近似的效果,但是本算法更能均衡網(wǎng)絡(luò)中的能量消耗,使得網(wǎng)絡(luò)中大部分的節(jié)點(diǎn)能存活更長的時(shí)間;雖然平均網(wǎng)絡(luò)生命周期較文獻(xiàn)提出的LAC協(xié)議獲得的生命周期要短,但是考慮到LAC協(xié)議需要?jiǎng)澐謪^(qū)域且需要TABLE存儲(chǔ)區(qū)域ID,不僅消耗了一部分能量,