Abstract: To achieve the balance between the degree of privacy protection and communication overhead of LBS (Location-based Service) in dynamic P2P (peer-to-peer) network, a location privacy-preserving technique was presented: mobile user regionalized his original position and selected a proxy node from self-organized P2P network when he consumed LBS service, and the selected node forwarded user's incremental nearest-neighbor query to LBS server. Meanwhile, the communication-cost estimation method and Voronoi technique were adopted to eliminate communication overhead. The experimental results validate the technique's effectiveness on LBS accuracy, privacy protection and communication QoS (Quality-of-Service) compared with SpaceTwist.