9/15/05 Jie Gao CSE590-fall05 1Simulations of the quadrilateralSimulations of the quadrilateral--based based localizationlocalization• Cluster success rate v.s. node degree.• Each plot represents a simulation run.9/15/05 Jie Gao CSE590-fall05 2Random deploymentRandom deployment• Poisson distribution does not look uniform.• ~400 nodes, average degree is about 5.9/15/05 Jie Gao CSE590-fall05 3Random deploymentRandom deployment• Poisson distribution does not look uniform.• ~800 nodes, average degree is about 10.9/15/05 Jie Gao CSE590-fall05 4What you can do & what you can not do What you can do & what you can not do by using anglesby using angles……9/15/05 Jie Gao CSE590-fall05 5Localization by distance informationLocalization by distance information• Flipping causes the trouble, especially for sparse graph. • Intuition: angle information helps to eliminate incorrect flips.9/15/05 Jie Gao CSE590-fall05 6Lemma: By local angles of a unit-disk graph, we can determine all pairs of crossing edges in a valid embedding.What does angle information buy us?What does angle information buy us?If AB crosses CD in UDG, then by the crossing lemma, one of them, say B, has edges to the other three nodes.9/15/05 Jie Gao CSE590-fall05 7Local angle informationLocal angle information• Using local angle information only can not solve the localization problem in the worst case – UDG embedding is NP-hard with only local angle info.• Preliminary experiments show the effectiveness of using angle information in sparse graphs. • More to be explored as to what one can do with angle information.9/15/05 Jie Gao CSE590-fall05 8Local angle info Local angle info UDG embeddingUDG embeddingNPNP--hardhard9/15/05 Jie Gao CSE590-fall05 9ll611l32l32l32l32Consider a unit-disk graph, where the two ‘teeth’ do not cross:Yet a different ambiguityYet a different ambiguity9/15/05 Jie Gao CSE590-fall05 10Two valid embeddingsTwo valid embeddingsConsider a unit-disk graph, where the two ‘teeth’ do not cross:Case 1: Case 2:ll611l32l32l32l32ll611l32l32l32l329/15/05 Jie Gao CSE590-fall05 11UDG embedding with angle info is NPUDG embedding with angle info is NP--hardhard• Reduction from 3SAT problem: represent the 3SAT graph by a UDG.9/15/05 Jie Gao CSE590-fall05 12Consider a unit-disk graph, where the two ‘teeth’ do not cross:Case 1: Case 2:ll611l32l32l32l32ll611l32l32l32l32l21≤ l21≤l32≥l32≥11=x01=x01=x11=xRepresent a binary variable by the ambiguityRepresent a binary variable by the ambiguity9/15/05 Jie Gao CSE590-fall05 13Some basic building blocksSome basic building blocks• A chain of 2l+1 nodes has length at most 2l and at least l.• A “triangle” with fixed aspect ratio between its edges.9/15/05 Jie Gao CSE590-fall05 1411=x01=xCase 1:01=x11=xCase 2:0/1 block 0/1 block ––the true realization by UDGthe true realization by UDGUse triangles to enforce that the teeth are large enough.9/15/05 Jie Gao CSE590-fall05 153SAT instance:3SAT graph:Formulate the 3SAT problem as a graphFormulate the 3SAT problem as a graph9/15/05 Jie Gao CSE590-fall05 163SAT clause:1x2x3x1v,2v,3v:l21≤orl32≥Realize a 3SAT clause by a UDGRealize a 3SAT clause by a UDG9/15/05 Jie Gao CSE590-fall05 17NPNP--hardnesshardness• What we have shown: finding an embedding without incorrect crossings is NP-hard.• Thus, finding a valid embedding is NP-hard.• Lemma: a -approx. embedding has no incorrect crossings. • -approximate embedding is also NP-hard. • The hardness results use degenerate configurations that do not happen often in practice.229/15/05 Jie Gao CSE590-fall05 18A localization algorithm with angle A localization algorithm with angle informationinformation9/15/05 Jie Gao CSE590-fall05 19Embedding by angle informationEmbedding by angle informationWe formulate an optimization problem:Variables: lengths of edges, .• Fix a node as the origin.• All angles are measured against x-axis.Each node’s position (x, y) is a linear function of the variables.9/15/05 Jie Gao CSE590-fall05 20Embedding by angle informationEmbedding by angle informationWe formulate an optimization problem:Variables: lengths of edges, .Constraints:1. Edge length constraint2. Cycle constraint: for a cycle with edges 3. Unit disk graph property.For two nodes u, v without an edge, |uv|>1.Non-convex. So we can’t solve it.9/15/05 Jie Gao CSE590-fall05 21An embedding method by LPAn embedding method by LPWe formulate a linear programming problem:Variables: lengths of edges, .Relax the constraints: use as many linear constraints as possible:1. Edge length constraint2. Cycle constraint: for a cycle with edges9/15/05 Jie Gao CSE590-fall05 22We formulate a linear programming problem:Variables: lengths of edges, .Linear Constraints:3. ∃edges AB, BC, and no AC4. Crossing edge constraint:An embedding method by LPAn embedding method by LPABCα for quasi-UDG9/15/05 Jie Gao CSE590-fall05 23Practical embedding using local anglesPractical embedding using local anglesThe LP doesn’t necessarily produces a valid embedding, but it works well in practice.True Network (600 nodes)Embedding9/15/05 Jie Gao CSE590-fall05 24True Network (600 nodes) EmbeddingThe LP doesn’t necessarily produces a valid embedding, but it works well in practice.Practical embedding using local anglesPractical embedding using local angles9/15/05 Jie Gao CSE590-fall05 25Performance evaluationPerformance evaluationLargest connected component9/15/05 Jie Gao CSE590-fall05 26Noisy angle measurements and QuasiNoisy angle measurements and Quasi--UDGUDG• α=0.8, angle can err 12° from the real value.True Network (225 nodes) Embedding9/15/05 Jie Gao CSE590-fall05 27Further work on using local informationFurther work on using local information• Linear programming is centralized.• We seek a distributed localization algorithm with angle information that works well for sparse graphs.9/15/05 Jie Gao CSE590-fall05 28Algorithm challengesAlgorithm challenges• Noisy measurements– Optimization• Insufficient connectivity, continuous deformation– Rigidity theory– Angle information• Hardness of embedding9/15/05 Jie Gao CSE590-fall05 29System challengesSystem challenges• Physical layer imposes measurement challenges– Multipath, shadowing, sensor imperfections, changes in propagation properties and more• Extensive computation aspects– Many formulations of localization problems, how do you solve theoptimization problem?–