Optimizing Connections:Applied Shortest Path Algorithms for MANETs

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.

New Methods to Solve Fuzzy Shortest Path Problems

This paper discusses the problem of finding a shortest path from a fixed origin s to a specified node t in a network with arcs represented as typical triangular fuzzy numbers (TFN). Because of the characteristic of TFNs, the length of any path p from s to t , which equals the extended sum of all arcs belonging to p , is also TFN. Therefore, the fuzzy shortest path problem (FSPP) becomes to select the smallest among all those TFNs corresponding to different paths from s to t (specifically, the smallest TFN represents the shortest path). Based on Adamo's method for ranking fuzzy number, the pessimistic method and its extensions - optimistic method and λ combination method, are presented, and the FSPP is finally converted into the crisp shortest path problems.

A genetic algorithm for the pareto optimal solution set of multi-objective shortest path problem

Unlike the shortest path problem that has only one optimal solution and can be solved in polynomial time, the muhi-objective shortest path problem （ MSPP ） has a set of pareto optimal solutions and cannot be solved in polynomial time. The present algorithms focused mainly on how to obtain a precisely pareto optimal solution for MSPP resulting in a long time to obtain multiple pareto optimal solutions with them. In order to obtain a set of satisfied solutions for MSPP in reasonable time to meet the demand of a decision maker, a genetic algo- rithm MSPP-GA is presented to solve the MSPP with typically competing objectives, cost and time, in this pa- per. The encoding of the solution and the operators such as crossover, mutation and selection are developed. The algorithm introduced pareto domination tournament and sharing based selection operator, which can not only directly search the pareto optimal frontier but also maintain the diversity of populations in the process of evolutionary computation. Experimental results show that MSPP-GA can obtain most efficient solutions distributed all along the pareto frontier in less time than an exact algorithm. The algorithm proposed in this paper provides a new and effective method of how to obtain the set of pareto optimal solutions for other multiple objective optimization problems in a short time.

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.

An efficient parallel algorithm for shortest pathsin planar layered digraphs

This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log^3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.

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.

An Algorithm to Find K Shortest Path

In this figure, it finds a vertex to another vertex k shortest path algorithm. Provided there are n vertices and edges in the diagram. If the path loops, the time complexity of the algorithm is allowed O（w ＋ n log 2 n ＋ kw log 2 k）. If the request path does not contain the loop, the time complexity of the algorithm O（kn（w ＋ n log2 n）＋ kw log2 k）. The algorithm utilizes a simple extension of the Dijkstra algorithm determined the end of the length of the shortest path to the other vertices, and then, based on these data, branch and bound method to identify the required path. Experimental results show that the actual running time has relations with the structure of FIG.

An efficient shortest path approach for social networks based on community structure

Finding the shortest path （SP） in a large-scale network analysis between any two nodes is a tough but very significant task. The SP can help us to analyze the information spreading performance and research the latent relationship in the weighted social network, and so on. As the size of the social network increases, the traditional SP algorithms have poor performance and there is not a suitable algorithm for weighted social network. Some features of the network analysis are beneficial to solve this problem, and community structure ignored by the traditional methods is one of the most important features. In this paper, we propose a shortest path algorithm based on community detection （SPCD） by integrating community detection algorithm with traditional search methods. SPCD constructs a community graph by using community structure to narrow the searching scope. The algorithm presented improves the time efficiency and maintains the accuracy scale of the SR Experimental results on five real-world networks demonstrate the effectiveness of the proposed methods for the SP problem.

A self-organizing shortest path finding strategy on complex networks

The shortcomings of traditional methods to find the shortest path are revealed, and a strategy of finding the self- organizing shortest path based on thermal flux diffusion on complex networks is presented. In our method, the shortest paths between the source node and the other nodes are found to be self-organized by comparing node temperatures. The computation complexity of the method scales linearly with the number of edges on underlying networks. The effects of the method on several networks, including a regular network proposed by Ravasz and Barabasi which is called the RB network, a real network, a random network proposed by Ravasz and Barabasi which is called the ER network and a scale-free network, are also demonstrated. Analytic and simulation results show that the method has a higher accuracy and lower computational complexity than the conventional methods.

Shortest Path Routing Algorithm Based on Chaotic Neural Network

A shortest path routing algorithm based on transient chaotic neural network is proposed in this paper. Gam-pared with previous models adopting Hopfield neural network, this algorithm has a higher ability to overcome the local minimum, and achieves a better performance. By introducing a special post-processing technique for the output matrixes, our algorithm can obtain an optimal solution with a high probability even for the paths that need more hops in large-size networks.

Shortest path of temporal networks:An information spreading-based approach

The shortest path is a widely studied network science problem and has attracted great attention.Nevertheless,it draws little attention in temporal networks,in which temporal edges determine information dissemination.In this paper,we propose an information spreading-based method to calculate the shortest paths distribution in temporal networks.We verify our method on both artificial and real-world temporal networks and obtain a good agreement.We further generalize our method to identify influential nodes and found an effective method.Finally,we verify the influential nodes identifying method on four networks.

Minimum-time trajectory planning based on the shortest path for the wheeled mobile robot

The time-optimal trajectory planning is proposed under kinematic and dynamic constraints for a 2-DOF wheeled robot. In order to make full use of the motor’s capacity, we calculate the maximum torque and the minimum torque by considering the maximum heat-converted power generated by the DC motor. The shortest path is planned by using the geometric method under kinematic constraints. Under the bound torques, the velocity limits and the maximum acceleration (deceleration) are obtained by combining with the dynamics. We utilize the phase-plane analysis technique to generate the time optimal trajectory based on the shortest path. At last, the computer simulations for our laboratory mobile robot were performed. The simulation results prove the proposed method is simple and effective for practical use.

Computing All Pairs Shortest Paths on Sparse Graphs with Articulation Points

In most network analysis tools the computation of the shortest paths between all pairs of nodes is a fundamental step to the discovery of other properties. Among other properties is the computation of closeness centrality, a measure of the nodes that shows how central a vertex is on a given network. In this paper, the authors present a method to compute the All Pairs Shortest Paths on graphs that present two characteristics： abundance of nodes with degree value one, and existence of articulation points along the graph. These characteristics are present in many real life networks especially in networks that show a power law degree distribution as is the case of biological networks. The authors＇ method compacts the single nodes to their source, and then by using the network articulation points it disconnects the network and computes the shortest paths in the biconnected components. At the final step the authors proposed methods merges the results to provide the whole network shortest paths. The authors＇ method achieves remarkable speedup compared to state of the art methods to compute the shortest paths, as much as 7 fold speed up in artificial graphs and 3.25 fold speed up in real application graphs. The authors＇ performance improvement is unlike previous research as it does not involve elaborated setups since the authors algorithm can process significant instances on a popular workstation.

A Practical Parallel Algorithm for All-Pair Shortest Path Based on Pipelining

On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.

基于标识密码的内生安全最短路径优先协议

路由协议如开放的最短路径优先协议OSPFV2的安全运行对网络的连通及信息安全传输至关重要。传统OSPFV2协议在设计上缺少抵御源路由伪造或路由信息篡改的能力,致使组网易遭遇攻击,而现有的安全策略多为外挂式,易引发新的安全问题或安全效能低,为此,提出基于标识密码的内生安全OSPFV2协议,将标识密码内嵌于路由交换流程内,使网络具备高效的、内生式的抵御路由在传输过程中的篡改和伪造攻击能力。另一方面,考虑大范围部署安全OSPFV2协议存在多种限制因素,利用不透明链路状态通告,设计支持增量部署的运行机制。仿真实验表明,设计的内生安全OSPFV2协议在不损耗过多收敛时延的同时,具备抵御源路由伪造、数据篡改的安全能力。

Extended Lorenz majorization and frequencies of distances in an undirected network

Purpose:To contribute to the study of networks and graphs.Design/methodology/approach:We apply standard mathematical thinking.Findings:We show that the distance distribution in an undirected network Lorenz majorizes the one of a chain.As a consequence,the average and median distances in any such network are smaller than or equal to those of a chain.Research limitations:We restricted our investigations to undirected,unweighted networks.Practical implications:We are convinced that these results are useful in the study of small worlds and the so-called six degrees of separation property.Originality/value:To the best of our knowledge our research contains new network results,especially those related to frequencies of distances.

Extracting multi-objective multigraph features for the shortest path cost prediction:Statistics-based or learning-based?

Efficient airport airside ground movement(AAGM)is key to successful operations of urban air mobility.Recent studies have introduced the use of multi-objective multigraphs(MOMGs)as the conceptual prototype to formulate AAGM.Swift calculation of the shortest path costs is crucial for the algorithmic heuristic search on MOMGs,however,previous work chiefly focused on single-objective simple graphs(SOSGs),treated cost enquires as search problems,and failed to keep a low level of computational time and storage complexity.This paper concentrates on the conceptual prototype MOMG,and investigates its node feature extraction,which lays the foundation for efficient prediction of shortest path costs.Two extraction methods are implemented and compared:a statistics-based method that summarises 22 node physical patterns from graph theory principles,and a learning-based method that employs node embedding technique to encode graph structures into a discriminative vector space.The former method can effectively evaluate the node physical patterns and reveals their individual importance for distance prediction,while the latter provides novel practices on processing multigraphs for node embedding algorithms that can merely handle SOSGs.Three regression models are applied to predict the shortest path costs to demonstrate the performance of each.Our experiments on randomly generated benchmark MOMGs show that(i)the statistics-based method underperforms on characterising small distance values due to severe overestimation;(ii)A subset of essential physical patterns can achieve comparable or slightly better prediction accuracy than that based on a complete set of patterns;and(iii)the learning-based method consistently outperforms the statistics-based method,while maintaining a competitive level of computational complexity.

基于分布式SDN的机动通信系统拓扑发现方法

针对目前传统机动通信系统、主流软件定义网络(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%,增加了收集信道种类等网络信息的新功能。

Study on Applying Optimal Path to Land Valuation

As an important role in the urban land price system, the basic land price appraisal directs and refleets all kinds of land price in the real estate market. Using geographic information systems （GIS） with algo rithms and powerful analysis functions to valuate land will improve the rationality and convenience of land valu- ation. The objective of the study on basic land price using the optimal path algorithm is to decrease the man made error, enhance automatization, avoid make inconvenience by roadblock object.

A novel similarity measure for mining missing links in long-path networks

Network information mining is the study of the network topology,which may answer a large number of applicationbased questions towards the structural evolution and the function of a real system.The question can be related to how the real system evolves or how individuals interact with each other in social networks.Although the evolution of the real system may seem to be found regularly,capturing patterns on the whole process of evolution is not trivial.Link prediction is one of the most important technologies in network information mining,which can help us understand the evolution mechanism of real-life network.Link prediction aims to uncover missing links or quantify the likelihood of the emergence of nonexistent links from known network structures.Currently,widely existing methods of link prediction almost focus on short-path networks that usually have a myriad of close triangular structures.However,these algorithms on highly sparse or longpath networks have poor performance.Here,we propose a new index that is associated with the principles of structural equivalence and shortest path length(SESPL)to estimate the likelihood of link existence in long-path networks.Through a test of 548 real networks,we find that SESPL is more effective and efficient than other similarity-based predictors in long-path networks.Meanwhile,we also exploit the performance of SESPL predictor and of embedding-based approaches via machine learning techniques.The results show that the performance of SESPL can achieve a gain of 44.09%over GraphWave and 7.93%over Node2vec.Finally,according to the matrix of maximal information coefficient(MIC)between all the similarity-based predictors,SESPL is a new independent feature in the space of traditional similarity features.