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

1(南開(kāi)大學(xué)計(jì)算機(jī)與控制工程學(xué)院 天津 300071) 2 (廣東省大數(shù)據(jù)分析與處理重點(diǎn)實(shí)驗(yàn)室(中山大學(xué)) 廣州 510006) (bowenyu@mail.nankai.edu.cn)

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

2.1 IoT設(shè)備資源模型

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

定義0-1控制變量ai j(t)為IoT設(shè)備-基站關(guān)聯(lián)變量.當(dāng)ai j(t)=1時(shí)表示IoT設(shè)備i與基站j關(guān)聯(lián)；否則ai j(t)=0.對(duì)于IoT設(shè)備i，本文定義其上傳功率為pi.當(dāng)IoT設(shè)備i與基站j關(guān)聯(lián)時(shí)，IoT設(shè)備i與基站j的上行鏈路SINRΓi j(t)可以通過(guò)IoT設(shè)備i以及i周?chē)钠渌鸌oT設(shè)備的上行傳輸鏈路的準(zhǔn)靜態(tài)衰落信道增益預(yù)估得到.本文假設(shè)IoT設(shè)備只有在當(dāng)前上行鏈路SINRΓi j(t)大于目標(biāo)SINRγi j時(shí)才能與相應(yīng)的基站建立關(guān)聯(lián).對(duì)于給定的IoT設(shè)備i的上行鏈路SINRΓi j(t)，如果不等式Γi j(t)≥γi j成立，本文將IoT設(shè)備i與基站j的上傳鏈路的速度定義為[19,22]

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

其中,B為鏈路帶寬.

對(duì)于IoT設(shè)備的傳輸模型，有約束條件：

(1)

(2)

(3)

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

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

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

2.2 邊緣服務(wù)器模型

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

(4)

2.3 任務(wù)模型

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

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

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

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

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

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

(5)

yi(t)≤ri(t),

(6)

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

(7)

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

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

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

其中,ci(t) min (vi/ρ,Li(t))表示虛擬機(jī)i在一個(gè)時(shí)間片內(nèi)處理的任務(wù)量.

2.4 能耗模型

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

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

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

Ej(t)=bj(t)Pj.

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

ai j(t)≤bj(t),

(8)

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

2.5 延 時(shí)

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

(9)

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

2.6 問(wèn)題形式化

本文通過(guò)對(duì)IoT設(shè)備任務(wù)、基站資源以及邊緣服務(wù)器資源的分配，旨在最小化系統(tǒng)整體的能量開(kāi)銷(xiāo)，同時(shí)從長(zhǎng)遠(yuǎn)角度滿足應(yīng)用的平均延時(shí).本文制定出優(yōu)化問(wèn)題：

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

3 算法設(shè)計(jì)

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

3.1 問(wèn)題轉(zhuǎn)化

為了滿足應(yīng)用延時(shí)的約束條件，本文引入虛隊(duì)列B：

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

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

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

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

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

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

因?yàn)樾碌哪繕?biāo)函數(shù)包含難以解決的二次項(xiàng)，所以本文將在最小化引理1中給出目標(biāo)函數(shù)的上限(即下面引理1中式(10)的右邊).

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

(10)

其中:

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

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

根據(jù)B(t)的更新規(guī)則以及事實(shí)([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))可以得到:

整理得到:

其中:

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

其中:

證畢.

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

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

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

3.2 JOSA算法

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

1) 找到每個(gè)IoT設(shè)備中的任務(wù)隊(duì)列的最佳工作負(fù)載分配、IoT設(shè)備-基站關(guān)聯(lián)以及基站睡眠調(diào)度：

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

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

s.t. 式(4)成立.

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

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

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

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

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

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

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

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

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

通過(guò)給定b(t)，x(t)和y(t)，P4轉(zhuǎn)化為問(wèn)題P5.

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

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

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

通過(guò)引入拉格朗日乘子θ和φ，可以得到P6的對(duì)偶問(wèn)題Dual-P6.

其中:

(11)

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

(12)

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

通過(guò)給定θ,φ,b(t)和y(t)，最大化式(11)是一個(gè)標(biāo)準(zhǔn)的LP問(wèn)題，可以表示為

P7:g(θ,φ)

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

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

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

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

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

P8可以通過(guò)次梯度法求解:

(13)

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

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

問(wèn)題P9是一個(gè)標(biāo)準(zhǔn)的LP問(wèn)題，可以通過(guò)單純形法等算法有效地進(jìn)行求解.

算法1. SlotCtrl算法.

輸入：框架中所有隊(duì)列的剩余量Θ(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的目標(biāo)函數(shù)最大值未收斂)；

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

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

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

4) SlotCtrl算法分析

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

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

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

證明. 為了分析P7的性質(zhì)，本文定義一個(gè)新向量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改寫(xiě)為標(biāo)準(zhǔn)形式:

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

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

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

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

其中,Wj∈M是m×n的矩陣，其第j行元素全為1，其余元素全為0；Ij∈M是n×n的單位矩陣.令Gk為約束矩陣A的任意k×k的子方陣，det(Gk)為Gk的行列式的值.當(dāng)k=1時(shí)，det(Gk)={0,1}.當(dāng)k≥2時(shí)，會(huì)有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個(gè)元素為1，其中一個(gè)來(lái)自Wj,另一個(gè)來(lái)自Ij.由于Wj和Ij中元素1的個(gè)數(shù)相等，因此可以通過(guò)變化使Gk的一行全為0.因此det(Gk)=0.

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

證畢.

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

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

對(duì)于b(t)，根據(jù)約束式(8)，即ai j(t) ≤bj(t)，如果存在任意i使得ai j(t)=1，則bj(t)=1.而如果?i∈N，ai j(t)=0，則相應(yīng)的bj(t)=0.這是因?yàn)镻4的目標(biāo)函數(shù)中bj(t)的系數(shù)σj(t)是非負(fù)的.

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

證畢.

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

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

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

通過(guò)引入拉格朗日乘子η，可以得到P10的對(duì)偶問(wèn)題Dual-P10.

其中:

(14)

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

其中,τ為每次迭代的步長(zhǎng)，iter為迭代次數(shù).通過(guò)給定η，最大化式(14)是一個(gè)標(biāo)準(zhǔn)的LP問(wèn)題，可以表示為

P11:g′(η)，

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

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

3.5 性能分析

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

定理1. 對(duì)于任意IoT設(shè)備i，假設(shè)平均工作負(fù)載到來(lái)量λi嚴(yán)格在系統(tǒng)處理能力范圍內(nèi)(例如λi+ε≤Ω)，那么可以通過(guò)推導(dǎo)得到:

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

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

通過(guò)對(duì)不等式兩邊取期望并對(duì)t=0,1,2,…,T-1進(jìn)行累加，可以得到:

(15)

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

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

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

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

證畢.

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

4 仿真評(píng)估

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

4.1 仿真結(jié)果

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

[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