學習周報_1

計算卸載決策

通過將計算和存盤資源廣泛地分布到更接近用戶或資料源的網路邊緣，移動
邊緣計算（Mobile Edge Computing, MEC）支持在無線接入網內完成移動應用的計
算卸載程序，大幅降低了網路的端到端時延，并有效減輕了核心網和資料中心的
處理壓力，計算卸載決策，包括用戶側卸載決策（如任務是否卸載、如何卸載以
及何時卸載）和運營商側卸載決策（如是否允許用戶卸載、分配多少資源進行卸
載），是MEC能否提升用戶體驗的關鍵，由于MEC環境的復雜性，影響卸載決策
的因素眾多，如何設計最優的卸載決策策略，以充分挖掘MEC在時延、能耗上的
性能增益，是非常具有挑戰性的科學問題，
任務調度與資源管理是MEC卸載決策程序中需要考慮的兩個重要因素，一方
面，MEC環境本質上是一個分布式異構并行計算環境，只有對任務進行合理調度，
才能充分發揮該計算環境的性能優勢，若考慮網路環境的動態變化，則還需要對
任務卸載的時機進行調度決策，另一方面，由于網路邊緣的資源有限，必須對這
些資源進行合理分配以充分發揮它們的效用，在用戶較多的情況下，還需要對是
否允許用戶卸載進行決策（即準入決策），避免資源的過度競爭，在此背景下，本
文分別針對用戶視角下的面向圖依賴關系的任務卸載調度和面向復雜任務佇列的
動態任務卸載調度，以及運營商視角下的考慮用戶移動性的準入決策與資源分配
三個場景，考慮靜態環境與動態環境中不同應用卸載模型的影響，探索MEC計算
卸載調度與資源管理的最優策略，

移動邊緣計算的由來

早在2000年左右，學術界就開始針對MD的這兩個問題（以及當時還普遍存
在的無線通信帶寬不足、流量昂貴等問題）進行研究，并提出了一種在當時看
來較為超前的解決方案——網路覓食（cyber foraging）
[3, 6–8]，根據該解決方案，
MD每當進入到一個新的區域時，就會主動尋找該區域內潛在的代理（surrogate），
1電子科技大學博士學位論文
MD通過近距離無線點對點技術與代理進行互動，并接受代理提供的計算和快取
服務，當需要執行計算密集型任務時，MD首先將該任務發送到代理，隨后，代
理將代表該MD對任務進行遠程執行，這個將任務發送出去進行遠程執行的程序
被稱為計算卸載，通過計算卸載，網路覓食可以顯著提升移動應用的執行性
能并有效降低MD的能耗，從而大幅提高MD的用戶體驗，這一解決方案在當時受
到了學術界的廣泛追捧，但最終并沒有被產業界所采用，這主要包括以下原因
[8]
，
首先是運營管理方面的問題，如：代理應該部署在網路的什么位置？由誰進行部
署及管理？商業模式是怎樣的？其次是技術實作方面的問題，如：代理上的多個
應用之間應采用何種隔離方案？移動應用程式應該怎樣進行分割？如何保證MD和
代理之間的狀態一致？在移動計算（Mobile Computing, MC）時代
[4–6]，這些問題都還沒有較為令人滿意的答案，
2006年，亞馬遜（Amazon）推出了兩款劃時代的互聯網產品——彈性云主
機EC2（Elastic Cloud Computer）和簡單存盤服務S3（Simple Storage Service），次
年，云計算（Cloud Computing, CC）的概念正式被谷歌（Google）提出，其基于
日益成熟的虛擬化和分布式技術，將計算和存盤資源在網路核心進行集中部署和
統一管理，并封裝為各種能力對用戶提供按需服務，具有很高的靈活性、可靠性、
可擴展性和性價比[9–11]
，在短短的十幾年中，云計算迅速從萌芽階段發展到空前
繁榮，深刻改變了當今的資訊技術產業格局，在云計算出現之后不久，移動計算
便開始與之融合，移動云計算（Mobile Cloud Computing, MCC）的概念隨之被提
出[12–14]，基于云資料中心提供的強大計算和存盤能力，以及3G/4G移動網路提供
的大帶寬資料傳輸能力，計算卸載得以在MD和云之間實作，很好地解決了MD所
面臨的計算能力弱和續航時間短的問題，各類移動應用不再受到MD能力的限制，
得以大規模部署，真正促成了移動互聯網的繁榮，
然而，隨著近年來移動互聯網的進一步發展以及物聯網（Internet of Things,
IoT）[15, 16]
的逐步普及，云解決方案的局限性也逐漸暴露出來，首先，其無法滿
足新興應用場景對網路時延更加苛刻的需求，由于云資料中心位于網路核心，遠
離終端用戶，導致應用資料需要遠距離傳輸，即使在不考慮網路擁塞的情況下，
云解決方案的端到端網路時延也在數十甚至數百毫秒級
[17]，但是，增強/虛擬現
實（Augmented/Virtual Reality, AR/VR），數字醫療（eHealth），自動駕駛，工業智
能控制等新興的強實時應用均要求網路的傳輸時延在毫秒級甚至次毫秒級[18–20]
，
這樣的網路時延需求是云解決方案無法達到的，其次，聯網設備數量的急劇增
加導致網路資料傳輸量呈爆炸性增長，而采用云解決方案匯聚所有網路流量將讓核心網不堪重負，根據思科（Cisco）在2017年發布的視覺網路指數白皮書[21]，到2022年，全球聯網設備數量將達到人口總數的三倍以上，預計為285億臺；而全球年網路流量更將達到4.8澤位元組（ZB），將上述海量資料通過核心網傳輸到云數
據中心會消耗巨大的能量，同時也可能導致嚴重的網路擁塞，
云解決方案的這些局限性均是由資源集中部署在網路核心所導致，因此，將
云計算資源下沉，在靠近用戶或資料源的“網路邊緣”提供計算和存盤能力進行
“就近服務”，已經成為了學術界和產業界的共識，早在2009年，學術界便已經
開始了針對云計算資源下沉的早期研究，隨后，微云（Cloudlet）、霧計算（Fog Computing, FC）[23]以及國內的海計算[24]等概念相繼出現，2014年，移動邊緣計算（Mobile Edge Computing, MEC）[25–29]被歐洲電信標準化協會（EuropeanTelecommunications Standards Institute, ETSI）正式提出，旨在在移動網路邊緣提供IT服務環境和云計算能力，為移動用戶提供更低時延、更高帶寬、更大規模連接的移動通信服務，并進一步打造開放、彈性、協作的生態系統，2017年，ETSI將MEC的概念進一步延伸至其它接入網路（如WiFi，車輛網路，甚至固定
網路），將其更名為多接入邊緣計算（Multi-access Edge Computing）[34]，承載各類云計算能力并為用戶提供就近服務的網路物體也從原來的移動基站或者其附屬服務器擴充為網路邊緣具有處理能力的所有設備，如無線接入點（Access Point,AP）、路邊單元（Road Side Unit, RSU）、交換機、路由器、甚至是其它的MD，這些具有處理能力的網路物體在本文中被統稱為“MEC服務器”（MEC Server,MS），

計算卸載關鍵技術及其卸載決策問題

在MEC中，計算卸載的具體程序如下：

1. 任務資料上傳：將需要卸載的任務的相關資料（如任務的輸入資料、環境
   背景關系資料、任務的執行代碼等）通過無線網路上傳至MS，這些資料可
   以通程序式分析器（program profiler）來獲取
   [13, 27, 47]
   ，
2. 任務遠程執行： MS保證所上傳任務的執行環境與MD一致并對該任務進
   行遠程執行，這是由MS上的計算卸載代理（surrogate/proxy，以下簡稱代
   理）實作的
   [13, 27, 47]
   ，代理的具體實作方式是多樣的：可以被實作為虛擬
   機（Virtual Machine, VM），也可以被實作為網路服務；可以由單用戶獨
   占，也可以由多用戶共享
   [35, 48–50]
   ，
3. 任務結果反饋：當任務遠程執行完成之后，MS通過無線網路將任務的運
   行結果反饋給MD，

可以看出，計算和通信在整個卸載程序中緊密結合，從計算的角度出發，通
過卸載可以大幅縮短任務的執行時延，也節省了任務的本地執行能耗；但從通信
的角度出發，計算卸載程序中資料的上傳和結果的反饋又引入了額外的時間和能
量開銷，因此，計算卸載實質上是一個用通信開銷換取計算開銷的程序，如何進
行合理的卸載決策，以更好地折中計算開銷和通信開銷，從而達到令人滿意的移
動應用體驗，是計算卸載技術的關鍵所在，

對移動用戶而言，其需要
解決是否卸載任務、卸載什么任務、何時卸載任務、何處卸載任務等問題；對運
7電子科技大學博士學位論文
營商而言，其需要解決是否允許用戶卸載任務、分配多少資源執行卸載任務、如
何解決用戶間的資源競爭等問題，由于MEC場景的復雜性，影響卸載決策的因素
眾多，以下分別站在移動用戶和運營商的視角對一些重要的影響因素進行說明，

站在移動用戶視角，卸載決策需要考慮以下因素，首先，待卸載的任務屬性
不同：有的任務不可分割，僅能作為整體進行卸載；有的任務可以劃分為多個子
任務，從而進行細粒度卸載，若進行細粒度卸載，則還需要考慮子任務的劃分方
式和子任務之間的依賴關系等問題，其次，用戶進行計算卸載的目的各異：可能
是為了加速程式運行，也可能是為了降低MD的能耗，還有可能是為了兩者兼顧，
這直接影響到卸載決策的最終優化目標，如果再將系統的動態因素考慮進來，如
任務的動態到達、用戶的移動性、無線信道質量的動態變化等，卸載決策問題將
變得非常復雜，
站在運營商視角，卸載決策需要考慮以下因素，首先，運營商需要服務于多
個用戶，而網路邊緣的計算和通信資源均是有限的，這就涉及到用戶之間的資源
競爭和分配問題，其次，運營商進行卸載決策的目的也同樣是多樣的：可能是為
了讓系統的資源利用率更高；也可能是為了服務更多數量的用戶；還有可能是為
了經濟收益更大，而不同的目的會得到不同的卸載決策問題，另外，為了解決網
絡邊猿澩有限的問題，運營商還可能引入“邊與云”或者“邊與邊”之間的協
作機制，這使得卸載決策問題進一步復雜化，