★中国地质大学（武汉）计算机学院杨在航，李跃鹏，曾德泽

摘要：边端融合计算架构由于其算力节点分布广、实时处理能力强的特点，近年来在各种领域被广泛使用，但是它在计算、通信与数据安全方面仍然面临诸多挑战。编码计算因其通信负载低、计算开销小、隐私保障高的特性恰好契合边端融合场景的需求而得到了学术界的广泛关注。因此，本文探索了将编码计算应用于边端融合计算架构中的发展趋势与关键技术，并在此基础上，提出了一种基于编码计算的边端融合任务卸载策略。

1简介

随着万物互联时代的到来，大量智能设备以及诸多新型应用得到了大规模普及，例如智慧城市、虚拟现实、智能交通等应用如雨后春笋般涌现，为智能社会的发展注入了新的活力。智能应用高速发展的背后实际上离不开边缘计算作为支撑和基础。边缘计算将计算与存储资源下沉到网络边缘处，由于更靠近终端设备，用户请求不再需要经过长时间传输到核心网进行处理，而是直接在数据产生处进行计算，从而大幅度降低了传输时延与能量消耗。边缘侧设备与端侧设备均可共同参与计算，协同构成边端融合计算环境。然而边端融合环境中的设备大多是由低算力硬件组成，这使得单个设备无法独自完成这个任务。而且，终端设备大多具有较强的移动性，当大量终端设备频繁地从一个边缘服务器的覆盖范围移动到另一个边缘服务器的覆盖范围内时，整个环境呈现出高度动态性。此外，相比于云数据中心，边缘侧和端侧设备因成本较低无法配备高强度安全保护策略导致其更容易受到恶意节点的攻击。

与此同时，近年来研究人员将编码理论应用到分布式计算领域，并提出了一种新的计算框架，即编码计算。编码计算旨在借助灵活多样的编码方式来降低通信负载、缓解计算延迟并保护数据隐私[1]。编码计算的出现引起了学术界的广泛讨论，被认为是解决上述边端融合计算所面临挑战的一个有潜力的途径。例如，Guo[2]等提出了一种面向无人机群的分布式编码计算框架，通过将无人机群的编码任务卸载到边缘服务器上，不仅节省了无人机群的飞行能耗，而且降低了掉队无人机节点所引发的计算延迟；Parkash[3]等提出了编码计算框架CodedFedL，将结构化编码冗余注入无线边缘网络下的联邦学习中，以减少离散并加快训练过程；Zhao[4]等提出了一种基于边缘节点选择的子任务分配方法，以减少编码边缘计算系统的总计算时间。

然而应用编码计算到边端融合环境中仍然面临着不小的阻力。首先，编码计算目前主要应用于分布式云环境中，边端融合环境所呈现的弱算力、高异构、弱连接、广分布、高动态等特性加大了编码任务传输和计算的难度。其次，传输并处理编码所产生的大量冗余数据会给整个系统带来极高的能量开销，边缘侧和端侧设备将难以承受这些额外能量开销所带来的成本问题。

因此，本文介绍了编码计算和将其融入边端融合计算的发展趋势以及面临的挑战，并探讨了一种基于编码计算的边端融合任务卸载策略。

2边端融合计算面临的挑战

近年来，边缘计算所蕴含的巨大潜力，使其已经成为学术界和工业界共同关注的热点话题。然而边缘计算仍处于发展早期，与相对成熟的云计算相比，将其与端侧设备融合构成边端融合计算，不论是其自身体系结构局限还是技术积累，都还存在诸多问题亟需解决。

（1）计算延迟

边端融合环境下的设备大多是由不可靠的低端硬件构成，单个设备的性能较差使得任务逐渐采取分布式计算完成。但相关研究[10]发现即使使用同构机器运算相同任务时，由于网络条件变化、资源竞争等因素，每个机器所需的计算时间也不尽相同，其中部分工作节点的任务完成速度非常慢，达到平均值的5到8倍。因此，一旦边端融合环境中存在因工作能力低下导致任务完成速度较慢的工作节点时，等待这些工作节点的反馈会给整个计算任务造成不可预测的延迟。

（2）通信瓶颈

数据洗牌是分布式计算系统（包括边端融合环境）的核心步骤，其目的是在分布式计算节点之间交换中间值或原始数据[5]。例如，在MapReduce架构中，数据从Mapper被传输到Reducer。通过对Facebook的Hadoop架构进行追踪分析，研究人员发现平均有33％的作业执行时间都花费在数据洗牌上。在TeraSort、WordCount、RankedInvertedIndex和SelfJoin等应用程序中，50％～70％的执行时间用于数据洗牌。然而，在每一次数据洗牌过程中，整个数据集都通过网络进行通信，频繁数据交互带来的通信开销造成了分布式计算系统的性能瓶颈。

（3）安全与隐私

缺乏对边端融合环境中的数据安全与隐私保护的举措将会增加人们的日常风险。假设一个家庭在周围部署了物联网，那么人们就可以从感知到的数据中了解到这个家庭的很多隐私信息，例如，通过读取电力或水的使用情况，人们可以很容易地推测房子是否空置[6]。造成这种现象的原因一方面是社会缺乏对隐私和数据的保护意识。我们以Wi-Fi网络安全为例，在4.39亿使用无线连接的家庭中，49%的Wi-Fi网络是不安全的，80%的家庭仍然将路由器设置为默认密码。另一方面是缺乏有效的工具来保护网络边缘处的数据隐私和安全。相比于云环境，边端融合环境中的资源高度受限，这使得传统的安全保护方法可能无法被部署，或者被有效应用。

（4）移动性问题

随着终端算力的增加，智能手机、平板、智能汽车等硬件逐渐成为了构成边端融合的算力主力军。这类设备最大的特性就是具有极强的移动性，当终端设备的移动范围跨越多个边缘服务器的覆盖范围时，终端设备状态的更新以及设备与应用之间的重新连接将是一大难点[7]。

3编码计算的出现

目前边端融合计算面临着多个方面的挑战，这严重制约了边端融合计算的进一步发展与应用。幸运的是，编码计算通过借助灵活多样的编码方式有望解决边端融合计算中存在的问题。为了方便读者理解编码计算的基本思想，我们将从计算延迟、通信负载和安全隐私三个方面来具体阐述并给出相关示例。

（1）降低通信负载编码。图1展示了一个由1个主节点和2个工作节点组成的分布式计算系统，其中A1、A2存储在工作节点W1中，A3、A3存储在工作节点W2中。我们的目标是将任务A3发送到工作节点W1，并将任务A2发送到工作节点W2。因此，我们可以设计这样一种编码，使主节点将编码信息A2+A3广播到2个工作节点，一旦工作节点接收到广播信息之后就能够利用本地已存储的数据进行解码。显然，与未编码方案相比，编码方案可以降低50％的通信负载。

图1降低通信负载编码示例

（2）减少计算延迟编码。图2展示了一个由1个主节点和3个工作节点组成的分布式计算系统，整个系统的目标是计算矩阵乘法AX。在进行数据传输之前，原始任务矩阵A被平均划分为两个子矩阵A1和A2，然后将两个子矩阵进行线性编码生成新的子矩阵（A1+A2），接着主节点M将A1、A2和（A1+A2）分别发送给工作节点W1、W2和W3。每个工作节点接收到子矩阵任务之后，将子矩阵与X相乘并将计算结果返回给主节点M。通过观察可知，主节点只需要接收到任意两个计算结果就能恢复出最终结果，而无需等待掉队节点的反馈。

图2减少计算延迟编码示例

（3）面向安全隐私编码。图3展示了一种用于保护双边隐私的编码计算示例。具体来说，输入矩阵被分割成子矩阵并用随机矩阵编码[8]。下面以工作节点为8、共谋节点为1来说明编码过程。

主节点首先将输入矩阵A，B进行划分，如式（1）所示：

                                                  （1）

然后分别为A、B各生成一个随机矩阵KA、KB。主节点为每个工作节点i选择不同的参数xi，生成的编码数据如式（2）和式（3）：

                                     （2）

                                                                   （3）

工作节点在接收到编码数据后，每个工作节点i计算，并将计算结果返回给主节点，则每个工作节点的计算任务相当于多项式h（x）在点x=xi的值如式（4）：

                       （4）

由上式可知，多项式h（x）中4项A1B1、A2B1x、A1B2x、A2B2x的系数可组成最终结果，而在整个过程中，任一计算节点均未收到原始数据，一定程度上保障了数据的安全与隐私。因此，主节点可以采取多项式插值法确定该多项式，从而获得所需的系数。

图3面向安全隐私编码示例

4基于编码计算的边端融合计算架构

传统的边端融合计算架构如图4（a）所示，边端融合环境下无论是边缘设备还是终端设备都可以被抽象为计算节点，它们既可以向其余节点发送任务，也可以参与到任务的计算中来。例如任务A可以在主节点处进行划分并分别卸载到三个不同的节点，只有所有计算结果成功返回主节点才能恢复出最终结果。但是边端融合环境中的节点大多是由不可靠的低端硬件构成，这些节点极易出现失效或掉队现象，这会给计算任务造成不可预测的延迟。此外，边端融合环境中节点资源受限并且网络条件处于高度动态变化中，这使得原有的数据保护方案难以应用到边端融合环境中，从而导致了数据泄露问题。

将编码计算融入至边端融合计算是解决上述问题的潜力途径，其架构如图4（b）所示。该架构中主节点在任务分发之前会对原始任务矩阵进行编码，即便在任务传输时数据遭到泄露，攻击者也只能获取到编码之后的数据而无法恢复出原始数据。同时，通过观察可知，主节点只需要接收到任意3个计算结果就能恢复出最终结果，即便某个节点出现掉队或者失效现象也不会对整个任务造成高延迟现象。

图4边端融合计算架构演变图

5案例：基于编码技术的边端融合任务卸载策略

即便基于编码计算的边端融合计算架构解决了由掉队现象带来的计算延迟并避免了数据泄露问题，但是主节点在任务分发阶段仍然延续了编码计算在分布式云环境中的平均分配原则。需要注意的是，边端融合环境中的节点在计算性能、地理位置、网络条件等方面存在极大的异构性，简单地将编码任务进行平均分配无疑会降低整个分布式系统的任务执行效率。此外，编码计算容易产生大量冗余数据，引发高能耗问题。为此，接下来我们探讨一个基于编码技术的边端融合任务卸载问题。

如图5所示，该系统由一个主节点和多个工作节点构成的集合I组成。这些节点大多是由不可靠的低端硬件组成，并且节点之间在计算性能、地理位置和通信能力等方面存在较大的异构性。在任务分发之前，位于主节点上的原始任务矩阵将按行平均划分为K个子任务，在使用MDS码编码之后整个任务矩阵变为了N行，即N个子任务。编码后的子任务既可以选择直接在本地执行，也可以卸载到工作节点上执行。当选择卸载到工作节点上执行时，工作节点会有一定几率出现掉队现象从而导致任务完成时间增加。一旦主节点接收到任意K个返回结果时就能恢复出最终结果。

图5编码任务部分卸载架构图

（1）系统算法设计：针对边端融合环境下的编码任务部分卸载问题，我们提出了一种基于迭代贪心的节点选择算法。该算法通过对工作节点进行迭代交换的方式不断降低整个系统的能量开销，算法的具体步骤如表1所示。

表1基于迭代贪心的节点选择算法

（2）实验结果：为了评估该系统所使用算法的性能，我们将所提出的算法（IterationGreedyPolicy，IGP）与随机卸载算法（RandomOffloadingPolicy，ROP）、全卸载算法（AllOffloadingPolicy，AOP）和本地优先算法（LocalComputingPolicy，LCP）进行对比并分别探究了主节点发送功率和工作节点CPU频率等因素对于不同方案能量开销的影响，实验结果如图6、7所示。

图6不同方案的能量开销与主节点发送功率关系图

图7不同方案的能量开销与工作节点CPU频率关系图

调节主节点发送功率，四种方案能量开销的变化情况如图6所示，增大主节点的发送功率会提高传输任务的能量开销但本地执行的能量开销保持不变。由于AOP方案将所有任务卸载到工作节点执行，故该方案的能量开销增幅最大。尽管LCP方案将大部分任务交由主节点执行，但受制于任务时延约束的影响，仍有少部分任务被卸载到工作节点执行，所以LCP方案的能耗曲线虽保持不断上涨但增幅较低。我们所提出的IGP方案产生的能量开销相比于其他方案保持最低，一方面是随着任务传输能量的提高，会有越来越多的任务转移到主节点上执行，另一方面IGP方案存在着工作节点的迭代交换过程，该过程会不断地对能耗进行优化调整。

调节工作节点CPU频率，四种方案能量开销的变化情况如图7所示，提高工作节点的CPU频率会缩短任务执行时间但主节点执行和发送任务的能量开销保持不变。同时工作节点性能的增强不会改变AOP方案和LCP方案的卸载决策，因此AOP方案与LCP方案的能量开销自动化博览·边缘计算专辑/2023.02/49保持不变，ROP方案的能量开销仍然呈现一定的波动性。我们所提出的IGP方案产生的能量开销保持最低，并且在1.5GHz至2.7GHz区间能量开销不断降低，随后保持不变，这是由于部分工作节点计算性能较差无法满足任务的时延约束，但这类节点在地理位置和网络条件方面存在优势，从而导致传输任务产生的能量开销较低。随着工作节点的性能增强，这类节点也会逐渐满足任务的时延约束，从而在IGP方案的迭代交换部分能够实现对于这类节点的选择。

6结语

随着智能设备算力的不断加强，边端融合计算架构正发挥着举足轻重的作用，但应用边端融合计算到实际生活中还面临着诸多挑战，编码计算的出现有望打破僵局。因此，本文介绍了边端融合计算架构所面临的挑战与编码计算的基本思想，提出了基于编码计算的边端融合计算架构，并设计了一种基于编码计算的边端融合任务卸载策略作为案例，以此验证编码计算与边端融合计算架构相结合技术的可行性。

作者简介：

杨在航（1997-），男，湖北人，硕士，现就读于中国地质大学（武汉）计算机学院，研究方向为编码计算、边端融合计算等。

李跃鹏（1994-），男，河南人，博士，现就读于中国地质大学（武汉）计算机学院，主要研究方向为可信边缘计算等。

曾德泽（1984-），男，四川人，中国地质大学（武汉）计算机学院教授、博士生导师，主要研究方向为边缘计算、未来网络等。

参考文献：

[1]郑腾飞,周桐庆,蔡志平,吴虹佳.编码计算研究综述[J].计算机研究与发展,2021,58(10):2187-2212.

[2]GuoY,GuS,ZhangQ,etal.Acodeddistributedcomputingframeworkfortaskoffloadingfrommulti-UAVtoedgeservers[C].2021IEEEWirelessCommunicationsandNetworkingConference(WCNC).IEEE,2021:1-6.

[3]PrakashS,DhakalS,AkdenizMR,etal.Codedcomputingforlow-latencyfederatedlearningoverwirelessedgenetworks[J].IEEEJournalonSelectedAreasinCommunications,2020,39(1):233-250.

[4]ZhaoS.Anode-selection-basedsub-taskassignmentmethodforcodededgecomputing[J].IEEECommunicationsLetters,2019,23(5):797-801.

[5]VargheseB,WangN,BarbhuiyaS,etal.Challengesandopportunitiesinedgecomputing[C].2016IEEEInternationalConferenceonSmartCloud(SmartCloud).IEEE,2016:20-26.

[6]ShiW,CaoJ,ZhangQ,etal.Edgecomputing:Visionandchallenges[J].IEEEInternetofThingsJournal,2016,3(5):637-646.

[7]LiH,ShouG,HuY,etal.Mobileedgecomputing:Progressandchallenges[C].20164thIEEEInternationalConferenceonMobileCloudComputing,Services,andEngineering(MobileCloud).IEEE,2016:83-84.

[8]ChangWT,TandonR.Onthecapacityofsecuredistributedmatrixmultiplication[C].2018IEEEGlobalCommunicationsConference(GLOBECOM).IEEE,2018:1-6.

[9]CaoC,WangJ,WangJ,etal.Optimaltaskallocationandcodingdesignforsecurecodededgecomputing[C].2019IEEE39thInternationalConferenceonDistributedComputingSystems(ICDCS).IEEE,2019:1083-1093.

[10]YadwadkarNJ,HariharanB,GonzalezJE,etal.Multi-tasklearningforstraggleravoidingpredictivejobscheduling[J].TheJournalofMachineLearningResearch,2016,17(1):3692-3728.

摘自《自动化博览》2023年第2期暨《边缘计算2023专辑》