Gruia Calinescu
email: calinescu@iit.edu

Relay placement for two-connectivity ⋆

Keywords: wireless and sensor networks, approximation algorithms, Steiner nodes

Motivated by applications to wireless sensor networks, we study the following problem. We are given a set S of wireless sensor nodes, given as a multiset of points in a normed space. We must place a minimum-size (multi)set Q of wireless relay nodes in the normed space such that the unit-disk graph induced by Q ∪ S is two-connected. The unit-disk graph of a set of points has an edge between two points if their distance is at most 1. Kashyap, Khuller, and Shayman (Infocom 2006) present algorithms for the two variants of the problem: two-edge-connectivity and biconnectivity. For both they prove an approximation ratio of at most 2dMST , where dMST is the maximum degree of a minimum-degree Minimum Spanning Tree in the normed space. In the Euclidean two and three dimensional spaces, dMST = 5, and dMST = 13 respectively. We give a tight analysis of the same algorithms, obtaining approximation ratios of dMST for biconnectivity and 2dMST -1 for two-edge-connectivity respectively.

Introduction

A wireless sensor network is composed of a large number of sensors, which can be densely deployed to monitor the targeted environment. Sensors may have a short transmission range since long transmission consumes more energy, and the sensors normally have limited power. Therefore, network partitions may occur or more sensors must be placed to maintain connectivity. Higher connectivity may be desired to ensure fault-tolerance.

Formally, in the Two-Connected Relay Placement problem, we are given a set S of wireless sensor nodes, given as a multiset of points in a finitedimensional normed space. A normed space is a metric space (X, d), given by a set X and a symmetric function d : X ×X → R + that obeys the triangle inequality: ∀x, y, z ∈ X, d(x, y) ≤ d(x, z) + d(z, y), and the property that d(x, y) = 0 if and only if x = y. As defined in the literature [START_REF] Bryant | Metric Spaces: Iteration and Application[END_REF], a normed space also has the following property (and others that we don't use): ∀x, y ∈ X and ∀α ∈ [0, 1], there exists z ∈ X such that d(x, y) = d(x, z) + d(z, y) and d(x, z) = αd(x, y). In other words, the normed space contains all the Steiner points. Normed spaces of interest to wireless networks are the two and three dimensional Euclidean space, with d being the Euclidean distance (the l 2 norm).

We must place a minimum-size (multi)set Q of wireless relay nodes in the normed space such that the unit-disk graph induced by Q ∪ S is two-connected. The unit-disk graph of a set of points has an edge between two points if their distance is at most 1 (we normalize to 1 the transmission range of the sensors). For a multiset of points P , let U (P ) be the unit-disk graph induced by P . Also, we call two vertices U -adjacent, or U -neighbors, if their distance is at most 1.

Kashyap, Khuller, and Shayman [START_REF] Kashyap | Relay placement for higher order connectivity in wireless sensor networks[END_REF] introduce the two variants of this problem: Two-Edge-Connected Relay Placement (U (S ∪ Q) must be twoedge-connected, that is, have between any two vertices two edge-disjoint paths) and Biconnected Relay Placement (U (S ∪Q) must be biconnected, that is, have between any two vertices two internally vertex-disjoint paths). Two paths are internally vertex-disjoint if they only have the endpoints in common. Biconnectivity also goes by the name of two-vertex-connectivity, or two-connectivity.

Let d MST be the maximum degree of a minimum-degree Minimum Spanning Tree in the normed space.It is known [START_REF] Robins | Low-degree minimum spanning trees[END_REF][START_REF] Martini | Low-degree minimal spanning trees in normed spaces[END_REF] that d MST is the Hadwiger number of the normed space, defined as follows: the maximum size of an independent set in U (N x ), taken over all points x of the space, with N x being the points, other than x, within distance 1 of x. Is is known that d MST = 5 in the Euclidean two-dimensional space, and d MST = 13 in three dimensions. [START_REF] Kashyap | Relay placement for higher order connectivity in wireless sensor networks[END_REF] presents two algorithms, based on the Khuller and Vishkin (Algorithm KV [START_REF] Khuller | Biconnectivity approximation and graph carvings[END_REF]) and the Khuller and Raghavachari [START_REF] Khuller | Improved approximation algorithms for uniform connectivity problems[END_REF] (Algorithm KR) algorithms for Minimum-Weight Spanning Two-Edge-Connected Subgraph, and Minimum-Weight Spanning Biconnected Subgraph, respectively. For these problems, a weighted graph G = (V, E, w) is given as input, and one must select a minimum weight set of edges F such that (V, F ) is two-edge-connected, or biconnected respectively. For Two-Connected Relay Placement, [START_REF] Kashyap | Relay placement for higher order connectivity in wireless sensor networks[END_REF] proves that each of the two algorithms has approximation ratio of at most 2d MST . [START_REF] Kashyap | Relay placement for higher order connectivity in wireless sensor networks[END_REF] also presents simulation results.

We give a tight analysis of the same algorithms, obtaining approximation ratios of d MST for biconnectivity and 2d MST -1 for two-edge-connectivity respectively. Thus, in the two-dimensional Euclidean plane, we get a ratio of 9, instead of 10, for two-edge-connectivity and 5, instead of 10 ( [START_REF] Kashyap | Relay placement for higher order connectivity in wireless sensor networks[END_REF]), for biconnectivity. Assuming that no post-processing removes redundant relay nodes, the ratios given in this paragraph are tight for these algorithms. We are not able to analyze the effect of removing useless beads, a step applicable after both Algorithm KR and Algorithm KV.

For the ratio of 2d MST -1, we use a more careful accounting and look inside Algorithm KV. Due to space limitations, we fully omit presenting this result, as well as several other proofs. For the ratio of d MST for biconnectivity, we look inside Algorithm KR, and prove a property of biconnected graphs that may be of independent interest. Precisely, we claim the following "parsimony" result, new to the best of our knowledge. Let H be a biconnected planar undirected graph, and replace every edge by two anti-parallel directed arcs. Let S be a subset of V (H). Then there exists a set of arc-disjoint paths P i of H, all starting and ending at a vertex of S and without interior vertices from S, such that, if we replace each P i by an arc e i joining the start and end vertex of P i , we obtain a biconnected digraph on vertex set S. This property allows one to "bypass" Steiner vertices ("parsimony") and in some sense eliminate them.

For graphs in general, we prove a "fractional outconnected" variant of the property above, and use it together with Algorithm KR to obtain an approximation ratio of d MST for biconnectivity in arbitrary normed spaces. Structural properties of biconnected Steiner networks were also studied by [START_REF] Hvam | Some structural and geometric properties of two-connected Steiner networks[END_REF][START_REF] Hvam | Bounding component sizes of two-connected Steiner networks[END_REF][START_REF] Winter | Two-connected Steiner networks: structural properties[END_REF][START_REF] Luebke | On the structure and complexity of the 2-connected Steiner network problem in the plane[END_REF], and we use some of their results and techniques for "outconnected parsimony". Using these structural properties, we construct from the optimum solution of an arbitrary Biconnected Relay Placement instance a fractional solution to a certain polytope. This polytope was proposed by Frank and Tardos [START_REF] Frank | An application of submodular flows[END_REF], who proved that it is integral (see also [START_REF] Frank | Connections in Combinatorial Optimization[END_REF]). Thus, there exists a integral solution with cost at most this fractional solution, for any non-negative cost function. We define costs that relate the objective function to an optimum relay solution, and notice that the output of Algorithm KR in a weighted graph we describe later is (almost) derived from an integral polytope optimum solution.

Also in previous work, Wang, Thai, and Du [START_REF] Wang | On the construction of 2-connected virtual backbone in wireless networks[END_REF] and Bredin, Demaine, Hajiaghayi, and Rus [START_REF] Bredin | Deploying sensor networks with guaranteed fault tolerance[END_REF] also gave constant factor algorithms, those of [START_REF] Bredin | Deploying sensor networks with guaranteed fault tolerance[END_REF] achieving a O(k 4 ) approximation for k-connectivity. We remark that in a wireless setting, one only needs k-connectivity between the vertices of S, i.e. k edgedisjoint (or internally vertex-disjoint) paths between any two vertices of S. For k = 1 or k = 2, by eliminating redundancy from any solution, one can see that k-connectivity or k-edge-connectivity between the vertices of S implies kconnectivity or k-edge-connectivity, respectively, of U (S ∪ Q). We only present the argument for 2-connectivity: If U (S ∪ Q) is not biconnected, it has a vertex v such that U ((S ∪ Q) \ {v}) has at least two connected components, and one of these two components contains no vertex of S, since we have two-connectivity between the vertices of S; the removal of this component does not decrease the connectivity between the vertices of S. This argument fails for k > 2. When requiring only k-connectivity between the vertices of S, [START_REF] Bredin | Deploying sensor networks with guaranteed fault tolerance[END_REF] obtains a O(k 3 )approximation ratio, improved to O(k 2 ) by Kamma and Nutov [START_REF] Kamma | Approximating survivable networks with minimum number of Steiner points[END_REF].

MSPT (Minimum Number of Steiner Points Tree with bounded edge length)

is the following related problem: Given S in the plane, find minimum Q such that U (S ∪ Q) is connected. This problem was introduced by Lin and Xue [START_REF] Lin | Steiner tree problem with minimum number of Steiner points and bounded edge-length[END_REF] and proven NP-Hard. They also prove that taking a Euclidean minimum spanning tree, and placing a minimum number of relay nodes on each edge of the tree to connect the endpoints of the edge, achieves an approximation ratio of 5. Mandoiu and Zelikovsky [START_REF] Ion | A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points[END_REF] give a tight analysis of 4 for the MST-based algorithm described above, and generalize to arbitrary normed spaces obtaining a ratio of d MST -1. Chen, Du, Hu, Lin, Wang, and Xue also prove in [START_REF] Chen | Approximation for Steiner trees with minimum number of Steiner points[END_REF] the same ratio of 4 but with a different approach, and present a 3-approximation algorithm. Later, Cheng, Du, Wang, and Xu [START_REF] Cheng | Relay sensor placement in wireless sensor networks[END_REF] improve the running time of the algorithms found in [START_REF] Chen | Approximation for Steiner trees with minimum number of Steiner points[END_REF] while the approximation ratio is unchanged. They also present a randomized algorithm with approximation ratio 2.5 for the same problem. In arbitrary normed spaces, Nutov and Yaroshevitch [START_REF] Nutov | Wireless network design via 3-decompositions[END_REF] obtain a ⌊(d MST + 1)/2⌋ + 1 + ǫapproximation.

Biconnectivity

For any graph G, we use -→ G to represent the bidirected version of G, that is the weighted digraph obtained from G by replacing every edge uv of G with two oppositely oriented arcs uv and vu with the same weight as the edge uv in G. As usual, the weight of a subgraph H of G is defined as w (H) = e∈E(H) w (e) , and the weight of a subdigraph D of -→ G is defined as w (D) = e∈E(D) w (e) .

A spanning subdigraph D of -→ G is said to be an arborescence rooted at some vertex s ∈ V if D contains exactly |V | -1 arcs and there is a path in D from s to any other vertex. In other words, arborescences in directed graphs are directed analogs of spanning trees in undirected graphs.

For any subdigraph D of -→ G , we use D to represent the undirected graph obtained from D by ignoring the orientations of the arcs and then removing multiple edges between any pair of nodes. Call a feasible solution Q of a Two-Connected Relay Placement instance a bead-solution if U (Q ∪ S) contains a two-edge-connected graph (or biconnected, respectively) H where each node of Q has degree exactly two. The Kashyap et. al. [START_REF] Kashyap | Relay placement for higher order connectivity in wireless sensor networks[END_REF] algorithms produces a bead solution -see for example Figure 1, borrowed from the thesis of Kashyap [START_REF] Kashyap | Robust design of wireless networks[END_REF]. In a bead-solution, we may call the relay nodes beads.

As [START_REF] Kashyap | Relay placement for higher order connectivity in wireless sensor networks[END_REF], we use the approximation algorithm of Khuller and Raghavachari [START_REF] Khuller | Improved approximation algorithms for uniform connectivity problems[END_REF], which we refer to as Algorithm KR. We use a variant of Algorithm KR and go deeper in the algorithm to obtain a better approximation ratio.

For x, y ∈ S, define w(x, y) = max(0, ⌈d(x, y)⌉ -1), where d(u, v) denotes the distance from u to v. One can easily verify that w(x, y) is the minimum number of relay nodes required to connect x and y, and that w(x, y) is an increasing function of d(x, y). Note that w is not a metric.

A digraph is said to be k-outconnected (short for k-vertex-outconnected ) from a vertex s if it contains k internally vertex-disjoint paths from s to any other vertex. The min-weight spanning subdigraph of a given weighted digraph which is k-outconnected from a specified vertex, if such a digraph exists, can be found in polynomial time by an algorithm of Frank and Tardos [START_REF] Frank | An application of submodular flows[END_REF]. Gabow [START_REF] Harold | A representation for crossing set families with applications to submodular flow problems[END_REF] has given a faster implementation of the Frank-Tardos algorithm. Suppose that D is a 2-outconnected digraph from a vertex s in which s has exactly two outgoing neighbors x and y. Then the graph V (D) \ {s}, E(D) ∪ {xy} \ {sx, sy} is biconnected [START_REF] Khuller | Improved approximation algorithms for uniform connectivity problems[END_REF]. Algorithm KR constructs a biconnected spanning subgraph of a given weighted graph G as follows.

1. Let xy be an edge of G and s be a vertex not in V . Add to -→ G two arcs sx and sy of weight 0. The resulting digraph is denoted by G + . 2. Find the minimum-weighted spanning subdigraph D of G + which is 2outconnected from s. 3. Output the edge set E(D) ∪ {xy} \ {sx, sy}.

Using as G the complete graph on vertex set S with w as the weight defined above, both us and [START_REF] Kashyap | Relay placement for higher order connectivity in wireless sensor networks[END_REF] use the slightly modified algorithm that tries as xy above all the edges of G, and picks the minimum of all output solutions. Replace each edge of positive weight by new beads (that is, every such edge has its own distinct beads); this is the output. It is known that this modified version is a 2-approximation for Minimum-Weight Spanning Biconnected Subgraph. The approximation ratio of 2d MST obtained by [START_REF] Kashyap | Relay placement for higher order connectivity in wireless sensor networks[END_REF] is based on showing that G has a biconnected subgraph of weight at most d MST • opt , where opt is the value of an optimum relay solution. Our approximation ratio of d MST follows from Theorem 2, proven after preliminary lemmas.

Given a cycle C in an undirected graph H and two distinct vertices u and v on C, a chord-path between u and v is path P in H between u and v that, except for u and v, shares neither vertices nor edges with C. Lemma 1. Let J be a biconnected simple undirected graph and A be a subset of V (J) with |A| > 1. Assume no proper biconnected subgraph J ′ of J exists such that A ⊆ V (J ′ ). Then for every cycle in J, any chord-path has in its interior a vertex of A. Every simple cycle of J contains two vertices of A.

Proof omitted. The property above is proved by Luebke and Pravan [START_REF] Luebke | On the structure and complexity of the 2-connected Steiner network problem in the plane[END_REF] (see also [START_REF] Luebke | k-Connected Steiner Network Problems[END_REF]) with a slightly different hypothesis and their approach works here as well. From here it is immediate to deduce the following: Corollary 1. Let J be a biconnected simple undirected graph and A be a subset of V (J) with |A| > 1. Assume no proper biconnected subgraph J ′ of J exists such that A ⊆ V (J ′ ). Let Q i be a connected component of the subgraph of J induced by V (J) \ A. Let A i be the set of vertices of A adjacent to some vertex in Q i , and let T i be the the subgraph of J with vertex set A i ∪ Q i and containing all the edges of J with at least one endpoint in Q i . Then T i is a tree (called full Steiner component).

We also need a maximum degree condition that is claimed and used in [START_REF] Kashyap | Relay placement for higher order connectivity in wireless sensor networks[END_REF]. The condition is stated in the lemma below whose proof we omit.

Lemma 2. Assume Q is minimal such that U (S ∪ Q) is biconnected. U (S ∪ Q) contains a biconnected subgraph such that every vertex of Q has degree at most d MST .
Now, it will be nice if we could use the "parsimony" propery for planar graphs mentioned in the introduction, and whose proof we omit due to space limitations. However we are unable to prove or disprove this property for non-planar graphs, and in three dimensions we cannot count on planarity. We do have Lemma 3 below, weaker in two respects: the solution is "fractional", and 2-outconnectivity replaces biconnectivity. It will be enough for our purpose.

Given digraph L and X, Y disjoint sets of V (L), define Λ(X, Y ) to be the set of arcs with tail in X and head in Y . Given digraph L and s ∈ V (L), consider the polytope P(L, s) in R |E(L)| (with vectors β having entries β e indexed by arcs of L) defined by the constraints:

0 ≤ β e ≤ 1 ∀e ∈ E(L) (1)
e∈Λ(V \X,X)

β e ≥ 2 ∀∅ = X ⊆ (V (L) \ {s}) (2)
e∈Λ(V \({z}∪X),X)

β e ≥ 1 ∀ z = s ∀ ∅ = X ⊆ (V (L) \ {s, z}) (3)
Using Menger's theorem, one can check that, for an integral vector β valid for P(L, s), the set A of arcs e of E(L) with β e = 1 is such that the digraph (V (L), A) is 2-outconnected from s. Thus one can think of a valid vector β as being "fractional-2-outconnected". Theorem 17.1.14 of [START_REF] Frank | Connections in Combinatorial Optimization[END_REF], (given there with more complicated notation as it solves k-outconnectivity), is given below: Theorem 1. (originally [START_REF] Frank | An application of submodular flows[END_REF]) The system giving P is Total Dual Integral, which implies that for any c : E(L) → N, if the linear program [Minimize e∈E(L) c e β e subject to β ∈ P(L, s)] has a valid optimum, it has an integer-valued optimum.

To use this deep theorem, which is also at the basis of Algorithm KR, we prove our main structural property (the "fractional outconnected parsimony"): Lemma 3. Let J be a biconnected undirected graph, and replace every edge by two anti-parallel directed arcs. Let A be a subset of V (J). Then there exist vertices x, y ∈ A, and there exist positive reals α i and a set of paths P i of J, all starting and ending at a vertex of A and without interior vertices from A, with the following properties. P 0 starts at x and ends at y and α 0 = 1/2. P 1 starts at y and ends at x and α 1 = 1/2. For every arc of e ∈ E(J),

i≥0 | e∈E(Pi) α i ≤ 1
For i ≥ 2, replace each P i by an arc e i joining the start and end vertex of P i , obtaining a directed graph H with vertex set A. Add new vertex s and two arcs sx and sy to H, resulting in digraph H + . Let α sx = α sy = 1, and for i ≥ 2, let α(e i ) = α i . Then the vector α is feasible for P(H + , s).

Proof. Remove edges and vertices not in A from J until it satisfies the conditions of Lemma 1 and Corollary 1. Let T j (j ≥ 0) be the full Steiner components (all our full Steiner components have at least one vertex not in A, and no edge with both endpoints in A) given by this corollary. Do an Eulerian traversal of each bidirected T j (as in Christofides' algorithm). Recall that the vertices of A∩V (T j ) are leafs, and thus each is visited exactly once. If vertices u, v of A appear in this traversal such that, after u, v is the next vertex of A (thus skipping the vertices not in A), have two paths P j and P k one from u to v and one from v to u, both with α i = 1/2. P j follows the traversal, while P k is the reverse of P j . Arbitrarily pick a T 0 and x and y consecutive in the Eulerian traversal of T 0 , and renumber the paths such that P 0 starts at x and ends at y and P 1 starts at y and ends at x. All α values are still 1/2. For two vertices u and v of A adjacent in J, make (one-arc) paths P j and P k , one from u to v and one from v to u, both with α i = 1. One can immediately check that for every arc e ∈ E(J), i≥0 | e∈E(Pi) α i ≤ 1, as indeed, for an arc e of a full Steiner component, e appears in two paths P i : one is a part of the Eulerian traversal, and one is the reverse of a path P in the Eulerian traversal, precisely P that contains the arc antiparallel to e. Incidentally to this proof, we remark that Kashyap et al. [START_REF] Kashyap | Relay placement for higher order connectivity in wireless sensor networks[END_REF] also do this Eulerian traversal (though they don't call it Eulerian, look at their Figure 2), but implicitly set α i = 1 for all i and then the equation above only holds with 2 as the RHS. Here is where we improve the approximation ratio by a factor of two.

For i ≥ 2, replace each P i by an arc e i joining the start and end vertex of P i , obtaining a directed graph H with vertex set A; note that H does not include arcs given by P 0 and P 1 . Add new vertex s and two arcs sx and sy to H, resulting in digraph H + . Let α sx = α sy = 1. It remains to show that the vector α is feasible for P(H + , s). Once again incidentally, we mention that [START_REF] Kashyap | Relay placement for higher order connectivity in wireless sensor networks[END_REF] implicitly obtain the same H + but put α = 1 on all the arcs, while we use 1/2 for all arcs with at least one Steiner endpoint. This is where we improve the ratio -and this also explains why our proof is much longer and complicated.

Constraints (1) are immediate. We proceed to Constraints [START_REF] Bryant | Metric Spaces: Iteration and Application[END_REF]. Pick an arbitrary X ⊆ (V (L) \ {s}). If {x, y} ∈ X, then the two arcs sx and sy with α = 1 satisfy Constraint (2) for X.

Consider now the case x ∈ X and y ∈ X. We have α sx = 1. Going back to the undirected J, there are two internally-disjoint paths P and P ′ from y to x. We claim that one of them must be P 1 , the path inside the full Steiner component T 0 . Indeed, assume otherwise, and let C be the cycle obtained from putting together P and P ′ . If P 1 has edges not C, then it has a subpath that is, in J, a chord-path for C with no internal vertices of A, contradicting Lemma 1. Thus without loss of generality we assume P = P 1 . As P 1 does not give an arc in H + , we concentrate on P ′ . Note that the lack of chord-paths without internal vertices of A also shows that not internal vertex of P ′ appears in T 0 . Let v be the first vertex of X on P ′ (v = x possible), and v ′ be the vertex before v on P ′ (v ′ = y possible). If v ′ ∈ A (note that v ∈ A), then we have a path P j from v ′ to v in the bidirected J with α j = 1, and then in H we have an arc e j from v ′ to v with α j = 1. Then the arcs sx and v ′ v together satisfy Constraint [START_REF] Bryant | Metric Spaces: Iteration and Application[END_REF]. If v ′ ∈ A, then there is a full Steiner component T i that contains v ′ and that has endpoints both in X and outside X (the last vertex of A on P ′ before v is not in X; recall v ∈ X). Note that i = 0. The Eulerian traversal of T i gives two paths, P j and P k , one entering X and one exiting X. Then α j = 1/2, and also there is another path P q , the reversal of P k , that also enters X and has α q = 1/2. Then the arcs sx, e j , and e q together satisfy Constraint (2).

The case x ∈ X and y ∈ X is symmetric. The last case for verifying Constraint (2), considered next, has x ∈ X and y ∈ X; let v ∈ X. Going back to the undirected J, there are two internally-disjoint paths P ′ 1 and P ′ 2 from x to v. Let C be the cycle obtained from putting together P ′ 1 and P ′ 2 . Let v 1 be the first vertex of X on P ′ 1 (v 1 = v possible), and v 2 be the first vertex of X on P ′ 2 (v 2 = v possible). Let v ′ 1 be the vertex before v 1 on P ′ 1 (v ′ 1 = x possible), and let v ′ 2 be the vertex before v 2 on P ′ 2 (v ′ 2 = x possible). If v ′ 1 ∈ A (note that v 1 ∈ A), then we have a path P r1 from v ′ 1 to v 1 in the bidirected J with α r1 = 1, and then in H we have an arc e j1 from v ′ 1 to v 1 with α j1 = 1. Similarly, if v ′ 2 ∈ A (note that v 2 ∈ A), then we have a path P r2 from v ′ 2 to v 2 in the bidirected J with α r2 = 1, and then in H we have an arc e j2 from v ′ 2 to v 2 with

α j2 = 1. If v ′ 1 ∈ A, then there is a full Steiner component T i1 that contains v ′ 1
and that has endpoints both in X and outside X. If v ′ 2 ∈ A, then there is a full Steiner component T i2 that contains v ′ 2 and that has endpoints both in X and outside X. If we have both T i1 and T i2 , we remark that i 1 = i 2 since otherwise we obtain in J a chord-path for C with no internal vertex in A. The Eulerian traversal of T i1 gives two paths, P j1 and P k1 , one entering X and one exiting X. Then α j1 = 1/2, and also there is another path P q1 , the reversal of P k1 , that also enters X and has α q1 = 1/2. The Eulerian traversal of T i2 gives two paths, P j2 and P k2 , one entering X and one exiting X. Then α j2 = 1/2, and also there is another path P q2 , the reversal of P k2 , that also enters X and has α q2 = 1/2. Note that neither of j 1 , q 1 , j 2 , and q 2 could be 0 or 1, as both P 0 and P 1 have their endpoints outside X. Thus H contains either e r1 with α j1 = 1, or both e j1 and e q1 with α j1 = α q1 = 1/2. Also H contains either e r2 with α j2 = 1, or both e j2 and e q2 with α j2 = α q2 = 1/2. In all four subcases, Constraint (2) is satisfied.

We proceed to Constraints (3), which must hold ∀ z = s ∀ ∅ = X ⊆ (V (L) \ {s, z}). If x ∈ X, regardless of y and z, the arc sx with α sx = 1 satisfies the constraint. Similarly, sy satisfies the constraint if y ∈ X. Consider now the case x ∈ X and y ∈ X. The argument is the same whether z = y or z = x or z ∈ {x, y}; we will assume by symmetry x = z, and let v ∈ X. Going back to the undirected J, there are two internally-disjoint paths P ′ 1 and P ′ 2 from x to v; assume by renaming P ′ 1 and P ′ 2 that z is not a vertex of P ′ 1 . Let C be the cycle obtained from putting together P ′ 1 and P ′ 2 . Let v 1 be the first vertex of X on Assume Q is minimal such that U (Q ∪S) is biconnected, and |S| ≥ 2. Choose a biconnected spanning subgraph K of U (Q∪S) as in Lemma 2. Apply Lemma 3 with K as J, and S as A, obtaining vertices x, y ∈ S, paths (P i ) i≥0 , nonnegative numbers α i , arcs e i (for i ≥ 2) giving digraph H, and then digraph H + after adding vertex s and arcs sx and sy. Use these x, y as the two vertices of G required by the theorem.

For arcs e of H + , define c e = 0 if e = sx or e = sy, and c e = l ′ K (P i ) if e = e i is obtained from P i (for i ≥ 2). Consider the linear program LP: Minimize e∈E(H + ) c e β e subject to β ∈ P(H + , s), and note that α from Lemma 3 gives a feasible solution. Apply Theorem 1 to get and integral solution for LP, and therefore a digraph D, subgraph of H + , 2-outconnected from s. It remains to check the weight condition. Note that for any edge e of G with endpoints u and v, and for any path P from u to v in K, w(e) ≤ l ′ K (P ), as beads can be placed on the vertices of P . Also, every arc e i of D of non-zero weight comes from a path P i (with i ≥ 2) of K. Thus (using Theorem 1 for the second inequality):

w(D) = e∈D w(e) ≤ i≥2 : ei∈D l ′ K (P i ) ≤ i≥2 α i l ′ K (P i ).
Write e ⋄ v if edge e is adjacent to vertex v, and next(P, v, e) if on path P , edge e is used to leave v. We have:

w(D) + w(xy) ≤ i≥0 α i l ′ K (P i ) = i≥0 α i v∈ Pi 1 = v∈Q i≥0 | v∈ Pi α i = v∈Q e | e⋄v i≥0 | next(Pi,v,e) α i ≤ v∈Q e | e⋄v 1 = v∈Q d K (v) ≤ |Q| • d MST
where the first inequality follows from the previous equation and the facts that P 0 is a path of K that starts at x and ends at y with α 0 = 1/2, and that P 1 is a path of K that starts at y and ends at x with α 1 = 1/2. The second inequality comes from Lemma 3, and the last inequality from Lemma 2. ⊓ ⊔ The analysis given above is tight. Precisely, in the two-dimensional Euclidean plane, the ratio of the biconnectivity algorithm above is indeed 5o(1), assuming all ties are broken in worst-case manner, and no post-processing removes redundant relay nodes. First look at the example in Figure 2. It has two sea stars (one relay node, the star's center, U -adjacent to five U -independent nodes of S, called tentacles) with u and v in the center. In general, we are going to use q spread-out sea stars, and we connect their tentacles as those of u, v are in Figure 2 -this can always be done maintaining planarity to create a biconnected graph. Precisely, plane curves connect tentacles of different sea stars such that no two points on distinct curves are at distance at most 1. Each curve is subdivided such that only consecutive nodes on the curve are U -adjacent; the nodes used for subdivision are put in S. Done carefully, we end up with m paths, each giving a x y v u Fig. 2. The nodes of S are black disks. Optimum uses the relay nodes u and v. If we start Algorithm KR with x and y as in the figure, ten edges of weight one would be chosen by the algorithm (precisely, the arcs passing "around" each of u and v, each arc needing a bead node). The two arborescences from Theorem 3 are represented, except for edges sx and sy, by dotted and solid arcs, respectively. One could get only nine beads by starting with x, y not U -adjacent. However, in a larger example, one or two beads saved still results in a ratio of five.

connected component of U (S) (one for each curve), such that m = 5q/2o(q). Optimum is q (and let q → ∞). We use the following theorem of Whitty [START_REF] Whitty | Vertex-disjoint paths and edge-disjoint branchings in directed graphs[END_REF]: Theorem 3. [START_REF] Whitty | Vertex-disjoint paths and edge-disjoint branchings in directed graphs[END_REF] Suppose that, given a directed graph D = (V, A) and a specified vertex s ∈ V , there are two internally vertex-disjoint paths from s to any other vertex of D. Then D has two arc-disjoint outgoing arborescences rooted at s such that for any vertex v ∈ Vs the two paths to s from v uniquely determined by the arborescences are internally vertex-disjoint.

Wherever we start with x and y in Algorithm KR, each of the two arborescences from the theorem above needs m -1 arcs of weight 1 to enter each of the m paths/connected components of U (S), except those containing x or y. Thus Algorithm KR produces a solution of weight at least 2(m -1) = 5qo(q).

A similar (but non-planar) construction can be made for the three dimensional Euclidean space, using far-apart sea stars with 13 tentacles each.

Fig. 1 .

 1 Fig. 1. Left, an optimum solution for two-edge-connectivity. The nodes of S are black disks, and the relay nodes are empty circles. Right, an optimum bead solution.

⋆ Research supported in part by NSF grant NeTS-0916743.

P ′

1 (v 1 = v possible), and v 2 be the first vertex of X on P ′ 2 (v 2 = v possible). Let v ′ 1 be the vertex before v 1 on P ′ 1 (v ′ 1 = x possible), and let v ′ 2 be the vertex before v 2 on P ′ 2 (v ′ 2 = x or v ′ 2 = z possible). If v ′ 1 ∈ A (note that v 1 ∈ A), then we have a path P r1 from v ′ 1 to v 1 in the bidirected J with α r1 = 1, and then in H we have an arc

Assume from now on that v ′ 1 ∈ A; therefore there is a full Steiner component T i1 that contains v ′ 1 and that has endpoints both in X and outside X. Consider the case when z is an interior vertex of P ′ 2 ; then we cannot have that T i1 has z as a vertex, since otherwise, in J, we get a chord-path of C with no internal vertex in A. The Eulerian traversal of T i1 gives two paths, P j1 and P k1 , one entering X and one exiting X. Then α j1 = 1/2, and also there is another path P q1 , the reversal of P k1 , that also enters X and has α q1 = 1/2. None of P j1 and P k1 and P q1 start or end at z, since z is not a vertex of T i1 . Also, {j 1 , q 1 } ∩ {0, 1} = ∅, since both P j1 and P q1 have one end in X, and P 0 and P 1 have endpoints x and y which are not in X. The two arcs of H: e j1 and e q1 satisfy Constraint [START_REF] Chen | Approximation for Steiner trees with minimum number of Steiner points[END_REF].

From now on, z is not an interior vertex of

, then we have a path P r2 from v ′ 2 to v 2 in the bidirected J with α r2 = 1, and then in H we have an arc

We are left with the case v ′ 1 ∈ A, z not on P ′ 2 , and v ′ 2 ∈ A; recall that z is not on P ′ 1 . We have the full Steiner component T i1 as above, and the full Steiner component T i2 that contains v ′ 2 and that has endpoints in both X and outside X. Note that i 1 = i 2 since otherwise we obtain, in J, a chord-path for C with no internal vertex in A.

Let v ′′ 1 be the last vertex of A before v 1 on P 1 ; then v ′′ 1 ∈ V (H + ) \ (X ∪ {z}). Consider the Eulerian traversal of T i1 ; it passes through each vertex of A∩V (T i1 ) exactly once (as these are the leafs of T i1 ). Then, in this traversal, we can get from v ′′ 1 to v 1 , or from v 1 to v ′′ 1 , without passing through z (which can be a leaf of T i1 ). Thus, we have that either a path P j1 of this traversal goes from V (H + ) \ (X ∪ {z}) to X, or goes from X to V (H + ) \ (X ∪ {z}). In the second case, P q1 , the reverse of P j1 goes from V (H + ) \ (X ∪ {z}) to X. Let P k1 be either P j1 or P q1 , such that it goes from V (H + ) \ (X ∪ {z}) to X. P k1 cannot be P 0 or P 1 , since it ends in X, and P 0 and P 1 end in x or y, both being outside X. Thus e k1 exists in H + ; also α k1 = 1/2. We repeat the argument for T i2 , to get another arc e k2 ∈ E(H + ) going from V (H + ) \ (X ∪ {z}) to X, and with α k2 = 1/2. These two arcs of H: e k1 and e k2 satisfy Constraint [START_REF] Chen | Approximation for Steiner trees with minimum number of Steiner points[END_REF].

In all cases, Constraint (3) is satisfied. ⊓ ⊔ Proof. Define, for graph L , d L (v) to be the degree of vertex v in L. For path P in L, define P to be the set of vertices in its interior, and define l ′ L (P ) = | P |.


Yi-Yin Chang

Cheng-Yu Lin

Ling-Jyh Chen

A Two-Layer Approach for Energy Efficiency in Mobile Location Sensing Applications

Keywords: energy efficiency, GPS tracking, location sensing

Mobile location sensing applications (MLSAs) represent an emerging genre of applications that exploit Global Positioning System (GPS) technology and facilitate location-based services. The design of MLSAs must incorporate a tradeoff between information accuracy and energy efficiency because GPS technology and data communications are energy expensive and unaffordable for most MLSA platforms, which are battery-powered and therefore resource-constrained. In this study, we propose a two-layer solution to address the above issue. The solution comprises an Event-based GPS Tracking (EBT) scheme and an Inter-Frame Coding (IFC) scheme for energy efficiency on the MLSA GPS tracking and data communication layers respectively. Using a comprehensive set of evaluations, as well as realistic MLSA traces, we evaluate the proposed solution in terms of power saving, location accuracy, and the data compression ratio. The results demonstrate that our solution can achieve better energy efficiency while preserving good location accuracy in all test cases. Moreover, the scheme is simple, effective, and generalizable to other mobile location sensing applications.

Introduction

With the advances in wireless communications and GPS technology, mobile location sensing applications (MLSAs) are rapidly permeating every part of our living environments. Unlike conventional Internet and mobile applications, MLSAs exploit Global Positioning System (GPS) technology and facilitate the provision of emerging locationbased services (LBS). This new genre has already spawned a wide range of applications, such as location-based social networks [START_REF] Kirkpatrick | Why We Check In: The Reasons People Use Location-Based Social Networks[END_REF][START_REF] Miluzzo | Sensing meets mobile social networks: The design, implementation and evaluation of the CenceMe applications[END_REF], mobile urban sensing systems [START_REF] Eisenman | BikeNet: A mobile sensing system for cyclist experience mapping[END_REF], and moving object tracking systems [START_REF] Huang | Cenwits: A sensor-based loosely coupled search and rescue system using witnesses[END_REF][START_REF] Zhang | Hardware design experiences in Ze-braNet[END_REF].

The use of GPS technology in MLSAs raises a new technical and 'green' challenge, namely, excessive power consumption due to GPS localization and stream data communications. There are two reasons for this phenomenon. First, an MLSA requires timely and accurate location information, so it favors keeping GPS receivers in the ON mode continuously. However, GPS receivers are known to be power-hungry; thus, keeping them "always-on" is unaffordable for MLSAs because the lifespan of the latter is constrained by the battery capacity of the associated mobile device. Second, an MLSA generates a substantial amount of continuous data, including the trajectory of the moving object (i.e., the location information as a function of time [START_REF] Sistla | Modeling and Querying Moving Objects[END_REF]) and other contextual information (e.g., sensory data and event logs); thus, data communications are costly in monetary terms as well as power consumption.

Several approaches have been proposed to solve the above issues. Generally, existing solutions to the first problem (i.e., reducing the energy required for MLSA GPS tracking) can be divided into two categories: static duty-cycle (SDC) approaches (e.g., [START_REF] Eisenman | BikeNet: A mobile sensing system for cyclist experience mapping[END_REF][START_REF] Zhang | Hardware design experiences in Ze-braNet[END_REF]), and dynamic duty-cycle (DDC) approaches (e.g., [START_REF] Constandache | Towards Mobile Phone Localization without War-Driving[END_REF][START_REF] Jurdak | Adaptive GPS duty cycling and radio ranging for energy-efficient localization[END_REF][START_REF] Kim | SensLoc: sensing everyday places and paths using less energy[END_REF][START_REF] Kjargaard | Energy-efficient Trajectory Tracking for Mobile Devices[END_REF][START_REF] Kjargaard | Entracked: energy-efficient robust position tracking for mobile devices[END_REF][START_REF] Paek | Energy-efficient rate-adaptive GPS-based positioning for smartphones[END_REF][START_REF] Sundaresan | Event-driven adaptive duty-cycling in sensor networks[END_REF][START_REF] Youssef | GAC: Energy-Efficient Hybrid GPS-Accelerometer-Compass GSM Localization[END_REF][START_REF] Zhuang | Improving energy efficiency of location sensing on smartphones[END_REF]). The former turn GPS receivers ON and OFF at regular intervals, while the latter adjust GPS duty cycles based on analytical models or events triggered by additional sensors. Unfortunately, these approaches are not feasible for MLSAs because 1) SDC approaches operate in a "blind" manner, without considering the context of moving objects; and 2) DDC approaches require a lookup table of pre-learned radio patterns, which is not practical for generic MLSA scenarios.

Solutions to the second problem (i.e., reducing the energy required for MLSA data communications) are either byte-level compression approaches (e.g., [START_REF] Salomon | Data Compression: The Complete Reference[END_REF]) or spatiotemporal compression approaches (e.g., [START_REF] Gudmundsson | Compressing spatiotemporal trajectories[END_REF][START_REF] Meratnia | Spatiotemporal Compression Techniques for Moving Point Objects[END_REF][START_REF] Potamias | Sampling Trajectory Streams with Spatiotemporal Criteria[END_REF]). These approaches are infeasible for MLSAs because 1) byte-level compression methods compress MLSA data without considering its intrinsic properties, so the compressed data cannot be processed directly without decompression into its raw form; and 2) spatio-temporal compression methods are based on the lossy concept, i.e., they achieve a good compression ratio at the expense of information loss.

Clearly, a comprehensive solution that can address the challenge without loss of functionality for MLSAs is highly desirable. An ideal solution should meet three criteria: 1) it should be self-adaptive with minimal prerequisites for extra knowledge (e.g., pre-learned radio patterns) and sensors; 2) it should provide lossless compression; and 3) it should be simple, lightweight, and portable to off-the-shelf phones.

In this study, we introduce a two-layer approach to improve the energy efficiency and preserve the location accuracy of MLSAs. Specifically, we propose an event-based GPS tracking approach that operates on the GPS tracking layer and triggers a GPS receiver to lock when either the receiver has been in the OFF mode longer than a threshold or a turn event is detected by the built-in 3-axis accelerometer (i.e., G-sensor) of the latest smart phones. We also propose an Inter-Fame Coding (IFC) algorithm that exploits spatio-temporal localities on the data communication layer to compress trajectory-based MLSA data. As a result, the compressed data can be used for spatiotemporal operations in MLSAs without decompression. The algorithm can also be implemented easily in conjunction with unequal erasure protection (UEP) and data prioritization schemes for operations in lossy or resource-constrained environments.

Using realistic bus trajectory data collected from the TPE-CMS system [START_REF] Lin | A comfort measuring system for public transportation systems using participatory phone sensing[END_REF], we evaluate the proposed approach in terms of location accuracy, power saving, and the compression ratio. The results demonstrate that the solution can achieve a balance between location accuracy and power saving in GPS tracking, and the IFC approach yields a good compression ratio of about 50%. Finally, the proposed approach is simple, effective, and ready for immediate real-world deployment.

The remainder of this paper is organized as follows. Section 2 contains a review of existing GPS tracking and trajectory compression schemes for MLSAs. In Section 3, we present the proposed Event-based GPS Tracking (EBT) approach for MLSA GPS tracking; and in Section 4, we describe the proposed Inter-Frame Coding (IFC) approach for MLSA data compression. We discuss the evaluation results for the EBT and IFC schemes in Sections 5, and then summarize our conclusions in Section 6.

Related Work

One of the most challenging aspects of GPS technology is its power consumption, which is expensive and renders it unaffordable for emerging mobile and battery-powered platforms, such as smart phones and wireless sensor networks. To prolong the lifespan of built-in GPS systems, several static duty-cycle (SDC) schemes reduce the power consumption of GPSs by turning them ON and OFF periodically. For instance, the BikeNet [START_REF] Eisenman | BikeNet: A mobile sensing system for cyclist experience mapping[END_REF] and ZebraNet [START_REF] Zhang | Hardware design experiences in Ze-braNet[END_REF] projects use SDC-based approaches and turn their GPS receivers ON and OFF according to a fixed duty cycle. BikeNet turns the GPS receivers ON for one minute every 8 minutes, while ZebraNet turns them ON for 150 seconds every 1,000 seconds. In contrast, dynamic duty-cycle (DDC) approaches adjust the GPS duty cycle based on sophisticated models [START_REF] Jurdak | Adaptive GPS duty cycling and radio ranging for energy-efficient localization[END_REF][START_REF] Paek | Energy-efficient rate-adaptive GPS-based positioning for smartphones[END_REF][START_REF] Sundaresan | Event-driven adaptive duty-cycling in sensor networks[END_REF] or events triggered by add-on sensors. For example, they adjust duty cycles according to whether users are in outdoor/indoor environments by using radio signal recognition [START_REF] Kim | SensLoc: sensing everyday places and paths using less energy[END_REF], or whether the tracked objects have traveled a certain distance by using accelerometers, gyros, and digital compasses [START_REF] Constandache | Towards Mobile Phone Localization without War-Driving[END_REF][START_REF] Kjargaard | Energy-efficient Trajectory Tracking for Mobile Devices[END_REF][START_REF] Kjargaard | Entracked: energy-efficient robust position tracking for mobile devices[END_REF][START_REF] Youssef | GAC: Energy-Efficient Hybrid GPS-Accelerometer-Compass GSM Localization[END_REF][START_REF] Zhuang | Improving energy efficiency of location sensing on smartphones[END_REF]).

On the other hand, to improve the scalability of moving object databases, several trajectory compression algorithms exploit the spatial and temporal localities in trajectory data [START_REF] Gudmundsson | Compressing spatiotemporal trajectories[END_REF][START_REF] Meratnia | Spatiotemporal Compression Techniques for Moving Point Objects[END_REF][START_REF] Potamias | Sampling Trajectory Streams with Spatiotemporal Criteria[END_REF]. For instance, Meratnia et al. proposed the time ratio algorithm [START_REF] Meratnia | Spatiotemporal Compression Techniques for Moving Point Objects[END_REF], which discards a data point on a trajectory if that point can be interpolated/extrapolated by any two adjacent data points on the trajectory within an error threshold. Gudmundsson et al. [START_REF] Gudmundsson | Compressing spatiotemporal trajectories[END_REF] developed a fast implementation of the well-known Douglas-Peucker line simplification algorithm [START_REF] Douglas | Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[END_REF], and reduced the computational complexity from O(n 2 ) to O(nlog k n). Finally, Potamias et al. [START_REF] Potamias | Sampling Trajectory Streams with Spatiotemporal Criteria[END_REF] proposed a threshold-guided technique, called STTrace, which compresses trajectories based on the target compression rate and the Synchronous Euclidean Distance (SED) within each trajectory. The main drawback of these approaches is that they use a lossy approach to compress trajectories. Thus, information loss is inevitable, and applications built on top of the approaches are dependent on the accuracy of the compressed trajectory data.

Green GPS Tracking for MLSA

In this section, we discuss the proposed event-based GPS tracking approach, called EBT, for energy conservation in MLSAs. EBT comprises two components: hybrid duty-cycle scheduling and trajectory reconstruction. The first component utilizes a hybrid approach that combines the conventional static duty-cycle (SDC) approach and an event-based dynamic duty-cycle (DDC) approach, which uses a 3-axis accelerometer (G-sensor) to detect turn events and trigger GPS receivers to lock accordingly. Then, the second component uses the sensory data of the G-sensor to estimate the location of the moving object and reconstruct the trajectory. The flowchart of the EBT approach is shown in Figure 1. Let T DC be the length of the duty cycle in the embedded SDC, and let T Of f be the elapsed time since the last successful GPS lock event. We describe the two components in detail in the following subsections.

Hybrid Duty-Cycle Scheduling

The proposed hybrid duty-cycle scheduling approach is based on the intuition that, to conserve energy, it is better to keep GPS receivers in the OFF mode, unless the location accuracy of the MLSAs is threatened. The location accuracy of GPS tracking deteriorates in two situations: 1) the GPS receiver has been in the OFF mode longer than a pre-defined threshold period; and 2) there has been a significant change in the movement pattern of the object that the GPS receiver is tracking. As shown in Figure 1, for the first situation, we define a threshold time T DC 1 , and employ an SDC-like approach that triggers a GPS receiver to lock whenever T Of f (i.e., the elapsed time since the last successful GPS lock event) reaches T DC . To address the second situation, we introduce the Turn Detection Algorithm (TDA), which detects 1 The value of TDC depends on the location accuracy required by the MLSA. 'significant changes' (i.e., changes in direction) in the movement pattern and triggers GPS receivers to lock accordingly 2 .

Specifically, TDA uses the Poisson Sampling approach to detect turn events at a rate of λ, i.e., the 'inter-sample' times follow an exponential distribution with a mean of 1/λ. For each sample, TDA utilizes the G-sensor to read the acceleration on three axes. Then, using a sliding window of size w, it calculates the standard deviation of the acceleration in the direction that is orthogonal to gravity and the trajectory's orientation 3 .

Let S be the set of the standard deviations stored in the history, let s i be the i-th standard deviation in ascending order in S, and let α be the target power saving ratio. We set S thresh = s j , where j = α × |S| . Then, TDA identifies a turn event whenever the standard deviation in a sliding window is greater than the latest S thresh value.

There are three ways to implement S in TDA:

1. Infinite-Queue Approach (IQA): S contains all standard deviations calculated in the previous sliding windows. The size of S is infinite. 2. FIFO-Queue Approach (FQA): The standard deviations calculated in the previous L sliding windows are stored in S in a First-In-First-Out (FIFO) manner. 3. Duo-Queue Approach (DQA): Similar to FQA, the size of S is limited to L, but DQA divides S into two subsets: one is used to store standard deviations that are smaller than or equal to S thresh ; and the other is used to store the standard deviations that are greater than the latest value of S thresh when they are calculated. The sizes of the subsets are αL and L -αL respectively. We use the FIFO approaches to implement both subsets.

Note that to achieve the target power saving ratio α, it is advisable to increase the sampling frequency (i.e., a large λ value) and keep as many of the standard deviations calculated in the previous windows as possible (i.e., using the IQA scheme). However, the higher the sampling rate, the greater will be the computational resource required by TDA, and that may impact other applications on a smart phone. With regard to the suitability of the three approaches, IQA is not feasible because it is impossible to have an infinite queue in practice. DQA is more suitable than FQA, as it is better able to preserve the distribution of the standard deviations calculated in the previous windows. Consequently, it yields a better approximation of S thresh .

Location Estimation

As shown in Figure 1, if no turn events are detected and the time since the last successful GPS lock event is less than T DC , EBT enters the Location Estimation phase to approximate its current location without using GPS. In this study, we integrate EBT with the displacement measurement algorithm (DMA) [START_REF] Chen | Displacement Measurement Algorithm Using Handheld Device with Accelerometer[END_REF], which uses accelerometers to measure the displacement of a moving object. Then, we implement the location estimation mechanism by combining the displacement measurement results and the location of the last successful GPS lock event.

DMA is comprised of six steps: interpolation, average filtering, de-shimmying, offset compensation, first integration, and second integration. We omit the interpolation step because we assume the granularity of the G-sensor's data is very fine. Moreover, to improve the integration of DMA with EBT and simplify the implementation, we set the window size used in the average filtering step equal to the sliding window size of TDA (i.e., w). The window size used in the de-shimmying step is 2w.

Green Data Communications in MLSAs

Like the excessive power consumption of GPS tracking, the data communication overhead is a challenging issue in MLSAs. This is because MLSA data runs as a continuous stream, which is expensive in terms of bandwidth utilization, monetary expense, and power consumption. In this section, we propose a trajectory compression algorithm, called Inter-Frame Coding (IFC), to reduce the energy consumption of MLSAs in the data communication layer. The rationale behind IFC is that (1) spatial and temporal localities are common on a trajectory; and (2) the spatial and temporal offsets between any two contiguous data points on a trajectory are limited to the object's mobility and the trajectory's sampling rate. Thus, IFC exploits the spatial and temporal localities of contiguous spatio-temporal data to reduce the redundancy in the raw spatio-temporal data stream.

There are two types of data points in the IFC scheme: I frames, which contain the index data points of a trajectory; and O frames, which contain the offsets of the subsequent data points that correspond to the I frames, as shown in Figure 2. Let I u i denote the i-th I frame that represents the v-th spatio-temporal data point of the u-th trajectory (i.e., T u v ); and let O u i,j denote the j-th O frame associated with I u i , i.e., the offset of T u v+j to T u v . Specifically, I u i = (i, u, x(u, i), y(u, i), z(u, i)), where i is the sequence number of I u i ; u is the trajectory identifier; and x(u, i), y(u, i), and z(u, i) are the longitude, latitude, and timestamp of T u v respectively. In addition, O u i,j =(i, ∆x(u, i, j), ∆y(u, i, j), ∆z(u, i, j)), where i is the sequence number of the I frame associated with O u i,j ; and ∆x(u, i, j), ∆y(u, i, j), and ∆z(u, i, j) represent, respectively, the longitude, latitude, and time offsets of T u v+j to T u v . Generally, an I frame is associated with n O frames. The value of n, which is a tunable system parameter, depends on several factors, such as the sampling rate of the trajectory data, the speed of the moving object, and the data compression ratio required by the application (which we discuss in detail in the next subsection). However, when the offset values exceed the range allowed in an O frame 4 , a new I frame must be created, even though the number of O frames associated with the old I frame is less than n.

We assume that 1) the maximum possible speed of a moving object along the lines of latitude and longitude is V max meters per second; 2) the trajectory data is collected at a rate of s data points per second; 3) the maximum value of the latitude and longitude offsets is M AX dist ; and 4) the maximum value of the time offset is M AX time . Since we know that V max × n s ≤ M AX dist and n s ≤ M AX time , we can obtain the upper bound of n as follows:

n ≤ M in M AX dist × s V max , M AX time × s . (1)
In addition, we define the compression ratio Ψ as the ratio of the data using the IFC scheme over the data without using the scheme, i.e., the raw data. Since the size of an I frame is Size I, the size of an O frame is Size O, and each I frame is associated with n O frames at most, we can obtain the value of Ψ by

Ψ = Size I + n × Size O Size I × (n + 1) = Size O Size I + Size I -Size O Size I × (n + 1) . ( 2
)
Thus, the higher the value of n, the smaller will be the compression ratio Ψ . The upper bound of the compression ratio is Size O Size I when n approaches infinity. However, we find that a very large n value is infeasible in the IFC scheme. There are two reasons for this phenomenon. First, when n is very large, the O frames are used to store most spatio-temporal data points. This is computationally expensive for spatio-temporal applications because (i) each data query in the application layer involves two separate database queries; and (ii), restoring the O frames to the raw data format requires a tremendous amount of computation. Moreover, if n is very large, the loss of a single I frame may result in the loss of the original data points because the I frames are crucial for restoring the original data points of the O frames.

The second reason is that, the larger the value of n, the greater the likelihood that an I frame will have less than n O frames in the database. In other words, when n is large, the subsequent n points of an I frame are more likely to have oversized offset values that can not be represented by O frames. As a result, a new I frame must be created, even though the number of O frames associated with the former I frame is less than n. Hence, the IFC scheme cannot achieve the theoretical compression ratio when n is large.

In this section, we evaluate the proposed solution for MLSA GPS tracking on a real dataset. The data was collected by volunteers during 50 trips on the TPE-CMS bus system [START_REF] Lin | A comfort measuring system for public transportation systems using participatory phone sensing[END_REF] using the VProbe application [START_REF]VProbe: sensing and probing your driving experience[END_REF] on their smart phones (including Acer Liquid, HTC Magic, Samsung Nexus S, and Sony Ericsson XPERIA X10 phones). Specifically, the sensory data includes GPS trajectories, digital compass directions, and 3-axis accelerations. The sampling rate for the data is 20Hz. We use the dataset as the ground truth and perform trace-based simulations. Unless otherwise specified, the maximum time allowed between two GPS locks (i.e., T DC ) is 60 seconds. The Poisson sampling rate used in TDA (i.e., λ) is 1 Hz; the target power saving ratio (i.e., α) is 0.95; the queue length in the three queue management schemes (i.e., L) is 1000; and the size of the sliding window (w) is 50 samples. All the results are based on the average performance of 10 simulation runs. We discuss the evaluation results in the following subsections.

Evaluation of Turn Event Detection

First, we use the realistic dataset to evaluate the feasibility of using digital compasses to detect turn events in MLSAs. The dataset contains trajectories of 86,607 seconds in total, and there are 235 turn events that are marked manually as ground truth. The digital compass-based approach reported 795 turn events. Among them, 115 turn events are detected correctly (i.e., the accuracy of turn event detection is 115/235=48.94%), and 680 events are false-alarms (i.e., the false positive ratio is 680/795=85.53%). The reason is that digital compasses are very sensitive to environmental factors, especially when they are placed in a vehicle with diverse magnetic fields. Thus, digital compasses may not be feasible for detecting turn events in general MLSA scenarios.

Next, we evaluate the proposed TDA scheme in terms of the hit rate of turn detection, with different values of α under EBT with the IQA, FQA, and DQA queue management schemes. The results are shown in Figure 3. We observe that EBT's hit rate is more than 98% in all test cases when the TDA scheme is used (i.e., α < 1). In contrast, the hit rate is approximately 71% when α = 1 (i.e., under the SDC scheme). There are no significant differences between the hit rates of the IQA, FQA and DQA schemes.

Evaluation of Event-based Tracking

We evaluate EBT's performance in terms of its power saving ratio and location accuracy in MLSA GPS tracking. Using the dataset of 50 bus trips, we compare the power saving ratio (α ) achieved with different target power saving ratios (α) under EBT with the three queue management schemes. From the results, shown in Figure 4, we observe that α increases with α, and the IQA and DQA schemes perform better than FQA. The reason is that FQA implements the FIFO queue with a size limit of L = 1, 000, and the selected threshold S thresh is not usually representative of the true distribution of turn events; hence, there is a large number of false alarms (i.e., false positive turn events). Meanwhile, although the values of α achieved by DQA are slightly lower than those Fig. 6. Comparison of the power saving ratio (α ) achieved with different sampling rates (λ) and target power saving ratios (α) under EBT with the DQA scheme under IQA in all test cases, we consider that the DQA scheme is a feasible solution because its power saving performance is comparable to that of the IQA scheme, and it is a practical solution that does not depend on an infinite queue.

In Figure 5, we compare the location estimation errors with different α values under EBT using the DQA scheme. The distance error increases with α because the loss of location accuracy is the price paid (i.e., the trade-off) for reduced energy consumption. The results demonstrate that the implementation of the TDA scheme improves the location accuracy significantly in EBT. The average location estimation error is about 120m when the TDA scheme is not applied (i.e., α = 0). By contrast, it is about 80m (i.e., a 33% improvement) with the TDA scheme and α = 0.95. We observe that the distribution of location estimation errors is skewed towards instances with large values. Even so, TDA's overall performance is considered acceptable because the median error rate is less than 30m when α = 0.95, and less than 10m when α < 0.85. We also evaluate the impact of MLSA sampling rates (λ) on the power saving performance and turn detection performance of GPS tracking in MLSAs. The results, shown in Figure 6, demonstrate that EBT achieves a good power saving ratio that is slightly lower than the target ratio when the value of λ is between 0.1 Hz and 10 Hz, which is the range of typical sampling rates in MLSAs. Moreover, the results in Figure 7 show that EBT can detect nearly all the turn events under different λ values.

Evaluation of Inter Frame Coding

Finally, we evaluate the proposed MLSA data communication solution, i.e., the IFC scheme, in terms of the data compression ratio. We implement the IFC scheme using the open-source PostgreSQL database (version 8.4.4) [24] and the PostGIS spatial database extension (version 1.5.1) [25]. For I frame data in the IFC scheme, we use the Point data type (16 bytes) to store the location information (x and y), the Timestamp data type (8 bytes) to store time information (z), and the Integer data type (4 bytes) to store sequence numbers (i) and trajectory identifiers (u). For the O frames, we use the Integer data type to store the I frame sequence number (i); and the Short Integer data type (2 bytes) to store the longitude, latitude, and time offsets ∆x, ∆y, and ∆z. Therefore, the size of an I frame (Size I) is 32 bytes, and that of an O frame (Size O) is 10 bytes. Note that the distance offsets (∆x and ∆y) are measured in meters 5 , and the time offset (∆z) is measured in seconds.

In Figure 8, we compare the theoretical compression ratio (cf. Equation 2) and the ratio achieved in the realistic trajectory dataset with different n values under the IFC scheme. We observe that the two curves are nearly overlapped completely, and the compression ratio is lower than 0.5 after the value of n becomes larger than 4. Moreover, using the same dataset, we compare IFC with five trajectory compression schemes: OPW [START_REF] Meratnia | Spatiotemporal Compression Techniques for Moving Point Objects[END_REF], TDTR [START_REF] Meratnia | Spatiotemporal Compression Techniques for Moving Point Objects[END_REF], STTrace [START_REF] Potamias | Sampling Trajectory Streams with Spatiotemporal Criteria[END_REF], Uniform Sample [START_REF] Potamias | Sampling Trajectory Streams with Spatiotemporal Criteria[END_REF], and Douglas-Peucker (DP) [START_REF] Douglas | Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[END_REF]. For each scheme, we use an exhaustive set of configurations 6 , and observe their Pareto frontiers [START_REF] Fudenberg | Game Theory[END_REF] between the average distance error and the compression ratio, as shown in Figure 9.

Figure 9 shows that the IFC scheme outperforms the other schemes significantly and it always achieves the "Pareto optimum" [START_REF] Fudenberg | Game Theory[END_REF]. In other words, there are no instances on the other schemes' frontiers that have smaller distance errors and lower compression ratios than the instances on IFC's frontier. The results also demonstrate that the IFC scheme is lossless during MLSA data compression, as its distance error is zero despite the different compression ratios achieved. In contrast, the other schemes are lossy during data compression. The lower the compression ratio, the larger will be the distance error.

Conclusion

We propose a two-layer approach to reduce the energy consumption of emerging mobile location sensing applications (MLSAs). Specifically, on the MLSA GPS tracking layer, our event-based GPS tracking approach (EBT) combines the strengths of static and dynamic duty-cycle scheduling approaches; and on the MLSA data communication layer, our Inter-Frame Coding (IFC) approach exploits the spatio-temporal localities in MLSA data compression. We evaluate the proposed schemes via a comprehensive set of simulations based on a real dataset. The results demonstrate that the EBT scheme can achieve a good power saving ratio while maintaining the location estimation error within an acceptable range. In addition, the results show that, compared to existing schemes, the IFC scheme is lossless and effective in MLSA data compression. The solution proposed in this study is simple and effective, and it is generalizable to other mobile location sensing applications.

Fig. 1 .

 1 Fig. 1. The flowchart of the event-based GPS tracking (EBT) approach

Fig. 2 .

 2 Fig. 2. An example of I frames and O frames in the IFC scheme.

Fig. 3 .Fig. 4 .Fig. 5 .

 345 Fig. 3. Comparison of turn detection hit rates with different target power saving ratios (α) under EBT with the three queue management schemes

Fig. 7 .Fig. 8 .

 78 Fig.7. Comparison of the turn detection hit rates with different sampling rates (λ) and target power saving ratios (α) under EBT and the DQA scheme

Fig. 9 .

 9 Fig.9. Comparison of the results of the IFC, OPW, TDTR, STTrace, Uniform Sample, and DP schemes in a two-objective space (i.e., the average distance error and the compression ratio) under various configurations

We do not use digital compasses to detect turn events because they are very sensitive to magnetic fields. We present a detailed evaluation in the following sections.

[START_REF] Eisenman | BikeNet: A mobile sensing system for cyclist experience mapping[END_REF] For simplicity, in the experiment, we place the smart phone on the vehicle carefully, such that the Y-axis of the G-sensor is parallel to the vehicle's orientation, and the Z-axis of the G-sensor is parallel to gravity. Therefore, the calculation of the standard deviation in TDA only counts the accelerations on the X-axis of the G-sensor.

For instance, the offset values may exceed the range allowed in an O frame if, in the data stream, a long period containing data points is missed due to transmission errors or GPS errors.

For simplicity, we approximate the distance between two data points along lines of latitude and longitude by one meter every 10 -5 degrees, which is valid at sea level on the Equator.

For instance, we vary the number of O frames per I frame (i.e., n) from 1 to 10 in the IFC scheme; the sampling gap from 1 to 10 in the Uniform Sample scheme; the target compression ratio from 10% to 90% in the STTrace scheme; and the error threshold from 10m to 90m in the OPW, TDTR, and DP schemes.

This research was supported in part by the National Science Council of Taiwan under Grants: NSC 100-2631-S-003-006, NSC 100-2219-E-001-001, and NSC 100-2219-E-001-002.


Syed Hasan

Sergey Gorinsky
email: sergey.gorinsky@imdea.org

Obscure Giants: Detecting the Provider-Free ASes

Keywords: Internet economics, transit, provider-free ASes

Internet routing depends on economic relationships between ASes (Autonomous Systems). Despite extensive prior research of these relationships, their characterization remains imprecise. In this paper, we focus on provider-free ASes that reach the entire Internet without paying anyone for the traffic delivery. While the ground truth about PFS (set of the provider-free ASes) lies outside the public domain, we use trustworthy non-verifiable sources as a baseline for result validation. Straightforward extraction of PFS from public datasets of inter-AS economic relationships yields poor results. Then, we develop a more sophisticated Temporal Cone (TC) algorithm that relies on topological statistics (customer cones of ASes) and exploits the temporal diversity of the datasets. Our evaluation shows that the TC algorithm infers PFS from the same public datasets with a significantly higher accuracy. We also assess the sensitivity of the TC algorithm to its parameters.

Introduction

Economic relationships between ASes (Autonomous Systems) are relevant for Internet routing. For example, it is financially more attractive for an AS to route traffic through a peering link than a transit connection of the AS to its provider. Despite a trend towards flattening [START_REF] Dhamdhere | The Internet is Flat: Modeling the Transition from a Transit Hierarchy to a Peering Mesh[END_REF], the Internet routing ecosystem is essentially hierarchical [START_REF] Dhamdhere | The Internet is Flat: Modeling the Transition from a Transit Hierarchy to a Peering Mesh[END_REF][START_REF] Gao | On Inferring Autonomous System Relationships in the Internet[END_REF][START_REF] Gregori | BGP and Inter-AS Economic Relationships[END_REF][START_REF] Ma | On Cooperative Settlement Between Content, Transit and Eyeball Internet Service Providers[END_REF]. A vast majority of ASes are relatively small and route traffic either as customers of transit links or by peering with local ASes of a similar stature. There exists only a handful of provider-free ASes that reach the entire Internet without paying anyone for the traffic delivery. While it is more common to call a provider-free AS a tier-1 network, our paper uses the former term because prior attempts to redefine AS tiers make network tiering an ambiguous notion. The set of the provider-free ASes, to which we refer as PFS, contains only large networks. Nevertheless, the real difference between them and another large network can be subtle. For example, if a network is not a provider-free AS because it pays for less than 1% of its inter-domain traffic, the lack of the provider-free status can be obscure to outsiders, especially if the disqualifying payments are for a paid peering relationship which is subject to a non-disclosure agreement. Due to the general reluctance of ASes to disclose their business agreements, researchers infer the inter-AS economic relationships from measurements of routing and forwarding. Such inferences are imperfect, as this paper demonstrates for provider-free ASes.

Our interest in PFS arises due to a number of reasons. First, the provider-free ASes clearly play a key role as the transit core of the Internet ecosystem. By delivering a significant portion of Internet traffic, PFS is highly relevant to the overall resilience of the Internet to accidental failures and intentional disruptions. In particular, economic disputes between provider-free ASes can endanger the universal connectivity of Internet users. Second, while humans prefer to think in discrete categories, designation of an autonomous system as provider-free can have tangible marketplace implications. Third, some algorithms for inter-AS relationship inference use PFS as an input [START_REF] Gregori | BGP and Inter-AS Economic Relationships[END_REF][START_REF] Xia | On the Evaluation of AS Relationship Inferences[END_REF] and hence need to know PFS accurately.

This paper contributes an algorithm that detects PFS from public datasets of inter-AS economic relationships. We show that straightforward extraction of PFS from the public datasets yields poor results. Our alternative algorithm utilizes topological statistics (customer cones of ASes) and temporal dataset diversity. The more sophisticated algorithm infers PFS with a significantly higher accuracy. Although related studies deal with the more general problem of inter-AS relationship inference, our algorithm succeeds by focusing on the more specific problem of PFS detection. Another group of related work redefines tier-1 networks according to a new classification of Internet ASes, e.g., based on their graph-theoretic topological properties. In contrast, our study detects providerfree ASes in accordance to the traditional tier-1 definition. The two main contributions of our paper are in deriving:

-PFS insights from mostly trustworthy non-verifiable sources via careful removal of occasional spurious answers; -TC (Temporal Cone) algorithm that detects PFS based on public datasets of inter-AS economic relationships. The derived TC algorithm is useful because it enables continued detection of PFS even if the trustworthy non-verifiable sources stop supplying data about PFS in the future.

We structure the rest of the paper as follows. Section 2 comments on related work. Section 3 reports PFS insights from the non-verifiable sources. Section 4 describes the public datasets in our study. Section 5 considers a straightforward PFS detection method. After analyzing the failures of this straightforward method, section 6 develops the more sophisticated TC algorithm. Section 7 evaluates the TC algorithm. Section 8 concludes the paper by summing up its contributions.

Related work

The TC algorithm derives PFS from inter-AS economic relationships. Since the pioneering work by Gao [START_REF] Gao | On Inferring Autonomous System Relationships in the Internet[END_REF], the problem of inter-AS relationship inference has attracted a variety of other heuristic solutions [START_REF] Dimitropoulos | AS Relationships: Inference and Validation[END_REF][START_REF] Ge | Hierarchical Structure of the Logical Internet Graph[END_REF][START_REF] Gregori | BGP and Inter-AS Economic Relationships[END_REF][START_REF] Subramanian | Characterizing the Internet Hierarchy from Multiple Vantage Points[END_REF][START_REF] Xia | On the Evaluation of AS Relationship Inferences[END_REF]. While our paper is the first to focus on detecting PFS, previous works used PFS as an input to their inter-AS relationship inference algorithms [START_REF] Gregori | BGP and Inter-AS Economic Relationships[END_REF][START_REF] Xia | On the Evaluation of AS Relationship Inferences[END_REF]. PFS also served as a basis for studies of backbone networks and resilience of routing to failures [START_REF] Mahajan | Uncovering Performance Differences among Backbone ISPs with Netdiff[END_REF][START_REF] Wu | Internet Routing Resilience to Failures: Analysis and Implications[END_REF].

Derivation of PFS from public inter-AS relationship datasets is challenging because missing or misclassified links make the datasets noisy. Addressing the problem of hidden links [START_REF] Chen | Where the Sidewalk Ends: Extending the Internet AS Graph using Traceroutes from P2P users[END_REF][START_REF] Oliveira | The (in)Completeness of the Observed Internet AS-level Structure[END_REF][START_REF] Zhang | Collecting the Internet AS-level Topology[END_REF] has a potential for making the results of our TC algorithm even better.

While the TC algorithm exploits the temporal diversity of the inter-AS relationship datasets, prior works explored the temporal dimension for studying other problems such as network graph evolution [START_REF] Dhamdhere | Ten Years in the Evolution of the Internet Ecosystem[END_REF][START_REF] Leskovec | Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations[END_REF].

The work by Subramanian et al. [START_REF] Subramanian | Characterizing the Internet Hierarchy from Multiple Vantage Points[END_REF] is the closest in spirit to ours. Among its other contributions, that paper proposed a new hierarchical taxonomy for Internet ASes and developed an algorithm that uses AS customer counts to detect the top-tier ASes of the newly proposed hierarchy. While similar in spirit, our work is very different in its specific goals and methods. In particular, we strive to detect PFS in accordance to the traditional definition of provider-free ASes.

Non-verifiable sources

Although the obscure inter-AS economic relationships do not reveal the ground truth about PFS, a number of non-verifiable sources offer insights into this set. Wikipedia maintains an article about provider-free ASes Except for few incidents in 6/2009 and 10/2009 when spurious modifications disappeared shortly after being made, PFS preserved this 10-member composition until the end of 2009. In 2010 and 2011, Wikipedia continued the trend of the PFS expansion and typically recognized Tinet as the 11th member of the PFS, e.g., in the 10/2/2011 revision [START_REF]Tier 1 Network[END_REF]:

W 2 = {AT&T, Global Crossing, Level 3, NTT, Qwest, Sprint, Verizon, Savvis, Telia, Tata, Tinet}.
Whereas Wikipedia is an online encyclopedia that anyone may edit, some short-lived revisions of this particular article certainly distorted the reality [21]. Nevertheless, experts think that on the whole the Wikipedia perspective reflects PFS accurately [START_REF] Gregori | BGP and Inter-AS Economic Relationships[END_REF]. The data from Renesys and Hurricane Electric also support the Wikipedia perspective [START_REF] Hasan | Obscure Giants: Detecting the Provider-free ASes[END_REF]. Based on the above considerations, the primary PFS answers from the non-verifiable sources in our paper are PFS insights in section 3 came from the non-verifiable sources that did not disclose their data and methods. The rest of our study explores datasets from two public sources: UCLA (University of California, Los Angeles) [18] and CAIDA (Cooperative Association for Internet Data Analysis) [4]. The datasets from both public sources characterize the economic relationships between Internet ASes. UCLA classifies inter-AS links as transit or peering. CAIDA uses an additional category for sibling relationships: a sibling link connects two ASes belonging to the same Internet service provider.

While the UCLA datasets are available starting from 10/2008, CAIDA reports its datasets infrequently for 2009 and only twice after 2009. During the development of our PFS detection algorithm in sections 5 and 6, we focus on the 12 months of 2009 to have similar time series for the two sources. Figure 1 depicts the inter-AS economic relationships in the UCLA and CAIDA datasets during 2009. When evaluating our TC algorithm in section 7, we utilize the UCLA datasets for all 32 months of their availability from 10/2008 to 5/2011. Our technical report [START_REF] Hasan | Obscure Giants: Detecting the Provider-free ASes[END_REF] elaborates on the UCLA and CAIDA datasets as well as inference methodology for the datasets.

Straightforward inference

Given a dataset of inter-AS economic relationships, one might hope to infer PFS using the following straightforward method: compose PFS from all such ASes in the dataset that have no transit provider. We apply this straightforward method to the UCLA and CAIDA datasets of section 4. Table 1 sums up the generally disappointing results for all 12 months of 2009. Throughout the year, the straightforward method includes into its PFS up to 23 non-W 1 ASes and excludes up to all 10 ASes of W 1 . For the UCLA and CAIDA datasets from 6/2009 (when the numbers of transit links for the two sources remain most stable and close to each other), PFS contains respectively 17 and 27 ASes, with respectively 9 and 7 of these ASes belonging to W 1 .

For the UCLA 6/2009 dataset, the straightforward method excludes Tata from PFS because NTT and GIT Telecom (a Cypriot AS) are transit providers for this missing member of W 1 according to the dataset. Among the 8 non-W 1 members of PFS, Sunkist Growers (a not-for-profit cooperative of citrus growers in California and Arizona), Open Peering Initiative (a public peering 6) 26 ( 6) 29 ( 7) 30 ( 7) 27 ( 7) 28 ( 7) 29 ( 7) 25 ( 6) 26 ( 6) 27 ( 6) 27 ( 6)

Table 1: PFS size according to the straightforward method for the UCLA and CAIDA datasets and (in parentheses) number of ASes from W1 in this PFS.

IXP in Amsterdam), and Siemens seem highly unlikely to be genuine providerfree ASes. These 3 ASes do have providers in the CAIDA dataset from the same month.

For the CAIDA 6/2009 dataset, the straightforward method omits NTT, Savvis, and Tata from PFS because these 3 members of W 1 have transit providers. Specifically, NTT has 3 providers: Verizon, Telia, and Easynet. Savvis has 5 providers: Telia, Tata, Tinet, XO, and Deutsche Telekom. Although Tata is a transit provider for Savvis, the straightforward method does not recognize Tata as a provider-free AS either: Tata appears as a customer of NTT, Telia, and Tinet. On the other hand, PFS of the straightforward method includes 20 non-W 1 ASes such as the University of Texas System, NASA, and New Zealand Research Network, which do have providers in the UCLA 6/2009 dataset.

The most common source of errors for the straightforward method is link misclassification in the UCLA and CAIDA datasets. We also applied the straightforward method to another dataset inferred with Gao's algorithm [10], and the respective results suffer from the link misclassification as well.

TC algorithm

Section 5 demonstrates that the straightforward inference yields disappointing PFS results with respect to both false positives and false negatives. Two factors undermine the straightforward method. First, while the UCLA and CAIDA datasets do not classify the inter-AS links fully and correctly, even a single error in the input dataset can mislead the straightforward method. The method can exclude a genuine provider-free AS (e.g., Tata in the UCLA 6/2009 dataset) from PFS because the dataset mistakenly reports a provider for this AS. Also, the method can wrongly include an AS (e.g., Sunkist Growers) into PFS because the dataset misses the transit link between this AS and its provider. Second, the straightforward method implicitly assumes that having no provider implies the ability to reach the entire Internet. In reality, some ASes in the Internet ecosystem do not strive for the universal reachability. For example, the main goal of an IXP (Internet eXchange Point) [START_REF] Augustin | IXPs: Mapped? In[END_REF][START_REF] Dhamdhere | The Internet is Flat: Modeling the Transition from a Transit Hierarchy to a Peering Mesh[END_REF] is to serve as a peering infrastructure that enables other ASes to exchange their local traffic. The straightforward method can incorrectly classify an IXP (e.g., Open Peering Initiative) as a providerfree AS.

Thus, we develop a more sophisticated TC (Temporal Cone) algorithm for detecting PFS. Sections 6.1, 6.2, and 6.3 discuss the three important components of our algorithm: its use of topological statistics to deal with the noisy data, setting the PFS size, and exploiting the temporal diversity of the datasets to improve the accuracy of the PFS detection further. Topological statistics represent a promising basis for accurate PFS detection because of their potential resilience to individual errors caused by the link misclassification.

While the datasets of inferred inter-AS relationships clearly contain numerous errors, our approach relies on the premise that the datasets are also rich in correct information and that looking at the datasets from a right perspective can reveal PFS accurately.

After examining a number of options [START_REF] Hasan | Obscure Giants: Detecting the Provider-free ASes[END_REF], we choose the customer cone as the topological parameter for the TC algorithm: the customer cone of an AS includes the AS itself as well as all direct and indirect customers of the AS, i.e., every customer reachable from the AS through a sequence of provider-tocustomer transit links [START_REF] Dimitropoulos | AS Relationships: Inference and Validation[END_REF]. We expect the customer cones of the provider-free ASes to be among the largest because the customer cone of an AS is strictly larger than the customer cone of any of its customers. This expectation is certainly a heuristic (in principle, a provider-free AS can have a smaller customer cone than a network that lies outside this customer cone and has a provider) but our results confirm its effectiveness. Due to multihoming [START_REF] Akella | A Measurement-based Analysis of Multihoming[END_REF] which is common throughout the Internet ecosystem, the customer cones of two ASes can overlap. We compute the customer cone of each AS using a recursive algorithm that takes the overlaps of the customer cones into account.

To illustrate the potential of the customer cone for PFS detection, let us revisit the false negatives and false positives of the straightforward method for the 6/2009 datasets in section 5. For the UCLA 6/2009 dataset, the straightforward method computes the PFS that incorrectly excludes Tata and wrongly includes Sunkist Growers, Open Peering Initiative, and Siemens. The customer cones of Tata, Sunkist Growers, Open Peering Initiative, and Siemens are 26014, 69, 75, and 8 ASes respectively. While the customer cone of 26014 ASes is the 13th largest among all networks in the dataset, the customer-cone perspective leaves Tata as a plausible candidate for PFS. On the other hand, the small customer cones of Sunkist Growers, Open Peering Initiative, and Siemens clearly suggest that these 3 networks are not provider-free ASes. Similarly, for the CAIDA 6/2009 dataset, the 3 false negatives of the straightforward method are NTT, Savvis, and Tata which have very large customer cones of 24473, 23769, and 23788 ASes respectively. The University of Texas System, NASA, and New Zealand Research Network are false positives of the straightforward method, and their small corresponding customer cones of 19, 11, and 232 ASes strongly indicate that these 3 networks are not provider-free. The above examples confirm that the customer-cone metric is more robust to the link misclassification than the simple inspection of the link types as with the straightforward method. Among alternative topological parameters that we considered as a basis for the TC algorithm, the customer count of an AS refers to the number of direct customers of the AS and is easier to compute than the customer cone. Also, while the PFS members peer with each other, another potential approach to detecting PFS is to search for close-knit peering communities, e.g., to examine the number of peering links of each AS. However, our preliminary analyses for peering-based, customer-count, and other alternative parameters did not yield encouraging results [START_REF] Hasan | Obscure Giants: Detecting the Provider-free ASes[END_REF]. Consequently, the customer cone serves as the topological basis for our PFS detection algorithm.

In the distributions of the customer cones in the UCLA and CAIDA datasets, only a tiny fraction of all ASes have a large customer cone [START_REF] Hasan | Obscure Giants: Detecting the Provider-free ASes[END_REF]. Table 2 zooms in on the tail of the UCLA 6/2009 distribution. The tail covers set W 1 quite tightly: all 10 members of W 1 appear among the top 13 ASes ranked by the customer cone; this is an improvement over the straightforward method which includes only 9 members of W 1 into its 17-member PFS for 6/2009.

Figure 2(a) tracks the UCLA customer-cone ranks of all ASes in W 1 throughout 2009. The ranks remain close to the top 10 with few exceptions such as three dramatic dips for Tata. While figure 2(a) corroborates the promising potential of the customer-cone statistics for PFS detection, the results also suggest that our algorithm needs additional features for overcoming the noise in the datasets.

Figure 2(b) depicts the CAIDA customer-cone ranks of all ASes in W 1 during 2009. In agreement with table 1, the customer-cone results in figures 2(a) and 2(b) imply that the UCLA datasets are less noisy and thus more suitable for PFS detection than the CAIDA datasets. To detect PFS, the TC algorithm has to size this set. Whereas the Internet is growing, our hypothesis is that the set of provider-free ASes scales up proportionally with the overall population of Internet ASes. More specifically, we set size S m of PFS at time m to:

PFS size

S m = k • P m (1)
where P m represents the total number of Internet ASes at time m, and k is a fixed factor.

To validate the hypothesis and select the value of k, we explore how PFS evolved from 10/2008 to 5/2011 according to the Wikipedia perspective. During this time interval, the article has been revised on 113 days, and multiple revisions on a single day were common. Figure 3 depicts the PFS size according to Wikipedia, with short-lived spikes representing spurious revisions. For every day throughout the 32-month interval, figure 3 also plots the PFS size as per equation 1 with the value of k set to 0.00032 using UCLA data, which corresponds to 1 in about 3000 Internet ASes being provider-free.

Whereas the amount of the available data is too limited to recommend strongly the specific value of k or confidently state the proportionality of PFS to the overall population of Internet ASes, our evaluation suggests that equation 1 offers a reasonable approximation for the PFS size [START_REF] Hasan | Obscure Giants: Detecting the Provider-free ASes[END_REF].

Temporal dimension

With the PFS size selected, the algorithm still needs to identify the ASes of the set. We utilize the temporal dimension of the datasets to tackle the noise remaining in the customer-cone statistics. Our intuition is that the membership of an AS in PFS is relatively stable. While a new AS can join PFS and subsequently lose the provider-free status again, such transitions are infrequent, caused by rare mergers/acquisitions and guarded against by long-term business contracts.

Therefore, to decide whether an AS is provider-free for month m, our algorithm looks w months back and ahead from month m and includes the AS into PFS for month m only if the AS belongs to the set according to the customercone ranks for at least n out of these 2w + 1 months. For an input with M months in the time series, our algorithm outputs PFS for each month except for the first w and last w months, i.e., the algorithm computes PFS for the M -2w middle months. While one-year contracts between ASes are common, we recommend w = 6 months and n = 5 months as default values for the w and n parameters of the algorithm, i.e., inclusion of an AS into PFS requires from the customercone ranks to endorse the AS for at least 5 out of 13 months. These settings enable our algorithm to recognize a genuine one-year PFS membership in spite of multiple months of erroneous disqualifications by the customer-cone ranks. These settings also allow the algorithm to exclude a non-providerfree AS from PFS despite multiple months of mistaken customercone endorsements. In section 7, we study sensitivity of the TC algorithm to the w and n parameters and show that w = 6 months and n = 5 months are reasonable settings. We refer to the developed PFS detection algorithm as TC (Temporal Cone) and present it in detail in figure 4.

Evaluation

According to sections 4 through 6, the datasets from UCLA are available for more months and less noisy than the CAIDA datasets. To evaluate the developed TC algorithm, section 7.1 relies on the UCLA datasets for the 32 months from 10/2008 to 5/2011 and (following the recommendations from the previous section) sets the PFS sizing factor, lookback/lookahead window, and PFS membership threshold to k = 0.00032, w = 6 months, and n = 5 months respectively. In section 7.2, we assess the parameter sensitivity of the TC algorithm.

TC results

During its first iterative stage, the TC algorithm determines the AS customercone ranks and PFS sizes for all M = 32 months. As shown in figure 3 With w = 6 months to look back and ahead, the TC algorithm executes its second stage to compute PFS for the M -2w = 20 middle months from 4/2009 to 11/2010. Among the 9 months of 2009 (when the PFS size is 10 ASes), PFS perfectly matches W 1 for one month, omits only Qwest for another month, and excludes only Tata for the other 7 months. For all 11 months of 2010 (when the PFS size is equal to 11 ASes), PFS matches W 2 exactly. Table 3 sums up the performance of the TC algorithm. A quick comparison of these results with table 1 reveals that the TC algorithm detects PFS significantly better than the straightforward method.

While the TC algorithm agrees with the Wikipedia perspective on the PFS size, the false positives of the algorithm are equal in number to its false negatives. Hence, we further quantify the performance of the TC algorithm with the following 2 metrics:

-Accuracy A m of the PFS detection for month m is the fraction of ASes in the computed PFS that are provider-free during month m according to Wikipedia; -Average accuracy of the PFS detection is the average of monthly accuracies A m over all the M -2w middle months in the input time series.

For the TC results in table 3, the accuracy of the PFS detection is 90% for 8 months and perfect 100% for the other 12 months. Thus, the corresponding average accuracy of the PFS detection is 96%.

Parameter sensitivity

Whereas our TC algorithm relies on parameters w and n, this section studies the sensitivity of the algorithm performance to these 2 parameters for the UCLA datasets. Throughout this study, we use k = 0.00032 as discussed in section 6.2.

Figure 5(a) shows that with w = 6 months, the average accuracy of the TC algorithm declines steadily and dramatically as PFS membership threshold n grows beyond 5 months. When n decreases from 5 months to 1 month, the average accuracy declines slightly. Hence, for w = 6 months, the average accuracy attains its peak of 96% when n is set to 5 months. Figure 5(a) also plots the average accuracy for w = 2 months and w = 8 months, with the profile of the accuracy sensitivity to n remaining qualitatively the same. The average accuracy is stable for smaller values of the PFS membership threshold but decreases consistently and significantly after n grows beyond a tipping point. the maximum of 96% when w is set to 6 months. w = 7 months and w = 8 months yield similarly high values of the average accuracy. Based on the above observations, we conclude that w = 6 months and n = 5 months constitute reasonable settings of the two parameters for the UCLA datasets.

For the CAIDA datasets, we conducted a similar study [START_REF] Hasan | Obscure Giants: Detecting the Provider-free ASes[END_REF] and observed a qualitatively similar profile for the sensitivity of the TC algorithm average accuracy to the PFS membership threshold and lookback/lookahead window. The optimal setting is 5 months for both parameters w and n and close to the settings recommended above for the UCLA data source.

Conclusion

PFS, or the set of provider-free ASes, is important for Internet resilience and economics. Based on the public UCLA and CAIDA datasets of inferred inter-AS economic relationships, our paper developed the TC algorithm that sized PFS to a fraction of the overall AS population and determined the PFS members by means of AS customer-cone ranking and temporal dataset diversity. In comparison to the straightforward method for extracting PFS, our TC algorithm detected PFS with a substantially higher precision. We also assessed the sensitivity of the TC algorithm to its parameters.

  [19]. According to Wikipedia, PFS consisted of 9 members on 28/1/2009. The 25/3/2009 revision expanded this PFS to the following set [20]: W 1 = {AT&T, Global Crossing, Level 3, NTT, Qwest, Sprint, Verizon, Savvis, Telia, Tata}.

Fig. 1 :

 1 Fig. 1: Inter-AS economic relationships in the UCLA and CAIDA datasets during 2009.

Fig. 2 :

 2 Fig. 2: Customer-cone ranks of the ASes in W1.

Fig. 3 :

 3 Fig.3: PFS size according to Wikipedia and TC algorithm for the UCLA datasets.

Fig. 4 :

 4 Fig. 4: TC (Temporal Cone) algorithm and its notation.

Figure 5 (Fig. 5 :

 55 Fig. 5: Sensitivity of the TC algorithm average accuracy to PFS membership threshold n and lookback/lookahead window w for the UCLA datasets.

Table 2 :

 2 UCLA customer-cone ranks of ASes for 6/2009.

  , the TC algorithm sizes PFS to 9 ASes between 10/2008 and 1/2009, 10 ASes between 2/2009 and 12/2009, and 11 ASes from 1/2010 to 5/2011. This expansion is consistent with the PFS insights from the trustworthy non-verifiable sources.

	Year	2009		2010
	Month	4-8, 10-12	9	1-11
	UCLA	10 (9)	10 (10)	11 (11)
	Table 3: Size of PFS according to the TC al-
	gorithm for the UCLA datasets and (in paren-
	theses) number of ASes in this PFS that match
	the Wikipedia insights (W1 for 2009 and W2 for
	2010).