The mobile adhoc network is highly dynamic and the nodes are mobile. It is a challenge to develop routing protocol that can meet different application needs and optimize routing paths according to the topology change in mobile adhoc networks. Basing their forwarding decisions only on the local topology, geographic routing protocols have drawn a lot of attentions in recent years. Providing reliable broadcasting is a challenging task. This paper analyses about various routing protocols available for routing packets between mobile nodes in Mobile Adhoc Network.
Keywords |
| Mobile Adhoc Network, Topology, Routing Protocol |
INTRODUCTION |
| Today’s Internet is very fast and effective. Currently many network researchers are working on networks
based on modern communication techniques, particularly wireless communications. Without the constraints of wired
connections, wireless networks allow their hosts to roam. Mobile users can move around but still they are staying
connected to the network. Notebook computer connectivity, Handheld personal computer connectivity, vehicle and ship
networks are applications of this kind of network. We can deploy a wireless network quickly and easily. Such networks
play vital role in both military and civilian systems [1]. |
| A Mobile Ad Hoc Network (MANET) is a set of nodes which can communicate with each other using multihop
wireless links. A node can directly communicate with only those nodes which are in its communication range [2].
The intermediate nodes which are in between the source node and the destination node forward messages to the nodes
that are more than one hop distance from the source. Since the nodes are mobile, this network topology is ever
changing. Hence in Mobile Ad hoc networks, the development of effective routing protocols that provide high quality
communication is an important challenge. This paper discusses about the various routing protocols available for routing
packets between mobile nodes in Mobile Adhoc Network. |
| The remaining sections are organized as follows. Section 2 presents summarizes the limitations of MANET routing
protocols, section 3 analyzes and briefly discusses about the MANET routing protocols for their efficiency and
performance. Section 4 summarizes the paper. |
LIMITATIONS OF MANET |
| The nodes in MANET have limited communication resources such as buffer space, bandwidth, battery power
etc. These resource constraints in MANET require the traffic to be properly distributed among the mobile host. A
routing protocol in MANET should fairly distribute the routing tasks among the mobile hosts. Hosts and routers in a
wireless network can move around. Therefore, the network topology can be dynamic and unpredictable. Traditional
routing protocols used for wired networks cannot be directly applied to most wireless networks because some common
assumptions are not valid in this kind of dynamic network [3]. For example, one assumption is that a node can receive
any broadcast message sent by others in the same subnet. However, this may not be true for nodes in a wireless mobile
network. The bandwidth in this kind of network is usually limited. Thus, this network model introduces great
challenges for routing protocols. MANET applications usually have bandwidth and, often, power constraints.
Therefore, overhead is an important issue for routing protocols in MANETs. |
| A. Applications of MANETs |
| Mobile AdHoc Network can be applied to the following areas: |
| • Virtual classrooms |
| • Military communications |
| • Emergency search and rescue-operation |
| • Data acquisition in hostile environments |
| • Communication set-up in exhibitions, conferences, presentations, meetings, lectures, etc. |
ANALYSIS ON MANET ROUTING PROTOCOLS |
| We have analyzed nine well known routing protocols for MANET. Before discussing the routing protocols’
performance analysis and results, in this section we briefly mention the operational methods and major features of these
protocols. |
| A. Open Shortest Path First (OSPF) |
| Open Shortest Path First (OSPF) [4] is a link state routing protocol. It is a mature proactive routing protocol widely
used in today’s wired networks. An identical topology database is maintained in all routers so that each node can build
its own local routing tables. Since the routing tables are built based on shortest path tree, a route identified by OSPF is
acyclic and always the shortest path. It maintains routes to all possible destinations continuously. Hence, it is
favourable for networks where many number of hosts in one subnet always communicate with hosts in other subnets. It
is a complex routing algorithm. OSPF is the overhead for control packets which are needed to maintain the link state
database. |
| Two major operations in OSPF are |
| 1. Determining adjacency |
| 2. Synchronizing the link state database |
| Five types of route control packets are used to support the above said two operations: |
| (i) Hello packets |
| (ii) Database description packets |
| (iii) Link state request packets |
| (iv) Link state update packets |
| (v) Link state acknowledgement packets |
| B. Dynamic Destination-Sequenced Distance-Vector Routing Protocol (DSDV) |
| Based on Bellman-Ford routing algorithm, DSDV is developed. It is a proactive routing protocol. Each mobile
node keeps a routing table which contains the list of all available destinations and the number of hops to each
destination. Routing table entry is labelled with a sequence number originated by the destination node. |
| Any update in the routing table is periodically transmitted and any new significant change is transmitted
immediately (periodic or event-driven). It helps to maintain the topology information of the network. Each mobile node
in DSDV advertises its own routing table to its neighbours. This advertisement is either broadcasted or multicasted [5].
By doing this, the neighbouring nodes know about the changes happened in the network due to the movements of
nodes. |
| Any updates in the routing table can be sent in two ways: |
| 1. Full dump |
| 2. Incremental |
| In full dump update method, the whole routing table is sent to the neighbours. In incremental update, only the entries
that require changes are sent. When there is no movement of nodes, full dump is transmitted less frequently. The
incremental update method is more appropriate when the network is stable so that extra traffic can be avoided. But,
when the movements of nodes occur often, the incremental updates sizes become large and approach the Network
Protocol Data Unit (NPDU). Hence, in such cases full dump method must be used. Transmitter assigns a sequence
number to each route update packet. In order to update the routing information in a node, the update packet with the
highest sequence number is used that means the most recent update packet. Each node will wait for some time interval
to advertise to its neighbours. Hence the latest information of better route to a destination will be informed to its
neighbours. |
| C. Temporally-Ordered Routing Algorithm (TORA) |
| Temporally-Ordered Routing Algorithm is an adaptive routing protocol used in multihop networks [6]. It
combines reactive and proactive routing. It is a distributed algorithm. Hence the routers need to maintain knowledge
about their neighbours only. On a predestination basis, TORA maintains states. Source node initiates route requests in a
reactive mode and simultaneously selected destinations can start proactive operations to construct routing tables.
Normally, routes to these destinations may be frequently or consistently required such routes are routes to servers or
gateways. TORA adapts to network topology changes as it supports multiple path routing. Since multiple paths are
used in TORA, routes may not be the shortest ones always. |
| TORA uses the routing metric height associated with particular destinations. Routers with higher heights
forward packet to neighbours with lower heights just like water flows in the pipes. As an independent copy of TORA
runs for each possible destination, routers may have different heights and links can have different directions. |
| TORA allocates directions to links ‘upstream’ or ‘downstream’. A link is an upstream link when neighbouring
router is “lower” and downstream link for the “higher” neighbouring router. |
| When compared with DSR, TORA is a complex algorithm. It has four operations: |
| (i) Routes Creation |
| (ii) Routes Maintenance |
| (iii) Routes Removal |
| (iv) Routes Optimization |
| Route creation operation selects proper heights for routers and forms a directed sequence of links which leads
to the destination in a previously undirected network. Route maintenance procedure responds to network topology
changes. Route removal sets the routers’ heights = NULL and makes the links undirected. Routes optimization
procedure adjusts the heights of routers to improve routing performance. There are 4 packets used to perform the above
said operations: Update (UPD), Query (QRY), Clear (CLR) and Optimize (OPT). |
| While maintaining routes, if a partition of the network is identified, the router with no downstream links
executes the procedures to remove routes. The node broadcasts CLR packet with the related destination and relevant
parameters. Once the removal procedure to erase routes is executed, routers heights and link directions are reset. |
| D. Dynamic Source Routing (DSR) |
| Dynamic Source Routing is a reactive routing protocol that allows the nodes in MANET to dynamically
identify a source route through multiple network hops to any destination. The mobile nodes keep the known routes in
the route caches. Whenever a new route is known, it must be updated in the cache. |
| In DSR, routing is done in two stages: route discovery and maintenance. When a node needs to send packets to any
destination, it searches its route cache to identify whether already known route to the destination available or not. If
there is such an entry to the particular destination, the source node uses that route to send the packet [7]. Otherwise it
broadcasts a route request. It includes the source address, destination address and unique identification number. Each
intermediate node checks whether it knows the destination or not. If the intermediate node does not know about the destination, it forwards the packet. Eventually this route request packet reaches the destination. Any intermediate node
processes the route request packet only if its address does not exist in the route record of the packet and it has not
previously processed the packet. When any node knows the route to reach the destination, a route reply packet is
created and sent to the source node. Sometimes it may be sent by the destination itself or by of the intermediate nodes. |
| E. Ad Hoc On-Demand Distance Vector Routing (AODV) |
| Ad Hoc On-Demand Distance Vector Routing [6] is basically an enhancement of Dynamic Destination-
Sequenced Distance-Vector (DSDV) routing protocol. But, it is a reactive routing protocol rather than being proactive.
It creates routes based on the demand hence it minimizes the number of broadcasts which is not the case in DSDV.
When a source node wants to send packet to any destination, it broadcasts a route request (RREQ) packet [1]. In turn
the neighbouring nodes broadcast the packet to their neighbour nodes and this process continues till RREQ reaches the
destination. While forwarding the route request, the intermediate nodes record the address of the neighbour from which
it receives the first copy of RREQ. This information is stored in their route tables to establish a reverse path. If same
copies of RREQ are received later, those packets are discarded. The reply is sent using the reverse path. For
maintaining routes, when a source node moves, it reinitiates route discovery process. If any intermediate node moves
within a particular route, the neighbour of the floated node detects the link failure and it sends this failure notification
to its upstream neighbour. It continues till the failure notification reaches the source node. The source node may decide
to reinitiate the route discovery phase based on the received information. |
| F. Optimized Link State Routing Protocol (OLSR) |
| Optimized Link State Routing protocol is a proactive link state routing protocol used in MANET. Comparing
with pure flooding mechanisms, OLSR, using Multi Point Relays (MPR), reduces control overhead by reducing the
number of broadcasts [3]. During the flooding process, MPR uses only selected routers to forward broadcast messages.
Every router declares only a small subset of all of its neighbors in order to reduce the size of broadcast messages.
OLSR is particularly suitable for huge and dense networks [3]. |
| In route discovery procedures, Multi Point Relays act as intermediate routers. Hence, the path identified by
OLSR may not be the shortest path. This is a major disadvantage of OLSR. |
| It has three functions: |
| 1. Packet forwarding |
| 2. Neighbor sensing |
| 3. Topology discovery |
| G. Topology Broadcast Based on Reverse-Path Forwarding (TBRPF) |
| The Topology Broadcast Based on Reverse-Path Forwarding (TBRPF) protocol is a link state, proactive
routing protocol used in MANETs [4]. Each router in this protocol constructs a source tree to all possible destinations
using partial topology information which is locally stored. It is the shortest path tree. In TBRPF the routers only
broadcast part of their source tree to their neighbours to reduce overhead. The partial source tree is called the reportable
tree. In the local copy of network topology, if a link is in the shortest path tree, this link cost is equal to the actual value.
Otherwise, the cost is greater than or equal to the real value. TBRPF is said to work better in dense networks [7]. |
| The reportable tree at a router is generated as follows: |
| Links that are in this router’s shortest path tree are checked |
| If the link is in the neighbors’ shortest path trees, it is added to the reportable tree |
| There are two modules in TBRPF: |
| 1. The neighbor discovery (TND) module |
| 2. The topology discovery and route computation module |
| TND uses differential HELLO messages which report only status changes in the neighbours [48]. It reduces
the size of HELLO packets. The HELLO packet contains three lists of router IDs in three different formats: |
| 1. Neighbour Request |
| 2. Neighbour Reply |
| 3. Neighbour Lost |
| Reportable trees are built in all routers. When these are broadcast, link information is propagated to all routers in this
network. If a router spots a link failure or detects a new link, it notifies its neighbours and its source tree is affected by
the changed new link. TBRPF may guarantee that correct shortest path trees in all routers are built using redundant
estimations. |
| H. Landmark Routing Protocol (LANMAR) |
| LANMAR is a proactive protocol for large-scale ad hoc networks. It uses the idea of logical subnets where the
members have common interest and are likely to move as a group [5]. In LANMAR, a router is elected as the landmark
in a subnet. It must have the knowledge of all the members in its group. This notion of LANMAR looks similar to the
designated router in broadcast network used in the OSPF protocol. Each router has to maintain distance vector to
landmarks in every subnet. In LANMAR, landmarks are elected based on the weight of routers such as the degree in
one subnet. If a tie occurs, the router with the lowest ID is selected. |
| LANMAR relies on a proactive routing protocol within each subnet. This protocol provides scoped routing i.e.
maximum number of hops in each subnet. It works with LANMAR and produces information about other routers in the
scoped area during the selection of a landmark. |
| I. Fisheye State Routing Protocol (FSR) |
| The Fisheye State Routing protocol [6] is used as the underlying protocol for LANMAR. It uses various
update frequencies based on the distance to that destination. A router uses the underlying protocol to periodically
update the routing information for destinations within the same subnet. For the routers lying outside the scoped area,
landmarks update the routing information with a non-zero frequency. Other routers use the route toward the landmark
of their subnet as the default route to a remote host or group if they do not have a direct connection to the remote
destination. Routes between subnets are not optimal because the landmark in one subnet is not guaranteed to be in the
shortest path from one router in this subnet to a destination outside of this subnet. |
| J. Zone Routing Protocol (ZRP) |
| The Zone Routing Protocol is a prototype routing protocol. It is created using two sub-protocols, |
| 1. Intrazone Routing Protocol (IARP) |
| 2. Interzone Routing Protocol (IERP) |
| Intrazone Routing Protocol is a limited scope proactive routing protocol used to improve the performance of
globally existing reactive routing protocols [7]. It relies on neighbour discovery protocol (NDP) for neighbour
information. IARP uses the Time-To-Live (TTL) field in IP packets to control the zone range. When a packet passes
through a router, TTL is decremented by 1 and then it is rebroadcast. When TTL equals to ‘0’, the packet is not
rebroadcast. |
| Interzone Routing Protocol is the reactive routing protocol of ZRP [5]. It does the job of detecting a global path.
ZRP has the advantages of both proactive and reactive routing protocols. But it lacks in route optimization. |
| K. Mobile IP |
| Mobile IP let its hosts and routers to roam seamlessly among IP subnetworks without any addressing
constraints. In this routing protocol there are two agents |
| 1. Home Agent (HA) |
| 2. Foreign Agent (FA) |
| When a mobile node is away from its home network, Home Agent keeps information about the current
location of the mobile node and delivers packets through tunnelling. When a mobile node enters a new network, it has to register with a Foreign Agent through which it gets services. The tunnelled packets from a HA will be detunnelled
by a Foreign Agent and forwards it to the mobile node. But to apply Mobile IP to MANET requires additional features
and investigation. |
CONCLUSION |
| We have analysed various routing protocols that are applicable for Mobile Adhoc Networks. Among these protocols
some are reactive protocols and some are proactive protocols and some are combination of proactive and reactive
namely hybrid protocols. These routing protocols have different criteria for route selection and to optimize the use of
MANET resources and to improve MANET performance. With the selection of appropriate routing protocol, Mobile
Adhoc Network can maximize packet delivery ratio, mobile nodes lifetime, throughput and minimize traffic congestion
and load unbalance. Hence the end-to-end packet delivery delay can be minimized and network energy consumption
can be balanced. |
Figures at a glance |
 |
| Figure 1 |
|
| |
References |
- Charles E. Perkins, “Ad Hoc Networking”, Publisher Addison Wesley, 2001.
- Jun Zhao Sun and J. Sauvola, “On Fundamental Concept of Mobility for Mobile Communications”, Proc. Of 13th IEEE InternationalSymposium on Personal, Indoor and Mobile Radio Communication, Lisbon, Portugal, vol. 2, pp. 799-803, 2002.
- C. Siva Ram Murthy and B.S. Manoj, “Ad Hoc Wireless Networks Architecture and Protocols”, Pearson Education, 2005.
- C. E. Perkins, P. Bhagwat, “Highly Dynamic Destination Sequenced Distance Vector Routing for Mobile Computers”, Proc. Of ComputerCommunication Rev. (1994), vol. 1, pp. 234-244.
- S. Murthy, J. J. Garcia-Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks”, ACM/Baltzer Mobile Networks andApplications (1996), vol. 1, no. 2, pp. 183-197.
- G. Pei, M. Gerla, T-W. Chen, “Fisheye State Routing: a routing scheme for Ad Hoc Wireless Networks”, IEEE International Conferenceon Communications (2000), vol. 1, pp. 70-74.
- S. Basagni, I. Chlamtac, V. R. Syrotivk, B. A. Woodward, “A Distace Routing Effect Algorithm for Mobility (DREAM)”, Proc. of fourthannual ACM/IEEE International Conference on Mobile Computing and Networking Mobicom’98, Dallas, Tx. (1998), pp. 76-84.
|
Menu