A new approach to solving target coverage problem in wireless sensor networks using an effective hybrid genetic algorithm and tabu search

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

Wireless sensor networks cover set formation scheduling algorithms genetic algorithm Tabu search

1 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.

2 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.

3 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. 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.

Fig. 1

List of notations.

Problem: How to organize available sensors into a number of cover sets each of which capable of covering all targets in the network and simultaneously extend the network lifetime as much as possible. To organize the sensors, the mode of each sensor is determined to be either active or passive and the best sensing ranges of the active sensors are identified.

Definition 1: A cover set is essentially consisted of a subset of minimal adjusted sensors capable of providing all the targets in the network with full coverage.

Definition 2: A target is critical if the network lifetime provided by the minimal adjusted sensors monitoring it is less than that of the other targets.

4 Proposed hybrid algorithm for MNLAR

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

Step 1: Setting the parameters of the proposed algorithm

Step 2: Initializing the population and setting generation

Step 3: Evaluating each chromosome in the population based on the defined objective

Step 4: Checking whether the termination criteria is met?

If yes, going to Step 7

If no, going to Step 5

Step 5: Generating the new population

Step 5.1: Using the genetic operators (selection, crossover, and mutation) to generate the new population

Step 5.2: Applying TS algorithm to improving the quality of each chromosome

Step 6: Setting Gen to Gen +1 and going to Step 3

Step 7: Obtaining the best solution as the output

(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].

Representation: When working with genetic algorithm to solve the problems in real-life situations, a key issue is how to model the problem in hand. In our problem, modelling can be done adopting two different approaches: sensor oriented and target oriented. In the senor-oriented approach, the length of a chromosome is set to the number of sensors in the network, and the value of a gene shows which sensing range has been selected by its corresponding sensor for coverage of the targets. On the other hand, in the target-oriented approach, the length of a chromosome is set to the number of targets in the network, and the value of a gen corresponding to a target shows which sensor with which one of its sensing ranges has been chosen to provide coverage on the targets. In the present paper, each chromosome stands for a cover set, and each cover set is capable of covering all targets in the network. It is worth mentioning that chromosomes in the sensor-oriented models cannot guarantee the construction of such cover set. In addition, authors in [23, 24] have confirmed the higher effectiveness of the target-oriented approach in terms of solving the coverage problem in DSNs. Accordingly, this study adopts the target-oriented approach to solve the problem. Thus, it uses an integer-based vector to model each chromosome, where its length is represented by m showing the total number of targets that exist within the network. In this study, each gene of the chromosome shows the status of a single target. At the time of allocating a value to genes of a chromosome, at first, the most critical target is identified and a value is allocated to its gene. In other words, the algorithm chooses a minimal adjusted sensor from among minimal adjusted sensors that monitor the target in hand. Note that in sensors with adjustable sensing range, at a given time, only one sensing range of a single sensor can be used in the process of creating a cover set. Therefore, once a sensing range of a sensor is chosen to assign a value to the gene of a given target, the other sensing ranges of the same sensor cannot be used for the same task. Modeling a chromosome this way results in having a valid chromosome that is able to cover all targets in the network. As we know, in random deployment environments, the number of targets is smaller than sensors; therefore, the use of this model shortens the length of the created chromosome, which finally results in saving a significant amount of memory.

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. t₁ = {(s₁, 1) , (s₂, 2)} , t₂ = {(s₁, 2) , (s₃, 2)} , t₃ = {(s₃, 1) , (s₄, 2)} , t₄ = {(s₅, 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 t₂ 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 (s₁, 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.

Fig. 2

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

Fig. 3

An example chromosom for the network.

Initial population: In population-based algorithms such as GA, after a solution to the problem is modeled as a chromosome, we need to produce an initial population of chromosomes. In this paper, we produce a set of chromosomes as the initial population where each chromosome is denoted by a set of integer numbers.

Fitness: In general, fitness function in evolutionary algorithms is widely used due to its implicit and explicit effects on direction of the search. If the fitness function is appropriately set for the give problem, sufficient information will be available in terms of the search direction, and appropriate candidate solutions can be clearly taken out of the inappropriate ones. In this paper, the amount of energy consumed by the sensors in the cover set is taken into account as fitness function. Remember that the amount of energy consumption depends on which sensing range of the sensors is selected to construct cover set. It is desirable to have smaller sensing ranges in the constructed cover set since in this condition, less energy will be consumed for coverage process. As a result, the solutions (chromosomes) with less amount of energy consumption are more desirable; in other words, our problem in this study is minimization problem. Let us assume that the batteries can keep the sensors active for 1 unit of time at power level 1 while 0.5 unit at power level 2. For example, the fitness function of the chromosome shown in Fig. 3 is 3. To this end, we calculate the energy consumption of the constructed cover set concerning which sensors with which one of their sensing ranges have participated in the cover set.

Selection: This paper makes use of the binary tournament selection method in order to choose two parents for the crossover operation. To this end, two chromosomes from among the current population are chosen in a random and uniform way; next, their fitness values are compared with each other. This way, the better chromosome is selected (with probability p) as one of the parents; otherwise, the other one is chosen. To select the second parent, the same procedure is performed.

Crossover and mutation: In the present paper, a single point crossover operator is applied to the production of a child chromosome from the two selected parents. For this purpose, the crossover point is selected randomly; then, the parent chromosomes exchange their own information (see Fig. 4). As mentioned earlier, in WSNs containing sensors with adjustable sensing range, only one sensing range of each sensor is employed at a given time. As a result, after the crossover operation, invalid chromosomes are possible to be produced (see Fig. 4.Child B). A chromosome is invalid if multiple sensing ranges of a single sensor are used in allocating values to its genes. To give validity to an invalid chromosome, a repair operator is proposed in this study. The mutation operation starts after a valid chromosome is produced. Through this operation, a gene of the chromosome is chosen randomly and its value is changed. In other words, the value of a gene that corresponds to a target is shifted to a new value chosen from the other minimal adjusted sensors that cover the same target. Note that when a new value is chosen for mutation operation, we need to avoid invalidity of the chromosome. To this end, after choosing a minimal adjusted sensor to allocate value to a gene, the value must be compared with those of the other genes of the chromosome. If the value chosen does not make the chromosome invalid, it is applied; otherwise, another value needs to be selected.

Fig. 4

An example of single point crossover operation.

Repair operator: To make sure of the feasibility of the child chromosome generated through the crossover operation, the repair operator proposed in [23] was modified to be applicable to the present study. The operator takes the value of the gene that corresponds to each of the targets. Each value holds two parameters, namely the sensor number and the sensing range of the sensor applied to a chromosome. Afterwards, the repair operator checks whether the other sensing ranges of that sensor are in the list of the sensing ranges that allocate value to genes corresponding to other targets. If yes, values of the invalid genes need to be changed. Such process continues until all genes hold a valid value.

Stopping criterion: The stopping criterion of the proposed algorithm is reaching up to the maximum number of consecutive iterations.

Local search by Tabu Search: TS pioneered by Glover et al. (1997) is a meta-heuristic method. This method has been found effective in solving different combinatorial optimization problems. TS enables the searching process to find permitted solutions that do not reduce the objective function value. Such solution can be found through keeping track of the final solution regarding the action that is done for the purpose of transforming one solution to the next. TS comprises a number of elements such as the move attributes, the neighborhood structure, aspiration criteria, the tabu list, and the termination criteria [26]. The present paper makes use of TS as a local search strategy in the proposed HA for MNLAR. The general TS process is elaborated as follows:

Step 1: Setting the parameters of TS; setting tabu list to empty mode; producing the initial solution and setting it as the current solution

Step 2: Checking whether the stopping criteria are met

If yes, going to Step 8

If not, going to Step 3

Step 3: Generating the novel neighborhood solutions with the use of the neighborhood function, and then evaluating the solutions

Step 4: Checking whether the aspiration criteria are met

If yes, going to Step 6

If not, going to Step 5

Step 5: Choosing the optimal solution, which is not tabu solution in the neighborhood solutions and then setting it as the current solution, and going to Step 7

Step 6: Setting the solution that meets the aspiration criteria as the current solution and the optimal solution; then, going to Step 7

Step 7: Updating the tabu list and going to Step 2

Step 8: Obtaining the optimal solution as the output

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.

5 Simulation results

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.

Experiment 1. In this experiment, we changed the number of sensors from 60 to 100, with incremental step 10 in order to examine the impact of the number of sensors on the network lifetime. As shown by the results in Fig. 5, when the number of sensors in the network increased, the network lifetime also increased. The reason of this direct relationship was that with an increase in the number of sensors, each target can be monitored by more sensors; this helped the algorithm form more cover sets each of which had more prolonged activation time. The comparative results, confirmed the superiority of the proposed GA-based algorithm over the other algorithms in terms of extending the network lifetime. The reason of this success was management of the critical targets in the process of cover set formation. Fig. 6 shows the number of cover sets formed by different algorithms. As shown by the results, GA formed the smallest number of cover sets. Of course it was not worrying since our algorithm was mainly aimed to maximize the network lifetime; therefore, in the cover set formation process, it attempted to select the sensors with minimum sensing range; which resulted in creation of cover sets with more prolonged activation time.

Fig. 5

Effect of the number of sensors on the network lifetime.

Fig. 6

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

Experiment 2. In this experiment, the number of targets were examined in terms of their effect on the network lifetime. For this purpose, this parameter was changed from 6 to 14, with incremental step 2. As shown by the results reported in Fig. 7, an increase in the number of targets caused the network lifetime to decrease. This was due to the fact that with more targets, more minimal adjusted sensors were naturally needed to monitor them. This exhausted energy of the sensors sooner. Fig. 8 shows how the number of targets affects the amount of energy each cover set consumes. Fig. 8 shows that increasing the number of targets results in an increase in the amount of energy each cover set consumes. It is because in this condition, to cover more targets, more sensors are required. As shown by the obtained results, GA consumes higher amount of energy compared to the other algorithms; the reason is that this algorithm uses more sensors of the network and, on the other hand, it forms fewer cover sets.

Fig. 7

Effect of the number of targets on the network lifetime.

Experiment 3. This experiment examined the relationship between the sensing range and the network lifetime. To do this, the sensing range was set to 80(m) to 120(m), with incremental step 10(m). The obtained results presented in Fig. 9 show a direct relationship between them; that is, increasing the sensing rang expanded the network lifetime. The reason was that with increasing the sensing range, the sensors were actually given chance to monitor more targets; therefore, fewer sensors would be needed to provide full coverage for all targets in the network. Comparison of the results obtained from the proposed GA-based algorithm with those of the other two algorithms showed better performance of the GA-based one in achieving a more expanded network lifetime.

Fig. 8

Effect of the number of targets on the energy consumption.

Fig. 9

Effect of sensing range on the network lifetime.

6 Conclusion

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.

References

Mohamadi

, Salleh

and Razali

M.N.

, Heuristic methods tomaximize network lifetime in directional sensor networks withadjustable sensing ranges, Journal of Network and Computer Applications 46 (2014), 26–35.

Mohamadi

, Salleh

, Razali

M.N.

and Marouf

, A new learningautomata-based approach for maximizing network lifetime in wirelesssensor networks with adjustable sensing ranges, Neurocomputing 153 (2015), 11–19.

Yick

, Mukherjee

and Ghosal

, Wireless sensor network survey, Computer Networks 52(12) (2008), 2292–2330.

Zhu

, Zheng

, Shu

and Han

, A survey on coverage andconnectivity issues in wireless sensor networks, Journal ofNetwork and Computer Applications 35(2) (2012), 619–632.

Cardei

, Thai

, Li

and Wu

, Energy-efficient target coverage in wireless sensor networks, In Paper presented at the IEEE INFOCOM 2005.

Cardei

and Du

D.-Z.

, Improving Wireless Sensor Network Lifetimethrough Power Aware Organization, Wireless Networks 11(3) (2005), 333–340.

Mostafaei

and Meybodi

M.R.

, Maximizing lifetime of targetcoverage in wireless sensor networks using learning automata, Wireless Personal Communications 71(2) (2013), 1461–1477.

Mohamadi

, Ismail

A.S.

, Salleh

and Nodhei

, Learningautomata-based algorithms for finding cover sets in wireless sensornetworks, The Journal of Supercomputing 66(3) (2013), 1533–1552.

Mohamadi

, Ismail

A.S.

and Salleh

, Solving target coverageproblem using cover sets in wireless sensor networks based onlearning automata, Wireless Personal Communications 75(1) (2014), 447–463.

10.

Cerulli

, De Donato

and Raiconi

, Exact and heuristic methodsto maximize network lifetime in wireless sensor networks withadjustable sensing ranges, European Journal of OperationalResearch 220(1) (2012), 58–66.

11.

Zorbas

, et al., Solving coverage problems in wireless sensornetworks using cover sets, Ad Hoc Networks 8(4) (2010), 400–415.

12.

Mohamadi

, Ismail

and Salleh

, A learning automata-basedalgorithm for solving coverage problem in directional sensornetworks, Computing 95(1) (2013), 1–24.

13.

Mohamadi

, Ismail

A.S.

, Salleh

and Nodehi

, Learningautomata-based algorithms for solving the target coverage problem indirectional sensor networks, Wireless Personal Communications 73(3) (2013), 1309–1330.

14.

Mohamadi

, Ismail

A.S.

and Salleh

, Utilizing distributedlearning automata to solve the connected target coverage problem indirectional sensor networks, Sensors and Actuators A: Physical 198 (2013), 21–30.

15.

Mohamadi

, Salleh

, Ismail

A.S.

and Marouf

, Schedulingalgorithms for extending directional sensor network lifetime, Wireless Networks 21(2) (2015), 611–623.

16.

Ting

C.-K.

and Liao

C.-C.

, A memetic algorithm for extendingwireless sensor network lifetime, Information Sciences 180(24) (2010), 4818–4833.

17.

Razali

M.N.

, Salleh

and Mohamadi

, Solving priority-basedtarget coverage problem in directional sensor networks withadjustable sensing ranges, Wireless Personal Communications 95(2) (2017), 847–872.

18.

Goldberg

D.E.

, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc. (1989).

19.

Cardei

, Wu

and Lu

, Improving network lifetime using sensorswith adjustable sensing ranges, Int J Sen Netw 1 (2006), 41–49.

20.

Arivudainambi

, Sreekanth

and Balaji

, Energy Efficient Sensor Scheduling for Target Coverage in Wireless Sensor Network, In: Zeng Q-A (ed) Wireless Communications, Networking and Applications, New Delhi, 2016. Springer India (2016), 693–705.

21.

Dhawan

, Vu

C.T.

, Zelikovsky

, Li

and Prasad

S.K.

, Maximum Lifetime of Sensor Networks with Adjustable Sensing Range, In: Seventh ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD’06) (2006), 285–289.

22.

Mohamadi

, Salleh

and Ismail

A.S.

, A learning automata-basedsolution to the priority-based target coverage problem indirectional sensor networks, Wireless Personal Communications 79(3) (2014), 2323–2338.

23.

Alibeiki

, Motameni

and Mohamadi

, A new genetic-basedapproach for maximizing network lifetime in directional sensornetworks with adjustable sensing ranges, Journal of Pervasiveand Mobile Computing 52 (2019), 1–12.

24.

Zannat

, Akter

, Tasnim

and Rahman

, The coverage problemin visual sensor networks: A target oriented approach, Journalof Network and Computer Applications 75 (2016), 1–15.

25.

Wolpert

D.H.

and Macready

W.G.

, No free lunch theorems foroptimization, IEEE Transactions on Evolutionary Computation 1(1) (1997), 67–82. doi: 10.1109/4235.585893.

26.

and Gao

, An effective hybrid genetic algorithm and tabusearch for flexible job shop scheduling problem, InternationalJournal of Production Economics 174 (2016), 93–110.

27.

Chen

Z.G.

, et al., Maximizing Lifetime of Range-Adjustable Wireless Sensor Networks: A Neighborhood-Based Estimation of Distribution Algorithm, IEEE Transactions on Cybernetics, (2020), 1–12.

28.

Arivudainambi

, et al., Cuckoo search algorithm for target coverage and sensor scheduling with adjustable sensing range in wireless sensor network, Journal of Discrete Mathematical Sciences and Cryptography, (2020), 1–22.

29.

Javan Bakht

, et al., A learning automata-based algorithm forsolving the target k-coverage problem in directional sensor networkswith adjustable sensing ranges, Physical Communication 42 (2020), 101156.

30.

Javan Bakht

, Motameni

and Mohamadi

, A learningautomata-based algorithm to solve imbalanced k-coverage in visualsensor networks, Journal of Intelligent & Fuzzy Systems 39 (2020), 2817–2829.