Distributed Adaptive Algorithms for Optimal Opportunistic Medium Access

We consider a wireless multi-access channel shared by N users, operating in a time-slotted fashion. The feasible transmission rates of the various users vary over time as a result of fading. Denote by R _i (t) the feasible transmission rate of user i in time slot t (measured for example in bits per second, bits per slot, or packets per slot). The feasible transmission rates are assumed to be independent among the various users and form a stationary sequence, i.e., R _i (1), R _i (2), ... have the same distribution as some generic random variable R _i , but may not be independent across time. We further suppose that the distribution function \(F_i(r) = {\mathbb P}\{R_i < r\}\) is continuous with positive density f _i (r) = dF _i (r) / d r > 0. The users decide to access the channel in a distributed fashion, based on a threshold strategy. Specifically, there exists some threshold value γ _i such that user i transmits in time slot t if R _i (t) > γ _i , regardless of the decisions of other users. Thus the probability that user i decides to transmit is τ _i  = 1 − F _i (γ _i ), which we will also refer to as the activity factor of user i. When a user j ≠ i transmits in the same slot as user i, this causes the transmission of user i to fail with probability p _ij , independent of anything else. The set S _i  = {j: p _ij  > 0} may be interpreted as the set of neighbors of user i in the interference ‘graph’, while the probabilities q _ij  = 1 − p _ij represent a form of channel capture allowing for arbitrary probabilistic interference constraints. Thus the transmission of user i in time slot t is successful if \({\prod_{j = 1}^{N}} {{\rm I}_{\{{R_{\!j}(t) \leq \gamma_{\!j} \mbox{ or } E_{ij}(t) = 0}\}}} = 1\), with E _ij (t) representing a 0–1 random variable which equals 0 with probability q _ij , independent of anything else, so that the probability that a given transmission of user i is successful, is \({\prod_{j = 1}^{N}} (q_{ij} + (1 - q_{ij}) F_{\!j}(\gamma_{\!j})) = (1 - p_{ij} (1 - F_{\!j}(\gamma_{\!j})))\), with the convention that p _ii  = 0 for all i = 1, ..., N. The above-described threshold strategy yields a Pareto-optimal throughput vector within the class of ‘distributed’ strategies. In order to see that, consider a ‘distributed’ strategy where user i transmits a certain fraction τ _i of the time. Given that user i transmits a fraction τ _i of the time, independent of the activity of the other users (because of the ‘distributed’ nature), it makes stochastically no difference to the other users when user i is active. For user i itself, it is best to be active when its feasible transmission rate exceeds some threshold value γ _i where τ _i  = 1 − F _i (γ _i ). Thus, for any given ‘distributed’ strategy, one can construct a threshold-based strategy that provides no worse throughputs to each of the users.

For notational convenience, define and The actual throughput or ‘goodput’ of user i in time slot t may be expressed as and the expected throughput of user i is with γ = (γ ₁, ..., γ _N ) representing the vector of threshold values.

As mentioned in the previous section, the above-described family of threshold strategies yield Pareto-optimal throughput vectors within the class of ‘distributed’ strategies. In this section we consider the problem of throughput optimization, i.e., finding a vector of threshold values which maximizes the aggregate throughput utility. We will focus on logarithmic throughput utility functions, which corresponds to weighted Proportional Fairness.

Denote by w _i  > 0 the weight of user i in the throughput optimization. Then the aggregate throughput utility function may be expressed as

Noting that \(\frac{dU_i(\gamma_i)}{d\gamma_i} = - \gamma_i f_i(\gamma_i)\), we obtain

Thus, the optimality condition becomes: Note that the latter equation has a unique solution \(\gamma_i^*\), since the left-hand side is strictly increasing in γ _i being equal to 0 for γ _i  = 0 and approaching ∞ for γ _i → ∞, while the right-hand side is nonnegative decreasing in γ _i . In particular, when p _ji  = 0 for all j ≠ i, the unique solution is \(\gamma_i^* = 0\). Indeed, it is optimal for user i to always transmit if it cannot cause any collisions to other users j ≠ i. A further important and remarkable property is that the optimal threshold value γ _i only depends on the weights w _j and transmission failure probabilities p _ji of the other users, and not on their transmission rate distributions. Inspection shows that the optimal threshold value γ _i is increasing (implying that the transmission strategy of user i becomes less aggressive) in the weights w _j and transmission failure probabilities p _ji of the other users.

In case p _ji is either 0 or 1 for all j ≠ i, the optimality condition in Eq. 1 reduces to with \(w_{- i} := {\sum_{j = 1}^{N}} w_{\!j} p_{\!ji}\), or equivalently

Now suppose that the transmission rate of user i has an exponential distribution with mean r _i , i.e., \(F_i(r) = 1 - e^{- r / r_i}\). This assumption is roughly valid when the user has a Rayleigh fading channel and the feasible rate is approximately linear in the SNR (signal-to-noise ratio). The latter approximation is reasonably accurate when the SNR is not too high. In that case, it is easily verified that \(U_i(r) = (r + r_i) e^{- r / r_i}\), and the optimality condition 2 takes the form: or equivalently which means that \(\gamma_i^* = r_i s_i^*\), with \(s_i^*\) the solution of the equation and the corresponding activity factor is \(\tau_i = e^{- s_i^*}\), independent of the mean transmission rate r _i . In particular, for symmetric weights, the optimal threshold values are proportional to the mean feasible rates of the various users, where the factor of proportionality is the solution of the equation

Substituting U _i (γ _i ) = C _i (γ _i ) (1 − F _i (γ _i )) in Eq 2, we obtain w _i γ _i F _i (γ _i ) = w _− i C _i (γ _i ) (1 − F _i (γ _i )), or equivalently, w _i γ _i  =  (w _i γ _i  + w _− i C _i (γ _i )) (1  −  F _i (γ _i )), which gives \(1 - F_i(\gamma_i) = \frac{w_i \gamma_i}{w_i \gamma_i + w_{- i} C_i(\gamma_i)}\). Noting that C _i (γ _i ) ≥ γ _i , we deduce in case p _ji  = 1 for all j ≠ i, and Hence, the collective activity factor of all the users is at most unity, and if the user’s weights are all equal, then the activity factor of each individual user is at most 1 / N. Recall that in the standard Aloha system without channel variations, the sum of the transmission probabilities of all the users is exactly equal to unity for every Pareto-optimal throughput vector [19]. Thus, the use of opportunistic medium access in the presence of channel variations reduces the optimal collective activity factor, essentially because the relative loss caused by collisions is larger.

In a symmetric scenario, it may be deduced that the optimal collective activity factor is with \(M := {\sum_{j = 1}^{N}} p_{\!ji} \leq N - 1\). In particular, the optimal collective activity factor may either be smaller or larger than unity, depending on whether (N  −  1) γ is smaller or larger than M C(γ), or equivalently whether M / (N  −  1) is smaller or larger than γ/ C(γ). Note that M / (N  −  1) provides a measure for the degree of interference among the users, while C(γ) / γ offers a proxy for the amount of channel variation.

As an alternative approach, we may work with the activity factors τ _i  = 1 − F _i (γ _i ) as the independent variables instead of the threshold values, and write, with minor abuse of notation, \(U_i(\tau_i) = {\mathbb E}\{R_i {{\rm I}_{\{{R_i > F_i^{- 1}(1 - \tau_i)}\}}}\}\). In that case, the expression for the expected throughput of user i is \(T_i(\tau) = U_i(\tau_i) {\prod_{j = 1}^{N}} (1 - p_{ij} \tau_{\!j})\) with τ = (τ ₁, ..., τ _N ). The expression for the aggregate throughput utility function is:

Noting that \(\frac{dU_i(\tau_i)}{d\tau_i} = F^{- 1}(1 - \tau_i)\), we obtain

Thus the optimality condition becomes which corresponds to Eq. 1 as F _i (γ _i ) = 1 − τ _i .

As observed before, the optimality condition 1 only involves the rate distribution function F _i (·) of user i, and the weights w _j and transmission failure probabilities p _ji of the other users, but not their rate distribution functions F _j (·). The optimal threshold values \(\gamma_i^*\) can therefore be found in a distributed fashion, as long as each user i knows the weights w _j and transmission failure probabilities p _ji of the other users. Particularly, in case p _ji is either 0 or 1 for all j ≠ i, user i only needs to know the aggregate weight \(w_{- i} = {\sum_{j = 1}^{N}} w_{\!j} p_{\!ji}\) of the other users it interferes with. When the rate distribution function F _i (·) and hence the function U _i (·) are known, Eq. 1 can then in principle be solved using numerical means. In practice, however, the function F _i (·) will not be known exactly and may exhibit non-stationary characteristics, which means that use of an adaptive algorithm based on actual rate observations is preferable.

We now proceed to specify such an algorithm, where we focus on a window-based version, but the basic concept easily extends to similar non-window-based incarnations. For convenience, we first treat the case where p _ji is either 1 or 0 for all j ≠ i, so that the optimality condition 2 applies. Below we will discuss the case of arbitrary values of p _ij .

We assume that user i operates in cycles of possibly variable lengths, where the k-th cycle consists of L _i (k) ≥ 1 consecutive time slots. Let γ _i (k) be the threshold value of user i at the beginning of the k-th cycle. In each slot of the k-th cycle, user i transmits if and only if its instantaneous rate exceeds γ _i (k). Denote by R _i (k, l) the feasible transmission rate of user i in the l-th time slot of the k-th cycle. Let the 0–1 variable \(X_i(k, l) = \text{I}_{\{R_i(k, l) > \gamma_i(k)\}}\) indicate whether user i transmits in the l-th time slot of the k-th cycle or not. At the end of the k-th cycle, we compute the fraction \(\hat{F}_i(k) = \frac{1}{L_i(k)} \sum_{l = 1}^{L_i(k)} (1 - X_i(k, l))\) as empirical estimate for F _i (γ _i (k)) and \(\hat{U}_i(k) = \frac{1}{L_i(k)} \sum_{l = 1}^{L_i(k)} X_i(k, l) R_i(k, l)\) as empirical estimate for U _i (γ _i (k)).

In view of the optimality condition 2, we next calculate the difference \(D_i(k) = w_i \gamma_i(k) \hat{F}_i(k) - w_{- i} \hat{U}_i(k)\). In case D _i (k) < 0, the current threshold value γ _i (k) is likely to be smaller than the optimal threshold value \(\gamma_i^*\), whereas in the opposite case, it is likely to be larger. Hence, in the former case it makes sense to increase the threshold, whereas in the latter case it is sensible to decrease the threshold. We will consider two specific options, (A) multiplicative updates with a constant factor and (B) additive updates with a variable step size, but alternative combinations are possible too. In option (A), we set the threshold value for the next cycle to γ _i (k + 1) = γ _i (k) (1 + ε) or γ _i (k + 1) = γ _i (k) (1 − ε), with ε > 0 a suitably small coefficient, depending on whether D _i (k) is negative or positive, respectively. In option (B), we set the threshold value for the next cycle to γ _i (k + 1) = γ _i (k) − δ _i (k) D _i (k) with δ _i (k) > 0 a sequence of coefficients such that \(\sum_{k = 0}^{\infty} \delta_i(k) = \infty\), \(\sum_{k = 0}^{\infty} \delta_i(k)^2 < \infty\).

In view of the drift condition, it is intuitively plausible that in both versions the threshold will approach the optimal value \(\gamma_i^*\) in some sense. In option (A), assuming L _i (k) ≡ L _i for all k = 1, 2, ..., the threshold value will converge to a random variable which will continue to toggle around \(\gamma_i^*\), with the magnitude of the oscillation governed by the value of ε. In option (B), the threshold value will converge to \(\gamma_i^*\) almost surely, as we will rigorously establish in the theorem below. (For mathematical convenience, we will make the common assumption that the feasible transmission rates are independent over time, but the proof arguments can be extended to scenarios where the rates show temporal correlations. A detailed convergence proof for option (A) would require a complex and lengthy mathematical treatment, and go beyond the scope of the present paper.) From a practical point of view, however, the downside of (B) is the sluggish response to changes in the underlying statistics, whereas option (A) is less accurate but more responsive. In Section 6 we will conduct numerical experiments to examine the performance of both versions (A) and (B).

The proof of Theorem 4.1 relies on a powerful convergence result for nonnegative ‘almost’ supermartingales which is stated in the next theorem.

The proof of Theorem 4.2 follows by using the definition of an ‘almost’ supermartingale and following the steps leading to Theorem 11.5 in [32], see also Chapter 10, and [20]

We are now in a position to prove Theorem 4.1.

We now briefly treat the case of probabilistic capture, where we suppose that all capture probabilities satisfy 0 < p _ij  < 1, j ≠ i, and are known exactly. Assume further that L rate samples are used before each update.

We will concentrate on user i and suppress the i index as well as the cycle index k. Let X _l , l = 1, ⋯ , L, be the indicator random variables as before, so that \({{\mathbb E}\left\{{X_l}\right\}} \!=\! 1 \!-\! F(\gamma)\). We now show that similar arguments to the above will lead to convergence to a point arbitrarily close (of O(1/L) to the root of Eq. 1).

Define then \({{\mathbb E}\left\{{A_L}\right\}}\) is decreasing in γ. Also, define so that \({{\mathbb E}\left\{{B_L}\right\}}\) is increasing in γ and the two expectations have a root 0 < γ _min < γ _L  < γ _max, for sufficiently large L. Hence, if we set D _L : = B _L  − A _L we obtain an ‘almost’ supermartingale as before.

Since at the root where ε _L →0 as L → ∞, the point of convergence can be chosen arbitrarily close to γ ^*.

In the previous section we considered the problem of throughput optimization, implicitly assuming the various users to have saturated queues, i.e., always have packets to transmit, and established the convergence of the proposed adaptive algorithm. In this section we turn our attention to a scenario with queue dynamics where users are not infinitely backlogged but have queues fed by packet arrivals, and address the stability of the adaptive transmission algorithm. Specifically, denote by A _i (t) the number of packets arriving to the queue of the ith user in the tth time slot. We assume that A _i (1), A _i (2), ... are i.i.d. copies of some discrete random variable A _i with mean \(\lambda_i = {\mathbb E}\{A_i\}\). We assume that a user only decides to transmit if its queue is non-empty and its feasible transmission rate exceeds the threshold value. Since the arrival processes are expressed in terms of packets per slot, it will be convenient to measure the feasible transmission rates in the same unit.

Let Q _i (t) represent the queue length of the ith user at the start of the tth time slot. Define as the number of packets served from the ith queue in the tth time slot, with indicating whether or not the ith user transmits in the tth time slot. The time evolution of the ith queue may then be described by the familiar recursion Observe that the queue size process Q(t) = (Q ₁(t),..., Q _N (t)) is a discrete-time Markov chain.

An important issue that arises, is (I) whether the queue process is ‘stable’ in some appropriate sense. More formally stated, for a given vector of threshold values γ = (γ ₁, ..., γ _N ), what is the stability region \(\Lambda(\gamma) \in {{\mathbb R}}_+^N\), i.e., the set of arrival rate vectors λ = (λ ₁, ..., λ _N ) for which the queue process is stable? A closely related question is (II) whether we can easily characterize the overall stability region, \(\Lambda = \cup_{\gamma \in {{\mathbb R}}_+^N} \Lambda(\gamma)\), i.e., the set of arrival rate vectors for which there exists a vector of threshold values such that the queues are stable. A further related question is (III) whether we can find threshold values that achieve stability, given that λ ∈ Λ, but without any explicit knowledge of the feasible transmission rate distributions and arrival parameters.

We will address each of the problems (I), (II) and (III) below.

We now present numerical results to further investigate the convergence properties of the adaptive algorithm described in Section 4. We consider a total of three different scenarios. Throughout, the feasible transmission rates of the various users are assumed to be independent from slot to slot, with an exponential marginal distribution and possibly user-dependent means. The threshold values are always initialized to the mean transmission rates.

In Scenario I we consider a system with N = 3 users with equal weights, mean rates of 1.0, 3.0 and 5.0, respectively, and full interference, i.e., the collision probabilities are given by p _ij  = 1 for all i ≠ j. We first examine the convergence of Algorithm (A). The length of the cycles is set to L _k  = 1000 slots, and the coefficient in the multiplicative update is taken to be ϵ = 0.001.

Figure 1 shows the behavior of the ‘drift’ term D _i (k) during the first 1,000 cycles. While the drift never reduces to zero in the presence of multiplicative updates with a constant factor, the figure confirms that the drift term cannot persistently be negative or positive. After an initial transient phase, the system rapidly settles into an equilibrium where the drift exhibits slight, random oscillations around zero.

Figure 2 plots the evolution of the threshold values γ _i (k) and illustrates that these converge to reasonably stable values which are proportional to the mean feasible transmission rates.

Figure 3 shows the transmission probabilities \(\bar{F}_i(\gamma_i(k))\) and indicates that these are equal for the various users.

The above-mentioned properties of the threshold values and transmission probabilities corroborate the results described in Section 3 for the case where the feasible transmission rates of the users are exponentially distributed. In particular, for N = 3, the solution s ^* of Eq. 4—representing the proportionality factor between the mean rates and the threshold values—is approximately 1.472, and the corresponding activity factor is roughly 0.23.

Figure 4 plots the evolution of the threshold values during the first 100 cycles when the coefficient in the multiplicative update is increased to ε = 0.01. Because of page limitations, we henceforth only present results for the threshold values and not the drift terms and transmission probabilities. As to be expected, the convergence occurs about 10 times as fast, but the amplitude of the oscillations in equilibrium is somewhat larger.

Figure 5 shows the evolution of the threshold values for Algorithm (B) with L _k  = 1 slots per update and a variable step size δ _k  = 1 / k. Thanks to the initially large and gradually reduced step size, the convergence occurs fast, and the random oscillations completely vanish in the limit, reflecting the almost-sure convergence established in Theorem 4.1.

Figure 6 shows the evolution of the threshold values for Algorithm (B) with L _k  = 1 slots per update and a constant step size δ _k  = 0.001. As a result of the constant step size, convergence occurs slower, and the amplitude of the random oscillations in equilibrium is larger.

In Scenario II, we consider a system with N = 5 users with equal weights and unit mean rates. Users only partly interfere with others, and the collision probabilities (or incidence matrix of the interference graph) are given by so that w _− 1 = w _− 2 = 2, w _− 3 = w _− 4 = 3, and w _− 5 = 4.

Figure 7 shows the evolution of the threshold values for Algorithm (B) with L _k  = 1 slots per update and a variable step size δ _k  = 1 / k. The solutions of Eq. 3 are now \(s_1^* = s_2^* = 1.472\), \(s_3^* = s_4^* = 1.744\), and \(s_5^* = 1.953\), respectively, which agree with the equilibrium values of the threshold parameters as observed in the figure.

Figure 8 plots the evolution of the threshold values for Algorithm (B) with L _k  = 1 slots per update and a constant step size δ _k  = 0.001. We observe again that convergence occurs slower as a result of the constant step size, and that the behavior in equilibrium is noisier.

In Scenario III, we consider the same system as in Scenario II, except that after 5,000 time slots, an additional user emerges and the incidence matrix of the interference graph changes to so that w _− 1  =  w _− 2  =  w _− 6  =  2 and w _− 3  =  w _− 4  =  w _− 5  =  4.

Figure 9 shows the evolution of the threshold values for Algorithm (B) with L _k  = 1 slots per update and a variable step size δ _k  = 1 / k. Once the additional user has entered the system, the solutions of Eq. 3 are \(s_1^* = s_2^* = s_6^* = 1.472\), and \(s_3^* = s_4^* = s_5^* = 1.953\), respectively, which agree with the equilibrium values of the threshold parameters in the figure. Observe however that the re-convergence after 5,000 time slots to the new equilibrium values is quite sluggish since the step size has been significantly reduced by then.

Figure 10 plots the evolution of the threshold values for Algorithm (B) with L _k  = 1 slots per update and a constant step size δ _k  = 0.001. Note that the algorithm exhibits better responsiveness and achieves substantially faster re-convergence to the new equilibrium values after 5,000 time slots due to the constant step size.