一种空间查询高效的无线传感网络路由协议*

2015-05-09聂云峰王长胜陈崇毅

传感技术学报 2015年5期

关键词：路由能耗无线

聂云峰,王长胜,陈崇毅

(南昌航空大学信息工程学院,南昌 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

elsebegin

Step1.X直接删除接收到的数据包.

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

}

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