【作者】 凌翔；

【导师】 吴清松； 胡茂彬；

【作者基本信息】 中国科学技术大学 ， 工程热物理， 2011， 博士

【摘要】 网络是节点和连边的集合。现实生活中存在着多种不同的网络,网络在人们的生活中发挥着重要的作用,如互联网、通讯网、道路交通网络等。这些网络系统都可以抽象成由许多相互作用的个体组成的网络模型,从真实网络系统中抽象出来的网络统称为复杂网络。复杂网络是研究复杂系统的一门新兴学科,近几年受到了国内外众多学者的广泛关注。如今,得到广泛研究的网络系统有:互联网、万维网、无线通讯网、城市道路网、航空网、电力网、科研合作网、蛋白质相互作用网等等。网络系统的研究不仅对人们的工作和生活至关重要,而且推动了统计物理、应用数学、非线性动力学、计算机科学、社会学和生物学等多学科的交叉。因此,复杂网络研究具有重大的理论价值。研究复杂网络的目的是为了了解各种真实网络的功能,而网络的功能可以通过研究网络上的动力学过程的特性来反映。其中交通动力学过程是复杂网络的一个重要研究课题。本文中,我们对复杂网络的交通动力学进行了系统的研究,包括了网络交通路由策略研究、网络交通迟滞现象研究、网络交通资源优化研究和交通资源有限时的优化路由策略研究。本文的主要工作如下。分别研究了基于局部信息的局部路由策略、基于全局信息的全局路由策略。在局部路由方面,我们根据蚁群的信息素原理,提出了信息素路由策略,和前人提出的局部路由策略相比,使用信息素路由策略,网络能达到更大的临界信息包产生率。在全局路由方面,我们提出了全局动态路由、联合路由和全局信息素路由。(I)全局动态路由:节点之间的路径是由路径上节点中的信息包排队长度决定的。和其它全局路由相比,全局动态路由能大大的提高网络的传输效率。(II)全局信息素路由:为了避免全局动态路由中不断更新路径列表的问题,我们探索出全局信息素路由策略。全局信息素路由属于静态路由,即两个不同节点之间的路径一旦确定,这两个节点之间所有的信息包将始终按照该路径进行传输。和全局动态路由相比,使用全局信息素路由时,网络临界信息包产生率相对略小,但是全局信息素路由避免了更新路径列表,因此节省了计算资源。(III)联合路由策略:在现实交通系统中,信息包或车辆在选择目的地都有一定的偏好性。根据这种情况,我们提出了适应目的地选择偏好性的联合路由策略,其基本思想是去不同目的地节点的信息包分别使用不同的路由策略进行传送,其结果使得网络的临界信息包产生率有了很大的提高。系统的研究了节点容量有限时,无标度网络、小世界网络和规则网络上出现的交通迟滞现象。我们发现在使用局部路由策略时,小世界网络和规则网络中出现迟滞现象的原因是由于节点处理能力有限,但在无标度网络中出现迟滞现象和节点处理能力没有关系。在使用全局路由策略时,无标度网络、小世界网络和规则网络上出现的迟滞现象和节点处理能力没有关系,即使节点处理能力无限大,迟滞现象同样会出现。探讨了网络交通资源的优化分配。分别研究了节点处理能力资源、连边带宽资源和节点容量资源的优化分配。发现这三种资源按节点(连边)的介数来分配是最优的,并且通过理论分析证明了,当节点处理能力资源按节点介数(连边带宽资源按连边介数)分配并且使用最短路径路由时,网络的临界信息包产生率能达到最大值。在前人提出的节点处理能力资源有限的优化路由策略的基础上,我们分别提出了连边带宽资源有限的优化路由策略,及节点容量资源有限的优化路由策略。在不同结构的网络上使用这两种优化路由策略,网络的临界信息包产生率及信息包流量比其它路由策略都要大很多。更多还原

【Abstract】 Networks are sets of vertices and edges. There are many kinds of networks in our world and daily life. Some networks play an important role in people’s lives, such as the Internet, the communications networks and urban traffic networks. Since the end of last century, complex networks have been considered as an important approach for describing and understanding complex systems.Complex network theory has been extensively researched by many researchers. Today, many networks have been widely studied, such as: the Internet, World Wide Web, wireless telecommunication networks, urban road networks, airline networks, power grids, research collaboration networks, protein-protein interaction networks, and so on. Study of these networks is not only crucial to people’s work and life, but also lead to the interdisciplinary development and interaction of statistical physics, applied mathematics, nonlinear dynamics, computer science, sociology, biology and other subjects.The purpose of studying complex networks is to understand the function of the real network system. The characteristics of traffic dynamic processes taking place on networks is a focus of network study. In this paper, we have systematically investigated the dynamics of information traffic on complex networks, including routing strategies, hysteresis phenomena, traffic resource allocation and the optimization routing under the condition of limited resources. The main work for this paper is as follows.Routing strategies based on local and/or global information. In the field of local routing strategy, we proposed a pheromone routing strategy which is based on the local link pheromone density. Comparing with other local strategy, using the pheromone strategy, the system can achieve a larger network capacity. In the field of global routing strategy, we proposed global dynamic routing strategy, global pheromone routing strategy and integrated routing strategy. (I) Global dynamic routing strategy: the path between source and destination is selected in the way that the sum of node queue lengths is minimal. Compared with other global routing strategy, the global dynamic routing can greatly improve the network’s transmission efficiency.(II)Global pheromone routing strategy: In the global routing strategy, because the node queue lengths change from time to time, it is computation consuming to update the global dynamic paths. To avoid this situation, we proposed the global pheromone routing strategy. Using the global pheromone routing strategy, the network capacity is slightly smaller than that of using the global dynamic routing strategy. But the global pheromone routing strategy can avoid path updating, so it can save a large amount of computing resources. (III) Integrated routing strategy: In real system, information packets or cars non-homogeneously select destinations. Inspired by this situation, we proposed an integrated routing strategy. In this routing strategy, the information packets or cars use different routing strategies for different destinations. The integrated routing strategy can greatly improve the network’s transmission efficiency.The dynamical hysteresis is investigated in constant-density traffic system of the scale-free networks, small-world networks, and lattice grids. With the local-searching strategy, hysteresis persists for the scale-free networks, while it disappears for small-world networks and lattice grids when the handling ability of nodes is higher than a certain threshold. With the global information strategy, hysteresis persists for all the three networks investigated.Optimal traffic resource allocation strategies are studied for complex network systems. The resources are the node’s total packet-delivering capacity, the link’s total bandwidth and node’s buffer. For each resource, the optimal allocation strategies depend on the node’s or link’s algorithmic betweenness. With the optimal resource allocation strategy, using the shortest path strategy, the network’s capacity can achieve the largest.We propose an optimization routing algorithm to improve the traffic flux where each node has a finite buffer and each link has a finite bandwidth. In different network structures, the system can reach a very high flux and the network’s capacity when using the optimized routing strategy.更多还原