Energy-aware Routing

Toh's four metrics

1. Minimum Total Transmission Power Routing (MTPR). Each link's cost is the transmission power needed to reach the next node with an acceptable signal-to-noise ratio, which grows with distance (Toh uses a 1 / d to the power n roll-off, with n = 2 for short and n = 4 for longer distances). The route with the smallest total is found by an ordinary shortest-path algorithm such as Dijkstra's or Bellman-Ford. Because power grows faster than distance, MTPR tends to choose many short hops, which add delay and instability; adding each receiver's power to the cost, as one refinement does, pulls it back towards fewer hops.

2. Minimum Battery Cost Routing (MBCR). Let c be a node's remaining battery capacity, from 0 to 100. Its cost is f(c) = 1 / c, so "The less capacity it has, the more reluctant it is". A route's cost is the sum of its nodes' costs, and the cheapest route is chosen. The flaw: "because only the summation of values of battery cost functions is considered, a route containing nodes with little remaining battery capacity may still be selected".

3. Min-Max Battery Cost Routing (MMBCR). A route's cost is the largest f(c) among its nodes, that is, the cost of its weakest node, and the route whose weakest node is strongest is chosen. Batteries are used "more fairly", but "since there is no guarantee that minimum total transmission power paths will be selected under all circumstances, it can consume more power".

4. Conditional Max-Min Battery Capacity Routing (CMMBCR). Toh's own proposal, with a threshold γ between 0 and 100. "The basic idea behind CMMBCR is that when all nodes in some possible routes between a source and a destination have sufficient remaining battery capacity (i.e., above a threshold), a route with minimum total transmission power among these routes is chosen." When every route contains a node below γ, it chooses the route with the largest minimum capacity, as MMBCR would. With γ = 0 it is MTPR; with γ = 100 it is MMBCR. γ is "a protection margin".

Worked example: two routes, four metrics

A source has two routes to the sink. Route 1 has 2 relays, with 90 and 10 per cent of their batteries left; route 2 has 4 relays, each with 30 per cent. Route 1, with fewer hops, needs less total transmission power.

Figure 40.1 The worked example: MBCR takes the short route through the weak relay, MMBCR the long one

MBCR still sends traffic through the relay with 10 per cent left, because the other relay's 90 per cent keeps the sum low: exactly the flaw Toh describes. MMBCR protects it. CMMBCR protects it only when it is actually in danger (below γ), and otherwise takes the cheaper route.

The four policies, run to the first death

The program places a sink and 12 nodes on a grid (columns at 20, 40, 60 and 80 m from the sink, rows at 20, 50 and 80 m), with a radio range of 40 m. Every round, every node sends one 2,000-bit packet to the sink along the route its policy chooses. Energy follows the first-order radio model of the LEACH papers: 50 nJ per bit for the electronics and 100 pJ per bit per square metre for the amplifier, with 0.5 J in each battery. The run stops when the first node dies.

# Four ways to choose routes, on one network, until the first node dies.
# Radio model: the first-order model of the LEACH papers (50 nJ/bit for the
# electronics, 100 pJ/bit/m^2 for the amplifier), 2,000-bit packets, 0.5 J each.
import heapq
import math

SINK = (0, 50)
NODES = [(x, y) for x in (20, 40, 60, 80) for y in (20, 50, 80)]
RANGE, BITS, START = 40.0, 2000, 0.5

def tx(d):                                 # joules to send one packet over d metres
    return BITS * (50e-9 + 100e-12 * d * d)

RX = BITS * 50e-9                          # joules to receive one packet

places = [SINK] + NODES                    # index 0 is the sink
links = {i: [j for j in range(len(places)) if j != i
             and math.dist(places[i], places[j]) <= RANGE] for i in range(len(places))}

def link_energy(i, j):                     # sending i to j, plus j receiving
    return tx(math.dist(places[i], places[j])) + (RX if j else 0)

def route(src, energy, policy, gamma=0.25):
    """The route from src to the sink (index 0) that a policy chooses."""
    if policy == "fewest hops":
        return dijkstra(src, energy, lambda i, j: 1)
    if policy == "least energy":           # MTPR
        return dijkstra(src, energy, link_energy)
    if policy == "strongest weakest":      # MMBCR
        return widest(src, energy)
    healthy = dijkstra(src, energy, link_energy,
                       allowed=lambda n: energy[n] >= gamma * START)
    return healthy or widest(src, energy)  # CMMBCR, threshold gamma

def dijkstra(src, energy, w, allowed=lambda n: True):
    best, heap = {src: 0.0}, [(0.0, src, [src])]
    while heap:
        c, n, path = heapq.heappop(heap)
        if n == 0:
            return path
        if c > best.get(n, math.inf):
            continue
        for m in links[n]:
            if m and (energy[m] <= 0 or not allowed(m)):
                continue
            nc = c + w(n, m)
            if nc < best.get(m, math.inf):
                best[m] = nc
                heapq.heappush(heap, (nc, m, path + [m]))
    return None

def widest(src, energy):
    """The route whose weakest relay has the most energy left."""
    best, heap = {src: math.inf}, [(-math.inf, src, [src])]
    while heap:
        neg, n, path = heapq.heappop(heap)
        if n == 0:
            return path
        for m in links[n]:
            if m and energy[m] <= 0:
                continue
            width = min(-neg, energy[m] if m else math.inf)
            if width > best.get(m, -1):
                best[m] = width
                heapq.heappush(heap, (-width, m, path + [m]))
    return None

for policy in ("fewest hops", "least energy", "strongest weakest", "conditional"):
    energy = [math.inf] + [START] * len(NODES)
    rounds, used = 0, 0.0
    while all(e > 0 for e in energy[1:]):
        for src in range(1, len(places)):    # every node reports once a round
            path = route(src, energy, policy)
            for a, b in zip(path, path[1:]):
                energy[a] -= tx(math.dist(places[a], places[b]))
                used += link_energy(a, b)
                if b:
                    energy[b] -= RX
        rounds += 1
    dead = [NODES[i - 1] for i in range(1, len(places)) if energy[i] <= 0]
    left = sum(energy[1:]) / (START * len(NODES))
    print("%-18s %.2f mJ a round; first death after %3d rounds, at %s; %2.0f%% unused"
          % (policy, 1000 * used / rounds, rounds, dead[0], 100 * left))

fewest hops        8.32 mJ a round; first death after 288 rounds, at (20, 20); 60% unused
least energy       8.32 mJ a round; first death after 142 rounds, at (40, 50); 80% unused
strongest weakest  10.46 mJ a round; first death after 447 rounds, at (20, 20); 22% unused
conditional        8.67 mJ a round; first death after 404 rounds, at (40, 50); 42% unused

Reading it.

1. The same energy, twice the lifetime difference. Fewest hops and least energy spend exactly the same energy per round, 8.32 mJ, yet the first node dies after 288 rounds in one case and after 142 in the other. The total is the same; where it is spent is not. Under least energy, the central node at (40, 50) spent its battery fastest and died after 142 rounds, about half as long.
2. The energy hole. When the first node dies under least energy, 80 per cent of the network's energy is still unused; under fewest hops, 60 per cent. The network is broken, or about to be, while most of its batteries are full. That is the cascade the LEACH authors describe, caught at its first step.
3. Sparing the weakest. "Strongest weakest" (MMBCR) spends more per round, 10.46 mJ, because it takes longer routes to avoid tired nodes, and yet lasts 447 rounds, and uses the batteries far more evenly: only 22 per cent is left when the first node dies. It is the most "fair", as Toh says, and here also the longest-lived.
4. The compromise. The conditional policy (CMMBCR with γ at 25 per cent) spends almost as little as least energy, 8.67 mJ, while the nodes are healthy, and switches to protecting the weak when they are not: 404 rounds.

A different network or radio model would change the numbers, and in a network where one node is the only way to the sink no metric can save it. What the run shows reliably is the shape: minimising energy per packet and maximising lifetime are different goals, and the metrics that watch the batteries serve the second.

The energy hole, and what else is done about it

Near the sink, every packet converges on the same few nodes: in a network where all traffic flows to one sink, the nodes one hop away relay everyone's data. Energy-aware routing spreads the load among them, but cannot abolish the funnel. Two other remedies appear in the sources held for this book:

• Rotating the heavy role. LEACH rotates the cluster-head role among nodes at random, which its authors describe as achieving "the same goal" as power-aware routing ([LEACH: Clusters That Take Turns]).
• Sending less. Aggregating data on the way to the sink cuts what the last hops must carry ([Design Principles: Distributed Organisation and In-network Processing]).

Distinctions

What it does not mean

Energy-aware does not mean shortest. The routes energy-aware metrics choose are often longer, deliberately.

Least energy per packet does not mean longest life. In the run above it gave the shortest lifetime of the four.

A network with energy left is not necessarily alive. When the nodes around the sink die, the rest cannot reach it, however full their batteries.

Battery-aware routing is not free. Nodes must learn their neighbours' remaining energy, which costs messages, and the extra route length costs energy every packet.

Quick revision

• Energy hole / hot spot: nodes near the sink relay everyone's traffic and die first, in a cascade (LEACH on MTE), leaving most energy unused.
• Goals: minimum energy per packet against maximum network lifetime (first death, partition).
• MTPR: minimise total transmission power; Dijkstra or Bellman-Ford; many short hops; overuses some nodes.
• MBCR: minimise the sum of f(c) = 1 / c; can still choose a nearly empty node.
• MMBCR: minimise the largest 1 / c (strongest weakest node); fair, may cost more power.
• CMMBCR: threshold γ; MTPR among routes whose nodes are all above γ, otherwise MMBCR; γ = 0 is MTPR, γ = 100 is MMBCR.
• Worked example: MBCR picks the route through the relay at 10 per cent (1/9 against 2/15); MMBCR avoids it.
• Our run: fewest hops 288 rounds, least energy 142, MMBCR 447, CMMBCR 404; least energy leaves 80 per cent unused at the first death.

Test yourself

1. What is energy-aware routing? Why is it needed? Routing that uses energy, either the energy a route consumes or the remaining battery of its nodes, as the route selection metric instead of hop count. It is needed because shortest-path routing makes the same nodes, especially those near the sink, relay most of the traffic, so they die early and cut off the network while other nodes still have energy.

2. Explain MTPR, MBCR and MMBCR. MTPR chooses the route with the minimum total transmission power, minimising energy per packet but possibly overusing some nodes. MBCR gives each node a cost that grows as its battery falls, such as 1 / remaining capacity, and chooses the route with the smallest total cost; it can still select a route through a nearly exhausted node if the others are well charged. MMBCR chooses the route whose most expensive node (the one with the least battery) is cheapest, so the weakest node is protected and batteries are used fairly, at the cost of sometimes using more total power.

3. Explain CMMBCR. Conditional max-min battery capacity routing uses a threshold γ. If there are routes in which every node has more than γ battery left, it chooses among them the one with minimum total transmission power. If every route contains a node below γ, it chooses the route whose weakest node has the most battery, as MMBCR does. With γ = 0 it behaves like MTPR and with γ = 100 like MMBCR.

4. What is the energy hole problem? In a network where all data flows to a sink, the nodes nearest the sink relay the traffic of all the others, so they use energy fastest and die first. Their death disconnects the rest of the network, or forces longer, costlier routes that kill more nodes, even though most of the network's energy is still unused.

5. A route has relays with 50 and 25 per cent battery; another has three relays at 40 per cent. Which does MBCR choose, and which MMBCR? MBCR: 1/50 + 1/25 = 3/50 = 0.06 against 3 × 1/40 = 3/40 = 0.075, so the first route. MMBCR: the first route's weakest relay costs 1/25 = 0.04, the second's 1/40 = 0.025, so the second route.