A δ-Degree-Based Clustering Algorithm in MANET

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.