A Task Scheduling Algorithm Based on Clustering Pre-processing in Space-Based Information Network

WANG Yufei; LIU Jun; ZHANG Shengnan; XU Sai; WANG Jingyi

doi:10.23919/cje.2022.00.114

Volume 33 Issue 1

Jan. 2024

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2024 > 33(1): 217-230

Yufei WANG, Jun LIU, Shengnan ZHANG, et al., “A Task Scheduling Algorithm Based on Clustering Pre-processing in Space-Based Information Network,” Chinese Journal of Electronics, vol. 33, no. 1, pp. 217–230, 2024 doi: 10.23919/cje.2022.00.114

Citation:

Yufei WANG, Jun LIU, Shengnan ZHANG, et al., “A Task Scheduling Algorithm Based on Clustering Pre-processing in Space-Based Information Network,” Chinese Journal of Electronics, vol. 33, no. 1, pp. 217–230, 2024 doi: 10.23919/cje.2022.00.114

Citation:

PDF( 3746 KB)

A Task Scheduling Algorithm Based on Clustering Pre-processing in Space-Based Information Network

doi: 10.23919/cje.2022.00.114

1.
School of Computer Science and Engineering, Northeastern University, Shenyang 110169, China

More Information

Author Bio:
Yufei WANG received the B.S. degree in communication engineering from Yanshan University, Qinhuangdao, China, in 2016, and the M.S. degree in electronic and communication engineering from Northeastern University, Shenyang, China, in 2020. He is currently a Ph.D. candidate in School of Computer Science and Engineering, Northeastern University, Shenyang, China. His current research interests include resource management and space information networks. (Email: yfwang@stumail.neu.edu.cn)

Jun LIU received the Ph.D. degree in communications and information systems from the Northeastern University. He is currently a Professor and Ph.D. Supervisor with Northeastern University. His research interests include space information networks, selforganizing networks, and information security.(Email: liujun@cse.neu.edu.cn)

Shengnan ZHANG received the B.S. degree in electronic information engineering from Dalian Nationalities University, Dalian, China, in 2018, and the M.S. degree in electronic and communication engineering from Northeastern University, Shenyang, China, in 2021. Her research direction includes space-based information network and resource scheduling. (Email: zsn112900@163.com)

Sai XU received the M.S. degree in computer software and theory from Northeastern University, Shenyang, China, in 2014. He is a Ph.D. candidate in computer technology with the School of Computer Science and Engineering, Northeastern University, Shenyang, China. His research interests include cloud computing and edge computing. (Email: xu_s@neusoft.com)

Jingyi WANG received the B.S. degree in communication engineering from Northeastern University, Shenyang, China, in 2021. She is an M.S. candidate in information and communication engineering with the school of Northeastern University, Shenyang, China. Her research interests include resource scheduling and space information network. (Email: wangjingyimmx@foxmail.com)
Corresponding author: Email: liujun@cse.neu.edu.cn
Received Date: 2022-05-03
Accepted Date: 2023-05-21

Available Online: 2023-07-07

Publish Date: 2024-01-05

Abstract

Abstract

With the diversification of space-based information network task requirements and the dramatic increase in demand, the efficient scheduling of various tasks in space-based information network becomes a new challenge. To address the problems of a limited number of resources and resource heterogeneity in the space-based information network, we propose a bilateral pre-processing model for tasks and resources in the scheduling pre-processing stage. We use an improved fuzzy clustering method to cluster tasks and resources and design coding rules and matching methods to match similar categories to improve the clustering effect. We propose a space-based information network task scheduling strategy based on an ant colony simulated annealing algorithm for the problems of high latency of space-based information network communication and high resource dynamics. The strategy can efficiently complete the task and resource matching and improve the task scheduling performance. The experimental results show that our proposed task scheduling strategy has less task execution time and higher resource utilization than other algorithms under the same experimental conditions. It has significantly improved scheduling performance.
- Space-based information network,
- Task scheduling,
- Resource clustering,
- Ant colony optimization,
- Simulated annealing

FullText(HTML)

References(45)

References

[1]	L. H. Chi, C. W. Lin, W. H. Lin, et al., “Research on development of space-ground integration information network,” in Proceedings of 2020 International Conference on Urban Engineering and Management Science (ICUEMS), Taiyuan, China, pp. 29–32, 2020.
[2]	M. Tropea, F. De Rango, and A. F. Santamaria, “Design of a two-stage scheduling scheme for dvb-S2/S2X satellite architecture,” IEEE Transactions on Broadcasting, vol. 67, no. 2, pp. 424–437, 2021. doi: 10.1109/TBC.2021.3051524
[3]	A. Y. Alhilal, T. Braud, and P. Hui, “A roadmap toward a unified space communication architecture,” IEEE Access, vol. 9, pp. 99633–99650, 2021. doi: 10.1109/ACCESS.2021.3094828
[4]	H. J. Pan, H. P. Yao, T. L. Mai, et al, “Scalable traffic control using programmable data planes in a space information network,” IEEE Network, vol. 35, no. 4, pp. 35–41, 2021. doi: 10.1109/MNET.011.2100027
[5]	H. T. Yang, W. Liu, H. Y. Li, et al, “Maximum flow routing strategy for space information network with service function constraints,” IEEE Transactions on Wireless Communications, vol. 21, no. 5, pp. 2909–2923, 2022. doi: 10.1109/TWC.2021.3116983
[6]	C. Q. Dai, C. Li, S. Fu, et al, “Dynamic scheduling for emergency tasks in space data relay network,” IEEE Transactions on Vehicular Technology, vol. 70, no. 1, pp. 795–807, 2021. doi: 10.1109/TVT.2020.3045140
[7]	K. P. Xue, T. De Cola, D. S. L. Wei, et al, “Guest editorial: Space information networks: Technological challenges, design issues, and solutions,” IEEE Network, vol. 35, no. 4, pp. 16–18, 2021. doi: 10.1109/MNET.2021.9520379
[8]	S. J. Ji, M. Sheng, D. Zhou, et al, “Flexible and distributed mobility management for integrated terrestrial-satellite networks: Challenges, architectures, and approaches,” IEEE Network, vol. 35, no. 4, pp. 73–81, 2021. doi: 10.1109/MNET.011.2100070
[9]	C. Q. Dai, S. P. Li, J. S. Wu, et al, “Distributed user association with grouping in satellite–terrestrial integrated networks,” IEEE Internet of Things Journal, vol. 9, no. 12, pp. 10244–10256, 2022. doi: 10.1109/JIOT.2021.3122939
[10]	H. J. Li, Y. Lu, F. H. Dong, et al, “Communications satellite multi-satellite multi-task scheduling,” Procedia Engineering, vol. 29, pp. 3143–3148, 2012. doi: 10.1016/j.proeng.2012.01.455
[11]	Y. S. Lin, H. L. Jiang, Y. L. Dong, et al, “Research of dynamic scheduling method for communication satellite resources based on genetic algorithm,” Radio Engineering, vol. 47, no. 6, pp. 20–23, 2017.
[12]	Y. He, H. Y. Zhang, and Z. Ren, “Research on GEO satellite communication resources-task analysis and modeling match,” Aerospace Control, vol. 32, no. 6, pp. 44–49,56, 2014. doi: 10.3969/j.issn.1006-3242.2014.06.010
[13]	J. Zhang and X. S. Yu, “Control and routing of satellite communication port in integrated space-ground networks,” Radio Communications Technology, vol. 43, no. 2, pp. 1–5, 2017. doi: 10.3969/j.issn.1003-3114.2017.02.01
[14]	Z. G. Liu, J. Zhu, J. M. Zhang, et al, “Routing algorithm design of satellite network architecture based on SDN and ICN,” International Journal of Satellite Communications and Networking, vol. 38, no. 1, pp. 1–15, 2020. doi: 10.1002/sat.1304
[15]	T. X. Li, H. C. Zhou, H. B. Luo, et al, “Service: A software defined framework for integrated space-terrestrial satellite communication,” IEEE Transactions on Mobile Computing, vol. 17, no. 3, pp. 703–716, 2018. doi: 10.1109/TMC.2017.2732343
[16]	X. L. Meng, L. D. Wu, J. Jiao, et al., “Research on resource allocation method of the sin based on SDN,” in Proceedings of 2019 IEEE International Geoscience and Remote Sensing Symposium, Yokohama, Japan, pp. 10071–10074, 2019.
[17]	P. Qin, H. J. Liu, X. N. Zhao, et al., “Software-defined space-based integration network architecture,” in International Conference in Communications, Signal Processing, and Systems, Dalian, China, pp. 449–458, 2020.
[18]	Z. Q. Wang, B. J. Cui, S. Yao, et al., “An SDN-based dynamic security architecture for space information networks,” in 4th International Conference on Space Information Network, Wuzhen, China, pp. 99–111, 2019.
[19]	R. Wang, X. D. Han, N. Xu, et al., “Resource scheduling and cooperative management of space information networks,” in Third International Conference on Space Information Network, Changchun, China, pp. 146–151, 2019.
[20]	Z. C. Qu, G. X. Zhang, T. Hong, et al, “Architecture and network model of time-space uninterrupted space information network,” IEEE Access, vol. 7, pp. 27677–27688, 2019. doi: 10.1109/ACCESS.2019.2902134
[21]	Y. Y. Zhang, Y. C. Shi, Y. H. Pang, et al., “Research on path selection for space network based on fuzzy neural network,” in Proceedings of 2019 11th International Conference on Wireless Communications and Signal Processing (WCSP), Xi’an, China, pp. 1–6, 2019.
[22]	M. Sheng, D. Zhou, R. Z. Liu, et al, “Resource mobility in space information networks: Opportunities, challenges, and approaches,” IEEE Network, vol. 33, no. 1, pp. 128–135, 2019. doi: 10.1109/MNET.2018.1700244
[23]	S. C. Cheng, Y. Gao, X. Y. Li, et al., “Blockchain application in space information network security,” in Third International Conference on Space Information Network, Changchun, China, pp. 3–9, 2019.
[24]	Y. Zhang, B. Wang, B. L. Guo, et al, “A research on integrated space-ground information network simulation platform based on SDN,” Computer Networks, vol. 188, pp. 107821, 2021. doi: 10.1016/j.comnet.2021.107821
[25]	X. N. Niu, H. Tang, and L. X. Wu, “Satellite scheduling of large areal tasks for rapid response to natural disaster using a multi-objective genetic algorithm,” International Journal of Disaster Risk Reduction, vol. 28, pp. 813–825, 2018. doi: 10.1016/j.ijdrr.2018.02.013
[26]	J. F. Cordeau and G. Laporte, “Maximizing the value of an earth observation satellite orbit,” Journal of the Operational Research Society, vol. 56, no. 8, pp. 962–968, 2005. doi: 10.1057/palgrave.jors.2601926
[27]	J. Berger, N. Lo, and M. Barkaoui, “Quest–a new quadratic decision model for the multi-satellite scheduling problem,” Computers & Operations Research, vol. 115, pp. 104822, 2020. doi: 10.1016/j.cor.2019.104822
[28]	D. Habet, M. Vasquez, and Y. Vimont, “Bounding the optimum for the problem of scheduling the photographs of an agile earth observing satellite,” Computational Optimization and Applications, vol. 47, no. 2, pp. 307–333, 2010. doi: 10.1007/s10589-008-9220-7
[29]	K. Sun, Z. Y. Yang, P. Wang, et al, “Mission planning and action planning for agile earth-observing satellite with genetic algorithm,” Journal of Harbin Institute of Technology, vol. 20, no. 5, pp. 51–56, 2013. doi: 10.3969/j.issn.1005-9113.2013.05.010
[30]	Z. Yuan, Y. W. Chen, and R. J. He, “Agile earth observing satellites mission planning using genetic algorithm based on high quality initial solutions,” in Proceedings of 2014 IEEE Congress on Evolutionary Computation (CEC), Beijing, China, pp. 603–609, 2014.
[31]	Y. Q. Li, R. X. Wang, and M. Q. Xu, “Rescheduling of observing spacecraft using fuzzy neural network and ant colony algorithm,” Chinese Journal of Aeronautics, vol. 27, no. 3, pp. 678–687, 2014. doi: 10.1016/j.cja.2014.04.027
[32]	Y. Q. Li, R. X. Wang, Y. Liu, et al, “Satellite range scheduling with the priority constraint: An improved genetic algorithm using a station ID encoding method,” Chinese Journal of Aeronautics, vol. 28, no. 3, pp. 789–803, 2015. doi: 10.1016/j.cja.2015.04.012
[33]	M. S. Huang, S. Y. Chen, Y. Zhu, et al, “Topology control for time-evolving and predictable delay-tolerant networks,” IEEE Transactions on Computers, vol. 62, no. 11, pp. 2308–2321, 2013. doi: 10.1109/TC.2012.220
[34]	F. Sun, L. Gui, and H. P. Chen, “Task flow based spatial information network resource scheduling,” in Second International Conference on Space Information Network, Yinchuan, China, pp. 249–258, 2018.
[35]	J. J. He, “Improvement of efficient scheduling algorithm for network massive resources,” in Proceedings of 2018 International Conference on Virtual Reality and Intelligent Systems (ICVRIS), Hunan, China, pp. 528–531, 2018.
[36]	X. L. Meng, L. D. Wu, and S. B. Yu, “Research on resource allocation method of space information networks based on deep reinforcement learning,” Remote Sensing, vol. 11, no. 4, pp. 448, 2019. doi: 10.3390/rs11040448
[37]	S. M. Wan, P. Yang, M. Zhuo, et al., “An improved space information networks topology algorithm,” in Proceedings of 2021 IEEE International Conference on Information Communication and Software Engineering (ICICSE), Chengdu, China, pp. 227–232, 2021.
[38]	M. Chen, J. Wen, Y. J. Song, et al, “A population perturbation and elimination strategy based genetic algorithm for multi-satellite TT&C scheduling problem,” Swarm and Evolutionary Computation, vol. 65, pp. 100912, 2021. doi: 10.1016/j.swevo.2021.100912
[39]	Z. Y. Jia, M. Sheng, J. D. Li, et al, “Joint hap access and LEO satellite backhaul in 6G: Matching game-based approaches,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 4, pp. 1147–1159, 2021. doi: 10.1109/JSAC.2020.3018824
[40]	F. Wang, D. D. Jiang, S. Qi, et al. “A dynamic resource scheduling scheme in edge computing satellite networks,” Mobile Networks and Applications , vol. 26, no. 2, pp. 597–608, 2021.
[41]	M. Naghibzadeh, H. Taheri, and P. Neamatollahi, “Fuzzy-based clustering solution for hot spot problem in wireless sensor networks,” in Proceedings of 7’th International Symposium on Telecommunications (IST’2014), Tehran, Iran, pp. 729–734, 2014.
[42]	Z. J. Zhang, F. N. Hu, and N. Zhang, “Ant colony algorithm for satellite control resource scheduling problem,” Applied Intelligence, vol. 48, no. 10, pp. 3295–3305, 2018. doi: 10.1007/s10489-018-1144-z
[43]	H. K. Chen, X. Zhang, L. Wang, et al, “Resource-constrained self-organized optimization for near-real-time offloading satellite earth observation big data,” Knowledge-Based Systems, vol. 253, pp. 109496, 2022. doi: 10.1016/j.knosys.2022.109496
[44]	N. Sharma, S. Tyagi, and S. Atri, “A comparative analysis of min-min and max-min algorithms based on the makespan parameter,” International Journal of Advanced Research in Computer Science, vol. 8, no. 3, pp. 1038–1041, 2017. doi: 10.26483/IJARCS.V8I3.3151
[45]	S. Lu, F. Zheng, W. Si, et al., “Computation resource allocation based on particle swarm optimization for LEO satellite networks,” in Proceedings of the 9th International Conference on Computer Engineering and Networks, Changsha, China, pp. 955–962, 2021.