<<

. 30
( 87 .)



>>

Ideas for determining the steering direction or beam selection include using the posi-
tions of the target node and reference node to derive the angle, using angle-of-arrival
(AOA) facilities in steered (smart/array) antennas, etc. Directional MACs are generally in-
different as to which method is used, as long as the relative angle is obtained with reason-
able accuracy. Note that it is the RTS direction that poses a challenging problem”the
CTS/DATA/ACK can use position information placed in, or the angle-of-arrival of, the
RTS/CTS/DATA (respectively) for determining the sending direction. To determine the
RTS direction in the first place, one may use angle-of- arrival from overheard packets, ob-
tain position information from overheard packets or (omnidirectional) beacons specifical-
ly used for this purpose, use piggybacked position information in routing control packets,
148 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS


or simply send the RTS omnidirectionally. Each of these techniques have their advantages
and disadvantages. In the ensuing discussion, we focus more on the spatial reuse qualities
of various schemes, treating the mechanics of direction determination as a largely orthog-
onal issue.
With this background in mind, let us now examine the ideas studied in the literature.
We first consider the theme of omnidirectional/directional RTS/CTS, and then consider
mechanisms for reducing collisions and increasing spatial reuse.
In [10], a MAC protocol is suggested for an ad hoc network in which each node has
multiple directional antennas (functionally equivalent to a switched-beam system for pro-
tocol purposes) with a single transceiver. The idea is to execute the 802.11 protocol al-
most verbatim, but on a per-antenna basis. Thus, for instance, if a CTS is heard only on
one antenna, an RTS may be sent out all other antennas except that one. Two schemes are
described, both of which use directional DATA/ACK and omnidirectional CTS, but differ
in the choice of how the RTS is sent”omnidirectionally or directionally. Simulations
done with a mesh topology show, as expected, a throughput improvement over 802.11
with omnidirectional antennas. The relative performance of the two schemes is topology
dependent. Although [10] was one of the early works on the problem and really kick-start-
ed this field, it makes a few assumptions that were later found to be unrealistic. For in-
stance, it was assumed that the node can identify the antenna through which a packet was
received, and that the omnidirectional antenna range is equal to the directional range.
The omnidirectional versus directional issue is examined more closely in [11]. Here,
each node is assumed to have a switched-beam antenna using a beamforming matrix. Two
schemes are compared. In both, CTS, DATA, and ACK are sent directionally. The differ-
ence is in the RTS”in one, called Di-RTS, it is sent directionally, and in the other, called
omni-RTS it is sent omnidirectionally. Simulations reported show that the Di-RTS scheme
outperforms the omni-RTS scheme significantly in all cases. The authors suggest that this
is because the directional RTSs generate less interference. Another way of looking at this is
that the exposed terminal problem affects throughput more than the hidden-terminal one.
Both RTS and CTS are sent omnidirectionally in the scheme in [26]. The authors con-
sider an ad hoc network with steered beam antennas. In order to alleviate the exposed-ter-
minal problem caused by the omnidirectionality of the RTS and CTS, the traditional back-
off due to virtual carrier sensing is violated by using a shorter NAV for nodes not wanting
to send to the source or destination of an ongoing communication. Thus, if a node C want-
ing to send to D hears an RTS from A to B, it will defer until the CTS from B to A is com-
plete, and then will proceed to send an RTS to D even while A is sending DATA to B.
Nodes A and B lock themselves into a tight directional transmit/receive link during data
transfer and are largely immune to the communication between C and D. Power control is
also used to reduce the signature of the DATA/ACK. Performance improvements over
802.11 of up to 130% in a 25 node grid and up to 260% in a 225 node grid are reported,
even without power control. The power control aspect will be addressed in Section
5.3.2.1.
Omnidirectional RTS/CTS has the advantage that one need not know the position of
the intended target. However, it cannot exploit the range advantage of directional anten-
nas, that is, two nodes can talk with each other only when one of them beamforms to get
the additional gain.
Unlike in omnidirectional networks, hearing an RTS/CTS does not always mean that it
is necessary to defer. On the other hand, not deferring at all is obviously going to lead to
collisions. Clearly, it is necessary to selectively defer depending upon the relative direc-
149
5.3 MEDIUM-ACCESS CONTROL


tions of the ongoing and intended transmissions. Such selective virtual carrier sensing us-
ing a directional NAV (or DNAV) was proposed in [12] and, independently, in [9]. The key
idea is that if a node receives an RTS or CTS from a certain direction, then it needs to de-
fer for only those transmissions that are in (and around) that direction. This is implement-
ed by augmenting the NAV table entries with a direction field, and deferring only if the in-
tended direction is within a threshold (for error margin) of that direction.
The scheme using such a DNAV in [12] improves network capacity by a factor of three
to four over 802.11 for a 100 node network. This scheme uses “cached directions” based
on angle-of-arrival information from overheard packets. This is used to send the RTS di-
rectionally. If the cache is empty, or if more than four RTS transmissions do not elicit a re-
sponse, omnidirectional RTS is used. A hallmark of this work is the very comprehensive
physical layer and antenna modeling that provides a high level of confidence in the re-
sults. The performance results in [9] indicate a throughput increase by a factor of about 2
over the traditional IEEE 802.11, but the antenna gains used were only 10 dBi. An inter-
esting insight, pointed out in [9], is that if the flows are “aligned,” directional transmis-
sions perform much worse since packets from the same flow contend along the transmis-
sion direction.
There are a number of other works that consider directional CSMA/CA. In [13], sig-
nal strength information is used in lieu of position information to determine the angles.
The novelty in [14] is in the use of an “Angle-SINR” table that keeps track of the com-
muniation events and their directionality at any point in time. In [9], multihop RTSs are
proposed for sending DATA to a receiver when both sender and receiver need to beam-
form toward each other for successful data transfer. Finally, a host of issues in direc-
tional CSMA/CA, including a comparison of switched and steered beams is presented in
[8].
Are there any lessons to be learned from the research, and is there a convergence in
thinking? Although this is still a very young field, some insights are emerging. First, there
is a bunch of “low-hanging fruit” available for the taking”that is, even with simple mod-
ifications to CSMA/CA and moderate gain beams a capacity improvement of two to four
is obtained. More sophisticated schemes should be able to increase this further. Second, as
many packets should be sent directionally as possible (unless lack of position or other
means forces one to use omnidirectional RTS). Third, a directional NAV and/or a short
NAV is a good idea for exploiting the spatial reuse. Finally, and this will be discussed
more in Section 5.3.2.1, augmenting beamforming with power control leads to a signifi-
cant difference in performance.

5.3.1.3 Directional TDMA. An alternative approach to channel access in ad hoc net-
works is the fixed, or contention-free approach. The most studied manifestation of this ap-
proach in ad hoc networks is Time Division Multiple Access (TDMA). Although TDMA
has not been studied as much as CSMA/CA (at least in recent times), there is no evidence
that this is due to any inherent demerits2 of TDMA. Rather, the relative simplicity of
CSMA/CA and its adaptation by the IEEE 802.11 subcommittee is the likely cause of this
relative imbalance in research.
In TDMA, time is divided into repeating frames. Each frame is divided into time slots,

2
Some demerits are sensitivity to topological change and unsuitability for highly bursty traffic. However, these
can be solved, and on the positive side it provides bounded delays and better utilization in general. TDMA ver-
sus CSMA/CA for ad hoc networks is an interesting topic, but beyond the focus of this chapter.
150 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS


which are at least approximately synchronized. Transmissions start and end within slots.
In a sufficiently spread out ad hoc network, slots can be reused by (adequately distant)
nodes. Some researchers (e.g., [20]) refer to this specifically as spatial reuse TDMA. In
the reminder of this discussion, we use TDMA as a synonymn for spatial reuse TDMA.
The use of TDMA in ad hoc networks with omnidirectional antennas has been exten-
sively studied. This includes theoretical studies based on a graph-coloring paradigm [15,
16, 17], and distributed procedures [18, 19]. Slots can be assigned to nodes”called
broadcast scheduling (which is more suitable for broadcast packets), or link scheduling
(which is more suitable for unicast packets). In both cases, the activations (assignments of
transmissions to a slot) must be made in a conflict-free manner: that is, the activations
must adhere to a set of constraints. An example of a constraint is “Do not schedule con-
current transmissions at two nodes that are within two hops of each other.” Another exam-
ple is “With all scheduled transmissions active, the signal-to-interference-noise ratio
(SINR) at all receivers must be above a certain threshold.”
The use of beamforming antennas in TDMA poses problems that are completely differ-
ent than with CSMA/CA. This is a consequence of the entirely different approach used for
resolving contention”while CSMA/CA does this “on the fly” based on overheard control
packets, TDMA does it apriori by coordinated decisions based on constraint information.
In particular, the deafness and loss-in-state types of problems cease to be an issue. Al-
though hidden and exposed terminals exist, the problem is different since this is resolved
while setting up the schedule (and factored in as part of the “constraints”).
With beamforming antennas, what changes is the nature of constraints for concurrent
transmissions. For instance, consider Figure 5.4. In the figure, two links are constrained if
they are adjacent, or if there is a line from a transmitter to a receiver. For instance, in Fig-
ure 5.4 (left) A B and D E are constrained, but A B and E F are not. Suppose
all horizontal and vertical links need to be activated. The figure on the left shows interfer-
ence constraints when omnidirectional tranmsissions are used and the figure on the right
shows constraints when highly directional transmissions are used. With omnidirectional
transmissions (left), many more links are constrained than with highly directional trans-
missions (right).
When scheduling, we need to ensure that there is no constraint line between a transmit-
ter and its intended receiver. When omnidirectional antennas are used, only two links can
be concurrently activated [Figure 5.4 (left)], namely A B and G H. However, with
directional communications [Figure 5.4 (right)], four links”A B, D E, G H, and
C F”can be concurrently activated, giving a 100% increase in capacity.
As with directional CSMA/CA, obtaining the angle at which to transmit can be done
using position information or angle of arrival. This may be done using specialized control
packets or using a packet in the previous slot to get the updated position/angle of the tar-
get. Schemes discussed here are largely orthogonal to the specific mechanism for obtain-
ing sending direction.
Given an existing omnidirectional TDMA design, and thus an extant vehicle for trans-
lating constraints into dynamic schedules, it appears incrementally less complex to accom-
modate directional antennas. What is needed is to determine the new set of constraints ac-
curately. We discuss ideas to do this by describing two representative works [20, 21].
In [20], the authors study the performance of ad hoc networks with a TDMA MAC and
two kinds of beamforming antennas”beam steering and adaptive beamforming. The al-
gorithm used is a centralized one that uses two constraints: (1) in each slot, links are acti-
151
5.3 MEDIUM-ACCESS CONTROL


A B C A B C




D E F D E F




H
G I G H I


Figure 5.4. Constraints and activated links for a network with omnidirectional (left) and highly di-
rectional (right) beamforming. The reduction in constraints (indicated by solid or dashed lines) in
the directional case allows four links to be simultaneously activated compared to two in the omnidi-
rectional case. Activated links are shown as bold arrows.


vated such that the SINR is above a certain threshold; (2) a node can either transmit or re-
ceive one packet in a slot. The difference between directional and omnidirectional anten-
nas is mostly found in (1). With beamforming, interference is significantly reduced at
many nodes, thereby increasing SINR and allowing more simultaneous activations. Simu-
lation results show that with beam steering for transmitting and adaptive beamforming for
receiving, a capacity gain of about 980% over omnidirectional antennas is obtained.
Although this order-of-magnitude improvement is impressive, the algorithm used is
centralized and is therefore ill-suited for ad hoc networks. In [21], a distributed algorithm
is given that only uses two-hop information for scheduling, thereby making it scalable, yet
implementable for mobile ad hoc networks. The beamforming antenna constraints are ac-
commodated by using the concept of an angular group. An angular group corresponds to
the coverage of a directional beam from a node and is used to determine conflicts. In par-
ticular, only activations resulting in disjoint angular groups are scheduled in the same slot.
Each node is able to determine this using two-hop information exchanged by means of
broadcast messages that use the omnidirectional mode on common control slots. The pa-
per describes a simulation comparison with UxDMA [17], which describes a centralized
heuristic for scheduling and shows significant performance gains.

5.3.2 Power-Controlled MAC
Traditional versions of CSMA/CA, including IEEE 802.11, FAMA, MACAW, and so on,
assume that all nodes transmit all packets with the same power. However, this does not
fully exploit the potential for spatial reuse. Spatial reuse using power control is possible at
two levels: first, each node can be assigned a different maximum power that it must not
exceed, but all packets from that node get sent with this power; second, within a given
maximum power, a node modulates the individual powers of each packet”including con-
trol and DATA”so as to cause the least interference.
It is the second topic that is the subject of this section”the first problem of picking the
right maximum power is addressed later in Section 5.4. We note that one can be done in-
dependently of the other and have their individual benefits.
We primarily consider CSMA/CA MACs here because, as with beamforming, most of
152 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS


the research has been done in this context. Further, we assume that all nodes only use om-
nidirectional transmissions. The combination of directional antennas and power control
will be considered in Section 5.3.2.1.
A simple idea is to send the RTS and CTS at the maximum power and, using their re-
ceived signal strengths, reduce the power of the DATA and ACK to the minimum required.
However, this does not affect spatial reuse because the number of other nodes that defer
based on the RTS and CTS is not reduced, and thus, there is no improvement in spectral
reuse.3 Thus, in order to obtain spatial reuse we need to send the RTS and CTS also at a
reduced power. Ideally, this power should be just enough to reach the neighbors, and
therefore might need to be different for different node pairs.
Unfortunately, CSMA/CA is inherently incompatible with such an approach. To see
why, consider the example illustrated in Figure 5.5. Consider two nodes A and B that are
close to each other, and suppose that A wishes to send to B. The CTS from B to A uses a
(low) power, say P1, which is less than the maximum possible power Pmax. Now, suppose
another node C that cannot hear the RTS/CTS exchange between A and B wishes to send
to a distant node D such that it has to use Pmax. If B is within range of C with Pmax, then
the RTS and the DATA from C to D will collide with the DATA from A to B.
In other words, the RTS/CTS exchange does not prevent hidden-terminal problems
when heterogenous power levels are used. In general, the control and data packets in a
CSMA/CA regime must be transmitted with the largest power that any node can use [22]
in order to guarantee collision-free floor acquisition. However, this brings us back to the
original problem”sending only RTS/CTSs at the maximum power yields little additional
benefit over no power control.
This dilemma has been addressed in [22, 23]. Both solutions make use of busy tones
for virtual carrier sensing, and utilize the RTS/CTS more as a way of negotiating the cor-
rect power level for DATA. In a way, this is similar to the violation of the virtual carrier
sensing described in the context of beamforming in Section 5.3.1.2. We describe the solu-
tion below, based on [22], called Power Controlled Multiple Access (PCMA).
In PCMA, collision avoidance is generalized to power control. Unlike the “on/off ”
model of conventional CSMA/CA, PCMA uses a “bounded power” model using two main
mechanisms:

1. A Request-Power-to-Send (RPTS) and Acceptable-Power-to-Send (APTS) hand-
shake used to determine the minimum power that will result in a succesful transmis-
sion. The RPTS/APTS transmission occurs in the data channel.
2. Each active receiver advertises its noise tolerance, given its current received signal
and noise levels. This is done using pulses in the busy tone channel. The strength of
the pulse indicates the tolerance to additional noise.

A sender node continuously monitors the busy tone channel to determine its power
bound by measuring the maximum power received on the busy tone channel over a thresh-
old time window. Then, using a backoff similar (but not identical) to traditional 802.11,
the sender transmits an RPTS at a power level slightly below the bounded level.
Unlike the traditional RTS/CTS handshake, the RPTS/APTS handshake does not force

3
In practice, depending upon the carrier sense threshold, one may see a slight improvement because nodes that
backed off due to sensing the DATA/ACK may now be free to transmit.
153

<<

. 30
( 87 .)



>>