Information Technology Reference
In-Depth Information
Fig. 4.4
A loop in directional routing
4.3.3
GPSR
Nearly Stateless Routing with Guaranteed Delivery are schemes where nodes
maintain only some local information to perform routing. The face routing and
Greedy-Face-Greedy (GFG) schemes were described in [
25
]. In order to ensure
message delivery, the face routing (called perimeter algorithm in [
10
]) constructs
planar and connected so-called Gabriel subgraph of the unit graph, and then applies
routing along the faces of the subgraph (e.g., by using the right-hand rule) that
intersect the line between the source and the destination. If a face is traversed using
the right-hand rule then a loop will be created; since face will never be existed.
Forwarding in right-hand rule is performed using directional approach. To improve
the efficiency of the algorithm in terms of routing performance, face routing can be
combined with algorithms that usually find shorter routes, such as the greedy
algorithm to yield GFG algorithm [
18, 24
]. Routing is mainly greedy, but if a
mobile host fails to find a neighbor closer than itself to the destination, it switches
the message from “greedy” state to “face” state [
6
].
Authors in [
10
] transformed GFG algorithm into Greedy Perimeter Stateless
Routing (GPSR) protocol by including IEEE 802.11 medium access control
scheme. The perimeter routing strategy of the GPSR is based on planar graph
traversal and proposed to address the local maximum problem of greedy forwarding
[
6, 23
]. It is performed on a per-packet basis and does not require the nodes to store
any additional information. A packet enters the recovery mode when it arrives at a
local maximum. It returns to greedy mode when it reaches a node closer to the
destination than the node where the packet entered the recovery mode [
6
]. GPSR
guarantees that a path will be found from the source to the destination if there exists
at least one such path in the original non-planar graph [
6
].
Search WWH ::
Custom Search