{'fraction_non_alphanumeric': 0.04049975165246628, 'fraction_numerical': 0.007565047950177664, 'mean_word_length': 4.277016129032258, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Resource Allocation for Cost Minimization in Limited Feedback MU-MIMO Systems with Delay Guarantee

In this paper, we design a resource allocation framework for the delay-sensitive Multi-User MIMO (MU-MIMO) broadcast system with limited feedback. Considering the scarcity and interrelation of the transmit power and feedback bandwidth, it is imperative to optimize the two resources in a joint and efficient manner while meeting the delay-QoS requirement. Based on the effective bandwidth theory, we first obtain a closed-form expression of average violation probability with respect to a given delay requirement as a function of transmit power and codebook size of feedback channel. By minimizing the total resource cost, we derive an optimal joint resource allocation scheme, which can flexibly adjust the transmit power and feedback bandwidth according to the characteristics of the system. Moreover, through asymptotic analysis, some simple resource allocation schemes are presented. Finally, the theoretical claims are validated by numerical results.


I. INTRODUCTION
Despite great progress in wireless communications during the past several years, it is still a challenging task to support delay-sensitive wireless services over time-varying fading channels given the scarcity of resources, such as wireless spectrum and energy efficiency. Under these circumstances, efficient resource allocation with delay guarantee (due to its wide applications in video broadcasting or tele-conferencing) becomes a hot topic in wireless research community [1] - [3]. In addition, advanced multiple antennas techniques have became the basic assumption in many international communications standards, e.g. IEEE 802.11ac and LTE-A, in order to support next generation multimedia communications. In particular, Multi-User MIMO (MU-MIMO) is a key technology that has been adopted by IEEE 802.11ac and LTE-A due to its capability to exploit the extra antenna at the base-station to serve multiple users concurrently.
Resource allocation in MU-MIMO systems receives considerable attentions due to its potential of improving spectral efficiency remarkably by exploiting the unique spatial degree of freedom, as seen in [4] - [6] and references therein. As suggested by previous study [7], the performance of MU-MIMO downlink is closely related to the amount of channel state information (CSI) at the base station (BS). For example, if the BS has no CSI, it can only work with a fixed transmission scheme, which is equivalent to the traditional point-to-point MIMO system [8].
If full CSI is available at the BS, dirty paper coding can be used to approach the capacity of MU-MIMO downlink [9]. Between the two extreme cases, if the BS has partial CSI, some effective preprocess techniques, such as zero-forcing beamforming (ZFBF) [10] [11], can be used to partially cancel the inter-user interference. Thus, the amount of CSI greatly impacts the performance of the MU-MIMO system. Furthermore, the performance of the MU-MIMO system is also affected by other resources, such as transmit power [12], since both the desired signal quality and the inter-user interference are the functions of the transmit power. Note that in the MU-MIMO system, power and feedback resources are interrelated for a given QoS constraint, e.g. delay requirement. For a MU-MIMO system with delay-QoS guarantee, the critical issue of the design of such joint power and feedback resource allocation is to reveal the relationship between the delay requirement and the involved resources. Based on the availability of CSI at the BS, a variety of models have been built to characterize the relationship between the delay requirement and the involved resources, and several adaptive resource allocation schemes have been derived [13], such as equivalent rate constraint [14] [15], Lyapunov drift [16] [17] and Markov decision process (MDP) [18] [19] schemes.
All the aforementioned delay driven resource allocation schemes consider average delay as the QoS requirement. In fact, for some delay sensitive services, e.g. video and audio services, maximum delay is of concern. Based on the large deviation principle, effective bandwidth theory can be used to establish the relationship between maximum delay and minimum serve rate for a given violation probability [20] [21]. Hence [22] studied the power allocation with maximum delay constraint in wireless systems according to the effective bandwidth theory. Nearly all previous works on resource allocation based on the effective bandwidth theory assume full CSI at the BS. However, as mentioned earlier, the BS only has partial CSI by consuming the feedback resource. To the best of our knowledge, feedback resource allocation in the delay-sensitive MU-MIMO downlink has not been well addressed.
In this paper, we focus on joint power and feedback resource allocation with maximum delay guarantee in the MU-MIMO downlink employing with ZFBF. Different from previous works, we consider limited CSI feedback with quantization codebooks. The main contribution of this paper lies in that we reveal the relation between the violation probability with respect to a maximum delay requirement, transmit power and feedback bandwidth based on the effective bandwidth theory, and then derive an optimal joint power and feedback resource allocation scheme by minimizing the resource cost function while satisfying delay constraint. The main contributions of this paper can be summarized as follows: 1) We reveal the relation between the violation probability with respect to a maximum delay requirement, transmit power and feedback bandwidth based on the effective bandwidth theory.
2) We design a framework of joint power and feedback resource allocation in the delaysensitive downlink MU-MIMO with limited feedback, and propose an optimal joint resource allocation schemes.
3) We formulate a resource cost function as the sum of power cost and feedback cost. By adjusting the relative cost factor according to the characteristics of the considered system, we can obtain the corresponding resource allocation results. 4) Through asymptotic analysis, we obtain two simple resource allocation schemes in the interference-limited and noise-limited scenarios respectively.
The rest of this paper is organized as follows. In Section II, the considered system model is briefly introduced, and then the adopted transmission protocol and effective bandwidth theory are discussed. We propose a joint transmit power and feedback bandwidth allocation scheme with delay-QoS provisioning in Section III. In Section IV, we derive two simple resource allocation schemes via asymptotic analysis. Simulation results are presented in Section V, and we conclude the whole paper in Section VI.
Notation: We use bold upper (lower) letters to denote matrices (column vectors), (·) H to denote conjugate transpose, (·) T to denote matrix transpose, x 2 to denote the l 2 norm of vector x, |y| to denote the absolute value of y and G ′ (x) to denote the differential of function G(x) with respect to x. The acronym i.i.d. means "independent and identically distributed", pdf means "probability density function" and cdf means "cumulative distribution function".

II. SYSTEM MODEL
Consider a homogeneous MU-MIMO downlink, which includes a base station (BS) with N t antennas, and N t single antenna mobile users (MUs), as shown in Fig.1. For tractability, it is assumed that the downlink channels h k , k = 1, · · · , N t from the BS to MUs are i.i.d. complex Gaussian random vectors with zero mean and unit variance. All the channels are assumed to remain unchanged during one time slot and fade independently slot by slot. At the beginning of each time slot, MUs convey the corresponding CSI to the BS based on quantization codebooks.
All the codebooks are designed in advance and stored at the BS and MUs. Assuming the codebook of size 2 B at the kth MU is H k = {ĥ k,1 , · · · ,ĥ k,2 B }, k = 1, · · · , N t , the optimal quantization codeword selection criterion can be expressed as whereh k = h k h k is the channel direction vector. Specifically, the optimal codeword index i is conveyed by the kth MU andĥ k,i is recovered at the BS as the instantaneous CSI of the kth

MU.
Based on the feedback information from the MUs, the BS designs the optimal transmit beams w k , k = 1, · · · , N t by making use of the ZFBF design method [10]. For the kth MU, the BS first constructs its complementary channel matrix whereĥ k−1 is the (k − 1)th MU's optimal channel quantization codeword. Taking singular value decomposition (SVD) toĤ k , if V ⊥ k is the matrix composed of the right singular vectors with respect to zero singular values, then w k is a normalized vector spanned by the space of V ⊥ k , so we haveĥ It is assumed that x k is the desired normalized signal of the kth MU, then its receive signal can be expressed as where P is the total transmit power of the BS, which is equally allocated to the N t MUs. n k is the additive Gaussian white noise with zero mean and variance σ n for all MUs. Hence, the ratio of the received signal to interference and noise (SINR) for the kth MU can be expressed as where γ = P Ntσ 2 n is the average transmit SNR at the BS and P/N t Although ZFBF is adopted, there are some residual interference, since the BS only has the quantized CSIĥ k , k = 1, · · · , N t . The beam w u is designed according to the criterion h H k w u = 0, so we have h H k w u = 0, resulting in the residual interference. Clearly, the more the feedback amount, the less the residual interference. If the BS has full CSI, the interference can be canceled completely due toĥ k =h k . It is worth pointing out that the SINRs for all MUs have the similar expression in virtue of the homogeneous characteristics.

A. Transmission Protocol
The data from high layer is organized in packet at the data link layer. Each packet has a fixed number of bits N b , including packet header, payload and cycle redundant check (CRC).
The arrived data packets for each MU enter its unique buffer (with infinite capacity) and wait for transmission at the physical layer. Within each transmission duration T b , the packets at the front of the buffers are adaptively modulated respectively according to the respective channel quality for the corresponding MU, namely SINR, and then form N t independent data frames.
Specifically, the whole SINR range is partitioned into N regions by N + 1 SINR thresholds Ω n , n = 0, · · · , N. For the kth MU, if the SINR of the current frame ρ k satisfies the condition that Ω n ≤ ρ k < Ω n+1 , then the nth modulation format is selected. The determination of SINR threshold depends on the relationship between packet error rate (PER) and modulation mode.
Through theoretic analysis and numerical simulation, the expression of PER in the form of modulation mode is given by [24] P e,n (ρ) ≈ where γ pn is the cutoff SINR, below which the PER is unacceptable. Notably, a n , g n and γ pn are the parameters dependent on the modulation mode n. For packet length N b = 1080, these parameters for various modulation modes can be found in Table I. It is assumed that the objective PER is fixed as P obj , a feasible method of determining the N + 1 SNR thresholds is given by Due to the delay constraint of real-time services, the packet will be discarded if its waiting time exceeds the upper bound on delay D max .

B. Effective Bandwidth
Since the pioneer work of Kelly [21], the concept of effective bandwidth is widely used in wireless communications together with queueing theory. Effective bandwidth is defined as the characteristics of the source in bounds, limits and approximations for various models of multiplexing under QoS constraints. Specifically, in this paper, effective bandwidth is defined as the minimum serve rate required by a stationary and ergodic arrival process while fulfilling the constraint of maximum waiting delay.
As mentioned earlier, the packet will be discarded if the waiting time is greater than D max .
Thus, according to the large deviation principle (LDP), the probability of dropping packet caused by delay, so called violation probability, can be written as [23] P where C is the serve rate, δ(C) = max(s ≥ 0; α(s) ≤ C) is the QoS exponent, the increasing function α(s) is the so-called effective bandwidth of the traffic source and s denotes the space variable.ρ is the probability that the buffer is nonempty. Let S n be the indicator of whether the nth packets is in service (S n ∈ 0, 1) and M is the total number of packet, then the approximate nonempty probabilityρ can be reckoned aŝ Given the maximum delay constraint D max and the tolerable upper bound on violation probability ε =ρ exp (−δ(C)CD max ), we could determine the required minimum serve rate C min . For the Poisson arrival process, α(s) can be computed as [21] α where F (x) is the cumulative distribution function (cdf) of the packet size. Since all packets have the same size, F (x) is a step function at x = N b . Thereby, we have By combining (6) and (9), we can obtain the property of the required minimum served rate as follows.
Theorem 1: When the average arrival rate λ is large enough, the required minimum served rate can be approximately expressed as . In other words, C min (λ, D max ) increases approximately linearly with λ.
Proof : Please refer to Appendix I for the proof.
Corollary 1: For high arrival rate, the gap ∆ C between C λ,min (D max,1 ) and C min (λ, D max,2 ) is a constant regardless of λ, where D max,1 and D max,2 are two arbitrary maximum delay constraints.
Because α(s) is an increasing function of s, δ(C) = max(s ≥ 0; α(s) ≤ C) has a unique solution in the form of C. In this context, we could derive the required minimum serve rate C min (λ, D max ) as a function of the QoS requirement D max and ε for an arbitrary arrival rate λ by solving the equations (6) and (9). Similarly, given C and D max , we can also obtain the corresponding ε easily.

III. JOINT RESOURCE ALLOCATION WITH DELAY GUARANTEE
In this section, we focus on joint transmit power and feedback bandwidth allocation while satisfying the delay constraint in a MU-MIMO downlink. Note that in this paper transmit power is the same for all MUs and only the total power is regulated, since equal power allocation is optimal in the statistical sense and can avoid a large amount of information feedback in a multiuser system. Considering the scarcity of the two resources in practical systems, we expect to minimize the total resource utilization. Hence, we set the optimization objective as minimizing the following resource cost function: where ϕ (cost per watt) and ψ (cost per bit) are the cost factors of transmit power P and feedback amount N t B, respectively. The cost factors depends on the characteristics of the considered system. For example, in a power-limited system, more feedback amount should be used to decrease the consumption of transmit power. Otherwise, if the system is feedback limited, it is better to use more transmit power. By changing the relative cost factor ξ = ϕ ψ , we can character the different systems. As a simple example, ξ >> 1 denotes the power-limited system, while ξ << 1 denotes the feedback-limited system. Since the two resources are independent of each other, we model the total cost as the linear sum of the two resource costs.
As analyzed earlier, given data arrival rate, the violate probability with respect to a maximum delay constraint is a function of the serve rate. Thus, based on adaptive modulation, the average violation probability for the kth MU with transmit power P and codebook size B can be computed asε where F ρ k (x) is the cumulative distribution function (cdf) of SINR ρ k , and P r (C n ) = F ρ k (Ω n+1 )− F ρ k (Ω n ) is the probability that the nth serve rate or modulation mode is selected. Assuming the downlink bandwidth is W , then we have C n = nW/N b . For the nth modulation mode or given the serve rate C n , the nonempty probability ρ(C n ) and the QoS exponent δ(C n ) are fixed based on (6) and (9), so the violation probability P d (C n ) is a constant. Following [10] [11], the cdf of ρ k based on limited feedback ZFBF can be expressed as where θ = 2 − B N t −1 . Substituting (12) into (11), we havē Therefore, cost-minimizing joint resource allocation with delay guarantee is equivalent to the following optimization problem where ε 0 , P 0 and B 0 are the constraints on violation probability, transmit power and feedback bandwidth, respectively. Since B is an integer variable, J 1 is a mixed integer programming problem, it is difficult to obtain a closed-form expression for the optimal P and B. Intuitively, the optimal algorithm is to compute the transmit power by lettingε k (P, B) = ε 0 for a given B. Then, search the optimal resource combination with the minimum resource cost by scaling B from 1 to B 0 , namely the exhaustive search algorithm. In fact, J 1 can be transformed as a general optimization problem if B is relaxed to a nonnegative real variable, so that it can be solved by some optimization softwares, such as the Lingo. Assuming P † and B † are the optimal solutions of the relaxed optimization problem, where B † may not be an integer. Under this condition, we take B c = ⌈B † ⌉ and B f = ⌊B † ⌋ as the two candidates, where ⌈B † ⌉ and ⌊B † ⌋ mean the smallest integer not less than B † and the largest integer not greater than B † , respectively. Given B c , we could get the optimal transmit power P c by lettingε k (P c , B c ) = ε 0 and the corresponding resource cost function η(P c , B c ). Similarly, we also could obtain P f and Thus, we proposed a joint resource allocation scheme based on the above idea. First, we derive the optimal feedback amount and transmit power based on the relaxed optimization problem by using the Lingo. Then, we round the feedback amount to two nearest integers, and compute the maximum transmit power while fulfilling delay constraint. Finally, by comparing the corresponding resource cost, the resource combination with the smallest cost is selected. The joint resource allocation scheme can be described as follows 1) Initialization: given N t , N, P 0 , B 0 , ϕ and ψ.
2) Relax B to a nonnegative real number and derive P † and B † by the Lingo.
3) Let B c = ⌈B † ⌉ and B f = ⌊B † ⌋. Compute P c satisfyingε k (P c , B c ) = ε 0 and P f satisfyinḡ Interestingly, it is found that although the proposed algorithm is derived based on the relaxed optimization problem, it is also optimal together with the exhaustive search algorithm. The complete proof is given by Appendix II.

IV. ASYMPTOTICAL ANALYSIS
In this section, we analyze the asymptotical characteristics of violation probability in some special cases. Based on the insight from the analysis, we can then derive some simple resource allocation schemes that are optimal asymptotically.

A. Interference-Limited Case
If the variance of noise is quite small, e.g. in the noise-free scenario, the noise can be negligible with respect to the inter-user interference, namely the interference-limited case. Under such a condition, the received SINR of the kth MU can be approximated as According to the analysis in previous section, we have the cdf of ρ k in this case as Thereby, the joint resource allocation can be described as the following optimization problem It is found that the first constraint is independent of P , this is because the effects of P on the desired signal and interference are canceled out each other when the noise is ignored. From the perspective of the optimization, it seems that P = 0 is the optimal solution to J 2 . However, in practical systems, a minimum transmit power is required to maintain the communications. In other words, P is set as the required minimum transmit power. For the optimal codebook size, we and then let B = ⌈B † ⌉ because of its integer constraint.

B. Noise-Limited Case
If the noise is quite large, the inter-user interference can be negligible compared with the noise, namely the noise-limited case. In this scenario, the received SINR of the kth MU can be approximated as Similarly, we have the cdf of ρ k in this case as Hence, we could formulate the joint resource allocation as the following optimization problem In this case, B = 0 is the optimal solution to J 3 , which is consistent with our intuition.
This is because when the noise is dominant, CSI feedback hardly affects the SINR. Furthermore, the optimal P can be obtained by solving the function

V. PERFORMANCE ANALYSIS AND SIMULATION RESULTS
To examine the effectiveness of the proposed cost minimizing joint transmit power and feedback bandwidth allocation scheme with delay guarantee, we present several numerical results in different scenarios. For all scenarios, we set N t = 4, N = 8, W = 1MHz, σ 2 n = 1, P obj = 10 −4 and N b = 1080 for convenience. Noticeably, considering resource limitation, we set P 0 = 40dB and B 0 = 10. The codebooks are designed based on vector quantization (VQ) method [25] [26]. Fig.3 show the required minimum served rates C min (λ, D max ) for the scenarios with high and low arrival rates respectively when ε 0 = 0.01. Depending on the arrival rates, we can see that there are different trends for the served rates in these two scenarios. For high arrival rate λ, minimum serve rate increases approximately linearly, which is well consistent with Theorem 1. However, for low arrival rate, the maximum delay constraint D max has a great impact on the slope of variation of the required serve rate, where the slope is inversely proportional to D max .

Fig.2 and
As seen in Fig.3, when D max is greater than 8ms, the slope is approaching zero asymptotically.
In addition, the gap of the required serve rates ∆ C = C min (D max,1 ) − C min (D max,2 ) is not a linear function of ∆ D = D max,1 − D max,2 . For example, the gap of the required serve rates due to the delay relaxation from D max = 8ms to 4ms is larger than the delay relaxation from D max = 12ms to 8ms.
In Tab.II, we compare the joint resource allocation results based on the proposed algorithm and exhaustive search algorithm. For ease of comparison, we fix arrival rate as λ = 300 packets/s and the upper bound on average violation probability ε 0 = 0.01. In addition, we use ξ = ψ/ϕ to denote the relative cost factor. For a strict delay constraint, such as D max = 2ms, with the increase of the relative cost factor, the optimal feedback bandwidth decreases accordingly while the required transmit power increases, this is because as the cost factor of feedback bandwidth increases, higher transmit power has a lower total cost while satisfying the delay constraint.
Therefore, we could flexibly adjust the resource combination by changing the relative cost factor according to the characteristics of the considered system. Moreover, it is found that the proposed algorithm gets the same results as exhaustive search algorith, which reconfirms our theoretical claim. For the case with loose constraint, e.g. D max = 8ms, the above observations also hold true.
Comparing with the allocation results with the same ξ, the two cases use the same feedback bandwidth, but the case with D max = 2ms has a higher transmit power, since it is relatively cheaper to add more power than to reduce feedback bandwidth.

VI. CONCLUSION
A major contribution of this paper is to provide a framework of joint transmit power and feedback bandwidth allocation with delay guarantee so that the two scarce resources can be utilized in a more efficient manner according to the characteristics of a multi-user MIMO broadcast system. First, according to the effective bandwidth theory, we established the intrinsic relationship between minimum required serve rate and maximum delay constraint. Then, based on adaptive modulation, we formulated the average violation probability with respect to maximum delay in terms of transmit power and codebook size. Eventually, by minimizing the total resource cost while satisfying the delay constraint, an optimal joint resource allocation scheme was derived accordingly.
Rearranging (21), it is obtained that where a(λ, D max ) = ln ε−lnρ λDmax . By solving the function (22), we have Therefore, the required minimum served rate can be approximately expressed as where (24) follows from the fact that If B † is an integer, then (P † , B † ) is also the optimal solution of J 1 definitely. Otherwise, we take B c = ⌈B † ⌉ and B f = ⌊B † ⌋ as the two candidates, and derive the corresponding optimal transmit power P c and P f . Since the violation probability is the monotonously decreasing function of P and B, we have P c < P f . In what follows, we prove (P c , B c ) is the optimal solution of J 1 if is the optimal solution. Prior to the proof, we first present the following lemma: Lemma 1: Given the requirement of the violation probability, the reduction of transmit power △P becomes smaller gradually by adding the same feedback bandwidth △B as feedback bandwidth B increases.
Lemma 1 holds true since the violation probability is a power function of feedback bandwidth.
If η(P c , B c ) < η(P f , B f ), then the cost of the added 1bit feedback bandwidth is less than that of the reduced transmit power. Assuming (P f −1 , B f −1 ) is the feasible solution of J 1 , due to P f −1 − P f > P f − P c according to Lemma 1, we have η(P f −1 , B f −1 ) > η(P f , B f ). Thus, it is obtained that η(P i , B i ) > η(P f , B f ) > η(P c , B c ) for all i < f . We consider the case of i > c.
Assuming η(P i , B i ) < η(P c , B c ) and (P ′ , B ′ ) is a feasible solution of the relaxed problem, where According to Lemma 1, we have P † − P ′ > P c − P i because of B † < B c . If η(P i , B i ) < η(P c , B c ), we have η(P ′ , B ′ ) < η(P † , B † ). However, (P † , B † ) is the optimal solution of the relaxed problem, it is impossible to find the (P ′ , B ′ ) such that η(P ′ , B ′ ) < η(P † , B † ).
In other words, η(P i , B i ) < η(P c , B c ) for any i > c can not hold true. Hence, (P c , B c ) is the optimal solution of J 1 . Similarly, if η(P c , B c ) > η(P f , B f ), (P f , B f ) is optimal.