=Paper=
{{Paper
|id=None
|storemode=property
|title=Complex Event Processing in Wireless Sensor Networks
|pdfUrl=https://ceur-ws.org/Vol-1020/paper_12.pdf
|volume=Vol-1020
|dblpUrl=https://dblp.org/rec/conf/gvd/Saleh13
}}
==Complex Event Processing in Wireless Sensor Networks==
https://ceur-ws.org/Vol-1020/paper_12.pdf
Complex Event Processing in Wireless Sensor Networks
Omran Saleh
Faculty of Computer Science and Automation
Ilmenau University of Technology
Ilmenau, Germany
omran.saleh@tu-ilmenau.de
ABSTRACT itored region. These nodes can sense the surrounding envi-
Most of the WSN applications need the number of sensor ronment and share the information with their neighboring
nodes deployed to be in order of hundreds, thousands or nodes. They are gaining adoption on an increasing scale
more to monitor certain phenomena and capture measure- for tracking and monitoring purposes. Furthermore, sensor
ments over a long period of time. The large volume of sensor nodes are often used in control purposes. They are capable
networks would generate continuous streams of raw events1 of performing simple processing.
in case of centralized architecture, in which the sensor data In the near future, it is prospective that wireless sensor
captured by all the sensor nodes is sent to a central entity. networks will offer and make conceivable a wide range of
In this paper, we describe the design and implementation applications and emerge as an important area of comput-
of a system that carries out complex event detection queries ing. WSN technology is exciting with boundless potential for
inside wireless sensor nodes. These queries filter and re- various application areas. They are now found in many in-
move undesirable events. They can detect complex events dustrial and civilian application areas, military and security
and meaningful information by combining raw events with applications, environmental monitoring, disaster prevention
logical and temporal relationship, and output this informa- and health care applications, etc.
tion to external monitoring application for further analysis. One of the most important issues in the design of WSNs
This system reduces the amount of data that needs to be is energy efficiency. Each node should be as energy effi-
sent to the central entity by avoiding transmitting the raw cient as possible. Processing a chunk of information is less
data outside the network. Therefore, it can dramatically re- costly than wireless communication; the ratio between them
duce the communication burden between nodes and improve is commonly supposed to be much smaller than one [19].
the lifetime of sensor networks. There is a significant link between energy efficiency and su-
We have implemented our approach for the TinyOS Oper- perfluous data. The sensor node is going to consume unnec-
ating System, for the TelosB and Mica2 platforms. We con- essary energy for the transmission of superfluous data to the
ducted a performance evaluation of our method comparing central entity, which means minimizing the energy efficiency.
it with a naive method. Results clearly confirm the effec- Furthermore, traditional WSN software systems do not
tiveness of our approach. apparently aim at efficient processing of continuous data or
event streams. According to previous notions, we are looking
for an approach that makes our system gains high perfor-
Keywords mance and power saving via preventing the generation and
Complex Event Processing, Wireless Sensor Networks, In- transmission of needless data to the central entity. There-
network processing, centralized processing, Non-deterministic fore, it can dramatically reduce the communication burden
Finite state Automata between nodes and improve the lifetime of sensor networks.
This approach takes into account the resource limitations in
1. INTRODUCTION terms of computation power, memory, and communication.
Sensor nodes can employ their processing capabilities to per-
Wireless sensor networks are defined as a distributed and
form some computations. Therefore, an in-network complex
cooperative network of devices, denoted as sensor nodes that
event processing 2 based solution is proposed.
are densely deployed over a region especially in harsh envi-
We have proposed to run a complex event processing en-
ronments to gather data for some phenomena in this mon-
gine inside the sensor nodes. CEP engine is implemented
1
The terms data, events and tuples are used interchangeably. to transform the raw data into meaningful and beneficial
events that are to be notified to the users after detecting
them. It is responsible for combining primitive events to
identify higher level complex events. This engine provides
an efficient Non-deterministic Finite state Automata (NFA)
[1] based implementation to lead the evaluation of the com-
plex event queries where the automaton runs as an integral
part of the in-network query plan. It also provides the the-
25th GI-Workshop on Foundations of Databases (Grundlagen von Daten-
oretical basis of CEP as well as supports us with particular
banken), 28.05.2013 - 31.05.2013, Ilmenau, Germany. 2
Copyright is held by the author/owner(s). CEP is discussed in reference [15]
operators (conjunction, negation, disjunction and sequence of active databases. Most of the models in these engines
operators, etc.). are based on fixed data structures such as tree, graph, fi-
Complex event processing over data stream has increas- nite automaton or petri net. The authors of [6] used a tree
ingly become an important field due to the increasing num- based model. Paper [9] used petri net based model to de-
ber of its applications for wireless sensor networks. There tect complex events from active database. Reference [17]
have been various event detection applications proposed in used Timed Petri-Net (TPN) to detect complex events from
the WSNs, e.g. for detecting eruptions of volcanoes [18], RFID stream.
forest fires, and for the habitat monitoring of animals [5].
An increasing number of applications in such networks is
confronted with the necessity to process voluminous data
3. RELATED WORKS
streams in real time fashion. It is preferable to perform In-Network Processing in-
The rest of the paper is organized as follows: section 2 pro- side sensor network to reduce the transmission cost between
vides an overview of the naive approaches for normal data neighboring nodes. This concept is proposed by several sys-
and complex event processing in WSNs. Related works are tems such as TinyDB [16], and Cougar [19]. Cougar project
briefly reviewed in section 3. Then we introduce the overall applies a database system concept to sensor networks. It
system architecture in order to perform complex event pro- uses the declarative queries that are similar to SQL to query
cessing in sensor networks in section 4. Section 5 discusses sensor nodes. Additionally, sensor data in cougar is consid-
how to create logical query plans to evaluate sensor portion ered like a “virtual” relational database. Cougar places on
queries. Section 6 explains our approach and how queries are each node an additional query layer that lies between the
implemented by automata. In section 7, the performance of network and application layers which has the responsibility
our system is evaluated using a particular simulator. Fi- of in-network processing. This system generates one plan for
nally, section 8 presents our concluding remarks and future the leader node to perform aggregation and send the data to
works. a sink node. Another plan is generated for non-leader nodes
to measure the sensors status. The query plans are dissem-
inated to the query layers of all sensor nodes. The query
2. NAIVE APPROACHES IN WSNS layer will register the plan inside the sensor node, enable
The ideas behind naive approaches which are definitely desired sensors, and return results according to this plan.
different from our approach lie in the processing of data as TinyDB is an acquisitional query processing system for
the central architectural concept. For normal sensor data sensor networks which maintains a single, infinitely-long vir-
processing, the centralized approach proceeds in two steps; tual database table. It uses an SQL-like interface to ask for
the sensor data captured by all the sensor nodes is sent to data from the network. In this system, users specify the
the sink node and then routed to the central server (base data they want and the rate at which the data should be
station) where it is stored in centralized database. High vol- refreshed, and the underlying system would decide the best
ume data are arriving at the server. Subsequently, query plan to be executed. Several in-network aggregation tech-
processing takes place on this database by running queries niques have been proposed in order to extend the life time
against stored data. Each query executes one time and re- of sensor network such as tree-based aggregation protocols
turns a set of results. i.e., directed diffusion.
Another approach which adopts the idea of centralized Paper [13] proposes a framework to detect complex events
architecture is the use of a central data stream management in wireless sensor networks by transforming them into sub-
system (DSMS), which simply takes the sensor data stream events. In this case, the sub-events can easily be detected
as input source. Sending all sensor readings to DSMS is also by sensor nodes. Reference [14] splits queries into server and
an option for WSN data processing. DSMS is defined as a node queries, where each query can be executed. The final
system that manages a data stream, executes a continuous results from both sides are combined by the results merger.
query against a data stream and supports on-line analysis In [20], symbolic aggregate approximation (SAX) is used to
of rapidly changing data streams [10]. Traditional stream transform sensor data to symbolic representations. To de-
processing systems such as Aurora [2], NiagraCQ [7], and tect complex events, a distance metric for string comparison
AnduIN [12] extend the relational query processing to work is utilized. These papers are the closer works to our system.
with stream data. Generally the select, project, join and Obviously, there is currently little work into how the idea
aggregate operations are supported in these stream systems. of in-network processing can be extended and implemented
The naive approach for Complex Event Processing in to allow more complex event queries to be resolved within
WSNs is similar to the central architectural idea of normal the network.
data processing, but instead of using traditional database
and data stream engine, CEP uses a dedicated engine for
processing complex events such as Esper [8], SASE [11] and 4. SYSTEM ARCHITECTURE
Cayuga [4], in which sensor data or events streams need to We have proposed a system architecture in which collected
be filtered, aggregated, processed and analyzed to find the data at numerous, inexpensive sensor nodes are processed
events of interest and identify some patterns among them, locally. The resulting information is transmitted to larger,
finally take actions if needed. more capable and more expensive nodes for further analysis
Reference [11] uses SASE in order to process RFID stream and processing through specific node called sink node.
data for a real-world retail management scenario. Paper [3] The architecture has three main parts that need to be
demonstrates the use of Esper engine for object detection modified or created to make our system better suited to
tracking in sensor networks. All the aforementioned engines queries over sensor nodes: 1- Server side: queries will be
use some variant of a NFA model to detect the complex originated at server side and then forwarded to the near-
event. Moreover, there are many CEP engines in the field est sink node. Additionally, this side mainly contains an
application that runs on the user’s PC (base station). Its
main purpose is to collect the results stream over the sen-
sor network and display them. Server side application can
offer more functions i.e., further filtering for the collected
data, perform joining on sensor data, extract, save, man-
age, and search the semantic information and apply further
complex event processing on incoming events after process-
ing them locally in sensor nodes. Because sensor data can
be considered as a data stream, we proposed to use a data
stream management system to play a role of server side, for
that we selected AnduIN data stream engine. 2- Sink side:
sink node (also known as root or gateway node) is one of the
motes in the network which communicates with the base sta-
tion directly, all the data collected by sensors is forwarded
to a sink node and then to server side. This node will be
in charge of disseminating the query down to all the sensor Figure 1: Logical query plan
nodes in the network that comes from server side. 3- Node
side: in this side, we have made huge changes to the tra-
ditional application which runs on the nodes themselves to mechanism takes as input primitive events from lower oper-
enable database manner queries involving filters, aggregates, ators and detects occurrences of composite events which are
complex event processing operator (engine) and other oper- used as an output to the rest of the system.
ators to be slightly executed within sensor networks. These
changes are done in order to reduce communication costs 6. IN-NETWORK CEP SYSTEM
and get useful information instead of raw data. Various applications including WSNs require the ability to
When combining on-sensor portions of the query with the handle complex events among apparently unrelated events
server side query, most of the pieces of the sensor data query and find interesting and/or special patterns. Users want
are in place. This makes our system more advanced. to be notified immediately as soon as these complex events
are detected. Sensor node devices generate massive sensor
5. LOGICAL PLAN data streams. These streams generate a variety of primitive
Each and every sensor node of a network generates tu- events continuously. The continuous events form a sequence
ples. Every tuple may consist of information about the node of primitive events, and recognition of the sequence supplies
id, and sensor readings. Query plan can specify the tuples us a high level event, which the users are interested in.
flow between all necessary operators and a precise computa- Sensor event streams have to be automatically filtered,
tion plan for each sensor node. Figure 1 (lower plan) illus- processed, and transformed into significative information.
trates how our query plan can be employed. It corresponds In non-centralized architecture, CEP has to be performed
to an acyclic directed graph of operators. We assume the as close to real time as possible (inside the node). The task
dataflow being upward. At the bottom, there is a homo- of identifying composite events from primitive ones is per-
geneous data source which generates data tuples that must formed by the Complex Event Processing engine. CEP en-
be processed by operators belonging to query plans. Tu- gine provides the runtime to perform complex event process-
ples are flowed through intermediate operators composed in ing where they accept queries provided by the user, match
the query graph. The operators perform the actual process- those queries against continuous event streams, and trigger
ing and eventually forward the data to the sink operator an event or an execution when the conditions specified in
for transmitting the resulting information to the server side the queries have been satisfied. The idea of this concept is
(base station). These operators adopt publish/subscribe close to Event-Condition-Action (ECA) concept in conven-
mechanism to transfer tuples from one operator to next op- tional database systems where an action has to be carried
erator. out in response to an event and one or more conditions are
We differ between three different types of operators within satisfied.
a query graph [12]: 1- Source operator: produces tuples Each data tuple from the sensor node is viewed as a prim-
and transfers them to other operators. 2- Sink operator: itive event and it has to be processed inside the node. We
receives incoming tuples from other operators. 3- Inner have proposed an event detection system that specifically
operators: receive incoming tuples from source operator, targets applications with limited resources, such in our sys-
process them, and transfer the result to sink operator or tem. There are four phases for complex event processing
other inner operators. in our in-network model: NFA creation, Filtering, Sequence
A query plan consists of one source at the bottom of a scan and Response as shown in figure 2.
logical query graph, several inner operators, and one sink
at the top and the tuples are flowing strictly upward. In 6.1 NFA Creation Phase
our system, we have extended this plan to give the system The first phase is NFA creation. NFA’s structure is cre-
the capability to perform the complex event processing and ated by the translation from the sequence pattern through
detecting by adding new operators. We have separated the mapping the events to NFA states and edges, where the con-
mechanism for detecting complex events from the rest of ditions of the events (generally called event types) are asso-
normal processing side. We have a particular component ciated with edges. For pattern matching over sensor node
working as an extra operator or engine within the main pro- streams, NFA is employed to represent the structure of an
cess, as we can see from figure 1 (upper plan). The detection event sequence. For a concrete example, consider the query
Figure 2: CEP Phases
Figure 4: Sequence Scan for SEQ (A, B+, D) within
6 Time Unit Using UNRESTRICTED Mode
Figure 3: NFA for SEQ(A a, B+ b, C c)
is waiting for the arrival of events in its starting state. Once
a new instance event e arrives, the sequence scan responds
pattern: SEQ(A a, B+ b, C c)3 . Figure 3 shows the NFA as follows: 1- It checks whether the type of instance (from
created for the aforementioned pattern (A, B+, C), where attributes) and occurrence time of e satisfy a transition for
state S0 is the starting state, state S1 is for the successful one of the logical existing sequences. If not, the event is
detection of an A event, state S2 is for the detection of a B directly rejected. 2- If yes, e is registered in the system (the
event after event A, also state S3 is for the detection of a C registration is done in the sliding window) and the sequence
event after the B event. State S1 contains a self-loop with advances to next state. 3- If e allows for a sequence to move
the condition of a B event. State S3 is the accepting state, from the starting state to next state, the engine will create
reaching this state indicates that the sequence is detected. other logical sequence to process further incoming events
while keeping the original sequence in its current state to
6.2 Filtering Phase receive new event. Therefore, multiple sequences work on
The second phase is to filter primitive events at early the events at the same time. 4- Delete some sequences when
stage, generated by sensor nodes. Sensor nodes cannot un- their last received items are not within a time limit. It be-
derstand whether a particular event is necessary or not. comes impossible for them to proceed to the next state since
When additional conditions are added to the system, possi- the time limits for future transitions have already expired.
ble event instances might be pruned at the first stage. Next, we use an example to illustrate how UNRESTRICTED
After filtering, timestamp operator will add the occur- sequence scan works. Suppose we have the following pat-
rence time of the event t. A new operator is designed for tern4 SEQ (A, B+, D) and sequence of events (tuples)
adding a timestamp t to the events (tuples) before entering presented as [a1, b2, a3, c4, c5, b6, d7 ...] within 6 time
the complex event processing operator. We can notice that unit. Figure 4 shows, step by step, how the aforementioned
from figure 1. The timestamp attribute value of an event events are processed. Once the sequence has reached the
t records the reading of a clock in the system in which the accepting state (F ), the occurrences of SEQ (A, B+, D)
event was created, in this case it can reflect the true order will be established at : {{a1, b2, d7 }, {a1, b6, d7 },
of the occurrences of primitive events. {a3, b6, d7 }}.
The drawback of this mode is the use of high storage to
6.3 Sequence Scan Phase accumulate all the events that participate in the combina-
The third phase is sequence scan to detect a pattern match. tions in addition to computation overhead for the detection.
We have three modes state the way in which events may con- It consumes more energy. On other hand, it gives us all the
tribute to scan a sequence: UNRESTRICTED, RECENT possibilities of event combination which can be used (e.g.
and FIRST. Every mode has a different behavior. The selec- for further analysis). In our system, we only output one of
tion between them depends on the users and the application these possibilities to reduce transmission cost overhead. All
domain. These modes have advantages and disadvantages. registered events are stored in a sliding window. Once the
We will illustrate them below. overflow has occurred, the candidate events would be the
In the UNRESTRICTED mode, each start event e, which newest registered ones from the first sequence. The engine
allows a sequence to move from the initial state to the next will continue to replace the events from the first sequence as
state, starts a separate sequence detection. In this case any long as there is no space. When the initial event (first event
event occurrence combination that matches the definition of in the first sequence combination) is replaced, the engine
the sequence can be considered as an output. By using this starts the replacement from the second sequence and so on.
mode, we can get all the possibilities of event combination The engine applies this replacement policy to ensure that
which satisfy the sequence. When the sequence is created, it the system still has several sequences to detect a composite
event, because replacing the initial events would destroy the
3
Notice: In this paper, we are going to only focus on se-
4
quence operator SEQ because of the limited number of The terms complex event, composite event, pattern and
pages. sequence are used interchangeably.
Figure 5: First and Recent Modes
whole sequence. Figure 6: Total Energy Consumption
In the FIRST mode, the earliest occurrence of each con-
tributing event type is used to form the composite event
output. Only the first event from a group of events which ing the in-network complex event processing techniques as
have the same type advances the sequence to the next state. well as base station functionality, is written in TinyOS. Our
In this mode, we have just one sequence in the system. The code runs successfully on both real motes and the TinyOS
automaton engine will examine every incoming instance e, Avrora simulator. The aim of the proposed work is to com-
whether the type of it and occurrence time of e satisfy a pare the performance of our system, in-network processor
transition from the current state to next state. If it is, the which includes complex event engine in comparison with
sequence will register the event in the current state and ad- centralized approach in wireless sensor networks and to as-
vance to next state. If not, the event is directly rejected. sess the suitability of our approach in an environment where
Suppose we have the following pattern SEQ (A, B+, C+, resources are limited. The comparison would be done in
D) and sequence of tuples presented as [a1, a2, b3, c4, c5, terms of energy efficiency (amount of energy consumed) and
b6, d7 ...] within 6 time unit. The result as shown in the the number of messages transmitted per particular interval,
upper part of figure 5 . in the entire network. The experiment was run for varying
In the RECENT mode (as the lower part of figure 5 which the SEQ length. We started with length 2 then 3 and finally
has FIRST pattern and the same sequence of tuples), the 5. Simulations were run for 60 seconds with one event per
most recent event occurrences of contributing event types second. The performance for different SEQ lengths and dif-
are used to form the composite event. In RECENT mode, ferent modes with a network of 75 nodes is shown in figure 6.
once an instance satisfies the condition and timing constraint The centralized architecture led to higher energy consump-
to jump from a state to next state, the engine will stay in tion because sensor nodes transmitted events to the sink
the current state unlike FIRST mode. This mode tries to node at regular periods. In our system, we used in-network
find the most recent instance from consecutive instances for complex event processing to decrease the number of trans-
that state before moving to next state. When a1 enters the missions of needless events at each sensor node. What we
engine. It satisfies the condition to move from S0 to S1. can notice from figure 6 is summarized as: 1- By increasing
The engine registers it, stays in S0 and does not jump to the SEQ length in our approach, the RAM size is increased
the next state. Perhaps the new incoming instance is more while energy consumption is reduced. The reason is: the
recent from the last one in the current state. transmission will not occur until the sequence reaches the
The advantages of FIRST and RECENT modes are the accepting state, few events (tuples) will be relatively satis-
use of less storage to accumulate all the events that partic- fied. Hence, the number of transmissions after detections
ipate in the combinations. Only a few events will be regis- will be decreased. 2- FIRST is a little bit better than RE-
tered in the system in addition to low computation overhead CENT, and both of them are better than UNRESTRICTED
for the detection. They consume less energy. Unlike UNRE- in energy consumption. The gap between them is resulting
STRICTED, they do not give all possible matches. from processing energy consumption, that is because UN-
RESTRICTED needs more processing power while the other
6.4 Response Phase needs less, as shown in figure 6.
Figure 7 shows the radio energy consumption for each
Once an accepting state F is reached by the engine, the
sensor node and the total number of messages when SEQ
engine should immediately output the event sequence. This
length was 3. The nodes in the centralized architecture sent
phase is responsible for preparing the output sequence to
more messages than our approach (nearly three times more).
pass it to the sink operator. The output sequence depends
Hence, it consumed more radio energy. Additionally, the
on the mode of the scan. This phase will start to create
gateway nodes consumed more radio energy due to receiv-
the response by reading the sliding window contents. In
ing and processing the messages from other sensor nodes.
case of FIRST and RECENT modes, the sliding window
In a 25 nodes network, the centralized approach consumed
contains only the events which contribute in sequence de-
energy nearly 4203mJ in sink side, while our approach con-
tection. In UNRESTRICTED mode, the engine randomly
sumed around 2811mJ. Thus, our system conserved nearly
selects a combination of events which matches the pattern
1392mJ (33% of the centralized approach) of the energy. In
in order to reduce transmission cost.
our architecture, the number of transmissions was reduced.
Therefore, the radio energy consumption is reduced not only
7. EVALUATION at the sensor nodes but also at the sink nodes.
We have completed an initial in-network complex event
processing implementation. All the source code, implement- 8. CONCLUSIONS
In ACM SIGMOD, pages 1100–1102, New York, NY,
USA, 2007. ACM.
[5] A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton,
and J. Zhao. Habitat monitoring: application driver
for wireless communications technology. SIGCOMM
Comput. Commun. Rev., 31(2 supplement):20–41,
Apr. 2001.
[6] S. Chakravarthy, V. Krishnaprasad, E. Anwar, and
S.-K. Kim. Composite events for active databases:
semantics, contexts and detection. In Proceedings of
the 20th International Conference on Very Large Data
Figure 7: Energy Consumption vs. Radio Message Bases, VLDB ’94, pages 606–617, San Francisco, CA,
USA, 1994. Morgan Kaufmann Publishers Inc.
[7] J. Chen, D. J. DeWitt, F. Tian, and Y. Wang.
NiagaraCQ: a scalable continuous query system for
Sensor networks provide a considerably challenging pro- Internet databases. In ACM SIGMOD, pages 379–390,
gramming and computing environment. They require ad- New York, NY, USA, 2000. ACM.
vanced paradigms for software design, due to their character- [8] EsperTech. Event stream intelligence: Esper &
istics such as limited computational power, limited memory NEsper. http://www.esper.codehaus.org/.
and battery power which WSNs suffer from. In this paper, [9] S. Gatziu and K. R. Dittrich. Events in an active
we presented our system, an in-network complex event pro- object-oriented database system, 1993.
cessing, a system that efficiently carries out complex event [10] V. Goebel and T. Plagemann. Data stream
queries inside network nodes. management systems - a technology for network
We have proposed an engine to allow the system to de- monitoring and traffic analysis? In ConTEL 2005,
tect complex events and valuable information from primitive volume 2, pages 685–686, June 2005.
events. [11] D. Gyllstrom, E. Wu, H. Chae, Y. Diao, P. Stahlberg,
We developed a query plan based approach to implement and G. Anderson. SASE: complex event processing
the system. We provided the architecture to collect the over streams (Demo). In CIDR, pages 407–411, 2007.
events from sensor network, this architecture includes three
[12] D. Klan, M. Karnstedt, K. Hose, L. Ribe-Baumann,
sides; sensor side to perform in-network complex event pro-
and K. Sattler. Stream engines meet wireless sensor
cessing, sink side to deliver the events from the network to
networks: cost-based planning and processing of
AnduIN server side which has the responsibility to display
complex queries in AnduIN, distributed and parallel
them and perform further analysis.
databases. Distributed and Parallel Databases,
We demonstrated the effectiveness of our system in a de-
29(1):151–183, Jan. 2011.
tailed performance study. Results obtained from a compari-
son between centralized approach and our approach confirms [13] Y. Lai, W. Zeng, Z. Lin, and G. Li. LAMF: framework
that our in-network complex event processing in small-scale for complex event processing in wireless sensor
and large-scale sensor networks has shown to increase the networks. In 2nd International Conference on
lifetime of the network. We plan to continue our research (ICISE), pages 2155–2158, Dec. 2010.
to build distributed in-network complex event processing, in [14] P. Li and W. Bingwen. Design of complex event
which each sensor node has a different complex event pro- processing system for wireless sensor networks. In
cessing plan and can communicate directly between them to NSWCTC, volume 1, pages 354–357, Apr. 2010.
detect complex events. [15] D. C. Luckham. The power of events. Addison-Wesley
Longman Publishing Co., Inc., Boston, MA, USA,
2001.
9. REFERENCES [16] S. R. Madden, M. J. Franklin, J. M. Hellerstein, and
[1] Nondeterministic finite automaton. W. Hong. TinyDB: an acquisitional query processing
http://en.wikipedia.org/wiki/Nondeterministic_ system for sensor networks. ACM Trans. Database
finite_automaton. Syst., 30(1):122–173, Mar. 2005.
[2] D. Abadi, D. Carney, U. Cetintemel, M. Cherniack, [17] J. Xingyi, L. Xiaodong, K. Ning, and Y. Baoping.
C. Convey, C. Erwin, E. Galvez, M. Hatoun, J.-h. Efficient complex event processing over RFID data
Hwang, A. Maskey, A. Rasin, A. Singer, stream. In IEEE/ACIS, pages 75–81, May 2008.
M. Stonebraker, N. Tatbul, Y. Xing, R. Yan, and [18] X. Yang, H. B. Lim, T. M. Özsu, and K. L. Tan.
S. Zdonik. Aurora: a data stream management system. In-network execution of monitoring queries in sensor
In ACM SIGMOD Conference, page 666, 2003. networks. In ACM SIGMOD, pages 521–532, New
[3] R. Bhargavi, V. Vaidehi, P. T. V. Bhuvaneswari, York, NY, USA, 2007. ACM.
P. Balamuralidhar, and M. G. Chandra. Complex [19] Y. Yao and J. Gehrke. The cougar approach to
event processing for object tracking and intrusion in-network query processing in sensor networks.
detection in wireless sensor networks. In ICARCV, SIGMOD Rec., 31(3):9–18, Sept. 2002.
pages 848–853. IEEE, 2010. [20] M. Zoumboulakis and G. Roussos. Escalation:
[4] L. Brenna, A. Demers, J. Gehrke, M. Hong, J. Ossher, complex event detection in wireless sensor networks.
B. Panda, M. Riedewald, M. Thatte, and W. White. In EuroSSC, pages 270–285, 2007.
Cayuga: a high-performance event processing engine.