Transcript Introduction to Sensor Networks

EECS 600 Advanced Network Research, Spring 2005
GPSR: Greedy Perimeter Stateless
Routing for Wireless Networks
Shudong Jin
February 14, 2005
Recall Last Lecture
• Dynamic Source Routing
–
–
–
–
Who gives the path?
How to obtain a path?
What is the routing metric?
What information is maintained?
• Different from Internet routing, but are there any
similarities?
EECS 600 Advanced Network Research, Spring 2005
2
This Lecture: Another Approach
• Geographical Routing
– Who gives the path?
• Routing is done locally by individual routers (hop-by-hop)
– How to obtain a path?
• Decided at the time of routing, no pre-computed full path
– What is the routing metric?
• Distance as the routing metric
– What information is maintained?
• A little local connectivity (and location) information is
maintained by each router
EECS 600 Advanced Network Research, Spring 2005
3
GPSR: Greedy Perimeter Stateless Routing
• Novel routing protocol for wireless datagram networks
that uses the positions of routers and the destination to
make packet forwarding decisions.
– Greedy forwarding used wherever possible and decisions made
using only information about the router’s immediate neighbors.
– Perimeter forwarding used where Greedy forwarding not
possible i.e. algorithm recovers by routing around the perimeter
of the region.
– Stateless in that a router keeps state only about local topology,
hence scales better as the number of destinations increases.
EECS 600 Advanced Network Research, Spring 2005
4
Greedy Forwarding
• Assumed: Packets are marked by the originator
with their destination’s location.
• A forwarding node can make a locally optimal,
greedy choice in choosing a packet’s next hop.
– Most of the times the locally optimal choice is the
neighbor closest to the packet’s destination. (how
locally?)
• The ideal case: The packet is successfully
forwarded using closer geographic hops to
reach the destination.
EECS 600 Advanced Network Research, Spring 2005
5
Greedy forwarding example
EECS 600 Advanced Network Research, Spring 2005
6
How to Know the Positions?
• Periodically each node transmits a beacon to the
broadcast MAC address, containing its identifier (e.g. IP
address ) and position.
– X and Y co-ordinates are encoded by two 4-byte quantities.
• Mean Beacon Transmission interval is uniformly
distributed. 0.5B ~ 1.5B
• Upon not receiving a beacon for longer than the time out
interval = 4.5B, a GPSR router assumes that either the
neighbor has failed or has moved out; the GPSR router
deletes that entry from its table.
EECS 600 Advanced Network Research, Spring 2005
7
More Optimizations on Beaconing
• Handling mobility
– Choice of beaconing interval to keep node’s neighbor
tables current depend on the mobility in the network
and range of node’s radios.
• Reducing overhead
– Beaconing generates proactive traffic. To avoid this
additional cost, GPSR piggybacks the local sending
node's position on all data packets it forwards. Thus
all packets serve as beacons.
• Q: How to enforce random beacon interval, then?
EECS 600 Advanced Network Research, Spring 2005
8
Greedy Forwarding May Fail
– The Greedy forwarding algorithm might fail in
circumstances where the only route to a destination
requires a packet to move temporarily away from the
destination.
• An example from the paper
• More knowledge on topology help?
EECS 600 Advanced Network Research, Spring 2005
9
Perimeters
• When Greedy Forwarding fails, how can we get
out of the situation?
– Right-hand rule to route around voids
EECS 600 Advanced Network Research, Spring 2005
10
Perimeter Forwarding
• Perimeter forwarding makes use of Planarized
graphs which are graphs in which there are no
crossing edges.
– Why need the no-crossing heuristics? Give an
example
– Two algorithms: RNG (Relative Neighborhood Graph)
and GG (Gabriel Graph)
EECS 600 Advanced Network Research, Spring 2005
11
RNG (Relative Neighborhood Graph)
EECS 600 Advanced Network Research, Spring 2005
12
GG (Gabriel Graph)
EECS 600 Advanced Network Research, Spring 2005
13
Planarized Graphs: Example
Full graph, the GG subset, the RNG subset.
EECS 600 Advanced Network Research, Spring 2005
14
GPSR
• This algorithm combines greedy forwarding on the full
network graph and perimeter forwarding on the
planarized graph.
• State information: All nodes maintain neighbor tables
which store addresses of all radio-hop neighbors.
• Packet header fields
– GPSR packet headers include a field which indicates whether
the packet is currently in greedy mode or perimeter mode.
• All data packets are marked originally as greedy mode.
– Only the packet’s source sets the destination field.
EECS 600 Advanced Network Research, Spring 2005
15
GPSR Operations
• Upon receiving a greedy-mode packet
– the node forwards it to the geographically closest neighbor if
there is one.
– When no neighbor is closer, the node marks the packet to the
perimeter mode. GPSR also records in the packet, the location
Lp, the site where greedy forwarding failed.
• These perimeter mode packets are forwarded using Planar Graphs.
• Upon receiving a perimeter mode packet.
– Forward the packet using a planar graph traversal. GPSR also
compares the location Lp with the forwarding node’s location. It
then returns the packet to greedy mode if the distance from the
forwarding node to D is less than that from Lp to D.
– Perimeter forwarding is only intended to recover from local
maximum.
EECS 600 Advanced Network Research, Spring 2005
16
Simulation Results and Evaluation
• Packet delivery ratio
• Routing protocol overhead
• Path length
• Effect of network diameter (size)
• Number of states per router
EECS 600 Advanced Network Research, Spring 2005
17
More discussions
EECS 600 Advanced Network Research, Spring 2005
18
GPSR Example
EECS 600 Advanced Network Research, Spring 2005
19