复杂网络交通过程的动态特性研究 - 非线性科学及复杂系统研究中心.ppt

复杂网络上交通过程的动态特性研究 凌翔 2012年3月10日 复杂网络上交通过程的动态特性研究 研究背景 基于局部信息的网络交通路由策略研究 基于全局信息的网络交通路由策略研究 网络交通迟滞现象研究 交通资源优化配置研究 网络资源有限情况下的路由策略研究 总结及展望 1.1 网络交通堵塞 如今某些网络系统的规模越来越大(如因特网、城市道路网)，这些网络系统中会出现一系列的问题，最典型的就是网络交通堵塞问题。 解决这些网络系统中出现的堵塞问题 ： (1).增加线路带宽、新修道路及拓宽道路等等 (2).这些网络系统抽象成复杂网络模型，基于些 复杂网络模型： (a).探索适应这些网络模型的新路由策略 (b).优化网络交通资源 1.2 几种常见的网络模型 小世界网络模型 （Watts ， Strogatz ） 虽然网络规模很大，但是网络中节点之间的距离却往往很短。 无标度网络模型 （Barabási，Albert ） 存在着少量的超级节点，其连边数目（度）非常的巨大，而其它的大部分节点中的连边数目非常的少。 1.3 小世界网络模型(WS模型) 给定一个节点总数为N，每个节点与它最近邻的4个节点相连接的一个一维规则网。 对于每条连边，以概率p进行随机重连边操作：连边的一个节点保持不变，随机选取另外一个节点进行重连边。重连边操作必须满足如下条件：两个节点之间最多只能有一条连边，而且每个节点都不能与自身相连接。 1.4 改进的小世界模型 (NW模型) 给定一个节点总数为N，每个节点与它最近邻的4个节点相连接的一个一维规则网。 对于规则网络中的个节点，以概率p选择任意两个不同节点，并在这两个节点之间加上连边，在该网络模型中不改变网络原始的连边，并且两个节点之间最多只能有一条连边，而且每个节点都不能与自身相连接。 1.5 无标度网络模型 (BA模型) 开始给定 个初始节点，该 个节点可以是孤立的，也可以是全连通的，一般情况我们给定个节点为全连通的。 每个时间步有一个具有 条边的新节点加入到网络中， 。每个增加的新节点连接到已有节点的概率正比例于节点的度： 时间步之后，网络中节点数目为 ，连边数为 。当演化时间足够大时，网络节点的度分布为：。 网络中的度分布, , 。 2 基于局部信息的网络交通路由策略研究 局部信息: 指的是网络中每个节点只能获知周围一定范围邻居的信息。局域信息可能是其邻居节点数目、邻居节点中信息包排队长度及邻居节点的度等等。而整个网络的拓扑结构，每个节点中的信息包排队长度等是无法获知的。 信息包: 真实网络系统中传输或移动的介质和信息，如互联网中的数据包，城市道路网络中的汽车以及航空网络中的飞机等抽象成网络模型中的移动单元 ，统称为“信息包”。 2.1 局部信息路由策略简介 2006年Wang（王文旭）等人提出了基于局部拓扑信息的路由策略，称之为静态局部路由策略。 Wen-Xu Wang, Bing-Hong Wang, Chuan-Yang Yin, et al. “Traffic dynamics based on local routing protocol on a scale-free network” Physical Review E, 73, 026111(2006). 2.2 静态局部路由策略规则 在每个时间步，系统中有R个信息包产生，每个信息包的产生源点和要传送到的目的地节点都是随机选择的。为了把信息包传送到目的地节点，每个节点对其邻居节点进行局部有哪些信誉好的足球投注网站。如果在有哪些信誉好的足球投注网站范围内发现了信息包的目的地节点，则该信息包将被直接传送至目的地节点；否则，就以如下概率传送到一个邻居节点去： 每个节点的信息包处理能力为C(C=1)。排在每个节点的等待发送的信息包队列都是按照先进先出(first in first out，FIFO)的规则按次序发出，如果信息包到达了目的地节点，则该信息包将从网络中移出。 在BA网络中，当信息包使用不同可调参数 的静态局部路由传输时，序参量 随信息包产生率R的变化情况， BA网络：N=1000,k=10,C=10 。 2.3 信息素路由策略 蚁群信息素简介 ： 信息素是一个生物概念，蚂蚁在觅食的过程中会在行走的路径上留下一种化学物质。信息素的作用主要是为后续的蚂蚁提供导航作用，每一个蚂蚁在其行走的路径上留下信息素，并且路径上的信息素浓度和该路径经过的蚂蚁数量成正比，但由于蚁群的信息素具有挥发作用，留在路径上的信息素浓度会随时间逐渐减小。著名