基于改进的Floyd算法求节点间所有最短路径

网络节点间的最短路径可能不止一条.首先运用加速的Floyd算法得到最短路径长度矩阵;然后根据最短路径长度矩阵构造各个节点的到达距离矩阵,用来与最短路径长度矩阵进行对比;最后得到每个节点的后继节点,进而得到所有最短路径.计算机仿真验证了该算法的高效性.     

基于最短路径数的网络抗毁评价方法

由于全连通网络具有最强的抗毁性,且节点间最短路径数对于网络抗毁性有重要意义,通过对计算节点之间的最短路径数,并将待评价网络与全连通网络进行结构差异比较,提出了一种基于最短路径数的网络抗毁评价方法.在此基础上建立了网络节点重要性的评价模型,一个节点与网络中其他节点之间的平均等效最短路径数越多,则该节点越重要.由于评价模型的关键是最短路径数的计算,因此,还提出了一种基于邻接阵的最短路径数计算方法.     

有向双环网络G(N;h)的容错路由算法

针对有向双环网络G(N;h)的容错问题,研究了有向双环网络G(N;h)容错节点所对应的等价节点的分布规律,给出一种有向双环网络G(N;h)的容错路由算法. 给出了当有向双环网络任意两个节点之间的最短路径出现故障时,找出另一条最短路径的方法. 此算法的时间复杂度为O(d).     

移动无线传感网的生存时间优化算法研究

当sink节点位置固定不变时,分布在sink 节点周围的传感节点很容易成为枢纽节点,因转发较多的数据而过早失效。为解决上述问题,提出移动无线传感网的生存时间优化算法（LOAMWSN）。LOAMWSN算法考虑sink节点的移动,采用减聚类算法确定sink节点移动的锚点,采用最近邻插值法寻找能遍历所有锚点的最短路径近似解,采用分布式非同步Bellman-Ford算法构建sink节点k跳通信范围内的最短路径树。最终,传感节点沿着最短路径树将数据发送给sink节点。仿真结果表明：在节点均匀分布和非均匀分布的无线传感网中,LOAMWSN算法都可以延长网络生存时间、平衡节点能耗,将平均节点能耗保持在较低水平。在一定的条件下,比Ratio_w、TPGF算法更优。     

光网络中分离路由算法的研究

光网络比传统的包含节点、链路的图论网络更为复杂,使用分离路径能够有效地改善光网络的可靠性.文章提出了一种基于改进蚁群算法的分离路由算法,通过与最短路径优先算法进行仿真比较可知,该算法在多条分离路径的搜索上具有较明显的优势.     

面向绿色互联网的低功耗多播路由算法

基于路径节点驱动策略,提出了一种绿色互联网中的一对多组播路由算法,充分利用路径节点共享路径,生成低功耗最短路径树,提高用户QoS满意度。基于CERNET2拓扑仿真实现了该算法,通过与现有的能量感知启发式路由算法在网络功耗、路由成功率和运行时间等方面的性能对比,表明本文提出的算法具有更好的性能。     

基于社交网络结构的节点影响力度量方法

度量社交网络节点影响力是社交网络结构分析的关键问题之一。目前研究社交网络节点影响力的方法主要有两大类：中心度方法和节点删除方法。前者主要通过度或最短路径等因素来判断节点的影响力，不考虑网络的连通性；后者通过节点删除后对网络结构的破坏程度来判断，计算复杂性很高，不适用于较大规模的社交网络。通过结合社交网络的局部连通度及节点间的最短路径，提出了连通中心度来度量社交网络中节点的影响力，并给出了连通中心度的计算方法和一些特殊网络中节点的连通中心度的值。最后，通过实验说明该指标能很好地度量社交网络中节点的影响力。     

一种基于AODV的链路中断预测和最短路径修复机制

在无线Ad Hoc网络中,为了提高链路质量和通信的稳定性,提出一种基于AODV路由协议的链路中断预测和最短路径修复机制(LIFSR-AODV).通过检测网络中的链接质量,预测和避免链路中断的发生,降低了本地修复过程中控制包的开销和传输延迟.同时,在修复过程中能够通过删除链路中的多余节点来缩短路径长度.通过在IEEE 802.15.4 Matlab模拟器下仿真,验证此路由机制能够提高AODV路由协议的性能和链路的稳定性.     

双环网络并行最优寻径策略及宽直径的研究

将双环网络拓扑结构映射到平面直角坐标系,基于直角坐标系研究双环网络的并行最优寻径方法。首先研究坐标轴上节点及其等价节点的分布规律,建立等价节点分布模型,得出基于等价节点的并行最优寻径策略及双环网络宽直径求解方法。在双环网络最小路径图（MDD）的基础上拓展,提出并行路径图（PDD）的设计思路并予以仿真实现,基于PDD图,设计两点间2条内点不交的并行最短路径的快速求解方法。仿真实验表明,宽直径分布随步长的变化呈现一定波动性,相对于传统的寻径方式,并行最优寻径明显提高了网络传输效率。     

基于相遇紧密程度估测的延迟容忍网络路由

针对延迟容忍网络中节点运动状态变化频繁、通信路径不完整,使得转发消息仅能通过节点相遇而获得连接机会来完成,以及在不知节点间相关性的延迟容忍网络中盲目转发消息易导致其转发成功率较低等问题,提出了基于相遇紧密程度动态估测的延迟容忍网络路由策略。通过设计节点间的条件相遇时间间隔和连接持续时间的计算模型,来确定节点间关系的紧密程度;定义延迟容忍网络模型,构造最短路径择取机制,动态地选出条件最短路径,对消息进行转发。仿真数据对比显示,所提策略可有效改善网络性能,提高消息成功投递率,降低传输时延和负载率。     

Constrained shortest link-disjoint paths selection: a network programming based approach

Given a graph G with each link in the graph associated with two positive weights, cost and delay, we consider the problem of selecting a set of k link-disjoint paths from a node s to another node t such that the total cost of these paths is minimum and that the total delay of these paths is not greater than a specified bound. This problem, to be called the constrained shortest link-disjoint path (CSDP(k)) problem, can be formulated as an integer linear programming (ILP) problem. Relaxing the integrality constraints results in an upper bounded linear programming problem. We first show that the integer relaxations of the CSDP(k) problem and a generalized version of this problem to be called the generalized CSDP (GCSDP (k)) problem (in which each path is required to satisfy a specified bound on its delay) both have the same optimal objective value. In view of this, we focus our work on the relaxed form of the CSDP(k) problem (RELAX-CSDP(k)). We study RELAX-CSDP(k) from the primal perspective using the revised simplex method of linear programming. We discuss different issues such as formulas to identify entering and leaving variables, anti-cycling strategy, computational time complexity etc., related to an efficient implementation of our approach. We show how to extract from an optimal solution to RELAX-CSDP(k) a set of k link-disjoint s-t paths which is an approximate solution to the original CSDP(k) problem. We also derive bounds on the quality of this solution with respect to the optimum. We present simulation results that demonstrate that our algorithm is faster than currently available approaches. Our simulation results also indicate that in most cases the individual delays of the paths produced starting from RELAX-CSDP(k) do not deviate in a significant way from the individual path delay requirements of the GCSDP(k) problem.     

Distributed algorithms for computing shortest pairs of disjointpaths

Distributed algorithms for finding two disjoint paths of minimum total length from each node to a destination are presented. The algorithms have both node-disjoint and link-disjoint versions and provide each node with information sufficient to forward data on the disjoint paths. It is shown that this problem can be reduced to the problem of finding a minimal shortest path from each node to the destination in a modified network, and a distributed algorithm on the original network that simulates a shortest-paths algorithm running on the modified network is presented. The algorithm has a smaller space complexity than any previous distributed algorithm for the same problem, and a method for forwarding packets is presented that does not require any additional space complexity. A synchronous implementation of the algorithm is also presented and studied     

A k shortest path algorithm for adaptive routing incommunications networks

An efficient and flexible algorithm is presented for finding a k shortest loopless path with distinct initial links from one node to each other node. Low-order polynomial bounds are established for the worst-case time complexity of the algorithm, showing it to offer a substantial improvement over applying known algorithms to the problem. The algorithm can incorporate various extensions, including the ability to handle an algebraic objective, which enhance its applicability to diverse network models. In addition, the k shortest path formulation and algorithm are proposed as a basis for network survivability measures where path length bounds exist     

A high-reliability relay algorithm based on network coding in multi-hop wireless networks

In multi-hop wireless networks, minimizing the transmission time is very important. In this paper, a high-reliability relay algorithm (HRRA) is proposed to decrease the transmission time based on the network coding in multi-rate environment. The HRRA includes the relay selection algorithm (RSA) and the block transmission algorithm (BTA). Based on the relay reliability of node, RSA chooses the neighbor with the higher link rate as the common relay node and creates more network coding opportunities at the common relay node. Thus, the network coding opportunities and the high-rate links associated with common node could both be exploited in the transmissions of BTA. Moreover, a comprehensive theoretical analysis of the transmission time of HRRA in a block is presented. Lastly, the simulation results show that HRRA can significantly reduce the transmission time compared with the shortest path algorithm and heuristic relay node selection algorithm and COPE.

     

A unified enhanced particle swarm optimization‐based virtual network embedding algorithm

Virtual network (VN) embedding is a major challenge in network virtualization. In this paper, we aim to increase the acceptance ratio of VNs and the revenue of infrastructure providers by optimizing VN embedding costs. We first establish two models for VN embedding: an integer linear programming model for a substrate network that does not support path splitting and a mixed integer programming model when path splitting is supported. Then we propose a unified enhanced particle swarm optimization‐based VN embedding algorithm, called VNE‐UEPSO, to solve these two models irrespective of the support for path splitting. In VNE‐UEPSO, the parameters and operations of the particles are well redefined according to the VN embedding context. To reduce the time complexity of the link mapping stage, we use shortest path algorithm for link mapping when path splitting is unsupported and propose greedy k‐shortest paths algorithm for the other case. Furthermore, a large to large and small to small preferred node mapping strategy is proposed to achieve better convergence and load balance of the substrate network. The simulation results show that our algorithm significantly outperforms previous approaches in terms of the VN acceptance ratio and long‐term average revenue. Copyright © 2012 John Wiley & Sons, Ltd.     

Approximate distributed Bellman-Ford algorithms

Routing algorithms based on the distributed Bellman-Ford algorithm (DBF) suffer from exponential message complexity in some scenarios. We propose two modifications to the algorithm which result in a polynomial message complexity without adversely affecting the response time of the algorithm. However, the new algorithms may not compute the shortest path. Instead, the paths computed can be worse than the shortest path by at most a constant factor (<3). We call these algorithms approximate DBF algorithms. The modifications proposed to the original algorithm are very simple and easy to implement. The message complexity of the first algorithm, called the multiplicative approximate DBF, is O(nmlog(nΔ)) where Δ is the maximum length over all edges of an n-nodes m-edges network. The message complexity of the second algorithm, called the additive approximate DBF, is O(δ/Δ nm) where δ is the minimum length over all edges in the network     

A new distributed algorithm to find breadth first search trees

A new distributed algorithm is presented for constructing breadth first search (BFS) trees. A BFS tree is a tree of shortest paths from a given root node to all other nodes of a network under the assumption of unit edge weights; such trees provide useful building blocks for a number of routing and control functions in communication networks. The order of communication complexity for the new algorithm isO(V^{1.6} + E)whereVis the number of nodes and E the number of edges. For dense networks withE geq V^{1.6}this order of complexity is optimum.     

Complexity of gradient projection method for optimal routing indata networks

In this paper, we derive a time-complexity bound for the gradient projection method for optimal routing in data networks. This result shows that the gradient projection algorithm of Goldstein-Levitin-Poljak type formulated by Bertsekas (1982), Bertsekas and Gallager (1987) and Bertsekas et al. (1984) converges to within ε in relative accuracy in O(ε^-2h_minN_max) number of iterations, where N_max is the number of paths sharing the maximally shared link, and h_min is the diameter of the network. Based on this complexity result, we also show that the one-source-at-a-time update policy has a complexity bound which is O(n) times smaller than that of the all-at-a-time update policy, where n is the number of nodes in the network. The result of this paper argues for constructing networks with low diameter for the purpose of reducing complexity of the network control algorithms. The result also implies that parallelizing the optimal routing algorithm over the network nodes is beneficial     

Oscillations in Complex Communication Networks under Attack

In this paper we study the traffic dynamics of a scale-free complex network under an intentional attack at the node with the largest betweenness (i.e., the hub). This node is removed from the network after the attack. Consequently, the traffic load which used to go through the hub has to find other paths. A weight is defined for each node to indicate how long a packet has to wait at this node. A shortest time delay routing strategy is then applied based on the weight. We find that with different values of the capacity redundancy parameter, the traffic dynamics are quite different. When the capacity has large redundancy, then all the nodes work in a free-flow state even after the attack. If the capacity redundancy is not that large, then congestion may occur at some nodes. Due to the shortest time delay routing strategy, this congestion occurs periodically. If the capacity is very small, then the traffic dynamics become complicated, and oscillations and chaotic phenomena take place.