GPSR routes tra?±c greedily in a direct geographic line from
370
Chapter 15 Information Forwarding and Tra?±c Engineering
the source to the destination. A route is not always guaranteed to be found
as, at any given node, there is a possibility that there is no neighboring node
in the direction of the destination. The routing is done on-demand where the
nodes only need to know the geographic location of their neighbors. At every
hop the routing node determines the best next hop by finding its neighboring
node which is closest to the destination, using the Euclidean distance as the
deciding metric. If no such neighbor is found, the node begins a search. The
search progresses as the node forwards the packet via the right-hand rule.
The right-hand rule states that the next hop is located counter clock-wise
to the edge created between the previous hop and the current hop. A visual
representation of this is shown in Figure 1.
Fig. 1. GPSR Algorithm: Light gray dashed lines represent greedy routing. Dark
dashed lines represent perimeter routing.
Every node receives its geographical position from a GPS or a localization
algorithm. This information is shared whenever a packet is forwarded
and during periodic transmissions. GPSR uses an absence of these periodic
messages as a flag that a neighboring node has either moved away or gone
to sleep. This method has been designed with scalability in mind. Regardless
of how many nodes are in the network or how many source-destination pairs
exist, the nodes only need the position of their neighbors to successfully route
data.
Pages:
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593