1 Introduction

Sensors have been extensively used in many areas, such as battlefield monitoring, traffic control, manufacture process management, and disaster detection. In the study of these applications, coverage and connectivity are two fundamental issues affecting sensors’ performances. Each sensor has a coverage area and a communication area. Those two areas are often disks. The radius of the coverage disk is called the coverage radius while the radius of the communication disk is called the communication radius. A sensor s is connected to another sensor s ′ if s ′ lies in the coverage area of s, i.e., the distance between s and s ′ is smaller than or equal to the communication radius of s. A set of sensors is said to be connected if they induce a (strongly) connected (directed) graph.

Given a region Ω and a set of homogenous sensors, \(\mathcal {S}\), find a minimum connected subset of sensors to cover region Ω. This problem is called the minimum connected sensor cover (MCSC) problem. In this paper, we study the MCSC problem.

Initially, the MCSC problem was studied by Gupta et al. [10]. They showed that this problem is NP-hard and proposed a greedy algorithm with approximation performance ratio O(rlnn) where n is the number of sensors and r is the link radius of the sensor network, i.e., the least upper bound for the hop-distance, in communication network, between two sensors with overlapping coverage disks. Zhang and Hou [16] gave a better algorithm in a special case that the communication radius is at least twice of the coverage. In this special case, the sensor coverage of a connected region induces the connectivity of sensors. This property is generalized by Zhou et al. [17] to the m-coverage and the m-connectivity that if every point of a connected region is covered by at least m sensors, then those sensors would induce an m-connected network. More relationships between the sensor coverage and the sensor connectivity can be found in [15]. Alam and Haas [1] studied the MCSC problem in three-dimensional sensor networks.

Funke et al. [7] modified the MCSC problem by allowing sensors to vary their coverage radius. With variable coverage radius and communication radius, Zhou et al. [18] designed a polynomial-time approximation with performance ratio O(logn). Ghosh and Das [9] designed a greedy algorithm without analysis on approximation performance ratio. The improvement of the bound O(rlogn) of Gupta et al. [10] was obtained by Wu et al. [14] in 2013. They designed two algorithms. The first one has approximation performance ratio O(log3nloglogn) independent from r, and the second one has approximation performance ratio O(r), independent from n. The existence of these two approximations suggests a conjecture that there exists a polynomial-time constant-approximation for the MCSC problem.

In both algorithms of Wu et al. [14], the first stage is to replace a given target area by a set of target points. Clearly, it is better to use less number of target points in this replacement. Indeed, reducing this number would have impact in efficiency of those approximation algorithm. In this paper, we make the following contributions.

  • First, we propose a new method to replace a target region by target points. The new method is able to reduce the number of target points significantly.

  • Second, we will give a new analysis for algorithms given in [14]. The new analysis will use some new results appearing in the literature and hence give improved approximation performance ratios.

2 Replace target region by target points

For a target region Ω, how do we find a set of target points, \(\mathcal {P}\) such that a subset of sensors, \(\mathcal {S}^{\prime }\) covers Ω if and only if \(\mathcal {S}^{\prime }\) covers all target points in \(\mathcal {P}\)?

Wu et al. [14] described two methods for selecting such a set of target points; both have size O(n 2) where n sensors are given for our consideration. One of them is to arbitrarily select one point from each small area obtained from partitioning the target area by sensing disks of all given n sensors (see Fig. 1). This method was also mentioned by earlier publications [2–5].

Fig. 1
figure 1

Choose one target point from each small area

Full size image

In this section, we would like to propose a new idea based on this method.

For a sensor, its coverage area is a disk. Therefore, our problem can be formulated as follows: Given a set \(\mathcal {D}\) of n disks with possibly different radius, and a target region Ω, find a set \(\mathcal {P}\) of target points such that a subset \(\mathcal {D}^{\prime }\) of \(\mathcal {D}\) covers target region Ω if and only if \(\mathcal {D}^{\prime }\) covers all target points in \(\mathcal {P}\). (For possible application in heterogeneous sensor systems, we allow disks to have different radius.)

Suppose all disks in \(\mathcal {D}\) partition Ω into m small areas. In each small area, we choose a target point; hence, denote as a 1,a 2,...,a m respectively. Two target points a i and a j are said to be adjacent if two small areas represented by a i and a j have a boundary in common. This boundary must be a piece of the boundary of a disk \(D \in \mathcal {D}\), denoted by ∂ D. If a i lies outside of D and a j lies inside of D, then we add an arc from a i to a j . The directed graph constructed in this way is denoted by G (Fig. 2).

Fig. 2
figure 2

Graph G

Full size image

Lemma 1

G is acyclic.

Proof

In fact, consider an arc (a i ,a j ). By the construction of arc (a i ,a j ), there exists a disk \(D \in \mathcal {D}\) such that a i lies outside of D and a j lies inside of D. Note that every arc crossing ∂ D has a direction from outside to inside of D. Therefore, no path exists from a j to a i . Thus, no cycle exists in G. □

A point a i is called a source node if every arc incident to a i is going out from a i . Let S be the set of all source nodes in G as shown as circled nodes in Fig. 2. It is easy to know that S≠∅ since clearly, m≥1 and if a 1 is not a source node, then there exists an arc \((a_{i_{2}},a_{1})\). If \(a_{i_{2}}\) is not a source node, then there exists an edge \((a_{i_{3}},a_{i_{2}})\). This process ends if either a source node or a cycle contradicting to acyclic property of G is found.

The following important fact has been established about the set S of all source nodes.

Theorem 1

A disk subset \(\mathcal {D}^{\prime }\) of \(\mathcal {D}\) covers target area Ω if and only if \(\mathcal {D}^{\prime }\) covers all points in S.

Proof

The proof of “only if” part is trivial. We can also show the proof of “if” part within a few lines as follows: By contradiction, suppose \(\mathcal {D}^{\prime }\) does not cover Ω. We take disks in \(\mathcal {D} - \mathcal {D}^{\prime }\) one by one and add to \(\mathcal {D}^{\prime }\) until \(\mathcal {D}^{\prime }\) becomes a maximal subset not covering Ω, that is, \(\mathcal {D}^{\prime }\) does not cover Ω and however, for any \(D \in \mathcal {D}-\mathcal {D}^{\prime }\), \(\mathcal {D}^{\prime } \cup \{D\}\) covers Ω. In this case, the uncovered area of Ω cannot be partitioned by any disk in \(\mathcal {D}\) and hence contains only one a i which must be a source node outside of all disks in \(\mathcal {D}^{\prime }\), contradicting to the assumption that \(\mathcal {D}^{\prime }\) covers all points in S. □

It is clear that |S| is much smaller than m. However, we do not have a good analysis for |S| instead of the following conjecture.

Conjecture 1

If ∂Ω, the boundary of given target area has o(n 2 ) intersection points with n disks, then the expected number of source nodes is o(n 2 ).

3 Approximations for MCSC

Based on the results in last section, we will consider to cover target points in \(\mathcal {P}\) instead of target region Ω. In other words, the MCSC problem is a special case of the minimum hitting set problem defined as follows: Given a collection \(\mathcal {P}\) of subsets of a finite set \(\mathcal {S}\) and a graph G with vertex set \(\mathcal {S}\), find a subset \(\mathcal {S}^{\prime }\) of \(\mathcal {S}\) such that \(\mathcal {S}^{\prime }\) induces a connected subgraph of G and hits all subsets in \(\mathcal {P}\), that is, for any \(a \in \mathcal {P}, a \cap \mathcal {S}^{\prime } \neq \emptyset \). Here, each target point \(a \in \mathcal {P}\) represents the set of sensors each with coverage area covering a.

The minimum connected hitting set problem can be easily reduced to the group Steiner tree problem defined as follows: Consider a graph G=(V,E) with positive edge length w:E→R +. Given k subsets of vertices, g 1,...,g k , find the shortest tree on a vertex subset which hits every g i , i=1,...,k.

To see the reduction, set \(V=\mathcal {S}\), w(s,s ′)=1 for every edge (s,s ′) of G and \(\{g_{1},...,g_{k}\}=\mathcal {P}\). Since every edge has length one, the total edge-length of a tree on a vertex subset \(\mathcal {S}^{\prime }\) is equal to \(|\mathcal {S}^{\prime }|-1\), the objective function value of the mi- nimum connected hitting set problem minus one. Note that for positive numbers a>b>1, we have inequality a/b≤(a−1)/(b−1). It follows that the following lemma holds.

Lemma 2

If the group Steiner tree problem has a polynomial-time ρ-approximation, then so does the minimum connected hitting set problem.

Garg et al. [8] showed that for any ε>0, there exists a polynomial-time algorithm that can produce an approximation solution for the group Steiner tree problem such that with probability 1−ε, the solution is O(log2nloglognlogk)-approximation where n is the number of vertices and k is the number of groups in input. One of the computation steps in this algorithm has been improved by Fakcharoenphol et al. [6] from running time O(lognloglogn) to O(logn). Therefore, we now have the following.

Lemma 3

For any 0<ε<1, there exists a polynomial-time approximation algorithm for the group Steiner tree problem, which with probability 1−ε produces a O(log2nlogk)-approximation.

Note that when we map the MCSC problem into the group Steiner tree problem, each group corresponds to a target point. Therefore, k = O(n 2). Hence, O(logk) = O(logn). By Lemmas 2 and 3, the following holds.

Theorem 2

For any 0<ε<1, there exists a polynomial-time approximation for the MCSC problem such that with probability 1−ε, this algorithm produces a O(log3n)-approximation solution.

Next, we present a O(r)-approximation for the MCSC problem that is a little different from the one given by Wu et al. [14]. First, we note that Min et al. [12] gave a polynomial-time 3-approximation for the ST-MSN (Steiner Tree with Minimum Number of Steiner Points) problem as follows: Given a unit disk graph G and a subset P of nodes, find a Steiner tree interconnecting nodes in P to minimize the number of Steiner points.

Lemma 4

There exists a polynomial-time 3-approximation for the ST-MSN problem.

In [13], we can found a PTAS for the minimum sensor cover problem defined as follows: Given a set of sensors, \(\mathcal {S}\) and a set of target points, \(\mathcal {P}\), find a minimum subset of sensors, \(\mathcal {S}^{\prime }\) to cover all target points.

Lemma 5

There exists a PTAS for the minimum sensor cover problem.

Suppose \(\mathcal {S}^{\prime }\) is a (1 + ε)-approximation for the minimum sensor cover problem. On communication network G which is a unit disk graph with node set \(\mathcal {S}\), we compute a 3-approximation \(\mathcal {D}\) for the ST-MSN problem with input point set \(P=\mathcal {S}^{\prime }\). Then, \(\mathcal {D} \cup \mathcal {S}^{\prime }\) is a connected sensor cover with performance described as follows.

Theorem 3

\(\mathcal {D} \cup \mathcal {S}^{\prime }\) is a polynomial-time approximation for the MCSC problem with performance ratio 3r+1+(3r−2)ε.

Proof

Suppose \(\mathcal {S}^{*}\) is an optimal solution for the MCSC problem. For each sensor s ′ in \(\mathcal {S}^{\prime }\), find a sensor in \(\mathcal {S}^{*}\) such that s and s ′ cover a target point in common. Then we can add a path with length at most r to connect them. Those \(|\mathcal {S}^{\prime }|\) paths plus \(\mathcal {S}^{*}\) form a feasible solution for the ST-MSN problem. Therefore,

$$|\mathcal{D}| \leq 3(|\mathcal{S}^{*}|+ (r-1)|\mathcal{S}^{\prime}|).$$

Note that \(|\mathcal {S}^{\prime }| \leq (1+\varepsilon )|\mathcal { S^{*}}|\). Thus, we have

$$|\mathcal{D} \cup \mathcal{S}^{\prime}| \leq (3r+1+(3r-2)\varepsilon)|\mathcal{S}^{*}|.$$

When the communication radius is at least twice of the coverage radius, we have r=1 and hence the following holds.

Corollary 1

When the communication radius is at least twice of the coverage radius, there exists a polynomial-time (4+ε)-approximation for the MCSC problem for any 0<ε<1.

4 Discussion

Recently, Huang et al. [11] found a polynomial-time O(C 2)-approximation for the MCSC problem where C is the ratio of the coverage radius over the communication radius. This result gives a new evidence that there exists a polynomial-time constant-approximation fo the MCSC problem, which is a conjecture of Wu et al. [14].