The Internet of Vehicles is a new Intelligent Transportation System paradigm and a promising solution to improve conventional Vehicular Ad-hoc NETworks (VANETs) performances. It has received a great deal of attention in recent years, from many researchers. For this reason, several control mechanisms have been proposed for these networks to confront their challenges, such as dynamic topology and the scalability problem due to the high mobility of vehicles and the high number of connected vehicles, respectively. As an important mechanism used in a VANET, clustering has significantly improved the performance in numerous applications. In this regard, the present work proposes a new Multi-hop Clustering Approach over Vehicle-to-Internet called MCA-V2I to improve VANETs performance. MCA-V2I is based on the reasonable assumption that a vehicle can connect to the Internet via a special infrastructure called a Road Side Unit Gateway. Once connected to the Internet, each vehicle can obtain and share the necessary information about its Multi-hop neighbors to perform the clustering process. This latter is performed using a Breadth-first search (BFS) algorithm for traversing a graph based on a Mobility Rate that is calculated according to mobility metrics. MCA-V2I strengthens clusters stability through the selection of a Slave Cluster Head in addition to the Master Cluster Head. We evaluate the performances of the proposed scheme using network simulator NS-2 and the VanetMobiSim integrated environment.