Abstract: In wireless sensor networks, the users often submit spatial window queries to obtain the summary information of a local area in the network such as maximum temperature, average humidity, et al. The current state-of-the-art itinerary-based spatial query processing algorithms make the assumption of the link model pertaining to the ideal disk model. However, it’s not valid in realistic networks, which leads to large energy consumption and poor quality query result. This paper proposes a link quality aware spatial window query processing algorithm called LSA(link aware spatial window query processing algorithm). It divides the query region into several grids according to the topology and link of the network, and collects data from the sensor nodes in each grid to derive the final query result. LSA traverses all the grids within the query region which ensures the query result quality of the algorithm. In order to reduce the packet loss rate of communications between nodes, a heuristic method is given which divides the query region into grids. Then, a link aware data collection algorithm is proposed to reduce energy consumption and improve the query result quality of the algorithm. Finally, this paper systematically analyzes and compares the energy consumption and the query result quality of the LSA and the existing IWQE(itinerary-based window query execution) algorithm through simulation experiments. Experimental results show that LSA algorithm outperforms IWQE in most cases.

Key words: wireless sensor network, query processing, spatial window query, link quality

摘要： 在无线传感器网络环境中, 用户经常提交空间范围查询以获取网络某局部区域的统计信息, 如最大温度、平均湿度等。现有的基于路线的空间范围查询处理算法假设节点通信模型为理想的圆盘模型, 而实际的网络并不满足该假设, 导致其能量消耗大且查询结果质量差。提出了一种链路感知的空间范围查询处理算法LSA, 它根据网络拓扑和链路质量动态地将查询区域划分为若干个网格, 依次收集各网格中节点的感知数据, 以生成最终的查询结果。LSA算法通过遍历查询区域内的所有网格, 保证了算法查询结果的质量。提出了启发式的网格划分方法以降低节点间数据通信的丢包率, 给出链路感知的数据收集算法, 以减少算法的能量消耗, 提高查询结果的质量。通过仿真实验系统地分析和比较了LSA算法和现有的IWQE算法的能量消耗及查询结果质量, 结果表明, 在绝大多数情况下, LSA算法优于IWQE算法。

关键词: 无线传感器网络, 查询处理, 空间范围查询, 链路质量