- 173 views
- 140 downloads
Optimizing Query Processing in Cache-Aware Wireless Sensor Networks
-
- Author(s) / Creator(s)
-
Technical report TR09-05. It is a well known fact that minimizing energy consumption in Wireless Sensor Networks (WSNs) is crucial for its usability; and minimizing the flow of data is one way to achieve that. Most WSN models assume the existence of a base station where query results could in principle be cached, however, the opportunity for re-using such cached data for minimizing data traffic in the WSN has not been well explored thus far. Aiming at filling this gap, we investigate the cache-aware query processing problem in WSNs. We propose an approach that first clips an original rectangular query area into a polygon by selecting a suitably good subset of the cached queries for reuse. Next, this polygon is partitioned into rectangular sub-queries that are then submitted to the WSN. Finding the cost-wise best combination of polygon clipping and rectangular partitioning amounts to a highly combinatorial problem that justifies the use of efficient and effective heuristics. This paper presents algorithms that are used within a cost-driven optimization search to find a good \"query-plan\". Algorithms for maintaining the cache consistency are also presented. Our proposal does not dependent on any particular algorithm for processing queries in a WSN; as long as there is a well-defined a cost-model for the same, any proposal can be used. Experimental results show that our heuristic algorithms are orders of magnitude faster than an exhaustive search, and yield no more than 10% loss compared to the optimal query cost, and are never worse than the two obvious alternatives, i.e., not using the cache at all or using all of it. | TRID-ID TR09-05
-
- Date created
- 2009
-
- Subjects / Keywords
-
- Type of Item
- Report
-
- License
- Attribution 3.0 International