2 of 92

Low-Power MACs, Meshing, and Flooding Goals

Investigate a decade of low power MAC research

Understand how low power MACs complicate routing

Understand why IoT might want to use mesh networks

Look at one ”traditional” mesh network algorithm in-depth

Look at emerging “non-traditional” ideas, see counter-intuitive tradeoffs

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

3 of 92

Outline

Low-Power MAC Design

Simple Routing

Mesh Routing

Flooding

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

4 of 92

THE question for low-power devices: When to talk, to listen?

Recall BLE, where advertisements are broadcast:

Who do I talk to is simple, anyone within one-hop
When do advertisers talk, listen?
When do scanners listen, talk?

Recall BLE, where connections use a star topology:

When do centrals, peripherals talk and listen?

What happens when networks get bigger?

No device has a “global” view

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

5 of 92

Always-on* Radios Simplify Protocols�*Or at least “usually-on” / “often-on”

Many protocols assume a more-powerful device with lots of energy

BLE: Central
Thread: Router/Leader
Zigbee: Router/Coordinator
WiFi: Router
LoRa: Gateway

This assumption simplifies the “when to listen” problem

Powerful device: always listen
Low-power device: listen-after-talk or synchronized schedule

What do we do when everyone is equal?

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

6 of 92

Asynchronous MAC principles

Communication is possible if one device is receiving while other is transmitting
Both devices want to minimize the time they are receiving or transmitting (i.e. their radio is on) to reduce power draw
Devices can only coordinate using the data communication channel (i.e. no out-of-band communication)

No global synchronization mechanism

Goal: scheme to schedule TX and RX to permit communication while minimizing energy
Energy is paramount, but additional metrics:

Latency
Throughput
Reliability
Network scale

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

7 of 92

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

8 of 92

Early�2000s

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

9 of 92

Early days of low power sensor nodes…

WINSng [Pottie00]

Mica [Hill01]

Rene [Hill99]

Mica2 [Xbow03]

MicaZ [Xbow05]

PC/104 [Cerpa01]

PASTA [Bajura05]

mPlatform[Lymberopoulos07]

WeC [Hill98]

WINS [Rockwell]

Stargate [Intel]

Telos/Tmote

[Polastre05]

Iris [Xbow07]

Tmote Mini

[Sentilla07]

MicaZ Stamp

[Xbow06]

Iris OEM

[Xbow07]

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

10 of 92

Low power: multiple year operation using batteries

P_node = P_CPU + P_TX + P_RX + P_SLEEP
E_BATT = P_node * lifetime

Lifetime ⬆️, P_node⬇️

P_CPU ≫ P_SLEEP
P_TX ≫ P_SLEEP
P_RX≫ P_SLEEP
_{→ Minimize compute, TX, RX}
_{→ Maximize sleep}

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

11 of 92

Low power MAC principles

Communication is possible if one device is receiving while other is transmitting
Devices can only coordinate using the data communication channel (i.e. no out-of-band communication)

No global synchronization mechanism

Goal: scheme to schedule TX and RX to permit communication while minimizing energy
Energy is paramount, but additional metrics:

Latency
Throughput
Reliability
Network scale

Both devices want to minimize the time they are receiving or transmitting (i.e. their radio is on) to reduce power draw

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

12 of 92

Low Power Listening (LPL) - B-MAC (2004)

Method:

Receiver periodically samples the channel
Transmitter sends a preamble long enough to ensure receiver will detect it
Upon detection, receiver stays awake to receive transmitted packet
Receiver ACKs if packet received correctly

CCA

Receiver

Transmitter

Sleep

CCA

Sleep

Preamble

Sleep

CCA

Sleep

Versatile Low Power Media Access for Wireless Sensor Networks. Joseph Polastre, Jason Hill and David Culler. SenSys 2004

CCA

TX ACK

RX ACK

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

13 of 92

LPL performance

CCA check interval

Too small: energy wasted on idle listening
Too large: energy wasted on transmissions (long preambles)

In general, it’s better to have larger preambles than to check more often!

Sensor sample period – controls the packet rate

Time between listening

(checking if the channel is idle)

Versatile Low Power Media Access for Wireless Sensor Networks. Joseph Polastre, Jason Hill and David Culler. SenSys 2004

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

14 of 92

LPL Drawback

Spend time listening to packets for someone else!

CCA

Receiver

Transmitter

Sleep

CCA

Sleep

Preamble

Sleep

CCA

Sleep

CCA

TX ACK

RX ACK

CCA

Receiver

Sleep

CCA

Sleep

CCA

Sleep

CCA

DROP

Versatile Low Power Media Access for Wireless Sensor Networks. Joseph Polastre, Jason Hill and David Culler. SenSys 2004

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

15 of 92

X-MAC: Shorter preambles and destination information

Method

Transmitter sends a short “I have a packet for this address” packet
Nodes periodically listen, and ACK if the packet is for them
Upon receiving the ACK, the transmitter sends full packet
Receiver successfully receives the full packet.

X-MAC: A Short Preamble MAC Protocol for Duty-Cycled Wireless Sensor Networks. Michael Buettner, Gary V. Yee, Eric Anderson, Richard Han. SenSys 2006.

Receiver

Transmitter

Sleep

TX ACK

RX ACK

TX ACK

RX ACK

TX (DST ID)

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

16 of 92

X-MAC: Overhearing node drops out early

Receiver

Transmitter

Sleep

TX (DST ID)

Sleep

TX ACK

RX ACK

TX ACK

RX ACK

Overhearer

Sleep

TX (DST ID)

X-MAC: A Short Preamble MAC Protocol for Duty-Cycled Wireless Sensor Networks. Michael Buettner, Gary V. Yee, Eric Anderson, Richard Han. SenSys 2006.

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

17 of 92

X-MAC: lower power draw than LPL with multiple nearby transmitters

X-MAC: A Short Preamble MAC Protocol for Duty-Cycled Wireless Sensor Networks. Michael Buettner, Gary V. Yee, Eric Anderson, Richard Han. SenSys 2006.

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

18 of 92

LPL (B-MAC) and X-MAC are transmitter initiated MAC protocols

Receiving nodes continuously periodically sample the wireless channel

When they detect a transmission they listen to receive packets

Transmitting nodes are only active when they want to transmit
Receiving nodes prone to unnecessary wakeups

Have to receive all nearby transmissions to see if the packet happens to be for them
Unnecessary wakeups lead to increasing receive energy 🡪 shorter lifetime
In general, difficult for receiver to know if it should stay awake or go back to sleep

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

19 of 92

Low Power Probing (LPP) is receiver initiated

Method

Receiver periodically transmits a probe, listens afterward
Transmitter listens for probe packet from intended recipient
Transmitter sends packet after receiving the correct probe packet

Koala: Ultra-Low Power Data Retrieval in Wireless Sensor Networks. Razvan Musaloiu-E., Chieh-Jan Mike Liang, Andreas Terzis. IPSN 2008.

TX Probe

Receiver

Transmitter

Sleep

TX ACK

RX ACK

TX Probe

RI-MAC: A Receiver-Initiated Asynchronous Duty Cycle MAC Protocol for Dynamic Traffic Loads in Wireless Sensor Networks. Yanjun Sun, Omer Gurewitz, David B. Johnson. SenSys 2008.

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

20 of 92

LPP introduces a new challenge for multiple nodes. What happens with multiple transmitters?

If multiple transmitters receive a probe, and they both want to transmit, it leads to a collision and a lost packet
Receiver is unsure if there actually was a packet, or just noise/interference on the channel

TX Probe

Receiver

Transmitter

Sleep

TX Probe

Transmitter

Sleep

Collision!!

Koala: Ultra-Low Power Data Retrieval in Wireless Sensor Networks. Razvan Musaloiu-E., Chieh-Jan Mike Liang, Andreas Terzis. IPSN 2008.

RI-MAC: A Receiver-Initiated Asynchronous Duty Cycle MAC Protocol for Dynamic Traffic Loads in Wireless Sensor Networks. Yanjun Sun, Omer Gurewitz, David B. Johnson. SenSys 2008.

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

21 of 92

A-MAC resolves this with backcast�(“constructive interference”, i.e., coherent combining)

Method

Transmitters send an ACK in response to a probe packet
With multiple transmitters, the ACKs collide, but interfere non-destructively, so the receiver still receives an ACK
The receiver stays awake to receive a packet, but the packet collides
The receiver sends a new probe, informing transmitters there was a collision
Transmitters use CSMA/CA to send packets [Recall, random initial backoff 0–7 slots]

TX Probe

Receiver

Transmitter

Sleep

TX ACK

TX Probe

RX ACK

Transmitter

Sleep

TX ACK

Collision!!

Design and Evaluation of a Versatile and Efficient Receiver-Initiated Link Layer for Low-Power Wireless. Prabal Dutta, Stephen Dawson-Haggerty, Yin Chen, Chieh-Jan Mike Liang, and Andreas Terzis. SenSys 2010.

TX Probe

CCA

Listen

TX ACK

CCA

TX ACK

RX ACK

Sleep

Listen

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

22 of 92

Summary: asynchronous low power MAC protocols

Transmitter initiated protocols

Receivers periodically sample the channel
Transmitters transmit sufficiently to ensure recipients heard
Examples: LPL, X-MAC
Pros:

Simple, intuitive
Can balance TX and RX energy with sample interval

Cons:

Receivers prone to false wake-ups
High idle listening energy costs

Receiver initiated protocols

Receivers periodically transmit probes
Transmitters listen for a probe before sending a packet
Examples: RI-MAC, Koala, A-MAC
Pros:

Fixed, small listening energy cost for receivers

Cons:

Multiple transmitters leads to collisions

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

23 of 92

Outline

Low-Power MAC Design

Simple Routing

Mesh Routing

Flooding

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

24 of 92

Routing goals

Have a packet, have a destination, how do we connect them?

Simple techniques

Broadcast, tree structures

Mesh techniques

Understand the available routes and select a “good” one

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

25 of 92

Refresher: Simple routing solutions

Broadcast

The link-layer solution for everything
Range: Limited to one “broadcast domain” (all nodes must be physically close)
Burden: Naïve version assumes everyone is always listening

Star topology

Only one location to send to: parent
Single parent needs to store information about all children

Addresses, schedules, etc.

Range: All nodes must be in range of the parent (but not necessarily each other)
Burden: The parent must participate in every packet; listen often for new arrivals

Tree topology

“Star of stars”
Two choices: send to descendent or send to parent
Each parent needs to store information about all children beneath it

Original ZigBee approach (knowledge built into addressing scheme)

Range: Works as long as a node is within one hop of any other node
Burden: “Higher” parents see more traffic; everyone must listen for new arrivals

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

26 of 92

Refresher: Simple routing solutions

Broadcast

The link-layer solution for everything
Range: Limited to one “broadcast domain” (all nodes must be physically close)
Burden: Naïve version assumes everyone is always listening

Star topology

Only one location to send to: parent
Single parent needs to store information about all children

Addresses, schedules, etc.

Range: All nodes must be in range of the parent (but not necessarily each other)
Burden: The parent must participate in every packet; listen often for new arrivals

Tree topology

“Star of stars”
Two choices: send to descendent or send to parent
Each parent needs to store information about all children beneath it

Original ZigBee approach (knowledge built into addressing scheme)

Range: Works as long as a node is within one hop of any other node
Burden: “Higher” parents see more traffic; everyone must listen for new arrivals

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

27 of 92

Refresher: Simple routing solutions

Broadcast

The link-layer solution for everything
Range: Limited to one “broadcast domain” (all nodes must be physically close)
Burden: Naïve version assumes everyone is always listening

Star topology

Only one location to send to: parent
Single parent needs to store information about all children

Addresses, schedules, etc.

Range: All nodes must be in range of the parent (but not necessarily each other)
Burden: The parent must participate in every packet; listen often for new arrivals

Tree topology

“Star of stars”
Two choices: send to descendent or send to parent
Each parent needs to store information about all children beneath it

Original ZigBee approach (knowledge built into addressing scheme)

Range: Works as long as a node is within one hop of any other node
Burden: “Higher” parents see more traffic; everyone must listen for new arrivals

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

28 of 92

Refresher: Simple routing solutions

Broadcast

The link-layer solution for everything
Range: Limited to one “broadcast domain” (all nodes must be physically close)
Burden: Naïve version assumes everyone is always listening

Star topology

Only one location to send to: parent
Single parent needs to store information about all children

Addresses, schedules, etc.

Range: All nodes must be in range of the parent (but not necessarily each other)
Burden: The parent must participate in every packet; listen often for new arrivals

Tree topology

“Star of stars”
Two choices: send to descendent or send to parent
Each parent needs to store information about all children beneath it

Original ZigBee approach (knowledge built into addressing scheme)

Range: Works as long as a node is within one hop of any other node
Burden: “Higher” parents see more traffic; everyone must listen for new arrivals

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

29 of 92

Refresher: Simple routing solutions

Broadcast

The link-layer solution for everything
Range: Limited to one “broadcast domain” (all nodes must be physically close)
Burden: Naïve version assumes everyone is always listening

Star topology

Only one location to send to: parent
Single parent needs to store information about all children

Addresses, schedules, etc.

Range: All nodes must be in range of the parent (but not necessarily each other)
Burden: The parent must participate in every packet; listen often for new arrivals

Tree topology

“Star of stars”
Two choices: send to descendent or send to parent
Each parent needs to store information about all children beneath it

Original ZigBee approach (knowledge built into addressing scheme)

Range: Works as long as a node is within one hop of any other node
Burden: “Higher” parents see more traffic; everyone must listen for new arrivals

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

30 of 92

Refresher: Simple routing solutions

Broadcast

The link-layer solution for everything
Range: Limited to one “broadcast domain” (all nodes must be physically close)
Burden: Naïve version assumes everyone is always listening

Star topology

Only one location to send to: parent
Single parent needs to store information about all children

Addresses, schedules, etc.

Range: All nodes must be in range of the parent (but not necessarily each other)
Burden: The parent must participate in every packet; listen often for new arrivals

Tree topology

“Star of stars”
Two choices: send to descendent or send to parent
Each parent needs to store information about all children beneath it

Original ZigBee approach (knowledge built into addressing scheme)

Range: Works as long as a node is within one hop of any other node
Burden: “Higher” parents see more traffic; everyone must listen for new arrivals

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

31 of 92

Refresher: Simple routing solutions

Broadcast

The link-layer solution for everything
Range: Limited to one “broadcast domain” (all nodes must be physically close)
Burden: Naïve version assumes everyone is always listening

Star topology

Only one location to send to: parent
Single parent needs to store information about all children

Addresses, schedules, etc.

Range: All nodes must be in range of the parent (but not necessarily each other)
Burden: The parent must participate in every packet; listen often for new arrivals

Tree topology

“Star of stars”
Two choices: send to descendent or send to parent
Each parent needs to store information about all children beneath it

Original ZigBee approach (knowledge built into addressing scheme)

Range: Works as long as a node is within one hop of any other node
Burden: “Higher” parents see more traffic; everyone must listen for new arrivals

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

32 of 92

Refresher: Simple routing solutions

Broadcast

The link-layer solution for everything
Range: Limited to one “broadcast domain” (all nodes must be physically close)
Burden: Naïve version assumes everyone is always listening

Star topology

Only one location to send to: parent
Single parent needs to store information about all children

Addresses, schedules, etc.

Range: All nodes must be in range of the parent (but not necessarily each other)
Burden: The parent must participate in every packet; listen often for new arrivals

Tree topology

“Star of stars”
Two choices: send to descendent or send to parent
Each parent needs to store information about all children beneath it

Original ZigBee approach (knowledge built into addressing scheme)

Range: Works as long as a node is within one hop of any other node
Burden: “Higher” parents see more traffic; everyone must listen for new arrivals

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

33 of 92

Many variations, e.g., “Many-to-one routing”�e.g. Collection Tree Protocol (CTP)

Tree optimization for sensor networks

Keep all devices except the “gateway” as simple as possible

Each device only needs to remember hop to gateway

If gateway wants to send message back, it must include a full hop path

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

34 of 92

Outline

Simple Routing

Mesh Routing

Efficient Flooding (Synchronous Transmissions)

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

35 of 92

Refresher: Mesh networks

Most devices can communicate with multiple neighbors

What are advantages of mesh?

Devices can communicate over longer distances
Device failures less likely to collapse the entire network

What are disadvantages of mesh?

Some nodes must spend more energy communicating
Network protocol becomes more complicated to manage routing

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

36 of 92

Enabling full mesh networks

All nodes:

Can send and receive data
Route and forward data in the network

Nodes connect with their neighbors
Gateway provides access to other networks/internet
We’re interested in meshes that

Use low power nodes (battery powered)
Are low data rate with small packets

802.15.4 provides a foundation to build mesh on top of:

Contention Access Period

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

37 of 92

Mesh network layers

PHY Layer

802.15.4 physical layer

MAC Layer: 802.15.4

802.15.4 spec gives us the option of implementing our own
Technically this layer is here, but we generally ignore it

MAC Layer

Need to allow to TWO low power devices to communicate
Devices are off most (~99%) of the time
No assumption of energy asymmetry (as with PAN coordinator or BLE)

Network Layer: Mesh

Handles organizing the network
How should packets travel from nodes to the gateway?
How should packets travel from the gateway to nodes?
How should packets travel from node to node?

PHY Layer�O-QPSK - 2.4 GHz

MAC Layer�Low Power

Network Layer�Mesh Routing

802.15.4 Contention MAC

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

38 of 92

Quantitative intuition of ‘why bother meshing’

Image: https://www.sciencedirect.com/topics/computer-science/transmitting-antenna

Traditionally written as transmit distance

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

39 of 92

A hand-wavy quantitative analysis of ‘why bother meshing’

Revelle Plaza is ~40m wide; how to get from one side to the other?

0 dBm

1 mW

-72 dBm (6.3e-8 mW)

-68 dBm (1.6e-7 mW)

-5.2 dBm

0.3 mW

Multi-hop mesh…

Reduces TX power

But adds RX, sync cost!

Improves aggregate network coverage
Can improve robustness
Reduces collision domain

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

40 of 92

Outline

Simple Routing

Mesh Routing

Motivation
Example Protocols

Efficient Flooding (Synchronous Transmissions)

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

41 of 92

Mesh Routing

Mesh topology makes routing question more complicated

Multiple hops in a route
Multiple routes between source and destination
Becomes a graph theory question based on cost metric

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

42 of 92

Naïve “routing” via flooding

Mesh equivalent of broadcast

Each node sends to each other node
Eventually packets will reach the desired destination
Not really routing at all…

Question: how do we make it stop?

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

43 of 92

Naïve “routing” via flooding

Mesh equivalent of broadcast

Each node sends to each other node
Eventually packets will reach the desired destination
Not really routing at all…

Question: how do we make it stop?

Maximum retransmissions counter on each packet

Decrement at each hop. Drop packet when it hits zero
Need some guess for how many hops to destination�

Keep some history of recently flooded packets

Don’t retransmit a recently sent packet

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

44 of 92

Reactive routing

Build up a map of the routes through a network

Hopefully the “optimal” routes

Map routes in reaction to a packet arrival

Sensor devices are slow and limited
Most likely to resend to same prior address
Discover a route when it is needed, then cache for next time

B Neighbor Table
A	c7:e3:45:00:1f:e4
C	c7:e3:45:ab:44:c6
D	54:99:10:aa:b1:c3

B Forwarding Table
DST	Next Hop
F	C
A	A

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

45 of 92

Neighbor discovery

Which nodes are nearby to me?

i.e. within one packet transmission range

General Techniques

Periodically listen for nearby transmissions

Overhear packets
Source addresses indicate neighbors

Periodically send neighbor discovery probes

Announce your existence
Ask for neighbors to respond

Centrally collect neighbor information

Gateway disseminates to nodes as needed

B Neighbor Table
A	c7:e3:45:00:1f:e4
C	c7:e3:45:ab:44:c6
D	54:99:10:aa:b1:c3

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

46 of 92

Ad-hoc On-demand Distance Vector Routing (AODV)

On-demand: Construct routes only when needed
Modern ZigBee routing approach (for Mesh topology)

Routing table

Destination node -> Next hop (for all cached destinations)
Store only next hop instead of full route

All routers along the path must also have Destination->Next mappings

Also keep hops-to-destination and last-seen-destination-sequence-number

Route discovery

Upon demand: check table
If not cached send Route Request (RREQ) via Flooding

Route is unknown, so flooding is needed

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

47 of 92

AODV Route Requests (RREQs)

Request ID identifies this RREQ

Used to discard duplicates during flooding

Sequence Numbers are per-device, monotonically increasing

Used as a notion of “how recently” device has been seen
Source SeqNo is the source’s most recent sequence number
Destination SeqNo is the most recently seen from the destination by the source. (Defaults to zero)

Hop Count is the number of hops this request has taken

Starts at 1 and incremented by each transmitter along the path

Request ID	Source Address	Destination Address	Source SeqNo	Destination�SeqNo	Hop Count

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

48 of 92

Example AODV RREQ (A to F)

Request ID	Source Address	Destination Address	Source SeqNo	Destination�SeqNo	Hop Count

A wants to find a route to F, so it sends out an RREQ

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

49 of 92

Example AODV RREQ (A to F)

Request ID	Source Address	Destination Address	Source SeqNo	Destination�SeqNo	Hop Count
1	A	F	1	0	1

B and D also opportunistically add a routing table entry for A

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

50 of 92

Example AODV RREQ (A to F)

Request ID	Source Address	Destination Address	Source SeqNo	Destination�SeqNo	Hop Count
1	A	F	1	0	2

B goes first via some access control protocol (D also in contention)

A and D ignore duplicate Request ID�C opportunistically adds a routing table entry to A

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

51 of 92

Example AODV RREQ (A to F)

Request ID	Source Address	Destination Address	Source SeqNo	Destination�SeqNo	Hop Count
1	A	F	1	0	2

D goes next by some access control protocol (C also in contention)

A, B, and C ignore duplicate Request ID�E and F opportunistically adds a routing table entry to A

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

52 of 92

Example AODV RREQ (A to F)

Request ID	Source Address	Destination Address	Source SeqNo	Destination�SeqNo	Hop Count
1	A	F	1	0	3

C and E repeat this process with Hop Count 3 (but everyone ignores them)

They go one-at-a-time, but I’m getting tired of drawing these
Actually, they’re in contention with the response from F

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

53 of 92

AODV Route Response (RREP)

Reply is sent unicast back to the source via newly constructed route

Each node along the way already knows the route back

Includes most recent destination sequence number as a sense of recency

No need for source sequence number anymore

Source Address	Destination Address	Destination�SeqNo	Hop Count

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

54 of 92

Example AODV RREP (F to A)

Source Address	Destination Address	Destination�SeqNo	Hop Count
F	A	7	2

F sends response back to A via D

D opportunistically adds a routing table entry for F

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

55 of 92

Break + Practice

C wants to send a packet to E

What RREQ(s) are sent and what RREP(s) are sent?

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

56 of 92

Break + Practice

C wants to send a packet to E

What RREQ(s) are sent and what RREP(s) are sent?

RREQs:

C -> (B,D,F)
(B or D) -> A
(D or F) -> E

RREPs:

E -> (D or F) -> C

Network could have multiple configurations

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

57 of 92

RREP optimization

An intermediate node responds with RREP if it has a path to destination with a more recent Destination sequence number

Source may get multiple RREP responses with different recency and hop counts

Note: we’re optimizing for some combination of most recent and lowest hop count

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

58 of 92

When to update your route

Routing table entries are updated on RREP if:

Sequence number in routing table is marked as invalid�
Destination sequence number in the RREP is greater the listed one�
Sequence numbers are the same, but the route was marked as inactive�
Sequence numbers are the same, but the hop count is smaller

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

59 of 92

Route maintenance in AODV

If a link in the routing table breaks, all active neighbors are informed with Route Error (RERR) messages

After some number of retransmissions and timeouts
RERR contains destination address that broke

Nodes receiving RERR can start RERQ for destination address

Which lets them find a new path through the network
And updates everyone’s cached next-hops

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

60 of 92

Dynamic Source Routing (DSR)

Another reactive routing technique

Similar design as AODV

In DSR, routing tables have full route to destination

Each packet transmission includes a list of hops to destination
So the route to an important destination only has to be stored on the source device that cares about it
Intermediate nodes do not need any route storage for that destination

Cost is extra bytes used in each packet for route

During discovery, all paths are returned by destination

So source gets a full list of possible route choices

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

61 of 92

Tradeoffs for reactive routing

Upside: no transmissions unless there is demand

Routes might appear, disappear, reappear, but no need to update if no one actually wants to transmit anything

Downside: large, variable delay when actually sending a packet

Full RREQ/RREP protocol before data can actually be sent
Route might have broken at some point

So data will be sent based on cached information
RERR will occur
RREQ/RREP will occur
Then data will be sent again

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

62 of 92

Proactive routing

Alternative to reactive is to know the routes ahead of time

Periodically query for the possible routes in the network

Save all routes that are important (maybe just all routes?)
Also redetermine routes whenever topology changes (nodes join/leave)

Upside: when a packet arrives, route to destination is already known

Downside: requires more memory and effort on part of routers

Wastes some network bandwidth on checking for route changes

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

63 of 92

Distance-Vector

Keep routes as “next hops” rather than full routes

AODV uses this method (DV for Distance Vector)

Can be combined with proactive techniques too

Each router periodically informs neighbors of its shortest paths to each destination (in terms of hop count)

Essentially just broadcast your routing table

Routers choose the best route available

Old next-hop it was already aware of
New next-hop through neighbor (with cost of their hops + 1)

Need to be careful to avoid loops!

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

64 of 92

Preview: Thread routing

Uses a proactive, distance-vector protocol for unicast routing

If node is a child, send packet to parent router

If node is a router,

Consult table for address within mesh

(RLOC helps here!)

Send to border router for address outside of mesh

Multicast uses a data dissemination protocol (Trickle)

Or falls back to flooding

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

65 of 92

Break + Discussion

Hop count is one possible metric for determining routes
What else might be considered?

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

66 of 92

Reliability as a cost metric

Link quality can very from node to node

Fewest hops might not be the “fastest” or “most reliable” path

ETX: minimize “expected transmissions”

Measure link quality over time to determine each link’s reliability

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

67 of 92

Alternative cost metrics

Spatial reuse

Prefer transmission on links that do not interfere with each other
Improves ability to pipeline data through network
Example: A<->B and E<->F

Energy availability

Prefer routing through nodes with more remaining�available energy
Prefer wall-powered nodes over battery-powered

Arbitrarily complex combinations possible

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

68 of 92

Outline

Simple Routing

Mesh Routing

Efficient Flooding (Synchronous Transmissions)

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

69 of 92

Traditional flooding is a ’mesh-local broadcast’

Goal: get information to all nodes

This is the problem of “data dissemination”

Problem: difficult in Mesh topologies

Packet loss, retransmission delays

Really, the desire for data dissemination is just to broadcast to all nodes

But broadcast transmissions don’t reach far enough to cover entire mesh

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

70 of 92

Glossy: What if we expand broadcast range by having multiple nodes participate?

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

71 of 92

Glossy foundations: A-MAC and Backcast

A little while back, we mentioned that A-MAC allowed (relied on!) “interfering packets”
I.e., concurrent transmissions of ACKs

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

72 of 92

Fundamental Insight: Say exactly the same thing at exactly (enough) the same time 🡪 coherence not interference

In 802.15.4, an ACK is sent exactly 192 µs after receiving

The ACK packet contains only the sequence number being ACK’d
Does not contain source address of the ACK-er
Which is why this works:

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

73 of 92

Synchronous transmissions extend this concept beyond ACKs to arbitrary packets (with data)

Multiple nodes transmit same packet at same time

R can receive packet with high probability if Δ is small

May even improve probability of reception (more energy at receiver)

500 ns is 1/32 of a symbol for 802.15.4 (chip duration)

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

74 of 92

Glossy key techniques

Temporally decouple network flooding from application tasks

Exploit synchronous transmissions for fast network flooding

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

75 of 92

Fast packet propagation in Glossy

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

76 of 92

Intuition behind flooding…

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

77 of 92

GO!

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

78 of 92

TRITONS!

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

79 of 92

GO!

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

80 of 92

Fast packet propagation in Glossy

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

81 of 92

Fast packet propagation in Glossy

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

82 of 92

Fast packet propagation in Glossy

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

83 of 92

Glossy details

When Glossy starts

All nodes turn on radios to receive

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

84 of 92

Glossy details

Initiator

Set relay counter in packet, C = 0
Broadcast packet

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

85 of 92

Glossy details

At packet reception:

Increment relay counter C
Transmit synchronously (at a fixed period after the reception)

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

86 of 92

Glossy details

At packet reception:

Increment relay counter C
Transmit synchronously (at a fixed period after the reception)

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

87 of 92

Glossy details

Stop rebroadcasting and turn off radio when

Already transmitted N times
Networks pick N for reliability/energy tradeoff

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

88 of 92

Glossy details

T_slot is constant by design

Needs to be to make constructive interference work

Beginning of slot (t_ref) provides synchronization point

As a bonus, all nodes are synchronized after flooding event

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

89 of 92

Glossy implementation

Device must be able to have tight time bounds on rx/tx

500 ns wiggle room maximum
Includes receive, processing, transmission

Need to pick an N for reliability

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

90 of 92

Extreme application of Glossy: Avoid routing altogether

Low-Power Wireless Bus (LWB)

Federico Ferrari, Zimmerling, Mottola, Thiele. SenSys’12

Use Glossy floods for all communication

Make one broadcast domain (a bus) where all nodes communicate
Avoids all issues of routing, everything is a broadcast

Works for unicast, multicast, anycast, and broadcast transmissions

General idea: TDMA Glossy floods

Synchronization is already given to nodes by Glossy
One coordinator makes the TDMA schedule

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell

91 of 92

Implications of Flooding

Synchronous Transmission Protocols were a major disruption

Showed that flooding data from A 🡪 F used less net energy than routing A 🡪 F

(Net here is energy consumed by all nodes in the network)

Why??

What kinds of applications, traffic patterns would synchronous transmissions be worse than routing for?

CSE 122/222C ; WES 269 [WI25]

CC BY-NC-ND Pat Pannuto – Content developed in coordination with Branden Ghena and Brad Campbell