随机行走在路由探测中的应用 指导教师 ： 王林 教授 1212班姓名：李发 学号：12081005781 研究背景与意义背景：作为研究复杂性科学和复杂系统的有力工具，复杂网络已成为学术界研究的一个热点，它在工程技术、社会、政治、医药、经济、管理领域都有着潜在、广泛的应用。随机行走作为网络动力学过程的一种最基本形式，对于揭示网络动力学过程的普遍规律具有重要的意义。除此之外，利用随机行走的方法还以快速有效的发现网络社团结构，探索目标节点和未知路径，控制网络上的数据传输，因此在学术领域得到了广泛的关注和研究。意义：人类已经进入信息时代，保证信息迅速可靠的传输对我们具有重要的意义。目前，一般可以通过两个方面提高网络传输能力，即优化网络的拓扑结构和设计最佳路由策略。由于更改已知网络的拓扑结构比较困难，因此，人们主要致力于寻找合适的路由策略方面。传统的最短路径路由策略（SR）虽然所用传输时间短、效率高，但实际中，无标度网络节点度的异构性导致介数的强异构性，使得高介数的节点处经常发生阻塞。因此，人们急需一种适应范围更加广泛的合适的路由策略。2 国内外研究进展 国际上的网络中的随机行走最早可以追溯到1905年，当年爱因斯坦发表了五篇学术论文，除了著名的狭义相对论、光电效应之外，还有一篇题为关于热的分子运动论所要求的静止液体中悬浮小粒子的运动的文章，主要研究了布朗运动的规律，后来研究者们将这种形式的运动称为随机行走。虽然对网络中的随机行走的研究已经将近有一个世纪的历史了，但是它在工程技术上的广泛应用则是最近二三十年的事情。 我国对随机行走的研究相对晚一些，主要研究领域主要集中在以下方面：随机行走和电路网络的联系；组合数学方法使得随机行走的研究有了更大的进步；对若干特殊类型图的谱分析深化了随机行走的理论；调和分析理论在随机行走问题中的应用。由于随机行走是一个分析网络资源、发现网络结构、探索未知路径、控制数据传播的有力工具，因此将随机行走理论应用到具体实例中去，是研究者们近几年的主要研究任务。3 目前网络上的路由策略主要有以下几种： 1. 最短路由策略（SR），这是现在网络上普遍采用的一种路由策略，数据包在源节点和目的节点之间的最短路径传输，速度快、效率高。然而这种路由策略在网络规模较小、传输数据量不大的情况下比较有效，当网络规模较大、数据流量较大时，随着无标度网络异构性的体现，在高介数的节点处容易发生严重的网络阻塞，降低数据的传输速率。 2.局域信息路由策略（LR），数据包根据各自邻居节点的局部信息以的概率随机选择选择下一步路由。我们推导出，在节点处理能力相同的情况下，当a=-1时，网络的负载分布最为均匀，整体传输能力达到最大。 3.有效路由策略（ER），已知源节点i和目标节点j，该路由策略通过最小化代价函数选择路由路径 pij ，在节点处理能力相同的情况下，=1时，该策略有效的把网络负载从核心节点转移到边缘节点。较多的利用了网络中度较小的节点，在传输平均路径长度仍符合网络特征的基础上，相比于最短路径法将网络的传输能力提高了十倍以上。4 根据以上三种基本的路由策略，人们又提出了其它几种路由算法。 一类方法采用诸如节点队列长度信息、节点信息等其它动态信息替换基础路由策略中节点度的信息。 另一类方法则根据邻居节点度、队列长度、全局拓扑结构和邻居节点排队等待时间等网络中各类静态或动态信息自适用调整路由策略。 还有一类方法通过极值优化方法获得最优路由策略。例如，通过更改网络中边的权值以降低网络中最大介数值的最优路径优化策略，以及规避网络中最大介数节点以找到次最短路径的路由策略。5 本文主要研究内容 本文将随机行走理论应用到网络的路径发现中去，提出了一种基于随机行走的路由探测方法，主要工作有以下方面：1.研究复杂网络的基础知识，重点分析网络拓扑的基本模型和常用的搜索策略。2.研究随机行走的经典理论，如布朗粒子的首达时间、首达概率、平均首达时间、位置概率分布、便宜距离、给定时间内的访问节点数量、覆盖时间等内容。3.将随机行走理论应用到网络中的路径发现中，提出一种基于随机行走的路由探测策略。4.仿真并测试该策略的可行性和可靠性。6 在对随机行走的研究过程中发现，单个粒子通过某条特定路径的时间正比于该路径上所有节点度的连乘积，在此基础上，以基于随机行走理论的优化路由策略为基础，通过调节可变参数，提出一种最佳路由策略（IR）。通过比较不同路由策略条件下，平均路由介数中心度、网络的临界负载量、平均路径长度以及平均搜索信息量等性能指标，表明此路由策略在保证网络平均路径长度较少增加的前提下，使网络的传输能力获得最大幅度的提升。7这三幅图表示的是平均路由介数中心度g(k)与节点度k的关系。图1显示，在最短路径策略中， g(k)- K1.7。图2显示，在有效路由策略下，g(k)-k曲线近似呈泊松分布，在k=15附近达到峰值。图3显示，优化路由策略下， g(k)-k曲线呈现线性关系。8 此图表示的是不同控制参数条件下，优化路由策略时的平均路由介数中心度与节点度的关系。可以看出，当=1.8和2.0时，g(k)的整体幅值小于=1.4和1.6时的整体幅值，说明当1.6时，各个节点的网络负载较小，进一步比较=1.8和=2.0时，有效路由策略下的g(k)可以发现，当k20时，只有=1.8时的g(k)的曲线下降较为缓慢，我们可以得知，当=1.8时，网络传输能力最强。9这是三种路由策略的-R曲线，其中，R为单位时间内节点接受数据包的值，W为网络上总的负载量。 这三种路由策略下，网络的临界负载量分别为28、433、522，平均路径长度分别为3.59、5.43、4.71。比较发现，优化路由策略在较小增加平均路径长度的前提下，大幅度的提高了网络的临界负载量。10左图表示的是改进路由策略的最大介数中心度与网络规模呈幂律关系：gmaxN，IR=1.2，在另外两种路由策略下，SR=2.0，ER=1.3，改进路由策略的最大介数中心值始终小于另外两个策略的对应值。右图显示，随着网络平均节点度的增加，改进路由策略所对应的RC始终优于最短路由策略和有效路由策略。11左图表示的是平均搜索信息量与网络规模的关系（网络平均节点度=6），右图表示的是平均搜索信息量与网络平均度的关系（网络节点数N=1500）。比较可知，改进路由策略的平均搜索信息量始终小于其它两个策略。12 研究方案和技术路线1.研究采用随机行走的方式探索未知路径 在复杂系统中，通过随机行走发现未知路径的现象是常见的。由于网络中的数据传输实际上就是数据包从源节点到目标节点的路由探测，因此考虑将随机行走的理论应用到路由探测中去。布朗粒子在网络上行走的时间越长，它发现指定路径的概率就越大，再者，布朗粒子所处的环境越简单，寻找指定路径就越容易。尽管不知道什么时候能找到指定路径，但只要它不停地在网络上随机行走，就一定会找到。与传统的跳数最少的最短路径相比，随机行走最短路径的不确定性最小，或者说信道容量最大，这点对于网络上的信息传输具有重要的意义。 既然是随机行走，就有不确定性，在此计算通过随机行走方式发现指定路径的概率，使用的数学技巧主要是迭代方法和生成函数。由于涉及到位置参数，所以此过程分为两步，首先在特殊情况下求解，得出未知参数，然后再利用第一步的结果，计算在一般情况下的路径发现概率。132.找出最优路径 既然布朗粒子是通过随机行走的方式来探索路径，那么它探索的是哪条路径呢？ 一方面，从统计物理的角度来看。设布朗粒子从源节点s出发，要探索的路径为其中路径的起点为u=0，终点为v=l，通过下式可以计算出布朗粒子发现路径C的平均首达时间：其中k(i)为节点i的度，m为网络上边的总数，j是矩阵Q=D-1/2PD1/2的特征值，j是相应的特征向量，这里P是布朗粒子的概率转移矩阵，D=diag(k(1),.k(n)是对角阵。 从上面的公式可以看出，第一项的大小主要是由除终点之外的所有节点的节点度的连乘积决定。因此，在源节点和目标节点之间的所有路径中，我们要寻找一条使得连乘积最小的路径，布朗粒子发现这条路径的所用的平均首达时间也是最短的，所用的能量也就最少。把这个结论应用到网络中的负载传输过程中，则这条节点度连乘积最小的路径即是从源节点到目标节点之间的最优路径。14 另一方面，从信息论的角度来看，一条路径搜索信息为 也就是说，节点度的连乘积越大，相应路径上的搜索信息越多，不确定性因素越多，越不利于布朗粒子从该路径上通过，反之，节点度的连乘积越小，则该路径上的不确定性因素越少，越有利于布朗粒子从该路径上通过。因此在源节点和目标节点的所有路径中，节点度连乘积最小的路径才是布朗运动意义下的最优路径。 由以上两个方面可知，我们要找的这条最优路径是从源节点到目标节点之间的所有路径中，节点度连乘积最小的路径。153.给出算法、编写程序、仿真测试 研究并给出用随机行走的方式探索最优路径的算法，编写程序，并在多种网络模型上进行仿真、测试，验证此方案的可行性。16 课题的主要难点及拟采取解决方案主要难点1.针对不同网络模型挑选出合适的随机行走方式。2.基于随机行走的路由探测算法的提出与改进。3.程序的编写与调试。解决方案1.认真研究不同的网络模型的结构和性质，分析几种经典的随机行走方式各自的优缺点并进行改进。2.仔细研究随机行走的经典算法，结合路由探测方法，在此基础上进行改性。3.认真学习C+语言和Matlab语言，多研究前人类似的程序，和同学们进行讨论分析并请教老师。17 预期研究成果该路由探测方法将具有以下优点：1.有效均衡网络上的负载，避免对核心节点的充分依赖，大大减少甚至消除网络拥塞。2.大幅度提高网络的整体承受能力，从而有效提高网络的抗饱和攻击的能力。3.随着网络规模和节点平均度的增加，路径长度趋于基于最短路径路由策略的路径长度，从而在网络规模较大的情况下保证数据的快速传输。18进度安排1、2013年08月-2013年12月：查阅资料，了解本行业的 研究现状，写出开题报告，进行开题答辩。2、2014年01月-2014年5月：在前期的基础上，进行基于 随机行走的路由探测方法的研究，并且进行 设计建模，获取相关的数据。3、2014年06月-2014年10月：在前期的基础上，对于在 系统模型基础上得到的数据进行整理，并且进行数据的 验真仿真，得到相应的结论。4、2014年11月-2014年12月：撰写毕业论文和准备预答辩。19谢谢观看，欢迎点评！20