Routing Protocols in Mobile Adhoc Networks
Active In SP
Joined: Oct 2009
24-10-2009, 02:07 PM
Routing Protocols in Mobile Adhoc Networks.doc (Size: 324 KB / Downloads: 279)
Routing Protocols in Mobile Adhoc Networks.ppt (Size: 358.5 KB / Downloads: 408)
Ad Hoc network is a big collection of wireless mobile hosts forming a temporary network without the aid of any centralized administration, in which individual nodes cooperate by forwarding packets to each other to allow nodes to communicate beyond direct wireless transmission range. Routing is a process of exchanging information from one station to other stations of the network. Routing protocols of mobile ad-hoc network tend to need different approaches from existing Internet protocols because of dynamic topology, mobile host, distributed environment, less bandwidth, less battery power. Ad Hoc routing protocols can be divided into two categories: table-driven (proactive schemes) and on-demand routing (reactive scheme) based on when and how the routes are discovered. In Table-driven routing protocols each node maintains one or more tables containing routing information about nodes in the network whereas in on-demand routing the routes are created as and when required. Some of the table driven routing protocols are Destination Sequenced Distance Vector Routing protocols (DSDV), Clusterhead Gateway Switching Routing Protocol (CGSR), Hierarchical State Routing (HSR), and Wireless Routing Protocol (WRP) etc. The on-demand routing protocols are Ad Hoc On-Demand Distance Vector Routing (AODV), Dynamic Source Routing (DSR), and Temporally Ordered Routing Algorithm (TORA). There are many others routing protocols available. Zone Routing Protocol (ZRP) is the hybrid routing protocol.
Active In SP
Joined: Feb 2011
20-04-2011, 09:44 AM
Routing in MANET.doc (Size: 217 KB / Downloads: 71)
Ad-hoc networks are temporary networks that are used only for the duration of the communication sessions. Cellular phones, laptops etc are the devices that used for mobile networks. However, mobile devices can be classified in to the following two categories:
Networks having a fixed infrastructure using a base station that covers a certain areas. During communication mobile devices communicates with the nearest base station that transmits the information to other base station or wired networks or other mobile devices. Cellular phone is the example of this type of network.
Network without having a fixed infrastructure is another promising type of network used in communication. It is used for any planned or unplanned events like in war fields or in a meeting of business people scattered geographically. However, this type of network can be created or destroyed when needed and that is why the name is mobile ad-hoc network and it has no central; controlling authority.
However, following are the protocols that are used for mobile ad-hoc networks:
2.1 Proactive protocols:
In this type of routing protocol, each node in a network maintains one or more routing tables which are updated regularly. Each node sends a broadcast message to the entire network if there is a change in the network topology. However, it incurs additional overhead cost due to maintaining up-to-date information and as a result; throughput of the network may be affected but it provides the actual information to the availability of the network. Distance vector (DV) protocol, Destination Sequenced Distance Vector (DSDV) protocol, Wireless Routing protocol Fisheye State Routing (FSR) protocol are the examples of Proactive protocols.
2.2 Reactive Protocols:
In this type of routing protocol, each node in a network discovers or maintains a route based on-demand. It floods a control message by global broadcast during discovering a route and when route is discovered then bandwidth is used for data transmission. The main advantage is that this protocol needs less touting information but the disadvantages are that it produces huge control packets due to route discovery during topology changes which occurs frequently in MANETs and it incurs higher latency. The examples of this type of protocol are Dynamic Source Routing (DSR), Ad-hoc On Demand Routing (AODV) and Associativity Based Routing (ABR) protocols.
2.3 Hybrid Protocols:
It is a combination of proactive and reactive protocols taking the best features from both worlds.
Four Routing Protocols:
In this report, the following four routing protocols have been discussed but only implementation and analysis for AODV and DSR are shown.
3.1 Distance Vector (DV) Protocol:
It is a proactive protocol that works on the principles of distance vector where each node in a network maintains a distance table that contains the shortest distance and the address of the next hop router. Initially, each node knows only the distance with the nodes that are directly connected and a distance vector is initialized with that distance. Initially, distance to all others nodes that are not directly connected are initialized to infinity. When a change occurs in the network, each node updates its directly connected neighbors to the least cost distance vector. This process continues until convergence.
The advantages of distant vector protocol are 1) No need for global broadcasting and 2) Short route acquisition delay since all information for each node are available in the routing table. The disadvantages are 1) Long convergence time which may cause counting to infinity problem for large networks, 2) Non-availability of alternative paths.
3.2 Wireless Routing Protocol (WRP):
It is an improved version of the distant vector protocol that eliminates the count-to-infinity problems and thereby decreasing the convergence time. It has some disadvantages also. It requires larger memory and greater processing. It is also not suitable large networks with mobility. However, in WRP, each node in a network maintains the following four tables:
1) Link Cost Table: Each node contains cost and other information like identifier to the directly connected nodes. The cost of a broken link is identified by infinity.
2) Distance Table: In this table, each node contains information to the nodes that are not directly connected.
3) Routing Table: It contains the shortest distance and the up-to-date information of all destinations.
4) Message Retransmission List (MRL): Each node in a network sends a hello message to its neighbors and informs them that he is alive and waits for the acknowledgement (ACK) from its neighbors. If it does get any ACK from any neighbors within a certain time, then keeps this information to MRL list. Next time it will send update message to nodes only that did not reply to the hello message.
3.3 Dynamic Source Routing (DSR) Protocol:
It is a reactive protocol that creates a route on demand using source routing protocol i.e. it requires a full series of paths to be established between source and destination nodes to transmit packets and each packet follows the same path. The major motivations of this protocol are to limit the bandwidth by avoiding the periodic table updates and long convergence time. The underline fact to this protocol is that it floods a route request message in the network to establish a route and it consists of two procedures: Route Discovery and Route Maintenance.
4 Route Discovery:
As it is an on-demand routing protocol, so it looks up the routing during transmission of a packet. At the first phase, the transmitting node search its route cache to see whether there is a valid destination exists and if so, then the node starts transmitting to the destination node and the route discovery process end here. If there is no destination address then the node broadcasts the route request packet to reach the destination. When the destination node gets this packet, it returns the learned path to the source node.
5 Route Maintenance:
It is a process of broadcasting a message by a node to all other nodes informing the network or node failure in a network. It provides an early detection of node or link failure since wireless networks utilize hop-to-hop acknowledge.
The advantage of this protocol are 1) Aware of existence of alternative paths that helps to find another path in case of node or link failure. 2) It avoids routing loops and 3) less maintenance overhead cost as it an on-demand routing protocol. On the other side, the disadvantages are 1) Long route acquisition delay for the route discovery which may not be acceptable in situations like the battle field. 2) It is not suitable for large number of nodes where speed may suffer and 3) it produced huge messaging overhead during busy times.
6 Ad-hoc On-demand Distance Vector (AODV) Protocol:
It is a classical routing protocol for MANETs that compromise the trade-off problems like large packet header in reactive source protocol and large messaging overhead due to periodic updates in proactive protocols. It uses a distributed approach i.e. it keeps track of the neighbor nodes only and it does not establish a series of paths to reach the destination. It also uses route discovery and route maintenance mechanism like DSR.
7 Route Discovery:
A source node send a broadcast message to its neighboring nodes if no route is available for the desired destination containing source address, source sequence number, destination address, destination sequence number, broadcast ID and hop count. Two pointers such as forward pointer and backward pointer are used during route discovery. Forward pointers keep track of the intermediate nodes while message being forwarded to destination node. Eventually, when route request message reached the destination node, it then unicast the reply message to the source via the intermediate nodes and the backward pointer keeps track of the nodes. The major feature of AODV that distinguish it from DSR is the destination sequence number which is used to verify the up-to-date path to the destination.
Three types of messages exchanged between source and destination such as route error message, hello message and time out message. Route error message ensures that this message will be broadcasted to all nodes because when a node observes a failed link, it will propagate this message to its upstream nodes towards source node only. Hello message ensures the forward and backward pointers from expiration. Time out message guarantees the deletion of link when there is no activity for a certain amount of time between source and the destination node.
Main advantages are 1) it is an efficient algorithm for mobile ad-hoc networks and it is scalable 2) it takes short time for convergence and is a loop free protocol and 3) messaging overhead to announce the link failure is less compared DSR. The main disadvantage is that it needs huge bandwidth to keep maintain periodic hello message.
7 Simulation Experiments:
Experimental modeling, design, results and analysis are described below to compare the performance of two routing protocols such as DSR and AODV.
7.1 Experimental Design:
A parallel event-driven simulator, Glomosim was used for comparing the results of two protocols. Simulation experiments were run on two desktop PCs with different speed and memory capacity though there were no effects of speed and memory capacity on the experimental results.
Mean end-to-end delay, packet delivery rate and routing overhead as measured by the number of control packets generated for routing are the performance matrices that were used to compare the two routing protocols.
1. Mean end-to-end delay: Average time taken for a packet to travel from source to destination including route acquision delay.
2. Packet delivery rate: Ratio of packets successfully delivered to the destination to the total number of packets transmitted by the source node.
3. Messaging overhead: Total number of control packets generated for routing.
Node density, node mobility and traffic are the three control parameters used for this simulation. Mean end-to-end delay, packet delivery rate and routing overhead were measured for node mobility in experiment 1 and node density were for three different levels of traffic load in experiment 2. Constant bit rate generator was used for generating packets of fixed size. Three different types of traffic load were used for simulation such as 1) Low traffic load – one packet transmitted every 10 seconds, 2) medium traffic load – one packet every second and 3) High traffic load – one packet every 0.1 second.
The following are the parameters that were used for configuring input file in the simulation:
1) Terrain size : 200 m X 200 m
2) Radio signal transmission range: 175 m
3) Link bandwidth: 2 Mbps
4) Simulation time: 500 s
5) Packet size: 1460 bytes
6) Node placement: Random Way Point
7) Propagation model: Free space
8) Transport layer protocol: UDP
9) MAC layer protocol: IEEE 802.11
10) Routing protocol: AODV and DSR
11) Number of nodes: 50, 75 and 100 respectively
12) Number of packet sender nodes: 25 (randomly selected)
13) Number of packet receiver nodes:25 (randomly selected)
14) Node speed: 45 km/h
15) Pause time: 0s, 120s, 300s, 400s and 500s respectively.
16) Seed value: Randomly selected between 1 and 10