一种基于结点聚类的网络定位算法

论文摘要

大规模的网络服务应用系统已经在全世界的范围内得到运行和使用,例如:P2P文件共享系统、覆盖网络多播系统以及内容分发服务系统。这些大规模的网络应用系统能够从一些性能较好的路由选择算法以及邻居结点选择算法中获益。这是因为延迟和带宽等网络性能参数与大规模网络应用密切相关,测量这些网络性能参数值将对这些算法性能的提高有帮助。然而,在真实的网络环境下,由于大规模网络应用存在数量巨大的端到端连接,如果对每一个连接都进行测量,则会带来巨大的物理开销和时间消耗。为了解决这个问题,可以通过一定的算法来预测端到端的网络距离,而不用在真实的网络环境里进行测量,这样可以极大的减小网络开销。当前已经出现了一些网络定位算法来预测网络结点间的距离,在这些算法当中已经证明了网络坐标是简单并且实用的。网络坐标能够表示出网络中某个主机的位置,并且从某种意义上来说,还能够表示网络的拓扑结构。本文提出了一种基于结点聚类的网络定位算法——Dumpling算法。该算法包括了两个核心机制:结点聚类机制和整体坐标移动机制。Dumpling算法致力于在更短的时间内对虚拟坐标空间中的误差进行收敛;在更少的显式测量内收敛更多的系统误差;尽量避免虚拟坐标系统的波动现象给带来的定位精度的影响。除了从理论上分析了Dumpling的优势外,本论文还经过仿真实验表明,Dumpling可以较好的达到上述三个目标,并且在最后的Dumpling整体性能测试中,表明Dumpling在真实的网络拓扑下,也能达到一定的效果。Dumpling是一个分布式的虚拟网络坐标定位系统,具有计算量少、通信开销低等优势,还能够与具体应用程序相结合。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景与意义
• 1.2 网络定位技术研究现状
• 1.3 本论文的研究思路和结构
• 第2章 相关工作
• 2.1 引言
• 2.2 网络坐标基本原理
• 2.3 两种基于虚拟坐标的网络定位算法
• 2.3.1 全局网络定位系统
• 2.3.2 Vivladi: 一种分布式的网络坐标系统
• 2.4 一种基于网络距离的结点聚类算法
• 2.5 小结
• 第3章 问题描述和 DUMPLING 算法基本思想
• 3.1 引言
• 3.2 问题描述
• 3.3 Dumpling 算法基础
• 3.4 一个简单版本的 Dumpling 算法
• 3.5 小结
• 第4章 一种基于网络距离的结点聚类机制
• 4.1 引言
• 4.2 聚类信息的基本数据结构
• 4.3 结点聚类初始阶段
• 4.4 结点聚类调整阶段
• b 为一个聚类中的普通结点'>4.4.1 若n_b为一个聚类中的普通结点
• b 为一个聚类中的根结点'>4.4.2 若n_b为一个聚类中的根结点
• 4.5 CLE、MC 和LA 的聚类性能仿真实验
• 4.5.1 数据集和仿真软件
• 4.5.2 仿真实验评判标准
• 4.5.3 仿真结果分析
• 4.6 小结
• 第5章 整体坐标移动机制
• 5.1 引言
• 5.2 地理位置无关整体坐标移动方式
• 5.3 地理位置感知整体坐标移动方式
• 5.4 整体坐标移动机制的仿真实验和结果分析
• 5.4.1 数据集
• 5.4.2 实验评判标准
• 5.4.3 仿真实验设置
• 5.4.4 仿真实验结果与分析
• 5.5 Dumpling 整体仿真实验
• 5.6 小结
• 本文工作总结及进一步工作
• 参考文献
• 致谢
• 附录A（攻读硕士学位期间所发表的学术论文目录）
• 附录B 攻读硕士学位期间所参与的项目