Collecting vehicle trajectory through message dissemination

Vehicle trajectory information can enable many promising applications, but obtaining the information is very challenging. Thanks to the Vehicular Adhoc Network (VANET), in which vehicles and access points can communicate, we can collect trajectory data from vehicles in an area through wireless communication. In this paper, we select intersections to disseminate requests for collecting moving trajectories of all the vehicles in the area, while at the same time minimizing the number of selected intersections. We prove the underlying intersection selection problem is NP-Complete and propose a greedy heuristic to address it approximately. The performance, efficiency and practical issues such as broadcast intervals of the scheme are analyzed in this paper. To deal with the situation that access points are unavailable, we propose a distributed protocol to make vehicles conduct message broadcasting at the selected intersections. The simulation shows our distributed protocol is both efficient and effective.