一種新的無線傳感器網絡半動態分簇路由協議

楊凌云, 馮友宏

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

0 引 言

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

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

1 LEACH算法

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

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

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

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

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

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

2 半動態路由算法描述

2.1 無線傳感器網絡分簇模型[11]

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

(2)基站遠離傳感器網絡節點區域,并且不考慮能量損耗。

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

2.2 算法描述

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

2.2.1 簇頭的選擇

首先是在簇頭個數的選擇上,最優簇頭選擇的計算公式為:

εfs自由空間信號放大倍數;

d2簇頭到基站的距離。

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

式中:Eremain節點剩余能量;

這里產生簇頭的閾值就可以變換為:

式中:Emax節點的初始能量值;

Eremain節點剩余能量值;

tch已經當選過簇頭的次數;

2.2.2 簇的形成

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

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

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

2.2.3 簇的路由

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

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

3 算法分析和仿真

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

在無線傳感器網絡中,第一個死亡節點出現的時間是衡量網絡壽命的一個重要參數,為了提高網絡性能,應盡量推遲第一個死亡節點出現的時間。

圖1 網絡生命時間比較

圖2 網絡總能耗比較

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

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

4 結 語

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

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

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

[3] 郭永玲,王潛平.無線傳感器網絡分簇路由協議的研究[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.