Meet in the air: Distributed neighbor discovery in 3D networks with directional transceivers

We formulate and analyze a generic neighbor discovery problem in three-dimensional wireless networks with directional transceivers, where any pair of neighbor nodes in 3D Euclidean space need to steer their transceivers towards each other simultaneously to discover each other. This problem, termed as 3D directional neighbor discovery, arises in a variety of emerging networked systems such as flying ad hoc networks composed of drones and distributed space systems composed of spacecrafts. Compared to the omni-directional 2D neighbor discovery problem extensively investigated in the literature, the 3D directional neighbor discovery problem is intuitively more challenging. Motivated by this observation, we establish an algorithmic framework on the 3D directional neighbor discovery problem. We first mathematically formulate the problem and derive the worst-case discovery delay of any neighbor discovery algorithm. Guided by the performance limit, we then design distributed neighbor discovery algorithms achieving bounded and minimal worst-case discovery delay. We further demonstrate how our algorithmic framework can be generalized to solve generic multi-dimensional rendezvous problems. Extensive numerical analysis is then presented to empirically evaluate of our neighbor discovery algorithms.