面向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