Transport Protocol Design Issues in WSNs

PSFQ was built for the downstream direction, ESRT and CODA for the upstream. A designer must say which problem is being solved before anything else is decided.

2. What does reliability mean here?

The traditional answer is per-packet: deliver every byte. A sensor network can often afford less, and sometimes needs something different.

Event reliability. ESRT's definitions: "The observed event reliability, ri, is the number of received data packets in decision interval i at the sink" and "The desired event reliability, R, is the number of data packets required for reliable event detection. This is determined by the application". The transport problem is then not to save every packet but "to configure the reporting rate, f, of source nodes so as to achieve the required event detection reliability, R, at the sink with minimum resource utilization."

Block reliability. For code and other objects, every fragment matters, and the unit of success is the whole block.

Nothing at all. Where readings are frequent and correlated, an application may want no reliability mechanism, only speed and low cost.

The choice decides everything downstream: with event reliability the protocol can control the rate instead of retransmitting, which is what ESRT does, and which can save energy rather than spend it.

3. How is a loss detected?

Four mechanisms, with different costs:

• Positive acknowledgement (ACK). The receiver confirms each packet; the sender resends when no confirmation comes. Simple and prompt, but one control packet per data packet, and a lost ACK causes a needless resend.
• Negative acknowledgement (NACK). The receiver notices a gap in the sequence numbers and asks for the missing packet. Cheap when losses are rare, but a loss at the end of a burst leaves no later packet to reveal the gap, so a timeout is still needed. PSFQ's note: "For a negative acknowledgement system, at least one message has to be received correctly at the destination after a loss has happened in order to detect the loss."
• Implicit acknowledgement. On a broadcast medium, a sender that hears its neighbour forward the packet knows it arrived. No control packet at all, but the radio must stay on to hear it, and the last hop has no onward transmission to overhear.
• Sequence numbers and timeouts at the receiver, used with any of the above.

Where the loss detection lives matters as much as its kind: a NACK to the source crosses the whole path, a NACK to the previous hop crosses one.

4. Where is a loss repaired?

This is the issue [Why a Sensor Network Cannot Simply Run TCP] sized. RMST puts it as the central decision: "The design decisions examined by this paper for the transport layer are primarily concerned with the balance of hop-by-hop vs. end-to-end functionality. Repair requests could be initiated by sinks (receiver end-points), or by in-network nodes on an established path."

• End to end. Only the source keeps the data; only the destination notices loss. Simple nodes, no caches, but each repair crosses every hop, and the chance of a repair itself getting through falls as (1 - p)^n.
• Hop by hop. Each node caches what it forwards and repairs its own hop, which PSFQ chose because it "essentially segments multihop forwarding operations into a series of single hop transmission processes that eliminate error accumulation."
• How much to cache. RMST makes caching optional: in caching mode every node keeps recent fragments; in non-caching mode "only the sources and sinks maintain a cache". Memory is the price.
• What the MAC already does. MAC retries repair most losses before transport sees them, and RMST found the transport's caching stops paying once the MAC brings losses below 1 per cent.

5. How is congestion noticed?

Congestion in a sensor network is not only a full queue. CODA's setting: "Sensor networks typically operate under light load and then suddenly become active in response to a detected or monitored event", and "The transport of event impulses is likely to lead to varying degrees of congestion in the network depending on the sensing application." The load arrives as a burst, exactly when the data matters most.

Three signals, each considered by CODA:

• Buffer occupancy or queue length, the wired network's choice. CODA found it weak here: "the buffer occupancy does not provide an accurate indication of congestion even when the link ARQ is enabled ... except in the extreme case when the queue is empty or about to overflow", a bimodal signal, "not responsive enough and too coarse to provide smooth and efficient congestion control."
• Channel loading. "In CSMA networks, it is straightforward for sensors to listen to the channel, trace the channel busy time and calculate the local channel loading conditions." It measures what a queue cannot: neighbours competing for the same air. But listening costs energy, so CODA samples rather than listening all the time.
• Rate mismatch, comparing what arrives with what can be forwarded, or, at the sink, comparing the reports received with the reports expected. This is inherently slow: CODA notes that detection based on the reporting rate "is inherently slow and end-to-end in nature".

Note what makes this different from a wired network: congestion is shared, since a node's neighbours use the same channel, so a node can be congested without a single packet in its own queue.

6. How is congestion told, and to whom?

• Explicit against implicit. A backpressure message says so directly; a bit set in a forwarded data packet costs nothing extra but travels only where data travels.
• Hop by hop. CODA's "open-loop hop-by-hop backpressure": "a node broadcasts backpressure messages as long as it detects congestion. Backpressure signals are propagated upstream toward the source. ... Nodes that receive backpressure signals can throttle their sending rates or drop packets based on the local congestion policy". It acts in one hop time, and each node decides whether to pass it on.
• From the sink. CODA's "closed-loop, multi-source regulation" "operates over a slower time scale and is capable of asserting congestion control over multiple sources from a single sink in the event of persistent congestion." Slow, but it can see and settle the whole event.

Both are needed because the hotspots differ: dense sources make "persistent hotspots" near the sources, sparse ones make "transient hotspots potentially anywhere in the sensor field but likely farther from the sources, toward the sink."

7. How is the rate adjusted?

Once congestion is known, something must give: throttle the sending rate, drop packets by a local policy, or have the sink assign each source a new reporting rate. TCP's additive-increase, multiplicative-decrease is one policy among several, and in a sensor network the rate is often the application's reporting rate, so transport and application decide together. That is ESRT's approach: control f, the reporting rate, to reach R with the least resource use, which also saves energy when the network is delivering more than the sink needs.

8 to 11. The constraints over all of it

• Energy. A protocol is judged in transmissions, not only in delivery ratio. CODA measures an "energy tax" against a "fidelity penalty"; ESRT uses congestion control to cut energy as well as loss.
• Memory and state. Caches, sequence-number maps and timers must fit in kilobytes; per-flow state at every node does not scale, which is why sensor protocols are usually stateless or keep only per-hop state.
• Fairness. Sources far from the sink spend more of the network's transmissions per delivered packet than near ones. Equal rates are fair but reduce total throughput; favouring near sources raises throughput and silences the far ones.
• Timeliness and priority. A fire alarm that arrives late is worthless, and a protocol may need to carry some traffic ahead of the rest. PSFQ's own goal, for its direction, is "to provide loose delay bounds for data delivery to all the intended receivers."

The issues, computed

The program computes event reliability from per-packet reliability; counts the transmissions ACK, NACK and implicit acknowledgement each cost over one lossy hop; counts the packets a hotspot drops before hop-by-hop backpressure and before end-to-end regulation reach it; and prices fairness in a field where four of six sources are five hops away.

# The design issues of a sensor transport protocol, put in numbers: what
# reliability means, what loss detection costs, how fast congestion control can
# react, and what fairness costs. All models are ours; the issues are the
# sources'.
from math import comb

# 1. Packet reliability against event reliability (ESRT's notion). n sources
#    each send one report per decision interval; each arrives with probability
#    p; the sink needs R reports to call the event detected.
def at_least(n, p, R):
    return sum(comb(n, k) * p ** k * (1 - p) ** (n - k) for k in range(R, n + 1))

print("Event detected (R of n reports arrive) against per-packet delivery p:")
print("  n   R      p=0.30   p=0.50   p=0.70   p=0.90")
for n, R in ((5, 3), (10, 3), (20, 3), (20, 8), (50, 8)):
    print("  %2d  %2d   " % (n, R) + "".join("%9.4f" % at_least(n, p, R) for p in (0.3, 0.5, 0.7, 0.9)))

# 2. What loss detection costs, in transmissions, to get 100 packets across one
#    hop that loses a fraction q. Every scheme resends the lost data; they
#    differ in the control traffic. ACK: one acknowledgement per arrival, and an
#    ACK may itself be lost. NACK: one per loss noticed, but a loss at the end
#    of a run is found only by a timeout. Implicit ACK: the forwarder's own
#    transmission onward is the acknowledgement, so no control packet at all,
#    but the sender must stay awake to hear it.
print("\nTransmissions to deliver 100 packets over one hop (data + control):")
print("  loss q       ACK: data + ACKs      NACK: data + NACKs   implicit: data")
for q in (0.0, 0.01, 0.05, 0.10, 0.20):
    # ACK: a packet is confirmed only if the data and its ACK both get through,
    # so data costs 100 / (1 - q)^2 and each arrival costs one ACK.
    ack_data, acks = 100 / (1 - q) ** 2, 100 / (1 - q)
    nack_data, nacks = 100 / (1 - q), 100 * q / (1 - q)
    print("  %6.2f  %7.0f + %-5.0f = %5.0f  %6.0f + %-4.0f = %5.0f  %8.0f"
          % (q, ack_data, acks, ack_data + acks, nack_data, nacks, nack_data + nacks, nack_data))

# 3. How fast congestion control can react. A hotspot u hops upstream of the
#    sink receives 10 packets per hop time and can forward 6, so it drops 4 a
#    hop time until the flow slows. Hop-by-hop backpressure throttles the
#    neighbour one hop time later. End-to-end regulation waits for the sink to
#    notice (u hop times for the thinned flow to reach it, plus a decision
#    interval of 5) and for its message to reach the sources (u + 3 hops).
print("\nPackets dropped at a hotspot before the flow slows (10 arrive, 6 forwarded):")
print("  hops from the sink   hop-by-hop backpressure   end-to-end regulation")
for u in (2, 5, 10, 20):
    print("  %18d   %22d   %21d" % (u, 1 * 4, (u + 5 + u + 3) * 4))

# 4. Fairness. Six sources, two 1 hop from the sink and four 5 hops away, share
#    a sink that can take 12 packets per second. Each packet costs one
#    transmission per hop, and the whole network can make 30 transmissions a
#    second. Equal rates against rates proportional to 1 / hops.
def jain(rates):
    return sum(rates) ** 2 / (len(rates) * sum(r * r for r in rates))

hops = [1, 1, 5, 5, 5, 5]
budget = 30.0
equal = [budget / sum(hops)] * 6
weighted = [budget / (len(hops) * h) for h in hops]
for name, rates in (("equal rate to every source", equal), ("rate proportional to 1 / hops", weighted)):
    print("\n%s:" % name)
    print("  rates (packets/s): " + ", ".join("%.2f" % r for r in rates))
    print("  transmissions/s %.1f of %.0f; packets reaching the sink %.2f/s; Jain's fairness %.3f"
          % (sum(r * h for r, h in zip(rates, hops)), budget, sum(rates), jain(rates)))

Event reliability is cheap. Five sources needing three reports fail half the time when packets arrive with probability 0.5. Twenty sources needing three succeed 99.98 per cent of the time at p = 0.5, and 96.45 per cent even at p = 0.3. Redundant sources do what retransmission would have done, at no cost in protocol: this is why a sensor network can often ask for rate control rather than reliability. But the demand matters: twenty sources needing eight reports succeed only 22.77 per cent of the time at p = 0.3, and there the protocol must act.

What detection costs. Over a hop losing 10 per cent, delivering 100 packets costs 111 data transmissions. NACK adds 11 control packets; a positive acknowledgement, which must itself get through, brings the total to 235 transmissions, more than twice the data. Implicit acknowledgement adds nothing on the air, but the sender's radio must be listening, which is where [Duty Cycling: Preamble Sampling, B-MAC and X-MAC] counts its cost. At 20 per cent loss, ACK costs 281 transmissions against NACK's 150.

What a slow signal costs. A hotspot receiving 10 packets a hop time and forwarding 6 drops 4 a hop time. Hop-by-hop backpressure stops the inflow one hop time later: 4 packets lost, wherever the hotspot is. End-to-end regulation waits for the sink to notice and for its message to travel out: 48 packets at 2 hops, 192 at 20. The first is fast and local, the second sees the whole event: CODA runs both.

What fairness costs. With a budget of 30 transmissions a second, giving all six sources the same rate delivers 8.18 packets a second to the sink, with Jain's fairness index at 1. Giving each source a rate proportional to 1 divided by its hop count delivers 14.00 packets a second, 71 per cent more, with fairness at 0.605: the two near sources send five times as often as the four far ones. A far source is expensive, and every sensor transport protocol must choose how much throughput to give up for it.

Distinctions

What it does not mean

Less reliability is not lower quality. Event reliability asks for what the application actually needs; delivering every duplicate report of one fire is the waste.

Hop-by-hop recovery is not always right. It costs a cache at every node, and RMST found it stops paying once the MAC keeps losses below 1 per cent.

A NACK scheme is not free. It is cheap when losses are rare, and it still needs timeouts for a loss with nothing behind it.

An empty queue does not mean no congestion. The channel is shared: a node's neighbours can be saturating the air while its own buffer is empty.

Fairness is not automatic. Equal rates cost throughput; maximum throughput silences the far sources. A protocol must choose, and say which.

These issues are not independent. Choosing event reliability makes rate control the natural remedy; choosing hop-by-hop recovery demands caches and memory; saving energy limits how often the channel can be sampled.

Quick revision

• Direction: upstream (many to one, bursty, often loss-tolerant) against downstream (one to many, code and commands, must be complete).
• Reliability: packet, block (every fragment: code), or event (ESRT: observed ri against desired R in a decision interval; control the reporting rate f).
• Loss detection: ACK, NACK (needs a later packet or a timeout), implicit ACK (overhear the forward), sequence numbers and timers.
• Loss recovery: end to end against hop by hop; caching at every node or only at the ends; the MAC's retries first.
• Congestion detection: queue length (bimodal, coarse), channel loading (accurate, costs listening, so sampled), rate mismatch (slow, end to end). Congestion is shared, not only local.
• Notification: explicit message or piggybacked bit; hop-by-hop backpressure (fast, local) and sink regulation (slow, whole-event). CODA runs both.
• Rate adjustment: throttle, drop, AIMD, or the sink assigns a reporting rate.
• Constraints: energy (count transmissions; CODA's energy tax and fidelity penalty), memory and state, fairness (far sources cost more), timeliness and priority.
• Program: 20 sources, 3 needed: 0.9998 at p = 0.5; ACK 235 transmissions against NACK 122 at 10 per cent loss; hotspot drops 4 with backpressure against 112 with sink regulation at 10 hops; equal rates 8.18 packets/s (fairness 1.000) against 14.00 (fairness 0.605).

Test yourself

1. List the design issues for a transport protocol in a wireless sensor network. The direction of the traffic (upstream from sources to sink, or downstream from sink to nodes); what reliability is required (every packet, a whole block, or the event); how loss is detected (positive acknowledgements, negative acknowledgements, implicit acknowledgements, sequence numbers and timeouts); where loss is repaired (end to end or hop by hop, with or without caching); how congestion is detected (queue length, channel loading, rate mismatch); how it is notified (explicit or piggybacked, hop-by-hop backpressure or regulation from the sink); how the rate is adjusted; and the constraints of energy, memory and state, fairness among near and far sources, and timeliness or priority.

2. Distinguish packet reliability from event reliability, and say why the difference matters. Packet reliability requires every packet to be delivered, and is achieved by retransmission. Event reliability requires only that the sink receive enough reports about an event to detect it: ESRT defines the observed event reliability as the number of data packets received in a decision interval and the desired reliability as the number needed by the application. It matters because many sensors report the same event, so redundancy replaces retransmission: the protocol can control the sources' reporting rate instead of repairing losses, which saves energy and avoids the congestion that extra traffic would cause.

3. Compare ACK, NACK and implicit acknowledgement as loss-detection mechanisms. A positive acknowledgement is sent for every packet received, so loss is detected quickly but one control packet is spent per data packet and a lost acknowledgement causes an unnecessary retransmission. A negative acknowledgement is sent only when the receiver notices a gap, which is cheap when losses are rare, but a loss at the end of a burst is not revealed by any later packet and needs a timeout. An implicit acknowledgement costs nothing on the air, since the sender overhears its neighbour forwarding the packet, but the sender's radio must be listening and the last hop cannot be confirmed this way.

4. Why is buffer occupancy a poor indicator of congestion in a sensor network, and what does CODA use instead? The medium is shared, so a node can be unable to send because its neighbours are using the channel while its own queue is nearly empty; CODA's simulations found the buffer occupancy bimodal, empty or about to overflow, too coarse and unresponsive for smooth control. CODA therefore combines present and past channel loading, measured by listening to the channel and tracing its busy time, with the current buffer occupancy, and samples the channel rather than listening continuously in order to save energy.

5. Compare hop-by-hop backpressure with regulation from the sink. Hop-by-hop backpressure is open-loop and fast: a congested node broadcasts backpressure to its upstream neighbours, which throttle or drop, and each decides whether to propagate it further, so the inflow falls after about one hop time. Sink regulation is closed-loop and slower: the sink notices that reliability or the reporting rate has fallen and sends new rates to all sources, which takes a detection interval plus the travel time of the message. The first resolves local, transient hotspots; the second settles persistent congestion across many sources; CODA uses both.

6. Why is fairness a problem in sensor transport, and what does it cost? A source many hops from the sink consumes one transmission on every hop for each packet delivered, while a source one hop away consumes one, so a fixed budget of transmissions buys far fewer packets from distant sources. Giving every source the same rate is fair but wastes capacity; giving near sources higher rates raises the total delivered but silences the far ones, and the sink then hears mostly about its own neighbourhood. In the chapter's example, equal rates delivered 8.18 packets per second with Jain's fairness index 1.000, while rates proportional to the inverse of the hop count delivered 14.00 packets per second with fairness 0.605.