Location-Aided Routing Protocol

LAR is an on-demand protocol who is based on the DSR (Dynamique Source Routing)!

The Location - Aided Routing Protocol uses location information to reduce routing overhead of the ad-hoc network! Normally the LAR protocol uses the GPS (Global Positioning System) to get these location informations. With the availability of GPS, the mobile hosts knows there physical location.

To reduce the complexity of the protocol, we assume, that every host knows his position exactly, the difference between the exact position and the calculated position of GPS will no be considered! We also assume that the mobile nodes are only moving in a two-dimensional plane!

Expected Zone & Request Zone

Expected Zone

First, we consider that the node S (source) needs to find a way to node D (destination) ! Node S knows that D was at position L. Then, the "expected zone" of node D, from the viewpoint of node S, is the region that node S expects to contain node D! When node S knows, that node D travels with a several speed, node S considers this speed to determine the expected zone of D!
When node S has no information about the position of D, the entire region of the ad-hoc network is assumed to the expected zone! Then the algorithm reduces to the basic flooding algorithm!
In general we can say, as more as the node S knows about D, as smaller can be considered the expected zone!

figure 1



a) The circular expected zone of node D
b) When node S knows that D is moving north, then the circular expected zone can be reduced to a semi-circle.

Request Zone

Again, we consider that node S needs to find a path to node D. Node S defines a Request Zone like in figure 1 (a)! After that S sends a route request like in the normal flooding algorithm. With the difference, that a node only forwards this route request when it is in the Request Zone!
But there are two different reasons, that regions outside the request zone havge to be include in the Request Zone:

1) Node S is not in the Expected Zone of D, then this Expected Zone has to be enlarged to the Request Zone like in figure 2 (a).

2) But now we ask us if this Request Zone of figure 2 (a) is a good Request Zone! We see in figure 2 (b) that all the nodes between S and D are outside of the Request Zone! So it is not guaranteed, that a path between S and D can be found. LAR allows to expand the Request Zone, so that it easier to find a path. But we have to consider, when we increase the Expected Zone like in figure 2 (c), the route discovery overhead will also increase.

figure 2

Membership of the Request Zone

LAR algorithms are essentially identical to the flooding algorithm! With the difference that an node not in the Request Zone doesn't forward the route request to it's neighbour! There are two different possibilities to determine that a node is 'member' of the Request Zone:

1) LAR Scheme 1

This first Scheme uses a Request that is rectangular! The Node S includes the coordinates of the four corners of the Request Zone in the route request message! Node S knows his own coordinates of his own GPS! The coordinates of the opposite corner becomes S with the corner of the Expected Zone! With these two points, Node S can make e rectangular and has the coordinates of the four corners of the rectangular! The following picture figure 3 shows this rectangle an helps to understand how the node S builds the rectangle!

figure 3



When an node with own coordinates outside of the rectangle, this node discards the route request! So the flooding of the ad-hoc network is reduced!

Now, the route request sended by node S is arrived at node D and replies with a route reply message! Node D includes in this route reply message its current location an the time where the message is sended! S, when node S receives this message and records the location of D and S can use it to determine the Request Zone in a future route discovery!

LAR Scheme 2

In this scheme of the LAR protocol node S, who will find a path to D, knows the location (Xd,Yd) of D. With this coordinates, node S calculates the distance from D (DISTd). Both, the coordinates and the distance are included in the route request! Now, when a node receives the route request from S, it calculates the distances between itself and D. When this distance as larger then DISTd from node S it discards the route request. Otherwise it sends the route request with included its own distance to D and the coordinates of D to his neighbours! So the route request will arrive at node D and route reply will be send back to S!
The figure 4 will help in the understanding of the scheme 2 of the LAR protocol!


figure 4



All pictures and references: Ko1998

"Location-Aided Routing Protocol" is mentioned on: Ad-Hoc Protocols (Classification) | Ad-Hoc Workshop Winter 04/05 (Termine)