無(wú)人機(jī)輔助邊緣計(jì)算網(wǎng)絡(luò)的任務(wù)卸載與資源分配聯(lián)合優(yōu)化

周曉天; 楊瀟輝; 張海霞; 鄧伊琴

doi:10.11999/JEIT240411

無(wú)人機(jī)輔助邊緣計(jì)算網(wǎng)絡(luò)的任務(wù)卸載與資源分配聯(lián)合優(yōu)化

doi: 10.11999/JEIT240411 cstr: 32379.14.JEIT240411

1.
山東大學(xué)控制科學(xué)與工程學(xué)院濟(jì)南 250061
2.
山東省智能通信與感算融合重點(diǎn)實(shí)驗(yàn)室濟(jì)南 250061

基金項(xiàng)目: 國(guó)家自然科學(xué)基金聯(lián)合基金項(xiàng)目(U22A2003)，山東省自然科學(xué)基金重大基礎(chǔ)研究項(xiàng)目(ZR2022ZD02)

詳細(xì)信息

作者簡(jiǎn)介:
周曉天：男，教授，研究方向?yàn)闊o(wú)線通信與網(wǎng)絡(luò)、邊緣計(jì)算與智能通信等

楊瀟輝：男，碩士生，研究方向?yàn)闊o(wú)人機(jī)、邊緣計(jì)算等

張海霞：女，教授，研究方向?yàn)闊o(wú)線通信與網(wǎng)絡(luò)、無(wú)線資源管理、智能通信技術(shù)等

鄧伊琴：女，博士后，研究方向?yàn)檫吘売?jì)算、車(chē)聯(lián)網(wǎng)、無(wú)線資源優(yōu)化等

通訊作者:
張海霞　haixia.zhang@sdu.edu.cn

中圖分類(lèi)號(hào): TN929.5; TP18
計(jì)量
- 文章訪問(wèn)數(shù): 748
- HTML全文瀏覽量: 238
- PDF下載量: 137
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2024-05-25
- 修回日期: 2024-11-07
- 網(wǎng)絡(luò)出版日期: 2024-11-13
- 刊出日期: 2024-12-01

Joint Optimization of Task Offloading and Resource Allocation for Unmanned Aerial Vehicle-assisted Edge Computing Network

1.
School of Control Science and Engineering, Shandong University, Jinan 250061, China
2.
Shandong Key Laboratory of Intelligent Communications and Sensing-Computation Integration, Shandong University, Jinan 250061, China

Funds: The Joint Funds of the National Natural Science Foundation of China (U22A2003), The Major Fundamental Research Project of Shandong Provincial Natural Science Foundation (ZR2022ZD02)

摘要

摘要: 利用無(wú)人機(jī)(UAV)作為空中中繼節(jié)點(diǎn)，構(gòu)建空地一體化的邊緣計(jì)算網(wǎng)絡(luò)，可以有效克服地面環(huán)境局限，拓展網(wǎng)絡(luò)覆蓋范圍，為用戶(hù)提供便利計(jì)算服務(wù)。該文面向無(wú)人機(jī)中繼輔助的多用戶(hù)、多服務(wù)器邊緣計(jì)算網(wǎng)絡(luò)場(chǎng)景，以最大化任務(wù)完成量為目標(biāo)，研究了無(wú)人機(jī)部署位置、用戶(hù)-服務(wù)器關(guān)聯(lián)策略、無(wú)人機(jī)帶寬分配的聯(lián)合優(yōu)化問(wèn)題。由于該問(wèn)題包含連續(xù)與離散變量，故該文綜合運(yùn)用差分進(jìn)化、粒子群優(yōu)化等工具，提出了一種基于塊坐標(biāo)下降(BCD)的次優(yōu)算法進(jìn)行求解。所提算法將原問(wèn)題解耦為3個(gè)子問(wèn)題獨(dú)立求解，并通過(guò)迭代逼近原始問(wèn)題最優(yōu)解。仿真實(shí)驗(yàn)表明，所提算法可在滿(mǎn)足用戶(hù)任務(wù)時(shí)延需求的前提下，最大化系統(tǒng)總?cè)蝿?wù)完成量，優(yōu)于其他對(duì)比算法。
- 無(wú)人機(jī)通信 /
- 多接入邊緣計(jì)算 /
- 任務(wù)卸載 /
- 資源分配
Abstract: It can effectively overcome the limitations of the ground environment, expand the network coverage and provide users with convenient computing services, through constructing the air-ground integrated edge computing network with Unmanned Aerial Vehicle (UAV) as the relay. In this paper, with the objective of maximizing the task completion amount, the joint optimization problem of UAV deployment, user-server association and bandwidth allocation is investigated in the context of the UAV assisted multi-user and multi-server edge computing network. The formulated joint optimization problem contains both continuous and discrete variables, which makes itself hard to solve. To this end, a Block Coordinated Descent (BCD) based iterative algorithm is proposed in this paper, involving the optimization tools such as differential evolution and particle swarm optimization. The original problem is decomposed into three sub-problems with the proposed algorithm, which can be solved independently. The optimal solution of the original problem can be approached through the iteration among these three subproblems. Simulation results show that the proposed algorithm can greatly increase the amount of completed tasks, which outperforms other benchmark algorithms.
- Unmanned Aerial Vehicle (UAV) communication /
- Multi-access edge computing /
- Task offloading /
- Resource allocation

HTML全文

圖 1 系統(tǒng)模型

下載: 全尺寸圖片幻燈片

圖 2 算法整體流程圖

下載: 全尺寸圖片幻燈片

圖 3 算法收斂性能分析與UAV部署位置示意圖

下載: 全尺寸圖片幻燈片

圖 4 不同方案及帶寬資源對(duì)任務(wù)完成量的影響

下載: 全尺寸圖片幻燈片

1 聯(lián)合UAV位置、帶寬分配、用戶(hù)-邊緣服務(wù)器關(guān)聯(lián)算法

(1) 初始化$ {{\boldsymbol{\varOmega}} ^0} $, $ {{\boldsymbol{B}}^0} $, $ {{\boldsymbol{A}}^0} $，置$ k $=0;
(2) While 目標(biāo)函數(shù)的增長(zhǎng)值低于閾值$ \varepsilon $：
(3) 　　給定{$ {{\boldsymbol{B}}^k},{{\boldsymbol{A}}^k} $}，輸入算法2，輸出結(jié)果$ {{\boldsymbol{\varOmega}} ^{k + 1}} $;
(4) 　　給定{$ {{\boldsymbol{\varOmega}} ^{k + 1}},{{\boldsymbol{A}}^k} $}，輸入算法3，輸出結(jié)果$ {{\boldsymbol{B}}^{k + 1}} $;
(5) 　　給定{$ {{\boldsymbol{\varOmega}} ^{k + 1}},{{\boldsymbol{B}}^{k + 1}} $}，輸入算法4，輸出結(jié)果$ {{\boldsymbol{A}}^{k + 1}} $;
(6) 　　更新$ k = k + 1 $;
(7) End While
(8) 得到最終$ {\boldsymbol{\varOmega}} $, $ {\boldsymbol{A}} $, $ {\boldsymbol{B}} $

下載: 導(dǎo)出CSV

2 基于PSO的UAV 3維位置優(yōu)化算法

輸入：用戶(hù)位置$ ({\boldsymbol{w}}_m^{\text{T}},0) $、邊緣服務(wù)器位置$ ({\boldsymbol{w}}_s^{\text{T}},0) $、任務(wù)參數(shù) 　$ ({l_i},{c_i},{\tau _i}) $；其他基本參數(shù)$ {A_1},{A_2},{\beta _0},N,\gamma ,{c_1},{c_2},{r_1},{r_2},{k_{{\text{max}}}} $;
輸出：無(wú)人機(jī)3維位置$ {\boldsymbol{\varOmega}} $
(1) 初始化迭代次數(shù)$ k $=1;
(2) For 每個(gè)粒子$ i $:
(3) 　For 每個(gè)維度$ d $:
(4) 　　在允許范圍內(nèi)隨機(jī)初始化粒子位置$ {{\boldsymbol{X}}_{id}} $;
(5) 　　在允許范圍內(nèi)隨機(jī)初始化粒子速度$ {{\boldsymbol{V}}_{id}} $;
(6) 　End For
(7) End For
(9) While $ k \le {k_{{\text{max}}}} $:
(10) 　 For 每個(gè)粒子$ i $:
(11) 　　計(jì)算每個(gè)粒子能夠完成的系統(tǒng)任務(wù)量;
(12) 　　 If $ f({\boldsymbol{X}}_{id}^k) < f({\bf{pbest}}_{id}^{k - 1}) $
(13) 　　　選擇當(dāng)前粒子位置作為該粒子的最優(yōu)位置$ {\bf{pbest}}_{id}^k $;
(14) 　　 End If
(15) End For
(16) For 每個(gè)粒子$ i $:
(17) 　 For 每個(gè)維度$ d $:
(18) 　　根據(jù)式(6)計(jì)算粒子新速度;
(19) 　　根據(jù)$ {\boldsymbol{X}}_{id}^{k + 1} = {\boldsymbol{X}}_{id}^k + {\mkern 1mu} {\mkern 1mu} {\boldsymbol{V}}_{id}^{k + 1} $更新粒子新位置;
(20) 　 End For
(21) End For
(22) $ k = k + 1 $;
(23) End While

下載: 導(dǎo)出CSV

3 基于DE的帶寬分配優(yōu)化算法

輸入：用戶(hù)位置$ ({\boldsymbol{w}}_m^{\text{T}},0) $、邊緣服務(wù)器位置$ ({\boldsymbol{w}}_s^{\text{T}},0) $、任務(wù)參數(shù) 　$ ({l_i},{c_i},{\tau _i}) $；其他基本參數(shù)$ {A_1},{A_2},{\beta _0},N,{\text{CR}},{k_{{\text{max}}}} $;
輸出：帶寬分配比例$ {\boldsymbol{B}} $
(1) 初始化迭代次數(shù)$ k $=1;
(2) For 每個(gè)個(gè)體$ i $：
(3) 　For 每個(gè)維度$ d $：
(4) 　　在允許范圍內(nèi)隨機(jī)初始化個(gè)體位置$ {{\boldsymbol{x}}_{n,1}} $;
(5) 　　計(jì)算每個(gè)個(gè)體能完成的系統(tǒng)任務(wù)量;
(6) 　End For
(7) End For
(8) While $ k \le {k_{{\text{max}}}} $：
(9) 　For 每個(gè)個(gè)體$ i $：
(10) 　從當(dāng)前$ {{\boldsymbol{x}}_{n,k}} $中選擇3個(gè)不同個(gè)體 $ {{\boldsymbol{x}}_{r1,k}} $, $ {{\boldsymbol{x}}_{r2,k}} $, $ {{\boldsymbol{x}}_{r3,k}} $;
(11) 　計(jì)算得到變異個(gè)體;
(12) End For
(13) For 每個(gè)個(gè)體$ i $：
(14) 　生成當(dāng)前個(gè)體的交叉概率$ {\text{CR}} $;
(15) 　根據(jù)式(8)計(jì)算得到試驗(yàn)個(gè)體;
(16) End For
(17) For 每個(gè)個(gè)體$ i $：
(18) 　根據(jù)式(9)擇優(yōu)選出最優(yōu)個(gè)體;
(19) End For
(20) $ k = k + 1 $;
(21) End While

下載: 導(dǎo)出CSV

4 基于交換的用戶(hù)-邊緣服務(wù)器關(guān)聯(lián)矩陣優(yōu)化算法

輸入：用戶(hù)位置$ ({\boldsymbol{w}}_m^{\text{T}},0) $、邊緣服務(wù)器位置$ ({\boldsymbol{w}}_s^{\text{T}},0) $、任務(wù)參數(shù) 　$ ({l_i},{c_i},{\tau _i}) $；其他基本參數(shù)$ \mathcal{H},\mathcal{F},{A_1},{A_2},{\beta _0} $；
輸出：用戶(hù)-邊緣服務(wù)器關(guān)聯(lián)矩陣$ {\boldsymbol{A}} $
(1) 初始化迭代次數(shù)$ k $=1；
(2) 根據(jù)式(10)計(jì)算得到當(dāng)前系統(tǒng)完成任務(wù)量$ \varPhi $；
(3) 根據(jù)用戶(hù)集合計(jì)算得到用戶(hù)組合個(gè)數(shù)$ {\rm{C}}_M^2 $；
(4) While $ k \le {\rm{C}}_M^2 $：
(5) 　計(jì)算此連接方式下系統(tǒng)完成任務(wù)量$ {\varPhi ^ * } $；
(6) 　If $ {\varPhi ^ * } > \varPhi $：
(7) 　　交換此用戶(hù)組合的連接方式，更新$ {{{a}}_{{{m}},{{s}}}} $；
(8) 　End If
(9) 　$ k = k + 1 $；
(10) End While

下載: 導(dǎo)出CSV

表 1 仿真參數(shù)設(shè)置

參數(shù)名	參數(shù)值	參數(shù)名	參數(shù)值
邊緣服務(wù)器計(jì)算能力f_s	[1, 9] GHz	無(wú)人機(jī)傳輸功率$ {P_{\mathrm{u}}} $	2 W
邊緣服務(wù)器最大用戶(hù)服務(wù)數(shù)$ {\eta _s} $	3	噪聲功率譜密度$ {N_0} $	–169 dBm/Hz
任務(wù)的數(shù)據(jù)量$ {l_i} $	[100, 900] kB	路徑損耗系數(shù)$ \alpha $	2.5
用戶(hù)-UAV上行鏈路帶寬W	6 MHz	平均信道功率增益$ {\beta _0} $	–60 dB
UAV-服務(wù)器下行鏈路帶寬W	6 MHz	Rice因子最小值$ {K_{{\text{min}}}} $	0 dB
用戶(hù)設(shè)備傳輸功率$ {P_m} $	15 dBm	Rice因子最大值$ {K_{{\text{max}}}} $	30 dB

下載: 導(dǎo)出CSV

表 2 PSO, DE子算法參數(shù)設(shè)置

算法	參數(shù)名	參數(shù)值	算法	參數(shù)名	參數(shù)值
PSO	種群規(guī)模大小	40	DE	種群規(guī)模大小	60
	粒子維度	3		粒子維度	14
	最大迭代次數(shù)	300		最大迭代次數(shù)	300
	個(gè)體學(xué)習(xí)因子	2		縮放因子	0.5
	群體學(xué)習(xí)因子	2		交叉因子	0.4

下載: 導(dǎo)出CSV

表 3 仿真對(duì)比算法

算法類(lèi)型	算法序號(hào)	算法簡(jiǎn)介
隨機(jī)分配	對(duì)比算法1	隨機(jī)給定UAV位置、用戶(hù)-服務(wù)器關(guān)聯(lián)矩陣、帶寬分配比例。
隨機(jī)分配	對(duì)比算法2	隨機(jī)給定UAV位置、用戶(hù)-服務(wù)器關(guān)聯(lián)矩陣，平均分配帶寬比例。
1維資源獨(dú)立優(yōu)化	對(duì)比算法3	單獨(dú)優(yōu)化用戶(hù)-服務(wù)器關(guān)聯(lián)矩陣；隨機(jī)給定UAV位置、帶寬分配比例。
	對(duì)比算法4	單獨(dú)優(yōu)化UAV位置；隨機(jī)給定帶寬分配比例、用戶(hù)-服務(wù)器關(guān)聯(lián)矩陣。
	對(duì)比算法5	單獨(dú)優(yōu)化帶寬分配比例；隨機(jī)給定UAV位置、用戶(hù)-服務(wù)器關(guān)聯(lián)矩陣。
2維資源聯(lián)合優(yōu)化	對(duì)比算法6	聯(lián)合優(yōu)化用戶(hù)-服務(wù)器關(guān)聯(lián)矩陣、UAV位置；隨機(jī)給定帶寬分配比例。
	對(duì)比算法7	聯(lián)合優(yōu)化UAV位置、帶寬分配比例，隨機(jī)給定用戶(hù)-服務(wù)器關(guān)聯(lián)矩陣。
	對(duì)比算法8	聯(lián)合優(yōu)化用戶(hù)-服務(wù)器關(guān)聯(lián)矩陣、帶寬分配比例，隨機(jī)給定UAV位置。

下載: 導(dǎo)出CSV

參考文獻(xiàn)(17)

[1]	DJIGAL H, XU Jia, LIU Linfeng, et al. Machine and deep learning for resource allocation in multi-access edge computing: A survey[J]. IEEE Communications Surveys & Tutorials, 2022, 24(4): 2449–2494. doi: 10.1109/COMST.2022.3199544.
[2]	周曉天, 孫上, 張海霞, 等. 多接入邊緣計(jì)算賦能的AI質(zhì)檢系統(tǒng)任務(wù)實(shí)時(shí)調(diào)度策略[J]. 電子與信息學(xué)報(bào), 2024, 46(2): 662–670. doi: 10.11999/JEIT230129. ZHOU Xiaotian, SUN Shang, ZHANG Haixia, et al. Real-time task scheduling for multi-access edge computing-enabled AI quality inspection systems[J]. Journal of Electronics & Information Technology, 2024, 46(2): 662–670. doi: 10.11999/JEIT230129.
[3]	陳新穎, 盛敏, 李博, 等. 面向6G的無(wú)人機(jī)通信綜述[J]. 電子與信息學(xué)報(bào), 2022, 44(3): 781–789. doi: 10.11999/JEIT210789. CHEN Xinying, SHENG Min, LI Bo, et al. Survey on unmanned aerial vehicle communications for 6G[J]. Journal of Electronics & Information Technology, 2022, 44(3): 781–789. doi: 10.11999/JEIT210789.
[4]	YAN Xuezhen, FANG Xuming, DENG Cailian, et al. Joint optimization of resource allocation and trajectory control for mobile group users in fixed-wing UAV-enabled wireless network[J]. IEEE Transactions on Wireless Communications, 2024, 23(2): 1608–1621. doi: 10.1109/TWC.2023.3290748.
[5]	LI Mushu, CHENG Nan, GAO Jie, et al. Energy-efficient UAV-assisted mobile edge computing: Resource allocation and trajectory optimization[J]. IEEE Transactions on Vehicular Technology, 2020, 69(3): 3424–3438. doi: 10.1109/TVT.2020.2968343.
[6]	LUO Weiran, SHEN Yanyan, YANG Bo, et al. Joint 3-D trajectory and resource optimization in multi-UAV-enabled IoT networks with wireless power transfer[J]. IEEE Internet of Things Journal, 2021, 8(10): 7833–7848. doi: 10.1109/JIOT.2020.3041303.
[7]	NASIR A A. Latency optimization of UAV-enabled MEC system for virtual reality applications under Rician fading channels[J]. IEEE Wireless Communications Letters, 2021, 10(8): 1633–1637. doi: 10.1109/LWC.2021.3075762.
[8]	LIU Boyang, WAN Yiyao, ZHOU Fuhui, et al. Resource allocation and trajectory design for MISO UAV-assisted MEC networks[J]. IEEE Transactions on Vehicular Technology, 2022, 71(5): 4933–4948. doi: 10.1109/TVT.2022.3140833.
[9]	CHENG Kaijun, FANG Xuming, WANG Xianbin, et al. Energy efficient edge computing and data compression collaboration scheme for UAV-assisted network[J]. IEEE Transactions on Vehicular Technology, 2023, 72(12): 16395–16408. doi: 10.1109/TVT.2023.3289962.
[10]	WANG Yong, RU Zhiyang, WANG Kezhi, et al. Joint deployment and task scheduling optimization for large-scale mobile users in multi-UAV-enabled mobile edge computing[J]. IEEE Transactions on Cybernetics, 2020, 50(9): 3984–3997. doi: 10.1109/TCYB.2019.2935466.
[11]	MEI Haibo, YANG Kun, LIU Qiang, et al. Joint trajectory-resource optimization in UAV-enabled edge-cloud system with virtualized mobile clone[J]. IEEE Internet of Things Journal, 2020, 7(7): 5906–5921. doi: 10.1109/JIOT.2019.2952677.
[12]	LIU Tianyu, ZHANG Guangchi, CUI Miao, et al. Task completion time minimization for UAV-enabled data collection in Rician fading channels[J]. IEEE Internet of Things Journal, 2023, 10(2): 1134–1148. doi: 10.1109/JIOT.2022.3204658.
[13]	YOU Changsheng and ZHANG Rui. 3D trajectory optimization in Rician fading for UAV-enabled data harvesting[J]. IEEE Transactions on Wireless Communications, 2019, 18(6): 3192–3207. doi: 10.1109/TWC.2019.2911939.
[14]	MONDAL A, MISHRA D, PRASAD G, et al. Joint optimization framework for minimization of device energy consumption in transmission rate constrained UAV-assisted IoT network[J]. IEEE Internet of Things Journal, 2022, 9(12): 9591–9607. doi: 10.1109/JIOT.2021.3128883.
[15]	LI Jianyu, DU Kejing, ZHAN Zhiui, et al. Distributed differential evolution with adaptive resource allocation[J]. IEEE Transactions on Cybernetics, 2023, 53(5): 2791–2804. doi: 10.1109/TCYB.2022.3153964.
[16]	MILNER S, DAVIS C, ZHANG Haijun, et al. Nature-inspired self-organization, control, and optimization in heterogeneous wireless networks[J]. IEEE Transactions on Mobile Computing, 2012, 11(7): 1207–1222. doi: 10.1109/TMC.2011.141.
[17]	LIU Jialei, ZHOU Ao, LIU Chunhong, et al. Reliability-enhanced task offloading in mobile edge computing environments[J]. IEEE Internet of Things Journal, 2022, 9(13): 10382–10396. doi: 10.1109/JIOT.2021.3115807.