T_CI 164-2023 面向移动边缘计算的软件自适应卸载技术规范.docx

ICS 35.240.50 CCS L70CI团体标准T/CI 164-2023面向移动边缘计算的软件自适应卸载技术规范Standard on adaptively offloading the software for mobile edge computing2023-10-16 发布2023-10-16 实施中国国际科技促进会发 布T/CI 164-2023目 次前 言II面向移动边缘计算的软件自适应卸载技术规范11 范围12 规范性引用文件13.术语和定义14 针对自适应卸载的软件自动重构34.1 针对 OO 软件自适应卸载的程序自动重构34.2 针对 DNN 软件自适应卸载的程序自动重构45 计算卸载的开销评估55.1 OO 模型的开销评估55.2 DNN 模型的开销评估86 计算卸载的智能调度116.1 卸载方案的求解加速116.2 卸载方案在线决策算法13II前 言本文件按照标准化工作导则 第 1 部分：标准的结构和编写GB/T 1.1-2020 给出的规则起草。某些内容可能涉及专利，本文件的发布机构不承担识别这些专利的责任。 本文件由福州大学提出。本文件中国国际科技促进会归口。本文件起草单位：福州大学、福建师范大学、上海交通大学、北京大学、国网信通亿 力科技有限责任公司、厦门盈趣科技股份有限公司、长威信息科技发展股份有限公司、国 科联盟（北京）国际信息科学研究院。本文件主要起草人：陈星、陈哲毅、李鸣、张建山、林兵、钟浩、马郓、林晓康、罗 义旺、李金湖、陈建成、林志斌、陈征宇、黄炳裕、赵芳萱。本文件为首次提出。T/CI 164-2023面向移动边缘计算的软件自适应卸载技术规范1 范围本文件规范了面向移动边缘计算的软件自适应卸载的相关技术，包括针对自适应卸载 的软件自动重构、计算卸载的开销评估、计算卸载的智能调度等。本文件适用于解决电力物联网、智能家居、智慧生态等领域中存在的移动边缘环境下 软件自适应卸载的相关问题。2 规范性引用文件下列文件对于本标准的应用是必不可少的。凡是注日期的引用文件，仅注日期的版本 适用于本标准。凡是不注日期的引用文件，其最新版本（包括所有的修改单）适用于本标 准。ISO/IEC TR 23188:2020 Edge computing landscape ISO/IEC TR 30164:2020 Edge computing T/ZGTXXH 0102021 边缘计算总体架构与要求3.术语和定义下列术语和定义适用于本文件。3.1计算密集型任务 Compute-intensive task计算量远大于访问存储器、通信和输入输出的一类任务。3.2中间件 Middleware中间件是介于应用系统和系统软件之间的一类软件，它使用系统软件所提供的基础服务（功能），衔接网络上应用系统的各个部分或不同的应用，能够达到资源共享、功能共享的目的。3.3移动云计算 Mobile Cloud Computing, MCC移动云计算是指通过移动网络以按需、易扩展的方式获得所需的基础设施、平台、软2件(或应用)等的一种 IT 资源或(信息)服务的交付与使用模式。3.4移动边缘计算 Mobile Edge Computing, MEC可利用无线接入网络就近提供电信用户 IT 所需服务和云端计算功能，而创造出一个具备高性能、低延迟与高带宽的电信级服务环境，加速网络中各项内容、服务及应用的快速 下载，让消费者享有不间断的高质量网络体验。3.5服务器 Server服务器是计算机的一种，它比普通计算机运行更快、负载更高、价格更贵。服务器在 网络中为其它客户机（如 PC 机、智能手机、ATM 等终端甚至是火车系统等大型设备）提供计算或者应用服务。服务器具有高速的 CPU 运算能力、长时间的可靠运行、强大的 I/O 外部数据吞吐能力以及更好的扩展性。3.6面向对象 Object Oriented, OO面向对象的方法就是利用抽象、封装等机制，借助于对象、类、继承、消息传递等概 念进行软件系统构造的软件开发方法。3.7深度神经网络 Deep Neural Networks, DNN深度神经网络是机器学习(ML, Machine Learning)领域中一种技术，是一种具备至少一个隐藏层的，利用激活函数去线性化，使用交叉熵作损失函数，利用反向传播优化算法（随机梯度下降算法、批量梯度下降算法）进行学习训练（调整并更新神经元之间的权重） 的前馈神经网络。3.8怀卡托智能分析环境 Waikato Environment for Knowledge Analysis, WekaWeka 是一款免费的，非商业化的，基于 JAVA 环境下开源的机器学习以及数据挖掘软件。3.9决策树 Decision Tree决策树是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值 大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析T/CI 164-2023的一种图解法。3.10随机森林 Random Forest, RF在机器学习中，随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个 别树输出的类别的众数而定3.11R 语言R 是用于统计分析、绘图的语言和操作环境。R 是属于 GNU 系统的一个自由、免费、源代码开放的软件，它是一个用于统计计算和统计制图的优秀工具。3.12深度强化学习 Deep Reinforcement Learning, DRL深度强化学习将深度学习的感知能力和强化学习的决策能力相结合，可以直接根据输 入的图像进行控制，是一种更接近人类思维方式的人工智能方法。4 针对自适应卸载的软件自动重构针对 OO 模型和 DNN 模型，以对象实例和 DNN 层为卸载单元，实现自适应卸载使能机制。4.1 针对 OO 软件自适应卸载的程序自动重构为支持 Android 应用的计算迁移，需要将应用进行重构。图 1 展示了重构步骤，具体内容如下：图 1 重构步骤步骤 1： 检测哪些类是 Movable 的。对于给定的应用程序， 将 Java 类分为两类： Anchored 和 Movable。Anchored 类必须留在移动设备上，因为它们直接使用仅在移动设备上可用的一些特殊资源，例如显示的 GUI（图形用户界面），重力传感器，加速度传感器，5指纹传感器和其他传感器。除了 Anchored 类之外，剩余的类都是 Movable 类。步骤 2：使 Movable 类能够迁移。当迁移类时，将该类与其交互类之间的本地调用结构变为按需远程调用结构。如果迁移类调用 Anchored 类，则后者需要前者的代理。代理生成是将应用程序代码中所有对象创建方式转换成如下：（1）当目标位置是本地主机时，直接创建实例及其 ID，然后使用类名和实例 ID 生成代理；（2）当目标位置是远程节点资源时，本地将序列化参数（类 N 的完全限定类名，要创建的实例的目标位置和类实例的构造函数参数值）并将它们传输到远程。然后远程反序列化参数，并在远程节点资源上创建实 例及其 ID 和代理。然后，返回 ID，本地使用它来生成代理。步骤 3：检测哪些类应作为一个整体迁移。将经常交互的类应作为一个整体迁移。步骤 4：打包可部署文件。完成上述三个步骤后，打包 Android 应用程序的 Java 字节码文件以及引用的资源文件，例如图像，xml 文件和 jar 库，然后生成两个工件。第一个是重构的 Android 应用程序，即.apk 文件，可以安装在手机上。第二个是可执行 jar 文件，其中包含从重构的应用程序克隆的可移动 Java 字节码文件，能够在远程服务节点上运行。4.2 针对 DNN 软件自适应卸载的程序自动重构为支持 DNN 应用的计算迁移，需要对 Python 源码进行如下几个步骤的重构：步骤 1：入参准备。在传入初始化数据至 DNN 网络中时，新增参数 InitL、EndL 和CurrentL，分别表示当前节点处理的初始层标号和结束层标号以及 DNN 应用执行的进度。步骤 2：新增管道机制。新增方法 Pipe(i)于执行每一层 layeri之前，该方法决定layeri是否由当前节点的过滤器执行，对过滤器起激活作用，具体算法如下：算法 1: Pipe(i)算法Input：The configuration file of DNN layers config-file; The number of current DNN layer CurrentLOutput:Target layer information Declare:remote(,CurrentL, k) the remote execution,where k is the last layer on the remote Procedure pipe(x, config-file, CurrentL)1: if x CurrentLthenT/CI 164-20232:return3: end if4: if x= CurrentLand config-file x = LOCAL then 5:return CurrentL6: end if7: if x= CurrentLand config-file x.contains(REMOTE) then 8:transfer Output through RPC9:calculate the number of the next filter on the current node k10:layerk - 1 = remote(Output, CurrentL, k - 1) 11:return k12: end if End Procedurepipe()函数的入参包括卸载方案以及即将激活的 DNN 层序号 x。如果该计算节点不负责 DNN 层 x的执行，直接返回从而卸载 DNN 层(第 1-3 行)。如果当前计算节点负责DNN 层 x的执行，因此直接返回需激活的过滤器标号从而激活过滤器 x(第 4-6 行)。如果执行至当前位置，然而下一个待激活的 DNN 层为不在当前计算节点上时，先将上述参数Output 通过该管道的 RPC 机制传输并激活远程节点的过滤器（第 7-8 行)；在等待远程卸载的结果返回后，计算下一个在当前计算节点上执行的 DNN 层，并将接收到的远程执行结果赋值给 DNN 层的前序 DNN 层 k- 1(第 9-10 行)；最后，返回下一个在本地待激活的DNN 层(第 11 行)。步骤 3：新增过滤器。新增两个判断语句。第一个判断语句用以控制当前网络层是否执行，第二个判断语句用以包装并存储本次调用中最后一个网络层执行的结果。5 计算卸载的开销评估针对 OO 模型和 DNN 模型，基于程序静态分析技术从程序结构角度建立软件的高层抽象模型，然后针对代码片段建立具有高准确率的预测模型，以评估 MEC 中软件卸载方案的执行开销。5.1 OO 模型的开销评估要实现对 OO 模型的开销评估，需要三个步骤：（1）应用程序的权重调用图提取；（2）预测模型的构建；（3）卸载方案评估。5.1.1 应用程序的权重调用图提取8根据 Android 应用程序的 main 方法，通过 Soot 工具去建立应用程序的权重调用图，具体流程如算法 2 所示。算法 2: 权重调用图生成算法Input：rrrrA main method mr ,its statement UOutput:= u1 , u 2 , ., un ;A weighted call graph Gp = (M , R)1:M M + mr2:R rr3: for each ui U dor4:keywords Soot(ui )5:if $invoke keywords then6:ms getMethodName (keywords )7:M M + ms 8:if mr ms R.key then 9:+ + rrs10:else11:12:rrs 1R R + rrs13:end if14:mr ms15:end if16: end for使用哈希图来存储边， 它的密钥格式为 mi mj ， 其中 mi 表示 mj 的后继。集合rrrrrrrrU = u1 , u 2 , ., un 表示方法 m 中的所有语句，每个ui U 表示U 中的第 i 个语句。第3 行遍历U ，对于每个元素，第 4 行使用 Soot 提取中 ui 的关键字。这里的关键词是由rrSoot 定义的指令，例如，关键字 JAssignStmt 表示赋值语句；关键字 JReturnStmt 表示方法的返回语句；关键字 JGotoStmt 表示跳转语句；而关键字 invoke 表示一个方法调用。对于T/CI 164-2023每个方法调用，第 6 到 14 行根据关键字更新集合 M 和 R 。如果边 mr ms 已经存在，则对应的值 rrs 加一，否则将边记录到 R 中。更新后，输入被调用方法 ms ，再次执行第 3 行。除了调用关系之外，对于每个方法，还需要提取块深度、语句数及其复杂度等特征。10Mij = ， 其中 blockDepth 表 示 函 数 的 深 度 ， 计 算 为 mi中 分 支 的 嵌 套 级 别 。percentBranchStatements 表示分支语句的比例，即 if、for、while 和 switch 等分支语句 占总语句的比例。complexity 表示 mi 中的路径数，其计算公式为： complexity =e - n +2 ，e 为控制流图的边的数量， n 为控制流图的节点数； statements 表示方法的语句数， calls表示方法内部调用的次数；5.1.2 预测模型的构建通过设定以下参数，构建预测模型：（1） 模 型 输 入 ： complexity ， blockDepth ， statements ， calls ，percentBranchStatements 。（2） 模型输出：方法的执行时间（3） 随机森林的类型：回归（4） 模型参数设定：基于回归树的数量（ Ntree ）设置为 50，决策树分支时随机抽样的变量个数（ Mtry ）设置为 3在构建好预测模型后，使用 5 个以上的 Android 应用，每个应用需要包含至少 4 个方法。将这些应用抽取到的特征信息，以及在计算节点上执行收集到每个方法的执行成本作 为数据集。其中，70%用作训练集来训练通过上述参数构建好的模型，另外 30%作为验证集来判断模型的准确率。表 1 展示了 OO 预测模型的数据集样本作为样例。表 1 OO 预测模型数据集样本方法complexityblockDepthstatementscallspercentBranchStatementTime(ms)Grey.clear ()4251280.07823207.27Detect.detect()105028022734.94Compare.get ()43134770.0371302.265.1.3 卸载方案评估5.1.3.1 方法执行成本评估将在 n 节点上执行 m 方法的执行成本表示为 Einvokemi =Etime, EdataSize ，其中kinkEtime 表示从第一个语句开始的执行到最后一个语句结束的时间，通过 5.1.2 构建的预测模型，就可以通过参数作为输入得到对应方法的执行时间； EdataSize 表示数据传输量，通过执行过程中可以直接分析得到。进 一 步 ， 将 在 计 算 节 点 nk上 执 行 的 方 法 mi的 净 成 本 定 义 为nSinvokemi =kStime, SdataSize ，其中 Stime 表示执行时间， SdataSize 表示在nk 中执行的方法 mi 中除了外部调用的所有数据传输量，具体计算如下：nknkSinvokemi = Einvokemi -mj Post (mi )nkijEinvokemi * r其中 rij 表示从 mi 到 mj 的方法调用的频率， Post(mi ) 表示 mi 的所有后继。5.1.3.2 整体卸载方案评估基于 5.1.3.1 得到的数据，在给定方案下的应用程序响应时间计算如下：nobjTresponse = T (obji ), obji OBJobj0OBJ = obj0 , obj1,., obji 表示对象的集合，其中， T (obji ) 计算如下：T (obji ) = Te (obji ) + Td (obji )其中， Te (obji ) 表示obji 的执行开销， Td (obji ) 表示obji 的传输开销，计算分别如下：eidep(obji )piT (obj ) = (Sinvokeinvokepi .callee .Stime *invokedep (obj )Sinvokeinvokepi .callee .SdatasizeT (obj ) =(i+ rtt.invokeTimes) *invoke invokeTimes)vdipidep (obj )dep (obj )dep (obj p )dep (obj i )pi .其中， objp OBJ 是obji 的调用者，并且invokepq 应满足约束q = i, invokepq INVOKE 。5.2 DNN 模型的开销评估5.2.1 应用程序的结构提取T/CI 164-2023训练后的模型存储于原型配置文件中，算法 3 将该文件作为输入，实现抽取 DNN 模型结构。算法 3: DNN 模型结构抽取算法Input：The statements of Python code U = u1, u2, , unOutput:A DNN model graph GD = (L, R)1: L 2: R 3: for each uiUdo4:keywords DNN Analyzer(ui) 5:ls getLayerName(keywords)6:if Convolutionkeywordsthen7:ls.type conv8:else if poolingkeywordsthen 9:ls.type pooling10:else if ReLUkeywordsthen 11:ls.type relu12:else if InnerProductkeywordsthen 13:ls.type fc14:end if15:ls.feature getParam(keywords) 16:if bottom:datakeywordsthen17:R R+ r0s18:else19:lt getBottom(keywords)20:R R+ rts21:end if22:L L+ ls23: end for该文件中的语句表示为 U = u1,u2,un，其中，语句uiU 表示文件中的第 i 条语句。对 U 集合进行迭代，对于每个元素，提取ui 中的关键字(第 3-4 行)，这里的关键字包括12“Convolution”, “pooling”, “ReLU”和“InnerProduct”。 (第 5 行)，根据关键字保存各层的类型(第 6-14 行)，然后根据类型保存对应的特征参数(第 15 行)。接着，根据关键字“bottom”更新 R 集(第 16-21 行)。最后，更新 L 集合(第 22 行)。除了调用关系之外，对于每个神经网络，还需要提取对应的特征。其中，conv 表示为卷积层， relu 表示为激励层， pooling 表示为池化层， fc 表示为全连接层。当type = conv 时， name channel, ksize, knumber, stride, padding ，channel 表示卷积层的特征定义频道数，ksize表示卷积层的卷积核尺寸，knumber表示卷积层的卷积核数量，stride 表示卷积层的移动步长，padding 表示卷积层的填充值；当 type = relu 或 type = fc 时， name innumber, outnumber ，innumber表示激励层或全连接层的输入神经元的数量，outnumber 表 示 激 励 层 或 全 连 接 层 的 输 出 神 经 元 的 数 量 ； 当 type = pooling 时 ， name channel, ksize, stride ，channel 表示池化层的输入通道维度，ksize表示池化层的区域大小，stride 表示池化层的移动步长。5.2.2 预测模型的构建通过设定表 2 中的参数，构建不同类型的神经网络的执行成本预测模型：表 2 神经网络预测模型的定义神经网络类型模型输入NtreeMtryconvchannel, ksize, knumber20003poolingchannel, ksize, stride15002reluinnumber, outnumber30002fcinnumber, outnumber5002在构建好预测模型后，使用 6 个以上的 DNN 应用。将这些应用抽取到每层神经网络的特征信息，以及在计算节点上执行收集到每层神经网络的执行成本作为数据集。其中，70% 用作训练集来训练通过上述参数构建好的模型，另外 30%作为验证集来判断模型的准确率。表 3 展示了 conv 预测模型的数据集样本作为样例。表 3 conv 预测模型的数据集样本sample No.channelksizeknumbertime(ms)1311961442965256183325633842005.2.3 卸载方案评估5.2.3.1 神经网络执行成本评估T/CI 164-2023一个 DNN 层l在某一计算节点n 上的执行成本表示为Costli = ，其中，iknktime 表示从接收输入数据到生成输出数据过程的执行时间，这取决于计算节点的性能，通过 5.2.2 构建的预测模型，可以对这个值进行估计；datasize 表示输出数据的数据量大小。5.2.3.2 整体卸载方案评估基于 5.2.3.1 中得到的数据，当给定一个卸载方案 DEP=(dep(l1),dep(l2),dep(ln)时候，能够得到一个 DNN 应用程序的响应时间Tresponse，具体计算如下：Tresponse= tn其中，ti是执行完 DNN 层li的时刻，最后一层ln执行完成的时刻即为总体响应时间。每一 DNN 层的ti计算如下述公式所示：t = maxtl + T (pli, l) + T(l), pliPli14piid j ije ijj执行完当前层li的时刻的计算由两部分组成，一部分是该层的执行时间Te(li)，另一部 分是所有父层pliPli执行完并将数据发送至当前层的时间。当前层li的执行时间()，以及与父节点pli的数据传输时间Td(pli, li)分别计算如下：jjdep(li)jTe(li)=Costli.time Costpi.datasizejjT(pli,l)=+rttd j ivdep(pi)dep(li)dep(pi)dep(li)其中， Costli.time 和Costpi.datasize 由 5.2.3.1 部分估计得到， v和jdep(l)dep(pi)dep(l)ijijrttdep(pi)dep(li)分别表示父节点和当前节点所在的计算节点执行的传输速率以及传输时延。6 计算卸载的智能调度为满足自适应卸载的实时性需求，需要两方面的工作：一方面，使用图划分操作对应 用程序的任务图进行预处理，降低任务图编码维度，从而减少启发式算法的执行时间（6.1 部分）；另一方面，采用强化学习算法训练决策模型，当环境资源变化时，由决策模型进行决策，使得能在毫秒级生成新的卸载方案。（6.2 部分）6.1 卸载方案的求解加速算法 4 显示了 DNN 的具体划分过程，其中输入是原始 DNN，输出是具有部署单元的DNN。算法 4: DNN 预划分Input：The original DNN NiOutput:The DNN N j1: beginwith deployment units.2:Divide different branches in Niki3:foreach module M i N dointo isolated modules4:/Initialize the set of partition points.5:Pk = M6:/Initialize the current layer and the index to the first andksecond layers of7:cur = 18:ind = 2i respectivelyMk9:while ind i do10:lleft = lcur ,.,lind -1;11:lright = lind ,.,lM;i k12:/U ( x, y) decides whether x and y are suitable to bepartitioned according to the fitness function defined in Eq. (16).13:pk = U (l,l); indleft rightp14:ifk indthen15:P = P pk ;16:17:kkindcur = ind ; ind = cur + 1;18:end19:else20:ind + = 1;21:end22:endT/CI 164-202323:/Based on the original module and the set of partition points,D(x; y) combines the layers between every two adjacent partition points into a deployment unit, and generates a new module.kkk24:M j = D(M j , P );25:end26:N = M j; /Generate a new DNN.18j27:return28: endkkN j ;DNN 中的不同分支首先被划分为独立的模块（第 2 行）。对于每个模块，当前层被初始化为起始层（第 6-8 行）。从当前层开始，每两个相邻层将根据适应度函数进行有序检查。（第 10-13 行）。一旦找到分区点，当前层将更新到该分区点之后的下一层（第 14-21 行）。将重复上述过程，直到检查 DNN 中的最后两个相邻层。最后，将每两个相邻分区点之间的层组合成一个部署单元（第 23-24 行）。6.2 卸载方案在线决策算法基于深度强化学习（DRL）的任务卸载决策模型可以实现在环境变化时快速完成决策 过程并生成新的卸载方案。决策过程包括两个步骤：首先，在运行时环境中使用 DQN 算法训练卸载操作 Q 值预测模型；然后，根据得到的卸载操作 Q 值预测模型寻找合适的卸载方案。6.2.1 卸载操作 Q 值预测模型卸载操作 Q 值预测模型的构建过程如算法 5 所示。算法 5: 基于 DQN 的云边缘环境卸载操作预测Input：F and VOutput:The Q-value prediction model. Initialize:The replay memory with the capacity M , the discount factor g, thelearning rate of the Adam optimizer a, the weight w of “EvalNet”, and the weight w = w of “TargetNet”.1: begin2:foreach epoch do3:Initialize the current offloading planget the current T ;DEPcur = (1, 0,., 0) and4:Generate the current state s = (F,V , DEPcur ) ;5:while not all tasks have been completed in s do 6:Select an action a by using the 𝑔𝑒7:Execute a and obtain the new response time T ;8:Calculate the reward r = T -T and update the current response time T = T ;9:Receive the next state s = P(s, a) ;10:Store (s, a, r, s )into the replay memory;11:Draw samples , , , |1 from the replay memory and calculate:, _ = + , ; , 𝑔 12:Update the weight w of ”EvalNet” by using the Adam optimizer according to the loss function:Loss = 1 (_𝑔 ( , ; )2=113:Update the weight = of “TargetNet” every iterations;14:Update the current state = ; 15:end16:end17: end首先，随机初始化神经网络的权重、神经网络的权重 = 。对于每个训练周期，当前卸载方案、当前状态 =和当前响应时间都会初始化(第 34 行)。在算法训练过程中，通过 𝑔𝑒策略依次决定每个子任务的执行位置，以的概率从所有的卸载方案中随机选择一个，以 1 的概率选择中 Q 值最大的卸载方案(第 6 行)。接下来，执行动作并获得新的响应时间，计算奖励并更新当T/CI 164-2023前响应时间，观测到下一个状态（第 7 行）。之后，将(, , , )放入经验存放池中，并随机抽取经验池中的 m 个