UCAM-CL-TR-783 ISSN 1476-2986
Distributed Complex Event Detection for Pervasive Computing Dan O’Keeffe
15 JJ Thomson Avenue Cambridge CB3 0FD United Kingdom phone +44 1223 763500 http://www.cl.cam.ac.uk/
c 2010 Dan O’Keeffe
This technical report is based on a dissertation submitted December 2009 by the author for the degree of Doctor of Philosophy to the University of Cambridge, St. John’s College. Technical reports published by the University of Cambridge Computer Laboratory are freely available via the Internet: http://www.cl.cam.ac.uk/techreports/ ISSN 1476-2986
Pervasive computing is a model of information processing that augments computers with sensing capabilities and distributes them into the environment. Many pervasive computing applications are reactive in nature, in that they perform actions in response to events (i.e. changes in state of the environment). However, these applications are typically interested in high-level complex events, in contrast to the low-level primitive events produced by sensors. The goal of this thesis is to support the detection of complex events by filtering, aggregating, and combining primitive events. Supporting complex event detection in pervasive computing environments is a challenging problem. Sensors may have limited processing, storage, and communication capabilities. In addition, battery powered sensing devices have limited energy resources. Since they are embedded in the environment, recharging may be difficult or impossible. To prolong the lifetime of the system, it is vital that these energy resources are used efficiently. Further complications arise due to the distributed nature of pervasive computing systems. The lack of a global clock can make it impossible to order events from different sources. Events may be delayed or lost en route to their destination, making it difficult to perform timely and accurate complex event detection. Finally, pervasive computing systems may be large, both geographically and in terms of the number of sensors. Architectures to support pervasive computing applications should therefore be highly scalable. We make several contributions in this dissertation. Firstly, we present a flexible language for specifying complex event patterns. The language provides developers with a variety of parameters to control the detection process, and is designed for use in an open distributed environment. Secondly, we provide the ability for applications to specify a variety of detection policies. These policies allow the system to determine the best way of handling lost and delayed events. Of particular interest is our ‘no false-positive’ detection policy. This allows a reduction in detection latency while ensuring that only correct events are generated for applications sensitive to false positives. Finally, we show how complex event detector placement can be optimized over a federated event-based middleware. In many cases, detector distribution can reduce unnecessary communication with resource constrained sensors.
To my family
To begin with, I would like to thank Jean Bacon, my supervisor, for all her encouragement and advice during the course of my PhD. In reaching the finish line, her knowledge and understanding (and patience!) have been invaluable. I am also indebted to Ken Moody, my PhD advisor, for the guidance he has given me throughout the time of my PhD. During my PhD I was fortunate enough to be a member of the Opera Group, and my research owes a debt to the many interesting discussions, talks, and ideas I was exposed to as a result. In particular, I would like to thank Salman Taherian, Peter Pietzuch, Eiko Yoneki, Dave Eyers, Jat Singh, Lauri Pesonen, Sriram Srinivasan, Pedro Brandao, Dave Evans, Dave Ingram, Luis Vargas, and Samuel Kounev for all their help over the years. I would like to also thank Salman,