Efficient Complex Event Processing over RFID Streams

Abstract

RFID events are a large volume of stream data that continuously come out for tracking and monitoring objects. Many studies have been done to detect a complex event in the RFID stream. However, the existing studies have many problems which increase unnecessary operations when complex events do not satisfy minimum conditions. In this paper, we propose a new scheme to detect complex events when the minimum conditions are satisfied to remove unnecessary operations. To check the minimum conditions of the complex events, we register complex queries in a query index. We detect complex events using the query index and bitmap. To demonstrate the superiority of the proposed method, we compare it with the existing methods through various experiments. As a result, it is shown that the proposed method outperforms the existing methods as a whole.

1. Introduction

RFID data are a large volume of stream data sensed by RF waves continuously for tracking and monitoring objects [1]. RFID tag has an identifier corresponding to its object. RFID readers can recognize a number of tags without any limitation at the same time. Sensor devices such as wireless motes and RFID readers are gaining adoption on an increasing scale for tracking and monitoring purposes [2, 3]. The wide deployment of these devices will soon generate an unprecedented volume of events. An emerging class of applications such as supply chain management, security, indoor location service, healthcare, and environmental monitoring requires the events to be filtered and correlated for complex pattern detection [4–7]. They require to be transformed to new events that reach a semantic level appropriate for the applications [8]. These requirements constitute a distinct class of queries that translate data describing a physical world into information useful to the end applications in real time [9].

RFID systems access other RFID systems to get information for tags. RFID events are divided into primitive events and complex events [10, 11]. A primitive event is the information of a tag recognized by an RFID reader. A primitive event consists of the identifier of a tag, the identifier of a reader, and a timestamp that the reader recognizes the tag. For example, we assume that a reader R is established in front of a building and the reader detects an object O at the time t. It is represented by (R, O, t). A complex event is a semantic event which consists of primitive events for application services. Primitive events are originated from the past to the current. Therefore, historical primitive events must be maintained to organize complex events. It is required to process the complex event that is composed of the historical primitive events [8, 12].

In recent, complex query processing schemes have been studied to detect a complex event over RFID stream. Moon et al. developed an RFID business aware framework for extending RFID events using business rules [13]. The work of [13] proposed the RFID complex event definition tool (Biz EDT) which provides drag-and-drop support to define activities and their flows and to generate complex events by a graphical user interface. Demers et al. designed and implemented the Cornell Cayuga System for scalable event processing [14]. The work of [14] proposed a query language based on Cayuga Algebra for naturally expressing complex event patterns. Bai et al. proposed a stream query language to process RFID events by extending an SQL-based stream query language with temporal operators and related constructors [3]. Wu et al. proposed a complex event language, called SASE and a query plan-based approach to efficiently implement this language [8]. The SASE is a declarative language which consists of a subset of six operators such as sequence scan, sequence construction, selection, window, negation, and transformation to satisfy the needs of RFID monitoring applications. Kawashima et al. extended SASE to calculate the confidence of complex event pattern outputs which are emanated from primitive physical events stream with noise information [15]. Wang et al. developed a graph-based RFID complex event detection scheme called RCEDA. To process the complex events, Wang et al. formulated a declarative rule based approach for the powerful support of automatic RFID data transformation between the physical world and the virtual world [16]. RCEDA generates pseudoevents when events are detected to process nonspontaneous events.

However, the existing schemes perform unnecessary operations to detect the complex events in the large-scale primitive events occurred from a lot of readers. It causes the low throughput and outputs with low quality. In this paper, we propose a novel processing scheme to efficiently process the large-scale complex events. To enhance the existing complex event processing schemes, we define the minimum conditions for complex events and identify complex events to know whether they satisfy the minimum requirements from all the compositions of complex events or not. The complex event is a logical event that combines a number of primitive events using the predefined event operators for serving RFID business applications. We use many event operators like AND (∧), OR (∨), NOT (!), SEQUENCE (:), INTERVAL (;), and so on. When the conditions are just satisfied, the operations for detecting the complex events are invoked. To check the minimum conditions of the complex events, we register them into the grid structure and detect them with a query index and a bitmap structure. Because the proposed scheme performs just operations only when the minimum requirements are satisfied, the number of operations is reduced and unnecessary operations are removed.

The rest of the paper is organized as follows. Section 2 introduces the related work of our paper. Section 3 presents the proposed complex event processing which treats the complex events as continuous queries to organize the query index. Section 4 describes experimental evaluation results to show the superiority of our approach. Finally, Section 5 concludes the paper.

2. Related Work

RFID events are divided into primitive events and complex events. A primitive event provides the information of RFID tags. A complex event is a composite logical event for an application. A primitive event is the information of a tag sensed by an RFID reader. A primitive event consists of an identifier of the tag, an identifier of the RFID reader, and a time sensed by the RFID reader. For example, we assume that an RFID reader R is established in front of a building and detects an object O at the time t. It is represented by (R, O, t). RFID tags can be grouped into units of similar patterns by the EPC code [17]. Also, readers can be managed by some groups according to their roles and positions. Services process complex events that consist of primitive events.

A complex event is a logical event that consists of primitive events for application services. A primitive event is originated from the past to the current. Thus, a historical primitive event must be maintained to organize complex events. It is required to process a complex event that is composed of historical primitive events. For example, we assume that a library processes complex events for borrowing books. If a book $O_{i}$ is read from a reader $R_{i}$ at $T_{i}$ , a primitive event is represented as ( $R_{i}$ , $O_{i}$ , $T_{i}$ ). To make a complex event from primitive events, many operators are required. There are many event operators like AND, OR, NOT, SEQUENCE, and INTERVAL as shown in Table 1.

Table 1

Event operators to make a complex event.

Operators	Notation	Description
AND	[ $E_{1}$ ∧ $E_{2}$ ]	Both events $E_{1}$ and $E_{2}$ are occurred simultaneously
OR	[ $E_{1}$ ∨ $E_{2}$ ]	Either event $E_{1}$ or $E_{2}$ is occurred without their occurrence order
NOT	! $E_{1}$	Event $E_{1}$ is not occurred
SEQUCENCE	[ $E_{1}$ , $E_{2}$ : t]	Events $E_{1}$ and $E_{2}$ are occurred sequentially within time interval t
INTERVAL	[ $E_{1}$ , $E_{2}$ ; t]	During time interval t, both events $E_{1}$ and $E_{2}$ are occurred without considering their occurrence order

Wang et al. proposed a graph-based RFID complex event processing algorithm, called RCEDA using a graph-based computation model [10, 16]. RCEDA defines the specification and semantics of RFID events and rules and constructs a graph representing the events. In each rule, RCEDA constructs an event graph with leaf nodes representing primitive events, internal nodes presenting complex events, and edges linking constituent events with parent complex events. For each event graph, if there is any internal constraint defined on an event node, event node's internal constraint is propagated to all the descendant nodes. Interval constraints are propagated top-down in the event graph, where internal constraints define set to be the minimum of the current interval constraint and that of its parent event node. RCEDA generates pseudoevents in event detection to process temporal constrained nonspontaneous events generated from SEQ+ and NOT constructors, where a pseudoevent is a special artificial event used for querying the occurrences of nonspontaneous events during a specific period, and is scheduled to happen the expiration time of an event node. When pseudoevents are created, they are put into a sorted pseudoqueue according to their scheduled execution timestamps. The incoming RFID event queue is ordered by their observation timestamps. When the event engine fetches an event, it always fetches the earliest event from the two queues.

Gyllstrom et al. proposed SASE that processes a complex event over real-time streams of RFID readings [9]. SASE designed a complex event language for specifying application logic for such transformation and devised a new query processing techniques to efficiently implement the language. The SASE language has a high-level structure similar to SQL for ease of use by database programmers, but the design of the language is centered on event pattern matching. SASE devised native sequence operators based on a nondeterministic-finite-automata-based model which can read query-specific event sequences efficiently from continuously arriving events. These operators are then used to form the foundation of each plan, pipelining the event sequences to subsequent operators such as selection, window, and negation. The user defines a query and registers it as a continuous query with the complex event processor. The complex event processor supports continuous long-running queries written in the SASE language over event streams.

To deal with the large volume of RFID data, Liu and Wang proposed a complex event processing engine based on DSMS [18]. To detect complex events, Liu and Wang [18] use tree-based graph according to the expression of detection patterns in DSMS. To present the detection in tree-based graph, it contains the leaves of the tree representing the primitive events and the branch nodes representing the operators. The leaves of the graph just pass the primitive events to the parent nodes immediately receiving them without any storage. The parent nodes have separated storages for their children nodes. Since the RFID data stream always floods into the system, we need a buffer to cache the data stream. The buffer can also work to preload data for processing to improve the efficiency and reduce the response time. When the event processor gets the sufficient information, it will match the collected data with the rules from the rule storage. Once the matching process is completed, a result will be generated and sent to the result manager which will deliver the result to the enterprise application. All the behaviors of the components in the engine are coordinated by the scheduler.

3. The Proposed Complex Event Processing

3.1. The Architecture of Complex Event Processing

To enhance the existing complex event processing schemes, we define the minimum conditions for the complex events and identify complex events to know whether they satisfy the minimum requirements from all the compositions of complex events or not. When the minimum requirements are satisfied, the detection phase that determines the meaningful event pattern required by an application from RFID streams is performed. This process reduces the number of operations and the computation cost in the proposed scheme. Figure 1 shows the proposed complex event processing architecture. When a complex event is registered, it is assigned with a new identifier $E_{i}$ and is stored as a continuous query $Q_{i}$ into the query index. The proposed scheme constructs the query index to perform the incremental evaluation of continuous queries whenever the status is changed. The query index treats queries as data and the data as queries to process incremental evaluation of continuous queries in location-based services [19, 20]. In our complex vent processing, the query index that we proposed in 2008 is used [19]. The proposed scheme treats the complex events as continuous queries to deal with multiple complex events. And then, in the complex query repository, the complex event is represented by a tree-based model in order to detect complex event patterns in the bottom-up fashion. When a primitive event occurs, it stores the occurrence history of primitive events into bitmap through the query index. If a complex event associated with the primitive event exists in the query index, we evaluate whether the minimum conditions are satisfied in the complex query repository. If the requirements of the complex event are satisfied, we perform the event detection process to determine it.

Figure 1

The complex event processing architecture.

We use the query index to rapidly hand over the occurrence information of the primitive events to the complex event repository for multiple complex events. The query index is a memory-based grid index. In query index, each cell has the query identifier list that stores the continuous query identifiers. Figure 2 shows an example of the query index, where $Q_{1}$ = [[B3, [A2, B2; 1 sec], [A4, B4; 1 sec]]:10 min], $Q_{2}$ = [[B2, B3: 5 sec]∧[C2, C3: 5 sec]], and $Q_{3}$ = [[A1∨A2]∧[C2∨C3]]. Figure 2(a) shows the logical representation of the query index. Each cell represents the primitive event contained in complex queries. Figure 2(b) represents the physical presentation of the query index. Each cell has the query identifier list.

Figure 2

An example of a query index: (a) shows the logical representation of a query index; (b) shows the physical representation of a query index.

When the complex event is registered, it is represented in complex query repository as a tree-based graph consisting of leaf nodes and internal nodes. Figure 3 shows an example of the query index and the tree-based graph for a complex event $Q_{1}$ = [[B3, [A2, B2; 1 sec], [A4, B4; 1 sec]]:10 min]. A leaf node consists of primitive events and last occurrence time, and an internal node contains an operator. In the leaf node, the last occurrence time of a primitive event is used to evaluate the minimum conditions of a complex event.

Figure 3

An example of a tree-based graph.

In the complex query repository, a node is classified into four types such as normal node, trigger node, virtual node, and negative node. The normal node means an ordinary node which is not used as the trigger node, the virtual node, and the negative node. The trigger node represents a starting point for detecting a complex event. The virtual node is an artificial node stored into an internal node and is generated to efficiently process OR and INTERVAL operators. The negative node represents NOT operator, that is, nonoccurrence event. The trigger node is the node to check minimum conditions and specially is the last primitive event in a case of SEQUENCE operator (:). For $Q_{1}$ = (A1, B2: 10), the trigger node is B2 because the primitive events A1 and B2 are occurred sequentially within 10. In the internal node, the node connected by another operator is the trigger node. Figure 4 shows the examples of the trigger node and the negative node. In Figure 4(a), the uppermost node contains OR operator. Since OR operator satisfies the minimum conditions when only a primitive event simply occurs without their order, all child nodes connected by the OR operator are the trigger nodes. Therefore, the node A3 is the trigger node in leaf node. However, because the left child node of OR operator contains SEQUENCE operator (:10 min), only A4 is the trigger node. In Figure 4(b), the upper node of A2 contains NOT operator (!). In other words, when A2 does not occur, the condition of NOT operator is satisfied. Therefore, the node A2 is the negative node.

Figure 4

Examples of the trigger node and the negative node.

The occurrence history of the primitive events is not managed in the complex query repository. However, the information of the previous occurrence event is required to detect the complex event. We define the bitmap structure to store the occurrence history of the primitive event. The bitmap is a bit string of logical regions for reader and tag domains in the query index. We manage the bitmap that represents the occurrence of primitive events during the longest time interval for time constraints such as SEQUENCE and INTERVAL operators. The bitmap structure sets a specific bit of the bit string to “1” along the occurrence time whenever the primitive event contained in the complex event occurs. Figure 5 shows the bitmap structure. Since the primitive events A1 and B3 occur at time $T_{1}$ , the bit string is “10000100” at $T_{1}$ . Moreover, at time $T_{n}$ , the bit string is “1000000” because the primitive event A1 only occurs.

Figure 5

The bitmap structure.

3.2. The Complex Event Detection

To process the complex events, they must be registered into the middleware. The registration of a complex event means that it is translated into a continuous query, a query index is organized in the logical grid, and a bitmap is assigned for storing the history of the primitive events. Whenever primitive events occur, RCEDA, one of the existing complex event processing methods, accesses all the combinations of the complex events to detect the complex events. It may be much overhead. The proposed scheme performs operations to detect complex events after checking the minimum conditions from them. To check the minimum conditions, the latest update times are updated in the nodes corresponding to the registered complex events whenever the primitive events occur. When events just occur in the trigger node, the checking procedure for the minimum requirements is invoked. The minimum requirements do not mean the detection of the complex events. Next, operations to detect the candidate set of the complex events are performed by checking the bitmap.

Figure 6 shows a procedure to check the conditions of the complex events. The primitive event B4 accesses the complex event $Q_{1}$ along the query index. The primitive event accessed to $Q_{1}$ updates the occurred time of the event in the corresponding node. Then, the minimum requirements of $Q_{1}$ are checked because the primitive event B4 is the trigger node of $Q_{1}$ . The primitive events, B3 and A2, occur in 10 minutes as shown in Figure 6, but they were not updated since their initial values are set. It means that B2 and A4 do not occur, the minimum requirements are not satisfied, and operations to detect the complex events are not performed.

Figure 6

A procedure for checking the minimum conditions of the complex events when the primitive event occurs.

We use a query index based on bitmap which needs smaller storage and enhances the processing performance. In the query index, each node in a grid has a bit pattern which represents the relationship between nodes and queries [19]. When the primitive events occur, we can compute quickly the minimum conditions because a node in a grid without unnecessary operations is checked. Even though the complex events satisfy the minimum requirements, it may not occur practically. To detect such complex events, the additional operations using the bitmap are required. Since the conditions of the complex event are satisfied, all bitmaps are retrieved when the final operation is performed. The proposed scheme determines sliding windows by considering the primitive events and the duration of operations in the upper nodes. The detected candidate sets are transferred to the upper nodes. This procedure is repeated until they reach the top node.

Figure 7 shows query processing using the sliding window. Figure 7(a) shows the case that the minimum requirements of the complex event are satisfied. At $T_{6}$ , the minimum requirements of the complex events are satisfied by $Q_{1}$ and the operation for detecting the complex events is performed. The duration of an operator is modified to the size of the sliding window along the tree of $Q_{1}$ and the candidate set is extracted. To detect the candidate set of the complex event, the combination of A4 and B4 is detected in the bitmap. Next, the combination of A2 and B2 is also detected. Because all combinations exist in the candidate set, the candidate set corresponding to the parent operator is accessed. The conditions of (1), (2), and (3) are checked sequentially in Figure 7(b). However, the final complex event is not detected because the combination of A2 and B2 has been occurred later than the combination of A4 and B4.

Figure 7

Query processing using the sliding window.

3.3. The Expansion of Complex Event Processing

We use the virtual node in the graph-based tree to efficiently process OR operator. In Figure 8(a), the node A3 is the virtual node connected by OR operator. If a number of primitive events occur in node A3, we traverse the left subtree of the root node each time to extract the candidate set that satisfies a complex event regardless of its minimum conditions. To solve this problem, we create a new internal node for the left child of OR operator as the virtual node. Figure 8(b) shows that a new internal node is created as the virtual node. For the child node (:10 min) of OR operator, we create a new internal node I_Q3 and allocate a bitmap structure for a new internal node. A new internal node is treated as a general complex event independently.

Figure 8

An example of a virtual node.

4. Experimental Evaluation

We compare the proposed scheme with RCEDA [16] through various experiments. We used the system with Pentium (R) 4 2.8 Ghz processor, 1 Gbyte memory, and Microsoft Windows XP Professional. First, we evaluate the number of the occurred complex events and the number of the detected complex events according to the complexity of the complex events. Second, we evaluate the number of average operations as the number of complex events and the number of primitive events per second is changed. Third, we evaluate the average elapsed time for processing the complex events. Table 2 shows simulation parameters.

Table 2

Simulation parameters.

Parameter	Description	Values
C	Complexity of a complex event (tree level)	1 ~ 3
N	The number of registered complex events	100 ~ 500
P	The number of primitive events per second	10,000 ~ 50,000

We evaluate the average elapsed time and the number of operations for processing complex events. The complex event is organized as a tree. We assume that the tree is a binary tree and N is 500. C denotes the tree level. Figure 9 shows the average elapsed time to detect complex events. We can see easily that both the proposed scheme and RCEDA increase the average elapsed time similarly as P increases. At C = 1, RCEDA achieves better performance than the proposed scheme by about 10 ms because the proposed scheme performs additional operations for checking the minimum requirements and for generating intermediate results for the detection phase. It means that checking the minimum requirements in the proposed method has elapsed more time than detecting complex events in RCEDA. However, the proposed method significantly decreases the average processing time over RCEDA as the complexity increases. In RCEDA, when the number of complex events is 30,000, the processing time is over one second. That is, in RCEDE, as the complexity of a complex event is increased, the number of the accessed primitive events and the number of unnecessary intermediate candidate sets are also increased.

Figure 9

Average processing time for the complexity.

Figure 10 shows the number of the accessed complex events as the complexity increases. As shown in Figure 10, the number of complex events processed in RCEDA is increased significantly. However, in the proposed scheme, many complex events are filtered out by the minimum requirements and the number of the processed complex events is reduced. In the result, when processing the complex events with high complexity, the proposed scheme achieves better performance than RCEDA. Figure 11 shows the average processing time as the number of the registered complex events, N, is changed. The average processing time is increased in both schemes. However, RCEDA shows higher increasing rate than the proposed scheme.

Figure 10

The number of the accessed complex events for the complexity.

Figure 11

Average processing time for the number of complex events.

Figure 12 shows the average processing time for the complex events as the number of the primitive events per second, P, is changed. The average processing time of the proposed scheme is not increased significantly as P is increased. This is because many complex events are filtered out by checking the minimum requirements. However, RCEDA increases significantly the average processing time as P is changed. If the number of events occurred per second is over 40,000, the complex event is not processed within a second. It causes the processing delay to detect the complex event.

Figure 12

Average processing time for the number of primitive events.

5. Conclusion

We proposed an efficient complex event processing scheme for RFID stream. First, we checked the minimum requirements of the complex event. If they are satisfied, operations for detecting the complex events are performed. The proposed scheme organizes a query index and exploits a tree structure to register and manage the primitive events. Because the proposed scheme just performs operations only when the minimum requirements is satisfied, the number of operations is reduced and unnecessary operations are removed. Finally, we have shown through various experiments that the proposed scheme outperforms RCEDA.

Footnotes

Acknowledgments

This work was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) Grant funded by the Korea government (MEST) (no. 2009-0089128) and Basic Science Research Program through the National Research Foundation of Korea (NRF) Grant funded by the Korea government (MEST) (no. 2009-0080279).

References

Lin

Elmongui

H. G.

Bertino

Ooi

B. C.

Data management in RFID applications

Proceedings of the International Conference on Database and Expert Systems Applications

2007

434 444

Derakhshan

Orlowska

M. E.

FID Data Management: challenges and opportunities

Proceedings of the IEEE International Conference on RFID

2007

175 182

Bai

Wang

Liu

Zaniolo

Liu

RFID data processing with a data stream query language

Proceedings of the 23rd International Conference on Data Engineering (ICDE ′07)

April 2007

1184 1193

2-s2.0-34548717574

10.1109/ICDE.2007.368977

Gonzalez

Han

Klabjan

Warehousing and analyzing massive RFID data sets

Proceedings of the 22nd International Conference on Data Engineering (ICDE ′06)

April 2006

2-s2.0-33749586133

10.1109/ICDE.2006.171

L. M.

Liu

Lau

Y. C.

Patil

A. P.

LANDMARC: indoor location sensing using active RFID

Wireless Networks 2004 10 6 701 710

2-s2.0-5544326540

10.1023/B:WINE.0000044029.06344.dd

Rahmati

Lin

Hiltunen

Jana

Reliability techniques for RFID-based object tracking applications

Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN ′07)

June 2007

113 118

2-s2.0-36048966061

10.1109/DSN.2007.81

Wang

Liu

Temporal management of RFID data

Proceedings of the 31st International Conference on Very Large Data Bases (VLDB ′05)

September 2005

1128 1139

2-s2.0-33745621088

Diao

Rizvi

High-performance complex event processing over streams

Proceedings of the ACM SIGMOD International Conference on Management of Data

June 2006

407 418

2-s2.0-34250735599

10.1145/1142473.1142520

Gyllstrom

Chae

H. J.

Diao

Stahlberg

Anderson

SASE: complex event processing over stream

Proceedings of the Biennial Conference on Innovative Data Systems Research

2007

407 411

10.

Wang

Liu

Bai

Bridging physical and virtual worlds: complex event processing for RFID data streams

Proceedings of the International Conference on Extending Database Technology

2006

588 607

11.

Jin

Lee

Kong

Yan

Efficient complex event processing over RFID data stream

Proceedings of the 7th IEEE/ACIS International Conference on Computer and Information Science (IEEE/ACIS ICIS ′08)

May 2008

75 81

2-s2.0-51349144818

10.1109/ICIS.2008.60

12.

Qun

Zhanhuai

Hailong

Optimizing complex event processing over RFID data streams

Proceedings of the IEEE 24th International Conference on Data Engineering (ICDE ′08)

April 2008

1442 1444

2-s2.0-52649094813

10.1109/ICDE.2008.4497583

13.

Moon

Kim

Yeom

Choi

Framework for extending RFID events with business rule

Proceedings of the International Conference on Database Systems for Advanced Applications

2007

955 961

14.

Demers

A. J.

Gehrke

Panda

Cayuga: a general purpose event monitoring system

Proceedings of the Conference on Innovative Data Systems Research

2007

412 422

15.

Kawashima

Kitagawa

Complex event processing over uncertain data streams

Proceedings of the International Conference on P2P, Parallel, Grid, Cloud and Internet Computing

2010

521 526

16.

Wang

Liu

Complex RFID event processing

VLDB Journal 2009 18 913 931

17.

EPCglobal http://www.epcglobalinc.org/

18.

Liu

Wang

Complex event processing engine for large volume of RFID data

Proceedings of the 2nd International Workshop on Education Technology and Computer Science (ETCS ′10)

March 2010

429 432

2-s2.0-77953199507

10.1109/ETCS.2010.214

19.

Park

Y. H.

Bok

K. S.

Yoo

J. S.

Continuous range query processing over moving objects

IEICE Transactions on Information and Systems 2008 E91-D 11 2727 2730

2-s2.0-68749085984

10.1093/ietisy/e91-d.11.2727

20.

Prabhakar

Xia

Kalashnikov

D. V.

Aref

W. G.

Hambrusch

S. E.

Query indexing and velocity constrained indexing: scalable techniques for continuous queries on moving objects

IEEE Transactions on Computers 2002 51 10 1124 1140

2-s2.0-0036808476

10.1109/TC.2002.1039840