Transcript wireless mesh networks

WIRELESS MESH NETWORKS
Ian F. AKYILDIZ* and Xudong WANG
* Georgia Institute of Technology
BWN (Broadband Wireless Networking) Lab &
** TeraNovi Technologies
10. STANDARDS
2
Standards related to WMNs
IEEE 802.11s
IEEE 802.15.1
IEEE 802.15.4
IEEE 802.15.5
IEEE 802.16a
3
Standard Activities:
IEEE 802.11 Mesh Networks
– Currently, IEEE 802.11 wireless networks can achieve a
peak rate of 11 Mbps (802.11b), 54 Mbps (802.11a/g),
and 600 Mbps (802.11n draft)
– 802.11n is still under development for higher speed
– Researchers expect 802.11n to increase the speed of
Wi-Fi connections by 10 to 20 times.
4
IEEE 802.11 Mesh Networks
– Protocols for 802.11 ad hoc mode are insufficient for
multi-hop and mesh networking, because of lack of
scalability in the MAC protocol, resulting in poor network
performance.
– A working group within IEEE 802.11, called 802.11s, has
been formed recently to standardize Mesh Networks
5
IEEE 802.11s:
Mesh Networking
Started in May 2004
802.11a/b/g were never intended to work
multi-hop
Target application:
extended 802.11 coverage
6
IEEE 802.11
– The infrastructure of each basic service set (BSS) is
connected via Ethernet LANs
– Such a fixed network architecture limits the flexibility
of network deployment and increases cost.
– Thus, mobility of BSS and multihop networking are
needed.
7
IEEE 802.11:
IBSS Mode (Ad Hoc Networking)
– Ad hoc networking has been specified in the independent basic service
set (IBSS) mode.
– Stations (STAs) can connect to each other without any central
coordinator like access point (AP).
– Moreover, there is no access or connection to the distributed system (DS).
– STAs are totally self-contained as an ad hoc network.
– Such as an operation mode has been researched in the field of ad hoc
networking.
8
IEEE 802.11: IBSS Mode
However, the IBSS mode is not enough for many
interesting application scenarios
where ad hoc networking is needed but Internet
access and support of client nodes are also
necessary
 Both infrastructure mode and IBSS mode shall
be integrated in a new type of multihop networks.
9
IEEE 802.11s:
Common Principles
X. Wang and A. Lim, “IEEE 802.11s Wireless Mesh Networks: Framework
and Challenges,’’ Ad Hoc Networks Journal, vol. 6, no. 6, pp. 970-984,
Aug. 2007.
 The network usually includes three types of nodes
– Mesh routers, clients, and gateways.
 An ad hoc routing protocol is implemented in mesh
routers to work together with 802.11 MAC.
 Certain radio aware functions may be included in the
routing protocol.
10
IEEE 802.11s:
Common Principles
 802.11 MAC driver is enhanced in mesh routers to improve
multi-hop performance.
[Typical examples]: fine-tuning CSMA/CA parameters, developing
algorithms for multi-radio or directional antennas, etc.
 Certain network configurations are needed to support
client access, Internet access, roaming, and so on.
11
Network Architecture of 802.11s:
Meshed Wireless LANs
Basic Concept
– A meshed wireless LAN is formed via ESS mesh
networking. i.e., BSSs in the DS do not need to be
connected by wired LANs
– Instead, they are connected via mesh networking possibly
with multiple hops in between
– Portals are needed to interconnect 802.11 wireless LANs
and wired LANs.
12
Network Architecture of 802.11s:
Meshed Wireless LANs
13
IEEE 802.11s:
Device Classes in a WLAN Mesh Network
STANDARDS
14
Network Architecture of 802.11s:
Meshed Wireless LANs
Three new nodes in this architecture
– A mesh point (MP) is an 802.11 entity that can support
wireless LAN mesh services
– A mesh access point is an MP but can also work as an
access point
15
Network Architecture of 802.11s:
Meshed Wireless LANs
– A mesh portal is a logical point where packets enter and
exit the mesh network from and to other parts of the
system such as a traditional 802.11 LAN or from and to
a non-802.11 network
– Mesh portal includes the functionality of MP. It can be
co-located with an 802.11 portal
16
IEEE 802.11s:
Device Classes in a WLAN Mesh Network
17
Network Architecture of 802.11s:
Protocol Stacks
 802.11s MAC is developed based on
existing 802.11 MAC for a MP (or
the MP module in a MAP or mesh
portal).
 Mesh routing protocol of a MP (or
the MP module in a MAP or mesh) is
located in the MAC layer.
 In a mesh portal, a layer 3 routing
protocol is also needed for path
selection from the mesh network to
external network or vice versa
18
Topology Formation/Discovery:
Discovery and Formation of Mesh Networks
 When a new mesh node powers up, it may use passive or
active scanning to discover a mesh network.
 In 802.11s, a new ID, called mesh ID, is used to identify
a mesh network.
– The mesh ID is attached in beacons and probe response frames
as a new IEs for passive and active scanning, respectively.
– One of the reasons is that a mesh ID can prevent STAs from
being associated with MPs without AP functionality.
19
Topology Formation/Discovery
Discovery and Formation of Mesh Networks
 Before a new mesh node associated with a mesh network
identified by a mesh ID, it needs to check if its mesh profile
matches the established mesh network.
 Each mesh device must support at least one profile consisting
of a mesh ID, a path selection identifier, and a path
selection metric identifier.
 If such mesh capability information in a mesh node matches
that in the mesh network, it will start association.
20
Topology Formation/Discovery:
Mesh Peer Link Establishment
 Once a mesh node has joined a mesh network and before it can start
sending packets, it needs to establish peer links with its neighbors.
 In 802.11s, state machines and detailed procedures have been
specified for setting up peer links.
 Once this step is completed, it is also necessary to establish a
measure of link quality for each peer link.
21
Topology Formation/Discovery:
Multi-Channel Topology Formation
Single-channel mode
– A mesh device just selects one channel during the
discovery process.
Multi-channel mode
– A mesh node needs to select multiple channels for its
multiple radios or for channel switching if single radio is
supported.
22
Topology Formation/Discovery:
Multi-Channel Topology Formation
 In order to manage the topology in a multi-channel mesh
network, the concept of unified channel graph (UCG) is used
– In a UCG, all devices are interconnected using the common
channel.
– Thus, in a single-channel mesh network, then entire
network has only one UCG.
23
Topology Formation/Discovery:
Multi-Channel Topology Formation
– For a multi-channel mesh network, the number of UCGs
depends on a self-organization of the network
– In the same UCG, the channel precedence value is the
same for all devices
– Such a value is different in different UCGs, and is used
for coalesce or switching the channel in UCGs
24
Topology Formation/Discovery:
Multi-Channel Topology Formation
A simple channel unification protocol and a
simple channel graph switching protocol were
specified in IEEE 802.11s draft.
25
Topology Formation/Discovery:
Multi-Channel Topology Formation
– However, such mechanisms are only applicable to simple
scenarios such as slow channel switching, e.g., DFS, is
only needed.
– If dynamic and fast channel switching is needed, the
UCG concept and its supporting procedures in the
current 802.11s draft may be too insufficient to be
useful.
26
Routing
Previously many proprietary 802.11 mesh
networks are built using different routing
protocols
which resulted in interoperability problems
27
Routing
In 802.11s, the framework for routing is extensible,
which means that different routing protocols can be
supported by following this framework
– But the mandatory protocol shall be implemented in
order to achieve interoperability.
28
Routing
Routing mechanism in 802.11s handles packet
forwarding for MPs, MAPs, and associated STAs.
Unicast, multicast, and broadcast frames are all
supported in the same framework.
29
Routing
– Since routing is performed in the MAC layer, packet
forwarding is carried out via MAC addresses,
which requires the MAC header contains at least 4 MAC
addresses.
– Compared to the previous MAC protocol, the two additional
MAC addresses are for the MAC addresses of the source
and the destination of an end-to-end flow.
30
Routing in Current 802.11s
 One mandatory routing protocol:
Hybrid Wireless Mesh Protocol (HWMP)
(hybrid of “on demand routing” and “proactive tree-based routing”)

One optional routing protocol
based on link state routing called
“radio aware optimized link state routing (RA-OLSR)”
31
Overview of Demand Routing Protocol
– In HWMP, on demand routing protocol is adopted for nodes
that experience a changing environment
while proactive tree-based routing protocol is an efficient
choice for nodes in a fixed network topology
– Mandatory routing metric is airtime cot which measures the
quality of links.
32
Overview of Demand Routing Protocol
– More types of metrics such as QoS parameters, traffic
load, power consumption, and so on can also be considered
– However, in the same mesh, only one metric shall be used.
– The on-demanding routing protocol is specified based on
radio-metric AODV.
33
Overview of Proactive tree-based routing
– Applied when there is root node configured in the mesh
– With this root, a distance vector tree can be built and
maintained for other nodes
– Such routing protocol can avoid unnecessary routing
overhead for routing path discovery and recovery
34
Routing:
HWMP
On-demand routing and tree-based routing can run simultaneously.
Four control messages
–
–
–
–
Root announcement (RANN),
Route request (RREQ),
Route reply (RREP), and
Route error (RERR).
35
Routing:
HWMP
– Except for RERR, all control messages contain three important fields:
* Destination sequence number (DSN)
* Time-to-live (TTL), and
* Routing Metric.
– DSN and TTL can prevent the counting to infinity problem,
– Routing metric helps to find a better routing path than just using hop
count
36
Routing:
HWMP: Procedures for On-Demand Routing
– A source MP broadcasts RREQ to set up a route to a
destination MP
– When an intermediate MP receives RREQ, it
creates/updates a route to the source if the sequence
number of the RREQ is greater than the previous one or
the sequence number is the same but the metric is better
– If the intermediate MP has no route to the destination, it
just forwards the RREQ message further.
37
Routing:
HWMP
 There have different cases depending on two flags: destination
only (DO) flag and reply and forward (RF) flag.
– If the DO flag is set to 1
then the intermediate MP does nothing but just forwards the
RREQ to the next-hop MPs until the destination node.
– Once the destination node gets this message, it sends a unicast
RREP back to the source MP.
– All intermediate MPs create a route to the destination when
receiving this RREP message.
38
Routing:
HWMP
– If “DO flag = 0” and “RF flag = 0”,
intermediate MP sends a unicast RREP message to the source
node and does not forward RREQ.
– If “DO flag = 0” and “RF flag = 1”,
intermediate MP sends a unicast RREP message to the source
node; additionally, it needs to set the RF flag into 0 and
then forwards the RREQ message to the destination node.
 Subsequent intermediate MPs will not be able to send RREP messages
to the source node.
39
Routing:
HWMP
REMARK:
“DO flag = 0” and “RF flag = 1” only when the source node
has no valid route and wants to create a new route to the
destination node.
 As compared to the original AODV protocol, the above
procedures have been modified for HWMP.
40
Routing:
HWMP: Procedures for the proactive treebased routing mode
Two mechanisms:
* Based on proactive RREQ
* Proactive RANN.
41
Routing:
HWMP: Procedures for the proactive
tree-based routing mode
Proactive RREQ mechanism
– The root MP periodically broadcasts the RREQ messages.
– An MP in the mesh receiving the RREQ
* creates/updates the path to the root,
* records the metric and hop count to the root,
* updates the RREQ with such information, and
* then forwards RREQ.
42
Routing :
HWMP
Proactive RANN mechanism
– The root periodically floods a RANN message into the
network.
– When an MP receives the RANN and also needs to
create/refresh a route to the root, it sends a unicast
RREQ message to the root.
43
Routing :
HWMP
– When the root receives this unicast RREQ, it replies with
a RREP to the MP.
 The unicast RREQ forms the reverse route from the
root to the originating MP,
while the unicast RREP creates the forward route from
the originating MP to the root.
44
Routing:
RA-OLSR
 A proactive link-state routing protocol that is developed
based on OLSR*.
* T. Clausen and P. Jacquet, “Optimized link state routing
protocol (OLSR)”, IETF RFC 3626, 2003
 To reduce flooding overhead, several extensions are made
45
Routing:
RA-OLSR
1) Only a subset of one-hop neighbors of an MP is
selected to relay control messages.
– Such neighbor MPs are called multipoint relays (MPRs)
– MPRs are selected such that control messages relayed by them can
reach all two-hop neighbors of the selecting MP.
– MPR selection is performed through periodic HELLO messages
between MPs.
46
Routing:
RA-OLSR
2) To provide shortest routes, RA-OLSR requires
only partial link state information to be flooded
- The minimum set of links are the links between the MPRs
and their selectors.
47
Routing:
Support of Legacy Nodes
For packets transmitting between legacy nodes via
the mesh network,
the routing protocol inside the mesh may need the source
and the destination MAC addresses of a legacy node
Thus, two additional MAC addresses are added into
the MAC header
– This is the mechanism of 6-address scheme specified in 802.11s
48
Routing:
Support of Legacy Nodes
Other than this mechanism, the routing protocol of
the mesh also needs to handle legacy nodes.
– E.g., the association of legacy nodes with a MP shall be
efficiently handled such that a routing path can be found
for legacy node to send packets via the mesh network.
In the current draft of 802.11s, this part of
functionality has not been fully specified.
49
MAC
 Basic operation mechanism of 802.11s MAC is
the enhanced distributed channel access (EDCA) specified in 802.11e.
 Other features of 802.11e such as HCCA are not adopted into 802.11s.
– QoS of 802.11s in its current form is still far from enough for
multimedia services
50
MAC
 Moreover, EDCA does not work well for mesh networks,
since its prioritization mechanism does not perform well in
a multihop mesh environment.
 Nevertheless, the current 802.11s MAC protocol is built
on top of EDCA with various enhancements.
51
MAC
Multi-Channel Operation
 Multichannel operation is important to WMNs.
– However, no mechanism has been specified in 802.11s.
– In the beginning, a proposal called common channel
framework (CCF) was adopted
into earlier versions of the draft (before draft 1.0).
– However, because of many problems that were not
resolved effectively, this CCF proposal was removed
from the draft
52
MAC
Multi-Channel Operation
Common Channel Framework
– Nodes that want to use multi-channel operation need to
negotiate its channel in the common channel
 The common channel is known to all nodes in the mesh
network.
53
MAC
Multi-Channel Operation
A transmitter first sends an RTX message to request a channel.
The receiver sends back a CTX to confirm the requested check.
If RTX-CTX is successful, then a channel is selected for these
two nodes.
Thus, both nodes switch to the selected channel and exchange
data following the data/ack procedure.
54
MAC
Mesh Deterministic Access
 Mesh deterministic access (MDA) allows MPs to access a
certain period with lower contention than other periods
without using MDA.
– Such a period is called MDA opportunity (MDAOP)
– Before using MDAOP to access the medium, the owner of this
MDAOP, i.e., the transmitter needs to set up the MDAOP with its
receiver.
55
MAC
Mesh Deterministic Access
 In the MDA mechanism, two types of time periods are defined
– RX-TX times: The neighborhood MDAOP times of an MP are the
RX-TX times in which the MP and its neighbors are either a
transmitter or receiver of these MDAOPs.
– Neighbor MDAOP interfering times: For a neighbor of this MP,
it also has such time periods, but to the MP, these times are
called neighbor MDAOP interfering times.
56
MAC
Mesh Deterministic Access
 When an intended transmitter wants to set up a new
MDAOP to an intended receiver, it needs to check
* its neighbor MDAOP times,
* the TX-RX times for other frames, and
* the neighbor MDAOP interfering times for the intended receiver.
 If no overlapping occurs and the MDA limit is not reached,
then the transmitter sends an MDAOP setup request to the
receiver.
57
MAC
Mesh Deterministic Access
 Receiver will do the same check.
– If the check is passed, the receiver accepts the MDAOP;
Otherwise, it rejects.
 Once the MDAOP is setup, both the transmitter and the
receiver will start to advertise their new MDAOP time in
the MDAOP advertisement IE.
 Both the transmitter and the receiver can initiate the
teardown process to release the MDAOP time period.
– The teardown is complete once the initiator is acked by the
receiver.
58
MAC
Intra-Mesh Congestion Control
An 802.11 mesh usually has multiple hops.
– The transmission of one hop may impact its previous hop, the next
hops, or any links in the neighbors.
– Links may be congested, and thus a node with congested links may
receive more packets than that can be sent out.
TCP can help mitigate this problem
– But not effective enough in a wireless multihop network.
59
MAC
Intra-Mesh Congestion Control
 On the other hand, contention resolution can also help
reduce congestion.
– However, in a mesh network, the contention level experienced by
different nodes is different, which make a contention resolution
protocol ineffective.
 For these reasons, intra-mesh congestion control is
specified in 802.11s.
– The intra-mesh congestion control is hop-by-hop scheme.
60
MAC
Intra-Mesh Congestion Control
 Nodes in the neighbor need to exchange congestion
information and control message in order to resolve
congestion in the network.
 Thus, the scheme consists of three modules:
* local congestion monitoring
* congestion control signaling, and
* local rate control.
61
MAC
Intra-Mesh Congestion Control
In the current draft of 802.11s, some local congestion monitoring
schemes are suggested.
– For example, congestion can be monitored by comparing the
transmitting rate and the receiving rate of packets that need to
be forwarded.
– Queue size can also be used to monitor congestion.
62
MAC
Intra-Mesh Congestion Control
– Once congestion is detected, the congested node will inform its
previous hop nodes by sending a unicast Congestion Control Request
message in the mesh action frame
– Node that receives message shall adjust its transmission rate
according to the locate rate control algorithm.
– Congested node also sends a broadcast message Neighborhood
Congestion Announcement to all its neighbors so that neighbors also
regulate their transmission rate
63
MAC
Intra-Mesh Congestion Control
 Locate rate control at node has not been discussed in
802.11s so far.
 Although congestion control can help improve the mesh
network performance, unfortunately the critical part of this
mechanism such as target rate computation and local rate
control algorithm have not been clearly specified yet;
– Only simple conceptual discussions are available in the draft of
802.11s.
64
MAC
Power Management
 Many nodes in 802.11s mesh networks always work in an
active state since they either need to be an AP or forward
traffic for other nodes.
 However, there are still other nodes that need to work in
power save mode.
– E.g., lightweight MPs or MPs that do not forward traffic for
other nodes.
– STAs associated with a MAP may also work in power save mode
65
MAC
Power Management
ATIM-window based power management scheme
– An MP works in two states: doze or wake state.
– The MP in power save mode needs to wake up during the
ATIM window to receive or send control messages
including beacons.
66
MAC
Power Management
The ATIM window repeats every one delivery traffic
indication message (DTIM) interval.
DTIM is usually equal to multiple beacon intervals.
An MP may also wake up in a scheduled time period negotiated
with other MPs.
In power save mode, packets in an MP need to be buffered
and wait for being sent during the wake state.
67
MAC
Power Management
To initiate the power management in a mesh, the following
procedure shall be used:
– An unsynchronizing MP shall set the values of
* DTIM
* ATIM window
* beacon interval, and
* power management mode.
- Such information is sent in beacon frames.
68
MAC
Inter-networking
 Bridging functions in MPPs in a manner compatible
with IEEE 802.1D.
– MPP needs to send an MPP announcement to the MPs
informing of its presence through IE in management
frames
– On receiving a valid MPP announcement IE, MP checks
the destination sequence number SN
69
MAC
Inter-networking
– If SN < than that of a previous MPP
announcement message, the current message
shall be discarded
– Otherwise, it forwards the message to other
MPs after the portal propagation delay expires
and also the TTL value >0
70
MAC
Inter-networking
–
MAC address and routing metric for this MPP is stored by the MP
– When an MP has packets to send, it first follows the data
forwarding procedures as defined in the routing protocol
– If an intra-mesh route to the destination MAC address cannot be
found, then the MP shall forward all packets to the active MPPs
in the mesh
71
MAC
Inter-networking
 MPP handles both egress and ingress messages
 Egress Message is handled by MPP based on knowledge of
– Dest. inside mesh: Message forwarded to the dest. node
– Dest. outside mesh: Message forwarded to external network
– Dest. unknown: Message forwarded to mesh + external network
 Ingress Message received by MPP from external network
– Dest. known: Message forwarded to the dest. node
– Dest. unknown: Establish a route to dest. Or broadcast
72
MAC
Inter-networking
 Node mobility scenarios handled in 802.11s
 Node moves from the LAN outside the mesh to another LAN outside
the mesh
–
No special action is needed and handled by 802.1D bridging
 Node moves within the mesh network
–
Handled by the routing protocol
 Node moves within the mesh network to outside the mesh
–
Routing protocol needs to repair path after detecting the route is changed
 Node moves from outside the mesh to inside the mesh
–
Both MPP functionality and routing protocol cooperate to build the new routing
path
73
MAC
Inter-networking
 MPP supports 802.1D bridging and VLAN functionality
– VLAN tag information defined in IEEE 802.1Q must be carried
between MPs and MPPs
– 802.1Q defines two header formats: Ethernet-encoded
formats and SNAP-encoded header
74
802.11s Open Research Issues
 Topology for Multi-Rate Operation and Physical Rate Control
– Measurement is based on the current transmission rate and
transmission error rate (called the airtime cost)
– What packets can be sent and how they are sent are not
specified, leading to measurement inaccuracies
– Eg. frequency of measurement packets and their
transmission rate impact the result of airtime cost
– The packet error rate due to transmission error does not
actually reflect the link quality owing to MAC dependency
75
802.11s Open Research Issues
 Routing Protocol
– Both HWMP and RA-OLSR has several shortcomings
 In HWMP, the proactive tree-based routing is totally
centralized and constrained by the root node
– the routing protocol still routes the packets via the root even
when there is a short path between two MPs
 For RA-OLSR, the overhead of control messages is too high
although Fisheye scope mechanism is adopted
76
802.11s Open Research Issues
 Though both HWMP and RA-OLSR are specified as a routing
module in the MAC layer, interactions with other MAC
functionality are not considered
 Supporting legacy nodes is still an on-going effort
– Such a functionality is not specified in the HWMP, while the
procedures in RA-OLSR incur high overhead
 No support for simultaneous use of multiple routing metrics
77
802.11s Open Research Issues
 Link quality measurement
– 802.11s specifies a framework in which the peer-link setup
takes into account the link quality measurement
– PHY technologies support multiple rates depending on the
selection of different modulation and coding schemes
– For such multi-rate networks, the topology is very sensitive to
the transmission rate that is being used
– No provision for rate-dependent topology control
78
802.11s Open Research Issues
 Multichannel operation
– No provision for multiple channels and single radio
operation
– Switching delay is considerably more than packet Tx
time
– RTX-CTX in the common channel does not avoid
collisions from nodes of other networks/standards in a
new channel
79
802.11s Open Research Issues
 QoS Provision
– The EDCA mechanism (used in 802.11s) provides soft QoS only
– This is useful for providing priority to traffic classes, rather
than actual priority to nodes
80
802.11s Open Research Issues
 Congestion control
– No effective way of congestion monitoring or co-working with
the TCP control mechanism
– The target rate computation method required 1- and 2- hop
node information, no method it is specified to collect such info
– Adjusting EDCA parameters cannot solve congestion problem as
it is more effective for traffic prioritization rather than
ensuring a certain traffic rate

MDA mechanism for reducing contention may also raise
interoperabiility issues
81
802.11s Open Research Issues
 Incorporating multiple MPPs
– In the current framework of 802.11s, single MPP is assumed
– In large scale mesh network (enterprise network) multiple MPPs
are needed to provide backhaul capacity to the Internet
– For multiple MPPs, many functionalities such as interworking
and routing protocols in the current 802.11s draft need to be
modified accordingly.
82
IEEE 802.15 Mesh Networks
 Goal: high throughput personal area networking (PANs)
(~10m or less) with applications in home
 IEEE 802.15.3a standard is based on MultiBand OFDM
Alliance (MBOA)'s physical layer
– Uses ultra wide band (UWB) to reach up to 480 Mbps
– A competing proposal of a Direct Sequence-UWB (DS-UWB)
claims support for up to 1.3 Gbps
– WiMedia Alliance
83
IEEE 802.15.5:
High Rate Mesh Network
WPAN Coordinator
Mesh Link
Star Link
Coordinator
End Device
84
High Rate (HR) Mesh Network
Types of nodes in 802.15.5 WPANs
Pan Coordinator
Initiates network
formation
Coordinator
Connected to each
other as a mesh
network
End Device
Connected to
Coordinator in star
topology
 Motivation for 802.15.5
– Both 802.15.1 scatternet and 802.15.4 are limited to tree
topologies owing to their master-slave architecture
– Problems of poor network coverage, low reliability
85
High Rate (HR) Mesh Network
 802.15.5 Mesh based WPANs target
– Extending network coverage without increasing transmit power
or receive sensitivity
– Enhancing reliability via route redundancy
– Simplifying network configuration
– Increasing device battery life with better transmissions and
fewer retransmissions
 802.15.5 Mesh based WPANs have PHY/MAC and routing
protocol – higher layer specifications absent in 802.15 PANs
86
High Rate (HR) Mesh Network
Applications
Multimedia Home
Networking
e.g., HDTV, DVD,
Interacting gaming
Interconnections among
PCs/peripherals
Interconnections among
PCs/peripherals
 Standards for HR mesh networks must cover
– MAC: Mobility, QoS, beacon management
– Routing : Must balance robustness, reliability, load balancing
– Security: Need for trusted authority
87
PROTOCOL STACK
Frame Convergence Sublayer
Device Management Entity
(FCSL)
(DME)
Mesh Functions
(DME)
mesh routing
Enhancement for mesh
Enhancement for mesh
802.15 MAC
802.15 MAC Management
802.15 PHY
802.15 PHY Management
88
Low Rate Mesh Network

Low Rate Mesh PANs
- Based on 802.15.4b
-Applications include automation + control, monitoring, sensing
location services, entertainment, among others.
- Mainly tree-topology based
Critical Requirements
Reliability
Power Consumption
Large Coverage
89
UWB-Based Mesh Wireless
PANs
UWB-Based Wireless PANs (2
Industrial Consortiums)
WiMedia Alliance
UWB Forum
Physical Layer: Multi-band OFDM
Physical Layer: Direct-sequence
UWB (DS-UWB)
MAC Layer: Developed by itself
MAC Layer: Inherited from IEEE
802.15.3 – follows piconet topology
Multiple beacons possible, allowing
multiple “groups” of nodes
Each piconet has 1 superframe.
Hence, only 1 beacon sent /
superframe
WiMedia Alliance more widely accepted, and also chosen by Bluetooth SIG
90
Pros and Cons of UWB based
mesh networks
 Advantages of using UWB in Mesh Networks
–
–
–
–
Efficient communications
Low-power/cost requirement
Accurate location information
High Bandwidth
* However, these advantages have not been really realized
yet !
 Disadvantage
– Communication range is rather short
91
WiMedia UWB

Standards published by the European association for
standardizing information and communication systems (ECMA)
WiMedia Alliance (December 2005).
-
-
ECMA-368 is a standard on UWB MAC and physical layer
technologies
ECMA-369 is a standard for the interface between MAC and
physical layers specified in ECMA-368
92
WiMedia UWB

Overview of WiMedia UWB Physical Layer
(ECMA-368)
- 3.1–10.6 GHz unlicensed frequency bands
- Data rates of
53.3/80/106.7/160/200/320/400/480 Mbps.
- UWB spectrum is divided into 14 bands, each with
b/w of 512 MHz.
93
WiMedia UWB

OFDM symbol structure
- In each band there are 110 subcarriers (100 data
subcarriers and 10 guard subcarriers) to transmit
information and 12 pilot subcarriers for coherent
detection
- The data is coded by convolution codes and spread
by time-frequency codes (TFC)
94
WiMedia UWB
 TFC code Types:
– Time-frequency interleaving (TFI) : Coded data is interleaved
over 3 Tx bands
– Fixed-frequency interleaving (FFI): Coded data sent over the
same band
 WiMedia UWB MAC
– Superframe consists of 256 medium access slots for a total of
65536 μs
95
WiMedia UWB
 Superframe structure
Beacon Period (BP)
Data Transmission Period
Reservation Period
Prioritized Contention Access
 Beacon Period (BP) has multiple beacon slots
– BP can be further extended to support variable number of
nodes in range
96
WiMedia UWB
 Nodes periodically send BP occupancy IE (BPOIE) in each
beacon
– Allows nodes within two hops to uniquely occupy the beacon
slots
– Reduces beacon collisions
– Based on a multi-beacon BP, beacon groups can be easily
merged as an extended beacon group
97
WiMedia UWB
 Data transmission types
– prioritized contention access (PCA)
– reservation via distributed reservation protocol (DRP)
 PCA Features
– Similar to IEEE 802.11e EDCA
– Used for non-real-time traffic
– Any medium access slots that are not reserved by DRP can be
used for PCA
98
WiMedia UWB
 Types of DRP Reservations
– Alien BP: Reserves medium access slots to protect alien BPs
– Hard: Reserves medium access slots for reservation owner and
target only
– Soft: Permits PCA, but reservation owner has priority access
– Private: Reservation owner and target may use by other access
schemes that are not specified by WiMedia MAC
– PCA: Reserves medium access slots exclusively for PCA
99
Open Research Issues

Standards have not kept pace with technological progress
- Both IEEE 802.15.5 and WiMedia specifications of the MAC protocol for wireless
mesh PANs are far from being completed

Proposed standards protocols lack thorough evaluation
- For both high/low rate wireless mesh PANs, routing protocols are all
tree-based without validating their utility for mesh networks
802.15.5 will only be a recommended practice rather than a
mandatory standard

- Possible interoperability issues
100
Open Research Issues
For WiMedia UWB, the DRP module (handles resource
allocation in a distributed network) does not consider multiple
hops

For
both 802.15.5 and WiMedia Alliance, there is no
provision for cross-layer design between MAC and routing
Multichannel
operation not yet incorporated in the standards
101
IEEE 802.15.1 Bluetooth
 Low data rate (<1 Mbps) PAN technology
 Targets wire replacement
 Piconets formed by master-slave(s)
 Has provisions for multi-hop scatternets with
several masters and slaves
Master
Slave
Single Slave
(Point-to-point)
Multi-Slave
(Point-to-multipoint)
Multi-Slave
(Point-to-multipoint)
Master/Slave
102
Open Research Issues
Bluetooth is not a popular wireless mesh
network platform due to:
– Low bandwidth
– Limited hardware support for scatternets
– Need for more distributed network
architecture support
103
IEEE 802.15.4 Zigbee
 Lower data rate PAN (250,40,20kbps)
 Multi-months – years lifetime on small batteries
 Supports star topology and peer-to-peer multihop mesh
topology
– One coordinator responsible for setting up the network
Full Function Device
Reduced Function
Device
104
IEEE 802.16a WiMax
 April 2003
 Enhances the original 802.16 standard
 Original IEEE 802.16 specifies only point to multipoint
functionality – great for gateway to internet links
 The extensions specifies user-user links using:
– either centralized schedules, or
– distributed schedules.
105
IEEE 802.16a WiMax
 IEEE 802.16a WMAN features
point-to-multipoint
– “mesh mode” in addition to the
point-to-multipoint (PMP) mode
defined in IEEE 802.16.
– Operating in the licensed and
unlicensed lower frequencies of 2–11
GHz, allowing non-line-of-sight
(NLO) communications, spanning up
to 50 km range.
mesh-mode
– Supporting multihop communications.
106
WiMAX Positioning: Capacity and Mobility
Wireless Technology Positioning
Mobility / Range
Fixed
Walk
Vehicle
High Speed
Vehicular
Rural
Vehicular
Urban
Pedestrian
Flash-OFDM
GSM
GPRS
Indoor
Personal Area
UMTS
with limited mobility
HSDPA
EDGE
Nomadic
Fixed urban
WiMAX for wireless-DSL
DECT
WLAN
(IEEE 802.11x)
Bluetooth
0.1
IEEE
802.16e
1
10
IEEE
802.16d
Data rates
100
Mbps
107
MAP OF WIRELESS SYSTEMS
108
More Than 250 Operator Trials and Deployments
in 65+ Countries!
* Other names and brands may be claimed as the property of others
Source: Intel, the WiMAX Forum
109
WiMAX: New Broadband Last Mile

Wi-Fi  for the last one hundred feet (300 ft)
 WiMAX (Worldwide Interoperability for Microwave Access)
 for the last mile (30 miles)
110
WiMAX ARCHITECTURE
111
WiMAX Architecture
1. A WiMAX Tower
(similar in concept to a cell-phone tower; a single
WiMAX tower can provide coverage to a very large
area -- as big as 3,000 square miles (~8,000 sq.km).
2. A WiMAX Receiver
The receiver and antenna could be a small box or
PCMCIA card, or they could be built into a laptop the
way WiFi access is today.
112
WiMAX TOWER
113
WiMAX RECEIVER
114
Fixed WiMAX
 IEEE 802.16d
 1BS – thousands of users
 < 50km coverage
 < 75Mbps
115
Fixed WiMAX Architecture
116
Mobile WiMAX
 IEEE 802.16e
 2-3km coverage (optimal)
 High speed hand over
(< 50ms latencies)
 Ensures performance at
vehicular speeds greater than
120km/h
 < 30Mbps for downlink
 < 15Mbps for uplink
117
Two Forms of Wireless Service
1. Non-Line-of-Sight Service:
* Lower frequency range – 2 GHz to 11 GHz
2. Line-of-Sight Service:
118
WiMAX Facts
 Ideal for the "last-mile" problem that plagues many neighborhoods
that are too remote to receive Internet access via cable or DSL.
 In areas with cable or DSL access, WiMAX will provide consumers
with an additional — and possibly cheaper — alternative (less than
$50).
 Uplink and the downlink up to 75 Mbps
119
WiMAX Facts
 Up to 50 km (31 miles)
 This should not be taken to mean that users 50 km away
without line of sight will always have connectivity.
 Practical limits from real world tests seem to be around 3
to 5 miles.
 If the density of users and thus the demand for bandwidth
are high, the range will be determined by the demand for
BW.
120
802.16 Standards History
802.16
802.16c
(Dec 2001)
(2002)
802.16 Amendment
WiMAX System Profiles
10 - 66 GHz
802.16a
(Jan 2003)
802.16REVd
(802.16-2004)
(Oct 2004)
802.16e
(802.16-2005)
(Dec 2005)
• Original fixed wireless broadband air Interface
for 10 – 66 GHz: Line-of-sight only, Point-toMulti-Point applications
• Extension for 2-11 GHz: Targeted for nonline-of-sight, Point-to-Multi-Point
applications like “last mile” broadband access
• Adds WiMAX System Profiles and Errata for
2-11 GHz
• MAC/PHY Enhancements to support
subscribers moving at vehicular speeds
121
IEEE 802.16 Specifications
 802.16a
Uses the licensed frequencies from 2 to 11 GHz
Supports Mesh network
 802.16b
Increase spectrum to 5 and 6 GHz
Provides QoS( for real time voice and video service)
 802.16c
Represents a 10 to 66GHz
 802.16d
Improvement and fixes for 802.16a
 802.16e
Addresses on Mobile
Enable high-speed signal handoffs necessary for communications with users
moving at vehicular speeds
122
RESEARCH CHALLENGES
* Limited Radio Spectrum
Much of the radio spectrum is already allocated
by governments or used for other purposes by
carriers.
123
RESEARCH CHALLENGES
* High Cost
The cost of deploying WiMAX towers is considerably high
when the service is offered on higher radio frequencies
because the line-of-sight requirements of WiMAX
necessitate the installation of additional antennas to cover
the same service area.
124
RESEARCH CHALLENGES
* Incomplete Network Architecture
IEEE 802.16e standard only addresses PHY and MAC
layers, leaving it to the WiMAX Forum to tackle issues
such as call control, session management, security, the
network architecture, roaming, etc.
125
Open Research Issues
 A group within 802.16, the Mesh Ad Hoc committee is investigating
ways to improve the performance of mesh networking.
 Following issues are yet to be fully considered in specifying the 802.16
mesh MAC protocol
–
–
–
–
–
Avoiding hidden terminal collisions
Selection of links
Synchronization
Power versus data rate tradeoffs
Greater routing-MAC interdependence
126
IEEE 802.16j
Mobile multihop relay (MMR) based on
relaying stations
A more practical multihop networking mode
than mesh mode
Features
– Improve network capacity
– Extend coverage
– Support mobile stations
127
IEEE 802.16j Network
Architecture
128