AdHoc传感器网络中连通支配集算法的研究

发布时间：2018-06-11 10:26

本文选题：Ad + Hoc传感器网络　；参考：《天津工业大学》2016年硕士论文

【摘要】：Ad Hoc传感器网络是一种具有大规模性、自组织性、无基础设施支持等特点的网络,能够应用于各个领域,具有重要的现实意义。该网络利用连通支配集作为虚拟网络骨干,以此来进行数据聚合和网络节点通信,实现网络的广播和路由。本文针对在Ad Hoc传感器网络中构建最小连通支配集进行了如下研究,通过分析现有算法,得出目前效果较好的求解连通支配集的方法是基于二阶段的方法,因此本文针对其求解过程的两个阶段提出了三种改进的算法。针对第一阶段——求解MIS(极大独立集)阶段,本文分析了现有的基于协同覆盖的最小连通支配集算法。该类算法的协同覆盖思想虽然可以使问题接近最优解,但也降低了覆盖效率。本文对此进行改进,采用新的支配点选择方案,优先从当前支配节点的三跳邻居中选择下一个支配节点,如果不存在,则从当前支配节点的两跳邻居中选择下一个支配节点,使覆盖尽可能少的存在交集,增大覆盖效率。针对第二阶段——斯坦纳树构建阶段,多数算法均采用贪心方式寻找斯坦纳节点,该类算法简单但容易陷入局部最优解。本文对此进行改进,在斯坦纳节点的选择上了进行了相应的权值处理同时加入了检测处理阶段,即检测是否存在冗余的节点。提出了两种改进的斯坦纳树构建算法——IK-ST算法和ML-ST算法。进一步降低了支配集的规模。仿真实验中,首先对比了IC-MIS算法和Rajiv Misra提出的算法,通过比较所求得的MIS的节点数目来衡量算法的优劣,接着通过IK-ST和ML-ST算法优化Rajiv Misra算法的斯坦纳树构建阶段,然后与其进行比较,通过比较得到的斯坦纳节点数目来衡量算法的优劣。结果显示本文提出的算法较先前的算法在优化支配集规模上有了很大的改善。
[Abstract]:Ad Hoc sensor network is a kind of large-scale, self-organization, no infrastructure support and other characteristics of the network, can be used in various fields, has important practical significance. The network uses the connected dominating set as the backbone of the virtual network to aggregate the data and communicate with the network nodes to realize the broadcast and routing of the network. In this paper, the minimum connected dominating set in Ad Hoc sensor networks is studied as follows. By analyzing the existing algorithms, it is concluded that the most effective method to solve the connected dominating set is based on the two-stage method. Therefore, this paper proposes three improved algorithms for the two stages of the solution process. In this paper, we analyze the existing least connected dominating set algorithms based on cooperative covering for the first stage-solving MISS (maximal Independent set). The co-covering idea of this kind of algorithm can make the problem close to the optimal solution, but it also reduces the coverage efficiency. In this paper, a new dominating point selection scheme is adopted to select the next dominating node from the three-hop neighbor of the current dominant node, and if it does not exist, the next dominating node is selected from the two-hop neighbor of the current dominating node. Make the cover as little as possible exist intersection, increase coverage efficiency. In the second stage of Stener tree construction, most of the algorithms are greedy to find the Steiner node, which is simple but easy to fall into the local optimal solution. In this paper, the corresponding weights are processed on the selection of Steiner nodes, and the detection processing stage is added, that is, to detect the redundant nodes. Two improved Steiner tree construction algorithms, IK-ST algorithm and ML-ST algorithm, are proposed. The size of dominating set is further reduced. In the simulation experiment, the IC-MIS algorithm and the algorithm proposed by Rajiv Misra are compared at first. The advantages and disadvantages of the algorithm are measured by comparing the number of nodes in the obtained MIS. Then, the Stener tree construction phase of Rajiv Misra algorithm is optimized by IK-ST and ML-ST algorithms. Then compared with the algorithm, the algorithm is evaluated by comparing the number of Stener nodes. The results show that the proposed algorithm is much better than the previous algorithm in optimizing the size of dominating set.
【学位授予单位】：天津工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP212.9;TN929.5

【相似文献】