基于概率性能感知演化博弈策略的“云+邊”混合環(huán)境中任務(wù)卸載方法

雷 鷹 ，鄭萬(wàn)波，魏嵬，夏云霓，李曉波，劉誠(chéng)武，謝洪

（1.重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044；2.昆明理工大學(xué)理學(xué)院，昆明 650500；3.西安理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，西安 710048；4.重慶市畜牧技術(shù)推廣總站，重慶 401121；5.上海交通大學(xué)重慶研究院，重慶 401135）

0 引言

隨著互聯(lián)網(wǎng)的普及和物聯(lián)網(wǎng)的高速發(fā)展，越來(lái)越多的移動(dòng)終端被廣泛運(yùn)用于人們的日常生活中，預(yù)計(jì)到2030 年，全球移動(dòng)終端數(shù)接近180 億［1］。移動(dòng)設(shè)備使用量的爆發(fā)式增長(zhǎng)趨勢(shì)是由移動(dòng)用戶的增加和移動(dòng)應(yīng)用程序開發(fā)（例如iPhone應(yīng)用程序和谷歌應(yīng)用程序）共同作用的結(jié)果。與此同時(shí)，諸如交互式游戲［2］、增強(qiáng)現(xiàn)實(shí)、虛擬現(xiàn)實(shí)等新興應(yīng)用也隨著5G 技術(shù)的發(fā)展而廣泛普及。這些需要大量計(jì)算和能量消耗的應(yīng)用要想純粹依賴移動(dòng)設(shè)備本身去處理并不現(xiàn)實(shí)，有限的計(jì)算能力、通信傳輸能力、電池壽命制約著移動(dòng)設(shè)備上新興應(yīng)用的發(fā)展；所以將任務(wù)卸載到外部的計(jì)算節(jié)點(diǎn)，由其提供更為豐富的計(jì)算資源，將是解決移動(dòng)設(shè)備資源限制的一種行之有效的方法。

移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）［3］相較于云計(jì)算，是將原先本應(yīng)在網(wǎng)絡(luò)中心節(jié)點(diǎn)進(jìn)行的各種計(jì)算遷移到網(wǎng)絡(luò)的邊緣，靠近用戶側(cè)提供服務(wù)。通過(guò)提供最近端服務(wù)，使得應(yīng)用程序在邊緣側(cè)發(fā)起時(shí)，能夠最大限度減少不必要的數(shù)據(jù)搬運(yùn)，減少由此帶來(lái)的延遲和能耗，加快網(wǎng)絡(luò)響應(yīng)，降低對(duì)中心節(jié)點(diǎn)的壓力；同樣也能滿足行業(yè)在實(shí)時(shí)、安全、隱私保護(hù)、智能應(yīng)用等方面的基本需求。在MEC 平臺(tái)中，邊緣網(wǎng)絡(luò)部署著豐富的小型服務(wù)器，為就近的用戶提供豐富的計(jì)算能力和資源；只需要將計(jì)算密集型任務(wù)卸載到邊緣云上，在他們的移動(dòng)終端上即可享受流暢的應(yīng)用服務(wù)。為滿足動(dòng)態(tài)增加的服務(wù)需求，目前常用的是多邊緣節(jié)點(diǎn)與中心節(jié)點(diǎn)協(xié)同為多用戶提供的服務(wù)，用戶任務(wù)允許被卸載到不同的目標(biāo)處理位置，包括附近的MEC 節(jié)點(diǎn)或中心云上的節(jié)點(diǎn)。當(dāng)任務(wù)被卸載到不同的目標(biāo)處理位置時(shí)，可能會(huì)產(chǎn)生不同的使用成本。因此，在最大限度地降低資源采購(gòu)成本方面，應(yīng)綜合地考慮備選邊緣節(jié)點(diǎn)的性能與定價(jià)策略。在純粹的邊緣計(jì)算環(huán)境中，邊緣節(jié)點(diǎn)本身的任務(wù)處理性能和通信能力往往體現(xiàn)出隨時(shí)間波動(dòng)的動(dòng)態(tài)特性。

針對(duì)上述“云+邊”混合環(huán)境中的多用戶任務(wù)卸載場(chǎng)景，本文提出了一種基于概率性能感知的演化博弈論動(dòng)態(tài)卸載策略。之所以使用演化博弈來(lái)解決該問(wèn)題，是由于傳統(tǒng)博弈論追求的是納什均衡（Nash Equilibrium，NE），需要單個(gè)用戶在完全理性的情況下最大化自身收益，從而達(dá)到每一個(gè)參與者都能接受的平衡狀態(tài)。而在“云+邊”混合環(huán)境中，地理位置分布的多用戶不具備完全透明的信息和全局的邏輯推演能力，因此并不能達(dá)到完全理性。在這種不完全理性狀態(tài)下，本文考慮追求種群的最大適應(yīng)度，進(jìn)而取得演化穩(wěn)定策略（Evolutionary Stability Strategy，ESS）。該策略不會(huì)因?yàn)槟骋粋€(gè)參與人的決策改變而導(dǎo)致整體再計(jì)算，從而節(jié)省了大量的決策計(jì)算開銷。同時(shí)，本文考慮到真實(shí)環(huán)境中的邊緣云服務(wù)器的運(yùn)行是隨時(shí)間動(dòng)態(tài)變化的，是非穩(wěn)定性的。基于真實(shí)的公開的邊緣云服務(wù)器的性能數(shù)據(jù)集和位置分布數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)性案例研究，實(shí)驗(yàn)結(jié)果表明，本文所提出的方法在平均用戶期望達(dá)成度、平均卸載時(shí)延、平均貨幣成本指標(biāo)上優(yōu)于傳統(tǒng)的貪婪（Greedy）算法、遺傳算法（Genetic Algorithm，GA）和基于納什均衡的博弈論（Nash-based Game）算法。

1 相關(guān)工作

作為移動(dòng)邊緣計(jì)算（MEC）的一個(gè)重要主題，移動(dòng)任務(wù)卸載近年來(lái)被廣泛研究。部分研究將MEC 環(huán)境中任務(wù)卸載問(wèn)題作為一種混合整數(shù)規(guī)劃（Mixed Integer Programming，MIP），利用最優(yōu)化方法進(jìn)行求解。文獻(xiàn)［4］通過(guò)將MIP 問(wèn)題分解為多個(gè)凸優(yōu)化問(wèn)題并基于Lagrange 乘子的算法來(lái)進(jìn)行求解，但是該方法主要考慮靜態(tài)性能參數(shù)，無(wú)法確保時(shí)變波動(dòng)性能條件下的卸載性能。文獻(xiàn)［5］則基于邏輯的字節(jié)分解的求解方法，減小了海量任務(wù)卸載請(qǐng)求所帶來(lái)的搜索空間，但是該方法主要針對(duì)中心化的任務(wù)調(diào)度場(chǎng)景，無(wú)法有效地解決分布條件下的云邊混合環(huán)境下的任務(wù)卸載。文獻(xiàn)［6］考慮將MEC 環(huán)境下任務(wù)執(zhí)行次序作為求解目標(biāo)，提出了一種基于分支定界的算法進(jìn)行求解，在保證卸載時(shí)的服務(wù)質(zhì)量的同時(shí)提高了服務(wù)器的收益。此外，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，啟發(fā)式算法也被大量采用。文獻(xiàn)［7］提出了一種基于粒子群優(yōu)化（Partical Swarm Optimization，PSO）的計(jì)算卸載策略以解決工業(yè)生產(chǎn)線中的多用戶多MEC 時(shí)延優(yōu)化問(wèn)題。文獻(xiàn)［8］提出了一個(gè)分割時(shí)間槽的資源分配算法（Slotted Time Resource Allocation algorithm，STRA）并結(jié)合遺傳算法進(jìn)行最優(yōu)卸載策略的搜索，能夠明顯提高邊緣節(jié)點(diǎn)的利用率，減緩核心網(wǎng)絡(luò)壓力。文獻(xiàn)［9］提出了一種基于元啟發(fā)式的雙目標(biāo)優(yōu)化調(diào)度算法，考慮最大限度地縮短最大完成時(shí)間并最小化成本。該算法是流行的元啟發(fā)式-引力搜索算法（Gravitational Search Algorithm，GSA）與流行的啟發(fā)式-異構(gòu)完成時(shí)間（Heterogeneous Earliest Finish Time，HEFT）算法的混合體，并通過(guò)引入一個(gè)稱為成本-時(shí)間等效的因子將雙目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為一個(gè)帶約束條件的單目標(biāo)優(yōu)化問(wèn)題來(lái)求解。而文獻(xiàn)［10］提出了一種多目標(biāo)細(xì)菌覓食優(yōu)化算法（Multi-Objective Bacterial Foraging Optimization Algorithm，MOBFOA），通過(guò)應(yīng)用帕累托最優(yōu)前沿技術(shù)對(duì)原始的細(xì)菌覓食優(yōu)化算法（Bacterial Foraging Optimization Algorithm，BFOA）進(jìn)行改進(jìn)以處理多目標(biāo)優(yōu)化調(diào)度問(wèn)題，其改進(jìn)主要是從占優(yōu)和非占優(yōu)前沿中選擇細(xì)菌的位置以獲得解的多樣性。隨著機(jī)器學(xué)習(xí)的發(fā)展，文獻(xiàn)［11］提出了一種分布式深度神經(jīng)網(wǎng)絡(luò)（Deep Neural Network，DNN）模型，使用半定松弛的二次約束線性規(guī)劃對(duì)DNN 模型進(jìn)行訓(xùn)練，得到最優(yōu)卸載策略。文獻(xiàn)［12］考慮了優(yōu)勢(shì)系統(tǒng)模型中的多任務(wù)多服務(wù)卸載場(chǎng)景，并提出了一種基于深度強(qiáng)化學(xué)習(xí)的在線卸載決策方法。文獻(xiàn)［13］將能量消耗和延遲作為卸載目標(biāo)，文獻(xiàn)［14］以最小化時(shí)延和成本作為求解目標(biāo)，提出了一種分布式博弈理論方法來(lái)進(jìn)行卸載策略的選擇。文獻(xiàn)［15］提出了基于博弈論方法的在線卸載算法，能實(shí)現(xiàn)在一臺(tái)邊緣服務(wù)器與多個(gè)用戶的網(wǎng)絡(luò)場(chǎng)景中開展在線自組織的任務(wù)分配和卸載，并通過(guò)博弈算法求解納什均衡來(lái)指導(dǎo)用戶選擇合適的網(wǎng)絡(luò)信道進(jìn)行卸載。文獻(xiàn)［16］將進(jìn)化博弈運(yùn)用于邊緣節(jié)點(diǎn)卸載問(wèn)題中，討論用戶在非理性的情況下達(dá)到ESS，但是它主要考慮純邊緣計(jì)算的環(huán)境，而非本文研究的“云+邊”混合環(huán)境。

以上研究，均將邊緣服務(wù)器的性能視為一個(gè)恒定的常量輸入決策或優(yōu)化模型，以獲得任務(wù)調(diào)度和卸載的決策方案。然而，真實(shí)環(huán)境下的邊緣服務(wù)器或邊緣計(jì)算節(jié)點(diǎn)的性能，因?yàn)橥ㄐ艂鬏敗⒛茉垂┙o、任務(wù)負(fù)載等不確定因素的影響，往往體現(xiàn)出隨時(shí)間變化和波動(dòng)的特點(diǎn)。采用恒定或靜態(tài)的性能參數(shù)或測(cè)試值作為調(diào)度算法的輸入，將導(dǎo)致算法生成的調(diào)度策略難以在性能波動(dòng)的系統(tǒng)中取得穩(wěn)定的調(diào)度效果。針對(duì)上述問(wèn)題，本文通過(guò)歷史經(jīng)驗(yàn)概率分布函數(shù)來(lái)描述性能的波動(dòng)變化，并將用戶的收益進(jìn)行概率化計(jì)算處理。

2 系統(tǒng)和計(jì)算模型

2.1 系統(tǒng)模型

本文假設(shè)云服務(wù)器和邊緣服務(wù)器都有各自的覆蓋范圍，覆蓋范圍內(nèi)的終端用戶可以通過(guò)無(wú)線訪問(wèn)連接到它［17］。邊緣服務(wù)器分布式地部署到蜂窩基站附近從而為用戶就近提供服務(wù)。同時(shí)考慮一個(gè)由單個(gè)宏基站和K個(gè)微基站組成的異構(gòu)網(wǎng)絡(luò)來(lái)承載邊緣計(jì)算環(huán)境。為了保證某一地理區(qū)域中的N個(gè)用戶都能獲得中心云服務(wù)，中心云服務(wù)器部署在宏基站上。中心云服務(wù)器可以以一個(gè)較大的覆蓋范圍為終端用戶提供服務(wù)。而K個(gè)微基站上則分別部署K個(gè)邊緣服務(wù)器，在更靠近終端用戶的位置上為他們提供邊緣云服務(wù)。邊緣服務(wù)器的計(jì)算能力、存儲(chǔ)資源以及覆蓋范圍都要比中心云服務(wù)器小，為用戶提供的計(jì)算處理性能也更低，但是價(jià)格卻較低。根據(jù)文獻(xiàn)［16］的分析，上述云邊混合環(huán)境的區(qū)域，通?？杀粍澐譃镴個(gè)小服務(wù)區(qū)域，每個(gè)區(qū)域內(nèi)的用戶被視為一個(gè)群體，劃分的原則是確保每個(gè)區(qū)域的邊緣服務(wù)器數(shù)量幾乎相等，同時(shí)每個(gè)區(qū)域內(nèi)用戶的數(shù)量不超過(guò)邊緣服務(wù)器數(shù)量的10 倍。每個(gè)區(qū)域的用戶所構(gòu)成的種群，在有限理性假設(shè)下，以固定的比例采取相同的博弈策略。

圖1 給出了一個(gè)代表性的例子，闡述上述混合環(huán)境。在本例中，存在一個(gè)集中式的中心化云服務(wù)器（CS0）、6個(gè)邊緣服務(wù)器（CS1～CS6）和9 個(gè)用戶（U0～U8）。不同邊緣服務(wù)器的覆蓋區(qū)域可能重疊，因此用戶可以選擇多個(gè)候選服務(wù)器進(jìn)行任務(wù)卸載。例如，可以將U1的任務(wù)分配卸載給CS0、CS1或CS2，然而U6只能將任務(wù)卸載到CS0上進(jìn)行處理。將區(qū)域劃分為三個(gè)大小相同的區(qū)域（R0～R2），每個(gè)區(qū)域都部署兩臺(tái)邊緣服務(wù)器。

圖1 云邊混合環(huán)境Fig.1 Hybrid cloud-edge environment

本文使用的變量信息如表1所示。

表1 參數(shù)具體信息Tab.1 Specific information of parameters

2.2 計(jì)算模型

對(duì)于用戶Ui而言，首先要確定其與各服務(wù)器之間的距離。若滿足dist(i，k)

其中，ηi，k=(i，k)是與距離有關(guān)的參數(shù)，用戶與服務(wù)器之間距離越遠(yuǎn)，誤碼率越高，平均傳輸速度就會(huì)越低，wk和fk分別表示CSk的平均帶寬和平均計(jì)算能力。fk可根據(jù)其對(duì)應(yīng)的歷史經(jīng)驗(yàn)分布［19］計(jì)算，計(jì)算式如下：

根據(jù)式（3），用戶的貨幣成本包括三部分，即通信成本、計(jì)算成本和租用服務(wù)器的費(fèi)用。Ct，k和Cf，k分別表示CSk單位傳輸速率的價(jià)格和單位計(jì)算資源的費(fèi)用。Vrent，k與服務(wù)器的當(dāng)前負(fù)載有關(guān)。如果服務(wù)器的使用效率更高，并且為更多的用戶提供服務(wù)，則每個(gè)用戶分?jǐn)偟淖饨鹁驮降?，因此用戶Ui的卸載成本為：

本文使用USi來(lái)表示Ui的用戶期望達(dá)成度，它可以表示為卸載時(shí)間和貨幣成本約束都得到滿足的概率：

代表區(qū)域內(nèi)Pj的期望達(dá)成度，其中numj表示Pj中的用戶數(shù)量：

US是整個(gè)區(qū)域的期望達(dá)成度，并將其作為最終優(yōu)化目標(biāo)：

3 演化博弈

演化博弈相較于經(jīng)典博弈論，區(qū)別在于其側(cè)重于對(duì)博弈主體的動(dòng)態(tài)均衡［20］的研究，而不同于經(jīng)典博弈論所研究的靜態(tài)均衡。動(dòng)態(tài)均衡是在參與人以不完全信息為條件、有限理性為前提下研究的一種動(dòng)態(tài)分析過(guò)程。所謂有限理性，即指參與人具有一定的統(tǒng)計(jì)分析能力，能夠在一定的限度下判斷不同策略組合下的開銷和收益程度，而有異于完全理性所具備的完全的信息搜索能力、邏輯計(jì)算能力和對(duì)未來(lái)的預(yù)測(cè)能力。演化博弈論正是將傳統(tǒng)博弈論和動(dòng)態(tài)演化過(guò)程結(jié)合在一起進(jìn)行分析的一種理論，用以分析參與人在有限理性下，對(duì)資源配置行為及博弈策略的選擇。演化博弈的研究對(duì)象是群體，基本思想為：賦予群體一個(gè)最開始的形態(tài)，然后在時(shí)間演化過(guò)程中，群體中的參與者自由地去選擇更優(yōu)的策略。

由于每個(gè)邊緣服務(wù)器的計(jì)算資源和帶寬資源的限制，不同區(qū)域的終端用戶不得不競(jìng)爭(zhēng)中心云服務(wù)器的資源。這種多分布資源節(jié)點(diǎn)、多用戶競(jìng)爭(zhēng)的場(chǎng)景，與演化博弈所研究的理論模型高度契合。

3.1 博弈標(biāo)準(zhǔn)式

經(jīng)典博弈標(biāo)準(zhǔn)式包括三個(gè)因素：博弈的參與者、每個(gè)參與者可供選擇的策略集合和針對(duì)所有參與者可能選擇的策略組合，以及每個(gè)參與者在選擇策略時(shí)的收益函數(shù)。在演化博弈的背景下，群體可被用來(lái)代表一組具有相同的性質(zhì)的參與者［21］。

將演化博弈的形式設(shè)計(jì)如下：

1）參與者。對(duì)于圖1所示的“云+邊”混合多用戶環(huán)境，區(qū)域內(nèi)的每個(gè)終端用戶都是演化博弈中的參與者。在有限理性的假設(shè)下，參與博弈的目的是通過(guò)參與博弈實(shí)現(xiàn)自身效益最大化。

2）群體。如圖1所示，參與者們按照位置可劃分為J個(gè)不同的群體，每個(gè)群體中的用戶數(shù)量用numj表示。用{P0，P1，…，PJ-1}來(lái)表示J個(gè)群體的參與者集合，每個(gè)群體中的參與者都位于同一地理區(qū)域并滿足所有群體的用戶數(shù)之和為總用戶數(shù)。

3）策略。每個(gè)參與者的策略是指它所能選擇的服務(wù)器，在該博弈環(huán)境中共有1+K種服務(wù)器可供參與者選擇，使用xk來(lái)表示用戶是否選擇服務(wù)器CSk進(jìn)行任務(wù)卸載的實(shí)際情況：

6）收益。參與者的收益取決于其凈效用函數(shù)（4），由其最大可容忍時(shí)延和成本以及實(shí)際產(chǎn)生的時(shí)延和成本決定。則Pj群體的用戶Uj選擇CSk服務(wù)器上所獲得的收益可以表示為：

3.2 演化穩(wěn)定策略

在傳統(tǒng)博弈中，所有參與人都可以達(dá)到一個(gè)穩(wěn)定狀態(tài)，即沒(méi)有參與人可以通過(guò)單方面改變策略來(lái)進(jìn)一步獲得額外的利益，這種狀態(tài)稱為NE。將混合構(gòu)架下服務(wù)器的選擇及資源分配看作一個(gè)博弈Γ，參與者集合為N，策略集合為S=[s1，s2，…，sN]表示對(duì)每個(gè)參與者的策略進(jìn)行了統(tǒng)計(jì)。用S-i=[S1，…，Si，Si+1，…，SN]表示除開參與人Ui以外其他人所選擇的策略組合。在收益集合Π=[π1，π2，…，πN]中，參與人Ui的收益與自己選擇策略和他人選擇策略有關(guān)，表示為π(si，s-i)。

定義1一個(gè)博弈Γ=〈N，S，Π〉的納什均衡解S*=

納什均衡具有一種自我強(qiáng)化的特性，即每個(gè)參與者都沒(méi)有動(dòng)機(jī)偏離這個(gè)均衡。獲得納什均衡的一般解是基于所有參與者完全理性的假設(shè)。然而，在一個(gè)小擾動(dòng)下，所有參與者都可能改變策略，以達(dá)到另一個(gè)納什均衡。在進(jìn)化博弈論［21］中，保持有限理性的參與人所達(dá)到的一種穩(wěn)定狀態(tài)可以抵抗小干擾，這種均衡稱作EE（Evolutionary Equilibrium），達(dá)到該均衡的策略為ESS。

與納什均衡相比，定義2的條件1）保證了EE 是納什均衡（NE）。定義2 的條件2）保證了博弈過(guò)程的穩(wěn)定性。在策略演進(jìn)過(guò)程中，使用變異策略的玩家將減少，直到群體中的所有參與者漸近接近EE。在本文的問(wèn)題中，云邊混合構(gòu)架下的終端用戶在一組有限的策略中調(diào)整他們的策略以獲得更好的回報(bào)。在每一時(shí)刻，終端用戶都可以獲得自己的策略集，同時(shí)獲得所在群體的平均收益信息，從而隨著時(shí)間的推移，不斷地演進(jìn)自己的服務(wù)器選擇策略。經(jīng)過(guò)足夠多的重復(fù)和推演，使用其他策略的突變參與者會(huì)因?yàn)槭找孑^低而數(shù)量不斷減少，最后突變玩家滅絕，達(dá)到群體的演化穩(wěn)定狀態(tài)。這個(gè)動(dòng)態(tài)的過(guò)程可以通過(guò)復(fù)制動(dòng)態(tài)方程進(jìn)行求解。下一節(jié)將對(duì)此進(jìn)行詳細(xì)描述。

3.3 復(fù)制者動(dòng)態(tài)方程

演化博弈模型主要是基于突變機(jī)制和選擇機(jī)制建立起來(lái)的模型，突變指的是在一個(gè)群體中，小部分參與者以隨機(jī)的方式選擇不同于大部分參與者的策略，選擇的策略可能獲得較高的收益，也可能獲得較低的收益，但是只有優(yōu)秀的策略才不會(huì)被歷史淘汰，而被保留下來(lái)。選擇則是指該策略能夠獲得更高的收益，能在以后不斷地被其他參與者采用。這種選擇機(jī)制正是復(fù)制者動(dòng)態(tài)模型的關(guān)鍵，它提供了一種獲取他人群體信息的方法，并向均衡點(diǎn)收斂，直到策略適應(yīng)以達(dá)到演化均衡（EE），即群體不會(huì)改變其選擇。其基本思想是在有限理性的博弈者群體中，結(jié)果優(yōu)于平均水平的策略將逐漸被更多的博弈者所采用，博弈者策略的比例也隨之發(fā)生變化。具體如下：

其中δ用來(lái)控制同一群體中參與者策略適應(yīng)的收斂速度。增長(zhǎng)率(t)表示對(duì)時(shí)間進(jìn)行一階求導(dǎo)得到的函數(shù)，(t)是群體中的參與者選擇服務(wù)器CSk時(shí)所獲得的當(dāng)前收益，(t)為t時(shí)刻群體的平均收益，可以通過(guò)式（10）計(jì)算得到：

基于在群體Pj中策略選擇的復(fù)制者動(dòng)態(tài)方程，當(dāng)選擇策略s的收益高于同一群體的平均收益時(shí)，選擇該終端用戶的數(shù)量在總體上將呈正增長(zhǎng)趨勢(shì)。通過(guò)設(shè)置=0，可以得到復(fù)制者動(dòng)態(tài)的不動(dòng)點(diǎn)，在該不動(dòng)點(diǎn)上，由于同一群體中的所有參與者都有相同的收益，因此群體狀態(tài)不會(huì)改變，也沒(méi)有參與人愿意改變策略。

基于復(fù)制者動(dòng)態(tài)的算法描述如算法1所示。

4 實(shí)驗(yàn)和結(jié)果分析

4.1 數(shù)據(jù)集

為了驗(yàn)證本文所提出方法的正確性和有效性，基于EUA（Edge User Allocation）數(shù)據(jù)集［22］提供的邊緣服務(wù)器與用戶的位置和針對(duì)邊緣服務(wù)器性能的數(shù)據(jù)集［23］進(jìn)行了模擬實(shí)驗(yàn)。圖2 顯示該區(qū)域包含200 個(gè)終端用戶、1 個(gè)中心云服務(wù)器和12個(gè)邊緣云服務(wù)器。邊緣云的服務(wù)半徑在100～300 m，中心云服務(wù)器的覆蓋范圍設(shè)定為800 m。服務(wù)器的覆蓋范圍使用圓圈表明。根據(jù)地理位置信息，將該區(qū)域劃分成4 個(gè)小區(qū)域，每個(gè)小區(qū)域中的用戶被看作一個(gè)群體，分屬于不同群體的用戶用不同圖形進(jìn)行標(biāo)注。

圖2 實(shí)驗(yàn)數(shù)據(jù)的地理分布情況Fig.2 Geographical distribution of experimental data

對(duì)于中心云服務(wù)器的性能數(shù)據(jù)，測(cè)試了一個(gè)典型的第三方商用云服務(wù)，即騰訊云。圖3～4 顯示了中心云服務(wù)器的吞吐量和計(jì)算性能（以每秒百萬(wàn)條指令（Million Instructions Per Second，MIPS）為單位），另外12 組邊緣云服務(wù)器的性能統(tǒng)計(jì)圖與之類似，這些數(shù)據(jù)被劃分為24 個(gè)連續(xù)的時(shí)間窗口，每個(gè)窗口記錄相鄰10 次記錄，以便于在不同的時(shí)間階段測(cè)試和比較不同策略的性能。

圖3 處于不同時(shí)間窗口的中心云服務(wù)器的吞吐量Fig.3 Throughput for central cloud server at different time windows

4.2 對(duì)比方法

將本文提出的方法與以下三種經(jīng)典方法進(jìn)行了比較。

1）貪心（Greedy）算法［24］。在求解問(wèn)題時(shí)只考慮當(dāng)前最優(yōu)的結(jié)果，而不從整體去考慮，忽略整體策略的改變對(duì)當(dāng)前局部策略的影響。

2）遺傳算法（GA）［25］。該算法模擬生物自然選擇和基因遺傳，通過(guò)對(duì)策略集合進(jìn)行多代的選擇、交叉和變異過(guò)程，不斷向最優(yōu)解靠攏。

3）基于納什均衡的博弈論（Nash-based Game）算法［15］。假設(shè)每個(gè)參與人都是完全理性的，為使個(gè)體收益最大，博弈最后會(huì)趨向一個(gè)均衡點(diǎn)，使所有參與人都不會(huì)優(yōu)先改變策略。

圖4 處于不同時(shí)間窗口的中心云服務(wù)器的計(jì)算性能Fig.4 Computational performance for central cloud server at different time windows

4.3 對(duì)比結(jié)果分析

通過(guò)對(duì)24個(gè)窗口信息求離散概率分布，每個(gè)窗口進(jìn)行50次實(shí)驗(yàn)求平均值，將參數(shù)設(shè)置為ξ=0.1、λ=2、δ=0.4、ε=0.05，可得到圖5 的結(jié)果。通過(guò)分析，得出以下幾個(gè)結(jié)論：1）在所有24 個(gè)時(shí)間窗口中，本文方法的總用戶期望達(dá)成度和卸載時(shí)延都優(yōu)于其他算法，總用戶期望達(dá)成度為171.6，平均用戶期望達(dá)成度為85.8%；2）本文的方法和基于納什的博弈算法在貨幣成本方面明顯優(yōu)于其他方法，平均貨幣成本為Greedy 算法的11.3%，且比GA 更穩(wěn)定；3）本文的方法在所有窗口下都比其他算法具有更少的迭代次數(shù)，均能在10 次迭代內(nèi)達(dá)到穩(wěn)定狀態(tài)。

綜合考慮卸載時(shí)延和貨幣成本得到的用戶總體期望達(dá)成度，本文提出的方法在多次實(shí)驗(yàn)后，在每一個(gè)窗口都表現(xiàn)比較好，但是將其分為兩個(gè)單獨(dú)的指標(biāo)，其他方法也會(huì)得到更好的結(jié)果。

圖5（b）中，Greedy 算法得到的貨幣成本在多個(gè)窗口下表現(xiàn)略微優(yōu)于本文提出的方法，但在多個(gè)窗口（w=2，12，15，17，18），該指標(biāo)又表現(xiàn)極端糟糕，總體表現(xiàn)沒(méi)有兩種博弈論方法穩(wěn)定。

圖5（c）中，Greedy 算法和Nash-based Game 算法在多個(gè)窗口（w=12，19）上的卸載時(shí)延都略低于本文的方法，表現(xiàn)更優(yōu)，但本文的方法在更多窗口表現(xiàn)出相較于這兩種算法的顯著優(yōu)勢(shì)，且整體表現(xiàn)更加穩(wěn)定。同時(shí)可見(jiàn)，該方法通過(guò)群體的動(dòng)態(tài)迭代和學(xué)習(xí)，表現(xiàn)出更好的環(huán)境適應(yīng)性。

具體來(lái)看，對(duì)24 個(gè)窗口求平均值可得到的平均性能指標(biāo)如表2所示。

表2 不同方法在不同衡量指標(biāo)下的平均值對(duì)比Tab.2 Comparison of average values of different methods under different measurement indexes

其中，本文提出的方法在平均用戶期望達(dá)成度方面相較于Greedy、GA 和Nash-based Game 方法分別提升了13.7%、117.0%、13.8%，平均卸載時(shí)延分別降低了6.5%、24.9%、8.3%，平均貨幣成本分別降低了67.9%、88.7%、18.0%。

圖5 是在得到最優(yōu)卸載策略后用戶執(zhí)行卸載時(shí)所產(chǎn)生的成本和時(shí)延開銷。若將服務(wù)器計(jì)算推演算法的用時(shí)考慮進(jìn)去，如圖5（d）所示，本文的方法表現(xiàn)出最低且最穩(wěn)定的迭代次數(shù)，一定程度上加快了服務(wù)器對(duì)用戶的響應(yīng)，提高了用戶的滿意度。

圖5 不同時(shí)間窗口下不同衡量指標(biāo)的比較Fig.5 Comparison of different measurement indexes at different time windows

4.4 引入突變后的結(jié)果分析

由于GA 在復(fù)雜環(huán)境中在多個(gè)指標(biāo)上都表現(xiàn)出局部最優(yōu)，不能在合理時(shí)間內(nèi)得到最優(yōu)解，而Greedy 算法又表現(xiàn)出極不穩(wěn)定性，故本節(jié)將著重研究?jī)煞N博弈論算法，即基于納什均衡的博弈論算法和本文所提出的演化博弈論算法，主要研究在用戶突變后的響應(yīng)。

通過(guò)實(shí)驗(yàn)比較了兩種博弈論算法對(duì)變異后種群的收斂性。首先，群體均達(dá)到了穩(wěn)定狀態(tài)1（NE1或EE1）。經(jīng)過(guò)五次迭代，群體中的少數(shù)用戶將隨機(jī)變異，表現(xiàn)為用戶任務(wù)的大小發(fā)生變化，可容忍的延遲和成本也會(huì)發(fā)生變化。突變后，群體通過(guò)重新調(diào)整卸載策略以達(dá)到穩(wěn)定狀態(tài)2（NE2 或EE2）。本文將在某一博弈論策略下，突變后重新達(dá)到新的穩(wěn)定狀態(tài)（NE或EE）的迭代次數(shù)作為群體收斂性的度量。

如圖6 所示，使用傳統(tǒng)博弈論算法，參與者在變異后需要經(jīng)過(guò)10 次迭代才能達(dá)到新的穩(wěn)定狀態(tài)，而演化博弈算法（本文方法）在圖7 中只需要一次迭代就可以達(dá)到新的穩(wěn)定狀態(tài)。實(shí)驗(yàn)結(jié)果表明，本文方法在抗干擾能力方面優(yōu)于傳統(tǒng)方法。

圖6 基于納什均衡的博弈論的收斂性Fig.6 Convergence of Nash-based Game

圖7 基于演化博弈的收斂性Fig.7 Convergence of evolutionary Game

5 結(jié)語(yǔ)

本文研究了具有非穩(wěn)定性能的“云+邊”混合環(huán)境中的任務(wù)卸載問(wèn)題，提出了一個(gè)基于歷史性能數(shù)據(jù)概率分析與演化博弈的多用戶卸載方法。為了驗(yàn)證所設(shè)計(jì)方法的正確性和有效性，基于一個(gè)公開的云/邊緣資源位置數(shù)據(jù)集設(shè)計(jì)模擬實(shí)驗(yàn)，將本文的方法與傳統(tǒng)的Greedy、GA 和Nash-based Game 方法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，本文所提出的方法在平均用戶期望達(dá)成度、平均卸載時(shí)延、平均貨幣成本指標(biāo)上優(yōu)于對(duì)比方法。

在今后的擴(kuò)展研究中，將進(jìn)一步開展以下工作：1）考慮用戶和邊緣節(jié)點(diǎn)的移動(dòng)性，研究在非規(guī)則移動(dòng)軌跡下多用戶的任務(wù)在線卸載的策略；2）引入基于時(shí)間序列和神經(jīng)網(wǎng)絡(luò)的性能預(yù)測(cè)模型，并用軌跡預(yù)測(cè)信息和性能預(yù)測(cè)信息，驅(qū)動(dòng)多用戶任務(wù)卸載決策的模型；3）考慮在非可信通信條件下，任務(wù)失效和傳輸故障對(duì)任務(wù)卸載的影響，設(shè)計(jì)故障容忍和容錯(cuò)的多用戶任務(wù)卸載的策略和算法。