R²CEDM: A Rete-Based RFID Complex Event Detection Method

Abstract

In various RFID application scenarios, RFID generates real-time and inherent unreliable raw data continually, which contain valuable enterprises business event. How to detect valuable event from RFID raw data has becoming a key issue. A Rete-based RFID complex event detection method called R²CEDM is proposed. Firstly, α_detecting net is established to detect all attribute of RFID primitive events in R²CEDM. Then β_detecting net is used to assemble RFID events into RFID complex events with the business rules, and concerned RFID complex events is obtained. The comparative experiments show the proposed R²CEDM can effectively improve the processing efficiency.

1 Introduction

RFID system consists of tags, readers and management information systems. RFID is a non-contact automatic identification technology, which has some characteristic such as batch identification, fast mobile identification in comparison with the barcode. In recent years, RFID technology has been widely used in logistics, transportation, medical, agriculture, animal husbandry, special materials management, manufacturing lines and other fields [1]. In various application scenarios, RFID system will generate vast amounts of real-time raw data continually. Although these raw data contain valuable enterprises business event, they are difficult to be used directly by enterprises application system. There are also redundant, incorrect and other characteristics in the RFID raw data [1,2,3]. How to detect enterprises business logic events from RFID raw data, which are concerned by enterprises, has becoming a key issue that must be solved in RFID application system [4]. Event is a meaningful change in the system, or an occurrence of the interested content, such as a RFID reading process in the RFID system. In general, the RFID events can be classified into RFID primitive event and RFID complex event [5].

RFID event process is shown in Fig. 1 [6]. Through the data cleaning from event filter, the redundant and erroneous RFID primitive events have been removed. Then, RFID complex event can be detected through RFID event aggregation according to the business logic rules, and actively inform to the business system such as WMS, ERP. RFID complex event detection is the key for RFID event processing, which directly affects the application of RFID system.

Fig. 1.

RFID event process

RFID complex event detection is an important topic in RFID application system. Now, there are some popular RFID complex event detection methods such as finite automata-based methods [7], matching tree-based methods [8], directed graph-based methods [9] and Petri net-based methods [10]. In the actual application scenarios such as manufacturing process, these objects such as materials, products, personnel and location are composed of many logical attributes. In addition, these objects always will extend some other attributes at any time as needed. When determining the concerned complex events, the user must decide several attributes and make their range as the detection rules. However, it is difficult that how to directly determine which kinds of primitive events are interested in, then we need to detect the attributes of each primitive event to determine whether it meets the rules.

Focusing on multi-attribute detection scenarios for RFID primitive events, this paper proposes a Rete-based RFID complex event detection method called R²CEDM, which expands attributes of primitive event. The aim of this method is to do as follows:

• (1) To extend object attributes for primitive events and do complex events detection. Extending all their attributes of the primitive events, and then transferring them to do complex event detection.

• (2) To create an event detection network. Firstly, finding out the primary component events with detecting the attributes of input events. Secondly, generating parent events continually from Rete network. Finally, outputting the target complex events.

2 RFID Complex Event Detection Model

The primitive event is defined as PE = <OID, RID, T>  [2] in traditional studies, but the definition is unsatisfied in actual application environment and cannot be used directly in complex event detection. Take a manufacturing workshop for example, managers are interested in all events which batch number is “M20160923”. When the complex event detection system receives a primitive event <O1, R1, t> , it can’t determine whether the object O1 belongs to the batch of “M20160923”, unless we query all objects of the batch “M20160923” in the database.

In most scenarios, the complex event detection mainly focuses on those events, which are about a type of objects or happen in a region or period, rather than an individual, which is uniquely labeled by an OID. Moreover, the biggest drawback about focusing on the individual will generate a huge number of complex events, which are not all interested by the actual application. Therefore, in order to be more suitable for RFID complex event detection system in real scenario, this paper proposes expanding primitive event to expansion primitive event.

Definition 1:

Expansion primitive event. EPE = <TypeID, O, R, L, T> , where TypeID is an identification of the expansion primitive event. O, R, L and T are defined as follows.

Definition 2:

Monitor object. O = {OID, a1, a2, …, an}, where O denotes a finite attribute set of RFID tag object, and its content can be increased or decreased on demand. OID denotes the object’s unique identification (OID as a default tag data), and a1, a2, …, an denote the other attributes of the monitor object. OID is the key of this data field, expressed as O.ID = OID.

Definition 3:

RFID reader. R = {RID, ReadPointID, a1, a2, …, an}, where Rdenotes a finite attribute set of RFID reader, and its content can be increased or decreased on demand, RID denotes a unique identification of the reader, ReadPointID is used to associate the incident locations of events, and a1, a2, …, an express other attributes of the RFID reader. RID is the key of this data field, expressed as R.ID = RID.

Definition 4:

Incident location of event. L = {ReadPointID, BusinessLocationID, a1, a2, …, an}, where L denotes a finite attribute set of incident location of event, and its content can be increased or decreased on demand. ReadPointID denotes the identification of physical reading position. BusinessLocationID denotes the location identification specified by the upper system. And a1, a2, …, an denotes other attributes to incident location of event. ReadPointID is the key to incident location of event, expressed as L.ID = ReadPointID.

Definition 5:

Event time. T = {Timestamp, a1, a2, …, an}, where T denotes a finite attribute set of event time, and its content can be increased or decreased on demand, Timestamp is defined in primitive event PE, and a1, a2, …, an denotes other attributes of event time. Timestamp is the key to event time, expressed as T.ID = Timestamp.

In the definition of PE, the location of fixed RFID reader is treated as the incident location of event, but actually, this has the following three questions:

• (1) There may have multiple readers at the same location.

• (2) Without being specified explicitly, the reader located between two areas cannot judge where the object with tag enters into.

• (3) The reader is moving in control scene, so it may read the tag in many locations not just one.

Therefore, we propose to define L separately. In practical applications, to solve the above problems is to read the “location tag”. When the reader’s location changes, the reader can read the location tag, which is previously fixed on a specified object, to update the associated relationship between RFID reader and incident location of event.

We can do complex event detection after expanding PE to EPE for the processing object. The R²CEDM model is shown in Fig. 2.

Fig. 2.

RFID complex event detection model

3 R²CEDM

The complex event consists of component events according to certain rules, so it is suitable to Rete algorithm, which is widely used for rule-based system. The main idea of Rete algorithm is as following: Firstly, to do routine detecting in α net. Secondly, to do detection and combination to these data arriving β net. Finally, to output rules which are triggered. EPE is also need to detect attributes and judge primary component event where it belongs at first, do combination to triggered primary component event with rules, and generate triggered target complex event at last. Consequently, we propose a Rete-based RFID complex event detection method.

3.1 R²CEDM Network

R²CEDM network consists of two stages, attribute detection and event logic relationship detection. Attribute detection, called α net, detects attributes of O, R, L and T in EPE to determine whether it matches the attribute constraint of the primary component events of target complex event. Event logic relationship detection, called β net, detects to determine whether it matches the logic relationship between primary component events of target complex event for the EPE from α net.

Let’s take the event rules of SASE language [11] described as Table 1 for example to illustrate and show the structure of R²CEDM network shown in Fig. 3.

Table 1. Example of SASE described target complex event

Fig. 3.

The example of R²CEDM network

Because there need to record and transfer intermediate results of detection in β net, we define an event_token structure to illustrate R²CEDM algorithm.

Definition 6:

Event_token. It is an event flag to record and transfer intermediate results in $\upalpha\_{\text{memory}}$ and $\upbeta\_{\text{memory}}$. ${\text{Event}}\_{\text{token }} = \left( {{\text{Component}}\_{\text{event}}\_{\text{List}},\,{\text{Event}}\_{\text{Description}}} \right)$, where Event_Description denotes complex event expression with SASE language [11], Component_event_List denotes recording the entering component events and their attributes in WHERE clause of Event_Description and discarding attribute values which are unconcerned.

3.2 The Steps of R²CEDM Algorithm

As shown in Fig. 4, the steps of R²CEDM algorithm are as following:

Fig. 4.

R²CEDM algorithm flow chart

• (1) To execute β net to construct β_construct: querying rule configuration database, constructing β net, and generating β_node.

• (2) To execute α net to construct α_construct: constructing α net according to attributes of O, R, L and T in information database, generatingarea_node, attribute_node and value_node, establishing connection between value_node and corresponding α_node.

• (3) To execute α_Detecting algorithm of α net: waiting the input of EPE, calculating primary complex events triggered by EPE.

• (4) To execute β_Detecting algorithm of β net: waiting event_token output by $\upalpha\_{\text{node}}$, calculating whether there are rules to be triggered.

The difference between Rete algorithm and traditional RFID complex event detection is as following: Every input processed by Rete is statement and has a single attribute that has a unique value. However, RFID events need to detect every attribute of each data area, compare every value to determine which type of event it belongs to. Based on the comparison above, it is important for R²CEDM to optimize α_Detecting.

3.3 β_Construct Algorithm

β_construct algorithm works as follows: Taking out the rule from rule database one by one, constructing β net, $\upalpha\_{\text{node}}$ and $\upalpha\_{\text{memory}}$ according to EVENT clause, WHERE clause and WITHIN clause of the rules, and determining the event_token structures of $\upalpha\_{\text{memory}}$ and $\upbeta\_{\text{memory}}$.

3.4 α_Construct Algorithm

3.4.1 Algorithm Description

Process description:

Creating αttribute_node and vαlue_node according to the attribute which appears in the event_token’s WHERE clause of $\upalpha\_{\text{node}}$, and establishing a connection between $\upalpha\_{\text{node}}$ and vαlue_node.

Initialization:

• (1) Generating root_node and 4 αrea_node of O, R, L and T respectively.

• (2) Constructing Hash mapping between root_node and αrea_node.

• (3) Using constraint to represent a comparison condition of WHERE clause.

3.4.2 Algorithm Steps

Step 1: :

To take out the next unprocessed $\_{\text{node}}$ $\upalpha_{\text{i}} \left( {1 \le {\text{i}} \le 4} \right)$. If $\upalpha_{\text{i}} = {\text{null}}$, it represents all $\upalpha\_{\text{node}}$ have been disposed, then go to step 6. Else, go to step 2

Step 2: :

To take out the next unprocessed ${\text{constraint}}_{\text{j}} \left( {1 \le {\text{j}} \le\upalpha_{\text{i}} .{\text{compare}}\_{\text{condition}}\_{\text{count}}} \right)$ in $\upalpha_{\text{i}}$. If ${\text{constraint}}_{\text{j}} = {\text{null}}$, it represents all attribute constraints of $\upalpha_{\text{i}}$ have been disposed, ${\text{i}}++$, then go to step 1. Else, go to step 3

Step 3: :

To take out an unprocessed attribute constraint ${\text{constraint}}_{\text{j}}$ in $\upalpha_{\text{i}}$. If the attribute of ${\text{constraint}}_{\text{j}}$ is not in α net which has constructed, we need to construct a new $\upalpha{\text{ttribute}}\_{\text{node}}$ required by ${\text{constraint}}_{\text{j}}$. Construct Hash mapping between $\upalpha{\text{ttribute}}\_{\text{node}}$ and corresponding $\upalpha{\text{rea}}\_{\text{node}}$, and let $\upalpha{\text{ttribute}}\_{\text{node}}.\upalpha\_{\text{relate}}\_{\text{set}} = \left\{ {\upalpha_{\text{i}} } \right\}$. Else, let $\upalpha{\text{ttribute}}\_{\text{node}}.\upalpha\_{\text{relate}}\_{\text{set}} =\upalpha{\text{ttribute}}\_{\text{node}}.\upalpha\_{\text{relate}}\_{\text{set}} \cup \left\{ {\upalpha_{\text{i}} } \right\}$ . Then, go to step 4

Step 4: :

If the attribute value required by ${\text{constraint}}_{\text{j}}$ is not in α net, we need to construct a ${\text{v}}\upalpha{\text{lue}}\_{\text{node}}$ for the attribute value, connect $\upalpha_{\text{i}}$, construct Hash mapping between ${\text{attribute}}\_{\text{node}}$ and its ${\text{v}}\upalpha{\text{lue}}\_{\text{node}}$, let ${\text{value}}\_{\text{node}}.\upalpha\_{\text{relate}}\_{\text{set}} = \left\{ {\upalpha_{\text{i}} } \right\}$. Else, let ${\text{value}}\_{\text{node}}.\upalpha\_{\text{relate}}\_{\text{set}} = {\text{value}}\_{\text{node}}.\upalpha\_{\text{relate}}\_{\text{set}} \cup \left\{ {\upalpha_{\text{i}} } \right\}$. Then, go to step 5

Step 5: :

${\text{j++}}$, go to step 2

Step 6: :

For all ${\text{attribute}}\_{\text{node}}$, sorting the values of ${\text{attribute}}\_{\text{node}}.{\text{value}}\_{\text{node}}\_{\text{count}}$ descending, if the value of ${\text{attribute}}\_{\text{node}}.{\text{value}}\_{\text{node}}\_{\text{count}}$ is equal to ${\text{attribute}}\_{\text{node}}$, sorting descending according to the value $\left| {{\text{attribute}}\_{\text{node}}.\upalpha\_{\text{relate}}\_{\text{set}}} \right|$, and outputting ${\text{Sequence}}\_{\text{attribute}}\_{\text{node}}$ to end α_construct

3.5 α_Detecting Algorithm

α_Detecting in R²CEDM algorithm is based on bidirectional reasoning of production system: Firstly, reasoning from the attribute values of EPE to $\upalpha\_{\text{node}}$. Secondly, selecting appropriate time to do verification from the alternative targets $\upalpha\_{\text{node}}$ set $\left( {{\text{Set}}\_{\text{target}}\_\upalpha} \right)$, whose range has been narrowed, to the attribute values of EPE to find the triggered primary complex event quickly. This α_Detecting algorithm avoids comparing each attribute of EPE or every rule.

So, there are two problems in α_Detecting: One is how to greatly reduce the number of target $\upalpha\_{\text{node}}$ by less comparison times. The other is when reverse reasoning starts.

For the first problem, we detect an attribute value of EPE in α net. To choose a corresponding $\upalpha{\text{ttribut}}\_{\text{node}}$ to do Hash mapping for an attribute value of EPE to see if it can hit the corresponding of the $\upalpha{\text{ttribut}}\_{\text{node}}$. Assuming the hit rate of each ${\text{value}}\_{\text{node}}$ is roughly equal. If we compare the attribute value of this $\upalpha{\text{ttribut}}\_{\text{node}}$ in EPE at first, the greater the number of ${\text{value}}\_{\text{node}}$, the greater the probability of being hit, and the more $\upalpha\_{\text{node}}$ related by ${\text{value}}\_{\text{node}}$ which is not hit being ruled out at the same time. Even if not being hit, it also can directly rule out all $\upalpha\_{\text{node}}$ related by this $\upalpha{\text{ttribut}}\_{\text{node}}$. So the target scope is narrowed quickly. If we compare those $\upalpha{\text{ttribut}}\_{\text{node}}$ whose quantity is small in ${\text{value}}\_{\text{node}}$ at first, not only the smaller the hit rate, but also the less the irrelevant $\upalpha\_{\text{node}}$ being ruled out. The target scope is narrowed slowly. By the same token, it also can narrow the scope quickly to compare this attribute item at first whose $\left| {{\text{attribute}}\_{\text{node}}.\upalpha\_{\text{relate}}\_{\text{set}}} \right|$ is greater. So α_detecting compares those $\upalpha{\text{ttribut}}\_{\text{node}}$ that the quantity of $\upalpha{\text{rewaa}}\_{\text{node}}$ is greater and the value of $\left| {{\text{attribute}}\_{\text{node}}.\upalpha\_{\text{relate}}\_{\text{set}}} \right|$ is bigger at first. In addition, the ID value of a data area can uniquely determine all the other attribute values of this data area, therefore, if the ID attribute value of an EPE is hit, the EPE’s other attributes can no longer be detected. This can greatly avoid unnecessary comparison and reduce detection times.

For the second problem, the paper proposes that we should set different inputs to different rules and amend the opportunity according to the actual situation. It is not always high efficiency to set a fixed bidirectional reasoning conversion opportunity. So we use configurable parameters $\updelta$ in α_Detecting algorithm to set when the event detection process satisfies the Eq. (1), we can start backward reasoning. In Eq. (1), $\upalpha\_{\text{node}}.{\text{wait}}\_{\text{fulfil}}\_{\text{constraint}}$ denotes the number of constraint to be compared in $\upalpha\_{\text{node}}$ of detection process, and ${\text{EPE}}.{\text{wait}}\_{\text{check}}\_{\text{attribute}}\_{\text{node}}$ denotes the number of attributes to be compared in EPE of detection process. That is to say, when the number of attributes to be compared in default rules is less than the number of input attributes in EPE, we can start backward reasoning.

$$ \sum\nolimits_{{{\text{m}} = 1}}^{{\left| {{\text{Set}}\_{\text{target}}\_\alpha } \right|}} {\alpha \_{\text{node}}_{\text{m}} . {\text{wait}}\_{\text{fulfil}}\_{\text{constrait < }}\frac{ 1}{\delta } * {\text{EPE}} . {\text{wait}}\_{\text{check}}\_{\text{attribute}}\_{\text{node(}}\delta \ge 1 )} $$

(1)

α_Detecting Algorithm description is as following.

Process description: according to the sequence of attribute nodes in ${\text{Sequence}}\_{\text{attribute}}\_{\text{node}}$ ,detecting the attributes of EPE in the sequence to narrow the target scope, when the Eq. (1) is satisfied, reversely detecting attributes of EPE putting the target $\upalpha\_{\text{node}}$ as the starting point to make those $\upalpha\_{\text{node}}$ active.

Input:

every attributes of EPE.

Output:

${\text{Set}}\_{\text{target}}\_\upalpha$, whose ${\text{event}}\_{\text{token}}$ is output by the $\upalpha\_{\text{node}}$ to corresponding $\upbeta\_{\text{node}}$.

Initialization:

• (1) To let $\upalpha\_{\text{net}}.\upalpha\_{\text{node}}\_{\text{count}}$ denote the total number of $\upalpha\_{\text{node}}$ in α net. ${\text{EPE}}.{\text{wait}}\_{\text{check}}\_{\text{attribute}}\_{\text{node}} = \left| {{\text{Sequence}}\_{\text{attribute}}\_{\text{node}}} \right|$, where $\left| {{\text{Sequence}}\_{\text{attribute}}\_{\text{node}}} \right|$ denotes the number of elements in the attribute of the queue.

• (2) To let ${\text{Set}}\_{\text{target}}\_\upalpha = \mathop \sum \limits_{{{\text{j}} = 1}}^{{\upalpha\_{\text{net}}.\upalpha\_{\text{node}}\_{\text{count}}}} \left\{ {\upalpha_{\text{j}} } \right\}$ denote the set of alternative target $\upalpha\_{\text{node}}$, where $\left| {{\text{Set}}\_{\text{target}}\_\upalpha} \right|$ denotes the number of elements of alternative target $\upalpha\_{\text{node}}$.

• (3) To let $\upalpha\_{\text{node}}.{\text{constraint}}\_{\text{count}}$ denote the number of attribute constraint condition of $\upalpha\_{\text{node}}$.

• (4) To let ${\text{SEQ}}\_{\text{wait}}\_{\text{check}}\_{\text{attribute}}\_{\text{node}}$ denote the ${\text{attribute}}\_{\text{node}}$ queue to be compared and ${\text{SEQ}}\_{\text{wait}}\_{\text{check}}\_{\text{attribute}}\_{\text{node}} = {\text{Sequence}}\_{\text{attribute}}\_{\text{node}}$.

• (5) To generate the ID attribute queue ${\text{ID}}\_{\text{node}}\_{\text{list}}$ according to the sequence of the ID attribute in each data area of O, R, L, T in SEQ_wait_check_attribute_node.

3.6 β_Detecting Algorithm

Because β_Detecting algorithm is not the emphasis of R²CEDM, we simply expound the work process as follows: To β-node whose input comes from α_node, to detect the constraints of EVENT clause, WHERE clause and WITHIN clause of β-node. To record the input of the satisfied constraint. If the event_token in β-node is activated, outputting down to trigger the father β-node to do the same detection, and traveling all β-node which has received input until the target complex event is output.

4 Experiment

R²CEDM is for multi-attribute detection scenes of RFID primitive event, and optimize algorithm for event detection at the primary complex events stage of attribute detection. So one of the core of R²CEDM is α_detecting algorithm. Generally, the multi-attribute procession is not considered by the complex event processing mechanism. Therefore, we treat each EPE to be detected as a simple primitive event in the experiment. In this condition, we do the performance test for optimized α_detecting algorithm, and compare it with non- optimized α_detecting algorithm. Experimental platform are as follows: Inter (R) Core (TM) 2 T5500 1.66GHZ, 1.5 GB RAM. Windows XP. JRE1.6.0 compiler environment.

To set there are 200 attribute items at most in the data areas of O and R of EPE, 80 and 20 attribute items in the data areas of L and T of EPE respectively. 60 primitive complex events are averagely divided into 3 groups A, B and C, that each contains 4, 3, 2 attribute constraints and has 20 events respectively. Group A is divided equally into 5 parts, that each contains 4 to 0 attribute constraints and has 4 events respectively. Group B is divided equally into 4 parts, that each contains 3 to 0 attribute constraints and has 5 events respectively. Group C is divided into 3 parts, and each has 5, 5 and 10 events. To set each attribute has the range of 100 discrete attribute values, meanwhile to randomly set the constraint value of primary complex events.

As shown in Fig. 5, the optimized α_detecting algorithm has certain advantage comparing to non-optimized α_detecting algorithm, and with the increase in the number of expansion primitive events, the advantage of optimized α_detecting algorithm in efficiency increases gradually. The experiment result shows that α_detecting algorithm has the feasibility, and has improved the computation efficiency.

Fig. 5.

The comparison of optimized and non-optimized α_detecting algorithm

5 Summary

With the wide application of the RFID technology in various industries, the efficiency of RFID complex event processing will be a key issue. Taking manufacturing enterprise environment as the background, this paper proposes a Rete-based RFID complex event detection method called R²CEDM, using expansion primitive event and Rete algorithm to do complex detection. The core of the R²CEDM is α_Detecting. On the attribute detection stage of R²CEDM, we use the method of rapid narrowing the scope of the target nodes and bidirectional reasoning to improve the efficiency. Experiment shows that the optimized algorithm have improved the processing efficiency and reduced the processing time.