基于博弈論和啟發(fā)式算法的超密集網(wǎng)絡(luò)邊緣計(jì)算卸載

劉振鵬，郭超，王仕磊，陳杰，李小菲

（1.河北大學(xué) 電子信息工程學(xué)院，河北 保定 071002；2.河北大學(xué) 信息技術(shù)中心，河北 保定 071002）

0 概述

隨著5G 時(shí)代的到來，智能終端設(shè)備的數(shù)量快速增長，許多新應(yīng)用也隨之流行［1-3］。然而諸如增強(qiáng)現(xiàn)實(shí)、虛擬現(xiàn)實(shí)、智能互聯(lián)等低時(shí)延、高能耗的應(yīng)用往往需要移動設(shè)備具有充足的電池容量和豐富的計(jì)算資源［4-5］，這些應(yīng)用可能會受限于移動設(shè)備的性能而無法實(shí)現(xiàn)。移動邊緣計(jì)算（Mobile Edge Computing，MEC）技術(shù)［6］可以有效應(yīng)對該問題，當(dāng)任務(wù)卸載到邊緣服務(wù)器上時(shí)，邊緣服務(wù)器可以分擔(dān)用戶設(shè)備的一部分計(jì)算任務(wù)，從而降低時(shí)延和能耗［7-9］。超密集網(wǎng)絡(luò)（Ultra-Dense Network，UDN）［10-12］是5G 中的一種關(guān)鍵技術(shù)，也被認(rèn)為是支持未來無線網(wǎng)絡(luò)部署的最佳方式之一［13-14］。UDN通過在傳統(tǒng)的宏蜂窩小區(qū)中部署大量低功耗、低成本的微型基站，來形成宏微蜂窩共存網(wǎng)絡(luò)，在縮短用戶接入距離的同時(shí)可實(shí)現(xiàn)小區(qū)內(nèi)的無縫覆蓋，提高數(shù)據(jù)的傳輸效率和用戶的服務(wù)質(zhì)量［15］。然而UDN 帶來的網(wǎng)絡(luò)致密化雖然提高了服務(wù)質(zhì)量，但是高密度的基站分布會對同一用戶進(jìn)行重復(fù)覆蓋，用戶選擇哪個基站進(jìn)行任務(wù)卸載，以及如何選擇合適的卸載比例，都是邊緣計(jì)算卸載中面臨的新問題。

針對MEC 網(wǎng)絡(luò)中用戶任務(wù)的卸載和資源分配問題，國內(nèi)外學(xué)者進(jìn)行了大量的研究。CHEN等［16］將任務(wù)卸載問題表示為一個隨機(jī)優(yōu)化問題，并以降低任務(wù)卸載能耗為目標(biāo)對問題進(jìn)行了優(yōu)化，然而該方法沒有充分考慮時(shí)延對任務(wù)卸載造成的影響。LIU等［17-18］將Lyapunov優(yōu)化框架應(yīng)用在任務(wù)卸載中，研究了多用戶進(jìn)行任務(wù)卸載的情況下功率和時(shí)延的權(quán)衡問題，并在時(shí)延和可靠性的約束下，采用Lyapunov 隨機(jī)優(yōu)化方法解決該優(yōu)化問題。GUO等［19］提出了一種計(jì)算效率更高的兩層博弈論貪婪近似卸載方案，并證明了其優(yōu)越的性能。ZHOU等［20］通過構(gòu)建斯塔克伯格博弈模型對帶寬資源進(jìn)行合理分配，同時(shí)適當(dāng)調(diào)整任務(wù)卸載比例來減少任務(wù)的計(jì)算時(shí)延，然而該方法僅考慮了單服務(wù)器的情況，未考慮多用戶多服務(wù)器場景。LYU等［21］提出了一種啟發(fā)式卸載決策算法，該算法是半分布式的，能夠聯(lián)合優(yōu)化卸載決策和通信資源，從而提高系統(tǒng)的性能。針對UDN 環(huán)境中的計(jì)算卸載問題，CHEN等［22］利用軟件定義網(wǎng)絡(luò)的思想，研究了基于UDN 和MEC 的任務(wù)卸載問題，減少了任務(wù)的執(zhí)行時(shí)延和能量消耗。DENG等［23］研究了在多服務(wù)器邊緣計(jì)算環(huán)境下的卸載決策優(yōu)化問題，通過啟發(fā)式算法對資源進(jìn)行配置并優(yōu)化決策，有效提高了服務(wù)質(zhì)量，但該方法沒有考慮多服務(wù)器多用戶情況下用戶之間的競爭關(guān)系對系統(tǒng)性能產(chǎn)生的影響。GUO等［24］將該問題轉(zhuǎn)化為一個混合整數(shù)非線性規(guī)劃問題，結(jié)合遺傳算法和粒子群算法的優(yōu)點(diǎn)，設(shè)計(jì)了分層遺傳算法，并證明了該算法的有效性。FENG等［25］提出了一種融合灰狼算法的混合鯨魚優(yōu)化算法，該算法考慮了模型中的多個因素，獲得了較好的性能。雖然上述研究中提出的系統(tǒng)或算法在能耗和時(shí)延方面都具有較優(yōu)的性能，但主要針對時(shí)延或能耗中的某一方面進(jìn)行優(yōu)化，且沒有考慮在多用戶多服務(wù)器的UDN 網(wǎng)絡(luò)環(huán)境下的用戶卸載對象選取問題。由于UDN 中會出現(xiàn)多個基站的覆蓋范圍相互重疊的狀況，當(dāng)任務(wù)被卸載到不理想的MEC 服務(wù)器上時(shí)，可能會造成系統(tǒng)能耗過高［26-28］。此外，當(dāng)大量用戶分配到同一MEC 服務(wù)器時(shí)，會使得該服務(wù)器負(fù)載過大，對部分用戶和全局性能都會造成不利影響，因此，需要一種能夠在UDN環(huán)境下合理分配用戶的卸載選擇，并使時(shí)延和能耗最小的策略。

本文對超密集網(wǎng)絡(luò)環(huán)境中的卸載決策問題進(jìn)行建模，將其分為卸載對象選取和卸載比例選取2 個問題。針對卸載對象選取問題，考慮MEC 服務(wù)器的鄰近性和工作負(fù)載對性能的影響，定義偏好度函數(shù)，各用戶根據(jù)偏好度進(jìn)行博弈，選擇最優(yōu)的服務(wù)器進(jìn)行卸載。為降低問題的復(fù)雜度，將卸載到相同服務(wù)器的用戶分為一組，根據(jù)分組結(jié)果，將原問題分解成若干個并行的卸載比例選取子問題，采用螢火蟲群優(yōu)化（Glowworm Swarm Optimization，GSO）算法尋找最佳的任務(wù)卸載比例，最終得到最優(yōu)卸載策略。

1 系統(tǒng)模型

當(dāng)用戶設(shè)備的計(jì)算能力無法滿足應(yīng)用的時(shí)延要求時(shí)，需要將部分任務(wù)卸載到MEC 服務(wù)器進(jìn)行計(jì)算。為不失一般性，在5G環(huán)境中采用正交頻分多址（Orthogonal Frequency Division Multiple Access，OFDMA）技術(shù)，為每個基站配備一個計(jì)算能力有限的MEC服務(wù)器，在MEC服務(wù)器中實(shí)現(xiàn)具體計(jì)算。由于基站和MEC 服務(wù)器的距離很小，因此兩者之間的傳輸時(shí)延可以忽略。每個用戶設(shè)備隨機(jī)分布在各個基站的覆蓋范圍之內(nèi)，且每個計(jì)算任務(wù)可以按一定比例進(jìn)行分割，將部分任務(wù)的數(shù)據(jù)上傳到MEC 服務(wù)器進(jìn)行計(jì)算，用戶設(shè)置在任務(wù)卸載期間保持不變。

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

由于5G 網(wǎng)絡(luò)的基站部署密度很高，因此基站的覆蓋范圍可能會存在大量重疊，部分用戶可能處于多個基站的覆蓋范圍之內(nèi)，如圖1 所示。其中，n個用戶表示為集合U={u1，u2，…，un}，m個服務(wù)器表示為集合S={s1，s2，…，sm}。考慮到用戶的移動速度相對于基站的覆蓋范圍較小，可以假定用戶是近似靜止的。

圖1 5G 網(wǎng)絡(luò)模型Fig.1 5G network model

1.2 通信模型

通信模型采用正交頻分復(fù)用技術(shù)，服務(wù)器sj的分組內(nèi)總帶寬表示為，在同一分組內(nèi)，基站為每個用戶分配相同的帶寬，子帶數(shù)量與該分組內(nèi)用戶設(shè)備數(shù)量相同，分組內(nèi)用戶數(shù)量表示為，代表服務(wù)器的工作負(fù)載。不同分組之間的用戶相互無影響，僅受同組內(nèi)其他用戶的影響。由于用戶設(shè)備到服務(wù)器之間需要通過無線信道傳輸，根據(jù)香農(nóng)定理，用戶ui到服務(wù)器sj的數(shù)據(jù)傳輸速率Ri，j如式（1）所示：

其中：pi表示用戶ui的發(fā)射功率；gi，j表示用戶ui到服務(wù)器sj的信道增益；σ2表示背景噪聲的功率。顯然，服務(wù)器負(fù)載與該分組內(nèi)用戶的帶寬和信噪比具有很強(qiáng)的關(guān)聯(lián)性，因此，數(shù)據(jù)上傳速率受服務(wù)器負(fù)載的影響較大。

1.3 時(shí)延模型

用戶的任務(wù)在本地計(jì)算和在MEC 服務(wù)器上計(jì)算具有不同的時(shí)延。由于需要將當(dāng)前任務(wù)的一部分?jǐn)?shù)據(jù)上傳到MEC 服務(wù)器上運(yùn)行，因此需要考慮兩類時(shí)延：本地完成時(shí)延和外部完成時(shí)延。

1.3.1 本地完成時(shí)延

對于本地完成時(shí)延，主要考慮任務(wù)在本地設(shè)備進(jìn)行處理的部分，無需考慮數(shù)據(jù)傳輸造成的時(shí)延，因此僅與計(jì)算任務(wù)所需周期和用戶設(shè)備的計(jì)算能力有關(guān)。本地完成時(shí)延的計(jì)算公式如式（2）所示：

其中：di表示處理任務(wù)的數(shù)據(jù)量；fc表示處理每比特?cái)?shù)據(jù)量所需的時(shí)鐘周期數(shù)表示用戶ui的本地設(shè)備的CPU 周期頻率；βi表示用戶ui的任務(wù)卸載比例，βi∈[0，1]，βi=0 表示任務(wù)全部在本地設(shè)備完成。

1.3.2 外部完成時(shí)延

外部完成時(shí)延是指從用戶發(fā)送數(shù)據(jù)開始，到結(jié)果返回這段過程所產(chǎn)生的時(shí)延。用戶ui外部完成時(shí)延主要包括三部分：任務(wù)數(shù)據(jù)上傳時(shí)延，MEC 服務(wù)器上任務(wù)的執(zhí)行時(shí)延，接收計(jì)算結(jié)果所需的反饋時(shí)延。外部完成時(shí)延和任務(wù)數(shù)據(jù)上傳時(shí)延的計(jì)算公式如式（3）和式（4）所示：

設(shè)MEC 服務(wù)器為該組內(nèi)所有用戶設(shè)備分配相同的計(jì)算資源，則MEC 服務(wù)器上任務(wù)執(zhí)行時(shí)間的計(jì)算公式如式（5）所示：

其中：fs表示MEC 服務(wù)器的CPU 周期頻率。由于反饋時(shí)延遠(yuǎn)小于上傳時(shí)延，因此可以忽略反饋時(shí)延［29］，則外部完成時(shí)延可由式（6）表示：

1.3.3 任務(wù)完成時(shí)延

由于任務(wù)在本地設(shè)備和MEC 服務(wù)器上的計(jì)算是同步進(jìn)行的，任務(wù)實(shí)際完成時(shí)間應(yīng)取兩者的最大值，因此用戶ui的任務(wù)完成時(shí)延Ti如式（7）所示：

1.4 能耗模型

由于用戶的移動設(shè)備受電池電量消耗的影響較大，而MEC 服務(wù)器具有穩(wěn)定的供電來源，因此暫不考慮MEC 服務(wù)器產(chǎn)生的能耗，而主要考慮用戶移動設(shè)備產(chǎn)生的能耗。用戶ui完成任務(wù)所需的能耗主要由兩部分組成：用戶的本地計(jì)算能耗和數(shù)據(jù)傳輸?shù)組EC 服務(wù)器的能耗本地計(jì)算能耗的計(jì)算公式如式（8）所示：

其中：Ci是取決于用戶設(shè)備架構(gòu)的能量系數(shù)。傳輸能耗的計(jì)算公式如式（9）所示：

用戶ui完成任務(wù)所需總能量Ei的計(jì)算公式如式（10）所示：

1.5 問題建模

為平衡用戶的時(shí)延和能耗，首先對用戶進(jìn)行分組，然后分別計(jì)算各組用戶的時(shí)延和能耗，此處引入用戶成本函數(shù)Hi，j，用于表示服務(wù)器sj的分組內(nèi)用戶ui的綜合開銷，計(jì)算公式如式（11）所示：

其中：αi為調(diào)整時(shí)延和能量的權(quán)重系數(shù)，αi∈[0，1]，當(dāng)αi接近1 時(shí)，則該用戶更傾向于低時(shí)延，當(dāng)αi接近0 時(shí)，則更關(guān)注是否滿足低能耗，每個用戶可根據(jù)自己的需求進(jìn)行設(shè)置。因此，優(yōu)化目標(biāo)可以表示為式（12）：

2 卸載對象選取策略

為解決用戶的卸載對象選取問題，可以先通過計(jì)算一個偏好度指標(biāo)來兼顧基站的距離和負(fù)載對用戶性能產(chǎn)生的影響［30］，再根據(jù)該指標(biāo)選擇卸載對象。用戶ui到服務(wù)器sj的偏好度如式（13）所示：

其中：表示用戶ui到服務(wù)器sj的距離；cj表示基站的覆蓋范圍；表示當(dāng)前分配給該基站的用戶數(shù)量；n表示用戶總數(shù)。偏好度越高，則該基站越有利于用戶的任務(wù)卸載。為降低原問題的復(fù)雜度，在用戶確定卸載對象后再對其進(jìn)行分組，將卸載到相同MEC 服務(wù)器的用戶分為一組，將原問題分解為多個并行的子問題。

然而當(dāng)所有用戶都選擇自己偏好度最大的基站進(jìn)行卸載時(shí)，會存在計(jì)算資源和通信資源競爭的問題。假設(shè)所有用戶同時(shí)發(fā)送任務(wù)卸載請求，每個用戶無法得知其他人的卸載選擇，都會選擇距離最近的基站進(jìn)行卸載，當(dāng)大量用戶集中在某一基站附近時(shí)，如式（1）所示，基站負(fù)載的增加會降低該基站內(nèi)所有用戶的性能。當(dāng)多個用戶同時(shí)進(jìn)行任務(wù)卸載時(shí)，都會為了達(dá)到自身的最優(yōu)而選擇卸載對象，但是由于無法及時(shí)得到當(dāng)前基站的負(fù)載狀態(tài)，其他選擇反而有可能獲得更好的性能，因此，本文考慮采用博弈論的方法得到最優(yōu)的卸載對象選取策略。

本文使用有限的完全信息非合作博弈策略，每個用戶都可以得到自己和其他用戶的全部策略信息，由于用戶可卸載的基站數(shù)量是有限的，因此各用戶的策略空間也是有限的。每個用戶按順序進(jìn)行決策并公開，后決策的用戶依據(jù)當(dāng)前狀況做出決策，每個用戶追求自身最優(yōu)。

假設(shè)用戶ui的可選策略集用Xui表示，選擇的策略用xi表示，xi∈Xui，其他用戶的策略用x-i表示，博弈的最終目標(biāo)是使網(wǎng)絡(luò)的全局偏好度最大，全局偏好度ppre*的計(jì)算公式如式（14）所示：

其中：U代表所有用戶；{}代表用戶ui的可選策略集；{(xi x-i)}表示該用戶所選策略的偏好度。

由于用戶數(shù)量和策略空間都是有限的，且每個用戶從有限的策略集中選擇一個純策略，使得行動次數(shù)也是有限的，因此該卸載對象選取策略中的博弈存在納什均衡，并可以經(jīng)過有限次數(shù)的迭代后得到均衡點(diǎn)。均衡時(shí)的總體最佳策略Xpre*可以表示為：

其中：為用戶ui的最佳策略。為獲得該平衡點(diǎn)策略，本文提出一種有效的卸載對象選取算法。假設(shè)用戶能夠獲取各基站的當(dāng)前負(fù)載、服務(wù)器計(jì)算能力和基站位置信息。首先，每個用戶分別計(jì)算到各個服務(wù)器的偏好度，服務(wù)器初始負(fù)載為覆蓋范圍內(nèi)的用戶數(shù)量，用戶初始卸載策略為選擇偏好度最大的服務(wù)器進(jìn)行卸載；然后，所有用戶根據(jù)偏好度計(jì)算自身是否存在更好的策略，并選取其中能夠使全局偏好度最大的策略作為提案與其他用戶進(jìn)行競爭。每次迭代選取對全局偏好度提升最大的用戶進(jìn)行策略更新；最后，將所有用戶的偏好度相加得到全局偏好度。

將所有用戶提案的更新策略儲存到策略更新集Xupdate中，并把全局偏好度更新到偏好度更新集Pupdate中，當(dāng)Xupdate為空時(shí)，表示所有用戶已達(dá)到當(dāng)前的最優(yōu)策略，同時(shí)系統(tǒng)達(dá)到納什均衡狀態(tài)，用戶分組算法收斂到全局最優(yōu)解。卸載對象選取算法的具體步驟如算法1 所示。

算法1卸載對象選取算法

在完成卸載對象選取和用戶分組之后，原本多用戶多服務(wù)器環(huán)境下的任務(wù)卸載問題被轉(zhuǎn)化為多個并行的多用戶單服務(wù)器任務(wù)卸載問題。由于用戶可以將任務(wù)的一部分卸載到邊緣服務(wù)器進(jìn)行計(jì)算，兩者是同時(shí)進(jìn)行的，可以顯著減少完成任務(wù)所需的時(shí)間，因此本文采用部分卸載策略對任務(wù)進(jìn)行卸載。然而將任務(wù)卸載到服務(wù)器上會產(chǎn)生數(shù)據(jù)上傳時(shí)延和傳輸能耗，為了使用戶的開銷最小化，選擇合適的任務(wù)卸載比例至關(guān)重要。為解決該問題，本文采用螢火蟲群優(yōu)化（GSO）算法來對任務(wù)卸載比例進(jìn)行分配。

GSO 算法是受螢火蟲閃爍行為啟發(fā)提出的算法，各只螢火蟲根據(jù)適應(yīng)度函數(shù)調(diào)整自身熒光素濃度，濃度低的個體向決策范圍內(nèi)濃度高的移動，然后根據(jù)決策范圍內(nèi)的螢火蟲數(shù)量調(diào)整決策范圍半徑，重新在決策范圍內(nèi)尋找更優(yōu)點(diǎn)進(jìn)行移動，當(dāng)達(dá)到最大迭代次數(shù)時(shí)得到最優(yōu)解。

本文分別對各用戶的最優(yōu)卸載比例進(jìn)行計(jì)算，為每個用戶分配一定數(shù)量的螢火蟲尋找最優(yōu)解，將卸載比例β∈(0，1)作為螢火蟲的移動空間，熒光素濃度通過用戶總開銷表示。用戶ui的第x只螢火蟲的熒光素濃度如式（17）所示：

其中：Li，x(a)表示第a次迭代時(shí)的熒光素濃度，且Li，x(0)=0；ρ為熒光素?fù)]發(fā)系數(shù)；η為適應(yīng)度提取比例；J(βi，x(a))=表示第a次迭代時(shí)用戶的總開銷；βi，x(a)表示第a次迭代時(shí)用戶ui的第x只螢火蟲的初始位置，為(0，1)之間的隨機(jī)值。

首先根據(jù)式（17）計(jì)算各螢火蟲初始熒光素濃度，由于J(βi，x(a))是關(guān)于βi，x(a)的函數(shù)，因此可知各螢火蟲熒光素初始濃度也為隨機(jī)值。在此之后，螢火蟲個體需要根據(jù)決策范圍內(nèi)其他螢火蟲的熒光素濃度大小計(jì)算移動概率Q，如式（18）所示：

其中：Qx，y(a)表示第x只螢火蟲向第y只螢火蟲移動的概率，y∈Gx(a)；Gx(a)為a次迭代時(shí)第x只螢火蟲所有鄰居的集合，Gx(a)={y：||βi，y(a)-βi，x(a)||

其中：s為移動步長。螢火蟲移動后需要對決策半徑進(jìn)行更新，當(dāng)決策范圍內(nèi)的鄰居密度小于閾值時(shí)，擴(kuò)大決策半徑，反之縮小。決策半徑的更新方式如式（20）所示：

其中：rs表示螢火蟲感知半徑；λ表示鄰域變化率；ga表示控制螢火蟲鄰居數(shù)的閾值。用戶卸載比例算法的具體步驟如算法2 所示。

算法2用戶卸載比例算法

3 實(shí)驗(yàn)對比

3.1 仿真環(huán)境及參數(shù)設(shè)置

通過Matlab 對實(shí)驗(yàn)環(huán)境進(jìn)行仿真，驗(yàn)證所提方案在5G 超密集網(wǎng)絡(luò)中的實(shí)際性能，并與其他同類方案進(jìn)行對比。仿真所用的相關(guān)參數(shù)如表1 所示。

表1 仿真參數(shù)Table 1 Simulation parameters

為驗(yàn)證本文方案的性能，選擇3 種方案進(jìn)行對比，分別是全本地處理（All-Local Processing，ALP）策略、全卸載策略（All-Offloading Strategy，AOS）和基于粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法的任務(wù)卸載策略。全本地處理策略將全部任務(wù)在本地執(zhí)行，不進(jìn)行卸載，這種方式避免了數(shù)據(jù)傳輸帶來的時(shí)延和能耗，但會增大用戶本地設(shè)備處理的成本。全卸載策略將用戶的所有任務(wù)都卸載到隨機(jī)可達(dá)的邊緣服務(wù)器，這種方式可以有效減少本地計(jì)算帶來的能量消耗，但會增加數(shù)據(jù)上傳的能耗，且在傳輸過程中存在較高的時(shí)延?；赑SO 算法的任務(wù)卸載策略對任務(wù)進(jìn)行部分卸載，卸載到距離最近的服務(wù)器，PSO 算法受到鳥類捕食行為的啟發(fā)，將任務(wù)卸載比例作為優(yōu)化問題的搜索空間，將每個用戶抽象為一個粒子，用于表征問題的一個可行解，這種方式可以快速地找到卸載對象，同時(shí)能夠?qū)θ蝿?wù)的卸載比例進(jìn)行自適應(yīng)調(diào)整。

3.2 結(jié)果分析

根據(jù)表1 中的參數(shù)進(jìn)行仿真實(shí)驗(yàn)，分別考慮用戶數(shù)量、用戶設(shè)備計(jì)算能力、權(quán)重系數(shù)、螢火蟲鄰域變化率等因素，對所有用戶的平均時(shí)延和總能耗進(jìn)行分析，其中平均時(shí)延為所有用戶時(shí)延的總和求平均，而不是所有用戶時(shí)延的總和，總能耗為所有用戶能耗的總和。模擬環(huán)境設(shè)置在500 m×500 m 的多服務(wù)器覆蓋場景中，如圖2 所示。

圖2 模擬超密集網(wǎng)絡(luò)分布圖Fig.2 Distribution diagram of simulated UDN

3.2.1 用戶數(shù)量對平均時(shí)延的影響

用戶數(shù)量對平均時(shí)延的影響如圖3 所示。AOS策略的平均時(shí)延隨著用戶數(shù)量的增加持續(xù)增大，且遠(yuǎn)高于其他3 種策略，這是因?yàn)樵摬呗詫⑷咳蝿?wù)進(jìn)行卸載，當(dāng)環(huán)境內(nèi)用戶數(shù)量增加時(shí)，分配給每個用戶的帶寬資源和計(jì)算資源會減少，從而使任務(wù)數(shù)據(jù)上傳時(shí)延和MEC 服務(wù)器的計(jì)算時(shí)延增加，導(dǎo)致該策略時(shí)延過大。ALP 策略將所有任務(wù)放在本地執(zhí)行，平均時(shí)延僅與用戶設(shè)備的計(jì)算能力相關(guān)，因而不受用戶數(shù)量變化的影響，由于不存在上傳時(shí)延和MEC服務(wù)器的計(jì)算時(shí)延，使得平均時(shí)延較低，但由于用戶移動設(shè)備的計(jì)算能力比MEC 服務(wù)器低，若把全部任務(wù)放在本地處理，將會失去計(jì)算能力更高的MEC 服務(wù)器的協(xié)助，進(jìn)而顯著增大本地計(jì)算的時(shí)延，對總時(shí)延造成影響，因此該策略在時(shí)延上還存在改進(jìn)的空間。PSO 和本文策略對部分任務(wù)進(jìn)行卸載，可以根據(jù)當(dāng)前網(wǎng)絡(luò)狀況自適應(yīng)調(diào)節(jié)卸載比例，協(xié)調(diào)本地設(shè)備和MEC 服務(wù)器同時(shí)工作，從而獲得更低的平均時(shí)延。

3.2.2 不同用戶數(shù)量對總能耗的影響

不同用戶數(shù)量對總能耗的影響如圖4 所示。ALP 和PSO 策略雖然平均時(shí)延較低，但存在著能耗較高的問題，這是因?yàn)樵诓豢紤]邊緣服務(wù)器能耗的前提下，能耗主要來自于本地計(jì)算能耗和數(shù)據(jù)上傳能耗，ALP 策略將全部任務(wù)放在本地執(zhí)行，會使本地計(jì)算量增大，導(dǎo)致能耗迅速增高，而PSO 策略由于所有用戶僅選擇距離最近的基站進(jìn)行卸載，導(dǎo)致部分服務(wù)器工作負(fù)載過大，從而將用戶的卸載比例減小，使得本地能耗增加。AOS 和本文策略由于本地計(jì)算數(shù)據(jù)量較小，獲得了較低的能耗，然而隨著用戶數(shù)量的增加，分配的帶寬資源減少，任務(wù)上傳速率也會變慢，AOS 策略的傳輸能耗會隨上傳時(shí)延的增加而迅速增加。根據(jù)以上分析，當(dāng)用戶數(shù)量增加時(shí)，綜合時(shí)延和能耗兩方面來看，本文策略具有更好的表現(xiàn)。

圖4 用戶數(shù)量對總能耗的影響Fig.4 Impact of number of users on total energy consumption

3.2.3 用戶計(jì)算能力對平均時(shí)延的影響

用戶計(jì)算能力對平均時(shí)延的影響如圖5 所示。當(dāng)用戶設(shè)備的計(jì)算能力增強(qiáng)時(shí)，由于AOS 策略將全部數(shù)據(jù)卸載到邊緣服務(wù)器計(jì)算，因而平均時(shí)延不受影響，但會導(dǎo)致其上傳時(shí)延過高。ALP 策略將全部任務(wù)放在本地計(jì)算，當(dāng)用戶設(shè)備的計(jì)算能力提升時(shí)，平均時(shí)延會迅速下降。PSO 和本文策略由于可以根據(jù)當(dāng)前網(wǎng)絡(luò)狀況動態(tài)調(diào)節(jié)卸載比例，因此使得平均時(shí)延較小。

圖5 用戶計(jì)算能力對平均時(shí)延的影響Fig.5 Impact of user computing power on average delay

3.2.4 用戶計(jì)算能力對總能耗的影響

用戶計(jì)算能力對總能耗的影響如圖6 所示。AOS策略可以將任務(wù)全部卸載到邊緣服務(wù)器，總能耗不受本地計(jì)算能力影響，但導(dǎo)致該策略能耗較高的原因是：雖然僅存在傳輸能耗，但并不意味著卸載比例越大總能耗越低。本地計(jì)算能耗減小的代價(jià)是大量數(shù)據(jù)需要上傳到MEC 服務(wù)器，使得上傳時(shí)延遠(yuǎn)超其他幾種策略，而傳輸能耗和上傳時(shí)延正相關(guān)，使得傳輸能耗大幅增加，造成總能耗較高。ALP 策略將全部任務(wù)在本地執(zhí)行，總能耗隨著用戶計(jì)算能力的提升迅速增加。PSO策略具有較好的表現(xiàn)但本文所提方法的能耗更低。綜上所述，當(dāng)用戶計(jì)算能力提升時(shí)，本文策略在時(shí)延和能耗上的表現(xiàn)更優(yōu)。

圖6 用戶計(jì)算能力對總能耗的影響Fig.6 Impact of user computing power on total energy consumption

3.2.5 權(quán)重系數(shù)對時(shí)延和能耗的影響

權(quán)重系數(shù)α可以用來調(diào)整用戶對能耗和時(shí)延的側(cè)重程度，例如在線直播、網(wǎng)絡(luò)游戲等高實(shí)時(shí)性應(yīng)用可以調(diào)高該系數(shù)，當(dāng)α接近1 時(shí)強(qiáng)調(diào)時(shí)延對用戶的影響，可以有效降低系統(tǒng)平均時(shí)延，如圖7 所示。對于電池容量有限的移動設(shè)備可以減小α，降低系統(tǒng)總能耗，如圖8 所示。

圖7 權(quán)重參數(shù)α 對平均時(shí)延的影響Fig.7 Impact of weight parameters α on average delay

圖8 權(quán)重參數(shù)α 對總能耗的影響Fig.8 Impact of weight parameters α on total energy consumption

3.2.6 鄰域變化率對時(shí)延和能耗的影響

鄰域變化率是GSO 算法中調(diào)整決策范圍變化程度的參數(shù)。如式（20）所示：當(dāng)鄰域變化率過小時(shí)，若決策范圍內(nèi)的鄰居數(shù)量沒有達(dá)到領(lǐng)域螢火蟲閾值，決策范圍不能有效擴(kuò)大，容易陷入局部最優(yōu)；當(dāng)鄰域變化率過大且決策范圍較大時(shí)，螢火蟲決策范圍內(nèi)的鄰居數(shù)量較大，可能會過度減小決策范圍，進(jìn)而陷入局部最優(yōu)。鄰域變化率對時(shí)延和能耗的影響如圖9、圖10 所示，可以看到當(dāng)鄰域變化率接近0.6 左右時(shí)效果更好，因此，選擇鄰域變化率為0.6。

圖9 鄰域變化率對平均時(shí)延的影響Fig.9 Impact of neighborhood change rate on average delay

圖10 鄰域變化率對總能耗的影響Fig.10 Impact of neighborhood change rate on total energy consumption

4 結(jié)束語

本文研究多用戶多服務(wù)器的超密集網(wǎng)絡(luò)環(huán)境下移動邊緣計(jì)算的部分任務(wù)卸載問題。以最小化所有用戶的平均時(shí)延和總能耗為目標(biāo)，將該問題分為卸載對象選取問題和卸載比例選取問題，設(shè)計(jì)一種基于博弈論和螢火蟲群優(yōu)化算法的卸載策略。針對卸載對象選取問題，綜合考慮MEC 服務(wù)器到用戶的傳輸距離和MEC 服務(wù)器的工作負(fù)載，定義偏好度指標(biāo)。各用戶根據(jù)偏好度進(jìn)行博弈，得到最有利于自己和全局的卸載對象選取策略。在此基礎(chǔ)上，將選擇同一服務(wù)器卸載的用戶分為一組，使原問題分解為若干個并行的卸載比例選取的子問題。針對卸載比例選取的問題，采用螢火蟲群優(yōu)化算法對各用戶的最佳卸載比例進(jìn)行計(jì)算，將任務(wù)的卸載比例作為螢火蟲的位置，以降低平均時(shí)延和總能耗為目標(biāo)，算法經(jīng)過多次迭代后得到各用戶的最佳卸載比例。仿真實(shí)驗(yàn)結(jié)果表明，本文策略相比基于PSO 的卸載策略時(shí)延降低22%，能耗降低20%，有效提高了系統(tǒng)的運(yùn)行效率。下一步將考慮服務(wù)緩存對應(yīng)用程序時(shí)延和帶寬成本的影響，結(jié)合緩存決策優(yōu)化MEC 系統(tǒng)中的任務(wù)卸載結(jié)構(gòu)。