1 Introduction

Currently Wireless Sensor Networks (WSNs)find use in innumerable fields such as geographical area monitoring which includes military surveillance, geo-fencing; Medicine and healthcare applications like patient monitoring, clinical data collection; Industrial applications like monitoring machine health, water management, structural health management; environment-related applications that support disaster management, landslides and forest fire detection, water quality management, pollution control and monitoring [1]. A WSN is a group of spatially dispersed collaborative devices that work together to provide surveillance services and recording of information on various physical conditions within a real world environment. WSNs have become a pivotal research area due to many challenges aroused over time in terms of energy management, security and privacy, data aggregation, clock synchronization, unattended operation, maintenance, performance and latencies, decentralized architecture, etc., [2].

A sensor node is one of the most significant elements in a WSN and consists of a sensing device for observation, controllers for information processing, communication devices for data transfer and power sources for energy supply. A large number of sensor nodes are dispersed over the area of surveillance based on different topologies depending upon the quality requirements and the type of application. Data collected by the sensors or actuators from a physical environment are transferred to an application in a main server for processing with the help of gateways that constitute a data path for exchange of information [3].

Specific applications such as multimedia sensor networks may require the deployment of sensor nodes capable of directional sensing i.e. enabling surveillance in a particular direction within a specific sensing range. This is made possible through employment of directional sensor nodes in the network instead of the conventional ones that facilitate omnidirectional sensing. Such directional sensors are becoming increasingly popular because of their manufacturing size and cost. They are specially designed to serve a number of civil as well as military applications. A study of characteristics such as coverage, scheduling, maintenance, connectivity and deployment of directional sensor nodes which vary when compared to networks with omnidirectional sensor nodes is important.

Several constraints to be considered while designing a WSN which are deal with power supply, memory, hardware circuits, data size, deployment etc. One such constraint is exiguous energy supply to the sensor nodes as the sensor devices are generally established in an unattended area where recharging or replacing the energy source is either complicated or impossible and hence conservation of energy becomes important. Enhancing energy efficiency of a WSN is one of the main subjects on which most of the research works directed in recent years [4, 5]. One of the common strategies for energy conservation is designing protocols based on which sensors are scheduled to operate in a network. In directional sensor networks, these protocols facilitate operation of selected sensor nodes in specific sensing directions to ensure complete coverage (Target or Point coverage [6], Area Coverage [7], Barrier Coverage [8]), while other inactive sensor nodes are reserved for further utilization, thus extending the lifetime of the network. Each sensor node can be actuated in only one specific direction at any point of time. Target Coverage, in particular, deals with a set of points of interest called targets that are established in an environment and sensors are deployed and actuated to cover all these target points. Coverage can be a quality element in service requirement in some applications i.e. targets need to be covered by more than one sensor node for effective data collection. Target coverage in such applications is generalized as K-coverage which aims to ensure that each target is monitored by at least K different sensor nodes. In a directional sensor network, K-coverage aims to ensure coverage of every target by at least K different sensor nodes, each operated in a different specific direction.

Some applications involve targets associated with different importance and require to be covered by different number of sensors based on the importance. For such applications, a \(Q\)-coverage problem has been proposed in which the minimum number of sensors (sensing directions of various sensor nodes in case of directional sensor networks) required to cover each target is different from others. The sensing directions of the sensor nodes are designed for actuation in cover sets one after another with the requirement of each sensing direction in a cover to cover at least one target. This paper addresses the Q-coverage problem of directional sensor networks with respect to target coverage and a solution based on genetic algorithm is discussed.

2 Related Works

Enhancing energy efficiency of a WSN is one of the main goals for many researchers in the recent years. The SET K-COVER problem was proposed in [7] to find the maximum number of disjoint set covers consisting of a set of sensor nodes that can ensure complete coverage of the physical area and these set covers can be activated one after another to extend the lifetime of the network. Cardei et al. [9] have proposed Maximum Set Cover problem in which sensors are scheduled for actuation in different set covers that ensure coverage of specific points in the physical area referred to as targets. In Maximum Disjoint Set Covers problem [10], no sensor can be grouped into any multiple set cover this was to be ensured. Different protocols have been proposed to solve the target coverage problem in a WSN, which dealt with omnidirectional sensors.

Directional sensor networks facilitate operation of sensor nodes in specific sensing directions. Such directional sensors have many applications including video sensor networks that provide useful visual information [11], image sensors [12], ultrasonic sensors etc. The target coverage problem of a directional sensor network in which the sensors can be operated in different directions or orientations was modeled as Maximum Coverage with Minimum Sensors (MCMS) problem in [13] and has also been solved using an Integer Linear Programing approach that provides the most appropriate solution and a centralized greedy algorithm that provides an approximate solution but can be used in a large scale. The aim of the MCMS problem was to find the minimum number of directions that can cover the maximum number of targets. Cai et al. have proposed several algorithms for the multiple directional cover sets (MDCS) problem which aims at organizing the directions of sensors into disjoint groups [14]. A priority augmented graph and direction partition algorithm have been discussed in [15] to ensure coverage of targets based on different priorities by directional sensors. A column generation algorithm has been proposed for lifetime maximization in any directional sensor network [16].It consists of sensors with predefined directions and also for the network in which sensing directions can be varied. A search heuristic to find non-disjoint cover sets for Multiple Directional Cover Sets problem has been proposed and aimed to compute a group of cover sets that are non-disjoint and in each of these cover sets the directions ensure coverage of all the targets [17]. A randomized technique is used to approximate the network lifetime by scheduling the directional sensors for efficient target coverage [18].

Genetic algorithms based solutions are proposed for target coverage problem in directional sensor networks [19, 20]. These works deal with single coverage of targets i.e. all targets are entitled for coverage by at least one sensor meant only for efficient data collection. AQ-coverage problem [21] in a WSN is formulated for addressing the different QoS constraints faced by targets and various solutions are proposed [22, 23]. These solutions for Q-coverage problems deal with wireless omnidirectional sensor networks. A protocol for identifying the cover sets for Q-coverage in directional sensor networks with bounded service delay has been proposed by formulating the problem into a mixed integer programming problem [24]. A scheduling scheme is provided for reducing the energy consumed for rotating the directional sensor nodes while switching from one group to the next [25]. Quality based target coverage through use of directional sensor nodes was modeled as integer programming problem and two heuristics were discussed [26]. In this paper, we propose the Genetic Algorithm for Directional Q coverage (GA-DQC) for finding the maximum number of cover sets.

3 Problem Description

Consider a directional sensor network with a set of \(n\) sensor nodes \(S = \{ S_{1} ,S_{2} ,S_{3} ,........,S_{n} \}\) that are distributed in a particular locale for observation of a set of \(m\) targets \(T = \{ T_{1} ,T_{2} ,T_{3} ,........,T_{m} \} .\) A particular target \(T_{j}\) in the plane \(\left( {x_{j} ,y_{j} } \right)\) is said to be covered by a sensor node \(S_{i}\) in the plane \(\left( {x_{i} ,y_{i} } \right),\) if it satisfies the condition \(\sqrt {\left( {x_{i} - x_{j} } \right)^{2} + \left( {y_{i} - y_{j} } \right)^{2} } \le R,\) where \(R\) is the sensing range of the sensor, \(1 \le i \le n\) and \(1 \le j \le m.\)

The sensor coverage of the targets in a network is represented in form of a matrix,

\(\phi = \left[ {\begin{array}{*{20}c} {\phi_{11} } & {\phi_{12} } & \cdots & {\phi_{1m} } \\ {\phi_{21} } & {\phi_{22} } & \cdots & {\phi_{2m} } \\ \vdots & {} & {} & \vdots \\ {\phi_{n1} } & {\phi_{n2} } & \cdots & {\phi_{nm} } \\ \end{array} } \right],\) where \(\phi_{ij} = \,\,\left\{ \begin{gathered} 1,\;\;{\text{if}}\;{\text{sensor}}\;S_{i} \;{\text{covers}}\;{\text{target}}\;T_{j} \hfill \\ 0,\;\;{\text{otherwise}} \hfill \\ \end{gathered} \right.\)

In contrast to the conventional sensors which are omnidirectional in nature, directional sensors are capable of being actuated in varied sensing directions at different instances of time. For each sensor node \(S_{i}\) in set \(S,\) there can be \(p\) possible sensing directions and the set of all sensing directions for sensors in the network is represented by \(D = \left\{ {D_{11} ,D_{12} ,..,D_{1p} ,D_{21} ,D_{22} ,..,D_{2p} ,..,D_{n1} ,..,D_{np} } \right\}\) and the number of directions \(p\) is determined by the desired sensing angle \(\theta\) of the sensors as \(p = 2\pi /\theta .\) The omnidirectional sensing area within the sensing radius \(R\) of the sensors is partitioned into \(p\) different directional sensing areas. The \(kth\) sensing direction of \(ith\) sensor is represented as \(D_{ik} .\) A particular target \(T_{j}\) is said to be covered by \(D_{ik} ,\) \(kth\) sensing direction of sensor \(S_{i} ,\) if value of \(\phi_{ij}\) is 1 in the sensor coverage matrix \(\phi\) and the location of target \(T_{j}\) lies in the area within the \(kth\) direction of sensor \(S_{i} .\) A target \(T_{j}\) can be covered by only one operable sensing direction of a sensor \(S_{i} .\)

The target coverage in terms of directions of each of the sensors in a network is represented as a directional sensor coverage matrix,

\(\omega = \left[ {\begin{array}{*{20}c} {\omega_{11} } & {\omega_{12} } & \cdots & {\omega_{1m} } \\ {\omega_{21} } & {\omega_{22} } & \cdots & {\omega_{2m} } \\ \vdots & {} & {} & \vdots \\ {\omega_{n1} } & {\omega_{n2} } & \cdots & {\omega_{nm} } \\ \end{array} } \right],\) where \(\omega_{ij} = \phi_{ij} \times \left( {\alpha_{ij} /\theta } \right)\).

The angle at which a particular target \(T_{j}\) lies with respect to the sensor \(S_{i}\) is calculated as \(\alpha_{ij} = \arctan 2\left( {y_{j} - y_{i} ,x_{j} - x_{i} } \right)\) in degrees. If \(\arctan 2\) function returns a negative value, it is converted to positive by adding \(2\pi .\) For example, assume the directional sensor node \(S\) as shown in Fig. 1 at position \(\left( {0,0} \right)\) could operate in four different sensing directions with 90 degrees sensing angle and sensing range \(R = 60.\) Assume a target \(T\) is located at location \(\left( { - 40, - 40} \right)\) on the plane. Since the target \(T\) is located within the sensing range of the sensor \(S,\) the sensor coverage \(\phi_{ST}\) is \(1.\) The result of \(\arctan 2\left( {y_{T} - y_{S} ,x_{T} - x_{S} } \right)\) function is obtained as \(- 135\)(when converted to degrees) and \(2\pi\) is added as the result is negative \(\left( {\alpha_{ST} = 225} \right).\) The direction coverage for the target \(T\) and sensor \(S\) in figure is given by \(\omega_{ST} = 1 \times \left( {225/90} \right) = 2.5\) which is rounded off to 3. Thus the target \(T\) is covered by third sensing direction of sensor \(S.\)

Fig. 1
figure 1

An illustration to find direction coverage

Full size image

In general, the target coverage problem deals with the observation of the entire set of targets in a network while managing the energy consumption of the sensor nodes and thus extending the lifetime of the network. One of the approaches is to partition the sensor nodes into sensor covers and to actuate these covers in succession. But it is ensured that each cover set monitors the complete set of \(m\) targets in that network.

Most of the communication and scheduling protocols of a WSN are aimed at minimizing the energy consumption of the network. Every sensor \(S_{i}\) in the network is equipped initially with a definite amount of energy, \(e.\) Once the sensor nodes are installed in the environment, recharge or replacement of the source of energy in the sensors is difficult. When a particular sensor with initial energy \(e\) is activated in any one of the directions, \(e/p\) amount of energy gets dissipated. The residual energy in the sensor, given by \(\left( {p - 1} \right)e/p,\) can be used for further consumption during the lifetime of the network.

In some applications, there may be a requirement for a specific target \(T_{j}\) to be covered by at least \(K\) number of sensors at a time to ensure desired quality of service. A specific coverage parameter \(K\) is defined as the minimum number of sensor nodes to cover each target in set \(T,\) such that every target \(T_{j}\) lies within the sensing range of at least \(K\) different sensor nodes. The coverage parameter, in specific applications, can also be different for each target based on the difference in importance or QoS requisites of the targets. In such cases, a set \(Q = \,\left\{ {q_{1} ,q_{2} ,q_{3} ,...,q_{m} } \right\}\) denotes the minimal number of sensor nodes \(q_{j}\) that are necessary to cover each target \(T_{j}\) at any specific moment.

The set \(u = \left\{ {u_{1} ,u_{2} ,u_{3} ,..,u_{m} } \right\},\) where \(u_{k}\) denotes the total number of sensors in the network that cover the target \(T_{k} .\) If a target \(T_{k}\) is covered by \(u_{k}\) number sensors, then it is possible to form a maximum of \(\left( {u_{k} \times e} \right)/q_{j}\) covers in case of Q-coverage problem and \(\left( {u_{k} \times e} \right)/K\) covers in case of K-coverage problem. The target \(T_{k}\) will be left uncovered or would not meet the required Q-coverage or K-coverage constraints if \(\left( {u_{k} + 1} \right)^{th}\) cover is determined. The minimum value among the set \(u = \,\left\{ {u_{1} ,u_{2} ,...,u_{m} } \right\}\) is set as the upper bound,\(ub.\) Since a target is covered by only one direction of a particular sensor, the upper bound for the directional sensor network is same as the upper bound for omnidirectional sensor network and is defined as.

\(ub = \mathop {Min}\limits_{j} \left( {\left( {\sum\limits_{i} {\phi_{ij} } } \right) \times v} \right)\),where \(v = e/q_{j}\) for Q-coverage problem and \(v = e/K\) for K-coverage problem.

3.1 Illustration

The sample network depicted in Fig. 2 consists of a set of 3 targets observed by a set of 6 sensor nodes each with a fixed sensing range \(R,\) initial energy \(e = 3\) and fixed sensing angle of \(\theta = 120.\) Let the randomly generated Q-coverage constraints for the targets be defined by \(Q = \left[ {\begin{array}{*{20}c} 2 & 1 & 2 \\ \end{array} } \right]\) which implies that targets \(T_{1} ,\) \(T_{2}\) and \(T_{3}\) are to be covered by at least 2, 1 and 2 sensor nodes respectively in order to meet the QoS requisites.

Fig. 2
figure 2

A sample directional sensor network with 6 sensors and 3 targets

Full size image

The sensor coverage \(\left( \phi \right)\) and direction coverage \(\left( \omega \right)\) for the sample network depicted in Fig. 2are represented in a matrix form as follows:

$$\begin{gathered} \,\;\;\;\;\;\;\;\;\,\,\begin{array}{*{20}c} {T_{1} } & {T_{2} } & {T_{3} } \\ \end{array} \hfill \\ \phi = \begin{array}{*{20}c} {S_{1} } \\ {S_{2} } \\ {S_{3} } \\ {S_{4} } \\ {S_{5} } \\ {S_{6} } \\ \end{array} \left[ {\begin{array}{*{20}c} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \\ \end{array} } \right] \hfill \\ \;{\text{sum}} = \left( {\begin{array}{*{20}c} 3 & 3 & 3 \\ \end{array} } \right) \hfill \\ \end{gathered} \begin{gathered} \;\,\,\,\,\,\,\,\,\,\begin{array}{*{20}c} {\,\,\,\,T_{1} } & {T_{2} } & {T_{3} } \\ \end{array} \hfill \\ \omega = \begin{array}{*{20}c} {S_{1} } \\ {S_{2} } \\ {S_{3} } \\ {S_{4} } \\ {S_{5} } \\ {S_{6} } \\ \end{array} \left[ {\begin{array}{*{20}c} 3 & 0 & 0 \\ 2 & 3 & 0 \\ 0 & 2 & 3 \\ 0 & 0 & 2 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \\ \end{array} } \right] \hfill \\ \end{gathered}$$

The upper bound for the coverage problem in the given sample network is calculated as minimum value in the set,\(u = \left\{ {\,\left\lfloor {\left( {3 \times e} \right)/2} \right\rfloor ,\,\,\left\lfloor {\left( {3 \times e} \right)/1} \right\rfloor ,\,\,\left\lfloor {\left( {3 \times e} \right)/2} \right\rfloor \,} \right\},\) where \(e\) is the initial energy of the sensors. The minimum value among the set \(u,4\) is the upper bound \(\left( {ub} \right)\) of the network in Fig. 2.The possible set of covers that could be obtained for the network are \(Cover_{1} = \{ D_{13} ,D_{23} ,D_{33} ,D_{42} ,D_{51} \} ,\)\(Cover_{2} = \{ D_{13} ,D_{42} ,D_{51} ,D_{61} \} ,\)\(Cover_{3} = \{ D_{13} ,D_{22} ,D_{33} ,D_{61} \}\) and \(Cover_{4} = \{ D_{22} ,D_{42} ,D_{51} D_{61} \} .\)

4 Enhancing Lifetime of Directional Sensor Network

Genetic algorithm is a heuristic search algorithm used for solving optimization problems which imitate certain characteristics of natural evolution process. The individual solutions are upgraded repeatedly to achieve an ideal solution. In order to steer towards a potential solution for a specific problem, the individual solutions are encoded as chromosomes and refined using three main operators namely selection, crossover and mutation. A selection operator randomly chooses individual candidates from a population based on the fitness criterion for introduction into the successive stages of the algorithm. The crossover operator diversifies the population from one generation to the next by producing child solutions from two parent solutions. Mutation operator facilitates alteration of one or more values in individual solutions based on a user defined probability to vary the population in successive generations. The fittest population survives at each successive generation and finally an optimal solution is obtained after maximum number of generations. The pseudo code of the genetic algorithm is depicted as:

Input: Initial_pop, generation_size

Output: Coversets

1

for 1 to generation_size

2

Parent_fitness = Fitness(Initial_pop);

3

Offspring = Crossover(Initial_pop);

4

Offspring = Mutation(Offspring);

5

Child_fitness = Fitness(Offspring);

6

Initial_pop = Selection(Initial_pop,Offspring,Parent_fitness,Child_fitness);

7

End for;

9

Coversets = Initial_pop;

4.1 Representation

Representation involves encoding the solutions in a form that is suitable for evolutionary computations. The solutions are encoded in the form of a matrix with \(n\) rows and \(ub\) columns, where \(n\) is the number of sensor nodes and \(ub\) is the upper bound of the network. Each entry in the matrix is randomly assigned sensing directions of the sensors that cover at least one target. These sensing directions are distributed over the covers based on the residual energy of the sensors. Since the expected number of covers is predicted as \(ub\) and the solution sets are confined to \(ub\) number of columns, the ideal solution is obtained with minimal amount of computation. A sample representation of the matrix is given by:

$$\begin{gathered} \begin{array}{*{20}c} {\,\;\;\,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;C_{1} } & {C_{2} } & {\,\,\,\,\,...} & {C_{ub} } \\ \end{array} \hfill \\ Population = \begin{array}{*{20}c} {S_{1} } \\ {S_{2} } \\ . \\ . \\ . \\ {S_{n} } \\ \end{array} \left[ {\begin{array}{*{20}c} {\beta_{1,1} } & {\beta_{1,2} } & {...} & {\beta_{1,ub} } \\ {\beta_{2,1} } & {\beta_{2,2} } & {...} & {\beta_{2,ub} } \\ . & . & . & . \\ . & . & . & . \\ . & . & . & . \\ {\beta_{n,1} } & . & . & {\beta_{n,ub} } \\ \end{array} } \right] \hfill \\ \end{gathered}$$

where \(\beta_{i,j}\) is a randomly selected sensing direction of \(S_{i}\) that covers at least one target in set \(T\) and \(1 \le \beta_{i,j} \le p.\)

4.2 Generation of Initial Population

Genetic algorithm involves random generation of a set of 100 initial populations that participate in the successive stages of the algorithm. The initial population is formed by identifying the sensing directions of each sensor that cover at least one target from the direction coverage matrix. These identified sensing directions are randomly distributed over the \(e\) number of columns out of the \(ub\) number of columns for the respective sensors in the population matrix where \(e\) denotes the energy of the sensors. The remaining column values of each sensor are set to zero. In a similar manner, other initial populations are generated randomly.

The matrices \(pop_{1}\) and \(pop_{2}\) form the first two initial population matrices for the network mentioned in Fig. 2.The sensing directions of each sensor that covers at least one target are identified to be \(S_{1} = \left\{ 3 \right\},\,\,S_{2} = \left\{ {2,3} \right\},\,\,S_{3} = \left\{ {2,3} \right\},\,\,S_{4} = \left\{ 2 \right\},\,\,S_{5} = \left\{ 1 \right\},\,\,S_{6} = \left\{ 1 \right\}\) and the energy of the sensors \(e = 3.\) In population matrix \(pop_{1} ,\) for sensor node, \(S_{1}\) the direction 3 is randomly assigned to 3columns as the total energy is 3 and for sensor node \(S_{2}\) the directions 2and 3are randomly assigned to 3 columns. In a similar manner, the direction values are generated for all the sensors in the \(pop_{1}\) matrix. The remaining values are set to zero.

$$pop_{1} = \begin{array}{*{20}c} {S_{1} } \\ {S_{2} } \\ {S_{3} } \\ {S_{4} } \\ {S_{5} } \\ {S_{6} } \\ \end{array} \left[ {\begin{array}{*{20}c} 3 & 3 & 3 & 0 \\ 3 & 0 & 2 & 2 \\ 3 & 3 & 0 & 0 \\ 2 & 0 & 2 & 2 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ \end{array} } \right]\;\;\;\;pop_{2} = \begin{array}{*{20}c} {S_{1} } \\ {S_{2} } \\ {S_{3} } \\ {S_{4} } \\ {S_{5} } \\ {S_{6} } \\ \end{array} \left[ {\begin{array}{*{20}c} 3 & 0 & 3 & 3 \\ 2 & 3 & 0 & 2 \\ 2 & 2 & 0 & 3 \\ 2 & 2 & 0 & 2 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ \end{array} } \right]$$

4.3 Fitness Function

A fitness function is designed for analysis of the extent of a given solution to the ideal solution to be obtained. Selection of population in each generation is based on the outcome of the fitness function. The fitness value of a population is determined by the sum of fitness values of all individual covers in that population. The fitness value of a cover is one if it covers all the targets with respect to the Q-coverage or K-coverage constraints of each target. If not, the fitness value is zero.

The set of sensors with respective sensing directions that belong to \(C_{1}\) in the matrix \(pop_{1}\) is \(C_{1} = \{ D_{13} ,D_{23} ,D_{33} ,D_{42} ,D_{51} ,D_{61} \} .\) The sensor nodes \(S_{1} ,S_{2}\) and \(S_{3}\) are activated in the third direction while the sensor nodes \(S_{5} ,S_{6}\) are to be activated in the first direction and \(S_{4}\) in the second directions. The targets covered by the sensors in the set described by \(C_{1}\) are \(S_{1} = \left\{ {T_{1} } \right\},S_{2} = \left\{ {T_{2} } \right\},S_{3} = \left\{ {T_{3} } \right\},S_{4} = \left\{ {T_{3} } \right\},S_{5} = \left\{ {T_{1} } \right\},S_{6} = \left\{ {T_{2} ,T_{3} } \right\}.\) Thus, the targets \(T_{1}\) and \(T_{2}\) are covered twice and target \(T_{3}\) is covered thrice. This signifies the cover \(C_{1}\) covering all the targets with respect to their coverage constraints as mentioned in set \(Q = \left[ {\begin{array}{*{20}c} 2 & 1 & 2 \\ \end{array} } \right]\) and its fitness value is one. Similarly, the fitness values of \(C_{1} ,C_{2} ,C_{3} ,C_{4}\) in \(pop_{1}\) are 1, 0, 1 and 0 respectively. Thus the fitness value of \(pop_{1}\) is 2, which is the sum of the individual fitness values of \(C_{1} ,C_{2} ,C_{3}\) and \(C_{4}\).

4.4 Selection

The selection operator is responsible for the selection of candidates on the basis of the fitness values for the formation of the mating pool from the initial population and the random selection of parent populations from the mating pool to produce offspring. Based on the fitness function results, the best individuals are selected for the next generation.

4.5 Crossover

The crossover operator remodels the population in each generation by producing offsprings through exchange of genes between two parent solutions at specific locations determined by the randomly chosen crossover point which could vary between 1 and \(n.\) The result of performing crossover operation for \(pop_{1}\) and \(pop_{2}\) with crossover point chosen to be 3 is given by \(Offspring_{1}\) and \(Offspring_{2} .\)

$$\begin{gathered} \;\;\;\;\begin{array}{*{20}c} {\,\;\;\,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,\,\,\,\,\,\,\,C_{1} } & {\,\,C_{2} } & {\,\,C_{3} } & {\,\,C_{4} } \\ \end{array} \,\;\;\;\begin{array}{*{20}c} {\,\;\;\,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,\,\,\,\,C_{1} } & {\,\,\,C_{2} } & {\,\,C_{3} } & {\,\,C_{4} } \\ \end{array} \hfill \\ Offspring_{1} = \begin{array}{*{20}c} {S_{1} } \\ {S_{2} } \\ {S_{3} } \\ {S_{4} } \\ {S_{5} } \\ {S_{6} } \\ \end{array} \left[ {\begin{array}{*{20}c} 3 & 3 & 3 & 0 \\ 3 & 0 & 2 & 2 \\ 3 & 3 & 0 & 0 \\ 2 & 2 & 0 & 2 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ \end{array} } \right]\;\;\;\;Offspring_{2} = \begin{array}{*{20}c} {S_{1} } \\ {S_{2} } \\ {S_{3} } \\ {S_{4} } \\ {S_{5} } \\ {S_{6} } \\ \end{array} \left[ {\begin{array}{*{20}c} 3 & 0 & 3 & 3 \\ 2 & 3 & 0 & 2 \\ 2 & 2 & 0 & 3 \\ 2 & 0 & 2 & 2 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ \end{array} } \right] \hfill \\ \end{gathered}$$

4.6 Mutation

The mutation operator further refines the population matrices of successive generations by altering the sequence of a particular sensor chosen at random on the basis of probability. The sensing directions of the chosen sensor are altered in between the covers in such a way to ensure satisfactory fitness for the obtained offspring. The outcome of mutation operation on \(Offspring_{1}\) and \(Offspring_{2}\) when the mutation point is set as 3

$$\begin{gathered} \;\;\;\begin{array}{*{20}c} {\,\;\;\,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,\,\,\,\,\,\,\,\,\,\,\,\,C_{1} } & {\,\,\,C_{2} } & {\,\,\,C_{3} } & {\,\,C_{4} } \\ \end{array} \,\;\;\begin{array}{*{20}c} {\,\;\;\,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,\,\,\,C_{1} } & {\,\,\,\,C_{2} } & {\,\,C_{3} } & {\,\,C_{4} } \\ \end{array} \, \hfill \\ Offspring_{1} = \begin{array}{*{20}c} {S_{1} } \\ {S_{2} } \\ {S_{3} } \\ {S_{4} } \\ {S_{5} } \\ {S_{6} } \\ \end{array} \left[ {\begin{array}{*{20}c} 3 & 3 & 3 & 0 \\ 3 & 0 & 2 & 2 \\ 3 & 0 & 3 & 0 \\ 2 & 2 & 0 & 2 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ \end{array} } \right]\;\;\;\;Offspring_{2} = \begin{array}{*{20}c} {S_{1} } \\ {S_{2} } \\ {S_{3} } \\ {S_{4} } \\ {S_{5} } \\ {S_{6} } \\ \end{array} \left[ {\begin{array}{*{20}c} 3 & 0 & 3 & 3 \\ 2 & 3 & 0 & 2 \\ 2 & 0 & 2 & 3 \\ 2 & 0 & 2 & 2 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ \end{array} } \right] \hfill \\ \end{gathered}$$

The best solution is identified on the basis offitness values of \(pop_{1} ,pop_{2} ,Offspring_{1}\) and \(Offspring_{2}\) which are found to be 2, 1, 4 and 3 respectively. The fitness value of the population matrix \(Offspring_{1}\) is the highest and hence identified as the ideal solution given in Fig. 2 and the cover sets are \(Cover_{1} = \left\{ {D_{13} ,D_{23} ,D_{33} ,D_{42} ,D_{51} } \right\},\)\(Cover_{2} = \left\{ {D_{13} ,D_{42} ,D_{51} ,D_{61} } \right\},\)\(Cover_{3} = \left\{ {D_{13} ,D_{22} ,D_{33} ,D_{61} } \right\}\) and \(Cover_{4} = \left\{ {D_{22} ,D_{42} ,D_{51} D_{61} } \right\}.\)

5 Simulation

The proposed algorithm has been simulated using MATLAB. Simulations are implemented in a Windows7 operating system on a Intel Core processor with 4 GB RAM and 2.3 GHz speed. The sensors and targets are located randomly on a plane of \(100 \times 100\) square units. Since the sensors are randomly deployed, there may be slight variation in results based on the random locations at which they are placed in different instances. For each experiment, five instances are simulated and the average is calculated. The number of generations and the population size of the genetic algorithm are set to a fixed value of \(100\) in all the experiments. The mutation rate is fixed at a constant rate of \(0.7.\)

The results for GA-DQC problem with the number of sensors varying between 50 and 100 and the number of targets from 20 to 40 with a fixed sensing range \(R = 60\) and a fixed sensing angle \(\theta = 120\) are simulated and the average lifetime is calculated. Figures 3 and 4 show the variation in lifetime of the network with respect to variations in number of sensor nodes, number of targets and different maximum Q-Coverage constraints \((Q_{\max } ).\) The different Q-coverage values of targets are randomly assumed between 1 and \(Q_{\max } .\) The \(Q_{\max }\) values are varied as 1, 2, 3 and 4. When \(Q_{\max }\) value is set to 1, the problem is generalized as a K-coverage problem or a single coverage problem where all the targets are required to be covered by at least one sensor node. Figure 3 represents Lifetime for varying number of sensors, 20 targets and varying Q-coverage constraints and Fig. 4 represents Lifetime of the network for 100 sensors with varying number of targets and Q-coverage constraints. It is found, that for all varying Q-coverage values, the lifetime tends to increase with an increase in the number of sensor nodes in general.

Fig. 3
figure 3

Network lifetime for varying number of sensors and Q coverage constraints

Full size image
Fig. 4
figure 4

Network lifetime for varying number of targets and Q coverage constraints

Full size image

The effect of variations in sensing angle of the sensors on the lifetime of a network with 100 sensors and 40 targets is shown in Fig. 5 for \(Q_{\max }\) values 1, 2 and 3. The sensing angles are varied as 36, 45, 60, 72, 90, 120, 180 and 360 degrees, while the sensing range is set at a constant of 60 units. The initial energy of the sensors is assumed to be the number of total sensing directions in each sensor. There is only a decrease in the lifetime when the sensing angle of sensors is increased for each of the \(Q_{\max }\) constraints. This is so because, the number of different directions in which a sensor can be activated is decreased when the sensing angle increases which limits the number of possible cover sets that can be formed.

Fig. 5
figure 5

Effect of varying sensing angles in the network lifetime

Full size image

Figure 6 shows the results of the algorithm simulated for varying number of sensors and targets with K-coverage constraints as 1 and 2. Similar to simulations of Q-coverage, the sensing angle is set to 120 degrees and sensing range is 60 units, with variations in the number of sensor nodes between 50 and 100, variations in the number of targets between 20 and 40. The average lifetime of Q-coverage problem is found to be slightly higher in most of the cases as compared to lifetime of the K-coverage problem (i.e. when comparing results of networks with maximum Q-coverage and K-coverage constraint set as 2).

Fig. 6
figure 6

Network lifetime for varying number of sensors and targets with K-coverage constraints 1 and 2

Full size image

The simulations in Tables1, 2, 3, 4 and 5 are aimed at comparison of the results of the proposed GA-DQC with the results of existing algorithms [8, 11, 12] for complete target coverage problem \((Q_{\max } = 1)\) in which omnidirectional sensors are used in the network \((\theta = 360).\) The simulations are tabulated for varied number of targets and varying number of sensor nodes with differing sensing ranges deployed on a \(500 \times 500\) plane. The results of improved Memetic Algorithm (iMA) [27], Memetic Algorithm (MA) [28], integer based Genetic Algorithms (iGA) [29], MCMCC [7], and the results of the proposed GA-DQC are compared.

Table 1 Network lifetime vs. sensing ranges (for small scale networks)
Full size table
Table 2 Network lifetime vs. sensing ranges (for large scale networks)
Full size table
Table 3 Network lifetime vs. number of targets (for large scale networks)
Full size table
Table 4 Network lifetime vs. number of sensor nodes (for small scale networks)
Full size table
Table 5 Network lifetime vs. number of sensor nodes(for large scale networks)
Full size table

The average upper bound, average and standard deviation of network lifetime of five instances of proposed GA-DQC are tabulated in columns 2, 3 and 4 respectively. In columns 5and 6, the average upper bound and average lifetime of 100 instances of iMA are tabulated. Column 7 represents the average upper bound of MA, iGA and MCMCC for varying number of sensor nodes with different sensing ranges and varying number of targets. The averages and standard deviations of network lifetime obtained by MA, iGA and MCMCC are specified in columns 8 to 13 in the corresponding tables.

Table 1 shows the results of small scale networks with 10 targets and 90 sensor nodes with varying sensing ranges between 100 and 500. Table 2 shows the results for large scale networks with 300 sensors and 500 targets with varying sensing ranges between 100 and 500. The lifetime obtained in the simulation instances of GA-DQC have reached the upper bound in almost all cases, which implies the optimal nature of the solution. The GA-DQC algorithm tends to assume the upper bound taking into consideration the coverage constraints and energy of the sensors, which minimize the search space and facilitate obtaining of an optimal solution. The lifetime increases with increase in the sensing ranges of the sensor nodes.

Table 3 show tabulation of results for large networks (300 sensors with sensing range 400) with varied number of targets (varied between 10 and 500). In most of the cases, the average lifetime of GA-DQC is said to reach the average upper bound. The upper bound of GA-DQC algorithm is found appropriate for the coverage of targets while the fitness function evaluates each solution for efficient coverage of each target with respect to Q-coverage constraints.

Tables 4 and 5 show the results of networks with 10 targets and 500 targets respectively. The sensing range in Table 4 is maintained at 250, while in Table 5, the sensing range is set to 400. The number of sensors is varied between 90 and 300 with constant sensing ranges of 250 (Table 4) and 400 (Table 5).The GA-DQC algorithm finds different directions of sensors that can be activated in different covers for ensuring complete coverage. The initial population, though it is randomly generated, consists only of the sensing directions of sensors that cover at least one of the targets and this gives a population that has better fitness as the unused directions (directions of sensor nodes that do not cover any of the targets) are eliminated even at the initial stage. This results in better performance of the proposed algorithm when compared to existing algorithms.

6 Conclusion

This paper discussed the Q-coverage problem, a generalized case of K-coverage and single coverage problem (Target coverage) of directional sensor networks with respect to power supply constraints and proposed a genetic algorithm based solution. The sensing ranges of sensor nodes are varied based on the requirements and each sensor node can operate in multiple directions (the number of sensing direction is decided by the sensing angle). Most common method for extending the lifetime of the network is to divide the sensor nodes in a wireless sensor network (sensing directions of different sensor nodes in a directional sensor network) into groups called cover sets and schedule the network such that the cover sets are activated one at a time. It is assured that the coverage constraints of all targets are met by the set of sensing directions in each cover set. The results of GA-DQC for varying Q-coverage and K-coverage constraints, various sensing ranges and varying count of sensor nodes and target points are simulated. The results are also compared with those of memetic and genetic algorithms proposed earlier for a complete coverage problem (the K-coverage value is set to 1) of omnidirectional sensor networks (the sensing angle is set to 360 degrees). The proposed GA-DQC reached the upper bound in most of the simulations and an optimal solution was obtained for both small scale and large scale networks. GA-DQC performs better than other algorithms as the target coverage is ensured from the initial population formation and as a result of the ability of each sensor nodes to be activated in different sensing directions in various covers.