Joint Queue-Aware and Channel-Aware Delay Optimal Scheduling of Arbitrarily Bursty Traffic over Multi-State Time-Varying Channels
Meng Wang Juan Liu Wei Chen Anthony Ephremides




















Joint Queue-Aware and Channel-Aware Delay Optimal Scheduling of Arbitrarily Bursty Traffic over Multi-State Time-Varying Channels
    Meng Wang, Juan Liu, Wei Chen, Senior Member, IEEE, Anthony Ephremides, Life Fellow, IEEE







    December 30, 2023
=================================================================================================================================

1.5

This paper is motivated by the observation that the average queueing delay can be decreased by sacrificing power efficiency in wireless communications. In this sense, we naturally wonder what is the minimum queueing delay when the available power is limited and how to achieve the minimum queueing delay. To answer these two questions in the scenario where randomly arriving packets are transmitted over multi-state wireless fading channel, a probabilistic cross-layer scheduling policy is proposed in this paper, and characterized by a constrained Markov Decision Process (MDP). Using the steady-state probability of the underlying Markov chain, we are able to derive the mathematical expressions of the concerned metrics, namely, the average queueing delay and the average power consumption. To describe the delay-power tradeoff, we formulate a non-linear programming problem, which, however, is very challenging to solve. By analyzing its structure, this optimization problem can be converted into an equivalent Linear Programming (LP) problem via variable substitution, which allows us to derive the optimal delay-power tradeoff as well as the optimal scheduling policy. The optimal scheduling policy turns out to be dual-threshold-based, which means transmission decisions should be made based on the optimal thresholds imposed on the queue length and the channel state.





Cross-layer design, delay-power tradeoff, quality of service, probabilistic scheduling, controllable queueing system, Markov Decision Process.






















§ INTRODUCTION
















With the explosive proliferation of mobile devices, future wireless networks should provide an increasing number of multimedia applications  with more stringent Qualities of Service (QoS). Among various QoS metrics, latency and energy efficiency are two key metrics of interest<cit.>. Low latency is highly expected when providing delay-sensitive or time-critical applications such as in Tactile Internet <cit.> and is an important metric in URLLC (Ultra-Reliable Low Latency Communications) which is a new feature brought by 5G <cit.>. Meanwhile, high energy efficiency is urgently required especially for mobile devices powered by rechargeable batteries of finite capacity. Thus, it is of great importance to study the delay optimal and energy/power efficient transmission strategy for users in wireless communications<cit.>. Intuitively, to reduce the latency, the transmitter would conduct transmission more frequently or increase the transmission data rate, which inevitably costs more transmission power. Therefore, there exists a fundamental tradeoff between the average queueing delay and the average power/energy consumption. 

In general, it is very challenging to derive the delay-power tradeoff in wireless communication systems, considering the randomness of data packet arrivals, and the time-varying characteristics of wireless channels. These randomness occur in different layers of the transmitter, which increases the difficulty of characterizing the delay-power tradeoff<cit.>. To deal with this issue, the cross-layer design framework, first presented in <cit.>, was proposed to capture the uncertainties occurring at different layers in the last decades<cit.>.

Within the cross-layer architecture, many works have focused on revealing the delay-power tradeoff, which can be classified into two major categories. One line of the works attempt to find the analytical delay-power tradeoffs by considering some ideal or simplified  assumptions on the system model <cit.>. In <cit.>, the authors proposed a scheduling policy named Lazy scheduling which assigns transmission chances based on the backlog in the queue under the assumption that the arrival times of the packets are known in advance. In <cit.>, the authors minimized the transmission power with QoS constraits by assuming that the data arrival is known ahead of schedule and the channel is static or slow fading. The power constrained delay minimization problem was studied for a cognitive multi-access channel and a two-state block fading channel in <cit.> and <cit.>, respectively. 
This line of works mainly provide theoretical value more than engineering value, since the assumptions are too ideal to be practical. However, they are able to provide deeper insights to guide for engineering applications such as protocol design. 



The works in the other category consider more complex and practical system models<cit.>. In <cit.>, Berry and Gallager proposed  adapting the users' transmission rate and power by regulating the average power and average buffer delay over a wireless fading channel. They also focused on studying the cross-layer resource allocation in wireless fading channels for <cit.> and deriving the optimal power-delay tradeoff for a single user in the regime of asymptotically small delays in <cit.>. Ata investigated the power minimization problem subject to the packet drop rate in <cit.>, assuming the fixed channel state, Possion packet arrival and exponentially distributed packet size. In <cit.>, the authors studied the delay-bounded packet scheduling problem with bursty traffic arrival over wireless channels. This line of works studied the delay-power curve and analyzed its property under some circumstances. While it is difficult to derive theoretical solutions in general cases. This line of works mainly focus on studying resource allocation solutions and designing efficient algorithms for practical usage, which is of great importance in designing delay/power-efficient wireless transmission strategies.





More recently, 

a simple probabilistic scheduling policy was proposed to achieve the minimum queueing delay under power constraint in our previous work <cit.>, where Bernoulli packet arrivals and a two-state fading channel model were considered. Further, arbitrarily random packet arrival patterns were considered to capture the impact of bursty network traffic in <cit.> and adaptive transmission is considered in <cit.>. In these works, we proved that the optimal delay-power tradeoff can be achieved by applying the optimal scheduling polices which determine packet transmissions based on the threshold imposed on the queue length. The structured policy is appealing for the scheduler thanks to its ease of  deployment
. Hence, it inspires us to further dig into this topic. We naturally wonder if the optimal solution still has a special structure in more general scenarios and what kind of structure it may have.

In this paper, we study the delay-power tradeoff in wireless packet transmissions in a more realistic but complex communication system, where data packets are generated from an arbitrarily bursty traffic and a multi-state wireless fading channel is considered. Some potential application scenarios are shown in <ref>. The major challenges of this work lie in two aspects: 1) how to perform probabilistic scheduling jointly based on the randomness of the data packet arrival, the occupancy of the transmission data queue, and the time-varying characteristics of the wireless channel, and 2) how to reveal the structure of the optimal policy.

At the first task, the major challenge confronted is to build a proper cross-layer framework which includes all the system dynamics. Incorporating all these effects, our proposed scheduling policy performs joint scheduling based on the time-varying environment. Hence, it is very challenging to formulate the optimal cross-layer scheduling problem while facilitating theoretical analysis of its optimal solution. To deal with this difficulty, we propose a stochastic scheduling policy being aware of packet arrival, buffer and channel states. Then, we formulate a non-linear optimization problem to find the optimal probabilistic scheduling parameters. The challenge behind the second task is how to solve the optimal scheduling problem and derive the closed-form solution. This lies in the fact that the dimensionality of solving the optimal scheduling problem increases significantly due to the enlarged number of scheduling parameters that increases linearly with the number of channel and packet arrival states. By solving the obtained non-linear problem, we can surely obtain the optimal delay-power tradeoff. However, it is not trivial to search for the optimal solution to the non-linear optimization problem, let alone derive the optimal scheduling solution theoretically. To deal with this challenge, we first find a method to convert it to an LP problem, through which we can further analyze the structure of the optimal solution and reveal that the optimal scheduling policy has a dual-threshold-based structure step by step. By dual-threshold-based, we mean that packets should be transmitted based on the thresholds imposed on not only the queue state but also the on channel state. 







The remainder of this paper is organized as follows. The system setting is introduced in Section <ref>. In Section <ref>, we propose the probabilistic scheduling policy to schedule packet transmissions based on the buffer and the channel states simultaneously. In Section <ref>, 
we formulate a non-linear power constrained delay minimization problem and then convert it to an equivalent LP problem. In Section <ref>, we reveal that the optimal scheduling policy is dual-threshold-based with a rigorous mathematic proof and propose an algorithm to find simplified suboptimal policy. Simulation results are demonstrated in Section <ref> to validate the dual-threshold-based policy and concluding remarks are presented in Section <ref>. Some notations frequently used are explained as follows. Given a positive integer K, the notation  𝕂 denotes an integer set {0,1,2,⋯,K} while 𝕂^+ denotes integer set 𝕂/{0}. Sets 𝕎 and 𝕎^+, 𝕄 and 𝕄^+ are defined in the same way.[Part of this work was published in <cit.>, where main results were presented while most important derivations for some conclusions towards the dual-threshold-based structure were omitted due to the limited space.]

























































































§ SYSTEM MODEL
 



We consider a wireless communication system where the source node transmits to the destination over a time-varying wireless link. As shown in <ref>, packets of bursty traffic generated by higher-layer applications arrive at the network layer randomly, and are stored at the buffer in the data link layer. In the physical layer, the transmitter determines when to transmit the queued packets over a multi-state wireless channel, with the aid of efficient scheduling policies.

Let a[n] denote the number of packets randomly arriving in the nth slot. To capture the burstiness and variability of real-time applications, we assume an arbitrarily packet arrival pattern, i.e., the number of newly arriving packets could follow any distribution. Suppose that a[n] is independent and identically distributed (i.i.d.). Thus, the mass probability function of a[n] can be characterized by

    Pr{a[n]=m}=θ_m, m = 0,1,2,⋯

where θ_m ∈ [0,1]. Considering traffic shaping and admission control adopted in the system, the number of packets newly arriving in each time slot must be upper-bounded by a large integer M. In other words, there exists a positive  integer M such that θ_m = 0, for all m>M, and ∑_m=0^Mθ_m=1. The average packet arrival rate a̅ is obtained as

    a̅=lim_N→∞sup  1/N∑_n=0^N a[n] =∑_m=0^M m·θ_m.


At the source node, a buffer is employed to store the backlogged packets which cannot be sent immediately. 
The queue state, denoted by q[n], is characterized by the number of packets in the buffer at the end of nth slot and updated as

    q[n]   =max{ min{q[n-1]+a[n], K}-s[n] , 0 },

where s[n] is the transmitted packets in the nth time slot and K is the capacity of the buffer[Packet overflow will occur if K is quite small. In this work, we assume that K is a sufficiently large constant such that no packet overflow will occur. In Section V, we give the conclusion that if K is greater than a threshold, the queueing length will never reach the capacity according to our proposed scheduling scheme. Thus, the max operation in (<ref>) can be omitted.]. 







We adopt a W-state block fading channel model, where W is a positive integer. Let h[n] denote the channel state in the nth time slot. By  block fading, we mean that the channel state h[n] stays invariant during each time slot and follows an i.i.d. fading process across the time slots. Here, the discrete W channel states indicate different wireless channel qualities. Let  d_1 = 0 < d_2 <⋯ < d_W < d_W+1 = ∞ be the channel power gain levels. If the channel gain in the nth time slot ranges in interval [d_w,d_w+1), we say that the wireless channel is at state w. 
Since the channel quality becomes better with the increase of the index, w = 1 and w = W represent the worst and the best channel condition, respectively. 
The mass probability function of h[n] is described as

    Pr{h[n] = w }=η_w,

where η_w ∈ [0,1] and w∈𝕎^+.









Suppose that there exists a feedback channel through which the Channel State Information (CSI) is sent back from the receiver to the transmitter. Intuitively, the transmission power shall be adapted to the channel state to meet the requirement of successful packet delivery. Let P_w (w∈𝕎^+) denote the power needed to transmit one packet successfully in the channel sate w. Since more power is required to combat wireless channel fading when the channel condition is worse, it is reasonable to assume P_1>P_2>⋯>P_w>⋯>P_W.

In our model, we consider a fixed-rate transmission scheme which has been widely adopted in practice <cit.>. Without loss of generality, we assume the transmission rate is one packet per slot. Hence, at most one data packet can be delivered in each slot, namely, s[n] ∈ {0,1}.


In the cross-layer design framework shown in <ref>, the scheduler will schedule packets transmissions in each slot n based on the packet arrival state a[n], the queueing state q[n-1], and the channel state h[n] subjected to a power constraint, as will be discussed in details in the next section where the scheduling problem is treated as a power constrained Markov Decision Process (MDP), and discussed in Section <ref>.




§ PROBABILISTIC SCHEDULING POLICY


In this section, we introduce a probabilistic scheduling policy based on which the transmitter decides whether or not to deliver one data packet to its receiver in each slot.



 §.§ Probabilistic Scheduling


To improve the power efficiency, the transmitter should exploit a better channel state to deliver the packets to spend much less power. Thus, the source is more willing to keep silent till the channel state gets better. However, this may induce undesirable large latency waiting for good channel states, which is intolerable for serving delay-sensitive or time-critical traffics. To overcome this issue, some backlogged packets should be transmitted immediately at the cost of consuming higher power, even when the channel state may not be so good. Hence, the proposed scheduler must achieve a balance between the average delay and the power consumption.

In this work, a probabilistic cross-layer scheduling policy is proposed to schedule packet transmissions in each time slot. At the beginning of the nth time slot, the scheduler collects the current system state including the queueing state q[n-1]=k, the packet arrival state a[n]=m, and the channel state h[n]=w. Given q[n-1]=k, a[n]=m, and h[n]=w, it decides to transmit one packet with probability f_k+m,w or keep silent with probability 1-f_k+m,w
. By f_k+m,w, we mean that the scheduler can schedule packet transmissions based on the updated queue state q[n-1]+a[n]=k+m after one packet arrival. The reason lies in the fact that one of the packets newly arriving at this slot can be delivered immediately. Hence, it is not necessary to distinguish between the backlogged packets and the newly arriving packets.  Clearly, the transmission probability f_k+m,w lies in the interval  [0,1]. 

According to the above probabilistic scheduling policy, the number of transmitted packets s[n] for the current slot is a random variable, the probability mass function of which is given by 

    s[n]={[   1     w.p.    f_k+m,w,; 0     w.p.    1-f_k+m,w, ].

where k ∈𝕂, m ∈𝕄, w ∈𝕎 and the abbreviation 'w.p.' is short for 'with the   probability  of'[In Eq. (<ref>), when a[n]+q[n-1]=0, there is no packet waiting to be transmitted,  and when a[n]+q[n-1]>K, packet loss will happen. Thus, f_0,w (w ∈𝕎) and f_k+m,w (k+m>K, w ∈𝕎) are set as zero for notational consistence.].













We aim to find the optimal policy with a set of optimal transmission probabilities {f_k+m,w^*}  that can minimize the average queueing delay under an average transmission power constraint.






 §.§ Markov Decision Process
 


Based on the scheduling policy in section <ref>, the scheduler makes decision of transmitting s[n] packet(s) in every slot. The transmission decision affects the number of the packets queueing in the buffer as well as the transmission power. In this sense, we model the scheduling problem as a constrained MDP with the queue length q[n] being the system state. The decision, either waiting or transmitting (s[n]∈{0,1}), is treated as one candidate action taken at the current state. Executing each action certainly causes some system costs, namely, the delay cost associated with the queue length and the power cost associated with the packet transmission. Let τ_k,l denote the one-step state transition probability from state q[n-1]=k to state q[n]=l, i.e., 

    τ_k,l =Pr{q[n]=l | q[n-1]=k}.

The transition probabilities of the underlying Markov chain are presented in Lemma <ref>.


	The forward and backward state transition probabilities denoted by λ_k,m=τ_k,k+m and μ_k=τ_k,k-1 are obtained as
	

	
    λ_k,m    = θ_m∑_w=1^W η_w(1-f_k+m,w) + θ_m+1∑_w=1^W η_w f_k+m+1,w ,

	
    μ_k    = θ_0∑_w=1^W η_w f_k,w,

	

	where k ∈𝕂 and m ∈𝕄^+. The state transition probability λ_k,0 is the probability that the queue length remains the same, given by
	

	
    λ_k,0=τ_k,k={[     1 -∑_m=1^Mλ_k,m,                 k=0,; 1 -∑_m=1^Mλ_k,m-μ_k,              k ∈𝕂^+. ].



From Eq. (<ref>), the transition from state q[n-1]=k to q[n]=k+m takes place with probability λ_k,m when a[n]-s[n]=m.[Due to the assumption in Footnote 1, the operators "max" and "min" in Eq. (<ref>) can be omitted here.] This happens in two cases. In Case I, when there are a[n]=m packets arrive at the queue over channel state w, no packet is delivered (s[n]=0) with probability 1-f_k+m,w. In this situation, the transition probability is θ_m(1-f_k+m,w).In case II, when there is a[n]=m+1 packets arrive at the queue over channel state w, one packet is transmitted (s[n]=1) with probability f_k+m+1,w. Accordingly, the transition probability is θ_m+1f_k+m+1,w. Combining these two cases,  λ_k,m can be calculated using the law of total probability, and shown in Eq. (<ref>). Similarly, the probability μ_k can be derived, as given by Eq. (<ref>). The probability λ_k,0 given by Eq. (<ref>) is obtained using probability normalization.

Notice that, τ_k,l=0 holds for |l-k|>M, since the queue length increases from k up to l=k+M after one packet arrival. In <ref>, we show an example of the MDP model with M=2. In each time slot, q[n] increases by no more than M due to one new data arrival, while decreases by one since at most one packet can be delivered. Let matrix Λ denote the (K+1)-by-(K+1) transition probability matrix of the underlying Markov chain. The (j+1,i+1)-th element of Λ is transition probability τ_i,j. The transition probability matrix Λ is a banded matrix, since the number of the newly arrival packets and departing packets are limited in one slot.


















Let π_k denote the steady-state probability of the queue length being equal to k. The stationary distribution of the system state is denoted by the vector π = [π_0,π_1,⋯, π_K]^T, where the superscript T denotes matrix transpose. Vectors 1 and 0 are used to denote the (K+1)-dimensional column vectors whose entries are zero and one, respectively. According to the property of the steady-state probability, we have Λπ=π and 1^T π =1. Hence, the stationary distribution π is the solution to the following linear equations

    [
    [ 𝐐_K; 1^T ]]π =
    [
    [ 0; 1 ]],

where 𝐐_K is a matrix consisting of the first K rows of the generator matrix 𝐐 = Λ - 𝐈. From Eq. (<ref>) and Lemma <ref>, we can see that the steady-state probability π is determined by the scheduling policy with the parameters {f_k+m,w}.












































































§ DELAY AND POWER TRADEOFF



In this section, we first analyze the two key performance metrics: the average queueing delay and the average power consumption. Then, we formulate optimization problems to describe the delay minimum power constrained scheduling problem, based on the stationary probability of the built Markov Decision Process.




 §.§ Delay and Power Metrics



In accordance with every transmission action s[n], the scheduler spends some system costs due to queue occupation and packet transmission. Given action s[n], the queueing cost for buffer occupation is denoted by C_q[n] and the power cost for packet transmission is denoted by C_p[n], respectively, expressed as

    C_q[n]=(q[n-1]+a[n]-s[n])^+  and C_p[n]=P_w s[n]

As time goes by, the time-average costs can be built up as 

    Q_Ω = lim_N→∞1/N∑_n=1^NC_q[n]  and  
    P_Ω = lim_N→∞1/N∑_n=1^NC_p[n],

respectively. Considering  the minus and connotative plus operators before s[n] in Eq. (<ref>), an action s[n] exerts opposite influences on the buffer occupation and power consumption, which naturally leads to a tradeoff between the average  delay (the Little's Law) and the average power.

The above analyses explain the average delay and the average power from the cost perspective of the scheduling policy. It's much easier to understand the tradeoff from the expressions of the two metrics given in Eq. (<ref>). To mathematically derive the two metrics, we refer to the MDP model built in Section <ref>. Once the stationary distribution π is obtained, the average queueing delay and power consumption can be derived and shown in the following theorem. 
 
	Given a probabilistic scheduling policy {f_k+m,w}, the average queueing delay D and power consumption P can be expressed as
	
    D = 1/a̅∑_k=0^K kπ_k, 
       P = ∑_k=0^K  π_k ∑_w=1^W  η_w P_w ∑_m=0^M   θ_m f_k+m,w.



	Given the stationary probability distribution of the Markov chain, the average queue length can be expressed as Q = 𝔼{q[n]}= ∑_k=0^K kπ_k.
	
	
	
	Then according to the Little's Law <cit.>, the average queueing delay D can be derived as Q/a̅ and shown in Eq. (<ref>). 
	
	With C_p[n] = P_ws[n], we have C_p[n]=P_w and C_p[n]=P_0=0, respectively, when one packet is transmitted over the channel state w, i.e., s[n]=1, and no transmission takes place, i.e., s[n]=0. Let ψ_k,w denote the conditional probability of C_p[n]=P_w (w ∈𝕎 = {0 ∪𝕎^+}) given the queue state q[n-1]=k and channel state h[n]= w. It can be expressed as
	
	
	
	
	
    ψ_k,w =   Pr{ C_p[n]=P_w | q[n-1]=k,h[n]= w } 
    	=  {[ ∑_m=0^Mθ_m f_k+m,w,             w ∈𝕎^+,;     1-∑_w=1^Wψ_k,w,              w = 0. ].

	
	
	
	
	By the law of total probability, the average power can be derived as
	
	
	
	
	
	
	
    P=    ∑_k=0^K ∑_w=1^W  Pr{q[n-1]=k}Pr{h[n]=w}Pr{ C_p[n]=P_w | q[n-1]=k,h[n]=w }× P_w 
    
    	=     ∑_k=0^K ∑_w=1^W  π_k η_w ψ_k,wP_w  
    
    	=    ∑_k=0^K  π_k ∑_w=1^W  η_w P_w ∑_m=0^M   θ_m f_k+m,w.



We notice that, the steady state probability π is an  implicit function of the transmission probabilities, since it is uniquely determined by the transmission probabilities {f_k+m,w} based on the analyses in Section <ref>. Thus, from Theorem <ref>, the average queueing delay and the average power consumption are both functions of transmission probabilities.






 §.§ Delay-Power Tradeoff



To find the optimal scheduling policy with a set of transmission probabilities {f_k+m,w^* | , k ∈𝕂, m ∈𝕄, w ∈𝕎}, we formulate an optimization problem to minimize the average queueing delay D under the power constraint P_aver as follows:

    min_{f_k+m,w}  D=1/a̅∑_k=0^K kπ_k 
       s.t.{[     P  ⩽ P_aver             (a); f_k+m,w∈ [0,1],             (b);            𝐐π=0             (c);        1^T π =1             (d);           0≼π≼1             (e) ].

where k ∈𝕂, m ∈𝕄,  w ∈𝕎, and symbol '≼' represents the component-wise inequality between vectors. In problem (<ref>), the objective is to minimize the average queueing delay. Constraint (<ref>.a) denotes the maximum power constraint. Constraint (<ref>.b) indicates the range of the optimization variables {f_k+m,w}. Constraints (<ref>.c-<ref>.e) are derived from the properties of the Markov chain. Constraint (<ref>.e) specifies the range of the steady-state probabilities. Since problem (<ref>) is a non-linear programming problem, it is rather difficult to obtain the optimal solution { f_k+m,w^* } analytically. To make it tractable, we first convert problem (<ref>) into an equivalent LP problem via variable substitution.




 §.§ LP Problem Formulation



To formulate an LP problem, we introduce a set of new variables {y_k,w | k ∈𝕂, w ∈𝕎} as

    y_k,w = ∑_m=0^Mπ_k+1-mθ_m f_(k+1-m)+m,w  = ∑_m=0^Mπ_k+1-mθ_m f_k+1,w.

In Eq. (<ref>)[We assume the steady-state probability whose subscript is negative is zero for notation convenience. Otherwise, variable y_k,w should be defined as y_k,w = ∑_m=0^min{M,(k+1)}π_k+1-mθ_m f_k+1,w.], π_k+1-mθ_m f_k+1,w is the probability of transmitting one packet, i.e., s[n]=1, when there are q[n-1]=k+1-m data packets in the buffer and a[n]=m data packets newly arriving at the transmitter. Thus, y_k,w is the probability that there are k packets backlogged in the queue after one packet transmission over channel state w. This procedure allows us to express the objective function and the constraints of (<ref>) as linear functions of {y_k,m}. Hence, we are able to  convert the non-linear problem (<ref>) into a more tractable LP problem, as shown below.

	Let ξ = ∑_m=1^M-1m(m+1)/2θ_m+1 be a constant. The optimization problem (<ref>) is equivalent to the following LP problem:
	
    min_{ y_k,w}  D=1/a̅^2( ∑_k=0^K∑_w=1^W k η_w y_k,w - ξ) 
       s.t.{[                   P=∑_k=0^K∑_w=1^W η_w P_w y_k,w⩽ P_aver                                                      (a);                            ∑_k=0^K∑_w=1^W η_w y_k,w = a̅                                                      (b); 0 ⩽ y_k,w⩽∑_m=0^Mθ_m∑_i=0^K∑_j=1^W G_(k+2-m,iW+j)· y_i,j                                                      (c);                                                          ].

	where G_(i,j) is the (i,j)-th element of (K+1) ×[W(K+1)] matrix G which describes the relationship between the steady-state probabilities {π_k} of the Markov chain and the variables {y_k,w}, as given by
	
    π_k = ∑_i=0^K∑_j=1^W  G_(k+1,iW+j)· y_i,j,




	The detail is given in Appendix <ref>.


As shown in problem (<ref>), there exists a minimum queueing delay for any feasible power constraint P_aver. Hence, the optimal queueing delay D^* can be expressed as a function of P_aver, i.e., D^*=d(P_aver). In the following theorem, we reveal the decreasing  property of the delay-power function to discuss the structure of the optimal scheduling policy in the next section. 

	The delay function D^∗=d(P_aver) monotonically decreases with the maximum transmission power P_aver.


	The detail is given in Appendix <ref>.

Till now, we construct an LP problem to describe the delay-minimal scheduling problem under power constraint. After deriving the optimal solution y_k,w^*, we can then obtain the steady-state probability π_k^* by Eq. (<ref>) and the optimal scheduling probability {f_k,w^*} by Eq. (<ref>). In the sequel, we show how to derive the optimal solution as well as the optimal probabilities. 






§ DUAL-THRESHOLD-BASED POLICY
 

In this section, we focus on revealing the dual-threshold-based structure of the optimal scheduling policy. We first present the definition of the threshold-based structure.

	Let 𝕀={0,1,2,⋯} denote an integer set. A probability set {Υ_i | i ∈𝕀} has a i^*-threshold-based structure if and only if there exists an optimal threshold  i^*∈𝕀 such that Υ_i = 0, i < i^* and Υ_i = 1, i > i^*.

In what follows, we show that the optimal scheduling policy has such a structure on both the buffer state dimension and the channel state dimension, referred to as a dual-threshold-based policy. An example of the structure is illustrated in <ref>, where positive scheduling probabilities with the indexes of buffer and channel states are plotted, and zero scheduling probabilities are omitted for briefness. In particular, given the queue state k, the optimal scheduling probabilities {f_k,w^*} follows a threshold-based structure, i.e., f_k,w^*=1 for w>T_k^* and f_k,w^*=0 for w<T_k^*, where T_k^* is the optimal threshold on the channel state dimension. Similarly, given the channel state w, the optimal scheduling probabilities {f_k,w^*} has a threshold-based structure on the queue state dimension. That is, there exists an optimal threshold I_w^*  on the queue state such that f_k,w^*=1 for k>I_w^* and f_k,w^*=0 for k<I_w^*, respectively.
The proof of the dual-threshold-based policy is presented in two steps in subsections A and B, in accordance with the two dimensions of the channel and buffer states. What's more, we show that there is at most one threshold state (k^⋆, w^⋆) at which the optimal scheduling probability is non-zero in subsection C. Simplified threshold policy is proposed to achieve suboptimal performance in subsection D.






















 §.§ Threshold-based Structure on the Channel State Dimension


We firstly reveal the non-decreasing property of the optimal solution {y_k,w^*} to problem (<ref>). Then, we equivalently transform problem (<ref>) into a new problem, which facilitates us to prove that {y_k,w^*} has a T_k-threshold-based structure. By mapping {y_k,w^*} back to {f_k,w^*}, the optimal scheduling policy is shown to have a threshold-based structure.


	The optimal solution to problem (<ref>) {y_k,w^*} has the following property, for any queue length k, 
	
    y_k,w_1^*⩽ y_k,w_2^*,   ∀   0 < w_1 < w_2 ⩽ W.



	The detail is given in Appendix <ref>.


Recall that, y_k,w is the probability that there are k packets left in the queue after one packet transmission over channel w. Thus, the physical meaning of Lemma 2 is that, it reveals the tendency of exploiting a better channel state when one transmission has to be performed for the optimal policy.


	The LP Problem (<ref>) is equivalent to the following problem
	
    min_{y_k,w}  D=1/a̅( ∑_k=0^K  k ·max_w{y_k,w} - p_0π_0 - ς) 
       s.t.{[ max_w{y_k,w} = ∑_m=0^Mθ_mπ_k+1-m                              (a);           (<ref>.a) - (<ref>.c),;                                  ].

	where ς=∑_i=1^M-1 i θ_i+1 - θ_0 is a constant. 



	The detail is given in Appendix <ref>.


With above two lemmas, we derive the threshold structure imposed on the channel state for a given queue length of the optimal solution {y_k,w^*} to problem (<ref>) as follows:

	For any queue length k, there exists an optimal integer threshold T_k^* ∈𝕎 such that the variables {y_k,w^*} has a T_k^*-threshold-based structure, i.e.,
	
    {[                      y_k,w^* = 0,                    0 < w < T_k^*;; 0 ⩽ y_k,w^* ⩽∑_m=0^Mθ_mπ_k+1-m^*,                        w = T_k^*;;   y_k,w^* = ∑_m=0^Mθ_mπ_k+1-m^* ,                        w > T_k^*.;                                   ].




	The detail is given in Appendix <ref>.


On one hand, Theorem <ref> is a stronger conclusion compared to Lemma 2 where the tendency of the optimal policy is revealed. It illustrates that one packet can only be transmitted if the channel state is better than a threshold. On the other hand, with the bond between  {y_k,w^*} and {f_k,w^*}, the threshold structure in Theorem <ref> reflects the structure of the optimal scheduling policy {f_k,w^*}. Specifically, the optimal scheduling probability f_k,w^* is derived according to Eq. (<ref>) and given as 1) f_k,w^* = 0, if w<T_k; 2) f_k,w^* = 1, if w>T_k; 3) f_k,T_k^* = y_k-1,T_k^*(∑_m=0^Mπ_k+1-m^*θ_m)^-1. Thus,  {f_k,w^*} also satisfies Definition <ref> and the optimal scheduling policy has a threshold-based structure on the channel state dimension for any given queue length k. 















 §.§ Threshold-based Structure on the Queue Length Dimension


















It is not a trivial work to reveal the threshold structure on the queue state dimension straightforwardly due to the highly complicated relationship between the variables {y_k,w^*}. Thus, we turn to the scheduling action s[n] taken by the optimal policy. Then, we map the transmission action s[n] back to the scheduling probability {y_k,w^*} and find that the optimal policy also has an I_w^*-threshold-based structure on the queue state dimension.


	For a given channel state w, there exists an optimal integer threshold I_w^* ∈𝕂 such that the optimal transmission action s^*[n] has the I_w^*-threshold structure, namely
	
    s^*[n]={[          0, t[n]<I_w^*;;          1, t[n]>I_w^*, ].

	where t[n] =q[n-1]+a[n] denotes the updated queue state after one new packet arrival in the nth time slot.


	The detail is given in Appendix <ref>.


In Lemma <ref>, we show that the optimal transmission action s^*[n] is determined based on the updated queue state t[n] and the optimal threshold I_w^*. Together with Eq. (<ref>), we can connect s[n] to the scheduling probability f_k,w^*, and reveal that the probabilities {f_k,w^*} also depend on the updated queue state t[n]=k and the optimal threshold I_w^*: 1) f_k,w^* = 0, if k < I_w; 2) f_k,w^* = 1, if k > I_w. Thus, the optimal policy is proved to has a threshold-based structure on the queue length for any given channel state.



 §.§ Dual-threshold-based Policy



The optimal scheduling policy turns out to be a dual-threshold-based policy, as illustrated in <ref>. We complete it as follows by specifying the values on the threshold points.

	(1) The optimal scheduling policy corresponds to a dual-threshold policy. In detail, a) for any queue length k, there exists a threshold T_k^* ∈𝕎, f_k,w^* = 0 for w < T_k^* and f_k,w^* = 1 for w > T_k^*; b) there exists T_1^* ⩾ T_2^* ⩾⋯⩾ T_K^*. (2) There is at most one threshold state (k^⋆, w^⋆) at which the optimal scheduling probability is non-zero.


Conclusion (1-a) is exactly the threshold structure obtained in subsection A. Combining the threshold structure imposed on the queue length for a given channel state, we obtain conclusion (1-b) which describes the non-increasing property of {T_k^*}.  The proof of conclusion (2) is given in Appendix G. 


According to our proposed scheduling scheme, once the queue length exceeds max_w {I_w^*}, one packet will be transmitted whatever the channel state. Thus, if we set the buffer capacity K>max_w {I_w^*}, the queueing length will never reach the capacity and no packet overflow will occur. The threshold structure is a tradeoff result of reducing the queueing delay and saving power resource. An intuition explanation that explains why the policy has such a structure can be found in Appendix H. 





 §.§ The Suboptimal Policy




It is not a trivial work to obtain closed-form expressions of the thresholds even if we have revealed their properties in Theorem 5. By solving the LP problem, we surely can obtain optimal thresholds and the non-zero scheduling parameter that might exist at one of the joint threshold points. Otherwise, we have to resort to some search methods to find these optimal thresholds directly. In what follows, we come up with two search methods in two different scenarios.





1.2



Scenario I: we develop a structured search algorithm to find a suboptimal solution by fully exploiting the non-increasing properties of the optimal thresholds, as presented in Theorem 5. In other words, this property helps to reduce the search space of the candidate threshold points significantly. In detail, combing the non-increasing property of the threshold points T_k, i.e., T_k_1⩾ T_k_2 if k_1 ⩽ k_2, and the fact that the buffer capacity K is usually greater than the number of channel states W, we know some neighbor queue lengths are likely to share a same threshold T_k. Based on this property, we can reduce the number of the thresholds points that need to be searched. In detail, the queue length range [0,K] can be divided into several small intervals, each of which is assigned one threshold imposed on the channel states. Thus, we only need to determine how to divide the queue states and assign one threshold for each small interval. The simplified suboptimal policy is given in Algorithm 1, where the total queue states is divided into two sub-intervals. A table can be built up to store the induced delay and power metrics for all the 1/2KW^2 simple policies. Then, to obtain the suboptimal policy for a given power constraint, we only need to look up the table and return the thresholds. The performance can be further improved by assigning one scheduling probability to some threshold points. 








































Scenario II: we find the optimal thresholds  by looking up a preset table. Specifically, we first set up a table containing the delay and power information of all possible candidates of the optimal thresholds {T_k^*, I_w^*} by performing intensive computations. The table formulation surely costs a lot of computation resources, but it can be done once for all.  Afterwards, when designing the optimal scheduling policy given the power constraint p_aver, we can first find the optimal thresholds {T_k^*, I_w^*} by comparing p_aver with the power information in the table. The optimal scheduling parameter f_k^⋆,w^⋆ can be further determined with the obtained {T_k^*, I_w^*} and p_aver. And different power constraints lead to different optimal thresholds and hence the optimal scheduling parameters.











§ NUMERICAL RESULTS
 




















In this section, simulation results are given to validate the derived dual-threshold-based scheduling policy and to demonstrate its potential. For performance comparison, theoretical results of the optimal delay-power function D^*(P_aver) are obtained by solving the LP problem (<ref>). Meanwhile, simulation results are obtained by applying the dual-threshold-based scheduling policy with the optimal transmission parameters. In simulations, data packets are generated following a given probabilistic distribution {θ_m}. The W-state block fading channel model is adopted and follows with probability {η_m}. Each simulation runs over 10^6 time slots. As shown in <ref>-<ref>, the theoretical and simulation results are plotted by lines (solid or dashed) and marked by red square dots, respectively.










































<ref> plots the delay-power tradeoff curves under different average packet arrival rates. The simulation results are in good agreement with the theoretical results, which validates the optimality of the derived dual-threshold-based policy. The delay-power tradeoff curve is piecewise linear since the threshold-based is obtained as the linear combinations of deterministic scheduling parameters. Besides, the average delay monotonically decreases with the maximum average power, as stated in Theorem <ref>. When the power constraint P_aver decreases to zero, the queueing delay increases dramatically to infinity, which implies that the queueing system is unstable. Given the same power constraint, the queueing delay increases with the packet arrival rate since more packets are detained in the buffer due to lack of transmission opportunities. 













In <ref>, we evaluate the effect of the burstiness of the packet arrival on the optimal delay-power tradeoff curves, considering different packet arrival patterns, namely, the Bernoulli arrival and the bursty arrival. We can see that the proposed scheduling policy has a better delay-power tradeoff performance when the packet arrivals follow the Bernoulli distribution rather than the more bursty probabilistic distribution (with larger variance), subject to the same average arrival rate. This is due to the fact that the bursty packet arrivals bring more randomness to the queueing system. The average queueing delay decreases with the increase of the power constraint and remains constant when the power constraint exceeds a constant P_max. In other words, the delay-power curve becomes flat after an inflection point (D^*_min, P_max),  where D^*_min is the globally minimum delay and P_max denotes the power consumption that the source spends to keep transmitting packets as long as the buffer is not empty, regardless of the channel state. However, the value of P_max is identical for the two different patterns. The value of D_min is able to reach zero for the Bernoulli arrival since the transmission rate is fixed as one packet per slot and is greater than zero due to the burstiness.   












Inspired by the observation in <ref>, we further demonstrate the delay-power tradeoffs in <ref> for the packet arrivals have the same average arrival rate and different variances. It is observed that a higher queueing delay is induced when the data arrival variance is larger. Due to higher bursty arrivals, some packets have to wait for a longer time before they are transmitted, which leads to a larger queueing delay. 











In <ref>, we demonstrate the theoretical results to validate the dual-threshold-based  structure of the optimal scheduling policy, which are in agreement with the structure shown in <ref>. The transmission probabilities reveal a threshold-based structure on both the channel state dimension and the queue length dimension. In <ref>, the threshold is in channel state 1 and queue length 8 while in <ref>, it is in channel state 1 and queue length 3. Thus, transmission is much easier to occur in <ref>, which corresponds to a higher power consumption. That is, the scheduler makes use of the power resource mainly by adjusting the threshold point for quite different power constraints. In <ref> and <ref>, it's calculated for both scenarios that the threshold is in channel state 1 and queue length 3. However the scheduler makes a decision of transmitting one packets with probability 0.2377 in <ref> and 0.4899 in <ref> on the threshold point, respectively. That is, the scheduler makes full use of the power resource mainly by adjusting the transmission probability on the threshold point for slight different power constraints. 



In <ref>, we plot the optimal delay-power curve of our proposed scheme and 1000 delay-power points of the deterministic policy with the binary transmission parameters f_k,w∈{0,1} randomly generated. As can be seen from this figure, the  delay-power tradeoff curve is the lower boundary of the convex hull of the achievable delay-power region, which is in accordance with the conclusion proved in [21] that the optimal probabilistic policy can be constructed by the convex combination of deterministic scheduling policies. Hence, our proposed optimal scheduling policy outperforms any deterministic scheduling policies given the same power constraint. Meanwhile,  our proposed stochastic scheduling policy with the optimal thresholds and scheduling parameters can achieve the same optimal delay-power tradeoff performance as the optimal scheduling policies found by the DP method.






In <ref>, we plot the delay-power tradeoff curves induced by the optimal policy and suboptimal policy proposed in subsection V-D. Since same suboptimal policy will be assigned to close power constraints, the suboptimal curve remains flat sometimes. Also, the suboptimal policy may indeed be the optimal policy for some power, thus, there exist intersections for the two curves. The suboptimal policy determines the scheduling with less threshold points compared to the optimal one, thus, it is easier to be found and apply but with less accuracy. One can also assign a probability for the threshold points and further make use of the power as given in the purple curves.





§ CONCLUSION
 



In this paper, we studied the power-constrained delay-optimal scheduling problem in wireless systems, where arbitrary packet arrivals and multi-state block-fading channels were considered. A probabilistic queue-aware and channel-aware scheduling policy was proposed to schedule packet transmissions over a W-state wireless fading channel and investigated in the framework of constrained MDP. Through theoretical analysis, we reveal the  dual-threshold-based structure of the optimal scheduling policy. It is found that the optimal scheduler always seeks to exploit a good channel while maintaining a relatively short queue as possible to reduce the latency. To this end, the scheduler should schedule packet transmissions based on the queue state and the channel state. Specifically, given a channel state, if the queue length exceeds the threshold, the transmitter  should transmit to decrease the latency. Otherwise, it should keep silent to save power. In the future, we will extend this work to more general  scenarios with adaptive-rate transmission and/or multi-user scheduling.











§ THE PROOF OF THEOREM <REF>


In this appendix, we show that problem (<ref>) can be equivalently converted into LP problem (<ref>) with variables {y_k,w} being the optimization variables. To make it clear, we explain the transformation procedure in the following five steps. We first present the equivalent expressions of the average queueing delay and the power constraint in Part <ref>. Secondly, we specify the ranges of optimization variables {y_k,w} corresponding to constraint (<ref>.b) in Part <ref>. Then,  we reformulate constraints (<ref>.c) and (<ref>.d) in Part <ref> and Part <ref>, respectively. Finally, we explain why constraints (<ref>.c) and (<ref>.e) are not shown in the LP problem (<ref>) in Part <ref>.



  §.§.§ The average queueing delay and the power constraint can be re-expressed as



    {[ D=1/a̅^2( ∑_k=0^K∑_w=1^W k η_w y_k,w - ξ),;            P=∑_k=0^K∑_w=1^W η_w P_w y_k,w, ].

where ξ = ∑_m=1^M-1m(m+1)/2θ_m+1.

Firstly, we re-express the average queueing delay. Adding the weighted sum of the terms ∑_w=1^Wη_w y_k,w with k being the weight, we have

    ∑_k=0^K k ∑_w=1^W η_w y_k,w =^ 1∑_k=0^K k ∑_m=0^M-1π_k-m∑_i=m+1^Mθ_i    
       =^ 2 (θ_1 + θ_2 + ⋯ + θ_M) ∑_k=0^K k π_k + (θ_2 + ⋯  + θ_M) ∑_k=0^K k π_k-1 +⋯ + θ_M ∑_k=0^K k π_k-(M-1)
       =^ 3 (θ_1 + θ_2 + ⋯  + θ_M) Q  + (θ_2 + ⋯  + θ_M) (Q+1) + ⋯  + θ_M  (Q+(M-1))               
       =^ 4a̅Q + ∑_m=1^M-1∑_i=1^m i θ_m+1
       =^ 5a̅Q + ∑_m=1^M-1m(m+1)2θ_m+1     =    a̅Q +   ξ,

where equality 1 is derived by substituting (<ref>), equality 2  is obtained by expressing each term in  π_k-m∑_i=m+1^Mθ_i separately for m=0,  1,  2,⋯, M-1, equality 3 comes from the definition of the average queue length, equality 4 is obtained by substituting a̅=∑_m=0^M m·θ_m, and equality 5 stems from ∑_i=1^mi=m(m+1)/2.
Thus, the average queue length is:

    Q = 1/a̅( ∑_k=0^K∑_w=1^W k η_w y_k,w - ξ).

According to the Little's Law, we obtain the average queueing delay as given in Eq. (<ref>).

Secondly, we express the average power as a function of variables {y_k,m}.
From the definition of variable y_k,w in Eq. (<ref>), we have

    ∑_k=0^K  π_k  ∑_m=0^M   θ_m f_k+m,w = ∑_k=0^K y_k,w.

By substituting Eq. (<ref>) into Eq. (<ref>), we obtain the average power as presented in Eq. (<ref>).















































  §.§.§ 	The variable y_k,w satisfies the following inequalities


    0 ⩽ y_k,w⩽∑_m=0^M θ_mπ_k+1-m.


We know that probability f_k+1,w takes its value from the  interval [0,1]. By substituting f_k+1,w=0 and f_k+1,w=1 in Eq.(<ref>), we get the lower and upper bounds of variable y_k,w, respectively. In this way, the range of variable y_k,w is specified by the inequalities in Eq. (<ref>).














  §.§.§ The constraint (<ref>.c) can be equivalently expressed as


    ∑_m=0^M-1π_k-m∑_i=m+1^Mθ_i = ∑_w=1^W η_w y_k,w = ∑_i=0^M-1π_k-i r_i.

where r_i=∑_m=i+1^M  θ_m.

In fact, constraint (<ref>.c) denotes the steady-state equilibrium equation of the underlying Markov chain:

    π_k+1μ_k+1= ∑_m=0^M-1π_k-m∑_i=m+1^Mλ_k-m,i,    k ∈ 𝕂.


We can obtain the following conclusion

    ∑_i=m^Mλ_k,i=    ∑_i=m^Mθ_i   -  θ_m∑_w=1^W η_w f_k+m,w,     m ∈𝕄

by adding up the terms {λ_k,i | i=m,⋯,M} in Eq. (<ref>). 

By substituting Eq. (<ref>) and Eq. (<ref>) into Eq. (<ref>), we have 

    π_k+1 ( θ_0∑_w=1^W η_w f_k+1,w )  = ∑_m=0^M-1 π_k-m (∑_i=m+1^Mθ_i   -  θ_m+1∑_w=1^W η_w f_k-m+m+1,w ).

Then, we can further simplify this equation as 	

    ∑_m=0^M-1π_k-m∑_i=m+1^Mθ_i
       = ∑_m = -1^M-1π_k-mθ_m+1∑_w=1^Wη_w f_k+1,w
       = ∑_w=1^Wη_w ( ∑_m = -1^M-1π_k-mθ_m+1 f_k+1,w )    
       =∑_w=1^Wη_w  y_k,w.



















































  §.§.§ The constraint (<ref>.d) can be re-expressed as ∑_k=0^K∑_w=1^W η_w y_k,w = a̅.
 

Summarizing all the k on both sides of Eq. (<ref>), we have 

    ∑_k=0^K∑_w=1^W η_w y_k,w 
    =∑_k=0^K∑_m=0^M-1π_k-m∑_i=m+1^Mθ_i =∑_m=0^M-1∑_i=m+1^Mθ_i    =a̅,

where the second equality holds because the normalization of the steady-state probabilities, i.e., ∑_k=0^Kπ_k =1.


To construct the LP problem (<ref>), we need to express π_k as a linear function of variables {y_k,m}. For ease of exposition, we introduce a (K+1) ×[W(K+1)] constant matrix G to describe the relationship between {π_k} and  {y_k,m} based on Eq. (<ref>). The (k+1)-th row vector of matrix G, denoted by g_k+1, is given as



    {[                                   g_k+1                             = 1/r_0l_1,                                    k=0,;                                   g_k+1 = 1/r_0 ( l_k+1 - ∑_i=1^M-1 r_i g_k-i),                                   k ∈𝕂. ].

In Eq. (<ref>), l_k+1 is a W(K+1)-dimensional vector whose (Wk+w)th element is η_w while the other elements are zero. In this way, the steady-state probabilities {π_k} can be linearly expressed by the set of variables {y_k,w}, namely,

    π_k = ∑_i=0^K∑_j=1^W  G_(k+1,iW+j)· y_i,j,

where G_(i,j) is the (i × j)-th element of matrix G.



  §.§.§ Constraints (<ref>.c) and (<ref>.e) can be left out in the new equivalent LP problem


The constraint (<ref>.c) is incorporated in the derivation of Eq. (<ref>) which is the reason that it can be left out. As for constraint (<ref>.e), since the elements in matrix G and variable y_i,j are non-negative, as given by Eq. (<ref>), π_k is clearly non-negative. On the other hand, since r_i (c.f.  Eq. <ref>) is non-negative and ∑_w=1^W η_w y_k,w is equal to or less than one, π_k is no more than one. Thus, constraint (<ref>.e) is also implied in  constraints (<ref>.c). 









In summary, we have shown that how to construct the LP problem (<ref>) step by step equivalently from problem (<ref>), which completes the proof of Theorem <ref>.



§ THE PROOF OF THEOREM <REF>



Suppose {y_k,w} is a set of variables that  minimize the average delay D under constraints [<ref>.(a-c)]. The corresponding transmission power P is equal to  ∑_k=0^K∑_w=1^W η_w P_w y_k,w. We show that if there exists another set of variables {ŷ_k,w} which cost a higher power P̂ > P to transmit, a smaller queueing delay D̂ < D will be induced.

Let k_th be a positive integer. We construct variables {ŷ_k,w} as follows:

    {[ ŷ_k,w = y_k,w + Δ y_k,w,                k ⩽ k_th;; ŷ_k,w = y_k,w - Δ y_k,w,                k > k_th, ].
 
where {Δ y_k,w} are set as non-negative quantities to make sure that variables {ŷ_k,w} meet constraints [<ref>.(b-c)] and the constraint P̂-P>0 is satisfied. Let Δ P = P̂-P, we then have

    Δ P = ∑_w=1^W η_w P_w (∑_k=0^k_thΔ y_k,w - ∑_k=k_th+1^KΔ y_k,w) > 0,

which means that Δ y_k,w strictly stays positive for some k ⩽ k_th. 

In this way, the average delay gap satisfies the following inequality 

    D̂-D 
       = 1/a̅^2∑_k=0^K∑_w=1^Wkη_w (ŷ_k,w-y_k,w)
       =1/a̅^2∑_w=1^Wη_w (∑_k=0^k_thk Δ y_k,w - ∑_k=k_th+1^K k Δ y_k,w)
       <1/a̅^2∑_w=1^Wη_w[k_th∑_k=0^k_thΔ y_k,w-(k_th+1)∑_k=k_th+1^KΔ y_k,w].
 


Since both {ŷ_k,w} and {y_k,w} meet constraint (<ref>.b), we have

    ∑_w=0^Wη_w ∑_k=0^k_thΔ y_k,w=∑_w=0^Wη_w ∑_k=k_th+1^KΔ y_k,w.

Combining Eq. (<ref>) and Eq. (<ref>), we know D̂<D.

We have proven that if P_aver^'<P_aver^”, then d(P_aver^”)<d(P_aver^'). Thus, the delay-power tradeoff function d(·) is a monotonically decreasing function of the average power.



§ THE PROOF OF LEMMA <REF>



We adopt the proof by contradiction, namely, if there exists a set of optimal variables {y_k,w} that do not meet Eq. (<ref>), we can find another set of variables {ŷ_k,w} that can use less power to obtain the same queueing delay, which contradicts Theorem <ref>. 

Suppose that, there exists a set of optimal variables {y_k,w}, in which there are 0 < w_1 < w_2 ⩽ W that make y_k,w_1 > y_k,w_2. With this solution, the minimum delay D can be achieved at the power cost of Γ_k. We construct another set of {ŷ_k,w} as

    ŷ_k,w = {[           y_k,w,          w > w_2;         y_k,w_1,          w = w_2;           y_k,w,    w_1 < w < w_2; y_k,w - Δ y_k,w,         w ⩽ w_1, ].

where the quantities {Δ y_k,w, w ⩽ w_2} are all non-negative reals that meet the constraints that ∑_w=1^w_1η_w Δ y_k,w = η_w_2(y_k,w_1-y_k,w_2) and 0 ⩽ŷ_k,w⩽ŷ_k,w+1. Thus, all the variables  ŷ_k,w satisfy Eq. (<ref>) and  ∑_w=1^Wη_wŷ_k,w = ∑_w=1^Wη_wy_k,w. Also, we have  max_w{ŷ_k,w} = max_w{y_k,w}. Thus, by introducing the new set of variables, the objective function in problem (<ref>) does not change. The corresponding power consumption can be calculated as

    Γ̂_k = ∑_w=1^Wη_wP_wŷ_k,w    = Γ_k+η_w_2P_w_2(y_k,w_1-y_k,w_2) - ∑_w=1^w_1η_wP_wΔ y_k,w
        < Γ_k + P_w_2[η_w_2(y_k,w_1-y_k,w_2) - ∑_w=1^w_1η_wΔ y_k,w]                                                                                                        ,
 
where the last inequality holds due to that less power is consumed for a better channel, namely, P_1> P_2 >⋯> P_W. Thus, we obtain that Γ̂_̂k̂<Γ_k since ∑_w=1^w_1η_w Δ y_k,w = η_w_2(y_k,w_1-y_k,w_2). This  means the new constructed variables lead to the same queueing delay while consuming less power. This contradicts the assumption that variables {y_k,w} are the optimal solution.




§ THE PROOF OF LEMMA <REF>



Let us denote L = ∑_k = 0^Kk ∑_m=0^Mθ_mπ_k+1-m. With some transformation, we have  

    L    = θ_0 ∑_k = 0^Kk π_k+1 + θ_1 ∑_k = 0^Kk π_k + ⋯ +θ_M∑_k = 0^Kk π_k+1-M
        = θ_0[Q-(1-π_0)] +θ_1Q +θ_2(Q+1) + ⋯ + θ_M(Q+M-1) 
        = Q(θ_0+⋯θ_M) - θ_0(1-π_0) + ∑_m=1^M-1m θ_m+1
        = Q + θ_0π_0 -θ_0+∑_m=1^M-1m θ_m+1
       =  Q + θ_0π_0 + ς,

where ς = ∑_m=1^M-1m θ_m+1. Thus, the average queue length Q can be expressed as Q = L - θ_0π_0 -  ς. From the Little's Law, we have 

    D = 1/a̅(L - θ_0π_0 -  ς).

In Eq. (<ref>), y_k,w satisfies the inequalities  0 ⩽ y_k,w⩽∑_m=0^Mθ_mπ_k+1-m. Thus, we know max_w{y_k,w}⩽∑_m=0^Mθ_mπ_k+1-m. Recalling that L = ∑_k = 0^Kk ∑_m=0^Mθ_mπ_k+1-m, we have L ⩾∑_k=0^K  k ·max_w{y_k,w}. Thus,

    D ⩾1/a̅(∑_k=0^K  k ·max_w{y_k,w} - θ_0π_0 -  ς),

the "=" holds if and only if max_w{y_k,w} = ∑_m=0^k+1θ_mπ_k+1-m.



§ THE PROOF OF THEOREM <REF>
 

In Theorem <ref>, we have shown that problem (<ref>) is equivalent to problem (<ref>). To minimize the average queueing delay in (<ref>), the weighted sum of max_w{y_k,w} should be minimized while π_0 should be maximized. To minimize ∑_k=1^K k max_w{y_k,w}, the term max_w{y_k,w} should be assigned its maximum for smaller k and its minimum for larger k. Subject to constraint (<ref>.c), we have

    max_w{y_k,w^*}={[ ∑_m=0^Mθ_mπ_k+1-m^*,             k < k^*;;                   0,             k > k^*, ].
 
where k^* is a threshold imposed on the queue length. Once the queue length exceeds k^*, the maximum of variable {y_k,w^*} is zero, and hence all of the variables {y_k,w^*} are equal to zero. Thus, we only consider the situation when k<k^*.

Based on the result in Lemma <ref>, we know that for any k, there exists y_k,1⩽ y_k,2⩽⋯⩽ y_k,W. Thus, y_k,W = max_w{y_k,w^*}, the threshold value T_k introduced in Theorem <ref> meets the constraint that T_k<W. Suppose that there exists a set of optimal variables {y_k,w^*} which violate the assignment described in Eq. (<ref>), we can always find another set of variables {ŷ_k,w} which consume less power while achieving to achieve the same delay.

Suppose that {y_k,w^*} are the optimal variables and satisfy Eq. (<ref>). Accordingly, the steady-state probabilities π_k^* are  given by Eq. (<ref>), and the minimum delay D^* ia achieved at the cost of power Γ_k. For a given queue state k, we reassign π̂_k=π_k^* to a new set of variables {ŷ_k,w} as 

    {[            ŷ_k,w = 0,       1⩽ w < T_k-1,; 0 ⩽ŷ_k,T_k-1⩽ŷ_k,T_k⩽∑_m=0^Mθ_mπ_k+1-m^*,;   ŷ_k,w=∑_m=0^Mθ_mπ_k+1-m^*,    T_k<w⩽ W. ].
 Notice that this set of variables violate the constraints in Eq. (<ref>) since it has more than one term that lies between the maximum and the minimum of {ŷ_k,w}. Since the steady-state probabilities do not change, the minimum queueing delay remains the same. By comparing {ŷ_k,w} with {y_k,w^*}, we get y_k,T_k-1^*<ŷ_k,T_k-1⩽ŷ_k,T_k<y_k,T_k^*. Since π_k^*=π̂_k, from Eq. (<ref>), we have  η_T_k-1(y_k,T_k-1^*-ŷ_k,T_k-1) + η_T_k(y_k,T_k^*-ŷ_k,T_k) = 0.The power consumption can be calculated as

    Γ̂_k 
       = ∑_w=1^Wη_wP_wŷ_k,w
        = Γ_k+η_T_k-1P_T_k-1(ŷ_k,T_k-1-y_k,T_k-1^*)  + η_T_kP_T_k(ŷ_k,T_k-y_k,T_k^*) 
       =Γ_k + P_T_k-1η_T_k(y_k,T_k^*-ŷ_k,T_k) + η_T_kP_T_k(ŷ_k,T_k-y_k,T_k^*) 
       =Γ_k + η_T_k(y_k,T_k^*-ŷ_k,T_k)(P_T_k-1-P_T_k) >Γ_k.
  
The last inequality holds since less power is consumed in a better channel, i.e.,  P_T_k-1>P_T_k and y_k,T_k^*>ŷ_k,T_k. This means that {y_k,w} violating Eq. (<ref>) will cause a higher power consumption. The same conclusion can be obtained when more than two variables violate Eq. (<ref>). In this way, we prove Theorem <ref> by contradiction.




§ THE PROOF OF LEMMA <REF>
 


Given channel state w, we define the delay minimization problem subject to the power constraint from the perspective of buffer occupation and power consumption costs discussed in Section <ref> as follows:

    min_{s[n]} 1/α̅𝔼[(t[n]-s[n]+a[n+1])^+] 
       s.t.  𝔼(P_w s[n]) ⩽ P_aver^',

where t[n] = q[n-1] + a[n] is the queue state after a new datat arrival. The objective is derived  based on the Little's Law and the average symbol 𝔼 means the expectation taken over all the time slots. In the above optimization problem, the scheduling policy is described by the transmission variable {s[n]}. We mainly consider the optimal scheduling policy in the case when the equality (<ref>) holds. 
If the power constraint is sufficiently large, i.e., the inequality in (<ref>) holds, we only need to apply the scheduling policy to transmit packets as long as the queue is not empty, regardless of the channel state. Thus, using the method of Lagrangian multipliers, we only need to minimize the following Lagrangian function

    min_{s[n],β}   L(s[n],β') =    1/α̅𝔼[(t[n]-s[n]+a[n+1])^+] + β'[𝔼(P_w s[n]) - P_aver^'],

where  β' is a Lagrangian multiplier. Equivalently, for each multiplier β', we should solve the following problem

    min_{s[n]} 𝔼[(t[n]-s[n]+a[n+1])^+] + β𝔼(s[n]),

where β is defined as α̅β^'P_w. In the sequel, we show that the optimal solution to Eq. (<ref>) has a threshold structure. We define the expected total cost function in time slot n as

    C_n(t[n],s[n]) = 𝔼[(t[n]-s[n]+a[n+1])^+] + β s[n],

where the first term represents the queue length cost and the second term represents the power cost, respectively. Define V_n(t[n]) as the total cost spent from slot n to slot N if we follow the optimal policy from slot n thereafter, namely,

    V_n(t[n]) =  inf_s[n^'],n^'⩾ n𝔼∑_n'=n^Nγ^n'C_n'(t[n'],X^Ω(t[n'])).

The factor γ in Eq.(<ref>) is the discount factor. Hence, the quantity V_n adds up all the costs spent across the slots n, n+1, ⋯, N and ignores the costs spent previously before slot n.

Let z = t[n]-s[n]. Define G_n as a function of z

    G_n(z) = -β z + 𝔼[(z+a[n+1])^+] + γ𝔼[V_n+1(z+a[n+1])] .

The cost V_n can be rewritten as 

    V_n(t[n]) = β t[n] + min_z G_n(z).

Let I_w = argmin_zG_n(z). Since[See subsection <ref>.] G_n(z) is a convex function of z among all the feasible z, we should choose a solution z=I_w rather than any other s[n]. Otherwise, the transmission action s[n] should always be chosen to make z=t[n]-s[n] approach I_w. To this end, when t[n] is greater than I_w, the transmission action s[n]=1 should be made and otherwise s[n]=0 is selected. Combining these two cases, we show that s[n] is obtained as given by Eq. (<ref>).



 §.§ Function G_n(z) is convex of z for all n

We use the mathematical induction to prove the convexity of G_n(z). Firstly, considering the fact that term  (z+a[N+1])^+ is convex in z for any value of a[n+1],

    G_N(z) = -β z + 𝔼[(z+a[N+1])^+]

is convex in z. Secondly, we assume that G_n+1(z) is convex. Then, we know 

    V_n+1(t[n+1]) = β t[n+1] + min_z G_(n+1)(z)

is convex. Finally, We can derive G_n(z) as

    G_n(z) =    -β z + 𝔼[(z+a[n+1])^+] + γ𝔼[V_n+1(z+a[n+1])]

is convex in z.



§ THE PROOF OF (2) IN THEOREM <REF>
 




As shown in the <ref>, the threshold points are highlighted with the shadow rectangles (in red and gray). We first notice that some of the values on the threshold points are zero due to the threshold structure imposed on the queue length (the vertical direction), like the gray areas. Then, we show that there is at most one nonzero value for these left threshold points in what follows.
	
We use contradiction proof. Suppose that {y_k,w^*} is the optimal solution for a given power constraint P^*, and there are two threshold points (k_1, w_1) and (k_2, w_2 ), whose scheduling probabilities  are nonzero. If k_1/k_2⩾P_w_1/P_w_2, we can reconstruct a new set of {y_k,w^'} by reducing y_k_1,w_1^* and increasing y_k_2,w_2^* based on equation η_w_1P_w_1Δ y^*_k_1,w_1 = η_w_2P_w_2Δ y^*_k_2,w_2, until y_k_1,w_1^* is zero or y_k_2,w_2^* becomes its maximum as given in Eq. (23)
. Let D^' and P^' denote the average delay and power induced under parameters {y_k,w^'}. Based on the expression of the average power in Eq. (19), the difference between P^' and P^* is 

    Δ P = P^' -  P^* =  η_w_2P_w_2Δ y^*_k_2,w_2 - η_w_1P_w_1Δ y^*_k_1,w_1  = 0,

and the difference between D^' and D^*

    Δ D    = D^' -  D^* 
       = 1/a̅^2( k_2η_w_2Δ y^*_k_2,w_2 - k_1 η_w_1Δ y^*_k_1,w_1) 
       = η_w_1Δ y^*_k_1,w_1/a̅^2 P_w_2( k_2P_w_1 - k_1 P_w_2) ⩽ 0.

It means that, with the new constructed parameters, we can obtain a lower average delay which contradicts the optimality of the {y_k,w^*}. Thus, there is at most one threshold point at which y_k,w^* takes value between zero and its maximum. For the case  k_1/k_2 < P_w_1/P_w_2, same conclusion can be obtained if we reduce y_k_2,w_2^* and increase y_k_1,w_1^*. If there are more than two nonzero threshold points, we can eliminate the nonzero values one by one and degrade to the above case.

Based on the relationship between{y_k,w^*} and {f_k,w^*} in Eq. (18), we can obtain the conclusion.





§ A STRAIGHTFORWARD WAY TO EXPLAIN THE DUAL-THRESHOLD-BASED POLICY 
 



For the dual-threshold-based policy, we would like to give a straightforward way to explain why the solution is a threshold policy with the help of the following picture. The average delay has the form of weighted sum with the steady-state probability π_k being the weight, i.e., D = 1/a̅∑_k=0^Kk π_k. In order to minimize the average delay, the limit power resource should be allocated to decrease the π_k which has greater k. As shown in <ref>, the limit power can only afford to transmit for some greater k. However, transmitting one packet over a bad channel consumes much more power than over a better channel. Thus, the power consumed over these bad channels for greater k can be moved to transmit for relative lower k but over better channels. In <ref>, we remove the power from the orange area to the blue circled area. The black arrows show the order of priority of the move process. Thus, the optimal policy shows up with the dual-threshold-based policy.























































1.15
IEEEtran






























