無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議研究綜述

劉瓊

(1.湖南大學(xué)軟件學(xué)院,湖南長(zhǎng)沙 410082;2.湖南人文科技學(xué)院教務(wù)處,湖南婁底 417001)

無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議研究綜述

劉瓊1,2

(1.湖南大學(xué)軟件學(xué)院,湖南長(zhǎng)沙 410082;2.湖南人文科技學(xué)院教務(wù)處,湖南婁底 417001)

首先分析了無(wú)線傳感器網(wǎng)絡(luò)區(qū)別于傳統(tǒng)無(wú)線網(wǎng)絡(luò)的個(gè)性化特點(diǎn),然后從簇頭選舉、簇的形成和數(shù)據(jù)傳輸?shù)确矫娓爬藷o(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議的研究現(xiàn)狀,最后對(duì)無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議進(jìn)行了總結(jié)。

無(wú)線傳感器網(wǎng)絡(luò);節(jié)能;路由協(xié)議

作為新一代傳感器網(wǎng)絡(luò),無(wú)線傳感器網(wǎng)絡(luò) (W ireless SensorNetwork,WSN)的研究始于 1990年代末期。從 2000年起,國(guó)內(nèi)外的無(wú)線傳感器網(wǎng)絡(luò)研究日趨活躍,取得了很多

研究成果。由于無(wú)線傳感器網(wǎng)絡(luò)可以使人們?cè)谌魏螘r(shí)間、地點(diǎn)和任何環(huán)境下獲取大量可靠的信息,所以這已經(jīng)引起了世界上許多國(guó)家在軍事領(lǐng)域、工業(yè)領(lǐng)域和學(xué)術(shù)領(lǐng)域的極大關(guān)注。美國(guó)《商業(yè)周刊》認(rèn)為無(wú)線傳感器是全球未來(lái)四大新技術(shù)之一,是 21世紀(jì)世界最具有影響力的 21項(xiàng)技術(shù)之一。

本文從簇頭選舉、簇的形成、數(shù)據(jù)傳輸?shù)确矫娓爬四壳把芯空咴跓o(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議節(jié)能方面的相關(guān)研究,為進(jìn)一步研究無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議提供參考。

1 無(wú)線傳感器網(wǎng)絡(luò)特點(diǎn)

無(wú)線傳感器網(wǎng)絡(luò)是指一組傳感器節(jié)點(diǎn)被部署在監(jiān)測(cè)區(qū)域中,這些傳感器節(jié)點(diǎn)以無(wú)線通信方式形成一個(gè)自組織網(wǎng)絡(luò)系統(tǒng),它們協(xié)作的感知、采集并處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對(duì)象的信息,并發(fā)送給基站[1]。與傳統(tǒng)無(wú)線網(wǎng)絡(luò)相比它具有如下特點(diǎn):

1.1 自組織網(wǎng)絡(luò)

網(wǎng)絡(luò)的部署無(wú)需依賴(lài)任何預(yù)設(shè)的網(wǎng)絡(luò)設(shè)施,節(jié)點(diǎn)通過(guò)分層協(xié)議和分布式算法協(xié)調(diào)各自的行為,節(jié)點(diǎn)活躍狀態(tài)下可以快速、自動(dòng)地組成一個(gè)獨(dú)立的網(wǎng)絡(luò)。

1.2 動(dòng)態(tài)網(wǎng)絡(luò)

傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)由于各種因素而改變,如節(jié)點(diǎn)的電能耗盡或自然災(zāi)害等原因影響失效,各種條件的變化可能造成無(wú)線通信鏈路帶寬發(fā)生變化,甚至通信不穩(wěn)定,這些問(wèn)題要求傳感器網(wǎng)絡(luò)系統(tǒng)要能夠適應(yīng)這種變化,具有動(dòng)態(tài)系統(tǒng)可重構(gòu)性。

1.3 通信能力受限

傳感器節(jié)點(diǎn)的通信帶寬是有限的,通常僅有幾百 kbps。傳感器節(jié)點(diǎn)的通信范圍與無(wú)線電發(fā)送設(shè)備的發(fā)送信號(hào)強(qiáng)度、接收設(shè)備的接收能力及自然環(huán)境 (如山地,樹(shù)林)等干擾因素有關(guān)。

1.4 以數(shù)據(jù)為中心的網(wǎng)絡(luò)

互聯(lián)網(wǎng)中將網(wǎng)絡(luò)設(shè)備用唯一的 IP地址進(jìn)行標(biāo)識(shí),是一個(gè)以地址為中心的網(wǎng)絡(luò)。無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)是否編號(hào)取決于網(wǎng)絡(luò)通信協(xié)議的設(shè)計(jì),用戶使用無(wú)線傳感器網(wǎng)絡(luò)查詢事件時(shí),直接將所關(guān)心的事件通告給網(wǎng)絡(luò),網(wǎng)絡(luò)在獲得指定事件的信息后匯報(bào)給用戶。

1.5 電源能量有限

傳感器節(jié)點(diǎn)通常通過(guò)自身攜帶的電池供電,能量是非常有限的,由于傳感器節(jié)點(diǎn)的數(shù)量規(guī)模龐大,而且工作的環(huán)境非常復(fù)雜甚至有危險(xiǎn)的,通過(guò)人工更換電池的方式補(bǔ)給能量是不太現(xiàn)實(shí)的。

1.6 多跳路由

傳感器節(jié)點(diǎn)覆蓋在一定的區(qū)域外,因此節(jié)點(diǎn)之間采用多跳的通信方式來(lái)減少遠(yuǎn)距離傳輸能量消耗。

傳統(tǒng)的無(wú)線網(wǎng)絡(luò)首要目標(biāo)是提供高可靠性和更高的帶寬;而無(wú)線傳感器網(wǎng)絡(luò)存在能量受限的問(wèn)題,因此無(wú)線傳感器網(wǎng)絡(luò)路由設(shè)計(jì)大多把能耗最小化作為首要目標(biāo)。針對(duì)以上特點(diǎn),許多研究人員提出了很多高效節(jié)能的路由協(xié)議。

2 無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議研究綜述

LEACH[2]是最早提出的分簇路由協(xié)議,它的基本思想是:以循環(huán)的方式隨機(jī)選擇簇頭節(jié)點(diǎn),將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均到每個(gè)傳感器節(jié)點(diǎn),從而達(dá)到降低網(wǎng)絡(luò)能量耗費(fèi)、延長(zhǎng)網(wǎng)絡(luò)生命周期的目的。從LEACH執(zhí)行過(guò)程我們看出,每輪循環(huán)大致包括了三個(gè)階段:簇頭的產(chǎn)生、簇的形成和簇的路由。

簇頭的產(chǎn)生是簇形成的基礎(chǔ),簇的路由依賴(lài)于簇的結(jié)構(gòu)。它們是分簇路由協(xié)議設(shè)計(jì)的關(guān)鍵技術(shù),三者密切相關(guān),但也相對(duì)獨(dú)立。所有的無(wú)線傳感器分簇路由協(xié)議都是圍繞著如何選擇簇頭、如何成簇、如何進(jìn)行數(shù)據(jù)傳輸來(lái)考慮設(shè)計(jì)的[3]。

2.1 簇頭節(jié)點(diǎn)的優(yōu)化

LEACH采用分布式協(xié)議,算法簡(jiǎn)單,基本解決了負(fù)載平衡的問(wèn)題,但是簇頭分布不均,為此 Heinzelman作了改進(jìn) (LEACH-C)[4],它采用集中式協(xié)議,在成簇階段各節(jié)點(diǎn)將自身信息和剩余能量匯報(bào)給基站 (BS,Base Station),由BS根據(jù)各節(jié)點(diǎn)剩余能量占網(wǎng)絡(luò)總能量的比例等指標(biāo)進(jìn)行優(yōu)化運(yùn)算,選出合適的簇首。文獻(xiàn)[5]中引入了剩余能量,使能量消耗比例較低的節(jié)點(diǎn)優(yōu)先當(dāng)選簇頭,并且進(jìn)一步改進(jìn)了閾值大小,該算法綜合考慮了節(jié)點(diǎn)能量和閾值大小對(duì)簇頭選擇的影響,使能量更加均衡。

在 LEACH中簇頭的產(chǎn)生具有極大的隨機(jī)性,容易出現(xiàn)部分節(jié)點(diǎn)剩余能量相對(duì)較小但仍被選為簇頭,此時(shí)節(jié)點(diǎn)的能量會(huì)很快耗盡,成為“盲節(jié)點(diǎn)”的情況,張怡等人[6]提出了依據(jù)節(jié)點(diǎn)剩余能量的隨機(jī)數(shù)生成策略,該策略進(jìn)一步降低了剩余能量較小的節(jié)點(diǎn)成為簇頭的可能性,進(jìn)一步均衡網(wǎng)絡(luò)能量負(fù)載。在 CPRE協(xié)議[7]中,選擇剩余能量大于或等于平均能量且產(chǎn)生的隨機(jī)數(shù)小于閾值的節(jié)點(diǎn)為簇頭,并選取離基站較近且具有較高能量的簇頭作為中繼節(jié)點(diǎn),通過(guò)簇間轉(zhuǎn)發(fā)的方式將數(shù)據(jù)發(fā)送到基站。

張磊等人提出了 EDBCM協(xié)議[8],該協(xié)議選擇能量較高且距基站距離的平方較近的節(jié)點(diǎn)為最佳簇頭,進(jìn)一步降低數(shù)據(jù)轉(zhuǎn)發(fā)的能量損耗。文獻(xiàn)[9]中提出了基于低能量的雙簇頭路由分簇協(xié)議,該協(xié)議使能量最小的 K個(gè)節(jié)點(diǎn)盡可能地接近簇頭,同時(shí),在發(fā)送數(shù)據(jù)時(shí)在簇內(nèi)選擇能量較大且距離基站較近的節(jié)點(diǎn)作為 Data簇頭,通過(guò)雙簇頭的建立,進(jìn)一步均衡簇內(nèi)和簇間的通信消耗。

2.2 簇的形成

簇頭產(chǎn)生之后,廣播當(dāng)選的消息給周?chē)墓?jié)點(diǎn),周?chē)墓?jié)點(diǎn)根據(jù)收到的廣播信號(hào)強(qiáng)度來(lái)決定加入哪一個(gè)簇,這是大數(shù)協(xié)議常用的成簇方式。在成簇過(guò)程中,不少人綜合能量等因素來(lái)考慮簇的規(guī)模和負(fù)載均衡問(wèn)題,提出了不同的成簇方法。

在 PEGASIS協(xié)議[10]中,通過(guò)貪婪協(xié)議把節(jié)點(diǎn)組織成一條鏈,數(shù)據(jù)只在相鄰節(jié)點(diǎn)間進(jìn)行發(fā)送接收,每個(gè)節(jié)點(diǎn)在數(shù)據(jù)融合[11]后以最小的功率發(fā)送數(shù)據(jù),并且每輪中只選擇一個(gè)簇頭與基站通信。該協(xié)議沒(méi)有簇的重構(gòu)開(kāi)銷(xiāo),降低了能耗,但是節(jié)點(diǎn)之間由于數(shù)據(jù)的轉(zhuǎn)發(fā)有較大延時(shí)。EECS協(xié)議[12],綜合考慮了成員節(jié)點(diǎn)的能量與簇頭到基站的距離能量消耗,從而保證了簇頭的負(fù)載均衡。

馬玉剛等人提出了基于固定聚類(lèi)的節(jié)能算法[13],所有節(jié)點(diǎn)分為固定的聚類(lèi),聚類(lèi)內(nèi)節(jié)點(diǎn)自動(dòng)輪換擔(dān)任簇頭,通過(guò)減少聚類(lèi)區(qū)域內(nèi)節(jié)點(diǎn)之間的信息傳輸,從而減少不必要的能量消耗,更高效地傳送有用數(shù)據(jù),均衡了網(wǎng)絡(luò)負(fù)載。

以上分簇路由協(xié)議大都是基于均勻分簇的,傳感器節(jié)點(diǎn)間往往采用多跳方式進(jìn)行通信,一些節(jié)點(diǎn)既要發(fā)送數(shù)據(jù)也要轉(zhuǎn)發(fā)數(shù)據(jù)。同時(shí),數(shù)據(jù)流遵循多對(duì)一的模式,離基站較近的節(jié)點(diǎn)需要承擔(dān)更多的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)。因此這些節(jié)點(diǎn)容易過(guò)早耗盡自身的能量,導(dǎo)致在基站周?chē)霈F(xiàn)“能量空洞”(energy hole)現(xiàn)象。“能量空洞”現(xiàn)象的出現(xiàn)使整個(gè)網(wǎng)絡(luò)采集的數(shù)據(jù)不能進(jìn)一步傳送給基站節(jié)點(diǎn),此時(shí)網(wǎng)絡(luò)的生存周期提前結(jié)束,但是網(wǎng)絡(luò)中仍有大量較高能量的節(jié)點(diǎn)未被充分利用,基于此,李成法等人提出了 EEUC非均勻分簇協(xié)議[14],該協(xié)議分簇時(shí)使靠近基站的簇的規(guī)模小于遠(yuǎn)離基站的簇,使靠近基站的簇頭有更多的能量為簇間數(shù)據(jù)轉(zhuǎn)發(fā)使用,較好地避免了“能量空洞”的問(wèn)題。

2.3 簇的數(shù)據(jù)傳輸

無(wú)線傳感器網(wǎng)絡(luò)中,節(jié)點(diǎn)能量受限,節(jié)點(diǎn)的有效通信半徑也比較小。雖然可以通過(guò)調(diào)整發(fā)射功率來(lái)增大通信半徑,但由于隨著距離的逐漸變大,信號(hào)的空間損耗也迅速增大,因此,在分簇路由協(xié)議中一般采用多跳的傳輸方式來(lái)傳輸數(shù)據(jù)以達(dá)到節(jié)省能量的目的[15]。

但是,采用多跳傳輸方式并不是節(jié)點(diǎn)之間傳送數(shù)據(jù)采用多跳或是跳數(shù)越多越節(jié)能[16]。一些研究表明[17],節(jié)點(diǎn)距離基站較近時(shí),應(yīng)避免多跳路由機(jī)制,減少路由開(kāi)銷(xiāo),當(dāng)節(jié)點(diǎn)傳輸距離較大時(shí),在限制轉(zhuǎn)發(fā)距離和跳數(shù)的前提下,多跳傳輸策略能夠減少網(wǎng)絡(luò)的能量消耗。

目前無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議都是綜合考慮了以上一個(gè)或多個(gè)方面來(lái)延長(zhǎng)網(wǎng)絡(luò)的生命周期。在文獻(xiàn)[18]中,以剩余能量為參數(shù)限制簇頭多跳算法中間節(jié)點(diǎn)的選擇,由Pr im算法生成包括基站在內(nèi)的所有簇頭節(jié)點(diǎn)的最小生成樹(shù),在簇頭剩余能量滿足條件時(shí),使得簇間以最短距離進(jìn)行多跳通信。在 EEHCA協(xié)議[19]中,由基站根據(jù)節(jié)點(diǎn)剩余能量和簇頭之間的距離選舉簇頭,節(jié)點(diǎn)用單跳和多跳模式交替與簇頭進(jìn)行通信,從而使簇頭的分布更均勻,節(jié)點(diǎn)的負(fù)載更均衡。

3 結(jié)論

通過(guò)學(xué)者對(duì)當(dāng)前無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議的分析研究,可以看出一個(gè)好的無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議應(yīng)具備如下特點(diǎn):

3.1 節(jié)能

采用數(shù)據(jù)融合技術(shù),減少節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)不必要的控制信息,合理選擇多跳進(jìn)行遠(yuǎn)距離通信。

3.2 負(fù)載平衡

采用不均勻的分簇方式,避免靠近基站的節(jié)點(diǎn)過(guò)早的死亡,綜合考慮節(jié)點(diǎn)的剩余能量、與基站的距離以及最優(yōu)數(shù)據(jù)轉(zhuǎn)發(fā)路徑等因素,盡可能解決負(fù)載平衡的問(wèn)題。

[1]任豐原,黃海寧,林闖.無(wú)線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào),2003,14(7):1282-1291.

[2]HE INZELMAN W R,CHANDRAKASAN A,BALAKR ISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd hawaii International Conference on System Sciences.Washington,DC:IEEE Computer Society,2000:8020-8030.

[3]沈波,張世永,鐘亦平.無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].軟件學(xué)報(bào),2006,17(7):1588-1600.

[4]HE INZELMAN W R,CHANDRAKASAN A,BALAKR ISHNAN H.An application-specific protocol architecture forwirelessmicro-sensor networks[J].IEEE Transactions on W ireless Communications,2002,1(4):660-670.

[5]HANDYM J,HAASEM,T IMMERMANN D.Low energy adaptive clustering hierarchywith deterministic cluster-head selection[C]//In:Proc.of the 4th IEEE Conf.on Mobile and W ireless Communicatin Networks.Stockholm:IEEE communications Society,2002:368-372.

[6]張怡,李云,劉占軍,等.無(wú)線傳感器網(wǎng)絡(luò)中基于能量的簇頭選擇改進(jìn)算法[J].重慶郵電大學(xué)學(xué)報(bào),2007,19(5):613-616.

[7]龔本燦,李臘元,蔣廷耀,等.一種基于剩余能量的無(wú)線傳感器網(wǎng)絡(luò)分簇協(xié)議[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(8).

[8]張磊,陳曙.一個(gè)新的基于能量和距離的傳感器網(wǎng)絡(luò)協(xié)議[J].計(jì)算機(jī)應(yīng)用,2008,28(5):1117-1119.

[9]李輝,李臘元,李方云.一種基于低能量的雙簇首 WSN路由算法[J].武漢理工大學(xué)學(xué)報(bào):交通科學(xué)與工程版,2009,33(3):450-453.

[10]L INDSEY S,RAGHAVENDRA C S.PEGASIS:Powerful-efficient gathering in sensor infor mation systems[EB/OL].GregRichardson.Proceedings of IEEE Aerospace Conference of the IEEE Computer SocietyMT.2002:9-16.

[11]王娟,王汝傳,孫力娟.數(shù)據(jù)融合在傳感器網(wǎng)絡(luò)協(xié)議中的節(jié)能性分析[J].計(jì)算機(jī)技術(shù)與發(fā)展,2006,16(11):4-6.

[12]YeM,LiC F,Chen GH,et al.EECS:An energy efficient clustering scheme in wireless sensor networks[C]//In:Proc.of the IEEE Int’1 Performance Computing and Communications Conf.New York:IEEE Press,2005:535-540..

[13]馬玉剛,周群彪.基于 LEACH的無(wú)線傳感器網(wǎng)絡(luò)節(jié)能算法[J].計(jì)算機(jī)應(yīng)用,2009,29(6):1514-1516.

[14]李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)學(xué)報(bào),2007,30(1):27-36.

[15]ZHANG Wenya,L IANG Zize.Apower efficient routing protocol for wireless sensor network[C]//Proceedings of the 2007 IEEE International Conference on Networking,sensing and Control(ICNSCp07).Washington,DC:IEEE Computer Society,2007:20-25.

[16]ZHU Jin,PAPAVASS IL I OU S.On the energy-efficientorganization and the lifetime of multihop sensor networks[J].IEEE CommunicationsLetters,2003,7(11):537-539.

[17]尚鳳軍,雷陽(yáng).無(wú)線傳感器網(wǎng)絡(luò)能量有效成簇算法研究[J].小型微型計(jì)算機(jī)系統(tǒng),2009,30(5):839-842.

[18]王國(guó)芳,李臘元,李春林,等.無(wú)線傳感器網(wǎng)絡(luò)中基于能量約束的簇頭多跳算法[J].傳感技術(shù)學(xué)報(bào),2009,22(7):997-1001.

[19]劉述鋼,劉宏立,詹杰,等.無(wú)線傳感網(wǎng)絡(luò)中能耗均衡的混合通信算法研究[J].通信學(xué)報(bào),2009,30(1):12-17.

(責(zé)任編校:光明)

Research Summary on Cluster Routing Protocols in W ireless Sensor Network

LIU Q iong1,2

(1.College of Software,Hunan University,Changsha,410082,China;
2.Hunan Institute of Humanities,Science and Technology,Loudi,417001,China)

First compared with traditionalwireless network,the characteristics ofwireless sensor network are analyzed.Then cluster head election,cluster fornation and data transmission etc.are discussedwithin the framework of cluster routingprotocols in wireless sensor ne twork.Finally the development ofwireless sensor network router is summed up.

wireless sensor network;saving energy;routing protocol

TP393

A

1673-0712(2010)02-0024-03

2010-02-15.

劉瓊(1977-),男,湖南雙峰人,湖南人文科技學(xué)院助教,湖南大學(xué)軟件學(xué)院在讀碩士,研究方向:無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議。