Transcript ALOHA protocols

ALOHA based wireless
random access technique
ECE431/Wireless communication
Multiple Access Protocols
 Many algorithms exist for allocation of
Multiple Access Channel. To begin
with let us investigate representative
algorithms:
Pure ALOHA
Slotted ALOHA
Reservation ALOHA
ECE431/Wireless communication
Pure ALOHA
 In 1970s, Norman Abramson and his
team at University of Hawaii devised
the algorithm
 The basic idea used in the algorithm
is applicable to any system in which
uncoordinated users are competing
for the use of single shared channel
 The algorithm is referred to as
Random Multiple Access Protocol or
Pure ALOHA
ECE431/Wireless communication
Random Multiple Access Protocol
 Users transmit whenever they have
data to be sent
 There will be collisions and the
colliding frames are destroyed
 However, due to the broadcasting
nature of the channel, a sender can
always find out whether or not its
frame was destroyed by listening to
the channel, the same way other
users do
ECE431/Wireless communication
Random Multiple Access Protocol
 With a LAN, the feedback is immediate
 However, with a satellite, there is a delay of
270 ms, before the sender knows if the
transmission was successful
 If the frame was destroyed, the sender just
waits a random amount of time and sends it
again
 This kind of system where users share a
common channel resource is referred to as
Contention System
ECE431/Wireless communication
Pure ALOHA System
ECE431/Wireless communication
Pure ALOHA System
 Frames have the same length
 Whenever two frames try to occupy
the channel at the same time, there
will be collision and both fames are
garbled
 Question: Can this system work? If
yes, What is the efficiency or
throughput of the system?
ECE431/Wireless communication
Formal Description of the Algorithm
 Transmission Mode: Users transmit at any
time they desire, encoding their transmission
with an error detection code
 Listening Mode: After a message
transmission, the user listens for the
acknowledgement (ACK) from the receiver.
Transmissions from different users will
sometimes overlap in time, causing errors in
the data in each of the colliding partners.
The user then receives a negative
acknowledgement (NAK)
ECE431/Wireless communication
Formal Description of the Algorithm
 Retransmission Mode: When NAK is
received, the messages are simply
retransmitted. Colliding users retransmit
after a random amount of delay
 Timeout Mode: If, after a transmission, the
user does not receive either an ACK or NAK
within a specified time, the user
retransmits the message
ECE431/Wireless communication
Slotted ALOHA
 By introducing a small amount of coordination
among users, the performance of the pure
ALOHA can be improved
 Such a scheme is referred to as S-ALOHA or
Slotted-ALOHA system
 As with pure ALOHA system, in S-ALOHA the
packet size is constant
 Packets are required to be sent in the slot
time between synchronization pulses and can
be started only at the beginning of the time
slot.
ECE431/Wireless communication
Slotted ALOHA
 This simple change reduces the rate
of collisions by half, since only
packets transmitted in the same slot
can interfere with one another.
 Normalized throughput of S-ALOHA
system is thus given by:
  Ge
G
ECE431/Wireless communication
Slotted ALOHA Operation
ECE431/Wireless communication
Slotted ALOHA Throughput
 The maximum value of throughput =
1/e=0.37
 This maximum occurs at G =1.0
 In S-ALOHA 37% of the Channel
Resource can be utilized
 There exists tradeoff between
Channel utilization and Coordination
ECE431/Wireless communication
Reservation ALOHA
(R-ALOHA)
 Significant improvement in performance can be
achieved over ALOHA system by using Reservations
 The R-ALOHA system has two basic modes:
Unreserved Mode (Quiescent State)
1. A time frame is established and divided into small
reservation subslots
2. Users use these subslots to reserve message slots
3. After requesting a reservation, the user listens for
an acknowledgement and a slot assignment
ECE431/Wireless communication
Reservation ALOHA
(R-ALOHA)
Reserved Mode:
1. The time frame is divided into M+1
slots whenever a reservation is made
2. The first M slots are used for
message transmission
3. The last is subdivided into subslots
to be used for reservations
4. Users send message packets only
in their assigned portions of the M
slots
ECE431/Wireless communication
5 Slots, 6 Subslots R-ALOHA
System
ECE431/Wireless communication
R-ALOHA System
 In the quiescent state, with no
reservations, time is partitioned into short
subslots for making reservations
 Once reservation is made, the system is
configured so that 5 message slots followed
by 6 reservation subslots becomes the
timing format
 In the Figure the station seeks to reserve
three message slots
 The reservation acknowledgement advises
the station where to locate its data packets.
ECE431/Wireless communication
R-ALOHA System
 Since the control is distributed, all
stations receive the downlink
transmission and are aware of the
reservation format
 The acknowledgement need not
disclose any more than the location of
the first slot to use.
 When there are no reservations
taking place, the system reverts back
to its quiescent mode
ECE431/Wireless communication