于存謙，李靖宇，李 航，張春芳，何榮希，林 彬,3

(1.大連海事大學 信息科學技術學院，遼寧 大連 116026；2.沈陽航空航天大學 計算機學院，沈陽 110136;3.鵬程實驗室 網(wǎng)絡通信研究中心，廣東 深圳 518052)

0 引 言

隨著移動互聯(lián)網(wǎng)的快速發(fā)展，移動終端的通信流量呈現(xiàn)出爆炸式的增長，預計2025年全球移動互聯(lián)網(wǎng)用戶總數(shù)會達到50億[1]。近年來，邊緣計算(Edge Computing,EC)結合彈性光網(wǎng)的服務模式兼顧了用戶側的計算服務和核心網(wǎng)中靈活的頻譜分配，使用戶可將計算任務放置在恰當?shù)倪h端單元(Remote Unit,RU)執(zhí)行，而將繁重的計算任務委托給云端，提高了計算效率并降低了延遲[2]。例如，工廠和港口擁有大量快速移動的自動導引運輸車(Automated Guided Vehicle,AGV)和攜帶控制設備的工程師，這為EC網(wǎng)絡在工業(yè)和物流領域的服務自適應性帶來了需求。

AGV本身是具備一定數(shù)據(jù)收集和計算能力的智能移動終端，并需實時保持載重運轉，故其無人化控制程度高于民用的自動駕駛車輛，這就要求AGV頻繁與RU節(jié)點溝通。AGV、機械臂和便攜控制器等設備利用RU側的EC能力提供極低延遲的數(shù)據(jù)分析服務，甚至是任務拆解和送達云端，這樣便構成了一個極簡的特定用途的網(wǎng)絡功能切片，即工業(yè)虛擬網(wǎng)絡(Virtual Network,VN)，它為生產(chǎn)定制化帶來革命性的新載體。VN中虛擬節(jié)點包括AGV的計算單元、RU側的輕量級容器和云端虛擬機(Virtual Machine,VM)，連接它們的虛擬鏈路可由光纖鏈路、射頻鏈路以及mmWave鏈路等來構成[3]。

工廠和港口通常占地面積大且地形復雜，隨著AGV在不同的RU間移動，需要遷移其EC服務以跟隨AGV來保持EC的低延遲優(yōu)勢。但遷移可能會導致EC服務中斷并消耗網(wǎng)絡資源，而不遷移服務則會加劇數(shù)據(jù)延遲。因此，設計合理的Container遷移策略，滿足AGV在生產(chǎn)側的運算和低延遲需求，實現(xiàn)EC網(wǎng)絡的不間斷服務和負載均衡，已成為提高生產(chǎn)效率和網(wǎng)絡服務質量(Quality of Service,QoS)的熱點問題。

由于AGV移動的不確定性，以及與遷移和遠程數(shù)據(jù)傳輸相關成本間的復雜權衡，做出最佳服務遷移決策需考慮時域、光鏈路和計算資源等多重限制。故本文首先建立了最小化服務宕機時間、頻譜資源占用與提高負載均衡為聯(lián)合優(yōu)化目標的混合整數(shù)非線性規(guī)劃(Mixed Integer Nonlinear Programming,MN-ILP)模型，隨后設計了基于停留時間(Stay Time in Cell,STC)的Container遷移判決和提高負載均衡的最優(yōu)遷移目標RU(Target-destination RU,TRU)選取策略，并提出了基于AGV時域和空間位置信息的自適應Container遷移算法(Adaptive Container Migration Algorithm based on Time-domain and Location Information,ACMA-TLI)。當然，本文所提數(shù)學模型和算法不局限于工業(yè)場景中的AGV，同樣適合于行人和其他行駛載體，僅在生產(chǎn)側產(chǎn)生的前端數(shù)據(jù)和移動速度存在差異，其基于邊緣-云協(xié)同計算(Edge-Cloud Computing,ECC)網(wǎng)絡和服務遷移需求是一致的。

1 相關工作與研究動機

1.1 利用Container遷移解決網(wǎng)絡QoS下降

vSphere等傳統(tǒng)虛擬化技術以操作系統(tǒng)為中心，而Container技術以應用程序為中心，可共享主機的操作系統(tǒng)內(nèi)核，比VM體量更小。Container遷移被視為一種高效、輕量級的動態(tài)負載平衡虛擬化技術,目前兩個主要的研究方向是遷移策略和具體遷移的實施[4]。通過Container遷移在減少計算延遲[5]、平衡資源利用[6]、降低成本和能源消耗[7]等方面都取得了不錯效果。圖1展示了基于Linux Docker Container平臺為移動AGV服務的Container遷移的示例。AGV漸漸遠離初始EC服務器1，服務遷移將承載APP A的Container遷移到服務器2上，而后AGV可直連服務器2獲取APP A。

圖1 Docker環(huán)境下的Container遷移示意圖

1.2 面向工業(yè)用戶移動性的遷移判決

AGV等生產(chǎn)設備在移動中切換無線鏈路的接入點，造成網(wǎng)絡QoS下降甚至管控上的困難。頻繁或盲目服務遷移所造成的遷移開銷會給服務器和網(wǎng)絡帶來不必要的壓力，且遷移鏈路偶發(fā)的斷裂也會降低用戶體驗甚至造成AGV碰撞危險[8]。本文方法只需在每個時隙采集用戶位置，根據(jù)AGV在小區(qū)內(nèi)的STC來判斷其所在RU是否為目的地(End-destination RU,ERU)，以此來合理地啟動服務遷移，避免短STC造成的頻繁遷移。

1.3 目標RU的選取和Container遷移損失

以往的遷移算法常采取直接遷移至ERU的策略，忽視邊緣計算資源和局部網(wǎng)絡資源缺乏均衡性對網(wǎng)絡吞吐量和后續(xù)遷移業(yè)務的影響。當目標小區(qū)的資源不充裕時，鄰近的資源豐富小區(qū)可以承擔服務遷移為后續(xù)Container節(jié)約空間。但傳統(tǒng)負載均衡遷移算法著眼于資源消耗最小的鄰近服務器，卻顧此失彼地提高了Container為AGV提供服務的往返時間(Round-Rrip Time,RTT)[9]。故遷移目標RU的選取應兼顧計算、網(wǎng)絡資源使用率以及與用戶的路由距離。典型的遷移損失包括服務宕機時間過長以及遷移長時間占用熱點區(qū)域的鏈路頻譜。此前學者已就此兩問題分別提出了方案，但仍未見同時優(yōu)化兩目標并調和彼此矛盾的研究[8]。本文的目的是基于用戶的時-空維度信息，同時考慮遷移中和遷移后的資源占用率，最小化邊緣服務遷移造成的服務中斷時間和遷移資源成本。

2 網(wǎng)絡和數(shù)學模型

本文針對工廠和港口的特殊地形采用包括C-RAN(Cloud-Radio Access Network)、GPON(Gigabit Passive Optical Network,GPON)和光城域網(wǎng)在內(nèi)的融合網(wǎng)絡架構，每個交換節(jié)點都對應一個獨立的無源光網(wǎng)絡(Passive Optical Network,PON)接入網(wǎng)，如圖2所示。首先，網(wǎng)絡可表示為G(N,E)，其中N={Nsw,Nru,Nagv}分別為交換節(jié)點、RU和AGV的節(jié)點集，E={Ewl,Eof}為由無線鏈路和光纖組成的邊集合。在RU的地理位置為Nru={RUi,j}，i為RU所在PON編號，j為RU的PON內(nèi)編號，如RU1,2為PON1的2號RU。

圖2 網(wǎng)絡架構圖及AGV在PON內(nèi)和PON間移動示例

表1 參數(shù)和變量

2.1 容器遷移判決

(1)

(2)

(3)

(4)

(5)

2.2 遷移目標RU的選取

式(6)計算當前RUi,j的資源使用率，其中α+β=1。式(7)和式(8)計算目標PONi內(nèi)RUi,j在當前時隙的計算資源使用率。式(9)和式(10)計算RUi,j在當前時隙的無線鏈路頻譜資源使用率。由于本文關注的是在線EC服務遷移而非深入探討蜂窩網(wǎng)的頻譜分配問題，故將RUi,j的無線鏈路資源使用率等價為計算資源使用率[11]，使式(6)轉化為式(11)，其中μr,c≤1為無線鏈路資源與計算資源轉換比。

(6)

(7)

(8)

(9)

(10)

?i,?ji,j∈Nru。

(11)

(12)

(13)

2.3 Container最優(yōu)化遷移過程

首先，補充表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問題，雖采用順序線性規(guī)劃松弛MN-ILP，但限制條件較多，不適合大規(guī)模拓撲。下節(jié)將基于數(shù)學模型進行算法設計，并針對遷移判決和最優(yōu)TRU選取設計子算法。

3 ACMA-TLI算法

本節(jié)提出ACMA-TLI，旨在優(yōu)化宕機時間和遷移頻譜開銷。ACMA-TLI針對數(shù)學模型中兩個核心問題設計了子算法：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 根據(jù)頻域信息構建輔助圖，刪掉資源不足的光纖鏈路，同時利用頻譜資源在時域的信息由式(18)～(21)計算鏈路的新代價，基于Dijkstra's算法選取源RU至TRU的最小遷移開銷路徑，并基于頻譜連續(xù)性、一致性和不重疊性選取最優(yōu)子載波段，執(zhí)行Step 6。

ACMA-TLI算法主要由CMMA、TRSA和遷移數(shù)據(jù)的RSA部分構成，其中CMMA的時間復雜度為O(2·|Γ|·|Nagv|)，TRSA的為O(|Nru|)，RSA的為O(|Bof|·|Nsw|2)。最終ACMA-TLI的時間復雜度經(jīng)化簡為O(|Γ|·|Nagv|+|Bof|·|Nsw|2)=O(|Bof|·|Nsw|2)。

4 仿真與分析

若將順序線性規(guī)劃中時隙的粒度劃分得足夠細，則在單位時隙內(nèi)可視同靜態(tài)。本節(jié)采用5 min作為的時隙長度，并采集港口日常工作時段內(nèi)的數(shù)據(jù)作為輸入量，拓撲如圖2所示。

本文采用Visual C++在Intel(R) Xeon(R) CPU E3-1225 v6@3.30 GHz 8 GB RAM Windows-7 64位平臺搭建仿真環(huán)境，使用LINGO 18.0對數(shù)學模型進行求解。仿真參數(shù)設置如表3所示。

表3 仿真參數(shù)設置

(a)CAAM、QASM

(b)MN-ILP平均延遲圖3 ACMA-TLI與CAAM、QASM以及MN-ILP的平均延遲對比

圖4比較了ACMA-TLI、CAAM、QASM和MN-ILP的STA。在圖4(a)中，隨著業(yè)務量增長CAAM、QASM與ACMA-TLI的STA差值越來越大，最大為153 tfs。這是由于CAAM的Container頻繁遷移，以占用更多頻譜來減少遷移時間，但隨著業(yè)務量增加剩余頻譜資源愈發(fā)緊張，不能提供足夠的頻譜去抵消平均延遲的升高。雖然QASM可通過遷移閾值減少遷移的頻次，但其粗粒度的遷移目標選取會影響資源消耗。ACMA-TLI通過式(5)和式(21)進行合理的遷移判斷，規(guī)避了PON內(nèi)遷移造成的資源浪費。從圖4(b)可看出，ACMA-TLI與MN-ILP的STA結果比較接近，其最大差值控制在17 tfs內(nèi)。

(a)CAAM、QASM

(b)MN-ILP圖4 ACMA-TLI與CAAM、QASM以及MN-ILP的STA對比

圖5 三種算法的業(yè)務量阻塞率對比

圖6 三種算法的服務器資源占用率方差對比

5 結 論

針對工業(yè)AGV移動導致EC服務頻繁遷移的問題，本文首先抽象出最小化宕機時間和Container遷移開銷為聯(lián)合優(yōu)化目標的MN-ILP模型，并設計了Container遷移判決和TRU選取策略。同時，提出了基于AGV時域和位置信息的自適應Container遷移算法ACMA-TLI。仿真結果表明，相較于對比算法，ACMA-TLI算法在業(yè)務量阻塞率、平均延遲和PON內(nèi)資源負載均衡等方面取得了一定優(yōu)勢。本文嘗試令Container遷移等新一代信息技術與工業(yè)互聯(lián)網(wǎng)架構有機融合，所提模型和算法可為解決工業(yè)生產(chǎn)中的具體問題提供新的途徑。