实时更新与复制事务的周期与截止期分派

白 天, 范 波(湖南理工学院 计算机学院, 湖南 岳阳 414006 )

实时更新与复制事务的周期与截止期分派

白 天, 范 波
(湖南理工学院 计算机学院, 湖南 岳阳 414006 )

在信息物理融合系统中, 本地以及副本实时数据的有效性分别由更新事务及复制事务负责. 本文研究了如何为这两类事务赋予执行周期与截止期以在保证数据有效性的同时最小化生成的系统负载的问题, 给出了解决此问题的次梯度优化方法和基于模拟退火的方法, 并对两种方法的性能进行了实验评价. 结果表明, 基于模拟退火的方法在系统负载以及平均截止期错失率等指标上均优于次梯度优化方法.

信息物理融合系统; 实时数据更新; 实时复制事务

信息物理融合系统(Cyber-physical system, CPS)是计算、通信和物理过程高度集成的系统[1[. 在CPS中, 各结点通过传感器设备来获取相应外部实体的状态数据. 这些状态数据通常被称为实时数据. 结点之间通过本地实时数据共享来协同工作. 保证本地以及共享实时数据的有效性对于CPS来说至关重要. 对无效或过时数据的访问会使得系统无法获取外部环境的真实状态, 产生错误的控制决策.

文[2[与文[3[使用完全复制的方法来共享实时数据. 前者根据系统当前的负载分布情况为到达系统的用户事务指派结点, 之后事务只能在此结点上执行. 后者则允许用户事务负载在不同结点之间动态迁移.文[4[与文[5[使用分组的方法来实现数据共享. 前者可在运行时对组内单个结点上的数据更新策略以及数据副本在组内的分布模式进行动态调整. 后者基于Kalman滤波器与数据精度界限来实现组内数据的更新与更新广播. 文[6[采用发布者/订阅者模型, 通过反馈与前馈控制相结合的方式来调整数据精度界限与结点资源利用率界限. 上述工作均采用基于服务质量的方法来维护数据和事务的实时性. 不同于这些工作,本文研究如何为更新与复制事务分派执行周期与截止期以保证实时数据对象的有效性.

1 系统模型

图1为本文使用的系统模型. 系统包含两类不同的结点: 传感器结点和数据处理结点. 传感器结点负责采集环境数据. 数据通过多跳无线网络上传至数据处理结点. 数据处理结点进行本地实时数据的更新并将汇总后的实时数据发送到其它相关的数据处理结点. 这两项工作分别由本地更新事务与数据复制事务负责. 除此之外, 数据处理结点还将执行控制决策与数据查询分析事务. 数据处理结点之间通过局域网连接, 每个结点负责处理一部分传感器结点的数据. 两类结点的对应关系在系统设计时确定并在系统运行时保持不变.

图1 系统模型

定义[7[在时刻t是有效的, 或称为时态一致的, 若当前值的采样时刻ts()与之和不小于t, 即ts()+≥t.

结点Si到结点Sj的数据共享是通过复制事务集Γi,j={来完成的. 事务(1≤k≤)由子事务与组成.在Si上进行本地实时数据的汇总, 其执行时间为Sj在接收到汇总数据后, 执行以更新对应的副本数据.的执行时间为. 汇总数据在网络中的传输时延为汇总数据主副本之间的时间一致性界限为.

2 事务执行周期与截止期分派

我们用早期截止期优先算法(EDF)来调度各结点上的事务. 使用EDF的好处在于其容易实现不同类型事务的联合调度. 对于更新事务, 其周期j与截止期的设置需要满足

并要求约束条件

考虑到结点iS上还有其它类型的事务需要执行, 因此需要尽量减小更新与复制事务执行所带来的负载. 给定iS的权重为iw, 整个系统的负载U为

综上, 事务的周期与截止期分派问题可描述为确定各结点上各事务的周期与截止期, 使之在满足式(1)、式(2)、式(3)与式(7)的前提下最小化U. 令D={D(S)表示问题的一个解. 考虑以下两种解决此

i问题的方法. 方法之一是使用次梯度算法(SG). 步骤如下:

① 设定k为0, 拉格朗日乘子λk的初始值为0.

② 根据λk求出Dk:其中Dk中各元素的取值范围由式(1)、式(2)和式(3)确定. 此时得到的次梯度为Wk-Dk, 若其值为0, 则算法结束. 此时的Dk与λk分别为原问题和对偶问题的最优解.

③ 计算下次迭代中的λ:

其中εk为步长.

④ 设置k=k+1, 回到第②步. 此过程重复直到给定的迭代次数用完为止.

第二种方法是使用模拟退火算法(SAP). 为了处理问题中的约束, 定义目标函数V为:

其中p为惩罚因子. 初始时设置p0为一个较小的值. 在第k次迭代中, 使用SA算法求出pk下的V的最小值. 若找不到可行解, 则设置pk+1=pkσ1, Tk+1=Tkσ

2(σ1＞1, σ2＞1). 这里Tk表示使用SA算法时的初始温度值. 之后进行新一轮迭代. 此过程重复直到给定的迭代次数用完为止.

3 实验评价

本节通过实验来比较两种方法的性能. 评价指标为系统负载(SU)与平均截止期错失率(AMDR). 前者由式(8)给出, 后者的定义如下:

实验中假定数据对象放在各结点的内存中. 考虑到当前的内存容量及中小型系统的应用需求, 这个假设是合理的. 用户事务只在单个结点上执行, 通过访问本地实时数据与远程数据的副本来工作. 我们使用EDF来调度用户事务. 表1给出了部分实验参数及取值. 所有数据传输时延均设为零,,ijΓ的大小为[1,5[内的随机值. 每个结点的复制扇出为[1,sN/5[内的随机值, 具体的复制结点从所有结点中随机选取.设定各结点的权重相同, 均为1/sN. 表1中的事务执行时间指更新事务与复制子事务的执行时间. 表1中参数的值在相应的范围内随机选取.

表1 实验参数及设置

图2给出了两种方法对应的系统负载比较. 在图2a中, 系统的结点个数固定为15个, 而各结点上的实时数据对象个数逐渐增加. 在图2b中, 各结点上的实时数据对象个数固定为30个, 而系统的总结点数目逐渐增加. 由图2可知, 在这两种设置下, 由SAP所得到的解均要优于SG. 此外, 随着结点个数或数据对象个数的增加, 两种方法下的系统负载都会随之增加.

图3给出的是系统结点个数为15, 各结点上的实时数据对象个数为50时的用户事务平均截止期错失率比较. 在每个结点上我们按泊松分布生成用户事务到达系统. 由图3可知, 在SAP下的平均截止期错失率要低于SG. 原因在于SAP下的系统负载要低于SG, 因此能留出更多的时间给用户事务执行. 此外, 随着事务到达率的提高, 两种方法下的平均截止期错失率都会增加. 通过修改相关的参数设置, 我们重复进行了上述实验, 得到的结果类似, 在此不再赘述.

图2 系统负载比较

图3 平均截止期错失率比较

4 结束语

本文研究信息物理融合系统中的本地以及共享实时数据的有效性维护问题. 已有的研究主要考虑如何保证数据及事务的服务质量. 与这些工作不同，本文考虑如何为更新与复制事务分派周期与截止期以最小化系统的总负载. 给出了两种解决此问题的方法，即基于次梯度优化的方法（SG）和基于模拟退火的方法（SAP）. 模拟实验的结果表明，相比SG，SAP生成的解在系统负载以及平均截止期错失率等指标上的表现更优. 在下一步的研究中，我们将考虑更新事务、复制事务与用户事务的联合调度问题.

[1]温景容，武穆清，宿景芳. 信息物理融合系统[J[. 自动化学报，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

湖南省自然科学基金资助项目(2015JJ6044)

白 天(1983- ), 男, 湖南岳阳人, 博士, 湖南理工学院计算机学院讲师. 主要研究方向: 实时数据库, 信息物理融合系统