Abstract: To solve the problem of neighbor discovery in designing the MAC layer of Mesh networks, two neighbor discovery algorithms were designed and realized based on fast-switching multi-beam antennas, which are called direct-discovery algorithm and gossip-based discovery algorithm respectively. The performances of the proposed algorithms were also verified by simulations. Analyses and simulations indicate that, by adopting either of the two proposed algorithms, efficient scan and discovery of neighbor nodes in the network could be achieved. Furthermore, gossip-based discovery algorithm is able to discover neighbors faster than direct-discovery algorithm and especially it is benefit of working in the environment with high node density and relatively narrow beam width.