PEGASIS, TEEN and the Other Hierarchical Protocols

Building the chain. The shortest chain through all the nodes is a travelling salesman problem, "which is known to be intractable", but "a simple chain built with a greedy approach performs quite well." "To construct the chain, we start with the furthest node from the BS", so that the far nodes get close neighbours, and each step adds the nearest node not yet on the chain. "When a node dies, the chain is reconstructed in the same manner to bypass the dead node."

A round. "each node receives data from one neighbor, fuses with its own data, and transmits to the other neighbor on the chain." Leadership rotates: "we will use node number i mod N (N represents the number of nodes) to transmit to the BS in round i", so the leader sits at a random place on the chain, and nodes die at random places. The leader starts the round with a small token passed to one end of the chain; data flows from that end to the leader; then the token goes to the other end and its data flows back. Every node except the two ends fuses, so "each node will receive and transmit one packet in each round and be the leader once every 100 rounds."

What it saves over LEACH. The paper lists three savings: members send to a close chain neighbour rather than to a cluster head; the leader receives at most two messages instead of a cluster's twenty; and "only one node transmits to the BS in each round". There is also no cluster formation to pay for each round.

Figure 60.1 The first program's field joined by PEGASIS's greedy chain, with one round's leader

PEGASIS against LEACH, counted

The first program uses the set-up of [LEACH: Clusters That Take Turns]: 100 nodes at random in a 50 m by 50 m field, the base station 100 m below it, 0.5 J per node, 2,000-bit messages, the first order radio model, and 5 nJ/bit to fuse each message received. It runs direct transmission, LEACH with P = 0.05, and PEGASIS with a greedy chain rebuilt whenever a node dies, and records the round by which 1, 20, 50 and 100 per cent of the nodes have died, the measures of the PEGASIS paper.

# PEGASIS against LEACH and direct transmission, on the set-up of the LEACH
# chapter: 100 nodes at random in 50 m by 50 m, the base station 100 m below
# the field, 0.5 J per node, 2,000-bit messages, 50 nJ/bit and 100 pJ/bit/m2,
# and 5 nJ/bit to fuse each message received. PEGASIS builds a greedy chain
# from the node farthest from the base station; each node sends to its chain
# neighbour towards the round's leader, fusing what it received with its own
# reading; the leader (node i mod N in round i) sends one message to the base.
import random

E_ELEC, E_AMP, E_FUSE, K = 50e-9, 100e-12, 5e-9, 2000
BS, START, P = (0.0, -100.0), 0.5, 0.05

def d2(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

def tx(a, b):
    return E_ELEC * K + E_AMP * K * d2(a, b)

RX = E_ELEC * K + E_FUSE * K            # receive one message and fuse it

def greedy_chain(nodes, alive):
    left = set(alive)
    chain = [max(left, key=lambda n: d2(nodes[n], BS))]
    left.discard(chain[0])
    while left:
        nxt = min(left, key=lambda n: d2(nodes[n], nodes[chain[-1]]))
        chain.append(nxt)
        left.discard(nxt)
    return chain

def round_pegasis(nodes, alive, r, chain):
    use = dict.fromkeys(alive, 0.0)
    order = sorted(alive)
    leader = chain.index(order[r % len(order)])
    for p, n in enumerate(chain):
        if p < leader:
            use[n] += tx(nodes[n], nodes[chain[p + 1]]) + (RX if p > 0 else 0)
        elif p > leader:
            use[n] += tx(nodes[n], nodes[chain[p - 1]]) + (RX if p < len(chain) - 1 else 0)
        else:
            use[n] += tx(nodes[n], BS) + RX * ((p > 0) + (p < len(chain) - 1))
    return use

def round_leach(nodes, alive, r, last_head, rnd):
    epoch = round(1 / P)
    heads = {n for n in alive if last_head[n] < r - r % epoch
             and rnd.random() < P / (1 - P * (r % epoch))}
    for h in heads:
        last_head[h] = r
    use = dict.fromkeys(alive, 0.0)
    for n in alive:
        if n in heads:
            use[n] += E_FUSE * K + tx(nodes[n], BS)
        elif heads:
            h = min(heads, key=lambda h: d2(nodes[n], nodes[h]))
            use[n] += tx(nodes[n], nodes[h])
            use[h] += RX
        else:
            use[n] += tx(nodes[n], BS)
    return use

def run(nodes, protocol, rnd):
    energy, alive = [START] * len(nodes), set(range(len(nodes)))
    last_head, chain = [-100] * len(nodes), None
    marks, r = {}, 0
    while alive:
        if protocol == "PEGASIS":
            chain = chain or greedy_chain(nodes, alive)
            use = round_pegasis(nodes, alive, r, chain)
        elif protocol == "LEACH":
            use = round_leach(nodes, alive, r, last_head, rnd)
        else:
            use = {n: tx(nodes[n], BS) for n in alive}
        for n, e in use.items():
            energy[n] -= e
        dead = {n for n in alive if energy[n] <= 0}
        if dead:
            alive -= dead
            chain = None                         # rebuild the chain round the dead
        r += 1
        gone = len(nodes) - len(alive)
        for pct in (1, 20, 50, 100):
            if gone >= pct and pct not in marks:
                marks[pct] = r
    return [marks[p] for p in (1, 20, 50, 100)]

rnd = random.Random(60)
nodes = [(rnd.uniform(-25, 25), rnd.uniform(0, 50)) for _ in range(100)]
print("rounds until this share of nodes has died:   1%    20%    50%   100%")
for name in ("direct", "LEACH", "PEGASIS"):
    print("%-40s %6d %6d %6d %6d" % (name, *run(nodes, name, rnd)))

Reading it. From 20 per cent of nodes dead onwards, PEGASIS lasts about 1.7 to 1.8 times as long as LEACH (1,934 rounds against 1,088 at 20 per cent, 2,184 against 1,266 at 100), close to the paper's "approximately 2x the number of rounds compared to LEACH" for a 50 m by 50 m field. Its first death comes only a little later than LEACH's, because the greedy chain leaves a few nodes with a distant neighbour, and such a node pays heavily every round. The paper met this directly: "We improved the performance of PEGASIS by not allowing such nodes to become leaders", by a threshold on the distance to their chain neighbours, a refinement this program leaves out.

PEGASIS's limits

The survey collects them. Nodes must know the positions of all others to build the chain, and must be able to reach the base station directly. "PEGASIS introduces excessive delay for distant node on the chain": data from one end must pass through every node before it. "In addition, the single leader can become a bottleneck." And like LEACH it assumes equal starting energy.

Hierarchical-PEGASIS attacks the delay: with CDMA-capable nodes, the chain is arranged as a tree-like hierarchy, and only spatially separated nodes transmit at the same time, so data moves in parallel; the survey reports that it performs better "than the regular PEGASIS scheme by a factor of about 60".

TEEN: report only what matters

"In this scheme, at every cluster change time, in addition to the attributes, the cluster-head broadcasts to its members":

• Hard Threshold (HT): "This is a threshold value for the sensed attribute. It is the absolute value of the attribute beyond which, the node sensing this value must switch on its transmitter and report to its cluster head."
• Soft Threshold (ST): "This is a small change in the value of the sensed attribute which triggers the node to switch on its transmitter and transmit."

"The nodes sense their environment continuously. The first time a parameter from the attribute set reaches its hard threshold value, the node switches on its transmitter and sends the sensed data." The node stores that value as its sensed value (SV), and thereafter transmits in the current cluster period only when both conditions hold: "The current value of the sensed attribute is greater than the hard threshold" and "The current value of the sensed attribute differs from SV by an amount equal to or greater than the soft threshold." Each transmission updates SV.

The two thresholds divide the work: "the hard threshold tries to reduce the number of transmissions by allowing the nodes to transmit only when the sensed attribute is in the range of interest", and "The soft threshold further reduces the number of transmissions" when the value hardly changes. The user can move both at each cluster change, and "A smaller value of the soft threshold gives a more accurate picture of the network, at the expense of increased energy consumption." Sensing continuously costs little; "Message transmission consumes much more energy than data sensing."

TEEN's drawback. "if the thresholds are not reached, the nodes will never communicate": the user cannot tell a quiet network from a dead one.

APTEEN (Adaptive Periodic TEEN) keeps the thresholds and adds, in the survey's words, a count time (CT): "the maximum time period between two successive reports sent by a node". "If a node does not send data for a time period equal to the count time, it is forced to sense and retransmit the data." It "combines both proactive and reactive policies", at the cost of more complexity; in the survey's summary, APTEEN's energy and lifetime lie between LEACH's and TEEN's.

TEEN's thresholds, counted

The second program gives one node a day of temperature readings, one a minute, from an illustrative trace swinging about 85 F with a little noise. The thresholds are TEEN's own experiment's: "The hard threshold is set at the average value of the lowest and the highest possible temperatures, 100 F", and "The soft threshold is set at 2 F". It counts the reports sent by a proactive node, by TEEN with the hard threshold only, by TEEN with both thresholds, and by APTEEN with a count time of 60 minutes, and the worst error the user sees while the temperature is at or above HT.

# TEEN's thresholds on one node's day of temperature readings, one a minute.
# The trace is illustrative: a daily swing about 85 F with a little noise. The
# thresholds are the TEEN paper's own: a hard threshold of 100 F and a soft
# threshold of 2 F. A proactive node reports every minute; TEEN reports the
# first time the reading reaches HT, then only while it stays at or above HT
# and has changed by ST or more since the last report (the stored value SV).
import math
import random

rnd = random.Random(60)
HT, ST, MINUTES = 100.0, 2.0, 24 * 60
noise, trace = 0.0, []
for m in range(MINUTES):
    noise = 0.9 * noise + rnd.gauss(0, 0.4)
    trace.append(85 + 18 * math.sin(2 * math.pi * (m - 6 * 60) / MINUTES) + noise)

def teen(soft, count_time=None):
    """Reports and the worst error the user sees while the reading is at or
    above HT. count_time (APTEEN) forces a report after that many minutes."""
    sent, sv, since, worst = 0, None, 0, 0.0
    for t in trace:
        since += 1
        due = t >= HT and (sv is None or not soft or abs(t - sv) >= ST)
        if count_time and since >= count_time:
            due = True
        if due:
            sent, sv, since = sent + 1, t, 0
        if t >= HT and sv is not None:
            worst = max(worst, abs(t - sv))
    return sent, worst

hot = sum(1 for t in trace if t >= HT)
print("readings: %d; at or above %.0f F: %d minutes, peak %.1f F" % (MINUTES, HT, hot, max(trace)))
print("proactive, every minute       %4d reports" % MINUTES)
for name, soft, ct in (("TEEN, hard threshold only", False, None),
                       ("TEEN, hard and soft", True, None),
                       ("APTEEN, count time 60 min", True, 60)):
    sent, worst = teen(soft, ct)
    print("%-29s %4d reports; worst error above HT %.2f F" % (name, sent, worst))

readings: 1440; at or above 100 F: 278 minutes, peak 104.8 F
proactive, every minute       1440 reports
TEEN, hard threshold only      278 reports; worst error above HT 0.00 F
TEEN, hard and soft              5 reports; worst error above HT 1.99 F
APTEEN, count time 60 min       26 reports; worst error above HT 1.97 F

Figure 60.2 The second program's day of readings, the hard threshold, and TEEN's five reports

Reading it. The temperature is at or above 100 F for 278 of the day's 1,440 minutes. A proactive node reports 1,440 times. The hard threshold alone cuts this to 278, one a minute while it is hot, and the user always knows the exact value. Adding the 2 F soft threshold cuts it to 5 reports, and the value the user holds is never more than 1.99 F out: the soft threshold is exactly the accuracy the user chose to give up. For the other 1,162 minutes TEEN says nothing at all, which is its drawback; APTEEN's count time of an hour adds a report at least every 60 minutes, 26 in all, so that silence can be told from failure.

Distinctions

What it does not mean

PEGASIS is not multi-hop to the base station. Data travels along the chain, but the leader still reaches the base station in one hop.

A chain is not a shortest route. The greedy chain is not the shortest possible, and a few nodes end up with distant neighbours.

TEEN does not sense less. Its nodes sense all the time; it is transmissions that the thresholds remove.

A soft threshold is not an error. It is a chosen resolution: the user asks to hear only changes of at least ST.

Quick revision

• PEGASIS (Lindsey and Raghavendra, 2002): one greedy chain from the node farthest from the base station; each node receives from one neighbour, fuses, passes on; leader node i mod N sends to the base station; token passing; chain rebuilt when a node dies.
• Saves: short sends, at most two receptions for the leader, one transmission to the base station, no cluster formation. About 2 times LEACH's lifetime (paper); program about 1.8 times from 20 per cent dead. Limits: delay, bottleneck leader, needs positions and one-hop reach. Hierarchical-PEGASIS: parallel transmissions in a tree of chains.
• TEEN (Manjeshwar and Agrawal, 2001): reactive, cluster-based. Hard threshold (report at or beyond it), soft threshold (report again only after this much change), stored SV. Paper's values: HT 100 F, ST 2 F. Drawback: silent if thresholds are never reached.
• APTEEN: adds count time (longest gap between reports): proactive and reactive combined.
• Program (one day, one node): proactive 1,440 reports; hard only 278; hard and soft 5 (error at most 1.99 F); APTEEN 26.

Test yourself

1. How does PEGASIS form its chain and gather data? Using global knowledge of node positions, the chain is built greedily: it starts at the node farthest from the base station and repeatedly adds the nearest node not yet on the chain, so far nodes get close neighbours. In each round, a token from the leader starts data at one end; each node receives its neighbour's data, fuses it with its own, and passes it towards the leader; the same happens from the other end; the leader fuses both and sends one message to the base station. The leader is node i mod N in round i, so the role rotates.

2. Why does PEGASIS outperform LEACH? Each node transmits only to a close chain neighbour instead of a possibly distant cluster head, the leader receives at most two messages instead of a whole cluster's, only one node transmits to the distant base station per round instead of several heads, and there is no cluster formation each round. The paper reports about twice LEACH's lifetime for a 50 m by 50 m network.

3. What are the disadvantages of PEGASIS? Data from the far end of the chain must pass through many nodes, causing long delays; the single leader can become a bottleneck; nodes need the positions of all others to build the chain and must be able to reach the base station directly; and nodes with distant chain neighbours spend much more energy than the rest.

4. Explain the hard and soft thresholds of TEEN. At each cluster change the head broadcasts a hard threshold, an absolute value of the sensed attribute, and a soft threshold, a small change in it. A node senses continuously; the first time the value reaches the hard threshold it transmits and stores the value as SV. After that it transmits only if the value is still beyond the hard threshold and differs from SV by at least the soft threshold, and each transmission updates SV. The hard threshold confines reports to values of interest; the soft threshold suppresses reports when the value barely changes.

5. What is the main drawback of TEEN, and how does APTEEN address it? If the thresholds are never reached, nodes never transmit, so the user receives no data and cannot tell a quiet network from a failed one; TEEN also cannot give periodic reports. APTEEN adds a count time, the longest period a node may go without reporting, after which it is forced to sense and transmit, so the network gives periodic snapshots as well as immediate reports of threshold crossings.

6. In the program, how many reports did each scheme send in a day, and what did the soft threshold cost? A proactive node sent 1,440 reports, TEEN with the hard threshold only 278, TEEN with hard and soft thresholds 5, and APTEEN with a 60-minute count time 26. The soft threshold of 2 F meant that while the temperature was above 100 F the value the user held was at most 1.99 F away from the true one.