無線供能移動邊緣網(wǎng)絡(luò)中計算時延最小化資源分配方法研究

葉迎暉 施麗琴 盧光躍

(西安郵電大學(xué)陜西省信息通信網(wǎng)絡(luò)及安全重點(diǎn)實(shí)驗(yàn)室 西安 710121)

1 引言

泛在物聯(lián)被認(rèn)為是下一代無線通信網(wǎng)的關(guān)鍵驅(qū)動力[1]，而提供智能服務(wù)與決策是泛在物聯(lián)的主要目的之一，這要求物聯(lián)網(wǎng)節(jié)點(diǎn)具備快速處理數(shù)據(jù)的能力。由于制造成本的限制，物聯(lián)網(wǎng)節(jié)點(diǎn)自身的處理器能力往往不強(qiáng)(即計算能力受限)，無法實(shí)現(xiàn)高效數(shù)據(jù)處理。移動邊緣計算(Mobile Edge Computing, MEC)可將物聯(lián)網(wǎng)節(jié)點(diǎn)數(shù)據(jù)卸載至計算能力較強(qiáng)的MEC服務(wù)器，從而突破節(jié)點(diǎn)計算能力受限問題[2]，但數(shù)據(jù)處理及任務(wù)卸載將會消耗節(jié)點(diǎn)大量的電池能量，從而縮短節(jié)點(diǎn)工作時長。由于物聯(lián)網(wǎng)節(jié)點(diǎn)具有數(shù)量多、部署無規(guī)律等特點(diǎn)，為物聯(lián)網(wǎng)節(jié)點(diǎn)更換電池或?qū)⑵浣尤腚娋W(wǎng)將會產(chǎn)生較大的開銷。因此，如何兼顧物聯(lián)網(wǎng)的數(shù)據(jù)處理能力以及能量供應(yīng)對實(shí)現(xiàn)泛在物聯(lián)顯得尤為重要。在這一背景下，無線供能MEC應(yīng)運(yùn)而生，其核心思想是在物聯(lián)網(wǎng)節(jié)點(diǎn)周圍部署專用能量站(Power Beacon, PB)和MEC服務(wù)器來實(shí)現(xiàn)按需供能與計算增強(qiáng)[3]，并通過權(quán)衡能量供應(yīng)、計算資源以及通信資源來設(shè)計高效資源分配方法，從而為解決物聯(lián)網(wǎng)節(jié)點(diǎn)計算能力與能量雙重受限問題提供理論支持。

文獻(xiàn)[3]考慮了一個單節(jié)點(diǎn)的無線供能MEC網(wǎng)絡(luò)，并在物聯(lián)網(wǎng)節(jié)點(diǎn)能量因果以及計算時延等約束下，通過聯(lián)合優(yōu)化時隙資源和節(jié)點(diǎn)計算頻率來最大化任務(wù)成功計算概率。隨后，文獻(xiàn)[4]將單節(jié)點(diǎn)的無線供能MEC網(wǎng)絡(luò)[3]拓展到多個物聯(lián)網(wǎng)節(jié)點(diǎn)共存的場景，并設(shè)計了加權(quán)計算比特數(shù)之和最大的資源分配方法。文獻(xiàn)[3]和文獻(xiàn)[4]均假設(shè)節(jié)點(diǎn)任務(wù)比特數(shù)不可分割，因此其所設(shè)計的資源分配方法是基于二元卸載策略。當(dāng)節(jié)點(diǎn)任務(wù)比特數(shù)可被任意分割時，文獻(xiàn)[5]考慮了一個部分卸載策略，并在滿足任務(wù)計算需求前提下，通過聯(lián)合優(yōu)化PB的能量波束矩陣、計算頻率以及卸載比特數(shù)來最小化PB和MEC服務(wù)器的能量消耗?？紤]到無線供能MEC的網(wǎng)絡(luò)性能受限于無線能量傳輸效率這一客觀因素，而PB與物聯(lián)網(wǎng)節(jié)點(diǎn)有可能不存在可視路徑，文獻(xiàn)[6]將無人機(jī)引入到無線供能MEC網(wǎng)絡(luò)，利用空地可視鏈路提高無線能量傳輸效率，并依次在二元卸載策略和部分卸載策略下提出計算比特數(shù)之和最大的多維聯(lián)合資源分配方法。不同于上述所考慮的無線供能MEC網(wǎng)絡(luò)，文獻(xiàn)[7]和文獻(xiàn)[8]通過部署中繼節(jié)點(diǎn)來增強(qiáng)無線供能MEC的性能。具體來說，文獻(xiàn)[7]在給定任務(wù)計算比特數(shù)約束下提出一種PB和MEC服務(wù)器能量最小化的多維資源分配方法，而文獻(xiàn)[8]則是將無人機(jī)當(dāng)作移動中繼節(jié)點(diǎn)，并提出加權(quán)計算比特數(shù)之和最大的多維資源分配方法。不同于上述工作所考慮的性能指標(biāo)，文獻(xiàn)[9]提出了計算能效這一性能指標(biāo)，并通過聯(lián)合優(yōu)化PB工作時長與發(fā)射功率、節(jié)點(diǎn)計算頻率、卸載時間以及所采用的發(fā)射功率設(shè)計了一種用戶計算能效最大的資源分配方法。考慮到用戶計算能效并未考慮PB和MEC服務(wù)器的能耗，文獻(xiàn)[10]研究了一種系統(tǒng)計算能效最大的資源分配方法，并揭示了用戶能效是系統(tǒng)能效的一種特殊情況。隨后，文獻(xiàn)[11]將文獻(xiàn)[10]的工作拓展到了基于非正交多址的無線供能MEC網(wǎng)絡(luò)中，并通過聯(lián)合優(yōu)化通信資源、計算資源以及能量資源來最大化系統(tǒng)最大能效。

綜上所述，面向無線供能MEC設(shè)計高效資源分配方法已經(jīng)受到了國內(nèi)外學(xué)者的廣泛關(guān)注與研究，但已有工作[3–11]均是在給定時延要求前提下面向不同的優(yōu)化目標(biāo)(如計算比特數(shù)等)設(shè)計資源分配方法。計算時延是MEC的關(guān)鍵性能指標(biāo)之一。雖然計算時延最小化在電池供能的MEC網(wǎng)絡(luò)得到了廣泛的研究與關(guān)注[11–14]，但截至目前，還未有相關(guān)工作面向無線供能MEC網(wǎng)絡(luò)研究計算時延最小化的資源分配方法。受此啟發(fā)，本文考慮多個物聯(lián)網(wǎng)節(jié)點(diǎn)共存的無線供能MEC網(wǎng)絡(luò)，在給定任務(wù)比特數(shù)和物聯(lián)網(wǎng)節(jié)點(diǎn)能量因果關(guān)系的約束下，研究節(jié)點(diǎn)計算時延之和最小的多維資源分配方法。

本文的主要技術(shù)貢獻(xiàn)總結(jié)如下：

(1)在部分卸載策略基礎(chǔ)上，通過聯(lián)合優(yōu)化PB工作時長、物聯(lián)網(wǎng)節(jié)點(diǎn)任務(wù)分割系數(shù)、計算頻率以及發(fā)射功率，建立一個滿足物聯(lián)網(wǎng)節(jié)點(diǎn)能量因果約束的計算總時延最小化的多維資源分配問題。

(2)節(jié)點(diǎn)計算總時延是一個max-max函數(shù)且含有多個耦合變量，與此同時，能量因果約束中也存在優(yōu)化變量耦合這一情況，因此，所建的計算總時延最小化多維資源分配問題是一個高度非凸問題且使用已有凸優(yōu)化工具無法獲取該問題的最優(yōu)解。為求解所建的非凸優(yōu)化問題，本文通過引入輔助變量與松弛變量，將原問題轉(zhuǎn)化為一個形式更易處理的優(yōu)化問題，并通過分析轉(zhuǎn)換之后問題的結(jié)構(gòu)特性，提出一種基于二分法的迭代算法來獲取最優(yōu)解。此外，為縮小二分法的搜索范圍，本文還推導(dǎo)得到計算總時延的上界。最后，通過MATLAB實(shí)驗(yàn)驗(yàn)證了所提算法的正確性和優(yōu)越性。

本文其他部分組織如下：第2節(jié)給出了系統(tǒng)模型以及節(jié)點(diǎn)的工作流程；第3節(jié)建立了計算總時延最小化的多維資源分配問題，并針對該問題設(shè)計了一種迭代算法來獲取最小計算總時延；第4節(jié)對所提算法進(jìn)行了驗(yàn)證；最后一節(jié)總結(jié)了全文的工作。

2 系統(tǒng)模型

考慮一個圖1所示的無線供能MEC網(wǎng)絡(luò)。在PB和MEC服務(wù)器的幫助下，K個能量與計算能力雙重受限的物聯(lián)網(wǎng)節(jié)點(diǎn)需要在滿足能量因果關(guān)系等約束下快速處理給定的任務(wù)比特數(shù)Lk。假設(shè)物聯(lián)網(wǎng)節(jié)點(diǎn)采用部分卸載策略，即物聯(lián)網(wǎng)節(jié)點(diǎn)k通過一個任務(wù)分割系數(shù)δk(0≤δk ≤1 ) 將任務(wù)比特數(shù)Lk分成兩部分：一部分任務(wù)比特數(shù) ( 1?δk)Lk用于物聯(lián)網(wǎng)節(jié)點(diǎn)k的本地計算，而剩余任務(wù)比特數(shù)δkLk將會卸載至MEC服務(wù)器進(jìn)行計算。本文考慮準(zhǔn)靜態(tài)衰落信道，即信道增益在一個傳輸時隙內(nèi)保持不變。圖1所示的網(wǎng)絡(luò)可應(yīng)用于智慧車間，通過部署MEC服務(wù)器和PB來提高智慧車間傳感節(jié)點(diǎn)的計算能力與工作時長。假設(shè)物聯(lián)網(wǎng)節(jié)點(diǎn)的數(shù)據(jù)并非隨機(jī)到達(dá)且節(jié)點(diǎn)數(shù)據(jù)是時延敏感的，因此本文從短期優(yōu)化角度來設(shè)計資源分配方法。

圖1 無線供能MEC網(wǎng)絡(luò)

2.1 無線供能MEC網(wǎng)絡(luò)計算總時延

考慮一個圖2所示的時隙結(jié)構(gòu)圖。整個傳輸時隙包括3個階段：能量收集階段、數(shù)據(jù)卸載階段以及任務(wù)計算與下傳階段。假設(shè)每個物聯(lián)網(wǎng)節(jié)點(diǎn)都配置了能量收集電路、信息收發(fā)機(jī)以及任務(wù)計算電路，因此，在上述3個階段中，物聯(lián)網(wǎng)節(jié)點(diǎn)可同時進(jìn)行本地計算。

圖2 時隙結(jié)構(gòu)圖

在能量收集階段，PB以功率P0來廣播能量射頻信號xs，與此同時，K個物聯(lián)網(wǎng)節(jié)點(diǎn)從射頻信號xs中收集能量。因此，物聯(lián)網(wǎng)節(jié)點(diǎn)k在時隙t0內(nèi)所收集的能量可表示為

當(dāng)K個物聯(lián)網(wǎng)節(jié)點(diǎn)將自身數(shù)據(jù)上傳至MEC服務(wù)器之后，MEC服務(wù)器進(jìn)行計算并將結(jié)果返回。本文假設(shè)MEC服務(wù)器具有很強(qiáng)的計算能力以至于處理K個物聯(lián)網(wǎng)節(jié)點(diǎn)上傳數(shù)據(jù)所需的時間接近于0，同時，假設(shè)MEC服務(wù)器計算的結(jié)果很小，因此MEC服務(wù)器將計算結(jié)果返回給K個物聯(lián)網(wǎng)節(jié)點(diǎn)的時間也接近于0。需要指出的是，上述假設(shè)在MEC網(wǎng)絡(luò)[6–9]中被廣泛使用。

對于本地計算而言，物聯(lián)網(wǎng)節(jié)點(diǎn)k所需的時間可以表示為

其中，fk表示物聯(lián)網(wǎng)節(jié)點(diǎn)k所采用的計算頻率，Gk表示節(jié)點(diǎn)k計算一個比特所需要的CPU時鐘周期數(shù)。

基于上述分析，圖1所示的無線供能MEC網(wǎng)絡(luò)計算總時延可由物聯(lián)網(wǎng)節(jié)點(diǎn)的本地計算時間以及卸載任務(wù)所需時間決定，其數(shù)學(xué)表達(dá)式可以表示為

2.2 能量消耗

3 任務(wù)計算總時延最小化資源分配方法

3.1 優(yōu)化問題建立

本小節(jié)在物聯(lián)網(wǎng)節(jié)點(diǎn)能量因果關(guān)系等約束下，通過聯(lián)合優(yōu)化PB工作時長、任務(wù)分割系數(shù)、物聯(lián)網(wǎng)節(jié)點(diǎn)的計算頻率與發(fā)射功率來最小化任務(wù)計算總時延。因此，任務(wù)計算總時延最小化的優(yōu)化問題可表示為

3.2 優(yōu)化問題轉(zhuǎn)換與求解

由上述分析可知，若要解決原問題P0，就必須要對目標(biāo)函數(shù)式(7b)和能量因果約束式(7c)進(jìn)行等價轉(zhuǎn)換。為此，通過引入輔助變量以及松弛變量，對原問題進(jìn)行3次變換之后，得到了一個形式簡單且易處理的等價優(yōu)化問題。

其中，式(8c)和式(8d)是對輔助變量進(jìn)行松弛而得到的。需要指出的是，優(yōu)化問題P1達(dá)到最優(yōu)時，約束條件式(8c)和式(8d)中至少會存在一個等號成立。因此，優(yōu)化問題P1和原問題P0等價。在P1中，雖然目標(biāo)函數(shù)是一個線性函數(shù)，但其約束條件式(7b)、式(8c)和式(8d)均非凸。

為了處理這些非凸約束，首先引入如下引理。

引理1 構(gòu)建如下優(yōu)化問題：

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

本節(jié)將通過MATLAB來驗(yàn)證所提方案的優(yōu)越性以及所提基于二分法的迭代算法的有效性。如無特殊說明，本節(jié)采用如表1所列的參數(shù)[8–12]。在仿真中，本文采用來自文獻(xiàn)[15]的非線性能量收集模型，且非線性能量收集模型參數(shù)設(shè)置與文獻(xiàn)[15]保持一致。本文采用弗里斯傳輸公式去刻畫各物聯(lián)網(wǎng)節(jié)點(diǎn)與專用能量站及MEC服務(wù)器之間的信道增益，即hk=GpGh?2/(4πd0k)2,gk=GhGr?2/(4πd1k)2，其中?表示波長，Gp, Gh和Gr分別表示專用能量站、物聯(lián)網(wǎng)節(jié)點(diǎn)和MEC服務(wù)器上的天線增益。參考Powercast公司生產(chǎn)的能量收集電路和專用能量站，本文將專用能量站和網(wǎng)關(guān)的天線增益設(shè)置為6 dBi，每個用戶的天線增益設(shè)置為1.8 dBi。假設(shè)載波頻率為915 MHz。專用能量站與4個物聯(lián)網(wǎng)節(jié)點(diǎn)之間的距離依次設(shè)置為d01=d04=6.5 m 和d02=d03=6 m。MEC服務(wù)器與4個物聯(lián)網(wǎng)節(jié)點(diǎn)之間的距離分別設(shè)置為d11=d14=12 m以 及d12=d13=12.5 m。

表1 仿真參數(shù)

圖3描述了所提基于二分法的迭代算法(即算法1)所能完成任務(wù)計算總時延與迭代次數(shù)的關(guān)系圖。從圖3可以看出，所提迭代算法經(jīng)過8次迭代之后均能達(dá)到收斂狀態(tài)，這一現(xiàn)象表明本文所提算法具有快速收斂性且在實(shí)際中是計算有效的。其次，可以看出不同Lk下的任務(wù)計算總時延也不同，且較大的Lk將帶來較大的任務(wù)計算總時延。這是因?yàn)殡S著Lk的增大，物聯(lián)網(wǎng)節(jié)點(diǎn)需要進(jìn)行較長時間的能量收集、任務(wù)卸載以及本地計算來確保每個節(jié)點(diǎn)均能完成計算任務(wù)，從而增加了任務(wù)計算總時延。此外，我們還將所提資源分配方法得到的最優(yōu)值與通過窮搜方法得到的最優(yōu)值進(jìn)行了對比，發(fā)現(xiàn)所提資源分配方法最終收斂的值與窮搜得到的值是相等的，這也說明了所提資源分配方法的正確性。

圖3 所提基于二分法的迭代算法的迭代情況圖

圖4刻畫了6種方案下任務(wù)計算總時延隨PB發(fā)射功率P0變化的情況。在全部卸載方案中，每個物聯(lián)網(wǎng)節(jié)點(diǎn)將自身所需要計算的任務(wù)比特數(shù)全部卸載至MEC服務(wù)器而不進(jìn)行本地計算。本地計算方案中，每個物聯(lián)網(wǎng)節(jié)點(diǎn)只進(jìn)行本地計算而不進(jìn)行任務(wù)卸載。值得注意的是，本文所提方案、全部卸載方案、本地計算方案以及二元卸載方案均是通過相同的優(yōu)化目標(biāo)優(yōu)化得到的。當(dāng)節(jié)點(diǎn)采用全部卸載方案時，本文所考慮的網(wǎng)絡(luò)可退化為基于無線供能通信網(wǎng)絡(luò)，此時，采用基于無線供能通信網(wǎng)絡(luò)的時延最小化資源優(yōu)化方法[16]可以獲得該卸載方案的最優(yōu)解。本地計算方案可由引理2確定。文獻(xiàn)[4,9]對應(yīng)的時延是來自計算比特數(shù)與計算能效最大時對應(yīng)的時間(仿真中設(shè)置最大容忍時延為1.2 s)。在二元卸載方案中，每個物聯(lián)網(wǎng)節(jié)點(diǎn)要么全部進(jìn)行本地計算要么將任務(wù)全部卸載至MEC服務(wù)器。由圖可以看出，文獻(xiàn)[4,9]對應(yīng)的計算時延與PB發(fā)射功率無關(guān)，而其他4種方案下的計算時延均隨P0的增大而減小。其次，對于所提方案，當(dāng)P0較小時，節(jié)點(diǎn)傾向于進(jìn)行本地計算以降低任務(wù)計算總時延，而當(dāng)P0足夠大時，節(jié)點(diǎn)將全部的計算任務(wù)卸載至MEC服務(wù)器來取得更低的時延。這是因?yàn)殡S著P0的增大，各物聯(lián)網(wǎng)節(jié)點(diǎn)在保障收集到能量、卸載比特數(shù)和/或本地計算比特數(shù)的情況下縮短能量收集時間、任務(wù)卸載時間和/或本地計算時間，從而帶來任務(wù)計算總時延的降低。此外，我們可以發(fā)現(xiàn)，就任務(wù)計算總時延而言，本文所提方案總是優(yōu)于其他5種方案，從而進(jìn)一步驗(yàn)證了本文所提方案的優(yōu)越性。需要指出的是，隨著PB發(fā)射功率的增加，計算時延會逐漸收斂于某個常數(shù)。在圖4中，由于PB發(fā)射功率較小，并不能使得物聯(lián)網(wǎng)節(jié)點(diǎn)能量收集器工作在飽和狀態(tài)，因此上述曲線并未收斂于某個常數(shù)。

圖4 任務(wù)計算總時延與PB的發(fā)射功率的關(guān)系

5 結(jié)束語

面向無線供能MEC網(wǎng)絡(luò)，本文提出了一種計算總時延最小化的多維資源分配方法。首先，在部分卸載策略的基礎(chǔ)上，考慮物聯(lián)網(wǎng)節(jié)點(diǎn)能量因果關(guān)系，通過聯(lián)合優(yōu)化PB工作時長、物聯(lián)網(wǎng)節(jié)點(diǎn)任務(wù)分割系數(shù)、計算頻率以及發(fā)射功率建立了一個計算總時延最小化的優(yōu)化問題。其次，通過引入輔助變量與松弛變量簡化了原問題，并通過利用簡化問題的結(jié)構(gòu)特性提出了一種基于二分法的迭代算法來獲取最小計算總時延。為縮小二分法搜索范圍，本文還推導(dǎo)了計算總時延的上界。最后，通過仿真不僅驗(yàn)證了所提迭代算法的收斂性與正確性，而且表明了相比于部分卸載方案、全部卸載方案、全部本地計算方案以及二元制卸載方案，所提資源分配方法能在較短的時間內(nèi)計算完給定的任務(wù)比特數(shù)。