一種多傳感器網絡節能路由算法

0無線傳感器網絡隨著微機電技術、計算機科學和通信技術的發展和融合，具有通信能力的微傳感器出現。它們被放置在特定的區域內，形成一個無線網絡，相互協作，感知、收集和處理區域內感知對象的信息，即傳感器網絡。傳感器網絡可以廣泛應用在如國防軍事、環境監測、交通管理、醫療衛生、反恐救災等領域,成為近幾年國內外研究的熱點。與傳統網絡相比,傳感器網絡具有以下特點:1)節點分布極其稠密且數目很大,每個節點維護全局信息是不可能的;2)節點的能量、存儲空間及計算能力等資源非常有限;3)傳感器節點布置完畢后,除了少數節點需要移動以外,大部分節點都是靜止的。因此,傳統的路由算法并不適合于無線傳感器網絡,必須針對其特性研究新的路由算法。由于無線傳感器網絡通常工作在人無法接近或者高危險區域,使得隨時更換節點能源是非常困難的,因此路由算法的節能性就成為研究人員關注的焦點,并提出了多種新穎的路由算法。1跳鄰近節點先對無線傳感器網絡模型進行描述,無線傳感器網絡的拓撲可看作是由節點和鏈路構成的圖,記為G=(V,E)。其中,V表示節點的集合,E表示邊的集合。節點x和y之間存在邊(x,y),意味著節點x和節點y是可以互相通信的1跳鄰居節點。Rx=x,n0,n1,…,S表示節點x到Sink節點的一條路徑,R*為節點x到Sink節點的所有路徑的集合。1.1mtpr的計算路徑MTPR(MinimumTotalTransmissionPowerRouting)算法基本思想是選擇消耗能量值最小的路徑傳送數據。令Rd=n0,n1,…,nd表示從源節點n0到目的節點nd的路徑(無線傳感器網絡中nd為Sink節點),E(ni,nj)為節點ni將數據傳給nj所要消耗的能量,則路徑Rd能量總消耗值計算公式為:P(Rd)=∑i=1d?1E(ni?ni+1)Ρ(Rd)=∑i=1d-1E(ni?ni+1)MTPR算法選擇的路徑RMTPR滿足:RMTPR=minRj∈R?P(Rj)RΜΤΡR=minRj∈R*Ρ(Rj)MTPR算法雖然選擇消耗能量值之和最小的路徑,但是有可能該路徑中的某個節點剩余能量值已經很小,造成該節點過度使用。1.2點ni剩余能量MMBCR(MinimumMaxBatteryCostRouting)算法能夠避開剩余能量值小的節點,用Pi(t)表示在t時刻節點ni的剩余能量,則對于路徑Rd定義權值P(Rd)=min?ni∈RdPi(t)Ρ(Rd)=min?ni∈RdΡi(t),MMBCR算法選擇路徑RMMBCR滿足P(RMMBCR)=maxRj∈R?P(Rj)Ρ(RΜΜBCR)=maxRj∈R*Ρ(Rj)。MMBCR算法能夠避開能量值很小的節點,增加了網絡的公平性,但是該算法卻不能保證每次傳輸數據消耗的能量最少,而有可能會增加網絡的能量消耗,從而導致網絡的生存周期縮短。1.3算法選擇路徑CMMBCR(ConditionalMMBCR)綜合了以上兩種算法,其思想如下:節點x向Sink節點發送數據時,搜索所有能夠達到Sink節點的路徑,若路徑上節點的剩余能量都很充足,則按照MTPR算法選擇消耗能量值之和最小的路徑。而如果路徑上節點的剩余能量值都較小,就按照MMBCR算法選擇路徑。這一過程可以通過為網絡節點增設閾值來實現,如果某一節點的剩余能量小于該閾值,則在選擇路由時盡量避開該節點,來延長整個網絡的生存周期。該算法既考慮了總的傳輸能量又考慮到了網絡中節點的剩余能量。但是,上述算法都很難在大規模無線傳感器網絡中實現,主要問題在于節點發送數據之前先確定數據要沿哪條路徑進行轉發,而節點在搜索轉發路徑時,需要知道整個網絡的拓撲結構,以及每個節點的剩余能量值,而網絡中每個節點的能量都在不斷變化,要得到每個節點確切的剩余能量值是很困難的。當然節點可以向其他節點廣播自己的剩余能量值,但這種方式會增加大量的控制消息,而且網絡規模越大,控制消息越多,同樣會縮短網絡的生存周期。因此,針對大規模無線傳感器網絡,提出了一種基于分簇的節能路由算法(Cluster-basedEnergySavingRouting,CESR),該算法是CMMBCR的近優算法,而存儲開銷和控制消息卻相對少得多。2簇內路由模塊算法的基本思想是采用逐步求解的方式,先將整個網絡分成若干個重疊簇,把一個簇看成一個整體,每個簇都有一個能量度量值(算法中采用簇內節點的平均能量值),這樣簇之間也形成了一個網絡拓撲結構,整個網絡存在兩級拓撲,簇間拓撲,及簇內拓撲。節點在選擇路由時先根據簇間拓撲選擇簇路由,確定發送的數據要經過哪幾個簇進行轉發,當數據經過某個簇時,重疊節點根據簇內拓撲,確定如何將信息傳送到下一個簇,即產生簇內路由。算法的前提是將網絡分成若干個相互重疊的簇,若兩個簇之間有重疊節點,則認為兩個簇是連通的,簇之間的數據通過重疊節點進行轉發,通常兩個簇之間有多個重疊節點,這樣就形成了多網關機制,重疊節點共同承擔轉發數據的任務。簇頭節點只負責維護簇內拓撲信息,以及收集簇內節點的剩余能量值,而不轉發任何數據,這就避免了傳統的算法只通過簇頭轉發數據,從而造成簇頭節點能量消耗過快,而頻繁更換簇頭節點的缺陷。具體的重疊簇分簇算法參考文獻。分簇工作完成之后,算法可以歸結為以下三個問題:1)簇頭如何計算簇的剩余能量值;2)節點如何選擇簇間路由;3)節點如何選擇簇內路由。2.1節點剩余能量值的變化當分簇穩定之后,簇內的每個節點都向自己的簇頭報告自己的剩余能量值,當簇頭節點收集了簇內各節點的剩余能量值之后,計算其平均值,作為簇的能量值的標識,然后向其他所有簇廣播,簇頭收集到其他簇的信息之后,形成簇間拓撲,然后向簇內所有節點廣播,這樣網絡中每個節點都有了簇拓撲圖。由于節點的剩余能量值在不斷變化,所以簇的剩余能量值也會隨時變化,這就需要簇頭節點周期性地收集簇內所有節點的剩余能量值,從而重新度量簇的能量值。當剩余能量值比較大時,局部節點能量的變化不會對整個網絡造成太大的影響,所以這時更新周期可以長一些,只有當網絡中每個節點的剩余能量值都比較小時,信息傳輸會對網絡的能量分布造成比較明顯的影響,這時更新周期相應地延長。簇的剩余能量值計算完成之后,這時如果把簇看成一個整體,那么所有的簇就形成了一個簇的拓撲圖,例如圖1中(a)中所示為一個網絡拓撲圖,有A,B,C,D,E五個簇,括號中的數字代表每個簇內節點的平均剩余能量值,那么圖1(a)中的網絡所對應的簇拓撲為圖1(b)所示。2.2控制參數的選取當節點有數據要向Sink節點發送時,該節點首先要計算簇間路由,即該消息要經過哪幾個簇進行轉發。由于簇拓撲圖中的邊沒有權值,所以簇間路由算法采用MMBCR算法,盡量選擇剩余能量值較大的簇轉發數據,下面采用改進的Bellman-Ford算法計算簇路由。算法描述如下:網絡拓撲圖G(V,E),對v∈V,P(v)表示v的剩余能量值,V[G]表示圖中頂點的個數,E[G]表示圖中邊的條數。尋找路徑s=v0,v1,v2,…,vk-1,vk=t(t為Sink節點所在的簇)使mink?1i=1i=1k-1p(vi)最大。for(eachvertexv∈V[G])//算法初始化{//對于圖中的每個頂點If(edge(s,v)∈E[G])//如果s到v存在邊{d[v]=INFINITE;n[v]=s;}else{d[v]=0;n[v]=NULL;}}d[s]=INFINITE;//#defineINFINITE65536for(i=1;i<|V[G]|;i++){for(eachedge(u,v)∈E[G]andu≠s){//對網絡中的每條邊if(d[v]<min(d[u],p[u])){//如果d[v]比d[u],p[u]都小d[v]=min(d[u],p[u]);n[v]=u;}}}i=n[t];while(n[i]≠s){//Path為從s到t的路由push(Path,n[i]);i=n[i];}當計算好簇路由之后,形成一個簇路由表,數據包攜帶簇路由信息向目標傳送。2.3cmmcr算法簇內路由決定一個數據包在簇內經過哪些節點進行轉發,當邊界節點收到來自其他簇的數據包之后,首先根據數據包攜帶的簇路由表,確定該數據包將要轉發到哪一個簇,將該簇與下一個簇的一個重疊節點作為目標節點,對簇內的網絡拓撲運用CMMBCR算法,計算數據包的轉發路徑,然后將數據包沿此路徑進行轉發。如圖2所示,數據包要經過簇A,B,C進行轉發,節點1接收到來自A簇的數據包后,首先根據數據包中的簇路由信息,確定要將數據包轉發到C簇,節點1根據簇內拓撲圖選擇一個B與C的重疊節點作為目的節點(節點4),然后利用CMMBCR算法計算到節點4的路徑1,2,3,4,數據包沿此路徑進行轉發到達節點4,節點4以同樣的方法將數據包向下一個簇進行轉發,直到轉發到目標節點所在的簇(目標節點一般為Sink節點)。一般情況下,兩個簇的重疊節點不止一個,這時在選擇重疊節點進行轉發數據時,選擇剩余能量值最大的一個。3算法分析與模擬實驗3.1整個網絡的更新在大型的無線傳感器網絡中,CESR算法比CMMBCR算法有明顯優勢,其存儲開銷小,控制消息少。下面以一個實際的網絡模型說明兩種算法的差別,假如網絡中有300個節點,網絡分為20個簇,每個簇內平均20個節點(因為簇間有重疊,一個節點可能同時屬于多個簇)。對于CESR算法,每個節點需要存儲簇間拓撲和所在簇的簇內拓撲兩個拓撲圖,但這要比存儲整個網絡拓撲圖小得多。對上述網絡中,每個普通節點需要存儲有20個頂點的簇間拓撲,以及20個頂點的簇內拓撲。而對于CMMBCR算法每個節點都要存儲有300個頂點的整個網絡拓撲。兩種算法都周期性地更新網絡拓撲圖。在上述的網絡中,對CMMBCR算法,在每次更新時,每個節點都需要向網絡中其他所有節點廣播自己的剩余能量值,所以會產生300×300條控制消息。而對于CESR算法,每個節點向簇頭發布自己的剩余能量值,簇頭收集簇內所有節點剩余能量之后,重新形成簇內拓撲,然后將簇內拓撲圖在本簇內廣播,所以每個簇內會產生40條控制消息,整個網絡內會形成20×40條控制消息。簇頭根據簇內節點的剩余能量值計算簇的平均剩余能量值,然后向其他的簇頭廣播,這樣會形成20×20條控制消息,而每個簇頭需要將形成的簇間拓撲向簇內所有節點廣播,又會形成20×20條控制消息,所以對CESR算法,每次更新網絡拓撲圖時將會產生1600條控制消息,這要比CMMBCR算法中控制消息少得多。由于CESR算法中,簇內消息不向其他簇傳播,對節點級造成的移動影響限制在本簇區域,只有當節點移動改變了簇間的連接時才在簇間傳播消息,這樣限制了由于節點移動對網絡拓撲結構的影響。3.2不同算法仿真下面采用OMNET++對算法進行仿真,并與CMMBCR算法進行比較。在OMNET++實驗環境中,設置網絡圖范圍為500×500,隨機分布71個節點(1個Sink節點),節點通信半徑為50,每個節點的初始能量值為2000(計算單位使用OMNET++仿真環境規定),節點ni與nj傳輸數據消耗的能量E(ni,nj)與其距離D(ni,nj)的關系為:E(ni,nj)=0.01×D2(ni,nj),采用的傳輸信道數據傳輸率為250kb、出錯率為0、信道延遲為0.01s,數據包長度為128bit。實驗中,從第10s開始,每10s為一個周期,每個周期內每個節點向Sink節點發送一個數據包,若某個節點的能量低于初始能量的30%,則認為該節點為低能量節點,數據不再通過該節點轉發,對于CESR算法采用了簡單的基于地理位置的分簇方法。仿真結果如圖3～圖5所示。圖3表示了某一周期內,每個節點向Sink節點發送數據所需要消耗的能量值,由圖可以看出,CESR算法中,節點向Sink節點發送一個數據包消耗的能量值略高于CMMBCR算法中消耗的能量值,但比較接近。圖4顯示了如果不考慮控制消息(即控制消息不消耗能量),50s內兩種算法能量消耗情況,可以看出,在不考慮控制消息的情況下,CESR算法在能量消耗方面比CMMBCR算法要多一些,但是比較接近。由以上兩圖可以看出,在不考慮控制消息的情況下,CESR算法是CMMBCR的近優算法,兩種算法在節能方面都表現出良好性能。圖5所示為考慮控制消息時兩種算法的能量消耗,實驗中,每傳送完一輪數據之后都進行拓撲圖的更新,由圖可以看出,對于CMMBCR算法,其能量消耗呈現快速上升趨勢,而CESR算法中由于控制消息少,其能量消耗是一種平緩上升的趨勢。由此可見,在考慮控制消息的情況下,CESR算法在節能方面明顯優于CMMBCR算法。為了說明CESR算法與普通分簇算法