A dynamic routing strategy with limited buffer on scale-free network

In this paper, we propose an integrated routing strategy based on global static topologyinformation and local dynamic data packet queue lengths to improve the transmissionefficiency of scale-free networks. The proposed routing strategy is a combination of aglobal static routing strategy (based on the shortest path algorithm) and local dynamicqueue length management, in which, instead of using an infinite buffer, the queue lengthof each node i in the proposed routing strategy is limited by acritical queue length Q_ic. When the networktraffic is lower and the queue length of each node i is shorter than itscritical queue length Q_ic, it forwardspackets according to the global routing table. With increasing network traffic, when thebuffers of the nodes with higher degree are full, they do not receive packets due to theirlimited buffers and the packets have to be delivered to the nodes with lower degree. Theglobal static routing strategy can shorten the transmission time that it takes a packet toreach its destination, and the local limited queue length can balance the network traffic.The optimal critical queue lengths of nodes have been analysed. Simulation results showthat the proposed routing strategy can get better performance than that of the globalstatic strategy based on topology, and almost the same performance as that of the globaldynamic routing strategy with less complexity.     

Integrating network structure and dynamic information for better routing strategy on scale-free networks

We study information packet routing processes on scale-free networks by mimicking the Internet traffic delivery strategies. We incorporate both the global network structure information and local queuing information in the dynamic processes. We propose several new routing strategies to guide the packet routing. The performance of the routing strategies is measured by the average transit time of the packets as well as their dependence on the traffic amount. We find that the routing strategies which integrate both global network structure information and local dynamic information perform much better than the traditional shortest-path routing protocol which takes into account only the global topological information. Moreover, from comparative studies of these routing strategies, we observe that some of our proposed methods can decrease the average transit time of packets but the performance is closely dependent on the total amount of traffic while some other proposed methods can have good performance independent of the total amount of traffic with hyper-excellent average transit time of packets. Also, numerical results show that our proposed methods integrating network structure information and local dynamic information can work much better than the methods recently proposed in [S. Sreenivasan, R. Cohen, E. López, Z. Toroczkai, H.E. Stanley, Phys. Rev. E 75 (2007) 036105, Zhi-Xi Wu, Gang Peng, Eric W.M. Wong, Kai-Hau Yeung, J. Stat. Mech. (2008) P11002.], which only considered network structure information.     

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

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

Bandwidth allocation strategy for traffic systems of scale-free network

In this Letter, the bandwidth resource allocation strategy is considered for traffic systems of complex networks. With a finite resource of bandwidth, an allocation strategy with preference parameter α is proposed considering the links importance. The performance of bandwidth allocation strategy is studied for the local routing protocol and the shortest path protocol. When important links are slightly favored in the bandwidth allocation, the system can achieve the optimal traffic performance for the two routing protocols. For the shortest path protocol, we also give a method to estimate the network traffic capacity theoretically.     

Adaptive local routing strategy on a scale-free network

Due to the heterogeneity of the structure on a scale-free network, making the betweennesses of all nodes become homogeneous by reassigning the weights of nodes or edges is very difficult. In order to take advantage of the important effect of high degree nodes on the shortest path communication and preferentially deliver packets by them to increase the probability to destination, an adaptive local routing strategy on a scale-free network is proposed, in which the node adjusts the forwarding probability with the dynamical traffic load (packet queue length) and the degree distribution of neighbouring nodes. The critical queue length of a node is set to be proportional to its degree, and the node with high degree has a larger critical queue length to store and forward more packets. When the queue length of a high degree node is shorter than its critical queue length, it has a higher probability to forward packets. After higher degree nodes are saturated (whose queue lengths are longer than their critical queue lengths), more packets will be delivered by the lower degree nodes around them. The adaptive local routing strategy increases the probability of a packet finding its destination quickly, and improves the transmission capacity on the scale-free network by reducing routing hops. The simulation results show that the transmission capacity of the adaptive local routing strategy is larger than that of three previous local routing strategies.     

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.     

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.     

A dynamic model for traffic network flow

Concerning the link properties in traffic networks, we introduce a dynamic equation of road flow into each link, and thereby propose a dynamic model for network flow. Using this model, we investigate the evolutions of inflow, outflow and flow on each link caused by a small perturbation of the network inflow under different route choice rules. Numerical results show that the dynamic model can reasonably capture the basic characteristics of network flow.     

Correlations and clustering in a scale-free network in Euclidean space

Empirical study shows that many real networks in nature and society share two generic properties: they are scale-free and they display a high degree of clustering. Quite often they are modular in nature also, implying occurrences of several small tightly linked groups which are connected in a hierarchical manner among themselves. Recently, we have introduced a model of spatial scale-free network where nodes pop-up at randomly located positions in the Euclidean space and are connected to one end of the nearest link of the existing network. It has been already argued that the large scale behaviour of this network is like the Barabási-Albert model. In the present paper we briefly review these results as well as present additional results on the study of non-trivial correlations present in this model which are found to have similar behaviours as in the real-world networks. Moreover, this model naturally possesses the hierarchical characteristics lacked by most of the models of the scale-free networks.      

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

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

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.     

Choosing effective controlled nodes for scale-free network synchronization

Previous studies concerning pinning control of complex-network synchronization have very often demonstrated that in an unweighted symmetrical scale-free network, controlling the high-degree nodes is more efficient than controlling randomly chosen ones; due to the heterogeneity of the node-degree or edge-connection distribution of the scale-free network, small-degree nodes have relatively high probabilities of being chosen at random but their control has less influence on the other nodes through the network. This raises the question of whether or not controlling the high-degree nodes is always better than controlling the small ones in scale-free networks. Our answer to this is yes and no. In this study, we carry out extensive numerical simulations to show that in an unweighted symmetrical Barabasi-Albert scale-free network, when the portion of controlled nodes is relatively large, controlling the small nodes becomes better than controlling the big nodes and controlling randomly chosen nodes has approximately the same effect as controlling the big ones. However, we also show that for normalized weighted scale-free networks, controlling the big nodes is in fact always better than controlling the small ones.     

一种有效提高无标度网络负载容量的管理策略

现有研究表明明显的社团结构会显著降低网络的传输性能. 本文基于网络邻接矩阵的特征谱定义了链路对网络社团特性的贡献度, 提出一种通过逻辑关闭或删除对网络社团特性贡献度大的链路以提高网络传输性能的拓扑管理策略, 即社团弱化控制策略(CWCS 策略). 在具有社团结构的无标度网络上分别进行了基于全局最短路径路由和局部路由的仿真实验, 并与关闭连接度大的节点之间链路的HDF 策略进行了比较. 仿真实验结果显示, 在全局最短路径路由策略下, CWCS策略能更有效地提高网络负载容量, 并且网络的平均传输时间增加的幅度变小. 在局部路由策略下, 当调控参数0<α<2, 对网络负载容量的提升优于HDF策略. 关键词： 复杂网络 社团特性 负载容量 拓扑管理     

基于改进声线跟踪法的室内交通噪声动态模拟

对碰撞点的有效性判断是传统声线跟踪法的一个重要步骤,在计算复杂的室内空间问题时计算量较大,为解决这一问题采用了一种与空间剖分相结合的改进的声线跟踪法。将该方法与微观交通流仿真和车辆噪声排放模型进行结合,实现了道路交通噪声透过窗户在多连通室内空间传播的动态模拟。最后采用该方法对相同道路和交通流条件下不同建筑朝向的4种布局室内噪声进行动态模拟。分析了室内交通噪声的大小和分布与建筑物布局、窗户的朝向、窗户的形式和面积等因数之间的关系。结果表明:窗户正对道路的房间比窗户侧对道路的房间噪声高4～6 d B(A),房间内等效声级与窗户面积的对数成正比关系。     

Chaos in a dynamic model of traffic flows in an origin-destination network

In this paper we investigate the dynamic behavior of road traffic flows in an area represented by an origin-destination (O-D) network. Probably the most widely used model for estimating the distribution of O-D flows is the gravity model, [J. de D. Ortuzar and L. G. Willumsen, Modelling Transport (Wiley, New York, 1990)] which originated from an analogy with Newton's gravitational law. The conventional gravity model, however, is static. The investigation in this paper is based on a dynamic version of the gravity model proposed by Dendrinos and Sonis by modifying the conventional gravity model [D. S. Dendrinos and M. Sonis, Chaos and Social-Spatial Dynamics (Springer-Verlag, Berlin, 1990)]. The dynamic model describes the variations of O-D flows over discrete-time periods, such as each day, each week, and so on. It is shown that when the dimension of the system is one or two, the O-D flow pattern either approaches an equilibrium or oscillates. When the dimension is higher, the behavior found in the model includes equilibria, oscillations, periodic doubling, and chaos. Chaotic attractors are characterized by (positive) Liapunov exponents and fractal dimensions.(c) 1998 American Institute of Physics.     

An optimal network for passenger traffic

The optimal solution of an inter-city passenger transport network has been studied using Zipf’s law for the city populations and the Gravity law describing the fluxes of inter-city passenger traffic. Assuming a fixed value for the cost of transport per person per kilometer we observe that while the total traffic cost decreases, the total wiring cost increases with the density of links. As a result the total cost to maintain the traffic distribution is optimal at a certain link density which vanishes on increasing the network size. At a finite link density the network is scale-free. Using this model the air-route network of India has been generated and an one-to-one comparison of the nodal degree values with the real network has been made.     

基于复杂网络的交通拥堵与传播动力学分析

本文运用改进的中观交通流模型,研究了网络拓扑结构对交通拥堵的影响,进而分析复杂网络上的交通传播动力学特征和传播规律.结论有助于提出消除交通拥堵的有效控制策略以及交通规划的合理方案. 关键词： 复杂网络 交通流 交通拥堵 传播特性     

混合状态下城市快速路交通流短时预测

建立交通流短时预测状态空间模型, 研究混合状态下城市快速路交通流短时预测. 结合城市快速路自由流状态、拥挤流状态和阻塞流状态下交通流参数的时间和空间分布特性, 基于交通流守恒方程和速度动态模型, 借鉴偏微分方程组求解时空离散的思想, 建立三种状态下交通流短时预测模型; 同时考虑进出口匝道、车道数变更以及道路坡度等因素的影响, 将交通流短时预测模型转化为交通流短时预测状态空间模型, 实现混合状态下交通流短时预测. 研究表明, 该方法能够实现混合状态下道路网内的交通流短时预测, 预测精度可达90.23%. 相同条件下, 经典自回归滑动平均模型的预测精度仅为81%. 关键词： 交通流短时预测 自由流状态 拥挤流状态 阻塞流状态     

A new dynamic model for heterogeneous traffic flow

Based on the property of heterogeneous traffic flow, we in this Letter present a new car-following model. Applying the relationship between the micro and macro variables, a new dynamic model for heterogeneous traffic flow is obtained. The fundamental diagram and the jam density of the heterogeneous traffic flow consisting of bus and car are studied under three different conditions: (1) without any restrictions, (2) under the action of the traffic control policy that restrains some private cars and (3) using bus to replace the private cars restrained by the traffic control policy. The numerical results show that our model can describe some qualitative properties of the heterogeneous traffic flow consisting of bus and car, which verifies that our model is reasonable.