The need for an effective clustering algorithm for Vehicular Ad Hoc Networks (VANETs) is motivated by the recent research in cluster-based MAC and routing schemes. VANETs are highly dynamic and have harsh channel conditions, thus a suitable clustering algorithm must be robust to channel error and must consider node mobility during cluster formation. This work presents a novel, mobility-based clustering scheme for Vehicular Ad hoc Networks, which forms clusters using the Affinity Propagation algorithm in a distributed manner. This proposed algorithm considers node mobility during cluster formation and produces clusters with high stability. Cluster performance was measured in terms of average clusterhead duration, average cluster member duration, average rate of clusterhead change, and average number of clusters. The proposed algorithm is also robust to channel error and exhibits reasonable overhead. Simulation results confirm the superior performance, when compared to other mobility-based clustering techniques