The widespread dissemination of small-scale sensor nodes has sparked interest in a powerful new database abstraction for sensor networks: Clients "program" the sensors through queries in a high-level declarative language (such as a variant of SQL) permitting the system to perform the low-level optimizations necessary for energyefficient query processing. In this paper we consider multi-query optimization for aggregate queries on sensor networks. We develop a set of distributed algorithms for processing multiple queries that incur minimum communication while observing the computational limitations of the sensor nodes. Our algorithms support incremental changes to the set of active queries and allow for local repairs to routes in response to node failures. A thorough experimental analysis shows that our approach results in significant energy savings, compared to previous work. Wireless sensor networks consisting of small nodes with sensing, computation and communication capabilities will soon be ubiquitous. Such networks have resource constraints on communication, computation, and energy consumption. First, the bandwidth of wireless links connecting sensor nodes is usually limited, on the order of a few hundred Kbps, and the wireless network that connects the sensors provides only limited quality of service, with variable latency and dropped packets. Second, sensor nodes have limited computing power and memory sizes that restrict the types of data processing algorithms that can be deployed. Third, wireless sensors have limited supply of energy, and thus energy conservation is a major system design consideration. Recently, a database approach to programming sensor networks has gained [7] , where the sensors are programmed through declarative queries in a variant of SQL. Since energy is a highly valuable resource and communication consumes most of the available power of a sensor network, recent research has focused on devising query processing strategies, like in-network aggregation, that reduce the amount of data propagated in the network. Our Model and Assumptions. We assume that nodes are stationary and battery-powered, and thus severely energy constrained. We distinguish a special type of node, referred to as a gateway node, where users inject query requests. The raw data generated at a sensor node is produced by one or more attached physical sensors. Sensor nodes generate new readings either at regular intervals (such as polling a temperature sensor every minute) or irregularly (such as a motion sensor detecting movement). The sensor network is programmed through declarative queries posed in a variant of SQL or an event-based language [5] . We concentrate on aggregation queries, and the sensor network performs in-network aggregation while routing data from source sensors through intermediate nodes to the gateway. Existing work has focussed on the execution of a single long-running aggregation query. In our new usage model, we allow multiple users to pose both long-running and snapshot queries (i.e. queries executed once). As new queries occur, they are not sent immediately to the network for evaluation, but are gathered at the gateway node into batches and are dispatched for evaluation once every epoch. The query optimizer groups together queries with the same aggregate operator and optimizes each group separately. Hence, in our presentation of our optimization techniques, we assume that queries use the same aggregate operator. Each epoch consists of a query preparation (QP) and a result propagation (RP) phase. In the QP phase, all queries gathered during the previous epoch are sent to the network together for evaluation. In the RP phase, query answers are forwarded back to the gateway. An example query workload is illustrated in Figure 1 . Request r ij represents the jth result of query q i . Queries q 1 and q 2 are presented in the first QP, while q 3 and q 4 are presented in the second. Query q 1 is active during the second epoch, while q 2 terminates after the first epoch. Notice that our model
In REF the authors consider multi-query optimization for aggregate queries on sensor networks by developing a set of distributed algorithms.
Multi-query optimization for sensor networks
In DCOSS
Computer Science