Location-based Services (LBS) have become a very important area for research with the rapid development of Internet of Things (IoT) technology and the ubiquitous use of smartphones and social networks in our daily lives. Although users can enjoy a lot of flexibility and conveniences from the LBS with IoT, they may also lose their privacy. Untrusted or malicious LBS servers with all users’ information can track users in various ways or release personal data to third parties. In this work, we first analyze the current dummy-location selection (DLS) algorithm—an efficient location privacy preservation approach and design an attack algorithm for DLS (ADLS) for test emerging IoT security. For efficiently preserving user’s location privacy, we propose a novel dummy location privacy-preserving (DLP) algorithm by considering both computational costs and various privacy requirements of different users. Extensive simulation experiments have been carried out to evaluate the efficiency of the proposed schemes. Evaluation results show that the ADLS algorithm has a high probability of identifying the user’s real location out from chosen dummy locations in the DLS algorithm. Our proposed DLP algorithm has clear advantages over the DLS algorithm in term of lower probability of revealing the user’s real location and improved computational cost and efficiency (i.e., time, speed, accuracy, and complexity) while preserve the same privacy level as DLS algorithm.