無人機無線網絡中基于隊列穩定的無線與計算資源分配優化

黨 甜，王 鵬，趙海舜，王 禹，杜龍海

(中國電子科技集團公司 第54研究所，石家莊 050081)

0 引言

無人機(UAV，unmanned aerial vehicle)無線網絡通過將基站部署到UAV上，提高信道環境質量，為用戶提供無線通信服務，具備快速部署和靈活機動的優勢[1]。同時，在UAV無線網絡中，將邊緣計算服務器部署在更靠近用戶的UAV基站處[2]，有助于充分利用邊緣計算資源，降低服務響應時間，減少網絡中基站與核心網間的流量負載。

在邊緣計算網絡中，邊緣計算服務器支持具有計算需求的通信應用，能夠降低網絡時延和能耗。文獻[3]將邊緣計算網絡中常見的計算任務模型劃分為二進制計算卸載和部分計算卸載，從計算時延和能耗方面介紹了邊緣計算網絡的邊緣計算功能，總結了無線和計算資源聯合管理對系統性能的增益。文獻[4]著重介紹了邊緣計算系統的計算卸載問題，綜合調研了已有工作對計算卸載決策、計算資源分配和移動性管理的研究。邊緣計算網絡中的資源調配優化是提高網絡性能的關鍵技術，已有研究主要從計算資源和通信資源方面展開。在計算資源調配方面，文獻[5]構建了基于邊緣計算卸載的車聯網架構，其中行駛車輛根據預測將計算任務提前卸載到行駛方向前方的邊緣計算服務器或直接卸載到臨近邊緣計算服務器，分析了各種卸載方式對成本和時延的影響，并在時延約束下提出了傳輸和計算成本最小化的預測組合模式卸載方案；為了最小化系統時延和能耗，文獻[6]研究了任務分配決策和終端中央處理器頻率優化問題，驗證了終端中央處理器頻率對任務分配決策有明顯影響；文獻[7]研究了以最小化能耗為目標的任務卸載決策優化問題，針對時分多址的邊緣計算卸載場景推導了最優的基于本地計算能量和信道增益的卸載優先級函數，針對正交頻分多址的邊緣計算卸載場景設計了低復雜度的局部最優算法。在聯合無線與計算資源調配方面，文獻[8]針對移動設備可獲取能量的邊緣計算系統，研究了以優化執行時延和丟包成本為目標的任務卸載、計算頻率、傳輸功率和能量采集速率分配問題，設計了一種低復雜度的基于李雅普諾夫優化的動態計算卸載算法。

將計算任務卸載到更靠近網絡邊緣的計算服務器上，有利于提高計算處理的響應時間，其中計算資源的分配和調度是任務處理效率的關鍵技術。文獻[9]提出一種基于模擬退火思想的改進遺傳算法，將虛擬計算資源上任務分配數的標準差作為選擇個體的依據來實現節點的負載均衡，降低任務完成時間，提高資源利用率。文獻[10]研究了云計算環境中的資源調度問題，針對蟻群優化算法在處理大規模組合優化問題時易陷入搜索速度慢和局部最優解的缺陷，提出了一種實現云計算負載均衡的雙向蟻群優化算法，具有較短的總任務完成時間和較好的尋優能力。文獻[11]提出一種虛擬機資源高效分配策略，旨在以最低限度的資源損耗成功執行任務，可以大幅節約能源消耗。文獻[12]研究了聯合通信與計算資源優化問題，考慮緩存容量與計算能耗限制，將問題建模為以優化時延為目標的緩存內容放置與計算任務卸載問題，旨在降低業務服務延遲。

在UAV無線網絡中，UAV作為空中基站并配置邊緣計算資源，為用戶終端提供通信服務和計算任務處理，已引起廣泛的關注和研究。文獻[13]在空天地綜合網絡中利用UAV為終端提供邊緣計算，研究了計算資源分配和任務調度方法，設計了基于機器學習的計算卸載算法，有效降低了網絡時延。文獻[14]構建了多個UAV協同的邊緣計算模型，其中UAV之間相互分擔計算任務，利用差分進化算法確定UAV位置，設計協同貪婪算法進行任務卸載和計算資源分配，有效降低了網絡能耗和UAV數量。文獻[15]為UAV配置邊緣計算服務器，提出了利用UAV作為計算和中繼節點來降低用戶時延，研究了UAV位置部署、用戶關聯、回程鏈路時間和計算資源分配優化問題。文獻[16]利用正交或非正交多址方案實現頻分雙工，在此基礎上通過地面設備與UAV的上下行通信完成任務卸載，聯合優化比特分配和UAV軌跡，有效降低了UAV能源消耗。文獻[17]利用UAV為地面用戶提供邊緣計算業務并傳輸能量，針對任務部分卸載模型推導出最優計算頻率、卸載時間和傳輸功率表達式，針對二進制卸載模型設計了最優的計算任務卸載方案。文獻[18]研究了UAV無線網絡的UAV軌跡與資源優化，提出了基于能耗感知的以最小化時延為目標的聯合軌跡、傳輸功率和處理頻率分配的交替優化算法，實現了時延與能耗之間可控的折中關系。

在UAV無線網絡中，用戶可以向UAV傳輸數據并卸載計算任務，然而UAV的處理能耗和用戶的傳輸能耗資源受限，這影響了網絡中數據傳輸和計算任務處理服務的穩定性。因此，在UAV無線網絡中，需在保證數據傳輸及任務處理的穩定性下，研究以最小化能耗為目標的資源分配優化問題，并考慮傳輸功率和處理資源等約束條件。

針對UAV無線網絡中用戶向UAV基站發送數據并卸載計算任務的場景，構建了數據隊列和計算任務隊列，在保證隊列穩定的前提下，解決以最小化平均能耗為目標的無線與計算資源分配優化問題，獲得能耗和隊列之間可控的折中關系，并利用數據仿真驗證所提方案的有效性。

1 系統模型

1.1 網絡模型

考慮UAV無線網絡：在升空UAV上配置基站設備和邊緣計算服務器，假設UAV是可在空中懸停的旋翼UAV，為地面用戶提供接入和任務卸載服務；地面用戶向UAV基站傳輸數據并卸載計算任務，如圖1所示。其中，假設UAV將計算任務處理后只需要將指令信息返回給用戶，此過程的功耗可忽略不計。假設每個用戶向UAV傳輸數據時，分別占用帶寬為W(MHz)的正交信道，則用戶間的無線數據傳輸無干擾。

圖1 UAV無線網絡數據傳輸和計算卸載模型

將連續時間劃分為T個時隙，每個時隙的時長為τ，假設網絡中有N個用戶向UAV基站傳輸數據并卸載計算任務。在每個時隙t上，用戶n需向UAV傳輸的數據量可以被表示為An(t)，用戶的數據傳輸速率是Rn(t)，其數學表達式為

(1)

其中：pn(t)是發射功率，hn(t)是信道增益，σ2表示噪聲功率。每個時隙上各用戶的傳輸功耗的計算公式為傳輸功率與傳輸時間的乘積，即pn(t)τ。另外，用戶到UAV基站的信道采用概率視距模型[19]，同時考慮視距信道和非視距信道，其中每個時隙上UAV基站與用戶之間構建的概率與通信環境以及UAV到用戶的距離有關，可在仿真中確定UAV和用戶的部署位置后再進行計算確定。

假設用戶向UAV基站卸載的計算任務量與數據量An(t)呈正比關系，記為γAn(t)，γ表示處理1比特數據所需要的CPU轉數，則計算任務量的含義是處理An(t)數據量的任務所需的CPU總轉數。假設UAV基站承載的邊緣計算服務器中CPU計算資源總量為Cmax，表示CPU處理頻率，即每秒的CPU轉數。在每個時隙上分配給各用戶的計算資源用Cn(t)表示，每個時隙上UAV處理每個用戶計算任務的處理功耗的數學表達式為γAn(t)kCn(t)2，其中k表示CPU的能量效率。

因此，每個時隙上的能耗包括所有用戶的傳輸能耗和UAV的處理能耗，其表達式為

(2)

所有時隙上平均能耗的表達式為

(3)

其中：e(0)=0，表示初始時刻的能耗。

1.2 隊列模型

針對用戶到UAV基站的數據傳輸和計算任務卸載場景，對數據隊列和任務隊列建模。

1)數據隊列：

用Qn(t)表示每個用戶在每個時隙上的數據隊列長度，其含義可以理解為每個用戶上待傳輸的數據量，其中Qn(0)=0，表示初始時刻的隊列長度。在每個時隙上，到達的數據量為An(t)，離開的數據量為Rn(t)τ。因此，相鄰兩個時隙上數據隊列長度的動態性可以表示為：

Qn(t+1)=[Qn(t)-Rn(t)τ]++An(t)

(4)

其中：運算符號[]+表示取正，當括號內數值為負數時，計算結果為0，當括號內數值為非負數時，計算結果等于括號內的數值。

2)任務隊列：

用Hn(t)表示每個用戶在每個時隙上的任務隊列長度，其含義可以理解為每個用戶所對應的待處理的計算量，其中Hn(0)=0，表示初始時刻的隊列長度。在每個時隙上，到達的任務計算量為γAn(t)，離開的任務計算量為Cn(t)τ。因此，相鄰兩個時隙上任務隊列長度的動態性可以表示為：

Hn(t+1)=[Hn(t)-Cn(t)τ]++γAn(t)

(5)

從(4)和(5)中可以看出，Qn(t)和Hn(t)是動態隊列，隨著時間、每個時隙上的隊列到達量和隊列離開量變化而變化。當數據隊列長度過大時，易導致用戶緩沖區數據堆積，數據丟包；當任務隊列長度過大時，易導致UAV基站上卸載的計算任務堆積，邊緣計算服務器的負載過大。為了避免數據隊列和任務隊列過長，需要在數據傳輸和計算任務處理的過程中，要求Qn(t)和Hn(t)均滿足隊列的穩定性[20]，即

(6)

(7)

2 問題建立與求解

接下來，在隊列穩定性約束下，考慮傳輸功率和處理資源的限制，構建以最小化平均能耗為目標的聯合無線和計算資源分配優化問題，如下所示：

s.t.

C2：Rn(t)≥Rmin

C3：pn(t)≤pmax

(8)

其中：約束條件C1表示所有用戶分配到的計算資源不超過UAV上配置的邊緣計算服務器的總計算資源，C2為用戶傳輸速率約束，Rmin表示用戶的最小傳輸速率，C3是用戶傳輸功率約束，pmax表示用戶的最大傳輸功率，C4和C5表示數據隊列和任務隊列滿足穩定性約束。

解決上述能耗優化問題，需要在已知所有時隙上隊列狀態的情況下，求解所有時隙的傳輸功率和計算資源分配結果，這是很難獲取到的。為了解決該問題，可以利用李雅普諾夫優化理論[20]，將其轉化，從全部時隙上的平均能耗最小化問題轉化為單個時隙的優化問題，每個時隙上的問題求解只需獲取過去和當前時隙的能耗和資源分配信息。

首先定義Θ(t)=[Qn(t)，Hn(t)]表示每個時隙上的所有數據隊列與任務隊列的狀態，接著構建李雅普諾夫函數J(Θ(t))作為度量隊列擁塞的標量，其數學表達式為

(9)

可以看出，J(Θ(t))取值越小，數據隊列與任務隊列的長度就越短，在此基礎上，能保證所有隊列是穩定的。為了在所有時隙上保證數據隊列和任務隊列穩定，在任意相鄰時隙上需控制李雅普諾夫函數的取值變化保持在較小的范圍，這也是保證隊列穩定的充分條件[20]。

根據李雅普諾夫優化理論，定義李雅普諾夫偏差函數，表示相鄰兩個時隙間李雅普諾夫函數的數值變化，即隊列擁塞的變化：

Δ(Θ(t))=Ε[J(Θ(t+1))-J(Θ(t))|Θ(t)]

(10)

每個時隙上，構建偏差加罰函數，表達式為偏差函數和能耗的加權和，即

Δ(Θ(t))+VΕ[e(t)|Θ(t)]

(11)

其中：常數V≥0是李雅普諾夫控制參數，表示能耗部分的權重，用來平衡偏差函數與能耗間的折中關系。具體而言，當參數V的取值變大時，式(11)中能耗部分占比變大，偏差加罰函數更加偏向于能耗，否則偏差函數部分占比變大，偏差加罰函數更加偏向于數據隊列和任務隊列。

根據文獻[20]中的定理4.2，在任意時隙上，對于所有隊列，存在非負常數D≥0、V≥0、ε≥0，滿足下列不等式

Δ(Θ(t))+VΕ[e(t)|Θ(t)]≤

(12)

其中：e*表示優化問題(8)對應的理論最小能耗。當V>0和ε>0時，還可以得到

(13)

(14)

其中：emin是期望能耗的下界，即Ε[e(t)]≥emin。

將數據隊列和任務隊列的計算公式(4)和(5)代入到李雅普諾夫偏差加罰函數(11)中，通過化簡，可以得到一個李雅普諾夫偏差加罰函數的上界：

Δ(Θ(t))+VΕ[e(t)|Θ(t)]≤B+VΕ[e(t)|Θ(t)]>-

(15)

其中：B為數值有限的常數。

通過最小化偏差加罰函數，可以得到在隊列穩定下，最小化能耗的資源分配結果。此時，相比于在每個時隙上最小化偏差加罰函數，可直接將問題轉化為在每個時隙上最小化偏差加罰函數的上界[20]，即不等式(15)的右側。

在此基礎上，將傳輸功率和計算資源分配變量解耦，轉化后的優化問題還可以被分解為兩個子問題，分別可以表示為：

s.t.C1

(16)

s.t.C2，C3

(17)

經分析可得，兩個子問題的目標函數都是優化變量的凸函數，約束條件都可以表示為變量的線性函數。因此，兩個子問題都是凸規劃問題，可以利用凸優化算法進行求解，也可以通過Matlab數學仿真平臺中的凸規劃(CVX，convex programming)工具包[21]進行求解。最后總結求解能耗優化問題的流程，如圖2所示。CVX工具箱采用一種規則化的編程語言來描述數學優化問題[22]。通過將凸優化問題構建為滿足CVX格式要求的標準形式，可以利用簡潔的CVX語言實現求解的Matlab編程，簡化求解過程[23]。

圖2 流程圖

下面利用CVX工具箱分別對兩個子優化問題進行求解。針對計算資源分配優化問題(16)，利用CVX工具箱對計算資源分配變量的求解過程如圖3所示。

圖3 利用CVX工具箱求解計算資源分配問題

為了簡潔性，圖中省略了對優化問題中其他參數的初始化步驟。圖3中的第一列數字為行號，以便對各行進行解釋。圖3中各行代碼的具體含義如下：

1)CVX開始標識，從Matlab運行程序模式切換到CVX優化問題求解模式。

2)定義優化變量，其中c_ue(N)是優化目標向量，N表示陣元數量。優化問題求解結束后，c_ue(N)將被替換為最優解。

3)最小化目標函數，將計算資源分配問題(16)的優化目標函數代入。

4)約束條件的開始標識，接下來將描述優化問題中的約束條件。

5)設置不等式約束，所有用戶分配到的計算資源的總和不超過UAV中的總計算資源。

6)設置不等式約束，每個用戶分配到的計算資源不小于0。

7)CVX結束標識，優化問題描述完成，CVX工具箱開始求解上述優化問題。

同樣，針對功率分配問題(17)，利用CVX工具箱的求解過程如圖4所示。

圖4 利用CVX工具箱求解功率分配問題

圖4中CVX工具箱求解步驟與圖3內容相似，在此只對不同的步驟做出解釋。圖4中的第3行通過將功率分配問題(17)的優化目標函數代入得到最小化目標函數，第5行是每個用戶傳輸功率的最大值約束，第6行根據每個用戶傳輸速率的最小值約束得到，第7行要求每個用戶的傳輸功率不小于0。

3 仿真結果與分析

最后，利用仿真數值結果驗證所提方案的有效性。在仿真場景中，假設考慮300個時隙，每個時隙的時間長度為0.5秒。具體仿真參數設置如下：每個用戶的通信帶寬為0.15 MHz，噪聲功率為10-14W。每個用戶的最大傳輸功率為0.05 W，最小傳輸速率為2 Mbps，UAV上總計算資源為1 GHz，假設處理1 bit數據所需的CPU轉數為0.1，UAV上邊緣計算處理器的處理能量效率為10-32。每個時隙上，用戶需傳輸的數據量服從均勻分布U(0.5×106，1.5×106)。

利用Matlab工具進行仿真時，首先將所有用戶通過隨機撒點放置到以(0，0)為圓心，以80 m為半徑的圓形平面中，每個用戶的高度為0。將UAV的水平位置固定為圓心坐標，飛行高度為80 m。基于概率視距模型[19]，可以計算得到用戶到UAV基站的信道增益為hn(t)=10-PLn(t)/10，其中PLn(t)表示鏈路的平均路徑損耗，是視距信道和非視距信道路徑損耗的概率均值。

考慮無人機無線網絡中有12個用戶，圖5驗證了隊列的穩定性，展示了不同李雅普諾夫控制參數下隊列長度隨時隙的變化情況。其中，縱坐標隊列長度為Qn(t)和Hn(t)隊列長度的總和，兩類隊列長度分別表示用戶向UAV傳輸數據時等待被傳輸的數據量以及UAV上對各用戶的計算任務進行處理時等待被處理的任務量，單位分別是比特和轉數。由于兩類隊列長度的單位不同，所以僅在此做出解釋，在圖中縱坐標處未標明單位。從圖5中可以看出，對于不同的控制參數，隊列長度均隨著時隙的增加而增大，然后逐漸趨于穩定。另外，從圖5中還可以看出，當控制參數取值增大時，隊列長度隨之變大，這是因為控制參數的取值影響了隊列與能耗的折中關系，在以增大隊列為代價下可以進一步降低能耗。

圖5 隊列長度隨時隙增大而逐漸穩定

圖6和圖7展示了不同李雅普諾夫控制參數下的平均能耗和平均隊列長度，驗證了能耗與隊列長度之間存在折中關系。其中，圖6和圖7中橫坐標是李雅普諾夫控制參數，是沒有量綱的常量。圖6中縱坐標是平均能耗，單位是焦耳每時隙(J/slot)，圖7中縱坐標是平均隊列長度，跟圖5縱坐標情況類似，因此未在圖中標明坐標。

圖6 平均能耗隨V的變化

圖7 平均隊列長度隨V的變化

從圖6中可以看出，平均能耗隨控制參數的增大而減小。這是因為控制參數取值增大，導致李雅普諾夫偏差加罰函數中能耗的比重增大，在優化過程中能獲得更低的能耗。同時，當用戶數量增加時，能耗隨之增大。

從圖7中可以看出，平均隊列長度隨控制參數的增大而增大。這是因為控制參數取值增大，李雅普諾夫偏差加罰函數中隊列的比重相對降低，在求解優化問題的過程中導致隊列長度變大。同時，用戶數量增加時，平均隊列長度隨之增大，這是因為在有限的資源下，用戶數量增大造成每個用戶獲取的資源變少，導致隊列變大。

4 結束語

在無人機無線網絡場景中，對最小化能耗的無線與計算資源分配問題進行研究，考慮數據隊列與任務隊列的穩定性約束，利用李雅普諾夫優化理論對問題進行轉換，并分解為凸優化問題進行求解。仿真結果表明，利用所提方案，能夠保證隊列的穩定性，并分析了能耗和隊列長度之間可控的折中關系，通過調整李雅普諾夫參數V的數值大小，可以按需降低能耗或者降低隊列長度。