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 receiver and transmitter. The receiver receives a registration packet from a first device. The registration packet indicates interest in a service provided by another device in a wireless communications network. The receiver further receives a discovery packet from a second device during a first discovery interval of a plurality of discovery intervals. The discovery packet advertises a service provided by the second device, and the plurality of discovery intervals include recurring time intervals when a plurality of devices are configured to transmit and receive discovery packets in the wireless communications network. The transmitter transmits a notification packet configured to enable the first device and the second device to communicate directly.