Reliable neighbor discovery for mobile ad hoc networks

We define a reliable neighbor discovery layer for mobile ad hoc networks and present two distributed algorithms that implement this layer with varying progress guarantees. First we describe a basic reliable region-based neighbor discovery protocol which does not guarantee communication links between nodes which are constantly crossing region boundaries. We next describe how to use this basic protocol (or any other protocol with the same properties) as a black-box to implement a reliable region-based neighbor discovery protocol that does guarantee communication links between nodes which are constantly crossing region boundaries. To achieve this we run multiple copies of the basic neighbor discovery protocol in parallel, each copy using a different region partition. We then show how the output of each of these protocols can be composed in a way as to not violate any of the guarantees of a reliable neighbor discovery layer, while at the same time attaining the stronger progress guarantees. In particular we study how this technique can be applied when the region partition is a regular square- or hexagonal-tiling of the plane. Finally we discuss an additional property of a neighbor discovery layer that we call coordination, and the potential trade-off between progress and coordination guarantees.