9/25/05 Jie Gao CSE590-fall06 1LocationLocation--based Routing in based Routing in Sensor Networks ISensor Networks IJie GaoComputer Science DepartmentStony Brook University9/25/05 Jie Gao CSE590-fall06 2PapersPapers• [Karp00] Karp, B. and Kung, H.T., Greedy Perimeter Stateless Routing for Wireless Networks, in MobiCom2000.• [Gao01] J. Gao, L. Guibas, J. Hershberger, L. Zhang, A. Zhu, Geometric Spanner for Ad hoc Mobile Networks, in MobiHoc'01.9/25/05 Jie Gao CSE590-fall06 3Routing in ad hoc networksRouting in ad hoc networks• Obtain route information between pairs of nodes wishing to communicate. • Proactive protocols: maintain routing tables at each node that is updated as changes in the network topology are detected.– Heavy overhead with high network dynamics (caused by link/node failures or node movement).– Not practical for ad hoc networks.9/25/05 Jie Gao CSE590-fall06 4Routing in ad hoc networksRouting in ad hoc networks• Reactive protocols: routes are constructed on demand. No global routing table is maintained.• Due to the high rate of topology changes, reactive protocols are more appropriate for ad hoc networks.– Ad hoc on demand distance vector routing (AODV)– Dynamic source routing (DSR)• However, both depend on flooding for route discovery.9/25/05 Jie Gao CSE590-fall06 5Geographical routingGeographical routing• “Data-centric” routing: routing is frequently based on a nodes’attributes and sensed data, rather than on pre-assigned network address.• Geographical routing uses a node’slocation to discover path to that route.9/25/05 Jie Gao CSE590-fall06 6Geographical routingGeographical routing• Assumptions:– Nodes know their geographical location– Nodes know their 1-hop neighbors– Routing destinations are specified geographically (a location, or a geographical region)– Each packet can hold a small amount (O(1)) of routing information.– The connectivity graph is modeled as a unit disk graph.9/25/05 Jie Gao CSE590-fall06 7Geographical routingGeographical routing• The source node knows – The location of the destination node;– The location of itself and its 1-hop neighbors.• Geographical forwarding: send the packet to the 1-hop neighbor that makes most progress towards the destination. – No flooding is involved.• Many ways to measure “progress”.– The one closest to the destination in Euclidean distance.– The one with smallest angle towards the destination: “compass routing”.9/25/05 Jie Gao CSE590-fall06 8Greedy progressGreedy progress9/25/05 Jie Gao CSE590-fall06 9Compass routing may get in loopsCompass routing may get in loops• Compass routing may get in a loop.Send packets to the neighbor with smallest angle towards the destination9/25/05 Jie Gao CSE590-fall06 10Geographical routing may get stuckGeographical routing may get stuck• Geographical routing may stuck at a node whose neighbors are all further away from the destination than itself.tst?sSend packets to the neighbor closest to the destination9/25/05 Jie Gao CSE590-fall06 11How to get around local minima?How to get around local minima?• Use a planar subgraph: a straight line graph with no crossing edges. It subdivides the plane into connected regions called faces.9/25/05 Jie Gao CSE590-fall06 12Face RoutingFace Routing• Keep left hand on the wall, walk until hit the straight line connecting source to destination.• Then switch to the next face.s t9/25/05 Jie Gao CSE590-fall06 13• All necessary information is stored in the message– Source and destination positions– The node when it enters face routing mode.– The first edge on the current face.• Completely local:– Knowledge about direct neighbors’ positions is sufficient– Faces are implicit. Only local neighbor ordering around each node is needed.Face Routing PropertiesFace Routing Properties“Right Hand Rule”9/25/05 Jie Gao CSE590-fall06 14What if the destination is disconnected?What if the destination is disconnected?• Face routing will get back to where it enters the perimeter mode.• Failed – no way to the destination. • Guaranteed delivery of a message if there is a path.9/25/05 Jie Gao CSE590-fall06 15Face routing needs a planar graphFace routing needs a planar graph……..Compute a planar subgraph of the unit disk graph.– Preserves connectivity.– Distributed computation.9/25/05 Jie Gao CSE590-fall06 16A detour on Delaunay triangulationA detour on Delaunay triangulation9/25/05 Jie Gao CSE590-fall06 17Delaunay triangulationDelaunay triangulation• First proposed by B. Delaunay in 1934.• Numerous applications since then.9/25/05 Jie Gao CSE590-fall06 18VoronoiVoronoidiagramdiagram• Partition the plane into cells such that all the points inside a cell have the same closest point.Voronoi vertexVoronoi cellVoronoi edge9/25/05 Jie Gao CSE590-fall06 19Delaunay triangulationDelaunay triangulation• Dual of Voronoi diagram: Connect an edge if their Voronoi cells are adjacent.• Triangulation of the convex hull.9/25/05 Jie Gao CSE590-fall06 20Delaunay triangulationDelaunay triangulation• “Empty-circle property”: the circumcircle of a Delaunay triangle is empty of other points.• The converse is also true: if all the triangles in a triangulation are locally Delaunay, then the triangulation is a Delaunay triangulation.9/25/05 Jie Gao CSE590-fall06 21Greedy routing on Delaunay triangulationGreedy routing on Delaunay triangulation• Claim: Greedy routing on DT never gets stuck.9/25/05 Jie Gao CSE590-fall06 22Delaunay triangulationDelaunay triangulation• For an arbitrary point set, the Delaunay triangulation may contain long edges.• Centralized construction.• If the nodes are uniformly placed inside a unit disk, the longest Delaunay edge is O((logn/n)1/3). [Kozmaet.al. PODC’04]• Next: 2 planar subgraphs that can be constructed in a distributed way: relative neighborhood graph and the Gabriel graph.9/25/05 Jie Gao CSE590-fall06 23Relative Neighborhood Graph and Gabriel Relative Neighborhood Graph and Gabriel GraphGraph• Relative Neighborhood Graph (RNG) contains an edge uv if the lune is empty of other points.• Gabriel Graph (GG) contains an edge uv if the disk with uv as diameter is empty of other points.• Both can be constructed in a distributed way.9/25/05 Jie Gao CSE590-fall06 24Relative Neighborhood Graph and Gabriel GraphRelative Neighborhood Graph and Gabriel Graph• Claim: MST ⊆ RNG ⊆ GG ⊆ Delaunay• Thus, RNG and GG are