基于ENFA的乱序RFID复杂事件检测算法  

Out-of-order RFID complex event detecting algorithm based on ENFA

作　　者：刘海龙[1] 李战怀[1] 

机构地区：[1]西北工业大学计算机学院,陕西西安710029

出　　处：《华中科技大学学报（自然科学版）》2010年第1期25-30,共6页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：NSFC-JST重大国际(地区)合作项目(60720106001)

摘　　要：针对时间戳乱序的无线射频识别(RFID)复杂事件检测带来的诸如建立事件关联关系的方法失效、判定复杂事件的构成时机困难、判定事件未发生与未到达困难等问题,提出了基于扩展的非确定性有限自动机(ENFA)模型的复杂事件检测算法.形式化地描述了时间戳乱序问题,分析了时间戳乱序给复杂事件检测带来的问题;引入插入优化策略,采用多时间槽索引策略进行滑动窗口处理,摒弃中间结果中过期数据;支持含有非事件的复杂事件检测.实验结果表明该算法能够有效解决时间戳乱序带来的问题.The detection order of radio frequency identification （RFID） events are always different from the occurrence order, which cause some problems, such as difficult to establish the relationship of correlated events, difficult to judge the final state of complex events, difficult to judge the nonoccurrence or non-arriving of an even. A algorithm based on extensive based nondeterministic finite automata（ENFA） was presented to solve these problems. Formal description of out-of-order problem was proposed and difficulties brought by out-of-order problem were analyzed. Based on an extensive nondeterministic finite automata （NFA） model, some optimization techniques were applied. For example, the strategies using multiple timeslots were proposed to eliminate expired intermediate data. The method to support detection of complex events with negative pattern was also studied in detail. Results of the experiments demonstrate that ENFA is effective and efficient.

关 键 词：无线射频识别 非确定性有限自动机 乱序数据流 复杂事件 检测 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]