|
Several recent scholarly publications, following an approach suggested by Ji, [2], recognize that algorithms useful for engineering applications can be obtained via the formulation of radio resource management issues, in particular power control in wireless data applications, on the foundations of microeconomic theory (A reader not already familiar with this formulation may benefit from consulting [1] and/or [3], for a general discussion). This approach is centered around the notion of a quality-of-service (QoS) index, referred to as a ``utility function'', defined as a real-valued function of certain physically-significant quantities. Algorithms are designed seeking the maximization, under appropriate rules and constraints, of the utility of each transmitter.
Utility maximization in a practical setting need not involve a human user instantaneously choosing utility-maximizing levels of resources during transmission. Rather, it may be implemented by software inside transmitting terminals. Depending upon the service agreement, a human ``customer'' may or may not have control of the embedded program. This observation is important because an inappropriate QoS index may lead the terminal to behave in a manner inconsistent with human intelligence.
Utility maximization, like other radio resource optimizations of practical interest, depends critically on a function giving the probability of the correct reception of a data packet in terms of the signal-to-interference ratio (SIR) at the receiver. This ``frame-success'' function (FSF) 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. It may be prohibitively difficult or impractical to obtain and/or work with an exact expression of this function. Therefore, functions corresponding to highly simplified situations are often utilized in analytical studies. Regrettably, the obtained results may only be valid for the rare situations for which the assumed functional form is appropriate.
In view of the above, it is highly desirable that analytical studies be based on generalized frame-success/utility functions, whose assumed characteristics match most realistic situations. Results obtained on the basis of such ``generic'' functions would then be robust, in the sense that they would apply to a wide variety of practical situations.
Perhaps the only non-trivial feature which can be assumed to match most if not all frame-success functions of practical interests is ``sigmoidness''; that is, the graph of any such function is S-shaped. Below it is assumed that the frame-success function f of interests obeys the technical properties of the generalized S-curve discussed in greater detail in [4].
Another critical issue is specifying an appropriate utility function, which is the QoS index whose maximization is assumed to be sought by each user. Below, after discussing other such indices available in the literature, the earned-throughput-to-power ratio (ETPR) is discussed. As a QoS index, the ETPR is shown to exhibit good mathematical behavior, be physically significant, attain or surpass the intuitive appeal of related measures already accepted by the scientific literature, and, perhaps more significantly, be defined for arbitrary frame-success functions of practical interest. The ETPR is discussed further in [6].
Finally, a game in which terminals with dissimilar data rates choose transmission power seeking to independently maximize their respective ETPR is analyzed. Various closed-form conditions leading to Nash equilibria (power vectors such that no terminal would be better off by unilaterally changing its power) are derived ``from first principles''. The analysis shows that all terminals want the same ``optimal'' signal-to-interference ratio (SIR). The optimal value can be clearly identified in the graph of the FSF function. But power limitations prevent some terminals from reaching the necessary power level. At equilibrium, a number of terminals transmit at full power, and others operate at power levels leading to the optimal SIR. A basic procedure to search for various equilibria is given.
It is assumed that the function, fs, giving the probability of the successful reception of a transmitted data packet in terms of the signal-to-interference ratio (SIR) at the base station is such that the related function f defined by f(x)=fs(x)-fs(0) obeys the general properties of the generalized sigmoidal function discussed in [4]. It is further assumed that this function has a continuous second derivative. The specific assumptions made in [4] are provided below.
The function fs is such that the related function f defined by f(x)=fs(x)-fs(0) has the following characteristics:
|
The Intuitive Index and Its Problem. The ratio of a terminal's throughput to the power employed by it was introduced by Zorzi and Rao [9] in an analysis of re-transmission schemes of data packets. Specifically, let fs(g) denote the frame success function, and g the received SIR. The TPR is proportional to the quantity Rfs(g)/P, where P is the transmission power of the concerned transmitter, and R its transmission rate. This yields a physically significant measure in bits per Joule of considerable appeal as a user's quality-of-service index. Below, a development leading to this measure ``from first principles'' is given. But, generally, fs(0) > 0, which implies that the TPR grows without bound as the transmission power approaches zero.
The zero-power issue can become a practical problem. The implementation of utility maximization in a practical setting may take the form of an algorithm, not necessarily controllable by a human operator, possibly embedded into a transmitting terminal. Thus, the misbehavior of the TPR near zero could drive the algorithm toward arbitrarily small transmission power levels, or no transmission at all, in situations where such behavior would be inappropriate. To counter this, the algorithm would need to be endowed with additional ``intelligence'', which would increase its computational complexity.
The Efficiency Function Remedy and its problems. Shah, et al. [8] and the literature that followed it replaced the frame success function in the numerator of the TPR with an ``efficiency function'', fe(g), which gives (as a function of the SIR in the received signal) a ``measure of the efficiency of the transmission protocol'' [8]. Then, they defined the utility function as proportional to the ratio Rfe(gi)/Pi.
But fe was only specified, as (1-2BER(gi))M, for frame-success functions of the simple form (1-BER(gi))M (BER denotes the bit error rate). Moreover, there is no clear physical or probability interpretation for this function, nor for the utility function obtained from it. Furthermore, power control algorithms designed with this efficiency function can be highly suboptimal (of the order of 18 to 1 in a specific example) [6].
The development of a QoS index from first principles may provide some additional valuable insights into this issue. This is attempted below.
It is assumed that the underlying communication technology is CDMA, although the general approach could be extended to other technologies. Specifically:
Given:
Since only one terminal is being considered in this development, the subscript i is dropped. Let Q=P·h be the power at the receiver when a certain data packet is transmitted with power P; and let I be the interference (noise) power. Then, fs(GQ/I) is the probability that said packet is correctly received. G is the spreading (processing) gain, defined as the ratio of the channel's ``chip rate'', Rc, to the transmission bit rate, R.
Assuming that, once a packet is received in error, re-transmission is ideal, then the total number of times a given packet needs to be transmitted, including re-transmissions, is a geometric random variable, whose probability distribution is of the form p(1-p)k-1 with p = fs(GQ/I). The expected value of this random variable is 1/p, interpreted as the average number of times the same packet needs to be transmitted to ensure correct reception.
The average amount of energy that needs to be spent in order to achieve
the successful reception of a data packet when transmission power is set
to P can be obtained as follows. Each packet requires an amount of
energy equal to the product of P times the length in time of a packet
(given the transmission rate R) times the average number of times
the same packet needs to be transmitted to ensure correct reception. Each
bit lasts 1/R secs, so each M-bit frame lasts M/R
secs. Therefore, the average amount of energy required by a packet is P·(M/R)·(1/p)=PM/(pR).
Thus, with transmission power fixed at P, the average number of information
bits which can be successfully transmitted with an energy budget E
is then (assuming all variables are continuous)
|
The preceding analysis has led naturally to the throughput-to-power ratio, TPR. It is tempting to assume that the terminal should choose its power in order to maximize this index, which would result in the maximal average number of bits transmitted before energy runs out. But it has already been discussed that doing so leads to technical difficulties of both theoretical and practical importance.
Throughput: Earned vs. Serendipitous. In order to prevent the technicalities in question, while preserving the physical meaning and probability interpretation of the relevant quantities, one must distinguish between two additive components of the throughput: the earned throughput, and the serendipitous (trivial) throughput. The earned throughput is the result of the expenditure of transmission power. On the other hand, the serendipitous throughput is that obtained without power expenditure, due to serendipity (a detector's wild guesses), which yields a correct detection of a packet with a probability of 2-M.
An appropriate criterion. An appropriate objective for the terminal is to choose its transmission power in order to maximize the ratio of the earned throughput derived by a transmitter to the transmission power, or the earned-throughput-to-power ratio (ETPR). This results in the maximal average number of earned successfully transmitted bits before the available energy is exhausted.
Specifically, if fs(g)
gives the probability that a packet sent by terminal i is correctly
detected, when its SIR at the base station is g
= GhP/I, then the ETPR (``utility'') of terminal i is
defined as:
|
If one wishes to make the range of the numerator equal to the interval [0,1], one can divide the ETPR by (1-fs(0)). Likewise, by multiplying, as in the original index, by the data rate R, one obtains a physically meaningful QoS index in bits per Joule. However, in the subsequent development, the scaling constants are ignored.
As long as G , h, and I are fixed, k:=Gh/I is a constant. Thus, maximizing (fs(GhP/I)-fs(0))/P is equivalent to maximizing k(fs(kP)-fs(0))/kP , or simply maximizing (fs(x)-fs(0))/x with x:=kP º GhP/I. Much relevant information about the technical behavior of the ETPR can be found in [4], which discusses the ``context-free'' maximization of the ratio f(x)/x, with f an arbitrary function with an S-shaped graph, as discussed in section II. This reference shows that this ratio is quasi-concave, and admits a unique global maximizer. The maximizer can be graphically identified in figure (1) as x*, the abscissa of the only point at which a line tangent to f passes through the origin. Below, the behavior of the ETPR around 0 is of special interest.
The generalized frame-success function being considered is strictly convex
over the interval [0,xf], with xf
a positive number. It is well-known that the continuously differentiable
function fs:I®
R defined on an interval I Ì
 is strictly convex if and only if, " x1,x2 ΠI,
|
|
(2) |
This inequality, (2), immediately implies that if fs ``starts out'' convex, as assumed, fs¢(0) must be finite. And a simple application of L'Hospital rule shows that the ETPR (see equation (1)) goes to kfs¢(0) when its argument goes to zero. Therefore, as long as fs has the assumed shape, ETPR(0)=limx¯ 0ETPR(x) is finite. Furthermore, inequality (2) can be re-written as k(fs(x)-fs(0))/x > kfs¢(0). The left hand side of this inequality is the ETPR evaluated at x (equation (1)), and the right-hand side is ETPR(0). Thus the ETPR is actually minimized at 0, and, for the assumed family of frame-success functions, an ETPR-maximizing algorithm will never choose 0 as the maximizer.
It is interesting to note that if fs were a function which ``starts out'' strictly concave, inequality (2) would be reversed, and could be written as (fs(x)-fs(0))/x < fs¢(0) for any x £ xf. In that case, zero would be, indeed, a (local) maximizer for (fs(x)-fs(0))/x.
In most, if not all, practical systems, the serendipitous throughput is negligible, and so is the difference between the earned-throughput-to-power ratio (ETPR) and the (total) throughput-to-power ratio (TPR). However, the mis-behavior of the TPR for low transmission power is of theoretical and practical importance, as has already been explained.
By contrast, the ETPR is well-behaved throughout its entire domain. Not only does this facilitate mathematical analysis. It also means that an ETPR-maximizing algorithm will not choose an unreasonably small transmission power because of the technical misbehavior of the objective function. This additional reliability comes without any significant complexity cost.
Intellectual curiosity may lead one to consider which one of these two ratios, regardless of the technical issue at the origin, come closer to an `ideal' QoS index. The TPR divides the average amount of data successfully transmitted (per time unit) by the energy spent (in each time unit). This yields a sensible measure in bits per Joule which is appealing as a guide for energy-expenditure decisions. On the other hand, the ETPR compares the amount of energy spent (in each time unit), to the average amount of data (per time unit) the transmitter could not have delivered without energy expenditure. Hence, the ETPR, in fact, reflects a refinement of the intuition leading originally to the TPR. As it turns out, this refinement solves a problem of practical and theoretical importance, without exacting any significant cost.
Finally, one may wonder why the transformation leading to the ETPR, which may superficially seem `obvious', was not made in earlier works. A plausible answer is that, if some increasing function g is such that g(0) > 0 which makes g(x)/x go to infinity as x¯ 0, the transformed ratio (g(x)-g(0))/x may also go to infinity as x¯ 0. An example of this is g(x)=Öx+1, for which (g(x)-g(0))/x=1/Öx which clearly goes to infinity as x¯ 0. In fact, it was shown in section IV-C that for any function g which ``starts out'' concave, (g(x)-g(0))/x indeed reaches a (local) maximum at zero! One has to invoke the ``initial convexity'' of the frame-success function in order to show that an ETPR-maximizing algorithm will not converge to zero. Interestingly, all this implies that if a communication channel is ever found with a concave frame-success function, then an ETPR-maximizing terminal should decline to use this channel.
For a given level of interference, Ii , terminal
i wants to choose its transmission power, Pi
, to maximize:
|
(3) |
subject to:
|
where Gi=Rc/Ri (i.e., the processing gain or ratio of the ``chip rate'' Rc (chips/sec) to the fixed transmission rate Ri (bits/sec)), hi £ 1 is the path loss factor, Qi=Pihi is the received power at the base station, and Pmax is the highest possible transmission power. Moreover, N will denote the number of active users, and s2 the average noise power in the receiver.
As discussed in section IV-C, the maximization of the ratio f(x)/x for function f as described in section II has been discussed extensively by Rodriguez[4]. This work shows that f(x)/x is quasi-concave, and admits as unique global maximizer x*, which is the only positive number satisfying xf¢(x)=f(x) (see figure (1)).
This implies that the maximizer sought in the problem of section V-A.1 is the smallest of xMi
and x*. Let xi*=min(x*,xMi).
It follows that, for a given interference level Ii,
transmitter i will respond with a Pi*
such that
|
(4) |
In this context, a Nash equilibrium is a power vector, specifying a power level for each active terminal, such that no terminal can increase its utility by unilaterally changing its power level.
The preceding development indicates that the ``best response'' of each terminal is such that, for a given interference level, each would like to set its transmission power to achieve a ``received'' signal-to-interference ratio of x*, a constant determined by the physical layer through the frame-success function. When a terminal cannot reach the power level leading to x*, it transmits at the highest possible power level. However, the interference level is not a fixed constant, but rather, a variable determined by the transmission power levels of all active terminals. Thus, it is, in principles, unclear whether an equilibrium power vector will exist.
It can be shown on the basis of a well-known result by Gerard Debreu that, if transmission power is limited and utility functions are quasi-concave (which the ETPR is), a Nash-equilibrium does exist (see [7] for further details). Nevertheless, below the conditions for the existence of Nash-equilibria of various forms (with and without transmission power limits) are explored ``from first principles'', without explicitly invoking Debreu's or similar results.
This section seeks conditions under which a solution exists for a set of N equations of the form:
|
(5) |
This problem is fully discussed in [5]. The equations defining the ai's (equation (5)) lead to a system of equations:
|
(6) |
Then, one can show that if the condition
|
(7) |
|
(8) |
Evidently, if all Gi's are identical, then ai=a = x*/G :=1/[^(G)], and the feasibility condition given by (7) reduces to:
|
(9) |
Likewise, equation (8) becomes:
|
(10) |
This development leads to the following conclusion about the feasibility of the ERSNE. In order for the ERSNE to be feasible, condition (7) must be satisfied. When this condition is satisfied, equation (8) gives the levels of received power which would lead the terminals to the desired SIR, x*. Therefore, the ERSNE may fail for either of two reasons: failure of condition (7), or inability by any terminal to reach the required power level. In either case, the possibility that a non-ERS equilibrium exists needs to be explored.
This section explores conditions under which a Nash equilibrium exists in which one terminal operates at maximal power, while all others operate at whichever power level is necessary to achieve the optimal SIR of x*. This case will be identified as an ERSoMP-NE-1 for an equal-received-SIR or maximal-power Nash equilibrium of order 1.
For expositional convenience, it is assumed that terminal N is the one
operating at maximal power. In this scenario, the received power from terminal
N, QN, is presumed fixed at hNPmax:=[`(Q)]N, while others need
to be found to satisfy :
|
(11) |
where S2:=[`(Q)]N+s2 . For i=1¼N-1 the value of each ai is the same as in the original equation (5).
Evidently, the equations of the form (11) lead
to a system analogous to (6), except that it is of order
N-1, and S2 replaces s2. From the development leading to condition
(7), the feasibility condition for the solution
of this new system is:
|
(12) |
Likewise, if inequality (12) is satisfied, a unique solution exists, in which the first N-1 components of the received power vector satisfy:
|
(13) |
Notice that if inequality (7) is satisfied, so is inequality (12). But the converse is obviously not true.
Again, if "i, ai=x*/G=a, the feasibility condition given by (12) reduces to:
|
(14) |
and equation (13) becomes:
|
(15) |
Even if the new feasibility condition (12) is satisfied, and each of the terminals from 1 to N-1 can reach the required power level (13), the possibility that this allocation may not be a Nash equilibrium needs to be explored. According to the development in section V-A.2, the best-response function of terminal N is given by equation (4) as QN*=min([(IN)/([^(G)])],[`(Q)]N). This means that if [`(Q)]N > IN/[^(G)], terminal N would be better off by lowering its power, and the allocation being considered would fail to be a Nash equilibrium. This possibility is explored below for the identical-rates case. The extension of this procedure to consider nonidentical rates is straightforward.
On the basis of equation (15), IN
can be obtained as
|
(16) |
In order to ascertain whether [^(G)][`(Q)]N
< IN, this inequality can be expressed as
|
|
|
(17) |
On the other hand, if condition (9) failed, which means that the original ERSNE would have been impossible even without a power limitation, then the left-hand-side of inequality (17) is negative, which directly implies that this inequality is necessarily satisfied.
In conclusion, the ERSoMP-NE-1 exists whenever three requirements are met: (i) condition (12) is satisfied, (ii) each of the terminals from 1 to N-1 can reach the required power level (13), and (iii) the ERSNE failed to exist. (For this purpose, it does not matter whether the ERSNE failed because condition (9) failed, or because terminal N could not reach the required power level).
The preceding development suggests the following extension to the more general equilibrium in which M terminals operate at maximal power, with the remaining ones operating with received SIR equal to x*; i.e., an equal-received-SIR or maximal-power Nash equilibrium of order M (ERSoMP-NE-M) . As discussed in the introduction to section V-B, given the quasi-concavity of our utility function, such equilibrium exists, whenever transmission power is limited [7].
For expositional convenience, it is assumed that the terminals have been labeled so that if M terminals cannot reach the required power level, they are terminals N-M+1 through N. For instance, this will happen if both the transmission bit rates, and the maximal transmission power levels are constant across terminals, but the ``gain'' (path loss) factors satisfy h1 > ¼ > hN.
First, check whether condition (9), which determines the feasibility of the power-unlimited ERSNE, is satisfied, and all terminals can reach the appropriate power level given by
equation (8). If this is the case, then the ERSNE is the only available NE. If condition (9) fails and transmission power is unlimited, then no NE is available. If an ERSNE is not possible (for whatever reason), and transmission power is limited, then set terminal N at maximal power and determine whether an ERSoMP-NE-1 is possible. If condition (14) fails, or if this condition is satisfied but one or more of the first N-1 terminals cannot reach the required power level, (equation (13)), then an ERSoMP-NE-1 is not possible. Hence, set both terminal N and terminal N-1 at maximal power, and proceed to verify whether an ERSoMP-NE-2 is possible. Continue this recursion, until an ERSoMP Nash equilibrium of order M is reached.
Supported in part by the NSF through the grant ``Multimodal Collaboration Across Wired and Wireless Networks'', and by NYSTAR through the Wireless Internet Center for Advanced Technology (WICAT http://wicat.poly.edu) at Polytechnic University. Comments by Dr. Cem Saraydar have improved this paper.
