Methods and apparatus related to peer to peer communication networks are described. A peer to peer timing structure is implemented which includes recurring peer discovery intervals and traffic intervals. During a peer discovery interval, a wireless communications device, supporting peer to peer communications, monitors for and receives a broadcast signal from another peer wireless communications device, recovers an identifier from the received broadcast signal, and stores the received identifier in memory. The identifier is one of a device identifier and a user identifier. The wireless communications device maintains a list of discovered identifiers in its vicinity. In some embodiments, paging intervals are also included in the recurring peer to peer timing structure. In various embodiments, a wireless communications device receives or sends a page to a peer node prior to sending or receiving user data in a traffic interval. Various features are directed to peer paging protocol implementations.