当前位置:首页 » 物联网/云计算 » 正文

第5章 RFID 复杂事件检测算法

913 人参与  2019年04月10日 12:24  分类 : 物联网/云计算  评论

我们完成了RFID仓储管理系统的设计与实现,这样的系统应用是非常广泛的,然而在实际应用过程中,又存在许多问题。对于仓储管理系统的智能化管理模块来说,复杂事件检测的功能必不可少。举个简单的例子吧,超市里货架处设有Reader1,收银台处设有Reader2,大门出口处设有Reader3,对于一件商品来说,在三个Reader处被读到分别记为事件A,B和C。那么一件商品被售出的完整的事件流应为A,B,C。假如只为A和C,缺少事件B,说明在Reader2处没被读到,那么就属偷盗行为,出现异常,系统会自动报警。基于RFID的仓储管理系统还有很多应用,比如应用到电子装配和化学实验等,在这样的应用中,每个事件发生的顺序都是很重要的,不能颠倒,否则都需要报警,可见复杂事件检测对于我们的系统是至关重要的。

由于RFID数据一般是时间相关的,动态变化的、大量的,一般的RFID数据处理框架都需要实时处理大量RFID数据流。然而大部分的RFID应用的事件都有时间限制,一个事件只在一段时间内或一段时间后发生才有效。例如在我们实现的基于RFID的仓储管理系统中,许多商品都存在保质期,商品只在保质期内才有效,这个保质期就是对商品的时间约束。还有例如在机场,包裹或行李必须在飞机起飞前三十分钟被送到指定地点。于是我们意识到研究出一个可以处理不同的时间相关事件的RFID仓储管理系统是很有必要的,这些事件可以是简单的或复杂的,带有时间约束条件。由于带有时间约束的事件类型只在特定的时间段内有效,于是参考文献[1]提出了一个新的时间概念,生命周期(TTL),适用于所有复杂的时间相关的事件类型,包括那些在现有系统中可以处理的事件类型。在互联网上,TTL是一个非常重要的概念,能够帮助互联网丢弃无用数据包,这些无用数据包对处理数据以达到最终结果没有任何帮助。RFID技术被广泛认为是一个很有前途的技术,在不久的将来用来创建一个“物联网”。TTL的概念对特联网是很重要的,它可以帮助丢弃无用的中间结果以减少数据量,并对实时事件作出快速响应。所有可用的RFID系统都有一个时间观念,即时间戳,当标签被阅读时会由RFID阅读器指派给RFID数据。时间戳代表时间点,也就是事件在现实世界中发生的时间,TTL代表标签事件需要遵守的时间约束。因此,除了时间戳,我们提倡TTL应该成为RFID数据管理系统另一个重要的时间概念。

当处理复杂的事件时,事件到达系统的顺序可能会与事件在真实世界中发生的顺序不一致,这个问题,命名为乱序事件流(UnES)问题,可能是由于网络路由延迟或一个标签被许多阅读器同时读到而产生的。现有的解决方案有两种:一种是忽略这个问题,假设事件到达系统的顺序与它们在现实世界中发生的顺序一致。另一种是在组成更复杂事件前对事件按照它们的时间戳进行排序。这两种方案都有缺点,由于阅读器分布广泛并且每个都可能存在延时,这就不能保证事件到达系统的顺序与发生的顺序一致,另外,RFID电子标签可以被多个阅读器读到,而阅读器可能会把这些原始的事件在不同的时期发送到系统。同样,即使事件发生后进入系统,他们也许还从属于不同进程的队列,显然,对大多数RFID应用,忽略UnES问题是不切实际的。对于第二种方案,它们要求事件进入系统的时间点必须不迟于一个约束范围,用同一个约束范围处理所有应用程序。如果系统同时处理多个应用程序,那么用一个这样的约束范围不能处理所有数据产生的混合的结果。要解决这个问题,参考文献[1]又提出了一种数据结构-双表结构(DLSIList),记录无序事件流以使整个系统从一个无序的事件序列提取有序的事件流。为了避免中间结果以指数方式增长,算法通过TTL机制来维护和更新DLSIList

5.1.RFID事件类型的基本概念

一个事件是在现实世界的特定时间和特定地点发生的,它被记录在RFID数据管理系统中,事件类型描述了具有一系列属性值的一类事件。每个事件都有一个事件类型和与这个事件类型一致的一系列属性值。根据应用不同可以将事件分为不同的事件类型,一般每个事件类型都有四个关键点:1.事件的名称2.发生的时间和相关数据3.发生的地点4.商业背景。

原子事件:由阅读器读取的单个事件。例如在货架上取走一块香皂,或在收银台对一块香皂付款都是一个原子事件。

复杂事件:一段时间内发生的多个原子事件组合起来成为复杂事件。例如先取香皂再付款就是由两个原子事件组成的一个复杂事件。

5.2.问题的提出

当处理复杂事件时,由于路由延时或同一事件可能被多个阅读器记录等原因,通常情况下事件到达系统的顺序与现实世界中事件发生的顺序不一定完全吻合,于是乱序数据流(UnES )问题应运而生。

image.png

其中Ai,Bi,Ci都是单个的原子事件。例如一个顾客在货架拿走货物这个事件被ReaderA读取记为事件Am,在收银台结帐由ReaderB读取记为Bm,在出口被ReaderC读取记为Cm。此例中正确的事件序列应为AmBmCm,然而由于路由延迟或其它原因,数据管理系统接收到三个阅读器发送过来的这三个事件的顺序为

AmCmBm,这个事件序列就是乱序的。也就是所谓的UnES问题。

解决方案:

为了解决UnES问题,从乱序数据流中找出多个有序事件序列,参考文献[1]提出了一种新型数据结构Double Level Sequence Instance List (DLSIList) DLSIList中有两个表,用来存储和处理进入数据管理系统的乱序数据流。通常只有当一个事件在特定时间内发生才有效,也就是说事件在时间上会有一些约束条件,这样DLSIList中存储的许多中间结果不会继续向后发展,于是需要一个机制来去除这些无用的中间结果,这样我们才有能力处理海量的数据流,于是又提出了Time To Live (TTL)的概念。

5.3.RFID事件的数据结构

先给出一个SEQ类型序列,例如:

SEQ(EventType1EventType2, ...EventTypeN)

SIList中的每个事件序列都要遵守SEQ中的事件类型顺序。

在被加入到DLSIList之前,每个事件e都有一个timpstamp属性,代表此事件在真实世界中的发生时被阅读器读取的时间。当事件被加入进DLSIList中时,另外一个systemstamp属性产生了,代表这个事件进入系统的时间。

每个事件都有一个Location信息,代表事件发生的位置,也就是接收此事件的阅读器的序号或位置信息。

这样每个RFID事件的数据结构包括以下四个信息:

timestamp,systemstamp,location.

DLSIList数据结构:

image.png

PSIList有n-1个部分,每个部分都由同种事件类型的部分事件序列组成,如下所示:

image.png

LPiPSIListi中元素的个数,并且每部分的事件类型都是SEQ中的EventTypei

SIList中的每个部分将形成一个事件序列,并有一个属性,即changed,以显示是否有新的事件已经被加入到这个部分。中对于SI1SI2SIm中的每个事件当它们被加入到SIList中时另外两个属性被加入进来,一个是Systemstamp用来表示事件加入系统的时间。另一个是First属性,用来表示这个事件是否在前面的部分已经存在了。

image.png

其中1<=j<i;

DLSIList有两个表,一个是用来存储事件序列中的部分事件,另一个存储事件序列,PSIList用来存储单个事件以便系统可以解决UnES问题。SIList用来存储不同阶段的中间事件序列,这些事件序列很可能形成最终的事件序列。需要说明的是事件必须按照SEQ中定义的顺序进入SIList中同一部分的。另外一个需要说明的是PSIList是从2开始的,而不是1,也就是事件序列的第一个事件可以直接加入到SIList中去。PSIListi;j代表PSIListi 中第j个事件。SIi;j代表SIi 中第j个事件。

当一个SEQ类型给出时,一个新的DLSIList会被创建,刚开始时DLSIList是空的,当事件到来时,DLSIList被更新并且将生成的完整事件序列返回给用户。整个算法主要是围绕DLSIList中的PSIListSIList进行的,事件先用来更新SIList,然后存储在PSIList中以便将来使用。每当SIList中的某部分发生改变时,开始检查PSIList 中的事件是否可以使SIList继续扩展。

5.4.TTL(Time To Live):生命周期

可以针对处理不同的事件类型对TTL进行不同的分类:

1.Absolute TTL(TTLa)

2.Relative TTL(TTLr)

3.Periodical TTL(TTLP)

4.Sequential TTL(TTLs)

Absolute TTL(TTLa):

是指一个RFID标签的生命周期,即一个RFID标签在物理世界中有效的一段时间。

例:

假设在货架上放着许多瓶药品,这种药品只有在有效期内才有效,而且这种药品只能被用一次,如果过了有效期药品还放在货架上,系统就会给出警告,提示用户药品已过期。

例子中药品的有效期就是TTLa

Relative TTL(TTLr):

是指一个事件在一次应用中的有效时间。事件可以是原子事件或复杂事件。

例:

假设每个参观者进入建筑物时都会被标记一个RFID标签,不同的参观者可以停留不同的时间,当参观者离开建筑物时,标签被收回,并且可以留给下一批参观者再次使用。

在这个例子中,一个RFID标签可以要据不同的应用使用多次,而且每次它的效时间都可能不同,参观者可以有建筑物中停留的时间就是TTLr

每个原子事件只能有一个TTLa

每个事件可以根据不同的应用有不同的TTLr

TTLrTTLa的扩展。

Periodical TTL(TTLP):

是指在一个事件序列中两个连续事件之间的时间约束,这个事件序列是由同种类型的事件组成。

例:

假设一种机器可以用很多年,但是其中的一些零件有一个较短的生命周期,必须定期更换。如果这些零件都附有一个RFID标签,那么系统就会根据RFID阅读器阅读到的信息在需要更换零件时给出提示。一个零件前后两次更换的时间间隔就是TTLp

Sequential TTL(TTLs):

是指在一个事件序列中两个连续事件的时间间隔的约束条件。但是它并不要求事件序列中事件类型相同。

TTLsTTLp的扩展。

TTL机制总结:

TTL机制表示对事件的一些时间约束,可以将其抽象为四类,在处理复杂事件时,通常这四类是同时工作的,用TTL机制可以减少DLSIList 表中的冗余数据,从而可以有能力处理大量数据流。 

5.5.本地复杂事件检测算法流程

image.png

约束条件(1:

假设任何两个连续事件的时间间隔为:

image.png 

Index为事件e的事件类型在SEQ中的序号,那么进入SIList中的事件必须满足:

image.png

约束条件(2):

如果PSIList中的事件可以满足下面的约束条件,则可以将其加入到SIList中去。

image.png

约束条件(3):

PSIList中的事件都在等待那些SEQ事件类型在它们之前但是在它们之后到来的事件,如果系统表明不会再有这样的事件到来,则PSIList中的相应事件可以被删除。有两个约束条件需要被检查:

第一:

image.png

如果满足,则PSIListi,j不能被删除。

若第一个条件不满足,则需要继续检查系统时间SystemTimeSystemTime就是当前到来事件的systemstamp。一个RFID标签被读取和处理之间的最大时间间隔被称为Delay,由用户自定义。

PSIListi,j满足下面条件,则没有前面的事件再会到来,则PSIListi,j可以被删除。

SystemTime>PSIListi,j.timestamp-Li-1+Delay

约束条件(4):

如果已经有了j个事件,它正在等待第j+1个事件,由于中的事件已经被检查过了,如果系统时间表明没有事件会再来了,可以删除了,约束条件如下所示:

 

SystemTime>SIi,j.timestamp+Uj+Delay

 

约束条件(5):

如果事件序列有TTLRC的限制,即一个事件序列的首尾时间差不能大于TTLRC,若SIList中的一个事件序列中尾事件的timestamp与首事件的timestamp之差大于TTLRC,则此事件序列可被删除。其中TTLRC由用户自定义。

 

约束条件(6):

每个事件都有一个Location属性,包含读取此事件的有效的阅读器的属性信息,例如序号或位置,TTL机制通过检查事件的Location属性,若不能与任何有效阅读器属性匹配,则此事件被删除,属无用事件。

算法实例:

输入的乱序数据流为Reader在一段时间内读到并存入数据库中的,为了明显地显示,将其存放在一个文件中,如图5-5所示。

image.png

其中disc是Reader实际读到TagList信息的时间,也就是timestamp,last是这些信息发送到系统的时间,也就是Systemstamp ,Ant是阅读器的天线类型,本例中共有四类天线. 

程序运行结果:

image.png

来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=1254

RFID  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!