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蜂窩無線系統(tǒng)需求的回應。UMTS有時也叫3GSM，強調結合了3G技術而且是GSM標準的后續(xù)標準。UMTS分組交換系統(tǒng)是由GPRS系統(tǒng)所演進而來，故系統(tǒng)的架構頗為相像。

LTE（Long Term Evolution，長期演進):3GPP（The 3rd Generation Partnership Project，第三代合作伙伴計劃）組織制定的UMTS（Universal Mobile Telecommunications System，通用移動通信系統(tǒng)）技術標準的長期演進。

IEEE 802.16:為用戶站點和核心網絡（如：公共電話網和 Internet）間提供通信路徑而定義的無線服務。

WiMAX(?Worldwide Interoperability for Microwave Access):全球微波互聯接入。WiMAX也叫802·16無線城域網或802.16，是一項新興的寬帶無線接入技術，能提供面向互聯網的高速連接，數據傳輸距離最遠可達50km。WIMAX是又一種為企業(yè)和家庭用戶提供“最后一英里”的寬帶無線連接方案。

UE：User Equipment 用戶設備

eNB：e-NodeB。Evolved Node B，即演進型Node B簡稱eNB，LTE中基站的名稱，相比現有3G中的Node B，集成了部分RNC的功能，減少了通信時協議的層次。

PRACH（Physical Random Access Channel，物理隨機接入信道）：是UE一開始發(fā)起呼叫時的接入信道，UE接收到FPACH響應消息后，會根據Node B指示的信息在PRACH信道發(fā)送RRC Connection Request消息，進行RRC連接的建立。

LTE接入協議中定義的3層:

LTE接入協議中定義的三層

RLC(Radio Link Control，無線鏈路層控制協議)：GPRS/WCDMA/TD-SCDMA/LTE 等無線通信系統(tǒng)中的無線鏈路控制層協議。在WCDMA系統(tǒng)中，RLC層位于MAC層之上，屬于L2的一部分，為用戶和控制數據提供分段和重傳業(yè)務。

RRC（Radio Resource Control）是指無線資源控制。RRC處理UE(User Equipment)和eNodeB(Evolved Node-B)之間控制平面的第三層信息。

Random Access：

基于競爭的隨機接入流程

?random access preambles (RAPs)：是UE在物理隨機接入信道中發(fā)送的實際內容，由長度為Tcp的循環(huán)前綴CP和長度為Tseq的序列Sequence組成。

Multiple-access interference（MAI）：多址干擾是指同CDMA系統(tǒng)中多個用戶的信號在時域和頻域上是混疊的。因為CDMA系統(tǒng)為碼分多址，CDMA系統(tǒng)采用的是不同的地址碼來區(qū)分每個用戶，但多個用戶的信號在時域和頻域上是混疊的，所以在頻域在產生一定的同頻和鄰頻干擾，則為多址干擾。

吸收馬爾科夫鏈

時隙ALOHA（S-ALOHA）：思想是用時鐘來統(tǒng)一用戶的數據發(fā)送。辦法是將時間分為離散的時間片，用戶每次必須等到下一個時間片才能開始發(fā)送數據，從而避免了用戶發(fā)送數據的隨意性，減少了數據產生沖突的可能性，提高了信道的利用率。在時隙ALOHA系統(tǒng)中，計算機并不是在用戶按下回車鍵后就立即發(fā)送數據，而是要等到下一個時間片開始時才發(fā)送。

2.system Model

兩個系統(tǒng)都是OFDM-CDMA。

F個Random Access channel， P個RAP，終端選中一個RAP在選中的Random ? Access channel中傳輸?；谕昝勒?，這等于是在一個有F*P個RAP 的系統(tǒng)。

如果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要發(fā)送時，立刻通過backoff algorithm進入backlogged。

3. Uniform Backoff ?in UMTS-LTE

backlogged terminal從0到U-1中隨機選取一個數進行倒計時，數到0之后在（0，1）中隨機選一個實數。如果這個實數比persistence 概率p小，則發(fā)送package。否則在下一個slot重復倒數，最多重傳L次，否則放棄這個package進入idle。要是傳輸失敗，比如遇上collision了，又開始倒數。

4. BEB algorithm in IEEE802.16

BEB在傳輸失敗時會double 時間窗。然后在W_i內隨機選取一個數來倒數，數到零就傳。

在第K個count stage， 可以retry L次

5. 優(yōu)先級

UMTS提供8種優(yōu)先級。

p為優(yōu)先級。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)之間的零點，則穩(wěn)定系統(tǒng)。若有兩個，則為雙穩(wěn)定系統(tǒng)。

每個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作為優(yōu)先級來看吧

重傳概率pr，在某個倒數階段的最后，然后優(yōu)先級通過了可傳輸的邊界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 無優(yōu)先級

增加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表現相似。

區(qū)別：1.輕載區(qū)UB延時比BEB小 2.BEB的方差性質比UB差很多

overload區(qū)域，提高U，L，K能增加系統(tǒng)容量，減少丟包率，但也會增加延時。

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特別大時，兩個性質趨于平穩(wěn)

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.

優(yōu)先級差異越大，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.