Connected k-Coverage Protocols for Densely Deployed Wireless Sensor Networks

Connected k-Coverage Protocols for Densely Deployed Wireless Sensor Networks

Habib M. Ammari (Hofstra University,USA)
DOI: 10.4018/978-1-61520-701-5.ch010
OnDemand PDF Download:
No Current Special Offers


In this chapter, we study duty-cycling to achieve both k-coverage and connectivity in highly dense deployed wireless sensor networks, where each location in a convex sensor field (or simply field) is covered by at least k active sensors while maintaining connectivity between all active sensors. Indeed, the limited battery power of the sensors and the difficulty of replacing and/or recharging batteries on the sensors in hostile environments require that the sensors be deployed with high density in order to extend the network lifetime. Also, the sensed data originated from source sensors (or simply sources) should be able to reach a central gathering node, called the sink, for further analysis and processing. Thus, network connectivity should be guaranteed so sources can be connected to the sink via multiple communication paths. Finally, wireless sensor networks suffer from scarce energy resources. A more practical deployment strategy requires that all the sensors be duty-cycled to save energy. With duty-cycling, sensors can be turned on or off according to some scheduling protocol, thus reducing the number of active sensors required for k-coverage and helping all sensors deplete their energy as slowly and uniformly as possible. We also extend our discussion to connected k-coverage with mobile sensors as well as connected k-coverage in a three-dimensional deployment area. Furthermore, we discuss the applicability of our protocols to heterogeneous wireless sensor networks.
Chapter Preview


Recent advances in miniaturization, low-cost and low-power circuit design, and wireless communications have led to a new technology, called wireless sensor networking. A wireless sensor network consists of tremendous number of low-cost, low-power, and tiny communication devices, named sensors. Like nodes (or computers, laptops, etc) in traditional wireless networks, such as mobile ad hoc networks (MANETs), the sensors have data storage, processing, and communication capabilities. Unlike MANET nodes, the sensors have an extra functionality related to their sensing capability. Precisely, the sensors are densely deployed in a physical environment for monitoring specific phenomena. Wireless sensor networks can be used for a wide variety of applications dealing with monitoring (health environments monitoring, seism monitoring, etc), control, and surveillance (battlefields surveillance). Sensors sense some phenomenon in the environment and perform in-network processing on the sensed data at intermediate nodes before sending their results to a central gathering component, called the sink.

Sensing coverage is an essential functionality of wireless sensor networks. However, it is also well-known that coverage alone in wireless sensor networks is not sufficient because data originated from source sensors are not guaranteed to reach the sink for further analysis. Thus, network connectivity should also be considered for a network to function correctly. In wireless sensor networks, coverage and connectivity have been jointly addressed in an integrated framework. While coverage is a metric that measures the quality of surveillance provided by a network, connectivity provides a means to the source sensors to report their sensed data to the sink. Some real-world applications, such as intrusion detection, may require high degree of coverage, and hence large number of sensors to enable accurate tracking of intruders. For such highly dense deployed and energy-constrained sensors, it is necessary to duty-cycle them to save energy. Thus, the design of coverage configuration protocols for wireless sensor networks should minimize the number of active sensors to guarantee the degree of coverage of a field required by an application while maintaining connectivity between all active sensors. Hence, the first challenge is the determination of the number of sensors required to remain active to k-cover a sensor field. Given that sensors have limited battery power and wireless sensor networks are generally randomly and hence highly dense deployed, the second challenge is the design of an efficient scheduling protocol that decides which sensors to turn on (active) or off (inactive) for k-coverage of a field.

The objective of this chapter is to study the problem of connected k-coverage in wireless sensor networks, which can be stated as follows:

Connected k-Coverage Problem: Given a field, a set S of sensors, and k ≥ 3, select a minimum subset SminS of sensors such that each point in the field is k-covered, all sensors in Smin are connected and have the highest remaining energy.

Because the problem of selecting a minimum subset of sensors to k-cover a field is NP-hard (Gupta et al., 2006), we propose energy-efficient centralized, clustered, and distributed approximation algorithms to solve the connected k-coverage problem using as small number of sensors as possible.

The remainder of this chapter is organized as follows. First, we present the major challenges in the design of connected k-coverage protocols, specify the network model, and review related work. Second, we discuss connected k-coverage protocols for two-dimensional and three-dimensional wireless sensor networks. Third, we describe future and emerging trends. Then, we conclude the chapter.



In this section, we discuss the major challenges that face the design of connected k-coverage protocols for wireless sensor networks. Then, we specify the network model for the design of our own protocols for connected k-coverage configurations in densely deployed wireless sensor networks. Moreover, we present a sample of existing studies of k-coverage and connectivity in wireless sensor networks as well as some related work in connected k-coverage.

Key Terms in this Chapter

Heterogeneous Wireless Sensor Networks: A wireless sensor network is said to be heterogeneous if all of it sensors do not have the same storage, processing, battery power, sensing, and communication capabilities.

Interior and Boundary Lenses: An interior lens of a cluster is not shared with any of its adjacent clusters while a boundary lens is shared by two adjacent clusters.

Sensing Range: The sensing range of a sensor is a region where every event that takes place in this region can be detected by

k-Coverage: Let a be an area of a deployment field. A point is said to be covered if it belongs to the sensing range of at least one sensor. The area a is said to be covered if every point is covered. a is said to be k-covered if each point belongs to the intersection of sensing ranges of at least sensors. A wireless sensor network that provides full k-coverage of a field is called k-covered wireless sensor network, where a maximum value of is called degree of coverage of the network.

Sensing Neighbor Set: The sensing neighbor set of is a set of all the sensors located in its sensing range.

Communication Range: The communication range of a sensor is a region such that can communicate with any sensor located in this region.

Connectivity: A wireless sensor network is said to be connected if all the sensors can communicate with each other directly or indirectly.

Homogeneous Wireless Sensor Networks: A wireless sensor network is said to be homogeneous if all of it sensors have the same storage, processing, battery power, sensing, and communication capabilities.

Communication Neighbor Set: The communication neighbor set of is a set of all the sensors in its communication range.

Width: The width of a closed convex area is the maximum distance between parallel lines that bound it.

Complete Chapter List

Search this Book: