Abstract
Literature in recent years has introduced several studies conducted to solve the target coverage problem in wireless sensor networks (WSNs). Sensors are conventionally assumed as devices with only a single power level. However, real applications may involve sensors with multiple power levels (i.e., multiple sensing ranges each of which possesses a unique power consumption). Consequently, one of the key problems in WSNs is how to provide a full coverage on all targets distributed in a network containing sensors with multiple power levels and simultaneously prolong the network lifetime as much as possible. This problem is known as Maximum Network Lifetime With Adjustable Ranges (MNLAR) and its NP-completeness has been already proved. To solve this problem, we proposed an efficient hybrid algorithm containing Genetic Algorithm (GA) and Tabu Search (TS) aiming at constructing cover sets that consist of sensors with appropriate sensing ranges to provide a desirable coverage for all the targets in the network. In our hybrid model, GA as a robust global searching algorithm is used for exploration purposes, while TS with its already-proved local searching ability is utilized for exploitation purposes. As a result, the proposed algorithm is capable of creating a balance between intensification and diversification. To solve the MNLR problem in an efficient way, the proposed model was also enriched with an effective encoding method, genetic operators, and neighboring structure. In the present paper, different experiments were performed for the purpose of evaluating how the proposed algorithm performs the tasks defined. The results clearly confirmed the superiority of the proposed algorithm over the greedy-based algorithm and learning automata-based algorithm in terms of extending the network lifetime. Moreover, it was found that the use of multiple power levels altogether caused the extension of the network lifetime.
Keywords
Introduction
Generally, wireless sensor networks (WSNs) contain a number of tiny, cheap, low-power sensor nodes distributed randomly within an area of interest in order to provide coverage on some elements in the environment like humidity, temperature, light, voice, and video. A variety of environments can be covered by WSNs, including undersea, forests, borders, battle fields, and urban areas [2, 3]. Target coverage is one of the most significant applications of WSNs, which refers to covering a set of fixed or moving targets in the network. As sensors work based on battery power and the batteries are not rechargeable, we need to not only solve the target coverage problem, but also maximize the network lifetime [4].
In this paper, we are to solve the target coverage problem in cases where sensors hold multiple sensing ranges (i.e., each sensor has more than one power level each of which consumes a certain amount of energy). We aim to maximize the network lifetime that refers to the amount of time during which the coverage operation can be continued. In [10, 15], this problem is termed Maximum Network Lifetime with Adjustable Ranges (MNLAR). To accomplish this aim, the use of power saving mechanisms is a good idea. These mechanisms, which optimize the energy consumption of the sensors, can be classified into two techniques: 1) scheduling sensors by switching between their active and sleep modes, and 2) adjusting sensing range of the sensors. Scheduling technique is applied to environments in which sensors are distributed densely. Some of the available sensors are kept active and the others are switched to sleep mode in order to efficiently control the energy consumption in the network. For the adjusting technique, each sensor is assumed with multiple sensing ranges. In this condition, increasing the sensing range rises the amount of energy consumed. In the other words, the use of sensors with adjustable sensing ranges causes two new challenges: 1) the expansion of search space, which happens because of the increase of the number of possible activation modes, and 2) energy allocation of higher complexity; this is due to the fact that when sensors use different sensing ranges, they consume different amounts of energy. Due to the above-mentioned challenges, it is a big challenge to find direct solutions to the problem of maximizing the lifetime of WSNs with range-adjustable sensors [5, 11–14].
Every algorithm has some advantages and disadvantages, and any single algorithm cannot be expected to solve all optimization problems [25]. As a consequence, the present study prefers to propose a hybrid model containing two algorithms, i.e., GA and TS, for exploration and exploitation purposes. GA has been recognized for its powerful global searching capacity, whereas TS has been widely used for its capacity for local searching purposes. The model proposed in this paper integrates the advantages of both above-mentioned algorithms to provide an acceptable balance between intensification and diversification. The ultimate goal is to solve the MNLR problem addressed in this paper. To do this more efficiently, we take advantage of both power saving techniques: scheduling and adjusting. The proposed algorithm operates in a several rounds each of which results in a cover set. To form an appropriate cover set, the algorithm searches to find the best solution from among the possible solutions obtained through applying the GA operators and TS. The cover set formation process goes on until all the targets in the network are provided with full coverage. A number of experiments were carried out to examine the proposed algorithm performance concerning the network lifetime, and the obtained results were compared with those of some other works introduced in literature. The final results showed that the proposed model outperformed the others in terms of maximizing the network lifetime.
The current study has the following contributions: 1) addressing the target coverage problem in WSNs containing sensors with adjustable sensing ranges, 2) designing an efficient hybrid algorithm containing GA and TS in order to solve the problem, 3) developing a repair operator for the enhancement of the algorithm’s performance quality, and 4) designing several simulations with the aim of evaluating the effectiveness of the proposed algorithm.
The rest of the paper is organized as follows: Section 2 gives a brief review of the studies reported in literature related to target coverage problem. Section 3 presents an introduction to MNLAR problem in WSNs. Section 4 gives a brief description of the genetic algorithm and proposes a hybrid genetic algorithm and tabu search to solve the problem in hand. Section 5 reports the experiments conducted to test the efficiency of the proposed algorithm and the obtained results. Finally, Section 6 concludes the paper.
Related work
In this paper, we center on finding a solution to the target coverage problem using both power saving techniques, scheduling and adjusting. In the following, some of brilliant studies conducted to solve this problem in WSNs using the above-mentioned techniques are discussed.
Several studies have been published in recent years focusing on the target coverage problem in WSNs through the use of scheduling techniques. Cardeiet al., [5] were among the first researchers who addressed this problem in WSNs and modeled it as disjoint cover sets each of which was able to cover all targets in the network. In addition, they confirmed the NP-completeness of the target coverage problem. In [6], the previous study was extended to non-disjoint cover sets in which each sensor could participate in more than one cover set. The researchers in [11] proposed two greedy-based algorithms to maximize the number of constructed cover sets and, at the same time, manage the critical targets. In [7–9, 22], several learning automata-based scheduling algorithms were introduced to solve the target coverage problem. The authors in [16] made use of the optimization capacity of the memetic algorithms to solve the problem.
In all approaches mentioned above, the sensors are assumed with fixed sensing ranges. Though, sensors in recently-designed applications are mostly with adjustable sensing ranges [27]. This shift in adjustability of the sensors’ sensing range has resulted in new challenges to the process of scheduling the sensors’ activities. Note that when sensing range has the capacity to be adjusted, the sensor’s activation mode is no longer binary (sleep/activated), but it is multilevel. As a result, the search space for exploring the coverage schemes would be enlarged. Furthermore, sensors with different sensing ranges would require different quantities of energy for the same length of time. This means that the sensors activated in one coverage scheme might have different remaining amounts of energy left after activation. In this condition, those sensors that have abundant remaining energy are capable of continuing their monitoring tasks, which could be taken into consideration when forming other coverage schemes to achieve higher levels of energy efficiency. Nonetheless, the fact that one sensor is allowed to join more than one coverage scheme causes the energy allocation problem more complex. The literature consists of only a few new scheduling approaches applicable to managing such challenges.
In this sense, the authors in [19] addressed the same problem in networks containing sensors with multiple sensing ranges that can be naturally adjusted to obtain more efficient solutions. In addition, a number of heuristics were proposed on the basis of both greedy and LP relaxation methods, aiming to prolong the network lifetime as much as possible. In [21], an approximation algorithm was introduced as a solution to the target coverage problem; it was aimed to maximize the network lifetime. The authors in [20] model the target coverage problem as Sensor Cover with Adjustable Sensing Range (SC-ASR) and proposed a memetic algorithm to solve the problem. In [10], the researchers attempted to solve the MNLAR problem that had been formerly known as Maximum Network Lifetime Problem (MLP). They developed an approach on the basis of a delayed column generation technique and also a greedy-based heuristic was developed, which was embedded in a local search scheme.
In [27], a neighborhood-based estimation of distribution algorithm is proposed to find a solution to the problem. Instead of suggesting a direct solution to the problem, the algorithm divides the problem into two sub-problems: 1) forming a set of coverage schemes, and 2) determining the activation time of each coverage scheme in a way to best allocate the sensors’ energy with the aim of maximizing the network lifetime. It is obvious that the solution proposed for the first sub-problem will comprise an idea for solving the second one. Indeed, in case all the possible coverage schemes in a WSN are explored, it will be possible to model the second sub-problem as a linear programming problem. In this problem, the activation time of each scheme could be allocated in an optimal way so that their sum, the network lifetime, could be maximized. Though, since the problem has a large search space, enumerating all the coverage schemes is extremely difficult or even impossible. In [2], an LA-based algorithm was proposed to solve the MNLAR problem. The algorithm consisted of two phases: initialization and sensing node selection. In the first phase, three operations were done: creating an automata network, defining the action-set of the automata, and defining the their action probability vector. In the second phase, a set of appropriate adjusted sensors were selected by LA in order to form a cover set. To have an appropriate cover set as output at the end of each round, the automata network in each stage of the algorithm forms a possible cover set from among the ones that can be potentially formed. Next, optimality of the constructed cover set is measured using a random environment. In this study, WSN is considered as the random environment of LA. The environment calculates the total energy consumed by minimal adjusted sensors existing in the cover set and generates a response to optimality. In other words, to mark out an appropriate cover set from among other cover sets, the amount of energy consumed by the cover sets is used as criteria. The process of forming a cover set goes on until a cover set consuming minimum amount of energy is constructed.
In [28], the authors addressed the problem of target k-coverage with adjustable sensing range in WSNs and attempts to formulate the problem as a non-linear integer programming problem for the purpose of maximizing the network lifetime. The problem has been already proved as an NP-hard one; as a result, an improved cuckoo search algorithm is developed in this paper to schedule the available sensors. This algorithm divides the sensor set into non-disjoint set covers with adjustable sensing range so that each cover monitors each target with k requirement. Several simulations were carried out to assess the efficiency of the proposed algorithm.
In [1], two greedy-based algorithms were proposed to solve the same problem in directional sensor networks(DSNs). In these algorithms, the power saving techniques were used and it was confirmed that the use of these techniques can have a significant effect on prolonging the network lifetime. Remember that due to limited field of view of directional sensors, they are not applicable to WSNs. In [17], a combination of the two power saving techniques was used to offer a solution to the priority-based target coverage problems in DSNs. In [29], the authors addressed the problem of target k-coverage with adjustable sensing range in DSNs. They proposed two learning automata-based algorithms, which are both provided with a strong pruning rule for facilitating the selection of the best sensor directions that can provide k-coverage for all the targets within the network.
In [29], the authors addressed the problem of target k-coverage with adjustable sensing range in DSNs. They proposed two learning automata-based algorithms, which are both provided with a strong pruning rule for facilitating the selection of the best sensor directions that can provide k-coverage for all the targets within the network. In [30], the authors addressed the problem of imbalanced k-coverage in visual sensor networks. They proposed a learning automata-based algorithm capable of selecting a minimum number of sensors in a way to provide k-coverage for all targets in a balanced way. Although many efforts have been made in the literature, there is still a need for an algorithm to solve the MNLAR problem in effectively.
The problem of maximum network lifetime with adjustable ranges
The following scenario is taken into consideration. Several targets with known locations are distributed in a given field and a number of sensors with adjustable sensing ranges are scattered within the same field in order to cover the targets. Each sensor cover all targets situated in its operational range. The sensors have a limited energy resource and also they are normally activated for a finite number of alternative power levels (sensing ranges). Each sensing range of a sensor (depending on its size) holds a notion showing its battery consumption [10]. The sensors in this network are alike in two parameters: initial battery power and the energy consumed for each level. The sensors are assumed non-rechargeable. Power levels extend gradually the sensing range of the sensors; therefore, for each sensor s i and each level a > 1, we have T(s i , b) ⊆ T(s i , a) ∀ b ∈ {1, . . . , a - 1}. Moreover, the adjusted sensor (s i , a) is defined as minimal adjusted sensor for target t j if t j ∈ T(s i , a) and either a = 1 or t j ∉ T(s i , b) ∀ b ∈ {1, . . . , a - 1}.
To model various battery consumptions, a positive parameter Δ a is applied to each power level a [10]. The parameter Δ a denotes the ratio of battery consumption at level a to level 1 that is the weakest level, hence the cheapest one. For instance, Δ a = 2 shows that level a consumes 2 times more energy compared to level 1. Obviously, Δ1 = 1. In addition, we normalize the total battery power on the energy consumption of level 1. In other words, a battery keeps a sensor active for 1 time unit if it is set to level 1. The notations used in this paper are as follow.

List of notations.
In this section, we propose a new algorithm hybridizing GA and TS (which is a guided local search algorithm) in order to solve MNLAR problem. Literature offers a number of methods for designing hybrid algorithms. The present study inserts TS into the GA process to do local searching. In this algorithm, the network operates in several rounds each of which results in a cover set capable of covering all targets in the network. The procedure of one round of the proposed algorithm is shown in Algorithm 1. When the current round of the algorithm is terminated and a cover set is formed, the algorithm calculates the maximum activation time that the minimal adjusted sensors in the cover set can hold. The value of this time is then added to total network lifetime. Afterwards, the residual energy of the sensors participating in the cover set is updated based on which sensing ranges of the sensors have been used in the cover set construction process. Then, the sensors without any residual energy are removed from the set of available sensors. The cover set formation process goes on until all the targets in network are provided with full coverage. Finally, the formed cover sets and their activation times are returned as the algorithm output. In the following, the main steps of the proposed hybrid algorithm is described in detail.
GA is a meta-heuristic approach applied to the solution of different optimization problems. In the initial step, this algorithm randomly generates a population of possible solutions. Each solution is denoted by a string of genes termed chromosome or individual. Quality of the chromosomes is tested using a fitness function. Following the generation of the initial population, the algorithm performs three operations: selection, crossover, and mutation. Through the selection operation, a set of possible solutions is selected from among the initial population. Afterwards, two selected chromosomes
Algorithm 1 : Proposed Algorithm
If yes, going to Step 7
If no, going to Step 5
(parents) are applied to production of two child chromosomes by crossover operation where the genetic information is exchanged between the parent chromosomes. Then the child chromosomes perform the mutation operation in order to generate a better solution. In order to improve the quality of each chromosome, a new function is added to the GA algorithm. The new function is applicable to all individuals of the current population; but the problem is that it is computationally costly. In our case, tabu search is applied with a small probability. This parameter is able to effectively tune the convergence of GA since TS typically well improves the individuals. After this operation is done, the fitness function is used again to evaluate the child chromosomes. A comparison is done between the values of these chromosomes and those of all the chromosomes belonging to previous generation. Finally, from among the initial population and the population produced through the crossover and mutation operations, those with better fitness value are selected as the next generation. As the evolution process continues, GA attempts to drive the search toward the global optima [18].
To illustrate the model in hand, here we present an example. As depicted in Fig. 2, the network is consisted of five sensors and four targets. Each sensor in this network has two sensing ranges. The minimal adjusted sensors covering each target are as follow. t1 = {(s1, 1) , (s2, 2)} , t2 = {(s1, 2) , (s3, 2)} , t3 = {(s3, 1) , (s4, 2)} , t4 = {(s5, 1)}. As the number of targets is fixed at 4, the length of each chromosome is set to 4, too. In other words, each gene shows the status of one target. The beginning step of creating a chromosome is identifying the most critical target. As target t2 is the first target identified as being critical, the algorithm starts allocating a value to its gene. In other words, a minimal adjusted sensor from among all minimal adjusted sensors monitoring that target is chosen (we call it (s1, 2)). Next, if any other sensing range of the same sensor is in the list of the minimal adjusted sensors monitoring other targets, it is eliminated from that list. The process, during which a critical target is selected and a value is allocated to its gene, goes on until formation of the chromosome in hand is accomplished (i.e., all genes are allocated with their appropriate values). Fig. 3 shows an example chromosome.

Example network with five adjustable sensors, four targets and two sensing ranges.

An example chromosom for the network.

An example of single point crossover operation.
If yes, going to Step 8
If not, going to Step 3
If yes, going to Step 6
If not, going to Step 5
The HA in the present study ends once either the maximum number of generations is obtained or the permitted maximum step size is attained without any improvement. On the other hand, TS ends its operation once the maximum number of iterations is reached.
In this section, the performance of the proposed algorithm is evaluated through conducting a number of experiments testing the impact of different parameters on the network lifetime. To model a WSN, m targets were distributed in an area of size 500(m) ∗ 500(m) and then n homogenous sensors with identical sensing radius were also deployed in the vicinity of the targets to monitor them. In these experiments, each sensor held multiple sensing ranges; at each unit of time, only one of the sensing range of a single sensor could be selected to cover the targets. By default, in all experiments, each sensor had one unit of energy, and the number of targets and sensors were fixed at 10 and 100, respectively. Additionally, each sensor’s radius was set to 100(m) and the number of its sensing ranges was fixed at 4. To do the experiments with a higher reliability, each simulation scenario was run for 10 times and the average network lifetime was calculated for each scenario. To have a more accurate evaluation of the proposed algorithm performance, the obtained results were compared to those of two recently-proposed algorithms, namely a greedy-based algorithm [10] and an LA-based algorithm [2]. In the proposed algorithm, the population size was set to 60, and the probability of crossover and mutation was fixed at 0.2 and 0,05, respectively.

Effect of the number of sensors on the network lifetime.

Effect of the number of sensors on the number of cover sets.

Effect of the number of targets on the network lifetime.

Effect of the number of targets on the energy consumption.

Effect of sensing range on the network lifetime.
This paper presents a hybridized model containing GA (for its evolutionary searching capability) and TS (for its capability in local searching) in order to solve the MNLR problem. The objective of the proposed model is to form cover sets that can provide all targets within the network with a desirable coverage and, simultaneously, consume minimum amount of energy aiming for maximizing the network lifetime. In this paper, we combined two techniques, i.e., scheduling and adjusting, in order to select sensors with appropriate sensing ranges, which led to maximizing the network lifetime. Several experiments were carried out to check the efficiency of the proposed algorithm performance, and the obtained results were compared with those of some other algorithms introduced already in literature. The final results showed the superiority of the proposed algorithm in terms of forming cover sets with minimum amount of energy consumption, hence having a significantly extended network lifetime.
