Most of routing protocols in VANETs are position-based due to their well scalability. The forwarding decisions of such protocols are simply based on the location information of forwarders' neighborhood and the destination node. Due to high mobility of vehicles, location-service protocols are required to provide the destination location. Location services protocols can be categorized as flooding-based and quorum-based. They are unrealistic for VANETs. In the former approaches, global network flooding require extreme high cost, while in the latter approaches, quorums' hand-off is impossible because of high volume of exchange data. In this paper, we present a routing by utilizing locality of vehicles' traces (i.e., left location information). Besides, by the aid of high mobility of vehicles and news exchange (new information about vehicles' location), vehicles' location information can be spread to improve the possibility of meeting a vehicle which has the location information of the destination. Our protocol is realistic and practical because neither global network flooding nor quorums are required. The simulation results show that our protocol works efficiently for VANETs in city environments and has higher successful query rate and lower cost.