# Wireless Sensor Network Coverage Optimization: Comparison of Local Search-Based Heuristics

Authors: Krzysztof Trojanowski; Artur Mikitiuk
Journal: Applied Computational Intelligence and Soft Computing
 (2022)

---

## Abstract

The Maximum Lifetime Coverage Problem (MLCP) requires heuristic optimization methods due to its complexity. A real-world problem model determines how a solution is represented and the operators applied in these heuristics. Our paper describes adapting a local search scheme and its operators to MLCP optimization. The operators originate from three local search algorithms we proposed earlier: LSHMA, LSCAIA, and LSRFTA. Two steps of the LS scheme’s main loop can be executed in three different ways each. Hence, nine versions of the LS approach can be obtained. In experimental research, we verified their effectiveness. Test cases come from three benchmarks: SCP1, proposed and used in our earlier research on the three LS algorithms mentioned above, and two others found in the literature. The results obtained with SCP1 showed that the algorithm based on the hypergraph model approach (HMA) is the most effective. The remaining results of the other algorithms divide them into two groups: effective ones and weak ones. However, other benchmarks showed that the more redundant the coverage of points of interest (POIs) by sensors, the more effective the perturbation method from the approach inspired by cellular automata (CAIA). The findings expose the strengths and weaknesses of the problem-specific steps applied in the LS algorithms.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) are essential parts of IT solutions in many applications: military, like battlefield surveillance, and civil ones, including forecast systems, environment observation, or habitat monitoring [1]. Sensors can be integrated into numerous electronic devices and machines. Moreover, due to the advances in semiconductor and microelectromechanical technologies and the miniaturization of computing and sensing technologies, sensors and microcontrollers are tiny, consume low power, and are inexpensive. Thus, WSNs may consist of large numbers of small yet powerful devices cooperating in large areas. WSNs aim to monitor a region or a set of targets for collecting valuable information for modeling and forecasting situations in the area or controlling the usage of resources. In WSNs consisting of miniature devices, monitoring quality becomes an energy efficiency issue due to limited battery capacities.WSN lifetime maximization techniques depend on two main components of a problem model. The first is objective, e.g., network lifetime optimization, coverage, connectivity, or transmission parameters. The second one represents WSN design constraints, for example, communication medium, resource limits, fault tolerance and self-organization, QoS requirements, or mobility and deployment [2]. In our research, we focus on the issues concerning network lifetime maximization, that is, the maximization of an uninterrupted interval when the network satisfies the level of coverage above a certain threshold under some resource-limited constraints. Our research concerns a simplified network model, where sensors remain immobile once deployed, and their connectivity is always guaranteed. We assume that individual sensor placement is infeasible due to environmental conditions, such as monitoring a disaster area or a battlefield. Therefore, sensors are randomly scattered over the monitored field. Sensors have a finite battery capacity. Thus, after the drain, they should be replaced or recharged. However, we assume that neither of these options is applicable due to the operating conditions. So, once the energy reserve is depleted, the sensor is regarded as irretrievably lost to the network. The network is equipped with an external solid computational unit responsible for optimally scheduling and distributing tasks among the network devices.We assume that sensors have uniform batteries and sensing ranges and have to monitor a set of targets also called points of interest (POIs). When the number of sensors is extensive and their monitoring ranges overlap, some sensors can be off while the required level of coverage is still satisfied. In this case, the optimization aims to find a sensor activity schedule with the longest makespan and guarantee a sufficient coverage level. This class of problems is called the Maximum Lifetime Coverage Problem (MLCP). The approaches to solving MLCP are based on different models of real-world circumstances; thus, they have different structures of the solution and the complexity of the problem.In this paper, we develop local search strategies enriched by problem-specific procedures originating from three algorithms we proposed earlier: LSHMA, LSCAIA, and LSRFTA. The strategies share the same execution scheme. In the beginning, they find a first feasible schedule that becomes a preliminary solution to the problem. Then, iteratively, they generate its neighbor and try to refine it. The new solution takes the place of its ancestor when we gain an improvement. The advantage of these strategies lies in the neighbor generation (so-called perturbation) and refinement procedures, which take advantage of some model-specific properties.In recent years, many heuristic approaches have been proposed; thus, quite naturally, an idea arose to verify the efficiency of hybrid heuristic algorithms composed of components of various origins. Unfortunately, some approaches do not share the same model of the real-world problem and the same set of constraints. Therefore, their integration into one method is a nontrivial task and sometimes even questionable. However, this is not the case for LSHMA, LSCAIA, and LSRFTA, where the approaches share the same model of the real-world problem and the structure of the solution representation. Hence, one can easily use selected problem-specific steps as exchangeable building blocks. Eventually, we constructed nine local search strategies by swapping the two steps: perturbation and refinement, from each of the three approaches. Then, we evaluated their performance experimentally.The main contribution of this paper lies in generating nine heuristics, based on the building blocks originating from three other existing approaches, and experimentally verifying their efficiency. We used three benchmarks for testing the performance of the heuristics: SCP1, provided in our earlier publications [3–6]; the benchmark from [7, 8]; and the benchmark from [9].The paper is organized as follows. Related work is briefly discussed in Section2. Section 3 formally defines the Maximum Lifetime Coverage Problem (MLCP). The local search approach is introduced in Section 4. Section 5 describes our experiments with LS algorithms for MLCP. Our conclusions are given in Section 6.


## 2. Related Work

The majority of MLCP solving methods are based on two-stage approaches. In the first stage, we solve the Target Coverage Problem by finding the maximum number of sensor sets so that every set can perform the coverage task individually. In the second stage, we solve the Set Coverage Problem by finding the optimal scheduling for the sets of covers obtained in the first stage. The constraint for the sets concerning full coverage of POIs proposed in the first publications, for example, in [10], was later relaxed in [11] by introducing the required minimum percentage of coverage constraint.The sets of covers are of minimum cardinality and can be disjoint or non-disjoint. In the disjoint sets, every sensor can be included in one of the sets of covers at most, whereas in the non-disjoint sets, there is no such restriction. In [12], the authors introduce the Disjoint Set Cover (DSC) problem, that is, the problem of finding the maximum number of disjoint covers, where every cover is a set of sensors that together monitor all the POIs, and prove its NP-completeness. The complexity of the case with non-disjoint sets of covers is analyzed in [13], where the Maximum Set Cover (MSC) problem is defined. It is a problem of determining a number of p non-disjoint covers to maximize the network lifetime t1+⋯+tp, where tj,j=1,…,p, is the time interval while the j-th cover is active. The authors of [13] prove that the MSC problem is also NP-complete.Selected papers on MLCP optimization with Disjoint and Non-Disjoint Set Cover based approaches are presented in Table1 (DSC) and Tables 2 and 3 (NDSC). For information about sensor activity scheduling strategies for other WSN lifetime optimization definitions, the reader is referred to surveys and monographs, for example, [1, 2, 35, 36].Table 1
Selected papers on MLCP optimization with Disjoint Set Cover based approaches.
No.ReferenceYearBrief information about the approach and its optimization goal1S. Slijepcevic and M. Potkonjak [10]2001The most constrained–minimally constraining covering heuristic maximizes the cardinality of the set of covers2M. Cardei and D. Z. Du [12]2005The problem of set cover maximization converted into maximum-flow problem is modeled and solved by mixed integer programming (MIP), and then a heuristic computes the covers based on the solution returned by MIP3C.-C. Lai et al. [14]2007A genetic algorithm finds the maximum number of covers using the idea of critical sensors (the sensors covering the most sparsely covered POIs) to find an upper bound of the number of covers4X.-M. Hu et al. [15]2010The schedule transition hybrid genetic algorithm with the forward encoding scheme for the representation of chromosomes and problem-specific operators maximizes the number of covers and schedules them for makespan maximization5N. Ahn and S. Park [16]2011a binary integer programming formulation and heuristics compute the maximum number of covers6J.-M. Gil and Y.-H. Han [17]2011A genetic algorithm using a two-dimensional chromosome and problem-specific operators finds and schedules a given number of covers for makespan maximization in directional sensor networks7R. Cerulli et al. [18]2012A greedy heuristic and exact approach based on the column generation technique find the maximum number of covers8Y. Lin et al. [19]2012An ant colony optimization-based approach finds the maximum number of covers9M. E. Keskin et al. [20]2014The period iteration heuristic and the sequential assignment heuristic maximize four design issues: sensor locations, activity scheduling, data, and mobile sink routes integrated into an integer linear programming model10L. Wang et al. [21]2017Whale group algorithm optimizes the cover in terms of overall network performance: coverage, node utilization, and energy consumption11S. Balaji et al. [22]2020a cuckoo search algorithm finds the maximum number of coversTable 2
Selected papers on MLCP optimization with Non-Disjoint Set Cover based approaches—Part I.
No.ReferenceYearBrief information about the approach and its optimization goal1P. Berman et al. [23]2004For a given series of covers, the method maximizes the sum of activation times of the covers by formulating the problem as a packing linear program2M. Cardei et al. [13]2005(1) The problem of set cover maximization is modeled and solved by the mixed integer programming (MIP), and then a linear programming based heuristic computes the covers based on the solution returned by MIP. (2) A greedy heuristic solves the problem of set cover maximization3D. Zorbas et al. [24]2010A greedy heuristic reinforced by the idea of critical targets (POIs with small neighbor-sensor sets) finds the maximum number of covers which is equal to the schedule makespan since sets provide coverage for the same unit of time4K. Deschinkel [25]2011The column generation based heuristic finds covers and maximizes the sum of activation times of the covers for the problem modeled with a linear programming formulation5Manju and A. K. Pujari [26]2011High-energy-first heuristic finds covers using the highest remaining battery states; the selection priorities change after every execution of the selected set, hence the variety of sets over the network lifetime6H. Mohamadi et al. [27]2013Three learning automata-based scheduling algorithms find both disjoint and non-disjoint covers and then optimize their cardinality7A. Tretyakova and F. Seredynski [28]2013Two approaches—genetic algorithm and memetic algorithm with a two-dimensional representation of schedules (columns: covers; rows: sensors)—maximize the number of feasible covers satisfying the battery capacity restriction in the rows8F. Castaño et al. [29]2014The problem of set cover maximization is solved by the column generation based framework having embedded the greedy randomized adaptive search procedure and the variable neighborhood search9A. Tretyakova and F. Seredynski [7]2015Simulated annealing with a two-dimensional representation of schedules (columns: covers; rows: sensors) maximizes the number of feasible covers satisfying the battery capacity restriction in the rows10Y. E. E. Ahmed et al. [30]2016A genetic algorithm maximizes the number of covers and schedules them for makespan maximization11Y. E. E. Ahmed et al. [31]2016A genetic algorithm with problem-specific operators maximizes the number of covers and schedules them for makespan maximization12A. Tretyakova et al. [8]2016Graph cellular automata approach for cover generation and makespan maximization where cells correspond to sensors, and the neighborhood relation between cells maps the existence of targets or areas commonly monitored by these sensors13K. Trojanowski et al. [4]2017Local search-based approach with problem-specific perturbation operators (LSRFTA) for cover generation and makespan maximizationTable 3
Selected papers on MLCP optimization with Non-Disjoint Set Cover based approaches—Part II.
No.ReferenceYearBrief information about the approach and its optimization goal14K. Trojanowski et al. [5]2017Local search-based approach with a hypergraph model of the WSN and problem-specific perturbation operators (LSHMA) for cover generation and makespan maximization15J. Roselin et al. [32]2017Heuristic for cover generation and makespan maximization where the sensor priority depends on its sensing coverage/connectivity and its remaining energy16Manju et al. [9]2017Minimal heuristic finds covers and maximizes the makespan17A. Tretyakova et al. [33]2017Stochastic greedy heuristic and simulated annealing algorithm maximize the number of feasible covers and optimize their execution times in the way satisfying the battery capacity restriction in the rows18K. Trojanowski et al. [6]2018Local search-based approach with perturbation operator inspired by cellular automata (LSCAIA) for cover generation and makespan maximization19Y. E. E. Ahmed et al. [34]2018An exact method of cover generation based on the sensor coverage relation matrix and using the integer linear programming model20The approach presented in this publication2022Local search-based approaches with the neighbor generation (so-called perturbation) and refinement procedures taking advantage of some model-specific properties and originating from LSHMA, LSCAIA, and LSRFTA for cover generation and makespan maximization


## 3. Maximum Lifetime Coverage Problem (MLCP)

### 3.1. Model of the Real-World Sensor Network

The subject of our research is a network of immobile homogenous sensors monitoring a number of points of interest (POIs). These sensors are randomly distributed over a monitored area. Sensors’ batteries have limited capacity. For energy saving purposes, some sensors can be turned off from time to time. We propose a model of such a network activity where we assume that time is discrete. During every time slot, a sensor can be on or off. When a sensor is off, its energy consumption is negligible. When a sensor is active, it consumes one unit of energy during every time slot. The number of time slots when the sensor can be active, that is, the initial battery load of a sensor, is denoted byTbatt.The model of a sensor considered here is simplified. In real life, the working time of a battery depends on the surrounding temperature and how the battery is used. When we turn it on and off frequently, it discharges more than when we keep it on and off for extended periods. We ignore such problems in this research.We assume that every POI can be covered by at least one sensor. Some POIs can be within the sensing range of multiple sensors. Since an active sensor covers every POI in its sensing range, this means that not all sensors must be active all the time. Moreover, many applications do not need to monitor all POIs all the time. It is often sufficient to monitor 80 or 90% of them anytime. We call this value the required level of coverage and denote it bycov∈0,1. We want to maintain this level of coverage all the time, but to save sensor batteries, we want to keep the coverage level as close to cov as possible. It should not exceed cov by more than the tolerance factor δ (usually 2–5%).In the real world, some sensors not needed for monitoring may be necessary to assure communication within the network. Our simplified model assumes steady sensor connectivity over the network lifetime and negligible energy spent on communication.


### 3.2. Formal Description

Let us formulate the network makespan maximization regarding a scheduling problem as proposed in [37]. We consider NS parallel machines which represent sensors from S=s1,…,sNS and NP POIs from P=p1,…,pNP. Each machine has assigned its task t⋅ consisting of a subset of POIs. The i-th task contains POIs located in the monitoring range of the i-th sensor: tsi=pk,…,pl. An m-th job Jm, where m∈1,…,NJ, consists of some tasks scheduled for being executed simultaneously in a single time slot. The tasks included in a job are not chosen randomly. They identify a set of machines active when this job is executed. That is, they are a set of sensors for which the selection criterion is to cover the requested number of POIs. Each slot has its duration time sdtm; hence, the schedule makespan Msch is a sum of jobs’ duration times: Msch=∑m=1NJsdtm. In further considerations, for simplicity, we assume that sdt equals a time unit, and thus the schedule makespan is the same as the total number of jobs in the schedule NJ.In our experiments, a network activity scheduleH is represented as a 0–1 matrix with rows corresponding to machines and columns corresponding to jobs. The element in row i and column m is equal to 1 (resp., 0) when the machine i is on (resp., off) in job Jm.The required level of coverage constraint says that the cardinality of the sum of POIs in tasks assigned to active machines in the jobJm should be equal to or exceed the cov⋅cardP; that is,t(1)cov⋅cardP≤card∪i=1NStsiifHi,m=1∅otherwise.Moreover, for all machines, the processing time should not exceed the limitTbatt:(2)∑m=1NJHi,m≤Tbatt.The objective is the maximization of the schedule makespanMsch with the required level of coverage and without exceeding the maximum processing time of machines Tbatt.


## 3.1. Model of the Real-World Sensor Network

The subject of our research is a network of immobile homogenous sensors monitoring a number of points of interest (POIs). These sensors are randomly distributed over a monitored area. Sensors’ batteries have limited capacity. For energy saving purposes, some sensors can be turned off from time to time. We propose a model of such a network activity where we assume that time is discrete. During every time slot, a sensor can be on or off. When a sensor is off, its energy consumption is negligible. When a sensor is active, it consumes one unit of energy during every time slot. The number of time slots when the sensor can be active, that is, the initial battery load of a sensor, is denoted byTbatt.The model of a sensor considered here is simplified. In real life, the working time of a battery depends on the surrounding temperature and how the battery is used. When we turn it on and off frequently, it discharges more than when we keep it on and off for extended periods. We ignore such problems in this research.We assume that every POI can be covered by at least one sensor. Some POIs can be within the sensing range of multiple sensors. Since an active sensor covers every POI in its sensing range, this means that not all sensors must be active all the time. Moreover, many applications do not need to monitor all POIs all the time. It is often sufficient to monitor 80 or 90% of them anytime. We call this value the required level of coverage and denote it bycov∈0,1. We want to maintain this level of coverage all the time, but to save sensor batteries, we want to keep the coverage level as close to cov as possible. It should not exceed cov by more than the tolerance factor δ (usually 2–5%).In the real world, some sensors not needed for monitoring may be necessary to assure communication within the network. Our simplified model assumes steady sensor connectivity over the network lifetime and negligible energy spent on communication.


## 3.2. Formal Description

Let us formulate the network makespan maximization regarding a scheduling problem as proposed in [37]. We consider NS parallel machines which represent sensors from S=s1,…,sNS and NP POIs from P=p1,…,pNP. Each machine has assigned its task t⋅ consisting of a subset of POIs. The i-th task contains POIs located in the monitoring range of the i-th sensor: tsi=pk,…,pl. An m-th job Jm, where m∈1,…,NJ, consists of some tasks scheduled for being executed simultaneously in a single time slot. The tasks included in a job are not chosen randomly. They identify a set of machines active when this job is executed. That is, they are a set of sensors for which the selection criterion is to cover the requested number of POIs. Each slot has its duration time sdtm; hence, the schedule makespan Msch is a sum of jobs’ duration times: Msch=∑m=1NJsdtm. In further considerations, for simplicity, we assume that sdt equals a time unit, and thus the schedule makespan is the same as the total number of jobs in the schedule NJ.In our experiments, a network activity scheduleH is represented as a 0–1 matrix with rows corresponding to machines and columns corresponding to jobs. The element in row i and column m is equal to 1 (resp., 0) when the machine i is on (resp., off) in job Jm.The required level of coverage constraint says that the cardinality of the sum of POIs in tasks assigned to active machines in the jobJm should be equal to or exceed the cov⋅cardP; that is,t(1)cov⋅cardP≤card∪i=1NStsiifHi,m=1∅otherwise.Moreover, for all machines, the processing time should not exceed the limitTbatt:(2)∑m=1NJHi,m≤Tbatt.The objective is the maximization of the schedule makespanMsch with the required level of coverage and without exceeding the maximum processing time of machines Tbatt.


## 4. General Scheme of the Local Search

In our earlier papers [4–6], we proposed three heuristic algorithms for solving MLCP. They all follow the general approach of local search presented in Algorithm 1. Each of them uses different methods in the three steps of local search: initialization (Step #1: line 1), perturbation (Step #2: line 3), and refinement (Step #3: line 4).Algorithm 1: Local search (for the schedule maximization context).
(1)
Initializex∈D ⊳ step #1(2)
Repeat(3)
x′=perturbationx ⊳ step #2(4)
x′′=refinementx′ ⊳ step #3(5)
IfFx′′>Fxthen(6)
x=x′′ ⊳ x is replaced by its neighbor(7)
End if(8)
Until termination condition met(9)
ReturnxThe methods used at the stage of initialization of the proposed algorithms have the following names: the random and fine-tuning approach (RFTA), the cellular automata inspired approach (CAIA), and the hypergraph model approach (HMA). Thus, we denote the LS algorithms proposed in the corresponding papers, respectively, by LSRFTA, LSCAIA, and LSHMA. This notation appeared for the first time in [3], not in original papers [4–6]. In all initialization step methods, we start with an empty schedule and add to it new slots, one by one. Just the methods used to obtain a new slot are different. Adding a new slot to a schedule decreases the battery levels of the sensors active in this slot.When the initialization step terminates (Step#1 in Algorithm 1), some sensors are usually left with non-empty batteries. However, turning on even all these sensors does not guarantee a sufficient coverage level. Thus, we cannot regard this set as a configuration for yet another slot. These sensors contribute to the perturbation and refinement steps (Steps #2 and #3 in Algorithm 1). In the perturbation step, we either remove some slots or modify sets of active sensors in some slots, adding sensors from the set mentioned above and removing others. When we remove an entire slot from the schedule or turn off one or more sensors in a slot, we recover energy. This way, the set of sensors with non-empty batteries grows, and we hope to obtain one or more new slots from this set. In the refinement step, we employ one of the methods used in the initialization step to create new slots and add them to the modified schedule. If the new schedule is longer than the initial one, it replaces the initial one. The perturbation and refinement steps are repeated until some termination condition is met.Removing some slots from the schedule in the perturbation step can be done in two ways. In [4], such slots are selected randomly. In [6], first, we try to turn off every active sensor in every slot. The decision to turn it off is made with a low probability threshold. Next, if removing an active sensor from a slot makes this slot unfeasible, the whole slot is deleted. Our experiments show that more than one slot is removed even for a very low probability, such as 0.0005. Thus, this method of perturbation is stronger than the former.In [5], we used a completely different perturbation approach. We add the sensors from the set with non-empty batteries to randomly selected slots but only when adding an additional sensor increases the coverage level. If this is not the case, we must choose another slot for this sensor. When we use up all the sensors, we attempt to remove from the modified slots other sensors to make their coverage level as close to cov as possible.Thus, for each of the three steps of local search, we have three different methods of proceeding. By selecting one of these methods at every step, we get 27 different variants. We will call these algorithms using the names of every step’s origins. For example, [HMA, RFTA, CAIA] denotes an algorithm where the initialization procedure from the LSHMA algorithm generates the initial schedule, the perturbation step originates from LSRFTA, and the refinement step originates from LSCAIA. [RFTA, RFTA, RFTA] is identical with the LSRFTA algorithm because all three problem-specific steps come from this algorithm.


## 5. Experiments

To assess the performance of new algorithms, we conducted experiments with some of them. We decided to always use the same method to generate an initial schedule. This way, the set of 27 algorithms described in Section4 has been reduced to 9 because our algorithms differ only in the steps of the main loop in Algorithm 1. For the initialization step, a method producing schedules of moderate quality would be appropriate. It should give the main loop more room to improve these schedules and thus highlight performance differences between algorithms. Since HMA usually generates the most extended schedules, which are often hard to improve, we chose between the remaining two methods—RFTA and CAIA. We decided to use CAIA, and this choice was somewhat arbitrary. Eventually, we compared experimentally nine versions of LS algorithms of the form [CAIA,∗,∗] where ∗ stands for one of HMA, CAIA, and RFTA. Consequently, for a problem instance, all versions of the main loop start with the same initial schedule. The termination condition of the loop is a limit of 500 iterations.From now on, we skip the initial CAIA in notation given at the end of Section4 and refer to tested algorithms giving only the origins of the perturbation step and the refinement step. The compared nine algorithms are [HMA, HMA], [HMA, RFTA], [HMA, CAIA], [RFTA, HMA], [RFTA, RFTA], [RFTA, CAIA], [CAIA, HMA], [CAIA, RFTA], and [CAIA, CAIA].In the experimental part, we used the benchmark SCP1 proposed in our earlier publications but also did tests with two external benchmarks: one from [7, 8] and the other from [9], selected due to compatible problem definitions and optimization criteria but differently defined test cases.Experiments were conducted on HP Workstation Z2 G4 SFF with Intel® Core™ i7-8700 CPU @ 3.20 GHz and 16 GB RAM and Windows 10 Pro. Application for simulations was implemented in MS Visual Studio C++.


### 5.1. Measurement Methodology

The best measure of the efficiency of our LS algorithms would be a comparison of the obtained problem solution with an optimal solution. In this case, we would compare the length of the schedule returned by an LS algorithm with the length of an optimal schedule for the given problem instance. Unfortunately, we do not know optimal solutions because it is impossible to compute them in a reasonable time due to the problem’s computational complexity. Therefore, we decided to compare our solutions to the best-obtained suboptimal solution of the problem instance. These best-obtained suboptimal solutions were produced by LS algorithms using HMA to get initial schedules. Since initial schedules produced by HMA are longer than those obtained by other approaches, we hope the resulting schedules are genuinely close to optimal after applying LS to improve them. The lengths of best-obtained suboptimal schedules were used as reference values to evaluate the percentage quality of the schedules produced by our nine LS algorithms.Moreover, we measured the mean percentage improvement of the initial schedule’s length, obtained in the main loop of Algorithm1. It was calculated by subtracting the length of the initial schedule from the length of the final schedule and dividing the difference by the length of the initial schedule. For every class of problems, the obtained values were averaged over the number of problem instances.


### 5.2. Performance Comparisons Using Benchmark SCP1

In our first group of experiments, we used the benchmark SCP1 (Sensor Coverage Problem, Set No. 1) introduced in our earlier publications [3–6].


#### 5.2.1. Benchmark SCP1

SCP1 consists of eight classes of problems. There are 2000 sensors with the sensing range of one abstract unit in all of them. The monitored area is a square. Its side size varies from 13 to 28 abstract units (possible values: 13, 16, 19, 22, 25, and 28). POIs are placed in nodes of a rectangular or a triangular grid. Since the distance between grid nodes grows together with the area side size, the number of nodes is similar for all classes of SCP1. However, only about 80% of grid nodes have a POI. A POI is located in the node only if a randomly generated number between 0 and 1 is less than 0.8.Consequently, instances of the same test case can have different numbers of POIs. For the triangular grid, this number is between 199 and 240, while for the rectangular grid, it is between 166 and 221. Coordinates of sensor locations are obtained using either a random generator or a Halton generator. Eventually, the test classes have the following configurations: 1.13×13,Δℛ, 2.13×13,⋄Η, 3.16×16,Δℋ, 4.19×19,⋄ℛ, 5.19×19,Δℛ, 6.22×22,Δℋ, 7.25×25,Δℛ, 8.28×28,Δℋ, where Δ means a triangular grid of POI locations, ⋄ means a rectangular grid, and ℋ and ℛ mean a Halton and a random generator of sensor locations. We generated 40 instances of every class.Figure1 depicts boxplots (minimum, lower quartile, median, upper quartile, and maximum) of Maximum–Minimum Distance (MMD) [38] values for the sensors and POIs in the instances sets. Precisely, the boxplots show the MMD of the evenness measure and are calculated as follows:(3)MMD=maxx∈Sminv∈Vdx,v,where dx,v is an Euclidean distance between x and v, S is the set of sensors’ locations, and V is the set of vertices in the Voronoi polygons for the set of POIs locations. The values in the diagram grow as the side size of the monitored area grows, which is reasonable. Moreover, for the areas of the same side size, values for the cases where POIs are located on the nodes of the triangular grid are smaller than those for the cases applying a rectangular grid for the POI distribution.Figure 1
Boxplots of MMD values (minimum, lower quartile, median, upper quartile, maximum, and outliers) for the sets of 40 instances for the eight classes of SCP1.Figure2 shows the mean numbers of sensors covering 0, 1, 2, 3, 4, 5, and more than 5 POIs for the eight test cases of SCP1. One can see that the number of sensors covering a more significant number of POIs decreases as the side size of the monitored area grows. When the side sizes increase, the overlapping sections of neighbor sensor monitoring areas shrink, and some even disappear, so the numbers of shared POIs decrease. In the last class of problems, almost 75% of the sensors cover only one POI.Figure 2
Mean numbers of sensors covering 0, 1, 2, 3, 4, 5, and more than 5 POIs for the eight test cases of SCP1.In our experiments, we assumed the required level of coveragecov as either 80 or 90%, while the tolerance factor δ was 5%. The same set of experiments was repeated for five different values of Tbatt—10, 15, 20, 25, and 30.


#### 5.2.2. Mean Normalized Lengths of Schedules and Percentage Quality of Schedules

The lengths of the schedules returned by the LS algorithms in question are the natural outcome of our experiments. However, the average length returned for all problem instances from a particular class may not measure the algorithm quality well. The optimal schedule lengths may differ for subsequent instances and values ofTbatt. For the purpose of compatibility of output values, we normalized the schedule lengths. We assumed that the lifetime of batteries is the same, but different numbers of sensor activity intervals represented by Tbatt can be available for scheduling. We assumed that, for Tbatt=30, the battery lifetime is divided into 30 intervals and a slot takes one unit. Thus, the schedule makespan equals exactly the number of slots in a schedule. Consequently, for Tbatt=10, one slot takes three time units; for Tbatt=15, two units; for Tbatt=20, 1.5 units; and for Tbatt=25, 1.2 units. Eventually, normalized lengths of schedules represent the schedule makespans, that is, the total number of slots multiplied by the number of time units per slot.Another measure is to compute for every result its percentage quality with respect to the best-known suboptimal schedule and then average these percentages over all the problem instances in a class.Table4 presents the mean makespans of schedules for particular classes of test cases. The mean makespan is computed as the sum of the makespans obtained for all instances and all values of Tbatt divided by 40×5 (the number of instances for a class of problems multiplied by the number of different values of Tbatt). Table 5 shows, for each of the eight classes of SCP1, the mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table). It also shows the mean percentage improvement of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table). Tables 4 and 5 present results for cov=80%. Tables 6 and 7 show the same types of results as Tables 4 and 5 but assuming cov=90%.Table 4
Mean makespans of schedules returned by the LS algorithms for the SCP1 benchmark withcov=80%. Codes in column headers: C: CAIA, H: HMA, R: RFTA; e.g., HR represents the version [HMA, RFTA].
No.HHHRCHHCRHCRRRCCRC11076.951013.421064.47992.50630.75645.21623.29627.43623.0221123.491049.561115.981030.01653.39670.46644.69649.18644.503741.78706.81739.25698.68428.38429.47419.91421.79419.724490.89493.20456.59483.83282.14273.80268.23269.27268.055524.84520.62498.60514.87300.56295.96290.57291.67290.326423.40418.12412.82415.20241.59233.57230.17231.02229.927308.84311.64291.18308.24183.09175.99172.92173.57172.678272.86273.61263.97272.79161.22152.76150.51150.94150.24Table 5
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvement of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the eight classes of SCP1 withcov=80%.
No.HHHRCHHCRHCRRRCCRC197.2991.5596.1689.6656.9858.2956.3056.6856.28297.2390.8396.5889.1456.5558.0255.8056.1855.78397.4592.8597.1291.7956.2856.4255.1655.4155.14495.0195.4588.3793.6454.6152.9951.9152.1251.88596.6595.8791.8294.8255.3554.5053.5153.7153.46698.3497.1195.8996.4456.1254.2553.4653.6653.41794.2495.0988.8694.0655.8853.7152.7752.9752.69897.3697.6394.1897.3357.5354.5053.7153.8653.61No.HHHRCHHCRHCRRRCCRC173.4563.2271.4259.851.583.910.381.040.33274.9363.4273.7560.371.734.390.381.070.35377.6369.2677.0167.312.582.830.540.990.50484.5385.4171.6481.886.072.930.831.230.77582.0780.6172.9678.624.272.670.801.180.71685.7583.4381.1082.155.992.460.971.340.86781.0582.6970.7080.697.353.171.371.761.23884.0484.5478.0483.998.753.031.521.811.33Table 6
Mean makespans of schedules returned by the LS algorithms for the SCP1 benchmark withcov=90%.
No.HHHRCHHCRHCRRRCCRC1905.12887.02814.68862.19678.27456.90432.13434.15431.502975.69946.18861.55905.32746.50480.18450.46452.91449.923636.98626.42576.43605.41523.98305.81293.27294.35292.794365.33371.18322.44366.09302.65191.88181.82181.75180.705418.08420.40372.41414.85358.20208.96200.04200.36199.426356.69358.54331.46352.69317.19168.57162.84163.17162.127236.60239.14214.89237.34182.97125.54120.13119.72119.128228.63230.24213.71229.33201.44112.21108.55108.24107.75Table 7
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvement of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the eight classes of SCP1 withcov=90%.
No.HHHRCHHCRHCRRRCCRC196.8394.8987.1692.2472.5948.8846.2346.4546.16297.7494.7886.3190.6974.8048.1045.1245.3745.07397.4195.7988.1692.5780.1646.7644.8545.0144.77492.8194.3081.9393.0076.9248.7446.2046.1845.91594.0394.5583.7793.3080.6047.0045.0045.0744.86697.2697.7790.3996.1786.5245.9744.4144.5044.21792.8193.8184.3093.1071.8049.2447.1346.9646.73895.5896.2589.3495.8784.2346.9145.3845.2545.05No.HHHRCHHCRHCRRRCCRC1110.97106.7789.87100.9858.146.490.711.190.572118.13111.5492.58102.4066.917.350.701.250.583119.27115.6598.41108.4180.415.270.951.320.794104.58107.8680.58105.0169.477.481.831.791.205112.08113.2688.92110.4481.736.001.481.641.176122.97124.13107.21120.4798.325.381.792.001.347102.55104.7283.97103.1856.637.492.862.501.998116.57118.09102.43117.2390.866.282.832.532.07One can see from these results that [HMA, HMA] is usually the best version of LS. Three other LS algorithms, [HMA, RFTA], [CAIA, HMA], and [HMA, CAIA], are also effective, while the remaining five LS versions give much worse results—we will call them weak approaches. However, forcov=90%, [RFTA, HMA] is better than the other weak approaches but not so good as effective ones. Thus, all LS algorithms with the perturbation method from LSHMA produce a relatively good schedule, no matter what way is used to refine the schedule obtained after the perturbation.However, our results also show that [HMA, HMA] is not always the best method. In Table4, in three cases, the values for [HMA, RFTA] are slightly better than those for [HMA, HMA]. Moreover, in the first three lines of Tables 4 and 5, the values for [CAIA, HMA] are better than the corresponding values for [HMA, RFTA]. In Tables 6 and 7, the values for [HMA, CAIA] are always better than those for [CAIA, HMA] and, in three cases, better than the corresponding values for [HMA, HMA]. Moreover, for the last five classes of SCP1, the values for [HMA, RFTA] are better than those for [HMA, HMA]. From these observations, we can only say that one group of algorithms is better than the other group, but we cannot claim that one specific algorithm is always better than another one.Comparing the results produced by [CAIA, HMA] and [RFTA, HMA], one could ask why the first approach belongs to the group of effective ones, whereas the second one can be weak. A possible explanation is that the perturbation method from LSCAIA is much stronger than the one from LSRFTA in terms of the number of slots deleted from the original schedule. Thus, in the case of [CAIA, HMA], the refinement step begins with higher energy levels in the batteries of available sensors. This allows an efficient HMA method to improve a shorter input schedule much more than in the case of a more extended input schedule but less energy in the batteries of available sensors.Figures3 and 4 present boxplots of makespans of schedules returned by the four good LS algorithms for the SCP1 benchmark with cov of 80% and 90%, respectively. These graphs show that all statistical parameter values (minimum, lower quartile, median, upper quartile, maximum) for [HMA, HMA] are usually better than the corresponding values for the three other algorithms.Figure 3
Boxplots of makespans of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the SCP1 classes nos. 1, 2, 3, and 4 (top figures) and classes nos. 5, 6, 7, and 8 (bottom figures) withcov=80%.Figure 4
Boxplots of makespans of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the SCP1 classes nos. 1, 2, 3, and 4 (top figures) and classes nos. 5, 6, 7, and 8 (bottom figures) withcov=90%.In Figure3, only for class 7, the values of minimum, maximum, and quartiles for [HMA, RFTA] are better than the ones for [HMA, HMA]. For class 8, the values of the minimum, the lower quartile, and the median for [HMA, RFTA] are better than the ones for [HMA, HMA], while the values of the upper quartile and the maximum are equal. For class 4, the median and the upper quartile for [HMA, RFTA] are better than the ones for [HMA, HMA], but the minimum, the lower quartile, and the maximum are equal. Thus, none of these two algorithms can produce a schedule longer than the best schedule given by the other, but [HMA, RFTA] more often returns better results. For classes 1–3, the maximum for [CAIA, HMA] is better than the maximum for [HMA, HMA], but the other boxplot parameters for [CAIA, HMA] are worse than those for [HMA, HMA]. [CAIA, HMA] has a more extensive interquartile range and distribution of the results. This is due to the properties of the perturbation method from LSCAIA which is more random than the method used by LSHMA. Hence sometimes, it can produce better usage of the sensors than the more systematic approach of LSHMA.In Figure4, for classes 4–8, the values of minimum, maximum, and quartiles for [HMA, RFTA] are better than the ones for [HMA, HMA]. Moreover, for classes 4 and 8, the values of almost all parameters for [HMA, CAIA] are better than the ones for [HMA, HMA] (the only exception is the maximum in class 8). For class 8, [HMA, CAIA] has smaller interquartile range than [HMA, HMA]. For class 7, the values of the corresponding parameters for [HMA, CAIA] and [HMA, HMA] are almost equal. Thus, boxplot graphs confirm conclusions from mean values.


### 5.3. Performance Comparisons Using Two Other Benchmarks

To validate our findings from Section5.2, we decided to conduct additional experiments using benchmarks provided by other authors. We selected the same two benchmarks we used for experiments with our original algorithms LS HMA, LS CAIA, and LS RFTA [3].


#### 5.3.1. The Benchmark Proposed by Tretyakova et al. in [7, 8]

We selected four classes of problems proposed in [7, 8]. In all cases, the monitored area is a square with a side size of 100 abstract units. In three classes from [8], there are 100 POIs while the number of sensors is 100, 200, and 300 (cases #1, #2, and #3). In the class from [7], we have 400 POIs and 100 sensors (case #4). The remaining parameters have also the same values as in [7, 8]; that is, cov=90%, the sensing range is 20 abstract units, and Tbatt=20. Table 8 presents the mean measured lengths of schedules. Table 9 shows the mean percentage qualities of the best-found schedules returned by our LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the four classes of the benchmark in question, assuming cov=90%.Table 8
Mean lengths of schedules returned by the LS algorithms for each of the four classes of the benchmark given in [7, 8] with cov=90%.
No.HHHRCHHCRHCRRRCCRC#1165.97153.47134.63147.07110.20104.40101.10102.07100.23#2337.97297.37284.47272.10219.80200.87191.20193.53190.00#3510.53423.50441.43373.33319.07301.10282.20287.87281.07#4157.00145.03127.60139.17104.63100.9798.6399.5397.63Table 9
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the four classes of the benchmark given in [7, 8] with cov=90%.
No.HHHRCHHCRHCRRRCCRC#197.0689.7578.7386.0064.4461.0559.1259.6958.62#298.5386.7082.9379.3364.0858.5655.7456.4255.39#399.1382.2385.7272.4961.9558.4754.8055.9054.58#498.1390.6579.7586.9865.4063.1061.6562.2161.02No.HHHRCHHCRHCRRRCCRC#171.3558.4739.0351.8713.777.784.365.353.46#280.8559.1252.2245.5917.647.472.293.551.64#383.9452.5759.0334.4814.988.471.663.711.25#465.9553.3534.8847.1210.636.714.245.183.18This set of experiment results are similar to our earlier results with the benchmark SCP1. [HMA, HMA] always gives the most extended schedules. Algorithms [HMA, RFTA], [CAIA, HMA], and [HMA, CAIA] are worse than [HMA, HMA] but significantly better than the remaining five approaches.Since in experiments with SCP1, we performed computations for two values ofcov, 80% and 90%, we did the same for the test cases from [7, 8]. Tables 10 and 11 show the set of results similar to the ones in Tables 8 and 9 but obtained for cov=80%.Table 10
Mean lengths of schedules returned by the LS algorithms for the benchmark given in [7, 8] with cov=80%.
No.HHHRCHHCRHCRRRCCRC#1193.90166.07168.80162.27141.03141.33138.77140.03138.10#2388.53308.73355.70290.93271.33276.40267.37271.00267.03#3573.10443.87553.23425.07402.53413.93397.50402.23397.10#4183.30160.37163.17155.40138.50139.00136.40137.27135.77Table 11
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the four classes of the benchmark given in [7, 8] with cov=80%.
No.HHHRCHHCRHCRRRCCRC#195.9982.2183.5680.3369.8269.9768.7069.3268.37#296.8976.9988.7072.5567.6668.9366.6767.5866.59#395.6874.1092.3670.9667.2069.1066.3667.1566.29#494.4882.6684.1180.1071.3971.6570.3170.7669.98No.HHHRCHHCRHCRRRCCRC#143.0022.4624.4619.673.994.212.323.251.82#247.1316.9034.6810.162.734.651.232.601.10#345.2412.4840.217.732.014.900.741.940.63#437.5820.3722.4616.623.944.322.363.011.88For this set of benchmarks, loweringcov from 90% to 80% has not changed the relative performance of the three groups of our LS algorithms. However, the relative performance of the three effective algorithms has changed.Figures5 and 6 show boxplots of lengths of schedules returned by the four good LS algorithms for the benchmark proposed in [7, 8] with cov of 90% and 80%, respectively. In Figure 5, one can see that the minimum for [HMA, HMA] is always greater than or equal to the maximum for the other three algorithms. Moreover, the results for [HMA, HMA] have a much smaller interquartile range than those for the other algorithms. The schedules’ lengths are less dispersed, proving the higher stability of the [HMA, HMA] variant for cov=90%. In Figure 6, the values of all parameters for [HMA, HMA] are better than those of the corresponding parameters for the other algorithms. However, for three out of four classes of the benchmark, the results for [CAIA, HMA] have the smallest interquartile range. Less dispersed schedules’ lengths prove the higher stability of the [CAIA, HMA] variant for cov=80%. Again, boxplot graphs confirm conclusions from mean values.Figure 5
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [7, 8] with cov=90%.Figure 6
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [7, 8] with cov=80%.


#### 5.3.2. The Benchmark Proposed by Manju et al. in [9]

The authors of the minimal-heuristic approach [9] proposed the following set of benchmarks for experiments with algorithms solving MLCP. The monitored area is a square with a side size of 150 abstract units. POIs and sensors are distributed randomly over this area. In the first five test cases (1.1–1.5), we have 100 POIs while the sensors’ numbers are 50, 100, 150, 200, and 250, respectively. In the next five test cases (2.1–2.5), there are 150 sensors, while the numbers of POIs are 20, 40, 60, 80, and 100. As in [9], the sensing range is 70 abstract units and cov=100%. Requiring full coverage is reasonable because this set of benchmarks gives much more redundant coverage of POIs by sensors; that is, larger numbers of sensors cover individual POIs than in SCP1 and the benchmark from [7, 8] (see the next subsection for details). We used Tbatt=40.Table12 gives the results of our LS strategies for the benchmarks from [9]. The top part of Table 13 shows the mean percentage qualities of the best-found schedules returned by the LS algorithms. In the bottom part of Table 13, we present mean percentage improvements of the lengths of schedules produced by the LS phase with respect to the lengths of schedules returned by the initialization phase.Table 12
Mean lengths of schedules returned by the LS algorithms for the benchmark given in [9] with cov=100%.
No.HHHRCHHCRHCRRRCCRC1.1548.27506.38487.45406.88392.13452.05374.50435.50370.631.21189.92925.00983.15759.95775.80892.48744.90848.02741.751.31756.401328.171444.801099.901125.381299.631088.631222.151085.401.42509.071730.051979.031487.801516.351763.381476.351651.331473.051.53100.282009.632495.501861.131892.332212.931854.702059.821850.702.12121.101711.031787.531442.901459.331655.031437.531583.551434.222.21984.281513.631637.901271.301282.831481.331264.701410.901259.922.31808.701405.951558.401196.831207.881403.971186.651328.501182.952.41829.631311.081520.031154.171173.421362.001143.471284.971140.052.51850.971317.221487.131128.251144.101331.421116.951256.551113.05Table 13
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the ten classes of the benchmark given in [9] with cov=100%.
No.HHHRCHHCRHCRRRCCRC1.178.4472.4469.7458.2156.1064.6753.5862.3053.021.285.3666.3670.5354.5255.6564.0253.4460.8353.211.384.4063.8269.4352.8554.0862.4552.3158.7352.161.489.2361.5270.3852.9153.9262.7152.5058.7252.381.587.8056.9170.6752.7153.5962.6752.5358.3452.412.181.9666.1169.0755.7556.3963.9555.5561.1955.422.284.3364.3369.6154.0354.5262.9553.7559.9653.552.385.8866.7674.0056.8357.3566.6756.3563.0856.172.483.3259.7069.2252.5653.4362.0252.0758.5151.912.586.2561.3869.3052.5753.3162.0452.0558.5551.87No.HHHRCHHCRHCRRRCCRC1.151.1740.2334.2212.638.1224.503.1719.992.051.262.1126.7833.673.415.5521.401.2915.350.861.362.9023.9933.891.934.3020.460.8813.280.581.471.3418.6635.031.533.5120.370.7512.690.521.568.149.2735.250.862.5819.950.5111.620.292.148.7620.3825.380.982.1516.030.6010.980.362.258.5721.1030.721.402.3418.210.8612.560.462.354.2319.6332.421.682.6119.330.8212.900.502.461.9216.0834.061.863.5820.190.8913.380.582.567.5419.5634.422.013.4320.390.9613.600.61One can see from these results that [HMA, HMA] is still the winner. [CAIA, HMA] is the second best LS approach in 9 out of 10 cases. As the number of sensors grows (which means that the redundancy of coverage also increases), [CAIA, RFTA] becomes better than [HMA, RFTA].Since in our experiments with the benchmark set SCP1 and with the benchmarks from [7, 8] we used cov equal to 80% and 90%, we also performed tests with the data sets from [9] using the same values of cov. For these test cases, the number of alternative sensor activity configurations satisfying coverage level is relatively high due to high redundancy in POI coverage. Lowering cov makes the number of these configurations even greater. The results for cov=90% are given in Tables 14 and 15 while the results for cov=80% are provided in Tables 16 and 17.Table 14
Mean lengths of schedules returned by the LS algorithms for the benchmark given in [9] with cov=90%.
No.HHHRCHHCRHCRRRCCRC1.1755.92728.50826.48724.63725.30802.63723.38786.83722.481.21490.421469.131664.131464.281465.501599.301463.421559.721462.221.32206.972140.102444.952137.322139.202325.252136.702267.322135.471.42976.402921.503361.132920.652921.303181.552919.973095.382918.681.53743.653654.904226.153651.303652.183977.003650.053860.323649.282.12523.252338.202584.652305.632308.552480.972303.382422.952301.882.22293.402230.902521.252214.822215.182399.502213.632344.302212.052.32253.452197.202508.682195.402197.352388.502194.782332.572193.782.42259.722195.902512.952192.752194.932382.682192.402327.032191.452.52242.602191.822508.322190.002191.202388.402188.882321.752187.60Table 15
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the ten classes of the benchmark given in [9] with cov=90%.
No.HHHRCHHCRHCRRRCCRC1.178.9176.0486.2775.6475.7183.7875.5182.1375.411.280.3079.1689.6678.8978.9686.1778.8584.0478.781.381.8679.3890.6979.2879.3586.2579.2584.1079.211.480.2578.7790.6278.7478.7685.7878.7383.4678.691.581.0579.1391.4979.0579.0786.1079.0283.5779.012.172.7467.4074.5166.4666.5571.5266.4069.8566.362.278.3376.1986.1175.6475.6581.9575.6080.0675.552.378.6076.6487.5076.5776.6483.3176.5581.3676.522.477.0474.8785.6874.7674.8481.2474.7579.3474.722.578.3976.6187.6776.5576.5983.4876.5181.1576.46No.HHHRCHHCRHCRRRCCRC1.15.571.5015.270.911.0111.890.730.730.611.22.270.7914.280.450.539.810.390.390.311.33.790.4114.820.270.369.150.240.240.181.42.240.2015.380.170.199.190.150.150.101.52.870.2716.020.160.189.150.120.120.102.110.291.8612.730.360.498.120.260.260.192.23.801.0014.270.270.298.700.220.220.152.32.910.3214.640.230.339.110.210.210.162.43.320.3714.960.230.338.960.210.210.172.52.790.3714.970.280.349.430.230.230.17Table 16
Mean lengths of schedules returned by the LS algorithms for the benchmark given in [9] with cov=80%.
No.HHHRCHHCRHCRRRCCRC1.1973.10969.851030.22968.80968.671020.33968.081009.98967.631.21969.781968.402083.751967.951967.922056.051967.602032.171966.921.32890.602886.073059.932885.402885.353009.222884.972971.972884.501.43938.823934.854197.383934.703934.404110.503934.454051.633933.531.54931.934930.525277.354930.234930.885149.184930.255072.934929.882.13062.823039.933205.323038.503039.253155.603038.453120.103037.852.22963.932961.723136.972960.532960.653086.782960.823050.032959.802.32980.102978.783161.282977.652976.973102.932977.103067.322976.322.42961.702959.603140.322958.552958.303086.322958.103047.952957.432.52968.402966.473145.072965.952965.973093.152966.033055.302965.28Table 17
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the ten classes of the benchmark given in [9] with cov=80%.
No.HHHRCHHCRHCRRRCCRC1.182.0581.7786.8781.6981.6886.0381.6385.1681.591.285.5785.5190.5285.4985.4989.3285.4788.2885.441.382.4782.3487.3082.3282.3285.8682.3184.7982.301.483.7383.6589.2383.6583.6487.3883.6486.1383.621.584.7184.6990.6484.6884.6988.4484.6887.1384.682.181.2680.6685.0480.6280.6483.7380.6282.7880.602.286.9486.8892.0286.8486.8590.5586.8589.4786.822.386.3886.3491.6386.3186.2989.9486.2988.9186.272.486.7586.6991.9886.6686.6590.4086.6589.2886.632.583.2083.1488.1583.1383.1386.6983.1385.6383.11No.HHHRCHHCRHCRRRCCRC1.10.960.616.980.500.485.930.424.860.371.20.290.226.170.190.194.740.183.510.141.30.340.186.280.150.154.500.143.200.121.40.220.116.840.110.104.620.103.110.081.50.090.067.160.060.074.530.062.980.052.10.980.175.780.120.154.090.122.890.102.20.250.186.180.140.144.460.153.200.112.30.250.206.390.160.144.410.153.210.122.40.270.206.380.160.164.540.153.230.132.50.200.136.210.110.114.450.113.160.09In this set of experiments, [CAIA, HMA] is the best LS algorithm in all cases. Forcov=90%, [HMA, HMA] is the second best in test Case 2.1. In all other test cases, for both cov equal to 80% and that equal to 90%, the second best is [CAIA, RFTA]. The third is [CAIA, CAIA]. Thus, for cov equal to 80% or 90%, the perturbation method used in CAIA always gives results better than the other two methods. Interestingly, for cov=80%, the remaining six LS algorithms (including [HMA, HMA]) give a relative improvement of less than 1%.Figures7, 8, and 9 show boxplots of lengths of schedules returned by the four good LS algorithms for the benchmark proposed in [9] with cov of 100%, 90%, and 80%, respectively. In Figure 7 [HMA, HMA] always gives the largest values of minimum, maximum, and quartiles. [CAIA, HMA] and [HMA, CAIA] have usually smaller interquartile ranges than [HMA, HMA] and [HMA, RFTA]. The small value of the interquartile range for [HMA, CAIA] with the mean value lower than the mean values of the results returned by other algorithms means that [HMA, CAIA] never gives good results for this benchmark and cov=100%. In Figure 8, [CAIA, HMA] not only has the highest values of all parameters but also almost always has the smallest interquartile range (only for class 1.1, [HMA, RFTA] has a smaller interquartile range). Decreasing cov from 100 to 90% changed the winner—more random perturbation method from LSCAIA turned out to be better in this case. Finally, in Figure 9, [CAIA, HMA] again has the highest values of all parameters and often has the smallest interquartile range. However, in this case, interquartile ranges for all four algorithms are close to each other. One more time, boxplot graphs confirm conclusions from mean values.Figure 7
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [9] with cov=100%.Figure 8
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [9] with cov=90%.Figure 9
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [9] with cov=80%.


### 5.4. What Affects Algorithms’ Effectiveness?

#### 5.4.1. The Redundancy in Coverage of POIs by Sensors in the Benchmarks

To explain differences in the relative performance of our nine LS approaches on various benchmarks, we investigated the numbers of sensors able to control particular POIs in SCP1 and the benchmarks from [7–9]. Our findings are presented in Figures 10–12.Figure 10
Percentage numbers of POIs covered by different numbers of sensors for SCP1.Figure 11
Percentage numbers of POIs covered by different numbers of sensors for the benchmark given in [9].Figure 12
Percentage numbers of POIs covered by different numbers of sensors for the benchmark given in [7, 8].Figures10 and 12 show that in the test cases from SCP1 and from [7, 8], every POI can be monitored by not more than 50 sensors and, in some of these cases, even by not more than 20 sensors. On the other hand, Figure 11 shows that in the test cases from [9], many POIs can be monitored by more than 100 sensors. This high monitoring redundancy makes finding a cover for POIs much more manageable, even for cov=100%.We conclude from the above considerations that the perturbation method used in LSCAIA works better than the other two methods when there are many possibilities of forming a required cover for a given set of POIs. When the number of such options decreases due to a higher value of cov or a smaller number of sensors, the perturbation method from LSHMA becomes better. The advantage of the perturbation method from LSCAIA over the one from LSHMA when there is much redundancy in coverage of POIs is probably that the former removes more slots from the original schedule than the latter. When the number of similar legal covers becomes large, there are many possibilities of creating a valid schedule. Removing more slots and restoring more power to sensor batteries gives the refinement method more space to show its effectiveness and improve the original schedule. On the other hand, when the redundancy in coverage of POIs decreases, a more systematic approach of HMA works better.Let us also notice that too much redundancy in coverage of POIs by sensors is not desirable in real life due to increased costs. Of course, the ultimate redundancy level depends mainly on a specific application.


#### 5.4.2. Strengths and Weaknesses of the Perturbation Operators

The good performance of the perturbation method from LSHMA comes from the fact that this method does not remove a single slot from the original schedule. Instead, the method only changes sets of active sensors in selected slots. Consequently, the set of sensors with non-empty batteries changes too. It opens up new possibilities for producing one additional slot in the refinement step, which is sufficient to obtain a more extended schedule. On the other hand, the perturbation methods from LSRFTA and LSCAIA delete slots from the initial schedule. It means that during the refinement step, the minimum goal is to create at least as many new slots as were removed during the perturbation. When we succeed, we can go further and try to generate more slots to make the new schedule longer. It can happen, nevertheless, that we are not able to get as many additional slots as we removed. Despite the refinement step execution, we get a shorter schedule. Slots or sensors in slots are selected for removal randomly, so our success depends on luck. As we mentioned above, when there is much redundancy in coverage of POIs by sensors and we remove many slots from the original schedule, the chances of removing the right slots and eventually getting a more extended schedule grow.


## 5.1. Measurement Methodology

The best measure of the efficiency of our LS algorithms would be a comparison of the obtained problem solution with an optimal solution. In this case, we would compare the length of the schedule returned by an LS algorithm with the length of an optimal schedule for the given problem instance. Unfortunately, we do not know optimal solutions because it is impossible to compute them in a reasonable time due to the problem’s computational complexity. Therefore, we decided to compare our solutions to the best-obtained suboptimal solution of the problem instance. These best-obtained suboptimal solutions were produced by LS algorithms using HMA to get initial schedules. Since initial schedules produced by HMA are longer than those obtained by other approaches, we hope the resulting schedules are genuinely close to optimal after applying LS to improve them. The lengths of best-obtained suboptimal schedules were used as reference values to evaluate the percentage quality of the schedules produced by our nine LS algorithms.Moreover, we measured the mean percentage improvement of the initial schedule’s length, obtained in the main loop of Algorithm1. It was calculated by subtracting the length of the initial schedule from the length of the final schedule and dividing the difference by the length of the initial schedule. For every class of problems, the obtained values were averaged over the number of problem instances.


## 5.2. Performance Comparisons Using Benchmark SCP1

In our first group of experiments, we used the benchmark SCP1 (Sensor Coverage Problem, Set No. 1) introduced in our earlier publications [3–6].


### 5.2.1. Benchmark SCP1

SCP1 consists of eight classes of problems. There are 2000 sensors with the sensing range of one abstract unit in all of them. The monitored area is a square. Its side size varies from 13 to 28 abstract units (possible values: 13, 16, 19, 22, 25, and 28). POIs are placed in nodes of a rectangular or a triangular grid. Since the distance between grid nodes grows together with the area side size, the number of nodes is similar for all classes of SCP1. However, only about 80% of grid nodes have a POI. A POI is located in the node only if a randomly generated number between 0 and 1 is less than 0.8.Consequently, instances of the same test case can have different numbers of POIs. For the triangular grid, this number is between 199 and 240, while for the rectangular grid, it is between 166 and 221. Coordinates of sensor locations are obtained using either a random generator or a Halton generator. Eventually, the test classes have the following configurations: 1.13×13,Δℛ, 2.13×13,⋄Η, 3.16×16,Δℋ, 4.19×19,⋄ℛ, 5.19×19,Δℛ, 6.22×22,Δℋ, 7.25×25,Δℛ, 8.28×28,Δℋ, where Δ means a triangular grid of POI locations, ⋄ means a rectangular grid, and ℋ and ℛ mean a Halton and a random generator of sensor locations. We generated 40 instances of every class.Figure1 depicts boxplots (minimum, lower quartile, median, upper quartile, and maximum) of Maximum–Minimum Distance (MMD) [38] values for the sensors and POIs in the instances sets. Precisely, the boxplots show the MMD of the evenness measure and are calculated as follows:(3)MMD=maxx∈Sminv∈Vdx,v,where dx,v is an Euclidean distance between x and v, S is the set of sensors’ locations, and V is the set of vertices in the Voronoi polygons for the set of POIs locations. The values in the diagram grow as the side size of the monitored area grows, which is reasonable. Moreover, for the areas of the same side size, values for the cases where POIs are located on the nodes of the triangular grid are smaller than those for the cases applying a rectangular grid for the POI distribution.Figure 1
Boxplots of MMD values (minimum, lower quartile, median, upper quartile, maximum, and outliers) for the sets of 40 instances for the eight classes of SCP1.Figure2 shows the mean numbers of sensors covering 0, 1, 2, 3, 4, 5, and more than 5 POIs for the eight test cases of SCP1. One can see that the number of sensors covering a more significant number of POIs decreases as the side size of the monitored area grows. When the side sizes increase, the overlapping sections of neighbor sensor monitoring areas shrink, and some even disappear, so the numbers of shared POIs decrease. In the last class of problems, almost 75% of the sensors cover only one POI.Figure 2
Mean numbers of sensors covering 0, 1, 2, 3, 4, 5, and more than 5 POIs for the eight test cases of SCP1.In our experiments, we assumed the required level of coveragecov as either 80 or 90%, while the tolerance factor δ was 5%. The same set of experiments was repeated for five different values of Tbatt—10, 15, 20, 25, and 30.


### 5.2.2. Mean Normalized Lengths of Schedules and Percentage Quality of Schedules

The lengths of the schedules returned by the LS algorithms in question are the natural outcome of our experiments. However, the average length returned for all problem instances from a particular class may not measure the algorithm quality well. The optimal schedule lengths may differ for subsequent instances and values ofTbatt. For the purpose of compatibility of output values, we normalized the schedule lengths. We assumed that the lifetime of batteries is the same, but different numbers of sensor activity intervals represented by Tbatt can be available for scheduling. We assumed that, for Tbatt=30, the battery lifetime is divided into 30 intervals and a slot takes one unit. Thus, the schedule makespan equals exactly the number of slots in a schedule. Consequently, for Tbatt=10, one slot takes three time units; for Tbatt=15, two units; for Tbatt=20, 1.5 units; and for Tbatt=25, 1.2 units. Eventually, normalized lengths of schedules represent the schedule makespans, that is, the total number of slots multiplied by the number of time units per slot.Another measure is to compute for every result its percentage quality with respect to the best-known suboptimal schedule and then average these percentages over all the problem instances in a class.Table4 presents the mean makespans of schedules for particular classes of test cases. The mean makespan is computed as the sum of the makespans obtained for all instances and all values of Tbatt divided by 40×5 (the number of instances for a class of problems multiplied by the number of different values of Tbatt). Table 5 shows, for each of the eight classes of SCP1, the mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table). It also shows the mean percentage improvement of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table). Tables 4 and 5 present results for cov=80%. Tables 6 and 7 show the same types of results as Tables 4 and 5 but assuming cov=90%.Table 4
Mean makespans of schedules returned by the LS algorithms for the SCP1 benchmark withcov=80%. Codes in column headers: C: CAIA, H: HMA, R: RFTA; e.g., HR represents the version [HMA, RFTA].
No.HHHRCHHCRHCRRRCCRC11076.951013.421064.47992.50630.75645.21623.29627.43623.0221123.491049.561115.981030.01653.39670.46644.69649.18644.503741.78706.81739.25698.68428.38429.47419.91421.79419.724490.89493.20456.59483.83282.14273.80268.23269.27268.055524.84520.62498.60514.87300.56295.96290.57291.67290.326423.40418.12412.82415.20241.59233.57230.17231.02229.927308.84311.64291.18308.24183.09175.99172.92173.57172.678272.86273.61263.97272.79161.22152.76150.51150.94150.24Table 5
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvement of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the eight classes of SCP1 withcov=80%.
No.HHHRCHHCRHCRRRCCRC197.2991.5596.1689.6656.9858.2956.3056.6856.28297.2390.8396.5889.1456.5558.0255.8056.1855.78397.4592.8597.1291.7956.2856.4255.1655.4155.14495.0195.4588.3793.6454.6152.9951.9152.1251.88596.6595.8791.8294.8255.3554.5053.5153.7153.46698.3497.1195.8996.4456.1254.2553.4653.6653.41794.2495.0988.8694.0655.8853.7152.7752.9752.69897.3697.6394.1897.3357.5354.5053.7153.8653.61No.HHHRCHHCRHCRRRCCRC173.4563.2271.4259.851.583.910.381.040.33274.9363.4273.7560.371.734.390.381.070.35377.6369.2677.0167.312.582.830.540.990.50484.5385.4171.6481.886.072.930.831.230.77582.0780.6172.9678.624.272.670.801.180.71685.7583.4381.1082.155.992.460.971.340.86781.0582.6970.7080.697.353.171.371.761.23884.0484.5478.0483.998.753.031.521.811.33Table 6
Mean makespans of schedules returned by the LS algorithms for the SCP1 benchmark withcov=90%.
No.HHHRCHHCRHCRRRCCRC1905.12887.02814.68862.19678.27456.90432.13434.15431.502975.69946.18861.55905.32746.50480.18450.46452.91449.923636.98626.42576.43605.41523.98305.81293.27294.35292.794365.33371.18322.44366.09302.65191.88181.82181.75180.705418.08420.40372.41414.85358.20208.96200.04200.36199.426356.69358.54331.46352.69317.19168.57162.84163.17162.127236.60239.14214.89237.34182.97125.54120.13119.72119.128228.63230.24213.71229.33201.44112.21108.55108.24107.75Table 7
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvement of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the eight classes of SCP1 withcov=90%.
No.HHHRCHHCRHCRRRCCRC196.8394.8987.1692.2472.5948.8846.2346.4546.16297.7494.7886.3190.6974.8048.1045.1245.3745.07397.4195.7988.1692.5780.1646.7644.8545.0144.77492.8194.3081.9393.0076.9248.7446.2046.1845.91594.0394.5583.7793.3080.6047.0045.0045.0744.86697.2697.7790.3996.1786.5245.9744.4144.5044.21792.8193.8184.3093.1071.8049.2447.1346.9646.73895.5896.2589.3495.8784.2346.9145.3845.2545.05No.HHHRCHHCRHCRRRCCRC1110.97106.7789.87100.9858.146.490.711.190.572118.13111.5492.58102.4066.917.350.701.250.583119.27115.6598.41108.4180.415.270.951.320.794104.58107.8680.58105.0169.477.481.831.791.205112.08113.2688.92110.4481.736.001.481.641.176122.97124.13107.21120.4798.325.381.792.001.347102.55104.7283.97103.1856.637.492.862.501.998116.57118.09102.43117.2390.866.282.832.532.07One can see from these results that [HMA, HMA] is usually the best version of LS. Three other LS algorithms, [HMA, RFTA], [CAIA, HMA], and [HMA, CAIA], are also effective, while the remaining five LS versions give much worse results—we will call them weak approaches. However, forcov=90%, [RFTA, HMA] is better than the other weak approaches but not so good as effective ones. Thus, all LS algorithms with the perturbation method from LSHMA produce a relatively good schedule, no matter what way is used to refine the schedule obtained after the perturbation.However, our results also show that [HMA, HMA] is not always the best method. In Table4, in three cases, the values for [HMA, RFTA] are slightly better than those for [HMA, HMA]. Moreover, in the first three lines of Tables 4 and 5, the values for [CAIA, HMA] are better than the corresponding values for [HMA, RFTA]. In Tables 6 and 7, the values for [HMA, CAIA] are always better than those for [CAIA, HMA] and, in three cases, better than the corresponding values for [HMA, HMA]. Moreover, for the last five classes of SCP1, the values for [HMA, RFTA] are better than those for [HMA, HMA]. From these observations, we can only say that one group of algorithms is better than the other group, but we cannot claim that one specific algorithm is always better than another one.Comparing the results produced by [CAIA, HMA] and [RFTA, HMA], one could ask why the first approach belongs to the group of effective ones, whereas the second one can be weak. A possible explanation is that the perturbation method from LSCAIA is much stronger than the one from LSRFTA in terms of the number of slots deleted from the original schedule. Thus, in the case of [CAIA, HMA], the refinement step begins with higher energy levels in the batteries of available sensors. This allows an efficient HMA method to improve a shorter input schedule much more than in the case of a more extended input schedule but less energy in the batteries of available sensors.Figures3 and 4 present boxplots of makespans of schedules returned by the four good LS algorithms for the SCP1 benchmark with cov of 80% and 90%, respectively. These graphs show that all statistical parameter values (minimum, lower quartile, median, upper quartile, maximum) for [HMA, HMA] are usually better than the corresponding values for the three other algorithms.Figure 3
Boxplots of makespans of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the SCP1 classes nos. 1, 2, 3, and 4 (top figures) and classes nos. 5, 6, 7, and 8 (bottom figures) withcov=80%.Figure 4
Boxplots of makespans of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the SCP1 classes nos. 1, 2, 3, and 4 (top figures) and classes nos. 5, 6, 7, and 8 (bottom figures) withcov=90%.In Figure3, only for class 7, the values of minimum, maximum, and quartiles for [HMA, RFTA] are better than the ones for [HMA, HMA]. For class 8, the values of the minimum, the lower quartile, and the median for [HMA, RFTA] are better than the ones for [HMA, HMA], while the values of the upper quartile and the maximum are equal. For class 4, the median and the upper quartile for [HMA, RFTA] are better than the ones for [HMA, HMA], but the minimum, the lower quartile, and the maximum are equal. Thus, none of these two algorithms can produce a schedule longer than the best schedule given by the other, but [HMA, RFTA] more often returns better results. For classes 1–3, the maximum for [CAIA, HMA] is better than the maximum for [HMA, HMA], but the other boxplot parameters for [CAIA, HMA] are worse than those for [HMA, HMA]. [CAIA, HMA] has a more extensive interquartile range and distribution of the results. This is due to the properties of the perturbation method from LSCAIA which is more random than the method used by LSHMA. Hence sometimes, it can produce better usage of the sensors than the more systematic approach of LSHMA.In Figure4, for classes 4–8, the values of minimum, maximum, and quartiles for [HMA, RFTA] are better than the ones for [HMA, HMA]. Moreover, for classes 4 and 8, the values of almost all parameters for [HMA, CAIA] are better than the ones for [HMA, HMA] (the only exception is the maximum in class 8). For class 8, [HMA, CAIA] has smaller interquartile range than [HMA, HMA]. For class 7, the values of the corresponding parameters for [HMA, CAIA] and [HMA, HMA] are almost equal. Thus, boxplot graphs confirm conclusions from mean values.


## 5.2.1. Benchmark SCP1

SCP1 consists of eight classes of problems. There are 2000 sensors with the sensing range of one abstract unit in all of them. The monitored area is a square. Its side size varies from 13 to 28 abstract units (possible values: 13, 16, 19, 22, 25, and 28). POIs are placed in nodes of a rectangular or a triangular grid. Since the distance between grid nodes grows together with the area side size, the number of nodes is similar for all classes of SCP1. However, only about 80% of grid nodes have a POI. A POI is located in the node only if a randomly generated number between 0 and 1 is less than 0.8.Consequently, instances of the same test case can have different numbers of POIs. For the triangular grid, this number is between 199 and 240, while for the rectangular grid, it is between 166 and 221. Coordinates of sensor locations are obtained using either a random generator or a Halton generator. Eventually, the test classes have the following configurations: 1.13×13,Δℛ, 2.13×13,⋄Η, 3.16×16,Δℋ, 4.19×19,⋄ℛ, 5.19×19,Δℛ, 6.22×22,Δℋ, 7.25×25,Δℛ, 8.28×28,Δℋ, where Δ means a triangular grid of POI locations, ⋄ means a rectangular grid, and ℋ and ℛ mean a Halton and a random generator of sensor locations. We generated 40 instances of every class.Figure1 depicts boxplots (minimum, lower quartile, median, upper quartile, and maximum) of Maximum–Minimum Distance (MMD) [38] values for the sensors and POIs in the instances sets. Precisely, the boxplots show the MMD of the evenness measure and are calculated as follows:(3)MMD=maxx∈Sminv∈Vdx,v,where dx,v is an Euclidean distance between x and v, S is the set of sensors’ locations, and V is the set of vertices in the Voronoi polygons for the set of POIs locations. The values in the diagram grow as the side size of the monitored area grows, which is reasonable. Moreover, for the areas of the same side size, values for the cases where POIs are located on the nodes of the triangular grid are smaller than those for the cases applying a rectangular grid for the POI distribution.Figure 1
Boxplots of MMD values (minimum, lower quartile, median, upper quartile, maximum, and outliers) for the sets of 40 instances for the eight classes of SCP1.Figure2 shows the mean numbers of sensors covering 0, 1, 2, 3, 4, 5, and more than 5 POIs for the eight test cases of SCP1. One can see that the number of sensors covering a more significant number of POIs decreases as the side size of the monitored area grows. When the side sizes increase, the overlapping sections of neighbor sensor monitoring areas shrink, and some even disappear, so the numbers of shared POIs decrease. In the last class of problems, almost 75% of the sensors cover only one POI.Figure 2
Mean numbers of sensors covering 0, 1, 2, 3, 4, 5, and more than 5 POIs for the eight test cases of SCP1.In our experiments, we assumed the required level of coveragecov as either 80 or 90%, while the tolerance factor δ was 5%. The same set of experiments was repeated for five different values of Tbatt—10, 15, 20, 25, and 30.


## 5.2.2. Mean Normalized Lengths of Schedules and Percentage Quality of Schedules

The lengths of the schedules returned by the LS algorithms in question are the natural outcome of our experiments. However, the average length returned for all problem instances from a particular class may not measure the algorithm quality well. The optimal schedule lengths may differ for subsequent instances and values ofTbatt. For the purpose of compatibility of output values, we normalized the schedule lengths. We assumed that the lifetime of batteries is the same, but different numbers of sensor activity intervals represented by Tbatt can be available for scheduling. We assumed that, for Tbatt=30, the battery lifetime is divided into 30 intervals and a slot takes one unit. Thus, the schedule makespan equals exactly the number of slots in a schedule. Consequently, for Tbatt=10, one slot takes three time units; for Tbatt=15, two units; for Tbatt=20, 1.5 units; and for Tbatt=25, 1.2 units. Eventually, normalized lengths of schedules represent the schedule makespans, that is, the total number of slots multiplied by the number of time units per slot.Another measure is to compute for every result its percentage quality with respect to the best-known suboptimal schedule and then average these percentages over all the problem instances in a class.Table4 presents the mean makespans of schedules for particular classes of test cases. The mean makespan is computed as the sum of the makespans obtained for all instances and all values of Tbatt divided by 40×5 (the number of instances for a class of problems multiplied by the number of different values of Tbatt). Table 5 shows, for each of the eight classes of SCP1, the mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table). It also shows the mean percentage improvement of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table). Tables 4 and 5 present results for cov=80%. Tables 6 and 7 show the same types of results as Tables 4 and 5 but assuming cov=90%.Table 4
Mean makespans of schedules returned by the LS algorithms for the SCP1 benchmark withcov=80%. Codes in column headers: C: CAIA, H: HMA, R: RFTA; e.g., HR represents the version [HMA, RFTA].
No.HHHRCHHCRHCRRRCCRC11076.951013.421064.47992.50630.75645.21623.29627.43623.0221123.491049.561115.981030.01653.39670.46644.69649.18644.503741.78706.81739.25698.68428.38429.47419.91421.79419.724490.89493.20456.59483.83282.14273.80268.23269.27268.055524.84520.62498.60514.87300.56295.96290.57291.67290.326423.40418.12412.82415.20241.59233.57230.17231.02229.927308.84311.64291.18308.24183.09175.99172.92173.57172.678272.86273.61263.97272.79161.22152.76150.51150.94150.24Table 5
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvement of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the eight classes of SCP1 withcov=80%.
No.HHHRCHHCRHCRRRCCRC197.2991.5596.1689.6656.9858.2956.3056.6856.28297.2390.8396.5889.1456.5558.0255.8056.1855.78397.4592.8597.1291.7956.2856.4255.1655.4155.14495.0195.4588.3793.6454.6152.9951.9152.1251.88596.6595.8791.8294.8255.3554.5053.5153.7153.46698.3497.1195.8996.4456.1254.2553.4653.6653.41794.2495.0988.8694.0655.8853.7152.7752.9752.69897.3697.6394.1897.3357.5354.5053.7153.8653.61No.HHHRCHHCRHCRRRCCRC173.4563.2271.4259.851.583.910.381.040.33274.9363.4273.7560.371.734.390.381.070.35377.6369.2677.0167.312.582.830.540.990.50484.5385.4171.6481.886.072.930.831.230.77582.0780.6172.9678.624.272.670.801.180.71685.7583.4381.1082.155.992.460.971.340.86781.0582.6970.7080.697.353.171.371.761.23884.0484.5478.0483.998.753.031.521.811.33Table 6
Mean makespans of schedules returned by the LS algorithms for the SCP1 benchmark withcov=90%.
No.HHHRCHHCRHCRRRCCRC1905.12887.02814.68862.19678.27456.90432.13434.15431.502975.69946.18861.55905.32746.50480.18450.46452.91449.923636.98626.42576.43605.41523.98305.81293.27294.35292.794365.33371.18322.44366.09302.65191.88181.82181.75180.705418.08420.40372.41414.85358.20208.96200.04200.36199.426356.69358.54331.46352.69317.19168.57162.84163.17162.127236.60239.14214.89237.34182.97125.54120.13119.72119.128228.63230.24213.71229.33201.44112.21108.55108.24107.75Table 7
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvement of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the eight classes of SCP1 withcov=90%.
No.HHHRCHHCRHCRRRCCRC196.8394.8987.1692.2472.5948.8846.2346.4546.16297.7494.7886.3190.6974.8048.1045.1245.3745.07397.4195.7988.1692.5780.1646.7644.8545.0144.77492.8194.3081.9393.0076.9248.7446.2046.1845.91594.0394.5583.7793.3080.6047.0045.0045.0744.86697.2697.7790.3996.1786.5245.9744.4144.5044.21792.8193.8184.3093.1071.8049.2447.1346.9646.73895.5896.2589.3495.8784.2346.9145.3845.2545.05No.HHHRCHHCRHCRRRCCRC1110.97106.7789.87100.9858.146.490.711.190.572118.13111.5492.58102.4066.917.350.701.250.583119.27115.6598.41108.4180.415.270.951.320.794104.58107.8680.58105.0169.477.481.831.791.205112.08113.2688.92110.4481.736.001.481.641.176122.97124.13107.21120.4798.325.381.792.001.347102.55104.7283.97103.1856.637.492.862.501.998116.57118.09102.43117.2390.866.282.832.532.07One can see from these results that [HMA, HMA] is usually the best version of LS. Three other LS algorithms, [HMA, RFTA], [CAIA, HMA], and [HMA, CAIA], are also effective, while the remaining five LS versions give much worse results—we will call them weak approaches. However, forcov=90%, [RFTA, HMA] is better than the other weak approaches but not so good as effective ones. Thus, all LS algorithms with the perturbation method from LSHMA produce a relatively good schedule, no matter what way is used to refine the schedule obtained after the perturbation.However, our results also show that [HMA, HMA] is not always the best method. In Table4, in three cases, the values for [HMA, RFTA] are slightly better than those for [HMA, HMA]. Moreover, in the first three lines of Tables 4 and 5, the values for [CAIA, HMA] are better than the corresponding values for [HMA, RFTA]. In Tables 6 and 7, the values for [HMA, CAIA] are always better than those for [CAIA, HMA] and, in three cases, better than the corresponding values for [HMA, HMA]. Moreover, for the last five classes of SCP1, the values for [HMA, RFTA] are better than those for [HMA, HMA]. From these observations, we can only say that one group of algorithms is better than the other group, but we cannot claim that one specific algorithm is always better than another one.Comparing the results produced by [CAIA, HMA] and [RFTA, HMA], one could ask why the first approach belongs to the group of effective ones, whereas the second one can be weak. A possible explanation is that the perturbation method from LSCAIA is much stronger than the one from LSRFTA in terms of the number of slots deleted from the original schedule. Thus, in the case of [CAIA, HMA], the refinement step begins with higher energy levels in the batteries of available sensors. This allows an efficient HMA method to improve a shorter input schedule much more than in the case of a more extended input schedule but less energy in the batteries of available sensors.Figures3 and 4 present boxplots of makespans of schedules returned by the four good LS algorithms for the SCP1 benchmark with cov of 80% and 90%, respectively. These graphs show that all statistical parameter values (minimum, lower quartile, median, upper quartile, maximum) for [HMA, HMA] are usually better than the corresponding values for the three other algorithms.Figure 3
Boxplots of makespans of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the SCP1 classes nos. 1, 2, 3, and 4 (top figures) and classes nos. 5, 6, 7, and 8 (bottom figures) withcov=80%.Figure 4
Boxplots of makespans of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the SCP1 classes nos. 1, 2, 3, and 4 (top figures) and classes nos. 5, 6, 7, and 8 (bottom figures) withcov=90%.In Figure3, only for class 7, the values of minimum, maximum, and quartiles for [HMA, RFTA] are better than the ones for [HMA, HMA]. For class 8, the values of the minimum, the lower quartile, and the median for [HMA, RFTA] are better than the ones for [HMA, HMA], while the values of the upper quartile and the maximum are equal. For class 4, the median and the upper quartile for [HMA, RFTA] are better than the ones for [HMA, HMA], but the minimum, the lower quartile, and the maximum are equal. Thus, none of these two algorithms can produce a schedule longer than the best schedule given by the other, but [HMA, RFTA] more often returns better results. For classes 1–3, the maximum for [CAIA, HMA] is better than the maximum for [HMA, HMA], but the other boxplot parameters for [CAIA, HMA] are worse than those for [HMA, HMA]. [CAIA, HMA] has a more extensive interquartile range and distribution of the results. This is due to the properties of the perturbation method from LSCAIA which is more random than the method used by LSHMA. Hence sometimes, it can produce better usage of the sensors than the more systematic approach of LSHMA.In Figure4, for classes 4–8, the values of minimum, maximum, and quartiles for [HMA, RFTA] are better than the ones for [HMA, HMA]. Moreover, for classes 4 and 8, the values of almost all parameters for [HMA, CAIA] are better than the ones for [HMA, HMA] (the only exception is the maximum in class 8). For class 8, [HMA, CAIA] has smaller interquartile range than [HMA, HMA]. For class 7, the values of the corresponding parameters for [HMA, CAIA] and [HMA, HMA] are almost equal. Thus, boxplot graphs confirm conclusions from mean values.


## 5.3. Performance Comparisons Using Two Other Benchmarks

To validate our findings from Section5.2, we decided to conduct additional experiments using benchmarks provided by other authors. We selected the same two benchmarks we used for experiments with our original algorithms LS HMA, LS CAIA, and LS RFTA [3].


### 5.3.1. The Benchmark Proposed by Tretyakova et al. in [7, 8]

We selected four classes of problems proposed in [7, 8]. In all cases, the monitored area is a square with a side size of 100 abstract units. In three classes from [8], there are 100 POIs while the number of sensors is 100, 200, and 300 (cases #1, #2, and #3). In the class from [7], we have 400 POIs and 100 sensors (case #4). The remaining parameters have also the same values as in [7, 8]; that is, cov=90%, the sensing range is 20 abstract units, and Tbatt=20. Table 8 presents the mean measured lengths of schedules. Table 9 shows the mean percentage qualities of the best-found schedules returned by our LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the four classes of the benchmark in question, assuming cov=90%.Table 8
Mean lengths of schedules returned by the LS algorithms for each of the four classes of the benchmark given in [7, 8] with cov=90%.
No.HHHRCHHCRHCRRRCCRC#1165.97153.47134.63147.07110.20104.40101.10102.07100.23#2337.97297.37284.47272.10219.80200.87191.20193.53190.00#3510.53423.50441.43373.33319.07301.10282.20287.87281.07#4157.00145.03127.60139.17104.63100.9798.6399.5397.63Table 9
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the four classes of the benchmark given in [7, 8] with cov=90%.
No.HHHRCHHCRHCRRRCCRC#197.0689.7578.7386.0064.4461.0559.1259.6958.62#298.5386.7082.9379.3364.0858.5655.7456.4255.39#399.1382.2385.7272.4961.9558.4754.8055.9054.58#498.1390.6579.7586.9865.4063.1061.6562.2161.02No.HHHRCHHCRHCRRRCCRC#171.3558.4739.0351.8713.777.784.365.353.46#280.8559.1252.2245.5917.647.472.293.551.64#383.9452.5759.0334.4814.988.471.663.711.25#465.9553.3534.8847.1210.636.714.245.183.18This set of experiment results are similar to our earlier results with the benchmark SCP1. [HMA, HMA] always gives the most extended schedules. Algorithms [HMA, RFTA], [CAIA, HMA], and [HMA, CAIA] are worse than [HMA, HMA] but significantly better than the remaining five approaches.Since in experiments with SCP1, we performed computations for two values ofcov, 80% and 90%, we did the same for the test cases from [7, 8]. Tables 10 and 11 show the set of results similar to the ones in Tables 8 and 9 but obtained for cov=80%.Table 10
Mean lengths of schedules returned by the LS algorithms for the benchmark given in [7, 8] with cov=80%.
No.HHHRCHHCRHCRRRCCRC#1193.90166.07168.80162.27141.03141.33138.77140.03138.10#2388.53308.73355.70290.93271.33276.40267.37271.00267.03#3573.10443.87553.23425.07402.53413.93397.50402.23397.10#4183.30160.37163.17155.40138.50139.00136.40137.27135.77Table 11
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the four classes of the benchmark given in [7, 8] with cov=80%.
No.HHHRCHHCRHCRRRCCRC#195.9982.2183.5680.3369.8269.9768.7069.3268.37#296.8976.9988.7072.5567.6668.9366.6767.5866.59#395.6874.1092.3670.9667.2069.1066.3667.1566.29#494.4882.6684.1180.1071.3971.6570.3170.7669.98No.HHHRCHHCRHCRRRCCRC#143.0022.4624.4619.673.994.212.323.251.82#247.1316.9034.6810.162.734.651.232.601.10#345.2412.4840.217.732.014.900.741.940.63#437.5820.3722.4616.623.944.322.363.011.88For this set of benchmarks, loweringcov from 90% to 80% has not changed the relative performance of the three groups of our LS algorithms. However, the relative performance of the three effective algorithms has changed.Figures5 and 6 show boxplots of lengths of schedules returned by the four good LS algorithms for the benchmark proposed in [7, 8] with cov of 90% and 80%, respectively. In Figure 5, one can see that the minimum for [HMA, HMA] is always greater than or equal to the maximum for the other three algorithms. Moreover, the results for [HMA, HMA] have a much smaller interquartile range than those for the other algorithms. The schedules’ lengths are less dispersed, proving the higher stability of the [HMA, HMA] variant for cov=90%. In Figure 6, the values of all parameters for [HMA, HMA] are better than those of the corresponding parameters for the other algorithms. However, for three out of four classes of the benchmark, the results for [CAIA, HMA] have the smallest interquartile range. Less dispersed schedules’ lengths prove the higher stability of the [CAIA, HMA] variant for cov=80%. Again, boxplot graphs confirm conclusions from mean values.Figure 5
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [7, 8] with cov=90%.Figure 6
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [7, 8] with cov=80%.


### 5.3.2. The Benchmark Proposed by Manju et al. in [9]

The authors of the minimal-heuristic approach [9] proposed the following set of benchmarks for experiments with algorithms solving MLCP. The monitored area is a square with a side size of 150 abstract units. POIs and sensors are distributed randomly over this area. In the first five test cases (1.1–1.5), we have 100 POIs while the sensors’ numbers are 50, 100, 150, 200, and 250, respectively. In the next five test cases (2.1–2.5), there are 150 sensors, while the numbers of POIs are 20, 40, 60, 80, and 100. As in [9], the sensing range is 70 abstract units and cov=100%. Requiring full coverage is reasonable because this set of benchmarks gives much more redundant coverage of POIs by sensors; that is, larger numbers of sensors cover individual POIs than in SCP1 and the benchmark from [7, 8] (see the next subsection for details). We used Tbatt=40.Table12 gives the results of our LS strategies for the benchmarks from [9]. The top part of Table 13 shows the mean percentage qualities of the best-found schedules returned by the LS algorithms. In the bottom part of Table 13, we present mean percentage improvements of the lengths of schedules produced by the LS phase with respect to the lengths of schedules returned by the initialization phase.Table 12
Mean lengths of schedules returned by the LS algorithms for the benchmark given in [9] with cov=100%.
No.HHHRCHHCRHCRRRCCRC1.1548.27506.38487.45406.88392.13452.05374.50435.50370.631.21189.92925.00983.15759.95775.80892.48744.90848.02741.751.31756.401328.171444.801099.901125.381299.631088.631222.151085.401.42509.071730.051979.031487.801516.351763.381476.351651.331473.051.53100.282009.632495.501861.131892.332212.931854.702059.821850.702.12121.101711.031787.531442.901459.331655.031437.531583.551434.222.21984.281513.631637.901271.301282.831481.331264.701410.901259.922.31808.701405.951558.401196.831207.881403.971186.651328.501182.952.41829.631311.081520.031154.171173.421362.001143.471284.971140.052.51850.971317.221487.131128.251144.101331.421116.951256.551113.05Table 13
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the ten classes of the benchmark given in [9] with cov=100%.
No.HHHRCHHCRHCRRRCCRC1.178.4472.4469.7458.2156.1064.6753.5862.3053.021.285.3666.3670.5354.5255.6564.0253.4460.8353.211.384.4063.8269.4352.8554.0862.4552.3158.7352.161.489.2361.5270.3852.9153.9262.7152.5058.7252.381.587.8056.9170.6752.7153.5962.6752.5358.3452.412.181.9666.1169.0755.7556.3963.9555.5561.1955.422.284.3364.3369.6154.0354.5262.9553.7559.9653.552.385.8866.7674.0056.8357.3566.6756.3563.0856.172.483.3259.7069.2252.5653.4362.0252.0758.5151.912.586.2561.3869.3052.5753.3162.0452.0558.5551.87No.HHHRCHHCRHCRRRCCRC1.151.1740.2334.2212.638.1224.503.1719.992.051.262.1126.7833.673.415.5521.401.2915.350.861.362.9023.9933.891.934.3020.460.8813.280.581.471.3418.6635.031.533.5120.370.7512.690.521.568.149.2735.250.862.5819.950.5111.620.292.148.7620.3825.380.982.1516.030.6010.980.362.258.5721.1030.721.402.3418.210.8612.560.462.354.2319.6332.421.682.6119.330.8212.900.502.461.9216.0834.061.863.5820.190.8913.380.582.567.5419.5634.422.013.4320.390.9613.600.61One can see from these results that [HMA, HMA] is still the winner. [CAIA, HMA] is the second best LS approach in 9 out of 10 cases. As the number of sensors grows (which means that the redundancy of coverage also increases), [CAIA, RFTA] becomes better than [HMA, RFTA].Since in our experiments with the benchmark set SCP1 and with the benchmarks from [7, 8] we used cov equal to 80% and 90%, we also performed tests with the data sets from [9] using the same values of cov. For these test cases, the number of alternative sensor activity configurations satisfying coverage level is relatively high due to high redundancy in POI coverage. Lowering cov makes the number of these configurations even greater. The results for cov=90% are given in Tables 14 and 15 while the results for cov=80% are provided in Tables 16 and 17.Table 14
Mean lengths of schedules returned by the LS algorithms for the benchmark given in [9] with cov=90%.
No.HHHRCHHCRHCRRRCCRC1.1755.92728.50826.48724.63725.30802.63723.38786.83722.481.21490.421469.131664.131464.281465.501599.301463.421559.721462.221.32206.972140.102444.952137.322139.202325.252136.702267.322135.471.42976.402921.503361.132920.652921.303181.552919.973095.382918.681.53743.653654.904226.153651.303652.183977.003650.053860.323649.282.12523.252338.202584.652305.632308.552480.972303.382422.952301.882.22293.402230.902521.252214.822215.182399.502213.632344.302212.052.32253.452197.202508.682195.402197.352388.502194.782332.572193.782.42259.722195.902512.952192.752194.932382.682192.402327.032191.452.52242.602191.822508.322190.002191.202388.402188.882321.752187.60Table 15
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the ten classes of the benchmark given in [9] with cov=90%.
No.HHHRCHHCRHCRRRCCRC1.178.9176.0486.2775.6475.7183.7875.5182.1375.411.280.3079.1689.6678.8978.9686.1778.8584.0478.781.381.8679.3890.6979.2879.3586.2579.2584.1079.211.480.2578.7790.6278.7478.7685.7878.7383.4678.691.581.0579.1391.4979.0579.0786.1079.0283.5779.012.172.7467.4074.5166.4666.5571.5266.4069.8566.362.278.3376.1986.1175.6475.6581.9575.6080.0675.552.378.6076.6487.5076.5776.6483.3176.5581.3676.522.477.0474.8785.6874.7674.8481.2474.7579.3474.722.578.3976.6187.6776.5576.5983.4876.5181.1576.46No.HHHRCHHCRHCRRRCCRC1.15.571.5015.270.911.0111.890.730.730.611.22.270.7914.280.450.539.810.390.390.311.33.790.4114.820.270.369.150.240.240.181.42.240.2015.380.170.199.190.150.150.101.52.870.2716.020.160.189.150.120.120.102.110.291.8612.730.360.498.120.260.260.192.23.801.0014.270.270.298.700.220.220.152.32.910.3214.640.230.339.110.210.210.162.43.320.3714.960.230.338.960.210.210.172.52.790.3714.970.280.349.430.230.230.17Table 16
Mean lengths of schedules returned by the LS algorithms for the benchmark given in [9] with cov=80%.
No.HHHRCHHCRHCRRRCCRC1.1973.10969.851030.22968.80968.671020.33968.081009.98967.631.21969.781968.402083.751967.951967.922056.051967.602032.171966.921.32890.602886.073059.932885.402885.353009.222884.972971.972884.501.43938.823934.854197.383934.703934.404110.503934.454051.633933.531.54931.934930.525277.354930.234930.885149.184930.255072.934929.882.13062.823039.933205.323038.503039.253155.603038.453120.103037.852.22963.932961.723136.972960.532960.653086.782960.823050.032959.802.32980.102978.783161.282977.652976.973102.932977.103067.322976.322.42961.702959.603140.322958.552958.303086.322958.103047.952957.432.52968.402966.473145.072965.952965.973093.152966.033055.302965.28Table 17
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the ten classes of the benchmark given in [9] with cov=80%.
No.HHHRCHHCRHCRRRCCRC1.182.0581.7786.8781.6981.6886.0381.6385.1681.591.285.5785.5190.5285.4985.4989.3285.4788.2885.441.382.4782.3487.3082.3282.3285.8682.3184.7982.301.483.7383.6589.2383.6583.6487.3883.6486.1383.621.584.7184.6990.6484.6884.6988.4484.6887.1384.682.181.2680.6685.0480.6280.6483.7380.6282.7880.602.286.9486.8892.0286.8486.8590.5586.8589.4786.822.386.3886.3491.6386.3186.2989.9486.2988.9186.272.486.7586.6991.9886.6686.6590.4086.6589.2886.632.583.2083.1488.1583.1383.1386.6983.1385.6383.11No.HHHRCHHCRHCRRRCCRC1.10.960.616.980.500.485.930.424.860.371.20.290.226.170.190.194.740.183.510.141.30.340.186.280.150.154.500.143.200.121.40.220.116.840.110.104.620.103.110.081.50.090.067.160.060.074.530.062.980.052.10.980.175.780.120.154.090.122.890.102.20.250.186.180.140.144.460.153.200.112.30.250.206.390.160.144.410.153.210.122.40.270.206.380.160.164.540.153.230.132.50.200.136.210.110.114.450.113.160.09In this set of experiments, [CAIA, HMA] is the best LS algorithm in all cases. Forcov=90%, [HMA, HMA] is the second best in test Case 2.1. In all other test cases, for both cov equal to 80% and that equal to 90%, the second best is [CAIA, RFTA]. The third is [CAIA, CAIA]. Thus, for cov equal to 80% or 90%, the perturbation method used in CAIA always gives results better than the other two methods. Interestingly, for cov=80%, the remaining six LS algorithms (including [HMA, HMA]) give a relative improvement of less than 1%.Figures7, 8, and 9 show boxplots of lengths of schedules returned by the four good LS algorithms for the benchmark proposed in [9] with cov of 100%, 90%, and 80%, respectively. In Figure 7 [HMA, HMA] always gives the largest values of minimum, maximum, and quartiles. [CAIA, HMA] and [HMA, CAIA] have usually smaller interquartile ranges than [HMA, HMA] and [HMA, RFTA]. The small value of the interquartile range for [HMA, CAIA] with the mean value lower than the mean values of the results returned by other algorithms means that [HMA, CAIA] never gives good results for this benchmark and cov=100%. In Figure 8, [CAIA, HMA] not only has the highest values of all parameters but also almost always has the smallest interquartile range (only for class 1.1, [HMA, RFTA] has a smaller interquartile range). Decreasing cov from 100 to 90% changed the winner—more random perturbation method from LSCAIA turned out to be better in this case. Finally, in Figure 9, [CAIA, HMA] again has the highest values of all parameters and often has the smallest interquartile range. However, in this case, interquartile ranges for all four algorithms are close to each other. One more time, boxplot graphs confirm conclusions from mean values.Figure 7
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [9] with cov=100%.Figure 8
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [9] with cov=90%.Figure 9
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [9] with cov=80%.


## 5.3.1. The Benchmark Proposed by Tretyakova et al. in [7, 8]

We selected four classes of problems proposed in [7, 8]. In all cases, the monitored area is a square with a side size of 100 abstract units. In three classes from [8], there are 100 POIs while the number of sensors is 100, 200, and 300 (cases #1, #2, and #3). In the class from [7], we have 400 POIs and 100 sensors (case #4). The remaining parameters have also the same values as in [7, 8]; that is, cov=90%, the sensing range is 20 abstract units, and Tbatt=20. Table 8 presents the mean measured lengths of schedules. Table 9 shows the mean percentage qualities of the best-found schedules returned by our LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the four classes of the benchmark in question, assuming cov=90%.Table 8
Mean lengths of schedules returned by the LS algorithms for each of the four classes of the benchmark given in [7, 8] with cov=90%.
No.HHHRCHHCRHCRRRCCRC#1165.97153.47134.63147.07110.20104.40101.10102.07100.23#2337.97297.37284.47272.10219.80200.87191.20193.53190.00#3510.53423.50441.43373.33319.07301.10282.20287.87281.07#4157.00145.03127.60139.17104.63100.9798.6399.5397.63Table 9
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the four classes of the benchmark given in [7, 8] with cov=90%.
No.HHHRCHHCRHCRRRCCRC#197.0689.7578.7386.0064.4461.0559.1259.6958.62#298.5386.7082.9379.3364.0858.5655.7456.4255.39#399.1382.2385.7272.4961.9558.4754.8055.9054.58#498.1390.6579.7586.9865.4063.1061.6562.2161.02No.HHHRCHHCRHCRRRCCRC#171.3558.4739.0351.8713.777.784.365.353.46#280.8559.1252.2245.5917.647.472.293.551.64#383.9452.5759.0334.4814.988.471.663.711.25#465.9553.3534.8847.1210.636.714.245.183.18This set of experiment results are similar to our earlier results with the benchmark SCP1. [HMA, HMA] always gives the most extended schedules. Algorithms [HMA, RFTA], [CAIA, HMA], and [HMA, CAIA] are worse than [HMA, HMA] but significantly better than the remaining five approaches.Since in experiments with SCP1, we performed computations for two values ofcov, 80% and 90%, we did the same for the test cases from [7, 8]. Tables 10 and 11 show the set of results similar to the ones in Tables 8 and 9 but obtained for cov=80%.Table 10
Mean lengths of schedules returned by the LS algorithms for the benchmark given in [7, 8] with cov=80%.
No.HHHRCHHCRHCRRRCCRC#1193.90166.07168.80162.27141.03141.33138.77140.03138.10#2388.53308.73355.70290.93271.33276.40267.37271.00267.03#3573.10443.87553.23425.07402.53413.93397.50402.23397.10#4183.30160.37163.17155.40138.50139.00136.40137.27135.77Table 11
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the four classes of the benchmark given in [7, 8] with cov=80%.
No.HHHRCHHCRHCRRRCCRC#195.9982.2183.5680.3369.8269.9768.7069.3268.37#296.8976.9988.7072.5567.6668.9366.6767.5866.59#395.6874.1092.3670.9667.2069.1066.3667.1566.29#494.4882.6684.1180.1071.3971.6570.3170.7669.98No.HHHRCHHCRHCRRRCCRC#143.0022.4624.4619.673.994.212.323.251.82#247.1316.9034.6810.162.734.651.232.601.10#345.2412.4840.217.732.014.900.741.940.63#437.5820.3722.4616.623.944.322.363.011.88For this set of benchmarks, loweringcov from 90% to 80% has not changed the relative performance of the three groups of our LS algorithms. However, the relative performance of the three effective algorithms has changed.Figures5 and 6 show boxplots of lengths of schedules returned by the four good LS algorithms for the benchmark proposed in [7, 8] with cov of 90% and 80%, respectively. In Figure 5, one can see that the minimum for [HMA, HMA] is always greater than or equal to the maximum for the other three algorithms. Moreover, the results for [HMA, HMA] have a much smaller interquartile range than those for the other algorithms. The schedules’ lengths are less dispersed, proving the higher stability of the [HMA, HMA] variant for cov=90%. In Figure 6, the values of all parameters for [HMA, HMA] are better than those of the corresponding parameters for the other algorithms. However, for three out of four classes of the benchmark, the results for [CAIA, HMA] have the smallest interquartile range. Less dispersed schedules’ lengths prove the higher stability of the [CAIA, HMA] variant for cov=80%. Again, boxplot graphs confirm conclusions from mean values.Figure 5
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [7, 8] with cov=90%.Figure 6
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [7, 8] with cov=80%.


## 5.3.2. The Benchmark Proposed by Manju et al. in [9]

The authors of the minimal-heuristic approach [9] proposed the following set of benchmarks for experiments with algorithms solving MLCP. The monitored area is a square with a side size of 150 abstract units. POIs and sensors are distributed randomly over this area. In the first five test cases (1.1–1.5), we have 100 POIs while the sensors’ numbers are 50, 100, 150, 200, and 250, respectively. In the next five test cases (2.1–2.5), there are 150 sensors, while the numbers of POIs are 20, 40, 60, 80, and 100. As in [9], the sensing range is 70 abstract units and cov=100%. Requiring full coverage is reasonable because this set of benchmarks gives much more redundant coverage of POIs by sensors; that is, larger numbers of sensors cover individual POIs than in SCP1 and the benchmark from [7, 8] (see the next subsection for details). We used Tbatt=40.Table12 gives the results of our LS strategies for the benchmarks from [9]. The top part of Table 13 shows the mean percentage qualities of the best-found schedules returned by the LS algorithms. In the bottom part of Table 13, we present mean percentage improvements of the lengths of schedules produced by the LS phase with respect to the lengths of schedules returned by the initialization phase.Table 12
Mean lengths of schedules returned by the LS algorithms for the benchmark given in [9] with cov=100%.
No.HHHRCHHCRHCRRRCCRC1.1548.27506.38487.45406.88392.13452.05374.50435.50370.631.21189.92925.00983.15759.95775.80892.48744.90848.02741.751.31756.401328.171444.801099.901125.381299.631088.631222.151085.401.42509.071730.051979.031487.801516.351763.381476.351651.331473.051.53100.282009.632495.501861.131892.332212.931854.702059.821850.702.12121.101711.031787.531442.901459.331655.031437.531583.551434.222.21984.281513.631637.901271.301282.831481.331264.701410.901259.922.31808.701405.951558.401196.831207.881403.971186.651328.501182.952.41829.631311.081520.031154.171173.421362.001143.471284.971140.052.51850.971317.221487.131128.251144.101331.421116.951256.551113.05Table 13
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the ten classes of the benchmark given in [9] with cov=100%.
No.HHHRCHHCRHCRRRCCRC1.178.4472.4469.7458.2156.1064.6753.5862.3053.021.285.3666.3670.5354.5255.6564.0253.4460.8353.211.384.4063.8269.4352.8554.0862.4552.3158.7352.161.489.2361.5270.3852.9153.9262.7152.5058.7252.381.587.8056.9170.6752.7153.5962.6752.5358.3452.412.181.9666.1169.0755.7556.3963.9555.5561.1955.422.284.3364.3369.6154.0354.5262.9553.7559.9653.552.385.8866.7674.0056.8357.3566.6756.3563.0856.172.483.3259.7069.2252.5653.4362.0252.0758.5151.912.586.2561.3869.3052.5753.3162.0452.0558.5551.87No.HHHRCHHCRHCRRRCCRC1.151.1740.2334.2212.638.1224.503.1719.992.051.262.1126.7833.673.415.5521.401.2915.350.861.362.9023.9933.891.934.3020.460.8813.280.581.471.3418.6635.031.533.5120.370.7512.690.521.568.149.2735.250.862.5819.950.5111.620.292.148.7620.3825.380.982.1516.030.6010.980.362.258.5721.1030.721.402.3418.210.8612.560.462.354.2319.6332.421.682.6119.330.8212.900.502.461.9216.0834.061.863.5820.190.8913.380.582.567.5419.5634.422.013.4320.390.9613.600.61One can see from these results that [HMA, HMA] is still the winner. [CAIA, HMA] is the second best LS approach in 9 out of 10 cases. As the number of sensors grows (which means that the redundancy of coverage also increases), [CAIA, RFTA] becomes better than [HMA, RFTA].Since in our experiments with the benchmark set SCP1 and with the benchmarks from [7, 8] we used cov equal to 80% and 90%, we also performed tests with the data sets from [9] using the same values of cov. For these test cases, the number of alternative sensor activity configurations satisfying coverage level is relatively high due to high redundancy in POI coverage. Lowering cov makes the number of these configurations even greater. The results for cov=90% are given in Tables 14 and 15 while the results for cov=80% are provided in Tables 16 and 17.Table 14
Mean lengths of schedules returned by the LS algorithms for the benchmark given in [9] with cov=90%.
No.HHHRCHHCRHCRRRCCRC1.1755.92728.50826.48724.63725.30802.63723.38786.83722.481.21490.421469.131664.131464.281465.501599.301463.421559.721462.221.32206.972140.102444.952137.322139.202325.252136.702267.322135.471.42976.402921.503361.132920.652921.303181.552919.973095.382918.681.53743.653654.904226.153651.303652.183977.003650.053860.323649.282.12523.252338.202584.652305.632308.552480.972303.382422.952301.882.22293.402230.902521.252214.822215.182399.502213.632344.302212.052.32253.452197.202508.682195.402197.352388.502194.782332.572193.782.42259.722195.902512.952192.752194.932382.682192.402327.032191.452.52242.602191.822508.322190.002191.202388.402188.882321.752187.60Table 15
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the ten classes of the benchmark given in [9] with cov=90%.
No.HHHRCHHCRHCRRRCCRC1.178.9176.0486.2775.6475.7183.7875.5182.1375.411.280.3079.1689.6678.8978.9686.1778.8584.0478.781.381.8679.3890.6979.2879.3586.2579.2584.1079.211.480.2578.7790.6278.7478.7685.7878.7383.4678.691.581.0579.1391.4979.0579.0786.1079.0283.5779.012.172.7467.4074.5166.4666.5571.5266.4069.8566.362.278.3376.1986.1175.6475.6581.9575.6080.0675.552.378.6076.6487.5076.5776.6483.3176.5581.3676.522.477.0474.8785.6874.7674.8481.2474.7579.3474.722.578.3976.6187.6776.5576.5983.4876.5181.1576.46No.HHHRCHHCRHCRRRCCRC1.15.571.5015.270.911.0111.890.730.730.611.22.270.7914.280.450.539.810.390.390.311.33.790.4114.820.270.369.150.240.240.181.42.240.2015.380.170.199.190.150.150.101.52.870.2716.020.160.189.150.120.120.102.110.291.8612.730.360.498.120.260.260.192.23.801.0014.270.270.298.700.220.220.152.32.910.3214.640.230.339.110.210.210.162.43.320.3714.960.230.338.960.210.210.172.52.790.3714.970.280.349.430.230.230.17Table 16
Mean lengths of schedules returned by the LS algorithms for the benchmark given in [9] with cov=80%.
No.HHHRCHHCRHCRRRCCRC1.1973.10969.851030.22968.80968.671020.33968.081009.98967.631.21969.781968.402083.751967.951967.922056.051967.602032.171966.921.32890.602886.073059.932885.402885.353009.222884.972971.972884.501.43938.823934.854197.383934.703934.404110.503934.454051.633933.531.54931.934930.525277.354930.234930.885149.184930.255072.934929.882.13062.823039.933205.323038.503039.253155.603038.453120.103037.852.22963.932961.723136.972960.532960.653086.782960.823050.032959.802.32980.102978.783161.282977.652976.973102.932977.103067.322976.322.42961.702959.603140.322958.552958.303086.322958.103047.952957.432.52968.402966.473145.072965.952965.973093.152966.033055.302965.28Table 17
Mean percentage qualities of the best-found schedules returned by the LS algorithms (the top table) and mean percentage improvements of the lengths of schedules returned by the LS phase with respect to the lengths of schedules returned by the initialization phase (the bottom table) for each of the ten classes of the benchmark given in [9] with cov=80%.
No.HHHRCHHCRHCRRRCCRC1.182.0581.7786.8781.6981.6886.0381.6385.1681.591.285.5785.5190.5285.4985.4989.3285.4788.2885.441.382.4782.3487.3082.3282.3285.8682.3184.7982.301.483.7383.6589.2383.6583.6487.3883.6486.1383.621.584.7184.6990.6484.6884.6988.4484.6887.1384.682.181.2680.6685.0480.6280.6483.7380.6282.7880.602.286.9486.8892.0286.8486.8590.5586.8589.4786.822.386.3886.3491.6386.3186.2989.9486.2988.9186.272.486.7586.6991.9886.6686.6590.4086.6589.2886.632.583.2083.1488.1583.1383.1386.6983.1385.6383.11No.HHHRCHHCRHCRRRCCRC1.10.960.616.980.500.485.930.424.860.371.20.290.226.170.190.194.740.183.510.141.30.340.186.280.150.154.500.143.200.121.40.220.116.840.110.104.620.103.110.081.50.090.067.160.060.074.530.062.980.052.10.980.175.780.120.154.090.122.890.102.20.250.186.180.140.144.460.153.200.112.30.250.206.390.160.144.410.153.210.122.40.270.206.380.160.164.540.153.230.132.50.200.136.210.110.114.450.113.160.09In this set of experiments, [CAIA, HMA] is the best LS algorithm in all cases. Forcov=90%, [HMA, HMA] is the second best in test Case 2.1. In all other test cases, for both cov equal to 80% and that equal to 90%, the second best is [CAIA, RFTA]. The third is [CAIA, CAIA]. Thus, for cov equal to 80% or 90%, the perturbation method used in CAIA always gives results better than the other two methods. Interestingly, for cov=80%, the remaining six LS algorithms (including [HMA, HMA]) give a relative improvement of less than 1%.Figures7, 8, and 9 show boxplots of lengths of schedules returned by the four good LS algorithms for the benchmark proposed in [9] with cov of 100%, 90%, and 80%, respectively. In Figure 7 [HMA, HMA] always gives the largest values of minimum, maximum, and quartiles. [CAIA, HMA] and [HMA, CAIA] have usually smaller interquartile ranges than [HMA, HMA] and [HMA, RFTA]. The small value of the interquartile range for [HMA, CAIA] with the mean value lower than the mean values of the results returned by other algorithms means that [HMA, CAIA] never gives good results for this benchmark and cov=100%. In Figure 8, [CAIA, HMA] not only has the highest values of all parameters but also almost always has the smallest interquartile range (only for class 1.1, [HMA, RFTA] has a smaller interquartile range). Decreasing cov from 100 to 90% changed the winner—more random perturbation method from LSCAIA turned out to be better in this case. Finally, in Figure 9, [CAIA, HMA] again has the highest values of all parameters and often has the smallest interquartile range. However, in this case, interquartile ranges for all four algorithms are close to each other. One more time, boxplot graphs confirm conclusions from mean values.Figure 7
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [9] with cov=100%.Figure 8
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [9] with cov=90%.Figure 9
Boxplots of lengths of schedules (minimum, lower quartile, median, upper quartile, maximum, and outliers) returned by the LS algorithms for the benchmark given in [9] with cov=80%.


## 5.4. What Affects Algorithms’ Effectiveness?

### 5.4.1. The Redundancy in Coverage of POIs by Sensors in the Benchmarks

To explain differences in the relative performance of our nine LS approaches on various benchmarks, we investigated the numbers of sensors able to control particular POIs in SCP1 and the benchmarks from [7–9]. Our findings are presented in Figures 10–12.Figure 10
Percentage numbers of POIs covered by different numbers of sensors for SCP1.Figure 11
Percentage numbers of POIs covered by different numbers of sensors for the benchmark given in [9].Figure 12
Percentage numbers of POIs covered by different numbers of sensors for the benchmark given in [7, 8].Figures10 and 12 show that in the test cases from SCP1 and from [7, 8], every POI can be monitored by not more than 50 sensors and, in some of these cases, even by not more than 20 sensors. On the other hand, Figure 11 shows that in the test cases from [9], many POIs can be monitored by more than 100 sensors. This high monitoring redundancy makes finding a cover for POIs much more manageable, even for cov=100%.We conclude from the above considerations that the perturbation method used in LSCAIA works better than the other two methods when there are many possibilities of forming a required cover for a given set of POIs. When the number of such options decreases due to a higher value of cov or a smaller number of sensors, the perturbation method from LSHMA becomes better. The advantage of the perturbation method from LSCAIA over the one from LSHMA when there is much redundancy in coverage of POIs is probably that the former removes more slots from the original schedule than the latter. When the number of similar legal covers becomes large, there are many possibilities of creating a valid schedule. Removing more slots and restoring more power to sensor batteries gives the refinement method more space to show its effectiveness and improve the original schedule. On the other hand, when the redundancy in coverage of POIs decreases, a more systematic approach of HMA works better.Let us also notice that too much redundancy in coverage of POIs by sensors is not desirable in real life due to increased costs. Of course, the ultimate redundancy level depends mainly on a specific application.


### 5.4.2. Strengths and Weaknesses of the Perturbation Operators

The good performance of the perturbation method from LSHMA comes from the fact that this method does not remove a single slot from the original schedule. Instead, the method only changes sets of active sensors in selected slots. Consequently, the set of sensors with non-empty batteries changes too. It opens up new possibilities for producing one additional slot in the refinement step, which is sufficient to obtain a more extended schedule. On the other hand, the perturbation methods from LSRFTA and LSCAIA delete slots from the initial schedule. It means that during the refinement step, the minimum goal is to create at least as many new slots as were removed during the perturbation. When we succeed, we can go further and try to generate more slots to make the new schedule longer. It can happen, nevertheless, that we are not able to get as many additional slots as we removed. Despite the refinement step execution, we get a shorter schedule. Slots or sensors in slots are selected for removal randomly, so our success depends on luck. As we mentioned above, when there is much redundancy in coverage of POIs by sensors and we remove many slots from the original schedule, the chances of removing the right slots and eventually getting a more extended schedule grow.


## 5.4.1. The Redundancy in Coverage of POIs by Sensors in the Benchmarks

To explain differences in the relative performance of our nine LS approaches on various benchmarks, we investigated the numbers of sensors able to control particular POIs in SCP1 and the benchmarks from [7–9]. Our findings are presented in Figures 10–12.Figure 10
Percentage numbers of POIs covered by different numbers of sensors for SCP1.Figure 11
Percentage numbers of POIs covered by different numbers of sensors for the benchmark given in [9].Figure 12
Percentage numbers of POIs covered by different numbers of sensors for the benchmark given in [7, 8].Figures10 and 12 show that in the test cases from SCP1 and from [7, 8], every POI can be monitored by not more than 50 sensors and, in some of these cases, even by not more than 20 sensors. On the other hand, Figure 11 shows that in the test cases from [9], many POIs can be monitored by more than 100 sensors. This high monitoring redundancy makes finding a cover for POIs much more manageable, even for cov=100%.We conclude from the above considerations that the perturbation method used in LSCAIA works better than the other two methods when there are many possibilities of forming a required cover for a given set of POIs. When the number of such options decreases due to a higher value of cov or a smaller number of sensors, the perturbation method from LSHMA becomes better. The advantage of the perturbation method from LSCAIA over the one from LSHMA when there is much redundancy in coverage of POIs is probably that the former removes more slots from the original schedule than the latter. When the number of similar legal covers becomes large, there are many possibilities of creating a valid schedule. Removing more slots and restoring more power to sensor batteries gives the refinement method more space to show its effectiveness and improve the original schedule. On the other hand, when the redundancy in coverage of POIs decreases, a more systematic approach of HMA works better.Let us also notice that too much redundancy in coverage of POIs by sensors is not desirable in real life due to increased costs. Of course, the ultimate redundancy level depends mainly on a specific application.


## 5.4.2. Strengths and Weaknesses of the Perturbation Operators

The good performance of the perturbation method from LSHMA comes from the fact that this method does not remove a single slot from the original schedule. Instead, the method only changes sets of active sensors in selected slots. Consequently, the set of sensors with non-empty batteries changes too. It opens up new possibilities for producing one additional slot in the refinement step, which is sufficient to obtain a more extended schedule. On the other hand, the perturbation methods from LSRFTA and LSCAIA delete slots from the initial schedule. It means that during the refinement step, the minimum goal is to create at least as many new slots as were removed during the perturbation. When we succeed, we can go further and try to generate more slots to make the new schedule longer. It can happen, nevertheless, that we are not able to get as many additional slots as we removed. Despite the refinement step execution, we get a shorter schedule. Slots or sensors in slots are selected for removal randomly, so our success depends on luck. As we mentioned above, when there is much redundancy in coverage of POIs by sensors and we remove many slots from the original schedule, the chances of removing the right slots and eventually getting a more extended schedule grow.


## 6. Conclusions

In this paper, we proposed 27 local search algorithms solving MLCP and studied the relative performance of 9 of them. The starting point in this research was three LS algorithms presented in our earlier papers:LSHMA, LSCAIA, and LSRFTA.The local search approach consists of two major steps: generating an initial solution to the problem and looking for its neighbor. The second step can be divided into two substeps executed iteratively: perturbation of the original solution and refinement of the perturbation’s result. This way, we have three problem-specific steps in our LS algorithms for MLCP. By swapping these three steps between three basic algorithms, we can get 27 different versions of LS solving MLCP.Our research studied the relative performance of just nine of these versions—the initial problem solution was always generated using CAIA. For experimental research, we used the benchmark SCP1 (proposed in our earlier papers) and the benchmarks proposed in [7–9].We computed the mean lengths of schedules returned by the LS algorithms, mean percentage qualities of the best-found schedules returned by the LS algorithms, and mean percentage improvements of the lengths of schedules produced by the LS phase with respect to the lengths of schedules returned by the initialization phase. Moreover, we analyzed boxplots of lengths of schedules returned by the four best LS algorithms.The results of our experiments show that for the SCP1 benchmark and the benchmarks from [7, 8], the best pair of perturbation and refinement methods is usually the one used in LSHMA, i.e., [HMA, HMA]. Approaches [HMA, RFTA], [CAIA, HMA], and [HMA, CAIA] are also effective, while the remaining combinations give much worse results. However, experiments with the benchmarks from [9] gave different results. When we assume cov=100%, [HMA, HMA] is still the best approach, but for cov equal to 80% or 90%, the perturbation method used in LSCAIA gives better results. We conclude that the more redundant the coverage of POIs by sensors and the lower the value of cov, the more effective the perturbation method from LSCAIA. When this redundancy is lower or cov is higher, the perturbation method used in LSHMA becomes better. One could ask about a threshold value of cov for which the perturbation method from LSCAIA becomes better than the method from LSHMA. The results show that this value is problem-dependent. It depends on the redundancy in coverage of POIs by sensors. However, no rule defining this threshold value can be determined based on the presented experiments. It can be figured out only by conducting experiments with a given class of problems.



---

*Source: 3745358-2022-11-12.xml*