一種空間查詢高效的無線傳感網絡路由協議*

聶云峰,王長勝,陳崇毅

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

?

一種空間查詢高效的無線傳感網絡路由協議*

聶云峰*,王長勝,陳崇毅

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

在以數據為中心的大規模無線傳感網絡中,感知數據查詢通常以空間查詢為主,而感知節點攜帶能量極為有限,因此提高感知數據空間查詢能量利用效率尤為重要。GeoGrid協議是一種完全基于地理位置信息的路由協議,適用于大規模無線傳感網絡應用場景,但其空間查詢效率較低。針對大規模空間查詢應用場景,從成簇方式、簇首選舉、網絡拓撲層次構建及路由策略等方面對GeoGrid進行優化,提出一種基于四叉樹結構的空間查詢能量高效的無線傳感網絡路由協議——QuadGrid,并對GeoGrid、QTBDC及QuadGrid的空間查詢能耗進行仿真分析。實驗結果表明,與GeoGrid、QTBDC相比,QuadGrid網絡能耗更均衡,網絡生命周期更長,空間查詢更高效。

無線傳感網絡;路由協議;空間查詢能量高效;四叉樹結構;GeoGrid;QuadGrid

無線傳感網絡WSNs(Wireless Sensor Networks)是以數據為中心的網絡,其目的是由各感知節點協作地感知、采集和處理監測區域中感知對象的信息,并將信息發布給觀察者[1]。無線傳感網絡路由協議設計的首要目標是能量高效[2]。在WSNs中,感知數據與時間和空間高度相關,并且感知數據查詢以時空查詢為主,而傳感器節點通常由電池供電,攜帶能量極為有限,在野外、戰場等特定環境下,受條件制約很難補充節點能量[3],因此,能量高效的空間查詢處理是目前亟需解決的問題。

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

GeoGrid協議是一種基于地理位置信息的路由協議,適用于大規模無線傳感網絡應用場景,但其空間查詢效率較低。針對大規模空間查詢應用場景,從成簇方式、簇首選舉、網絡拓撲層次構建及路由策略等方面對GeoGrid進行優化,提出一種基于四叉樹的空間查詢能量高效的無線傳感網絡路由協議——QuadGrid,并對GeoGrid、QTBDC及QuadGrid的空間查詢能耗進行仿真分析。

1 GeoGrid簡介

GeoGrid是基于Grid協議提出的一種完全基于地理位置信息的均勻分簇路由協議,將監測區域均勻劃分為若干個大小相等的網格,單個網格內的全部感知節點構成一個簇,以網格內距離網格中心最近的節點作為簇首,在數據傳輸過程中僅由簇首節點承擔數據轉發任務,普通節點不參與數據轉發。

GeoGrid中簇首選擇是動態的,當簇首死亡或離開本網格時,簇內隨即選取距離網格中心最近的節點作為新的簇首。網格劃分后,每個網格都被賦予一個與其在網絡中的位置相對應的網格坐標(x,y),如圖1中節點A、D所處的網格坐標分別為(0,0)、(3,3)。當有數據包需要轉發時,GeoGrid將根據當前網格坐標與目的網格坐標所體現的相對位置關系逐網格進行數據轉發,直至數據包到達目標網格內的目標節點。

圖1 GeoGrid路由協議

在處理地域群播(Geocasting)問題時,GeoGrid利用源節點及目標區域的位置信息來限制數據傳播區域,將洪泛區限制在包含源節點與目標區域的最小矩形內,由位于洪泛區內的簇首節點負責數據轉發。

GeoGrid是比較成熟并且常用的均勻分簇路由協議,能夠在減少冗余數據傳輸的同時提高數據傳輸成功率,適用于地域群播應用場景,但是GeoGrid在以下5個方面仍存在不足:①網格劃分方法不夠靈活,沒有充分考慮到實際應用需求;②采用三維坐標(x,y,id)(其中x和y分別為節點所在網格的橫縱坐標,id為節點的簇內標識)來標識感知節點位置信息,在數據傳輸過程中消耗較多能量;③在簇首選舉上未考慮節點的剩余能量因素,其簇首選取與更換方式易導致各節點能耗不均衡,從而易導致部分節點過早死亡;④在下一跳路由節點的選取上未考慮節點剩余能量因素,易導致能量空洞[14](Energy Hole)問題;⑤其網絡拓撲層次結構不利于高效的空間查詢。

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

2 QuadGrid協議

2.1 簇的劃分與編碼

與GeoGrid不同,QuadGrid協議采用基于二進制Morton碼(簡稱M碼)的編碼方法對網格進行四叉樹編碼,簇劃分與編碼的具體過程如下:

①擴展監測區域

定義完全覆蓋監測區域并且Sink節點位于網絡正中心的最小正方形GridBond,定義此正方形邊長為L。

圖2 監測區域四叉樹層次劃分

②劃分監測區域

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

位于同一個網格內的所有感知節點構成一個簇,網絡劃分后的網格邊長l與GridBond邊長L之間滿足如下關系:

l=L/2Z

(1)

③對網格進行M碼編碼

網格劃分后,GeoGrid利用網格的行列號(m,n)來表示網格位置,m為行號,n為列號,如圖3左下角網格位置表示為(0,0),右上角網格位置為(7,7),而QuadGrid則是在此在基礎上進一步采用Morton碼對網格進行編碼,將二維的網格行列信息通過比特交叉映射成一個二進制數,編碼完成后網格的M碼以及感知節點的簇內id共同組成節點標識號。節點標識號占用16個比特,其中感知節點的簇內id占用16-2Z低位比特,網格M碼為高位的2Z比特,M碼中每兩位比特代表相應層次的子區域,以“010110”為例,頭兩位“01”表示網絡區域的左上部分的子區域,中間兩位“01”代表該子區域的左上部分的次級子區域,最后兩位“10”表示次級子區域的右下部分的網格,如圖2陰影區域所示。

與GeoGrid利用三元組標識感知節點相比,QuadGrid利用一維節點序列號標識感知節點,可在一定程度上減少數據占用空間,從而能夠降低感知節點數據傳輸能耗。監測區域M碼編碼如圖3所示。

圖3 網格的Morton編碼圖

④計算節點通信半徑R

圖4 QuadGrid節點通信半徑

2.2 簇首選舉及父簇首選擇

簇首選舉在分簇算法中起著關鍵作用,GeoGrid協議選擇離網格中心位置最近的節點作為簇首,節點一旦當選簇首將持續工作直到剩余能量達到最小存活閾值為止,簇內才會重新選舉簇首,這種簇首選擇方式沒有考慮到各節點的負載均衡,易導致部分簇首因負載過重而過早死亡。QuadGrid在簇首選舉初始階段也選取距離網格中心位置最近的節點作為簇首,但在重新選取簇首時綜合考慮節點剩余能量、節點與網格中心的距離及節點與周圍8個鄰居簇簇首的距離等3方面因素。以CH為節點的簇首競選因子,選取簇內CH值最小的節點作為簇首,CH值的計算如下:

(2)

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

Sink節點以Ts為時間間隔周期性向網絡內所有節點廣播簇首選舉的消息,各簇節點接收到消息后,開始新一輪簇首選舉。簇內某一節點當選為簇首后向簇內節點及周圍鄰居簇廣播當選消息,簇內成員節點接收消息后記錄該簇首信息,周圍鄰居簇首節點接收消息后在各自鄰居表中記錄該簇首信息。

QuadGrid協議中每經過一次簇首選舉,性能較差的簇首節點會被新的綜合性能最優的節點所取代,因而可以在有效避免簇首節點過早死亡的同時均衡簇內節點能量損耗,從而能夠在一定程度上延長節點乃至整個網絡的生命周期。

文獻[17]指出,有效的網絡拓撲控制結構能夠為其他網絡服務支持技術提供基礎,提高網絡通信協議的應用效率,同時有利于延長網絡的生命周期。QuadGrid采用基于四叉樹的拓撲層次結構,在相應四叉樹層次增加管理節點,除Sink節點外,每層簇首節點都有一個父簇首節點(簡稱父節點),父節點負責收集其4個子簇首節點(簡稱子節點)匯報上來的感知數據,并將收集到的數據進行融合然后發送給其自身的父節點。為簡化算法,QuadGrid在4個子節點中選擇所屬網格距離Sink節點最近的子節點作為這4個子節點的父節點。在該算法中網絡中某一簇首節點僅根據其節點標識號就可以計算出其各級父節點所在簇的M碼,因而不需簇首之間進行額外通信協商。

父簇首節點選擇算法:

getFatherNode_MC(nodeMC md,leveli,treeDepthd){

begin

//md為感知節點序列號,i為父節點的層

//次級別并且(1≤i

//將節點序列號低位16-2(d-i)比特清零,保留高位2(d-i)比特

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

//截取網格M碼前兩位,按位取返后作為

//網格M碼后兩位

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

for(intj=1;j

begin

md2=md2+(md2?2);

end

fmd=md1+md2;

//fmd為當前簇首節點指定層次級別的

//父節點所在網格的M碼

return fmd;

end

}

2.3 路由選擇

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

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

①計算當前父節點經候選簇首到下一級父節點的距離

圖5 QuadGrid路由協議

②計算下一級路由選擇因子NHop

綜合考慮距離與節點剩余能量兩方面因素,給出第i個鄰居簇首的選擇因子NHopi的計算公式:

式中:λ和μ為平衡系數,λ+μ=1且λ>0、μ>0;Lmax為L2、L3及L4中的最大值;pi=Ecurrent i/Einitial i,Ecurrent i為當前簇首剩余能量,Einitial i為當前簇首初始能量。當簇首D需要進行數據傳輸時,其位于路由限制區內的鄰居簇首E、H和I將分別計算各自的NHop值,簇首D將選取其中NHop值最小的簇首為下一跳路由節點。各級中間簇首節點將采取相同方式選取各自的下一跳節點,直至所需傳輸的數據分組到達目標父節點G,圖5中所示D到Sink節點的路徑為D→E→F→G→Sink。

圖6 數據轉發區域

2.4 空間查詢

①Sink節點向待查詢區域感知節點發送查詢請求數據包

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

//X為接收查詢請求數據包的感知節點,查詢請

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

//詢窗口的最小矩形,R為包含節點與G的最小

//矩形,id為查詢請求包id

ReceiveQueryRequestPackage(G,R,id){

begin

if(X位于R區域內)

thenbegin

if(X為簇首節點)

begin

//判斷X是否接收過當前請求包

if(packageId==id)

begin

Step1.X直接刪除接收到的數據包.

end

elsebegin

Step1.X向鄰居簇首節點轉發查詢請求包.

if(X位于G區域內)

begin

Step1.X向其所轄簇內成員節點發送數據包.

end

end

end

end

elsebegin

Step1.X直接刪除接收到的數據包.

end

end

}

②感知節點向Sink節點反饋感知數據

QuadGrid中,查詢窗口內的簇首節點向Sink節點反饋感知數據時,由各層父節點負責收集、融合并轉發監測區域內的監測數據,具體算法如下:

//假定X為查詢窗口內的感知節點,queryWindow為

//查詢窗口;rendezvousLevel表示的是父簇首節點的

//層次級別0≤rendezvousLevel

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

GetDataByRegion(queryWindow,rendezvousLevel,treeDepth){

begin

if(X不為簇首節點)

then

begin

Step1.獲取數據;

Step2.將數據發送給X所屬簇首節點;

end

//如果X為第0～treeDepth-2級父簇首節點

elseif(0≤rendezvousLevel

then

begin

//對收集到的感知數據進行融合;

Step1.fuseReceivedData();

//通過父簇首節點選擇算法計算出X的父簇首節點;

Step2.getRendezvousNode();

Step3.X通過式及式計算出到達父簇首節點

的下一跳中間節點M,將融合后的數據包轉

發給M,并由M繼續承擔數據轉發任務。

end

//如果X為第treeDepth-1級父簇首節點

else

begin

Step1.fuseReceivedData();

Step2.X直接通過簇間通信將融合后的數據轉發給Sink節點;

end

end

}

3 QuadGrid仿真結果分析

3.1 能耗模型

數據通信是無線傳感網絡最為耗能的部分,與之相比較,傳感器節點運算和存儲所需要的能量基本可忽略不計。因此,無線傳感網絡生存時間的長短主要取決于數據傳輸消耗能量的大小。

本文采用文獻[18]中的一階無線模型(firstorderradiomodel)來計算節點發送和接收能耗。在該能耗模型中,節點發送能耗與傳播距離的平方成正比,將k比特數據傳送距離d,發送節點能為ETx=ETx(k,d)=Eeleck+εampkd2,接收節點能耗為ERx=ERx(k,d)=Eeleck,其中Eelec是發送接收電路的能耗系數,εamp是傳輸放大器為保證數據可靠傳輸所需的能耗系數。

3.2 實驗參數設置

表1 實驗參數

3.3 仿真結果及分析

本文采用由美國加州大學LBL網絡研究組研發的網絡仿真工具NS2[19](NetworkSimulatorversion2)從網絡平均能耗、網絡存活節點數量及空間查詢能耗等3個方面對QuadGrid、GeoGrid及QTBDC進行仿真分析。

圖7 網絡平均耗能對比

實驗一對網絡中節點向Sink節點發送數據的平均能耗及平均節點存活數目進行仿真,網絡中初始節點數目為400,柵格分辨率Z=3,各簇首節點向Sink節點發送感知數據,每10輪簇內重新進行一次簇首選舉,仿真結果分別如圖7及圖8所示。

圖8 網絡中節點存活數

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

圖9 空間區域查詢平均能耗對比

4 結論

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

[1] 郭龍江,李建中,李貴林. 無線傳感器網絡環境下時-空查詢處理方法[J]. 軟件學報,2006,17(4):794-805.

[2]彭鐸,黎鎖平,楊喜娟. 一種能量高效的無線傳感器網絡非均勻分簇路由協議[J]. 傳感技術學報,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的改進WSN路由算法[J]. 傳感技術學報,2013,26(1):116-121.

[5]劉鐵流,巫詠群. 基于能量優化的無線傳感器網絡分簇路由算法研究[J]. 傳感技術學報,2011,24(5):764-770.

[6]陳慶章,趙小敏,陳曉瑩. 提高無線傳感器網絡能效的雙輪成簇協議設計[J]. 軟件學報,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]劉琳,于海斌,曾鵬. 節能有效的無線傳感器網絡狀態信息收集算法[J]. 通信學報,2009,30(6):126-134.

[14]曾志文,陳志剛,劉安豐. 無線傳感器網絡中基于可調發射功率的能量空洞避免[J]. 計算機學報,2010,33(1):12-22.

[15]盛業華,唐宏,杜培軍. 線性四叉樹快速動態編碼及其實現[J]. 武漢測繪大學學報,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]錢志鴻,王義君. 面向物聯網的無線傳感器網絡綜述[J]. 電子與信息學報,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中一種能量均衡的分簇路由協議的設計[J]. 傳感技術學報,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-),男,博士,副教授,主要研究方向為無線傳感器網絡,遙感與地理信息系統,nieyunf@gmail.com;

王長勝(1990-),男,碩士研究生,主要研究方向為無線傳感器網絡,994358998@qq.com。

項目來源:國家自然科學基金項目(41101426,61364023);江西省自然科學基金項目(CA201204330);江西省教育廳科學技術研究項目(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