【作者】 麻涵； 陈妍； 李红艳；

【Author】 MA Han;CHEN Yan;LI Hong-Yan;State Key Laboratory of Integrated Service Networks,Xidian University;Xi’an Research Institute of Navigation Technology;

【机构】 西安电子科技大学综合业务网理论及关键技术国家重点实验室； 西安导航技术研究所；

【摘要】 针对数据链网络时间确定性路由与调度这一NP-hard问题,提出了基于时变图的数据链网络时间确定性路由与调度算法,在保障算法性能的同时,大幅降低了问题的求解时间。首先,提出时变图模型,联合表征了数据链网络时变拓扑、时隙分配和任务的时延约束;在此基础上,提出了数据链网络时间确定性路由与调度算法,保障了任务的时间确定性,支持数据链网络按需规划。仿真结果表明,该算法相比于传统求解方法,算法运行速度提升了5倍。更多还原

【Abstract】 Aiming at the NP-hard problem of time-deterministic routing and scheduling in data link networks,this paper proposes a time-deterministic routing and scheduling algorithm based on time-varying graph,which not only ensures the performance of the algorithm,but also greatly reduces the solving time of the problem.Firstly,a time-varying graph model is proposed to jointly represent the time-varying topology of the data link network,time-slot allocation and task delay constraints.On this basis,a time deterministic routing and scheduling algorithm for data link networks is proposed to ensure the time deterministic task and support on-demand planning of data link networks.Simulation results show that the proposed algorithm is 5 times faster than the traditional algorithm.更多还原