Use Bluetooth LE for peer discovery
Some newer Android devices support Bluetooth LE peripheral mode, which allows them to send beacons advertising their presence. This could be used as a low-energy and privacy-preserving alternative to polling for device pairs that support it.
https://altbeacon.github.io/android-beacon-library/beacon-transmitter-devices.html