The new generation of GPS-based tolling systems allow for a much higher degree of road sensing than has been available up to now. We propose an adaptive sampling scheme to collect accurate real-time traffic information from large-scale implementations of on-board GPS-based devices over a road network. The goal of the system is to minimize the transmission costs over all vehicles while satisfying requirements in the accuracy and timeliness of the traffic information obtained. The system is designed to make use of cellular communication as well as leveraging additional technologies such as roadside units equipped with WiFi and vehicle-to-vehicle (V2V) dedicated short-range communications (DSRC). As opposed to fixed sampling schemes, which transmit at regular intervals, the sampling policy we propose is adaptive to the road network and the importance of the links that the vehicle traverses. Since cellular communications are costly, in the basic centralized scheme, the vehicle is not aware of the road conditions on the network. We extend the scheme to handle non-cellular communications via roadside units and vehicle-to-vehicle (V2V) communication. Under a general traffic model, we prove that our scheme always outperforms the baseline scheme in terms of transmission cost while satisfying accuracy and real-time requirements. Our analytical results are further supported via simulations based on actual road networks for both the centralized and V2V settings.