Transcript uCast Presentation

uCast
Unified Connectionless
Multicast for
Energy Efficient Content
Distribution in
Sensor Networks
Qing Tao, Tian He, Tarek Abdelzaher
Presented By
Andrew Connors
Introduction
• This paper introduces uCast:
– Connection-less protocol
Does not keep state in any intermediate
node
Keeps list of destination addresses in
message headers
Forwarding decisions made at each node
– Uses underlying unicast protocols
Defines simple interface to use “distance”
embedded in unicast protocol
– And demonstrates performance
improvements
Sensor Challenges
• Extremely Energy Constrained
– Short battery life
– Use conservation protocols
• Limited Memory
– 4K bytes on Mica2/MicaZ
• Dynamic
– For this paper this means topology
changes due to nodes entering sleep
states
– Not changes due to sensor movement
Unicast
• Used to send packets to single
destination
Unicast
• Multiple addressing schemes:
– Identifier
– Geographical location
– Network Encoding
Unicast
• Identifier
– No topology information
– Requires routing tables
– Uses flooding to establish routes
– Examples for ad-hoc networks include
• Dynamic Source Routing (DSR)
• Ad-Hoc, On Demand Distance Vector
Routing (AODV)
Unicast
• Geographical location
– Each node is location aware using
GPS or localization
– Location approximate relative
topology
– Do not need flooding as only local
information is used for routing
– Examples include
•
•
•
•
Greedy Perimeter Stateless Routing (GPSR)
GEographical DIstance Routing (GEDIR)
GEDIR + FACE-2 + GEDIR (GFG)
Location Aided Routing (LAR)
Unicast
• Network Encoding
– Topology information encoded in
identifier
– Identifiers directly used for routing
– No flooding needed
– Examples include
• Virtual location-based geographical
routing
• Logical coordinate-based routing (LCR)
• Graph embedded-based routing (GEM)
Multicast
• Used to send packets to multiple
destinations
Multicast
• Three types of multicast:
– Sensor Networks
– Ad-Hoc Networks
– Internet
Multicast
• Sensor Network Multicast Protocols
– Geocast
Destinations located within geographical region
– Mobicast
Spatiotemporal multicast where destinations are in
a moving zone and the goal is to deliver packets
just in time to zone for tracking purposes
– Data Caching & Placement
Uses multicast for asynchronous data updates
– Two-Tier Data Dissemination (TTDD)
Optimized for mobile sinks and uses a grid
structure combined with localized flooding to
track sinks (users that collects these data reports
from the sensor network)
Multicast
• Ad-Hoc Network Multicast Protocols
– Tree-Based
For example Ad-hoc On-Demand Distance Vector
Routing (AODV), that builds multicast trees ondemand to connect members
– Mesh-Based
For example, core-assisted mesh protocol (CAMP)
forms multicast meshes (higher connectivity graphs
than trees) for each multicast group
– Group-Based
For example, On-Demand Multicast Routing Protocol
(ODMRP) also mesh based but also uses forwarding
groups
Multicast
• Internet Multicast Protocols
– Internet Group Management Protocol (IGMP)
Used to maintain groups of multicast members by IP
and routes through existing routers to optimize
delivery through network
– Distance Vector Multicast Routing Protocol
(DVMRP)
Used to share information between routers to
transport multicast packets, and each router
generates a router table for multicast group
– Explicit Multi-Unicast (Xcast)
Does not use multicast addresses but places IP
addresses of destinations into headers, but still
relies on routing tables and a single unicast
protocol
Related Work
• Existing protocols for sensor, ad-hoc or
IP networks are not suitable for
dynamic sensor networks
– Either do not use unicast or only one
specific unicast protocol – and difficult to
maintain multiple protocols in small
memory footprint
– Construction of overlays expensive – uses
flooding to maintain topology – uses too
much energy
– Designed more for laptops not sensors
– Rely on routing tables and/or connection
state – again difficult to implement in small
memory
Connection-Less Threshold
• When to use a connection-less
protocol versus connection based
Cost per
Member
Cost Threshold
(Conceptual)
Application Domain
of uCast
Fewer Members/Light
Traffic per Session
Connection-based Multicast
More Members/Heavy
Traffic per Session
uCast Design
• Uses underlying unicast protocol
through single interface to facilitate a
pair-wise comparison to obtain “closest”
to destination
• Implements a scoreboard algorithm
executed at intermediate nodes using
destination list and current node
neighbors and generates a multicast
task allocation of a list of next hop
nodes that should receive multicast
packet
Unicast Interface
• Defines only one method:
compare (Node N1, Node N2, Node Dest)
• Which returns the selected
“nearest” Node to the Destination
node
Scoreboard Algorithm
INPUT Destination Set (DS), Neighbor Set NS,
and Current Node (S)
FOR EACH node in NS that are in DS, set
selected in NS and move from DS into
Covered Set (CS)
FOR EACH node in DS, if only one neighbor in
NS closer than S, set that node in NS to
selected, and move from DS into CS
FOR EACH node is DS, if no neighbor in NS
closer than S move from DS to Local
Maximum Set (LS)
FOR EACH node in SN, find all destinations for
which it closer compared to S, move those
from DS to CS
Scoreboard Algorithm
WHILE DS is NOT EMPTY
FOR EACH node in DS, find all unselected nodes in NS,
set each node with a score of 0, assign one more
score to node closer to S to node in DS
FIND unselected node K in NS with highest score,
break ties randomly or using node ID, set K to
selected
FOR EACH node is DS, find nodes for which K is closer
than current node S and move them from DS to CS
FOR EACH node in SN, find all destinations for which it
closer compared to S, move those from DS to CS
Scoreboard Algorithm
FINALLY PERFORM OPTIMIZATION
FOR EACH node in NS that are selected insert into SN
FOR EACH destination in CS choose the best node,
snode, among nodes in SN (i.e. “closest” to that CS
node) add destination to SD set of snode
FOR EACH node is NS, remove nodes with empty SD,
for other nodes form individual delivery tasks based
on SD
IF LS is not empty, switch to underlying unicast
protocol and corresponding local maximum handling
approach to deliver packets to destination in LS
Detailed Example
5
1
5
2
S = N53
DS { N51,N55 }
4
NS { N52,N54,N434}
2
1
Score { 1 1 0}
CS { N51}
S =S N
=DS
N33{ N55}
33
3
}
DSNS
{N{51N
,N5215,N
,N5455,N
} 43 3
1
2
Score
_ ,N
1 ,N
0} ,N
NS{N
NS
{N32{32,N
,N
,N
,N
,N
,N
,N
,N
,N
,N
,N
42
42 43
43 44
44 34
34 24
24 23
23 22
22}}
ScoreCS
{1 { N
1 51,,N
2 55}1 2 1 1 0}
CSSN
{ N{51N
,N5255,N}54 }
{ N{N
=>
51}15
DS
} N52
2
2
{
N
}
=>
N
2 }
1 ,N ,N ,N
55 ,N ,N
54 ,N ,N
NS{N
32
42
43
44
Score {0 0 _ 0 0
CS { N51,N55,N15 }
SN { N43,N24 }
1
{ N51,N55 } => N43
1
{ N15} => N24
34
24
1
23
22
5
3
5
4
5
5
4
3
4
4
4
5
1
4
1
5
3
3
2
3
0 0}
1
2
1
3
S = N22
DS { N51,N15,N55 }
NS { N21,N31,N32,N33,N23,N13,N12 }
Score3 { 1 1 23 3 2 1 1}
CS4{ N51,N15,N555 }
S = N11
SN { N }
DS {{}N51,N1533,N55 }
{ N51,N15,N55 } => N33
NS { N
21,N22,N12 }
Score { 22 3 2 } 2
5
CS { N4
51,N15,N55 }
SN { N22 }
{ N51,N15,N55 } => N22
Handling Local Minima
5
1
5
2
5
3
5
4
5
5
4
1
4
2
4
3
4
4
4
5
3
1
3
2
3
3
3
4
3
5
2
1
2
2
2
3
2
4
2
5
1
1
1
2
1
3
1
4
1
5
Other Examples
Design Tradeoffs
• Uses greedy algorithm – may not be
globally optimal
• Limit to maximum number of
destinations due to packet header size
limitations
• However, is at least as good as the NPComplete Set Cover problem
• To be globally optimal would need
another NP-Complete problem - Steiner
tree generation – but cannot be
generated in reasonable time due to
large number of nodes
Optimality Analysis
• Use simulation
– With nodes having range of 50m
– In 500m x 500m region
– Source node placed an (250, 250)
– 6 destination nodes in 60 degree
region
– At least six hops in each route
– Each scenario tested for 100 rounds
– Same topology used for minimum
cover selection, scoreboard, and plain
unicast
Optimality Analysis
Destination Encodings
• Imposes limit to size of multicast
destinations
• Three possible trade-offs to mitigate:
– With longer packets – such as used in video
streams – size not an issue
– Compress destination header – trading
space for computational time
– In network aggregation – use train of
packets that share destination list – but
need synchronization and retransmission
mechanisms
• In any case uCast is designed for smallgroup multicast
Performance Evaluation
• Compare with connection-based
protocols:
– Shortest Path Tree (SPT)
Source node sends packets along shortest paths to
destinations and aggregates common paths to
form tree structure
– Greedy Incremental Tree (GIT)
Centralized construction and requires full
knowledge of topology and is computationally
intensive
– Plain unicast
• Uses geographical forwarding with the
GPSR traversing technique to handle
local minimum set
Destination Placement
• Uses four parameters:
– Polar angle of
dispersion (AOD)
– Radius – which is
furthest destination
node
– Density – number of
nodes within
communication range
– Number of destination
nodes
Default Parameters
• Communication range = 50m
• Area = 500m x 500m
• Density = 20 nodes per communication
range
• AOD = 900
• Number of destinations = 10
• Radius = 250m
• Total nodes = 636
• Data rate = 6 packets / minute
• Use PicaZ nodes with CC2420 radio
Energy Efficiency
GIT is best but impractical
uCast performs better than SPT & Unicast
Impact of AOD
Energy Efficiency
GIT is best but impractical
uCast performs better than SPT & Unicast
Impact of # Destinations
Energy Efficiency
GIT is best but impractical
uCast performs better than SPT & Unicast
Impact of Range
Energy Efficiency
GIT is best but impractical
uCast has longer path length then SPT due
to GPSR – but in reality voids are not
common
Impact of Density
Average Path Length
uCast & GIT have longer path lengths due
to path aggregation leading to higher endto-end delay
SPT & Unicast find near optimal paths
But trading energy consumption for longer
path lengths
Impact of AOD
Average Path Length
uCast & GIT have longer path lengths due
to path aggregation leading to higher endto-end delay
SPT & Unicast find near optimal paths
But trading energy consumption for longer
path lengths
Impact of Density
Topological Changes
• Introduce topological changes by
using energy saving protocols
• Using parameters:
– Toggle cycle – time interval between
sleep state transitions
– Scale – size of multicast area – larger
the area then cost of reconstruction
greater
– Packet Delivery Rate – use 6 and 12
packets per minute
Topological Changes
Shows stateless multicast is superior with
node state transitions
As toggle periods shorten SPT degrades
considerably, but uCast achieves 96%
delivery ratio
Impact of Toggle Period (Rate = 10ppm)
Topological Changes
Connection based multicast is less scalable
than uCast as range increased there is
higher probability of state loss
Impact of Scale
Topological Changes
Shows 1000s of control
packets are needed to rebuild
tree
Impact of Toggle Cycle & Range = 250m
On SPT
Topological Changes
Shows 1000s of control
packets are needed to rebuild
tree
Impact of Toggle Cycle & Range = 500m
On SPT
Topological Changes
Shows effect of increased data
rate – which decreases
delivery ratio
Increasing Data Rate to 12 ppm
Unicast Protocols
Geo forwarding and logical coordinatesbased routing similar in their performances.
However, uCast based on GEM shows quite
different performance characteristics due to
convoluted delivery paths and polar
coordinates
Running System
• Used actual
sensor platform
with
– 25 MICA2 motes
– Code Size of 992
bytes
– 3V supplies
– 19.2 kbps
– 12 byte payload
System Evaluation
uCast significantly reduces
energy consumption
uCast & unicast
uCast significantly reduces
data load
Recorded data load at each node
Conclusions
• uCast is generally as efficient as
connection-based protocols even
with static networks
• uCast is more robust in a dynamic
network due to its connectionless
nature
• uCast can be implemented on
different unicast routing protocols
• A real implementation supports
these conclusions