Greedy Distributed Spanning Tree Routing in Wireless Sensor Networks

undefined
GREEDY DISTRIBUTED SPANNING TREE ROUTING
(GDSTR)
CMPE 259: SENSOR NETWORKS
MATTHEW HENDRICKS
WIRELESS SENSOR NETWORKS
Requirements:
Made up of several nodes/sensors
Nodes consist of a CPU, storage, transmitter,
and battery
Communications sometimes take many hops
to reach the sink
 
SCALABILITY OF SENSOR NETWORKS
  Limited recourses lead design
Battery powered
Less storage
Scalability and Robustness
Must accommodate additional
nodes
Has to work though node failure
 
MICA 2 "MOTE"
Price (about $150)
Sensor expantion board ($120)
        - light
        - temperature
        - microphone
More sofisticated boards available
        - accelerometers
        - GPS
DYNAMIC TOPOLOGIES
    Node issues
Nodes are subject to physical harm
Hardware issues
Battery failure
Transmission issues
Physical obstacles
RF interference 
THE APPROACH OF GDSTR
     Route via location
Nodes are aware of their location
GPS
Static location
Indoor networks
             
Packet destination field = the destination location
PREREQUISITES OF GDTSR
Node placement occur on a plane
Radio Links are Bi-Directional
Transmission power is uniform
GEOGRAPHIC ROUTING
 
Greedy forwarding:
Uses local information to route
Hop closest to destination  is
chosen
ISSUES
Dead ends
Closest neighbor to destination
not always available
Face routing remedy used in
other protocols
FACE ROUTING
Route messages through planar
graph
Does not scale well
HULL TREES
Each node has a
"
convex hull
"
Convex hulls contain
all  descendant nodes
within
Storage is O(1) vs. O(N)
ROUTING WITH HULL TREES
If destination is not within
convex hull, forward to the
parent
If destination is in the convex
hull, forward packet
ROUTING WITH HULL TREES CONTINUED...
           If the packet was in greedy mode previously or was sent from the parent node:
Packet will be forwarded to first child node containing destination.
If the packet came from a child node:
Packet will be forwarded to the next child node that's convex has the destination within it
If the packet came from child node from hulls that have destination within:
Packet will go to the parent or child node that is also root node.
Routing via decisions based on trees is slower
GDSTR only uses trees when needed
GDSTR switches back to greedy routing as soon as
possible
Tree hops are used as little as possible
PERFORMANCE ISSUES
CREATION OF HULL TREES
Routing performance gains
from less overlap between
convex hulls
Compact trees are ideal and
lead to less  hop count
Smaller trees broadcast
chosen parent node and
convex hull
ROUTING ALGORITHM
Mode: current greedy or tree routing style
N min: node where packet switches from greedy to tree routing
Tree: identifier for the root of hull tree
N anchor: first discovered node while traversing tree
ALGORITHM (GDSTR)
1.
Check for Greedy mode switch
2.
Greedy Mode
3.
Tree Mode
4.
Choose Hull Tree
5.
Check Hull Tree
6.
Not in Hull Tree
7.
Check Anchor Node
8.
Termination Condition
9.
Tree Traversal
1. CHECKING FOR MODE
"If p.mode = Tree and there is at least one immediate neighbor
 w such that |wt| < |(p.nmin)t|,
     then set p.mode := Greedy,
     p.nmin := w and clear p.nanchor and p.tree if they are set.
     Execute step 2 or 3 according to p.mode"
2. GREEDY MODE
Find the node w in the set of immediate neighbors that is closest to t.
If |wt| < |vt|,
     forward the packet to w.
Otherwise,
     set p.mode := Tree and follow step 3.
3. TREE MODE
If
 p.tree is not set or if the root for p.tree has changed,
    follow step 4,
else
    follow step 5.
4. CHOOSE HULL TREE
Choose one of the existing hull trees for forwarding and set p.tree to the chosen
tree’s identifier.
Follow step 5.
5. CHECK HULL TREE
If
 hull tree does not contain destination node t,
    follow step 6;
otherwise,
    follow step 7 instead.
6. NOT IN HULL TREE
If
 none of the hulls in H contains the destination node t
    conclude that the packet is not deliverable.
Otherwise,
    forward p to the parent node in p.tree.
7. CHECK ANCHOR NODE
If
 p.nanchor is set,
    follow step 8.
Else
,
    set p.nanchor := v and follow step 9 instead.
8. TERMINATION CONDITION
Given a global ordering for node identifiers, arrange the child nodes (relative to p.tree) with convex
hulls that contain the destination point in a ascending sequence according to the global ordering.
Then: 5
    If
 v = p.anchor and either (i) u is the last child and v is the root node for p.tree,
    (ii) u is the last child and the set of conflict hulls H does not contain destination node t,
   or (iii) u is the parent node,
        conclude that packet is not deliverable;
    else  If
 u is the parent node and the set of conflict hulls H does not contain destination node t,
        set p.nanchor := v. Follow step 9. "
9. TREE TRAVERSAL
If
 p.mode = Greedy
    set p.mode := Tree, forward packet to the first child node;
If
 packet was received from the parent node
    forward packet to the first child node;
If
 packet was received from a child node
    forward packet to the next child node in the sequence;
If
 packet was received from the last child node
    
if
 one of the hulls in H contains the destination point;
        forward packet to the parent node
    
Else
       
forward packet to the first child node. 
SIMULATION
Unit radio range
    Communication if and only if within range, and have line of site
Wireless issues not accounted for
Networks of 25 to 500 nodes
    Randomly place in 10 x 10 unit square
200 networks tested
    20,000 packets routed
    Source and destination randomly selected
SIMULATION COMPARISONS
Greedy Perimeter Stateless Routing (GPSR)
Greedy Other Adaptive Face Routing Plus (GOAFR+)
Greedy Path Vector Face Routing (GPVFR)
Cross-Link Detection Protocol (CLDP) planarization
A density of 500 nodes in 100 square units is high enough that greedy
forwarding almost always succeeds
ROUTING RESULTS
 
Path stretch: Ratio of path length
between nodes
Hop stretch: ratio of hops
between two nodes against the
number of hops on the shortest
path
Metrics were considered similar
enough to be plotted together
ROUTING RESULTS
From node degree range 2 to 9 GDSTR
outperforms other algorithms
Most improvement in the node degree range 4 to 6
GDSTR routes where often shorter
        Faster delivery
        Less consumption of radio resources
BANDWIDTH RESULTS
GDSTR broadcast (keep alive) vs.
CLDP probes
Broadcast messaging smaller on
average up till a node degree of 4
to 8
Probes contain all point faces
4 to 8 range had largest
perimeters
BANDWIDTH RESULTS
CLDP probes are sent out until all links
are considered dormant or non-routable
GDSTR converges when hull information
stabalizes
SCALABILITY RESULTS
CLDP message count
independent of node count
GDSTR fail messaging
increases gradually with
node count
GDSTR join messaging
independent of node count
CONCLUSIONS
Hull trees can be at least as efficient as planar graphs after greedy
forwarding
GDSTR uses less maintenance bandwidth than CLDP
Testing was conducted on stationary two dimensional graphs, but could adapt
to mobile multidimensional situation
Slide Note
Embed
Share

Wireless sensor networks play a critical role in various applications, and the Greedy Distributed Spanning Tree Routing (GDSTR) protocol, developed by Matthew Hendricks, offers an efficient routing approach. This protocol addresses challenges such as scalability, dynamic topologies, and sensor node issues by utilizing a distributed tree structure based on greedy forwarding. GDSTR leverages location awareness, convex hull trees, and face routing methods to enhance routing efficiency in sensor networks.

  • Wireless Sensor Networks
  • GDSTR Protocol
  • Routing Techniques
  • Sensor Node Issues
  • Scalability

Uploaded on Sep 22, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. GREEDY DISTRIBUTED SPANNING TREE ROUTING (GDSTR) CMPE 259: SENSOR NETWORKS MATTHEW HENDRICKS

  2. WIRELESS SENSOR NETWORKS Requirements: Made up of several nodes/sensors Nodes consist of a CPU, storage, transmitter, and battery Communications sometimes take many hops to reach the sink

  3. SCALABILITY OF SENSOR NETWORKS Limited recourses lead design Battery powered Less storage Scalability and Robustness Must accommodate additional nodes Has to work though node failure

  4. MICA 2 "MOTE" Price (about $150) Sensor expantion board ($120) - light - temperature - microphone More sofisticated boards available - accelerometers - GPS

  5. DYNAMIC TOPOLOGIES Node issues Nodes are subject to physical harm Hardware issues Battery failure Transmission issues Physical obstacles RF interference

  6. THE APPROACH OF GDSTR Route via location Nodes are aware of their location GPS Static location Indoor networks Packet destination field = the destination location

  7. PREREQUISITES OF GDTSR Node placement occur on a plane Radio Links are Bi-Directional Transmission power is uniform

  8. GEOGRAPHIC ROUTING Greedy forwarding: Uses local information to route Hop closest to destination is chosen

  9. ISSUES Dead ends Closest neighbor to destination not always available Face routing remedy used in other protocols

  10. FACE ROUTING Route messages through planar graph Does not scale well

  11. HULL TREES Each node has a "convex hull" Convex hulls contain all descendant nodes within Storage is O(1) vs. O(N)

  12. ROUTING WITH HULL TREES If destination is not within convex hull, forward to the parent If destination is in the convex hull, forward packet

  13. ROUTING WITH HULL TREES CONTINUED... If the packet was in greedy mode previously or was sent from the parent node: Packet will be forwarded to first child node containing destination. If the packet came from a child node: Packet will be forwarded to the next child node that's convex has the destination within it If the packet came from child node from hulls that have destination within: Packet will go to the parent or child node that is also root node.

  14. PERFORMANCE ISSUES Routing via decisions based on trees is slower GDSTR only uses trees when needed GDSTR switches back to greedy routing as soon as possible Tree hops are used as little as possible

  15. CREATION OF HULL TREES Routing performance gains from less overlap between convex hulls Compact trees are ideal and lead to less hop count Smaller trees broadcast chosen parent node and convex hull

  16. ROUTING ALGORITHM Mode: current greedy or tree routing style N min: node where packet switches from greedy to tree routing Tree: identifier for the root of hull tree N anchor: first discovered node while traversing tree

  17. ALGORITHM (GDSTR) 1. Check for Greedy mode switch 2. Greedy Mode 3. Tree Mode 4. Choose Hull Tree 5. Check Hull Tree 6. Not in Hull Tree 7. Check Anchor Node 8. Termination Condition 9. Tree Traversal

  18. 1. CHECKING FOR MODE "If p.mode = Tree and there is at least one immediate neighbor w such that |wt| < |(p.nmin)t|, then set p.mode := Greedy, p.nmin := w and clear p.nanchor and p.tree if they are set. Execute step 2 or 3 according to p.mode"

  19. 2. GREEDY MODE Find the node w in the set of immediate neighbors that is closest to t. If |wt| < |vt|, forward the packet to w. Otherwise, set p.mode := Tree and follow step 3.

  20. 3. TREE MODE If p.tree is not set or if the root for p.tree has changed, follow step 4, else follow step 5.

  21. 4. CHOOSE HULL TREE Choose one of the existing hull trees for forwarding and set p.tree to the chosen tree s identifier. Follow step 5.

  22. 5. CHECK HULL TREE If hull tree does not contain destination node t, follow step 6; otherwise, follow step 7 instead.

  23. 6. NOT IN HULL TREE If none of the hulls in H contains the destination node t conclude that the packet is not deliverable. Otherwise, forward p to the parent node in p.tree.

  24. 7. CHECK ANCHOR NODE If p.nanchor is set, follow step 8. Else, set p.nanchor := v and follow step 9 instead.

  25. 8. TERMINATION CONDITION Given a global ordering for node identifiers, arrange the child nodes (relative to p.tree) with convex hulls that contain the destination point in a ascending sequence according to the global ordering. Then: 5 If v = p.anchor and either (i) u is the last child and v is the root node for p.tree, (ii) u is the last child and the set of conflict hulls H does not contain destination node t, or (iii) u is the parent node, conclude that packet is not deliverable; else If u is the parent node and the set of conflict hulls H does not contain destination node t, set p.nanchor := v. Follow step 9. "

  26. 9. TREE TRAVERSAL If p.mode = Greedy set p.mode := Tree, forward packet to the first child node; If packet was received from the parent node forward packet to the first child node; If packet was received from a child node forward packet to the next child node in the sequence; If packet was received from the last child node if one of the hulls in H contains the destination point; forward packet to the parent node Else forward packet to the first child node.

  27. SIMULATION Unit radio range Communication if and only if within range, and have line of site Wireless issues not accounted for Networks of 25 to 500 nodes Randomly place in 10 x 10 unit square 200 networks tested 20,000 packets routed Source and destination randomly selected

  28. SIMULATION COMPARISONS Greedy Perimeter Stateless Routing (GPSR) Greedy Other Adaptive Face Routing Plus (GOAFR+) Greedy Path Vector Face Routing (GPVFR) Cross-Link Detection Protocol (CLDP) planarization A density of 500 nodes in 100 square units is high enough that greedy forwarding almost always succeeds

  29. ROUTING RESULTS Path stretch: Ratio of path length between nodes Hop stretch: ratio of hops between two nodes against the number of hops on the shortest path Metrics were considered similar enough to be plotted together

  30. ROUTING RESULTS From node degree range 2 to 9 GDSTR outperforms other algorithms Most improvement in the node degree range 4 to 6 GDSTR routes where often shorter Faster delivery Less consumption of radio resources

  31. BANDWIDTH RESULTS GDSTR broadcast (keep alive) vs. CLDP probes Broadcast messaging smaller on average up till a node degree of 4 to 8 Probes contain all point faces 4 to 8 range had largest perimeters

  32. BANDWIDTH RESULTS CLDP probes are sent out until all links are considered dormant or non-routable GDSTR converges when hull information stabalizes

  33. SCALABILITY RESULTS CLDP message count independent of node count GDSTR fail messaging increases gradually with node count GDSTR join messaging independent of node count

  34. CONCLUSIONS Hull trees can be at least as efficient as planar graphs after greedy forwarding GDSTR uses less maintenance bandwidth than CLDP Testing was conducted on stationary two dimensional graphs, but could adapt to mobile multidimensional situation

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#