Apparatus and method are provided for discovery and networking of proximate devices using acoustic messaging. In one novel aspect, a peer discovery protocol is used to discover proximate devices using voting messages encoded in ultrasonic waveform. In one embodiment, the UE receives one or more voting messages from neighboring UEs encoded in ultrasonic waveform, builds its voting message and broadcasts the voting message encoded in ultrasonic waveform. In another embodiment, based on the voting result, a multi-tier wireless LAN is established by the master UEs through two RF interfaces. In another novel aspect, an optimized synchronization by the receiver is used to locate the transmitted frame boundary of the ultrasonic message. In one embodiment, the UE reversed-looks up a pre-calculated boundary-offset table to estimate the tone boundary and searches the maximum synchronization tone energy down to per sampling interval using a predefined search algorithm to optimize locating the tone boundary.