论文题目: 基于随机图理论的负载分配研究
论文类型: 博士论文
论文专业: 计算机应用
作者: 郭敬林
导师: 陈平
关键词: 负载分配,随机图,软件重用,可信
文献来源: 西安电子科技大学
发表年度: 2005
论文摘要: 负载分配属于分布式系统的资源管理模块,其功能是合理调配系统资源以优化系统性能。负载分配一般是个NP完全问题,采用随机方法处理此类问题具有实用价值。本文工作集中在基于随机图理论建模balls-and-bins问题,通过谱系化该问题以研究负载分配过程的统计特征,重点关注负载方差在各种随机图中的变化,同时,为随机化的负载分配算法的可信软件重用提供理论依据。本文主要包含四个内容:(1)采用泊松分布随机图研究多选范型顶点间的关系。通过有向随机图研究多选范型中负载的方差,并利用随机图生成过程拓展了经典的多选范型,给出了多选强度d在1<d<2时的物理意义;(2)利用随机二分图建模ALWAYS-GO-LEFT算法,研究了在分组的两部分不对称情况下,负载方差的变化规律;(3)将balls-and-bins问题结构化,给出具有Small World现象随机图中,balls-and-bins问题的统计特性;(4)给出利用Small World现象改善负载平衡算法的方法。
论文目录:
摘 要
ABSTRACT
第一章 绪论
1.1 研究背景
1.2 选题依据
1.3 工作思路
1.4 工作切入点的选取
1.5 主要研究内容及创新点
1.6 本章小结
第二章 负载分配及相关工作分析
2.1 负载分配
2.1.1 负载分配简述及关键要素分析
2.1.2 负载分配算法介绍及分析
2.2 复杂网络与随机图
2.3 随机图简介
2.3.1 随机图的基本概念
2.3.2 经典的ER随机图
2.3.3 SCALE FREE随机图
2.3.4 “SMALL-WORLD”现象与SMALL WORLD随机图
2.3.5 任意度随机图
2.3.6 有向随机图
2.3.7 随机二分图
2.3.8 随机图的阈值
2.3.9 随机图过程
2.4 复杂网络的相关研究
2.5 随机图在计算机领域的应用
2.5.1 信息扩散
2.5.2 拓扑结构
2.5.3 系统健壮性分析
2.5.4 其它类型应用
2.6 BALLS AND BINS问题
2.6.1 单选范型
2.6.2 多选范型
2.6.3 ALWAYS GO LEFT模型
2.6.4 其它关于BALLS AND BINS的工作
2.6.5 进一步分析BALLS AND BINS
2.7 研究方法说明
2.8 本章小结
第三章 基于随机图的BALLS AND BINS分析
3.1 基于随机图的BALLS AND BINS建模
3.1.1 多选范型建模
3.1.2 ALWAYS GO LEFT过程建模
3.1.3 建模过程的进一步说明
3.2 多选范型分析
3.2.1 多选范型仿真分析思路
3.2.2 多选范型所确定随机图
3.2.3 多选范型仿真
3.2.4 多选范型仿真结果说明
3.2.5 多选范型进一步讨论
3.3 ALWAYS GO LEFT分析及仿真
3.3.1 ALWAYS GO LEFT分组不对称性
3.3.2 ALWAYS GO LEFT仿真
3.3.3 ALWAYS GO LEFT度数特征
3.3.4 ALWAYS GO LEFT进一步讨论
3.4 多选范型（D=2）和标准ALWAYS GO LEFT过程的异同
3.5 多选范型的选筐和放球策略
3.6 本章小节
第四章 多选范型拓展
4.1 拓展多选范型的意义
4.1.1 单选范型和多选范型混合的示例
4.1.2 单选范型和多选范型性质分析
4.2 多选范型1< d < 2 过程建模
4.3 1< d < 2 过程微分方程模型
4.4 1< d < 2 过程的仿真
4.5 1< d < 2 过程的性质分析
4.6 对1< d < 2 过程的进一步讨论
4.7 本章小节
第五章 “SMALL-WORLD”现象与负载分配
5.1 结构化BALLS AND BINS分析
5.2 环型结构的BALLS AND BINS
5.2.1 问题起源
5.2.2 环型结构BALLS AND BINS分析
5.3 SMALL WORLD结构的BALLS AND BINS
5.3.1 SMALL WORLD结构与环型结构的异同
5.3.2 SMALL WORLD结构BALLS AND BINS
5.4 与D=1+P过程的对比
5.5 改进SMALL WORLD结构的BALLS AND BINS
5.6 其它结构的BALLS AND BINS
5.6.1 ER随机图结构BALLS AND BINS
5.6.2 树型结构BALLS AND BINS
5.7 本章小节
第六章 利用“SMALL-WORLD”现象实现负载平衡
6.1 无集中节点的BALLS AND BINS问题
6.2 “SMALL-WORLD”现象与负载平衡关系
6.2.1 实例分析
6.2.2 “SMALL-WORLD”现象促进负载平衡的原因
6.3 “SMALL-WORLD”与拓扑结构
6.3.1 拓扑结构生成
6.3.2 拓扑结构的健壮性分析
6.4 利用“SMALL-WORLD”现象实现负载平衡
6.4.1 SMALL WORLD随机图上的最近邻居算法
6.4.2 ER随机图上的直接方法
6.5 层次化随机图与负载分配的关系
6.5.1 层次化随机图的生成
6.5.2 层次化随机图上的负载分配
6.6 本章小节
第七章 负载分配随机算法重用分析
7.1 随机算法和可信软件重用
7.2 BALLS AND BINS的应用讨论
7.2.1 传感器网络简介
7.2.2 聚类首领选举策略
7.2.3 聚类首领选举策略仿真
7.2.4 内存分配应用
7.2.5 BFSDM详细设计
7.2.6 BALLS AND BINS内存分配算法
7.2.7 关于BALLS AND BINS内存分配算法实现的简单说明
7.3 BALLS AND BINS的应用总结
7.4 BALLS AND BINS与排队模型
7.5 其它和随机图有关的负载分配模型
7.6 本章小节
第八章 总结及未来工作展望
致谢
参考文献
博士期间的学术论文及科研成果
发布时间: 2006-12-29
相关论文
- [1].独立马氏链边随机图过程与随机分枝树研究[D]. 于娜.上海大学2012
- [2].基于随机图演化与图上随机游动的复杂网络研究[D]. 郑中团.上海大学2009
- [3].随机图中若干矩阵的谱性质[D]. 丁雪.吉林大学2010
- [4].随机图及对个体系统的一致性问题[D]. 尚轶伦.上海交通大学2010
- [5].多类型随机图形生成方法及应用研究[D]. 莫灿林.浙江大学2004
- [6].动力系统与复杂网络：理论与应用[D]. 卢文联.复旦大学2005
- [7].高可信软件可靠性和防危性测试与评价理论研究[D]. 覃志东.电子科技大学2005
- [8].基于逻辑的程序验证方法在高可信软件开发上的应用[D]. 项森.中国科学技术大学2006
- [9].有向无标度图与二项随机图图因子[D]. 颜云志.上海大学2007
- [10].基于小世界和随机图理论的多QoS路由算法研究[D]. 冯杰.大连理工大学2007