Introductory Example

Mesh clients (mobile)

Gateway
Internet

Mesh router (stationary)

Wireless Mesh Networks: Introduction
Basic Concepts

Eduard Glatz ([email protected])

Mesh network

Example Scenario: Infrastructure/backbone Wireless Mesh Network

■ Multi-hop network: one or more routers on path between source and destination node
■ Mesh network: multipoint to multipoint connectivity

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 1 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 2 of 45

Objectives Agenda
■ You can define and characterize a wireless mesh network ■ Definition and characteristics of a wireless mesh network
■ You can illustrate five different application areas of wireless mesh networks ■ Typical application scenarios
■ You know how to calculate a wireless communication range ■ RF communication basics
■ You can explain the relationship between coding/modulation schemes and capacity ■ Channel access schemes in wireless communications
■ You can give an overview about wireless channel access schemes and their properties ■ Multi-hop wireless networking and formation guidelines
■ You know the history and formation guidelines of wireless mesh networks ■ The path length and power control problem
■ You know the path length and power control problem ■ Routing in mesh networks: requirements, taxonomy, example
■ You can name five wireless-specific routing problems
NB: Not covered topic is security
■ You know the taxonomy of wireless routing protocols
■ You can explain the principle of the ad-hoc wireless distance vector (AODV) routing

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 3 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 4 of 45

Mesh Networking Characteristics of a WMN
■ Network Topologies: ■ WMN‘s are considered to be a subclass of ad hoc networking
--> Routing nodes are stationary (unlike in Mobile Ad Hoc Networks, MANET‘s)

■ WMN‘s have properties of an autonomic system:

Full mesh: each node
- Self-Configuration
is directly connected
to all other nodes - Self-Healing (redundant, decentralized, no central point of failure)
- Self-Managment
Partial mesh: not all - Self-Optimization
nodes are directly --> Challenging tasks for a good system design
interconnected
■ High overall capacity:
- Spatial diversity
■ Definition of a Wireless Mesh Network (WMN): - Power management

In short: Multi-hop network built from wireless routers Important constraints:

- Shared bandwidth & interference
- Number and location of nodes
More detailed: Multi-hop peer-to-peer wireless network in which nodes connect with
redundant interconnections and cooperate with one another to route packets

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 5 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 6 of 45

Application Scenario Application Scenario

Broadband Internet Access (last mile) Community Mesh Network

ADSL

Backbone Middle Mile Last Mile

Cable

■ Wired infrastructure often too expensive for last and middle mile:
- Rural areas
- Weakly populated countries
■ Cost factors in wired infrastructure:
- Number of endpoints
- Cable costs (length, unfriendly terrain) WiMAX
WiMAX ADSL
■ Issues in wireless solutions: Cablemodem
- Range and bandwidth (mesh networking is the key) Mesh network
Mesh infrastructure owned by participants Wholesale local loop
- Costs and maintenance requirements of hardware

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 7 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 8 of 45

Application Scenario Application Scenario
City-wide Wireless Coverage (Blanket) Spontaneous Mesh Network
■ Temporary mesh network for collaboration (usually with portable wireless devices)
■ Scenarios:
Example: Roofnet Project

- 802.11b mesh network Real-time advisory

- volunteer user host nodes (e.g. traffic information)
- omnidirectional antennas
- only up/downlink to wired
ethernet
- goal: high TCP throughput
(average realized 627 kbps,
routing queries failed for
Public safety
10% of source-destination
(emergency teams, fire, rescue)
pairs)

Peer-to-peer calling within

local groups (events, university campus, conference

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 9 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 10 of 45

Application Scenario RF Communications Basics

Industry Breakdown Transmission Formula (ideal conditions)
Neighborhood Mesh Network Wireless mesh based
Internet broadband access
101
architecture:
Bus Stop
206

Gas Station
Master node: connects Transmitter Receiver
(Internet TAP)
to wired internet
Mesh Router 7
Mini base station: mesh ■ Friis transmission formula (free space, ideal isotropic antennas):
router rented to subscriber 2
c
P r = -------------------- ˜ P t [1]
Franchising: system and 2
EXIT 90
4 S df
business model rented to
Mesh Router 5
local service provider
Mesh Router 2 Pr: Signal power available at receiver antenna output [W]
Mesh Router 3 (usually as a „side busi- Pt: Signal power fed to transmitter antenna input [W]
Mesh Zone
ness“) d: Distance between antennas [m]
Mesh Router 1
End Device f: Frequency [Hz]
Mesh End Device (Guest to Router 1) [image source: V. Bahl, MSR] c: Speed of light (3 x 108 m/s)

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 11 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 12 of 45

Multipath Fading and Shadowing Transmissions under Non-ideal Conditions
Effects to consider
■ Distance between transmitter and receiver (Friis transmission law): Path loss
■ Receiver sensitivity: Thermal noise
■ Multipath fading: Reflection (eg. ground, buildings, water surface), diffraction, refrac-
tion
■ Shadowing: Absorption (e.g. walls, buildings, rain, windows)
LOS (Line-Of-Sight) ■ Interference: same source or different source
- May annihilate signal (same frequency & amplitude, 180o fixed phase relation)
- May amplify signal (same frequency, 0o fixed phase relation)

NLOS (Non Line-Of-Sight)

■ Multipath fading: diffraction, reflection, scattering

- May be caused by other radio sources (e.g. microwave oven, WLAN, WPAN)
■ Shadowing: absorption ■ Technical: Antenna Gains, Cable Losses

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 13 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 14 of 45

Communication Range Calculations Communication Range Calculations

Use of the Decibel (dB) Strength of received signal
■ Ratio between two quantities expressed by a dimensionless logarithmic unit [dB] ■ Receive signal strength expressed in dBm (non isotropic antennas):
■ May be used in different application areas (acoustics, physics, electronics)
P r > dBm @ = P t > dBm @ – L fs > dB @ + G t > dBi @ + G r > dBi @ [2] „Link Budget“
■ Usage in calculations for RF communications:
Ratio between two power values = 10 log10(P2/P1)
Pr: Signal power available at receiver antenna output
■ Special use: [dBm] = Power level relative to a reference value of 1 mW Pt: Signal power fed to transmitter antenna input
Lfs: Free space loss
Gt, Gr: Gain of transmit antenna, of receive antenna
Examples:
- Typical 802.11 receiver sensitivity -60...-80 dBm
- Typical 802.11 maximum transmitter power ~14 dBm ■ Path loss (free space)
- Typical minimal Signal-to-Noise (S/N, SNR) values for BPSK modulation ~6 dB
§ Pt · 4 S df
L fs > dB @ = 10 ˜ log ¨ ------¸ > dB @ = 20 ˜ log § ------------· > dB @ [3]
■ Special use: [dBi] = Antenna gain relative to an isotropic antenna (one-point source) © P r¹ © c ¹

Examples: 2 dBi (simple antenna), 5 dBi (omnidirectional), 18-27 dBi (parabolic) d: Distance between antennas
f: Frequency
c: Speed of light

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 15 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 16 of 45

Communication Range Calculations Antenna Types
■ Maximum usable communication range is given by: ■ Many different forms:
- Signal strength at receiver - omnidirectional radiation pattern
- Noise level at receiver - sectorial radiation pattern
- Minimum required S/N (given by modulation and coding used) - directive radiation patterns

■ Antenna: reciprocity property

■ Signal-to-Noise Ratio (SNR):
(same behavior for transmit/receive)
SNR > dB @ = P r > dBm @ – N > dBm @ [4]
■ Basic reference is ideal isotropic antenna
■ Thermal noise level: (radiates equally in all directions)
N = k B ˜ T ˜ fbw > W @ [5a] ■ Antenna gain: expressed in dBi relative to
kB: Boltzmann‘s constant [J/K]
an ideal isotropic antenna
T: Temperature [K] ■ Example „Cantenna“:
fbw: Bandwidth [Hz]
- Uses a tin can as a wave guide
- Cheap solution for developing countries
■ Formula for room temperature (20o C equiv. 293 K) for a non-ideal receiver:

N > dBm @ = – 174 + 10 ˜ log f bw + NF [5b]

NF (Noise Figure): Ratio of actual receiver noise to ideal receiver noise

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 17 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 18 of 45

MIMO (Multiple-Input Multiple-Output) Antennas Communication Range and Modulation/Coding

■ Maximum communication range is given by minimal required S/N
MIMO SIMO MISO
■ Minimal required S/N is determined by an acceptable BER (Bit Error Rate)

Modulation scheme and code

rate determine SNR re-
quirements

Modulation schemes (e.g. 802.16):

■ MIMO is a promising multi-antenna systems approach to: BPSK: Binary Phase-shift keying
- increase link capacity (eg. 802.11n) QPSK: Quadrature Phase-shift
- improve robustness Keying
- benefit from „constructive“ interference QAM: Quadrature amplitude
- avoid „destructive“ interference modulation

■ MIMO allows for: FEC (Forward Error Correction):

- multiple radio links (spatial multiplexing) Code rate = useful bits/total bits
- space-time coding e.g., code rates in 802.16:
- beamforming 1/2, 2/3, 3/4

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 19 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 20 of 45

Adaptive Modulation and Coding Overview: Spectrum Usage Regulations
■ Constellation diagram: shows a digital modulation scheme in the complex plane ■ Government regulations restrict frequency spectrum usage
--> distances between constellation points are a measure for „robustness“
■ Regulations are not equal in all countries (e.g. Europe, USA, Asia)
■ Examples:
■ Frequency spectrum is „overloaded“
BPSK QPSK 16QAM
- For example the 2.4 GHz band („junk band“):
, ,
,
WLAN 802.11b&g, WPAN 802.15 Bluetooth, 15.245 sensors, Part18-ISM, amateur, ....
- For example the 5.8 GHz band:
WLAN 802.11a, WiMAX 802.16a, 15.209 generic unlicensed, satellite, aviation,...
Adaptive modulation and coding: Switch between modulation/coding scheme based on actual SNR
■ Regulations differentiate between „licensed“ and „unlicensed“ spectrum usage
Coverage Area Capacity

available SNR

r min. SNR

r (radius) 2.4 GHz Band (USA) 5.8 GHz Band (USA)

Optimization: automate adaptation (SNR-based, packet loss-based, ...)

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 21 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 22 of 45

CSMA and Wireless Communication CSMA and Wireless Communication

The Collision Detection Problem The Hidden Terminal Problem

Wired ethernet

B A B C
A B C Wireless LAN

A C

■ A wants to send to B: if the channel is clear then the transmission starts

■ Example CSMA/CD situation:
- A and C both want to transmit ■ C wants also to send (A is still sending) and checks if channel is free
- If channel is idle, then both A and C start to transmit --> Collision
■ Since C can not hear A it assumes the channel is free
■ Wired Ethernet: A and C detect collision during sending (stop and backoff) --> Collision at B!
■ Wireless LAN: Sender cannot detect collision during sending (technically not feasible)
■ A is a hidden station (hidden terminal) from the viewpoint of C

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 23 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 24 of 45

CSMA and Wireless Communication MACA (Multiple Access Collision Avoidance)
The Exposed Terminal Problem D RTS A RTS B C

CTS CTS
B
DATA
D C A

■ Before a data transmission starts a RTS/CTS handshaking is done

■ Example: A wants to send data to B
- A waits until the channel is clear
- A announces its transmission intent with a Request-To-Send (RTS)
- The addressed node B responds with a Clear-To-Send (CTS)
■ A starts a transmission to B - A transmits the data
■ C detects an occupied channel and waits with its transmission to D (until A-->B ends) ■ Behavior of C and D in this example:
- The RTS and CTS PDU‘s contain the length of the transmission
■ Since D cannot receive A this waiting is not really necessary - Hidden node C overhears the CTS and does not send during A‘s data transmission
- Exposed node D overhears RTS (but not CTS) and may send if he wants
(NB: depending on WLAN standard this may be treated alike a CTS reception)

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 25 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 26 of 45

Backoff Procedure Carrier Sense in Wireless Systems

RTS RTS RTS

Physical Carrier Sensing
D A B C
■ Done at the air interface
(CTS) (CTS) ■ Carrier sensing by CCA (Clear Channel Assessment):
--> Process of detecting transmitting stations inside of the CCA detection range

■ Channel access: ■ CCA detection range depends on detector implementation

- before transmission choose a backoff time tb in the range (0, cw); cw = contention window
- count down tb when channel is idle ■ Interference may be interpreted as non-clear channel
- suspend countdown when channel is busy
- when tb=0 then start transmission Virtual Carrier Sensing
■ Collision example: A and C want to send data to B ■ Done at the MAC layer
- A and C send both RTS to B at the same time --> collision at B!
- A and C can not detect collision during sending ■ Transmission duration info is extracted from MAC PDU header of RTS/CTS
- B will not send CTS --> A and C back off
■ Stations use so-called NAV (Network Allocation Vector) to store reservation periods
■ Binary exponential backoff:
- each time expected CTS is not received: cw is doubled (up to a maximum size cwmax) ■ NAV reservation periods represent a virtually detected carrier
- upon each successful transmission cw is restored to cwmin ■ For carrier sensing both methods are combined in an OR‘ed fashion

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 27 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 28 of 45

Communication and Interference Range Lost Packet Detection

Interference
range D RTS A RTS B C
ri
A B CTS CTS

DATA
rc
ACK

Communication range
■ Typical reasons for packet loss:
- poor signal quality (path loss, multipath fading, scattering, absoprtion, ...)
- interference
■ Example: A transmits to B
■ Communication range rc: Area for possible communication links - Transmission is successfully completed when A receives ACK
- a missing ACK would cause a timeout and a retransmission
■ Interference range ri: Area of interfered stations - Announced transmission time includes ACK (NAV reservation covers RTS/CTS,DATA,ACK)
■ ri/rc ratio: depends on radio technology, typical values are 1.5 - 3
■ MACAW (Multiple Access Collision Avoidance for Wireless LAN):
■ rc, ri may vary between stations (eg. A hears B, but B does not hear A) - extends basic MACA sequence by ACK

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 29 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 30 of 45

Dynamic TDMA Multi-hop wireless networking

■ TDMA (Time Division Multiple Access)
- used in circuit switched networks Historical perspective
- examples: GSM, DECT ■ DoD: Battlefield communications in infrastructureless hostile environments
■ Dynamic TDMA: - PRNET (Packet Radio Network) 1972 - 1983
- alternative to CSMA/CA in wireless networks - SURAN (Survivable Adaptive Radio Network) 1983 - 1992
- dynamically assigns a variable number of time Characteristics (both): Combined Aloha & CSMA, distance vector routing,
slots per frame to each data flow frequency 1.78 - 1.84 GHz, data rates 100..400 kbps
- combines characteristics of circuit switching
and packet switching ■ DoD: Office environment multimedia communications with handheld devices
- data flows may differ in guaranteed capacity - GloMo (Global Mobile Information Systems) 1995 - 2000
(and other QoS properties) Characteristics: CSMA/CA and TDMA, several routing and topology control schemes,
frequency 225-450 MHz, data rate 300 kbps
■ Dynamic TDMA application examples:
- 802.16 (WiMAX), combined with TDD ■ IETF: „ad hoc networks“
(Time Division Duplexing) or FDD (Frequency - Mobile ad hoc networking (MANET) working group, since 1997
Division Duplexing)
- 802.15 (Bluetooth), combined with FHSS ■ IEEE:
(Frequency Hopping Spread Spectrum) - 802.11s working group, since 2004

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 31 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 32 of 45

Mesh formation guidelines & results Performance: Packets in Flight Problem
RTS RTS

1 2 3 4 5 6 7 8 9 10 11
■ Problem:
How many nodes have to sign up RTS RTS
before a viable mesh network forms? 1 2 3 4 5 6 7 8 9 10 11
■ Answer: Depends on CTS CTS
- Interpretation of „viable“ RTS RTS RTS RTS RTS
- Topology 1 2 3 4 5 6 7 8 9 10 11
- Wireless range
- Probability of participation Zeit CTS CTS

Backoff window doubles

■ Experimental results for mesh forma-
tion (MS Research):
■ Using MACAW (Multiple Access Collision Avoidance for Wireless):
- at least 5-10% subscription rate re- - Step 1: RTS 3-> 4 (inhibits 2), RTS 9-> 8 (inhibits 10)
quired with wireless ranges > 100 m - Step 2: CTS 4-> 3 (inhibits 5), CTS 8->9 (inhibits 7)
- if a mesh forms, then it is typically 0 20 40 60 80 100 120 140 160 - Step 3: RTS 1->2 (can‘t proceed), RTS 11->10 (can‘t proceed), RTS 6->5 (can‘t proceed)
well connected (node degree > 2) ■ 2 packets in flight
- increasing range is a key for ■ Only 4 out of 11 nodes are active
good mesh connectivity [image source: V. Bahl, MSR] ■ Backoff algorithm hurts (binary exponential backoff)

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 33 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 34 of 45

Performance: Path Length Problem Performance: Power Control Problem

■ Example situation:

A B C
1 2 3 4 5 6
D

■ Reducing transmit power decreases interference (eg. C does not interfere with B)
■ Traffic flow through chain (starting from node 1)
--> Increases throughput
■ Sending node 1 has least interference resulting in highest throughput
■ However: Collision at C when B and D transmit simultaneously

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 35 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 36 of 45

Performance: Power Control Problem Routing in Wireless Mesh Networks
■ Solution for example situation
- Reduced transmit power for B Differences to Wired Networks
- Collision problem solved ■ Topology changes related to environmental fluctuations
- However: network disconnected - new nodes may join
--> What power setting is optimal? - nodes may leave network
B C - link qualities may vary over time (movement)
■ Implementation issues: A
--> Dynamics may prevent convergence of routing algorithm
- Set all nodes to same power level? D
- Tune each node at deployment time? ■ Limited bandwidth and battery life
- Use equipment capable for automatic
--> periodic updates are unattractive
power control? Availability?
- Use directional antennas? ■ Partly unidirectional links
--> computed routes may not work

■ Many redundant links

--> increase routing updates

■ Additional factors to consider for path selection

- link quality (stability, BER, bandwidth, ...)
- interference

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 37 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 38 of 45

Taxonomy Addressing
■ Pro-active (table-driven) ■ Flat addressing
- routes are learned and spread out - node address independent of location
- typically periodic updates - each node runs routing protocol

■ Reactive (on-demand) ■ Hierarchical addressing

- discover routes only when needed - a subnet per cluster
- overhead scales automatically with movement - nodes acquire address of subnet
- only cluster heads run routing protocol
■ Hybrid (Pro-Active/Reactive)
■ Clustering
■ Hierarchical - node address independent of location
- only cluster heads run routing protocol
■ Geographical
■ Each wireless routing protocol is related to a particular addressing scheme
■ Power aware

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 39 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 40 of 45

Path Selection Metrics AODV (Ad hoc On-demand Distance Vector)
■ Minimal hop count metric often not optimal ■ Popular but still experimental routing protocol (IETF RFC 3561)
- wireless links often vary in quality
■ Routing problem divided into two parts: route discovery and route maintenance
■ Link metric: assign weights to links
- weights derived from low rate, available bandwidth, ... ■ Route discovery: on-demand when packets have to be routed

■ Path metric: combine all link metrics on path ■ Route maintenance: when routing failures (packet loss) occur
- prefer short paths
■ Sequence numbers:
■ Metrics: - route freshness
- hop count - loop prevention
- ETT (Expected Transmission Time)
■ Routing tables at nodes:
- ETX (Expected Transmission Count)
- WCETT (Weighted Cumulative ETT) - routes are stored as long as routes are active
- timeouts: mark route(s) as inactive

■ Two-dimensional routing metric: hop count, sequence number

■ Basic routing messages:
- RREQ (Route Request)
- RREP (Route Reply)
- RERR (Route Error)

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 41 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 42 of 45

AODV (Ad hoc On-demand Distance Vector) Summary

Route discovery: ■ A wireless mesh network is a multi-hop network built from wireless routers and has
properties of an autonomic system
■ Wireless mesh networks have promising application areas, e.g.
- broadband internet access (last mile)
- community mesh networks
- city-wide wireless voverage (blanket)
- spontaneous mesh networks
- industry breakdown

■ The wireless communication range can be calculated exactly in theory, but in practice
the topology of the terrain has often a limiting influence
■ Advanced wireless systems use adaptive modulation/coding schemes to leverage
RREQ range and capacity for optimum performance
RREQ rebroadcast
■ Wireless networks may use several channel access schemes (CDMA/CA, MACAW,
RREP
RREP rebroadcast TDM, ...), which are clearly different from wired solutions
Reverse route
■ Wireless mesh networks have evolved over more than 30 years and allow to build up
Forward route
viable networks if the communication range and node density fit reasonably

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 43 of 45 ¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 44 of 45

Summary (2)
■ The performance of a wireless mesh network is degraded when using long paths and
in the case of interfering nodes
■ The routing in wireless networks is different from wired networks because of:
- topology changes related to environmental fluctuations
- limited bandwidth and battery life
- partly unidirectional links
- many redundant links
- link quality

■ Wireless mesh routing protocols may be classified into the following categories:
- pro-active (table-driven)
- reactive (on-demand)
- hybrid (pro-active/reactive)
- hierarchical
- geographical
- power aware

■ The AODV routing protocol uses on-demand route discovery and is resilient by doing
route maintenance in case of routing failures

¤ E. Glatz ATCN: WMN-BasicsWS0607.fm 45 of 45