移動邊緣計算任務卸載和基站關聯(lián)協(xié)同決策問題研究

于博文 蒲凌君,2 謝玉婷 徐敬東 張建忠

1(南開大學計算機與控制工程學院 天津 300071) 2 (廣東省大數(shù)據(jù)分析與處理重點實驗室(中山大學) 廣州 510006) (bowenyu@mail.nankai.edu.cn)

隨著無線通信技術的發(fā)展以及傳感器種類的豐富，諸如智能汽車、手機等IoT設備可以通過蜂窩網(wǎng)絡、低功耗廣域網(wǎng)等方式接入互聯(lián)網(wǎng)，并能使用裝備的傳感器感知周圍環(huán)境的狀態(tài).在這一背景下，眾多IoT應用應運而生，例如群智感知、智能監(jiān)控、車聯(lián)網(wǎng)應用等.在這類應用中，IoT設備會周期性地采集指定的數(shù)據(jù)，本地處理或上傳到云端服務器進行分析，產(chǎn)生相應知識或模式，為人們的生活和工作提供便利.隨著IoT應用的類型不斷豐富、功能日益強大，它們對計算能力和響應延時提出了更高的要求.例如在車聯(lián)網(wǎng)和增強現(xiàn)實等領域，這些應用要求實時處理采集到的視頻信息并將結果反饋給用戶.大量的密集型計算任務勢必會加快IoT設備的能源消耗，縮短其使用壽命.目前，IoT設備與云端相結合是IoT應用的主要模式.然而IoT設備和遠程云平臺間長距離通信存在網(wǎng)絡傳輸延時不穩(wěn)定的問題，這將會導致IoT應用的延時過長，無法滿足對延時有明確要求的應用.

作為一種很有前景的解決方案，移動邊緣計算能夠有效地解決傳統(tǒng)移動云計算的不足.移動網(wǎng)絡運營商和云服務提供商以合作的形式在網(wǎng)絡邊緣提供豐富的通信和計算資源，IoT設備可以通過高速無線接入網(wǎng)絡在蜂窩網(wǎng)絡邊緣近距離地獲取所需的計算資源和服務[1-2].隨著萬物互聯(lián)和大數(shù)據(jù)時代的到來，IoT設備的數(shù)量和移動數(shù)據(jù)流量得到了飛速提升.根據(jù)Cisco的報告[3]，移動數(shù)據(jù)流量將在未來的5年中增長7倍，到2021年將達到每月49艾字節(jié)(exabyte，EB)(1 EB=106TB)，同時全球IoT設備數(shù)量將從目前的80億增長到120億.這將使其接入網(wǎng)絡獲取移動邊緣服務器的計算資源變得困難.目前的網(wǎng)絡架構將很難應對未來大規(guī)模設備接入網(wǎng)絡的需求.為應對海量的設備連接和數(shù)據(jù)流量，5G架構下的多基站協(xié)作服務場景如超密集網(wǎng)絡(ultra-dense networks， UDN)逐漸成為移動網(wǎng)絡運營商廣泛接受的模式[4-5].在UDN網(wǎng)絡中，移動網(wǎng)絡運營商會部署大量微基站和宏基站為移動設備提供接入服務，這必然會導致蜂窩網(wǎng)絡的能耗顯著提升，使運營成本大幅度提高.因此如何降低UDN網(wǎng)絡的能耗是目前蜂窩網(wǎng)絡研究關注的核心問題[6].本文希望通過對IoT設備的計算卸載、設備-基站關聯(lián)以及基站睡眠的合理調度，提高IoT設備的計算能力，同時盡可能減少IoT設備和蜂窩基站的能源開銷.

結合5G的移動邊緣計算的能耗問題近年來得到了工業(yè)界和學術界的廣泛關注[7-10].文獻[11-13]研究了多設備的計算卸載的最優(yōu)能耗問題.文獻[14-16]對計算卸載與移動邊緣服務器資源聯(lián)合調度展開了研究，解決了移動設備和服務器整體能耗或能源效率最優(yōu)化的問題.然而這些研究工作通常只考慮單一基站(即宏基站)為IoT設備提供接入服務，沒有解決未來5G環(huán)境下的多基站協(xié)作服務場景下的IoT設備、基站和邊緣服務器聯(lián)合調度的問題.

本文提出了一個基于超密集網(wǎng)絡的移動邊緣計算框架(computing offloading framework based on MEC and UDN, COMED).與以往研究工作不同的是:COMED框架實現(xiàn)了超密集網(wǎng)絡中高效的計算卸載、基站睡眠以及IoT設備-基站關聯(lián)三者的調度.框架的示意圖如圖1所示，其中包括IoT設備、微基站、宏基站以及邊緣服務器.IoT設備通過自身的傳感器采集數(shù)據(jù).宏基站負責調度IoT設備與最合適的基站進行關聯(lián)并令沒有關聯(lián)IoT設備的基站進入睡眠狀態(tài)以節(jié)約能量；同時負責調度IoT設備本地處理任務或將任務卸載到邊緣服務器上進行處理.服務器根據(jù)定制的服務計劃為IoT設備上傳的任務分配計算資源.當IoT設備的任務在本地或邊緣服務器上處理完畢之后，結果將會被傳送到互聯(lián)網(wǎng)上.例如車聯(lián)網(wǎng)應用中的危險預警系統(tǒng)需要使用高清攝像頭、超聲波和激光雷達周期性地采集道路上的視頻和數(shù)據(jù)信息，分析當前道路上是否存在異常狀況，進而為人們的生命財產(chǎn)安全提供保障.在COMED框架中，車輛可以本地處理采集到的視頻和數(shù)據(jù)，也可以通過相關調度利用移動邊緣計算提供的豐富的計算資源處理任務.為了讓COMED框架在實際中能夠對IoT應用提供高效的計算卸載支持，它需要滿足3個要求：

1) COMED框架需要在保證IoT應用的服務質量(如延時)的前提下盡可能做到高效節(jié)能.降低IoT設備和基站的能源消耗，對延長IoT設備的使用壽命、提高設備和基站的能源利用率具有十分重要的現(xiàn)實意義.

2) COMED框架需要在線運行.由于蜂窩網(wǎng)絡狀態(tài)、IoT設備移動性以及邊緣云可用資源均隨時間動態(tài)變化，準確預測未來系統(tǒng)信息比較困難，因此這就要求COMED框架能夠僅使用當前系統(tǒng)信息進行任務卸載、基站開關和設備-基站關聯(lián)決策.

3) COMED框架需要具有可伸縮性.由于在城市環(huán)境中會部署大規(guī)模的IoT設備，因此要求COMED框架設計的任務卸載、基站開關和關聯(lián)決策具有較低時間復雜度，從而能為更多的設備和應用提供服務.

Fig. 1 The framework of task offloading for COMED圖1 COMED任務卸載框架示意圖

基于上述要求，本文首先對COMED框架進行系統(tǒng)建模，包括IoT設備資源模型、邊緣服務器模型、IoT應用和負載排隊模型、設備和基站能耗模型等.在此基礎上，本文提出并形式化了一個針對全網(wǎng)絡的任務負載調度、IoT設備-基站關聯(lián)以及基站睡眠調度的聯(lián)合任務卸載問題，旨在最小化時間平均意義下COMED框架的能耗(即IoT設備和基站的能耗之和)，同時兼顧應用任務的延時要求(第2節(jié)).針對優(yōu)化問題，本文根據(jù)李雅普諾夫優(yōu)化理論提出了聯(lián)合計算卸載、基站睡眠和用戶-基站關聯(lián)(joint computing offloading,BS sleeping and user-BS assoication, JOSA)的在線任務卸載算法.作為該算法的核心模塊，本文提出了一個基于松弛-對偶理論的SlotCtrl算法，該算法僅根據(jù)當前時間片內的系統(tǒng)信息進行調度.通過數(shù)學證明可知，本文提出的在線JOSA算法與線下理論最優(yōu)算法的節(jié)能效果十分接近(第3節(jié)).大量模擬實驗結果不但證實了理論分析結果，而且與設備本地處理相比，系統(tǒng)整體節(jié)能30%以上(第4節(jié)).

1 相關工作

為了節(jié)約IoT設備的能量，同時有效地利用邊緣服務器的計算資源，近年來許多研究者開展了針對移動邊緣計算中計算卸載與服務器資源聯(lián)合調度問題的研究.其中，文獻[14]將移動邊緣計算與無線充電技術相結合，研究了可無線充電的IoT設備的計算卸載問題，提出了基于李雅普諾夫優(yōu)化的在線調度策略;文獻[15]假設云端服務器為每個IoT設備分配一臺虛擬機，研究了多設備任務卸載開銷最小化的問題，提出了高效的資源分配策略;文獻[16]研究了車載云計算場景中最大化數(shù)據(jù)傳輸和計算的能源效率問題，在最小的傳輸率、最大的延時和時延抖動的情況下，滿足應用的服務質量要求;文獻[17]假設IoT設備共享有限的無線帶寬和服務器資源，研究了同時滿足無線帶寬和服務器資源限制條件下最大化計算卸載執(zhí)行收益的優(yōu)化問題.通過對問題進行解耦分析，該文提出了高效的設備無線傳輸功率設置及服務器資源分配策略.然而上述這些研究工作只針對單一蜂窩基站場景，難以適用于未來5G架構下的UDN網(wǎng)絡.

針對UDN網(wǎng)絡的移動邊緣計算卸載問題，文獻[18]開展了基于MIMO的多蜂窩基站場景下多設備任務執(zhí)行能耗最小化的研究；文獻[19]解決了C-RAN網(wǎng)絡架構中多設備任務執(zhí)行能耗最小化問題.然而這些工作只關注設備任務執(zhí)行能耗最優(yōu)，并沒有涉及5G架構下蜂窩基站睡眠、設備與蜂窩基站關聯(lián)[20]等關鍵問題.

在這些研究的基礎上，本文重點研究了5G超密集網(wǎng)絡中移動邊緣計算的計算卸載、IoT設備-基站關聯(lián)及基站睡眠調度的聯(lián)合優(yōu)化問題，提出了IoT設備與基站能源最優(yōu)的調度方案，同時保證了任務的延遲約束.

2 系統(tǒng)模型與問題形式化

本文提出的COMED框架如圖1所示，其中包括一個基站集合M={1,2,…,m}和一個IoT設備集合N={1,2,…,n}.在基站集合M中存在一個宏基站以及m-1個微基站.IoT設備可以通過無線網(wǎng)絡接入基站，獲得處于邊緣云服務器的資源.IoT設備的任務可以通過調度，本地執(zhí)行或卸載到邊緣云服務器上執(zhí)行.本文考慮框架內的每個IoT設備用戶在邊緣云服務提供商處購買計算資源，用來處理IoT設備卸載到邊緣云的任務.

類似于UDN以宏基站作為小型基站和微基站的控制器，本文將宏基站作為COMED框架的中央控制器對系統(tǒng)中的任務卸載、基站睡眠以及設備-基站關聯(lián)進行調度，在宏基站中執(zhí)行一個任務引擎進程.任務引擎負責收集IoT設備本地及邊緣服務器端待完成的任務信息、計算資源信息以及IoT設備和基站的網(wǎng)絡狀況信息.這些信息可以用于估計當前任務在每個IoT設備和邊緣服務器上的執(zhí)行時間和能耗，對于框架的調度至關重要.COMED需要訪問這些配置文件，以便更好地對任務卸載、基站睡眠以及設備-基站關聯(lián)進行調度.

本文考慮COMED框架以時間片為單位運行.單位時間片t∈{1,2,3,…}的長度由IoT應用的服務提供商決定.對每個時間片，IoT設備和邊緣服務器需要向宏基站提供當前未完成的任務量和可用的計算資源，IoT設備和基站需要提供當前的網(wǎng)絡狀況(如圖1步驟①).宏基站收到當前任務量和網(wǎng)絡狀況后，由任務引擎構建完整的任務信息、網(wǎng)絡信息以及計算資源信息(如圖1步驟②).這些信息將用于決定任務卸載、基站睡眠以及設備-基站關聯(lián)的調度.接下來，任務引擎將啟動一個負責當前時間片任務卸載、基站睡眠以及設備-基站關聯(lián)調度的調度器(如圖1步驟③).調度器利用當前時間片的任務信息、網(wǎng)絡信息以及計算資源信息來估計如何更好地對任務卸載、基站睡眠以及設備-基站關聯(lián)進行調度.為此，調度引擎需要確定調度策略.目前COMED使用在滿足任務平均延時的前提下盡可能降低執(zhí)行任務能耗的策略.在調度器計算得到該時間片的調度結果之后，調度結果會通過網(wǎng)絡傳給IoT設備、基站和邊緣服務器(如圖1步驟④).任務引擎會通知IoT設備關聯(lián)到哪個基站、本地執(zhí)行和卸載到邊緣服務器的任務量；通知基站是否開啟以及關聯(lián)哪些IoT設備；通知邊緣服務器為相應IoT設備的虛擬機提供服務.

2.1 IoT設備資源模型

本文假設IoT設備搭載單核CPU，按照FIFO順序處理IoT應用的任務.目前主流處理器有許多不同的工作模式，比如根據(jù)工作負載通過動態(tài)電壓頻率調節(jié)CPU頻率(DVFS)的按需模式、以最高CPU頻率運行的性能模式以及以最低CPU頻率運行的節(jié)能模式等.令si(t)為單位時間片IoT設備i的CPU周期數(shù)，其值可通過穩(wěn)定CPU工作頻率得到[21].令pi(si(t))為CPU單位時間片周期數(shù)所對應的功率.

定義0-1控制變量ai j(t)為IoT設備-基站關聯(lián)變量.當ai j(t)=1時表示IoT設備i與基站j關聯(lián)；否則ai j(t)=0.對于IoT設備i，本文定義其上傳功率為pi.當IoT設備i與基站j關聯(lián)時，IoT設備i與基站j的上行鏈路SINRΓi j(t)可以通過IoT設備i以及i周圍的其他IoT設備的上行傳輸鏈路的準靜態(tài)衰落信道增益預估得到.本文假設IoT設備只有在當前上行鏈路SINRΓi j(t)大于目標SINRγi j時才能與相應的基站建立關聯(lián).對于給定的IoT設備i的上行鏈路SINRΓi j(t)，如果不等式Γi j(t)≥γi j成立，本文將IoT設備i與基站j的上傳鏈路的速度定義為[19,22]

ri j=Blog(1+γi j),

其中,B為鏈路帶寬.

對于IoT設備的傳輸模型，有約束條件：

(1)

(2)

(3)

式(1)表示每個IoT設備在同一時間片至多與1個基站進行關聯(lián)；式(2)表示對于任意基站j，同一時刻最多可關聯(lián)hj個IoT設備；式(3)表示IoT設備i只有在上行鏈路SINRΓi j(t)大于目標SINRγi j時才能與基站j建立關聯(lián).此外為了方便起見，本文定義IoT設備i在時間片t的上傳速度為

出于對IoT設備的安全和隱私考慮，本文不考慮宏基站對IoT設備的CPU頻率進行控制.同時為了不增加現(xiàn)有蜂窩網(wǎng)絡調度的開銷，本文不考慮控制IoT設備的上傳功率.為方便讀者閱讀，本文只對問題的約束條件以及重要的公式加以編號.

① 本節(jié)只考慮了IoT設備和基站的能耗，對于邊緣服務器能耗在3.2節(jié)中討論.

2.2 邊緣服務器模型

本文考慮每個IoT設備的用戶分別在邊緣云服務提供商處購買一臺特定的虛擬機.虛擬機每個時間片的計算能力為vi.令0-1控制變量ci(t)表示在時間片t邊緣云是否為虛擬機i分配相應的計算資源.如果ci(t)=1，表示邊緣云在時間片t為虛擬機i分配計算資源；否則ci(t)=0.邊緣云每個時間片分配的計算資源不能超過服務器的物理資源vmax(t)，即存在約束條件:

(4)

2.3 任務模型

本文考慮如下類型的IoT設備應用：應用按照一定頻率周期性使用IoT設備的傳感器采集信息，并進行處理分析.通常，此類應用的任務被要求在一定延時內處理完畢，如車載計算中綠燈最優(yōu)速度建議應用、蜂窩IoT應用以及通過IoT設備收集數(shù)據(jù)的Crowdsourcing應用等.與許多現(xiàn)有工作相同[13,16,23]，COMED框架關注于對IoT應用本地執(zhí)行與卸載執(zhí)行的任務工作量調度.

1) 任務模型.在每個時間片t，移動節(jié)點i會生成ki(t)比特的任務.本文假設任務的平均到來量為λ，其值可以通過離線統(tǒng)計得到.CPU處理任務需要消耗一定的CPU計算資源.定義任務的處理密度為ρ，即處理1 b任務需要ρ個CPU運行周期.例如識別高清視頻一幀中的某一種物體(如車輛、障礙物或行人等)大約需要9.6×104個CPU周期，其任務處理密度大約為50CPU cycles/b[24].

2) 任務隊列模型.本文引入任務隊列來描述當前IoT設備和邊緣服務器中尚未處理的任務量.定義Qi(t)為IoT設備i的任務隊列，其值為IoT設備i在時間片t時的本地任務殘余量.Qi(t)在下一個時間片的更新規(guī)則：

Qi(t+1)=Qi(t)+ki(t)-xi(t)-yi(t),

其中，控制變量xi(t)為時間片t時的本地任務執(zhí)行量，控制變量yi(t)為時間片t時的卸載任務量.這里包含約束條件：

xi(t)≤si(t)/ρ,

(5)

yi(t)≤ri(t),

(6)

xi(t)+yi(t)≤Qi(t)+ki(t).

(7)

式(5)表示IoT設備每個時間片本地處理的任務量不能超過其計算能力；式(6)表示IoT設備每個時間片卸載的任務量不能超過其傳輸能力；式(7)表示IoT設備每個時間片本地處理的任務量和卸載的任務量之和不能超過其任務隊列中的任務殘余量.

定義Li(t)為IoT設備i在邊緣云虛擬機的任務隊列，其值為虛擬機i在時間片t時的任務殘余量.Li(t)在下個時間片的更新規(guī)則為

Li(t+1)=Li(t)+yi(t)-ci(t) min (vi/ρ,Li(t)),

其中,ci(t) min (vi/ρ,Li(t))表示虛擬機i在一個時間片內處理的任務量.

2.4 能耗模型

在COMED框架中，本文考慮的能耗包括IoT設備和基站的能耗①.在IoT設備的能耗模型中，IoT設備能耗由本地計算的能耗和卸載任務的能耗組成.本文假設IoT設備本地計算與卸載任務產(chǎn)生的能耗分別與其計算和傳輸?shù)臅r間成正比.因此IoT設備的能耗可以表示ei(t)為

等式右側前一部分為IoT設備i本地處理xi(t)比特任務的能耗，后一部分為卸載yi(t)比特任務的能耗.

基站的功耗可由一個基礎功耗加一個動態(tài)功耗表示[25].為了方便起見，本文將基站的功耗Pj定義為其基礎功耗的β倍，β可通過對基站能耗的統(tǒng)計得到.在UDN中基站可以通過睡眠調度節(jié)省能量.本文定義0-1控制變量bj(t)為基站睡眠調度變量.當bj(t)=1時，表示基站j處于工作模式；否則bj(t)=0.框架內作為調度服務器的宏基站需要一直處于工作狀態(tài).基站j的能耗可表示為

Ej(t)=bj(t)Pj.

0-1控制變量bj(t)有約束條件：

ai j(t)≤bj(t),

(8)

即IoT設備i只有在基站j處于工作模式時，才能與j進行關聯(lián).

2.5 延 時

IoT設備在運行應用時，通過傳感器采集到的數(shù)據(jù)應在有限的延時dmax內被執(zhí)行.為了滿足應用的延時要求，同時考慮未來5G網(wǎng)絡環(huán)境下大規(guī)模的IoT設備，根據(jù)利特爾法則[26]，本文定義在全局意義上的任務平均延時為

(9)

根據(jù)任務隊列模型，通過迭代可以得到:

2.6 問題形式化

本文通過對IoT設備任務、基站資源以及邊緣服務器資源的分配，旨在最小化系統(tǒng)整體的能量開銷，同時從長遠角度滿足應用的平均延時.本文制定出優(yōu)化問題：

s.t. 式(1)～(9)成立.

3 算法設計

李雅普諾夫優(yōu)化[27]對于解決具有時間平均意義下的目標函數(shù)和約束條件的優(yōu)化問題是非常有效的.通過調用李雅普諾夫drift-plus-penalty方法，本文設計了一個利用每個時間片當前系統(tǒng)信息的任務卸載、基站睡眠和IoT設備-基站關聯(lián)調度的在線算法JOSA對問題P進行求解.

3.1 問題轉化

為了滿足應用延時的約束條件，本文引入虛隊列B：

B(t+1)=[B(t)-nλdmax]++U(t),

其中,[x]+=max(0,x)，U(t)為虛隊列B每個時間片的任務到來量，nλdmax為相應的離開量.虛隊列B用來描述當前系統(tǒng)整體待完成任務的堆積情況.本文規(guī)定虛隊列B的初始值為0.

本文采用李雅普諾夫優(yōu)化框架對目標函數(shù)進行優(yōu)化，同時保證虛隊列和實隊列的穩(wěn)定性.定義如下的二次李雅普諾夫方程：

其中,向量Θ(t)=[Q1(t),Q2(t),…,Qn(t),L1(t),L2(t),…,Ln(t),B(t)]T為框架中所有隊列的剩余量.本文定義每個時間片的drift-plus-penalty方程為

其中,ΔY(Θ(t))=E[Y(Θ(t+1))-Y(Θ(t))]，V是目標函數(shù)最優(yōu)性和隊列穩(wěn)定性之間的權衡參數(shù).根據(jù)李雅普諾夫drift-plus-penalty方程，本文將問題P轉化為

s.t. 式(1)～式(8)成立.

因為新的目標函數(shù)包含難以解決的二次項，所以本文將在最小化引理1中給出目標函數(shù)的上限(即下面引理1中式(10)的右邊).

引理1. 對于任意Θ(t)，李雅普諾夫drift-plus-penalty方程D(Θ(t))滿足：

(10)

其中:

F*是常量，f(t)是不包含控制變量的部分.

證明. 根據(jù)Qi和Li(t)的更新規(guī)則，可以得到

根據(jù)B(t)的更新規(guī)則以及事實([a-b]++c)2≤a2+b2+c2+2a(c-b)可以得到:

B(t+1)2≤B(t)2+(Nλdmax)2+U(t)2+
2B(t)[U(t)-Nλdmax].

將上述等式和不等式代入李雅普諾夫drift-plus-penalty方程D(Θ(t))可以得到:

整理得到:

其中:

我們假設ki(t)≤kmax,xi(t)≤xmax,yi(t)≤ymax,min(vi/ρ,Li(t))≤zmax，整理得到:

其中:

證畢.

由于F*是常量，f(t)中不包含控制變量，因此本文在求解drift-plus-penalty方程D(Θ(t))上界的過程中不考慮F*和f(t).那么最小化drift-plus-penalty方程D(Θ(t))上界的問題可以表示為

s.t. 式(1)～(8)成立.

在此情況下，最小化drift-plus-penalty方程D(Θ(t))的上限能使原問題P有良好的表現(xiàn)是可以被證明的(見3.5節(jié)定理1).

3.2 JOSA算法

本文提出一個在線算法JOSA用來最小化drift-plus-penalty方程D(Θ(t))的上限.

1) 找到每個IoT設備中的任務隊列的最佳工作負載分配、IoT設備-基站關聯(lián)以及基站睡眠調度：

s.t. 式(1)～(3)，式(5)～(8)成立.

2) 找到邊緣服務器資源的最佳分配：

s.t. 式(4)成立.

3) 根據(jù)步驟1和步驟2的結果，更新框架中的實隊列和虛隊列.

3.3 求解P2的SlotCtrl算法實現(xiàn)

問題P2是在線優(yōu)化算法JOSA需要求解的核心問題.P2的控制變量中包含2個0-1整數(shù)變量和2個連續(xù)變量，因此P2是典型的混合整數(shù)規(guī)劃問題，通常是NP難問題.為了能夠高效地對P2進行求解，本文提出了一個基于松弛-對偶理論的SlotCtrl算法作為在線優(yōu)化算法JOSA的核心模塊.其核心思路如圖2所示.首先算法將P2中的0-1整數(shù)控制變量松弛至[0,1]，使問題轉化為P4.其次通過給定控制變量b(t)，x(t)和y(t)，將P4轉化為P5.問題P5是一個較難求解的分數(shù)規(guī)劃問題，因此算法引入與P5具有相同最優(yōu)解的線性規(guī)劃(LP)問題P6.通過引入拉格朗日乘子得到P6的對偶問題Dual-P6，并使用次梯度法獲得對偶問題的優(yōu)化方案.在給定引入拉格朗日乘子的前提下，求解LP問題P7得到a(t).在此基礎上，SlotCtrl算法使用次梯度法對控制變量b(t)和y(t)進行優(yōu)化，即P8.求解LP問題P9得到x(t).最后算法通過迭代(P5至P9)，直至控制變量a(t),b(t)，x(t)和y(t)收斂，得到問題P4的最優(yōu)解.通過分析，可以證明經(jīng)由上述步驟得到的問題P4的解是整數(shù)解，即P2與P4具有相同的最優(yōu)解.

Fig. 2 Schematic diagram of SlotCtrl algorithm圖2 SlotCtrl算法流程示意圖

1) 松弛0-1整數(shù)控制變量a(t)和b(t).

通過將變量ai j(t)和bj(t)松弛至[0,1]，P2轉化為P4.

s.t. 式(1)～(3)、式(5)～(8)成立，且0≤ai j(t),bj(t)≤1.

在P4目標函數(shù)的第2項中，包含控制變量ai j(t)的分數(shù)與控制變量yi(t)相乘的部分.同時在P4的約束條件式(6)中，ai j(t)和yi(t)也耦合在一起.這使問題P4很難直接求解.因此本文將P4分解為2個子問題：首先，對于給定的控制變量b(t)，x(t)和y(t)，對P4進行求解(問題P5～P9)；然后根據(jù)之前的結果，使用次梯度法對b(t)和y(t)進行優(yōu)化(問題P8)，最后求解LP問題P9得到x(t).

2) 對于給定的b(t)，x(t)和y(t)，求解P4.

通過給定b(t)，x(t)和y(t)，P4轉化為問題P5.

s.t. 式(1)～(3)、式(6)、式(8)成立，且0≤ai j(t)≤1.

P5是關于控制變量a(t)的分數(shù)規(guī)劃.由于其目標函數(shù)中除了ai j(t)之外的參數(shù)都是定值且ai j(t)只存在于目標函數(shù)第1項的分母部分，因此可以通過求解與P5具有相同最優(yōu)解的LP問題P6獲得P5的最優(yōu)解.

s.t. 式(1)～(3)、式(6)、式(8)成立，且0≤ai j(t)≤1.

通過引入拉格朗日乘子θ和φ，可以得到P6的對偶問題Dual-P6.

其中:

(11)

Dual-P6的優(yōu)化方案可以通過次梯度法獲得[28]:

(12)

其中,τ為每次迭代的步長，iter為迭代次數(shù).

通過給定θ,φ,b(t)和y(t)，最大化式(11)是一個標準的LP問題，可以表示為

P7:g(θ,φ)

s.t. 式(1)～(3)成立，且0≤ai j(t)≤1.

P7可以通過單純形法等算法有效地進行求解.雖然ai j(t)被松弛為0～1的小數(shù)，但通過P7求得的ai j(t)中的最優(yōu)解仍然是整數(shù).這部分的證明詳見本節(jié)引理2的證明.

3) 優(yōu)化b(t)，x(t)和y(t).

由于問題P6的目標函數(shù)和約束條件都是線性的，因此P6是一個凸優(yōu)化問題.同時，由于P6是具有線性約束條件的LP問題，因此P6滿足Slater條件.根據(jù)Slater定理，P6具有強對偶性，P6和其對偶問題Dual-P6的對偶間隙為0.

令f(a(t))為在給定a(t)的前提下，問題P6的目標函數(shù).b(t)和y(t)的優(yōu)化可以通過求解問題P8得到:

P8可以通過次梯度法求解:

(13)

令f′(a(t),b(t),y(t))為在給定a(t),b(t),y(t)的前提下，問題P5的目標函數(shù).x(t)的優(yōu)化可以通過求解問題P9得到:

s.t. 式(5)、式(7)成立.

問題P9是一個標準的LP問題，可以通過單純形法等算法有效地進行求解.

算法1. SlotCtrl算法.

輸入：框架中所有隊列的剩余量Θ(t)；

輸出：a(t)，b(t)，x(t)和y(t).

① 初始化θ，φ，a(t)，b(t)，x(t)和y(t)；

② do{

③ do{

④ 用LP solver求解P7得到a(t)；

⑤ 根據(jù)式(12)更新θ和φ；}

⑥ while(P7的目標函數(shù)最大值未收斂)；

⑦ 根據(jù)式(13)更新b(t)和y(t)；

⑧ 用LP solver求解P9得到x(t)}

⑨ while (P5的目標函數(shù)最小值未收斂)；

4) SlotCtrl算法分析

性質1. 令A為完全單模矩陣，b為整數(shù)向量，則多面體P{x|Ax≤b}的頂點為整數(shù)[29].

性質2. 如果一個LP問題具有最優(yōu)解，則至少有一個最優(yōu)解在由約束條件定義的多面體的頂點處[30].

引理2.P7的最優(yōu)解是整數(shù)解.

證明. 為了分析P7的性質，本文定義一個新向量a′(t)，a′(t)將a(t)中所有的列整合在一起：

a′(t)=[a1,1(t),a1,2(t),…,a1,m(t),a2,1(t),
a2,2(t),…,a2,m(t),…,an,1(t),
an,2(t),…,an,m(t)]T.

然后將P7改寫為標準形式:

s.t.Aa′(t)≤b，

其中,約束矩陣A和向量b為

b?[h1,h2,…,hm,1,1,…,1]T.

顯然向量b是一個整數(shù)向量.本文需要證明約束矩陣A為完全單模矩陣.將矩陣A分塊:

其中,Wj∈M是m×n的矩陣，其第j行元素全為1，其余元素全為0；Ij∈M是n×n的單位矩陣.令Gk為約束矩陣A的任意k×k的子方陣，det(Gk)為Gk的行列式的值.當k=1時，det(Gk)={0,1}.當k≥2時，會有2種情況：

情況1.Gk是Wj,Ij或0的子方陣.如果Gk是Wj的子方陣，由于Gk至少有一行元素全為0，因此det(Gk)=0.如果Gk是Ij的子方陣，由于Ij是單位矩陣，因此det(Gk)={0,1}.

如果Δv*=0，則第v*列的元素全為0，因此det(Gk)=0.

如果Δv*=1，則det(Gk)=det(Gk-1)={0,±1}.

如果Δv*=2，則Gk的每列都正好有2個元素為1，其中一個來自Wj,另一個來自Ij.由于Wj和Ij中元素1的個數(shù)相等，因此可以通過變化使Gk的一行全為0.因此det(Gk)=0.

所以，約束矩陣A的任意子方陣的行列式值為0或1.根據(jù)完全單模矩陣的定義，約束矩陣A為完全單模矩陣.最后，通過性質1和性質2可以得到P7的最優(yōu)解一定是整數(shù)解.

證畢.

引理3. 算法1的結果是P2的最優(yōu)解.

證明. 根據(jù)引理2可以得到對于任意可行的b(t)，x(t),y(t),θ和φ，P4的最優(yōu)解中控制變量ai j(t)是取值為0或1的整數(shù).因此通過算法1得到的最優(yōu)解中，ai j(t)也是取值為0或1的整數(shù).

對于b(t)，根據(jù)約束式(8)，即ai j(t) ≤bj(t)，如果存在任意i使得ai j(t)=1，則bj(t)=1.而如果?i∈N，ai j(t)=0，則相應的bj(t)=0.這是因為P4的目標函數(shù)中bj(t)的系數(shù)σj(t)是非負的.

綜上所述，根據(jù)算法1求得的最優(yōu)解中，ai j(t)和bj(t)都是取值為0或1的整數(shù)，可以確定算法1的最優(yōu)解即為P2的最優(yōu)解.

證畢.

3.4 求解P3的算法實現(xiàn)

P3是一個0-1整數(shù)規(guī)劃問題，可以通過與P2類似的方法進行求解.本文將P3中的0-1控制變量c(t)松弛至[0,1]，則P3轉化為P10.

s.t. 式(4)成立，且0≤ci(t)≤1.

通過引入拉格朗日乘子η，可以得到P10的對偶問題Dual-P10.

其中:

(14)

Dual-P10的優(yōu)化方案可以通過次梯度法獲得:

其中,τ為每次迭代的步長，iter為迭代次數(shù).通過給定η，最大化式(14)是一個標準的LP問題，可以表示為

P11:g′(η)，

s.t. 式(4)成立，且0≤ci(t)≤1.

證明c(t)的最優(yōu)解為整數(shù)的過程與引理2相同.

3.5 性能分析

定理1表明框架在時間平均意義下的最小能耗期望值的范圍，以及框架內實隊列和虛隊列剩余量在時間平均意義下的積壓范圍.

定理1. 對于任意IoT設備i，假設平均工作負載到來量λi嚴格在系統(tǒng)處理能力范圍內(例如λi+ε≤Ω)，那么可以通過推導得到:

證明. 設通過離線優(yōu)化得到的最佳調度策略為Φ*(t)={x*(t),y*(t),a*(t),b*(t),c*(t))，它滿足:

首先證明平均隊列的上限.由于JOSA算法可以得到每個時間片的最優(yōu)解，因此對于李雅普諾夫drift-plus-penalty方程有:

通過對不等式兩邊取期望并對t=0,1,2,…,T-1進行累加，可以得到:

(15)

又因為Y(0)=0,Y(T)≥0,J(T)≥0，式(15)兩邊分別除以εT可以得到:

接下來證明平均能量的上限.對于式(15)，由于:

不等式兩邊同時除以TV，并令T→∞得到：

綜上所述，系統(tǒng)的任務隊列的堆積量和能量的上限得證.

證畢.

定理1表明，JOSA算法可以在V增加時近似實現(xiàn)離線最優(yōu)化.同時，框架中的所有實隊列和虛隊列在時間平均意義下都是穩(wěn)定的.

4 仿真評估

本文采用芬蘭阿爾托大學和德國慕尼黑大學開發(fā)的機會網(wǎng)絡模擬器ONE[31]，結合模擬器自帶的虛擬城市區(qū)域場景對提出的JOSA算法進行了仿真評估.本文將宏基站設置在場景的中心，30臺微基站隨機分布在場景內，宏基站和微基站分別可同時關聯(lián)50個和20個IoT設備.本文將微基站的功耗設置為190 W，由于宏基站需要一直開啟，因此在仿真評估中不計算宏基站的能耗.對于IoT設備每個時間片的本地計算資源，本文考慮IoT設備CPU的工作頻率為1.0 GHz.IoT設備的CPU和傳輸功率分別設置為60W和3W.IoT設備與基站之間的傳輸帶寬為10 MHz，并采用文獻[32]中的pass-loss和SINR模型.對于每個IoT設備在邊緣服務器中的虛擬機資源，本文將每個設備的虛擬機CPU設置為單核1.5 GHz，所有用戶共享20臺16核物理CPU的服務器.IoT應用的平均到來量為1.5×106bps，任務處理密度為1 CPU cycles/b，延時為1個單位時間片長度.在仿真模擬執(zhí)行過程中，IoT設備在場景內沿著道路按照WorkingDay移動模型移動.仿真模擬實驗執(zhí)行3 600個時間片.

4.1 仿真結果

Fig. 3 The impact of IoT devices number on the COMED system (V=1)圖3 IoT設備的數(shù)量對系統(tǒng)的影響(V=1)

1) IoT設備數(shù)量對系統(tǒng)的影響.IoT設備的數(shù)量對系統(tǒng)整體的影響如圖3所示.我們發(fā)現(xiàn)隨著框架中IoT設備的增多，系統(tǒng)整體能耗與本地執(zhí)行任務相比，有穩(wěn)定在30%左右的整體節(jié)能率.隨著IoT設備數(shù)量的逐漸增加，系統(tǒng)會開啟更多的基站為設備提供服務.本地執(zhí)行任務的比率相應上升，而卸載執(zhí)行的任務比例下降.這是因為這組仿真中我們設置了只有1個時間片的嚴格的任務延時約束，即任務最多在系統(tǒng)中停留1個時間片.而當IoT設備增多時，服務器為每個用戶提供服務的平均時間會減少，因此在嚴格的任務延時設置的條件下，IoT設備不得不選擇本地處理未完成的任務，以滿足應用的QoS要求.

2)V值對系統(tǒng)的影響.圖4展示了不同的V值對于系統(tǒng)性能的影響.在李雅普諾夫優(yōu)化理論中，V是權衡目標函數(shù)最優(yōu)性和隊列穩(wěn)定性之間的參數(shù).在COMED框架中，V用來權衡系統(tǒng)能耗與隊列的穩(wěn)定性.V值越大，代表系統(tǒng)更多關注于能量的節(jié)約，而更少關注隊列的堆積狀況.本文通過設置不同的V值，評估其對系統(tǒng)的能耗和隊列堆積的影響.實驗結果與理論相符，隨著V的增大，系統(tǒng)的能量開銷變少，更加節(jié)能.這是因為，當V較小時，系統(tǒng)會傾向于即時處理到來的任務，這種方式可能不是最節(jié)能的任務執(zhí)行方式；而當V較大時，在延時允許的情況下，任務在系統(tǒng)中會不斷堆積，等待最佳的執(zhí)行任務的時機，例如IoT設備在本地積累一定的任務量，然后在某一個時間片將所積累的任務卸載到服務器上執(zhí)行.

Fig. 4 The impact of V on the COMED system (dmax=5)圖4 V對系統(tǒng)的影響(dmax=5)

3) 任務延時對系統(tǒng)的影響.不同的任務延時dmax設置對系統(tǒng)的影響結果如圖5所示.dmax主要影響系統(tǒng)中隊列堆積的上限.dmax設置的越長，系統(tǒng)中隊列所能堆積的任務數(shù)量越多.與V對系統(tǒng)的影響類似，系統(tǒng)會為隊列中堆積的任務尋找最佳的執(zhí)行時機和方式，因此較長的任務延時設置將會節(jié)省更多的能量.

Fig. 5 The impact of the task delay on the COMED system (V=1)圖5 任務延時設置對系統(tǒng)的影響(V=1)

Fig. 6 System energy consumption versus DualControl algorithm圖6 與DualControl算法的比較

4) 性能比較.由于目前很少有研究涉及任務卸載、基站睡眠與車輛-基站關聯(lián)協(xié)同調度的研究，因此本文考慮使用目前已有的任務卸載策略與不同的基站調度策略相結合的方式與COMED框架進行比較.本文與2種方法進行了比較：①DualControl +微基站以50%的概率隨機開啟.DualControl[15]是一種用戶-運營商協(xié)作任務調度策略，在假設云端服務器為每個移動設備分配一臺虛擬機的前提下，通過用戶調整CPU速度以及運營商將云資源分配給用戶虛擬機最大化兩者的整體效用；②DualControl+微基站一直開啟.對于這2種策略，本文考慮其在調度過程中根據(jù)需求使用網(wǎng)絡資源，但不考慮基站能耗對于調度策略的影響.圖6展示了COMED框架與這2種方法的能量開銷的比較結果.結果說明，任務卸載、設備-基站關聯(lián)以及基站睡眠調度對框架的整體能耗起著至關重要的作用.換句話說，COMED框架將三者結合起來，對于系統(tǒng)整體的節(jié)能是有意義的.

5) 算法執(zhí)行時間.本文在不同微基站數(shù)量的情況下，評估了IoT設備節(jié)點的數(shù)量對JOSA算法執(zhí)行時間的影響.本文使用了一臺處理器為Intel Core i5-2400 Processor@3.1 GHz的臺式機對算法的執(zhí)行時間進行了評估，結果如圖7所示.JOSA算法有2個主要的步驟，步驟1用來調度IoT設備的任務執(zhí)行和卸載量、設備基站-關聯(lián)與基站睡眠，步驟2用來求解移動邊緣服務器的任務調度.可以看到隨著IoT設備的數(shù)量的增加，算法的2個步驟執(zhí)行時間的增長都近似呈線性.在步驟1中，微基站數(shù)量和用戶數(shù)量共同影響算法的執(zhí)行時間.而在步驟2中，微基站的數(shù)量對算法的執(zhí)行時間幾乎沒有影響.

Fig. 7 The execution time of the JOSA algorithm圖7 JOSA算法執(zhí)行時間

5 結束語

本文提出了一個基于超密集網(wǎng)絡的移動邊緣計算框架COMED.IoT設備通過與最適合的基站進行關聯(lián)可以將任務卸載到移動邊緣云服務器上執(zhí)行，服務器根據(jù)定制的服務計劃為每個IoT設備分配計算資源，在處理完設備卸載的任務后將結果傳到互聯(lián)網(wǎng)上.為了實現(xiàn)COMED框架，本文制定了一個任務卸載問題，通過對任務負載調度、設備-基站關聯(lián)以及基站睡眠調度，旨在最小化IoT設備和基站的能耗，同時滿足任務的延時限制.針對這一優(yōu)化問題，本文提出了JOSA在線任務卸載算法，并通過理論分析和仿真實驗證實了COMED框架的性能適用于IoT應用.

[1] Mach P, Becvar Z. Mobile edge computing: A survey on architecture and computation offloading[J]. IEEE Communi-cations Surveys & Tutorials, 2017, 19(3): 1628-1656

[2] Zhang Ke, Mao Yuming, Leng S, et al. Energy-efficient offloading for mobile edge computing in 5G heterogeneous networks[J]. IEEE Access, 2016, 4: 5896-5907

[3] Cisco. Cisco visual networking index: Global mobile data traffic forecast update, 2016—2021[OL]. [2017-09-23]. http://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/mobile-white-paper-c11-520862.html

[4] Wu Jun, Zhang Zhifeng, Hong Yu, et al. Cloud radio access network (C-RAN): A primer[J]. IEEE Network, 2015, 29(1): 35-41

[5] Ge Xiaohu, Tu Song, Mao Guoqiang, et al. 5G ultra-dense cellular networks[J]. IEEE Wireless Communications, 2016, 23(1): 72-79

[6] Wu Jingjin, Zhang Yujing, Zukerman M, et al. Energy-efficient base-stations sleep-mode techniques in green cellular networks: A survey[J]. IEEE Communications Surveys & Tutorials, 2015, 17(2): 803-826

[7] Hu Yunchao, Patel M, Sabella D, et al. Mobile edge computing—A key technology towards 5G[OL]. [2017-09-23]. http://www.etsi.org/images/files/ETSIWhitePapers/etsi_wp11_mec_a_key_technology_towards_5g.pdf

[8] Brown G. Mobile edge computing use cases & deployment options[OL]. [2017-09-18]. https://www.juniper.net/assets/us/en/local/pdf/whitepapers/2000642-en.pdf

[9] Atreyam S. Mobile edge computing—A gateway to 5G era[OL]. [2017-09-18] http://carrier.huawei.com/～/media/CNBG/Downloads/track/mec-whitepaper.pdf

[10] Intel?Builders. Real-world impact of mobile edge computing (MEC)[OL]. [2017-09-18]. https://builders.intel.com/docs/networkbuilders/Real-world-impact-of-mobile-edge-computing-MEC.pdf

[11] Chen Xu. Decentralized computation offloading game for mobile cloud computing[J]. IEEE Trans on Parallel and Distributed Systems, 2015, 26(4): 974-983

[12] Chen Xu, Jiao Lie, Li Wenzhong, et al. Efficient multi-user computation offloading for mobile-edge cloud computing[J]. IEEE/ACM Trans on Networking, 2016, 24(5): 2795-2808

[13] You Changsheng, Huang Kaibin, et al. Energy-efficient resource allocation for mobile-edge computation offloading[J]. IEEE Trans on Wireless Communications, 2017, 16(3): 1397-1411

[14] Mao Yuyi, Zhang Jun, Letaief K B. Dynamic computation offloading for mobile-edge computing with energy harvesting devices[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(12): 3590-3605

[15] Kim Y, Kwak J, Chong S. Dual-side dynamic controls for cost minimization in mobile cloud computing systems[C] //Proc of the 13th IEEE Int Symp on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks. Piscataway, NJ: IEEE, 2015: 443-450

[16] Shojafar M, Cordeschi N, Baccarelli E. Energy-efficient adaptive resource management for real-time vehicular cloud services[OL]. [2017-09-01]. http://ieeexplore.ieee.org/document/7448886/

[17] Lyu X, Tian H, Sengul C, et al. Multiuser joint task offloading and resource optimization in proximate clouds[J]. IEEE Trans on Vehicular Technology, 2017, 66(4): 3435-3447

[18] Sardellitti S, Scutari G, Barbarossa S. Joint optimization of radio and computational resources for multicell mobile-edge computing[J]. IEEE Trans on Signal and Information Processing over Networks, 2015, 1(2): 89-103

[19] Cheng Jinkun, Shi Yuanming, Bai Bo, et al. Computation offloading in cloud-RAN based mobile cloud computing system[C] //Proc of the 17th IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2016

[20] Liu Dantong, Wang Lifeng, Chen Yue, et al. User association in 5G networks: A survey and an outlook[J]. IEEE Communications Surveys & Tutorials, 2016, 18(2): 1018-1044

[21] Kim J M, Kim Y G, Chung S W. Stabilizing CPU frequency and voltage for temperature-aware DVFS in mobile devices[J]. IEEE Trans on Computers, 2015, 64(1): 286-292

[22] Lin Yicheng, Bao Wei, Yu Wei, et al. Optimizing user association and spectrum allocation in HetNets: A utility perspective[J]. IEEE Journal on Selected Areas in Communications, 2015, 33(6): 1025-1039

[23] Kwak J, Kim Y, Lee J, et al. DREAM: Dynamic resource and task allocation for energy minimization in mobile cloud systems[J]. IEEE Journal on Selected Areas in Communications, 2015, 33(12): 2510-2523

[24] Han Siyang, Wang Xiao, Xu Linhai, et al. Frontal object perception for Intelligent Vehicles based on radar and camera fusion[C] //Proc of the 35th IEEE Chinese Control Conf. Piscataway, NJ: IEEE, 2016: 4003-4008

[25] Yan Ming, Chan C A, Li Wenwen, et al. Network energy consumption assessment of conventional mobile services and over-the-top instant messaging applications[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(12): 3168-3180

[26] Little J D C, Graves S C. Little’s law[G] //Building Intuition. Berlin: Springer, 2008: 81-100

[27] Neely M J. Stochastic network optimization with application to communication and queueing systems[J]. Synthesis Lectures on Communication Networks, 2010, 3(1): 1-211

[28] Fisher M L. The Lagrangian relaxation method for solving integer programming problems[J]. Management Science, 1981, 27(1): 1861-1871

[29] Schrijver A. Theory of Linear and Integer Programming[M]. New York: John Wiley & Sons, 1998

[30] Berenstein C A, Gay R. Complex Variables: An Introduction[M]. Berlin: Springer Science & Business Media, 2012

[31] Ker?nen A, Ott J, K?rkk?inen T. The ONE simulator for DTN protocol evaluation[C] //Proc of the 2nd Int Conf on Simulation Tools and Techniques. New York: ACM, 2009: Article No.55

[32] Bethanabhotla D, Bursalioglu O Y, Papadopoulos H C, et al. User association and load balancing for cellular massive MIMO[C] //Proc of the 5th Information Theory and Applications Workshop. Piscataway, NJ: IEEE, 2014: 1-10