Location based Routing in Sensor Networks Jie Gao Computer Science Department Stony Brook University 9 22 05 Jie Gao CSE590 fall05 1 Location based routing Greedy forwarding send the packet to the neighbor closest to the destination Face routing on a planar subgraph t s 9 22 05 Jie Gao CSE590 fall05 2 Two 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 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 a short 3 Tackle problem I Find a planar spanner 9 22 05 Jie Gao CSE590 fall05 4 Find a good subgraph 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 9 22 05 Euclidean spanning ratio 2 Hop spanning ratio 2 Let s first focus on Euclidean spanner Jie Gao CSE590 fall05 5 Delaunay triangulation is an Euclidean spanner 9 22 05 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 Jie Gao CSE590 fall05 6 Restricted Delaunay graph 9 22 05 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 Jie Gao CSE590 fall05 7 Construction 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 8 Detect crossings between local delaunay edges 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 9 22 05 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 Jie Gao CSE590 fall05 9 Restricted Delaunay graph 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 9 22 05 b Jie Gao CSE590 fall05 10 Restricted Delaunay graph 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 Delaunay triangulation How to tell that an edge is not in the Delaunay triangulation 9 22 05 Jie Gao CSE590 fall05 11 Removing non Delaunay edges If two edges AB CD cross there are only three cases 9 22 05 Jie Gao CSE590 fall05 12 Removing non Delaunay edges If two edges AB CD cross there are only three cases The shape is fixed Node C can tell which edge is not Delaunay 9 22 05 Jie Gao CSE590 fall05 13 Removing non Delaunay edges Case i Use the empty circle test of Delaunay triangulation AC 1 CD BC 1 CD Conclusion The edge AB is not a Delaunay edge 9 22 05 Jie Gao CSE590 fall05 14 Find 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 9 22 05 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 Jie Gao CSE590 fall05 15 Reduce 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 a clusterhead 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 3 9 22 05 Jie Gao CSE590 fall05 16 Connect clusterheads by 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 17 Path on clusterheads and gateways For two nodes u v that are k hops away there is a path through clusterheads and gateways with at most 3k 2 hops 3k clusterheads Shortest path 9 22 05 Construct RDG on clusterheads and gateways which have constant bounded density Jie Gao CSE590 fall05 18 A Routing Graph Sample 9 22 05 Jie Gao CSE590 fall05 19 Restricted Delaunay graph Claim RDG on clusterheads and gateways edges from clients to clusterheads is a constant hop spanner of the original UDG clusterheads H and gateways P unit disk graph 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 2 42 3k 2 has O k nodes inside So hops of H is O k This concludes the hop spanner property 9 22 05 Jie Gao CSE590 fall05 20 Restricted Delaunay graph 9 22 05 RNG Jie Gao CSE590 fall05 RDG 21 Restricted Delaunay graph 9 22 05 RNG Jie Gao CSE590 fall05 RDG 22 Tackle problem II Improve face routing to find a short path 9 22 05 Jie Gao CSE590 fall05 23 Lower bound of localized routing Any deterministic or randomized localized routing algorithm takes a path of length k2 if the optimal path has length k The adversary decides where the chain wt is Since we store no information on nodes in the worst case we have to visit about k chains and pay a cost of k2 9 22 05 Jie Gao CSE590 fall05 t s 24 Performance of greedy routing If greedy routing gets to the destination then the path length is at most O k2 if the optimal path has length k uv is at most k On the greedy path every other node is not visible so they are of distance at least 1 away By a packing lemma there …