Journal of South China University of Technology(Natural Science) >
Time Sensitive Network Scheduling Method Based on Genetic Algorithm
Received date: 2023-02-02
Online published: 2023-06-20
Supported by
the National Key R&D Program of China(2020YFB1805300)
With the progress of network technology, applications such as vehicle networks, industrial Internet of Things and 5G ultra-reliable low-delay communication (uRLLC) all require TSN to ensure ultra-low delay deterministic data transmission. TSN traffic scheduling requires a fast and accurate scheduling algorithm. The existing accurate solution methods are of high complexity and cannot meet the real-time requirements in large-scale joint scheduling. This paper designed a routing optimization genetic algorithm (Routing-GA) with better performance. Combining routing and traffic scheduling constraints, it can improve the efficiency of scheduling algorithm by optimizing routing and provide services for link load balancing scheduling. This strategy increases the space and flexibility of scheduling, and has the characteristics of fast near-optimal solution of meta-heuristic algorithm. It can deal with large-scale TSN routing constraint joint scheduling problem simply and effectively. Routing-GA takes the minimum end-to-end delay of time-sensitive flow as the optimization objective, considers Routing and TSN constraints jointly, and provides a genetic algorithm coding method with low complexity, high efficiency and high scalability according to the characteristics of TSN transmission problems. In addition, in order to improve the performance of the scheduling algorithm, a crossover mutation mechanism was proposed to optimize the route length and link load balancing. The experimental results show that the realized Routing-GA can effectively reduce the end-to-end delay and significantly improve the solution quality. The evolution rate can reach 24.42%, and the average iteration time of traditional genetic algorithm (GA) is only 12%. It can effectively improve the performance of the algorithm and meet the constraint requirements of TSN scheduling.
LU Yiqin, HUANG Chenghai, CHEN Jiarui, et al . Time Sensitive Network Scheduling Method Based on Genetic Algorithm[J]. Journal of South China University of Technology(Natural Science), 2024 , 52(2) : 1 -12 . DOI: 10.12141/j.issn.1000-565X.230032
| 1 | IEEE 802.1 GroupWorking．Institute of electrical and electronics engineers，time-sensitive networking［EB/OL］．［2022-12-25］．. |
| 2 | 韩运实.装箱问题方法研究及其集成应用［D］．青岛：中国海洋大学，2004. |
| 3 | STEINER W ．An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks［C］∥Proceedings of the 2010 31st IEEE Real-Time Systems Symposium．San Diego，CA：IEEE，2010：375-384. |
| 4 | CRACIUNAS S S， OLIVER R S， CHMELíK M，et al ．Scheduling real-time communication in IEEE 802.1Qbv time sensitive networks［C］∥Proceedings of the International Conference on Real-time Networks & Systems．Brest：ACM，2016：183-192. |
| 5 | YU N， YAEGASHI R， NGUYEN A，et al ．Real-time reconfiguration of time-aware shaper for ULL transmission in dynamic conditions［J］．IEEE Access，2021，9：115246-115255. |
| 6 | PAHLEVAN H M， TABASSAM N， OBERMAISSER R ．Heuristic list scheduler for time triggered traffic in time sensitive networks［J］．ACM SIGBED Review，2019，16（1）：15-20. |
| 7 | PAHLEVAN H M， OBERMAISSER R ．Genetic algorithm for scheduling time-triggered traffic in time-sensitive net-works［C］∥Proceedings of the IEEE 23rd International Conference on Emerging Technologies and Factory Automation（ETFA）．Politecnico Torino，Torino：IEEE，2018：337-344. |
| 8 | DüRR F， NAYAK N G ．No-wait packet scheduling for IEEE time-sensitive networks （TSN） ［C］∥Proceedings of the 24th International Conference on Real-Time Networks and Systems．Brest：ACM，2016：203-212. |
| 9 | IEEE 802.1 GroupWorking．IEEE standard for local and metropolitan area networks-bridges and bridged networks-amendment 25：enhancements for scheduled traffic［EB/OL］．（2016-08-30）［2022-12-25］．. |
| 10 | YU Q H， WAN H， ZHAO X，et al ．Online scheduling for dynamic VM migration in multicast time-sensitive networks［J］．IEEE Transactions on Industrial Informatics，2020，16（6）：3778-3788. |
| 11 | ARESTOVA A， HIELSCHER K S J， GERMAN R ．Design of a hybrid genetic algorithm for time-sensitive networking［C］∥Proceedings of the 20th International GI/ITG Conference on Measurement，Modelling and Evaluation of Computing Systems． Saarbrucken：Springer，2020：99-117. |
| 12 | HEILMANN F， FOHLER G ．Size-based queuing：an approach to improve bandwidth utilization in TSN networks［J］．ACM SIGBED Review，2019，16（1）：9-14. |
| 13 | NASRALLAH A， BALASUBRAMANIAN V， THYAGATURU A，et al ．Reconfiguration algorithms for high precision communications in time sensitive networks ［C］∥Proceedings of the 2019 IEEE Globecom Workshops．Waikoloa，HI：IEEE，2019：1-6. |
| 14 | NASRALLAH A， THYAGATURU A S， ALHARBI Z，et al ．Performance comparison of IEEE 802.1 TSN time aware shaper （TAS） and asynchronous traffic shaper （ATS）［J］．IEEE Access，2019，7：44165-44181. |
| 15 | SAID S B H， TRUONG Q H，BOC M ．SDN-based configuration solution for IEEE 802.1 time sensitive net-working （TSN）［J］．ACM SIGBED Review，2019，16（1）：27-32. |
| 16 | VLK M， HANZALEK Z， BREJCHOVA K，et al ．Enhancing schedulability and throughput of time-triggered traffic in IEEE 802.1Qbv time-sensitive networks［J］．IEEE Transactions on Communications，2020，11：5-13. |
| 17 | ENNS R， BJ?RKLUND M， BIERMAN A，et al ．Network configuration protocol （NETCONF）［EB/OL］．（2011-06-01）［2023-01-15］．. |
| 18 | 高亮，张国辉，王晓娟 ．柔性作业车间调度智能算法及其应用［M］∥李培根．先进生产规划与调度理论研究．武汉：华中科技大学出版社，2012：70-163. |
/
| 〈 |
|
〉 |