INTRODUCTION:

The rapid progress of wireless communication and embedded micro-sensing MEMS technologies has made wireless sensor networks possible. Such environments may have many inexpensive wireless nodes, each capable of collecting, storing, and processing environmental information, and communicating with neighboring nodes. In the past, sensors are connected by wire lines. Today, this environment is combined with the novel ad hoc networking technology to facilitate inter-sensor communication [20, 25]. The flexibility of installing and configuring a sensor network is thus greatly improved. Recently, a lot of research activities have been dedicated to sensor networks, including design issues related to the physical and media access layers [23, 31, 34] and routing and transport protocols [3, 5, 8]. Localization and positioning applications of wireless sensor networks are discussed in [2, 21, 27].

Since sensors may be spread in an arbitrary manner, one of the fundamental issues in a wireless sensor network is the coverage problem. The purpose of this paper is to review the recent progress in this direction. Given a sensor network, the coverage problem in general is to determine how well the sensing field is monitored or tracked by sensors.

In the literature, this problem has been formulated in various ways. Even in computational geometry, some coverage-related solutions can be found. Although solutions to those problems cannot be directly applied to wireless sensor networks, it is still worth to study those problems to establish some theoretical backgrounds on the coverage problem. Indeed, a lot of works have been dedicated to the coverage-related problems in wireless sensor networks in the last few years. These include the surveillance and exposure of sensor networks, and the concerns of coverage versus connectivity issues when deploying a sensor network. Through this survey, we intend to provide a comprehensive study and comparison among those works.

On the other hand, some works are targeted at particular applications, but the central idea is still related to the coverage issue. For example, to reduce sensors’ on-duty time, those sensors that share the common sensing region and task may be turned off to conserve energy and thus to extend the network lifetime. To do this, we have to determine which sensors to be turned off and how to schedule sensors’ on-duty time such that no blind point will appear after turning off some nodes. Several works addressing these issues will be discussed.

This paper is organized as follows. Section 2 studies relevant geometric problems. Section 3 and Section 4 present several works aimed at solving coverage-related problems in wireless sensor networks. Several coverage preserving energy-conserving protocols are then presented in Section 5. Section 6 draws our conclusions.

Related Geometric Problems:

In this section, we review two computational geometric problems which are related to the coverage problem in a sensor network. The first problem is the Art Gallery Problem [18]. Imagine that the owner of an art gallery wants to place cameras in the gallery such that the whole gallery is thief-proof. There are two questions to be answered in this problem: (i) how many cameras are needed, and (ii) where these cameras should be deployed. Every point in the gallery should be monitored by at least one camera. Cameras are assumed to have a viewpoint of 360 degrees and rotate at an infinite speed. Moreover, a camera can monitor any location as far as nothing is in the middle, i.e., a line-of-sight exists. The number of cameras used should be minimized. The gallery is usually modeled as a simple polygon on a 2D plane. A simple solution to this problem is to divide the polygon into non-overlapping triangles and place one camera in each of these triangles. By triangulating the polygon, it has been shown that any simple polygon can be guarded by (n/3) cameras, where is the number of triangles in the polygon. This is also the best result in the worst case [18]. An example of triangulating a simple polygon is shown in Fig. 1 and two cameras are sufficient to cover the gallery. Although this problem can be solved optimally in a 2D plane, it is shown to be NP-hard when being extended to a 3D space [19].

Figure 1: An example of triangulating a polygon and a possible deployment of cameras. Circles represent positions of cameras.

Another related problem in computational geometry is the circle covering problem [30], which is to arrange identical circles on a plane that can fully cover the plane. Given a fixed number of circles, the goal is to minimize the radius of circles. This issue is discussed in [9, 16, 17] for the covering of a rectangle. The coverings with less than or equal to five circles and seven circles can be done optimally [9]. For example, an optimal covering of seven circles is shown in Fig. 2. Reference [16] shows the coverings of six and eight circles and presents a new covering with eleven circles by an approach based on the simulated annealing. The coverings with up to 30 circles are discussed in [17].

Figure 2: An example of an optimal covering with 7 circles. The radius of each circle is about 0.2742918.

The above geometrical computation problems are similar to the nature of coverage problems in wireless sensor networks: we need to know whether an area is sufficiently covered and monitored. The number of sensors is important in terms of cost. These results also provide some theoretical backgrounds to the coverage issue. However, there are several reasons which make solutions of geometric problems not directly applicable to wireless sensor networks. The first reason is that the assumptions are different. For example, a camera in the Art Gallery Problem can see infinite distance unless there is an obstacle. On the contrary, sensors in fact have their maximal sensing ranges. Besides, a sensor network usually has no fixed infrastructure and its topology may even change at any time. Thus, many decisions have to be made in a distributed manner. However, most geometric problems are solved in a centralized manner.

Surveillance and Exposure:

Below, we introduce several coverage-related works aimed at wireless sensor networks. In this kind of work [1, 11, 12, 13, 14, 15, 28], coverage is regarded as a metric to evaluate the quality of service (surveillance) provided by a particular sensor network. Between a given pair of points in the sensing field, the key idea is to find a path connecting these two points which is best or worst monitored by sensors when an object traverses along the path. It is believed that such a path could reflect the best or worst sensing ability provided by the sensor network.

Reference [13] defines the maximal breach path and the maximal support path as paths on which the distance from any point to the closest sensor is maximized and minimized, respectively. Polynomial-time algorithms are proposed to find such paths. The key idea is to use the Voronoi diagram and the Delaunay triangulation of sensor nodes to limit the search for the optimal paths in each case. The Voronoi diagram is formed from the perpendicular bisectors of lines that connect two neighboring sensors, while the Delaunay triangulation is formed by connecting nodes that share a common edge in the Voronoi diagram. Examples of the Voronoi diagram and Delaunay triangulation are shown in Fig. 3.

Because the line segments of the Voronoi diagram of sensors have the maximal distance to the closest sensors, the maximal breach path must lie on the line segments of the Voronoi diagram. To find the maximal breach path, each line segment is given a weight equal to its minimum distance to the closest sensor. The proposed algorithm then performs a binary search between the smallest and largest weights. In each step, a breadth-first-search is used to check the existence of a path from the source point to the destination point using only line segments with weights that are larger than the search criterion. If a path exists, the criterion is increased to further restrict the lines considered in the next search iteration. Otherwise, the criterion is decreased. An example of the maximal breach path is shown in Fig. 3(a). Similarly, since the Delaunay triangulation produces triangles which have minimal edge lengths among all possible triangulations, the maximal support path must lie on the lines of the Delaunay triangulation of sensors. To find the maximal support path, the weights of line segments of the Delaunay triangulation are assigned the lengths of the line segments. The rest of the search steps are the same as above. An example of the maximal support path is shown in Fig. 3(b).

Figure 3: Examples of (a) the Voronoi diagram and the maximal breach path, and (b) the Delaunay triangulation and the maximal support path. S and D are the source and destination points.

Figure 4: An example of exposure.

Distinct from the breach and support paths, the concept of time should be included to reflect more realistic probability of a moving target being sensed since the sensing ability of sensors can be improved as the allotted sensing time (exposure) increases. An example is shown in Fig. 4, A is a sensor and an object moves form point S to point D with a constant speed. There are three possible paths. Although path 3 is the farthest path from A, it is also the longest path. The object moving along this path would take longer time, thus tracked by A longer. In contract to path 3, path 2 is the shortest path. If the object moves along this path, it is tracked by A for the least period of time. However, path 2 is closest to A and the sensing intensity would be strongest. As a result, path 1 might be the least exposure path among these three paths.

How to find the minimal exposure and maximal exposure paths that take into account the durations that an object is monitored by sensors is addressed in [11, 14, 15, 28]. The minimal exposure path, which can be thought of as the worst coverage of a sensor network, is first introduced in [14]. The exposure for an object in the sensor field during the interval along a path is defined as:

Where, is the sensor field intensity measured at location from the closest sensor or all sensors in the sensor field F, and is the element of arc length. A numerical approximation approach is proposed in [14] to solve the problem of finding the minimal exposure path. The approach is to divide the sensor network region into grids and force the path to only pass the edges of girds and/or the diagonals of grids. Each line segment is assigned a weight equal to the exposure of this segment. Then a single-source-shortest-path algorithm is used to find the minimal exposure path.

Reference [15] further discusses how to compute the exposure of a sensor network in a distributed manner. The key idea is to use the Voronoi diagram to partition the sensor field and then each sensor is responsible for the calculation of exposure in its region. Inside each region, the above gird approximation is used. Another localized algorithm is proposed in [28], which can reduce the computational complexity of [15]. In addition, [28] further introduces the concept of maximal exposure path, by following which the total exposure to the sensors is maximized, i.e., the best covered path by sensors. This paper proves that finding such a path is NP-hard by reducing the problem to the longest path problem [6] and then proposes some heuristic solutions.

Coverage and Connectivity:

Figure 5: Determining the perimeter-coverage of a sensor S₁’s perimeter.

In this section, we discuss some works that consider the coverage and connectivity of sensor networks [7, 10, 22, 29, 35]. Each sensor is assumed to have a fixed sensing region and a fixed communication range, both of which are modeled as disks. The goal is to achieve certain sensing coverage and/or communication connectivity requirements.

In [10], the coverage problem is formulated as a decision problem. Given a set of sensors deployed in a target area, the problem is to determine if the area is sufficiently k-covered, in the sense that every point in the target area is covered by at least k sensors, where k is a given parameter. Rather than determining the coverage of each location, the proposed approach looks at how the perimeter of each sensor’s sensing range is covered, thus leading to an efficient polynomial-time algorithm. Specifically, the algorithm tries to determine whether the perimeter of a sensor under consideration is sufficiently covered. By collecting this information from all sensors, a correct answer can be obtained.

An example of determining the perimeter-coverage of a sensor’s perimeter is shown in Fig. 5. Each sensor first determines which segments of its perimeter are covered by its neighboring nodes. As shown in Fig. 5(a), segments , , and of sensor S₁’s perimeter are covered by three of its neighboring nodes. Those segments are then sorted in an ascending order on the line segment , as shown in Fig. 5(b). By traversing the line segment , the perimeter-coverage of the sensor can be determined. In this example, the perimeter-coverage of S₁ from 0 to b is one, from b to a is two, from a to d is one, from d to c is two, and from c to is one. Reference [10] proves that as long as the perimeters of sensors are sufficiently covered, the whole area is sufficiently covered. The solution proposed in this paper can be easily translated to a distributed protocol where each sensor only needs to collect local information to make its decision. The result can be applied to unit and non-unit disk sensing regions, and can even be extended to irregular sensing regions of sensors. How to use the results for discovering insufficiently covered areas, for conserving energy, and for supporting coverage of hot spots are also discussed.

For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Reference [29] proposes another solution to determine if a target area is k-covered and further studies the relationship between coverage and connectivity. To determine the coverage level, this work looks at how intersection points between sensors' sensing ranges are covered. It claims that a region is k-covered by a set of sensors if all intersection points between sensors and between any sensor and the boundary of this region are at least k-covered. However, this solution may incur higher computational complexity compared to [10]. For the network communication connectivity, it claims that if a region is k-covered, then the sensor network is k-connected as long as those sensors' communication ranges are no less than twice their sensing ranges.

Based on the above two properties, a Coverage Configuration Protocol (CCP) that can provide different degrees of coverage and meanwhile maintain communication connectivity is presented in [29] when the communication ranges are no less than twice their sensing ranges. Initially, all sensors are in the active state. If an area exceeds the required degree of coverage, redundant nodes will find themselves unnecessary and switch to the sleep state. A sensor is unnecessary to stay active if all the intersection points inside its sensing circle are at least k-covered by other nodes in its neighborhood. A sleeping node also periodically wakes up and enters the listen state. In the listen state, the sensor evaluates whether it is necessary to return to the active state.

If the communication ranges are less than twice the sensing ranges, reference [29] proposes to integrate CCP with SPAN [4] to provide both sensing coverage and communication connectivity. SPAN is a connectivity-maintaining protocol which can turn off unnecessary nodes such that all active nodes are connected through a communication backbone and all inactive nodes are directly connected to at least one active node. Reference [29] proposes that an inactive node should become active following rules of SPAN or CCP. An active node will turn to sleep if it satisfies neither SPAN’s nor CCP’s wake up rules.

Reference [7] investigates the coverage and connectivity issues from another point of view. When a spatial query is issued to the sensor network to request the data of interest in a geographical region, we may like to select the smallest subset of sensors which are connected and are sufficient to cover the region. The proposed solution is a greedy algorithm which recurrently selects a path of sensors that is connected to an already selected sensor and then adds these sensors into the selected subset until the given query region is completely covered. The greedy rule of the algorithm is to select a path of sensors who can cover the largest uncovered query region at each stage. Fig. 6 shows an example with two consecutive stages of the algorithm. Fig. 6(b) is resulted from (a) by selecting sensors of path since consists of sensors and who together cover the largest uncovered region.

Coverage-Preserving and Energy-Conserving Protocols:

Since sensors are usually powered by batteries, sensors' on-duty time should be properly scheduled to conserve energy. If some nodes share the common sensing region and task, then we can turn off some of them to conserve energy and thus extend the lifetime of the network. This is feasible if turning off such a node still provides the same “coverage” (i.e., the provided coverage is not affected). An example is shown in Fig. 7(a). The sensor f can be put into sleeping mode since all its sensing area is covered by the other nodes. Sensor g satisfies this condition too and can go to sleeping mode. However, f and g are not allowed to be turned off at the same time; otherwise a blind point, which is a region not covered by any sensor, could appear, as shown in Fig. 7(b). As a result, sensors not only need to be checked if they satisfy certain eligibility rules but also need to be carefully scheduled.

Reference [24] proposes a heuristic to select mutually exclusive sets of sensor nodes such that each set of sensors can provide a complete coverage of the monitored area. They claim that this problem is a NP-complete problem by reducing it to the minimum cover problem. The key idea of the proposed heuristic is to find out which sensors cover fields that are less covered by other sensors and then avoid including those sensors into the same set. Also targeted at turning off some redundant nodes, [33] proposes a probe-based density control algorithm to put some nodes in a sensor-dense area to a doze mode to ensure a long-lived, robust sensing coverage. In this solution, nodes are initially in the sleeping mode.

After a sleeping node wakes up, it broadcasts a probing message within a certain range and then waits for a reply. If no reply is received within a pre-defined time period, it will keep active until it depletes its energy. The coverage degree (density) is controlled by sensor's probing range and wake-up rate. However, this probing-based approach has no guarantee of sensing coverage and thus blind points could appear.

A coverage-preserving node scheduling scheme is presented in [26] to determine when a node can be turned off and when it should be rescheduled to become active again. It is based on an eligibility rule which allows a node to turn itself off as long as other neighboring nodes can cover its sensing area. After evaluating its eligibility for off-duty, each sensor adopts a back-off scheme to prevent the appearance of blind points. If a node is eligible for off-duty, it will delay a random back-off time before actually turning itself off. During this period of time, if it receives any message from its neighbors requesting to go to sleep, it marks the sender as an off-duty node and evaluates its eligibility. If the eligibility still holds after the back-off time, this node broadcasts a message to inform its neighbors, waits for a short period of time, and then actually turns itself off. A sleeping node will periodically wake up to check if it is still eligible for off-duty and then decide to keep sleeping or go back to on-duty.

However, the solution in [26] may lead to excess energy consumption. An example is shown in Fig. 8. Based on the eligibility rule proposed in [26], a sensor only regards a node whose sensing range can cover the sensor as a neighboring node. In Fig. 8(a), sensor c is eligible for off-duty since its sensing region is covered by its neighboring nodes a, b and d. In contrast to the above case, in Fig. 8(b), sensor c is not eligible for off-duty since sensor b is not regarded as a neighboring node of c. According to the eligibility rule of [26], c cannot be turned off. In fact, c’s sensing region is fully covered by sensors a, b and d, thus leading to excess energy consumption.

Another node scheduling scheme is proposed in [32]. In this scheme, the time axis is divided into rounds with equal duration. Each sensor node randomly generates a reference time in each round. In addition, the whole sensing area is divided into grid points which are used to evaluate whether the area is sufficiently covered or not. Each sensor has to join the schedule of each grid point covered by itself based on its reference time such that the grid point is covered by at least one sensor at any moment of a round. Then a sensor's on-duty time in each round is the union of schedules of grid points covered by the sensor. However, this scheme may suffer from the time synchronization problem in a large-scale sensor network.

CONCLUSION:

In this survey, we have presented some comparative studies of the coverage-related problem in wireless sensor networks. We first study several coverage-related geometric problems. Then, an extensive survey of works studying the coverage problem targeted at wireless sensor networks is presented. Next, we discuss several energy-conserving protocols related to coverage issues. As to future research, distributed protocols are needed to resolve these coverage issues in a wireless sensor networks. Sensing regions are typically assumed to be circles. In practice, they may be irregular in shape, or even follow a probabilistic model. In several works, the communication distance of sensors is assumed to be much longer than the sensing distance of sensors. This is not necessarily true and deserves further investigation.

REFERENCES:

1. S. Adlakha and M. Srivastava. Critical density thresholds for coverage in wireless sensor networks. In IEEE Wireless Communications and Networking Conf. (WCNC), 2003, pp. 1615 –1620.

2. P. Bahl and V. N. Padmanabhan. RADAR: An in-building RF-based user location and tracking system. In IEEE INFOCOM, 2000, pp. 775–784.

3. D. Braginsky and D. Estrin. Rumor routing algorithm for sensor networks. In ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), 2002.

4. B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris. Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. ACM/Kluwer Wireless Networks, 2002, Vol. 8, No. 5.

5. D. Ganesan, R. Govindan, S. Shenker, and D. Estrin. Highly resilient, energy efficient multipath routing in wireless sensor networks. ACM Mobile Comput. and Commun. Review, 2001, Vol. 5, No. 4.

6. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of Np-Completeness. W H Freeman & Co., 1979.

7. H. Gupta, S. R. Das, and Q. Gu. Connected sensor cover: Self-organization of sensor networks for efficient query execution. In ACM International Symp. on Mobile Ad Hoc Networking and Computing (MobiHOC), 2003, pp. 189–200.

8. W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocols for wireless microsensor networks. In Hawaii International Conf. on Systems Science (HICSS), 2000.

9. A. Heppes and J. B. M. Melissen. Covering a rectangle with equal circles. Period. Math. Hung., Vol. 34, 1996, pp. 65–81.

10. C.-F. Huang and Y.-C. Tseng. The coverage problem in a wireless sensor network. In ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), 2003, pp. 115–121.

11. Q. Huang. Solving an open sensor exposure problem using variational calculus. Technical Report WUCS-03-1, Washington University, Department of Computer Science and Engineering, St. Louis, Missouri, 2003.

12. X.-Y. Li, P.-J. Wan, and O. Frieder. Coverage in wireless ad hoc sensor networks. IEEE Trans. Comput., Vol. 52, No. 6, 2003, pp. 753–763.

13. S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In IEEE INFOCOM, 2001, pp. 1380–1387.

14. S. Meguerdichian, F. Koushanfar, G. Qu, and M. Potkonjak. Exposure in wireless ad-hoc sensor networks. In ACM International Conf. on Mobile Computing and Networking (MobiCom), 2001, pp. 139–150.

15. S. Meguerdichian, S. Slijepcevic, V. Karayan, and M. Potkonjak. Localized algorithms in wireless ad-hoc networks: location discovery and sensor exposure. In ACM International Symp. On Mobile Ad Hoc Networking and Computing (MobiHOC), 2001, pp. 106–116.

16. J. B. M. Melissen and P. C. Schuur. Improved coverings of a square with six and eight equal circles. Electronic Journal of Combinatorics, Vol. 3, No. 1, 1996.

17. K. J. Nurmela and P. R. J. Ostergard. Covering a square with up to 30 equal circles. Re- search Report A62, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, June 2000.

18. J. O’Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, 1987.

19. J. O’Rourke. Computational geometry column 15. International Journal of Computational Geometry and Applications, Vol. 2, No. 2, 1992, pp. 215–217.

20. G. J. Pottie and W. J. Kaiser. Wireless integrated network sensors. Commun. ACM, Vol. 43, No. 5, 2000, pp. 51–58.

21. A. Savvides, C.-C. Han, and M. B. Strivastava. Dynamic fine-grained localization in ad-hoc networks of sensors. In ACM International Conf. on Mobile Computing and Networking (MobiCom), 2001, pp. 166–179.

22. S. Shakkottai, R. Srikant, and N. Shroff. Unreliable sensor grids: coverage, connectivity and diameter. In IEEE INFOCOM, 2003, pp. 1073 – 1083.

23. E. Shih, S.-H. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, and A. Chandrakasan. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks. In ACM International Conf. on Mobile Computing and Networking (MobiCom), 2001, pp. 272–287.

24. S. Slijepcevic and M. Potkonjak. Power efficient organization of wireless sensor networks. In IEEE International Conf. on Communications (ICC), 2001, pp. 472–476.

25. K. Sohrabi, J. Gao, V. Ailawadhi, and G. J. Pottie. Protocols for self-organization of a wireless sensor network. IEEE Personal Commun., Vol. 7, No. 5, 2000, pp. 16–27.

26. D. Tian and N. D. Georganas. A node scheduling scheme for energy conservation in large wireless sensor networks. Wireless Commun. and Mobile Comput. (WCMC), Vol. 3, 2003, pp. 271–290.

27. Y.-C. Tseng, S.-P. Kuo, H.-W. Lee, and C.-F. Huang. Location tracking in a wireless sensor network by mobile agents and its data fusion strategies. In International Workshop on Information Processing in Sensor Networks (IPSN), 2003.

28. G. Veltri, Q. Huang, G. Qu, and M. Potkonjak. Minimal and maximal exposure path algorithms for wireless embedded sensor networks. In ACM International Conf. on Embedded Networked Sensor Systems (SenSys), 2003, pp. 40–50.

29. X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill. Integrated coverage and connectiv- ity configuration in wireless sensor networks. In ACM International Conf. on Embedded Networked Sensor Systems (SenSys), 2003, pp. 28–39.

30. R. Williams. The Geometrical Foundation of Natural Structure: A Source Book of Design, pp. 51–52. Dover, New York, 1979.

31. A. Woo and D. E. Culler. A transmission control scheme for media access in sensor networks. In ACM International Conf. on Mobile Computing and Networking (MobiCom), 2001, pp. 221–235.

32. T. Yan, T. He, and J. A. Stankovic. Differentiated surveillance for sensor networks. In ACM International Conf. on Embedded Networked Sensor Systems (SenSys), 2003, pp. 51–62.

33. F. Ye, G. Zhong, S. Lu, and L. Zhang. PEAS: A robust energy conserving protocol for long-lived sensor networks. In International Conf. on Distributed Computing Systems (ICDCS), 2003.

34. W. Ye, J. Heidemann, and D. Estrin. An energy-efficient MAC protocol for wireless sensor networks. In IEEE INFOCOM, 2002, pp. 1567–1576.

35. H. Zhang and J. C. Hou. Maintaining sensing coverage and connectivity in large sensor networks. In NSF International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks, 2004.

Received on 16.08.2011 Accepted on 30.09.2011

Research J. Engineering and Tech. 2(4):Oct.-Dec. 2011 page188-194