張 揚(yáng),楊松濤,周 鵬,張香芝

(1.安徽中醫(yī)學(xué)院醫(yī)藥信息工程學(xué)院,合肥230038;2.安徽中煙工業(yè)公司,合肥230088;3.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,合肥230009)

0 引言

無線傳感器網(wǎng)絡(luò)是由數(shù)以百萬個(gè)散布在一個(gè)特定區(qū)域內(nèi)價(jià)格低廉的微型傳感器節(jié)點(diǎn)通過無線通信方式形成的自組織網(wǎng)路,能夠?qū)崟r(shí)感知、采集、處理區(qū)域內(nèi)的各種信息并發(fā)送給終端用戶,在軍事、環(huán)境、醫(yī)療、家庭等領(lǐng)域有廣闊的應(yīng)用前景。由于傳感器節(jié)點(diǎn)靠電池驅(qū)動(dòng),一般應(yīng)用于無人值守的區(qū)域,一旦投放,就很難再補(bǔ)充能量。因此,如何有效地降低能耗,最大限度地延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間就成為目前無線傳感器網(wǎng)絡(luò)研究的熱點(diǎn)問題之一。

為了降低能耗和延長(zhǎng)傳感器網(wǎng)絡(luò)的生命周期,研究人員先后提出了2個(gè)經(jīng)典的協(xié)議:一是基于簇結(jié)構(gòu)的LEACH協(xié)議;二是基于鏈的PEGASIS協(xié)議。由于這2個(gè)協(xié)議自身的缺陷,較適用于規(guī)模較小的應(yīng)用。本文提出了一個(gè)可應(yīng)用于大規(guī)模無線傳感器網(wǎng)絡(luò)的混合式協(xié)議,該協(xié)議將LEACH和PEGASIS協(xié)議進(jìn)行混合,即在同一簇內(nèi)采用PEGASIS鏈?zhǔn)降姆椒?。LEACH中簇頭(CH)和基站(BS)采用直接通信,有關(guān)文獻(xiàn)中也提到采用節(jié)點(diǎn)多跳的方式,但對(duì)如何實(shí)現(xiàn)這種多跳路由都沒有給出具體的說明,本書針對(duì)這個(gè)問題給出了距離能量(D-E)的多跳方法來實(shí)現(xiàn)和基站通信,從而有效地減少能量的消耗。

1 相關(guān)準(zhǔn)備工作

1.1 LEACH協(xié)議及其存在的問題

1.1.1 LEACH協(xié)議描述

LEACH是MIT的Chandrakasan等為無線傳感器網(wǎng)路設(shè)計(jì)的低能耗自適應(yīng)分層路由協(xié)議。它的基本思想是以循環(huán)的方式隨機(jī)選舉簇頭節(jié)點(diǎn),將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)上,從而達(dá)到降低網(wǎng)絡(luò)能耗、提高網(wǎng)絡(luò)整個(gè)生存周期的目的。LEACH每一循環(huán)為一輪,每一輪可以分為2個(gè)階段:簇的建立階段和穩(wěn)定階段。建立階段各節(jié)點(diǎn)獨(dú)立地按照一定概率自選舉為簇頭。選舉思想是:每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù),如果這個(gè)數(shù)小于閥值 T(n),則該節(jié)點(diǎn)被選為簇頭節(jié)點(diǎn)。T(n)的計(jì)算如下:

式中:P——網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)所占總節(jié)點(diǎn)數(shù)目百分比;

r——當(dāng)前的輪數(shù);

G——最近1/P輪中還未當(dāng)選過簇頭的節(jié)點(diǎn)集合。

從T(n)可以看出,當(dāng)選過簇頭的節(jié)點(diǎn)在接下來的輪中將不能成為簇頭,剩余節(jié)點(diǎn)當(dāng)選簇頭的閾值T(n)增大,節(jié)點(diǎn)產(chǎn)生小于 T(n)的隨機(jī)數(shù)的概率隨之也增大,所以節(jié)點(diǎn)當(dāng)選簇頭的概率增大。選定簇頭節(jié)點(diǎn)后,通過廣播一個(gè)消息告之整個(gè)網(wǎng)絡(luò)。網(wǎng)絡(luò)中的其他節(jié)點(diǎn)根據(jù)接收的信號(hào)強(qiáng)度決定從屬的簇,簇頭了解成員的數(shù)量及其標(biāo)志采用TDMA方法為簇中每個(gè)節(jié)點(diǎn)分配向其傳送數(shù)據(jù)的時(shí)間片。

穩(wěn)定階段,傳感器節(jié)點(diǎn)在自己的時(shí)間片內(nèi)將采集的數(shù)據(jù)傳送到簇頭節(jié)點(diǎn)。簇頭節(jié)點(diǎn)對(duì)簇中所有采集的數(shù)據(jù)進(jìn)行信息融合后再傳送給基站。穩(wěn)定階段持續(xù)一段時(shí)間后,網(wǎng)絡(luò)重新進(jìn)入簇的建立階段,進(jìn)行下一輪的簇重構(gòu),不斷循環(huán)直到所有節(jié)點(diǎn)都充當(dāng)過簇頭為止。每個(gè)簇采用不同的CDMA碼進(jìn)行通信,減少其他簇內(nèi)節(jié)點(diǎn)的干擾。

1.1.2 LEACH存在的問題

LEACH算法中選舉簇頭沒有考慮到節(jié)點(diǎn)剩余能量的問題,有可能使剩余能量低的節(jié)點(diǎn)當(dāng)選為簇頭,這就加速了節(jié)點(diǎn)的死亡。為了達(dá)到每個(gè)節(jié)點(diǎn)平均消耗能量的目標(biāo),必須滿足2個(gè)前提條件:(1)每個(gè)節(jié)點(diǎn)初始能量相等;(2)每個(gè)節(jié)點(diǎn)擔(dān)任簇頭期間消耗的能量相等。實(shí)際上,每個(gè)簇的大小以及簇頭到基站的距離都不一樣,條件(2)很難達(dá)到。其次,簇頭節(jié)點(diǎn)和基站直接通信使離基站遠(yuǎn)的簇頭節(jié)點(diǎn)加快了能量的消耗。在一些文獻(xiàn)中提出了采用多跳間接方式與基站通信,但該方法在選舉下一個(gè)鄰居節(jié)點(diǎn)時(shí)未考慮能量問題,這樣會(huì)使離基站較近的節(jié)點(diǎn)會(huì)因?yàn)橐D(zhuǎn)發(fā)大量其他節(jié)點(diǎn)的數(shù)據(jù)而首先死亡,從而影響了整個(gè)網(wǎng)絡(luò)的生命周期。

1.2 PEGASIS協(xié)議及其存在的問題

1.2.1 PEGASIS協(xié)議描述

PEGASIS協(xié)議借鑒了 LEACH協(xié)議中分簇算法的思想。PEGASIS的簇就是一條基于地理位置的鏈,所有的節(jié)點(diǎn)被組織成一個(gè)鏈。節(jié)點(diǎn)僅與它的鄰居節(jié)點(diǎn)通信,避免了LEACH簇的形成過程。除端節(jié)點(diǎn)外,每個(gè)節(jié)點(diǎn)將收到的數(shù)據(jù)與本地?cái)?shù)據(jù)進(jìn)行融合,然后再將融合后的數(shù)據(jù)沿鏈頭方向傳遞給相鄰節(jié)點(diǎn),這一過程一直持續(xù)到數(shù)據(jù)到鏈頭節(jié)點(diǎn),鏈頭節(jié)點(diǎn)負(fù)責(zé)將數(shù)據(jù)傳送到基站。PEGASIS與LEACH相比延長(zhǎng)了網(wǎng)絡(luò)的生命周期和能耗的均衡。

PEGASIS算法的核心思想是利用貪婪算法生成一條由所有節(jié)點(diǎn)組成的單鏈,類似于旅行商問題,是一個(gè)經(jīng)典的NP問題,算法假設(shè)節(jié)點(diǎn)通過定位裝置或者通過發(fā)送能量遞減的測(cè)試信號(hào)來發(fā)現(xiàn)距自己最近的鄰居節(jié)點(diǎn),然后從距基站最遠(yuǎn)的節(jié)點(diǎn)開始來構(gòu)造整條鏈。

1.2.2 PEGASIS存在的問題

盡管PEGASIS協(xié)議避免了動(dòng)態(tài)簇的形成過程,但PEGASIS算法仍然存在不足:(1)PEGASIS建鏈?zhǔn)腔谪澙匪惴?已經(jīng)加入鏈的節(jié)點(diǎn)和死亡節(jié)點(diǎn)都不能被再次訪問,因此長(zhǎng)鏈的形成是不可避免的,從而增加了數(shù)據(jù)傳輸?shù)难訒r(shí);(2)鏈頭采用輪轉(zhuǎn)擔(dān)任方式會(huì)使離基站遠(yuǎn)的節(jié)點(diǎn)率先死亡;(3)每一輪通信結(jié)束后都要重新選取鏈頭節(jié)點(diǎn),增加了通信開銷。

2 混合式協(xié)議提出

針對(duì)LEACH和PEGASIS協(xié)議存在的不足和只能用于規(guī)模小的無線傳感器網(wǎng)絡(luò)的缺陷。本文提出了一種混合式路由協(xié)議算法,即在每一個(gè)簇內(nèi)采用PEAGSIS算法形成各個(gè)簇的分鏈,并在每個(gè)分鏈中選取一個(gè)剩余能量多的充當(dāng)簇頭,每個(gè)簇頭不是直接和基站通信,而是采用一種新的基于距離能量的多跳達(dá)到基站的方法。

在本文的算法中,一個(gè)簇內(nèi)節(jié)點(diǎn)將采集到的數(shù)據(jù)按鏈的方法傳遞給簇頭節(jié)點(diǎn),和LEACH相比與簇頭直接通信的節(jié)點(diǎn)大量減少了,從而更好地節(jié)省了簇頭的能量、延長(zhǎng)了簇頭的生命。如果簇頭死亡,整個(gè)簇內(nèi)的節(jié)點(diǎn)將失去和基站通信的能力,需要重新選舉簇頭。

3 混合式算法的描述

和LEACH算法相同,每輪也包括兩個(gè)階段:(1)建立階段;(2)穩(wěn)定階段。建立階段主要的工作是簇和鏈的形成以及簇頭的選舉,所有節(jié)點(diǎn)必須保持同步以便在同一時(shí)間完成簇的建立過程。穩(wěn)定階段就是數(shù)據(jù)的傳輸階段。

3.1 建立階段

建立階段包括建立簇和建立鏈。LEACH算法在簇形成過程中沒有考慮到節(jié)點(diǎn)的能量,文獻(xiàn)[4]提出了改進(jìn)算法。本文采用集中式簇頭產(chǎn)生算法LEACH-C,每個(gè)節(jié)點(diǎn)將自己的剩余能量和地理位置報(bào)告給基站,基站計(jì)算平均能量,當(dāng)前能量低于平均能量的節(jié)點(diǎn)不能成為候選簇頭?；靖鶕?jù)所有成員節(jié)點(diǎn)到簇頭的距離平方和最小原則,采用模擬退火算法。最后,基站把簇頭集合和簇的結(jié)構(gòu)廣播出去。

針對(duì)PEGASIS算法可能產(chǎn)生一條長(zhǎng)鏈的問題,本文采用文獻(xiàn)[5]的方法來建立鏈。其思想是:簇內(nèi)的每個(gè)成員將自己的地理位置發(fā)給簇頭,簇頭采用模擬退火算法構(gòu)造鏈,避免了長(zhǎng)鏈的形成。

3.2 傳輸階段

簇內(nèi)成員節(jié)點(diǎn)接收到鄰居節(jié)點(diǎn)的信息,并和自己的信息進(jìn)行融合后在發(fā)送給下一個(gè)鄰居節(jié)點(diǎn),這個(gè)過程重復(fù)進(jìn)行直到達(dá)到簇頭節(jié)點(diǎn)為止。在傳輸過程中為了減少功率的消耗,每個(gè)節(jié)點(diǎn)都具有功率控制能力,能以最小的能量到達(dá)目的接收節(jié)點(diǎn)。

每一輪通信結(jié)束后,要進(jìn)行簇頭的重新選擇,這和LEACH每輪都有重新構(gòu)成簇不同,在LEACH中重組簇要消耗大量的能量。因此,為了減少簇形成過程的能量的消耗,我們采用的方法是在簇內(nèi)輪流選舉鏈頭,而不重組簇。這種方法能有效提高節(jié)點(diǎn)的能效。

4 距離能量多跳算法(D-E)

本文探討的是大規(guī)模無線傳感器網(wǎng)絡(luò)如何來降低節(jié)點(diǎn)能量的消耗。直接通過文獻(xiàn)[1]中簇頭和基站直接通信的方法,這就使得離基站遠(yuǎn)的節(jié)點(diǎn)提早的消耗掉能量而死亡。雖然有的文獻(xiàn)也給出了通過采用鄰居節(jié)點(diǎn)多跳的方法,但在選舉下一跳過程中并沒有考慮到節(jié)點(diǎn)剩余能量和該節(jié)點(diǎn)到BS的距離問題。本文所提出的距離能量多跳方法的算法思想如下:在選舉下一跳鄰居節(jié)點(diǎn)時(shí)考慮了節(jié)點(diǎn)的剩余能量Eresidual及節(jié)點(diǎn)到基站的距離Di。通過計(jì)算剩余能量Eresidual和距離Di的比值來進(jìn)行。如果當(dāng)前節(jié)點(diǎn)的比值小于選取鄰居節(jié)點(diǎn)的比值的話,我們就通過該鄰居節(jié)點(diǎn)傳輸數(shù)據(jù),依次采用同樣的方法,直到傳遞到基站。否則,當(dāng)前節(jié)點(diǎn)直接和基站通信。每個(gè)簇頭節(jié)點(diǎn)計(jì)算自己到基站的距離Di為

其中,(Xi,Yi)和(Xbs,Ybs)分別是節(jié)點(diǎn)i和基站的坐標(biāo),Eresidual-i是節(jié)點(diǎn)i的剩余能量。

5 仿真實(shí)驗(yàn)

5.1 仿真環(huán)境

仿真以NS2為平臺(tái),與 LEAC、HEED和 PEGASIS作比較,仿真參數(shù):網(wǎng)絡(luò)大小為 100 m×100 m,隨機(jī)生成200個(gè)傳感器節(jié)點(diǎn),基站位于坐標(biāo)(50,175)處,每個(gè)節(jié)點(diǎn)具有2 J的初始能量,每個(gè)節(jié)點(diǎn)接受或發(fā)送數(shù)據(jù)需要消耗Eelec=50 nJ/bit,ζamp=0.001 3 pJ/bit/m4,ζfs=10 pJ/bit/m2,每個(gè)數(shù)據(jù)包的大小固定為100 B,控制消息為25 B。所有節(jié)點(diǎn)一旦投放就不能再移動(dòng),節(jié)點(diǎn)死亡發(fā)生在能量為0時(shí)。

5.2 仿真結(jié)果

圖1顯示了節(jié)點(diǎn)存活量隨時(shí)間的變化情況,從圖中明顯看出,不論是第一個(gè)節(jié)點(diǎn)死亡的時(shí)間,還是最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間,本文算法都優(yōu)于其他3種。第一個(gè)節(jié)點(diǎn)死亡時(shí)間到最后一個(gè)節(jié)點(diǎn)死亡時(shí)間的跨度距離反映了網(wǎng)絡(luò)中的能量消耗均衡的情況。如果這個(gè)時(shí)間跨度的距離越短說明網(wǎng)絡(luò)能量使用率就越高。而 LEACH協(xié)議不僅簇首分配不均勻而且在選擇簇首時(shí)沒有考慮能量問題,使其部分節(jié)點(diǎn)較早死亡。PEGASIS協(xié)議將所有的節(jié)點(diǎn)組成一條鏈,有且僅有一個(gè)鏈?zhǔn)坠?jié)點(diǎn),如果鏈?zhǔn)纂x基站較遠(yuǎn),節(jié)點(diǎn)將要消耗掉大量的能量和基站通信。并且鏈?zhǔn)走x擇時(shí)也沒有考慮到剩余能量的問題;HEED協(xié)議簇間采用單跳的方式傳輸,所以節(jié)點(diǎn)的能量效率也低于提出的算法。

圖1 節(jié)點(diǎn)生存時(shí)間對(duì)比分析

結(jié)果表明,簇首消耗能量均衡的情況和簇首承載的負(fù)擔(dān)有直接關(guān)系,只有較好地均衡簇首的能量消耗,才能提高能量的使用效率,延長(zhǎng)網(wǎng)絡(luò)的生命周期。

在圖2顯示了前10輪簇首能量消耗的方差和時(shí)間的關(guān)系。從圖中可以看出提出的算法簇首能量消耗方差最小且最穩(wěn)定,有效地均衡了簇首的能量消耗,而 LEACH、PEGASIS和HEED協(xié)議方差均大于該算法且波動(dòng)也較明顯。

圖2 簇首消耗的能量方差對(duì)比

從以上仿真結(jié)果可以看出,本文算法在節(jié)點(diǎn)生存時(shí)間和簇首消耗能量方差上有一定優(yōu)勢(shì),主要是算法在簇間通信過程中大大減少了簇首直接和基站通信的個(gè)數(shù),大部分簇首節(jié)點(diǎn)只要和自己相鄰的節(jié)點(diǎn)通信,不僅減少了簇首的能量消耗,而且降低了整個(gè)網(wǎng)絡(luò)的能量消耗,從而延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間。

6 結(jié)語

針對(duì)LEACH能量消耗不均和PEGASIS產(chǎn)生的長(zhǎng)鏈加大了數(shù)據(jù)傳輸?shù)难訒r(shí),并由于2個(gè)算法本身的不足,往往只能用于小規(guī)模的無線傳感器網(wǎng)絡(luò)。本文給出了一個(gè)新的算法,通過混合這2種算法的優(yōu)點(diǎn),即在簇內(nèi)調(diào)節(jié)節(jié)點(diǎn)能量的消耗,節(jié)點(diǎn)將采集到的信息發(fā)送給它的鄰居節(jié)點(diǎn)而不是簇頭節(jié)點(diǎn),從而減少了成員節(jié)點(diǎn)的能量消耗。同時(shí)還提出了適用于大規(guī)模無線傳感器網(wǎng)絡(luò)的距離能量多跳路由算法。仿真表明,以上措施有效地平衡了節(jié)點(diǎn)能量消耗,延長(zhǎng)了網(wǎng)絡(luò)生存周期。

[1]Heinzelman A,Chandrakasan A,Balakrishnan.Energy-EfficeintCommunication Protocol forWireless Microsensor Networks[A].IEEE.Proceedings of the 33rd Hawaii conference on system sciences[C].Hawaii.Jan,2000:15-21.

[2]Stephanie Lindsey,S Cauligi.Raghavendra,PEGASIS:Power-Efficient Gathering in Sensor Information Systems[J].IEEE Aerospace and Electronic Systems Society,2002(3):1125-1130.

[3]趙芳芳,高媛.基于LEACH協(xié)議的無線傳感器網(wǎng)絡(luò)路由算法的改進(jìn)與仿真[J].電子測(cè)試,2011,3(3):47-49.

[4]Siva D M G,Ma D C F.A Centralized Energy-efficient Routing Protocol for Wireless Sensor Networks[J].IEEE Radio Communication,2005,43(3):660-669.

[5]胡森來,張昱,金心宇,等.基于遺傳算法的無線傳感網(wǎng)PEGASIS算法的改進(jìn)[J].江南大學(xué)學(xué)報(bào),Aug 2008,7(4):421-424.