GPSR: an Overview
GPSR is a geographic routing protocol that was originally designed for mobile
ad-hoc networks. Given the coordinates of a node, GPSR routes a packet to
that node using location information only. To do this, GPSR contains two
di?®erent algorithms: greedy forwarding and perimeter forwarding.
Greedy forwarding is conceptually simple. Assume each node in a network
knows its own location, and that of its neighbors. When a node receives a
message destined to location D, it sends the message to another neighbor
C which is closer to D than itself. Such a neighbor might not always exist;
in this case, GPSR invokes perimeter routing at that node. We now describe
perimeter routing.When a packet finds itself at a node which has no neighbors
closer to the destination than itself, we say that the packet has encountered a
void. Figure 5 depicts a situation where a packet destined for node D arrives
at a node A. No neighbor of A is closer to D than A itself, indicating the
existence of a void. Voids can result from irregular deployment of nodes, as
well as from radio-opaque obstacles. A natural technique to route around
a void is the right-hand rule (Figure 5). According to this rule, a traversal
walks around the perimeter of the void. However, it can be shown that using
the right-hand rule on the graph formed by mere connectivity between nodes
300
Chapter 12 Data Management in Sensor Networks
may not work in many cases.
Pages:
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483