A blockchain bee colony double inhibition labor division algorithm for spatio-temporal coupling task with application to UAV swarm task allocation

doi:10.23919/JSEE.2021.000101

Journal of Systems Engineering and Electronics ›› 2021, Vol. 32 ›› Issue (5): 1180-1199.doi: 10.23919/JSEE.2021.000101

• SYSTEMS ENGINEERING • Previous Articles Next Articles

A blockchain bee colony double inhibition labor division algorithm for spatio-temporal coupling task with application to UAV swarm task allocation

Husheng WU¹(), Hao LI²(), Renbin XIAO^3,*()

¹ School of Equipment Management and Support, Armed Police Engineering University, Xi’an 710086, China
² Department of Intelligence, Air Force Early Warning Academy, Wuhan 430019, China
³ School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China

Received:2020-08-04 Online:2021-10-18 Published:2021-11-04
Contact: Renbin XIAO E-mail:wuhusheng0421@163.com;afeu_li@163.com;rbxiao@hust.edu.cn
About author:|WU Husheng was born in 1986. He received his B.S. degree in automobile command, M.E. degree in military equipment science from the Armed Police Engineering University (APEU) in 2008 and 2011, respectively, and Ph.D. degree in systems engineering from the Air Force Engineering University in 2014. He is currently an associate professor with the School of Equipment Management and Support, APEU. He is the author of more than three books and more than 30 journal papers. His research interests include swarm intelligence, unmanned system and its combat operation, and military intelligent equipment. E-mail: wuhusheng0421@163.com||LI Hao was born in 1981. He completed his Ph.D. degree in electronic science and technology from Air Force Engineering University in 2017. He published more than 30 journal papers as the major author, among which 20 articles were retrieved by SCI/EI. He hosted and participated in several National Natural Science Foundation projects. His current research interests are swarm intelligence, UAV swarm, intelligence systems, and signal processing. E-mail: afeu_li@163.com||XIAO Renbin was born in 1965. He received his B.S. degree in ship engineering, M.E. degree in ship hydrodynamics, and Ph.D. degree in systems engineering from Huazhong University of Science and Technology (HUST) in 1986, 1989, and 1993, respectively. He is currently a professor with the School of Artificial Intelligence and Automation, HUST. He is the author of more than 200 journal papers and the first author of six books. His research interests include swarm intelligence, emergent computation, intelligent design and innovative design of complex products.E-mail: rbxiao@hust.edu.cn
Supported by:
This work was supported by the National Natural Science and Technology Innovation 2030 Major Project of Ministry of Science and Technology of China (2018AAA0101200), the National Natural Science Foundation of China (61502522; 61502534), the Equipment Pre-Research Field Fund (JZX7Y20190253036101), the Equipment Pre-Research Ministry of Education Joint Fund (6141A02033703), Shaanxi Provincial Natural Science Foundation (2020JQ-493), the Military Science Project of the National Social Science Fund (WJ2019-SKJJ-C-092), and the Theoretical Research Foundation of Armed Police Engineering University (WJY202148).

Abstract

Abstract:

It is difficult for the double suppression division algorithm of bee colony to solve the spatio-temporal coupling or have higher dimensional attributes and undertake sudden tasks. Using the idea of clustering, after clustering tasks according to spatio-temporal attributes, the clustered groups are linked into task sub-chains according to similarity. Then, based on the correlation between clusters, the child chains are connected to form a task chain. Therefore, the limitation is solved that the task chain in the bee colony algorithm can only be connected according to one dimension. When a sudden task occurs, a method of inserting a small number of tasks into the original task chain and a task chain reconstruction method are designed according to the relative relationship between the number of sudden tasks and the number of remaining tasks. Through the above improvements, the algorithm can be used to process tasks with spatio-temporal coupling and burst tasks. In order to reflect the efficiency and applicability of the algorithm, a task allocation model for the unmanned aerial vehicle (UAV) group is constructed, and a one-to-one correspondence between the improved bee colony double suppression division algorithm and each attribute in the UAV group is proposed. Task assignment has been constructed. The study uses the self-adjusting characteristics of the bee colony to achieve task allocation. Simulation verification and algorithm comparison show that the algorithm has stronger planning advantages and algorithm performance.

Key words: bee colony double inhibition labor division algorithm, high dimensional attribute, sudden task, reforming the task chain, task allocation model

Husheng WU, Hao LI, Renbin XIAO. A blockchain bee colony double inhibition labor division algorithm for spatio-temporal coupling task with application to UAV swarm task allocation[J]. Journal of Systems Engineering and Electronics, 2021, 32(5): 1180-1199.

Figures/Tables 25

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Fig 9

Fig 10

Fig 11

Fig 12

Fig 13

Table 1

Fig 14

Fig 15

Table 2

Fig 16

Fig 17

Fig 18

Fig 19

Fig 20

Fig 21

Fig 22

Table 3

References 50

1	SHEN H, LIU G, CHANDLER H Swarm intelligence based file replication and consistency maintenance in structured P2P file sharing systems. IEEE Trans. on Computers, 2015, 64 (10): 2953- 2967. doi: 10.1109/TC.2015.2389845
2	GANDOMI A H, KASHANI A R Construction cost minimization of shallow foundation using recent swarm intelligence techniques. IEEE Trans. on Industrial Informatics, 2017, 14 (3): 1099- 1106.
3	WANG S Q, XING J C, JIANG Z Y, et al A decentralized swarm intelligence algorithm for global optimization of HVAC system. IEEE Access, 2019, 7, 64744- 64757. doi: 10.1109/ACCESS.2019.2913359
4	KANG Q, ZHOU M C, AN J, et al Swarm intelligence approaches to optimal power flow problem with distributed generator failures in power networks. IEEE Trans. on Automation Science and Engineering, 2012, 10 (2): 343- 353.
5	SLOWIK A, KWASNICKA H Nature inspired methods and their industry applications—swarm intelligence algorithms. IEEE Trans. on Industrial Informatics, 2017, 14 (3): 1004- 1015.
6	HU J Q, WU H S, ZHONG B, et al. Swarm intelligence-based optimization algorithms: an overview and future research issues. International Journal of Automation and Control, 2020, 14(5):656−693.
7	HU X M, ZHANG J, CHUNG H S H, et al SamACO: variable sampling ant colony optimization algorithm for continuous optimization. IEEE Trans. on Systems, Man and Cybernetics, Part B (Cybernetics), 2010, 40 (6): 1555- 1566. doi: 10.1109/TSMCB.2010.2043094
8	KENNEDY J, EBERHART R. Particle swarm optimization. Proc. of the IEEE International Conference on Neural Networks, 1995:1942−1948.
9	HUANG S J, LIU X Z, SU W F, et al Application of enhanced honey-bee mating optimization algorithm to fault section estimation in power systems. IEEE Trans. on Power Delivery, 2013, 28 (3): 1944- 1951. doi: 10.1109/TPWRD.2013.2264142
10	FENG Y, ZHAO S, LIU H Analysis of network coverage optimization based on feedback K-means clustering and artificial fish swarm algorithm. IEEE Access, 2020, 8, 42864- 42876. doi: 10.1109/ACCESS.2020.2970208
11	NAUG D From division of labor to collective behavior: behavioral analyses at different levels. Behavioral Ecology and Sociobiology, 2016, 70 (7): 1113- 1115. doi: 10.1007/s00265-016-2092-4
12	ROBINSON G E Regulation of division of labor in insect societies. Annual Review of Entomology, 1992, 37 (1): 637- 665. doi: 10.1146/annurev.en.37.010192.003225
13	XIAO R, WANG Y Labour division in swarm intelligence for allocation problems: a survey. International Journal of Bio-Inspired Computation, 2018, 12 (2): 71- 86. doi: 10.1504/IJBIC.2018.094186
14	GAO W F, HUANG L L, LIU S Y, et al Artificial bee colony algorithm based on information learning. IEEE Trans. on Systems, Man, and Cybernetics, 2015, 45 (12): 2827- 2839.
15	ZHANG Z S, LONG K P, WANG J P, et al On swarm intelligence inspired self-organized networking: its bionic mechanisms, designing principles and optimization approaches. IEEE Communications Surveys and Tutorials, 2013, 16 (1): 513- 537.
16	JIANG C B, CHEN T G, LI R L, et al Construction of extended ant colony labor division model for traffic signal timing and its application in mixed traffic flow model of single intersection. Concurrency and Computation: Practice and Experience, 2020, 32 (7): e5592.
17	WANG Y C, XIAO R B An ant colony based resilience approach to cascading failures in cluster supply network. Physica A: Statistical Mechanics and its Applications, 2016, 462, 150- 166. doi: 10.1016/j.physa.2016.06.058
18	RAVARY F, LECOUTEY E, KAMINSKI G, et al Individual experience alone can generate lasting division of labor in ants. Current Biology, 2007, 17 (15): 1308- 1312. doi: 10.1016/j.cub.2007.06.047
19	WU H S, LI H, XIAO R B, et al Modeling and simulation of dynamic ant colony’s labor division for task allocation of UAV swarm. Physica A: Statistical Mechanics and its Applications, 2018, 491, 127- 141. doi: 10.1016/j.physa.2017.08.094
20	HUANG L W, QU H, ZUO L Multi-type UAVs cooperative task allocation under resource constraints. IEEE Access, 2018, 6, 17841- 17850. doi: 10.1109/ACCESS.2018.2818733
21	CHEN Y B, YANG D, YU J Q Multi-UAV task assignment with parameter and time-sensitive uncertainties using modified two-part wolf pack search algorithm. IEEE Trans. on Aerospace and Electronic Systems, 2018, 54 (6): 2853- 2872. doi: 10.1109/TAES.2018.2831138
22	ZHU M N, DU X X, ZHANG X H, et al Multi-UAV rapid-assessment task-assignment problem in a post-earthquake scenario. IEEE Access, 2019, 7, 74542- 74557. doi: 10.1109/ACCESS.2019.2920736
23	ZHOU Z Y, FENG J H, GU B, et al When mobile crowd sensing meets UAV: energy-efficient task assignment and route planning. IEEE Trans. on Communications, 2018, 66 (11): 5526- 5538. doi: 10.1109/TCOMM.2018.2857461
24	MOTLAGH N H, BAGAA M, TALEB T Energy and delay aware task assignment mechanism for UAV-based IoT platform. IEEE Internet of Things Journal, 2019, 6 (4): 6523- 6536. doi: 10.1109/JIOT.2019.2907873
25	LIU D, WANG J, XU K, et al Task-driven relay assignment in distributed UAV communication networks. IEEE Trans. on Vehicular Technology, 2019, 68 (11): 11003- 11017. doi: 10.1109/TVT.2019.2942095
26	FU X W, FENG P, GAO X G Swarm UAVs task and resource dynamic assignment algorithm based on task sequence mechanism. IEEE Access, 2019, 7, 41090- 41100. doi: 10.1109/ACCESS.2019.2907544
27	DUAN X J, LIU H Y, TANG H, et al A novel hybrid auction algorithm for multi-UAVs dynamic task assignment. IEEE Access, 2019, 8, 86207- 86222.
28	CHENG L H, ZHONG L, TIAN S S, et al Task assignment algorithm for road patrol by multiple UAVs with multiple bases and rechargeable endurance. IEEE Access, 2019, 7, 144381- 144397. doi: 10.1109/ACCESS.2019.2944881
29	AMDAM G V, OMHOLT S W The hive bee to forager transition in honeybee colonies: the double repressor hypothesis. Journal of Theoretical Biology, 2003, 223 (4): 451- 464. doi: 10.1016/S0022-5193(03)00121-8
30	NAUG D, GADAGKAR R Flexible division of labor mediated by social interactions in an insect colony—a simulation model. Journal of Theoretical Biology, 1999, 197 (1): 123- 133. doi: 10.1006/jtbi.1998.0862
31	BESHERS S N, HUANG Z Y, OONO Y, et al. Social inhibition and the regulation of temporal polyethism in honey bees. Journal of Theoretical Biology, 2001, 213(3): 461−479.
32	ZAHADAT P, CRAVSCHEIM K, SCHMICK T, et al. Social inhibition managements division of labour in artificial swarm system. Proc. of the 12th European Concentration on Artificial Life, 2013: 609–616.
33	FU Z J, MAO Y H, HE D J, et al Secure multi-UAV collaborative task allocation. IEEE Access, 2019, 7, 35579- 35587. doi: 10.1109/ACCESS.2019.2902221
34	HU J W, JIANG M, ZHANG Q, et al Joint optimization of UAV position, time slot allocation, and computation task partition in multiuser aerial mobile-edge computing systems. IEEE Trans. on Vehicular Technology, 2019, 68 (7): 7231- 7235. doi: 10.1109/TVT.2019.2915836
35	ARAFAT M Y, MOH S Localization and clustering based on swarm intelligence in UAV networks for emergency communications. IEEE Internet of Things Journal, 2019, 6 (5): 8958- 8976. doi: 10.1109/JIOT.2019.2925567
36	KOUSHIK A M, HU F, KUMAR S Deep Q-learning-based node positioning for throughput-optimal communications in dynamic UAV swarm network. IEEE Trans. on Cognitive Communications and Networking, 2019, 5 (3): 554- 566. doi: 10.1109/TCCN.2019.2907520
37	MUKHERJEE A, MISRA S, CHANDRA V S P, et al Resource-optimized multiarmed bandit-based offload path selection in edge UAV swarms. IEEE Internet of Things Journal, 2019, 6 (3): 4889- 4896. doi: 10.1109/JIOT.2018.2879459
38	DONG X W, LI Y F, LU C, et al Time-varying formation tracking for UAV swarm systems with switching directed topologies. IEEE Trans. on Neural Networks, 2019, 30 (12): 3674- 3685. doi: 10.1109/TNNLS.2018.2873063
39	ISCOLD P, PEREIRA G A S, TORRES L A B Development of a hand-launched small UAV for ground reconnaissance. IEEE Trans. on Aerospace and Electronic Systems, 2010, 46 (1): 335- 348. doi: 10.1109/TAES.2010.5417166
40	BAZI Y, MELGANI F Convolutional SVM networks for object detection in UAV imagery. IEEE Trans. on Geoscience and Remote Sensing, 2018, 56 (6): 3107- 3118. doi: 10.1109/TGRS.2018.2790926
41	DONG C X, CHANG X A novel scattered wave deception jamming against three channel SAR GMTI. IEEE Access, 2018, 6, 53882- 53889. doi: 10.1109/ACCESS.2018.2871518
42	LIU H, YOO S J, KWAK K S Opportunistic relaying for low-altitude UAV swarm secure communications with multiple eavesdroppers. Journal of Communications and Networks, 2018, 20 (5): 496- 508. doi: 10.1109/JCN.2018.000074
43	SURESH M, GHOSE D UAV grouping and coordination tactics for ground attack missions. IEEE Trans. on Aerospace and Electronic Systems, 2012, 48 (1): 673- 692. doi: 10.1109/TAES.2012.6129663
44	LEE J H, KIM J W, SONG J Y, et al A novel memetic algorithm using modified particle swarm optimization and mesh adaptive direct search for PMSM design. IEEE Trans. on Magnetics, 2015, 52 (3): 1- 4.
45	LI J C, LI L A hybrid genetic algorithm based on information entropy and game theory. IEEE Access, 2020, 8, 36602- 36611. doi: 10.1109/ACCESS.2020.2971060
46	WANG L, ZHANG X, ZHANG X Antenna array design by artificial bee colony algorithm with similarity induced search method. IEEE Trans. on Magnetics, 2019, 55 (6): 1- 4.
47	MA Y N, GONG Y J, XIAO C F, et al Path planning for autonomous underwater vehicles: an ant colony algorithm incorporating alarm pheromone. IEEE Trans. on Vehicular Technology, 2019, 68 (1): 141- 154. doi: 10.1109/TVT.2018.2882130
48	CASTILLO-CAGIGAL M, MATALLANAS E, NAVARRO I, et al Variable threshold algorithm for division of labor analyzed as a dynamical system. IEEE Trans. on Systems, Man, and Cybernetics, 2014, 44 (12): 2242- 2252.
49	DU J An evolutionary game coordinated control approach to division of labor in multi-agent systems. IEEE Access, 2019, 7, 124295- 124308. doi: 10.1109/ACCESS.2019.2938254
50	YU X, CHEN W N, GU T, et al ACO-A: ant colony optimization plus A for 3-D traveling in environments with dense obstacles. IEEE Trans. on Evolutionary Computation, 2018, 23 (4): 617- 631.

Cost function	The algorithm of this paper	Bee colony labor division	Ant colony labor division	Algorithm in [48]	Algorithm in [49]	Algorithm in [50]
Min	77.3205	82.5620	83.3530	79.6902	79.3347	77.9551
Average	78.3763	82.9944	84.3801	80.0487	80.2851	79.0156
Variance	1.3537	1.6286	1.9977	1.4713	1.5642	1.1135
Time-consuming	0.5377	1.3499	1.6715	0.8864	0.8637	2.0991

Cost function	The algorithm of this paper	Bee colony labor division	Ant colony labor division	Algorithm in [48]	Algorithm in [49]	Algorithm in [49]
Min	42.8168	46.1087	46.0672	43.7242	43.3587	43.0057
Average	43.0036	46.3920	46.4903	44.3134	44.3390	43.3505
Variance	1.0816	2.5849	1.2977	0.9302	0.8053	1.2326
Time-consuming	0.3188	0.7873	0.8093	0.5305	0.5968	1.165 8

Cost function	The algorithm of this paper	Bee colony labor division	Ant colony labor division	Algorithm in [48]	Algorithm in [49]	Algorithm in [50]
Min	53.2255	57.4162	58.7066	53.6427	53.3404	53.3354
Average	53.9264	58.7420	59.4014	54.3888	54.4026	54.2643
Variance	1.7927	2.8647	3.3160	1.6347	1.6094	1.8479
Time-consuming	1.5545	2.1977	2.7015	2.0187	2.0679	4.257 3

A blockchain bee colony double inhibition labor division algorithm for spatio-temporal coupling task with application to UAV swarm task allocation

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 25

References 50

Related Articles 0

Recommended Articles

Metrics

Comments