<<

. 17
( 87 .)



>>

Station A cannot hear transmissions from C. Let us also assume that Station B is transmit-
ting to Station A and Station C receives a frame to be transmitted to D. According to the
DCF protocol, C senses the medium and finds it busy because of B™s transmission. There-
fore, it refrains from transmitting to C, although this transmission would not cause a colli-
sion at A. The “exposed-station” problem may thus result in a throughput reduction.




Figure 3.6. The “exposed-station” problem.
76 IEEE 802.11 AD HOC NETWORKS: PROTOCOLS, PERFORMANCE, AND OPEN ISSUES


3.2.3 Ad Hoc Networking Support
In this section, we will describe how two or more 802.11 stations set up an ad hoc net-
work. In the IEEE 802.11 standard, an ad hoc network is called an Independent Basic Ser-
vice Set (IBSS). An IBSS enables two or more 802.11 stations to communicate each other
without the intervention of either a centralized AP or an infrastructure network. Hence,
the IBSS can be considered as the support provided by the 802.11 standard for mobile ad
hoc networking.4
Due to the flexibility of the CSMA/CA protocol, to receive and transmit data correctly
it is sufficient that all stations within the IBSS are synchronized to a common clock. The
standard specifies a Timing Synchronization Function (TSF) to achieve clock synchro-
nization between stations. In an infrastructured network, the clock synchronization is pro-
vided by the AP, and all stations synchronize their own clock to the AP™s clock. In an
IBSS, due to the lack a centralized station, clock synchronization is achieved through a
distributed algorithm. In both cases, synchronization is obtained by transmitting special
frames, called beacons, containing timing information.
The TSF requires two fundamental functionalities, namely synchronization mainte-
nance and synchronization acquirement, that will be sketched below. We only focus on
IBSS.

3.2.3.1 Synchronization Maintenance. Each station has a TSF timer (clock) with
modulus 264 counting in increments of microseconds. Stations expect to receive beacons
at a nominal rate defined by the a Beacon Period parameter. This parameter is decided on
by the station initiating the IBSS, and is then used by any other station joining the IBSS.
Stations use their TSF timers to determine the beginning of beacon intervals or periods. At
the beginning of a beacon interval, each station performs the following procedure:

1. It suspends the decrementing of the backoff timer for any pending (nonbeacon)
transmission.
2. It generates a random-delay interval uniformly distributed in the range between
zero and twice the minimum value of the Contention Window.
3. It waits for the random delay.
4. If a beacon arrives before the random delay timer has expired, it stops the random-
delay timer, cancels the pending beacon transmission, and resumes the backoff
timer;
5. If the random delay timer has expired and no beacon has been received, it sends a
beacon frame.

The sending station sets the beacon timestamp to the value of its TSF timer at the time
the beacon is transmitted. Upon reception of a beacon, the receiving station looks at the
timestamp. If the beacon timestamp is later than the station™s TSF timer, the TSF timer is
set to the value of the received timestamp. In other words, all stations within the IBSS
synchronize their TSF timer to the quickest TSF timer.

4
To uniquely identify a IBSS it is necessary to associate to it an identification number (IBSSID) that is locally
administered and that will be used by any other Station to join the IBSS, i.e., the ad hoc network. When a station
starts a new IBSS, it generates a 46-bit random number in a manner that minimizes the probability that the same
number is generated by another station.
77
3.2 IEEE 802.11 ARCHITECTURE AND PROTOCOLS


3.2.3.2 Synchronization Acquirement. This functionality is necessary when a sta-
tion wants to join an already existing IBSS. The discovery of existing IBSSs is the result
of a scanning procedure of the wireless medium during which the station receiver is tuned
to different radio frequencies, looking for particular control frames. Only if the scanning
procedure does not result in finding any IBSS, the station may start with the creation of a
new IBSS. The scanning procedure can be either passive or active.
In passive scanning, the station listens to the channels for a beacon frame. It is worth
repeating that a beacon frame contains not only timing information for synchronization,
but also the complete set of IBSS parameters. This set includes the IBSS identifier IB-
SSID, the aBeaconPeriod parameter, the data rates that can be supported, and the parame-
ters relevant to IBSS management functions (e.g., power-saving management).
Active scanning involves the generation of Probe frames, and the subsequent process-
ing of received Probe Response frames. The station that decides to start an active scanning
procedure has a ChannelList of radio frequencies that will be scanned during the proce-
dure. For each channel to be scanned, a probe with broadcast destination is sent by using
the DCF access method. At the same time, a ProbeTimer is started. If no response to the
probe is received before the ProbeTimer reaches the MinChannelTime, the next channel
of the list is considered. Otherwise, the station continues to scan the same channel until
the timer reaches the MaxChannelTime. Then, the station processes all received Probe re-
sponses.
Probe responses are sent using normal frame transmission rules as directed frames to
the address of the station that generated the Probe request. In an IBSS, only the station
that generated the last beacon transmission will respond to a probe request, in order to
avoid wasting bandwidth with repetitive control frames. In each IBSS, at least one station
must be awake at any given time to respond to the Probe request. Therefore, the station
that sent the last beacon remains in the awake state in order to respond to Probe requests,
until a new beacon is received. There may be more than one station in a IBSS that re-
sponds to a given probe request, particularly in the case where more than one station
transmitted a beacon, either due to not successfully receiving a previous beacon, or due to
collision between beacon transmissions.

3.2.4 Power Management
In a mobile environment, portable devices have limited energy resources since they are
powered by batteries. Power-management functionalities are thus extremely important
both in the infrastructure-based and in the ad hoc modes. Obviously, in the ad hoc mode,
that is, inside an IBSS, power-saving (PS) strategies need to be completely distributed in
order to preserve the self-organizing nature of the IBSS. A station may be in one of two
different power states: awake (the station is fully powered) or doze (the station is not able
to transmit or receive). Multicast and/or directed frames destined to a power-conserving
station are first announced during a period when all stations are awake. An Ad Hoc Traffic
Indication Map (ATIM) frame does the announcement. A station operating in the PS
mode listens to these announcements and, based on them, decides whether it has to remain
awake or not.
ATIM frames are transmitted during the ATIM Window, a specific period of time fol-
lowing the beginning of a beacon period whose length is defined by the aATIMWindow
parameter (an IBSS parameter included in the beacon content). During the ATIM Win-
dow, only beacon and ATIM frames can be exchanged and all stations must remain awake.
78 IEEE 802.11 AD HOC NETWORKS: PROTOCOLS, PERFORMANCE, AND OPEN ISSUES




Figure 3.7. A data exchange between stations operating in PS mode in an ad hoc network.


Directed ATIM frames are to be acknowledged by the destination station, whereas multi-
cast ATIMs are not to be acknowledged. Hence, a station sends a directed ATIM frame
and waits for the acknowledgment. If this acknowledgement does not arrive, it executes
the backoff procedure for retransmitting the ATIM frame.
A station receiving a directed ATIM frame must send the acknowledgement and re-
main awake for the entire duration of the beacon interval, waiting for the announced data
frame. Data frames are transmitted at the end of the ATIM Window according to the DCF
access method (see Figure 3.7). If a station does not receive any ATIM frame during the
ATIM Window, it can enter the doze state at the end of the ATIM window.


3.3 SIMULATION ANALYSIS OF IEEE 802.11 AD HOC NETWORKS

As mentioned above, in this chapter we are primarily interested in the performance pro-
vided by the 802.11 MAC protocol in an ad hoc environment. In this framework, almost
all previous works are based on simulation and have looked at the performance of TCP
applications. Less attention has been devoted to UDP applications (this can be easily jus-
tified since, currently, the most popular applications use TCP as the transport protocol).
The previous studies have been pointed out several performance problems. They can be
summarized as follows. In a dynamic environment, mobility may have a severe impact on
the performance of the TCP protocol [2, 4, 6, 9, 12, 13, 17]. However, even when stations
are static, the performance of an ad hoc network may be quite far from ideal. It is highly
influenced by the operating conditions, that is, TCP parameter values (primarily the con-
gestion window size) and network topology [9, 16]. In addition, the interaction of the
802.11 MAC protocol (hidden- and exposed-station problems, exponential backoff
scheme, etc.) with TCP mechanisms (congestion control and time-out) may lead to unex-
pected phenomena in a multihop environment. For example, in the case of simultaneous
TCP flows, severe unfairness problems and, in extreme cases, capture of the channel by
few flows [24, 26“29] may occur. Even in the case of a single TCP connection, the instan-
taneous throughput may be very unstable [26, 27]. Such phenomena do not appear, or ap-
pear with less intensity, when the UDP protocol is used [29].
79
3.3 SIMULATION ANALYSIS OF IEEE 802.11 AD HOC NETWORKS


In the next subsections, we will briefly survey the findings of the previous studies. To
better understand the results presented below, it is useful to provide a model of the rela-
tionships existing among stations when they transmit or receive. In particular, it is useful
to make a distinction between the transmission range, the interference range, and the car-
rier sensing range. The following definitions can be given.
The Transmission Range (TX_range) is the range (with respect to the transmitting sta-
tion) within which a transmitted packet can be successfully received. The transmission
range is mainly determined by the transmission power and the radio propagation proper-
ties.
The Physical Carrier Sensing Range (PCS_range) is the range (with respect to the
transmitting station) within which the other stations detect a transmission. It mainly de-
pends on the sensitivity of the receiver (the receive threshold) and the radio propagation
properties.
The Interference Range (IF_range) is the range within which stations in the receive
mode will be “interfered with” by a transmitter, and thus suffer a loss. The interference
range is usually larger than the transmission range, and it is a function of the distance be-
tween the sender and receiver, and of the path loss model. It is very difficult to predict the
interference range as it strongly depends on the ratio between power of the received “cor-
rect” signal and the power of the received “interfering” signal. Both these quantities heav-
ily depend on several factors (i.e., distance, path, etc.) and, hence, to estimate the interfer-
ence we must have a detailed snapshot of the current transmission and relative station
position.
In the simulation studies presented hereafter, the following relationship has been gen-
erally assumed: TX_range IF_range PCS_range. For example, in the ns-2 simulation
tool [20] the following values are used to model the characteristics of the physical layer:
TX_range = 250 m, IF_range = PCS_range = 550 m.


3.3.1 Influence of Mobility
Station mobility may severely degrade the performance of the TCP protocol in mobile ad
hoc networks (MANETs) [2, 4, 6, 9, 12, 13, 17]. This is due to the inability of the TCP
protocol to manage efficiently the effects of mobility. Station movements may cause route
failures and route changes and, hence, packet losses and delayed ACKs. The TCP misin-
terprets these events as congestion signals and activates the congestion control mecha-
nism. This leads to unnecessary retransmissions and throughput degradation. In addition,
mobility may exacerbate the unfairness between competitive TCP sessions [24].
Numerous new mechanisms have been proposed for optimizing the TCP performance
in MANETs, including the adaptation of TCP error-detection and recovery mechanisms to
the mobile ad hoc environment. Chandran et al. propose to introduce explicit signaling
(Route Failure and Route Re-establishment notifications) from intermediate stations to
notify the sender TCP of the disruption of the current route, and construction of a new one
[4]. Upon receiving a route failure notification, the sender TCP does not activate the con-
gestion control mechanism, but simply freezes its status, which will be resumed when a
Route Establishment notification has been received.
In [13] an Explicit Link Failure Notification (ELFN) is still used to notify the sender
TCP about a route failure. However, no explicit signaling about route reconstruction is
provided. Monks, Sinha, and Bharghavan present a simulation study of the ELFN mecha-
nism, both in static and dynamic scenarios [19]. This study points out the limitations of
80 IEEE 802.11 AD HOC NETWORKS: PROTOCOLS, PERFORMANCE, AND OPEN ISSUES


this approach that are intrinsic to TCP properties (e.g., long recovery time after a timeout),
and proposes to implement mechanisms below the TCP layer. A similar approach is taken
in [17] where the standard TCP is unmodified but new mechanisms are implemented in a
thin layer, Ad hoc TCP (ATCP), between TCP and IP. ATCP uses Explicit Congestion No-
tifications (ECN) and ICMP “destination unreachable” messages to discriminate conges-
tion conditions from link failures, and from packet losses in wireless links. The ATCP
takes the appropriate actions according to the type of event recognized.
All previous techniques require an explicit notification from intermediate stations to
the sender TCP. To avoid this complexity, a heuristic is used in [6] to distinguish route fail-
ures from congestions. When timeouts occur consecutively, the sender TCP assumes that a
route failure occurred rather than a network congestion. The unacknowledged packet is
retransmitted again but the retransmission timeout is not doubled a second time. The re-
transmission timeout remains fixed until the route is reestablished and the packet is ac-
knowledged. An implicit detection approach is also taken in [31], where the authors pro-
pose to infer route changes by observing the out-of-order delivery events.

3.3.2 Influence of the Network Topology
Even in a static environment, the performance of an ad hoc network is strongly limited by
the interaction between neighboring stations [16]. Stations™ activity is limited by the be-
havior of neighboring stations (a station must sense the medium before it starts transmit-
ting) and by stations in its interfering range (interferences may cause collisions at the des-
tination station). For example, it can be shown that in a string (or chain) topology, like the
one shown in Figure 3.8, the expected maximum bandwidth utilization is only 0.25 [16].
However, things may be even worse in practice. This discrepancy is due to 802.11 MAC
inability to find the optimum schedule of transmissions by itself. In particular, in a chain
topology it happens that stations early in the chain starve later stations (similar considera-
tions apply to other network topologies). In general, the 802.11 MAC protocol appears to
be more efficient in the case of local traffic patterns, that is, when the destination is close
to the sender [16].

3.3.3 Influence of the TCP Congestion Window Size
The TCP congestion window size may have a significant impact on performance. In [10],
it is shown that, for a given network topology and traffic pattern, there exists an optimal
value of the TCP congestion window size at which the channel utilization is maximized.
However, the TCP does not operate around this optimal value and typically grows its aver-
age window size much larger, leading to decreased throughput (throughput degradation is
in the order of 10“30% with respect to the optimal case) and increased packet losses. This
behavior can be explained by considering the origin of packet losses, which in ad hoc net-
works is completely different from that in traditional wired networks. In ad hoc networks,




Figure 3.8. A string network topology.
81
3.3 SIMULATION ANALYSIS OF IEEE 802.11 AD HOC NETWORKS


packet losses caused by buffer overflows at intermediate stations are rare events (unless
the station buffer is very small), whereas packet losses due to link-layer contention (i.e., a
station that fails to reach its adjacent station; see Section 3.3.4 and [26]) are largely domi-
nant. Furthermore, the multihop wireless network collectively exhibits graceful loss be-
havior. In general, the link loss probability is insufficient to stabilize the average TCP
congestion window around the optimal value. To achieve this objective, Fu and others
propose two link-level mechanisms: Link RED, and adaptive spacing [10]. Similarly to
the RED mechanism implemented in Internet routers, the Link RED tunes the packet loss
probability at the link layer by marking/discarding packets according to the average num-
ber of retries experienced in the transmission of previous packets. The Link RED thus
provides TCP with an early sign of overload at the link level. Adaptive spacing is intro-
duced to improve spatial channel reuse, thus reducing the risk of stations™ starvation. The
idea here is the introduction of extra backoff intervals to mitigate the exposed receiver
problems. Adaptive spacing is complementary to Link RED: it is activated only when the
average number of retries experienced in previous transmission is below a given thresh-
old.

<<

. 17
( 87 .)



>>