Research On Spatio-temporal Query Processing Techniques In Wireless Sensor Networks

Wireless sensor networks (WSNs) can be used to sense, collect and process the information aboutthe monitored objects in the area of deployment. WSNs have a wide coverage area and high precisionof information. It has become a hot spot in recent years for its broad prospects in applications ofnational defense, environment monitoring, medical services, transportation control and etc. Unliketraditional networks, WSNs have many limitations in terms of computing, storage, energy,communication bandwidth, reliability, fault tolerance. After the deployment of sensor networks,ambient noise, communication interference and hardware failures are not predictable and controllable.These factors make the development of WSN application to be very complex and difficult. How toshield the complexity of WSNs and reduce the difficulty of development of sensor network applicationsis an urgent problem to be solved.WSNs are data-centric networks. The main purpose of using it is to query the spatio-temporalsensor readings. We view the whole sensor network as a distributed spatio-temporal database, and studythe spatio-temporal query processing technology in WSNs. We designed a spatio-temporal queryprocessing system for WSNs to manage and query the spatio-temporal data sensed. Our final aims is toshields the complexity and difficulty of development of sensor network applications. The maincontributions of this dissertation are summarized as follows:(1) In static wireless sensor networks, most of the existing spatio-temporal window queryprocessing algorithms organized all the nodes in the whole network or the nodes in the query area intoa single routing tree. The sensor readings of the nodes in the query area are sent back to the sink guidedby the routing tree. We point out that the path along which the query results are sent back to the sink isfairly long when a single routing tree is adopted, which leads to a large amount of energy consumption.Organizing the nodes in the query area into multiple routing trees can avoid this problem. Based on theabove findings, we design a protocol of constructing multiple routing trees for the nodes in the queryarea, and propose an energy-efficient spatio-temporal query processing algorithm called E2STA.Theoretical and experimental results show that the proposed algorithm based on multiple routing treesoutperforms the existing algorithms based on one single routing tree in terms of energy consumption.(2) We propose an efficient spatio-temporal query processing framework for dynamic wirelesssensor networkscalled EST in this paper. It consists of three stages: dividing query area, distributingquery message and collecting sensor readings. Through dividing query area, the sensory data within thequery area been returned through a number of different data forwarding paths, which reduces thenetwork "hot spots". We also proposed a geographic routing based query message multicast protocoland an itinerary based data collection protocol, which saves energy of distributing query messages byscheduling some nodes with the query area broadcast query messages. The proposed data collectionprotocol returns the query results back to the sink through geographic routing protocol, which reducesthe number of data forwarding. Experimental results show that EST outperforms the existingalgorithms in terms of energy consumption and lifetime.(3) The energy consumption of existing spatial window query processing algorithms and k nearestneighbor query processing algorithms in wireless sensor networks is fairy high. When some sensornodes fail, the query process of these algorithms is very likely to be interrupted and unable to returnquery results. We propose a node failure tolerant and energy optimization method based on dividingquery area. The query area is divided into several sub-regions. While a node fails, the alive nodes in the sub-region where the failed node resides in recover the interrupted process of query processing, whichreduces the outage probability of query processing due to node failures. We prove that largersub-regions result in less energy consumption while meeting the constraints of wireless communication.Based on this theory, we propose a query area dividing algorithm which maximizes the area of eachsub-region to reduce the total energy consumption.(4) We design and implement SensorMapReduce: a dynamically scalable spatio-temporal queryprocessing system in wireless sensor networks. It is composed of the query compiler at the base stationend and the virtual machine at the node side. A unified spatio-temporal query processing framework isproposed. It abstract various spatio-temporal query to four basis operation: Map, Reduce,GetNextClusterNode and GetNextClusterShape. The query compiler compiles the submitted query intoMap and Reduce code which are sent to run in the virtual machine of sensor nodes. SensorMapReduceprovides declarative spatio-temporal query language to shield the complexity of the underlyingdistributed query processing. Through extending the query compiler, SensorMapReduce can supportother types of queries without changing the node-side code, which reduces the cost of nodereprogramming.