文摘

互联网的车辆(IoV)是一个重要的研究领域使用物联网的智能交通系统理论。复杂事件处理技术的一个基本问题处理IoV的数据流。近年来,许多研究人员处理时间和空间数据流的复杂事件处理技术。空间时间事件处理(步骤)是一个复杂的事件查询语言关注车辆的时间和空间数据流在网络。有四个处理的事件流模型基于复杂事件处理系统查询语言:有限自动机模型,匹配树模型,有向无环图模型,佩特里网模型。此外,最坏的事件流处理系统的响应时间的一个重要指标评估系统的性能。首先,本文提出了一个核心算法的时间和空间事件流处理程序基于一步Petri网模型。其次,我们提出了一个新颖的方法来估计最坏的事件流处理系统的响应时间,基于随机Petri网和排队理论。基于排队论的最后,通过仿真实验,本文基于一步证明了数据流处理系统具有良好的动态性能在处理时空数据流在网络的车辆。

1。介绍

互联网的汽车是一个重要的应用和物联网智能交通,也是智能城市的一个重要组成部分1- - - - - -6]。在互联网的车辆系统,有各种类型的数据源产生大量的时间和空间不间断数据流。处理这些数据流是大数据的一个重要研究方向7]。现在,有一些产品的处理网络的数据流:Twitter的风暴系统(8),雅虎的简单的可伸缩的流媒体系统(S4) [9),Facebook的数据高速公路和彪马系统(10),LinkedIn的卡夫卡系统[11),和一个交互式实时计算系统伯克利的火花12]。

因为互联网的数据流的车辆从互联网上不同,因此,我们不能直接使用互联网数据流处理方法处理的时间和空间数据流网络的车辆。近年来,有一些进展,处理时间和空间数据流网络的车辆使用复杂事件处理技术。在事件驱动体系结构网络的车辆,各种时间和空间数据流生成的传感设备抽象为基本时间和空间活动。通过一个复杂事件的查询语言,系统会得到有意义的复杂事件的基本时空事件由特定模式匹配滤波器。SpaTec穆迪提出了一个复杂事件的查询语言,它将被应用到伦敦的总线监控系统(13,14]。金等人提出了一个复杂的事件查询语言铝业,它可以描述各种事件的时空属性(15]。并提出了一个时间和空间约束事件查询语言的步骤,可以有效地描述车辆的时间和空间约束信息网络(16]。许等人提出了一个时空的事件交互模型STEIM表达时空信息的时空的事件流V2X [17]。

有四种类型的处理模型,基于复杂事件的事件流处理系统查询语言:有限自动机模型,匹配树模型,一个有向无环图模型,佩特里网模型。最糟糕的事件流处理系统的响应时间的一个重要指标的绩效评估系统。Akili Weidlich开始专注于最糟糕的事件流处理系统的响应时间(18]。嗯等人提出了一个关联约束标签方法来估计最坏响应时间的事件流处理系统19]。江等人提出一个模型汽车区块链向外传输的数据,然后给详细的理论分析和数值结果20.]。胡锦涛等人提出一个新颖的双层联盟模型分析互联网的数据处理系统的性能的车辆(21]。

分析了目前的工作并没有流处理算法的动态性能。本文算法的动态性能进行了分析通过排队论模型,从而在理论上验证算法的可行性。在本文中,我们提出一个方法来估计最坏的情况下的响应时间步事件流处理系统,基于随机Petri网和排队理论。仿真结果证明了该方法的有效性。本文的其余部分的结构如下:部分2介绍了复杂事件查询语言的步骤。部分3介绍了随机Petri网理论和排队论。部分4让一步事件流处理系统的体系结构和核心算法。部分5分析四种类型的结构化事件流处理程序实例通过排队论。部分6通过仿真验证相关结论是正确的。最后,本文最后一部分得出结论。

2。事件查询语言:一步

一步是时空约束事件查询语言,其重点是处理网络的时空约束数据的车辆。步骤包含五个类型的布尔表达式的语法,和布尔表达式的事件实例EBEXP由其他人。语法规则的步骤如下:

对象标识符的布尔表达式OBEXP:

一般的布尔表达式ABEXP数值属性:

布尔表达式TBEXP颞属性:

布尔表达式LBEXP空间属性:

布尔表达式EBEXP事件实例:

3所示。随机Petri网和排队理论

3.1。随机Petri网

随机Petri网模型与随机延迟时间与每个之间的过渡的情况可以实现及其实现。随机Petri网的性能分析的基础是建立在其状态空间马尔可夫链的同构。随机Petri网提供了一个良好的系统的性能模型的描述方法,和马尔可夫随机过程的评价提供了一个坚实的数学基础。

定义1。在连续时间随机Petri网,一个过渡需要一个延迟时间的情况下可以实现的情况下实现的。它被视为一个连续的随机变量x我(采取积极的实数)。因为排队系统中的数据流的速度让泊松分布,因此,延迟时间服从指数分布函数如下: 随机Petri网表示为SPN) = (S T;F, M0,λ),((S T;F, M0)是一个佩特里网系统,λ= {λ1,λ2,…λm}是平均实现率过渡的集合。其中,真正的参数λt > 0是实现过渡的年平均增长率t,它表示单位时间内平均执行时间。平均实现率的倒数的过渡t我被称为平均实现延迟或平均服务时间。
有三个系列的性能等价公式,平行,和选择结构随机Petri网模型,及相关结论如下:

定理1。系统B的n系列转换。假定的延迟时间n系列转换独立随机变量,他们服从指数分布函数参数λ1,λ2…λn。所以,总的等效延迟时间如下:

定理2。系统B的n并行转换。假定的延迟时间n并行转换独立随机变量,他们服从指数分布函数参数λ1,λ2…λn。所以,总的等效延迟时间如下:

定理3。系统B的n选择转换。假定的延迟时间n选择转换独立随机变量,他们服从指数分布函数参数λ1,λ2…λn。假设的实现概率过渡t我是α我。的平均延迟时间n选择转换和总等效延迟时间如下:

3.2。排队论

排队论,也称为随机服务系统理论,是一门数学学科,研究拥挤现象。它解决了最优系统设计和最优控制通过的概率特征多种服务排队系统。排队论是运筹学的一个重要分支,应用概率的一个重要分支。研究有很强的实际背景,它是由丹麦电信工程师a . k . Erlang的研究在20世纪。现在,它是一个成熟的理论。

排队现象包括两个方面:一是获得服务,和其他试图给服务。第一个被称为客户,这就需要服务。服务器给别人服务。客户和服务器组成一个排队系统。

定义2。排队系统包括三个部分:输入过程、排队规则,和服务器。排队系统的这三个部分是一个有机整体,从不同方面描述了排队系统。(1)输入过程描述了如何客户到达排队系统。它通常所描述的客户到达时间的概率分布。常见分布如下:固定长度的输入、负指数输入(泊松流),几何输入,Erlang输入,等等。(2)的排队规则排队系统的顾客接受服务。它可以分为先到先得(先),最后到先得(lcf),等等。(3)服务器的结构意味着服务器的数量和客户的服务时间。公共客户服务时间分布如下:固定长度的分布、负指数分布、几何分布。排队系统模型如下(见图1)。排队系统给出的数学表示定理4。


图1
排队系统模型。

定理4。一个排队系统可以用一个三个字母的符号表达了A / B / C。代表客户到达时间分布,B显示了服务时间的分布,C代表了服务器的数量。A和B米、D、g M代表了负指数分布,D代表的是固定长度的分布,G代表一般分布。

一个排队系统的关键性能指标如下:(1)平均队列长度l的数量,也就是说,客户的排队系统及其数学期望公式,如下: (2)客户的平均停留时间W的处理时间,也就是说,每个客户的系统及其数学期望公式,如下: (3)顾客的平均等待时间W问的等待时间,也就是说,每个客户的系统及其数学期望公式,如下:

4所示。事件流处理系统的步骤

4.1。一步事件流处理系统的体系结构

时空事件流处理系统的体系结构基于介入互联网的车辆如图2。首先,用户写事件查询表达式的步骤并发送这些表达式到事件流处理系统。其次,事件流处理系统接收事件查询表达式,并将表达式转换为事件流处理模型。然后,事件流处理系统生成相应的事件流处理程序根据事件流处理模型。事件流处理程序将开始处理接收到的事件流和生产查询结果。事件流处理程序处理接收到的事件流和生产开始查询结果。最后,查询结果将发送给用户。


图2
事件流处理系统的体系结构。

完成事件流查询,我们需要将事件查询表达式转换成事件流处理模型。有四种类型的事件流处理模型:树模型,有向无环图模型,自动机模型,佩特里网模型。佩特里网络模型可以用来模拟并发、异步的、分布式的、不确定的,并行系统。因此,我们使用Petri网模型事件处理系统。

4.2。事件流处理系统的核心算法步骤

一步事件流处理系统的主要功能是接收事件流处理Petri网模型,并返回处理结果。系统的核心算法如表所示1。

表1
的核心算法步骤事件流处理系统。

在算法中,所有的输入转换Petri网模型分为三个类别:一开始过渡(TransitionStart),中间的过渡(TransitionMid)和结束(TransitionEnd)过渡。TransitionStart的功能是检测接收到的事件实例的属性值。TransitionStart传达的信息通过共享的地方连接TransitionMid:输出的TransitionStart股票相同的变量与输入TransitionMid的地方。TransitionEnd是一种特殊的转型:它没有继承人。

在TransitionStart算法,首先,实施和其他转换将实现一步一步直到TransitionEnd沿着佩特里网结构。因为转换的数量是有限的TransitionStart TransitionMid,因此,该算法终止事件实例。假设有n佩特里网模型转换,然后算法的复杂度是O (logn)。

4.3。排队论模型的事件流处理系统

事件流的排队论模型一步处理程序基于算法1所示图3。它可以清楚地表达算法1的总体框架和加工过程的排队论模型。


图3
一步的排队论模型事件流处理程序。

我们通过排队论分析系统的动态性能。排队系统的动态性能主要是指处理时间的变化程度的服务系统,当输入数据的速度变化。首先,事件流传输到系统内存,和这些事件实例将队列。然后,他们将处理的事件流处理程序。车辆的事件流在互联网可以被看作是泊松流。服务规则是先到先得(先),和事件流处理系统的排队系统模型是一个米/米/ 1排队系统。

有两个重要的参数,分析了排队系统的动态性能:参数年代泊松事件流和参数μ服务时间分布的事件流处理系统。

因为参数的物理意义年代泊松事件流的数据传输网络,可以确定参数根据网络传输环境。接下来,我们关注的参数μ服务时间的分布。

随机Petri网是一种强大的工具来分析系统的动态性能。根据定义1,我们可以构建的随机Petri网模型事件流处理系统。我们可以分析事件流处理系统的动态性能定理4。

示例显示如下:

如图4,有三个独立的随机变量转换的延迟时间,和他们的参数λ1,λ2,λ3指数分布函数。三个随机变量代表了处理时间在每一步计算的数据流处理系统。


图4
一个例子的事件流处理程序的随机Petri网模型。

假设随机Petri网的整体延迟时间服从指数分布函数的参数λ。根据定理4,我们得到

因此,我们可以得到参数的值λ最后。

假设处理速度μ事件流处理的程序速度成正比λ的随机Petri网模型:μ=kλ(k> 0的值k与操作环境的处理器速度)。所以,我们可以分析一个事件流处理程序的动态性能根据速度参数μ事件流处理程序和传输速度参数年代事件流。

5。案例研究

有四种不同结构的事件流处理程序模型,如图5。我们分析这些例子的随机Petri网模型和排队论。

(一)
(一)
(b)
(b)
(c)
(c)
(d)
(d)
图5
四个例子的事件流处理程序的随机Petri网模型。

如数据所示5(一)-5(d),有四个事件流处理程序:例1、例2、例3、例4。例子,结构中的两个代表一个复杂的计算过程和操作。结构b代表一个复杂的计算过程或操作执行第一,然后一个操作执行。结构c代表了一个复杂的计算过程的执行和操作,然后执行或操作。结构d代表一个复杂的计算过程或操作执行第一,然后一个操作执行。在这些例子中,事件流的传输速率是s1, s2、s3和s4。他们的事件流处理的速度μ1,μ2,μ3,μ4所示。因为服务排队系统的强度ρ=年代/μ的必要和充分条件,排队系统的稳态分布ρ< 1,所以假设ρ1 = s1 /μ1 < 1,ρ2 = s2 /μ2 < 1,ρ3 = s3 /μ3 < 1,ρ4 = s4 /μ4 < 1。

为了比较这四个结构的例子的性能,我们设置参数表2。在本文的流数据处理结构,前者数据处理通常花费更少的时间,而后者数据处理需要更多的时间。因此,根据这一情况,我们假设参数设置如表所示2。根据定理4,我们可以得到这些例子所示的总体水平λ表的列。假设每个分支的跃迁概率等于选择结构。

表2
四参数的例子。

根据定理4,例1的动态性能可以计算如下:

假设事件流的传输速率是s1和事件处理程序的处理速度 = k。排队系统的服务强度 ;的数量的等待事件队列系统 ;每个事件的停留时间的排队系统 ;每个事件的等待时间的排队系统 ;排队系统的等待时间的比例 ;

同样,根据定理4例2的动态性能可以计算如下:

假设事件流的传输速率是s2,和事件处理程序的处理速度 ,排队系统的服务强度 ;的数量的等待事件队列系统 ;每个事件的停留时间的排队系统 ;每个事件的等待时间的排队系统 ;排队系统的等待时间的比例 ;

同样,根据定理4例3的动态性能可以计算如下:

假设事件流的传输速率是s3,和事件处理程序的处理速度 ,排队系统的服务强度 ;的数量的等待事件队列系统 ;每个事件的停留时间的排队系统 ;每个事件的等待时间的排队系统 ;排队系统的等待时间的比例 ;

同样,根据定理4示例4的动态性能可以计算如下:

假设事件流传输速率是s4,和事件处理程序的处理速度 ,排队系统的服务强度 ;的数量的等待事件队列系统 ;每个事件的停留时间的排队系统 ;每个事件的等待时间的排队系统 ;排队系统的等待时间的比例 ;

为了更清楚地分析动态性能上面的例子,讨论目前分为两个场景:

5.1。应用第一幕

事件流的到达率年代是不断变化的,计算机的处理速度k是没有改变。假定常数k= 100和系统的动态性能,如表所示3。

表3
场景中的示例应用程序的动态性能。

图中数据的表3如图6。有四个图的子图6。图的平均等待事件队列系统的四个例子是图6(a)。图的平均停留时间的事件队列系统的四个例子是图6(b)。图的平均等待时间的事件队列系统的四个例子是图6(c),等待时间的比例的图事件队列系统的四个例子是图6(d)。

(一)
(一)
(b)
(b)
(c)
(c)
(d)
(d)
图6
图中的示例应用程序场景的动态性能。

我们可以看到在图6当计算机处理速度并没有改变,所以有一个事件流传输速率,增加的平均等待事件,事件的平均停留时间,平均等待时间的事件,事件的等待时间的比例,这是排队系统的四个例子。此外,从图可以看出,它需要示例1中的最大处理事件时间和最小处理事件在例2。

5.2。应用程序场景两个

事件流的到达率年代不是改变,计算机的处理速度k正在发生变化。假定常数年代= 200和系统的动态性能,如表所示4。

表4
示例应用程序场景的动态性能。

图中数据的表4如图7。有四个图的子图7。图的平均等待事件队列系统的四个例子是图7(a)。图的平均停留时间的事件队列系统的四个例子是图7(b)。图的平均等待时间的事件队列系统的四个例子是图7(c),等待时间的比例的图事件队列系统的四个例子是图7(d)。

(一)
(一)
(b)
(b)
(c)
(c)
(d)
(d)
图7
动态性能的图2中的示例应用程序的场景。

我们可以看到在图7,当事件流传输速度没有变化,计算机处理速度的增加,平均的等待事件,事件的平均停留时间,和平均等待时间的事件,以及事件的等待时间的比例减少,这是排队系统的四个例子。此外,从图可以看出,它需要示例1中的最大处理事件时间和最小处理事件在例2。

6。仿真和结果

为了验证推导结果一节动态性能的四个例子,我们建立排队论的四个模拟例子的仿真工具v0.9.1 Java建模工具。为每一个例子中,仿真程序将运行100000次,我们得到结果的平均值。在仿真实验中,边界条件k= 100,年代> 0。

6.1。仿真实验一

实验与应用程序场景。当事件流到达率变化,计算机处理速度并没有改变(这里集合k= 100),仿真结果如表所示5- - - - - -8。

表5
示例1的仿真实验的结果(μ= 143.5)。
表6
例2的仿真实验的结果(μ= 320)。
表7
仿真实验的结果示例3 (μ= 240)。
表8
示例4的模拟实验的结果(μ= 202.4)。

我们在散点图绘制仿真结果,比较理论推理结果图的图8。

(一)
(一)
(b)
(b)
(c)
(c)
(d)
(d)
图8
动态性能的比较图表中的示例应用程序的场景。

从上面的图可以看出,仿真结果已经同意与之前的理论结果。此外,从散点图可以看出实验结果,随着事件流的到达率得到了阈值,事件处理时间大大增加。但是等待时间的比值和处理时间都改变了。

6.2。模拟实验两个

实验与应用程序场景。当事件流到达率没有改变(这里集合年代= 200),计算机处理速度变化,仿真结果如表所示9- - - - - -12。

表9
结果两例1的仿真实验。
表10
例2的仿真实验结果。
表11
仿真实验的结果示例3 2。
表12
例4的模拟实验的结果。

我们绘制散点图的仿真结果和理论推理结果的比较图,如图9。

(一)
(一)
(b)
(b)
(c)
(c)
(d)
(d)
图9
动态性能比较图2中的示例应用程序的场景。

从上面的图可以看出,仿真结果已经同意与之前的理论结果。此外,从散点图可以看出实验结果,以及计算速度增加,事件处理时间迅速减少。但是等待时间的比值和处理时间都改变了。

7所示。结论

在本文中,我们提出的体系结构和核心算法步骤事件流处理系统。其次,我们分析了事件流处理系统的动态性能与随机Petri网和排队论。这些动态表演包括事件流的队列长度,每个活动实例的处理时间,每个活动实例的等待时间,等待时间和比例的事件。最后,我们给四个结构例子,把他们的理论动态性能。我们还建立了模拟程序来验证推理结果的正确性,这显示了相关方法的有效性。

数据可用性

使用的数据来支持本研究的发现可以从相应的作者。

的利益冲突

作者宣称没有利益冲突。

确认

这项工作是支持的2021基础科学研究项目的南通,江苏,中国(没有。JC2021127)和江苏航运学院的科学基金会、中国(没有。HYKY / 2021 b07)。