具有“深度嵌入、泛在融合、智能感知和交互协同”等特点的信息物理融合系统(Cyber-Physical System, CPS)[1]高度融合一系列物理进程、嵌入式计算及网络通信,系统通过网络节点使软件进程与物理实体联系,应用网络交互技术使各节点连续物理系统的物理进程通过闭环反馈循环不断与离散计算系统的计算进程实时交互,同时,物理实体也利用系统硬件组件和网络节点感知、传输周边环境信息[2]。CPS系统能通过自身软硬件结构、装置分析物理动态变化,控制物理系统,执行误差修正等功能,该系统涵盖计算机网络、软件工程、控制工程、传感器、电子学等多领域学科,整个系统由大量传感器、物理硬件、软件系统及通信网络节点构成[3]。
为保证系统计算进程与物理实体行为深度交互,考虑软件与硬件相互作用的时间度量和表示的一致性,通过微分不变式计算连续时钟约束的收敛函数,使计算结果趋近离散模型的某一不动点,该点为严格收敛的时间信号函数的唯一不动点,函数不动点能确认所对应的系统实时交互行为的正确性与唯一性。采用超致密时间模型(Super Dense Time model, SDT)[4]拓展执行器输出事件驱动系统状态转移过程,以SDT表达事件实时性,将任务执行顺序用事件的时间轨迹描述,这样,在控制物理系统时能提供更严格的时间模型。
事件是一组计算变量、一条指令集合或输入/输出信号的表达。一个事件由执行器输出,事件本身含有的信息量由自身的不确定性决定,而一组输出事件的平均信息量表示执行器的平均不确定性,即执行器的信息熵(Information Entropy, IE)[5-6]。对比事件执行任务的执行周期和可执行时间构成执行器的数据服务质量(Quality of Data, QoD)[7-8]表达执行器驱动系统状态转移的时钟约束条件。
本文描述了CPS的基本系统状态转移过程,定义了计算过程的时钟约束,执行器输出事件本身的自信息量、执行器的信息熵及其数据质量,通过信息熵与数据质量构成的评价方程对执行器执行的任务进行价值评价,将评价结果反馈至执行器即可控制下一周期的输出事件更有效地驱动系统状态转移。
CPS系统中执行器输出事件执行任务所对应的时间序列对系统功能能否正常实现尤其重要,由此,基于执行器的信息熵和数据质量能在很大程度上影响系统性能和正确性。UC Berkeley的Ptolemy Ⅱ平台[9]可对包含时间和行为类型属性的组件交互过程进行验证,该平台支持对实时嵌入式异构系统执行分层设计[10],本文通过在Ptolemy Ⅱ的离散事件模型(Discrete-Event Modeling, DEM)[11-13]上加入基于信息熵与数据质量的执行器输出事件的价值评价策略——VE-IE & QoD(Value Evaluation-Information Entropy and Quality of Data), 验证基于此价值评价策略能提高系统性能与正确性。
1 系统状态转移模型基本的CPS系统一般由物理实体、计算平台和网络通信三个部分组成, 如图 1所示,物理实体通过传感器感知、收集环境信息,信息数据由网络节点传输至计算平台,经过嵌入式计算及数据融合后将控制信息、反馈信息或决策信息以命令代码的形式输出至驱动器,进而控制物理设备。
CPS基本模型可以看作一种面向执行器(Actor)的模型,所谓执行器就是通过端口执行并行处理、分享数据的组件。执行器并非简单地按照执行队列驱动系统状态转移,而是以一种输入/输出数据端口执行信号通信交流的系统部件。
定义1 设在六元组〈A, S, I, Q, T, E〉中,∃ai∈A表示执行器释放离散随机变量ai,以连续时钟约束T为指定周期,ai驱动系统状态si∈S进行转移任务,随机变量ai携带信息标签ai(I, Q)。其中:I称为自信息,表示ai本身所包含的信息量;Q称为数据质量,衡量ai能否有效控制系统状态转移。假设〈s, s′, a, I, Q, c〉∈E表示在随机事件a的控制下,状态由s→s′的转移路径,C为离散时钟集,c:=0表示在s→s′过程中时钟c重置为0,c∈C。如图 2所示,当满足时钟约束条件c < 3时,s′→s。
假设通过微分不变式计算连续时钟约束T的收敛函数,使T趋于离散模型C的某一不动点,保证在E中,(s→s′|a)能在时间度量和表示上与系统状态和行为保持一致。
若离散时钟集C以实数值表示,则一旦存在间隔释放的事件ai与ai+1且lim[C(ai+1)-C(ai)]=0,所有离散时间值ti无法用任意小的固定常数的倍数表示。
定义2 考虑引用具有偏序性质的超致密时间模型(SDT)[8]对E进行拓展,则时间轨迹t→t′可以表示(s→s′|a)。
令SDT中,t→t′为时间序列(l, n)∈(C= R+×N),其中l∈R+表示步长,n∈N表示步数。若t→t′,则说明t′>t,即(l′, n′)>(l, n),那么有l′>l或(l′=l∨n′>n)。
定理1 实时状态转移〈A, S, I, Q, T, E〉中,当且仅当s(l, n)通过a[I(l, n), Q(l, n)]控制时,(s→s′|a)通过实时标签a(I, Q)驱动执行任务。
证明 由定义1与定义2可知,执行器以离散时钟集C为周期连续释放离散随机变量a(I, Q),离散时间值ti∈C,若l为〈A, S, I, Q, T, E〉中时钟集C的最小公倍数,对于ti在有限转移次数nx内有nl=ti,n≤nx。那么∀ti∈C,∃l∈R+,使(n-1)l≤ti≤nl无限接近ti。所以时间序列(l, n)可以无限接近地代替离散时间值ti作为(s→s′|a)的时钟约束。
1.3 执行器的价值评价事件ai的自信息量I由ai的不确定性决定,认为执行器作为释放离散随机变量ai的信源,表征整个信源的不确定度需要由平均自信息量H决定。
定义3 设事件ai由执行器输出的概率为p(ai),则I(ai)=-lb(p(ai))=lb(1/p(ai))。
I(ai)在定义域[0,1]内是概率p(ai)的严格递减函数,p(a1) < p(a2)时,I(a1)>I(a2),说明事件发生的概率越小,其不确定性越大,a(I, Q)携带的自信息量越大。特别的,当p(ai)=0时,I(ai)→∞;当p(ai)=1时,I(ai)=0。
令随机变量X的所有取值及其对应的概率称为概率空间:
$ \left[\begin{gathered} \;\;A \hfill \\ P\left( A \right) \hfill \\ \end{gathered} \right] = \left[\begin{gathered} A = {a_0}\;\;A = {a_1}\;\;...\;\;A = {a_i} \hfill \\ p\left( {{a_0}} \right)\;\;\;\;p\left( {{a_1}} \right)\;\;...\;\;\;p\left( {{a_i}} \right) \hfill \\ \end{gathered} \right] $ |
其中
假设系统是在无噪声的情况下执行任务的,则接收执行器所收到的信息消除了发送执行器所释放的事件的不确定性,故发送执行器的不确定度可由平均自信息量表示。
定义4 将平均自信息量H称为执行器释放事件的信息熵,记H(A)。
$ H[p(A)] = {\text{E}}\{ p[I({a_j})\} =- \sum\limits_{j = 0}^i {\left[{p({a_j})\operatorname{lb} \left( {p({a_j})} \right)} \right]} $ |
定理2 信息熵H(A)有以下性质:
1) H[p(a0), p(a1), …, p(ai)]=H[p(a1), p(a0), …, p(ai)]=…=H[p(ai), p(ai-1), …, p(a0)]。即H(A)各释放的事件顺序改变不影响执行器总体信息熵值。
2) H[p(a)]=H[p(a0), p(a1), …, p(ai)]≥0。当且仅当执行器为确定信源时,等号成立。
证明 由定义4可知,I(a)在定义域[0,1]内是非负的,而H(A)是I(a)的数学期望,且a为离散随机变量,故H(A)必为非负。
3) ∃a, b∈A, 有:
$ \begin{gathered} \mathop {\lim }\limits_{b \to 0} {H_{i + 1}}[p({a_0}), p({a_1}), \cdots, p({a_i}), p(b)] = \hfill \\ {H_i}[p({a_0}), p({a_1}), \cdots, p({a_i})] \hfill \\ \end{gathered} $ |
即执行器多释放一个基本不会出现的小概率事件对信源的信息熵值不会产生改变。虽然事件b的自信息量很大,但信息熵是执行器的平均自信息量,b的比重小至可以忽略不计。
4) H[p(a0), p(a1), …, p(ai)]≤H(1/i, 1/i, …, 1/i)=lb(i)。即当各事件等概率释放时,H(A)最大。
证明 设∃bi∈A,若p(b)/p(a)=1时,有:
$ \begin{gathered} H[p({a_0}), p({a_1}), \cdots p({a_i})] + \sum\limits_{j = 0}^i {\left[{p({a_j})\operatorname{lb} \left( {p({b_j})} \right)} \right]} = \hfill \\ - \sum\limits_{j = 0}^i {\left[{p({a_j})\operatorname{lb} \left( {p({a_j})} \right)} \right]} + \sum\limits_{j = 0}^i {\left[{p({a_j})\operatorname{lb} \left( {p({b_j})} \right)} \right]} = \hfill \\ \sum\limits_{j = 0}^i {\left[{p\left( {{a_j}} \right){\text{lb}}\left( {p\left( {{b_j}} \right)/p\left( {{a_j}} \right)} \right) \leqslant } \right.} \hfill \\ \operatorname{lb} \left( {\sum\limits_{j = 0}^i {[p({a_j}) \times p({b_j})/p({a_j})]} } \right) = 0 \hfill \\ \end{gathered} $ |
若p(a)=p(b)=1/n时,有:
$ \begin{gathered} H[p({a_0}), p({a_2}), \cdots, p({a_i})] \leqslant - \sum\limits_{j = 0}^i {p({a_j})} \operatorname{lb} \left( {p({b_j})} \right) = \hfill \\ H\left( {1/i, 1/i, ..., 1/i} \right) = {\text{lb}}\left( i \right) \hfill \\ \end{gathered} $ |
5) 在定义域[0,1]内,H(A)的极大值为最大值。
证明 设p(b)=[p(b0), p(b1), …, p(bi)],且
故Δp(a)+(1-Δ)p(b)定义为新的概率分布。可以分析:
$ \begin{gathered} H[\Delta p(a) + (1-\Delta )p(b)] = - \sum\limits_{j = 0}^i [\Delta p(a) + \hfill \\ (1-\Delta )p(b)] \times \operatorname{lb} [\Delta p(a) + (1-\Delta )p(b)] = \hfill \\ - \{ \Delta \times \sum\limits_{j = 0}^i {p(a)\operatorname{lb} } [\Delta p(a) + (1-\Delta )p(b)]\} - \hfill \\ (1 - \Delta ) \times \{ \sum\limits_{j = 0}^i {p(b)} [\Delta p(a) + (1-\Delta )p(b)]\} \geqslant \hfill \\ - \Delta \times \{ \sum\limits_{j = 0}^i {\left[{p(a)\operatorname{lb} p(a)} \right]} \} - \hfill \\ (1 - \Delta ) \times \{ \sum\limits_{j = 0}^i {\left[{p(b)\operatorname{lb} p(b)} \right]} \} \geqslant \hfill \\ \Delta H[p(a)] + (1 - \Delta )H[p(b)] \hfill \\ \end{gathered} $ |
当p(a)≠p(b)时,有:
$ \begin{gathered} H[p({a_0}), p({a_1}), \cdots, p({a_i})] \leqslant - \sum\limits_{j = 0}^i {\left[{p(a)\operatorname{lb} p(b)} \right]} \hfill \\ H[\Delta p(a) + (1-\Delta )p(b)] > \hfill \\ \Delta H[p(a)] + (1 - \Delta )H[p(b)] \hfill \\ \end{gathered} $ |
故H(A)在定义域内为上凸函数,结合H(A)的极值性可知在定义域[0,1]内,H(A)的极大值为最大值。
1.4 与事件有依赖关系的执行器的信息冗余度若执行器输出事件序列长度为i,则事件序列的数学模型为i维随机变量序列A=a0, a1, …, ai,并且∀aj∈A与∃aj+1∈A存在依赖关系,即:
$ \begin{gathered} H[p(A)] = H[p({a_0})p({a_1}) \cdots p({a_i})] = H[p({a_0})] + \hfill \\ H[p({a_1})|p({a_0})] + H[p({a_2})|p({a_0})p({a_1})] + \cdots + \hfill \\ H[p({a_i})|p({a_0})p({a_1}) \cdots p({a_{i-1}})] \hfill \\ \end{gathered} $ |
设事件驱动系统状态转移概率p(St+1=sj+1|St=sj)是系统在t时刻处于sj状态的情况下,在t+1时刻转移至sj+1状态的概率。
对于输出事件有依赖关系的执行器,所释放的每个事件间的依赖关系也称为相关性。由定义3、定义4可知,当所有事件等概率输出时,执行器的信息熵最大,Hmax=lb(i)。即,只有一个输出事件时,H(A)≈Hmax;当事件序列越来越长时,每个事件的依赖关系越长,则执行器输出事件的平均信息量越小,导致执行器的信息熵H(A)越小。对于有相同信息量的不同执行器,依赖关系越大,输出的信息量越少,执行器内剩余信息越多。
定义5 设执行器的信息熵与具有相同事件集的最大熵的比值称为信息输出率μ:
$ \mu = H(A)/{H_{\max }} $ |
以信息冗余度χ表示执行器内剩余信息:
$ \chi = 1 - \mu = 1 - H(A)/{H_{\max }} = 1 - H(A)/\operatorname{lb} \left( i \right) $ |
为了使输出事件更高效地驱动系统状态转移,需要尽量降低执行器的信息冗余度。
为了使系统得到确定的控制、反馈或决策信息,在避免执行器的信息冗余度χ过高的同时,需要提高执行器的数据质量以保证输出事件能提供有效的信号或指令。
1.5 事件的有效性与执行时延执行器输出的事件在一定执行周期内对系统才是有效的,在此周期前提前驱动系统状态转移会非法抢占其他任务的资源,在截止期后执行任务会产生无效增益,浪费系统能耗,若事件执行时间已超过执行周期但还未到截止期,且下一任务还未开始,则此时该事件的有效性会随着执行时间逐渐降低,通过执行时延可度量其有效性降低的过程。
定义6 设执行器输出事件的释放时刻为tr,有效周期为TV,则事件a在时间t内能有效驱动系统状态转移的条件为:TV+tr≥t,其执行时延表示为:
$ {Z_i}(t)\left\{ \begin{gathered} 0, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;t \in [{t_r}, {t_r} + {T_V}] \hfill \\ t - ({t_r} + {T_V}), \;\;\;\;\;t > {t_r} + {T_V} \hfill \\ \end{gathered} \right. $ |
Z(t)∈[0, ∞),在下一任务开始时,该事件执行权被抢占,此时Z(t)=0。如图 3所示,t=[tr1, TV1]时,a0的Z1(t)=0;在t=(TV1, t1],Z1(t1)=t1-TV1;在t=(TV1, tr2),Z1(t)=tr2-TV1;当t=tr2时,Z2(t)=0,此时,a0被a1替换;之后t=[tr2, TV2]时,Z2(t)=0;当t=[TV2, tr3]时,Z2(t)=tr3-TV2。
系统在实时调度情况下是一种不确定因素很大的状态,在实时离散事件aj的有效周期TV内数据也可能是无效的,为了增大事件的有效周期,定义有效周期范围(TVmin, TVmax),其中TVmin与定义6所述的有效周期相同,TVmax则取决于下一释放事件周期。
∀aj+1∈A的释放时间为trj+1,则∃aj在执行时延内对系统状态转移的有效作用时间t∈[trj, trj+1+TV, jmax]。
aj由执行器释放后执行任务的有效时间为Zj(t)=trj+1+TV, jmax-trj,由于t∈[trj, TV, jmin]时,Zj(t)=0,故Zj(t)=trj+1+TV, jmax-TV, jmin。
定义7 用执行时延与事件的有效周期量化执行器的数据质量,记为事件的价值量,表示为:
$ Q(t) = 1 - Z(t)/\left( {T_V^{\max } - T_V^{\min }} \right) > 0 $ |
定理3 0 < Q(t)≤1,则事件仍是有价值的,若Z(t)>TVmax-TVmin,则该事件已失效。
证明 如图 4,由定义6可知,t∈[tr, tr+TV]时,Z(t)=0,Q(t)=1;当t>TVmax而下一事件未释放时,Z(t)>TVmax-TVmin,Q(t) < 0,与命题相悖; 若在t=TVmax前释放下一事件,则0 < Q(t) < 1,仍对系统有价值,故在需满足Z(t) < TVmax-TVmin的前提下有0 < Q(t)≤1。
本章结合执行器的冗余度与事件的数据质量,分析执行器执行任务的效益,描述一种基于价值评价的调度策略。
2.1 价值评价调度策略定义7 对嵌入式控制状态转移的执行器进行价值评价,记为V。
$ {V_A}(t) = \alpha (k - n)H(A) + \beta Q(t) $ |
其中:α,β为价值评价参量,α, β≥1;(k-n)是测得事件信息熵的时间信号周期。
$ \begin{gathered} H(A) = \operatorname{lb} \left( i \right) \times (1 - \chi ) = {\text{E}}\{ p[I({a_j})\} = \hfill \\ \;\;\;\;\;\;\;\;\;\;\;- \sum\limits_{j = 0}^i {\left[{p({a_j})\operatorname{lb} \left( {p({a_j})} \right)} \right]} \hfill \\ Q(t) = 1 - \left( {{t_r} + T_V^{\max } - T_V^{\min }} \right)/\left( {T_V^{\max } - T_V^{\min }} \right) \hfill \\ \end{gathered} $ |
令f1=α(k-n)H(A),f2=βQ(t),则
在〈A, S, I, Q, T, E〉中,为保证最有效地执行〈s, s′, a, I, Q, c〉∈E过程,需要控制执行器以最高的价值评价调度事件,对时钟约束要求更高的执行器可适当提高β参量,同样,对信息量约束更高的执行器可提高α参量。
假设需要执行任务的执行器为执行器A与执行器B,且A与B不能并行执行,则所述的价值评价调度策略状态转移过程如图 5所示,面对不同情况的策略选择如下。
情况1 若[(d(A)-k(B))≥(k(A)-n(A))]∪[(d(B)-k(A))≥(k(B)-n(B))]。
策略1 不论先执行A还是B,都能保证另一方能顺序完成任务,为了节约执行时间,对比A与B的数据质量Q,选择执行周期k更短的一方优先执行。
情况2 若[(d(B)-k(A)) < (k(B)-n(B))]∪[(d(A)-k(B))≥(k(A)-n(A))]。
策略2 明显的,先执行A后执行B可以避免A与B的冲突,同时保证A与B都能在截止期前完成任务,若此时正在执行B,系统可适当增大A的β值,使A抢占处理器。
情况3 若[(d(B)-k(A)) < (k(B)-n(B))]∪[(d(A)-k(B)) < (k(A)-n(A))]。
策略3 执行A还是B,都不能保证另一方能顺利完成任务,则比较V(A)与V(B)中f1的大小,以执行器的信息熵决定首先执行A或B。
2.2 建立价值评价调度策略仿真模型为了验证2.1节描述的调度能提高系统性能与正确性,本文利用开源嵌入式系统研究与开发平台PtolemyⅡ建立离散事件模型(DEM),在模型中加入基于CPS执行器输出事件价值评价调度策略,并与传统常用的最早截止时间优先(Earliest Deadline First, EDF)算法、基于信息熵的IE* (Information Entropy*)调度策略进行比较。PtolemyⅡ平台是由美国加州大学伯克利分校的Edward Ashford Lee教授领导的团队所开发的。
本文实验均在处理器为1.6 GHz双核Intel Core i5,RAM为8.00 GB的MacBook Air PC上运行,使用系统为macOS Sierra,建模平台版本为PtolemyⅡ10.0.1 Mac OS X版。
系统对比模型如图 6所示,服务器执行器Serve的服务时间由随机数发生器ColtExponential执行器随机产生,ColtExponential的参数λ为1.0/averageServiceTime,其中:参数averageServiceTime的初始值为0.1,随机数种子seed为0 L。模型利用参数Random模拟事件输出概率,在有限状态机(Finite State Machine, FSM)模型中,设状态A为初始状态,自身的状态转移为一种默认的转移模式(A default transition),其中set:Random=10。FSM模型输入端为一种随机事件发生器Bernoulli执行器,该发生器在随机时间产生触发事件,其trueProbability=0.1。当FSM模型端口被触发时,状态A转移至状态B,并且set:Random=0,在B状态下,自身的状态转移为一种history transition,条件guard:Random < 10,并set:Random=Random+x,其中:x为0~10的随机数,当guard:Random≥10时,状态B再转移至状态A,此时set:Random=10。
模型中,参数Random的初始值为10,执行器输出事件由组合执行器EventGenerator产生,在组合执行器内,初始事件由PoissonClock执行器在随机时间触发,该执行器参数seed=0 L,meanTime=1.0/60.0,values={Random},当一个事件产生时,通过CurrentTime执行器记录释放时间,并将Random值与释放时间tr同时记录在RecordAssembler执行器内。如图 6所示,Swich执行器为执行器输出事件的价值评价调度策略,CompositeActor3与Swich组合成一个反馈模型,通过2.1节的调度策略判断价值评价高的事件优先执行,而价值评价相对较低的返回CompositeActor执行器重新等待执行。Swich2执行器与其前部相连接的执行器构成基于EDF算法的调度模型[14-16],下方5个执行器组合成基于IE*调度策略[17-18]的调度模型。整个对比模型的时间参量由DE Director负责,本文模型使用的模型时间(Model Time)统筹调度,故在DE Director中,startTime=0.0,stopTime=100.0,而参数stopWhenQueueIsEmpty =ture,synchronizeToRealTime=false。
2.3 仿真结果分析本文在PtolemyⅡ平台上建立了2.2节所述的离散事件执行器对比模型,模型内随机数执行器的种子参数都为默认值seed=0 L。模型中,Display执行器可以显示模型运行情况,由EventGenerator产生的事件集通过VE-IE & QoD调度策略的Swich执行器后,结果输出在VE-IE & QoD的Display1执行器,而作为对比,EDF结果输出在Display2执行器上,IE*结果输出在Dispay3执行器上,事件集从释放到执行完成,对系统产生的价值评价由TimedScope显示,而事件集每个事件的执行时间则由HistogramPlotter显示。
对离散事件对比模型做30次重复实验,得到30组对比数据,随机取出5(Ⅰ~Ⅴ)组,在同一条件下系统不同模型的运行时间,内存使用量及空闲内存如表 1所示。VE-IE & QoD(Ⅴ)调度策略的平均执行时间为690.6 ms,EDF(E)算法的平均执行时间为822.4 ms,IE*调度策略的平均执行时间为876.2 ms,VE-IE & QoD调度策略的平均运行速度比EDF算法提高了16.03%,比IE*(Ⅰ)调度策略提高了21.18%;平均内存使用效率上,VE-IE & QoD调度策略比EDF算法提高了17.91%,比IE*调度策略提高了22.79%。
PtolemyⅡ中TimedScope和HistogramPlotter显示的数据生成曲线图,在重复的30次实验中,随机抽取2次的结果,其价值评价随时间变化如图 7所示。由图 7可以明显看出,VE-IE & QoD策略与EDF、IE*策略相比,价值评价略高,并且在执行过程中,EDF与VE-IE & QoD调度策略的事件集价值评价稳定上升,由确定的初始值增长至确定的终值,而IE*策略的事件集在执行过程中系统颠簸现象严重,在指定的执行过程内,并不能确切地知道某个固定的价值量。
相对应的执行器输出事件的执行时间如图 8所示,分析执行器输出事件集内每个事件的执行时间,由于事件value与释放时间tr是在DE Director控制下随机产生,所以每个事件的具体执行时间无法一致,但由图 8可知,执行器在模型时间开始-结束为0.0~100.0 ms内,所输出的事件集包含90个随机事件,并且事件在用VE-IE & QoD策略时的执行时间基本都比用EDF、IE*策略时低。由于EDF算法更加强调时序性,虽然IE*策略的价值评价偶尔高于EDF算法,但是在针对执行时间这一比较上,EDF算法基本比IE*策略用时更少。
根据上述分析可以得出,在同一条件下随机产生的事件通过由信息熵与数据质量描述的一种基于CPS执行器输出事件的价值评价调度策略可以有效降低各个事件的执行时间,提高整个事件集的平均运行速度,在执行过程中,系统价值评价稳定上升,证明该调度策略能在一定程度上提高系统性能及其正确性。
3 结语本文首先定义了计算过程的时钟约束,执行器输出事件本身的自信息量、执行器的信息熵及其数据质量,然后基于CPS的基本系统状态转移过程,通过信息熵与数据质量描述一种评价方程对执行器执行的任务进行价值评价,最后利用Ptolemy Ⅱ平台可对包含时间和行为类型属性的组件交互过程进行仿真验证。在Ptolemy Ⅱ的离散事件模型上加入由信息熵与数据质量的执行器输出事件的VE-IE & QoD调度策略,利用执行器模拟输出事件的调度策略,组合反馈模型,实现模型对调度策略的应用,通过建立仿真模型,将VE-IE & QoD调度策略与传统EDF调度算法、基于信息熵的IE*调度策略进行比较。仿真结果表明,VE-IE & QoD调度策略的平均运行速度比EDF算法提高了16.03%,比IE*调度策略提高了21.18%;平均内存使用效率上,VE-IE & QoD调度策略比EDF算法提高了17.91%,比IE*调度策略提高了22.79%,并且VE-IE & QoD策略的价值评价略高。本文所述建模方法与执行过程略为繁琐,今后可将离散事件模型系统调度性问题简化为有限状态机的可达性问题进行分析,这样可提高系统分析效率。
[1] | 李仁发, 谢勇, 李蕊, 等. 信息-物理融合系统若干关键问题综述[J]. 计算机研究与发展, 2012, 49(6): 1149-1161. ( LI R F, XIE Y, LI R, et al. Survey of cyber-physical systems[J]. Journal of Computer Research and Development, 2012, 49(6): 1149-1161. ) |
[2] | LEE E A.Computing foundations and practice for cyber-physical system[R]. Berkeley, CA:University of California, 2007. |
[3] | AKKAYA I, DERLER P, EMOTO S, et al. Systems engineering for industrial cyber-physical systems using aspects[J]. Proceedings of the IEEE, 2016, 104(5): 997-1012. doi: 10.1109/JPROC.2015.2512265 |
[4] | ALUR R, DILL D L. A theory of timed automata[J]. Theoretical Computer Science, 1994, 126(2): 183-235. doi: 10.1016/0304-3975(94)90010-8 |
[5] | 赵兴旺, 梁吉业. 一种基于信息熵的混合数据属性加权聚类算法[J]. 计算机研究与发展, 2016, 53(5): 1018-1028. ( ZHAO X W, LIANG J Y. An attribute weighted clustering algorithm for mixed data based on information entropy[J]. Journal of Computer Research and Development, 2016, 53(5): 1018-1028. doi: 10.7544/issn1000-1239.2016.20150131 ) |
[6] | 刘江冬, 梁刚, 冯程, 等. 基于信息熵和时效性的协同过滤推荐[J]. 计算机应用, 2016, 36(9): 2531-2534. ( LIU J D, LIANG G, FENG C, et al. Collaborative filtering recommendation based on entropy and timeliness[J]. Journal of Computer Applications, 2016, 36(9): 2531-2534. doi: 10.11772/j.issn.1001-9081.2016.09.2531 ) |
[7] | 黄姝娟, 朱怡安, 李兵哲, 等. 具有依赖关系的周期任务实时调度方法[J]. 计算机学报, 2015, 38(5): 999-1006. ( HUANG S J, ZHU Y A, LI B Z, et al. Real-time scheduling method for dependency period tasks[J]. Chinese Journal of Computers, 2015, 38(5): 999-1006. ) |
[8] | ZHOU Y, KANG K D. Deadline assignment and feedback control for differentiated real-time data services[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(12): 3245-3257. doi: 10.1109/TKDE.2015.2441725 |
[9] | ZHAO Y, XIONG Y H, LEE E A, et al. The design and application of structured types in ptolemy Ⅱ, TR UCB/EECS-2007-21[R]. Berkeley, CA:University of California, 2007. |
[10] | 徐洪智, 李仁发, 曾理宁. 基于Ptolemy的信息物理融合系统建模与仿真[J]. 系统仿真学报, 2014, 26(8): 1633-1638. ( XU H Z, LI R F, ZENG L N. Modeling and simulation of cyber-physical system based on Ptolemy[J]. Journal of System Simulation, 2014, 26(8): 1633-1638. ) |
[11] | EIDSON J C, LEE E A, MATIC S, et al. Distributed real-time software for cyber-physical systems[J]. Proceedings of the IEEE, 2012, 100(1): 45-59. doi: 10.1109/JPROC.2011.2161237 |
[12] | DERLER P, JOHN E, STUART G, et al. Deterministic execution of ptides programs, TR UCB/EECS-2013-65[R]. Berkeley, CA:University of California, 2013. |
[13] | TRIPAKIS S, DAI B, GEILEN M, et al. Compositionality in synchronous data flow:modular code generation from hierarchical SDF graphs[J]. ACM Transactions in Embedded Computing Systems, 2013, 12(3): Article No. 83. |
[14] | 陈瑶, 李峭, 鲁俊, 等. 改进的多处理器混合关键性系统可调性分析[J]. 北京航空航天大学学报, 2016, 42(9): 1918-1926. ( CHEN Y, LI Q, LU J, et al. Improved schedulability analysis for multiprocessor mixed-criticality systems[J]. Journal of Beijing University of Aeronautics and Astronautics, 2016, 42(9): 1918-1926. ) |
[15] | 张杰, 阳富民, 卢炎生, 等. EDF统一调度硬实时周期任务和偶发任务的可调度性判定算法[J]. 小型微型计算机系统, 2009, 30(12): 2383-2388. ( ZHANG J, YANG F M, LU Y S, et al. Schedulability test of scheduling hard real-time period and sporadic tasks unified with EDF policy[J]. Journal of Chinese Computer Systems, 2009, 30(12): 2383-2388. ) |
[16] | 袁暋, 檀明, 周晶晶. EDF调度算法可调度性分析方法的改进研究[J]. 计算机应用研究, 2013, 30(8): 2429-2431. ( YUAN M, TAN M, ZHOU J J. Research on improved schdulability analyzing method for tasks scheduled under EDF[J]. Application Research of Computers, 2013, 30(8): 2429-2431. ) |
[17] | 张娟, 夏忠婷. 基于信息熵的自适应资源调度算法[J]. 现代雷达, 2015, 37(8): 33-36. ( ZHANG J, XIA Z T. An adaptive resource scheduling searching method based on information entropy[J]. Modern Radar, 2015, 37(8): 33-36. ) |
[18] | 饶运清, EFSTATHIOUJ. 基于信息熵的制造系统复杂性测度及其在调度中的应用[J]. 机械工程学报, 2006, 42(7): 8-13. ( RAO Y Q, EFSTATHIOU J. Entropy-based measurement of manufacturing system complexity and its application in scheduling[J]. Chinese Journal of Mechanical Engineering, 2006, 42(7): 8-13. ) |