白 天, 范 波(湖南理工學(xué)院 計算機學(xué)院, 湖南 岳陽 414006 )

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

白 天, 范 波
(湖南理工學(xué)院 計算機學(xué)院, 湖南 岳陽 414006 )

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

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

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

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

1 系統(tǒng)模型

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

圖1 系統(tǒng)模型

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

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

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

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

并要求約束條件

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

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

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

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

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

③ 計算下次迭代中的λ:

其中εk為步長.

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

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

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

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

3 實驗評價

本節(jié)通過實驗來比較兩種方法的性能. 評價指標為系統(tǒng)負載(SU)與平均截止期錯失率(AMDR). 前者由式(8)給出, 后者的定義如下:

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

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

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

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

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

圖3 平均截止期錯失率比較

4 結(jié)束語

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

[1]溫景容，武穆清，宿景芳. 信息物理融合系統(tǒng)[J[. 自動化學(xué)報，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é)基金資助項目(2015JJ6044)

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