基于移动边缘计算的无人机资源分配及轨迹优化.pdf

第 51 卷收稿日期：2023年4月21日，修回日期：2023年5月6日作者简介：崔维庆，男，硕士研究生，研究方向：移动边缘计算。1引言近年来，传感器网络被广泛应用到农作物环境检测、森林火灾检测、健康监护、交通控制以及家庭自动化等领域，可以有效地检测温度、湿度、压力、声音及运动状态等信息。然而，传感器网络中的传感器设备电池容量有限且计算能力有限，并且位置偏远或恶劣环境中的传感器不方便进行信息采集处理1。这对传感器设备带来了许多挑战。将无人机应用到传感器网络中利用了移动边缘计算（MEC）的思想23，无人机作为移动边缘云更加靠近传感器，能够减少路径损耗46，进而提高传感器设备的上传速率，为MEC系统带来更大的收益。另一方面，MEC系统中的无人机给传感器设备带来便利的同时也造成了也给自身带来了相当多的能耗7，并且优化无人机在整个MEC系统中的资源分配可以合理利用无人机作为边缘云和移动基站的计算资源和通信资源89，设计无人机的飞行轨迹可以减少无人机的飞行能耗并且给传感器设备带来更加有力的通信条件1011。Zeng等设计一种新型的基于时分多址的工作流模型，并联合优化无人机和物联网设备之间的通信关联、计算资源、无人机悬停时间和物联网设备的服务序列来最小化无人机的总能耗12。Mei等将无人机作为边基于移动边缘计算的无人机资源分配及轨迹优化崔维庆（中国石油大学（华东）计算机科学与技术学院青岛266580）摘要传感器网络中传感器设备计算能力有限，且不方便收集处理其存储的信息。针对这个问题，提出一种传感器网络中无人机支持下的移动边缘计算系统，且对无人机设计一种动态任务缓存模型。提出一种基于天牛群算法的块坐标下降法来提高无人机的能耗效率，并引入Cubic映射和Le vy飞行改进天牛群算法得到最优的无人机轨迹。实验结果表明，与其他能耗控制方法相比，该方法提高了无人机的能耗效率，进而提高整个移动边缘计算系统的收益。关键词无人机；资源分配；轨迹优化；天牛群算法；块坐标下降法中图分类号TN929.5DOI：10.3969/j.issn.1672-9722.2023.10.020Resource Allocation and Trajectory Optimization of the UAVBased on Mobile Edge ComputingCUI Weiqing（College of Computer Science and Technology，China University of Petroleum（East China），Qingdao266580）AbstractSensors in wireless sensor network have limited computing capability，and it is not convenient to harvest the storedinformation for processing.To address this problem，an UAV assisted mobile edge computing system is proposed in wireless sensornetwork，and a dynamic task caching model based on the UAV is presented.In this paper，the block coordinate descent algorithmon the strength of the beetle swarm optimization is used to maximize the energy efficiency of the UAV.And the optimal UAV trajectory is derived by the beetle swarm optimization based on Cubic mapping andLe vyflight mutation mechanism.Numerical results indicate that the proposed algorithm improve the energy efficiency of the UAV compared with other solutions，and then increase therevenue of the total mobile edge computing system.Key Wordsunmanned aerial vehicle（UAV），resource allocation，trajectory optimization，beetle swarm optimization，block coordinate descent algorithmClass NumberTN929.5总第 408 期2023 年第 10 期计算机与数字工程Computer&Digital EngineeringVol.51 No.1023182023 年第 10 期计算机与数字工程缘云为每一个地面终端配备了移动克隆，通过网络功能虚拟化实现的移动克隆来执行地面终端卸载的任务，最终使用块坐标下降法得到最优的资源分配和无人机轨迹13。本文将无人机作为移动基站收集传感器设备的信息，并作为边缘云与中央云共同分析处理收集到的数据。首先根据数据流动方向设计无人机端的任务缓存模型，动态表示系统中的数据流向。然后使用基于天牛群算法的块坐标下降法来优化无人机的通信资源、计算资源和飞行轨迹来最大化无人机的能耗效率，并且引入Cubic混沌映射和Le vy飞行对天牛群算法进行改进。2问题描述2.1通信模型传感器网络中无人机支持下的移动边缘计算系统模型如图 1 所示，其中中央云与基站有线连接。无人机作为移动基站配备有信号收发器可以为传感器提供通信服务，并且作为边缘云配备有轻量级服务器可以提供计算服务。本文采用部分卸载策略，无人机接收传感器上传的数据并在本地处理一部分数据，然后将剩余数据卸载到中央云，无人机可以同时进行数据收集、数据处理和任务卸载。固定翼无人机2任务卸载3回程 1数据上传中央云传感器设备图1无人机支持下的移动边缘计算系统模型图为了结合现实，无人机支持下的移动边缘计算系统使用了一个三维的欧几里得坐标。M个异构传感器不均匀地分布在二维平面内，在平面内的位置表示为qm=xmym，mM，M=1，2，M，并且这些传感器设备的坐标对无人机来说是已知的。在整个任务处理期间，无人机在一个固定的高度H飞行，并且本文将无人机轨迹分解为N条轨迹段，用N+1个轨迹点xnynHNn=0来表示，nN，N=1，2，N。tnNn=1表示无人机在第n条轨迹段飞行的时间。传感器设备中的任务数据可分，即可以在两个或多个服务器中处理该数据并将反馈的结果统一分析。将每个传感器设备中待处理的任务定义为 RmFm，mM。Rm表示第m个设备待处理任务的数据规模，Fm表示处理任务所需的CPU周期数。本文使用正交频分多址来消除传感器与无人机之间的通信干扰14，无人机和传感器m之间的信道增益表示为m n=0d2mn=0H2+qu n qm2（1）其中0是距离为1m时的信道增益；dmn表示无人机在第n条轨迹段与传感器m之间的距离；表示欧几里得范数。则传感器m在无人机第n条轨迹段的上传速率表示为Vm n=mnB1log2(1+Pmm n2)（2）其中mnB1表示分配给传感器m的带宽；Pm是传感器m的上传功率；2表示传感器m上的噪声功率。值得注意的是，当无人机在第n条轨迹段和传感器m没有通信连接时，Vm n的值为0。当无人机接收到传感器上传的数据后，其中一部分数据在本地进行处理，另一部分卸载到中央云，卸载速率表示为Vu n=B2log2(1+Pnn2)（3）其中 n=0H2+qu n qe2表示无人机在第n条轨迹段与中央云之间的信道增益；qe=xeye表示中央云的坐标；Pn是无人机的卸载速率。2.2任务缓存模型对于本地计算方法，本文假设无人机数据的一部分Dn（0，1）在无人机本地处理，则剩余的()1 Dn卸载到中央云上处理，本文定义fnFu为无人机的计算能力（每秒的CPU周期数），Fu表示无人机服务器的最大计算能力。对于中央云服务器计算方法，中央云边收集无人机上传的数据边进行分析处理。中央云有充足的计算能力能够确保数据在有限时间内处理完成。让Hn表示无人机在每一轨迹段终点的队列长度，表示为Hn+1=HnDn+An。An表示无人机在第n条轨迹段接收到的数据，表示为An=m=1MVm n tn（4）Dn表示无人机在第n条轨迹段在本地处理的数据以及卸载数据的总和，表示为2319第 51 卷Dn=fntn+Vuntn（5）其中=0.025表示处理单位比特数据所需的CPU周期数，并且本文假设无人机从第2条轨迹段开始处理和卸载数据。则在时间T内处理的总数据量表示为D=n=2NDn。2.3能耗效率模型本文的目标是最大化无人机的能耗效率，首先建立无人机的能耗模型，无人机的能耗由三部分组成：本地计算的能耗、卸载数据的能耗以及飞行能耗。无人机服务器在本地处理数据的能耗表示为Ec=n=2Nktnf3n（6）其中k=1026表示能量转化能力。无人机在整个任务处理时间T内卸载数据的能耗表示为Eu=n=2NPntn（7）本文所使用的无人机为固定翼无人机，其能耗模型表示为Euav=n=1Ntn(c1v3 n+c2vn)（8）其中c1和c2是两个与无人机重量、飞行翼范围及密度有关的常数；vn表示无人机在第n条轨迹段的飞行速度，表示为v n=qu n qun1tn（9）其中qu n qun1表示无人机在第n条轨迹段的飞行距离。本 文 定 义 无 人 机 的 能 耗 效 率 模 型 为D1(Ec+Eu)+2Euav，其中1与2是两个常数用来平衡这两部分的能耗。2.4问题描述本文的优化问题是最大化无人机在传感器网络 中 的 能 耗 效 率。让F=fnnN，P=Pn nN，T=tnnN，Q=qnnN，则问题P可以表示为maxFPTQD1(Ec+Eu)+2Euav（10）s.t.C1：n=1Ntn=TC2：0PnPmaxC3：0fnFuC4：vminv n vmaxC5：qu n qun1max其中C1是有关无人机飞行时间的限制条件；C2确保无人机的上传功率在可控制的范围内；C3确保无人机的计算能力不超过其最大限制；C4确无人机的飞行速度在可控制范围内；C5确保在每条轨迹段内无人机和传感器设备之间的距离基本不变。3基于天牛群算法的块坐标下降法问题P的目标函数和限制条件有非凸性，因此本文使用块坐标下降法来分布迭代求解问题P，得到最优的资源分配和无人机轨迹。3.1资源分配本文首先将问题P转化为两个有关计算资源F和通信资源P的子问题P1和P2，问题P1表示为maxFn=2Nfntn/n=2Nktnf3n（11）s.t.0fnFu问题P2表示为maxPn=2NVuntnn=2NPntn（12）s.t.0PnPmax本文对问题P1和问题P2分别使用KKT条件和拉格朗日乘子法求解15，得到最优的计算资源F*和通信资源P*。3.2轨迹优化根据得到的最优的计算资源和通信资源，本文将问题P转化为两个有关无人机飞行时间T和无人机轨迹Q的子问题P3和P4，问题P3表示为maxTD1(Ec+Eu)+2Euav（13）s.t.n=1Ntn=T不难看出问题P3是一个线性规划问题，本文使用Matlab里的linprog函数对问题P3求解得到最优的无人机飞行时间T*。有关无人机飞行轨迹的子问题P4表示为minQn=1Ntn(c1v3 n+c2vn)（14）s.t.vminv n vmaxqu n qun1max崔维庆：基于移动边缘计算的无人机资源分配及轨迹优化23202023 年第 10 期计算机与数字工程本文使用改进的天牛群算法来求解此问题14，天牛群算法结合了天牛须算法和粒子群算法1516，解决了传统天牛须算法面对多维问题收敛性差的问题。并且本文引入了Cubic混沌映射生成多样性的初始种群17，引入Le vy飞行策略扰动最优个体位置避免求得局部最优解18。基于Cubic混沌映射与Le vy飞行的天牛群算法介绍如下：首先，使用Cubic混沌映射生成多样性的初始种群：xi+1=xi(1x2i)（15）其中iI表示第i个天牛，I=1，2，I，为控制参数。每个天牛都代表一架无人机，本文先初始化多架无人机的位置和飞行速度，无人机的初始位置表示为Xti=(xti1xti2xtinxtiN)，初始速度表示为Vti=(vti1vti2vtinvtiN)。然后定义最优的无人机位置为Ptg=(ptg1ptg2ptgnptgN)，每架无人机的最优位置为Pti=(pti1pti2ptinptiN)。最后定义无人机群的随机搜索方向为dti=rand(1D)rand(1D)（16）天牛须长与最优的种群位置和个体最优位置相关，因此每架无人机的左右须长表示为lti=Ptg-Pti（17）其中表示缩放因子。然后每架无人机的左右须坐标分别表示为Xtil=Xtiltidti（18）Xtir=Xti+ltidti（19）每架无人机的速度更行方式为Vt+1i=Vti+C1rand()1D*()PtiXti+C2rand()1D*()PtgXti（20）其中表示惯性权重；C1和C2是两个常数代表学习因子；A*B表示具有相同形状的矩阵A和B对应元素逐个相乘。本文设置惯性权重和缩放因子随时间递减来增强前期的全局搜索能力和后期的局部搜索能力。=max-tT(max-min)（21）=max-tT(max-min)（22）另外本文定义增量函数的更新方式为t+1=ltirand(1D)*dtisignf(Xtil)-f(Xtir)（23）其中ltirand(1D)表示步长与最优的种群位置和个体最优位置相关。最终每架无人机的位置更新方式表示为Xt+1i=Xti+Vt+1i+(1-)t+1（24）其中=0.6。然而，启发式算法容易出现早熟收敛状态，此时无人机最优位置为一局部最优解，无人机通常向无人机群最优解位置靠近，从而导致无人机聚集在局部最优解附近。为了使无人机跳出局部最优解，本文对最优的无人机位置使用Le vy飞行对进行扰动，使其跳出局部最优解，Le vy飞行扰动表示如下：xt+1gk=xtgk*(1+*L()（25）其中L()=|v1/，=1+，和服从标准正态分布。最终算法得到的最优的无人机位置为最优的无人机轨迹Q*。3.3算法实现基于天牛群算法的块坐标下降法流程如图 2所示。使用改进的天牛群算法得到最优的无人机轨迹算法开始初始化场景信息并构建无人机能耗效率模型使用KKT条件得到最优的计算资源分配使用拉格朗日乘子法得到最优的通信资源分配使用linprog函数得到最优的无人机飞行时间算法收敛到给定的准确度YN算法结束得到最大的无人机能耗效率及最优的优化参数图2算法流程图4实验分析本文将基于天牛群算法的块坐标下降法应用于传感器网络中无人机的资源分配和轨迹优化，使用Matlab软件进行算法仿真实验，本文提出的算法2321第 51 卷和对比算法均部署在 Windows 10，64bit；Matlab2018b，处 理 器 为 AMD Ryzen 5600H；主 频 为3.3GHz；内存为16.0GB。本文假设传感器设备不均匀地分布在 100100m2的地面上，且基站的坐标为 0，0，具体的参数如表1所示。表1模拟实验所用的参数参数MTHB1B2Rm0201，2Pmvmin，vmaxPmaxFu值710s5m10MHz20MHz40Mb-30dB-60dBm100,1200mW5m/s，35m/s5W108cycles/s参数意义传感器设备数量总飞行时间无人机飞行高度无人机与传感器设备间的通信带宽无人机与中央云间的通信带宽传感器设备需要处理的数据量距离为1m时的信道增益噪声功率平衡因子传感器传输功率无人机飞行的最小及最大速度无人机最大的传输功率无人机最大的计算能力使用基于天牛群算法的块坐标下降法得到的无人机轨迹如图3所示。传感器设备位置基站位置无人机轨迹10108 86420h/m100100806040200 x/m020406080100y/m图3无人机轨迹图为了验证本论文提出的算法（OP）的有效性，将其与另外三种方法进行比较，方法1采用了二元卸载策略（BOM），方法2使用了网络功能虚拟化技术（NFV）12，方法3使用了工作流调度（WS）13。如图4所示，以收集数据规模为横坐标，以无人机能耗效率为纵坐标画出本论文算法与其他方法的对比图，能够直观看出采用本文基于天牛群算法的块坐标下降法的能耗效率要大于其他三种方法。这说明本文提出的算法性能更好，并使得无人机的能耗效率更高，进而降低无人机能耗给传感器网络中的无人机带来更大的收益。21051105能耗效率/（bit/J）2.8109收集到的数据量/bitOPBOMNFVWS图4无人机能耗效率对比图5结语基于传感器网络中传感器设备计算能力不足和不方便收集处理其存储数据的问题，本论文提出一种传感器网络中无人机支持下的移动边缘计算系统模型。首先设计一种无人机端的任务缓存模型动态表示数据流动方向，然后提出一种基于天牛群算法的块坐标下降法来优化无人机的通信资源、计算资源和飞行轨迹，其中天牛群算法中引入了Cubic混沌映射和Le vy飞行策略能够得到最优的无人机轨迹，最终得到了最大的无人机能耗效率。实验结果表明，该算法能够显著提高无人机的能耗效率，从而保证无人机给传感器设备带来计算服务的同时能够有效控制自身功耗。参 考 文 献1Mozaffari M，Saad W，Bennis M，et al.A Tutorial onUAVs for Wireless Networks：Applications，Challenges，and Open ProblemsJ.IEEE Communications SurveysTutorials，2019，21（3）：2334-2360.2Kuang Z，Li L，Gao J，et al.Partial Offloading Scheduling and Power Allocation for Mobile Edge Computing Systems J.IEEE Internet of Things Journal，2019，6（4）：6774-6785.3Chen M，Hao Y.Task Offloading for Mobile Edge Computing in Software Defined Ultra-Dense NetworkJ.IEEEJournal on Selected Areas in Communications，2018，36（3）：587-597.4Linghe，Kong，Linsheng，et al.Autonomous Relay forMillimeter-Wave Wireless CommunicationsJ.IEEEJournal on Selected Areas in Communications，2017，35（9）：2127-2136.5Zhang S，Zhang H，Di B，et al.Joint Trajectory and Power Optimization for UAV Relay Networks J.IEEE Com（下转第2389页）崔维庆：基于移动边缘计算的无人机资源分配及轨迹优化23222023 年第 10 期计算机与数字工程（5）：119-139.11李家春，李芝棠.入侵检测的规划识别模型研究 J.华中科技大学学报（自然科学版），2004，32（3）：80-82.LI Jiachun，LI Zhitang.Research on planning and identification model of intrusion detectionJ.Journal of Huazhong University of science and Technology（Natural Science Edition），2004，32（3）：80-82.12Kautz H，Allen J F.Generalized plan recognitionC/Proceedings of the Fifth National Conference on Artificial Intelligence.Philadelphia，PA，1986.13蔡增玉，冯媛，甘勇.基于加权规划知识图的入侵规划识 别 研 究J.科 学 技 术 与 工 程，2014，14（14）：257-260.CAI Zengyu，FENG Yuan，GAN Yong.Research on intrusion planning recognition based on weighted planningknowledge graphJ.Science，Technology and Engineering，2014，14（14）：257-260.14 刘啸剑，谢飞，吴信东.基于图和LDA主题模型的关键词抽取算法 J.情报学报，2016，35（06）：664-672.LIU Xiaojian，XIE Fei，WU Xindong.Keyword extraction algorithm based on graph and LDA topic modelJ.Journal of Information Technology，2016，35（06）：664-672.15颜奇.基于皮尔逊相关系数的差分隐私决策树方法研究 D.桂林：广西师范大学，2021.YAN Qi.Research on differential privacy decision treemethod based on Pearson correlation coefficientD.Guilin：Guangxi Normal University，2021.munications Letters，2018，22（1）：161-164.6Mozaffari M，Saad W，Bennis M，et al.Unmanned AerialVehicle with Underlaid Device-to-Device Communications：Performance and TradeoffsJ.IEEE Transactionson Wireless Communications，2016，15（6）：3949-3963.7Zeng Y，Zhang R.Energy-Efficient UAV Communicationwith Trajectory OptimizationJ.IEEE Transactions onWireless Communications，2017，16（6）：3747-3760.8Du Y，Yang K，Wang K，et al.Joint Resources and Workflow Scheduling in UAV-Enabled Wirelessly-PoweredMEC for IoT Systems J.IEEE Transactions on VehicularTechnology，2019，68（10）：10187-10200.9Wang H，Wang J，Ding G，et al.Resource Allocation forEnergy Harvesting-Powered D2D Communication Underlaying UAV-Assisted Networks J.IEEE Transactions onGreen Communications&Networking，2018，2（1）：14-24.10Xu J，Zeng Y，Zhang R.UAV-Enabled Wireless PowerTransfer：Trajectory Design and Energy OptimizationJ.IEEE Transactions on Wireless Communications，2018，17（8）：5092-5106.11Hu X，Wong K K，Zhang Y.Wireless-Powered EdgeComputing with Cooperative UAV：Task，Time Scheduling and Trajectory DesignJ.IEEE Transactions onWireless Communications，2020，19（12）：8083-8098.12Zeng Y，Zhang R.Energy-Efficient UAV Communication with Trajectory Optimization J.IEEE Transactionson Wireless Communications，2017，16（6）：3747-3760.13H Mei，Yang K，Liu Q，et al.Joint Trajectory-ResourceOptimization in UAV-Enabled Edge-Cloud System withVirtualized Mobile CloneJ.IEEE Internet of ThingsJournal，2019，7（7）：5906-5921.14Yin H，Alamouti S.OFDMA：a broadband wireless access technologyC/IEEE Sarnoff Symposium.Princeton，NJ：IEEE，2006：33-36.15Boyd，Vandenberghe，Faybusovich.Convex OptimizationJ.IEEE Transactions on Automatic Control，2006，51（11）：1859-1859.16Wang T，Long Y，Qiang L.Beetle Swarm OptimizationAlgorithm：Theory and Application J.Filomat，2018，34（15）：5127-5137.17Zhu Z，Zhang Z，Man W，et al.A new beetle antennaesearch algorithm for multi-objective energy managementin microgridC/IEEE Conference on Industrial Electronics and Applications.Wuhan，Peoples R China：IEEE，2018：1599-1603.18Eberhart R，Kennedy J.A new optimizer using particleswarm theory C/Mhs95 Sixth International Symposiumon Micro Machine&Human Science.IEEE，2002：39-43.19Fogedby H C.Lvy flights in random environments J.Phys.rev.lett，1994，73（19）：2517.20Palacios，Antonio.Cycling Chaos in One-DimensionalCoupled Iterated Maps J.International Journal of Bifurcation&Chaos，2002，12（08）：1859-1868.（上接第2322页）2389