0 引言

随着物联网技术的发展和应用不断深入，智能感知节点(Intelligent Sensing Nodes, ISN)应用范围和数量不断攀升，其性能、功耗等要求越来越高。为提高ISN的续航能力，必须对其进行低功耗软硬件划分( Low Power Consumption Hardware and Software Partitioning, LPHSP)。在ISN设计和研发过程中，软硬件划分属于顶层规划与设计范畴，因此,对ISN进行低功耗软硬件划分是其设计和研发过程的最高层次低功耗的抽象，使其能耗达到最优化。低功耗软硬件划分对ISN至关重要，且有利于降低节点能耗，提高续航能力。

国内外研究者对低功耗软硬件划分算法进行了相关研究。文献[1]对双目标多选择软硬件划分进行了研究，提出了快速生成近似解的启发式算法，用定制禁忌搜索算法改进近似解算法和快速计算精确解的动态规划算法来研究软硬件划分。文献[2]对智能系统可变需求下的软硬件划分进行了研究，提出了一组增强的硬件/软件资源共享参数的划分算法。文献[3]对异构多处理器片上系统(Multi-Processor System-on-Chip, MPSoC)的软硬件划分进行了研究，提出了一种利用优化的整数线性规划算法来解决小输入的软硬件划分问题的方法。文献[4]对片上可编程门阵列作为控制器的软硬件划分进行了研究，提出了非主流排序遗传算法，并对算法进行了验证。文献[5]对复杂嵌入式系统软硬件划分进行了研究，提出了一种更加适合软硬件划分的盲优化算法，并对算法进行了验证和对比分析。文献[6]对大规模软硬件划分进行了研究，提出了一种爬山淘汰粒子群算法，并对算法进行了验证与分析。这些研究提出的低功耗软硬件划分算法、方法和策略，为研究ISN低功耗软硬件划分问题提供了很好的参考，但未针对物联网ISN进行低功耗软硬件划分研究。

π网是一种能够处理并发事件的建模工具,融入了π演算和Petri网,是Petri网发展的高级阶段[7]。鉴此，针对物联网ISN设计时对低功耗的要求，根据π网理论，建立ISN低功耗软硬件划分模型，并对模型进行分析和仿真实验。分析与仿真实验结果表明，与基于禁忌搜索算法和遗传算法的模型相比，该模型在适应度和划分执行时间等方面具有一定的优越性和实用性，可降低物联网智能感知节点能耗，提高其续航能力。

1 智能感知节点约束模型

感知层作为物联网的最底层，由多种不同类型的感知设备、感知节点构成，这些设备大多为智能型设备，能够完成感知、处理和传输任务，故可抽象为ISN，其功能需求可用任务流程图法来描述[8]。

任务流程图法是依据待完成目标对象的要求及其主要过程，采用图表进行分析和选择实现目标所需的实际线路，描述实现顺序和过程的一种计划管理方法。智能感知节点具有一定的约束条件，特别是功耗和能耗方面的约束。为更好地描述智能感知节点,使用任务流程图来描述ISN划分任务。任务流程图通过有向无环图(Directed Acyclic Graph, DAG)予以描述,物联网的若干ISN也可以抽象为DAG，故可用定义1来描述。

定义1 若物联网ISN的软硬件划分问题为加权DAG，则可定义其软硬件划分任务流程为一个五元组表，即PCG={V,E,W,Fec,Oo}。

PCG为ISN的加权DAG；V为候选的IP核顶点集合，V={v1,v2,…,vn}，且IP核为具有一定功能的软件或硬件组件；E为中顶点间有向边的集合，即E⊆为顶点vi到顶点vj的有向边，亦表示顶点vi,vj间的依赖关系；W为专用复杂功能组件加权集合，W={Pro,Fp,Ap,Rp,Po}，Pro,Fp,Ap,Rp,Po分别为处理器核、FPGA或CPLD核、ASIC核、RSIC核和其他IP内核；Fec为各种IP核功耗/能耗加权函数；Oo为面积、执行时间等其他指标的加权函数集合。

定义2 物联网ISN能耗。若ISN的第i个IP核的能耗主要由空闲能耗和运行能耗构成(式(1))，则ISN的总能耗为式(2)。

Ci=Cd(i)+Cr(i)

(1)

(2)

式中：Cd(i)为第i个IP核空闲能耗；Cr(i)为第i个IP核运行能耗；Cg为给定的功耗最大值。

由定义1可知，若W中的每个硬件处理核有本地内存，则每个处理核上的任务间的通信即可实现。为便于进行ISN抽象，在此假定在ISN架构中的处理器数量足够，无资源竞争和临界问题，则可得到如图1所示的ISN抽象架构。

图1 ISN抽象架构
Fig.1 Abstract architecture of ISN

由定义1可知，ISN任务流程为DAG时，有向边上的数字ωij为顶点vi到顶点vj的功耗值；边eij除表示依赖关系外，还表示顶点vi到顶点vj的通信链路，此链路可能是多种总线,也可能是点到点的通信，任意2个顶点至少有一条通信链路直接连接。一个任务流程图中有且只有一个起始的顶点，且其入度为0，同时，也仅有一个顶点的出度为0，将这2个顶点分别称为起始顶点和终止顶点，如图2所示，其中v1为智能节点的某种功能的软硬件划分开始，vn为实现该功能的软硬件划分的最优结果。

图2 ISN功能IP核任务流程
Fig.2 IP core task flow of ISN function

由定义1和定义2可得，用任务流程图来描述ISN的任务划分时，在功耗等约束下，可寻求ISN在功耗和其他指标的最优解。图2即为某个ISN在若干划分任务下的最优解。

依据定义1和定义2，可得到ISN软硬件划分问题的定义,即定义3。

定义3 物联网ISN软硬件划分问题定义。ISN软硬件划分问题可定义如下：给定一个PCG={V,E,W,Fec,Oo}，在功耗/能耗和其他指标约束下，求解每个v∈V的任务在给定的最小功耗min(Fec(PCG))下的划分P(v)，使得式(3)成立，则P(v)为给定PCG={V,E,W,Fec,Oo}的一个最优划分解。P(v)为给定的软硬件划分函数，即P:v→W，且v∈V，是W中由硬件或软件实现的任务，若P(vi)=1，表示节点v由硬件实现，同样地，P(vi)=0，表示节点v由软件实现；min(Fec(PCG))≤Fec(PCG)≤Cg为描述的任务流程图的功耗/能耗不等式；Oo(PCG)≤Od为其他约束项加权不等式，Od为给定的加权值。

(3)

2 基于π网的低功耗软硬件划分模型

依据π网理论，可有效解决并发性的建模问题。ISN的低功耗软硬件划分问题，存在多种要求、多种约束的硬件、软件可选择组件，是一个典型的并发性问题。本文通过建立基于π网的低功耗软硬件划分模型来解决ISN的软硬件划分问题，并对模型进行动态演化分析。

2.1 模型建立

根据π网理论，建立基于π网的物联网ISN的低功耗软硬件划分LPHSP[9]模型,即NLPHSP。

定义4 物联网ISN的LPHSP模型为一个π网NLPHSP，NLPHSP=(Af,SIPo,Darc,Tτ)，Af为设计中的软硬件IP核实现的功能集合，是模型NLPHSP的库所集；SIPo为系统设计中软硬件IP核对应的功耗/能耗和其他约束项的集合，是模型NLPHSP的变迁集，使得Af∩SIPo=φ；Darc⊆(Af×SIPo)∪(SIPo×Af),是模型NLPHSP的有向弧集；Tτ是定义在Af∪SIPo∪Darc上的一个属性函数，表示物联网ISN设计中的各种约束评价因子所构成的函数关系。

由定义4可知，物联网ISN软硬件划分就是在IP核集合上做最优划分，该划分保证在Darc和Tτ条件下代价最小。

定义5 约束评价因子函数Tτ为一个八元组，用来表示各种评价因子间的相互关系，即

Tτ=(CL,Tr,Q,FC,FD,ID,Tt,B)

(4)

式中：CL={cl1,cl2,…,cln}，是有限的库所集，在此表示各种IP核的功耗/能耗和其他约束项的集合，即cli=SIPi∪SIPoi，其中SIPi,SIPoi分别为第i个IP核的功耗/能耗和其他约束项；Tr={Tr1,Tr2,…,Trn}，为有限迁移集合，且CL∪Tr≠φ,CL∩Tr=φ，表示由硬件IP核库所到软件IP核的变迁集合，反映ISN的动态迁移；Q={q1,q2,…,qn}，是有限的数据变迁集，qi为第i个数据变迁，且CL∩Tr=φ,CL∩Q=φ,Q∩Tr=φ，在此表示各IP核的成本；FC⊆(CL×Tr)∪(Tr×CL)∪(CL×Q)，是控制流的弧的集合；FD⊆(CL×Q)∪(Q×CL)∪(CL×Tr)，是数据流的弧的集合，表示硬件、软件IP核间的动态关系；ID:CL→X(X为非负整数集合),是位置集合上的标识向量，表示各种约束因子的优先级别；为迁移所需的时间，表示模型NLPHSP迁移为下一个变迁后的π网模型所需的时间；B表示其他评价因子。

定义4、定义5定义了物联网ISN软硬件划分LPHSP模型，其动态迁移规则参见文献[7]。

由此，可得到模型NLPHSP的软硬件划分算法步骤如下：

第1步：输入、输出和约束条件设置。输入设置：ISN-DAG及模型NLPHSP的初始条件、候选IP核库所、约束条件；输出设置：符合约束条件的划分集合，并进行最优化处理；约束条件设置：按照式(3)设定。

第2步：初始网。按照输入的ISN-DAG及约束，得到初始π网。

第3步：初始网演算。依据π网理论，在初始输入设置下进行初始π网演算。

第4步：子网划分。对初始π网进行变迁的使能与激发，得到中间π网依据约束条件进行库所、变迁的删减，得到最小网在中，计算变迁的最小时间及其对应的子网，直到得到子网N‴LPHSP中没有被2个变迁同时覆盖的变迁，否则继续进行子网划分。

第5步：得到NLPHSP模型。经过第3、4步，在约束下，对得到的子网N‴LPHSP进行评估，若符合约束条件，则得到模型NLPHSP，否则返回第3步。

第6步：模型NLPHSP的效用评估。对模型NLPHSP进行效用度计算，并将其与给定的约束条件中的效用度值进行比较，若其值小于约束中的效用度值，则返回第1步。

第7步：输出划分结果。符合约束条件的划分，输出划分结果，启用最优化处理。

第8步：得到最优的划分结果。从所有符合约束条件的划分输出中，采用多目标最优化处理方法，得到最优的结果，并以此作为物联网ISN的软硬件划分的最后结果输出；否则返回到第1步。

按照以上步骤，得到物联网ISN软硬件划分模型NLPHSP,如图3所示。图3中，左边为模型NLPHSP的库所、变迁在约束条件下进行软硬件划分的过程；右边为模型NLPHSP进行划分之后，得到选中的可选IP核构成的ISN模型。图3中，Datai为第i个库所的功耗/能耗等约束条件集合；Ei表示Af软硬件IP核实现的功能集合，是模型NLPHSP的库所集；ti为变迁集合，是模型NLPHSP中的SIPo，表示划分中的软硬件IP核对应功耗/能耗和其他约束项的集合；FMi为划分后得到的功能模块;Cji为第i个功能模块进行软硬件划分时得到的多种IP核集合；e1,e2表示对划分效用评估后重新返回模型NLPHSP的某个步骤。

图3 模型NLPHSP的划分结果与功能模块的映射关系
Fig.3 Partitioning results betweenNLPHSPmodel and mapping relation of functional modules

2.2 模型动态演化分析

应用π网理论，得到物联网ISN的LPHSP模型NLPHSP，还需利用π网理论对NLPHSP模型进行动态演化分析。动态演化即为模型NLPHSP增加新的库所或服务组件时，模型NLPHSP仍然能够保持良好的性能；若模型NLPHSP中某个库所发生了更新，或者被新的组件取代，则为更新演化。在此主要对模型NLPHSP进行库所增加和更新的演化分析。

若模型NLPHSP的库所Af有新库所s加入，可用如下进程进行描述，即进程NewPlace可描述为

newPCreate(id,s)=PCreate(id,s)

(5)

regPlace(id,s)=(id,s)(reg(id,s))

(6)

conregplace(x,y)=(x,y)(reg(x,y))

(7)

式(5)为库所创建进程，即创建了一个标志符为id、服务为s的候选库所；式(6)为库所注册进程，即库所通过通道reg传递其标志符id和服务s到候选库中；式(7)为库所在候选库中的注册进程，即库所通过通道reg获取新库所的注册信息x和y，同时更新其知识库Kp。只有式(5)—式(7)同时成立时，才能进入模型。

模型NLPHSP的库所Af有新库所s加入后，需要参与模型NLPHSP的各种变迁，可用NewPlaceP进程来描述变迁的加入，即

(8)

QueserPro(i,r,p)=i(y)([y=a]r<p>+

(9)

(10)

式(8)为请求服务的进程,通道新候选IP核通过通道i发送请求a到库所,然后通过通道r等待库所回复,一旦收到应答标志z,就通过z发送请求服务地址l到库所。式(9)为连接件中相应的服务查询进程,p为进程；式(10)为服务提供进程。只有式(8)—式(10)同时成立时，才能进入模型。

模型NLPHSP的库所Af有新库所s加入后，s为不完备时，则用π网的弱时间等价关系可将式(9)改写为

QueserPro(i,r,p,Rf)=i(y)([y=a]r<p>+

(11)

式中Rf是在定义5的八元组上对时间的抽象与进程Qf的弱时间等价。

由此，模型NLPHSP可进行库所添加，而且加入新库所后，新库所能够和与之适应的服务组件进行交互，从而参与模型NLPHSP的变迁。

若模型NLPHSP的库所Af要进行变化或升级，则需对原库所进行语义更新和扩展更新[10]。对模型NLPHSP的库所Af进行语义更新时，其更新规则为规则1。

规则1 设候选IP核Cp,0的接口为Ψ，组件Cp,1的接口为Ω，若Ψ≈Ω成立，并∃β和M，有βΨ+M≈βΩ+M成立，则称Cp,1可使Cp,0进行保持语义更新。

若模型NLPHSP的库所Af需进行扩展更新，利用规则2对原有库所进行扩展更新。

规则2 设候选IP核Cp,0的接口为Γ，Cp,1的接口为Π，若Γ和Π使以下条件同时成立:①fn(Γ)⊆fn(Π)，即Γ的自由名字是Π自由名字的子集；② 如果τΓ→Γ′，那么∃Π′，Π⟹Π′;③ 如果那么∃果那么∃则进程Π对Γ进行了扩展性更新，标记为Γ Π。故Cp,1对Cp,0进行了扩展性更新。

综上分析可知，当模型NLPHSP有新的IP核加入时，经过模型NLPHSP的库所创建进程、库所注册进程和库所在候选库中的注册进程而融入模型NLPHSP，成为模型NLPHSP的一部分。因此，模型NLPHSP能够对库所Af进行增加和更新，即模型NLPHSP能够进行动态增加和更新演化。

3 实验与仿真

以具体物联网ISN为例，对模型NLPHSP进行验证与优化[11]。

以温度湿度感知采集节点为例，用模型NLPHSP对其进行描述，并按照模型步骤进行低功耗软硬件划分。候选IP核在此以硬件核和软件核来区分，并按照功能模块予以分类描述，即模型NLPHSP的库所由硬件库所和软件库所构成，且库所又按照功能来区别。多参数感知采集节点的库所Af={AHW,ASW}，其中AHW为硬件IP核，且AHW={Proc,Mem,Com,Sen,…}，Proc,Mem,Com,Sen分别为候选的处理器核、存储器核、通信核、传感器核，而每个候选硬件核又对应多个选项，如Proc可为MCS-51核、ARM7TDMI核、moto68K核和ARM Cortex Mx核等，Sen为按照感知信号的不同进行分类的候选传感器核集合，比如温度传感器核可为DHT11、金属热电阻、热电偶、DS18B20、铜电阻和热敏电阻等；ASW为软件IP核，即能够实现一定功能的软件核，如模块初始化程序、板级驱动程序、操作系统、网络协议和应用软件模型等。模型NLPHSP的变迁为SIPo，SIPo为库所IP核对应的功耗和其他性能指标约束集合。由此，温度湿度感知采集节点NLPHSP模型划分如图4所示。

图4 温度湿度感知采集节点NLPHSP模型划分
Fig.4 Partitioning ofNLPHSPmodel of temperature and humidity sensing acquisition node

实验测试时，ZigBee模块选用F8913D,WiFi选用CC2540,蓝牙采用RKi6000,处理器使用Cortex M系列,软件IP核采用标准C语言编写的功能核。测试时采用运行测试和源代码级程序分析相结合的方式，综合得到实验数据。在测试过程中，每种算法使用相同的面积、体积和其他参数，具体实验得到的数据见表1。

利用表1数据作为属性DAG-PCG，并输入NLPHSP模型、基于遗传算法[12-13]的模型、基于蚂蚁优化算法的模型[14]和基于禁忌搜索算法[15-16]的模型，利用Matlab编程仿真每个模型的适应度、划分运行时间和最小系统划分能耗，得到如图5所示的比较曲线。

(a) 适应度(b) 划分执行时间(c) 最小系统划分能耗

图5 模型NLPHSP与其他算法模型的适应度、执行时间和最小系统划分能耗的比较曲线
Fig.5 Comparison curves ofNLPHSPmodel and other algorithms model in fitness, partitioning execution time and minimum system partition energy consumption

本实验在一定的约束条件下优化其软硬件划分。从图5(a)可看出，与其他算法相比，当候选IP核增加时，模型NLPHSP的适应度曲线总的趋势是在增加，但适应度值较其他算法小，说明更加容易适应候选IP核数量的增加。从图5(b)可看出，在相同候选IP核下，模型NLPHSP软硬件划分执行时间比其他算法少，说明其运行速度比较快。从图5(c)可看出，随着候选IP核数量的增加，各模型执行时能耗均在增加，但模型NLPHSP的能耗增加量比较小，说明模型NLPHSP在能量消耗方面具有优越性。

实验及仿真结果表明，与基于蚂蚁优化算法、禁忌搜索算法和遗传算法的模型相比，模型NLPHSP在适应度、划分执行时间和最小系统划分能耗等方面具有一定的优越性和实用性[17]，可降低物联网ISN能耗，提高其续航能力。

表1 候选IP核参数及其实验数据
Table 1 Parameters of candidate IP core and its experimental data

功能模块IP核运行时功耗/能耗其他指标执行时间/μs适应度可用性处理器TI MSP43295 μA/MHz-0.999 70.999 1STM32L476100 μA/MHz-0.999 60.999 3Atmel SAML2135 mA/MHz-0.999 20.999 2Cortex M035 mA/MHz-0.999 90.999 5︙︙︙︙︙存储器ROM150 μA10～200.999 90.999 6RAM170 μA10～200.999 80.999 5Nor Flash9 mA10～200.999 30.999 4Nand Flash9 mA10～200.999 40.999 6传感器DHT113 mW150.999 50.999 7DS18B202.6 mW21 0.999 40.999 9湿度传感器1.8 mW32 0.999 20.999 5通信模块WiFi模块 发送接收 72 mW58.8 mW—0.999 10.992 6ZigBee模块 发送接收 96.1 mW91.7 mW—0.999 50.993 2蓝牙发送接收 60 mW60 mW—0.999 20.994 5软件IP核CSW1113 μW6370.995 90.934 3CSW28 μW4220.954 10.943 4CSW321 μW4830.921 30.920 1CSW4231 μW7490.956 20.957 1CSW5251 μW6980.934 20.934 1CSW6342 μW9720.967 10.967 3CSW7207 μW6530.957 30.931 4CSW8239 μW5490.923 50.936 7CSW9213 μW4970.991 20.923 5︙︙︙︙︙︙

4 结语

物联网ISN的低功耗软硬件划分的优劣直接影响节点的续航能力和网络寿命。首先对物联网ISN进行带约束定义，得到了ISN的约束模型；然后根据π网理论，建立了基于π网的物联网ISN软硬件低功耗划分模型，实现了依据软硬件IP核功耗和系统总体功耗约束下的低功耗软硬件划分，并对模型进行了演化分析；最后，与基于禁忌搜索算法和遗传算法等的模型进行了对比实验。分析与实验仿真结果表明，与基于禁忌搜索算法和遗传算法等的模型相比，该模型在适应度、划分执行时间和最小系统划分能耗等方面具有一定的优越性和实用性，可降低物联网ISN能耗，提高其续航能力。

参考文献(References)：

[1] SHI W J,WU J G,LAM S K,et al.Algorithms for bi-objective multiple-choice hardware/software partitioning [J].Computers & Electrical Engineering,2016,50(3):127-142.

[2] WANG R,HUNG W,YANG G,et al.Uncertainty model for configurable hardware/software and resource partitioning[J].IEEE Transactions on Computers,2016,65(10):3217-3223.

[3] OUYANG Aijia,PENG Xuyu,LIU Jing,et al.Hardware/software partitioning for heterogenous MPSoC considering communication overhead[J].International Journal of Parallel Programming,2017,45(4):1-24.

[4] BAHRI I,IDKHAJINE L,MONMASSON E,et al.Original articles: optimal hardware/software partitioning of a system on chip FPGA-based sensorless AC drive current controller[J].Mathematics & Computers in Simulation,2013,90(2):145-161.

[5] ZHANG Tao,ZHAO Xin,AN Xinqi,et al.Using blind optimization algorithm for hardware/software partitioning[J].IEEE Access,2017,5(99):1353-1362.

[6] 鄢小虎,何发智,陈壹林.求解大规模软硬件划分问题的爬山淘汰粒子群算法[J].东南大学学报(自然科学版),2017,47(2):225-230.

YAN Xiaohu,HE Fazhi,CHEN Yilin.Elimination particle swarm optimization with hill climbing algorithm for solving large-scale hardware / software partitioning problem[J].Journal of Southeast University(Natural Science Edition),2017,47(2):225-230.

[7] 曹木亮,吴智铭,杨根科.一类新型的模块化高级Petri网——π网[J].上海交通大学学报,2004,38(1):52-58.

CAO Muliang,WU Zhiming,YANG Genke.π-nets:a new modular high level Petri net[J].Journal of Shanghai Jiaotong University,2004,38(1):52-58.

[8] SHA E,LI W,ZHUGE Q F,et al.Power efficiency for hardware/software partitioning with time and area constraints on MPSoC[J].International Journal of Parallel Programming,2015,43(3):381-402.

[9] RIABI M,MANAI Y,HAGGGE J.Hardware/software partitioning approach for embedded system design based on genetic algorithm[J].International Journal of Scientific Research & Engineering Technology,2015,3(3):20-25.

[10] TALEB M,LECLERCQ E,LEFEBVRE D.Model predictive control for discrete and continuous timed Petri nets[J].International Journal of Automation & Computing,2018(2):1-14.

[11] CHAKRABORTY D,GUHA D,DUTTA B.Multi-objective optimization problem under fuzzy rule constraints using particle swarm optimization[J].Soft Computing,2016,20(6):2245-2259.

[12] 侯能,何发智.混合并行两步调整遗传策略的软硬件划分算法[J].华中科技大学学报(自然科学版),2017,45(12):39-45.

HOU Neng,HE Fazhi.Hybrid parallel genetic strategy with two-step adjustment for HW/SW partitioning[J].Journal of Huazhong University of Science & Technology (Natural Science Edition),2017,45(12):39-45.

[13] 朱峰军.多选择软硬件划分问题的算法研究[D].天津:天津工业大学,2014.

[14] 潘颖,阮文惠.基于改进蚁群算法的嵌入式系统软硬件划分[J].现代电子技术,2017,40(3):164-166.

PAN Ying,RUAN Wenhui.Embedded system hardware and software partition based on improved ant colony algorithm[J].Modern Electronics Technique,2017,40(3):164-166.

[15] 高健,李涛.三种软硬件划分算法的比较分析[J].计算机工程与设计,2007,28(14):3426-3428.

GAO Jian,LI Tao.Comparison and analysis of three hardware/software partitioning algorithms[J].Computer Engineering and Design,2007,28(14):3426-3428.

[16] 周立秋.可重构系统中的一种动态软硬件划分算法[D].长沙:湖南大学,2009.

[17] 焦素敏，王彩红，王学梅.应用于大规模SoC软硬件划分的多种群协同进化方法研究[J].计算机应用研究,2011,28(10):3690-3693.

JIAO Sumin,WANG Caihong,WANG Xuemei.Multi-group co-evolutionary method research:applied in large scale SoC hardware/software partitioning[J].Application Research of Computers,2011,28(10):3690-3693.