Bryan Davis

October 22, 2000

Analytical Results on Calculating the Number of Pairs in CDMA system using Nonuniform PSK Modulation

Conditions Necessary for Pairing

In the forward link on a CDMA system it can be assumed that the wireless channel identically affects each code division channel. Thus, if no wave steering is implemented using adaptive array antennas (other than perhaps sectorization), each receiver in a cell sector will receive every signal with a signal-to-noise ratio proportional to the power sent at the tower. When power control is implemented on the forward-link, the signals meant for receivers farther away from the tower will have more power in relation to signals meant for receivers close to the tower. This property gives rise to a modulation technique described in [1] that allows receiver a to receive the signal b, where signal b has additional information encoded on it at a lower power level. This auxiliary information cannot be decoded by receiver b itself, because b receives the signal b with just enough power to satisfy the QoS for the primary signal. But, if receiver a receives signal b with a sufficient signal-to-noise ratio, it can decode this auxiliary information. Thus whether receiver a is more capable [1] than a receiver b is solely a function of the ratio of transmitted power for b and a, and power ratio of auxiliary encoded data to the primary data.

 

Let the ratio of the power of primary data to auxiliary data be g, and let p(i, j) be the received power of signal i at receiver j. Then receiver a will be more capable than receiver b if

.

If we assume that the channel filtering affects each channel identically, then the ratio

Using this property, we can order the receivers according to the relative power of their signals. Let receiver 1, have the signal with the least power, receiver 2 has the next to least power, etc.  Then receiver i is less than receiver j, if i < j.

Formula for the Number of Pairs

Remember that a receiver can pair with only one other less capable receiver, and one more capable receiver. Assume we have a total of N receivers. Then if all receivers can pair with one another there can be at most N – 1 pairings, with (1, 2), (2, 3), …, (N – 1, N). The problem of finding the maximum number of pairs of receivers given their distances from the tower can be reduced to the problem of finding the maximum number of consecutive receivers (in distance from the tower) that cannot communicate with each other. If we assume that there are N users in the sector, with distances from the tower of x1, x2, …, xN, and the maximum number of consecutive receivers that cannot pair is l then the pairing {(1, l + 1), (2, l + 2), …,(N – l, N)} is allowable it is the maximum possible number of pairs.

 

Proof:

Let us assume the maximum number of consecutive receivers that cannot communicate with each other is l. Then let a be smallest (in terms of transmitter signal power) receiver in such a series.

 

First, a cannot pair with {(a + 1), (a + 2), …, (a + l – 1)}, but can pair with {(a + l), (a + l + 1),…}. Since a is the worst case, any other receiver b must also be able to pair with (b + l). Thus each element of {(1, l + 1), (2, l + 2), …,(N – l, N)} is allowable pairing.

 

Second, let us assume that the only receivers that cannot pair with each other are the ones in this series {a, (a + 1), (a + 2), …, (a + l – 1)}. This assumption provides for the best-case scenario for maximal pairing given the above condition. Then any pairing is possible, as long as both members of the pair are not from the above series. If we just consider pairings with the set of less capable receivers {1, 2, …, (a + l – 1)}, then the set of more capable receivers than can pair with them is {1, 2, …, (a – 1)}. This leaves l members of the set {1, 2, …, (a + l – 1)} not having any more capable receivers to pair with. Thus there cannot be a pairing with more than N ­– l pairs. Thus the set {(1, l + 1), (2, l + 2), …,(N – l, N)}, which has N – l pairs, is a maximal set of pairs.

 

Thus when determining the maximal set of pairs, we only need to consider the maximum number of consecutive receivers that cannot pair with each other.

Incorporating the Path Model

If we assume an exponential path loss model of

where   d is usually modeled between 2 and 4,

            ki is the power control coefficient for signal i,

and       xj is the distance between the jth receiver and the tower.

 

If we model interference as white-Gaussian noise, and we assume the interference is constant throughout the cell sector, independent of the distance from the tower, and we have perfect power control, then

ή ,

since the power of signal i received by receiver i will always be the minimum power required for a given bit error rate, and since the noise is independent of position within the cell, this minimum power is the same for all receivers. Also, clearly

,

or

Therefore, in this model, the condition of a receiver being more capable than another is entirely constrained by the ratio of their distances from the cell tower. If we let d(i) = d’(j) be the minimum distance required between the receiver i and receiver j such that i and j can pair then

ή

ή

ή

ή

 

Thus, the distance between a receiver and its more capable pair is proportional to the distance of the receivers to the tower.

Density of Receivers

If the receivers in a sector are uniformly distributed throughout the sector, then the distribution function of distances of the receivers from the tower will be , i.e.  if x is ratio of the distance from the receiver to the tower to the edge of the cell to the tower.  This means that the density function will be .

Determining the Probability of k Pairs

Assume that we have N receivers uniformly distributed throughout the sector. Let us order the receivers according to the power of the transmitted signals. Let Xi be the distance from the tower of the ith receiver. Then Xi is an order statistic of the distances from the tower. If we let the random variable K be maximum number of pairs in a sector then L Ί N – K is the maximum number of consecutive receivers that cannot communicate with each other. Then

We note that Xi2 is a uniform r.v. on [0,1). Let Ui = Xi2, for all i. Then

.

The problem in calculating this probability is that the terms of the intersection are dependent. An approximation can be given for small N: UN/UN-l will have the lowest probability of occurring, since the ratio of order statistics will be smaller as the order statistic gets larger. Thus UN /UN-l ³ g2/p will therefore dominate the intersection. Thus, the following is an upper bound that is close to the result for small N and l on the order of N.

.

The joint density function for Ui and UN is given by

.

Derivation of this expression can be found in [2] p.30.

 

Let a = 1/g 2/p. Using the method of distribution functions, that the condition is true when x < ay,

No closed form solution for this expression could be found. Thus,

Note that

Performing binomial expansion,

Then

If we pull out the j = 0 term from the first summation, and increment the index of the second summation,

We can manipulate the second summation to look like the first, except for a factor.

Adding the j = 0 term back into the summation,

Note that the summation is simply a binomial expansion. Then,

This is a binomial distribution with N - 1 events, each with a probability of a. The following are well-known results of a binomial distribution:

and

 

This approximation is accurate for a wide range of practical values for N and a.

References

[1]        “Nonuniform Phase-Shift-Key Modulation for Multimedia Multicast Transmission in Mobile Wireless Networks” Michael B. Pursely, John M. Shea, IEEE Journal on selected areas in communications, Vol.17, No.5

[2]        Approximate Distributions of Order Statistics, R.-D. Reiss, Springer-Verlag Inc.