Perimeter Coverage Scheduling in Wireless Sensor Networks Using Sensors with a Single Continuous Cover Range

In [1‐4], we studied how to identify a set of sensors to cover the perimeter of a large object with the minimum size and minimum cost. Since sensors are battery-powered and the battery is unlikely to be rechargeable, every sensor network has a functional network lifetime. In this work, we are particularly interested in how to schedule the sensors so as to maximize the network lifetime in the perimeter coverage problem. To the best of our knowledge, the lifetime maximization issue in the perimeter coverage problem was first studied in [5]. In [5], we adopted several heuristic energy-related scheduling objectives as cost metrics. Different sets of sensors are identified using these objectives to monitor the target at different times. The energy-related objectives include the minimization of energy of each sensor set found, the minimization of the battery cost which is defined as the reciprocal of the remaining battery capacity of the sensor, the hybrid algorithm, and so forth. The heuristic scheduling algorithms developed based on the adoption of different energy-related objectives are then compared through extensive simulations.

Unlike that of [5], in this paper, we study the problem from the theoretical perspective and make the following contributions: (1) We formally prove that the perimeter coverage problem is NP-hard in general, but polynomial time solution exists in some special cases. (2) We identify the sufficient conditions for a perimeter coverage scheduling algorithm to be a -approximation solution. (3) We develop a distributed scheduling algorithm that generates (size of the minimum cover) number of messages. The schedules generated must have a lifetime that is at least half of the optimal one. (4) We simulate the proposed algorithm and compare it with the optimal schedules.

The paper is organized as follows. Section 2 discusses the related work on the other coverage problems. Section 3 describes the notations, problem statement, and the properties of the problem. Section 4 studies the special cases in which polynomial time optimal solutions exist. A formal proof of NP-hardness of this problem in general is given in Section 5. The sufficient condition for a perimeter coverage scheduling algorithm to be a -approximation solution is discussed in Section 6. Our proposed distributed -approximation solution which requires (size of the minimum cover) number of messages is also described. Section 7 presents the simulation results of our proposed algorithm by comparing it with the optimal schedules. Finally, we conclude our work with some of the future directions in Section 8.

Extensive research has been carried out to extend the lifetime of sensor networks [6‐8]. In this study, network lifetime is defined as the length of the time period that the target area or target objects are being covered continuously. One way to extend network lifetime is to schedule the sensor nodes' activities to alternate between active and sleep modes so that only a minimal number of sensors are turned on at any time [9]. Tian and Georganas [10] propose a distributed scheduling algorithm which turns off the sensors with a cover area completely replaceable by the cover areas of their neighboring nodes. Yan et al. [11] adopt a similar concept. However, instead of considering whether the sensing area of a sensor is covered by its neighbors, the sensor considers a certain number of grid points inside the area. Later, Hsin and Liu [12] propose a randomized algorithm and a coordinated algorithm so as to schedule the sleeping times of the nodes. In the randomized algorithm, a sensor will sleep with a certain probability. In the coordinated algorithm, a sensor will sleep only when its sensing area is completely covered by others. On the other hand, Huang and Tseng [13] study the criteria for determining whether the sensing area of a sensor is covered by different sensors simultaneously. Huang et al. [14] propose several decentralized energy-conserving and coverage-preserving protocols so as to solve the area coverage problem. Other than those suggested above which aim at full area coverage, the fractional coverage problem, in which only a certain fraction of the target area has to be covered, has also been considered in [15]. In [15], Ye et al. first calculate the ideal density for providing a certain fraction of coverage. Then, each sensor is activated with a probability. This probability is determined based on the ratio between the current density and the ideal density calculated. On the contrary, Wang and Kulkarni [16] investigate similar problem in another direction, and they show that sacrificing a certain fraction of the target area can significantly increase the network lifetime. Ren et al. [17] study the relationship between the fraction of coverage and the quality of the object detection capability. As a result, the network can be deployed with a fraction of coverage that can achieve an acceptable quality.

Cardei et al. [18] study the target coverage problem where a target object has to be monitored by at least one sensor at any moment and each sensor can monitor multiple target objects if the objects fall within the sensor's sensing area. They formulate this target coverage problem as a set coverage problem, and propose both centralized approximation and distributed heuristic solutions. In [19], Liu et al. study similar problem. However, they assume that each sensor can only monitor one target object at any moment even if multiple targets fall within the sensing area of a sensor. Unfortunately, the cover formed by using these approaches may not be connected as some nodes in the cover may not have any route back to the sink node. Therefore, Zhao and Gurusamy [20] further investigate the connected target coverage problem. They prove that this problem is NP-complete, and develop a centralized approximation solution and a distributed heuristic solution. Thai et al. [21] propose an -approximation distributed algorithm to solve the target coverage problem, where denotes the number of sensors in the network. They organize the sensors into nondisjoint cover sets in which each set can cover all the target objects with high probability. They formally show that their solution is an approximation solution if the initial battery capacity of all the sensors is the same, but the approximation ratio is worsen if the initial battery capacity of the sensors is different. On the other hand, Calines and Ellis [22] suggest an -approximation algorithm. Their solution achieves the same approximation ratio no matter the initial battery capacity of all the sensors is the same or not. Unfortunately, these algorithms cannot guarantee that all the targets are covered all the time.

Another related problem is the barrier coverage problem. In [23], Kumar et al. consider the barrier coverage problem. They assume that an intruder can be detected by a sensor if it falls within its sensing area. They consider the scenario in which an intruder will be detected by at least sensors if she goes through a thin strip of area (known as belt) no matter where her start point and her end point are. In [23], Kumar et al. propose a polynomial time mechanism to determine whether there exists barrier coverage. On the other hand, Kumar et al. [24] study the optimal sleeping schedule on the barrier coverage problem. They transform the problem to a maximum flow problem so that it can be solved optimally in a centralized manner. Chen et al. further propose a localized algorithm in [25]. They first study the critical conditions for the existence of barrier coverage locally. The sensor can then turn into sleep mode when it determines that barrier coverage can be provided by its neighbors. Chen et al. further study how to find and measure the quality of barrier coverage accurately in [26]. Later, Liu et al. [27] discover that it may not be possible to guarantee barrier coverage by using the approach in [25] under some special situations. They identify the critical conditions for the existence of a strong barrier coverage and devise an efficient technique to guarantee coverage. Other than that, Saipulla et al. [28] study the barrier coverage problem where the sensors are dropped from air. They suggest that the sensors are deployed along a line with a certain offset by using this deployment strategy. They show that the performance achievable by using this method is much better than that of using the random deployment strategy which is generally assumed in most of the literatures.

We assume that the object is a very big one and we want the whole perimeter to be monitored continuously. Each sensor has a certain sensing range. It can monitor a point such that the distance between the point and the sensor is less than or equal to the sensing range. The area that the sensor can monitor, called sensing area, is a circle. The object that falls within the sensing area of a sensor is said to be monitored by the sensor. It is assumed that each sensor can only monitor a single continuous portion of the perimeter, and no sensor can monitor the whole perimeter as shown in Figure 1. Sensors are randomly distributed around the big object. The set of sensors that can cover a portion of the target object is denoted as . Also, we use to denote the number of sensors in , that is, .

In this section, we describe how to find a schedule when is a proper sensor set, such that there is no sensor whose cover range is contained inside another sensor. We consider two scenarios: uniform battery scenario and nonuniform battery scenario. In the following, we drop the superscript in notations for simplicity if the context is clear.

In this section, we would like to prove that the perimeter coverage scheduling problem is NP-hard if is a general set of sensors. We first consider the situation where , . To prove the perimeter coverage scheduling problem is NP-hard, a reduction is constructed from the -coloring problem on a circular-arc graph, which was first shown to be NP-hard in [37], to the perimeter coverage scheduling problem. Here, denotes a perimeter scheduling problem instance with a set of sensors , and the maximum lifetime achievable on is .

Before we go into details about the transformation, we first describe the -coloring problem on a circular arc graph . A circular arc in is denoted as , where denotes the anti-clockwise endpoint, and denotes the clockwise endpoint of a circular arc. In other words, a circular arc is open on the clockwise endpoint. We further assume that all the endpoints are distinct. Arcs and are neighbors if the arcs overlap. In the -coloring problem, we would like to determine whether colors are enough to assign a color to each arc such that no two neighbor arcs share the same color.

We further introduce some notations so as to define the problem formally. Here, we use to denote the number of circular arcs in . Therefore, there are endpoints in . We sort the endpoints in ascending order, and denote them as , where . A pair of consecutive endpoints are denoted as . We use to denote the set of arcs covering , that is, , . Let denote the set of circular arcs with Color . Since the sensors in are neighbors of each other, at least colors are needed.

Given any instance of the -coloring problem in the circular arc graph, where is an integer larger than or equal to , an instance of the perimeter coverage scheduling problem can be constructed from as follows.

Consider Arcs , , in Figure 8; Sensors , , are put into according to (1) in Figure 9. Suppose = 3. Consider the range ; according to (2), Sensor is put in . Similarly, Sensors , , , , , , , , , , , and are put into as shown in Figure 9. As a result, we know that . Since , . Therefore, .

Lemma 2.

is -colorable if and only if the maximum lifetime on is .

Proof.

"⇒" part: if is -colorable, we can put the arcs into different partitions according to their colors. We show that covers can be formed in by using the following approach:

The corresponding formed, , are covers, because ; there is a sensor in covering . At the same time, , . Therefore, , for any . Since is and , by Property 2, the maximum lifetime is upper bounded by . Hence, the maximum lifetime can be achieved by activating each cover for unit of time. This results in . Therefore, if is -colorable, then the maximum lifetime on is .

" " part: If the maximum lifetime on is and the corresponding schedule is , then there must exist a mutually disjoint cover set with covers since each sensor has a battery lifetime of unit. Without loss of generality, these covers are . In other words, and , where .

Hence, with the existence of covers, partitions on can be formed by the following approach:

, , . Note that we do not need to consider the sensors in , where and .

Since is constructed in such a way that every , where , is exactly covered by sensors, if there exist covers, then every is exactly covered by sensor in each cover. Therefore, by constructing , , according to the above description, neighbor arcs must fall into different color partitions. As a result, , , forms a color partition and so is -colorable if the maximum lifetime on is .

By Lemma 2, Theorem 1 can then be developed.

Theorem 1.

The perimeter coverage scheduling problem is NP-hard.

Since the perimeter coverage problem is NP-hard, it is not likely to have a polynomial time solution. The problem can be formulated as a mixed integer programming problem, and solved by some existing software. However, a centralized approach is not appropriate. Therefore, we develop a distributed approximation solution with a small overhead. Before describing our algorithm, we first show that any scheduling algorithm that selects a proper cover in each cycle is a -approximation algorithm.

For comparison, we have implemented several algorithms. The first algorithm is the optimal solution found by transforming the maximum lifetime scheduling problem to the Multicommodity Network Flow problem, and solved by AMPL-CPLEX [38], which is denoted as Optimal in our figures. The second algorithm is the one proposed in this paper, which is denoted as Proposed algorithm in the figures. The third algorithm is the one proposed in [5], which is denoted as Round-based algorithm in the figures. In this algorithm, a minimum size cover, known as , is found to monitor the target object in each monitoring cycle until no more MC can be found. The fourth algorithm is denoted as Single-MC in the figures. In this algorithm, an MC is found and this MC is activated until a sensor is running out of energy. Afterwards, another MC is found and activated again. This process continues until no more MC can be found.

In our simulations, we considered an area of grids grids. Each grid takes up an area of unit and has a certain probability of containing a sensor. A grid that is partially/completely occupied by the target does not have any sensor. This probability is known as thesensor availability probability, and we use to denote it. If the grid contains a sensor, the sensor is located at the center of the grid. This is similar to the simulation environment considered in [5]. Each sensor has a sensing range ; The target object is located at the center with the object radius of . For uniform initial battery case, each sensor has units of energy. In the nonuniform battery case, each sensor has a mean value units of energy. The uniform case is denoted as , while the nonuniform case is denoted as in the figures. Each monitoring cycle is assumed to take up units of energy, and each message takes up unit of energy if transmission cost is counted.

In this paper, we study the perimeter coverage scheduling problem. We found that this problem is solvable in polynomial time under some special sensor configurations. However, this problem is NP-hard in general. We realize that the selection of a proper cover in each cycle leads to a -approximation solution. We then propose a simple distributed -approximation solution with size of the minimum cover number of messages, and we demonstrate its effectiveness through simulations.

In the future, we plan to study the perimeter coverage scheduling issues on the scenario where a sensor can monitor multiple continuous portions of the perimeter on the target object instead of a single continuous portion. In [29], we have proposed a distributed maximum number of cover ranges per sensor approximation solution on the problem of finding the minimum size and minimum cost set of sensors to cover the perimeter of the whole target object. To the best of our knowledge, no approximation solution has been developed on the scheduling problem up to now and the approximation ratio is likely to be larger than maximum number of cover ranges per sensor . Therefore, we would like to develop a distributed approximation solution to tackle this issue in the coming future.