Apparatus and method are provided for performing asynchronous discovery among multiple peers in a wireless peer-to-peer (P2P) network. In an aspect of the disclosure, a peer selects a duty cycle C corresponding to a probability that the peer is in either a scanning state or an advertising state, rather than a sleeping state, wherein the duty cycle C is selected in accordance with a power consumption of the peer. The peer also selects a first probability Pt for being in the advertising state, and performs an asynchronous discovery protocol in accordance with the duty cycle C and the first probability Pt.