Utilizing Voronoi Cells of Location Data Streams for Accurate Computation of Aggregate Functions in Sensor Networks |
| |
Authors: | Mehdi Sharifzadeh Cyrus Shahabi |
| |
Affiliation: | (1) Computer Science Department, University of Southern California, Los Angeles, CA 90089-0781, USA |
| |
Abstract: | Sensor networks are unattended deeply distributed systems whose database schema can be conceptualized using the relational
model. Aggregation queries on the data sampled at each sensor node are the main means to extract the abstract characteristics
of the surrounding environment. However, the non-uniform distribution of the sensor nodes in the environment leads to inaccurate
results generated by the aggregation queries. In this paper, we introduce “spatial aggregations” that take into consideration
the spatial location of each measurement generated by the sensor nodes. We propose the use of spatial interpolation methods
derived from the fields of spatial statistics and computational geometry to answer spatial aggregations. In particular, we
study Spatial Moving Average (SMA), Voronoi Diagram and Triangulated Irregular Network (TIN). Investigating these methods
for answering spatial average queries, we show that the average value on the data samples weighted by the area of the Voronoi
cell of the corresponding sensor node, provides the best precision. Consequently, we introduce an algorithms to compute and
maintain the accurate Voronoi cell at each sensor node while the location of the others arrive on data stream. We also propose
AVC-SW, a novel algorithm to approximate this Voronoi cell over a sliding window that supports dynamism in the sensor network.
To demonstrate the performance of in-network implementation of our aggregation operators, we have developed prototypes of
two different approaches to distributed spatial aggregate processing.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee
provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the
full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires
prior specific permission and/or a fee. GIS'04, November 12–13, 2004, Washington DC, USA. Copyright 2004 ACM 1-58113-979-9/04/0011...$5.00. |
| |
Keywords: | sensor networks aggregation spatial interpolation Voronoi cell spatial data stream |
本文献已被 SpringerLink 等数据库收录! |
|