9/13/05 Jie Gao CSE590-fall05 1Localization of Sensor NetworksLocalization of Sensor NetworksJie GaoComputer Science DepartmentStony Brook University9/13/05 Jie Gao CSE590-fall05 2PapersPapers• D. Moore, J. Leonard, D. Rus, S. Teller, Robust distributed network localization with noisy range measurements, Proc. ACM SenSys 2004.• Anchor-free method.• Rigidity-aware.9/13/05 Jie Gao CSE590-fall05 3TrilaterationTrilaterationwithout noisewithout noise• If three anchors are not on the same line, trilateration with accurate distance measurements gives a unique location.Exercise: verify this.9/13/05 Jie Gao CSE590-fall05 4TrilaterationTrilaterationwith noisewith noise……• With noisy measurements, trilateration can have flip ambiguity.9/13/05 Jie Gao CSE590-fall05 5Use quadrilateralsUse quadrilaterals• Four nodes with fixed pair-wise distances• It is the smallest 3-connected redundantly rigid graph  globally rigid.9/13/05 Jie Gao CSE590-fall05 6Robust quadrilateralsRobust quadrilaterals• If measurement noise is bounded, the quadrilateral has no incorrect flip.Incorrect flip: can’t verify whether C or C’is correct.'2 2 22sin 4sin ( )sin sin2sin(2 )C D CDerrABd dddφ θ φ θ φθ φ−=+ + −=+9/13/05 Jie Gao CSE590-fall05 7Robust quadrilateralsRobust quadrilaterals• If measurement noise is bounded, the quadrilateral has no incorrect flip.Minimize the error by choosing φφφφ=π/2-2θ.2sinABerrd dθ=Robust quadrilateral satisfies2sinerrd bθ<Where b is the shortest side and θis the smallest angle.9/13/05 Jie Gao CSE590-fall05 8ClustersClusters• Robust quads that share three nodes can be merged into clusters.• The cluster is still a 3-connected redundantly rigid graph  globally rigid.• Actually it has 3n-6 edges.9/13/05 Jie Gao CSE590-fall05 9Three phasesThree phases• Cluster localization– Each node x find its local robust quadrilaterals.– Merge them to a robust cluster around x.• (optional) cluster optimization– Refine the nodes’ location inside a cluster.• Cluster transformation– Glue the local quadrilaterals together– Transformation to a global coordinate system.9/13/05 Jie Gao CSE590-fall05 10Algorithm phase I: cluster localizationAlgorithm phase I: cluster localization1. Each node x gets the distance measurements between each pair of 1-hop neighbors.2. Identify the set of robust quadrilaterals.3. Merge the quads if they share 3 nodes.4. Estimate the positions of as many nodes as possible by iterative trilateration.• Note: Local coordinate system rooted at x.9/13/05 Jie Gao CSE590-fall05 11Algorithm phase II: cluster optimizationAlgorithm phase II: cluster optimization• For each cluster around node x, refine the position estimates, for example, by mass-spring relaxation.• Optional.9/13/05 Jie Gao CSE590-fall05 12Algorithm phase III: cluster Algorithm phase III: cluster transformationtransformation• Align neighboring local coordinates systems.• Find the set of nodes in common between two clusters. • Compute the translation, rotation that best align them.9/13/05 Jie Gao CSE590-fall05 13SimulationsSimulations• 183 nodes uniformly inside a building.• Connectivity is only between nodes not obstructed by walls.9/13/05 Jie Gao CSE590-fall05 14SimulationsSimulations• Cluster success rate v.s. node degree.• Each plot represents a simulation run.9/13/05 Jie Gao CSE590-fall05 15Algorithm propertiesAlgorithm properties• Nodes not included in the robust quadrilaterals are not localized.– A wrong location is worse than no location.• Even as noise goes to 0, avg degree ≥ 10 to achieve 100% localization.• Not good for sparse networks. • The avg degree ≅ 6 for best throughput of the network.9/13/05 Jie Gao CSE590-fall05 16DemoDemo• Localize mobile nodes• Show a video clip9/13/05 Jie Gao CSE590-fall05 17ObservationsObservations• Localization algorithm performs poorly when the graph is sparse.• Next, we’ll study in the theoretical worst case what information is sufficient for the localization problem.9/13/05 Jie Gao CSE590-fall05 18Computational hardness of localizationComputational hardness of localization9/13/05 Jie Gao CSE590-fall05 19PapersPapers• [Breu98] H. Breu and D. G. Kirkpatrick. Unit disk graph recognition is NP-hard. Computational Geometry, Theory and Applications, 9(1-2):3-24, 1998. • [Bruck05] J. Bruck, J. Gao and A. Jiang, Localization and Routing in Sensor Networks by Local Angle Information, Proc. of the Sixth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'05), 181-192, May, 2005.9/13/05 Jie Gao CSE590-fall05 20Unit disk graph abstractionUnit disk graph abstraction• Unit disk graph: Given a set of points in the plane, each pair is connected by an edge if their distance is no more than 1.9/13/05 Jie Gao CSE590-fall05 21Quasi unit disk graph modelQuasi unit disk graph model• A better model of the radio coverage range.• Quasi-UDG model.∃ uv if |uv|<α<1; no uv if |uv|>1; unclear otherwise.α 19/13/05 Jie Gao CSE590-fall05 22Localization and embeddingLocalization and embedding• Embedding: Given a graph in the plane, assign coordinates to the vertices such that neighboring nodes are within distance 1 and non-neighboring nodes are of distance α apart.• α=1: UDG embedding.• α<1: 1/α-approximate UDG embedding or α-Quasi UDG embedding.9/13/05 Jie Gao CSE590-fall05 23Input of the embeddingInput of the embedding• Connectivity information: only the combinatorial graph.• Local distance information: (accurate) edge lengths.• Local angle information: (accurate) angle between any two incoming links.• We study whether UDG embedding is NP-hard.9/13/05 Jie Gao CSE590-fall05 24Local measurements do not sufficeLocal measurements do not suffice• With connectivity information: – UDG embedding is NP-hard. – α-Quasi UDG embedding is NP-hard, for α>• With local distance information: – UDG embedding is NP-hard.– If the graph has Ω(n2) edges, then there is a unique solution which can be found by semi-definite programming.• With local angle information: – UDG embedding is NP-hard.– α-Quasi UDG embedding is NP-hard, for α>• With both local distance & angle information:– UDG embedding is in P.2 / 31/ 29/13/05 Jie Gao CSE590-fall05 25Hardness of UDG embeddingHardness of UDG embedding• Reduction from 3-SAT problem.• A 3-SAT instance:• A variable appears at most 3 times; A clause has at most 3 literals.•