一種空間查詢高效的無(wú)線傳感網(wǎng)絡(luò)路由協(xié)議*

聶云峰,王長(zhǎng)勝,陳崇毅

(南昌航空大學(xué)信息工程學(xué)院,南昌 330063)

?

一種空間查詢高效的無(wú)線傳感網(wǎng)絡(luò)路由協(xié)議*

聶云峰*,王長(zhǎng)勝,陳崇毅

(南昌航空大學(xué)信息工程學(xué)院,南昌 330063)

在以數(shù)據(jù)為中心的大規(guī)模無(wú)線傳感網(wǎng)絡(luò)中,感知數(shù)據(jù)查詢通常以空間查詢?yōu)橹?而感知節(jié)點(diǎn)攜帶能量極為有限,因此提高感知數(shù)據(jù)空間查詢能量利用效率尤為重要。GeoGrid協(xié)議是一種完全基于地理位置信息的路由協(xié)議,適用于大規(guī)模無(wú)線傳感網(wǎng)絡(luò)應(yīng)用場(chǎng)景,但其空間查詢效率較低。針對(duì)大規(guī)?？臻g查詢應(yīng)用場(chǎng)景,從成簇方式、簇首選舉、網(wǎng)絡(luò)拓?fù)鋵哟螛?gòu)建及路由策略等方面對(duì)GeoGrid進(jìn)行優(yōu)化,提出一種基于四叉樹(shù)結(jié)構(gòu)的空間查詢能量高效的無(wú)線傳感網(wǎng)絡(luò)路由協(xié)議——QuadGrid,并對(duì)GeoGrid、QTBDC及QuadGrid的空間查詢能耗進(jìn)行仿真分析。實(shí)驗(yàn)結(jié)果表明,與GeoGrid、QTBDC相比,QuadGrid網(wǎng)絡(luò)能耗更均衡,網(wǎng)絡(luò)生命周期更長(zhǎng),空間查詢更高效。

無(wú)線傳感網(wǎng)絡(luò);路由協(xié)議;空間查詢能量高效;四叉樹(shù)結(jié)構(gòu);GeoGrid;QuadGrid

無(wú)線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)是以數(shù)據(jù)為中心的網(wǎng)絡(luò),其目的是由各感知節(jié)點(diǎn)協(xié)作地感知、采集和處理監(jiān)測(cè)區(qū)域中感知對(duì)象的信息,并將信息發(fā)布給觀察者[1]。無(wú)線傳感網(wǎng)絡(luò)路由協(xié)議設(shè)計(jì)的首要目標(biāo)是能量高效[2]。在WSNs中,感知數(shù)據(jù)與時(shí)間和空間高度相關(guān),并且感知數(shù)據(jù)查詢以時(shí)空查詢?yōu)橹?而傳感器節(jié)點(diǎn)通常由電池供電,攜帶能量極為有限,在野外、戰(zhàn)場(chǎng)等特定環(huán)境下,受條件制約很難補(bǔ)充節(jié)點(diǎn)能量[3],因此,能量高效的空間查詢處理是目前亟需解決的問(wèn)題。

現(xiàn)階段WSN路由協(xié)議大體上可分為平面路由協(xié)議和分簇路由協(xié)議,平面路由協(xié)議不適用于大規(guī)模網(wǎng)絡(luò)[4],而分簇路由協(xié)議可以減少節(jié)點(diǎn)發(fā)送數(shù)據(jù)的距離和數(shù)據(jù)包碰撞次數(shù),此外經(jīng)過(guò)數(shù)據(jù)融合處理,分簇路由協(xié)議還能夠減少發(fā)送數(shù)據(jù)的長(zhǎng)度,從而極大地降低節(jié)點(diǎn)能耗[5]。分簇路由協(xié)議是一種基于分簇的層次路由協(xié)議,其引入分簇的思想,將網(wǎng)絡(luò)劃分為若干個(gè)簇(cluster),每個(gè)簇由一個(gè)簇首CH(Cluster Head)節(jié)點(diǎn)和多個(gè)簇內(nèi)成員CM(Cluster Member)節(jié)點(diǎn)組成,低一級(jí)網(wǎng)絡(luò)的簇首是高一級(jí)網(wǎng)絡(luò)中的簇內(nèi)成員,由最高層的簇頭與Sink節(jié)點(diǎn)或基站BS(Base Station)進(jìn)行通信[6]。分簇路由協(xié)議具有能耗較低、維護(hù)簡(jiǎn)單以及便于節(jié)點(diǎn)管理等特點(diǎn),適用于較大規(guī)模網(wǎng)絡(luò),經(jīng)典的分簇路由協(xié)議有LEACH、PEGASIS、HEED[7-9]等。根據(jù)簇的劃分是否均勻可將分簇路由協(xié)議劃分為均勻分簇路由協(xié)議和非均勻分簇路由協(xié)議。非均勻分簇成簇開(kāi)銷較大,各簇大小不等易造成不同簇的簇內(nèi)節(jié)點(diǎn)能耗不均,并且簇的不規(guī)則性會(huì)使簇間多跳路由變得更加復(fù)雜,不利于空間查詢。而均勻分簇則是把整個(gè)感知網(wǎng)絡(luò)劃分為多個(gè)大小基本相等的簇,簇內(nèi)節(jié)點(diǎn)數(shù)目相近,不同簇的簇內(nèi)節(jié)點(diǎn)在與本簇簇首節(jié)點(diǎn)進(jìn)行數(shù)據(jù)通信時(shí)的能量損耗基本均衡。經(jīng)典的均勻分簇路由協(xié)議有:GAF、Grid、GeoGrid[10-12]。相比于非均勻分簇路由協(xié)議,均勻分簇路由協(xié)議在節(jié)點(diǎn)及網(wǎng)絡(luò)能耗均衡性方面和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)方面具有天然的優(yōu)勢(shì),更加有利于空間查詢及提高網(wǎng)絡(luò)空間區(qū)域查詢能量利用效率。當(dāng)前,國(guó)內(nèi)關(guān)于均勻分簇路由協(xié)議空間查詢的研究相對(duì)較少。文獻(xiàn)[13]提出QTBDC,對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行編碼并在節(jié)點(diǎn)間建立起一個(gè)邏輯層次簇結(jié)構(gòu),然后利用各個(gè)子簇狀態(tài)數(shù)據(jù)的相似性和編碼的連續(xù)性,實(shí)現(xiàn)網(wǎng)內(nèi)無(wú)損聚合。該監(jiān)測(cè)機(jī)制使得網(wǎng)絡(luò)狀態(tài)信息的收集在不丟失數(shù)據(jù)細(xì)節(jié)信息的情況下,數(shù)據(jù)通信量大大減少。本文針對(duì)大規(guī)模無(wú)線傳感網(wǎng)絡(luò)空間查詢應(yīng)用場(chǎng)景,在GeoGrid的基礎(chǔ)上提出一種空間查詢能量高效的均勻分簇路由協(xié)議。

GeoGrid協(xié)議是一種基于地理位置信息的路由協(xié)議,適用于大規(guī)模無(wú)線傳感網(wǎng)絡(luò)應(yīng)用場(chǎng)景,但其空間查詢效率較低。針對(duì)大規(guī)模空間查詢應(yīng)用場(chǎng)景,從成簇方式、簇首選舉、網(wǎng)絡(luò)拓?fù)鋵哟螛?gòu)建及路由策略等方面對(duì)GeoGrid進(jìn)行優(yōu)化,提出一種基于四叉樹(shù)的空間查詢能量高效的無(wú)線傳感網(wǎng)絡(luò)路由協(xié)議——QuadGrid,并對(duì)GeoGrid、QTBDC及QuadGrid的空間查詢能耗進(jìn)行仿真分析。

1 GeoGrid簡(jiǎn)介

GeoGrid是基于Grid協(xié)議提出的一種完全基于地理位置信息的均勻分簇路由協(xié)議,將監(jiān)測(cè)區(qū)域均勻劃分為若干個(gè)大小相等的網(wǎng)格,單個(gè)網(wǎng)格內(nèi)的全部感知節(jié)點(diǎn)構(gòu)成一個(gè)簇,以網(wǎng)格內(nèi)距離網(wǎng)格中心最近的節(jié)點(diǎn)作為簇首,在數(shù)據(jù)傳輸過(guò)程中僅由簇首節(jié)點(diǎn)承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù),普通節(jié)點(diǎn)不參與數(shù)據(jù)轉(zhuǎn)發(fā)。

GeoGrid中簇首選擇是動(dòng)態(tài)的,當(dāng)簇首死亡或離開(kāi)本網(wǎng)格時(shí),簇內(nèi)隨即選取距離網(wǎng)格中心最近的節(jié)點(diǎn)作為新的簇首。網(wǎng)格劃分后,每個(gè)網(wǎng)格都被賦予一個(gè)與其在網(wǎng)絡(luò)中的位置相對(duì)應(yīng)的網(wǎng)格坐標(biāo)(x,y),如圖1中節(jié)點(diǎn)A、D所處的網(wǎng)格坐標(biāo)分別為(0,0)、(3,3)。當(dāng)有數(shù)據(jù)包需要轉(zhuǎn)發(fā)時(shí),GeoGrid將根據(jù)當(dāng)前網(wǎng)格坐標(biāo)與目的網(wǎng)格坐標(biāo)所體現(xiàn)的相對(duì)位置關(guān)系逐網(wǎng)格進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā),直至數(shù)據(jù)包到達(dá)目標(biāo)網(wǎng)格內(nèi)的目標(biāo)節(jié)點(diǎn)。

圖1 GeoGrid路由協(xié)議

在處理地域群播(Geocasting)問(wèn)題時(shí),GeoGrid利用源節(jié)點(diǎn)及目標(biāo)區(qū)域的位置信息來(lái)限制數(shù)據(jù)傳播區(qū)域,將洪泛區(qū)限制在包含源節(jié)點(diǎn)與目標(biāo)區(qū)域的最小矩形內(nèi),由位于洪泛區(qū)內(nèi)的簇首節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)轉(zhuǎn)發(fā)。

GeoGrid是比較成熟并且常用的均勻分簇路由協(xié)議,能夠在減少冗余數(shù)據(jù)傳輸?shù)耐瑫r(shí)提高數(shù)據(jù)傳輸成功率,適用于地域群播應(yīng)用場(chǎng)景,但是GeoGrid在以下5個(gè)方面仍存在不足:①網(wǎng)格劃分方法不夠靈活,沒(méi)有充分考慮到實(shí)際應(yīng)用需求;②采用三維坐標(biāo)(x,y,id)(其中x和y分別為節(jié)點(diǎn)所在網(wǎng)格的橫縱坐標(biāo),id為節(jié)點(diǎn)的簇內(nèi)標(biāo)識(shí))來(lái)標(biāo)識(shí)感知節(jié)點(diǎn)位置信息,在數(shù)據(jù)傳輸過(guò)程中消耗較多能量;③在簇首選舉上未考慮節(jié)點(diǎn)的剩余能量因素,其簇首選取與更換方式易導(dǎo)致各節(jié)點(diǎn)能耗不均衡,從而易導(dǎo)致部分節(jié)點(diǎn)過(guò)早死亡;④在下一跳路由節(jié)點(diǎn)的選取上未考慮節(jié)點(diǎn)剩余能量因素,易導(dǎo)致能量空洞[14](Energy Hole)問(wèn)題;⑤其網(wǎng)絡(luò)拓?fù)鋵哟谓Y(jié)構(gòu)不利于高效的空間查詢。

本文主要針對(duì)上述問(wèn)題,對(duì)GeoGrid協(xié)議進(jìn)行改進(jìn),提出一種網(wǎng)絡(luò)層次更分明、能耗更均衡、網(wǎng)絡(luò)生命周期更長(zhǎng)并且空間查詢更加高效的QuadGrid路由協(xié)議。QuadGrid協(xié)議從以下4個(gè)方面對(duì)GeoGrid進(jìn)行改進(jìn):①采用新的網(wǎng)絡(luò)劃分方法,根據(jù)實(shí)際應(yīng)用需求,對(duì)網(wǎng)絡(luò)覆蓋區(qū)域進(jìn)行四叉樹(shù)層次劃分,在相應(yīng)網(wǎng)絡(luò)層次增加管理節(jié)點(diǎn)對(duì)感知數(shù)據(jù)做進(jìn)一步融合以進(jìn)一步減少冗余數(shù)據(jù)傳輸,從而有效降低網(wǎng)絡(luò)中數(shù)據(jù)傳輸能耗,此外四叉樹(shù)層次結(jié)構(gòu)更加有利于路由維護(hù)以及感知數(shù)據(jù)時(shí)空查詢;②對(duì)網(wǎng)格簇進(jìn)行四叉樹(shù)Morton[15]編碼,利用一維二進(jìn)制數(shù)來(lái)表達(dá)節(jié)點(diǎn)標(biāo)識(shí)信息,減少數(shù)據(jù)冗余,進(jìn)一步降低節(jié)點(diǎn)及網(wǎng)絡(luò)數(shù)據(jù)傳輸能耗;③在簇首節(jié)點(diǎn)選取上,綜合考慮節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)與簇中心位置的距離及節(jié)點(diǎn)與周圍8個(gè)鄰居簇首的距離等3個(gè)方面的因素,以均衡簇內(nèi)節(jié)點(diǎn)能量損耗,進(jìn)一步延長(zhǎng)網(wǎng)絡(luò)生命周期;④在下一跳目標(biāo)簇首的選擇上綜合考慮節(jié)點(diǎn)剩余能量及數(shù)據(jù)傳輸距離兩方面因素,從而降低出現(xiàn)能量空洞的可能性并提高數(shù)據(jù)通信成功率。

2 QuadGrid協(xié)議

2.1 簇的劃分與編碼

與GeoGrid不同,QuadGrid協(xié)議采用基于二進(jìn)制Morton碼(簡(jiǎn)稱M碼)的編碼方法對(duì)網(wǎng)格進(jìn)行四叉樹(shù)編碼,簇劃分與編碼的具體過(guò)程如下:

①擴(kuò)展監(jiān)測(cè)區(qū)域

定義完全覆蓋監(jiān)測(cè)區(qū)域并且Sink節(jié)點(diǎn)位于網(wǎng)絡(luò)正中心的最小正方形GridBond,定義此正方形邊長(zhǎng)為L(zhǎng)。

圖2 監(jiān)測(cè)區(qū)域四叉樹(shù)層次劃分

②劃分監(jiān)測(cè)區(qū)域

區(qū)域四叉樹(shù)[16]RQT(Region Quadtrees)是一種典型的樹(shù)形層次結(jié)構(gòu),QuadGrid依據(jù)區(qū)域四叉樹(shù)層次遞歸分解的原理,將GridBond作為RQT的根區(qū)域,對(duì)根區(qū)域進(jìn)行四等分操作,將監(jiān)測(cè)區(qū)域分割成4個(gè)大小相等的方形子區(qū)域,分別表示為01(NW)、11(NE)、00(SW)、10(SE)(如圖2所示),然后再分別對(duì)上述4個(gè)子區(qū)域進(jìn)行四等分操作,接下來(lái)再分別對(duì)子區(qū)域迭代進(jìn)行四等份分割直至整個(gè)GridBond區(qū)域被劃分成4Z(Z≥0)個(gè)大小相等的葉子節(jié)點(diǎn),Z為根據(jù)實(shí)際應(yīng)用需求(如感知數(shù)據(jù)空間分辨率)確定的四叉樹(shù)深度,葉子節(jié)點(diǎn)代表用戶感興趣的最小網(wǎng)格區(qū)域,如圖2中陰影區(qū)域所示。

位于同一個(gè)網(wǎng)格內(nèi)的所有感知節(jié)點(diǎn)構(gòu)成一個(gè)簇,網(wǎng)絡(luò)劃分后的網(wǎng)格邊長(zhǎng)l與GridBond邊長(zhǎng)L之間滿足如下關(guān)系:

l=L/2Z

(1)

③對(duì)網(wǎng)格進(jìn)行M碼編碼

網(wǎng)格劃分后,GeoGrid利用網(wǎng)格的行列號(hào)(m,n)來(lái)表示網(wǎng)格位置,m為行號(hào),n為列號(hào),如圖3左下角網(wǎng)格位置表示為(0,0),右上角網(wǎng)格位置為(7,7),而QuadGrid則是在此在基礎(chǔ)上進(jìn)一步采用Morton碼對(duì)網(wǎng)格進(jìn)行編碼,將二維的網(wǎng)格行列信息通過(guò)比特交叉映射成一個(gè)二進(jìn)制數(shù),編碼完成后網(wǎng)格的M碼以及感知節(jié)點(diǎn)的簇內(nèi)id共同組成節(jié)點(diǎn)標(biāo)識(shí)號(hào)。節(jié)點(diǎn)標(biāo)識(shí)號(hào)占用16個(gè)比特,其中感知節(jié)點(diǎn)的簇內(nèi)id占用16-2Z低位比特,網(wǎng)格M碼為高位的2Z比特,M碼中每?jī)晌槐忍卮硐鄳?yīng)層次的子區(qū)域,以“010110”為例,頭兩位“01”表示網(wǎng)絡(luò)區(qū)域的左上部分的子區(qū)域,中間兩位“01”代表該子區(qū)域的左上部分的次級(jí)子區(qū)域,最后兩位“10”表示次級(jí)子區(qū)域的右下部分的網(wǎng)格,如圖2陰影區(qū)域所示。

與GeoGrid利用三元組標(biāo)識(shí)感知節(jié)點(diǎn)相比,QuadGrid利用一維節(jié)點(diǎn)序列號(hào)標(biāo)識(shí)感知節(jié)點(diǎn),可在一定程度上減少數(shù)據(jù)占用空間,從而能夠降低感知節(jié)點(diǎn)數(shù)據(jù)傳輸能耗。監(jiān)測(cè)區(qū)域M碼編碼如圖3所示。

圖3 網(wǎng)格的Morton編碼圖

④計(jì)算節(jié)點(diǎn)通信半徑R

圖4 QuadGrid節(jié)點(diǎn)通信半徑

2.2 簇首選舉及父簇首選擇

簇首選舉在分簇算法中起著關(guān)鍵作用,GeoGrid協(xié)議選擇離網(wǎng)格中心位置最近的節(jié)點(diǎn)作為簇首,節(jié)點(diǎn)一旦當(dāng)選簇首將持續(xù)工作直到剩余能量達(dá)到最小存活閾值為止,簇內(nèi)才會(huì)重新選舉簇首,這種簇首選擇方式?jīng)]有考慮到各節(jié)點(diǎn)的負(fù)載均衡,易導(dǎo)致部分簇首因負(fù)載過(guò)重而過(guò)早死亡。QuadGrid在簇首選舉初始階段也選取距離網(wǎng)格中心位置最近的節(jié)點(diǎn)作為簇首,但在重新選取簇首時(shí)綜合考慮節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)與網(wǎng)格中心的距離及節(jié)點(diǎn)與周圍8個(gè)鄰居簇簇首的距離等3方面因素。以CH為節(jié)點(diǎn)的簇首競(jìng)選因子,選取簇內(nèi)CH值最小的節(jié)點(diǎn)作為簇首,CH值的計(jì)算如下:

(2)

式中:α、β、γ為平衡系數(shù),α+β+γ=1且α>0,β>0,γ>0;Ecurrent i為候選簇首節(jié)點(diǎn)當(dāng)前剩余能量;Einitial i為該節(jié)點(diǎn)的初始能量;∑D為該節(jié)點(diǎn)與其所屬網(wǎng)格的周圍8個(gè)鄰居網(wǎng)格簇簇首節(jié)點(diǎn)的距離之和;d為該節(jié)點(diǎn)到其所屬網(wǎng)格中心的距離;l為網(wǎng)格邊長(zhǎng)。

Sink節(jié)點(diǎn)以Ts為時(shí)間間隔周期性向網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)廣播簇首選舉的消息,各簇節(jié)點(diǎn)接收到消息后,開(kāi)始新一輪簇首選舉。簇內(nèi)某一節(jié)點(diǎn)當(dāng)選為簇首后向簇內(nèi)節(jié)點(diǎn)及周圍鄰居簇廣播當(dāng)選消息,簇內(nèi)成員節(jié)點(diǎn)接收消息后記錄該簇首信息,周圍鄰居簇首節(jié)點(diǎn)接收消息后在各自鄰居表中記錄該簇首信息。

QuadGrid協(xié)議中每經(jīng)過(guò)一次簇首選舉,性能較差的簇首節(jié)點(diǎn)會(huì)被新的綜合性能最優(yōu)的節(jié)點(diǎn)所取代,因而可以在有效避免簇首節(jié)點(diǎn)過(guò)早死亡的同時(shí)均衡簇內(nèi)節(jié)點(diǎn)能量損耗,從而能夠在一定程度上延長(zhǎng)節(jié)點(diǎn)乃至整個(gè)網(wǎng)絡(luò)的生命周期。

文獻(xiàn)[17]指出,有效的網(wǎng)絡(luò)拓?fù)淇刂平Y(jié)構(gòu)能夠?yàn)槠渌W(wǎng)絡(luò)服務(wù)支持技術(shù)提供基礎(chǔ),提高網(wǎng)絡(luò)通信協(xié)議的應(yīng)用效率,同時(shí)有利于延長(zhǎng)網(wǎng)絡(luò)的生命周期。QuadGrid采用基于四叉樹(shù)的拓?fù)鋵哟谓Y(jié)構(gòu),在相應(yīng)四叉樹(shù)層次增加管理節(jié)點(diǎn),除Sink節(jié)點(diǎn)外,每層簇首節(jié)點(diǎn)都有一個(gè)父簇首節(jié)點(diǎn)(簡(jiǎn)稱父節(jié)點(diǎn)),父節(jié)點(diǎn)負(fù)責(zé)收集其4個(gè)子簇首節(jié)點(diǎn)(簡(jiǎn)稱子節(jié)點(diǎn))匯報(bào)上來(lái)的感知數(shù)據(jù),并將收集到的數(shù)據(jù)進(jìn)行融合然后發(fā)送給其自身的父節(jié)點(diǎn)。為簡(jiǎn)化算法,QuadGrid在4個(gè)子節(jié)點(diǎn)中選擇所屬網(wǎng)格距離Sink節(jié)點(diǎn)最近的子節(jié)點(diǎn)作為這4個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)。在該算法中網(wǎng)絡(luò)中某一簇首節(jié)點(diǎn)僅根據(jù)其節(jié)點(diǎn)標(biāo)識(shí)號(hào)就可以計(jì)算出其各級(jí)父節(jié)點(diǎn)所在簇的M碼,因而不需簇首之間進(jìn)行額外通信協(xié)商。

父簇首節(jié)點(diǎn)選擇算法:

getFatherNode_MC(nodeMC md,leveli,treeDepthd){

begin

//md為感知節(jié)點(diǎn)序列號(hào),i為父節(jié)點(diǎn)的層

//次級(jí)別并且(1≤i

//將節(jié)點(diǎn)序列號(hào)低位16-2(d-i)比特清零,保留高位2(d-i)比特

md1=(md?16-2(d-i))?16-2(d-i);

//截取網(wǎng)格M碼前兩位,按位取返后作為

//網(wǎng)格M碼后兩位

md2=(～md?14)?(16-2d)

for(intj=1;j

begin

md2=md2+(md2?2);

end

fmd=md1+md2;

//fmd為當(dāng)前簇首節(jié)點(diǎn)指定層次級(jí)別的

//父節(jié)點(diǎn)所在網(wǎng)格的M碼

return fmd;

end

}

2.3 路由選擇

QuadGrid的路由過(guò)程是根據(jù)父簇首節(jié)點(diǎn)算法,計(jì)算出各簇首在四叉樹(shù)結(jié)構(gòu)中相應(yīng)層次的父節(jié)點(diǎn),底層簇首經(jīng)由其對(duì)應(yīng)的各級(jí)父節(jié)點(diǎn)向Sink節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù),由父節(jié)點(diǎn)對(duì)數(shù)據(jù)包做進(jìn)一步融合處理,同時(shí),在空間距離較遠(yuǎn)的父節(jié)點(diǎn)之間采取逐網(wǎng)格傳輸方式進(jìn)行數(shù)據(jù)傳輸。具體而言,底層感知節(jié)點(diǎn)將采集到的感知數(shù)據(jù)直接發(fā)送給其所屬的簇首節(jié)點(diǎn)(即第0級(jí)父節(jié)點(diǎn)),第0級(jí)父節(jié)點(diǎn)對(duì)感知數(shù)據(jù)進(jìn)行融合后采用逐網(wǎng)格傳輸方式將數(shù)據(jù)發(fā)送給第1級(jí)父節(jié)點(diǎn),第1級(jí)父節(jié)點(diǎn)采取同樣方式將數(shù)據(jù)發(fā)送給第2級(jí)父節(jié)點(diǎn),迭代此過(guò)程直到感知數(shù)據(jù)到達(dá)第Z-1級(jí)父節(jié)點(diǎn),然后再由第Z-1級(jí)父節(jié)點(diǎn)直接將感知數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn)。

GeoGrid在下一跳中間節(jié)點(diǎn)的選擇上僅考慮中間節(jié)點(diǎn)與Sink節(jié)點(diǎn)的距離因素而沒(méi)有考慮到下一跳簇首節(jié)點(diǎn)剩余能量因素,易導(dǎo)致能量空洞問(wèn)題。QuadGrid對(duì)此進(jìn)行了優(yōu)化,當(dāng)前父節(jié)點(diǎn)在選擇下一級(jí)中間簇首時(shí),首先將路由區(qū)域限制在包含當(dāng)前父節(jié)點(diǎn)所在網(wǎng)格以及下一級(jí)父節(jié)點(diǎn)所在網(wǎng)格的最小矩形內(nèi)(如圖5陰影區(qū)域所示),然后綜合考慮候選中間簇首節(jié)點(diǎn)的剩余能量以及當(dāng)前父節(jié)點(diǎn)經(jīng)候選簇首到下一級(jí)父節(jié)點(diǎn)的距離等兩方面因素,選擇下一級(jí)路由選擇因子NHop值最小的候選簇首作為下一級(jí)中間簇首節(jié)點(diǎn),具體步驟如下:

①計(jì)算當(dāng)前父節(jié)點(diǎn)經(jīng)候選簇首到下一級(jí)父節(jié)點(diǎn)的距離

圖5 QuadGrid路由協(xié)議

②計(jì)算下一級(jí)路由選擇因子NHop

綜合考慮距離與節(jié)點(diǎn)剩余能量?jī)煞矫嬉蛩?給出第i個(gè)鄰居簇首的選擇因子NHopi的計(jì)算公式:

式中:λ和μ為平衡系數(shù),λ+μ=1且λ>0、μ>0;Lmax為L(zhǎng)2、L3及L4中的最大值;pi=Ecurrent i/Einitial i,Ecurrent i為當(dāng)前簇首剩余能量,Einitial i為當(dāng)前簇首初始能量。當(dāng)簇首D需要進(jìn)行數(shù)據(jù)傳輸時(shí),其位于路由限制區(qū)內(nèi)的鄰居簇首E、H和I將分別計(jì)算各自的NHop值,簇首D將選取其中NHop值最小的簇首為下一跳路由節(jié)點(diǎn)。各級(jí)中間簇首節(jié)點(diǎn)將采取相同方式選取各自的下一跳節(jié)點(diǎn),直至所需傳輸?shù)臄?shù)據(jù)分組到達(dá)目標(biāo)父節(jié)點(diǎn)G,圖5中所示D到Sink節(jié)點(diǎn)的路徑為D→E→F→G→Sink。

圖6 數(shù)據(jù)轉(zhuǎn)發(fā)區(qū)域

2.4 空間查詢

①Sink節(jié)點(diǎn)向待查詢區(qū)域感知節(jié)點(diǎn)發(fā)送查詢請(qǐng)求數(shù)據(jù)包

與GeoGrid類似,當(dāng)需要查詢某一空間區(qū)域的感知數(shù)據(jù)時(shí),QuadGrid采用限制區(qū)域的洪泛方式向查詢窗口廣播查詢請(qǐng)求數(shù)據(jù)包(如圖6所示),具體算法如下:

//X為接收查詢請(qǐng)求數(shù)據(jù)包的感知節(jié)點(diǎn),查詢請(qǐng)

//求包包含字段(G,R,id),其中G為完全包含查

//詢窗口的最小矩形,R為包含節(jié)點(diǎn)與G的最小

//矩形,id為查詢請(qǐng)求包id

ReceiveQueryRequestPackage(G,R,id){

begin

if(X位于R區(qū)域內(nèi))

thenbegin

if(X為簇首節(jié)點(diǎn))

begin

//判斷X是否接收過(guò)當(dāng)前請(qǐng)求包

if(packageId==id)

begin

Step1.X直接刪除接收到的數(shù)據(jù)包.

end

elsebegin

Step1.X向鄰居簇首節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢請(qǐng)求包.

if(X位于G區(qū)域內(nèi))

begin

Step1.X向其所轄簇內(nèi)成員節(jié)點(diǎn)發(fā)送數(shù)據(jù)包.

end

end

end

end

elsebegin

Step1.X直接刪除接收到的數(shù)據(jù)包.

end

end

}

②感知節(jié)點(diǎn)向Sink節(jié)點(diǎn)反饋感知數(shù)據(jù)

QuadGrid中,查詢窗口內(nèi)的簇首節(jié)點(diǎn)向Sink節(jié)點(diǎn)反饋感知數(shù)據(jù)時(shí),由各層父節(jié)點(diǎn)負(fù)責(zé)收集、融合并轉(zhuǎn)發(fā)監(jiān)測(cè)區(qū)域內(nèi)的監(jiān)測(cè)數(shù)據(jù),具體算法如下:

//假定X為查詢窗口內(nèi)的感知節(jié)點(diǎn),queryWindow為

//查詢窗口;rendezvousLevel表示的是父簇首節(jié)點(diǎn)的

//層次級(jí)別0≤rendezvousLevel

//rendezvousLevel為整數(shù);treeDepth表示四叉樹(shù)的深度。

GetDataByRegion(queryWindow,rendezvousLevel,treeDepth){

begin

if(X不為簇首節(jié)點(diǎn))

then

begin

Step1.獲取數(shù)據(jù);

Step2.將數(shù)據(jù)發(fā)送給X所屬簇首節(jié)點(diǎn);

end

//如果X為第0～treeDepth-2級(jí)父簇首節(jié)點(diǎn)

elseif(0≤rendezvousLevel

then

begin

//對(duì)收集到的感知數(shù)據(jù)進(jìn)行融合;

Step1.fuseReceivedData();

//通過(guò)父簇首節(jié)點(diǎn)選擇算法計(jì)算出X的父簇首節(jié)點(diǎn);

Step2.getRendezvousNode();

Step3.X通過(guò)式及式計(jì)算出到達(dá)父簇首節(jié)點(diǎn)

的下一跳中間節(jié)點(diǎn)M,將融合后的數(shù)據(jù)包轉(zhuǎn)

發(fā)給M,并由M繼續(xù)承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)。

end

//如果X為第treeDepth-1級(jí)父簇首節(jié)點(diǎn)

else

begin

Step1.fuseReceivedData();

Step2.X直接通過(guò)簇間通信將融合后的數(shù)據(jù)轉(zhuǎn)發(fā)給Sink節(jié)點(diǎn);

end

end

}

3 QuadGrid仿真結(jié)果分析

3.1 能耗模型

數(shù)據(jù)通信是無(wú)線傳感網(wǎng)絡(luò)最為耗能的部分,與之相比較,傳感器節(jié)點(diǎn)運(yùn)算和存儲(chǔ)所需要的能量基本可忽略不計(jì)。因此,無(wú)線傳感網(wǎng)絡(luò)生存時(shí)間的長(zhǎng)短主要取決于數(shù)據(jù)傳輸消耗能量的大小。

本文采用文獻(xiàn)[18]中的一階無(wú)線模型(firstorderradiomodel)來(lái)計(jì)算節(jié)點(diǎn)發(fā)送和接收能耗。在該能耗模型中,節(jié)點(diǎn)發(fā)送能耗與傳播距離的平方成正比,將k比特?cái)?shù)據(jù)傳送距離d,發(fā)送節(jié)點(diǎn)能為ETx=ETx(k,d)=Eeleck+εampkd2,接收節(jié)點(diǎn)能耗為ERx=ERx(k,d)=Eeleck,其中Eelec是發(fā)送接收電路的能耗系數(shù),εamp是傳輸放大器為保證數(shù)據(jù)可靠傳輸所需的能耗系數(shù)。

3.2 實(shí)驗(yàn)參數(shù)設(shè)置

表1 實(shí)驗(yàn)參數(shù)

3.3 仿真結(jié)果及分析

本文采用由美國(guó)加州大學(xué)LBL網(wǎng)絡(luò)研究組研發(fā)的網(wǎng)絡(luò)仿真工具NS2[19](NetworkSimulatorversion2)從網(wǎng)絡(luò)平均能耗、網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)量及空間查詢能耗等3個(gè)方面對(duì)QuadGrid、GeoGrid及QTBDC進(jìn)行仿真分析。

圖7 網(wǎng)絡(luò)平均耗能對(duì)比

實(shí)驗(yàn)一對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)向Sink節(jié)點(diǎn)發(fā)送數(shù)據(jù)的平均能耗及平均節(jié)點(diǎn)存活數(shù)目進(jìn)行仿真,網(wǎng)絡(luò)中初始節(jié)點(diǎn)數(shù)目為400,柵格分辨率Z=3,各簇首節(jié)點(diǎn)向Sink節(jié)點(diǎn)發(fā)送感知數(shù)據(jù),每10輪簇內(nèi)重新進(jìn)行一次簇首選舉,仿真結(jié)果分別如圖7及圖8所示。

圖8 網(wǎng)絡(luò)中節(jié)點(diǎn)存活數(shù)

由圖7可知,QuadGrid的平均能耗低于GeoGrid及QTBDC,而且能量消耗速率更加平穩(wěn),這是由于采用了簇首節(jié)點(diǎn)輪換機(jī)制,簇內(nèi)節(jié)點(diǎn)能量損耗更加均衡,同時(shí)還采用數(shù)據(jù)融合技術(shù),減少了冗余數(shù)據(jù)的傳播,從而能夠避免部分簇首節(jié)點(diǎn)因負(fù)載過(guò)重而過(guò)早死亡,進(jìn)而能夠有效節(jié)省網(wǎng)絡(luò)總能耗。圖8表明,同GeoGrid及QTBDC相比,QuadGrid存活節(jié)點(diǎn)數(shù)目更多、網(wǎng)絡(luò)生命周期更長(zhǎng),與QTBDC相比網(wǎng)絡(luò)存活時(shí)間延長(zhǎng)7%,與GeoGrid相比則存活時(shí)間延長(zhǎng)16.7%,此外QuadGrid第1個(gè)簇首死亡時(shí)間遠(yuǎn)遠(yuǎn)遲于GeoGrid及QTBDC,能夠在很大程度上確保感知數(shù)據(jù)的可靠性。實(shí)驗(yàn)二對(duì)三者的空間查詢能耗進(jìn)行仿真,仿真結(jié)果如圖9所示。由圖9可知,QuadGrid的空間查詢能耗低于GeoGrid及QTBDC,能耗低于GeoGrid是因?yàn)楦骷?jí)父簇首節(jié)點(diǎn)對(duì)查詢窗口內(nèi)的簇首節(jié)點(diǎn)發(fā)送過(guò)來(lái)的感知數(shù)據(jù)進(jìn)行再融合,大大降低了冗余數(shù)據(jù)傳輸能耗,能耗低于QTBDC則是由于采用了簇頭輪換機(jī)制及下一跳路由選舉機(jī)制,增加了網(wǎng)絡(luò)中節(jié)點(diǎn)的負(fù)載均衡性,此外,當(dāng)查詢窗口覆蓋一個(gè)網(wǎng)格時(shí),三者查詢能耗幾乎相等,但是隨著查詢窗口覆蓋范圍的增大,QuadGrid相對(duì)GeoGrid及QTBDC節(jié)省能耗的幅度變得越來(lái)越大,其中相對(duì)于QTBDC空間查詢能耗減少5.7%～8.6%,相對(duì)于GeoGrid空間查詢能耗減少12%～27%。

圖9 空間區(qū)域查詢平均能耗對(duì)比

4 結(jié)論

本文提出一種基于四叉樹(shù)的均勻分簇路由協(xié)議QuadGrid,從成簇方式、簇首選舉、網(wǎng)絡(luò)拓?fù)鋵哟螛?gòu)建及路由策略等方面對(duì)GeoGrid協(xié)議進(jìn)行了改進(jìn)。首先,在簇的劃分方面,采用四叉樹(shù)層次結(jié)構(gòu)將監(jiān)測(cè)區(qū)域劃分若干個(gè)大小相等的正方形網(wǎng)格,并采用二進(jìn)制Morton碼對(duì)網(wǎng)格進(jìn)行編碼,將二進(jìn)制的網(wǎng)格位置信息映射成一維的二進(jìn)制數(shù),在一定程度上減少數(shù)據(jù)占用空間。然后,在簇首節(jié)點(diǎn)選舉時(shí)綜合考慮節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)與其所屬網(wǎng)格中心的距離以及節(jié)點(diǎn)與其周圍鄰居簇首進(jìn)行數(shù)據(jù)通信的距離等因素,使網(wǎng)絡(luò)具有更好的負(fù)載平衡度,同時(shí)選擇出簇首節(jié)點(diǎn)的各級(jí)父簇首節(jié)點(diǎn),由父簇首節(jié)點(diǎn)負(fù)責(zé)維護(hù)四叉樹(shù)結(jié)構(gòu)以及對(duì)數(shù)據(jù)作進(jìn)一步融合以減少冗余數(shù)據(jù)在網(wǎng)絡(luò)中的傳播。最后,在下一跳路由節(jié)點(diǎn)選擇方面綜合考慮節(jié)點(diǎn)剩余能量和數(shù)據(jù)傳輸距離兩方面因素,使節(jié)點(diǎn)及整個(gè)網(wǎng)絡(luò)能量損耗更均衡。QuadGrid不需增加額外硬件設(shè)施,對(duì)網(wǎng)絡(luò)平均能耗、網(wǎng)絡(luò)存活時(shí)間以及區(qū)域查詢能耗進(jìn)行仿真分析,實(shí)驗(yàn)結(jié)果表明,QuadGrid協(xié)議能夠在延長(zhǎng)網(wǎng)絡(luò)生命周期的同時(shí)還能夠有效降低空間區(qū)域查詢及網(wǎng)絡(luò)總體能耗,尤其適用于大規(guī)模無(wú)線傳感網(wǎng)絡(luò)及空間區(qū)域查詢應(yīng)用場(chǎng)景。

[1] 郭龍江,李建中,李貴林. 無(wú)線傳感器網(wǎng)絡(luò)環(huán)境下時(shí)-空查詢處理方法[J]. 軟件學(xué)報(bào),2006,17(4):794-805.

[2]彭鐸,黎鎖平,楊喜娟. 一種能量高效的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J]. 傳感技術(shù)學(xué)報(bào),2014,27(12):1687-1691.

[3]Luo J,He Y. GeoQuorum:Load Balancing and Energy Efficient Data Access in Wireless Sensor Networks[C]//Infocom,2011 Proceedings IEEE. IEEE,2011:616-620.

[4]陳曉娟,王卓,吳潔. 一種基于LEACH的改進(jìn)WSN路由算法[J]. 傳感技術(shù)學(xué)報(bào),2013,26(1):116-121.

[5]劉鐵流,巫詠群. 基于能量?jī)?yōu)化的無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法研究[J]. 傳感技術(shù)學(xué)報(bào),2011,24(5):764-770.

[6]陳慶章,趙小敏,陳曉瑩. 提高無(wú)線傳感器網(wǎng)絡(luò)能效的雙輪成簇協(xié)議設(shè)計(jì)[J]. 軟件學(xué)報(bào),2010,21(11):2933-2943.

[7]Heinzelman W R,Chandrakasan A P. An Application-Specific Protocol Architecture for Wireless Microsensor Networks Wireless Communications[J]. IEEE Transactions,2002,1(4):600-670.

[8]Lindsey S,Raghavendra C S. PEGASIS:Power Efficient Gathering in Sensor Information Systems[C]//Proc of the IEEE Aerospace Conf. San Francisco:IEEE Computer Society,2002:1-6.

[9]Younis O,Fahmy S. Distributed Clustering in Adhoc Sensor Networks:A Hybrid,Energy-Efficient Approach[J]. IEEE Transactions on Mobile Computing,2004,3(4):660-669.

[10]Yu Y,Estrin D,Govindan R. Geographical and Energy Aware Routing:A Recursive Data Dissemination Protocol for Wireless Sensor Networks[R]. UCLA Computer Science Department,2001:1-11.

[11]Wen-Hwa Liao,Yu-Chee Tseng,Jang-Ping Sh. GRID:A Fully Location-Aware Routing Protocol for Mobile Ad Hoc[J]. Telecommunication Systems,2001:18(1-3):37-60.

[12]Wen-Hwa Liao,Yu-Chee Tseng,Kuo-Lun Lo,et al. GeoGRID:A Geocasting Protocol for Mobile Ad Hoc Networks Based on GRID[J]. Journal of Internet Technology,2000,1(2):23-32.

[13]劉琳,于海斌,曾鵬. 節(jié)能有效的無(wú)線傳感器網(wǎng)絡(luò)狀態(tài)信息收集算法[J]. 通信學(xué)報(bào),2009,30(6):126-134.

[14]曾志文,陳志剛,劉安豐. 無(wú)線傳感器網(wǎng)絡(luò)中基于可調(diào)發(fā)射功率的能量空洞避免[J]. 計(jì)算機(jī)學(xué)報(bào),2010,33(1):12-22.

[15]盛業(yè)華,唐宏,杜培軍. 線性四叉樹(shù)快速動(dòng)態(tài)編碼及其實(shí)現(xiàn)[J]. 武漢測(cè)繪大學(xué)學(xué)報(bào),2000,25(4):324-328.

[16]Hill J,Szewczyk R,Woo A,et al. System Architecture Directions for Network Sensors[C]//Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems. Cambridge,MA,USA,2000:93-104.

[17]錢(qián)志鴻,王義君. 面向物聯(lián)網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)綜述[J]. 電子與信息學(xué)報(bào),2013,35(1):215-227.

[18]Heinzelman W,Chandrakasan A,Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc of the 33rd Annual Hawaii Int’l Conf. on System Sciences,2000:3005-3014.

[19]何延杰,李臘元,邢明彥. WSN中一種能量均衡的分簇路由協(xié)議的設(shè)計(jì)[J]. 傳感技術(shù)學(xué)報(bào),2009,22(10):1510-1514.

QuadGrid:A Quadtree Based Spatial Query Routing Protocol for Wireless Sensor Networks*

NIEYunfeng*,WANGChangsheng,CHENChongyi

(School of Information and Engineering,Nanchang Hangkong University,Nanchang 330063,China)

In the data-centric large scale wireless sensor networks,most of the queries submitted by users are spatial queries. However,sensor nodes are severely constrained in energy supply,thus,improving the spatial-query energy efficiency is becoming more and more important. GeoGrid is a totally geographical location based routing protocol,and it is well suitable for the large-scale wireless sensor network application scenarios. However,it suffers from a relatively low spatial query efficiency. Aimed at the large scale spatial-query application scenarios,this paper proposes QuadGrid,a new quadtree structure based routing protocol for wireless sensor networks. QuadGrid improves the GeoGrid in its cluster set-up,cluster head election,networks topology hierarchy and routing strategy. Simulation results reveal that QuadGrid has a better performance than the GeoGrid and the QTBDC in:the energy-balancing,the network existing time and the spatial query efficiency.

wireless sensor networks;routing protocol;spatial query efficiency;quadtree structure;GeoGrid;Quadtree

聶云峰(1980-),男,博士,副教授,主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò),遙感與地理信息系統(tǒng),nieyunf@gmail.com;

王長(zhǎng)勝(1990-),男,碩士研究生,主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò),994358998@qq.com。

項(xiàng)目來(lái)源:國(guó)家自然科學(xué)基金項(xiàng)目(41101426,61364023);江西省自然科學(xué)基金項(xiàng)目(CA201204330);江西省教育廳科學(xué)技術(shù)研究項(xiàng)目(GJJ12429)

2014-12-24 修改日期:2015-02-02

C:6150P

10.3969/j.issn.1004-1699.2015.05.022

TP393

A

1004-1699(2015)05-0744-08