Resilient sensor network query processing using logical overlays

The typical nodes used in mote-level wireless sensor networks (WSNs) are often brittle and severely resource-constrained. In particular, nodes are often battery-powered, thereby making energy depletion a significant risk. When changes to the connectivity graph occur as a result of node failure, the overall computation may collapse unless it is capable of adapting to the new WSN state. Sensor network query processors (SNQPs) construe a WSN as a distributed, continuous query platform where the streams of sensed values constitute the logical extents of interest. Crucially, in the context of this paper, they must make assumptions about the connectivity graph of the WSN at compile time that are likely not to hold for the lifetime of the compiled query evaluation plan (QEP) the SNQPs generate. This paper addresses the problem of extending the lifetime of an evaluating QEP in the event of node failures. The basic idea is to derive an equivalence class over the nodes in the WSN that are equipotent for a given QEP and then to assign each QEP fragment instance to a set of equipotent nodes (rather than a single one). In this respect, the scheduling of QEP fragment instances is onto an overlay network of logical nodes, each of which maps to many physical nodes in the connectivity graph. We contribute a description of how this approach has been implemented in an existing SNQP and present experimental results indicating that it significantly increases the overall lifetime of a query whilst incurring small runtime adaptation costs. Copyright © 2012 ACM.