Abstract: The k-anonymity model is employed to protect the location privacy in Location-Based Services (LBS) in recent years. A Moving-Pattern Attack (MPA) is presented, in a scenario that the moving user keeps delivering queries. It is shown that traditional algorithms fail in this attack. In order to protect against MPA, a novel anonymity measurement based on entropy is proposed, which leads to a cloaking algorithm under mobile environments, i.e. Mclique. Experiments show that Mclique protects effectively user privacy against MPA. By simplifying the computing of entropy in Mclique, a fast cloaking algorithm, Fclique, is proposed. Experiments show that Fclique is capable of surviving MPA, and reduces greatly the time complexity as well.