新型无线网络组邻居发现算法的研究

论文摘要

无线网络在21世纪取得了巨大的成功。基于集中式控制架构的蜂窝网与WiFi网已经深入我们的生活,无线自组织网络因其自组织与自维护特性也得到广泛的应用。应用的普及推动着低功耗与高容量技术的发展,反过来也推动着无线网络的发展。新型网络形态初见端倪,占空比无线传感器网络、多包接收无线自组织网络是其中的典型。本文研究新型无线自组织网络中的组邻居发现问题。邻居发现是大规模自组织网络不可或缺的操作,可以为后续的操作,比如路由协议与移动社交应用,提供必需的信息。我们研究两类新的自组织网络运行模式：占空比模式与多包接收模式。在占空比模式中,节点在工作与睡眠状态间不断切换以节省能量；在多包接收模式中,节点可以一次接收多个同时发送的数据包。这些特性给邻居发现带来了机会与挑战。占空比模式下一次成功传输不代表能被邻居节点所发现,多包接收模式下允许并行的邻居发现。针对这些特性,我们提出了几种随机算法,并利用渐进分析与概率分析工具研究这些算法的性能。在占空比无线网络中,我们证明邻居发现时间以很大概率为O(n ln ln lnn),与全工作模式相比,运行时间相差O(ln ln n)。在多包接收网络中,我们证明邻居发现的紧确下界是(?)(n/k),并提出了两种算法,分别以很大概率达到Θ (n In n/κ)与(?)(n/k)。这些理论结果扩展了我们对邻居发现在各种无线网络运行效果的认识。所提出的方法也适用于其他网络类型的分析。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 无线网络现状
• 1.1.2 无线网络发展趋势
• 1.1.3 新型无线网络简介
• 1.2 研究内容
• 1.2.1 研究问题
• 1.2.2 研究意义
• 1.2.3 研究方法
• 1.2.4 主要贡献
• 1.3 论文组织
• 第二章 相关工作
• 2.1 确定接入邻居发现协议
• 2.2 随机接入邻居发现协议
• 2.3 基于跨层的邻居发现协议
• 2.4 组邻居发现算法
• 2.4.1 时间分析
• 2.4.2 相关分布式算法
• 第三章 占空比网络邻居发现
• 3.1 占空比新型网络简介
• 3.2 模型与假设
• 3.2.1 问题定义
• 3.3 算法设计与分析
• 3.3.1 想网络模型
• 3.3.2 实际网络模型
• 3.4 仿真实验
• 3.4.1 仿真设置
• 3.4.2 仿真结果
• 3.5 小结
• 第四章 多包接收网络邻居发现
• 4.1 多包接收新型网络简介
• 4.2 模型与假设
• 4.2.1 问题定义
• 4.3 算法设计与分析
• 4.3.1 紧确下界分析
• 4.3.2 算法MPR4
• 4.3.3 算法MPR5
• 4.4 仿真实验
• 4.5 小结
• 第五章 结束语
• 参考文献
• 简历与科研成果
• 致谢