Location free Routing in Sensor Networks Explore the Global Topology Jie Gao Computer Science Department Stony Brook University 9 29 05 Jie Gao CSE590 fall05 1 Papers Qing Fang Jie Gao Leonidas Guibas Vin de Silva Li Zhang GLIDER Gradient Landmark Based Distributed Routing for Sensor Networks Proc of the 24th Conference of the IEEE Communication Society INFOCOM 05 March 2005 J Bruck J Gao A Jiang MAP Medial Axis Based Geometric Routing in Sensor Networks to appear in the 11th Annual International Conference on Mobile Computing and Networking MobiCom 05 August 2005 9 29 05 Jie Gao CSE590 fall05 2 Routing in a dense sensor field with complex geometry Is there an efficient routing scheme for dense sensor filed with complex geometry Light weight Localized routing Guaranteed delivery Load balancing Robust to dynamic change 9 29 05 Jie Gao CSE590 fall05 3 General methodology 2 level architecture When the sensor field has complex geometric shape or nontrivial topology Top level a compact abstraction of the global geometry topology of the sensor field E g there is a hole in the middle of the sensor field Bottom level a naming scheme with respect to the global topology that enables local gradient routing 9 29 05 Jie Gao CSE590 fall05 4 General methodology routing Top level a compact abstraction of the global geometry topology of the sensor field Check the compact abstract graph to get a global guidance on how to get around obstacles Bottom level a naming scheme with respect to the global topology that enables local gradient routing The actual routing is local gradient descending 9 29 05 Jie Gao CSE590 fall05 5 General methodology routing Top level a compact abstraction of the global geometry topology of the sensor field Stable topological information is proactively maintained Bottom level a naming scheme with respect to the global topology that enables local gradient routing Actual routing is local and reactive 9 29 05 Jie Gao CSE590 fall05 6 GLIDER Gradient Landmark based Distributed Routing for Sensor Networks 9 29 05 Jie Gao CSE590 fall05 7 Combinatorial Delaunay graph Given a communication graph on sensor nodes with path length in shortest path hop counts Select a set of landmarks Landmarks flood the network Each node learns the hop count to each landmark Construct Landmark Voronoi Complex LVC 9 29 05 Jie Gao CSE590 fall05 8 Combinatorial Delaunay graph Construct Landmark Voronoi Complex LVC Each sensor identifies its closest landmark A sensor is on the boundary if it has 2 closest landmarks or its distance to its closest and 2nd closest landmarks differs by 1 due to rounding error If flooding are synchronized then restricted flooding up to the boundary nodes is enough 9 29 05 Jie Gao CSE590 fall05 9 Combinatorial Delaunay graph Construct Combinatorial Delaunay Triangulation CDT on landmarks If there is at least one boundary node between landmark i and j then there is an edge ij in CDT Holes in the sensor field map to holes in CDT CDT is broadcast to the whole network 9 29 05 Jie Gao CSE590 fall05 10 Definitions 9 29 05 Jie Gao CSE590 fall05 11 Combinatorial Delaunay graph Theorem If G is connected then the Combinatorial Delaunay graph D L for any subset of landmarks is also connected 1 Compact 2 Each edge in D L is relatively stable 3 Each edge can be mapped to a path that uses only the nodes in the two corresponding Voronoi tiles Each path in G can be lifted to a path in D L 9 29 05 Jie Gao CSE590 fall05 12 Information Stored at Each Node The shortest path tree on D L rooted at its home landmark The predecessors on the shortest path trees in the network rooted at its reference landmarks i e the next hop towards the reference landmark A bit to record if the node is on the boundary of a tile Its coordinates and those of its neighbors for greedy routing 9 29 05 Jie Gao CSE590 fall05 13 Local Routing with Global Guidance Global Guidance the D L that encodes global connectivity information is accessible to every node for proactive route planning on tiles Local Routing high level routes on tiles are realized as actual paths in the network by using reactive protocols 9 29 05 Jie Gao CSE590 fall05 14 GLIDER Routing 1 Global planning 2 Local routing Inter tile routing Intra tile routing 9 29 05 u2 u1 u3 q p Jie Gao CSE590 fall05 15 Intra tile routing L5 L1 p q L0 L4 L3 9 29 05 How to route from one node to the other inside a tile Each node knows the hop count to home landmark and neighboring landmarks No idea where the landmarks are L2 A bogus proposal p routes to the home landmark then routes to q Jie Gao CSE590 fall05 16 Centered Landmark Distance Coordinates and Greedy Routing L5 Reference landmarks L0 Lk L1 T p L0 2 2 Let s mean pL0 pLk p q Local virtual coordinates L0 L4 2 centered metric L2 L3 2 c p pL0 s pLk s Distance function 2 d p q c p c q Greedy strategy to reach q do gradient descent on the function d p q 9 29 05 Jie Gao CSE590 fall05 17 Local Landmark Coordinates No Local Minimum Theorem In the continuous Euclidean plane gradient descent on the function d p q always converges to the destination q for at least three non collinear landmarks Landmark distance coordinates Centered coordinates The function function 9 29 05 Landmark i is a linear Jie Gao CSE590 fall05 18 Node Density vs Success Rate of Greedy Routing In the discrete case we empirically observe that landmark gradient descending does not get stuck on networks with reasonable density each node has on average six neighbors or more 2000 nodes distributed on a perturbed grid Perturbation Gaussian 0 0 5r where r is the radio range 9 29 05 Jie Gao CSE590 fall05 19 u2 u1 u3 q p 9 29 05 Jie Gao CSE590 fall05 20 Examples Each node on average has 6 one hop neighbors 9 29 05 Jie Gao CSE590 fall05 21 Simulations Path Length and Load Balancing GLIDER 41 hops GPSR 52 hops Each node on average has 6 one hop neighbors 9 29 05 Jie Gao CSE590 fall05 22 Simulations Hot Spots Comparison Randomly pick 45 source and destination pairs each separated by more than 30 hops GLIDER GPSR Blue 6 8 transit paths orange 9 11 transit paths black 11 transit paths 9 29 05 Jie Gao CSE590 fall05 23 Open issues How to select landmarks What is a good criterion in selecting landmarks What can we say about the intra tile greedy routing on a discrete network Notice that one of the challenges is that the hop count is a rough estimation of the Euclidean distance And the approximation is independent of the sensor density 9 29 05 Jie Gao CSE590 fall05 24 MAP