Intelligent transportation systems (ITSs) havebecome increasingly important for public transportation inShanghai, China. In response, ShanghaiGrid (SG) aims toprovide abundant intelligent transportation services to improvetraffic conditions. A fundamental service in SG is to locate thenearest desirable vehicles for users. In this paper, we proposean innovative protocol called ANTS to locate a desirable vehicleclose to the querying user. The protocol finely mimics the efficientsearching strategy adopted by a lost ant searching for its nest.Taking query locality into account, ANTS can retrieve the closestvehicles satisfying the query with high probability but incurssmall query latency and modest network traffic. ANTS is afully distributed and robust protocol and, therefore, has goodscalability. Extensive simulations based on the real road networkand the trace data of vehicle movements in Shanghai demonstratethe efficacy of ANTS.

PDF