Stabilizing Multi-Channel Slotted Aloha for Machine-Type Communications

In this paper, we consider a wireless cellular system with an unbounded population of machine-type users. The system provides a number of non-interfering slotted-time channels which users contend for when sending their uplink data packets. We propose a provably stable control procedure for the channel access probability in the sense that it maintains a finite number of unserviced users in the system. We also compare the proposed algorithm against the optimal multi-channel slotted Aloha to conclude that our solution demonstrates near-optimum performance.

Olga Galinina, Andrey Turlikov, Sergey Andreev and Yevgeni Koucheryavy

To view the full version, please follow: this link.

In the Proc. of the IEEE International Symposium on Information Theory – ISIT’13, Istanbul, Turkey, July 2013 (pages 2119 - 2123).

Introduction

In wireless communications, Medium Access Control (MAC) algorithms are applied to arbitrate access of the user population to the shared channel. Currently, Aloha [1], slotted Aloha [2], and their numerous variations are the most deployed and studied solutions. The main idea of Aloha-based channel access is to defer the packet retransmission probabilistically whenever two or more users collide.

However, it is commonly known that the original (uncontrolled) slotted Aloha protocol may be unstable [3] in some scenarios. Addressing such instability, several dynamic control procedures have been proposed by [4] to prevent channel saturation. One such heuristic retransmission control algorithm, named later the Binary Exponential Backoff (BEB), allows a user to adjust its channel access probability basing on history of its own transmission attempts. Hence, the use of BEB has been increasingly attractive due to little feedback required from the channel. Not surprisingly, over the years the BEB algorithm has become a part of most wireless systems.

Currently, BEB is widely used in cellular networks (such as 3GPP LTE and IEEE 802.16), when user requests resources from the network, as well as in local area networks (such as IEEE 802.11), for actual data transmissions. Whereas these systems were performing well in practice, the community has been cautioned about the poor asymptotic behavior of the BEB algorithm. For instance, in [5] the BEB algorithm was shown to be unstable in the infinite population model. By contrast, in [6] the BEB algorithm was demonstrated to be stable for sufficiently small arrival rates and finite population model. This seeming contradiction has been due to different assumptions and definitions of stability.

We reiterate the fact that infinite population model (where every new data packet is typically treated as a separate contending user) is known to highlight the limiting performance metrics of an algorithm, whereas finite population model (typically, with unbounded queues for newly arrived packets) provides insight into the practical applicability of an algorithm. Since in conventional human-oriented networks the number of users remained relatively small, the results for infinite population model have often been treated by most practitioners as a merely theoretical exercise.

This has been true until recently, when a huge number of unattended devices became integrated into the wireless infrastructure. Industry predicts that up to 30 thousand devices can connect to a single cellular base station [7] while infrequently transmitting very small data packets. Consequently, cellular technologies are now developing enhancements to support emerging machine-type communications (MTC) [8].

This evolved vision suggests a decisive step toward the infinite population model. In such extreme conditions, the conventional BEB-based control schemes become overloaded and fail to guarantee an acceptable quality of service [9]. Hence, the incentive is growing high to seek for alternative stabilizing solutions by e.g. looking back to the classical works, such as [10], [11], or [12].

Another characteristic feature of MTC is that the system (e.g., 3GPP LTE) naturally provides a number of non-interfering channels (in time, frequency, or code) for MTC users to send their small data packets [13]. Whereas the original slotted Aloha is unstable for multiple channels [14], there are some practical works [15], [16] that propose feasible modifications. In particular, [16] and its extended version [17] build upon the control procedure from [11]. However, as no strict stability proof for infinite population model has been provided, it remains unclear whether these and many other algorithms will be stable for growing user population in MTC.

To the best of our knowledge, there has been no multi-channel algorithm that is provably stable for infinite population model in the sense that it can maintain a finite number of unserviced users in the system. We, therefore, propose our own variation of controlled slotted Aloha basing on the technique from [12] and rigorously prove its stability.

In the remainder of this paper, we first summarize the assumptions of our system model. Further, we formulate an optimal channel access algorithm, which however cannot be implemented in practical systems, and then our proposed algorithm. We show that our algorithm is stable for infinite user population and that its performance is close to the optimum.

System Model

We consider a centralized wireless system, where an unbounded number of users contend when sending their uplink data packets to a common base station. In our infinite population slotted-time model, we assume that A(t) new users arrive in slot t (e.g., according to a homogeneous Poisson point process). The random variables A(t) are independent and identically distributed, the arrival rate is E[A(t)] = λ, and E[A2(t)] < ∞.

A newly arrived user acquires exactly one packet to be transmitted and competes with other backlogged users retransmitting their packets. Once a user has transmitted its packet successfully, it permanently leaves the system. Therefore, we may employ the terms user and packet interchangeably.

The system comprises K synchronous and non-interfering channels. Once a user decides to transmit, it randomly chooses one such channel following the uniform distribution. Packet transmissions may begin only at the start of a fixed-length slot and every user is synchronized to the slotted time. Data packets from all users have equal size and last the entire slot.

When a user has a packet to send, it may attempt to transmit it in any slot. Typically, a newly arrived user will send its packet in the next available slot, whereas backlogged users retransmit probabilistically. However, following e.g. [18] we assume that the newly arrived packets are treated identically to the backlogged ones.

At the end of a slot, the base station reliably determines the event in the channel, i.e. whether the channel was idle in this time slot or that it had successful or failed transmission. The transmission is considered successful if and only if exactly one user transmits on a given channel. If two or more users attempt to transmit on the same channel, all such transmissions are considered failed and the users remain backlogged. The maximum number of retransmission attempts is unbounded. The total number of unserviced users at the slot t forms the system backlog N(t).

Every backlogged user decides whether to transmit in a particular slot with a given probability. We assume that such channel access probability is identical for all the backlogged users in the current slot and that it has been made available by the base station instantaneously and reliably at the end of the previous slot. The value of the channel access probability is determined by the base station basing on the history of the system. Various dynamic control procedures to manage this probability are considered in the rest of this paper.

Channel Access Algorithms

Optimal Control Procedure

Below we formulate the optimal procedure to control the channel access probability in our system.

We denote the channel access probability as p(λ, w), where λ is the arrival rate and w denotes the complete history of the system up to the slot t (including information about individual transmission history, channel events, new user arrivals, system backlog, etc.) We are interested in formulating the optimal control procedure p ∗(λ, w) that minimizes the mean number of backlogged users in the system n(t)= E[N(t)]:

p^*(\lambda, w) =p^*(\lambda, N(t))=\frac{K}{N(t)}

where K is the number of channels and N(t) is the system backlog at the time slot t.

In [19], the optimality of a similar control procedure in a single-channel system (that is, for K =1) has been rigorously proved. Here, we generalize the result from [19] for K> 1 and formulate it as a theorem. In existing literature (see e.g., [17]), this optimal procedure is mentioned as folklore knowledge, but we are unaware of any strict proof of this important fact.

Theorem 1. For any arrival flow such that the random variables A(t) are i.i.d., E[A(t)] = λ, and E[A2(t)] < ∞, the control procedure p = N(t) maintains the minimum number of backlogged users in the system, i.e., E[N(t; λ, p∗)] ≤ E[N(t; λ, p)] for all t =0, 1, 2, ... and any p ∈ S, where S is the set of all possible control procedures.

Proof is given in the Appendix.

In practical systems, however, the implementation of such optimal control procedure is not possible. This is due to the fact that the number of backlogged users in the system N(t) cannot be known even at the base station without prohibitive levels of additional coordination between the users. The question we seek to answer in the rest of this text is whether there is a feasible control procedure based solely on the history of channel events.

Proposed Control Procedure

Since the optimal control of channel access probability is impractical, we propose an alternative control procedure p(λ, w) based only on the channel history and not requiring any information about the system backlog. We would like it to have the highest value of the maximum stable throughput λc, which is defined as the least upper bound of arrival rates λ for which the system is stable [20].

In [12], an adaptive control procedure for the single-channel slotted Aloha has been formulated and its stability conditions have been established. Motivated by [12], we propose our own control procedure suitable for a multi-channel system.

We introduce the following random process Z(t), Z(1) = 1 with the evolution given as:

Z(t+1)=\max \left\{ 1, Z(t) +\Delta Z(t)\right\}, (2)

\Delta Z(t)=\sum_{i=1}^{K} \left( a I\{v_i(t)=0\}+b I\{v_i(t)=1\}+c I\{v_i(t) \geq 2\} \right)

where vi(t) is the number of users attempting to access the channel i at the slot t; I{vi(t)=0}, I{vi(t)=1}, I{vi(t) ≥ 2} are the indicator functions of channel events, when 0, 1, or more users attempt to access the channel, respectively; and a, b, and c are some constant values which we discuss in more detail in the next section.

Summarizing, we propose the following channel access probability control procedure for multichannel slotted Aloha, which is only based on the past channel events:

 p(\lambda, w) =p(\lambda, Z(t))=\frac{K}{Z(t)}

where the process Z(t) has been described above.

Proof of Stability

In this section, we establish stability conditions for the proposed control procedure. There is a variety of alternative definitions of stability with one of the first strict interpretations given by [21]. Most of the time, it is equivalent to stating that a stable algorithm can maintain a finite number of backlogged unserviced users with probability one [22].

We note that the random process X(t)=(N(t),Z(t)) constitutes a two-dimensional Markov chain. Therefore, the ergodicity of the process X(t) would ensure the stability of our algorithm in terms of [22] and [21]. Hence, below we determine a combination of coefficients a, b, and c of the process Z(t), such that the process X(t) is ergodic and the corresponding maximum stable throughput λc is the highest.

In order to establish the ergodicity conditions, we will further use the stability theorems for two-dimensional process formulated by [12]. We begin by obtaining the average drifts for the two-dimensional process X(t) and then calculate the boundary vectors for the average drifts of X(t).

Average Drifts

The average drifts for the process X(t) are given as:

E[N(t + 1)-N(t)|N(t)= n, Z(t)= z] , (4)

E[Z(t + 1)-Z(t)|N(t)= n, Z(t)= z] . (5)

Proposition 1. Let Y (t) represent the number of users leaving the system in the slot t; N(t)= n, Z(t)= z. Then, for a multi-channel slotted Aloha algorithm with K channels it holds:

E[Y(t)|n,z]=\frac{nK}{z}\left(1-\frac{1}{z}\right)^{n-1}.

where Yi(t) denotes the number of users that select the channel number i and successfully leave the system in the slot t. We note that E[Y (t)|n, z]= K · E[Yi(t)|n, z],i =1,K, where E[Yi(t)|n, z] can easily be calculated as:

 E[Y_i(t)|n,z]=\frac{np(t)}{K}\left(1-\frac{p(t)}{K}\right)^{n-1}=\frac{n}{z}\left(1-\frac{1}{z}\right)^{n-1}

Therefore,

 E[Y(t)|n,z]=\frac{nK}{z}\left(1-\frac{1}{z}\right)^{n-1} .

Lemma 1. The drift (4) of the process X(t) is established as:

 E[N(t+1)-N(t)|N(t)=n,Z(t)=z]=\lambda-\frac{nK}{z}\left(1-\frac{1}{z}\right)^{n-1} (6)
Proof. We denote by A(t) the number of newly arrived users and by Y (t) the number of users that successfully leave the system in the slot t. E[N(t + 1) − N(t)|n, z]= E[A(t) − Y (t)|n, z]= = E[A(t)] − E[Y (t)|n, z]= λ − E[Y (t)|n, z]. (7)

We substitute the results of Proposition 1 into (7) to obtain:

 E[N(t+1)-N(t)|N(t)=n,Z(t)=z]=\lambda -n\frac{K}{z}\left(1-\frac{1}{z}\right)^{n-1}

Lemma 2. The drift (5) of the process X(t) is established as:
E[Z(t+1)-Z(t)|N(t)=n, Z(t)=z] =
=Kc + K(a-c) \left( 1- \frac{1}{z} \right)^{n} + K(b-c) \frac{n}{z} \left( 1- \frac{1}{z} \right)^{n-1} .(8)

Proof. We consider the average increment of the process Z(t):
 E[\Delta Z(t) ] =\sum_{i=1}^{K}E[a {I\{v_i(t)=0\}}+b {I\{v_i(t)=1\}}+c {I\{v_i(t) \geq 2\}}]=
 = \sum_{i=1}^{K} ( {a }E[ I\{v_i(t)=0\}]+ {b} E[ I\{v_i(t)=1\}]+ {c} E[I\{v_i(t) \geq 2\}] ),

and find the sought expectation by using Proposition 1.

Further, we consider a particular channel. The probability that it has been chosen (i) by zero users is π0 = (1 − p(t) 1 )n, (ii) by exactly one user is π1 = np(t) 1 (1 − p(t) 1 )n−1, and (iii) by two or more users is π2 =1 − π0 − π1, where p(t)= K . Then, we can establish the expressions for the components z of the equation (9) as:
E\left[ \sum_{i=1}^{K} I\{v_i(t)=0\}\right] = \sum_{k=1}^{K} k\cdot {K \choose k} \pi_0^k (1-\pi_0)^{K-k} =
 = K \pi_0 = K(1-\frac{1}{z})^n,
E\left[ \sum_{i=1}^{K} I\{v_i(t)=1\}\right] = \sum_{k=1}^{K} k\cdot {K \choose k} \pi_1^k (1-\pi_1)^{K-k} =
 = K \pi_1 = K n \frac{1}{z}(1-\frac{1}{z})^{n-1},
E\left[ \sum_{i=1}^{K} I\{v_i(t) \geq 2\}\right] = \sum_{k=1}^{K} k\cdot {K \choose k} \pi_2^k (1-\pi_2)^{K-k} =
= K \pi_2 = K \left( 1 - (1-\frac{1}{z})^n - n \frac{1}{z}(1-\frac{1}{z} )^{n-1} \right) .
We now substitute the obtained results into the expression (9):

E\left[Z(t+1)-Z(t)|N(t)=n, Z(t)=z\right] ={K} \times
\times \left[ a\left( 1- \frac{1}{z} \right)^{n} +b \frac{n}{z} \left(1- \frac{1}{z} \right)^{n-1} + c \left( 1- \left( 1- \frac{1}{z} \right)^{n} - \frac{n}{z} \left( 1- \frac{1}{z} \right)^{n-1} \right) \right] =
= Kc +K (a-c) \left( 1- \frac{1}{z} \right)^{n} + K(b-c) \frac{n}{z} \left( 1- \frac{1}{z} \right)^{n-1}.

Boundary Vectors and Stability

In what follows, we continue by establishing the boundary vectors of the average drift. By a limit argument n2 + z2 →∞, n/z = k, we obtain the following boundary vector function µ =(µn(k),µz(k)) of the process X(t):

\mu_z(k) = \lim_{\sqrt{n^2+z^2 }\rightarrow \infty, n/z = k} E[Z(t+1)-Z(t)|N(t)=n, Z(t)=z] ,
\mu_z(k) = Kc +K (a-c) e^{-k} + K(b-c) ke^{-k} , \label{mu_z}
\mu_n(k)= \lim_{\sqrt{n^2+z^2 }\rightarrow \infty, n/z = k} E[N(t+1)-N(t)|N(t)=n, Z(t)=z] ,
\mu_n(k)= \lambda - K ke^{-k} .\label{mu_n} (11)
We now investigate the stability by solving the vector equation µ(k)||k, which is equivalent to an equation: µn(k)= kµz(k). (12) Substituting the expressions (10) and (11) into (12), we derive:

\lambda - K ke^{-k} = K\dot k(c + (a-c) e^{-k}+ (b-c)k e^{-k}), k > 0 . (13)

Here, we refer to the stability theorems in [12] for two-dimensional process and claim that the considered Markov chain is ergodic if µn(k) < 0 for all roots of (13). Next, we establish the maximum stable throughput λc.

Lemma 3. For a multi-channel slotted Aloha algorithm with K channels, the maximum stable through put λc ≤ Ke−1 .
Proof. Here, we refer to the results of [12] and [19]. The considered Markov chain X(t) is ergodic only
if the condition µn(k) < 0 holds. Hence, λ − Kke−k < 0. We also note that ke−k <e−1. Therefore,
if λ > Ke−1 then the chain is not ergodic, and, consequently, any stable throughput is always bounded by Ke−1. herefore, λc ≤ Ke−1.

We finally establish the parameters of the process Z(t), such that λc is the highest, that is, λc = Ke−1 .
Theorem 2. If for the coefficients a, b, and c of the process Z(t), where c> 0 and a< 0, it holds the
following:
 c\cdot(e-2)+a+b =0 \label{main_abc},

then the Markov chain X(t) is ergodic and λc = Ke−1.
Proof. We seek to find such values of a, b, and c that λc = Ke−1 . We also remind that for λ<λc it
holds that µn(k) < 0. firstly, we consider the maximum stable throughput λc = Ke−1 >λ. Therefore,

 K (-k_i)e^{-k_i}=- \frac{K}{e}, k_i = 1. (15)
We now substitute (15) into (13):

 0=K k \left( c+(a-c)e^{-k}+(b-c)ke^{-k} \right),
 c+(a-c)\frac{1}{e}+(b-c)\frac{1}{e} =0. (16)

Hence, satisfying the following equation provides ergodicity for any λ<λc = Ke−1: c·(e−2)+a+b =

0. It can also be proved that the Markov chain X(t) is not recurrent if a> 0 or c< 0. For that reason, we only consider such sets of coefficients, when a< 0 and c> 0.

Theorem 3. If the coefficients a, b, and c satisfy the conditions of Theorem 2, then the proposed control procedure converges to the optimal control procedure in the sense that n(t) → n ∗(t) for K →∞, where n(t) is the system backlog under the proposed control and n ∗(t) is the respective value under the optimal control.

Proof of this theorem employs the same technique as the proof of Theorem 1. But it is also using an auxiliary proposition that the random process N(t) converges to Z(t) for K →∞, and, particularly, δ(t) = (1/N(t) − 1/Z(t)) →K→∞ 0. This proposition can be proved analyzing the system behavior for K and K +1, accounting for the definition of a limit, and at the same time studying the convergence rate. We omit the proof here due to space limitations.

Numerical Results

In this section, we compare the proposed multi-channel control procedure against the optimal multichannel control. To give more insight, we also consider a single-channel procedure in the equivalent conditions, that is, when a newly arrived user is uniformly assigned a particular channel to transmit on and no channel reselection is allowed by users.

Such independent use of channels allows accounting for only one channel i with the optimal probability pi(t)=1/Ni(t), where Ni(t) is the number of users sharing this channel. The performance metrics for the single-channel case may be obtained numerically according to [19]. For other procedures, we present simulation data of 106 slots and Poisson arrivals. For the proposed control, we set the parameters of the process Z(t) (see eq. (3)) as a = −1, b = −1, and c = . These values satisfy the Th. e−2.

slotted_Aloha_img_0
figure 1: System backlog per channel for arrival rate λ =0.3 · K.

In figure 1, we fix the arrival rate per channel to be sufficiently high (i.e., λ =0.3 · K) and study the conditions of Theorem 2.average number of users in the system for all the three procedures by varying the number of available channels. From the figure, we learn that the proposed multi-channel procedure rapidly approaches optimum with the increase in K, whereas the single-channel procedure maintains independent constant performance.

slotted_Aloha_img_1
figure 2: System backlog per channel for K =5 channels.

In figure 2, we fix the number of available channels to be K =5 and again study the average system
backlog by varying the arrival rate per channel. The use of the proposed control procedure results in the
lower system backlog than that for the optimal control over a single channel, and remains close to the
multi-channel optimum in the entire range of feasible arrival rates.

Conclusion

This work considers a wireless cellular system with an unbounded population of contending users. These users share a number of non-interfering uplink channels subject to a common channel access probability advertised by the base station. Whereas we demonstrate that the optimal control of such probability is not feasible, we also detail a practical adaptive procedure that provably maintains a finite number of unserviced users in the system. With the increasing number of channels, the proposed procedure quickly converges to the optimal solution. We, therefore, conclude that our stabilized multichannel slotted Aloha algorithm is naturally suitable for future machine-type systems with large user population.

Acknowledgment
This work is supported by the Internet of Things program of Tivit, funded by Tekes, GETA, and the Academy of finland.

Appendix

To view current proofs please check the full version.

Bibliography

[1] N. Abramson, “The Aloha system – another alternative for computer communications,” in Proc. AfiPS, pp. 281–285, 1970.

[2] L. Roberts, “ALOHA packet system with and without slots and capture,” in Proc. ACM SIGCOMM, vol. 5, pp. 28–42, 1975.

[3] L. Kleinrock and S. Lam, “Packet switching in a multiaccess broadcast channel: Performance evaluation,” IEEE Trans. Commun., vol. COM-23, pp. 410–423, 1975.

[4] S. Lam and L. Kleinrock, “Packet switching in a multiaccess broadcast channel: Dynamic control procedures,” IEEE Trans. Commun., vol. COM-23, pp. 891–904, 1975.

[5] D. Aldous, “Ultimate instability of exponential back-off protocol for acknowledgment based transmission control of random access communication channels,” IEEE Trans. Inf. Theory, vol. 33, pp. 219–223, 1987.

[6] J. Goodman, A. Greenberg, N. Madras, and P. March, “Stability of binary exponential backoff,” Journ. of the ACM, vol. 35, pp. 579–602, 1988.

[7] M. Cheng, G. Lin, H. Wei, and A. Hsu, “Overload control for machine-type-communications in LTE-Advanced system,” IEEE Commun. Mag., vol. 50, pp. 38–45, 2012.

[8] G. Wu, S. Talwar, K. Johnsson, N. Himayat, and K. Johnson, “M2M: from mobile to embedded Internet,” IEEE Commun. Mag., vol. 49, pp. 36–43, 2011.

[9] M. Gerasimenko, V. Petrov, O. Galinina, S. Andreev, and Y. Koucheryavy, “Impact of MTC on energy and delay performance of random-access channel in LTE-Advanced,” Trans. on Emerging Telecom. Techn., 10.1002/ett.2631, 2013.

[10] B. Hajek and T. V. Loon, “Decentralized dynamic control of a multiaccess broadcast channel,” IEEE Trans. Autom. Control, vol. 27, pp. 559–569, 1982.

[11] R. Rivest, “Network control by Bayessian broadcast,” IEEE Trans. Inf. Theory, vol. 33, pp. 323– 328, 1987.

[12] V. Mikhailov, “Geometrical analysis of the stability of Markov chains in Rn+ and its application to throughput evaluation of the adaptive random multiple access algorithm,” Probl. Inform. Transm., vol. 24, pp. 47–56, 1988.

[13] S. Andreev, A. Larmo, M. Gerasimenko, V. Petrov, O. Galinina, T. Tirronen, J. Torsner, and

Y. Koucheryavy, “Efficient small data access for machine-type communications in LTE,” in Proc. IEEE ICC, 2013.

[14] I. Pountourakis and E. Sykas, “Analysis, stability and optimization of Aloha-type protocols for multichannel networks,” Computer Comm., vol. 15, pp. 619–629, 1992.

[15] W. Yue and Y. Matsumoto, “Output and delay of multi-channel slotted ALOHA systems for integrated voice and data transmission,” Telecom. Systems, vol. 13, pp. 147–165, 2000.

[16] D. Shen and V. Li, “Stabilized multi-channel ALOHA for wireless OFDM networks,” in Proc. IEEE GLOBECOM, vol. 1, pp. 701–705, 2002.

[17] D. Shen and V. Li, “Performance analysis for a stabilized multi-channel slotted ALOHA algorithm,” in Proc. IEEE PIMRC, pp. 249–253, 2003.

[18] A. MacKenzie and S. Wicker, “Stability of multipacket slotted Aloha with selfish users and perfect information,” in Proc. IEEE INFOCOM, pp. 1583–1590, 2003.

[19] G. Falin, “Performance evaluation for a class of algorithms of random multiple access to a radio-communication channel,” Probl. Peredachi Inf., vol. 18, pp. 85–90, (in Russian) 1982.

[20] D. Bertsekas and R. Gallager, Data Networks. Prentice Hall, 1992.

[21] B. Tsybakov and V. Mikhailov, “Random multiple packet access: Part-and-try algorithm,” Probl. Inform. Transm., vol. 16, pp. 305–317, 1980.

[22] D. Chan and T. Berger, “Upper bound for the capacity of multiple access protocols on multipacket reception channels,” in Proc. IEEE ISIT, pp. 1603–1607, 2012.