  Neighbor discovery is a fundamental task for wireless networks deployment. It
is essential for setup and maintenance of networks and is typically a
precondition for further communication. In this work we focus on passive
discovery of networks operating in multi-channel environments, performed by
listening for periodically transmitted beaconing messages. It is well-known
that performance of such discovery approaches strongly depends on the structure
of the adopted Beacon Interval (BI) set, that is, set of intervals between
individual beaconing messages. However, although imposing constraints on this
set has the potential to make the discovery process more efficient, there is
demand for high-performance discovery strategies for BI sets that are as
general as possible. They would allow to cover a broad range of wireless
technologies and deployment scenarios, and enable network operators to select
BI's that are best suited for the targeted application and/or device
characteristics. In the present work, we introduce a family of novel
low-complexity discovery algorithms that minimize both the Expected Mean
Discovery Time (EMDT) and the makespan, for a quite general family of BI sets.
Notably, this family of BI sets completely includes BI's supported by IEEE
802.15.4 and a large part of BI's supported by IEEE 802.11. Furthermore, we
present another novel discovery algorithm, based on an Integer Linear Program
(ILP), that minimizes EMDT for arbitrary BI sets. In addition to analytically
proving optimality, we numerically evaluate the proposed algorithms using
different families of BI sets and compare their performance with the passive
scan of IEEE 802.15.4 w.r.t. various performance metrics, such as makespan,
EMDT, energy usage, etc.
