Multiple access in the uplink

Let's consider an ALOHA random access scheme in a network with two cells. We address a multi-access channel with a large (possibly infinite) number of distributed terminals that send data packets to a central receiver. The transmission rate of packets per cell, i.e., the offered traffic is denoted a m packets per second. The fixed message length is L bits and the system bandwidth is B_N. For a system without spreading, the packet duration T_L = L / (h _r B_N). The system is slotted, i.e., the time axis is divided into slots and any packet transmission starts at the beginning of a slot and finishes at the end of the same slot. Ignoring propagation delays and power-up (guard) times, we assume that the slot time is of duration T_L.

Basically, the system designer as two options, one is to split the available bandwidth B_N into two bands each of B_w = B_N/2 and allocate a different band to every cell (Scenario 1, "cellular"). In this case the slot time increases to 2T_L. The other option is to allow the two cells to share the entire bandwidth (Scenario 2, contiguous frequency use). In the latter case the slot time is T_L but the traffic competing for access is that of two cells. A pessimistic assumption is that no capture occurs, i.e., any packet which sees interference from another transmission is lost. Assuming that transmit packets arrive according to a Poisson process, the probability that a packet sees no interference is exp(-G), where the offered traffic G is the average number of packets transmitted per time slot. In scenario 1 the packet length is 2T_L, so G = 2m T_L packets per slot, so the throughput is S = G exp{-G} = 2m T_L exp{-2m T_L }. In scenario 2, the offered traffic is that of two cells, so G = 2m T_L packets per slot, so the throughput also is S = 2m T_L exp{-2m T_L }. Since the statistical behavior of the retransmissions is the same, the delay is proportional to the packet duration. Hence scenario 2 outperforms scenario 1 by a factor 2 in terms of delay. This back-of-the-envelope style calculation suggests that frequency reuse, though customary for telephone traffic, is not necessarily beneficial for packet traffic. In fact, if we take into account that signal capture can occur, and that particularly in the second scenario, the two base stations can capture different packets, scenario 2 will outperform scenario 1.

More in detail, the probability of a successful transmission of a test packet is

where we inserted the Laplace expression for q_n, which stands for the conditional probability of capture, give the presence of n other contenders in the same slot.

Interestingly, for the plane-earth loss model for large-scale propagation, this can be rewritten in the form of Q = exp{-G'} where G' is the effective interfering traffic. In fact, after some manipulations, we arrive at the probability for successful transmission of packet from a location r,

where G(r) is the offered packet traffic per unit of area, transmitted from a distance r. The above expression allows iterative computing of the traffic that will be offered to the channel to achieve a certain throughut S(r) In fact S(r) = G(r) Q(r) where Q(r) depens on G(r).

A further elaboration of this model also allows analytical evaluation of the case for multiple base station in a virtual cellular network (VCN) using the same channel in every cell.

Figure 7: Attempted traffic per unit of area in VCN for throughput of 0.15 packet per slot per unit of area.

In the VCN of Figure 7 base stations are located at integer grid points. A packet is assumed to be successful if it captures at least one base station. The communication protocol must handle the routing of packets from the base stations, and resolve reception of the same packet at multiple base stations. This replaces the traditional handover schemes. Vvedenskaia [] showed that the stack algorithm can efficiently handle the retransmission of lost packets for such system. It has been proven that the scheme ensures stability in a single base station scenario. Although no formal proof exists yet, it is likely that the scheme can also ensure stability in a multi base station system.

The second design aspect is whether or not to apply DS-CDMA. In order to make a fair comparison, we take a fixed bandwidth B_N for the entire system. We compare this system with CDMA transmission with spreading factor K. This implies that the slot duration and packet transmission time are proportional to K so these become equal to T_L = K L / (h _r B_N). The message arrival rate, expressed in packets per time slot G = m K T_L = m K L / (h _r B_n). We normalize the unit of time taking L / (h _r B_n) = 1, i.e., one unit of time equals the slot duration in a system with K = 1.

Some studies assume perfect reception as long as the number of packets present in the channel is less than the spread factor. Thus, for K = 1 (no spreading), successful transmission only occurs if exactly one packet is present in that slot. If the arrival process of packets were truly Poissonian, the throughput per unit of time becomes

where S denotes the expected number of successful packets per slot. For K = 1, this reduces to the throughput of slotted ALOHA without capture, namely S = G exp(-G). Increasing K adds more positive terms to the summing, so it enhance the throughput. Throughput improves with increasing spread factors: S tends to G = m K L / (h _r B_n). For a traffic load G less than unity and K goes to infinity.

If one uses retransmission probability p, and (unrealistically !, see later) assumes a steady-state stable network, the delay d can be expressed as

This in a lightly load system (G << 1, G @ S) , the delay grows approximately proportional to K. Destructive collisions (for which k + 1 > K) become increasingly unlikely because of the law of large numbers. The ALOHA random access system 'looses' its contention character and its properties become closer to that of a fixed assignment scheme.

The capture assumption made here above requires relatively sophisticated signal processing in the receiver, to separate multiple signals. A typical simple correlation receiver may not achieve this performance. It attenuates (but not eliminates) interfering signals, coarsely by a factor equal to 1/K. Some back-of-the-envelope results can be obtained by assuming that all signals are transmitted over a Linear Time-Invariant (LTI) frequency non-selective Additive White Gaussian Noise (AWGN) channel. The energy per bit is taken identical and constant for all users and it is denoted as E_b. The noise spectral power density is N₀. The signal to noise ratio is E_b/N₀. A commonly used model for the bit error rate given K interferers is to assume that interfering CDMA signals behave a AWGN, but attenuated by the spread factor C. We assume that all signal are received with the same signal power. This allows us to compute the probability of not more than t errors in a packet. The number of packets k out of K colliding packets capture the receiver has a binomial probability distribution.

Despite these seemingly beneficial effects on throughput, even perfect CDMA with finite K cannot repair the instability of the ALOHA system with a fixed retransmission back-off probability p. Even though the probability on a destructive collision involving more than K new packets rapidly becomes small with increasing K, retransmission traffic spoils the stability of networks. The proof is based on the observation that for any finite K and fixed retransmission probability p, their exists an M such that if more than M terminals are in backlog, the backlog is expected to grow without bounds. As the probability of having M terminals in backlog is nonzero, the system will eventually experience ever-increasing backlog. In order to ensure reliable operation, CDMA packet networks thus need a control mechanism that regulates the number of packets transmitted in each time slot.

Efficient collision resolution algorithms have been proposed, such as the Stack Algorithm. For this system the network is stable, even if the number of terminals in infinite. Hence, for the stack algorithm one can compute delays, whereas rigid computations show that the delay in infinite-user ALOHA nets is unbounded.

Results in Figure 8 have been obtained for packets of L= 256 bits without error correction coding (t = 0) and with a two-bit error correcting code (t = 2). The arrival rate corresponds to the expected number of new packets per slot in an non-spreading system. The message delay expressed in seconds is [3/2 + d] K, so it includes one packet time and a half for the random waiting time till the beginning of the next slot and the message transmission duration.

The curves show that K = 1 gives a significantly smaller delay than a larger spreading factor. For large arrival rates, however, spreading gives better performance. Even if CDMA allows perfect capture, for m < 0.3 the delay is minimized if K = 1 (no spreading).

These examples suggest that Direct-sequence CDMA is not necessarily beneficial. Advances in signal separation and multi-user detection may change this conclusion in future. Frequency hopping, which is another form of spread spectrum for instance used in Bluetooth, can be useful. It ensures that during every retransmission attempt the packet experience different multipath attenuation. This enhances fairness and stability.

Hitherto we discussed an ALOHA-type of access. Practical traffic patterns usually involve the transmission of a sequence of packets. It is not effective to let every packet compete for access. In stead one desires to exploit knowledge gained from the first packet, and to reserve just adequate resources for following packets. On the other, one must guarantee that spatially separation from other transmission should be minimized. to achieve efficient spectrum usage.

Space Time Reservation Multiple Access (STRMA) is a spatial extension of the Packet Reservation Multiple Access (PRMA) concept developed at Winlab. PRMA is a framed access scheme with frames of a fixed number of slots. If a terminal has a series of packets or speech segments to transmit, it competes for access in any free slot. If it successfully captures the base station, the terminal gains reservation in the corresponding slots of the next frames, until it releases the reservation. In PRMA, adjacent cells use different carrier frequencies according to a cellular reuse plan, but in STRMA we synchronize base stations and terminals at slot level. Time slots are common to all cells, and all cells use the same carrier frequencies. However if a terminal gains a reservation in one cell for certain time slots, the base stations of the first tier of surrounding cells inhibit all other terminals to use the same time slots. Hence reservations occurs not only in time domain, as in PRMA, but also in space.

Figure 9 gives sample runs for the case of three slots per frame. Simulations at Delft University of Technology revealed that for a uniform distribution of speech terminals, STRMA with frames of 21 slots outperforms a PRMA with system with 7 slots per frame and a three cell reuse pattern. We address a system with 5 erlang per cell and a speech activity of 0.4 (40 %) according to a Markovian on-off process with average duration of speech burst of 1 second and average length of a gap of 1.35 seconds. The speech clipping probability for PRMA was about 0.5% and 0.2% for STRMA, while both systems use the same spectrum bandwidth. With non-uniform distributions of users, we expect a further performance gain over PRMA.

Surprisingly, the STRMA system remains efficient, also at higher message traffic loads. Intuitively, one may expect that during overload an inefficient reuse would occur. in contrast to this simulations consistently showed that the system tends to adhere a rigid C = 3 reuse pattern, as illustrated by Figure 10. Its behavior can be interpreted as one of cooling down a liquid into a crystalline structure. The simulation run reveals that once into such a structure, the network only tolerates new transmissions that fit in the preferred reuse pattern. This can be an explanation for the behavior.