Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.

4, 2011

www.iiste.org

Simulation, Analysis and Performance Comparison among different Routing Protocols for Wireless Sensor Network
Boshir Ahmed Department of Computer Science & Engineering Rajshahi University of Engineering & Technology, Rajshahi-6204, Bangladesh. Tel: +8801713228547 E-mail: [email protected] Md. Khaled Ben Islam Department of Computer Science & Engineering Rajshahi University of Engineering & Technology, Rajshahi-6204, Bangladesh. E-mail: [email protected] Julia Rahman Department of Computer Science & Engineering Rajshahi University of Engineering & Technology, Rajshahi-6204, Bangladesh. E-mail: [email protected]

Abstract Wireless sensor network is a network of tiny, autonomous sensor nodes. Nodes of these networks functions as a hosts and routers which discovers and maintains the routes to other nodes in the network. In such networks, nodes are able to move and synchronize with their neighbors. Due to mobility, connections in the network can change dynamically and nodes can be added and removed at any time. In this paper, we are going to compare wireless sensor networks routing protocols AODV, DYMO and OLSR using network simulator NS-2.34. We have compared the performance of three protocols together. The performance matrix includes PDR (Packet Delivery Ratio), Throughput, End to End Delay, Normalized Routing Load. We are comparing the performance of routing protocols when number of nodes changes, when mobility of nodes changes. Here we basically emphasize to show the behavior of the protocols in different scenario, so that it becomes easier for the network designer to choose a specific protocol based on his/her needs. The comparison results suggest that different routing protocol performs well in different scenarios and good for specific performance metrics. For example, OLSR performs well in the network with strict requirement on time but doesnt perform well in high mobility environment whereas DYMO performs well in high mobility environment. AODV shows average behavior. Keywords: Wireless Sesnsor Network, Routing Protocol, AODV, DYMO, OLSR, Performance Analysis. 1. Introduction Wireless sensor network consists of large number of self-organized sensor nodes. Due to their application nature, they are open to a bunch of real world constrains. Routing in this network is difficult due to their infrastructure less deployment. Routing protocol as an indispensable part of the ad hoc network takes on the responsibility to assist these sensor nodes to discover multi-hop paths and forward packages correctly and smoothly to destinations. Many different routing protocols have been proposed in the past decade based on different assumptions and intuitions. Since the routing protocol is one of the determinant factors of the performance of ad hoc networks, the research that compares different protocols in a realistic setting is necessary and valuable. In this paper, we conduct a set of simulating experiments to analyze and compare the performance of three prevalent ad hoc routing protocols in WSN i.e. AODV (Ad hoc On-Demand Distance Vector) (Charles et al

61

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011

www.iiste.org

2010), DYMO (Dynamic MANET On-demand) (Ian et al 2011) and OLSR (the Optimized Link State Routing) (Aleksandr et al 2004) using NS2 (Network Simulator 2.34) simulation software (Kevin et al 2010). The metrics adopted in experiments include Packet delivery ratio, the average end-to-end time delay, Normalized routing load, packet drop ratio and data throughput. Based on the experimental evaluations, we conclude advantages and disadvantages of each protocol and summarize their most appropriate application environments respectively. The rest of this paper is organized as follows: In section 2, we briefly introduce the four routing protocols and the performance metrics. Section 3 discusses the experiments. Section 4 concludes the experimental results. 2. Protocols and Performance Metrics 2.1 Routing protocols Routing is the process of selecting paths in a network along which to send data or physical traffic. Routing directs the passing of logically addressed packets from their source toward their ultimate destination through intermediary nodes. So routing protocol is the routing of packets based on the defined rules and regulations (Asma et al 2010). According to routing strategy, routing protocols of ad hoc networks can generally be classified into three categories: table driven routing protocols, on-demand routing protocols and hybrid routing protocols (Fotis et al 2006).

Figure 1: Classification of Ad-Hoc routing protocols 1. On-Demand or Reactive protocols, which construct only necessary routes on demand. In these protocols the routes are created only when source wants to send data to destination. This strategy is suitable for large, high mobility networks. The major representative protocols are AODV, DYMO and DSR. 2. Table-driven or proactive protocols, where each node maintains routing information for every possible destination. They usually use link-state routing algorithms for flooding the link information. In proactive routing, each node has one or more routing tables that contain the latest information of the routes to any node in the network. These protocols are not suitable for larger networks, as they need to maintain node entries for each and every node in the routing table of every node. This causes more overhead in the routing table leading to consumption of more bandwidth. DSDV and OLSR are the main representative protocols (Ian et al 2004). 3. Hybrid protocols, which combine on-demand and proactive routing, like Zone Routing protocol (ZRP). 2.1.1 Optimized Link State Routing (OLSR) OLSR is an optimization version of a pure link state protocol that is developed for mobile ad hoc networks. So the topological changes cause the flooding of the topological information to all available hosts in the network. The routes are always immediately available when needed. To reduce the possible overhead in the network, nodes select some neighbors as relay point (MPRs) and announce this information periodically in their control messages. Only the MPRs are allowed to transmit control messages. In route calculation, the MPRs are used to form the route from a given node to any destination in the network. OLSR uses two kinds of the control messages (Aleksandr et al 2004): 1. 2. Hello messages, which are used for finding the information about the link status, the hosts neighbors and Multipoint Relay (MPR) points. Topology Control (TC), TC messages are used to exchange the topological information and build the topology information base. The TC messages are broadcasted periodically.

Routes to every destination are immediately available when data transmission begins. As a proactive routing protocol, every node constructs its own routing table and stores the whole network state. The information about broken links or partially known links is not stored in the routing table.

62

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011
Table 1: Fields of Routing table of OLSR node Destination address Next address Number of hops to destination

www.iiste.org

Local interface address

Figure 2: A Sensor Network with 7 sensor nodes. Table 2: Routing Table of Node B Node B One hop neighbors A, C, F, G Two hop neighbors D, E MPRs C

Figure 2 shows an example a node, say node B, periodically broadcasts HELLO messages to all immediate neighbors (1-hop) to exchange neighborhood information (i.e., list of neighbors) and to compute the MPR set. From neighbor lists, node B Figure out the nodes that are two hops away and computes the minimum set of one hop relay points required to reach the two-hop neighbors. Such set is the MPR set. Each node informs its neighbors about its MPR set in the HELLO message. Upon receiving such a HELLO, each node records the nodes (called MPR selectors) that select it as one of their MPRs. OLSR is particularly suited for dense networks. When the network is sparse, every neighbor of a node becomes a multipoint relay. The OLSR then reduces to a pure LS protocol. 2.1.2 Ad-Hoc On -demand Distance Vector (AODV) AODV is capable of both unicast and multicast routing (Charles et al 2010). It builds routes between nodes only as desired by source nodes and maintains these routes as long as they are needed by the source nodes. Control messages used for the discovery and breakage of route are as follows: 1. Route Request Message (RREQ): A route request packet is broadcasted through the network when a route is not available for the destination from source. Table 3 : Route Request message (Asar et al 2009) Source Address Request ID Source Seq. No Destination Address Destination Seq. No Hop Count

The new RREQ is discarded if there is already RREQ packet with same pair of parameters. A node that has no route entry for the destination, it rebroadcasts the RRER with incremented hop count parameter. A route reply (RREP) message is generated and sent back to source if a node has route with sequence number greater than or equal to that of RREQ (Asar et al 2009).

63

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011

www.iiste.org

Figure 3: Route Request (RREQ) flooding (Georgy et al 2009) 2. Route Reply Message (RREP): On having a valid route to the destination or if the node is destination, a RREP message is unicasted back to the source by the node. Table IV Route Reply message (Asar et al 2009) Source Address Destination Address Destination Seq. No. Hop Count

Life Time

The reason one can unicast RREP back is that every node forwarding a RREQ message caches a route back to the source node.

Figure 4: Route Reply (RREP) propagation (Georgy et al 2009) 3. Route Error Message (RERR): When a route that is active is lost, the neighborhood nodes are notified by route error message (RERR) on both sides of link. 4. Hello Messages: Hello messages are periodically broadcasted by active nodes and use to detect and monitor links to neighbors (Nitiket et al 2010). If a node fails to receive several Hello messages from a neighbor, a link break is detected. 2.1.3 Dynamic MANET On -Demand (DYMO) DYMO routing protocol is first defined in Internet Engineering Task Force (IETF) Internet-Draft and this paper uses the terminologies described in that draft (Ian et al 2011). The DYMO routing protocol is successor to the popular AODV Routing protocol and shares many of its benefits Using AODV as the basis, DYMO borrows Path Accumulation from DSR and removes unnecessary Route Reply (RREP), precursor lists and Hello messages , thus simplifying AODV (Narendran et al). This protocol has two basic operations 1. Route Discovery: In route discovery, when anode needs a route it initiates flooding of Route Requests (RREQ) throughout the network for finding the target node, where each intermediate node records the route to the originating node. On receiving the RREQ, the target node responds with a Route Reply (RREP) which is sent in a unicast, hop-by-hop fashion towards the originating node. The routes between the originating node and the target node are established in both directions. The information about the originator found in the RREQ is processed first, but subsequent entries are processed the same way: 1.1 If the routing table does not contain an entry for the originator, one is created. The next hop entry is the address of the node from which the RREQ was received. Likewise, the next hop interface is the interface on which the RREQ was received.

64

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011

www.iiste.org

1.2 If an entry exists, the sequence number and hop count found in the RREQ is compared to the sequence number route and hop count in the table entry to check if the information in the RREQ is stale or should be disregarded. 1.3 If an entry exists and is not stale or disregarded, the entry is updated with the information found in the RREQ.

Figure 5: DYMO Route discovery (Dhananjay et al 2009) 2. Route Management: Since DYMO applies to a context of a changing network topology; routes need to be actively monitored after being established. The protocol does not impose a monitoring mechanism, but specifies how this can be done with route timers. Each time a node creates or updates a route in its routing table, it can monitor the route with associated timers. To ensure that nodes can rely on the information they receive in RREPs, nodes are expected to keep their routes for a minimum amount of time.

When the route monitoring process detects a broken route, a broken flag is set for the corresponding route entry. If a node tries to use this route, a route error (RERR) message is flooded. The RERR contains information about the unreachable node, and may also contain information about nodes previously reachable through this node. A RERR warns other nodes that some nodes are no longer available through the sender of the RERR.

Figure 6: Generation and dissemination of RERR messages (Dhananjay et al 2009) 2.2. Performance Metrics Throughput Throughput is the measure of the number of packets or data successfully transmitted to their final destination via a communication link per unit time (Nital et al 2010). It is measured in bits per second (bit/s or bps). Packet Delivery Ratio It can be defined as the ratio of the data packets delivered to the destinations to those generated by the sources. Sometimes it is known as Packet Delivery Fraction (PDF) (Nital et al 2010, Anuj et al 2010). Mathematically, it can be expressed as:

65

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011

www.iiste.org

Where P is the fraction of successfully delivered packets, C is the total number of flow or connections, f is the unique flow id serving as index, Rf is the count of packets received from flow f and N f is the count of packets transmitted to f. End to End Delay It can be defined as the average time between packets sent and receive. It can be defined as:

Where N is the number of successfully received packets, i is unique packet identifier, r i is time at which a packet with unique id i is received, si is time at which a packet with unique id i is sent and D is measured in ms. It should be less for high performance (Nital et al 2010, Anuj et al 2010). Normalized Routing Load (NRL) It can be defined as the number of routing packets transmitted per data packet delivered at the destination. This metric gives an idea of the extra bandwidth consumed by overhead to deliver data packet (Sukanto et al 2010). NRL=((cp_sent+cp_forw)/data_agt_rec)*100; Where cp_sent = rreq + rrep + rerr; cp_sent =Controll Packets sent cp_forw=Control packet forwarded data_agt_rec=Data packets received rreq= route request rrep=route reply rerr=routeerror Packet Drop Rate/Ratio Packet drop ratio is calculated by subtract to the number of data packets sent to source and number of data packets received at destination through the number of packets originated by the application layer of the source (i.e. CBR source) (Nital et al 2010). 3. Experimental Result and Performance Analysis To measure the performance of the different protocols, two experiments have been carried out on the 1000m 1000m square simulation fields of different scales of sensor nodes and different mobility of sensor nodes. 3.1 Simulation scenario1: different density of the network In this scenario, all the three routing protocols are evaluated in different number of nodes, keeping other factors fixed and performance evaluated based on the four performance metrics which are Packet Delivery Fraction, End-to-End Delay, Normalized Routing load and Packet Drop Ratio. Table 4 list the simulation parameters applied in the experiments. Table 4: Simulation Parameter Parameter name Number of Nodes Pause Time Simulation time Traffic type Data Payload Mobility Model Value 10 to 90 (varying) 2 Seconds 180 seconds CBR 512 bytes/packet Random Way Point Algorithm

3.1.1 Packet Delivery Fraction Packet delivery ratio decreases with the increase of number of nodes. It shows the loss rate as seen by the transport layer, because more packets will be dropped at the interface queue.

66

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011

www.iiste.org

Figure 7: Packet Delivery Fractions in Scenario 1 From the above Figure, it is that packet delivery ratio of OLSR is best than other two. This is happen because in OLSR, whole networks information is available to all others nodes, so lower number of packet will be dropped for link breakage since alternate route can be found in routing table, where reactive protocols AODV and DYMO (on-demand protocol) drop a considerable number of packets during the route discovery phase, as route acquisition takes time proportional to the distance between the source and destination. 3.1.2 End-to-End Delay End-to-End delay increases with the increase of number of node. Because when number of node increases, more delay occurred because of node processing time, more queue management time. For better performance it should be low.

Figure 8: End-to-End delay in Scenario 1 From the graph in Figure 8, it is easily shown that increase rate of End-to-End delay for OLSR is less than others two and it is relatively smooth. But AODV and DYMO shows more peak. This is happen because AODV takes more time in route discovery phase, DYMO takes less time than AODV in route discovery and alternate route is immediately available in OLSR from its routing table. As topology is dynamically changing, so in some cases EED decrease instead of increase since at that case, route discovery phase takes less time. 3.1.3 Normalized Routing Load NRL increases with the increase of number of node. Because when a route is going to be setup, more nodes will be involved, so more control packet will be generated by the increased nodes. For better performance, it should be low.

67

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011

www.iiste.org

Figure 9: Normalized Routing Load in Scenario 1 From the graph in Figure 9 we see that, normalized routing load is maximum for DYMO than other two. Because besides route discovery, it generates huge hello message for local connectivity maintenance which exceed both AODV and OLSR. OLSR update its routing table in a pre-specified interval, so overhead at packet sending time is less and only selected MPR set can generate and retransmit control packet, not all the nodes. 3.1.4 Packet Drop ratio Packet Drop Ratio will be increase with the increase of Number of nodes as more packets will be dropped at interface queue. It should be low for high performance.

Figure10: Packet Drop Ratio in Scenario 1 From the above Figure, we see that DYMO drops more packets than others. Because at route discovery phase DYMO creates more routing load than others and OLSR has alternate route immediately available, so less drop ratio. 3.2. Simulation scenario 2: different mobility of the nodes In this scenario, all the three routing protocols are evaluated in different pause time, keeping other factors fixed and performance evaluated based on the four performance metrics which are Throughput, End-to-End Delay, Packet Drop Ratio and the Normalized Routing Load. Table VII list the simulation parameters applied in the experiments. Table 7: Simulation Parameters Parameter name Number of Nodes Pause Time Node Speed Value 20 0 to 100 Seconds (varying) 10 m/s

68

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011
Simulation time Traffic type Data Payload Mobility Model 100 seconds CBR 512 bytes/packet Random Way Point Algorithm

www.iiste.org

3.2.1 Throughput Throughput decreases with increase of mobility (lower pause time). As the packet drop at such a high mobility is much high. Large value of pause time means more stationary node. Also here more route break occurs, more routes needs to be setup, so more packet will be dropped at interface queue.

Figure 11: Throughput in Scenario 2 From the graph in Figure 11, it is easily shown that, OLSR has less effect on pause time when we consider throughput as it always needs to keep update of whole networks information. But in case of DYMO, when nodes becomes more stationary less control packet will be needed for route maintenance as data will be sent for longer time in the same route. So throughput increases. But AODV doesnt show uniform behavior. This is happen because though nodes become stationary, packet drop factors like queue overflow also depends on network arrangement. Here throughput of wireless channel is considered. 3.2.2 End-to-End Delay End to End Delay is decrease with increase of pause time, because probability of route breaks decrease with the increase of pause time. Large value of pause time means more stationary node. Also when more route break occurs, more routes needs to be setup. So more node processing happened & more delay occurred to deliver data to the destination.

Figure 12: End-to-End (EED) delay in Scenario 2 From the graph in Figure 12 we see that, EED decreasing rate of OLSR is more than others. Because when nodes becomes stationary, convergence time of OLSR for routing table calculation will also become less and route will be available soon. But AODV and DYMO shows similar nature as when route breaks occurs both setups routes on-demand. We also see that in high mobility, EED for DYMO is less as its convergence rate is high.

69

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011

www.iiste.org

3.2.3 Normalized Routing Load NRL decreases with the increase of pause time, because probability of route break decreases with the increase of pause time. Large value of pause time means more stationary node. Also when more route break occurs, more routes needs to be setup, so more control packet will be generated and more routing packet will be needed to send a data packet.

Figure 13: Normalized Routing Load in Scenario 2 From the graph in Figure 13, it is clear that OLSR needs more control packet to send a data packet as it needs to update the whole networks routing table and when nodes becomes more mobile, more route breaks occurs and convergence time also increase. But it is less for AODV and DYMO. 3.2.4 Packet Drop Ratio Packet drop ratio will be decrease with the increase of pause time. Since when nodes become more stationary, probability of route break and queue overflow will be low.

Figure 14: Packet Drop Ratio in Scenario 2 From the graph in Figure 14 we see that, OLSR has less effect on pause time when we consider packet drop ratio as it always needs to keep update of whole networks information. But in case of DYMO, when nodes becomes more stationary less control packet will be needed for route maintenance as data will be sent for longer time in the same route. But AODV doesnt show uniform behavior. This is happen because though nodes become stationary, drop factors like queue overflow also depends on network arrangement. 4. C o n c l usi o n an d O b s er v atio n To find out the best performance of this system, two experiments have been performed for this in two different scenarios. If Packet Delivery Ratio is our main requirement, then OLSR is better but it takes more resources to store the state of network topology. So if resources are limited, then AODV is better than OLSR. But when Endto-End delay is our main requirement, then in high mobility environment, DYMO is better and if density of the network is dynamically changing then OLSR is better. If Normalized Routing Load is our main requirement, then in high mobility environment DYMO is better than other two. In such environment, OLSR shows worst behavior as its convergence time is high and needs more control packets exchange. But if we consider different density of the network then AODV is better; because in such case less control packet is needed than other two

70

Computer Engineering and Intelligent Systems ISSN 2222-1719 (Paper) ISSN 2222-2863 (Online) Vol 2, No.4, 2011

www.iiste.org

protocols. If Packet Drop Ratio is our main requirement, then AODV may be preferable as its drop ratio is less. If Throughput is our main requirement, then DYMO is better in high mobility environment as it has high adaptation rate and relatively low loss rate. R e f er en c es Kevin Fall & Kannan Varadhan (Eds.) (2010), The ns Manual (formerly ns Notes and Documentation), The VINT Project, A Collaboration between researchers at UC Berkeley, LBL, USC/ISI, and Xerox PARC. Charles E. Perkins & Elizabeth M. Royer (1999) Ad Hoc On-Demand Distance Vector Routing, in Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, pp- 90-100. Ian D. Chakeres & Charles E. Perkins, (2011) Dynamic MANET on demand (DYMO) routing protocol. Internet-Draft Version 21, IETF. Aleksandr Huhtonen, (2004) Comparing AODV and OLSR Routing Protocols, Helsinki University of Technology Telecommunication Software and Multimedia Laborator. Asma Tuteja, Rajneesh Gujral & Sunil Thalia, (2010) Comparative Performance Analysis of DSDV, AODV and DSR Routing Protocols in MANET using NS2, 2010 International Conference on Advances in Computer Engineering, IEEE Computer Society, DOI 10.1109/ACE.2010.16. Fotis Diamantopoulos & Anastasios A. Economides, (2006) A performance study of DSDV based CLUSTERPOW and DSDV routing algorithms for sensor network applications, University of Macedonia, Proceedings IEEE International Symposium on Wireless Pervasive computing. Ian D. Chakeres & Elizabeth M. Belding-Royer, (2004) AODV routing protocol implementation design, Proceeding ICDCSW '04 Proceedings of the 24th International Conference on Distributed Computing Systems Workshops - W7: EC (ICDCSW'04) 7 Computer Society Washington, DC, USA. Asar Ali & Zeeshan Akbar, (2009) Evaluation of AODV and DSR Routing Protocols of Wireless Sensor Networks for Monitoring Applications, Department of Electrical Engineering with emphasis on Telecommunication, Blekinge Institute of technology. Georgy Sklyarenko & Zuriati Ahmad Zukarnain, (2009) Performance Comparison of AODV, DSDV and IDSDV Routing Protocols in Mobile Ad Hoc Networks, ISSN 1450-216X, 31(4) pp-566-576. Nitiket N Mhala & N K Choudhari, (2010) An Implementation Possibilities For AODV Routing Protocol In Real World, International Journal of Distributed and Parallel Systems (IJDPS) 1(2). Narendran Sivakumar & Satish Kumar Jaiswal, Comparison of DYMO protocol with respect to various quantitative performance metrics, Department of Computer Science, Malardalen University. Dhananjay Bisen, Preetam Suman, Prof. Sanjeev Sharma & Rajesh Shukla, (2009)Effect of Pause Time on DSR, AODV and DYMO Routing Protocols in MANET . Nital Mistry, Devesh C Jinwala, Member, IAENG and Mukesh Zaveri (2010) Improving AODV Protocol against Blackhole Attacks, Proceedings of the International Multiconfarence of Engineers and Computer Scientists(IMECS) 2. Anuj K. Gupta & Dr. Anil K. Verma, (2010) Performance analysis of AODV, DSR & TORA Routing Protocols, IACSIT International Journal of Engineering and Technology, 2(2). Sukant Kishoro Bisoyi & Sarita Sahu, (2010) Performance analysis of Dynamic MANET On- demand (DYMO) Routing protocol, Special Issue of IJCCT, 1(2, 3, 4); 2010 for International Conference [ACCTA2010].

71