Geometric Routing in Sensor Networks III Explore the Global Topology Jie Gao Computer Science Department Stony Brook University 10 5 06 Jie Gao CSE590 fall06 1 Routing around holes Real world deployment is not uniform has holes due to buildings landscape variation Face routing is too Short sighted and greedy Boundary nodes get overloaded 10 5 06 Jie Gao CSE590 fall06 2 Intuition When sensors are densely uniformly deployed greedy forwarding is sufficient most of the time When the sensor field is irregular holes become prominent capture this topological information for routing What is wrong with greedy routing with holes Mismatch between routing rule network connectivity 10 5 06 Jie Gao CSE590 fall06 3 Routing around holes Routing rule Two ways to get around the hole Face routing short sighted 10 5 06 Jie Gao CSE590 fall06 4 Topology is important The global topology of the sensor field holes genus Positions of holes Three questions How to extract it How to represent it How to use it 10 5 06 Jie Gao CSE590 fall06 5 General methodology 2 level infrastructure Top level capture the global topology Where the holes are e g CS building Javitz center etc General routing guidance e g get around the Javitz center go straight to SAC Bottom level capture the local connectivity Gradient descent to realize the routing path 10 5 06 Jie Gao CSE590 fall06 6 2 level infrastructure Why this makes sense Global topology is stable the position of buildings are unlikely to change often Global topology is compact a small number of buildings From each node s point of view A rough guidance Local greedy rule 10 5 06 Jie Gao CSE590 fall06 7 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 Major difference different ways to capture the global topology 10 5 06 Jie Gao CSE590 fall06 8 GLIDER Landmark based schemes We use landmarks in real life 5th ave and 42 street Two blocks after bank of America Use landmark based virtual coordinates 10 5 06 Jie Gao CSE590 fall06 9 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 10 5 06 Jie Gao CSE590 fall06 10 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 If flooding are synchronized then restricted flooding up to the boundary nodes is enough 10 5 06 Jie Gao CSE590 fall06 11 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 10 5 06 Jie Gao CSE590 fall06 12 Virtual coordinates Each node stores virtual coordinates d1 d2 d3 dk dk hop count to the kth reference landmark home neighboring landmarks home landmark think about post office resident tile p reference landmarks 10 5 06 Boundary nodes Jie Gao CSE590 fall06 13 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 and stable 2 Abstract the connectivity graph 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 10 5 06 Jie Gao CSE590 fall06 14 Information Stored at Each Node The shortest path tree on D L rooted at its home landmark Its coordinates and those of its neighbors for greedy routing 10 5 06 Jie Gao CSE590 fall06 15 Virtual coordinates With the virtual coordinates a node can test if It is on the boundary two closest landmarks A neighbor who is closer to a reference landmark 10 5 06 Jie Gao CSE590 fall06 16 Local Routing with Global Guidance Global Guidance routing on tiles the D L that encodes global connectivity information is accessible to every node for proactive route planning on tiles Local Routing how to go from tile to tile high level routes on tiles are realized as actual paths in the network by using reactive protocols 10 5 06 Jie Gao CSE590 fall06 17 GLIDER Routing 1 Global planning u2 2 Local routing Inter tile routing u1 Intra tile routing p 10 5 06 Jie Gao CSE590 fall06 u3 q 18 Intra tile routing L5 L1 p L0 L4 L3 10 5 06 q 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 fall06 19 Centered Landmark Distance Coordinates and Greedy Routing L5 L1 Reference landmarks L0 Lk T p L0 2 p L0 L4 q Local virtual coordinates 2 2 c p pL0 s pLk s centered metric L2 L3 2 Let s mean pL0 pLk Distance function 2 d p q c p c q Greedy strategy to reach q do gradient descent on the function d p q 10 5 06 Jie Gao CSE590 fall06 20 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 10 5 06 Landmark i is a linear function Jie Gao CSE590 fall06 21 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 10 5 06 Jie Gao CSE590 fall06 22 u2 u1 u3 q p 10 5 06 Jie Gao CSE590 fall06 23 Examples 10 5 06 Each node on average has 6 one hop Jie Gao CSE590 fall06 neighbors 24 Simulations Path Length and Load Balancing GLIDER 41 hops GPSR 52 hops Each node on average has 6 one hop neighbors 10 5 06 Jie Gao CSE590 fall06 25 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