  Neighbor discovery plays a crucial role in the formation of wireless sensor
networks and mobile networks where the power of sensors (or mobile devices) is
constrained. Due to the difficulty of clock synchronization, many asynchronous
protocols based on wake-up scheduling have been developed over the years in
order to enable timely neighbor discovery between neighboring sensors while
saving energy. However, existing protocols are not fine-grained enough to
support all heterogeneous battery duty cycles, which can lead to a more rapid
deterioration of long-term battery health for those without support. Existing
research can be broadly divided into two categories according to their
neighbor-discovery techniques---the quorum based protocols and the co-primality
based protocols.In this paper, we propose two neighbor discovery protocols,
called Hedis and Todis, that optimize the duty cycle granularity of quorum and
co-primality based protocols respectively, by enabling the finest-grained
control of heterogeneous duty cycles. We compare the two optimal protocols via
analytical and simulation results, which show that although the optimal
co-primality based protocol (Todis) is simpler in its design, the optimal
quorum based protocol (Hedis) has a better performance since it has a lower
relative error rate and smaller discovery delay, while still allowing the
sensor nodes to wake up at a more infrequent rate.
