1.   引言

雾计算技术的基本思想是将由云服务器提供的网络功能下沉到网络边缘，由于雾服务器的位置部署更加靠近网络用户，因此与云计算相比，雾计算可以有效降低数据传输时延。此外，雾计算采用的分布式处理方式还能有效缓解大量数据涌入云端造成的网络拥塞问题。雾计算所具备的优势能够满足未来的网络应用需求，文献[1-4]对其进行了深入的研究。此外，区块链是基于互联网的分布式记账技术，其特点是分散和透明。分布式账本的出现可以有效地解决集中认证方式中交易成本昂贵，数据容易丢失等问题，并且还可以有效提升虚拟货币体系中节点间的信任度^[5,6]。这些优点使得每个安装了区块链应用程序的设备都能参与到数据的记录和存储中，极大提升了电子交易中记账方式的灵活性和安全性。文献[7-10]对区块链技术进行了研究。

在区块链技术中，通过求解计算密集型的工作量证明(Proof of Work, PoW)难题，矿工将获得可观的数字货币收入。求解PoW难题需要消耗大量计算资源，因此在现实应用中通常需要部署大规模的硬件设施。然而，在尺寸有限的移动终端设备上部署大规模计算单元是不切实际的，所以区块链技术在移动终端上的广泛应用受到了很大限制。

为了解决上述问题，可以考虑将雾计算技术引入到区块链系统中，借助雾计算提供的强大算力进行PoW难题的求解，并向安装了区块链应用程序的移动用户(Mobile User with Blockchain, MUB)提供低时延的网络性能保证。文献[11]从安全性、通用性的角度分析了融合区块链和雾计算系统的可行性。通过将区块链结合到雾计算网络中，系统可以在大量分布式边缘节点上提供对网络的可靠访问和控制，存储和计算。此外，还有少数学者在融合区块链和雾计算网络环境中基于资源管理进行了系统收益的研究。文献[12]提出了一种Stackelberg博弈模型，为雾计算中的资源分配提供有效的管理方法。此后引入支持雾计算的区块链系统模型，以帮助雾服务提供商获取更多利润。

这些研究成果致力于研究雾计算和区块链技术的融合，并有少数文献分析了系统的资源管理和效益问题。然而，却没有对MUB的收入问题进行研究。如文献[12]中的作者只分析了网络运营商的利润。本文结合网络资源管理，重点研究了融合区块链和雾计算系统中的优化任务卸载策略。总体而言，本文的主要贡献有以下几个方面：(1)基于节点剩余的计算资源、存储资源和功率资源对MUB虚拟货币收益的影响进行了分析，具有充足资源的雾节点提供较低的服务报价吸引MUB的任务，从而提升网络的闲置资源利用率。(2)分析了将PoW难题迁移至各种类型雾节点时的传输时延和计算时延对MUB收益的影响，并获得了雾节点计算PoW难题的总时延的闭合表达式。(3)基于节点剩余资源和网络时延的分析，以最大化MUB的虚拟货币收入为目的，建立了一种优化任务卸载模型。

2.   系统模型

融合区块链及雾计算系统的分布式雾服务结构如图1所示，根据雾服务器提供的服务能力和雾服务器的移动性，将雾节点分为3类：基站雾服务器 (Base station-based fog Node, BN)，固定位置雾服务器 (Fixed-location fog Node, FN)和移动雾服务器 (Moving fog Node, MN)。基站雾服务器指在基站中部署多个具有雾计算能力的雾服务器，面向网络接入用户提供计算、存储等服务。同时，雾服务器还可以部署在一些地理位置固定的设备，形成固定位置雾节点。此外，雾服务器同样可以部署在智能车辆等移动设备上，本文中把能够提供雾服务的移动设备称为移动雾节点。

图 1  系统模型

下载: 全尺寸图片 幻灯片

在上述泛在雾结构中，MUB可以将PoW 难题迁移至3种类型的雾节点，借助雾服务器强大的计算能力进行PoW 难题的求解进而节约数据处理的时间，确保MUB以最快的速度获得收益。本文考虑的任务卸载方式为MUB按照一定的比例将原始任务划分为多个子任务，并分别卸载至不同类型的雾节点进行处理。设MUB将任务划分为3部分，分别卸载到BN, FN和MN。设任务的总任务量为${Q_{\rm{n}}}$，卸载到BN, FN和MN的任务量占总任务量的比例分别为$\alpha$, $\beta$, $\gamma$，满足$0 \le \alpha \le 1$, $0 \le \beta \le 1$, $0 \le \gamma \le 1$及$\alpha + \beta + \gamma = 1$。

3.   基于网络时延和资源管理的优化任务卸载方案

3.1   收益分析

MUB求解PoW难题的目的是获得交易信息的记录权，而最终的目的则是获得虚拟货币奖励，如比特币等。MUB能够获取虚拟货币的概率与PoW难题的数据量之间存在一定关系。MUB计算的任务数量越多，其获得奖励的概率就越大，预期收益就越高。设任务的任务量为${Q_{\rm{n}}}$，执行完此任务MUB能够获得数字货币奖励的概率为${p_{{\rm{income}}}}$，则MUB获取的收益可表达为

3.2   时延分析

设基站处部署了a个雾服务器，其计算能力均为${f_{{\rm{bn}}}}$。将任务量为$\alpha {Q_{\rm{n}}}$的PoW难题迁移至基站雾节点，需要的传输时间可表述为

$r_{\rm{n}}^i = {W_i}{\log _2}{(1 \!+\! ({P_{\rm{m}}}h_{\rm{n}}^i)/({\omega _i}\! +\! {I_i}))_{}}_{},i = 1,2, ···, a$为MUB到基站之间的信道速率。${W_i}$代表信道i的带宽，${P_{\rm{m}}}$为MUB的发射功率，$h_{\rm{n}}^i$为信道增益，${\omega _i}$和${I_i}$分别代表信道i的噪声和干扰。

将任务迁移至BN进行求解需要的计算时间为

进一步可得到将任务卸载至BN所花费的总时间为

此外，设在MUB的通信范围内有b个计算能力均为${f_{{\rm{fn}}}}$的固定位置雾服务器，则将任务量为$\beta {Q_{\rm{n}}}$的PoW难题迁移至FN需要的传输时间可表述为

$r_{\rm{n}}^j = {W_j}{\log _2}{(1 + ({P_{\rm{m}}}h_{\rm{n}}^j)/({\omega _j}+ {I_j}))},j = 1,2,···, b$代表MUB到第j个FN间的信道速率。${W_j}$为信道j的带宽，${P_{\rm{m}}}$为MUB的发射功率，$h_{\rm{n}}^j$为信道增益，${\omega _j}$和${I_j}$分别代表信道j的噪声和干扰。

任务在FN处进行计算所需要的计算由式(6)给出

则将任务卸载到FN需要执行的总时间为

再设在MUB的通信范围内有c个具有相同计算能力${f_{{\rm{mn}}}}$的固定位置雾服务器，则将任务量为$\gamma {Q_{\rm{n}}}$的PoW难题迁移至MN花费的传输时间可表述为

$r_{\rm{n}}^k = {W_k}{\log _2}{(1 \!+\! ({P_{\rm{m}}}h_{\rm{n}}^k)/({\omega _k} \!+\! {I_k}))_{}}_{},k \!=\! 1,2, ···, c$代表MUB到第k个MN间的信道速率。${W_k}$为信道带宽，${P_{\rm{m}}}$为MUB的发射功率，$h_{\rm{n}}^k$为信道增益，${\omega _k}$和${I_k}$分别代表信道k的噪声和干扰。

MN处理数据所需要的时间为

则将任务卸载至MN需要的总时间可表述为

根据上述分析，成功求解PoW难题的总时延可以表述为

其中，$T_{{\rm{back}}}^{}$代表某个网络节点成功解决PoW难题后，将交易记录信息传回MUB所消耗的时间。由于成功求解PoW难题后的回传信息是区块链系统中的交易记录，与PoW难题的任务量相比而言，此交易记录的数据量极小，在许多研究^[13,14]中均将其设置为0，本文采用同样的分析方法，最终得到任务执行时延的表达式为

3.3   支出分析

当剩余资源较为充分时，雾节点可以设置较低的报价以吸引MUB将更多的任务迁移至本地服务器，从而提升本地闲置资源的利用率。此外，如果雾节点当前剩余资源较为匮乏，雾节点可以将报价设置得较高从而引导MUB将任务卸载至其它雾节点。即雾节点的剩余资源与报价间呈反比关系。另一方面，BN服务器由运营商提供，一般而言，这种雾服务器的功能远强于FN和MN，若仅使用剩余资源作为雾服务器的定价标准显然会导致不公平的定价。

基于上述考虑，本文将节点的剩余资源和总资源均视为影响雾节点报价的因素，3种类型的雾节点的单位报价表述为

式中，$\displaystyle\sum\nolimits_{i = 1}^a {S_i^{{\rm{bn}}}}$, $\displaystyle\sum\nolimits_{i = 1}^a {C_i^{{\rm{bn}}}}$和$\displaystyle\sum\nolimits_{i = 1}^a {E_i^{{\rm{bn}}}}$分别代表基站雾节点的总存储资源、总计算资源和总功率资源。${s^{{\rm{bn}}}}(t)$, ${c^{{\rm{bn}}}}(t)$和${e^{{\rm{bn}}}}(t)$则分别代表t时刻剩余的存储资源、计算资源和功率资源。$\theta _{\rm{1}}^{{\rm{bn}}}$, $\theta _{\rm{2}}^{{\rm{bn}}}$和$\theta _{\rm{3}}^{{\rm{bn}}}$为权重值，分别代表3种不同类型的资源对价格的影响。不同类型的雾节点对每种资源的侧重不同，如MN对功率资源较为重视，故$\theta _{\rm{3}}^{{\rm{mn}}}$的取值会高于$\theta _{\rm{3}}^{{\rm{bn}}}$和$\theta _{\rm{3}}^{{\rm{fn}}}$，同时也高于$\theta _{\rm{1}}^{{\rm{mn}}}$和$\theta _{\rm{2}}^{{\rm{mn}}}$。式(14)和式(15)中的符号定义和上述分析一致，不再赘述。

综上所述，MUB的支出函数可表述为

4.   数学建模

MUB的最终收益等于其预期收益减去花销，所以，MUB的最终收益可表述为

由于本文研究的主要目的是最大化MUB的收益，在MUB求解PoW难题过程中，其收益受到网络时延、卸载比例的影响。基于以上分析，将最大化MUB收益的数学优化模型建模为

由于MUB的收益与任务的执行时间紧密相关，所以限制条件C1将总时延限制在${T_{\rm{\tau }}}$范围内以保证MUB解决PoW的速度。C2和C3则是将总任务划分为子任务分别卸载到BN, FN和MN以达到降低总时长的目的。C4～C6则保证BN, FN和MN具有充足的剩余资源处理矿工卸载的任务。上述优化模型的优化目标与约束条件之间存在非线性关系，所以利用适合解决此类问题的模拟退火算法对其进行求解。

5.   模拟退火算法求解

对于上述优化模型，在满足$0 \le \alpha \le 1$, $0 \le \beta \le 1$, $0 \le \gamma \le 1$及$\alpha + \beta + \gamma = 1$的前提条件下，$\alpha$, $\beta$和$\gamma$的不同取值构成解空间。在使用模拟退火算法寻求最优解时，首先设置最高温度${T_{\max }}$，以及降温速度$\nu$，满足$T(k + 1) = \nu T(k)$, $T(k)$代表$k$时刻的温度，当温度降至最低温度${T_{\min }}$时，算法结束。每一次降温过程中，都会出现L个解，为了求出最优解，假设在当前状态i下系统的解为$E_{ni}^T$，下一状态j下的解为$E_{nj}^T$。根据metropolis准则，有式(19)成立

其中，${p_{{\rm{sol}}}}$为接受当前解为最优解的概率，表达为

式中$\varphi$为玻尔特兹曼常数，满足$\varphi \! =\! {\rm{1}}{\rm{.3806505}} \!\times\! {\rm{1}}{{\rm{0}}^{{\rm{ - 23}}}}$。

求解优化模型的模拟退火算法流程描述表1。

表 1  求解优化模型的模拟退火算法流程

输入：${Q_{\rm{n}}}$, $\varphi$, ${T_{\max }}$, ${T_{\min }}$, $L$, $\nu$；

输出：优化解$\pi^* = \{ \alpha^*,\beta^*\}$；

(1) 初始化${Q_{\rm{n}}}$, 最高温度${T_{\max }}$和最低温度${T_{\min }}$，降温速度$\nu$，迭代 　　 次数$L$；

(2) for m=1:L do；

(3) 求解状态${\pi _m} = \{ {\alpha _m},{\beta _m}\}$, 并计算当前$E_{{\rm{n}}m}^{\rm{T}}$，将 　　 ${\pi _m} = \{ {\alpha _m},{\beta _m}\}$赋值给最佳解$\pi^* = \{ \alpha^*,\beta^*\}$；

(4) 计算下一状态解${\pi '} = \{ {\alpha '},{\beta '}\}$，并计算对应的$E_{{\rm{n}}(m + 1)}^{\rm{T}}$；

(5) 计算增量$\Delta E_{{\rm{n}}m}^{\rm{T}} = E_{{\rm{n}}(m + 1)}^{\rm{T}} - E_{{\rm{n}}m}^{\rm{T}}$；

(6)　　if $\Delta E_{{\rm{n}}m}^{\rm{T}} < 0$ then；

(7) 接受当前解为最佳解，并将${\pi _m} = \{ {\alpha _m},{\beta _m}\}$赋值给最佳解 　　 $\pi^* = \{ \alpha^*,\beta^*\}$；

(8)　　else；

(9) 以metropolis准则中的概率${p_{{\rm{sol}}}}$接受${\pi _m} = \{ {\alpha _m},{\beta _m}\}$作为当 　　 前最佳解；

(10)　　End if；

(11)　　if m≠L；

(12)　　　返回(2)；

(13)　　else；

(14)　　　　end for；

(15) $T(k + 1) = \nu T(k)$；

(16)　if $T(k + 1) > {T_{\min }}$；

(17)　　　返回(2)；

(18)　else；

(19) end for

下载: 导出CSV 

| 显示表格

6.   仿真结果

仿真中的参数设置如下。基站中部署的雾服务器数量a为10。在MUB通信的范围内的FN和MN的个数也设置为10。为了方便分析，所有的带宽均设置为10 MHz，所有的噪声和干扰均设置为1。基站的覆盖半径为300 m，MUB的通信范围同样为300 m。BN, FN和MN的总存储资源，总计算资源和总功率资源的数值见表2。为体现各种资源间的公平性，将权重值设为近似相等。

表 2  各种节点的总资源和剩余资源量及其权重的设置

节点类型	资源类型	总资源	剩余资源	权重
BN	存储资源(GB)	1024	[600, 800]	0.33
	计算资源(MCPS)	1000	[600, 800]	0.33
	功率资源(W)	400	[280, 350]	0.34
FN	存储资源(GB)	512	[256, 300]	0.33
	计算资源(MCPS)	400	[280, 350]	0.33
	功率资源(W)	40	[28, 30]	0.34
MN	存储资源(GB)	128	[16, 32]	0.33
	计算资源(MCPS)	200	[100, 160]	0.33
	功率资源(W)	2	[1.2, 1.6]	0.34

下载: 导出CSV 

| 显示表格

表2中的[x, y]代表服从x到y的均匀分布。此外，我们将模拟退火算法中的最高温度和最低温度分别设置为200°和1°，降火速率为0.99，循环次数L=10000。

图2分析了雾节点数量与网络时延之间的关系。从图中可以明显看出，随着网络节点(包含BN, FN和MN)的增加，网络时延逐渐减少。图2说明了MUB将PoW卸载到多个雾节点上计算可以节省任务执行时间。如在网络中部署了10个雾服务器时，网络总时延达到17 ms，而如果网络中的雾服务器数量增加到30个时，网络时延可以降至10 ms。

图 2  节点数量与时延的关系

下载: 全尺寸图片 幻灯片

在接下来的仿真中以MN为例，设任务的大小为2 GB，对不同类型的资源对报价的影响进行了分析。从图3中首先可以看出，剩余资源量的增加会导致节点的报价越来越低。这主要是因为当剩余资源较多时，MN为了充分利用闲置资源，将报价设置得较低可以引导MUB将更多的任务迁移至MN。从图3中还可观察到，功率资源对MN的报价影响最大，这主要是由于MN往往都是功率受限的设备。如在剩余的功率资源仅有10%时，MN关于功率资源的报价为9.3，而同样条件下，MN关于存储资源和计算资源的报价仅有2.4。

图 3  不同资源类型与定价的关系

下载: 全尺寸图片 幻灯片

从图4中可以明显看到，根据SA算法将任务按照比例进行卸载的开销是最小的。如在任务量为5 GB时，将任务全部卸载到MN, FN, BN和使用SA算法的总开销分别为107, 80, 68, 48。

图 4  将任务迁移至不同执行主体的开销对比

下载: 全尺寸图片 幻灯片

在图5中将不同的迁移模式所对应的收益进行了比较。使用本文所提的方案能够有效提升MUB的收益。如任务量为5 GB时，将任务全部卸载到MN, FN, BN和使用SA算法的总收益分别为105, 127, 140, 161。

图 5  将任务迁移至不同执行主体的收益对比

下载: 全尺寸图片 幻灯片

图6比较了任务的数量与MUB开销在分别使用模拟退火算法，贪婪算法和随机卸载算法时的收益。从图6中可以看出，MUB的花销随着任务量的增加而增加，其主要原因是任务量的增加会占用雾节点更多的资源，雾节点会收取更多的费用，MUB的花销自然随之上涨。同时，由于任务量的增加，传输时延和处理时延也会一起增长，所以MUB的花销也会随之增加。如当任务量为4 GB时，使用SA算法时MUB的开销为36，当任务量增长到7 GB时，开销增长到了73。同时，从图6中还可以看到，当任务量为5 GB时，使用SA的开销为50，这个值要低于使用GA时的62，而GA的开销又远低于RA的104。上述数据说明，SA算法的性能要优于GA，而GA的性能又要优于RA。同样的结论在图7中也可以得出，这主要是因为使用GA算法求解出的只是局部最优解，同时RA算法的解是随机生成的，其性能均不及SA算法。

图 6  使用不同算法时的MUB收益对比

下载: 全尺寸图片 幻灯片

图 7  数据量大小与收益的关系

下载: 全尺寸图片 幻灯片

7.   结束语

本文在融合区块链和雾计算系统中基于节点剩余资源和网络时延对优化卸载PoW难题进行了研究。在由基站雾节点、固定位置雾节点及移动雾节点共同构成的网络场景中分析了将PoW难题卸载至各种类型的雾节点所需要的总时长。此后基于网络节点剩余的计算资源、存储资源、功率资源对MUB的支出进行了分析。并基于节点剩余资源和网络时延提出了优化任务卸载方案，并以最大化MUB收益为目标构建了数学优化模型，使用SA算法对优化模型进行了求解。最后，通过模拟仿真分析证明上述方案的优越性。未来的工作中将考虑在系统内引入人工智能的智能任务卸载方式。