Abstract: With advances in wireless communication and mobile positioning technologies, location-based services (LBSs) have seen wide-spread adoption. The academia and industry have pay attention to location privacy preserving in LBSs for about ten years. Most existing location cloaking algorithms over road networks are based on DFS-based or BFS-based graph traversal algorithms. However, the main drawback of these approaches is the repetitive global road network traversal, which results in the low efficiency and high communication cost. In order to resolve the problem, we propose a network Voronoi-based location anonymization algorithm NVLA on road networks. Under the help of network Voronoi diagram (NVD), the road network is divided into several network Voronoi cells offline. Then, we reduce the problem of anonymization over the global road network into finding cloaking sets in local network Voronoi cells (NVC). Next, according to the number of road segments and the number of users in a cell, network Voronoi cells are classified to unsafe, safe-medium and safe-large cells. Finally, according to the features of the different network Voronoi cells, different cloaking algorithms are proposed. We design and conduct a series of experiments, and the experimental results validate the efficiency and effectiveness of the proposed algorithm. The average cloaking time is only 0.4 ms and the cloaking success rate is about 100%. On the other hand, only 0.01% of the query cost is sacrificed.