CSE 590 Information Processing in Sensor Networks Fall 2005Lecture 5 : Sep. 15, 2005Lecturer: Jie Gao Scribe: Yue Wang1 OverviewIn the last lecture, We presented a distributed, linear time, anchor-free algorithm to localizethe sensor nodes, followed by the NP-hardness proof of Unit Disk Graph embedding.In this lecture, we demonstrate m ore on hardness results. Especially, we will introduce alocalization algorithm w ith angle information. The basic idea of this algorithm is to use apractical anchor-free embedd ing scheme by solving a linear program. In the second part ofthis lecture, we focus on Location-based Routing in Sensor Networks su ch as Face Routing.2 Location and Routing in Sensor Networks by Local AngleInformation2.1 What you can do & what you can not do by using angles?We start f rom a simple example to have the intuition why we need angle information.Suppose we have had distance information, flip ping will probably cause different embed ding,especially for sparse graph like Figure 1. But if we have angle information, this probablitywill be eliminated.Figure 1: Flipping ExampleLemma 1. If we know the angles between adjacent edges of a unit disk graph, we candetermine all pairs of crossing edges in a valid embedding.1Proof. In particular, if two edges AB, CD intersect with each other, there must be a no dethat is connected with all the other three nodes by the crossing lemma mentioned in thelast lecture. Suppose B is connected with the other three nodes. Then AB, CD cross eachother if and only if AB is located in side the cone defined ∠CBD < π and A, B are ondifferent sides of the line defined by CD.First we can decide if AB is located inside the cone defined by ∠CBD < π easily by th eangle information. Further, if AB is located inside the cone defined by ∠CBD and A, Bare on the same side of the line defined by CD, then A is inside the triangle BCD. SeeFigure 2, then A is connected to B, C, D due to plane geometry. This s ituation can beidentified since BA must be outside the cone defined by ∠CAD.Figure 2: How to determine crossing edges?The above lemma implies that we can id entify all crossing edges in a valid embedding withlocal angle information. However, it is not sufficient for us to decide a valid embedding. Itturns out that the problem of finding a valid embedding for unit disk graph by usin g theconnectivity and the local angle information is still hard. In fact, its even NP-hard to finda topologically equivalent embedding.Definition 2. A topologically equivalent embedding ε of a graph G with angle informationis an embedding of the vertices such that two edge s cross in ε if and only if they cross in avalid embedding. The angle between any two adjacent edges uv, uw is as spec i fied.2.2 The hardness of UDG embedding with anglesNow we prove that UDG embedding with angles is NP-hard by a reduction from a 3SATproblem. A 3SAT problem consists of a set of Boolean variables and clauses such that eachclause is composed of at most 3 literals, which are either negated (0) or unnegated (1).2The 3SAT problem is to find an assignment to the variables such that all the clauses aresatisfied. A 3SAT instance C can be formulated as a graph GCwhere vertices are the set ofclauses and variables, and there is a path connecting a clause with a variable (or its negatedversion) if the variable appears in the clause. Figure 3 is an example of GC. Such a graphcan be d rawn on a grid in polynomial time.Figure 3: Unit Disk Graph Representation for 3SAT problemNext, we focus on realizing the graph GCby a unit-disk graph with the angle constraintsuch that there is a topologically equivalent embedding if and only if the corresponding3SAT problem is satis fied.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 aset of 2l + 1 nodes placed on a straight line such that there are only edges between adjacentpairs, as shown in Figure 4. In particular, each edge in a unit disk graph has length at most1, so a chain of 2l + 1 nodes have length at most 2l. For 3 adjacent nodes a, b, c, since acannot communicate with c, their distance must be at least 1 away. Thus the chain is noshorter than l.Figure 4: The realization of a spring by unit disk graphAmplifier. An amplifier is a triangle with fixed inner angles. Thus the ratio between the3edge lengths of the triangle is fixed. For a number l we can use an amplifier to get thenumber l′= cl f or any c > 0. An amplifier can be realized by a unit disk graph withpre-specified angles between adjacent edges.Figure 5: The realization of an amplifier by unit disk graph0/1 block. To represent negated or unnegated literals. Consider a unit disk graph, wherethe two ”teeth” do not cross, there are only two types of valid embedding (Figur e 6). Inshort, we construct a concave cycle with one top tooth and one bottom tooth. If we dontallow the teeth to overlap, there are basically two ways to embed the concave cycle, eitherby putting the top tooth to the left of the bottom tooth, or the other way around. Figure6 also points out the length ranges for blue and green segments in different cases.Figure 6: Two valid embeddingFigure 7 shows a complete 0/1 block by unit disk graph. The concave cycle is bounded byAEF GHDCKLIJB, the top tooth is the part of the cycle EF GH, the bottom tooth isthe part of the cycle JILK. Suppose the length of AB = CD is l, we use amplifiers andpropagators 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 squaresdon’t have edges in between. Thus any embedding without incorrect crossings will have toembed the graph in two ways, either by putting the square EF GH to the left of IJKL orthe other way around. I n the first case, the length of the path AE is no more than l/2, the4length 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 n o 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. T hen how about the clauses?A clause component puts constraints on the input variables. In particular, it put a totalmaximum length on the concatenation of springs whose lengths represent the assignmentsof input variables. Figure 8 is an example for a