【正文】 uation 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 optimal solution to the placement aspect of the task, we consider the minimum munication cost placement (MCP) problem. The MCP problem is that of minimizing the total amount of data municated among work nodes , which have been assigned one or more vertices of Q, during a single evaluation of Q. We show that the MCP problem is MAX SNPhard even when Q is a tree of height 1 with unit cost edges. We describe a simple and efficient greedy heuristic, which we call the GREEDYMCP algorithm, for the MCP problem ,and show practically useful cases under which GREEDYMCP finds provably optimal solutions to the MCP problem. To find a near optimal solution to the routing aspect of the task, we solve a maximum lifetime concurrent flow (MLCF) problem. The MLCF problem is the problem of maximizing the lifetime of a system that concurrently pushes flow to satisfy the data rate demands for a given set of source–destination pairs. We provide an efficient and simple algorithm for the MLCF problem, which we call the ALGRSMMLCF algorithm, that finds at most n + N paths that maximize the fractional system lifetime To for satisfying the concurrent flow data demands for N source–destination pairs in a work with n nodes. By rounding down that fractional solution, we get an aoptimal integral concurrent flow solution to the MLCF problem, where Since often in practice We experimentally show that ALGRSMMLCF outperforms existing routing algorithms that could be applied to the MLCF problem ,in terms of system life time and energy overhead. ALGRSMMLCF is an iterative algorithm based on the Revised Simplex Method (RSM). Our approach for the continuous inwork evaluation of query Q consists of using both GREEDYMCP and ALGRSMMLCF. First, we use GREEDYMCP to find a placement of Q on the work, and we use ALGRSMMLCF for routing all the data values that need to be municated. We show, through an extensive experimental evaluation, that our approach consistently finds the maximum lifetime solution for the continuous inwork evaluation of plex queries in wireless sensor works. Although we take a centralized approach to tackle the task at hand, we only require the knowledge of two work metadata – the work topology and the initial energy of sensors, which are very useful to many other work tasks as well. Note that the small size of the routing solution found by our approach limits the overhead of distributing the routing information to the sensors. In summary, for the task of continuous inwork processing of plex queries in wireless sensor works (WSNs), the original contributions of this paper are as follows: theoretically analyze the plexity of the MCP problem, the problem of placing expression DAGs on WSNs with minimum total munication cost. provide a greedy heuristic GREEDYMCP , for the MCP problem. GREEDYMCP finds provably optimal solutions in practical useful cases. provide a simple and effective algorithm, ALGRSMMLCF, that finds near optimal integral solutions to the maximum lifetime concurrent flow (MLCF) problem in WSNs . ALGRSMMLCF outperforms existing routing methods. 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. our approach, consisting of using GREEDYMCP and ALGRSMMLCF together is both effective and efficient at maximizing the system lifetime. The rest of the paper is organized as follows. We review related work in Section 2 , and then in Section 3 we give the necessary preliminaries. We describe our GREEDYMCP algorithm for the placement of expression DAGs into WSNs in Section 4, and show that GREEDYMCP finds optimal solutions to MCP problem instances under certain conditions . We analyze the plexity of the MCP problem in Section and show that the MCP problem is MAX SNPhard even for trees of height 1 and unit cost edged provided they have restricted vertices. We then turn our attention to the routing of operands, and we present our ALGRSMMLCF algorithm for the MLCF problem in Section 5. We discuss the results from our experimental evaluation of the proposed approach in Section 6. We conclude in Section 7. 2. Related work Pietzuch et al. [26] consider workaware operator placement in conventional distributed stream processing systems. In similar work settings, Ahmad et al. [1] give three operator placement algorithms for constructing a query processing overlay work and pare their performance