移動邊緣計算系統中無人機和用戶的分層博弈優化方法*

崔 巖，姚 葉

（中國人民解放軍陸軍工程大學 通信工程學院，江蘇 南京 210007）

0 引言

近年來，VR/AR、自動駕駛等飛速發展。此類應用會在短時間內產生大量數據，且對時延的要求很高，但移動設備無法配備足夠的計算資源和能量資源進行處理。作為5G/B5G 中的一種新興技術，移動邊緣計算被提出來解決這一難題[1]。移動邊緣計算通過將計算、控制和存儲移動到網絡邊緣，使得資源受限的移動設備獲得對計算密集型任務和時延敏感型任務的支持。

傳統的邊緣計算服務器通常部署在固定的地方（如基站），降低了移動邊緣計算系統的靈活性。而無人機部署靈活、易于管理、成本低廉，引入移動邊緣計算中能帶來諸多潛在的增益[2]。例如，由于無人機與地面用戶之間遮擋較少，因此兩者通常能夠建立視距傳輸鏈路[3]。此外，當地面情況惡劣（如自然災害）時，無人機也可以快速、低成本地提供邊緣計算服務。

傳統的集中式優化往往需要大量的信息交互，復雜度較高且不能反映個體訴求。而在博弈模型中，每個個體都能獨立做出適合自己的策略。合理的博弈模型能減少甚至消除用戶之間的信息交互，且能以較低復雜度的算法解決問題[4]。但是，現階段用博弈論解決使用無人機的移動邊緣計算系統中問題的論文還很少，且多僅考慮了地面用戶和無人機資源的異構性及用戶不同的利益訴求，少有文章充分考慮無人機的動態性。良好的動態性是無人機相比于傳統的地面基站最大優勢之一。因此，基于博弈論思想，本文提出一種聯合優化方案，充分考慮無人機的動態性和用戶的利益訴求，建立斯坦伯格博弈模型，優化無人機的位置，從而進一步提高多無人機為傳統的移動邊緣計算系統帶來的潛在增益，最后證明了納什均衡解的存在性，并找到了納什均衡點[5]。

1 系統模型

如圖1 所示，這是一個多無人機為多地面用戶提供邊緣計算服務的場景。其中，地面用戶i∈I={1,2,…,I}分布在任務區域A中，無人機n∈N={1,2,…,N}在空中為地面用戶提供邊緣計算服務。以A的左下角為坐標原點，建立三維空間直角坐標系，則地面用戶i的坐標可表示為li=(xi,yi,0)，無人機n的坐標可表示為ln=(xn,yn,h)。在地面用戶集合I中，每個地面用戶i都有一個計算密集型任務ψi=(di,Fi)亟待處理，其中di代表該計算任務的數據量（bit），Fi代表完成該計算任務所需的CPU 周期數。

本文考慮無人機和地面用戶建立了視距傳輸鏈路，因此信道增益可以表示如下：

其中||·||表示歐氏距離，di,n為無人機n和地面用戶i之間的距離。β0表示參考距離為1 m 時的信道增益。

圖1 多無人機多地面用戶系統模型

1.1 本地計算模型

當地面用戶i在本地處理計算任務時，用表示其CPU 頻率，用ei表示每CPU 周期的能耗，則可得到任務處理時間和任務處理能耗分別為：

因此，可得到本地計算總開銷為：

其中表示時間權重因子，表示能耗權重因子，。權重因子反映了系統對時延和能耗的敏感程度。

1.2 卸載模型

無人機i的卸載策略ai包括兩部分：卸載到哪個無人機上？從無人機處請求多少計算資源？可用分別表示這兩個子策略，即，其中∈{0,1,…,N}表示地面用戶i選擇卸載到的無人機。當時，表示地面用戶i選擇了在本地處理任務。表示地面用戶i從無人機n處請求的計算資源量（CPU 周期數/單位時間）。

計算地面用戶i的卸載開銷前，首先定義地面用戶卸載時受到的干擾。在無人機集合N中，每個無人機n提供有限的頻譜資源，即有限的正交子載波c∈C={1,2,…,C}。當多個地面用戶通過同一信道進行卸載時，它們會相互干擾[6]。用∈C表示地面用戶i卸載時使用的信道，則地面用戶i在卸載到無人機n時受到的干擾表示為：

其中pj是地面用戶j的發射功率。本文考慮地面用戶采取固定的信道選擇策略，由此可得到地面用戶i卸載過程中的信噪比：

其中σ0為背景噪聲功率。因此，地面用戶i的卸載速率為：

其中B表示地面用戶i的信道帶寬，則地面用戶i卸載時的上傳時間、上傳能耗分別為：

假設地面用戶i向無人機n請求的計算資源量為，那么完成其計算任務ψi所需的時間為：

由此得到地面用戶i選擇卸載時的總時延為：

綜上，當地面用戶i選擇卸載時，付出的總計算開銷為總時延和能耗的加權和表示如下：

當地面用戶i從無人機n處請求計算資源時，需要按照無人機n對其計算資源的定價支付一定的價錢。當無人機n的定價是ηn時，地面用戶i為計算資源付出的成本為：

綜上所述，當地面用戶i將計算任務卸載到無人機時，付出的總開銷包括總計算開銷和為計算資源付出的價格兩部分：

綜合1.1 和1.2 兩部分內容，可得到地面用戶i完成計算任務ψi所需的總開銷為：

其中t{·}為指示函數。當條件{·}為真時，指示函數t{·}取值為1；反之，指示函數t{·}取值為0。

1.3 無人機的收益模型

本文中無人機搭載邊緣計算服務器，有償為地面用戶提供計算卸載服務。本文僅考慮無人機為地面用戶提供計算資源獲得的收益，因此當無人機n的定價為ηn時，獲得的收益為：

此外，無人機也應適當調整位置ln，位置的改變將影響信道質量，進而影響其服務質量。因此，無人機n的策略bn=(ln,ηn)。

2 博弈模型和問題形成

在使用無人機的移動邊緣計算系統中，地面用戶通過優化自身的卸載策略、請求的資源量，使開銷最小化。而搭載了邊緣計算服務器的無人機由移動運營商提供，目的在于在合適的位置以合理的定價提供計算資源，從而獲得更高的收益。作為移動邊緣計算系統中的兩大核心部分，兩者的利益訴求不一樣。同時，作為服務提供者，搭載邊緣計算服務器的無人機通常更具主動性。因此，針對系統中不同用戶的優先級和需求的差異性，采用分層博弈模型能有效刻畫地面用戶的策略和無人機的策略對系統性能的影響。斯坦伯格博弈是一種典型的分層博弈[7]，模型中包含具有高優先級別、先行動的領導者以及觀測領導者決策信息而后行動的跟隨者。本文將采用多領導者-多跟隨者斯坦伯格博弈建模分析地面用戶和無人機的決策行為。其中，無人機被建模為領導者，地面用戶被建模為跟隨者。不失一般性地，無人機和地面用戶都被建模為自私且理性的博弈參與者。該多領導者-多跟隨者斯坦伯格博弈表示如下：

（1）博弈參與者：無人機被建模為領導者，擔任邊緣服務器的角色，地面用戶被建模為跟隨者擔任用戶的角色。

（2）策略：無人機n的策略bn=(ln,ηn)，其中ln=(xn,yn,h)表示無人機的三維坐標，ηn表示無人機n對每CPU 周期的定價。地面用戶i的策略，其中∈{0,1,…,N}表示地面用戶i卸載到的無人機，=0 時表示地面用戶i選擇在本地處理其計算任務，表示地面用戶i從無人機n處請求的計算資源量。

（3）效用函數：對于無人機來說，效用函數為其提供計算資源得到的收益，而地面用戶的效用函數則為其總開銷。

首先，定義領導者（無人機）的效用函數為向地面用戶提供計算資源得到收益：

無人機通過調整其位置和對計算資源的定價，尋求收益的最大化。因此，無人機之間的非合作博弈模型可描述為：

其中b={b1,b2,…,bN}表示無人機的聯合策略。

定義跟隨者（地面用戶）的效用函數，構建基于局部互利的博弈模型，即用戶在做決策的時候會考慮其鄰居用戶[8]。所謂鄰居，指對于地面用戶i來說，當它選擇卸載到無人機時，如果存在一個地面用戶j∈I{i}與其使用相同的信道，則兩者互為鄰居。由此可定義地面用戶i的效用函數為地面用戶i和其鄰居的總開銷之和：

其中Vi(ai,a-i)是地面用戶i的總開銷。該局部互利博弈模型可以表示為：

其中a={a1,a2,…,aI}表示地面用戶的聯合策略。

3 納什均衡分析

3.1 對跟隨者（地面用戶）進行分析

定理1：局部互利博弈Gf是一個精準勢博弈，至少有一個純策略的納什均衡解。

證明：首先構造下面的勢能函數：

當任意地面用戶i的策略單方面地從ai變更為時，則該地面用戶的效用函數的改變量如下：

即策略改變導致的勢函數之差等于效用函數之差，因此該博弈為精準勢博弈，定理1 成立。

3.2 對領導者（無人機）進行分析

本文以無人機的收益作為其效用函數，且僅考慮無人機為地面用戶提供計算資源獲得的收益，而不考慮其他收益和開銷。定理1 表明，地面用戶層構成的局部互利博弈模型存在均衡解，而無人機的收益就是地面用戶為計算資源付出的開銷，如式（16）所示。因此，地面用戶層存在均衡解就意味著無人機層同樣存在均衡解。

最后，本文基于最佳響應算法[5]找到這一均衡點。無人機作為領導者根據對地面用戶策略的預判，根據最佳響應作出收益最大化的決策[9]，然后地面用戶以無人機的策略b＊為條件進行策略優化。如此反復，直至均衡。

4 仿真分析

本節通過仿真驗證了所提方案的性能。仿真參數設置如下：A=50 m×50 m、N=5、I=100、B=5×106Hz、C=5。圖2 展示了地面用戶的開銷和無人機收益的收斂情況。相較于初始情況（所有地面用戶均本地處理），本方案在數次迭代后顯著降低了地面用戶的開銷，并提高了無人機收益。圖2中迭代曲線在后期的波動是因為本方案最終收斂到局部最優點，而該系統的局部最優點并不唯一。

圖2 地面用戶開銷和無人機收益的收斂情況

圖3 展示了不同信道數下，本方案基于最佳響應和隨機選擇下收斂結果的差異性。曲線表明，基于最佳響應的方案優化效果更好。可以看出，隨著信道數的增加，地面用戶的開銷顯著降低，且基于最佳響應的方案降幅更大，但隨著信道數的增加，無人機的收益并沒有明顯變化。這是由于該參數設置下，幾乎所有的地面用戶都已將計算任務卸載到無人機上進行計算，信道數的增加無法吸引到新用戶，再加上無人機之間的競爭，使得其收益沒有顯著變化。

圖3 不同信道數下地面用戶開銷和無人機收益情況

圖4 展示了在地面用戶均勻分布、正態分布、指數分布3 種分布方式下，地面用戶的開銷和無人機收益的收斂情況。柱狀圖表明，不同的分布方式下，基于最佳響應的方案相較于基于隨機選擇的方案，無論是地面用戶的開銷，還是無人機收益，都更具優勢。

圖4 不同分布方式下地面用戶開銷和無人機收益情況

5 結語

本文考慮了一個多無人機多地面用戶的移動邊緣計算場景，建立了斯坦伯格博弈模型。無人機被建模為領導者，通過優化位置和對計算資源的定價，使自身收益最大化；地面用戶被建模為跟隨者，通過優化卸載策略和請求的計算資源量，使自身開銷最小化。最后，仿真結果驗證了本方案的有效性，方案能有效降低地面用戶的開銷，提高無人機的收益。