高级检索
    赵春晓, 王光兴. 一种δ-度约束的自组网成簇算法[J]. 计算机研究与发展, 2005, 42(5): 818-822.
    引用本文: 赵春晓, 王光兴. 一种δ-度约束的自组网成簇算法[J]. 计算机研究与发展, 2005, 42(5): 818-822.
    Zhao Chunxiao, Wang Guangxing. A δ-Degree-Based Clustering Algorithm in MANET[J]. Journal of Computer Research and Development, 2005, 42(5): 818-822.
    Citation: Zhao Chunxiao, Wang Guangxing. A δ-Degree-Based Clustering Algorithm in MANET[J]. Journal of Computer Research and Development, 2005, 42(5): 818-822.

    一种δ-度约束的自组网成簇算法

    A δ-Degree-Based Clustering Algorithm in MANET

    • 摘要: 简单地描述了自组网的特点,分析了不相交簇、重叠簇和混合簇,对相关工作进行了比较. 为了保持拓扑稳定,提出了一个基于时间因素的δ-度定义.在此基础上,提出了一个基于δ- 度约束的混合簇的成簇策略(δ-DHCA).混合簇的成簇问题可以归结为找一个最大独立集问题 ,而找一个最大独立集问题是一个著名的NP-难问题.提出了一个近似解法,给出了算法的正 确性证明.解析性能评价和仿真结果均表明,该方法的性能优于最高节点度成簇算法HD和最 低标识符成簇算法LCC.

       

      Abstract: Describing briefly the characteristics of mobile ad hoc networks and analyzing the disjoint, overlapping and hybrid clustering, the related works are compared. Because HD clustering considered only node degree as clustering standard and thi s has caused frequently cluster head change, a reconfiguration of the system is often unavoidable. To keep the topology stable, a new definition of δ-degree is given in view of the highly dynamic topology and absence of any fixed infrastru cture in MANET. According to δ-degree definition, δ-degree sequence stabilize relatively fairly and steady cluster structure is produced. Analyzing the link r elationship between two adjacent nodes, an ad hoc network model is set up. A hyb rid clustering algorithm(δ-DHCA) is therefore proposed on the basis of δ-degre e. The hybrid clustering can be reduced to find a maximum independent set (MIS) problem, but this is a well-known NP-hard problem and the proposed scheme is an approximate algorithm based on polynomial time. The correctness of the algorithm is proved. Analytical and simulation results show that δ-DHCA outperforms LCC and HD clustering algorithms.

       

    /

    返回文章
    返回