Dynamic method controls delays and collisions in shared channels
Dynamic Wakeup under Costly Collisions
Distributed, Parallel, and Cluster Computing
Summary
Devices that share a communication channel need to take turns sending messages without interfering with each other. The authors study a way to quickly get a message through even when many devices become active at different times, and when collisions cause extra delays. They offer a new random approach that balances the time taken to succeed and the cost from collisions, working well even without knowing how many devices are involved or having collision detection. Their results show limits on how well such strategies can perform under these conditions.
What this means in practice
- •For network schedulers: Optimize scheduling in shared wireless channels to reduce delays caused by simultaneous transmissions and costly collisions.
- •For internet of things developers: Improve communication efficiency among IoT devices waking up at unpredictable times without centralized control or collision detection.
Authors
Umesh Biswas, Maxwell Young
Abstract
The wakeup problem captures a fundamental symmetry-breaking challenge among devices sharing a communication channel. We study the dynamic setting, where packets become active at arbitrary times on a time-slotted multiple access channel. In each slot, a transmission succeeds if and only if exactly one packet transmits; two or more simultaneous transmissions cause a collision. The goal is to obtain a successful transmission quickly. Prior work on wakeup has largely focused on the number of slots until the first success, referred to as the latency. However, a collision may incur substantial additional delay, represented by a per-collision cost $C$. We therefore seek to control both latency and the collision cost of an execution, defined as $C$ times its number of collisions. We design and analyze a randomized algorithm for dynamic wakeup, Lowball, without collision detection or knowledge of the number of packets, $n$. Fix a constant $0<ε\le 1/2$. There is a constant $K>0$ such that, when $C\ge K\lg^{1/ε} n$, Lowball has expected latency $O(C^{1/2+ε}\ln C)$ and expected collision cost $O(\sqrt{C})$. Below this threshold, both expectations are $O(n\log^{Θ(1/ε)} n)$. These guarantees hold against an adaptive, non-anticipating adversary, and the algorithm succeeds with probability 1. For algorithms in which each packet's transmission probability depends only on $C$ and the packet's local age, with packets activated together using the same probability schedule, we prove that the maximum of expected latency and expected collision cost is $Ω(\sqrt{C})$.