This paper proposes a synchronous device discovery solution for ad-hoc networks based on the observations that time synchronization, along with an FDM based channel resource allocation, can lead to gains in terms of energy consumption, discovery range, and the number of devices discovered. These attributes are important for the success of proximity-aware networking, where devices autonomously find peer-groups over human mobility scales. In this paper, we develop the PHY and MAC protocols to enable autonomous device discovery. Using both simulations and stochastic-geometry based analysis, we validate our design, and argue that there can be significant gains over a conventional Wi-Fi based solution.