CS Paper Radar

Self-Adaptive Threshold ALOHA

Ahsen Topbas, Aimin Li, Elif Tugce Ceran

cs.NI ·submitted 2026-09-13 21:25 UTC · v1
benchmark

Abstract

We propose Self-Adaptive Threshold ALOHA (SATA), a distributed random-access policy to minimize the Age of Information (AoI). SATA uses 1-bit broadcast feedback and requires no explicit coordination or message passing among nodes. {We show that this minimal feedback is sufficient for each node to perfectly track the number of active users and adjust its access probabilities accordingly.} For any initial network state, SATA converges to a collision-free TDMA steady state in finite time whenever the age threshold satisfies $Γ\geq n$, where $n$ is the network size. We derive closed-form expressions for the long-term average AoI and throughput in steady state, and establish that, for $Γ=n$, the expected transient duration scales as $O(n\log n)$. Simulation results confirm that SATA closely approaches TDMA performance across a wide range of network sizes, significantly outperforming Slotted ALOHA, Threshold ALOHA, and 1-persistent Threshold Slotted ALOHA. Notably, the performance gap between SATA and the benchmark random-access policies becomes more pronounced as network size grows.

Comment
5 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Analysis and Optimization of Age of Information in Large-Scale Random Access Networks

cs.NI ·2026-10-20 ·Yueqi Chen, Siqi Fan, Zhuoyi Zhao, I-Hong Hou, Igor Kadota
similarity 0.64
Abstract · 8 pages, 1 figure, 2 tables

We consider a large-scale network where multiple nodes transmit time-sensitive information via a shared channel to a wireless base station using a Carrier-Sense Multiple Access (CSMA) protocol. In this network, packet transmissions from different nodes are interdependent, making it challenging to analyze and optimize information freshness, captured by the Age of Information (AoI) metric. In this paper, we develop a tractable analytical framework for analyzing and optimizing the AoI. By combining mean-field approximation with first return time and renewal reward analysis, the proposed approach provides a fast, tractable, and accurate AoI approximation that explicitly accounts for carrier sensing, enabling us to quickly find the network parameters that minimize AoI. Since the framework is built on a finite-state Markov representation of the CSMA protocol, it applies to a broad class of Random Access systems. As a concrete example, we study age-threshold CSMA protocols and derive closed-form or efficiently computable AoI approximations under different protocol settings. We validate the proposed AoI analysis via extensive simulations, demonstrating a tight agreement between analysis and simulation.

0.28

AFRA: Age-Threshold Frame-Based Random Access for Timely Communication in Multi-Agent Systems

cs.IT ·2026-10-23 ·Jiedan Tan, Fang Liu
publishedtheory similarity 0.61
Abstract · Accepted for presentation at IEEE ROBIO 2026

Timely state updates are essential for coordination and monitoring in multi-agent systems, such as teams of mobile robots exchanging state information. When agents share a wireless channel, collisions and slow convergence of distributed access schemes can degrade information freshness over finite operating periods. This paper proposes age-threshold frame-based random access (AFRA), a distributed medium access control protocol for minimizing age of information (AoI). Once its age reaches a threshold, an agent starts a local frame with a mandatory transmission and, if unsuccessful, makes one further attempt at a uniformly selected remaining slot. Each attempt carries a freshly generated update. AFRA requires only local state and acknowledgment feedback, with shared slot boundaries but independently timed local frames. We prove almost-sure convergence from any legal initial state to collision-free periodic operation when the frame length $L$ and age threshold $T$ satisfy $L\ge T>N\ge2$, where $N$ is the number of agents. We also derive closed-form expressions for steady-state throughput, average AoI, and average peak AoI. Simulations demonstrate that AFRA combines rapid convergence at small age thresholds with lower window-averaged AoI than the existing age-aware random access schemes evaluated in this study.

0.42

Exponential Backoff: Meta-Stability and Implicit Admission Control

cs.NI cs.IT ·2026-09-29 ·Richard Combes, Fabien Mathieu, Thomas Bonald
code/data similarity 0.59
Abstract · 25 pages

We analyze exponential backoff, an algorithm used to share a single communication channel in a distributed manner between several users, in a similar way as many networking standards such as 802.11. We demonstrate that this algorithm has a meta-stable behavior, in the sense that the system oscillates over long time-scales between meta-stable configurations where only a subset of the sources effectively access the channel. In other words, meta-stability creates a form of implicit admission control. We provide both theoretical tools and numerical experiments to understand this phenomenon further. Our experiments are fully reproducible and the code is publicly available as a Python package available at https://pypi.org/project/slotted-aloha-simulator/.

0.38

Collision-Free Schedule Acquisition through Slotted ALOHA: Scaling Laws and Fluctuations

cs.IT ·2026-09-09 ·Plínio Santini Dester
similarity 0.58
Abstract · Submitted to Wireless Networks

Decentralized networks can learn collision-free periodic transmission schedules, but acquisition can consume much of a finite operating horizon. We characterize acquisition in a reservation protocol for a fixed population of $n$ nodes and a period of $Γ_n\ge n$ slots. Initially, each node attempts independently in each slot with probability proportional to $1/n$. A success reserves a slot that the node reuses every $Γ_n$ slots, retaining it after collisions. Nodes use only their own acknowledgments and small local memory. An exact finite-population Markov reduction, independent of the arrangement of reserved slots, characterizes the time until every node has a distinct reservation. As $n\to\infty$, mean acquisition takes $O(n^2)$ slots when $Γ_n=n$ and $O(n\log n)$ slots when $Γ_n\sim(1+θ)n$, for fixed $θ>0$. With a fixed number $Γ_n-n$ of spare slots, the standard deviation of acquisition time has the same asymptotic order as its mean. If that number diverges while $Γ_n/n$ remains bounded, the ratio of standard deviation to mean tends to zero. A diverging sublinear number of spare slots yields $o(n^2)$ mean acquisition while long-run utilization, the fraction $n/Γ_n$ of slots with successful transmissions, tends to one. Simulations validate these laws and compare acquisition and delivered packets per slot with existing access protocols.

0.31

Contention Resolution with a Fast-but-Fickle Channel

cs.DC ·2026-11-09 ·Umesh Biswas, Vini Chaudhary, Shafqat Hasan, Maxwell Young
theory similarity 0.57
Abstract

The contention-resolution problem studies how $n$ devices share a communication channel without centralized coordination. Classical models typically assume a single continuously available channel and focus on minimizing total completion time. However, modern wireless systems increasingly rely on shared spectrum, where access may be abruptly revoked by incumbent users. Motivated by this setting, we study contention resolution with two channels: a reliable slow channel and a faster channel that can be intermittently disabled by unpredictable eviction periods. Moving a batch of packets from the slow channel to the fast channel incurs a unit cost, while evictions from the fast channel impose a larger per-packet penalty. Our goal is to achieve asymptotically optimal latency while minimizing switching overhead relative to an optimal offline algorithm that knows the eviction schedule. We present Randomized Adaptive Channel Exploitation (RACE), a randomized algorithm that exploits the fast channel when available while maintaining progress on the slow channel during disruptions. When the fast channel has rate $ρ\in \bigl[Ω(\log n), O(\sqrt n)\bigr]$ and a sufficiently large constant-factor resource augmentation, RACE achieves an $O(1)$ competitive ratio for expected latency. RACE's expected switching-cost competitive ratio relative to any optimal-latency offline algorithm OPT is $O(ρ+\sqrt{n/m})$, where $m \geq 1$ is the number of fast-channel availability intervals used by OPT. We also prove a worst-case $Ω(\sqrt n)$ switching-cost competitive ratio for latency-competitive randomized algorithms, and a separate $Ω(ρ)$ switching-cost competitive-ratio lower bound. These lower bounds hold even with fixed constant-factor augmentation on both channels.

0.31

Elapsed-Service-Time-Aware Preemption for Age of Information Minimization

cs.IT ·2026-11-04 ·Mohammad Moltafet, Nail Akar, Sennur Ulukus, Marian Codreanu, Roy D. Yates
similarity 0.55
Abstract

We study the age of information and peak age of information in status update systems with an arbitrary number of independent sources sharing a single server with generally distributed service times. We consider a general age-dependent self-preemptive policy in which an in-service update from source $c$ is preempted by a new same-source arrival with a probability $p_c(x)$ that depends on the elapsed service time $x$. This formulation subsumes the non-preemptive, fully self-preemptive, and probabilistically preemptive policies as special cases, and also accommodates threshold-based preemption. We develop a unified analytical framework based on non-homogeneous absorbing continuous-time Markov chains and semi-Markov chains to derive explicit expressions for the average age of information and peak age of information of each source under general per-source service-time distributions and age-dependent preemption rules. The framework applies to both single-source and multi-source systems and enables joint tuning of per-source preemption parameters. Numerical results for fifteen service-time distributions in the single-source setting reveal that the benefits of preemption depend strongly on the service-time hazard-rate structure, with threshold-based preemption providing its most notable additional gains over age-independent policies for distributions with unimodal hazard rates. For a dual-source system with lognormal service times, jointly tuned threshold-based preemption achieves lower sum average age of information and peak age of information than the considered age-independent policies, highlighting the importance of cross-source interactions in preemption decisions.

0.09

Value-Based Massive Access through Goal-Oriented Irregular Repetition Slotted ALOHA

cs.NI cs.MA ·2026-09-17 ·Pietro Talli, Andrea Munari, Federico Mason, Federico Chiariotti, Andrea Zanella
similarity 0.54
Abstract

The goal-oriented communication paradigm is poised to enable novel real-time applications by easing the burden on communication networks while still delivering task-relevant information. However, efforts so far have focused on the encoding problem, while the design of medium access schemes is still in the early stages of development, especially when connectivity is to be provided to a massive number of devices, e.g., for remote monitoring. In this respect, existing goal-oriented approaches are often centralized or based on simplified underlying mechanisms, requiring unrealistic assumptions. In this work, we present the Goal-oriented Irregular Repetition Slotted ALOHA (GO-IRSA) scheme, which combines modern random access techniques with belief-based policies. GO-IRSA does not impose significant computing loads on the sensors or require frequent feedback, and it can reduce the average and worst-case error of the estimate of a distributed Wiener process by over 30% with respect to the optimal centralized solution in a network with thousands of sensors, and is robust to imperfect interference cancellation and inaccurate process knowledge.

0.26

Can Bandits Learn to Share a Channel? Distributed Multi-Armed Bandits for Slotted ALOHA

cs.NI ·2026-11-18 ·Kamil Szczech, Maksymilian Wojnar, Krzysztof Rusek, Katarzyna Kosek-Szott, Szymon Szott
similarity 0.54
Abstract

Slotted ALOHA networks constitute a playground for research on machine learning (ML)-based channel access schemes. We consider ML agents deployed in such networks and operating under severe constraints: fully distributed (independent operation), fully online (no pre-training), aperiodic (no fixed schedule), and with no explicit coordination (no signaling). We ask whether a multi-armed bandit (MAB), a minimal reinforcement learning agent, can learn the optimal policy for a capture-free slotted ALOHA system. We evaluate several MAB algorithms on aggregate network throughput and per-node fairness. Our best-performing agent is based on a Softmax bandit, which we call SALSA (Softmax ALOHA Learning for Shared Access). SALSA learns a per-node transmission policy close to optimal, with throughput near the theoretical maximum for fair random access. We achieve performance comparable to a competing state-of-the-art solution, but without requiring a priori knowledge of the network size.

0.11