工业物联网中大规模受损边缘计算网络修复机制

田辉，伍浩，田洋，任建阳，崔亚娟，艾文宝，袁健华

（1.北京邮电大学网络与交换技术国家重点实验室，北京 100876；2.北京邮电大学理学院，北京 100876）

1 引言

工业物联网（IIoT,industrial Internet of things）被视为全球工业体系智能化变革的重要推手。依靠数以亿计无缝部署的感知器、采集器与控制器，工业物联网可以实现对生产制造过程全周期的模拟、预测与控制[1]。作为工业物联网的“大脑”，边缘计算网络为无线采集设备提供了更充足的计算处理能力，有效降低了处理、传输时延，为数字孪生（DT,digital twin）[2]、虚拟现实（VR,virtual reality）等企业高层应用打下了坚实的基础[3]。同时，边缘计算节点间有线的链路连接方式，也使节点间的计算任务迁移更加顺畅，有效缓解了工业物联网计算需求空时波动所造成的计算资源空时分配不均衡问题。

边缘计算网络的正常、稳定运行是工业物联网高效运转的关键，一旦“大脑”受损，工业物联网系统将失去对“四肢”（例如供应链监控、数据可视化分析）的有效控制，带来难以计数的经济损失，甚至威胁生命。然而，边缘计算网络的稳定性需求面临内外两方面的挑战。一方面，边缘计算网络与工业物联网中的电网、控制网等多种子网相互耦合，形成了极易受损的互依赖网络[4]。其他子网的任意微小波动，都有可能传导到边缘计算网络，造成大规模的系统级联故障。另一方面，自然灾害与人为攻击等不可预测事件也随时考验着边缘计算网络的稳健性[5]。为应对上述挑战，一方面可以加强边缘计算网络的可靠性，使其能够自适应地应对各种网络波动，防止网络出现故障；另一方面，也是更重要的，需要探究网络受损后的快速修复机制，使网络性能尽快恢复到接近受损前的水平。

尽管修复机制的设计对网络可持续稳定运行至关重要，当前尚无特定针对工业物联网中边缘计算网络场景的研究文献。鉴于网络拓扑、网络动态等特征的相似性，部分现存网络修复策略仍可以为工业物联网中边缘计算网络修复机制设计提供一定的借鉴。现存网络修复机制的研究主要着重于局部网络受损后的快速修复。文献[6]将网络单一节点或链路受损问题构建为一个整数线性规划问题，提出了一种数据迁移感知的修复模型，实现了服务中断率与修复成本的有效均衡。进一步地，文献[7-8]考虑到多节点失效场景网络连通性受损问题，提出可以通过设备到设备（D2D,device to device）方式利用用户作为失连边缘节点间的中转节点[7]或者利用可移动接入节点实现网络节点间数据的处处可达[8]，保障受损网络的连通性。与上述研究不同，文献[9]考虑到网络受攻击情况下的持续性受损状态，将网络动态修复问题转化为微分博弈论问题，并通过纳什均衡必要条件与竞争策略集增强了网络修复能力。然而，上述针对局部网络修复的研究，往往忽略了全局网络节点、链路间的动态特征（例如流迁移）和实际场景限制（例如链路空间布局无法改动），难以有效扩展至工业物联网中更可能发生的网络大规模受损场景。

网络大规模受损后，初期可利用的修复资源（例如修理人员数量、可替换设备数量）往往是有限的。如何有效平衡修复初期受限的系统修复资源与急迫的系统性能恢复需求是当前工业物联网中亟待解决的问题。当前研究主要集中于对网络拓扑结构的分析。文献[10]认为，大度节点，即节点度大的节点，在网络连通性方面有着更重要的作用，需要优先修复。类似地，文献[11]考虑链路受损情况下，应优先修复介数中心性（BC,betweenness centrality）大的链路。文献[12]通过实际网络数据分析发现，网络中的弱连接节点，即自身的度不高但连接着数个大度节点的节点，在网络连通性上发挥着最关键的作用，其修复优先级应比大度节点更高。然而，上述基于网络连通性不断壮大最大连通子图的方案均是静态网络架构分析，忽略了网络的动态性特征。真实环境下的网络大规模修复往往是先形成相互独立的子图，然后将多子图连接形成最大连通图[13]。因此，工程分析中，需要融入更多的网络设备细节与实际传输动态分析[14]。这类问题也被称为网络设计问题（NDP,network design problem）。由于网络动态性特征的加入，网络设计问题的复杂性极高（至少是NP 完全问题），传统动态规划算法将引发“维度灾难”[15]。为解决上述问题，文献[16]提出了一种更易求解的启发式算法，然而，其缺乏网络宏观分析，算法性能方差大，无法提供可靠的性能保障。类似地，模拟退火算法[17]与遗传算法[18]均面临一般启发式算法的相同困境，且极易陷入局部最优解。尽管通过爬山算法[19]或梯度下降算法[20]可以方便地跳出局部最优点并极大降低问题计算复杂度，但解的最优性仍无法得到保障。

针对当前研究所面临的现实困境，本文提出了一种针对工业物联网环境下受损边缘计算网络的修复机制。区别于现有文献，本文基于工业物联网子网间的互依赖特性所造成的网络脆弱性，深入挖掘了大规模受损边缘计算网络的结构特性（拓扑关系、链路容量）与动态特性（节点计算需求），联合考虑了链路优先修复集合决策与网络计算迁移问题，以期实现网络修复初期计算需求与修复开销的高效均衡。本文主要贡献总结如下。

1) 提出了一种边缘计算网络大规模受损情况下的网络修复机制。结合边缘计算网络结构与动态特征，提供了一种网络修复初期优先修复集合决策与资源调度分析框架。

2) 基于Benders 分解算法，将复杂的混合整数问题分解为更易求解的主问题与子问题两部分，通过各自解集的相互迭代，逐渐逼近系统最优解。针对多变量组的子问题，通过添加虚拟源节点与目的节点，将问题转化为网络最大流问题进行求解。

3) 设计了一种基于局部分支法的Benders 分解加速算法。采用基于汉明距离的信赖域，收缩可行域的搜索范围，加速算法的收敛速度。

仿真结果表明，本文所提算法具有较好的收敛性能与较低的系统总开销。相对现有随机修复、最大连通图修复和介数中心性排序修复算法等基于拓扑结构的修复算法，本文所提算法在多场景下均具有较优表现和具有很好的可扩展性与适应性。

2 系统模型

针对工业物联网中边缘计算网络，考虑一个含有N个节点的边缘计算网络，用集合∀i∈ N={1,2,…,N}表示。边缘节点之间均通过有线链路连接，链路集合用Ε表示，网络中总链路数量为。由于有线链路通常是可靠的，且相对边缘节点的计算任务只需要少量的信道编码复杂性，2 个边缘节点间的链路可以认为是无差错的[21]。系统参数如表1所示。值得注意的是，实际工业物联网中边缘计算网络往往是由有线链路与无线链路组成的混合链路传输网络。由于无线链路几乎不存在受损情况，且其修复成本相对于有线链路可以忽略不计，本文只考虑所有传输链路均为有线链路的情况。尽管如此，如果不考虑短期无线信道的深衰弱，静态场景下的无线链路（不考虑修复过程中的频谱重分配）可视为容量不变的不可受损链路，混合链路传输网络可以等效为纯有线链路网络进行考虑，本文所提算法仍将适用。

表1 系统参数

受损边缘计算网络拓扑关系如图1 所示。在实际网络中，由于边缘节点常拥有复杂的自我保护机制（例如过热保护），通常不易发生损坏，因此本文不考虑节点损坏的情况，重点关注链路受损问题。为模拟因自然灾害等因素而导致大面积网络故障的状态，假设初始时刻网络中有条有线链路遭到破坏，其中q表示受损链路占所有链路的百分比，集合Ε0表示受损链路集合，Ε1=ΕΕ0表示仍可以正常工作的链路集合。链路的受损将导致边缘节点间平衡的计算迁移流被打破，甚至形成计算孤岛（无法进行计算迁移，如图1 中节点1 所示），从而造成计算需求与计算能力不匹配，影响网络计算性能。受限于网络修复初期的有限修复资源（例如修理人员数量、可替换设备库存），同时修复所有的受损链路不切实际。为使网络状态尽快得到恢复，可以根据网络计算需求分布，优先修复部分受损链路，用集合Εr（Εr⊆Ε0）表示。对于任意链路ij∈Ε0，由于受损程度不同，对其进行维护、检修、替换的成本cij也各不相同。

图1 受损边缘计算网络拓扑关系

令节点i与节点之间的迁移计算量为fij。若fij>0，数据计算任务由节点i迁移至节点j；若fij<0，数据计算任务由节点j迁移至节点i。受有线链路容量限制，链路ij实际计算迁移量满足

进一步地，对于受损链路，其实际计算迁移量不仅取决于有线链路容量，也受到链路修复决策的影响，即

其中，有

其中，eij=1表示优先修复链路ij，即ij∈Εr；当eij=0表示链路ij未被修复，其实际计算迁移量fij=0。此外，对于单一链路ij，由迁移流对称性可知

当集合Εr中链路得到修复时，根据节点的计算量守恒定律可知

其中，ri表示节点i的本地数据计算量需求；di表示因计算能力有限导致数据积压，边缘节点i不得不舍弃的计算任务量，有

为了修复尽可能多的链路，可以减少数据的丢弃量，提升系统性能，但会造成较大的系统修复开销。修复链路过少，系统修复开销固然变小，但可能造成数据因堆积在本地无法处理而被丢弃，损害网络性能。为进行量化分析，本文中网络性能通过系统数据丢弃总代价来进行衡量，数据丢弃量越大，数据丢弃总代价越高，网络性能越差。因此，为均衡网络修复初期的修复开销与网络性能（数据丢弃总代价），可以构建如下的系统总开销最小化问题

其中，cij表示修复链路ij∈Ε0所需要的修复成本，ci表示节点丢弃每单位数据的代价，链路修复决策向量e=(eij,∀ij∈Ε0)，数据丢弃决策向量d=(di,∀i∈N)，流分配向量f=(fij,∀ij∈Ε)，本地实际计算量向量p=(pi,∀i∈N)。问题P 中，系统总开销包含两部分内容：系统修复开销与数据丢弃总代价。如前文所述，系统修复开销与数据丢弃总代价是一对相互矛盾的量，一个值的增加将导致另一个值的减少，最小化它们的和可以有效均衡两者影响。当链路修复成本cij较大时，表明计算数据重要性相对不高，系统倾向于暂时修复较少的受损链路，并丢弃无法处理的数据；而当每单位数据丢弃代价ci较大时，系统倾向于修复更多的受损链路以减少计算数据的丢弃。

问题P 是一个混合整数问题，是NP-hard 问题，且其数据规模较大，目前还没有已知的多项式时间算法能够解决上述问题。当前求解上述问题的方法可以分为三大类：启发式算法[22]、近似算法[23]与精确算法[24]。启发式算法速度快、应用简单，但缺乏严格的理论证明，结果常常严重偏离最优解。近似算法，例如松弛变量法，其求解规模有限，松弛问题的解也不能准确描述原问题最优解。与上述2 种方法不同，精确算法，例如割平面算法，通过割平面的迭代更新，可以很好地探索问题最优解，在混合整数问题求解过程中被广泛采用。

3 算法设计

Benders 分解算法[25]是一种经典的割平面算法，被广泛用于处理现实中的混合整数规划问题（例如机车调度、航空路线规划）。该算法既不会像分支定界法那样迭代次数随着运算变量的增多而显著增加，也不会像动态规划那样产生维度灾难，同时不会出现启发式、模拟退火等算法的巨大方差[26]。本节将基于Benders 分解算法，给出问题P 的高效解决方案。

3.1 子问题描述与转换

在Benders 分解算法中，原问题可以被分解为主问题与子问题两部分，主问题中的优化变量称为复杂变量。当复杂变量固定后，原问题中剩下的优化问题（即子问题）变得相对容易求解。对于问题P，若给定第t次迭代过程中的复杂变量的值，则子问题可以表示为

由于原问题P 中的0-1 变量eij被分解到主问题中，上述子问题中优化变量均为连续变量，该问题可以等效为一个最小费用流问题。本文考虑工业物联网中典型的环境监控场景，边缘网络中各边缘节点负责处理无线传感器采集的环境数据。在环境监控场景下，各边缘节点处的计算任务有着相同的计算优先级[3,15]，即节点丢弃每单位数据的代价相同(ci=cj,∀i,j∈N)。从而问题可进一步转化为网络最大流问题[27]。图2 通过一个含有4 个节点的边缘网络对上述等效关系进行了说明。

图2 子问题等效最大流问题示例

在图2 中，节点2 与节点3 之间的连接线为迭代过程中所确定的需要修复的受损链路，即{ij,ij∈Εr,Εr⊆Ε0}。源节点s与目的节点z为新增的虚拟节点，源节点s与4 个边缘节点的虚拟链路容量为4 个边缘节点的最大计算能力，4 个边缘节点与目的节点z的虚拟链路表示各边缘节点的本地数据计算量需求。图2 中各边上的数值表示该链路的链路容量，从而最大化目的节点z的总到达流等价于最小化总数据的丢弃量。上述转化后的最大流问题，可以通过已有算法，如Ford-Fulkerson 算法[28]，进行高效的多变量问题求解。

3.2 割平面生成与主问题构建

在Benders 分解算法中，子问题的解将代入主问题用于生成主问题中的线性约束，即Benders 割平面。由于本文考虑了完善资源[29]，即对于任意可行的主问题解，总有可行的子问题解，不需要再生成可行割，只需要构建最优割即可。为形成Benders最优割平面，需要利用对偶问题的互补松驰性原理[30]，根据上述子问题的解，提取限制条件式(3)所对应的对偶变量，即可修复链路ij的边际系统增量。

定理1在第t次迭代中的Benders 最优割平面可以表示为

其中，η为子问题目标函数的最优解的上界，θt为子问题在第t次迭代中所求得的目标函数的最优值，即第t次迭代中的最小数据丢弃总代价。

证明见附录1。

将上述Benders 最优割平面代入主问题求解的限制条件中，可得主问题为

与子问题确定边缘网络的数据迁移、计算与丢弃不同，主问题负责确定受损链路集合Ε0中需要被优先修复的链路集合Er。在主、子问题的循环迭代过程中，主问题的求解都是在给定数据迁移、计算与丢弃量的情况下进行的。主问题求解所得的Εr反过来被用于子问题的进一步求解，从而逐步逼近系统的最优数据迁移、计算、丢弃与链路修复策略。

3.3 基于Benders 分解理论的迭代路径修复与计算迁移算法

将上述主问题初始化后代入子问题，并开始循环迭代寻找最优解。若在迭代过程中主问题的决策变量不能满足所有约束条件，则终止算法，原问题无解；否则持续迭代过程直至找到网络最优配置。上述过程的具体步骤如算法1 所示。

算法1基于Benders 分解理论的迭代路径修复与计算迁移算法

当算法收敛后，系统将根据当前迭代计算所得的et，修复其中值为1 的链路。之后，利用子问题的解ft确定节点间的数据流迁移量，依据pt调整各节点的实际计算能力，并丢弃超出计算能力的数据dt。需要注意的是，主问题中η为一个连续变量，e为离散变量，该问题仍是一个混合整数问题。尽管可以采用诸如遗传蚁群算法在内的算法进行求解，但由于其搜索域空间较大，算法复杂度依旧很高。此外，在每次迭代过程中，主问题中新的割平面的引入使算法下界保持了非减特性，但并没有类似机制保障算法上界的单调特性。这种非单调约束界特性将进一步加剧上述算法的计算时间开销。

4 Benders 分解加速算法设计

为解决算法1 提出的基于Benders 分解理论的迭代路径修复与计算迁移算法所存在的问题，本文在迭代求解过程中进一步引入了局部分支技术[31]。其主要目的在于在每次迭代过程中找到更好的问题上界，以期实现上下界的内向夹逼，减少主问题的计算复杂性。

4.1 信赖域与汉明距离

如前文所述，基于割平面的Benders 分解算法并不是一种稳定的算法，在迭代的早期，问题的解会在不同的可行域内大范围波动，从而导致较慢的收敛速度。在本文所考虑的工业物联网中的边缘计算场景下，大规模网络受损所引入的大量优化变量，特别是初始搜索空间为的修复链路决策向量e的引入，将使该收敛速度问题进一步恶化。信赖域是解决上述大范围波动特性问题的一种极佳策略[32]。考虑到主问题中的e是一组0-1 变量，可以采用汉明距离来限制两次迭代解的距离。

假设(e t,d t,p t,ft)为原问题第t次迭代所得到的可行解，此时所有0-1 优化变量中值为1 的集合可以表示为，则第t+1次迭代与第t次迭代的汉明距离为

即第t+1 次迭代中e相对第t次迭代中变化的二进制变量的数目。

为加快收敛速度，可以将解空间分解为2 个相互独立的信赖域

其中，Δt+1表示在第t+1 次迭代中信赖域的规模大小，其值的选取取决于主问题的复杂性及搜索范围的波动性需求。通过上述方式，原问题自然地被分为2 个子解空间，局部分支法便是基于此产生。在局部分支法中，式(11)和式(12)分别被称为左枝和右枝。

4.2 局部分支法

基于汉明距离，原问题P 的解空间可根据Benders 分解第t次迭代所得的可行解(e t,d t,p t,ft)，分割为2 个紧密相连的邻域空间。设ek,k∈Kt为Benders 分解第t次迭代过程中局部分支法迭代所计算的所有e的解（包括可行解与非可行解），其中可行解的集合表示为Lt（Lt⊆Kt）。根据汉明距离，原问题P 可以分支为2 个独立的左右枝问题。其中左枝问题为

其中，式(13)表示不重复比较之前已比较过的e值，式(14)表示当前左枝应该是上一级分支中的右分枝的分枝，式(15)表示左枝限制条件，为当前获取的最优解。相应地可以得到右枝问题为

其中，式(16)表示右枝限制。

令(ek+1,dk+1,pk+1,fk+1)为左枝问题Pk的最优解，对应的目标函数值为φk1+，则有局部分支法算法流程如算法2 所示。

算法2局部分支算法

算法2 循环条件中的Tmax是为了避免在计算过程中，由于汉明距离设置过大导致分枝问题无法解出的情况。在大规模受损网络下，修复链路决策e的解空间规模十分庞大，选取较小的信赖域规模Δt将更有利于提升左枝问题的计算速度。

4.3 基于局部分支法的Benders 分解加速算法

将局部分支算法融入Benders 分解得到的基于局部分支法加速的Benders 分解算法如算法3 所示。

算法3基于局部分支法的Benders 分解加速理论的迭代路径修复与计算迁移算法

与算法1 类似，当算法3 收敛后，系统将根据当前迭代计算所得的et确定修复链路集合。然后，根据计算所得ft、pt及dt的值，确定网络中数据的迁移、计算与丢弃量。不同于算法1，算法3 通过局部分支技术，保证了原问题P 的上界在迭代过程中的严格递减。对于大规模受损网络，这意味着每次迭代过程中，主问题M 所需优化的链路修复决策向量te的搜索空间逐步减少，解的搜索速度随着迭代次数的增加而逐渐加快。

上述算法每次迭代获得的新割平面中，并不是所有的割平面都需要加入主问题求解过程，可以只添加最深的割平面（即使可行域最大程度减少的割平面）。考虑到算法的收敛性要求与Benders 分解初始阶段的糟糕表现，可以仅在初始迭代阶段添加信赖域限制。当迭代趋于稳定后，解除该限制条件。

值得注意的是，在每次分支过程中，分支问题P1,P2,…都拥有与原问题P 相同的结构。因此针对每个分支问题，可以单独使用算法1 进行求解。之前的分支问题求得的割平面也可以继续用于后续分支问题的求解。

5 仿真分析

本节对所提基于Benders 分解理论的迭代路径修复与计算迁移算法（下文简称为Benders 分解算法）以及基于局部分支法的Benders 分解加速理论的迭代路径修复与计算迁移算法（下文简称为Benders 分解加速算法）性能进行了仿真测试，并验证分析了所提算法相较于其他基准算法的性能优势。

5.1 仿真参数与对比算法

本文考虑一个包含N=50 个节点的边缘计算网络，网络修复初期各节点的最大计算能力相互独立且均匀分布于[10,25]Gbit。考虑到计算能力与计算需求的匹配性，网络修复初期节点的计算需求ir同样服从[10,25]Gbit 上的均匀分布。不失一般性地，假设边缘网络原始拓扑中有线链路数量=2N，网络拓扑同随机网络[4]，且节点间数据传输处处可达。考虑到计算节点的处理能力波动范围，链路容量服从[5,15]Gbit 上的均匀分布。为模拟网络大规模受损情况，在下文中，如无特殊说明，链路受损比例q=75%。假设修复每条受损链路的成本cij均匀分布于[1×104,2×104]元，因计算能力不足而丢弃数据的代价ci为104元/Gbit。

为了验证本文所提受损网络修复机制的效果，将本文算法与以下基准算法进行比较。

1）随机修复算法。随机选择网络中受损的链路进行修复，不考虑网络的具体拓扑结构与网络计算流迁移的动态特征。

2）最大连通图修复算法[16]。修复网络的最大连通图中的所有受损链路，确保网络中最大连通图中的所有节点能达到强连通状态。

3）介数中心性排序修复算法[11]。分析边缘网络受损前的拓扑结构，对各条有线链路的介数中心性进行排序，优先修复介数中心性大的受损链路，修复链路数量与所提算法相同。

5.2 算法收敛性

图3 为所提Benders 分解算法与Benders 分解加速算法的收敛性对比。从图3 可以看出，2 种算法可以在有限次数内实现快速迭代，具有较好的收敛性。需要注意的是，图3 中迭代次数表征的是算法1 与算法3 中主问题与子问题的总循环迭代次数。在每次迭代过程中，子问题的计算复杂度为O(|N||Ε|2)，主问题计算复杂度为O(n|Ε0|3),其中n为主问题求解的内循环迭代次数。尽管Benders分解加速算法相对Benders 分解算法，总迭代次数只减少一次，但其实际计算时间复杂度降低O(|N||Ε|2+n|Ε0|3)。在大规模受损网络环境下，该计算时间复杂度的改善仍十分可观。从图3 中相同迭代次数情况下算法上下界的对比可以看出，相对于Benders 分解算法，局部分支法辅助的Benders分解加速算法由于有更深割平面的引入，收敛速度得到显著提升，能够更好地适应大规模网络的应用需求。此外，Benders 分解算法与Benders 分解加速算法在收敛后系统总开销趋于一致。因此，在下文中，为便于与基准算法进行对比，Benders 分解算法和Benders 分解加速算法统称为“本文算法”。

图3 所提Benders 分解算法与Benders 分解加速算法收敛性对比

5.3 算法性能

图4 和图5 分别为不同网络受损程度q以及不同网络规模N情况下，本文算法、随机修复算法、最大连通图修复算法、介数中心性排序修复算法的系统总开销曲线。从图4 和图5 可以看出，在不同网络受损程度以及网络规模情况下，由于考虑了网络中节点的计算需求与实际计算能力、链路容量限制等网络动态特征，本文算法性能均优于基准算法。值得注意的是，最大连通图修复算法的系统总开销性能是所有算法中最差的，甚至弱于随机修复算法，这与现实网络中网络修复呈现的状态十分吻合。在现实网络中，修复过程总是先使网络中形成大大小小各自独立的簇，在修复的最后才将各个簇连接起来形成最大连通图[13]。

图4 不同网络受损程度下算法性能对比

图5 不同网络规模下算法性能对比

5.4 算法多场景适用性

图6 和图7 分别表示不同单位数据丢弃代价场景下本文算法修复的受损链路数目与计算数据丢弃量。考虑到本文算法系统总开销对于链路修复成本和计算数据丢弃的双重考量，随着单位数据丢弃代价ci的增大，修复链路数目与数据丢弃量呈现出相反的增减关系。与经验相符，随着ci增大，即数据丢弃成本增大，网络倾向于修复更多的链路使计算需求得以满足。当ci取值在[1,1.5]万元/Gbit 时，图7 中数据丢弃量开始出现显著下降，这是因为在该范围内，系统刚好处于敏感临界点附近。在该值附近，系统均衡修复成本与丢弃数据开销的能力最强。任意微小的ci值变化都可能带来均衡决策的较大幅度改变。在ci超过2 万元/Gbit 后，继续修复受损链路带来的边际效益降低，网络修复链路数目与计算数据丢弃量保持稳定。可以看出，本文算法能够很好地适用于各种不同数据丢弃代价场景，具有较好的可扩展性与适应性。

图6 不同单位数据丢弃代价下本文算法受损链路修复数目

图7 不同单位数据丢弃代价下本文算法计算数据丢弃量

为进一步分析本文算法在不同网络拓扑场景下的性能，本文将网络形式由单一的随机网络场景扩展至栅格网络与无标度网络[33]。与随机网络不同，栅格网络各节点的度完全相同，无标度网络节点的度服从幂律分布。从图8 可以看出，在3 类网络下，各算法性能均会产生不同程度的波动，但本文算法的系统总开销性能均优于基准算法。得益于对于网络拓扑与动态特征的联合分析，本文算法具有很好的多场景适应性。

图8 不同网络拓扑下算法对比情况（N=100）

6 结束语

本文针对工业物联网中边缘计算网络的易受损特征，提出了一种网络大规模受损后的修复机制，给出了优先修复链路集合决策与计算迁移配置的联合优化方法，有效缓解了网络修复初期有限修复资源与大量数据计算需求的矛盾。考虑到原始问题的求解困难，利用Benders 分解算法将其转化为更易求解的主问题与子问题，通过割平面的不断更新，逐步逼近问题最优解。进一步地，结合局部分支法，设计了一种Benders 分解加速算法，有效提升了算法收敛速度。仿真结果表明，相对现有基于拓扑结构的修复算法，本文算法具有较好的系统修复性能。

尽管出于数据公平性考量，本文考虑计算数据具有相同处理优先级，即不同节点丢弃每单位数据的代价相同，本文思想仍可以十分便捷地扩展至每单位数据丢弃代价不同的场景，只需将子问题解法替换为现有最小费用流算法（如Dinic 算法）即可。

本文算法主要针对节点间为有线链路连接的情况。对于存在动态无线链路的场景，例如无人机充当移动边缘节点的场景，信道容量随无人机位置改变而改变，需要进一步联合考量无人机运行轨迹、无线频谱分配等问题。这将使本已复杂的网络修复问题变得更加难以求解，已超出本文的考虑范围，留待后续研究。

附录1 Benders 最优割平面证明