根据系统的执行流程,基于设备的当前状态评估其能耗值.当设备周围没有事件发生时,则将部分模块置于空闲状态,即,设备的能耗比较低.按照一定的规则将这些设备上的处理操作转移到可替换设备,原设备调到低消耗状态(休眠状态).假设设备ae完成任务tk一次成功运行所需执行的操作序列称为设备ae的路径,如射频卡为了完成任务tk_i,2的路径为op₂,op₃.由于设备通常是由某个初始操作开始,运行到某个终止操作结束,根据完成功能的不同,有些设备可能有多个初始操作和多个终止操作.由于设备初始和终止时的特性是系统关心的内容,在具有多个初始操作的设备中,通过添加启动操作ini将多个初始操作转化为一个唯一的初始操作ini.同理,引入正常结束end操作和超时结束fo操作.此外,为了统一描述设备的执行路径,在只有1个初始操作的设备中也添加一个ini操作表示设备的开始运行.因此,设备的一次成功运行表示为执行了一个以ini操作开始、以end或fo操作为结束的操作序列,即,设备执行的一个路径.ini,end,fo操作在设备实际运行描述中是不存在的,它所执行的操作是一个空操作,本文规定这些操作的能耗和运行时间为0.由于设备完成不同任务所调用的操作不同,对应的能耗也会有差异.此外,设备完成同一个任务时,其选择路径不唯一,因此其能耗也会不同.设设备ae_i完成任务集TK_j的路径集合为Lat(ae_i,TK_j)={Lat₁,Lat₂,….,Lat_n},其中,路径Lat_k={op_k,1,op_k,2,…,op_k,f}.路径Lat_i的能耗值为

设备ae_i完成任务集TK_j的平均能耗值为

如,射频卡为了完成任务tk_i,2的能耗为7.

定义2. 设是DES需求模型,ae_i,ae_j∈AE,ae_i,ae_j∈AE是系统两个不同的设备,ext(ae_i,ae_j)为两个设备的 距离.

两个设备是无关的,是指其作用集不相交;两个设备完全覆盖,则指设备的作用集之间存在属于关系.在实际运行中,虽然有些设备具有相同的功能,但是由于其地理位置不同,导致执行的能耗也会有所差异.因此,在定义覆盖和等同关系时,不仅需要考虑设备的作用集,而且还需要考虑设备的间隔距离.分析矿井监控系统可以发现,射频卡间是无关的.设人员定位的距离阈值为20,发现读卡器ae^r₂的作用集:

且ext(ae^r₂,ae^r₃)=20,所以,ae^r₃▽ae^r₂.进一步计算两个设备的平均能耗值,可知ae^r₃完全覆盖ae^r₂同理,可以分析其余设备间的关系.

DES的能耗需求为=(AE,AG,AL,RE,TW,RA,OP,D),初始化当前设备集AE_now=AE,当前任务集TK_now=TK,启动设备集AE_ac=∅,设备ae的执行任务集为TK(ae)=∅,则其启动策略是:

(1) 候选设备集计算:ae_i∈AE_now,若∃ae_j使得ae_j在任务集TK下完全覆盖ae_i,则AE_now=AE_now-ae_i.

(2) 启动设备集计算:ae_i∈AE_now,若VW(ae_i,TK_now)=max{VW(ae_j,TK_now)},ae_j∈AE_now,则AE_ac=AE_ac∪ae_i, AE_now=AE_now-ae_i,TK_now=TK_now-VW(ae_i,TK_now),TK(ae_i)=VW(ae_i,TK_now).若TK_now≠∅,则继续转步骤(2);若TK_now=∅,则转步骤(3).

(3) 输出AE_ac,TK(ae_i).进一步根据任务间关系增加相应的连接件,输出启动连接件集合La_ac.

利用启动策略可以计算出系统的启动设备集合,其原理是,根据实际设备的能耗随着执行任务数的增加不呈线性增加.因此,可以充分使用设备完成多个任务,减少系统的启动设备数,从而减低系统的整体能耗.Agent根据系统需要完成的功能,利用启动策略动态计算启动设备集和连接件集合.

由于DES整体有时限要求,但没有细化到各个设备,因此有必要分析设备的局部时限要求,以降低设备的供应电压.下面根据关键任务集提出调整策略,并计算设备的局部时限和动态供电电压.

设任务tk_i在设备ae_g中有操作集合op(tk_i,ae_g)={op₁,op₂,…,op_k},则关键任务集的计算方法为:

则KC=KC∪tk_i,temp=temp-tempc_i,若temp≠∅,则转步骤②;否则,输出KC.

关键任务集就是DES中运行时间最长的一条执行路径,下面基于此调整任务的运行时间和供电电压.设关键任务集为KC,tk_i由设备ae_g执行,具体调整策略为:

利用调整策略,Agent可以调整设备的动态电压以适应任务的运行,在保证时限的前提下,降低系统的总体能耗.进一步地,可以按照比例计算各个操作的运行时间etp'.

Petri网作为一种图形化建模工具和一种具有丰富数学基础的形式化模型,可以广泛应用于描述和研究并发、异步和分布式特征的系统,因此,Petri非常适合描述分布式嵌入这种松耦合的系统.下面介绍一些系统运行的基本概念,其余的概念见文献^[4].

定义3. 十一元组Ω=(PN,IO,D,A_T,A_F,l,G,TI,TA,PI,PA)称作分布式嵌入式能耗网(distributed embedded net,简称DE-Net),其中,

(1) PN=(P,T,F)是一个基本Petri网,其中,P,T,F分别表示库所、变迁和弧的有限集,且两两不相交;

(2) IO⊂P是一类特殊的库所,称为Ω的接口,用虚线圆圈表示;

(3) D为非空有限的个体集,规定f_D,f_S分别为D上给定的公式集和符号集;

(4) A_T:T→f_D,对于t∈T,A_T(t)中的自由变量必须是以t为一端的有向弧上自由变量;

(5) A_F:F→f_S,若(p,t)∈F或(t,p)∈F,则A_F(p,t)或A_F(t,p)为n元符号集,缺省为空;

(6) AT:T→N^*×N^*是变迁的属性函数,t_i∈T,AT(t_i)=(λ_i,en_i)描述t_i的优先级和单位能耗,默认值为0.本文假设:λ_i越小,变迁t_i的优先级越大;

(7) Ct:P→N^*×N^*是库所的属性函数,描述了库所的延迟时间和能耗,默认为0;

(8) M₀:P→f_S是Ω的初始标识,p∈P,M₀(p)不含任何自由变量;

(9) Γ={Γ_i|i∈N^*}是DE-Net的有限集,其中每个组件称为Ω的一个页面;

(10) TI⊂T是替代节点的集合,其中每个页面对应一个替代节点,用实心矩形表示;PI⊂P是端口节点的集合,端口节点描述替代节点的输入和输出库所,用实心圆圈表示;

(11) TA:TI→Γ是一个页分配函数,即,为每个替代节点分配一个页面;PA是端口映射函数,主要是把端口节点映射到对应页面的输入和输出接口.

DE-Net模型是对确定的时间延迟进行建模,当变迁的触发发生冲突时,以竞争来选择触发的变迁,将库所P_i的延迟时间记作ct_i.DE-Net模型主要是对设备、连接件、Agent或整个分布式嵌入式系统进行建模,其中,库所、变迁和接口分别描述组件的所处位置、可能操作和输入输出参数.个体集D主要用来描述DES中的资源,本文将DES的资源和信息抽象成个体d_i=(it,i,RW_i),其中,it∈{e,g,l,d}说明该个体所描述的对象,e,g,l,d分别表示可用设备集、Agent集、连接件、数据包.i表示个体的标记,如,设备ae_j在设备集AE中所处位置为j.当it为d时,RW_i表示数据包的内容;否则,RW_i为描述对象的属性,如能耗、电压.设k#(d_i)表示个体d_i中的第k个组件,而把系统中的普通数据包统一抽象成个体.如果没有无特殊说明,则DE-Net模型中出现的个体均为.因为设备没有下一层组件,所以其模型的Γ,TI,TA,PI,PA均为空.而Agent模型中每个页面代表一个设备,且其接口非空;而分布式嵌入式系统中每个页面表征一个Agent.任意x∈(P∪T),集合^·x={y|y∈(P∪T)∧(y,x)∈F}和x^·={y|y∈(P∪T)∧(x,y)∈F}分别对应于x的输入和输出;任意t_i∈T,将变迁t_i的输入/输出弧(A_F(t_i,p)/A_F(p,t_i))以及A_T(t_i)中出现的自由变量集记作FV(t_i).

图 2描述了一个简单的DE-Net模型Ω₁,该模型中有一个页面(虚线框).Ω₁中的替代节点T₄分配给页面Ta,也就是说,该节点描述了页面Ta的内部操作.相应地,端口节点P₄,P₆分别映射为页面Ta的输入和输出接口P₈,P₉.

Fig. 2 DE-Net model W1图 2 DE-Net模型W1

在各库所中,个体的分布状况称为DE-Net模型的标识,记作M.p∈P,M(p)={(d_i,q_i),…,(d_k,q_k)},其中,{d_i,d_j,…, d_k}为标识M下库所p中存放的个体集,而{q_i,q_j,…,q_k}为相应的数量.

定义4. 设Ω为DE-Net模型,在q时刻,模型处于标识M.设p_i∈P,在标识M下库所p_i有j个个体,d^k_i为p_i的第k个个体(0<k<j),ξ_k为个体d^k_i的产生时刻,ct_i为库所p_i的延迟时间,称向量:

为库所p_i的所有个体等待时间,其中,.

称为个体d^k_i的等待时间,若库所p_i中只有1个个体,则直接用TS(p_i)表示.=m表示系统还要再等m时间单位才可以使用个体表示该个体可用.为了减少分析的复杂度,本文假设:若库存的时间延迟大于0,则该库所中只存放同一种个体.记TS(M,θ)为θ时刻标识M下库所的等待时间集合.如Ω₁在全局时间1时,库所P₂,P₁₀,P₁₁中分别有个体d₁,d₂,d₃,且TS(P₂)=TS(d₁)=0,TS(P₁₀)=1,TS(P₁₁)=3.记M^a为M中可用的个体分布,而M^u标记M中不可用的个体分布.|M^a(P_i)|=k表示在库所P_i中有且仅有k个个体的等待时间为0, |M^u(P_i)|=k表示在库所P_i有k个个体不可用.如W₁在全局时间1时,M₁(P₂)=(d₁,1),M₁(P₁₀)=(d₂,1),M₁(P₁₁)=(d₃,1),但是只有库所P₂的个体d₁可用.因此:

设Ω为DE-Net模型,二元组S=(M,TS)称为Ω在θ时刻的状态,其中,M为标识,描述了系统的资源分布;TS为在θ时刻标识M的等待时间,刻画了系统的时间特性.初始状态S₀=(M₀,TS₀),TS₀为一个零向量(在初始状态下所有令牌都是可用的).如,S₁=(M₁,TS₁)是Ω₁在时刻1的状态,其中,TS₁={0,1,3}.

二元组S=(M,TS)为Ω在θ时刻的状态,根据状态的定义可知,有两种方式可以改变状态S:(1) 时间的消逝.在时刻θ+w(w>0),由于系统中令牌的等待时间发生改变,促使系统到达新的状态S',记作S[w>S'.(2) 变迁替换的触发.变迁t_i替换的触发会产生新的标识,从而系统进入新的状态S',记作S[t_i<d₁,d₂,…,d_n>>S';.

若Ω₁在时刻1处于状态S₁=(M₁,TS₁)下,则不触发任何变迁,系统在时刻2处于另一个状态S₂=(M₂,TS₂),其中, M₁=M₂,TS₁≠TS₂.若Ω₁在时刻1触发t₁,则系统进入新的状态S₃=(M₃,TS₃),其中,M₁≠M₃,TS₁≠TS₃.将S经过时间w后再触发替换t_i<d₁,d₂,…,d_n>到达S',S[w>S'且S'[t_i>S'',记为S[(t_i<d₁,d₂,…,d_n>,w)>S''.t∈T,若FV(t_i)={x₁,x₂,…,x_n},则个体集{d₁,d₂,…,d_n}满足d_i∈{M^a(p)|p∈^·t∪t^·}且d_i对应于变量x_i,将个体d₁,d₂,…,d_n分别替换x₁,x₂,…,x_n所得到变迁t的实例称为变迁t的一个替换,记作t<x₁←d₁,x₂←d₂,…,x_n←d_n>,简写为t<d₁,d₂,…,d_n>.替换主要是对t的输入/输出弧以及A_T(t)中出现的所有自由变量绑定相应的个体.记A_T(t)<d₁,d₂,…,d_n>和A_F(p,t)<d₁,d₂,…,d_n>分别描述将个体d₁,d₂,…,d_n替换到公式A_T(t)和输入弧上谓词A_F(p,t)所得到的值.若替换t<d₁,d₂,…,d_n>使得A_T(t)<d₁, d₂,…,d_n>=true,则称t<d₁,d₂,…,d_n>是S下变迁t的可行替换.记变迁t在状态S=(M,TS)下的所有可行替换集合为VP(S,t).设变迁t的自由变量集FV(t_i)为空,若p∈^·t,M(p)≠∅,则变迁t在S下肯定存在可行替换.对应可行替换的执行过程为:从t的每个输入库所p_i中任选一个可用个体d_i即可.

设Ω为DE-Net模型,S=(M,TS)为Ω的一个状态,若VP(S,t)≠∅,则称变迁t在状态S下有发生权,记作S[t>.在DE-Net模型中,变迁t在状态S下是有发生权的,当且仅当t在状态S下存在可行替换.将状态S下所有有发生权的变迁集合记为ET(S).

定义5. 设Ω为DE-Net模型,S=(M,TS)为Ω的一个状态,对于变迁t_i∈ET(S),如果t_i满足下列条件:β_i≤min(β_j),其中,t_j∈ET(S),则称变迁t_i在状态S下的触发是有效的.

将状态S下所有可以有效触发的变迁集合记为FT(S).状态S下t_i的触发是有效的,当且仅当t_i在状态S下有发生权,且变迁集ET(S)中不存在比t_i优先级高的变迁.在状态S下通过有效触发变迁t_i的一个可行替换t_i<d₁,d₂,…,d_n>到达新状态S'的过程记为S[t_i<d₁,d₂,…,d_n>>S'.设Ω为DE-Net模型,M为Ω的一个标识,对于t_i,t_j∈ FT(S),若:^·t_iÇ^·t_j=∅,则称t_i,t_j在状态S下是并发;否则,称变迁t_i,t_j在M下冲突.若两个变迁间存在并发关系,则无论触发哪个变迁都不会影响另一个变迁的触发.将S下并发的变迁集合称为S的最大并发集,记为MT(S).集合H(S)={t<d₁,d₂,…,d_n>|t∈MT(S),t<d₁,d₂,…,d_n>∈VP(S,t)}称为S的一个最大触发集.

定义6. 设Ω为DE-Net模型,S=(M,TS)为Ω的一个状态,系统通过有效触发H(S)中所有变迁到达新的状态S',记作S[H(S)>S',称S'是S的可达状态.S'分别按如下规则计算:

t_i<d₁,d₂,…,d_n>∈H(S),p_j∈^·t_i∪t_i^·:M'(p_j)=M(p_j)-A_F(p_j,t_i)<d₁,d₂,…,d_n>+A_F(t_i,p_j)<d₁,d₂,…,d_n>.

在DE-Net模型中,可达状态按照触发变迁的可行替换进行相应的调整.如果存在触发序列H₁,H₂,…,H_k和状态序列S₁,S₂,…,S_k使得S[H₁>S₁[H₂>S₂…S_k-1[H_k>S_k,则称S_k是从S可达的.从S可达的所有标识集合记为R(S),规定S∈R(S).基于上述触发规则,从初始状态S₀出发构造模型的可达状态.

下面针对DES的需求模型,采用DE-Net模型对系统的基础组件分别进行建模,进而根据执行流程构造DES的能耗模型.为了区别输入接口和输出接口,对于输入接口用上标I标示,输出接口用上标O标记.另外,在设备、Agent、连接件的变迁和库所前标注对应的组件.如,设备ae_i的开始变迁t_in表示为ae_i.t_in.如果变迁是为了描述数据流程而引入,则不标注.

设备ae_i的DE-Net模型为Ω_aei如图 3所示,其中,引入库所分别描述设备的启动输入、休眠输入、执行输出、超时输出这4个接口,引入变迁t_i,t_e,t_ie,t_fo分别表示设备的启动、完成、休眠和超时处理操作.设备中的操作op_i运行过程如下:首先,引入变迁t_a,i刻画操作的执行,ct(p_a,i)=etp(op_i)表示操作的执行时间, en(t_a,i)=enp(op_i);若引入库所p_r,i用于标记操作的可执行,若设备发生超时或休眠,即|M(p_p,i)|≠0,则调用变迁t_p,i,使得操作处于中断位置p_p,i.变迁获得重新执行(p_r,i),则调用变迁t_r,i使得操作处于可用位置(p_w,i).引入库所p_c用于标记设备处于运行位置,引入库所p_d用来控制设备的运行时限,因此,设置Ct(p_d)为设备的动态运行时限.若时限截止时设备还未运行成功,则调用变迁t_fo输出超时故障P^o_dt若设备运行成功,则调用变迁t_e消除设备运行标记并输出结果到P^o_o同时,设备进入结束位置p_e.

Fig. 3 DE-Net model of device图 3 设备的DE-Net模型

在DES能耗模型中,连接件la_i的DE-Net模型Ω_lai如图 4所示.设连接件对应的两个组件为A和B,则对A,B分别引入两个接口用于接收和发送,对应库所描述组件的消息缓存,其中,库所p_po中存放连接件的解析策略.连接件接收到消息后触发变迁t_re,并按照d_i^p的规定来确定解析消息的策略.引入变迁t_se1,t_se2,用于发送消息到目的端,en(t_se1)=en(t_se1)=nl(la_i).

Fig. 4 DE-Net model of connector图 4 连接件的DE-Net模型

在DES能耗模型中,代理ag_i的DE-Net模型Ω_agi如图 5所示,其中,深色框内表示代理内设备和连接件的执行,即Agent的环境.Agent从环境中获取信息,根据自适应策略计算启动设备(即,对环境执行一定的控制).引入变迁t_st启动设备,而变迁t_ns使得其他设备进入休眠状态.变迁t_e表示Agent设备的结束.在收到Agent发出的指令后,设备会做出相应的调整和修改,若收到启动指令则设备进入运行位置.当设备收到休眠指令时,无论其处于等待执行、初始还是执行位置,设备都会调用相应的变迁进入休眠位置.若Agent下有设备运行超时,则启动超时处理,使得所有管辖的设备都进入休眠位置,并将超时信息上报系统.

Fig. 5 DE-Net model of agent图 5 Agent的DE-Net模型

下面根据DES的需求,构建DES的能耗模型.设需求模型的能耗模型Ω构造步骤如下:

(1) 根据各个设备的属性,构造所有设备的DE-Net模型.在上层模型中用表示设备ae_i的启动输入、休眠输入、输出、超时输出接口;进一步地,根据Agent与设备的关系建立Agent的能耗 模型.

(2) 引入变迁t_s和库所p_s分别描述整个系统的开始操作和位置,对整个系统进行初始化;引入变迁t_e和库所p_e分别描述整个系统的结束操作和位置.依据Agent关系,通过对应连接件的模型来组合Agent模型,以形成整个系统的能耗模型.引入变迁t_dt、库所p_a,p_c,p_dt描述系统的时限控制.

(3) 利用自适应能耗管理策略,依次计算启动设备集和设备的动态电压,并对模型中的库所进行初始化设置.

(4) 设置初始标识M₀(p_s)=,同时,设置变迁t_dt和系统级别所有变迁的优先级为4.本文将变迁优先级分为5个等级,可以根据实际需要适当地调整优先级的等级.

利用上述步骤,可以构建DES的能耗模型,为后续的系统分析和模型验证奠定基础.

基于构建的能耗模型,从分布式嵌入式系统结构中的任务、设备、代理和系统这4个角度着手,给出具体的能耗值计算公式,并映射到模型.

由于DES任务采用不同设备完成功能,会直接导致对应能耗模型可达状态的不同.设任务tk_i在设备ae_j上通过调用操作OP(ae_j,tk_i)执行,下面从能耗模型的角度对DES常见的能耗值进行计算和分析.

(1) 任务tk_i的能耗

操作新单位能耗和运行时间主要表现为能耗模型中对应变迁和库所的属性.任务tk_i的功能是由操作集合OP(ae_j,tk_i)中的所有操作共同完成的,因此,任务tk_i的能耗

基于任务的能耗可以分析系统中消耗最大的任务和最小的任务,以了解系统整体能耗的分布,进而为能耗分析奠定数据基础.映射到模型中,为任务对应路径的能耗.

(2) 设备的能耗性能

分析系统中各个设备的总能耗和平均能耗,可以将节能分析进一步定位到总能耗和平均能耗较大的设备.设备的总能耗映射到能耗模型中,为设备对应可达路径上变迁的能耗之和.

(3) 代理和系统的能耗值

代理的能耗主要由其所管辖的设备和连接件的能耗组成,因此,代理ag_j的能耗值为

利用上述能耗指标,可以从多方面对DES的能耗进行定量分析.此外,还可以利用模型中资源的分布动态获得正在运行的设备和操作集合、已经运行结束的设备和操作集合、超时的设备等信息.

计算树逻辑(computation tree logic,简称CTL)是时态逻辑的一种.CTL引入以下算子描述未来的不确定性: always(用G表示),sometimes(用F表示),next(用X表示),until(用U表示),all paths(用A表示),exists a path(用E表示).CTL公式语法可以表示为(使用BNF范式描述):

其中,pf属于原子公式集合.本节基于分布式嵌入式系统能耗模型的可达状态集,利用CTL描述系统的性质,借助Petri网的操作语义验证方法的正确性和有效性.

设模型Ω是利用DE-Net模型对DES需求进行建模所得到的能耗模型,R(Ω)表示对应的可达状态集,S是Ω的一个可达状态,是一个使用CTL描述的公式:性质可以描述为Ω,S|=,表示S状态满足公式.

能耗模型主要刻画DES的功能性需求,因此,有必要分析能耗模型能否正确描述嵌入式系统的执行流程.嵌入式系统的执行流程是由多个任务按照一定的关系组合而成,因此,可以从能耗模型能否正确描述任务间的关系着手.

定理1. 设模型Ω是利用DE-Net模型对DES需求进行建模所得到的能耗模型,R(Ω)是对应的可达状态集,S∈R(Ω),tk_i,tk_j∈TK,设tk_i∈TK(ae_f),tk_j∈TK(ae_g),则有:

(1) 若RL(tk_i,tk_j)=>且Ω,S|=₂,则Ω,S|=AX₁,其中,₁为任务tk_i得到执行,₂为任务tk_j得到执行;

(2) 若RL(tk_i,tk_j)=+,则Ω,S₀|=AG₃,其中,₃为|M(ae_f·p_e,o)|+|M(ae_g·p_e,p)|≤1,op_o∈op(tk_i),op_p∈op(tk_j);

(3) 若RL(tk_i,tk_j)=||,则Ω,S|=₄,其中,₄为|M(ae_f·p_e,o)|=|M(ae_g·p_e,p)|=1∨|M(ae_f·p_e,o)|=|M(ae_g·p_e,p)|=0.

证明:

(1) 因为RL(tk_i,tk_j)=>,若f=g,即tk_i,tk_j由同一个设备ae_f完成,则从设备的建模过程可知,存在变迁ae_f·t_i,j,将任务tk_i的运行结果输出到tk_j的输入.因此,任务tk_i在状态S得到执行,则存在状态S'∈R(S),使得ae_f·t_i,j∈ET(S).因此有Ω,S|=AX₁.否则,若两个任务分别由不同的设备完成(f≠g),根据系统建模过程可知,会引入连接件la_f用于完成任务tk_i到任务tk_j的交互.因此,任务tk_i在状态S得到执行,则存在状态S'∈R(S),使得连接件la_f得到执行.同理,存在状态S'∈R(S),任务tk_j得到执行.因此有Ω,S|=AX₁.

(2) 反证法,设子命题(2)不成立.即,∃S∈R(S₀),使得|M(ae_f·p_e,o)|+|M(ae_g·p_e,p)|>1,因为在任意一个设备模型中,库所p_e,o保存操作op_o运行结束的标记,所以|M(ae_f·p_e,o)|≤1,|M(ae_g·p_e,p)|≤1,|M(ae_f·p_e,o)|=|M(ae_g·p_e,p)|≤1.因为RL(tk_i,tk_j)=+,所以不存在某个状态使得两个任务同时执行,与上述假设推导结论矛盾,所以假设不成立.即,子命题(2)成立.

(3) 同理可证,子命题(3)成立.

定理1说明:能耗模型可以正确地描述DES的业务执行流程,因此可以使用能耗模型在系统设计前期演示和分析DES的功能性需求.由于系统的节能主要通过自适应能耗管理策略来实现,因此有必要分析能耗模型对能耗管理策略的正确执行.能耗模型对启动和调整策略的正确执行,主要体现在根据计算好的启动设备集和动态单位能耗,实现设备的启动和休眠控制.

定理2. 设模型Ω是利用DE-Net模型对DES需求进行建模所得到的能耗模型,R(Ω)是对应的可达状态集, S∈R(Ω),ae_i∈AE,系统的启动设备集AE_ac,则:

(1) 若ae_i∈AE_ac,Ω,S|=₁,其中,₁为|M(ae_i·p_e)|=1;

(2) 若ae_i∉AE_ac,Ω,S|=₂,其中,₂为|M(ae_i·p_p)|=1.

证明:

(1) 若ae_i∈AE_ac,不妨设ae_i∈eg(ag_j),即ae_i属于Agent的管辖范围.

(2) 同理,从Agent对设备执行休眠操作的建模过程可证子命题(2)成立.

定理2说明,能耗模型可以正确地描述Agent与设备之间的交互,包括获得设备信息、Agent启动和休眠设备.在实际运行中,设备的启动和休眠不一定是固定不变的,比如,设备ae在某次运行中需要启动,在新的环境中(系统设备分布发生改变时)可能需要休眠.因此,有必要分析在能耗模型中设备被休眠后是否可以被重新启动,已经运行的设备是否可以被中断.

定理3. 设模型Ω是利用DE-Net模型对DES需求进行建模所得到的能耗模型,R(Ω)是对应的可达状态集, S∈R(Ω),ae_i∈AE,则:

(1) 若|M(ae_i·p_p)|=1,则Ω,S|=₁,其中,₁为|M(ae_i·p_e)|=1;

(2) 若|M(ae_i·p_p,j)|=1,Ω,S|=₂,其中,₂为|M(ae_i·p_g,j)|=1.

证明:

(1) ae_i∈AE,因为|M(ae_i·p_p)|=1,所以在状态S下,设备ae_i处于休眠位置.设经过一段时间后,ae_i得到重新启动,即,存在S₁∈R(S)有|M₁(ae_ip_i^I·)|=1.下面证明ae_i的休眠不会影响再次启动,主要从两个方面证明:

首先证明ae_i可以重新进入运行位置,即,调用操作.因为ae_ip_i^I·={ae_i·t_i,ae_i·t_r},^·ae_i·t_r={ae_ip_i^I·ae_i·p_p},所以ae_i·t_r具有发生权,且ae_i·t_r的优先级为0.所以状态S₁下,变迁ae_i·t_r的触发是有效的.不妨设S₁通过触发变迁ae_i·t_r到达状态S₂,则有|M₂(ae_i·p_w)|=|M₁(ae_ip_i^I·)|=1,因为^·ae_i·t_i={ae_ip_i^I·,ae_i·p_w},所以ae_i·t_i在状态S₂下的触发是有效的,即,ae_i可以重新进入运行位置.

其次证明所有的操作都可以正常执行,op_f∈op(ae_i)在ae_i被休眠时刻可能处于运行位置p_a,f或结束位置p_e,f.因为^·ae_i·p_p=ae_i·t_ie,ae_ip_i^I·={ae_i·p_p,ae_i·p_p,1,ae_i·p_p,2,…,ae_i·p_p,n},所以在状态S下,有:

|M(ae_i·p_p,1)|=|M(ae_i·p_p,2)|=...=|M(ae_i·p_p,n)|=|M(ae_i·p_p,n)|=|M(ae_i·p_p,n)|=1.

因为op_f∈op(ae_i)在状态S下有|M(ae_i·p_w,f)|=1,^·ae_i·t_p,f={ae_i·p_w,f,ae_i·p_p,f},且变迁ae_i·t_p,f的优先级等于0,所以ae_i·t_p,f在S下可以有效触发.不妨设S通过有效触发ae_i·t_p,f到达状态S₃,因为ae_i·t_p,f^·=ae_i·p_g,f,所以S₃下有|M₃(ae_i·p_g,f)|=1,操作可以正常执行.即,ae_i通过执行一些操作后,可能到达结束位置p_e.因此,Ω,S|=₁,其中,₁为|M(ae_i·p_e)|=1.

(2) 同理可以证明子命题(2)成立.

定理3说明:当Agent需要重新启动某个已经被休眠的设备时,设备及其操作都可以正常执行,完成相应的功能.同时,当操作处于运行位置时,对应设备得到休眠指令,操作可以被挂起,进入到中断位置.在DES能耗建模过程中,自适应能耗管理策略是核心部分,因此,有必要分析自适应策略的有效性.

定理4. 设DES需求为,利用自适应策略计算出系统的启动设备集为AE_ac,任务tk_i的运行时间和供电电压分别为tc_i,Vⁱ_dd则:

(1) 任意一个可以完成系统功能的设备集为AE_f,则有EN(AE_ac)≤EN(AE_f);

(2) 在启动设备集AE_ac下,调压后的系统能耗小于等于调压前的能耗.

证明:

(1) 反证法:设存在设备集AE_f,利用AE_f可以完成系统功能且EN(AE_ac)>EN(AE_f).根据假设有两种情形:

情形1:存在设备ae_i∈AE_ac可以完成ae_j∈AE_f的功能,其余设备相同.根据假设有EN(ae_i)>EN(ae_j).基于设备间关系可得,若设备ae_i和ae_j的距离在阈值范围内,则ae_j完全覆盖ae_i.根据启动策略可知,系统会选择ag_j替代ae_i.所以假设不成立,否则,若设备ae_i和ae_j的距离不在阈值范围内,则虽然EN(ae_i)>EN(ae_j),但是由于ae_j的地理位置比较远,所以选择ae_j会导致传输能耗变大,最终执行的能耗增加.所以假设不成立.

情形2:存在设备集ae_j,1,ae_j,2,…,ae_j,k可以完成ae_i的功能,但是EN(ae_i)>EN(ae_j,1)+EN(ae_j,2)+…+ EN(ae_j,k).根据分布式嵌入式系统可知,设备的启动和休眠的能耗差距比较大,因此,将多个任务分散到不同设备执行比将任务集中在一个设备上能耗大.因情形2与实际相悖,所以假设不成立.

综上所述,若任意一个可以完成系统功能的设备集为AE_f,则有EN(AE_ac)≤EN(AE_f).

(2) 设op_f是系统执行过程中调用的一个操作,op_f的新能耗为

即,通过电压调整操作的能耗得到降低.系统的整体能耗等于执行的各操作能耗之和,因此,调压后的系统能耗小于等于调压前的能耗.

定理4说明:通过自适应能耗的两个子策略,DES的整体能耗可以逐步得到降低.