三维覆盖控制及其在无线ad hoc网络中的应用研究-research on 3d coverage control and its application in wireless ad hoc network.docxVIP

摘要顶点覆盖问题是图论中的经典组合优化问题。已被证明是 NP 完备的，具有较高 的计算复杂性。本文主要研究无权图与加权图的最大独立集，目的是为了求解最小加 权顶点覆盖。论文主要研究工作和成果包括以下几个方面：首先，对无权图的顶点覆盖和独立集进行了深入研究，在基于两者关系的基础上， 得出结论，即在无权图中，对于任意一个顶点判断属于独立集比顶点覆盖简单。接着， 在邻接矩阵与独立集自身特性的基础上，设计了一种基于邻接矩阵求解最大独立集的 算法，进而解决最小顶点覆盖。通过实验验证算法的时间复杂度和正确性。其次，利用上述求解无权图的方法，同样从邻接矩阵与独立集自身特性入手，对 加权图进行分析，并结合改进传统的贪婪算法，提出两个概念集合，即邻接集合和非 邻接集合，设计一种基于贪婪算法求解最大加权独立集，进而求解最小加权顶点覆盖。 同样通过实验验证算法的正确性和可行性。最后，文中对最大加权独立集在无线 Ad hoc 网络分簇算法方面的应用进行了研 究。通过实验，将最大加权独立集算法和目前应用较为广泛的最小 ID 和最大节点的 分簇算法分别对同一幅系统拓扑图进行求解，根据三种不同的结果图，说明本文算法 的可行性与优越性。实验结果表明本文的算法可以达到解决簇首选择问题，从而改善 网络中分级结构的最优服务质量问题。 关键词：顶点覆盖问题；独立集问题；贪婪算法；分簇算法AbstractThe vertex cover problem is a classical problem in combinatorial optimization. It has been proved to be a NP-complete problem with high complexity of computation. In this paper the independent set problem of unweighted and weighted graphs are studied to solve the weighted vertex cover problem. The research work and achievements of thesis include the following:Firstly, the unweighted vertex cover problem and independent set problem are deeply studied, and based on the relationship between vertex cover problem and independent set problem we draw a conclusion that any vertex is judged in an independent set is more simple than in a vertex cover set in unweigthed graph. Then, we design an algorithm based on adjacency matrix to solve the maximum independent set problem and then to solve the vertex cover problem, which according to the analysis of the adjacency matrix and independent set own characteristics. The time complexity and correctness of algorithm are verified by experiment.Secondly, we analyze the weighted graph using the obove method of solving unweighted graph, which according to the analysis of the adjacency matrix and independent set own characteristics. Then, two concept sets that are adjacency set and non-adjacency set, are proposed by combining with the improved traditional greedy algorithm, thereby we design a algorithm to solve the maximum weighted independent set problem ba