GREEDY DISTRIBUTED SPANNING TREE ROUTING (GDSTR) CMPE 259:

GREEDY DISTRIBUTED SPANNING TREE ROUTING (GDSTR) CMPE 259:

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.

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 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 trees 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

Recently Viewed Presentations

  • Intorduction to the Creation/Evolution Controversy

    Intorduction to the Creation/Evolution Controversy

    General Overview Creation/Evolution Controversy What, history, importance Biblical Basis for Creation Reliability, archaeology, special revelation Evidence for a Global Flood Scientific Basis for Creation Scientific Case Against Evolution Compromising Theories of Origins Intelligent Design Movement The Impact of Evolution on...
  • Solutions Design - Yale ITS

    Solutions Design - Yale ITS

    Yale Solutions Design ... Systems no longer connect directly thereby allowing greater control and enforcement of the following principles: Standards Security Governance Reusability Consistency Data Integrity We can build and leverage a suite of business services that can be assembled...
  • TIME OF USE RATES EDUCATION & OUTREACH FOR

    TIME OF USE RATES EDUCATION & OUTREACH FOR

    for customers that do not have a SCE generator output meter. Standby Demand (SB) kW = the load that the generator regularly serves and SCE is expected to instantaneously provide when the generator goes down, excluding any SCC . SB...
  • Assembly Language - cs.colostate.edu

    Assembly Language - cs.colostate.edu

    First In, Last Out (FILO) data structure. PUSH adds data, POP removes data. Stack grows and shrinks as data is added and removed. Stack grows downward in memory. ... Stack frame below this frame contains the function that called this...
  • Science with Antarctic Infrared and Sub-millimetre Telescopes

    Science with Antarctic Infrared and Sub-millimetre Telescopes

    The UNSW-CSIRO Millimetre Collaboration: An overview of the Star Formation Program Michael Burton UNSW / CSIRO Collaboration MNRF-funded upgrade to ATCA (1997) UNSW SIP grant (1999-2001): Extend dish to 22-m for mm-capable performance Operate over mm "season" Research Tool Teaching...
  • collegiate.dsbn.org

    collegiate.dsbn.org

    Select & change answers. Getting Started... Logging On and Signing In: On the day of the OSSLT testing, Log onto a DSBN device using your DSBN credentials. Click on the EQAO Online Kiosk App on your desktop. ... Practice using...
  • Bellringer - Loudoun County Public Schools

    Bellringer - Loudoun County Public Schools

    The Eastern Hemisphere. Japan. Geography. Archipelago (4 islands) east of China in the Pacific. Mountainous islands with little farmland. Separated from the mainland by the Sea of Japan. Close to China and Korea. Government.
  • ECMO Coding Changes Karen Bridgeman, MSN, RN, CCDS

    ECMO Coding Changes Karen Bridgeman, MSN, RN, CCDS

    APR-DRG 133 Respiratory Failure. MS-DRG. MS-DRG 003 ECMO or Trach w Vent >96 HRS or PDX EXC Face, Mouth & Neck w Maj O.R. MS-DRG 207 Respiratory System Diagnosis w Ventilator Support >96 HRS or Peripheral Extracorporeal Membrane Oxygenation (ECMO)