Exact and Efficient Heuristic Deployment in WSN under Coverage, Connectivity, and Lifetime Constraints

Introduction

Wireless Sensor Networks (WSNs) are composed of a multiplicity of many tiny, low-power nodes that integrate processing units, sensing units and radio transceivers. The sensors are used to collect process and transport data to the sink nodes in the network. A sensor is the device which converts physical phenomenon, such as temperature, light, motion or vibration, to electric signals. Sensor devices are generally deployed inside a region of interested to collect information about the environment. WSNs have been already used successfully in different application scenarios, such as military, environmental applications, health, home automation or business. For the interested reader, more details can be found in (Gupta & Poonam, 2014).

Among the multitude of challenges facing the design and implementation of cost-efficient and energy-conservative WSNs, though providing a satisfactory grade of service, sensor deployment or placement strategy has been identified as a critical lever (Sharma, Patel, Bhadauria & Prasad, 2015). Not only the sensors have to closely monitor a number of physical phenomena (or targets), possibly scattered over a large geographical region, but also the network formed by these nodes must be fully connected: every collected data must reach the sink without relying on any type of wired transmission facility. Moreover, the energy that each sensor will dissipate in accomplishing its duties, such as sensing or transmitting/receiving data, is clearly dependent on the amount of handled data traffic and the separating physical distance from its peers. Still that no deployment strategy can be suited to all application scenarios and usage requirements, as many objectives are usually conflicting, such as observability, latency, cost or longevity.

Depending on the system goals and the topography of the surrounding environment, we can roughly distinguish two types of deployment strategies: random and controlled (preplanned). Random deployments are adapted to inaccessible or hostile environments, such as battle fields or disaster regions. Whereas, controlled deployment strategies are usually applied in accessible environments where the sensors can be placed exactly in the desired locations, eventually by using a robot.

In this paper, we focus on the following key design parameters in the context of a controlled sensor placement strategy: cost (number of sensors), coverage, network connectivity and lifetime (energy efficiency). Coverage is usually defined as a measure of how well and for how long the sensors are able to fulfill their sensing tasks. (Megha & Sonia, 2013) analyzed several coverage types in the context of different deployment strategies. Typically, the sensing range is a circular disk centered at the sensor. A given point is said to be covered by a sensor network if it falls in the sensing range of at least one sensor. A region is said to be covered if all the inner points are covered (Wei, Vikram & Kee-Chaing, 2008). The target coverage problem is to determine the sensor locations such that a set of given targets are observed with some required quality. One natural question here is how coverage and quality can be met by deploying a minimum number of sensors?

Another fundamental parameter in WSNs is connectivity, which can be defined as the ability of every sensor node to send its data to the sink. Network lifetime is another important issue due to the very limited capacity of sensor batteries. Lifetime was defined in different ways in the literature (Madhu & Suchismita, 2015; Manirajan & Sathishkumar, 2015), but a widely accepted one, that we adopt in this paper, is the time from the start of network operation to the instant when the first sensor exhausts it energy.