The shortest path planning issure is critical for dynamic traffic assignment and route guidance in intelligent transportation systems. In this paper, a Particle Swarm Optimization (PSO) algorithm with priority-based e...The shortest path planning issure is critical for dynamic traffic assignment and route guidance in intelligent transportation systems. In this paper, a Particle Swarm Optimization (PSO) algorithm with priority-based encoding scheme based on fluid neural network (FNN) to search for the shortest path in stochastic traffic networks is introduced. The proposed algorithm overcomes the weight coefficient symmetry restrictions of the traditional FNN and disadvantage of easily getting into a local optimum for PSO. Simulation experiments have been carried out on different traffic network topologies consisting of 15-65 nodes and the results showed that the proposed approach can find the optimal path and closer sub-optimal paths with good success ratio. At the same time, the algorithms greatly improve the convergence efficiency of fluid neuron network.展开更多
“Minimizing path delay” is one of the challenges in low Earth orbit (LEO) satellite network routing algo-rithms. Many authors focus on propagation delays with the distance vector but ignore the status information an...“Minimizing path delay” is one of the challenges in low Earth orbit (LEO) satellite network routing algo-rithms. Many authors focus on propagation delays with the distance vector but ignore the status information and processing delays of inter-satellite links. For this purpose, a new discrete-time traffic and topology adap-tive routing (DT-TTAR) algorithm is proposed in this paper. This routing algorithm incorporates both inher-ent dynamics of network topology and variations of traffic load in inter-satellite links. The next hop decision is made by the adaptive link cost metric, depending on arrival rates, time slots and locations of source-destination pairs. Through comprehensive analysis, we derive computation formulas of the main per-formance indexes. Meanwhile, the performances are evaluated through a set of simulations, and compared with other static and adaptive routing mechanisms as a reference. The results show that the proposed DT-TTAR algorithm has better performance of end-to-end delay than other algorithms, especially in high traffic areas.展开更多
Due to the diversified demands of quality of service(QoS) in volume multimedia application, QoS routings for multiservice are becoming a research hotspot in low earth orbit(LEO) satellite networks. A novel QoS sat...Due to the diversified demands of quality of service(QoS) in volume multimedia application, QoS routings for multiservice are becoming a research hotspot in low earth orbit(LEO) satellite networks. A novel QoS satellite routing algorithm for multi-class traffic is proposed. The goal of the routing algorithm is to provide the distinct QoS for different traffic classes and improve the utilization of network resources. Traffic is classified into three classes and allocated priorities based on their QoS requirements, respectively. A priority queuing mechanism guarantees the algorithm to work better for high-priority classes. In order to control the congestion, a blocking probability analysis model is built up based on the Markov process theory. Finally, according to the classification link-cost metrics, routings for different classes are calculated with the distinct QoS requirments and the status of network resource. Simulations verify the performance of the routing algorithm at different time and in different regions, and results demonstrate that the algorithm has great advantages in terms of the average delay and the blocking probability. Meanwhile, the robustness issue is also discussed.展开更多
Human beings’ intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms.It is detailed in this paper how to utilize the hierarchical reasonin...Human beings’ intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms.It is detailed in this paper how to utilize the hierarchical reasoning on the basis of greedy and directional strategy to establish a spatial heuristic,so as to improve running efficiency and suitability of shortest path algorithm for traffic network.The authors divide urban traffic network into three hierarchies and set forward a new node hierarchy division rule to avoid the unreliable solution of shortest path.It is argued that the shortest path,no matter distance shortest or time shortest,is usually not the favorite of drivers in practice.Some factors difficult to expect or quantify influence the drivers’ choice greatly.It makes the drivers prefer choosing a less shortest,but more reliable or flexible path to travel on.The presented optimum path algorithm,in addition to the improvement of the running efficiency of shortest path algorithms up to several times,reduces the emergence of those factors,conforms to the intellection characteristic of human beings,and is more easily accepted by drivers.Moreover,it does not require the completeness of networks in the lowest hierarchy and the applicability and fault tolerance of the algorithm have improved.The experiment result shows the advantages of the presented algorithm.The authors argued that the algorithm has great potential application for navigation systems of large_scale traffic networks.展开更多
Research on brain function after brachial plexus injury focuses on local cortical functional reorganization,and few studies have focused on brain networks after brachial plexus injury.Changes in brain networks may hel...Research on brain function after brachial plexus injury focuses on local cortical functional reorganization,and few studies have focused on brain networks after brachial plexus injury.Changes in brain networks may help understanding of brain plasticity at the global level.We hypothesized that topology of the global cerebral resting-state functional network changes after unilateral brachial plexus injury.Thus,in this cross-sectional study,we recruited eight male patients with unilateral brachial plexus injury(right handedness,mean age of 27.9±5.4years old)and eight male healthy controls(right handedness,mean age of 28.6±3.2).After acquiring and preprocessing resting-state magnetic resonance imaging data,the cerebrum was divided into 90 regions and Pearson’s correlation coefficient calculated between regions.These correlation matrices were then converted into a binary matrix with affixed sparsity values of 0.1–0.46.Under sparsity conditions,both groups satisfied this small-world property.The clustering coefficient was markedly lower,while average shortest path remarkably higher in patients compared with healthy controls.These findings confirm that cerebral functional networks in patients still show smallworld characteristics,which are highly effective in information transmission in the brain,as well as normal controls.Alternatively,varied small-worldness suggests that capacity of information transmission and integration in different brain regions in brachial plexus injury patients is damaged.展开更多
In order to form an algorithm for distribution network routing,an automatic routing method of distribution network planning was proposed based on the shortest path.The problem of automatic routing was divided into two...In order to form an algorithm for distribution network routing,an automatic routing method of distribution network planning was proposed based on the shortest path.The problem of automatic routing was divided into two steps in the method:the first step was that the shortest paths along streets between substation and load points were found by the basic ant colony algorithm to form a preliminary radial distribution network,and the second step was that the result of the shortest path was used to initialize pheromone concentration and pheromone updating rules to generate globally optimal distribution network.Cases studies show that the proposed method is effective and can meet the planning requirements.It is verified that the proposed method has better solution and utility than planning method based on the ant colony algorithm.展开更多
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.展开更多
A “Random Shortest Path”traffic assignment model and its algorithm arepresented by simulating the trip-makers’route-choice characters,and the dynamic meth-od is introduced in the assignment model.It is a ideal mult...A “Random Shortest Path”traffic assignment model and its algorithm arepresented by simulating the trip-makers’route-choice characters,and the dynamic meth-od is introduced in the assignment model.It is a ideal multiple path assignment modelwhich can be carried out by the dynamic method and static method,can better reflect boththe shortest path factor and the random factor in the route-choice,and is of reasonableassignment volumes.Besides,both dynamic and static softwares particularly suited to thetraffic assignment of large and medium-sized transportation networks arc developed.展开更多
Based on their "Theorem 2", an O(δ)-time algorithm of searching for the shortest path between each pair of nodes in a double loop network was proposed by K.Mukhopadyaya, et al.(1995). While, unfortunately, ...Based on their "Theorem 2", an O(δ)-time algorithm of searching for the shortest path between each pair of nodes in a double loop network was proposed by K.Mukhopadyaya, et al.(1995). While, unfortunately, it will be proved that both "Theorem 2" and its proof are in error. A new and more faster O(△)-time, △≤δ, algorithm will be presented in this paper.展开更多
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.展开更多
Routing, modulation and spectrum allocation in elastic optical networks is a problem aiming at increasing the capacity of the network. Many algorithms such as shortest path algorithm can be used as the routing section...Routing, modulation and spectrum allocation in elastic optical networks is a problem aiming at increasing the capacity of the network. Many algorithms such as shortest path algorithm can be used as the routing section of this problem. The efficiency of these algorithms is partly based on how the cost of each link is defined. In this study, we considered several basic metrics in cost of network links and compared their effects on the network capacity. In particular, the static costs and the dynamic costs were evaluated and compared. For dynamic scenarios, compared to static scenarios, at least one additional factor, the usage of the links, was added. We further considered a new factor that is based on probability of accommodating the signal at a given time in any given link. The results show that, among them, the shortest path algorithm provides the least blocking probability when the cost is a combination of link length and the abovementioned possibility/usage of the link.展开更多
针对目前传统机动通信系统、主流软件定义网络(software defined network,SDN)的拓扑发现方法不适合基于分布式SDN的机动通信系统这一问题,遵循OpenFlow拓扑发现算法(OpenFlow discovery protocol,OFDP)移植传输控制协议/网际协议(trans...针对目前传统机动通信系统、主流软件定义网络(software defined network,SDN)的拓扑发现方法不适合基于分布式SDN的机动通信系统这一问题,遵循OpenFlow拓扑发现算法(OpenFlow discovery protocol,OFDP)移植传输控制协议/网际协议(transmission control protocol/Internet protocol,TCP/IP)相关协议到SDN网络的研究思路,对开放最短路径优先(open shortest path first,OSPF)协议进行优化,精简协议状态机、优化协议报文、增加协议功能并设计拓扑发现算法,提出一种适合基于分布式SDN的机动通信系统的拓扑发现方法,并搭建仿真实验平台进行验证。实验结果表明,优化后OSPF协议适应于分布式SDN网络,网络拓扑建链时间降低80%且重新收敛时间显著降低,建链开销平均每秒接收字节数、发送字节数分别下降了31.7%和21.5%,维持开销平均每秒收发字节数降低了45%,增加了收集信道种类等网络信息的新功能。展开更多
Based on the model of the same degree of all nodes we proposed before, a new algorithm, the so-called “spread all over vertices” (SAV) algorithm, is proposed for generating small-world properties from a regular ri...Based on the model of the same degree of all nodes we proposed before, a new algorithm, the so-called “spread all over vertices” (SAV) algorithm, is proposed for generating small-world properties from a regular ring lattices. During randomly rewiring connections the SAV is used to keep the unchanged number of links. Comparing the SAV algorithm with the Watts-Strogatz model and the “spread all over boundaries” algorithm, three methods can have the same topological properties of the small world networks. These results offer diverse formation of small world networks. It is helpful to the research of some applications for dynamics of mutual oscillator inside nodes and interacting automata associated with networks.展开更多
In order to evaluate the practicality and effectiveness of the turn-based algorithm for logit loading (TALL), the TALL is implemented using C++, and it is compared with a combination of the network-expanding metho...In order to evaluate the practicality and effectiveness of the turn-based algorithm for logit loading (TALL), the TALL is implemented using C++, and it is compared with a combination of the network-expanding method and the Dial algorithm based on the analysis of algorithm procedures. The TALL uses the arc-labeling shortest path searching, bidirectional star and the deque structure to directly assign the traffic flow, while the Dial algorithm should be used in an expanded network. The test results over realistic networks of eight cities show the superior performance of the TALL algorithm over the combination of the network-expanding method and the Dial algorithm, and the average processing time is reduced by 55. 4%. Furthermore, it is found that the operational efficiency of the TALL relates to the original densities of the cities. The average processing time is reduced by 65. 1% when the original density is about 14%, but the advantage of the TALL is not obvious with the increase in the original density.展开更多
Consideration of the travel time variation for rescue vehicles is significant in the field of emergency management research.Because of uncertain factors,such as the weather or OD(origin-destination)variations caused b...Consideration of the travel time variation for rescue vehicles is significant in the field of emergency management research.Because of uncertain factors,such as the weather or OD(origin-destination)variations caused by traffic accidents,travel time is a random variable.In emergency situations,it is particularly necessary to determine the optimal reliable route of rescue vehicles from the perspective of uncertainty.This paper first proposes an optimal reliable path finding(ORPF)model for rescue vehicles,which considers the uncertainties of travel time,and link correlations.On this basis,it investigates how to optimize rescue vehicle allocation to minimize rescue time,taking into account travel time reliability under uncertain conditions.Because of the non-additive property of the objective function,this paper adopts a heuristic algorithm based on the K-shortest path algorithm,and inequality techniques to tackle the proposed modified integer programming model.Finally,the numerical experiments are presented to verify the accuracy and effectiveness of the proposed model and algorithm.The results show that ignoring travel time reliability may lead to an over-or under-estimation of the effective travel time of rescue vehicles on a particular path,and thereby an incorrect allocation scheme.展开更多
We put forward an optimal disk schedule with n disk requests and prove its optimality mathematically.Generalizing the idea of an optimal disk schedule, we remove the limit of n requests and, at the same time, consider...We put forward an optimal disk schedule with n disk requests and prove its optimality mathematically.Generalizing the idea of an optimal disk schedule, we remove the limit of n requests and, at the same time, consider the dynamically arrival model of disk requests to obtain an algorithm, shortest path first-fit first (SPFF). This algorithm is based on the shortest path of disk head motion constructed by all the pendent requests. From view of the head moving distance, it has the stronger glohality than SSTF. From view of the head-moving direction, it has the better flexibility than SCAN. Therefore, SPFF keeps the advantage of SCAN and, at the same time, absorbs the strength of SSTF. The algorithm SPFF not only shows the more superiority than other scheduling polices, but also have higher adjustability to meet the computer system's different demands.展开更多
ISA100.11 a industrial wireless network standard is based on a deterministic scheduling mechanism.For the timeslot delay caused by deterministic scheduling,a routing algorithm is presented for industrial environments....ISA100.11 a industrial wireless network standard is based on a deterministic scheduling mechanism.For the timeslot delay caused by deterministic scheduling,a routing algorithm is presented for industrial environments.According to timeslot,superframe,links,channel and data retransmission of deterministic scheduling mechanisms that affect the design of the routing algorithm,the algorithm selects the link quality,timeslot delay and retransmission delay as the routing criteria and finds the optimum communication path by k shortest paths algorithm.Theoretical analysis and experimental verification show that the optimal paths selected by the algorithm not only have high link quality and low retransmission delay,but also meet the requirements of the deterministic scheduling.The algorithm can effectively solve the problem of packet loss and transmission delay during data transmission,and provide a valuable solution for efficient data transmission based on determinacy.展开更多
软件定义网络(Software Defined Network,SDN)以其强大的可编程性和集中控制的优势得到了学术界的广泛关注。现有的SDN设备在执行报文转发时仍然使用最短路径协议,当最短路径中的结点发生故障时,网络仍然需要重新收敛,在此期间报文可能...软件定义网络(Software Defined Network,SDN)以其强大的可编程性和集中控制的优势得到了学术界的广泛关注。现有的SDN设备在执行报文转发时仍然使用最短路径协议,当最短路径中的结点发生故障时,网络仍然需要重新收敛,在此期间报文可能会被丢弃,进而无法传递至目的结点,给实时性应用的流畅性造成了冲击,影响用户体验。学术界普遍采用路由保护的方案来应对网络故障,现有的路由保护方案存在以下两个方面的问题:(1)故障保护率低;(2)当网络出现故障时,备份路径可能会出现路由环路。为了解决上述两个问题,首先提出了备份下一跳计算规则;然后基于此规则设计了一种软件定义网络下的高故障保护率的路由保护算法(Routing Protection Algorithm with High Failure Protection Ratio,RPAHFPR),该算法融合了路径生成算法(Path Generation Algorithm,PGA)、旁支优先算法(Side Branch First Algorithm,SBF)和环路规避算法(Loop Avoidance Algorithm,LAA),可以同时解决已有路由保护方法面临的故障保护率低和路由环路问题;最后在大量的真实网络拓扑和模拟网络拓扑中验证了RPAHFPR方案的性能。与经典的NPC和U-TURN相比,RPAHFPR的故障保护率分别提高了20.85%和11.88%,并且在86.3%的拓扑中可以达到100%的故障保护率,在所有拓扑中可以达到99%以上的故障保护率。RPAHFPR的路径拉伸度基本接近1,不会引入过多的时间延迟。展开更多
文摘The shortest path planning issure is critical for dynamic traffic assignment and route guidance in intelligent transportation systems. In this paper, a Particle Swarm Optimization (PSO) algorithm with priority-based encoding scheme based on fluid neural network (FNN) to search for the shortest path in stochastic traffic networks is introduced. The proposed algorithm overcomes the weight coefficient symmetry restrictions of the traditional FNN and disadvantage of easily getting into a local optimum for PSO. Simulation experiments have been carried out on different traffic network topologies consisting of 15-65 nodes and the results showed that the proposed approach can find the optimal path and closer sub-optimal paths with good success ratio. At the same time, the algorithms greatly improve the convergence efficiency of fluid neuron network.
文摘“Minimizing path delay” is one of the challenges in low Earth orbit (LEO) satellite network routing algo-rithms. Many authors focus on propagation delays with the distance vector but ignore the status information and processing delays of inter-satellite links. For this purpose, a new discrete-time traffic and topology adap-tive routing (DT-TTAR) algorithm is proposed in this paper. This routing algorithm incorporates both inher-ent dynamics of network topology and variations of traffic load in inter-satellite links. The next hop decision is made by the adaptive link cost metric, depending on arrival rates, time slots and locations of source-destination pairs. Through comprehensive analysis, we derive computation formulas of the main per-formance indexes. Meanwhile, the performances are evaluated through a set of simulations, and compared with other static and adaptive routing mechanisms as a reference. The results show that the proposed DT-TTAR algorithm has better performance of end-to-end delay than other algorithms, especially in high traffic areas.
基金Supported by the National High Technology Research and Development Program of China(″863″Program)(2010AAxxx404)~~
文摘Due to the diversified demands of quality of service(QoS) in volume multimedia application, QoS routings for multiservice are becoming a research hotspot in low earth orbit(LEO) satellite networks. A novel QoS satellite routing algorithm for multi-class traffic is proposed. The goal of the routing algorithm is to provide the distinct QoS for different traffic classes and improve the utilization of network resources. Traffic is classified into three classes and allocated priorities based on their QoS requirements, respectively. A priority queuing mechanism guarantees the algorithm to work better for high-priority classes. In order to control the congestion, a blocking probability analysis model is built up based on the Markov process theory. Finally, according to the classification link-cost metrics, routings for different classes are calculated with the distinct QoS requirments and the status of network resource. Simulations verify the performance of the routing algorithm at different time and in different regions, and results demonstrate that the algorithm has great advantages in terms of the average delay and the blocking probability. Meanwhile, the robustness issue is also discussed.
文摘Human beings’ intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms.It is detailed in this paper how to utilize the hierarchical reasoning on the basis of greedy and directional strategy to establish a spatial heuristic,so as to improve running efficiency and suitability of shortest path algorithm for traffic network.The authors divide urban traffic network into three hierarchies and set forward a new node hierarchy division rule to avoid the unreliable solution of shortest path.It is argued that the shortest path,no matter distance shortest or time shortest,is usually not the favorite of drivers in practice.Some factors difficult to expect or quantify influence the drivers’ choice greatly.It makes the drivers prefer choosing a less shortest,but more reliable or flexible path to travel on.The presented optimum path algorithm,in addition to the improvement of the running efficiency of shortest path algorithms up to several times,reduces the emergence of those factors,conforms to the intellection characteristic of human beings,and is more easily accepted by drivers.Moreover,it does not require the completeness of networks in the lowest hierarchy and the applicability and fault tolerance of the algorithm have improved.The experiment result shows the advantages of the presented algorithm.The authors argued that the algorithm has great potential application for navigation systems of large_scale traffic networks.
文摘Research on brain function after brachial plexus injury focuses on local cortical functional reorganization,and few studies have focused on brain networks after brachial plexus injury.Changes in brain networks may help understanding of brain plasticity at the global level.We hypothesized that topology of the global cerebral resting-state functional network changes after unilateral brachial plexus injury.Thus,in this cross-sectional study,we recruited eight male patients with unilateral brachial plexus injury(right handedness,mean age of 27.9±5.4years old)and eight male healthy controls(right handedness,mean age of 28.6±3.2).After acquiring and preprocessing resting-state magnetic resonance imaging data,the cerebrum was divided into 90 regions and Pearson’s correlation coefficient calculated between regions.These correlation matrices were then converted into a binary matrix with affixed sparsity values of 0.1–0.46.Under sparsity conditions,both groups satisfied this small-world property.The clustering coefficient was markedly lower,while average shortest path remarkably higher in patients compared with healthy controls.These findings confirm that cerebral functional networks in patients still show smallworld characteristics,which are highly effective in information transmission in the brain,as well as normal controls.Alternatively,varied small-worldness suggests that capacity of information transmission and integration in different brain regions in brachial plexus injury patients is damaged.
基金Project(2009CB219703) supported by the National Basic Research Program of ChinaProject(2011AA05A117) supported by the National High Technology Research and Development Program of China
文摘In order to form an algorithm for distribution network routing,an automatic routing method of distribution network planning was proposed based on the shortest path.The problem of automatic routing was divided into two steps in the method:the first step was that the shortest paths along streets between substation and load points were found by the basic ant colony algorithm to form a preliminary radial distribution network,and the second step was that the result of the shortest path was used to initialize pheromone concentration and pheromone updating rules to generate globally optimal distribution network.Cases studies show that the proposed method is effective and can meet the planning requirements.It is verified that the proposed method has better solution and utility than planning method based on the ant colony algorithm.
基金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.
基金The Project Supported by National Natural Science Foundation of China
文摘A “Random Shortest Path”traffic assignment model and its algorithm arepresented by simulating the trip-makers’route-choice characters,and the dynamic meth-od is introduced in the assignment model.It is a ideal multiple path assignment modelwhich can be carried out by the dynamic method and static method,can better reflect boththe shortest path factor and the random factor in the route-choice,and is of reasonableassignment volumes.Besides,both dynamic and static softwares particularly suited to thetraffic assignment of large and medium-sized transportation networks arc developed.
基金Supported by the National Natural Science Foundation of China(No.69772035)
文摘Based on their "Theorem 2", an O(δ)-time algorithm of searching for the shortest path between each pair of nodes in a double loop network was proposed by K.Mukhopadyaya, et al.(1995). While, unfortunately, it will be proved that both "Theorem 2" and its proof are in error. A new and more faster O(△)-time, △≤δ, algorithm will be presented in this paper.
基金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.
文摘Routing, modulation and spectrum allocation in elastic optical networks is a problem aiming at increasing the capacity of the network. Many algorithms such as shortest path algorithm can be used as the routing section of this problem. The efficiency of these algorithms is partly based on how the cost of each link is defined. In this study, we considered several basic metrics in cost of network links and compared their effects on the network capacity. In particular, the static costs and the dynamic costs were evaluated and compared. For dynamic scenarios, compared to static scenarios, at least one additional factor, the usage of the links, was added. We further considered a new factor that is based on probability of accommodating the signal at a given time in any given link. The results show that, among them, the shortest path algorithm provides the least blocking probability when the cost is a combination of link length and the abovementioned possibility/usage of the link.
基金The project supported by the Key Project5 of National Natural Science Foundation of China under Grant No 70431002, and National Natural Science Foundation of China under Grant Nos. 70371068 and 10247005
文摘Based on the model of the same degree of all nodes we proposed before, a new algorithm, the so-called “spread all over vertices” (SAV) algorithm, is proposed for generating small-world properties from a regular ring lattices. During randomly rewiring connections the SAV is used to keep the unchanged number of links. Comparing the SAV algorithm with the Watts-Strogatz model and the “spread all over boundaries” algorithm, three methods can have the same topological properties of the small world networks. These results offer diverse formation of small world networks. It is helpful to the research of some applications for dynamics of mutual oscillator inside nodes and interacting automata associated with networks.
基金National Science and Technology Action Program for Road Traffic Safety (No. 2009BAG13A05)the National Natural Science Foundation of China (No. 51078086)
文摘In order to evaluate the practicality and effectiveness of the turn-based algorithm for logit loading (TALL), the TALL is implemented using C++, and it is compared with a combination of the network-expanding method and the Dial algorithm based on the analysis of algorithm procedures. The TALL uses the arc-labeling shortest path searching, bidirectional star and the deque structure to directly assign the traffic flow, while the Dial algorithm should be used in an expanded network. The test results over realistic networks of eight cities show the superior performance of the TALL algorithm over the combination of the network-expanding method and the Dial algorithm, and the average processing time is reduced by 55. 4%. Furthermore, it is found that the operational efficiency of the TALL relates to the original densities of the cities. The average processing time is reduced by 65. 1% when the original density is about 14%, but the advantage of the TALL is not obvious with the increase in the original density.
基金Projects(72071202,71671184)supported by the National Natural Science Foundation of ChinaProject(22YJCZH144)supported by Humanities and Social Sciences Youth Foundation,Ministry of Education of China+3 种基金Project(2022M712680)supported by Postdoctoral Research Foundation of ChinaProject(22KJB110027)supported by Natural Science Foundation of Colleges and Universities in Jiangsu Province,ChinaProject(D2019046)supported by Initiation Foundation of Xuzhou Medical University,ChinaProject(2021SJA1079)supported by General Project of Philosophy and Social Science Research in Jiangsu Universities,China。
文摘Consideration of the travel time variation for rescue vehicles is significant in the field of emergency management research.Because of uncertain factors,such as the weather or OD(origin-destination)variations caused by traffic accidents,travel time is a random variable.In emergency situations,it is particularly necessary to determine the optimal reliable route of rescue vehicles from the perspective of uncertainty.This paper first proposes an optimal reliable path finding(ORPF)model for rescue vehicles,which considers the uncertainties of travel time,and link correlations.On this basis,it investigates how to optimize rescue vehicle allocation to minimize rescue time,taking into account travel time reliability under uncertain conditions.Because of the non-additive property of the objective function,this paper adopts a heuristic algorithm based on the K-shortest path algorithm,and inequality techniques to tackle the proposed modified integer programming model.Finally,the numerical experiments are presented to verify the accuracy and effectiveness of the proposed model and algorithm.The results show that ignoring travel time reliability may lead to an over-or under-estimation of the effective travel time of rescue vehicles on a particular path,and thereby an incorrect allocation scheme.
基金Supported by the National Natural Science Founda-tion of China (60373088)
文摘We put forward an optimal disk schedule with n disk requests and prove its optimality mathematically.Generalizing the idea of an optimal disk schedule, we remove the limit of n requests and, at the same time, consider the dynamically arrival model of disk requests to obtain an algorithm, shortest path first-fit first (SPFF). This algorithm is based on the shortest path of disk head motion constructed by all the pendent requests. From view of the head moving distance, it has the stronger glohality than SSTF. From view of the head-moving direction, it has the better flexibility than SCAN. Therefore, SPFF keeps the advantage of SCAN and, at the same time, absorbs the strength of SSTF. The algorithm SPFF not only shows the more superiority than other scheduling polices, but also have higher adjustability to meet the computer system's different demands.
基金Supported by the National Natural Science Foundation of China(No.61301125)the National High Technology Research and Development Programme of China(No.0AA0401028003)+2 种基金National Science and Technology Major Project(No.2013ZX03005005)the Fundamental and Advanced Research Program of Chongqing(No.cstc2013jcyjA40008)the Youth Top-notch Talent Support Program of Chongqing(No.2013-139)
文摘ISA100.11 a industrial wireless network standard is based on a deterministic scheduling mechanism.For the timeslot delay caused by deterministic scheduling,a routing algorithm is presented for industrial environments.According to timeslot,superframe,links,channel and data retransmission of deterministic scheduling mechanisms that affect the design of the routing algorithm,the algorithm selects the link quality,timeslot delay and retransmission delay as the routing criteria and finds the optimum communication path by k shortest paths algorithm.Theoretical analysis and experimental verification show that the optimal paths selected by the algorithm not only have high link quality and low retransmission delay,but also meet the requirements of the deterministic scheduling.The algorithm can effectively solve the problem of packet loss and transmission delay during data transmission,and provide a valuable solution for efficient data transmission based on determinacy.
文摘软件定义网络(Software Defined Network,SDN)以其强大的可编程性和集中控制的优势得到了学术界的广泛关注。现有的SDN设备在执行报文转发时仍然使用最短路径协议,当最短路径中的结点发生故障时,网络仍然需要重新收敛,在此期间报文可能会被丢弃,进而无法传递至目的结点,给实时性应用的流畅性造成了冲击,影响用户体验。学术界普遍采用路由保护的方案来应对网络故障,现有的路由保护方案存在以下两个方面的问题:(1)故障保护率低;(2)当网络出现故障时,备份路径可能会出现路由环路。为了解决上述两个问题,首先提出了备份下一跳计算规则;然后基于此规则设计了一种软件定义网络下的高故障保护率的路由保护算法(Routing Protection Algorithm with High Failure Protection Ratio,RPAHFPR),该算法融合了路径生成算法(Path Generation Algorithm,PGA)、旁支优先算法(Side Branch First Algorithm,SBF)和环路规避算法(Loop Avoidance Algorithm,LAA),可以同时解决已有路由保护方法面临的故障保护率低和路由环路问题;最后在大量的真实网络拓扑和模拟网络拓扑中验证了RPAHFPR方案的性能。与经典的NPC和U-TURN相比,RPAHFPR的故障保护率分别提高了20.85%和11.88%,并且在86.3%的拓扑中可以达到100%的故障保护率,在所有拓扑中可以达到99%以上的故障保护率。RPAHFPR的路径拉伸度基本接近1,不会引入过多的时间延迟。