能量高效的无线传感器网络空间范围查询处理算法  

An Energy-Efficient Spatial Window Query Processing Algorithm in Wireless Sensor Networks

作　　者：刘亮[1] 秦小麟[1] 郑桂能[1] 李博涵[1] 

机构地区：[1]南京航空航天大学信息科学与技术学院,南京210016

出　　处：《计算机学报》2011年第5期763-778,共16页Chinese Journal of Computers

基　　金：国家自然科学基金(60673127);国家"八六三"高技术研究发展计划项目基金(2007AA01Z404);江苏省支撑计划项目(BE2008135);高等学校博士学科点专项科研基金(20103218110017);工信部电子信息产业发展基金;中国博士后科学基金(20100481133);江苏省博士后基金(1001005B)资助~~

摘　　要：现有无线传感器网络空间范围查询处理算法能量消耗大且当节点失效时查询处理过程易被中断,无法返回查询结果.文中提出了一种能量高效的算法ESA(Energy-efficient Spatial window query processing Algorithm).它将查询区域划分为若干个网格,每个网格中有一个簇头节点负责收集所在网格中其它节点的感知数据,对这些数据进行聚集运算得到部分查询结果,并将其发送至下一个网格的簇头节点,直至收集到查询区域内所有节点的感知数据,以生成最终的查询结果.ESA算法只需查询区域内的节点发送一次数据消息,减少了发送的数据消息数目.根据ESA的能耗公式给出了两种网格划分和簇头节点选择算法,以降低算法分发查询消息消耗的能量.设计了一种利用节点冗余保证查询处理过程鲁棒性的算法,避免了ESA因节点失效而中断.提出了两种感知数据收集算法,以减少簇头节点收集其邻居节点感知数据的能耗.最后,对ESA算法和现有的IWQE算法(Itinerary-based Window Query Execution)的性能进行了系统的理论和实验分析.分析结果表明:在绝大多数情况下,ESA算法在能量消耗、查询成功率和查询结果质量方面优于IWQE算法.The energy consumption of existing spatial window query processing algorithms in wireless sensor networks is fairy high.When some sensor nodes fail,the query process of these algorithms is very likely to be interrupted and unable to return query result.An energy-efficient spatial window query processing algorithm called ESA is proposed in this paper.It divides the query region into several grids.Each grid has a cluster node which collects the sensory data in it,aggregates the data to derive partial query result and sends it to the cluster node in the next grid.The above process is repeated until all nodes within the query region are traversed in order to generate the final query result.ESA only requires each node within the query region send data message once,which reduces the data messages.The authors propose two grid dividing and cluster node selection algorithms according to the ESA＇s energy consumption formula to reduce the energy consumption of distributing the query messages.Then,the authors design a query processing recovery algorithm using node redundancy,which avoids the interruption of ESA due to node failures,and two data collection algorithms to reduce the energy consumption during the process where the cluster nodes collect the sensory data of its neighbors.Finally,the performance of ESA and IWQE（itinerary-based window query execution） is analyzed systematically.Analytical and experimental results show that in most cases ESA outperforms IWQE in terms of energy consumption,query success rate and query result quality.

关 键 词：物联网 无线传感器网络 查询处理 空间范围查询 能量高效 容忍节点失效 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]