Simulations of the quadrilateral based localization 9 15 05 Cluster success rate v s node degree Each plot represents a simulation run Jie Gao CSE590 fall05 1 Random deployment Poisson distribution does not look uniform 400 nodes average degree is about 5 9 15 05 Jie Gao CSE590 fall05 2 Random deployment Poisson distribution does not look uniform 800 nodes average degree is about 10 9 15 05 Jie Gao CSE590 fall05 3 What you can do what you can not do by using angles 9 15 05 Jie Gao CSE590 fall05 4 Localization 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 5 What does angle information buy us Lemma By local angles of a unit disk graph we can determine all pairs of crossing edges in a valid embedding 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 6 Local 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 7 NP hard Local angle info 9 15 05 UDG embedding Jie Gao CSE590 fall05 8 Yet a different ambiguity Consider a unit disk graph where the two teeth do not cross l 2l 3 2l 3 2l 3 2l 3 11l 6 9 15 05 Jie Gao CSE590 fall05 9 Two valid embeddings Consider a unit disk graph where the two teeth do not cross Case 1 l 2l 3 2l 3 Case 2 2l 3 2l 3 l 2l 3 11l 6 9 15 05 2l 3 2l 3 2l 3 11l 6 Jie Gao CSE590 fall05 10 UDG embedding with angle info is NPhard Reduction from 3SAT problem represent the 3SAT graph by a UDG 9 15 05 Jie Gao CSE590 fall05 11 Represent a binary variable by the ambiguity Consider a unit disk graph where the two teeth do not cross Case 1 1l 2 Case 2 x1 0 x1 1 l 2l 3 9 15 05 2l 3 x1 0 2l 3 2l 3 2l 3 11l 6 2l 3 l 2l 3 Jie Gao CSE590 fall05 2l 3 1l 2 x1 1 2l 3 11l 6 2l 3 12 Some 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 13 0 1 block the true realization by UDG Case 1 x1 1 x1 0 Case 2 x1 0 x1 1 Use triangles to enforce that the teeth are large enough 9 15 05 Jie Gao CSE590 fall05 14 Formulate the 3SAT problem as a graph 3SAT instance 3SAT graph 9 15 05 Jie Gao CSE590 fall05 15 Realize a 3SAT clause by a UDG 3SAT clause x1 x2 x3 v1 v2 v3 9 15 05 1l 2 or 2 l 3 Jie Gao CSE590 fall05 16 NP hardness What we have shown finding an embedding without incorrect crossings is NP hard Thus finding a valid embedding is NP hard Lemma a 2 approx embedding has no incorrect crossings 2 approximate embedding is also NP hard The hardness results use degenerate configurations that do not happen often in practice 9 15 05 Jie Gao CSE590 fall05 17 A localization algorithm with angle information 9 15 05 Jie Gao CSE590 fall05 18 Embedding by angle information We 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 19 Embedding by angle information We formulate an optimization problem Variables lengths of edges Constraints 1 Edge length constraint 2 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 20 An embedding method by LP We formulate a linear programming problem Variables lengths of edges Relax the constraints use as many linear constraints as possible 1 Edge length constraint 2 Cycle constraint for a cycle with edges 9 15 05 Jie Gao CSE590 fall05 21 An embedding method by LP We formulate a linear programming problem Variables lengths of edges Linear Constraints 3 edges AB BC and no AC C A B for quasi UDG 4 Crossing edge constraint 9 15 05 Jie Gao CSE590 fall05 22 Practical embedding using local angles The LP doesn t necessarily produces a valid embedding but it works well in practice True Network 600 nodes 9 15 05 Jie Gao CSE590 fall05 Embedding 23 Practical embedding using local angles The LP doesn t necessarily produces a valid embedding but it works well in practice True Network 600 nodes 9 15 05 Jie Gao CSE590 fall05 Embedding 24 Performance evaluation Largest connected component 9 15 05 Jie Gao CSE590 fall05 25 Noisy angle measurements and QuasiUDG 0 8 angle can err 12 from the real value True Network 225 nodes 9 15 05 Jie Gao CSE590 fall05 Embedding 26 Further 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 27 Algorithm challenges Noisy measurements Optimization Insufficient connectivity continuous deformation Rigidity theory Angle information Hardness of embedding 9 15 05 Jie Gao CSE590 fall05 28 System challenges 9 15 05 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 the optimization problem How do you solve the problem in a distributed manner under computation and storage constraints Networking and coordination issues Nodes have to collaborate and communicate to solve the problem If you are using it for routing it means you don t have routing support to solve the problem How do you do it System Integration issues How do you build a whole system for localization How do you integrate location services with other applications Different implementation for each setup sensor integration issue Jie Gao CSE590 fall05 29 Location based Routing in Sensor Networks Jie Gao Computer Science Department Stony Brook University 9 15 05 Jie Gao CSE590 fall05 30 Papers 9 15 05 Bose01 P Bose P Morin I Stojmenovic and J Urrutia Routing with guaranteed delivery in ad hoc wireless networks Wireless Networks 7 6 609 616 2001 Karp00 Karp B and Kung H T Greedy Perimeter Stateless Routing for Wireless Networks in MobiCom 2000 Jie Gao CSE590 fall05 31 Routing in ad hoc networks Routing protocols in communication networks obtain route information between pairs of nodes wishing to …