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

发布时间：2018-06-29 22:09

本文选题：无线网络 + 支配集　；参考：《曲阜师范大学》2017年硕士论文

【摘要】：随着无线技术的不断进步,无线网络可以广泛地应用于各种领域,如军事,医疗,环境等。然而,无线网络的缺点限制了网络的性能,造成能量浪费、信息冗余等。解决这些问题的高效的技术是拓扑控制。连通支配集是无线网络中拓扑控制的代表性技术,它方便了许多工作的实现,如广播,路由,数据采集等。本文通过对现有连通支配集的分析与研究,在SINR(Signal-to-Interference-plus-Noise-Ratio)模型下研究了CDS的构造算法。近年来,大多数的工作使用简单的基于图或者基于距离的干扰模型,来研究CDS构造问题。对此,很少有文章的研究模型为物理干扰模型(SINR模型)。SINR模型是一个考虑到累积干扰的模型,且接近现实的自然环境。本文共分为五章。第1章说明了本文研究的背景以及现状。第2章对现存的连通支配集工作进行了总结,并分析了其中经典的构造算法。第3章给出了SINR模型下构建自稳定的连通支配集算法(DS_CDS-1),该算法将网络中的节点划分在不同的网格中,它包括两个阶段,第一阶段形成MIS,第二阶段,MIS中的节点通过寻找相邻方格中的邻居节点,连通得到CDS,最后证明该CDS可以得到常数性能的近似因子且是自稳定的。第3章的算法并没有考虑连通支配集的优化因子,为了近一步地解决构建SINR模型中的连通支配集问题,第4章给出了SINR模型下自稳定且限制直径的连通支配集构造算法(DS_CDS-2),该算法和第3章中的算法相比,缩小了CDS可得到的常数性能的近似因子,并减小了时间复杂度,且可以证明CDS的直径所满足的上界。第4章分析SINR约束时,做了相应的假设简化SINR模型,以便于分析与计算。为了进一步地优化算法的真实性,在第5章中我们再一次设计了SINR模型中自稳定的分布式CDS构造算法(DS_CDS-3),我们继续关注CDS的两个重要的性能指标,密度以及CDS的直径,并取得了相应的研究成果。据我们所知,这是实际SINR模型下,对于分布式CDS构造算法的密度和直径渐近地最优的自稳定结果。第6章总结了全文,并展望了未来的进一步研究。
[Abstract]:With the development of wireless technology, wireless network can be widely used in various fields, such as military, medical, environment and so on. However, the shortcomings of wireless networks limit the network performance, resulting in energy waste, information redundancy and so on. The efficient technique to solve these problems is topology control. Connected dominating set is the representative technology of topology control in wireless network. It facilitates the implementation of many work, such as broadcast, routing, data acquisition and so on. Based on the analysis and study of the existing connected dominating sets, the construction algorithm of CDS is studied under the SINR (Signal-to-Interference-plus-Noise-Ratio) model. In recent years, most of the work uses simple graph-based or distance-based interference models to study the construction of CDS. For this reason, few research models are physical interference model (SINR model). SINR model is a model which takes into account cumulative disturbance and is close to the real environment. This paper is divided into five chapters. Chapter 1 explains the background and present situation of this paper. In chapter 2, the existing work of connected dominating set is summarized, and the classical construction algorithm is analyzed. In chapter 3, the algorithm of constructing a self-stable connected dominating set (DSSP CDS-1) under the SINR model is presented. The algorithm divides the nodes in the network into different meshes, and it includes two stages. In the first stage, MISS is formed, and in the second stage, the nodes in MIS are connected to obtain the CDS by finding the neighbor nodes in the adjacent squares. Finally, it is proved that the CDS can obtain the approximate factor of constant performance and is self-stable. In chapter 3, the algorithm does not consider the optimization factor of the connected dominating set. In order to solve the problem of constructing the connected dominating set in the SINR model, In chapter 4, we present a self-stable and diameter-limiting connected dominating set construction algorithm (DSSCS-2) in the SINR model. Compared with the algorithm in Chapter 3, this algorithm reduces the approximate factor of the constant performance of the CDS and reduces the time complexity. The upper bound of the diameter of CDS can be proved. In chapter 4, when analyzing the SINR constraint, the corresponding assumptions are made to simplify the SINR model for easy analysis and calculation. In order to further optimize the authenticity of the algorithm, in Chapter 5, we once again design a self-stable distributed CDS construction algorithm (DSSCS-3) in the SINR model. We continue to pay attention to the two important performance indicators of CDS, density and diameter of CDS. And obtained the corresponding research result. As far as we know, this is the asymptotically optimal self-stability result for the density and diameter of the distributed CDS construction algorithm under the actual SINR model. Chapter 6 summarizes the full text and looks forward to further research in the future.
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN92

【相似文献】