TDMA and Schedule-based MAC

Figure 49.1 One frame of a ten-member cluster, and one slot with its guards

Allocating the slots

In a cluster, one node decides. LEACH's head gives each member one slot, and every slot has the same length, so the time to send a frame grows with the number of nodes in the cluster. The head, which must receive every slot, is awake far longer than any member: "The cluster head must be awake to receive all the data from the nodes in the cluster." LEACH rotates the role for exactly that reason.

Between clusters, neighbouring clusters' slots overlap in time. LEACH separates them by code instead of time: each cluster uses its own direct-sequence spreading code, and the paper notes the cost: "the drawback of using DSSS is the need for tight timing synchronization".

In a multi-hop network, a slot can be used again by nodes far enough apart, which is TDMA's spatial reuse. The rule is set by the receivers. Two nodes that are neighbours cannot share a slot (each may be the other's receiver), and two nodes with a common neighbour cannot either, because that neighbour would hear both at once. So nodes within two hops of each other need different slots; nodes three or more hops apart may share.

Worked example: a chain. Seven nodes in a line, A to G, each hearing only its neighbours, send hop by hop towards A. Giving every node its own slot needs a frame of 7. With the two-hop rule, slots can repeat every third node:

Check one pair: B and E both use slot 2. B's neighbours are A and C, E's are D and F; no node hears both, so their frames cannot collide. A, D and G share slot 1 for the same reason. The frame shrinks from 7 slots to 3, and a node's reading waits for a frame less than half as long. Any two nodes one or two hops apart (A and B, A and C) have different slots, so 3 is also the least possible. The paired practical does the same on a grid, where a node and its four neighbours are all within two hops of each other and at least 5 slots are needed.

Distributed allocation needs no head. Akyildiz and colleagues describe SMACS, in which nodes "discover their neighbors and establish transmission/reception schedules for communication without the need for any local or global master nodes", each link being "a pair of time slots operating at a randomly chosen but fixed frequency". Its drawback, in the same survey, is that members of different subnets "might never get connected".

Keeping the schedule: synchronisation and guard times

A slot is only useful if sender and receiver agree when it starts, and their clocks drift. [Time Synchronisation and Localisation] gave the figure: a mote's clock may be up to 40 ppm out, 40 microseconds per second, and 802.15.4 demands the same ±40 ppm of the radio's crystal, "This accuracy must also take ageing and temperature drift into consideration." Two clocks each 40 ppm out, in opposite directions, drift apart by up to 80 ppm.

So a TDMA node must wake early, and a slot must carry a guard on each side, as wide as the drift since the last synchronisation.

Worked example. If the head's beacon resynchronises everyone once a minute, the drift before the next beacon can reach 80 ppm × 60 s = 0.0048 s, 4.8 ms. A 50-byte frame lasts only 1.6 ms, so each slot needs 4.8 ms of guard on each side of it: the guards are six times the frame. Beaconing every 10 s cuts the guard to 0.8 ms; every second, to 80 microseconds.

The guards cost the listener, who must be awake from the earliest moment the frame might start to the latest. LEACH simply assumes the problem away ("We assume that the nodes are all time synchronized"), suggesting that the base station could send "synchronization pulses". A real schedule pays for it in beacons and in guards, and the program finds the balance.

TDMA against CSMA, for the same traffic

The program charges a LEACH-style cluster of a head and 10 members for one hour. Each member sends one 50-byte reading a minute in its own slot and hears an 11-byte ACK; the head sends a 20-byte beacon every sync seconds, which resets the members' clocks. Members wake early by the guard to hear each beacon; the head listens to every slot for its full width, guards included. Everyone sleeps at 0.02 mA otherwise. For comparison, the same member traffic is charged with CSMA and the receiver always on. Lifetimes are for 2,500 mAh.

# One cluster, as in LEACH: a head and 10 members, each member sending one
# 50-byte reading a minute. TDMA: the frame is one minute and each member owns
# one slot in it. The head's beacon resets the members' clocks every `sync`
# seconds; in between, two clocks each up to 40 ppm out drift apart by up to
# 80 ppm, so a slot needs a guard on each side, and whoever listens for a
# beacon or a slot must wake that much early.
RX, TX, SLEEP = 18.8, 17.4, 0.02           # mA, the CC2420
BYTE = 8 / 250_000                         # seconds per byte on air
DATA, ACK, BEACON = 50, 11, 20             # bytes on air
DRIFT = 2 * 40e-6                          # two clocks, each up to 40 ppm out
MEMBERS, FRAME, HOUR = 10, 60.0, 3600.0

def charge(rx, tx):                        # mA-s over the hour, asleep otherwise
    return rx * RX + tx * TX + (HOUR - rx - tx) * SLEEP

def tdma(sync):
    guard = DRIFT * sync                   # the worst drift since the last beacon
    beacons, frames = HOUR / sync, HOUR / FRAME
    slot = DATA * BYTE + ACK * BYTE + 2 * guard
    member = charge(rx=beacons * (guard + BEACON * BYTE) + frames * ACK * BYTE,
                    tx=frames * DATA * BYTE)
    head = charge(rx=frames * MEMBERS * (2 * guard + DATA * BYTE),
                  tx=beacons * BEACON * BYTE + frames * MEMBERS * ACK * BYTE)
    return slot, member, head

def life(mas):                             # days on 2,500 mAh at this mA-s an hour
    return 2500 / (mas / HOUR) / 24

print("beacon every   slot    member mA-s   days    head mA-s   days")
for sync in (1, 10, 60, 600):
    slot, member, head = tdma(sync)
    print("%9d s %6.1f ms %10.1f %7.0f %11.1f %6.0f"
          % (sync, slot * 1000, member, life(member), head, life(head)))
# the same member traffic with CSMA and the receiver always on
frames = HOUR / FRAME
csma = charge(rx=HOUR - frames * DATA * BYTE, tx=frames * DATA * BYTE)
print("CSMA, always on        %10.1f %7.1f" % (csma, life(csma)))

beacon every   slot    member mA-s   days    head mA-s   days
        1 s    2.1 ms      122.7    3055       135.5   2767
       10 s    3.6 ms       83.8    4475       115.7   3240
       60 s   11.6 ms       80.2    4676       202.5   1851
      600 s   98.0 ms       79.5    4714      1175.5    319
CSMA, always on           67679.9     5.5

Reading it: the members. A TDMA member spends between 79.5 and 122.7 mA-s an hour, against 67,679.9 for the same traffic with CSMA listening all the time: some 550 to 850 times less. Of its 80.2 mA-s at a one-minute beacon, 72 are the sleep current alone (3,600 s × 0.02 mA). The computed lifetimes, 3,055 to 4,714 days, are 8 to 13 years, beyond the alkaline cell's 10-year shelf life that [How Long a Node Lasts: The Energy Budget Worked Out] warned about: once a schedule has removed idle listening, the battery's chemistry sets the lifetime, not the MAC.

The members hardly care how often the beacon comes. A member's guard grows with the interval, but it hears proportionally fewer beacons, and the two cancel: 80 ppm of every hour, 0.288 s, is spent in guards whatever the interval. Only the beacons' own airtime changes, which is why beaconing every second costs the members most.

The head does care. It listens to every slot across both guards. With a beacon every 10 s it spends 115.7 mA-s an hour; every minute, 202.5; every 10 minutes, 1,175.5, when each slot has grown to 98.0 ms, almost all guard, and the head lasts 319 days. Every second, the beacons themselves cost it 135.5. The best interval here is near 10 s, and it depends on the clocks: better crystals push it out, worse ones pull it in.

What TDMA costs besides energy

Latency. A reading waits for its node's slot, on average half a frame: 30 s in a one-minute frame. In a multi-hop network it waits again at every hop unless the slots are ordered along the route. S-MAC's authors, whose protocol is not TDMA, face the same trade in its sleep schedule ([S-MAC: Latency, Adaptive Listening and the Energy Saved]).

Wasted slots. A slot belongs to its owner whether or not it has anything to send, and a node cannot borrow another's. Ye, Heidemann and Estrin note of Sohrabi and Pottie's super frame that "A drawback of the scheme is its low bandwidth utilization. For example, if a node only has packets to be sent to one neighbor, it cannot reuse the time slots scheduled to other neighbors."

Change. "When the number of nodes within a cluster changes, it is not easy for a TDMA protocol to dynamically change its frame length and time slot assignment. So its scalability is normally not as good as that of a contention-based protocol." Every node that dies or joins, and every change in traffic, means a new schedule. LEACH rebuilds its clusters and schedules every round.

The synchronisation itself. Beacons, guards, and a node that must never miss its beacon.

These are why most sensor MACs are hybrids: S-MAC shares a coarse schedule of listen and sleep and contends inside it ([S-MAC: Periodic Listen and Sleep, and Keeping Neighbours in Step]); 802.15.4's superframe offers a contention access period and, for devices that need them, guaranteed time slots ([The 802.15.4 Superframe and Guaranteed Time Slots]).

Distinctions

What it does not mean

TDMA does not mean every node needs its own slot. Nodes three or more hops apart can share one; the chain of seven needed three.

A schedule is not free once built. Clocks drift from the moment they are set, and the guards and beacons that absorb the drift cost energy every frame.

Rare beacons are not always cheaper. The members save a little; the head, listening across ever wider guards, pays far more.

No idle listening does not mean no waste. An owned slot with nothing to send is channel wasted, and a reading waiting for its slot is time wasted.

Quick revision

• TDMA: frames of slots; each node transmits only in its own slot: no collisions, no idle listening; radio off otherwise.
• LEACH: the head "sets up a TDMA schedule"; members send "at most once per frame"; the frame grows with the cluster; the head stays awake for all slots; clusters separated by DSSS codes.
• Two-hop rule: nodes within two hops need different slots; farther ones may reuse a slot. A chain of 7 needs 3 slots (1, 2, 3, 1, 2, 3, 1); a grid needs at least 5.
• SMACS: distributed, pairs of slots on a random fixed frequency, no master.
• Guard = relative drift × time since the last sync: 80 ppm × 60 s = 4.8 ms each side, against a 1.6 ms frame.
• Program: member about 80 mA-s an hour (mostly sleep current) against 67,679.9 for always-on CSMA; head cheapest with a beacon near every 10 s (115.7), worst at 10 minutes (1,175.5, slots of 98 ms).
• Costs: latency, wasted slots, poor adaptability, synchronisation. Hence hybrids: S-MAC, 802.15.4's GTS.

Test yourself

1. What is TDMA, and why does it save energy in a sensor network? Time is divided into repeating frames and each frame into slots, and each node is allocated a slot in which alone it transmits. Because interfering nodes never share a slot, there are no collisions and no contention, and each node knows exactly when it must transmit or receive, so it can keep its radio off at all other times and avoid idle listening and overhearing.

2. Explain the two-hop rule for reusing slots, with an example. Two nodes that are neighbours cannot share a slot, and two nodes with a common neighbour cannot either, because that neighbour would receive both transmissions at once. So nodes within two hops of each other need different slots, while nodes three or more hops apart can share one. In a chain A to G, slots 1, 2, 3, 1, 2, 3, 1 are enough: B and E share slot 2, and no node hears both.

3. Why does a TDMA schedule need guard times? Compute one. Clocks drift, so a sender's slot may start a little earlier or later than the receiver expects. A guard on each side of the slot, as wide as the worst drift since the last synchronisation, absorbs this. With clocks up to 40 ppm out each (80 ppm between two) and a beacon once a minute, the guard is 80 ppm × 60 s = 4.8 ms, three times the 1.6 ms of a 50-byte frame.

4. How does the beacon interval affect the energy of the members and of the cluster head? Members wake early for each beacon by a guard proportional to the interval, but hear proportionally fewer beacons, so their guard cost per hour is fixed and only the beacons' airtime falls with longer intervals. The head listens across the guards of every slot, which widen with the interval, so its cost rises steeply for long intervals, while very short intervals cost it many beacon transmissions. In the program the head spent least with a beacon every 10 s.

5. What are the disadvantages of TDMA in a wireless sensor network? Readings wait for their slots, adding latency at every hop; a slot is wasted when its owner has nothing to send; schedules must be rebuilt whenever nodes join, leave or change their traffic, so it scales and adapts poorly; and all nodes must be kept synchronised, which costs beacons and guard times.

6. How does LEACH use TDMA and CDMA together? Inside each cluster the cluster head builds a TDMA schedule and sends it to the members, who transmit in their own slots and turn their radios off otherwise, so there are no collisions within the cluster. Between clusters, whose slots overlap in time, each cluster uses a different direct-sequence spreading code, which keeps neighbouring clusters from interfering but requires tight timing synchronisation.