Random Access

Random access schemes dynamically assign radio resources to a large set of users, each with relatively bursty traffic.

A wide variety of solutions have been proposed to solve the problem of how to efficiently allow many terminals to transmit their randomly arriving messages.

Audio playlist: Data transmission differs from circuit-switched telephony. Particularly for bursty data or multimedia traffic, random access schemes are needed. The ALOHA system was the first implementation of a wireless packet data network. Such networks can exhibit instability problems. Boris Tsybakov invented the "stack algorithm" to ensure stability. Similarly, Frits Schoute's "Dynamic Frame Length ALOHA" also is stable. Jim Massey's "Protocol Sequences" allow guaranteed throughput even if no feedback is available.

An series of slides giving an overview on random access: html and ppt

ALOHA Radio Access

Any terminal is allowed to transmit without considering whether channel is idle or busy. If packet is received correctly, the base station transmits an acknowledgement. If no acknowledgement is received by the mobile, it retransmits the packet after waiting a random time.

Retransmission control

ALOHA needs some adaptive control of the retransmission scheme. Otherwise the system will become unstable. A popular method is to increase the mean waiting time if too many collisions occur. Shorter delay and higher throughput can be achieved if collision resolution schemes are used that exploit feedback about the collisions. One example is the stack algorithm.

Carrier Sense Multiple Access : CSMA

" Listen before talk ": no new packet transmission is initiated when the channel is busy. This reduces collisions.

Hidden terminals form a problem. Sometimes a new terminal may not be aware of an active transmission by another remote terminal.

Inhibit Sense Multiple Access : ISMA

Sometimes called: Busy Tone Multiple Access : BTMA

If busy, base station transmits a "busy" signal to inhibit all other mobile terminals from transmitting. In ISMA or BTMA, collisions still occur, because of

Signalling delay:
New packet transmissions can start during a delay in the broadcasting of the inhibit signal,
Persistent terminals:
after the termination of transmission packets from persistent terminals, awaiting the channel to become idle, can collide.

Performance Comparison

The most popular measure of performance is the throughput, i.e., the average fraction of time slots that contain a successfully transmitted packet. Delay is another essential parameter, but it highly depends on the stability of the network.

Figure: Throughput versus attempted traffic, for ALOHA, slotted ALOHA, 1-persistent and nonpersistent ISMA. Infinite population of terminals transmitting Poisson traffic of packets.

Historical Setting
Prof. Boris Tsybakov discusses the history of the development of random access schemes, the difficulties in analyzing the performance of the stack algorithm, and the access issues in wireless.

Random access without feedback

Conflict-avoiding codes can act as protocol sequences for successful transmission over a collision channel without feedback. Such codes guarantee for a certain user the successful transmission of a single packet, despite other users attempting to transmit packets.

JPL's Wireless Communication Reference Website

Chapter: Data Networks