鄧 宇，趙軍輝，2，張青苗

1.華東交通大學(xué) 信息工程學(xué)院，南昌 330013

2.北京交通大學(xué) 電子信息工程學(xué)院，北京 100044

隨著5G 無(wú)線通信技術(shù)[1]的迅猛發(fā)展與物聯(lián)網(wǎng)（Internet of things，IoT）的規(guī)模性部署，通信網(wǎng)絡(luò)的傳輸速率[2]、接入密度[3]、頻譜效率[4]等都得到了極大的提升，各種IoT終端設(shè)備的數(shù)量和數(shù)據(jù)量呈現(xiàn)出爆炸式的增長(zhǎng)，也涌現(xiàn)出許多計(jì)算密集型應(yīng)用，如增強(qiáng)現(xiàn)實(shí)、虛擬現(xiàn)實(shí)[5]和智慧交通[6-7]等。與此同時(shí)，由于IoT 設(shè)備的計(jì)算、存儲(chǔ)能力以及電池技術(shù)的限制，執(zhí)行高能耗任務(wù)并實(shí)時(shí)處理應(yīng)用數(shù)據(jù)成為了一個(gè)巨大的挑戰(zhàn)。云計(jì)算[8]的出現(xiàn)很好地解決了終端設(shè)備計(jì)算能力不足和電量有限等問(wèn)題，用戶設(shè)備可通過(guò)將計(jì)算任務(wù)卸載至遠(yuǎn)程云服務(wù)器進(jìn)行計(jì)算，從而大大提升任務(wù)的計(jì)算時(shí)間和設(shè)備的運(yùn)行效率。然而，由于云服務(wù)器位置較遠(yuǎn)且部署集中，將任務(wù)數(shù)據(jù)上傳至云服務(wù)器的通信過(guò)程中需要較高的傳輸時(shí)延，無(wú)法滿足一些時(shí)延敏感性較高的實(shí)時(shí)任務(wù)的要求[9]。

為了解決上述問(wèn)題，多接入邊緣計(jì)算（multi-access edge computing，MEC）技術(shù)應(yīng)運(yùn)而生。MEC 技術(shù)通過(guò)將任務(wù)從資源受限的IoT 設(shè)備轉(zhuǎn)移到功能強(qiáng)大且部署于網(wǎng)絡(luò)邊緣側(cè)的邊緣服務(wù)器（edge server，ES），可以為資源受限的IoT 設(shè)備提供實(shí)時(shí)、動(dòng)態(tài)的數(shù)據(jù)處理能力，減少總體執(zhí)行時(shí)延和能耗，增強(qiáng)系統(tǒng)通信的可靠性[10-11]。因此，MEC技術(shù)已經(jīng)成為IoT系統(tǒng)研究中一個(gè)活躍的研究領(lǐng)域。目前對(duì)于MEC的研究主要集中于多邊緣節(jié)點(diǎn)（edge nodes，ENs）部署策略和卸載策略。在ENs 部署策略方面，2018 年，文獻(xiàn)[12]提出了扁平式部署ENs 網(wǎng)絡(luò)，即在邊緣系統(tǒng)中所有邊緣云與ENs 同地的網(wǎng)絡(luò)架構(gòu)。2019年，文獻(xiàn)[13]提出面向復(fù)雜性較高的多路訪問(wèn)邊緣網(wǎng)絡(luò)的垂直式ENs 部署，即邊緣云與ENs 異地，用戶依據(jù)計(jì)算資源的利用率和任務(wù)分類選擇性地將計(jì)算任務(wù)通過(guò)不同層級(jí)的ENs 卸載至ES，降低總體傳輸能耗。在邊緣卸載策略方面，目前研究主要為通過(guò)不同的任務(wù)派發(fā)和調(diào)度方式，提高任務(wù)計(jì)算的時(shí)延或能耗特性。文獻(xiàn)[14]考慮了MEC 網(wǎng)絡(luò)中的流量分集和無(wú)線分集，對(duì)多路訪問(wèn)邊緣節(jié)點(diǎn)的不同部署方式進(jìn)行了時(shí)延分析和能耗分析。文獻(xiàn)[15]針對(duì)計(jì)算資源不足而導(dǎo)致MEC 服務(wù)器無(wú)法滿足需求的現(xiàn)實(shí)問(wèn)題，提出了移動(dòng)場(chǎng)景的計(jì)算資源分配方案，并設(shè)計(jì)了一種分布式資源分配算法以提高系統(tǒng)效用和計(jì)算時(shí)間。在文獻(xiàn)[16-17]中，研究了在保證信道分配公平的情況下最大提升MEC系統(tǒng)吞吐量的問(wèn)題，考慮了任務(wù)之間的相互依賴關(guān)系對(duì)任務(wù)卸載時(shí)延的影響，提出了基于協(xié)調(diào)算法的卸載策略以使得系統(tǒng)時(shí)延最低。文獻(xiàn)[18]將用戶服務(wù)質(zhì)量作為邊緣網(wǎng)絡(luò)有效性的重要評(píng)價(jià)指標(biāo)，通過(guò)一種在線學(xué)習(xí)方法盡可能地提升了邊緣系統(tǒng)能效。文獻(xiàn)[19]提出在移動(dòng)場(chǎng)景下協(xié)同優(yōu)化邊緣節(jié)點(diǎn)之間的服務(wù)緩存決策和資源分配，大大節(jié)省了重新配置服務(wù)的成本，提高了通信資源的利用效率。文獻(xiàn)[20]首次提出了在ENs所占用計(jì)算資源不相同的情況下，采用多級(jí)ENs卸載策略能夠極大實(shí)現(xiàn)傳輸鏈路復(fù)用，提高傳輸能效。

上述的研究均取得了一定的成果，但還存在著一些不足之處：一方面，現(xiàn)有的研究對(duì)于計(jì)算資源及信道資源聯(lián)合優(yōu)化問(wèn)題還考慮的不夠充分；另一方面，對(duì)于異構(gòu)資源，大多數(shù)研究采用平坦式邊緣網(wǎng)絡(luò)架構(gòu)進(jìn)行處理，對(duì)于多層級(jí)邊緣網(wǎng)絡(luò)的性能表現(xiàn)的研究仍尚少。本文在IoT場(chǎng)景下，綜合考慮IoT設(shè)備的時(shí)延約束特性、邊緣節(jié)點(diǎn)的異構(gòu)資源、多路訪問(wèn)邊緣網(wǎng)絡(luò)的無(wú)線干擾三個(gè)方面的因素，研究由多個(gè)設(shè)備及兩級(jí)邊緣節(jié)點(diǎn)構(gòu)成的IoT系統(tǒng)中多計(jì)算任務(wù)卸載策略。主要?jiǎng)?chuàng)新點(diǎn)如下：

（1）提出了一種具有異構(gòu)資源的二級(jí)ENs網(wǎng)絡(luò)；

（2）提出了一種計(jì)算資源及信道資源聯(lián)合優(yōu)化的最優(yōu)能耗卸載策略算法（optimal energy consumption algorithm，OECA）。

1 系統(tǒng)模型

本文設(shè)計(jì)的兩級(jí)節(jié)點(diǎn)MEC 網(wǎng)絡(luò)系統(tǒng)模型如圖1 所示?？紤]IoT 節(jié)點(diǎn)下的一組IoT 設(shè)備，每個(gè)設(shè)備產(chǎn)生一個(gè)計(jì)算任務(wù)，記任務(wù)集為N={ }1,2,…,i,…,n，每一任務(wù)需要在延遲約束tmaxi內(nèi)完成，且不同設(shè)備之間是異構(gòu)的。對(duì)于設(shè)備而言，可選擇兩種卸載策略來(lái)完成計(jì)算任務(wù)：在本地執(zhí)行或卸載到ES。在MEC 網(wǎng)絡(luò)中，存在一級(jí)邊緣節(jié)點(diǎn)EN1和二級(jí)邊緣節(jié)點(diǎn)EN2，每個(gè)邊緣節(jié)點(diǎn)具有若干信道，記作K={ }1,2,…,k,…,λ，帶寬均為B?？紤]到IoT設(shè)備僅配備一個(gè)無(wú)線電設(shè)備，在任務(wù)執(zhí)行過(guò)程中，IoT 設(shè)備只能選擇一個(gè)EN 來(lái)將計(jì)算任務(wù)卸載到ES。為了提高頻譜復(fù)用效率，EN1與EN2在相同的頻帶中運(yùn)行，且其二者之間存在回程鏈路。由于回程鏈路與其他基礎(chǔ)通信架構(gòu)共享，其功耗可以忽略不計(jì)，回程的時(shí)延受到時(shí)延系數(shù)γ控制，系統(tǒng)模型如圖1所示。

圖1 兩級(jí)MEC網(wǎng)絡(luò)系統(tǒng)模型Fig.1 Two-level MEC network system model

2 問(wèn)題描述

本文旨在研究面向IoT應(yīng)用的MEC能耗效率問(wèn)題，以來(lái)自不同設(shè)備的計(jì)算任務(wù)為對(duì)象，制定一種優(yōu)化的計(jì)算任務(wù)策略，使得系統(tǒng)在滿足時(shí)延約束的前提下能耗最小化。為進(jìn)一步分析系統(tǒng)總體能耗并研究多IoT 設(shè)備的卸載決策及ENs的任務(wù)調(diào)度對(duì)系統(tǒng)能耗的影響，將面向物聯(lián)網(wǎng)應(yīng)用的MEC能耗效率分解為以下兩個(gè)問(wèn)題。

（1）任務(wù)放置問(wèn)題：根據(jù)時(shí)延約束與能耗特性，綜合考慮全局IoT 設(shè)備任務(wù)總能耗，對(duì)i∈N決定是在本地執(zhí)行該任務(wù)還是將任務(wù)卸載到ES。

（2）資源調(diào)度問(wèn)題：在系統(tǒng)中，IoT 節(jié)點(diǎn)計(jì)算任務(wù)集總是由一系列由不同設(shè)備上傳的任務(wù)組成，這些任務(wù)通常是異構(gòu)的，需要對(duì)所有任務(wù)確定其卸載優(yōu)先級(jí)順序。主要原因一是系統(tǒng)的頻帶資源有限，應(yīng)當(dāng)把增益較強(qiáng)的信道分配給優(yōu)先級(jí)更高的任務(wù)，以使系統(tǒng)整體任務(wù)傳輸過(guò)程中的總能耗更??；二是改變?nèi)蝿?wù)的執(zhí)行順序也會(huì)影響系統(tǒng)的總能耗。

在任務(wù)卸載到EN1的情況下，系統(tǒng)的全局時(shí)延，即系統(tǒng)中所有用戶的時(shí)延之和，可表示為：

其中約束C1～C3 保證了任務(wù)i的通過(guò)計(jì)算方式的時(shí)延要求，tmax表示該用戶自身的時(shí)延約束；C4～C6 表示任務(wù)i只能選擇一種計(jì)算方式；C7 表示必須為每個(gè)任務(wù)分配一種計(jì)算方式；C8 表示信道只能分配給一個(gè)設(shè)備。

在卸載過(guò)程中，將{ai,j,k}視作表示設(shè)備卸載方式選擇的指示器，優(yōu)化問(wèn)題（15）的解用二進(jìn)制集合{ai,j,k}表示，{ai,j,k}的影響因素有任務(wù)的時(shí)延約束、任務(wù)傳輸?shù)臒o(wú)線干擾、用戶所選計(jì)算方式的能耗屬性和任務(wù)所屬信道的無(wú)線資源。

定義 問(wèn)題（15）是NP-hard問(wèn)題，具有多項(xiàng)式復(fù)雜性。

證明 選定特殊情況，將系統(tǒng)模型簡(jiǎn)化為只有一個(gè)EN且各無(wú)線信道具有相同信干噪比（signal to interference plus noise ratio，SINR）設(shè)xi={ }0,1 表示任務(wù)i是否被卸載到ES，xi=0 表示任務(wù)未卸載，xi=1 表示任務(wù)卸載，則問(wèn)題（15）可簡(jiǎn)化為：

3 最優(yōu)能耗邊緣卸載策略

為了有效求解優(yōu)化問(wèn)題（12），本章提出了針對(duì)多聯(lián)合優(yōu)化最優(yōu)能耗算法（optimal energy consumption algorithm，OECA），OECA 主要分為3 個(gè)階段：設(shè)備分類、設(shè)備優(yōu)先級(jí)劃分、無(wú)線資源分配。

3.1 設(shè)備分類算法

按照任務(wù)計(jì)算的時(shí)延約束和能耗特性，將IoT設(shè)備分為兩類：第一類設(shè)備定義為將任務(wù)放置在本地的設(shè)備，即任務(wù)被放置在本地執(zhí)行；第二類設(shè)備定義為將任務(wù)卸載至ES執(zhí)行的設(shè)備，這類設(shè)備需要符合兩個(gè)條件：

（1）本地CPU 的計(jì)算能力不足以在時(shí)延約束內(nèi)完成任務(wù)執(zhí)行；

（2）本地CPU 在執(zhí)行任務(wù)時(shí)延的內(nèi)能耗高于ES的CPU。

3.2 設(shè)備優(yōu)先級(jí)劃分

對(duì)于{?O}中的設(shè)備集，由于無(wú)線信道的容量有限、設(shè)備之間存在無(wú)線干擾以及任務(wù)之間的異構(gòu)特性，在為其分配無(wú)線信道資源之前有必要對(duì)其優(yōu)先級(jí)進(jìn)行劃分，即優(yōu)先級(jí)越高的設(shè)備，越優(yōu)先選擇信道資源。設(shè)備優(yōu)先級(jí)的主要影響因素有延遲約束、無(wú)線資源以及本地計(jì)算和邊緣卸載計(jì)算之間的計(jì)算能耗差。設(shè)備優(yōu)先級(jí)分配過(guò)程如下所示。

其中β1、β2、β3為權(quán)重系數(shù)，滿足β1+β2+β3=1。

式（27）為i的多項(xiàng)加權(quán)表達(dá)式，其中第一項(xiàng)表示設(shè)備i的時(shí)延約束的嚴(yán)格程度，時(shí)延約束嚴(yán)格的設(shè)備應(yīng)獲得更高的權(quán)重；第二項(xiàng)表示設(shè)備所處的信道環(huán)境，應(yīng)優(yōu)先為系統(tǒng)中信道環(huán)境較差的設(shè)備分配信道資源；第三項(xiàng)表示設(shè)備選擇不同的任務(wù)計(jì)算方式之間的能耗差值，若設(shè)備選擇邊緣卸載能夠節(jié)約較高的能量，則設(shè)備應(yīng)獲得更高權(quán)重。φi的值與設(shè)備的優(yōu)先程度成正比。

3.3 無(wú)線資源分配

基于所得權(quán)重序列{φi}可得設(shè)備的優(yōu)先級(jí)順序集合，由此可執(zhí)行OECA為設(shè)備分配無(wú)線信道資源。能耗表現(xiàn)是影響設(shè)備信道選擇的決定性因素，但在設(shè)備進(jìn)行無(wú)線信道選擇時(shí)因優(yōu)先選擇SINR 較高的信道，其原因是：（1）SINR 直接影響任務(wù)運(yùn)算的時(shí)延，且不同信道之間的傳輸功率相等；（2）以SINR為選擇無(wú)線信道指標(biāo)能夠有效縮短算法迭代時(shí)間。無(wú)線信道分配的具體步驟如下：

4 仿真結(jié)果及分析

本章通過(guò)仿真結(jié)果評(píng)估OECA 的性能。設(shè)定EN1和EN2覆蓋面積為100 m×100 m的區(qū)域，每個(gè)基站具有K=50 條信道，同屬一個(gè)基站的信道之間兩兩正交。區(qū)域內(nèi)存在n=100 個(gè)用戶，每個(gè)用戶即為1 個(gè)IoT 設(shè)備，每個(gè)IoT設(shè)備根據(jù)主流應(yīng)用程序（例如面部識(shí)別應(yīng)用程序、視頻導(dǎo)航應(yīng)用程序等）產(chǎn)生一個(gè)計(jì)算任務(wù)需求。IoT 設(shè)備產(chǎn)生的計(jì)算任務(wù)大小在[500 KB，1 500 KB]間均勻分布，其所需本地計(jì)算能力在[1.5 GHz，2.0 GHz]間均勻分布，所需的CPU 計(jì)算能力在[0.2 GHz，0.3 GHz]間均勻分布，初始時(shí)延系數(shù)γ=1×10-4s/KB。具體的實(shí)驗(yàn)參數(shù)如表1所示。在實(shí)驗(yàn)中，將所提出的二級(jí)邊緣節(jié)點(diǎn)網(wǎng)絡(luò)模型與平坦式邊緣網(wǎng)絡(luò)模型[9]相對(duì)比，將所提出的OECA 算法分別與無(wú)卸載機(jī)制計(jì)算方案、基于有向無(wú)環(huán)圖的卸載算法（directed acyclic graph algorithm，DAGA）[16-17]進(jìn)行對(duì)比。

表1 實(shí)驗(yàn)參數(shù)Table 1 Experimental parameters

如圖2 為4 種不同的任務(wù)計(jì)算方式的能耗表現(xiàn)對(duì)比。隨著用戶數(shù)量的增加，不同方案下的系統(tǒng)能耗都逐漸增加，無(wú)卸載機(jī)制的系統(tǒng)的能耗要明顯高于其他3種方案，OECA 算法的能耗最低。當(dāng)系統(tǒng)用戶總數(shù)較少時(shí)，各計(jì)算方案能耗之間差異較小。當(dāng)系統(tǒng)用戶總數(shù)n=60 時(shí)，二級(jí)邊緣網(wǎng)絡(luò)OECA 的能耗為20.9 J，是無(wú)卸載機(jī)制計(jì)算方案的56.3%。當(dāng)系統(tǒng)用戶總數(shù)n=100 時(shí)，在平坦式邊緣網(wǎng)絡(luò)模型下，OECA的能耗為42.7 J，對(duì)比DAGA 減少了8.2 個(gè)百分點(diǎn)；在二級(jí)邊緣網(wǎng)絡(luò)模型下，OECA 的能耗為37.1 J，對(duì)比平坦式邊緣網(wǎng)絡(luò)OECA 能耗減少了13.1個(gè)百分點(diǎn)。

圖2 不同任務(wù)執(zhí)行方式下能耗對(duì)比Fig.2 Comparison of energy consumption under different task execution methods

與DAGA算法對(duì)比，系統(tǒng)可卸載用戶數(shù)量的對(duì)比情況如圖3所示。隨著系統(tǒng)用戶總數(shù)的變化，兩種算法的可卸載用戶數(shù)量都逐漸增加，當(dāng)系統(tǒng)用戶數(shù)量n=100時(shí)，二級(jí)邊緣網(wǎng)絡(luò)OECA 的可卸載用戶數(shù)為71，相比DADA 算法高出18.3 個(gè)百分點(diǎn)。在系統(tǒng)用戶數(shù)量較多的情況下，可卸載用戶數(shù)的增長(zhǎng)速度逐漸平緩，這說(shuō)明系統(tǒng)逐漸達(dá)到容量上限。

圖3 系統(tǒng)可卸載用戶數(shù)量對(duì)比Fig.3 Comparison of system offloading user numbers

如圖4 揭示了回程鏈路時(shí)延系數(shù)對(duì)系統(tǒng)能耗及二級(jí)邊緣節(jié)點(diǎn)下卸載用戶數(shù)量的影響。當(dāng)回程鏈路時(shí)延系數(shù)γ較大時(shí)，兩級(jí)ENs 之間的鏈路時(shí)延約束更加嚴(yán)格，此時(shí)二級(jí)邊緣節(jié)點(diǎn)下的用戶將可能無(wú)法滿足自身時(shí)延需求，因此轉(zhuǎn)為連接一級(jí)EN 執(zhí)行卸載。與此同時(shí)，對(duì)于這些用戶來(lái)說(shuō)，通過(guò)一級(jí)邊緣節(jié)點(diǎn)進(jìn)行傳輸需要更高的傳輸能耗，因此系統(tǒng)能耗隨著γ的增加逐漸增大。

圖4 不同γ 時(shí)系統(tǒng)能耗和卸載用戶數(shù)量Fig.4 System energy consumption and unloaded user numbers under different γ

如圖5 揭示了不同用戶數(shù)量與不同卸載策略下ES的CPU 占用情況。隨著用戶數(shù)量的增加，兩種卸載策略所對(duì)應(yīng)的CPU占用都在不斷增加。當(dāng)系統(tǒng)中的用戶數(shù)量n>90 時(shí)，服務(wù)器CPU占用幾乎不隨設(shè)備數(shù)量而增長(zhǎng)，這是由于用戶數(shù)量逐漸趨近MEC系統(tǒng)的容納上限，系統(tǒng)趨于飽和。當(dāng)用戶數(shù)量n=100 時(shí)，二級(jí)邊緣網(wǎng)絡(luò)DAGA 的CPU 占用為65%，二級(jí)邊緣網(wǎng)絡(luò)OECA 的CPU占用為57.8%，對(duì)比DAGA減少7.2個(gè)百分點(diǎn)。

圖5 CPU占用情況Fig.5 CPU usage

如圖6 揭示了時(shí)延約束tmax的變化對(duì)兩種不同的網(wǎng)絡(luò)模型下的MEC系統(tǒng)全局能耗的影響。對(duì)比平坦式邊緣網(wǎng)絡(luò)，二級(jí)邊緣網(wǎng)絡(luò)的能效更優(yōu)，在tmax=50 ms時(shí)二者的能效差達(dá)到40.14 W。當(dāng)tmax<80 ms 時(shí)，兩種網(wǎng)絡(luò)模型的MEC 系統(tǒng)能耗都隨著tmax的減小大幅增加。這是由于此時(shí)系統(tǒng)的時(shí)延敏感性大幅提高，即系統(tǒng)中的用戶在進(jìn)行應(yīng)用任務(wù)計(jì)算時(shí)的時(shí)延要求更為嚴(yán)格，更多的用戶選擇通過(guò)ES進(jìn)行邊緣卸載以滿足自身應(yīng)用任務(wù)的時(shí)延要求。隨著tmax的逐漸增大，用戶自身的計(jì)算任務(wù)時(shí)延要求降低，更多的用戶被移出ES 卸載序列以降低MEC系統(tǒng)能耗。

圖6 不同tmax 時(shí)系統(tǒng)能耗對(duì)比Fig.6 Comparison of system energy consumption under different tmax

如圖7為不同時(shí)延約束tmax下，兩種不同的網(wǎng)絡(luò)模型下的MEC 系統(tǒng)中可卸載用戶數(shù)量的對(duì)比。與平坦式邊緣網(wǎng)絡(luò)相比，二級(jí)邊緣網(wǎng)絡(luò)所能容納的邊緣卸載用戶更多，即網(wǎng)絡(luò)吞吐量更大。當(dāng)tmax=163 ms時(shí)二者相差達(dá)到最大值25%。隨著tmax逐漸增大，系統(tǒng)中可卸載用戶數(shù)量逐漸下降，這是由于此時(shí)用戶自身計(jì)算任務(wù)的時(shí)延要求逐漸寬松，更多的用戶傾向于在自身IoT 設(shè)備上計(jì)算應(yīng)用任務(wù)。當(dāng)tmax<67 ms 時(shí)，隨著tmax的增大，MEC 系統(tǒng)可卸載用戶數(shù)的下降趨勢(shì)較為平緩，主要原因是在時(shí)延約束較為嚴(yán)苛的情況下，絕大部分用戶依然需要依賴ES 所提供的計(jì)算能力進(jìn)行任務(wù)計(jì)算。

圖7 不同tmax 時(shí)可卸載用戶數(shù)對(duì)比Fig.7 Comparison of offloading user numbers under different tmax

5 結(jié)語(yǔ)

本文將IoT 場(chǎng)景下用戶應(yīng)用任務(wù)卸載問(wèn)題建模為二級(jí)邊緣節(jié)點(diǎn)下的多用戶邊緣卸載策略選擇，為了降低IoT 設(shè)備進(jìn)行邊緣卸載過(guò)程中的能耗，在滿足IoT 時(shí)延約束的前提下，通過(guò)優(yōu)先級(jí)函數(shù)平衡卸載時(shí)延與能耗，并提出OECA 卸載策略。仿真結(jié)果表明，對(duì)比基于DAG的算法，所提方案可提升MEC網(wǎng)絡(luò)容量18.3個(gè)百分點(diǎn)，縮減能耗13.1 個(gè)百分點(diǎn)，有效提升了通信過(guò)程中的能效。下一步工作將考慮在多任務(wù)場(chǎng)景下，針對(duì)多級(jí)邊緣網(wǎng)絡(luò)的并行任務(wù)放置問(wèn)題研究卸載策略，并采用啟發(fā)式算法進(jìn)行無(wú)線資源分配，以進(jìn)一步分析MEC 系統(tǒng)的最優(yōu)能效卸載方案。