Abstract: A Mobile ad hoc Network (MANET) is a self-configuring infrastructure less network of mobile devices connected by wireless. These are a kind of wireless ad hoc Networks that usually has a routable networking environment on top of Link Layer ad hoc Network. The routing approach in MANET includes mainly three categories viz., Reactive Protocols, Proactive Protocols and Hybrid Protocols. These traditional routing schemes are not pertinent to the so called Intermittently Connected Mobile ad hoc Network (ICMANET). ICMANET is a form of Delay Tolerant Network, where there never exists a complete end-to-end path between two nodes wishing to communicate. The intermittent connectivity araise when a network is sparse or highly mobile. The study in general is carried out to get hold of a plain gen about the routing schemes possible in disconnected networks. It could aid to put together a proposal for a novel routing technique which is capable of holding the benefits and excluding the detriments of its prior existing techniques. Routing in such a spasmodic environ is arduous. An indication of prevailing routing approaches for ICMANET and their comparisons on different network parameters are portrayed in further discussions.
INTRODUCTION
Mobile ad hoc Networks (MANET) is well-thought-out to be the rapid deployment of independent mobile users. Such network setups cannot count on centralized and organized connectivity and can be conceived as the applications of MANET.
A MANET in general is defined as the assortment of nodes that are relatively capable of moving within the network extending its communication over relatively Band Width constrained wireless links. The mobility of nodes in the network, leads to a rapid change in network topology from time to time. In quintessence, the network is decentralized where, all network activity including discovering the topology and delivering messages must be executed by nodes themselves (i.e.,) routing functionality will be assimilated into mobile nodes.
The routing methodologies in such networks are made through traditional routing protocols like AODV (ad hoc On demand Distance Vector) (Lakshmi and Sankaranarayanan, 2006; Asfand-e-Yar and Sher, 2004), DSR (Distance Source Routing), Link State routing protocol (Alagiri et al., 2012) On demand Multipath Routing (Ramesh and Kumar, 2012a) etc. Ample routing algorithms (Wang et al., 2008; Bhagyaveni and Shanmugavel, 2005; Manickam and Shanmugavel, 2007) have been proposed for MANET since the past two decade. The Mobile ad hoc Network (Sesay et al., 2004; Nazir et al., 2006) drawn from wireless sensor networks (Ramesh and Kumar, 2012b) paves to a new form of network called the Intermittently Connected Mobile ad hoc Networks (ICMANET).
ICMANET is considered to be one of the new-fangled areas in the field of wireless communication. Network setup under this area remains a challenging task and the nodes are assumed to communicate with potentially restricted resources. These are emerging as a promising technology in applications such as in Wildlife Management, Military Surveillance, Underwater Networks and Vehicular Networks (Kuiper and Nadim-Tehrani, 2011). ICMANET, a novel network typically different from other traditional MANETs (Sharma et al., 2007; Ramesh et al., 2012c), is also referred to as Delay Tolerant Networks (DTN) which means that in the latter; communication between two nodes is possible at any time via a path of intermediate nodes although, this path may vary with time. However, in an ICMANET, communication between nodes is possible through multiple paths connecting variant intermediate nodes met at the particular instant of time. Unlike the traditional MANET, a complete end to end path can never be established in ICMANET. In this study, the possible routing schemes in ICMANET are discussed.
The various routing protocols available for routing across ICMANET are Flooding based routing, Epidemic routing, Beaconless routing (Khan et al., 2008), Context Aware routing, Brownian Gossip, Mobility Profile Based routing, Direction based Geographic routing, Single Copy Case routing, Multiple Copy Case routing, Semi Probabilistic routing, Contention based routing, Spray and Hop, Spray and Wait (Spyropoulos et al., 2005) and LAROD-LoDiS routing. A brief description is available in the latter sub sections.
This study, speaks about the comparative analysis of the various routing techniques available for ICMANET. In the following sections, the routing protocols based on different parameters are discussed. The sections includes the various routing techniques and the performance each technique with respect to various network parameters like overhead, delivery latency, number of transmissions and the delivery rate.
ROUTING TECHNIQUES
The traditional Flooding based routing scheme forms the basis for other routing schemes in ICMANET. In this, one node sends packet to all other nodes in the network. Each node acts as both a transmitter and a receiver. Each node tries to forward every message to every one of its neighbours (Cokuslu and Erciyes, 2008). The results in every message eventually delivered to all reachable parts of the network.
The Epidemic routing oeuvres on the basis of the traditional flooding based routing protocol which states that periodic pair-wise connectivity is necessitate for message delivery (Vahdat and Becker, 2000). The protocol banks on immediate dissemination of messages across the network. Routing occurs based on the node mobility of carriers that are within distinctive position of the network.
The Beaconless routing protocol (Heissenbuttel et al., 2004) is grounded on the hypothesis where, there never exists an intervallic diffusion of beacons into the network. Routing primarily makes a choice of forwarding node in a dispersed modus amidst its neighbours, without any form of erudition about their location or prevalence.
The Context Aware Routing (CAR) (Musolesi et al., 2005) algorithm paves the forethought of asynchronous communication in ICMANET. The algorithm endows a basement of organising the messages in the network. It addresses that the nodes are able to exploit the context information to make local decisions which imparts the good delivery ratios and latencies with less overhead. CAR is pain staked as a general framework to predict and evaluate context information for superior delivery of messages.
The Brownian Gossip (Choudhury, 2005) is an amalgamation of gossip and the random node mobility which provides a scalable geographical routing. In this routing, each node forwards the query related to other nodes information with certain values of probability in multipath (Ramesh et al., 2012a) manner. Gossiping is a resourceful approach for information dissemination and is done with a probability viz., Pgossip. The probability value makes certain that the query can reach the secondary nodes in the network with highest probability.
The Mobility Profile Based routing (Ghosh et al., 2006a) addresses, a hub-level routing method and two versions of user-level routing methods as Static-SOLAR-HUB and Dynamic-SOLAR-HUB (Ghosh et al., 2006b). The routing involves a SOLAR-HUB (Sociological Orbit aware Location Approximation and Routing) which manipulates the user profiles that aids in hub-level routing.
The Direction Based Geographic Routing (DIG) (Li and Shen, 2008) algorithm is grounded on geographic location of packets that are routed in an average approximate ideal path towards destination. The algorithm postulates that when two nodes encounter each other, the nodes exchange the knowledge of their current location, moving direction and the packets. The packets are forwarded to nodes whose distance and moving direction are closest to destination.
The Single Copy Case routing (Spyropoulos et al., 2008a), from its nomenclature it postulates that only a single copy of message packet is carried to destination. The routing scheme includes direct transmission, randomized routing, utility based routing, seek and focus and Oracle based routing.
The Multiple Copy Case (Spyropoulos et al., 2008b) scheme deals with the mechanism of spraying a few copies of message and then routing each copy in isolated manner to the destination. The algorithm that holds multiple copy case routing are Spray and Wait and Spray and Focus.
The Semi Probabilistic Routing (SPR) (Shi, 2010) algorithm considers that the network is partitioned into tiny portions that have a stable topology. The protocol upholds the information about host mobility and connectivity changes for more accurate message forwarding.
The Contention Based Routing postulates that the efficiency of routing can be achieved only by taking into account the contention and dead end (Jebajothi et al., 2010). The Spray Select and Focus provides a better performance considering the contention and dead ends.
The Spray and Hop (Lai et al., 2009) is a routing protocol that holds two phases namely, Spray phase that sprays few copies of message into the network and Hop phase which occurs after the spraying phase, a node that was not able to find the destination, switches to the hop phase.
The Spray and Wait (Spyropoulos et al., 2008a) is a scheme that sprays into the network a fewer number of message copies and waits until one of these nodes that holds the copies reaches the destination. It is simple to implement and can be optimized to achieve the depicted performance.
The LAROD-LoDiS (Kuiper and Nadim-Tehrani, 2011) is a new form of routing that complements efficient routing in the Intermittently Connected Mobile ad hoc Networks. The LAROD-LoDiS, as the name indicates it is an amalgamation of LAROD-Location Aware Routing for Delay Tolerant Networks and LoDiS-Location Dissemination Services. The amalgamation of these techniques suits ICMANET in a well-versed way. LAROD (Kuiper and Nadim-Tehrani, 2011) routes packet only with partial knowledge of the geographic positions. To impose low overhead, it uses beaconless protocol to route packets. It combines the routing scheme with store-carry-forward technique and uses greedy packet forwarding whenever required. LoDiS (Kuiper and Nadim-Tehrani, 2011) maintains a local database and updates it by using the gossiping technique in addition to routing. The database is updated by exchanging their information in database as nodes encounter each other.
OVERHEAD
The routing techniques in ICMANET are compared with a constraint namely overhead. Overhead is one of the main constraints that are to be contemplated for efficient routing. Overhead is any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to attain a particular goal.
From the analysis, it is studied that certain protocols viz., Flooding, Epidemic, HUB protocol, Multiple Copy case experiences a maximum overhead ratio. The higher overhead is due to the spraying of multiple data packets in to the network that upshot the congestion.
While certain protocols like BLR (Beacon Less Routing) which is based on position, CAR (Context Aware Routing), Brownian Gossip, Single Copy, SPR yields minimum overhead. These algorithms are based upon either direct message delivery or based on single message transmission.
The algorithms like Spray Select Focus and Spray and Wait exhibits an optimal overhead i.e., reasonable overhead based on the node density, number of transmissions and various other network parameters. The Spray and Hop shows highly scalable overhead since routing of messages do not wait until the relay node encounters the destination.
Of all the Routing Schemes LAROD-LoDiS shows constant overhead at all loads. It’s a main reason that this algorithm aids in efficient routing. The Fig. 1 shows depicts that the overhead ratio for LAROD-LoDiS is minimum when compared to other routing protocols of ICMANET (Intermittently Connected MANET). The comparison is evaluated with respect to the packet life time and the number of transmissions for each packet to reach the destination.
From the Fig. 1, it is evident that, the overhead ratio is high in Epidemic routing (Vahdat and Becker, 2000) in contrast to other routing techniques. The gossiping technique due to the frequent broadcasting of queries in various directions, it shows slight higher overhead.
| Fig. 1: | Overhead with respect to packet lifetime and number of transmissions |
Spray and Hop (Vahdat and Becker, 2000) shows slight better performance than Spray and Wait since, in the former case there is no province to wait until the destination is encountered i.e., once spray phase is complete, it is shifted to hop phase where utility function is used to reach the destination. LAROD-LoDiS (Kuiper and Nadim-Tehrani, 2011) shows a constant behaviour at all loads.
DELIVERY LATENCY
The second constraint under which the routing techniques of ICMANET were studied is the Delivery Latency. In general the latency is defined as the amount of time it takes for a packet to travel from source to destination. The delivery latency is the time interval taken for the source or any relay node to reach the destination.
In general due to the sparse nature of the ICMANET, i.e., due to its highly mobile nature, the time period to deliver the data packets are desirably high. Certain routing methodologies adopt technique in a way to reduce the delivery delay. Of the well known routing techniques of ICMANET, the flooding based routing scheme endows higher delivery delay in spite of its flooding nature.
The Epidemic routing shows a slight lesser overhead than the flooding scheme. Many routing techniques like BLR, CAR, Brownian Gossip, Single Copy and Multiple Copy routings exhibit a good reasonable delivery delay (Subramanyam and Prasad, 2006).
The Spray and Wait and Spray and Hop has a higher delivery delay, since after spraying they either wait for the destination to encounter destination or performs hops based on the utility factor of each node, respectively. The LAROD-LoDiS marks an optimal delay. Figure 2 shows that the delay in delivering the packets is less in LAROD-LoDiS as it’s a scheme of multiple copy case. Epidemic has the highest delay due to its pair-wise connectivity. The graph is evaluated with respect to the transmission range of each node.
From the Fig. 2, it is learnt that, the delay in delivering a message is higher in Epidemic routing. Whereas Gossiping even though exerts maximum delay, it is better when compared to epidemic. The delivery latency is considered to be slightly high in both Spray and Wait and Spray and Hop. In LAROD-LoDiS, since it propagates multiple copies into multiple directions, there is a possibility of one certain copy to reach the destination soon. Hence, exerts optimal or reasonable delay in delivering the message towards the destination.
| Fig. 2: | Delivery latency with respect to transmission range |
TRANSMISSIONS
The third factor with which the routing schemes are compared is the transmission range. This factor is used to determine the number of transmissions i.e., the average number of packets been transmitted within the specified range.
The Flooding based protocol due to its flooding nature explicitly provides more number of transmissions. In BLR, the transmissions are based on the position of the nodes i.e., the area of their location. The number of transmission in Brownian Gossip is estimated based on the value of the probability Pgossip. The DIG scheme, says that the number of packets transmitted are based upon the delay exerted in the network i.e., transmission increases with increase in delay.
In Single Copy and the Spray Focus scheme the transmissions are worse when copies get lost in the network which desperately shoots up the number of transmissions. The routing protocols viz., Multiple Copy case, Spray and Wait and LAROD-LoDiS exhibits a fewer transmission since they spray fewer message copies into network that widely reach different relay nodes. The Fig. 3 depicts the comparison of number of transmissions of all the routing protocols.
From the Fig. 3, it is understood that LAROD-LoDiS (Kuiper and Nadim-Tehrani, 2011) exhibits fewer transmissions in contrast to other routing protocols. The probability of number of transmissions in Gossiping technique is based on certain probability Pgossip where, Pgossip is calculated as a maximum value of the Query Count and the Average Speed (Shi et al., 2010) i.e., the number of times queried of destination position within a particular interval and the speed with which the node has travelled in the past, respectively. Epidemic has the higher number of transmissions due to its pair-wise connectivity. Spray and Wait and Spray and Hop have slight higher value than LAROD-LoDiS.
DELIVERY RATE
Another important factor that is been considered for comparative study is the rate of delivery i.e., the speed with which the data packets are delivered to the desired destination. Of all the protocols of routing in ICMANET, Single Copy scheme shows poor delivery rate, since only a single copy of message packet is transmitted into the network.
| Fig. 3: | Number of transmissions with respect to transmission range |
| Fig. 4: | Delivery rate with respect to packet lifetime |
The Spray and Wait scheme holds average message delivery rate even though they spray multiple copies into the network. It is so because after spraying during the wait phase, the relay or intermediate node waits until they encounter the destination. Since, the message delivery is based on the availability of destination node at the time of wait phase hence the delivery rate is said to be average. In LAROD-LoDiS, the delivery rate is high with maximum probability of delivery. Figure 4 explict that LAROD-LoDiS delivers packets at a higher rate than all the available routing protocols for ICMANET (Intermittently Connected MANET). The graph is done for delivery ratio with respect to the life time of the data packets.
Figure 4 shows that the delivery ratio i.e., the probability of delivering the message to the destination is higher than any other traditional routing protocols. The delivery ratio is much lower in Epidemic routing as it is based on the pair-wise routing. Gossiping provides slight better ratio as it determines the location of destination by querying in multiple directions. In Spray and Wait and Spray and Hop the ratio is merely the same and is poor as they have to wait to encounter the destination and determine the utility of node to reach the destination unless the relay or source node has only one token left with it, respectively. The graph clearly states that LAROD-LoDiS (Ramesh et al., 2012b) exerts a higher delivery ratio as it uses partial geographical information. Since, it overhears about the delivered packets, it provides higher delivery rate.
CONCLUSION
This study depicts the various routing techniques that were possibly adapted in ICMANET, Intermittently Connected Mobile ad hoc Network. It also out frames the performance metrics of various algorithms and their comparisons with each other. The techniques described in this paper are analyzed in well versed manner and their comparative evaluation is depicted in the subsequent figures. From the graphs the slight variation that each routing differs from each other can be clearly studied. These techniques prove the possibilities of routing in the partially connected mobile ad hoc networks. All the comparative evaluations, it is seen that LAROD-LoDiS outperforms of all the possible routing techniques of ICMANET. The study of these routing methodologies aids in developing new techniques to route across the network.