張 晶, 陳 垚, 范洪博，孫 俊

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，昆明650500)

基于信息物理融合系統(tǒng)執(zhí)行器輸出事件的價(jià)值評價(jià)調(diào)度策略

張 晶, 陳 垚, 范洪博*，孫 俊

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，昆明650500)

(*通信作者電子郵箱414356764@qq.com)

對于信息物理融合系統(tǒng)狀態(tài)轉(zhuǎn)移實(shí)時(shí)過程會影響系統(tǒng)性能及其正確性的問題，針對執(zhí)行器的輸出事件驅(qū)動(dòng)系統(tǒng)狀態(tài)轉(zhuǎn)移過程，提出一種基于信息熵與數(shù)據(jù)質(zhì)量的執(zhí)行器輸出事件的價(jià)值評價(jià)調(diào)度策略——VE-IE&QoD。首先,以超致密時(shí)間模型表達(dá)事件的實(shí)時(shí)性，定義輸出事件的自信息量、執(zhí)行器的信息熵及其數(shù)據(jù)質(zhì)量分別為價(jià)值評價(jià)的函數(shù)指標(biāo);然后,對執(zhí)行器執(zhí)行任務(wù)的過程進(jìn)行價(jià)值評價(jià)，并考慮適當(dāng)增加加權(quán)系數(shù);最后,利用Ptolemy Ⅱ平臺建立包含價(jià)值評價(jià)調(diào)度策略、傳統(tǒng)最早截止時(shí)間優(yōu)先(EDF)調(diào)度算法以及考慮信息熵的IE*調(diào)度策略的離散事件模型。分析不同算法模型的運(yùn)行情況，對比價(jià)值評價(jià)的變化以及執(zhí)行時(shí)間，實(shí)驗(yàn)結(jié)果表明,價(jià)值評價(jià)調(diào)度策略可降低系統(tǒng)平均執(zhí)行時(shí)間，提高內(nèi)存使用效率與任務(wù)價(jià)值評價(jià)。該策略能在一定程度上提高系統(tǒng)性能及其正確性。

信息物理融合系統(tǒng)；執(zhí)行器；事件；信息熵；數(shù)據(jù)質(zhì)量；價(jià)值評價(jià)

0 引言

具有“深度嵌入、泛在融合、智能感知和交互協(xié)同”等特點(diǎn)的信息物理融合系統(tǒng)(Cyber-Physical System, CPS)[1]高度融合一系列物理進(jìn)程、嵌入式計(jì)算及網(wǎng)絡(luò)通信，系統(tǒng)通過網(wǎng)絡(luò)節(jié)點(diǎn)使軟件進(jìn)程與物理實(shí)體聯(lián)系，應(yīng)用網(wǎng)絡(luò)交互技術(shù)使各節(jié)點(diǎn)連續(xù)物理系統(tǒng)的物理進(jìn)程通過閉環(huán)反饋循環(huán)不斷與離散計(jì)算系統(tǒng)的計(jì)算進(jìn)程實(shí)時(shí)交互，同時(shí)，物理實(shí)體也利用系統(tǒng)硬件組件和網(wǎng)絡(luò)節(jié)點(diǎn)感知、傳輸周邊環(huán)境信息[2]。CPS系統(tǒng)能通過自身軟硬件結(jié)構(gòu)、裝置分析物理動(dòng)態(tài)變化，控制物理系統(tǒng)，執(zhí)行誤差修正等功能，該系統(tǒng)涵蓋計(jì)算機(jī)網(wǎng)絡(luò)、軟件工程、控制工程、傳感器、電子學(xué)等多領(lǐng)域?qū)W科，整個(gè)系統(tǒng)由大量傳感器、物理硬件、軟件系統(tǒng)及通信網(wǎng)絡(luò)節(jié)點(diǎn)構(gòu)成[3]。

為保證系統(tǒng)計(jì)算進(jìn)程與物理實(shí)體行為深度交互，考慮軟件與硬件相互作用的時(shí)間度量和表示的一致性，通過微分不變式計(jì)算連續(xù)時(shí)鐘約束的收斂函數(shù)，使計(jì)算結(jié)果趨近離散模型的某一不動(dòng)點(diǎn)，該點(diǎn)為嚴(yán)格收斂的時(shí)間信號函數(shù)的唯一不動(dòng)點(diǎn)，函數(shù)不動(dòng)點(diǎn)能確認(rèn)所對應(yīng)的系統(tǒng)實(shí)時(shí)交互行為的正確性與唯一性。采用超致密時(shí)間模型(Super Dense Time model, SDT)[4]拓展執(zhí)行器輸出事件驅(qū)動(dòng)系統(tǒng)狀態(tài)轉(zhuǎn)移過程，以SDT表達(dá)事件實(shí)時(shí)性，將任務(wù)執(zhí)行順序用事件的時(shí)間軌跡描述，這樣，在控制物理系統(tǒng)時(shí)能提供更嚴(yán)格的時(shí)間模型。

事件是一組計(jì)算變量、一條指令集合或輸入/輸出信號的表達(dá)。一個(gè)事件由執(zhí)行器輸出，事件本身含有的信息量由自身的不確定性決定，而一組輸出事件的平均信息量表示執(zhí)行器的平均不確定性，即執(zhí)行器的信息熵(Information Entropy, IE)[5-6]。對比事件執(zhí)行任務(wù)的執(zhí)行周期和可執(zhí)行時(shí)間構(gòu)成執(zhí)行器的數(shù)據(jù)服務(wù)質(zhì)量(Quality of Data, QoD)[7-8]表達(dá)執(zhí)行器驅(qū)動(dòng)系統(tǒng)狀態(tài)轉(zhuǎn)移的時(shí)鐘約束條件。

本文描述了CPS的基本系統(tǒng)狀態(tài)轉(zhuǎn)移過程，定義了計(jì)算過程的時(shí)鐘約束，執(zhí)行器輸出事件本身的自信息量、執(zhí)行器的信息熵及其數(shù)據(jù)質(zhì)量，通過信息熵與數(shù)據(jù)質(zhì)量構(gòu)成的評價(jià)方程對執(zhí)行器執(zhí)行的任務(wù)進(jìn)行價(jià)值評價(jià)，將評價(jià)結(jié)果反饋至執(zhí)行器即可控制下一周期的輸出事件更有效地驅(qū)動(dòng)系統(tǒng)狀態(tài)轉(zhuǎn)移。

CPS系統(tǒng)中執(zhí)行器輸出事件執(zhí)行任務(wù)所對應(yīng)的時(shí)間序列對系統(tǒng)功能能否正常實(shí)現(xiàn)尤其重要，由此，基于執(zhí)行器的信息熵和數(shù)據(jù)質(zhì)量能在很大程度上影響系統(tǒng)性能和正確性。UC Berkeley的Ptolemy Ⅱ平臺[9]可對包含時(shí)間和行為類型屬性的組件交互過程進(jìn)行驗(yàn)證，該平臺支持對實(shí)時(shí)嵌入式異構(gòu)系統(tǒng)執(zhí)行分層設(shè)計(jì)[10]，本文通過在Ptolemy Ⅱ的離散事件模型(Discrete-Event Modeling, DEM)[11-13]上加入基于信息熵與數(shù)據(jù)質(zhì)量的執(zhí)行器輸出事件的價(jià)值評價(jià)策略——VE-IE&QoD(Value Evaluation- Information Entropy and Quality of Data),驗(yàn)證基于此價(jià)值評價(jià)策略能提高系統(tǒng)性能與正確性。

1 系統(tǒng)狀態(tài)轉(zhuǎn)移模型

基本的CPS系統(tǒng)一般由物理實(shí)體、計(jì)算平臺和網(wǎng)絡(luò)通信三個(gè)部分組成,如圖1所示，物理實(shí)體通過傳感器感知、收集環(huán)境信息，信息數(shù)據(jù)由網(wǎng)絡(luò)節(jié)點(diǎn)傳輸至計(jì)算平臺，經(jīng)過嵌入式計(jì)算及數(shù)據(jù)融合后將控制信息、反饋信息或決策信息以命令代碼的形式輸出至驅(qū)動(dòng)器，進(jìn)而控制物理設(shè)備。

圖1 基本的CPS系統(tǒng)結(jié)構(gòu)

1.1 事件驅(qū)動(dòng)系統(tǒng)狀態(tài)轉(zhuǎn)移

CPS基本模型可以看作一種面向執(zhí)行器(Actor)的模型，所謂執(zhí)行器就是通過端口執(zhí)行并行處理、分享數(shù)據(jù)的組件。執(zhí)行器并非簡單地按照執(zhí)行隊(duì)列驅(qū)動(dòng)系統(tǒng)狀態(tài)轉(zhuǎn)移，而是以一種輸入/輸出數(shù)據(jù)端口執(zhí)行信號通信交流的系統(tǒng)部件。

定義1 設(shè)在六元組〈A,S,I,Q,T,E〉中，?ai∈A表示執(zhí)行器釋放離散隨機(jī)變量ai，以連續(xù)時(shí)鐘約束T為指定周期，ai驅(qū)動(dòng)系統(tǒng)狀態(tài)si∈S進(jìn)行轉(zhuǎn)移任務(wù)，隨機(jī)變量ai攜帶信息標(biāo)簽ai(I,Q)。其中：I稱為自信息，表示ai本身所包含的信息量；Q稱為數(shù)據(jù)質(zhì)量，衡量ai能否有效控制系統(tǒng)狀態(tài)轉(zhuǎn)移。假設(shè)〈s,s′,a,I,Q,c〉∈E表示在隨機(jī)事件a的控制下，狀態(tài)由s→s′的轉(zhuǎn)移路徑，C為離散時(shí)鐘集，c:=0表示在s→s′過程中時(shí)鐘c重置為0，c∈C。如圖2所示，當(dāng)滿足時(shí)鐘約束條件c<3時(shí)，s′→s。

圖2 事件驅(qū)動(dòng)狀態(tài)轉(zhuǎn)移路徑模型

1.2 拓展?fàn)顟B(tài)轉(zhuǎn)移路徑

假設(shè)通過微分不變式計(jì)算連續(xù)時(shí)鐘約束T的收斂函數(shù)，使T趨于離散模型C的某一不動(dòng)點(diǎn)，保證在E中，(s→s′|a)能在時(shí)間度量和表示上與系統(tǒng)狀態(tài)和行為保持一致。

若離散時(shí)鐘集C以實(shí)數(shù)值表示，則一旦存在間隔釋放的事件ai與ai+1且lim[C(ai+1)-C(ai)]=0，所有離散時(shí)間值ti無法用任意小的固定常數(shù)的倍數(shù)表示。

定義2 考慮引用具有偏序性質(zhì)的超致密時(shí)間模型(SDT)[8]對E進(jìn)行拓展，則時(shí)間軌跡t→t′可以表示(s→s′|a)。

令SDT中，t→t′為時(shí)間序列(l,n)∈(C= R+×N)，其中l(wèi)∈R+表示步長，n∈N表示步數(shù)。若t→t′，則說明t′>t，即(l′,n′)>(l,n)，那么有l(wèi)′>l或(l′=l∨n′>n)。

定理1 實(shí)時(shí)狀態(tài)轉(zhuǎn)移〈A,S,I,Q,T,E〉中，當(dāng)且僅當(dāng)s(l,n)通過a[I(l,n),Q(l,n)]控制時(shí)，(s→s′|a)通過實(shí)時(shí)標(biāo)簽a(I,Q)驅(qū)動(dòng)執(zhí)行任務(wù)。

證明 由定義1與定義2可知，執(zhí)行器以離散時(shí)鐘集C為周期連續(xù)釋放離散隨機(jī)變量a(I,Q)，離散時(shí)間值ti∈C，若l為〈A,S,I,Q,T,E〉中時(shí)鐘集C的最小公倍數(shù)，對于ti在有限轉(zhuǎn)移次數(shù)nx內(nèi)有nl=ti，n≤nx。那么?ti∈C，?l∈R+，使(n-1)l≤ti≤nl無限接近ti。所以時(shí)間序列(l,n)可以無限接近地代替離散時(shí)間值ti作為(s→s′|a)的時(shí)鐘約束。

1.3 執(zhí)行器的價(jià)值評價(jià)

事件ai的自信息量I由ai的不確定性決定，認(rèn)為執(zhí)行器作為釋放離散隨機(jī)變量ai的信源，表征整個(gè)信源的不確定度需要由平均自信息量H決定。

定義3 設(shè)事件ai由執(zhí)行器輸出的概率為p(ai)，則I(ai)=-lb(p(ai))=lb(1/p(ai))。

I(ai)在定義域[0,1]內(nèi)是概率p(ai)的嚴(yán)格遞減函數(shù)，p(a1)I(a2)，說明事件發(fā)生的概率越小，其不確定性越大，a(I,Q)攜帶的自信息量越大。特別的，當(dāng)p(ai)=0時(shí)，I(ai)→∞；當(dāng)p(ai)=1時(shí)，I(ai)=0。

令隨機(jī)變量X的所有取值及其對應(yīng)的概率稱為概率空間：

假設(shè)系統(tǒng)是在無噪聲的情況下執(zhí)行任務(wù)的，則接收執(zhí)行器所收到的信息消除了發(fā)送執(zhí)行器所釋放的事件的不確定性，故發(fā)送執(zhí)行器的不確定度可由平均自信息量表示。

定義4 將平均自信息量H稱為執(zhí)行器釋放事件的信息熵，記H(A)。

定理2 信息熵H(A)有以下性質(zhì)：

1)H[p(a0),p(a1),…,p(ai)]=H[p(a1),p(a0),…,p(ai)]=…=H[p(ai),p(ai-1),…,p(a0)]。即H(A)各釋放的事件順序改變不影響執(zhí)行器總體信息熵值。

2)H[p(a)]=H[p(a0),p(a1),…,p(ai)]≥0。當(dāng)且僅當(dāng)執(zhí)行器為確定信源時(shí)，等號成立。

證明 由定義4可知，I(a)在定義域[0,1]內(nèi)是非負(fù)的，而H(A)是I(a)的數(shù)學(xué)期望，且a為離散隨機(jī)變量，故H(A)必為非負(fù)。

3)?a,b∈A,有：

即執(zhí)行器多釋放一個(gè)基本不會出現(xiàn)的小概率事件對信源的信息熵值不會產(chǎn)生改變。雖然事件b的自信息量很大，但信息熵是執(zhí)行器的平均自信息量，b的比重小至可以忽略不計(jì)。

4)H[p(a0),p(a1),…,p(ai)]≤H(1/i,1/i,…,1/i)=lb(i)。即當(dāng)各事件等概率釋放時(shí)，H(A)最大。

證明 設(shè)?bi∈A，若p(b)/p(a)=1時(shí)，有：

若p(a)=p(b)=1/n時(shí)，有：

5)在定義域[0,1]內(nèi)，H(A)的極大值為最大值。

故Δp(a)+(1-Δ)p(b)定義為新的概率分布。可以分析：

H[Δp(a)+(1-Δ)p(b)]>ΔH[p(a)]+(1-Δ)H[p(b)]

故H(A)在定義域內(nèi)為上凸函數(shù)，結(jié)合H(A)的極值性可知在定義域[0,1]內(nèi)，H(A)的極大值為最大值。

1.4 與事件有依賴關(guān)系的執(zhí)行器的信息冗余度

若執(zhí)行器輸出事件序列長度為i，則事件序列的數(shù)學(xué)模型為i維隨機(jī)變量序列A=a0,a1,…,ai，并且?aj∈A與?aj+1∈A存在依賴關(guān)系，即：

H[p(A)]=H[p(a0)p(a1)…p(ai)]=H[p(a0)]+H[p(a1)|p(a0)]+H[p(a2)|p(a0)p(a1)]+…+H[p(ai)|p(a0)p(a1)…p(ai-1)]

設(shè)事件驅(qū)動(dòng)系統(tǒng)狀態(tài)轉(zhuǎn)移概率p(St+1=sj+1|St=sj)是系統(tǒng)在t時(shí)刻處于sj狀態(tài)的情況下，在t+1時(shí)刻轉(zhuǎn)移至sj+1狀態(tài)的概率。

對于輸出事件有依賴關(guān)系的執(zhí)行器，所釋放的每個(gè)事件間的依賴關(guān)系也稱為相關(guān)性。由定義3、定義4可知，當(dāng)所有事件等概率輸出時(shí)，執(zhí)行器的信息熵最大，Hmax=lb(i)。即，只有一個(gè)輸出事件時(shí)，H(A)≈Hmax；當(dāng)事件序列越來越長時(shí)，每個(gè)事件的依賴關(guān)系越長，則執(zhí)行器輸出事件的平均信息量越小，導(dǎo)致執(zhí)行器的信息熵H(A)越小。對于有相同信息量的不同執(zhí)行器，依賴關(guān)系越大，輸出的信息量越少，執(zhí)行器內(nèi)剩余信息越多。

定義5 設(shè)執(zhí)行器的信息熵與具有相同事件集的最大熵的比值稱為信息輸出率μ：

μ=H(A)/Hmax

以信息冗余度χ表示執(zhí)行器內(nèi)剩余信息：

χ=1-μ=1-H(A)/Hmax=1-H(A)/lb(i)

為了使輸出事件更高效地驅(qū)動(dòng)系統(tǒng)狀態(tài)轉(zhuǎn)移，需要盡量降低執(zhí)行器的信息冗余度。

為了使系統(tǒng)得到確定的控制、反饋或決策信息，在避免執(zhí)行器的信息冗余度χ過高的同時(shí)，需要提高執(zhí)行器的數(shù)據(jù)質(zhì)量以保證輸出事件能提供有效的信號或指令。

1.5 事件的有效性與執(zhí)行時(shí)延

執(zhí)行器輸出的事件在一定執(zhí)行周期內(nèi)對系統(tǒng)才是有效的，在此周期前提前驅(qū)動(dòng)系統(tǒng)狀態(tài)轉(zhuǎn)移會非法搶占其他任務(wù)的資源，在截止期后執(zhí)行任務(wù)會產(chǎn)生無效增益，浪費(fèi)系統(tǒng)能耗，若事件執(zhí)行時(shí)間已超過執(zhí)行周期但還未到截止期，且下一任務(wù)還未開始，則此時(shí)該事件的有效性會隨著執(zhí)行時(shí)間逐漸降低，通過執(zhí)行時(shí)延可度量其有效性降低的過程。

定義6 設(shè)執(zhí)行器輸出事件的釋放時(shí)刻為tr，有效周期為TV，則事件a在時(shí)間t內(nèi)能有效驅(qū)動(dòng)系統(tǒng)狀態(tài)轉(zhuǎn)移的條件為：TV+tr≥t，其執(zhí)行時(shí)延表示為：

圖3 事件的執(zhí)行時(shí)延

1.6 數(shù)據(jù)質(zhì)量

定義7 用執(zhí)行時(shí)延與事件的有效周期量化執(zhí)行器的數(shù)據(jù)質(zhì)量，記為事件的價(jià)值量，表示為：

圖4 事件的數(shù)據(jù)質(zhì)量

2 VE-IE&QoD調(diào)度策略

本章結(jié)合執(zhí)行器的冗余度與事件的數(shù)據(jù)質(zhì)量，分析執(zhí)行器執(zhí)行任務(wù)的效益，描述一種基于價(jià)值評價(jià)的調(diào)度策略。

2.1 價(jià)值評價(jià)調(diào)度策略

定義7 對嵌入式控制狀態(tài)轉(zhuǎn)移的執(zhí)行器進(jìn)行價(jià)值評價(jià)，記為V。

VA(t)=α(k-n)H(A)+βQ(t)

其中：α，β為價(jià)值評價(jià)參量，α,β≥1；(k-n)是測得事件信息熵的時(shí)間信號周期。

在〈A,S,I,Q,T,E〉中，為保證最有效地執(zhí)行〈s,s′,a,I,Q,c〉∈E過程，需要控制執(zhí)行器以最高的價(jià)值評價(jià)調(diào)度事件，對時(shí)鐘約束要求更高的執(zhí)行器可適當(dāng)提高β參量，同樣，對信息量約束更高的執(zhí)行器可提高α參量。

假設(shè)需要執(zhí)行任務(wù)的執(zhí)行器為執(zhí)行器A與執(zhí)行器B，且A與B不能并行執(zhí)行，則所述的價(jià)值評價(jià)調(diào)度策略狀態(tài)轉(zhuǎn)移過程如圖5所示，面對不同情況的策略選擇如下。

圖5 價(jià)值評價(jià)調(diào)度策略下的狀態(tài)轉(zhuǎn)移過程

情況1 若[(d(A)-k(B))≥(k(A)-n(A))]∪[(d(B)-k(A))≥(k(B)-n(B))]。

策略1 不論先執(zhí)行A還是B，都能保證另一方能順序完成任務(wù)，為了節(jié)約執(zhí)行時(shí)間，對比A與B的數(shù)據(jù)質(zhì)量Q，選擇執(zhí)行周期k更短的一方優(yōu)先執(zhí)行。

情況2 若[(d(B)-k(A))<(k(B)-n(B))]∪[(d(A)-k(B))≥(k(A)-n(A))]。

策略2 明顯的，先執(zhí)行A后執(zhí)行B可以避免A與B的沖突，同時(shí)保證A與B都能在截止期前完成任務(wù)，若此時(shí)正在執(zhí)行B，系統(tǒng)可適當(dāng)增大A的β值，使A搶占處理器。

情況3 若[(d(B)-k(A))<(k(B)-n(B))]∪[(d(A)-k(B))<(k(A)-n(A))]。

策略3 執(zhí)行A還是B，都不能保證另一方能順利完成任務(wù)，則比較V(A)與V(B)中f1的大小，以執(zhí)行器的信息熵決定首先執(zhí)行A或B。

2.2 建立價(jià)值評價(jià)調(diào)度策略仿真模型

為了驗(yàn)證2.1節(jié)描述的調(diào)度能提高系統(tǒng)性能與正確性，本文利用開源嵌入式系統(tǒng)研究與開發(fā)平臺PtolemyⅡ建立離散事件模型(DEM)，在模型中加入基于CPS執(zhí)行器輸出事件價(jià)值評價(jià)調(diào)度策略，并與傳統(tǒng)常用的最早截止時(shí)間優(yōu)先(EarliestDeadlineFirst,EDF)算法、基于信息熵的IE*(InformationEntropy*)調(diào)度策略進(jìn)行比較。PtolemyⅡ平臺是由美國加州大學(xué)伯克利分校的EdwardAshfordLee教授領(lǐng)導(dǎo)的團(tuán)隊(duì)所開發(fā)的。

本文實(shí)驗(yàn)均在處理器為1.6GHz雙核IntelCorei5，RAM為8.00GB的MacBookAirPC上運(yùn)行，使用系統(tǒng)為macOSSierra，建模平臺版本為PtolemyⅡ10.0.1MacOSX版。

系統(tǒng)對比模型如圖6所示，服務(wù)器執(zhí)行器Serve的服務(wù)時(shí)間由隨機(jī)數(shù)發(fā)生器ColtExponential執(zhí)行器隨機(jī)產(chǎn)生，ColtExponential的參數(shù)λ為1.0/averageServiceTime，其中：參數(shù)averageServiceTime的初始值為0.1，隨機(jī)數(shù)種子seed為0L。模型利用參數(shù)Random模擬事件輸出概率，在有限狀態(tài)機(jī)(FiniteStateMachine,FSM)模型中，設(shè)狀態(tài)A為初始狀態(tài)，自身的狀態(tài)轉(zhuǎn)移為一種默認(rèn)的轉(zhuǎn)移模式(Adefaulttransition)，其中set∶Random=10。FSM模型輸入端為一種隨機(jī)事件發(fā)生器Bernoulli執(zhí)行器，該發(fā)生器在隨機(jī)時(shí)間產(chǎn)生觸發(fā)事件，其trueProbability=0.1。當(dāng)FSM模型端口被觸發(fā)時(shí)，狀態(tài)A轉(zhuǎn)移至狀態(tài)B，并且set∶Random=0，在B狀態(tài)下，自身的狀態(tài)轉(zhuǎn)移為一種historytransition，條件guard∶Random<10，并set∶Random=Random+x，其中：x為0～10的隨機(jī)數(shù)，當(dāng)guard∶Random≥10時(shí)，狀態(tài)B再轉(zhuǎn)移至狀態(tài)A，此時(shí)set∶Random=10。

圖6 離散事件對比模型

模型中，參數(shù)Random的初始值為10，執(zhí)行器輸出事件由組合執(zhí)行器EventGenerator產(chǎn)生，在組合執(zhí)行器內(nèi)，初始事件由PoissonClock執(zhí)行器在隨機(jī)時(shí)間觸發(fā)，該執(zhí)行器參數(shù)seed=0 L，meanTime=1.0/60.0，values={Random}，當(dāng)一個(gè)事件產(chǎn)生時(shí)，通過CurrentTime執(zhí)行器記錄釋放時(shí)間，并將Random值與釋放時(shí)間tr同時(shí)記錄在RecordAssembler執(zhí)行器內(nèi)。如圖6所示，Swich執(zhí)行器為執(zhí)行器輸出事件的價(jià)值評價(jià)調(diào)度策略，CompositeActor3與Swich組合成一個(gè)反饋模型，通過2.1節(jié)的調(diào)度策略判斷價(jià)值評價(jià)高的事件優(yōu)先執(zhí)行，而價(jià)值評價(jià)相對較低的返回CompositeActor執(zhí)行器重新等待執(zhí)行。Swich2執(zhí)行器與其前部相連接的執(zhí)行器構(gòu)成基于EDF算法的調(diào)度模型[14-16]，下方5個(gè)執(zhí)行器組合成基于IE*調(diào)度策略[17-18]的調(diào)度模型。整個(gè)對比模型的時(shí)間參量由DEDirector負(fù)責(zé)，本文模型使用的模型時(shí)間(ModelTime)統(tǒng)籌調(diào)度，故在DEDirector中，startTime=0.0，stopTime=100.0，而參數(shù)stopWhenQueueIsEmpty=ture，synchronizeToRealTime=false。

2.3 仿真結(jié)果分析

本文在PtolemyⅡ平臺上建立了2.2節(jié)所述的離散事件執(zhí)行器對比模型，模型內(nèi)隨機(jī)數(shù)執(zhí)行器的種子參數(shù)都為默認(rèn)值seed=0 L。模型中，Display執(zhí)行器可以顯示模型運(yùn)行情況，由EventGenerator產(chǎn)生的事件集通過VE-IE&QoD調(diào)度策略的Swich執(zhí)行器后，結(jié)果輸出在VE-IE&QoD的Display1執(zhí)行器，而作為對比，EDF結(jié)果輸出在Display2執(zhí)行器上，IE*結(jié)果輸出在Dispay3執(zhí)行器上，事件集從釋放到執(zhí)行完成，對系統(tǒng)產(chǎn)生的價(jià)值評價(jià)由TimedScope顯示，而事件集每個(gè)事件的執(zhí)行時(shí)間則由HistogramPlotter顯示。

對離散事件對比模型做30次重復(fù)實(shí)驗(yàn)，得到30組對比數(shù)據(jù)，隨機(jī)取出5(Ⅰ～Ⅴ)組，在同一條件下系統(tǒng)不同模型的運(yùn)行時(shí)間，內(nèi)存使用量及空閑內(nèi)存如表1所示。VE-IE&QoD(V)調(diào)度策略的平均執(zhí)行時(shí)間為690.6ms，EDF(E)算法的平均執(zhí)行時(shí)間為822.4ms，IE*調(diào)度策略的平均執(zhí)行時(shí)間為876.2ms，VE-IE&QoD調(diào)度策略的平均運(yùn)行速度比EDF算法提高了16.03%，比IE*(I)調(diào)度策略提高了21.18%；平均內(nèi)存使用效率上，VE-IE&QoD調(diào)度策略比EDF算法提高了17.91%，比IE*調(diào)度策略提高了22.79%。

表1 不同模型的運(yùn)行情況

PtolemyⅡ中TimedScope和HistogramPlotter顯示的數(shù)據(jù)生成曲線圖，在重復(fù)的30次實(shí)驗(yàn)中，隨機(jī)抽取2次的結(jié)果，其價(jià)值評價(jià)隨時(shí)間變化如圖7所示。由圖7可以明顯看出，VE-IE&QoD策略與EDF、IE*策略相比，價(jià)值評價(jià)略高，并且在執(zhí)行過程中，EDF與VE-IE&QoD調(diào)度策略的事件集價(jià)值評價(jià)穩(wěn)定上升，由確定的初始值增長至確定的終值，而IE*策略的事件集在執(zhí)行過程中系統(tǒng)顛簸現(xiàn)象嚴(yán)重，在指定的執(zhí)行過程內(nèi)，并不能確切地知道某個(gè)固定的價(jià)值量。

圖7 價(jià)值評價(jià)隨時(shí)間變化

相對應(yīng)的執(zhí)行器輸出事件的執(zhí)行時(shí)間如圖8所示，分析執(zhí)行器輸出事件集內(nèi)每個(gè)事件的執(zhí)行時(shí)間，由于事件value與釋放時(shí)間tr是在DEDirector控制下隨機(jī)產(chǎn)生，所以每個(gè)事件的具體執(zhí)行時(shí)間無法一致，但由圖8可知，執(zhí)行器在模型時(shí)間開始-結(jié)束為0.0～100.0ms內(nèi)，所輸出的事件集包含90個(gè)隨機(jī)事件，并且事件在用VE-IE&QoD策略時(shí)的執(zhí)行時(shí)間基本都比用EDF、IE*策略時(shí)低。由于EDF算法更加強(qiáng)調(diào)時(shí)序性，雖然IE*策略的價(jià)值評價(jià)偶爾高于EDF算法，但是在針對執(zhí)行時(shí)間這一比較上，EDF算法基本比IE*策略用時(shí)更少。

圖8 執(zhí)行器輸出事件的執(zhí)行時(shí)間

根據(jù)上述分析可以得出，在同一條件下隨機(jī)產(chǎn)生的事件通過由信息熵與數(shù)據(jù)質(zhì)量描述的一種基于CPS執(zhí)行器輸出事件的價(jià)值評價(jià)調(diào)度策略可以有效降低各個(gè)事件的執(zhí)行時(shí)間，提高整個(gè)事件集的平均運(yùn)行速度，在執(zhí)行過程中，系統(tǒng)價(jià)值評價(jià)穩(wěn)定上升，證明該調(diào)度策略能在一定程度上提高系統(tǒng)性能及其正確性。

3 結(jié)語

本文首先定義了計(jì)算過程的時(shí)鐘約束，執(zhí)行器輸出事件本身的自信息量、執(zhí)行器的信息熵及其數(shù)據(jù)質(zhì)量，然后基于CPS的基本系統(tǒng)狀態(tài)轉(zhuǎn)移過程，通過信息熵與數(shù)據(jù)質(zhì)量描述一種評價(jià)方程對執(zhí)行器執(zhí)行的任務(wù)進(jìn)行價(jià)值評價(jià)，最后利用PtolemyⅡ平臺可對包含時(shí)間和行為類型屬性的組件交互過程進(jìn)行仿真驗(yàn)證。在PtolemyⅡ的離散事件模型上加入由信息熵與數(shù)據(jù)質(zhì)量的執(zhí)行器輸出事件的VE-IE&QoD調(diào)度策略，利用執(zhí)行器模擬輸出事件的調(diào)度策略，組合反饋模型，實(shí)現(xiàn)模型對調(diào)度策略的應(yīng)用，通過建立仿真模型，將VE-IE&QoD調(diào)度策略與傳統(tǒng)EDF調(diào)度算法、基于信息熵的IE*調(diào)度策略進(jìn)行比較。仿真結(jié)果表明，VE-IE&QoD調(diào)度策略的平均運(yùn)行速度比EDF算法提高了16.03%，比IE*調(diào)度策略提高了21.18%；平均內(nèi)存使用效率上，VE-IE&QoD調(diào)度策略比EDF算法提高了17.91%，比IE*調(diào)度策略提高了22.79%，并且VE-IE&QoD策略的價(jià)值評價(jià)略高。本文所述建模方法與執(zhí)行過程略為繁瑣，今后可將離散事件模型系統(tǒng)調(diào)度性問題簡化為有限狀態(tài)機(jī)的可達(dá)性問題進(jìn)行分析，這樣可提高系統(tǒng)分析效率。

)

[1] 李仁發(fā),謝勇,李蕊,等.信息-物理融合系統(tǒng)若干關(guān)鍵問題綜述[J].計(jì)算機(jī)研究與發(fā)展,2012,49(6):1149-1161.(LIRF,XIEY,LIR,etal.Surveyofcyber-physicalsystems[J].JournalofComputerResearchandDevelopment, 2012, 49(6): 1149-1161.)

[2]LEEEA.Computingfoundationsandpracticeforcyber-physicalsystem[R].Berkeley,CA:UniversityofCalifornia, 2007.

[3]AKKAYAI,DERLERP,EMOTOS,etal.Systemsengineeringforindustrialcyber-physicalsystemsusingaspects[J].ProceedingsoftheIEEE, 2016, 104(5): 997-1012.

[4]ALURR,DILLDL.Atheoryoftimedautomata[J].TheoreticalComputerScience, 1994,126(2): 183-235

[5] 趙興旺,梁吉業(yè).一種基于信息熵的混合數(shù)據(jù)屬性加權(quán)聚類算法[J].計(jì)算機(jī)研究與發(fā)展,2016,53(5):1018-1028.(ZHAOXW,LIANGJY.Anattributeweightedclusteringalgorithmformixeddatabasedoninformationentropy[J].JournalofComputerResearchandDevelopment, 2016, 53(5): 1018-1028)

[6] 劉江冬，梁剛，馮程，等.基于信息熵和時(shí)效性的協(xié)同過濾推薦[J].計(jì)算機(jī)應(yīng)用,2016,36(9):2531-2534.(LIUJD,LIANGG,FENGC,etal.Collaborativefilteringrecommendationbasedonentropyandtimeliness[J].JournalofComputerApplications, 2016, 36(9): 2531-2534.)

[7] 黃姝娟，朱怡安，李兵哲，等.具有依賴關(guān)系的周期任務(wù)實(shí)時(shí)調(diào)度方法[J].計(jì)算機(jī)學(xué)報(bào),2015,38(5):999-1006.(HUANGSJ,ZHUYA,LIBZ,etal.Real-timeschedulingmethodfordependencyperiodtasks[J].ChineseJournalofComputers, 2015, 38(5): 999-1006.)

[8]ZHOUY,KANGKD.Deadlineassignmentandfeedbackcontrolfordifferentiatedreal-timedataservices[J].IEEETransactionsonKnowledgeandDataEngineering, 2015, 27(12): 3245-3257.

[9]ZHAOY,XIONGYH,LEEEA,etal.ThedesignandapplicationofstructuredtypesinptolemyⅡ,TRUCB/EECS- 2007- 21 [R].Berkeley,CA:UniversityofCalifornia, 2007.

[10] 徐洪智，李仁發(fā)，曾理寧.基于Ptolemy的信息物理融合系統(tǒng)建模與仿真[J].系統(tǒng)仿真學(xué)報(bào)，2014，26(8)：1633-1638.(XUHZ,LIRF,ZENGLN.Modelingandsimulationofcyber-physicalsystembasedonPtolemy[J].JournalofSystemSimulation, 2014, 26(8): 1633-1638.)

[11]EIDSONJC,LEEEA,MATICS,etal.Distributedreal-timesoftwareforcyber-physicalsystems[J].ProceedingsoftheIEEE, 2012, 100(1): 45-59.

[12]DERLERP,JOHNE,STUARTG,etal.Deterministicexecutionofptidesprograms,TRUCB/EECS- 2013- 65 [R].Berkeley,CA:UniversityofCalifornia, 2013.

[13]TRIPAKISS,DAIB,GEILENM,etal.Compositionalityinsynchronousdataflow:modularcodegenerationfromhierarchicalSDFgraphs[J].ACMTransactionsinEmbeddedComputingSystems, 2013, 12(3):ArticleNo. 83.

[14] 陳瑤，李峭，魯俊，等.改進(jìn)的多處理器混合關(guān)鍵性系統(tǒng)可調(diào)性分析[J].北京航空航天大學(xué)學(xué)報(bào),2016,42(9):1918-1926.(CHENY,LIQ,LUJ,etal.Improvedschedulabilityanalysisformultiprocessormixed-criticalitysystems[J].JournalofBeijingUniversityofAeronauticsandAstronautics, 2016, 42(9): 1918-1926.)

[15] 張杰，陽富民，盧炎生，等.EDF統(tǒng)一調(diào)度硬實(shí)時(shí)周期任務(wù)和偶發(fā)任務(wù)的可調(diào)度性判定算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2009,30(12):2383-2388.(ZHANGJ,YANGFM,LUYS,etal.Schedulabilitytestofschedulinghardreal-timeperiodandsporadictasksunifiedwithEDFpolicy[J].JournalofChineseComputerSystems, 2009, 30(12): 2383-2388.)

[16] 袁暋，檀明，周晶晶.EDF調(diào)度算法可調(diào)度性分析方法的改進(jìn)研究[J].計(jì)算機(jī)應(yīng)用研究，2013,30(8):2429-2431.(YUANM,TANM,ZHOUJJ.ResearchonimprovedschdulabilityanalyzingmethodfortasksscheduledunderEDF[J].ApplicationResearchofComputers, 2013, 30(8): 2429-2431.)

[17] 張娟，夏忠婷.基于信息熵的自適應(yīng)資源調(diào)度算法[J].現(xiàn)代雷達(dá),2015,37(8):33-36.(ZHANGJ,XIAZT.Anadaptiveresourceschedulingsearchingmethodbasedoninformationentropy[J].ModernRadar, 2015, 37(8): 33-36.)

[18] 饒運(yùn)清,EFSTATHIOUJ.基于信息熵的制造系統(tǒng)復(fù)雜性測度及其在調(diào)度中的應(yīng)用[J].機(jī)械工程學(xué)報(bào),2006,42(7):8-13.(RAOYQ,EFSTATHIOUJ.Entropy-basedmeasurementofmanufacturingsystemcomplexityanditsapplicationinscheduling[J].ChineseJournalofMechanicalEngineering, 2006, 42(7): 8-13.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61562051),theKeyProjectofAppliedBasicResearchProgramofYunnanProvince(2014FA029).

ZHANG Jing, born in 1974, Ph. D., professor. His research interests include real-time control software, cyber-physical system.

CHEN Yao, born in 1993, M. S. candidate. His research interests include cyber-physical system.

FAN Hongbo, born in 1982, Ph. D., lecturer. His research interests include network security, high performance string matching algorithm.

SUN Jun, born in 1985, Ph. D., lecturer. His research interests include real-time control software.

Scheduling strategy of value evaluation for output-event of actor based on cyber-physical system

ZHANG Jing, CHEN Yao, FAN Hongbo*, SUN Jun

(FacultyofInformationEngineeringandAutomation,KunmingUniversityofScienceandTechnology,KunmingYunnan650500,China)

The performances and correctness of system are affected by the state transition real-time process of the cyber-physical system. In order to solve the problem, aiming at the state transition process of actor’s output-event driven system, a new scheduling strategy of value evaluation for output-event of actor named Value Evaluation-Information Entropy and Quality of Data (VE-IE&QoD) was proposed. Firstly, the real-time performance of event was expressed through the super dense time model. The self-information of the output-event, the information entropy of the actor and the quality of data were defined as the function indexes of value evaluation. Then, the value evaluation mission was executed for the process of the actor in performing task and it was considered about suitably increasing the weighting coefficient for parametric equation. Finally, the discrete event models which contain the proposed VE-IE&QoD scheduling strategy, the traditional Earliest Deadline First (EDF) scheduling algorithm and Information Entropy*(IE*) scheduling strategy were built by Ptolemy Ⅱ platform. The operation situation of different algorithm models was analyzed, the change of value evaluation and execution time of different algorithm models were compared. The experimental results show that, the VE-IE&QoD scheduling strategy can reduce the system average execution time, improve the memory usage efficiency and task value evaluation. The proposed VE-IE&QoD scheduling strategy can improve the system performance and correctness to some extent.

cyber-physical system; actor; event; Information Entropy (IE); quality of data; value evaluation

2016- 11- 28;

2017- 01- 22。

國家自然科學(xué)基金資助項(xiàng)目(61562051)；云南省應(yīng)用基礎(chǔ)研究計(jì)劃重點(diǎn)項(xiàng)目(2014FA029)。

張晶(1974—)，男，云南昆明人，教授，博士，主要研究方向：實(shí)時(shí)控制軟件、信息物理融合系統(tǒng)； 陳垚(1993—)，男，福建莆田人，碩士研究生，主要研究方向：信息物理融合系統(tǒng)； 范洪博(1982—)，男，黑龍江哈爾濱人，講師，博士，主要研究方向：網(wǎng)絡(luò)安全、高性能串匹配算法； 孫俊(1985—)，男，云南昆明人，講師，博士，主要研究方向：實(shí)時(shí)控制軟件。

1001- 9081(2017)06- 1663- 07

10.11772/j.issn.1001- 9081.2017.06.1663

TP302.7

A