Transcript REAL TIME COMMUNICATION IN WIRELESS SENSOR NETWORKS

REAL TIME
COMMUNICATION IN
WIRELESS SENSOR
NETWORKS
BY
ZILLE HUMA KAMAL
WHAT IS A REAL TIME
SYSTEM (RTS)
“A real time system is one in which the
correctness of the computations not only
depends on their logical correctness, but
also on the time at which the result is
produced” [St]
CS 691 - WMU - WSNR
CLASSIFICATION OF RTS
• 2 Categories of RTS:
– A Hard RTS is one in which one or more
activities must never miss a deadline or timing
constraints, otherwise the system fails or
results in catastrophe. [St]
– A Soft RTS is one that has timing constraints,
but occasionally missing them has negligible
effects, as application requirements as a whole
continue to be met. [St]
CS 691 - WMU - WSNR
TERM AND DEFINITIONS
• Task – executable entity
• Job – instance of a task
• Release Time – time at which task becomes ready
to run and job is released
• Period – time between releases of two instances
of the same task
• Deadline – relative time at which a job should
complete execution
• Execution Time/ Run Time – time taken to
complete execution without interruption
• Frame – discrete unit of time
[CZSB]
WIRELESS SENSOR
NETWORKS
• CHARACHTERISTICS
– An instance of MANET
– Resource constraint – energy and storage
capacity
– Limited range for communication and sensing
– Frequent network topology changes
– Individual entities are not critical, aggregation
of results is necessary for effectiveness and
accuracy
CS 691 - WMU - WSNR
RTS IN WSN
• Two types of communication groups are
inherently formed
– Local Coordination – to aggregate results
– Sensor-Base Communication – to send results to base
station
• This introduces contention on the communication
channel, thus the main schedulable resource is
the communication channel
CS 691 - WMU - WSNR
RAP
• A Real-Time communication architecture
Sensing/Control
Application
Query/Event Service APIs
Query/Event Service
Coordination Service
Location Addressed Protocol
Geographic Forwarding
Velocity Monotonic Scheduling
Prioritize MAC
CS 691 - WMU - WSNR
RAP
APIs
• Issue Query
- query name
- attribute list
- area
- timing constraints, e.g. period, deadline
- querier location
CS 691 - WMU - WSNR
APIs
• Event Registration
- event name
- area
- query
CS 691 - WMU - WSNR
Example
register_event{
virus_found(0,0,100,100),
query{
virus.count,
area=(Xevent-1 ,Yevent-1,Xevent+1,Yevent+1),
period=1.5, deadline=5,
base=(100,100)
}
};
CS 691 - WMU - WSNR
LAP
• Location Addressed Protocol
- transport layer
- connectionless
- no IP/ID addressing, location based
addressing
- three types of communication
» unicast
» area multicast
» area anycast
CS 691 - WMU - WSNR
LAP
• Unicast
• Message is delivered to node closest to destination, e.g when
sensors send query results back to base station
• Area Multicast
• Message is delivered to every node in a specified area, e.g
when base station sends query to an area, or for local
coordination
• Area Anycast
• Message is delivered to at least one node in the specified
area, e.g when base station wants to send a query to an area,
the node which receives it can start the initiation process
CS 691 - WMU - WSNR
GF
• Greedy algorithm
A packet is forwarded to a neighbor only if:
(1) the neighbor node has the shortest distance to the
packet’s destination among all immediate
neighbors AND
(2) the neighbor node is closer to the destination than
the forwarding node
• If these conditions not satisfied, GPSR is
used instead of GF
CS 691 - WMU - WSNR
VMS Deadline aware
Distance aware
• Deadline aware
• Distance aware
• Packet scheduling policy
– 2 types of packet scheduling policies
– Static Velocity Monotonic
– Dynamic Velocity Monotonic
CS 691 - WMU - WSNR
VMS
• SVM
– Requested velocity is fixed at each hop
V = dis(x0, y0, xd, yd)/D
• DVM
– Requested velocity changes at each hop and reflects
the time the packet has spent in the network
vi = dis(x0, y0, xd, yd)/(D-Ti)
v0 = dis(x0, y0, xd, yd)/D
CS 691 - WMU - WSNR
Priority Queues
• various FIFO queues, one for each priority
• Advantage – per packet overhead decreases,
ordering of each packet is not required
• Disadvantage – more storage capacity required
• single FIFO queue, with priority ordering
• Advantage – reflects order of packets requested
• Disadvantage – greater number of packets lost
CS 691 - WMU - WSNR
MAC PRIORITIZATION
• Extensions to 802.11
– Initial wait time after idle
– Backoff Increase Function
• Initial wait time after idle
DIFS = BASE_DIFS * PRIORITY
• Backoff Increase Function
CW = CW * (2+(PRIORITY-1)/MAX_PRIORITY)
CS 691 - WMU - WSNR
EXPERIMENTATION
Overall deadline miss ratio of DSR and GF with
deadlines (5,10)
CS 691 - WMU - WSNR
EXPERMENTATION
Overall deadline miss ratio
CS 691 - WMU - WSNR
EXPERIMENTATION
Miss ratio vs distance between source and
destination (Deadline: (5:10) s; Rates: (0.8, 0.36)/s)
CS 691 - WMU - WSNR
REAL TIME
COMMUNICATIONS IN
WIRELESS SENSOR
NETWORK
NOW PRESENTING SPEED
BY
Zille Huma Kamal
UNFAVORABLE
• Despite the simplicity of RAP and the high
miss deadline ratio it serves, RAP does not
guarantee for soft or hard real time
communication systems.
• Therefore, our search for a Real Time
Communication protocol is unsatisfied.
CS 691 - WMU - WSNR
TO END THE SEARCH
• SPEED is a real time communication
protocol which guarantees end to end soft
real time communication
• We will discuss the components of SPEED
and then relate SPEED to other existing
protocols for MANETS, ad-hoc networks
and real-time communication systems.
CS 691 - WMU - WSNR
COMPONENTS OF SPEED
•
•
•
•
•
•
•
•
API
Neighbor Beacon Exchange
Delay Estimation
Stateless Non-deterministic Geographic
Forwarding(SNGF)
Neighborhood Feedback Loop(NFL)
Backpressure Rerouting
Void Avoidance
Last mile processing
CS 691 - WMU - WSNR
API & PACKET FORMAT
• UnicatSend(Global_ID, packet)
• AreaMulticastSend(position, radius,
packet)
• AreaAnycastSend(position, radius, packet)
• SpeedReceive( )
• SPEED packet format:
PacketType
Global_ID
DestinationArea
CS 691 - WMU - WSNR
TTL
Payload
Neighbor Beacon Exchange
• Periodic beacons – exchange location
information
• In static or slow moving sensor networks –
very low beaconing rate
• Further reduce overhead – piggybacking,
include ID on data packets, so that you are
using the existing packets and not
introducing more traffic
CS 691 - WMU - WSNR
NEIGHBOR TABLE
• Through beaconing each node is capable of
maintaining a Neighbor Table (NT)
Neighbor_ID
…
…
…
Position
…
…
…
SendToDelay
…
…
…
ExpireTime
…
…
…
• In addition to location beacons, you have delay
estimation beacons and backpressure rerouting
beacons
CS 691 - WMU - WSNR
DELAY ESTIMATION
• Single Hop Delay – delay across one router
• Sender - timestamps when packet leaves node
and then waits for acknowledgement from
receiver.
• Receiver – in acknowledgment packet sends the
time taken to process the acknowledgment
• Sender – after receiving the acknowledgment,
calculates round trip time as
timestamp – ACK time – ACK processing time
CS 691 - WMU - WSNR
DELAY ESTIMATION
• This round trip delay time is aggregate
with previous delay times via EWMA
• Since delay estimation expensive – SPEED
only invokes delay estimation when round
trip delay for an individual case exceeds a
predetermined threshold value
CS 691 - WMU - WSNR
BACK-PRESSURE
REROUTING
• Routing layer adaptation to congestion
• Beacon format
ID
Destination
AvgSendToDelay
• When congestion occurs, node sends backpressure beacon to sender with
AvgSendToDelay equal to infinity
CS 691 - WMU - WSNR
SNGF - TERMINOLOGY
• Nsi = {all nodes within radio range of
nodei}
• FSi(destination) = {x | x  Nsi and it is
closer to the destination than nodei}
• Relay Speed
CS 691 - WMU - WSNR
SNGF – FORWARDING
CONDITIONS
• Only if node belongs to FSi(destination)
• FSi(destination) into 2 categories:
– FS1i(destination)of nodes with
relay speed > Ssetpoint
– FS2i(destination) of nodes with
relay speed < Ssetpoint
– Forwarding node is always from FS1i(destination)
• If no node in FS1i(destination) then call
Neighborhood Feedback Loop (NFL) and decide
whether to drop packet or not
CS 691 - WMU - WSNR
NFL - TERMINOLOGY
• Miss = when packet delivered at neighbor
with relay speed < Ssetpoint or any packet
loss due to collision
• Miss ratio calculation
CS 691 - WMU - WSNR
NFL
• MAC layer adaptation to avoid congestion
CS 691 - WMU - WSNR
VOID AVOIDANCE
• By using backpressure rerouting
• Only guarantees to find a path if a greedy
path exists
CS 691 - WMU - WSNR
LAST MILE PROCESS
• For AreaMulticast and AreaAnycast – TTL
manipulation
• For Unicast
CS 691 - WMU - WSNR
EXPERIMENTATION CONGESTION
CS 691 - WMU - WSNR
EXPERIMENTATION CONGESTION
CS 691 - WMU - WSNR
EXPERIMENTATION – E2E
DEADLINE MISS RATIO
CS 691 - WMU - WSNR
EXPERIMENTATION – E2E
DEADLINE MISS RATIO
CS 691 - WMU - WSNR
EXPERIMENTATION - COST
CS 691 - WMU - WSNR
EXPERIMENTATION - COST
CS 691 - WMU - WSNR
EXPERIMENTATION –
ENERGY CONSUMPTION
CS 691 - WMU - WSNR
EXPERIMENTATION –
TRAFFIC BALANCING
CS 691 - WMU - WSNR
REFERENCES
• [CZSB] M Caccamo, L.Y Zhang, L Sha, G
Buttazzo, “An Implicit Access Protocol for
Wireless Sensor Networks,”Proceedings of
IEEE Real-Time Systems Symposium,
Austin, TX , Dec 2002.
http://www.cs.wustl.edu/~venkita/publications/class/implicit
edf.pdf
CS 691 - WMU - WSNR
REFERENCES
• [HSLA] T He, J.A Stankovic, C Lu, T
Abdelzaher, “SPEED: A Stateless Protocol for
Real-Time Communication in Sensor Networks,”
Department of Computer Science, University of
Virginia and Department of Computer Science
and Engineering, Washington University in St
Louis
http://www.cs.virginia.edu/~stankovic/psfiles/SPEED_ICDCS.pdf
CS 691 - WMU - WSNR
REFERENCES
• [LBASH] C Lu, B.M Blum, T.F Abdelzaher, J.A
Stankovic, T He, “RAP: A Real-Time
Communication Architecture For Large-Scale
Wireless Sensor Networks,” Department of
Computer Science, University of Virginia
www.cs.virginia.edu/~stankovic/psfiles/rtas02-rap.pdf
• [P] T. F Piatkowski, “Citation and
acknowledgment guide,” Department of
Computer Science, Western Michigan University,
Aug, 2000
www.cs.wmich.edu/~piat/citationAckGuide.pdf
CS 691 - WMU - WSNR
REFERENCES
• [Sp] “Delay Analysis,” Sprint, 2003
http://ipmon.sprintlabs.com/delaystat/
• [St] D.B Stewart, “Introduction to Real
Time,” Embedded.com, Nov 1, 2001
www.embedded.com/story/OEG20011016S0120
CS 691 - WMU - WSNR