0 引言
随着信息物理融合系统(cyber-physical system,CPS)在工业4.0中核心地位的提出,CPS成为众多学者研究与关注的焦点.软件作为CPS的重要使能部分[1],优化软件的能耗对提高CPS效率具有重要意义. Petri网自Petri教授提出后,一直被应用于离散并发系统的建模中,其数字化和直观图形的两种表述方法极大地满足了建模的需求.
至今为止,国内外众多学者对CPS软件能耗与Petri网建模进行了大量的有针对性的研究.其中,文[2-3]指出CPS具有在物理世界中嵌入网络,改变信息与物理世界交互的能力,应用CPS可以成为进一步发展各领域的重要手段,但这些系统不够充分,需要更广泛的数据分析和通信网络.文[4-6]引入软件可信性评估的概念,根据CPS体系结构级特征向量建立了基于能耗时间的CPS能耗模型和可信性指标模型,并用实例对其模型进行验证.文[7]在搭建能耗监控系统硬件电路的基础上,通过基于蚁群算法的CPS异构网络路由算法,保证系统的传输质量.文[8]针对装备系统提出了将层次着色Petri网与图灵机相结合的方法,并通过网络状态生成图分析验证.文[9]利用层次着色Petri网对网构软件的性能从服务开始请求到服务执行完成进行了详细的建模.文[10]利用层次着色Petri网将庞大的交通系统分为若干子系统,并将数据赋予颜色,使功能与描述更好地对应.文[11]中对体系结构特征量与软件能耗之间做出了存在非线性函数关系的假设,并分析了软件体系结构特征向量对软件能耗的影响程度.文[12]利用CPS语言对嵌入式进行建模,并采用进程的方式,通过最大、最小与平均能耗算法对能耗进行分析.文[13-15]分别基于随机Petri网和时间Petri网对嵌入式软件能耗从构件、接口与连接件的角度考虑进行模型建立.
目前,国内外学者针对CPS软件能耗和Petri网建模做了许多研究,但对基于Petri网的CPS软件能耗层化建模方面的研究还有诸多不足.现阶段,对软件能耗的分析求解大多集中在单源路径[16-17],但由于CPS软件系统大型、复杂,单源路径在求解并分析能耗方面往往不能满足高效运算的要求.本文以CPS软件能耗建模与分析为背景,在传统Petri网的基础上,引入了层次和颜色的概念,将CPS软件能耗模型分为顶层CPN(color Petri net)与若干个子层CPN. CPS软件能耗的顶层CPN的构成要素包括计算模块、通信模块和控制模块三个部分,计算模块和控制模块可以通过通信模块连接起来,也可以分别与通信模块相连.子层CPN是顶层CPN的展开视图,计算模块和控制模块都具有各自的子层CPN,其中,计算模块的子层CPN包括数据信息处理和控制决策,控制模块的子层CPN包括网络化分布式协同控制和数据驱动的自适应控制,该模型对CPS软件能耗进行自顶向下、详细地建模,使能耗计算更加具体、细致.能耗分析方面,本文在分层着色Petri网对CPS软件建立能耗模型的基础上,采用分层并行的最小能耗算法进行能耗求解分析,该算法实现了每个模块的能耗可独立计算分析的能力,有效地提高了计算运行速度,该算法再将各个模块的能耗汇总后计算出总的能耗.最后通过对汽车远程车位定位系统这一典型的CPS软件进行实例分析,并将其与最新能耗模型的研究相比较,验证该模型的有效性与可靠性.
1 基本定义 1.1 分层着色Petri网定义1 一个基本Petri网定义为五元祖:N=(P,T,F,W,M0),其中,
(1) P是库所(place)有限集;
(2) T是变迁(transition)有限集;
(3) F是有向弧(flow relation)集,其中,F⊆(P×T)∪(T×P);
(4) W是弧的权函数;
(5) M0是初始标识.
其中,F⊆(P×T)∪(T×P)表示有向弧F既可由库所P指向变迁T,也可由变迁T指向库所P,且
M(p)=a表示库所内有a个托肯,在Petri网中,托肯是可以从一个库所经由变迁的作用移动到另一个库所.在传统Petri网中,托肯用黑色的实心圆点表示.托肯移动的规律为:当输入库所包含托肯的同时,输出库所不包含托肯,变迁就可以发生使能.变迁发生使能后,输入库所内的托肯转移到输出库所内,如图 1所示.
定义2 一个着色Petri网CPN是一个六元组:CPN=(P,T,F,W,M0,C),其中
(1) P,T,F,W,M0与定义1中的含义相同.
(2) C是颜色集,满足C{C(p),C(t)},其中C(p)是库所颜色集,表示处在p状态的属性集,属性集包括参数信息和描述信息两部分,参数信息用来记录过程控制和结果,描述信息用来区分对象. C(t)是变迁颜色集.
定义3 一个完整的分层着色Petri网HCPN是由一组HCPN子网模型组成,表示为
式中n表示该模型分为n层,HCPN_i表示第i层子网模型.
定义4 一个HCPN第i层子网模型是由一个三元组组成,表示为
其中,Ai表示该子网的名称,CPN_i表示一个着色Petri网CPN,Vi表示该子网的一组定义变量[18]. HCPN模型如图 2所示.
1.2 CPS软件能耗定义5 软件能耗Esoft可用式(1)所表示:
(1) |
其中:
(2) |
(3) |
其中,CP表示计算模块,Ei表示第i个计算模块所产生能耗,CM表示无线通信模块,Ef表示第f个无线通信模块所产生能耗,CT表示控制模块,Ek表示第k个控制模块所产生能耗,EQ表示顶层模块间的能耗,En表示数据信息处理所产生能耗,Em表示控制决策所产生能耗,El表示网络化分布式协同控制所产生能耗,Ep表示数据驱动的自适应控制所产生能耗.
定义6 带权有向图G=(V,E,W),其中V表示节点集,V={v1,v2,…,vn},E表示路径集,E={vivj|i≠j,1≤i,j≤n},vivj表示有序节点 < vi,vj > 相关联的路径,W表示每条路径的权值集合,W={wij|i≠j,1≤i,j≤n}.
2 建立CPS软件能耗模型 2.1 分层由于CPS软件系统复杂,直接铺开建模非常庞大.在建立大型、复杂的Petri网时,可以引入层次的概念,采用自顶向下的方式,将CPS软件的主要模块放在模型的顶层,然后对每个主要模块进行进一步的细化为子模块,逐步丰富模型,本文将CPS软件能耗模型分为两层:
(1) 顶层:根据研究表明,在任何CPS软件中,都存在计算模块、通信模块和控制模块三个主要部分,所以,我们将这三部分组成了能耗模型的第一层.
(2) 子层:将顶层中的计算模块和控制模块进一步展开细化,计算模块包括数据信息处理和控制决策两个子部分,控制模块根据控制的施加者不同,分为网络化分布式协同控制和数据驱动的自适应控制两个子部分,将这4个子部分组成了能耗模型的第二层.
2.2 着色在传统Petri网的基础上,通过对库所内的托肯赋予颜色,不同颜色的托肯可以代表不同的个体.在本文中,我们通过对CPS软件内的不同组成部分托肯赋予不同颜色,在计算总能耗的同时,加以区分各个不同组件的能耗.
着色Petri网内颜色数据类型丰富,包括整型(INT)、布尔型(BOOL)、字符串型(STRING)、列表型(LIST)、记录型(RECORD)、序偶型(PRODUCT)等类型.本文使用这些数据类型对CPS软件能耗模型中的主要涉及的对象进行定义.
Declarations
colset Computer=product no_cp:LIST*c_cp:INT;
colset Communicate=product no_cm:LIST*c_cm:INT;
colset Control=product no_ct:LIST*c_ct:INT;
colset CP_Dtpr=record st_dtpr:STRING*c_dtpr:INT;
colset CP_Dec=record st_cpdc:STRING*c_cpdc:INT;
colset CT_Cpt=record st_ctcpt:STRING*c_ctcpt:INT;
colset CT_Self=record st_cts:STRING*c_cts:INT;
其中,Computer、Communicate、Control、CP_Dtpr、CP_Dec、CT_Cpt、CT_Self分别表示顶层CPN中的计算模块、通信模块、控制模块和子层CPN中的数据信息处理、控制决策、网络化分布式协同控制和数据驱动的自适应控制.其中,Computer、Communicate和Control定义为序偶型;CP_Dtpr、CP_Dec、CT_Cpt和CT_Self定义为记录型,这7个模块分别含有两个元素. no_cp、no_cm和no_ct分别表示计算模块、通信模块和控制模块编号,都定义为list类型;c_cp、c_cm和c_ct分别表示计算模块、通信模块和控制模块的能耗;st_dtpr、st_cpdc、st_ctcpt和st_cts分别表示为数据信息处理、控制决策、网络化分布式协同控制和数据驱动的自适应控制的状态,都定义为string类型;c_dtpr、c_cpdc、c_ctcpt和c_ctcpt分别表示为数据信息处理、控制决策、网络化分布式协同控制和数据驱动的自适应控制的能耗.
2.3 能耗模型 2.3.1 顶层CPN能耗模型任何CPS都具有计算模块、通信模块和控制模块,这三部分之间具有以下三种连接关系.
其一,计算模块与控制模块通过通信模块相连组成其中一部分;
其二,计算模块与通信模块组成其中一部分;
其三,控制模块与通信模块组成其中一部分.
根据这三种关系,可以得出CPS的结构模型图,如图 3所示.
根据CPS结构之间连接关系,本文可以构造出符合CPS结构模型实际情况的CPS软件能耗的顶层CPN模型,如图 4所示.
图 4中展示CPS软件的作业流程以及库所内的托肯颜色的类型及所含元素,其涉及的库所和变迁的含义如表 1和表 2所示.
在CPS软件系统中,图 4中d2计算模块,d3控制模块都必须展开成子模块进行建模,展开后的子模块形成子层CPN模型.由于计算模块与控制模块的子层CPN类似,在这里只给出计算模块的子层CPN模型,如图 5所示.其中,数据信息处理、控制决策都具有状态变量st_dtpr、st_cpdc,将st_dtpr、st_cpdc赋予不同的颜色,代表不同的状态.现令:
由数据信息处理、控制决策的状态颜色取值,可以出现4种状态情况.
(1) 如果st_dtpr=0且st_cpdc=0时,即数据信息处理和控制决策的能耗都未计算过,则能耗计算到达Td2.1,开始计算模块的能耗计算. Pd2.2启动数据信息处理功能,Td2.2统计数据信息处理产生的能耗. Pd2.3启动控制决策功能,Td2.3统计控制决策产生的能耗. Pd2.4,将数据信息处理产生的能耗与控制决策产生的能耗汇总,Td2.4计算模块能耗统计完成.
(2) 如果st_dtpr=0而st_cpdc=1时,即数据信息处理的能耗未计算过,控制决策的能耗已经计算过,则能耗计算到达Td2.5,开始计算模块中数据信息处理的能耗计算. Pd2.5启动数据信息处理功能,Td2.6统计数据信息处理产生的能耗. Pd2.6,将数据信息处理产生的能耗汇总,Td2.7计算模块能耗统计完成.
(3) 如果st_dtpr=1而st_cpdc=0时,即数据信息处理的能耗已经计算过,控制决策的能耗未计算过,则能耗计算到达Td2.8,开始计算模块中控制决策的能耗计算. Pd2.5启动控制决策功能,Td2.6统计控制决策产生的能耗. Pd2.6,将据控制决策产生的能耗汇总,Td2.7计算模块能耗统计完成.
(4) 如果st_dtpr=1且st_cpdc=1时,即数据信息处理和控制决策的能耗都已计算过,则能耗计算到达Td2.11,开始统计下一个计算模块的能耗.
3 能耗分析 3.1 分层并行算法思想根据上节所构造的CPS软件能耗的顶层CPN和子层CPN模型,将它们合在一起为完整的HCPN模型,根据HCPN模型可以构造出对应的能耗状态可达图,本文将分析CPS软件能耗问题归纳到寻找HCPN所对应的能耗状态可达图中节点路径问题.并且采用分层并行求解的方法[19]对已层次化建模的CPS软件进行最小能耗求解.
根据CPS软件能耗层次着色Petri网的层次模型,对最小能耗的求解过程可以分两步进行,其一:对顶层CPN模块节点之间求最小能耗.其二:求各个模块内部的所有节点到顶层模块节点的最小能耗.经过这两步的计算后,再汇总到一起,得出最终结果.
在并行算法中,本文通过具有相同代码段的进程对不同的数据进行操作来实现计算最小能耗.当处理器各自完成计算后,将各子层模块的能耗与顶层模块的能耗汇总计算出总的能耗,该并行算法加快了最小能耗的计算速度,并行最小能耗算法的步骤如图 6所示.
(1) 将每个模块独立划分出来,方便分别同时进行能耗计算.
(2) 每个模块同时独立地进行求解离顶层模块起点距离的局部最小值,局域最小值的求解为dmin+W(v,a)<d(v),则修改最小值为d(v)=dmin+W(v,a).
(3) 重复第(2)步骤,直到所有模块的能耗全部计算完.
3.2 分层并行算法及流程本文涉及的分层并行算法如下
输入:CPS软件内所有节点
输出:CPS软件能耗
Step 1:将CPS软件内所有节点根据HCPN模块划分为不同区域.
Step 2:将每个区域分给不同的能耗计算处理器.
Step 3:将顶层模块的节点分配给主处理器.
Step 4:判断该区域是不是子层CPN模型中的节点.如果是,进行Step 5,如果不是,进行Step 7.
Step 5:确定节点所在子网.
Step 6:计算该子网最小能耗.
Step 7:计算顶层模块内节点间的最小能耗.
Step 8:将所有子层模块的能耗与顶层能耗相加.
Step 9:输出总能耗.
分层并行算法流程图如图 7所示.
4 实例建模与分析本文模拟了一种汽车远程车位定位系统为实例对象.汽车远程车位定位系统是典型的CPS系统,随着车位紧张,车主及时找到车位并停车成了一大难题.汽车远程车位定位系统可以及时收集信息并反馈给车主作为参考,该系统一般包括3个模块:监控管理模块、无线通信模块、参数采集数据库模块.通过对这3个模块的分析,可以对该系统进行基于HCPN的能耗建模.将顶层CPN模型与子层CPN模型汇总在一起,结果如图 8所示.
在建立了汽车远程车位定位系统的HCPN模型后,本文通过插桩的方式测量各个模块及其子模块的执行时间,并取得相对应的能耗,表 3为HCPN模型中涉及到的主要变迁的具体操作、执行时间和能耗值.
变迁 | 操作 | 执行时间 | 能耗 |
T1 | 启动相关传感器 | 58 | 5.8 |
T2 | 采集传感器工作状态 | 43 | 4.3 |
T3 | 发送正常工作状态 | 30 | 3 |
T4 | 发送异常工作状态 | 30 | 3 |
T5 | 与中心监控电脑连接 | 60 | 6 |
T6 | 将正常工作状态发送给中心监控电脑 | 35 | 3.5 |
T7 | 将异常工作状态发送给中心监控电脑 | 35 | 3.5 |
T8 | 对数据进行实时监测 | 65 | 6.5 |
T9 | 对数据进行分析 | 62 | 6.2 |
T10 | 收到定位准确信息 | 33 | 3.3 |
T11 | 收到定位不准确信息 | 33 | 3.3 |
T12 | 预定车位 | 47 | 4.7 |
T13 | 重新定位 | 20 | 2 |
T14,T15,T16,T17,T18,T19,T20,T21 | 通信 | 35 | 3.5 |
根据图 8的HCPN模型,可以得出该模型的能耗状态可达图,如图 9所示.
在构造出汽车远程车位定位系统的状态可达图后,就可以根据状态可达图分析该系统的能耗问题.本文有多条路径,通过对这数条路径进行多次模拟实验,得出最小能耗为50.3.
为了验证本模型的有效性与可靠性,本文汽车远程车位定位系统应用到张广泉等人提出的基于能耗时间Petri网建模和祝义等人提出的基于进程代数[20]的建模中求解其能耗Esoft,并通过实验模拟进行3次实验,实验得到的能耗记为ESE,得到如表 4所示的结果.
能耗 | 建模方法 | 最小能耗 |
Esoft | 本文层次着色Petri网能耗模型 | 50.3 |
能耗时间Petri网能耗模型 | 46.8 | |
进程代数能耗模型 | 57.3 | |
ESE | 本文第一次实验 | 62.7 |
本文第二次实验 | 64 | |
本文第三次实验 | 58.9 |
根据Esoft与ESE可以得出误差式(4)
(4) |
根据式(4)可以得出本文方法与上述两种方法和实际测量的结果相对误差分别为7.48%、12.22%、19.78%、21.41%、14.60%,由于相对误差在合理范围内,可以证明本文构建的模型有效且合理.
5 结束语本文针对CPS软件能耗建模问题,从CPS软件的体系结构出发,构建了由计算模块、通信模块和控制模块为顶层CPN和由数据信息处理、控制决策、网络化分布式协同控制和数据驱动的自适应控制为子层CPN的层次着色Petri网,在层次着色Petri网的基础上,给出了CPS软件能耗模型.在CPS软件能耗分析上,提出了分层并行求解最小能耗的算法,提高了能耗计算效率.通过汽车远程车位定位系统这一CPS软件典型实例,对比其它能耗模型与实验,验证这一模型的有效性和合理性.本文提出的基于层次着色Petri网的CPS软件能耗建模没有考虑时间参数,因此该模型与能耗分析还需进一步完善.
[1] | Sandeep K S G, Tridib M, Georgios V, et al. Research directions in energy-sustainable cyber-physical systems[J]. Sustainable Computing Informatics & Systems, 2011, 1(1): 57–74. |
[2] | Poovendran R. Cyber-physical system:Close encounters between two parallel worlds[J]. Proceedings of the IEEE, 2010, 98(8): 1363–1366. DOI:10.1109/JPROC.2010.2050377 |
[3] | Kunzemann P, Jacobs G, Schelenz R. Application of CPS within wind energy-current implementation and future potential[M]. Berlin, Germany: Springer, 2017. |
[4] |
孙振华.
基于CPS软件的体系结构能耗建模评估研究[J]. 节能技术, 2017, 35(4): 339–343.
Sun Z H. Architecture energy consumption modeling evaluation studies based on CPS software[J]. Energy Conservation Technology, 2017, 35(4): 339–343. |
[5] |
张广泉, 张侃, 祝义, 等.
基于体系结构能耗建模的CPS软件可信性评估方法[J]. 电子学报, 2013, 41(11): 2270–2275.
Zhang G Q, Zhang K, Zhu Y, et al. Trustworthing evaluation method for CPS software based on software architecture energy consumption modeling[J]. Acta Electronica Sinica, 2013, 41(11): 2270–2275. DOI:10.3969/j.issn.0372-2112.2013.11.025 |
[6] |
张侃. 基于体系结构能耗建模的CPS软件可信性评估研究[D]. 苏州: 苏州大学, 2013. Zhang K. CPS software trustworthiness evaluation based on software architecture energy consumption modeling[D]. Suzhou: Suzhou University, 2013. |
[7] |
任婧娅, 马斌. 基于CPS的能耗监控系统网络架构及协议研究[D]. 沈阳: 沈阳建筑大学, 2013. Ren J Y, Ma B. Research on network architecture and protocol of energy monitoring system based on CPS[D]. Shenyang: Shenyang Construction University, 2013. |
[8] |
宋荆州, 马铁军, 孙汉旭, 等.
基于分层着色Petri网的增强现实装配系统建模[J]. 计算机集成制造系统, 2012, 18(10): 2166–2174.
Song J Z, Ma T J, Sun H X, et al. Modeling of augmented reality assembly system based on hierarchy colored Petri net[J]. Computer Integrated Manufacturing Systems, 2012, 18(10): 2166–2174. |
[9] |
徐倩, 应时, 贾向阳, 等.
基于层次着色Petri网的网构软件性能建模与仿真分析方法[J]. 小型微型计算机系统, 2016, 37(4): 641–645.
Xu Q, Ying S, Jia X Y, et al. Performance modeling and simulation analysis approach of internetware using hierarchical colored Petri nets[J]. Journal of Chinese Computer Systems, 2016, 37(4): 641–645. |
[10] |
顾鸿儒, 孙连坤.
基于层次颜色Petri网的全感应控制交通信号灯建模与仿真[J]. 计算机工程与科学, 2016, 38(9): 1887–1893.
Gu H R, Sun L K. Modeling and simulation of full-sensitive control traffic lights based on hierarchical colored Petri net[J]. Computer Engineering & Science, 2016, 38(9): 1887–1893. |
[11] |
刘啸滨, 郭兵, 沈艳.
嵌入式软件体系结构级能耗建模方法[J]. 软件学报, 2012, 23(2): 230–239.
Liu X B, Guo B, Shen Y. Embedded software energy modeling method at architecture level[J]. Journal of Software, 2012, 23(2): 230–239. |
[12] |
张滕滕, 吴晓, 李长德.
基于CSP的构件化嵌入式软件能耗分析与评估方法研究[J]. 计算机学报, 2009, 32(9): 1876–1833.
Zhang T T, Wu X, Li C D. On energy-consumption analysis and evaluation for component-based embedded system with CPS[J]. Chinese Journal of Computers, 2009, 32(9): 1876–1833. |
[13] |
张晶, 王中正, 范洪博.
基于随机Petri网的嵌入式软件能耗模型[J]. 计算机工程, 2017, 43(9): 316–321.
Zhang J, Wang Z Z, Fan H B. Energy consumption evaluation model of embedded software based on stochastic Petri net[J]. Computer Engineering, 2017, 43(9): 316–321. |
[14] |
张晶, 王亮, 范洪博, 等.
基于时间Petri网的嵌入式系统构件建模与能耗分析[J]. 计算机工程, 2017, 43(6): 30–34.
Zhang J, Wang L, Fan H B, et al. Component modeling and energy consumption analysis of embedded system based on time Petri net[J]. Computer Engineering, 2017, 43(6): 30–34. |
[15] |
陈沫良. 基于体系结构级的嵌入式软件能耗模型及性能研究[D]. 昆明: 昆明理工大学, 2015. Chen M L. The energy consumption model and performance study of embedded software based on architecture level[D]. Kunming: Kunming University of Science and Technology, 2015. |
[16] | Zhu C J, Lam K Y, Han S. Approximate path searching for supporting shortest path queries on road networks[J]. Information Sciences, 2015, 325(C): 409–428. |
[17] | Maleki S, Nguyen D, Lenharth A, et al. DSMR: A parallel algorithm for single-source shortest path problem[D]. Istanbul, Turkey: University of Illinois at Urbana-Champaign, 2016. |
[18] |
赵艳丽, 江志斌. 面向临床路径的分层赋时着色Petri网建模及优化调度方法研究[D]. 上海: 上海交通大学, 2010. Zhao Y L, Jiang Z B. The hierarchical timed colored Petri net based modeling and scheduling optimization of clinical pathway[D]. Shanghai: Shanghai Jiao Tong University, 2010. |
[19] |
林乘飞. Petri网可达图的并行算法[D]. 西安: 西安电子科技大学, 2011. Lin C F. The parallel algorithm of Petri net accessible graph[D]. Xi'an: Xi'an University of Electronic Science and Technology, 2011. |
[20] |
祝义, 肖芳雄, 周航, 等.
一种嵌入式实时系统软件能耗与分析的方法[J]. 计算机研究与发展, 2014, 51(4): 848–855.
Zhu Y, Xiao F X, Zhou H, et al. Method for modeling and analyzing software energy consumption of embedded real-time System[J]. Journal of Computer Research and Development, 2014, 51(4): 848–855. DOI:10.7544/issn1000-1239.2014.20120868 |