Vehieles enlisted with eomputing,sensing and communicating devices can create vehicular networks,a subset of cooperative systems in heterogeneous environments,aiming at improving safety and entertainment in traffic.In vehicular networks,a vehicle’s identity is associated to its owner’s identity as a unique linkage.Therefore,it is of importance to protect privacy of vehicles from being possibly tracked.Obviously,the privacy protection must be scalable because of the high mobility and large population of vehicles.In this work,we take a non-trivial step towards protecting privacy of vehicles.As privacy draws public concerns,we firstly present privacy implications of operational challenges from the public policy perspective.Additionally,we envision vehicular networks as geographically partitioned subnetworks(cells).Each subnetwork maintains a list of pseudonyms.Each pseudonym includes the cell’s geographic id and a random number as host id.Before starting communication,vehicles need to request a pseudonym on demand from pseudonym server.In order to improve utilization of pseudonyms,we address a stochastic model with time-varying arrival and departure rates.Our main contribution includes:1)proposing a scalable and effective algorithm to protect privacy;2)providing analytical results of probability,variance and expected number of requests on pseudonym servers.The empirical results confirm the accuracy of our analytical predictions. Vehieles enlisted with eomputing, sensing and communicating devices can create vehicular networks, a subset of cooperative systems in heterogeneous environments, aiming at improving safety and entertainment in traffic.In vehicular networks, a vehicle’s identity is associated to its owner’s identity as a unique linkage. Therefore, it is of importance to protect privacy of vehicles from being possibly tracked. Obviously, the privacy protection must be scalable because of the high mobility and large population of vehicles.In this work, we take a non-trivial step towards protecting privacy of vehicles.As privacy draws public concerns, we first present privacy implications of operational challenges from the public policy perspective. Additionally, we envision vehicular networks as geographically partitioned subnetworks (cells). Each subnetwork maintains a list of pseudonyms. Each pseudonym includes the cell’s geographic id and a random number as host id.Before starting communication, vehicles need to req uest a pseudonym on demand from pseudonym server.In order to improve utilization of pseudonyms, we address a stochastic model with time-varying arrival and departure rates. Our main contribution includes: 1) proposing a scalable and effective algorithm to protect privacy; 2) providing analytical results of probability, variance and expected number of requests on pseudonym servers. The empirical results confirm the accuracy of our analytical predictions.