Predicate Detection in Asynchronous Pervasive Environments

An important task in sensor networks is to sense locally to detect global properties that hold at some instant in physical time, namely, Instantaneously. We propose software logical clocks, called strobe clocks, that can be implemented by the middleware when synchronized physical clocks are not available or are too expensive in resource-constrained environments. Strobe clocks come in two flavors--scalar and vector. Let (n) be the number of sensors and (p) be the upper bound on the number of relevant events sensed at a sensor. We propose an algorithm using vector strobes that can detect all occurrences of a conjunctive predicate in time (O(n³p)). The algorithm has some false negatives but this is the best achievable accuracy in the face of race conditions. We also present a variant algorithm using scalar strobes; it needs time (O(n²p)) but may also suffer from some false positives. We provide a characterization of the errors. Both algorithms can also detect relational predicates but with a greater chance of error. The message complexity of strobe clocks (scalar and vector) and both algorithms is (O(np)), which is the same as that of reporting each sensed event for detection of the predicate even with synchronized physical clocks. We formalize the physical time modality, Instantaneously, and show its relationship to the logical time modalities Definitely and Possibly.