加權能耗最小化的無人機輔助移動邊緣計算策略研究

曾耀平，夏玉婷，江偉偉，劉月強

（西安郵電大學通信與信息工程學院，陜西 西安 710121）

0 引言

隨著物聯網的發展和計算密集型移動應用的普及，現有移動設備在處理應用或提供能源等方面已經無法滿足用戶需求。同時，移動視頻等大數據流量也呈指數級增長［1］，這使得移動網絡計算資源受限的問題日益突出。大多數移動設備計算能力和功耗有限，物聯網設備很難在最后期限內完成計算任務，移動邊緣計算（MEC）被認為是一種有效的解決方案，其可以增強計算服務以應對上述挑戰［2］。

目前，大部分研究致力于靜態MEC 服務器的部署，但是，為了實現更廣泛的區域覆蓋和更多的設備服務，需要部署更多的靜態MEC，這將大幅提高部署成本。針對該問題，無人機（UAV）輔助的無線通信被視為一種高效的解決方案，其能夠在缺乏傳統基礎設施或基礎設施有限的農村或偏遠地區實現全方位的通信覆蓋［3］。無人機具備按需操作、靈活部署、可控移動性強、鏈路質量高等優點，得到了廣泛研究和關注。

文獻［4］在基于云的無人機系統中，研究由無人機安裝的MEC 服務器的穩定性與大數據采集率之間的關系。文獻［5］將網絡布局與5G 技術相結合，綜合考慮波束寬度對頻率、覆蓋范圍等因素的影響，以最小化網絡功耗。文獻［6］介紹一種空-地集成的MEC 架構，該架構由地面和無人機安裝的MEC 服務器組成。文獻［7］考慮無人機安裝的MEC 服務器集群，并研究其中的計算卸載問題，以延長無人機使用壽命并減少整體計算時間。文獻［8］研究無人機輔助MEC 系統中針對多用戶的資源優化問題，完成了計算卸載、無人機軌跡和用戶調度任務，然而，文獻［8］方法的計算復雜度較高。文獻［9］應用博弈論，以實現執行時間和能量消耗之間的權衡，并探究無人機網絡中的計算卸載問題?，F有關于計算卸載的研究大多集中在移動設備向MEC 服務器的卸載過程，打破了移動設備在計算能力、電池資源和存儲可用性方面的限制。

然而，盡管無人機輔助計算通信在優化任務執行性能方面表現出色，但是相較于大型遠程云服務器，MEC 平臺的計算資源依然具有有限性。當大量計算任務被卸載到MEC 上時，可能會引發資源競爭現象。此外，移動邊緣網絡的流量分布具有異構性和動態性，單個MEC 難以持續地提供令人滿意的計算服務。針對這些問題，本文研究D2D（Device-to-Device）通信，通過在MEC 之間實現任務卸載以提高MEC 性能。通過將重負載的MEC 上的任務卸載到輕負載的MEC 上，可實現異構網絡中非均勻分布的流量的平衡。文獻［10］基于當前蜂窩網絡中的真實數據，建立一種描述多基站時間流量變化的正弦疊加模型。文獻［11］研究具有有限回程能力的聯合負載平衡和干擾管理策略。文獻［12］提出一種睡眠控制服務器計算任務卸載在線優化策略，采用睡眠控制方案來降低MEC 網絡的長期能耗。文獻［13］設計一種新的在線小基站（SBS）對等卸載框架，以優化SBS 長期能源預算下的系統延遲。此外，非正交頻分多址（NOMA）也能夠通過功率分配和串行干擾消除（SIC）技術使SBS 共享同一資源（如頻率等），從而大幅提升整個系統的吞吐量及能源效率［14］。因此，將D2D 與NOMA 技術相結合可以更好地部署未來系統，提高用戶服務質量。文獻［15］首次提出基于NOMA 的D2D 通信系統，使得單個D2D 發送端和幾個接收端在同一頻譜資源下實現通信。文獻［16］提出當NOMA 傳輸同信道干擾時向MEC 服務器卸載更多信息的最優策略。文獻［17］提出基于NOMA的無人機支持MEC 框架，該框架可以降低卸載能耗，克服設備的計算能量限制。

上述計算卸載方案通常忽略了MEC 間的協同作用，本文研究雙層MEC 間的協同作用，其中，上層為多無人機輔助計算卸載，下層為SBS 間的協同作用，并設計MEC 間的卸載策略和資源分配方案，以優化全網絡的系統能耗。隨著基站的密集化和邊緣計算平臺的增加，對能源效率的需求進一步提升。本文考慮在系統每個區域內都設置無人機輔助SBS計算，利用李雅普諾夫（Lyapunov）優化框架將目標問題進行分解，提出一種在線資源分配調度優化算法。針對流量分布不均勻且會出現大部分流量突發的情況，本文在多服務器多SBS 的場景下，充分考慮隨機的應用請求、不可預測的SBS 狀態、計算資源分配以及共信道干擾約束等因素，以系統平均能耗為優化目標，基于排隊論構建聯合優化資源分配與飛行軌跡的自定義應用卸載模型。首先，構建本文模型時融合本地設備的M/M/1 計算模型和無人機的M/M/m 排隊模型；其次，通過Lyapunov 隨機優化理論，構建漂移懲罰函數，將隨機優化問題轉變為4 個獨立的子問題；然后，設計一種啟發式的用戶匹配算法，獲取用戶最佳匹配方案；接著，提出改進的自適應下降交替方向乘子法（AD-ADMM），獲取最優卸載決策；最后，利用塊坐標下降法和連續凸逼近（SCA）算法，聯合優化資源分配、卸載決策以及飛行軌跡調度問題。

1 系統模型

如圖1 所示，本文考慮一種基于NOMA-D2D 的多無人機輔助邊緣計算系統模型，該系統由K架搭載MEC 服務器的無人機和M個低功率SBS 構成。當網絡流量分布不均時，重負載的SBS 可以選擇將計算任務卸載到低負載的SBS 上進行處理。在附近無SBS 可供輔助卸載時，為確保整個系統的穩定性，請求SBS 選擇將卸載的計算任務分配至UAV 上。為了便于表達，定義SBS、UAV 的集合分別為?m∈M{1，2，…，M}、?k∈K{1，2，…，K}。在該系 統中，每個SBS 和無人機均可以維護到達的任務隊列，將到達的任務存儲在任務緩沖區中，按照先進先出的順序進行處理。

圖1 系統模型Fig.1 System model

此外，無人機依靠有限的機載能量飛行，并在持續時間T內為SBS 提供邊緣計算服務，將T均勻離散成N個時隙，各時隙間隔τ=T/N足夠小，以確保各時隙內無人機和SBS 的位置基本恒定，記時隙集合為?t∈N{1，2，…，N}。不失一般性，考慮一個三維笛卡爾坐標系，規定SBS 均位于水平地面上，無人機均以固定高度H飛行，SBSm在t時隙的水平位置為pm=(xm，ym)，無人機的位置為pk(t)=(xk(t)，yk(t))。假設無人機k在飛行周期結束后返回初始位置，鑒于實際工程應用中存在的局限性，無人機k在每個時隙內的飛行距離與飛行速度有關，且無人機之間需要維持最小安全飛行距離，以避免碰撞。因此，無人機應滿足如下的移動性約束：

其 中：pk，I和pk，F分別表 示UAV 的初始 位置和 終止位置；Vmax表示無人機的最大飛行速度；Dmin表示防碰撞的最小安全距離。系統中使用的主要參數及含義如表1 所示。

表1 系統參數說明 Table 1 System parameters description

1.1 通信模型

考慮到在無人機飛行過程中視距鏈路（LoS）受環境中其他障礙物的影響，參考文獻［18］，假設t時隙SBSm將計算任務卸載至UAVk上，則兩者之間的仰角和LoS 概率分別為：

其中：a和b分別為取決于載波頻率和環境類型的參數。因此，SBSm向UAVk傳輸的上行信道功率增益表示為：

其中：h0為參考距離d0=1 m 處的信道功率增益；P(LoS，?m，k(t))=P(LoS，?m，k(t))+μ(1-P(LoS，?m，k(t))) 表示考慮了使用μ＜1 的非視距信道的衰減效應的正則化LoS 概率［19］；?m，k(t)是t時刻SBSm和無人機k之間的角度。

根據NOMA 的原理，針對無人機之間的干擾問題，本文將整個頻譜劃分為K個帶寬為B的正交無線子信道。假設不同的UAV 通過頻分多址占用不同的子信道，將每個時隙共享同一子信道的SBSs 稱為一個NOMA 組。將各NOMA 組中的SBSs 按其信道增益大小進行升序排列，無人機k將進行SIC 解調來自多個SBSs 的信號，而SIC 的排序方式則遵循信道增益的降序排列。根據NOMA 組中SBSs 的排序方法，上行SBS 可能會受到其他信道增益較低的SBSs 的干擾，從而導致組內干擾存在［20］。由香農公式可知，在t時刻，SBSm卸載的計算任務量應滿足：

其 中：B=1 MHz 為信道帶寬；為SBSm向UAV卸載的最大傳輸功率；N0=10-12W 為信道噪聲功率；為同一NOMA 組內的用戶間干擾。

在本文模型中，SBS 之間通過局域網進行數據傳輸，但局域網帶寬有限，規定SBSm僅可向一個適宜的接收SBS 請求進行D2D 輔助卸載。然而，一個接收SBS 可以為多個請求SBS 提供協同傳輸。不失一般性，定義lmm'(t)∈{0，1}為D2D 卸載選擇指示器，其中，m'∈M-m表示除SBSm外的屬于SBS 集合M的其他SBS，lmm'(t)=1 時表示請求SBSm選擇接收SBSm'輔助卸載，否則，lmm'(t)=0。因此，約束條件如下：

同時，定義αm，k(t)∈{0，1}為無人機卸載指示器，其中，αm，k(t)=1 表示SBSm卸載計算任務至UAVk上，否則，αm，k(t)=0。假設在任意時隙t，SBSm最多選擇一個UAV 進行任務卸載，因此，約束條件應滿足：

1.2 應用程序分區和協同傳輸調度模型

根據描述多基站時間流量變化的正弦疊加模型，在t時隙SBSm的計算任務用二元組Ω=＜Am(t)，ρ＞表示，其中，Am(t)表示SBSm到達的任務量，ρ為計算每比特任務所需的CPU 周期數［21］。定義fl，m(t)為SBSm的計算頻率，fk，m(t)為UAVk分配給SBSm的計算資源，則本地執行和無人機執行的任務量分別表示為：

定義Qm(t)表示SBSm在時隙t的任務隊列積壓，和分別表示從Qm(t)傳輸給本地計算隊列Lm(t)和卸載的任務量，則任務隊列的更新過程滿足：

由于應用狀態的不可預測性，SBS 可能在不同時隙處于不同的運行狀態（請求、接收和中立狀態）。為了確保卸載任務不會發生卸載循環現象，從其他請求SBS 卸載的數據必須在接收SBS 的本地執行，可以得到本地計算隊列Lm(t)的動力學公式為：

為了保證隊列的穩定性，隊列積壓在時間平均意義上需滿足：

1.3 能耗模型

系統中的總能耗［22］主要包括計算能耗、通信能耗和無人機的飛行能耗。

1.3.1 計算能耗

根據電路理論，執行任務的大部分能量消耗來自CPU，且CPU 周期頻率與CPU 電壓近似呈線性關系。任務執行的CPU 周期頻率和CPU 能耗可以通過CPU 電壓的變化來調整。因此，t時隙SBSm本地計算和UAVk處理來自SBSm計算任務的能耗分別為：

其中：κ是由硬件架構決定的CPU 有效切換電容［23］；fl，m(t)和fk，m(t)分別表示SBSm的計算頻率以及UAVk分配給SBSm的計算頻率。

1.3.2 通信能耗

根據文獻［23］，從MEC 服務器到SBS 返回計算結果的過程中能耗足夠小，其值在能量消耗模型中可以忽略不計。同時，值得注意的是，SBS 之間的數據傳輸主要依賴于光纖、同軸電纜等高效的局域網連接，其能耗在能量消耗模型中也可忽略［24］。因此，t時隙SBSm卸載任務至無人機k的能量消耗為：

1.3.3 無人機的機動性和飛行能耗模型

無人機k在第t時隙與第t-1 時隙之間的速度為：

其中：P0和PH分別代表懸停狀態下的葉片輪廓功率和誘導功率；Utip為轉子葉片的尖端速度；v0表示無人機懸停時轉子的平均轉子感應速度的一個常數；d0、ρ、s和A表示無人機空氣動力學的相關參數。無人機k的飛行總能耗表示為：

因此，整個系統的總能耗可以通過時隙t的計算能耗、通信能耗和飛行能耗的總和來計算，如下：

其中：ωm∈{0，1}和ωc∈{0，1}分別為SBS 和UAV 的權重因子，滿足ωm+ωc=1，這2 個值可根據實際系統進行調整，以滿足優先能源需求，或實現SBS 和無人機之間的能耗平衡；η是飛行能量消耗的一個懲罰系數，旨在緩解幅度差異。式（27）假設所有的通信鏈路都是可靠的，不考慮計算任務重傳的問題。

1.4 問題定式化

本文旨在解決一個基于NOMA-D2D 的多UAV輔助通信問題，在同時滿足計算資源、緩存資源和任務緩沖區的限制條件下，通過聯合優化卸載策略、發射功率、計算資源分配和軌跡調度，以最小化全網絡的平均能耗。上述目標表述為如下的隨機優化問題：

2 問題轉換與算法

Lyapunov 優化是解決確定性時隙問題并求解低時間復雜度下平均最優解的有效算法，不需要使用先驗數據的統計信息來預先指定控制參數，可以根據實時輸入的數據在線計算出控制參數，從而實現對系統的在線控制和調整。本文采用Lyapunov 對任務到達隊列進行分析和卸載，將式（28）轉化為4 個易于優化的子問題，從而迭代地解決系統的資源分配和無人機軌跡優化問題。

2.1 隊列分析與問題轉換

假 設θ(t)=(Qm(t)，Lm(t)，Jm(t))|m∈M表示系 統中所有的任務隊列積壓，定義一個二次Lyapunov 函數為：

定義單槽Lyapunov 漂移為：

根據Lyapunov 優化理論，定義漂移加懲罰函數為：

其中：V≥0 是控制系統效用和隊列穩定性之間權衡關系的系數；Es(t)是系統加權能耗。通過最小化D(θ(t))的上界來最小化漂移加懲罰函數：

通過優化式（32）右側的上界，可以最小化漂移加懲罰函數，即將目標問題轉化為：

從式（34）可以看出，解決優化問題需要考慮能量消耗和任務執行狀態2 個方面，基于此，每個SBS可根據其狀態（包括服務需求和數據隊列積壓等）采取獨立的卸載方案。

2.2 在線資源協調分配分案

由于指示器的選擇只和周圍SBS 的位置信息以及空閑狀態有關，因此lmm'(t)和其他優化變量無關。為了求解上述優化問題，針對不同的優化變量將問題分解為4 個最優子問題進行交替迭代求解。

2.2.1 SBS 卸載決策

本節提出一種最佳SBS 卸載決策方案，避免傳統的遍歷匹配等方法中計算復雜度呈幾何倍數遞增的問題。該方案采用一種基于匹配博弈的啟發式算法，以降低計算復雜度，提高計算效率，并獲得近似匹配結果。

本文將匹配的請求SBSm和接收SBSm'稱為D2D匹配，這些SBSs 通過一個共同的控制渠道廣播它們的需求和本地資源。對于需要卸載計算任務的請求SBS，首先根據收集到的信息檢查是否存在潛在的接收SBS 可以提供幫助，若不存在潛在的接收SBS，則根據與UAV 之間的距離進行優先排序和選擇，以獲取最終的卸載決策。否則，針對所有潛在的接收SBS，根據卸載所需能耗生成偏好列表，以便在卸載決策時做出適宜的選擇。因此，請求SBSm和接收SBSm'在D2D 匹配中的偏好可以分別表示為：

2.2.2 計算任務分配

在給定UAV 飛行軌跡的情況下，任務分配q=與UAV 的飛行軌跡pk(t)被解耦，此時任務分配問題可以表示為：

顯然，式（37）是一個多變量耦合的線性約束凸優化問題，將原問題轉化成增廣拉格朗日形式，如下：

其中：β∈R+是用于調整AD-ADMM 收斂速度的懲罰參數。因此，AD-ADMM 會執行如下迭代直到收斂：

為了加 快收斂速度，定 義PΛ=max{λ，0}，v=執行以下迭代：

其中：γk是自適應步長的延長因子，一般γk∈(1，2)時收斂速度較快。是最優步長，表達式為：

此外，式（37）是具有強對偶性的凸優化問題，即其拉格朗日量具有鞍點，更新的變量隨著迭代次數的增加都將收斂。定義算法收斂準則為：

其中：ε是一個值較小的正常數。

2.2.3 計算資源優化

固定無人機的飛行軌跡，對無人機上的計算資源進行分配，為MEC 服務器分配更大的計算能力來執行卸載任務，表述為：

對于式（45），元素之間沒有耦合，因此，無人機的最佳處理頻率由每個SBSm推導出，通過內點法求得的鞍點除此之外，MEC 服務器的最佳處理頻率也可以由邊界得到。綜上，MEC 服務器的最優計算資源分配為：

2.2.4 無人機軌跡調度優化

預先確定無人機的頻率分配和卸載決策，旋翼無人機的軌跡優化問題表示為：

為了處理目標函數中的非凸項Pk(||vk(t)||)，采用SCA 的方法，引入輔助變量vk，t≥||vk，t(t)||，將無人機的推進功率重寫為：

由于式（50）的右側第二項仍然非凸，因此進一步引入輔助變量：

由于式（52）是關于vk，t和yk，t的聯合凸函數，記其右側為，第j次迭代時的展開點為對 其進行一階泰勒展開可得下界為：

由此，式（50）的右側第二項轉變為凸函數。接下來對非凸約束式（3）的左側進行一階泰勒展開，得其凸約束為：

因此，原始優化問題式（49）可以轉化為：

此時，目標函數及約束條件均為凸函數，即式（58）為凸問題，可以很容易地通過CVX 等凸優化求解器進行求解。結合以上分析，求解各子問題的交替迭代優化算法描述如算法1 所示。

3 仿真結果分析

本節將通過一系列的仿真實驗來分析所提算法的性能。在仿真實驗中，在100 m×100 m 區域內隨機分布50 個SBS，無人機為3 架。無人機從固定的初始位置出發，飛行一段時間后回到初始位置。無人機任務完成總時間T=2 s，平均包括N=50 個時隙。系統相關參數設置如表2 所示［26］。

表2 仿真參數設置 Table 2 Simulation parameter settings

為了體現本文所提算法的優越性，實驗首先分析算法的參數對最終結果的影響，其次分析計算任務量對系統能耗的影響，將本文所提算法與以下算法進行比較：

1）本地計算算法（簡稱為Local 算法）：所有的SBS 均在本地執行計算任務。

2）隨機算法（簡稱為Random 算法）：用戶在無人機覆蓋范圍內時，隨機地選擇任務在本地計算還是卸載到無人機上處理。

3）ADMM 算法：未改進的計算任務分配算法，其他條件與本文所提算法相同。

圖2 和圖3 所示為不同權重因子下卸載能耗性能和Lyapunov 控制參數之間的關系。從中可以看出，系統平均能耗隨著控制參數的增加而逐漸降低并趨于穩定，且任務隊列隨之增大。這是因為通過調節控制參數來實現系統效用和隊列穩定性之間的權衡，從而表明本文所提算法在保證系統長期穩定的約束前提下，能夠實現能耗最優的效果。同時圖2和圖3 也反映了權重因子對能耗和隊列積壓的影響，權重因子越大，無人機的能耗占比越大，系統向無人機卸載的任務量越小，導致任務緩沖區剩余的任務量越多。

圖2 V 和ωc 權重因子對能耗的影響Fig.2 The effect of V and ωc on energy consumption

圖3 V 和ωc 對任務隊列積壓的影響Fig.3 The effect of V and ωc on task queue backlogs

圖4 和圖5 分別描述了最大任務到達量以及無人機計算能力下系統總能耗的變化情況。圖4 中能耗隨著任務量的增加而顯著增加并最終趨于穩定狀態，這是因為在系統中通信資源和計算資源均有限，當系統中任務量達到飽和狀態時，網絡中就會出現任務擁塞現象。圖5 反映了SBS 計算能力對系統總能耗的影響，從中可以看到，隨著移動設備本地計算能力的提高，全部在本地計算的系統總成本降低得最快，這是因為當設備本身計算能力提高時，計算任務的效率也會提高，隊列中任務等待的時間變短，因此，其總成本降低得較快。而其他算法隨著用戶計算能力的提高，系統總成本逐漸降低，但是降低幅度不大，因為當設備本身計算能力提高時，其他卸載算法卸載到無人機上執行的任務量可能會減少，降低了任務的傳輸成本，因此，他們的系統總成本會逐漸降低。綜上，本文所提算法的系統總成本最低，體現了該算法的優越性。

圖4 任務到達量對能耗的影響Fig.4 The effect of task arrivals on energy consumption

圖5 用戶計算能力對能耗的影響Fig.5 The effect of user computing power on energy consumption

圖6 表示系統包含50 個SBS 時3 架UAV 的飛行軌跡，無人機從不同的初始位置開始并最終返回初始位置。從圖6 可以觀察到，優化軌跡后的無人機飛行靠近相應的用戶集群，更傾向于為更接近它們的用戶服務，這表明通過軌跡優化，UAV 能更好地為SBS 提供計算服務。然而，由于計算任務在隊列中積壓，優化后的軌跡不太平滑，包含較多的彎曲。在某些時刻，當大量計算任務被卸載到UAV 上時，導致無人機的位置發生跳躍。此外，可以觀察到3 架無人機的軌跡傾向于盡量遠離彼此，這是因為算法考慮了無人機的防碰撞約束。由于SBS 在不同時刻會產生隨機計算任務，因此UAV1 和UAV2 的軌跡圖像在某些時刻可能會重疊。最后，由于總的任務完成時間有限，因此無人機在飛行一段時間后會以高速和直線軌跡返回到最初位置。

圖6 無人機的飛行軌跡Fig.6 Fly trajectory of unmanned aerial vehicles

4 結束語

本文通過聯合優化資源分配、卸載決策以及軌跡調度，在保持隊列穩定性的基礎上，研究基于D2D的無人機輔助MEC 系統能耗最小化問題。該問題為非凸問題，為此，提出一種基于Lyapunov 的在線資源協調分配方案，將非凸問題分解為4 個易于管理的子問題。在每次迭代中，將卸載決策建模為給定無人機軌跡下的結構型凸優化問題，提出AD-ADMM算法進行求解。在給定資源分配的條件下，利用SCA 技術將旋翼無人機的軌跡優化問題轉化為標準的凸優化問題進行求解。仿真結果表明，與基準測試方案相比，該算法在能耗方面具有一定的優越性。下一步將研究無人機的飛行高度協同通信功率、卸載決策以及軌跡規劃問題，同時也將繼續探討其他類型無人機的軌跡優化技術。