Similar articles

Abstract: We study a mobile edge computing system assisted by multiple unmanned aerial vehicles (UAVs), where the UAVs act as edge servers to provide computing services for Internet of Things devices. Our goal is to minimize the energy consumption of this system by planning the trajectories of UAVs. This problem is difficult to address because when planning the trajectories, we need to consider not only the order of stop points (SPs), but also their deployment (including the number and locations) and the association between UAVs and SPs. To tackle this problem, we present an energy-efficient trajectory planning algorithm (TPA) which comprises three phases. In the first phase, a differential evolution algorithm with a variable population size is adopted to update the number and locations of SPs at the same time. In the second phase, the k-means clustering algorithm is employed to group the given SPs into a set of clusters, where the number of clusters is equal to that of UAVs and each cluster contains all SPs visited by the same UAV. In the third phase, to quickly generate the trajectories of UAVs, we propose a low-complexity greedy method to construct the order of SPs in each cluster. Compared with other algorithms, the effectiveness of TPA is verified on a set of instances at different scales.

多无人机辅助移动边缘计算系统能量有效的轨迹规划

[1]Chan TM, Man KF, Tang KS, et al., 2007. A jumping-genes paradigm for optimizing factory WLAN network. IEEE Trans Ind Inform, 3(1):33-43.

[2]Chen J, Zhang X, Xin B, et al., 2016. Coordination between unmanned aerial and ground vehicles: a taxonomy and optimization perspective. IEEE Trans Cybern, 46(4):959-972.

[3]Chen WH, Liu BC, Huang HW, et al., 2019. When UAV swarm meets edge-cloud computing: the QoS perspective. IEEE Netw, 33(2):36-43.

[4]Diao XH, Zheng JC, Cai YM, et al., 2019. Fair data allocation and trajectory optimization for UAV-assisted mobile edge computing. IEEE Commun Lett, 23(12):2357-2361.

[5]Du Y, Yang K, Wang KZ, et al., 2019. Joint resources and workflow scheduling in UAV-enabled wirelessly-powered MEC for IoT systems. IEEE Trans Veh Technol, 68(10):10187-10200.

[6]Garg S, Singh A, Batra S, et al., 2018. UAV-empowered edge computing environment for cyber-threat detection in smart vehicles. IEEE Netw, 32(3):42-51.

[7]Hu XY, Wong KK, Yang K, et al., 2019. UAV-assisted relaying and edge computing: scheduling and trajectory optimization. IEEE Trans Wirel Commun, 18(10):4738-4752.

[8]Huang L, Wang GC, Bai T, et al., 2017. An improved fruit fly optimization algorithm for solving traveling salesman problem. Front Inform Technol Electron Eng, 18(10):1525-1533.

[9]Huang PQ, Wang Y, Wang KZ, et al., 2020a. A bilevel optimization approach for joint offloading decision and resource allocation in cooperative mobile edge computing. IEEE Trans Cybern, 50(10):4228-4241.

[10]Huang PQ, Wang Y, Wang KZ, et al., 2020b. Differential evolution with a variable population size for deployment optimization in a UAV-assisted IoT data collection system. IEEE Trans Emerg Top Comput Intell, 4(3):324-335.

[11]Jain AK, 2010. Data clustering: 50 years beyond K-means. Patt Recogn Lett, 31(8):651-666.

[12]Jeong S, Simeone O, Kang J, 2018. Mobile edge computing via a UAV-mounted cloudlet: optimization of bit allocation and path planning. IEEE Trans Veh Technol, 67(3):2049-2063.

[13]Jin MS, Gao S, Luo HB, et al., 2019. Cost-effective resource segmentation in hierarchical mobile edge clouds. Front Inform Technol Electron Eng, 20(9):1209-1220.

[14]Li MS, Cheng N, Gao J, et al., 2020. Energy-efficient UAV-assisted mobile edge computing: resource allocation and trajectory optimization. IEEE Trans Veh Technol, 69(3):3424-3438.

[15]Low JE, Sufiyan D, Win LST, et al., 2019. Design of a hybrid aerial robot with multi-mode structural efficiency and optimized mid-air transition. Unmann Syst, 7(4):195-213.

[16]Mozaffari M, Saad W, Bennis M, et al., 2019. A tutorial on UAVs for wireless networks: applications, challenges, and open problems. IEEE Commun Surv Tutor, 21(3):2334-2360.

[17]Ryerkerk M, Averill R, Deb K, et al., 2019. A survey of evolutionary algorithms using metameric representations. Genet Program Evol Mach, 20(4):441-478.

[18]Storn R, Price K, 1997. Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim, 11(4):341-359.

[19]Ting CK, Lee CN, Chang HC, et al., 2009. Wireless heterogeneous transmitter placement using multiobjective variable-length genetic algorithm. IEEE Trans Syst Man Cybern Part B (Cybern), 39(4):945-958.

[20]Wang BC, Li HX, Zhang QF, et al., 2018. Decomposition-based multiobjective optimization for constrained evolutionary optimization. IEEE Trans Syst Man Cybern Syst, in press.

[21]Wang JH, Zhou Y, Wang Y, et al., 2016. Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: formulation, instances, and algorithms. IEEE Trans Cybern, 46(3):582-594.

[22]Wang KZ, Huang PQ, Yang K, et al., 2019. Unified offloading decision making and resource allocation in ME-RAN. IEEE Trans Veh Technol, 68(8):8159-8172.

[23]Wang L, Huang PQ, Wang KZ, et al., 2019. RL-based user association and resource allocation for multi-UAV enabled MEC. Proc 15^th Int Wireless Communications & Mobile Computing Conf, p.741-746.

[24]Wang Y, Cai ZX, Zhang QF, 2011. Differential evolution with composite trial vector generation strategies and control parameters. IEEE Trans Evol Comput, 15(1):55-66.

[25]Wang Y, Liu H, Long H, et al., 2018. Differential evolution with a new encoding mechanism for optimizing wind farm layout. IEEE Trans Ind Inform, 14(3):1040-1054.

[26]Wang Y, Ru ZY, Wang KZ, et al., 2020. Joint deployment and task scheduling optimization for large-scale mobile users in multi-UAV-enabled mobile edge computing. IEEE Trans Cybern, 50(9):3984-3997.

[27]Xin B, Chen J, Zhang J, et al., 2012. Hybridizing differential evolution and particle swarm optimization to design powerful optimizers: a review and taxonomy. IEEE Trans Syst Man Cybern Part C (Appl Rev), 42(5):744-767.

[28]Xu JW, Ota K, Dong MX, et al., 2018. SIoTFog: Byzantine-resilient IoT fog networking. Front Inform Technol Electron Eng, 19(12):1546-1557.

[29]Yang ZH, Pan CH, Wang KZ, et al., 2019. Energy efficient resource allocation in UAV-enabled mobile edge computing networks. IEEE Trans Wirel Commun, 18(9):4576-4589.

[30]Zaini AH, Xie LH, 2020. Distributed drone traffic coordination using triggered communication. Unmann Syst, 8(1):1-20.

[31]Zhang J, Huang T, Wang S, et al., 2019. Future Internet: trends and challenges. Front Inform Technol Electron Eng, 20(9):1185-1194.

[32]Zhang J, Zhou L, Zhou FH, et al., 2020. Computation-efficient offloading and trajectory scheduling for multi-UAV assisted mobile edge computing. IEEE Trans Veh Technol, 69(2):2114-2125.

[33]Zhang L, Zhao Z, Wu QW, et al., 2018. Energy-aware dynamic resource allocation in UAV assisted mobile edge computing over social Internet of vehicles. IEEE Access, 6:56700-56715.

[34]Zollars MD, Cobb RG, Grymin DJ, 2019. Optimal SUAS path planning in three-dimensional constrained environments. Unmann Syst, 7(2):105-118.