A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols:
Abstract:
An ad hoc network is a collection of wireless mobile nodes dynamically forming a temporary network without the use of any existing network infrastructure or centralized administration. Due to the limited transmission range of wireless network interfaces, multiple network "hops" may be needed for one node to exchange data with another across the network. In recent years, a variety of new routing protocols targeted specifically at this environment have been developed, but little performance information on each protocol and no realistic performance comparison between them is available. This paper presents the results of a detailed packet-level simulation comparing four multi-hop wireless ad hoc network routing protocols that cover a range of design choices: DSDV, TORA, DSR, and AODV. We have extended the ns-2 network simulator to accurately model the MAC and physical-layer behavior of the IEEE 802.11 wireless LAN standard, including a realistic
wireless transmission channel model, and present the results of simulations of networks of 50 mobile nodes.
1 Introduction
In areas in which there is little or no communication infrastructure or the existing infrastructure is expensive or inconvenient to use, wireless mobile users may still be able to communicate through the
formation of an ad hoc network. In such a network, each mobile node operates not only as a host but also as a router, forwarding packets for other mobile nodes in the network that may not be within direct wireless transmission range of each other. Each node participates in an ad hoc routing protocol that allows it to discover “multi-hop” paths through the network to any other node. The idea of ad hoc networking is sometimes also called infrastructureless networking [13], since the mobile nodes in the network dynamically establish routing among themselves to form their own network “on the fly.” Some examples of the possible uses of ad hoc networking include students using laptop computers to participate in an interactive lecture, business associates sharing information during a meeting, soldiers relaying information for situational awareness on the battlefield [12, 21], and emergency
disaster relief personnel coordinating efforts after a hurricane or earthquake.
Many different protocols have been proposed to solve the multihop routing problem in ad hoc networks, each based on different assumptions and intuitions. However, little is known about the actual performance of these protocols, and no attempt has previously been made to directly compare them in a realistic manner. This paper is the first to provide a realistic, quantitative analysis
comparing the performance of a variety of multi-hop wireless ad hoc network routing protocols. We present results of detailed simulations showing the relative performance of four recently proposed ad hoc routing protocols: DSDV [18], TORA [14, 15], DSR [9, 10, 2], and ODV [17]. To enable these simulations, we extended the ns-2 network simulator [6] to include:
Node mobility.
A realistic physical layer including a radio propagation model supporting propagation delay, capture effects, and carrier sense [20].
Radio network interfaces with properties such as transmission power, antenna gain, and receiver sensitivity.
The IEEE 802.11 Medium Access Control (MAC) protocol using the Distributed Coordination Function (DCF) [8].
Our results in this paper are based on simulations of an ad hoc network 50 wireless mobile nodes moving about and communicating with each other. We analyze the performance of each protocol and explain the design choices that account for their performance.
2 Simulation Environment
ns is a discrete event simulator developed by the University of California at Berkeley and the VINT project [6]. While it provides substantial support for simulating TCP and other protocols over conventional networks, it provides no support for accurately simulating the physical aspects of multi-hop wireless networks or the MAC protocols needed in such environments. Berkeley has recently released ns code that provides some support for modeling wireless LANs, but this code cannot be used for studying multi-hop ad hoc networks as it does not support the notion of node position; there is no spatial diversity (all nodes are in the same collision domain), and it can only
model directly connected nodes.
In this section, we describe some of the modifications we made to ns to allow accurate simulation of mobile wireless networks.
2.1 Physical and Data Link Layer Model
To accurately model the attenuation of radio waves between antennas close to the ground, radio engineers typically use a model that attenuates the power of a signal as 1 r 2 at short distances (r is the
distance between the antennas), and as 1 r 4 at longer distances.
The crossover point is called the reference distance, and is typically around 100 meters for outdoor low-gain antennas 1.5m above the ground plane operating in the 1–2GHz band [20]. Following this
practice, our signal propagation model combines both a free space propagation model and a two-ray ground reflection model. When a transmitter is within the reference distance of the receiver,
3.2.2 Implementation Decisions
IMEP must queue objects for some period of time to allow possible aggregation with other objects, but the IMEP specification [5] does not define this time period, and we discovered that the overall
performance of the protocol was very sensitive to the choice of this value. After significant experimentation, we chose as the best balance between packet overhead and routing protocol convergence, to aggregate H
ELLO and ACK packets for a time uniformly chosen between 150 ms and 250 ms, and to not delay TORA routing messages for aggregation. The reason for not delaying these messages is that the TORA link reversal process creates short-lived routing loops that exist from the time that the link-reversal starts until the time that all nodes that need to be aware of the reversal receive the corresponding U
PDATE (Section 5.2). Delaying the transmission of TORA routing messages for aggregation, coupled with any queuing delay at the network interface, allows these routing loops to last long enough that
significant numbers of data packets are dropped.
The TORA and IMEP specifications [15, 5] do not define the precise semantics of reliable object delivery required by TORA, but experimentation showed that very strong semantics must be provided
in order to prevent the creation of long-lived routing loops. In particular, all TORA objects must be delivered reliably and in order, without any duplication. Additionally, all neighboring nodes
in the ad hoc network must have a consistent picture of the network with regard to each destination. This implies that anytime a node A decides its link to a neighbor B has gone down, B must also decide that the link to A has gone down.
4.1 Movement Model
Nodes in the simulation move according to a model that we call the “random waypoint” model [10]. The movement scenario files we used for each simulation are characterized by a pause time. Each node begins the simulation by remaining stationary for pause time seconds. It then selects a random destination in the 1500m, 300m space and moves to that destination at a speed distributed uniformly between 0 and some maximum speed. Upon reaching the destination, the node pauses again for pause time seconds, selects another destination, and proceeds there as previously described, repeating this behavior for the duration of the simulation. Each simulation ran for 900 seconds of simulated time.
We ran our simulations with movement patterns generated for 7 different pause times: 0, 30, 60, 120, 300, 600, and 900 seconds. A pause time of 0 seconds corresponds to continuous motion, and a
pause time of 900 (the length of the simulation) corresponds to no motion.
Because the performance of the protocols is very sensitive to movement pattern, we generated scenario files with 70 different movement patterns, 10 for each value of pause time. All four routing protocols were run on the same 70 movement patterns.
We experimented with two different maximum speeds of node movement. We primarily report in this paper data from simulations using a maximum node speed of 20 meters per second (average speed 10 meters per second), but also compare this to simulations using a maximum speed of 1 meter per second.
8 Conclusions
The area of ad hoc networking has been receiving increasing attention among researchers in recent years, as the available wireless networking and mobile computing hardware bases are now capable of supporting the promise of this technology. Over the past few years, a variety of new routing protocols targeted specifically at the ad hoc networking environment have been proposed, but little performance information on each protocol and no detailed performance comparison between the protocols has previously been available.
This paper makes contributions in two areas. First, we describe our modifications to the ns network simulator to provide an accurate simulation of the MAC and physical-layer behavior of the IEEE 802.11 wireless LAN standard, including a realistic wireless transmission channel model. This new simulation environment provides a powerful tool for evaluating ad hoc networking protocols and other wireless protocols and applications. Second, using this simulation environment, we present the results of a detailed packet-level simulation comparing four recent multi-hop wireless ad hoc network routing protocols. These protocols, DSDV, TORA, DSR, and AODV, cover a range of design choices, including periodic advertisements vs. ondemand route discovery, use of feedback from the MAC layer to indicate a failure to forward a packet to the next hop, and hop by hop routing vs. source routing. We simulated each protocol in ad hoc networks of 50 mobile nodes moving about and communicating with each other, and presented the results for a range of node mobility rates and movement speeds.
Each of the protocols studied performs well in some cases yet has certain drawbacks in others. DSDV performs quite predictably, delivering virtually all data packets when node mobility rate and movement speed are low, and failing to converge as node mobility increases. TORA, although the worst performer in our experiments in terms of routing packet overhead, still delivered over 90%of the packets in scenarios with 10 or 20 sources. At 30 sources, the network was unable to handle all of the traffic generated by the routing protocol and a significant fraction of data packets were dropped. The performance of DSR was very good at all mobility rates and movement speeds, although its use of source routing increases the number of routing overhead bytes required by the protocol. Finally, AODV performs almost as well as DSR at all mobility rates and movement speeds and accomplishes its goal of eliminating source routing overhead, but it still requires the transmission of many routing overhead packets and at high rates of node mobility is actually more expensive than DSR.
DOWNLOAD LINK:
CLICK ME
Abstract:
An ad hoc network is a collection of wireless mobile nodes dynamically forming a temporary network without the use of any existing network infrastructure or centralized administration. Due to the limited transmission range of wireless network interfaces, multiple network "hops" may be needed for one node to exchange data with another across the network. In recent years, a variety of new routing protocols targeted specifically at this environment have been developed, but little performance information on each protocol and no realistic performance comparison between them is available. This paper presents the results of a detailed packet-level simulation comparing four multi-hop wireless ad hoc network routing protocols that cover a range of design choices: DSDV, TORA, DSR, and AODV. We have extended the ns-2 network simulator to accurately model the MAC and physical-layer behavior of the IEEE 802.11 wireless LAN standard, including a realistic
wireless transmission channel model, and present the results of simulations of networks of 50 mobile nodes.
1 Introduction
In areas in which there is little or no communication infrastructure or the existing infrastructure is expensive or inconvenient to use, wireless mobile users may still be able to communicate through the
formation of an ad hoc network. In such a network, each mobile node operates not only as a host but also as a router, forwarding packets for other mobile nodes in the network that may not be within direct wireless transmission range of each other. Each node participates in an ad hoc routing protocol that allows it to discover “multi-hop” paths through the network to any other node. The idea of ad hoc networking is sometimes also called infrastructureless networking [13], since the mobile nodes in the network dynamically establish routing among themselves to form their own network “on the fly.” Some examples of the possible uses of ad hoc networking include students using laptop computers to participate in an interactive lecture, business associates sharing information during a meeting, soldiers relaying information for situational awareness on the battlefield [12, 21], and emergency
disaster relief personnel coordinating efforts after a hurricane or earthquake.
Many different protocols have been proposed to solve the multihop routing problem in ad hoc networks, each based on different assumptions and intuitions. However, little is known about the actual performance of these protocols, and no attempt has previously been made to directly compare them in a realistic manner. This paper is the first to provide a realistic, quantitative analysis
comparing the performance of a variety of multi-hop wireless ad hoc network routing protocols. We present results of detailed simulations showing the relative performance of four recently proposed ad hoc routing protocols: DSDV [18], TORA [14, 15], DSR [9, 10, 2], and ODV [17]. To enable these simulations, we extended the ns-2 network simulator [6] to include:
Node mobility.
A realistic physical layer including a radio propagation model supporting propagation delay, capture effects, and carrier sense [20].
Radio network interfaces with properties such as transmission power, antenna gain, and receiver sensitivity.
The IEEE 802.11 Medium Access Control (MAC) protocol using the Distributed Coordination Function (DCF) [8].
Our results in this paper are based on simulations of an ad hoc network 50 wireless mobile nodes moving about and communicating with each other. We analyze the performance of each protocol and explain the design choices that account for their performance.
2 Simulation Environment
ns is a discrete event simulator developed by the University of California at Berkeley and the VINT project [6]. While it provides substantial support for simulating TCP and other protocols over conventional networks, it provides no support for accurately simulating the physical aspects of multi-hop wireless networks or the MAC protocols needed in such environments. Berkeley has recently released ns code that provides some support for modeling wireless LANs, but this code cannot be used for studying multi-hop ad hoc networks as it does not support the notion of node position; there is no spatial diversity (all nodes are in the same collision domain), and it can only
model directly connected nodes.
In this section, we describe some of the modifications we made to ns to allow accurate simulation of mobile wireless networks.
2.1 Physical and Data Link Layer Model
To accurately model the attenuation of radio waves between antennas close to the ground, radio engineers typically use a model that attenuates the power of a signal as 1 r 2 at short distances (r is the
distance between the antennas), and as 1 r 4 at longer distances.
The crossover point is called the reference distance, and is typically around 100 meters for outdoor low-gain antennas 1.5m above the ground plane operating in the 1–2GHz band [20]. Following this
practice, our signal propagation model combines both a free space propagation model and a two-ray ground reflection model. When a transmitter is within the reference distance of the receiver,
3.2.2 Implementation Decisions
IMEP must queue objects for some period of time to allow possible aggregation with other objects, but the IMEP specification [5] does not define this time period, and we discovered that the overall
performance of the protocol was very sensitive to the choice of this value. After significant experimentation, we chose as the best balance between packet overhead and routing protocol convergence, to aggregate H
ELLO and ACK packets for a time uniformly chosen between 150 ms and 250 ms, and to not delay TORA routing messages for aggregation. The reason for not delaying these messages is that the TORA link reversal process creates short-lived routing loops that exist from the time that the link-reversal starts until the time that all nodes that need to be aware of the reversal receive the corresponding U
PDATE (Section 5.2). Delaying the transmission of TORA routing messages for aggregation, coupled with any queuing delay at the network interface, allows these routing loops to last long enough that
significant numbers of data packets are dropped.
The TORA and IMEP specifications [15, 5] do not define the precise semantics of reliable object delivery required by TORA, but experimentation showed that very strong semantics must be provided
in order to prevent the creation of long-lived routing loops. In particular, all TORA objects must be delivered reliably and in order, without any duplication. Additionally, all neighboring nodes
in the ad hoc network must have a consistent picture of the network with regard to each destination. This implies that anytime a node A decides its link to a neighbor B has gone down, B must also decide that the link to A has gone down.
4.1 Movement Model
Nodes in the simulation move according to a model that we call the “random waypoint” model [10]. The movement scenario files we used for each simulation are characterized by a pause time. Each node begins the simulation by remaining stationary for pause time seconds. It then selects a random destination in the 1500m, 300m space and moves to that destination at a speed distributed uniformly between 0 and some maximum speed. Upon reaching the destination, the node pauses again for pause time seconds, selects another destination, and proceeds there as previously described, repeating this behavior for the duration of the simulation. Each simulation ran for 900 seconds of simulated time.
We ran our simulations with movement patterns generated for 7 different pause times: 0, 30, 60, 120, 300, 600, and 900 seconds. A pause time of 0 seconds corresponds to continuous motion, and a
pause time of 900 (the length of the simulation) corresponds to no motion.
Because the performance of the protocols is very sensitive to movement pattern, we generated scenario files with 70 different movement patterns, 10 for each value of pause time. All four routing protocols were run on the same 70 movement patterns.
We experimented with two different maximum speeds of node movement. We primarily report in this paper data from simulations using a maximum node speed of 20 meters per second (average speed 10 meters per second), but also compare this to simulations using a maximum speed of 1 meter per second.
8 Conclusions
The area of ad hoc networking has been receiving increasing attention among researchers in recent years, as the available wireless networking and mobile computing hardware bases are now capable of supporting the promise of this technology. Over the past few years, a variety of new routing protocols targeted specifically at the ad hoc networking environment have been proposed, but little performance information on each protocol and no detailed performance comparison between the protocols has previously been available.
This paper makes contributions in two areas. First, we describe our modifications to the ns network simulator to provide an accurate simulation of the MAC and physical-layer behavior of the IEEE 802.11 wireless LAN standard, including a realistic wireless transmission channel model. This new simulation environment provides a powerful tool for evaluating ad hoc networking protocols and other wireless protocols and applications. Second, using this simulation environment, we present the results of a detailed packet-level simulation comparing four recent multi-hop wireless ad hoc network routing protocols. These protocols, DSDV, TORA, DSR, and AODV, cover a range of design choices, including periodic advertisements vs. ondemand route discovery, use of feedback from the MAC layer to indicate a failure to forward a packet to the next hop, and hop by hop routing vs. source routing. We simulated each protocol in ad hoc networks of 50 mobile nodes moving about and communicating with each other, and presented the results for a range of node mobility rates and movement speeds.
Each of the protocols studied performs well in some cases yet has certain drawbacks in others. DSDV performs quite predictably, delivering virtually all data packets when node mobility rate and movement speed are low, and failing to converge as node mobility increases. TORA, although the worst performer in our experiments in terms of routing packet overhead, still delivered over 90%of the packets in scenarios with 10 or 20 sources. At 30 sources, the network was unable to handle all of the traffic generated by the routing protocol and a significant fraction of data packets were dropped. The performance of DSR was very good at all mobility rates and movement speeds, although its use of source routing increases the number of routing overhead bytes required by the protocol. Finally, AODV performs almost as well as DSR at all mobility rates and movement speeds and accomplishes its goal of eliminating source routing overhead, but it still requires the transmission of many routing overhead packets and at high rates of node mobility is actually more expensive than DSR.
DOWNLOAD LINK:
CLICK ME
No comments:
Post a Comment