<<

. 31
( 87 .)



>>

5.3 MEDIUM-ACCESS CONTROL




A B C




D
RTS(A->B) CTS(B->A)

RTS(C->D)

Figure 5.5. Heterogeneous transmit powers resulting from power control cause problems for
CSMA/CA. Nodes A and B reduce power when sending RTS/CTS, which is not heard by C. When
C transmits to a distant node D, it needs to use a high power, causing collision at B.



the hidden senders to back off. Rather, its utility is in calibrating the power level at which
the DATA is to be sent. Specifically, based on its current noise level, the receiver com-
putes the power P at which the DATA should be sent for it to be received successfully.
This power P is included as part of the APTS packet, which is itself sent at reduced power
based on the source™s noise level information sent as part of the RPTS packet.
The solution in [23] also uses busy tones to coordinate power control, but the tones
here are continuous. Two busy tones are used: a transmit busy tone, sent by an active
transmitter, and a receive busy tone, sent by an active receiver. Different power levels are
used for the tones by the transmitter and the receiver, and tuned appropriately.
Both [22] and [23] report significant performance gains from the respective methods
using simulation. A throughput improvement by a factor of two over nonpower-controlled
IEEE 802.11 is achieved using the mechanism in [22]. The approach of [23] is shown to
provide approximately twice the peak channel utilization when compared to a nonpower-
controlled dual busy tone technique, namely the one in [24].
Although the above solutions manage to avoid collisions, they require the use of a sec-
ond channel for busy tones. This implies a second transceiver since the busy tones and
transmission/reception may need to occur simultaneously. Thus, this is not possible with
the off-the-shelf 802.11 wireless cards, and, indeed, one might argue that with two chan-
nels and two transceivers, nonpower-controlled 802.11 might itself exhibit close to factor-
of-two performance gains. From a practical viewpoint, the problem that would be of most
interest is a power-controlled CSMA/CA with a single channel and transceiver. As far as
we know, this is an open problem. However, a trivial solution to this problem is to not ad-
dress the collisions, resolving them by means of backoffs and retransmissions. Our expe-
rience, reported in [8] and in other unpublished research, is that one can still get substan-
tial gains in performance.
Thus far, we have considered power control in the context of CSMA/CA. One of the
few works that addresses power control in the TDMA context is [25]. The authors present
a two-phase algorithm that searches for an admissible set of users in a slot, along with
154 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS


their transmission power. In the first phase, a scheduling algorithm is used to eliminate
“strong” or “primary” constraints”for example, a node cannot simultaneously transmit
and receive. In the second phase, a distributed algorithm is executed to control the admis-
sible set of powers that could be used by nodes scheduled in phase 1. As in the case of
TDMA with beamforming, power computation simply translates into a new set of con-
straints that need to be accommodated. In this case, the constraint is that the powers
should be such that the SINR at every receiver must be greater than a given threshold.

5.3.2.1 Power-Controlled Directional MAC. Although beam and power control
by themselves can improve spatial reuse considerably, it is when both are employed simul-
taneously that the full potential is realized. Figure 5.6 illustrates this very informally by
comparing the four combinations”no power or beamforming control, only power con-
trol, only beamforming, and both. Ignoring a number of details such as sidelobes, one can
take the ratio of the areas occupied by two schemes as a measure of the relative spatial
reuse. Suppose that a node wants to send to a node that is at half the range of its maximum
power (top left). With power control (top right), the relative area decreases by a factor of
r2/ (r/2)2 or four. With only beamforming and a beamwidth of 10 degrees (bottom left),
energy is redirected but the same energy is emanated. Assuming, and because of, r4 prop-
agation, the energy interferes with less area than without power control or beamforming
but still interferes significantly. Specifically, the range is (360/10)1/4. This gives a factor-
of-six improvement over no power control or beamforming, which is 50% better than with
only power control. When both power and beamforming control are used (bottom right),
the area occupied is approximately (10/360) · (r/2)2, or a reduction in the area by a fac-
tor of 144!
In other words, the additional gain of the antenna in the preferred direction allows us to




No power or Only
beamforming power
control control
r/2
Area = A
r
Area = A/4




Only Both power
10 degrees beamforming control and
beamforming


Area = A/44
Area = A/6

Figure 5.6. A rough comparison of relative interference reduction potential with power control,
beamforming, and both together. Assuming a beamwidth of 10 degrees and r4 propagation, and
many simplifying assumptions, the area of interference is reduced by a factor of four with power
control only, a factor of six with beamforming only, and a dramatic factor of 144 with both together.
155
5.3 MEDIUM-ACCESS CONTROL


reduce the power significantly. The savings depends upon the antenna gain”higher the
gain, the more the savings. It is not surprising that the combination of power control and
antenna gains is better than one or the other alone. What is surprising, and apparent from
the above, is the extent of this difference. When combined, power control and beamform-
ing are much more than the sum of the parts.
Figure 5.6 illustrates the relative potential for capacity enhancement. In order to har-
ness this potential, protocols have to simultaneously control beamforming and power. One
obviously cannot expect to match the theoretical potential, but the question of how much
difference the incorporation of power control in beamforming makes merits attention. We
now examine this further, and survey results on the comparative performance of beam-
forming with and without power control. We focus on two representative works, [8] and
[26], targeting the question: given that beamforming is already done, what is the effect of
doing power control in conjuction with it?
In [8], a simulation model of a 40 node static ad hoc network equipped with direction-
al antennas, and CSMA/CA, MAC, and link-state routing are used to study the perfor-
mance gains due to beamforming. The MAC protocol, called “Aggressive Collision
Avoidance,” sends RTS/CTS omnidirectionally, but virtual carrier sense is always violat-
ed; that is, the NAV is never honored. Idealized antenna patterns with varying gains are
used”see [8] for details. Figure 5.7 shows the performance benefits with and without
power control for various gains.
Because of the large packet buffers used, packets are delayed rather than dropped, and,
therefore, the delay metric is a better indicator of performance here [8]. We note that with-
out power control (Figure 5.7, top) there is a factor of two to three reduction in delay,
whereas with power control (Figure 5.7, bottom), there is a factor of about 28 reduction in
delay.
We now summarize the results from [26]. As mentioned earlier, in the protocol pro-
posed here, RTS and CTS are sent using an omnidirectional antenna, and a short NAV is
used to mitigate the exposed-terminal problem. In this context, the authors study two
power control schemes”global and local. In both cases, power control is applied only to
the DATA/ACK packets. In global power control (GPC), the DATA/ACK transmitter pow-
er is reduced to the same level for all nodes, to a value Pt, where Pt is the transmitter
power of RTS/CTS. In the local power control (LPC) scheme, the transmit power is set for
each transmission so that the SNR across the link is a predetermined value. This is done
by using the values of the received RTS/CTS power levels to compute how much power
reduction is required.
The global and local power control schemes were compared with no power control
(NPC) using a discrete event simulation on a 15 by 15 grid of 225 nodes. It was seen that
the normalized system capacity increase over plain 802.11 was about 260% with NPC,
about 475% with GPC, and about 525% with LPC. Thus, the addition of power control
yields significant benefits. The paper concluded that reduction in power is a “key factor”
in improving the capacity of an ad hoc network with smart antennas.
In sum, power control and beamforming are highly synergistic. Their use together far
outperforms the sum of the individual gains achieved by use of one or the other by itself.
Doing this, however, requires that we address the union of the MAC-layer issues present-
ed in the exploitation of power and beamforming control. We believe that this should be a
highly interesting and fruitful research area in the years to come.
156 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS


300
™Gain=0™
™Gain=10™
™Gain=14™
250 ™Gain=20™
™Gain=26™

200
Delay-ms


150


100


50


0
10 20 30 40 50 60 70 80 90 100 110 120
Density

Delay-ms vs Density for various Gain; 40 nodes; NumAnt=1
Delay-ms vs Density for various Gain; 40 nodes; NumAnt=1

300 Gain=0
™Gain=0™
™Gain=10™
™Gain=10™
™Gain=14™
™Gain=14™
250 ™Gain=20™
250 ™Gain=20™
™Gain=26™
™Gain=26™
200
200
Delay-ms
Delay-ms




150
150


100
100


50
50


0
0 10 20 30 40 50 60 70 80 90 100 110 120
10 20 30 40 50 60 70 80 90 100 110 120
Density
Density
Delay-ms vs Density for various Gain; 40 nodes; NumAnt=1

Figure 5.7. Performance of beamforming without (top) and with (bottom) power control: 40 node
stationary ad hoc network with steered beams.


5.4 NEIGHBOR DISCOVERY: TOPOLOGY CONTROL

In the previous section, we studied the issues related to the spatial reuse of the spectrum.
In this section, we consider the other dimension, namely, communication range, and, relat-
edly, connectivity control opportunities provided by antenna beam and power control.
The goal of neighbor discovery at each node is to determine the set of other nodes
within direct communication range (within one hop). Neighbor discovery is an inherent
157
5.4 NEIGHBOR DISCOVERY: TOPOLOGY CONTROL


part of most proactive protocols and uses a technique called beaconing to advertise itself
and discover other nodes. In some reactive protocols, there is no explicit neighbor discov-
ery. However, the process of building on-demand routes using route queries essentially
discovers neighbors (that are in many cases cached for later use). One might therefore
consider neighbor discovery as an implicit part of reactive protocols. Our description in
this section is in the context of a proactive protocol, but we note that many of the ideas
and issues are applicable in a modified form to reactive protocols as well.
The set of potential neighbors depends upon “uncontrollable” factors such as mobility,
weather, noise, interference, and so on, as well as “controllable” ones such as transmit
power and antenna direction. For instance, increasing the transmit power of beacons typi-
cally increases the number of neighbors. Similarly, depending upon whether the beacon-
ing employs beamforming at one or both ends, different neighbors can be discovered.
The topology of the network is a union of Si, where Si is the set of links discovered by a
node i. More generally, the topology of a network is the set of communication links used
explicitly or implicitly by a routing mechanism [27]. Controlling the neighborhood of
each node using power and beamforming obviously also controls the topology. This leads
us to the notion of topology control, which is the problem of controlling the topology of
the network to the desired form by changing the radio parameters; in this chapter, we only
consider transmit power and antenna beam.
Why do we need topology control? Simply because the wrong topology can consider-
ably reduce the effective capacity, increase the latency, and reduce the robustness of the
network. For instance, if the topology is too sparse, there is a danger of loss in connectivi-
ty, and higher chances of congestion at a single node. On the other hand, a dense topology
often implies reduced spatial reuse and increased battery consumption. Further, routing
protocols might incur too much overhead in maintaining the topology, and this may over-
whelm the routing process.
We observe that topology control can by accomplished in two ways:

1. Restrict the parameters to physically discover only some of the potential neighbors.
We call this physical topology control.
2. Given a set of discovered neighbors, filter or refer only a subset of these neighbors
to the routing process. We call this routing topology control.

The first use of the term topology control was as routing topology control [28] in the

<<

. 31
( 87 .)



>>