Methods, systems, and devices for wireless communications are described. A user equipment (UE) may implement a power-efficient discovery procedure to establish a relay. In some cases, the UE may monitor a resource pool for a relay beacon from a relay device and measure a received power of the relay beacon. If the received power satisfies a threshold, the UE may monitor for a relay announcement from the relay device and establish a sidelink connection with the relay device based on the relay announcement. The relay beacon may support a two-stage discovery procedure, where the UE determines a relay device is available before processing a relay announcement to conserve power. Additional techniques for proximity-based discovery are described herein.