Ahoi: Optimal Asymmetric Neighbor Discovery
Proceedings of the ACM on Networking · 19.11.2026 · 4 (CoNEXT4) · 1-20
DOI: 10.1145/3856971 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Networking, online erschienen am 19.11.2026. Verfasst von Philipp Heinrich Kindt und 1 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Dieter Schwarz Foundation.
Abstract (Originalsprache)
Neighbor discovery (ND) is the link-layer first-contact step that enables two wireless devices to find each other before any higher-layer communication can take place. Low-power devices perform ND by following wake-up schedules: they transmit short beacons at selected times, listen during selected reception windows, and sleep otherwise to save energy. Because these schedules determine both discovery latency and battery lifetime, ND has been studied for more than two decades and has led to a large body of protocols. Yet an important part of the design space remains insufficiently understood: asymmetric, duty cycle-unaware ND, where different devices may use different duty cycles and may adjust them independently at runtime, without knowing the duty cycle chosen by their peers. This setting arises naturally in heterogeneous IoT deployments, energy-harvesting devices, and battery-powered systems. This paper addresses this gap by introducing Ahoi, a deterministic family of transmission and reception schedules for asymmetric ND. We use optimal in the precise sense of matching the protocol-independent lower bound on worst-case discovery latency for a given pair of transmission and reception duty cycles. In unidirectional discovery, Ahoi allows each sender and receiver to autonomously select a schedule from a discrete set with different duty cycles, while still guaranteeing discovery for every combination of choices and matching the theoretical worst-case latency bound. This shows that, for this important class of ND protocols, the runtime flexibility of duty cycle-unaware operation need not incur any latency or energy penalty. We further extend the construction to bidirectional discovery. Here, Ahoi does not achieve this bound, but our evaluation results imply that the latencies remain close to it.
Förderung
- Dieter Schwarz Foundation
Zitieren
APA
Kindt, P. H., & Chakraborty, S. (2026). Ahoi: Optimal Asymmetric Neighbor Discovery. Proceedings of the ACM on Networking, 4(CoNEXT4), 1-20. https://doi.org/10.1145/3856971
Vancouver
Kindt PH, Chakraborty S. Ahoi: Optimal Asymmetric Neighbor Discovery. Proceedings of the ACM on Networking. 2026;4(CoNEXT4):1-20. doi:10.1145/3856971
BibTeX
@article{Kindt2026,
author = {Kindt, Philipp Heinrich and Chakraborty, Samarjit},
title = {Ahoi: Optimal Asymmetric Neighbor Discovery},
journal = {Proceedings of the ACM on Networking},
year = {2026},
volume = {4},
number = {CoNEXT4},
pages = {1--20},
doi = {10.1145/3856971}
}
EUVIMED