MAB-Based 3-Way Neighbor Discovery for Wireless Networks Using Directional Antennas

Neighbor discovery, one of the most crucial networking primitives, is particularly challenging in wireless networks with directional antennas. Most of the existing schemes have high discovery delays and serious long tail problems, especially for high-density networks. In this paper, neighbor discovery is formulated as a Markov multi-armed bandit (MAB) problem. Each node utilizes the result of past discovery attempts for learning. We use upper confidence bound (UCB) based algorithms to address the topic, which can effectively balance exploration and exploitation. In addition, a 3-way handshake algorithm with collision feedback is proposed in order to better perceive collisions in the network, thereby speeding up the learning process. Through extensive simulations, we demonstrate that the proposed algorithm is superior to existing methods in terms of neighbor discovery efficiency, while maintaining low overhead and computational complexity.