复杂网络上的路由策略及结构性质对其的影响

发布时间：2019-03-17 20:55

【摘要】：当前环境下,复杂性科学是一个研究的重点。基于理想条件或是单个粒子的理论已经无法满足现代科学技术的研究和应用。所以,复杂网络的研究是一个重要的方向。复杂网络是一种具有极大规模节点数和边数的图,是现实中复杂系统的异质性的一种抽象描述。复杂网络的研究,就是研究网络的各种性质,如度分布、聚类系数、介数等对网络上的动力学,如传播,路由,扩散等的影响。本文选择对网络上的传输过程以及路由策略进行研究。研究网络上的数据包传递的路由策略与网络结构性质的关系。本文首先给网络上的数据包传递建立了一个数学模型并进行解析,得到了描述传输过程的参数,如节点的平均队列长度L,包的平均传输时间T,以及传输能力Rc的关系。我们证明了网络传输能力的上界被RcGκ,其中C是每个节点每时间步处理的包数,κ是平均度。我们的结果同样可以用最短路径路由的介数来描述。接下来,我们提出了一种双随机路由策略,这个策略只需要局域信息以及一些简单通信就可以实现。通过模拟,我们发现相比较一般的局域信息静态路由,双随机路由可以提升传输能力Rc,但是并不是对所有网络都成立。最后,我们就双随机路由策略的数学本质,构造双随机矩阵的迭代过程展开讨论。从网络中图形结构的角度,我们发现当图形h个互不相连的节点只和另外9个节点相连(hg)不存在时,这个迭代过程收敛。当这种图形存在时,迭代不收敛。这种图形的存在性和两个因素有关,1.网络度分布的高阶矩的收敛性。2.网络中度为1的节点存在概率。模拟结果支持这个理论,并且,我们从理论上证明了,对BA网络当平均度为8时有一个相变。
[Abstract]:In the current environment, complexity science is the focus of research. The theory based on ideal condition or single particle can no longer satisfy the research and application of modern science and technology. Therefore, the study of complex networks is an important direction. Complex network is a graph with a large number of nodes and edges. It is an abstract description of the heterogeneity of complex systems in reality. The research of complex network is to study the influence of various properties of network, such as degree distribution, clustering coefficient, mesoscopic number, on the dynamics of network, such as propagation, routing, diffusion and so on. This paper chooses to study the transmission process and routing strategy on the network. In this paper, we study the relationship between the routing strategy of packet delivery and the nature of network structure. In this paper, a mathematical model for packet transmission over the network is established and analyzed, and the parameters describing the transmission process, such as the average queue length L of the node, the average transmission time T of the packet, and the transmission capacity Rc, are obtained. We prove that the upper bound of the transmission capacity of the network is RcG 魏, where C is the number of packets processed per time step per node, and 魏 is the average degree. Our results can also be described by the intermediate number of shortest path routes. Next, we propose a two-random routing strategy, which can be implemented only by local information and some simple communication. By simulation, we find that compared with the general local information static routing, dual random routing can improve the transmission capacity of Rc, but not all networks. Finally, we discuss the mathematical nature of the double random routing strategy and the iterative process of constructing the double random matrix. From the point of view of the graph structure in the network, we find that the iterative process converges when the graph h independent nodes are only connected to the other 9 nodes (hg) does not exist. When such a pattern exists, the iteration does not converge. The existence of this graph is related to two factors. Convergence of higher order moments of network degree distribution. 2. The probability of the existence of a node with a moderate degree of 1 in the network. The simulation results support this theory, and we prove theoretically that there is a phase transition for the BA network when the average degree is 8.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【共引文献】