無線傳感器網(wǎng)絡(luò)路由算法研究

無線傳感器網(wǎng)絡(luò)路由算法研究

無線傳感器網(wǎng)絡(luò)是計算機和技術(shù)應(yīng)用的一個新領(lǐng)域。它結(jié)合了傳感器技術(shù)、嵌入式控制技術(shù)、分布式數(shù)據(jù)處理技術(shù)、現(xiàn)代網(wǎng)絡(luò)和無線通信技術(shù)等。通過各類微型傳感器對目標(biāo)信息進行實時監(jiān)測,由嵌入式計算資源對信息進行處理,能夠協(xié)作地實時監(jiān)測、感知和采集各種環(huán)境信息。無線傳感器網(wǎng)絡(luò)具有十分廣闊的應(yīng)用前景,在軍事國防、工農(nóng)業(yè)控制、城市管理、生物醫(yī)療、環(huán)境監(jiān)測、搶險救災(zāi)、防恐反恐和危險遠程控制等許多領(lǐng)域都有重要的科研價值和巨大的實用價值。目前,對無線傳感器網(wǎng)絡(luò)的研究主要集中在網(wǎng)絡(luò)層和鏈路層,而路由算法已成為無線傳感器網(wǎng)絡(luò)的核心技術(shù)之一。根據(jù)網(wǎng)絡(luò)中各個節(jié)點的地位和功能是否相同,路由算法可以分成平面路由算法和分簇路由算法。LEACH(lowenergyadaptiveclusteringhierarchy)算法是比較成熟且常用的分簇路由算法,許多分簇路由算法如TEEN(thresholdsensitiveenergyefficientsensornetworkprotocol)、PEGASIS(powerefficientgatheringinsensorinformationsystems)等大部分都在它的基礎(chǔ)上發(fā)展而來,因而選擇LEACH算法作為探討的對象具有較好的代表性。1打造網(wǎng)絡(luò)空間鏈上的打造方法LEACH算法使用自適應(yīng)成簇技術(shù)和簇頭節(jié)點的輪換技術(shù)。LEACH算法中引入了輪的概念,操作是分輪進行的,每一輪包含簇建立和穩(wěn)定運行這2個階段。在簇建立階段,將所有節(jié)點劃分為若干簇,每個簇隨機選舉一個簇頭。隨機性確保簇頭節(jié)點與基站之間數(shù)據(jù)傳輸?shù)母吣芎某杀揪鶆虻胤謹(jǐn)偟剿袀鞲衅鞴?jié)點。具體的產(chǎn)生機制是,各個傳感器節(jié)點生成0到1之間的隨機數(shù),如果隨機數(shù)小于某一個閾值T(n),那么這個節(jié)點就成為簇頭節(jié)點。閾值T(n)定義為T(n)={p1?p×(rmod1p)n∈G0其他(1)Τ(n)={p1-p×(rmod1p)n∈G0其他(1)式中,p是網(wǎng)絡(luò)中簇頭節(jié)點所占總節(jié)點數(shù)目的百分比;r是已完成的輪數(shù);G是一個集合,集合中的節(jié)點是前r輪中沒有充當(dāng)過簇頭節(jié)點的節(jié)點。使用這個閾值,每個節(jié)點會在1/p輪操作內(nèi)充當(dāng)一次簇頭節(jié)點,符號mod是求模運算符號。在第1輪的時候(r=0),每個節(jié)點充當(dāng)簇頭節(jié)點的概率為p。在第1輪充當(dāng)過簇頭節(jié)點的節(jié)點,在后面的輪中將不能再次充當(dāng)簇頭節(jié)點。這樣,剩下的節(jié)點數(shù)目變少了,因此能夠充當(dāng)簇頭節(jié)點的概率必須增加才能保證每一輪中簇的個數(shù)保持均衡。經(jīng)過1/p-1輪以后,T(n)=1,此時還沒有做過簇頭節(jié)點的節(jié)點,都可以成為簇頭節(jié)點,因為所有節(jié)點生成的隨機數(shù)都是在0和1之間。等過了1/p輪以后,所有節(jié)點又可以重新充當(dāng)簇頭節(jié)點了。在簇頭節(jié)點選定后,該簇頭節(jié)點對網(wǎng)絡(luò)中所有節(jié)點進行廣播,廣播數(shù)據(jù)包含該節(jié)點成為簇頭節(jié)點的信息。一旦傳感器節(jié)點收到廣播數(shù)據(jù)包,根據(jù)接收到的各個簇頭節(jié)點廣播信號強度,該節(jié)點選擇信號強度最大的簇頭節(jié)點加入,并向其發(fā)送成為其成員的數(shù)據(jù)包。簇頭節(jié)點收到成員節(jié)點的響應(yīng)后,會產(chǎn)生一個TDMA時隙表,并向成員節(jié)點廣播,告訴成員節(jié)點什么時刻可以發(fā)送數(shù)據(jù)。簇形成后進入穩(wěn)定運行階段,簇頭節(jié)點開始接收簇內(nèi)各節(jié)點采集的數(shù)據(jù),然后采用數(shù)據(jù)融合技術(shù)進行處理,將融合后的數(shù)據(jù)傳輸給基站。LEACH算法作為一種典型的分簇式路由算法,相比平面路由算法,在路由的發(fā)現(xiàn)和數(shù)據(jù)的傳遞過程中,消耗的能量少,建立路徑的時間短,可以將網(wǎng)絡(luò)整體生存時間延長15%,利用分簇能得到更佳的資源分配,并有助于改進功率控制,是一個最優(yōu)化能量使用效率的協(xié)議體系。2餡料沒有隨機產(chǎn)生(1)在LEACH算法中,簇頭的選取采用閾值判定的方法。對于一個節(jié)點n來說,為n隨機選取一個0到1之間的隨機數(shù),成為標(biāo)志值。如果隨機數(shù)小于某一個閾值T(n),那么這個節(jié)點就成為本輪的簇頭節(jié)點。由于這是一個隨機過程,只能從概率的角度研究簇頭的產(chǎn)生,因此無法保證簇頭數(shù)目的準(zhǔn)確性。(2)LEACH算法是讓網(wǎng)絡(luò)中的節(jié)點自組織地形成簇,簇頭是隨機產(chǎn)生的,這種隨機產(chǎn)生的方式無法保證簇頭節(jié)點的合理分布。當(dāng)簇頭節(jié)點位置比較集中時,簇的覆蓋區(qū)域?qū)⒊霈F(xiàn)部分重疊的現(xiàn)象,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不夠優(yōu)化;當(dāng)簇頭分布在邊緣區(qū)域時,簇內(nèi)節(jié)點到簇頭的距離將變大,使得簇的載荷也相應(yīng)變大。(3)LEACH算法忽略了被選簇頭在網(wǎng)絡(luò)內(nèi)的分布狀態(tài)和節(jié)點間不同的通信距離而導(dǎo)致的節(jié)點能量損耗的不平衡。在能量不均衡的網(wǎng)絡(luò)下繼續(xù)運行隨機簇頭選擇策略,如果低能量級的節(jié)點當(dāng)選為簇頭,那么節(jié)點就會由于過重的載荷而加速其剩余能量的消耗,從而降低了網(wǎng)絡(luò)的生存時間。3賠償算法的改進3.1基于網(wǎng)絡(luò)拓?fù)渲行牡膫€團頭區(qū)分如前所述,LEACH協(xié)議中簇頭的產(chǎn)生存在較大的隨機性,在實際仿真中并不能保證每一輪都能選出固定數(shù)量的簇頭節(jié)點。為了消除每輪簇頭數(shù)的差異,對每個簇頭節(jié)點產(chǎn)生的區(qū)域進行預(yù)先設(shè)定,使得每個區(qū)域產(chǎn)生一個簇頭,從而實現(xiàn)每輪的簇頭數(shù)嚴(yán)格一致?；诰W(wǎng)絡(luò)能耗最小的考慮,通過數(shù)學(xué)推導(dǎo)和仿真實驗,一般選取簇頭比例為5%。對于一個節(jié)點數(shù)為100的傳感器區(qū)域,則最優(yōu)簇頭數(shù)為5。在網(wǎng)絡(luò)初始化階段,基站根據(jù)節(jié)點位置信息,生成節(jié)點拓?fù)鋱D,確定網(wǎng)絡(luò)拓?fù)渲行?。為了限定簇頭節(jié)點產(chǎn)生的區(qū)域,圍繞網(wǎng)絡(luò)拓?fù)渲行膭澐謧鞲衅鲄^(qū)域,保證每個區(qū)域覆蓋20個節(jié)點。區(qū)域內(nèi)的節(jié)點攜帶所在區(qū)域的標(biāo)志信息1、2、3、4和5,這樣便將100個節(jié)點分?jǐn)偟?個區(qū)域內(nèi),不同區(qū)域的節(jié)點通過標(biāo)志信息進行區(qū)分。在簇頭選取過程中,每一輪的5個簇頭分別從5個區(qū)域中產(chǎn)生,這樣便保證了每輪的簇頭數(shù)嚴(yán)格為5,從而避免了簇頭數(shù)量的隨機性差異。3.2相鄰簇頭間距d的限定在LEACH算法中,簇頭的產(chǎn)生是隨機的,可能造成簇頭位置比較集中或者簇頭分布在邊緣的情況。簇頭分布不合理,簇內(nèi)通信能耗不平衡,遠距離的節(jié)點必然要消耗更多的能量,從而嚴(yán)重影響網(wǎng)絡(luò)的生存周期。為此,考慮利用下面的方法對上述問題進行改進。對于傳感器區(qū)域,當(dāng)簇頭分布較為合理時,簇的范圍應(yīng)盡量均勻覆蓋整個區(qū)域。因此簇頭之間的距離必須適中,不能太近或太遠。相鄰簇頭的間距應(yīng)該作為一個重要參數(shù)來進行分析。為了做到簇頭的均勻分布,可以通過限定相鄰簇頭的間距來實現(xiàn)。設(shè)節(jié)點分布區(qū)域的面積為S,節(jié)點數(shù)為N,簇頭產(chǎn)生比例為P,如果要覆蓋整個節(jié)點區(qū)域,則要求簇的平均半徑R滿足R≥Sπ×N×P??????√(2)R≥Sπ×Ν×Ρ(2)設(shè)相鄰簇頭的間距為D,當(dāng)D接近2R時,簇恰好可以將整個傳感器區(qū)域覆蓋,一般認(rèn)為這種分布比較合理。實際操作中,D的取值范圍在2R的某個鄰域內(nèi)。為了實現(xiàn)上述機制,在簇頭選取階段,將相鄰簇頭間距D進行限定,使得D滿足以下條件:D∈[2R(1-a),2R(1+a)],a∈(0,1)(3)對于一個100m×100m的區(qū)域,節(jié)點數(shù)為100,簇頭比例P為0.05,代入式(2)計算可得R≥25.2m(4)令R=26m,a=0.5,代入式(3),可求得D∈(26m,78m)(5)這樣,在第一個簇頭產(chǎn)生后,其余簇頭的產(chǎn)生區(qū)域就會被限定在以第一個簇頭為圓心,D為半徑的環(huán)形區(qū)域內(nèi)。最終,所有簇頭的間距都被限定在一個合理的范圍內(nèi),使得簇頭的分布較為均勻。3.3層內(nèi)節(jié)點能量分析在LEACH算法中,簇頭的產(chǎn)生完全依賴于概率事件,沒有考慮節(jié)點特性的差異。在簇頭產(chǎn)生階段,沒有成為簇頭的節(jié)點,都有機會成為簇頭。有些節(jié)點能量偏低,也有可能成為簇頭,這樣這個節(jié)點的能量就會很快耗盡。因此,選取簇頭時應(yīng)該考慮節(jié)點的能量水平,讓能量高的節(jié)點優(yōu)先成為簇頭。由此可見,剩余能量應(yīng)該作為選取簇頭的一個重要參數(shù)。剩余能量越大,成為簇頭的可能性相應(yīng)也越大。在具體操作中,當(dāng)每輪結(jié)束,簇頭要將簇內(nèi)節(jié)點的能量信息發(fā)送給基站?；緦?jié)點的能量進行分析,凡是能量低于閾值(系統(tǒng)設(shè)定為初始值的50%)的節(jié)點將不納入簇頭的考慮范疇?；谀芰孔畲蠡紤],在每個區(qū)域內(nèi)選取能量最大的節(jié)點成為簇頭節(jié)點。綜合上述改進方案,得到LEACH的改進算法,其流程如圖1所示。4簇頭節(jié)點選取在無線傳感器網(wǎng)絡(luò)中,路由算法一直是研究熱點。LEACH算法采用簇頭輪換技術(shù)