In the recent years, advances in Vehicular networks have attracted special attraction of researchers. Lately two types of applications have gain popularity: Road safety and Driving comfort. Reliable data transformation in the city environment is hard to accomplish due to presence of noise and obstacles. In addition transient or permanent faults of vehicles or roadside routers (road components) are unavoidable, so we need a fault tolerant algorithm to overcome such failures. Although utilizing faulttolerant techniques cause to more efficiency and reliability in service discovery for vehicle networks, there are many few service discovery algorithms that have considered fault- tolerant techniques. In this paper we have improved one of these algorithms which is named Fault-Tolerant Location-Based Vehicular Service Discovery Protocol (FLocVSD) in order to being more reliable.