1
Self-Adaptive Threshold ALOHA
arXiv:2609.14800v1 [cs.NI] 13 Sep 2026
Ahsen Topbas, Aimin Li, Member, IEEE and Elif Tugce Ceran 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 Γ ≥ 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 randomaccess policies becomes more pronounced as network size grows. Index Terms—Slotted ALOHA, Age of Information, random access, adaptive, distributed, network state tracking.
I. I NTRODUCTION The rapid expansion of wireless sensing, the Internet of Things (IoT), and real-time monitoring applications has increased the demand for communication systems capable of delivering timely, up-to-date information [1]. The Age of Information (AoI) metric has emerged as a key measure of the time elapsed since the most recent update [2]. As a result, minimizing AoI has become a primary objective in the design of communication networks with timeliness goals. Simultaneously, many large-scale wireless systems employ random access mechanisms due to their simplicity, scalability, and distributed operation. Nevertheless, random access networks are prone to collisions and channel contention, which can substantially degrade information freshness. The resulting design question is how much coordination is actually needed for distributed random access to approach the freshness performance of scheduled access. Age-aware random-access schemes have approached this problem by controlling which users become active and how they contend for the channel [3]–[7]. [3] proposed LAZY, also known as Threshold ALOHA (TA) [4], and [4] presented the steady-state analysis of TA. They found that in the largenetwork limit, the policy converges to a Slotted ALOHA (SA) with fewer users, and the optimal AoI scales with the network size n as 1.4169n. The performance of Threshold ALOHA degrades as the network size decreases due to its lack of convergence in small networks. [5] proposed the Stabilized Authors are with the Department of Electrical and Electronics Engineering, Middle East Technical University (METU), 06800 Ankara, Turkiye (e-mails: {ahsen.topbas, aimin, elifce}@metu.edu.tr). This work was supported in part by the TÜBİTAK 1515 Frontier Research and Development Laboratories Support Program for Turk Telekom neXt Generation Technologies Lab (XGeNTT) under Project 5249902 and in part by the European Union through ERC Advanced Grant 101122990–GO SPACE–ERC-2023-A.
1[t]
Node 1
Node 2
Data source
Common AP
2[t]
Data source
Collision Channel
n[t]
Node n
Data source
Fig. 1. System model of a random access network of a common access point and n nodes transmitting with adaptive probability τi [t], i ∈ {1, 2, ..., n}.
Age-based Threshold (SAT) policy, which achieves an agebased thinning, similar to the result of [4], and asymptotic scaling of average age as 2e n ≈ 1.359n. The 1-persistent Threshold Slotted ALOHA (1-persistent TSA) [6] built on TA by having nodes with AoI exactly equal to the threshold transmit with probability 1. With this modification, 1-persistent TSA converges to a collision-free steady state and achieves a long-term average AoI of almost n and a throughput of nΓ−1 (n and Γ are the network size and the age threshold, respectively) for Γ = 2n − 1. When Γ = n, the transient duration of 1-persistent TSA grows to an impractical order of 1045 time slots. [7] proposed AoI-Q-ALOHA, which is a distributed learning-based random access policy that achieves performance close to TA. The closest prior works to ours are TA [4] and 1-persistent TSA [6]. However, both policies use predefined, fixed transmission probabilities for active users, which limits the range of network sizes for which they are feasible. As a result, designing distributed and adaptive random-access policies that work for a wide range of network sizes remains an open research area. In this letter, we propose Self-Adaptive Threshold ALOHA (SATA), a distributed random-access policy that uses 1-bit feedback to allow each node to track the network state and adapt its transmission probability in real time. In SATA, nodes with AoI above the threshold transmit with a probability inversely proportional to the estimated number of active users, while a node whose AoI equals the threshold transmits with probability 1, silencing all other active nodes. Through this mechanism, the network organizes itself into a TDMA scheme at steady state in finite time, without any explicit coordination. The key contributions of this letter are as follows: Minimal-feedback decentralized adaptation:We show that 1-bit feedback is sufficient for each node to perfectly track the number of active users at every time slot and adapt its transmission probability accordingly, without explicit coordination or message passing (Lemma 1). • Finite-time self-organization from random access to •
2
TDMA: We prove that SATA converges to a collisionfree TDMA regime in finite time almost surely for any initial network state when Γ ≥ n (Proposition 1). In this regime, each node transmits successfully once every Γ slots, yielding the closed-form long-term AoI ∆ = Γ+1 2 and long-term throughput η = Γn (Proposition 2). In particular, Γ = n matches collision-free TDMA in the long run, achieving average AoI (n + 1)/2 and unit throughput [6] • Fast transient duration analysis: We establish a finitetime characterization of SATA’s self-organization process: for Γ = n, the expected transient duration scales as O(n log n) and admits an exponentially decaying tail (Theorem 1). In comparison, 1-persistent TSA has been reported to exhibit prohibitively long transients under the same threshold [6]. II. S YSTEM M ODEL We consider a random-access network with n communication nodes and a common access point (AP). Time is divided into equal-sized time slots, and the time duration of a time slot is normalized to 1. At the beginning of each time slot, nodes access the AP through a collision channel. Each packet transmission takes one time slot. If more than one node attempts to transmit, their packets collide and are lost. If only one node transmits, it reaches the AP successfully. At the end of each time slot, the AP broadcasts a 1-bit success feedback, f ∈ {S, F }, indicating whether the transmission succeeded. We adopt the generate-at-will model [8]. Each node i generates a single information flow, and the Age of Information (AoI) of flow i at time slot t is [2] δi [t] = t − ui [t],
(1)
where ui [t] is the packet generation time of the latest received packet of flow i by the AP. The AoI of flow i evolves as if node i successfully 1, δi [t] = transmits at time slot t − 1, (2) δi [t − 1] + 1, otherwise. The long-term average AoI of the network equals T −1 n
1 XX δi [t], T →∞ nT t=0 i=1
¯ = lim ∆
(3)
if the limit exists. The throughput of the random access channel is defined as T −1 n
1 XX 1{δi [t] = 1}, η ≜ lim T →∞ T t=0 i=1
(4)
if the limit exists. Define the network state composed of the ages of nodes as ∆[t] ≜ δ1 [t] δ2 [t] . . . δn [t] , where the ages take values from S = Zn+ while discrete time t ∈ Z+ . Next, we define the Self-Adaptive Threshold ALOHA (SATA) policy.
III. SATA We consider a threshold-based random access policy in which, if a node transmits successfully, it waits for Γ time slots before becoming active with a stationary probability τ [3]. In such systems, the number of active users, denoted as m[t], is time-varying. In Threshold-ALOHA [4], asymptotically, it is shown that m[t] converges in probability to k0 n, where k0 is a constant between 0 and 1. Unlike Threshold ALOHA, in SATA, if a node’s AoI state exceeds Γ, it transmits with an adaptive probability τi [t] ∈ (0, 1], adjusted based on the network state belief. Also, a node transmits with probability 1 if its AoI state is equal to Γ. In that case, all active nodes stay silent, so that the one with δi [t] = Γ successfully transmits with probability 1 [6]. The number of active nodes at time slot t, denoted as m[t], is defined as n X m[t] ≜ 1{δi [t] > Γ}. (5) i=1
According to our policy, the adaptive transmission probability for node i at time t is defined as a function of m[t] δi [t] = Γ 1, (6) τi [t] = pm , δi [t] > Γ & ∄δj [t] = Γ ∀j ̸= i 0, otherwise, where pm is the throughput-optimal choice of transmission probability, that is, the reciprocal of the number of active users, 1 m[t] , [9]. Notably, if more than one user has the same inactive state in the initial network state, their states will grow until state Γ; they transmit with probability 1 and collide. It is a transient condition that lasts at most Γ − 1 time slots. IV. A NALYSIS OF SATA From (6), we truncate AoI states at Γ + 1, which describes δi [t] > Γ. Therefore, AoI processes δi [t] can be described by their truncated versions AΓi [t] and it evolves as node i successfully 1, Γ Ai [t] = transmits at t − 1, min(AΓi [t − 1] + 1, Γ + 1), otherwise. (7) The network state can also be defined as the vector of truncated AoI processes: AΓ [t] = AΓ1 [t] AΓ2 [t] . . . AΓn [t] , which forms a finite-state Markov Chain (FSMC) with state space S Γ = {1, 2, . . . , Γ + 1}n . As the network is symmetric, all active nodes have the same successful transmission probability ps [t] at time slot t, given that there does not exist a node with state Γ. Accordingly, the successful transmission probability of an active node can be written as ps [t] = pm (1 − pm )m[t]−1 ,
(8)
where pm denotes the transmission probability of active nodes. Using (8) and (5), the transition probability matrix P Γ of the FSMC AΓ [t] can be constructed.
3
The probability that exactly one active node succeeds in a contention slot with m active users is
7
#10
4
SATA - Simulation SATA - Upper Bound 1-persistent TSA
qm = mpm (1 − pm )m−1 > 0.
(9)
where SATA sets pm = 1/m, with q1 = 1 for the single-user case. A. Network State Belief Each node keeps a network state belief, denoted as BΓ [t]. After receiving the 1-bit feedback at the end of each time slot, nodes update their beliefs recursively. Since SATA sets the access probability according to the current number of active users, decentralized implementation requires every node to determine m[t] without explicit state exchange. The following lemma establishes that the belief state BΓ [t] is sufficient to determine the number of active users at every slot. Lemma 1. In a random-access network with n nodes under SATA, 1-bit feedback is sufficient to determine the number of active users, provided all nodes know the initial network state.
Transient Duration
6 5 4 3 2 1
0
200
400
Lemma 1 states that starting from any known initial state A [0], nodes can uniquely determine the state transition using the 1-bit feedback at every time slot t, since the AoI evolution can be uniquely inferred from the 1-bit feedback as in (7). This enables decentralized adaptation of the transmission probability based on the current number of active users, m[t]. Also, nodes can determine whether there is a node with state Γ and remain silent if so. Definition 1. The absorbing set can be defined as: D = {AΓ ∈ S Γ : AΓi ∈ {1, 2, ..., Γ}, AΓi ̸= AΓj , ∀i ̸= j}. The set D consists of states in which all nodes have distinct ages below or at the threshold. Consequently, at most one node reaches Γ in any slot, so transmissions within D are collisionfree. The next proposition shows that SATA reaches this set from any initial state in finite time and remains there thereafter. Proposition 1. Let Γ ≥ n and let AΓ [0] ∈ S Γ be any initial state. The target set can be defined as D = {AΓ ∈ S Γ : AΓi ∈ {1, 2, ..., Γ}, AΓi ̸= AΓj , ∀i ̸= j}, and let τD ≜ inf{t ≥ 0 : AΓ [t] ∈ D} denote the first hitting time of D by the network state. Then for any initial state AΓ [0] ∈ S Γ , the process reaches D in finite time almost surely: Pr(τD < ∞) = 1. Proof. See Appendix B. Proposition 1 therefore reduces the long-run behavior of SATA to a periodic collision-free regime. Once D is reached, each node succeeds exactly once every Γ slots. This periodic structure immediately determines the long-term AoI and throughput.
800
1000
Fig. 2. Transient duration of SATA as the network size varies from 50 to 1000 for 102 iterations of 105 time slots.
Proposition 2. For Γ ≥ n, the long-term average AoI and throughput of SATA are: Γ+1 , 2
∆=
Proof. See Appendix A. Γ
600
Network Size
η=
n . Γ
Proof. See Appendix C. In particular, setting Γ = n gives ∆=
n+1 , 2
η = 1,
matching collision-free TDMA in the long run. Long-run performance alone, however, does not indicate how quickly this regime is reached. Over a finite operating horizon, a long transient can contribute substantially to the realized AoI. We therefore next characterize the time required for SATA to enter D. B. Transient Analysis When a node transmits successfully, its AoI resets to 1, and it remains silent until its age reaches Γ. Upon reaching Γ, it deterministically transmits with probability 1, and this periodic transmission pattern repeats every Γ time slots for the rest of the network operation. As a result, the transient period consists of two types of time slots: contention slots, during which the m active nodes compete for channel access, and periodic slots, during which previously successful nodes transmit deterministically. The coexistence of contention and periodic slots leads to an irregular transmission pattern, motivating the derivation of the expected transient duration, E[τD ]. To this end, we assume the threshold equals the network size, Γ = n. Theorem 1. Under Γ = n and pm = m−1 , the hitting time τD has an exponentially decaying tail, and consequently, it scales with the network size as E[τD ] = O(n log n), and the upper bound has the form E[τD ] ≲ 2.18n log n. Proof. See Appendix D.
4
3000
Average AoI
gains increasing as network size grows. Future work includes extending the framework to imperfect feedback, heterogeneous networks, and different network goals beyond information freshness.
SATA SATA (steady state) Slotted ALOHA Threshold ALOHA 1-persistent TSA TDMA
2500
2000
R EFERENCES
1500
1000
500
0 0
200
400
600
800
1000
Network Size
Fig. 3. Average AoI as the network size varies from 50 to 1000 for 102 iterations of 105 time slots.
V. S IMULATION R ESULTS In Fig. 2, the transient durations of SATA and 1-persistent TSA [6] are shown. For 1-persistent TSA, we used their optimal parameters, Γ = 2n − 1 and τ = 2.5/n, and for SATA, Γ = n and τ is adaptive as in (6). In [6], it is reported that the transient duration of 1-persistent TSA is 1045 for n = 100 and Γ = n, for which the transient duration of SATA is approximately 1000. As n increases, the upper bound of SATA becomes looser, yet it still yields finite durations. The transient performance of SATA is superior to 1-persistent TSA. Notably, SATA converges to a steady-state TDMA in a reasonable finite time for network sizes between 50 and 1000, while 1-persistent TSA converges to a collision-free steadystate with cycle length 2n − 1. Fig. 3 presents the performance comparison of Slotted ALOHA, Threshold ALOHA (TA) [4], 1-persistent TSA [6], TDMA, and SATA. We have performed Monte Carlo simulations for Fig. 3 except TA, whose theoretical result is presented. In small network sizes (e.g., between 50 and 200), TA might not reach its theoretical limit, which is based on asymptotic analysis. In this case, SATA outperforms even TA’s best performance. 1-persistent TSA and TA are evaluated with their optimal parameters. As n increases, SATA’s performance gain becomes more pronounced relative to the benchmark policies. Notably, SATA works for a wide range of network sizes, as it is an adaptive policy with non-asymptotic analysis. SATA is the only policy that achieves performance closest to TDMA. The small difference between the results for SATA and TDMA is due to SATA’s transient duration. Notably, at steady state, the performance of SATA is identical to TDMA. VI. C ONCLUSION We proposed Self-Adaptive Threshold ALOHA (SATA), a distributed random-access policy to minimize the Age of Information (AoI). Using only 1-bit channel feedback, nodes can track the network state and adapt their transmission probabilities without explicit coordination. We showed that SATA converges to a collision-free TDMA regime in finite time for Γ ≥ n, derived closed-form expressions for the steady-state average AoI and throughput, and established bounds on the expected transient duration. Simulation results show that SATA achieves performance close to TDMA and significantly outperforms existing threshold-based random-access policies, with
[1] R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 5, pp. 1183–1210, 2021. [2] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in IEEE INFOCOM, 2012. [3] D. C. Atabay, E. Uysal, and O. Kaya, “Improving age of information in random access channels,” in IEEE INFOCOM WKSHPS, 2020. [4] O. T. Yavascan and E. Uysal, “Analysis of slotted aloha with an age threshold,” IEEE J. Sel. Areas Commun., 2021. [5] X. Chen, K. Gatsis, H. Hassani, and S. S. Bidokhti, “Age of information in random access channels,” IEEE Transactions on Information Theory, vol. 68, no. 10, pp. 6548–6568, 2022. [6] P. S. Dester, R. D. Souza, and P. Cardieri, “Analysis of the 1-persistent age threshold slotted aloha,” IEEE Communications Letters, vol. 30, pp. 1066–1070, 2026. [7] C. Cavalagli, L. Badia, and A. Munari, “Reinforcement learning for age of information aware transmission policies in slotted aloha channels,” in IEEE ISWCS, 2024, pp. 1–6. [8] Y. Sun, E. Uysal-Biyikoglu, R. D. Yates, C. E. Koksal, and N. B. Shroff, “Update or wait: How to keep your data fresh,” IEEE Trans. Inf. Theory, vol. 63, no. 11, pp. 7492–7508, 2017. [9] D. P. Bertsekas and R. G. Gallager, Data Networks, 2nd ed. Belmont, MA, USA: Athena Scientific, 1992.
A PPENDIX A P ROOF OF L EMMA 1 Proof. Suppose that BΓ [t] is known at the beginning of slot t. Since BΓ [t] contains the truncated AoI values, each node can determine the number of active users m[t] and the number of nodes with state Γ. We consider three cases. Case 1: No node is at state Γ. Only the m[t] active nodes may transmit. If the feedback is S, exactly one active node succeeds, so one state Γ + 1 resets to 1. If the feedback is F , no active node succeeds. In either case, all remaining states evolve deterministically according to (7). Case 2: Exactly one node is at state Γ. That node transmits with probability one while all active nodes remain silent. Hence the transmission succeeds, the state-Γ node resets to 1, and all remaining states evolve deterministically. Case 3: At least two nodes are at state Γ. All such nodes transmit simultaneously and collide, while the active nodes remain silent. Therefore, every state-Γ node moves to the active state Γ + 1, and the remaining states evolve deterministically. Thus, in all cases, BΓ [t+1] is uniquely determined by BΓ [t] and the 1-bit feedback. Starting from the known initial state BΓ [0] = AΓ [0], induction yields exact tracking of BΓ [t], and hence of m[t], for all t. A PPENDIX B P ROOF OF P ROPOSITION 1 Proof. Consider two nodes in the same inactive state, AΓi [t] = AΓj [t] < Γ. Their ages increase together until they reach Γ, where they transmit simultaneously and cause a collision. Both then move to the active state, Γ + 1, eliminating the duplicate inactive state. If an active node transmits successfully, its age resets to 1 while inactive nodes’ ages increase by 1, so no new duplicate inactive states are created.
5
The number of active nodes is denoted by m[t] (5). Let m[t] = m > 0. At a contention opportunity, the probability of a successful transmission is qm > 0, as defined in (9). Cm denotes the number of contention slots with m active users, i.e., the waiting time until the next successful transmission. Cm is geometrically distributed since the transmissions in each time slot are independently and identically distributed Bernoulli trials with probability qm . The probability of having no successful transmission of active nodes in the first k contention slots is given by Pr(Cm > k) = (1 − qm )k , k = 0, 1, . . .
(10)
Since the truncated state space is finite, there exists ϵ > 0 such that qm ≥ ϵ for every contention state with m active nodes. Therefore, Pr(Cm > k) ≤ (1 − ϵ)k .
A PPENDIX D P ROOF OF T HEOREM 1 Proof. By the duplicate-elimination argument in the proof of Proposition 1, after an initial period T0 ≤ n, all inactive states are pairwise distinct. Hence, no further threshold collisions occur, and the number of active users is non-increasing. Partition the subsequent evolution into blocks of n slots, and let Mk denote the number of active users at the beginning of the k-th block. Since Γ = n, each of the n−Mk inactive users occupies exactly one deterministic transmission slot within the block. Moreover, an active user that succeeds during the block cannot reach the threshold again within the same block. Thus, the block contains Mk contention opportunities. Whenever m ≥ 2 active users remain, SATA uses pm = 1/m, and the probability of exactly one successful active transmission is m−1 1 1 ≥ , (11) qm = mpm (1 − pm )m−1 = 1 − m e
which means Cm is finite with probability 1, Pr(Cm < ∞) = 1. If we repeat this argument for every m ∈ {1, . . . , n}, m[t] reaches 0 in finite time almost surely. At that time, all node states belong to {1, . . . , Γ} and pairwise distinct, so AΓ [t] ∈ D. Hence,
with q1 = 1. Let Sk denote the number of active-user successes during block k. At every contention opportunity before all active users have succeeded, the conditional success probability is at least e−1 ; if all active users succeed earlier, then Sk = Mk . Therefore, Mk E[Sk | Mk ] ≥ . (12) e Since no new active users are created after T0 ,
Pr(τD < ∞) = 1.
Mk+1 = Mk − Sk ,
Furthermore, k
lim (1 − ϵ) = 0,
k→∞
Finally, if AΓ [t] ∈ D, at most one node can have state Γ. If such a node exists, it transmits successfully and is reset to 1, while all other states increase by 1; otherwise, all states increase by 1. In either case, the states remain pairwise distinct and within {1, . . . , Γ}. Therefore, AΓ [t] ∈ D ⇒ AΓ [t + 1] ∈ D. Hence, D is absorbing. In fact, once the process enters D, the state trajectory evolves periodically within D rather than converging to a fixed state. A PPENDIX C P ROOF OF P ROPOSITION 2 Proof. Proposition 1 establishes the existence of a steady state, in which all n nodes operate in a TDMA fashion, each transmitting successfully exactly once every Γ time slots. Consider node i transmitting successfully at time t = kΓ + c for some constants k ∈ Z+ and 0 ≤ c ≤ Γ − 1. Following this transmission, the AoI of node i is reset to 1 and increases by 1 each subsequent time slot until its next successful transmission at t = (k + 1)Γ + c. Therefore, over one complete period of Γ slots, the AoI of node i takes values 1, 2, . . . , Γ, giving a long-term average AoI of Γ+1 2 . As the condition Γ ≥ n ensures that there are n periodic transmissions within each period without collision, exactly n successful transmissions occur every Γ slots, yielding a throughput of Γn .
and hence E[Mk+1 | Mk ] ≤
1 1− e
Mk .
Taking expectations and iterating yields k 1 E[Mk ] ≤ n 1 − . e
(13)
(14)
Since the transient has not ended after k blocks only if Mk ≥ 1, Markov’s inequality gives Pr(τD > T0 + kn) ≤ Pr(Mk ≥ 1) k 1 ≤n 1− . e
(15) (16)
Thus, τD has an exponentially decaying tail. To bound its expectation, define 1 log n α ≜ − log 1 − , k0 ≜ . e α Grouping the tail probability over blocks of n slots gives E[τD ] ≤ T0 + n
∞ X
Pr(τD > T0 + kn)
(17)
k=0
≤ T0 + n (k0 + e) (18) n log n = + O(n) = O(n log n). (19) α Since 1/α ≃ 2.18, the leading-order upper bound is 2.18 n log n, completing the proof.