Geographical routing protocols

Minimum Energy Communication Network (MECN)

Minimum Energy Communication Network (MECN)
Relies on localized search for each node through a relay region concept
P(A,B)=t*d(A,B) , n>=2.
n

Greedy Forwarding
Because of failures, network graphs formed by algorithms may change => reconstruct
Use localized algorithms such as Greedy Algorithms that selects the closest node to the sink

Greedy Forwarding
Closest node:

Greedy Forwarding failures

Greedy Forwarding
In addition to location, channel quality is also important
Closest nodes may decrease the number of hops, however, retransmission may be required to deliver messages to those nodes
Distance based
blacklist

Greedy Forwarding
Distance based blacklisting does not always say the channel quality
Reception-based blacklisting
Packet reception rate (PRR) may be used
Best reception neighbor algorithm

Greedy Perimeter State Routing (GPSR)
Uses node locations and packet destinations to make forwarding
Based on greedy forwarding and perimeter forwarding
When greedy forwarding fails, switch to perimeter forwarding

GPSR

Perimeter routing in GPSR
The right-hand rule
When arriving at x from y, the next edge is the next one sequentially counter clockwise about x from edge (y,x)
The right hand rule is used until reaching an edge that crosses sd. At that point we move to the next.

Perimeter routing in GPSR

GPSR

Problem

QoS based routing
Consider other QoS metrics such as delay, throughput
Minimum Cost Path Forwarding

Minimum Cost Path Forwarding

Minimum Cost Path Forwarding