paper no: mob3
last update: 23/05/08
(Location Based Dissemination Protocol For Mobile Adhoc Network)
1. INTRODUCTION :
A mobile ad hoc network  is an autonomous system of mobile, wireless nodes. There is no static infrastructure such as base station. If two nodes are not within radio range, all message communication between them must pass through one or more intermediate nodes. Thus, in such a network, each node functions not only as a host but also as a router. As the nodes are mobile, the network topology is dynamic, leading to frequent and unpredictable connectivity changes. It is critical to route packets to destinations effectively without generating excessive overhead.
This presents a challenging issue for routing protocol design since the protocol must adapt to frequently changing network topologies in a way that is transparent to the end user. Knowledge of geographic locations of the nodes can aid in routing protocol design. Several location based routing protocols have been proposed (see, for example, [7, 8, 6]) in recent literature.
These protocols utilize available location information of other nodes for low-overhead routing. However, for these protocols to be effective, this location information must be efficiently disseminated and/or updated in the proactively announce their locations to other nodes. While these schemes are simpler, they are usually inefficient as they are dependent on some form of periodic flooding.
2. RELATED WORK :
There is a growing body of work that uses location information for routing in ad hoc networks. Early work started with the LAR and DREAM protocols. LAR  works as an add-on to any on-demand flood based protocol such as DSR  or AODV , and limits the route request flood within a zone where the destination is most likely to be found based on its past location and speed information.
The location dissemination here is passive. DREAM , on the other hand, disseminates location information actively (periodically) and creates a location database locally. It then floods data packets within a cone radiating from the source, where the destination is guaranteed to be found within the broad end of the cone. The design of this cone follows from the available location information. (Note here that the DREAM routing protocol was not used in our study above; only the DREAM location service component was used, as our goal was to compare location service protocols with routing as an application.) Several techniques were proposed for geographic forwarding where availability of location information is assumed and this information is directed used for packet forwarding without having to explicitly establish a route.
A very simple forwarding scheme simply forwards the packet to the neighbor closest to the destination. This is the technique we used. As mentioned before, some techniques are needed if this greedy method reaches a dead end, i.e., there is no neighbor closer to destination than the current node itself. Karp and Kung in their GPSR technique , and Bose et. al.  independently, present efficient techniques to recover from such situations. Another solution is provided in . In  authors propose GLS, a location database service. GLS uses geographic hierarchy to partition the network space onto grids.
Each node then maintains its current location in a number of location servers distributed throughout the network. Queries and registrations are sent to these servers using geographic forwarding. Care is taken such that location queries are sent to servers closer to the queries
DESIGN OF THE LDP :
Our project design involves the designing of the following modules,
1 Position Estimation of Mobile Terminals:
- Position Estimation of Mobile Terminals.
- Enhanced Location Dissemination.
- Boundary Buffering Module.
Figure 1.Position Estimation of MT
In this module, we use a very simple dead reckoning model which as a simple first order model that models a moving node's velocity (speed and direction). Complex models and use of path planning applications are possible, but not investigated here. We assume that each node in the network is aware of its location. Most commonly the node will be able to learn its location using an on-board GPS (Global Positioning System) receiver. Other methods such as radio-location , beacons from an available fixed infrastructure , or GPS-less positioning systems such as  are also possible. The accuracy of the location information will affect performance, though we will not discuss it here. In the dead reckoning model we have used, each node constructs a movement model for itself by periodically sampling its location estimates. It then computes its velocity components v x and v y along the X and Y axes from two successive location samples ( x 1 ,y 1 ) and ( x 2 ,y 2 ) taken at times t 1 and t 2 .
y 2 -y 1
V x =
t 2 -t 1
x 2 -x 1
V y =
t 2 -t 1
After the first calculation of its velocity components, the node floods the network with this information using a DRM update packet. This packet contains the node's id, its location coordinates and the calculated velocity components. The location and movement models together form the dead-reckoning model. Each node maintains a DRM table. Whenever it receives a DRM update from another node it adds or updates an entry for that node's model in its DRM table.
The model entry for each node in the table has a timestamp denoting when it was last updated. Thus, each node now has a location and movement model for every other node in the network. It uses this to estimate the location (x est ,y est ) ) of the nodes at the current time as per the following formula:
x est = x mod + (v xmod *( t cur – t mod ))
y est = y mod + (v ymod *( t cur – t mod )),
where, ( x mod , y mod) are the (x,y) coordinates and ( v xmod , v ymod) are the velocity components of the node in the model table, t mod = time at which model was updated and t cur = current time.
Note that we have a tacit assumption here that t mod actually reflects the time when the model is computed at the originating node. It is possible to include this computation timestamp in the DRM update, and use this time as t mod instead of the update time. In that case, however, t mod and t cur would be timestamps taken on different nodes. So, for this scheme to work, the nodes must have access to synchronized clocks on all nodes. Synchronized clocks are not unrealistic as they can be obtained from GPS fixes. But even if such synchronization is not available, we expect that error introduced would be negligible unless the mobile nodes move at an unrealistic fast speed. The reasoning for this is as follows.
(i) Assuming that t mod is the computation time, “loosely” synchronized clocks will work fine so long as the time-scale of the clock error is much smaller than the time-scale of a node's movement to significant distances. A significant distance here is a distance larger than the radio range.(ii) If no clock synchronization is available at all, t mod should reflect the time when the DRM update is recorded. In this case, the speed at which update messages propagate in the network must be much faster than the speed of the mobile nodes.
After the initial distribution of its dead-reckoning model, each node continues to periodically sample its location ( x cur ,y cur ) and also computes its predicted location as per the above model it advertised. It calculates the deviation of its current location from its predicted location by simply computing the Euclidean distance.
If this distance d exceeds a predetermined threshold (called the dead reckoning threshold ) the node recalculates the DRM and disseminates it again in the network. Otherwise, no further dissemination takes place. The threshold essentially determines the allowable error in the location estimates. Too small a threshold results in too many updates adding to the load in the network. Too large a threshold results in inaccurate and stale location information persisting the network for a long time. It is expected that the application (e.g.,routing) that utilizes the location information is able to choose an appropriate threshold based on the desired level of accuracy.
For Further more download pdf...