Abstract:

Using the clustering algorithm to reduce the network churn effect and extend the network lifetime is one of the research emphasis points of mobile peer-to-peer networks. Based on studying the Kautz graph and its characteristics, a clustering algorithm of mobile peer-to-peer network based on the Kautz graph is proposed. In the algorithm, an address space tree is defined firstly, and then the Kautz string is used as nodes’ identifier. The breadth-first-search via post-order is used to travel a well-defined address tree for clusters creation. Besides, the mechanism for management and maintenance of cluster structure is designed to ensure the structural integrity. Theoretical proof and experimental evaluation show that the clustering algorithm can effectively reduce the churn effect and extend the network lifetime.

Key words: Kautz graph;clustering algorithm;mobile peer-to-peer network