Location based Routing in Sensor Networks I Jie Gao Computer Science Department Stony Brook University 9 25 05 Jie Gao CSE590 fall06 1 Papers 9 25 05 Karp00 Karp B and Kung H T Greedy Perimeter Stateless Routing for Wireless Networks in MobiCom 2000 Gao01 J Gao L Guibas J Hershberger L Zhang A Zhu Geometric Spanner for Ad hoc Mobile Networks in MobiHoc 01 Jie Gao CSE590 fall06 2 Routing 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 9 25 05 Heavy overhead with high network dynamics caused by link node failures or node movement Not practical for ad hoc networks Jie Gao CSE590 fall06 3 Routing 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 9 25 05 Ad hoc on demand distance vector routing AODV Dynamic source routing DSR However both depend on flooding for route discovery Jie Gao CSE590 fall06 4 Geographical routing 9 25 05 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 s location to discover path to that route Jie Gao CSE590 fall06 5 Geographical 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 6 Geographical routing The source node knows 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 9 25 05 The location of the destination node The location of itself and its 1 hop neighbors The one closest to the destination in Euclidean distance The one with smallest angle towards the destination compass routing Jie Gao CSE590 fall06 7 Greedy progress 9 25 05 Jie Gao CSE590 fall06 8 Compass routing may get in loops Compass routing may get in a loop Send packets to the neighbor with smallest angle towards the destination 9 25 05 Jie Gao CSE590 fall06 9 Geographical routing may get stuck Geographical routing may stuck at a node whose neighbors are all further away from the destination than itself t s t s Send packets to the neighbor closest to the destination 9 25 05 Jie Gao CSE590 fall06 10 How to get around local minima 9 25 05 Use a planar subgraph a straight line graph with no crossing edges It subdivides the plane into connected regions called faces Jie Gao CSE590 fall06 11 Face Routing Keep left hand on the wall walk until hit the straight line connecting source to destination Then switch to the next face s 9 25 05 t Jie Gao CSE590 fall06 12 Face Routing Properties 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 Right Hand Rule 9 25 05 Jie Gao CSE590 fall06 13 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 14 Face 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 15 A detour on Delaunay triangulation 9 25 05 Jie Gao CSE590 fall06 16 Delaunay triangulation 9 25 05 First proposed by B Delaunay in 1934 Numerous applications since then Jie Gao CSE590 fall06 17 Voronoi diagram Partition the plane into cells such that all the points inside a cell have the same closest point Voronoi cell Voronoi edge Voronoi vertex 9 25 05 Jie Gao CSE590 fall06 18 Delaunay triangulation 9 25 05 Dual of Voronoi diagram Connect an edge if their Voronoi cells are adjacent Triangulation of the convex hull Jie Gao CSE590 fall06 19 Delaunay 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 20 Greedy routing on Delaunay triangulation Claim Greedy routing on DT never gets stuck 9 25 05 Jie Gao CSE590 fall06 21 Delaunay 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 Kozma et 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 22 Relative Neighborhood Graph and Gabriel Graph 9 25 05 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 Jie Gao CSE590 fall06 23 Relative Neighborhood Graph and Gabriel Graph Claim MST RNG GG Delaunay Thus RNG and GG are planar Delaunay is planar and keep the connectivity MST has the same connectivity of UDG 9 25 05 Jie Gao CSE590 fall06 24 MST RNG GG Delaunay 1 2 9 25 05 RNG GG if the lune is empty then the disk with uv as diameter is also empty GG Delaunay the disk with uv as diameter is empty then uv is a Delaunay edge Jie Gao CSE590 fall06 25 MST RNG GG Delaunay 3 MST RNG Assume uv in MST is not in RNG there is a point w inside the lune uv uw uv vw Now we delete uv and partition the MST into two subtrees Say w is in the same component with u then we can replace uv by wv and get a lighter tree contradiction RNG and GG are planar Delaunay is planar and keep the connectivity MST has the same connectivity of UDG 9 25 05 Jie Gao CSE590 fall06 26 An example of UDG 200 nodes randomly deployed in a 2000 2000 meters region Radio range 250meters 9 25 05 Jie Gao CSE590 fall06 27 An example of GG and RNG RNG GG 9 25 05 Jie Gao CSE590 fall06 28 Two problems remain Both RNG and GG remove some edges a