一种限制反馈的在线无帧时隙ALOHA随机接入方案

赵玉丽 ,  张继宇 ,  刘重明 ,  赵立群

东北大学学报(自然科学版) ›› 2026, Vol. 47 ›› Issue (7) : 56 -61.

PDF (1542KB)
东北大学学报(自然科学版) ›› 2026, Vol. 47 ›› Issue (7) : 56 -61. DOI: 10.12068/j.issn.1005-3026.2026.20260036
研究论文

一种限制反馈的在线无帧时隙ALOHA随机接入方案

作者信息 +

An Online Frameless Slotted ALOHA Random Access Scheme with Limited Feedback

Author information +
文章历史 +
PDF (1578K)

摘要

针对在线无帧时隙ALOHA方案存在平均反馈次数高导致接入时延增加、最优接入概率更新滞后等问题,本文提出1种基于阈值的限制反馈在线无帧时隙ALOHA方案.该方案在分组传输前由基站向所有用户广播活跃用户数估计值,使用户端与基站可同步计算理论用户解析比例;基站实时监测理论用户解析比例与实际用户解析比例的偏差值,通过预设阈值动态决策是否需要广播更新最优接入概率.仿真结果表明,所提方案可在平均反馈次数降低约50%的条件下,达到与在线无帧时隙ALOHA方案相近的即时用户解析比例.通过灵活调整阈值参数,该方案可实现接入性能与反馈开销的有效权衡,为大规模机器类通信随机接入系统提供了1种解决方案.

Abstract

To address the issues of high average number of feedbacks that leads to increased access latency and lagged update of optimal access probability in online frameless slotted ALOHA schemes, a threshold-based online frameless slotted ALOHA scheme with limited feedback was proposed in this paper. Prior to packet transmission, the estimated number of active users was broadcast by the base station to all users, which enabled both the user terminals and the base station to synchronously calculate the theoretical user resolution rate. The deviation between the theoretical and actual user resolution rate was monitored by the base station in real time, and whether to broadcast and update the optimal access probability was dynamically determined through a preset threshold. Simulation results indicate that the proposed scheme achieves an instantaneous user resolution rate comparable to that of the online frameless slotted ALOHA scheme, while reducing the average number of feedbacks by approximately 50%. By flexibly adjusting the threshold parameter, an effective trade-off between access performance and feedback overhead can be realized by the proposed scheme, which provides a solution for random access systems in massive machine-type communications.

Graphical abstract

关键词

在线无帧时隙ALOHA / 随机接入 / 限制反馈 / 用户解析比例 / 大规模机器类通信

Key words

online frameless slotted ALOHA / random access / limited feedback / user resolution rate / massive machine-type communication

引用本文

引用格式 ▾
赵玉丽,张继宇,刘重明,赵立群. 一种限制反馈的在线无帧时隙ALOHA随机接入方案[J]. 东北大学学报(自然科学版), 2026, 47(7): 56-61 DOI:10.12068/j.issn.1005-3026.2026.20260036

登录浏览全文

4963

注册一个新账户 忘记密码

随着大规模机器类通信设备数量和突发数据流量的增长,6G将大规模机器类通信作为关键场景,以支撑工业互联网、智慧交通、环境监测、公共安全、智慧医疗等垂直行业的数字化转型[1-2].6G的连接密度可能达到108个设备/km2,端到端延迟需低于1 ms[3].如何在有限频谱资源下支持大规模机器类设备的低时延、高可靠接入,成为亟待解决的问题.
目前移动蜂窝网络大多采用基于经典时隙ALOHA(slotted ALOHA,SA)的随机接入协议.然而经典SA协议的平均吞吐量只有1/e≈0.37 packet/slot.文献[4]采用串行干扰消除(successive interference cancellation,SIC)算法,在1个固定时隙内,每个活跃设备随机选择2个时隙发送分组,使得渐进吞吐量增加到0.55 packet/slot.以此为基础,研究人员将基于SIC接收机的用户数据恢复过程模拟为纠删码的BP(belief propagation)译码过程,以提高系统吞吐量为目标,提出了基于LDPC码(low-density parity-check code)[5]、无码率码[6]和Polar码[7]的接入方案.
文献[6]详细阐述了分布式随机接入的无帧SA方法.该方法利用无码率码[8]的译码过程与SIC过程的相似性:1) 将每个用户的待发送分组看作1个输入符号,每个接收的时隙看作1个编码符号;2) 在译码过程中,编码符号数并非预先定义,而是接收端成功译码后,发送1个终止反馈给发送端,发送端停止继续产生及发送编码符号.同理,在无帧时隙ALOHA(frameless slotted ALOHA,FSA)方法中,并未提前定义碰撞周期包含的时隙数.当基站(base station,BS)发现满足碰撞周期终止条件时,以最大化吞吐量为目标自适应终止碰撞过程.文献[9]提出利用无码率码特性设计以最小化功率消耗为目标的能量分配算法,用于得到时延约束的多址接入方案.文献[10]利用与或树[11]分析方法,以碰撞周期内时隙数量为无穷大作为理论前提,得到了用户解析比例与时隙数和用户数之间的关系,并进一步以最大化用户数和吞吐量为目标,优化时隙接入概率,实现了第一类无帧时隙ALOHA协议.
为增强协议解析能力,研究人员提出了借助反馈信道优化FSA协议的方案.文献[12]受在线喷泉码的启发,将反馈策略用于FSA协议,并利用单部图描述用户-时隙之间的关系,给出即时最优用户接入概率公式,提出一种基于在线喷泉码的无帧时隙ALOHA协议,即在线无帧时隙ALOHA协议.理论分析和仿真结果都表明该方案得到优于传统FSA方案的吞吐量和分组错误率.文献[13]借鉴ZigZag可译码采用比特移位操作降低喷泉码的译码开销的优势,引入根据基站解析用户实时状态信息更新用户接入概率的动态反馈机制,通过时隙偏移策略在表示SIC过程的二部图中没有度为1的时隙的情况下,也能恢复一定数量的待解析用户,提升了FSA协议的即时用户解析比例以及吞吐量.然而,在某些应用场景中,完美的反馈信道往往并不存在.
近年来,针对反馈受限场景,研究人员提出了多种在线喷泉码的优化方案.文献[14]提出的HTLO(heuristic table-lookup strategies based on decoding overhead)算法采用启发式查表与分支定界法,在有限反馈次数下逼近最优开销;文献[15]提出的GDS(growth degree encoding scheme)方案在编码过程的完成阶段依据反馈点间隔动态调整编码符号度分布,以减少总编码符号数量;文献[16]提出的基于阈值设定的方法在译码状态变化不显著时减少反馈次数,以降低通信开销.
本文针对文献[12]提出的在线无帧时隙ALOHA方案采用反馈策略所引起的时延问题,借鉴在线喷泉码在反馈受限场景下的研究成果,提出1种基于阈值的在线无帧时隙ALOHA方案.该方案基于BS处理论用户解析比例与即时用户解析比例的差值,按需反馈最优接入概率,从而在保证即时用户解析比例的前提下,大幅降低反馈次数.

1 相关工作

假设系统共有N个活跃用户接入同一BS,所有用户按预定义的等长时隙同步传输数据,每个活跃用户在单个时隙内独立于其他用户自主决定是否发起传输.基站通过下行链路向所有用户广播初始接入概率p0以启动碰撞周期,并在接收端应用SIC技术实现多用户信号的解析.文献[12]将在线喷泉码的编码原理应用于在线无帧时隙ALOHA方案,将编码符号映射为时隙,输入符号映射为接入用户,根据BS端实时用户解析比例更新用户最优接入概率,从而提高整个系统吞吐量.

定义1 Case-u时隙[12]:若某一时隙内有u个未解析用户同时发送数据,则将该时隙定义为Case-u时隙.

用户选择时隙发送数据的过程可以用1个二部图表示,所有用户构成1个节点集合,所有时隙构成另1个节点集合,这2个集合不相交.如果第i个用户选择在碰撞周期内的第j个时隙发送数据,那么,在二部图中增加边(User i,Slot j).图1a以5个用户节点、4个时隙节点为例给出了用户选择时隙发送数据的过程.BS端采用单部图表征碰撞周期内用户的解析状态:图的节点对应碰撞周期内的活跃用户;若2个未解析用户在某一Case-2时隙的起始时刻同时发送分组,则在单部图中为这2个节点添加1条边;若某个用户被成功解析,其对应的单部图节点被标记为黑色;当图中所有节点均变为黑色时,表明所有用户均已被解析.图1a中Slot 2为Case-1时隙,采用SIC过程,因为Slot 2内只有User 2发送数据,所以User 2能够被成功解析,同时可以消去Slot 1中User 2发送数据的干扰,使得Slot 1成为1个Case-2时隙节点.图1b为User 2被求解后图1a对应的单部图.

与文献[17]中的在线编码机制类似,Case-1时隙的作用是将对应节点标记为黑色(即完成单用户解析),而Case-2时隙的作用是使得BS端的2个原本不连通的连通分量变得连通.与文献[3]中的改进的在线喷泉码机制类似,在SIC过程中,部分Case-u(u>2)时隙可在后续SIC求解过程中转化为Case-1或Case-2时隙,因此BS存储这些Case-u(u>2)时隙中传输的分组,用于后续解析.一旦单部图被更新,BS重新计算最优接入概率.若该最优接入概率的值与上一时隙的值存在差异,BS将更新后的最优接入概率反馈给所有用户.活跃用户在下一个时隙开始的位置以新接入概率为依据选择是否向BS发送分组.文献[12]通过理论分析表明,给定当前时隙的用户解析比例β,下一个时隙的最优接入概率(pa)为

pa=2.213(1-β)N.

定理1[12] 令βj为BS在第j个时隙收到分组后利用SIC得到的用户解析比例,即已成功解析用户数占总用户数的比例;令Nt,j表示第j个时隙后,第t类时隙的数量;令Pu^为基站接收到的时隙为Case-u时隙的概率.理论用户解析比例的迭代关系如式(2)~(3)所示:

β0=0,
βj=βj-1+P1^+∑t=36Nt,j-1⋅Pt→1,j(1-cj-1)N.

其中:Pq→w,j=qq-w⋅rj(1-βj-1)N(q-w)1-rj(1-βj-1)Nw表示第j个时隙后,1个Case-q时隙转变成Case-w时隙的概率;rj表示第j个时隙后可直接通过SIC解析的用户数量期望.根据单部图模型特性,未解析用户构成子图的平均度为cj=2N2,j(1-βj)N.推导可得

rj=P1^1-cj-1,
N2,j=N2,j-1+P2^+∑t=36Nt,j-1⋅Pt→2,j-P1^+∑t=36Nt,j-1⋅Pt→1,j11-cj-1-1,
Nt,j=Pt^+Nt,j-1⋅1-∑w=1t-1Pt→w,j+∑q=t+16Nt,j-1⋅Pq→t,j.

2 算法设计与分析

文献[12]指出,在碰撞周期开始阶段,用户解析概率的理论值和实际值差异不大;但是,随着时隙数增大,理论值和实际输出的用户解析比例存在一定偏差.因此,在时隙数较少时,用户端采用理论值计算优化的接入概率,则可以大幅减少BS端反馈的数据量,降低接入时延.以此为基础,本文提出1种基于已求解用户比例理论值与实际值偏差的限制反馈在线时隙ALOHA接入方案.

用户端和BS端在碰撞周期的每个时隙,均采用式(2)~(6)计算当前用户解析比例的理论值.BS端采用SIC技术求解用户发送的分组,因此BS端能够掌握任意时刻的实际用户解析比例.即,BS能够获取任意时刻的用户解析比例的理论值和实际值.

令βt为第t个时隙理论用户解析比例,βt*为第t个时隙BS获取的实际用户解析比例.BS根据Δp=βt-βt*得到理论用户解析比例与实际值之间的偏差.给定阈值δ,若Δp≤δ,BS判定当前用户解析比例的理论值与实际值之间的误差处于可接受范围内,表明用户端可依据理论用户解析比例计算的接入概率进行接入.在该种情况下,用户端在下一个时隙开始的位置,依据βt计算接入概率,将分组发送到链路上.相反,若Δp>δ,表明理论值与实际值间存在显著偏差.在此情形下,BS端启动反馈机制,向用户端反馈基于βt*计算得到的最优接入概率.用户端接收到该反馈后,在第t+1个时隙使用反馈的接入概率进行数据传输,如式(7)所示:

pt+1=2.213(1-βt)N,βt-βt*≤δ,2.213(1-βt*)N,βt-βt*>δ.

显然,反馈次数与系统性能之间存在权衡.高反馈次数(δ较小)能够及时调整最优接入概率,获得较好的即时用户解析比例,但对反馈信道的依赖性较强,会引起较高的接入时延;低反馈次数(δ较大)可降低系统对反馈信道的依赖,但可能导致即时用户解析比例下降.因此,所提方案通过控制阈值δ,实现反馈次数与用户解析比例之间的权衡.

图2为本文所提方案的整体结构图.在发送数据前,BS通过下行链路向所有用户端广播初始接入概率p0、活跃用户数N、阈值δ以启动碰撞周期.

在第一个时隙开始的位置,即t0时刻,用户端以概率p0决定是否发送数据到BS端.若接收到的分组存在碰撞,则接收端缓存发生碰撞的分组.在碰撞周期内,BS采用SIC技术,求解每个用户发送的分组,得到任意时刻的实际用户解析比例.图2中,黑色时隙表示该时隙内用户已完全解析,网状阴影表示该时隙存在多于2个用户的碰撞,点状阴影表示该时隙存在2个用户的碰撞.根据文献[12]所得结论,碰撞周期开始一段时间内,理论用户解析比例与实际用户解析比例相差不大,用户端根据理论用户解析比例,利用式(7)得到下一个时隙的接入概率;假设在第i个时隙,BS端感知到βi-βi*>δ,则BS端根据实际用户解析比例βi*,利用式(7)得到第i+1个时隙的接入概率pi+1,并反馈给用户端.在第i+1个时隙,用户端以概率pi+1决定是否发送数据到BS端.若某一时刻用户解析比例满足系统需求,则结束当前碰撞周期.

本文所提方案通过调整BS感知理论用户解析比例与实际用户解析比例的差值,决定反馈接入概率的时机,以减少反馈次数,进而降低接入时延.

3 仿真及分析

为了验证本文提出的基于阈值的在线无帧时隙ALOHA方案的有效性,本章仿真产生N∈{1 000,10 000}个接入用户,讨论所提方案的即时用户解析比例及反馈次数,并分析其与阈值的关系.每组实验结果均为1 000次独立实验所得结果的平均值,以确保结果的统计意义并消除随机波动的影响.

假设阈值δ∈{0.01,0.1,0.2},图3给出了在活跃用户数N=1 000情况下,即时用户解析比例随归一化时隙数M/N的变化曲线.分析可知,当阈值δ设定为0.01时,基于阈值的在线无帧时隙ALOHA方案可得到与文献[12]提出的在线无帧时隙ALOHA方案相近的即时用户解析比例.当归一化时隙值M/N大于1.1时,随着阈值δ增大,用户解析比例有所降低.

表1给出了不同阈值前提下,接入用户数N为1 000时,BS向用户发送反馈的次数.文献[12]提出的在线无帧时隙ALOHA方案在不设定阈值的情况下,解析全部1 000个用户所需平均反馈次数为287.30次.然而,当阈值为0.01时,平均反馈次数降至145.71次,表明本文提出的基于阈值的限制反馈方案在确保即时用户解析比例的前提下,大幅减少了反馈次数.当阈值增大到0.1和0.2时,平均反馈次数进一步减少,分别为15.20次和7.65次.结合图3可知,随着阈值增大,当归一化时隙数增大到1.1时,以一定的即时用户解析比例为代价,本文提出方案能够大幅降低反馈次数,进而减少接入时延.

进一步地,将本文提出的基于阈值的限制反馈在线无帧时隙ALOHA方案与文献[12]提出的在线无帧时隙ALOHA方案以及文献[10]提出的无帧时隙ALOHA方案进行比较分析.活跃用户总数N=1 000.根据文献[10]的参数设定,本文设置平均度G=3.07,仿真结果如图3所示.从图3可以看出,文献[12]提出的在线无帧时隙ALOHA方案以及本文提出δ=0.01的限制反馈的在线无帧时隙ALOHA方案均能够得到优于文献[10]提出的无帧时隙ALOHA方案的即时用户解析比例.当δ增大到0.1或0.2,M/N小于1.13时,限制反馈的在线无帧时隙ALOHA方案得到优于文献[10]提出的无帧时隙ALOHA方案的用户解析比例.限制反馈的在线无帧时隙ALOHA方案(δ=0.01)与文献[12]提出的在线无帧时隙ALOHA方案在M/N=1.2时,达到96%的用户解析比例.这意味着本文提出的方案在引入少量反馈的情况下,在保证最终用户解析比例的前提下,反馈次数降低为文献[12]方案的50%.

为了验证本文所提方案在用户数为10 000场景下的有效性,本章将提出的基于阈值的限制反馈在线无帧时隙ALOHA方案与文献[13]提出的带有反馈的ZDFA(ZigZag decodable frameless ALOHA)方案针对即时用户解析比例和反馈次数进行对比分析.所有方案的活跃用户数均设置为N=10 000.基于阈值的限制反馈方案的阈值设置为δ∈{0.01,0.05}.文献[13]提出的ZDFA方案设置G=3.32.图4给出了文献[12]提出的在线无帧时隙ALOHA方案、基于阈值的限制反馈在线无帧时隙ALOHA方案以及文献[13]提出的ZDFA方案的用户解析比例与归一化时隙数之间的关系曲线.

观察图4可以看出,基于阈值的限制反馈在线无帧时隙ALOHA方案与文献[12]提出的在线无帧时隙ALOHA方案能够得到近似相同的即时用户解析比例.基于阈值的限制反馈在线无帧时隙ALOHA方案在M/N>1.09时得到了比ZDFA方案更高的用户解析比例.当M/N=1.2时,基于阈值的限制反馈在线无帧时隙ALOHA方案解析了所有用户的分组.然而,在相同条件下,ZDFA方案解析了95%的用户分组.本文所提方案(δ=0.05)在M/N<1.07时与文献[12]提出的在线无帧时隙ALOHA方案得到近乎相同的用户解析比例.当M/N>1.07时,其用户解析比例相较于δ=0.01时有所下降.当M/N增大到1.12时,本文所提方案(δ=0.05)仍然取得了比ZDFA方案更高的用户解析比例.

表2列出了本文所提方案及文献[12]和文献[13]提出的无帧时隙ALOHA方案在活跃用户数为10 000情况下的平均反馈次数.

由表2可知,与文献[12]提出的无帧时隙ALOHA方案相比,本文提出的基于阈值的限制反馈方案在用户基数较大情况下也能在保证用户解析比例的前提下,有效降低反馈次数.本文方案在δ=0.01,0.05时需要平均反馈次数分别为1 238.40,35.60次就可以解析所有活跃用户.文献[13]提出的ZDFA方案需要1 063.83次反馈完成所有用户的解析.因此,本文方案在最终用户解析比例方面优于ZDFA方案,在反馈次数方面优于文献[12]提出的无帧时隙ALOHA方案.

表2 本文所提方案与文献[12]和文献[13]提出方案的

平均反馈次数

Table 2 Average number of feedbacks for proposed

scheme and schemes proposed in

references [12] and [13]

4 结 语

本文针对现有在线无帧时隙ALOHA方案平均反馈次数高导致的时延问题,提出一种基于理论和实际用户解析比例偏差的限制反馈在线无帧时隙ALOHA方案.通过设置阈值偏差,本文方案给出了一种自适应接入概率调整方法.仿真结果表明,本文提出的方案在阈值较小时,能够在保证用户解析比例的前提下,大幅降低反馈次数,减少系统接入时延.在未来的工作中,将分析理论与实际用户解析比例的偏差规律,实现基于理论用户解析比例预测的低反馈在线无帧时隙ALOHA方案.

参考文献

[1]

Chen X M, Ng D W K, Yu W, et al. Massive access for 5G and beyond[J]. IEEE Journal on Selected Areas in Communications, 2021, 39(3): 615-637.

[2]

Wu W, Zhou C H, Li M S, et al. AI-native network slicing for 6G networks[J]. IEEE Wireless Communications, 2022, 29(1): 96-103.

[3]

Wang C X, You X H, Gao X Q, et al. On the road to 6G: visions, requirements, key technologies, and testbeds[J]. IEEE Communications Surveys & Tutorials, 2023, 25(2): 905-974.

[4]

Casini E, de Gaudenzi R, Del Rio Herrero O. Contention resolution diversity slotted ALOHA (CRDSA): an enhanced random access schemefor satellite access packet networks[J]. IEEE Transactions on Wireless Communications, 2007, 6(4): 1408-1419.

[5]

Liva G. Graph-based analysis and optimization of contention resolution diversity slotted ALOHA[J]. IEEE Transactions on Communications, 2011, 59(2): 477-487.

[6]

Paolini E, Stefanovic C, Liva G, et al. Coded random access: applying codes on graphs to design random access protocols[J]. IEEE Communications Magazine, 2015, 53(6): 144-150.

[7]

Zhang Z J, Niu K, Dai J C, et al. Polar-slotted ALOHA over slot erasure channel[J]. IEEE Transactions on Vehicular Technology, 2023, 72(1): 760-771.

[8]

Luby M. LT codes[C]//The 43rd Annual IEEE Symposium on Foundations of Computer Science. Vancouver:IEEE, 2002: 271-280.

[9]

Chen X M, Jia R D. Exploiting rateless coding for massive access[J]. IEEE Transactions on Vehicular Technology, 2018, 67(11): 11253-11257.

[10]

Stefanovic C, Popovski P, Vukobratovic D. Frameless ALOHA protocol for wireless networks[J]. IEEE Communications Letters, 2012, 16(12): 2087-2090.

[11]

Luby M, Mitzenmacher M, Shokrollahi M A. Analysis of random processes via and-or tree evaluation [C] // Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. New York: Association for Computing Machinery, 1998:364-373 .

[12]

Zhang Y, Zhao L Q, Zhao Y L, et al. An improved frameless ALOHA scheme with feedback strategy[J]. IEEE Communications Letters, 2025, 29(3): 605-609.

[13]

Ogata S, Ishibashi K. Application of ZigZag decoding in frameless ALOHA[J]. IEEE Access, 2019, 7: 39528-39538.

[14]

Cai P X, Zhang Y, Wu Y C, et al. Feedback strategies for online fountain codes with limited feedback[J]. IEEE Communications Letters, 2020, 24(9): 1870-1874.

[15]

Shi P C, Wang Z Y, Li D Z. Low overhead growth degree coding scheme for online fountain codes with limited feedback[C]//International Conference on Wireless and Satellite Systems. Cham: Springer International Publishing, 2021: 456-467.

[16]

Huang J X, Fei Z S, Cao C Z, et al. Design and analysis of online fountain codes for intermediate performance[J]. IEEE Transactions on Communications, 2020, 68(9): 5313-5325.

[17]

Cassuto Y, Shokrollahi A. Online fountain codes with low overhead[J]. IEEE Transactions on Information Theory, 2015, 61(6): 3137-3149.

基金资助

中央高校基本科研业务费专项资金资助项目(N25LPY032)

AI Summary AI Mindmap
PDF (1542KB)

0

访问

0

被引

详细

导航
相关文章

AI思维导图

/

〈 〉