Gebali F. Analysis Of Computer And Communication Networks

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

10.6 Carrier Sense Multiple Access-Collision Avoidance (CSMA/CA) 349

former. This is due to the fact that CSMA/CA keeps transmitting frames even when

collisions have taken place. Therefore, precious bandwidth and time are wasted

transmitting frames while CSMA/CD stops the transmission promptly.

The access probability for a user in the CSMA/CA protocol is given by

(10.84)

Figure 10.12 shows the access probability of CSMA/CA when n = 50 and

N = 10. The solid line is the access probability of CSMA/CA, the dashed line

represents the access probability of slotted ALOHA, and the dotted line represents

the access probability of pure ALOHA.

The average energy required to transmit a frame is estimated as

E = E

∞



i=0

(i +1)(1 − p

)

(10.85)

where E

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

be written as

E =−10 log

dB (10.86)

Figure 10.13 shows the average energy required to transmit a frame for the

CSMA/CA when n = 50 and N = 10. The solid line is the average energy of

Fig. 10.12 Access

probability of CSMA/CA

protocol versus the average

input traffic per time step for

the case n = 50 and N = 10.

The solid line is the access

probability of CSMA/CA, the

dashed line represents the

access probability of slotted

ALOHA, and the dotted line

represents the access

probability of pure ALOHA

0 2.5 5 7.5 10

0.2

0.4

0.6

0.8

Input traffic

Access probability

350 10 Modeling Medium Access Control Protocols

Fig. 10.13 Average energy to

transmit a frame for the

CSMA/CA protocol versus

the average input traffic per

time step for the case n = 50

and N = 10. The solid line is

the energy for CSMA/CA,

the dashed line represents the

energy for slotted ALOHA,

and the dotted line represents

the energy for pure ALOHA

0 2.5

–1

5 7.5 10

Input traffic

Energy (dB)

CSMA/CA, the dashed line represents the average energy of slotted ALOHA, and

the dotted line represents the average energy of pure ALOHA.

The average number of attempts for a successful transmission is

∞



i=0

i (1 − p

)

1 − p

(10.87)

Figure 10.14 shows the delay of the CSMA/CA protocol when n = 50, N = 10,

and p = 1. The solid line is the delay of CSMA/CA, the dashed line represents the

delay of slotted ALOHA, and the dotted line represents the delay of pure ALOHA.

Fig. 10.14 Frame delay for

the CSMA/CA protocol

versus the average input

traffic for the case n = 50

and N = 10. The solid line is

the delay of CSMA/CA, the

dashed line represents the

delay of slotted ALOHA, and

the dotted line represents the

delay of pure ALOHA

0 2.5

–5

5 7.5 10

Input traffic

Delay

10.7 IEEE 802.11: DCF Function for Ad Hoc Wireless LANs 351

10.7 IEEE 802.11: DCF Function for Ad Hoc Wireless LANs

A major advance in wireless communications is introduction of the IEEE 802.11

medium access control (MAC) and physical layer (PHY) standard. The specification

includes three sublayers of the physical (PHY) layer: a frequency-hopping spread-

spectrum (FHSS) physical layer, a direct-sequence spread-spectrum (DSSS) link

layer, and a diffused infrared layer [9, 10]. IEEE 802.11 wireless LAN standard is

used for infrastructure as well as ad hoc networks.

Infrastructure wireless networks have a central controller called access point

(AP) that coordinates medium access among the users. This part of the protocol is

referred to as point coordination function (PCF) and it occupies a short time period

at the start of each transmitted frame as shown in Fig. 10.15. The frame starts with

a point coordination function (PCF) period, which is a time period to enable pri-

oritized access for control messages and time-critical traffic [11–13]. This form of

centralized medium access scheme enables the IEEE 802.11 to offer some quality

of service (QoS) guarantees through implementation of a scheduling algorithm at

the AP.

AD hoc wireless networks do not have a central controller. Instead, each node or

user attempts to access the shared medium on its own. This part of the protocol is

referred to as distributed coordination function (DCF) and it follows the PCF period

of each transmitted frame as shown in Fig. 10.15. This is a form of distributed

reservation scheme that could provide statistical QoS guarantees.

10.7.1 IEEE 802.11: DCF Medium Access Control

The DCF MAC part of IEEE 802.11 standard is based on CSMA-CA (listen-before-

talk) with rotating backoff window [11]. When a node receives a frame to be trans-

mitted, it chooses a random backoff value, which determines the amount of time the

node must wait until it is allowed to transmit its frame. A node stores this backoff

value in a backoff counter. During periods in which the channel is clear, the node

decrements its backoff counter. (When the channel is busy it does not decrement

its backoff counter.) When the backoff counter reaches zero, the node transmits the

frame. Since the probability that two nodes will choose the same backoff factor is

small, collisions between frames are minimized. Collision detection, as is employed

in Ethernet, cannot be used for the radio frequency transmissions of IEEE 802.11.

The reason is that when a node is transmitting it cannot hear any other node in the

system which may be transmitting, since its own signal will drown out any others

arriving at the node.

Fig. 10.15 Location of PCF

and DCF periods in the frame

of IEEE 802.11 protocol

Point Coordination

Function Period (PCF)

Frame

Transmitted packet

Distributed Coordination

Function Period (DCF)

352 10 Modeling Medium Access Control Protocols

Fig. 10.16 DCF part of the

IEEE 802.11 frame

PCF/

SIFS

Backoff window

Frame

Transmitted packet

01 2 345

In that sense, 802.11 could be classified as CSMA/CA but with provisions for

reducing the chance of collisions through adoption of the reservation slots using the

backoff counters. The slots have the effect of ensuring that a reduced number of

users compete for access to the channel during any given reservation slot.

Figure 10.16 shows the DCF part of the IEEE 802.11 frame. After the PCF period

(i.e., SIFS), there is the DCF period (i.e., DIFS) which is a contention window that

is divided into reservation slots. The figure shows six such slots. The duration of a

reservation slot depends on the propagation delay between stations. The rest of the

frame is dedicated to transmitting the frames.

A station that intends to transmit senses if the channel is busy. It will then wait

for the end of the current transmission and the PCF delay. It then randomly selects

a reservation slot within the backoff window. The figure shows that a station in time

reservation slot 2 starts transmitting a frame since the channel was not used during

reservation slots 0 and 1.

Collisions occur when two or more stations select the same reservation slot. If an-

other station started transmission at an earlier reservation slot, the station freezes its

backoff counter and waits for the remaining content of this counter after the current

transmission ends. We consider the behavior of one user, which we term the tagged

user. Figure 10.17 shows the IEEE 802.11 MAC scheme as viewed by a certain user

(called the tagged user). Figure 10.17 indicates that the tagged user, as indicated

by the black circle, randomly selected reservation slot 7 to start transmission. So its

backoff counter contains the value 7 now. However, another user starts transmission

at reservation slot 2 as indicated by the grey box. Since the channel was quiet for two

reservation slots (slot 0 and 1), the backoff counter of the tagged user will contain

the value 5 at the end of the current frame.

Figure 10.17(b) shows the next frame. However, another user at reservation slot

1 started transmission. Since the channel was quiet for one reservation slots (slot

0), the backoff counter of the tagged user will contain the value 4 at the end of the

current frame.

Figure 10.17(c) shows the next frame. The tagged user is successful in starting

transmission since the channel was quite for four reservation slots (0, 1, 2, and 3).

10.7.2 IEEE 802.11: DCF Model Assumptions

In order to facilitate developing an analytical model for the 802.11 protocol, we

model the backoff counters in each station in terms of allocation to a reservation

10.7 IEEE 802.11: DCF Function for Ad Hoc Wireless LANs 353

Fig. 10.17 IEEE 802.11

MAC scheme

Tagged user

Transmitted packet

01234567

(a)

Transmitted packet

01234567

(b)

Transmitted packet

01234567

(c)

slot. Figure 10.18 shows the backoff window divided into w reservation slots. The

value of w equals the maximum value that can be stored in the backoff counter of

any user.

At the start of the frame, users in slot 0 sense that the channel is idle and are able

to start transmission. When that happens, all users in the other slots will sense that

the channel is busy and will refrain from transmitting their data. A collision could

happen if two or more users in slot 0 begin to transmit simultaneously. However,

the likelihood of this event happening is small since the number of users in slot 0 is

lesser than the total number of users.

If all users in slot 0 remain idle, then users in slot 1 can transmit if they have

frames to send. The same argument can be applied to the rest of the reservation

slots.

We employ the following simplifying assumptions:

1. Since the current state of the channel depends only on its immediate past his-

tory, we can model the channel using Markov chain analysis.

2. The states of the Markov chain represent the states of the channel: idle, trans-

mitting, and collided.

Fig. 10.18 Modeling the

backoff counters in IEEE

802.11 MAC scheme in terms

of w reservation slots

w-1

Start of frame

Contention window

012

...

354 10 Modeling Medium Access Control Protocols

3. There are N equal priority users in the network. By network, we mean a single-

hop network or the nodes within the transmission range of a particular node.

4. There are w reservation slots in the contention window.

5. The duration of one time step in the contention window is roughly taken equal

to the maximum expected propagation delay τ

plus the time it takes a station

to sense the presence of a carrier. This time is called the distributed interframe

spacing (DIFS).

6. The Markov chain time step is taken equal to the DIFS period.

7. The ratio of frame transmission delay to contention window delay is n > 1.

8. All frames have equal lengths such that a frame takes n time steps to be trans-

mitted.

9. Probability that an idle station receives a frame for transmission during a time

step is a.

10. A station can have at most one message waiting for transmission.

11. A user selects a time slot with the same probability.

12. Collided users use the same slot reservation protocol as uncollided users—i.e.,

collided users employ a random backoff strategy as opposed to binary exponen-

tial backoff strategy.

The probability that a user with data to send reserves a particular reservation slot

is given by

α =

(10.88)

Slot reservation requests are representative of incoming traffic. Therefore, the

user population seen by each slot in the contention window is given by



= α N =

(10.89)

The above equation indicates that the number of users that compete to access the

medium is reduced from N to N



. We expect therefore that the chance of collisions

is reduced compared to the case when there were no reservation slots.

The probability that k users attempt a transmission during a given reservation slot

is given by







(1 −a)



−k

;0≤ k ≤ N



(10.90)

Based on the above assumptions, the 802.11 channel could be in one of three

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

our Markov chain. In the figure, the channel stays in the idle state with probability

x, which is the probability that all users do not have frames to send. The probability

x for this event is given by

10.7 IEEE 802.11: DCF Function for Ad Hoc Wireless LANs 355

Fig. 10.19 State transition

diagram for the 802.11

channel

Idle

Transmitting

Collided

111 1

...

x = u

= (1 −a)

(10.91)

The channel moves from idle to transmitting state with probability y, which is

the probability that only one user in any of the reservation slots requests a transmis-

sion and all users in the previous slots did not request to access the channel. The

probability y for this event is given by

y = u

+···+u

w−1



1 −u



1 −u

(10.92)

The channel moves from the idle to the collided state with probability z, which

is the probability that more than one user in any of the reservation slots requests a

transmission and all other users in the previous slots are idle. The probability z for

this event is simply given by

z = 1 −x − y (10.93)

We organize the distribution vector at equilibrium as follows:

s =



··· s



(10.94)

The corresponding state transition matrix of the channel for the case when n = 3

is given by

356 10 Modeling Medium Access Control Protocols

P =

⎡

⎢

⎣

x 001001

y 000000

0100000

0010000

z 000000

0000100

0000010

⎤

⎥

⎦

(10.95)

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

Ps = s (10.96)



s = 1 (10.97)

The solution to the above two equations is simple:

s =

n(1 − x) +1

⎡

⎢

⎣

⎤

⎥

⎦

(10.98)

When w = 1, the equilibrium distribution vector for IEEE 802.11 above becomes

identical to the equilibrium distribution vector for CSMA/CA in Eq. (10.79).

10.7.3 IEEE 802.11: DCF Protocol Performance

The throughput is given by the equation

Th =



i=1

n(1 − x) +1

(10.99)

Figure 10.20 shows the throughput of IEEE 802.11 when w = 8, n = 10, and

N = 32. The upper solid line is the throughput of IEEE 802.11/DCF, the lower

solid line is the throughput of CSMA/CA, the dashed line represents the throughput

of slotted ALOHA, and the dotted line represents the throughput of pure ALOHA.

10.7 IEEE 802.11: DCF Function for Ad Hoc Wireless LANs 357

Fig. 10.20 Throughput for

the IEEE 802.11/DCF

protocol versus the average

input traffic when w = 8,

n = 10, and N = 32. The

upper solid line is the

throughput of IEEE

802.11/DCF, the lower solid

line is the throughput of

CSMA/CA, the dashed line

represents the throughput of

slotted ALOHA, and the

dotted line represents the

throughput of pure ALOHA

0 16 32

0.2

0.4

0.6

0.8

Input traffic

Throughput

The throughput is high due to several factors such as distribution of users among

reservation channels and assuming the wireless medium is error free.

Changing the number of reservation slots has a direct effect on the throughput. To

test this, we selected values of w as 4, 8, and 16. Figure 10.21 shows the throughput

for the IEEE 802.11/DCF protocol versus the average input traffic when n = 10

and N = 32 and w = 4, 8, and 16. Dashed line represents the throughput of

slotted ALOHA, and the dotted line represents the throughput of pure ALOHA.

We note two things from this figure. First, reducing the value of n leads to lesser

throughput since more significant amount of time is spent listening to the carrier.

0 16 32

0.2

0.4

0.6

0.8

Input traffic

Throughput

w = 16

= 8

w = 4

CSMA/CA

Fig. 10.21 Throughput for the IEEE 802.11/DCF protocol versus the average input traffic when

n = 10 and N = 32 and w = 4, 8, and 16. Dashed line represents the throughput of slotted

ALOHA and the dotted line represents the throughput of pure ALOHA

358 10 Modeling Medium Access Control Protocols

0 16 32

0.5

Input traffic (packets/frame)

Collided probability

CSMA/CA

= 16

= 8

= 4

Fig. 10.22 Probability of collision for the IEEE 802.11/DCF protocol versus the average input

traffic when n = 10 and N = 32 and w = 4, 8, and 16

Second, adoption of reservation slots distributes the user requests among the slots.

This leads to less chance of collisions and more throughput results. To prove this

last point, the collision probability is shown in Fig. 10.22.

The user access probability is given by

(10.100)

Figure 10.23 shows the access probability of IEEE 802.11/DCF when w = 8,

n = 10, and N = 32. The upper solid line is the access probability of IEEE

802.11/DCF, the lower solid line is the access probability of CSMA/CA, the dashed

line represents the access probability of slotted ALOHA, and the dotted line repre-

sents the access probability of pure ALOHA.

The average energy required to transmit a frame is estimated as

E = E

∞



i=0

(i +1)(1 − p

)

(10.101)

where E

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

be written as

E =−10 log

dB (10.102)