Internet of Things

Cycle 3: IoT Protocols

UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN
What Are IoT Networks
What Are IoT Networks
We Can Make Individual Devices Now
• We can send data using wireless signals
• That’s not enough
• Need to communicate reliably, need to interpret bits, need to track who
I’m communicating with, need to discover who is there, etc.
• We need to perform more functions atop this communication
• We need protocols
• Next, I will talk about IoT protocols
• First, the challenges
• Next, some approaches/algorithms we can use
• Finally, I’ll talk about some specific ones
Challenges We Need to Deal With
1. How to send information without wires?
• Solution: Radio Frequency Communications

2. How to share the channel?

• Solution: Media Access Control (MAC)

3. How to communicate across multiple hops?

• Solution: Mesh Routing and Service Discovery
Roadmap
• Part 1: Intro to RF
• Part 2: Antenna Design and Operations
• Part 3: Signal Propagation
• Part 4: Encoding, Modulation, and Channel Sharing
• Part 5: IoT Communication Protocols
Radio Frequency
Communications
 1. Electromagnetism theory
 What is RF?

Radio Frequency 2. Antenna design

 How can we send RF?
Communications 3. Signal propagation
 How do wireless signals
propagate?

4. Modulation
 How do we encode data on RF?
What is light?
 What is light?
Lower Higher
frequency frequency
 What is light?
Lower Higher
frequency frequency

Infrared Visible light Ultraviolet

 The Electromagnetic Spectrum
(micron/
longer (km) (m) (cm) (mm) micrometer) (nm) shorter

Wavelength 103 102 101 1 10-1 10-2 10-3 10-4 10-5 10-6 10-7 10-8 10-9 10-10 10-11 10-12
(in meters)

Common name
of wave ULTRAVIOLET

VISIBLE
INFRARED

Frequency lower higher

(waves per
second)
106 107 108 109 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020
(MHz) (GHz) (THz)
 The Electromagnetic Spectrum
(micron/
longer (km) (m) (cm) (mm) micrometer) (nm) shorter

Wavelength 103 102 101 1 10-1 10-2 10-3 10-4 10-5 10-6 10-7 10-8 10-9 10-10 10-11 10-12
(in meters)

Size of
Wavelength Soccer
House
field Baseball Bee Animal Bacteria Virus Water
Cell Molecule

Common name
of wave ULTRAVIOLET “HARD” X-RAYS

VISIBLE
INFRARED

MICROWAVES “SOFT” X-RAYS GAMMA RAYS

Frequency lower higher

(waves per
second)
106 107 108 109 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020
(MHz) (GHz) (THz)
Can we use EM waves to communicate?

• Observation: We can “encode” information by sending

an EM source and varying properties of it
• Brightness, color, etc.

• Key question: Which frequency should we use?

• EM radiation acts differently at different wavelengths
EM Radiation Acts Differently at Different
Wavelengths
• Higher frequencies are more dangerous to humans

• High and low frequencies tend to go through objects

• IR, optical, and UV tend to be dissipated by air and building
materials

• Lower and middle frequencies are easier to make and

precisely control with circuits
What frequencies should we use?
• [same as previous slide but animate in what parts aren’t useful
for various reasons]
 The Electromagnetic Spectrum
(micron/
longer (km) (m) (cm) (mm) micrometer) (nm) shorter

Wavelength 103 102 101 1 10-1 10-2 10-3 10-4 10-5 10-6 10-7 10-8 10-9 10-10 10-11 10-12
(in meters)

Size of
wavelength Soccer
House
field Baseball Bee Animal Bacteria Virus Water
Cell Molecule

Common name
of wave ULTRAVIOLET “HARD” X-RAYS

VISIBLE
RADIO WAVES INFRARED

MICROWAVES “SOFT” X-RAYS GAMMA RAYS

Frequency longer Good for communication shorter

(waves per
second)
106 107 108 109 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020
(MHz) (GHz) (THz)
• Radio frequency: 3kHz to 300GHz
• Easy to generate, good propagation characteristics, relatively safe for people
How to generate EM waves?
• Need some way to generate them, controllably
• At specific frequencies, with certain patterns to encode data

• Observation: Electricity in a wire produces EM field

Magnetic Field Induces Current Flow

• This can be bad (crosstalk)

• This can be good (can transmit data)
We Can Use EM Leakage to Transmit Data

• Idea: Modulate electricity through wire

• Change modulation to encode information
• Bend wires to improve signal strength (dipole)
How to modulate electricity?
• We can make electrical components, which can manipulate
electricity

Resistor Oscillator Filter Amplifier

• We can combine these components into “circuits”

• Circuits that operate on radio frequencies are called RF circuits
 RF Transmitter Architecture

Digital Information
110101101 Antenna

Modulator Upconversion Amp.

101010101010101010101010101010

0 1 0 1 0 101010101010101010101010101010
 RF Transmitter Architecture

Digital Information
110101101 Antenna

Modulator Upconversion Amp.

0 1 0 1 0

0 1 0 1 0 0 1 0 1 0
RF Transmitter Architecture

Modulator Upconversion Amp.

 RF Transmitter Architecture
Digital Information
110101101 Antenna

Mixer

Modulation Pulse DAC LPF BPF PA

shaping

PLL

Modulation Upconversion Amplification

 RF Transmitter Architecture
Digital Information
110101101 Antenna

Mixer

Modulation Pulse DAC LPF BPF PA

shaping

PLL

Modulation Upconversion Amplification

 RF Transmitter Architecture
Digital Information
Antenna Antenna 110101101

Mixer

LNA BPF LPF Channel Demodulation

ADC
Equalization

PLL

on Amplification Downconversion Demodulation

We Can Use EM Leakage to Transmit Data

• Electronic oscillator generates alternating current at a

frequency (carrier signal)
• Rate of oscillation: Wavelength of signal
• Information is piggybacked by modulating carrier signal
• Bandpass filter used on receiver to extract information signal
Can We Use EM Waves to Communicate?
• Solution: Use low frequencies
• Radio Frequency: 3 kHz to 300 GHz
• Easy to generate, good propagation characteristics, relatively safe for
people

• Challenge: Low bandwidth of available frequencies

• Visible spectrum is 2 million GhZ wide!
• Takes more time to send data

•  Need smart ways to pack information into that bandwidth

• Modulation, channel sharing, frequency allocation
• [draw rf spectrum – talk about properties and why things are in
different locations on it]
• [foreshadow iot – diff wireless protocols are in diff locations
there for those reasons]
 1. Electromagnetism theory
 What is RF?

Radio Frequency 2. Antenna design

 How can we send RF?

Communications 3. Signal propagation

 How do wireless signals
propagate?

4. Modulation
 How do we encode
data on RF?
“Polarization” of EM Waves

• Signals are “polarized” in direction of current flow

• Receiver antenna orientation must match that of transmitter
Polarization Options
Antenna Placement for Polarization

• You don’t know how your users are polarized  propagate signals
for both
• Some APs propagate two polarizations
• Can manually configure antennas
• Also covers vertical and horizontal space
Radiation Patterns
Radiation Patterns

Omnidirectional Multidirectional Directional

• Light sources can transmit different amounts of intensity in different

directions
• Same can happen for antennas
Antenna Types: Omnidirectional

• Radiates equally in all directions in one plane

• Power decreases above/below plane
• Widely used in APs, NICs
Antenna Types: Directional (Yagi)

• Multiple parallel elements in a line

• Substantial increase in directionality and gain
Antenna Types: Directional (Parabolic)

• Reflector must be substantially larger than wavelength

• Metal screen reflects as well as solid dish if spaces < 1/10
wavelength
How to Choose an Antenna
• Directionality: Do you want to light up a particular area, or entire
surrounding region?

• Gain: How much “reach” the antenna has compared to an

omnidirectional antenna

• Bandwidth: Range of frequencies over which the antenna

operates effectively
 1. Electromagnetism theory
 What is RF?

Radio Frequency 2. Antenna design

 How can we send RF?

Communications 3. Signal propagation

 How do wireless signals
propagate?

4. Modulation
 How do we encode
data on RF?
Signal Propagation
What happens to radio waves between antennas?

1. They lose energy as they propagate out (path loss)

2. They get deflected when they hit objects (reflection)

3. They bounce off things and then recombine

(multipath/fading)
Free Space Propagation
PR
• Propagation from idealized r
(isotropic) antenna is a sphere
• Power density (PR is transmit power
PT divided by surface area)
PT
• PR= PT / (4πr2)

• If transmitting antenna has gain

GT, receiving antenna has gain GR
• Then power density increases by the
product of the gains GT GR
• PR= GT GR PT / (4πr2)
• Known as the Friis Transmission
Equation PT
r
PR
Path Loss Effects

• Wireless signals are like light

• Just a different wavelength along EM spectrum
• They interact with physical objects in similar ways
• Can be bad – can degrade signal
• Can be good – can leverage this to improve signal strength/range
Path Loss Effects
Wireless Signals Propagate Like Waves

• Propagate at speed of light in vacuum

• Propagation speed independent of wavelength
• Matching wavelengths construct, opposing wavelengths destruct
Wireless Signals Can Self-Interfere

• Could be a good thing, if they construct

• Could be a bad thing, if they destruct
Frequency Affects Propagation
• Low frequencies (long wavelengths):
• Diffract around objects, can follow curvature of earth
• Can penetrate through objects (e.g., ground, water)
• Require bigger antennas

• High frequencies (short wavelengths):

• Act more like light
• Can be “focused” (parabolic antennas)
• Attenuate more in air; increased scattering by objects, rain
 The Electromagnetic Spectrum
(micron/
longer (km) (m) (cm) (mm) micrometer) (nm) shorter

Wavelength 103 102 101 1 10-1 10-2 10-3 10-4 10-5 10-6 10-7 10-8 10-9 10-10 10-11 10-12
(in meters)

Size of
wavelength Soccer
House
field Baseball Bee Animal Bacteria Virus Water
Cell Molecule

Common name
of wave ULTRAVIOLET “HARD” X-RAYS

VISIBLE
RADIO WAVES INFRARED

MICROWAVES “SOFT” X-RAYS GAMMA RAYS

Frequency longer Good for communication shorter

(waves per
second)
106 107 108 109 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020
(MHz) (GHz) (THz)
• Radio frequency: 3kHz to 300GHz
• Easy to generate, good propagation characteristics, relatively safe for people
 Atmospheric Attenuation (dB/km)

Fog

H2 O Excessive Rain
O2
Heavy Rain
O2

Drizzle
H2 O

Air

RADIO WAVES MICROWAVES INFRARED

ELF SLF ULF VLF LF MF HF VHF UHF SHF EHF THF

1 101 102 103 104 105 106 107 108 109 1010 1011 1012 1013 1014
(Hz) (kHz) (MHz) (GHz) (THz)
 RADIO WAVES INFRARED

MICROWAVES

106 107 108 109 1010 1011 1012 1013 1014

(MHz) (GHz) (THz)
Atmospheric Opacity
• To do: insert “super figure” showing content at
https://docs.google.com/spreadsheets/d/1BmFjVgib-
b9230IYtUptooMWMzhJLzSviCEjMgNM-zE/edit#gid=0
• Like show the range at the top then have several long figures
lengthways showing properties, eg atmospheric attenuation will
be flat at lower freqs I think and then have some spikes around
a few GHz.
Interference Changes with Distance from
Line-of-Sight Path

• Vertical distance decreases signal strength of secondary path

• Increasing vertical distance alternates between constructive and
destructive interference
Fresnel Zone

• Ellipsoid drawn between transmitter and receiver should be kept

clear from obstacles
• Heuristic: Max obstruction <40%, recommended <20%
Fresnel Zone Radius Computation

• Online calculator:
https://www.everythingrf.com/rf-calculators/fresnel-zone-calculator
How Physical Objects Affect Wireless
Signals
• Different materials affect
reflection/absorption/
refraction in different
ways

• Conduct wireless surveys

to understand
propagation in your
environment
Is attenuation good or bad?
 Example: Two APs
• What if not
enough
capacity?
 Example: Nine APs
• Problem:
Increased
transmitter
density
lowers
available
bandwidth
 Example: Nine APs
• More attenuation
better for dense
deployments
Atmospheric Attenuation in Wifi
Spectrum

• 802.11ad: 60 GHz chosen because of increased atmospheric attenuation

How Physical Objects Affect Wireless Signals
Attenuation from Water
• Snow, ice, lakes, aquariums, plumbing, animals, etc.
• 2.4GHz attenuation in water to 1/3 signal strength:
• Pure water: 8.01Km
• Drinking water: 44.54m
• Sea water: 8.91mm
• Humans similar to sea water
• More fatmore attenuation
• Trees: Leaves and rain increase attenuation
Increased Capacity with Spectrum Division

• 802.11 supports
different
“channels”/
wavelengths
• Put nearby APs
on different
wavelengths
General Problem: Graph Coloring
Channel 7 Channel 3
Channel 3

Channel 3
Channel 2 Channel 2

Channel 3
Channel 3
Channel 7 Channel 7

• Vertices are APs, edges denote reachability

• Number of channels/colors needed a function of graph
connectivity
Rules of Thumb for Transmitter
Deployment
• Try to use the same SSID when possible, to enable
automated roaming to the highest-quality AP
• APs that use the same channel should be installed as
far away from each other as possible to minimize
interference
• AP cell size should overlap by 15-25% to ensure that
there are no gaps in coverage and to ensure a
roaming client will always have a connection visible
 1. Electromagnetism theory
 What is RF?

Radio Frequency 2. Antenna design

 How can we send RF?

Communications 3. Signal propagation

 How do wireless signals
propagate?

4. Modulation
 How do we encode
data on RF?
How do we encode data in wireless
signals?
• Need to generate signals to transmit data
• Challenges:
• Low bandwidth
• Propagation channel impairments (noise, multipath,
interference, etc.)
• Simplicity/cost of hardware
• Remember that we send using a carrier signal
• Options for modulation: Amplitude, frequency, phase
Amplitude Shift Keying (ASK)
1 0 1 0 1
Amplitude Shift Keying (ASK)
1 0 1 0 1

• Vary signal strength to transmit information

• Ones/zeros represented by presence/absence of carrier
• Modulating amplitude creates “sidebands”
• Optimizations – carrier suppression, single-sideband suppression
• Pros: Cheap receivers (envelope detection)
• Cons: Amplifies noise, inefficient use of bandwidth and power usage
Frequency Shift Keying (FSK)

1 0 1 0 1
Frequency Shift Keying (FSK)
1 0 1

• Uses two carrier frequencies to represent binary 1 and 0

• Optimizations: Multiple FSK (groups of bits represented by multiple
frequency levels)
• Pros: Higher immunity of noise, robust to variation in attenuation, simple
implementation, “capture effect” completely suppresses weaker signals
• Cons: Larger bandwidth compared to ASK and PSK
Phase Shift Keying (PSK)

1 0 1 0
Phase Shift Keying (PSK) 90°

1 0 1 0
1 0
180° 0°

phase

270°

• Changes phase of carrier to convey data

• Pros: Power efficient, less susceptible to errors than ASK
• Cons: Can be complicated to implement, worse noise
rejection than FSK
Constellation Diagram
90°

1 0
180° 0°

amplitude

phase

270°
Constellation Diagram
90°

01

10 00
180° 0°

* amplitude

phase

Received bit mapped 11

to closest symbol

270°
Common Phase-Amplitude Modulations

On-Off Keying Binary Phase-Shift Keying 4-ASK

(OOK) (BPSK)

Quadrature Phase 8-PSK 16-Quadrature

Shift Keying Amplitude Modulation
(QPSK) (16-QAM)
 What do real IoT protocols use?

BPSK, QPSK,
Modulation ASK FSK QPSK
QAM

Frequencies 13.56MHz 2.4GHz 2.4GHz 5GHz

Bandwidth 424 Kbps 1-3 Mbps 250 Kbps 1.3 Gbps

 Wireless/IoT Protocols

BPSK, QPSK, QPSK, 16QAM,

Modulation FSK, PSK QAM, QPSK 64QAM
QAM
750, 850,
868MHz, 700, 1700,
Frequencies 900MHz 1700, 1900,
915MHz 1900 MHz
2300 MHz
3.1 Mbps 5-12 Mbps
Bandwidth 347 Mbps 27-50Kbps down, down, 2-5
1.8 Mbps up Mbps up
Wireless/IoT Protocols
Near-Field Bluetooth Zigbee 802.11ac CDMA 4G LTE
Communication (WiFi) (Verizon) (AT&T)
(NFC)
Modulation ASK FSK QPSK BPSK, QAM and QPSK QPSK,
QPSK, QAM 16QAM,
64QAM
Frequency bands 13.56MHz 2.4GHz 2.4GHz 5GHz 750, 850, 1700, 700,
1900, 2300 MHz 1700,
1900
MHz
Bit rate 424 Kbps 1-3 Mbps 250 1.3 Gbps 3.1 Mbps down, 5-12
Kbps 1.8 Mbps up Mbps
down, 2-
5 Mbps
up
Wireless MAC
 1. Collision detection and
resolution
 What if two nodes send

Wireless MAC at same time?

2. Power-saving algorithms
 What if a node transmits
but the destination is
sleeping?

3. Association and neighbor

discovery
 Who is out there?
How can wireless hosts share the
spectrum?

• What happens when two hosts transmit at the same time?

• Collision
• What should we do about collisions?
How to mitigate collisions?
1. Just let transmissions collide
• Problem: Data gets corrupted

2. Collision detection (CD)

• Let transmissions collide, but detect collisions
• If sender knows their packet collided, they can retransmit

3. Collision avoidance (CA)

• Try to prevent collisions
Collision Detection (CD): Wired Networks
0:022 Collision detected! Packet
transmission unsuccessful. Wait and 0:016 Collision detected! Start
retry. ignoring packet.
0:016 Collision detected! Start
0:000 Packet transmission ignoring packet. 0:008 Packet transmission
begins. begins.

Collision!
Collision Detection (Wired, Small Packets)
0:022 Finished transmitting packet
successfully!  Start transmitting 0:016 Collision detected! Start
next packet. 0:016 Collision detected! Start ignoring packet.
0:000 Packet transmission ignoring packet. 0:008 Packet transmission
begins. begins.

Collision!
Collision Detection, Wireless

0:000 Packet transmission 0:008 Packet transmission

begins -30dB
begins
(maximum
practically-
achievable
signal
strength)

-65dB (minimum
signal strength for
applications that
require reliable,
timely
delivery)
“Hidden Node” problem – device may be visible to an AP but not to other
-70dB (minimum
signal strength for
nodes communicating with that AP reliable delivery)
On top of that, most radios are functionally half-duplex
• Transmitted signal much louder than received signal, can’t hear collisions
 I just saw an
I just
ACK– saw a CTS –
whoever
Collision Avoidance (CA), Wireless someone
was
before
else
transmitting
was allocated
is done,the
so
I canchannel
send a –RTSI if
should
I need to not
send
transmit anything
packets.

ACK

Yes, XX:XX:XX:XX, you may transmit.

(Clear To Send / CTS)
Data Packet
Can I have the channel please? My
MAC address is XX:XX:XX:XX.
(Request To Send / RTS)
 1. Collision detection and
resolution
 What if two nodes send

Wireless MAC at same time?

2. Power-saving algorithms
 What if a node transmits
but the destination is
sleeping?

3. Association and neighbor

discovery
 Who is out there?
Batteryless Light Vibration Monitoring
Switch Sensor
Smart Clothing Grain Monitoring
 Can we be smart about managing power?
Component Power Usage
(approx.)
LTE Radio (transmitting at 1Mbps) 1700 mW
3G Radio (transmitting at 1Mbps) 1700 mW
WiFi Radio (transmitting at 1Mbps) 400 mW
ARM CPU+RAM (100% CPU utilization) 2000 mW
ARM CPU+RAM (idle) 70 mW
Smartphone Screen (100% brightness) 850 mW
GPS (after lock is acquired) 100-150mW
Accelerometer (10Hz) 75μW
• Idea: Shut down or idle
Image Sensor (1080p@30Hz)
parts of system to save power
270mW
• Challenge: Low-power mode may reduce functionality
or stop components from working
Problem: Power Usage
Component Power Usage • Many IoT devices
(approx.)
LTE Radio (transmitting at 1Mbps) 1700 mW
operate in energy-
3G Radio (transmitting at 1Mbps) 1700 mW
constrained
WiFi Radio (transmitting at 1Mbps) 400 mW
environments
ARM CPU+RAM (100% CPU utilization) 2000 mW • Idea: Shut down or idle
ARM CPU+RAM (idle) 70 mW parts of them to save
Smartphone Screen (100% brightness) 850 mW power
GPS (after lock is acquired) 100-150mW • Low-power mode may
Accelerometer (10Hz) 75μW reduce functionality or
Image Sensor (1080p@30Hz) 270mW stop components from
working
Saving Power:
More Complex Than Just Not Sending
• High power consumption even
when receiving and idling Function Power Usage
(approx.)
• Sleep mode allows most of Transmit 1.33 Watts
electronics to be turned off
• Can’t receive or send packets when Receive 0.97 Watts
sleeping
Idle 0.84 Watts
• MUCH lower power usage
Sleep 0.07 Watts
• Only protocols that use sleep
mode a lot can save a
significant fraction of power
 Saving Power:
More Complex Than Just Not Sending
• Entering/leaving sleep mode
takes time
• Takes a little time to “wake up”
• Circuits need some time to
stabilize

• So, need to plan carefully

about sleeping
• Can’t just replace idling with
sleeping
Example Use Case:
Cold Supply Chain Auditing
• Need to keep items cold during transport
• Vaccines, blood, insulin, medicine
• Food: Meat, vegetables, dairy, wine
• Chemicals and sensitive electronics
• Cold Chain: Temperature-controlled supply chain
• Ensures cold temperatures at every step of transport
process
• Critical for product effectiveness and consumer safety
• $200B market
Example Use Case:
Cold Supply Chain Auditing
• Suppose you want to build
an IoT Cold Chain Auditor
• Implemented as tag
attached to product
• Continually monitors
temperature
• Alarms when above threshold
• Periodically records samples
• Records and communicates
findings
Example Use Case:
Cold Supply Chain Monitoring
Temperature
sensor
0.013W
Cold Tracker • System on:
0mW
Device • 0.013+0.07+0.07+0.006+10+1700+150+100+20+50+150+0.07
Vibration • = 2180.66mW  5.5 minutes
sensor 0.070mW
0mW
Microcontroller • Deep sleep (emergency mode):
Humidity 20mW • 0+0+0+0+0+0+0+0+0+0+0+0.07
0.03mW
sensor 0.070mW 0mW • = 0.07mW  battery lifetime (<7.8 years)
0mW
• Sensors-only mode:
Light RAM
sensor 0.006mW 50mW • 0.013+0.07+0.07+0.006+0+0+0+0+0.03+0.01+0
0.01mW
0mW
0mW • = 0.199mW  41.8 days
Bluetooth Low • Sensors+[BLE on 10ms per hour]:
Energy NIC Storage (SD)
10mW • 0.013+0.07+0.07+0.006+[(10mW)*10/1000/60/60+(0.03mW)*(1
0.03mW
0mW
150mW
0mW
-10/1000/60/60)]+0+0+0+0.03+0.01+0
• = 0.229mW  36.4 days
LTE NIC
1700mW
Power
• Sensors+[BTE on 10ms per hour]+[GPS on 10 seconds
0.07mW
0mW
Management
per 3 hours]+[LTE on 50ms per 24 hours]:
GPS
• 0.013+0.07+0.07+0.006+[(10mW)*10/1000/60/60+(0.03mW)*(1
0.07mW
-10/1000/60/60)]+[(150mW)*10/3/60/60+(0.03mW)*(1-
150mW
0.08mW 10/3/60/60)]+[(1700mW)*50/1000/60/60/24+(0.03mW)*(1-
0mW 50/1000/60/60/24)]+0+0+0+0.03+0.01+0
Coin Cell Battery
USB (0.2 Wh)
• = 0.428mW  19.4 days
100mW
0mW
What happens if we send data to a device
that’s sleeping?

• It’s ok to go to sleep, but need to be awake when data is sent to

you
• Need some way to coordinate when/how nodes sleep
• Sleeping also breaks CSMA/CD and CSMA/CA
• Need some other way to coordinate channel acquisition
Idea: Synchronize Sleep/Wake Times
Z
Z
Z
C
Z Node A Active Sleep
Z
Z
A
Z Node B Active Sleep
Z
Z
B
Node C Active Sleep
Time

• All nodes wake up and go to sleep at the same time

• Agree on “active” time when data can be exchanged, sleep time when they
can sleep
• Amount/ratio of active/sleep time may be statically configured
• Goal may be to minimize active ratio
• Problem: How do nodes know when to wake up and go to sleep?
Idea: Tell Other Nodes When You Wake Up
Z
Z
Z
C
Z Node A B Active Sleep
Z
Z
A
Z Node B Sleep
Z
Z
B
Node C Sleep
Time

• Tell other nodes we are awake with “beacons”

• Protocol: Stay awake for some duration after you send a beacon
• Problem: What if other nodes are asleep when beacon is sent?
MAC Power Saving Algorithms
• Low-energy wireless MACs (e.g., IEEE 802.15.4) have power-
saving algorithms to deal with these challenges
• Two main kinds of algorithms:
• Beacon mode (synchronous)
• Main idea: Keep nodes in sync with beacons
• Examples: Beacon Tracking (BT), Non-beacon Tracking (NBT)
• Non-beacon mode (asynchronous)
• Main idea: Let nodes autonomously discover each other’s wake times
on demand
• Examples: Long Preamble Emulation (LPE/BMAC), Long Preamble
Emulation with Ack (LPEA/XMAC), Non-beacon Tracking Emulation
(NTE), Global Synchronization (GS/SMAC)
MAC Power Saving Algorithms
IEEE 802.15.4
(Zigbee, Z-Wave, 6LoWPAN, etc.)

Beacon Mode Non-beacon Mode

(synchronous) (asynchronous)

Non-beacon Tracking (NBT) Long Preamble Emulation (LPE)

Beacon Tracking (BT) Global Synchronization (GS)

Non-beacon Tracking (NBT)
• Asynchronous wakeup algorithm:
• Uses beacons, but doesn’t force nodes to continually listen
for them

• Each node periodically wakes up and beacons

• Stays awake for a bit after the beacon
• If another node has data to send, it stays awake till it hears
the beacon of the destination, then transmits
Non-beacon Tracking (NBT)
I am not sure if A is
awake. Let me wait till I Ack
A is from
hear a beacon awakeA now!
So now I can
before I send data.
send data.
Z Z Node A
Z
Z Z
Z
A B
Node B
Data Time
arrives!
Data
Data arrives

• Questions:
• How long to make active, sleep durations?
• How long does a node have to “wait” in active state?
Non-beacon Tracking (NBT ): Downsides
• What if beacons collide?
• Regular schedule  they’d continually collide
• Idea: Restart beaconing after random delay, if detect another node’s
beacon during active window
• Doesn’t always work: Collision may happen outside radio range (hidden
terminal)

• May have to wait a long time for other node to wake up

• For beacon interarrival time tbi , need to idle active on average tbi/2 to
receive destination beacon
MAC Power Saving Algorithms
IEEE 802.15.4
(Zigbee, Z-Wave, 6LoWPAN, etc)

Beacon Mode Non-beacon Mode

(synchronous) (asynchronous)

Non-beacon Tracking (NBT) Long Preamble Emulation (LPE)

Beacon Tracking (BT) Global Synchronization (GS)

Beacon Tracking (BT)
• Synchronous wakeup algorithm using superframe
structures
• No long blocks of idle listening for beacons

• Coordinator broadcasts beacons, which contain the

coordinator’s schedule
• Nodes store coordinator’s schedule and sync clock to beacon
arrival time
• Nodes try to receive next beacon by turning on their receiver
slightly before expected beacon transmission time
 Beacon Tracking
Z Ack
Z
Z
C
Z Node A
Z
Z
A
Z Node B
Z
Z
Coordinator B Data arrives
I know A is asleep.
But, I know exactly Node C
when it will wake up! Data
arrives!

• Issues:
• Synchronized clocks, increase hardware costs
• What if beacon can’t be heard by entire network (multihop network)?
What if beacon can’t be heard by entire
network (multihop network)?
• Solution: Other nodes
also send beacons
D

• Nodes “wake up” for

C
E
any beacons in their
A
broadcast region
Coordinator B
I

F
• 802.15.4: Nodes form
an “association tree”
G
H J
• Nodes wake up for
parents in tree
 Outgoing
active
Beacon Tracking: Multihop Case duration
Ack

D
Node A
(level i)
Data arrival (dest=A) Data
C
Node B
(level i+1)

A
Node C
(level i+1)
Coordinator B
Node D
(level i+2)

Incoming active duration

Each node
• Issue: Nodeshas active
have durations
to idle for incoming
listen every and outgoing
superframe duration even
beacons+data
if they have no data to send
Incoming:
• Also, Beaconsselection
coordinator from controller oneincreases
procedure level up complexity,
• synchronized clocksto
Outgoing: Beacons increase
childrenhw costs
one level down
MAC Power Saving Algorithms
IEEE 802.15.4
(Zigbee, Z-Wave, 6LoWPAN, etc)

Beacon Mode Non-beacon Mode

(synchronous) (asynchronous)

Non-beacon Tracking (NBT) Long Preamble Emulation (LPE)

Beacon Tracking (BT) Global Synchronization (GS)

Global Synchronization (GS)
Similar to Beacon Tracking, but:

1. No continuous beacons; instead, a SYNC message is

transmitted occasionally
2. Don’t need coordinators or tree; if a node doesn’t hear a SYNC
message for a while it broadcasts one
3. SYNC message can’t collide; CSMA/CA is used on them to
prevent that

Downsides: Requires more active time to receive a SYNC, clock

errors aggregated over multiple hops in mesh network
MAC Power Saving Algorithms
IEEE 802.15.4
(Zigbee, Z-Wave, 6LoWPAN, etc)

Beacon Mode Non-beacon Mode

(synchronous) (asynchronous)

Non-beacon Tracking (NBT) Long Preamble Emulation (LPE)

Beacon Tracking (BT) Global Synchronization (GS)

Long Preamble Emulation (LPE)
• Also known as B-MAC
• Non-beacon mode, asynchronous
• Nodes don’t send beacons at all
• Instead, nodes wake up on regular intervals
• Intervals are unsynchronized, but happen regularly
• So if I need to send a node data, I know it will wake up within a certain
amount of time
• Sender sends “write requests” until receiver would have woken
up, then sends data
• Receiver stays awake when it hears a write request, stays awake until
data is received
Long Preamble Emulation (LP)
Ack

Z Z Node A
Z
Z Z
Z
A B
Node B
I Ok,
don’tI have
knowbeen transmitting
if A is awake. But
IWRs
know forfor
twisure
timeitunits. NodeupA
will wake Wakeup interval (twi)
Write
*must* be receiving
within the them
next twi time now.
units! Request
I can transmit data now! Data arrives Data

• Nodes wake up every Wakeup interval (twi)

• When sender has data, it sends Write Requests for twi, then sends data
• When receiver gets a Write Request, it remains awake until data arrives
• Issue: Seems wasteful to send all those Write Requests
Long Preamble Emulation with
Acknowledgement (LPA) Write
Ack Ack

Z Z Node A
Z
Z Z
Z
A B
Node B

Write
Request Data
Data arrives

• Idea: Receiver sends ACK when data is received

• Sender can stop sending, go back to sleep, on receiving ACK
• Issue: Sender still needs to stay awake until receiver wakes up
 Long Preamble Emulation with
Acknowledgement after Local
Synchronization (LPAS) Write
Write Ack Ack Ack
Ack

Z Z Node A
Z
Z Z
Z
A B
Node B
IIknow
received a Write
node A isn’tAck at this
awake. Buttime,
I
so I aknow
know timenode
whenAitwill
willbe
beawake
awake,at
Write Scheduled
now+tIwiknow
because (andhow
everylong
additional
I’ve slept twi
Request
Data Wakeup Data
since the lastafter that).
Write Ack from A. Data arrives

• When a node receives a Write Acknowledgement, it logs the time

• Can estimate the node’s schedule from that
• Later, if it needs to send to the same receiver, it turns on when it
expects the receiver to wake up
• Turns on a bit earlier to mitigate estimation delay
 1. Collision detection and
resolution
 What if two nodes send

Wireless MAC at same time?

2. Power-saving algorithms
 What if a node transmits
but the destination is
sleeping?

3. Association and neighbor

discovery
 Who is out there?
 Neighbor Discovery in Wired Networks:
Link-Layer Discovery Protocol (LLDP)
Eth1/40 Gi0/27 Gi0/43 Eth0/26

Switch1 Switch2 Switch3

switch# show lldp neighbor LLDPDU LLDPDU

Capability codes: TLV type Value TLV type Value
(R) Router, (B) Bridge, (T) Telephone,
Device ID (C) DOCSIS
“Switch2” Cable Device Device ID “Switch2”
(W) WLAN Access Point, (P) Repeater, (S)
Chassis ID
Station, (O) Other
0xDECA36080 Chassis ID 0xDECA36080
Device ID Local Intf Chassis ID Port ID Hold-time Capability
Port ID Gi0/27
Switch2 Eth1/40 000d.eca3.6080 Gi0/27 120 B Port ID Gi0/43

switch# Capabilities Bridge Capabilities Bridge

• Periodically (e.g., every 30 seconds) exchange LLDPDUs with physical neighbors

• Each LLDPDU contains set of type-length-value (TLV) records
• Example TLVs: Chassis ID, Port ID, System name, System description, Management address, etc.
• Common Cisco-Proprietary variant: Cisco Discovery Protocol (CDP)
Can we use LLDP to discover neighbors in
wireless?
• Wireless has additional challenges
• May have multiple “equivalent” neighbors (e.g., access points)
• May need to discover “closest” neighbor
• May need to reserve resources
• Neighbors may lie about who they are

• Wireless protocols have been developed to solve these

challenges
• Association, discovery, authentication
How to know where access points are?
SSIDs: SSIDs:
VFCorp, VFCorp,
VFGuest VFGuest

SSIDs:
xfinitywifi

SSIDs:
VFCorp,
VFGuest
SSIDs:
M1-Enclave-Wireless

• NICs scan all channels • Access points periodically send

searching for beacons beacon frames
• Can show list to user, e.g., • Contain SSIDs, supported rates,
sorted by signal strength or transmission parameters
preference
• NICs can also actively send • Default interval of 100ms
probe requests to actively scan
 AP Association Process

Probe request
Probe response AP Discovery

Authentication open seq:1

Time Authentication open seq:2
Authentication

Association request
Association response Association

Data
Data

• Done on first connection

• If signal becomes low, client repeats process to be associated with another AP
• TODO Need to flesh this out – association and such
Mesh Networking
 1. Addressing
 How to identify
destinations that may be multiple

Mesh Networking hops away?

2. Traditional Routing
 How can nodes discover
paths across intermediate hops?

3. Mesh Routing
 How to route in dynamic,
unstable wireless environment?
Motivating Scenario
• Distribute a bunch of nodes
in some environment
• Home, field, zoo, building
• Need to collect data,
monitor
• No (reliable) wireless
infrastructure
• They need to work together
to do things
Mesh Networking
• Networking elements cooperatively connect directly,
dynamically, and non-hierarchically to forward data
• Dynamically self-organize and self-configure

• Distributed algorithms solve key challenges

• Addressing and identifying nodes
• Routing across multiple hops
• Forming spanning topologies
• Replicating and collecting data
Mesh Networking: Applications

Space networking
Electric smart Smart homes (e.g., Iridium satellite
meters (e.g., Google Home) constellation)
How Routing Works
B K
Q
V

A
Send(msg,Q) S
F
X
J

• Each node has an address

• Goal: find path to destination
Scaling Routing With Aggregation
Area 1

1.1 1.2 Area 2

B K
2.1
Q 2.2
V

Area 4
Area 3 4.1
3.2 A 4.2
S 3.3
F
3.1 X
J

• Pick addresses that depend on location

• Topology-dependent addressing
• Aggregation provides excellent scaling properties
Types of Addressing
• What should addresses identify?
• Device
• Interface
• Application
• Service
• User
• Logical Node
• IoT presents additional requirements
• Zero-management (don’t want home users to manage addresses)
• Robust to churn (nodes may come and go over time)
• Uniqueness (each node identity should be unique)
Common Approaches to Addressing
1. Hardware addressing

2. Geographic addressing

3. Hierarchical addressing

4. Stochastic (random) addressing

 Hardware Addressing
• Interface/node comes
with burned-in 0a:4b:bd:62:3b:eb
ce:49:32:a3:5d:b4
address/key from factory b2:2f:21:95:7c:c0
ae:f8:2a:6d:f4:f1
(e.g., MAC addresses) ba:cc:2a:72:a1:29
da:e3:ef:b1:52:cf
4a:d4:db:15:67:11

• E.g., vendor given block

from standards body, 7a:99:75:04:cc:a2 76:ff:2a:35:6a:1b
1e:fa:1a:00:cf:49
allocates to production
line
ee:4e:41:1b:52:5b
36:b0:a2:36:df:4d
• Benefits: no address 66:11:52:d6:8b:74
92:43:01:57:3f:8d
assignment protocol
needed 56:b3:26:c3:f1:72

• Downsides: addresses
may be too long, harder
to route on addresses
 100
90
Geographic Addressing

80
70
• Assign address based
on GPS or other

60
coordinates (12,56)
(54,38)
(13,7)

• Can simplify routing, (4,51)

(51,48)
50
(48,75)
but requires (26,49)

mechanism for
coordinate assignment (0,39) (36,39)
40

(59,38)
(e.g., GPS)
• Benefits: can (13,27)
(85,25)
30

(44,25)
sometimes route on (62,22)

addresses, no address
20

assignment protocol (27,17)

needed


• Downsides: addresses
10

may be too long, Y

harder to route on X
addresses 0 10 20 30 40 50 60 70 80 90 100
0
Hierarchical Addressing
• Organize nodes in a
tree, parent gets
block of addresses, I
gives itself and E P
A
children K N
addresses/sub-blocks F
from that range B H L

D O
J
M

G
Hierarchical Addressing 0-2047

A
0
1-1023 1024-2047
• Organize nodes in a
tree, parent gets B E
1 1024
block of addresses, 2-511 1025-1535 1536-2047
gives itself and D F I
children 2 1025 1536

addresses/sub-blocks 3-255 1026-1280

from that range G H

3 1026
• Benefits: Easier to 4-127 1027-1151 1152-1280

route on addresses J L K
4 1027 1152
• Downsides: Requires 5-63 1153-1216

tree-like organization, M N
requires advance 5 1153

knowledge of future 6-31

arrival patterns O
6
7-15

P
7
Hierarchical Addressing:
Zigbee’s Distributed Addressing scheme
• Good for networks that happen to be structured as trees
• Assigns each node a unique 16-bit address
• Approach: Given limit on
• Maximum depth L
• Maximum children per parent C
• Maximum number of forwarding nodes (Routers) R
• The address of the nth child is [parent]+1+n+(n-1)*S(d)
• Where S(d) is the amount of addresses to “skip” at each level:
• If R=1, S(d)=1+C(L-d)
• If R>1, S(d)=(CRL-d-1-1-C-R)/(R-1)
 Hierarchical Addressing:
Zigbee’s Distributed Addressing scheme
Example: Coordinator
• Max depth L=2 C d=0
0
• Max routers R=4
• Max children C=3 Routers
S(d)=(CRL-d-1-1-C+R)/(R-1) R1 R2 R3 R4 d=1
1 6 11 16
S(0)=(3*42-0-1-1-3+4)/(4-1)=4
• (Children of level 0 will have a
pool of 4 addresses)
F
I G H I J K L M N O P d=2
S(1)=(3*42-1-1-1-3+4)/(4-1)=1
2 3 4 5 7 8 12 17 18 19 20
• Children of level 1 will have a Leaves
pool of 1 address)
Address of R1: 0+1+0=1
Address of R2: 0+1+1+S(0)=6
Address of R3: 0+1+2+2*S(0)=11
Stochastic Addressing
Yes, I’m
using 137!
That’s my address! I
• Nodes choose random need to let that guy
Problem:
know there’s an
number for address 204 Address conflict!
address conflict.
191
89
• Simple to implement, 133
110
but requires conflict 167
137

resolution to ensure
173 109
uniqueness 162

• Zigbee: broadcast
address on selection, if 188
6
217
a node has a conflict it 159
broadcasts an error
• Collisions more 137

common than you may

think (see “Birthday
problem”) Hmm, what address Is anyone
• Also, addresses are should I use.137
Address Let me
is in
using 137?
choose a random
location-independent use. I should choose
one. one.
another
Which devices use which protocol
Bluetooth
• Most cell phones, including
iPhone, Samsung Galaxy
• Tablets, gaming consoles,
 Bluetooth BLE Zigbee Z-Wave Thread
Used in Most cell Most cell
phones, phones,

Power
Management
Mesh Routing N/A ? AODV, DSR, AODV, DSR,
Tree Routing Tree Routing
 1. Addressing
 How to identify
destinations that may be multiple

Mesh Routing hops away?

2. Traditional Routing
 How can nodes discover
paths across intermediate hops?

3. Mesh Routing
 How to route in dynamic,
unstable wireless environment?
Problem: What if node you want to talk to
isn’t within radio range?

• Idea: nodes cooperate with each other to route data as far as

possible
• Challenge: need distributed algorithms to discover and maintain
paths across multiple hops
• Requirements: loop-free, fully-distributed, unidirectional links
Key approaches
• “We should always have routes available to everyone, at all times!”
• This is called proactive routing
• Better for fixed/static environments, frequent communication
• Requires more control overhead, memory, power; lower route acquisition time
• Examples: OSLR, Tree Routing

• “We should create routes only when we need them!”

• This is called reactive routing
• Better for dynamic environments, rare communication; higher route
acquisition time
• Requires less control overhead, memory, power
• Examples: AODV, DSR
Link
Eachstate: update
node maintains
a “topology database”
propagation F tells all routers:
there is a link
between F and E
[C,A]
[D,E]
[C,E]
[C,B]
[A,B]
[B,D]
[E,F]
[D,F]
[C,A]
[D,E]
[C,E]
[C,B]
[A,B]
[B,D]
[E,F]
[D,F] B D [C,A]
[D,E]
[C,E]
[C,B]
[A,B]
[B,D]
[E,F]
[D,F]

A [C,A]
[D,E]
[C,E]
[C,B]
[A,B]
[B,D]
[E,F]
[D,F] [C,A]
[D,E]
[C,E]
[C,B]
[A,B]
[B,D]
[E,F]
[D,F] [C,A]
[D,E]
[C,E]
[C,B]
[A,B]
[B,D]
[E,F]
[D,F] [C,A]
[D,E]
[C,E]
[C,B]
[A,B]
[B,D]
[E,F]
[D,F] F

[C,A]
[D,E]
[C,E]
[C,B]
[A,B]
[B,D]
[E,F]
[D,F]
[C,A]
[D,E]
[C,E]
[C,B]
[A,B]
[B,D]
[E,F]
[D,F] C E
[C,A]
[D,E]
[C,E]
[C,B]
[A,B]
[B,D]
[E,F]
[D,F]

• How to prevent update loops: (seq numbers)

• How to bring up new node: (load TDB from neighbor)
Link state: route computation

B D

A F

C E

• Each router computes shortest path tree, rooted at that router

• Determines next-hop to each destination, publish to forwarding table
• Protocols can assign link costs to control path selection
Link-state: packet forwarding
B D

IP packet A F
source destination

C E

• In practice: shortest path precomputed, next-hops stored in forwarding table

• Downsides of link-state:
– Lesser control on policy (certain routes can’t be filtered), more cpu
– Increased visibility (bad for privacy, but good for diagnostics)
Distance Vector Routing
• Each router knows the links to its neighbors
• Does not flood this information to the whole network
• Each router has provisional “shortest path” to
every other router
• E.g.: Router A: “I can get to router B with cost 11”
• Routers exchange this distance vector information with their
neighboring routers
• Vector because one entry per destination
• Routers look over the set of options offered by their neighbors and
select the best one
• Iterative process converges to set of shortest paths
Distance Vector: Update Propagation
D tells B: I am D, and
I can reach F via 1 hop
D’s forwarding table F tells D: I am F, and
B’s forwarding table Dest NextHop Dist
Dest NextHop Dist
I can reach F via 0 hops
F F 1
F D 2
(F,1)
(F,2) B D (F,0)

A (F,2) (F,2) (F,1) (F,1) F

source destination

(F,0)
(F,2) C E
(F,1)
 Distance Vector: Convergence
Updates
received by A: 0 1 2 3 4 5 6 7
Withdraw(H)
A B D
source

C E F G H
destination

• How many updates would link-state require?

• Is link-state better or worse than distance vector?
• Idea: What if updates were destination-sequenced?
 1. Addressing
 How to identify
destinations that may be multiple

Mesh Routing hops away?

2. Traditional Routing
 How can nodes discover
paths across intermediate hops?

3. Mesh Routing
 How to route in dynamic,
unstable wireless environment?
Why not use these protocols in wireless?

✓ K
E
A
I✓
F L
✓ O
B H
✓
D
J✓ N
M P
G✓
C • Problem 1: Unicasts to each neighbor
are kind of redundant
• Problem 2: Don’t really need all
neighbors to re-flood message
• Problem 3: May not really need routes
to all nodes
Why not use these protocols in wireless?

K
E
A
I
F L O
B H

D N
J
M P
G
C • Problem 1: Unicasts to each neighbor
are kind of redundant
• Problem 2: Don’t really need all
neighbors to re-flood message
• Problem 3: May not really need routes
to all nodes
Why not use these protocols in wireless?

K
E
A
I
F L O
B H

D N
J
M P
G
C • Problem 1: Unicasts to each neighbor
are kind of redundant
• Problem 2: Don’t really need all
neighbors to re-flood message
• Problem 3: May not really need routes
to all nodes
Why not use these protocols in wireless?

K
E
A
I
F L O
B H

D N
J
M P
G
C • Problem 1: Unicasts to each neighbor
are kind of redundant
• Problem 2: Don’t really need all
neighbors to re-flood message
• Problem 3: May not really need routes
to all nodes
 Why not use these protocols in wireless?

K
E
A
I
F L O
B H

D N
J
M P
G
C • Problem 1: Unicasts to each neighbor
are kind of redundant
• Problem 2: Don’t really need all
• Unnecessary transmissions waste neighbors to re-flood message
battery, bandwidth • Problem 3: May not really need routes
to all nodes
• Unnecessary routes waste storage
Solution: Mesh Networking
• Nodes cooperate to efficiently route data
• Nodes can act as relays, enabling multi-hop
forwarding
• Mesh networks dynamically self-organize and
self-configure
• Reduce management and configuration overhead
• Improves fault-tolerance
• Dynamically distributes workloads
Mesh Networking Protocols
1. Optimized Link State Routing (OLSR)
2. Destination-Sequenced Distance Vector (DSDV)
3. Dynamic Source Routing (DSR)
4. Ad Hoc On-demand Distance Vector (AODV)
5. Tree Routing
6. Geographic/Perimeter Routing
7. Gossip Routing
Optimized Link State Routing (OLSR)
• Main idea: Do link state, but avoid unnecessary transmissions of
link state updates
• All nodes will still receive all link state updates

• Nodes broadcast; reach all neighbors with one message

• Each node decides which of its neighbors will flood

• These neighbors are known as multipoint relays (MPRs)
• MPRs selected based on nodes neighbors can reach
• Only MPRs transmit updates, other nodes do not
 Optimized Link State Routing (OLSR):
Neighbor Discovery 1-hop: H K
2-hop: F J
1-hop: F 1-hop: H I
2-hop: H 2-hop: F J
I [I][K]
Hello
Hello
[F] Hello [I] Hello
E
[H] Hello K
[E] Hello F [F] Hello
[H]
[K] Hello
1-hop: H E [H] Hello
H
2-hop: I J K
[H]
[J] Hello
Hello
1-hop: F K J I
2-hop: E J • Step 1: Each node discovers
its two-hop neighbors
• By sending “hello” packets
1-hop: H with a list of the sender’s
2-hop: F I K neighbor set
 Optimized Link State Routing (OLSR):
Neighbor Discovery 1-hop: H K
2-hop: F J
1-hop: F 1-hop: H I
2-hop: H [I] Hello {H,K} 2-hop: F J
[I] Hello {H,K} I [K] Hello {H,I}
[H] Hello {F,K,J,I}
E
K
[E] Hello {F} F [F] Hello {H,E}
[K] Hello {H,I}
[F] Hello {H,E}
1-hop: H E [H] Hello {F,K,J,I} [H] Hello {F,K,J,I}
H
2-hop: K J I
[J] Hello {H}
1-hop: F K J I
2-hop: E J
[H] Hello {F,K,J,I} • Step 1: Each node discovers
its two-hop neighbors
• By sending “hello” packets
1-hop: H with a list of the sender’s
2-hop: F I K neighbor set
 Optimized Link State Routing (OLSR):
MPR Selection
1H: E H K
1H: A F I 2H: A F D G J N
2H: B H I K 1H: N O
1H: B E 2H: K L M
2H: I F D 1H: I H N 1H: K L P
I 2H: E F L P 2H: I H M
E P
A
2-Hop Neighbors of H K N
(need to select MPRs F
to “cover” these
nodes) B 1H: B E H
2H: A D G J I
H L
1H: D F G I J K
1H: H M N
2H: E B M N
1H: A D F 2H: D G F I O P 1H: M N P
2H: E H G D O 2H: J L K
J
M
1H: B G
2H: A F I K J L 1H: F H M
G 2H: D F I K O 1H: J L O • Step 2: Each node selects subset of
2H: G H N P neighbors to forward its link states
1-Hop Neighbors of H
(H can broadcast to reach
1H: D H J • Selected neighbors are called
these)
2H: B F I K L M multipoint relays (MPRs)
• LSs are broadcast and received by all
neighbors, but only MPRs forward
them onward
Optimized Link State Routing (OLSR):
MPR Selection Algorithm
• Goal:
• Given a node H, with 1-hop neighborhood N1(H), and 2-hop neighborhood
N2(H)
• Select within N1(H) the smallest possible set of nodes that covers the entire
set of nodes in N2(H)

• Algorithm:
• Step 1: Select all nodes in N1(H), which cover isolated points of N2(H)
• Isolated points are nodes that are reachable by only one member of N1(H)
• Step 2: Amongst all unselected nodes in N1(H), select the node, which covers
the maximum number of uncovered nodes in N2(H)
• Step 3: Repeat Step 2 until all nodes are covered

• This is just a heuristic (optimal/minimum MPR set is NP-complete)

Optimized Link State Routing (OLSR):
MPR Selection
A J
N
G
K
O
Isolated D
points H M

B L P
E
I
C • Step 1:
2: Select
Amongstall nodes in
F N 1(H), which
unselected coverin N1(H),
nodes
isolated
select onepoints
thatof N2(H)
covers
most nodes in N2(H)
Optimized Link State Routing (OLSR):
Forwarding
• Same as regular link state: Build a topology database, run
Dijkstra’s, store shortest-path next-hop for each destination
• However, observe that nodes tend to select higher-connected
nodes as MPRs
• Therefore, nodes tend to select same nodes as MPRs
• MPRs tend to form a smaller “spanning” subgraph of the topology
• Optimization: MPRs forward all traffic, not just link state adverts
• Reduces routing table size
• Allows more nodes to sleep
• But, asymmetric battery usage
• [may want to add an animation here on how Dijkstra’s computes
the tables given the mprs]
Optimized Link State Routing (OLSR):
Forwarding

I
E P
A
K N
F May want to animate packet
forwarding, just for clarity
B H L

D O
J
M

G
What’s wrong with OLSR?
• Great approach, used in some protocols

• However, it maintains routes to all nodes, all the time

• Good if most nodes need to talk to each other
• Wastes overhead if communication is more sparse/rare
• Also: Reveals the entire topology to all nodes  bad for privacy

• Idea: What if we only build routes “on demand” when we need

them?
• Idea behind “reactive” routing
• Examples: AODV, DSR
Dynamic Source Routing (DSR)
• When network starts, no routing updates are sent
• Network performs a discovery process only when data needs
to be sent

• When packet arrives at an interface, node floods “route

request” (RREQ) message for destination

• Message records list of intermediate hops in the packet

Dynamic Source Routing (DSR)
• When destination receives RREQ, it replies back to the
source with a RREP message
• RREP sent back along reverse of path contained in RREQ

• When source receives the RREP, it now knows a “source

route” to the destination
• It then sends the data, putting the source route in the header
• Intermediate hops determine the next hop by inspecting the
source route
• Source caches the source route in case it needs it later
 Dynamic Source Routing:
Route Request (RREQ)
Source – node Route – the source route
sending the learned by the RREQ
RREQ

Control packet
UID SRC DST RTE
format:

Unique id – used to ensure

each message not transmitted Destination – node the
more than once RREQ is destined to
 Dynamic Source Routing:
Route Request (RREQ)

RREQ Packet Format:

Source – node
Route – the source
sending the
route learned by the
RREQ
RREQ

UID SRC DST RTE

Unique id – used to
Destination –
ensure each message
node the RREQ is
not transmitted more
destined to
than once
 Dynamic Source Routing:
Route Request (RREQ)
Intermediate nodes append their
address to the path and forward
update; temporarily cache unique
Data packet id to avoid re-forwarding
3 A M EE I
arrives, triggers 3 A M E 3 A M E 3 A M EFHKNP
RREQ source 3 A M E I
E 3 A M EFHK
3 A M EFHKNP P
3 A M E F H 3K A M 3E F AH KM 3E FAH K
A 3 A M E F MN E F H K N
3 A M 3
3 A M E A M BB F 3 A M E F H K N
3 A M
3 A M B 3 A M B F
3 A M EF
3 A M EFHK
3 A M EFHKN
3 A M E F H3 A M E F H 3 A M EFHL 3 A M EFHKNP
3 A M B 3 A M E F H 3 A M E F H K N
3 A M EF 3 A M EFHL
B H3 A M EFH
L3 A M EFHKN
3 A M BD 3 A M EFHL
RREQ Packet Format:
3 A M B 3 A M EFH 3 A M EFHL
3 A M B D 3 A M BB3D A M E F H 3 A M EFHJ 3 A M EFHKNO
Source – node D 3 A M EFH
O
sending the
Route – the source
3 A M BDG J
RREQ
route learned by the M
RREQ destination
3 A M BD 3 A M BB D
DG I need to reply back to A.
3 A M BDG 3 A M BDG I can do that via the
UID SRC DST RTE
G reverse of the path in the
If Target Address RREQ LHFEA
matches this node’s IP
address, node returns a
Unique id – used to
Destination –
Route Reply (RREP) • Step 1: On data packet arrival,
ensure each message
not transmitted more
node the RREQ is node sends RREQ to discover
than once
destined to path to destination
 Dynamic Source Routing:
Route Reply (RREP)
Now I can send my data
packet to M, using the
path AEFHLM

source I
E P
A
K N
F
B H L
RREP Packet Format:

Source – node D A M EFHL

O
sending the
Route being sent J
RREP
back to the M
source destination I need to reply back to A.
I can do that via the
SRC DST RTE
G reverse of the path in the
RREQ LHFEA

Destination –
• Step 2: Upon receiving an RREQ,
node the RREP
destination returns discovered path back
is destined to to the source in an Route Reply (RREP)
 Dynamic Source Routing:
Forwarding
Now I can send my data
packet to M, using the
path AEFHLM

source I
A M EFHL Data E P
A
K N
F
B H L
Data Packet Format:

Source – node D O
sending the
Route being sent J
RREP
back to the M
source destination

SRC DST RTE Payload

G

Destination –
Payload – data • Step 3: Source can then send data
node the RREP
being sent in
packet
using source route contained in
is destined to RREP
Dynamic Source Routing:
Route Caching

• Source will cache route for some period of time, in case

it wants to send more packets to that same destination
later
• Intermediate nodes and other nodes overhearing RREQs and
RREPs may also cache paths they see
• Entries are deleted after timeout (tunable parameter)
• Route cache size can be limited (tunable parameter)
Dynamic Source Routing:
Route Caching

• If an intermediate node receives an RREQ for which it

has a cached route, it may reply even if it is not the final
destination
• Leads to “RREP Storms” where all nodes’ neighbors reply with
an RREP simultaneously
• Solution: RREP may be sent with some delay while listening if
another node replies with a shorter route
Dynamic Source Routing:
Route Error (RERR)
Source – node
sending the Route used to
RERR reach the source

SRC DST RTE Link

Destination –
The link that
node the RERR
failed
is destined to
 Dynamic Source Routing:
Route Error (RERR)

Source – node
Route used to
sending the
reach the source
RERR

SRC DST RTE Link

The link that

Destination –
failed
node the RERR
is destined to
 Dynamic Source Routing:
Route Error (RERR)
Dest Path
Now I can send my data
M E-F-H-L-M
packet to M, using the
path AEFHLM

source I
E P
A M A
EFHL Data
K N
F
L A EFH L-M
B H L
RERR Packet Format:

Source – node D O
sending the
Route used to J
RERR
reach the source M
destination
What if this link
SRC DST RTE Link
G goes down?

• Route Error: Sent back when data packet

Destination –
The link that encounters a failed link in the path
failed
node the RERR • Keeps route caches up-to-date in presence
is destined to of churn
What’s wrong with Dynamic Source
Routing?
• Nothing, it’s a great protocol
• Used in Zigbee, etc.
• However, as network gets big, source routes get long
• Lots of packet overhead
• Also caches can get stale
• Outages not discovered until packets sent
• Idea: What if we had each intermediate hop store a
pointer
• More like distance vector, embed the path in the network
Ad Hoc On-Demand Distance Vector
(AODV)
• Just like DSR, no route discovery process until data needs
to be sent (reactive routing)

• Just like DSR, RREQ sent to find a route

• But, no source routes are collected
• Instead, RREQ creates distance-vector entries at each hop
pointing back to source
• RREP used to set up forward path, traverses entries RREQ
created to reach source
Ad Hoc On-Demand Distance Vector
(AODV)

• Nodes on active path maintain routing information

• Table entries are expired if not used recently by data packets

• Destination-controlled sequence number stored with each

route
• Prevents storing of stale routes
• Also mitigates “count-to-infinity” problem and routing loops
Ad Hoc On-Demand Distance Vector (AODV):
Route Request (RREQ)
Source – node Destination Sequence
sending the Number – used to reduce
RREQ transient routing loops

SRC DST HOPS DSEQ BID

Hop count – number of Broadcast ID – used to

Destination –
transmissions needed to ensure each message
node the RREQ
reach destination not transmitted more
is destined to
than once
 Ad Hoc On-Demand Distance Vector (AODV):
Route Request (RREQ)

RREQ Packet Format:

Source – node Destination Sequence
sending the Number – used to
RREQ reduce transient
routing loops

SRC DST HOPS DSEQ BID

Destination Hop count – Broadcast ID –

– node the number of used to ensure
RREQ is transmissions each message
destined to needed to reach not transmitted
destination more than once
 Ad Hoc On-Demand Distance Vector (AODV):
Route Request (RREQ) Intermediate nodes maintain
tables; create distance-vector-style
Data packet entry pointing back to source of
arrives, triggers Dest Next Hops Seq
message Dest Next Hops Seq
Dest Next Hops Seq Dest Next Hops Seq
RREQ A H 4 7 A K 5 7
A A 1 7 A N 6 7
Each node maintains Dest Next Hops Seq
two counters: source
A M 1 7 4
A M 41 7 4
A I H 4 7
Sequence Number E M 3 7Hops
Dest ANext A 4M 4 Seq
7 4
A M 4 7 4
AM6 7 4
P
Broadcast ID A A B 2 7 AM 4 7 4
S:7 B:4 A MA0 M7 24 7 4
AM1 7 4
AM 4 7 4
Dest Next Hops Seq K
AM5 7 4 AM5 7 4
N
AM1 7 4
AM0 7 4
F
A FA M 43 7 4 7 Dest Next Hops Seq AM6 7 4
Dest Next Hops Seq AM2 7 4 A HA M 54 7 4 7
AM3 7 4 A M 3 7 4
A A 1 7 A M 1 7 4AM 2 7 4
B H
AM4 7 4 AM4 7 4 AM5 7 4
LAM7 7 4 AM7 7 4
AM1 7 4 AM3 7 4
A M 2 7 4 A M 3 7 4
RREQ Packet Format:
AM2 7 4 AM4 7 4 AM3 7 4 AM4 7 4
Source – node Destination Sequence D AM4 7 4 AM3 7 4 O
sending the Number – used to AM3 7 4 J AM4 7 4

RREQ reduce transient

Dest Next Hops Seq A M 2 7 4 A M 4 7 4
AM4 7 4
M
A
routing loops B 2 7 AM4 7 4 Dest Next Hops Seq
destination
Dest Next Hops Seq A P 7 7

SRC DST HOPS DSEQ BID

G A H 4 7 Dest Next Hops Seq
A L 5 7
Dest Next Hops Seq
A H 4 7
Destination
– node the
Hop count – Broadcast ID –
used to ensure
• Step 1: Source floods RREQ to
number of
RREQ is transmissions each message create reverse path for M to
destined to needed to reach not transmitted
destination more than once reach A
 Ad Hoc On-Demand Distance Vector
(AODV): Route Reply (RREP) Intermediate nodes maintain
tables; create distance-vector-style
Data packet entry pointing back to source of
arrives, triggers Dest Next Hops Seq
message Dest Next Hops Seq
Dest Next Hops Seq Dest Next Hops Seq
RREQ A H 4 7 A K 5 7
A A 1 7 A N 6 7
Dest Next Hops Seq
Each node maintains
M B 4 7 Dest Next Hops Seq
two counters: source I A H 4 7
Sequence Number E Dest Next Hops Seq
P
Broadcast ID A A B 2 7
S:7 B:4
M DestH Next
2 Hops
80 Seq K N
M A 0 80 160000 M A 0 80 160000 F A F 3 7 Dest Next Hops Seq
Dest Next Hops Seq M L 2 80 A H 4 7
A A 1 7 M A 0 80 160000 M M 1 80
M F 3 80 B H L
M A 1 80 160000
RREQ Packet Format:
M A 0 80 160000
Source – node Destination Sequence D O
sending the Number – used to J
RREP reduce transient
Dest Next Hops Seq M
A
routing loops B 3 7 destination Dest Next Hops Seq
Dest Next Hops Seq A P 7 7

SRC DST HOPS DSEQ Lifetime

G A H 4 7 Dest Next Hops Seq
A L 5 7
Dest Next Hops Seq
A H 4 7
Destination
– node the
Broadcast ID – Time in
milliseconds
• Step 2: Destination replies back
used to ensure
RREP is each message route should be via the trail of routing table
destined to not transmitted considered valid
more than once entries created by the RREQ
Ad Hoc On-Demand Distance Vector
(AODV): Route Error (RERR)
• Withdrawal message, sent when:
• Node detects a link break for next hop of routing table entry
• Receives data packet for which it has no route
• It receives an RERR pertaining to one of node’s active routes

• Nodes have the option to locally repair

• Instead of forwarding RERR, initiate RREQ for affected
destination
• Only attempted if dest’s # hops away < MAX_REPAIR_TTL
• Can inflate path lengths over time
 Hierarchical Addressing:
Zigbee’s Distributed Addressing Scheme
Example: Coordinator
• Max depth L=2 C d=0
0
• Max routers R=4
• Max children C=3 Routers
S(d)=(CRL-d-1-1-C+R)/(R-1) R1 R2 R3 R4 d=1
1 6 11 16
S(0)=(3*42-0-1-1-3+4)/(4-1)=4
• (Children of level 0 will have a
pool of 4 addresses)
F
I G H I J K L M N O P d=2
S(1)=(3*42-1-1-1-3+4)/(4-1)=1
2 3 4 5 7 8 12 17 18 19 20
• (Children of level 1 will have a Leaves
pool of 1 address)
Address of R1: 0+1+0=1
Address of R2: 0+1+1+S(0)=6
Address of R3: 0+1+2+2*S(0)=11
 Tree Routing
0-20
• Each node knows Coordinator
C d=0
subrange for each 0

of children Routers 1-5 6-10 11-15 16-20

R1 R2 R3 R4 d=1
• Each node checks 1 6 11 16
to see if
destination
address is in Dest=18 F
I G H I J K L M N O P d=2
children’s 2 3 4 5 7 8 12 17 18 19 20
subranges Leaves
• If so, sends to
appropriate child
• If not, sends to
parent
Geographic Routing
• Uses geographic position information to make progress
to destination

• Source sends message to geographic location of the

destination

• Each node keeps track of geographic location of its

neighbors, so it knows which neighbor makes most
progress to destination
Geographic Routing

• More complex than you might think

• You can get stuck in dead ends (“voids”)
• You can get stuck in loops (two neighbors think each other
makes the most progress to the destination)

• Example implementation of Geographic routing:

• Greedy Perimeter Stateless Routing (GPSR)
 Geographic Routing: Greedy Forwarding
110

Hello! My name is E,
E: (58,79)
Which next and my coordinates
100

H: (87,57)
E: (58,79)
hopA: should
(40,76)
I are (58,79)
K:E:(107,72) N: (140,71)
F: (70,69) (58,79)
C: (13,61) use?
I: (91,83) I: (91,83) K: (107,72) O: (151,41)
90

B: (37,58) E: (58,79) H: (87,57) L: (120,56)

E: (58,79) O: (151,41)
source
B: (37,58)
I
I: (91,83) N: (140,71)
P: (168,80)
H: (87,57) K: (107,72)
P
80

Dest=(126,37) E E: (58,79) (91,83)

L: (120,56)
A (58,79) J: (96,40) H: (87,57) (168,80)
A: (40,76) A: (40,76)
G: (72,25) K N: (140,71)
N
70

F: (70,69) (40,76)
F
79-37=42

D: (56,44)
D: (56,44) (107,72)M: (126,37)
F: (70,69) (140,71)
B: (37,58) (70,69)
C M: (126,37)
60

G: (72,25)
(13,61) B H: (87,57) H H: (87,57)
G: (72,25) L J: (96,40)
N: (140,71)
(87,57) P: (168,80)
(37,58) M: (126,37) L: (120,56)
50

(120,56) O: (151,41)

D D: (56,44)
O
J
40

H: (87,57)
(56,44) J: (96,40)
(96,40)
M (151,41)
126-58=68 (126,37)
30

G
20

(72,25)
10

0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190
Geographic Routing:
Variants of Greedy Forwarding
Greedy Routing: Choose node
with minimum remaining
Compass Routing: Choose distance to destination
node with minimum angle
between node and destination

source
D
C
A M
B
Nearest with Forwarding Most Forwarding Progress within Radius
Progress: Choose nearest node (MFR): Choose node that makes most
that makes progress along progress along straight line distance
straight line distance E

• How should we measure “progress” to the destination?

Geographic Routing:
Does greedy routing guarantee delivery?
F
D (81,104)

(60,92) G
(107,86)

source
Dest=(121,65) H
A C (116,67) M
(37,58) (70,63) (121,65)
E
(87,57)

B
(56,44)

• Problem: Dead ends (“Voids”)

Geographic Routing:
Perimeter Forwarding
F
D (81,104)

(60,92) G
(107,86)

source
H
A C (116,67) M
(37,58) (70,63) (121,65)
E Dest=(121,65)
(87,57)

B
(56,44)

• Problem: Perimeter forwarding breaks when there are closed faces

• Solution: “Face routing” – switch “faces” when we start going backwards
Geographic Routing:
Face Routing
F
D (81,104)

(60,92) G
(107,86)

source
H
A C (116,67) M
(37,58) (70,63) (121,65)
E Dest=(121,65)
(87,57)

B
(56,44)

• Problem: Perimeter forwarding breaks when there are closed faces

• Solution: “Face routing” – switch “faces” when we start going backwards
Geographic Routing:
Making Perimeter Forwarding Work
• Face Routing can fail if graph is non-planar (cross-
edges)
• To address this, we “Planarize” the graph
• Remove all cross edges
• There are distributed protocols to do this
• Work by removing edges from the graph
• Example: Relative Neighborhood Graphs
• Each edge (u,v) is allowed to remain in the graph only if there
does not exist another connected node r that is closer to
both u and v than they are to each other
Coming back to our motivating scenario…
• Assumed network is not partitioned
• Is it realistic?
• What if graph is not always connected?
• Occasionally-connected networks: Sensors
mounted on animals, floating in ocean; space
satellites that “pass” occasionally
• Highly unreliable environments: military
networks suffering from jamming, acoustic links
in air/water, free-space optical communications
• Low-power environments: low-duty cycle
sensors/actuators
Delay-Tolerant Networking

source I
Dest=(126,37) E P
A
K N
F
B H L

D O
J
M

G
Delay-Tolerant Networking:
Geographic Routing

source I
Dest=(126,37) E (91,83) P
A (58,79) (168,80)
(40,76) K N
F (107,72)
(140,71)
(70,69)

B H L
(37,58) (87,57)
(120,56)

D O
(56,44) J
(96,40)
M (151,41)
(126,37)

G
(72,25)
 Delay-Tolerant Networking:
Delay-Tolerant Link State Routing
E E
EE I II I
A A
AA K N
B B F F
FF
BB
H H
HH L L
D D L
DD
source I
G G
GG M
E P
A
K N
F K
P
N

B H L
L

O
J M

D O
J
M

• Run link state, but “age out” links when they go down
• Data will flow along paths that will hopefully re-appear in the future
Delay-Tolerant Networking:
Epidemic/Gossip Routing
Data

source Data I
Data E Data P
A Data
K N
F
Data Data
Data
B H L
Data

D Data
O
J
M
Data

• Every node waits random time, picks random target, and sends data
Delay-Tolerant Networking:
Epidemic/Gossip Routing
• If all link failures are transient and reoccurring, message will
eventually reach the destinations
• Will reach all other nodes too – good for multicast/anycast/broadcast

• However, high control traffic overhead, slow propagation

• Improvement: Rumor mongering

• When node gets new update it becomes a “hot rumor”
• When it encounters many nodes with the update, it propagates it less
frequently
 PLEASE IGNORE
ALL SLIDES
FOLLOWING THIS
ONE
Geographic Routing:
Variants of Greeding Forwarding

source I
Dest=(126,37) E (91,83) P
A (58,79) (168,80)
(40,76) K N
F (107,72)
(140,71)
(70,69)

B H L
(37,58) (87,57)
(120,56)

D O
(56,44) J
(96,40)
M (151,41)
(126,37)

G
(72,25)
Geographic Routing:
Variants of Greeding Forwarding

source I
E (91,83) P
A (58,79) (168,80)
(40,76) K N
F (107,72)
(140,71)
(70,69)
C
(13,61) B H L
(37,58) (87,57)
(120,56)

D O
(56,44) J
(96,40)
M (151,41)
(126,37)

G
(72,25)
• [why have a destination sequence number ] show a loop?
Tree Routing
• [see page 430 of 9789479493686.pdf]
Near-far problem
We can send data wirelessly – now what?
• We can send data using wireless signals
• That’s not enough
• Need to communicate reliably, need to interpret bits, need to track who
I’m communicating with, need to discover who is there, etc.
• We need to perform more functions atop this communication
• We need protocols
• Next I will talk about IoT protocols
• First, the challenges
• Next, some approaches/algorithms we can use
• Finally I’ll talk about some specific ones
Challenges we need to deal with
• How to communicate with other nodes? (RF Communications)
• How to share the channel (Wireless MAC)
• How to communicate across multiple hops (Wireless Routing)
• Who is out there? (Discovering other nodes)
What are IoT Networks
What are IoT Networks
Some challenges we need to deal with…

Who else is out there?

Neighbor Discovery/Beaconing/Pairing: Discovers other nodes within radio range
• Inquiry vs beaconing – inquiry nodes have to remain on to listen, beacon you can
broadcast and sleep. But, you may use more bandwidth – imagine dense
deployment, inqiry you may just be able to query for certain services you need, if
you’re looking fo the tv, ask for the tv, you don’t need the clock and the
microwave and each of your carpet tiles saying they’re there
• How do you know who you’re connecting to
• Identifiers/addressing
• Private addressing (BLE)
• Naming
• Who can reliably connect – RSSI estimation, wont connect to people far away
• Discoverable vs undiscoverable – no one can discover my existance (mitigates
finding/tracking)
• Association/authorization – who can connect to me
• Authentication – how I really know who you are
• Require central controller to authenticate
Some challenges we need to deal with…

How to “share the air”?

Channel Allocation: Allocates time/spectrum on shared wireless media
Some challenges we need to deal with…

How can we agree on communicating?

Associating/Connecting/Pairing: Forms a communication relationship
• Connectionless vs connection oriented
• Pairing
Some challenges we need to deal with…
I can measure heartbeats

I can make light

I can take a video

What services can my neighbors provide to me?

Service Discovery: Discovers services on the network
Service Discovery
• [defining feature structure – what are diff possible functions – like snmp
mib. Need to identify classes/type of functions, identify specific attributes,
and also data type for each atrriute and also their semantics (what data
means, but also what behavior is when you trigger something), and also
permissions (read/write, who can access, when they can access). May also
define relationshpis between data items
• Primary and secondary services – eg you may have a temperature sensor (primary).
You may also have a battery with attributes like power level (primary) but the battery
may have a temperature sensor (secondary) – the temp sensor is referenced from
within the battery service
• Device Profile: What device can do
• [query/advert protocol –
• Authorization vs permissions vs etc – who should be able t ocontrol access
to data, how, r/w, etc
How to send data

How do I send and receive information?

Physical Layer: Discovers services on the network
Some challenges we need to deal with…

How can I conserve power?

Sleeping/duty-cycling: enter low-power mode when idle
Sleeping
• Sleep-wake: when event occurs, you wake up and send
Some challenges we need to deal with…

Who else is on the network?

Network Discovery: Discovers other nodes on the network
Some challenges we need to deal with…

Who should I talk to?

Topology: mesh vs broadcast vs point-to-point vs hub-and-spoke vs backhaul
Some challenges we need to deal with…

How to reach other nodes on the network?

Mesh routing: compute paths to destinations
Other considerations
• Ownership: licensing fees, lock out competitors, market
perception, control
• Deployment: attachment
Protocol state diagram
• [talk through what a protocol is – get across state diagram and
time diagram – later can animate diagram and time series!]
 Delay-Tolerant Networking:
Delay Tolerant Link State Routing
E I
A
B F
H
D
source I
G
Dest=(126,37) E P
A
K N
F K
P
N

B H L
L

O
J M

D O
J
A
E I M
B F
H
D

G
G
E I
A
F E I
B A E I
A
H L F
D B F
B
H L
G D H L
D
G
G M
Protocol Architectures
How do we address these challenges?
• There are a number of IoT protocols out there which have been
created

• They sometimes take different approaches for these challenges

• Because they target different domains, for historical/policy reasons, etc.

• Next, we will talk about these protocols

• How they work, their pros/cons, etc.
 Draw a diagram showing local, wider, wider area
Person-area, house area, large area
The write names if diff protocols, lpwan, Bluetooth, etc
Bluetooth
Bluetooth: Application Profiles
• https://www.youtube.com/watch?v=WybSm5slt_o&list=PLHow1
T5bc-u83vfUcdzr2ORKULtLvhT5M&index=2 2:43 – see at top
Bluetooth Low Energy
(aka Bluetooth Smart)
• Light-weight subset of Bluetooth
• Easiest way to design something that can talk to most major
phone and PC platforms (iOS, Android, Windows Mobile, Linux,
MacOS, Windows, etc)
• Primary markets: phones, wearables, …
• Design goals: low-power/cost/bandwidth/range/complexity
• Run time: (long time off single coin cell)
• Chipsets: [see ref below]
• COVERAGE/PLACEMENT ALGORITHMS
• Graph coloring
• Facility location problem
Long Preamble Emulation (LP)

Node A

Node B
Wakeup interval (twi)
Time A Time C
Data arrives Time B