李芳芳，劉 沖，于 戈

東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110819

面向CPS的時(shí)間戳不確定事件調(diào)度算法*

李芳芳+，劉 沖，于 戈

東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 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.

信息物理融合系統(tǒng)（cyber-physical system，CPS）作為計(jì)算過程和物理過程的統(tǒng)一體，是集計(jì)算、通信、控制于一體的下一代智能系統(tǒng)。事件是連接信息世界和物理世界的重要元素，但是在實(shí)際應(yīng)用中，由于數(shù)據(jù)的漏讀，各個(gè)監(jiān)測(cè)系統(tǒng)之間事件的時(shí)間粒度不匹配，來自分布式系統(tǒng)的事件存在著時(shí)間不同步問題等原因，會(huì)造成事件的時(shí)間戳不確定。利用時(shí)間戳不確定復(fù)雜事件的剪枝技術(shù)改進(jìn)時(shí)間戳確定事件調(diào)度的低水標(biāo)記算法，提出了時(shí)間戳不確定的復(fù)雜事件調(diào)度算法，并對(duì)CPS中的讀寫事件進(jìn)行了合理調(diào)度。實(shí)驗(yàn)證明該算法的事件調(diào)度準(zhǔn)確性高，保證將正確的事件執(zhí)行順序反饋給CPS系統(tǒng)。

調(diào)度；事件；時(shí)間戳不確定；信息物理融合系統(tǒng)（CPS）

1 引言

信息物理融合系統(tǒng)（cyber-physical system，CPS）作為計(jì)算過程和物理過程的統(tǒng)一體，是集計(jì)算、通信、控制于一體的下一代智能系統(tǒng)[1-2]，具有廣泛的應(yīng)用前景[3]。CPS中計(jì)算機(jī)處理系統(tǒng)與物理世界之間以事件的信息形式發(fā)生聯(lián)系[4]，物理層和計(jì)算層的交互由事件中間件實(shí)現(xiàn)，是一種事件驅(qū)動(dòng)的應(yīng)用。當(dāng)前復(fù)雜事件處理已經(jīng)成為研究領(lǐng)域的熱點(diǎn)內(nèi)容[5-8]。CPS中的事件處理具有交互性和動(dòng)態(tài)反饋性，即在監(jiān)控過程當(dāng)中，通過檢測(cè)到的事件而觸發(fā)系統(tǒng)相應(yīng)行為，觸發(fā)的動(dòng)作也可以作為新的輸入對(duì)系統(tǒng)的狀態(tài)產(chǎn)生影響[9]。上述過程使CPS事件具有不確定性[10-12]，其中包括事件具有時(shí)間戳不確定性，比如數(shù)據(jù)的漏讀，各個(gè)監(jiān)測(cè)系統(tǒng)采集事件的時(shí)間粒度不匹配（例如有的采集器采集粒度為秒，而有的采集粒度為微秒），來自分布式系統(tǒng)的事件存在著時(shí)間不同步問題等原因，會(huì)造成事件發(fā)生時(shí)間不確定[13]，即時(shí)間戳不確定。

CPS終端產(chǎn)生的是原子事件，由于原子事件的語(yǔ)義十分有限，應(yīng)用通常使用復(fù)雜事件表達(dá)語(yǔ)義，即以事件驅(qū)動(dòng)的觀點(diǎn)來處理信息系統(tǒng)中產(chǎn)生的海量數(shù)據(jù)，檢測(cè)系統(tǒng)中的異常行為或者感興趣的行為模式等。在原子事件合成為復(fù)雜事件之后，對(duì)于復(fù)雜事件的調(diào)度順序也有較高的要求，錯(cuò)誤的讀寫順序會(huì)使CPS做出錯(cuò)誤的反饋。由于時(shí)間戳不確定，事件到達(dá)的準(zhǔn)確時(shí)間無法得知，從而無法準(zhǔn)確獲知事件的調(diào)度順序，只能通過對(duì)時(shí)間戳的分析與運(yùn)算，得出執(zhí)行先后順序的概率，進(jìn)行相對(duì)準(zhǔn)確的調(diào)度。

目前，對(duì)于時(shí)間戳確定事件的調(diào)度算法較多，可以保證對(duì)事件進(jìn)行準(zhǔn)確實(shí)時(shí)的調(diào)度。然而，對(duì)于時(shí)間戳不確定事件，尚未發(fā)現(xiàn)準(zhǔn)確率較高、實(shí)時(shí)性較好的算法。本文針對(duì)時(shí)間戳不確定事件提出了結(jié)合基于時(shí)間戳剪枝技術(shù)的低水標(biāo)記調(diào)度算法，該算法在準(zhǔn)確性和實(shí)時(shí)性方面都有較好的性能。

2 相關(guān)工作

在CPS系統(tǒng)中，事件調(diào)度是必要的機(jī)制，傳統(tǒng)的事件調(diào)度方法只能應(yīng)用在實(shí)時(shí)反饋要求不高的系統(tǒng)，例如兩段封鎖協(xié)議算法能真正保證調(diào)度可串行化，但是沒有解決死鎖問題，在調(diào)度過程中可能有死鎖的情況發(fā)生，在處理死鎖的過程中，涉及重做和撤銷操作。然而在CPS中，由于反饋的實(shí)時(shí)性，數(shù)據(jù)庫(kù)中更改的數(shù)據(jù)需要立刻反饋給其他設(shè)備，對(duì)數(shù)據(jù)庫(kù)的重做和撤銷操作，不能保證實(shí)時(shí)反饋系統(tǒng)的正常運(yùn)行。

在文獻(xiàn)[14]中，以醫(yī)療護(hù)理CPS為例，結(jié)合了兩段封鎖協(xié)議算法和多版本并發(fā)控制方法，提出了一種適用于實(shí)時(shí)反饋系統(tǒng)的調(diào)度方法——低水標(biāo)記算法（low water mark，LWM）。該算法通過設(shè)定低水標(biāo)記lwm，能夠適用于事件到達(dá)順序與應(yīng)用時(shí)間不符的情況，保證寫事件能夠按照應(yīng)用時(shí)間順序執(zhí)行，同時(shí)通過多版本控制，確保應(yīng)用時(shí)間比讀事件早的寫事件都執(zhí)行完，才執(zhí)行該讀事件，從而保證了調(diào)度算法的正確性。在調(diào)度算法的并發(fā)度方面，設(shè)立兩個(gè)隊(duì)列分別存儲(chǔ)未執(zhí)行的讀事件和寫事件，使讀事件和寫事件根據(jù)低水標(biāo)記獨(dú)自進(jìn)行調(diào)度，降低了讀事件與寫事件的耦合度，從而增加了事件之間的并發(fā)度。LWM算法中設(shè)置一個(gè)低水標(biāo)記lwm，代表著數(shù)據(jù)庫(kù)中所有寫操作中最早的寫操作的時(shí)間戳，當(dāng)一個(gè)新的寫操作到來，或者一個(gè)舊的寫操作釋放時(shí)，lwm會(huì)隨之更新，LWM算法根據(jù)lwm分別同步讀操作和寫操作。當(dāng)且僅當(dāng)寫操作成為共享表的所有寫鎖中最早的寫鎖，LWM才會(huì)授權(quán)寫鎖。LWM算法提高了鎖之間的兼容性，一方面，一個(gè)讀操作不會(huì)阻礙一個(gè)寫操作，另一方面，不是每一個(gè)寫操作都會(huì)阻礙一個(gè)讀操作，從而提高事務(wù)并發(fā)執(zhí)行效率。該算法只能用于時(shí)間確定的事件調(diào)度中，只有改進(jìn)低水標(biāo)記算法，使之能夠用于時(shí)間戳不確定事件的調(diào)度，才能應(yīng)用于CPS系統(tǒng)。

在真實(shí)情況中，事件發(fā)生時(shí)間是不確定的。在對(duì)原子事件的語(yǔ)義處理方法中，有很多處理時(shí)間戳不確定事件的方法。文獻(xiàn)[12]通過原子事件合成復(fù)雜事件的合成規(guī)則，對(duì)時(shí)間戳不確定進(jìn)行剪枝等一系列操作，確定原子事件合成的概率，對(duì)于合成概率相對(duì)高的原子事件，觸發(fā)合成原則，合成復(fù)雜事件。

本文結(jié)合時(shí)間戳不確定事件檢測(cè)的剪枝算法來改進(jìn)低水標(biāo)記調(diào)度算法，使之能夠調(diào)度時(shí)間戳不確定的事件，同時(shí)保證事件調(diào)度的準(zhǔn)確性和事務(wù)之間的并發(fā)性。

3 基于時(shí)間戳剪枝的不確定事件調(diào)度

3.1 算法思想

定義1（時(shí)間戳不確定事件）時(shí)間戳不確定事件采用的事件格式（event format）為(EventSource，Event-Type，EventId，UI:[lower，upper]，(p:UI→[0,1]),Attributes)。其中EventSource表示事件的來源；EventType表示事件的讀寫類型；EventId表示事件名稱；UI: [lower，upper]是時(shí)間點(diǎn)集合，表示該事件有可能發(fā)生時(shí)間，lower代表最早發(fā)生時(shí)間，upper代表最晚發(fā)生時(shí)間；(p:UI→[0,1])是概率的集合，代表該事件在各個(gè)時(shí)間點(diǎn)可能觸發(fā)的概率；Attributes表示該事件的一些特殊屬性。

為了說明調(diào)度算法，定義相關(guān)變量。

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

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

Vub（valid upper bound）：事件的有效上界，對(duì)事件進(jìn)行剪枝處理后事件的上界，在不同執(zhí)行順序下，有效上界的值也會(huì)改變，代表在這種順序下，允許該事件發(fā)生的最晚時(shí)間。

Vlb（valid lower bound）：事件的有效下界，對(duì)事件進(jìn)行剪枝處理后事件的下界，在不同執(zhí)行順序下，有效上界的值也會(huì)改變，代表在這種順序下，允許該事件發(fā)生的最早時(shí)間。

Nts（next transaction）：算法中下一個(gè)要執(zhí)行的事件，在算法運(yùn)行過程中不斷更新。

在時(shí)間戳不確定事件的語(yǔ)義處理中，當(dāng)一個(gè)原子事件到來時(shí)，監(jiān)測(cè)該事件可能合成復(fù)雜事件的合成規(guī)則，如果在一定時(shí)間段內(nèi)，合成規(guī)則中的事件全部到達(dá)，則根據(jù)合成規(guī)則，對(duì)事件進(jìn)行剪枝處理。剪枝之后，計(jì)算合成復(fù)雜事件的概率，若大于閾值則觸發(fā)該合成原則，合成復(fù)雜事件，若概率低于給定閾值，則認(rèn)為不具備觸發(fā)合成原則的條件，不對(duì)原子事件進(jìn)行合成處理。

具體來講，當(dāng)一個(gè)事件到來時(shí)，如果該事件的時(shí)間段與其他事件有重疊的部分，則生成這些事件所有可能的執(zhí)行順序，然后根據(jù)事件發(fā)生的可能概率對(duì)這些順序進(jìn)行剪枝，計(jì)算每個(gè)順序的執(zhí)行概率。例如若在一定時(shí)間段內(nèi)的3個(gè)事件A、B、C的可能執(zhí)行順序?yàn)锳BC、ACB、BAC、BCA、CAB和CBA，求得它們的執(zhí)行概率分別為PABC、PACB、PBAC、PBCA、PCAB和PCBA，則對(duì)于這3個(gè)事件來說，事件A先執(zhí)行的概率為PA=PABC+PACB，事件B先執(zhí)行的概率為PB=PBAC+PBCA，事件C先執(zhí)行的概率為PC=PCAB+PCBA，分別比較PA、PB、PC的大小，率先執(zhí)行概率大的事件。

3.2 概率計(jì)算

本文算法運(yùn)用剪枝技術(shù)對(duì)時(shí)間戳不確定事件進(jìn)行剪枝，目的是為了簡(jiǎn)化某個(gè)執(zhí)行順序概率的計(jì)算，但是對(duì)某個(gè)順序剪枝后，仍然需要對(duì)該執(zhí)行順序的執(zhí)行概率進(jìn)行計(jì)算。概率計(jì)算是一個(gè)循環(huán)遞歸算法。下面通過一個(gè)示例來說明概率計(jì)算的方法。

例1圖1分別表示事件A(A，Read，A1，UI[2,5])、事件B(B，Read，B1，UI[3,6])和事件C(C，Read，C1，UI[4,8])的時(shí)間段及其執(zhí)行概率，各事件的p:UI參見圖1標(biāo)注，后文中將事件簡(jiǎn)寫為A、B、C。這3個(gè)事件可能的執(zhí)行順序分別為ABC、ACB、BCA、BAC、CAB和CBA，通過計(jì)算執(zhí)行順序?yàn)锳BC的概率來說明概率計(jì)算過程。若計(jì)算順序?yàn)锳BC，則相當(dāng)于事件A、事件B和事件C必須在時(shí)間點(diǎn)2到8之間執(zhí)行完畢，且事件A先于事件B執(zhí)行，事件B先于事件C執(zhí)行，若事件C發(fā)生在時(shí)間點(diǎn)8，則要求事件A和事件B在時(shí)間點(diǎn)7之前以AB的執(zhí)行順序發(fā)生。用P(ABC，8)表示在時(shí)間點(diǎn)8之前3個(gè)事件以ABC為執(zhí)行順序的發(fā)生概率，同理P(AB，7)表示在時(shí)間點(diǎn)7之前兩個(gè)事件以AB為執(zhí)行順序的發(fā)生概率，則可以看出，P(ABC,8)=P(AB,7)×Pc5+P(AB,6)×Pc4+P(AB,5)×Pc3+P(AB,4)×Pc2+P(AB,3)×Pc1，通過遞歸的方式來計(jì)算執(zhí)行概率。當(dāng)遞歸至只有一個(gè)事件時(shí)，例如事件A在4之前執(zhí)行的概率P(A,4),則P(A,4)=Pa1+Pa2+Pa3。

Fig.1 Instances of events with imprecise timestamps圖1 時(shí)間戳不確定事件實(shí)例

通過例1可以看出，若要計(jì)算在某個(gè)時(shí)間點(diǎn)t之前n個(gè)事件的執(zhí)行概率(n>1)，就要計(jì)算在時(shí)間點(diǎn)t-1之前n-1個(gè)事件的執(zhí)行概率，當(dāng)n=1時(shí)，則為該事件在t時(shí)間之前執(zhí)行概率和。因此，不確定時(shí)間戳概率的計(jì)算是一個(gè)遞歸問題，通過不斷地遞歸，可以得出某個(gè)時(shí)間點(diǎn)t之前n個(gè)事件以特定順序執(zhí)行的概率。對(duì)于上述遞歸過程，可以將其轉(zhuǎn)化為迭代算法，從而簡(jiǎn)化復(fù)雜度。

3.3 調(diào)度算法

將時(shí)間戳不確定事件處理方法與低水標(biāo)記算法結(jié)合，提出本文研究的算法，計(jì)算出各個(gè)事件率先執(zhí)行的概率。當(dāng)一個(gè)復(fù)雜事件到達(dá)時(shí)，根據(jù)事件的讀寫類型的不同，分別執(zhí)行以下操作。

3.3.1 讀事件

當(dāng)?shù)竭_(dá)的事件是讀事件時(shí)，則判斷該事件的原始上界Iub是否小于低水標(biāo)記lwm。如果Iub大于lwm，則將該讀事件加入到讀事件隊(duì)列SLock中，等到Iub小于lwm時(shí)，再執(zhí)行該事件。若Iub小于lwm，則繼續(xù)判斷在讀事件可能發(fā)生的這段時(shí)間內(nèi)是否有數(shù)據(jù)更新，即查看歷史版本，是否有寫事件在這段時(shí)間內(nèi)對(duì)數(shù)據(jù)庫(kù)進(jìn)行寫操作。如果歷史版本沒有在這個(gè)時(shí)間段內(nèi)更新，則直接讀取距該事件最近版本的數(shù)據(jù)庫(kù)中的數(shù)據(jù)；如果數(shù)據(jù)庫(kù)在這段時(shí)間內(nèi)發(fā)生數(shù)據(jù)更新，則根據(jù)歷史版本將讀事件中的時(shí)間段分組，將各個(gè)組的概率相加，選取概率和大的組，讓讀事件讀取該版本的數(shù)據(jù)庫(kù)中的數(shù)據(jù)。讀事件調(diào)度過程如算法1所示。

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

輸入：寫隊(duì)列XL，數(shù)據(jù)庫(kù)歷史版本History，系統(tǒng)時(shí)間t

輸出：更新數(shù)據(jù)庫(kù)和系統(tǒng)時(shí)間

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;

下面通過一個(gè)例子說明本文算法對(duì)讀事件的調(diào)度方法。

例2數(shù)據(jù)庫(kù)的歷史版本的時(shí)間標(biāo)簽為History(1, 3,5,8)，其中1、3、5、8分別代表著數(shù)據(jù)庫(kù)1、3、5、8時(shí)間點(diǎn)有數(shù)據(jù)更新，如圖2中三角標(biāo)記所注。讀事件A、B的時(shí)間戳及其概率分布如圖2所示。下面假設(shè)讀事件A、B在lwm為7時(shí)到達(dá)，A事件的Iub為6，小于lwm，則讀取數(shù)據(jù)庫(kù)中的歷史版本，發(fā)現(xiàn)在事件A可能執(zhí)行的時(shí)間段中，在3和5兩個(gè)時(shí)間點(diǎn)，數(shù)據(jù)庫(kù)都發(fā)生了數(shù)據(jù)更新，則將事件A的時(shí)間段以時(shí)間點(diǎn)3、5分開，分為3個(gè)時(shí)間段(2)、(3,4)、(5,6)，事件A讀取時(shí)間點(diǎn)3之前的版本的概率為0.1，讀取時(shí)間點(diǎn)3更新后的數(shù)據(jù)庫(kù)中數(shù)據(jù)的概率為0.2+0.4=0.6，讀取時(shí)間點(diǎn)5更新后的數(shù)據(jù)庫(kù)中數(shù)據(jù)的概率為0.2+0.1=0.3。之后比較事件在這3個(gè)時(shí)間段內(nèi)執(zhí)行的概率，得出事件A在(3,4)這個(gè)時(shí)間段執(zhí)行的概率最高，因此事件A讀取的數(shù)據(jù)庫(kù)版本為時(shí)間點(diǎn)3時(shí)數(shù)據(jù)庫(kù)。對(duì)于事件B來說，由于B的Iub大于lwm，也就是說可能有比讀事件B更早執(zhí)行的寫事件還未發(fā)生，因此將B事件加入到讀事件的隊(duì)列中，當(dāng)lwm更新到比B事件的Iub大之后，再對(duì)B事件進(jìn)行調(diào)度。雖然這樣的調(diào)度方法可能會(huì)影響事件反饋的實(shí)時(shí)性，但是這樣能使事務(wù)執(zhí)行的正確率大大提升，并且在反饋的實(shí)時(shí)性方面，延遲的造成主要是由于時(shí)間的不確定，而時(shí)間的不確定是由觸發(fā)器、網(wǎng)絡(luò)傳輸?shù)扔布栴}引起的，因此這樣微小的延遲在時(shí)間不確定的情況下是可以接受的。

Fig.2 Instances of reading event圖2 讀事件實(shí)例

3.3.2 寫操作

當(dāng)?shù)竭_(dá)事件為寫事件的時(shí)候，首先將寫事件加入到寫隊(duì)列中，寫隊(duì)列為XLock={xl1.t1,xl2.t2,…,xln.tn}，然后更新Fts（first transaction），F(xiàn)ts表示當(dāng)前寫隊(duì)列所有事件中Ilb最小的寫事件，接著更新lwm，lwm的值為當(dāng)前寫隊(duì)列所有事件中Ilb最小的值，也就是Fts的之后，遍歷寫隊(duì)列XLock，找出事件的Ilb

剪枝算法對(duì)于一個(gè)可能的執(zhí)行順序m(E(1),E(2),…,E(n)),E(i)是滿足該執(zhí)行順序的一個(gè)事件，其中i代表該事件在執(zhí)行順序中的位置，對(duì)該順序進(jìn)行兩次遍歷。

第一次遍歷，確定有效下界。

對(duì)于某個(gè)執(zhí)行順序，若E(i)為執(zhí)行順序中第一個(gè)事件，即i=1，則E(i).Vlb=E(i).Ilb；

若E(i)不是該順序中第一個(gè)事件，則E(i).Vlb= max(E(i-1).Vlb+1,E(i).Ilb)。

這樣，經(jīng)過第一次遍歷之后，會(huì)確定每一個(gè)事件的有效下界Vlb。

第二次遍歷，確定有效上界。

對(duì)于某個(gè)執(zhí)行順序，若E(i)為該順序中最后一個(gè)事件，即i=n，則E(i).Vub=E(i).Iub；

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

如果某個(gè)事件的Vub小于該事件的Vlb，那么該執(zhí)行順序不可能發(fā)生，因此該順序的概率為0；如果所有事件的Vub都大于等于該事件的Vlb，則通過概率計(jì)算，得出該執(zhí)行順序的執(zhí)行概率。計(jì)算出某個(gè)順序的執(zhí)行概率后，更新備選事件隊(duì)列buffer中事件率先執(zhí)行的概率，將這個(gè)執(zhí)行順序的概率加到該執(zhí)行順序第一個(gè)事件的率先執(zhí)行概率中。剪枝過程如算法2所示。

算法2CutTrans（Transaction[]seq）

輸入：待剪枝的事件順序

輸出：seq剪枝后的結(jié)果是否可行

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；

在對(duì)buffer中所有可能的執(zhí)行順序都剪枝并計(jì)算概率后，找出buffer的所有寫事件中率先執(zhí)行概率最大的寫事件，將其設(shè)置為下一個(gè)執(zhí)行的寫事件Nts（next transaction）。當(dāng)數(shù)據(jù)庫(kù)中沒有寫鎖限制時(shí)，從寫隊(duì)列中調(diào)度執(zhí)行Nts，同時(shí)更新數(shù)據(jù)庫(kù)的歷史版本History，記錄更新事件，用以讀事件的調(diào)度。接著將該事件從寫隊(duì)列中釋放，然后用以上方法更新lwm、Fts和Nts。

例3如圖3所示，事件A、事件B、事件C和事件D的執(zhí)行時(shí)間點(diǎn)及其概率分布，通過每個(gè)事件的時(shí)間點(diǎn)，可以得出事件A.Ilb=2,A.Iub=6；同理可以得出，B.Ilb=1,B.Iub=5;C.Ilb=4,C.Iub=8。當(dāng)3個(gè)事件都在寫事件隊(duì)列時(shí)，首先找到寫隊(duì)列中Ilb最小的寫事件為事件B，則對(duì)Fts和lwm賦值，令Fts=B,lwm=B.Iub=1。之后遍歷整個(gè)隊(duì)列，發(fā)現(xiàn)A.Ilb=2<5=B.Iub,B.Ilb= 1<5=B.Iub,C.Ilb=4<5=B.Iub，則將事件A、事件B和事件C加入到buffer中，得到6種可能的執(zhí)行順序分別為ABC、ACB、BCA、BAC、CAB和CBA。接著對(duì)這6種可能的執(zhí)行順序進(jìn)行剪枝操作并計(jì)算概率，每種順序的剪枝處理和概率計(jì)算的結(jié)果如下：

（1）ABC順序。A.Vlb=2,A.Vub=4,B.Vlb=3,B.Vub=5,C.Vlb=4,C.Vub=8，每一個(gè)事件的Vub都不小于該事件的Vlb，因此該順序是有可能發(fā)生的，發(fā)生的概率P(ABC)=0.526。

（2）ACB順序。A.Vlb=2.A.Vub=3,B.Vlb=5,B.Vub=5，C.Vlb=4，C.Vub=4，每一個(gè)事件的Vub都不小于該事件的Vlb，因此該順序是有可能發(fā)生的，發(fā)生的概率P(ACB)=0.051。

（3）BCA順序。A.Vlb=5,A.Vub=6,B.Vlb=1,B.Vub=4,C.Vlb=4,C.Vub=5，每一個(gè)事件的Vub都不小于該事件的Vlb，因此該順序是有可能發(fā)生的，發(fā)生的概率P(BCA)=0.015。

（4）BAC順序。A.Vlb=2,A.Vub=6,B.Vlb=1，B.Vub=5,C.Vlb=4,C.Vub=8，每一個(gè)事件的Vub都不小于該事件的Vlb，因此該順序是有可能發(fā)生的，發(fā)生的概率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，因此該順序不可能發(fā)生，即該順序發(fā)生的概率P(CAB)=0。

（6）CBA順序。A.Vlb=6,A.Vub=6,B.Vlb=5,B.Vub=5,C.Vlb=4,C.Vub=4，每一個(gè)事件的Vub都不小于該事件的Vlb，因此該順序是有可能發(fā)生的，發(fā)生的概率P(CBA)=0.003。

Fig.3 Instances of writing event圖3 寫事件實(shí)例

得出每個(gè)順序的執(zhí)行概率后，計(jì)算每個(gè)事件的率先執(zhí)行概率，事件A率先執(zhí)行的概率為Pa=P(ABC)+P(ACB)=0.577；事件B率先執(zhí)行的概率為Pb=P(BAC)+P(BCA)=0.162；事件C率先執(zhí)行的概率為Pc=P(CAB)+P(CBA)=0.003。比較3個(gè)事件的率先執(zhí)行概率，有Pb>Pa>Pc，也就是說事件B率先執(zhí)行的概率最大，因此將下一個(gè)執(zhí)行事件Nts設(shè)置為事件B，等到數(shù)據(jù)庫(kù)中沒有寫鎖限制時(shí)，調(diào)度Nts事件，從寫隊(duì)列中釋放Nts事件，并根據(jù)Nts事件的具體內(nèi)容對(duì)數(shù)據(jù)庫(kù)進(jìn)行上鎖，等到Nts事件的操作完成后，釋放對(duì)數(shù)據(jù)庫(kù)的寫鎖，更新數(shù)據(jù)庫(kù)的歷史版本History，并重新從寫隊(duì)列中調(diào)度Nts事件。在釋放Nts事件，或當(dāng)有新的寫事件加入時(shí)，更新寫隊(duì)列中的Nts事件、Fts事件以及l(fā)wm的值。

3.4 算法分析

本文算法注重時(shí)間戳不確定事件中每個(gè)時(shí)間點(diǎn)及其概率，無論時(shí)間點(diǎn)與概率怎樣分布，都將二者結(jié)合起來，再對(duì)事件群進(jìn)行處理，從理論上能夠更好地利用每一個(gè)時(shí)間點(diǎn)的概率，獲得更準(zhǔn)確的調(diào)度順序，提高調(diào)度算法的準(zhǔn)確率。

對(duì)于時(shí)間戳不確定的事件，在一定時(shí)間段內(nèi)，可能有多種事件發(fā)生順序，本文算法首先將同一時(shí)間段內(nèi)可能的事件發(fā)生順序全部列舉出來，并依次計(jì)算出每種順序可能發(fā)生的概率。在此過程中，通過對(duì)時(shí)間段剪枝的方法，簡(jiǎn)化概率的計(jì)算。剪枝操作可以減去該順序中每個(gè)事件不可能發(fā)生的時(shí)間點(diǎn)，從而將長(zhǎng)時(shí)間段減為短時(shí)間段。雖然有時(shí)對(duì)于某些順序，剪枝操作是多余的，例如例3中對(duì)于發(fā)生順序?yàn)锽AC的情況，剪枝操作沒有使任何一個(gè)事件的時(shí)間段變短，但是對(duì)于其他順序來說，剪枝操作能夠很有效地剪短時(shí)間段，方便概率計(jì)算。尤其是對(duì)于不可能的發(fā)生順序來說，例如例3中的CAB順序，剪枝操作可以在不用計(jì)算概率的情況下，就能得知該順序的發(fā)生概率為0。因此，對(duì)于全體事件可能的發(fā)生順序來說，對(duì)每個(gè)事件順序都進(jìn)行剪枝操作，可以有效地剪短時(shí)間段，為概率的計(jì)算提供很大幫助。

在得到每種順序發(fā)生的概率后，計(jì)算出每個(gè)事件率先執(zhí)行的概率。某個(gè)事件率先執(zhí)行的概率等于在全部可能的執(zhí)行順序中第一個(gè)發(fā)生事件為該事件的執(zhí)行順序的發(fā)生概率的和。事件率先執(zhí)行的概率越高，代表在這一時(shí)間段內(nèi)，該事件的應(yīng)用時(shí)間最早的概率越高，因此應(yīng)選取概率最高的事件作為下一個(gè)執(zhí)行事件進(jìn)行調(diào)度。

4 實(shí)驗(yàn)

參照相關(guān)文獻(xiàn)[13,15]的實(shí)驗(yàn)方法，本文實(shí)現(xiàn)了一個(gè)事件流產(chǎn)生器，對(duì)時(shí)間戳不確定事件的調(diào)度準(zhǔn)確率進(jìn)行測(cè)試和比較。本文另外提出了兩種滿足時(shí)間戳不確定事件的LWM基本改進(jìn)調(diào)度算法，將它們與本文提出的利用剪枝算法的LWM調(diào)度算法進(jìn)行了對(duì)比。

基本改進(jìn)算法中，一種是平均時(shí)間算法，即取得每個(gè)時(shí)間段的平均時(shí)間點(diǎn)后，結(jié)合LWM算法，當(dāng)新的事件到來時(shí)，計(jì)算其平均時(shí)間點(diǎn)，此時(shí)低水標(biāo)記lwm代表數(shù)據(jù)庫(kù)中所有寫操作中最小值，當(dāng)一個(gè)新的寫操作到來，或者一個(gè)舊的寫操作釋放時(shí)，lwm會(huì)隨之更新。另一種是初始時(shí)間算法，即選取時(shí)間戳不確定的事件中的Ilb作為調(diào)度時(shí)間點(diǎn)，使用LWM算法對(duì)時(shí)間戳不確定的事件進(jìn)行調(diào)度，將未被執(zhí)行的事件按照讀寫類型不同，分別加入到讀隊(duì)列和寫隊(duì)列中，此時(shí)lwm設(shè)置為數(shù)據(jù)庫(kù)中所有寫操作Ilb的最小值，當(dāng)一個(gè)新的寫操作到來，或者一個(gè)舊的寫操作釋放時(shí)，lwm會(huì)隨之更新。為對(duì)比3種算法的性能，設(shè)計(jì)了4個(gè)實(shí)驗(yàn)。

實(shí)驗(yàn)1在事件量不同的情況下，比較3種算法調(diào)度事件的準(zhǔn)確率。圖4為3種算法調(diào)度事件量為100、300和600時(shí)的準(zhǔn)確率。

Fig.4 Event amount vs.accuracy圖4 事件數(shù)量對(duì)準(zhǔn)確率的影響

實(shí)驗(yàn)1中事件的不確定時(shí)間段長(zhǎng)度不變，時(shí)間段中時(shí)間點(diǎn)的概率分布方式隨機(jī)分布，并且事件的讀寫比例為5∶5，只改變事件量，從而分析不同事件量對(duì)3種算法的影響。從圖4中可以看出，事件量較小時(shí)，3種算法調(diào)度的準(zhǔn)確性相對(duì)較高，隨著事件量的增加，事件調(diào)度的準(zhǔn)確性稍有下降，但基本能趨于固定值，因此算法的準(zhǔn)確性可以根據(jù)處理大量事件時(shí)的準(zhǔn)確率來衡量。同時(shí)可以發(fā)現(xiàn)，3種算法中，運(yùn)用時(shí)間戳剪枝的方法與LWM結(jié)合，能更好地保證調(diào)度的準(zhǔn)確性，這一結(jié)果與理論中得到的結(jié)論相同。通過實(shí)驗(yàn)可以看出，事件量較大時(shí)，時(shí)間戳剪枝結(jié)合LWM的算法能夠保證事件調(diào)度的準(zhǔn)確率在86%左右。

實(shí)驗(yàn)2在時(shí)間段長(zhǎng)度不同時(shí)，比較3種算法調(diào)度事件的準(zhǔn)確率。圖5為在時(shí)間段長(zhǎng)度為3、5和7以及時(shí)間段長(zhǎng)度不固定時(shí)，3種算法調(diào)度的準(zhǔn)確率。

Fig.5 Interval length vs.accuracy圖5 時(shí)間段長(zhǎng)度對(duì)準(zhǔn)確率的影響

實(shí)驗(yàn)2中的事件量為600，時(shí)間段中時(shí)間點(diǎn)的概率分布方式為隨機(jī)分布，并且事件的讀寫比例為5∶5，只改變事件的時(shí)間段長(zhǎng)度，用來分析不同的時(shí)間段長(zhǎng)度對(duì)3種算法的影響。從圖5中可以看出，當(dāng)事件數(shù)量達(dá)到一定程度時(shí)，時(shí)間段的長(zhǎng)度越短，調(diào)度的準(zhǔn)確率越高。這是顯而易見的，當(dāng)時(shí)間段長(zhǎng)度為1時(shí)，這3種算法就是經(jīng)典的低水標(biāo)記算法，因此正確率最高，隨著時(shí)間段長(zhǎng)度增加，事件執(zhí)行的準(zhǔn)確時(shí)間也就越難確定，調(diào)度的準(zhǔn)確率也會(huì)隨之下降。從整體來看，對(duì)于不同長(zhǎng)度的時(shí)間段，時(shí)間戳剪枝結(jié)合LWM的算法的準(zhǔn)確性最好。

實(shí)驗(yàn)3在時(shí)間概率分布類型不同的情況下，比較3種算法調(diào)度事件的準(zhǔn)確率。圖6為面對(duì)時(shí)間分布類型為正態(tài)分布、平均分布和隨機(jī)分布的事件時(shí)，3種算法調(diào)度的準(zhǔn)確率。

實(shí)驗(yàn)3中的事件量為600，時(shí)間段的長(zhǎng)度固定為5，并且事件的讀寫比例為5∶5，只改變事件時(shí)間點(diǎn)的概率分布類型，用來分析不同的事件概率分布類型對(duì)3種算法的影響。從圖6中可以看出，取平均時(shí)間為調(diào)度時(shí)間點(diǎn)結(jié)合LWM算法和取原始上界為調(diào)度時(shí)間點(diǎn)結(jié)合LWM算法在處理正態(tài)分布和平均分布時(shí)，調(diào)度的準(zhǔn)確度是一樣的。這是由于無論是正態(tài)分布還是隨機(jī)分布，取平均時(shí)間與取原始上界不會(huì)導(dǎo)致事件的順序發(fā)生變化，從而對(duì)事件調(diào)度的結(jié)果也一樣。同時(shí)可以看出，與其他兩種算法相比，時(shí)間戳剪枝結(jié)合LWM算法對(duì)于各種概率分布類型的事件，都能有較高的準(zhǔn)確性。

Fig.6 Probability distribution vs.accuracy圖6 概率分布對(duì)準(zhǔn)確率的影響

實(shí)驗(yàn)4在事件讀寫比例不同時(shí)，比較3種算法調(diào)度事件的正確率。圖7為事件讀寫比例分別為3∶7、5∶5、7∶3時(shí)，3種算法調(diào)度的準(zhǔn)確率。

Fig.7 Rate of reading and writing vs.accuracy圖7 讀寫事件比例對(duì)準(zhǔn)確率的影響

實(shí)驗(yàn)4中的事件量為600，時(shí)間段的長(zhǎng)度固定為5，并且事件的時(shí)間點(diǎn)概率分布類型為隨機(jī)分布，只改變事件的讀寫比例，用來分析不同的讀寫比例對(duì)3種算法的影響。從圖7中可以得出，隨著讀寫比例的增加，3種算法的執(zhí)行準(zhǔn)確率都會(huì)隨之提高，這從理論上是很容易解釋的。本文算法對(duì)讀事件的處理采用數(shù)據(jù)庫(kù)多版本控制的方法，因此一個(gè)讀事件是否能被正確調(diào)度取決于該讀事件讀到的數(shù)據(jù)庫(kù)版本。寫事件數(shù)量越少，數(shù)據(jù)庫(kù)的歷史版本就越少，因此讀事件讀到正確版本的可能性就越高。同時(shí)可以看出，與其他兩種算法相比，時(shí)間戳剪枝結(jié)合LWM算法對(duì)于各種讀寫比例，都能有較高的準(zhǔn)確性。

通過以上4組實(shí)驗(yàn)，可以總結(jié)出時(shí)間戳不確定事件的各種因素對(duì)調(diào)度算法準(zhǔn)確性的影響。對(duì)本文出現(xiàn)的時(shí)間不確定調(diào)度算法的準(zhǔn)確率影響較大的因素有兩個(gè)：不確定時(shí)間段的長(zhǎng)度和事件的讀寫比例。不確定時(shí)間段越短，讀事件在所有事件中所占的比例越高，算法的準(zhǔn)確性就越好。事件量和時(shí)間點(diǎn)概率分布類型對(duì)算法的準(zhǔn)確度影響不大。

同時(shí)，通過比較3種調(diào)度算法可以看出，在各種條件下，相對(duì)于取原始上界為調(diào)度時(shí)間點(diǎn)結(jié)合LWM算法和取平均時(shí)間為調(diào)度時(shí)間點(diǎn)結(jié)合LWM算法，時(shí)間戳剪枝結(jié)合LWM算法都能有更高的準(zhǔn)確性，因此時(shí)間戳剪枝結(jié)合LWM算法是一個(gè)更好的時(shí)間戳不確定的復(fù)雜事件調(diào)度算法。

5 結(jié)束語(yǔ)

事件是CPS中的重要元素，具有時(shí)間戳不確定的特點(diǎn)，本文結(jié)合時(shí)間戳不確定的事件檢測(cè)和優(yōu)化算法及支持確定時(shí)間戳的事件調(diào)度算法LWM提出了滿足CPS中時(shí)間戳不確定的事件調(diào)度算法，實(shí)驗(yàn)證明本文算法可以達(dá)到較高的調(diào)度準(zhǔn)確率。

[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.

附中文參考文獻(xiàn)：

[6]劉克中,莊洋,周少龍,等.基于節(jié)點(diǎn)感知信任度模型的無線傳感網(wǎng)絡(luò)事件檢測(cè)方法[J].北京郵電大學(xué)學(xué)報(bào),2015, 38(1):61-66.

李芳芳（1977—），女，黑龍江哈爾濱人，2009年于東北大學(xué)獲得博士學(xué)位，現(xiàn)為東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院講師，CCF會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)，CPS數(shù)據(jù)管理等。

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—），男，內(nèi)蒙古包頭人，東北大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)系統(tǒng)，機(jī)器學(xué)習(xí)等。

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年于東北大學(xué)計(jì)算機(jī)專業(yè)獲得碩士學(xué)位，1996年于日本九州大學(xué)獲得計(jì)算機(jī)工學(xué)博士學(xué)位，現(xiàn)為東北大學(xué)教授、博士生導(dǎo)師，中國(guó)計(jì)算機(jī)學(xué)會(huì)理事，美國(guó)ACM和IEEE會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)系統(tǒng)，分布式系統(tǒng)，并行計(jì)算，云計(jì)算等。

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(國(guó)家自然科學(xué)基金);the Fundamental Research Funds for the Central Universities of China under Grant No.140404013(中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金).

Received 2016-06,Accepted 2016-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-08-15,http://www.cnki.net/kcms/detail/11.5602.TP.20160815.1659.006.html