Many peer-to-peer (p2p) systems have been studied in distributed, ubiquitous computing environments. Distributed hash table (DHT)-based p2p systems can improve load-balancing even though locality utilization and user mobility are not guaranteed. We propose a mobile locality-based hierarchical p2p overlay network (MLH-Net) to address locality problems without any other services. MLH-Net utilizes mobility features in a mobile environment. MLH-Net is constructed as two layers, an upper layer formed with super-nodes and a lower layer formed with normal-nodes. Because super-nodes can share advertisements, we can guarantee physical locality utilization between a requestor and a target during any discovery process. To overcome a node failure, we propose a simple recovery mechanism. The simulation results demonstrate that MLH-Net can decrease discovery routing hops by 15% compared with JXTA and 66% compared with Chord.