跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2609.09934 · v3

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

Plínio Santini Dester
cs.IT
首次提交 2026-09-09 17:26
版本更新 2026-10-28 11:22
雷达观测 2026-10-30 09:53
arXiv ↗PDF ↗

摘要

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.

作者备注：Submitted to Wireless Networks

查看 arXiv 原文 ↗阅读 PDF ↗

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存，登录后共享已有结果。

版本差异

仅对比实际观测的元数据，不代表 PDF 正文或实验变化。版本可能不连续；带删除线为移除，下划线为新增。

摘要变化

Goal-orientedDecentralized sensing,networks estimation,can andlearn controlcollision-free benefitperiodic fromtransmission promptschedules, regularbut accessacquisition tocan task-relevantconsume updates.much Althoughof 1-persistenta age-thresholdfinite slottedoperating ALOHAhorizon. (1-pTSA)We cancharacterize self-organizeacquisition intoin a periodicreservation collision-freeprotocol schedule,for itsa acquisitionfixed transientpopulation canof dominate$n$ finite-horizonnodes performance.and Wea proposeperiod role-protectedof counter-threshold$Γ_n\ge slottedn$ ALOHAslots. (RP--CTSA)Initially, whicheach separatesnode reservationattempts memoryindependently fromin theeach ageslot ofwith informationprobability (AoI)proportional to $1/n$. A scheduledsuccess singletonreserves retainsa itsslot phasethat afterthe collidingnode withreuses activeevery contenders,$Γ_n$ whereasslots, aretaining collisionit involvingafter multiplecollisions. scheduledNodes nodesuse releasesonly themtheir immediately;own AoIacknowledgments resetsand onlysmall afterlocal amemory. decodedAn update.exact Thefinite-population protocolMarkov requiresreduction, individualindependent acknowledgmentsof andthe aarrangement binaryof RELEASE/HOLDreserved indicationslots, butcharacterizes nothe centralizedtime phaseuntil assignmentevery ornode identificationhas ofa collidersdistinct reservation. LetAs $n\to\infty$, denotemean theacquisition numbertakes of$O(n^2)$ nodesslots when $Γ_n=n$ and $O(n\log n)$ slots when $Γ_n\sim(1+θ)n$, thefor counterfixed threshold$θ>0$. UnderWith inversea fixed number $Γ_n-populationn$ accessof scalingspare slots, the standard deviation of acquisition dynamicstime admithas anthe exactsame pure-deathasymptotic representationorder as its mean. WhenIf that number diverges while $Γ_n=/n$ remains bounded, the acquisitionratio timeof isstandard deviation to mean tends to zero. A diverging sublinear number of spare slots yields $Oo(n^2)$; whenmean acquisition while long-run utilization, the fraction $Γ_n\sim(1+θ)n/Γ_n$, of slots with $θ>0$,successful ittransmissions, istends $O(n\logto n)$one. Simulations confirmvalidate boththese regimeslaws and show substantialcompare finite-horizonacquisition AoIand gainsdelivered overpackets 1-pTSAper whileslot preservingwith everyexisting collision-freeaccess scheduleprotocols.

观测到的版本

相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。

v3 · 2026-10-28 11:22 · 最新观测版本

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

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.

查看此版本解读 →查看此版本原文 ↗
v2 · 2026-10-27 20:27

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

Goal-oriented sensing, estimation, and control benefit from prompt, regular access to task-relevant updates. Although 1-persistent age-threshold slotted ALOHA (1-pTSA) can self-organize into a periodic collision-free schedule, its acquisition transient can dominate finite-horizon performance. We propose role-protected counter-threshold slotted ALOHA (RP--CTSA), which separates reservation memory from the age of information (AoI). A scheduled singleton retains its phase after colliding with active contenders, whereas a collision involving multiple scheduled nodes releases them immediately; AoI resets only after a decoded update. The protocol requires individual acknowledgments and a binary RELEASE/HOLD indication, but no centralized phase assignment or identification of colliders. Let $n$ denote the number of nodes and $Γ_n$ the counter threshold. Under inverse-population access scaling, the acquisition dynamics admit an exact pure-death representation. When $Γ_n=n$, the acquisition time is $O(n^2)$; when $Γ_n\sim(1+θ)n$, with $θ>0$, it is $O(n\log n)$. Simulations confirm both regimes and show substantial finite-horizon AoI gains over 1-pTSA while preserving every collision-free schedule.

查看此版本解读 →查看此版本原文 ↗