Energy efficient area coverage by evolutionary camera node scheduling algorithms in visual sensor networks

Abstract

Area coverage is an important research issue in the field of visual sensor networks (VSNs) because of the inherent constraints of VSNs, such as non-rechargeable energy resources and directionality of the sensing range of camera nodes. The dense deployment of camera nodes makes it possible to provide a satisfactory area coverage for a longer duration. At the same time the rest of camera nodes can be turned off and be scheduled to alternate the active nodes when it is necessary. In this paper, we define area coverage problem in VSNs aiming to minimize blind and redundantly covered grid cells of a desired area and energy distortion of camera nodes. Then we propose two scheduling algorithms for camera nodes which are randomly deployed to k-cover the desired area. In the first algorithm named evolutionary camera node scheduling (ECNS), we aim to achieve maximal area coverage by putting the smallest number of camera nodes into active mode and to minimize blind and redundantly grid cells. Since the objectives considered in ECNS conflict each other, we employ adaptive weighted sum method to formulate our objectives into a linear equation and then we propose a genetic algorithm to find the minimum value of the integrated linear equation. In the second algorithm named energy aware evolutionary camera node scheduling (EAECNS), we propose a method to strike a balance between the energy consumption of all camera nodes while it is providing satisfactory coverage of the target area and keeping the number of redundantly covered grid cells down. We evaluate the performance of both algorithms in terms of coverage, number of live nodes and redundancy by subsequent simulations. Also, we show that EAECNS has superior performance in comparison with ECNS and other state-of-the-art algorithms.

1 Introduction

Visual sensor networks (VSNs) consist of a large number of camera nodes each of which integrate capabilities of an image sensor, an embedded processor, and a wireless transceiver. Camera nodes in a VSN form a distributed multi-hop wireless network, where each node can capture image, process data locally and collaborate with other nodes to provide the system user application-specific information about intended targets. The powerful collaboration between nodes and the low cost of VSNs are some of the clear advantages that make these networks suitable for a variety of applications. Today, VSNs are widely used in different areas ranging from surveillance, monitoring and traffic controlling to advanced health care delivery and automated assistance for elderly people (Akyildiz et al. 2007, 2008; Soro and Heinzelman 2009; Hu and Kumar 2003; Reeves et al. 2005; Charfi et al. 2009).

In many typical VSN applications to successfully accomplish sensing tasks, camera nodes should cover the entire desired area. Therefore, area coverage problem is considered an important research issue especially when it comes to inherent characteristics of VSNs such as non-rechargeable energy resources and directionality of the sensing range of camera nodes (Guvensan and Yavuz 2011; Costa and Guedes 2010; Ai and Abouzeid 2006). According to the literature, many solutions have been proposed so far based on greedy, genetic and particle swarm optimization algorithms and binary integer programming methods to solve the problem of area coverage in VSNs (Cheng et al. 2007; Liang et al. 2011; Tezcan and Wang 2008a, b; Jiang et al. 2010; Kandoth and Chellappan 2009; Li et al. 2009; Morsly et al. 2012; Pham et al. 2011; Alaei and Barcelo-Ordinas 2010; Aghdasi et al. 2009; Hooshmand et al. 2013). Although the existing solutions provide suitable coverage of desired area, in majority of them it is assumed that camera nodes have the ability of rotation. This assumption needs special infrastructure and invokes high cost which is not satisfying for existing low-cost camera nodes (Tavli et al. 2012; Seema and Reisslein 2011; Newell et al. 2010; Kulkarni et al. 2005). However, there are a few number of solutions which employ high density of fixed camera nodes in a desired area and solve the area coverage problem in VSNs (Aghdasi et al. 2009; Hooshmand et al. 2013). Since these solutions do not consider the direct influence of remaining energy of camera nodes in their scheduling algorithms, they cannot induce a lot of camera nodes to be alive simultaneously and cannot prolong network lifetime while providing an acceptable coverage of the desired area.

Thus, in this paper we define area coverage problem in VSNs while minimizing blind and redundantly covered grid cells of desired area and minimizing camera nodes energy distortion as our objectives. We traverse the solution space with these three conflicting objectives. Then we rely on evolutionary methods and propose two new camera nodes scheduling algorithms to the defined area coverage problem in VSNs. We also simulate these algorithms with two different VSN scenarios to show effectiveness of proposed methods and fitness functions. The important part of our methods is emphasizing on prolonging network life time considering network power consumption distribution. Our defined fitness function is trying to schedule node in a fair way to achieve uniform power consumption in entire network. We also compared proposed methods with two other proposed methods to show effectiveness of them.

In our first scheduling algorithm for area coverage problem, we aim to provide maximal coverage by putting the least number of camera nodes into the active mode. First we apply geographical information to put the desired area into grid cells, and then we specify the grid cells covered by each camera node. We consider the objectives of minimizing blind and redundantly covered grid cells in the first scheduling algorithm. Second to obtain an acceptable compromise between the objectives which are conflicting each other, we utilize adaptive weighted sum method (Kim and De Weck 2006) to integrate them in a linear equation. Finally, we solve the area coverage problem using genetic algorithm to find the minimum value of the integrated linear equation which serves as a fitness function. Our proposed scheduling algorithm is named evolutionary camera node scheduling (ECNS).

A precise investigation on ECNS indicates that in network scenarios where camera nodes are densely deployed on desired area, this algorithm activates the best group of camera nodes in each scheduling time. Once the activated camera nodes die, ECNS replaces them with the best group of remaining camera nodes and provides area coverage for a longer duration. However, ECNS has some drawbacks. For instance, the group of camera nodes activated by ECNS to cover the desired area will die earlier than other camera nodes. As a result, based on the position of each camera node and the grid cells it covers, it is possible that the death of the first group of the activated nodes increases the number of blind and redundantly covered grid cells in the desired area.

Considering the drawbacks of ECNS and aiming to strike a balance between the remaining energy of all camera nodes, we set the minimization of camera nodes energy distortion as our third objective. The obtained result is a modified version of ECNS which we named energy aware evolutionary camera node scheduling (EAECNS). The core of EAECNS is based on genetic algorithm and it utilizes the integrated linear equation by weighted sum method (Kim and De Weck 2006) as its fitness function. The integrated linear equation used in EAECNS considers all the objectives we assumed in the defined area coverage problem. Our simulations prove the ability of EAECNS in satisfying all objectives in the defined area coverage problem (minimizing blind and redundantly covered grid cells besides minimizing remaining energy distortion of camera nodes) in comparison with ECNS and state-of-the-art algorithms.

The rest of this paper is organized as follows. Definition of the area coverage problem in VSNs is clarified in the next section. Related works is summarized in Sect. 3. In Sect. 4, the evolutionary camera nodes scheduling (ECNS) algorithm is proposed for the formulated area coverage problem. In Sect. 5, the modified version of ECNS, named energy aware ECNS (EAECNS) is proposed to strike a balance between the energy consumption of all camera nodes while providing acceptable coverage with a minimum number of redundantly covered grid cells of the desired area. Section 6 evaluates the performance of both ECNS and EAECNS algorithms through a set of extensive simulations. Finally, Sect. 7 is dedicated to some conclusion remarks.

2 Area coverage problem definition in VSNs

2.1 Preliminary assumptions

2.1.1 Considered area

A boundary region modeled in the form of a quadrilateral in a 2-D area which is gridded into $I$ rows and $J$ columns is considered the desired area in the area coverage problem of VSNs (see Fig. 1).

Fig. 1

A gridded sample of desired area in the area coverage problem

2.1.2 Camera node model

We use a common 2-D standard model for camera nodes. In this model, ($x_{C_{m}}, y_{C_{m}})$ are coordinates of $m$th camera node ($C_{m})$, $R_{\mathrm{S}}$ is radius of the camera sensing area, $\alpha$ is an angle representing the bisecting line of sight of camera sensing direction (rotation angle), $\theta$ is the angle of the FoV, and $R_{\mathrm{C}}$ is communication range of a camera node. Figure 2 represents a camera node model with the given characteristics. Due to high cost of camera nodes with ability of rotation, we assume that position of each camera node is fixed and its rotation angle cannot be changed; moreover, we assume that all camera nodes have the same characteristics and do not have the ability of changing FOV angle. Also we take into consideration that the camera nodes distributed randomly and uniformly all over of the desired area to provide a k-coverage for grid cells.

Fig. 2

The representation of a camera node in a 2-D space

2.2 Area coverage problem objectives

Considering our assumptions in Sect. 2.1 and requirements of VSN applications, we define the area coverage in a VSN so to attain following objectives.

• Blind Grid Cells Minimization: To minimize the number of uncovered grid cells in the desired area and to fulfill application-specific requirements.

• Redundantly Covered Grid Cells Minimization: To reduce the number of redundantly covered grid cells in the desired area and consequently put a minimum number of camera nodes into the active mode.

• Camera Nodes Remaining Energy Distortion Minimization: To minimize energy distortion of camera nodes by keeping their energy consumption balanced. This can be done by fairly putting some nodes into the active mode and keeping the rest of them alive for a longer duration.

2.3 Modeling the objectives of area coverage problem

In this section, before modeling the area coverage objectives some required variables are introduced. A 3-D array named $G_{I\times J\times M}$ is the first variable used in the modeling. $M$ is the maximum number of camera nodes and, $I$ and $J$ are the maximum number of rows and columns in the gridded desired area, respectively. In this array the element $G(i,j,m)$ with binary values ($1$ and $0)$ indicates whether or not the $i$th row and $j$th column of the gridded area is covered by the $m$th camera node respectively. The second variable in the modeling is the 1-D array named $Y_{M}$. Element $Y(m)$ with binary values ($1$ and $0)$ indicates whether or not $m$th camera node is selected as an activate node. The model of the three considered objectives of the area coverage problem is as follows:

To maximize the number of covered grid cells in the desired area, namely satisfying the Blind Grid Cells Minimization, Eq. (1) is designed to count the number of blind grid cells.

$$\begin{aligned} B_{\mathrm{Cells}}&= \sum \nolimits _{\text{ i }=1}^\mathrm{I} {\sum \nolimits _{\mathrm{j}=1}^\mathrm{J}} \nonumber \\&\quad \times {{\left( {1-\left\lceil {\frac{\sum \nolimits _{m=1}^M {\left[ {G(i,j,m)\times Y(m)} \right] } }{M}} \right\rceil }\right) } } \end{aligned}$$

(1)

where $M$ is the maximum number of camera nodes, $I$ and $J$ are the maximum number of rows and columns, respectively. The variables $G(j,j,m)$ and $Y(m)$ are the same as introduced in the first paragraph of this section. Increasing the number of $1$’s in $Y_{M}$ decreases the value of $B_{\mathrm{Cells}}$ in Eq. (1).

To minimize the number of grid cells that are covered more than once, namely satisfying the Redundantly Covered Grid Cells Minimization, we introduce Eq. (2) to count the number of redundantly covered grid cells.

$$\begin{aligned} R_{\mathrm{Cells}}&= \sum \nolimits _{{ i}=1}^{ I} \sum \nolimits _{{ j}=1}^{ J} \left( \left( {\sum \nolimits _{m=1}^M {\left[ {G(i,j,m)\times Y(m)} \right] } }\right) \right. \nonumber \\&\left. -\left\lceil {\frac{\sum \nolimits _{m=1}^M {\left[ {G(i,j,m)\times Y(m)} \right] } }{M}} \right\rceil \right) \end{aligned}$$

(2)

The definition and values of all parameters in Eq. (2) are the same as mentioned in Eq. (1).

To minimize the difference between the remaining energy of all camera nodes, namely satisfying the Camera Nodes Remaining Energy Distortion Minimization, Eq. (3) is designed to show the amount of distortion of scheduled camera nodes remaining energy

$$\begin{aligned} E_{\mathrm{Distortion}} =\sum \nolimits _{{ m}=1}^{ M} {[ {( {E_{\mathrm{Max}} -E(m)})\times Y(m)} ]} \end{aligned}$$

(3)

where $E_{\mathrm{Max}}$ is the maximum energy level of all camera nodes in each scheduling and $E(m)$ is the energy level of $m$th camera node. Other parameters have definition and values like Eq. (1).

3 Related works

In Cheng et al. (2007), authors employed a greedy approach named DGreedy to provide a maximal coverage. They used a minimum number of sensor nodes by scheduling their working directions. They assumed that each sensor node is equipped with multiple directional sensors and can activate only one at a time. In Liang et al. (2011) authors used DGreedy algorithm and presented update priority (UP) and least overlapped-area first (LOF) algorithms. The main difference between UP and DGreedy algorithms is that UP dynamically updates priority of nodes while DGreedy uses permanent priorities. The LOF algorithm follows all of schemes used in UP but it utilizes the size of overlapped area to assign priority to each sensor node. Although the mentioned algorithms increase area coverage, they are only applicable to scenarios in which multiple directional sensors with minimal density are deployed in target area.

Tezcan and Wang (2008a) introduced an algorithm in which each sensor orients its direction to maximize total coverage over the sensing field after determining its position. They focused on finding the most beneficial orientation for all sensors to maximize multimedia coverage and minimize the overlapping regions. Nodes scan their field of view (FoV) disk to find a visible FoV with the least possible occlusion. Besides, each sensor checks its FoV to examine whether or not it has overlap with any other sensor FoV.

Jiang et al. (2010) proposed a coverage-enhancement method based on genetic algorithm for occlusion-free surveillance model. They considered sub-areas all over the monitored area and assigned them some weights to calibrate their importance. The simulation results which compare the proposed algorithm with the self-oriented optimizing algorithm (Tezcan and Wang 2008a) indicated that the proposed algorithm enhances coverage.

Kandoth and Chellappan (2009) considered the issue of angular mobility to enhance coverage in directional camera sensor networks. They proposed a new distributed method called the face-away (FA) algorithm. This algorithm determines a new working direction for each sensor that is having the least density of neighbors to minimize the overlapping areas between neighboring sensors. It uses the exact position of neighboring sensors and plots lines to them. Thereafter, the largest angle between the adjacent directions is found and a bisector to that angle is drawn which indicates the new direction of the sensor. The experimental results show that FA algorithm achieves a satisfactory coverage percentage.

Li et al. (2009) presented a greedy approximation algorithm to optimize coverage in a directional sensor network while activating as few sensors as possible. The authors named this problem the optimal coverage in directional sensor networks (OCDSN), which can be solved by a greedy algorithm based on boundary Voronoi diagram. The assistant sensor, a traditional sensor with the same maximum sensing range as the directional sensor is used to solve the OCDSN problem. The objective of assistant sensor is to move through every edge of the diagram and determine whether the area is covered by any sensor or not. If not, it finds the nearest inactive sensor to the edge and changes its state to the active mode. Then, the activated node rotates its orientation toward the assistant sensor.

Altogether all of the mentioned algorithms (Cheng et al. 2007; Liang et al. 2011; Tezcan and Wang 2008a; Jiang et al. 2010; Kandoth and Chellappan 2009; Li et al. 2009) increase area coverage but they require motility which is expensive and cannot be achieved without infrastructure support (Tavli et al. 2012; Seema and Reisslein 2011; Newell et al. 2010; Kulkarni et al. 2005).

In our previous work in Aghdasi et al. (2009), we proposed a greedy algorithm called fair camera node scheduling (FCNS) to activate a suitable subset of camera nodes. FCNS is successful to strike a balance between energy consumption rates of all camera nodes while maximizing area coverage. However, it does not consider the Redundantly Covered Grid Cells Minimization objective for area coverage problem. Hooshmand et al. (2013) considered a large number of camera nodes in the desired area for achieving high network lifetime. They proposed five algorithms for scheduling camera nodes. When one or more of the activated camera nodes die, their algorithms select some other camera nodes instead and put them into the active mode. Maximum coverage area (MA), maximum lifetime and minimum overlap (MLMO) and symmetric difference (SD) are their three algorithms which are based on greedy approach, and the two others are based on genetic algorithm and particle swarm optimization. Simulation results in Hooshmand et al. (2013) showed that the SD algorithm has superior performance in comparison to the other algorithms.

4 Evolutionary camera node scheduling

4.1 A proposed function for minimizing blind and redundantly covered grid cells

One way to arrive at an acceptable compromise between the conflicting objectives of Eqs. (1) and (2) and integrate them into a linear equation is to utilize adaptive weighted sum method (Kim and De Weck 2006). Using this method, we define Eq. (4). Our final goal is to solve the defined area coverage problem by assigning proper values to $Y_{M}$ to minimize Eq. (4).

$$\begin{aligned} Z_{\mathrm{ECNS}} =w_1 \times \frac{B_{\mathrm{Cells}} }{B_{\mathrm{Cells}}^N }+w_2 \times \frac{R_{\mathrm{Cells}} }{R_{\mathrm{Cells}}^N } \end{aligned}$$

(4)

where $w_{1}$ and $w_{2}$ are weights of blind and redundantly covered grid cells minimization objectives, respectively, and their values should be specified by network administrator based on application constraints. $B_{\mathrm{Cells}}^N$ and $R_{\mathrm{Cells}}^N$ are nadir values of $B_{\mathrm{Cells}}$ and $R_{\mathrm{Cells}}$ in Eqs. (1) and (2) respectively.

The set cover optimization problem is reduced to the defined area coverage problem, thus, its complexity is NP-hard (Cormen et al. 2009; Neapolitan and Naimipour 2009) and finding a minimum value for Eq. (4) with the help of exact algorithms is fairly time consuming. Therefore, in ECNS we rely on evolutionary algorithms and propose a genetic algorithm to solve the coverage problem.

4.2 Proposed genetic algorithm

To schedule camera nodes and find a suitable set of them to minimize the $Z_{\mathrm{ECNS}}$ function, we apply a genetic algorithm with $Z_{\mathrm{ECNS}}$ as its fitness function. In this algorithm, $N$ is the number of individuals. Each individual is in the form of array $Y_{M}$ as described in Sect. 2.3 and is composed of $M$ genes. Each gene can be $1$ which means a camera node is activated or can be $0$ to show a turned-off or dead node. In the initial population which is related to live camera nodes, all individuals can be initialized to $1$s and $0$s randomly. Initialization performs according to probability P (initialization probability) and based on Eq. (5):

$$\begin{aligned}&n\in \{ {1,\ldots ,N} \}\,\, \text {and }\,\, m\in \{ {1,\ldots ,M} \} \nonumber \\&C_n^m =\left\{ \begin{array}{ll} 1 &{}\quad \text {if }\,\, (E(m)>0)\,\, \text {and}\,\, (\mathrm{Random}_n^m \le P) \\ 0 &{}\quad \text {otherwise} \\ \end{array} \right. \end{aligned}$$

(5)

where $E(m)$ is the remaining energy of the $m$th camera node and $\mathrm{Random}_n^m$ is a random number created for $m$th allele in $n$th individual. Finally, $C_{N\times M}$ is the population matrix.

Selection operator is the next component of our proposed solution. This operator uses binary tournament selection to transfer individuals from current population to mating pool. To create a pool of $L$ mating individuals, an individual with smaller fitness value from two randomly-chosen individuals of the current population is selected, and this process is repeated $L$ times to create the mating pool (MP$_{L\times M})$.

To produce a new population, individuals of the mating pool are divided into $L/2$ pairs. A proportion of $P_{\mathrm{C}}$ of the pairs is transferred to the new population after perturbation (offspring creation processes). Perturbation is composed of two processes: crossover and mutation. In the crossover process, two cut points $r_{1}$ and $r_{2}$ are selected randomly in the range of [$1 \ldots M$] and alleles of participating parents are swapped between these two points. (see the Eq. 6 for two-point crossover)

$$\begin{aligned} \begin{aligned}&l\in \{ {1,\ldots ,L} \} \\&\mathrm{MP}_l =(\mathrm{MP}_l^1 ,\ldots ,\mathrm{MP}_l^{r1} ,\mathrm{MP}_{l+1}^{r1+1} ,\ldots , \mathrm{MP}_{l+1}^{r2} , \\&\qquad \qquad \qquad \mathrm{MP}_l^{r2+1} ,\ldots ,\mathrm{MP}_l^M ) \\&\mathrm{MP}_{l+1} =(\mathrm{MP}_{l+1}^1 ,\ldots ,\mathrm{MP}_{l+1}^{r1} ,\mathrm{MP}_l^{r1+1} ,\ldots ,\mathrm{MP}_l^{r2} , \\&\qquad \qquad \qquad \mathrm{MP}_{l+1}^{r2+1} ,\ldots ,\mathrm{MP}_{l+1}^M ) \end{aligned} \end{aligned}$$

(6)

Next, each allele of the produced new individuals (offspring) is mutated with a probability $P_{m}$ in a mutation process based on Eq. (7):

$$\begin{aligned}&\!\!\! l\in \{ {1,\ldots ,L} \}\,\, \text{ and } \,\,m\in \{ {1,\ldots ,M} \} \nonumber \\&\!\!\! \mathrm{MP}_l^m \nonumber \\&= \left\{ \begin{array}{ll} 1-\mathrm{MP}_l^m &{}\quad \text{ if }\,\, (E(m)>0)\,\, \text{ and }\,\, (\mathrm{Random}_l^m \le P_m) \\ \mathrm{MP}_l^m &{}\quad \text{ otherwise } \\ \end{array} \right. \end{aligned}$$

(7)

After producing new individuals, the fitness value of each offspring is calculated. Next, the individuals in current $C_{N\times M}$ and MP$_{L\times M}$ are combined and $N$ individuals which have the lowest fitness values are picked to generate a new population (new $C_{N\times M})$. The selection, crossover, mutation, and combination processes are repeated to generate a new population until the termination condition of genetic algorithm is satisfied. In the final population, the best individual which has the least fitness value is considered to be the coverage optimization solution for ECNS and is formed the best $Y_{M}$. Figure 3 depicts flowchart of the proposed ECNS algorithm.

Fig. 3

ECNS algorithm flowchart

5 Energy aware evolutionary camera node scheduling

The ECNS algorithm initially activates the best group of camera nodes to provide maximal coverage of the desired area with minimal redundancy. It replaces the activated camera nodes with the best subset of remaining nodes just whenever their energy ends up. Obviously, ECNS does not activate camera nodes fairly so the energy of all camera nodes do not consume at an even rate. Nonetheless, fair activation of camera nodes, namely Camera Nodes Remaining Energy Distortion Minimization is essential to prolong the lifetime of each camera node and consequently keep most of them alive for a longer duration.

To minimize camera nodes energy consumption distortion, we modify ECNS algorithm and propose energy aware evolutionary camera nodes scheduling (EAECNS) which takes advantages of all objectives of defined area coverage problem. Since there should be a tradeoff between all objectives, we use the adaptive weighted sum method (Kim and De Weck 2006) and integrate them into a linear equation. We define $Z_{\mathrm{EAECNS}}$ function based on Eq. (8).

$$\begin{aligned} Z_{\mathrm{EAECNS}}&= w_1 \times \frac{B_{\mathrm{Cells}} }{B_{\mathrm{Cells}}^N }+w_2\nonumber \\&\times \frac{R_{\mathrm{Cells}} }{R_{\mathrm{Cells}}^N }+w_3 \times \frac{E_{\mathrm{Distortion}}}{E_{\mathrm{Distortion}}^N } \end{aligned}$$

(8)

where $w_1, w_2, B_{\mathrm{Cells}}, B_{\mathrm{Cells}}^N$, $R_{\mathrm{Cells}}$, and $R_{\mathrm{Cells}}^N$ are the same parameters defined in Eq. (4), $w_{3}$ is weight of fair activation objective and its value should be determined by the network administrator based on application requirements. Parameter $E_{\mathrm{Distortion}}^N$ is the nadir value for $E_{\mathrm{Distortion}}$ in Eq. (3).

Our goal is to assign a proper value to $Y_{M}$ that gets minimized value for Eq. (8); therefore, in EAECNS we utilize evolutionary algorithms and propose a genetic algorithm in which Eq. (8) is its fitness function. The genetic algorithms used in ECNS and EAECNS are the same except for their fitness functions are different. So there is no need to explain the genetic algorithm in this section again.

6 Performance evaluation

6.1 Simulation setup and assumptions

To evaluate the performance of ECNS and EAECNS, we implemented our simulations in MATLAB 7.6 executed on a Pentium Dual-Core CPU 2.5 GHz PC.

The desired area is put into grid cells and contains 18 camera nodes with the same characteristics described in Sect. 2.1.2. The camera nodes distributed randomly and uniformly to two-cover 90 % of a target area of size 50 m $\times$ 50 m. The size of each grid cell in the target area is 1 m$^{2}$ and the sensing range of camera nodes is 35 m with FoV of 75$^\circ$ and communication range tuned up to 70 m. We assume that each camera node has an initial energy of 10 J and consumes 1 J of its energy when it is activated in each scheduling. Since camera nodes are distributed randomly and uniformly in the desired area, we deployed camera nodes four times randomly with uniform distribution in the desired area making four different scenarios. Then we conducted simulations considering those scenarios and made final conclusions using the average of obtained results. To show performance of proposed algorithms, we compare simulation results with the results obtained from our previously designed FCNS algorithm (Aghdasi et al. 2009) and one of the state-of-the-art algorithms named SD (Hooshmand et al. 2013). Table 1 shows the parameters of genetic algorithm along with their values.

Table 1 Genetic algorithm parameters

Existing parameters in fitness functions ($Z_{\mathrm{ECNS}}$, $Z_{\mathrm{EAECNS}})$ which are based on desired area and camera nodes have constant values. By taking into consideration the characteristics of desired area and information of their nodes in simulations, the values of $B_{\mathrm{Cells}}^N$ and $R_{\mathrm{Cells}}^N$ are 2,500 and 7,500 grid cells, respectively. Also, $E_{\mathrm{Distortion}}^N$ is set to 180 J in $Z_{\mathrm{EAECNS}. }$ The weights of blind and redundantly grid cells and camera nodes remaining energy distortion minimization objectives should be initialized to proper values which will satisfy application requirements. Subsequently we explain how these weights should be determined.

First, we introduce a methodology for finding the value of weighting parameters in Eq. (8) ($Z_{\mathrm{EAECNS}})$. It should be taken into account that having satisfactory coverage of the target area is a vital requirement in many applications. So we put more emphasis on the objective of minimizing blind covered grid cells rather than the other two objectives. The satisfactory value for coverage is analogous to maximum number of blind covered grid cells which is tolerated by application and should be determined by network administrator. Moreover, fairly activating camera nodes is more important than minimizing redundancy. Keeping this in mind, the relation $w_{1} > w_{3} > w_{2}$ is acceptable for the weights in Eq. (8). In addition, whereas the objectives in $Z_{\mathrm{EAECNS}}$ have different types, we have $w_{1}+w_{2}+w_{3}=1$ according to the adaptive weighted sum method (Kim and De Weck 2006).

Applying these relations, the value of weight parameters in $Z_{\mathrm{EAECNS}}$ are $w_{1}=0.65$, $w_{2}=0.05$ and $w_{3}=0.3$ in all simulations. In Eq. (4) only the first relation ($w_{1} > w_{3} > w_{2})$ is applicable, therefore $w_{1}$ and $w_{2}$ are 0.65 and 0.05, respectively, in all steps of simulations.

6.2 Performance evaluation when the initial energy of camera nodes are homogeneous

In this section, we assume that all camera nodes have similar amount of initial energy (10 J). We run FCNS, ECNS, EAECNS and SD algorithms for 25 scheduling times with each of them operating in four different scenarios. In every running step, which is based on putting selected nodes into the active mode, the minimum average of blind grid cells, the number of live nodes and the number of redundantly covered grid cells are computed.

6.2.1 The number of blind grid cells

The simulation results shown in Fig. 4, indicates that EAECNS algorithm can provide 90 % coverage of desired area in 15 scheduling times and makes the average number of blind grid cells smaller than 250. However ECNS, SD, and FCNS can provide 90 % coverage of desired area just in 10, 10 and 13 scheduling times respectively. By taking into consideration the functionality of EAECNS algorithm to provide 90 % coverage of desired area, it can prolong network lifetime 1.15 times more than FCNS. Also it can prolong network lifetime 1.5 times more than ECNS and SD. The coverage by ECNS and SD cannot reach higher than 90 % after the 10$\mathrm{th }$ scheduling due to this regarding the remaining energy of camera nodes while they are selecting a set of active nodes. This will result in selecting nodes repeatedly in some scheduling times and causes their energy to end up after the 10$\mathrm{th}$ scheduling. As a result other alive camera nodes which are selected to active mode after 11$\mathrm{th }$ scheduling cannot provide desired coverage.

Fig. 4

The comparison between ECNS, EAECNS, FCNS, and SD in term of blind grid cells

We want to evaluate the minimum required coverage for better network functionality and providing 75 % coverage of desired area for applications (the number of blind grid cells are fewer than 625). The simulation results drawn in Fig. 4 imply that running FCNS algorithm can provide 75 % coverage of desired area (making the average number of blind grid cells fewer than 625) by 14 scheduling times. However EAECNS, ECNS and SD perform better than FCNS and can leave the average number of blind grid cells fewer than 625 up to 20 scheduling times and provide 75 % coverage of desired area. Although the functionalities of EAECNS, ECNS and SD in prolonging network lifetime are equal, the average number of blind grid cells until 20$\mathrm{th}$ scheduling time which provided by them at the same time are 176, 175 and 361 grid cells, respectively. By taking into account the better network functionality in simulations (providing 90 % minimum coverage and 75 % coverage of area) and the obtained results, we can conclude that EAECNS algorithm has better functionality in providing proper coverage in comparison with other algorithms.

6.2.2 The number of live camera nodes

The simulation results shown in Fig. 5 indicate that EAECNS can keep alive a high percentage of camera nodes for a noticeably longer duration of time in comparison with ECNS, SD and FCNS. It strikes a balance between remained energy of camera nodes. For instance the numerical results in Fig. 5 show that the percentage of alive nodes in 15$\mathrm{th }$ scheduling for EAECNS, ECNS, SD, and FCNS at the same time are 83.34, 55.56, 44.45, and 55.56 %, respectively. In 20$\mathrm{th}$ scheduling time, the percentage of live nodes for EAECNS, ECNS, SD, and FCNS are 66.67, 55.56, 44.45, and 0 %, respectively.

Fig. 5

The comparison between ECNS, EAECNS, FCNS, and SD in terms of live camera nodes

6.2.3 The number of redundantly covered grid cells

The simulation results shown in Fig. 6 imply that up to 10$\mathrm{th}$ scheduling time, ECNS algorithm provides less average redundancy than the other algorithms but the average number of redundantly covered grid cells up to 20$\mathrm{th }$ scheduling time in which EAECNS, ECNS, and SD can provide coverage more than 75 % are 1,479, 1,647, and 1,643 grid cells, respectively. Regarding this finding, EAECNS in redundantly covered grid cells performs better than the other algorithms. Also, we know that FCNS does not consider the objective of minimizing the number of redundantly covered grid cells so the number of redundantly covered grid cells in this algorithm is higher than the others. For instance, while FCNS provides 75 % coverage of the desired area in 14$\mathrm{th}$ scheduling times the average number of redundantly covered grid cells reaches 3,424.

Fig. 6

The comparison between ECNS, EAECNS, FCNS, and SD in terms of redundantly covered grid cells

6.3 Performance evaluation when the initial energy of camera nodes are heterogeneous

In this section, we evaluate the performance of EAECNS, ECNS, SD, and FCNS when they are applied to camera nodes supplied with different amounts of initial energy. In our simulations, we assume that two-third of camera nodes has 10 J and the rest have 5 J of initial energy. We run all the algorithms in four scenarios and in each run we calculate the minimum average number of blind grid cells, the number of live nodes and the number of redundantly covered grid cells.

6.3.1 The number of blind grid cells

The simulation results shown in Fig. 7 indicate that EAECNS algorithm can provide 90 % coverage of the desired area with 12 scheduling times and it makes the average of blind grid cells smaller than 250 grid cells. However, ECNS, SD, and FCNS can provide 90 % coverage of desired area just in 10 and 11 scheduling times, respectively. By take into consideration the functionality of EAECNS algorithm in providing 90 % coverage of desired area, it can prolong network lifetime 1.15 times more than FCNS and 1.5 times more than ECNS and SD. The coverage provided by ECNS and SD cannot get higher than 90 % after the 10$\mathrm{th}$ scheduling because the remaining energy of camera nodes are not considered while they are selecting a set of active nodes. This will result in selecting some nodes repeatedly in the first ten scheduling times so their energy will end up after the 10$\mathrm{th}$ times. The remaining nodes which are selected to active mode after 11$\mathrm{th}$ scheduling time cannot provide desired coverage.

Fig. 7

The comparison between ECNS, EAECNS, FCNS, and SD in terms of blind grid cells

Now we want to evaluate the minimum required coverage for a better network functionality and providing 75 % coverage of desired area for applications (the number of blind grid cells are fewer than 625). The simulation results shown in Fig. 7 imply that FCNS algorithm can provide 75 % coverage of desired area (making the average number of blind grid cells fewer than 625) by running the algorithm in 12 times schedule. However, EAECNS, ECNS, and SD perform better than FCNS. They can leave the average number of blind grid cells fewer than 625 up to 18$\mathrm{th}$, 15$\mathrm{th}$, and 15$\mathrm{th}$ scheduling times, respectively, and provide 75 % coverage of desired area. By taking into account better network functionality and providing 75 % minimum coverage, EACNS prolong network lifetime by 1.2 times more than ECNS and SD, and by 1.5 times more than FCNS. The average number of blind grid cells in EACNS, ECNS, SD and FCNS are 217, 159, 296, and 129, respectively, to provide 75 % minimum coverage of desired area.

6.3.2 The number of live camera nodes

The simulation results shown in Fig. 8 indicate that EAECNS can keep a high percentage of camera nodes alive for a noticeably longer duration than ECNS, SD, and FCNS by finding balance between camera nodes remained energy. For instance the numerical results in Fig. 8 indicate that the percentage of the number of alive nodes in 12$\mathrm{th}$ scheduling time for EAECNS, ECNS, SD, and FCNS are simultaneously 88.9, 55.56, 44.45, and 55.56 %. In 18$\mathrm{th}$ scheduling time the percentage of the number of alive nodes for EAECNS, ECNS, SD, and FCNS are 50, 33.34, 27.78, and 0 %, respectively.

Fig. 8

The comparison between ECNS, EAECNS, FCNS, and SD in terms of live camera nodes

6.3.3 The number of redundantly covered grid cells

The simulation results presented in Fig. 9 indicate that the average number of redundantly covered grid cells while EAECNS, ECNS, SD, and FCNS are able to provide more than 90 % coverage, are 1,407, 1,548, 1,683, and 3,217 grid cells, respectively. Moreover, while EAECNS, ECNS, SD, and FCNS are able to provide more than 75 % coverage, the average number of redundantly covered grid cells are 1,399, 1,555, 1,540, and 3,140 grid cells, respectively. Considering the obtained results we can say that EACNS in the case it provides 90 and 75 % minimum coverage and purposes a better functionality, operates better than the other algorithms and makes a reduced number of redundantly covered grid cell in comparison with them. The lack of minimizing redundantly covered grid cells in FCNS results in a higher redundantly covered grid cells.

Fig. 9

The comparison between ECNS, EAECNS, FCNS, and SD in terms of redundantly covered grid cells

7 Conclusion

In this paper, we studied the importance of area coverage in VSNs and proposed two evolutionary-based coverage algorithms to densely deployed camera nodes in a desired area. In both algorithms, we integrated the considered area coverage by contrasting the objectives into the linear equations and using adaptive weighted sum method. We used a genetic algorithm to find the minimum value of each equation (proposed fitness functions). The weight of each objective in both fitness functions can be adjusted based on its importance compared to the other objectives, thereby we ensured flexibility. Our first algorithm, evolutionary camera node scheduling (ECNS), effectively provided maximum area coverage and kept redundancy at its minimum value. Our main motivation to propose the second algorithm was the advantages of keeping all camera nodes alive as long as possible while it provides satisfactory coverage of the target area for a longer duration of time. Therefore, in the second algorithm, energy aware evolutionary camera node scheduling (EAECNS), we focused on energy consumption of all camera nodes at an even rate by activating nodes fairly while satisfying the two objectives considered in ECNS.

We evaluated the average performance of ECNS and EAECNS in two groups of network scenarios in comparison with our previous work named, FCNS (Aghdasi et al. 2009) and one of the state-of-the-art algorithms named, SD (Hooshmand et al. 2013). In the first group, all camera nodes had the equal amount of initial energy and in the second one they were initially supplied with different amounts of energy. The simulation results indicated that in both groups of network, EAECNS outperforms ECNS, FCNS, and SD algorithms in providing acceptable coverage of the desired area and keeping more camera nodes alive for a longer duration of time. Finally, the overall performance of EAECNS in terms of redundantly covered grid cells was better than ECNS, FCNS, and SD algorithms.