基于最短路径长度的空间网络路由

以通信网、电力网、交通网为代表的很多复杂网络以传输负载为基本功能.在这些网络中,网络的吞吐量是衡量网络传输性能的重要指标,如何提升网络的吞吐量是研究热点之一.不少研究人员提出了不同的路由算法,通过调节传输路径来提高网络吞吐量.但之前的研究很少考虑网络中节点的空间位置.本文针对空间网络提出了一种高效的路由策略,通过节点位置得到路径长度;采用该算法,负载从源节点沿着最短长度的路径传输到目标节点.为了检验算法的有效性,采用网络从自由流状态转变成拥塞状态的相变点Rc来衡量网络的吞吐量.在匀质和异质空间网络上的仿真表明,与传统的最少跳数路由策略相比,本文提出的基于最短路径长度的路由算法能有效提高空间网络的吞吐量.     

基于引力约束的复杂网络拥塞问题研究

如何在保证网络传输效率的同时提高网络的吞吐量是目前研究的主要问题. 通过研究节点对数据包传递过程的引力作用,提出了一种具有引力约束的路由算法. 为检验算法的有效性,通过引入一个状态参数H, 利用由稳态到拥塞状态的指标流量相变值来度量网络的吞吐量, 同时利用数据包的最大传输时间〈T_max〉 与平均传输时间 〈T_avg〉来分析网络的传输效率. 针对算法在不同引力约束条件下的路由情况进行了仿真.仿真结果表明, 若数据传递过程只考虑路径长度最短,则会导致网络吞吐量较低且流量分布极不均匀; 若只顾及等待时间最短,会导致传输路径过度迂回且大部分节点都会陷入拥塞状态; 同时考虑路径长度和等待时间的引力作用并选取适当引力的节点进行传递, 可以显著提高网络吞吐量并缓解网络的拥塞程度.     

基于局部路由策略的复杂网络拥塞控制

提出一种复杂网络上的局部路由策略,算法采用节点收缩法评估节点的重要度,发送节点根据邻居节点的重要度及网络的状态自适应地调整向邻居节点转发数据包的概率.在网络处于自由流通状态时充分发挥关键节点的优势,保证数据包快速到达目的地;在网络处于即将拥塞时分散业务,根据节点重要度准确识别网络中的关键节点,通过有效分流予以保护.仿真结果表明:在网络处于自由流通状态时,该局部路由策略能充分发挥网络中关键节点的枢纽作用,保持较低的传输时延;在网络部分关键节点出现拥塞时,该局部路由策略能有效避开拥挤严重的节点,将数据包均匀地分布在各个节点上,有效抑制网络拥塞,提高网络的容量.     

基于感知流量算法的复杂网络拥塞问题研究

研究了在具有感知流量的路由策略下,复杂网络的拓扑结构对网络中传输流量的影响.为了描述数据包传输过程的有效性,通过引入一个状态参数,利用由稳态到拥塞的指标流量相变值来刻画网络的吞吐量.基于每个节点的数据包处理能力与该节点的度或介数成比例提出两种模型并进行仿真.仿真结果表明,平均度相同的情况下,模型Ⅰ中,WS小世界网络比ER随机网络和BA无标度网络更容易产生拥塞;模型Ⅱ中,所有网络容量都得到较大的提高,尤其是WS小世界网络.但当网络的基本连接参数改变时,哪种模型更利于网络的流量传输,还要依据网络本身的结构特性 关键词： 复杂网络 无标度网络 感知流量 拥塞     

基于引力场理论的复杂网络路由选择策略研究

利用引力场理论对网络传输过程中节点激发的引力场进行了描述,建立了节点的引力场方程,引入α和γ两个参数,用于调节数据传输对节点畅通程度、节点传输能力和路径长度的依赖程度．基于节点的引力场,提出了一种高效的路由选择算法,该算法下数据包将沿着所受路径引力最大的方向进行传递．为检验算法的有效性,引入有序状态参数卵,利用其由自由流到拥塞态的指标流量相变值度量网络的吞吐量,并通过节点的介中心值B分析网络的传输性能和拥塞分布．针对算法在不同α,γ取值条件下的路由情况进行了仿真．仿真结果显示,与传统最短路由算法相比,本文算法将网络传输能力提高了数倍,有效地均衡了节点的介中心值分布,传输路径平均长度（Lavg）随负载量R的增加表现出先增后减的变化趋势,而参数α与γ值的变化对网络传输能力几乎没有影响,说明本文路由算法的性能不依赖于α与γ,对于可行域内任意的α与γ算法都能保证网络传输能力近似相等．     

无标度复杂网络负载传输优化策略

提出了一种能够显著提高无标度复杂网络负载传输性能的优化路由策略.实现了负载在核心节点与边缘节点间的合理分配.分析表明该策略使得网络的负载处理能力正比于网络规模的平方,而与单个节点的度值无关.实验结果显示优化路由策略在保持了最短路由策略小世界效应的同时,成倍地提升了网络的负载传输能力,且随着网络平均节点度的增加其优势越趋显著.此外,与有效路由策略的比较进一步验证了优化路由策略的优异性能. 关键词： 优化路由策略 复杂网络 负载传输 网络阻塞     

基于耦合强度的双层网络数据传输能力

为了降低网络拥塞,提升网络传输性能,对双层网络之间的耦合机理进行研究,层间关系依据度度相关性分成三种耦合方式:随机耦合、异配耦合、同配耦合.在基于最短路径路由策略和基于度的权重路由策略条件下,分析网络数据包的传输过程,并研究双层网络的耦合方式及其适合的路由策略对网络传输容量的影响.采用双层无标度网络进行仿真实验,分析在路由策略约束下传输容量和耦合方式之间的关系,依据双层网络之间耦合方式的特点,找出适合每一种路由策略的最佳耦合方式以提升网络的传输容量.经过仿真发现,采用最短路径路由策略时,异配耦合方式最佳;采用基于度的静态权重路由策略时,同配耦合方式最佳.路由策略在匹配的耦合方式下使得网络流量分配均匀,有利于网络传输容量的提升.本研究为实际网络设计和传输性能优化提供了理论基础.     

一种应用于含权无标度网络的全局路由算法

针对含权无标度网络提出了一种全局路由算法.该算法利用网络路径上的节点强度信息构建了一种全局路由代价函数,选择使该代价函数最小的路径来传输信息包,有效避开了网络中易发生拥塞的核心节点.实验结果表明,与最短路径算法相比,该算法以较小的平均路径长度的增加为代价,将网络容量提高了十多倍.     

一类基于随机行走机理的优化路由改进策略

在对随机行走过程的研究中发现:单个粒子通过某条特定路径的时间正比于该路径上所有节点度的连乘积.据此,文章提出基于随机行走机理的优化路由改进策略.该策略以节点度连乘积最小化为原则,通过调节可变参数,建立节点处理能力均匀分布的情况下最佳路由策略.通过分析比较不同路由策略条件下平均路由介数中心度,网络的临界负载量,平均路径长度以及平均搜索信息量等性能指标,研究结果表明,此改进路由策略在保证网络平均路径长度较少增加的前提下,使网络的传输能力获得最大幅度的提升. 关键词： 复杂网络 路由策略 负载传输     

无标度网络中基于能量的混合路由策略

针对节点能量受限的静态无标度网络,提出了一种基于能量和最短路径相结合的路由策略.该策略综合考虑邻居节点的能量水平和其到目的节点的最短路径长度,利用控制参数β调节二者的权重.仿真结果表明,存在最佳的β值使得网络生存时间和数据包到达数达到最大值.最后,基于提出的路由策略研究了网络结构特征与网络生存时间之间的关系.     

Effective strategy of adding nodes and links for maximizing the traffic capacity of scale-free network

In this paper, we propose an efficient strategy to enhance traffic capacity via the process of nodes and links increment. We show that by adding shortcut links to the existing networks, packets are avoided flowing through hub nodes. We investigate the performances of our proposed strategy under the shortest path routing strategy and the local routing strategy. Our obtained results show that using the proposed strategy, the traffic capacity can be effectively enhanced under the shortest path routing strategy. Under the local routing strategy, the obtained results show that the proposed strategy is efficient only when packets are more likely to be forwarded to low-degree nodes in their routing paths. Compared with other strategies, the obtained results indicate that our proposed strategy of adding nodes and links is the most effective in enhancing the traffic capacity, i.e., the traffic capacity can be maximally enhanced with the least number of additional nodes and links.     

Efficient packet routing strategy in complex networks

We investigate a new efficient packet routing strategy which mitigates traffic congestion on complex networks. In order to avoid congestion, we minimize the maximum betweenness, which is a measure for concentration of routing paths passing through a node in the network. Danila et al. propose a packet routing strategy in which, instead of shortest paths, they used efficient paths, which are the paths with the minimum total summations of weights assigned to nodes in the respective paths. They use a heuristic algorithm in which the weights are updated step by step by using the information of betweenness of each node in every step and the respective total summations of weights for paths through the nodes with large degrees become comparatively large. Thus passage through such nodes, where congestion almost occurs, is likely to be avoided in their algorithm. The convergence time by their algorithm is, however, quite long. In this paper, we propose a new efficient heuristic algorithm which balances traffic on networks by achieving minimization of the maximum betweenness in the much smaller number of iteration steps for convergence than that by the algorithm of Danila et al.     

Probability routing strategy for scale-free networks

This study proposes a probability routing strategy for improving traffic capability on scale-free networks. Compared with the shortest path routing strategy depending on central nodes largely and the efficient routing strategy avoiding hub routers as much as possible, the probability routing strategy makes use of hub routers more efficiently, transferring approximate average amount of packs of the whole network. Simulation results indicate that the probability routing strategy has the highest network capacity among the three routing strategies. This strategy provides network capacity that can be more than 30 times higher than that of the shortest path routing strategy and over 50% higher than that of the efficient routing strategy. In addition, the average routing path length of our proposed strategy is over 10% shorter than that of the efficient routing strategy and only about 10% longer than that of the shortest path routing strategy.     

Traffic dynamics based on a traffic awareness routing strategy on scale-free networks

By incorporating local traffic information into the shortest path routing strategy, we numerically investigate the effectiveness of the traffic awareness routing strategy for scale-free networks with different clustering. In order to characterize the efficiency of the packet-delivery process, we introduce an order parameter and an average transmission time that allow us to measure the network capacity by the critical value of phase transition from free flow to congestion. Compared with the shortest path routing protocol, the network capacity is greatly enhanced by the traffic awareness routing strategy. We also find that there exists an optimum value for the tunable parameter in the congestion awareness strategy. Moreover, simulation results show that the more clustered the network, the less efficient the packet-delivery process.     

Generalized minimum information path routing strategy on scale-free networks

This paper presents a new routing strategy by introducing a tunable parameter into the minimum information path routing strategy we proposed previously.It is found that network transmission capacity can be considerably enhanced by adjusting the parameter with various allocations of node capability for packet delivery.Moreover,the proposed routing strategy provides a traffic load distribution which can better match the allocation of node capability than that of traditional efficient routing strategies,leading to a network with improved transmission performance.This routing strategy,without deviating from the shortest-path routing strategy in the length of paths too much,produces improved performance indexes such as critical generating rate,average length of paths and average search information.     

Traffic resource allocation for complex networks

In this paper, an optimal resource allocation strategy is proposed to enhance traffic dynamics in complex networks. The network resources are the total node packet-delivering capacity and the total link bandwidth. An analytical method is developed to estimate the overall network capacity by using the concept of efficient betweenness (ratio of algorithmic betweenness and local processing capacity). Three network structures (scale-free, small-world, and random networks) and two typical routing protocols (shortest path protocol and efficient routing protocol) are adopted to demonstrate the performance of the proposed strategy. Our results show that the network capacity is reversely proportional to the average path length for a particular routing protocol and the shortest path protocol can achieve the largest network capacity when the proposed resource allocation strategy is adopted.     

Incremental routing strategy on scale-free networks

The most important function of a network is for transporting traffic. Due to the low traffic capacity of network systems under the global shortest path routing, plenty of heuristic routing strategies are emerging. In this paper, we propose a heuristic routing strategy called the incremental routing algorithm to improve the traffic capacity of complex networks. We divide the routing process into N$N$(the network size) steps and, at each step, we heuristically calculate all the routes for one source node considering both the dynamic efficient betweenness centrality and node degree information. We do extensive simulations on scale-free networks to confirm the effectiveness of the proposed incremental routing strategy. The simulation results show that the traffic capacity has been enhanced by a substantial factor at the expense of a slight lengthening in the average path.     

Optimized network structure and routing metric in wireless multihop ad hoc communication

Inspired by the Statistical Physics of complex networks, wireless multihop ad hoc communication networks are considered in abstracted form. Since such engineered networks are able to modify their structure via topology control, we search for optimized network structures, which maximize the end-to-end throughput performance. A modified version of betweenness centrality is introduced and shown to be very relevant for the respective modeling. The calculated optimized network structures lead to a significant increase of the end-to-end throughput. The discussion of the resulting structural properties reveals that it will be almost impossible to construct these optimized topologies in a technologically efficient distributive manner. However, the modified betweenness centrality also allows to propose a new routing metric for the end-to-end communication traffic. This approach leads to an even larger increase of throughput capacity and is easily implementable in a technologically relevant manner.     

Global forward-predicting dynamic routing for traffic concurrency space stereo multi-layer scale-free network

Many real communication networks, such as oceanic monitoring network and land environment observation network,can be described as space stereo multi-layer structure, and the traffic in these networks is concurrent. Understanding how traffic dynamics depend on these real communication networks and finding an effective routing strategy that can fit the circumstance of traffic concurrency and enhance the network performance are necessary. In this light, we propose a traffic model for space stereo multi-layer complex network and introduce two kinds of global forward-predicting dynamic routing strategies, global forward-predicting hybrid minimum queue(HMQ) routing strategy and global forward-predicting hybrid minimum degree and queue(HMDQ) routing strategy, for traffic concurrency space stereo multi-layer scale-free networks. By applying forward-predicting strategy, the proposed routing strategies achieve better performances in traffic concurrency space stereo multi-layer scale-free networks. Compared with the efficient routing strategy and global dynamic routing strategy, HMDQ and HMQ routing strategies can optimize the traffic distribution, alleviate the number of congested packets effectively and reach much higher network capacity.     

Efficient and robust routing on scale-free networks

Information routing is one of the most important problems in large communication networks. In this paper we propose a novel routing strategy in which the optimal paths between all pairs of nodes are chosen according to a cost function that incorporates degrees of nodes in paths. Results on large scale-free networks demonstrate that our routing strategy is more efficient than the shortest path algorithm and the efficient routing strategy proposed by Yan et al. [Phys. Rev. E 73, 046108 (2006)]. Furthermore our routing strategy has strong robustness against cascading failure attacks on networks.