郭輝，芮蘭蘭，高志鵬

（北京郵電大學(xué)網(wǎng)絡(luò)與交換國家重點(diǎn)實(shí)驗(yàn)室，北京 100876）

1 引言

云計算技術(shù)依靠其具有強(qiáng)大計算和存儲能力的中心服務(wù)器，可以為用戶提供廣泛的服務(wù)及資源，然而，面對目前VR、智能電網(wǎng)、智慧城市等新型技術(shù)[1-4]中萬物互聯(lián)的通信場景及低時延、高質(zhì)量的服務(wù)要求，傳統(tǒng)云計算技術(shù)的部署架構(gòu)及應(yīng)用技術(shù)亟需改善。例如，集中、單一式的云計算資源無法滿足密集型任務(wù)的計算需求，海量數(shù)據(jù)傳送到遠(yuǎn)程云中心進(jìn)行處理的過程極大增加了中心網(wǎng)絡(luò)的負(fù)擔(dān)和任務(wù)時延，隱私保護(hù)、數(shù)據(jù)安全性及能耗方面有待優(yōu)化等。

作為傳統(tǒng)云計算技術(shù)的一種補(bǔ)充與演進(jìn)，邊緣計算（edge computing）[5]技術(shù)將云中心服務(wù)器的遠(yuǎn)程集中式部署方式轉(zhuǎn)化為近端離散化部署，通過在網(wǎng)絡(luò)邊緣部署小型云服務(wù)器，實(shí)現(xiàn)數(shù)據(jù)計算、存儲、識別、分析等能力的下放，在極大減少核心網(wǎng)絡(luò)帶寬和數(shù)據(jù)處理負(fù)荷的同時，也為物聯(lián)網(wǎng)應(yīng)用提供了更好的支持。此外，其對于隱私數(shù)據(jù)的保護(hù)和權(quán)限設(shè)置更加靈活?；诖?，邊緣計算技術(shù)廣受關(guān)注并成為熱點(diǎn)研究領(lǐng)域[6-7]。進(jìn)一步地，隨著移動網(wǎng)絡(luò)的飛速發(fā)展，思科預(yù)測到2021 年全球移動業(yè)務(wù)流量月增長速度將達(dá)到7.2 EB[8]，為滿足高質(zhì)量的移動服務(wù)要求，移動邊緣計算（MEC,mobile edge computing）技術(shù)[9-14]于2013 年被提出并獲得歐洲電信標(biāo)準(zhǔn)協(xié)會（ETSI,European Telecommunications Standards Institute）的認(rèn)可[15]。

在車輛邊緣網(wǎng)絡(luò)（vehicular edge network）中，由于車輛高速移動及邊緣服務(wù)器（ES,edge server）覆蓋范圍有限，移動服務(wù)的連續(xù)性難以得到有效保障[16]，因此，為降低請求時延與服務(wù)中斷頻率、保障服務(wù)連續(xù)性，本文為車輛邊緣網(wǎng)絡(luò)設(shè)計了基于多參數(shù)馬爾可夫決策過程（MDP,Markov decision process）的動態(tài)服務(wù)遷移算法（DSMMP,dynamic service migration algorithm based on multiple parameter）。

本文的創(chuàng)新點(diǎn)如下。

1)改進(jìn)了單純基于跳數(shù)距離進(jìn)行服務(wù)遷移方案的不足，DSMMP 構(gòu)造了基于網(wǎng)絡(luò)性能、服務(wù)器處理能力及車輛運(yùn)動的多參數(shù)MDP 收益函數(shù)。

2)摒除了單一遷移目標(biāo)邊緣服務(wù)器（D-ES,destination ES）的限制，結(jié)合車輛運(yùn)動參數(shù)及請求對應(yīng)的時延限制構(gòu)造候選邊緣服務(wù)器（C-ES,candidate edge server）集合SetC-ES，利用Bellman 方程構(gòu)造長期收益表達(dá)式，根據(jù)長期收益值進(jìn)行遷移決策。

3)彌補(bǔ)了服務(wù)遷移方案動態(tài)適應(yīng)性差的缺點(diǎn)，提出了一種基于歷史數(shù)據(jù)的收益權(quán)重因子計算及網(wǎng)絡(luò)數(shù)據(jù)定期更新方案，提高了DSMMP 算法對動態(tài)網(wǎng)絡(luò)環(huán)境的適應(yīng)能力。

2 相關(guān)工作

Taleb 等[17]在FMC-Follow Me Cloud 架構(gòu)[18]中引入了一維馬爾可夫決策過程模型[19]，為移動用戶尋找最優(yōu)數(shù)據(jù)中心（DC,data center）。該方案基于隨機(jī)移動模型將MDP 狀態(tài)函數(shù)定義為用戶與最優(yōu)DC 之間的跳數(shù)，利用用戶運(yùn)動概率進(jìn)行狀態(tài)聚類，加深了對用戶行為的了解，并提高了預(yù)測準(zhǔn)確度。然而，其計算及設(shè)計嚴(yán)格依賴蜂窩網(wǎng)絡(luò)規(guī)則的部署方式，在移動Wi-Fi 等不規(guī)則信號覆蓋場景中的適用性較差。

有研究者將移動云計算（MCC,mobile cloud computing）場景下的服務(wù)遷移問題[20]建模為一維MDP，并進(jìn)一步在文獻(xiàn)[21]中用“常數(shù)+指數(shù)”的函數(shù)形式具體化MDP 開銷函數(shù)，并利用平衡方程求封閉解，同時改進(jìn)策略迭代方式以獲得更精準(zhǔn)的最優(yōu)策略，該設(shè)計的計算復(fù)雜度過高，而且在進(jìn)行MDP 開銷函數(shù)定義時未考慮環(huán)境動態(tài)性對函數(shù)參數(shù)的影響。

為規(guī)避MDP 遷移方案中的大量復(fù)雜計算和統(tǒng)計過程，IBM 研究人員[22]將Lyapunov 優(yōu)化技術(shù)[23]擴(kuò)展到約束的MDP 中，利用MDP 的解耦特性將約束MDP 問題轉(zhuǎn)化為一個簡單的確定性優(yōu)化問題，從而高效地求解。類似地，其設(shè)計忽略了網(wǎng)絡(luò)參數(shù)的動態(tài)特性，從而影響了遷移方案的動態(tài)適應(yīng)性及可靠性。

美國羅格斯大學(xué)的研究人員結(jié)合服務(wù)響應(yīng)時間參數(shù)和MDP 模型設(shè)計了一種主動式的邊緣云服務(wù)遷移決策系統(tǒng)SEGUE（quality of service aware edge cloud service migration）[24]?；谝环N混合的push/probe 技術(shù)[25]，SEGUE 可以實(shí)現(xiàn)對網(wǎng)絡(luò)中各個服務(wù)器響應(yīng)時間變化的監(jiān)測與收集；使用服務(wù)質(zhì)量（QoS,quality of service）預(yù)測模塊來檢測性能沖突并進(jìn)行遷移決策；利用MDP 的收益函數(shù)測量累計的QoS 提高程度，并選擇一個累計QoS 收益最高的ES 作為目標(biāo)遷移ES。該方案主動監(jiān)測QoS 并進(jìn)行服務(wù)遷移的過程能夠在一定程度上提高服務(wù)的可靠性。然而，其監(jiān)測數(shù)據(jù)的準(zhǔn)確性與及時性缺乏有效保障機(jī)制，響應(yīng)時間完全反映網(wǎng)絡(luò)狀態(tài)的設(shè)計思想也有待驗(yàn)證。

文獻(xiàn)[26]提出了基于多屬性的邊緣計算服務(wù)遷移算法，該算法考慮了每個虛擬機(jī)的能量消耗、遷移開銷、通信開銷、時延以及服務(wù)器計算能力等多個屬性因素對于服務(wù)遷移決策的影響，并建立相應(yīng)的決策矩陣，在用戶離開最優(yōu)服務(wù)器的連接范圍后，通過決策矩陣來決策此時是否需要進(jìn)行服務(wù)遷移。該算法雖然在服務(wù)遷移過程中充分考慮了能量、時延等開銷的影響，但忽略了網(wǎng)絡(luò)環(huán)境的動態(tài)性，缺乏參數(shù)的實(shí)時更新機(jī)制。

已有方案對比如表1 所示。通過以上調(diào)研發(fā)現(xiàn)，大多數(shù)的服務(wù)遷移方案忽略了網(wǎng)絡(luò)及節(jié)點(diǎn)動態(tài)性對遷移決策的影響，同時，動態(tài)決策參數(shù)的實(shí)時更新也是保障遷移算法有效性與可靠性的一個重要因素，如果不能根據(jù)環(huán)境變化對參數(shù)進(jìn)行學(xué)習(xí)更新，往往會因參數(shù)退化而導(dǎo)致算法性能下降。為此，本文提出了車輛邊緣網(wǎng)絡(luò)中基于多參數(shù)MDP 模型的動態(tài)服務(wù)遷移方案DSMMP。

3 DSMMP 算法設(shè)計

3.1 最優(yōu)遷移狀態(tài)閾值存在性證明

為保證DSMMP 算法的科學(xué)性，本節(jié)將利用一個通用的MDP模型來證明MDP服務(wù)遷移方案中最優(yōu)遷移閾值的存在。

本文將時間劃分為一個個相鄰等值的狀態(tài)檢測時隙，在每個狀態(tài)檢測時隙開始時，ES 基于以下MDP 模型進(jìn)行遷移決策。

1)狀態(tài)函數(shù)S(t)

從ES 角度出發(fā)，將S(t)定義為狀態(tài)檢測時隙為t時，ES 與對應(yīng)的車輛節(jié)點(diǎn)之間的鏈路跳數(shù)hop，有

2)動作函數(shù)a(t)

a(t)表示時隙為t時ES 節(jié)點(diǎn)對于某一特定車輛節(jié)點(diǎn)請求服務(wù)的遷移決策，有

(t)表示時隙為t時，ES 從s′遷移到狀態(tài)s的概率。

4)收益函數(shù)

需要說明的是，在本節(jié)中利用時延開銷來定義MDP 收益函數(shù)，則收益函數(shù)值越小對應(yīng)的策略越優(yōu)。DSMMP 綜合網(wǎng)絡(luò)性能、ES 處理能力、節(jié)點(diǎn)運(yùn)動的收益來定義MDP 收益函數(shù)，取收益函數(shù)值最大時的策略為最優(yōu)策略。雖然二者的定義不同，但其實(shí)質(zhì)意義相同，因此2 種定義方式具有一致性，并不沖突。

對服務(wù)不遷移和遷移這2 種決策分別產(chǎn)生的網(wǎng)絡(luò)時延開銷進(jìn)行如下分析。

①不進(jìn)行服務(wù)遷移。如圖1 所示，初始t時刻車輛V1處于節(jié)點(diǎn)ES2的覆蓋范圍內(nèi)，則S(t)=0，此時V1向ES2發(fā)送了一個分組請求，設(shè)請求時延為treq；然后ES2開始對該請求進(jìn)行服務(wù)計算，計算時延為tcom；在服務(wù)計算完成之前的每個狀態(tài)檢測時隙中，ES2均采取不遷移的動作，當(dāng)計算完成后ES2準(zhǔn)備向V1回復(fù)數(shù)據(jù)，卻發(fā)現(xiàn)V1節(jié)點(diǎn)已經(jīng)離開其信號覆蓋范圍并其處于ES1的覆蓋范圍，則ES2將結(jié)果數(shù)據(jù)返回給ES1，此過程的時延為ES 之間的傳輸時延tdata-trans；最后由節(jié)點(diǎn)ES1將請求應(yīng)答數(shù)據(jù)回復(fù)給V1，此時的時延為車輛和ES 之間的傳輸時延trep。

則不遷移策略的總時延開銷為

② 進(jìn)行服務(wù)遷移。如圖2 所示，t時刻車輛V1處于ES2的覆蓋范圍內(nèi)，則S(t)=0，V1此時向ES2發(fā)送了一個分組請求，請求時延為treq；在計算服務(wù)完成之前的某一個狀態(tài)檢測時隙t'',ES2發(fā)現(xiàn)車輛V1節(jié)點(diǎn)離開其信號覆蓋范圍，進(jìn)入ES1的覆蓋范圍，當(dāng)S(t′′)＞k（k為最優(yōu)閾值）時，ES2選擇進(jìn)行服務(wù)遷移，將其與V1之間的會話過程、請求內(nèi)容等具體信息打包發(fā)送給ES1，該過程的時延為tsession-trans；此后，ES1開始對車輛V1的請求進(jìn)行服務(wù)計算，計算時延為tcom；計算完成后，ES1再將結(jié)果數(shù)據(jù)回復(fù)給車輛V1，產(chǎn)生傳輸時延trep（此時也可能出現(xiàn)V1離開了ES1的范圍，但此處僅為證明閾值存在，故不考慮這種復(fù)雜情況）。

表1 已有方案對比

圖1 服務(wù)不遷移場景

圖2 服務(wù)遷移場景

則遷移策略的總時延開銷為

對比上述2 種情況可以發(fā)現(xiàn)，tnon-mig和tmig中存在部分相同參數(shù)，為簡化計算過程，去掉了重復(fù)的時延部分，并將MDP 中的收益函數(shù)定義為時間開銷，因此，狀態(tài)s下發(fā)生動作a的開銷函數(shù)為

5）折合系數(shù)γ

γ表示上述MDP 模型的當(dāng)前收益與未來收益之間的差異，本文取γ=0.9。

需要注意的是，雖然任務(wù)類型、網(wǎng)絡(luò)及節(jié)點(diǎn)狀態(tài)的差異會影響最優(yōu)閾值的具體值，但并不影響各個ES 最優(yōu)閾值的存在性，因此，本節(jié)不針對某一具體狀態(tài)下的收益函數(shù)進(jìn)行詳細(xì)計算。同時，定義狀態(tài)值上限值為N，當(dāng)s＞N時，無條件進(jìn)行服務(wù)遷移。

基于上述，提出以下命題，并給出相應(yīng)證明。

命題1在一個一維的移動邊緣網(wǎng)絡(luò)中，存在一個ES 與移動用戶之間的最優(yōu)狀態(tài)閾值k＜N，當(dāng)狀態(tài)s＜k時，最優(yōu)策略為不進(jìn)行服務(wù)遷移；當(dāng)s≥k時，最優(yōu)策略為進(jìn)行服務(wù)遷移。

證明

1)當(dāng)狀態(tài)值s=0 時，車輛節(jié)點(diǎn)與ES 直接相連，采取任何動作決策收益函數(shù)值均為0，即Ca(0)=0，此時取a*(0)=0。

2)假設(shè)在狀態(tài)s=k時，對應(yīng)的最優(yōu)策略為遷移服務(wù)，則此時的動作價值函數(shù)滿足

式(6)中等號右側(cè)表示一個從未進(jìn)行服務(wù)遷移的折合總開銷值。

3)假設(shè)在狀態(tài)k+1≤s′≤N采取不遷移動作，則每個時隙會產(chǎn)生一個時延tdata-trans，直到某個時隙tm到達(dá)遷移狀態(tài)S(tm)，則對于從s′開始的任何遷移路徑L有

其中，tm為s′之后需要進(jìn)行服務(wù)遷移的時隙值。則有

3.2 模型設(shè)計

3.2.1 系統(tǒng)模型

1)網(wǎng)絡(luò)模型

基于運(yùn)營商基站和交通部門RSU（road side unit）部署方案[27-28]，DSMMP 為每個基站和樁節(jié)點(diǎn)連接一個小型的ES，每個基站和樁節(jié)點(diǎn)的信號覆蓋范圍即為對應(yīng)ES 的服務(wù)覆蓋范圍。如圖3 所示，網(wǎng)絡(luò)分為兩級，主要包含3 種類型的節(jié)點(diǎn)：車輛、ES 以及一個后端云服務(wù)器（BCS,back-end cloud server）。其中，ES 和BCS 為靜態(tài)節(jié)點(diǎn)，BCS 位于車輛和ES 的上層并擁有所有服務(wù)請求所需的計算資源，某個ES 中只擁有部分請求的計算資源。同時，ES 之間以及ES 與BCS 之間通過一個靜態(tài)的回程網(wǎng)絡(luò)互連，ES 與車輛之間通過無線網(wǎng)絡(luò)連接。

圖3 網(wǎng)絡(luò)模型

2)服務(wù)請求模型

車輛節(jié)點(diǎn)將其服務(wù)請求發(fā)送給直接相連的ES，DSMMP 為每個車輛設(shè)置了一個請求表（如表2 所示）來記錄每個請求的標(biāo)識Rlabel、生存時間約束timer 以及接收該請求的ES 標(biāo)識ESlabel（服務(wù)遷移后，ESlabel更新）。timer 代表每個請求對于時延的限制，當(dāng)timer 未超時且收到回復(fù)時，車輛節(jié)點(diǎn)刪除該請求表項(xiàng)；當(dāng)timer 未超時且未收到回復(fù)時，車輛節(jié)點(diǎn)會一直保持該請求表項(xiàng)；當(dāng)timer 超時仍未收到回復(fù)時，車輛會認(rèn)為該請求暫時不能被滿足，并刪除該請求對應(yīng)的表項(xiàng)。

3)服務(wù)應(yīng)答模型

ES 收到一個請求后會立即查詢本地是否緩存了相應(yīng)的計算資源，若有則直接進(jìn)行服務(wù)計算；否則，需要向BCS 進(jìn)行資源請求再進(jìn)行服務(wù)計算。每個ES 會維持一個服務(wù)表來記錄向其發(fā)出請求的車輛標(biāo)識Vlabel、對應(yīng)的請求標(biāo)識Rlabel以及其與該車輛的跳數(shù)距離hop（通過回程網(wǎng)絡(luò)時刻跟蹤該車輛節(jié)點(diǎn)獲得，并在每個狀態(tài)檢測時隙進(jìn)行更新）。當(dāng)某個車輛的請求被滿足或進(jìn)行了服務(wù)遷移后，其對應(yīng)的表項(xiàng)將刪除。需要注意的是，一個車輛可能會向同一個ES 發(fā)送不同請求，如表3 所示，V2在不同時刻分別向同一個ES 發(fā)送了Request4、Request3和Request7。

表2 請求表

表3 服務(wù)表

3.2.2 MDP 模型

DSMMP 將時間劃分為一個個相等的狀態(tài)檢測時隙t，一個時隙作為一個采樣區(qū)間，在每個時隙開始時進(jìn)行ES 狀態(tài)檢測并做出服務(wù)遷移決策。

1)狀態(tài)函數(shù)S(t)

S(t)表示在狀態(tài)檢測時隙t時，某個ES 與向其進(jìn)行請求的車輛V之間的跳數(shù)距離（表3 中的hop表項(xiàng)值），有

2)動作函數(shù)a(t)

a(t)表示在狀態(tài)檢測時隙t時，ES 節(jié)點(diǎn)對于車輛請求的服務(wù)采取的遷移決策，有

(t)表示在狀態(tài)檢測時隙t時，一個ES 從狀態(tài)s′遷移到狀態(tài)s的概率。由于受道路拓?fù)湎拗?，能以較高的準(zhǔn)確度預(yù)測獲得車輛的下一個檢測時隙的狀態(tài)值，因此設(shè)(t)為0.85。此處，(t)＜1 是由車輛邊緣環(huán)境中的一些不確定因素導(dǎo)致的。

4)收益函數(shù)R(s,a)

R(s,a)表示ES 在狀態(tài)s下對車輛的請求采取動作a的收益值，在決策服務(wù)遷移時，ES 需要分別對a=0 和a=1 這2 種情景進(jìn)行收益函數(shù)值計算及比較。當(dāng)a=1 時，DSMMP 并不會只選擇一個目標(biāo)ES計算R(s,1)，而是基于車輛運(yùn)動及請求時延限制選擇多個候選C-ES 構(gòu)成集合SetC-ES，然后分別計算其對應(yīng)的收益函數(shù)，最后將最大值Rmax(s,1)設(shè)置為R(s,1)；當(dāng)a=0 時，DSMMP 利用原O-ES 對應(yīng)的參數(shù)計算R(s,0)。

DSMMP 算法在定義R(s,a)時綜合考慮了時延、帶寬、服務(wù)器處理能力以及車輛運(yùn)動參數(shù)的影響作用。設(shè)某個ES 在狀態(tài)s下采取動作a時，有C-ESm∈SetC-ES（當(dāng)a=0 時，C-ESm=O-ES），以C-ESm為例將各部分收益計算定義如下。

1)時延收益

(s,a)表示在狀態(tài)s下采取動作a后，對應(yīng)于C-ESm的時延收益值。

2)帶寬收益

(s,a)表示在狀態(tài)s下采取動作a后對應(yīng)于C-ESm的帶寬收益值。

3)邊緣服務(wù)器處理能力

(s,a)表示狀態(tài)s下采取動作a后獲得的C-ESm處理能力大小。DSMMP 從存儲和計算能力兩方面定義(s,a)，考慮到不同任務(wù)類型（如計算密集型業(yè)務(wù)、資源密集型業(yè)務(wù)等）對于服務(wù)器存儲和計算能力的要求各不相同，本文不涉及對具體業(yè)務(wù)類型的考慮，故各自取其權(quán)重為0.5。

4)運(yùn)動收益

①構(gòu)造SetC-ES

不進(jìn)行服務(wù)遷移時，候選服務(wù)器唯一且為O-ES。如圖4 所示，在某個狀態(tài)檢測時隙開始時，ES1上運(yùn)行著某車輛的服務(wù)計算并檢測到該車輛以速度v從Ps點(diǎn)離開其服務(wù)范圍，此時ES1若決定進(jìn)行服務(wù)遷移，DSMMP 將進(jìn)行如下操作構(gòu)造集合SetC-ES。首先，查詢車輛服務(wù)請求表中對應(yīng)請求的timer 值，根據(jù)車速v計算distmax=vtimer；然后，根據(jù)車輛運(yùn)動方向及distmax預(yù)測請求超時時車輛節(jié)點(diǎn)的位置Pe；最后連接點(diǎn)Ps及Pe，選擇線段PsPe穿過區(qū)域?qū)?yīng)的 ES 構(gòu)建集合 SetC-ES，圖 4 中SetC-ES={C-ES2,C-ES6,C-ES7}。

圖4 C-ES 選擇示意

(s,a)表示狀態(tài)s下采取動作a后對應(yīng)于C-ESm的運(yùn)動收益值。結(jié)合車輛運(yùn)動參數(shù)及網(wǎng)絡(luò)拓?fù)?，DSMMP 將根據(jù)車輛節(jié)點(diǎn)在C-ES 服務(wù)范圍的逗留時間定義其運(yùn)動收益。

需要說明的是，若車輛離開O-ES 的服務(wù)范圍且該O-ES 選擇不進(jìn)行服務(wù)遷移，DSMMP 設(shè)置此時的(s,0)=0，因?yàn)檐囕v短時間內(nèi)再運(yùn)動回O-ES 服務(wù)范圍的概率極小。下面以C-ESm為例，分別針對不同Pe位置對進(jìn)行服務(wù)遷移時的(s,1)進(jìn)行討論。

①當(dāng)Pe不在C-ESm的服務(wù)范圍內(nèi)時（圖4 中的C-ES2和C-ES6），如圖5 所示，記車輛與C-ESm服務(wù)范圍邊界的交點(diǎn)為Pm，θm表示車輛運(yùn)動方向與線段PmC-ESm的夾角，C-ESm的服務(wù)覆蓋半徑為R，則車輛在 C-ESm服務(wù)范圍內(nèi)的逗留距離為

圖5 運(yùn)動收益計算示意（Pe不在C-ESm的服務(wù)范圍）

② 當(dāng)Pe在C-ESm的服務(wù)范圍內(nèi)時（圖4 中的C-ES7），如圖6 所示，有

圖6 運(yùn)動收益計算示意（Pe在C-ESm的服務(wù)范圍）

最終，有

其中，αm、βm、δm、εm分別為C-ESm各個參量對應(yīng)的權(quán)重因子。對于每個權(quán)重因子的具體取值將在3.4.1 節(jié)中給出。

5)折合因子γ

γ表示當(dāng)前總收益與未來總收益之間的差異。

3.3 遷移決策

3.3.1 Bellman 方程計算累計收益

基于3.2.2 節(jié)中定義的MDP 模型，DSMMP 將服務(wù)遷移的期望總收益定義為

其中，π描述為狀態(tài)s時采取動作a的策略，將式(19)用遞歸形式表示為

其中，s′表示狀態(tài)s的前一個狀態(tài)檢測時隙對應(yīng)的狀態(tài)值，p(s',s)表示從狀態(tài)s′轉(zhuǎn)移到狀態(tài)s的概率，Vπ(s')表示狀態(tài)為s′時獲得的累計收益值。

DSMMP 的最終目標(biāo)是在狀態(tài)s根據(jù)策略π采取一個動作a，以實(shí)現(xiàn)Vπ(s)的最大化，即

3.3.2 求解遷移狀態(tài)閾值

DSMMP 利用收益函數(shù)值迭代的方法對3.3.1 節(jié)中的Bellman 方程進(jìn)行求解，從而保證在某一個具體狀態(tài)下為ES 提供合理的服務(wù)遷移決策。工作流程如圖7 所示，具體求解過程如下。

圖7 工作流程

1)初始化。狀態(tài)檢測時隙t時車輛Vi位于ESj的服務(wù)范圍內(nèi)，狀態(tài)值s′=0，threshold 表示進(jìn)行服務(wù)遷移的最小狀態(tài)閾值，初始時有threshold=N，N為車輛與邊緣服務(wù)器之間的最大狀態(tài)值，根據(jù)ESj的信息計算R(s′,0)=V*(s′)。

2)在接下來的每個新的狀態(tài)檢測時隙開始時，檢測ESj與Vi之間的狀態(tài)值s，若s=0，不進(jìn)行服務(wù)遷移。

3)若s＞0，根據(jù)ESj與Vi對應(yīng)的參數(shù)計算a=0時的R(s,0)，并獲得Va=0(s)。

4)當(dāng)a=1 時，計算distmax，獲得候選ES 集合SetC-ES，分別針對SetC-ES中的每個C-ES 計算其遷移收益值，并選擇收益最大的C-ES 作為D-ES，其對應(yīng)的收益值為Rmax(s,1)，計算Va=1(s)。

5)比較Va=0(s)和Va=1(s)的值，選擇長期收益最好做出遷移決策：當(dāng)Va=0(s)＞Va=1(s)時，不進(jìn)行服務(wù)遷移，將s賦值給s′，V*(s′)=Va=0(s)，下一個時隙繼續(xù)檢測重復(fù)上述操作；當(dāng)Va=0(s)＜Va=1(s)時，ESj將Vi的服務(wù)請求遷移到D-ES 上，將s賦值給threshold。

6)結(jié)束。

算法1求解遷移決策

輸入Vi，ESj，timeslot=t，最大狀態(tài)值N，遷移狀態(tài)閾值threshold=N，R(s′,0)=V*(s′)

3.4 權(quán)重因子計算及數(shù)據(jù)更新

3.4.1 權(quán)重因子計算

DSMMP 設(shè)置每個ES 對應(yīng)的權(quán)重因子各不相同，相同ES 在為不同車輛的服務(wù)進(jìn)行遷移決策時所使用的權(quán)重因子相同。為適應(yīng)車輛邊緣網(wǎng)絡(luò)環(huán)境的動態(tài)特征，DSMMP 采用基于ES 歷史數(shù)據(jù)并定期更新的權(quán)重因子計算方式。

以ESm為例，在初始時隙，設(shè)置權(quán)重的更新周期為，并取αm=βm=δm=εm=0.25，ESm基于歷史數(shù)據(jù)，建立矩陣Am進(jìn)行權(quán)重計算，如表4 所示。

表4 歷史數(shù)據(jù)矩陣Am

表4 中，X1、X2、X3分別代表ESm在此次更新之前最近獲得的3 組數(shù)據(jù)編號，Ai1、Ai2、Ai3、Ai4分別代表在第i組數(shù)據(jù)中的時延收益值、帶寬收益值、服務(wù)器服務(wù)能力以及運(yùn)動收益值，取

構(gòu)造一個新的矩陣Bm，其矩陣元素為Bij，如式(23)所示。

在信息論中，熵不僅是不確定性的度量，同時也可以用來表示數(shù)據(jù)中包含的信息量，將矩陣Bm進(jìn)行歸一化處理得到矩陣Cm，其矩陣元素為Cij，如式(24)所示。

j指標(biāo)的熵為

j指標(biāo)的差系數(shù)為

則j指標(biāo)的權(quán)重為

從而可以得到αm=w1，βm=w2，δm=w3，εm=w4。

3.4.2 數(shù)據(jù)更新

1)權(quán)重因子更新

權(quán)重因子會隨著網(wǎng)絡(luò)參數(shù)的變化而變化，因此本文對其采取定期更新方式。以ESm為例，設(shè)置更新周期為。初始設(shè)置2=t，其中t為一個狀態(tài)檢測時隙的時間長度。DSMMP 算法運(yùn)行一段時間之后，若算法 1 獲得了 threshold，則取，否則2=t。

在車輛節(jié)點(diǎn)和ESm之間的服務(wù)請求與應(yīng)答完成后，其對應(yīng)的參數(shù)就會失效，若二者未來再次連接，則在啟動DSMMP 算法時重新計算上述參數(shù)。

4 仿真與性能分析

4.1 仿真設(shè)置

4.1.1 參數(shù)設(shè)置

基于ORBIT[29]（open access research testbed for next-generation wireless network）平臺和CRAWDAD社區(qū)對某地區(qū)出租車進(jìn)行GPS 跟蹤得到的運(yùn)動軌跡數(shù)據(jù)集[30]，本文對城市車輛邊緣網(wǎng)絡(luò)中的動態(tài)服務(wù)遷移過程進(jìn)行了真實(shí)模擬。

根據(jù)圖3 中描述的網(wǎng)絡(luò)模型及移動運(yùn)營商對于基站的鋪設(shè)和區(qū)域覆蓋范圍的設(shè)置，取每個ES 的覆蓋半徑為2 100 m，相鄰ES 的重疊區(qū)域?yàn)?04 m，表5 具體展示了仿真實(shí)驗(yàn)中其他參數(shù)的詳細(xì)設(shè)置。

表5 參數(shù)設(shè)置

4.1.2 對比方案

DSMMP 策略的仿真過程有以下3 種對比方案。

1)不遷移策略，即服務(wù)一直在O-ES 上運(yùn)行。

2)一直遷移策略，即車輛離開O-ES 覆蓋范圍后就會進(jìn)行服務(wù)遷移且D-ES 為與車輛節(jié)直接連接的ES。

3)SEGUE 策略，根據(jù)檢測到的QoS 沖突決定是否遷移，利用累計收益計算獲得最優(yōu)D-ES。

4.1.3 對比指標(biāo)

1)服務(wù)響應(yīng)過程。描述了在每個策略指導(dǎo)下的具體請求服務(wù)響應(yīng)時間變化過程，該指標(biāo)可以清晰地展示出每個策略的工作方式及各個策略之間直觀的性能對比。

2)平均時延。時延是衡量網(wǎng)絡(luò)性能的一個代表性參數(shù)，通過對比不同策略指導(dǎo)下的服務(wù)平均時延，可以清晰地看出各個策略的優(yōu)劣。

3)分組丟失率。利用數(shù)據(jù)請求失敗率來反映每個策略的工作效率。

4)服務(wù)遷移次數(shù)。結(jié)合時延數(shù)據(jù)，服務(wù)遷移次數(shù)結(jié)果可以清晰地描述出每個策略對于環(huán)境動態(tài)變化的適應(yīng)能力。

4.2 仿真結(jié)果分析

4.2.1 服務(wù)響應(yīng)過程

以100 次服務(wù)請求作為一個采樣區(qū)間，圖8～圖11分別描述了數(shù)據(jù)分組大小為1 MB、4 MB、16 MB及64 MB 時，每個策略對應(yīng)的服務(wù)響應(yīng)過程。

圖8 數(shù)據(jù)分組為1 MB 時的服務(wù)響應(yīng)過程

圖9 數(shù)據(jù)分組為4 MB 時的服務(wù)響應(yīng)過程

首先，對于存在服務(wù)遷移過程的3 種策略，服務(wù)響應(yīng)曲線的每個波峰都代表著一次服務(wù)遷移，從服務(wù)遷移頻率的角度來說，一直遷移策略、SEGUE策略及DSMMP 策略依次遞減。一方面，與一直遷移策略相比，SEGUE 策略和DSMMP 策略的遷移決策是分別根據(jù)QoS 沖突檢測和累計收益值來決定，而不是僅僅基于車輛節(jié)點(diǎn)與ES 的位置，因此遷移次數(shù)均明顯小于一直遷移策略。另一方面，DSMMP 策略在收益函數(shù)中加入了對車輛運(yùn)動參數(shù)的考慮及多個C-ES 的選擇，因此，其服務(wù)遷移位置會更加符合車輛的運(yùn)動軌跡，有利于實(shí)現(xiàn)利用最小遷移次數(shù)最快響應(yīng)請求的目的。

圖10 數(shù)據(jù)分組為16 MB 時的服務(wù)響應(yīng)過程

圖11 數(shù)據(jù)分組為64 MB 時的服務(wù)響應(yīng)過程

其次，對于不遷移策略，其服務(wù)響應(yīng)曲線并不會出現(xiàn)大幅度的波峰形狀，而那些小的曲線波谷則是由于請求本地滿足或車輛位置靠近ES 引起的響應(yīng)時間降低。

最后，綜合比較圖8～圖11 可以發(fā)現(xiàn)，隨著數(shù)據(jù)分組的增大，各個策略的響應(yīng)時間均出現(xiàn)增長，但4 種策略的工作模式并未改變，DSMMP 策略表現(xiàn)最優(yōu)。

4.2.2 平均時延

以100 s 作為一個采樣區(qū)間，圖12～圖15 分別記錄了數(shù)據(jù)分組大小為1 MB、4 MB、16 MB 及64 MB時對應(yīng)的任務(wù)平均時延變化結(jié)果。

從圖12～圖15 中可以看出，一直遷移策略的任務(wù)平均時延要明顯大于其他3 種策略。通過分析，認(rèn)為原因如下：由于車輛節(jié)點(diǎn)一直運(yùn)動，因此會一直發(fā)生頻繁的ES 切換和服務(wù)遷移過程，使網(wǎng)絡(luò)中請求分組和回復(fù)分組的數(shù)據(jù)流量增大，甚至出現(xiàn)網(wǎng)絡(luò)擁塞情況，并最終增大任務(wù)的傳輸時延；而不遷移策略不會存在上述問題，SEGUE 策略和DSMMP策略根據(jù)各自的設(shè)計進(jìn)行遷移也不會對網(wǎng)絡(luò)流量造成嚴(yán)重影響。

圖12 數(shù)據(jù)分組為1 MB 時的平均時延

圖13 數(shù)據(jù)分組為4 MB 時的平均時延

圖14 數(shù)據(jù)分組為16 MB 時的平均時延

DSMMP 策略的平均時延明顯優(yōu)于SEGUE 策略的結(jié)果，因?yàn)橄啾扔赟EGUE 策略，DSMMP 策略在收益函數(shù)中加入了對網(wǎng)絡(luò)參數(shù)、ES 服務(wù)能力及車輛節(jié)點(diǎn)運(yùn)動參數(shù)的綜合考慮，在進(jìn)行服務(wù)遷移時，其遷移決策對動態(tài)車輛邊緣網(wǎng)絡(luò)環(huán)境具有更好的適應(yīng)能力，因此能夠更好地實(shí)現(xiàn)邊緣請求的快速處理。

圖15 數(shù)據(jù)分組為64 MB 時的平均時延

同時，可以發(fā)現(xiàn)4 條曲線均呈現(xiàn)出起點(diǎn)很高，然后急劇下降，最后趨于平緩的變化過程。因?yàn)槌醮握埱髸r，ES 本地?zé)o資源緩存，需要向BCS 進(jìn)行資源請求后再進(jìn)行服務(wù)計算，ES 在回復(fù)給請求節(jié)點(diǎn)的同時會進(jìn)行內(nèi)容的本地緩存，當(dāng)出現(xiàn)需要相同資源的請求時，可以在本地直接進(jìn)行請求計算，大大降低了服務(wù)時延。

4.2.3 分組丟失率

在進(jìn)行分組丟失率計算過程中，共進(jìn)行了235次仿真實(shí)驗(yàn)，每次持續(xù)100 s，然后綜合所有的仿真數(shù)據(jù)得到圖16，其分別記錄了數(shù)據(jù)分組大小為1 MB、2 MB、4 MB、8 MB、16 MB 以及64 MB 情況下各個策略的分組丟失率。

圖16 分組丟失率比較

首先，可以看出一直遷移策略的分組丟失率最高。因?yàn)槠湟攒囕v節(jié)點(diǎn)離開O-ES 服務(wù)覆蓋范圍作為遷移觸發(fā)條件，當(dāng)一個請求未得到滿足并且車輛發(fā)生移動時，該服務(wù)會被遷移到新的ES 上重新進(jìn)行服務(wù)計算。這種方式雖然簡單，但增大了服務(wù)中斷的頻率并且很容易造成一個請求及其對應(yīng)回復(fù)的大量重復(fù)，從而造成網(wǎng)絡(luò)流量的急劇增大，甚至引發(fā)網(wǎng)絡(luò)擁塞，引起丟失分組，增大了數(shù)據(jù)傳輸失敗的概率。

其次，不遷移策略的分組丟失率高于SEGUE策略及DSMMP 策略。因?yàn)樵摬呗圆扇〉牟贿w移方式雖然不會造成嚴(yán)重的網(wǎng)絡(luò)流量增長，但隨著車輛節(jié)點(diǎn)與O-ES 之間距離越來越遠(yuǎn)，很容易出現(xiàn)由于傳輸時延過大而造成數(shù)據(jù)傳輸超時的情況，進(jìn)而造成分組丟失。從本質(zhì)上來說，SEGUE 策略和DSMMP 策略是一直遷移策略與不遷移策略的一種折中方式，這2 種策略既不會隨著車輛的運(yùn)動一直遷移，也不會不遷移，因此，不會出現(xiàn)網(wǎng)絡(luò)流量急劇上升及大范圍數(shù)據(jù)分組超時的情況。

進(jìn)一步地，在遷移決策方面，SEGUE 策略基于QoS 沖突進(jìn)行遷移決策，其僅僅考慮了ES 的QoS；DSMMP 基于一個綜合性的動態(tài)累計收益函數(shù)值來決策，并利用車輛運(yùn)動參數(shù)在多個C-ES 中擇優(yōu)選擇，因此，DSMMP 比SEGUE 能夠更加適應(yīng)網(wǎng)絡(luò)的動態(tài)變化，性能更優(yōu)，分組丟失數(shù)更少。

最后，從總體上來看，可以發(fā)現(xiàn)隨著數(shù)據(jù)分組的增大，分組丟失率逐漸增大：一方面，由于數(shù)據(jù)分組增大，網(wǎng)絡(luò)流量勢必增大，網(wǎng)絡(luò)傳輸將會受到一定影響，嚴(yán)重時引起分組丟失；另一方面，數(shù)據(jù)分組增大，當(dāng)ES 不能本地滿足要向BCS 進(jìn)行數(shù)據(jù)請求時（如圖3 所示），其下載時延及傳輸時延也會相應(yīng)增大，嚴(yán)重時會造成數(shù)據(jù)超時。

4.2.4 服務(wù)遷移次數(shù)

圖17 展示了對235 次100 s 的仿真數(shù)據(jù)計算平均服務(wù)遷移次數(shù)的結(jié)果。DSMMP 策略的服務(wù)遷移次數(shù)最低，其次為SEGUE 策略，最大為一直遷移策略。

圖17 服務(wù)遷移次數(shù)比較

首先，SEGUE 策略基于QoS 沖突檢測以及DSMMP 策略利用累計收益決策遷移的方式，使二者的服務(wù)遷移次數(shù)小于一直遷移策略；其次，SEGUE 策略與DSMMP 策略相比，DSMMP 策略充分考慮了節(jié)點(diǎn)運(yùn)動參數(shù)及時延限制，因此其遷移位置會更加符合車輛的運(yùn)動軌跡，對于動態(tài)環(huán)境的適應(yīng)性更強(qiáng)；最后，可以看出數(shù)據(jù)分組的大小對于各個策略的平均遷移次數(shù)影響并不大，其原因是3 種策略的遷移決策中并沒有考慮數(shù)據(jù)分組大小的影響作用，因此數(shù)據(jù)分組大小變化只會對時延造成影響，對于策略的工作過程影響不大。

之所以對服務(wù)遷移次數(shù)進(jìn)行統(tǒng)計及比較，是因?yàn)槊看蔚姆?wù)遷移過程都對應(yīng)著不可忽視的遷移開銷，頻繁的服務(wù)遷移會對網(wǎng)絡(luò)造成大量的網(wǎng)絡(luò)負(fù)擔(dān)，結(jié)合時延及分組丟失率結(jié)果，可以發(fā)現(xiàn)DSMMP能夠在最小遷移次數(shù)前提下，實(shí)現(xiàn)更小的時延和分組丟失率，與其他策略相比，性能最優(yōu)。

5 結(jié)束語

為解決車輛邊緣網(wǎng)絡(luò)中車輛高速移動造成的大量連接切換及服務(wù)中斷問題，本文提出了基于多參數(shù)MDP 模型的動態(tài)服務(wù)遷移算法DSMMP。DSMMP結(jié)合網(wǎng)絡(luò)帶寬、時延、ES 處理能力及車輛運(yùn)動4 種參數(shù)構(gòu)造了動態(tài)適應(yīng)性更強(qiáng)的MDP 收益函數(shù)，利用Bellman 方程獲得累計收益，并求解收益最大的遷移狀態(tài)閾值，另外，DSMMP 還設(shè)計了基于歷史數(shù)據(jù)的權(quán)重因子計算及數(shù)據(jù)更新方案。仿真表明，該算法擁有更高的動態(tài)環(huán)境適應(yīng)性與可靠性，能在遷移次數(shù)最低的情況下達(dá)到時延及分組丟失率最優(yōu)。

在未來工作中，將進(jìn)一步對DSMMP 算法進(jìn)行改進(jìn)和完善。一方面，在遷移決策中加入對更多因素的考慮，如能耗、通信開銷、遷移代價等；另一方面，進(jìn)一步提高算法的可擴(kuò)展性及其對動態(tài)環(huán)境適用性，如考慮將該算法應(yīng)用于更為普遍的MANET 環(huán)境中。