Methods, devices, and computer program products for transmitting and receiving discovery and paging messages are described herein. In one aspect, an apparatus operable in a wireless communication system includes a transmitter and receiver. The transmitter transmits a discovery packet during a first discovery interval of a plurality of discovery intervals. The discovery packet advertises a service provided in a wireless communications network, and the plurality of discovery intervals include recurring time intervals when a plurality of devices are configured to transmit and receive discovery packets. The receiver receives a paging packet from a first device during a first paging interval of a plurality of paging intervals. The paging packet indicates interest in the service, and the plurality of paging intervals include recurring time intervals when the plurality of devices are configured to transmit and receive paging packets. The plurality of paging intervals do not overlap the plurality of discovery intervals.