Gebali F. Analysis Of Computer And Communication Networks

Подождите немного. Документ загружается.

10.3 ALOHA 329

12 3 4

Th 1 0.3965 0.3167 0.0376

10.9912 0.7916 0.0940

(lost) 0 0.0035 0.0833 0.3624

L 00.0088 0.2084 0.9060

00.6941 3.8790 4.9377

W 01.7507 12.2502 131.2926

As expected, the least priority queue has the worst performance.

10.3 ALOHA

ALOHA was developed by N. Abramson in the 1970s at the University of Hawaii

to allow several computers spread over a wide geographical area to communicate

using a broadcast wireless channel. The technique chosen was simple and applies to

any system where several users attempt to access a shared resource without the help

of a central controller. ALOHA did not require global time synchronization and this

impacted its performance.

In ALOHA network, a user that has a frame to transmit does so without waiting

to see if the channel is busy or not. When two users transmit at the same time both

colliding frames will be received in error due to interference. The collision phe-

nomenon that occurs in a shared medium is also known as contention. The sender

knows that contention has occurred by listening to the channel to check if the frame

it just sent is in error or not. If errors are detected, the sender retransmits the frame

after waiting for a random amount of time. Another way for the sender to sense

collision is to wait for an acknowledgment from the receiver.

Figure 10.2 illustrates the ALOHA contention problem. The figure assumes all

transmitted frames have equal lengths and each frame has a duration T . The time

T is equal to the maximum propagation delay between any pair of stations in the

network. Because of the “free for all” situation, anything can happen. Let us see how

a conflict might arise while attempting to transmit one frame, shown as the shaded

block in Fig. 10.2. Table 10.1 summarizes potential conflict situations.

Fig. 10.2 ALOHA

contention problem.

Illustrating all possible

conflict situations

encountered by the

transmitted frame (shaded

rectangle)

time

Critical Zone

330 10 Modeling Medium Access Control Protocols

Table 10.1 ALOHA contention problem: illustrating all possible conflict situations encountered

by the transmitted frame (shaded rectangle in Fig. 10.2)

Frame Start time t Contention with shaded frame

1 t

< t < t

2 t

< t < t

3 t

< t < t

Yes

4 t

< t < t

Yes

5 t

< t < t

We make the following conclusions based on Fig. 10.2 and Table 10.1. Any frame

transmitted in the period T before our shaded frame will cause contention (e.g.,

frame 3). Any frame transmitted during the period T when our shaded frame is being

sent will cause contention (e.g., frame 4). The critical zone during transmission

of the shaded frame is shown at the bottom of Fig. 10.2. Thus for a successful

transmission at a given time step, the channel must be quiet and all users must be

idle for previous time step.

10.3.1 Modeling the ALOHA Network

In this section, we perform Markov chain analysis of the ALOHA network. We

make the following assumptions for our analysis of ALOHA:

1. The states of the Markov chain represent the status of the wireless channel: idle,

transmitting, and collided.

2. The propagation delay between any pair of users is less than the frame time T .

3. The time step value T is taken equal to the frame transmission delay.

4. There are N users in the system.

5. Users can transmit any time they want.

6. The probability that a user transmits a frame in one time step is a.

7. All frames have equal lengths and the duration of each frame is T .

8. Contention occurs if a frame is sent at time t and there are transmissions during

the time period T−t to t + T .

9. A user retransmits a corrupted frame after waiting a random amount of time.

Based on the above assumptions, the wireless channel can be in one of three

states: idle, collided,ortransmitting. Figure 10.3 shows the transition diagram for

our Markov chain. The following observations help explain the figure:

Idle state: We remain in s

as long as all users are idle (probability u

). We

move to transmitting state if exactly one user requests access (probability u

)

and we move to collided state if two or more users request access (probability

1 −u

−u

Transmitting state: We move to idle state if all users are idle. If one or more

users request access, we move to collided state since there will be no period

of calm before the next transmission.

10.3 ALOHA 331

Fig. 10.3 State transition

diagram for the ALOHA

channel

Idle

CollidedTransmitting

1-u

-u

Collided state: We move to idle state if all users are idle. Any arriving requests

keep the system in collided state.

Note in the figure that the channel can move to the transmitting state in the next

time step only if it is presently idle. If the channel is presently in the collided state,

it cannot move to the transmitting state in the next time step since this would violate

condition 8 above. The channel must first become idle and quiet since any user

that attempts to transmit will only succeed in jamming the channel again. When

the channel is transmitting, a period of calm has to be maintained for one time step

and the channel then moves to the transmitting state. Otherwise, the channel will

become collided again.

The probability that k users request access during a time step is given by binomial

statistics:





(1 −a)

N−k

(10.14)

The transition matrix of the system is

P =

⎡

⎣

1 −u

−u

1 −u

⎤

⎦

(10.15)

At equilibrium, the distribution vector is obtained by solving the two equations

Ps= s (10.16)

= 1 (10.17)

The solution to the above two equations is simple:

= u

= 1 −u

−u

(10.18)

= u

332 10 Modeling Medium Access Control Protocols

10.3.2 ALOHA Performance

We are interested in the throughput of ALOHA, which is given by

Th = s

= u

(10.19)

Substituting the values of u

and u

from (10.14), we get

Th = Na(1 −a)

2N −1

(10.20)

For large N, the throughput can be expressed in terms of the input traffic as

Th = Nae

−2Na

(10.21)

The throughput is measured in units of frames/time step. The throughput in units

of frames/s is



(10.22)

The dotted line in Fig. 10.4 shows the variation of the throughput against the

average number of users transmitting frames per time step for the case when N = 10

users. The solid line is for the slotted ALOHA network, which is discussed in the

next section.

The input traffic is found from the binomial distribution

(in) = Na (10.23)

Fig. 10.4 The throughput for

ALOHA versus the average

number of requests per time

step for the case N = 10.

Dotted line is for ALOHA

and solid line is for slotted

ALOHA

0 1 2 3 4 5 6 7 8 9 10

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

Input traffic

Throughput

10.3 ALOHA 333

We define the acceptance probability or efficiency p

as the probability of a

successful transmission for a given user. p

is given by

(in)

= (1 −a)

2N −1

(10.24)

≈ e

−2aN

(10.25)

The last equation relies on the approximation

lim

n→∞



1 −



= e

The average energy required to transmit a frame is estimated as

E = E

∞



i=0

(i +1)(1 − p

)

(10.26)

where E

is the energy required to send the one frame. In dB, the above equation

can be written as

E =−10 log

dB (10.27)

≈ 20aN log

e = 8.7 aN dB (10.28)

We see that the average energy to transmit a packet increases exponentially with

increasing traffic.

The average number of attempts before a successful transmission is

∞



n=0

(

1 − p

)

(10.29)

This evaluates to

1 − p

(10.30)

If the average duration of the random wait period is τ (in seconds), then the

average wait for a frame before successful transmission is

W = n

×τ =

(

1 − p

)

seconds (10.31)

334 10 Modeling Medium Access Control Protocols

Assume that the number of stations is fixed. In that case, we can vary the ar-

rival probability a and investigate how the throughput varies with input traffic. The

maximum throughput occurs when

dTh

d a

= 0 (10.32)

Differentiating (10.20) indicates that the maximum throughput for ALOHA oc-

curs when

2 N

(10.33)

Thus, the maximum throughput is theoretically equal to

Th(max) =



1 −



2N −1

(10.34)

The above equation gives the maximum throughput for any number of users N.

A simple expression is obtained when the user population is very large, N →∞:

Th(max) =

= 18.394% (10.35)

In summary, maximum throughput occurs when N →∞and we would have

Th = 0.18394 frames/time step (10.36)

(in) = 0.5 frames/time step (10.37)

= 1/(2N) (10.38)

= Th/N

(in) = 0.367 (10.39)

This discrete-time, and very general, result compares extremely well with the

throughput estimate obtained using fluid flow analysis [1] for a continuous-time

system with Poisson traffic. Thus when the number of users increases, the trans-

mission request probability must decrease in proportion. For example, when the

system has N = 50 users, the maximum throughput is approximately 18.487%,

using Equation (10.34), and the transmission request probability for maximum

throughput must be a ≈ 0.01. The problems at the end of the chapter confirm our

predictions.

Example 10.2 Assume an ALOHA network supporting N = 20 users and each user

issues a request per time step with probability a = 0.01. Find

10.4 Slotted ALOHA 335

(a) The throughput

(b) The average number of time steps before successful transmission

(d) The value of a for maximum throughput

The performance figures are as follows:

Th = 0.1351 frames/time step

= 0.4799 attempts

Th(max) = 0.1839 frames/time step

= 0.025 for maximum throughput

10.4 Slotted ALOHA

Slotted ALOHA was proposed to improve the throughput of the original ALOHA

[2]. As the name implies, time in slotted ALOHA is divided into slots and the value

of one time step equals the frame time T . Users know about the start of a new slot

through a synchronizing signal that is transmitted by a source. A user with data to

send is permitted to transmit only at the start of a time step. This removes the chaos

of pure ALOHA and improves the efficiency as we shall see below.

10.4.1 Modeling the Slotted ALOHA Network

In this section, we perform Markov chain analysis of the slotted ALOHA network.

We employ the same assumptions that we used to model ALOHA in Section 10.3.1

with the only exception that users are allowed to transmit only at the start of a time

step and not at any time as before.

Based on our assumptions, the wireless channel can be in one of three states: idle,

collided,ortransmitting. Figure 10.5 shows the transition diagram for our Markov

chain. Further, the time step value is naturally chosen equal to the slot time value.

Now is a good time for the reader to compare that figure with the pure ALOHA

transition diagram of Fig. 10.3. What is the major difference?

The major difference is that the channel can move from collided state to trans-

mitting state in one time step. This basically creates more chances for the channel

to move to the transmitting state and this enhances the throughput and performance

in general.

Idle state: We remain in s

as long as all users are idle (probability u

). We

move to transmitting state if exactly one user requests access (probability u

)

and we move to collided state if two or more users request access (probability

1 −u

−u

336 10 Modeling Medium Access Control Protocols

Fig. 10.5 State transition

diagram for the slotted

ALOHA channel

Idle

CollidedTransmitting

1-u

-u

Transmitting state: We move to idle state if all users are idle. We move to trans-

mitting state if exactly one user requests access (probability u

) and we move

to collided state if two or more users request access (probability 1−u

−u

Collided state: We move to idle state if all users are idle. We move to transmit-

ting state if exactly one user requests access (probability u

) and we stay in

collided state if two or more users request access (probability 1 −u

−u

The probability that k users request access during a time step is given as before

by binomial statistics:





(1 −a)

N−k

(10.40)

The transition matrix of the system is

P =

⎡

⎣

1 −u

−u

1 −u

−u

1 −u

−u

⎤

⎦

(10.41)

At equilibrium, the distribution vector is obtained by solving the two equations

Ps= s (10.42)

= 1 (10.43)

The solution to the above two equations is simple:

= u

= 1 −u

−u

(10.44)

= u

Now is a good time for the reader to compare the above equation with the

corresponding equation for the equilibrium distribution vector of pure ALOHA

in (10.18). Several observations can be made even before we get any numerical

values:

10.4 Slotted ALOHA 337

1. Pure ALOHA and slotted ALOHA channels have the same probability of being

in state s

(the idle state).

2. Slotted ALOHA has a lower probability of being in state s

(the collided state)

compared to pure ALOHA.

3. Slotted ALOHA has a higher probability of being in state s

(the transmitting

state) compared to pure ALOHA.

All these factors contribute to enhance the performance of slotted ALOHA.

10.4.2 Slotted ALOHA Performance

We are interested in the throughput of slotted ALOHA, which is given by

Th = s

= u

= Na(1 −a)

N−1

(10.45)

A frame will be transmitted if only one user requests to access the channel ir-

respective of the previous state of the channel. For large N, the throughput can be

expressed in terms of the input traffic as

Th = Nae

−Na

(10.46)

Slotted ALOHA has higher throughput compared to ALOHA by a factor of

−1

= (1 −a)

−N

. We expect the two networks to perform almost the same for very

low traffic conditions (a  1). Slotted ALOHA will perform better than ALOHA

by orders of magnitude for high values of traffic (a ≈ 1), especially for systems

with many users (N  1).

The throughput in units of frames/s is



(10.47)

The solid line in Fig. 10.4 shows the variation of the throughput against the av-

erage number of users transmitting frames per time step for the case when N = 10

users. The average number of users is given by the binomial distribution

(in) = Na (10.48)

We define the acceptance probability or efficiency p

as the probability of a

successful transmission for a given user. p

is given by

(in)

= (1 −a)

N−1

(10.49)

≈ e

−aN

(10.50)

338 10 Modeling Medium Access Control Protocols

The average energy required to transmit a frame is estimated as

E = E

∞



i=0

(i +1)(1 − p

)

(10.51)

where E

is the energy required to send one frame. In dB, the above equation can

be written as

E =−10 log

dB (10.52)

≈ 10aN log

e = 4.3 aN dB (10.53)

We see that average energy to transmit a packet increases exponentially with

increasing traffic but at a rate half that of pure ALOHA.

The average number of attempts before a successful transmission is

∞



n=0

(

1 − p

)

(10.54)

This evaluates to

1 − p

(10.55)

If the average duration of the random wait period is τ (in seconds), then the

average wait for a frame before successful transmission is

W = n

τ =

(

1 − p

)

seconds (10.56)

Assume that the number of stations is fixed. In that case, we can vary the arrival

probability a and investigate how the throughput varies. The maximum throughput

occurs when

dTh

d a

= 0 (10.57)

Differentiating (10.20) indicates that the maximum throughput for ALOHA oc-

curs when

(10.58)