分布式最大独立集算法及其在无线传感网络中的应用研究

发布时间：2018-05-25 09:48

本文选题：分布式MIS算法 + 传感器网络　；参考：《河南理工大学》2014年硕士论文

【摘要】：最大独立集(Maximum Independent Set,MIS)问题是图论中的经典组合优化问题,是NP完备的。分布式环境(如:传感器网络)中的MIS算法的优化对分布式系统的效率和稳定性都有重要意义。最近,Afek等人从生物发育机制中获得启发,提出了一种具有线性时间复杂性、空间复杂性的分布式MIS算法(Science2011)。但是,如何将Afek-MIS算法应用到传感器网络中,特别是在物理干扰(Signal-to-Interference-Plus-Noise-Ratio,SINR)模型下对该算法的分析和改进仍是一个亟待解决的问题。本文在传感器网络SINR模型下对Afek-MIS算法进行分析和改进。通过理论分析得出MIS算法节点度数受SINR模型下路径损耗指数和信噪比值的约束,推导出相应的公式。利用NetLogo和Matlab软件进行仿真和分析得出:当路径损耗指数、信噪比的值越小,节点度数越大,MIS算法运行时间越短;当路径损耗指数、信噪比的值越大,节点度数越小,MIS算法运行时间越长。即路径损耗指数、信噪比与节点度数成反比,与MIS算法运行时间成正比。同时,节点度数较小时,网络分布较松散,节点连接不紧密,MIS算法运行时间较长;随着节点度数的增大,节点彼此之间连接更紧密,MIS算法运行时间就越快。本文研究促进了Afek-MIS算法在分布式传感器网络中的应用。
[Abstract]:The Maximum Independent Set (MIS) problem is a classic combinatorial optimization problem in graph theory. It is NP complete. The optimization of MIS algorithm in distributed environment (such as sensor network) is of great significance to the efficiency and stability of distributed systems. Recently, Afek and others have obtained inspiration from the mechanism of biological development. The distributed MIS algorithm (Science2011) with linear time complexity and spatial complexity. However, how to apply Afek-MIS algorithm to the sensor network, especially in the Signal-to-Interference-Plus-Noise-Ratio (SINR) model, is still an urgent problem to be solved. In this paper, the sensor network SI The Afek-MIS algorithm is analyzed and improved under the NR model. Through the theoretical analysis, it is concluded that the node degree of the MIS algorithm is constrained by the path loss index and the signal to noise ratio under the SINR model. The corresponding formulas are derived from the NetLogo and Matlab software. The smaller the value of the path loss index, the smaller the signal to noise ratio, the greater the node degree, M The shorter running time of IS algorithm; the greater the path loss index, the greater the value of the signal-to-noise ratio, the smaller the node degree, the longer the running time of the MIS algorithm. That is, the path loss index, the signal to noise ratio is inversely proportional to the node degree, and is proportional to the running time of the MIS algorithm. At the same time, the node degree is smaller, the network distribution is looser, the node connection is not close, MIS algorithm runs when the node is loose. As the node degree increases, the nodes connect more closely to each other, the faster the MIS algorithm runs. This study promotes the application of the Afek-MIS algorithm in the distributed sensor network.
【学位授予单位】：河南理工大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：O157.5;TP212.9;TN929.5

【相似文献】