As a promising branch of Internet of Things, Internet of Vehicles (IoV) is envisioned to serve as an essential data sensing and processing platform for intelligent transportation systems. In this paper, we aim to address location privacy issues in IoV. In traditional pseudonym systems, the pseudonym management is carried out by a centralized way resulting in big latency and high cost. Therefore, we present a new paradigm named Fog computing supported IoV (F-IoV) to exploit resources at the network edge for effective pseudonym management. By utilizing abundant edge resources, a privacy-preserved pseudonym (P3) scheme is proposed in F-IoV. The pseudonym management in this scheme is shifted to specialized fogs at the network edge named pseudonym fogs, which are composed of roadside infrastructures and deployed in close proximity of vehicles. P3 scheme has following advantages 1) context-aware pseudonym changing; 2) timely pseudonym distribution; and 3) reduced pseudonym management overhead. Moreover, a hierarchical architecture for P3 scheme is introduced in F-IoV. Enabled by the architecture, a context-aware pseudonym changing game and secure pseudonym management communication protocols are proposed. The security analysis shows that P3 scheme provides secure communication and privacy preservation for vehicles. Numerical results indicate that P3 scheme effectively enhances location privacy and reduces communication overhead for the vehicles.