Wireless Networks

Lecture 35
MAC Protocols for WSN Part II
Dr. Ghalib A. Shah

1


Outlines






Challenges in WSNs.
Attributes of MAC Protocol
Overview of MAC protocols
Energy Efficiency in MAC
Proposed Routing Protocol
►
►
►
►
►
►

S-MAC
T-MAC
DS-MAC

Traffic Adaptive MAC
DMAC
Contention-Free MAC
2


Last Lecture
 Introduction to WSN
 Applications of WSN
 Factors Influencing Performance of WSN
► Power consumption, fault tolerance, scalability, topology,
cost

 Architecture and Communication Protocols

3


Research Directions










Topology Control

Coverage
Data Aggregation
Temporal/Spatial Correlation
Localization / Synchronization
Energy Efficient Data Dissemination
QoS Framework
Network Monitoring and Management
How to integrate WSNs into NGWI ?
4


Simulation for Sensor Networks
Simulation provides :
 Controlled , Reproducible testing environment
 Cost – effective alternative
 Means to explore and improve design space

5


TinyOS
 The role of any operating system (OS) is to promote
development of reliable application software by
providing a convenient and safe abstraction of
hardware resources.
 Wireless sensor networks (WSNs) are embedded but
general-purpose, supporting a variety of applications,
incorporating heterogeneous components, and capable
of rapid deployment in new environments
 An open-source development environment

► A programming language and model (NesC)

 TOSSIM for simulating TinyOS
 TinyDB for Sensor DB in TinyOS
6


Introduction
 Important attributes of MAC protocols
► Collision avoidance
• Basic task — medium access control

► Energy efficiency
► Scalability and adaptivity
• Number of nodes changes overtime

►
►
►
►

Latency
Fairness
Throughput
Bandwidth utilization
7


Overview of MAC protocols
 Contention-based protocols

► CSMA — Carrier Sense Multiple Access
• Ethernet
• Not enough for wireless (collision at receiver)

C
A
B
Hidden terminal: A is hidden from C’s CS
► MACA — Multiple Access w/ Collision Avoidance
• RTS/CTS for hidden terminal problem
• RTS/CTS/DATA

8


Overview of MAC Protocols
 Contention-based protocols (contd.)
► MACAW — improved over MACA
• RTS/CTS/DATA/ACK
• Fast error recovery at link layer

► IEEE 802.11 Distributed Coordination Function
• Largely based on MACAW

 Protocols from voice communication area
► TDMA — low duty cycle, energy efficient
► FDMA — each channel has different frequency
► CDMA — frequency hopping or direct sequence
9



Energy Efficiency in MAC Design
 Energy is primary concern in sensor networks
 What causes energy waste?
►
►
►
►
►

Collisions
Control packet overhead
Overhearing unnecessary traffic
Overemitting
Dominant in sensor nets
Long idle time

 

• bursty traffic in sensor-net apps
• Idle listening consumes 50—100% of the power for
receiving (Stemm97, Kasten)

10


Energy Efficiency in MAC Design
 TDMA vs. contention-based protocols
► TDMA can easily avoid or reduce energy waste from
all above sources

► Contention protocols needs to work hard in all
directions
► TDMA has limited scalability and adaptivity
• Hard to dynamically change frame size or slot assignment
when new nodes join
• Restrict direct communication within a cluster

► Contention protocols easily accommodate node
changes and support multi-hop communications

11


S-MAC: Periodic Listen & Sleep

 Frame
 Duty cycle

Listen

Sleep

Listen

Sleep

Listen

► (Listen Interval / Frame Length)


 Frame schedule
► Nodes are free to choose their listen/sleep schedule
► Requirement: neighboring nodes synchronize together
► Exchange schedules periodically (SYNC packet)
• Synchronization period (SP)
C

A

B

D

 Nodes communicate in receivers scheduled
listen
12


S-MAC: Coordinated Sleeping (1)
Frame  S c he dule  Mainte nanc e
1. Choosing a schedule
• Listen to the medium for at least SP
• Nothing heard, choose a schedule
• Broadcast a SYNC packet (should contend for medium)

1. Following a schedule
• Receives a schedule before choosing/announcing
• Follows the schedule
• Broadcast a SYNC packet


1. Adopting multiple schedules
• Receives a schedule after choosing/announcing
• Can discard the new schedule; or
• Follow both the schedules – suffer more energy loss
13


S-MAC: Coordinated Sleeping (2)
Maintaining  S ync hro nizatio n
 Clock drifts – not a major concern (listen time =0.5s
– 105 times longer than typical drift rates)
 Need to mitigate long term drifts – schedule updating
using SYNC packet (sender ID, its next scheduled
sleep time – relative);
 Listen is split into 2 parts – for SYNC and RTS/CTS
Listen
Receiver

for SYNC

for RTS

for CTS

Sleep

 Once RTS/CTS is established, data sent in sleep
14
interval



S-MAC: Coordinated Sleeping (3)

Adaptive  Lis te ning  – Lo w­duty c yc le  to  ac tive  
mo de
* OverhearingListen
nodes – wakeup
at the end of the
Listen
current transmission (duration field in RTS/CTS)
R

Sender
Receiver

ON

RTS

DATA

CTS

ACK

Sleep (based on RTS)
Overhearing
nodes (ON)

Sleep (based on CTS)


Wakes up even though it
is not the correct listeninterval
Not all receiver’s nexthop nodes can hear the
transmission, if
adaptive

15


Drawbacks of S-MAC
 Active (Listen) interval – long enough to handle
to highest expected load
► If message rate is less – energy is still wasted in
idle-listening

 S ­MAC fixe d duty c yc le  – is  NOT OPTIMAL
 Hig h Late nc y
Normal
S-MAC

Sleep

Active

Sleep

Active

Sleep


16

Active


T-MAC: Preliminaries
 Adaptive duty cycle:
Active

Active

Active

Sleep
TA

Sleep
TA

TA

 A node is in active mode until no activation event
occurs for time TA
► Periodic frame timer event, receive, carrier sense, send-done,
knowledge of other transmissions being ended

 Communication ~=S-MAC/802.11
 Frame schedule maintenance ~=S-MAC
17



T-MAC: Choosing TA
 Requirement: a node should not sleep while its
neighbors are communicating, potential next
receiver
 TA > C+R+T
► C – contention interval length;
► R – RTS packet length;
► T – turn-around time, time bet. end of RTS and start
of CTS;

 TA =1.5 * (C+R+T);
18


 Prons
► Performs better under variable traffic load

 Cons
► Higher overheads than SMAC to maintain variable
wakeup schedule.
► Unfairness and unpredictable delay.

19


Dynamic Sensor-MAC (DSMAC)









TMAC improves the latency in SMAC at cost of complexity.
DSMAC provides simple solution to static duty cycle.
All nodes start with same duty cycle.
If one-hop latency is observed higher by receiver, it doubles its
duty cycle
Nodes share their one-hop latency values with neighbors during
SYNC period.
The transmitter also doubles its duty cycle if the destination
reported higher one-hop latency.
This change will not affect the schedule of other neighbors.

20


DSMAC Schduling

21


Traffic-Adaptive MAC (TRAMA)









Time is divided into random-access and scheduled-access
(transmission) periods.
The random-access period is used to establish two-hop topology
information
MAC layer can calculate the transmission duration needed, which
is denoted as S CHEDULE_INTER VAL
the node calculates the number of slots for which it will have the
highest priority among two-hop neighbors
The node announces the slots it will use as well as the intended
receivers for these slots with a s che dule  packe t.
the node announces the slots for which it has the highest priority
but it will not use
The schedule packet indicates the intended receivers using a
bitmap whose length is equal to the number of its neighbors
22


 Ad v antag e s  
► Higher percentage of sleep time and less collision
probability are achieved, as compared to CSMAbased protocols.
► Since the intended receivers are indicated by a
bitmap, less communication is performed for the
multicast and broadcast types of communication
patterns, compared to other protocols.

 Dis ad v antag e s

► Transmission slots are set to be seven times longer
than the random-access period. This means that
without considering the transmissions and
receptions, the duty cycle is at least 12.5 percent
(idle time),
23


DMAC
 Supports convergecast communication model,
 Data-aggregation tree is formed from sources to sink
node.
 It is an improved slotted ALOHA algorithm.
 Slots are allotted according to the level of tree from leaf
to root.
 It incurs low latency but no collision avoidance for
nodes at same level

24


DMAC
A minimum
period u consists
of one packet tx
and rx.
Wakeup period in
three is skewed
depending on
depth d. so du is

the wakeup time
Node at higher
layer will be in rx
state when lower
layer nodes are in
tx state

Nodes on path wakeup sequentially to forward packet to next hop: low latency
25
with efficient energy consumption