In this paper, a distributed taxi hailing protocol in vehicular ad-hoc networks (VANET) is suggested. Our protocol consists of two parts: taxi booking and taxi deblocking. Taxi booking part ensures that a vacant taxi with shortest driving distance to passenger under real traffic regulations is booked. Taxi de-blocking part aims to de-block blocked vacant taxis as soon as possible. Simulation results show that compared with previous results, at least 40% of booking time, 50% of waiting time of passengers and 50% of driving distance from booked taxi to passenger, is reduced in our protocol.