maximum lifetime continuous query processing in wireless sensor networks

1、Maximum Lifetime Continuous Query Processing in Wireless Sensor NetworksKonstantinos Kalpakis?,a, Shilang TangaaComputer Science & Electrical Engineering Department University of Maryland Baltimore CountyAbstractMoni

2、toring applications emerge as one of the most important applications of wireless sensornetworks (WSNs). Such applications typically have long–running complex queries that are contin-uously evaluated over the sensor measu

3、rement streams. Due to the limited energy of the sensors inWSNs, energy efficient query evaluation is critical to prolong the system lifetime — the earliest timethat the network can not perform its intended task anymore.

4、We model complex queries by expression trees and consider the problem of maximizing thelifetime of a wireless sensor network for the continuous in–network evaluation of an expressiontrees T , so the value of its root is

5、available at the base station. In–network evaluation means thatthe evaluation of the operators of T may be pushed to the network nodes, and continuous meansthe repeated evaluation of T (once at each round). Continuous in

6、–network evaluation of T entailsaddressing the following two coupled aspects of the problem: (a) the placement of the operators,variables, and constants of T to network nodes, and (b) the routing of their values to the a

7、ppropriatenetwork nodes that needed them to evaluate the operators.We analyze the complexity and provide a simple and effective algorithm for the placement ofthe nodes of T onto the sensor nodes of a WSN. Our algorithm o

8、f operator placement attemptsto minimize the total amount of data that need to be communicated. A placement of T induces acertain Maximum Lifetime Concurrent–Flow (MLCF) problem. We provide an efficient algorithmthat fin

9、ds near–optimal integral solutions to the MLCF problem, where a solution is a collection ofpaths on which certain amount of integral flow is routed. Our approach to the continuous in–networkevaluation of T consists of ut

10、ilizing both our placement and routing algorithms above.?Corresponding author. Email addresses: kalpakis@csee.umbc.edu (Konstantinos Kalpakis), stang2@csee.umbc.edu (Shilang Tang)Preprint submitted to Ad Hoc Networks Feb

11、ruary 7, 2010which routing is performed can have a major impact on placement decisions.While there are many important optimization goals for the continuous in–network evaluation ofqueries (eg. response time, reliability,

12、 etc), we focus on maximizing the system lifetime — the timeuntil the sensor network 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

13、 aspects of the task at hand. We find,as shown in our experimental evaluation, that having a near optimal solution to the routing aspecteffectively decouples the routing and placement aspects, and therefore allows us to

14、solve these twoaspects one at a time.To find a near optimal solution to the placement aspect of the task, we consider the minimumcommunication cost placement (MCP) problem. The MCP problem is that of minimizing the total

15、amount of data communicated among network nodes, which have been assigned one or more verticesof Q, during a single evaluation of Q. We show that the MCP problem is MAX–SNP hard even whenQ is a tree of height 1 with unit

16、 cost edges. We describe a simple and efficient greedy heuristic, whichwe call the GREEDYMCP algorithm, for the MCP problem, and show practically useful cases underwhich GREEDYMCP finds provably optimal solutions to the

17、MCP problem.To find a near optimal solution to the routing aspect of the task, we solve a maximum lifetimeconcurrent flow (MLCF) problem. The MLCF problem is the problem of maximizing the lifetimeof a system that concurr

18、ently 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 wecall the ALGRSM–MLCF algorithm, that finds at mos

19、t n + N paths that maximize the fractionalsystem lifetime To for satisfying the concurrent flow data demands for N source–destination pairsin a network with n nodes. By rounding down that fractional solution, we get an α

20、–optimal integralconcurrent flow solution to the MLCF problem, where α = (To ? n ? N + 1)/To. Since often inpractice To ? n + N, α ≈ 1. We experimentally show that ALGRSM–MLCF outperforms existingrouting algorithms that

21、could be applied to the MLCF problem, in terms of system lifetime andenergy overhead. ALGRSM–MLCF is an iterative algorithm based on the Revised Simplex Method(RSM).Our approach for the continuous in–network evaluation o

22、f query Q consists of using both GREEDYMCPand ALGRSM–MLCF. First, we use GREEDYMCP to find a placement of Q on the network, andwe use ALGRSM–MLCF for routing all the data values that need to be communicated. We show,thro