计算卸载作为MEC中的关键技术，文献［7］指出：在网络条件良好的情况下，数据量小但计算密集的任务卸载到服务器上执行可以降低时延。而这并非是从用户角度得出的结论，且仅仅揭示了对时延的影响。文献［8-9］提出的两种多目标算法对单峰问题或多峰问题处理能力不佳。文献［10-11］在原始粒子群算法的基础上设计了新的重组策略，一定水平上克服了对多峰问题处理效果不佳的缺点，但算法复杂度增加。蔡昕烨等［12］提出使用聚类算法将多目标优化问题进行划分，算法性能将直接受划分结果影响。为了提高搜索效率和搜索质量，梁正平等［13］选取高质量解作为种群进化的方向，使得解成为影响算法性能的重要因子。考虑到上述研究的不足，本文对单用户多任务MEC场景下的计算卸载问题进行建模，由于应用服务请求的多样性，MEC服务器需先对服务请求进行缓存。基于此，计算卸载过程可抽象为服务缓存、任务卸载两阶段。本文利用化学反应优化（chemical reaction optimization，CRO）算法解决服务缓存问题，利用改进化学反应优化（improved chemical reaction optimization，ICRO）算法来解决任务卸载问题。传统的CRO算法是一个最优化计算框架，其基本思想为：首先定义一些通用的操作代理（分子）和能量管理方案，通过不断迭代来找寻具备最优能量的分子，此过程中可通过设置分子分裂和重组的方式来适应环境，提高迭代效率。该框架的核心是分子的定义、分子间裂变的化学反应方式和熵或潜在能量的定义（即目标函数的定义）［14］。ICRO算法在继承CRO算法基本框架的基础上，有如下优点：（1）减小了CRO算法中随机概率对反应类型的影响，分子反应更加合理；（2）引入了新的分子基本反应，算法全局开发能力更强。
1 系统模型
单用户多任务边缘计算应用场景主要包括3个部分：移动终端、无线信道和边缘服务器。移动终端为应用服务请求的产生源，请求通过无线信道传输；在接收请求并同意后，边缘服务器将首先确定服务缓存集合，然后根据任务二进制卸载［15］决策，接受卸载的服务器将完成卸载过程，卸载结束后，应用服务请求的执行由移动终端（本地执行）和服务器（卸载执行）来完成，整个过程如图1所示。
<G:\武汉工程大学\2023\第4期\刘凌志-1.tif>[应用程序][服务器][迁移执行][本地执行][用户设备] [3] [6] [9] [7] [8] [9] [4] [5] [6] [1] [2] [3] [7] [8] [4] [5] [1] [2]
图1 移动边缘计算卸载场景
Fig. 1 Offloading scenario of MEC
1.1 服务缓存
应用程序的每个任务都属于一个确定的服务类型，集合M=｛m1，m2，m3，…，mn｝表示n种类型的服务。
服务器缓存的服务集合质量直接影响到最终的任务卸载决策，如图2所示，应用程序由4种服务类型的任务构成，服务器缓存了m1、m2两种类型的服务，表示只有属于这两种服务类型的任务能卸载到服务器上，服务类型属于m3、m4的任务也只能在本地执行。
服务类型的价值越大越有可能被缓存，第n类服务mn的价值定义如下：
[An=j=1tdi, jCni, jj=1tdi,j×Gnit] （1）
t为应用程序的任务数，di，j表示应用程序i中任务j的数据量，[Cni, j]表示应用程序i中任务j是否属于第n类服务mn，[Gni]表示应用i中属于服务mn任务的个数，其中：
[Cni,j=1 μi,j∈mn0 μi,j?mn] （2）
假设服务器容量为V，第n类服务mn的体积为vn，缓存集合Θ=｛Θ1，Θ2，…，Θm｝，由于进入缓存队列的服务应小于缓存最大容量，则有：
[Θm∈Θvn≤V] （3）
由式（1）-式（3）分析可知：缓存结果由匹配度、服务大小和缓存最大容量3个因素共同决定。
1.2 最优卸载模型建立
服务缓存结束后，系统进入最优卸载模型建立阶段，将为每个应用程序分配边缘服务器和无线信道，i个应用程序等待分配资源，则计算卸载资源集合为：
[Λ=Λ1, Λ2, ..., Λi] （4）
s.t. [Λi=Di, Zi] （5）
[Di∈D?0] （6）
[Zi∈Z?0] （7）
其中，第i个应用程序分配的MEC服务器与无线信道分别为[Di]、[Zi]，服务器集合D={1，2，…，d}，无线信道集合Z={1，2，…，z}，第i个应用程序的资源集合[Λi]={0，0}表示其将在本地执行。
1.2.1 通讯模型 当任务选择卸载到服务器执行时，终端通过无线信道将执行任务所需数据上传至边缘服务器，一个应用程序包含的所有任务仅能选择卸载到一个服务器上，所以要求设备选择单个无线信道与单个服务器建立通讯，运用香农公式［16］，带宽为B的无线信道传输速率为：
[v=Blog21+PHσ] （8）
其中，P为设备的发射功率，H为与输入输出无关的信道增益，σ为外界影响的噪声功率。通信过程中的时延和能耗分别为：
[ttransi,j=di,jv] （9）
[Etransi,j=ttransi,j×P] （10）
1.2.2 计算模型 终端设备请求的任务可以用一个二元组[μ]i，j=｛di，j，Фi，j｝来表示，其中Фi，j为应用程序i的任务j所需的CPU周期，di，j为应用程序i的任务j数据量，任务可以选择在本地执行或边缘服务器执行，对应的计算模型分别为：
（1）本地计算模型。终端设备执行任务所需时间和能源消耗为：
[tloci,j=Φi,jfloc] （11）
[Eloci,j=κlocΦi,j] （12）
其中， floc表示移动设备的一个CPU周期，κloc表示一个CPU周期的能耗。
（2）边缘服务器计算模型。边缘服务器执行任务所需时间和能源消耗为：
[toffi,j=Φi,jfoff] （13）
[Eoffi,j=κoffΦi,j] （14）
其中，foff表示服务器的CPU周期，κoff表示由硬件决定的边缘服务器每CPU周期的能耗。用户并不在意边缘服务器的能耗，因此在本模型中可以不纳入考虑范围。对于一个任务[μ]i，j，根据式（9）-式（14）推导出时延和能耗分别为：
[Ti,j=tloci,j Λi=0,0ttransi,j+toffi,j Λi≠0,0 ] （15）
[Ei,j=Eloci,j Λi=0,0Etransi,j Λi≠0,0] （16）
对于一个由t个任务组成的应用程序ψi，根据式（15）和式（16）计算出应用程序ψi的平均任务时延和能耗分别为：
[Ti=j=0tTi,jt] （17）
[Ei=j=0tEi,jt] （18）
1.3 卸载优化目标
研究的优化目标将通过设置权重来兼顾任务平均完成时间与设备终端的能耗，使用多目标优化可以在两者之间得到协调［17］，对于每一种任务卸载策略S，适应度函数（其值为分子势能）可由式（19）表示：
[f(S)=α×Ti+β×Ei] （19）
[α∈0,1] （20）
[β∈0,1] （21）
[α+β=1] （22）
其中Ti代表应用程序ψi中所有任务的时延平均值，Ei代表应用程序ψi完成终端设备所耗费的能源平均值，ɑ和β为个性化因子。当ɑ=β时，优化目标兼顾时延与能耗，当ɑ>β时，优化目标向时延倾斜，反之，则向能耗倾斜。分子势能越小，代表优化效果越理想。
2 问题解决
单用户多任务边缘计算应用场景中，遵循先来先服务的原则为应用程序指定空闲的服务器提供服务，服务器在缓存服务后确定卸载策略并执行任务，每一个应用程序执行完毕后，提供服务的服务器清空缓存，将剩下的应用程序分配给最先空闲的服务器，这一过程持续到应用程序全部执行完毕。如图3所示。
2.1 服务缓存问题
服务缓存阶段将选取最具价值的服务进行缓存，将服务缓存过程抽象为一维的0-1背包模型［18］。本文采用CRO算法解决这一问题。缓存区（背包）的最大存储空间为VM，第i类服务（物品）的价值记为Ai。现共有N类服务，要求在存储允许的前提下使得缓存服务的总价值最大。将最大值问题转化为最小值问题后，该问题可由式（23）-式（25）表示：
[F=N-maxi=1NxiAi] （23）
[i=1Nxivi≤V] （24）
[xi∈0, 1,?i∈(1, 2, ..., N)] （25）
反应产生的新分子可能会违反约束条件，因此引入修复函数来使违约解转化为可行解。修复操作具体包括两种相反的操作：第一种操作目的是使背包容量最大化利用，具体方法是依据价值容量比降低的次序检查每个变量xi，只要不超出背包的最大容量，就将变量的值0重置为1。第二种操作目的是减少装入物品，使非可行解转化为可行解，如果超出背包容量，随机将一个值为1的变量置为0。伪代码如下：
算法1. 修复算法
输入：原分子S
输出：经修复算子处理后的分子S’
1. p=V -∑xivm
2. i=1
3. while（p>0 & i≤n）
4. if（p≥vm）
5. xi=1；p=p-vm；i=i+1；
6. end if
7. end while
8. k=∑xivm-V；
9. while（k>0） ；
10. xi=0；k=k-vm；
11. end while//减少阶段结束
12. S←S’
采用CRO算法解决服务缓存问题伪代码如下所示：
算法2. CRO算法解决服务缓存问题
输入：终端应用程序信息、服务器缓存容量
输出：最优缓存策略
1. 初始化算法参数
2. for j=1 to IniPopSize//种群初始化
3. Random（S） ；//随机生成一个分子S
4. computeValue（S）； //计算价值（势能）
5. computeVolume（S）；//计算已用空间
6. 初始化动能
7. 满足约束，则将新策略添加到策略集中
8. end for
9. while IniPopSize<=j<=PopSize
10. t←random（0，1）；
11. if t>Ω //将发生单分子反应
12. if checkDecomp（S） then
13. decompose（S，s1，s2）；//单分子分解
14. else
15. ineff_coll_on_wall（S，s）；//单分子碰撞
16. 如果新分子s1，s2，s不满足约束，调用修复函数产生新分子，并将新策略添加到策略集中，更新当前分子数。
17. else //发生多分子反应
18. if checkSynth（S1）&checkSynth（S2）
19. synthesis（S1，S2，s）；//分子合成
20. else
21. ineff_wall（S1，S2，s1，s2）；//多分子碰撞
22. 重复步骤16
23. 更新势能
24. end while
25. 将最小势能分子转换为缓存策略并输出
2.2 任务卸载问题
服务缓存策略解决的是任务是否有资格卸载这一问题，卸载决策需要考虑网络链路质量、终端设备性能、边缘服务器性能等因素的影响 ［19］。与解决服务缓存问题时不同，化学反应函数中加入了奖惩机制，该机制只有在种群分子数达到一定要求后才被激活，改进的化学反应函数如图4所示。
与CRO算法中原始化学反应函数不同点在于：
1）定义两种反应的成功率之差为偏移值τ（初始为0），将其引入与Ω共同控制两类反应发生机率，减少随机概率对反应类型的影响，即Ω’=Ω+τ；
2）引入新的基本反应类型，分子结构变化较大将更有效地避免陷入局部最优的窘境，因此将双分子碰撞反应改为置换反应。
ICRO算法解决卸载决策问题伪代码如下：
算法3. ICRO算法解决卸载决策问题
输入：请求服务的应用程序
输出：最优卸载策略
1. 初始化算法参数
2.for i=1 to IniPopSize
3. Random（S） //随机生成一个分子S
4. computePE（S）//计算分子势能
5. 初始化动能
6. 如果满足约束，卸载策略S加入缓存集
7.end for
8.while MinNum<i<MaxNum
9. 调用改进化学反应函数，新解加入策略集
10. 根据各类反应总次数、成功次数计算出τ及下轮迭代Ω新值。
11.end while
12.while MaxNum≤j≤PopSize&j<MinNum
13. 调用原始化学反应函数，新解加入策略集
14. 重复步骤10
15.end while
16. 输出最小势能值及其最优策略
3 仿真实验
3.1 参数设置
为验证提出策略的有效性，在内置英特尔 i5 8250U处理器、主频率1.60?GHz的64位操作系统下使用Vistual Studio 2010平台进行了相关仿真实验，获得实验结果。
在实验场景中，服务器与设备的之间的传输速率v最大为10?MB/s，设备的发射功率P为3?W，终端设备CPU频率与MEC服务器CPU周期均为10-6?s，设备每个CPU周期能耗为0.3?J，边缘服务器每个CPU周期能耗为0.6?J。在无特别说明时，ICRO相关参数设置如下：个性化因子ɑ=β=0.5，初始化种群分子数IniPopSize为种群最大分子数PopSize的0.1倍，反应类型阈值Ω设置为0.2，初始化动能InitialKE为100，碰撞动能损失率KELossRate取0.8。
为验证算法有效性，选取本地计算（local computing，LC）、服务器计算（server computing，SC）、CRO三种卸载方法作为对比方法，在应用完成延时、能耗、分子适应度等算法评价指标上开展相关对比实验。
3.2 仿真结果及分析
为优化算法性能需选取种群最大分子数PopSize最优值，以分子适应度为衡量标准进行了相关实验。图5展示了ICRO算法参数PopSize与分子适应度的关系，图6展示了个性化因子比值（ɑ/β）对任务卸载率的影响，图7展示了CRO算法与ICRO算法对目标函数优化的结果。
<G:\武汉工程大学\2023\第4期\刘凌志-5.tif>
图5 种群最大分子数对适应度的影响
Fig. 5 Effects of PopSize on fitness
<G:\武汉工程大学\2023\第4期\刘凌志-6.tif>
图6 个性化因子对任务卸载率的影响
Fig. 6 Effects of personalization factors on task
offloading rates
<G:\武汉工程大学\2023\第4期\刘凌志-7.tif>
图7 目标函数优化结果比较
Fig. 7 Comparison of objective function optimization results
图5实验结果显示：任务数为300时，分子适应度在横坐标30?000左右收敛；任务数为250时，适应度在横坐标25?000左右收敛；任务数为200时，适应度在横坐标值20?000左右收敛。 由此可以得出结论：PopSize与分子结构的点位数（任务数）有关，前者约为后者的100倍为最优。图6表明ICRO算法收敛速度更快，对个性化因子ɑ、β更加敏感，卸载率的变化范围更大。图7结果显示ICRO算法对适应度的优化结果更理想，分子适应度在CRO算法的优化基础上平均再下降了5.0%左右。图8展示了4种方案的时延优化结果，此时取ɑ=0.9，β=0.1。图9展示了4种方案的能耗优化结果，此时ɑ=0.01，β=0.99。
<G:\武汉工程大学\2023\第4期\刘凌志-8.tif>
图8 各方案延时
Fig. 8 Delay of each scheme
<G:\武汉工程大学\2023\第4期\刘凌志-9.tif>
图9 各方案能耗
Fig. 9 Energy consumption of each scheme
虽然CRO算法对时延与能耗已有了明显的优化，但随着任务数的增多，时延与能耗也有了明显的上升趋势，ICRO算法结果曲线较平缓，随着任务的增加，时延与能耗的上升幅度较小，仿真结果更加理想，系统时延、设备能耗最低分别可降为极端情况下的33.3%、53.8%。
图10展现了服务缓存比例与服务类型数、缓存空间的关系，图11展示了特征任务对卸载率的影响。
<G:\武汉工程大学\2023\第4期\刘凌志-10.tif>
图10 服务缓存比例结果
Fig. 10 Results of service caching ratios
图10结果表明算法基本不受服务类型数量影响，较为可靠，且具有良好的收敛性。当可用缓存空间远小于存储所有服务类型所需空间时，所占空间小的服务被优先考虑缓存。更多的服务被缓存意味着更多的任务可以选择卸载，防止缓存区可用容量太小时只有少量服务被缓存，进而影响后续卸载决策制定的情况发生。图11结果显示计算密集型任务更适于卸载到服务器上执行，而通讯密集型任务恰好相反，因通讯成本高更倾向于本地执行，第三类任务无论选择本地执行还是卸载到服务器上执行成本差别不大，卸载率均在0.5左右。
<G:\武汉工程大学\2023\第4期\刘凌志-11.tif>
图11 任务特征对卸载率的影响
Fig. 11 Effects of task characteristics on offloading rates
4 结 论
本文针对单用户多任务场景，在建立计算卸载模型后，利用CRO算法解决服务缓存问题，提出利用ICRO算法来解决任务卸载问题。该算法采用二进制编码，模拟分子进行化学反应的过程改变分子编码，得出全局近似最优策略。仿真实验表明基于CRO算法的服务缓存策略与应用程序的总服务数无关，服务缓存比例在缓存容量相同时两者趋于一致；ICRO算法制定卸载策略时同时考虑个性化因子与任务特征，有效降低系统总开销，任务卸载率会受个性化因子与任务特征双因素影响；在算法性能方面，相比于CRO算法，ICRO算法在目标函数、设备能耗、系统时延等评价指标上的优化效果更佳。本文也有不足之处，如只考虑将同一个应用程序的任务卸载到一个服务器上的情况，服务器资源可能长时间闲置，并且终端设备只有一个，没有考虑多用户的情况下对资源的争夺。