基于博弈論和啟發式算法的超密集網絡邊緣計算卸載

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

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

0 概述

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

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

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

1 系統模型

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

1.1 網絡模型

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

圖1 5G 網絡模型Fig.1 5G network model

1.2 通信模型

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

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

1.3 時延模型

用戶的任務在本地計算和在MEC 服務器上計算具有不同的時延。由于需要將當前任務的一部分數據上傳到MEC 服務器上運行，因此需要考慮兩類時延：本地完成時延和外部完成時延。

1.3.1 本地完成時延

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

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

1.3.2 外部完成時延

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

設MEC 服務器為該組內所有用戶設備分配相同的計算資源，則MEC 服務器上任務執行時間的計算公式如式（5）所示：

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

1.3.3 任務完成時延

由于任務在本地設備和MEC 服務器上的計算是同步進行的，任務實際完成時間應取兩者的最大值，因此用戶ui的任務完成時延Ti如式（7）所示：

1.4 能耗模型

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

其中：Ci是取決于用戶設備架構的能量系數。傳輸能耗的計算公式如式（9）所示：

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

1.5 問題建模

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

其中：αi為調整時延和能量的權重系數，αi∈[0，1]，當αi接近1 時，則該用戶更傾向于低時延，當αi接近0 時，則更關注是否滿足低能耗，每個用戶可根據自己的需求進行設置。因此，優化目標可以表示為式（12）：

2 卸載對象選取策略

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

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

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

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

假設用戶ui的可選策略集用Xui表示，選擇的策略用xi表示，xi∈Xui，其他用戶的策略用x-i表示，博弈的最終目標是使網絡的全局偏好度最大，全局偏好度ppre*的計算公式如式（14）所示：

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

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

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

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

算法1卸載對象選取算法

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

GSO 算法是受螢火蟲閃爍行為啟發提出的算法，各只螢火蟲根據適應度函數調整自身熒光素濃度，濃度低的個體向決策范圍內濃度高的移動，然后根據決策范圍內的螢火蟲數量調整決策范圍半徑，重新在決策范圍內尋找更優點進行移動，當達到最大迭代次數時得到最優解。

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

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

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

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

其中：s為移動步長。螢火蟲移動后需要對決策半徑進行更新，當決策范圍內的鄰居密度小于閾值時，擴大決策半徑，反之縮小。決策半徑的更新方式如式（20）所示：

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

算法2用戶卸載比例算法

3 實驗對比

3.1 仿真環境及參數設置

通過Matlab 對實驗環境進行仿真，驗證所提方案在5G 超密集網絡中的實際性能，并與其他同類方案進行對比。仿真所用的相關參數如表1 所示。

表1 仿真參數Table 1 Simulation parameters

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

3.2 結果分析

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

圖2 模擬超密集網絡分布圖Fig.2 Distribution diagram of simulated UDN

3.2.1 用戶數量對平均時延的影響

用戶數量對平均時延的影響如圖3 所示。AOS策略的平均時延隨著用戶數量的增加持續增大，且遠高于其他3 種策略，這是因為該策略將全部任務進行卸載，當環境內用戶數量增加時，分配給每個用戶的帶寬資源和計算資源會減少，從而使任務數據上傳時延和MEC 服務器的計算時延增加，導致該策略時延過大。ALP 策略將所有任務放在本地執行，平均時延僅與用戶設備的計算能力相關，因而不受用戶數量變化的影響，由于不存在上傳時延和MEC服務器的計算時延，使得平均時延較低，但由于用戶移動設備的計算能力比MEC 服務器低，若把全部任務放在本地處理，將會失去計算能力更高的MEC 服務器的協助，進而顯著增大本地計算的時延，對總時延造成影響，因此該策略在時延上還存在改進的空間。PSO 和本文策略對部分任務進行卸載，可以根據當前網絡狀況自適應調節卸載比例，協調本地設備和MEC 服務器同時工作，從而獲得更低的平均時延。

3.2.2 不同用戶數量對總能耗的影響

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

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

3.2.3 用戶計算能力對平均時延的影響

用戶計算能力對平均時延的影響如圖5 所示。當用戶設備的計算能力增強時，由于AOS 策略將全部數據卸載到邊緣服務器計算，因而平均時延不受影響，但會導致其上傳時延過高。ALP 策略將全部任務放在本地計算，當用戶設備的計算能力提升時，平均時延會迅速下降。PSO 和本文策略由于可以根據當前網絡狀況動態調節卸載比例，因此使得平均時延較小。

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

3.2.4 用戶計算能力對總能耗的影響

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

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

3.2.5 權重系數對時延和能耗的影響

權重系數α可以用來調整用戶對能耗和時延的側重程度，例如在線直播、網絡游戲等高實時性應用可以調高該系數，當α接近1 時強調時延對用戶的影響，可以有效降低系統平均時延，如圖7 所示。對于電池容量有限的移動設備可以減小α，降低系統總能耗，如圖8 所示。

圖7 權重參數α 對平均時延的影響Fig.7 Impact of weight parameters α on average delay

圖8 權重參數α 對總能耗的影響Fig.8 Impact of weight parameters α on total energy consumption

3.2.6 鄰域變化率對時延和能耗的影響

鄰域變化率是GSO 算法中調整決策范圍變化程度的參數。如式（20）所示：當鄰域變化率過小時，若決策范圍內的鄰居數量沒有達到領域螢火蟲閾值，決策范圍不能有效擴大，容易陷入局部最優；當鄰域變化率過大且決策范圍較大時，螢火蟲決策范圍內的鄰居數量較大，可能會過度減小決策范圍，進而陷入局部最優。鄰域變化率對時延和能耗的影響如圖9、圖10 所示，可以看到當鄰域變化率接近0.6 左右時效果更好，因此，選擇鄰域變化率為0.6。

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

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

4 結束語

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