Abstract: Preserving location privacy is an essential requirement in mobile internet. A location privacy protection approach named KAP was proposed which aimed at the privacy issue of location service under the mobile Internet. Through the analysis on locating technology, a weighted adjacent graph-based topology model was given in order to describe the positional relationship between hot spots. Meanwhile, with the help of the model, combining the concept of k-anonymity, three privacy algorithms was shown to make sure the location can not be obtained precisely by attacker. The simulation results verified the correctness and performance of the approach.