面向用戶移動的邊緣云服務(wù)遷移方法*

李 苗

（中國石油大學(xué)（華東）計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 青島 266580）

1 引言

用戶移動過程中對服務(wù)質(zhì)量的實(shí)時(shí)需求不斷提高，如AR 游戲、自動駕駛［1］等，移動邊緣計(jì)算［2］以其為移動應(yīng)用提供超低服務(wù)時(shí)延的能力而日益受到重視。然而邊緣服務(wù)器的計(jì)算能力以及覆蓋范圍也是有限的，因此服務(wù)遷移應(yīng)用而生［3］。同時(shí)，時(shí)延與遷移開銷之間的優(yōu)化問題也更加突出，最初的解決方案是將假定用戶移動模型的遷移問題轉(zhuǎn)化為特定的馬爾科夫決策（MDP）系統(tǒng)框架來求解出最優(yōu)的遷移決策［4］。Wang［5］等建立了一個(gè)基于用戶移動距離的系統(tǒng)來決定何時(shí)何地進(jìn)行決策，但該系統(tǒng)可伸縮性較低，不能夠適應(yīng)于各種用戶移動場景。由于原有的MDP 決策在大量用戶移動時(shí)會出現(xiàn)狀態(tài)空間爆炸現(xiàn)象，因此將該遷移決策映射到強(qiáng)化學(xué)習(xí)決策的方法被相關(guān)的研究學(xué)者所采用［6］。隨后又提出了動態(tài)調(diào)配遷移過程中邊緣云資源，從而減少服務(wù)資源浪費(fèi)現(xiàn)象的發(fā)生［7］。但是這些方案中存在著用戶移動不確定、決策算法復(fù)雜以及系統(tǒng)架構(gòu)可擴(kuò)展較低的問題。因此本文提出的無模型深度強(qiáng)化學(xué)習(xí)算法建立了極具普適性的系統(tǒng)模型且可實(shí)現(xiàn)多個(gè)優(yōu)化目標(biāo)的快速遷移決策的功能。

2 系統(tǒng)模型

服務(wù)遷移［8］過程是將為移動用戶提供服務(wù)的源邊緣服務(wù)節(jié)點(diǎn)遷移至目標(biāo)邊緣服務(wù)節(jié)點(diǎn)，從而在用戶移動時(shí)可以降低服務(wù)延遲，提高服務(wù)體驗(yàn)度［9］。圖1展示的是用戶移動過程中邊緣云的服務(wù)遷移對比圖，其中圖（a）為不遷移過程，圖（b）為遷移過程。因此構(gòu)建通用的系統(tǒng)模型是高效遷移決策的基本要求，其可以使得無模型的深度強(qiáng)化學(xué)習(xí)算法實(shí)現(xiàn)多種優(yōu)化目標(biāo)需求的遷移決策。接下來將通過邊緣云網(wǎng)絡(luò)場景、用戶移動模塊、邊緣云服務(wù)模塊來介紹該系統(tǒng)模型。

圖1 服務(wù)遷移流程圖

2.1 邊緣云網(wǎng)絡(luò)場景

邊緣云服務(wù)遷移的網(wǎng)絡(luò)場景由基站（節(jié)點(diǎn)）、中間節(jié)點(diǎn)和移動用戶構(gòu)成，邊緣云服務(wù)隨機(jī)的放置在節(jié)點(diǎn)上，主要功能模塊由移動用戶模塊和邊緣云服務(wù)模塊組成。在該場景中邊緣云服務(wù)模塊收集移動用戶模塊中的相關(guān)信息，并且根據(jù)服務(wù)遷移的性能指標(biāo)來來決定邊緣云服務(wù)是否進(jìn)行遷移。

在該網(wǎng)絡(luò)架構(gòu)中的節(jié)點(diǎn)集合為B，b(b?B)被定義為其中的一個(gè)節(jié)點(diǎn)。邊緣云服務(wù)節(jié)點(diǎn)Mi?M隨機(jī)放置在邊緣云網(wǎng)絡(luò)中的任意節(jié)點(diǎn)上，并且為每個(gè)邊緣云設(shè)置了一個(gè)鄰域K。us(t)定義的是在t時(shí)為用戶u提供服務(wù)的信息。bu(t)?B定義的是在時(shí)間t時(shí)用戶所連的接入點(diǎn)。

2.2 用戶移動模塊

用戶移動模塊的主要功能是收集模擬的用戶在移動過程中的相關(guān)信息。實(shí)驗(yàn)中的用戶移動是基于隨機(jī)移動模型，用來研究無模型的遷移策略。

2.3 邊緣云服務(wù)模塊

邊緣云服務(wù)模塊主要功能是如何選擇最優(yōu)服務(wù)遷移方案。該模塊中會給出本研究中遷移成立的約束條件以及優(yōu)化目標(biāo)的評價(jià)標(biāo)準(zhǔn)。關(guān)于服務(wù)節(jié)點(diǎn)內(nèi)存資源的約束條件如式（1）所示：

其中代表的是邊緣云Mi可用的內(nèi)存源；代表Mi在t時(shí)刻可用內(nèi)存資源。

服務(wù)遷移過程中的性能優(yōu)化評價(jià)指標(biāo)是指在一段時(shí)間間隔內(nèi)用戶服務(wù)性能表現(xiàn)，具體如下：

1）時(shí)延

服務(wù)時(shí)延測量標(biāo)準(zhǔn)是與用戶關(guān)聯(lián)的邊緣云服務(wù)節(jié)點(diǎn)和用戶所連接的接入點(diǎn)之間的距離有關(guān)，如式（2）所示，其中λd和λ是實(shí)值的參數(shù)。

2）節(jié)點(diǎn)能耗

能耗指的是鄰域內(nèi)所有邊緣云節(jié)點(diǎn)在t時(shí)的內(nèi)存資源情況。

其中代表的是遷移能耗的最大值1，代表的是遷移能耗的最小值0，Effi(t)代表的是在t時(shí)刻邊緣云的資源利用率。

3）遷移開銷

遷移開銷是由節(jié)點(diǎn)能耗以及通信成本兩方面決定的。

其中式（4）中的為通信成本；代表的是邊緣云服務(wù)狀態(tài)，可劃分為遷移狀態(tài)的服務(wù)(=1) 和非遷移狀態(tài)的服務(wù)(=0) 。(t)表示的是t 時(shí)刻邊緣云Mi位置，1｛·｝表示的是當(dāng)括號內(nèi)的條件成立時(shí)其值為1，否則為0。

定義1：在服務(wù)遷移策略的選擇過程中優(yōu)化目標(biāo)函數(shù)的具體數(shù)學(xué)表現(xiàn)形式如下：

服務(wù)遷移的決策過程中要最小化MinC，其中ω1，ω2相關(guān)的參數(shù)。

在進(jìn)行服務(wù)遷移選擇過程中面臨的服務(wù)時(shí)延、遷移開銷以及兩者之間的折衷優(yōu)化問題會隨著用戶的移動以及邊緣云放置的不確定性而變得復(fù)雜，因此利用深度強(qiáng)化強(qiáng)化學(xué)習(xí)算法進(jìn)行合理的遷移決策成為解決服務(wù)遷移問題的方案之一［10］。

3 解決方案

用戶移動過程中關(guān)于最佳的服務(wù)遷移策略的選擇問題映射到一個(gè)基于深度強(qiáng)化學(xué)習(xí)方法的決策方案中，圖2 描述的就是深度強(qiáng)化學(xué)習(xí)中的遷移決策模型。在解決大規(guī)模的優(yōu)化策略問題中深度Q-Learning 算法與深度神經(jīng)網(wǎng)絡(luò)（DNN）的結(jié)合尤為突出［11］。

圖2 基于深度強(qiáng)化學(xué)習(xí)的服務(wù)遷移模型

3.1 基于NMDQN服務(wù)遷移算法

大規(guī)模移動用戶狀態(tài)信息呈現(xiàn)的算法復(fù)雜性的問題以及遷移決策中出現(xiàn)的算法收斂緩慢的問題［12］，促使了服務(wù)遷移決策不依賴于用戶移動模型的建立。在該遷移方案中，在不需要了解移動過程中用戶確切位置信息情況下，邊緣云節(jié)點(diǎn)（Agent）收集相關(guān)領(lǐng)域內(nèi)的邊緣云節(jié)點(diǎn)狀態(tài)信息以及用戶所連接的基站的狀態(tài)信息（State），并且通過Deep Q-Learning 算法做出相應(yīng)的動作（Action）抉擇，得到如式（8）所示的獎(jiǎng)勵(lì)值（Reward），通過DNN 來協(xié)助邊緣云節(jié)點(diǎn)學(xué)習(xí)有效的經(jīng)驗(yàn)值，反復(fù)進(jìn)行以上的操作，最終得到最優(yōu)的遷移決策［13］。

3.2 算法優(yōu)化設(shè)計(jì)

1）動作選擇的優(yōu)化

在強(qiáng)化學(xué)習(xí)算法中，動作決策中采用的是?-貪婪算法，主要是開發(fā)-探索（exploitation-exploration）的決策方案選擇［14］。由于大規(guī)模的狀態(tài)空間中會出現(xiàn)Q值重現(xiàn)的問題，相應(yīng)地會減緩算法的收斂速度，因此對exploitation 進(jìn)行了優(yōu)化。在exploitation 中以字典的方式將Q值存儲起來，將遷移過程中的狀態(tài)值作為鍵，將該狀態(tài)下動作的選擇以及對應(yīng)得到的獎(jiǎng)勵(lì)作為另一個(gè)參數(shù)來存儲。優(yōu)化后的動作選擇如式（9）所示：

2）神經(jīng)網(wǎng)絡(luò)的優(yōu)化

傳統(tǒng)Q-Learning算法中Q值更新如式（10）：

其中α為學(xué)習(xí)率，γ為折扣因子。

由于用戶移動的高度不確定性以及邊緣云服務(wù)放置的隨機(jī)性，傳統(tǒng)算法中缺乏對經(jīng)驗(yàn)值快速學(xué)習(xí)的能力，造成服務(wù)延遲的現(xiàn)象［15］，因此基于DQN算法可以有效地解決這些問題。在本研究中，服務(wù)遷移策略的選擇是不依賴于用戶移動的，因此采用無模型的DQN（NMDQN）算法可在大規(guī)模狀態(tài)空間中提高決策速率且實(shí)現(xiàn)多個(gè)目標(biāo)的優(yōu)化。

在NMDQN 算法中，Q值為DNN 中有一個(gè)帶有權(quán)重θ的近似值，其目的是在每一次迭代時(shí)通過不斷的更新θi的值來獲得服務(wù)遷移算法中最小的折損函數(shù)值，然后對折損函數(shù)求梯度，并且在此基礎(chǔ)上對回放經(jīng)驗(yàn)的取樣過程通過一個(gè)優(yōu)先級的來決定最終的抽樣經(jīng)驗(yàn)值。關(guān)于折損函數(shù)的描述如式（11）所示。

其中Y（t）的如式（12）所示。

首先對折損函數(shù)進(jìn)行批量梯度下降，然后更新參數(shù)θi，具體的實(shí)現(xiàn)如式（13）、式（14）所示。

在對回放經(jīng)驗(yàn)取樣操作時(shí)，進(jìn)行了一個(gè)優(yōu)先級的處理方法，可以減少服務(wù)遷移過程中無效經(jīng)驗(yàn)的選取使用。將折損函數(shù)與δpr之間取差值之后做了一個(gè)指數(shù)運(yùn)算，得出單個(gè)取樣的優(yōu)先級，最終與所有取樣結(jié)果之和相比，得出優(yōu)先級的大小，從而得到有效的經(jīng)驗(yàn)值，具體如下所示：

算法1是NMDQN的服務(wù)遷移算法。

4 實(shí)驗(yàn)分析

由于在真實(shí)世界的移動邊緣云網(wǎng)絡(luò)架構(gòu)中不易進(jìn)行實(shí)驗(yàn)，因此本文的性能評估是在實(shí)驗(yàn)平臺上模擬的網(wǎng)絡(luò)架構(gòu)中進(jìn)行的。實(shí)驗(yàn)平臺中的網(wǎng)絡(luò)模型是由50 個(gè)節(jié)點(diǎn)構(gòu)成的（30 個(gè)基站和20 個(gè)中間節(jié)點(diǎn)），節(jié)點(diǎn)之間通過最小生成樹連接的，且每個(gè)節(jié)點(diǎn)連接著4 個(gè)最近節(jié)點(diǎn)，邊緣云是被隨機(jī)放置在任意節(jié)點(diǎn)上，如圖3 所示。實(shí)驗(yàn)中相關(guān)的參數(shù)默認(rèn)值如表1 所示。采用線性運(yùn)動模型模擬了16 個(gè)用戶的移動模型，每個(gè)用戶都連接著一個(gè)基站，并與一項(xiàng)服務(wù)相關(guān)聯(lián)。每當(dāng)用戶連接到新的基站時(shí)，相關(guān)服務(wù)的被重新評估，并且遷移方案被觸發(fā)。狀態(tài)-動作值函數(shù)Q（S，A）由3層20個(gè)神經(jīng)元的深度神經(jīng)網(wǎng)絡(luò)逼近。

表1 實(shí)驗(yàn)參數(shù)設(shè)置

圖3 邊緣云網(wǎng)絡(luò)架構(gòu)圖

4.1 基于服務(wù)時(shí)延的評估

通過對服務(wù)時(shí)延的測評可以看出遷移策略對實(shí)時(shí)服務(wù)的響應(yīng)能力。圖4 展示的是在各個(gè)方法下對服務(wù)時(shí)延的評估。本文的提出的NMDQN 算法是有藍(lán)色的線表示的，將本文提出的方法與兩個(gè)基線策略進(jìn)行比較。其中一個(gè)基線策略為紅線表示的局部鄰域最優(yōu)的遷移方法，另外一個(gè)基線策略為黑線表示的基于DQN［10］的遷移方法。可以看出本文提出的NMDQN算法是優(yōu)于DQN算法的，主要?dú)w功于本文提出的算法是基于無模型的，不需要根據(jù)用戶的移動位置信息建立復(fù)雜的成本函數(shù)，在大規(guī)模邊緣云遷移時(shí)減小了算法復(fù)雜度，提高了策略響應(yīng)速度。

4.2 基于時(shí)延與遷移開銷折衷優(yōu)化的評估

本文中還將服務(wù)時(shí)延與遷移開銷的折衷優(yōu)化函數(shù)作為一個(gè)獎(jiǎng)勵(lì)函數(shù)進(jìn)行評估系統(tǒng)性能，以此來驗(yàn)證NMDQN 算法可實(shí)現(xiàn)時(shí)延與開銷之間的折衷優(yōu)化任務(wù)。圖5 展示了一段時(shí)間內(nèi)的平均遷移次數(shù)，可以看出本文的NMDQN 算法明顯較低。圖6展示了一段時(shí)間內(nèi)的平均回報(bào)，且NMDQN 的算法的效果是優(yōu)于DQN 算法的，由此可以看出本文的算法避免了頻繁遷移帶來的遷移開銷以及節(jié)點(diǎn)能耗的問題，提升了用戶整體的服務(wù)質(zhì)量水平。

圖5 平均遷移次數(shù)的評估

圖6 時(shí)延與開銷的評估

5 結(jié)語

本文研究關(guān)于移動邊緣云的服務(wù)遷移問題，由移動邊緣云節(jié)點(diǎn)來決定何時(shí)何地遷移邊緣云服，提出的基于無模型的深度強(qiáng)化學(xué)習(xí)算法無需根據(jù)事先已知的用戶移動模型即可建立通用的系統(tǒng)框架，從而在各種不同的優(yōu)化目標(biāo)需求條件下實(shí)現(xiàn)優(yōu)于基線水平的遷移決策。實(shí)驗(yàn)仿真結(jié)果驗(yàn)證了我們提出的方法。本文中邊緣云遷移過程中考慮到了對每一個(gè)邊緣云的局部領(lǐng)域范圍內(nèi)進(jìn)行策略優(yōu)化，在邊緣云動態(tài)添加時(shí)關(guān)于移動邊緣云的局部鄰域K 的最佳選擇值得考慮的。未來的工作將重點(diǎn)考慮動態(tài)添加邊緣云時(shí)的服務(wù)遷移策略問題。