面向CPS的时间戳不确定事件调度算法*

李芳芳，刘 冲，于 戈

东北大学 计算机科学与工程学院，沈阳 110819

面向CPS的时间戳不确定事件调度算法*

李芳芳+，刘 冲，于 戈

东北大学 计算机科学与工程学院，沈阳 110819

LI Fangfang,LIU Chong,YU Ge.Scheduling algorithm of events with imprecise timestamps for CPS.Journal of Frontiers of Computer Science and Technology,2017,11(6)：887-896.

信息物理融合系统（cyber-physical system，CPS）作为计算过程和物理过程的统一体，是集计算、通信、控制于一体的下一代智能系统。事件是连接信息世界和物理世界的重要元素，但是在实际应用中，由于数据的漏读，各个监测系统之间事件的时间粒度不匹配，来自分布式系统的事件存在着时间不同步问题等原因，会造成事件的时间戳不确定。利用时间戳不确定复杂事件的剪枝技术改进时间戳确定事件调度的低水标记算法，提出了时间戳不确定的复杂事件调度算法，并对CPS中的读写事件进行了合理调度。实验证明该算法的事件调度准确性高，保证将正确的事件执行顺序反馈给CPS系统。

调度；事件；时间戳不确定；信息物理融合系统（CPS）

1 引言

信息物理融合系统（cyber-physical system，CPS）作为计算过程和物理过程的统一体，是集计算、通信、控制于一体的下一代智能系统[1-2]，具有广泛的应用前景[3]。CPS中计算机处理系统与物理世界之间以事件的信息形式发生联系[4]，物理层和计算层的交互由事件中间件实现，是一种事件驱动的应用。当前复杂事件处理已经成为研究领域的热点内容[5-8]。CPS中的事件处理具有交互性和动态反馈性，即在监控过程当中，通过检测到的事件而触发系统相应行为，触发的动作也可以作为新的输入对系统的状态产生影响[9]。上述过程使CPS事件具有不确定性[10-12]，其中包括事件具有时间戳不确定性，比如数据的漏读，各个监测系统采集事件的时间粒度不匹配（例如有的采集器采集粒度为秒，而有的采集粒度为微秒），来自分布式系统的事件存在着时间不同步问题等原因，会造成事件发生时间不确定[13]，即时间戳不确定。

CPS终端产生的是原子事件，由于原子事件的语义十分有限，应用通常使用复杂事件表达语义，即以事件驱动的观点来处理信息系统中产生的海量数据，检测系统中的异常行为或者感兴趣的行为模式等。在原子事件合成为复杂事件之后，对于复杂事件的调度顺序也有较高的要求，错误的读写顺序会使CPS做出错误的反馈。由于时间戳不确定，事件到达的准确时间无法得知，从而无法准确获知事件的调度顺序，只能通过对时间戳的分析与运算，得出执行先后顺序的概率，进行相对准确的调度。

目前，对于时间戳确定事件的调度算法较多，可以保证对事件进行准确实时的调度。然而，对于时间戳不确定事件，尚未发现准确率较高、实时性较好的算法。本文针对时间戳不确定事件提出了结合基于时间戳剪枝技术的低水标记调度算法，该算法在准确性和实时性方面都有较好的性能。

2 相关工作

在CPS系统中，事件调度是必要的机制，传统的事件调度方法只能应用在实时反馈要求不高的系统，例如两段封锁协议算法能真正保证调度可串行化，但是没有解决死锁问题，在调度过程中可能有死锁的情况发生，在处理死锁的过程中，涉及重做和撤销操作。然而在CPS中，由于反馈的实时性，数据库中更改的数据需要立刻反馈给其他设备，对数据库的重做和撤销操作，不能保证实时反馈系统的正常运行。

在文献[14]中，以医疗护理CPS为例，结合了两段封锁协议算法和多版本并发控制方法，提出了一种适用于实时反馈系统的调度方法——低水标记算法（low water mark，LWM）。该算法通过设定低水标记lwm，能够适用于事件到达顺序与应用时间不符的情况，保证写事件能够按照应用时间顺序执行，同时通过多版本控制，确保应用时间比读事件早的写事件都执行完，才执行该读事件，从而保证了调度算法的正确性。在调度算法的并发度方面，设立两个队列分别存储未执行的读事件和写事件，使读事件和写事件根据低水标记独自进行调度，降低了读事件与写事件的耦合度，从而增加了事件之间的并发度。LWM算法中设置一个低水标记lwm，代表着数据库中所有写操作中最早的写操作的时间戳，当一个新的写操作到来，或者一个旧的写操作释放时，lwm会随之更新，LWM算法根据lwm分别同步读操作和写操作。当且仅当写操作成为共享表的所有写锁中最早的写锁，LWM才会授权写锁。LWM算法提高了锁之间的兼容性，一方面，一个读操作不会阻碍一个写操作，另一方面，不是每一个写操作都会阻碍一个读操作，从而提高事务并发执行效率。该算法只能用于时间确定的事件调度中，只有改进低水标记算法，使之能够用于时间戳不确定事件的调度，才能应用于CPS系统。

在真实情况中，事件发生时间是不确定的。在对原子事件的语义处理方法中，有很多处理时间戳不确定事件的方法。文献[12]通过原子事件合成复杂事件的合成规则，对时间戳不确定进行剪枝等一系列操作，确定原子事件合成的概率，对于合成概率相对高的原子事件，触发合成原则，合成复杂事件。

本文结合时间戳不确定事件检测的剪枝算法来改进低水标记调度算法，使之能够调度时间戳不确定的事件，同时保证事件调度的准确性和事务之间的并发性。

3 基于时间戳剪枝的不确定事件调度

3.1 算法思想

定义1（时间戳不确定事件）时间戳不确定事件采用的事件格式（event format）为(EventSource，Event-Type，EventId，UI:[lower，upper]，(p:UI→[0,1]),Attributes)。其中EventSource表示事件的来源；EventType表示事件的读写类型；EventId表示事件名称；UI: [lower，upper]是时间点集合，表示该事件有可能发生时间，lower代表最早发生时间，upper代表最晚发生时间；(p:UI→[0,1])是概率的集合，代表该事件在各个时间点可能触发的概率；Attributes表示该事件的一些特殊属性。

为了说明调度算法，定义相关变量。

Iub（initial upper bound）：事件的原始上界，事件可能发生的最晚值，也就是UI中的upper。

Ilb（initial lower bound）：事件的原始下界，事件可能发生的最早值，也就是UI中的lower。

Vub（valid upper bound）：事件的有效上界，对事件进行剪枝处理后事件的上界，在不同执行顺序下，有效上界的值也会改变，代表在这种顺序下，允许该事件发生的最晚时间。

Vlb（valid lower bound）：事件的有效下界，对事件进行剪枝处理后事件的下界，在不同执行顺序下，有效上界的值也会改变，代表在这种顺序下，允许该事件发生的最早时间。

Nts（next transaction）：算法中下一个要执行的事件，在算法运行过程中不断更新。

在时间戳不确定事件的语义处理中，当一个原子事件到来时，监测该事件可能合成复杂事件的合成规则，如果在一定时间段内，合成规则中的事件全部到达，则根据合成规则，对事件进行剪枝处理。剪枝之后，计算合成复杂事件的概率，若大于阈值则触发该合成原则，合成复杂事件，若概率低于给定阈值，则认为不具备触发合成原则的条件，不对原子事件进行合成处理。

具体来讲，当一个事件到来时，如果该事件的时间段与其他事件有重叠的部分，则生成这些事件所有可能的执行顺序，然后根据事件发生的可能概率对这些顺序进行剪枝，计算每个顺序的执行概率。例如若在一定时间段内的3个事件A、B、C的可能执行顺序为ABC、ACB、BAC、BCA、CAB和CBA，求得它们的执行概率分别为PABC、PACB、PBAC、PBCA、PCAB和PCBA，则对于这3个事件来说，事件A先执行的概率为PA=PABC+PACB，事件B先执行的概率为PB=PBAC+PBCA，事件C先执行的概率为PC=PCAB+PCBA，分别比较PA、PB、PC的大小，率先执行概率大的事件。

3.2 概率计算

本文算法运用剪枝技术对时间戳不确定事件进行剪枝，目的是为了简化某个执行顺序概率的计算，但是对某个顺序剪枝后，仍然需要对该执行顺序的执行概率进行计算。概率计算是一个循环递归算法。下面通过一个示例来说明概率计算的方法。

例1图1分别表示事件A(A，Read，A1，UI[2,5])、事件B(B，Read，B1，UI[3,6])和事件C(C，Read，C1，UI[4,8])的时间段及其执行概率，各事件的p:UI参见图1标注，后文中将事件简写为A、B、C。这3个事件可能的执行顺序分别为ABC、ACB、BCA、BAC、CAB和CBA，通过计算执行顺序为ABC的概率来说明概率计算过程。若计算顺序为ABC，则相当于事件A、事件B和事件C必须在时间点2到8之间执行完毕，且事件A先于事件B执行，事件B先于事件C执行，若事件C发生在时间点8，则要求事件A和事件B在时间点7之前以AB的执行顺序发生。用P(ABC，8)表示在时间点8之前3个事件以ABC为执行顺序的发生概率，同理P(AB，7)表示在时间点7之前两个事件以AB为执行顺序的发生概率，则可以看出，P(ABC,8)=P(AB,7)×Pc5+P(AB,6)×Pc4+P(AB,5)×Pc3+P(AB,4)×Pc2+P(AB,3)×Pc1，通过递归的方式来计算执行概率。当递归至只有一个事件时，例如事件A在4之前执行的概率P(A,4),则P(A,4)=Pa1+Pa2+Pa3。

Fig.1 Instances of events with imprecise timestamps图1 时间戳不确定事件实例

通过例1可以看出，若要计算在某个时间点t之前n个事件的执行概率(n>1)，就要计算在时间点t-1之前n-1个事件的执行概率，当n=1时，则为该事件在t时间之前执行概率和。因此，不确定时间戳概率的计算是一个递归问题，通过不断地递归，可以得出某个时间点t之前n个事件以特定顺序执行的概率。对于上述递归过程，可以将其转化为迭代算法，从而简化复杂度。

3.3 调度算法

将时间戳不确定事件处理方法与低水标记算法结合，提出本文研究的算法，计算出各个事件率先执行的概率。当一个复杂事件到达时，根据事件的读写类型的不同，分别执行以下操作。

3.3.1 读事件

当到达的事件是读事件时，则判断该事件的原始上界Iub是否小于低水标记lwm。如果Iub大于lwm，则将该读事件加入到读事件队列SLock中，等到Iub小于lwm时，再执行该事件。若Iub小于lwm，则继续判断在读事件可能发生的这段时间内是否有数据更新，即查看历史版本，是否有写事件在这段时间内对数据库进行写操作。如果历史版本没有在这个时间段内更新，则直接读取距该事件最近版本的数据库中的数据；如果数据库在这段时间内发生数据更新，则根据历史版本将读事件中的时间段分组，将各个组的概率相加，选取概率和大的组，让读事件读取该版本的数据库中的数据。读事件调度过程如算法1所示。

算法1ReadProcess（SlockQueue SL,Time[]History）

输入：写队列XL，数据库历史版本History，系统时间t

输出：更新数据库和系统时间

1.For each readtran inSLdo

2.TimeStamp[].temptime=readtran.timestamp.ToArray();

3.Time[].temphistory=new Time[];

4. For each timetin History do

5. If(t

6. continue;

7. Else

8. If(his[i]>=t.Iub)then

9. break;

10. Else

11. Addtinto temphistory;

12.Divide readtrans.timestamp into groups with temphistory;

13.Calculate the confidence of each group;

14.The Max group will be read;

15.Print readtran.idand the group;

16.Release readtran fromSL;

下面通过一个例子说明本文算法对读事件的调度方法。

例2数据库的历史版本的时间标签为History(1, 3,5,8)，其中1、3、5、8分别代表着数据库1、3、5、8时间点有数据更新，如图2中三角标记所注。读事件A、B的时间戳及其概率分布如图2所示。下面假设读事件A、B在lwm为7时到达，A事件的Iub为6，小于lwm，则读取数据库中的历史版本，发现在事件A可能执行的时间段中，在3和5两个时间点，数据库都发生了数据更新，则将事件A的时间段以时间点3、5分开，分为3个时间段(2)、(3,4)、(5,6)，事件A读取时间点3之前的版本的概率为0.1，读取时间点3更新后的数据库中数据的概率为0.2+0.4=0.6，读取时间点5更新后的数据库中数据的概率为0.2+0.1=0.3。之后比较事件在这3个时间段内执行的概率，得出事件A在(3,4)这个时间段执行的概率最高，因此事件A读取的数据库版本为时间点3时数据库。对于事件B来说，由于B的Iub大于lwm，也就是说可能有比读事件B更早执行的写事件还未发生，因此将B事件加入到读事件的队列中，当lwm更新到比B事件的Iub大之后，再对B事件进行调度。虽然这样的调度方法可能会影响事件反馈的实时性，但是这样能使事务执行的正确率大大提升，并且在反馈的实时性方面，延迟的造成主要是由于时间的不确定，而时间的不确定是由触发器、网络传输等硬件问题引起的，因此这样微小的延迟在时间不确定的情况下是可以接受的。

Fig.2 Instances of reading event图2 读事件实例

3.3.2 写操作

当到达事件为写事件的时候，首先将写事件加入到写队列中，写队列为XLock={xl1.t1,xl2.t2,…,xln.tn}，然后更新Fts（first transaction），Fts表示当前写队列所有事件中Ilb最小的写事件，接着更新lwm，lwm的值为当前写队列所有事件中Ilb最小的值，也就是Fts的之后，遍历写队列XLock，找出事件的Ilb

剪枝算法对于一个可能的执行顺序m(E(1),E(2),…,E(n)),E(i)是满足该执行顺序的一个事件，其中i代表该事件在执行顺序中的位置，对该顺序进行两次遍历。

第一次遍历，确定有效下界。

对于某个执行顺序，若E(i)为执行顺序中第一个事件，即i=1，则E(i).Vlb=E(i).Ilb；

若E(i)不是该顺序中第一个事件，则E(i).Vlb= max(E(i-1).Vlb+1,E(i).Ilb)。

这样，经过第一次遍历之后，会确定每一个事件的有效下界Vlb。

第二次遍历，确定有效上界。

对于某个执行顺序，若E(i)为该顺序中最后一个事件，即i=n，则E(i).Vub=E(i).Iub；

若E(i)不是合成原则中第一个事件，则E(i).Vub= min(E(i+1).Vub-1,E(i).Iub)。

如果某个事件的Vub小于该事件的Vlb，那么该执行顺序不可能发生，因此该顺序的概率为0；如果所有事件的Vub都大于等于该事件的Vlb，则通过概率计算，得出该执行顺序的执行概率。计算出某个顺序的执行概率后，更新备选事件队列buffer中事件率先执行的概率，将这个执行顺序的概率加到该执行顺序第一个事件的率先执行概率中。剪枝过程如算法2所示。

算法2CutTrans（Transaction[]seq）

输入：待剪枝的事件顺序

输出：seq剪枝后的结果是否可行

1.bool OKCheck=true;

2.seq[0].Vlb=seq[0].Ilb;//set theVlbof the first transaction

3.seq[seq.Length-1].Vub=seq[seq.Length-1].Iub; //set theVubof the last transaction

4.For each transactiontin seq do

5. If(t[i-1].Vlb+1

6.t[i].Vlb=t[i].Ilb;

7.Elset[i].Vlb=t[i-1].Vlb+1;

8.If(t[i+1].Vub-1

9.t[i].Vub=t[i+1].Vub-1

10.Elset[i].Vub=t[i].Iub;//setVubfor each transaction

11. If(t[i].Vub

12. OKCheck=false;

13. break;

14.Return OKCheck；

在对buffer中所有可能的执行顺序都剪枝并计算概率后，找出buffer的所有写事件中率先执行概率最大的写事件，将其设置为下一个执行的写事件Nts（next transaction）。当数据库中没有写锁限制时，从写队列中调度执行Nts，同时更新数据库的历史版本History，记录更新事件，用以读事件的调度。接着将该事件从写队列中释放，然后用以上方法更新lwm、Fts和Nts。

例3如图3所示，事件A、事件B、事件C和事件D的执行时间点及其概率分布，通过每个事件的时间点，可以得出事件A.Ilb=2,A.Iub=6；同理可以得出，B.Ilb=1,B.Iub=5;C.Ilb=4,C.Iub=8。当3个事件都在写事件队列时，首先找到写队列中Ilb最小的写事件为事件B，则对Fts和lwm赋值，令Fts=B,lwm=B.Iub=1。之后遍历整个队列，发现A.Ilb=2<5=B.Iub,B.Ilb= 1<5=B.Iub,C.Ilb=4<5=B.Iub，则将事件A、事件B和事件C加入到buffer中，得到6种可能的执行顺序分别为ABC、ACB、BCA、BAC、CAB和CBA。接着对这6种可能的执行顺序进行剪枝操作并计算概率，每种顺序的剪枝处理和概率计算的结果如下：

（1）ABC顺序。A.Vlb=2,A.Vub=4,B.Vlb=3,B.Vub=5,C.Vlb=4,C.Vub=8，每一个事件的Vub都不小于该事件的Vlb，因此该顺序是有可能发生的，发生的概率P(ABC)=0.526。

（2）ACB顺序。A.Vlb=2.A.Vub=3,B.Vlb=5,B.Vub=5，C.Vlb=4，C.Vub=4，每一个事件的Vub都不小于该事件的Vlb，因此该顺序是有可能发生的，发生的概率P(ACB)=0.051。

（3）BCA顺序。A.Vlb=5,A.Vub=6,B.Vlb=1,B.Vub=4,C.Vlb=4,C.Vub=5，每一个事件的Vub都不小于该事件的Vlb，因此该顺序是有可能发生的，发生的概率P(BCA)=0.015。

（4）BAC顺序。A.Vlb=2,A.Vub=6,B.Vlb=1，B.Vub=5,C.Vlb=4,C.Vub=8，每一个事件的Vub都不小于该事件的Vlb，因此该顺序是有可能发生的，发生的概率P(BAC)=0.147。

（5）CAB顺序。A.Vlb=5,A.Vub=4,B.Vlb=6,B.Vub=5,C.Vlb=4,C.Vub=3，其中有事件的Vub小于该事件的Vlb，因此该顺序不可能发生，即该顺序发生的概率P(CAB)=0。

（6）CBA顺序。A.Vlb=6,A.Vub=6,B.Vlb=5,B.Vub=5,C.Vlb=4,C.Vub=4，每一个事件的Vub都不小于该事件的Vlb，因此该顺序是有可能发生的，发生的概率P(CBA)=0.003。

Fig.3 Instances of writing event图3 写事件实例

得出每个顺序的执行概率后，计算每个事件的率先执行概率，事件A率先执行的概率为Pa=P(ABC)+P(ACB)=0.577；事件B率先执行的概率为Pb=P(BAC)+P(BCA)=0.162；事件C率先执行的概率为Pc=P(CAB)+P(CBA)=0.003。比较3个事件的率先执行概率，有Pb>Pa>Pc，也就是说事件B率先执行的概率最大，因此将下一个执行事件Nts设置为事件B，等到数据库中没有写锁限制时，调度Nts事件，从写队列中释放Nts事件，并根据Nts事件的具体内容对数据库进行上锁，等到Nts事件的操作完成后，释放对数据库的写锁，更新数据库的历史版本History，并重新从写队列中调度Nts事件。在释放Nts事件，或当有新的写事件加入时，更新写队列中的Nts事件、Fts事件以及lwm的值。

3.4 算法分析

本文算法注重时间戳不确定事件中每个时间点及其概率，无论时间点与概率怎样分布，都将二者结合起来，再对事件群进行处理，从理论上能够更好地利用每一个时间点的概率，获得更准确的调度顺序，提高调度算法的准确率。

对于时间戳不确定的事件，在一定时间段内，可能有多种事件发生顺序，本文算法首先将同一时间段内可能的事件发生顺序全部列举出来，并依次计算出每种顺序可能发生的概率。在此过程中，通过对时间段剪枝的方法，简化概率的计算。剪枝操作可以减去该顺序中每个事件不可能发生的时间点，从而将长时间段减为短时间段。虽然有时对于某些顺序，剪枝操作是多余的，例如例3中对于发生顺序为BAC的情况，剪枝操作没有使任何一个事件的时间段变短，但是对于其他顺序来说，剪枝操作能够很有效地剪短时间段，方便概率计算。尤其是对于不可能的发生顺序来说，例如例3中的CAB顺序，剪枝操作可以在不用计算概率的情况下，就能得知该顺序的发生概率为0。因此，对于全体事件可能的发生顺序来说，对每个事件顺序都进行剪枝操作，可以有效地剪短时间段，为概率的计算提供很大帮助。

在得到每种顺序发生的概率后，计算出每个事件率先执行的概率。某个事件率先执行的概率等于在全部可能的执行顺序中第一个发生事件为该事件的执行顺序的发生概率的和。事件率先执行的概率越高，代表在这一时间段内，该事件的应用时间最早的概率越高，因此应选取概率最高的事件作为下一个执行事件进行调度。

4 实验

参照相关文献[13,15]的实验方法，本文实现了一个事件流产生器，对时间戳不确定事件的调度准确率进行测试和比较。本文另外提出了两种满足时间戳不确定事件的LWM基本改进调度算法，将它们与本文提出的利用剪枝算法的LWM调度算法进行了对比。

基本改进算法中，一种是平均时间算法，即取得每个时间段的平均时间点后，结合LWM算法，当新的事件到来时，计算其平均时间点，此时低水标记lwm代表数据库中所有写操作中最小值，当一个新的写操作到来，或者一个旧的写操作释放时，lwm会随之更新。另一种是初始时间算法，即选取时间戳不确定的事件中的Ilb作为调度时间点，使用LWM算法对时间戳不确定的事件进行调度，将未被执行的事件按照读写类型不同，分别加入到读队列和写队列中，此时lwm设置为数据库中所有写操作Ilb的最小值，当一个新的写操作到来，或者一个旧的写操作释放时，lwm会随之更新。为对比3种算法的性能，设计了4个实验。

实验1在事件量不同的情况下，比较3种算法调度事件的准确率。图4为3种算法调度事件量为100、300和600时的准确率。

Fig.4 Event amount vs.accuracy图4 事件数量对准确率的影响

实验1中事件的不确定时间段长度不变，时间段中时间点的概率分布方式随机分布，并且事件的读写比例为5∶5，只改变事件量，从而分析不同事件量对3种算法的影响。从图4中可以看出，事件量较小时，3种算法调度的准确性相对较高，随着事件量的增加，事件调度的准确性稍有下降，但基本能趋于固定值，因此算法的准确性可以根据处理大量事件时的准确率来衡量。同时可以发现，3种算法中，运用时间戳剪枝的方法与LWM结合，能更好地保证调度的准确性，这一结果与理论中得到的结论相同。通过实验可以看出，事件量较大时，时间戳剪枝结合LWM的算法能够保证事件调度的准确率在86%左右。

实验2在时间段长度不同时，比较3种算法调度事件的准确率。图5为在时间段长度为3、5和7以及时间段长度不固定时，3种算法调度的准确率。

Fig.5 Interval length vs.accuracy图5 时间段长度对准确率的影响

实验2中的事件量为600，时间段中时间点的概率分布方式为随机分布，并且事件的读写比例为5∶5，只改变事件的时间段长度，用来分析不同的时间段长度对3种算法的影响。从图5中可以看出，当事件数量达到一定程度时，时间段的长度越短，调度的准确率越高。这是显而易见的，当时间段长度为1时，这3种算法就是经典的低水标记算法，因此正确率最高，随着时间段长度增加，事件执行的准确时间也就越难确定，调度的准确率也会随之下降。从整体来看，对于不同长度的时间段，时间戳剪枝结合LWM的算法的准确性最好。

实验3在时间概率分布类型不同的情况下，比较3种算法调度事件的准确率。图6为面对时间分布类型为正态分布、平均分布和随机分布的事件时，3种算法调度的准确率。

实验3中的事件量为600，时间段的长度固定为5，并且事件的读写比例为5∶5，只改变事件时间点的概率分布类型，用来分析不同的事件概率分布类型对3种算法的影响。从图6中可以看出，取平均时间为调度时间点结合LWM算法和取原始上界为调度时间点结合LWM算法在处理正态分布和平均分布时，调度的准确度是一样的。这是由于无论是正态分布还是随机分布，取平均时间与取原始上界不会导致事件的顺序发生变化，从而对事件调度的结果也一样。同时可以看出，与其他两种算法相比，时间戳剪枝结合LWM算法对于各种概率分布类型的事件，都能有较高的准确性。

Fig.6 Probability distribution vs.accuracy图6 概率分布对准确率的影响

实验4在事件读写比例不同时，比较3种算法调度事件的正确率。图7为事件读写比例分别为3∶7、5∶5、7∶3时，3种算法调度的准确率。

Fig.7 Rate of reading and writing vs.accuracy图7 读写事件比例对准确率的影响

实验4中的事件量为600，时间段的长度固定为5，并且事件的时间点概率分布类型为随机分布，只改变事件的读写比例，用来分析不同的读写比例对3种算法的影响。从图7中可以得出，随着读写比例的增加，3种算法的执行准确率都会随之提高，这从理论上是很容易解释的。本文算法对读事件的处理采用数据库多版本控制的方法，因此一个读事件是否能被正确调度取决于该读事件读到的数据库版本。写事件数量越少，数据库的历史版本就越少，因此读事件读到正确版本的可能性就越高。同时可以看出，与其他两种算法相比，时间戳剪枝结合LWM算法对于各种读写比例，都能有较高的准确性。

通过以上4组实验，可以总结出时间戳不确定事件的各种因素对调度算法准确性的影响。对本文出现的时间不确定调度算法的准确率影响较大的因素有两个：不确定时间段的长度和事件的读写比例。不确定时间段越短，读事件在所有事件中所占的比例越高，算法的准确性就越好。事件量和时间点概率分布类型对算法的准确度影响不大。

同时，通过比较3种调度算法可以看出，在各种条件下，相对于取原始上界为调度时间点结合LWM算法和取平均时间为调度时间点结合LWM算法，时间戳剪枝结合LWM算法都能有更高的准确性，因此时间戳剪枝结合LWM算法是一个更好的时间戳不确定的复杂事件调度算法。

5 结束语

事件是CPS中的重要元素，具有时间戳不确定的特点，本文结合时间戳不确定的事件检测和优化算法及支持确定时间戳的事件调度算法LWM提出了满足CPS中时间戳不确定的事件调度算法，实验证明本文算法可以达到较高的调度准确率。

[1]Wing J M.Cyber-physical systems research charge[C/OL]// Proceedings of the Cyber-Physical Systems Summit,St.Louis, USA,Apr 24-25,2008.http://www.cpsweek.org/.

[2]Lee E A.Cyber physical systems:design challenges[C]//Proceedings of the 11th IEEE Symposium on Object Oriented Real-Time Distributed Computing,Orlando,USA,May 5-7,2008.Piscataway,USA:IEEE,2008:363-369.

[3]Rajkumar R,Lee I,Sha L,et al.Cyber-physical systems: the next computing revolution[C]//Proceedings of the 47th Design Automation Conference,Anaheim,USA,Jun 13-18,2010.Piscataway,USA:IEEE,2010:731-736.

[4]Talcott C.Cyber-physical systems and events[M]//LNCS 5380:Software-Intensive Systems and New Computing Paradigms.Berlin,Heidelberg:Springer,2008:101-115.

[5]Zhang Haopeng,Diao Yanlei,Immerman N.On complexity and optimization of expensive queries in complex event processing[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data,Snowbird, USA,Jun 22-27,2014.New York:ACM,2014:217-228.

[6]Liu Kezhong,Zhuang Yang,Zhou Shaolong,et al.Event detection method based on belief model for wireless sensor networks[J].Journal of Beijing University of Posts and Telecommunications,2015,38(1):61-66.

[7]Lei Chuan,Rundensteiner E A.Robust distributed query processing for streaming data[J].ACM Transactions on Database Systems,2014,39(2):95-118.

[8]Braun L,Etter T,Gasparis G,et al.Analytics in motion:high performance event-processing and real-time analytics in the same database[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data,Melbourne, Australia,May 31-Jun 4,2015.New York:ACM,2015:251-264.

[9]Wang Di,Rundensteriner E A,Wang Han,et al.Active complex event processing:applications in real-time health care [J].Proceedings of the VLDB Endowment,2010,3(1/2): 1545-1548.

[10]Wasserkrug S,Gal A,Etzion O,et al.Efficient processing of uncertain events in rule-based systems[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(1):45-58.

[11]Wang Yongheng,Cao Kening,Zhang XiaoMing.Complex event processing over distributed probabilistic event streams [J].Computers and Mathematics with Applications,2013, 66(10):1808-1821.

[12]Tran T T L,Peng Liping,Diao Yanlei,et al.CLARO:modeling and processing uncertain data streams[J].The International Journal on Very Large Data Bases,2012,21(5):651-676.

[13]Zhang Haopeng,Diao Yanlei,Immerman N.Recognizing patterns in streams with imprecise timestamps[J].Proceedings of the VLDB Endowment,2010,3(1/2):244-255.

[14]Wang Di,Rundensteiner E A,Iii R T E.Active complex event processing over event streams[J].Proceedings of the VLDB Endowment,2011,4(10):634-645.

[15]Zhang Haopeng,Diao Yanlei,Immerman N.Recognizing patterns instreams with imprecise timestamps[J].Information Systems,2013,38(8):1187-1211.

附中文参考文献：

[6]刘克中,庄洋,周少龙,等.基于节点感知信任度模型的无线传感网络事件检测方法[J].北京邮电大学学报,2015, 38(1):61-66.

李芳芳（1977—），女，黑龙江哈尔滨人，2009年于东北大学获得博士学位，现为东北大学计算机科学与工程学院讲师，CCF会员，主要研究领域为数据库，CPS数据管理等。

LIU Chong was born in 1993.He is an M.S.candidate at Northeastern University.His research interests include database system and machine learning,etc.

刘冲（1993—），男，内蒙古包头人，东北大学硕士研究生，主要研究领域为数据库系统，机器学习等。

YU Ge was born in 1962.He received the M.S.degree in computer science from Northeastern University in 1986, and Ph.D.degree in computer science from Kyushu University of Japan in 1996.Now he is a professor and Ph.D. supervisor at Northeastern University,the senior member of CCF,and the member of ACM and IEEE.His research interests include database theory and technology,distributed system,parallel computing and cloud computing,etc.

于戈（1962—），男，辽宁大连人，1986年于东北大学计算机专业获得硕士学位，1996年于日本九州大学获得计算机工学博士学位，现为东北大学教授、博士生导师，中国计算机学会理事，美国ACM和IEEE会员，主要研究领域为数据库系统，分布式系统，并行计算，云计算等。

SchedulingAlgorithm of Events with Imprecise Timestamps for CPS*

LI Fangfang+,LIU Chong,YU Ge
School of Computer Science and Engineering,Northeastern University,Shenyang 110819,China
+Corresponding author:E-mail:lifangfang@mail.neu.edu.cn

Cyber-physical system(CPS)is a novel intelligent system integrating computing and physical procedures,which combines computing,communication and control technologies.Event is the key element to link the cyber world and the physical world.However,the time stamp of the event is imprecise in practical applications because of data missing,mismatching of the time granularities of event from different monitoring systems,or asynchronism of events in the distributed systems and so on.By improving the scheduling algorithm of events with precise timestamps named low water mark leveraging the pruning algorithm of composite events with imprecise timestamps, this paper proposes a scheduling algorithm of events with imprecise timestamps,which supports effective scheduling of reading events and writing events in CPS.The experiments verify that the scheduling algorithm is more accurate, which guarantees providing the correct feedback of event sequences to CPS.

scheduling;events;imprecise the timestamps;cyber-physical system(CPS)

ng was born in 1977.She

the Ph.D.degree in computer science from Northeastern University in 2009.Now she is a lecturer at Northeastern University,and the member of CCF.Her research interests include database and data management of CPS,etc.

A

TP311.13

*The National Natural Science Foundation of China under Grant No.61272180(国家自然科学基金);the Fundamental Research Funds for the Central Universities of China under Grant No.140404013(中央高校基本科研业务费专项资金).

Received 2016-06,Accepted 2016-08.

CNKI网络优先出版:2016-08-15,http://www.cnki.net/kcms/detail/11.5602.TP.20160815.1659.006.html