Directional Antenna for Multipath Ad Hoc Routing

Hamid Gharavi and Bin Hu

National Institute of Standards and Technology

100 Bureau Drive, Stop 8920, Gaithersburg, MD 20899-8920, USA

E-mail: [gharavi, bhu]@nist.gov

Abstract— Multipath routing can be effectively used to maximize the utilization of network resources for real-time traffic. In

mobile ad-hoc network environments, this approach can suffer

from co-channel interference due to the simultaneous transmission of packets via multiple routes. In this paper, by exploiting

the directionality of directional antennas, a Directional Dynamic

Source Routing (DDSR)-based Multipath routing protocol is proposed for mobile wireless ad hoc networks. Three metrics are

considered in the route discovery process in order to select the

best multiple routes. These are hop count, beam overlaps, and

the number of joint nodes between the different routes. The proposed directional routing protocol has shown to be capable of minimizing inter-path and intra-path interference, hence significantly

improving the system throughput performance for simultaneous

transmission of multimedia information over multiple routes.

Index Terms—Ad hoc networks, routing protocols, DSR, directional antennas, directional routing, multipath routing.

I. INTRODUCTION

The major obstacle in supporting real-time traffic for

MANET is the long delays associated with frequent route

changes due to the dynamically changing network topology.

This includes latency in detecting a link loss, as well as the

time needed to discover a new route. Multipath routing has

been shown to be an effective approach to reduce the blocking

capabilities for multimedia traffic. This approach has received

considerable attention in recent years [1], [2], [3], [4], [5], [6],

[7], [8]. However, in contrast to wired IP networks, in mobile ad-hoc network environments, multiple routing protocols

can suffer from co-channel interference due to the simultaneous transmission of packets via multiple routes. This is mainly

due to the fact that in such environments, nodes in different

routes are normally within interference range of each other. The

suppression of interference between nodes in different routes

(inter-path interference) has been considered previously, using a

multi-channel approach [6]. In this approach, omni-directional

antenna was applied. Alternatively, by using directional antenna it is possible to suppress inter-path and intra-path interferences for multiple path routing and single path routing, respectively.

For single path routing, smart antenna techniques have been

extensively investigated in order to improve the achievable performance and system capacity. They are capable of providing

spatial reuse, longer ranges, interference suppression, and other

beneficial features [9], [10], [11], [12]. In [9], a brief overview

of smart antenna techniques was provided and the issues that

arose when applying these techniques in ad hoc networks were

then described. Yi et al. [10] provided a theoretical framework

to understand how much capacity improvement can be achieved

using directional antennas. Aimed at developing a complete

ad hoc networking system with directional antennas, including

the unique challenge of real-life prototype development and experimentation, Ramanathan [11] proposed utilizing directional

antennas for ad hoc networking (UDAAN). Based on neighbor

discovery [11], Choudhury [12] proposed MultiHop RTS MAC

(MMAC), which uses multihop RTSs to establish links between

distant nodes, and then transmit CTS, DATA, and ACK over a

single hop. Takai proposed a novel carrier sensing mechanism

called Directional Virtual Carrier Sensing (DVCS) for wireless

communication using directional antennas in [13], which only

needs information on Angle of Arrival (AOA) and antenna gain

for each signal from the underlying physical device. Along a

different avenue, much attention has also been paid to exploiting the spatial diversity of antenna arrays. Park [14] designed

a novel MAC protocol, Mitigating Interference using Multiple Antennas with Antenna Selection (MIMA/AS-MAC), for

MIMO aided ad hoc wireless networks. The authors in [7]

did a comparative study on the performance of multipath routing using omni-directional and directional antenna. The simulation results in [7] showed that directional antenna is capable of providing significant improvement to the performance of

multipath routing. However, the employed directional antennabased multipath routing protocol did not aim at suppressing the

inter-path and intra-path interferences. In this paper we present

a DDSR-based multipath routing protocol for wireless ad-hoc

networks by exploiting the directionality of directional antennas to suppress both inter-path and intra-path interferences.

This paper is organized as follows: In Section II, after a brief

introduction to the DSR routing protocol, we propose a DDSRbased multipath routing protocol. In Section III the attainable

performance of the proposed DDSR-based multipath routing

protocol is investigated comparatively with other routing protocols. Finally, we offer our conclusions in Section IV.

II. DIRECTIONAL DSR-BASED MULTIPATH ROUTING

PROTOCOL

In this section, DDSR-based multipath routing protocol invoked for wireless ad hoc networks is described. In this approach, multiple paths from the source node to the destination

node are selected according to hop count, overlap count and the

number of joint nodes between the different routes.

US Government work not subject to copyright 1

Authorized licensed use limited to: NIST Researchers. Downloaded on February 19, 2009 at 08:51 from IEEE Xplore. Restrictions apply.
DSR [15] is a source-initiated on-demand routing protocols,

where complete hop-by-hop routes are stored in route cache of

each node. When a source node attempts to send a data packet

to an unknown destination, it initiates a route discovery process

to find routes to the destination node. In a route discovery process, Route Request (RREQ) packets and Route Reply (RREP)

packets are used to set up the routes from the source node to

the destination node. Once the source node finds routes to the

destination, it inserts the source route to the data packets and

send them out. If a link break occurs while the route is active,

Route Error (RERR) messages are generated. When a RRER is

received, the receiving node removes the hop in error from its

route cache and truncates all routes containing this hop [15].

A. Route Discovery

Node D

Node C

Node G Node H

Node I

Node E Node F

Node A

Node B

Node J

2β

α

Fig. 1. An example where the beam of A→E does not overlap with the beam

of D→F, since we have α>β.

We consider overlap count as an important metric in the proposed DDSR-based multipath routing protocol. This is based

on the number of overlaps among beams over multiple paths

in the route discovery process, so that multiple routes with the

fewest overlaps can be selected. As shown in Fig. 1, when directional antennas are employed, the transmit beam of A→E

does not overlap with the receive beam of D→F. This indicates

that the transmission from node A to node E does not impact

node D. By contrast, the transmit beam of A→B overlaps with

the receive beam of D→C, meaning that the transmission from

node A to node B interferes with node D. Note that in a wireless multi-hop network, the interference from the nodes hops

away may degrade the throughput greatly [16], [17]. Hence,

in this case the route of A→E→F→D is better than that of

A→B→C→D.

In the proposed routing protocol, if the angle between A→B

and A→D is less than a threshold β while the angle between

D→C and D→A is also less than the threshold β, they overlap

and hence interfere with each other. Therefore, in order to prevent any overlap, a sharp beam with a beam-width of 2β degree

should be used, where

α > β. (1)

As we can observe from Fig. 1, there is no overlap in route

A→G→H→D or route A→I→J→D. Under normal conditions

(single-path DSR-based routing), any one of these routes can be

selected for data transmission. It should be noted however, that

in single-path DDSR directional routing only intra-path overlaps need to be counted in order to eliminate interferences between neighboring hopping nodes [18]. Thus, in the case of

multipath schemes, routes A→G→H→D and A→I→J→D can

not be simultaneously selected to transmitting packets because

of the inter-path interferences between them. For example, the

transmit beam of A→G overlaps with the receive beam of I→A

while the transmit beam of A→I overlaps with the receive beam

of G→A. Instead, routes A→E→F→D and A→G→H→D, or

routes A→E→F→D and A→I→J→D can be used for simultaneous packet transmission. Under these conditions there would

be no intra-path or inter-path interference.

In the route discovery process of the proposed DDSR-based

multi-path routing protocol, the transmitting node will insert

its address and position information into the received RREQ or

RREP and then forwarded it to the neighboring nodes or the

next node. Under these conditions, every node uses its own

positional information as well as the positional information that

the node has received from its neighboring node (via RREQ and

RREP) to calculate the direction of arrival (DOA). According

to the position information, the DOAs and β in (1), the intrapath overlap count of a specific route can be achieved. Note

that for two adjacent hops, i.e. the hops of A & E and E & F

in A→E→F→D, although they don’t overlap with each other,

packet loss will inevitably occur when they transmit and receive

data at same time. This is mainly due to the fact that a packet

sent by node A cannot be received by node E, while this node

itself is engaged in relaying a packet to node F. Obviously, this

kind of packet loss is due to a form of hidden terminal effect,

which is unique in the case of directional communication. More

specifically, node A does not hear node E when this node is

forwarding a packet to node F. Based on the above observation,

we can draw a conclusion that the overlap between two adjacent

hops in the same route will not deteriorate the throughput. In

this respect we consider two schemes, namely scheme-1 where

the overlap between two adjacent hops in the same route is not

counted into the overlap count, and scheme-2 where the overlap

between two adjacent hops in the same route is counted into the

overlap count. For instance, in scheme-1 there is one overlap

between hops of A & B and C & D over the route A→B→C→D

(see Fig. 1), whereas in scheme-2 there are 3 overlaps over the

route A→B→C→D, namely, the overlap between the hops of

A & B and B & C, the overlap between the hops of A & B

and C & D, as well as the overlap between the hops of B &

C and C & D. Our simulation results in Fig. 5 demonstrate

that scheme-1 is capable of attaining similar performance as

scheme-2. This is a very important and useful merit, especially

in multi-path routing scenarios, where multiple routes with zero

overlap count are much easier to be found in scheme-1 than in

scheme-2.

The inter-path overlap count of multiple routes can be calculated by using the same method, where the position information

of the nodes over multiple routes is taken into consideration.

The intra-path overlap count and a positional information vector of the nodes along the route are inserted into the routing

entry as shown in the Table I. Note that in the original DSR,

since all the duplicated RREQs are discarded, it is unlikely to

find the best route to destination. To avoid this kind of situation,

intermediate nodes will forward the RREQs whose hop counts

are not bigger than that of the previously received RREQs, even

if they have the same ID. Therefore, the source node may re2

Authorized licensed use limited to: NIST Researchers. Downloaded on February 19, 2009 at 08:51 from IEEE Xplore. Restrictions apply.
Destination Source

Route

Positional

Information

Vector

Hop

Count

intra-path

Overlap

Count

TABLE I

ROUTING ENTRY STRUCTURE.

ceive multiple RREPs and hence obtain all possible routes to

the destination.

It should be noted that in the route discovery process, the

source node should be able to select best multiple routes from

its route cache for data transmission. For instance, based on

route selection metrics, it is possible that there would be too

many potential routes from the source to the destination, especially in a high-density ad hoc network. For the sake of avoiding

excessive overhead, a threshold is set in the destination node.

When the number of the RREQs received by the destination

is smaller than this threshold, the destination node will keep

sending RREPs. Otherwise, the RREQs will be discarded. In

our simulations, the threshold is set to 20, which would be sufficiently large enough to find multiple routes with the fewest

inter-path and intra-path overlaps (in our scenarios). In order to

select the most suitable multiple routes from the route cache after receiving multiple RREPs from the destination node, three

metrics are employed to measure the performance of selected

routes as follows:

1) Hop Count;

2) Number of joint nodes between two nodes;

3) Inter-path and intra-path Overlap count over multiple

routes.

Based on the information in Table I, the source node will select the most suitable multiple routes from its routing cache,

according to the following rules:

1) The route with the smallest hop count in the source node’s

route cache has the highest priority to be selected as the

first best route. If there are two or more routes with

the same smallest hop count, then the intra-path overlap

count is used to select a route with the fewest intra-path

overlaps.

2) The second best route is selected from the remaining

routes. Again, a route with a smaller hop count has higher

priority to be selected.

3) If there are more routes with the same minimal hop count,

the number of joint nodes will be used to select the second

best route. Obviously, the route with smallest number of

joint nodes will be selected as the second best route.

4) In the case that there are more routes with the same number of joint nodes, the overlap count (including intra-path

and inter-path overlaps) of the current route and the first

best route will be employed to decide the second best

route.

5) Repeat steps 2), 3) and 4) to select the best remaining

multiple routes.

Node D

Node C

Node G Node H

Node I

Node E Node F

Node A

Node B

Node J

Fig. 2. An example of a DDSR-based two-path routing system.

B. Data Transmission and Route Maintenance

After the source selects the most suitable multiple routes to

the destination, multiple data streams will be sent to the destination along these routes. An example of a DDSR-based two-path

routing system is shown in Fig. 2, where nodes are capable of

generating two beams at the same time, radiating to two different nodes. For example, node A simultaneously transmits packets to nodes E and I through transmit beams A→E and A→I,

respectively.

When a broken link (caused by mobility and packet loss) is

detected by a node, an RERR message will be generated and

sent in the upstream direction of the route. Once the source

node receives the RRER packet, it removes the hop in error

from its route cache and truncates all routes containing this

hop. After assessing the number of active routes left in the route

cache to the destination, the source node will carry out following steps: If there are two or more active routes left in the route

cache, the source node will select the two best routes using the

above-mentioned rules. Otherwise, the source node will initial

a new route discovery process as discussed in Section II-A.

III. PERFORMANCE RESULTS

In this section the performance of the proposed DDSR-based

multipath routing protocol is investigated by using our real-time

network simulation testbed, where the IEEE 802.11b standard

is invoked. In the simulations, the input data generated at a

Constant Bit Rate, is encapsulated into fixed 500 bytes UDP

packets. In the physical layer, the receiver sensitivity is -93.0

dBm, the IEEE 802.11b data-rate is 2 Mbps and the noise factor

is 10.0. The directional antenna model employed in our simulations is capable of forming a sharp beam with a beamwidth of

2β = 40 degrees, as portrayed in Fig. 3. The maximum antenna

gain is 15.56 dB, while the sidelobe gain outside the beam is -

4.00 dB. For simplicity, there is no fading in our simulation and

free space is selected as the path loss model. Due to the space

limitation, only a single-session scenario is considered in this

paper, which means that there is only one source and one destination in the network. It will be extended to a multi-session

scenario in our future research.

The performance of the proposed DDSR-based multi-path

routing protocol is investigated in a random ad hoc network

using directional antenna as seen in Fig. 4. Without loss of

generality, single-path routing schemes and two-path routing

schemes are studied in this figure. It is shown in Fig. 5 that the

3

Authorized licensed use limited to: NIST Researchers. Downloaded on February 19, 2009 at 08:51 from IEEE Xplore. Restrictions apply.
Maximum Antenna Gain = 15.56 dB

Sidelobe Gain = −4.0 dB

2β = 40

Fig. 3. Directional antenna model employed in our simulations.

Destination Node 

Source Node 

Fig. 4. Random ad hoc network. Two red routes are selected when using the

DDSR-based multi-path routing protocol scheme-1, where overlaps between

adjacent hops in the same route are not counted. By contrast, when invoking

the DDSR-based multi-path routing protocol scheme-2, two blue routes will be

used to transmit packets.

DDSR-based single-path routing protocol is capable of greatly

improving the performance of the original DSR-based singlepath routing protocol, since there is no interference from the

nodes hops away because of the directionality of the beam. The

packet loss in the DDSR-based routing protocols occurs mainly

because that when node i is directionally communicating with

node i + 1, node i can not receive data from node i − 1. This

kind of packet loss happens frequently when the input bit rate

is higher than 600Kbps. Based on this observation, a conclusion can be reached that we cannot further improve the performance by reducing overlaps between adjacent hops (in the

same route). In other words, overlaps between adjacent hops in

the same route cannot impact the throughput performance. Fig.

5 demonstrates that the DDSR-based single-path routing protocol (scheme-1) is capable of attaining a similar performance

as the DDSR-based single-path routing protocol (scheme-2). It

can also be seen from Fig. 5 that the DDSR-based two-path

routing protocols further improve the throughput performance

by simultaneously transmitting packets along two overlap-free

paths. As shown in Fig. 5, two red routes are selected when

using the DDSR-based multi-path routing protocol (scheme-1),

where overlaps between adjacent hops in the same route are

not counted. By contrast, when invoking the DDSR-based twopath routing protocol (scheme-2), two blue routes will be used

to transmit packets. Again, the DDSR-based two-path routing

protocol scheme-1 attains a similar performance as the DDSRbased two-path routing protocol scheme-2. Note that routes

with zero overlap count are much easier to be found in scheme1 than in scheme-2. Scheme-1, however, has an advantage over

200 400 600 800 1000 1200 1400 1600

0

10

20

30

40

50

60

70

80

90

100

Input Bit Rate (kbps)

Throughput (%)

Random Network using Directional Antenna

DDSR Multipath Routing scheme−1

DDSR Multipath Routing scheme−2

DDSR Single−path scheme−1

DDSR Single−path scheme−2

Original DSR Single−path

Fig. 5. Random ad hoc network using directional antenna. The proposed

DDSR-based multipath routing protocol achieves the best performance, followed by the DDSR-based single-path routing protocol. The worst one is the

original DSR-based single-path protocol.

0 200 400 600 800 1000 1200 1400 1600

0

10

20

30

40

50

60

70

80

90

100

Input Bit Rate (kbps)

Throughput (%)

Random ad hoc network

DDSR Multipath Directional Antenna

DSR Multipath Directional Antenna

Multipath Multi−Channel OMNI−Antenna

Multipath Single−Channel OMNI−Antenna

Fig. 6. Random ad hoc network. The proposed DDSR-based multipath routing

protocol with directional antenna achieves considerable performance gains over

other routing protocols, including the original DSR-based multipath routing

protocol with directional antenna or omnidirectional antenna, as well as the

multipath multichannel routing protocol with omnidirectional antenna.

scheme-2, especially in multi-path routing scenarios.

In Fig. 6, the performances of the proposed DDSR-based

multipath routing protocol with directional antenna are compared with other routing protocols, including the original DSRbased multipath routing protocol with directional antenna discussed in [7], the multipath multichannel routing protocol with

omnidirectional antenna described in [6], or the SMR scheme

proposed in [3]. Without loss of generality, two-path routing

schemes are considered in this figure. It should be noted that

we have used a different transmit power for different routing

schemes so that the average hop count of every path is 5. Obviously, the DDSR-based multipath routing protocol with directional antenna achieves the best performance, followed by the

original DSR-based multipath routing protocol with directional

antenna discussed in [7], in which case the inter-path and intrapath interferences are not eliminated as in the DDSR-based

multipath routing protocol. The third scheme is the multipath

4

Authorized licensed use limited to: NIST Researchers. Downloaded on February 19, 2009 at 08:51 from IEEE Xplore. Restrictions apply.
multichannel routing protocol with omnidirectional antenna described in [6], where intra-path co-channel interference has not

been suppressed. The SMR scheme proposed in [3] attains the

worst performance since it can not reduce either intra-path or

inter-path interference.

Finally, in Fig. 7 the proposed DDSR-based multipath routing protocol is examined in a dynamic ad hoc network environment, where nodes move randomly at a speed of 5 m/s. Again,

the proposed DDSR-based multipath routing protocol achieves

the best performance, since it is capable of eliminating both

inter-path and intra-path interferences. Fig. 7 also indicates that

the DDSR-based single-path routing protocol outperforms the

original DSR-based multipath routing protocol, which means

that the benefits of using multipath are counteracted by the

inter-path interference and intra-path interference.

100 200 300 400 500 600 700 800 0

10

20

30

40

50

60

70

80

90

100

Input Bit Rate (kbps)

Throughput (%)

Dynamic Network using Directional Antenna

DDSR Multipath Routing scheme

DSR Multipath Routing scheme

DDSR Single−path Routing scheme

Fig. 7. Random dynamic ad hoc network. The proposed DDSR-based multipath routing protocol is investigated in a dynamic ad hoc network, where the

nodes move randomly at a speed of 5 m/s.

IV. CONCLUSIONS

In this paper we have proposed an DDSR-based multipath

routing protocol, in order to enhance the performance of ad

hoc networks using directional antennas. The proposed directional routing protocol aims at preventing interference from

other nodes along the same path by exploiting the directionality

of the beams and hence, improve the performance. Additionally, a multipath scheme is incorporated to further improve the

throughput of the system by simultaneously transmitting packets over multiple paths. Finally, our comparative results demonstrated that the proposed DDSR-based multipath routing protocol with directional antenna is capable of achieving considerable performance gains over other routing protocols, including

the original DSR-based multipath routing protocol with directional antenna discussed in [7], the multipath multichannel routing protocol with omnidirectional antenna described in [6], or

the SMR scheme proposed in [3].

REFERENCES

[1] A. Nasipuri and S. R. Das, “On-demand multipath routing for mobile ad

hoc networks,” Proceedings of IEEE ICCCN’99, pp. 64–70, Oct. 1999.

[2] S. J. Lee and M. Gerla, “AODV-BR: backup routing in ad hoc networks,”

IEEE WCNC. 2000, vol. 3, pp. 1311–1316, Sept. 2000.

[3] S. J. Lee and M. Gerla, “Split multipath routing with maximally disjoint

paths in ad hoc networks,” ICC 2001, Vol. 10, pp. 3201–3205, June 2001.

[4] P. P. Pham and S. Perreau, “Performance analysis of reactive shortest

path and multipath routing mechanism with load balance,” Proceedings

of IEEE INFOCOM 2003, Vol. 1, pp. 251–259, April 2003.

[5] S. Tsirigos and Z. J. Haas, “Multipath routing in the presence of frequent

topological changes,” IEEE Communications Magazine, Vol. 39, pp. 132–

138, Nov. 2001.

[6] B. Yan and H. Gharavi,, “Multi-path Multi-Channel Routing Protocol,”

IEEE International Symposium on Network Computing and Applications

2006, IEEE NCA06, Cambridge, MA USA, July 2006.

[7] S. Roy, S. Bandyopadhyay, T. Ueda, and K. Hasuike, “Multipath Routing in Ad Hoc Wireless Networks with Omni Directional and Directional

Antenna: A Comparative Study,” Proceedings of the 4th International

Workshop on Distributed Computing, Mobile and Wireless Computing,

pp. 184–191, 2001.

[8] S. K. Das, A. Mukherjee, S. Bandyopadhyay, K. Paul, and D. Saha,

“Improving quality-of-service in ad hoc wireless networks with adaptive multi-path routing,” Global Telecommunications Conference, 2000,

vol. 1, pp. 261–265, 27 Nov.-1 Dec. 2000.

[9] J. H. Winters, “Smart antenna techniques and their application to wireless

ad hoc networks,” IEEE Wirelss Communications, vol. 13, pp. 77–83,

August 2006.

[10] S. Yi, Y. Pei, and S. Kalyanaraman, “On the Capacity Improvement of Ad

Hoc Wireless Networks Using Directional Antennas,” Proc. Mobihoc’03,

pp. 108–116, June 2003.

[11] R. Ramanathan, J. Redi, C. Santivanez, D. Wiggins, and S. Polit, “Ad

hoc networking with directional antennas: a complete system solution,”

IEEE Journal on Selected Areas in Communications, vol. 23, pp. 496–

506, March 2005.

[12] R. R. Choudhury, X. Yang, R. Ramanathan, and N. H. Vaidya, “On designing MAC protocols for wireless networks using directional antennas,”

IEEE Transactions on Mobile Computing, vol. 5, pp. 477–491, May 2006.

[13] M. Takai, J. Martin, A. Ren, and R. Bagrodia, “Directional virtual carrier sensing for directional antennas in mobile ad hoc networks,” Proc.

Mobihoc’02, pp. 183–193, June 2002.

[14] M. Park, R. W. Heath, Jr., and S. M. Nettles, “Improving throughput and

fairness for MIMO ad hoc networks using antenna selection diversity,”

Global Telecommunications Conference, 2004. GLOBECOM ’04. IEEE,

vol. 5, pp. 3363–3367, December 2004.

[15] D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad-Hoc

Wireless Networks,” Mobile Computing, T. Imielinski and H. Korth, Eds.,

Kluwer, pp. 153–181, 1996.

[16] H. Gharavi, “Control Based Mobile Ad-hoc Networks For Video Communications,” IEEE Transactions on Consumer Electronics, vol. 52, No. 2,

pp. 383–391, May 2006.

[17] H. Gharavi, “Multi-Channel Mobile Ad-hoc Links for Multimedia Communications,” Proceedings of the IEEE, Vol. 96, No. 1, pp. 77–96, January 2008.

[18] B. Hu and H. Gharavi,, “DSR-Based Directional Routing Protocol for

Ad Hoc Networks,” IEEE Global Telecommunications Conference, 2007.

GLOBECOM ’07, pp. 4936–4940, Washington DC, USA, Nov. 2007.

5

Authorized licensed use limited to: NIST Researchers. Downloaded on February 19, 2009 at 08:51 from IEEE Xplore. Restrictions apply.