實(shí)時(shí)更新與復(fù)制事務(wù)的周期與截止期分派

白 天, 范 波(湖南理工學(xué)院 計(jì)算機(jī)學(xué)院, 湖南 岳陽(yáng) 414006 )

實(shí)時(shí)更新與復(fù)制事務(wù)的周期與截止期分派

白 天, 范 波
(湖南理工學(xué)院 計(jì)算機(jī)學(xué)院, 湖南 岳陽(yáng) 414006 )

在信息物理融合系統(tǒng)中, 本地以及副本實(shí)時(shí)數(shù)據(jù)的有效性分別由更新事務(wù)及復(fù)制事務(wù)負(fù)責(zé). 本文研究了如何為這兩類事務(wù)賦予執(zhí)行周期與截止期以在保證數(shù)據(jù)有效性的同時(shí)最小化生成的系統(tǒng)負(fù)載的問(wèn)題, 給出了解決此問(wèn)題的次梯度優(yōu)化方法和基于模擬退火的方法, 并對(duì)兩種方法的性能進(jìn)行了實(shí)驗(yàn)評(píng)價(jià). 結(jié)果表明, 基于模擬退火的方法在系統(tǒng)負(fù)載以及平均截止期錯(cuò)失率等指標(biāo)上均優(yōu)于次梯度優(yōu)化方法.

信息物理融合系統(tǒng); 實(shí)時(shí)數(shù)據(jù)更新; 實(shí)時(shí)復(fù)制事務(wù)

信息物理融合系統(tǒng)(Cyber-physical system, CPS)是計(jì)算、通信和物理過(guò)程高度集成的系統(tǒng)[1[. 在CPS中, 各結(jié)點(diǎn)通過(guò)傳感器設(shè)備來(lái)獲取相應(yīng)外部實(shí)體的狀態(tài)數(shù)據(jù). 這些狀態(tài)數(shù)據(jù)通常被稱為實(shí)時(shí)數(shù)據(jù). 結(jié)點(diǎn)之間通過(guò)本地實(shí)時(shí)數(shù)據(jù)共享來(lái)協(xié)同工作. 保證本地以及共享實(shí)時(shí)數(shù)據(jù)的有效性對(duì)于CPS來(lái)說(shuō)至關(guān)重要. 對(duì)無(wú)效或過(guò)時(shí)數(shù)據(jù)的訪問(wèn)會(huì)使得系統(tǒng)無(wú)法獲取外部環(huán)境的真實(shí)狀態(tài), 產(chǎn)生錯(cuò)誤的控制決策.

文[2[與文[3[使用完全復(fù)制的方法來(lái)共享實(shí)時(shí)數(shù)據(jù). 前者根據(jù)系統(tǒng)當(dāng)前的負(fù)載分布情況為到達(dá)系統(tǒng)的用戶事務(wù)指派結(jié)點(diǎn), 之后事務(wù)只能在此結(jié)點(diǎn)上執(zhí)行. 后者則允許用戶事務(wù)負(fù)載在不同結(jié)點(diǎn)之間動(dòng)態(tài)遷移.文[4[與文[5[使用分組的方法來(lái)實(shí)現(xiàn)數(shù)據(jù)共享. 前者可在運(yùn)行時(shí)對(duì)組內(nèi)單個(gè)結(jié)點(diǎn)上的數(shù)據(jù)更新策略以及數(shù)據(jù)副本在組內(nèi)的分布模式進(jìn)行動(dòng)態(tài)調(diào)整. 后者基于Kalman濾波器與數(shù)據(jù)精度界限來(lái)實(shí)現(xiàn)組內(nèi)數(shù)據(jù)的更新與更新廣播. 文[6[采用發(fā)布者/訂閱者模型, 通過(guò)反饋與前饋控制相結(jié)合的方式來(lái)調(diào)整數(shù)據(jù)精度界限與結(jié)點(diǎn)資源利用率界限. 上述工作均采用基于服務(wù)質(zhì)量的方法來(lái)維護(hù)數(shù)據(jù)和事務(wù)的實(shí)時(shí)性. 不同于這些工作,本文研究如何為更新與復(fù)制事務(wù)分派執(zhí)行周期與截止期以保證實(shí)時(shí)數(shù)據(jù)對(duì)象的有效性.

1 系統(tǒng)模型

圖1為本文使用的系統(tǒng)模型. 系統(tǒng)包含兩類不同的結(jié)點(diǎn): 傳感器結(jié)點(diǎn)和數(shù)據(jù)處理結(jié)點(diǎn). 傳感器結(jié)點(diǎn)負(fù)責(zé)采集環(huán)境數(shù)據(jù). 數(shù)據(jù)通過(guò)多跳無(wú)線網(wǎng)絡(luò)上傳至數(shù)據(jù)處理結(jié)點(diǎn). 數(shù)據(jù)處理結(jié)點(diǎn)進(jìn)行本地實(shí)時(shí)數(shù)據(jù)的更新并將匯總后的實(shí)時(shí)數(shù)據(jù)發(fā)送到其它相關(guān)的數(shù)據(jù)處理結(jié)點(diǎn). 這兩項(xiàng)工作分別由本地更新事務(wù)與數(shù)據(jù)復(fù)制事務(wù)負(fù)責(zé). 除此之外, 數(shù)據(jù)處理結(jié)點(diǎn)還將執(zhí)行控制決策與數(shù)據(jù)查詢分析事務(wù). 數(shù)據(jù)處理結(jié)點(diǎn)之間通過(guò)局域網(wǎng)連接, 每個(gè)結(jié)點(diǎn)負(fù)責(zé)處理一部分傳感器結(jié)點(diǎn)的數(shù)據(jù). 兩類結(jié)點(diǎn)的對(duì)應(yīng)關(guān)系在系統(tǒng)設(shè)計(jì)時(shí)確定并在系統(tǒng)運(yùn)行時(shí)保持不變.

圖1 系統(tǒng)模型

定義[7[在時(shí)刻t是有效的, 或稱為時(shí)態(tài)一致的, 若當(dāng)前值的采樣時(shí)刻ts()與之和不小于t, 即ts()+≥t.

結(jié)點(diǎn)Si到結(jié)點(diǎn)Sj的數(shù)據(jù)共享是通過(guò)復(fù)制事務(wù)集Γi,j={來(lái)完成的. 事務(wù)(1≤k≤)由子事務(wù)與組成.在Si上進(jìn)行本地實(shí)時(shí)數(shù)據(jù)的匯總, 其執(zhí)行時(shí)間為Sj在接收到匯總數(shù)據(jù)后, 執(zhí)行以更新對(duì)應(yīng)的副本數(shù)據(jù).的執(zhí)行時(shí)間為. 匯總數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸時(shí)延為匯總數(shù)據(jù)主副本之間的時(shí)間一致性界限為.

2 事務(wù)執(zhí)行周期與截止期分派

我們用早期截止期優(yōu)先算法(EDF)來(lái)調(diào)度各結(jié)點(diǎn)上的事務(wù). 使用EDF的好處在于其容易實(shí)現(xiàn)不同類型事務(wù)的聯(lián)合調(diào)度. 對(duì)于更新事務(wù), 其周期j與截止期的設(shè)置需要滿足

并要求約束條件

考慮到結(jié)點(diǎn)iS上還有其它類型的事務(wù)需要執(zhí)行, 因此需要盡量減小更新與復(fù)制事務(wù)執(zhí)行所帶來(lái)的負(fù)載. 給定iS的權(quán)重為iw, 整個(gè)系統(tǒng)的負(fù)載U為

綜上, 事務(wù)的周期與截止期分派問(wèn)題可描述為確定各結(jié)點(diǎn)上各事務(wù)的周期與截止期, 使之在滿足式(1)、式(2)、式(3)與式(7)的前提下最小化U. 令D={D(S)表示問(wèn)題的一個(gè)解. 考慮以下兩種解決此

i問(wèn)題的方法. 方法之一是使用次梯度算法(SG). 步驟如下:

① 設(shè)定k為0, 拉格朗日乘子λk的初始值為0.

② 根據(jù)λk求出Dk:其中Dk中各元素的取值范圍由式(1)、式(2)和式(3)確定. 此時(shí)得到的次梯度為Wk-Dk, 若其值為0, 則算法結(jié)束. 此時(shí)的Dk與λk分別為原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解.

③ 計(jì)算下次迭代中的λ:

其中εk為步長(zhǎng).

④ 設(shè)置k=k+1, 回到第②步. 此過(guò)程重復(fù)直到給定的迭代次數(shù)用完為止.

第二種方法是使用模擬退火算法(SAP). 為了處理問(wèn)題中的約束, 定義目標(biāo)函數(shù)V為:

其中p為懲罰因子. 初始時(shí)設(shè)置p0為一個(gè)較小的值. 在第k次迭代中, 使用SA算法求出pk下的V的最小值. 若找不到可行解, 則設(shè)置pk+1=pkσ1, Tk+1=Tkσ

2(σ1＞1, σ2＞1). 這里Tk表示使用SA算法時(shí)的初始溫度值. 之后進(jìn)行新一輪迭代. 此過(guò)程重復(fù)直到給定的迭代次數(shù)用完為止.

3 實(shí)驗(yàn)評(píng)價(jià)

本節(jié)通過(guò)實(shí)驗(yàn)來(lái)比較兩種方法的性能. 評(píng)價(jià)指標(biāo)為系統(tǒng)負(fù)載(SU)與平均截止期錯(cuò)失率(AMDR). 前者由式(8)給出, 后者的定義如下:

實(shí)驗(yàn)中假定數(shù)據(jù)對(duì)象放在各結(jié)點(diǎn)的內(nèi)存中. 考慮到當(dāng)前的內(nèi)存容量及中小型系統(tǒng)的應(yīng)用需求, 這個(gè)假設(shè)是合理的. 用戶事務(wù)只在單個(gè)結(jié)點(diǎn)上執(zhí)行, 通過(guò)訪問(wèn)本地實(shí)時(shí)數(shù)據(jù)與遠(yuǎn)程數(shù)據(jù)的副本來(lái)工作. 我們使用EDF來(lái)調(diào)度用戶事務(wù). 表1給出了部分實(shí)驗(yàn)參數(shù)及取值. 所有數(shù)據(jù)傳輸時(shí)延均設(shè)為零,,ijΓ的大小為[1,5[內(nèi)的隨機(jī)值. 每個(gè)結(jié)點(diǎn)的復(fù)制扇出為[1,sN/5[內(nèi)的隨機(jī)值, 具體的復(fù)制結(jié)點(diǎn)從所有結(jié)點(diǎn)中隨機(jī)選取.設(shè)定各結(jié)點(diǎn)的權(quán)重相同, 均為1/sN. 表1中的事務(wù)執(zhí)行時(shí)間指更新事務(wù)與復(fù)制子事務(wù)的執(zhí)行時(shí)間. 表1中參數(shù)的值在相應(yīng)的范圍內(nèi)隨機(jī)選取.

表1 實(shí)驗(yàn)參數(shù)及設(shè)置

圖2給出了兩種方法對(duì)應(yīng)的系統(tǒng)負(fù)載比較. 在圖2a中, 系統(tǒng)的結(jié)點(diǎn)個(gè)數(shù)固定為15個(gè), 而各結(jié)點(diǎn)上的實(shí)時(shí)數(shù)據(jù)對(duì)象個(gè)數(shù)逐漸增加. 在圖2b中, 各結(jié)點(diǎn)上的實(shí)時(shí)數(shù)據(jù)對(duì)象個(gè)數(shù)固定為30個(gè), 而系統(tǒng)的總結(jié)點(diǎn)數(shù)目逐漸增加. 由圖2可知, 在這兩種設(shè)置下, 由SAP所得到的解均要優(yōu)于SG. 此外, 隨著結(jié)點(diǎn)個(gè)數(shù)或數(shù)據(jù)對(duì)象個(gè)數(shù)的增加, 兩種方法下的系統(tǒng)負(fù)載都會(huì)隨之增加.

圖3給出的是系統(tǒng)結(jié)點(diǎn)個(gè)數(shù)為15, 各結(jié)點(diǎn)上的實(shí)時(shí)數(shù)據(jù)對(duì)象個(gè)數(shù)為50時(shí)的用戶事務(wù)平均截止期錯(cuò)失率比較. 在每個(gè)結(jié)點(diǎn)上我們按泊松分布生成用戶事務(wù)到達(dá)系統(tǒng). 由圖3可知, 在SAP下的平均截止期錯(cuò)失率要低于SG. 原因在于SAP下的系統(tǒng)負(fù)載要低于SG, 因此能留出更多的時(shí)間給用戶事務(wù)執(zhí)行. 此外, 隨著事務(wù)到達(dá)率的提高, 兩種方法下的平均截止期錯(cuò)失率都會(huì)增加. 通過(guò)修改相關(guān)的參數(shù)設(shè)置, 我們重復(fù)進(jìn)行了上述實(shí)驗(yàn), 得到的結(jié)果類似, 在此不再贅述.

圖2 系統(tǒng)負(fù)載比較

圖3 平均截止期錯(cuò)失率比較

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

本文研究信息物理融合系統(tǒng)中的本地以及共享實(shí)時(shí)數(shù)據(jù)的有效性維護(hù)問(wèn)題. 已有的研究主要考慮如何保證數(shù)據(jù)及事務(wù)的服務(wù)質(zhì)量. 與這些工作不同，本文考慮如何為更新與復(fù)制事務(wù)分派周期與截止期以最小化系統(tǒng)的總負(fù)載. 給出了兩種解決此問(wèn)題的方法，即基于次梯度優(yōu)化的方法（SG）和基于模擬退火的方法（SAP）. 模擬實(shí)驗(yàn)的結(jié)果表明，相比SG，SAP生成的解在系統(tǒng)負(fù)載以及平均截止期錯(cuò)失率等指標(biāo)上的表現(xiàn)更優(yōu). 在下一步的研究中，我們將考慮更新事務(wù)、復(fù)制事務(wù)與用戶事務(wù)的聯(lián)合調(diào)度問(wèn)題.

[1]溫景容，武穆清，宿景芳. 信息物理融合系統(tǒng)[J[. 自動(dòng)化學(xué)報(bào)，2012，38（4）： 507～517

[2]Zhou Y ，Kang K D. A Federated Approach for Increasing the Timely Throughput of Real-Time Data Services[C[. IEEE 18th Real-Time and Embedded Technology and Applications Symposium，2012，163～172

[3]Wei Y，Son S H ，Stankovic J A，et al. QoS management in replicated real-time databases[C[. 24th IEEE Real-Time Systems Symposium，2003，86～97

[4]Kang W，Son S H，Stankovic J A. DRACON： QoS Management for Large-Scale Distributed Real-Time Databases [J[. JOURNAL OF SOFTWARE，2009，4（7）： 747～757

[5]Kang W，Son S H，Stankovic J A. Quality-aware data abstraction layer for collaborative 2-tier sensor network applications [J[. Real-time systems，2012，48： 463～498

[6]Kang W，Kapitanova K ，Son S H. RDDS： A Real-Time Data Distribution Service for Cyber-Physical Systems [J[. IEEE Transactions on Industrial Informatics，2012，8（2）： 393～405.

[7]Ramamritham K. Real-time databases [J[. Distributed and Parallel Databases，1993，1（2）： 199～226

Deriving Periods and Deadlines for Real-time Updates and Replication Transactions

BAI Tian, FAN Bo
(College of Computer Science, Hunan Institute of Science and Technology, Yueyang, 414006, China)

In Cyber-physical systems, the validity of local and replicated real-time data are maintained by update transactions and replication transactions respectively. This paper studied the problem of period and deadline assignment for these two kind of transactions so that the data validity is maintained while the imposed system workload is minimized. A subgradient method and a simulated annealing based method were proposed to solve the problem. The methods were evaluated through simulations. The results showed the simulated annealing based method performs better than the subgradient method in terms of the system workload and the average missed deadline ratio.

Cyber-physical systems, real-time updates, real-time replication transactions

TP311

A

1672-5298(2016)02-0020-04

2016-03-12

湖南省自然科學(xué)基金資助項(xiàng)目(2015JJ6044)

白 天(1983- ), 男, 湖南岳陽(yáng)人, 博士, 湖南理工學(xué)院計(jì)算機(jī)學(xué)院講師. 主要研究方向: 實(shí)時(shí)數(shù)據(jù)庫(kù), 信息物理融合系統(tǒng)