Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks

Abstract

In this paper, we address two problems associated with static ad hoc wireless networks; methods of saving energy during a deployment of the nodes, and efficient methods of performing adjacent neighbor discovery. To meet these goals we introduce a family of "birthday protocols"which use random independent transmissions to discover adjacent nodes. Various modes of the birthday protocol are used to solve the two problems. We provide a mathematical model and analysis of two modes of the protocol and are led to a third mode which is the probabilistic analog of the deterministic round robin scheduling algorithm. We show by analysis and simulation that the birthday protocols are a promising tool for saving energy during the deployment of an ad hoc network as well as an efficient and flexible means of having the nodes discover their neighbors