SkyOrbs: A Fast 3-D Directional Neighbor Discovery Algorithm for UAV Networks

Neighbor discovery (ND) is a critical network initialization stage, particularly challenging for highly-dynamic unmanned aerial vehicle (UAVs) with directional antennas. Considering that directional antennas focus signal energy in one direction, successful ND requires a pair of UAVs to point antennas towards each other simultaneously. However, due to the inherent constraints of autonomous UAVs (e.g., high mobility and decentralized coordination), spatial alignment of directional beams is difficult. Existing works resort to ideal assumptions (e.g., clock synchronization, assistance of omni-directional antennas and prior information) for simplification. Moreover, previous ND algorithms assume unlimited switching capability for directional antennas, often unrealistic for traditional mechanically steered antennas. In this paper, we propose <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SkyOrbs</i>, a fast directional ND algorithm for UAV networks without these ideal assumptions. To reduce ND latency, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SkyOrbs</i> presents a skip scanning strategy, dynamically adjusting antenna rotation speed to enhance discovery probability. Furthermore, to mitigate the uncertain rotation overhead induced by time-variant angular speed, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SkyOrbs</i> designs a novel antenna scanning path that accommodates limited mechanical rotation capacity. We analyze the theoretical delay performance of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SkyOrbs</i>, and expand its applicability to broader scenarios. Evaluation results show that <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SkyOrbs</i> can reduce discovery latency by 40.8% and rotation overhead by 55.0% compared to the baseline method.