9/22/05 Jie Gao, CSE590-fall05 1LocationLocation--based Routing in based Routing in Sensor NetworksSensor NetworksJie GaoComputer Science DepartmentStony Brook University9/22/05 Jie Gao, CSE590-fall05 2LocationLocation--based routingbased routing• Greedy forwarding: send the packet to the neighbor closest to the destination.• Face routing on a planar subgraph.ts9/22/05 Jie Gao, CSE590-fall05 3Two problems remainTwo problems remain• A subgraph G’ of G is a α-spanner if the shortest path in G’ is bounded by a constant α times the shortest path length in G.• Both RNG and GG are not spanners  a short path may not exist!• Even if the planar subgraph contains a short path, can greedy routing and face routing find a short one?9/22/05 Jie Gao, CSE590-fall05 4Tackle problem I: Tackle problem I: Find a planar spannerFind a planar spanner9/22/05 Jie Gao, CSE590-fall05 5Find a good Find a good subgraphsubgraph• Goal: a planar spanner such that the shortest path is at most α times the shortest path in the unit disk graph.– Euclidean spanner: The shortest path length is measured in total Euclidean length. – Hop spanner: The shortest path length is measured in hop count. • α: spanning ratio.– Euclidean spanning ratio ≥– Hop spanning ratio ≥ 2.• Let’s first focus on Euclidean spanner.29/22/05 Jie Gao, CSE590-fall05 6DelaunayDelaunaytriangulation is an Euclidean triangulation is an Euclidean spannerspanner• DT is a 2.42-spanner of the Euclidean distance.• For any two nodes uv, the Euclidean length of the shortest path in DT is at most 2.42 times |uv|.9/22/05 Jie Gao, CSE590-fall05 7Restricted Restricted DelaunayDelaunaygraphgraph• Keep all the Delaunay edges no longer than 1.• Claim: RDG is a 2.42-spanner (in total Euclidean length) of the UDG.• Proof sketch: If an edge in UDG is deleted in RDG, then it’s replaced by a path with length at most 2.42 longer.9/22/05 Jie Gao, CSE590-fall05 8Construction of RDGConstruction of RDG• Easy to compute a superset of RDG: Each node computes a local Delaunay of its 1-hop neighbors.– A global Delaunay edge is always a local Delaunay edge, due to the empty-circle property.– A local Delaunay may not be a global Delaunay edges.• What if the superset have crossing edges?9/22/05 Jie Gao, CSE590-fall05 9Detect crossings between local Detect crossings between local delaunay delaunay edgesedges• By the crossing Lemma: if two edges cross in a UDG, one of them has 3 nodes in its neighborhood and can tell which one is not Delaunay. • Neighbors exchange their local DTs to resolve inconsistency.• A node tells its 1-hop neighbors the non-Delaunay edges in its local graph.• A node receiving a “forbidden” edge will delete it from its local graph.• Completely distributed and local.9/22/05 Jie Gao, CSE590-fall05 10Restricted Restricted DelaunayDelaunaygraphgraph• 1-hop information exchange is sufficient.– Planar graph;– All the short Delaunay edges are included.– We may have some planar non-Delaunay edges but that does not hurt spanning property.a    b   9/22/05 Jie Gao, CSE590-fall05 11Restricted Restricted DelaunayDelaunaygraphgraph• RDG can be constructed without the full location information.• Only local angle information suffices.• Key operation: If two edges in the unit-disk graph cross, remove the one that is not in the Delaunaytriangulation.• How to tell that an edge is not in the Delaunaytriangulation?9/22/05 Jie Gao, CSE590-fall05 12Removing nonRemoving non--Delaunay Delaunay edgesedgesIf two edges AB, CD cross, there are only three cases:9/22/05 Jie Gao, CSE590-fall05 13If two edges AB, CD cross, there are only three cases:The shape is fixed!Node C can tell which edge is not Delaunay.Removing nonRemoving non--Delaunay Delaunay edgesedges9/22/05 Jie Gao, CSE590-fall05 14Case (i) : Use the “empty-circle” test of Delaunay triangulationConclusion: The edge AB is not a Delaunay edge.Removing nonRemoving non--Delaunay Delaunay edgesedges|AC| > 1 ≥ |CD||BC| > 1 ≥ |CD|9/22/05 Jie Gao, CSE590-fall05 15Find a hop spannerFind a hop spanner• Restricted delaunay graph is not a hop spanner.• Take n nodes, each pair is within distance 1. The hop count can be as large as n. • Reduce the density of the sensors.• Use clustering to reduce density.• Compute RDG on the subset to get a hop spanner.• Clustering also reduce interference and enables efficient resource reuse such as bandwidth.9/22/05 Jie Gao, CSE590-fall05 16Reduce node densityReduce node density• Find a subset of nodes, called clusterheads– Each node is directly connected to at least 1 clusterhead.– No two clusterheads are connected.• Use a greedy algorithm. Pick a node as aclusterhead, remove all the 1-hop neighbors, continue. • Constant density: ≤ 6 clusterheads in any unit disk.– The angle spanned by two clusterheads is at least π/6.π/39/22/05 Jie Gao, CSE590-fall05 17Connect Connect clusterheads clusterheads by gatewaysby gateways• For two clusterheads, if their clients have an edge, then we pick one pair as gateway nodes.• Notice that clusterheads x, y are within 3 hops to have a pair of gateways.• There are constant clusterheads and gateways inside any unit disk.9/22/05 Jie Gao, CSE590-fall05 18Path on Path on clusterheads clusterheads and gatewaysand gateways• For two nodes u, v that are k hops away, there is a path throughclusterheads and gateways with at most 3k+2 hops. • Construct RDG on clusterheads and gateways, which have constant bounded density.3kclusterheadsShortest path9/22/05 Jie Gao, CSE590-fall05 19A Routing Graph SampleA Routing Graph Sample     9/22/05 Jie Gao, CSE590-fall05 20Restricted Restricted DelaunayDelaunaygraphgraph• Claim: (RDG on clusterheads and gateways + edges from clients to clusterheads) is a constant hop spanner of the original UDG.• Proof sketch: – The shortest path P in the unit disk graph has k hops.– Though clusterheads and gateways ∃ a path Q with ≤ 3k+2 hops. – Q’s total Euclidean length is ≤ 3k+2.– The shortest path on the RDG, H, has Euclidean length ≤2.42×(3k+2).– By constant density property a region with width 1 and length