9/29/05 Jie Gao, CSE590-fall05 1LocationLocation--free Routing in free Routing in Sensor Networks Sensor Networks ––Explore the Global Explore the Global TopologyTopologyJie GaoComputer Science DepartmentStony Brook University9/29/05 Jie Gao, CSE590-fall05 2PapersPapers• 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 3Routing in a dense sensor field with Routing in a dense sensor field with complex geometrycomplex 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 4General methodology: 2General methodology: 2--level architecturelevel 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 5General methodology: routingGeneral 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 6General methodology: routingGeneral 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 7GLIDER: GLIDER: Gradient LandmarkGradient Landmark--based Distributed Routing based Distributed Routing for Sensor Networksfor Sensor Networks9/29/05 Jie Gao, CSE590-fall05 8Combinatorial Combinatorial Delaunay Delaunay graphgraph• 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 VoronoiComplex (LVC)• Select a set of landmarks9/29/05 Jie Gao, CSE590-fall05 9Combinatorial Combinatorial Delaunay Delaunay graphgraph• 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 2ndclosest landmarks differs by 1 (due to rounding error).• If flooding are synchronized, then restricted flooding up to the boundary nodes is enough.• Construct Landmark Voronoi Complex (LVC)9/29/05 Jie Gao, CSE590-fall05 10Combinatorial Combinatorial Delaunay Delaunay graphgraph• 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 11DefinitionsDefinitions           9/29/05 Jie Gao, CSE590-fall05 12Theorem: If G is connected, then the Combinatorial Delaunay graph D(L) for any subset of landmarks is also connected.1. Compact2. 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)Combinatorial Combinatorial Delaunay Delaunay graphgraph9/29/05 Jie Gao, CSE590-fall05 13Information Stored at Each NodeInformation 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 routing9/29/05 Jie Gao, CSE590-fall05 14Local Routing with Global GuidanceLocal Routing with Global Guidance• Global Guidancethe D(L) that encodes global connectivity information is accessible to every node for proactive route planning on tiles.• Local Routinghigh-level routes on tiles are realized as actual paths in the network by using reactive protocols.9/29/05 Jie Gao, CSE590-fall05 15GLIDER GLIDER ----RoutingRouting2. Local routing– Inter-tile routingpqu3u2u11. Global planning– Intra-tile routing9/29/05 Jie Gao, CSE590-fall05 16IntraIntra--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.9/29/05 Jie Gao, CSE590-fall05 17Local virtual coordinates:c(p)= (pL02– s,…, pLk2– s)(centered metric)Distance function:d(p, q) = |c(p) – c(q)|2Centered LandmarkCentered Landmark--Distance Coordinates Distance Coordinates and Greedy Routingand Greedy RoutingGreedy strategy: to reach q, do gradient descent on the function d(p, q)L2L1pL5L4L3L0qReference landmarks: L0,…LkT(p) = L0Let s = mean(pL02,…, pLk2)9/29/05 Jie Gao, CSE590-fall05 18Local Landmark Coordinates Local Landmark Coordinates ––No Local No Local MinimumMinimum• 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