-Net Approach to Sensor -Coverage

Coverage problems have been extensively studied in the context of sensor networks (see, e.g., [1‐4]). The objective of sensor coverage problems is to minimize the number of active sensors, to conserve energy usage, while ensuring that the required region is sufficiently monitored by the active sensors. In an over-deployed network we can also seek -coverage, in which every point in the area is covered by at least sensors. This ensures higher fault tolerance, robustness, and improves many operations, among which position detection and intrusion detection.

The -coverage problem is trivially NP-complete, and hence we focus on designing approximation algorithms. In this paper, we extend the well-known -net technique to our problem and present an -factor approximation algorithm, where is the size of the optimal solution. The classical greedy algorithm for set cover [5], when applied to -coverage, delivers an -approximation solution, where is the number of target points to be covered. Our approximation algorithm is an improvement over the greedy algorithm, since our approximation factor of is independent of and of the number of target points.

Instead of solving the sensor's -coverage problem directly, we consider a dual problem, the -hitting set. In the -hitting set problem, we are given sets and points, and we look for the minimum number of points that "hit" each set at least times (a set is hit by a point if it contains it). Brönnimann and Goodrich were the first [6] to solve the hitting set using the -net technique [7]. In this paper, we introduce a generalization of -nets, which we call -nets. Using -nets with the Brönnimann and Goodrich algorithm's [6], we can solve the -hitting set, and hence the sensor's -coverage problem. Our main contribution is a way of constructing -nets by random sampling. A recent Infocom paper [8] uses -nets to solve the -coverage problem. However we believe that their result is fundamentally flawed (see Section 2.1 for more details). So, to the best of our knowledge, we are the first to give a correct extension of -nets for the -coverage problem.

Paper Organization

The rest of the paper is organized as follow. The -coverage problem is introduced in Section 2. Section 2.1 contains detailed discussion about related work. The -net approach is presented in Section 3.

We start by defining the sensing region and then we will define the -coverage problem with sensors. In the literature, sensing regions have been often modeled as disks. In this paper, we consider sensing regions of general shape, because this reflects a more realistic scenario.

Definition 1 (sensing region).

The sensing region of a sensor is the area "covered" by a sensor. Sensing regions can have any shape that is closed, connected, and without holes, as in Figure 1(a). Often, sensing regions are modeled as disks as in Figure 1(b), but we consider more general shapes.

Definition 2 (target points).

Target points are the given points in the 2D plane that we wish to cover using the sensors.

-SC Problem

Given a set of sensors with fixed positions and a set of target points, select the minimum number of sensors, such that each target point is covered (is contained in the selected sensing region) by at least of the selected sensors.

For simplicity, we have defined the above -SC problem's objective as coverage of a set of given target points. However, as discussed later, our algorithms and techniques easily generalize to the problem of covering a given area.

Example 1.

Suppose we are given 4 sensors and 20 points as in Figure 2(a), and we want to select the minimum number of sensors to 2-cover all points. In this particular example, 2 sensors are not enough to 2-cover all points. Instead, 3 sensors suffice, as shown in Figure 2(b).

In this section, we present an algorithm based on the classical -net technique, to solve the -coverage problem. The classical -net technique is used to solve the hitting set problem, which is the dual of the set cover problem. The -SC problem is essentially a generalization of the set cover problem—thus, we will extend the -net technique to solve the corresponding generalization of the hitting set problem.

In this paper, we studied the -coverage problem with sensors, which is to select the minimum number of sensors so that each target point is covered by at least of them. We provided an -approximation, where is the number of sensors in an optimal solution. We introduced a generalization of the classical -net technique, which we called -net. We gave a method to build -nets based on random sampling. We showed how to solve the sensor's -coverage problem with the Brönnimann and Goodrich algorithm [6] together with our -nets. We believe to be the first one to propose this extension.

As a future work, we would like to extend this technique to directional sensors. A directional sensor is a sensor that has associated multiple sensing regions, and its orientation determines its actual sensing region. The -coverage problem with directional sensors is NP-complete and in [15] we proposed a greedy approximation algorithm. We believe that the use of -nets can give a better approximation factor for this problem.

This appendix contains the proof that when is equal to the size of the -hitting set, then , iterations of the doubling process are enough to retrieve the optimal -hitting set. This proof follows the lines of the one in [6], but with the additional parameter .

Theorem 4.

If , iterations of the internal for loop of Algorithm 1 are sufficient to find a -hitting set.

Proof.

Initially . The set selected at the end of the internal for loop satisfies , because the algorithm found a weighted -net. Doubling the weights of the elements in adds a total of new weight to the system. So grows at most by a factor at each iteration. Then, after iterations

Let be the optimal -hitting set. Initially we have . Since is a -hitting set, there are least elements of in each set of . So for any possible set chosen in step 11, there are at least elements of that are doubled. By the convexity of the function , the increase of is minimal if the doublings are spread out over the elements of as evenly as possible. So after iterations, we have

Since the weights are positive and , . We need to find the largest for which

can be true. Taking the log

and solving for

where we used the fact that for . Since the expression on the RHS is for any possible value of , the theorem follows.

This appendix contains the proof of Theorem 2, which is an extension of the -net theorem of Haussler and Welz [7]. As explained in Section 3.2, the two challenges in generalizing the random-sampling technique are that (i) sampling with replacement cannot be used, and (ii) weights must be part of the sampling process. Our contribution is a new method to obtain weighted -nets in which (i) we sample a subset of points at once (without duplicates), and (ii) we include the weights directly in the sampling process.

We start by proving three lemmas, and then we will prove Theorem 2. Let be as given by (1), and let be the subset of points randomly picked from as described in Theorem 2. After picking , pick another set (for the purpose of the below analysis) in the same way as . We now define two events

where .

Intuitively, is the event that does not -hit some set , but has a "large" intersection with the set (also remember that is disjoint from ). Note that is a lower bound the average size of the intersection of and (as computed below).

Lemma 1.

It holds that

Proof.

, because if happens, then happens too. From the definition of conditional probability

it suffices to show that .

Let (where the 's are pairwise different). Since happens, there is some set s.t. and . Therefore, is at least the probability that, for this , .

Let be the random variable (r.v.)

Each subset (resp., ) is picked with probability proportional to the sum of the weights of its elements, and each element can appear in (resp., ) subsets (because these are the ways of putting every other elements in the remaining positions). So the probability of picking one element depends only on its weight, and not on the other elements, which means that the elements are pairwise independent. So we have that

where is a function that returns the weight of given set, which is defined as the sum of the weights of its elements.

Let . Clearly . We have

To bound the deviation from the expectation, we use Chebyshev's inequality

Since 's are independent, the covariance is zero. So we get

where we used the fact that for the 0-1 r.v. , .

Applying Chebyshev's inequality

where in the last inequality we used the fact that

Finally we have that

Lemma 2.

It holds that where .

Proof.

The experiment of picking and can be viewed in an alternative way. Pick a subset of size at random (each subset is picked with probability proportional to the sum of the weights of its elements). Then, pick as a subset of of size at random (again with probability proportional to the sum of the weights of its elements). Finally, let . Note that this view is equivalent because the probability of picking any subset is the same as before, (similarly for ). This can be verified as follow. We are going to compute the probability of picking a certain subset in both cases. In order to do this, we need to compute the sum of all possible sets of size . Among all possible sets of size , each element appears in exactly of them (because these are the ways of putting every other element in the remaining positions). Now, it is not necessary to know exactly in which set each element gives its contribution, but it is enough to know that it appears a total of times. So, the sum of weight of all possible sets of size is . Then

Now we are going to compute the probability of picking a subset containing . This requires to determine the sum of the weights of all subsets of size that contain . appears in of them (as these are the number of ways of putting any other element in the remaining positions), and it gives a contribution of in each of them. Any other element can appear in any of the remaining positions, for a total of times (because fixed any element, the remaining elements can be placed in any of the remaining positions). So we get that

We also need to compute the probability of picking from

This requires to know , which can be computed as

So,

Finally, it is easy to verify that

Let , with , and define . Since and are disjoint, , and then is equivalent to . If , then does not happen, and it does not happen if either. Suppose that , where , then we can pick as follow. We select elements among the points outside the intersection with

and the remaining elements anywhere else

Their product can be bounded in the following way:

where in the last inequality we used the fact that

which can be proved by induction. The base case, , is trivial. Assuming that the formula is valid for , we get

where in the last inequality we used the fact that .

Using this fact, we can bound . Recall that happens only if . So

For two sets s.t. and , the events and are the same. This is because the occurrence of depends only on the intersection . The number of sets s.t. is unique at most by Corollary 1 below. Then

Lemma 3.

For any set system , with and VC-dimension , , where .

Proof.

See [16].

Given a set system , for any subset of the points , let denote the projection of onto , that is, the set .

Corollary 1.

For any set system , if , then has VC-dimension , which implies .

Finally, we prove the main theorem.

In this appendix we present a simple extension of [12] to build small weighted -nets for disks. The original construction in [12] easily extends to -nets by replacing with . The proof presented here is simplified respect to the original one, because we consider only disks, instead of pseudodisks.

The underlining idea is to pick points that are spaced apart, which hit all large enough disks. The strategy that we are going to use is to draw "colored" disks that contain a fixed number of points, and select points only on the border of the colored disks. The position and the size of colored disks depend on the input points, but not on the input disks. All colored disks, but one, will have exactly input points, where . Each input point gets the color of the colored disks that covers it or remains uncolored if uncovered. After placing the colored disks, we compute a Dealaunay triangulation (DT) of the colored points. DT will have uni-colored, bi-colored, and tri-colored triangles. Triangles will have uni-colored and bi-colored edges. Let us define some terminology (see Figure 3).

Definition 7 (corridor; hall; sides; ends; corners).

We start by describing the algorithm for the unweighted case, and we will show how to add weights afterwords. We are given , a family of disks, and a set of points in the plane. For simplicity assume that the points are in general position (i.e., no three points are collinear, and no four points are cocircular). Let define (the reason for this will be clear soon). Let be disjoints subsets of constructed in the following manner. From the boundary of , "bite off" subsets of of size with the following properties.

Now, consider the internal points of , that are not part of any disk . We are going to draw the largest number of disks of size to cover the internal points. Specifically, let be a maximal collection of disjoint subsets of satisfying

At this point, we have a total of disks . For each , , color the points of with color , and call the disk defining color , or colored disk . Let be the set of colored points, and call the points in colorless. Let DT be the Dealaunay triangulation of the set of colored points . Break each corridor into a minim number of subcorridors, that is, subchains of the chain of triangles that form , so that each subcorridor contains at most colorless points. Let be the set of the corners of all subcorridors. Clearly . We are going to show that is a the -net for that is, any disk of that contains points of also contains points of . This construction is summarized in Algorithm 2.

Algorithm 2: Small -nets for disks.

First of all note that colorless points can only be in corridors and halls (because unicolored triangles are contained in the corresponding color-defining disks). Also, we can observe that any disk containing no colored points contains less than points of . In fact, from the maximality of the construction, there cannot be colorless disks with points. Than we claim what follows.

Claim

There are at most corridors in DT, and

Proof.

See [12]. Note that, since all are disjoint, and all but maybe one contain points, so .

We now prove the -net theorem for disks.

Theorem 5 ( -net theorem for disks).

Algorithm 2 creates a -net of size for , where is a set of points in non-D-degenerate position (i.e., no three points are collinear, and no four points are cocircular), and D is a family of disks.

Proof.

By claim we have that the size of is . So we only need to show that contains at least points in each input disk of size at least .

First of all, the case is already proved in [12], so we focus on the case of .

For a generic input disk of size at least , we are going to compute the minimum number of corners contributed by each intersecting region (colored disk, subcorridor, or hall), while assuming that it has the largest possible intersection. Also, we will pay attention not to count the same corner multiple times. If a colored disk is completely contained in an input disk, it will contribute for the biggest number of corners. So we should only consider colored disks that intersect the boundary of the input disk. We claim that the minimum contribution is given when the boundary of an input disk intersects an alternation of colored disks and corridors. In this case we should count 1 corner, for each colored disk/corridor. The only case in which (a part of) the boundary of the input disk does not intersect any colored disk is when it is contained inside a corridor. But this can only happen if there is a colored disk inside the input disk, but we already argued that this will give a higher contribution. The following is an upper bound on the number of intersecting points. There can be points for the colored disk, plus another points for the subcorridor on the side of the corner that we are counting, plus another points for the hall adjacent to them. This means that for points there is at least 1 corner. We are considering input disks of size at least , and this implies that there are at least points in each disk.

Finally, we consider the weighted case. The construction is similar to the unweighted one, with the only difference that the colored disks contain points, where is the sum of the weights of all points. It is easy to see that the proof follows through.