Vehicular Ad-hoc Networks are dynamic and temporary network of on-the-fly vehicles with contemporaneous connectivity. Such a network is suitable for a range of applications; starting with those concerning entertainment to improved traffic negotiation to those aimed at human safety and emergency assistance. By its very nature, such a network has higher node mobility, ever-changing topology, varying environmental conditions and error-prone communication links. Such constraints impose challenges on maintaining robust connectivity among nodes. Therefore, the solution lies in creation of such a mechanism that could enable an acceptable performance even in presence of transient disruptions due to link errors, transmission errors as well as failures of one or more links, routers or nodes. This is precisely what the present work tries to achieve. The principal component of this work is an efficient, adaptive and robust protocol that is capable of such effective data communications. Based on temporal, spatial and environmental dependencies of the network, robust links and routes has been found and effectively used for route selection. Probabilistic modeling techniques have been exploited to serves the purpose. Awareness of the movement of nodes gets reflected in adaptive selection of route. Experimental results suggest that the resulting e-ARP protocol is efficient and leads to significant improvement in network performance. © 2017 IEEE.