Geographical Routing with Location Service in Intermittently Connected MANETs

Geographical Routing with Location Service in Intermittently Connected MANETs

Praseena Prahlad Rajeena.M

PG scholar in CSE Asst.Professor in CSE

Younus College of Engineering and Technology, Younus College of Engineering and Technology, Vadakkevila, Kollam-691010 Vadakkevila, Kollam-691010

Abstract: Combining mobile platforms such as manned or unmanned vehicles and peer-assisted wireless communication is an enabler for a vast number of applications. A key enabler for the applications is the routing protocol that directs the packets in the network. Routing packets in fully connected mobile ad hoc networks (MANETs) has been studied to a great extent, but the assumption on full connectivity is generally not valid in a real system. This case means that a practical routing protocol must handle intermittent connectivity and the absence of end-to-end connections. In this paper, propose a geographical routing algorithm called location-aware routing for delay-tolerant networks (LAROD), enhanced with a location service, location dissemination service (LoDiS), which together are shown to suit an intermittently connected MANET (IC-MANET). Because location dissemination takes time in IC- MANETs, LAROD is designed to route packets with only partial knowledge of geographic position. To achieve low overhead, LAROD uses a beaconless strategy combined with a position-based resolution of bids when forwarding packets. LoDiS maintains a local database of node locations, which is updated using broadcast gossip combined with routing overhearing. The algorithms are evaluated under a realistic application ,i.e., unmanned aerial vehicles deployed in a reconnaissance scenario, using the low-level packet simulator ns-2.This holistic approach justifies that the choice of maintaining a local database of node locations is both essential and feasible. The LARODLoDiS scheme is compared with a leading delay-tolerant routing algorithm (spray and wait) and is shown to have a competitive edge, both in terms of delivery ratio and overhead.

1.INTRODUCTION

A wireless ad-hoc network consists of a collection of nodes that communicate with each other through wireless links without a pre-established networking infrastructure .It originated from battle field communication applications, where infrastructure networks are often impossible. Due to its flexibility in deployment there are many potential applications of a wireless adhoc network. For example ,it may be used as a communication network for a rescue-team in an emergency caused by disasters, such as earthquakes or floods, where fixed infrastructures may have been damaged. It may also provide a communication system for pedestrians or vehicles in a city Another example of a wireless ad-hoc network is a roof top network which consists of a number of wireless nodes spread over an area to provide local networking service and access to wired networks, such as the Internet, for residents in the neighborhood. Another

application of wireless ad-hoc networks is a sensor network, which consists of a large number of small computing devices deployed in a region that collect data and may send the information to a central server. The adhoc network can set up at anywhere , that means no base station or external infrastructure. They often mobile, thats why the term Mobile Adhoc Network (MANET).

A mobile ad-hoc network (MANET) is a self-configuring network of mobile routers (and associated hosts) connected by wireless links.

Some of the main features of MANET are listed below

1. MANET can be formed without any preexisting infrastructure.

2. It follows dynamic topology where nodes may join and leave the network at any time and the multi-hop routing may keep changing as nodes join and depart from the network.

3. It does have very limited physical security, and thus increasing security is a major concern.

4. Every node in the MANET can assist in routing of packets in the network.

5. Limited Bandwidth & Limited Power.

Intermittently connected mobile ad hoc networks (IC- MANET) are wireless networks where the nodes do not form a completely connected network. Instead, they will form connected partitions that changes their topology often. This kind of intermittent connectivity may happen when the network is quite sparse, in which case it can be viewed as a set of disconnected, time-varying clusters of nodes. Intermittently connected mobile ad hoc networks is a type of Delay Tolerant Networks (DTN), that is, networks were incurred delays can be very large and unpredictable. There are many real networks that fall into this category. Examples include disaster scenarios and military operations, wildlife tracking and habitat monitoring sensor networks (IPN) etc.

Since in the IC-MANET model there may not exist an end- to-end path between a source and a destination, existing ad- hoc network routing protocols, such as GPSR, DSR, AODV etc., would fail. To overcome the disconnected nature of IC- MANETs and to successfully route the packets under such conditions, a store-carry forward technique is used. Mobility can be exploited when wireless nodes cannot forward the packet.

In this paper we present a geographical routing protocol called Location Aware Routing for Opportunistic Delay- Tolerant networks (LAROD) which relies on position information of the nodes. LAROD is a beaconless protocol that greedily forwards packets towards the destination. When greedy forwarding is not possible a packet is temporarily stored by the current custodian until a suitable forwarding node comes up. Routing of packets toward the geographical location has shown to work well in IC- MANETs.

Clearly, a geographical routing protocol needs to be supplemented by a location service that can provide the current physical location of the destination node for a packet. A location service can range from simple flooding-based services to hierarchical services. There have been many suggestions on how a location service can be provided in MANETs, but there have been no suggestions on how this service can be provided in an IC-MANET or DTN setting. The location dissemination service (LoDiS) is the first location service for IC-MANETs which disseminates node locations in the network using a Brownian gossip technique. This paper bridges the gap between an application area and MANET/DTN research by providing a holistic approach to routing and location services in a realistic setting. The routing and location update problem is rooted on the application-driven pheromone mobility, for which the whole system is illustrated to provide a competitive edge. The contributions of this paper are listed as follows.

• We propose the first location service for IC-MANETs, i.e., the location dissemination service (LoDiS), evaluated in a conceivable setting and illustrate the challenges of this setting compared with the standard random waypoint mobility model.

• We present the integrated LARODLoDiS scheme and show that it is more effective and efficient compared with a leading nongeographic scheme: spray and wait .

  An early version of LAROD has been shown to work well with mobile sources and static receivers . This paper extends the reach of this beaconless geographical routing protocol for IC-MANETs. The missing building block to enable routing toward mobile receivers is a location service. LoDiS disseminates node locations in the network using a gossip- inspired technique with a constant per-node overhead. Although local gossiping may seem an inefficient method, we demonstrate that, in combination with updtes from the routing protocol, it is both effective and efficient. Due to the disconnected nature of IC-MANETs, the dissemination takes time, which means that the location state maintained by LoDiS could be stale. To overcome this problem, our approach builds on an incremental update of the location knowledge as a packet travels through the forwarding chain. The intermediate routers update the location information in a packet if their local LoDiS service has more recent information about the destinations location. It is based on the simple idea that the nodes closer to the destination have better information on the correct location of the destination.

  Thus, the knowledge about the destination position will incrementally be improved as the packet is routed toward the destination. Our evaluation of the combined LAROD LoDiS scheme shows that, in the reconnaissance scenario, spray and wait fails to provide an acceptable delivery ratio within a reasonable delay, whereas LARODLoDiS can provide more than a 95% delivery ratio. The significance of the more realistic mobility model is further illustrated by comparison with the standard random waypoint mobility. Another major result in this paper is that the LoDiS element of the combined scheme surprisingly comes close to a perfect location service (an oracle) but only contributes to a constant and modest increase in overhead

  1. BACKGROUND RELATED WORKS

     Proposals on how we can route packets in fully connected MANETs have been studied to a great extent. In the last decade, this interest has broadened into networks with intermittent connectivity. In this section, we give an overview of IC-MANET routing and location services.

     IC-Manet Routing

     The design of an IC-MANET routing protocol depends on the amount of contact information available with the node. The mobility of the nodes will constantly change the network topology and that nodes constantly come in contact with new nodes and leave the communication range of others. Node contacts can be classified based on their predictability into scheduled, predicted and opportunistic contacts. In scheduled contacts, the nodes know when they will be able to communicate with a specific node. In predicted contacts, nodes can estimate likely meeting times or meeting frequencies with specific nodes. If no such contact information is available with node then the contacts are opportunistic. LAROD neither requires scheduled contacts nor predicted contacts and is thus well suited for networks with opportunistic contacts.

     Routing in IC-MANETs with opportunistic contacts is challenging since contact information is not known in advance. Three simple location unaware routing protocols for this environment are Randomized Routing, Epidemic Routing and Spray and Wait. Randomized Routing is a single copy routing scheme in which a packet randomly moves around the network until it reaches the destination. Epidemic routing extends the concept of flooding in IC- MANETs where every node in the network receives a copy of the packet. Spray and Wait routing protocol sprays a limited number of copies into the network, and then waits until one of these nodes meets the destination.

     If nodes are location-aware, then the relative position of the nodes can be used to make the forwarding decision. This is a property used by LAROD. In addition to LAROD there are two other delay-tolerant geographical routing protocols published. These protocols are motion vector (MoVe) and

     GeoDTN+Nav. Both these protocols are used in vehicular ad hoc networks (VANETs) and assume the destination to be static.

     Location Services

     For a geographical routing protocol to be successful, it must be supplemented by a location service that can provide position information for all potential destinations. There is a substantial body of research that treats location services for MANETs but as indicated, through the use of static receivers in MoVe and GeoDTN+Nav, there are, to our knowledge, no proposals on how a location service can be provided in a delay-tolerant setting. In this section, we will provide an overview of the principles used for location services in MANETs and discuss why most of them are not directly transferrable to an IC-MANET. For connected MANETs, there have been several suggestions for location services, ranging from simple flooding-based services to hierarchical services. These location services have been classified according to Fig..1., based on how location servers are selected and queried. One major difference between the flooding-based location services and the mapping based services is the number of nodes that act as location servers. In the mapping-based services, a subset of the nodes in the system act as location servers and location information requests have to be routed to one of these nodes. In the flooding based services, all nodes act as location servers. If we study the architectural concepts used by the location services from a delay-tolerant perspective, we will see that most concepts will have significant problems when full network connectivity is not available. In a mapping-based service, the node that requests location information needs to access one node in the subset of nodes that act as location servers for the destination node. In a delay-tolerant setting, this case will significantly delay the time until a message can be sent toward its destination due to the transport time for a location query and its response .In the flooding-based services, there is no delay for reaching the location service, because it is located in the source node, but the time to acquire the location information significantly differs between proactive and reactive services. A reactive location service first tries to obtain the position of the destination when it is requested. If the information is not available in the local cache, then the location server broadcasts an information request over the network. Due to the disconnected nature of the network, there will be similar problems with delays as for the mapping-based location services. One protocol that attempts to limit the cost of a location request by having a proactive component is Brownian gossip. In Brownian gossip, nodes exchange information on previous encounters when two nodes meet. This information is used to guide a location request toward the destination nodes position. We have taken the principle of how Brownian gossip routes location requests by continuous refinement of the destinations position when routing data packets within LARODLoDiS.

     A proactive location service continuously distributes the position of all nodes in the network, which means that location information will immediately be available when

     needed in the source node. The problem with this system wide distribution of location information is that it can consume large amounts of system resources if not properly designed. Two location services with very different proactive elements are: 1) the DREAM location service (DLS) and 2) the simple location service (SLS) . In DLS, a node broadcasts its position to nearby nodes at a given rate and to nodes further away at a lower rate. The rates depend on a nodes speed, but a minimum rate is guaranteed if a node moves very slowly or not at all. In SLS, on the other hand, location data are only exchanged between neighbors. By exchanging location tables between neighbors, communication is kept local while permitting the location data to globally be distributed in the system. Both DLS and SLS have a reactive component that inquires a node location by broadcasting a request if the required location data are not available in the source node. As previously discussed, these system wide broadcasts are problematic in an IC- MANET.

     We believe that, to minimize routing delays in an IC- MANET, all nodes need to have a location service that has data about the location of all other nodes in the system. Due to the disconnected nature of IC-MANETs, this information might be old for some nodes, but as we will show in the evaluatios, even inaccurate data can successfully be used with a proper design of the routing protocol. We will base LoDiS on the proactive element of SLS and modify the concept as required to meet the demands of an IC-MANET environment.

     Fig.1. Taxonomy of location services

  2. ROUTING WITH LOCATION SERVICE

     In this section, we first describe an enhanced version of the IC-MANET geographical routing protocol LAROD and how it integrates with a location service, followed by a description of the novel IC-MANET location service LoDiS. The ns-2 source code for LAROD and LoDiS is freely available for scholarly research

     LAROD

     LAROD is a geographical routing protocol for IC-MANETs that combines geographical routing with the storecarry forward principle. It is a beaconless protocol and uses greedy packet forwarding when possible. When greedy forwarding is not possible, the node that holds the packet (the custodian) waits until node mobility makes it possible to resume greedy forwarding.

     To forward a message toward the destination, a custodian simply broadcasts the message. All nodes within a predefined forwarding area are eligible to forward the packet and are called tentative custodians. All tentative custodians set a delay timer td specific for each node, and the node whose delay timer expires first is the selected new custodian. Upon becoming a custodian, the node forwards the message in the same manner as the previous custodian. The old custodian that sent the message and most other tentative custodians will overhear this transmission and conclude that a new node has taken over custody of the packet. If no such transmission is heard, the current custodian repeats (and keeps repeating) the broadcast of the message (with an interval of tr) until a new custodian becomes available due to node mobility. The rebroadcast time tr is randomly chosen for each transmission between two configured values. The values should be chosen so that forwarding opportunities are not missed as well as to avoid wasting bandwidth. It is possible that not all nodes in the forwarding area will overhear the broadcast made by the new custodian, thereby producing packet duplicates. This case will not only increase the load in the system but will enable the exploration of multiple paths to the destination as well. When the paths of two copies cross, only one copy will continue to be forwarded. To prevent a packet from indefinitely trying to find a path to its destination, all packets have a time to live tTTL expressed as a duration. When the TTL expires, a packet is deleted by its custodian.

     Fig.2. LAROD Forwarding area examples

     The forwarding area can have many shapes, but it should be designed in such a way that progress toward the destination is guaranteed. One attractive property is the potential for all nodes within the forwarding area to hear each others transmissions. This case will reduce the risk of tentative custodians failing to receive the packet transmitted by the new custodian. Examples of shapes that meet these criteria include a 60 circle sector, a Reuleaux triangle, or a circle [see Fig. 2.(a)(c)]. The longest distance between two points within these shapes must be the assumed radio range. If overhearing is not a critical property and we want to maximize the probability of finding a new custodian, then the forwarding area should include all nodes that guarantee progress toward the destination [see Fig. 2(d)]. To avoid very small hops and to cater for inaccuracies in the positioning service, e.g., the Global Positioning System (GPS),a minimum forward distance may be prudent [the small gap between the custodian and the progress forwarding area in Fig. 2(d)].

     All these forwarding areas can be used in LAROD as a parameterized input. In this paper, we have chosen the

     progress forwarding area, The delay timer td for each node can be set based on many principles, where two natural ones are to favor short hops or long hops toward the destination. Short hops are advantageous if much data will be exchanged between the nodes, because the transfer probability is higher with a shorter distance. The downside is that more hops create higher overhead. Long hops will reduce the number of hops, but the downside is that the transfer reliability between distant nodes is lower. As a middle ground, one can consider a delay timer that prioritizes nodes at some set distance from the custodian. The function that sets the delay timer is a configuration parameter in LAROD, but for purposes of this paper, we have chosen a mechanism that provides long hops toward the destination. Details on the delay timer function is found elsewhere and are omitted due to space restrictions. The proposed delay timer functions do not take the direction of node movement into account, although this condition would have been feasible. The main reason is that, even if the next custodian might move in the wrong direction, the hope is that it can forward the packet to a node closer to the destination. Another reason is that node directions are not stable, and a node might turn and move toward the destination. For these reasons, a packet is always forwarded toward the destination, even if it, in some cases, might be returned to the old custodian due to node movement.

     To stop further transmission of a packet by custodians and tentative custodians when it has been delivered to the destination, an acknowledgement packet (ack) is sent by the destination at reception. All nodes that hear an ack will store the acknowledgement information until the packet times out. If a node receives a packet for which it previously has received an acknowledgement, then it broadcasts an acknowledgement to stop the transmission of the packet. Acknowledgements are not intended to reach the source; they are only intended to prevent further forwarding attempts by nodes holding the acknowledged packet

     Fig. 3. LAROD-LoDiS path visualization example.

     To manage the inaccuracies inherent in an IC-MANET location service, LAROD inquires the location service at each packet hop, and if more accurate (more recent) position data are available, then the routed packet is updated. This way, the quality of the location data is incrementally improved as the packet approaches the destination. To further improve the quality of the location data in the location service, LAROD provides it with the location data

     available in received packets. For a full description of the routing protocol, see Fig. 3.

     One actual LARODLoDiS routing example with the progress forwarding area illustrates in Fig.4 . Solid lines are wireless forwards, dotted lines are movements by custodians when a packet could not be forwarded, and the dashed line is the movement by the destination. When the packet is generated by the source, we see that the actual location of the destination differs from the one stored in the sources location service. In addition, while the packet is routed, the destination moves, and the destination position in the routed packet has to be updated to reflect the movement. When the source node transmits the packet, there are two tentative custodians that are very far from each other to overhear the others transmission, which means that two copies of the packet are created and sent through different paths. After a while, these paths cross, and one copy is discarded.

     o Source node at data packet generation Get destination location from location

     service

     Broadcast data packet

     Set up timer for rebroadcasting packet to

     tr

     • Destination node at data packet reception If the packet is received for the first time

       Deliver the data packet to the application Broadcast ack packet

     • All intermediate nodes at data packet reception

       Update location service with data packet location information

     • At ack packet reception

       Update location service with ack packet location information

       If the node has a copy of the packet Remove packet

     • When a data packet rebradcasting timer expires

     If the packet s TTL has expired (tTTL) Remove packet

     Else

     Update location information in the packet with location server data

     Broadcast data packet

     Set up timer for rebroadcasting the packet

     to tr

     o Source node at data packet generation Get destination location from location

     service

     Broadcast data packet

     Set up timer for rebroadcasting packet to

     tr

     • Destination node at data packet reception If the packet is received for the first time

       Deliver the data packet to the application Broadcast ack packet

     • All intermediate nodes at data packet reception

       Update location service with data packet location information

     • At ack packet reception

       Update location service with ack packet location information

       If the node has a copy of the packet Remove packet

     • When a data packet rebroadcasting timer expires

     If the packet s TTL has expired (tTTL) Remove packet

     Else

     Update location information in the packet with location server data

     Broadcast data packet

     Set up timer for rebroadcasting the packet

     to tr

     Fig. 4. LAROD pseudocode

     LoDiS

     In MANETs, it is generally assumed that the relative movement of a node compared with the radio range is small during the interval from a node location request to the data packet delivery at the destination. If this is not the case, then either the location of the destination must be updated in the

     routed packet as it approaches the destination, or some other routing mechanism must be used after the packet has reached the assumed location of the destination.In an IC- MANET environment, we know that information exchange can be delayed by partitions in the topology, which means that any time-dependent information that is received is more or less inaccurate. This condition means that any location service in an IC-MANET will generally only provide inaccurate location information due to the time taken for a location update to reach the server and/or the time taken for a location request to be answered by a location service. These issues force a designer of a location service in an IC- MANET to decide on how the location errors that the system will inevitably have are managed.

     LoDiS Protocol:

     In LoDiS, every node is a location server, and location data are updated by data exchanges as nodes encounter each other. The reason that all nodes are location servers is to avoid delaying the packet at the source node. If only a limited set of nodes were location servers, then the transmission of a data packet will be delayed by the time it takes for a location server to respond to the location request. Due to the disconnected nature of IC-MANETs, this delay could be long. With the low cost of memory, maintaining location tables that contain data on all nodes in the system should not be a problem in a UAV, even for fairly large systems (thousands of nodes). If we assume that each location entry requires 30 B, then 1000 nodes would require

     30 kB, which is a very small requirement by modern standards. When the routing protocol requests a location from LoDiS, one thing that it can relatively be sure of is that the location will be wrong, but if the provided location points the packet in the approximate right direction, it should be possible to use it as an initial estimate. To reduce the location error, the geographical routing protocol should update the location data in a packet for each node that the packet traverses. This approach is done by inquiring that nodes local LoDiS server whether it has more accurate information about the destination. Because nodes closer to the destination should have better information on the destinations location, the accuracy of the destination position is incrementally increased. This position update approach, to some extent, resembles the query routing in Brownian gossip . Although Brownian gossip uses the distributed location information to guide location queries toward the destination, LARODLoDiS uses the location information to route the actual data packets due to the disconnected nature of IC-MANETs. LoDiS builds on the conceptual solution used by SLS and employs the principle of MANET broadcast gossip to distribute the continuously changing location data. A LoDiS location server broadcasts the information it has in its location table. Any node that hears this broadcast merges the information with the one it has, and the most recent information will be propagated when that node makes its LoDiS broadcast. This way, location information is spread like rings on water. In addition

     to the broadcasts, LoDiS also accepts location updates from the routing protocol. The routing protocol will have some location information in the packets that it routes, which could improve the data in the location service. The pseudocode for LoDiS is shown in Fig. 5

     • At a set interval broadcast location data Select location data: vector with elements (

       node, location ,timestamp) Broadcast the data

     • When a LoDiS broadcast is received

       For each received location data that is more recent

       Update the entry in the LoDiS server

     • When location data is received from the routing protocol

     If the supplied information is more recent

     Update the entry in the

     LoDiS server

     • At a set interval broadcast location data Select location data: vector with elements (

       node, location ,timestamp) Broadcast the data

     • When a LoDiS broadcast is received

       For each received location data that is more recent

       Update the entry in the LoDiS server

     • When location data is received from the routing protocol

     If the supplied information is more recent

     Update the entry in the

     LoDiS server

     To limit the overhead generated by LoDiS, each node is only allowed to generate one packet worth of location data at a set rate. If we assume a packet size of 1000 B and that 10 B is required for each node (which includes some compression), then an update can transfer information on 100 nodes. If all location information stored in the node can fit in one packet,

     then all is well. If that is not the case, then a selection has to be made. The selection could range from simple round-robin algorithms to selection based on distance and information age.In the results presented in this paper, the number of nodes has been less than the data limit in a packet, and the use of different selection techniques has not been explored. The reason for having a fixed broadcast interval is that it will limit the per-node overhead. If a dynamic interval would be used, then it should be influenced by factors such as the frequency of neighbor change, the number of neighbors, and the amount of new data to be distributed. As an example, Brownian gossip approximates these factors with the speed of the node. we will show that the overhead introduced by LoDiS is small compared with the routing overhead from LAROD. There are several reasons that we have chosen to regularly broadcast the location data instead of using an exchange each time two nodes meet. If an encounter exchange scheme is chosen, then the nodes need to broadcast regular beacon messages instead of location data broadcasts. When a beacon message is received, a node needs to determine whether it is a new encounter and, if it is, initiate an information exchange. This scheme is more complicated, and it also has the drawback that the exchange may not be properly be finished due to

     node movement or changed transmission conditions

     with the broadcast technique,if the data received by node then all is fine and well, and if it is not then the information will be again be broadcatrelatively soon

     another advantage with the choosen scheme is that

     each LoDiS node consumes a predictable amount of bandwidth. We have experimented with using time-outs for location ntries to reflect aging as done in SLS, i.e., that

     location data older than a set time period are inaccurate and should not be used. The results indicated that it is better to start to route a packet with existing location data rather than to wait until reasonably fresh location data become available

  3. EVALUATION

     In this section, we present the results from our evaluations of LARODLoDiS. The routing protocols have been evaluated in the network simulator ns-2 using the pheromone reconnaissance mobility model. The two main evaluation metrics used are delivery ratio and effort required for each generated data packet (overhead). The delivery ratio is the most important evaluation criterion, because it determines the quality of service as perceived by the user or application. The effort used to transfer a packet is also important, because lean protocols will allow either a higher throughput or lower power consumption by the nodes, which will be measured as the number of transmissions performed per generated data packet. The node density is a very important parameter, because, together with the mobility model, it determines how well connected the system is. A study of node densities used in a range of earlier works has shown that a wide range of relative densities are used by various researchers. The density used in this paper produces small groups of connected nodes (partitions). The chosen density gives a degree of connectedness in the network that is below the percolation threshold , which means that it is very likely that no large dominating partitions exist at any point in time.

     LARODLoDiS Compared to Spray and Wait

     To show the merit of LARODLoDiS compared with other routing schemes, we have compared it with spray and wait. Spray and wait is reportedly an efficient routing protocol with good delivery properties. It would also be interesting to compare LARODLoDiS with another geographical ICMANET routing protocol. However, because both MoVe and GeoDTN+Nav are designed for road-based scenarios and lack a location service, we have not found it worth the effort to reimplement them in ns-2. In a previous paper, we have compared LAROD with an epidemic routing protocol and showed that LAROD gave essentially the same delivery ratio as the epidemic protocol under low-load scenarios but with four to eight times lower overhead. Because spray and wait was originally implemented for a custom simulator, we have reimplemented it in ns-2. Comparing the delivery ratio and overhead of LARODLoDiS with spray and wait, we see that the benefit of using geographical information and active forwarding is very high . Under the pheromone reconnaissance mobility model, spray and wait does not provide an acceptable delivery ratio. In Fig. 6 , we see the impact of the packet lifetime on the delivery ratio. As expected, both routing protocols benefit from having more time to find a path from the source to the destination. The relative performance of the two protocols is not surprising, because spray and wait mainly uses node mobility to forward packets, whereas LAROD actively forwards the packet through peers toward the destination. As long as node encounters are frequent, then protocols that actively forward

     should outperform protocols that rely on node mobility as the main delivery mechanism. It is also interesting to note that the overhead for spray and wait is about double that of LARODLoDiS for a spray factor of 10 and almost four times higher with a spray factor of 20 in Fig.7.

     Fig.6. Delivery ratio for different packet lifetimes under pheromone mobility

     Fig. 7. Overhead for different packet lifetimes under pheromone mobility

     If we study the performance of the two routing protocols under varying node densities, we can make some interesting observations. For both routing protocols, the delivery ratio improves with increased node density in Fig. 8, but the change is more pronounced for LARODLoDiS than for spray and wait. The reason that the delivery ratio for spray and wait is only marginally improved with increased node density is that its main routing mechanism, i.e., waiting until a node that holds the packet meets the destination, is not affected by the node density. The improvement with increased node density results from the initial distribution of the packet taking less time. LAROD, on the other hand, actively tries to forward a packet toward the destination through wireless forwards, and with increased node density, the forwarding opportunities are increased.

     Fig.8. Delivery ratio for different node densities under pheromone

     mobility

     The overheads in the two protocols, as presented in Fig. 9, illustrate what is expected from the protocol designs. For LARODLoDiS, the overhead increases with a decreased node density as delivery latency increases, and more packets exist in the network for their maximum lifetime (TTL). For spray and wait, the overhead increases with increased node density, because the node encounter rate increases, and for each new encounter, some data have to be exchanged toward possible message replication.

     These results and the influence of the mobility model presented in this section show the impact that system parameters have on the network performance. For these reasons, we think that it is very important to determine the system parameters and required performance before the routing protocol is selected. In some systems, it might be trivial to achieve the required performance, whereas in other systems, it might be impossible ,even with oracle knowledge.

     Fig. 9. Overhead for different node densities under pheromone mobility

  4. CONCLUSION

     The availability of node location information enables the use of efficient geographical routing protocols in MANETs and IC-MANETs. One major component for a geographical routing protocol is a well-performing location service. The location service will provide information on where a destination is located to have a point to route a packet toward. In this paper, we have shown that, by using aMANET broadcast gossiping technique and continuous modification of packet location information, geographical routing in IC-MANETs is feasible. The proposed location service (LoDiS) has then been integrated with a routing protocol (LAROD) and thoroughly studied in comparison with a high-performance baseline. We have also shown that the delivery ratio for LARODLoDiS is the same as that obtained using LAROD with an oracle location servicea very important result. The cost of LoDiS is also relatively small compared with the basic cost of routing using LAROD. Because the cost of LoDiS is constant per node, the more traffic there is in the network, the lower the relative cost will be. We have also shown that LARODLoDiS gives a much higher delivery rate at a much lower overhead compared with the efficient topological routing protocol spray and wait at a node density relevant to a realistic UAV reconnaissance application. The fact that LARODLoDiS would have a better delivery ratio than spray and wait was

     not that surprising. What was a bit more unexpected was the large difference in overhead to the benefit of LAROD LoDiS. One reason for this difference is that spray and wait uses message replication to exploit the mobility of several nodes to reach the destination. Another reason is that spray and wait uses more packets to transfer eachdata packet. LAROD uses overhearing as acknowledgement, whereas spray and wait transmits an explicit acknowledgement packet. LoDiS is a very good base to use for further studies of location services in IC-MANETs and DTNs. Depending on what one considers a reasonable scenario for an IC- MANET,further studies and improvements of the LAROD LoDiS routing algorithm should be done for very sparse systems (nodes that normally lack a neighbor) or a mixed scenario with both dense and sparse areas. Current work includes the evaluation of a manycast algorithm in disaster area networks where pockets of intense activity and large sparse areas can simulaneously be present . In addition, the location service performance shouldbe studied for very large systems (thousands of nodes). For the very sparse systems, information dissemination will probably be very slow, and it is not certain that geographical routing is the best choice in such a scenario. For very large systems, the challenge will be how the location information is distributed for all the nodes in the system. To do this approach, one probablyhas to employ some kind of data compression or approximation methods for nodes located far away. If parts of the network become very dense, the transfer of location data may start to consume too much bandwidth locally at the dense spots. It might be interesting to study some throttling techniques to free up the bandwidth. As found in the experiments reported in this paper, it is important to start to route a message, even if the exact location is not known. It would be interesting to study the best approach to use if there is no location data for a node with which one wants to communicate or if the location data is very old. Another topic that should be studied is how areas permanently void of nodes (e.g., no fly zones for UAVs) can be handled. If these zones do not have a convex shape, then it is possible that packets get stuck in local minima and never manage to navigate past the empty area. To better understand the properties of LAROD and LoDiS, our ongoing work mathematically analyzes the algorithms. Using the mathematical descriptions, it is possible to predict the behavior of LARODLoDiS, for example, in the aforementioned settings

  5. FUTURE ENHANCEMENT

LAROD mainly focus on the Geographical routing with greedy forwarding .Greedy routing is very simple and efficient since node do not need to maintain rooting information and packets are forwarded immediately without being duplicated. Compared to other protocols, greedy routing has extremely low routing over-head and it scales well to large wireless adhoc networks. However, greedy routing does not guarantee that a packet reaches its destination. If the distance to the destination is used to choose the next edge to send a packet, a local minimum may be reached. Even if the direction is used to choose the next edge, a loop may be formed, it is the major drawback of greedy forwarding . That is, it stuck at local minimum or a

dead end. Here we can provide a recovery strategy. As a future enhancement the design of LAROD-LoDiS may be changed by considering Face Routing at the local minimum. Face routing, is the first geometric routing algorithm that guaranteed message delivery without flooding. Several variants of face routing protocols were subsequently proposed. Face routing is applied on a plane sub graph of the network graph. A plane graph divides the plane in to faces. The line segment between the source node and the destination node intersects some faces. In face routing, the packet is forwarded along the boundaries of these faces. A specific face routing protocol provides a set of rules for each node to decide where to send a packet using only the local information about its neighbors and the information in the packet header. So there by increasing the performance of LAROD-LoDiS routing by using Greedy Forwarding with Face Routing.

REFERENCES

1. A. Lindgren and P. Hui, The quest for a killer app for opportunistic and delay-tolerant networks, in Proc. 4th ACM Workshop Challenged Netw., 2009, pp. 5966.

2. N. Aschenbruck, E. Gerhards-Padilla, and P. Martini, Modeling mobility in disaster area scenarios, Perform. Eval., vol. 66, no. 12, pp. 773790, Dec. 2009.

3. M. Asplund and S. Nadjm-Tehrani, A partition-tolerant manycast algorithm for disaster area networks, in Proc. 28th Int. Symp. Reliable Distrib. Syst., 2009, pp. 156165.

4. M. B. Donley and N. A. Schwartz, United States Air Force Unmanned Aircraft Systems Flight Plan 20092047, 2009. [Online]. Available: http://handle.dtic.mil/100.2/ADA505168

5. E. Kuiper and S. Nadjm-Tehrani, Mobility models for UAV group reconnaissance applications, in Proc. Int. Conf. Wireless Mobile Commun., 2006, p. 33.

6. F. Warthman, Delay-Tolerant Networks (DTNs): A Tutorial v1.1.Warthman Assoc., Mar. 2003. [Online]. Available: http://www.dtnrg.org/docs/tutorials/warthman-1.1.pdf

7. P.-C. Cheng, K. C. Lee, M. Gerla, and J. Härri, GeoDTN +Nav: Geographic DTN routing with navigator prediction for urban vehicular environments, Mobile Netw. Appl., vol. 15, no. 1, pp. 6182, Feb. 2010.

8. J. LeBrun, C. Chuah, D. Ghosal, and M. Zhang, Knowledge-based opportunistic forwarding in vehicular wireless ad hoc networks, in Proc. IEEE 61st Veh. Technol. Conf., 2005, pp.22892293.

9. E. Kuiper and S. Nadjm-Tehrani, Geographical routing in intermittently connected ad hoc networks, in Proc. 1st IEEE Int.Workshop Opportunistic Netw., 2008, pp. 16901695.

10. S. M. Das, H. Pucha, and Y. C. Hu, Performance comparison of scalable location services for geographic ad hoc routing, in Proc. IEEE 24th Annu. Joint Conf. IEEE Comput. Commun. Soc., 2005, pp. 12281239.

11. T. Spyropoulos, K. Psounis, and C. S. Raghavendra, Spray and wait: An efficient routing scheme for intermittently connected mobile networks, in Proc. ACM SIGCOMM Workshop Delay-Tolerant Netw., 2005, pp. 252259.

12. R. Friedman, D. Gavida, L. Rodrigues, A. C. Viana, and S. Voulgaris, Gossiping on MANETs: The beauty and the beast, Oper. Syst. Rev.,vol. 41, no. 5, pp. 6774, Oct. 2007.

13. V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, R. Durst, K. Scott, K. Fall, and H.Weiss, Delay-tolerant networking architecture. RFC 4838. [Online]. Available: ftp://ftp.rfc-editor.org/in-notes/rfc4838.txt

14. T. Spyropoulos, K. Psounis, and C. S. Raghavendra, Efficient routing in intermittently connected mobile networks: The single-copy case,IEEE/ACM Trans. Netw., vol. 16, no. 1, pp. 6376, Feb. 2008.

15. A. Vahdat and D. Becker, Epidemic routing for partially connected ad hoc networks, Duke Univ., Durham, NC, Tech. Rep. CS-2000-06, 2000.

16. R. Bruno and M. Nurchis, Survey on diversity-based routing in wireless mesh networks: Challenges and solutions, Comput. Commun., vol. 33, no. 3, pp. 269282, Feb. 2010.