基于混合策略博弈的無人機(jī)輔助移動(dòng)邊緣計(jì)算任務(wù)卸載

摘 要：在單無人機(jī)輔助的移動(dòng)邊緣計(jì)算系統(tǒng)中， 為使無人機(jī)能服務(wù)于大區(qū)域中的所有用戶設(shè)備， 可將大區(qū)域分成多個(gè)子區(qū)域， 并設(shè)定無人機(jī)以固定路線在各個(gè)子區(qū)域間飛行來為用戶設(shè)備提供計(jì)算服務(wù)。 考慮到用戶設(shè)備計(jì)算資源較匱乏且無人機(jī)覆蓋區(qū)域外的用戶可選擇移動(dòng)至覆蓋區(qū)域內(nèi)進(jìn)行任務(wù)卸載以最大化自身效用， 可將用戶設(shè)備的部分卸載問題轉(zhuǎn)化為每個(gè)用戶設(shè)備的效用最大化問題， 并利用混合策略博弈和子模博弈來分別確定用戶設(shè)備的移動(dòng)概率和卸載數(shù)據(jù)量， 從而得出最優(yōu)卸載策略， 且分別證明了混合策略納什均衡和純策略納什均衡的存在性。 仿真結(jié)果表明， 所提方案與MBO（Binary Offloading Based on Mixed Strategy Game）等經(jīng)典方案相比可有效提高用戶設(shè)備的效用， 并驗(yàn)證了其收斂性和穩(wěn)定性。

關(guān)鍵詞：無人機(jī)； 移動(dòng)邊緣計(jì)算； 計(jì)算卸載； 混合策略博弈； 子模博弈

中圖分類號(hào)：TJ760； V279

文獻(xiàn)標(biāo)識(shí)碼： A

文章編號(hào)：1673-5048（2024）04-0112-09

DOi： 10.12132/iSSN.1673-5048.2023.0246

0 引 言

無人機(jī)（Unmanned Aerial Vehicle， UAV）因其具有靈活性高、 成本低、 魯棒性強(qiáng)等諸多優(yōu)點(diǎn)， 已廣泛滲透至交通監(jiān)管、 公共安全、 搜救等多個(gè)行業(yè)。 由于無人機(jī)的高海拔使無線設(shè)備能夠有效地建立通信鏈路， 從而減輕潛在的信號(hào)阻塞和陰影， 因此無人機(jī)可以充當(dāng)無線中繼或空中基站， 擴(kuò)大地面無線設(shè)備的覆蓋范圍［1］， 這一優(yōu)勢也促進(jìn)了其在物聯(lián)網(wǎng)和邊緣計(jì)算等新一代通信技術(shù)中的推廣應(yīng)用。

移動(dòng)邊緣計(jì)算（Mobile Edge Computing， MEC）是為解決終端設(shè)備資源匱乏， 無法滿足各類時(shí)延敏感型和計(jì)算密集型任務(wù)需求的問題而提出的一種有效方法［2］。 將計(jì)算任務(wù)卸載到離終端設(shè)備更近的MEC服務(wù)器， 不僅為任務(wù)的執(zhí)行提供了較充足的計(jì)算資源， 而且相比云計(jì)算， 在傳輸過程中產(chǎn)生的時(shí)延和能耗成本也顯著降低。 相對(duì)于固定的邊緣服務(wù)， UAV搭載的邊緣服務(wù)器具有更高的靈活性， 可以獲得良好的空對(duì)地視距［3］。 此外， 突發(fā)事件發(fā)生時(shí)， 在基站受損、 地面服務(wù)器難以快速部署的情況下， UAV輔助的MEC系統(tǒng)可以很好地彌補(bǔ)傳統(tǒng)邊緣服務(wù)器的不足， 為用戶提供靈活且高質(zhì)量的計(jì)算服務(wù)。

目前已有很多相關(guān)UAV輔助的MEC系統(tǒng)的研究。 文獻(xiàn)［4］研究了UAV輔助的MEC系統(tǒng)中相關(guān)公平感知的任務(wù)數(shù)據(jù)分配和軌跡優(yōu)化問題， 目的在于最小化移動(dòng)終端的能耗。 文獻(xiàn)［5］解決了非均勻異構(gòu)蜂窩網(wǎng)絡(luò)移動(dòng)用戶的計(jì)算卸載問題， 提出一種面向小區(qū)邊緣移動(dòng)用戶的基站協(xié)作和地空卸載方案， 并采用定期調(diào)度的方式使邊緣用戶可在地面基站和無人機(jī)之間進(jìn)行選擇卸載。 此外， 該文也提出了分析頻譜效率和平均網(wǎng)絡(luò)吞吐量的框架。 文獻(xiàn)［6］設(shè)計(jì)了一個(gè)基于貪婪算法的無人機(jī)軌跡模型來預(yù)測用戶坐標(biāo)， 并為用戶選擇合適的邊緣服務(wù)器進(jìn)行卸載， 從而聯(lián)合優(yōu)化無人機(jī)的通信、 緩存和計(jì)算的能源效率。 文獻(xiàn)［7］通過聯(lián)合優(yōu)化用戶關(guān)聯(lián)和無人機(jī)部署， 最小化MEC排隊(duì)延遲， 從而降低任務(wù)的平均延遲。 此外， 引入了最優(yōu)傳輸理論來分析用戶關(guān)聯(lián)子問題， 采用經(jīng)典粒子群優(yōu)化算法來優(yōu)化無人機(jī)部署。 文獻(xiàn)［8］研究了一種基于蜂窩連接的多UAV輔助的MEC網(wǎng)絡(luò)， 聯(lián)合優(yōu)化無人機(jī)-地面基站的關(guān)聯(lián)卸載、 無人機(jī)發(fā)射功率、 無人機(jī)軌跡和能量收集時(shí)間， 從而最小化無人機(jī)的總能量消耗， 并提出一種基于聯(lián)合塊坐標(biāo)下降的資源分配和無人機(jī)軌跡算法， 以解決整體優(yōu)化問題。 上述文獻(xiàn)主要解決的是最小化UAV輔助的MEC網(wǎng)絡(luò)中的任務(wù)執(zhí)行能耗和時(shí)延等成本問題， 并未考慮設(shè)備在卸載過程中的收益， 而且大部分文獻(xiàn)都以研究UAV的移動(dòng)軌跡為主， 而較少研究可移動(dòng)用戶設(shè)備之間的協(xié)作。

博弈論可解決在多個(gè)決策主體間存在利益沖突的情況下， 利益相關(guān)者或參與者如何根據(jù)決策者自身的能力和決策者掌握的信息做出有利于決策者自身的決策， 適用于MEC場景中各個(gè)用戶之間決策相互影響的情況。 文獻(xiàn)［9］通過最小化系統(tǒng)中多個(gè)UAV的總能耗來確定任務(wù)的卸載目標(biāo)， 提出服務(wù)器選擇博弈算法SSGT， 并提出一種卸載激勵(lì)機(jī)制為MEC服務(wù)器的資源定價(jià)， 將無人機(jī)的能耗和移動(dòng)用戶的意愿建模為Stackelberg博弈， 基于算術(shù)下降的多輪迭代博弈算法來實(shí)現(xiàn)最優(yōu)解。 文獻(xiàn)［10］提出一個(gè)針對(duì)UAV輔助的MEC系統(tǒng)中基于非合作博弈的兩階段計(jì)算卸載策略。 第一階段通過動(dòng)態(tài)調(diào)整移動(dòng)用戶的CPU頻率和傳輸功率， 實(shí)現(xiàn)社會(huì)效益的最大化； 第二階段針對(duì)無人機(jī)計(jì)算資源的分配進(jìn)行優(yōu)化， 旨在最小化無人機(jī)在此過程中的能源消耗。 文獻(xiàn)［11］提出一種基于博弈論的GTCS方法， 用于在MEC和無人機(jī)網(wǎng)絡(luò)中選擇最合適的無人機(jī)服務(wù)提供商。 通過考慮用戶需求和無人機(jī)提供商的特點(diǎn)、 限制和價(jià)格， 利用博弈論選擇最佳的服務(wù)提供商。 文獻(xiàn)［8］提出一種在災(zāi)難或偏遠(yuǎn)地區(qū)為物聯(lián)網(wǎng)設(shè)備提供空中計(jì)算服務(wù)的計(jì)算框架。 首先基于匹配博弈理論處理物聯(lián)網(wǎng)設(shè)備到無人機(jī)的卸載決策， 然后利用啟發(fā)式算法處理無人機(jī)和高空平臺(tái)之間的卸載決策。 上述文獻(xiàn)說明利用博弈論算法解決計(jì)算卸載問題可以更全面地考慮卸載過程中其他用戶以及無人機(jī)對(duì)用戶決策帶來的影響是可靠且有效的。

本文主要研究了無人機(jī)輔助的移動(dòng)邊緣網(wǎng)絡(luò)中的計(jì)算卸載策略。 為了使區(qū)域內(nèi)所有用戶設(shè)備（User Equipments， UEs）都有卸載任務(wù)至UAV的機(jī)會(huì)， 規(guī)定無人機(jī)按照固定路線飛行過所有子區(qū)域， 并且服務(wù)區(qū)域外的UE可根據(jù)自身效用情況判斷是否移動(dòng)到該時(shí)隙的UAV服務(wù)覆蓋范圍。 首先利用混合策略博弈計(jì)算UE的移動(dòng)概率， 并結(jié)合UE和UAV的偏好函數(shù)構(gòu)建雙邊匹配博弈， 確定區(qū)域內(nèi)可服務(wù)的UE。 然后將UE的部分卸載問題轉(zhuǎn)化為每個(gè)UE的效用最大化問題， 并作為UE之間的非合作博弈進(jìn)行處理。 在子模博弈理論的基礎(chǔ)上， 證明了該非合作博弈存在純納什均衡點(diǎn)， 并利用最佳響應(yīng)算法獲得UE的最佳卸載數(shù)據(jù)量。

1 系統(tǒng)模型

圖1給出了一個(gè)包含多個(gè)UE和搭載MEC服務(wù)器的UAV的兩層網(wǎng)絡(luò)架構(gòu)， 其中UE的集合可表示為K{1， 2， …， K}。 該網(wǎng)絡(luò)模型利用軟件定義網(wǎng)絡(luò)（Software Defined Network， SDN）技術(shù)實(shí)現(xiàn)了集中式的控制和資源管理， 使得基于UAV的MEC系統(tǒng)能夠高效地為服務(wù)覆蓋區(qū)域內(nèi)的UE提供服務(wù)。 系統(tǒng)內(nèi)的基站可以將包括UE位置、 UAV位置、 數(shù)據(jù)信息等實(shí)時(shí)信息進(jìn)一步分發(fā)給各UE和UAV， 進(jìn)行所需的信息交換。 基于這一機(jī)制， 設(shè)UAV能夠獲取服務(wù)區(qū)域內(nèi)所有UE設(shè)備的先驗(yàn)信息。

設(shè)定系統(tǒng)在T時(shí)隙序列中運(yùn)行， 整個(gè)序列可定義為T{1， 2， …， T}。 第k個(gè)UE在每個(gè)時(shí)隙都有一個(gè)需要執(zhí)行的任務(wù)， 可具體表示為fk（t）={bk（t）， ak（t）}， 其中： bk（t）為計(jì)算任務(wù)所需輸入的數(shù)據(jù)量； ak（t）表示任務(wù)的計(jì)算密度， 即計(jì)算任務(wù)所需的CPU周期與任務(wù)數(shù)據(jù)量之間的比例。 由于UAV服務(wù)的區(qū)域一般較大， 為了讓大面積區(qū)域內(nèi)所有UE都有被服務(wù)的機(jī)會(huì)， 整個(gè)區(qū)域被平均分割成若干個(gè)子區(qū)域， 并設(shè)定UAV采用巡邏的方式在各個(gè)子區(qū)域之間按照固定路線飛行。 出于服務(wù)的公平性， UAV處理任務(wù)時(shí)懸停于每個(gè)子區(qū)域的中心位置的正上方。 由于UE自身資源有限且每個(gè)UE都是自私的， 為了獲得UAV的服務(wù)權(quán)限， 服務(wù)覆蓋區(qū)域之外的UE有可能會(huì)移動(dòng)到UAV的覆蓋區(qū)域， 將部分任務(wù)進(jìn)一步傳輸?shù)経AV上的MEC服務(wù)器來執(zhí)行， 而這樣會(huì)導(dǎo)致選擇移動(dòng)的UE與原本在服務(wù)覆蓋范圍內(nèi)的UE在資源上競爭， 因此需要制定一個(gè)有效的移動(dòng)策略使得每個(gè)UE都能獲得最大的收益。

系統(tǒng)中的每個(gè)時(shí)隙都可以分割為兩個(gè)部分： 第一部分為UAV的飛行時(shí)間tf； 第二部分為UE的任務(wù)處理時(shí)間tp。 考慮一個(gè)3維的歐幾里得空間， 設(shè)定UAV在UE的任務(wù)處理時(shí)間內(nèi)保持固定位置且具體位置可以表示為s（t）=［x（t）， y（t）， H］， 其中： x（t）， y（t）表示UAV在時(shí)隙t的水平位置； H為UAV的固定飛行高度。 為了防止UE無法接收到任務(wù)處理的結(jié)果， tp不小于UE移動(dòng)的最大時(shí)延以及執(zhí)行任務(wù)的最大時(shí)延之和。 移動(dòng)最大時(shí)延和任務(wù)執(zhí)行最大時(shí)延分別用離UAV最遠(yuǎn)的UE移動(dòng)至服務(wù)覆蓋區(qū)域的時(shí)間和所有UE本地執(zhí)行任務(wù)的最大時(shí)延來表示， 即tp≥Tmo， max（t）+Tl， max（t）。 第k個(gè)UE在第t個(gè)時(shí)隙的位置為wk（t）=［xk（t）， yk（t）］， 可得UAV與各個(gè)UE之間的空間距離為dk（t）=H2+（x（t）－xk（t））2+（y（t）－yk（t））2， 水平距離為lk（t）=（x（t）－xk（t））2+（y（t）－yk（t））2。

1.1 通信模型

設(shè)定UAV與UE之間的通信信道為視距（Line of Sight， LOS）傳輸鏈路［12］， 對(duì)每個(gè)時(shí)隙t， UAV和UE之間的信道功率增益為

hk（t）=g0·（dk（t））－2 （1）

式中： g0為基準(zhǔn)距離等于1 m的情況下的信道增益。 設(shè)定系統(tǒng)采用正交頻分多址的通信制式并且具有服務(wù)權(quán)限的UE平均分配MEC服務(wù)器中的資源， 那么在第t個(gè)時(shí)隙， 第k個(gè)UE與UAV之間的信息傳輸速率可表示為

rk（t）=BY·log21+τk·hk（t）N0（2）

式中： B為系統(tǒng)帶寬； Y為UAV在一個(gè)時(shí)隙內(nèi)可以服務(wù)的UE數(shù)量； τk為第k個(gè)UE的傳輸功率； N0為白噪聲功率。 若第k個(gè)UE選擇將任務(wù)卸載到UAV搭載的MEC服務(wù)器上處理， 則上行鏈路的傳輸時(shí)延可表示為

Tutk（t）=buk（t）rk（t）（3）

式中： buk（t）表示第k個(gè)UE在時(shí)隙t卸載至UAV的數(shù)據(jù)量。 在卸載過程中UE的能耗為上行鏈路所需要的傳輸能耗。 需要說明的是， 由于任務(wù)處理結(jié)果的數(shù)據(jù)量一般較小， 因此本文不考慮UE接收任務(wù)處理結(jié)果需要的時(shí)間和消耗的能量。 在此情況下， 傳輸能耗可以表示為

Eutk（t）=τk·buk（t）rk（t）（4）

1.2 計(jì)算模型

設(shè)定UE所需執(zhí)行的任務(wù)可任意劃分為兩部分， 由于UE的能量不足且計(jì)算資源有限， 所以當(dāng)UE位于UAV的服務(wù)范圍時(shí)， 為了減小能耗和時(shí)延成本并獲得最大收益， 可將部分任務(wù)卸載至UAV上的MEC服務(wù)器進(jìn)行計(jì)算。 定義fu為UAV搭載的MEC服務(wù)器的計(jì)算頻率， Y為UAV每時(shí)隙可以服務(wù)的UE數(shù)量， 并且計(jì)算資源同樣平均分配給每一個(gè)確定卸載的UE， 那么可得MEC服務(wù)器在第t個(gè)時(shí)隙處理第k個(gè)UE任務(wù)的計(jì)算時(shí)延為

Tuek（t）=buk（t）·ak（t）·Yfu（5）

在UE卸載部分任務(wù)至MEC服務(wù)器的同時(shí)， UE本地也需執(zhí)行未傳輸至服務(wù)器的部分任務(wù)。 UE本地執(zhí)行剩余任務(wù)的時(shí)延和能耗為

Tulk（t）=（bk（t）－buk（t））·ak（t）fk（6）

Eulk（t）=κ·（fk）2·（bk（t）－buk（t））·ak（t）（7）

式中： fk為第k個(gè)UE的計(jì)算頻率； κ為CPU的有效電容系數(shù)（其取決于其處理芯片的結(jié)構(gòu)）。 結(jié)合通信模型和計(jì)算模型可以得到， UE在MEC上的計(jì)算時(shí)延為

Tutek（t）=Tutk（t）+Tuek（t）（8）

當(dāng)UE選擇以部分卸載的方式執(zhí)行任務(wù)時(shí)， UE的任務(wù)執(zhí)行時(shí)延需要綜合考慮本地執(zhí)行的時(shí)延Tulk（t）和卸載至MEC服務(wù)器執(zhí)行的總時(shí)延Tutek（t）， 并取兩者中的最大值作為任務(wù)執(zhí)行的實(shí)際時(shí)延。 而部分卸載時(shí)UE的任務(wù)執(zhí)行能耗則是UE本地的計(jì)算能耗Eulk（t）與其傳輸能耗Eutk（t）之和。 因此當(dāng)UE選擇將任務(wù)卸載至MEC服務(wù)器時(shí)， 任務(wù)執(zhí)行時(shí)延和能耗可分別表示為

Tuk（t）=max{Tulk（t）， Tutek（t）}（9）

Euk（t）=Eulk（t）+Eutk（t）（10）

當(dāng)UE未在UAV的服務(wù)覆蓋范圍內(nèi)時(shí)， 便無法傳輸任務(wù)至UAV處理， 只能在本地執(zhí)行任務(wù)。 那么可以得到第k個(gè)UE在任務(wù)全部本地執(zhí)行情況下的計(jì)算時(shí)延和計(jì)算能耗為

Tlk（t）=bk（t）·ak（t）fk（11）

Elk（t）=κ·（fk）2·bk（t）·ak（t）（12）

考慮到UE電量有限， 需設(shè)定相關(guān)參數(shù)以權(quán)衡任務(wù)執(zhí)行過程中的能量消耗和時(shí)間延遲。 設(shè)qk， to是第k個(gè)UE的電池總?cè)萘浚?qk， re（t－1）是第k－1個(gè)時(shí)隙UE的剩余電量。 當(dāng)UE不移動(dòng)時(shí)， 單個(gè)時(shí)隙UE電量平均下降m1， 則UE的剩余電量比為λ（t）=（qk， re（t－1）－m1）/qk， to。 而當(dāng)UE移動(dòng)時(shí)， 單個(gè)時(shí)隙UE電量平均下降m2， 剩余電量比為λ（t）=（qk， re（t－1）－m2）/qk， to。 當(dāng)設(shè)備電量充足時(shí)， 時(shí)延是首先要考慮的因素； 相反， 當(dāng)設(shè)備電量不足時(shí)， 應(yīng)首先考慮降低能耗。 若將剩余功率的時(shí)延加權(quán)系數(shù)定義為ρk， delay（t）=ln［λ（t）（ew－1）+1］， 則能耗加權(quán)系數(shù)為ρk， energy（t）=1－ρk， delay（t）， 其中w為自定義加權(quán)系數(shù)［13］。 由此可得任務(wù)在UAV和本地執(zhí)行過程中能耗和時(shí)延的加權(quán)和分別為

Cuk（t）=ρk， delay（t）·Tuk（t）+ρk， energy（t）·Euk（t）（13）

Clk（t）=ρk， delay（t）·Tlk（t）+ρk， energy（t）·Elk（t）（14）

1.3 收益模型

考慮到若一個(gè)任務(wù)需要在MEC服務(wù)器上進(jìn)行大量計(jì)算處理， 則會(huì)導(dǎo)致任務(wù)處理的成本較高， 同時(shí)執(zhí)行該任務(wù)的UE獲得的回報(bào)也會(huì)較少。 因此， 用回報(bào)率表示UE在MEC服務(wù)器遠(yuǎn)程執(zhí)行其任務(wù)獲得的收益， 并設(shè)定回報(bào)率函數(shù)ror（N）相對(duì)于UE的歸一化有效需求N是連續(xù)單調(diào)遞減的［14］。 若UE的歸一化有效需求N較高， 則意味著MEC服務(wù)器的計(jì)算資源被過度利用， UE通過服務(wù)器處理數(shù)據(jù)獲得的滿意度會(huì)降低。 結(jié)合上述回報(bào)率特征， UE在MEC服務(wù)器處得到的回報(bào)率函數(shù)可表述如下：

ror（N）=2－ln（1+N）（15）

式中： N表示UE的歸一化有效需求， 其將來自MEC服務(wù)器的UE的實(shí)際計(jì)算需求映射到0到1之間［14］， 具體公式如下：

N（buk（t））=－1+21+e－θ∑Kk=1（bk（t）ak（t））buk（t）bk（t），

N（buk（t））∈［0， 1］（16）

式中： θ為一個(gè)正常數(shù)， 可以用于校準(zhǔn)函數(shù)曲線并以此捕獲MEC服務(wù)器的計(jì)算能力。 在實(shí)際實(shí)現(xiàn)中， 服務(wù)器向UE廣播歸一化有效需求N的數(shù)值， 以顯示MEC服務(wù)器的使用程度， 方便UE進(jìn)行下一步卸載決策。

2 優(yōu)化問題描述

聯(lián)合考慮UE的回報(bào)率以及任務(wù)執(zhí)行時(shí)的能耗和時(shí)延成本， 可得在時(shí)隙t第k個(gè)UE的效用函數(shù)為

Uk（t）=W0+buk（t）·ror（N）－φ·Cuk（t）， xk（t）=1W0－φ·Clk（t）， xk（t）=0（17）

式中： xk（t）為時(shí)隙t第k個(gè)UE的卸載決策， xk（t）=1表示UE將部分任務(wù)卸載至MEC服務(wù)器執(zhí)行， xk（t）=0表示UE本地執(zhí)行全部任務(wù)； φ為能耗和時(shí)延成本的懲罰系數(shù)； W0為一個(gè)大于最大φ·Clk（t）的常數(shù)， 用于均衡不同卸載決策下UE的收益。 當(dāng)UE選擇將部分任務(wù)卸載至MEC服務(wù)器時(shí)， 其效用可表示為UE卸載至MEC服務(wù)器獲得的回報(bào)率與卸載過程中所花費(fèi)的時(shí)延和能耗成本的加權(quán)和的差值與W0之和。 當(dāng)UE選擇在本地執(zhí)行全部任務(wù)時(shí)， 其效用為本地任務(wù)執(zhí)行的成本相較最大任務(wù)執(zhí)行成本的減小量與成本懲罰系數(shù)的乘積。

綜合分析可得， 若需獲得UE卸載策略， 首先要確定UE在該時(shí)隙是否需要進(jìn)行卸載。 若UE移動(dòng)成本以及其他UE的影響大于卸載帶來的效用， 則UE會(huì)在本地執(zhí)行任務(wù)； 若UE的卸載效用足夠大， 即UE確定要進(jìn)行卸載， 再進(jìn)一步計(jì)算得出UE最優(yōu)的卸載數(shù)據(jù)量。 然而該問題涉及到對(duì)卸載決策和卸載數(shù)據(jù)量的同時(shí)優(yōu)化， 較難直接解決， 而且每個(gè)時(shí)隙UE任務(wù)的隨機(jī)性、 異構(gòu)性以及移動(dòng)決策的不透明性， 使得整個(gè)系統(tǒng)變得更加隨機(jī)， 也進(jìn)一步增加了解決問題的難度。 可將問題的解決分為兩個(gè)部分： 第一部分設(shè)計(jì)了一個(gè)基于混合策略博弈的用戶設(shè)備卸載決策模型， 首先固定UE的卸載數(shù)據(jù)量并計(jì)算所有UE的移動(dòng)概率， 然后通過UE和UAV的偏好函數(shù)確定卸載至MEC服務(wù)器的UE； 第二部分基于非合作博弈理論闡述部分卸載問題， 得到UE的最優(yōu)卸載數(shù)據(jù)量， 并基于子模博弈理論證明該博弈純納什均衡的存在性， 最終實(shí)現(xiàn)UE效用最大化的目標(biāo)。

3 優(yōu)化問題求解

3.1 基于混合策略博弈的用戶設(shè)備卸載決策

考慮到系統(tǒng)會(huì)通過衡量UE移動(dòng)后的效用來決定UE是否進(jìn)行移動(dòng)和卸載， 先引入混合策略博弈方法， 根據(jù)UE移動(dòng)后的效用計(jì)算出UE的移動(dòng)概率， 再進(jìn)一步結(jié)合UE和UAV的偏好函數(shù)， 利用雙邊匹配博弈最終確定UE卸載決策。 為了方便計(jì)算， 可在初始化階段固定UE的卸載數(shù)據(jù)量buk（t）。

首先將基本的計(jì)算卸載博弈模型定義為G1{K， （Pk， mo（t））k∈K， （Rk）k∈K}， 其中： Pk， mo（t）∈［0， 1］為第k個(gè)UE的移動(dòng)概率或者博弈中第k個(gè)UE的混合策略； Rk為第k個(gè)UE在收益函數(shù)Rk（P（t））中獲得的收益。 令P－k， mo（t）{P1， mo（t）， …， Pk－1， mo（t）， Pk+1， mo（t）， …， PK， mo（t）}表示除了第k個(gè)UE之外的所有UE的移動(dòng)概率， 并在該博弈中引入混合策略納什均衡概念［15］。

定義1 （混合策略納什均衡）設(shè)定Pk， mo（t）為第k個(gè)UE的最優(yōu)移動(dòng)概率， 如果沒有任何UE能夠通過改變其移動(dòng)概率來提高收益， 那么可以說移動(dòng)概率Pk， mo（t）是該博弈的混合策略納什均衡， 該均衡滿足以下條件：

Rk（Pk， mo（t）， P-k， mo（t））≥Rk（Pk， mo（t），P-k， mo（t）） （18）

定義δ和lk（t）分別表示UE的移動(dòng)懲罰系數(shù)和最小移動(dòng)距離。 結(jié)合UE的收益函數(shù)Uk， 則可得到UE進(jìn)行移動(dòng)后的卸載收益函數(shù)為

Ek（t）=Uk（t）－δ·lk（t）·Ⅱ{lk（t）>s} （19）

式中： Ⅱ{·}為指示函數(shù)， 當(dāng)且僅當(dāng)括號(hào)中的條件正確時(shí)為1， 否則為0； s為UAV的服務(wù)覆蓋范圍的最大半徑。 式（19）表示根據(jù)UE所在的位置來討論UE的卸載收益： 當(dāng)UE位于UAV的服務(wù)區(qū)域時(shí)， 則無需移動(dòng)便可以進(jìn)行任務(wù)卸載， 其卸載收益為Uk（t）； 當(dāng)UE位于其他區(qū)域時(shí)， 則需要通過移動(dòng)來爭取服務(wù)權(quán)限， 其卸載收益可以表示為Uk（t）－δ·li（t）。 將Pkj， mo表示為從第k個(gè)UE的預(yù)測中得到的第j個(gè)UE的移動(dòng)概率， 則可得到第j個(gè)UE關(guān)于Pkj， mo的偽收益函數(shù)為

Ukj（Pkj， mo（t））=（W0+buk（t）·ror（N）－φ·Cuj（t））·（Ⅱ{lj（t）>s}·Pkj， mo（t）+1－Ⅱ{lj（t）>s}）－δ·lj（t）·Ⅱ{lj（t）>s}·Pkj， mo（t）+（W0－φ·Clj（t））·Ⅱ{lj（t）>s}·（1－Pkj， mo（t））（20）

偽收益最大化問題可以定義如下：

maxPkj，moⅡ{lj（t）>s}·Pkj， mo（t）·M+Q

s.t. 0≤Pkj， mo（t）≤1（21）

式中：

M=buk（t）·ror（N）－φ·Cuj（t）－δ·lj（t）+φ·Clj（t）；

Q=（1－Ⅱ{lj（t）>s}）·（W0+buk（t）·ror（N）－φ·Cuj（t））+（W0－φ·Clj（t））·Ⅱ{lj（t）>s}。

解決上述線性規(guī)劃問題可以得到最優(yōu)移動(dòng)概率為

Pkj， mo（t）=0， Ⅱ{lj（t）>s}·Pkj， mo（t）·M+Q>0

1， others （22）

根據(jù)Pk， mo（t）和Pkj， mo（t）， 可以得出考慮移動(dòng)時(shí)UE最終的效用計(jì)算式為

Uk=（W0+buk（t）·ror（N）－φ·Cuk（t））·Pk， mo（t）－δ·lk（t）·Ⅱ{lk（t）>s}·Pk， mo（t）+（W0－φ·Clk（t））·Ⅱ{lk（t）>s}·（1－Pk， mo（t））－ρ·Pk， mo（t）2·［1－∏j≠k， j∈K（1－bj（t）∑Kk=1bk（t）·Pkj， mo（t））］ （23）

式中： ρ為其他UE對(duì)第k個(gè)UE的影響系數(shù)。 當(dāng)ρ固定時(shí)， 其他UE的移動(dòng)概率和任務(wù)數(shù)據(jù)量增加會(huì)加劇MEC服務(wù)器的資源占用情況， 從而導(dǎo)致第k個(gè)UE的卸載成本增加， 同時(shí)也會(huì)削弱UE的卸載意愿。 根據(jù)UE的效用函數(shù)， 可得最佳的卸載概率為

Pk， mo（t）=argmaxPk（t）Uk（Pk， mo（t））=

Uuk（t）－Cmk（t）·Ⅱ{lk（t）>s}－Ulk（t）·Ⅱ{lk（t）>s}2·ρ·Cojk（t）10（24）

式中： Uuk（t）=W0+ror（N）－φ·Cuk（t）；

Ulk（t）=W0－φ·Clk（t）；

Cmk（t）=δ·lk（t）；

Cojk（t）=1－∏j≠k， j∈K1－bj（t）∑Kk=1bk（t）·Pkj， mo（t）；

運(yùn)算符［x］10可以規(guī)定Pk， mo（t）的取值在0到1之間。

為了避免UE盲目移動(dòng)導(dǎo)致移動(dòng)成本過高， 可以選擇部分移動(dòng)意愿較強(qiáng)的UE參與下一步博弈。 設(shè)定μ為UE的移動(dòng)概率閾值， 只有當(dāng)Pk， mo（t）>μ時(shí)， 第k個(gè)UE才有機(jī)會(huì)進(jìn)行移動(dòng)和卸載。 為了方便接下來的計(jì)算， 這里規(guī)定位于服務(wù)覆蓋范圍內(nèi)的UE的移動(dòng)概率為1。

考慮到系統(tǒng)的效益， 可以綜合考慮UAV和UE的效用， 采用雙邊匹配算法來進(jìn)一步對(duì)可卸載的UE進(jìn)行選擇。 將考慮移動(dòng)后的UE的卸載收益定義為其偏好函數(shù)， 具體計(jì)算如下：

Xk=Uuk（t）·Pk， mo（t）－Cmk（t）·Ⅱ{lk（t）>s}·Pk， mo（t）+

Ulk（t）·Ⅱ{lk（t）>s}·（1－Pk， mo（t））（25）

對(duì)UE的偏好函數(shù)按降序排序， 形成UE的偏好表， 然后取出前2Y的UE， 形成新的UE集S。 對(duì)于UAV， 可以將選擇卸載的UE的任務(wù)數(shù)據(jù)總量作為其偏好函數(shù)， 具體可表達(dá)為

Xu（t）=∑k∈Sbk（t）·xk（t）（26）

通過搜索方法， 最終可得UE的卸載決策集合， 即

x（t）=argmaxx（t） Xu（t） （27）

式中： x（t）{x1（t）， x2（t），…， xK（t）}。 最終可以得到一組在時(shí)隙t中參與卸載服務(wù)的UE集O。 基于混合策略博弈的UE卸載決策算法如算法1所示。

算法1 基于混合策略博弈的用戶設(shè)備卸載決策算法

初始化： buk（t），Y，s（t），wk（t）

1： 對(duì)于第k個(gè)UE， 依據(jù)式（22）計(jì)算出Pkj，mo（t）

2： 依據(jù)式（24）計(jì)算第k個(gè)UE的移動(dòng)概率Pk，mo（t）

3： if 滿足Pk，mo（t）>μ的UE個(gè)數(shù)小于Y then

4： 得到最終參與卸載的UE集O

5： else

6： 依據(jù)式（25）計(jì)算UE的收益并按照降序排列

7： 選擇收益最大的前2Y個(gè)UE并且得到新的UE集S

8： UAV通過式（27）對(duì)UE進(jìn)行選擇

9： 得到最終參與卸載的UE集O

10： end if

11： returnO

依據(jù)文獻(xiàn)［16］， 若式（24）是一個(gè)收縮映射， 則可證明算法1中利用最佳響應(yīng)算法得到的策略會(huì)收斂到唯一的納什均衡點(diǎn)上。

引理1 若最佳響應(yīng)映射是整個(gè)策略空間的收縮， 那么博弈中存在唯一的納什均衡點(diǎn)。

定理1 若影響系數(shù)ρ滿足式（28）：

ρ≥Uuk（t）+Ulk（t）·Ⅱ{lk（t）>s}2（28）

則算法1中用采用最佳響應(yīng)算法定義的迭代都能收斂至唯一的納什均衡解。

證明 根據(jù)引理1和收縮映射理論［17］， 只需要證明式（24）是一個(gè)收縮映射， 并通過雅可比矩陣J的無窮范數(shù)小于1來推導(dǎo)ρ所需滿足的條件。 首先構(gòu)建式（24）的最佳響應(yīng)雅可比矩陣Jn×n：=（Jk， j）， 具體為

Jk， j=Pk， mo（t）Ps， mo（t）=

0， k=j－［Uuk（t）－Cmk（t）·Ⅱ{lk（t）>s}－Ulk（t）·Ⅱ{lk（t）>s}］·Cosk（t）2·ρ·（Cojk（t））2，

others （29）

式中： Cosk（t）=∏s≠k≠j， s∈K1－bs（t）∑Kk=1bk（t）·Pks， mo（t）。 也就是說， Jk， j是算法1中每個(gè)UE相對(duì)于其他UE策略的最佳響應(yīng)

函數(shù)的斜率矩陣。 其無窮范數(shù)可以表示為式（30）， 其中

J∞表示J中非對(duì)角元素絕對(duì)值之和的最大值。 令r=Uuk（t）+Ulk（t）·Ⅱ{lk（t）>s}/2， 如果滿足ρ≥r， 則J∞<1， 式（24）為收縮映射， 這也保證了算法1中Pk， mo（t）的收斂性和唯一性。

J∞=Uuk（t）－Cmk（t）·Ⅱ{lk（t）>s}－Ulk（t）·Ⅱ{lk（t）>s}·Cosk（t）2·ρ·（Cojk（t））2≤（Uuk（t）+Ulk（t）·Ⅱ{lk（t）>s}）·Cosk（t）2·ρ·（Cojk（t））2≤

（Uuk（t）+Ulk（t）·Ⅱ{lk（t）>s}）·∑l≠k， l∈K1－bl（t）∑Kk=1bk（t）·Pl， mo（t）22·ρ·（Cojk（t））2=

（Uuk（t）+Ulk（t）·Ⅱ{lk（t）>s}）·∑l≠k， l∈K1－bl（t）∑Kk=1bk（t）·Pl， mo（t）2（Cojk（t））22·ρ≤（Uuk（t）+Ulk（t）·Ⅱ{lk（t）>s}）2·ρ≤1 （30）

3.2 基于非合作博弈的卸載策略優(yōu)化

為了進(jìn)一步提高UE的效用， 本文將UE效用最大化問題描述為UE之間的非合作博弈， 并基于子模博弈理論證明了該非合作博弈純納什均衡的存在性， 最終得到UE的最優(yōu)卸載數(shù)據(jù)量。 相應(yīng)的優(yōu)化問題如下所示：

maxbuk（t）∈［0， bk（t）］， k∈OE（Uk（buk（t）， bu-k（t）））

s.t. 0≤buk（t）≤bk（t）（31）

式中： bu-k（t）表示除了第k個(gè)UE外其他UE所卸載的數(shù)據(jù)量。 可將式（31）中的分布式優(yōu)化問題表述為非合作博弈G2=［K， （Bk（t））k∈O， {E（Uk（buk（t）， bu-k（t）））}k∈O］， 其中Bk（t）=［0， bk（t）〗為UE的卸載策略空間， E（Uk（buk（t）， bu-k（t）））表示UE的效用函數(shù)。 可以用非合作博弈G2的解來確定每個(gè)UE的最優(yōu)數(shù)據(jù)卸載策略buk（t）， 以使其效用最大化， 因此本文利用納什均衡來尋求數(shù)據(jù)卸載的解決方案。

定義2 （純納什均衡點(diǎn)）給定非合作博弈G2及數(shù)據(jù)卸載向量bu（t）=（bu1（t）， bu2（t），…， buK（t））， 若在策略空間Bk（t）=［0， bk（t）］中滿足以下條件：

E（Uk（buk（t）， bu-k（t）））≥E（Uk（buk（t）， bu-k（t））） （32）

則可以說buk（t）是G2的純納什均衡點(diǎn)。

由此可得， 當(dāng)該博弈達(dá)到純納什均衡點(diǎn)buk（t）時(shí)， 博弈中的每個(gè)設(shè)備的效用達(dá)到最大值， 且其他UE改變策略并不會(huì)使得其效用增加。 為了確定非合作博弈G2的純納什均衡點(diǎn)存在且唯一， 本文采用子模博弈［18］證明。

定義3 （子模博弈）G2是子模博弈， 若所有UE都滿足以下條件：

（1） Bk（t）是歐式空間的緊子集；

（2） E（Uk（buk（t）， bu-k（t）））是光滑的且在（buk（t）， bu-k（t））是非遞增的， 即E（Uk（buk（t）， bu-k（t）））buj（t）buk（t）≤0。

定理2 G2是子模博弈且至少有一個(gè)純納什均衡點(diǎn)。

證明 策略空間Bk（t）=［0， bk（t）］是歐式空間的緊子集且效用函數(shù)E（Uk（buk（t）， bu-k（t）））在定義域中處處光滑。 下面對(duì)效用函數(shù)進(jìn)行二次偏導(dǎo)數(shù)的求解， 證明其有非遞增的趨勢。 首先定義效用函數(shù)為

E（Uk（buk（t）， bu-k（t）））=W0+buk（t）·

（2－ln（1+N））－φ·Cuk（t）（33）

已知Nbuj（t）>0， Nbuk（t）>0， ror（N）buj（t）>0， ror（N）buk（t）>0， 則求效用函數(shù)的二階偏導(dǎo)數(shù)為

2E（Uk（buk（t）， bu-k（t）））buj（t）buk（t）=buk（t）·1（1+N）2·

Nbuj（t）·Nbuk（t）－

11+N·Nbuj（t）（34）

當(dāng)N=0時(shí)， buk（t）=0， 可得

2E（Uk（buk（t）， bu-k（t）））buj（t）buk（t）=－Nbuj（t）<0（35）

當(dāng)N=1時(shí)， buk（t）≈bk（t）， 可得

2E（Uk（buk（t）， bu-k（t）））buj（t）buk（t）=bk（t）·14·Nbuj（t）·

Nbuk（t）－12·Nbuj（t）=12·Nbuj（t）·

12·bk（t）·Nbuk（t）－1

<0（36）

由于2E（Uk（buk（t）， bu-k（t）））buj（t）buk（t）是連續(xù)的， 根據(jù)上述證明容易得出2E（Uk（buk（t）， bu-k（t）））buj（t）buk（t）<0， buk（t）∈［0， bk（t）］。 因此非合作博弈G2屬于子模博弈， 且至少存在一個(gè)純納什均衡點(diǎn)bu（t）=（bu1（t）， bu2（t），…， buK（t））。

下面采用分布式方法來確定數(shù)據(jù)卸載策略， 根據(jù)最佳響應(yīng)算法， 可以依據(jù)其他設(shè)備的卸載策略， 來決定當(dāng)前設(shè)備的最佳卸載策略， 其表示如下：

buk（t）=argmaxbuk（t）∈［0， bk（t）］E（Uk（buk（t）， bu-k（t））） （37）

基于子模博弈的部分卸載策略優(yōu)化算法的具體步驟如算法2所示。

算法 基于非合作博弈的卸載策略優(yōu)化算法

初始化： iter=0， buk，k∈O（t）（iter=0）， convergence=false

1： while convergence=false do

2： iter=iter+1

3： for k=1to K do

4： 第k個(gè)UE依據(jù)式（37）確定最佳卸載策略， 并接收此 次迭代的效用函數(shù)E（Uk（buk（t）， bu-k（t）））iter

5： end for

6： if buk（t）（iter）=buk（t）（iter－1）

7： 得到第k個(gè)UE的最優(yōu)卸載數(shù)據(jù)量buk（t）

8： convergence=true

9： end if

10： end while

11： return buk（t）

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

考慮一個(gè)無人機(jī)輔助的MEC系統(tǒng)為分布在一個(gè)50 m×50 m矩形區(qū)域內(nèi)的20個(gè)UE提供計(jì)算服務(wù)， 已知該區(qū)域被劃分為4個(gè)25 m×25 m的子區(qū)域， 且UAV的通信覆蓋區(qū)域?yàn)榘霃綖?2.5 m的圓形區(qū)域。 整個(gè)系統(tǒng)運(yùn)行20個(gè)時(shí)隙， 每個(gè)時(shí)隙的長度根據(jù)UAV的最大懸停時(shí)間進(jìn)行調(diào)整。 仿真參數(shù)的數(shù)值可參照文獻(xiàn)［14， 19］， 具體如表1所示。

圖2為UE的初始位置示意圖， 其中紅色星號(hào)表示不同時(shí)隙UAV懸停時(shí)的地面投影。 為了方便后續(xù)仿真結(jié)果的評(píng)估， 設(shè)定每個(gè)子區(qū)域的UE數(shù)量基本相同， 但在各個(gè)子區(qū)域中的UE是隨機(jī)分布的。

表2為前10個(gè)時(shí)隙編號(hào)為1～5的UE的移動(dòng)距離， 表中數(shù)據(jù)可以進(jìn)一步驗(yàn)證前面的理論， 即UE會(huì)在卸載效用與移動(dòng)成本之間衡量。 當(dāng)卸載產(chǎn)生的效用足夠大時(shí)， UE會(huì)選擇移動(dòng)至當(dāng)前時(shí)隙UAV的服務(wù)覆蓋區(qū)域進(jìn)行任務(wù)的部分卸載， 而具體移動(dòng)的距離與該時(shí)隙UAV和UE之間的距離相關(guān)。

圖3展示了進(jìn)行部分卸載的5個(gè)UE的卸載數(shù)據(jù)量隨迭代次數(shù)變化的情況， 并在其中著重標(biāo)注了具有代表性的均值變化情況。 由圖3可知， 所引入的最佳響應(yīng)算法收斂速度較快， 便于實(shí)際應(yīng)用。 此外， 隨著迭代周期的增加， 每個(gè)UE的卸載數(shù)據(jù)量趨于穩(wěn)定， 證明了算法的收斂性。

圖4描述了UE效用值及均值隨迭代次數(shù)變化的情況。 結(jié)果表明， UE最初傾向于將大量數(shù)據(jù)卸載到MEC

服務(wù)器上（如圖3所示）， 因此相應(yīng)的效用值也會(huì)增加（如圖4所示）， 然而這也導(dǎo)致了UE卸載至MEC服務(wù)器的能耗和時(shí)延成本的增加。 因而， 隨著迭代次數(shù)的增加， 設(shè)備減少了卸載到MEC服務(wù)器的數(shù)據(jù)量， 最終收斂到純納什均衡點(diǎn)。

圖5展示了UAV可以提供服務(wù)的UE數(shù)量Y不同時(shí)UE的平均收益隨時(shí)隙的變化情況。 當(dāng)Y=3時(shí)， 由于UAV可服務(wù)的UE數(shù)量較少， 因此UE可卸載的機(jī)會(huì)較小， 大多數(shù)情況下只能本地執(zhí)行， 無法獲得MEC服務(wù)器帶來的收益。 當(dāng)Y=4和Y=5時(shí)， 隨UAV可提供服務(wù)的UE數(shù)量增加， UE獲得來自MEC服務(wù)器的收益提高， 因此UE的平均效用也在增加。 但當(dāng)Y=5時(shí)， UAV雖然可以為更多UE提供服務(wù)， 但由于分配給每個(gè)UE的資源較少， 其卸載能耗和時(shí)延都有所增加， 這也影響了部分UE卸載至UAV的意愿， 因此相較于Y=3至Y=4， Y=4至Y=5的效用提升更少。

圖6展示了UE在移動(dòng)懲罰系數(shù)δ不同的情況下每個(gè)時(shí)隙的平均效用。 從圖中可看出， 隨著移動(dòng)懲罰系數(shù)δ的減小， UE在每個(gè)時(shí)隙的平均效用在增加。 這是由于UE移動(dòng)成本的減少， 增強(qiáng)了UE的移動(dòng)意愿， 促進(jìn)了UE之間的合作。 而在合作博弈中合作越多， 收益越高， 因此δ=5×105時(shí)平均效用值最大。 此外， 當(dāng)δ=5×107時(shí)， 每個(gè)時(shí)隙得到的UE平均效用之間相差較大。 這是因?yàn)橐苿?dòng)成本過高時(shí)大多數(shù)UE移動(dòng)概率較低， 這會(huì)導(dǎo)致無人機(jī)服務(wù)的UE大多是原本就位于無人機(jī)所在子區(qū)域的UE。 而由于UE在每個(gè)時(shí)隙處理任務(wù)的數(shù)據(jù)量是隨機(jī)的， 不同UE在不同時(shí)隙進(jìn)行卸載得到的具體效用值也有所不同， 因此UAV位于不同子區(qū)域時(shí)得到的UE總效用有一定差異， 各時(shí)隙之間的平均效用的差距也會(huì)較大。 而移動(dòng)成本較低時(shí)， UE有較大的意愿選擇移動(dòng)， 區(qū)域外卸載所得效用較大以及任務(wù)數(shù)據(jù)量較大的UE也有機(jī)會(huì)卸載， 因此UAV位于不同子區(qū)域時(shí)得到的UE平均效用的差異減小， 平均效用折線圖也會(huì)較為平穩(wěn)。 此外δ值的設(shè)定可以結(jié)合具體場景， 若UE移動(dòng)意愿不強(qiáng)或基本無法移動(dòng)， 可以增大δ值以使算法更適用于應(yīng)用場景。

圖7展示了影響系數(shù)ρ不同的情況下的平均效用。 為方便表示， 設(shè)定ρ=r·rmul， 其中rmul>1， 代表ρ大于其最小值r。 從圖中可看出， 當(dāng)rmul增加時(shí)， UE的平均效用值會(huì)變小。 可見當(dāng)ρ增大時(shí)， UE考慮到其他UE的影響過多， 導(dǎo)致UE不敢去冒險(xiǎn)選擇移動(dòng)， 以免承擔(dān)更大的成本， 同時(shí)也導(dǎo)致了各時(shí)隙之間的平均效用差距較大及系統(tǒng)不穩(wěn)定的情況。

圖8展示了不同任務(wù)執(zhí)行方案下每時(shí)隙UE的平均效用， 其中， non movement表示區(qū)域內(nèi)的所有UE的移動(dòng)概率都為0， 僅等待UAV移動(dòng)到自己的子區(qū)域時(shí)才考慮卸載任務(wù)至MEC服務(wù)器執(zhí)行； local only表示每個(gè)UE只在本地執(zhí)行自己的任務(wù)， 不考慮卸載； all offloading 表示當(dāng)UE進(jìn)行卸載時(shí)， 將全部任務(wù)數(shù)據(jù)量都卸載至MEC服務(wù)器； MBO algorithm［19］中UE利用混合策略博弈來計(jì)算UE的二進(jìn)制卸載概率， UE移動(dòng)的條件是UE移動(dòng)后的卸載效用大于0。 從圖中可以看出， 所提方案能獲得最高的UE平均效用。 local only方案下UE只能本地執(zhí)行任務(wù)， 由于UE的計(jì)算資源非常有限， 因此獲得的效用最小。 采用non movement方案則會(huì)使得不在服務(wù)覆蓋區(qū)域的UE無法卸載， 從而導(dǎo)致所有UE獲得MEC服務(wù)器的收益變少， 因此平均效用較低。 all offloading方案雖然為全部卸載， 獲得了最多的卸載收益， 但這也同時(shí)增加了卸載的能耗和時(shí)延， 從而降低了UE的效用。 MBO algorithm雖然使用混合策略博弈來進(jìn)行卸載決策， 提高了UE的卸載效用， 但在UE移動(dòng)決策上僅考慮了UE自身的效用， 并未考慮其他用戶的影響。 此外， 該方案與all offloading一樣采用二進(jìn)制卸載， 也會(huì)出現(xiàn)卸載時(shí)延和能耗較大的問題， 因此相較所提方案， MBO algorithm的平均效用值更小。

5 結(jié) 束 語

本文研究了無人機(jī)輔助移動(dòng)邊緣計(jì)算系統(tǒng)中的任務(wù)卸載問題， 采用混合策略博弈模型聯(lián)合優(yōu)化UE的卸載決策和卸載數(shù)據(jù)量， 以最大化UE效用。 考慮到所求優(yōu)化問題很難直接求解， 可分兩個(gè)步驟對(duì)問題進(jìn)行處理。 首先構(gòu)建混合策略博弈模型， 得到UE的移動(dòng)概率， 并利用匹配博弈進(jìn)一步篩選UAV可服務(wù)的UE。 而后為了得到最優(yōu)的UE數(shù)據(jù)卸載量， 構(gòu)建了UE之間的非合作博弈， 并基于子模博弈理論證明了純納什均衡的存在性。 仿真結(jié)果表明， 所提出的UE任務(wù)卸載方案相比non movement， local only， all offloading， MBO algorithm四種UE任務(wù)執(zhí)行方案可獲得最高的UE平均效用。 所提方法僅可用在單無人機(jī)為大區(qū)域UE提供服務(wù)的情況下， 考慮到多架無人機(jī)的合作服務(wù)可以進(jìn)一步提高系統(tǒng)性能， 可進(jìn)一步針對(duì)多無人機(jī)協(xié)同輔助的移動(dòng)邊緣計(jì)算系統(tǒng)場景進(jìn)行深入研究。

參考文獻(xiàn)：

［1］ Liu C H， Chen Z Y， Tang J， et al. Energy-Efficient UAV Control for Effective and Fair Communication Coverage： A Deep Reinforcement Learning Approach［J］. IEEE Journal on Selected Areas in Communications， 2018， 36（9）： 2059-2070.

［2］ Ning Z L， Yang Y X， Wang X J， et al. Dynamic Computation Offloading and Server Deployment for UAV-Enabled Multi-Access Edge Computing［J］. IEEE Transactions on Mobile Computing， 2023， 22（5）： 2628-2644.

［3］ Wang J Y， Ma Y， Lu R R， et al. Hovering UAV-Based FSO Communications： Channel Modelling， Performance Analysis， and Parameter Optimization［J］. IEEE Journal on Selected Areas in Communications， 2021， 39（10）： 2946-2959.

［4］ Diao X B， Zheng J C， Cai Y M， et al. Fair Data Allocation and Trajectory Optimization for UAV-Assisted Mobile Edge Computing［J］. IEEE Communications Letters， 2019， 23（12）： 2357-2361.

［5］ Wu H C， Wei Z Q， Hou Y Z， et al. Cell-Edge User Offloading via Flying UAV in Non-Uniform Heterogeneous Cellular Networks［J］. IEEE Transactions on Wireless Communications， 2020， 19（4）： 2411-2426.

［6］ Wu G X， Liu Q， Xu J F， et al. Energy Efficient Task Caching and Offloading in UAV-Enabled Crowd Management［J］. IEEE Sensors Journal， 2022， 22（18）： 17565-17572.

［7］ Han Z H， Zhou T， Xu T H， et al. Joint User Association and Deployment Optimization for Delay-Minimized UAV-Aided MEC Networks［J］. IEEE Wireless Communications Letters， 2023， 12（10）： 1791-1795.

［8］ Xue J B， Zhang T J， Shao F， et al. Joint Optimization of Trajectory and Resource Allocation in Cellular-Connected Multi-UAV MEC Networks［J］. Physical Communication， 2023， 61： 102209.

［9］ Wang M L， Zhang L， Gao P， et al. Stackelberg-Game-Based intelligent Offloading incentive Mechanism for a Multi-UAV-Assisted Mobile-Edge Computing System［J］. IEEE Internet of Things Journal， 2023， 10（17）： 15679-15689.

［10］ Lin W W， Huang T S， Li X， et al. Energy-Efficient Computation Offloading for UAV-Assisted MEC： A Two-Stage Optimization Scheme［J］. ACM Transactions on internet Technology， 2021， 22（1）： 1-23.

［11］ Brahimi S Y， Mouffak F， Bousbaa F Z， et al. Cloud Service Selection in ioFT-Enabled Multi-Access Edge Computing： A Game Theoretic Approach［J］. Annals of Telecommunications， 2023， 78（11）： 717-728.

［12］ Lin X Q， Yajnanarayana V， Muruganathan S D， et al. The Sky is not the Limit： LTE for Unmanned Aerial Vehicles［J］. IEEE Communications Magazine， 2018， 56（4）： 204-210.

［13］ 戰(zhàn)俊偉， 莊毅. 基于能耗與延遲優(yōu)化的移動(dòng)邊緣計(jì)算任務(wù)卸載模型及算法［J］. 計(jì)算機(jī)與現(xiàn)代化， 2022（8）： 86-93.

Zhan Junwei， Zhuang Yi. Mobile Edge Computing Task Offloading Model and Algorithm Based on Energy Consumption and Delay Optimization［J］. Computer and Modernization， 2022（8）： 86-93.（in Chinese）

［14］ Mitsis G， Tsiropoulou E E， Papavassiliou S. Price and Risk Awareness for Data Offloading Decision-Making in Edge Computing Systems［J］. IEEE Systems Journal， 2022， 16（4）： 6546-6557.

［15］ Tadelis S. Game Theory： An Introduction［M］. Princeton： Princeton University Press， 2013.

［16］ Lang P， Wang J， Mei F， et al. A Vehicle’s Weight-Based Prioritized Reciprocity MAC［J］. Transactions on Emerging Telecommunications Technologies， 2019， 30（12）： e3654.

［17］ Wang Y P， Lang P， Tian D X， et al. A Game-Based Computation Offloading Method in Vehicular Multiaccess Edge Computing Networks［J］. IEEE Internet of Things Journal， 2020， 7（6）： 4987-4996.

［18］ Tsiropoulou E E， Vamvakas P， Papavassiliou S. Joint Customized Price and Power Control for Energy-Efficient Multi-Service Wireless Networks via S-Modular Theory［J］. IEEE Transactions on Green Communications and Networking， 2017， 1（1）： 17-28.

［19］ Zeng Y P， Chen S S， Cui Y P， et al. Joint Resource Allocation and Trajectory Optimization in UAV-Enabled Wirelessly Powered MEC for Large Area［J］. IEEE Internet of Things Journal， 2023， 10（17）： 15705-15722.

UAV-Assisted Mobile Edge Computing Task Offloading

Based on Mixed-Strategy Games

Zhu Yun1， Liu Shuwen1， Chen Qiang2， Liao Jian1， Guo Zhengyu3， Lu Chunyu4， Luo Delin5， 6*

（1. School of Physics and Electronic Information， Gannan Normal University， Ganzhou 341000， China;

2. Unit 92808 of PLA， Haikou 570311， China; 3. China Airborne Missile Academy， Luoyang 471009， China;

4. Unit 91504 of PLA， Taizhou 318050， China; 5. School of Aerospace Engineering， Xiamen University， Xiamen 361102， China;

6. National Key Laboratory of Air-based Information Perception and Fusion， Luoyang 471009， China）

Abstract： In a single UAV-assisted mobile edge computing system， in order to enable the UAV to serve all user devices in a large area， the large area can be divided into a plurality of sub-areas and the UAV can be set to fly between the sub-areas with a fixed route to provide computing services for the user devices. Considering the scarcity of computational resources for user devices and the fact thkwk0qo7TeAV+paIBvBZddw==at users outside the coverage area of the UAV may choose to move to the coverage area for task offloading in order to maximize their own utility， the partial offloading problem of user devices can be transformed into the problem of maximizing the utility of each user device. The mixed-strategy game and the submodular game are used to determine the movement probability of user devices and the amount of offloaded data， so as to derive the optimal offloading strategy， and the existence of mixed-strategy Nash equilibrium and pure-strategy Nash equilibrium is proved， respectively. Simulation results show that the proposed scheme can effectively improve the utility of user device compared with classical schemes such as MBO （Binary Offloading Based on Mixed Strategy Game）， and its convergence and stability are verified.

Key words： UAV; mobile edge computing; computational offloading; mixed-strategy game; submodular game