Geographic Routing: Greedy Forwarding and GPSR

The right-hand rule and planar graphs

To get round a void, GPSR uses an old maze-walking rule. "The long-known right-hand rule for traversing a graph" states that when a packet arrives at node x from node y, "the next edge traversed is the next one sequentially counterclockwise about x from edge (x, y)." Applied repeatedly, it walks around the edges of a face, one of the regions into which a drawing of the graph divides the plane, and on the face bordering a void it leads round the void.

The rule works only on a planar graph, one whose edges do not cross; on a radio graph with crossing links it can loop. So GPSR prunes the radio graph to a planar subgraph, using only each node's neighbour list:

• Relative neighbourhood graph (RNG). Edge (u, v) is kept if no other node w is closer to both u and v than they are to each other: d(u, v) is at most max[d(u, w), d(v, w)] for every w. The region that must be empty of a witness w is the lune between the two circles of radius d(u, v).
• Gabriel graph (GG). Edge (u, v) is kept if no other node w lies inside the circle whose diameter is uv: d squared (u, v) < d squared (u, w) + d squared (v, w) for every w.

Neither can disconnect a connected network: an edge is removed only when a witness w within range of both ends offers another way round. Karp and Kung note that the RNG is a subset of the GG, so the GG keeps more links. The program uses the GG.

GPSR: greedy, then perimeter, then greedy

"All data packets are marked initially at their originators as greedy-mode." When greedy forwarding fails at x, "the node marks the packet into perimeter mode", and records in the packet the fields of the paper's Table 1:

• Lp, "Location Packet Entered Perimeter Mode", the point where greedy failed;
• Lf, "Point on xV Packet Entered Current Face" (the text's xV is the line from x to the destination);
• e0, "First Edge Traversed on Current Face".

Entering perimeter mode. "x forwards the packet to the first edge counterclockwise about x from the line xD." Thereafter each node forwards by the right-hand rule around that face.

Changing face. At each hop, a node checks whether the edge to its chosen next hop crosses the line from Lp to D at a point y closer to D than Lf. If so, the packet has reached the far side of this face: Lf becomes y, and "The node forwards the packet along the first edge of this next face", "the next edge counterclockwise about itself" from the one that crossed, recording it as the new e0. "This process repeats at successively closer faces to D."

Returning to greedy. A packet goes back to greedy mode at the first node whose distance to D is less than the distance from Lp to D. Perimeter forwarding is only a detour round the obstacle.

An unreachable destination. If D is not connected to the network, the packet ends on a face that does not contain it and tours the whole face; when it is about to traverse e0 a second time, the destination is declared unreachable and the packet dropped.

Figure 61.1 One of the program's routes: greedy until the shore, then perimeter mode round the lake

Greedy and GPSR, counted

The program places 300 nodes at random over 200 m by 200 m, none inside a lake of radius 50 m at the centre, and implements both methods as the paper describes them: greedy forwarding on the full radio graph, and GPSR with the Gabriel graph, the right-hand rule, face changes on the line from Lp to D, the return to greedy mode, and the e0 test. For 400 random pairs of connected nodes, at radio ranges of 25 m and 20 m, it records how often greedy forwarding alone delivers, how often GPSR delivers, how many deliveries needed perimeter mode, and how long GPSR's paths are compared with the shortest path in hops.

# Greedy forwarding and GPSR (Karp and Kung 2000) on a field with a void: 300
# nodes at random over 200 m by 200 m, none inside a lake of radius 50 m at the
# centre, radio range 25 m. Greedy uses the full graph; perimeter mode uses its
# Gabriel graph and the right-hand rule, with the packet fields Lp, Lf and e0.
import math
import random
from collections import deque

rnd = random.Random(61)
N, SIDE, LAKE = 300, 200.0, 50.0
pts = []
while len(pts) < N:
    p = (rnd.uniform(0, SIDE), rnd.uniform(0, SIDE))
    if math.dist(p, (SIDE / 2, SIDE / 2)) > LAKE:
        pts.append(p)

def radio_graph(reach):
    return [[j for j in range(N) if j != i and math.dist(pts[i], pts[j]) <= reach]
            for i in range(N)]

def gabriel(u):
    """Keep edge (u, v) only if no neighbour w lies inside the circle on uv."""
    keep = []
    for v in nbr[u]:
        m = ((pts[u][0] + pts[v][0]) / 2, (pts[u][1] + pts[v][1]) / 2)
        if all(math.dist(m, pts[w]) >= math.dist(pts[u], m) for w in nbr[u] if w != v):
            keep.append(v)
    return keep

def angle(a, b):
    return math.atan2(pts[b][1] - pts[a][1], pts[b][0] - pts[a][0])

def ccw_from(u, ref):
    """The planar neighbour first counterclockwise about u from direction ref."""
    return min(planar[u], key=lambda v: (angle(u, v) - ref) % (2 * math.pi) or 2 * math.pi)

def crossing(a, b, c, d):
    """Where segment ab crosses segment cd, or None."""
    (x1, y1), (x2, y2), (x3, y3), (x4, y4) = a, b, c, d
    den = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
    if abs(den) < 1e-12:
        return None
    t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / den
    s = ((x1 - x3) * (y1 - y2) - (y1 - y3) * (x1 - x2)) / den
    return (x1 + t * (x2 - x1), y1 + t * (y2 - y1)) if 0 < t < 1 and 0 < s < 1 else None

def route(src, dst, gpsr=True, limit=4 * N):
    D, u, prev, path = pts[dst], src, None, [src]
    mode, Lp, Lf, e0, perimeter_hops = "greedy", None, None, None, 0
    while u != dst and len(path) < limit:
        if mode == "perimeter" and math.dist(pts[u], D) < math.dist(Lp, D):
            mode = "greedy"                       # closer than where greedy failed
        if mode == "greedy":
            best = min(nbr[u], key=lambda v: math.dist(pts[v], D))
            if math.dist(pts[best], D) < math.dist(pts[u], D):
                prev, u = u, best
                path.append(u)
                continue
            if not gpsr or not planar[u]:
                return None, path, perimeter_hops     # a local maximum: greedy is stuck
            mode, Lp, Lf = "perimeter", pts[u], pts[u]
            nxt = ccw_from(u, math.atan2(D[1] - pts[u][1], D[0] - pts[u][0]))
            e0 = (u, nxt)
        else:
            nxt = ccw_from(u, angle(u, prev))         # the right-hand rule
            changed = False
            for _ in range(len(planar[u])):           # change face where Lp-D is crossed
                y = crossing(pts[u], pts[nxt], Lp, D)
                if y is None or math.dist(y, D) >= math.dist(Lf, D):
                    break
                Lf, changed = y, True
                nxt = ccw_from(u, angle(u, nxt))      # first edge of the next face
            if changed:
                e0 = (u, nxt)
            elif (u, nxt) == e0:
                return None, path, perimeter_hops     # toured the whole face: unreachable
        prev, u = u, nxt
        path.append(u)
        perimeter_hops += 1
    return (u == dst), path, perimeter_hops

def hops(src, dst):
    seen, q = {src: 0}, deque([src])
    while q:
        a = q.popleft()
        for b in nbr[a]:
            if b not in seen:
                seen[b] = seen[a] + 1
                q.append(b)
    return seen.get(dst)

print("range  pairs  greedy alone  GPSR    needed perimeter  path / shortest")
for RANGE in (25.0, 20.0):
    nbr = radio_graph(RANGE)
    planar = [gabriel(u) for u in range(N)]
    tried = greedy_ok = gpsr_ok = needed = 0
    stretch = []
    for _ in range(400):
        s, d = rnd.sample(range(N), 2)
        best = hops(s, d)
        if best is None:
            continue                              # not connected at all: skip
        tried += 1
        g, _, _ = route(s, d, gpsr=False)
        ok, path, per = route(s, d)
        greedy_ok += bool(g)
        if ok:
            gpsr_ok += 1
            needed += per > 0
            stretch.append((len(path) - 1) / best)
    print("%3.0f m %6d %11.1f%% %6.1f%% %10d %13.2f (worst %.2f)"
          % (RANGE, tried, 100 * greedy_ok / tried, 100 * gpsr_ok / tried, needed,
             sum(stretch) / len(stretch), max(stretch)))

Reading it: greedy alone. With a 25 m range, greedy forwarding delivers 94.5 per cent of packets; the rest stop at a local maximum on the lake's shore. With 20 m, the network is sparser, small voids appear everywhere, and greedy delivers only 76.8 per cent.

Reading it: GPSR. GPSR delivers every one of the 400 connected pairs at both densities, as the paper promises for a connected planar graph: perimeter mode always finds a way round. In the dense field it needed perimeter mode for 22 packets and its paths averaged only 1.04 times the shortest; in the sparse field it needed it for 93, and paths averaged 1.69 times the shortest, one of them almost 30 times. Perimeter mode guarantees delivery, not a short path: a packet that must follow the outside of the network, the exterior face, can wander a long way.

GEAR: energy and regions

Many sensor queries name a region ("what is the average temperature in a region R"), not a node. GEAR, from UCLA and USC, adds two things to geographic forwarding.

Energy-aware neighbour selection. Each node keeps a learned cost h(N, R) of reaching region R, and, where it has none for a neighbour, uses an estimated cost (the paper's equation 1):

c(N, R) = α d(N, R) + (1 - α) e(N),

where α is a tunable weight, d(N, R) the neighbour's distance to the region's centroid normalised by the largest such distance among the node's neighbours, and e(N) its consumed energy, normalised likewise. With equal energy everywhere, "this degenerates to the classical greedy geographic forwarding"; with equal distances, it spreads load towards the neighbours that have used the least energy. After choosing a next hop, a node updates its own learned cost to the chosen neighbour's plus the cost of the hop, and these learned costs, propagated back, teach nodes to route round holes.

Inside the region. Once a packet reaches the target region, GEAR uses recursive geographic forwarding, splitting the region into sub-regions and sending a copy towards the centre of each, recursively, "or Restricted Flooding algorithm to disseminate the packet inside the destination region" where the region is too sparse for recursion to terminate. Its authors found that, "especially for non-uniform traffic distribution, GEAR exhibits noticeably longer network lifetime than non-energy-aware geographic routing algorithms."

Distinctions

What it does not mean

Geographic routing does not need GPS on every node. It needs positions, which may come from localisation with a few anchors ([Time Synchronisation and Localisation]).

Stateless does not mean no state at all. Each node keeps its neighbours' positions; the paper's footnote says the word refers to "this small, purely local state".

Perimeter mode is not shortest-path routing. It finds a way round, not the shortest way; in the sparse field one path was almost 30 times the shortest.

Planarising does not change the radio. Nodes still hear all their neighbours and greedy mode uses them all; the planar subgraph is used only in perimeter mode.

Quick revision

• Greedy forwarding: send to the neighbour closest to D, if closer than self; only neighbours' positions needed; scales well.
• Fails at a local maximum at the edge of a void.
• Right-hand rule: next edge = first counterclockwise about x from the edge the packet came in on; walks round a face; needs a planar graph.
• RNG: no witness in the lune; GG: no witness in the circle on uv; RNG is a subset of the GG; neither disconnects the graph.
• GPSR: greedy on the full graph; at a local maximum, perimeter mode on the planar graph: first edge counterclockwise from the line xD, then the right-hand rule; change face where the edge crosses Lp-D closer than Lf; back to greedy when closer to D than Lp; e0 again: unreachable.
• Program (300 nodes, lake of 50 m): 25 m range, greedy 94.5 per cent, GPSR 100 per cent, paths 1.04 times the shortest; 20 m, greedy 76.8, GPSR 100, paths 1.69 times (worst about 30).
• GEAR: estimated cost c = α d + (1 - α) e, learned costs round holes; recursive geographic forwarding or restricted flooding inside the region.

Test yourself

1. Explain greedy geographic forwarding and when it fails. Each node knows its neighbours' positions, and each packet carries the destination's position. A node forwards the packet to the neighbour geographically closest to the destination, provided that neighbour is closer to it than the node itself. It fails at a local maximum: a node that is closer to the destination than all of its neighbours, typically at the edge of a void, a region with no nodes, even though a path around the void may exist.

2. What is the right-hand rule, and why must the graph be planar? When a packet arrives at node x from node y, it is sent on the next edge counterclockwise about x from edge (x, y). Repeated, this traverses the boundary of a face of the graph, which lets the packet walk round a void. The rule traverses faces correctly only if no edges cross; on a graph with crossing edges it can loop, so GPSR first reduces the radio graph to a planar subgraph.

3. How are the RNG and the Gabriel graph built, and why do they not disconnect the network? In the relative neighbourhood graph, an edge (u, v) is kept only if no other node w is closer to both u and v than they are to each other, that is, no witness lies in the lune between them. In the Gabriel graph, an edge is kept only if no other node lies inside the circle having uv as its diameter. An edge is removed only when such a witness exists within range of both u and v, which provides an alternative path, so a connected network stays connected.

4. Describe GPSR's perimeter mode, including the fields Lp, Lf and e0. When greedy forwarding fails at x, the packet enters perimeter mode and records Lp, the location where it did so. x sends it on the first edge counterclockwise from the line x to D, and subsequent nodes forward by the right-hand rule on the planar graph. When an edge about to be used crosses the line from Lp to D at a point closer to D than Lf, the point where the packet entered its current face, Lf is updated and the packet moves onto the next face, recording that face's first edge as e0. As soon as a node closer to D than Lp is reached, the packet returns to greedy mode. If the packet is about to traverse e0 again, it has toured a whole face without progress, and D is unreachable.

5. In the program, what did GPSR gain over greedy forwarding, and at what cost? Greedy forwarding alone delivered 94.5 per cent of packets with a 25 m range and 76.8 per cent with 20 m; GPSR delivered all of them at both densities. The cost was longer paths: 1.04 times the shortest on average in the dense field, 1.69 times in the sparse one, and once almost 30 times.

6. How does GEAR differ from GPSR? GEAR routes towards a region rather than a point, and chooses its next hop by an estimated cost that weighs the neighbour's distance to the region's centroid against the energy it has already consumed, with a tunable weight α, so as to spread the load; learned costs updated from each choice let it route round holes. Inside the target region it disseminates the packet by recursive geographic forwarding, or by restricted flooding where the region is sparse.