車輛邊緣網(wǎng)絡(luò)中基于多參數(shù)MDP 模型的動(dòng)態(tài)服務(wù)遷移策略

郭輝，芮蘭蘭，高志鵬

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

1 引言

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

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

在車輛邊緣網(wǎng)絡(luò)（vehicular edge network）中，由于車輛高速移動(dòng)及邊緣服務(wù)器（ES,edge server）覆蓋范圍有限，移動(dòng)服務(wù)的連續(xù)性難以得到有效保障[16]，因此，為降低請(qǐng)求時(shí)延與服務(wù)中斷頻率、保障服務(wù)連續(xù)性，本文為車輛邊緣網(wǎng)絡(luò)設(shè)計(jì)了基于多參數(shù)馬爾可夫決策過程（MDP,Markov decision process）的動(dòng)態(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)動(dòng)的多參數(shù)MDP 收益函數(shù)。

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

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

2 相關(guān)工作

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

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

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

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

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

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

3 DSMMP 算法設(shè)計(jì)

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

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

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

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

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

2)動(dòng)作函數(shù)a(t)

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

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

4)收益函數(shù)

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

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

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

則不遷移策略的總時(shí)延開銷為

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

表1 已有方案對(duì)比

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

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

則遷移策略的總時(shí)延開銷為

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

5）折合系數(shù)γ

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

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

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

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

證明

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

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

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

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

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

3.2 模型設(shè)計(jì)

3.2.1 系統(tǒng)模型

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

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

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

2)服務(wù)請(qǐng)求模型

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

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

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

表2 請(qǐng)求表

表3 服務(wù)表

3.2.2 MDP 模型

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

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

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

2)動(dòng)作函數(shù)a(t)

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

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

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

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

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

1)時(shí)延收益

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

2)帶寬收益

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

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

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

4)運(yùn)動(dòng)收益

①構(gòu)造SetC-ES

不進(jìn)行服務(wù)遷移時(shí)，候選服務(wù)器唯一且為O-ES。如圖4 所示，在某個(gè)狀態(tài)檢測(cè)時(shí)隙開始時(shí)，ES1上運(yùn)行著某車輛的服務(wù)計(jì)算并檢測(cè)到該車輛以速度v從Ps點(diǎn)離開其服務(wù)范圍，此時(shí)ES1若決定進(jìn)行服務(wù)遷移，DSMMP 將進(jìn)行如下操作構(gòu)造集合SetC-ES。首先，查詢車輛服務(wù)請(qǐng)求表中對(duì)應(yīng)請(qǐng)求的timer 值，根據(jù)車速v計(jì)算distmax=vtimer；然后，根據(jù)車輛運(yùn)動(dòng)方向及distmax預(yù)測(cè)請(qǐng)求超時(shí)時(shí)車輛節(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下采取動(dòng)作a后對(duì)應(yīng)于C-ESm的運(yùn)動(dòng)收益值。結(jié)合車輛運(yùn)動(dòng)參數(shù)及網(wǎng)絡(luò)拓?fù)?，DSMMP 將根據(jù)車輛節(jié)點(diǎn)在C-ES 服務(wù)范圍的逗留時(shí)間定義其運(yùn)動(dòng)收益。

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

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

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

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

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

最終，有

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

5)折合因子γ

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

3.3 遷移決策

3.3.1 Bellman 方程計(jì)算累計(jì)收益

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

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

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

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

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

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

圖7 工作流程

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

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

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

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

5)比較Va=0(s)和Va=1(s)的值，選擇長期收益最好做出遷移決策：當(dāng)Va=0(s)＞Va=1(s)時(shí)，不進(jìn)行服務(wù)遷移，將s賦值給s′，V*(s′)=Va=0(s)，下一個(gè)時(shí)隙繼續(xù)檢測(cè)重復(fù)上述操作；當(dāng)Va=0(s)＜Va=1(s)時(shí)，ESj將Vi的服務(wù)請(qǐng)求遷移到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)重因子計(jì)算及數(shù)據(jù)更新

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

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

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

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

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

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

在信息論中，熵不僅是不確定性的度量，同時(shí)也可以用來表示數(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)重因子會(huì)隨著網(wǎng)絡(luò)參數(shù)的變化而變化，因此本文對(duì)其采取定期更新方式。以ESm為例，設(shè)置更新周期為。初始設(shè)置2=t，其中t為一個(gè)狀態(tài)檢測(cè)時(shí)隙的時(shí)間長度。DSMMP 算法運(yùn)行一段時(shí)間之后，若算法 1 獲得了 threshold，則取，否則2=t。

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

4 仿真與性能分析

4.1 仿真設(shè)置

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

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

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

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

4.1.2 對(duì)比方案

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

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

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

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

4.1.3 對(duì)比指標(biāo)

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

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

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

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

4.2 仿真結(jié)果分析

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

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

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

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

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

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

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

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

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

4.2.2 平均時(shí)延

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

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

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

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

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

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

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

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

4.2.3 分組丟失率

在進(jìn)行分組丟失率計(jì)算過程中，共進(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 情況下各個(gè)策略的分組丟失率。

圖16 分組丟失率比較

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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