| Node clustering is a technique to mitigate the topology changes in mobile ad hoc networks (MANETs). It stabilizes the end-to-end communication paths and maximizes the path lifetime. It also improves the network scalability such that the routing overhead does not become tremendous in large-scale ad hoc networks. Its effectiveness, however, depends largely on the cluster stability which is measured by the lifetime of the cluster heads and the membership time of the cluster members. The existing clustering algorithms do not achieve this objective well. In this paper, we show that the cluster stability is fundamentally related to the mobility and the energy status of the nodes in the network and propose a new clustering algorithm using the node mobility and energy information. Our new algorithm maximizes the cluster stability by choosing the low mobility and high energy nodes to be the cluster heads and by keeping the constructed clusters unchanged to the extent of their maximum possible lifetime. In addition, the proposed clustering algorithm performs equally well in large-scale ad hoc networks as in the small ones. We also show that it is a near-optimal clustering algorithm. |