Design and Analysis of Backoff Algorithms for Random Access Channels in UMTS-LTE and IEEE 802.16 Systems
1. terminology
UMTS (Universal Mobile Telecommunications System): 一种第三代（3G）移动电话技术。它使用WCDMA作为底层标准，由3GPP定型，代表欧洲对ITUIMT-2000关于3G蜂窝无线系统需求的回应。UMTS有时也叫3GSM，强调结合了3G技术而且是GSM标准的后续标准。UMTS分组交换系统是由GPRS系统所演进而来，故系统的架构颇为相像。
LTE（Long Term Evolution，长期演进):3GPP（The 3rd Generation Partnership Project，第三代合作伙伴计划）组织制定的UMTS（Universal Mobile Telecommunications System，通用移动通信系统）技术标准的长期演进。
IEEE 802.16:为用户站点和核心网络（如：公共电话网和 Internet）间提供通信路径而定义的无线服务。
WiMAX( Worldwide Interoperability for Microwave Access):全球微波互联接入。WiMAX也叫802·16无线城域网或802.16，是一项新兴的宽带无线接入技术，能提供面向互联网的高速连接，数据传输距离最远可达50km。WIMAX是又一种为企业和家庭用户提供“最后一英里”的宽带无线连接方案。
UE：User Equipment 用户设备
eNB：e-NodeB。Evolved Node B，即演进型Node B简称eNB，LTE中基站的名称，相比现有3G中的Node B，集成了部分RNC的功能，减少了通信时协议的层次。
PRACH（Physical Random Access Channel，物理随机接入信道）：是UE一开始发起呼叫时的接入信道，UE接收到FPACH响应消息后，会根据Node B指示的信息在PRACH信道发送RRC Connection Request消息，进行RRC连接的建立。
LTE接入协议中定义的3层:
LTE接入协议中定义的三层
RLC(Radio Link Control，无线链路层控制协议)：GPRS/WCDMA/TD-SCDMA/LTE 等无线通信系统中的无线链路控制层协议。在WCDMA系统中，RLC层位于MAC层之上，属于L2的一部分，为用户和控制数据提供分段和重传业务。
RRC（Radio Resource Control）是指无线资源控制。RRC处理UE(User Equipment)和eNodeB(Evolved Node-B)之间控制平面的第三层信息。
Random Access：
基于竞争的随机接入流程
random access preambles (RAPs)：是UE在物理随机接入信道中发送的实际内容，由长度为Tcp的循环前缀CP和长度为Tseq的序列Sequence组成。
Multiple-access interference（MAI）：多址干扰是指同CDMA系统中多个用户的信号在时域和频域上是混叠的。因为CDMA系统为码分多址，CDMA系统采用的是不同的地址码来区分每个用户，但多个用户的信号在时域和频域上是混叠的，所以在频域在产生一定的同频和邻频干扰，则为多址干扰。
吸收马尔科夫链
时隙ALOHA（S-ALOHA）：思想是用时钟来统一用户的数据发送。办法是将时间分为离散的时间片，用户每次必须等到下一个时间片才能开始发送数据，从而避免了用户发送数据的随意性，减少了数据产生冲突的可能性，提高了信道的利用率。在时隙ALOHA系统中，计算机并不是在用户按下回车键后就立即发送数据，而是要等到下一个时间片开始时才发送。
2.system Model
两个系统都是OFDM-CDMA。
F个Random Access channel， P个RAP，终端选中一个RAP在选中的Random Access channel中传输。基于完美正交，这等于是在一个有F*P个RAP 的系统。
如果1.不同的terminal选了同样的RAP，或者2.传输的RAP因为MAI不被BS acknowledged 则传输失败，会等一段时间再传。等待时间在UMTS-LTE中根据UB算法，在IEEE802.16中根据BEB算法。
如果RAP传输成功，terminal可以在上行通道传输请求带宽的信息，而BS会在RAR（Random Access Response）中准许。
设window size为U。terminal知道传输功率和时间，可简化UMTS-LTE中的power-ramping scheme。在UMTS-LTE中，每个BS都能指定64个RAP，其中一部分为非竞争接入保留。
在I型FDD模式中，频域中的一个Random Access channel每2个slots出现一次。（？？？）
假设：每个slot中F=1，即每个slot对应一个RAP（或一个package）。有限人口，M个terminals。idle terminal在每个slot产生package服从概率为\varepsilon的伯努利分布（两点分布）。当一个terminal有package要发送时，立刻通过backoff algorithm进入backlogged。
3. Uniform Backoff in UMTS-LTE
backlogged terminal从0到U-1中随机选取一个数进行倒计时，数到0之后在（0，1）中随机选一个实数。如果这个实数比persistence 概率p小，则发送package。否则在下一个slot重复倒数，最多重传L次，否则放弃这个package进入idle。要是传输失败，比如遇上collision了，又开始倒数。
4. BEB algorithm in IEEE802.16
BEB在传输失败时会double 时间窗。然后在W_i内随机选取一个数来倒数，数到零就传。
在第K个count stage， 可以retry L次
5. 优先级
UMTS提供8种优先级。
p为优先级。s_i为0.2到0.9之间的一位小数，N在1到8之间
6.分析
A. Channel MOdel
总共P个RAP，传输v个，其中k个成功的概率。假设针对最后一个，v个中共有m个与最后一个重复。m!=1时，在排除掉重复的m个v中另找k个来成功传输，此时RAP的种类排除掉一种，故为P-1。若m=1，则代表无重复，另找k-1个来成功传输。
传输一个package成功的概率ps。p_r为一个package的重传概率。M-1个terminal中选n个进行重传，C_{k+1,n+1}代表传n+1个中有k+1个成功的概率，那么方括号中可以表示n+1个package中成功传输数量的期望，除以n+1表示概率。
B. Uniform Backoff algorithm
πE为terminal idle的概率。第一项表示上一个slot空闲，然后接着空闲。π_{i,j}表示第i个倒数stage的第j个倒数项的概率。第二项表示倒数到零了，生成的实数小于p，而且成功传输的概率。第三项表示在极限倒数结束后随机实数在可传输范围内。
求出π_{i,j}代入后，可得
重传概率为p_r
要使p_r同时满足上式和p_s展开式，定义一个p_r的函数
若函数只有一个(0,1)之间的零点，则稳定系统。若有两个，则为双稳定系统。
每个slot传输的package数量为吞吐量τ。可以看出是个期望值。
packet-dropping probability Pd
要求平均传输时延，通常用mean-value analysis，诶就不，就要用吸收马尔科夫链。
定义成功传输用时：
d bar ：=a terminal to successfully transmit a packet, after it is generated. D_{I,j}:packet retransmission delay, an absorbing process starting from the initial backoff countervalue j at the ith backoff stage to reach (i.e., be absorbed into)the idle state.
用到的Dij性质
第一项：传且传成功，用一个slot；第二项：没传，等一个slot，又开始倒数；第三项：传，没成功，等一个slot，又开始倒数。
最终得到的D
C. BEB algorithm
类似的
这里的p作为优先级来看吧
重传概率pr，在某个倒数阶段的最后，然后优先级通过了可传输的边界p
构造函数fB
packet-dropping probability Pd
D. Stability
UB算法证明stability
UB和BEB只有stable、unstable的情况，没有bistable。
E. Access Prioritization Scheme
定义1
定义2
对UB和BEB都有
throughout
F. DWA algorithm
Notation
BS可匹配滤波，进而决定CE和CS，没有成功传输的RAP有
未成功传输的RAPs
R为正交resource数，B(t)由terminal来估计
算法伪代码
7. Numerical Studies
2000 slots + W0=20 in BEB algorithm 无优先级
增加channel总数P可以提高容量，但是system固有性质不变。M =160 and P =4 are identical to those of M =40 andP = 1.
Fig. 1. UB algorithm with different M and P . (a) Normalized throughput. (b) Mean of retransmission delay. (c) Variance of retransmission delay. (d) Packet- dropping probability.
L越大，整个过程越接近无记忆。UB with U=20(L=5)and BEB with K=5(L=0)性质接近，也就是说，一定条件下，UB可以跟BEB表现相似。
区别：1.轻载区UB延时比BEB小 2.BEB的方差性质比UB差很多
overload区域，提高U，L，K能增加系统容量，减少丢包率，但也会增加延时。
Fig. 2. Comparison of the UB and BEB algorithms with different U and L. The horizontal axis indicates the traffic load (Mε) with M = 70 (a) Throughput. (b) Mean of retransmission delay. (c) Variance of retransmission delay. (d) Packet-dropping probability.
collision probability特别大时，两个性质趋于平稳
Fig. 3. Performance of the BEB algorithm with different K, L, and M. The line with black squares indicates the case withM = 100, whereas other lines and marks indicate the cases with M = 70.(a) Throughput. (b) Mean of retransmission delay. (c) Variance of retransmission delay. (d) Packet-dropping probability.
优先级差异越大，performance差异越大。
Fig. 4. Access prioritization scheme of the UB algorithm with differential p and U. (a) Throughput. (b) Mean of retransmission delay. (c) Variance of retransmission delay. (d) Packet-dropping probability.
Fig. 5.Access prioritization scheme of the UB algorithm with differential p. (a) Throughput. (b) Mean of retransmission delay.
Fig. 6.Access prioritization scheme of the BEB algorithm with differential p and K. (a) Throughput. (b) Mean of retransmission delay. (c) Variance of retransmission delay. (d) Packet-dropping probability.
DWA in UB Algorithm:
Fig. 7. Performance comparison of the UB algorithm with or without window assignment algorithm. (a) Throughput. (b) Mean of retransmission delay. (c) Throughput. (d) Mean of retransmission delay.
网友评论