Real-time Communications over Wireless Sensor Networks
Instructor: Chang-Gun Lee
Forest Monitoring Sensor Networks
•Periodic monitoring of forest
•Fast delivery of emergency event
Rescue Supporting Sensor Networks
Periodic messages Æmessage delivery meeting deadlines Aperiodic messages Æmessage delivery ASAP
Wireless Sensor Networks
• Delivering sensory data to the sink in time is important
• Most existing wireless protocols make the underlying assumption that the network traffic is intrinsically random and work in a contention-based way
– No-deterministic guarantee of message
delivery
CSMA/CA MAC Protocol (802.11)
Problems
1. Random arbitration: collisions Æwaste of channel 2. No overload prevention: Miss all deadlines
Can Real-Time Techniques solve the problems?
I-EDF
• Motivation: Can we leverage on the
“Periodic” nature of sensor messages?
– Collision-free deterministic MAC protocol
• Ideas
– Cellular Architecture
– Implicit EDF for collision free scheduling – Frame reclaiming of unused reserved slots for
serving Aperiodic messages ASAP
Network Architecture
Cell structure:
• 7 channels
• messages are broadcasted inside the cell
• a router node at cell center
router
Intra-cell broadcast
• Medium Access for intra-cell communication
• Time is divided into synchronized frames
• Inside each cell, nodes use implicit contention:
– Periodic nature of sensor data streams, once initialized, allows for EDF scheduling via implicit contention – no contention phase, no conflicts, no backoff
data
Frame
data
Implicit prioritized medium access using EDF Implicit prioritized medium access using EDF
• Distributed scheduling
• The EDF scheduler is replicated to each cell node
node message size (frames)
period (frames)
A 3 8
B 1 6
1 8
C 1 4
This table is stored in each node of one cell
∑
= + + + ≤i i
i
period MsgSize
4 1 1 8 1 6 1 8 3
Message set is schedulable!
C B A A A B C
0 4 8
B C
12
A A A B
16
C B C
20
A A A B B C
24
C
Mechanism for inter
Mechanism for inter- -cell communication cell communication
• Inter-cell communication mechanism uses TDM+EDF
– routers have two transceivers (used at the same time on different channels) – sender uses its own cell
frequency
– each router sends the message with earliest deadline
– Inter-cell frames are reserved – blocking term in local
schedulability analysis
IC IC IC IC IC IC
How to send
How to send aperidic aperidic messages? messages?
• Use an aperiodic server
– Polling server– CUS (Constant utilization server) – TBS (Total bandwidth server) – CBS (Constant bandwidth server)
Problems with implicit EDF Problems with implicit EDF
z Implicit EDF drawback Îif a message finishes earlier, the unused reserved frames are wasted
z Implicit EDF cannot reclaim unused reserved frames!
Node A Node B Node C
Aperiodic message Length = 4
Tmin=12 Tavg=16
Polling server Qs=1 Ts=4
FRASH (
FRASH (FRAme FRAme Sh S haring) Algorithm aring) Algorithm
Node A Node B Node C
Aperiodic message Length = 4
Tmin=12 Tavg=16
Polling server Qs=1 Ts=4
Experimental results Experimental results
Normalized system throughput
z
A set of experiments was run in the ns-2 network
simulator: IEDF and IEDF+FRASH schemes have
been compared with Black-Burst, Enhanced DCF and
CSMA/CA.
Experimental results Experimental results
Avg. delay of aperiodic messages with offered load = 90%
z
Implicit EDF (I-EDF) and I-EDF with FRASH provide higher system throughput and lower latency under heavy load condition and in dense networks.
Problem of I
Problem of I- -EDF? EDF?
• All nodes need to be synchronized!
• Distributed Synchronization is an expensive job
• Any idea?
– Build I-EDF schedule
– But, chained triggering of the next execution (not by time- triggering)
– ÆRI-EDF (Robust Implicit EDF)
How RI
How RI- -EDF works? EDF works?
• Due to the lack of clock synchronization, each node is triggered by the reception of previous message.
• If a message completes earlier than the reserved budget, the left-over budget is forwarded
Any problem?
Any problem?
• Packet loss or node failure will stop the schedule
• Recovery is needed!:
Each successful packet reception is a synchronization
point in the schedule Highest priority node
has the shortest recovery timer: capture the channel and send a recovery packet distributed state
Any further problem?
Any further problem?
• End-to-end deadline guarantee?
• We have to solve a combined problem of scheduling and routing
Summary Summary
• Wireless sensor networks introduce new challenges not addressed by classical ad hoc networks literature
• A scheduling based MAC protocol has been introduced to guarantee bounded message delay
• Key Finding
– Similarity of job scheduling on CPU and packet scheduling on wireless shared medium
– So, we can reuse real-time job scheduling techniques
• References
– Marco Caccamo, L. Zhang, L. Sha, and G. Buttazzo, An Implicit Prioritized Access Protocol for Wireless Sensor Networks, RTSS 2002
– T. L. Crenshaw, A. Tirumala, S. Hoke, and M. Caccamo, A Robust
