A Survey of Geosensor Networks: Advances in Dynamic Environmental Monitoring <s> Decentralized and Collaborative Spatial Computation <s> We present the Tiny AGgregation (TAG) approach to distributing declarative SQL-style aggregate queries with grouping over networks of low-power, wireless sensors. We discuss various generic properties of aggregates, and show how those properties affect the performance of our in-network approach. We include a performance study demonstrating the advantages of our approach over traditional centralized, out-ofnetwork methods, and discuss a variety of optimizations for improving the performance and fault-tolerance of the basic solution. <s> BIB001 </s> A Survey of Geosensor Networks: Advances in Dynamic Environmental Monitoring <s> Decentralized and Collaborative Spatial Computation <s> Declarative queries are proving to be an attractive paradigm for ineracting with networks of wireless sensors. The metaphor that "the sensornet is a database" is problematic, however, because sensors do not exhaustively represent the data in the real world. In order to map the raw sensor readings onto physical reality, a model of that reality is required to complement the readings. In this paper, we enrich interactive sensor querying with statistical modeling techniques. We demonstrate that such models can help provide answers that are both more meaningful, and, by introducing approximations with probabilistic confidences, significantly more efficient to compute in both time and energy. Utilizing the combination of a model and live data acquisition raises the challenging optimization problem of selecting the best sensor readings to acquire, balancing the increase in the confidence of our answer against the communication and data acquisition costs in the network. We describe an exponential time algorithm for finding the optimal solution to this optimization problem, and a polynomial-time heuristic for identifying solutions that perform well in practice. We evaluate our approach on several real-world sensor-network data sets, taking into account the real measured data and communication quality, demonstrating that our model-based approach provides a high-fidelity representation of the real phenomena and leads to significant performance gains versus traditional data acquisition techniques. <s> BIB002 </s> A Survey of Geosensor Networks: Advances in Dynamic Environmental Monitoring <s> Decentralized and Collaborative Spatial Computation <s> Information about dynamic spatial fields, such as temperature, windspeed, or the concentration of gas pollutant in the air, is important for many environmental applications. At the same time, the development of geosensor networks (wirelessly communicating, sensor-enabled, small computing devices distributed throughout a geographic environment) present new opportunities for monitoring dynamic spatial fields in much greater detail than ever before. This paper develops a new model for querying information about dynamic spatial fields using geosensor networks. In order to manage the inherent complexity of dynamic geographic phenomena, our approach is to focus on the qualitative representation of spatial entities, like regions, boundaries, and holes, and of events, like splitting, merging, appearance, and disappearance. Based on combinatorial maps, we present a qualitative model as the underlying data management paradigm for geosensor networks. This model is capable of tracking salient changes in the network in an energy-efficient way. Further, our model enables reconfiguration of the geosensor network in response to changes in the environment. We present an algorithm capable of adapting sensor network granularity according to dynamic monitoring requirements. Regions of high variability can trigger increases in the geosensor network granularity, leading to more detailed information about the dynamic field. Conversely, regions of stability can trigger a coarsening of the sensor network, leading to efficiency increases in particular with respect to power consumption and longevity of the sensor nodes. Querying of this responsive geosensor network is also considered, and the paper concludes with a review of future research directions. <s> BIB003 </s> A Survey of Geosensor Networks: Advances in Dynamic Environmental Monitoring <s> Decentralized and Collaborative Spatial Computation <s> Real-world data --- especially when generated by distributed measurement infrastructures such as sensor networks --- tends to be incomplete, imprecise, and erroneous, making it impossible to present it to users or feed it directly into applications. The traditional approach to dealing with this problem is to first process the data using statistical or probabilistic models that can provide more robust interpretations of the data. Current database systems, however, do not provide adequate support for applying models to such data, especially when those models need to be frequently updated as new data arrives in the system. Hence, most scientists and engineers who depend on models for managing their data do not use database systems for archival or querying at all; at best, databases serve as a persistent raw data store.In this paper we define a new abstraction called model-based views and present the architecture of MauveDB, the system we are building to support such views. Just as traditional database views provide logical data independence, model-based views provide independence from the details of the underlying data generating mechanism and hide the irregularities of the data by using models to present a consistent view to the users. MauveDB supports a declarative language for defining model-based views, allows declarative querying over such views using SQL, and supports several different materialization strategies and techniques to efficiently maintain them in the face of frequent updates. We have implemented a prototype system that currently supports views based on regression and interpolation, using the Apache Derby open source DBMS, and we present results that show the utility and performance benefits that can be obtained by supporting several different types of model-based views in a database system. <s> BIB004 </s> A Survey of Geosensor Networks: Advances in Dynamic Environmental Monitoring <s> Decentralized and Collaborative Spatial Computation <s> 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 algorithm 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. <s> BIB005 </s> A Survey of Geosensor Networks: Advances in Dynamic Environmental Monitoring <s> Decentralized and Collaborative Spatial Computation <s> Recent research on sensor networks has focused on the efficient processing of declarative SQL queries over sensor nodes. Users are often interested in querying an underlying continuous phenomenon such as a toxic plume, whereas only discrete readings of sensor nodes are available. Therefore, additional information estimation methods are necessary to process the sensor readings to generate the required query results. Most estimation methods are computationally intensive, even when computed in a traditional centralized setting. Furthermore, energy and communication constraints of sensor networks challenge the efficient application of established estimation methods in sensor networks. In this paper, we present an approach using Gaussian kernel estimation to process spatial window queries over continuous phenomena in sensor networks. The key contribution of our approach is the use of a small number of Hermite coefficients to approximate the Gaussian kernel function for subclustered sensor nodes. As a result, our algorithm reduces the size of messages transmitted in the network by logarithmic order, thus saving resources while still providing high-quality query results. <s> BIB006 </s> A Survey of Geosensor Networks: Advances in Dynamic Environmental Monitoring <s> Decentralized and Collaborative Spatial Computation <s> Wireless sensor networks (WSNs) can provide real-time information about geospatial environments, and so have the potential to play an important role in the monitoring of geographic phenomena. The research reported in this paper uses WSNs to provide salient information about spatially distributed dynamic fields, such as regional variations in temperature or concentration of a toxic gas. The focus is on topological changes to areas of high-activity that occur during the evolution of the field. Topological changes investigated include region merging and splitting, and hole formation or elimination. Such changes are formally characterized, and an algorithm is developed that detects such changes by means purely of in-network processing. The efficiency of this algorithm is investigated both theoretically and using simulation experiments. <s> BIB007
Due to the scale and limitations of wireless geosensor networks, the data processing paradigm changed fundamentally as mentioned before. Overall, the battery limitations and the objective of maximizing the application lifetime are driving the paradigm to collect data and detect events. The biggest energy sink is the use of the wireless radio communication, since sending data consumes about 800 times more energy than computing the same amount of data on the local chip BIB001 . Thus, design of algorithms is driven by the objective to minimize communication, i.e., the number of messages to be sent between nodes, and the size of the messages. Using a wireless sensor network purely as a raw data collector depletes batteries fast, because the data is forwarded in a multi-hop fashion between nodes to the network's base station. Each node in the network attaches its own raw data, and the message size increases with each network 'hop'. Thus, nodes close to the base station energy-deplete significantly faster compared to leaf nodes in the network. The general idea of the computational paradigm shift is to push the computation into the 'network'. Instead of forwarding large amounts of raw data to be analyzed outside of the sensor network, local processing and storage can be utilized to only forward 'interesting' data (e.g., data above or below a certain threshold) or events (e.g., a tremor of a volcano). Also, neighboring nodes collaborate on detecting 'interesting' data, collaboratively filter data, or detect local events (such as the boundary of a toxic plume and its motion). This is advantageous since events such as a contamination event is locally confined to one or several regions, and can be computed by the nodes deployed within the confines of the event, while distant nodes are irrelevant for the processing. Thus, the locality of events can be leveraged by local in-network computation and collaboration, which at the same time reduces communication since only spatially neighboring nodes exchange messages, and only local decision making is necessary. Typical types of spatio-temporal queries over geosensor network concern either continuous phenomena such as microclimates or event detection such as toxic plumes or wildfires. Many environmental phenomena, such as a microclimate within an orchard or a gas concentration in an open space are continuous. Sensor data samples, however, are discrete and point-based, and the resolution is based on the density of sensor nodes in the observation region. The challenge is to provide an accurate and precise estimation of the dynamic spatial field based on limited discrete point samples collected by the sensor nodes. Well-know data analysis and estimation techniques need to be redesigned to be lightweight and processed collaboratively 'in the network' while minimizing communication BIB005 BIB006 . Instead of estimating dynamic spatial fields quantitatively, for queries targeting to identify events such as detection of a toxic plume or the occurrence of a flood, finding the boundary of such a phenomenon can be sufficient. The boundary indicates the (dangerous) region of the event, and the user typically knows how to define the event (e.g., a chemical gas concentration above a certain threshold). Identifying only the boundaries and tracking their changes over time can save energy significantly since processing is localized to the boundary, and can be minimized or suppressed elsewhere in the network. Much work has been accomplished in the area of in-network boundary detection, and monitoring. Part of the work is focused on identifying boundary points  ; other work focuses on computing the geometry of the phenomena in the network BIB003 , and the third part of the work tracks changes of the object boundaries in the network BIB007   . The third aspect can be classified into approaches that a) identify the topology of the object boundary and track its topological changes (e.g., "does the toxic plume split?" "Do the Witch fire and Poway fire merge?") BIB007  , and b) approaches that track the geometric changes of the boundary incrementally in the network  . It is foreseeable that with the availability of more in-network algorithms of well-known spatial data analysis methods, geographic information systems (GIS) will disappear as a centralized data analysis tool for raw sensor data. Now, the "sensor network is the GIS"  . Another approach related to processing raw, noisy and sometimes missing sensor network data is to use model-based collection methods BIB002 BIB004 . Here, the user can define confidence values necessary for requested sensor data, and the in-network data acquisition algorithm takes those guarantees into account, i.e., automatically correlates data spatially or increases local sampling frequency. Several technical challenges with regard to the time synchronization of data sampling in sensor networks has been elucidated in the volcano deployment application. Here, the sensor network collected a rapid time series of data during a tremor; each sensor node produced a stream of data tuples including a location and time stamp. Once collected at the base station, the data tuples need to be sorted accurately to compute an event correctly. This is challenging since it is difficult to synchronize the local clock of all sensor nodes, which, however, is a vital aspect in this specific scenario. The second challenge is to be able to catch 'significant' triggering events to start a data collection, and e.g., not to catch a precursor event and miss the significant event occurring right afterwards. Thus, domain knowledge about the nature of volcano tremors needs to influence the programming.