In the seventies, the ALOHA system was proposed by Norman Abramson as an effective solution to provide for wireless access to computer systems. The ALOHA-net at the University of Hawaii employed fixed transmitters at islands located at ranges of several tens of kilometers. The main advantage of the ALOHA random access scheme was simplicity. Terminals can transmit their data regardless of the activity of other terminals. If a message is successful the base station sends an acknowledgement over a feedback channel. If the terminal does not received an acknowledgement, the terminal retransmits the message after waiting a random time. The delay is mainly determined by the probability that a packet is not received (because of interference from another transmission, called a "collision") and the average value of the random waiting time before a retransmission is made.
Later studies revealed that, for an infinite population of users and under certain channel conditions, the ALOHA system is unstable. Packets lost in a collision are retransmitted, but the retransmission again experiences a collision. This may set off an avalanche of retransmission attempts. Almost surely, the "backlog", i.e., the number of previously unsuccessful packets that need to be retransmitted, grows beyond any finite bound. One method to mitigate instability is to dynamically adapt the random waiting times of all terminals if the base station notices that many collisions occur. Examples of methods to ensure stability are Dynamic Frame Length (DFL) ALOHA, by Frits Schoute, or the Stack Algorithm by Boris Tsybakov et al. DFL uses a centralized control, mastered by the base station, while the stack algorithm is a decentralized method.
|See the collision resolution animation and the exercise.|
ALOHA in Mobile Radio Nets
The ALOHA concept is very commonly used in modern wireless communication systems. The call set-up procedure of almost any (analog or digital) cellular telephone system uses some kind of ALOHA random access. But the performance differs from what one would expect in a wireline network.
In a radio channel, packets may be lost because of signal fading even if no contending other signal is present. On the other hand, packets may be received successfully despite interference from competing terminals. This is called `receiver capture'. This effect has a significant influence on the throughput.
Optimum frequency reuse for ALOHA Random Access networks differs from frequency reuse for telephony, because the performance criteria differ (throughput / delay versus outage probability, respectively). The best reuse pattern for an ALOHA system is to use the same frequency in all cells.
Figure: Description of terminal behavior in ALOHA random access network
In unslotted ALOHA, a transmission may start at any time. In slotted ALOHA the time axis is divided to slots. All terminals are assumed to know the times at which a new slot begins. Packets may only be transmitted at the beginning of a new slot. Slotted ALOHA has significantly better throughput than unslotted ALOHA.
If the transmitter-to-receiver propagation time is large and unknown, the slot time must be equal to the packet length plus a sufficiently large guard time. In the call set-up of GSM, random access packets are substantially shorter than normal telephone speech blocks: During call set-up the propagation time is still unknown because the subscriber can be anywhere in the cell. During the call, the propagation times are measured and the terminal transmitter will compensate for it, by sending all blocks a bit in advance. A closed-loop control circuit, sending adaptive timing advance/delay feedback information, is used to ensure that the timing remains correct even if the subscribers moves in the cell.
Relevant performance measures are