. 29
( 87 .)


0 0 0




Figure 5.1. An example “polar” pattern, with a main lobe at 0 degrees, and multiple sidelobes of
varying gains.

dB). But since the power emanating is the same (you only have so much dough), the lobes
have to balance each other out, that is, preserve the law of conservation of power.
A related concept is the antenna beamwidth. Typically, this means the “3 dB beam
width,” which refers to the angle subtended by the two directions on either side of the di-
rection of peak gain that are 3 dB down in gain. Gain and beamwidth are related. Typical-
ly, the more directional the antenna, the higher the gain and the smaller the beamwidth.
However, two antennas with the same gain could have different beamwidths”for in-
stance, the antenna with the smaller main lobe width may have more or larger sidelobes.

5.2.2 “Smart” Beamforming Antennas
The simplest way of improving the “intelligence” of antennas is to have multiple ele-
ments. The slight physical separation between elements results in signal diversity and can
be used to counteract multipath effects. There are two well-known methods. In switched
diversity, the system continually switches between elements so as to always use the ele-
ment with the best signal. Although this reduces the negative effects of multipath fading,
there is no increase in gain. In diversity combining, the phase error of multipath signals is
corrected and the power combined to both reduce multipath and fading, as well as in-
crease the gain.
The next step up in sophistication involves incorporating more control in the way the
signals from multiple elements (the antenna array) are used to provide increased gain,
more beams, and beam agility. Again, there are two main classes of techniques, as de-
scribed below.
In switched beam systems, multiple fixed beams are formed by shifting the phase of
each element™s signal by a predetermined amount (this is done by a beamforming net-
work), or simply by switching between several fixed directional antennas. The transceiver
can then choose between one or more beams/antennas for transmitting or receiving. Al-
though they provide increased spatial reuse, switched beam systems cannot track moving
nodes, which therefore experience periods of lower gain as they move between beams.
In a steered beam system, the main lobe can be pointed virtually in any direction, often
automatically using the received signal from the target and sophisticated “direction-of-ar-
rival” techniques. One may distinguish between two kinds of steered beam systems”dy-
namic phased arrays that maximizes the gain toward the target, and adaptive arrays that
additionally minimize the gain (produce nulls) toward interfering sources. The former al-
lows beam steering, and the latter additionally provides adaptive beamforming.
In this chapter, we consider switched beam and steered beam antennas, jointly referred
to as beamforming antennas.

5.2.3 Relevance for Ad Hoc Networks
When considering the use of beamforming antennas for ad hoc networks, a question is:
Aren™t beamforming antennas too expensive and/or too big for ad hoc networks? In this
section, we argue that there do exist antenna techniques with suitable price and form-fac-
tor combinations.
Applications for ad hoc networking may be classified broadly into three categories:
military, commercial outdoor, and commerical indoor, each with its own distinctive pro-
file and able to accommodate different antenna technologies.
Military networks, which are by far the most prevalent application of mobile ad hoc

networks, contain a significant number of large nodes (such as tanks, airplanes). The size
of these platforms makes the form factor of most antennas quite irrelevant. Further, each
platform by itself is so expensive that the cost of even the most sophisticated antenna is
dwarfed by comparison. Thus, beamforming antennas are extremely relevant to military
networks. An added bonus is that use of directional transmissions provides improved re-
sistance to jammers and eavesdroppers.
Fixed ad hoc networks for commercial outdoor insfrastructure extend the reach of base
stations using wireless repeaters organized into an ad hoc network. Packets are multihop
routed through these repeater nodes with dynamic path selection. In some commercial ap-
proaches, the end-user terminals themselves serve as repeaters. Here, steered beam ap-
proaches may be too expensive. However, switched beams using inexpensive beamform-
ing networks such as the Butler matrix [2] are easily manufactured using inexpensive
hybrid couplers [1], making switched beamforming quite relevant.
The biggest deterrent to using beamforming antennas for networking small nodes
such as PDAs and laptops within an indoor environment is the size. At 2.4 GHz and the
typical half-wavelength element spacing, an eight-element cylindrical array would have
a radius of about 8 cm, making it quite unwieldy. However, as the operating frequency
continues to increase (the IEEE 802.11a is already working on wireless LANs in the 5
GHz band), the antenna sizes will shrink. At the 5.8 GHz ISM band, the eight-element
cylindrical array will have a radius of only 3.3 cm, and at the 24 GHz ISM band, a mere
0.8 cm. Thus, the future looks bright for applying beamforming technology even to such
Thus, while at first glance it may seem that ad hoc networks and beamforming anten-
nas are not compatible, a more careful examination opens up a number of possibilities.


The goal of medium-access control (MAC) is to enable efficient sharing of the common
wireless channel between nodes that need access to it. In order to be efficient, the MAC
typically needs to employ spatial reuse of the channel, that is, it must provide as many si-
multaneous communications as possible.
Both transmit power and beamforming have an obvious and significant impact on spa-
tial reuse. Reducing the transmit power reduces the circular range of interference and,
thus, the number of interfered nodes. Directing the beam toward the intended receiver re-
duces energy in directions other than toward the receiver and, therefore, also reduces the
number of interfered nodes.
Harnessing this potential, however, is nontrivial. Many MAC solutions tacitly assume
homogeneous transmit power and/or omnidirectional transmissions. When these assump-
tions are violated, performance may deteriorate to below the performance when no control
is used. We shall discuss these pitfalls in more detail later. For now, it suffices to say that
techniques specifically targeted at supporting and exploiting power and beam control are
required. Such techniques are the subject of this section.
Medium-access-control approaches may be broadly classified as either contention-
based or contention-free. For ad hoc networks, the most commonly considered con-
tention-based approach is CSMA/CA (Carrier Sense Multiple Access with Collision
Avoidance), and the most commonly considered contention-free approach is TDMA
(Time Division Multiple Access). We shall survey adaptations of both CSMA/CA and

TDMA, but focusing more on CSMA/CA because, being the basis for the IEEE 802.11
standard, it has received far greater attention.
We begin with a treatment of directional medium access control, and then survey pow-
er-controlled MAC. Finally, we consider MAC solutions that exploit both beam and pow-
er control.

5.3.1 Directional MAC
We first consider CSMA/CA. Collision avoidance for ad hoc networks was first suggested
by Karn [3], who proposed the MACA protocol. Many improvements on this were sug-
gested in MACAW [4], FAMA [5], and others. The IEEE 802.11 standard Distributed Co-
ordination Function (DCF) is based on CSMA/CA and is a good example of this ap-
proach. We describe it briefly below. Details can be found in [6, 7].
The IEEE 802.11 MAC Protocol. The IEEE 802.11 DCF used up to four frames for
each data packet transfer. A sender first transmits a Request-to-Send (RTS), and the re-
ceiver responds with a Clear-to-Send (CTS). Then the sender sends the DATA and, finally,
the receiver completes the transaction with an Acknowledgment (ACK). Both RTS and
CTS contain the proposed duration of the data frame. Nodes located in the vicinity of the
sender and the receiver that overhear one or both of the RTS/CTS store the duration infor-
mation in a network allocation vector (NAV), and defer transmission for the proposed du-
ration. This is called virtual carrier sensing (VCS).
The IEEE 802.11 protocol uses a backoff mechanism to resolve contentions. Before
initiating transmission, the sender first waits for a short time to see if the channel is idle
(this “inter-frame spacing” is different for different kinds of frames). Then, the sender
chooses a random backoff interval from a range (0, CW) in which CW is the contention
window. The sender then decrements the backoff counter once every “slot time.” When
the backoff counter reaches 0, the sender transmits the frame. During this backoff stage, if
a node senses the channel as busy, it freezes the backoff counter. When the channel is
once again idle for a duration called DIFS (DCF Interframe Spacing), the node continues
counting down from its previous (frozen) value.
If there is no CTS forthcoming from the receiver (due to collision, etc.), the sender
doubles its CW, chooses a new backoff interval, and attempts retransmission. The con-
tention window is doubled upon each such event until it reaches a maximum threshold.
Upon successful delivery of a packet, the contention window is reset to CW.
We now consider the problem of adapting CSMA/CA and, in particular, 802.11 to the
directional regime. An obvious solution to the problem is to do exactly as in IEEE 802.11,
but simply send all of the RTS/CTS/DATA/ACK packets directionally. Unfortunately, this
presents a number of problems. We discuss some of these problems below. Problems with CSMA/CA When Beamforming Is Used. We present
examples of four kinds of problems due to directionality of transmission/reception. The
scenarios are taken from [8] and [9].
The first two examples are based on Figure 5.2. In the left-hand side of Figure 5.2, A
wants to send a packet to B, and C wants to send a packet to D. The RTS from A is sent
omnidirectionally or directionally to B, but is heard by C, and C is inhibited from sending
even though it can do so without interfering with the transmission from A to B. We term
this the directional exposed terminal.
In the right-hand side of Figure 5.2, suppose A is sending a packet to B after having ini-



Figure 5.2. Examples of when traditional CSMA/CA is insufficient when beamforming is em-
ployed. In the example on the left, termed “directional exposed terminal,” C is prevented from send-
ing when it can. In the example on the right, termed “loss in channel state,” there is a collision at D.

tiated an RTS“CTS exchange. Neither the RTS nor the CTS is heard by C, which proceeds
to initiate a transmission to D. The RTS“CTS exchange between C and D is directional
and not heard by A, which, after completing its transmission to B, now initiates a trans-
mission to E. The RTS from A to E interferes with the data being received by D from C.
We refer to this situation as loss in channel state by node A.
For the next two examples, we refer to Figure 5.3. The first of these examples is as fol-
lows. Assume all nodes in Figure 5.3 when idle, are receiving using an omnidirectional
beam that has an azimuthal gain of Go. Now, suppose B transmits a directional RTS to F,
and F responds with a directional CTS. Suppose node A is far enough from node F so as
to not be able to hear this CTS. B begins DATA transmission to F, both nodes pointing at
each other with gain Gd. Because B sends directionally, and assuming very low gain in the
opposite direction, A cannot sense this DATA transmission. While this is in progress, sup-
pose A wants to send to E. When it sends the RTS directionally toward E (and it does so
because it cannot sense anything), it interferes with the reception at F. This can happen
because beams of both F and A are pointed toward each other. In other words, sender and
receiver nodes with a combined gain of Gd + Go may be out of range of each other, but
within range with a combined range of 2 · Gd (note that Gd is by definition greater than
Go). We term this the directional hidden terminal problem.
For the final example, refer again to Figure 5.3. Suppose B initiates communication
with E and starts sending a DATA to E. Further suppose that C is on a null for this trans-
mission and so cannot hear these. While the B“E communication is ongoing, C wishes to
send a DATA packet to B, and so sends an RTS to B. Since B is beamformed in the direc-
tion of E, it does not receive the RTS and so does not respond with a CTS. Node C, upon



Figure 5.3. Figure to illustrate “directional hidden terminal” and “deafness” (refer to text)

not receiving the CTS, retransmits the RTS. This goes on until the RTS retranmission lim-
it is exceeded. This wastes network capacity by sending unproductive control packets.
Furthermore, C increases its backoff interval on each attempt, and thus, unfairness is in-
troduced. This problem has been termed deafness in [9].
In addition to all this, there are some aspects of CSMA/CA protocol design that do not
quite work when beamforming antennas are used. Consider the backoff scheme in IEEE
802.11, for example. This involves picking a random number of slots and counting down,
freezing the count whenever the channel is busy. This is straightforward when there is
only one beam that can be formed (omni), but is not so straightforward when beamform-
ing is possible (steered or switched). While backing off, what beam should the node
pick/form? Should it be omnidirectional, or should it continue to be beamformed in the
direction of the intended transmission? If the former, the node misses the activity in the
vicinity of the intended receiver. If the latter, then it may not be able to receive RTSs from
nodes in other directions.
Last but not least, there is the issue of determining the direction in which the beam
should be pointed to send to a target node or, in switched beams, which beam should be
The examples outlined are by no means the only problems. However, they should have
given the reader a flavor of the kinds of issues that researchers have grappled with in
adapting CSMA/CA to beamformed transmissions. We now present a survey of research
on solving these problems, under the informal umbrella of “directional CSMA/CA.” Directional CSMA/CA. The examples above indicate that the RTS/CTS
handshake as used in traditional CSMA/CA is insufficient to overcome the new “direc-
tional” hidden- and exposed-terminal problems. In general, as the number of nodes hear-
ing the RTS/CTS increases, the severity of the exposed-terminal problem increases, and
that of the hidden-terminal problem decreases (the reader should examine the above ex-
amples again to grasp this). Thus, one idea is to attempt to find an optimum point by ex-
ploring the various combinations of omnidirectional/directional RTS/CTS.
The other, largely orthogonal, approach to the problem is to introduce mechanisms that
explicitly try to reduce the exposed- or hidden-terminal problems. For instance, an ex-
posed terminal may violate the protocol rules and transmit anyway to reuse the space.
These ideas, or a combination thereof, form the underlying rationale behind many of
the schemes in the literature. A specific example is a simple scheme in which nodes send
omnidirectional RTS/CTS, but nodes never honor the NAV”that is, they always violate
the virtual carrier sensing”and the RTS/CTS is used merely to assist in the pointing of
antennas for the subsequent DATA/ACK exchange and for power control. This was sug-
gested as a simple baseline scheme in [8].


. 29
( 87 .)