S-MAC: Collision Avoidance, Overhearing Avoidance and Message Passing

Overhearing avoidance: who should sleep?

In 802.11 every node listens to everything. The journal is blunt about the cost: "In 802.11 each node keeps listening to all transmissions from its neighbors in order to perform effective virtual carrier sense. As a result, each node overhears many packets that are not directed to itself." S-MAC borrows the answer of PAMAS, an earlier protocol, but without PAMAS's second radio channel: "S-MAC tries to avoid overhearing by letting interfering nodes go to sleep after they hear an RTS or CTS packet. Since DATA packets are normally much longer than control packets, the approach prevents neighboring nodes from overhearing long DATA packets and following ACKs."

Which nodes should sleep? The paper argues it on a line of six nodes, E, C, A, B, D and F, each hearing only its immediate neighbours, with A sending to B.

Figure 52.1 Who sleeps while A sends to B (after the paper's Fig. 5), and message passing

• D must sleep. It is B's neighbour; anything it sends would collide with A's data at B. "Remember that collision happens at the receiver."
• E and F need not. They are out of range of both A and B, and cause no interference.
• C should sleep too, although it is two hops from B and its own transmission would not disturb B. C could send to E, but E's reply would collide at C with A's transmission, which C hears; and C's transmission could corrupt B's ACK arriving at A. "So C's transmission is simply a waste of energy."

The conclusion: "all immediate neighbors of both the sender and receiver should sleep after they hear the RTS or CTS until the current transmission is over". C learns of the exchange from A's RTS, D from B's CTS, and each sets its NAV from the duration field: "a node should sleep to avoid overhearing if its NAV is not zero. It can wake up when its NAV becomes zero." C's case is [Hidden and Exposed Terminals, and RTS and CTS]'s exposed terminal, and S-MAC settles it the same way the acknowledgement does in 802.11: the exposed node stays quiet, and here it also sleeps.

Overhearing is not always waste. The paper notes that some algorithms rely on it "to gather neighborhood information for network monitoring, reliable routing or distributed queries", and S-MAC can be configured to allow it; but it suggests that algorithms that do not need it suit energy-limited networks better, and uses explicit acknowledgements rather than inferring delivery from overheard forwarding.

Message passing

In-network processing works on messages: "A message is the collection of meaningful, interrelated units of data. The receiver usually needs to obtain all the data units before it can perform in-network data processing or aggregation." A long message poses a dilemma. Sent as one long packet, a few corrupted bits force the whole of it to be sent again. Sent as independent small packets, "we have to pay the penalty of large control overhead and longer delay", because each packet contends and runs its own RTS and CTS.

S-MAC's answer is to "fragment the long message into many small fragments, and transmit them in a burst. Only one RTS and one CTS are used. They reserve the medium for transmitting all the fragments." Three details make it work:

1. Every fragment is acknowledged. "If it fails to receive the ACK, it will extend the reserved transmission time for one more fragment, and re-transmit the current fragment immediately."
2. Every packet carries the time left. The duration field in each fragment and ACK is the time still needed for all the remaining fragments and ACKs, so "if a node wakes up or a new node joins in the middle of a transmission, it can properly go to sleep no matter if it is the neighbor of the sender or the receiver."
3. The ACKs guard against hidden terminals. A node that is a neighbour of the receiver only cannot hear the fragments; without frequent ACKs it "may mistakenly infer from its carrier sense that the medium is clear" and start sending, corrupting the transfer at the receiver.

Against 802.11's fragmentation. 802.11 can also fragment, but its RTS and CTS reserve the channel only for the first fragment and its ACK, and each fragment then reserves the next. A neighbour therefore learns only that one more fragment follows, "So it has to keep listening until all the fragments are sent." And when a fragment fails, 802.11, designed for fairness, "must give up the transmission and re-contend for the medium so that other nodes have a chance to transmit", while S-MAC extends and resends at once, with "less contention and a small latency." S-MAC caps the number of extensions in case the receiver has died.

The fairness it gives up. Message passing is unfair by design: a node with a long message holds the channel, and neighbours with a short packet wait. The 2002 paper accepts it: "a node who has more data to send gets more time to access the medium." In a network serving one application, "application-level performance is the goal as opposed to per-node fairness."

One message, three ways

The program sends one message of 10 fragments from A to B on the paper's line, where C is A's other neighbour and D is B's. Timings follow the journal's Table I for the Mica motes: 20 kbit/s with Manchester coding, so 0.8 ms per byte; 10-byte control packets (8 ms); fragments of 40 bytes of data, the size used in the paper's two-hop test, plus an 8-byte MAC header (38.4 ms). Powers are the TR3000's: 14.4 mW receiving or listening, 36 mW transmitting, 0.015 mW asleep. It compares a handshake for every fragment, 802.11's fragmentation (one handshake, neighbours listening throughout), and S-MAC's message passing (one handshake, C asleep after the RTS and D after the CTS). Contention time and the gaps between frames are left out of all three.

# One message of 10 fragments from A to B, on a line E - C - A - B - D - F where
# each node hears only its neighbours: C hears A, D hears B. Mica numbers from
# the S-MAC journal paper: 20 kbit/s with Manchester coding (0.8 ms a byte),
# 10-byte control packets, and fragments of 40 bytes plus an 8-byte header.
# Energy in mJ (mW x s); radio powers of the TR3000.
BYTE = 8 * 2 / 20_000                    # s per byte on air
CTRL, FRAG = 10 * BYTE, 48 * BYTE        # an RTS, CTS or ACK; one data fragment
P_RX, P_TX, P_SLEEP = 14.4, 36.0, 0.015  # mW
N = 10                                   # fragments

def exchange(handshakes, neighbours_sleep):
    """handshakes: how many RTS/CTS pairs the message needs. Returns the time on
    air and each node's energy. Without overhearing avoidance, C and D keep
    their receivers on for the whole exchange."""
    a_tx = handshakes * CTRL + N * FRAG               # RTSs and fragments
    b_tx = handshakes * CTRL + N * CTRL               # CTSs and ACKs
    total = a_tx + b_tx
    energy = {"A": a_tx * P_TX + b_tx * P_RX,
              "B": b_tx * P_TX + a_tx * P_RX}
    if neighbours_sleep:          # C sleeps after the RTS, D after the CTS
        energy["C"] = CTRL * P_RX + (total - CTRL) * P_SLEEP
        energy["D"] = 2 * CTRL * P_RX + (total - 2 * CTRL) * P_SLEEP
    else:
        energy["C"] = energy["D"] = total * P_RX
    return total, energy

print("scheme                        time ms     A      B      C      D    total mJ")
for name, handshakes, sleep in (("RTS/CTS for every fragment", N, False),
                                ("802.11 fragmentation", 1, False),
                                ("S-MAC message passing", 1, True)):
    total, e = exchange(handshakes, sleep)
    print("%-28s %8.1f %6.2f %6.2f %6.2f %6.2f %9.2f"
          % (name, total * 1000, e["A"], e["B"], e["C"], e["D"], sum(e.values())))

scheme                        time ms     A      B      C      D    total mJ
RTS/CTS for every fragment      624.0  19.01  12.44   8.99   8.99     49.42
802.11 fragmentation            480.0  15.38   8.81   6.91   6.91     38.02
S-MAC message passing           480.0  15.38   8.81   0.12   0.24     24.55

Reading it. A handshake for every fragment keeps the channel busy for 624 ms and costs 49.42 mJ in all. One handshake for the burst, as 802.11's fragmentation and S-MAC both use, saves 9 RTS/CTS pairs: 480 ms and 38.02 mJ. So far S-MAC and 802.11 are equal.

Overhearing avoidance makes the difference. In 802.11 the neighbours C and D listen through all 480 ms, 6.91 mJ each. In S-MAC, C sleeps after the 8 ms RTS and D after the RTS and CTS, and they spend 0.12 and 0.24 mJ. The total falls to 24.55 mJ, about half of the first scheme, and every other neighbour of A or B would save as much again.

The sender and receiver pay the same in all three but the first. Message passing does not change what A and B must send; it removes the repeated handshakes, and overhearing avoidance removes the listening of everyone else. In a dense network, where a node has many neighbours, the second saving dominates.

The paper measured the same pattern. On its two-hop test with two sources, under heavy traffic, "802.11 MAC uses more than twice the energy used by S-MAC", and since idle listening was rare at that load, "S-MAC achieves energy savings mainly by avoiding overhearing and efficiently transmitting long messages." Under light traffic, periodic sleep took over as the main saving ([S-MAC: Latency, Adaptive Listening and the Energy Saved]).

Distinctions

What it does not mean

Overhearing avoidance is not collision avoidance. The NAV stops a neighbour from transmitting; sleeping also stops it from listening. S-MAC does both with the same duration field.

Message passing is not a longer packet. Each fragment is short and separately acknowledged; only the reservation is long.

Sleeping neighbours do not lose track. Every fragment and ACK carries the time left, so a node that wakes in the middle can go back to sleep for exactly the right time.

Giving up fairness is not giving up delivery. Short messages still get through; they wait for the long one, which suits a network where the long message is what the application needs.

Quick revision

• Collision avoidance as in 802.11: physical and virtual carrier sense (NAV), carrier-sense time randomised in a contention window; contention in the receiver's listen interval, split into SYNC and RTS parts (15 and 31 slots on Mica).
• Loser sleeps until the receiver's next listen; winners use their sleep time to finish. Unicast: RTS/CTS/DATA/ACK. Broadcast: no RTS/CTS.
• Overhearing avoidance (after PAMAS, in-channel): nodes that hear an RTS or CTS for another node sleep while their NAV is non-zero. On E, C, A, B, D, F with A sending to B: D and C sleep, E and F are free: all immediate neighbours of sender and receiver.
• Message passing: fragments in a burst, one RTS and one CTS; ACK per fragment; duration = all remaining fragments and ACKs; lost fragment: extend and resend; a cap on extensions. Trades per-node fairness for message latency and energy.
• Program (10 fragments, Mica numbers): handshake per fragment 49.42 mJ; 802.11 fragmentation 38.02; S-MAC message passing 24.55, neighbours 0.12 and 0.24 mJ against 6.91 each.

Test yourself

1. How does S-MAC avoid collisions? It follows IEEE 802.11: before sending, a node performs virtual carrier sense, checking that its NAV (set from the duration fields of overheard packets) is zero, and physical carrier sense, listening to the channel, with its carrier-sense time randomised within a contention window. Unicast packets use the RTS/CTS/DATA/ACK exchange, which protects against hidden terminals; broadcasts use carrier sense only. All contention takes place in the receiver's listen interval, divided into parts for SYNC and for RTS packets.

2. Which nodes should sleep when node A transmits to node B, and why? All immediate neighbours of both A and B. B's neighbours must not transmit, because they would collide with the data at B. A's neighbours could transmit without disturbing B, but they could not receive any reply, since A's transmission would collide with it at them, and their transmissions could corrupt B's ACK at A; so transmitting would waste energy. Nodes farther away are free.

3. Explain overhearing avoidance in S-MAC. When a node hears an RTS or CTS addressed to another node, it reads the duration field, sets its NAV and goes to sleep until the NAV reaches zero, so it does not overhear the long data packet and the ACK that follow. The idea comes from PAMAS, but S-MAC uses only the ordinary RTS and CTS on the data channel rather than a separate signalling channel.

4. What is message passing, and how does it differ from 802.11's fragmentation? A long message is split into fragments sent in a burst, reserved by a single RTS and CTS whose duration covers all of them; each fragment is acknowledged, a lost one is resent at once by extending the reservation, and every fragment and ACK carries the remaining duration. In 802.11 the RTS and CTS reserve only the first fragment and each fragment reserves the next, so neighbours must keep listening, and a failed fragment makes the sender give up and contend again for the sake of fairness.

5. What does message passing trade off, and why is that acceptable in a sensor network? It gives up per-node fairness: a node with a long message holds the channel while neighbours with short packets wait. It gains lower message-level latency and less control overhead and contention. In a sensor network the nodes serve one application and in-network processing needs whole messages, so application-level performance matters more than fairness between nodes.

6. Using the program's figures, how much energy do message passing and overhearing avoidance save? Sending a 10-fragment message with a handshake for every fragment cost 49.42 mJ over the four nodes; one handshake for the burst (802.11 fragmentation) cost 38.02 mJ, with each neighbour spending 6.91 mJ listening; S-MAC's message passing with overhearing avoidance cost 24.55 mJ, the neighbours spending only 0.12 and 0.24 mJ.