<<

. 33
( 87 .)



>>

1



0.8



0.6
Tput




0.4



0.2
™algo=GIFT™
™algo=NoTC™
™algo=LINT™
0
4 6 8 10 12 14
Density

Tput vs Density for various nbrMax; 60 nodes; Mobility=0.001, VC=N, LST=T




1



0.8



0.6
Delay




0.4



0.2
™algo=GIFT™
™algo=NoTC™
™algo=LINT™
0
4 6 8 10 12 14
Density

Delay vs Density for various nbrMax; 60 nodes; Mobility=0.001, VC=N, LST=T

Figure 5.9. A comparison of a decentralized algorithm (GIFT) (top) and a distributed algorithm
(LINT) (bottom) with no topology control (NoTC) in a 60 node mobile ad hoc network.
165
5.4 NEIGHBOR DISCOVERY: TOPOLOGY CONTROL


OO neighbors
Establishing DD neighbors using
S R
multihop RTS


CTS
DO neighbors
S R MHRTS

MHRTS
MHRTS
DD neighbors
MHRTS
S R



Figure 5.10. Left: OO, DO, and DD neighbors. Solid lines indicate transmitter beamforming,
dashed lines indicate receiver beamforming. DO has longer range than OO, and DD has longer
range than DO. Right: Illustration of multihop RTS for establishing DD neighbors.



ing traditional beaconing. Doing OD neighbor discovery is harder than doing DO, and
does not yield additional range or other benefits. Thus, we shall examine only two types
in greater detail here: DO and DD. Figure 5.10 (left) illustrates OO, DO, and DD neigh-
bors.
We first consider DO discovery. A key issue here is to know which direction a node A
must point to in order to send to a node B. There are two ways of doing this. If B is
equipped with a smart antenna, it can eavesdrop on A™s transmissions and compute the an-
gle of arrival (AOA). Another method is to use relayed position information. If a link-state
protocol is used, such position information becomes automatically available if current po-
sition is included in each update. Alternatively, one may use efficient position dissemina-
tion techniques, as in [38, 39]. Using one™s own position and the neighbor™s position, the
direction is easily computed. Assume that A knows the direction of B using one of these or
other techniques. Then DO discovery is fairly simple: A beamforms towards B and sends a
beacon. We assume that nodes are receiving in omnidirectional mode when not active.
Thus, if the gain is sufficient, then B receives the beacon. The beacon contains A™s posi-
tion. B uses that information to beamform toward A and send a beacon, enabling DO
neighbor discovery.
DD discovery is more complicated, especially in a system that uses CSMA/CA at the
MAC layer. In addition to the direction issue, which may be addressed in the same manner
as for DO, a problem here is that the receiver must be beamformed in the direction of the
sender at the precise time the beacon is sent. This is a problem not just for discovery, but
for every single data packet transfer, although, in a TDMA system, scheduling the point-
ing could solve the data transfer problem.
Suppose, however, that the network is connected using links that are DO or OO. In that
case, a rendezvous packet may be sent multihop from A to B. The rendezvous packet con-
tains A™s position and the exact time at which A expects B to point toward A based on the
position. Upon receipt of the rendezvous packet, and at the scheduled time, A and B can
point to each other and try sending beacons to see if they can be DD neighbors.
In a CSMA/CA-based system, a multihop RTS may be used in place of a separate ren-
dezvous packet. That is, when the beacon reaches the MAC layer, the MAC protocol de-
termines that this is not a DO or OO neighbor and source-routes the RTS multihop to the
166 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS


receiver. During this time, A remains beamformed in the direction of B. Upon receipt of
the RTS, which contains A™s position, B beamforms toward A and sends a CTS. If they can
be DD neighbors, then the CTS will reach A and A can directly send the DATA (in this
case the beacon). Such a multihop RTS scheme is described in [9], and further implemen-
tation details may be found there.
Clearly, this approach will only work if the network is connected using only DO and
OO links. What if it is not? This is a hard problem. However, if another physical layer pa-
rameter, namely spreading gain, were controllable, one could trade data rate for increased
processing gain (and, hence, range) just for the RTS, and use that to bootstrap the point-
ing.
What do DO and DD discovery give us? They essentially provide range extension,
which, in turn, provides richer connectivity and a smaller average number of hops. Both
of these are beneficial for the performance, but not under all circumstances. In the re-
mainder of this section, we study some performance implications of range extension using
beamforming antennas.
In [9] two protocols called DMAC and MMAC are compared. DMAC is a
CSMA/CA-based protocol that uses a directional NAV table, as described in Section
5.3.1.2. DMAC only implements OO and DO modes. MMAC is an enhancement of
DMAC with multihop RTS, which enables the DD mode. Thus, in DMAC, a packet may
have to travel multiple hops, each of which involves an RTS/CTS/DATA/ACK exchange,
whereas in MMAC, the packet may travel only one hop which involves a single
MHRTS/CTS/DATA/ACK exchange. Using beamwidth of 45 degrees and a DD range
of about 900 meters, compared to 250 meters for OO and a 25 node random network
with random flows, the simulation results show that MMAC outperforms DMAC by a
factor of up to 2.5. This clearly indicates the power of longer range transmissions to in-
crease the capacity. MMAC also reduces the end-to-end delay by about 15%. The num-
ber is not very high because the queues saturate and packets are dropped (delay is only
calculated for delivered packets). Further, the higher failure probability of multihop RTS
in MMAC causes more timeouts and retransmissions, thereby offsetting some of the re-
duction in average packet latency.
In [8], the effect of range extension is studied using a model of switched beam anten-
nas. A beacon is sent out on each of K beams. Since these beacons travel farther than omni
beacons, longer-range neighbors and a richer topology are possible. The comparison is be-
tween OO- and DO-based topologies. The number of beams K is 12. A 40 node randomly
placed static ad hoc network (see [8]) is used. The simulation results comparing the per-
formance for different beam gains (including omnidirectional as gain of 0) using a realis-
tic model in OPNET are in Figure 5.11.
The relative performance appears to depend in a fairly complex manner on the density.
Therefore, let us consider low, medium, and high densities separately.
At low densities, the throughput with beamforming antennas is far higher. For density
8, using a 20 dBi switched-beam antenna yields 118% better throughput and a factor of 20
reduction in delay.
For density 4 nodes/sq mile, a partitioned network results when omnidirectional anten-
nas are used, but connected with beamforming antennas, as illustrated in Figure 5.12. For
very sparse deployments, use of omnidirectional antennas leaves the network highly parti-
tioned (a), whereas use of directional neighbor discovery with 10 dBi beams (b) and 20
dBi beams (c) provides good connectivity and commensurate performance. In such a sce-
nario, the longer range provided by beamforming is simply indispensable to the connec-
167
5.4 NEIGHBOR DISCOVERY: TOPOLOGY CONTROL


100



80



60
Tput%




40


™Gain=0™
20 ™Gain=10™
™Gain=14™
™Gain=20™
™Gain=26™
0
0 5 10 15 20 25 30 35 40 45 50
Density

Tput% vs Density for various gains; 40 nodes; NumAnt=12


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




100




50




0
0 5 10 15 20 25 30 35 40 45 50
Density

Delay-ms vs Density for various gains; 40 nodes; NumAnt=12

Figure 5.11. Comparision between using OO- and DO-based topologies. The “gain=0” indicates
performance of OO topology. Performance of DO topologies with different values of transmitter
beamforming gain are also shown. A 40 node stationary ad hoc network with switched beams and
power control is modeled.
168 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS




(a)




(b)

Figure 5.12. (a) Comparison of topologies resulting from omnidirectional antennas. (b) 10 dBi
beams.
169
5.4 NEIGHBOR DISCOVERY: TOPOLOGY CONTROL




(c)

Figure 5.12. (c) 20 dBi beams.



tivity survivability of the network. We note that each link depicted is a directional link
and, hence, unlike the omnidirectional case, a high average degree is not necessarily bad.
The performance drops at middle densities before rising again. This reflects a playing
out of the interference versus range forces. That is, as density increases, the interference
increases (which is bad) but the average number of hops decreases (which is good). At
middle densities, the beneficial effects of the number of hops probably has not manifested
itself, whereas the interference effects are dominant.
Now consider higher densities. The throughput is about the same or worse with beam-

<<

. 33
( 87 .)



>>