5 Geographical routing protocols

Some routing protocols make use of geographical information, such as GPS coordinates. Typically, nodes communicate their location through the network, so that other nodes can determine the shortest path. Using geographical information makes it possible to select the truly shortest path. Furthermore, one only needs an (geographical) address to contact a host.

The disadvantage is, obviously, that each node has to know its location. In some environments, a GPS receiver can be used to obtain the location. However, GPS receivers are expensive and consume relatively much power.

Geographical routing
Figure 5: Geographical routing

5.1 DREAM

The DREAM protocol was proposed in [Bas98]. It assumes that each node knows its own location. Each node then communicates its address and location through the network. When a packet is sent, it is sent to the direction of the receiving node.

DREAM makes use of what is called the distance effect: the greater the distance separating two nodes, the slower they appear to be moving with respect to each other. Neighbours close by are frequently informed of the location of a node; nodes which are farther away only occasionally receive this information. The further a packet travels to its destination, the more detailed the position of the destination becomes.

Furthermore, DREAM takes into account the mobility of the nodes. When a node travels fast, it frequently sends its location information to its neighbours.

DREAM is similar to HSLS in that the update frequency is dependant on the distance to a node, only it uses coordinates instead of routing paths. This makes it very well scalable, but introduces the problem of determining the location for each node.

5.2 Location Aided Routing

Location Aided Routing
Figure 6: Location Aided Routing

The Location Aided Routing Protocol (LAR, [Ko00]) only uses geographical information for route discovery. It is based on an on-demand protocol, like AODV. If the sender knows where the destination was at some time and it knows its speed, it can determine in which area the destination is now. This area is called the expected zone. LAR uses this to limit the flooding of route discovery packets. Packets are flooded within an defined area containing both the source and the expected zone. When a node outside this area recieves a packet, it ignores it. When the destination receives the route discovery packet, it returns it with its current location and speed, which can assist in future route discoveries.

When a node enters the network, it has no information about the geographical position of other nodes. LAR will then fall back to the underlying protocol, which floods the route discovery packet. For LAR to be an improvement over flooding, the network has to be stable. LAR will perform well for moving nodes and disappearing nodes, but not when a lot of new nodes are added to the network. Furthermore, connections in the network has to be stable. If nodes connect to many other nodes for a short time, location information will not be available or accurate enough to make use of LAR.