With the development of the Internet of Things (IoT) and edge computing, more and more devices, such as sensor nodes and intelligent automated guided vehicles (AGVs), can serve as edge devices to provide Location-Based Services (LBS) through the IoT. As the number of applications increases, there is an abundance of sensitive information in the communication process, pushing the focus of privacy protection towards the communication process and edge devices. The challenge lies in the fact that most traditional location privacy protection algorithms are not suited for the IoT with edge computing, as they primarily focus on the security of remote servers. To enhance the capability of location privacy protection, this paper proposes a novel K-anonymity algorithm based on clustering. This novel algorithm incorporates a scheme that flexibly combines real and virtual locations based on the requirements of applications. Simulation results demonstrate that the proposed algorithm significantly improves location privacy protection for the IoT with edge computing. When compared to traditional K-anonymity algorithms, the proposed algorithm further enhances the security of location privacy by expanding the potential region in which the real node may be located, thereby limiting the effectiveness of “narrow-region” attacks.