時月茹 , 李俊

1. 中國科學(xué)院計算機網(wǎng)絡(luò)信息中心，北京 100190

2. 中國科學(xué)院大學(xué)，北京 100049

引 言

隨著5G 和物聯(lián)網(wǎng)的蓬勃發(fā)展，智能終端設(shè)備不斷涌現(xiàn)，網(wǎng)絡(luò)邊緣數(shù)據(jù)以爆炸式增長[1]。然而，其中大部分設(shè)備的計算和存儲能力有限，在處理邊緣數(shù)據(jù)時無法滿足時延敏感、計算密集的需求，需要卸載（offload）到服務(wù)器平臺上處理。

以云計算模型為核心的集中式數(shù)據(jù)處理技術(shù)將這一卸載過程商業(yè)化，表現(xiàn)出明顯的可擴放性和自治性[2]。通過按需付費，云計算用戶可以使用虛擬資源池中的動態(tài)資源，將任務(wù)卸載到云平臺上處理，再在設(shè)備端接收處理結(jié)果。這種軟件即服務(wù)（software as a service）的新體驗，免去了用戶的硬件部署和資源操控環(huán)節(jié)[3]，成為產(chǎn)業(yè)界和學(xué)術(shù)界的研究熱點。但是，考慮到云計算的固有局限性，即任務(wù)經(jīng)過漫長的傳輸距離到達云平臺后才能被處理[4]，云計算不再適用于時延要求極高且應(yīng)用逐漸廣泛的新興場景，例如AR/VR、人臉識別、動態(tài)內(nèi)容交付等。與此同時，萬物互聯(lián)[5]產(chǎn)生了海量的邊緣數(shù)據(jù)，若全部通過云計算處理，將給骨干網(wǎng)帶來巨大的帶寬壓力。涉及到個人隱私的數(shù)據(jù)如果被卸載到云平臺，也會加大安全風(fēng)險[6]。

為此，Satyanarayanan 等人[7]在2009年提出Cloudlet 的概念，通過將計算能力強的服務(wù)器部署在無線網(wǎng)絡(luò)邊緣，為附近的移動設(shè)備提供輕量級服務(wù)。Cloudlet 被視作移動邊緣計算的雛形[8]。2014年，歐洲電信標(biāo)準(zhǔn)化協(xié)會正式提出移動邊緣計算的概念，并發(fā)布白皮書。相比于云計算，移動邊緣計算具有明顯優(yōu)勢[9]：1）時延低。MEC 場景下，節(jié)點之間的距離更短，網(wǎng)絡(luò)傳輸協(xié)議也更簡單，減少了流量控制和路由轉(zhuǎn)發(fā)操作，降低了各個節(jié)點的傳輸和通信時延；2）情景感知（context awareness）。MEC 服務(wù)器能夠利用短距離優(yōu)勢，收集豐富的實時數(shù)據(jù)，了解、掌握用戶的行為習(xí)慣和生活喜好，根據(jù)不同的情景提供個性化服務(wù)；3）安全性高。云平臺屬于大型的公共數(shù)據(jù)中心，信息資源集中，且用戶沒有管理權(quán)限，很可能成為安全攻擊的目標(biāo)，移動邊緣計算則規(guī)避了這些問題。

作為移動邊緣計算的重要研究領(lǐng)域，計算卸載通過將任務(wù)卸載到服務(wù)器的方式，拓展了設(shè)備的計算和存儲能力，幫助用戶獲得更加優(yōu)質(zhì)的服務(wù)體驗[10]。在MEC 系統(tǒng)中，為每位用戶制定合適的卸載策略，是計算卸載的研究核心。2011年，Lagerspetz 等人[11]進行了計算卸載的初步嘗試，并歸納得到基本原則：數(shù)據(jù)量小、計算量大的任務(wù)在可用帶寬充足的條件下，應(yīng)當(dāng)被卸載。但是這一結(jié)論僅考慮能耗對用戶體驗的影響，而在移動邊緣計算中，時延也是非常重要的影響因素。Yang 等人[12]從多用戶角度，研究了時延和能耗的權(quán)衡優(yōu)化問題，通過概率轉(zhuǎn)移矩陣預(yù)測用戶的請求分布，提出基于貪心的在線卸載策略。Sundar 等人[13]將存在鏈?zhǔn)揭蕾囮P(guān)系的多個任務(wù)作為卸載對象，通過啟發(fā)式算法優(yōu)化二進制松弛解，有效地提高了收斂速度。但是上述文獻沒有考慮資源爭奪產(chǎn)生的通信干擾問題。

無線通信資源的爭奪是MEC 網(wǎng)絡(luò)的典型特征。如果多個設(shè)備同時選擇將任務(wù)卸載到服務(wù)器，傳輸信道將被大量占用，引發(fā)嚴(yán)重的同頻干擾，導(dǎo)致資源浪費。Wang 等人[14]提出一種解決方案：首先比較任務(wù)的執(zhí)行開銷等決定是否卸載，再結(jié)合圖著色算法分配物理資源塊（physical resource block），接著最小化時延實現(xiàn)計算資源的優(yōu)化分配。Liu 等人[15]引入排隊論，構(gòu)建MEC 系統(tǒng)多目標(biāo)優(yōu)化模型，通過設(shè)置權(quán)重轉(zhuǎn)化為單目標(biāo)問題，并借助標(biāo)量化方案和內(nèi)點法解決了這一問題。但是上述文獻沒有考慮MEC 服務(wù)器處理不同類型的服務(wù)請求時，必須滿足的先決條件。實際上，只有提前緩存了服務(wù)的源信息、相關(guān)數(shù)據(jù)庫和程序包等，才能在對應(yīng)類型的請求到達后做出處理[16]。另外，MEC 服務(wù)器一般由具備計算和存儲能力的小型基站擔(dān)任[17]，因此服務(wù)器的存儲空間是有限的，同一時刻允許緩存的服務(wù)數(shù)據(jù)也是有限的，需要根據(jù)具體的MEC 場景審慎選擇，緩存最有利于用戶的服務(wù)集合。

本文描述多個基站和多位用戶的移動邊緣計算卸載場景，根據(jù)任務(wù)請求的分布情況，解決基站的服務(wù)緩存問題和用戶的個性化需求問題，實現(xiàn)各位用戶的開銷最小化。本文的主要貢獻如下：

（1）介紹MEC 計算卸載研究成果，對蜂窩同頻小區(qū)拓撲形成的移動邊緣計算卸載場景建模，提出多基站多用戶的計算卸載問題，命名為COmP（Computation Offloading with multiple base stations and user equipment Problem），并給出解決方案；

（2）將服務(wù)緩存過程抽象為一維的0/1 背包模型，通過動態(tài)規(guī)劃建立遞歸關(guān)系，幫助基站挑選待緩存的服務(wù)，采用多人博弈聯(lián)合優(yōu)化通信和計算資源，經(jīng)過有限次迭代后，用戶做出相互滿意的開銷最小化決策，系統(tǒng)達到納什均衡狀態(tài)。

1 MEC 系統(tǒng)模型

移動邊緣計算卸載場景如圖1所示。本場景共包括B個蜂窩同頻小區(qū)，每個小區(qū)內(nèi)有一個基站和數(shù)位用戶，分別介紹如下：

（1）基站。每個基站的信號覆蓋范圍與所在小區(qū)的劃分范圍一致，不存在重疊現(xiàn)象。作為MEC 服務(wù)器，基站具備較強的計算和存儲能力，可以為小區(qū)內(nèi)的用戶提供服務(wù)，滿足多種類型的用戶需求，但必須提前緩存對應(yīng)類型的服務(wù)數(shù)據(jù)；

（2）用戶。一位用戶就是一個用戶設(shè)備（user equipment）。相比于基站，設(shè)備的計算和存儲能力較弱，在處理任務(wù)請求時，需要考慮是否將任務(wù)卸載到基站。每個設(shè)備允許請求多個排隊等待的任務(wù)，但要求它們相互獨立，沒有先后依賴關(guān)系。

為了方便討論，本文引入準(zhǔn)靜態(tài)概念[18]。每個準(zhǔn)靜態(tài)階段一般持續(xù)幾百毫秒，處在該階段時，每位用戶的位置固定，并且請求一項任務(wù)。只有過渡到下一個準(zhǔn)靜態(tài)階段，才會更新用戶的位置坐標(biāo)和任務(wù)請求，基站也會更新緩存的服務(wù)集合。選取任一準(zhǔn)靜態(tài)階段作為研究對象，構(gòu)建計算卸載模型，將建模過程涉及的常量參數(shù)匯總?cè)绫?所示。

表1 移動邊緣計算常量參數(shù)表Table 1 Constant parameter table for MEC

1.1 服務(wù)緩存

服務(wù)緩存是實現(xiàn)移動邊緣計算卸載的重要環(huán)節(jié)。對于MEC 系統(tǒng)來說，基站緩存的服務(wù)集合的好壞，直接影響最終的卸載決策。如圖2所示，4 位用戶請求的任務(wù)分別屬于類型左圖假設(shè)基站緩存了和的服務(wù)數(shù)據(jù)，以此為條件，4 位用戶均無法獲得來自基站的幫助，即使設(shè)備處在低電量的極端狀態(tài)，用戶也只能做出本地執(zhí)行的卸載決策。右圖則假設(shè)基站緩存的服務(wù)類型為和，那么至少有2 位用戶獲得了將任務(wù)卸載到基站的機會，可以在自身能力不足的情況下選擇基站執(zhí)行任務(wù)。

圖1 移動邊緣計算卸載場景Fig.1 Scenario of computation offloading of MEC

圖2 服務(wù)緩存效果比較Fig.2 Comparison of service caching

因此，基站應(yīng)當(dāng)在服務(wù)緩存環(huán)節(jié)審慎選擇。為保證服務(wù)質(zhì)量，需要衡量每個基站與每種服務(wù)類型的匹配度。本文定義為衡量參數(shù)，則

將B個基站的服務(wù)緩存結(jié)果記作Θ，則

1.2 資源調(diào)度

1.2.1 通信模型

用戶在本地執(zhí)行任務(wù)時，無需考慮通信過程，但當(dāng)用戶做出卸載任務(wù)到基站的決策時，考慮到任務(wù)的上傳和下載問題，需要構(gòu)建通信模型。由于大部分的任務(wù)請求，例如語音識別、認(rèn)知輔助等，輸出結(jié)果都遠小于輸入的數(shù)據(jù)規(guī)模，因此，類似于文獻[19]和[20]，本文只研究數(shù)據(jù)上傳過程中的通信開銷而忽略下載過程。

用戶通過無線信道，將執(zhí)行任務(wù)所需的數(shù)據(jù)上傳到基站。小區(qū)內(nèi)的無線信道采用同頻方式部署，頻帶被等分為K個相互正交的子信道，準(zhǔn)靜態(tài)條件又要求每位用戶僅能選擇單個子信道與單個基站建立連接關(guān)系，相應(yīng)地，用戶請求的任務(wù)沿著子信道卸載到基站的信號與干擾加噪聲比為

式(12)考慮了MEC 用戶復(fù)用相同的子信道，可能產(chǎn)生的信號干擾，再引入香農(nóng)頻譜公式[21]，得到數(shù)據(jù)的傳輸速率為

式(14)說明卸載的用戶數(shù)目與傳輸速率成負相關(guān)關(guān)系。如果已經(jīng)有較多的用戶選擇卸載，那么不建議卸載用戶的繼續(xù)加入，甚至需要將部分“基站執(zhí)行”的用戶決策調(diào)整為“本地執(zhí)行”，以降低無線信道的干擾影響。另外，通信過程是一個消耗時間和能量的過程，時延和能耗分別為

1.2.2 計算模型

（1）本地計算模型。設(shè)備擁有一定的計算和存儲能力，可以執(zhí)行自身請求的任務(wù)，時延為

任務(wù)執(zhí)行過程中消耗的能量降低了設(shè)備的工作時長，進而被用戶感知，則

（2）基站計算模型?；镜挠嬎愫痛鎯Y源更為豐富，只要提前緩存了對應(yīng)類型的服務(wù)數(shù)據(jù)，就可以在任務(wù)卸載到基站后做出處理。與本地執(zhí)行類似，基站處理任務(wù)的時延和能耗分別為

1.3 COmP 優(yōu)化目標(biāo)

在計算卸載過程中，每個基站根據(jù)信號覆蓋范圍內(nèi)的用戶請求，緩存合適的服務(wù)集合，每位用戶則根據(jù)基站緩存的服務(wù)情況，比較本地執(zhí)行和卸載到基站執(zhí)行的開銷，并以較低的開銷方式完成任務(wù)。針對蜂窩同頻小區(qū)拓撲形成的移動邊緣計算卸載場景，COmP 將B個基站和N位用戶作為研究對象，目標(biāo)是最小化各位用戶的可感知開銷，其數(shù)學(xué)形式為

COmP 問題的研究面向整個MEC 系統(tǒng)，因此，實現(xiàn)用戶開銷最小化的系統(tǒng)最優(yōu)解為

2 問題解決

本文將COmP 分解為服務(wù)緩存和資源調(diào)度兩個子問題，根據(jù)不同的問題特征設(shè)計解決方案，確定基站緩存的服務(wù)集合和用戶的卸載決策。

2.1 動態(tài)規(guī)劃

為了幫助基站高效地緩存服務(wù)數(shù)據(jù)，引入移動邊緣計算場景下的0/1 背包問題。將基站視作一個等待物品裝入的“背包”，背包的最大存儲空間為，種不同類型的服務(wù)是件等待裝入的“物品”，第 件物品的體積為，價值為?，F(xiàn)要求挑選數(shù)件物品放入背包，使得背包的總價值最大。該問題可表示為

0/1 背包問題具有最優(yōu)子結(jié)構(gòu)，可以通過動態(tài)規(guī)劃建立遞歸關(guān)系，自底向上地構(gòu)造出最優(yōu)解。具體來說，動態(tài)規(guī)劃將原問題轉(zhuǎn)化為多個結(jié)構(gòu)相似的子問題，不斷使用新的子問題的解替換現(xiàn)有結(jié)果，逐步接近乃至確定最優(yōu)解。本文定義變量，表示僅能挑選第1 件到第件的物品放入背包且總體積不超出時，背包的最大價值量，則

式(36)即為原問題和子問題最優(yōu)解之間的遞歸關(guān)系。根據(jù)子問題的物品挑選情況，可以遞歸得到的解，進而確定基站的服務(wù)緩存集合。給出動態(tài)規(guī)劃方案如算法1 所示。

2.2 多人博弈

移動邊緣計算場景下的每一位用戶都是理性個體，只關(guān)心自己的利益，將執(zhí)行自己的任務(wù)需要付出的開銷作為是否卸載的衡量標(biāo)準(zhǔn)，而不關(guān)心其他用戶的開銷情況。但數(shù)據(jù)在上傳的過程中存在信號干擾，這意味著各個任務(wù)的執(zhí)行開銷相互影響，用戶需要先計算出其他位用戶的卸載決策產(chǎn)生的干擾強弱，再由此做出自己的個性化決策?？紤]到不同用戶對于服務(wù)的偏好有所不同，MEC 系統(tǒng)中不會自發(fā)形成用戶間的合作關(guān)系，甚至可能出現(xiàn)較大范圍的資源爭奪現(xiàn)象。

博弈論能夠幫助理性的參與者根據(jù)已知信息和偏好關(guān)系確定下一步的行動計劃，不斷迭代直至系統(tǒng)達到穩(wěn)定狀態(tài)。相應(yīng)地，博弈論適用于解決上述的用戶決策問題。令

納什均衡在博弈論研究中占有重要地位。處在納什均衡狀態(tài)時，對于任意用戶，如果只改變而保持不改變，需要付出的開銷值不會更小。因此，如果其他用戶的卸載決策保持不變，足夠理性的用戶沒有理由打破這種均衡局面。接下來，對移動邊緣計算場景下多人博弈的納什均衡做出定義。

定義1位用戶的決策集合是博弈過程的一個納什均衡，若滿足

根據(jù)這一概念定義可知，如果MEC 系統(tǒng)處于納什均衡狀態(tài)，那么用戶無法通過改變卸載決策繼續(xù)降低開銷值，即實現(xiàn)了COmP 問題的優(yōu)化目標(biāo)。

算法2 確定用戶的卸載決策集合begin：輸入、、、、、、、、、、、、；提前緩存；2）本地執(zhí)行的開銷根據(jù)參與條件：1）請求的服務(wù)被基站集合卸載到基站執(zhí)行的最小開銷，篩選得到參與博弈的用戶集合；//開始多人博弈初始化的卸載決策集合；repeat：for to num將集合的元素賦值給；的當(dāng)前最優(yōu)決策及開銷；保持其他用戶的決策不改變，計算用戶if 當(dāng)前最優(yōu)決策的開銷用戶提出申請：將修改為當(dāng)前最優(yōu)決策；end end從提出申請的用戶集合中隨機挑選一位用戶，同意其申請內(nèi)容，并清除剩余的申請；根據(jù)式 (39)的任務(wù)執(zhí)行開銷；until 所有參與博弈的用戶均未提出申請for to num if輸出末輪迭代結(jié)果；else輸出；end end end

3 實驗結(jié)果與分析

通過Matlab R2015b 平臺驗證算法的有效性。在MEC 仿真系統(tǒng)中，每個蜂窩小區(qū)的單邊長度為30m，基站位于小區(qū)的中心，信號覆蓋范圍與小區(qū)范圍一致?；九c用戶之間的距離取中的隨機值，信道增益為路徑損耗指數(shù)。設(shè)備的發(fā)送功率為3W，背景噪聲為-100dBm，傳輸子信道帶寬為2MHz。另外，除非文中給出特殊說明，否則取

圖3 用戶開銷變化Fig.3 Change of users’ overhead

在三個小區(qū)內(nèi)分別部署基站BS1、BS2 和BS3，不同基站根據(jù)信號覆蓋范圍內(nèi)的用戶請求緩存服務(wù)的情況如圖4和圖5所示。實驗結(jié)果表明，面對用戶的個性化請求，基站的最低空間利用率為81%，平均空間利用率為92%，緩存空間得到了靈活且高效地利用。需要注意的是，緩存空間取值為600 時，BS1、BS2和BS3 已經(jīng)緩存了全部類型的服務(wù)，即使繼續(xù)擴大緩存空間，各基站緩存的服務(wù)集合依然保持不變。

圖6展示了不同的用戶數(shù)目對于博弈參與率和任務(wù)卸載率的影響。根據(jù)圖6可知，小區(qū)用戶從5位增加至60 位，但參與率一直保持在90%以上，證明了算法的有效性。另一方面，在用戶數(shù)目較少的情況下，MEC 系統(tǒng)允許所有參與博弈的用戶將任務(wù)卸載到基站，此時參與率與卸載率相等，而隨著用戶的不斷加入，無線信號干擾嚴(yán)重，因此從25 位用戶開始，卸載率與參與率不再相等，越來越多的用戶選擇本地執(zhí)行任務(wù)。若要緩解這一問題，可以考慮部署更多的子信道。

圖4 基站服務(wù)緩存結(jié)果Fig.4 Cached service of BSs

圖5 基站空間利用率Fig.5 Space utilization of BSs

圖6 博弈效果比較Fig.6 Comparison of games

將本文的卸載策略COmPA（COmP Algorithm）與另外三種算法作對比，結(jié)果如圖8所示。其中，GA（Greedy Algorithm）表示貪心算法，用戶總是選擇當(dāng)前看來開銷最小的決策，并認(rèn)為是最優(yōu)決策；LocalC（Local Computing）表示本地執(zhí)行算法，用戶請求的任務(wù)在自己的設(shè)備上執(zhí)行，不考慮卸載的可能性；BSC（Base Station Computing）表示基站執(zhí)行算法，用戶選擇一條子信道，將請求的任務(wù)卸載到基站后執(zhí)行。從圖8可以看出，在用戶數(shù)目相同的條件下，COmPA 性能明顯優(yōu)于其他算法，用戶平均開銷相比GA、LocalC 和BSC，最高分別節(jié)省28%、98%和64%。但隨著小區(qū)內(nèi)用戶的增加，大部分用戶不再選擇將任務(wù)卸載到基站，而是直接本地執(zhí)行，因此COmPA 的開銷值逐漸接近LocalC。

圖7 個性化需求因子對用戶平均開銷的影響Fig.7 Impact of weighting parameters on overhead

圖8 算法性能比較Fig.8 Comparison of algorithms for MEC

以上仿真實驗說明了COmPA 適用于移動邊緣計算的計算卸載問題，能夠提升基站的緩存空間利用率，增加博弈的參與人數(shù)，優(yōu)化用戶的卸載決策，同時具有較高的魯棒性，可以滿足不同用戶的個性化需求。相比于GA、LocalC 和BSC 等典型算法，COmPA 也能顯著降低用戶的卸載開銷。

4 結(jié)束語

本文針對多個基站和多位用戶的密集網(wǎng)絡(luò)場景，研究移動邊緣計算卸載策略。根據(jù)用戶的請求分布，按照任務(wù)執(zhí)行過程構(gòu)建計算卸載模型，采用動態(tài)規(guī)劃緩存服務(wù)數(shù)據(jù)，并采用多人博弈實現(xiàn)通信和計算資源的優(yōu)化分配，從而降低用戶的卸載開銷，提升MEC 系統(tǒng)性能。仿真結(jié)果表明，經(jīng)過有限次數(shù)的迭代后系統(tǒng)實現(xiàn)納什均衡，計算卸載問題得到有效解決。在下一步的工作中，將引入激勵機制，討論部分用戶受到激勵而聯(lián)合行動的卸載現(xiàn)象。

利益沖突聲明

所有作者聲明不存在利益沖突關(guān)系。