The success of Skype has inspired Peer-topeer (P2P) based solution for satisfactory real-time multimedia service over Internet. However, there still existsome limits such as incapability of interoperability incurredby proprietary protocol. To address the problem, we construct a novel SIP based Peer-to-peer overlay for Voiceover IP (VoIP) with preferable search performance. Themain contributions includes: (1) A novel algorithm waspresented for end-nodes to join the clusters with locationawareness; (2) Super-node (SN) overlay network was builtbased on the small world models, taking into account bothunderlying geographical distance and relationship proximity. Analysis results and preliminary simulation demonstrate that the proposed protocols could significantly decrease user searching delay, which is required by large P2PSIP network for its scalability.