基于有效度函数的传感器事务调度策略*

白 天,李国徽,范 波

(1.湖南理工学院计算机学院，湖南 岳阳 414000 ；2.华中科技大学计算机科学与技术学院，湖北 武汉 430074)

基于有效度函数的传感器事务调度策略*

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

(1.湖南理工学院计算机学院，湖南 岳阳 414000 ；2.华中科技大学计算机科学与技术学院，湖北 武汉 430074)

针对数据的绝对一致性概念只能够描述二元数据状态的问题，提出了数据有效度函数的概念。给出了两种基于有效度函数的传感器事务调度策略VM-DS与VM-SN。策略通过合理的设置数据对象的有效时间段长度及事务的执行频率来最大化系统中数据的有效程度。通过实验对两种策略的性能进行了对比分析。结果表明，VM-SN在平均数据有效度、有效度负载比等性能指标上均优于VM-DS，能够更好的满足系统的实时性要求。

信息物理融合系统；传感器事务；有效度函数

信息物理融合系统(cyber physical system, CPS)是将感控、计算和通信能力深度嵌入物理过程后形成的网络化智能系统[1-2]。在CPS的相关研究中，一个重要的领域是实时数据对象的有效性维护。实时数据对象描述了外部物理实体的当前状态。与传统数据对象不同的是，实时数据对象的值具有时效性。访问无效或过度陈旧的数据值会导致错误的控制决策，给系统带来危害。

已有的研究工作基本上使用数据的绝对一致性定义作为数据有效性的定义[3-4]。在此定义下，系统中的每个数据对象都被赋予一个时态有效期。数据对象的当前值在有效期内是绝对一致(有效)的，超过期限后，数据值将失效。典型的单处理器数据一致性维护算法包括More-Less算法(ML)、DS-FP算法与基于动态优先级的算法。ML使用周期性事务模型与截止期单调算法(DM)[4-5]，其通过合理分派事务的周期与相对截止期来满足事务集的可调度性与数据的绝对一致性。DS-FP采用非周期性事务模型[6-8]，其在满足绝对一致性的前提下通过适当调整实例的开始时间来降低更新负载。基于动态优先级的算法主要解决早期截止期优先策略(EDF)下的事务周期与截止期分派问题[9-10]。文献[11]提出了用于多处理器平台的事务分派策略，在单个处理器上事务的调度执行采用EDF算法。以上研究只考虑如何确保实时数据对象本身的绝对一致性，文献[12]和[13]研究了如何通过并发控制及串行化顺序调整来确保用户事务所读取的实时数据满足绝对以及相对一致性。

绝对一致性定义的主要不足在于其仅能够说明数据在某一时刻是处于有效状态还是无效状态，而不能具体给出数据的有效程度是多少以及有效程度随时间变化的情况。在支持多级服务质量的系统中，服务质量级别通常会基于数据的有效程度来定义。级别越低，数据的有效程度就越低，对应的事务更新频率也会越低。这样系统在运行时可以根据当前的负载及用户对数据有效性的要求进行服务质量级别的动态调整。数据的绝对一致性定义无法用来构建这类系统的服务质量模型，为此本文提出数据有效度函数的概念。在此基础上给出两种传感器事务调度策略以实现数据有效程度的最大化。

1 数据有效度函数

图1 典型的有效度函数Fig.1 Typical validity functions

定义hi(t)的方法有多种。一种方法是预先确定n个有效级别，级别j(1≤j≤n)对应数据值与外部状态值的差值dj。d1=0。若i≤j，则di≤dj。级别j的有效程度vj设置为(dn-dj)/dn。根据外部状态值的变化率可以得到级别j对应的时间段Lj。由此可以得到hi(t)如下：

在现有的绝对一致性定义下，传感器事务调度的目标是确保数据在任何时刻都是完全有效的。而在有效度函数的定义下，传感器事务调度的目标则是尽量提高数据的有效程度。图2给出了一般化的调度策略下，使用图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实例的执行而交替的下降和上升。

图2 数据有效程度的变化Fig.2 Evolution of data validity degree

给定开始于ts且长度为T的观察窗口，数据集X在窗口内的平均有效程度V(X)由式(1)给出。为了使用户访问到的数据尽可能的有效，调度策略应使得V(X)的值尽可能的大。这里假定数据对象的重要程度是相同的。例如数据具有相同的访问频率。若不相同，可以在V(X)的定义中加上权重系数。

(1)

2 传感器事务调度策略

根据有效度函数的定义，传感器事务调度策略需要确定每个数据对象的有效时间段，事务的执行频率与事务的调度算法，以最大化V(X)。在单处理器实时任务调度算法中，EDF算法具有最优的可调度性，故本文使用EDF来调度事务。此外在CPS中除了传感器事务之外,通常还存在对外部过程进行控制的事务，使用EDF易于实现两种类型事务的联合调度。

2.1 VM-DS策略

(2)

问题满足以下的约束条件：

(3)

(4)

算法1Llb的计算

2)若Llb不满足式(3)，则Γ不可调度，返回失败;

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 若实时数据对象Xi的有效度函数hi(t)为kit+bi(ki<0)，且满足

与

则式(2)的最优解为：

证明 根据式(2)及hi(t)的定义可得：

(5)

设置ui与vi为零，则由上述条件可求得：

根据文献[14]，事务在时间区间[0,t)内的最大累计执行时间需求可表示为：

(6)

事务集可被EDF调度的充要条件可表示为：

(7)

若采用后者，则设置：

具有很好的防水性能，这是保障路面不会受到路表或外界环境中的水的影响而造成路面整体性、强度和刚度下降的主要因素。

令P(τi,tc)表示在tc时刻可以使dbf(τi,tc)减小的调整策略集合。若不存在这样的策略，则P(τi,tc)=Ø。P(τi,tc)中的第j个策略简记为pi,j。使用pi,j后dbf(τi,tc)的减小量记为Δdbf(τi,tc,pi,j)。Xi的有效程度可表示为：

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

令Δdbf(Γ,tc)表示dbf(Γ,tc)与tc的差值。需要确定每个事务的调整策略，使得Δdbf(Γ,tc)不大于零且V(X)的增加量最小。令xi,j表示pi,j被选中，则有：

(8)

式(8)满足以下的约束条件：

(9)

(10)

算法2给出了Llb和F的求解过程。算法判断式(7)是否在测试范围内的每个时间点上成立。若不成立，则通过求解式(8)得到Llb与F的更新量ΔLlb与ΔF，并据此更新Δ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 实验评价

本节给出两种策略的实验评价。主要评价指标为平均数据有效度和有效度负载比。平均数据有效度由式(1)直接计算得到。有效度负载比定义为平均数据有效度与事务更新负载的比值。此外，实验还比较不同策略下的事务有效度，定义为用户事务所访问数据的有效程度的平均值。

表1 实验参数及设置

图3给出了两种策略的平均数据有效度比较。由图可知，在不同的事务数目下，VM-SN的平均数据有效度均高于VM-DS。两者的差异随着事务数目的增加而增加。原因在于VM-DS将事务的执行频率简单设置为所允许的最低执行频率的两倍，且使用了充分条件来寻找有效时间段，这使得许多满足条件的更优的解被VM-DS丢弃。VM-SN不将执行频率与有效时间段简单关联，而是通过充要条件来寻找两者的取值，这极大的提高了解的质量。

图3 平均数据有效度的比较Fig.3 Average data validity degree comparison

图4给出了不同的事务数目下两种策略的有效度负载比。在绝对一致性定义下，评价传感器事务调度策略的一个重要指标是策略产生的更新负载。在有效度函数的定义下，不同策略得到的有效时间段不同，直接比较更新负载不再合适。而有效度负载比则能较好的反映数据有效度与系统负载之间的相对关系。由图4可知，VM-SN的有效度负载比在不同情况下均高于VM-DS。这说明在保证较高数据有效度的前提下，VM-SN所产生的负载也是较为合理的。这有利于系统中其它类型事务的实时性维护。

图4 有效度负载比的比较Fig.4 Ratio of validity degree to workload comparison

图5给出了用户事务的到达率为12事务/s时的事务有效度比较。由于VM-SN的平均数据有效度高于VM-DS，使用VM-SN时用户事务在任何时刻访问到更高有效度的数据的可能性也更大。这使得VM-SN下的用户事务有效度高于VM-DS。此外随着事务数目的增加，两者的差异也会增大。在其他的参数设置下我们重复进行了上述的实验，得到了类似的结果，在此不再给出。

图5 事务有效度的比较 (12事务/s)Fig.5 Transaction validity degree comparison (12 trans /s)

4 结 语

如何维护实时数据对象的有效性是CPS研究中的一个重要问题。提出了数据有效度函数的概念。传统的数据绝对一致性定义可视为数据有效度函数的一个特例。给出了一种有效度函数的定义方法。在有效度函数的定义下，传感器事务调度的目标是尽量提高系统中数据的有效程度。提出了两种用于实现此目标的传感器事务调度策略VM-DS与VM-SN。VM-DS将事务的采样频率固定设置为其最低允许采样频率的两倍，并使用EDF可调度的充分条件来求出事务的有效时间段。而VM-SN则是利用EDF可调度的充要条件来同时确定事务的采样频率及有效时间段。实验分析表明，相比VM-DS，VM-SN能够确保更高的平均数据有效度，其产生的更新负载相对于其提供的平均数据有效度也更低。文中提出的调度策略只能用于单处理器平台。下一步的研究工作是设计基于有效度函数的多处理器事务调度策略。

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

[2] 温景容, 武穆清, 宿景芳. 信息物理融合系统[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] 刘波, 范士明, 刘华. 一种动态调整串行化顺序的实时并发控制协议[J].小型微型计算机系统, 2013, 34(3):443-449.

[13] 肖迎元, 刘云生. 确保时态一致性的实时并发控制协议[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年生),男;研究方向：实时数据库、信息物理融合系统；E-mail:baitiannobel@163.com

TP311

A

0529-6579(2016)02-0042-06