Placement of unmanned aerial vehicles as communication relays in two-tiered multi-agent system: clustering based methods

doi:10.23919/JSEE.2020.000001

Journal of Systems Engineering and Electronics ›› 2020, Vol. 31 ›› Issue (2): 231-242.doi: 10.23919/JSEE.2020.000001

• Electronics Technology • Next Articles

Placement of unmanned aerial vehicles as communication relays in two-tiered multi-agent system: clustering based methods

Gaofeng WU(), Kaifang WAN*(), Xiaoguang GAO(), Xiaowei FU()

College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China

Received:2019-04-11 Online:2020-04-30 Published:2020-04-30
Contact: Kaifang WAN E-mail:wgfnwpu@163.com;wankaifang@nwpu.edu.cn;cxg2012@nwpu.edu.cn;fxw@nwpu.edu.cn
About author:WU Gaofeng was born in 1991. He received his B.S. degree in detection homing and control technology from Northwestern Polytechnical University (NWPU) in 2012. He received his M.S. degree in system engineering from NWPU in 2015. He is currently a doctoral student in the Key Laboratory of Aerospace Information Perception and Photoelectric Control, Ministry of Education, NWPU. His research interests include UAV task planning, multi-agent systems, optimization and control of UAV-assisted communication networks and internet of things. E-mail: wgfnwpu@163.com|WAN Kaifang was born in 1987. He received his B.E. degree in detection homing and control technology and his Ph.D. degree in system engineering from Northwestern Polytechnical University (NWPU) in 2010 and 2016, respectively. He is currently an assistant researcher of the Key Laboratory of Aerospace Information Perception and Photoelectric Control, Ministry of Education, NPU. His research interests include sensor management application, multi-agent theory, approximate dynamic programming and reinforcement learning theory. E-mail: wankaifang@nwpu.edu.cn|GAO Xiaoguang was born in 1957. She received her B.E. degree in detection homing and control technology from Northwestern Polytechnical University (NWPU) in 1982. She received her master degree in system engineering from NWPU in 1986. She received her Ph.D. degree from NWPU in 1989. She is currently a professor and the head in the Key Laboratory of Aerospace Information Perception and Photoelectric Control, Ministry of Education, NWPU. Her research interests include machine learning theory, Bayesian network theory, and multi-agent control application. E-mail: cxg2012@nwpu.edu.cn|FU Xiaowei was born in 1976. He received his B.S., M.S., and Ph.D. degrees from the School of Electronics and Information, Northwestern Polytechnical University (NWPU) in 1998, 2001, and 2004, respectively. He was a postdoctoral fellow with NWPU from 2004 to 2007. He joined the School of Electronics and Information, in 2004 and became an associate professor, in 2007. His research interests include UAVs cooperative control and optimization, and intelligent optimization algorithm. E-mail: fxw@nwpu.edu.cn
Supported by:
the National Natural Science Foundation of China(61573285);This work was supported by the National Natural Science Foundation of China (61573285)

Abstract

Abstract:

The network performance and the unmanned aerial vehicle (UAV) number are important objectives when UAVs are placed as communication relays to enhance the multi-agent information exchange. The problem is a non-deterministic polynomial hard (NP-hard) multi-objective optimization problem, instead of generating a Pareto solution, this work focuses on considering both objectives at the same level so as to achieve a balanced solution between them. Based on the property that agents connected to the same UAV are a cluster, two clustering-based algorithms, M-K-means (MKM) and modified fast search and find density of peaks (MFSFDP) methods, are first proposed. Since the former algorithm requires too much computational time and the latter one requires too many relays, an algorithm for the balanced network performance and relay number (BPN) is proposed by discretizing the area to avoid missing the optimal relay positions and defining a new local density function to reflect the network performance metric. Simulation results demonstrate that the proposed algorithms are feasible and effective. Comparisons between these algorithms show that the BPN algorithm uses fewer relay UAVs than the MFSFDP and classic set-covering based algorithm, and its computational time is far less than the MKM algorithm.

Key words: unmanned aerial vehicle (UAV), relay, communication, clustering, relay node placement, wireless network

Gaofeng WU, Kaifang WAN, Xiaoguang GAO, Xiaowei FU. Placement of unmanned aerial vehicles as communication relays in two-tiered multi-agent system: clustering based methods[J]. Journal of Systems Engineering and Electronics, 2020, 31(2): 231-242.

Figures/Tables 12

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Fig 9

Fig 10

Fig 11

Fig 12

References 54

1	ALJEHANI M, INOUE M. Communication and autonomous control of multi-UAV system in disaster response tasks. Smart Innovation, Systems and Technologies, 2017, 74, 123- 132.
2	CURRY J A, MASKLANIK J, HOLLAND G, et al. Applications of aerosondes in arctic. Bulletin of the American Meteorological Society, 2004, 85 (12): 1855- 1861. doi: 10.1175/BAMS-85-12-1855
3	WAGNER A, ARKIN R. Multi-robot communication-sensitive reconnaissance. Proc. of the IEEE International Conference on Robotics and Automation, 2003, 4674- 4681.
4	YANG W L, LUO L, DENG J S. Optimization and improvement for multi-UAV cooperative reconnaissance mission planning problem. Proc. of the 11th International Computer Conference on Wavelet Active Media Technology and Information Processing, 2014, 10- 15.
5	CASBEER D W, BEARD R W, MCLAIN T W. Forest fire monitoring with multiple small UAVs. Proc. of American Control Conference, 2015, 3530- 3535.
6	U. S. Office of the Secretary of Defense. Unmanned Aircraft Systems Roadmap, 2005: 2005-2030.
7	GOLDSMITH A. Wireless communication. Cambridge: Cambridge University Press, 2005.
8	VALAVANIS K P, VACHTSEVANOS G J. Handbook of unmanned aerial vehicles. New York: Springer, 2015.
9	RANGA V, DAVE M, VERMA A K. Relay node placement to heal partitioned wireless sensor networks. Computers and Electrical Engineering, 2015, 48, 371- 388. doi: 10.1016/j.compeleceng.2015.09.014
10	CHANDRASHEKAR K, DEKHORDI M R, BARAS J S. Providing full connectivity in large ad hoc networks by dynamic placement of aerial platforms. Proc. of the IEEE Military Communication Conference, 2004, 1429- 1436.
11	SENTURK I F, AKKAYA K, YILMAZ S. Relay placement for restoring connectivity in partitioned wireless sensor networks under limited information. Ad Hoc Networks, 2014, 13, 487- 503. doi: 10.1016/j.adhoc.2013.09.005
12	CALINESCU G. Relay placement for two-connectivity. Discrete Optimization, 2014, 14, 17- 33. doi: 10.1016/j.disopt.2014.06.002
13	HOU Y T, SHI Y, SHERALI H D, et al. On energy provision and relay node placement for wireless sensor networks. IEEE Trans. on Wireless Communications, 2005, 4 (5): 2579- 2590. doi: 10.1109/TWC.2005.853969
14	MISRA S, MAJD N E, HUANG H. Approximation algorithms for constrained relay node placement in energy harvesting wireless sensor networks. IEEE Trans. on Computers, 2014, 60 (12): 2933- 2947.
15	MA C F, LIANG W, ZHENG M. Delay constrained relay node placement in wireless sensor networks-a subtree-and-mergence based approach. Mobile Network Application, 2018, 23, 1220- 1232. doi: 10.1007/s11036-017-0815-z
16	BHATTACHARYA A, KUMAR A. Delay constrained optimal relay placement for planned wireless sensor networks. Proc. of the IEEE 18th International Workshop on Quality of Service, 2010, 1- 0.
17	BHATTACHARYA A, KUMAR A. A shortest path tree based algorithm for relay placement in a wireless sensor network and its performance analysis. Computer Networks, 2014, 71 (4): 48- 62.
18	MA C F, LIANG W, ZHENG M. Delay constrained relay node placement in two-tiered wireless sensor networks: a set-covering-based algorithm. Journal of Network and Computer Applications, 2017, 93, 76- 90. doi: 10.1016/j.jnca.2017.05.004
19	HAN B, LI J, SU J. Optimal relay node placement for multi-pair cooperative communication in wireless net-works. Proc. of the IEEE Wireless Communications and Networking Conference, 2013, 4724- 4729.
20	ISLAM M, DZIONG Z, SOHRABY K. Capacity-optimal relay and base station placement in wireless networks. Proc. of the International Conference on Information Networking, 2012, 358- 363.
21	BARI A, TENG D, AHMED R, et al. Relay node placement with energy and buffer constraints in wireless sensor networks using mobile data collector. International Journal of Sensor Networks, 2010, 8 (3/4): 147- 159. doi: 10.1504/IJSNET.2010.036190
22	CHEN G, CUI S. Relay node placement in two-tiered wireless sensor networks with base stations. Journal of Combinatorial Optimization, 2013, 26 (3): 499- 508. doi: 10.1007/s10878-012-9451-5
23	YOUNIS M, LEE S. Optimized relay node placement for federating wireless sensor sub-networks. Dissertations & Theses-Gradworks, 2010, 56 (12): 2788- 2804.
24	BHATTACHARYA A, RAO A, NAVEEN K P, et al. QoS constrained optimal sink and relay placement in planned wireless sensor networks. Proc. of the International Conference on Signal Processing and Communications, 2014, 1- 5.
25	NIKOLOV M, HAAS Z J. Relay placement in wireless networks: minimizing communication cost. IEEE Trans. on Wireless Communications, 2016, 15 (5): 3587- 3602. doi: 10.1109/TWC.2016.2523984
26	WANG H, HUO D, ALIDAEE B. Position unmanned aerial vehicles in the mobile ad hoc network. Journal of Intelligent & Robotic Systems, 2014, 74 (1/2): 455- 464.
27	GUTIERREZ J M L, PULIO J A G, RODRIGUEZ M A V, et al. A parallel evolutionary approach to solve the relay node placement problem in wireless sensor networks. Proc. of the Conference on Genetic & Evolutionary Computation, 2013, 1157- 1164.
28	GUTIERREZ J M L, PULIO J A G, RODRIGUEZ M A V. A trajectory algorithm to solve the relay node placement problem in wireless sensor networks. Proc. of the International Conference on Theory and Practice of Natural Computing, 2013, 145- 156.
29	BURDAKOV O, DOHERTY P, HOLMBERG K, et al. Optimal placement of UV-based communications relay nodes. Journal of Global Optimization, 2010, 48 (4): 511- 531. doi: 10.1007/s10898-010-9526-8
30	PEREZ A J, LABRADOR M A, WIGHTMAN P M. A multi-objective approach to the relay placement problem in WSNs. Proc. of the IEEE Wireless Communications and Networking Conference, 2011, 475- 179.
31	GUERIN R, ORDA A. Computing shortest paths for any number of hops. IEEE/ACM Trans. on Networking, 2002, 10 (5): 613- 620. doi: 10.1109/TNET.2002.803917
32	BURDAKOV O, DOHERTY P, HOLMBERG K, et al. Relay positioning for unmanned aerial vehicle surveillance. The International Journal of Robotics Research, 2010, 29 (8): 1069- 1687.
33	RUBIN I, ZHANG R. Placement of UAVs as communication relays aiding mobile ad hoc wireless networks. Proc. of the Military Communication Conference, 2007, 1- 7.
34	MOZAFFARI M, SAAD W, BENNIS M, et al. Mobile unmanned aerial vehicles (UAVs) for energy-efficient internet of things communications. IEEE Trans. on Wireless Communications, 2017, 16 (11): 7574- 7589. doi: 10.1109/TWC.2017.2751045
35	YOUNIS M, AKKAYA K. Strategies and technigues for node placement in wireless sensor networks: a survey. Ad Hoc Networks, 2008, 6 (4): 621- 655. doi: 10.1016/j.adhoc.2007.05.003
36	TANG J, HAO B, SEN A. Relaynode placement in large scale wireless sensor networks. Computer Communications, 2006, 29 (4): 490- 501. doi: 10.1016/j.comcom.2004.12.032
37	CHENG X, DU D Z, WANG L, et al. Relay sensor placement in wireless sensor networks. Wireless Networks, 2008, 14 (3): 347- 355. doi: 10.1007/s11276-006-0724-8
38	LIN G H, XUE G L. Steiner tree problem with minimum number of Steiner points and bounded edge length. Information Processing Letters, 1999, 69 (2): 53- 57. doi: 10.1016/S0020-0190(98)00201-4
39	LLOYD E L, XUE G L. Relay node placement in wireless sensor networks. IEEE Trans. on Computers, 2007, 56 (1): 134- 138. doi: 10.1109/TC.2007.250629
40	YANG D J, MISRA S, FANG X, et al. Two-tiered constrained relay node placement in wireless sensor networks: efficient approximations. Proc. of the 7th Annual IEEE Communication Society Conference on Sensor, Mesh and Ad Hoc Communication and Networks, 2010: 1-9.
41	MISRA S, HONG S D, XUE G L, et al. Constrained relay node placement in wireless sensor networks-formulation and approximations. IEEE/ACM Trans. on Networking, 2010, 18 (2): 434- 447. doi: 10.1109/TNET.2009.2033273
42	NIGAM A, AGARWAL Y K. Optimal relay node placement in delay constrained wireless sensor network design. European Journal of Operational Research, 2014, 233 (1): 220- 233.
43	AZHARUDDIN M, JANA P K. A GA-based approach for fault tolerant relay node placement in wireless sensor networks. Proc. of the Third International Conference on Computer, 2015, 1- 6.
44	HOU Y T, SHI Y, SHERALI H D, et al. On energy provisioning and relay node placement for wireless sensor networks. IEEE Trans. on Wireless Communications, 2005, 4 (5): 2579- 2590. doi: 10.1109/TWC.2005.853969
45	RICHARD M G. Cooperative control of distributed autonomous systems with applications to wireless sensor networks. California, America: Naval Postgraduate School, 2009.
46	YAB Y, MOSTOFI Y. Robotic router formation in realistic communication environments. IEEE Trans. on Robotics, 2012, 28 (4): 810- 827. doi: 10.1109/TRO.2012.2188163
47	DIXON C. Controlled mobility of unmanned aircraft chains to optimize network capacity in realistic communication environments. Colorado, America: University of Colorado, 2010.
48	LAWLER E L. Combinatorial optimization: networks and matroids. New York: Library of Congress Cataloging in Publication Data, 1976.
49	YANG D J, MISRA S, FANG X. Two-tiered constrained relay node placement in wireless sensor networks: computational complexity and efficient approximations. IEEE Trans. on Moible Computing, 2012, 11 (8): 1399- 1412. doi: 10.1109/TMC.2011.126
50	KAUFMAN L, ROUSSEEUW P J. Finding groups in data: an introduction to cluster analysis. New York: Wiley-Interscience Publication, 2009.
51	HARTIGAN J, WONG M. Algorithm AS 136: a k-means clustering algorithm. Journal of the Royal Statistical Society, Series C (Applied Statistics), 1979, 28 (1): 100- 108.
52	ANDREW N G. Supervised learning, discriminative algorithms. http://cs229.stanford.edu/syllabus.html.
53	SPALL J C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans. on Automation Control, 1992, 37 (3): 332- 341. doi: 10.1109/9.119632
54	RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks. Science, 2014, 344 (6191): 1492- 1496.

[1]	Guisheng WANG, Yequn WANG, Shufu DONG, Guoce HUANG. Multiple transformation analysis for interference separation in TDCS [J]. Journal of Systems Engineering and Electronics, 2022, 33(5): 1064-1078.
[2]	Honghong ZHANG, Xusheng GAN, Shuangfeng LI, Zhiyuan CHEN. UAV safe route planning based on PSO-BAS algorithm [J]. Journal of Systems Engineering and Electronics, 2022, 33(5): 1151-1160.
[3]	Yangjun GAO, Guangyun LI, Zhiwei LYU, Lundong ZHANG, Zhongpan LI. Improved adaptively robust estimation algorithm for GNSS spoofer considering continuous observation error [J]. Journal of Systems Engineering and Electronics, 2022, 33(5): 1237-1248.
[4]	Yuan ZENG, Wenbin LU, Bo YU, Shifei TAO, Haosu ZHOU, Yu CHEN. Improved IMM algorithm based on support vector regression for UAV tracking [J]. Journal of Systems Engineering and Electronics, 2022, 33(4): 867-876.
[5]	Hao FENG, Jianzhong WU, Lu ZHANG, Mingsheng LIAO. Unsupervised change detection of man-made objects using coherent and incoherent features of multi-temporal SAR images [J]. Journal of Systems Engineering and Electronics, 2022, 33(4): 896-906.
[6]	Jinfeng LYU, Fucai LIU, Yaxue REN. Fuzzy identification of nonlinear dynamic system based on selection of important input variables [J]. Journal of Systems Engineering and Electronics, 2022, 33(3): 737-747.
[7]	Dongju CAO, Wendong YANG, Hui CHEN, Yang WU, Xuanxuan TANG. Energy efficiency maximization for buffer-aided multi-UAV relaying communications [J]. Journal of Systems Engineering and Electronics, 2022, 33(2): 312-321.
[8]	Yangyang JIANG, Yan GAO, Wenqi SONG, Yue LI, Quan QUAN. Bibliometric analysis of UAV swarms [J]. Journal of Systems Engineering and Electronics, 2022, 33(2): 406-425.
[9]	Xiaohui LI, Cong FANG, Tao FAN. Analysis of reflected signal of quad rotor UAV based on model fitting in mobile communication system [J]. Journal of Systems Engineering and Electronics, 2022, 33(1): 97-104.
[10]	Jinqiang HU, Husheng WU, Renjun ZHAN, Rafik MENASSEL, Xuanwu ZHOU. Self-organized search-attack mission planning for UAV swarm based on wolf pack hunting behavior [J]. Journal of Systems Engineering and Electronics, 2021, 32(6): 1463-1476.
[11]	Ziquan YU, Youmin ZHANG, Bin JIANG. PID-type fault-tolerant prescribed performance control of fixed-wing UAV [J]. Journal of Systems Engineering and Electronics, 2021, 32(5): 1053-1061.
[12]	Juan Antonio VAZQUEZ TREJO, Adrien GUENARD, Manuel ADAM-MEDINA, Jean-Christophe PONSART, Laurent CIARLETTA, Damiano ROTONDO, Didier THEILLIOL. Event-triggered leader-following formation control for multi-agent systems under communication faults: application to a fleet of unmanned aerial vehicles [J]. Journal of Systems Engineering and Electronics, 2021, 32(5): 1014-1022.
[13]	Zhengjuan TIAN, Rui CHEN, Wenxuan LONG, Hong ZHOU, Marco MORETTI. Broadband beam steering for misaligned multi-mode OAM communication systems [J]. Journal of Systems Engineering and Electronics, 2021, 32(4): 779-788.
[14]	Tao YE, Zongyang ZHAO, Jun ZHANG, Xinghua CHAI, Fuqiang ZHOU. Low-altitude small-sized object detection using lightweight feature-enhanced convolutional neural network [J]. Journal of Systems Engineering and Electronics, 2021, 32(4): 841-853.
[15]	Zhongxiang CHANG, Zhongbao ZHOU, Feng YAO, Xiaolu LIU. Observation scheduling problem for AEOS with a comprehensive task clustering [J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 347-364.

Placement of unmanned aerial vehicles as communication relays in two-tiered multi-agent system: clustering based methods

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 12

References 54

Related Articles 15

Recommended Articles

Metrics

Comments