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

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

0 引 言

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

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

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

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

1 相關(guān)工作與研究動(dòng)機(jī)

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

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

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

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

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

1.3 目標(biāo)RU的選取和Container遷移損失

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

2 網(wǎng)絡(luò)和數(shù)學(xué)模型

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

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

表1 參數(shù)和變量

2.1 容器遷移判決

(1)

(2)

(3)

(4)

(5)

2.2 遷移目標(biāo)RU的選取

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

(6)

(7)

(8)

(9)

(10)

?i,?ji,j∈Nru。

(11)

(12)

(13)

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

首先，補(bǔ)充表2所示變量。

表2 補(bǔ)充變量

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ī)模拓?fù)?。下?jié)將基于數(shù)學(xué)模型進(jìn)行算法設(shè)計(jì)，并針對(duì)遷移判決和最優(yōu)TRU選取設(shè)計(jì)子算法。

3 ACMA-TLI算法

本節(jié)提出ACMA-TLI，旨在優(yōu)化宕機(jī)時(shí)間和遷移頻譜開銷。ACMA-TLI針對(duì)數(shù)學(xué)模型中兩個(gè)核心問題設(shè)計(jì)了子算法：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的資源負(fù)載均衡

(29)

(30)

3.2 ACMA-TLI步驟與時(shí)間復(fù)雜度分析

Step5 根據(jù)頻域信息構(gòu)建輔助圖，刪掉資源不足的光纖鏈路，同時(shí)利用頻譜資源在時(shí)域的信息由式(18)～(21)計(jì)算鏈路的新代價(jià)，基于Dijkstra's算法選取源RU至TRU的最小遷移開銷路徑，并基于頻譜連續(xù)性、一致性和不重疊性選取最優(yōu)子載波段，執(zhí)行Step 6。

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

4 仿真與分析

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

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

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

(a)CAAM、QASM

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

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

(a)CAAM、QASM

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

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

圖6 三種算法的服務(wù)器資源占用率方差對(duì)比

5 結(jié) 論

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