Sage Journals: Discover world-class research

Abstract

Lifetime requirements and coverage demands are emphasized in wireless sensor networks. An area coverage algorithm based on differential evolution is developed in this study to obtain a given coverage ratio $ε$ . The proposed algorithm maximizes the lifetime of wireless sensor networks to monitor the area of interest. To this end, we translate continuous area coverage into classical discrete point coverage, so that the optimization process can be realized by wireless sensor networks. Based on maintaining the ε-coverage performance, area coverage algorithm based on differential evolution takes the minimal energy as optimization objective. In area coverage algorithm based on differential evolution, binary differential evolution is redeveloped to search for an improved node subset and thus meet the coverage demand. Taking into account that the results of binary differential evolution are depended on the initial value, the resulting individual is not an absolutely perfect node subset. A compensation strategy is provided to avoid unbalanced energy consumption for the obtained node subset by introducing the positive and negative utility ratios. Under the helps of those ratios and compensation strategy, the resulting node subset can be added additional nodes to remedy insufficient coverage, and redundancy active nodes can be pushed into sleep state. Furthermore, balance and residual energy are considered in area coverage algorithm based on differential evolution, which can expand the scope of population exploration and accelerate convergence. Experimental results show that area coverage algorithm based on differential evolution possesses high energy and computation efficiencies and provides 90% network coverage.

Keywords

Wireless sensor networks differential evolution node subset of coverage minimal cost maximal lifetime

Introduction

Numerous micro-sensor nodes that monitor events are randomly deployed in areas of interest within a network. Although battery power is limited, batteries are always selected as the energy provider in sensor networks because utilization of passive power can make this network highly flexible. Another problem that should be resolved for a network is how to prolong its life cycle^1–3 while using battery power to maintain network performance, such as coverage, sensing quality, and link quality.

The energy efficiency is a constant topic of concern. In the networks with continuous power supply, the most energy efficient path is also required by some mission-critical applications. In big data collection, energy efficiency means to find an appropriate data center.⁴ For cloud computing, we hope to build framework to gain a most energy efficient route to the data center.^5,6 Even for service-defined internet of things (IOT), an energy-aware composition plan is also appreciated due to energy control.⁷

For the battery-powered sensor network, the efficient energy control is the most essential topic in order to gain the longer lifetime. A common and effective method to balance these demands is to schedule a part of the nodes^8,9 to participate in covering the area of interest. This scheduled part of nodes is called the node subset of coverage. The entire network exhibits equilibrium energy consumption and expanded lifetime because of this node subset schedule.

A new opinion is that consecutive area coverage can be translated into discrete point coverage when the monitored target is a plane area. This process can feasibly solve the area coverage problem in machine devices. The area of interest can be equal to finite interest points from the microscopic point of view. When nodes cover these points, the area of interest that is replaced by points also exhibits satisfactory coverage demands.^10,11 Thus, in this study, several particular nodes are scheduled to satisfy coverage requirements for interest points to save energy and extend the network lifetime. Interest points are also called target points.

Three fundamental issues should be examined. The first issue is determining the relationship between point and area coverage through a numerical study. The second issue is solving the point coverage. The third one is selecting an improved node subset that uniformly costs minimal energy.

For the first issue, the ε-coverage algorithm in the literatures^11,12 provides a bridge between area coverage and point coverage. The coverage ratio of any point on a circular plane is not less than $ε$ when the coverage ratio of a given target point $p_{j}$ in the area of interest is $ε e^{K R_{j}}$ or more, where $ε$ is the coverage threshold for the area of interest, K is the network parameter, $p_{j}$ is the center, and $R_{j}$ is the radius.

The area is named as the ε-coverage. When $ε e^{K R_{j}}$ and ε-coverage theory¹³ are used, the problem of how area coverage becomes equivalent to finite point coverage can be solved well. If the entire area needs to meet coverage ratio $ε$ , target points within area must be extensively distributed at a probability of not less than $ε e^{K R_{j}}$ . In our study, the target points are deployed as grids.

To address the second issue, we can employ any of the algorithms presented in Chen et al.,¹¹ Yen et al.,¹³ Usman et al.,¹⁴ and Qin et al.^15,16 to deal with the point coverage problem. The literature¹³ reported lifetime-maximized target coverage on the basis of game theory. However, the number of targets was only 10–60, which could not satisfy the number level of target points. The greedy idea¹⁷ can be used to activate sensors and ensure that each target point satisfies the coverage requirement. However, the balance problem among sensors is not fully considered, resulting in many undesirable results, including numerous redundant and related nodes, unbalanced energy consumption, and shortened network life cycle, as shown in Chen et al.,¹¹ Yang et al.,¹² Qin et al.,¹⁶ and Altinel et al.¹⁷

In addition to target points, the research results on node subsets might not be directly applied to our study, although these conclusions are very inspiring. Generally, sensor nodes can be divided into subsets and take turns to monitor the area of interest.^3,18–20 As a result, the system’s lifetime is considerably extended. Genetic algorithm aims at finding the maximum number of disjoint complete sensor cover sets in Hu et al.,¹⁹ but its full coverage demand is more stringent than our ε-coverage requirement. The literature²⁰ addressed the node subset problem by activating the part of sensors that forms several approximate equilateral triangles to cover the entire area of interest. However, the algorithm is unsuitable for randomly deployed sensor networks because the formation of an approximate triangle cannot be guaranteed on the basis of activated nodes only.

The last issue is the minimal-cost problem for node subset. To reduce costs, Sarkar et al.²¹ and Chen et al.²² built a subset of nodes by scheduling nodes into sleep state or wake-up state at a particular time. However, their work needs support from clock-offset estimation, which is not a common capability of sensor networks. Mathematical models of coverage and energy consumption were considered in Amirhosein and Mohsen²³ and Yu et al.²⁴ to select a minimum cost subset of nodes among deployed nodes. However, the specified deployment was not applied to random networks. Linear programming was used in Amjad et al.²⁵ to investigate the lifetime sequence of wireless sensor networks (WSNs). Although a method to maximize lifetime was not provided directly, the key influencing factors were discussed, and the importance of linear programming in applications was revealed. The biological evolution idea can be adopted to demonstrate the effectiveness of node subsets in new applications.^18,19,26,27 Node subsets were properly selected and activated in many existing studies, in which an intelligent algorithm was combined with optimal planning. The literature¹¹ introduced the particle swarm optimization (PSO) algorithm based on the index perception model for maximizing the lifetime of WSNs. Compared with the greedy algorithm, PSO exhibited a longer lifetime but had lower convergence speed. Improved ant colony optimization was proposed in Lin et al.¹⁸ to maximize the lifetime of heterogeneous WSNs, and this algorithm can consider coverage and connectivity simultaneously. However, these improved algorithms possess high computational complexity because it consumes a large amount of time in the global search procedure.

The literature²⁸ was inspired by the Jenga game and presented a Jenga-inspired optimization algorithm (JOA) to balance the optimal solution and short computation time. This algorithm can select a minimum-cost node subset through the roulette method without considering the independence of players and their competitive weights. We improved JOA in our previous work and constructed a node subset with minimum relevance and cost; the improved JOA benefited from the additional independence of players and bios of the sensor.¹⁵

This article presents the area coverage algorithm based on differential evolution (ACADE), which is a balance-idea-based algorithm that uses improved differential evolution (DE)²⁹ without parameter variation. In this algorithm, the requirements for balanced cost and minimal energy for each node are regarded as repairing factors. When the algorithm is combined with variation, crossover, selection, and other operations in DE, the population search range is expanded, and convergence up to the optimal solution is accelerated. The presented compensation strategy repairs node subsets of coverage. Accordingly, under given coverage demands with balanced cost and minimal energy, satisfactory node subsets and increased lifetime are provided by ACADE.

Network model

Background

The given area of interest A has $N_{s}$ nodes with uniform physical properties and $N_{I}$ target points. The locations, sensing radii r, and communication radii $R_{c}$ of these nodes are known. $R_{c} = 2 r$ ²⁶ is set to ensure connectivity and coverage. Several key elements are defined as follows: the set of sensor nodes is $S = {s_{1}, s_{2}, \dots, s_{i}, \dots s_{N_{S}}}$ , and the set of target points is $P = {p_{1}, p_{2}, \dots, p_{j}, \dots p_{N_{I}}}$ , where $s_{i} = {x_{S_{i}}, y_{S_{i}}, r}$ and the location of $s_{i}$ is $(x_{S_{i}}, y_{S_{i}})$ .

Given a unit of time slice $t_{S}$ and number of lifetime $T_{S}$ , the network lifetime is $T_{S} t_{S}$ . Without any ambiguity, $T_{S}$ is selected to represent the network lifetime. For each slice $t_{S}$ , the energy consumed by the sensor nodes in the active state is fixed, whereas that in the sleep state is negligible. The weight of nodes is the energy cost $c_{i}$ , which can increase with increasing energy consumption.³⁰ $c_{i}$ can be shown as follows

c_{i} = k^{E_{R, i}}

(1)

where $k \in (0, 1)$ is a characteristic constant for a sensor node. The remaining energy of node $s_{i}$ is presented as $E_{R, i}$ . In a given $t_{S}$ , our algorithm recursively activates several nodes to form a node subset with minimal cost. The higher the remaining energy of the nodes is, the higher the priority is scheduled in the active state.

Coverage model

If the probabilistic sensing model is used in our study, then target point $p_{j}$ is detected by sensor node $s_{i}$ in the following model¹¹

λ_{s_{i}} (p_{j}) = {\begin{matrix} 0 d (i, j) > r_{u} \\ e^{- a {(d (i, j) - r_{s})}^{β}} r_{s} < d (i, j) \leq r_{u} \\ 1 d (i, j) \leq r_{s} \end{matrix}

(2)

where $d (i, j)$ is the Euclidean distance between $s_{i}$ and $p_{j}$ . If $r_{s} = r - r_{e}$ and $r_{u} = r + r_{e}$ , then $r_{e}$ shows the uncertainty of the node during the monitoring process. a and $β$ are the attenuation coefficients of sensing quality when $d (i, j)$ falls within the range of $(r - r_{e})$ to $(r + r_{e})$ .

Target point $p_{j}$ is generally detected by more than one node. A certain node subset covering $p_{j}$ is called $S_{j}$ , where $S_{j} \subset S$ . The detected probability of the node by $S_{j}$ is shown as follows

λ (p_{j}) = 1 - \underset{s_{i} \in S_{j}}{Π} (1 - λ_{s_{i}} (p_{j}))

(3)

According to Chen et al.,¹¹ if $λ (p_{j}) \geq ε e^{K R_{j}}$ , then the coverage ratio of a circle plane is not less than $ε$ . Thus, if all target points with coverage ratios not less than $ε e^{K R_{j}}$ are deployed as grids (Figure 1), then the coverage ratio of the area of interest is not less than $ε$ . In our future studies, we will only consider meeting the new coverage threshold $\bar{ε} = ε e^{K R_{j}}$ for the target points. For the distance between target points, L can determine $R_{j}$ .

Figure 1.

Relationship between the area of interest and the target points.

Description of our problem

Given an area of interest, the sensor network aims to achieve a maximal lifetime to consume minimal cost in covering the target points $P = {p_{1}, p_{2}, \dots, p_{j}, \dots p_{N_{I}}}$ . According to Yen et al.,¹³ this coverage problem can be formulated as an integer programming problem as follows

Min \sum_{i = 1}^{N_{S}} c_{i} x_{i}

(4)

S . t . \forall p_{j} \in P, \sum_{i = 1}^{N_{S}} α_{ij} x_{i} \geq δ, x_{i} \in {0, 1}

(5)

where $α_{ij} = - \ln (1 - λ_{s_{i}} (p_{j}))$ . $x_{i} = 1$ indicates that $s_{i}$ is activated; otherwise, $x_{i} = 0$ . $δ$ varies with $ε$ because $δ = - \ln (1 - \bar{ε})$ . Equation (5) reveals that the node number is required to meet the coverage demand for every target point.

DE with non-parametric variation

Classical DE

Our effective coverage problem is minimum optimization; therefore, the proposed ACADE employs DE with the repaired factor on the basis of the balance idea. Prior to the introduction of ACADE, the solution of the minimum optimization problem using classical DE should be explained. A case of minimum optimization is considered as follows

Min f (y_{1}, y_{2}, \dots, y_{D})

(6)

S . t . y_{j min} \leq y_{j} \leq y_{j max} (j = 1, 2, \dots, D)

(7)

The dimension of an independent variable is D, and $y_{j min}$ and $y_{j max}$ are the lower and upper bounds for $y_{j}$ , respectively. The steps of classical DE are depicted as follows:

Step 1: initialization. NP D-dimensional vectors constitute each generation population $y_{i, g} = {y_{i, 1, g}, \dots, y_{i, D, g}}$ , where $i = 1, 2, \dots, NP$ . Its initial value is defined as follows

y_{i, j} = y_{j min} + r a n d • (y_{j max} - y_{j min})

(8)

where rand is one random value in the interval $(0, 1)$

Step 2: variation. DE achieves individual variation through the following difference process

v_{j, g} = y_{r 0, g} + F • (y_{r 1, g} - y_{r 2, g})

(9)

where F is the scaling factor. r0, r1, and r2 are random unequal integers in ${1, 2, \dots, NP}$ , where r0, r1, and r2 are not equal to i.

Step 3: crossover. The variation and target vectors are used to generate child individual $u_{i, g} = u_{i, 1, g}, \dots, u_{i, D, g}$ to improve population diversity. The crossover operation is as follows

u_{i, g} = {\begin{matrix} v_{i, g}, i f r a n d < CR or j = j_{r a n d} \\ y_{i, g}, o t h e r w i s e \end{matrix}

(10)

where CR is the crossover probability factor and $j_{r a n d}$ is randomly selected from ${1, 2, \dots, D}$ .

Step 4: selection. DE uses a greedy strategy to determine the evolutionary individual for the next generation. The strategy details are as follows

y_{i, g + 1} = {\begin{matrix} u_{i, g}, i f f (u_{i, g}) \leq f (y_{i, g}) \\ y_{i, g}, o t h e r w i s e \end{matrix}

(11)

Step 5: termination. If the generation number $g \geq g_{max}$ or the accuracy requirement of the evolution is satisfied, the current optimal results are produced. Otherwise, Step 2 is repeated.

Improved scaling factor

Using the power function, we improve the scaling factor F in Kong et al.²⁹ by designing a binary code without variation. The variant individuals $v_{i, g} = {v_{i, 1, g}, \dots, v_{i, D, g}}$ are produced in the discrete domain

v_{i, j, g} = y_{r 0, j, g} + {(- 1)}^{y_{r o, j, g}} • | y_{r 1, j, g} - y_{r 2, j, g} |, j = 1, 2, \dots, D

(12)

We infer only two states for the nodes, namely, active and sleep. Similar to the equation described in section “Description of our problem,” $x_{i} = 1$ when $s_{i}$ is active; otherwise, $x_{i} = 0$ . In this study, $y_{i, j, g}$ is the state variable of $s_{i}$ and is specified as 1 or 0. Therefore, $| y_{r 1, j, g} - y_{r 2, j, g} |$ can be 0 or 1. Equation (12) implies that the value of a variant individual can be 0 or 1. This closure operation result suggests that the proposed improved DE is unbiased.

The above variation is essentially an XOR operation process, and the difference vector $| y_{r 1, j, g} - y_{r 2, j, g} |$ determines whether an individual can exist or not. When $| y_{r 1, j, g} - y_{r 2, j, g} | = 1$ , $y_{r 0, j, g}$ initializes state reversal, that is, state “0” is changed to “1” or state “1” is changed to “0.” When $| y_{r 1, j, g} - y_{r 2, j, g} | = 0$ , nothing happens. The former case is a variation that benefits population diversity. The latter maintaining state can increase the probability of $y_{r 1, j, g} = y_{r 2, j, g}$ , thereby accelerating the convergence.

ACADE

Our effective coverage problem can be described as a minimum optimization problem. Thus, DE is a good choice to solve this problem, in which the node subset of coverage is considered an individual in a population, the dimension of the individual is the size of the subset, and the value of each dimension indicates the node state (active or sleep). The global exploration capability of an individual is enhanced after variation, crossover, and selection.

Thus, we expect to obtain a node subset (named as an individual in DE) with a suitable minimal size and satisfactory coverage performance but without any non-significant nodes. The results of DE as a heuristic method depend on the initial value. Thus, this process cannot always search for an absolutely perfect resulting individual. The individual in DE is only a node subset in coverage. Two types of cases are discussed.

In the first case, the resulting individual, also known as the node subset, cannot satisfy coverage demands. Numerous nodes should be activated for addition to this individual. Those sleeping nodes, which can maximize the increase in coverage ratio in the target point with the lowest coverage ratio, should be activated. In the second case, for individuals that satisfy coverage demands, there are redundancy active nodes. Those active nodes, which can maximize the decrease in coverage ratio in the target point with the highest coverage ratio, should be slept.

Regardless of whether an individual (node subset) satisfies coverage demands or not, the individual should be adjusted repeatedly in each time slice to become the best one. The adjusted subset can only satisfy coverage demands without any redundant nodes, which will not consume too much energy. By combining coverage and energy, the conception of bios $Ψ_{S, i} (T) = I_{S, i} (T) • E_{R, i} (T)$ ²⁸ is introduced to characterize the efficiency of the node, where $I_{S, i} (T)$ is the number of target points that can be covered by $s_{i}$ and $E_{R, i} (T)$ is the remaining energy of node $s_{i}$ in the $T th$ slice, such that $0 \leq T \leq T_{s}$ . The two presented notions, namely, positive and negative utility ratios, express the value of whether the node is in active or sleeping mode. These notions are the two benchmarks to push the node into different states.

Positive utility ratio

When a node is in the active state, its state value is the positive utility ratio. In the $T th$ time slice, the positive utility ratio $Ω_{p o s, s_{i}, p_{j}} (T)$ of $s_{i}$ in target point $p_{j}$ is the product of the coverage ratio of node $s_{i}$ in target point $p_{j}$ and the remaining energy of node $s_{i}$

Ω_{p o s, s_{i}, p_{j}} (T) = λ_{s_{i}} (p_{j}) • E_{R, i} (T)

(13)

where $E_{R, i} (T)$ is the remaining energy of node $s_{i}$ in the $T th$ time slice. For node $s_{i}$ , with increasing coverage performance $λ_{s_{i}} (p_{j})$ or remaining energy $E_{R, i} (T)$ , $Ω_{p o s, s_{i}, p_{j}} (T)$ will increase. Jointing coverage and energy, $Ω_{p o s, s_{i}, p_{j}} (T)$ can measure the contribution of $s_{i}$ in target point $p_{j}$ .

Negative utility ratio

Similarly, the value of a node in the sleeping state is the negative utility ratio. The negative utility ratio $Ω_{n e g, s_{i}, p_{j}} (T)$ of node $s_{i}$ in target point $p_{j}$ is shown in equation (14). This ratio is the product of the coverage ratio of node $s_{i}$ in target point $p_{j}$ and the consumed energy of node $s_{i}$

Ω_{n e g, s_{i}, p_{j}} (T) = λ_{s_{i}} (p_{j}) • (E_{R, i} (0) - E_{R, i} (T))

(14)

If $E_{R, i} (T) \leq 0$ , then $λ_{s_{i}} (p_{j}) = 0$ . $Ω_{n e g, s_{i}, p_{j}} (T)$ will identify the weakness of node $s_{i}$ in target point $p_{j}$ . We found that $Ω_{n e g, s_{i}, p_{j}} (T)$ will increase and maybe higher than $Ω_{p o s, s_{i}, p_{j}} (T)$ when its remaining energy $E_{R, i} (T)$ decreases. It means node $s_{i}$ will be more likely go to sleep to avoid exhaust energy.

If the coverage ratio on $p_{j}$ is to be improved, then the node that provides more $Ω_{p o s, s_{i}, p_{j}} (T)$ to $p_{j}$ is prior to be activated because of its greater contribution in maintaining coverage and energy. However, when a lower coverage ratio on $p_{j}$ is required (i.e. there are redundant nodes), the node that provides more $Ω_{n e g, s_{i}, p_{j}} (T)$ to $p_{j}$ is put into sleep easily.

Steps of ACADE

Simple DE can be used to search for node subsets up to the coverage standard. The resulting node subsets are not guaranteed to have minimal energy, and the maximum lifetime is uncertain. We improve the scaling factor in the variation to expand the search range. We introduce a compensation strategy to rebuild the node subset and cover the target points on the basis of resource balance and maximum lifetime. ACADE is implemented as follows.

Algorithm 1. ACADE.
Step 1: Initialization: The area of interest A, sensor nodes $S = {s_{1}, s_{2}, \dots, V_{i}, \dots s_{N_{S}}}$ , target points $P = {p_{1}, p_{2}, \dots, p_{j}, \dots p_{N_{I}}}$ , $T = 0$ , $T_{S} = 0$ , $g = 0$ , $ε$ , $c_{i}$ , $λ (A_{j})$ , $E_{R, i} (T)$ , and $\bar{ε}$ are calculated.
Step 2: NP random 0–1 vectors with $N_{S}$ dimensionality are randomly generated in A. These vectors act as the initial populations $y_{i, g} = {y_{i, 1, g}, \dots, y_{i, j, g}, \dots, y_{i, N_{s}, g}}$ , where $i = 1, 2, \dots, NP$ , and $j = 1, 2, \dots, N_{S}$ .
Step 3: If $y_{i, g}$ does not satisfy equation (5), then the compensation strategy described in section “Compensation strategy” is applied.
Step 4: The fitness values are calculated for father individuals using equation (4).
Step 5: Based on equation (12), variant individual $v_{i, j, g}$ is adopted.
Step 6: The offspring individuals $u_{i, j, g}$ are calculated based on equation (10). If these individuals $u_{i, j, g}$ cannot satisfy equation (5), then the compensation strategy described in section “Compensation strategy” is applied.
Step 7: The fitness values are calculated for $u_{i, j, g}$ using equation (4).
Step 8: $y_{i, g + 1}$ is selected according to equation (11).
Step 9: $g = g + 1$ . If $g < g_{max}$ , then the process is repeated from Step 5.
Step 10: $T = T + 1$ , $E_{R, i} (T)$ , and $c_{i}$ are updated for every sensor node, and $λ_{s_{i}, p_{j}} (T)$ and $λ (p_{j})$ are updated for every target point $p_{j}$ .
Step 11: If $y_{i, g}$ does not satisfy equation (5), this algorithm is repeated from Step 2.
Step 12: $T_{S} = T$ . This algorithm is then terminated.

The variation $y_{i, j, g}$ can only be set to “0” or “1” because sensors can only be in the “sleep” or “active” state. The problem of binary encoding is thus solved in passing, which is an important issue in the evolutionary algorithm.

Compensation strategy

In the resulting generation populations of classical DE, not all perfect node subsets reach the coverage accuracy. A compensation strategy for imperfect node subsets is presented to rebuild node subsets with minimal costs and to balance the energy cost and network lifetime. The assumption that $H$ is a subset is amended, and the compensation strategy is described as follows.

Algorithm 2. Compensation strategy.
Step 1: $λ_{s_{i}} (p_{j})$ and $λ (p_{j})$ are calculated for each active node $s_{i} \in H$ and target point $p_{j}$ .
Step 2: If $H$ satisfies equation (5), then the algorithm skips to step 7.
Step 3: For each target point $p_{j}$ , $\bar{ε} - λ (p_{j})$ is calculated such that one target point with the maximum difference assures one point $p_{inc}$ , which is required to improve the coverage ratio.
Step 4: For each sleeping node $s_{k} \in H$ , its coverage ratio is $λ_{s_{k}, p_{inc}} (T)$ on $p_{inc}$ , and the remaining energy and positive utility ratio $Ω_{pos, s_{k}, p_{i n c}} (T)$ are calculated.
Step 5: The sleeping nodes are listed in terms of descending $Ω_{p o s, s_{k}, p_{inc}} (T)$ . The nodes are awakened one by one until equation (5) is satisfied. The awakened nodes are recorded in a new subset $H_{1}$ . Step 10 is then performed.
Step 6: All nodes of $H_{1}$ are listed in terms of ascending remaining energy. According to the redundant eligibility rule, the redundant nodes are pushed into sleep in turn. The node states in $H$ are updated on the basis of $H_{1}$ .
Step 7: For each target point $p_{j}$ , $λ (p_{j}) - \bar{ε}$ is calculated such that one target point with the maximum difference assures a certain $p_{d e c}$ , which is permitted to decrease its own coverage ratio.
Step 8: The coverage ratio $λ_{s_{i}} (p_{d e c})$ on $p_{d e c}$ and negative utility ratio $Ω_{n e g, s_{i}, p_{d e c}} (T)$ are calculated for each active node $s_{i}$ in H.
Step 9: The active nodes are listed in terms of descending $Ω_{n e g, s_{i}, p_{d e c}} (T)$ . According to a sleep eligibility rule, these nodes decide whether to go to sleep or not. The node states in $H$ are updated.
Step 10: The algorithm is terminated.

Two criteria are considered. First, the redundant eligibility rule states that a node is redundant if the coverage performance is not diminished when this node goes into the sleep state. Otherwise, that node is not redundant. Second, the sleep eligibility rule states that if a certain active node goes to sleep and the resulting node subset still satisfies equation (5), then this active node can be pushed into the sleep state. Otherwise, the active state should be maintained.

Figure 2 shows the relation among several presented algorithms mentioned in sections “DE with non-parametric variation” and “ACADE.” With classical DE, our ACADE shows improved key steps, as shown in the following flowchart. Variation, crossover, and selection are performed to acquire the improved node subset.

Figure 2.

Relation among several presented algorithms.

Simulation analysis

Scenario

The MATLAB platform is used in the simulation. Area of interest A is set as a square zone covering 100 m × 100 m, and the target points are deployed in each 1 m × 1 m grid. The sensor nodes are randomly positioned, and the probabilistic sensing mode is employed. Each sensor node has primary energy of 1 J, and 0.1 J is spent in one-unit time slice. The sensor node can last 10 slices in the active state.

To evaluate the number of activated nodes, effectiveness, and availability, we compare ACADE with PSO,¹¹ JOA,^15,28 and our previous balanced rate area coverage algorithm (BRACA)¹⁶ through random simulation experiments with multiple settings. The configuration parameters are listed in Table 1. The experimental parameters can significantly influence the algorithms’ performance. To ensure a fair comparison, we refer to the algorithms’ original literature and set their experimental parameters to a similar coverage level.

Table 1.

Parameters of the four compared algorithms.

Parameter	PSO	JOA	BRACA	ACADE
$r_{s}$	15	15	15	15
a	0.05	0.05	0.05	0.05
K	0.05	0.05	0.05	0.05
$ε$	0.9	0.9	0.9	0.9
k	0.5	0.5	0.5	0.5
−	$M = 2$	$M_{P} = 4$	$MP = 4$	$NP = 10$
−	$M_{c} = 10$	$N_{T} = 10$	$K = 0.05$	$g_{max} = 5$
−	$ω = 0.99$	$θ_{s} = 0.9$	$τ = 2$	CR = 0.9
−	$c_{1} = 2.5$	$θ_{e} = 0.4$	L = 1 (m)	L = 1 (m)
−	$c_{2} = 1.5$	$T_{\max} = 4$	$α_{ij} \leq - \ln (1 - e^{- 1})$	F = –1

PSO: particle swarm optimization; JOA: Jenga-inspired optimization algorithm; BRACA: balanced rate area coverage algorithm; ACADE: area coverage algorithm based on differential evolution.

In consideration of randomness sourcing from the algorithms and scenes, we average the resulting data based on 30 random trials in the following simulations, except for special instructions.

Topological structural analysis

We illustrate the working process for one ACADE case with 250 sensor nodes. Figure 3(a)–(d) shows several topological structures when the sensor network is in the starting phase, the 1st time slice, the 62th time slice, and the last slice ( $T_{S} = 124$ ). An increasing number of sensor nodes are activated to maintain the coverage requirement $ε = 90 %$ , whereas several nodes have to quit the active state because of exhausted energy. The number of activated sensor nodes increases with the lifetime cycle. Hence, the longer lifetime cycle $T_{s}$ is, the more sensor nodes will be needed.

Figure 3.

Network topology in four phases: (a) starting phase ( $T = 0$ ); (b) $T = 1$ ; (c) $T = 62$ ; and (d) last slice ( $T_{s} = 124$ ).

Number of activated nodes

The number of activated nodes that will vary with the different scopes of the sensor networks is determined. The experiment is repeated 1000 times for each scene, and the average result is obtained and shown in Figure 4. Seven scenes (N_s = 100, 150, 200, 250, 300, 350, and 400) are considered in this test. The average numbers of activated sensor nodes are nearly the same, that is, 22. However, their medians slowly decrease with increasing N_s and result in approximately 15 (i.e. 14.7). The maximal number in each scene increases with increasing N_s, where the maximal numbers in N_s = 100, 150, 200 are nearly 54. Further increase in N_s increases the maximal numbers. Although N_s = 400 shows the highest number of activated nodes, its quartile and median are lower than those of several scenes. This result illustrates that ACADE can efficiently control the number of activated sensor nodes.

Figure 4.

Number of active sensor in scenarios.

Residual energy analysis

The four algorithms (ACADE, PSO, JOA, and BRACA) are run 100 times with N_s = 250, and their average residual energies are presented in Figure 5. ACADE and BRACA show obvious advantages in lifetime and energy efficiency because of the presented balance idea. The energy of PSO is consumed more rapidly than that in the others. JOA provides better energy efficiency than PSO because of its combination of two essential factors, namely, the remaining energy and the number of covered target points. The proposed ACADE shows the gentlest decrease in energy consumption among all of the algorithms, resulting in the longest lifetime. This phenomenon is due to the introduction of the compensation strategy in the improved DE to determine an improved coverage node subset, and the presented balance idea is beneficial in extending the lifetime.

Figure 5.

Average residual energy analysis ( $N_{S} = 250$ ).

Lifetime analysis

The lifetimes of the four algorithms are compared and analyzed in the various scenarios in Figure 6. BRACA shows the longest lifetime when $N_{S} \in [100, 150]$ , and ACADE shows the longest lifetime when $N_{S} \in [160, 400]$ . These results are caused by more than one factor. The balance idea is used to control energy and prevent a high cost for a certain node. The improved DE algorithm with no parameter variation can extend the population-search scope when determining the minimum-cost node subset. The two utility ratios are introduced to repair the node subset that does not satisfy the coverage constraints. These factors accelerate the convergence speed in the exploration of the optimum results.

Figure 6.

The lifetime varying with $N_{S}$ .

Time cost analysis

The operational efficiencies of the four algorithms are evaluated by comparing their average machine time costs. Figure 7 shows their fluctuating times in different cases. BRACA is an efficient algorithm because of its shortest operation time, whereas PSO shows the lowest operating efficiency.

Figure 7.

Analysis of average computation time in different scenarios.

In BRACA and JOA, M_P = 4 players are considered to select the node subset. However, an upper bound $- \ln (1 - ε e^{(\sqrt{2} aL / 2)})$ exists for $α_{ij}$ to avoid the tedious calculation among infinite values in BRACA.¹⁶ Thus, BRACA shows the lowest time cost. For JOA, M_P = 4 players are called together for not more than N_T = 10 recursions to select the proper node subset by the roulette method depending on node independence. Thus, the time cost of JOA is slightly higher than that of BRACA. Unlike BRACA, ACADE, and JOA, PSO has to adopt sufficient populations to perform numerous iterations and produce the minimal node set. Accordingly, PSO consumes the largest amount of time among all of the algorithms.

Although ACADE originates from biological evolution as same as PSO, an additional compensation strategy is integrated to avoid high complexity. NP = 10 populations perform not more than $g_{max} = 5$ times of iterative evolution in ACADE. Hence, the time cost of ACADE is lower than that of PSO, as shown in Figure 6.

Comprehensive comparison

Table 2 presents the performance evaluations for the four algorithms on the basis of the simulation results. We provide four levels to describe their working quality. PSO and JOA are poor at balancing energy, and they cannot solve the energy inefficiency problem. Consequently, their quality levels are poor. ACADE is good at saving energy and maintaining the longest lifetime. However, BRACA exhibits better operation efficiency than ACADE. A certain method cannot easily gain effectiveness and efficiency. Thus, we will apply ACADE in inconvenient battery replacement in the future. For real-time applications, BRACA is the best among all of the compared algorithms.

Table 2.

Comparison of the four algorithms in different tests.

Performance level (excellent/good/average/bad)		ACADE	BRACA	JOA	PSO
Effectiveness	Average residual energy	Excellent	Good	Average	Bad
Effectiveness	Average lifetime	Excellent	Good	Average	Bad
Efficiency	Average machine cost time	Good	Excellent	Average	Bad

ACADE: area coverage algorithm based on differential evolution; BRACA: balanced rate area coverage algorithm; JOA: Jenga-inspired optimization algorithm; PSO: particle swarm optimization.

Conclusion

Improved DE is used in this study to solve the area coverage problem. Several considerable merits are added to the proposed ACADE. Non-parametric variation is adopted as the scaling factor for DE, from which our algorithm framework is established. The operation processes, such as population variation, crossover, and selection, help expand the search range of node subsets. The presented compensation strategy, which exploits positive and negative utility ratios, repairs the node subset. All introduced techniques guide networks to determine the minimal cost node subset in each time slice and reach the coverage standard.

Although negative factors are disregarded in this study because optimal assumptions can make the research feasible, highly realistic environment settings and modules are still important. Specifically, terrain morphology, magnetic condition, and climate station should be considered in the coverage model. Future research will focus on combining our resulting work and a realistic model to achieve improved energy consumption efficiency and coverage performance.

Footnotes

Handling Editor: Marco Scarpa

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: All the authors appreciate the supports from the Chinese National Natural Science Foundation, No. 61702228, Jiansu National Natural Science Foundation, No. BK20170198, the 11th Batch of Jiangsu “Six Level Talents Peak” Project, No. DZXX-026, Jiangsu Planned Projects for Postdoctoral Research Funds, No. 1601012A, and the Fundamental Research Funds for the Central Universities, No. JUSRP1805XNC.

References

Sun

Zheng

Chen

et al . An energy-effective clustering algorithm for multilevel energy heterogeneous wireless sensor networks. In: Proceedings of the 2nd IEEE international conference on advanced computer control (ICACC 2010), Shenyang, China, 27–29 March 2010, vol. 3, pp.168–172. New York: IEEE.

Ren

Huang

Lin

Wireless sensor networks. J Softw 2003; 14(7): 1282–1291.

Akyildiz

Sankarasubramaniam

et al . Wireless sensor networks: a survey. Comput Netw 2002; 38(4): 393–422.

Aldawsari

Barker

England

Trusted energy-efficient cloud-based services brokerage platform. Int J Intell Comput Res 2015; 6(4): 630–639.

Al-Darsari

Barker

Tawfik

et al . GreeDi: an energy efficient routing algorithm for big data on cloud. Ad Hoc Netw 2015: 35: 83–96.

Baker

Nogoko

Tolosana-Calasanz

et al . Energy efficient cloud computing environment via autonomic meta-director framework. In: 2013 sixth international conference on developments in esystems engineering, Abu Dhabi, United Arab Emirates, 16–18 December 2013, pp.198–203. New York: IEEE.

Baker

Asim

Tawfik

et al . An energy-aware service composition algorithm for multiple cloud-based IoT applications. J Netw Comput Appl 2017; 89: 96–108.

QW.

Energy efficient coverage control algorithm for wireless sensor networks. J Chin Comput Syst 2011; 32(2): 233–236.

Sengupta

Das

Nasir

et al . Multi-objective node deployment in WSNs: in search of an optimal trade-off among coverage, lifetime, energy consumption, and connectivity. Eng Appl Artif Intel 2013; 26(1): 405–416.

10.

Kasbekar

Bejerano

Sarkar

Lifetime and coverage guarantees through distributed coordinate-free sensor activation. IEEE/ACM T Network 2011; 19(2): 470–483.

11.

Chen

et al . Energy-efficient coverage based on probabilistic sensing model in wireless sensor networks. IEEE Commun Lett 2010; 14(9): 833–835.

12.

Yang

et al . Energy-efficient probabilistic full coverage in wireless sensor networks. In: 2012 IEEE global communications conference, Anaheim, CA, 3–7 December 2012, vol. 64, issue 1, pp.591–596. New York: IEEE.

13.

Yen

Lin

Leung

VCM

. Distributed lifetime-maximized target coverage game. ACM Trans Sens Netw 2013; 9(4): 1–23.

14.

Usman

Har

Koo

Energy-efficient infrastructure sensor network for ad hoc cognitive radio network. IEEE Sens J 2016; 16(8): 2775–2787.

15.

Qin

Chen

Ding

ZG.

Maximum-minimum set dispatching algorithm based on respective biogen. J Chin Comput Syst 2015; 36(5): 1059–1063.

16.

Qin

Chen

Ding

ZG.

Balanced rate area coverage algorithm. Chin J Sens Actuat 2015; 28(4): 578–584.

17.

Altinel

Aras

Gney

et al . Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor networks. Comput Netw 2008; 52(12): 2419–2431.

18.

Lin

Zhang

Chung

et al . An ant colony optimization approach for maximizing the lifetime of heterogeneous wireless sensor networks. IEEE T Syst Man Cy C 2012; 42(3): 408–420.

19.

Zhang

et al . Hybrid genetic algorithm using a forward encoding scheme for lifetime maximization of wireless sensor networks. IEEE T Evolut Comput 2010; 14(5): 766–781.

20.

Hefeeda

Ahmadi

Energy-efficient protocol for deterministic and probabilistic coverage in sensor networks. IEEE T Parall Distr 2010; 21(5): 579–593.

21.

Sarkar

Venkatesha

Rajan

et al . Sleeping beauty: efficient communication for node scheduling. In: 2016 IEEE 13th international conference on mobile ad hoc and sensor systems, Brasilia, Brazil, 10–13 October 2016, pp.56–64. New York: IEEE.

22.

Chen

Zhao

A reinforcement learning-based sleep scheduling algorithm for desired area coverage in solar-powered wireless sensor networks. IEEE Sens J 2016; 16(8): 2763–2774.

23.

Amirhosein

Mohsen

. Effect of heterogeneity on coverage, energy consumption and connectivity of wireless sensor networks. In: 25th Iranian conference on electrical engineering (ICEE 2017), Tehran, Iran, 2–4 May 2017, pp.1923–1928. New York: IEEE.

24.

Wan

Cheng

et al . Coverage contribution area based k-coverage for wireless sensor networks. IEEE T Veh Technol 2017; 66(9): 8510–8523.

25.

Amjad

Hong

Satyajayant

Maximizing lifetime sequences of wireless sensor networks powered by renewable energy. Sensor Rev 2014; 34(4): 374–381.

26.

Fang

Zhu

et al . Differential evolution for lifetime maximization of heterogeneous wireless sensor networks. Math Probl Eng 2013; 2013: 172783.

27.

Ozan

Özgur

. Node placement with evolutionary algorithms for maximum coverage of heterogeneous WSNs. In: 25th signal processing and communications applications conference (SIU), Antalya, 15–18 May 2017, pp.1–4. New York: IEEE.

28.

Lee

JJ.

Jenga-inspired optimization algorithm for energy-efficient coverage of unstructured WSNs. IEEE Wirel Commun Le 2013; 2(1): 34–37.

29.

Kong

Gao

YHB

et al . Binary differential evolution algorithm based on parameterless mutation strategy. J Northeast Univ 2014; 35(4): 484–487.

30.

Huang

Hung

Yang

et al . Energy-efficient probabilistic target coverage in wireless sensor networks. In: Proceedings of the 2011 17th IEEE international conference on networks, Singapore, 14–16 December 2011, pp.53–58. New York: IEEE.

An area coverage algorithm for wireless sensor networks based on differential evolution

Abstract

Keywords

Introduction

Network model

Background

Coverage model

Description of our problem

DE with non-parametric variation

Classical DE

Improved scaling factor

ACADE

Positive utility ratio

Negative utility ratio

Steps of ACADE

Compensation strategy

Simulation analysis

Scenario

Topological structural analysis

Number of activated nodes

Residual energy analysis

Lifetime analysis

Time cost analysis

Comprehensive comparison

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References