基于SINR模型无线网络连通支配集构造算法的研究

摘要

随着无线技术的不断进步，无线网络可以广泛地应用于各种领域，如军事，医疗，环境等。然而，无线网络的缺点限制了网络的性能，造成能量浪费、信息冗余等。解决这些问题的高效的技术是拓扑控制。连通支配集是无线网络中拓扑控制的代表性技术，它方便了许多工作的实现，如广播，路由，数据采集等。通过对现有连通支配集的分析与研究，在 SINR(Signal-to-Interference-plus-Noise-Ratio)模型下研究了CDS的构造算法。近年来，大多数的工作使用简单的基于图或者基于距离的干扰模型，来研究CDS构造问题。对此，很少有文章的研究模型为物理干扰模型（SINR模型）。SINR模型是一个考虑到累积干扰的模型，且接近现实的自然环境。
　　本研究分为五个部分：第一章阐述了研究的背景以及现状。第二章对现存的连通支配集工作进行了总结，并分析了其中经典的构造算法。第三章给出了SINR模型下构建自稳定的连通支配集算法（DS_CDS-1），该算法将网络中的节点划分在不同的网格中，它包括两个阶段，第一阶段形成MIS，第二阶段，MIS中的节点通过寻找相邻方格中的邻居节点，连通得到CDS，最后证明该CDS可以得到常数性能的近似因子且是自稳定的。第3章的算法并没有考虑连通支配集的优化因子，为了近一步地解决构建SINR模型中的连通支配集问题，第4章给出了 SINR模型下自稳定且限制直径的连通支配集构造算法（DS_CDS-2），该算法和第3章中的算法相比，缩小了CDS可得到的常数性能的近似因子，并减小了时间复杂度，且可以证明CDS的直径所满足的上界。第四章分析SINR约束时，做了相应的假设简化SINR模型，以便于分析与计算。第五章设计了 SINR模型中自稳定的分布式 CDS构造算法（DS_CDS-3），继续关注CDS的两个重要的性能指标，密度以及CDS的直径，并取得了相应的研究成果。据我们所知，这是实际SINR模型下，对于分布式CDS构造算法的密度和直径渐近地最优的自稳定结果。第6章总结了全文，并展望了未来的进一步研究。

目录

声明

第1章 绪论

1.1 研究背景与意义

1.2 国内外研究现状

1.3 论文的组织结构

第2章 CDS算法概述

2.1 引言

2.2 集中式CDS构造算法

2.3 分布式CDS构造算法

2.4 其他通信机制的算法

2.5 基于SINR模型的CDS构造算法

2.6 自稳定CDS构造算法

2.7 限制直径的CDS构造算法

2.8 本章小结

第3章 SINR模型下的DS_CDS-1算法

3.1 引言

3.2 模型与定义

3.3 算法DS_CDS-1及其理论分析

3.4 本章小结

第4章 SINR模型下的DS_CDS-2算法

4.1 引言

4.2 模型与定义

4.3 DS_MIS-2算法及其理论分析

4.4 DS_CDS-2算法及其理论分析

4.5 本章小结

第5章 SINR模型下的DS_CDS-3算法

5.1 引言

5.2 模型与定义

5.3 DS_DS算法及理论分析

5.4 DS_CDS-3算法及理论分析

5.5 本章小结

第6章 总结与展望

6.1 总结

6.2 展望

参考文献

在校期间发表的学术论文

致谢