雷 鷹 ，鄭萬波，魏嵬，夏云霓，李曉波，劉誠武，謝洪

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

0 引言

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

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

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

1 相關(guān)工作

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

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

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

2.1 系統(tǒng)模型

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

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

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

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

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

2.2 計算模型

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

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

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

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

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

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

3 演化博弈

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗和結(jié)果分析

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

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

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

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

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

4.2 對比方法

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

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

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

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

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

4.3 對比結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

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

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