Internet of Vehicles (IoV) is an evolution of the Internet of Things (IoT) to improve the capabilities of vehicular ad-hoc networks (VANETs) in intelligence transport systems. The network topology in IoV paradigm is highly dynamic. Clustering is one of the promising solutions to maintain the route stability in the dynamic network. However, existing algorithms consume a considerable amount of time in the cluster head (CH) selection process. Thus, this study proposes a mobility aware dynamic clustering-based routing (MADCR) protocol in IoV to maximize the lifespan of networks and reduce the end-to-end delay of vehicles. The MADCR protocol consists of cluster formation and CH selection processes. A cluster is formed on the basis of Euclidean distance. The CH is then chosen using the mayfly optimization algorithm (MOA). The CH subsequently receives vehicle data and forwards such data to the Road Side Unit (RSU). The performance of the MADCR protocol is compared with that of Ant Colony Optimization (ACO), Comprehensive Learning Particle Swarm Optimization (CLPSO), and Clustering Algorithm for Internet of Vehicles based on Dragonfly Optimizer (CAVDO). The proposed MADCR protocol decreases the end-to-end delay by 5-80 ms and increases the packet delivery ratio by 5%-15%.