Font Size: a A A

Research On ε-Approximate Query Processing Algorithms In Wireless Sensor Networks

Posted on:2011-12-08Degree:MasterType:Thesis
Country:ChinaCandidate:J GaoFull Text:PDF
GTID:2178330338979938Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
Wireless sensor networks is a kind of wireless self-organizing networks with a distinct data-centric property, which consists of a large number of sensor nodes that integrate sensor devices, data processing unit and the module for the short distance wireless communications. Wireless sensor networks have been used for numerous applications including medical monitoring, military surveillance, environment and traffic monitoring, space exploration and disaster relief. In many real-world scenarios, the results of aggregation queries and Top-k queries are important for users to get summarization information about the monitored area.The early aggregation algorithms and Top-K algorithms for wireless sensor networks focus on getting the exact results. However, in practice there is always some noise in the sensed data due to the errors during sensing and the interference during transmission. As many applications only require approximate aggregation results rather than the exact ones, a number of approximate algorithms have been proposed in order to reduce energy consumption. However, almost all these methods target on processing queries over all sensor nodes in the network, and can not process spatial window queries which specify a particular window in the network area. In addition, these approximate methods require users to specify fixed error bounds in advance, which is infeasible and inefficient in many real-world scenarios.To resolve all the above problems, we extendε-approximate query processing architecture by proposingε-approximate spatial-window aggregate query processing technique andε-approximate spatial-window Top-K query processing technique to satisfy the requirement of arbitrary regions and arbitrary accuracy specified by the users. For the aggregation function Sum and Min, we present EA-Sum algorithm and EA-Min algorithm respectively. We devise dynamic programming algorithm EA-Sum to compute minimum number of data to refine approximate summation to reach arbitrary accuracy. Our algorithm EA-Min is efficient to compute minimum/maximum values by only transmitting values promising to be in the exact results in order to reduce energy consumption. We present EA-TopK algorithm based on the filtering strategy whose main idea is to drop candidate data which has no chance to enter the final result set as early as possible. Our EA-TopK algorithm allows users to specify arbitrary regions and arbitrary precision, as well as guarantee that the probability of failure can be smaller than users'requirement. In our experiment using real-world data, we demonstrate our algorithms can provide high quality results and reach arbitrary accuracy with low energy cost.
Keywords/Search Tags:wireless sensor networks, aggregation, Top-K, ε-Approximate, spatial window
PDF Full Text Request
Related items