一種新的無線傳感器網(wǎng)絡半動態(tài)分簇路由協(xié)議

楊凌云, 馮友宏

(安徽師范大學物理與電子信息工程學院,安徽蕪湖 241000)

0 引 言

無線傳感器網(wǎng)絡[1]是由部署在檢測區(qū)域的大量無線傳感器網(wǎng)絡節(jié)點組成,通過無線通信方式形成的多跳的自組織網(wǎng)絡系統(tǒng),其目的是通過協(xié)作感知采集和處理網(wǎng)絡中感知對象的信息,并發(fā)送給觀察者。

在無線傳感器網(wǎng)絡中,網(wǎng)絡層路由協(xié)議[2]具有十分重要的地位,從網(wǎng)絡的拓撲結構進行分類,一般分為兩類:平面路由協(xié)議和分簇路由協(xié)議。平面路由協(xié)議主要從數(shù)據(jù)傳輸?shù)慕嵌瓤紤],每個傳感器節(jié)點既能搜集發(fā)生的事件產(chǎn)生數(shù)據(jù),也能作為中繼點進行數(shù)據(jù)轉發(fā)[3]。這些算法簡單,易于實現(xiàn),能夠很好地適應小規(guī)模的傳感器網(wǎng)絡,但是隨著網(wǎng)絡規(guī)模的增大,這些協(xié)議就出現(xiàn)了網(wǎng)絡開銷大和延遲長等缺點。比較常見的平面路由協(xié)議有gossiping[4],DD[5]和SAR[6]。在分簇協(xié)議中,路由算法基于大量高密度的sensor節(jié)點,重點考慮了算法的可擴展性。網(wǎng)絡通常被劃分成簇,典型的分簇路由協(xié)議有LEACH[7],TEEN[8],PEGASIS[9]等,分簇式路由在拓撲管理、節(jié)省能量、平衡網(wǎng)絡負載、節(jié)點移動等方面具有很多優(yōu)勢。

1 LEACH算法

LEACH協(xié)議是由MIT的Heinzelman等人[4]提出的一種分層次算法協(xié)議,它的核心思想是將所有的節(jié)點分為若干個簇,每個簇選舉一個簇頭,簇頭負責接收本簇內所有節(jié)點發(fā)送的數(shù)據(jù),進行數(shù)據(jù)融合之后,把信息發(fā)送給基站。

LEACH的基本思想是通過隨機循環(huán)選擇簇頭,將整個網(wǎng)絡的能量負載平均分配到每個節(jié)點,從而降低網(wǎng)絡能量消耗,延長網(wǎng)絡生命周期,LEACH的執(zhí)行是周期循環(huán)的,它把整個通信過程分為多輪,每一輪都包括簇的形成階段和數(shù)據(jù)傳輸階段。在每輪的簇頭選擇中,LEACH算法為每個節(jié)點設置了一個閾值T(n):

但是,LEACH算法也存在著很大缺陷:

(1)LEACH算法中簇頭的產(chǎn)生具有極大的隨機性,不能保證簇頭節(jié)點的均勻分布和簇規(guī)模的合理性。

(2)簇頭之間能量負載不均衡,距離基站比較近的簇頭節(jié)點因信息傳輸量大而過早死亡。

(3)用于簇形成和簇頭選擇的能量消耗在整個通信過程中的消耗不可忽略,頻繁的簇形成和簇頭選擇會使整個網(wǎng)絡的傳輸速率下降,同時加速網(wǎng)絡節(jié)點的死亡。

2 半動態(tài)路由算法描述

2.1 無線傳感器網(wǎng)絡分簇模型[11]

(1)無線傳感器網(wǎng)絡是由M個隨機部署在變成為N的正方形感知區(qū)域內的傳感器節(jié)點構成。

(2)基站遠離傳感器網(wǎng)絡節(jié)點區(qū)域,并且不考慮能量損耗。

(3)傳感器網(wǎng)絡中的節(jié)點是同構的,具有相同的處理信息和通信能力,節(jié)點初始能量相同且有限。

2.2 算法描述

節(jié)點的初始位置是未知的,在進行分簇之前,可以根據(jù)節(jié)點接收到的基站能量的大小判斷自身相對于基站的距離和現(xiàn)在所處位置,自身位置信息可通過某種定位算法得到,鄰居位置可以通過鄰居節(jié)點交換信息得到[12]。基站根據(jù)接收到節(jié)點能量的大小和確定的位置信息,確認簇的大小和簇頭的位置等信息,基本原則就是距離基站較近的簇較小,防止近簇頭能量的過快消耗。同時,還要考慮簇頭在整個網(wǎng)絡的均勻分布性,簇頭既不能過于集中,又要防止較遠節(jié)點無法正常加入簇。

2.2.1 簇頭的選擇

首先是在簇頭個數(shù)的選擇上,最優(yōu)簇頭選擇的計算公式為:

εfs自由空間信號放大倍數(shù);

d2簇頭到基站的距離。

同時結合具體的網(wǎng)絡實用環(huán)境,在仿真軟件重進行能耗分析可以發(fā)現(xiàn),在通常情況下簇頭的個數(shù)占整個網(wǎng)絡中節(jié)點綜述的p=5%為最佳。在簇頭選擇上,文中同時考慮剩余能量、已擔任簇頭時間、臨節(jié)點的接近程度等因素的影響。

式中:Eremain節(jié)點剩余能量;

這里產(chǎn)生簇頭的閾值就可以變換為:

式中:Emax節(jié)點的初始能量值;

Eremain節(jié)點剩余能量值;

tch已經(jīng)當選過簇頭的次數(shù);

2.2.2 簇的形成

在簇的形成過程中,要加入節(jié)點相對于基站的地理位置對簇大小的影響,文中利用非均勻的競爭半徑,使得靠近匯聚點的成員數(shù)目相對較小,從而簇頭能夠節(jié)約能量以供數(shù)據(jù)轉發(fā)使用,達到均衡簇頭能量消耗的目的,節(jié)點發(fā)送m bit消息所消耗的能量公式為:

在簇內,LEACH節(jié)點加入簇的時候僅考慮節(jié)點到簇頭的最優(yōu)化,決定加入哪個簇。也可以使用CMMBCR協(xié)議對重疊節(jié)點和簇頭節(jié)點之間建立一條能量之和最小的路由,在充分考慮了簇內鄰居節(jié)點的能量和距離分布信息的前提下優(yōu)化簇頭的選擇。

在簇的形成過程中,需要在考慮減少拓撲生成過程中的控制報文開銷,以及降低拓撲結構變動的頻率,減少網(wǎng)絡通信開銷的同時均衡網(wǎng)絡能量消耗,延長無線傳感器網(wǎng)絡的壽命。文中提出的半動態(tài)分簇路由就是這種思想很好的體現(xiàn)。在進行完簇的形成和簇頭的選擇后,簇的大小范圍基本保持不變,只是在固定的簇內進行簇頭的選擇,所有節(jié)點在簇頭進行完傳輸輪數(shù)之后,僅更新簇頭節(jié)點信息,而不必更換鄰居節(jié)點信息,減少非數(shù)據(jù)信息的通信量。如果簇內有節(jié)點死亡,則允許其它節(jié)點的加入,直至簇內節(jié)點死亡個數(shù)占簇內節(jié)點總個數(shù)的30%,基站根據(jù)網(wǎng)絡中存活節(jié)點個數(shù)等信息重新進行簇和簇頭的選擇。

2.2.3 簇的路由

在分層路由協(xié)議中,簇的路由主要分為簇內路由和簇間路由,簇內路由一般采用單跳形式,便于管理,對于簇半徑較大的簇,可以采用兩跳形式實現(xiàn)。在簇間、簇頭之間的傳送一般采用多跳形式,節(jié)約簇能量的消耗。但無論是簇內路由還是簇間路由,所有與基站的數(shù)據(jù)信息傳送都要通過簇頭進行傳送,特別是靠近基站的簇頭,通信量非常大容易死亡。

文中提出在路由通信采用雙簇頭形式(分為主簇頭和副簇頭,Head=0,Head=1),分別進行簇內節(jié)點信息的數(shù)據(jù)融合和簇頭之間的信息傳送,前面在簇的形成過程中,我們僅說明了如何進行主簇頭的選擇,在主簇頭確定之后,主簇頭根據(jù)節(jié)點距離自己的遠近選舉最近的節(jié)點作為副簇頭,并通知簇內節(jié)點。節(jié)點間的簇頭(包括主簇頭和副簇頭)組成類似與雙環(huán)的路由結構,主簇頭主要負責簇內節(jié)點的信息處理和傳送,副簇頭負責簇間節(jié)點信息的傳送,同時在主簇頭出現(xiàn)死亡或者不能正常工作等情況后,副簇頭能暫時直接代替主簇頭工作,保證通信的流暢性和信息的不丟失。這不僅能減少主簇頭的能量消耗,也能保證網(wǎng)絡信息傳送的安全性,減少第一個節(jié)點的死亡時間,延長整個網(wǎng)絡的壽命。

3 算法分析和仿真

為了比較LEACH及其改進算法的性能,將這兩個算法在Matlab中仿真實現(xiàn)。仿真假設無線傳感器網(wǎng)絡為一個邊長M=100 m的正方形區(qū)域,節(jié)點數(shù)N=100個,每個節(jié)點的初始能量E0=2 J,基站遠離無線傳感器網(wǎng)絡中的所有節(jié)點。每個信號的長度為1 000 bit,模型能量參數(shù)為:Eelec=50 nJ/bit。Efs=10 pJ/bit/m2,Emp=0.001 3 pJ/bit/m4。在仿真實驗中,若節(jié)點的剩余能量為0,則我們認為節(jié)點已經(jīng)死亡。隨著工作輪數(shù)的變化,兩種路由算法的網(wǎng)絡能量消耗以及網(wǎng)絡死亡節(jié)點數(shù)的性能比較如圖1和圖2所示。

在無線傳感器網(wǎng)絡中,第一個死亡節(jié)點出現(xiàn)的時間是衡量網(wǎng)絡壽命的一個重要參數(shù),為了提高網(wǎng)絡性能,應盡量推遲第一個死亡節(jié)點出現(xiàn)的時間。

圖1 網(wǎng)絡生命時間比較

圖2 網(wǎng)絡總能耗比較

從圖1中可以看出,LEACH算法的第一個死亡節(jié)點在368輪,在1 700輪之后節(jié)點全部死亡。而改進后的半動態(tài)路由算法的第一個死亡節(jié)點出現(xiàn)在840輪,節(jié)點全部死亡出現(xiàn)在2 450輪,可以看出,半路由協(xié)議有效地延長了整個無線傳感器網(wǎng)絡的壽命。

改進后的算法每一輪的總能量變化趨勢都比LEACH算法慢,這是由于半動態(tài)路由算法減少了網(wǎng)絡拓撲結構變化的能量消耗。同時,根據(jù)節(jié)點的分布情況,建立更有效、更合理的分簇方式,保證簇頭在整個網(wǎng)絡中的均勻分布,簇間通信采用副簇頭協(xié)助傳輸?shù)耐ㄐ欧绞?有效節(jié)省了總能耗。

4 結 語

LEACH算法是無線傳感器網(wǎng)絡中分層路由的一個很具有代表性的算法,它使資源有限的無線傳感器網(wǎng)絡得到了廣泛的應用,文中就是在LEACH算法的基礎上提出了半動態(tài)路由算法,改進了LEACH算法中簇的形成,簇頭在網(wǎng)絡中的均衡分布,同時盡量減少網(wǎng)絡拓撲結構的變化損耗等非信息損耗,均衡網(wǎng)絡節(jié)點能量消耗,延長網(wǎng)絡使用壽命。仿真結果表明,新算法基本達到了預想的目的。

[1] 崔 莉,鞠海玲.無線傳感器網(wǎng)絡研究進展[J].計算機研究與發(fā)展,2005,42(1):163-174.

[2] 高傳善,楊 珉,毛迪林.無線傳感器網(wǎng)絡路由協(xié)議研究綜述[J].世界科技研究與發(fā)展,2005(8):1-8.

[3] 郭永玲,王潛平.無線傳感器網(wǎng)絡分簇路由協(xié)議的研究[J].計算機與信息技術,2007(9):57-58.

[4] Hedetniemi S,Liestman A.A survey of gossiping and broadcastingin communication networ-ks[J].Networks,1988,18(4):319-349.

[5] Intanagonwiwat C,Govindan R,Estrin D,et al.Directed diffusion for wireless sensor networking[J].IEEE/ACM Trans.On NetWworking,2003,11(1):2-16.

[6] Sohrabi K,GAO J,Ailawadhi V.Protoco-ls for self-organization of a wireless sensor network[J].IEEE Personal Communications,2000,7(5):16-27.

[7] A Kyildizif,Suw Sankara Subramaniamy,Ca Yirc E.A survey on senso r netwo rk s[J].IEEE Communi2cations Magazine,2002,40(8):32-35.

[8] M anjeshwar A,Grawal D P.TEEN:a protocol for enhanced efficiency in wireless sensor networks[C].//Proc.of the 15th Parallel and Distributed Processing Symp.San Francisco:IEEE Computer Society,2001.

[9] Lindsey S,Raghavendr A C S.PEGASIS:Power-Efficient gathering in sensor information systems[C].//Pro.of the IEEE Aerospace Conference Proceedings,2002.

[10] WendiRabinerHeinzelman,Anantha Chandrakasan,Hari Balakrish2nan.Energy-efficient communication protocol for wireless microsensor network[C].//The proceedings of the Hawaii International Conference on Sys2tem Science,IEEE,2000:14-17.

[11] Ding W,Iyengar S S,Kannan R,et al.Energy equivalenceroutingin wireless sensornetworks[J].Microprocessors and Microsystems,2004,28(8):467-475.

[12] Chang J H,Tassiulas L.Maximum lifetime routing in wireless sensor networks[J].IEEE/ACM Transactions on Networking,2004,12(4):609-610.