Journal of Information Security Research Lan Sun, Ying-jie Wu, Zhao Luo, Yi-lei Wang 6 4 2015 http://www.dline.info/jisr/fulltext/v6n4/v6n4_1.pdf Within the field of data privacy preserving research, privacy preserving Location-based Services for mobile users in road networks is a topic of great concern in recent years. However, most previous works on location privacy protection in road networks adopt spatial cloaking techniques, which may easily suffer replay attack. In addition, existing solutions for resisting replay attack generally add some randomized mechanisms into the cloaking process, which may reduce the query efficiency. In this paper, we firstly propose a group-division method to prevent replay attack, and then present two strategies based on this method to form the cloaking group of road segments. The experiment results on real datasets of road networks demonstrate the effectiveness and feasibility of our solutions