Ahoi: Optimal Asymmetric Neighbor Discovery

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.

Authors

Institutions

Publication Details

Journal
Proceedings of the ACM on Networking
Published
2026-11-19
DOI
https://doi.org/10.1145/3856971
Primary Topic
Energy Efficient Wireless Sensor Networks
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Ahoi: Optimal Asymmetric Neighbor Discovery

Philipp H. Kindt, Samarjit Chakraborty
Proceedings of the ACM on Networking
Energy Efficient Wireless Sensor Networks
article

Ahoi: Optimal Asymmetric Neighbor Discovery

Philipp H. Kindt, Samarjit Chakraborty
article en

Abstract

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.

Proceedings of the ACM on NetworkingVol. 4(CoNEXT4)
Technical University of Munich (DE)
Energy Efficient Wireless Sensor Networks
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon