You can use jmdns http://sourceforge.net/projects/jmdns/
I used it to search for Bonjour / Zeroconf services with good accuracy with Android 2.2. Depending on your needs, you may need to modify your code a bit to get a better opening.
Please note that some of the old HTC phones have multicast errors, but I think they fixed it on their latest phones