|
Modern wireless networks will accommodate simultaneous transceivers operating at very different bit rates. Several technologies have been proposed to accommodate multi-rate traffic in such networks. Ottosson and Svensson [3] discuss several multi-rate schemes based on Direct Sequence Code-Division Multiple Access (DS-CDMA). One such scheme is variable spreading gain (VSG) CDMA, as described, for example, by I and Sabnani[1]. In a VSG-CDMA system, each terminal's spreading gain is determined as the ratio of the common chip rate to the terminal's bit rate.
The model discussed in this paper is relevant to an interference-limited single-cell VSG-CDMA system in which each data terminal can operate within a range of bit rates, which is assumed continuous for tractability. We seek an allocation specifying, for each active terminal, a choice of data rate and power level which will maximize the network weighted throughput. The weights admit various interpretations, including levels of importance or priority, ``utilities'', or monetary prices (contribution to the network's revenues). The traffic is assumed to be delay-tolerant (``best-effort'').
Similar situations have been considered by the literature. Our formulation has much in common with that of Ulukus and Greenstein [9]. Major differences between ours and their work include (a) our consideration of weights (b) our adoption
of a ``generalized'' frame-success function (discussed below), and (c) the simplifying linearization involved in their solution procedure. A recent work by Lee, et al. [2] is also of interest. They also seek data rates and power allocation, and consider a ``sigmoidal-like'' frame-success function. But they focus on the downlink, do not consider weights, and provide a sub-optimal algorithmic solution based on pricing. Our work has also many similarities with that of Sung and Wong [8]. They maximize a fairly general ``capacity function''. But they do not consider weights, and assume that the terminal's data rates are fixed exogenous parameters, as opposed to variables to be chosen optimally. Other related works seek decentralized solutions.
Of special notice is our characterization of the frame-success function (FSF), which gives the probability that a data packet is received successfully in terms of the terminal's received signal-to-interference ratio (SIR). This function, which is at the core of the analysis, is determined by physical attributes of the system, including the modulation technique, the forward error detection scheme, the nature of the channel, and properties of the receiver, including its demodulator, decoder, and antenna diversity, if any. We do not impose any particular algebraic functional form (``equation'') as FSF. Rather, we assume that all that is known about this function is that its graph is a smooth S-shaped curve, as displayed in fig. (1)(see [4] for further discussion of this approach). Our development exploits properties derived from this shape. Hence, our analysis should apply to many physical layer situations of practical interest, as long as they give rise to an FSF with an S-shaped graph.
Below, we first build a relatively simple optimization model relevant to uplink data transmission in one VSG-CDMA cell. Afterward, we provide an outline of the general solution procedure. Then, we discuss the two-terminal special case, as it provides insights useful for the general analysis. Subsequently, we apply the general solution procedure to the N-terminal scenario, and provide some general results. Finally, we discuss our results, and comment on additional research which is needed before we fully comprehend all interesting aspects of this problem.
We seek to solve:
| (1) |
| (2) |
| (3) |
In this simple model,
| (4) |
| (5) |
| (6) |
The general procedure is as follows:
For pedagogical reasons, we first discuss a two-terminal situation. This case is analyzed in greater detail in [7]. Here, we discuss the essential ideas and results.
We seek to solve:
| (7) |
It can be easily verified that for N=2, the constraint (2) reduces to a1a2=1 . This also follows from the fact that, with negligible noise, a1:=Q1/Q2:=1/a2.
Our ``augmented'' objective function is f(G1,G2,a1,a2)=
| (8) |
The FONOC can be expressed in vector form, with gi=Giai,
as:
| (9) |
| (10) |
First we seek a solution to FONOC which lies in the interior of the feasible region. That is, we presume that a solution exists in which both G1 and G2 are greater than G0, which require m1=m2=0 (see equations (10)). Then, we proceed to check whether such a solution actually exists.
Working with the top 2 rows of the matrix equation (9), we obtain gif¢(gi)=f(gi), an equation of the general form:
| (11) |
Rodriguez[6] shows that for the class of generalized sigmoidal functions, such as f, there is a unique positive value g0 which satisfies equation (11). This value can be graphically identified in figure (1) as the abscissa of the point where the graph of f is tangent to a ray emanating from the origin; that is, tangent to the straight line y=f¢(g0)x.
Therefore, if any values of the variables of interest satisfy, under the stated hypotheses, equations (9) and (10) , they must be such that:
| (12) |
By working with the bottom half of the matrix equation (9), we establish that:
| (13) |
Now, substituting equation (12) into equation (13),
we obtain a1*/a2*=b, which leads to
a complete ``interior'' solution to FONOC:
| ||||||||||||||||
Notice that, in order for these values to be feasible, Gi* ³ G0; i.e., G0Ö{b} £ g0.
Replacing these values into the objective function yields
| ||||||||||||||||||||
We have found a closed form solution. If the function f is known,
g0 can be easily obtained graphically (see figure (1))
or equation(11) can be solved numerically. For instance,
for the FSF corresponding, under suitable assumptions, to non-coherent
FSK with packet size M=80, which is,
| (16) |
This allocation has an interesting property: it is `balanced' in the sense that both users experience the same weighted throughput: f(g0)Ö{b}/g0. The ``fairness'' of this operating point may be a desirable feature in certain situations.
Second-order sufficient conditions: The previously found allocation does satisfy FONOC . But it can be shown through the second-order sufficient conditions that it is neither a minimizer nor a maximizer. It is a saddle point [7].
In the preceding section, we identified an ``interior'' solution to FONOC. But this allocation is a non-maximizer, which suggests that a maximizer be sought over the ``boundary'' of the feasible region; i.e., when Gi=G0 for one or both i. Below, we seek an ARBS solution, in which the ``favorite'' terminal is the only one transmitting at the highest allowable data rate. That is, we set G2=G0, which allows m2 ¹ 0, and m1=0, which allows G1 ³ G0.
Working with the first row of equation (9), and keeping in mind that we have set m1=0, we obtain G1a1=g0, with g0 as defined by equation (11). Working with the bottom half of equation (9), and using the preceding result, we establish that:
| (17) |
with x:=G0a2. Hence, a2* is obtained by solving this equation.
For the class of functions being considered, x2f¢(x) is a ``bell-shaped'' function, as shown by figure (1).
|
This implies that, if G02/b surpasses the ``peak'' of the function on the left hand side of equation (17), then, this equation has no solutions. Therefore, if we denote as t2 the maximal value (peak) of the function x2f¢(x)/f¢(g0), (see figure (1)) a condition for the ARBS to exist is that G02/b £ t2 or that G0 £ tÖ{b}. If G02/b is sufficiently small, two values of x will satisfy equation(17). The larger value, to the right of the peak, is chosen as a prospective maximizer, and is denoted as g00.
In terms of g00 we can identify a complete solution to FONOC. By definition, g00=G0a2, which implies that a2*=g00/G0 satisfies FONOC, and obviously so does a1*=1/a2*=G0/g00. And since FONOC requires that G1*a1*=g0, then G1* can be obtained as g0/a1*=g0g00/G0.
But feasibility requires that G1* ³ G0, which imposes that G02 < g0g00. And we already had the condition that G02 £ bt2, so G02 cannot exceed min{g0g00,bt2} in order for the ARBS to be feasible.
For example, for the frame success function introduced previously as equation (16), g0=10.75, and f(g0)=0.83. When G0=2 and b = 2, both x=22.1 and x=3.97 satisfy equation (17) . Hence, g00 = 22.1. This gives TARBS=1.01. By comparison, the `balanced' solution only yields TB=0.15Ö2=0.21, which is much less.
Second-order sufficient conditions: It can be verified that the allocation we just found in terms of g00, if feasible, is a maximizer.
In the preceding section, we considered the ARBS, in which only the ``favorite'' terminal operates at the lowest available spreading gain (fastest data rate). It was observed that the ARBS fails to exist if G02/b is ``too large'', and would be infeasible if G0 > Ö{g0g00}. In this section we seek a ``greedy'' solution to FONOC, in which both terminals operate at the highest available data rate.
Working with the last two rows of equation (9) we establish that:
| (18) |
with the constraint g1g2=G02.
The symmetric case (b = 1). To gain insight into the general case, we consider the special case in which b=1. In this case, it is evident that g1=g2=G0 (a1=a2=1) (equal received powers) satisfies equation (18), and hence FONOC .
Second-order sufficient conditions: For the class of functions we are considering, the graph of the function xf¢(x) is a ``bell-shaped'' curve, as shown by figure (1). Let [^(x)] be the unique point [^(x)] where xf¢(x) reaches its maximum. In [7] we discuss that, when b = 1, the allocation g1=g2=G0 is a maximizer for G0 > [^(x)], but the same allocation is a minimizer if G0 < [^(x)]. In particular, for the function given as equation (16), xf¢(x) reaches its maximum at [^(x)]=7.95. Thus, in this example, with b = 1, g1=g2=G0 is a maximizer for G0 > 7.95, but a minimizer for G0 < 7.95.
We discuss now the N-terminal situation. The pertinent ``augmented''
objective function is f(G1,¼,GN,a1,¼,aN)=
| (19) |
The general FONOC can be expressed in vector form, with gi=Giai,
as:
| (20) |
| (21) |
| (22) |
First we seek an interior solution to FONOC. That is, we presume that a solution to FONOC exist in which each Gi is greater than G0, which requires mi=0, (see equations (21)). Then, we proceed to check whether such a solution exists.
Working with the top half of the vector equation (20), we obtain gif¢(gi)=f(gi) . Therefore, from the discussion following equation (11), we conclude that, under the stated hypotheses,
| (23) |
By working with the bottom half of the vector equation (20), we establish that:
| (24) |
Now, substituting equation (23) into equation (24), we obtain :
| (25) |
Equation (25) enables us to express aj*
(j > 1) in terms of a1. This way, the constraint relation
(6) becomes an equation which we can solve
for a1*:
| (26) |
| (27) |
Once we know the value of a1*, equation (25)
gives us the value of each aj*. And once we know each
ai*, equation (23) gives us immediately
the corresponding Gi* as g0/ai*.
Therefore, we now have a complete ``interior'' closed-form solution
to the first-order optimizing conditions :
| |||||||||||||||||
Notice that, in order for these values to be feasible, Gi*=g0/ai* ³ G0 or ai* £ g0/G0. Under the construction 1=b1 £ ¼ £ bN, the largest ai* is actually a1* (see equation (28)). Thus, this condition requires that B=åj=1NÖ{bj} £ (N-1)g0/G0.
Substituting the above values into the objective function yields :
|
| (30) |
We stress that this a closed form solution. g0 can be easily obtained from the graph of function f (see fig. (1)), or equation (11) can be solved numerically.
It is noteworthy that, if bi=1 for all i (terminals are equally ``important''), B=N and equation (30) reduces to 1/(N-1). Thus, all terminals enjoy the same throughput.
Second-order sufficient conditions It can be shown that the previously found allocation (equations (28 and29)) is neither a maximizer nor a minimizer, but a saddle point.
We sought and found an allocation satisfying FONOC, where every terminal's data rate is less than the highest available value (equations (29,28)). Unfortunately, this allocation is neither a maximizer, nor a minimizer. This indicates that the true maximizer is a non-interior solution to FONOC; i.e., a solution in which one or more terminals operate at the lowest available spreading gain. In principle, the number of possible non-interior solutions could be very large, of the order of 2N. A basic rationale is needed to systematically search for these solutions.
A reasonable starting point is to to seek an allocation satisfying FONOC in which only the spreading gain of the ``most important'' terminal is set at the lowest available value, G0 (i.e. this terminal operates at the highest available data rate), with other terminals' spreading gains to be determined by the analysis. Below we seek one such solution to FONOC. Our presumption implies that GN=G0, and that the associated Lagrange multipliers are such that mi=0 for 1 £ i < N.
Working with the first N-1 rows of the vector equation (20),
and keeping in mind that we have presumed that mi=0 for 1 £ i < N,
we obtain
| (31) |
By working with the bottom half of the vector equation (20),
we establish that:
| (32) |
| (33) |
Combining equations (31and 32)
we get
| (34) |
Equation (34) enables us to express ai*
(1 < i < N) in terms of a1. This way, the constraint relation
(6) becomes an equation with only two unknowns,
a1 and aN. Thus, we can express a1*
in terms of aN*. With
| (35) |
| ||||||||||||||||||||||||||||||
Equations (32, and 33) can be
combined as (b1=1):
| (39) |
| (40) |
| (41) |
Let us assume that a meaningful solution to equation (40) can be found, and denote this solution as g00. In terms of g00 we can identify a complete allocation satisfying FONOC.
By definition, g00=G0aN* which implies
that aN*=g00/G0 satisfies FONOC. From aN*,
equation (38) gives us immediately a1*,
and from a1* we can obtain each ai*
(1 < i < N) through equation (34). And since each
Gi* (1 £ i < N) must satisfy Gi*ai*=g0
(equation (31)), once each ai* (1 < i < N)
is known, so is the corresponding Gi*. The complete allocation
is given by:
| ||||||||||||||||||||||||||||||||||||
4.3.2.2 Existence of this solution
The preceding allocation depends on a solution to the single-variable algebraic equation (40). Here we examine the conditions under which this algebraic equation has solution(s), and if it does, which one of its solutions should be chosen.
Observe, first, that C1x/G0+D1 £ x+1. This is so, because the left-hand side of this inequality is largest when G0 and BN-1 are smallest (see equations (41)). Because of technological limitations, G0 ³ 1 (the highest available data rate cannot exceed the channel's ``chip rate''). And, BN-1=åj=1N-1Ö{bj} ³ N-1, since, by construction, 1=b1 £ bi for "i. Hence, C1 £ 1 and D1 £ (N-2)/(N-1) £ 1. All this implies that C1x/G0+D1 £ x+1.
It can be shown that, as displayed by figure (1), for the class of functions being considered, the graph of the function x2f¢(x) is ``bell-shaped'', and so is the graph of (x+1)2f¢(x)/f¢(g0). On the basis of the preceding paragraph, it can be further concluded that the function (C1x/G0+D1)2f¢(x)/f¢(g0) is also bell-shaped. This implies that, if G0 is ``too large'', the ``peak'' of this function may fall below 1/bN, unless bN is also ``very large''. Thus, equation (40) may have no solution. On the other hand, when G0 is sufficiently small and/or bN is sufficiently large, two values of x, on either side of the peak of the concerned function, will satisfy equation (17). The larger value is chosen as the prospective maximizer called g00 in the preceding subsection. Equations (42-45) give a complete solution to FONOC in terms of g00 .
As discussed in section IV-C.2.b, there may not be a feasible solution to FONOC in which the favorite terminal is the only one operating at the highest available data rate. In this section we explore the existence of a boundary allocation satisfying FONOC, in which both the favorite, and second-favorite terminals operate at the highest data rate. That is, we set GN=GN-1=G0, and mi=0 for 1 £ i £ N-2, and determine under which conditions, if any, a solution to FONOC satisfying these hypotheses actually exists.
Proceeding as in section IV-C.2, we determine that, for the
special case in which both favorite terminals have the same weight,
bN, in order for the desired solution to exist, the SIR
of the ``non-favorite'' terminals should be g0, and
the SIR of the favorites should be a solution to the algebraic equation:
| (46) |
| (47) |
But notice that this equation is nearly identical to equation (40). The only difference is that the constants C2 and D2 replace C1 and D1 (equation (41)). Accordingly, the discussion of section IV-C.2.b also applies to this case. Thus, we know that a meaningful solution to equation (46) exists under conditions analogous to those given in section IV-C.2.b for the existence of a solution to equation (40). Notice also that BN-2 < BN-1 which tends to make the left-hand side of equation (46) larger than the left-hand side of equation (40) (in particular, C2 > C1). This means that, for fixed G0 and bN, equation (46) may have solutions even if (40) does not.
Once a meaningful solution to equation (46) has been found, following a development analogous to that leading to equations (42, 43, 44, and 45), we can obtain a complete ``dual favorite'' solution to FONOC.
We have sought the optimum power levels and data rates for terminals transmitting to one base station, in a scenario relevant to 3G CDMA. The objective function is the weighted sum of each terminals' throughput. These weights admit various interpretations, including levels of importance, ``utilities'', or monetary prices. We have utilized a model which can accommodate many physical layer configurations of practical interest. The properties of the physical layer are embodied in the frame success function (FSF), which gives, in terms of received signal-to-interference ratio (SIR) the probability that a data packet is correctly received. Each physical layer has a preferred SIR, g0, easily identified in the graph of the FSF.
The 2-terminal special case makes us focus on 3 assignments: (i) a ``balanced'' allocation, in which both terminals operate at g0, and achieve equal weighted throughput; (ii) an ``unfair'' assignment in which the favorite terminal operates at maximum data rate, with the other terminal achieving the optimal SIR, g0; and (iii) a ``greedy'' assignment in which both terminals operate at maximal bit rate. The balanced assignment is always suboptimal, implying that ``fairness'' comes at the expense of performance, in this context. The favorite terminal should always operate at maximal data rate. Only when the ratio G0/Ö{b} is larger than certain threshold determined by the physical layer through the FSF should both terminals operate at maximal data rate (G0 is the smallest available spreading gain and b is the weight of the favorite terminal).
The ``greedy'' allocation is particularly treacherous, which can be shown clearly when both terminals are equally weighted. In this case, an equal-received-power assignment satisfies the first-order necessary optimizing conditions (FONOC). But this assignment can lead to either a maximum or a minimum, depending upon whether G0 exceeds a specific value determined by the physical layer. It is significant that the greedy and the unfair allocations are complementary in this sense: A low G0 may turn the greedy allocation into a minimizer, but the unfair allocation, which is a maximizer, needs a low G0 in order to be feasible.
With N terminals, the situation is more opaque, and necessitates additional research. Nevertheless, our results provide useful guidance. We have identified an ``interior'' solution to FONOC in which all terminals achieve the optimal SIR, g0, referred to above, and operate with data rates below the highest available. This solution is ``fair'' at least when terminals are equally weighted; but it is suboptimal (a saddle point). Thus, one or more terminals should operate at the highest available data rate. But, for a large N, many such allocations are possible.
A reasonable starting point for examining these solutions is to seek an allocation satisfying FONOC in which only the favorite terminal operates at the highest available data rate. Our analysis shows that in order for this ``single favorite'' solution to exist, the SIR of the ``non-favorite'' terminals should be the previously mentioned g0, and the SIR of the favorite terminal should be a solution to the equation (C1x/G0+D1)2f¢(x)/f¢(g0)=1/bN. In this equation, f is the FSF, bN ³ 1 is the weight of the favorite terminal, and C1 and D1 are constants which are largest when the weights of the non-favorite terminals are smallest. But the function (C1x/G0+D1)2f¢(x)/f¢(g0) is ``bell-shaped''. Thus, if G0 is ``too large'' the ``peak'' of this function may fall below 1/bN, unless bN is also ``very large''. All this makes intuitive sense. When G0 is ``very large'', the highest available data rate is relatively low, so keeping only one terminal operating at the highest data rate is not appealing, unless that terminal has ``a lot more weight'' than the others. However, when G0 is ``very small'', the highest available data rate is very high, and an allocation in which only one terminal operates at this very high data rate is more appealing .
When a ``single favorite'' solution to FONOC is not possible, a natural step is to seek a ``dual favorite'' solution. Doing so led us to a situation very similar to what we just described. The non-favorite terminals should operate with an SIR of g0, and the SIR of the 2 favorites should be a solution to an equation analogous to that discussed in the previous paragraph. Even if the previous equation has no solution, this equation may have solutions. But if G0 is sufficiently large, the dual-favorite solution to FONOC may also fail to exist. In this case, we would seek a ``triple favorite'' solution. And so on.
Other factors held constant, lowering the highest available data rate increases the number of terminals which should operate at maximum data rate. It is noteworthy that terminals not operating at maximal data rate should still achieve the preferred SIR of g0, which is a respectable value. For example, for a simple, but plausible FSF (equation (16)), f(g0)=0.83. Thus, even ``non-favorite'' terminals enjoy reasonable error performance.
More research is needed before we fully comprehend all interesting aspects of this problem. This includes various technical tasks, such as verifying certain second-order optimality conditions, which are essential to ascertain that a solution to FONOC is actually a maximizer. This involves showing that certain matrices are positive definite. But with an arbitrary FSF, and symbolic parameters (N, G0, bi , etc.), these matrices are symbolic, which complicates this matter. Consideration of interesting special cases could enhance our intuition, as would additional numerical exercises. The issues of QoS requirements, fairness, non-negligible out-of-cell interference, and decentralized implementations are of practical importance and deserve future consideration.
Supported in part by the NSF through the grant ``Multimodal Collaboration Across Wired and Wireless Networks'', and by NYSTAR through WICAT (http://wicat.poly.edu).
