Full Text:   <1041>

Summary:  <1052>

CLC number: TN929.5; TP301.6

On-line Access: 2020-12-10

Received: 2020-07-02

Revision Accepted: 2020-09-09

Crosschecked: 2020-10-29

Cited: 0

Clicked: 2735

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Pei-qiu Huang

https://orcid.org/0000-0001-6278-4566

Yong Wang

https://orcid.org/0000-0001-7670-3958

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2020 Vol.21 No.12 P.1713-1725

http://doi.org/10.1631/FITEE.2000315


Energy-efficient trajectory planning for a multi-UAV-assisted mobile edge computing system


Author(s):  Pei-qiu Huang, Yong Wang, Ke-zhi Wang

Affiliation(s):  School of Automation, Central South University, Changsha 410083, China; more

Corresponding email(s):   pqhuang@csu.edu.cn, ywang@csu.edu.cn, kezhi.wang@northumbria.ac.uk

Key Words:  Multiple unmanned aerial vehicles, Mobile edge computing, Trajectory planning, Differential evolution, k-means clustering algorithm, Greedy method


Pei-qiu Huang, Yong Wang, Ke-zhi Wang. Energy-efficient trajectory planning for a multi-UAV-assisted mobile edge computing system[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(12): 1713-1725.

@article{title="Energy-efficient trajectory planning for a multi-UAV-assisted mobile edge computing system",
author="Pei-qiu Huang, Yong Wang, Ke-zhi Wang",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="21",
number="12",
pages="1713-1725",
year="2020",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2000315"
}

%0 Journal Article
%T Energy-efficient trajectory planning for a multi-UAV-assisted mobile edge computing system
%A Pei-qiu Huang
%A Yong Wang
%A Ke-zhi Wang
%J Frontiers of Information Technology & Electronic Engineering
%V 21
%N 12
%P 1713-1725
%@ 2095-9184
%D 2020
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2000315

TY - JOUR
T1 - Energy-efficient trajectory planning for a multi-UAV-assisted mobile edge computing system
A1 - Pei-qiu Huang
A1 - Yong Wang
A1 - Ke-zhi Wang
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 21
IS - 12
SP - 1713
EP - 1725
%@ 2095-9184
Y1 - 2020
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2000315


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,王勇1,王可之2
1中南大学自动化学院,中国长沙市,410083
2诺桑比亚大学计算机信息科学系,英国纽卡斯尔市,NE18ST

摘要:本文研究多无人机辅助移动边缘计算系统,该系统中无人机可作为边缘服务器为物联网设备提供计算服务。本文目标是通过规划无人机轨迹将系统能耗最小化。规划无人机轨迹不仅要考虑停靠点的访问顺序,还要考虑停靠点的布局(包括其数量和位置)以及无人机与停靠点的关联。为解决该问题,提出一个3阶段的能量有效轨迹规划算法。第一阶段采用种群大小可变的差分进化算法,同时更新停靠点的数量和位置。第二阶段采用k均值聚类算法将给定停靠点聚类为一系列子组,其中子组数目等于无人机数目,且每个子组中包含一个无人机需要访问的所有停靠点。第三阶段提出一种低复杂度的贪婪方法用于快速获取每个子组中停靠点的访问顺序。最后,在一组不同规模的实例上验证所提出算法的有效性。

关键词:多无人机;移动边缘计算;轨迹规划;差分进化算法;k均值聚类算法;贪婪算法

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[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 15th 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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE