A (Stability constraints) (2.25) P(V£ > rji) < Si (Robustness constraints) (2.26) fl. < flax (2-27) i £ 3, k € Z+ where jj,k is given by (2.15) and fk is defined in (2.8). 2.4 Oppor tun i s t i c Scheduling A l g o r i t h m For St reaming H S D P A Users In this section we present an opportunistic algorithm for joint user scheduling and M C M assignment as a solution to the problem outlined in (2.25), (2.26) and (2.27). First, we outline the methodology to obtain a feasible solution and summarize the steps of the algorithm. Next, each step of the algorithm is discussed in more detail. M a i n result: The main result of this section is Algorithm 1 in Section 2.4.1, which is proposed as a solution to the HSDPA scheduling problem. Remark: If not specified, throughout this section, we assume i e 3, k € Z+. 30 Chapter 2. Opportunistic Scheduling in HSDPA 2 A.l Summary of the Opportunistic Streaming Algorithm We consider the following general structure for the HSDPA scheduling algorithm: 0(x f c) = a r g m a x 7 i v 2 / 4 (2.28) where a\\ are the per-TTI capacities defined in (2.14) and Vk are the queues' lengths defined in (2.9). 7$ are real constants, denoted by fairness parameters, that provide additional flexibility for assigning priorities (fairness) among the users. The idea is to assign higher priorities to the relatively better channels (higher u^) and hence ex-ploiting channel variations to maximize the overall throughput. On the other hand the algorithm assigns higher priorities to the users with larger queue lengths and therefore reducing the probability of the queues growing larger. The fairness parameters can then be adjusted to further shape the priority distribution among the users. The algorithm in (2.28) is denoted by M-LWWF (Modified Largest-Weighted-(unfinished) Work-First) and is proven to guarantee the stability of the queues (if possible with any other pol-icy) [12]. We present a joint opportunistic scheduling and M C M assignment algorithm by further modifying the M-LWWF scheduling algorithm and combining it with a suit-able M C M assignment scheme (in particular, the per-TTI capacities in M-LWWF are replaced with their optimal minimum-variance estimates). We prove that the resulting joint opportunistic scheduling and M C M assignment algorithm guarantees the stability of the queues as well and hence satisfies the stability condition in (2.25) (if feasible). Next, we present Stochastic Approximation methods to adapt the fairness parameters 7i in a way that the robustness constraint in (2.26) is satisfied as well (if feasible) and there-fore a solution for HSDPA scheduling problem is obtained. The proposed opportunistic algorithm is denoted by Algorithm 1 and is summarized in the following steps: Algori thm 1: Joint Opportunistic Scheduling and M C M Assignment Step 0 - Initialization Step 1 - Estimating per-TTI capacities: Apply equation (2.34) t° estimate the maximum achievable rate p\\ for all users i 6 3 at time k. Step 2 - Computing a throughput optimal MCM for each user: Apply equation (2.37) to calculate the optimal MCM denoted by a(i, xk) for each user i E 3. The optimal MCM of user i is calculated in a xuay that the throughput of user i is maximized (in case of scheduling user i). Step 3 - Joint MCM assignment and M-LWWF scheduling: Apply equation (2.41) to schedule user ik at time k. Substitute ik in Step-2 by applying equation (2.42) 31 Chapter 2. Opportunistic Scheduling in HSDPA to assign a(ik,xk) as the MCM of the scheduled user ik. Step 4 - Updating the fairness parameters: Apply Stochastic Approximation algo-rithm in (2.46) and (2.47). Set k —• k + 1 and go to Step 1. 2.4.2 Initialization We start with empty queues: VQ =0, i G 3 and assume all the fairness parameters are identical and equal to one: 7g = 1, i £ 3 (note that later in the simulations, we may also consider random initial fairness parameters). 2.4.3 Estimating per-TTI Capacities Here, Step-1 of Algorithm 1 is discussed. The main result of this step is to show how to evaluate the per-TTI capacities fik, i G 3 in the M-LWWF algorithm (since the occurrence of a frame error is not known a priori, the relation in (2.15) cannot be directly used). We prove that instead of the exact values of the per-TTI capacities p\\, i € 3, the optimal estimate (i.e., conditional expectation) of plk can be used by the scheduler without degrading the stability of the queues. Consider the optimal (Minimum-Variance) estimate of u.k. i G 3, defined as: ti-.= E(pi\\xk). (2.29) Now consider the following well-known smoothing property of conditional expectations [51, Thm.10, Chapter 4.6, p. 106]: E ( /4 l { 0 ( S f c ) = i }) = E (E (fik\\xk) l{*(Sfc)=i}) • Substituting from (2.29) gives: E {Pk1W(xk)=i}) = E (i»Uwife)=t}) • (2-30) The stability condition in (2.25) can then be reformulated as: E(Atfci{0(xfc)=o) > Di- ' (2-31) The relations in (2.30) and (2.31) state that any scheduling policy that keeps the buffers stable with per-TTI capacities i 6 3, will do so as well with per-TTI capacities u.xk, i G 3, (and vice versa). 32 Chapter 2. Opportunistic Scheduling in HSDPA Assuming perfect channel information, plk has a deterministic value at time k. From (2.29) and (2.15), p[ is given by: Pk = E ('rU{No Frame Error} W) = 4(1 - fl), (2.32) where r\\ and flk are defined in (2.6) and (2.8), respectively. In the proposed algorithm, we use the deterministic value in (2.32) as the measure for user i capacity at time k which is equivalent to the original definition in (2.15) in terms of stability of queues. Here, we only need to consider the M C M combinations that satisfy the maximum FER constraints in (2.27). Define: &{xk) := {(rn,, n) e M x N s.t. 0 < ft < fmax}, (2.33) Let p\\ be the maximum per-TTI capacity (estimate) of user i at time k. We have: Pk = , J'k = , r(m,,n)[l- f(m,n,clk)}, (2.34) where r(-) and /'(•) are defined in (2.7) and (2.8), respectively. Also define: Pk = (Pk,pl, •••,($)• (2-35) Note that in practice the exact form of /*(•) due to the use of Turbo-code and com-plexity of the system may not be known. Later in the simulations we use the simulation results and measurements from Motorola research group to map the channel state to the corresponding FER [23]. 2.4.4 Computing Optimal M C M ' s Here we elaborate step 2 of Algorithm 1. We compute the throughput optimal M C M for each user i € 3 at time k, i.e., the M C M that gives the highest throughput for user i (in case of scheduling user i at time k). Define: a(i, xk) = (m\\, 4 ) , ^ » : X x 3 - > M x W , (2.36) where mk and nk are given by (2.4) and (2.5), respectively. In order to satisfy (2.31), the pair (mlk,nk) must be chosen to maximize the per-TTI capacity (estimate) jl\\ while keeping the instantaneous FER below the allowable threshold. Therefore, by using (2.32) 33 Chapter 2. Opportunistic Scheduling in HSDPA and (2.8) the following gives the optimal M C M for each user: a(i,Xk)= argmax pi (2.37) — argmax r(m, n)[l — fl(rn, n, cjL)]. (2.38) (m,n)£&{xk) where Gi(xk) is defined in (2.33). 2.4.5 Joint M - L W W F User Scheduling and M C M Assignment Here, Step-3 of Algorithm 1 is elaborated. First consider a joint scheduling and M C M assignment policy A as defined as in (2.18). We provide additional degrees of freedom if we introduce a parameter vector 7 in the policy A and define: A(-, 7) = {>(-, 7), V(-, 7)}, A : X -> 3 x M x N . Here (-, 7) is the scheduling policy, ip(, 7) is the M C M assignment rule, both depending on 7, and 7 = ( 7 l 7 l . . . 7 L ) , (2.39) where 7$ 6 3?+, i € 3 are any arbitrary positive real constants denoted by fairness parameters (parameters of the algorithm). The main result of this section can be stated by the following theorem which presents a parametric joint scheduling and M C M assignment policy that guarantees the stability of queues (see the constraint in (2.25). Theorem 1 Assume maximum per-TTI capacity pk, defined in (2.35), is an irreducible finite-state discrete-time Markov process. Consider the following parametric policy: A(-,7) = 7); * 12.044 19.82 12.044 crs 19.2853 10.70 19.2853 10.70 00 18.72 to C£> 9.11 18.72 I O <35 7.17 T-H 18.11 4.67 18.11 4.67 to *

5, the optimal action at time k is to attempt to process, and if pk < 5, the optimal action at time k is to suspend processing. Proof: By observing the corresponding optimality equations, we established in Section 3 that our platform control problem is equivalent to a special form of a two-state Marko-vian search in [47]. The reader is then referred to [47] to see the details of the proof for 117 I Appendix A. Optimal Scheduling of a Dedicated-Platform the equivalent search problem. It is shown in [47] that depending on the system parameters {a, h, c\\, C2,pd}, there are three different threshold levels ,5. In particular, whether which threshold level is applicable depends explicitly on the fixed points of the evolution equations in (A. 17) and (A.18). Let Pj\\t be the fixed point of c/>(-, At) in equation (A.17) and Ps u be the fixed point of (/)(-, Su) in equation (A. 18). P^t and Ps u are then given by: l-p, where we have defined: P 2 - ((1 - pd)q + h) - - pd)a + hf - 4(1 - p~^ P A T = . (A .22) l - / i PSu = fi = a + h - l . (A.23) /i is an eigenvalue of the target-task transition matrix, A (defined in (A.3)), and hence can be regarded as a measure of the memory in the target-task state transitions (e.g. if H — 0 then the target-task state transitions are i.i.d). Also, to express the main result of this section we need to define the following mappings of the information state by two different consecutive actions (i.e. {At, Su} and {Su, At}): PAt,Su(-) = M an optimal MCS selection policy described in (3.5) and by V*(-) : X —> 01 the associated value function. The proof is presented by contradiction: suppose an optimal policy u*(s,j) that is non-increasing in s. We will show that an increasing policy must exist with a less or equal cost. First, note that Proposition 3.4.2 (ii) implies that u*(s, 1) = 2 =>• u*(s, 2) — 2 and u*(s, 2) — 1 u*(s, 1) = 1. Hence u(s,j) is increasing in j , and consequently, it is enough to show that an optimal policy u*(s,j) exists that is increasing in s. Here, without loss of generality, assume j = 1 is fixed and we show that u*(s, 1) is increasing in s. The case of j — 2 can be treated with a similar argument. Define ro € § as ro — min {s € § : (his) < d\\(s)} where di(s) are delay costs. Note that based on Assumption 5.1, ci2(s) < d\\(s) for all s > TQ and d2(s) > di(s) for s < TQ. Define forte region i, denoted by It, as the collection of states for which the transmission mode i gives the minimum delay, i.e., 7\\ = {s € S : s < ro} and J2 — {s E S : s > ro}. Clearly, Proposition 3.4.2 (ii) implies that for any optimal policy /i*(s,j) /z*(s, 1) = 1, s e J i , /i*(s,2) = 2, 5 6 ^ 2 . (B.l) Assume an optimal policy u*(s,j) such that u*(s,l) is not increasing in s. It will be shown that the cost associated with u*(s,j) can be improved or replicated by a monotone policy. Without loss of generality, assume l ^ l > 1 since otherwise u*(s,l) must be monotone by (B.l) (here \\A\\ denotes the cardinality of set A). Let m i , 777,2, and 7713 be some integers. It is easy to see that by adjusting integers mi > 0, 7712 > 0, and 7712 > 0 any optimal non-monotone policy u*(s,l) for s E 3\\ can be described, starting from 124 Appendix B. Proof of Theorem 5 state ro, as follows. ro — 1 < s < r 0 + mi, ro + mi < s < r\\ := ro + mi + rn2 r\\ < s < r-i := ro + m\\ + m 2 + 77x3 s = r 2 , (if r 2 < JV), s > r 2 . 2 1 2 x where x denote the undetermined part of the policy (\"don't care\"), and TV is the maxi-mum channel state. Figures B.l(a) and B.l(b) show the portion of the policy constructed by (B.l) and (B.2) with TV > r 2 and TV — r 2 — 1, respectively. Here, the circles in row j and column s of the grid gives the action (selected transmission mode) in state (s,j). States associated with action 1 are shown by blank circles and states associated with action 2 are shown by filled circles. The hatched circles represent the states for which the optimal action is not determined by (B.l) and (B.2). The vertical lines in the fig-ures, show the border of the forte regions. It should be clear that the descriptions in (B.l) and (B.2) are valid for any non-monotone optimal policy for some integers mi > 0 and m 2 > 0, and rn3 > 0. This is as much construction as we need to complete the contradiction proof. We show that policies described in (B.l) and (B.2) and shown in Figure B . l can be improved by monotone policies. First, we derive conditions on delay variations for policies described by (B.l) and (B.2). Both cases in Figures B.l(a) and B.l(b) can be treated with the same argument as follows. Let 7*1 := ro + mi-t-m 2 and 2 := {ri,r\\ + l,... , r 2 — 1}. Assuming initial channel state r i , define random variable n to be the number of time-slots that the Markovian channel remains in set B before the first departure. Starting from initial channel state r i , let Ai denote the event the that channel first visits state r i — 1 (departure from left). Also, starting from initial channel state r i , let Ar denote the event that the channel first visits state r 2 (departure from right). Let pr := P(Ar) and pi := P(.A/) with the understanding that if r 2 > TV (Figure B.l(b)) then Ar = 0 and pr — 0. Note that since only adjacent channel transitions are allowed, the first departure must be in either one of the states r\\ — 1 or r 2 . The optimal cost in state (rj, 1) and (ri,2) is then given by V*(r1,l).= plE(an\\Al)V*(r1-l,l)+ prE(ah\\Ar)V*(r2,1) + E(J s ( r , 1, n)). (B.2) 125 Appendix B. Proof of Theorem 5 j = 2 j = l j = 2 j = l ro ro + mi T\\ (a) General form of non-monotone optimal policies with ri < N. i'Q ro + mi r i (b) General form of non-monotone optimal policies with 1-2 > N. T2 N Figure B . l : A general form of non-monotone optimal transmission mode selection poli-cies as described by (B.l) and (B.2): Blank and filled circles represent transmission mode-1 and transmission mode-2, respectively. Hatched circles represent undetermined transmission modes. r ( r i , 2 ) = p , E ( a f i | ^ ) r ( r i - 1,2)+ pr E(ah\\Ar) V*(r2, 2) + E ( J s ( n , 2, n)), (B.3) where E denotes expectation over h and Js ( r i , j , h) denotes the conditional expected cost over all trips of length h. started from state (r\\.j) and before any departure from set ¥>. Since by (B.2), p*(s,j) — j for s 6 B, so the switching cost is zero and the cost-per-stage is given by dj(sk) for sk G 23, and we have ^ s ( n , j , n ) = E \\ yZakg(sk,j,j)\\n Sfce23 U=o 126 Appendix B. Proof of Theorem 5 n = i ' E a ' d j W l f i - 5o = r i . (B.4) S k & U=o J By (B.2), / z * ( n - 1,1) = 2, and ,j*(r2, 1) = 2, so V > i - l , l ) = C s-rV * ( r i - l , 2 ) , V*(r2,l) = Cs + V*(r2,2). (B.5) Subtracting equations in (B.2) and substituting from (B.5) gives V\\rul)-V%ru2)=plE(aA\\Ai)Cs+prE(afi\\Ar)C8-r • E ( J B ( r i , l , f i ) ) - E(J s (r i ,2 ,n)) - E (a\"C s + J s ( n , l , 7 i ) - Mn,2,n)) . (B.6) Also, since u*(ri, 1) = 1, we need V*(ri, 1) — V*(ri , 2) < C s , otherwise, in state (ri, 1), it is not worse to pay switching cost Cs and select the transmission mode 2 which is a contradiction. It follows by (B.6) that E (ahCs + J B ( n , 1, n) - Jv(n, 2, n)) < Cs. (B.7) Therefore, there exists some integer value n — TLQ such that an°Cs + Mn, 1,n0) - Mn,2,n0) < C s . (B.8) On the other hand, (B.4) gives J s(7-i , l ,n 0)-Ja}(ri,2,no)) = V\\f2«k(di(sk)-d2(sk))\\. (B.9) S A : 6 U=o J Let A(s) := di(s) - d2(s). Assumption 5.1 then implies A(s) > A(ri) > 0, Vs € 03. It follows by (B.9) that Mn,l,n0) - Mn,2,nQ) > A ( n ) ^ - . (B.10) 1 — a 127 Appendix B. Proof of Theorem 5 By (B.8) and (B.10), we have 1 - an° A ( n ) - < (1 - an°)Cs. I — a The dependence on no remarkably vanishes, hence the following local necessary condition is obtained A ( r x ) < (1 - a)Cs. (B.ll) Therefore, for any non-monotone pattern described by (B.2), we have a necessary con-dition given by (B.ll) on the delay variation in state r\\ (smallest channel state in set We repeat the above argument for a single element set B ' — {n — 1} with the optimal action p*(r\\ — 1,1) = 2. Assuming initial channel state r\\ — 1, define random variable fh to be the first departure time of the Markovian channel from set B ' . As defined in (B.4), J!%(r, l ,m) is then the conditional expected cost over all trips of length fh inside B ' before any departure. Furthermore, observe that Proposition 3.4.l(i) gives V * ( r i - l , l ) < C a + V * ( r i - l , 2 ) , V*(r2,l)