Neighbor discovery latency in BLE-like duty-cycled protocols

摘要

Neighbor discovery is the procedure using which two wireless devices initiatea first contact. In low power ad-hoc networks, radios are duty-cycled and thelatency until a packet meets a reception phase of another device is determinedby a random process. Most research considers slotted protocols, in which thepoints in time for reception are temporally coupled to beacon transmissions. Incontrast, many recent protocols, such as ANT/ANT+ and Bluetooth Low Energy(BLE) use a slotless, periodic-interval based scheme for neighbor discovery.Here, one device periodically broadcasts packets, whereas the other deviceperiodically listens to the channel. Both periods are independent from eachother and drawn over continuous time. Such protocols provide 3 degrees offreedom (viz., the intervals for advertising and scanning and the duration ofeach scan phase). Though billions of existing BLE devices rely on theseprotocols, neither their expected latencies nor beneficial configurations withgood latency-duty-cycle relations are known. Parametrizations for theparticipating devices are usually determined based on a "good guess". In thispaper, we for the first time present a mathematical theory which can computethe neighbor discovery latencies for all possible parametrizations. Further,our theory shows that upper bounds on the latency can be guaranteed for allparametrizations, except for a finite number of singularities. Therefore,slotless, periodic interval-based protocols can be used in applications withdeterministic latency demands, which have been reserved for slotted protocolsuntil now. Our proposed theory can be used for analyzing the neighbor discoverylatencies, for tweaking protocol parameters and for developing new protocols.