Bidirectional Dijkstra algorithm whose time complexity is 8O(n~2) is proposed. The theory foundation is that the classical Dijkstra algorithm has not any directional feature during searching the shortest path. The alg...Bidirectional Dijkstra algorithm whose time complexity is 8O(n~2) is proposed. The theory foundation is that the classical Dijkstra algorithm has not any directional feature during searching the shortest path. The algorithm takes advantage of the adjacent link and the mechanism of bidirectional search, that is, the algorithm processes the positive search from start point to destination point and the negative search from destination point to start point at the same time. Finally, combining with the practical application of route-planning algorithm in embedded real-time vehicle navigation system (ERTVNS), one example of its practical applications is given, analysis in theory and the experimental results show that compared with the Dijkstra algorithm, the new algorithm can reduce time complexity, and guarantee the searching precision, it satisfies the needs of ERTVNS.展开更多
This study is trying to address the critical need for efficient routing in Mobile Ad Hoc Networks(MANETs)from dynamic topologies that pose great challenges because of the mobility of nodes.Themain objective was to del...This study is trying to address the critical need for efficient routing in Mobile Ad Hoc Networks(MANETs)from dynamic topologies that pose great challenges because of the mobility of nodes.Themain objective was to delve into and refine the application of the Dijkstra’s algorithm in this context,a method conventionally esteemed for its efficiency in static networks.Thus,this paper has carried out a comparative theoretical analysis with the Bellman-Ford algorithm,considering adaptation to the dynamic network conditions that are typical for MANETs.This paper has shown through detailed algorithmic analysis that Dijkstra’s algorithm,when adapted for dynamic updates,yields a very workable solution to the problem of real-time routing in MANETs.The results indicate that with these changes,Dijkstra’s algorithm performs much better computationally and 30%better in routing optimization than Bellman-Ford when working with configurations of sparse networks.The theoretical framework adapted,with the adaptation of the Dijkstra’s algorithm for dynamically changing network topologies,is novel in this work and quite different from any traditional application.The adaptation should offer more efficient routing and less computational overhead,most apt in the limited resource environment of MANETs.Thus,from these findings,one may derive a conclusion that the proposed version of Dijkstra’s algorithm is the best and most feasible choice of the routing protocol for MANETs given all pertinent key performance and resource consumption indicators and further that the proposed method offers a marked improvement over traditional methods.This paper,therefore,operationalizes the theoretical model into practical scenarios and also further research with empirical simulations to understand more about its operational effectiveness.展开更多
Rational planning of agricultural product transport route from initial node to destination node can effectively reduce the cost price of agricultural products,and the calculation of shortest path between any two point...Rational planning of agricultural product transport route from initial node to destination node can effectively reduce the cost price of agricultural products,and the calculation of shortest path between any two points also affects people’s daily travel.Taking Heze Railway Station to Heze College for example,with remote sensing image data as the base map,we conduct vectorization and topological analysis on roads in the target area.With Dijkstra as theoretical basis of shortest path algorithm,we use ArcG IS network analysis method to build road network,and calculate the planning program of the shortest distance path,the shortest path by driving and the shortest path by walking.展开更多
Network failures are unavoidable and occur frequently.When the network fails,intra-domain routing protocols deploying on the Internet need to undergo a long convergence process.During this period,a large number of mes...Network failures are unavoidable and occur frequently.When the network fails,intra-domain routing protocols deploying on the Internet need to undergo a long convergence process.During this period,a large number of messages are discarded,which results in a decline in the user experience and severely affects the quality of service of Internet Service Providers(ISP).Therefore,improving the availability of intra-domain routing is a trending research question to be solved.Industry usually employs routing protection algorithms to improve intra-domain routing availability.However,existing routing protection schemes compute as many backup paths as possible to reduce message loss due to network failures,which increases the cost of the network and impedes the methods deployed in practice.To address the issues,this study proposes an efficient routing protection algorithm based on optimized network topology(ERPBONT).ERPBONT adopts the optimized network topology to calculate a backup path with the minimum path coincidence degree with the shortest path for all source purposes.Firstly,the backup path with the minimum path coincidence with the shortest path is described as an integer programming problem.Then the simulated annealing algorithm ERPBONT is used to find the optimal solution.Finally,the algorithm is tested on the simulated topology and the real topology.The experimental results show that ERPBONT effectively reduces the path coincidence between the shortest path and the backup path,and significantly improves the routing availability.展开更多
Data center networks may comprise tens or hundreds of thousands of nodes,and,naturally,suffer from frequent software and hardware failures as well as link congestions.Packets are routed along the shortest paths with s...Data center networks may comprise tens or hundreds of thousands of nodes,and,naturally,suffer from frequent software and hardware failures as well as link congestions.Packets are routed along the shortest paths with sufficient resources to facilitate efficient network utilization and minimize delays.In such dynamic networks,links frequently fail or get congested,making the recalculation of the shortest paths a computationally intensive problem.Various routing protocols were proposed to overcome this problem by focusing on network utilization rather than speed.Surprisingly,the design of fast shortest-path algorithms for data centers was largely neglected,though they are universal components of routing protocols.Moreover,parallelization techniques were mostly deployed for random network topologies,and not for regular topologies that are often found in data centers.The aim of this paper is to improve scalability and reduce the time required for the shortest-path calculation in data center networks by parallelization on general-purpose hardware.We propose a novel algorithm that parallelizes edge relaxations as a faster and more scalable solution for popular data center topologies.展开更多
电力路由器融合了信息技术和电力电子变换技术,为分布式能源大范围地接入能源互联网提供了条件,但也给能源互联网的优化运行提出了新的要求。以图论为手段,以能源互联网的结构为基础构成单源点单汇点的电能路由拓扑;以Dijkstra为基础,...电力路由器融合了信息技术和电力电子变换技术,为分布式能源大范围地接入能源互联网提供了条件,但也给能源互联网的优化运行提出了新的要求。以图论为手段,以能源互联网的结构为基础构成单源点单汇点的电能路由拓扑;以Dijkstra为基础,节点仅根据其相邻节点的状态调节其自身状态,搜寻最短路径,完成电能路由,实现电能的分布式管理和协调控制,使系统运行在优化状态。多代理系统(multi-agent system,MAS)技术为实现分布式电能路由策略提供了技术支撑。最后,在Matlab/Simulink平台下搭建了分布式电网,结合基于JADE(Java Agent DEvelopment framework)平台的多代理系统对分布式电能路由策略进行仿真实现。展开更多
文摘Bidirectional Dijkstra algorithm whose time complexity is 8O(n~2) is proposed. The theory foundation is that the classical Dijkstra algorithm has not any directional feature during searching the shortest path. The algorithm takes advantage of the adjacent link and the mechanism of bidirectional search, that is, the algorithm processes the positive search from start point to destination point and the negative search from destination point to start point at the same time. Finally, combining with the practical application of route-planning algorithm in embedded real-time vehicle navigation system (ERTVNS), one example of its practical applications is given, analysis in theory and the experimental results show that compared with the Dijkstra algorithm, the new algorithm can reduce time complexity, and guarantee the searching precision, it satisfies the needs of ERTVNS.
基金supported by Northern Border University,Arar,Kingdom of Saudi Arabia,through the Project Number“NBU-FFR-2024-2248-03”.
文摘This study is trying to address the critical need for efficient routing in Mobile Ad Hoc Networks(MANETs)from dynamic topologies that pose great challenges because of the mobility of nodes.Themain objective was to delve into and refine the application of the Dijkstra’s algorithm in this context,a method conventionally esteemed for its efficiency in static networks.Thus,this paper has carried out a comparative theoretical analysis with the Bellman-Ford algorithm,considering adaptation to the dynamic network conditions that are typical for MANETs.This paper has shown through detailed algorithmic analysis that Dijkstra’s algorithm,when adapted for dynamic updates,yields a very workable solution to the problem of real-time routing in MANETs.The results indicate that with these changes,Dijkstra’s algorithm performs much better computationally and 30%better in routing optimization than Bellman-Ford when working with configurations of sparse networks.The theoretical framework adapted,with the adaptation of the Dijkstra’s algorithm for dynamically changing network topologies,is novel in this work and quite different from any traditional application.The adaptation should offer more efficient routing and less computational overhead,most apt in the limited resource environment of MANETs.Thus,from these findings,one may derive a conclusion that the proposed version of Dijkstra’s algorithm is the best and most feasible choice of the routing protocol for MANETs given all pertinent key performance and resource consumption indicators and further that the proposed method offers a marked improvement over traditional methods.This paper,therefore,operationalizes the theoretical model into practical scenarios and also further research with empirical simulations to understand more about its operational effectiveness.
基金Supported by Science Foundation of Heze University(XY14SK14)
文摘Rational planning of agricultural product transport route from initial node to destination node can effectively reduce the cost price of agricultural products,and the calculation of shortest path between any two points also affects people’s daily travel.Taking Heze Railway Station to Heze College for example,with remote sensing image data as the base map,we conduct vectorization and topological analysis on roads in the target area.With Dijkstra as theoretical basis of shortest path algorithm,we use ArcG IS network analysis method to build road network,and calculate the planning program of the shortest distance path,the shortest path by driving and the shortest path by walking.
基金This work is supported by the Hainan Provincial Natural Science Foundation of China(620RC562)the Natural Science Foundation of Shanxi Province(Grant Nos.20210302123444,20210302123455)+5 种基金the China University industry university research innovation fund(No.2021FNA02009)the Open Project Program of the Key Laboratory of Embedded System and Service Computing of Ministry of Education(Tongji University)ESSCKF 2021-04the National Natural Science Foundation of China(Grant Nos.61702315,61802092)the Applied Basic Research Plan of Shanxi Province(No.201901D211168)the Program of Hainan Association for Science and Technology Plans to Youth R&D Innovation(QCXM201910)the Key R&D Program(International Science and Technology Cooperation Project)of Shanxi Province China(No.201903D421003).
文摘Network failures are unavoidable and occur frequently.When the network fails,intra-domain routing protocols deploying on the Internet need to undergo a long convergence process.During this period,a large number of messages are discarded,which results in a decline in the user experience and severely affects the quality of service of Internet Service Providers(ISP).Therefore,improving the availability of intra-domain routing is a trending research question to be solved.Industry usually employs routing protection algorithms to improve intra-domain routing availability.However,existing routing protection schemes compute as many backup paths as possible to reduce message loss due to network failures,which increases the cost of the network and impedes the methods deployed in practice.To address the issues,this study proposes an efficient routing protection algorithm based on optimized network topology(ERPBONT).ERPBONT adopts the optimized network topology to calculate a backup path with the minimum path coincidence degree with the shortest path for all source purposes.Firstly,the backup path with the minimum path coincidence with the shortest path is described as an integer programming problem.Then the simulated annealing algorithm ERPBONT is used to find the optimal solution.Finally,the algorithm is tested on the simulated topology and the real topology.The experimental results show that ERPBONT effectively reduces the path coincidence between the shortest path and the backup path,and significantly improves the routing availability.
基金This work was supported by the Serbian Ministry of Science and Education(project TR-32022)by companies Telekom Srbija and Informatika.
文摘Data center networks may comprise tens or hundreds of thousands of nodes,and,naturally,suffer from frequent software and hardware failures as well as link congestions.Packets are routed along the shortest paths with sufficient resources to facilitate efficient network utilization and minimize delays.In such dynamic networks,links frequently fail or get congested,making the recalculation of the shortest paths a computationally intensive problem.Various routing protocols were proposed to overcome this problem by focusing on network utilization rather than speed.Surprisingly,the design of fast shortest-path algorithms for data centers was largely neglected,though they are universal components of routing protocols.Moreover,parallelization techniques were mostly deployed for random network topologies,and not for regular topologies that are often found in data centers.The aim of this paper is to improve scalability and reduce the time required for the shortest-path calculation in data center networks by parallelization on general-purpose hardware.We propose a novel algorithm that parallelizes edge relaxations as a faster and more scalable solution for popular data center topologies.
文摘电力路由器融合了信息技术和电力电子变换技术,为分布式能源大范围地接入能源互联网提供了条件,但也给能源互联网的优化运行提出了新的要求。以图论为手段,以能源互联网的结构为基础构成单源点单汇点的电能路由拓扑;以Dijkstra为基础,节点仅根据其相邻节点的状态调节其自身状态,搜寻最短路径,完成电能路由,实现电能的分布式管理和协调控制,使系统运行在优化状态。多代理系统(multi-agent system,MAS)技术为实现分布式电能路由策略提供了技术支撑。最后,在Matlab/Simulink平台下搭建了分布式电网,结合基于JADE(Java Agent DEvelopment framework)平台的多代理系统对分布式电能路由策略进行仿真实现。
