1 Introduction

Wireless sensor networks are made up of a large number of autonomous sensors that are densely deployed into an environment. Each of these sensors will typically have limited power, memory, and computational power to reduce the cost of the network. To solve the problems caused by these limitations, additional nodes can be added to a sensor network called relays. The relay nodes will be equipped with more powerful broadcasting hardware, giving them a larger communication range but making relays more expensive than the sensor nodes. We consider one further generalization to this problem by adding a set of basestations to the input, which have practically infinite broadcasting range (being part of the wired infrastructure). In this paper we study the problem of placing the minimum number of relay nodes to produce a network that connects all sensors and basestations.

In order to make the discussion more general, we use normed spaces. A normed space is a metric space \((X,d)\), given by a set \(X\) (of points) and a symmetric function (distance) \(d:X\times X \rightarrow {\mathbb {R}}^+\) that obeys the triangle inequality: \(\forall x,y,z \in X, d(x,y) \le 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 Bryant (1985), a normed space also has the following property (and others that we do not use): \(\forall x,y \in X\) and \(\forall \alpha \in [0,1]\), there exists \(z \in X\) such that \(d(x,y) = d(x,z) + d(z,y)\) and \(d(x,z) = \alpha \cdot 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).

Formally, we first consider the problem of Single-Tiered Relay (Node) Placement with Basestations (RPwB), which is defined as follows: As input we are given two sets \(S\) and \(B\) of points in a normed space \((M,d)\), which are the coordinates of the sensor nodes and basestations respectively, and two real numbers \(r\) and \(R, 0<r\le R\), which are the broadcast ranges of sensor and relay nodes respectively (Basestations have infinite broadcast range). When \(B = \emptyset \), we have the Single-Tiered Relay Placement problem.

A solution to the problem is a set \(Q\) of points to place relay nodes at. The sets \(S, B\) and \(Q\) induce an undirected graph \(G=(V,E)\) defined as follows: \(V=S\cup B\cup Q\) and \(E=\{uv|u,v\in B\}\cup \{uv|u\in Q\) and \(v\in Q\cup B\) and \(d(u,v)\le R\} \cup \{uv|u\in S\) and \(v\in S\cup Q\cup B\) and \(d(u,v)\le r\}\). A solution \(Q\) is feasible if the induced graph of \(S, B\) and \(Q\) is connected. The objective is to find a feasible solution of minimum cardinality.

Note that in Single-Tiered Relay Placement (with Basestations), sensor nodes can communicate with any other node within distance \(r\). A related problem is Two-Tiered Relay Node Placement, which only differs in that sensors cannot communicate directly with other sensors.

Single-Tiered Relay Placement in the two-dimensional Euclidean plane was proposed Lloyd and Xue (2007), who showed that an algorithm based on minimum spanning tree (MST) achieves approximation ratio 7. This algorithm works as follows. It first constructs an undirected edge-weighted complete graph of the set of sensors, where the edge weight is the distance between two sensors. Then it computes a MST of that graph. Finally, if the length of an edge, \(d\), is greater than sensor’s transmission range, \(r\), but less than or equal to \(2r\), the algorithm places a relay node on the middle of the edge. If \(d > 2r\), it places two relay nodes at the points, the distance of which is \(r\) from each endpoint of the edge, and another \(\lceil \frac{d - 2r}{R}\rceil - 1\) relay nodes on the rest of the edge, keeping the same distance between any two consecutive relay nodes on this edge. One can easily check that this distance is at most \(R\). The analysis of this algorithm is improved in (Calinescu and Tongngam 2008) to 6, which is also shown to be tight. We use this result which we present in a more general form. No other submission based on Calinescu and Tongngam (2008) was made (since in the time between the final version of Calinescu and Tongngam (2008) was submitted and the date it was published, a better result - next paragraph - was published).

For Two-Tiered Relay Node Placement in the two-dimensional Euclidean plane, Efrat, Fekete, Gaddehosur, Mitchell, Polishchuk, and Suomela, Efrat et al. (2008) claim a polynomial time approximation scheme (PTAS) (a description with proof sketches appears in Efrat et al. (2008), a version of Efrat et al. (2008) that we obtained online). Further, they show that the Single-Tiered problem admits no PTAS, assuming \(\hbox {P}\ne \hbox {NP}\), and presented a \(3.11\)-approximation algorithm for the two-dimensional Euclidean plane.

We improve this to \(2.8\), for the generalized problem with basestations. Our approximation ratio is based on using Zelikovsky’s Relative Greedy (Zelikovsky 1996) algorithm for Steiner tree and results on the \(k\)-restricted ratio (defined later) of Cohen and Nutov (2013). Thus this paper follows closely Cohen and Nutov (2013), who consider the special case where \(r=R\) , with the following main difference. We use our own (generalized from Calinescu and Tongngam 2008) \(\alpha _2\) ratio (defined later), which differs from the same ratio in the case \(r=R\) (which was settled by Mandoiu and Zelikovsky 2000).

In order to discuss generalizations, we use the strict Hadwiger number of the unit ball in the normed space, defined as follows: let \(\varDelta \) be the maximum number of points on a unit ball with distance strictly bigger than 1 between any pair of points. It is known (Robins and Salowe 1995; Martini and Swanepoel 2006) that \(\varDelta \) is the maximum degree of a minimum-degree MST in the normed space. It is known that in the Euclidean two-dimensional space, \(\varDelta = 5\), and in the three dimensional space, \(\varDelta = 12\). In Sect. 2, we will prove the following Theorem:

Theorem 1

Single-Tiered Relay Placement with Basestations in the case of Euclidean \(\mathbb {R}^2\) admits a polynomial time algorithm with approximation ratio \(\left( 1+\ln 6 + \epsilon \right) \,<\,2.8\). In arbitrary normed spaces, the ratio is \(1+\ln (\varDelta +1) + \epsilon \), provided that instances of Single-Tiered Relay Placement with Basestations on a constant number of sensors can be \((1+\epsilon )\)-approximated in polynomial time.

A related problem has the same input and output type, except that we explicitly allow any combination of two sensors and/or relays to have the same coordinates, and we require that \(G\) be two-connected. Our paper (Zhang et al. 2007) introduced Single-tiered Relay Placement for Biconnectivity and obtain, in the Euclidean two-dimensional space, an approximation ratio of 14 by computing a \(2\)-approximation (using Khuller and Raghavachari 1996) of the minimum-cost spanning two-connected subgraph, with costs as in the previously mentioned MST-based approximation for Single-Tiered Relay Placement, followed by placing, also as above, the necessary number of relays on each edge of the two-connected subgraph produced by the approximation algorithm. For Biconnectivity with basestations (\(2\)-RPwB) in the Euclidean two-dimensional plane, Zhang et al. (2007) claimed a \(16\)-approximation using a similar approach.

We incorporate results from Zhang et al. (2007) to prove, in Sect.  4, the next theorem. No other submission based on Zhang et al. (2007) was made, and, even though Zhang et al. (2007) has more than 100 citations, we could not find any improvements in the approximation ratio for the single-tiered results.

Theorem 2

Single-tiered Relay Placement for Biconnectivity with Basestations admits a polynomial-time algorithm with approximation ratio \(\varDelta +2\). In the Euclidean two-dimensional plane, the approximation ratio is \(7\).

This is obtained by a variant of the algorithm used by Cohen and Nutov (2013), with the only significant difference being computing a (different) average degree bound of certain trees. This part comes from Zhang et al. (2007), overcoming some technical difficulties to improve by an additive term of 1 for the version with basestations.

1.1 Related work

In Tang et al. (2006), Tang, Hao, and Sen present a \(4.5\)-approximation algorithm for Single-tiered Relay Placement and its version where two connectivity is required. However, Tang et al. (2006) assumes that \(R > 4r\) and that the sensors are uniformly distributed.

MSPT (Minimum Number of Steiner Points Tree with bounded edge length) is Single-Tiered Relay Placement in the case \(R=r\). In the case of Euclidean \(\mathbb {R}^2\), MSPT was introduced by Lin and Xue (1999) and proven NP-hard. They also prove that the MST heuristic achieves an approximation ratio of 5. Mandoiu and Zelikovsky (2000) give a tight analysis of 4 for the MST-based algorithm and generalize the proof to arbitrary normed spaces obtaining a ratio of \(\varDelta -1\). Chen et al. (2001) also prove the same ratio of \(4\) but with a different approach, and present a \(3\)-approximation algorithm. Later, Cheng et al. (2008) improve the running time of some of the algorithms found in Chen et al. (2001) and present a randomized algorithm with approximation ratio \(2.5\). In arbitrary normed spaces, Nutov and Yaroshevitch (2009) obtain a \(\left( \lfloor (\varDelta + 1)/2 \rfloor + 1 + {\epsilon }\right) \)-approximation. Recently, Cohen and Nutov (2013) propose a \(\left( 1+\ln (\varDelta -1)+\epsilon \right) \)-approximation for this problem using Zelikovsky’s Relative Greedy Zelikovsky (1996) local replacement algorithm.

The MSPT variant where two-connectivity is required was introduced by Kashyap et al. (2006, 2011), and they obtain an approximation ratio of \(10\) (\(=2 \varDelta \)) in the Euclidean \(\mathbb {R}^2\). A variant of the same algorithm, was shown by Calinescu (2012) to have approximation ratio of \(\varDelta \) in arbitrary normed spaces. Here and later, elements of \(S \cup B\) are also called terminals.

2 Proof of Theorem 1

Given a tree \(T\) on \(S \cup B \cup Q\), a Steiner component is a maximal subtree all whose internal vertices (if any) are from \(Q\). The edges of \(T\) are partitioned into these Steiner components. If, for a tree \(T\), each of its Steiner components has at most \(k\) vertices from \(B \cup S\), they form a \(k\)-restricted decomposition of \(T\).

Call a feasible solution \(Q\) of the Single-Tiered Relay Placement problem a bead-solution if the graph \(G\) induced by \(S, B\), and \(Q\) contains a spanning tree \(T\) where each node from \(Q\) has degree exactly two. The MST-based algorithm produces a bead solution. In a bead-solution, we may call the relay nodes beads.

For \(x,y \in S\cup B\), define

$$\begin{aligned} w(x,y) = \left\{ \begin{array}{l@{\quad }l} 0 &{} \hbox { if } ||x,y|| \le r \hbox { or }x,y\in B\\ 1 + \lceil \frac{||x,y|| - 2r}{R} \rceil &{} \hbox { if } r < ||x,y|| \hbox { and }x,y\in S\\ 1 + \lceil \frac{||x,y|| - r - R}{R} \rceil &{} \hbox { otherwise.}\\ \end{array} \right. \end{aligned}$$

One can easily verify that \(w(x,y)\) is the minimum number of relay nodes required to connect \(x\) and \(y\). Moreover, if one is to construct a bead-solution, then only the spanning tree \(T\) matters, and we may as well directly construct a spanning tree with minimum number of beads - that is a tree \(T'\) spanning \(S\) with minimum \(\sum _{xy \in E(T')} w(x,y)\).

Our approximation algorithm is based on Zelikovsky’s Relative Greedy (Zelikovsky 1996). The general idea is that we first select a group of up to \(k\) sensors and basestations that if connected optimally improve the approximation given by a MST. Then this \(k\)-restricted Steiner component is connected, and the algorithm repeats until no \(k\)-restricted Steiner component improves the spanning tree approach. Finally, a MST is used to finish connecting the sensors.

In an arbitrary normed space, Theorem 1 depends on the existence of a method for finding a \((1+ {\epsilon })\)-approximation to the problem with a fixed number of sensors. Even in the Euclidean \({\mathbb {R}}^2\), there is no known way to compute an exact solution to Single Tiered Relay Placement with Basestations on a set of up to \(k\) sensors for our \(k\)-restricted Steiner components. Still, from the definition of a \(k\)-restricted components, the sensors and basestation nodes make up the leafs of a tree in the induced graph.

In fact, we never need more than one basestation in the same Steiner component, as they are already connected by a path of total weight \(0\). With no basestation, we can consider the problem on these at most \(k\) sensors to be an instance of Two-Tiered Relay Node Placement. Since Efrat et al. (2008) claims a PTAS for this problem in \({\mathbb {R}}^2\), we will use a \((1+\epsilon )\)-approximation of the optimal solution in our algorithm. One basestation does not change the approach of Efrat et al. (2008).

We remark that, using this PTAS, a \((1+\epsilon )\)-approximation of the single tiered problem can be done in time exponential in the number of sensors.

We will briefly sketch the approximation argument of Zelikovsky (1996) to show the result of replacing optimal solutions on subproblems with \(\left( 1+\epsilon \right) \)-approximations. For a problem instance \(I\), we use \(opt(I)\) to denote the optimal solution to \(I\) and \(\tau _k(I)\) to denote the optimal solution that decomposes into \(k\)-restricted Steiner components. Then we define \(\alpha _k=\text {sup}_{I\in \mathcal {I}}\frac{\tau _k(I)}{opt(I)}\).

Lemma 1

For any integer \(k\ge 2\) and \(\epsilon >0\), Single-Tiered Relay Placement with Basestations admits a polynomial time approximation with approximation ratio \((1+\epsilon )\alpha _k(1+\ln \alpha _2)\).

Proof

The lemma follows immediately from the the following statement, with \(\beta = 1 + {\epsilon }\).

It just happens that the approximation ratio proof of Relative Greedy given by Gröpl et al. (2001) (Theorem 3.1) goes through when one uses a \(\beta \)-approximation instead of finding the optimum way when connecting \(k\) terminals, given an overall ratio of \(\beta \alpha _k(1+\ln \alpha _2)\).

If one wants to check, please refer to Gröpl et al. (2001) for most of the notions below (which differs from what we use in the rest of the paper). We denote the number of relays our \(\beta \)-approximation uses to connect a set of terminals \(T\) by \( appr (T)\) and, (to match Gröpl et al. 2001) by \(|T|\) denote the optimum number of relays to connect \(T\). Here \(R\) denotes the set of terminals (in our Lemma, this is \(S\cup B\)). Let \(T_i\) be the set of terminals that our algorithm chooses to connect in iteration \(i\), and \(j_i\) be the index that achieves the minimum in their Eq. (10). Then

$$\begin{aligned}&\frac{ appr (T_{i+1})/\beta }{\textit{MST}(R/T_1...T_{i})-\textit{MST}(R/T_1...T_{i}T_{i+1})}\end{aligned}$$
(1)
$$\begin{aligned}&\le \frac{ appr (T^*_{j_i})/\beta }{\textit{MST}(R/T_1...T_{i})-\textit{MST}(R/T_1...T_{i}T^*_{j_i})}\end{aligned}$$
(2)
$$\begin{aligned}&\le \frac{|T^*_{j_i}|}{\textit{MST}(R/T_1...T_{i})-\textit{MST}(R/T_1...T_{i}T^*_{j_i})} \end{aligned}$$
(3)

Then the same proof will work with \( appr (T_i)/\beta \) instead of \(|T_i|\). The final result will be

$$\begin{aligned} \sum \limits _{i=0}^{i_{max}} appr (T_i)/\beta =\textit{smt}_k+\textit{smt}_k\ln \frac{\textit{MST}(R)}{\textit{smt}_k}. \end{aligned}$$

The \(\beta \alpha _k(1+\ln \alpha _2)\) ratio immediately follows. \(\square \)

The method proposed by Cohen and Nutov (2013) for the special case when \(r=R\) and \(B=\emptyset \) uses the result in Chen et al. (2001) to solve the k-restricted Steiner trees exactly in the two-dimensional Euclidean plane. However, Chen et al. (2001) has the limitation of requiring a polynomial bound on the distance between any two sensors. This bound is required because their method enumerates out all possible candidate points for relays, which may be exponentially large between distant relays. Our work avoids this issue by utilizing the existing PTAS for the Two-Tiered problem. This PTAS gives its output as a set of points to place relays and lines to place relays evenly along. This allows it to output a solution with an exponential number of relays in polynomial time.

Then all that remains in order to prove Theorem 1 is to give an upper bound on the values of \(\alpha _2\) and \(\alpha _k\).

Lemma 2

\(\alpha _2\le \varDelta +1.\)

The proof of this lemma is deferred to Sect. 3. This result is tight in the two-dimensional Euclidean plane as shown by the example given in Fig. 1.

Fig. 1
figure 1

a is an optimal solution, b is an output from the MST-based algorithm. For such an example where the optimal solution requires \(|Q|\) relays (here \(|Q|=3\)), the MST solution will be \(4+6(|Q|-1)\). Thus the ratio approaches 6 in the Euclidean two-dimensional plane

Full size image

Cohen and Nutov (2013) proved that for ST-MSP, \(\alpha _k\) approaches 1 as \(k\) grows. We adapt their proof to apply it to RPwB to get the following Lemma.

Lemma 3

For any integer \(k\ge 4\varDelta -2, \alpha _k \le 1+\frac{2}{\lfloor \text {lg}\lfloor k/(2\varDelta -1)\rfloor \rfloor }\)

Proof

This lemma can be found by adapting a lemma used in Cohen and Nutov (2013) to prove a similar result for the special case when \(r=R\) follows. Their lemma is as follows:

Lemma 4

[Lemma 9 of Cohen and Nutov (2013)] Let \(T=(V,F)\) be a tree of maximum degree \(\delta \ge 2\), let \(S\subseteq V\), and let \(Q=V{\setminus } S\). Then for any integer \(k\ge 2\delta -2\) there exists a connected hypergraph \(\mathcal {H}=(S,\mathcal {E})\) of rank \(\le k\) such that \(\sum _{A\in \mathcal {E}}|V_A\cap Q|\le \left( 1+\frac{2}{\lfloor \text {lg}\lfloor k/\delta -1\rfloor \rfloor }\right) |Q|\).

The hyperedges of this lemma are \(k\)-restricted Steiner components. Combining this with the proof below that the induced graph of any feasible solution has a spanning tree with maximum degree at most \(2\varDelta \) will let us conclude Lemma 3.

Let \(Q\) be a feasible solution to the problem on sensor set (Basestations are handled as in Lemma 5 below). To find this degree bounded spanning tree, we use the following construction. Assign every edge in the graph induced by \(S\) and \(Q\) weight equal to the Euclidean distance between the endpoints. Then let \(T\) be a minimum-weight spanning tree of this graph. It is known that for ST-MSP (ie when \(r=R\) and thus all edges can have length from 0 to \(r\)), there exists such a minimum weight tree with maximum degree \(\varDelta \) (Robins and Salowe 1995; Martini and Swanepoel 2006).

We partition our tree \(T\) into two edge-disjoint forests \(F_1\) and \(F_2\), where an edge is in \(F_1\) if and only if its length is less or equal to \(r\), and \(F_2\) has all remaining edges. Each tree in these forests must be a minimum weight tree, otherwise \(T\) could be shortened. All edges in \(F_1\) have lengths between 0 and \(r\), inclusive. So we can use the previously mentioned result on each tree in \(F_1\) to find another minimum weight tree the same nodes with maximum degree \(\varDelta \). Similarly, all edges in \(F_2\) have length greater than \(r\), which implies they are all have relays or basestations as both endpoints. Therefore all edges in \(F_2\) have lengths between 0 and \(R\). Using the same result as before, we can find another minimum-weight tree for each tree in \(F_2\) with maximum degree \(\varDelta \). By taking the union of \(F_1\) and \(F_2\) after these modifications, we get a minimum weight tree with maximum degree \(2\varDelta \).

This degree bounded tree along with the Lemma 4 allows us to conclude Lemma 3. \(\square \)

By combining Lemma 1 with the upper bounds given by Lemmas 2 and 3, we find that for any \(k\ge 4\varDelta -2\), we can compute a \(\left( (1\!+\!\epsilon )(1\!+\!\frac{2}{\lfloor \text {lg}\lfloor k/(2\varDelta -1)\rfloor \rfloor })(1\!+\!\ln (\varDelta \!+\!1)) \right) \)-approximation in polynomial time. For large enough \(k\), the approximation ratio becomes \((1+\epsilon ')(1+\ln (\varDelta +1))\), which completes our proof of Theorem 1.

3 Proof of Lemma 2

Lemma 2 follows immediately from the lemma below, whose proof only has minor modifications compared to our proof from Calinescu and Tongngam (2008).

Lemma 5

Given \({\bar{Q}}\) a solution to the Single-Tiered Relay Placement with Basestations problem with input \(S\), we can construct a bead-solution \(\bar{Q}'\) for \(S\) with \(|{\bar{Q}}'| \le (\varDelta +1)|{\bar{Q}}|\).

Proof

Let \(G\) be the connected graph induced by \({\bar{Q}}\) and the input \(S\) and \(B\). We assign each edge between basestations in \(G\) weight zero, and all other edges weight equal to the distance between the endpoints. Let \({\bar{T}}\) be a MST in \(G\) where ties are broken such that edges between two nodes of \(S\cup B\) are lighter than edges with only one endpoint in \(S\cup B\).

Now consider the Steiner components in \({\bar{T}}\). It is sufficient to prove that each Steiner component can be connected by a bead solution with at most \(\varDelta +1\) times more relays. Therefore we will let \(T\) be a single subtree, \(S\) to be the sensors in \(T, Q\) to be the relays of \({\bar{Q}}\) in \(T\). If \(Q \ne \emptyset \), this component must have at most one edge incident to a basestation (otherwise a lighter spanning tree is created by replacing one of those edges with a basestation to basestation edge), and let \(b\) to be the single basestation in our component, if one exists (in which case \(b\) is a leaf in \(T\)).

Partition \(Q\) into \(X\) and \(Y\): the nodes of \(X\) have a neighbor from \(S\) in \(T\), and the nodes of \(Y\) do not. So a node of \(Y\) has, in \(T\), only neighbors from \(Q\cup \{b\}\). \(T\) will be a minimum Euclidean spanning tree since it only contains one vertex in \(B\). This implies, from a standard argument (Robins and Salowe 1995; Martini and Swanepoel 2006) that each node of \(Y\) has at most \(\varDelta \) neighbors from \(Q\cup \{b\}\). Our proof, like (Lin and Xue 1999; Mandoiu and Zelikovsky 2000), is based on replicating nodes of \(Q\), which means replacing a node by a number of beads placed in the same position.

Take a maximal set \(A\) of \(Y\) which is connected in \(T\). \(A\) together with the nodes of \(X\) adjacent to it induces a subtree \(T_A\) of \(T\) (this is akin to the Steiner component used for the Steiner tree problem (Zelikovsky 1993; Borchers and Du 1997). We use the standard argument of doubling each edge of \(T_A\), and doing an Eulerian tour of \(T_A\) starting from a node of \(X\). Each node of \(X\) other than the start appears once in this tour, and each node of \(Y\) exactly as many times as its degree in \(T_A\), that is, at most \(\varDelta \) times. Replicate each node of \(Y\) according to its degree, and replace \(T_A\) by the Eulerian tour above minus the last edge of the tour. Do this for all such \(A\) and obtain a new tree \(T'\) with node set \(S \cup X \cup Y' \cup \{b\}\), where \(Y'\) are the nodes obtained by replicating nodes of \(Y\), and such that \(T'\) is spanning and each node of \(Y'\) has degree at most two, i.e., is a bead. Note that \(|Y'| \le \varDelta |Y|\).

Repeatedly remove nodes of \( X \cup Y'\) if they have degree one, resulting in a spanning tree \(T''\) with node set \(S \cup X' \cup Y''\cup \{b\}\), where \(Y''\) and \(X'\) respectively, are those nodes of \(Y'\) and \(X\) respectively, not removed. Thus in \(T''\) all the leaves are from \(S\cup \{b\}\), and all the nodes of \(Y''\) have degree exactly two and neighbors only in \(X' \cup Y''\cup \{b\}\).

Root \(T''\) at \(b\) if it exists and at an arbitrary leaf otherwise, and then execute a postorder traversal of \(T''\), processing each node of \(x \in X'\) as described below. While doing this we construct a new tree \(T_3\), initialized to be \(T''\). Node \(x\) must have, in \(T''\), at least one neighbor in \(S\) - and in fact, since the neighbors of \(x\) from \(S\) in \(T''\) are exactly neighbors of \(x\) from \(S\) in \(T\), we can derive that \(x\) has at most \(\varDelta \) neighbors from \(S\) in \(T''\).

During the postorder traversal, we maintain the following invariant: each node of \(x \in X'\) ready to be processed (that is, with all its descendants in \(X'\) already processed) has, in \(T_3\), between one and \(\varDelta \) children, and all are from \(S\). Also, except for \(x\), all its descendants are nodes from \(S\) or beads. In addition, at all times, nodes from \(Y''\) remain beads (have degree two) with neighbors only from \(Y''\cup X'\cup \{b\}\) or are newly introduced beads.

Note that this invariant holds for nodes from \(X'\) which do not have proper descendants from \(X'\): such a node \(x'\) must have descendants or it would have been removed, and if \(x'\) has a child \(y\) from \(Y''\), then \(y\) must be on path to a node \(s\) from \(S\) (or all the subtree rooted at \(y\) would have been removed, starting with the leafs). Now, on the path from \(y\) to \(s\) there must be a node from \(X'\) - since nodes of \(Y''\) are not adjacent in \(T''\) to nodes of \(S\). Thus if \(y\) is a child of \(x'\), we obtain that \(x'\) has proper descendants from \(X'\) - a contradiction.

Now we describe how a node \(x\) from \(X'\) is processed: let \(s_1, s_2, \ldots , s_k\) be its children; recall that all belong to \(S\) and that \(1 \le k \le \varDelta \). If the parent of \(x\) in \(T_3\) is a node \(s\) from \(S\), change \(T_3\) by replicating \(x\) \(k\) times connecting, by paths of length two with the middle node a bead, \(s_1\) to \(s_2, s_2\) to \(s_3\), and so on until \(s_k\) is connected to \(s\). If the parent of \(x\) in \(T_3\) is \(b\), change \(T_3\) as before with \(b\) instead of \(s\).

If the parent of \(x\) in \(T_3\) is not from \(S\cup \{b\}\), then there is a path \(P\) from \(x\) to an ancestor node \(x' \in X' \cup \{b\}\) with all the intermediate nodes from \(Y''\) - this is since the root is from \(S\) or is \(b\), and nodes in \(Y''\) are never adjacent in \(T_3\) with nodes from \(S\). If \(x'\in X'\) then let \(s'\) be some node of \(S\) adjacent to \(x'\), otherwise let \(s'=b\). For ease of presentation, we consider two subcases: \(P\) has two nodes or strictly more than two.

In the first subcase, \(x\) is the child of \(x'\). Change \(T_3\) by replicating \(x\) \(k\) times into beads \(x_1, x_2, \ldots , x_k\), and adding a new bead, called \(x''\), connecting by beads \(s_1-x_1-s_2-x_2 \ldots x_{k-1} - s_k-x_k-x''-s'\). This is possible by placing \(x''\) at the same position as \(x'\). If \(x'\) is left without children, remove it from \(T_3\). Otherwise \(x'\) stays in \(T_3\), with one less neighbor (\(x\) is gone, and the new nodes are not adjacent directly to \(x'\)), until all its descendants are processed. See Fig. 2 for an illustration. The result is that all the nodes of the subtree rooted at \(x\) go in a subtree rooted at \(s'\), and this subtree consists only of nodes of \(S\) and beads. In total, instead of \(x\), we introduced up to \(k+1 \le \varDelta +1\) beads.

Fig. 2
figure 2

Illustration of the first subcase

Full size image

In the second subcase, let \(y_1\) be the second node of \(P\) and \(y_2\) be the next to last node of \(P\); note that \(y_1,y_2 \in Y''\), and it is possible \(y_1=y_2\). Replicate \(x\) \(k\) times, connecting by paths of length two with the middle node a bead: \(s_1\) and \(s_2\), etc, \(s_{k-1}\) to \(s_k\), and \(s_k\) to \(y_1\). Also, add another bead \(x''\) connecting \(y_2\) to \(s'\) by a path of length two. This is possible with \(x''\) being a bead in the same position as \(x'\). If \(x'\) is left without children, remove it from \(T_3\). Otherwise \(x'\) stays in \(T_3\), with one less neighbor (\(y_2\) is not adjacent to \(x'\) anymore, and the new nodes are not adjacent directly to \(x'\)), until all its descendants are processed. See Fig. 3 for an illustration. As before, the result is that all the nodes in the subtree rooted at \(y_2\) go in a subtree rooted at \(s'\), and this subtree consists only of nodes of \(S\) and beads. In total, instead of \(x\), we introduced up to \(k+1 \le \varDelta +1\) beads.

Fig. 3
figure 3

Illustration of the second subcase

Full size image

Note that in no case a node of \(X'\) maintains children from \(X'\cup Y''\) when it is time to be processed - such children are now adjacent to some newly introduced bead \(x''\), and \(x''\) is adjacent to some node in \(S\). Thus the invariant is maintained, each node of \(X'\) is replaced by \(\varDelta +1\) beads, and by the time we finish this postorder processing \(T_3\) consists of beads only, with the number of new beads being at most \((\varDelta +1) |X'|\).

We conclude that the final \(T_3\) has only nodes of \(S\) and beads, and the number of beads does not exceed

$$\begin{aligned} |Y''| + (\varDelta +1)|X'| \le |Y'| + (\varDelta +1) |X| \le (\varDelta +1) (|Y| + |X|) = (\varDelta +1) |Q|. \end{aligned}$$

\(\square \)

4 Proof of Theorem 2

Definition 1

For a subset \(C\) of nodes of a graph \(G=(V,E)\), let us use the following notation: \(\varGamma _G(C)\) is the set of neighbors of \(C\) in \(G\); \(\delta _G(C)=\delta _E(C)\) is the set of edges in \(E\) with exactly one endpoints in \(C\); \(E(C)\) is the set of edges in \(E\) with both endpoints in \(C\). Given \(S\subseteq V\), a Steiner component of \(G\) is a subgraph of \(G\) with node set \(C\cup \varGamma _G(C)\) and edge set \(E(C) \cup \delta _G(C)\), where \(C\) is a connected component of \(G{\setminus } (S\cup B)\). Let \(E(X,Y)\) to be the set of edges in \(E(G)\) with one endpoint in \(X\) and the other in \(Y\).

Continuing to follow (Cohen and Nutov 2013) with simplified notation, we consider the fractional bead solutions to the standard cut linear program relaxation problem of bead solutions \(2\)-RPwB. Thus \(G\) below is the complete simple graph of \(S \cup B\), with \(w_e\) for \(e = uv\) being equal to \(w(u,v)\). We can assume that our weighted complete graph is simple, as parallel edges have no effect on two-connectivity. The variables of the program are “capacities” \(x_e\) for all \(e \in E(G)\).

$$\begin{aligned} \begin{array}{lll} \text {minimize } &{} \sum \limits _{e\in E} w_e x_e \\ \text {subject to } &{} \sum \limits _{e \in E(V(G) {\setminus } X,X)} x_e \ge 2 \; &{} \; \forall \; X \subseteq V(G), \emptyset \ne X \ne V(G) \\ &{} \sum \limits _{e \in E(V(G) {\setminus } (\{z\} \cup X),X)} x_e \ge 1 \; &{} \; \forall \; z \in V(G) \;\; \forall \; \emptyset \ne X \subset V(G) {\setminus } \{z\} \\ &{} 0\le x_e\le 1 \ &{}\; \forall e\in E. \end{array} \end{aligned}$$

Using Menger’s theorem, one can check that, for a simple graph \(G\) and for an integral vector \(x\) valid for the linear program above, the set \(E'\) of edges \(e\) of \(E(G)\) with \(x_e=1\) is such that the graph \((V(G),E')\) is two-connected. Thus one can think of a valid fractional vector \(x\) as being “fractional-two-connected”. We use \(\tau ^*\) to denote the optimal solution to our linear program.

We will show that for any problem instance \(I\) the ratio \(\frac{\tau ^*(I)}{opt(I)}\) is at most \(\frac{\varDelta +2}{2}\). Now notice that an approximation algorithm that produce a bead solution of cost at most \(\rho \tau ^*\), will then give \(2\)-RPwB a \(\left( \rho \frac{\varDelta +2}{2} \right) \)-approximation. The \(2\)-approximation for minimum-cost two-connected subgraph of Fleischer et al. (2006) (also handling a more general problem) is based on iterative rounding and does have \(\rho =2\) above, and thus we have a \(\left( \varDelta +2 \right) \)-approximation.

To prove our upper bound on the gap between the optimal relay placement and the optimal fractional bead solution, we need the two lemmas below. The first of these, Lemma 6, is a special case of a theorem proven in Cohen and Nutov (2013).

Lemma 6

[From Theorem 5 of Cohen and Nutov (2013), also implicit in the journal version of Calinescu (2012)] Let \(G\) be a two-connected graph such that \(V(G)=S \cup B \cup Q\), and such that no proper two-connected subgraph \(J'\) of \(G\) exists such that \(S \cup B \subseteq V(J')\). Then every Steiner component of \(G\) is a tree. Furthermore for any subset \(\mathcal {C}\) of Steiner components of \(G\), replacing each \(C\in \mathcal {C}\) by a fractional DFS cycle of capacity \(1/2\) results in a two-connected fractional bead solution.

Aside from the existence of basestations, the next lemma is our Lemma 3.3 of Zhang et al. (2007) with \(\varDelta \) instead of 5. With basestations, it improves by an additive term of 1 the bound in Lemma 3.7 of Zhang et al. (2007).

Lemma 7

Let \(Q\) be a feasible solution to \(2\)-RPwB on sensor set \(S\) and basestation set \(B\). Then the induced graph has a two-connected subgraph that can be decomposed in to Steiner components such that each component is a tree and satisfies the following: Let \(Q'\) denote the set of relays of some Steiner component. Then \(\sum _{v\in Q'}\text {degree}(v)\le (\varDelta + 2)|Q'|\).

Proof

Let \(G\) be the induced graph of \(S, B\), and \(Q\). We will first find a subgraph \(G'\) of \(G\) that is still two-connected, but has at most one edge incident to a basestation per Steiner component. We assume that there are at least three basestations in total, we will handle the case of two or less basestations in the last paragraph of our analysis.

We construct \(G'\) as follows: Start with \(G'\) being a cycle going through all basestations in \(G\). While there are sensors in \(G\) that are not in \(G'\), find a path starting and ending in \(G'\) containing such a sensor (such a path exists because \(G\) has two paths, disjoint except the sensor endpoint, between the sensor and \(G'\)). Add this path to \(G'\) and repeat. Note that this corresponds to an ear-decomposition and \(G'\) is two-connected; at the end, \(S \cup B \subseteq V(G')\).

Our algorithm maintains the loop invariant that all Steiner components in \(G'\) have at most one edge incident to a basestation. This is trivially true in the initial cycle. Each path added to \(G'\) can be adjacent to at most two basestations (the first and last edge). Since the path contains a sensor, these two basestations will be incident to different Steiner components. Therefore any Steiner component created has at most one adjacent basestation. An existing Steiner component only becomes larger when an added path starts or ends in it. Then by the same argument, no edge incident to a basestation can be added to this component.

Let \(G''\) by a subgraph of \(G'\) such that no proper two-connected subgraph \(J'\) of \(G''\) exists such that \(S \cup B \subseteq V(J')\). Now, by Lemma 6, all the Steiner components are trees, and we still have that each Steiner components has at most one basestation. Further assume that the total length (in the normed space) of the edges of \(G''\) is minimized, and ties are broken such that two nodes of \(S\) are considered closer than any other combination of two nodes, if their pairwise length is the same. Let \(Q''\) be the set of relays of \(G''\). We use the following version of Lemma 3.2 of Zhang et al. (2007).

Claim

Every vertex of \(Q''\) has at most \(\varDelta \) neighbors in \(S\).

Proof

Assume that there is a relay node \(y \in Q''\) that has at least \(\varDelta +1\) neighbors in \(S\). We will show that this assumption leads to another another two-connected \({\hat{G}}\) subgraph of \(G'\) with \(S \cup B \subseteq V({\hat{G}})\), contradicting the shortest length assumption of \(G''\).

Recall that \(\varDelta \) is the maximum number of points on a unit ball with pairwise distance strictly bigger than 1. Let \(x_1, x_2, \ldots , x_k\) be the neighbors of \(y\) in \(S\). As \(k > \varDelta \), two of these, say, \(x_1\) and \(x_2\), satisfy \(d(x_1,x_2) \le r\) and thus the undirected edge \(x_1x_2\) is induced by \(S\). In fact, then next paragraph (whole argument taken from Robins and Salowe (1995)) shows that we can assume \(d(x_1,x_2) \le d(y,x_1)\).

Draw a ball of radius \({\epsilon }\) (using distance \(d\)) around \(x\), where \({\epsilon }< d(y,x_i)\) for all \(i\). Let \(x'_i\) be the intersection of a segment \(y x_i\) with the boundary of this ball. Since \(k\) exceeds the Hadwiger number of the unit ball in the normed space, there exist \(i,j\) with \(d(x'_i, x'_j) \le {\epsilon }\). Assume by symmetry that \(d(y,x_i) \le d(y,x_j)\). Drawing the ball of radius \(d(y,x_i)\) around \(y\); and let \(x''_j\) be the point where the segment \(y x_j\) used for finding \(x'_j\) intersects the boundary of this bigger ball. Then we also have \(d(x_i, x''_j) \le d(y,x_i)\), and therefore

$$\begin{aligned} d(y,x_j)&= d(y,x''_j) + d(x''_j,x_j) = d(y,x_i) + d(x''_j, x_j) \ge d(x_i, x''_j)\\&\quad +\, d(x''_j,x_j) \ge d(x_i,x_j), \end{aligned}$$

and all that remains is to relabel \(x_j = x_1\) and \(x_i = x_2\). use \(y_i\) as \(y\) and \(y_j\) as \(z\), and then \(d(x_1,x_2) \le d(y,x_1)\) as desired.

We first prove the following proposition.

  1. (a):

    \(G''\) does not contain edge \(x_1 x_2\).

Since \(G''\) is two-connected, there is a path \(\pi \) in \(G''\) connecting \(x_k\) and \(x_1\) without using node \(y\). If \(\pi \) does not go through \(x_2\), we have a scenario as shown in Fig. 4a. If \(\pi \) goes through \(x_2\), we have a path \(\pi '\) in \(G''\) connecting \(x_k\) and \(x_2\) without using nodes \(y\) and \(x_1\), as shown in Fig. 4(b). In the first scenario (see Fig. 4a), \(G''\) contains a cycle going through \(x_1, x_2, y\), and \(x_k\) and a chord (edge connecting two non-consecutive vertices of the cycle) \(y x_1\). Deleting the chord \(y x_1\) from \(G''\) will reduce the length without destroying two-connectivity (Frank 2011), contradicting the shortest length assumption of \(G''\). Similarly, deleting the chord \(y x_2\) will lead to a contradiction in the second scenario (refer to Fig. 4b). This proves (a).

Let \({\hat{G}}\) be the subgraph of the graph induced by \(S, B\), and \(Q''\) that is obtained from \(G''\) by replacing the edge \(y x_1\) with \(x_1 x_2\). Note that \({\hat{G}}\) has smaller total edge length compared to \(G''\). Next we prove

  1. (b):

    For any two \(u,v \in S \cup B\), there exists a pair of internally-disjoint paths in \({\hat{G}}\) connecting \(u\) and \(v\).

Fig. 4
figure 4

\(G''\) cannot contain the edge \(x_1, x_2\). In case (a), the edge \(y x_1\) can be removed, and in case (b), the edge \(y x_2\) can be removed

Full size image

Since \(G''\) is two-connected, there exists a pair of internally-disjoint paths \(\pi _1\) and \(\pi _2\) in \(G''\) connecting \(u\) and \(v\). If neither path uses edge \(y, x_1\), then \(\pi _1\) and \(\pi _2\) also form a pair of internally-disjoint paths in \({\hat{G}}\). Now we consider the case where one of the paths (WLOG, assuming \(\pi _1\)) uses edge \(y x_1\).

First, consider the subcase where \(\{u, v \} = \{x_1, x_2\}\). In this case, \(\pi _2\) and the edge \(x_1 x_2\) form two internally-disjoint \(x_1\)–\(x_2\) paths in \({\hat{G}}\) (note that \(\pi _2\) is a path in \(G''\) and the edge \(x_1 x_2\) was proven not to be in \(G''\), and thus \(\pi _2\) is internally-disjoint from the edge \(x_1 x_2\)).

Next, consider the subcase where \(u = x_1\) but \(v \ne x_2\). Since \(\pi _1\) goes through \(y\) (which is a relay node), \(\pi _2\) does not go through \(y\). If \(\pi _2\) goes through \(x_2, G''\) contains the cycle formed by the two paths \(\pi _1\) and \(\pi _2\), as well as a chord \(y x_2\). This contradicts the shortest length assumption of \(G''\) (see Fig. 5a and the similar argument used in the proof of (a)).

Therefore \(\pi _2\) does not go through \(x_2\) (see Fig. 5b). We can replace \(\pi _1\) with a new \(v\)–\(x_1\) path \(\pi _3\) which goes from \(v\) to \(y\) along \(\pi _1\), then to \(x_2\) via edge \(y x_2\), then to \(x_1\) via edge \(x_2 x_1\) (see Fig. 5c). \(\pi _2\) and \(\pi _3\) form a pair of node disjoint \(x_i\)–\(x_1\) paths in \({\hat{G}}\). This shows that (b) is true in this subcase.

If \(v = x_2\) and \(u \ne x_1\), and \(\pi _1\) uses the edge \(y x_1\), we may as well replace (if needed) the portion of \(\pi _1\) between \(y\) and \(x_2\) by the edge \(y x_2\). If \(\pi _1\) still contains \(y x_1\), the we replace in \(\pi _1\) the edges \(x_2 y\) and \(y x_1\) by \(x_2 x_1\), resulting in a path of \({\hat{G}}\) that is still internally-disjoint from \(\pi _2\) (which remains a path of \({\hat{G}}\)). This shows that (b) is true in this subcase.

Finally we consider the subcase where \(\{u, v\} \cap \{x_1, x_2\} = \emptyset \). Since \(\pi _1\) goes through \(y, \pi _2\) does not go through \(y\). If \(\pi _2\) goes through \(x_2\), then \(G''\) contains the cycle formed by the two paths \(\pi _1\) and \(\pi _2\), as well as a chord \(y x_2\), contradicting the shortest length assumption of \(G''\). Therefore \(\pi _2\) does not go through \(x_2\). We can replace \(\pi _1\) with a new \(u\)–\(v\) path \(\pi _3\) which goes from \(u\) to \(y\) along \(\pi _1\), then to \(x_2\) via edge \(y x_2\), then to \(x_1\) via edge \(x_2 x_1\), then to \(v\) following the subpath on \(\pi _1\). \(\pi _2\) and \(\pi _3\) form a pair of node disjoint \(u\)–\(v\) paths in \({\hat{G}}\). This shows that (b) is true in this subcase, and completes the proof for (b).

Thus according to (b), for any two distinct \(u,v \in S \cup B\), there exists a pair of internally-disjoint paths in \({\hat{G}}\) connecting \(u\) and \(v\). If \({\hat{G}}\) is not two-connected, it has a vertex \(z\) such that removing \(z\) from \({\hat{G}}\) results in at least two connected components, and one of these components contains no vertex of \(S \cup B\), since we have two internally-disjoint paths between any two vertices of \(S \cup B\). Change \({\hat{G}}\) by removing one such component, and note this does not decrease the connectivity between the vertices of \(S \cup B\).

The total edge length of \({\hat{G}}\) also does not increase, so we did reach the contradiction of finding in \({\hat{G}}\) a two-connected subgraph subgraph of \(G'\) with \(S \cup B \subseteq V({\hat{G}})\), contradicting the shortest length assumption of \(G''\). This completes the proof of the claim.\(\square \)

Fig. 5
figure 5

Replacing the edge \(y x_1\) with the edge \(x_1 x_2\). The situation in a is impossible. Subfigure b shows part of \(G''\) (before) and subfigure c shows part of \({\hat{G}}\) (after)

Full size image

Let \(Q'\) denote the set of relays of some Steiner component of \(G''\). Therefore we have at most \(\varDelta |Q'|\) edges between sensors and relays in this Steiner component.

All internal nodes of the Steiner component are relays, and therefore our tree has \(|Q'|-1\) relay to relay edges. When summing over the degree of all relays, these edges will be counted twice. Combining this, with our bound on the number of edges incident to a sensor and incident to a basestation the total degree of relays in our Steiner component is bounded by:

$$\begin{aligned} \sum _{v\in Q'}\delta (v)\le 1+2(|Q'|-1) + \varDelta \cdot |Q'| <(\varDelta +2)|Q'| \end{aligned}$$

This analysis assumed that we had at least three basestations. If there are two or fewer basestations, then we can bound the number of edges of a Steiner component incident to a basestation by 2 (the Steiner component being a tree where basestations, if any, are leafs), which gives \(\sum _{v\in Q'}\delta (v)\le (\varDelta +2)|Q'|\) by the same arguments. This finishes the proof of Lemma 7. \(\square \)

For a given Steiner component in the optimal solution, we can create a cycle by using a depth first traversal and duplicating each relay every time it is visited. From Lemma 7, we know this cycle will have at most \(\varDelta +2\) beads per relay node on average. Then by Lemma 6, assigning the cycle in each Steiner component of the optimal relay placement capacity \(1/2\) we find a fractional bead solution with cost at most \(\frac{\varDelta +2}{2}\) times more than the optimal relay placement.

5 Conclusion

We have shown that the method presented by Cohen and Nutov for ST-MSP can be extended to give a \(\left( 1+\ln (\varDelta +1)+\epsilon \right) \)-approximation to Single-Tiered Relay Placement with Basestations. In the case of relay placement on a Euclidean plane, this result improves the best known approximation from \(3.11\) to \(2.8\).

In three dimensions, our result (Theorem 1) is conditional on the existence of a \(\left( 1+{\epsilon }\right) \)-approximation for a constant number \(k\) of sensors. Actually, the running time of this approximation can be any function of \(k\), but must be polynomial in the length of the (binary) representation of \(R\) and the coordinates of the sensors. We comment on the existence of such an algorithm. A \(\left( 1 + {\epsilon }\right) \)-approximation seems possible if the solution is at least \(k^2\) (the sensor are far apart), since the minimum Euclidean-length Steiner tree can be approximated (Arora 1998) and used, with nodes relay on the Steiner points and beads on the edges, losing only \(12k\) beads compared to an optimum solution. When the sensors are close to each-other, the typical approach is to construct a finite set of points (a large number such as \(k^k\)) using rigidity/motion planning and/or local changes arguments (in two dimensions, this appears in Chen et al. (2001), 11), and argue that an optimum or close-to-optimum solution exists with all the relays place on this finite set of points. We leave the existence of such an algorithm open. If it exists, then this paper gives a \(3.57\)-approximation. It is not clear to us whether the approach of Efrat et al. (2008) extends to three dimensions at all.

We also considered the biconnected version of relay node placement with basestations and obtained a \(\left( \varDelta + 2 \right) \)-approximation. We choose to base our presentation on Cohen and Nutov (2013) and Fleischer et al. (2006) as it allows for citations instead of longer proofs. We believe that using the variant of Khuller and Raghavachari (1996) proposed by Auletta et al. (1999), with Gabow (1993) implementation of the Frank and Tardos (1989) gives the same approximation ratio without the (slower) iterative rounding method of Fleischer et al. (2006). This would be a variant of our Zhang et al. (2007) algorithm.

A more general problem has as input connectivity requirements \(r_{uv}\in \{0,1,2\}\) and the induced graph is required to have \(r_{uv}\)-internally disjoint between for each \(u,v\in S\cup B\). We failed in generalizing our \(\left( \varDelta + 2 \right) \)-approximation for this model, precisely the claim inside the proof of Lemma 7 does not seem to hold, in light of the example of Fig. 4 of Kashyap et al. (2006), when connectivity requirements are 1 between any two sensors other than the (already) adjacent sensors, where connectivity requirements are 2.