This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
In proactive protocols the topological information is exchanged among all the nodes in a network. Thus, when there is a need for a route to a destination, such route information is available immediately. These protocols require each node to keep up to date routing information in different tables and to propagate updates throughout the network. As such these protocols are often called as table-driven. Periodic route updates are exchanged in order to synchronize the tables. These protocols try and maintain valid routes to all communication mobile nodes all the time before a route is actually desired. To achieve this, control messages are transmitted amongst the nodes periodically. These protocols are not bandwidth efficient because of the control messages that are broadcasted even when there is no actual data flow. However, these protocols differ in the way routing information is updated and detected, the number of routing tables used, the type of information stored in each table and the changes that are periodically broadcasted in the network. This class of routing protocols has its own advantages and disadvantages. One of its main advantages is the fact that nodes can easily get routing information and it's easy to establish a session. The disadvantage is too much data stored by the nodes for route maintenance and it is slow to restructure when there is a failure in a particular node link.
Some of the existing proactive routing protocols are:
Destination Sequenced Distance-Vector Routing Protocol (DSDV)
Optimized Link State Routing Protocol (OLSR)
Wireless Routing Protocol (WRP)
Source Tree Adaptive Routing (STAR)
Cluster Switch Gateway Routing (CGSR)
Gateway Switch Routing (GSR)
Fisheye State Routing (FSR)
Perkins et al. (1994) have proposed some modifications to the traditional Bellman-Ford routing mechanism, thus making it suitable for mobile ad hoc networks. This protocol work on the distance vector routing technique, thus named as Destination Sequenced Distance Vector routing protocol. All the processes of route discovery and data transfer are done through sequence numbers assigned to each and every packet that move from source node to destination node. One of the major problems of the previous Bellman-Ford algorithm was loop formation in case of broken links and changing topology. Different ways have been described and some revisions were proposed to provide MAC layer support for MANETs. In this protocol, routing tables are formed at each node which contains all the available information regarding nodes. The data is transferred with the help of a sequence number that is initiated by the destination node. Each node keeps on sending updates as soon as there is any change in the location, topology, etc. in the network. Before the actual data transfer each node advertises itself to its neighbouring nodes and shares its routing table. This helps a mobile node in data exchange with other nodes even if the destination is not within its range. When the packet is sent from source node it contains destination address, number of hops required and sequence number. Routes with recent sequence number are always preferred. In the case that two routes have a same sequence number, the one with a better cost metric is preferred. One important modification was responding to topology change which may cause link failures. Link breaks as nodes move from one location to other. In DSDV, a link failure is described by âˆž (infinity). Whenever any node detects a link to its next node as broken, it immediately assigns âˆž and updates the sequence number. When any node receives a âˆž, it issues a route update message and broadcast it to all the nodes following that route. So, the DSDV protocol guarantees loop-free routes to every destination as it provides only a single path to a destination which is selected using shortest path routing. In order to minimize the overhead caused in routing DSDV uses two types of packets - full dump and incremental. The full dump carries all the available information about routing whereas incremental only carries the changed information since the last full dump. But still DSDV incurs large amounts of overhead due to update messages which are periodically sent by the nodes. So this protocol does not scale well in large size networks since a large part of the available bandwidth is wasted in sending update messages only. An alternative is to propose a technique that performs routing operations as and when needed i.e. on-demand.
Hu, Johnson and Perrig presented SEAD (Secure Efficient Ad hoc Distance vector routing), a lightweight secure routing protocol based on DSDV. The same authors present Ariadne which is a secure on-demand routing protocol based on DSR. The main difference between these two systems is that SEAD authenticates messages in each hop while Ariadne operates on an end-to-end basis.
Murthy and Garciaproposed Wireless Routing Protocol based on familiar Bellman-Ford algorithm. It works similar to DSDV in which each node maintains a routing table that contains an entry for each destination with the next hop and cost. Next hop is used to select the immediate neighbor node for forwarding packets. In addition to DSDV, link costs are also stored in a separate table. All the tables keep on updating themselves as the topology changes with the help of HELLO messages but only the recent path updation is considered instead of whole routing table to send data. The main goal is maintaining routing information among all nodes in the network regarding the shortest distance to every destination. Each node in the network uses a set of four tables to maintain more accurate information:
Distance table (DT)
Routing table (RT)
Link-cost table (LCT)
Message retransmission list (MRL) table
DT contains network view of the neighbours of a node. RT contains the up-to-date view of the network for all identified destinations. LCT contains the cost required to relay messages through each link. MRL table contains an entry for every update that is to be retransmitted and also maintains a counter for that. Each entry contains a sequence number, a retransmission counter, an acknowledgment and a list of updates sent in the update message. It also records which neighbours should acknowledge the retransmission. Creating and maintaining a number of tables bear an extra overhead at each node if the size of network keeps on increasing. Also WRP has one more drawback of sending empty HELLO messages to keep the links updated which consume a significant amount of bandwidth and power at each node. WRP belongs to the class of path-finding algorithms with an important exception. It counters the "count-to-infinity" problem by forcing each node to perform consistency checks of predecessor information reported by all its neighbours. This eliminates looping situations and enables faster route convergence when a link failure occurs.
Clausen et al. designed the Optimized Link State Routing protocol which was an improvement to the traditional link state protocols through few optimizations concerned with MANETs. OLSR is a point to point routing protocol which optimizes the network by focusing on specially selected nodes called multipoint relays (MPR). Only these nodes are capable of forwarding the messages during route discovery process. This in turn reduces the number of messages broadcasted thus minimizes the routing overhead. Also only MPRs generate the link state information and share this information with other MPRs. OLSR aims to minimize the flooding within the network as each node does not have to forward data to all of its neighbours.. It can forward to its respective MPR which can further forward it on the route established. Only MPRs broadcasts the packets. MPRs are chosen on the criteria that they are attached with maximum number of nodes so that least number of packets may be broadcasted. During each update a node selects a set of neighbours to forward its packet. This set is called MPR of that node. All the nodes which are outside this set can only read and process each packet they receive but cannot forward it. OLSR is based on the following three mechanisms:
computation of an optimal route using the shortest-path algorithm
Neighbour sensing is the detection of changes in the neighbourhood of node. MPR strategy decreases the flooding overhead in contrast with full flooding because it only retransmits a broadcast packet if it is received from a node for which it is located in the MPR set. Further receptions of the same packet are dropped. Every node determines an optimal path to every destination and stores this information in a routing table. The path to every destinations node is available as and when the when data transmission begins and remains valid for a specific period of time till the information is expired.
In proactive protocols the topological information is exchanged among all the nodes in a network. In contrast to source initiated routing, table driven routing has extensive precedents in the research done for routing in the wired domain. Also wired routing protocols have inspired their own classes of protocols in table driven ad hoc routing. One of these classes is the distance vector protocols where the nodes maintain only a local topology, and use the distributed Bellman-Ford algorithm to maintain the routing tables, the other class of protocols is the link state routing protocols, where the routers exchange full topology information, and then use a graph-theoretic shortest path algorithm (Dijkstra's) on the resulting graph. However, these protocols differ in the way routing information is updated and detected, the number of routing tables used, the type of information stored in each table and the changes that are periodically broadcasted in the network. This class of routing protocols has its own advantages and disadvantages. One of its main advantages is the fact that nodes can easily get routing information and it's easy to establish a session. The disadvantage is too much data stored by the nodes for route maintenance and it is slow to restructure when there is a failure in a particular node link. Table 2.2 shows the comparison of some of the existing proactive routing protocols.
2.4 Reactive Routing Protocols
The reactive or on-demand routing protocols are based on Query-Reply topology in which they do not attempt to continuously maintain the up-to-date topology of the network. When a route is desired, a procedure is invoked to find a route to the destination node. Such a procedure requires some sort of flooding the network with the route query. Their major goal is to minimize the network traffic overhead. The common elements in reactive protocols are the mechanisms used for discovering and maintaining routes. The source node emits a request message for requesting a route to the destination node. This message is then flooded, i.e. forwarded by all nodes in the network, until it reaches the destination. The path followed by the request message is recorded and returned to the sender by the final destination, or by intermediate nodes with sufficient topological information. Thus there exist multiple reply messages which yield to multiple paths from source to destination node, of which the shortest is chosen. No periodic updates are required for these protocols but the routing information is only available when needed. However, this class of routing protocols is bandwidth efficient as compared to its counterpart i.e. proactive. Route is built as and when it is desired by sending route requests across the network. But still there are few disadvantages with this class also. One of them is that a large amount of time is wasted finding routes. The other disadvantage is in case of excessive flooding, there might be a possibility of network clog.
Some of the existing reactive routing protocols are:
Dynamic Source Routing Protocol (DSR)
Ad Hoc On-Demand Distance Vector Routing Protocol (AODV)
Dynamic MANET On-demand routing protocol (DYMO)
Temporally-Ordered Routing Algorithm (TORA)
Cluster Based Routing Protocol (CBRP)
Associativity Based Routing (ABR)
Location Aided Routing (LAR)
Perkins and Royer (1996) have proposed Ad hoc on demand distance vector routing protocol (AODV). It is an enhancement of their previous work i.e. DSDV routing protocol developed in 1994 with an aim to reduce the unnecessary broadcasts. It performs excellently in case of unicast and multicast routing and scale well to large size networks. The main focus was to limit the broadcasting of messages to neighbour nodes by discovering new routes reactively besides keeping all the information in routing tables as in the case of simple distance vector routing. AODV works on two procedures: route discovery and route maintenance. Before sending any packet towards the destination, the source node first consults its routing table to confirm a valid route to the destination node. If the node exists, the packets are forwarded to the immediate next neighbour on the path to destination. Otherwise, a route discovery is initiated by the sender node. In route discovery process, a route request RREQ packet is forwarded to immediate neighbouring nodes and the process continues till the packet reaches a node with a valid route to destination or the destination node itself. In return, the intermediate nodes send back route reply RREP packet, only if it contains the sequence number greater than or equal to the number already contained in the RREQ packet. All the process is recorded in the form of a routing table at each node which contains the address of neighbouring nodes which first send the packet. Figure 2.2 shows the complete process of route discovery.
(a) Source node S initiates the path discovery process (b) A RREP packet is sent back to the source
Figure 2. AODV route discovery process
The frame formats of RREQ and RREP are shown below.
Route Request packet
Source sequence no.
Destination sequence no.
Route Reply packet
Destination sequence no.
Each node can get to know its neighborhood by using local broadcasts, so-called HELLO messages. Nodes neighbours are all the nodes that it can directly communicate with. Although AODV is a reactive protocol it uses these periodic HELLO messages to inform the neighbours that the link is still alive. The information contained in the routing table is used to back track the path established. The process is similar to route discovery. In this the destination node sends RREP to its immediate next node on the path and the links are maintained till packet reaches the source node. However, route maintenance is required in case the destination or any intermediate node changes its position. In such case a special message link failure notification is send to each of the upstream nodes for ensuring a valid existing route. If the node is not reachable, another path is discovered with the help of RREQ messages. The moment packet reaches the source node route discovery is again initialized for next transfer. The main advantage of AODV is that it is adapted to highly dynamic networks, however extra delays may occur during route discovery and link failure, and thereby consumes more bandwidth. The main drawback of AODV is that it does not repair a broken path locally. Whenever a link breaks, the source and destination nodes are notified about it. The source node then reestablishes the route with destination. Also AODV does not provide any type of security. Zapata et al. applied some security extensions to AODV using one-way hash functions to serve metric fields during route discovery.
Johnson et al. have proposed a simple but very efficient protocol specifically designed for MANETs called Dynamic Source Routing protocol. It was developed at Carnegie Mellon University and is based on source routing scheme used in LANs. It was basically designed to restrict the unnecessary bandwidth consumption by eliminating the periodic routing updates as in distance vector algorithms. DSR is beacon-less which allows loop-free routing of packets and all the information about routing is stored in a buffer called cache. It is based on two procedures of route discovery and route maintenance which work collaboratively in discovering new routes and maintaining those routes as shown in figure 2.3.
(a) Building of the route record.
(b) Propagation of the route reply.
Figure 2. DSR Route Discovery Process
DSR is purely on-demand i.e. the routes are formed as and when there is any transfer of information between the nodes. The route can be discovered automatically by the source node to any destination in a network. In the route discovery process, the source node transmits a Route Request packet, on the route that identifies the target. Upon receiving the Route Request, the nest node retransmits the request further towards the target node. Also it returns a Route Reply to the source node. DSR also allows piggy-backing of a data packet which sends the data packet with Route Request message itself. Each and every packet contains a complete sequence of nodes through which the packet must travel. This information about the nodes list is declared in the packet header sent by source. The packet then travels through the nodes until it reaches the destination. Whenever a node detects a new route to some destination it immediately adds it into its cache. In addition to this each node also takes care of the sequence number which uniquely represents the requests sent by any node. DSR assumes the route as the shortest that the first packet has travelled from source node to destination. Route reply packet is sent back to the source which contains the complete route information form source to destination. The source node then stores this route information in its cache. Maintaining a route cache in every node allows any particular node to react to any routing changes quickly as a node having multiple routes to a destination can easily switch to another route if one link fails. Thus it reduces the amount of overhead generated by avoiding performing a new route discovery each time a route fails.
DSR enables the mobile nodes to automatically form a complete self-configuring and self-organizing network among themselves. In route maintenance phase two types of packets have been used: route error (RERR) and route acknowledgment (RACK). Acknowledgements are used to ensure the validity of existing routes. A RERR message is generated only in case of transmission problems that is when a node fails to receive the RACK back. The RERR packet is sent to the source node to initiate a new route discovery process. The node then removes all the entries from its cache that are using the broken route. So, DSR has an advantage that nodes can store multiple routes in their route cache which is very favourable in network with low mobility. Another advantage of DSR is that it does not require any periodic beaconing so nodes can easily enter into sleep node to conserve their battery life which in turn helps in conserving a considerable amount of network bandwidth. Besides this DSR has some disadvantages like the route maintenance mechanism cannot locally repair a broken links, stale route cache information could also result in inconsistencies during route discovery phase, connection setup delay is higher and the overall performance degrades rapidly with increase in mobility.
Park and Corson developed the Temporary Ordered Routing Algorithm (TORA) which was based on the concept of link reversal routing. The protocol was specifically designed to combat the problem of link failures. TORA is an adaptive and scalable protocol that operates in a highly dynamic mobile network by discovering multiple routes from source to destination. The term link reversal deals with effectively searching for alternative routes. The protocol operates on these basic functions: route creation, route maintenance and route erasure. In first two functions the nodes use a special metric to build a Directed Acyclic Graph (DAG). The metric considered is 'height' for calculating the height of each neighbour node. DAG is built as follows: initially the source node broadcasts a route request message to all its neighbours to discover a route to the destination node. This message is rebroadcasted until DAG is completely built. On receiving route request message, each node broadcasts its height to its neighbouring nodes. Figure 2.4 represents the DAG created during route discovery procedure in TORA. The arrows represent edges of graph and dotted arrows are the height of source node S, ht.
Figure 2. Directed Acyclic Graph for TORA
Every link is assigned a direction, upstream or downstream based upon the relative heights of neighbouring nodes. The link with null height is declared as unfit for use. Route erasure is enabled only when any node detects a partition in the network. When the neighbouring nodes are informed of this thing they immediately set their heights to null and all the links associated with them become undirected. These three functions are accompanied using three unique control packets namely query, update and clear. TORA assumes the links to be freed from loops. At any given time no two nodes can deny on the link direction assigned to the link. TORA is a loop free and distributed protocol and works well in handling network partitions. It is basically designed to minimize the reaction of nodes in case of any topology change. It provides number of routes from source to destination route and improves the speed of rebuilding the routes.
Dynamic Manet On demand routing protocol (DYMO) has been proposed by Perkins and Chakeres as ad advancement to the existing AODV protocol developed by Perkins et al. DYMO is a purely reactive protocol in which routes are computed on demand i.e. as and when required. It is a descendant of AODV protocol, and can act both as proactively as well as reactively. It extends AODV with source route path accumulation feature of DSR. We can say that DYMO is a combination of AODV with DSR. It is based on AODV structure but works on the mechanism of DSR. The basic operations of the DYMO protocol are route discovery and route management. During route discovery, the originating node initiates dissemination of a Route Request (RREQ) throughout the network to find the target node. When the target node receives the RREQ, it responds with a Route Reply (RREP) unicast toward the originating node. When the originating node receives the RREP, routes have then been established between the originating node and the target node in both directions. RERR is sent to the packet source to indicate the current route is broken. Once the source receives the RERR, it can perform route discovery. DYMO uses sequence numbers as they have been proven to ensure loop freedom. In addition, DYMO protocol can be used both in IPv4 and IPv6 network and people may use it to connect with the Internet. It can adapt to changes of the network topology, and establish a unicast route between the target node and the originating node.
As DYMO routing protocol is successor to the popular Ad hoc On-Demand Distance Vector routing protocol, it shares many of its benefits. DYMO protocol has the similar basic functions and operations to AODV. As a reactive protocol, DYMO does not explicitly store the network topology. Instead, nodes compute a unicast route towards the desired destination only when needed. As a result, little routing information is exchanged, which reduces network traffic overhead and thus saves bandwidth and power. DYMO is applicable to memory constrained devices. AODV supports unicast, multicast and broadcast. The DYMO only supports unicast routing established between the on-demand nodes in the network . DYMO routing protocol with excellent performance is simple, compact, easy to implement and highly scalable characteristics, and is a very promising protocol. A detailed discussion about DYMO protocol has been presented in chapter 3.
Reactive routing is best adapted to the most challenging incarnations of the ad hoc networks. Their major goal is to minimize the network traffic overhead. The baseline for this class of protocols is set by AODV and DSR; both of them have several independent implementations for various operating systems. DYMO protocol is a successor of AODV which is based on the concept of source routing in which routing tables are maintained at each and every node unlike AODV. The common elements in reactive protocols are the mechanisms used for discovering and maintaining routes. The source node emits a request message for requesting a route to the destination node. This message is then flooded, i.e. forwarded by all nodes in the network, until it reaches the destination. The path followed by the request message is recorded and returned to the sender by the final destination, or by intermediate nodes with sufficient topological information. Thus there exist multiple reply messages which yield to multiple paths from source to destination node, of which the shortest is chosen. No periodic updates are required for these protocols but the routing information is only available when needed. However, this class of routing protocols is bandwidth efficient as compared to its counterpart i.e. proactive. Route is built as and when it is desired by sending route requests across the network. But still there are few disadvantages with this class also. One of them is that a large amount of time is wasted finding routes. The other disadvantage is in case of excessive flooding, there might be a possibility of network clog. Table 2.3 shows the comparison of some of the existing reactive routing protocols.
2.5 Hybrid Routing Protocols
Hybrid protocols are a new generation of protocols, a combination of both proactive and reactive protocols. These protocols are designed to incorporate various aspects of the other two classes of routing protocols. They are generally used to provide hierarchical routing. The difficulty of all hybrid routing protocols is how to organize the network according to network parameters. These protocols have the great potential to provide higher scalability than the other two classes. They attempt to minimize the number of re-broadcasting nodes by defining a zone, which allows the nodes to work together. The best or most suitable nodes can then be used to perform route discovery. The common disadvantage of hybrid routing protocols is that the nodes that have high level topological information maintains more routing information, which requires more memory and power consumption.
Some of the existing Hybrid Routing Protocols are:
Core Extraction Distributed Ad hoc Routing (CEDAR)
Zone Routing Protocol (ZRP)
Secure Routing Protocol (SRP)
Zone-based Hierarchical Link State (ZHLS)
Distributed Dynamic Routing (DDR)
Out of these ZRP combines the best features of both reactive and proactive routing protocols. For example, a node communicates with its neighbours using a proactive routing protocol, and uses a reactive protocol to communicate with nodes farther away. In other words, for each node, nodes within a zone are reached using proactive routing protocols. Outside this zone, reactive routing protocols will be used. Most hybrid protocols proposed to date are zone-based, which means that the network is partitioned into zones. Each node maintains both the topology information within its zone and the information neighbouring zones that means proactive behaviour within a zone and reactive behaviour among zones. Thus, a route to each destination within a zone is established without delay, while a route discovery and a route maintenance procedure is required for destinations that are in other zones. The zone routing protocol, Zone-based Hierarchical Link State routing protocol and Distributed Dynamic Routing algorithm are three hybrid routing approaches that can provide a better trade-off between communication overhead and delay. But this trade-off is subjected to the size of a zone and the dynamics of a zone. Furthermore, hybrid approaches provide a compromise on scalability issue in relation to the frequency of end-to-end connection, the total number of nodes and the frequency of topology change. Thus, the hybrid approach is an appropriate candidate for routing in a large network.
Hass and Pearlman have designed the Zone Routing Protocol (ZRP) for large scale networks. It dynamically adjusts itself according to the operational conditions of the network by varying the size of a single parameter i.e. zone radius. A simple example of ZRP architecture is shown in figure 2.5 in which the network in divided into zones with a fixed value of zone radius. This figure shows the routing zone for node S. The inner circle marks the zone with radius 1 and outer circle represents the zone with radius 2. With zone radius = 1, the nodes 6, 7, 9 and 11 are interior nodes whereas nodes 2, 3, 4, 8 and 10 are peripheral nodes. The nodes 1 and 5 are out of the range of node S zones.
Figure 2. ZRP architecture
ZRP minimizes the cost of updates caused due to dynamically changing topology by linking their scope within a particular zone instead of whole network. It allows an efficient and faster route discovery and requires a very small amount of routing information at each node. It is more reliable, has high performance and easily detects multiple loop-free routes to the destination. ZRP is a hybrid protocol; it is both reactive and proactive in nature. The protocol works proactively within a zone and reactively between the zones. The size of zone depends on the radius, although zones may overlap with each other that help in route optimization. The nodes within a zone share the information through a proactive scheme i.e. Intrazone Routing Protocol (IARP). The neighbour discovery is done either by IARP or through HELLO messages. IARP always maintains up-to-date routing tables. On the other hand, all the routes that are discovered outside a zone follow Interzone Routing Protocol (IERP) scheme which is reactive. The route queries from a zone are forwarded to the peripheral nodes (nodes 1 & 5 as seen from figure (()) using Bordercast Resolution Protocol (BRP). ZRP provides a flexible approach in discovering new routes and maintaining those routes. The advantage of ZRP is reduced routing overhead and delays as compared to other proactive protocols. The disadvantage is that it behaves like a proactive protocol in case the zone radius is very large and reactive in case of small zone radius. One more problem with ZRP is the overlapping zone which was later removed in ZHLS (Zone Hierarchical Link State) routing protocol discussed in next section.
Haas and Pearlman proposed Zone based Hierarchical Link State routing protocol which employs hierarchical architecture represented by non-overlapping zone. Each zone in a network has a zone id and every node within a zone is assigned a node id which is computed using GPS. The whole topology is divided into two levels; node level and zone level. When route discovery process is initiated, only the node and zone ids of a node are required. No updates are required as long as node is within its zone it is only needed when a node switches to another location outside its zone. The only disadvantage of ZHLS is that before any route discovery, all the nodes must have a static zone map that contains information about all the zones in the network. So it is more suitable for network having fixed boundaries. ZHLS has an advantage of reduced overheads and compared to other reactive protocols like AODV, DSR, etc. and is highly adaptable to dynamic topologies. ZHLS has a simplified location management as all the transmission is done in the absence of any designated zone head or location manager. This helps in avoiding any single failure and congestion.
The nodes in the network are grouped into a number of trees. Each tree has two types of nodes; route node, and internal node. The root controls the structure of the tree and whether the tree can merge with another tree, and the rest of the nodes within each tree are the regular nodes. Each node can be in one three different states; router, merge and configure depending on the type of task that it trying to perform. DST proposes two strategies to determine a route between a source and a destination pair:
Hybrid Tree Flooding (HTF): In this scheme, the source sends the control packets to all the neighbours and adjoining bridges in the spanning tree. Each packet is remained static at these places for a specific holding time.
Distributed Spanning Tree (DST): In this approach, the source sends the control packets to the tree edges till each of them reaches a leaf node. When a packet reaches the leaf node, it is forwarded to a shuttling level.
The drawback with such architecture is the existence of a single point of failure for the entire tree. If the root node fails, the entire routing structure falls apart. Furthermore, the holding time used to buffer the packets may introduce extra delays in to the network.
Nikaein et al. proposed a tree-based routing protocol without the need of a root node. In this strategy tree are constructed using periodic beaconing messages, which are exchanged by neighbouring nodes only. These trees within the network form a forest with the created gateway nodes acting as links between the trees in the forest. These gateway nodes are regular nodes belonging to separate trees but within transmission range of each other. A zone naming algorithm is used to assign a specific zone ID to each tree within the network. Hence, the overall network now comprises of a number of overlapping zones The DDR algorithm comprise of the following six phases: (i) preferred neighbour election; (ii) intra-tree clustering; (iii) inter-tree clustering; (iv) forest construction; (v) zone naming; and (vi) zone partitioning. To determine routes, hybrid ad hoc routing protocol (HARP) is used. HARP uses the intra-zone and inter-zone routing tables created by DDR to determine a stable path between the source and the destination. The advantage of DDR is that unlike ZHLS, it does not rely on a static zone map to perform routing and it does not require a root node or a cluster-head to coordinate data and control packet transmission between different nodes and zones.
Hybrid protocols are a new generation of protocols, a combination of both proactive and reactive protocols. They have the potential to provide higher scalability than pure reactive or proactive protocols. Another novelty of hybrid routing protocols is that they attempt to eliminate single point of failures and creating bottleneck nodes in the network. This is achieved by allowing any number of nodes to perform routing or data forwarding if the preferred path becomes unavailable. They are generally used to provide hierarchical routing. The difficulty of all hybrid routing protocols is how to organize the network according to network parameters. These protocols have the great potential to provide higher scalability than the other two classes. They attempt to minimize the number of re-broadcasting nodes by defining a zone, which allows the nodes to work together. The best or most suitable nodes can then be used to perform route discovery. The common disadvantage of hybrid routing protocols is that the nodes that have high level topological information maintains more routing information, which requires more memory and power consumption. Out of these ZRP combines the best features of both reactive and proactive routing protocols. Table 2.4 shows the comparison of some of the existing hybrid routing protocols.
2.6 Comparison of various routing protocols
In this section a comparison between existing routing protocols has been presented. The comparisons basically consider the characteristic properties of routing protocols in high load networks. In order to make flat addressing more efficient, the number of routing overheads introduced in the networks must be reduced. The hybrid routing protocols employ both reactive and proactive properties by maintaining intra-zone information proactively and inter-zone information reactively. Another way to reduce routing overheads is by using conditional updates rather than periodic ones. In on-demand routing protocols, the flooding-based routing protocols such as DSR and AODV will also have scalability problems. In order to increase scalability, the route discovery and route maintenance must be controlled. Hybrid routing protocols such as the ZHLS may also perform well in large networks. ZRP is another hybrid routing protocol which is designed to increase the scalability of MANETs. It maintains strong network connectivity (proactively) within the routing zones while determining remote route (outside the routing zone) quicker than flooding. Also it can incorporate other protocols to improve its performance. Although newer protocols have built upon the earlier ones, we cannot identify a single best protocol. Table 2.5 shows the overall comparison of all routing strategies against few parameters.
2.8 Swarm Intelligence
Swarm Intelligence (SI) is a part of artificial intelligence. It is an innovative artificial distributed intelligent paradigm based on the study of emergent behaviour in decentralized (multi agent), self-organized systems for solving optimization problems. SI is the emergent collective intelligence of groups of simple autonomous agents. SI is sometimes also called as "collective intelligence" as it is inspired from the collective movement characteristics of ants, bees, flock of birds, herds of animals etc. The communication between insects in a colony has been the base for all the communication systems that contribute to the collective intelligence. SI is based on two techniques to optimize the network performance i.e. Bee colony and Ant colony as discussed in next section. Bee colony optimization has taken inspiration from real ants' behaviour while bee colony optimization has been inspired from the behaviour of honey bees.
2.8.1 Bee Colony Optimization (BCO)
The Bee colony is a new and youngest meta-heuristic technique capable of solving hard and complex combinatorial optimization problems. It is inspired by the behaviour of honey bee colony in nectar collection. The honey bees evaluate the quality of every discovered food source and wave to and fro if the quality is above a certain threshold level. Three main things that are important while taking some action are the direction, distance from source and quality. Same inspiration has been taken and applied on networks to find best routes from source to destination. Mainly two agents are used to find an efficient route in the network that is scouts and foragers. Scouts are helpful in searching new fresh routes to the destinations while foragers carry the data packets that need to be sent and simultaneously evaluate the quality of the discovered paths. The population of artificial bees searches for the best optimal path. The artificial bees represent agents which collectively solve the problem. The technique has toe phases: forward phase and backward phase. In forward phase the scout agents search for new paths while in backward phase the forager agents share information about the solutions. The list of a few BCO applications for solving optimization problems have been given in table 2.6.
2.8.2 Ant Colony Optimization (ACO)
Ant colony is basically inspired from the behaviour and action of the natural ants. The ants navigate their designated selection of paths while depositing a certain amount of substance called pheromone on the ground, marking a trail. The idea behind this technique is that the more ants follow a particular trail, the more attractive is that trail for being followed by other ants. They therefore dynamically find a path on the fly, using the explained notion of stigmergy to communicate indirectly amongst them. An ant chooses a trail depending on the amount of pheromone deposited on the ground. Each ant compares the amounts of trails, for the selected destination on each link, toward the neighbouring nodes. The larger the concentration of pheromone in a particular trail, the greater is the probability of trail being selected by an ant. The concentration of the pheromone on the links formed evaporates with time at a certain rate. Each node in the network has a routing table which helps it determine where to send the next packet or ant. These routing tables have the neighbours of the node as rows, and all of the other nodes in the network as columns.
ACO algorithms have been employed to solve numerous problems in ad hoc networks. Dorigo et al. were first to propose ant algorithms as a multi-agent approach to difficult combinatorial optimizations problems such as the travelling salesman problem, graph colouring, quadratic assignment problem and routing in communication networks and so on. The list of a few ACO applications for solving optimization problems have been given in table 2.7. Ant algorithms are inspired by the observation of real ant colonies.
An important behaviour of ant colonies is their foraging behaviour i.e. how ants find the shortest paths between food sources and their nest. While searching for food, ants deposit on ground an amount Î”Ï„ of special substance called pheromone at each visited node, where.
The amount of pheromone deposited is proportional to the quality of the route found by the ant depositing pheromone. The quality of the route is inversely proportional to the route length, Ld(t).The pheromone trail helps ants to find their way back to the food source. The ants which traverse through the shortest path reinforce the path with more amount of pheromone that helps other ants to follow. However the deposition of amount of pheromone diverges from the observed behaviour of real ants. Therefore, ants employ two forms of solution evaluation:
Explicit evaluation- Here ants deposit an amount of pheromone proportional to the quality of the solution.
Implicit evaluation- Here ants deposit the same amount of pheromone and the algorithm exploits the differential path length effect to find solutions.
As ad hoc networks have dynamic topologies it is necessary to develop a mechanism for eliminating the old routes. In ACO this is achieved by evaporating the pheromone exponentially over time. The pheromone values at any edge (i, j) are updated by all the ants that have completed the path length as follows:
Where m is the number of ants that have completed the path. is the evaporation constant that determines the evaporation rate of the pheromone. is the quantity ofpheromone deposited by ant k on edge (i, j).
2.9 Ant based routing protocols
This section will present an overview of the different ways in which Ant algorithms have been employed to solve various variations of routing in ad hoc networks. ACO is used in both flat as well as hierarchical ad hoc networks. Dorigo et al. combined ACO with source routing to develop AntNet. Schoonerwoerd et al combined ACO with distance vector routing to develop Ant-based control (ABC) routing.
2.9.1 Ant based flat routing algorithms
All the nodes form a homogeneous network. All the nodes share similar network responsibility and packet handling. The protocols proposed basically use ACO with basic source routing or distance vector algorithms where routing tables are replaced with pheromone tables. This section presents some of the existing routing algorithms that incorporate the applications of ACO.
AntNet algorithm was basically proposed for fixed wired networks, which derives features from parallel replicated Monte Carlo systems, previous work on artificial ant colonies techniques and telephone network routing. Dorigo et al. used Ant Net to describe the application of ACO to dynamic routing in packet-switched networks. It is based on source routing mechanism. The basic idea in AntNet is to use two network exploration agents - Forward ants (FA) and Backward ants (BA), which collect information about the delay, congestion status and path in the network. Each node n generates a FA at regular time intervals to a randomly selected destination d. FA uses the current routing tables to find a path to node d and records the route taken. On reaching at the destination, FA creates another ant called BA moves back to the source node n reverse the path of FA. The BAs get their information from the FAs and use it to achieve routing updates at the nodes. After creating a BA, the FA dies. Each node stores a routing table Tk organized as in distance-vector algorithms storing probability values. For each destination-neighbour pair (d, n), Tk stores a probability value Pnd which helps in choosing n as next-hop node to destination d, such that
According to Dorigo the AntNet algorithm provides better performance in terms of average delay. The last step is to update the routing table when a BA arrives. The action involves increase in corresponding routing probability of FA and decrease in probabilities of all other neighbouring nodes. The values are increased and decreased such that the sum of all probabilities will remain 1.
Ant Based Control is the first ACO application to dynamic problems proposed by Schoonerwoerd. ABC is another stigmergy-based ant algorithm designed for packet-switched telephone networks and uses distance vector routing. It shares many similarities with AntNet, but also incorporates certain differences. ABC replaces routing tables with pheromone tables. Another difference is that ABC only uses a single class of ants (i.e. forward ants), which are initiated at regular time intervals from every source to a randomly chosen destination. Ants move from node to node selecting next node to move according to the probabilities in pheromone tables for their destination node. Arriving at a node, ants update the pheromone tables' entries for corresponding node. The ants die after reaching their destination. Here the probability increase is represented by Î”P as shown below in the probability update equation.
Schoonerwoerd et al. introduced two new aspects - age and delay. They set all pheromone levels to an initial value and intend to primarily encourage the ants to find short paths, and to secondly prevent the agents from visiting heavily congested nodes. The first goal is accomplished by reducing the Î”P value, which reinforces the routing table, gradually over time. A relative pheromone update scheme was implemented in which the amount of pheromone updated by each ant is inversely proportional to the age of ant. The second objective is obtained by adding an artificial delay to the ants when passing congested nodes. Though ABC is a simple algorithm designed for packet-switched networks, it performs better than other ACO based algorithms.
Ant-colony based Routing Algorithm was proposed by Gunes et al. Route discovery is done by flooding a forward ant to the destination, similar to Route Request in AODV. Duplicate packets are identified by the use of a sequence number and are deleted by system. When a route is found to the destination, a backward ant is created similar to Route Reply in AODV. The backward ant follows the path with the shortest trip time detected by the forward ant. The amount of pheromone deposited by both ants is a function of route length associated with pheromone. The route maintenance phase is responsible for updating the routing information during the communication. The algorithm updates both the forward and the backward path with an equal amount of pheromone (presumed as 0.1). ARA also allows for the evaporation of pheromones. Every second the amount of pheromone is decreased by a multiplicative factor f as shown below:
ARA achieves loop free paths using sequence numbers. If a node receives a duplicate packet, it sets the DUPLICATE_ERROR flag and returns the packet to the previous node, and removes the link. According to Gunes et al. ARA performs comparatively better in terms of overhead ratio and delivery rate.
DiCaro and Gambardella et al. proposed a hybrid multipath routing algorithm called AntHocNet that combines both proactive and reactive components with ACO. Routes are discovered reactively, where reactive forward ants (FA) are sent by the source node to find multiple paths towards the destination node. Unlike AODV, AntHocNet compares both travel time and hop count of subsequent forward ant and rebroadcasts only if both the criteria are within a certain factor of the best forward ant. The FA gathers route information while moving towards destination node. After reaching there it becomes backward ant (BA) which traces its path back to source node and creates a route with the help of intermediate visited nodes. Each node m stores a routing table Tm which contains a measure Tmnd of the desirability of using node n as the next hop to destination d. The amount of pheromone deposited by BA is measured as the average of the inverse of cost (in terms of delay and number of hops) of travelling to the node d through node n. For each destination-neighbour pair Tm stores a probability value Pnd calculated using:
Once the route is created, the source node sends one proactive forward ant to the destination node on every nth data packet. One important thing to notice is that the proactive forward ant can discover new routes in the vicinity (within the boundary) of existing route only. The main purpose of using proactive forward ants is to search for any route improvements or variations and not to search for entirely new route. Like AODV, AntHocNet also uses HELLO messages to improve local connectivity of nodes. In case of link failure the node updates it routing table and send a notification to its neighbours. But Di Caro et al. did not mentioned about the status of data packet in case of link failure, whether the packet is to be drop7ped or backtracked to any upstream node in the network. However, AntHocNet gives a superior delivery ratio and better packet delay than AODV.
2.9.2 Ant based hierarchical routing algorithms
Hierarchical networks help improve network scalability by diving the nodes into a hierarchy of clusters. But they are less suited for high mobility network scenarios. This section presents a hierarchical routing algorithm that uses swarm intelligence to discover and maintain new routes.
Mobile Ants Based Routing was proposed by Heissenbuttel and Bruan, the first algorithm for large-scale networks based on AntNet. MABR works on GPS where node are aware of the position of all other nodes present in the network. Each node stores two data structures - routing table and link cost table. Unlike rows of node entries used in traditional routing tables, rows of zone entries are recorded for every known destination zone. Columns of zones are added for every outgoing logical link. Every destination zone owns eight logical links for each adjacent zone called relay zones. The pheromones are directly transformed into probabilities stored in the routing table. The link-cost table retains information about link quality from different destination zones from where mean values, variance of end-to-end delay and hop count can be measured. When a packet arrives, it allows computing some goodness value, which may be used for stronger or weaker reinforcement of the relay zone. The algorithm consists of two sub-protocols:
Topology Abstracting Protocol (TAP)
Each node groups the network into logical zones with itself as the center node.
Straight Packet Forwarding (SBF) Protocol
MABR determines the next logical router for a destination by means of pheromone concentrations. The forwarding process along the logical links is accomplished by SBF protocol. It just forwards the packets based on the geographical coordinates of the next logical router, received by MABR.
MABR uses three different protocol packets. Forward ants are used to explore new paths in the network. Backward ants serve the purpose to inform the originating node about the information collected by the forward ant. Data ants encapsulate data packets sent across the network. Forward ants are transmitted from a mobile node to some randomly chosen logical router in the network. Forward ants store information such as packet type, sender coordinates, address of the destination logical router, coordinates of the last hop in order to detect logical router changes, coordinates of the last logical router to reinforce the correct logical link, a TTL value, a sequence number to uniquely identify packets, a timestamp about the initiation of the packet, just to enumerate the most important ones. These values are required for routing and updating the two tables. On occurrence of a forward ant MABR updates the pheromone concentrations of the backward path towards the source at every intermediate node, which processes or overhears the packet. If the forward ant arrives at the destination, it updates the routing table's probabilities and is dropped afterwards. The initiating node may optionally request a backward ant to update the forward path toward the destination. A backward ant stores the same information as a forward ant but additionally includes the network delay experienced by the forward ant as well as the first logical router where the forward ant had been sent through. Backward ants follow the same path as data packets.
Probabilistic Emergent Routing Algorithm
PERA works reactively with ants being broadcasted towards any random destination. As multiple paths are set up, only the one with highest pheromone value is used by data and the other paths are available for backup. The route discovery and maintenance is done by flooding the network with ants. Both forward and backward ants are used to fill the routing tables with probabilities. These probabilities reflect the likelihood that a neighbour will forward a packet to the given destination. Multiple paths between source and destination are created. The neighbours are discovered using HELLO messages, but entries are only inserted in the routing table after receiving a backward ant from the destination node. Each neighbour receives a probability value for destination. This value is increased as a backward ant comes from that node, establishing a path towards destination. The algorithm uses sequence numbers to avoid loops and duplicate packets. Forward ant with a lower sequence number is dropped, similar to AODV Route Request packets, but discovers a set of routes instead of one. Data packets can be routed according to the highest probability in the routing table for the next node.
AntHocNet is most efficient in maintaining paths. It has greater chance of exploring new paths due to proactive nature. Although AntHocNet maintains paths between nodes and explores new routes it is costly and requires more resources. AntHocNet requires more number of resources as compared to other ant based algorithms. This is because there are two forward ants (Proactive and Reactive) and two backward ants (Proactive and Reactive). PERA uses routing table which has the following structure: [Destination, Next hop, Probability]. It works similar to AntNet. Each node periodically sends forward ant to randomly chosen destination, whereas source node is chosen according to some probability of data flow. ARA is quite similar to PERA. One difference is that both forward and backward ants leave pheromone behind: forward ants update pheromone about the path to the source, while backward ants update pheromone about the path to the destination. ARA keeps more of the original ACO characteristics than PERA. AntNet was basically developed for packet switched wired networks. HELLO messages are used initially to discover the neighbours. In PERA, HELLO messages are broadcasted each time any node moves to a different position so that node can discover its new neighbours. ABC Routing was developed for wired telecommunication networks and it assumes symmetric path costs between nodes. Like in AntNet, each node s periodically sends out ants to randomly chosen destinations. In ABC, it is not data packets that are routed according to the pheromone, but call setup messages. Table 2.8 gives the comparison of different ant based routing algorithms based on various parameters.