一种面向移动边缘计算的无人机基站部署方法

doi:10.11896/jsjkx.220200089

摘要/Abstract

摘要： 在移动边缘计算(Mobile Edge Computing,MEC)中,本地设备可以将任务卸载到边缘服务器执行,以此来提高服务质量(Quality of Service,QoS)。但在受灾地区或遇到紧急情况时,地面固定的基站可能会出现大面积瘫痪,为了应急通信,无人机(Unmanned Aerial Vehicle,UAV)支持的移动边缘计算系统应运而生。作为新兴的应急通信手段,无人机可以携带边缘服务器,地面用户设备可以将其计算任务卸载给无人机执行,但在多用户网络中部署多个无人机基站是具有挑战性的。为此,重点研究无人机基站的战略部署问题,将该问题建模为多目标优化问题,旨在平衡无人机基站之间的工作负载,最小化地面用户和无人机基站之间的访问延迟。与单目标优化问题相比,多目标之间相互作用并且解不唯一,给模型求解带来了一定困难。为此,提出基于K-中心点(K-medoids)的帕累托边界搜索算法求解该问题,之后进一步提出利用主成分分析算法(Principal Component Analysis,PCA)从帕累托边界中寻找最合适的解作为最终的无人机基站部署策略。实验使用真实的数据集,并与其他几种基线方法进行性能比较,验证了所提解决方案的有效性。

关键词: 无人机基站部署, 多目标优化, K-中心点, 帕累托边界, 主成分分析

Abstract: In mobile edge computing (MEC),local devices can offload tasks to edge servers for execution to improve the quality of service (QoS).However,in disaster-stricken areas or in emergencies,ground-fixed base stations may be paralyzed on a large scale.For emergency communications,mobile edge computing systems supported by unmanned aerial vehicles (UAV) have emerged.As an emerging means of emergency communication,drones can carry edge servers,and ground user equipment can offload their computing tasks to the drones for execution.However,it is challenging to deploy multiple UAV base stations in a multi-user network.To this end,this paper focuses on the strategic deployment of UAV base stations,modeling the problem as a multi-objective optimization problem,which aims to balance the workload among UAV base stations and minimize the access delay between ground users and UAV base stations.Compared with single-objective optimization problems,multi-objectives interact with each other and the solutions are not unique,which brings certain difficulties to model solving.For this reason,this paper proposes a Pareto boundary search algorithm based on K-medoids to solve the problem,and then further proposes to use the principal component analysis algorithm (PCA) to find the most suitable solution from the Pareto boundary as the final deployment strategy for UAV base stations.The experiment in this paper uses real data sets and compares the performance with several other baseline methods to verify the effectiveness of the proposed solution.

Key words: UAV base station deployment, Multi-objective optimization, K-medoids, Pareto boundary, Principal component analysis

中图分类号:

TP393

刘芳正, 马博闻, 吕博枫, 黄霁崴. 一种面向移动边缘计算的无人机基站部署方法[J]. 计算机科学, 2022, 49(11A): 220200089-7. https://doi.org/10.11896/jsjkx.220200089

LIU Fang-zheng, MA Bo-wen, LYU Bo-feng, HUANG Ji-wei. UAV Base Station Deployment Method for Mobile Edge Computing[J]. Computer Science, 2022, 49(11A): 220200089-7. https://doi.org/10.11896/jsjkx.220200089

参考文献

[1]SHI W S,ZHANG X Z,WANG Y F,et al.Edge Computing:State-of-the-Art and Future Directions[J].Journal of Computer Research and Development,2019,56(1):69-89.
[2]BALASUBRAMANIAN V,OTOUM S,ALOQAILY M,et al.Low-latency vehicular edge:A vehicular infrastructure model for 5g[J/OL].Simulation Modelling Practice and Theory,2020,98:101968.https://doi.org/10.1016/j.simpat.2019.101968.
[3]QI Y L,ZHOU Y Q,LIU L,et al.MEC Coordinated Future 5G Mobile Wireless Networks[J].Journal of Computer Research and Development,2018,55(3):478-486.
[4]ZHANG H J,ZHANG J M,LONG K P.Energy efficiency optimization for NOMA UAV network with imperfect CSI[J].IEEE Journal on Selected Areas in Communication,2020,8(12):2798-2809.
[5]WANG H C,WANG J L,CHEN J,et al.Network-connectedUAV communications:potentials and challenges[J].China Commun,2018,15(12):111-121.
[6]WANG W,ZHAO J J,PENG L,et al.Research on the Energy Saving Strategy for Long Distance Communication of Mobile Internet of Things Based on UAVs[J].Acta Electronica Sinica,2018,46(12):2914-2922.
[7]CHENG F,ZHANG S,LI Z,et al.UAV trajectory optimization for data offloading at the edge of multiple cells[J].IEEE Transactions on Vehicular Technology,2018,67(7):6732-6736.
[8]DU Y,YANG K,WANG K,et al.Joint resources and workflow scheduling in UAV-enabled wirelessly-powered MEC for IoT systems[J].IEEE Transactions on Vehicular Technology,2019,68(10):10187-10200.
[9]LIN C,CHEN Y,HUANG J W,et al.A Survey on Models and Solutions of Multi-Objective Optimization for QoS in Services Computing[J],Chinese Journal of Computers,2015,38(10):1907-1923.
[10]ZENG Y,ZHANG R,TENG J L.Wireless communications with unmanned aerial vehicles:opportunities and challenges[J].IEEE Communications Magazine.2016,54(5):36-42.
[11]URAMA J,WIREN R,GALININA O,et al.UAV-aided interference assessment for private 5G NR deployments:challenges and solutions[J].IEEE Communications Magazine,2020,58(8):89-95.
[12]TAFINTSEV N,GERASIMENKO M,MOLTCHANOV D,et al.Improved network coverage with adaptive navigation of mmwave-based dronecells[C]//Proc of the 2018 IEEE Globecom Workshops (GC Wkshps).2018:1-7.
[13]SAVKIN A V,HUANG H.Deployment of unmanned aerial vehicle base stations for optimal quality of coverage[J].Wireless Communications Letters IEEE,2019,8(1):321-324.
[14]SUN S J,ZHANG G P,MEI H B,et al.Optimizing Multi-UAV Deployment in 3-D Space to Minimize Task Completion Time in UAV-Enabled Mobile Edge Computing Systems[J].IEEE Communications Letters,2021,25(2):579-583.
[15]ZHAO J W,WANG Y,FEI Z X,et al.UAV Deployment Design for Maximizing Effective Data with Delay Constraint in a Smart Farm[C]//Proc of the 2020 IEEE International Conference on Communications in China (ICCC).2020:424-429.
[16]HU J S,ZHANG H L,LIU Y M,et al.An intelligent UAV deployment scheme for load balance in small cell networks using machine learning[C]//Proc of the 2019 IEEE Wireless Communications and Networking Conference (WCNC).NJ:IEEE,2019:1-6.
[17]YANG L,YAO H P,WANG J J,et al.Multi-UAV-enabledload-balance mobile edge computing for IoT networks[J].IEEE Internet of Things Journal,2020,7(8):6898-6908.
[18]WANG H J,ZHAO H T,WU W Y,et al.Deployment algo-rithms of flying base stations:5G and beyond with UAVs[J].IEEE Internet of Things Journal,2019,6(6):10009-10027.
[19]MOZAFFARI M,SAAD W,BENNIS M,et al.Efficient Deployment of Multiple Unmanned Aerial Vehicles for Optimal Wireless Coverage[J].IEEE Communications Letters,2016,20(8):1647-1650.
[20]WANG B J,ZHANG R Q,CHEN C,et al.Density-sware de-ployment with multi-layer UAV-V2X Communication Networks[J].IET Communications,2020,14(16):2709-2715.
[21]GALKIN B,KIBILDA J,DASILVA L A.Deployment of UAV-mounted access points according to spatial user locations in two-tier cellular networks[C]//Proc of the Wireless Days.NJ:IEEE,2016:1-6.
[22]LIU X,LIU Y W,CHEN Y.Reinforcement learning in multiple-UAV networks:Deployment and movement design[J].IEEE Transactions on Vehicular Technology,2019,68(8):8036-8049.
[23]ZENG Y,XU J,ZHANG R.Energy minimization for wireless communication with rotary-wing UAV[J].IEEE Transactions on Wireless Communications,2019,18(4):2329-2345.
[24]HUO Y,DONG X,LU T,et al.Distributed and multilayer UAV networks for next-generation wireless communication and power transfer:A feasibility study[J].IEEE Internet of Things Journal,2019,6(4):7103-7115.
[25]PHU L,HE Q,MOHAMED A,et al.Optimal Edge User Allocation in Edge Computing with Variable Sized Vector Bin Packing[C]//Proc of the 16th International Conference on Service-Oriented Computing (ICSOC2018).Switzerland:Cham,2018:230-245.
[26]WAGSTAFF K,CARDIE C,ROGERS S,et al.Constrained k-means clustering with background knowledge[C]//Proc of the 2001 Proceedings of the International Conference on Machine Learning(ICML).New York:ACM,2001:577-584.

相关文章 15

[1]	李其烨, 邢红杰. 基于最大相关熵的KPCA异常检测方法 KPCA Based Novelty Detection Method Using Maximum Correntropy Criterion 计算机科学, 2022, 49(8): 267-272. https://doi.org/10.11896/jsjkx.210700175
[2]	阙华坤, 冯小峰, 刘盼龙, 郭文翀, 李健, 曾伟良, 范竞敏. Grassberger熵随机森林在窃电行为检测的应用 Application of Grassberger Entropy Random Forest to Power-stealing Behavior Detection 计算机科学, 2022, 49(6A): 790-794. https://doi.org/10.11896/jsjkx.210800032
[3]	孙刚, 伍江江, 陈浩, 李军, 徐仕远. 一种基于切比雪夫距离的隐式偏好多目标进化算法 Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance 计算机科学, 2022, 49(6): 297-304. https://doi.org/10.11896/jsjkx.210500095
[4]	李浩东, 胡洁, 范勤勤. 基于并行分区搜索的多模态多目标优化及其应用 Multimodal Multi-objective Optimization Based on Parallel Zoning Search and Its Application 计算机科学, 2022, 49(5): 212-220. https://doi.org/10.11896/jsjkx.210300019
[5]	彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰. 视频缓存策略中QoE和能量效率的公平联合优化 Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos 计算机科学, 2022, 49(4): 312-320. https://doi.org/10.11896/jsjkx.210800027
[6]	高际航, 张艳. 基于FWA-PSO-MSVM的船舶区域配电电力系统故障诊断 Fault Diagnosis of Shipboard Zonal Distribution Power System Based on FWA-PSO-MSVM 计算机科学, 2022, 49(11A): 210800209-5. https://doi.org/10.11896/jsjkx.210800209
[7]	郭亚琳, 李晓晨, 任志磊, 江贺. 自动化软件重构质量目标与非质量目标有效性研究 Study on Effectiveness of Quality Objectives and Non-quality Objectives for Automated Software Refactoring 计算机科学, 2022, 49(11): 55-64. https://doi.org/10.11896/jsjkx.220300058
[8]	吴善杰, 王新. 基于AGA-DBSCAN优化的RBF神经网络构造煤厚度预测方法 Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks 计算机科学, 2021, 48(7): 308-315. https://doi.org/10.11896/jsjkx.200800110
[9]	胡昕彤, 沙朝锋, 刘艳君. 基于随机投影和主成分分析的网络嵌入后处理算法 Post-processing Network Embedding Algorithm with Random Projection and Principal Component Analysis 计算机科学, 2021, 48(5): 124-129. https://doi.org/10.11896/jsjkx.200500058
[10]	王艺皓, 丁洪伟, 李波, 保利勇, 张颖婕. 基于聚类与特征融合的蛋白质亚细胞定位预测 Prediction of Protein Subcellular Localization Based on Clustering and Feature Fusion 计算机科学, 2021, 48(3): 206-213. https://doi.org/10.11896/jsjkx.200200081
[11]	王珂, 曲桦, 赵季红. 多域SFC部署中基于强化学习的多目标优化方法 Multi-objective Optimization Method Based on Reinforcement Learning in Multi-domain SFC Deployment 计算机科学, 2021, 48(12): 324-330. https://doi.org/10.11896/jsjkx.201100159
[12]	崔国楠, 王立松, 康介祥, 高忠杰, 王辉, 尹伟. 结合多目标优化算法的模糊聚类有效性指标及应用 Fuzzy Clustering Validity Index Combined with Multi-objective Optimization Algorithm and Its Application 计算机科学, 2021, 48(10): 197-203. https://doi.org/10.11896/jsjkx.200900061
[13]	朱汉卿, 马武彬, 周浩浩, 吴亚辉, 黄宏斌. 基于改进多目标进化算法的微服务用户请求分配策略 Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms 计算机科学, 2021, 48(10): 343-350. https://doi.org/10.11896/jsjkx.201100009
[14]	冯安然, 王旭仁, 汪秋云, 熊梦博. 基于PCA和随机树的数据库异常访问检测 Database Anomaly Access Detection Based on Principal Component Analysis and Random Tree 计算机科学, 2020, 47(9): 94-98. https://doi.org/10.11896/jsjkx.190800056
[15]	张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法 Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery 计算机科学, 2020, 47(8): 284-290. https://doi.org/10.11896/jsjkx.190700082

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed