Service discovery is an important and challenging issue in pervasive environments. Recent studies on service discovery mainly adopt Distributed Hash Tables (DHTs) based approaches without the consideration of private information protection. The main disadvantage of such approaches is that P2P overlay network does not reflect the physical topology and consequently generate substantial traffic overhead. In this paper, we propose a new service discovery scheme, considering both discovery efficiency and privacy protection. In the proposed scheme, we will present polar coordinate description and semantic service description to build location-aware overlay network. The polar coordinate description is able to efficiently build overlay networks, provide location-based searching, and alleviate traffic congestion. The physical hop counts and message overhead are significantly reduced due to the essentially distributed topology and ignorance of flooding operations. The usage of semantic description can find similar services more quickly and efficiently. We also consider the protection of mobile nodes private information. Results show that our proposed service discovery scheme is able to achieve much higher discovery success ratio and lower cost, compared to existing approaches.