Neighbor discovery is a critical first step in estab- lishing communication in a wireless ad-hoc network. Existing quorum-based neighbor discovery algorithms only consider a pair of nodes and ensure that this pair can communicate at least once in a bounded interval. However, when the node density of a wireless network increases, collisions are more likely to happen, which makes these quorum-based algorithms inefficient in practice. We propose a novel self-adapting quorum-based neighbor discovery algorithm that can dynamically adjust its cycle pattern to decrease the impact of such collisions. We first assess the collision problem in wireless networks when using quorum-based neighbor discovery algorithms and then establish a theoretical framework to analyze the discovery delay when considering collision effects. Guided by these theoretical results, we design a self-adapting mechanism for cycle patterns in quorum-based algorithms. Simulation results show that our algorithm can achieve complete neighbor discovery in less time than existing quorum-based neighbor discovery algorithms.
展开▼
