ISSN 1000-1239 CN 11-1777/TP

• Paper • Previous Articles     Next Articles

A δ-Degree-Based Clustering Algorithm in MANET

Zhao Chunxiao1,2 and Wang Guangxing1   

  1. 1(School of Information Science & Engineering, Northeastern University, Shenyang 110004) 2(School of Information Science & Engineering, Bohai University, Jinzh ou 121000)
  • Online:2005-05-15

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.

Key words: mobile ad hoc network, maximum independent set, clustering, δ-degree