無人機與車輛協(xié)助下的分布式多任務(wù)邊緣計算卸載算法

尼俊紅， 呂夢楠

(華北電力大學(xué)(保定)信息與通信工程學(xué)院， 保定 071003)

隨著第五代移動通信技術(shù)(the fifth generation，5G)的飛速發(fā)展，新型多媒體服務(wù)和自動駕駛等人工智能應(yīng)用將成為移動用戶的熱門選擇[1]。不同用戶在服務(wù)質(zhì)量和體驗質(zhì)量等方面對通信網(wǎng)絡(luò)提出了不同的要求,其中有些應(yīng)用程序(如共享單車)對網(wǎng)絡(luò)延遲和可靠性要求是彈性的，而有些應(yīng)用(如智能交通和智能醫(yī)療)則對網(wǎng)絡(luò)延遲、吞吐量、可靠性等方面有嚴(yán)格的要求。考慮到如此多樣化的服務(wù)質(zhì)量和體驗質(zhì)量要求，在密集用戶場景，如何給用戶提供較好的用戶體驗正面臨著前所未有的挑戰(zhàn)[2]。

一個根本的問題是如何解決計算密集型應(yīng)用與資源受限的移動設(shè)備之間的沖突。值得注意的是許多計算密集型任務(wù)所要求的計算量都很大，而且需要很高的能耗。然而，由于受到物理尺寸的限制，這些輕量級移動設(shè)備的計算資源和電池壽命總是有限的。為了解決這個問題，移動邊緣計算卸載(mobile edge computation offloading, MECO)[3]提供了一個可行的解決方案。文獻(xiàn)[4]研究了動態(tài)環(huán)境下的多用戶MECO問題并將其表述為一個隨機問題，動態(tài)環(huán)境下移動用戶的主動性和無線信道的增益都是時變的。論文提出了一種高效的多主體隨機學(xué)習(xí)算法，降低了系統(tǒng)的計算量。文獻(xiàn)[5]將MECO問題與干擾管理相結(jié)合，將卸載決策、物理資源塊分配和移動邊緣計算(mobile edge computing, MEC)的計算資源分配作為三個優(yōu)化問題，設(shè)計了博弈論算法，并取得了較好的性能。文獻(xiàn)[6]通過部署非常密集的接入結(jié)點(如微基站、家庭熱點)，大大減小用戶與其相關(guān)接入節(jié)點之間的距離，使得系統(tǒng)性能得到顯著提高。此外，為了進(jìn)一步降低移動設(shè)備的能耗，一些研究人員利用能量收集技術(shù)來設(shè)計計算卸載方案。文獻(xiàn)[7]研究了綠色MEC系統(tǒng)，提出了一種最小化能耗的在線計算卸載方案，通過該算法，可以確定計算卸載決策、移動設(shè)備執(zhí)行任務(wù)的CPU周期和移動設(shè)備的計算卸載發(fā)送功率。

最近也有一些文獻(xiàn)研究具有多邊緣服務(wù)器的超密集網(wǎng)絡(luò)中的MECO問題。通過引入軟件定義網(wǎng)絡(luò)的思想，文獻(xiàn)[8]研究了超密集網(wǎng)絡(luò)中的任務(wù)卸載問題，目的是在減少宏基站能耗的同時最小化延遲，作者將該問題轉(zhuǎn)化為一個混合整數(shù)非線性規(guī)劃問題，提出了一種有效的基于軟件定義的任務(wù)卸載方案。文獻(xiàn)[9]提出了一種新穎的霧、云混合網(wǎng)絡(luò)和任務(wù)分配算法，致力于最小化所有用戶的計算延遲。文獻(xiàn)[10]提出了一種能量感知的卸載方案，該方案考慮了小區(qū)的數(shù)量和用戶的CPU頻率。此外，小型無人機也被應(yīng)用到任務(wù)卸載中。在臨時性群眾活動中，部署無人機可以滿足用戶對移動數(shù)據(jù)的高需求，擴展蜂窩網(wǎng)絡(luò)的容量[11]。文獻(xiàn)[12]提出一些部署無人機的最新技術(shù)，這些技術(shù)包括移動邊緣計算、軟件定義的網(wǎng)絡(luò)工作(soft definition network，SDN)和網(wǎng)絡(luò)功能虛擬化(network function virtualization，NFV)。盡管近幾年來針對多邊緣服務(wù)器的計算卸載問題進(jìn)行了一些研究工作，這些工作主要考慮簡單的計算任務(wù)場景[13]，通常忽略了任務(wù)類型的多樣性以及空中地面聯(lián)合協(xié)助任務(wù)卸載的情況。此外，目前現(xiàn)有的計算卸載方案比較簡單，在密集用戶場景下不能保證服務(wù)質(zhì)量和體驗質(zhì)量。

考慮到現(xiàn)有工作的局限性，在密集場景下(如臨時性群眾活動、體育場館比賽、大型購物中心等)的任務(wù)卸載問題，以車輛、無人機、路邊單元作為邊緣節(jié)點，設(shè)計了一種車輛和無人機協(xié)助下基于分布式匹配-貪婪算法的多接入邊緣計算卸載方案，將不同的任務(wù)按需傳輸?shù)讲煌倪吘壒?jié)點進(jìn)行處理，以最小化系統(tǒng)能耗。

1 系統(tǒng)模型

采用不同的卸載策略時，系統(tǒng)處理時間和能耗模型如下所述。

1.1 本地執(zhí)行代價模型

1.2 車輛、無人機代價模型

1.2.1 車輛計算模型

Ui將計算任務(wù)卸載到車輛k的數(shù)據(jù)傳輸速率為

式(4)中：Bi,k為用戶和車輛之間傳輸信道的帶寬。

Ui向車輛發(fā)送其任務(wù)，數(shù)據(jù)量為mi,j，則數(shù)據(jù)傳輸延遲為

同理，將計算結(jié)果數(shù)據(jù)從車輛傳回用戶的傳輸速率為

傳回延遲為

計算能耗可表示為

總能耗可表示為

1.2.2 無人機計算模型

式(12)中：第一項表示自由空間路徑損耗，該損耗取決于載波頻率f、光速c和路徑損耗指數(shù)α。參數(shù)ζLoS和ζNLoS分別表示由于視線和非視線鏈路造成的額外損耗。

Ui將計算任務(wù)卸載到無人機u的數(shù)據(jù)傳輸速率為

式(14)中：Bi,u為用戶和無人機之間傳輸信道的帶寬。數(shù)據(jù)傳輸延遲為

將計算結(jié)果數(shù)據(jù)從無人機傳回用戶的傳輸速率為

傳回延遲為

則由無人機處理計算任務(wù)，傳輸能量消耗為

計算能量消耗為

總體能耗為

1.3 RSU代價模型

用戶將類型j任務(wù)傳輸?shù)絉SU，假設(shè)此種卸載模式下的用戶被分配到正交信道，即用戶之間沒有干擾。傳輸鏈路之間的有效信噪比(SNR)表示為

式(23)中：Bi,r指的是用戶和RSU之間信道帶寬，如果用戶以數(shù)據(jù)大小mi,j向RSU發(fā)送其任務(wù)，則可以將數(shù)據(jù)傳輸延遲表示為

傳回延遲為

2 分布式匹配-貪婪算法

2.1 優(yōu)化模型

給定所有用戶計算任務(wù)模型、任務(wù)產(chǎn)生概率、以及車輛、無人機和RSU的計算能力。針對第一節(jié)中的系統(tǒng)模型，可以將問題表述為

式(27)中：C1表示Ui的j型任務(wù)可以選擇其中任何一種卸載決策，C2、C3、C4、C5是延遲約束，保證能在最大延遲容忍時間內(nèi)完成任務(wù)。

任務(wù)卸載的優(yōu)化變量為Ei,j，以車輛計算模型為例，假設(shè)有K輛車，定義aj,k=1表示將任務(wù)j卸載到車輛k，否則，aj,k=0。任務(wù)卸載問題轉(zhuǎn)換為任務(wù)j和車輛k之間的匹配問題，可以表示為

式(28)中：C1為延遲約束，C2表示車輛k可以同時接受多達(dá)q個任務(wù)。

2.2 算法實現(xiàn)

為了優(yōu)化目標(biāo)函數(shù)，本文提出一種邊緣節(jié)點與用戶的分布式匹配算法，一方面，每個用戶基于偏好列表選擇最優(yōu)的車輛進(jìn)行卸載；另一方面，車輛將基于其服務(wù)能力對其要處理的任務(wù)進(jìn)行篩選。

Step1①每個用戶根據(jù)延遲約束選擇滿足條件的車輛，然后對其功耗值進(jìn)行升序排序，在這一步，每個用戶根據(jù)最小的功耗值都有其自己的首選車輛列表；②每個用戶根據(jù)偏好列表向車輛發(fā)送卸載請求。

Step2每個車輛會一一接受任務(wù)發(fā)來的請求，對當(dāng)前車輛上的任務(wù)功耗值進(jìn)行升序排列。若當(dāng)前車輛上的任務(wù)請求未達(dá)到服務(wù)上限，它將接受所有請求的任務(wù)；否則，車輛選擇前q個任務(wù)進(jìn)行處理，然后拒絕其余任務(wù)請求。

Step3每個被拒絕的用戶都嘗試卸載到第二候選的車輛，并在偏好列表中刪除首選車輛的索引，若第二候選車輛未超出服務(wù)能力則接受該用戶，否則，則同樣選出前q個功耗值小的用戶任務(wù)在當(dāng)前車輛上卸載。

Step4在車輛的服務(wù)能力范圍內(nèi)，當(dāng)所有用戶都匹配到合適的卸載車輛，該算法停止，此時得到車輛計算模型下的功耗矩陣、時間矩陣以及對應(yīng)的車輛索引值。

Step5無人機、RSU計算模型重復(fù)上述步驟。

貪婪近似過程：經(jīng)過上述步驟，每種類型的任務(wù)都獲得了四種計算模式下的功耗矩陣及其對應(yīng)的索引值。比較四種功耗值的大小，選擇最小的功耗值進(jìn)行卸載，此時得到最終的卸載決策，并求得目標(biāo)函數(shù)的解。

3 仿真結(jié)果

3.1 仿真參數(shù)

仿真參數(shù)如表1所示。

表1 仿真參數(shù)

考慮異構(gòu)蜂窩網(wǎng)絡(luò)中密集用戶多邊緣節(jié)點計算場景，用戶在300 m范圍內(nèi)超密集隨機分布，300～500 m范圍內(nèi)較稀疏隨機分布。車輛在停車場的位置隨機分布，無人機在密集用戶的上方隨機分布，RSU在道路兩側(cè)分布。根據(jù)任務(wù)的大小分成五種不同類型的任務(wù)，每個用戶產(chǎn)生的任務(wù)類型是隨機的。用戶的本地計算能力為1.5 GHz，車輛、無人機的計算能力分別為4 GHz和4.5 GHz，假設(shè)RSU與云服務(wù)器連接，其計算能力遠(yuǎn)大于車輛和無人機。在停車場附近車輛數(shù)量為30～40輛，無人機在密集用戶上方隨機部署，其數(shù)量由用戶的密集程度決定，RSU的數(shù)量為4～5 個，仿真次數(shù)均為5 000次。

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

給定每個用戶的任務(wù)生成概率，不同業(yè)務(wù)類型卸載方案的概率分布如圖1所示。五種類型業(yè)務(wù)的復(fù)雜度和所需的計算資源不同，容忍延遲也不同。顯然，當(dāng)業(yè)務(wù)類型較簡單時，大多數(shù)用戶選擇在本地進(jìn)行計算，原因是在滿足時延約束的條件下本地計算的功耗值較小。隨著任務(wù)復(fù)雜度增加，卸載到車輛和無人機的概率增大，原因是受時延要求的限制，用戶本地計算無法滿足要求時，無人機和車輛能在延遲約束下處理更多的任務(wù)，這進(jìn)一步解釋了引入無人機和車輛協(xié)助任務(wù)卸載的必要性。

圖1 不同業(yè)務(wù)類型卸載方案的概率分布Fig.1 Probability distribution of offloading schemes for different task types

不同用戶層的卸載方案概率分布隨用戶數(shù)量的變化關(guān)系如圖2所示，可以看出隨著用戶個數(shù)的增加，中心用戶卸載到無人機的概率增大。原因是在基于匹配的關(guān)聯(lián)下，由于用戶的密集分布和服務(wù)質(zhì)量的限制，一些用戶，特別是中心用戶無法與車輛或者RSU進(jìn)行連接，或者信道質(zhì)量較差無法滿足計算任務(wù)的需求。此外，邊緣用戶卸載策略的選擇隨著用戶數(shù)量的變化不大，其中，卸載到車輛和RSU的概率較大，卸載到無人機的概率最小。原因是邊緣用戶距離無人機較遠(yuǎn)，考慮到時延限制，在邊緣用戶的偏好列表中，RSU和車輛成為了大多數(shù)用戶的選擇。

圖2 不同用戶層的卸載策略對比Fig.2 Comparison of offloading strategies of different user layers

每個用戶完成同類型任務(wù)的平均處理時間如圖3所示，用戶數(shù)量不同的情況下五種不同類型的任務(wù)消耗的系統(tǒng)功耗值的關(guān)系如圖4所示。很明顯，平均處理時間和系統(tǒng)功耗值隨著用戶數(shù)量單調(diào)增加，原因是用戶數(shù)量增加時更多的任務(wù)需要被卸載，這增加了傳輸延遲和功耗，此外，由于計算任務(wù)的競爭，越來越多的任務(wù)被卸載可能導(dǎo)致更長的等待延遲，相應(yīng)的功耗值也會增加。由圖中還可以看出，任務(wù)量越大平均處理時延和消耗的功耗越大。原因是密集用戶下，隨著任務(wù)大小的增加，更多的用戶選擇卸載而不是在本地來處理計算任務(wù)。此外，由圖中可以看出用戶數(shù)量越多五種類型曲線的斜率增加的越快，原因是當(dāng)用戶數(shù)量越多時，越多的計算任務(wù)被卸載時，需要消耗的時延和功耗增加的越多。

圖3 平均任務(wù)處理時間Fig.3 Average task processing time

圖4 系統(tǒng)總功耗Fig.4 Total system power consumption

系統(tǒng)中全部用戶和中心用戶滿意度分別如圖5所示，其中，模型1為本文的卸載模型，模型2為不使用無人機的模型，模型3為只有宏基站的模型，模型4為本地計算模型。從圖5可以看出，本文中包含車輛、無人機和路邊單元的多元化的邊緣計算卸載模型使整體用戶和中心用戶的滿意度最高，且用戶個數(shù)越多，這種優(yōu)越性體現(xiàn)的越明顯。

圖5 用戶滿意度Fig.5 User satisfaction

最后，為了驗證本文卸載模型和分布式匹配算法的功耗性能，對不同分流卸載策略的功耗性能進(jìn)行了對比，如圖6所示。可以看出，以系統(tǒng)總功耗為指標(biāo)，本文提出的卸載模型和算法與其他三種卸載模型相比，分別可以減少多達(dá)25%、62%、46%的功率消耗。這組實驗不僅證明了引入無人機協(xié)助卸載的必要性，而且還證明了在超密集用戶下使用多種類型的邊緣節(jié)點參與卸載的優(yōu)越性。

圖6 不同算法對應(yīng)的系統(tǒng)總功耗Fig.6 Total system power consumption corresponding to different algorithms

4 結(jié)論

本文主要研究了車輛、無人機和路邊單元協(xié)助下的密集用戶多任務(wù)、多接入邊緣計算卸載問題，旨在滿足延遲約束的條件下最小化任務(wù)卸載的功耗。考慮到車輛、無人機、RSU的服務(wù)能力，提出了一種新的分布式匹配-貪婪算法。與其他算法相比，結(jié)論如下：

(1) 用戶密集分布的情況下，無人機的引入有助于提升用戶的滿意度，與其他三種模型對比，特別是當(dāng)用戶分布密度較大時，本文的新模型對中心用戶滿意度的提升尤其明顯。

(2)通過基于分布式匹配-貪婪算法取得了系統(tǒng)功耗的最優(yōu)解，通過合理選取卸載策略，降低卸載延遲，有效保證了用戶的服務(wù)質(zhì)量。