基于有效度函數(shù)的傳感器事務調(diào)度策略*

白 天,李國徽,范 波

(1.湖南理工學院計算機學院，湖南 岳陽 414000 ；2.華中科技大學計算機科學與技術(shù)學院，湖北 武漢 430074)

基于有效度函數(shù)的傳感器事務調(diào)度策略*

白 天1,李國徽2,范 波1

(1.湖南理工學院計算機學院，湖南 岳陽 414000 ；2.華中科技大學計算機科學與技術(shù)學院，湖北 武漢 430074)

針對數(shù)據(jù)的絕對一致性概念只能夠描述二元數(shù)據(jù)狀態(tài)的問題，提出了數(shù)據(jù)有效度函數(shù)的概念。給出了兩種基于有效度函數(shù)的傳感器事務調(diào)度策略VM-DS與VM-SN。策略通過合理的設置數(shù)據(jù)對象的有效時間段長度及事務的執(zhí)行頻率來最大化系統(tǒng)中數(shù)據(jù)的有效程度。通過實驗對兩種策略的性能進行了對比分析。結(jié)果表明，VM-SN在平均數(shù)據(jù)有效度、有效度負載比等性能指標上均優(yōu)于VM-DS，能夠更好的滿足系統(tǒng)的實時性要求。

信息物理融合系統(tǒng)；傳感器事務；有效度函數(shù)

信息物理融合系統(tǒng)(cyber physical system, CPS)是將感控、計算和通信能力深度嵌入物理過程后形成的網(wǎng)絡化智能系統(tǒng)[1-2]。在CPS的相關(guān)研究中，一個重要的領(lǐng)域是實時數(shù)據(jù)對象的有效性維護。實時數(shù)據(jù)對象描述了外部物理實體的當前狀態(tài)。與傳統(tǒng)數(shù)據(jù)對象不同的是，實時數(shù)據(jù)對象的值具有時效性。訪問無效或過度陳舊的數(shù)據(jù)值會導致錯誤的控制決策，給系統(tǒng)帶來危害。

已有的研究工作基本上使用數(shù)據(jù)的絕對一致性定義作為數(shù)據(jù)有效性的定義[3-4]。在此定義下，系統(tǒng)中的每個數(shù)據(jù)對象都被賦予一個時態(tài)有效期。數(shù)據(jù)對象的當前值在有效期內(nèi)是絕對一致(有效)的，超過期限后，數(shù)據(jù)值將失效。典型的單處理器數(shù)據(jù)一致性維護算法包括More-Less算法(ML)、DS-FP算法與基于動態(tài)優(yōu)先級的算法。ML使用周期性事務模型與截止期單調(diào)算法(DM)[4-5]，其通過合理分派事務的周期與相對截止期來滿足事務集的可調(diào)度性與數(shù)據(jù)的絕對一致性。DS-FP采用非周期性事務模型[6-8]，其在滿足絕對一致性的前提下通過適當調(diào)整實例的開始時間來降低更新負載?；趧討B(tài)優(yōu)先級的算法主要解決早期截止期優(yōu)先策略(EDF)下的事務周期與截止期分派問題[9-10]。文獻[11]提出了用于多處理器平臺的事務分派策略，在單個處理器上事務的調(diào)度執(zhí)行采用EDF算法。以上研究只考慮如何確保實時數(shù)據(jù)對象本身的絕對一致性，文獻[12]和[13]研究了如何通過并發(fā)控制及串行化順序調(diào)整來確保用戶事務所讀取的實時數(shù)據(jù)滿足絕對以及相對一致性。

絕對一致性定義的主要不足在于其僅能夠說明數(shù)據(jù)在某一時刻是處于有效狀態(tài)還是無效狀態(tài)，而不能具體給出數(shù)據(jù)的有效程度是多少以及有效程度隨時間變化的情況。在支持多級服務質(zhì)量的系統(tǒng)中，服務質(zhì)量級別通常會基于數(shù)據(jù)的有效程度來定義。級別越低，數(shù)據(jù)的有效程度就越低，對應的事務更新頻率也會越低。這樣系統(tǒng)在運行時可以根據(jù)當前的負載及用戶對數(shù)據(jù)有效性的要求進行服務質(zhì)量級別的動態(tài)調(diào)整。數(shù)據(jù)的絕對一致性定義無法用來構(gòu)建這類系統(tǒng)的服務質(zhì)量模型，為此本文提出數(shù)據(jù)有效度函數(shù)的概念。在此基礎(chǔ)上給出兩種傳感器事務調(diào)度策略以實現(xiàn)數(shù)據(jù)有效程度的最大化。

1 數(shù)據(jù)有效度函數(shù)

圖1 典型的有效度函數(shù)Fig.1 Typical validity functions

定義hi(t)的方法有多種。一種方法是預先確定n個有效級別，級別j(1≤j≤n)對應數(shù)據(jù)值與外部狀態(tài)值的差值dj。d1=0。若i≤j，則di≤dj。級別j的有效程度vj設置為(dn-dj)/dn。根據(jù)外部狀態(tài)值的變化率可以得到級別j對應的時間段Lj。由此可以得到hi(t)如下：

在現(xiàn)有的絕對一致性定義下，傳感器事務調(diào)度的目標是確保數(shù)據(jù)在任何時刻都是完全有效的。而在有效度函數(shù)的定義下，傳感器事務調(diào)度的目標則是盡量提高數(shù)據(jù)的有效程度。圖2給出了一般化的調(diào)度策略下，使用圖1(a)中的hi(t)時Xi的有效程度隨時間變化的情況。在0時刻，Xi完全有效。隨后其有效程度下降。當τi的第一個實例τi,1在fi,1時刻完成后，Xi的有效程度上升至hi(fi,1-ri,1)。ri,1為τi,1的開始時刻(即采樣時刻)。在fi,1之后，Xi的有效程度將隨著τi實例的執(zhí)行而交替的下降和上升。

圖2 數(shù)據(jù)有效程度的變化Fig.2 Evolution of data validity degree

給定開始于ts且長度為T的觀察窗口，數(shù)據(jù)集X在窗口內(nèi)的平均有效程度V(X)由式(1)給出。為了使用戶訪問到的數(shù)據(jù)盡可能的有效，調(diào)度策略應使得V(X)的值盡可能的大。這里假定數(shù)據(jù)對象的重要程度是相同的。例如數(shù)據(jù)具有相同的訪問頻率。若不相同，可以在V(X)的定義中加上權(quán)重系數(shù)。

(1)

2 傳感器事務調(diào)度策略

根據(jù)有效度函數(shù)的定義，傳感器事務調(diào)度策略需要確定每個數(shù)據(jù)對象的有效時間段，事務的執(zhí)行頻率與事務的調(diào)度算法，以最大化V(X)。在單處理器實時任務調(diào)度算法中，EDF算法具有最優(yōu)的可調(diào)度性，故本文使用EDF來調(diào)度事務。此外在CPS中除了傳感器事務之外,通常還存在對外部過程進行控制的事務，使用EDF易于實現(xiàn)兩種類型事務的聯(lián)合調(diào)度。

2.1 VM-DS策略

(2)

問題滿足以下的約束條件：

(3)

(4)

算法1Llb的計算

2)若Llb不滿足式(3)，則Γ不可調(diào)度，返回失敗;

3)LOOP

4)Llb′←Llb-▽V(Llb)·δ;

5)若Llb′不滿足式(3)或式(4)，exit;

6)Llb←Llb′;

7)REPEAT

8)Vmax=V(Llb);

9)FORi=1 tok

10)?V(Llb)←TF(ΔV(Llb));

11)LOOP

12)Llb′←Llb-?V(Llb)·δ1;

13)若Llb′不滿足式(3)或式(4)，exit;

14)Llb←Llb′;

15)REPEAT

16)Vmax=max(V(Llb),Vmax);

17)ENDFOR

定理1 若實時數(shù)據(jù)對象Xi的有效度函數(shù)hi(t)為kit+bi(ki<0)，且滿足

與

則式(2)的最優(yōu)解為：

證明 根據(jù)式(2)及hi(t)的定義可得：

(5)

設置ui與vi為零，則由上述條件可求得：

根據(jù)文獻[14]，事務在時間區(qū)間[0,t)內(nèi)的最大累計執(zhí)行時間需求可表示為：

(6)

事務集可被EDF調(diào)度的充要條件可表示為：

(7)

若采用后者，則設置：

具有很好的防水性能，這是保障路面不會受到路表或外界環(huán)境中的水的影響而造成路面整體性、強度和剛度下降的主要因素。

令P(τi,tc)表示在tc時刻可以使dbf(τi,tc)減小的調(diào)整策略集合。若不存在這樣的策略，則P(τi,tc)=?。P(τi,tc)中的第j個策略簡記為pi,j。使用pi,j后dbf(τi,tc)的減小量記為Δdbf(τi,tc,pi,j)。Xi的有效程度可表示為：

據(jù)此可求出X有效程度的變化量ΔV(xi,pi,j)。

令Δdbf(Γ,tc)表示dbf(Γ,tc)與tc的差值。需要確定每個事務的調(diào)整策略，使得Δdbf(Γ,tc)不大于零且V(X)的增加量最小。令xi,j表示pi,j被選中，則有：

(8)

式(8)滿足以下的約束條件：

(9)

(10)

算法2給出了Llb和F的求解過程。算法判斷式(7)是否在測試范圍內(nèi)的每個時間點上成立。若不成立，則通過求解式(8)得到Llb與F的更新量ΔLlb與ΔF，并據(jù)此更新ΔLlb與F。若無法通過更新Llb與F來滿足式(7)，則算法失敗。

算法2Llb和F的計算

2)tc←0;

3)LOOP

4)tc←tc+1

5)IFΔdbf(Γ,tc)>0

6)求解式(8), 得到ΔLlb與ΔF;

7)若ΔLlb與ΔF均為0，返回失敗;

8)Llb←Llb+ΔLlb;

9)F←F+ΔF;

10)ENDIF

11)若tc已達到測試范圍的上界，返回成功;

12)REPEAT

3 實驗評價

本節(jié)給出兩種策略的實驗評價。主要評價指標為平均數(shù)據(jù)有效度和有效度負載比。平均數(shù)據(jù)有效度由式(1)直接計算得到。有效度負載比定義為平均數(shù)據(jù)有效度與事務更新負載的比值。此外，實驗還比較不同策略下的事務有效度，定義為用戶事務所訪問數(shù)據(jù)的有效程度的平均值。

表1 實驗參數(shù)及設置

圖3給出了兩種策略的平均數(shù)據(jù)有效度比較。由圖可知，在不同的事務數(shù)目下，VM-SN的平均數(shù)據(jù)有效度均高于VM-DS。兩者的差異隨著事務數(shù)目的增加而增加。原因在于VM-DS將事務的執(zhí)行頻率簡單設置為所允許的最低執(zhí)行頻率的兩倍，且使用了充分條件來尋找有效時間段，這使得許多滿足條件的更優(yōu)的解被VM-DS丟棄。VM-SN不將執(zhí)行頻率與有效時間段簡單關(guān)聯(lián)，而是通過充要條件來尋找兩者的取值，這極大的提高了解的質(zhì)量。

圖3 平均數(shù)據(jù)有效度的比較Fig.3 Average data validity degree comparison

圖4給出了不同的事務數(shù)目下兩種策略的有效度負載比。在絕對一致性定義下，評價傳感器事務調(diào)度策略的一個重要指標是策略產(chǎn)生的更新負載。在有效度函數(shù)的定義下，不同策略得到的有效時間段不同，直接比較更新負載不再合適。而有效度負載比則能較好的反映數(shù)據(jù)有效度與系統(tǒng)負載之間的相對關(guān)系。由圖4可知，VM-SN的有效度負載比在不同情況下均高于VM-DS。這說明在保證較高數(shù)據(jù)有效度的前提下，VM-SN所產(chǎn)生的負載也是較為合理的。這有利于系統(tǒng)中其它類型事務的實時性維護。

圖4 有效度負載比的比較Fig.4 Ratio of validity degree to workload comparison

圖5給出了用戶事務的到達率為12事務/s時的事務有效度比較。由于VM-SN的平均數(shù)據(jù)有效度高于VM-DS，使用VM-SN時用戶事務在任何時刻訪問到更高有效度的數(shù)據(jù)的可能性也更大。這使得VM-SN下的用戶事務有效度高于VM-DS。此外隨著事務數(shù)目的增加，兩者的差異也會增大。在其他的參數(shù)設置下我們重復進行了上述的實驗，得到了類似的結(jié)果，在此不再給出。

圖5 事務有效度的比較 (12事務/s)Fig.5 Transaction validity degree comparison (12 trans /s)

4 結(jié) 語

如何維護實時數(shù)據(jù)對象的有效性是CPS研究中的一個重要問題。提出了數(shù)據(jù)有效度函數(shù)的概念。傳統(tǒng)的數(shù)據(jù)絕對一致性定義可視為數(shù)據(jù)有效度函數(shù)的一個特例。給出了一種有效度函數(shù)的定義方法。在有效度函數(shù)的定義下，傳感器事務調(diào)度的目標是盡量提高系統(tǒng)中數(shù)據(jù)的有效程度。提出了兩種用于實現(xiàn)此目標的傳感器事務調(diào)度策略VM-DS與VM-SN。VM-DS將事務的采樣頻率固定設置為其最低允許采樣頻率的兩倍，并使用EDF可調(diào)度的充分條件來求出事務的有效時間段。而VM-SN則是利用EDF可調(diào)度的充要條件來同時確定事務的采樣頻率及有效時間段。實驗分析表明，相比VM-DS，VM-SN能夠確保更高的平均數(shù)據(jù)有效度，其產(chǎn)生的更新負載相對于其提供的平均數(shù)據(jù)有效度也更低。文中提出的調(diào)度策略只能用于單處理器平臺。下一步的研究工作是設計基于有效度函數(shù)的多處理器事務調(diào)度策略。

[1]RAJKUMARR,LEEI,SHAL,etal.Cyber-physicalsystems:Thenextcomputingrevolution[C]∥Proceedingsofthe47thACM/IEEEDesignAutomationConference(DAC).Anaheim,CA:IEEE, 2010: 731-736.

[2] 溫景容, 武穆清, 宿景芳. 信息物理融合系統(tǒng)[J].自動化學報, 2012, 38(4):507-517.

[3]RAMAMRITHAMK.Real-timedatabases[J].DistributedandParallelDatabases, 1993, 1(2): 199-226.

[4]XIONGM,RAMAMRITHAMK.Derivingdeadlinesandperiodsforreal-timeupdatetransactions[J].IEEETransactionsonComputers, 2004, 53(5):567-583.

[5]WANGJ,HANS,LAMKY,etal.Maintainingdatatemporalconsistencyindistributedreal-timesystems[J].Real-TimeSystems, 2012, 48(4): 387-429.

[6]XIONGM,HANS,LAMKY,etal.Deferrableschedulingformaintainingreal-timedatafreshness:Algorithms,analysis,andresults[J].IEEETransactionsonComputers, 2008, 57(7): 952-964.

[7]HANS,CHEND,XIONGM,etal.Schedulabilityanalysisofdeferrableschedulingalgorithmsformaintainingreal-timedatafreshness[J].IEEETransactionsonComputers, 2014, 63(4): 979-994.

[8]XIONGM,HANS,CHEND,etal.DESH:overheadreductionalgorithmsfordeferrablescheduling[J].Real-TimeSystems, 2010, 44(1/2/3): 1-25.

[9]XIONGM,WANGQ,RAMAMRITHAMK.Onearliestdeadlinefirstschedulingfortemporalconsistencymaintenance[J].Real-TimeSystems, 2008, 40(2): 208-237.

[10]LIJ,XIONGM,LEEVCS,etal.Workload-efficientdeadlineandperiodassignmentformaintainingtemporalconsistencyunderEDF[J].IEEETransactionsonComputers, 2013, 62(6): 1255-1268.

[11]LIJ,CHENJ,XIONGM,etal.Workload-awarepartitioningformaintainingtemporalconsistencyuponmultiprocessorplatforms[C]∥Proceedingsofthe2011IEEE32ndReal-TimeSystemsSymposium.Vienna:IEEE, 2011: 126-135.

[12] 劉波, 范士明, 劉華. 一種動態(tài)調(diào)整串行化順序的實時并發(fā)控制協(xié)議[J].小型微型計算機系統(tǒng), 2013, 34(3):443-449.

[13] 肖迎元, 劉云生. 確保時態(tài)一致性的實時并發(fā)控制協(xié)議[J].電子學報, 2009, 36(11):2102-2106.

[14]BARUAHSK,MOKAK,ROSIERLE.Preemptivelyschedulinghard-real-timesporadictasksononeprocessor[C]∥IEEEReal-TimeSystemsSymposium.LakeBuenaVista,FL:IEEE, 1990: 182-190.

Validity degree function based sensor transaction scheduling schemes

BAITian1,LIGuohui2,FANBo1

(1. College of Computer Science, Hunan Institute of Science and Technology,Yueyang 414000, China；2. College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China )

The disadvantage of the concept of temporal consistency is that it only describes binary states of real-time data objects. The concept of validity degree function is presented to overcome the problem. Based on the new concept, two sensor transaction scheduling schemes VM-DS and VM-SN are proposed. Both schemes maximize the data validity degree by judiciously setting the lengths of data validity intervals and the execution frequencies of sensor transactions. Experiments are conducted to evaluate the performance of two schemes. The results show VM-SN outperforms in terms of the average data validity degree and the ratio of validity degree to workload, thus it can better satisfy the timeliness requirements of the systems.

cyber physical systems; sensor transactions; validity degree function

10.13471/j.cnki.acta.snus.2016.02.008

2015-11-15

國家自然科學基金資助項目(61173049);湖南省自然科學基金資助項目(2015JJ6044)

白天(1983年生),男;研究方向：實時數(shù)據(jù)庫、信息物理融合系統(tǒng)；E-mail:baitiannobel@163.com

TP311

A

0529-6579(2016)02-0042-06