无标度网络信息传输研究现状综述

菜单

现代社会中与人们日常生活密切相关的互联网、电话网、万维网等都是具有无标度特性的大型通信网络。随着网络节点规模和用户数的不断增加，网络信息拥堵问题也日益突出。因此，如何有效地减轻网络拥塞问题已成为学术界研究的热点。目前在通信网络中使用的路由协议，例如OSPF、ISIS、RIP等都是以最短路径算法为核心思想来选择路径的。虽然这些协议在网络规模较小时能够较好地运作，但是在网络规模较大并且结构动态变化的情况下需要维护大量的拓扑结构数据来计算最短路径，网络路由表会出现振荡、长时间收敛等问题。复杂网络理论为大规模网络信息拥塞问题的解决提供了新的思路。64529

信息传输是通信网络最基本的功能之一。在网络负载有限的条件下，大量实时并发的信息传输极易导致网络通信性能下降，并最终导致网络信息传输拥塞。Arenas等人提出了一种信息拥塞模型，并给出了关于网络吞吐量的一种度量----信息包临界生成率。该临界值是网络信息流从自由流通状态到拥塞状态的相变点。在该信息拥塞模型基础上，学术界展开了在无标度网络容量方面的研究。该类研究分别从网络拓扑结构、网络资源和信息路由策略三个方面入手。论文网

网络拓扑结构方面的研究显示，在最短路由条件下，网络中节点度分布越均匀，网络容量越大；删除网络中部分核心节点之间的连边，可以使得一部分最短路径避开网络核心节点，从而能减轻网络拥塞；删除网络中节点介数较大的节点之间的一部分连边能提高网络的信息容量；删除差异度指标值最大的节点和它的节点度最大的邻居节点之间的连边，也能提高网络的信息容量；删除网络中易拥塞的边，网络容量会有明显的增大；另外，对节点度相关与网络容量关系的研究表明，正相关和负相关都能降低网络核心节点的负载，提高中等度值节点的负载，从而提高网络的整体容量；在最短路径算法传递信息条件下，聚类系数越大信息传输能力越弱。即使考虑网络结构演化和信息负载动态变化等因素，网络信息传输性能仍与聚类系数强相关。

在网络资源方面的研究发现，在网络存在信息拥塞的条件下，利用容量较小的边反而能更快的传输信息；Ling等人在目标节点分布非均匀条件下的研究发现，在最短路径条件下网络容量与网络的平均度无关，并且在局部路由条件下网络容量随着网络的平均度增加而增大；在节点处理能力与网络容量关系的研究表明，在网络拓扑结构和路由策略给定的条件下，通过适当分配节点的处理能力网络能够达到信息容量极值，该极值与网络平均路径长度成反比；对网络带宽与信息传输的关系研究表明，在网络带宽较低的条件下节点处理能力相同和节点处理能力等于节点度这两种情况对应的路由最佳参数相同；在对目标节点分布非均匀条件下的信息传输的研究发现，得到在最短路径条件下网络容量与网络的平均度无关，而在局部路由条件下网络容量随着网络的平均度增加而增大。

信息路由策略方面的研究又分为基于网络全局信息的全局路由、基于网络局部信息的局部路由和基于网络结构信息和负载信息的动态路由三个方面。全局路由包括最短路径路由、有效路由以及优化介数等等。此类研究主要通过最小化某种代价函数，例如路径节点的度数和、网络最大介数等来选择信息流传输的最佳路径的。局部路由包括随机行走、一阶邻居搜索、二阶邻居搜索等等。动态路由则是通过在一定时间间隙里不断更新的路由信息来适应不断变化的网络，并即时获得最优的路径。