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

I. INTRODUCTION

• Age-aware thinning and TSA leave random contention, while MiSTA adds control signaling and collision sensing; 1-persistent TSA can converge prohibitively slowly near N [11, 12, 13, 14].Source: §I · p. 1
• At age threshold T, an agent transmits at its local frame head and, after failure, retries once in a uniformly selected remaining slot.Local frames need not align; access uses local state and acknowledgment feedback.Source: §I · p. 2
• AFRA converges almost surely to collision-free periodic operation when L ≥ T > N ≥ 2 and has closed-form steady-state throughput, average AoI, and average peak AoI results.Simulations also evaluate transient behavior and finite-window AoI against Original TSA, 1-persistent TSA, and SAT, with TDMA as an ideal reference.Source: §I · p. 2
• AFRA’s faster convergence lets it use smaller age thresholds effectively, improving information freshness over finite observation windows.Source: §I · p. 2

A. Network and Channel Model

• The model has N ≥ 2 agents sending updates over a shared, single-hop wireless channel to one AP, without orthogonal channels or a central scheduler.Source: A. Network and Channel Model · p. 2
• Simultaneous transmissions collide and all fail; error-free ACKs are the only receiver feedback, and agents exchange no coordination messages.Source: A. Network and Channel Model · p. 2

B. Age of Information

• AoI is the elapsed time since the latest successfully received update was generated.Source: B. Age of Information · p. 2
• A successful delivery resets age in the next slot, while silence or collision increases it by one.Under generate-at-will traffic, each transmission samples a fresh report, so a retry is a new attempt rather than retransmission of a queued report.Source: B. Age of Information · p. 2
• Time-average AoI measures typical freshness at the AP, while average peak AoI averages slot-beginning age in successful transmission slots.The latter records sampled age peaks before resets and assumes infinitely many successful deliveries.Source: B. Age of Information · p. 2
• Throughput is the average number of reports delivered per slot by the system, bounded between 0 and 1.Source: B. Age of Information · p. 2

C. Distributed Access Protocol

• Each agent tracks its age, frame position Q_i(t), and retry position R_i(t), with inactive agents represented by Q_i(t) = −1 and R_i(t) = 0.At each frame start, the retry position is drawn uniformly from {1, ..., L−1}.Source: C. Distributed Access Protocol · p. 3
• At age threshold T, an inactive agent starts a length-L local frame, transmits at its head, and independently draws one retry position from the remaining slots.The retry position is uniform over {1, ..., L−1}.Source: C. Distributed Access Protocol · p. 3
• If the frame-head attempt fails, the agent retries once at its selected position; after two failures, it starts a new frame when the current one ends.Any successful attempt resets the agent to threshold-based waiting and cancels a pending retry.Source: C. Distributed Access Protocol · p. 3, Figure 2 · p. 3
• Agents’ local frames start independently, so AFRA requires shared slot boundaries but no aligned frames, inter-agent signaling, global slot index, or central scheduler.Each agent uses its own age and two local variables, together with acknowledgment feedback.Source: C. Distributed Access Protocol · p. 3
• The example timeline aligns AoI with transmission decisions, frame position, and retry position for T = L = 5.It illustrates failed attempts, a successful retry, and cancellation of a pending retry after a successful frame-head transmission.Source: C. Distributed Access Protocol · p. 3, Figure 2 · p. 3

III. THEORETICAL ANALYSIS

• AFRA enters a collision-free periodic regime almost surely from any legal initial state when L ≥ T > N ≥ 2.The analysis describes this regime as TDMA-like.Source: §III · p. 3
• The analysis derives closed-form expressions for AFRA’s steady-state throughput, average AoI, and average PAoI.Source: §III · p. 3
• The section formulates AFRA’s Markov state and establishes the system’s long-run behavior.It identifies a closed set of TDMA-like states with collision-free periodic operation.Source: §III · p. 3

A. Markov State Formulation

• The joint state X(t) consists of each agent’s triple X_i(t) = (Δ_i(t), Q_i(t), R_i(t)).These components represent age, frame position, and retry position, respectively.Source: A. Markov State Formulation · p. 3
• The system state is a time-homogeneous Markov chain because decisions and channel outcomes follow from the current state, while randomness comes from independent retry-position redraws.The redraw occurs at frame starts.Source: A. Markov State Formulation · p. 4
• A successful delivery updates an agent to (1, −1, 0); without success, its age increases and its frame state either advances or restarts with a fresh retry draw.The transition branches distinguish successful delivery from no delivery, and the redraw is uniform on {1, ..., L−1}.Source: A. Markov State Formulation · p. 4

B. TDMA-Like Steady-State Set

• A TDMA-like state has distinct agent ages in {1, ..., T}; agents below threshold T are inactive, while an agent at T is at its frame head.Source: B. TDMA-Like Steady-State Set · p. 4
• The TDMA-like set is nonempty if and only if T ≥ N.Its states assign distinct ages from {1, ..., T} to the N agents.Source: B. TDMA-Like Steady-State Set · p. 4
• Once the system enters the TDMA-like set, at most one agent transmits in a slot, and any transmission succeeds without collision.The state remains in the set, with ages evolving under f_T and the system repeating deterministically every T slots.Source: B. TDMA-Like Steady-State Set · p. 4
• The age map f_T cyclically permutes {1, ..., T}, keeping ages distinct and producing a T-slot repeat.Source: B. TDMA-Like Steady-State Set · p. 4

C. Almost-Sure Convergence

• A state belongs to ST exactly when every agent has succeeded at least once in the preceding T slots.Recent successes imply distinct ages because at most one report succeeds per slot.Source: C. Almost-Sure Convergence · p. 4
• Under L ≥ T > N ≥ 2, AFRA enters the collision-free periodic set ST almost surely from every legal initial state.The proof constructs a finite path with positive probability to ST, then uses the finite state space to establish almost-sure convergence.Source: C. Almost-Sure Convergence · pp. 4–5
• The reachability proof clears pending retries, then schedules retry positions so collided agents can succeed without disrupting agents already operating periodically.Only finitely many frame-head collisions remain before all agents operate periodically and the system enters ST.Source: C. Almost-Sure Convergence · pp. 4–5
• The strict margin T > N is necessary for convergence from every legal initial state; when T = N, pending retries can circulate among occupied frame-head slots.At least one slot without a frame head is needed to safely absorb pending retries.Source: C. Almost-Sure Convergence · p. 5

D. Steady-State Performance

• Under L ≥ T > N ≥ 2, the system enters ST almost surely, so its transient does not affect long-run averages.Within ST, agents follow the period-T orbit and succeed once per period.Source: D. Steady-State Performance · p. 5
• In the period-T orbit, the system delivers N reports per T slots and each delivery occurs at peak age T.Each agent visits the T ages once per period.Source: D. Steady-State Performance · p. 5
• The average age in the period-T orbit is (T + 1)/2.This is the time-average age reported for each agent in steady state.Source: D. Steady-State Performance · p. 5

IV. NUMERICAL RESULTS

• The evaluation focuses on convergence and information freshness over finite observation windows.It uses the paper’s system model.Source: §IV · p. 5
• AFRA is compared with Original TSA, 1-persistent TSA, and SAT, with TDMA serving as an ideal scheduling reference.Source: §IV · p. 5
• The comparisons examine convergence time, window-averaged AoI, throughput across age thresholds, and AoI across network scales.Source: §IV · p. 5

A. Comparison with Other Access Protocols

• The N = 100 comparison uses H = 100N and 100 seeds per configuration, with threshold-based schemes initialized in an unfavorable synchronized state.Original TSA uses an empirically optimized configuration, while 1-persistent TSA uses an access probability selected to minimize expected transient time in the auxiliary model.Source: A. Comparison with Other Access… · pp. 5–6
• At T = 122, AFRA’s window AoI is 77.91, 25.9% below 1-persistent TSA’s best sampled value of 105.12; window throughput is 0.780 versus 0.510.At T = 110, AFRA reaches steady operation in about 3.8 × 10^3 slots, while none of the 1-persistent runs finishes within 10^6 slots; AFRA also has lower window AoI and higher throughput than Original TSA and SAT at the reported operating points.Source: A. Comparison with Other Access… · p. 6
• AFRA reduces window-averaged AoI by 48.5%, 27.3%, and 43.7% relative to Original TSA, 1-persistent TSA, and SAT, respectively.Fig. 3 compares team sizes over an observation window H = 100N.Source: A. Comparison with Other Access… · p. 6, Figure 3 · p. 6

• For H = 100N, AFRA reduces average AoI by 48.5%, 27.3%, and 43.7% relative to Original TSA, 1-persistent TSA, and SAT, respectively.Source: §V · p. 6
• AFRA converges almost surely to collision-free steady operation when L ≥ T > N ≥ 2.Source: §V · p. 6
• At N = 100 and T = 110, mean absorption time is approximately 3.8 × 10^3 slots, while no tested 1-persistent TSA run reached steady state within 10^6 slots.Source: §V · p. 6
• Future work will analyze time to steady state, optimize thresholds over finite observation windows, and explore reserving recurring transmission slots after success.Source: §V · p. 6