無線傳感器網(wǎng)絡(luò)路由協(xié)議的改進(jìn)

無線傳感器網(wǎng)絡(luò)路由協(xié)議的改進(jìn)

無線傳感器網(wǎng)絡(luò)是監(jiān)測遠(yuǎn)程環(huán)境的強(qiáng)大工具之一。隨著計算機(jī)和無線傳感器技術(shù)的發(fā)展，其重要性日益突出。但是傳感器節(jié)點(diǎn)的通信范圍有限,只能與覆蓋范圍內(nèi)的節(jié)點(diǎn)進(jìn)行通信,因而在大規(guī)模的網(wǎng)絡(luò)中,需要采用多跳通信的方式進(jìn)行信息傳輸。傳感器節(jié)點(diǎn)通常由電池供電,且計算能力和存儲空間有限,所以必須有一個好的路由協(xié)議以盡量延長生存時間。無線傳感器網(wǎng)絡(luò)的路由協(xié)議可以分成平面路由協(xié)議和分層路由協(xié)議兩種。由于平面路由協(xié)議需要維持較大的路由表,占據(jù)較多的存儲空間,因而并不適合在大規(guī)模網(wǎng)絡(luò)中采用。分層路由算法可以在一定程度上解決這個問題。LEACH算法是比較成熟且常用的分層路由算法。但是LEACH算法并沒有考慮到每個節(jié)點(diǎn)的能量狀態(tài)因而不能有效提高網(wǎng)絡(luò)的生存時間,本文主要在能量的基礎(chǔ)上對LEACH做出改進(jìn)。1層次開理算法的性能1.1letch算法中簇頭的產(chǎn)生LEACH算法建立在所有節(jié)點(diǎn)都是平等且無線電信號在各個方向上能耗相同的假設(shè)上。在LEACH算法中,節(jié)點(diǎn)自組織成不同的簇,每個簇只有一個簇頭。所有非簇頭節(jié)點(diǎn)將自己的數(shù)據(jù)發(fā)給所屬簇的簇頭節(jié)點(diǎn),為減少冗余數(shù)據(jù)的傳輸,簇頭節(jié)點(diǎn)在數(shù)據(jù)融合后將數(shù)據(jù)發(fā)送給遠(yuǎn)方的接收器。這樣,每個非簇頭節(jié)點(diǎn)都只需要知道自己所屬簇的簇頭信息即可;簇頭也只需要維持很小的路由表。在實(shí)際使用中,還可以根據(jù)需要建立更多層次。在LEACH算法中,為了避免簇頭能量消耗過快,每個節(jié)點(diǎn)須輪流擔(dān)任簇頭。因此LEACH算法的實(shí)現(xiàn)分成一個個回合,每個回合又可分成簇形成階段和簇穩(wěn)定階段。為了減少分簇帶來的額外能耗,簇穩(wěn)定階段遠(yuǎn)遠(yuǎn)長于簇形成階段。在簇形成階段,每個傳感器節(jié)點(diǎn)先生成0-1之間的隨機(jī)數(shù),如果生成的隨機(jī)數(shù)小于閥值,那么這個節(jié)點(diǎn)就被選為簇頭。閥值的大小由式(1)確定:I={p/(1?p?(rmod(1/p)))c∈G0其它(1)Ι={p/(1-p*(rmod(1/p)))c∈G0其它(1)其中:p是網(wǎng)絡(luò)中簇頭所占比例,r是目前進(jìn)行的回合次,G是在最后1/p輪中沒有成為簇頭的節(jié)點(diǎn)集合。節(jié)點(diǎn)被選為簇頭后,就向外發(fā)送廣播信息;其它節(jié)點(diǎn)根據(jù)收到的廣播信息的信號大小決定要加入的簇,并向簇頭發(fā)送加入簇的請求。簇頭收到請求后將節(jié)點(diǎn)加入自己的路由表并為每個節(jié)點(diǎn)設(shè)定一個TDMA時間表,再將該表發(fā)送給所有簇內(nèi)節(jié)點(diǎn)。此后的簇穩(wěn)定階段,節(jié)點(diǎn)按照該表進(jìn)行數(shù)據(jù)傳輸。每隔一定時間整個網(wǎng)絡(luò)重新進(jìn)入簇形成階段開始新一輪的簇頭選舉過程。和平面路由算法相比,LEACH算法可以延長將近30%的網(wǎng)絡(luò)生存時間。但是,由于LEACH算法中簇頭的產(chǎn)生具有極大的隨機(jī)性,可能會出現(xiàn)部分簇頭相距過近或部分區(qū)域的節(jié)點(diǎn)離簇頭太遠(yuǎn)的情況,大大增加了節(jié)點(diǎn)的傳輸能耗,故不能有效地延長網(wǎng)絡(luò)生存時間。而且由于簇頭選舉的隨機(jī)性使得網(wǎng)絡(luò)的簇頭需要負(fù)擔(dān)的節(jié)點(diǎn)數(shù)不同,加重了個別簇頭節(jié)點(diǎn)的負(fù)擔(dān),使得網(wǎng)絡(luò)的負(fù)載平衡程度下降。1.2簇穩(wěn)定階段tdma本文在考慮了節(jié)點(diǎn)剩余能量和成為簇頭容易程度之間的關(guān)系以及簇頭間相對距離的基礎(chǔ)上,對LEACH算法進(jìn)行了改進(jìn),改進(jìn)后的算法和LEACH算法采用相同的網(wǎng)絡(luò)要求。和LEACH算法一樣,改進(jìn)算法依然分成一個個回合,每個回合分成簇形成階段和簇穩(wěn)定階段。同樣,為了減少簇形成階段帶來的額外能耗,簇穩(wěn)定階段遠(yuǎn)遠(yuǎn)長于簇形成階段。在簇形成階段,每個節(jié)點(diǎn)先根據(jù)自己的能量生成一個定時器,其中定時時間和剩余能量、簇頭比例成反比。定時時間到的節(jié)點(diǎn)產(chǎn)生一個0-1的隨機(jī)數(shù),剩余能量越大的節(jié)點(diǎn)越容易產(chǎn)生較小的隨機(jī)數(shù)。生成的隨機(jī)數(shù)小于閥值T的節(jié)點(diǎn)將自動升為簇頭并向外發(fā)送簇頭信息;隨機(jī)數(shù)不小于閥值T的節(jié)點(diǎn)將重新生成隨機(jī)數(shù),根據(jù)產(chǎn)生的隨機(jī)數(shù)和閥值的關(guān)系直接將自己確定為簇頭或普通節(jié)點(diǎn),再和LEACH算法一樣根據(jù)自己的節(jié)點(diǎn)屬性發(fā)送簇頭信息或加入簇請求;如果節(jié)點(diǎn)在定時時間結(jié)束之前收到簇頭的信息,就取消定時并向簇頭發(fā)送加入簇的請求。簇頭收到節(jié)點(diǎn)信息后,為每個簇內(nèi)節(jié)點(diǎn)分配TDMA時間表,并將它發(fā)送給簇內(nèi)節(jié)點(diǎn)。在簇穩(wěn)定階段,簇內(nèi)節(jié)點(diǎn)按照TDMA表進(jìn)行數(shù)據(jù)傳輸,簇頭將收到的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合后發(fā)送給遠(yuǎn)方的接收器。每隔一段時間整個網(wǎng)絡(luò)重新進(jìn)入簇形成階段開始新一輪的簇頭選舉過程。在簇形成階段,節(jié)點(diǎn)成為簇頭或簇內(nèi)節(jié)點(diǎn)的流程大致如圖(1)所示。1.3節(jié)點(diǎn)平均程度。網(wǎng)絡(luò)使用具有新的特征特性,網(wǎng)絡(luò)在傳感器網(wǎng)絡(luò)中,評價一個分簇算法好壞的參數(shù)有負(fù)載均衡程度、覆蓋率、節(jié)點(diǎn)擔(dān)任簇頭時間的公平度、分簇所需能量大小等。其中負(fù)載均衡程度和分簇所需能量是比較重要的兩個參數(shù)。在不考慮其它外界可能破壞因素的前提下,當(dāng)一個傳感器節(jié)點(diǎn)的能量小于零時,我們就認(rèn)為這個節(jié)點(diǎn)死亡;當(dāng)網(wǎng)絡(luò)中出現(xiàn)節(jié)點(diǎn)能量小于零,網(wǎng)絡(luò)就死亡。即將網(wǎng)絡(luò)中第一個節(jié)點(diǎn)死亡的時間定義為網(wǎng)絡(luò)生存時間。分簇所需的額外能量越少越有利于網(wǎng)絡(luò)生存時間的延長。在分層算法中,除了分簇時的能量消耗外,每輪中簇覆蓋節(jié)點(diǎn)的平均程度也會影響網(wǎng)絡(luò)的生存時間。而且由于簇中包含節(jié)點(diǎn)數(shù)目的不平衡會導(dǎo)致不同簇之間數(shù)據(jù)的容量不同,因此簇的負(fù)載平衡程度也是分層算法中衡量簇性能的重要標(biāo)準(zhǔn)之一。負(fù)載平衡因子的計算公式如下:=[head_num]∑i=1head???num(xi?μ)2=[head_num]∑i=1head_num(xi-μ)2其中:xi為第i個簇包含的節(jié)點(diǎn)個數(shù),μ為本輪簇平均包含的節(jié)點(diǎn)個數(shù)。LBF的數(shù)值越大說明簇的負(fù)載越平衡。2打造穩(wěn)定的節(jié)點(diǎn)在無線傳感器網(wǎng)絡(luò)中,相對于傳輸數(shù)據(jù)所需要的能量,傳感器節(jié)點(diǎn)需要進(jìn)行的運(yùn)算和存儲都比較少,所需要的能量基本可以忽略不計。所以無線傳感器網(wǎng)絡(luò)中,網(wǎng)絡(luò)生存時間主要取決于數(shù)據(jù)傳輸。在分層路由協(xié)議中,分簇所消耗的能量越少越好。由于本文提到的兩種算法的簇頭在簇形成階段都只需要發(fā)送兩次數(shù)據(jù)、接收一次數(shù)據(jù),分簇時簇頭所消耗的能量可以定義為:Ehead=k(Etran+Eamp·d2covercover2)·2+kEtran(-1)(2)其中:dcover為簇覆蓋的最遠(yuǎn)距離,是本輪的簇頭個數(shù),Etran為節(jié)點(diǎn)接收或發(fā)送一比特數(shù)據(jù)消耗的能量,Eamp是放大器消耗能量。由于兩種算法在穩(wěn)定階段的數(shù)據(jù)傳輸過程相同,且接收器的距離極遠(yuǎn),可以近似認(rèn)為所有節(jié)點(diǎn)到接收器的距離相等,所以暫不考慮簇穩(wěn)定階段的能量消耗情況。兩種算法的其它節(jié)點(diǎn)在分簇時都接收兩次數(shù)據(jù)、發(fā)送一次數(shù)據(jù),因此每個其它節(jié)點(diǎn)消耗的能量為:Enodetran=kEtran(+1)+k(Etran+Eamp·d2)(3)其中:d是傳感器節(jié)點(diǎn)到所屬簇頭的距離。3打造網(wǎng)絡(luò)生存時間和負(fù)載均衡程度lbf我們用Matlab隨機(jī)生成一個節(jié)點(diǎn)分布圖,在100×100的范圍內(nèi)隨機(jī)安放200個節(jié)點(diǎn),如圖(2)所示:這里,我們假定每個節(jié)點(diǎn)最初都具有5J的初始能量,每個節(jié)點(diǎn)接收或發(fā)送數(shù)據(jù)需要消耗Etran=50nJ/bit,為了能夠?qū)?shù)據(jù)傳輸足夠遠(yuǎn),放大器所消耗的能量為Eamp=100pJ/bit·m2,且每個數(shù)據(jù)包的大小固定為50bit,所有節(jié)點(diǎn)一旦放置就不能再移動,節(jié)點(diǎn)死亡只發(fā)生在能量為零時。根據(jù)本文的參數(shù)定義,利用Matlab仿真出在不同簇頭比例(簇頭比例從0.05到0.15變化)下,只考慮分簇消耗能量可以達(dá)到的網(wǎng)絡(luò)生存時間和負(fù)載均衡程度LBF。分別如圖(3)、(4)所示。圖3顯示了兩種算法不同的簇頭比例下只考慮簇形成階段時網(wǎng)絡(luò)可以生存的時間,顯然改進(jìn)后的算法可以有更長的生存時間,在簇頭比例為0.15時甚至可以達(dá)到LEACH算法生存時間的1.