基于自动导引车时-空信息使能的边云服务迁移策略*

于存谦，李靖宇，李 航，张春芳，何荣希，林 彬,3

(1.大连海事大学 信息科学技术学院，辽宁 大连 116026；2.沈阳航空航天大学 计算机学院，沈阳 110136;3.鹏程实验室 网络通信研究中心，广东 深圳 518052)

0 引 言

随着移动互联网的快速发展，移动终端的通信流量呈现出爆炸式的增长，预计2025年全球移动互联网用户总数会达到50亿[1]。近年来，边缘计算(Edge Computing,EC)结合弹性光网的服务模式兼顾了用户侧的计算服务和核心网中灵活的频谱分配，使用户可将计算任务放置在恰当的远端单元(Remote Unit,RU)执行，而将繁重的计算任务委托给云端，提高了计算效率并降低了延迟[2]。例如，工厂和港口拥有大量快速移动的自动导引运输车(Automated Guided Vehicle,AGV)和携带控制设备的工程师，这为EC网络在工业和物流领域的服务自适应性带来了需求。

AGV本身是具备一定数据收集和计算能力的智能移动终端，并需实时保持载重运转，故其无人化控制程度高于民用的自动驾驶车辆，这就要求AGV频繁与RU节点沟通。AGV、机械臂和便携控制器等设备利用RU侧的EC能力提供极低延迟的数据分析服务，甚至是任务拆解和送达云端，这样便构成了一个极简的特定用途的网络功能切片，即工业虚拟网络(Virtual Network,VN)，它为生产定制化带来革命性的新载体。VN中虚拟节点包括AGV的计算单元、RU侧的轻量级容器和云端虚拟机(Virtual Machine,VM)，连接它们的虚拟链路可由光纤链路、射频链路以及mmWave链路等来构成[3]。

工厂和港口通常占地面积大且地形复杂，随着AGV在不同的RU间移动，需要迁移其EC服务以跟随AGV来保持EC的低延迟优势。但迁移可能会导致EC服务中断并消耗网络资源，而不迁移服务则会加剧数据延迟。因此，设计合理的Container迁移策略，满足AGV在生产侧的运算和低延迟需求，实现EC网络的不间断服务和负载均衡，已成为提高生产效率和网络服务质量(Quality of Service,QoS)的热点问题。

由于AGV移动的不确定性，以及与迁移和远程数据传输相关成本间的复杂权衡，做出最佳服务迁移决策需考虑时域、光链路和计算资源等多重限制。故本文首先建立了最小化服务宕机时间、频谱资源占用与提高负载均衡为联合优化目标的混合整数非线性规划(Mixed Integer Nonlinear Programming,MN-ILP)模型，随后设计了基于停留时间(Stay Time in Cell,STC)的Container迁移判决和提高负载均衡的最优迁移目标RU(Target-destination RU,TRU)选取策略，并提出了基于AGV时域和空间位置信息的自适应Container迁移算法(Adaptive Container Migration Algorithm based on Time-domain and Location Information,ACMA-TLI)。当然，本文所提数学模型和算法不局限于工业场景中的AGV，同样适合于行人和其他行驶载体，仅在生产侧产生的前端数据和移动速度存在差异，其基于边缘-云协同计算(Edge-Cloud Computing,ECC)网络和服务迁移需求是一致的。

1 相关工作与研究动机

1.1 利用Container迁移解决网络QoS下降

vSphere等传统虚拟化技术以操作系统为中心，而Container技术以应用程序为中心，可共享主机的操作系统内核，比VM体量更小。Container迁移被视为一种高效、轻量级的动态负载平衡虚拟化技术,目前两个主要的研究方向是迁移策略和具体迁移的实施[4]。通过Container迁移在减少计算延迟[5]、平衡资源利用[6]、降低成本和能源消耗[7]等方面都取得了不错效果。图1展示了基于Linux Docker Container平台为移动AGV服务的Container迁移的示例。AGV渐渐远离初始EC服务器1，服务迁移将承载APP A的Container迁移到服务器2上，而后AGV可直连服务器2获取APP A。

图1 Docker环境下的Container迁移示意图

1.2 面向工业用户移动性的迁移判决

AGV等生产设备在移动中切换无线链路的接入点，造成网络QoS下降甚至管控上的困难。频繁或盲目服务迁移所造成的迁移开销会给服务器和网络带来不必要的压力，且迁移链路偶发的断裂也会降低用户体验甚至造成AGV碰撞危险[8]。本文方法只需在每个时隙采集用户位置，根据AGV在小区内的STC来判断其所在RU是否为目的地(End-destination RU,ERU)，以此来合理地启动服务迁移，避免短STC造成的频繁迁移。

1.3 目标RU的选取和Container迁移损失

以往的迁移算法常采取直接迁移至ERU的策略，忽视边缘计算资源和局部网络资源缺乏均衡性对网络吞吐量和后续迁移业务的影响。当目标小区的资源不充裕时，邻近的资源丰富小区可以承担服务迁移为后续Container节约空间。但传统负载均衡迁移算法着眼于资源消耗最小的邻近服务器，却顾此失彼地提高了Container为AGV提供服务的往返时间(Round-Rrip Time,RTT)[9]。故迁移目标RU的选取应兼顾计算、网络资源使用率以及与用户的路由距离。典型的迁移损失包括服务宕机时间过长以及迁移长时间占用热点区域的链路频谱。此前学者已就此两问题分别提出了方案，但仍未见同时优化两目标并调和彼此矛盾的研究[8]。本文的目的是基于用户的时-空维度信息，同时考虑迁移中和迁移后的资源占用率，最小化边缘服务迁移造成的服务中断时间和迁移资源成本。

2 网络和数学模型

本文针对工厂和港口的特殊地形采用包括C-RAN(Cloud-Radio Access Network)、GPON(Gigabit Passive Optical Network,GPON)和光城域网在内的融合网络架构，每个交换节点都对应一个独立的无源光网络(Passive Optical Network,PON)接入网，如图2所示。首先，网络可表示为G(N,E)，其中N={Nsw,Nru,Nagv}分别为交换节点、RU和AGV的节点集，E={Ewl,Eof}为由无线链路和光纤组成的边集合。在RU的地理位置为Nru={RUi,j}，i为RU所在PON编号，j为RU的PON内编号，如RU1,2为PON1的2号RU。

图2 网络架构图及AGV在PON内和PON间移动示例

表1 参数和变量

2.1 容器迁移判决

(1)

(2)

(3)

(4)

(5)

2.2 迁移目标RU的选取

式(6)计算当前RUi,j的资源使用率，其中α+β=1。式(7)和式(8)计算目标PONi内RUi,j在当前时隙的计算资源使用率。式(9)和式(10)计算RUi,j在当前时隙的无线链路频谱资源使用率。由于本文关注的是在线EC服务迁移而非深入探讨蜂窝网的频谱分配问题，故将RUi,j的无线链路资源使用率等价为计算资源使用率[11]，使式(6)转化为式(11)，其中μr,c≤1为无线链路资源与计算资源转换比。

(6)

(7)

(8)

(9)

(10)

∀i,∀ji,j∈Nru。

(11)

(12)

(13)

2.3 Container最优化迁移过程

首先，补充表2所示变量。

表2 补充变量

Minimizeη·Dm+μ·Om,

(14)

(15)

(16)

Dru(ρi,j),∀ρi,j∈Nru,

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

模型中存在变量相乘的MN-ILP问题，虽采用顺序线性规划松弛MN-ILP，但限制条件较多，不适合大规模拓扑。下节将基于数学模型进行算法设计，并针对迁移判决和最优TRU选取设计子算法。

3 ACMA-TLI算法

本节提出ACMA-TLI，旨在优化宕机时间和迁移频谱开销。ACMA-TLI针对数学模型中两个核心问题设计了子算法：Container迁移判决算法(CMM Algorithm,CMMA)和TRU选取算法(TRU Selection Algorithm,TRSA)。

CMMA伪代码如下：

Output:ψk

1 for each time-slot ∀Tx∈Γdo

5 end for

9 calculateψk=f(k,Tx) based on Eq.(5);

10 ifψkthen

12 end if

TRSA伪代码如下：

Output:TRU index and IP address.

1 for ∀RUi,j∈PONido

7 end if

8 end for

10 run ARUOR I or II according toρi,ERU;

12 end if

3.1 基于TRSA的资源负载均衡

(29)

(30)

3.2 ACMA-TLI步骤与时间复杂度分析

Step5 根据频域信息构建辅助图，删掉资源不足的光纤链路，同时利用频谱资源在时域的信息由式(18)～(21)计算链路的新代价，基于Dijkstra's算法选取源RU至TRU的最小迁移开销路径，并基于频谱连续性、一致性和不重叠性选取最优子载波段，执行Step 6。

ACMA-TLI算法主要由CMMA、TRSA和迁移数据的RSA部分构成，其中CMMA的时间复杂度为O(2·|Γ|·|Nagv|)，TRSA的为O(|Nru|)，RSA的为O(|Bof|·|Nsw|2)。最终ACMA-TLI的时间复杂度经化简为O(|Γ|·|Nagv|+|Bof|·|Nsw|2)=O(|Bof|·|Nsw|2)。

4 仿真与分析

若将顺序线性规划中时隙的粒度划分得足够细，则在单位时隙内可视同静态。本节采用5 min作为的时隙长度，并采集港口日常工作时段内的数据作为输入量，拓扑如图2所示。

本文采用Visual C++在Intel(R) Xeon(R) CPU E3-1225 v6@3.30 GHz 8 GB RAM Windows-7 64位平台搭建仿真环境，使用LINGO 18.0对数学模型进行求解。仿真参数设置如表3所示。

表3 仿真参数设置

(a)CAAM、QASM

(b)MN-ILP平均延迟图3 ACMA-TLI与CAAM、QASM以及MN-ILP的平均延迟对比

图4比较了ACMA-TLI、CAAM、QASM和MN-ILP的STA。在图4(a)中，随着业务量增长CAAM、QASM与ACMA-TLI的STA差值越来越大，最大为153 tfs。这是由于CAAM的Container频繁迁移，以占用更多频谱来减少迁移时间，但随着业务量增加剩余频谱资源愈发紧张，不能提供足够的频谱去抵消平均延迟的升高。虽然QASM可通过迁移阈值减少迁移的频次，但其粗粒度的迁移目标选取会影响资源消耗。ACMA-TLI通过式(5)和式(21)进行合理的迁移判断，规避了PON内迁移造成的资源浪费。从图4(b)可看出，ACMA-TLI与MN-ILP的STA结果比较接近，其最大差值控制在17 tfs内。

(a)CAAM、QASM

(b)MN-ILP图4 ACMA-TLI与CAAM、QASM以及MN-ILP的STA对比

图5 三种算法的业务量阻塞率对比

图6 三种算法的服务器资源占用率方差对比

5 结 论

针对工业AGV移动导致EC服务频繁迁移的问题，本文首先抽象出最小化宕机时间和Container迁移开销为联合优化目标的MN-ILP模型，并设计了Container迁移判决和TRU选取策略。同时，提出了基于AGV时域和位置信息的自适应Container迁移算法ACMA-TLI。仿真结果表明，相较于对比算法，ACMA-TLI算法在业务量阻塞率、平均延迟和PON内资源负载均衡等方面取得了一定优势。本文尝试令Container迁移等新一代信息技术与工业互联网架构有机融合，所提模型和算法可为解决工业生产中的具体问题提供新的途径。