1
Optimal Channel-aware ALOHA Protocol for Random Access in WLANs with Multipacket Reception and Decentralized Channel State Information
Minh Hanh Ngo, Vikram Krishnamurthy and Lang Tong
Abstract—Perfect decentralized channel state information (CSI) is utilized to design an optimal distributed Medium Access Control (MAC) protocol for wireless local area networks (WLANs) with the multipacket reception capability, which is available in CDMA systems for example. In particular, we consider the scenario where a ?nite number of users transmit packets to a common access point via a channel-aware ALOHA protocol. We analyse the structure of the optimal channel-aware transmission policies for both the spatially homogeneous WLAN system model, where users deploy identical transmission policies, and the spatially heterogeneous WLAN system model, where users are allowed to deploy different transmission policies. It is showed that the optimal transmission policy is non-randomized and piecewise continuous with respect to the channel state. Furthermore, we prove for CDMA systems, which represent the most important example of networks with the MPR capability, that under a suitable condition, there exists a channel state threshold beyond which it is optimal not to transmit. Lastly, we propose a provably convergent stochastic approximation algorithm for estimating the optimal transmission policy for spatially homogeneous networked users. Numerical studies illustrate the performance of the algorithm and the degenerate, non-randomized structure of the optimal transmission policy.
I. I NTRODUCTION An important issue in optimizing the performance of wireless local area networks (WLANs) is to design a Medium Access Control (MAC) protocol that enhances radio resource utilization. Especially, in wireless networks, where the channel quality can vary dramatically in time and affect the error rate directly, knowledge of the channel state can be exploited for multiuser diversity and opportunistic transmission to improve the system performance. In this paper, we consider a WLAN system model where the physical layer can receive multiple packets simultaneously, depending on the channel states of the transmitting users (as in [1]), and propose an optimal channelaware distributed MAC protocol. The optimal channel-aware MAC protocol exploits multiuser diversity and results in substantial gains in the system throughput and the transmission success rates, especially when the system is heavily loaded with many active users.
M. H. Ngo and V. Krishnamurthy are with the Department of Electrical and Computer Engineering, University of British Columbia, Vancouver, BC, Canada V6T 1Z4 (email: minhn@ece.ubc.ca; vikramk@ece.ubc.ca). L. Tong is with the School of Electrical and Computer Engineering, Cornell University, Ithaca, NY 14853 (email: ltong@ece.cornell.edu).
Distributed MAC protocols that are used in practice can be broadly divided into three classes [2]: ?xed allocation MAC protocols, such as TDMA (time division multiple access); random access protocols; and reservation based protocols. The two main types of random access MAC protocols are [2], [3]: random access MAC protocols that are based on carrier sensing and collision avoidance, and ALOHA protocols. Traditionally, these MAC protocols have been designed for the collision channel model, which assumes that all packets are lost when two or more users transmit at the same time. However, in modern communication systems, due to many advances in communications and signal processing, the channel capacity is increased and the collision channel model does not necessarily hold [2], [4], [5]. For example, Code Division Multiple Access (CDMA) with random signature sequences can be implemented to allow for soft collision, where packets are not necessarily lost in the case of simultaneous transmissions. As in literature, we refer to the capability that the physical layer can receive multiple packets at the same time as the multipacket reception (MPR) capability [1], [6]. When the physical channel has the MPR capability, random access protocols such as the traditional ALOHA and CSMACD protocols are not ef?cient as they are designed with the wrong assumption that it is optimal to have exactly one user transmitting at any given time. In fact, the MPR capability changed the problem of random access considerably. This is due to the fact that in the case of simultaneous transmissions, the reception can be described by conditional probabilities in the MPR models (instead of deterministic failure) [4], [6]. While it is not immediately clear how the carrier sensing idea can be generalized for random access in MPR networks, the basic ALOHA protocol can be modi?ed to exploit the MPR capability of the physical layer. Since the introduction of the ?rst MPR channel model in [6], there has been extensive work on analysis and proposals of ALOHA-based protocols for MPR models, for example [1], [4], [7]–[9]. The (generalized) MPR model proposed in [1] is a generalization of the MPR model in [6], and allows for explicit incorporation of CSI information into the reception process at the physical layer. This channel model is suitable for wireless networks, where the channel quality affects the error rate directly. The generalized MPR (G-MPR) model in [1] also offers a framework for exploiting CSI and multiuser diversity for random access. In the paper, we consider the WLAN
2
model with the G-MPR model in [1]. The MAC protocol is a distributed channel-aware ALOHA protocol, where the Signal to Noise Ratio (SNR) represents the channel state of a user. It is assumed that every user knows its instantaneous channel state perfectly, and transmits according to its transmission policy, which maps its CSI to transmit probabilities as in [1]. The aim of this paper is to analyse the structure of the optimal channel-aware ALOHA protocol. Context and Related Work: Slotted ALOHA protocol is originally proposed for the collision channel model. The classical ALOHA protocol optimization problem is to consider the symmetric system with a collision channel model and pick a constant transmit probability, that is common to all users, to maximize the system maximum stable throughput. The expression for the maximum stable throughput is known for the symmetric ALOHA system model [10], [11] and the optimal transmit probability can be derived explicitly. In comparison, for the asymmetric ALOHA system model, the problem of determining the system maximum stable throughput and the optimal transmission probabilities is still unsolved. Stability of asymmetric ALOHA systems is analysed in [10], [12], [13]. In [6], the symmetric MPR model, where the probability that a packet is correctly received depends on the total number of transmitting nodes, is proposed. The MPR model in [6] provides a framework for designing new protocols that can achieve a signi?cantly better system throughput in comparison to the original slotted ALOHA protocol. It is proved in [6], [14], [15] that by allowing the transmit probability to be a function of the number of active nodes, a non-zero asymptotic throughput can be achieved for the MPR model. A generalization of the MPR model in [6] to the asymmetric model and the investigation of stability region is given in [16]. The MPR model in [6] is a coarse abstraction of the physical (PHY) and MAC layers where the channel states of the transmitting users do not explicitly affect the reception of packets at the base station. In [1] a Generalized MPR (G-MPR) model is proposed to provide explicit incorporation of channel states in the reception model. In the G-MPR model channel states directly affect the reception of packets. Then CSI can be exploited at the MAC layer (by allowing transmit probabilities to depend on CSI) for much higher ef?ciency [4]. The G-MPR model is suitable for a broad class of physical layers, whenever the channel state affects the error rate. In fact, the collision channel model and the MPR model in [6] are special cases of the G-MPR model. The most important instance of the GMPR model is the Signal to Interference Noise Ratio (SINR) threshold reception model [17] for Direct Sequence CDMA (DS-CDMA) systems with random signature sequences. In [1], a channel-aware ALOHA protocol that is based on channel-aware transmission policies is proposed. An expression for the system maximum stable throughput is derived for the ?nite population symmetric network model. In addition, a bound on the asymptotic maximum stable throughput is given for the symmetric system model. In [1] there is no analytical result on the structure of the optimal transmission policies. Early work of exploiting decentralized CSI includes [18] in an information theoretic setting and [19], [20], which combine ALOHA with information theoretic measures. The ALOHA
Tx. probabilities
1 C
0
Chanel state information
γ
Fig. 1. Structure of optimal transmission policy proved in this paper. The transmission policy p(γ ) is non-randomized: p(γ ) is either 0 or 1 for all γ , piecewise continuous in γ , and there exists a constant C such that p(γ ) = 0 for all channel states γ > C .
aspect of [19], [20] is relevant to our setup although the encoding strategies therein lead to the collision channel model. Main Results: We consider the problem of optimizing the channel-aware ALOHA protocol for symmetric and asymmetric wireless networks with the G-MPR model proposed in [1]. For the asymmetric network model, users are allowed to have different transmission policies. In comparison, spatially homogeneous networked users deploy a common transmission policy. The results in this paper are best understood, and directly applicable to CDMA systems with the SINR threshold reception model, which is the most important example of the G-MPR model. The main results are as follows. 1) In [1] it is proved for the symmetric network model that the system maximum stable throughput is the full-load system throughput, which corresponds to the scenario where all users are backlogged. Here we prove for the asymmetric network model that the full-load system throughput is a lower bound for the system maximum stable throughput. 2) We prove for both symmetric and asymmetric network models that, under certain conditions, the optimal transmission policies have the properties outlined by Fig. 1. In particular, the optimal transmission policies are nonrandomized, and piecewise continuous in the channel state. Furthermore, for the SINR threshold reception model for CDMA systems, which is the most important example of the G-MPR model, we prove that if a fullload system throughput greater than 2 can be achieved, there exists a constant C such that if the channel state of a user is beyond C , it is optimal for the user to not transmit. 3) An off-line stochastic approximation algorithm is proposed for estimating the optimal transmission policy, i.e. numerically solving the MAC protocol optimization problem, for the symmetric network model. The obtained MAC protocol can then be implemented in a decentralized fashion and offers substantial improvement in the system throughput. Perpective: It is well known that probabilistic transmissions are essential to obtain non-zero throughputs for the collision channel model. Similarly, for the multipacket reception model without CSI in [6], [7], probabilistic transmissions are optimal. However, in this paper we prove that optimal channel-aware transmission policies are non-randomized in the sense of Def. 2. As it will be explained carefully later, for channel-
3
aware transmission policies, randomization comes from the fact that the channel states are random variable and the proved structural results are in fact intuitive. The paper is organized as follows. The WLAN model and the G-MPR model are described in Section II. The optimization problems are formulated in Section III. Section IV and Section V contain structural results. A stochastic approximation algorithm for estimating the optimal transmission policies is proposed in Section VI. Section VII contains numerical examples. II. PACKET T RANSMISSION IN WLAN S WITH THE G-MPR M ODEL In this section we de?ne the symmetric (spatially homogeneous) and asymmetric (spatially heterogeneous) random access WLAN models, as well as the G-MPR model considered in the paper. We also introduce important concepts that are used in the paper, including the system maximum stable throughput, the stability notion, and de?nitions of pure and randomized transmission policies. In this paper the abstract G-MPR model, where channel states affect the outcome of every transmission time slot is assumed. The G-MPR model can model a broad class of physical layers [1]. In fact, the collision channel model and the MPR model in [6] are special cases of the G-MPR model. The derivation of the G-MPR model for a speci?c network requires the selection of a parameter to represent the channel state, and an explicit expression on how the channel states affect the instantaneous transmission success probabilities. In this paper SNR represents the channel state. In other MPR networks, the selection of a parameter to represent the channel state may not be immediately straightforward. For a multiple antenna system, for example, the channel state may be the best channel gain, or the mean of the channel gains. In some cases, it is possible to abstract the reception in the uplink of a multiple antenna system into the G-MPR model [1]. Throughout the paper we use the SINR threshold reception model for CDMA systems with matched ?lter or linear minimum mean square error (LMMSE) receivers as an example of the G-MPR model. Furthermore, the results in the paper are directly applicable to CDMA networks. However, most of the results (except for the existence of a threshold channel state C beyond which it is optimal not to transmit; this result is proved explicitly for CDMA networks) only assume the abstract GMPR model. In other words, as long as the channel state and the G-MPR model are well-de?ned, and satisfy the described assumptions, the analytical results proved here are applicable. This paper, however, does not concern the derivation of the G-MPR model for networks other than CDMA systems. A. Decentralized Uplink MAC Control Let i = 1, 2, . . . , K (K < ∞) index the users in a K user WLAN system with the multipacket reception capability, which means that in the presence of simultaneous transmissions, one or more packets can still be received correctly but with probabilities less than 1. An example of networks with the multipacket reception capability is CDMA systems.
We consider the uplink where all users communicate with a common base station. Assume that time is slotted and indexed by t = 1, 2, . . .. Assume Signal to Noise Ratio (SNR) represents the channel state of a user. Denote the channel state of user i by γi for all i ∈ {1, 2, . . . , K } and assume that γ i is a continuous random variable in [0, M ], where M ∈ R + and M < ∞. M can be arbitrarily large so that [0, M ] includes the entire range of CSI that is of practical interest. Denote the (channel) probability distribution function of γ i by Fi (.). Assume that the packet arrival (input) process of user i has mean λi and ?nite variance. Further assume that the arrival processes are independent across all users. De?ne the system average cumulative input rate λ by
K
λ=
i=1
λi .
(1)
We consider both asymmetric (spatially heterogeneous) and symmetric (spatially homogeneous) WLAN system models. The above description is the asymmectric WLAN system model. The symmetric WLAN system model is a special case, where the arrival rates as well as the channel state probability distribution functions of all users are identical i.e. Fi (.) = Fj (.) and λi = λj for all i, j ∈ {1, 2, . . . , K }. Assume that every user knows its instantaneous channel state realization perfectly at the beginning of each transmission time slot. A user can estimate its channel state by measuring the strength of a beacon signal or any acknowledgment (ACK) signal sent (or broadcast) by the local base station. At each time slot, every user i picks a transmit probability according to its transmission policy, which is a function mapping CSI to transmit probabilities as follows: pi (.) : [0, M ] → [0, 1]. (2)
We now de?ne pure and randomized transmission policies. De?nition 1: A randomized transmission policy is a transmit probability function p(.) : [0, M ] → [0, 1] such that 0 < p(γ ) < 1 for some non-zero measure set of values of γ. De?nition 2: A pure transmission policy is a transmit probability function p(.) : [0, M ] → [0, 1] such that p(γ ) ∈ {0, 1} for all γ ∈ [0, M ] except for possibly a zero-measure set of values of γ . (t) Let Ni be the length of the buffer of user i at time slot t. We use the stability notion of [1] and [11], i.e. the system is considered stable if for all i ∈ {1, 2, . . . , K } there exists a H (x), whose domain is Z+ (the set of non-negative integers) such that
t→∞
lim P(Ni
(t)
< x) = H (x)
limx→∞ H (x) = 1.
(3)
De?ne the throughput of a system to be the average number of packets that are transmitted and successfully received at the base station in a time slot. In addition, the maximum stable throughput is the supremum of all cumulative input (arrival) rates λ, de?ned in (1), for which the system is stable [1]. Notation: A subscript is used to index users while a superscript (k ) indicates that there are k transmitting users. A K k is any unordered set of k integers selected from 1, 2, . . . , K ,
4
i.e. AK ? {1, 2, . . . , K }. In the paper, A K k k is used to specify the set of transmitting users. γ AK = γi : i ∈ AK k k (k ) represents channel states of the users indexed by A K ; γ = k (k ) ( . ) and F ( . ) are the joint proba(γi : i = {1, . . . , k }). FAK k bility distribution functions of γ AK and γ (k) respectively. The k expected system throughput is a function of the transmission policies of all users and is denoted as L K (p1 (.), . . . , pK (.)). When it is clear which set of transmission policies are being referred to, L K (p1 (.), . . . , pK (.)) is abbreviated as L K . B. G-MPR Model We consider an identical G-MPR model to that in [1]. This G-MPR model is also used in [21]–[23]. In the G-MPR model, the probability of receiving a packet correctly depends on the channel states of all transmitting users. In particular, the outcome of a transmission time slot when k users indexed by AK k transmit belongs to an event space where each elementary event is represented by a binary k-tuple = ?i : i ∈ AK Θ AK k , k where ?i = {0, 1}, ?i = 1 indicates that the packet sent by user i is correctly received and ? i = 0 indicates otherwise. The reception capability of the system is described by a set of K functions, where the k -th function Φ(γ AK ; Θ AK ) assigns k k when k users indexed by a probability to the outcome Θ AK k with channel state γ K transmit: AK Ak k Φ(γAK ; Θ AK ) = P(ΘAK |k users tx, γAK ). k k k k (4) Equation (4) implies that the probability distribution of the outcome ΘAK is determined by the channel states of all k transmitting users. We assume that (4) is symmetric, i.e. ; Θ AK ) = Φ(Rk (γAK ), Rk (ΘAK )) Φ(γAK k k k k (5)
For the SINR threshold reception model for a DS-CDMA system with the matched ?lter receiver, (4) is given by , Θ AK )= Φ(γAK k k where ?i = I 1+
1 N
1 0
if ΘAK = (?i : i ∈ AK k ) k otherwise. γi
j ∈ AK k ?i
(8)
γj
>β ,
where I(·) is the indicator function, γ j is the channel state (SNR) of user j , N is the spreading gain and β is the SINR threshold for correct reception [17] 1 . It should be noted that the SINR threshold models derived in [17] are for instantaneous success probabilities in CDMA systems with linear receivers. In [24], [25], expressions for average bit error rates have been derived for different CDMA system models. Then, Ψ(k) (.) de?ned by (6) can be rewritten as Ψ(k) (γAK )= k I
i∈AK k
1+
1 N
γi
j ∈ AK k ?i
γj
>β .
(9)
It should also be noted that the classical collision model and the MPR model proposed in [7] are two special cases of (6) when channel states of the transmitting users are not relevant. For the classical collision model we have )= Ψ(k) (γAK k 1 0 if k = 1 k≥2
In addition, there is a straightforward translation from a MPR reception matrix in [7] to a corresponding set of K functions de?ned as in (6) using Bayesian rule. III. M AXIMUM S TABLE T HROUGHPUT AND P ROBLEM F ORMULATION Using the dominant system approach for analysing stability of Markov Chains, it is shown in [1] (Theorem 1) that a symmetric random access network is stable as long as the arrival rate is less than or equal to the expected throughput when the system is fully loaded, i.e. every user has at least one packet to transmit. That is, the maximum stable throughput of a symmetric network is equal to the expected throughput when all users are backlogged, which is in some sense the worst scenario. Due to a conjecture in [11] and Theorem 1 in [10], it can be predicted that this result in [1] can be generalized for the asymmetric model. We now show that for the asymmetric WLAN system model, the full-load system throughput is a lower bound for the system maximum stable throughput. The problem of optimizing the channel-aware ALOHA protocol is then formulated as ?nding the optimal transmission policies that maximize the full-load system throughput. The optimization problems for the asymmetric and symmetric network models are de?ned in Sections III-A and III-B respectively. Theorem 1: Consider a WLAN system of K users indexed by i = 1, 2, . . . , K with channel state probability distribution functions Fi (.) and transmission policies p i (.). Assume the
1 The
for any permutation R k of a k -element vector. (5) is also an assumption in [1], [21]. Our objective is to maximize the system throughput. That is, we are concerned with the expected total number of packets that are received correctly or the success rate. This information is represented by the following set of K functions )= Ψ(k) (γAK k
i∈AK k
. EFAK ?i |k users tx, γAK k
k
(6)
Throughout the paper we assume that EFAK ?i |k users tx, γAK k
k
≥ EFAK ?i |k + 1 users tx, γAK ,γ k
k
(7)
for all γ ≥ 0. Intuitively, (7) means that the success probability of a user decreases when one more user transmits, which is satis?ed by most non-trivial reception models, including the collision channel model. An example of the G-MPR model is the SINR threshold reception model that is derived in [17] for DS-CDMA systems with LMMSE or matched ?lter receivers. The SINR threshold reception models derived in [17] have been widely used to characterize the asymptotic performance of CDMA systems.
expression for the LMMSE receiver is very similar, see [17].
5
G-MPR model (6). The system maximum stable throughput is lower-bounded by LK p1 (.), . . . , pK (.) =
M M K
× p(γk )Ψ(k) (γ (k) )dF (γ1 ) . . . dF (γk )
K
= pi (γi ) (10) where Ψ
k=1 (k )
...
0 0
K k=0 AK k i∈Ak
K (1 ? pav )K ?k pk av k (γ
(k )
M
M
...
0 0
)dG(γ1 ) . . . dG(γk ),
M 0
(13)
j ∈ AK k
(1 ? pj (γj ))Ψ(k) (γAK )dF1 (γ1 ) . . . dFK (γK ). k
Proof: See the appendix. For symmetric networks, the system maximum stable throughput and the full-load system throughput are equivalent [1]. In what follows we formulate the MAC protocol optimization problems. A. Problem 1: Optimal distributed channel-aware MAC protocol for asymmetric WLAN systems Consider the asymmetric WLAN system of K users with the G-MPR model (6) described in Section II. We allow different users to have different transmission policies and aim to maximize the full-load system throughput given by (10), which is a lower bound of the system maximum stable throughput (Theorem 1). Denote the policy of user i by p i (.). Consider the normed linear functional space L ∞ [0, M ], which is the space of all Lebesgue measurable functions on [0, M ] that are bounded almost everywhere. The norm of a function in L ∞ [0, M ] is its essential supremum [26]. Let B L∞ [0,M ] [0, 1] be the subset of L∞ [0, M ] that contains all Lebesgue measurable functions that have norms in the range [0, 1]. The problem of optimizing the system throughput for the asymmetric network model can be formulated on B L∞ [0,M ] [0, 1] as: sup
p1 (.),...,pK (.):pi (.)∈BL∞ [0,M ] [0,1]
pav =
p(γ )dF (γ )
(14)
is the average transmit probability for each user and the distribution function G(.) is given by G(γ ) =
γ 0
p(γ )dF (γ ) . pav
(15)
The problem of optimizing the system maximum stable throughput for the symmetric network model can be formulated on the set BL∞ [0,M ] [0, 1] as
p(.)∈BL∞ [0,M ] [0,1]
max
L(p(.)),
(16)
LK (p1 (.), . . . , pK (.)) , (11)
with the underlying assumption in (16) being that the optimal transmission policy is Lebesgue measurable. Remark: The optimization problems (12) and (16) can be formulated as continuous state space, in?nite horizon, average reward constrained Markov Decision Processes (MDPs), where the dynamics of the (channel) state are i.i.d. The constraint is multilinear (polynomial for the case of a symmetric network model) and re?ects the fact that each user has to select its transmission policy independently of other users. Due to space restriction details are omitted. However, the MDP formulations of the optimization problems help clarifying that ?nding the structure of the optimal transmission policy is nontrivial and numerically solving for the optimal transmission policy is very challenging. IV. O PTIMAL T RANSMISSION P OLICIES FOR S PATIALLY H ETEROGENEOUS WLAN S YSTEMS In this section structural results for the optimization problem (12) for the asymmetric WLAN system model are proved. It is shown that the optimal transmission policies have the properties outlined in Fig. 1, i.e., the optimal transmission policies are non-randomized (Theorem 2(a)), and piece-wise continuous (Theorem 2(b)) with respect to the channel state. Furthermore, it is also proved for CDMA systems that if a system throughput greater than 2 can be achieved, there exists a limit beyond which it is optimal not to transmit. A. Optimality of pure and piecewise continuous transmission policies
? We now claim that there exists a solution p? 1 (·), . . . , pK (·) ? to (12) such that p i (·) is non-randomized in the sense of Def. 2. Furthermore, in part (b) of Theorem 2 below, it is proved that if the success rate functions (6) are piecewise continuous with respect to the channel states, the optimal transmission policies are not only pure but also piecewise continuous. Piecewise continuity of success rates means that if the channel state of a user changes, e.g., a user increases its
where the objective function L K (p1 (.), . . . , pK (.)) is given by (10). Assume the supremum of (10) can be achieved in BL∞ [0,M ] [0, 1], i.e. the optimal transmission policies are Lebesgue measurable, rewrite (11) as
p1 (.),...,pK (.):pi (.)∈BL∞ [0,M ] [0,1]
max
LK (p1 (.), . . . , pK (.)) , (12)
where LK (p1 (.), . . . , pK (.)) is given by (10). B. Problem 2: Optimal distributed channel-aware MAC protocol for symmetric WLAN systems Here we formulate the problem maximizing the system maximum stable throughput for the spatially homogeneous WLAN model, where all users have the same channel state probability distribution function, the same arrival rate and deploy the same transmission policy, i.e. F i (.) = F (.), λi = λ, pi (.) = p(.) for all i ∈ {1, 2, . . . , K }. As users are long-term symmetric, fairness is automatically guaranteed. The maximum stable throughput of the system is given in [1], and can also be derived from (10) as
K
L(p(.)) =
k=1
K (1 ? pav )K ?k k
M
M
...
0 0
p(γ1 ) . . .
6
transmit power, by an in?nitely small amount, the success rate change is also small. This condition is expressed mathematically by (17) and is in fact not very restrictive. For example, (17) is satis?ed by the SINR threshold reception model (9) for DS-CDMA systems. Theorem 2: Consider the asymmetric WLAN model described in Section II and optimization problem (12). The following results can be claimed: (a) There exists a solution ( i.e. a set of Lebesgue mea? surable transmission policies) p? 1 (·), . . . , pK (·) that maximizes the full-load system throughput (10) and p ? i (.) is nonrandomized in the sense of Def. 2 for all i ∈ {1, . . . , K }. (b) Assume that the success rate function is piecewise continuous, i.e.
γi →γ ?
, γi ) = Ψ(k) (γAk ,γ ? ), lim Ψ(k) (γAk K ?i K ?i
(17)
? ∈ [0, M ], except for possibly a zerofor all Ak K and γ measure set of values of γ ? . Then there exists a solution (i.e. a set of Lebesgue measurable transmission poli? cies) p? 1 (·), . . . , pK (·) that maximizes the full-load system throughput (10) such that p ? i (.) is non-randomized in the sense of Def. 2 and piecewise continuous, i.e.
γ →γ0
lim pi (γ ) = p? i (γ0 )
?γ0 ∈ [0, M ]
(18)
except for possibly a zero-measure set of values of γ 0 , for all i = 1, 2, . . . , K. Proof: See the appendix. Remarks: As it is remarked after the proof of Theorem 2(a), if the expected system throughput when user i transmit with positive power is almost surely different from the expected system throughput when user i does not transmit then we can claim a stronger result that solution(s) of (12) must consist of pure policies only, i.e. pure policies are strictly optimal. Verifying this condition may be hard. Nevertheless, we conjecture that this condition holds for the SINR threshold reception model for CDMA systems. Lastly, Theorem 2 actually implies that p? i (·) is piece-wise constant for all i = 1, 2, . . . , K . B. A threshold beyond which not transmitting is optimal for the SINR threshold reception model In this part of the paper we prove one more structural result for the most important example of the G-MPR model, which is the SINR threshold reception model (9) for CDMA systems. Theorem 3 states that under a mild condition, there exists a limit such that if the channel state of a user is beyond this limit, the user should not transmit. Intuitively, it is known that the performance of a CDMA system is limited by Multiple Access Interference (MAI) and an increase in the transmit power for a user implies an increase in the interference to all other users. One might then suspect that if a user has an extremely good channel state and transmits, it will likely decrease the expected system throughput. In Theorem 3, we show that this is really the case. In practice, a user should not be banned from transmitting if its channel is of super quality. However, Theorem 3 implies that a power control scheme should be used to guarantee that the effective SNR of any single user is not beyond the limit.
In deriving the conditions in Theorem 3, we compare the average system throughput when the user with the extremely good channel state transmits, to the case when the user does not transmit. It is optimal for the user not to transmit, if the loss in the system throughput when the user transmits is more than 1, or at least more than its probability of success (which should be approximately 1 for an extremely good channel state). Therefore, the ?rst condition in Theorem 3 is that a system throughput greater than 2 can be achieved. This condition directly implies that there are strictly more than 2 users in the system, hence there exists multiple access interference; and more subtly, it is possible that the loss in the average system throughput when a user transmits and introduces interference to other users is more than 1. Theorem 3: Consider the asymmetric WLAN system model described in Section II and the optimization problem (12). Assume the SINR threshold reception model (9). Let the mean channel state value for user i be E Fi [γi ] = μi . De?ne μ = K ? ? i=1 μi . Let (p1 (.), . . . , pK (.)) be a solution to (12). Assume that it is possible to achieve a system throughput greater than 2 + 0 , for some 0 ∈ R+ . Let Nμ , (19) C= β 0 where N and β are the spreading gain and the SINR threshold in (9), then p? i (γi ) = 0 for γi > C, ?i = 1, 2, . . . , K. (20) Proof: See the appendix. It should be noted from Theorem 3 that the limit C given by (19) decreases when 0 increases, i.e. we can obtain a tighter limit C by showing that a higher system throughput is achievable. V. O PTIMAL T RANSMISSION P OLICY FOR S PATIALLY H OMOGENEOUS WLAN S YSTEMS Here we consider the symmetric (spatially homogeneous) WLAN system model and the optimization problem (16) formulated in Section III-B. We provide a suf?cient condition for which the optimal transmission policy also has the properties outlined by Fig. 1. First, recall that the spatially homogeneous network is a special case of the spatially heterogeneous network, where all users have the same channel distribution function and the same input (arrival) rate. The optimization problem (12), which has been analysed in Section IV, can also be formulated for the spatially homogeneous network model. In particular, for the spatially homogeneous network model, the system maximum stable throughput given by (10) can be rewritten as follows LK (p1 (.), . . . , pK (.)) =
M M K
...
0 0
K k=0 AK k i∈Ak
pi (γi ) (21)
j ∈ AK k
(1 ? pj (γj ))Ψ(k) (γAK )dF (γ1 ) . . . dF (γK ). k
Hence, we can rewrite the optimization (12) for spatially homogeneous networked users as follows
p1 (.),...,pK (.):pi (.)∈BL∞ [0,M ] [0,1]
max
LK (p1 (.), . . . , pK (.)) , (22)
7
where LK (p1 (.), . . . , pK (.)) is given by (21). Theorems 2 and 3 hold for (22). Second, it should be noted that the optimization problem (16) is actually (12) with the objective function rewritten as (21) above and subject to an extra constraint: pi (.) = pj (.) for all i, j ∈ {1, 2, . . . , K }.
a.e
where N and β are the spreading gain and the SINR threshold in (9) then p? (γ ) = 0 ? γ > C. (25)
(23)
In what follows, we claim that if (22) has a unique solution then the structural results outlined in Fig. 1 can be proved for the optimization problem (16), which is equivalent to (22) with the constraint (23). Corollary 1: Consider the spatially homogeneous WLAN model described in Section II. If (22) has a unique solution, i.e. (21) has a unique global optimum, then the optimization problem (16) has a unique solution p ? (.) that is a nonrandomized transmission policy in the sense of Def. 2. Proof: See the appendix The classical collision channel model and the MPR model without CSI [7] clearly do not satisfy the condition that the solution of (22) is unique. However, it can still be claimed for these models that (16) has a non-randomized solution. Indeed, for the symmetric network model with a collision channel, the classical optimization problem is to pick a constant transmission probability to maximize the system throughput, which is equivalent to the optimization problem (22) with one extra constraint that p(·) = a, for some constant a ∈ [0, 1]. This constraint makes the optimal transmission policy randomized in the sense of Def. 1. However, if transmission policies are allowed to be functions of channel states as in (16), there exists a solution that is non-randomized in the sense of Def. 2. The underlying reason is that, when CSI is available, each (randomized) constant transmission policy is equivalent to at least one, and usually an in?nite number of, nonrandomized transmission policies of the form (2), assuming that the physical channel distribution is continuous. The same arguments apply to the MPR model in [6], [7]. Using a similar approach to Corollary 2, we claim the other structural results for the symmetric network model. Corollary 2: Consider the spatially homogeneous WLAN system model described in Section II. Assume that (17) holds. If (21) has a unique global optimum, then the optimization problem (16) has a unique solution p ? (.) that is pure in the sense of Def. 2 and piece-wise continuous, i.e.
γ →γ0
Proof: Similar to the proofs of Corollaries 1 and 2, (25) follows from the assumption that (21) has a unique global optimum, the symmetry of the objective function (21) and Theorem 4. VI. S TOCHASTIC G RADIENT A LGORITHM FOR E STIMATING O PTIMAL T RANSMISSION P OLICY In this section we focus on deriving an algorithm to numerically solve the optimization problem (16) for the symmetric WLAN system model. In particular, we use a novel spherical coordinate parameterization technique to convert the transmission policy optimization problem from a constrained problem, where the constraint is that the transmit probabilities are in [0, 1], to an unconstrained problem. Then, we proposed a stochastic approximation algorithm (Algorithm 1), that can numerically solve the optimization problem (16). Algorithm 1 is an off-line gradient-based algorithm and can be used to ?nd the optimal transmission policy for spatially homogeneous networked users. For spatially heterogeneous networked users, an analogous algorithm can be easily obtained. However, for the asymmetric network model, a game theoretic approach gives a more ef?cient way to update the transmission policy of each user in a real-time, distributed fashion [23]. The core of Algorithm 1 is the stochastic estimation of the gradient (of the objective function), which cannot be derived in close-form. The gradient estimates in Algorithm 1 are obtained by the score function method [27]. The score function method is one of the exact gradient estimation methods that yield unbiased gradient estimates. Other methods for obtaining unbiased gradient estimates include the weak derivative method and the process derivative method [27]. In this paper we select the score function method for its relative simplicity. The essence of the score function method is the use of the Rao-Blackwellization (smoothing by conditioning) technique to reduce the variance of the gradient estimates. An alternative, very simple and widely used method for gradient estimation is the ?nite difference method [28]. However, gradient estimates by the ?nite difference method are subject to a random systematic error of mean 0 and variance in the order of 1/c, where c is the perturbation factor (see [27], Chapter 5). In other words, gradient estimates by the ?nite difference method are biased, and as the perturbation factor tends to zero, the variance of the estimate error is unbounded. First, quantize the channel state space into a ?nite number of ranges and convert (16) into a ?nite dimensional optimization problem. In particular, let SNR represent channel state and quantize the SNR domain (i.e. channel state space) into M regions by αi , i = 1, 2 . . . M +1, αi < αj ?i < j . The function optimization problem (16) is then replaced by selecting an optimal transmit probability for each SNR range. We use the novel spherical coordinate parameterization method, ?rst
lim p? (γ ) = p? (γ0 )
?γ0 ∈ [0, M ]
(24)
except for possibly a zero-measure set of values of γ 0 . Proof: See the appendix. Corollary 3: Consider the spatially homogeneous WLAN model described in Section II and the SINR threshold reception model (9), which is an example of the G-MPR model. Assume that (22) has a unique solution, i.e. (21) has a unique global optimum. Further assume that it is possible to achieve a system throughput greater than 2 + 0 , for some 0 ∈ R+ . Let p? (.) be an optimal transmission policy. Let C= Nμ , β 0
8
proposed in [29], [30], to represent a transmission policy by
M
pθ (γ ) =
sin2 θi I(αi ≤ γ < αi+1 ).
(26)
i=1
Stochastic Approximation Algorithm with Likelihood Ratio Gradient Estimation: First, we need to generate unbiased estimates of the gradient of the system throughput, ? θ L(θ) given by (27). Generation of ? θi L(θ) requires the generation of unbiased estimates of E F (k) X θ, γ (k) and its gradient with respect to the θ. Since the channel distribution function is known, we can reduce variance of the estimates by the Rao-Blackwellization (smoothing by conditioning) technique. We estimate EF (k) [Xk ] and ?θi EF (k) [Xk ] conditioned on the event that all k users transmit, which we denote as event Z k . The a posteriori channel state distribution of a user given that it transmits is computed in [21], [1]: Gθ (γ ) =
γ 0 pθ (γ )dF (γ ) ∞ 0 pθ (γ )dF (γ )
The system maximum stable throughput (10) can be rewritten as:
K
L(θ) =
k=1
K (1 ? pθ )K ?k EF k pθ (γ1 ) . . . pθ (γk ) k × Ψ(k) (γ (k) ) , (27)
where θ = (θ1 , . . . , θM ) and
M
=
γ 0
pθ (γ )dF (γ ) pθ
(32)
pθ =
sin2 θi (F (αi+1 ) ? F (αi ))
(28)
The corresponding density function is gθ (γ ) =
∞
i=1
is the average transmit probability, and Ψ (k) (γ (k) ) is given by the reception model (6). The optimization problem (16) becomes ?nding θ that maximizes the system throughput, i.e. max L(θ).
θ
pθ (γ )f (γ ) , pθ
(29)
where pθ = 0 pθ (γ )dF (γ ) is the average transmit probability corresponding to θ. The conditional expectation of E X (θ, γ (k) ) can be computed straightforwardly by E X (θ, γ (k) ) =E E X (θ, γ (k) )|Zk =P(Zk )EF (k) |Zk Ψ(k) (γ (k) ) =pk E k Ψ(k) (γ (k) ) θ G
θ
In what follows, we will derive a numerical algorithm to estimate the parameter θ that maximizes L(θ) given by (27). The use of the spherical coordinates as in (26) guarantees that the norm of the estimated transmission policy p θ (γ ) is in [0, 1]. First, de?ne a stationary point, which is also a local maximizer of the system throughput by θ? = {θ : ?θ L(θ) = 0, ?2 L(θ) < 0}. θ The gradient of (27) with respect to θ i is given by
K
(33)
(30)
?θi L(θ =
k=1
K k
(k ? K )(1 ? pθ )K ?k?1 F (αi+1 )
?F (αi ) sin(2θi )EF (k) X (θ, γ (k) ) +(1 ? pθ )K ?k ?θi EF (k) X (θ, γ (k) ) , (31)
It should be noted that after conditioning the (a posteriori) channel state distribution G θ (γ ) is parameterized by θ , i.e. EGk Ψ(k) (γ (k) ) is of the parameterized integrators form θ [27]. There are three methods to simulate the gradient of an expectation of the parameterized integrators form: the score function method (ratio likelihood), the weak derivatives method and the process derivatives method [27]. In Algorithm 1, the score function method is selected due to its relative simplicity. Furthermore, as estimates of Ψ (k) (γ (k) ) are i.i.d over time, the three methods are expected to have similar performance in terms of the gradient estimate variances. Due to (33) and by the score function method in [27], ?θi EF (k) Xk (γ (k) ) = kpk?1 (sin(2θi ))(F (αi+1 ) ? F (αi ))
θ
where X (θ, γ (k) ) = pθ (γ1 ) . . . pθ (γk )Ψ(k) (γ (k) ). Unbiased gradient estimates of every factor in (31), including F (α i ) for all i, can be easily obtained without knowing the channel state probability distribution function F (·). Hence, it is straightforward to derive a blind stochastic approximation algorithm for estimating the optimal transmission policy. However, when the channel probability distribution function is known, there are several methods for reducing the gradient estimate variance and greatly improve the convergence rate of the algorithm [27]. Below we assume that F (·) is known and propose an off-line optimal transmission policy learning algorithm that uses the Rao-Blackwellization (smoothing by conditioning) technique for gradient estimation.
? E k [Ψ(k) (γ (k) )], ×EGk [Ψ(k) (γ (k) )] + pk θ θi G
θ θ
where ?θi EGk Ψ(k) (γ (k) ) = EGk Ψ(k) (γ (k) )
θ θ
×
?θi gθ (γ1 ) . . . gθ (γk )
gθ (γ1 ) . . . gθ (γk ) ?θi gθ (γ1 ) ?θi gθ (γk ) + ...+ = EGk Ψ(k) (γ (k) ) θ gθ (γ1 ) gθ (γk )
(34)
9
Simple mathematical derivations give ?θi gθ (γ1 ) sin(2θi )I(αi ≤ γ < αi+1 ) = M 2 gθ (γ1 ) j =1 sin (θj )I(αj ≤ γ < αj +1 ) ?
M j =1
sin(2θi )[F (αi+1 ) ? F (αi )]
sin(θj )[F (αj +1 ) ? F (αj )]
.
(35)
Plugging (33), (34), (35) into (27) gives the following score function estimate for ? θi L(θ)
K
?θi L(θ) =
k=1
K k
(k ? Kpθ )(1 ? pθ )K ?k?1 pk?1
θ
× F (αi+1 ) ? F (αi ) sin(2θi )Ψk (γ (k) ) + (1 ? pθ )K ?k pk Ψ(k) (γ (k) ) θ + ?θi gθ (γk ) gθ (γk ) , ?θi gθ (γ1 ) + ... gθ (γ1 ) (36)
where γi ? Gθ (.), which is given by (32), for all i ∈ {1, 2, . . . , K }. Algorithm 1: Initialize l = 0 ; θ(0) = (θ1 , . . . , θM ) ∈ RM . For time index l = 1, 2, . . . repeat ? Generate γi ? Gθ (l) (.) for i = 1, . . . , K . Obtain ?θ(1) L(θ(1) ) using (36) θ(l+1) = θ(l) + εl ? ?θ L(θ)
?
(37)
Conditions on decreasing step size ε l with
∞ ∞
εl = ∞;
l=1 l=1
ε2 l <∞
(38)
Theorem 4: The estimates θ(l) generated by Algorithm 1 converge w.p.1 to a local maximizer θ? , de?ned in (30), of the system stable throughput (27). Proof: For a ?xed initial θ , the sequence ?θ L(l) (θ ) : l = 1, 2 . . . are i.i.d, and (37) is an instance of the well known Robbins Munro algorithm. In [31], the convergence proof for gradient-based algorithms for much more general, correlated signals (e.g. Markovian signals) is given. The convergence conditions are (38) and uniform integrability of ? θ L(l) (θ ). A suf?cient condition for uniform integrability is that the channel distribution has ?nite variance. VII. N UMERICAL S TUDIES In this section the structural results and the performance of Algorithm 1 are illustrated via numerical examples. We consider a spatially homogeneous WLAN system of K users that communicate with a common base station using the DSCDMA scheme with random signature sequences of spreading gain N = 32. Assume that SNR represents channel state and that the base station has a matched ?lter receiver to decode signals from different users. Then the reception model is given by (8) and (9). That is, in a transmission time slot, a packet transmitted from user i is successfully received if and only if: γi >β , I 1 1 + N j ∈AK ?i γj
k
where AK k is the set of all transmitting users, N is the spreading gain and β is a SINR threshold. Assume the underlying channel is Rayleigh fading, then the channel state (SNR) is exponentially distributed. We relax the assumption that γ ∈ [0, M ] for some ?nite M and let the channel state probability distribution function, which is identical for all users, be 1 F (γ ) = 1 ? e?γ/μ , μ where μ is the mean value of γ . Improvement in system throughput and success rates: Let μ = 10 and quantize the channel state space into 25 ranges by αi = i for i = 0, 1, . . . , 25 and α26 = ∞. Fig. 2 compares three transmission schemes in the sense of the fullload system throughput, which is also the system maximum stable throughput as the network is symmetric, and the average success rates. The transmission schemes are by (i) the optimal channel-aware transmission policies designed by Algorithm 1; (ii) the non-channel-aware optimal transmission policy in [7]; (iii) the policy of always transmitting. The emperical full-load system throughput is computed from (10) and the average success rate is de?ned by R = T /(pK ), where p is the average transmit probability given by (14), K is the total number of users, and T is the system maximum stable throughput. The size of the network is varied from 1 to 40 users. It is seen that the system throughput is improved with the size of the network only when optimal channel-aware transmission policies are deployed. In addition, the success rate remains at 0.76 for optimal channel-aware transmission policies even when the system is overloaded, i.e. the number of active users is greater than the spreading gain. That is, when CSI is exploited, channel utilization is signi?cantly enhanced. Convergence of the estimates by Algorithm 1: We quantize the channel state space into 25 ranges as in the previous example but assume that μ = 5 instead of μ = 10. Algorithm 1 is run to estimate the optimal transmission policy for the case when there are 20 active users in the network. Fig. 3 illustrates that the estimates θ (l) generated by Algorithm 1 seem to converge to a transmission policy p ? (·) that has the properties outlined in Fig. 1, i.e. non-randomized as proved in Theorem 2(a), piece-wise constant as proved in Theorem 2(b), and p? (γ ) = 0 for all γ greater than some constant C . It can be seen from Fig. 3 that the convergence of Algorithm 1 is not plagued by any local optimum and the generated estimates θ(l) converge to a good neighbourhood of the optimum after about 50 iterations. In fact, the system throughput for the transmission policy obtained after 50 iterations of Algorithm 1 is very close to the optimal throughput, which is approximately 4.61 for a network of 20 users with μ = 5. VIII. A NALYSIS OF 2- USER SYSTEMS In this section we aim to give a simple analytical example to provide more insight into the structural results in Section IV. In particular, we consider a symmetric system of two users and compute the optimal transmission policy explicitly to illustrate the results in Section IV. We relax the assumption that the channel state space lies in [0, M ] for some ?nite M and let the channel state space be [0, ∞).
10
Assume the users communicate with a common base station using DS-CDMA with random signature sequences. Similarly to previous sections, we assume the SINR threshold reception model (9). Further assume that the physical channel is Rayleigh fading, which leads to an exponential channel state (SNR) probability distribution function, i.e. F (γ ) = γ/μ) . The full-load system throughput (10) can be 1 ? exp(? μ rewritten as L (p1 (.), p2 (.)) =
∞ 0 0 ∞
A PPENDIX A. Proof of Theorem 1 The proof of this theorem follows very similar lines to the proof of the suf?cient part of Theorem 1 in [1]. For completion and clarity we reproduce the proof with necessary generalizations. Readers are referred to [1] for the original proof on the equivalence between the system maximum stable throughput and the full-load system throughput for homogeneous networks with the multipacket reception capability. (t) (t) (t) Let N(t) = N1 , . . . , NK , where Ni is the length of the (t) buffer of user i at time t. The evolution of N i is given by Ni
(t) (t+1)
p1 (γ1 )p2 (γ2 )Ψ(2) (γ1 , γ2 )
+ p1 (γ1 )(1 ? p2 (γ2 ))Ψ(1) (γ1 ) + (1 ? p1 (γ1 )) × p2 (γ2 )Ψ(1) (γ2 ) dF (γ1 )dF (γ2 ), (39)
= (Ni
(t)
? Yi )+ + Xi ,
(t)
(t)
(42)
γ1 γ2 where Ψ(2) (γ1 , γ2 ) = I( 1+γ > β ) + I( 1+γ > 2 /N 1 /N (1) (1) β ), Ψ (γ1 ) = I(γ1 > β ), Ψ (γ2 ) = I(γ2 > β ). The optimization problem (12) becomes ? (p? 1 (.), p2 (.)) = arg
p1 (.),p2 (.)
max
L (p1 (.), p2 (.)) .
(40)
We will now solve (40) completely to show that the results in Section IV indeed hold. Nβ Theorem 5: Consider the problem (40). Let A = N ?β , if 1 + e?A/μ ? 2e?β/μ > 0 (41)
? then the optimal solution for (40) is p ? 1 (·) = p2 (·) = I(· > β ). Proof: See the appendix.
IX. C ONCLUSION We consider optimizing the channel-aware ALOHA protocol for the ?nite population random access network model. The network has the multi-packet reception capability and the outcome of each transmission time slot depends on the number of transmitting users and their channel states. We prove that the optimal transmission policy is non-randomized and piece-wise constant for every user. Furthermore, it is proved for CDMA networks, which is the most important example of networks with the MPR capability, that there exists a channel state C beyond which non-transmitting is optimal. In the second part of the paper, we propose an offline stochastic approximation algorithm to numerically solve the optimization problem for spatially homogeneous networks. The algorithms use the spherical coordinates parameterization method proposed in [29], [30] to con?ne the transmission probabilities in [0, 1]. The optimal transmission policy is then estimated by a gradient-based algorithm, where the gradient is estimated using the score-function method presented in [27]. In this paper, the system throughput is the objective and the optimization problem is analysed by a centralized design approach. In [23], we use a game theoretic approach to analyse the structure of the optimal channel-aware transmission policies for non-cooperative users. Therein, it is proved that the optimal transmission policy is a non-randomized threshold function of the channel state. When the system performance is limited by multiuser interference, a game theoretic approach would also improve the system throughput even though the users do not cooperate [23].
where Yi is 1 if user i transmits a packet successfully in (t) time slot t and 0 otherwise, X i is the number of packets that (t) arrive during time slot t. N is therefore a K -dimensional Markov Chain. Assume that the arrival process and the reception model are such that the Markov Chain is aperiodic and irreducible. This assumption is satis?ed for most nontrivial arrival processes and reception models [1]. With this assumption the stability of the system in the sense of (3) is equivalent to the existence of a stationary distribution for the Markov Chain N (t) . The theorem follows from two lemmas. First, Lemma 1 (t) (t) states that the full-load version Q i of the Markov Chain N i (t) stochastically dominates N i . Lemma 1: (Also see Lemma 2 in [1]) Consider a system of K spatially heterogeneous networked users. For each user (t) i = 1, 2, . . . , K de?ne a one-dimensional Markov Chain Q i (t) that is the full-load version of N i , i.e. P(Qi
(t+1)
= P(Ni
(t+1)
= k |Qi = s) = k |Ni
(t) (t)
(t)
= s, Nj
(t)
> 0, i = 1, . . . , K, j = i).
(t)
The Markov Chain Q i stochastically dominates N i , i.e. for all t, s, k, x ∈ N+ P(Qi
(t+1)
> x|Qi = s, Qi
(t)
(0)
= k) k) (43) (44)
(t+1) (t) (0) > x|Qi = s + 1, Qi = ≤ P(Qi (t+1) (t) P(Ni > x|Ni = s, N (0) = k ) (t+1) (t) (0) > x|Qi = s, Qi = k ), ≤ P(Qi
where k = (k1 , . . . , kK ). Proof: (43) is implied by the fact that the probability that the buffer goes beyond level x at time t + 1 is greater if the buffer store more packets at time t [1]. We now show (44). (t) The time evolution Q i can be written as Qi
(t) (t+1)
= (Qi ? Zi )+ + Xi ,
(t)
(t)
(t)
where Zi is 1 if user i transmits a packet successfully in (t) time slot t and 0 otherwise, X i is the number of packets that arrive during time slot t. Therefore, in order to show (44) it suf?ces to show that the probability of success is lower in the full-load system, i.e. P(Yi = 1|Ni
(t)
= s, Ni
(0)
= k)
11 (t) (0)
≥ P(Zi = 1|Qi = s, Qi
= k ).
(45)
It should be noted that the success probability of a user decreases when there is one more user that has a packet to transmit (due to (7)). Hence, (45) clearly holds. Second, we restate Lemma 3 in [1], which is an application of Pakes’ Lemma [32]. The lemma provides a suf?cient condition (t) (t) for the stability of Q i , which implies the stability of N i . (t) Lemma 2: For the Markov chain Q i de?ne the drift (t+1) (t) (t) Di (j ) = E[Qi ? Qi |Qi = j ]. Suppose that the drift Di (j ) < ∞ for all j and that for some scalar δ > 0 and integer j ≥ 0 we have D i (j ) ≤ ?δ for all j > j . Then the (t) Markov chain Q i has a stationary distribution. For the full-load system the drift D i (j ) of the Markov chain corresponding to the buffer of user i is independent of j and is given by
N
(k ) (γAK ?1 )dF1 (γ1 ) . . . dFK ?1 (γK ?1 ). ? p? j (γj Ψ k (50)
When user K uses the transmission policy p K (.) the new system throughput is given by LK (pK (.)) = where
K ?1 M 0
pK (γ )h(γ ) + (1 ? pK (γ ))LK ?1 dFK (γ ), (51)
h(γ ) = EF (γ1 ,...,γK ?1 )
k=0 AK ?1 i∈AK ?1 k k
p? i (γi ) (52)
×
?1 j ∈ AK k
(k+1) (1 ? p? (γAK ?1 , γ ) j (γj )) Ψ
k
.
Di (j ) = λi ?
k=1 AK k ?i
M
M
...
0 0 l∈ A k K
pl (γl )
? l∈ A k K
1
It is clear that pK (γ ) = 1 0 if h(γ ) > LK ?1 otherwise (53)
? p? dF1 (γ1 ) . . . dFK (γK ). (46) l (γ? l ) E θi |k users tx, γAK k From the above equation it can be seen that a suf?cient (t) condition for the stability of Q i is
N M M
λi <
k=1 AK k ?i
...
0 0 l∈ A k K
pl (γl )
? l∈ A k K
(1 ? p? l (γ? l )) (47)
(t)
dF1 (γ1 ) . . . dFK (γK ), × E θi |k users tx, γAK k
which is also a suf?cient condition for the stability of N i . Hence a suf?cient condition for the stability of the system is
K
λ=
i=1
M
M K
λi <
...
0 0
K k=0 AK k i∈Ak
pi (γi )
j ∈ AK k
(1 ? pj (γj ))Ψ(k) (γAK )dF1 (γ1 ) . . . dFK (γK ). (48) k
Therefore, the system maximum stable throughput de?ned as the supremum of all accumulative input rates for which the system is stable is lower-bounded by (10). B. Proof of Theorem 2 1) Proof of Theorem 2(a): We will prove the Theorem by ? ? contradiction. First, let (p ? 1 (.), p2 (.), . . . , pK (.)) be a solution ? ? ? to (12). Suppose that (p 1 (.), p2 (.), . . . , pK (.)) does not satisfy Theorem 1. Without loss of generality, suppose p ? K (.) is / {0, 1} for randomized in the sense of Def. 1, i.e. p K (γ ) ∈ some non-zero measure set of values of γ . We now show that the solution to the optimization problem
pK (.)∈BL∞ [0,M ) [0,1]
is a Lebesgue measurable transmission policy that maximizes (51). Hence, if we assign p ? K (·) = pK (·) given by (53), the system throughput is still maximized. This step can be re? peated until (p? 1 (.), . . . , pK (.)) only contains non-randomized policies, hence Theorem 1. Remark: If h(.) is non-zero almost everywhere, we can claim a stronger result that solution(s) of (12) must consist of pure policies only. Intuitively, h(.) is non-zero almost everywhere means that the system throughput when user i always transmits is almost surely different from the case when user i never transmits. Verifying this condition is hard. Nevertheless, we conjecture that the condition holds for the SINR reception model for CDMA systems. The condition does not hold for the collision model or the MPR reception model without CSI. 2) Proof of Theorem 2(b): We follow the same approach as the proof of Theorem 2(a). ? ? Let (p? 1 (.), p2 (.), . . . , pK (.)) be a solution to (12). We will show that there exists a non-randomized piecewise continuous solution to (49). In particular, we will show that the solution (53) is a piecewise continuous, non-randomized transmission policy. This can be done by showing that h(γ ) given by (52) is piecewise continuous. Given the channel states of all users, the probability ?1 transmit is given that the only users indexed by A K k K ?1 by P(Ak |γ1 , . . . , γK ?1 ) = i∈AK ?1 pi (γi ) j ∈AK ?1 (1 ? k k pj (γj )). Hence h(.) can be rewritten as
(k+1) (γAK ?1 , γ ) ? LK ?1 , (54) h(γ ) = EF ? (γ K ?1 ,AK ?1 ) Ψ
k k
max
? LK (p? 1 (.), . . . , pK ?1 (.), pK (.))
(49)
is non-randomized in the sense of Def. 2. Indeed, the system throughput when user K never transmits is given by L K ?1 =
M M K ?1
joint distribution of is a smoothing operator, h(γ ) is piecewise continuous if (17) holds. C. Proof of Theorem 3
? (γ1 , . . . , γK ?1 , AK ?1 ) is the where F k ?1 γ1 , . . . , γK ?1 , k, AK . As expectation k
...
0 0 k=0
?1 AK k ?1 i∈AK k
p? i (γi )
?1 j ∈ AK k
1
? ? Let (p? 1 (.), p2 (.), . . . , pK (.)) be a solution to (12). Without loss of generality we will show that (20) holds for p ? K (.). For
12
? ? (p? 1 (.), p2 (.), . . . , pK (.)) to be an optimum, it must be the case a.e. ? that pK (γ ) = pK (γ ) ?γ s.t. h(γ ) = 0, where pK (γ ) is given by (53) and h(γ ) is given by (52). The proof will be complete if we can show that h(γ ) < 0 for all γ > C . ? Due to the theorem’s assumption, L (p ? 1 (.), . . . , pK (.)) > 2 + 0 . Furthermore, when user K never transmits the system throughput is L K ?1 given by (50). From (50) it is easy to see that LK ?1 ≥ L? K ? 1 > 1 + 0. For the SINR threshold reception model (9) we have γi Ψ(k+1) (γAK ?1 , γ ) = I (γ > β + β ) k N K ?1 i∈Ak γ N
? ? that p? i (·) = p (·) for all i ∈ 1, . . . , K, and p (.) is piecewise ? continuous due to Theorem 3 and p (.) is the unique optimum of (13).
F. Proof of Theorem 5 Our approach to prove the theorem is as follows: ?rst, we aim to solve for p ? 1 (.) without any assumption or constraint on p2 (.). Then by symmetry, we claim the same result for p ? 2 (.). 1) γ1 ≥ A =
∞ A 0 ∞ Nβ N ?β
> β . (39) can be rewritten as
+
?1 i∈AK k
I(
1+
γi +
γj j =i N
> β) γj ) β (55)
p1 (γ1 ) + p2 (γ2 )I(γ2 > β ) + p1 (γ1 )p2 (γ2 ) γ2 γ1 ) + I(γ2 > β + β ) ? 2 N N
≤1+
i∈Ak K ?1
γi I(γ < N ? N ? β K ?1 I(γ < N γi ). β
× I(γ1 > β + β dF (γ2 )dF (γ1 ).
j =i
≤1+
i=1
We need to select p1 (.) to maximize
∞ A
Hence the following inequalities and equality holds:
K ?1
p1 (γ1 )
∞ 2
p2 (γ2 ) I(γ2 < N
γ1 ? N) β
h(γ ) ≤ 1 + EF ? (γ (K ?1) ,k,AK ?1 )
k
I(γ <
i=1
N γi ) ? LK ?1 β
+ I(γ2 > β + β
γ1 ) ? 2 dF (γ2 ) + 1 dF (γ1 ) N
K ?1
=1+
i=1 K ?1
P(γi > μi β γ i=1 N
β γ ) ? L K ?1 N (By Markov’s inequality)
γ1 1 For γ1 ≥ A we have N γ β ? N ≥ β + β N . Hence γ1 γ1 I(γ2 < N β ? N ) + I(γ2 > β + N β ) ≥ 1 and ∞ A
≤1+
? L K ?1
p2 (γ2 ) I(γ2 < N + I(γ2 > β + β
Nμ Nμ ? L K ?1 ≤ 1 + ? L K ?1 ≤1+ βγ βC = 1 + 0 ? L K ?1 < 0 . Hence h(γ ) < 0 for all γ > C . D. Proof of Corollary 1
γ1 ? N) β
(56)
γ1 ) ? 2 dF (γ2 ) + 1 > 0. (57) N
Under the assumption that all users have the same channel distribution, (10) becomes (21) and the optimization problem ? (12) becomes (22). Let (p ? 1 (.), . . . , pK (.)) be the unique solution of (22). Then due to Theorem 2 p ? i (.) is a pure policy for all i = 1, 2, . . . , K . Since (21) is symmetric with respect to the transmission policies p1 (.), . . . , pK (.) it must be the case that any permu? tation of (p? 1 (.), . . . , pK (.)) is also a global optimum of (21). It follows from the uniqueness of the global optimum that ? ? ? p? i (.) = pj (.) for all i, j ∈ 1, . . . , K = p (.). Then p (.), which is non-randomized in the sense of Def. 2, is the unique optimum of (13). E. Proof of Corollary 2 Similar to the proof of corollary 2, under the assumption that all users have the same channel distribution, the objective function (10) becomes (21), which is symmetric with respect to the transmission policies of all users. This symmetry implies ? that if (p? 1 (.), . . . , pK (.)) is a global optimum of (21) then ? so is any permutation of (p ? 1 (.), . . . , pK (.)). It then follows
Therefore p ? 1 (γ1 ) = 1 for all γ1 > A. Since (57) does not require any assumption on p 2 (.), by symmetry we can claim that p? 2 (γ2 ) = 1 for all γ2 > A. Nβ 2) β ≤ γ1 < A = N ?β 1 For γ1 in this region we have 0 ≤ N γ β ? N ≤ β + γ1 γ1 β N ≤ A and therefore I(γ 2 < N β ? N ) + I(γ2 > 1 β +βγ N ) ? 2 ≥ ?1 for all γ2 > A. It then follows that
∞ β
p2 (γ2 ) I(γ2 < N
γ1 ? N) β
+ I(γ2 > β + β ≥ ?2 > ?2
A β A
γ1 ) ? 2 dF (γ2 ) + 1 N
∞ A
p2 (γ2 )dF (γ2 ) ? dF (γ2 ) ? ? 2e
∞
p2 (γ2 )dF (γ2 ) + 1
=1+e
β ?A/μ
A ?β/μ
dF (γ2 ) + 1
It follows that a suf?cient condition for the strict optimality of p1 (γ1 ) = 1 in this region is (41). Similarly, if (41) holds p ? 2 (.) = 1 in [β, A]. Lastly, it is clear from (39) that p ? 1 (γ1 ) = 0 and p? 2 (γ2 ) = 0 for all γ1 , γ2 ∈ [0, β ].
13
R EFERENCES
[1] S. Adireddy and L. Tong, “Exploiting decentralized channel state information for random access,” IEEE Trans. Info Theory, vol. 51, no. 2, pp. 537–561, February 2005. [2] G. Dimic, N. D. Sidiropoulos, and R. Zhang, “Medium access control physical cross-layer design,” Signal Processing Magazine, IEEE, vol. 21, no. 5, pp. 40–50, 2004. [3] A. Gummalla and J. Limb, “Wireless medium access control protocols,” IEEE Communications Surveys and Tutorials, vol. 3, no. 2, 2000. [4] L. Tong, V. Naware, and P. Venkitasubramaniam, “Signal processing in random access,” Signal Processing Magazine, IEEE, vol. 21, no. 5, pp. 29–39, 2004. [5] R. A. Berry and E. M. Yeh, “Cross-layer wireless resource allocation,” Signal Processing Magazine, IEEE, vol. 21, no. 5, pp. 59–68, 2004. [6] S. Ghez, S. Verdu, and S. C. Schwartz, “Stability properties of slotted ALOHA with Multipacket reception capability,” IEEE Trans. Auto. Control, vol. 33, no. 7, pp. 640–649, July 1988. [7] ——, “Optimal decentralized control in the random access Multipacket channel,” IEEE Trans. Auto. Control, vol. 34, no. 11, pp. 1153–1163, November 1989. [8] A. B. MacKenzie and S. B. Wicker, “Stability of multipacket slotted ALOHA with sel?sh users and perfect information,” in Proceedings of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies, 2003, vol. 3, April 2003, pp. 1583–1590. [9] Q. Zhao and L. Tong, “A multiqueue service room mac protocol for wireless networks with multipacket reception,” Networking, IEEE/ACM Transactions on, vol. 11, no. 1, pp. 125–137, 2003. [10] W. Szpankowski, “Stability conditions for some distributed systems: buffered random access systems,” Advances in Applied Probability, vol. 26, pp. 498–515, 1994. [11] B. Tsybakov and V. Mikhailov, “Ergodicity of slotted ALOHA system,” Problemy Peredachi Informatsii, vol. 15, pp. 73–87, Oct-Dec 1979. [12] R. Rao and A. Ephremides, “On the stability of interacting queues in a multiple-access system,” IEEE Trans. Inform. Theory, vol. 34, pp. 918– 930, September 1988. [13] W. Luo and A. Ephremides, “Stability of n interacting queues in random access systems,” IEEE Trans. Inform. Theory, vol. 45, pp. 1579–1587, July 1999. [14] M. Zorzi and R. Rao, “Capture and retransmission in mobile radio,” IEEE J. Selected Areas Communications, vol. 12, no. 8, pp. 1289–1298, October 1994. [15] B. Hajek, A. Krishna, and R. LaMaire, “On the capture probability for a large number of stations,” IEEE Trans. Commun., vol. 45, no. 2, pp. 254–260, February 1997. [16] V. Naware, G. Mergen, and L. Tong, “Stability and delay of ?niteuser slotted aloha with multipacket reception,” Information Theory, IEEE Transactions on, vol. 51, no. 7, pp. 2636–2656, 2005. [17] D. Tse and S. Hanly, “Linear multiuser receivers: effective interference, effective bandwith and user capacity,” IEEE Trans. Inform. Theory, vol. 45, pp. 641–657, March 1999. [18] S. Shamai and E. Telatar, “Some information theoretic aspects of decentralized power control in multiple access fading channels,” in Proceedings of Information Theory and Networking Workshop, Metsovo, Greece, June 1999. [19] X.Qin and R.Berry, “Exploiting Multiuser Diversity in Wireless ALOHA Networks,” in Proceedings of 2001 Allerton Conference on Communication, Control and Computing, October 2001. [20] ——, “Exploiting Multiuser Diversity for Medium Access Control in Wireless Networks,” in Proceedings of IEEE INFOCOM, San Francisco, CA, 2003. [21] G. Mergen and L. Tong, “On the asymptotic stable throughput of opportunistic random access,” in Conference on Information Sciences and Systems, Princeton University, March 2004. [22] M. H. Ngo and V. Krishnamurthy, “On Optimal Transmission Algorithms for Slotted ALOHA Sensor Networks with Multi-Packet Reception,” in Proc. International Conference on Acoustics, Speech, and Signal Processing, Philadelphia, USA, March 2005, pp. 669–672. [23] ——, “Game Theoretic Cross-Layer Transmission Policies in Multipacket Reception Wireless Networks,” Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on], vol. 55, no. 5, pp. 1911–1926, 2007. [24] T. Rappaport, Wireless Communications: Principles and Practice, 2nd ed. Prentice Hall, 2002. [25] A. Goldsmith, Wireless Communications. Cambridge University Express, 2005.
Throughputs and success rates for different transmission schemes 10 9 8 Throughput and success rate 7 6 5 4 3 2 1 0 ?1 0 5 10 15 20 25 30 Number of active nodes in the network 35 40 Optimal throughput with decentralized CSI Optimal throughput without CSI Throughput without transmission control Optimal success rate with decentralized CSI Optimal success rate without CSI Success rate without transmission control
Fig. 2. The optimal distributed channel-aware MAC protocol offers a substantial gain in the system maximum stable throughput and the success rate especially when the network size is large. Simulation parameters: spreading gain N = 32, SINR threshold β = 4dB, mean channel state value μ = 10.
Convergence of the estimates of the optimal channel?aware transmission policy 1.8 1.6 1.4 Transmit probabilities 1.2 1 0.8 0.6 0.4 0.2 0 ?0.2 0 5 10 15 Channel state (SNR) 20 25 Initial tx. probabilities, Throughput = 1.56 After 50 iterations, Throughput = 4.6 After 200 iterations, Throughput = 4.61
Fig. 3. Estimates of the optimal transmission policy by Algorithm 1 converge to a transmission policy that has the properties outlined by Fig. 1. Throughput obtained by the estimated transmission policy is close to optimal after 50 iterations. Simulation parameters: K = 20 users, spreading gain N = 32, SINR threshold β = 4dB, mean channel state value μ = 5.
[26] D. Luenberger, Optimization by Vector Space Methods. New York: Wiley, 1969. [27] G. P?ug, Optimization of Stochastic Models: The Interface between Simulation and Optimization. Kluwer Academic Publishers, 1996. [28] J. C. Spall, Introduction to Stochastic Search and Optimization, ser. Wiley-Interscience series in Discrete Mathematics and Optimization. Wiley-Interscience, 2003. [29] F. V. Abad and V. Krishnamurthy, “Self learning control of constrained Markov decision processes– a valued gradient approach,” GERAD-HEC Montreal, http://www.gerad.ca/?chiers/cahiers/G-200351.pdf, Tech. Rep. G-2003-51, August 2003. [30] F. V. Abad, V. Krishnamurthy, I. Baltcheva, and K. Martin, “Self learning control of constrained Markov decision processes,” in IEEE Conference on Decision and Control, Las Vegas, 2002. [31] H. Kushner and G. Yin, Stochastic Approximation Algorithms and Applications. New York: Springer-Verlag, 1997. [32] A. Pakes, “Some conditions for ergodicity and recurrence of markov chains,” Operations Research, vol. 17, pp. 1058–1061, 1969.