無人機與車輛協助下的分布式多任務邊緣計算卸載算法

尼俊紅， 呂夢楠

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

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

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

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

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

1 系統模型

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

1.1 本地執行代價模型

1.2 車輛、無人機代價模型

1.2.1 車輛計算模型

Ui將計算任務卸載到車輛k的數據傳輸速率為

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

Ui向車輛發送其任務，數據量為mi,j，則數據傳輸延遲為

同理，將計算結果數據從車輛傳回用戶的傳輸速率為

傳回延遲為

計算能耗可表示為

總能耗可表示為

1.2.2 無人機計算模型

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

Ui將計算任務卸載到無人機u的數據傳輸速率為

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

將計算結果數據從無人機傳回用戶的傳輸速率為

傳回延遲為

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

計算能量消耗為

總體能耗為

1.3 RSU代價模型

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

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

傳回延遲為

2 分布式匹配-貪婪算法

2.1 優化模型

給定所有用戶計算任務模型、任務產生概率、以及車輛、無人機和RSU的計算能力。針對第一節中的系統模型，可以將問題表述為

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

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

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

2.2 算法實現

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

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

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

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

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

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

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

3 仿真結果

3.1 仿真參數

仿真參數如表1所示。

表1 仿真參數

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

3.2 仿真結果及分析

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

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

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

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

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

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

圖4 系統總功耗Fig.4 Total system power consumption

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

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

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

圖6 不同算法對應的系統總功耗Fig.6 Total system power consumption corresponding to different algorithms

4 結論

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

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

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