复杂网络上的拥塞分析与控制问题研究

摘要

20世纪末以来,对复杂网络系统的研究开始更多关注数量众多、连接结构复杂的实际网络的统计特性及其上发生的动态过程。拥塞现象是发生在通信网络和交通网络等复杂网络上的一种典型的动态行为。拥塞与搜索及路由优化策略互相影响、密切相关。和以前的研究不同之处在于,基于复杂网络理论的拥塞、搜索及路由策略的研究更为关注网络的结构特性对网络的拥塞、搜索及路由优化策略的影响,比如是否可以利用网络的局部或者全局拓扑特性来提高搜索以及路由策略的有效性、路由策略是否会导致网络拓扑结构发生变化从而反过来影响算法的效率、如何设计对网络拓扑结构变化具有自适应能力的路由策略以及局部优化策略对无标度网络结构的形成有何影响等。 本文的主要研究内容正是基于各种复杂网络模型,分析不同网络结构上拥塞产生的原因及其控制策略,并对网络结构和其上发生的动态行为之间的相互影响关系进行初步探讨,提出了改进的路由策略来提高网络的吞吐量以及传输性能等动态指标。本文的主要内容和研究成果总结如下: 1.基于Barabasi和Albert提出的无标度网络模型,按照节点在网络中的重要程度将其分类,并通过定义相应的动态过程及性能指标,研究了网络节点自身容量或者处理速度以及网络的无标度结构特性对拥塞的影响。 提出了相应的控制策略来改善网络的拥塞,发现控制策略是否有效和网络的拓扑结构紧密相关,相同的策略在不同网络结构中的作用会有明显不同。特别地,不需要对整个网络施加控制作用,而仅需要对一些最关键的节点加以控制,就可以得到类似控制所有节点所产生的控制效果。 2.提出了一种结合最短路径路由和局部拥塞检测的改进路由算法,并在具有可变聚类系数的无标度网络上进行了研究。研究结果表明可以得到一个最优参数使得该路由算法具有最好的性能,并且随着捌塞的加剧,最优参数值随之增加.和最短路径路由算法相比,该算法在拥塞加剧的情形下性能提升更加明显,但是最优参数值几乎不随聚类系数的变化而变化。 3.进一步研究了可以感知局部拥塞信息的路由算法在不同网络拓扑结构下的性能,发现在各种拓扑结构下,该路由算法均可以显著的提高网络吞吐量,并且路由算法的提高程度和网络的异质性有密切关系。 4. 研究了梯度网络中的拥塞问题。基于指数可调幂律随机网络,对由其得到的梯度网络模型的入度分布进行了研究,发现梯度网络的入度分布均为幂律的。当基础网络的幂律指数γ>2时,梯度网络的幂律指数和基础网络的几乎一致,而当γ≤2时,梯度网络的幂律指数小于基础网络的指数。其次,平均度的相变值к<,c>也与幂律指数γ相关,基础网络的幂律指数越小,其平均度的相变值也越大。特别地,当七,为有限值时,如果平均度〈к〉<к<,c>,那么较为异质的网络容易发生拥塞,而当平均度(к)>к<,c>之后,结论相反,较为同质的网络结构更容易发生拥塞。当平均度(к)→∞时,所有网络都将趋于最大拥塞状态。

目录

文摘

英文文摘

上海交通大学学位论文原创性声明及版权使用授权书

第一章绪论

§1.1引言

§1.2复杂网络基本概念

§1.2.1随机图理论概要

§1.2.2经典复杂网络模型

§1.3复杂网络上的拥塞、路由及其它动态过程研究进展

§1.3.1现实网络中的拥塞及路由概述

§1.3.2复杂网络上的拥塞问题研究

§1.3.3复杂网络上的路由及优化策略

§1.3.4其它动态过程

§1.4本文主要研究内容及意义

第二章BA无标度网络中的拥塞分析及控制

§2.1引言

§2.2网络模型及动态过程

§2.2.1网络模型及节点分类

§2.2.2动态过程及性能指标

§2.3控制策略及仿真分析

§2.3.1控制中心节点的容量或处理速度

§2.3.2控制关键节点的容量或处理速度

§2.4其它控制策略及与二维网格的比较

§2.5本章小结

第三章可调聚类系数的无标度网络中的拥塞分析及路由改进策略

§3.1引言

§3.2可调聚类系数的无标度网络模型

§3.3路由算法及动态过程

§3.3.1基本路由策略及其改进

§3.3.2动态过程及指标

§3.4仿真结果及分析

§3.5本章小结

第四章异质性不同的网络中的拥塞分析及路由改进策略

§4.1引言

§4.2网络结构的比较

§4.3路由算法及动态过程

§4.4仿真结果及分析

§4.5本章小结

第五章复杂梯度网络中的拥塞分析

§5.1引言

§5.2一种指数可调幂律网络模型

§5.3梯度网络模型

§5.3.1梯度网络的构造

§5.3.2解析结果及仿真

§5.4基于指数可调幂律网络的梯度网络入度分布研究

§5.5基于指数可调幂律网络的梯度网络的拥塞研究

§5.5.1平均度不变情形下拥塞和幂律指数的关系

§5.5.2平均度可变情形下拥塞和幂律指数的关系

§5.6本章小结

第六章总结与展望

§6.1全文总结

§6.2研究展望

参考文献

攻读博士学位期间发表的论文

致谢