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.