A protocol for discovering a new neighbor node and detecting the loss of an existing neighbor node in a network is described. A node receives a neighbor discovery message from a neighbor node. The node receiving the neighbor discovery message periodically transmits a predetermined number of neighbor discovery messages in response to the received neighbor discovery message. Each neighbor discovery message includes an identity of the neighbor node. After transmitting the predetermined number of neighbor discovery messages, the node transmits neighbor discovery messages that omit the identity of the neighbor node until another neighbor discovery message is received from the neighbor node that indicates a change in a communications state associated with the neighbor node.