Optimal structure of complex networks for minimizing traffic congestion

To design complex networks to minimize traffic congestion, it is necessary to understand how traffic flow depends on network structure. We study data packet flow on complex networks, where the packet delivery capacity of each node is not fixed. The optimal configuration of capacities to minimize traffic congestion is derived and the critical packet generating rate is determined, below which the network is at a free flow state but above which congestion occurs. Our analysis reveals a direct relation between network topology and traffic flow. Optimal network structure, free of traffic congestion, should have two features: uniform distribution of load over all nodes and small network diameter. This finding is confirmed by numerical simulations. Our analysis also makes it possible to theoretically compare the congestion conditions for different types of complex networks. In particular, we find that network with low critical generating rate is more susceptible to congestion. The comparison has been made on the following complex-network topologies: random, scale-free, and regular.     

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

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

Dynamics of traffic networks: From microscopic and macroscopic perspectives

Considering the microscopic characteristics (vehicle speed, road length etc.) of links and macroscopic behaviors of traffic systems, we derive the critical flow generation rate in scale-free networks. And the dynamics of traffic congestion is studied numerically in this paper. It is shown that the queue length increases with microscopic characteristics of links. Additionally, the critical flow generation rate decreases with increase of the network size N, maximum speed v_max and parameter τ. The significance of this finding is that, in order to improve the traffic environment, both the local information for the single link and behaviors of the whole network must be analyzed simultaneously in a traffic system design.     

Congestion analysis of traffic networks with direction-dependant heterogeneity

Traffic flow directionality and network weight asymmetry are widespread notions in traffic networks. This paper investigates the influence of direction-dependant heterogeneity on traffic congestion. To capture the effect of the link directionality and link weight asymmetry, the heterogeneity indexes of complex networks and the traffic flow model are introduced. The numerical results show that the critical value of heterogeneity determines congestion transition processes. The congestion degree increases with heterogeneity when the network heterogeneity is at a subcritical region. A network is more tolerant of congestion if the heterogeneity of the network is smaller or larger than the critical value. Furthermore, when heterogeneity reaches the critical value, the average number of accumulated vehicles arrives at the maximum and the traffic flow is under a serious congestion state. A significant improvement on the tolerance to congestion of traffic networks can be made if the network heterogeneity is controlled within a reasonable range.     

Criticism of generally accepted fundamentals and methodologies of traffic and transportation theory: A brief review

It is explained why the set of the fundamental empirical features of traffic breakdown (a transition from free flow to congested traffic) should be the empirical basis for any traffic and transportation theory that can be reliably used for control and optimization in traffic networks. It is shown that the generally accepted fundamentals and methodologies of the traffic and transportation theory are not consistent with the set of the fundamental empirical features of traffic breakdown at a highway bottleneck. To these fundamentals and methodologies of the traffic and transportation theory belong (i) Lighthill–Whitham–Richards (LWR) theory, (ii) the General Motors (GM) model class (for example, Herman, Gazis et al. GM model, Gipps’s model, Payne’s model, Newell’s optimal velocity (OV) model, Wiedemann’s model, Bando et al. OV model, Treiber’s IDM, Krauß’s model), (iii) the understanding of highway capacity as a particular (fixed or stochastic) value, and (iv) principles for traffic and transportation network optimization and control (for example, Wardrop’s user equilibrium (UE) and system optimum (SO) principles). Alternatively to these generally accepted fundamentals and methodologies of the traffic and transportation theory, we discuss the three-phase traffic theory as the basis for traffic flow modeling as well as briefly consider the network breakdown minimization (BM) principle for the optimization of traffic and transportation networks with road bottlenecks.     

Phase diagrams of noisy traffic states in the presence of a bottleneck

The traffic states are investigated for the noisy traffic flow in the presence of a bottleneck under the open boundary condition. The phase diagrams of the different kinds of congested traffic are presented for different values of sensitivity (the inverse of delay time). It is shown that the five different types of traffic states appear below the critical point: the free traffic with a pinned localized cluster, the weak standing shock, the moving localized cluster, the oscillatory congested traffic, and the strong standing shock. Above the critical point, the moving localized cluster and oscillatory congested traffic do not occur. Also, in the traffic flow without noise, the moving localized cluster and oscillatory congested traffic do not appear.     

Traffic flow velocity disturbance characteristics and control strategy at the bottleneck of expressway

In the three-phase traffic flow studies, the traffic flow characteristic at the bottleneck section is a hot spot in the academic field. The controversy about the characteristics of the synchronized flow at bottleneck is also the main contradiction between the three-phase traffic flow theory and the traditional traffic flow theory. Under the framework of three-phase traffic flow theory, this paper takes the on-ramp as an example to discuss the traffic flow characteristics at the bottleneck section.In particular, this paper mainly conducts the micro-analysis to the effect of lane change under the two lane conditions, as well as the effect of the on-ramp on the main line traffic flow. It is found that when the main road flow is low, the greater the on-ramp inflow rate, the higher the average speed of the whole road section. As the probability of vehicles entering from the on-ramp increases, the flow and the average speed of the main road are gradually stabilized, and then the on-ramp inflow vehicles no longer have a significant impact on the traffic flow. In addition, this paper focuses on the velocity disturbance generated at the on-ramp, and proposes the corresponding on-ramp control strategy based on it, and the simulation verified that the control strategy can reasonably control the traffic flow by the on-ramp, which can meet the control strategy requirements to some extent.     

结合可视图的多状态交通流时间序列特性分析

交通流时间序列的研究主要采用数据挖掘和机器学习的方法,这些"黑箱"挖掘方法很难直观反映序列特性.为增强交通流时间序列及其特征分析的可视化性,结合可视图理论来构建交通流时间序列的关联网络,从复杂网络角度实现交通流时间序列的特性分析.在网络构建的过程中,考虑到不同交通状态下交通流表征具有的差异性,首先利用交通流参量的相关性对交通流状态进行分类,然后构建不同交通状态下的时间序列复杂网络,并对这些网络的特征属性给出统计分析,如度分布、聚类系数、网络直径、模块化等.研究表明,可视图法可为交通流时间序列映射到网络提供有效途径,并且不同状态下交通流时间序列构建的复杂网络的模块化、聚类系数和度分布等统计特征呈现一定的变化规律,为交通流运行态势的研究提供了可视化的分析角度.     

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.     

Traffic Flow States in a Freeway with Bottleneck

The system of mixture of single lane and double lane is studied by a cellular automata model, which is developed by us based on the Nagel and Schreckenberg's models. We justify that the model can reach a stable states quickly. The density distributions of the stable state is presented for several cases, which illustrate the manner of the congestion. The relationship between the outflow rate and the total number of vehicles and that between the outflow rate and the density just before the bottleneck are both given. Comparing with the relationship that occurring in the granular flow, we conclude that the transition from the free traffic flow to the congested traffic flow can also be attributed to the abrupt variation through unstable flow state, which can naturally explain the discontinuities and the complex time variation behavior observed in the traffic flow experiments.     

考虑动态车间距的一维元胞自动机交通流模型

基于NaSch元胞自动机交通流模型, 考虑司机复杂的性格特征和驾驶行为差异, 引入相邻车辆的动态车间距, 提出了一个改进的单车道元胞自动机交通流模型. 通过数值模拟得到了流量-密度关系, 在中高密度区域呈现出一种弥散分布的状态而非惟一确定的关系, 再现了交通系统中的自由流、同步流及宽幅运动阻塞, 表明道路上即使没有交通瓶颈也会出现同步流和拥挤交通, 同时揭示了在同步流中存在的车辆高速跟驰现象, 高速跟驰率与交通实测结果较为符合.     

虚拟网络行为对互联网整体特性的影响

虚拟网络是一种依赖Internet基础设施所提供的传输能力，但又具有独立拓扑结构和信息传递规则的应用层网络行为逻辑网络.提出了耦合虚拟网络行为与物理节点的抽象模型，对一类典型的虚拟网络逻辑拓扑给互联网整体特性带来的影响进行了分析.研究表明在虚拟网络作用下，节点数据包排队长度存在相变特性，但相变临界点比对规则网络发生了明显左移，网络性能相对恶化.当数据包注入速率小于相变临界速率时，节点数据包排队长度不相关或短程相关；在接近临界速率处，节点数据包排队长度长程相关，幂指数H增大，网络获得更强的长程相关性.同时，在注入速率大于或等于临界速率时，虚拟网络行为使网络呈现出一致的长程相关特性.     

基于多尺度熵的交通流复杂性分析

交通流演化复杂性的研究有助于深刻理解交通系统的内在演化规律,为交通流的预测和控制提供理论依据.多尺度熵方法在生理时间序列和计算机网络流量的分析中得到了广泛的应用.考虑到交通流中的车辆到达和计算机网络中的分组到达具有类似特性,本文以刹车灯模型的车头时距为分析对象,利用多尺度熵方法来分析交通流演化的复杂性.分析结果表明:1)车头时距的复杂性随着时间尺度的增加而降低,反映了交通流的短时间难预测性;2)当时间尺度较小时,车头时距复杂性在自由流时和同步流时差异不大,但是,随着时间尺度的增加,自由流时车头时距的熵值迅速下降,而同步流时车头时距的熵值下降较慢.这一特性对于识别自由流中是否产生了同步流有非常重要的参考价值.本文的研究可以为揭示交通流演化的复杂性提供新的思路和方法.     

复杂交通运输网络上的拥挤与效率问题研究

本文研究复杂交通运输网络上的拥挤与效率问题. 在无标度网络、随机网络以及小世界网络等不同拓扑结构中, 探讨了不同的能力分配方式和不同的OD (Origin-Destination) 交通需求分布对网络拥挤度和效率的影响. 随着平均交通需求的增加, 分析无标度网络、随机网络以及小世界网络从自由流状态到交通拥堵状态的变化规律. 为便于比较, 本文侧重研究网络拥挤度的倒数, 并将其定义为通畅度. 研究发现网络中的通畅度与效率之间存在线性相关关系, 并且不同网络中的线性比例系数 (或斜率)是不同的, 从而体现了不同网络具有不同的运输性能. 关键词： 复杂网络 拥挤 效率     

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

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

Network traffic behaviour near phase transition point

We explore packet traffic dynamics in a data network model near phase transition point from free flow to congestion. The model of data network is an abstraction of the Network Layer of the OSI (Open Systems Interconnect) Reference Model of packet switching networks. The Network Layer is responsible for routing packets across the network from their sources to their destinations and for control of congestion in data networks. Using the model we investigate spatio-temporal packets traffic dynamics near the phase transition point for various network connection topologies, and static and adaptive routing algorithms. We present selected simulation results and analyze them.     

公交车停靠诱发交通瓶颈的元胞自动机模拟

利用双车道元胞自动机模型,研究公交车停靠对道路混合交通流的影响.针对港湾式和非港湾式两种不同公交车站设置,在开放边界下模拟了公交车停靠所产生的交通瓶颈问题,给出了车辆入流概率-公交车比例相平面上的相图,区分了自由流相和拥挤相,研究了相图各区中公交车站附近的平均密度和速度分布图,比较了两种公交车站情况下的道路交通流的动力学特征.研究发现,当公交车比例较小时,与非港湾式车站相比,港湾式车站可以显著改善车站处的交通状况. 关键词： 元胞自动机 混合交通流 交通瓶颈 公交车站     

Optimal traffic networks topology: A complex networks perspective

We investigate and analyse an optimal traffic network structure for resisting traffic congestion with different volumes of traffic. For this aim, we introduce a cost function and user-equilibrium assignment (UE) which ensures the flow balance on traffic systems. Our finding is that an optimal network is strongly dependent on the total system flow. And the random network is most desirable when the system flow is small. But for the larger volume of traffic, the network with power-law degree distribution is the optimal one. Further study indicates, for scale-free networks, that the degree distribution exponent has large effects on the congestion of traffic network. Therefore, the volume of traffic and characteristic of network determine the optimal network structure so as to minimize the side-effect produced by traffic congestion.     

Phase transition in evolution of traffic flow with scale-free property

This paper investigates the behaviour of traffic flow in traffic systems with a new model based on the NaSch model and cluster approximation of mean-field theory. The proposed model aims at constructing a mapping relationship between the microcosmic behaviour and the macroscopic property of traffic flow. Results demonstrate that scale-free phenomenon of the evolution network becomes obvious when the density value of traffic flow reaches at the critical point of phase transition from free flow to traffic congestion, and jamming is limited in this scale-free structure.     

基于复杂网络理论的多元混合空管技术保障系统网络特征分析

为提高空管技术保障系统应对突发事件的能力,本文以空管技术保障系统导航、通信、监视设备覆盖的航路结构为基础,构建系统对应的空间网络模型.提出从灵活性、鲁棒性、高效性三个方面度量空管技术保障系统网络特性,对北京、上海、广州、昆明、沈阳、兰州飞行情报区的空管技术保障系统网络的平均度、度分布、度-度相关性、聚集系数、平均路径长度、直径等进行分析.分析结果显示,各飞行情报区空管技术保障系统的平均聚集系数在0.25—0.39之间,网络聚集程度偏低;网络平均路径长度为3.4,表现出小世界网络特征;度值3时服从幂律分布,度-度分布不表现出正相关或负相关.对网络进行基于度优先的和随机的抗毁性测度,空管技术保障系统网络抗毁性较差,网络的可靠性由少数核心节点决定,应对核心节点进行目标免疫,提高网络的抗毁性.这些规律为空管技术保障系统能力提升、新建扩建提供理论依据,对降低突发事件对空管系统保障能力的影响,保障空中交通持续安全具有现实意义.