Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/9710
Title: Predicate detection in asynchronous pervasive environments
Authors: Kshemkalyani, AD
Cao, J 
Keywords: Distributed system
Middleware
Pervasive computing
Predicate detection
Sensor networks
Strobe clocks
Issue Date: 2013
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on computers, 2013, v. 62, no. 9, 6226372, p. 1823-1836 How to cite?
Journal: IEEE transactions on computers 
Abstract: 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(n3p)). 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(n2p)) 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.
URI: http://hdl.handle.net/10397/9710
ISSN: 0018-9340
EISSN: 1557-9956
DOI: 10.1109/TC.2012.162
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

3
Last Week
0
Last month
0
Citations as of Aug 18, 2017

WEB OF SCIENCETM
Citations

3
Last Week
0
Last month
1
Citations as of Aug 15, 2017

Page view(s)

30
Last Week
1
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.