Distribution network planning based on shortest path

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.

The Shortest Path Analysis Based on Road Network

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 Shortest Path Algorithm for Multi-stage Network with Linear Parameter

In this paper, we give the shortest path algorithm for multi-stage network with a linear parameter, and study its complexity.

Implementation and comparative testing of turn-based algorithm for logit network loading

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.

A routing algorithm for industrial wireless network based on ISA100.11a

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.

Efficient Routing Protection Algorithm Based on Optimized Network Topology

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.

Small World Properties Generated by a New Algorithm Under Same Degree of All Nodes

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.

A Disk Scheduling Algorithm:SPFF

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.

面向可编程网络的高可靠路由优化算法研究

随着网络规模的不断扩大和复杂度的增加,网络的可靠性和性能变得越来越重要。在可编程网络中,路由优化算法成为提高网络性能和可靠性的重要手段之一。在网络中,路由优化是一个非常重要的问题,因为它直接影响网络的性能和可靠性。传统的路由算法存在一些问题,如收敛速度慢、资源利用率低等。为了解决上述问题,提出了一种新的路由优化算法,即结合Bellman-Ford的双向Dijkstra算法进行最短路径计算。具体来说,首先从可编程网络入手,分析了传统的路由算法存在的问题;接着,为了改进传统Dijkstra算法中无法对存在负权边进行求解的不足,在存在负权边时融入Bellman-Ford算法进行求解,对所有边进行V-1次松弛操作,预处理出源点和汇点到每个节点的距离上界,从而减少计算量;然后通过预处理出源点和汇点到所有节点的最短路径长度的上界,可以减少Dijkstra算法的搜索范围,从而提高搜索效率;最后通过仿真对所提出的算法进行了验证,并与传统的路由算法进行了比较。实验结果表明,所提出的算法在收敛速度、资源利用率等方面均表现优秀,能够有效提高网络的性能和可靠性。因此,以上的研究具有一定的理论和实际意义,对于网络技术的发展具有重要的参考价值。

ON THE FAULT-TOLERANT ROUTING IN DISTRIBUTED LOOP NETWORKS

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.

Resource Allocation Using SPA Based on Different Cost Functions in Elastic Optical Networks

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设备在执行报文转发时仍然使用最短路径协议,当最短路径中的结点发生故障时,网络仍然需要重新收敛,在此期间报文可能会被丢弃,进而无法传递至目的结点,给实时性应用的流畅性造成了冲击,影响用户体验。学术界普遍采用路由保护的方案来应对网络故障,现有的路由保护方案存在以下两个方面的问题:(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,不会引入过多的时间延迟。

基于空间最短距离算法的三相不平衡人工翻仓治理策略

随着社会的发展,人们对电能质量的要求越来越高,而配变台区三相负荷不平衡会对配电网的供电安全性、供电质量和经济运行产生不良影响,是低压电网运行的薄弱环节。通过将空间最短距离算法应用于三相不平衡治理策略研究中,完成了同站配变三相不平衡人工翻仓治理,为配电网三相不平衡科学治理提供了新的可行方案。

基于城市道路网的最短路径分析解决方案

近年来 GIS对网络分析功能的需求迅速增长 .网络分析中的一个关键问题是最短路径问题 ,它作为许多领域中选择最优问题的基础 ,在交通网络分析系统中占有重要地位 .由于最短路径分析常用于汽车导航系统以及各种城市应急系统 (如 110报警、119火警以及 12 0急救系统 ) ,本文针对城市道路网的特点 ,提出了一种实用。

动态网络最短路径射线追踪

最短路径射线追踪算法 ,用预先设置的网络节点的连线表示地震波传播路径 ,当网络节点稀疏时 ,获得的射线路径呈之字形 ,计算的走时比实际走时系统偏大 .本文在波前扩展和反向确定射线路径的过程中 ,在每个矩形单元内 ,通过对某边界上的已知走时节点的走时进行线性插值 ,并利用Fermat原理即时求出从该边界到达其他边界节点的最小走时及其子震源位置和射线路径 ,发展了相应的动态网络算法 .从而克服了最短路径射线追踪算法的缺陷 ,大大提高了最小走时和射线路径的计算精度 .

适合复杂网络分析的最短路径近似算法

基于互联网抽取的社会网络往往具有较大的规模,这对社会网络分析算法的性能提出了更高的要求.许多网络性质的度量都依赖于最短路径信息,社会网络等现实网络往往表现出"无标度"等复杂网络特征,这些特征指示了现实网络中最短路径的分布规律.基于现实网络的拓扑特征,提出了一种适合于复杂网络的最短路径近似算法,利用通过局部中心节点的一条路径近似最短路径,该算法能够方便地用于需要最短路径信息的社会网络性质的估算,为复杂网络的近似分析提供了一种新的思路.在各种生成网络与现实网络上的实验结果表明,该算法在复杂网络上能够大幅降低计算复杂性并保持较高的近似准确性.

图的节点-弧段联合结构表示法及其在GIS最优路径选取中的应用

最短路径分析是ＧＩＳ网络分析的一个基本问题，获取最短路径的经典算法主要有迪杰斯特拉（Ｄｉｊｋｓｔｒａ）及弗罗伊德（Ｆｌｏｙｄ）算法，这两种方法的实现都主要借助于图的节点邻接矩阵来表示图并通过适当的搜索技术完成。本文从节约存储空间、提高运算速度出发，采用节点－弧段联合结构来表示图，避开采用大规模数组，并利用深度优先搜索算法，实现最短路径的自动判断与提取，并给出算法的实现方法。

物理节点可重复映射的虚拟网映射算法

该文在已有的映射算法基础上,结合K短路径的思想,改进了链路映射过程。算法通过多次搜索K短路径,寻找满足虚链路带宽需求的物理路径,有效地提高了虚链路的映射率。同时,根据虚拟网映射特性,针对节点映射过程,提出了物理节点可重复映射的映射算法,即在同一虚拟网映射过程中,物理节点可接受多个虚节点的映射。算法不仅减少了部分虚链路的映射过程,降低了映射的复杂度,而且节约了链路映射的成本,使物理网可以接收更多的虚拟网请求,有效地提高了映射效率。模拟实验表明,算法在执行时间、映射成功率以及映射收益等指标上都有着明显优势。

基于稳定分支的变权网络最优路径算法

有向网络的最短路问题在交通、通讯系统的最优传输路径中有重要应用.在通常的模型中,每条弧的权是给定的.但在实际问题中,弧的权会发生变化,例如在交通拥堵时运行时间会变长.如果当权发生变化时,要重新调用最短路算法,则浪费计算时间.本文提出最短路稳定性的概念,给出了关于最短路长度稳定、最优解稳定与稳定分支的命题与理论证明,在此基础上给出一种新的变权网络最短路径算法,利用权发生变化前的信息,减少计算量,提高计算效率.通过模拟实验验证了该算法的有效性.

时间依赖的网络中最小时间路径算法

时间依赖的网络与传统网络模型相比更具有现实意义 ,具有广泛的应用领域 .交通网络和通信网络可以抽象为时间依赖的网络模型 .当模型中弧的长度是时间依赖的变量 ,最短路径问题的求解变得非常困难 ,早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的 ,因此给出限制性条件使得传统最短路径算法是有效的 .该文从最短路径算法的理论基础入手 ,从理论上证明了传统最短路径算法 ,如 Dijkstra算法和标号设置算法 ,在时间依赖的网络上不能有效地求解最短路径问题 ;并且 ,在没有任何限制性条件下 ,给出了时间依赖的网络模型、理论基础、求解最小时间路径的优化条件和 SPTDN算法 ,从理论上证明了 SPTDN算法的正确性 .算法的实验结果是正确的 .