Quality of Service for Flat Routing Protocols in Mobile Ad hoc Networks

Vahid Nazari Talooki

Instituto de Telecomunicaes (IT), Aveiro, Portugal

Jonathan Rodriguez
Instituto de Telecomunicaes (IT), Aveiro, Portugal

[email protected] ABSTRACT
Ad hoc networks are temporary networks with a dynamic topology which doesnt have any established infrastructure or centralized administration. These networks need efficient routing protocols in terms of Quality of Services (QoS) metrics. In this paper we present performance comparisons of the DSDV, AODV, DSR and TORA routing protocols with respect to weighted path optimality, average end-to-end delay, load balancing capability, and average jitter. In comparison to previous works, we use a wide range of different movement and communication scenarios which are characterized by the pause time, mobility, and the number of nodes to cover many issues and finding benefits and drawback of these protocols in different situations especially in extreme emergency cases as described in the EU-FP7 PEACE project.

[email protected]
we use a wide range of different movement and communication scenarios which are characterized by the pause time, mobility, and the number of nodes to cover many issues and finding benefits and drawback of these protocols in different situations.

2. PREVIOUS WORKS
Routing in ad hoc networks is a very challenging issue due to nodes mobility, dynamic topology, frequent link breakage, limitation of nodes (memory, battery, bandwidth, and processing power), and lack of central point like base stations or servers. On the other hand, there are a lot of performance metrics and quality services which should be satisfied in an ad hoc network like Endto-end data throughput, average end-to-end data delay, jitter, packet loss ratio, Normalized Routing Load(NRL), Packet Delivery Ratio(PDR), and path optimality. Each protocol can satisfy some of these metrics and has some drawbacks in terms of other metrics. Furthermore, due to the nature of ad hoc networks (distributed and cooperated routing), even for a fixed metric, each protocol can show a different performance with different networks features like number of mobile nodes, mobility of nodes, and pause time (pause time is introduced in section 5). So by comparing between different ad hoc routing protocols we can extract very important information about the performance of these protocols in different situations. In related works, the performance of some protocols like DSDV [2] and AODV [3] are analyzed individually and some other multi hop protocols are compared together [4,5], but this paper presents an extensive performance comparison between all these flat routing protocols (DSDV, AODV, DSR, and TORA). Furthermore, where most of previous works focused on some well known metrics like delay, PDR, path optimality, and NRL, this paper not only considers the average end to end delay and weighted path optimality, but also presents performance comparison of two other important metrics: jitter and traffic load balancing. Additionally, most of the related papers on performance comparison are limited to one future of ad hoc network like number of mobile nodes in network [6,7] or pause time [1,8], but this paper considers different features of ad hoc networks like pause time, number of mobile nodes in networks, and mobility of nodes simultaneously.

Categories and Subject Descriptors

C.2.2 [Network Protocols]: Routing protocols.

General Terms
Algorithms, Measurement, Performance.

Keywords
Mobile Ad hoc Networks, Routing Protocol, Quality of Services

1. INTRODUCTION
Nodes in ad hoc networks operate not only as a transceiver but also as a router and forward packets for other mobile nodes in the network that may not be within direct transmission range of each other [1]. In this paper simulation results of comparisons between four routing protocols in mobile ad hoc networks (DSDV, AODV, DSR, and TORA) in terms of weighted path optimality, average end-to-end delay, traffic balancing capability, and average jitter are given, when topology of network is changing and considering parameters like pause time, number of nodes, and nodes mobility. In comparison to the related previous papers on this subject, here

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Mobimedia09, September 79, 2009, London, UK. Copyright 2009 ICST 978-963-9799-62-2/00/0004$5.00.

3. DESCRIPTION OF PROTOCOLS
Flat routing approaches adopt a flat addressing scheme and all nodes participating in routing play an equal role. Flat routing schemes are classified in two classes: Proactive and Reactive.

Proactive protocols attempt to find and maintain consistent, up-todate routes between all source-destination pairs regardless of the use or need of such routes; here routing techniques are either linkstate or distance vector. But in reactive protocols routes are created only when a source node request them and data forwarding is accomplished according to source routing or hopby-hop routing [2].

the length of the shortest path that existed physically when path i was selected by the protocol, SPZ(i) is the sum of data packets that had been transferred through path i, and N is the number of all paths (from the start of the simulation to its end).

4.1.2 Average end-to-end delay

End-to-end delay includes all possible delay caused by buffering during route discovery latency, transmission delays at the MAC, queuing at interface queue, and propagation and transfer time [1]. For packet j which was sent by source node i and received successfully at destination node, end-to-end delay is: End-to-end delayij = Start_timeij - End_timeij Where Start_timeij is the time when the sending of packet j at node i starts, End_timeij is the time when packet j, sent by node I, is received successfully at the destination node. Table 1. Parameters of movement and communication model
Movement model I, characterized by pause time. Topology area Maximum mobility of nodes Pause time Number of nodes Simulation time 700m 700m 30 m/s 1..100 40 100s

3.1 Destination Sequenced Distance Vector

DSDV is a proactive table-driven protocol based on the classical Bellman-Ford algorithm. All nodes try to find all paths to possible destinations nodes in a network and the number of hops to each destination and save them in their routing tables. New route broadcasts contain the address of destination, the number of hops to reach the destination, the sequence number of the information receive regarding the destination, as well as a new unique sequence number for the new route broadcast. [2].

3.2 Dynamic Source Routing

DSR is a reactive (On demand) source routing protocol. Route Discovery process is based on flooding the network with route request (RREQ) packets. Every mobile host that receives a RREQ packet checks the contents of its route cache, and if it is the destination it replies to the RREQ with a route reply (RREP) packet that is routed back to the original source; the RREQ is propagated till the destination. [3].

Movement model II, characterized by number of mobile nodes Topology area Maximum mobility of nodes Pause time Number of nodes Simulation time Topology area 700m 700m 30 m/s 50s 1060 100s 700m 700m

3.3 Ad Hoc On-demand Distance Vector

AODV, which is a hop-by-hop reactive (On demand) routing protocol, combines DSR and DSDV mechanisms for routing, by using the on-demand mechanism of routing discovery and route maintenance from DSR and the hop-by-hop routing and sequence number from DSDV. For each destination, AODV creates a routing table like DSDV, while DSR uses node cache to maintain routing information [4].

3.4 Temporally Ordered Routing Algorithm

TORA is a highly adaptive loop-free distributed routing algorithm based on the concept of link reversal and applies a reactive (On demand) source routing scheme. The key design concept of TORA is the localization of control messages to a very small set of topological changes by performing three basic functions: Route creation, Route maintenance, and Route deletion. All nodes in TORA use a height metric to establish a direct acyclic graph (DAG) rooted at the destination [5].

Movement model III, characterized by node mobility Maximum mobility of nodes Pause time Number of nodes Simulation time Topology area 0m/s40m/s 50s 40 100s 700m 700m Parameters of communication model Traffic sources CBR 512 bytes 8 packets/second 10

4. NUMERICAL RESULTS 4.1 Performance Metrics

4.1.1 Weighted Path Optimality
Weighted Path Optimality (WPO), which is introduced in [1], shows how much a path which is selected by a routing protocol is optimized in terms of the difference between the number of hops a packet took to reach its destination and the length of the shortest path that physically existed through the network.
N

Data packets size Sending rate Maximum connection

4.1.3 Traffic Load Balancing

Nodes in ad hoc networks can be unfairly burdened to support many packet-relaying functions, resulting in excessive loads on these hot spots. Unbalanced traffic may lead to more delay, packet dropping, and decreasing packet delivery ratio (PDR). First we should compute Load(i) for each node i in the network and then the standard deviation of these load values will be our metric for traffic load balancing of protocols. The smaller standard deviation will show better load balancing capability of protocol.

WPO =

i =1

( AL(i ) SL(i)) SPZ (i )

N

(1)

SPZ (i)
i =1

Where WPO stands for weighted path optimality, AL(i) is the actual length of the path i that was taken by the protocol, SL(i) is

Wg t d a l n t df r n er mh re t e h p t e g i eec f o s ot s i e h h f

Load(i)=

j =1 N i =1 M

packet
i

_ size

1 .75

ij

A ODV DSDV DSR TORA

(2)
ij

1 5 .6

j =1

packet

_ size

1 .55

1 5 .4

Where Packet_sizeij is the size of packet j forwarded by node i, Mi is the number of packets that node i have forwarded, and N is the number of networks nodes.

1 5 .3

1 5 .2

1 5 .1

4.1.4 Jitter
Jitter metric, which is used in this paper, is a quantifier of the changeability over time of the packet latency across a network and can be a measurement for the quality of a communication (like a voice or video call). A zero jitter shows a very high quality communication without any latency. In a specific stream of packets, at Si the sender sent packet i and the receiver received it at Ri. So the jitter of packet i is: Ji = | (Ri+1 - Ri ) - ( Si+1 - Si) | = | (Ri+1 - Si+1) - (Ri - Si) | (3) We have M streams of packets between sender and receiver nodes during the entire simulation time and by each stream N packets will be transferred.

1 5 .0

0 .9 5 1 0 1 5 20 25

no. of nodes

30

35

40

45

50

55

60

Figure 1. Weighted path optimality vs. no. of nodes

A ODV 1 .65 DSDV DSR TORA 1 .55

w ig te p thle g d r n efr m h r s e h d a n th iffee c o s ote t

1 .45

1 .35

1 .25

4.2 RESULTS
The simulation results presented in this paper were obtained using the ns-2 simulator [9]. The required parameters for simulation (like Random Waypoint for moving model) are similar to previous works in previous papers [1, 5] and NS-2 tested default values. The movement scenario files we used for each simulation are categorized into three different groups based on pause time, number of mobile nodes, and maximum node mobility. Table 1 lists parameters of three movement models and one communication model.

1 5 .1

1 .05

0.95 0 1 0 20 30 40

paused time

50

60

70

80

90

1 0 0

Figure 2. Weighted path optimality vs. pause time

1 5 .6 A ODV DSDV

w ig t dp t le ghd f r n ef o s ot s e he ah n t ifee c r m h re t

1 .55

DSR TORA

4.2.1 Weighted Path Optimality (WPO)

Figures 1, 2, and 3 highlight the performance of four protocols with respect to weighted path optimality metric. The closer the value to zero, the better the weighted path optimality. As mentioned in section 2, DSDV employs Bellman-Ford algorithm to find the shortest path between source node and destination node. Hence DSDV performs particularly well regardless of changes in the number of nodes (figure 1) or pause time (figure 2) or mobility ratio (figure 3). Figures 1, 2, and 3 reveal that DSDV has the best performance of the four protocols; DSR, AODV, and TORA follow, in terms of performance, respectively.

1 5 .4

1 5 .3

1 5 .2

1 5 .1

1 5 .0

0 .9 5 0 4 8 1 2

m obility(m /s )

1 6

20

24

28

32

36

40

4.2.2 Average end-to-end delay

End-to-end delay of data packets includes all possible delay caused by buffering during route discovery latency, transmission delays at the MAC, queuing at interface queue, and propagation and transfer time [1]. Among the four protocols, DSDV has the shortest average end-to-end delay. DSDV is a proactive protocol and the advantage of these protocols is that a path to a destination is immediately available, so no delay for route discovery is experienced when an application needs to send a packet. In addition, as can be understood from the presented in section 2, in reactive protocols, AODV is a hop by hop initiate protocol while DSR is a source routing protocol. The source routing protocols have longer delay because their route discovery takes more time as every intermediate node tries to extract information before forwarding the reply.
1 0 .9 0 .8

Figure 3. Weighted path optimality vs. mobility

A ODV DSDV DSR TORA

a ea ee dt - n d l y v r g n - oe d e a

0 .7

0 .6

0 .5

0 .4

0 .3 0 .2

0 .1

0 1 0 1 5 20 25 30

no. of nodes

35

40

45

50

55

60

Figure 4. Average delay vs. no. of nodes

And the same thing happens when a data packet is forwarded hop by hop through the path by source routing method. Hence, while source routing makes route discovery more profitable, it slows down the transmission of packets. This is the reason why AODV performs better than two other reactive protocols in general. Although simulation results demonstrate good performance of DSDV and AODV with changing the number of networks nodes (figure 4), pause time (figure 5) and mobility ratio (figure 6), but poor performance of DSR. TORA has the worst performance among protocols as shown in figures 5 and 6. On the other hand, increasing the node number of networks does not greatly affect TORA with respect to average end-to-end delay (figure 4).

0 .7

A ODV DSDV DSR TORA

0 .6

a ea ee dt - n d l y v r g n -oe d e a

0 .5

0 .4

0 .3

0 .2

0 .1

0 0 1 0 20 30 40

paused time

50

60

70

80

90

1 0 0

4.2.3 Traffic Load Balancing

In this section results of simulations are presented in terms of load balancing. As the number of networks nodes increases, the performance of all four protocols improves. This can be due to formation of more paths through nodes and participation of more nodes in routing (figure 7). With more mobility ratio, more links will be disconnected and the stability of the paths will decrease. This pattern results in decreasing delivery ratio and as a result, fewer sample point. This, in turn, leads to a reduction in the standard deviation of networks load (figure 9). Increasing pause time leads to fewer networks topology changing and so the selected paths by the protocols will be more stable. Therefore, protocols tend to use particular nodes (through these paths). This, in turn, leads to more loads on these nodes and, consequently, more standard deviation of networks load (figure 8). DSDV is a proactive protocol and focuses on the shortest paths which are computed from the resulting tables recorded in nodes; DSV employs only those nodes which are through these paths. Consequently DSDV has the worst performance in all three diagrams of figure 7, 8, and 9.
0 .6

Figure 5. Average delay vs. pause time

A ODV DSDV DSR TORA 0 .5

a ea ee dt - n d l y v r g n - oe d e a

0 .4

0 .3

0 .2

0 .1

0 0 4 8 1 2 1 6 20 24 28 32 36 40

mobility(m/s)

Figure 6. Average delay vs. mobility

0 .0 0 4 A ODV DSDV 0 .0 0 3 5 DSR TORA

4.2.4 Average jitter

Here each protocols curves fluctuate around some similar values regardless of any change in number of nodes (figure 10), pause time (figure 11), and mobility (figure 12). DSR, TORA, AODV, and DSDV average jitters are spread around 80, 50, 30, and 10 msec respectively. Average jitter of DSDV is approximately 10 msec, which is a relatively low and, therefore, proper value. As a guideline, 30 msec matches a single frame time in a full-motion video stream, or a little over the acceptable level of jitter for an audio stream. DSR has the worst average jitter.

d v to o n t ok l a e i i n f e r 'so d a w

0 .0 0 3

0 .0 0 2 5

0 .0 0 2

0 .0 0 1 5

0 .0 0 1

0 .0 0 0 5 1 0 1 5 20 25 30 35 40 45 50 55 60

no. of nodes

Figure 7. Load balancing vs. no. of nodes

0 .00 3 4 A ODV DSDV DSR 0 .00 2 9 TORA

5. CONCLUSION
This paper presents performance study of ad hoc routing protocols using a variety of workload such as pause time, mobility, and number of nodes. Four protocols - DSDV, AODV, DSR, and TORA - are compared with respect to some metrics. In comparison to the previous works, we use a wide range of different movement and communication scenarios which are characterized by the pause time, mobility, and the number of nodes. So a lot of useful information about benefits and drawbacks of these protocols in different situations are extracted. We used the standard deviation of load values on network nodes to compare protocols in terms of load balancing metric.
d va o o n twr 'sl a e i ti n f e ok o d
0 .00 2 4

0.0 01 9

0.0 01 4

0 .00 0 9

0 .00 0 4 0 1 0 20 30 40

paused time

50

60

70

80

90

1 0 0

Figure 8. Load balancing vs. pause time

0 .0 0 2 3

A ODV DSDV DSR TORA

dvao on t ok l a ei t n f e r 's o d i w

0 .0 0 1 8

0 .0 0 1 3

Also path optimality, delay, and average jitter of these protocols are compared. Each of the protocols studied performs well in some cases yet has certain drawbacks in others. DSDV performs very well in weighted path optimality while TORA has the worst performance. We observed that DSDV and AODV have the best performance in terms of average end to end delay. DSR has the best performance with respect to load balancing. DSDV has the best average jitter; AODV, TORA, and DSR follow. For future work, other ad hoc routing protocols like hierarchical or multicast can be selected. The simulations presented in this paper are in a 700700m topology area however a smaller (like 300300m) or bigger (like 1500300m) topology area may shows more and new interesting results. Other ad hoc networks like velocity of nodes can be tested in future works.

0 .0 0 0 8

0 .0 0 0 3 0 4 8 1 2

mobility(m/s)

1 6

20

24

28

32

36

40

Figure 9. Load balancing vs. mobility

0 .1 4 A ODV DSDV DSR TORA

0 .1 2

6. ACKNOWLEDGMENTS
This work was carried out in the scope of the PEACE project that is supported by the European Commission in the framework of FP7 ICT-SEC-2007 with contract number 225654.

0 .1

a ea ejt e v r g it r

0 .0 8

0 .0 6

7. REFERENCES
[1] Nazari,V. and Ziarati, K., Performance Comparison of Routing Protocols for Mobile Ad Hoc Networks, IEEE Conf., Asia-Pacific Conference on Communications, Busan, Korea, 2006 pp. 1-5.
1 0 1 5 20 25

0 .0 4

0 .0 2

no. of nodes

30

35

40

45

50

55

60

Figure 10. Average jitter vs. no. nodes

0 .1 2 A ODV DSDV 0 .1 DSR TORA

[2] Vahid Garousi, Simulating Network traffic in Multi-hop Wireless Ad Hoc Networks based on DSDV (Destination Sequenced Distance Vector) protocol using NS (Network Simulator) Package, University of Waterloo, Fall 2001. [3] E.M. Royer, and C. E. Perkins, An Implementation Study of the AODV Routing Protocol, Proceedings of the IEEE Wireless Communications and Networking Conference, Chicago, IL, September 2000. [4] D. Sun, H. Man, TCP Flow-based Performance Analysis of Two On-Demand Routing Protocols for Mobile Ad Hoc Networks, In Vehicular Technology Conference VTC, 2001, Fall. IEEE VTS 54th, volume 1, pages 272275, 2001. [5] J. Broach, D.A. Maltz, D.B. Johnson, Y.C. Hu, and J.Jetcheva, A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols, Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, Dallas, TX, 1998. [6] Li Layuan , Li Chunlin, Yaun Peiyan ,Performance evaluation and simulations of routing protocols in ad hoc networks, Computer Communications ,2007 [7] Arun Kumar B. R, Lokanatha C. Reddy, Prakash S. Hiremath , Performance Comparison of Wireless Mobile Ad-Hoc Network Routing Protocols, IJCSNS International Journal of Computer Science and Network Security, 2008 [8] Karavetsios & Economides, Performance comparison of distributed routing algorithms in ad hoc mobile networks WSEAS Transactions on Communications, Vol. 3, Issue 1, pp. 317-321, 2004.

0 .0 8

a ea ejit r v r g te

0 .0 6

0 .0 4

0 .0 2

0 0 1 0 20 30 40

paused time

50

60

70

80

90

1 0 0

Figure 11. Average jitter vs. pause time

0 .0 9 A OD V D SD V 0 .0 8 D SR TOR A

0 .0 7

0 .0 6

aea e t r v r g jite

0 .0 5

0 .0 4

0 .0 3

0 .0 2

0 .0 1 0 5 1 0

m obility(m /s )

1 5

20

25

30

35

40

[9] The Network simulator (NS-2), http://www.isi.edu/nsnam/ns

Figure 12. Average jitter vs. mobility