Localization of Sensor Networks Jie Gao Computer Science Department Stony Brook University 9 13 05 Jie Gao CSE590 fall05 1 Papers 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 2 Trilateration without 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 3 Trilateration with noise 9 13 05 With noisy measurements trilateration can have flip ambiguity Jie Gao CSE590 fall05 4 Use quadrilaterals 9 13 05 Four nodes with fixed pair wise distances It is the smallest 3 connected redundantly rigid graph globally rigid Jie Gao CSE590 fall05 5 Robust quadrilaterals If measurement noise is bounded the quadrilateral has no incorrect flip Incorrect flip can t verify whether C or C is correct d err d C D d CD 2 d AB 9 13 05 sin 2 4sin 2 sin 2 sin 2sin 2 Jie Gao CSE590 fall05 6 Robust quadrilaterals If measurement noise is bounded the quadrilateral has no incorrect flip Minimize the error by choosing 2 2 d err d AB sin 2 Robust quadrilateral satisfies d err b sin 2 Where b is the shortest side and is the smallest angle 9 13 05 Jie Gao CSE590 fall05 7 Clusters 9 13 05 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 Jie Gao CSE590 fall05 8 Three 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 9 13 05 Glue the local quadrilaterals together Transformation to a global coordinate system Jie Gao CSE590 fall05 9 Algorithm phase I cluster localization 1 2 3 4 9 13 05 Each node x gets the distance measurements between each pair of 1 hop neighbors Identify the set of robust quadrilaterals Merge the quads if they share 3 nodes Estimate the positions of as many nodes as possible by iterative trilateration Note Local coordinate system rooted at x Jie Gao CSE590 fall05 10 Algorithm phase II cluster optimization 9 13 05 For each cluster around node x refine the position estimates for example by massspring relaxation Optional Jie Gao CSE590 fall05 11 Algorithm phase III cluster transformation 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 12 Simulations 9 13 05 183 nodes uniformly inside a building Connectivity is only between nodes not obstructed by walls Jie Gao CSE590 fall05 13 Simulations 9 13 05 Cluster success rate v s node degree Each plot represents a simulation run Jie Gao CSE590 fall05 14 Algorithm 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 15 Demo Localize mobile nodes Show a video clip 9 13 05 Jie Gao CSE590 fall05 16 Observations 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 17 Computational hardness of localization 9 13 05 Jie Gao CSE590 fall05 18 Papers 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 19 Unit disk graph abstraction 9 13 05 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 Jie Gao CSE590 fall05 20 Quasi 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 9 13 05 Jie Gao CSE590 fall05 1 21 Localization 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 22 Input of the embedding 9 13 05 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 Jie Gao CSE590 fall05 23 Local measurements do not suffice With connectivity information UDG embedding is NP hard Quasi UDG embedding is NP hard for With local distance information 2 3 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 1 2 With both local distance angle information 9 13 05 UDG embedding is in P Jie Gao CSE590 fall05 24 Hardness of UDG embedding Reduction from 3 SAT problem A 3 SAT instance 0 1 variable 9 13 05 clause literal A variable appears at most 3 times A clause has at most 3 literals A 3 SAT instance is satisfied if there is an assignment to the variables such that all clauses are 1 Jie Gao CSE590 fall05 25 Graph representation of a 3 SAT instance An edge connects a literal to a clause if the literal appears in that clause clauses variables 9 13 05 Jie Gao CSE590 fall05 26 Find orientations of the edges 9 13 05 Define an edge directed from a clause c to a literal u to be that c chooses u to satisfy it Or u is assigned 1 Jie Gao CSE590 fall05 27 A feasible orientation 1 2 9 13 05 If a literal has incoming edges then its negated version has outgoing edges Each clause has at least 1 outgoing edge every clause is satisfied Jie Gao CSE590 fall05 28 Find orientations of the edges The graph is orientable if and only if the 3SAT instance is satisfiable Now we realize the graph by a unit disk graph s t a valid embedding in 2D gives a valid orientation of the edges 9 13 05 Jie Gao CSE590 fall05 29 A widely used lemma about UDG Crossing lemma if