基于随机行走理论的路由理论与技术研究

摘要

复杂网络理论作为复杂系统与复杂性科学研究的重要分支,其目标在于揭示蕴涵于现实网络关系中的普遍规律,并探索其在科学技术领域中的应用。现实网络中,WWW网、因特网、城市交通网等大规模网络对传输性能的要求越来越高,通常可以通过优化网络拓扑结构和设计优化路由策略来提高网络传输性能。本文围绕“基于随机行走的路由理论与技术”开展工作,具体研究内容和主要贡献如下:
　　 首先,本文分析了现实世界复杂网络的统计学特性、复杂网络演化模型及动力学机制等方面的研究进展,并介绍了本文所开展的主要研究工作。
　　 其次,本文对复杂网络进行了概述。其中详细描述了复杂网络研究中的重要概念,比如平均路径长度、聚类系数、度分布、度的相关性、介数、信息熵等。研究表明现实世界众多的网络并不是规则网络或者随机网络,它们拥有小世界、无标度等特性,基于这些概念,介绍了ER随机图模型、WS小世界模型、BA无标度模型以及无标度模型的扩展模型。
　　 接着,本文介绍了复杂网络负载传输优化策略。基于复杂网络传输模型,文章从优化网络路由策略和改进网络拓扑结构两方面介绍了优化网络负载传输的方法。传统的最短路径路由策略在大规模高流量的异构网络中显示出了劣势,改进的路由策略主要集中在基于网络全局信息、基于网络的局部信息以及基于网络的动态信息这三个方面。
　　 最后,本文介绍了基于随机行走的路由策略。首先基于复杂网络中的随机行走,本文通过在随机行走中研究搜索到特定路径的平均首达时间,提出了最小信息路径路由策略。接着详细介绍了泛化最小信息路由策略。该路由利用无标度网络的异构特性,通过在BA无标度网络模型中构造了一个基于节点度对数的指数和的代价函数,在节点处理能力均匀分布和节点处理能力与度成正比两种情况下,调节可变路由参数,最小化构造的代价函数,进而设计出一种基于搜索信息量的无标度网络路由策略。通过与传统路由策略比较,实验证实提出的泛化最小信息路由策略在保证网络平均路径长度较少增加的前提下,使网络的传输能力获得了较大幅度的提升。同时,本文也提出了一种综合路由策略,该路由策略可以在网络节点处理能力相同时,更为合理的分配网络负载,进一步提高网络的传输能力。