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

尼俊紅， 呂夢(mèng)楠

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

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

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

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

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

1 系統(tǒng)模型

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

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

1.2 車(chē)輛、無(wú)人機(jī)代價(jià)模型

1.2.1 車(chē)輛計(jì)算模型

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

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

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

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

傳回延遲為

計(jì)算能耗可表示為

總能耗可表示為

1.2.2 無(wú)人機(jī)計(jì)算模型

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

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

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

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

傳回延遲為

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

計(jì)算能量消耗為

總體能耗為

1.3 RSU代價(jià)模型

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

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

傳回延遲為

2 分布式匹配-貪婪算法

2.1 優(yōu)化模型

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

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

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

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

2.2 算法實(shí)現(xiàn)

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

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

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

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

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

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

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

3 仿真結(jié)果

3.1 仿真參數(shù)

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

表1 仿真參數(shù)

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

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

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

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

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

圖2 不同用戶(hù)層的卸載策略對(duì)比Fig.2 Comparison of offloading strategies of different user layers

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

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

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

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

圖5 用戶(hù)滿(mǎn)意度Fig.5 User satisfaction

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

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

4 結(jié)論

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

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

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