10/5/06 Jie Gao, CSE590-fall06 1Geometric Routing in Sensor Networks III: Geometric Routing in Sensor Networks III: Explore the Global TopologyExplore the Global TopologyJie GaoComputer Science DepartmentStony Brook University10/5/06 Jie Gao, CSE590-fall06 2Routing around holesRouting 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 3IntuitionIntuition• 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 4Routing around holesRouting around holesRouting ruleFace routing: short-sightedTwo ways to get around the hole10/5/06 Jie Gao, CSE590-fall06 5Topology is importantTopology 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 6General methodologyGeneral methodology• 2-level infrastructure• Top-level: capture the global topology.– Where the holes are (e.g., CS building, Javitzcenter, 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 722--level infrastructurelevel 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 8PapersPapers• 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 9GLIDER: LandmarkGLIDER: Landmark--based schemesbased schemes• We use landmarks in real life:– 5thave and 42 street.– Two blocks after bank of America.• Use landmark-based virtual coordinates.10/5/06 Jie Gao, CSE590-fall06 10Combinatorial Delaunay graphCombinatorial Delaunay graph• Given a communication graph on sensor nodes, with path length in shortest path hop counts• Landmarks flood the network. Each node learns the hop count to each landmark.• Construct Landmark Voronoi Complex (LVC)• Select a set of landmarks10/5/06 Jie Gao, CSE590-fall06 11Combinatorial Delaunay graphCombinatorial Delaunay graph• 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.• Construct Landmark Voronoi Complex (LVC)10/5/06 Jie Gao, CSE590-fall06 12Combinatorial Delaunay graphCombinatorial 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 13Virtual coordinatesVirtual coordinatesresident tilehome landmark(think about post-office)preference landmarksEach node stores virtual coordinates (d1, d2, d3, … dk), dk= hop count to the kth reference landmark (home+neighboringlandmarks)Boundary nodes10/5/06 Jie Gao, CSE590-fall06 14Theorem: If G is connected, then the Combinatorial Delaunay graph D(L) for any subset of landmarks is also connected.1. Compact and stable2. Abstract the connectivity graph: Each edge can be mapped to a path that uses onlythe nodes in the two corresponding Voronoitiles; Each path in G can be “lifted” to a path in D(L)Combinatorial Delaunay graphCombinatorial Delaunay graph10/5/06 Jie Gao, CSE590-fall06 15Information Stored at Each NodeInformation 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 routing10/5/06 Jie Gao, CSE590-fall06 16Virtual coordinatesVirtual 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 17Local Routing with Global GuidanceLocal Routing with Global Guidance• Global Guidance: routing on tilesthe 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 18GLIDER GLIDER ----RoutingRouting2. Local routing– Inter-tile routingppppqqqquuuu3333uuuu2222uuuu11111. Global planning– Intra-tile routing10/5/06 Jie Gao, CSE590-fall06 19IntraIntra--tile routingtile routing• 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.L2L1pL5L4L3L0q• A bogus proposal: p routes to the home landmark then routes to q.10/5/06 Jie Gao, CSE590-fall06 20Local virtual coordinates:c(p)= (pL02– s,…, pLk2– s)(centered metric)Distance function:d(p, q) = |c(p) – c(q)|2Centered LandmarkCentered Landmark--Distance Coordinates and Distance Coordinates and Greedy RoutingGreedy RoutingGreedy strategy: to reach q, do gradient descent on the function d(p, q)L2L1pL5L4L3L0qReference landmarks: L0,…LkT(p) = L0Let s = mean(pL02,…, pLk2)10/5/06 Jie Gao, CSE590-fall06 21Local Landmark Coordinates Local Landmark Coordinates ––No Local MinimumNo 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