October 2, 2006, Torremolinos, Malaga, Spain. October 2, 2006, Torremolinos, Malaga, Spain.
Closed Form Solution for QoS--Constrained Information--Theoretic Sum Capacity of Reverse Link CDMA Systems

Closed Form Solution for QoS-Constrained Information-Theoretic Sum Capacity of Reverse Link CDMA Systems

Arash Abadpour



Attahiru Sule Alfa



Anthony C.K. Soong


Abstract

The information-theoretic maximum system capacity in a CDMA network, which guarantees fairness to mobile stations, can be achieved by optimally allocating transmit powers to the mobile stations while imposing individual QoS constraints. Even though this optimization is carried out in a multi-dimensional space we show that the optimal solution can be reduced to a search in a one-dimensional space. In this paper we first show that the previous results can be obtained by a simpler and more intuitive approach. Also, we show that the optimal solution is actually bang-bang. In addition, we show that the candidate solutions can be determined in a closed form. This considerably reduces the computational effort. Because rather than carrying out numerical search on a set of intervals, only a few explicitly determined points should now be examined.

1  Introduction

In a recent paper Oh and Soong [6,7] developed a method for obtaining reverse link capacity of a CDMA system under some imposed quality of service constraints. In the current paper we improve the results by significantly reducing the computational effort required.
Capacity of a single point-to-point communication link is well approximated by the well-known Shannon theorem as C=Blog2(1+S/N) [3] (Also, see [5]). Here, B is the bandwidth and S/N is the signal to noise ratio of the communication link. Assume that there are M mobile stations whose reverse link gains are g1,¼, gM, satisfying g1 > ¼ > gM. Define the i-th mobile station's transmit power as pi, for which we have 0 £ pi £ pmax. With a background noise of I, the signal to noise ratio for the i-th station becomes,
æ
è 		S
N
 ö
ø
i 
 = pigi
I+ M
å
j=1,j ¹ i 
 pjgj
 .
(1)
Substituting (1) into the Shannon formula we have,
Ci=log2
I+ M
å
j=1 
 pjgj
I+ M
å
j=1,j ¹ i 
 pjgj
 ,
(2)
which results in the aggregate capacity of,
C(
®
p
 
 )= M
å
i=1 
 Ci=log2
æ
è 		I+ M
å
j=1 
 pjgj ö
ø 		M
 
M
Õ
i=1 
 æ
è 		I+ M
å
j=1,j ¹ i 
 pjgj ö
ø
,
(3)
where, [(p)\vec]=(p1,¼,pM).
There are some conditions which should be added to the problem. First, the total power reaching the base station should be smaller than a fixed margin (åi=1Mpigi £ Pmax). Also, each station should have a minimum threshold quality of service ("i, (S/N)i ³ g). The above formulations lead to the optimization problem stated as finding [(p)\vec]=(p1,¼,pM), which,

max
[(p)\vec] 
æ
è 		I+ M
å
j=1 
 pjgj ö
ø 		M
 
M
Õ
i=1 
 æ
è 		I+ M
å
j=1,j ¹ i 
 pjgj ö
ø
,
(4)

"i, 0 £ pi £ pmax,
(5)

"i, pigi
I+ M
å
j=1,j ¹ i 
 pjgj
 ³ g,
(6)

M
å
i=1 
 pigi £ Pmax.
(7)
Analysis of this problem is given in [6,7]. There, the authors derive useful results and limit the search-space from RM to M one-dimensional intervals in R. The algorithm given in [6,7] uses numerical methods at its core. In this way, a number of intervals, of order M, should be numerically searched for the best solution. In this paper, we enhance the results by limiting the search to order of M points in RM which are given in closed form.

2  Proposed Method

In this section, the classical problem as introduced in [6,7] is analyzed. First we carry out a few linear transformations to simplify problem formulation in Section 2.1. Then, we investigate the behavior of the problem in specific hyperplanes and give an important theorem in Section 2.2. In Section 2.3, we localize the solution to a smaller search space than what was developed before and this gives practical inequalities. Then, in Section 2.4 we rigorously analyze the problem and prove another important theorem which is used in Section 2.5 to propose a new algorithm for accurately finding the solution to the problem.

2.1  Linear Transformation of the Search-Space

The first contribution of this paper is to use few transformations to give a simpler representation of the problem. This will also lead to a simpler solution. First, we rewrite (6) as,
"i, pigi
I+ M
å
j=1 
 pjgj
 ³ j.
(8)
Here, j is a fixed parameter defined as j = g/(g+1). Clearly, 0 < j < 1. Now, substituting,
xi= pigi
I
 ,
(9)
into (4) and finding the reciprocal we have to minimize,
F(
®
x
 
 )=
M
Õ
i=1 
 æ
è 		1+ M
å
j=1 
 xj-xi ö
ø
æ
è 		1+ M
å
j=1 
 xj ö
ø 		M
 
 ,
(10)
where [(x)\vec]=(x1,¼,xM). Now, we find the new representations of the constraints using the transformation shown in (9). Substituting (9) into (5) gives,
"i, 0 £ xi £ li, li= pmax
I
 gi.
(11)
Note that as gis are sorted in a descending fashion, so are lis. Here, to comply with the history of the problem, we have assumed that pmax is fixed for all stations. Though, we have never used it, except for proving that lis are sorted. Obviously, we may assume that the stations are sorted in the way that pmax,igis are ordered in a descending fashion, not gis. Hence, the solution given here is more general than the previous discussion given in [6,7]. Here, pmax,i is the maximum transmit power of the i-th station. Substituting (9) into (8) gives,
"i, xi
1+ M
å
j=1 
 xj
 ³ j.
(12)
Finally, (7) becomes,
M
å
i=1 
 xi £ Xmax, Xmax= Pmax
I
 .
(13)

2.2  Working on a Specific Hyper-Plane

The second contribution of this paper is to investigate the behavior of the problem in specific hyperplanes. This investigation leads to a very important theorem about the problem at the end of this section. Hence, we investigate the problem in the hyperplane,
M
å
i=1 
 xi=T,
(14)
for different values of T. In this hyperplane, the problem reduces to finding the minimum of F([(x)\vec]) = (1+T)-MFT([(x)\vec]), where,
FT(
®
x
 
 )= M
Õ
i=1 
 æ
è 		1+T-xi ö
ø 		.
(15)
While T is fixed, the problem which should be solved is to minimize FT([(x)\vec]). On the other hand, the problem can be rephrased as finding T for which minimum value of FT([(x)\vec]) is the smallest possible.
In the hyperplane indicated in (14), the constraints have simpler formulations. Inequality (13) simply changes to a limitation for T as,
T £ Xmax.
(16)
Also, (12) changes to "i, xi ³ j(1+T), which, in combination with (11) gives,
"i, j(1+T) £ xi £ li.
(17)
Now, the question is to minimize (15) given that [(x)\vec] lies on the hyperplane defined as (14). The vector [(x)\vec] should also satisfy (17). Also, T should not become larger than Xmax. It is clear that if the [(x)\vec] satisfying (14) is the minimum of (10) then it is the minimum of (15), but not vice versa. Now, we will develop further tools to introduce the essential theorem.
Assume that [(x)\vec] is the minimum of (15). Also, assume two distinct values of i and j. We will find an important condition about xi and xj. Let us rewrite (15) in terms of xi and xj. We have, FT([(x)\vec])=(1+T-xi)(1+T-xj)Õk=1,k ¹ i,jM(1+T-xk). Here, the last term (which contains M-2 factors) depends neither on xi nor on xj. Hence, we have to maximize the product of the first and the second terms. As the summation of these two terms is constant, algebraic operations prove that they should be as much as possible far apart. Using this, we state the essential theorem.
Essential Theorem: In the solution to the problem, there can be no two xi and xjs that can increase their distance. We call them an extending joint if they can do so and the situation is called an extension. In other words, the inequalities for xis (see (17)) should always stop xis from increasing the distance among themselves.
We will use a graphical visualization to explain this rule. Before that, remember a rule of thumb: F([(x)\vec]) is independent of permutations of xis. Also, rather than the bounds for T in (16), the only conditions are those put on xis independently (see (17)). Though, in these constraints, the minimum possible value of all xis are identical, while maximum possible values are lis which are sorted in a descending scheme. Hence, it is reasonable to show the range of xi as,
xi: é
ë 		j(1+T)¼¼¼¬×®¼¼¼li ù
û 		,
(18)
where, × shows approximate place of xi and arrows indicate possible movements. Here, we give names for three situations of xi. xi is called to be at the beginning, at the middle, or at the end if xi=j(1+T), j(1+T) < xi < li, or xi=li, respectively. Now, to show the power of the essential theorem and the proposed visual notation, we prove the first lemma in [7]. The Lemma says that in the optimum solution there is at most one xi at the middle. We will tighten this lemma later by showing that actually there is no xi in the middle, i.e. there is no in-between point. Let us assume otherwise, so that there are xi and xj, both at the middle and i < j. There are two possibilities, xi ³ xj or xi < xj. The first case leads to,
xi: é
ë 		j(1+T)¼¼¼¼¼×®¼¼¼¼li ù
û
xj: é
ë 		j(1+T)¼¼¼¬×¼¼¼¼¼lj ù
û
,
(19)
which is clearly an extension. The later case is similar,
xi: é
ë 		j(1+T)¼¼¬×¼¼¼¼¼¼¼¼li ù
û
xj: é
ë 		j(1+T)¼¼¼¼×®¼¼¼¼¼lj ù
û
.
(20)
We compare this visually intuitive and simple proof with the one given in [6,7].
The second lemma in [7] states that in the optimum solution, if there is one xi at the middle, all xjs for j > i will be at the beginning. Again assume two distinctive xi and xjs, where i < j and xi is at the middle. Now, if xj is the end, there are two possibilities, namely xi ³ lj or xi < lj. The first one is shown as,
xi: é
ë 		j(1+T)¼¼¼¼¼¼¼¼×®¼li ù
û
xj: é
ë 		j(1+T)¼¼¼¼¼¬×lj ù
û
,
(21)
which is clearly extendable. The second condition is extendable, though a bit harder to realize,
xi: é
ë 		j(1+T)¼¼¼×¼¼¼¼¼¼¼li ù
û
xj: é
ë 		j(1+T)¼¼¼¼¼×lj ù
û
.
(22)
Replacing xi and xj gives,
xi: é
ë 		j(1+T)¼¼¼¼¼×®¼¼¼¼li ù
û
xj: é
ë 		j(1+T)¼¼¬×¼¼lj ù
û
,
(23)
where the extension is trivial.
Lemma 3 in [7] is talking about xis above the one at the middle. The claim is that if xk is at the middle and for m < k, xm is at the beginning, then for m < i < k, xi can not be at the end. Using the above rules, the result is that xi should always be at the beginning. The situation which this lemma refers to is,
xm: é
ë 		j(1+T)×¼¼¼¼¼¼¼¼¼¼¼¼lm ù
û
xi: é
ë 		j(1+T)¼¼¼¼¼¼¼¼¼×li ù
û
xk: é
ë 		j(1+T)¼¼¼×¼¼¼¼lk ù
û 		,
(24)
which changes to the extendable case of,
xm: é
ë 		j(1+T)¼¼¼¼¼¼¼¼¼×®¼¼lm ù
û
xi: é
ë 		j(1+T)×¼¼¼¼¼¼¼¼¼li ù
û
xk: é
ë 		j(1+T)¼¼¬×¼¼¼¼lk ù
û 		.
(25)
Now, like the proposition 1 given in [7] we concludes if there is a solution to the problem then it is as,
®
x
 
 = æ
è 		l1,¼,lk-1,xk,j(1+T),¼,j(1+T) ö
ø 		.
(26)

2.3  Finding Necessary and Sufficient Inequalities for xk

Equation (26) gives the structure of the optimum solution to the problem. In this section we reduce the size of the search space by finding both necessary and sufficient bounds for both k and xk. The problem now is to find k and xk for which the solution given in (26) is optimum. Derivation shows that T=xk+L+(M-k)j(1+T), where L=åi=1k-1li. Hence,
1+T= xk+L+1
1-(M-k)j
 .
(27)
Algebraic operations on the constraints of the problem show that all the conditions are abbreviated in two bounds on xk,
xk £ min
 ì
í
î 		lk,(Xmax+1) é
ë 		1-(M-k)j ù
û 		-L-1,
(28)
lM 1-(M-k)j
j
 -L-1 ü
ý
þ 		,

xk ³ j(L+1)
1-(M-k+1)j
 ,
(29)
for those values of k satisfying,
M- 1
j
 +1 < k < 1
j
 - 1
lM
 +1.
(30)

2.4  Accurate Spotting of xk

It was proved in Section 2.2 that the solution to the problem (given in (10)) with the constraints shown in (11), (12), and (13) is like (26). Now, the question is to find appropriate values of k and xk. Here, we assume that we have selected a value of k and will give practical choices for xk. In this situation we know from what was described in Section 2.3 that it is both necessary and sufficient for xk to satisfy (28) and (29). In this section we prove that F([(x)\vec]) has a very useful behavior in terms of xk (when other xis are selected as in (26)). Actually, we show how to prove that the minimum value of F([(x)\vec]) happens on a boundary (at a margin). This directly leads to the two choices given in (28) and (29) for xk. In this way, the problem reduces to checking two values for xk for any value of k (also limited by (30)). Hence, the solution is actually a bang-bang one, compared to the semi-bang-bang solution developed in [6,7]. The importance of this non-iterative method over the numerical one used in previous works is clear. Here we have the exact solution to the problem in the proposed method while the available approach is only capable of giving the solution up to some precision. And also, the proposed method is essentially faster.
Substituting for T in (10) as given in (14) we have,
F(xk)=C
k
Õ
i=1 
 (xk+bi)
(xk+b)k
 ,
(31)
where C=(M-k)j(1-j)M-k,
bi=L+1- æ
è 		1-(M-k)j ö
ø 		li,    i=1,¼k-1 L+1
(M-k)j
 ,                           i=k,
(32)
and b = L+1. Note that with these definitions we have 0 < b1 < b2 < ¼ < bk-1 < b < bk and åi=1kbi-kb > 0. Figure 1 shows a sample shape of F(xk)/C when k=3 with values of bi and b defined as,
b1=1.0082, b2=1.6728, b3=5.7966,b = 2.2310.
(33)
Note that in this example, it is clear that in any interval in the positive side, the minimum value happens at the boundaries. A lengthy, and yet straight-forward, analysis of (31) proves that this is actually always the case for the bi and b defined here. We do not go through the mathematics of the proof because of space shortage.
rep2_fig1.jpg
Figure 1: Sample shape of F(xk)/C defined in (31) with values of parameters given in (33).

2.5  Proposed Algorithm

2.6  Computational Cost

Analysis of the proposed algorithm shows that its computational cost equals 8M2+20M+10 flops. As an example, substituting M=100 results in computational costs of 82K flops. In a 1Gfps (one Giga flops per second) processor, it takes less than 0.1ms to do the calculations of the proposed algorithm when M equals 100. As a general measure note that here the computational cost is of order O(M2).

3  Experimental Results

The proposed algorithm is developed in MATLAB 7.0.4 on a PIV 3.00GHZ with 1GB of RAM. In this platform it takes less than 2ms to give the solution for a cell containing 100 stations.
Note that the parameters of the problem are the sequence g1,¼,gM plus I, g, pmax, and Pmax. To compare the effects of different parameters, a sample sequence gi is produced using a set of random numbers that comply with the conditions. To be able to compare the results for different values of M having a controlled variation, we down-sample this sequence to produce new sequences with different lengths (to analyze the effect of number of stations). This way we can compare the effect of selecting different values of different parameters. This analysis is solely for the purpose of showing that the proposed solution is actually functional. Here, we do not intend to give a precise experimental analysis of the problem in hand.
The base parameters used in this study are g = -30dB, I=-113dBm, Pmax=-106dBm, and pmax=23dBm  [2,1]. Whenever a parameter is different from the list given here it is mentioned. The conversion from dB to a real value is done according to x dB º 10[1/20]x. Also, x dBm º 10[1/10]x mw.
Here, we work on a circular cell of radius R=2.5Km. For the station i at the distance di from the base station we only assume the path gain which is calculated as gi=Cdin. Here, C and n are constants equal to 7.75×10-3 and -3.66 when di is in meters. Equivalently, with di in kilometers we will have C=1.2283×10-13 [2]. To produce M values of gi we uniformly put 3M points in [-R,R]×[-R,R] and from those in the circle with radius R centered at the origin we select M points.
Figure 2 shows the values of the relative aggregate system capacity for different number of stations, M, with varying I and g. The x-axis in all curves shows the number of stations. Also, each graph shows the effect of choosing between different candidates for I. Clearly, as expected, choosing smaller background noise results in a higher aggregate system capacity. In any situation that the curves stop abruptly, it means that the set of parameters does not yield any result. Again, as expected, by easing the minimum quality of service guaranteed bound, the aggregate system capacity increases.
s2.jpgs3.jpgs4.jpg
(a)(b)(c)
Figure 2: Relative aggregate capacity for different number of stations with varying I and g. (a) g = -30dB. (b) g = -40dB. (c) g = -50dB.
Similar experiments are carried out to investigate the effects of other parameters, too. Summarizing the effects of different parameters on the relative aggregate capacity, increasing I and g decreases the total performance. While the first one is a parameter showing the amount of background noise and may be reduced using better engineering, reducing the second one makes the system partial. Also, larger values of pmax and Pmax are better. Though, these values indicate the maximum power which one station affords to transmit and the maximum total interference which is tolerated, respectively. These two parameters may not be easily increased. After all, increasing pmax with fixed Pmax may not be beneficial to the aggregate system capacity, because then the condition of total transmission power will push the maximum transmission power of each station down. Also, generally, the system performance decreases as the number of stations increases.
A closer look reveals a negative aspect in the solution to the problem analyzed here. We define the ratio unfairness as the ratio between the maximum and the minimum capacities in the cell and denote it by [f\tilde]. Basically, [f\tilde] is always more than one while smaller values indicate more fair situations. Figure 3 shows the unfairness curves corresponding to the aggregate capacity curves shown in Figure 2. We see that the system is actually very unfair; one station is given a hundred times more bandwidth than another one. This observation is in accordance with what is seen in [8,4]. Actually, this unfairness was the main reason the authors in [7] devised the minimum signal to noise ratio constraint. Basically, we argue that the impracticality of the solution comes from the fact the definition of the problem neglects the unfairness of the solution. Furthermore, the formulation ignores the fact that while a minimum bound for the signal to noise ratio, and thus for the capacity, is vital there should also be a maximum bound in place too. lack of appropriate constraints on these two important aspects of the problem makes the final results partial and non-realizable. Hence, the future direction of this research is to incorporate more constraints into the problem and to use the interesting mathematical framework introduced here to yield more practical results.
s2ft.jpgs3ft.jpgs4ft.jpg
(a)(b)(c)
Figure 3: Ratio unfairness for different number of stations with varying I and g. (a) g = -30dB. (b) g = -40dB. (c) g = -50dB.

4  Conclusions

In this paper, the problem of optimizing the aggregate system capacity of reverse link CDMA systems was addressed. In this way, we analyzed a single cell and gave closed form solution to the optimization problem in the cell. Compared to the approach which relies on running a numerical search in some 1-D spaces, the proposed method only demands the computation of the objective function in less than M points in RM. Sample experiments are conducted and the results are discussed. In addition, in [6,7] the authors showed that the optimal solution has a semi-bang-bang structure. In the current paper, we establish that it is actually bang-bang.

5  Acknowledgments

We thank the respected referees for their constructive suggestions. The research of A. S. Alfa is partially supported by a grant from NSERC. The first author wishes to thank Ms. Azadeh Yadollahi for her encouragement and valuable discussions.

References

[1]
D. J. Goodman. Wireless Personal Communications Systems. Addison-Wesley Wireless Communications Series, Readings, Massachusetts, 1997.
[2]
D. J. Goodman and N. B. Mandayam. Power control for wireless data. IEEE Personal Communications Magazine, 7:48-54, 2000.
[3]
S. V. Hanly and D. Tse. Power control and capacity of spread-spectrum wireless networks. Automatica, 35 (12):1999, 1987-2012.
[4]
S. A. Jafar and A. Goldsmith. Adaptive multirate cdma for uplink throughput maximization. IEEE Transactions on Wireless Communications, 2:218-228, 2003.
[5]
S. Kandukuri and S. Boyd. Simultaneous rate and power control in multirate multimedia cdma systems. In IEEE Sixth International Symposium on Spread Spectrum Techniques and Applications, pages 570-574, NJIT, NJ, 2000.
[6]
S.-J. Oh, A. D. Damnjanovic, and A. C. K. Soong. Information theoretic sum capacity of reverse link cdma systems. In Proceedings of The 57th IEEE Semiannual Vehicular Technology Conference (VTC 2003-Spring), pages 93-97, 2003.
[7]
S.-J. Oh and A. C. K. Soong. Qos-constrained information-theoretic sum capacity of reverse link cdma systems. IEEE Transactions on Wireless Communications, 5 (1):3-7, 2006.
[8]
S.-J. Oh, D. Zhang, and K. M. Wasserman. Optimal resource allocation in multi-service cdma networks. IEEE Transactions on Wireless Communications, 2:811-821, 2003.


File translated from TEX by TTH, version 3.72.
On 11 Aug 2006, 12:53.