【正文】 we find that having near optimal solutions to the MLCF problem enables the decoupling of the placement and routing aspects of the task at hand. provide a greedy heuristic GREEDYMCP , for the MCP problem. GREEDYMCP finds provably optimal solutions in practical useful cases. 外文原文 Maximum lifetime continuous query processing in wireless sensor works Konstantinos Kalpakis* , Shilang Tang Computer Science and Electrical Engineering Department, University of Maryland, Baltimore ABSTRACT Monitoring applications emerge as one of the most important applications of wireless sensor works (WSNs). Such applications typically have longrunning plex queries that are continuously evaluated over the sensor measurement streams. Due to the limited energy of the sensors in WSNs , energy efficient query evaluation is critical to prolong the system lifetime – the earliest time that the work can not perform its intended task anymore. We model plex queries by expression trees and consider the problem of maximizing the lifetime of a wireless sensor work for the continuous in–work evaluation of an expression trees T , so the value of its root is available at the base station. Inwork evaluation means that the evaluation of the operators of T may be pushed to the work nodes, and continuous means the repeated evaluation of T (once at each round). Continuous inwork evaluation of T entails addressing the following two coupled aspects of the problem: (a) the placement of the operators, variables, and constants of T to work nodes and (b) the routing of their values to the appropriate work nodes that needed them to evaluate the operators. We analyze the plexity and provide a simple and effective algorithm for the placement of the nodes of T onto the sensor nodes of a WSN. Our algorithm of operator placement attempts to minimize the total amount of data that need to be municated. A placement of T induces a certain Maximum Lifetime Concurrent Flow (MLCF) problem. We provide an efficient algorithm that finds nearoptimal integral solutions to the MLCF problem, where a solution is a collection of paths on which certain amount of integral flow is routed. Our approach to the continuous inwork evaluation of T consists of utilizing both our placement and routing algorithms above. We demonstrate experimentally that our approach consistently and effectively find the maximum lifetime solutions for the continuous inwork evaluation of expression trees in wireless sensor works. 1. Introduction Remote monitoring applications are one of the most attractive applications of wireless sensor works. Such applications, like environmental monitoring and building surveillance, normally have long running queries over the data streams that are continuously generated by sensors near the points of interest. For example, one such query can be found in volcano monitoring application – report the current activity level every five minutes, which is measured by processing and correlating the data streams generated by sensors on surface vibration, air pressure and temperature, gas density change, magic variance, and etc. How to energy efficiently process these longrunning queries is a critical problem to the success of the deployment and operation of wireless sensor works, since often replenishing the energy of the sensors by replacing their batteries is cost prohibitive or even infeasible. In this paper, we consider the task of the continuous evaluation of longrunning plex queries in wireless sensor works. Such queries have multiple functiondependent operators and require repeated evaluation once per each round. Due to the disparity between the amount of data generated by the sensors and the amount of data the work can municate before the sensors deplete their energy, we aim to push the queries into the work for processing [18]. We model a query with a rooted expression directed acyclic graph (DAG) Q, whose internal nodes are operators (functions) with children as their operands, and its leaves are constants or variables. Each vertex of Q has a size for its value and a set of candidate work nodes to which it may be placed. Each variable vertex of Q has a set of source sensor nodes, whose measurements are used to assign values to that variable. The continuous inwork evaluation of a rooted expression DAG Q entails addressing the following two aspects of the task: (a) the placement of the operators, variables, and constants of Q to work nodes, and (b) the routing of the operand values to the appropriate work nodes that needed them to evaluate the operators. These two aspects are coupled because the placement of Q imposes certain source–destination routing requirements among the sensor nodes, and the manner in which routing is performed can have a major impact on placement decisions. While there are many important optimization goals for the continuous inwork evaluation of queries (. response time, reliability, etc.), we focus on maximizing the system lifetime – the time until the sensor work losses its ability to perform its intended task due to depletion of energy at (some of) its sensors, and analyze how to decouple the two aspects of the task at hand. We find, as shown in our experimental evaluation, that having a near optimal solution to the routing aspect effectively decouples the routing and placement aspects, and therefore allows us to solve these two aspects one at a time. To find a near op