A variable degree based clustering algorithm for networks

Hierarchical routing is used to reduce routing update costs, and clustering algorithms partition networks into multilevel cluster structures. In hierarchical networks, routing performance is greatly affected by the sizes and structures of partitioned clusters. Two existing clustering algorithms are based on the concepts of the lowest ID and the maximum degree of nodes. In this paper, we present a new clustering algorithm based on the concept of the variable degree of nodes. Our new algorithm produces clusters with the low cluster variance in size, and the number of the clusters is close to the optimal value that leads to the smallest total routing table size. The performance of the algorithm is evaluated by using simulated ad hoc networks.