CSE 590 Information Processing in Sensor Networks Fall 2005 Lecture 5 Sep 15 2005 Lecturer Jie Gao 1 Scribe Yue Wang Overview In the last lecture We presented a distributed linear time anchor free algorithm to localize the sensor nodes followed by the NP hardness proof of Unit Disk Graph embedding In this lecture we demonstrate more on hardness results Especially we will introduce a localization algorithm with angle information The basic idea of this algorithm is to use a practical anchor free embedding scheme by solving a linear program In the second part of this lecture we focus on Location based Routing in Sensor Networks such as Face Routing 2 Location and Routing in Sensor Networks by Local Angle Information 2 1 What you can do what you can not do by using angles We start from a simple example to have the intuition why we need angle information Suppose we have had distance information flipping will probably cause different embedding especially for sparse graph like Figure 1 But if we have angle information this probablity will be eliminated Figure 1 Flipping Example Lemma 1 If we know the angles between adjacent edges of a unit disk graph we can determine all pairs of crossing edges in a valid embedding 1 Proof In particular if two edges AB CD intersect with each other there must be a node that is connected with all the other three nodes by the crossing lemma mentioned in the last lecture Suppose B is connected with the other three nodes Then AB CD cross each other if and only if AB is located inside the cone defined CBD and A B are on different sides of the line defined by CD First we can decide if AB is located inside the cone defined by CBD easily by the angle information Further if AB is located inside the cone defined by CBD and A B are on the same side of the line defined by CD then A is inside the triangle BCD See Figure 2 then A is connected to B C D due to plane geometry This situation can be identified since BA must be outside the cone defined by CAD Figure 2 How to determine crossing edges The above lemma implies that we can identify all crossing edges in a valid embedding with local angle information However it is not sufficient for us to decide a valid embedding It turns out that the problem of finding a valid embedding for unit disk graph by using the connectivity and the local angle information is still hard In fact its even NP hard to find a topologically equivalent embedding Definition 2 A topologically equivalent embedding of a graph G with angle information is an embedding of the vertices such that two edges cross in if and only if they cross in a valid embedding The angle between any two adjacent edges uv uw is as specified 2 2 The hardness of UDG embedding with angles Now we prove that UDG embedding with angles is NP hard by a reduction from a 3SAT problem A 3SAT problem consists of a set of Boolean variables and clauses such that each clause is composed of at most 3 literals which are either negated 0 or unnegated 1 2 The 3SAT problem is to find an assignment to the variables such that all the clauses are satisfied A 3SAT instance C can be formulated as a graph GC where vertices are the set of clauses and variables and there is a path connecting a clause with a variable or its negated version if the variable appears in the clause Figure 3 is an example of GC Such a graph can be drawn on a grid in polynomial time Figure 3 Unit Disk Graph Representation for 3SAT problem Next we focus on realizing the graph GC by a unit disk graph with the angle constraint such that there is a topologically equivalent embedding if and only if the corresponding 3SAT problem is satisfied We first present a set of building blocks by using unit disk graphs Spring A spring is a line segment with length between l and 2l It can be realized by a set of 2l 1 nodes placed on a straight line such that there are only edges between adjacent pairs as shown in Figure 4 In particular each edge in a unit disk graph has length at most 1 so a chain of 2l 1 nodes have length at most 2l For 3 adjacent nodes a b c since a cannot communicate with c their distance must be at least 1 away Thus the chain is no shorter than l Figure 4 The realization of a spring by unit disk graph Amplifier An amplifier is a triangle with fixed inner angles Thus the ratio between the 3 edge lengths of the triangle is fixed For a number l we can use an amplifier to get the number l cl for any c 0 An amplifier can be realized by a unit disk graph with pre specified angles between adjacent edges Figure 5 The realization of an amplifier by unit disk graph 0 1 block To represent negated or unnegated literals Consider a unit disk graph where the two teeth do not cross there are only two types of valid embedding Figure 6 In short we construct a concave cycle with one top tooth and one bottom tooth If we dont allow the teeth to overlap there are basically two ways to embed the concave cycle either by putting the top tooth to the left of the bottom tooth or the other way around Figure 6 also points out the length ranges for blue and green segments in different cases Figure 6 Two valid embedding Figure 7 shows a complete 0 1 block by unit disk graph The concave cycle is bounded by AEF GHDCKLIJB the top tooth is the part of the cycle EF GH the bottom tooth is the part of the cycle JILK Suppose the length of AB CD is l we use amplifiers and propagators such that the length of BC DA 11l 6 There are two squares EF GH IJKL inside the rectangle ABCD Both of them have side length 2l 3 The two squares don t have edges in between Thus any embedding without incorrect crossings will have to embed the graph in two ways either by putting the square EF GH to the left of IJKL or the other way around In the first case the length of the path AE is no more than l 2 the 4 length of HD is at least 2l 3 In the second case the length of the path AE is at least 2l 3 and the length of HD is no more than l 2 The segments AE HD BJ KC are springs thus their lengths can be stretched and shrinked by a factor no more than 2 0 1 blocks implement the literals variables in 3SAT problem Then how about the clauses A clause component puts constraints on the input variables In particular it put a total maximum length on …