Determining Sensor Locations in Wireless Sensor Networks

Abstract

Network lifetime plays an important role in the design of wireless sensor networks. This paper studies the problem of prolonging the wireless sensor network's lifetime, through introducing additional sensors at proper locations to achieve the goal of minimizing the length of the longest edge in the network. The problem is in fact the bottleneck Steiner tree problem, trying to find a Steiner tree minimizing the length of the longest edges for the given n terminals in the Euclidean plane by introducing at most k Steiner points. A restricted bottleneck Steiner tree problem is studied in this paper, which requires that only degree ≥3 Steiner points are not allowed to be adjacent in the optimal solution. We show that the restricted problem is MAX-SNP hard and cannot be approximated within performance ratio $\sqrt{2}$ in polynomial time unless P = NP; we first propose a polynomial time $\sqrt{3}$ -approximation algorithm and then improve the ratio to $\sqrt{2}+\epsilon$ for any given $\epsilon >0$ , by presenting a polynomial time randomized approximation algorithm, which is almost optimal to the restricted problem.

1. Introduction

Wireless sensor networks have been applied in a variety of defense and civil domains. The efficiency and reliability of these applications rely on the availability and performance of radio-frequency sensors. These applications generally involve deployment of sensors to make information communicate through wireless sensor networks [1]. A security and protection system includes many sensors capable of collecting the changes of environment and sending signals to data collection node through the sensor network. Generally, sensors use batteries to provide power, which has a potential danger of consumed power causing sensors to stop working, just because the battery can operate only for a limited time. In the radio-frequency wireless sensor networks, the power required to transfer a signal is related to the distance between the source and destination sensors. In general, shorten distance among nodes means longer network lifetime. Given n sensors to be put on fixed locations and at most k additional sensors can be introduced, this paper tries to construct a Steiner tree interconnecting the given n sensors and up to k additional sensors such that the length of the largest distance between sensors in the tree is minimized. Therefore, the power needed to transfer signals on the longest link is minimized and the network lifetime is thus prolonged.

Above problem can be formulated as the bottleneck Steiner tree problem, which is a variation of the traditional Steiner tree problem. Unlike the traditional Steiner tree problem, asking to find a tree spanning, the required points by introducing some additional such that the length of the tree are minimized [2, 3], the bottleneck Steiner tree minimizes the length of the longest edge in the tree. We call the required points terminals, the additional points Steiner points, and such a tree a Steiner tree.

The traditional Steiner tree problem has been proved to be NP-hard even if the weights of edges are defined as 1 or 2 [3]. Arora proposed a polynomial-time approximation scheme (PTAS) [4] for the traditional Steiner tree problem in the Euclidean plane, which is the best result that can be achieved for NP-hard problems.

Emerging applications in VLSI layout design, wavelength division multiplexing optical network and wireless networks trigger the study of variations of the traditional Steiner tree problem and attract many researchers’ interests and efforts. Algorithms for the two variations, the bottleneck Steiner tree problem [1, 5–8] and the Steiner tree problem with minimum number of Steiner points and bounded edge-length [9, 10], have been studied widely and deeply.

This paper studies the bottleneck Steiner tree problem. We first give a formal definition.

Definition 1.

Given n terminals set $P=\{p_1,p_2,\dots ,p_n\}$ and an integer $k>0$ , the bottleneck Steiner tree problem asks a Steiner tree spanning P with at most k Steiner points minimizing the length of the longest edge in the tree.

The bottleneck Steiner tree problem is proved to be MAX-SNP hard in both rectilinear plane and Euclidean plane, in further, it cannot be approximated within ratios 2 and $\sqrt{\mathrm{2}}$ in polynomial time for the two kinds of planes, and a ratio 2 approximation algorithm for the problem in two planes was presented [5]. In 2002, we improve the approximation ratio to 1.866 by proposing a randomized polynomial approximation algorithm [6]. Later, Cardei et al. proved the existence of approximation ratio $\sqrt{\mathrm{3}}$ and provide a corresponding approximation algorithm [1], which is the best ratio so far. But the gap between the approximation ratio and inapproximation result is still big.

Restricted versions of the bottleneck Steiner tree problem are considered and studied. One kind of restriction is to restrict the number of Steiner points. Bae et al. restricted the number of Steiner points to 1 and 2 of the Euclidean bottleneck Steiner tree and gave an algorithm for computing the exact Steiner tree in polynomial time [11]. In fact, the closest string problem studied by Li et al. is a bottleneck Steiner tree problem with $k=1$ in the String space, in [12], the problem is shown to be NP-hard and a polynomial time approximation scheme is presented. As to the kind of restriction of consideration of adjacency of Steiner points, in [7, 8], when requiring that either any two Steiner points are not adjacent or only degree 2 Steiner points are adjacent in the optimal Steiner tree, both of the two versions of Euclidean bottleneck Steiner tree problem cannot be approximated within $\sqrt{\mathrm{2}}$ in polynomial time and the existence of approximation ratio $\sqrt{\mathrm{2}}$ is proved.

In this paper, we further loosen the restriction of adjacency of Steiner points by requiring that only Steiner points of degree at least 3 are not allowed to be adjacent in the optimal Steiner tree in the Euclidean plane. This version is more general than the one studied in [8] and is almost close to the original Euclidean bottleneck Steiner tree problem. For describing convenience, we denote the problem restrict-EuclidBST for short. We will first prove that it is NP-hard and cannot be approximated within $\sqrt{\mathrm{2}}$ ; then, we show the existence of ratio $\sqrt{\mathrm{3}}$ and design a $\sqrt{\mathrm{3}}$ -approximation algorithm in $O(n\log n+kn)$ time for later algorithm's call. Consequently, we will show the existence of ratio $\sqrt{\mathrm{2}}$ and devise a randomized approximation algorithm with ratio $\sqrt{\mathrm{2}}+\epsilon$ , for any $\epsilon >0$ . The algorithm almost solves the restrict-EuclidBST problem.

Following is the organization of the paper. Section 2 shows the hardness result for the restrict-EuclidBST problem and design a $\sqrt{\mathrm{3}}$ -approximation algorithm in polynomial time. We further improve the performance ratio to $\sqrt{\mathrm{2}}$ by a notion of 3-restricted Steiner tree. Section 4 concludes the whole content.

2. $\sqrt{3}$ -Approximation Algorithm

In this section, we first give the hardness result for restrict-EuclidBST and then show the existence of a Steiner tree with the length of the longest edge at most $\sqrt{\mathrm{3}}$ the optimum. Similar to the proof in paper [5], by using a polynomial reduction from planar graph vertex cover with vertex degree ≤4 problem to our restrict-EuclidBST problem, together with the NP-hardness of the former problem, we prove that our problem is also NP-hard, in fact, we get a more strong result.

Theorem 2.

Under the assumption that $P\ne NP$ , the restrict-EuclidBST problem cannot be approximated within $\sqrt{\mathrm{2}}$ in polynomial time.

We try to propose a $\sqrt{\mathrm{3}}$ -approximation algorithm for the restrict-EuclidBST problem. We first show the existence of ratio $\sqrt{\mathrm{3}}$ by introducing the notion of full Steiner component of a Steiner tree.

We call a Steiner tree full if each of its terminals is a leaf and all the Steiner points are internal nodes. It is easy to see that a not-full Steiner tree can be decomposed into the union of edge-disjoint full subtrees at the terminals that are not leaves. Each of the decomposed full subtrees may share one or more common terminals with others. It is natural to call these full subtrees full Steiner components, in contrast to full Steiner tree. More formally, a full Steiner component can be defined as below.

Definition 3.

A full Steiner component of a Steiner tree is a subtree with the degree of each terminal being 1 and the degree of each Steiner point being at least 2; that is, all terminals in the subtree are leaves and all the internal nodes are Steiner points.

By the notion of full Steiner component, our first lemma indicates that each full Steiner component of the optimal Steiner tree can be transformed into a “Steinerized” subtree with the degree of each Steiner points is 2 and the length of the longest edges at most $\sqrt{\mathrm{3}}$ the optimum. Then, by unionizing all these subtrees at their sharing common terminals, we get a “Steinerized” spanning tree with the largest edge length at most $\sqrt{\mathrm{3}}$ the optimum and such a tree can be computed in polynomial time easily.

For convenience, supposing that a and b are terminals in the Euclidean plane, we use $ab$ to denote the segment and $\left|ab\right|$ to denote the length of segment $ab$ . Without loss of generality, assume the length of the longest edge in the optimal solution is 1.

Lemma 4.

Given n terminals set P and integer k, suppose T is an optimal bottleneck Steiner tree interconnecting P with at most k Steiner points for the restrict-EuclidBST problem; there exists a steinerized spanning tree $T^{\prime }$ with the same number of Steiner points as T and the degree of each Steiner point is 2 such that the length of each edge in $T^{\prime }$ is at most $\sqrt{\mathrm{3}}$ .

Proof.

For the restrict-EuclidBST problem, since Steiner points with degree at least 3 are not possible to be adjacent in the optimal bottleneck Steiner tree, according to the notion of full Steiner component introduced above, the optimal bottleneck Steiner tree T can always be decomposed into the union of its edge-disjoint full Steiner components, each of which is either a star-like subtree with a Steiner point of degree at least 3 as center while other Steiner points are all of degree 2 (see Figure 1) or just a line-segment path connecting two terminals with $l\ge 0$ intermediate degree-2 Steiner points (see Figure 2).

For a star-like subtree $T_s$ with at least 3 terminals, we can modify the tree step by step to a tree with the degree of each Steiner point exactly 2 by decreasing the degree of the center Steiner point and make sure that the length of the longest edge in the modified tree is at most $\sqrt{\mathrm{3}}$ .

Suppose v is the center of $T_s$ and its degree is 3 (the case of degree more than 3 can be processed similarly); let a, b, and c be the three terminals around v (see Figure 3); then, $\angle avb$ , $\angle bvc$ , and $\angle cva$ form 360°. Thus, at least one of $\angle avb$ , $\angle bvc$ , and $\angle cva$ is at most 120°. Without loss of generality, assuming $\angle avb$ ≤120° and $\left|vb\right|\le \left|va\right|$ , that is, the length of $vb$ is no longer than $va$ , it is easily seen that

$$\begin{array}{l}\left|ab\right|=\sqrt{{\left|va\right|}^{\mathrm{2}}+{\left|vb\right|}^{\mathrm{2}}-\mathrm{2}\left|va\right|·\left|vb\right|\cos \angle avb}\\ \le \sqrt{\mathrm{3}}\left|va\right|.\end{array}$$

(1)

Let x be the number of Steiner points degree-2 (not including v) on segment $va$ ; then, we can directly connect a and b and add x equally spaced degree-2 Steiner points to it (which we call “Steinerize” the segment), and the length of each edge in the segment $ab$ is at most $\sqrt{\mathrm{3}}$ because the length of segment $va$ is at most $x+1$ (remember the length of each edge on the path from a to v is at most 1), removing the longer segment $va$ results in the decrease of degree of v by 1. Figure 3 illustrates the transformation procedure.

The above procedure transforms the star-like subtree $T_s$ into a Steinerized subtree with the same number of Steiner points as $T_s$ and the length of each edge is at most $\sqrt{\mathrm{3}}$ . As to the line-segment path, no work is need because its edge length is at most 1. Unite all the Steinerized subtrees and the line-segment paths at their sharing common terminals forming a Steinerized spanning tree with same number of Steiner points as the optimal tree T; the degree of each Steiner point is exactly 2 and the length of each edge is at most $\sqrt{\mathrm{3}}$ . This completes the proof.

Figure 1

A star centered at Steiner point v.

Figure 2

A line-segment path with 2 degree-2 Steiner points.

Figure 3

Decrease the degree of v from 3 to 2.

Lemma 4 indicates that the bottleneck Steiner tree can be found among Steinerized spanning trees with k degree-2 Steiner points. By an excellent property of minimum spanning tree as described in Lemma 5, we can compute such a Steinerized spanning tree by step by step adding k degree-2 Steiner points to long edges in a minimum spanning tree for the n given terminals.

Lemma 5 (see [5]).

Let $e_1,e_2,\dots ,e_{n-1}$ be the edges in a spanning tree T and let ${e_1}^{*},{e_2}^{*},\dots ,{e_{n-1}}^{*}$ be edges in a minimum spanning tree $T^{*}$ for the same set P of terminals. Suppose $\left|e_i\right|\le \left|e_{i+1}\right|$ and $\left|{e_i}^{*}\right|\le \left|{e_{i+1}}^{*}\right|$ for all $1\le i\le n-1$ where $\left|e\right|$ denotes the length of e. Then, $\left|{e_i}^{*}\right|\le \left|e_i\right|$ for all $1\le i\le n-1$ .

Before we present our algorithm, we need some notations and explanations to make the algorithm easier to understand. First, for any edge $e_i=(a,b)$ in a spanning tree, if we add $l_i$ Steiner points of degree 2 to Steinerize it, the Steiner points together with the two endpoints a and b must be equally spaced to guarantee each of the edges formed in the path from a to b achieves the minimum possible length; that is $\left|e_i\right|/(l_i+1)$ ; here $\left|e_i\right|$ is the original length of $e_i$ . Denote $l(e_i)=\left|e_i\right|/(l_i+1)$ ; we call it the Steinerized length of $e_i$ .

$l(e_i)$ is initialized as $\left|e_i\right|$ and $l_i$ is initialized as 0, in the beginning. During the algorithm process, degree-2 Steiner points are added step by step to the edge $e_i$ with largest Steinerized length $l(·)$ value at a time. If one more degree 2 Steiner point is added to edge $e_i$ , the Steinerized length $l(e_i)$ of $e_i$ is updated by $\left|e_i\right|/(l_i+1)$ and the number of Steiner points on $e_i$ increases by 1; that is, $l_i=l_i+1$ .

It is worthy to point out that when we add a degree 2 Steiner point to an edge, we need not to compute the positions of the Steiner points on that edge at each time but only update the Steinerized length $l(·)$ and the number of Steiner points of that edge. Computation of Steiner points’ positions can be left to the last step to improve the algorithm's efficiency. The complete ratio- $\sqrt{\mathrm{3}}$ algorithm for Restricted-EuclidBST is as below.

Algorithm (restrict-EuclidBST-ratio- $\sqrt{3}\hspace{0.17em}\hspace{0.17em}(P,n,k)$ ).

• (1)

Find a minimum spanning tree T for P; let $e_1,e_2,\dots ,e_{n-1}$ be the edges of T.

(2)

Initialize $l(e_i)\leftarrow \left|e_i\right|$ and $l_i\leftarrow 0$ for $1\le i\le n-1$ .

(3)

Find $e_i=(u,v)$ with the largest $l(·)$ value and add a Steiner point to it.

(4)

Update $l(e_i)$ by $\left|e_i\right|/(l_i+1)$ and $l_i$ by $l_i+1$ .

(5)

Repeat steps (3) and (4) until k Steiner points are added; that is, $\sum l_i=k$ .

(6)

Organize the $l_i$ Steiner points by evenly partition edge $e_i=(u,v)$ for $1\le i\le n-1$ .

It is easy to check that the time complexity of the above algorithm is $O(n\log n+kn)$ . In fact, one can check that the first step can be implemented in $O(n\log n)$ time when combining the Prim's algorithm with a Delaunay triangulation [13] for the input n terminals in the Euclidean plane. Obviously, step (2) only uses linear time. Steps (3) and (4) run in linear time and constant time, respectively, and the two steps loops for k times, so steps (3) and (4) run in $O(kn)$ in total. Step (6) can be implemented in $O(n+k)$ time locating the position of added Steiner points.

Following Lemmas 4 and 5, we get a $\sqrt{\mathrm{3}}$ -approximation algorithm running in $O(n\log n+kn)$ time (see Theorem 6).

Theorem 6.

Algorithm restrict-EuclidBST-ratio- $\sqrt{\mathrm{3}}$ outputs a bottleneck Steiner tree with the length of each edge at most $\sqrt{\mathrm{3}}$ the optimum in $O(n\log n+kn)$ time for the restricted Euclidean bottleneck Steiner tree problem when only degree ≥3 Steiner points are not allowed to be adjacent in the optimal solution.

3. $\sqrt{2}$ -Approximation Algorithm

In this section, we try to improve the performance ratio to decrease the gap between current approximation ratio $\sqrt{\mathrm{3}}$ and the inapproximate result $\sqrt{\mathrm{2}}$ indicated by Theorem 2. By introducing a structure called 3-restricted Steiner tree and the notion for spanning tree of a 3-hypergraph, we find the restrict-EuclidBST problem can be approximated within $\sqrt{\mathrm{2}}$ .

Definition 7.

A Steiner tree is called a 3-restricted Steiner tree if each of its full component spans at most 3 terminals.

Similar to Lemma 4, supposing that a and b are terminals in the Euclidean plane, we use $ab$ to denote the segment and $\left|ab\right|$ to denote the length of segment $ab$ . We also assume the length of the longest edge in the optimal bottleneck Steiner tree is 1.

Lemma 8.

Given n terminals set P and integer k, suppose T is an optimal bottleneck Steiner tree interconnecting P with at most k Steiner points for the restrict-EuclidBST problem; there exists a 3-restricted Steiner tree $T^{\prime }$ for P with the same number of Steiner points as T such that the length of each edge in $T^{\prime }$ is at most $\sqrt{\mathrm{2}}$ .

Proof.

For the restrict-EuclidBST problem, since Steiner points with degree at least 3 are not possible to be adjacent in the optimal bottleneck Steiner tree, according to the notion of full Steiner component introduced above, the optimal bottleneck Steiner tree T can always be decomposed into the union of its edge-disjoint full Steiner components, each of which is either a star-like subtree with a Steiner point of degree at least 3 as center while other Steiner points are all of degree 2 (see Figure 1) or just a line-segment path connecting two terminals with $l\ge 0$ intermediate degree-2 Steiner points (see Figure 2).

For a star-like subtree $T_s$ centered at some Steiner point v with at least 4 terminals, we can modify the tree step by step to a tree with the degree of the center Steiner point v 3 and make sure that the length of each edge in the modified tree is at most $\sqrt{\mathrm{2}}$ .

Suppose v is the center of $T_s$ and its degree is 4 (the case of degree more than 4 can be processed similarly); let a, b, c, and d be the four terminals around v (see Figure 4); then, $\angle avb$ , $\angle bvc$ , $\angle cvd$ , and $\angle dva$ form 360°. Thus, at least one of $\angle avb$ , $\angle bvc$ , $\angle cvd$ , and $\angle dva$ is at most 90°. Without loss of generality, assuming $\angle avb$ ≤90° and $\left|vb\right|\le \left|va\right|$ , that is, the length of $vb$ is no longer than $va$ , it is easily seen that

$$\begin{array}{ll}& \left|ab\right|=\sqrt{{\left|va\right|}^{\mathrm{2}}+{\left|vb\right|}^{\mathrm{2}}-\mathrm{2}\left|va\right|·\left|vb\right|\cos \angle avb}\\ \le \sqrt{\mathrm{2}}\left|va\right|.\end{array}$$

(2)

Let x be the number of Steiner points degree-2 (not including v) on segment $va$ ; then, we can directly connect a and b and add x equally spaced degree-2 Steiner points to it, and the length of each edge in the segment $ab$ is at most $\sqrt{\mathrm{2}}$ because the length of segment $va$ is at most $x+1$ (remember the length of each edge on the path from a to v is at most 1), removing the longer segment $va$ results in the decrease of degree of v by 1. Figure 4 illustrates the transformation procedure.

The above procedure transforms the star-like subtree $T_s$ into a 3-restricted Steiner subtree with the same number of Steiner points as $T_s$ and the length of each edge is at most $\sqrt{\mathrm{2}}$ . As to the line-segment path, no work is need because its edge length is at most 1. Union all the 3-restricted Steiner subtrees and line-segment paths at their sharing common terminals forming a 3-restricted Steiner tree $T^{\prime }$ with same number of Steiner points as the optimal tree T and the length of each edge in $T^{\prime }$ is at most $\sqrt{\mathrm{2}}$ . This completes the proof.

Figure 4

Decrease the degree of v from 4 to 3.

By introducing the notion of 3-hypergraph, we reduce our computation of an optimal 3-restricted Steiner tree into the computation of a minimum spanning tree in a weighted 3-hypergraph. The notion of 3-hypergraph, weighted 3-hypergraph, and spanning tree of a 3-hypergraph can be found in [6]. The following theorem indicates that there is a polynomial time randomized algorithm for computing the minimum spanning tree in a weighted 3-hypergraph [14].

Lemma 9.

There exists a randomized algorithm for the minimum spanning tree problem for weighted 3-hypergraphs, with probability at least 0.5, running in $poly(n,w_{max})$ time, where n is the number of nodes in the hypergraph and $w_{max}$ is the largest weight of edges in the hypergraph.

To introduce our algorithm we must first construct a weighted 3-hypergraph; the weight of an edge of the hypergraph is defined as the number of Steiner points; consequently, a bound B should be given to determine the number of Steiner points, where B is the length of the longest edges in an optimal solution. Apparently, it is not easy to find the exact value of B efficiently since restrict-EuclidBST problem is NP-hard. However, we can guess the length by enumerating all possibilities. The following procedure finds a value $B^{\prime }$ that is at most $(1+\epsilon )B$ for any $\epsilon >0$ .

• (i)

Run Algorithm restrict-EuclidBST-ratio- $\sqrt{\mathrm{3}}$ to get an upper bound X of B.

(ii)

Try $X/\sqrt{\mathrm{3}},(X/\sqrt{\mathrm{3}})(\mathrm{1}+\epsilon ),(X/\sqrt{\mathrm{3}})(\mathrm{1}+\mathrm{2}\epsilon ),\dots ,X$ as $B^{\prime }$ , where ε is a positive number.

Thus, we can adopt $B^{\prime }=(1+\epsilon )B$ as the estimate length of the longest edge in an optimal bottleneck Steiner tree. It is ready for us to construct weighted 3-hypergraph $H_3=(V,F;W)$ from the terminal set P. The process of construction of a 3-hypergraph is described as follows.

3-Hypergraph $H_3=(V,F;W)$ .

• (i)

Vertex set $V=P$ .

(ii)

Edge set $F=\left\{\left(a,b\right)\hspace{0.17em}|\hspace{0.17em}a\in P\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and}\mathrm{\hspace{0.17em}\hspace{0.17em}}b\in P\right\}\cup \left\{\left(a,b,c\right)\hspace{0.17em}|\hspace{0.17em}a\in P,\hspace{0.17em}\hspace{0.17em}b\in P\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and}\mathrm{\hspace{0.17em}\hspace{0.17em}}c\in P\right\}$ .

(iii)

The weight for an edge $f=(a,b)\in F$ is the smallest number of Steiner points added to f such that the lengths of the resulting edges are at most $\sqrt{\mathrm{2}}{B}^{\prime }$ . If an edge length is at most $\sqrt{2}{B}^{\prime }$ , then its weight is 0; generally, $w(f)=⌈\left|ab\right|/\sqrt{\mathrm{2}}{B}^{\prime }⌉-\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{1}$ .

(iv)

The weight for an edge $f=(a,b,c)\in F$ is the smallest number of Steiner points used to connect a, b, and c possibly via a degree 3 Steiner point v such that the length of each edge thus obtained is at most $\sqrt{\mathrm{2}}{B}^{\prime }$ (see below for details).

Computing the Weight for $f=(a,b,c)$ . Without loss of generality, suppose $\left|ab\right|\le \left|bc\right|\le \left|ca\right|$ ; then, $w=\min \{⌈\left|ab\right|/\sqrt{2}{B}^{\prime }⌉+⌈\left|bc\right|/\sqrt{2}{B}^{\prime }⌉-2,k\}$ is an upper bound of the weight of f; here, k is the given number of Steiner points. Let $l_a$ , $l_b$ , and $l_c$ be the number of Steiner points degree-2 in the segments $va$ , $vb$ , and $vc$ such that $w(f)=l_a+l_b+l_c+1$ is minimized. We can enumerate all the possibilities to guess the values of $l_a$ , $l_b$ , and $l_c$ to find $w(f)$ . Obviously, this can be done in $O(k^3)$ time since k is the upper bound for $l_a$ , $l_b$ , and $l_c$ . For each possibility of $l_a$ , $l_b$ , and $l_c$ , we only have to test if the three circles centered at a, b, and c with radii $l_a\times \sqrt{\mathrm{2}}{B}^{\prime }$ , $l_b\times \sqrt{\mathrm{2}}{B}^{\prime }$ , and $l_c\times \sqrt{\mathrm{2}}{B}^{\prime }$ share a common point. This can be done in $O(1)$ time.

Lemma 10 (see [6]).

Testing whether three circles share a common a point can be done in $O(1)$ time.

It is easy to see that the construction of a 3-hypergraph can be finished in $O(n^3{k}^3)$ time with given bound $B^{\prime }$ because the number of edges of the hypergraph is in $O(n^3)$ and the weight of an edge can be computed in $O(k^3)$ time. The algorithm in [14] can be introduced to compute a minimum spanning for the constructed hypergraph. Our $\sqrt{\mathrm{2}}$ -approximation algorithm can be described as below (Ratio- $\sqrt{2}$ Algorithm for Restrict-EuclidBST Problem).

Algorithm (restrict-EuclidBST-ratio- $\sqrt{2}\hspace{0.17em}\hspace{0.17em}(P,n,k,\epsilon )$ ).

• (1)

Call restrict-EuclidBST-ratio- $\sqrt{\mathrm{3}}\hspace{0.17em}\hspace{0.17em}(P,n,k)$ to get the upper bound for optimal length X.

(2)

Try each of $B^{\prime }\leftarrow X/\sqrt{\mathrm{3}}$ ,  $(X/\sqrt{\mathrm{3}})(\mathrm{1}+\epsilon )$ ,  $(X/\sqrt{\mathrm{3}})(1+2\epsilon ),\dots ,(X/\sqrt{\mathrm{3}})(1+\lceil (\sqrt{\mathrm{3}}-1)/\epsilon \rceil \times \epsilon )$ .

• (a)

  Construct the weighted 3-hypergraph $H_3(V,F;W)$ according to $B^{\prime }$ .

• (b)

  Call the polynomial randomized algorithm in [14] to compute a minimum spanning tree $T^{\prime }$ for $H_3(V,F;W)$ .

• (c)

  if $w(T^{\prime })\le k$ , then exit the loop.

(3)

Replace every edge f of the minimum spanning tree $T^{\prime }$ with a Steiner subtree.

• (a)

  If $f=(a,b)$ , replace f with a line-segment path connecting a and b by adding $w(f)$ equal spaced Steiner points.

• (b)

  If $f=(a,b,c)$ , replace f with a star-like subtree centered at a common point v of circles centered at a, b, and c with radii $l_a\times \sqrt{\mathrm{2}}{B}^{\prime }$ , $l_b\times \sqrt{\mathrm{2}}{B}^{\prime }$ , and $l_c\times \sqrt{\mathrm{2}}{B}^{\prime }$ , adding $l_a$ , $l_b$ , and $l_c$ intermediate Steiner points with an even partition to segment $va$ , $vb$ , and $vc$ , respectively, where $l_a$ , $l_b$ , and $l_c$ are determined in the process of construction of hypergraph $H_3(V,F;W)$ .

(4)

Output the resulting 3-restricted Steiner tree.

Lemmas 8 and 9 indicate the existence of a randomized approximation algorithm for the restrict Euclidean bottleneck Steiner tree problem. Combined with algorithm restrict-EuclidBST-ratio- $\sqrt{\mathrm{2}}$ , we have the following Theorem.

Theorem 11.

Algorithm restrict-EuclidBST-ratio- $\sqrt{\mathrm{2}}$ outputs a bottleneck Steiner tree with the length of each edge at most $\sqrt{2}+\epsilon$ (for any $\epsilon >0$ ) the optimum with probability at least 0.5 in time $(\mathrm{1}/\epsilon )\times poly(n,k)$ , for the restricted Euclidean bottleneck Steiner tree problem when only degree ≥3 Steiner points are not allowed to be adjacent in the optimal solution.

4. Conclusion

We studied a restricted bottleneck Steiner tree problem in the Euclidean plane which require only degree ≥ 3 Steiner points are not allowed to in the optimal bottleneck Steiner tree. The problem studied in this paper is much close to the general problem. We first show that the restricted problem is MAX-SNP hard and cannot be approximated within ratio $\sqrt{2}$ in polynomial time unless $P=\text{NP}$ . Then, with the notion of full Steiner component, we transformed the computation of a bottleneck Steiner tree problem into a Steinerized spanning problem, which is polynomial time $\sqrt{\mathrm{3}}$ -approximation algorithm and then improve the ratio to $\sqrt{\mathrm{2}}+\epsilon$ for any given $\epsilon >0$ , by presenting a polynomial time randomized approximation algorithm, which is almost optimal to the restricted problem.

Our algorithm can be used to improve the lifetime of wireless sensor networks by minimizing the length of the longest distance between sensors in the network.