楊凌云, 馮友宏

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

0 引 言

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

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

1 LEACH算法

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

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

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

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

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

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

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

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

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

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

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

2.2 算法描述

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

2.2.1 簇頭的選擇

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

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

d2簇頭到基站的距離。

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

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

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

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

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

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

2.2.2 簇的形成

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

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

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

2.2.3 簇的路由

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

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

3 算法分析和仿真

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

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

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

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

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

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

4 結(jié) 語

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

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

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

[3] 郭永玲,王潛平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議的研究[J].計算機(jī)與信息技術(shù),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.