无标度网络上的紧凑路由研究
文献类型：学位论文
| 作者 | 唐明董 |
| 答辩日期 | 2010-01-13 |
| 文献子类 | 博士 |
| 授予单位 | 中国科学院研究生院 |
| 授予地点 | 北京 |
| 导师 | 杨景 |
| 关键词 | 无标度网络 紧凑路由 路由表规模 拉伸系数 地标 树覆盖 图嵌入 |
| 学位专业 | 其它专业 |
| 英文摘要 | 目前针对一般性网络的通用紧凑路由研究已经取得了很多成果。然而，通用的紧凑路由算法在真实网络上并不一定是最优的，因为它们没有考虑实际网络的拓扑特征。近年来的诸多研究表明，世界上很多真实网络都是无标度网络，即节点度分布满足幂律。针对无标度网络的特定紧凑路由研究还未受到足够重视。本文针对无标度网络上的紧凑路由问题进行了研究，取得了以下的研究成果。 （1）提出了一系列基于最大度地标的紧凑路由策略——HDLR、HDLR+、NIHDLR+。在随机幂律图上分析发现， 上述策略具有比通用的紧凑路由策略更优的基本扩展性，即在路由表大小、拉伸系数和包首部长度等指标上具有更优的界限，填补了这方面的理论研究空白。仿真试验验证了上述的分析结果。 （2）提出了基于稀疏树覆盖（sparse tree cover）的路由策略。基于无标度网络上可以由少数子树来覆盖大多数节点之间的较短路径这一事实，将网络路由转换成少数树上的路由，从而大大缩减路由表信息。 （3）提出了基于贪心嵌入（greedy embedding）的路由策略。为了构造贪心嵌入同时保证良好的路由效率，提出了基于网络骨架嵌入的思想。在无标度网络上，将源于最大度节点的生成树看成是网络的骨架，通过对骨架树标记来构造网络的贪心嵌入。利用无标度网络的小世界特征，该策略能够将各项路由指标限制在合理的范围内。而在幂律图上仿真发现，该策略在主要路由指标上具有很高的平均性能。 |
| 学科主题 | 计算机应用 |
| 语种 | 中文 |
| 公开日期 | 2010-01-19 |
| 源URL | [http://ictir.ict.ac.cn/handle/311040/97]  |
| 专题 | 中国科学院计算技术研究所学位论文_2010博士 |
| 推荐引用方式 GB/T 7714 | 唐明董. 无标度网络上的紧凑路由研究[D]. 北京. 中国科学院研究生院. 2010. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。