Optimizing Coverage in Wireless Sensor Networks: A Binary Ant Colony Algorithm with Hill Climbing

Abstract

Wireless sensor networks (WSNs) play a vital role in various fields, but ensuring optimal coverage poses a significant challenge due to the limited energy resources that constrain sensor nodes. To address this issue, this paper presents a novel approach that combines the binary ant colony algorithm (BACA), a variant of ant colony optimization (ACO), with other search optimization algorithms, such as hill climbing (HC) and simulated annealing (SA). The BACA is employed to generate an initial solution by emulating the foraging behavior of ants and the pheromone trails they leave behind in their search for food. However, we acknowledge that the BACA alone may not guarantee the most optimal solution. Subsequently, HC and SA are optimization search algorithms that refine the initial solution obtained by the BACA to find a more enhanced solution. Through extensive simulations and experiments, we demonstrate that our proposed approach results in enhanced coverage and energy-efficient coverage in a two-dimensional (2D) field. Interestingly, our findings reveal that HC consistently outperforms SA, particularly in less complex search spaces, leveraging its robust exploitation approach. Our research contributes valuable insights into optimizing WSN coverage, highlighting the superiority of HC in this context. Finally, we outline promising future research directions that can advance the optimization of WSN coverage.

1. Introduction

Wireless sensor networks (WSNs) have emerged as a transformative technology with diverse applications in environmental monitoring, security/surveillance, and health care. These networks consist of a system of spatially dispersed and dedicated sensors that are aimed to monitor and cover a field. The core challenge lies in achieving optimal coverage while considering the inherent constraints of WSNs, such as limited energy resources, including processing power, energy consumption, and communication range.

The primary objective with coverage is to be able to monitor a field for the longest amount of time while minimizing energy consumption. There are different types of coverage that can be achieved: area coverage and target coverage. Area coverage refers to the extent to which the sensing area is covered by the sensing nodes. Sensors are strategically placed to ensure that the entire area is covered and overlap exists between neighboring sensors. This overlap, or redundancy of sensors, allows us to achieve “k-coverage”, which guarantees that every point in the field of interest is covered by at least k sensors. On the other hand, target coverage refers to the extent to which specific points of interest are covered by sensor nodes. Rather than monitoring the entire field, target coverage involves positioning the sensor nodes in a way that they can detect events occurring at specific points. Target coverage is crucial for applications such as surveillance, event detection, and localization.

To address the problem of coverage in WSNs, various nature-inspired algorithms have been employed. For example, particle swarm optimization (PSO) emulates the behavior of flocks of birds where particles are used to explore the search space to find the most optimal solution. Each particle represents a possible solution and moves with the search space based on its own experience and the experiences of neighboring particles. Another approach is known as the genetic algorithm, which simulates the process of natural selection and evolution. It uses methods such as reproduction, crossover, and mutation to introduce new potential solutions toward an optimal or near-optimal solution.

1.1. Problem Statement

The major questions that are related to the coverage problem in 2D wireless sensor networks, which we attempt to answer in this paper, are listed below:

• How can we determine the optimal configuration of sensor nodes so that we can achieve one coverage?
• How can we minimize energy consumption while maintaining adequate coverage?

1.2. Motivations

The problem of coverage optimization in WSNs poses several challenges, primarily due to the limited energy resources of sensor nodes. Achieving high coverage while considering energy consumption, network lifetime, and deployment costs requires a delicate balance. Despite notable progress, the problem is still very challenging, and there is still considerable scope for future advancements in this work. Particularly, the binary ant colony algorithm (BACA) has not been extensively researched in the context of coverage. To the authors’ knowledge, no existing work has explored the combination of the BACA with an optimization algorithm such as hill climbing or simulated annealing to enhance the solution of coverage.

1.3. Major Contributions

In our approach, we propose utilizing a variant of the ant colony optimization algorithm, a swarm-based nature-inspired algorithm known as the binary ant colony algorithm (BACA). To further enhance the effectiveness of our approach, we integrate and compare the effectiveness between two optimization algorithms known as hill climbing (HC) and simulated annealing (SA). By refining the coverage problem using the BACA and incorporating the optimization capabilities of HC and SA, we expect to achieve enhanced coverage and energy-efficient WSNs to cover a 2D field.

1.4. Paper Organization

The remainder of this paper is organized as follows: In Section 2, we present some of the terminology and assumptions that are necessary to provide context and define key terms and variables used in this paper. In Section 3, we present some of the existing approaches that were proposed to address the problem of coverage in 2D wireless sensor networks. In Section 4, we briefly address the traveling salesman problem (TSP) and how it relates to ant colony optimization (ACO). In Section 5, we discuss our approach to the problem of coverage in WSNs and how we use the ACO and the binary ant colony algorithm (BACA) to achieve coverage. In Section 6, we investigate how we can improve the BACA by using other search algorithms such as hill climbing (HC) and simulated annealing (SA). In Section 7, we present our simulation results and compare the effectiveness between HC and SA. Finally, in Section 8, we conclude and discuss our future work.

2. Preliminaries and Assumptions

2.1. Terminology

Definition 1

(Sensing Range). The sensing range of a sensor $s_i$ is the area where any occurring event inside that area is sensed by $s_i$.

Definition 2

(Communication Range). The communication range of a sensor $s_i$ is the area where $s_i$ communicates with any other sensor $s_j$ that is within the area.

Definition 3

(Coverage). Coverage involves the placement and coordination of sensor nodes to ensure that the target area or points of interest are accurately monitored. The goal is to maximize the sensing capabilities of the field by considering factors such as sensing range, communication range, energy efficiency, and redundancy.

Definition 4

(k-Coverage). A point in a field of interest is said to be k-covered if every point in this field is covered by at least k sensors. k is called the degree of coverage.

Definition 5

(Nature-inspired Algorithms). Nature-inspired algorithms are optimization algorithms that mimic nature processes to find solutions to complex solutions like the traveling salesman problem (TSP). Some examples of nature-inspired algorithms include particle swarm optimization (PSO), genetic algorithm (GA), and lion optimization (LO).

2.2. Assumptions

In our study of the above problems, we made the following assumptions.

Assumption 1

(Dense and Random Sensor Deployment). The sensors are densely and randomly deployed enough in a 2D WSN to form a connected network that fully covers the sensing field.

Assumption 2

(Sensor Homogeneity). All the sensors are homogeneous in terms of their sensing range, communication range, and energy consumption.

Assumption 3

(Disk Sensing Model). The sensors’ sensing range is modeled by a disk of radius r.

Assumption 4

(Disk Communication Model). The sensors’ communication model is modeled by a disk that is twice the size of the sensing range, represented by 2r.

Assumption 5

(Obstacle-free). The sensing field is obstacle-free, so ants can move directly to their destination without any environmental hindrances.

3. Related Work

In this section, we review existing approaches that utilize nature-inspired algorithms for coverage in wireless sensor networks (WSNs). While ant colony optimization (ACO) and the binary ant colony algorithm (BACA) have gained attention, these methods have not been extensively researched in the context of coverage.

Singh [1] proposed a survey paper that discussed the ant colony optimization method and the lion optimization method as nature-inspired algorithms to achieve coverage in WSNs. Ganzha, Maciaszek, Paprzycki, and Ślezak [2] addressed the ant colony optimization problem to cover an area. Ants chose their path based on probabilistic rules, such as the pheromone trails, and they ensured connectivity among sensors. They introduced penalties if a sensor was not covered by at least one other sensor. Li, Liu, and Cui [3] proposed an improved ant colony algorithm for sensor deployment in real sensor network systems. This paper made modifications to the convergence strategy and the ant state transition rule by proposing an improved ant colony algorithm known as EasiDesign. EasiDesign was proven to be more effective than the traditional ant colony algorithm. Carr and Wang [4] proposed a fast-spanning ant colony optimization for mobile robot cover path planning. Their method involved ants with higher velocities finding destinations or obstacles faster and keeping lower-velocity ants informed by communicating such information via pheromone paths. Additionally, they employed coverage path planning (CPP), where robots would plan a path to cover all the free cells on an occupancy grid map.

Rukundo and Cao [5] presented an advance in image interpolation based on the ant colony algorithm for high-resolution image scaling. Their work focused on leveraging the ant colony algorithm to improve image scaling by interpolating missing pixels. Wang, Zhang, Fan, and Le [6] proposed a self-deployment algorithm for maintaining maximum coverage and connectivity in underwater sensor networks based on ant colony optimization. They carried out a greedy strategy and improved path selection probability by using a pheromone update system. Quasim [7] applied the ant colony optimization (ACO) algorithm in a realistic 3D environment by making modifications to the standard ACO algorithm. By making these adjustments, the algorithm demonstrated improved performance in solving optimization problems in the given environment. Jian [8] proposed a hybrid ant colony algorithm, which combines the strong adaptability of the ant colony algorithm and the high convergence of the genetic algorithm to achieve network coverage and prolong the network lifetime.

Kashef and Nezamabadi-pur [9] introduced a new feature selection algorithm based on binary ant colony optimization. This paper addressed an advanced binary ant colony optimization (ABACO) that treats features as nodes in a graph model, where each feature has two nodes representing selection and deselection. Ants traverse the graph and select nodes using the ant colony algorithm, resulting in a binary vector that represents a possible solution. Tian, Gao, and Ge [10] proposed an improved genetic algorithm and the binary ant colony algorithm to achieve coverage. Their work incorporates enhancements to the genetic algorithm and the binary ant colony algorithm to find the local optimization of the problem of coverage. Fernandos, Rosa, and Ramos [11] proposed a binary ant algorithm (BAA) to solve the problem of dynamic optimization. BAA acts by building pheromone maps over a graph of possible traits representing pseudo-solutions of increasing quality to a specific optimization problem.

Our proposed approach in this paper is different from these related works. Specifically, this work takes into account two search optimization algorithms known as hill climbing (HC) and simulated annealing (SA) and compares the effectiveness between the two with the binary ant colony algorithm. The binary ant colony algorithm first gives us an initial solution, and the HC or SA refines the previous solution, resulting in a near-optimal solution.

4. Traveling Salesman Problem (TSP)

The traveling salesman problem (TSP) is a widely studied problem in computational mathematics that aims to find the shortest route between all the nodes, where each node is visited exactly once and is returned back to the origin node. It is an NP-hard problem, meaning that finding an efficient algorithm to solve it in polynomial time is computationally challenging. However, NP-hard problems may still be solvable using algorithms that have exponential time complexity or through heuristic or approximation methods. In Figure 1, we present an example graph illustrating a simple solution to the TSP problem.

Mathematically, the TSP problem can be represented by the following formula, where n represents the number of nodes:

$$\begin{array}{c}\frac{(n-1)!}{2}\end{array}$$

(1)

For small instances of the problem, the optimal solution can be found by exhaustive search. However, as you increase the number of nodes, the problem size increases, and the time required to find an optimal solution increases dramatically. For instance, at 5 nodes, the number of possible paths is 12, while at 30 nodes, the number of paths increases exponentially to $4\times {10}^{30}.$ Consequently, finding an optimal solution by exhaustively exploring all the possibilities becomes infeasible because of the immense computing cost and time required.

To address the challenges posed by the TSP, one approach is to employ ant colony optimization (ACO). ACO aims to simplify the TSP by emulating the behavior of ants and their pheromone trails. ACO algorithms can efficiently explore the solution space and give us a near-optimal solution to the TSP problem and coverage in WSNs.

5. Ant Colony Optimization

Ant colony optimization (ACO) is a simple mathematical method that draws inspiration from the foraging behavior of ants. The ACO algorithm allows the ants to explore various routes to discover the optimal or near-optimal path.

Within an ant colony, individual ants venture through different paths in search of food to sustain the colony. As they travel through these paths, they leave an odorous trail of pheromones, which allows them to return to the colony. When an ant finds a shorter and more efficient route, it goes back and forth through this route more times, leaving a stronger pheromone path. Eventually, more ants are attracted to this reinforced pheromone path, and the other pheromone paths eventually evaporate since the ants are now traveling along the shorter and more efficient path.

The goal of the ACO is to converge the optimal path through the accumulation and update of pheromones and achieve the optimal path through the appropriate amount of iterations. Figure 2 represents a simple demonstration of the ACO. As the ant follows the shorter path, it traverses the route more frequently, resulting in a stronger pheromone attraction, depicted by the thicker path. Consequently, more ants are inclined to follow this path, enticed by the stronger pheromone scent. This cooperative behavior by the ants guides the algorithm into finding a near-optimal solution through a suitable number of iterations.

The ACO can be simplified into four steps:

• First, a population of virtual ants is created, where each ant and its path represent a possible solution to the problem. Each ant starts at a random point on the field and iteratively constructs a path based on certain probabilistic rules. These probabilistic rules include the intensity of the pheromone scents and heuristic information, like proximity, which is the inverse of the distance between the nodes. An example of how an ant uses the probability rules is shown in Figure 3 from [5]. As shown in the figure, the ant chooses the next node to move based on the functions of the pheromone count ${\tau }_{i,j}$ and the heuristic values ${\eta }_{i,j}$.
• At each step, an ant selects the next node based on the combination of the pheromone trail intensity and the heuristic information, like the distance or cost associated with moving to that node. This equation can be represented by the following:

  $$P_{i,j}\left(t\right)=\frac{{\tau }_{i,j}^{\alpha }\ast {\eta }_{i,j}^{\beta }}{{\sum }_{mϵallowed}{\tau }_{i,m}^{\alpha }\ast {\eta }_{i,m}^{\beta }}$$

  (2)

  where $P_{i,j}$ represents the probability of moving from node i to node j, ${\tau }_{i,j}\ast {\eta }_{i,j}$ represents the desire to move from node i to node j, ${\tau }_{i,j}$ represents the number of pheromones between nodes i and j, ${\eta }_{i,j}$ represents the proximity between nodes i and j, and ${\sum }_{mϵallowed}{\tau }_{i,m}\ast {\eta }_{i,m}$ represents the sum of the desires of an ant to move from node i to all vertices available for the ant. Altering $\alpha$ and $\beta$ affects the probability of choice. It represents the power to which either proximity or pheromone is raised. For instance, a higher value of $\beta$ means that the algorithm places more importance on the heuristic information, and a higher value for $\alpha$ means that there is more importance on the pheromone information.
• In each iteration, a number of ants are going to use the probability rules to construct their initial paths. Then, the pheromones are going to be updated after each iteration. The pheromone update aims to reinforce the paths taken by the ants that lead to better solutions while evaporating the weaker pheromone trails to encourage exploration.
• This process is repeated until a termination criterion is met. The termination criteria can be a predetermined number of iterations, reaching a specific threshold for the solutions or a specific time limit. Once the termination criteria are met, the algorithm concludes.

Binary Ant Colony Algorithm (BACA)

The binary ant colony algorithm (BACA) is a variant of ant colony optimization. BACA denotes the parameters directly with binary coding; thus, it can take up less storage space and reduce the complexity of the algorithm. Compared with the traditional ant colony algorithm, the biggest difference is the ant’s path selection. The states of the BACA are either 1 or 0, indicating the activation or sleep of a sensor node, respectively. This reduces the complexity of the algorithm and allows for more efficiency. Similarly, in the traditional algorithm, artificial ants are used to explore the search space of a given optimization problem.

The BACA consists of five phases:

In the first phase, we initialize parameters such as the number of ants, the number of iterations, and the pheromone trails on the binary string positions. In the second phase, the ants construct a solution by making binary decisions based on the pheromone trails and the heuristic information. Each virtual ant constructs a solution by flipping the bits in a binary string representation, where each bit corresponds to an activation status of a sensor node. The ants determine the movement direction according to the information quantity of each path and the movable probability. We can rewrite Equation (2) to look like the following [6]:

$$P_{i,j}^m\left(t\right)=\left\{\begin{array}{c}\frac{{\tau }_{i,j}^{\alpha }\ast {\eta }_{i,j}^{\beta }}{{\sum }_{mϵallowed}{\tau }_{i,m}^{\alpha }{\eta }_{i,m}^{\beta }}ifjϵallowed\hfill \\ \\ 0otherwise\hfill \end{array}\right.$$

(3)

where $P_{i,j}$ represents the probability of moving from node i to node j, ${\tau }_{i,j}\ast {\eta }_{i,j}$ represents the desire to move from node i to node j, ${\tau }_{i,j}$ represents the number of pheromones between nodes i and j, ${\eta }_{i,j}$ represents the proximity between nodes i and j, and ${\sum }_{mϵallowed}{\tau }_{i,m}\ast {\eta }_{i,m}$ represents the sum of the desires of an ant to move from node i to all vertices available for the ant.

Additionally, in the process of movement, the ant leaves pheromones trails based on the following equation:

$$\begin{array}{c}\Delta \tau =\frac{Q}{L_k}(i,j)ϵkpath\end{array}$$

(4)

where $\Delta \tau$ represents the number of pheromones that are deposited, Q represents a constant, and $L_k$ represents the length of the kth ant tour.

As the ants traverse through this process, it creates a configuration of sensor node activations. Each configuration represents a potential solution to the coverage problem, wherein the selected set of activation nodes fulfills the desired coverage requirements [10]. Figure 4 provides a visual representation of the traversal path of an ant starting at a random point in the field represented by the root and making binary decisions at each step. As an ant enters the field on the left side and stops on the other end, it creates a binary string as it passes through the nodes. Notably, each ant, as it traverses through the field, generates a unique binary string, encapsulating a potential solution to the problem. In Figure 5, we observe a random distribution of sensor nodes in a field depicted by the figure on the left. As the ants traverse through these nodes, their decision-making process adheres to the probabilistic principles dictated by pheromone levels and heuristic information. This interplay of factors guides the ants to form a potential solution, illustrated by the figure on the right. Nodes with the red outline indicate that the ants chose those nodes to be in sleep mode.

In the third phase, we evaluate the quality of fitness of each solution based on a fitness function. The fitness function is crucial for evaluating the quality or performance of potential solutions that are generated by the algorithm. The fitness function generally considers the coverage quality, energy consumption, sensing overlap, network lifetime, and deployment cost.

$$\begin{array}{c}\begin{array}{c}\hfill Fitness\left(S\right)=w_1\ast Coverage\left(S\right)-w_2\ast Energy\left(S\right)\\ \hfill -w_3\ast Overlap\left(S\right)+w_4\ast Lifetime\left(S\right)-w_5\ast Cost\left(S\right)\end{array}\end{array}$$

(5)

Weights $w_1,w_2,w_3,w_4,$ and $w_5$ represent the relative importance of each parameter in the fitness evaluation. These weights can be adjusted to prioritize certain objectives over others, depending on the specific requirements of the WSN. Using the fitness function, the solutions are ranked in the order of the fittest solutions, or best solutions. The best solution is represented by that with the highest fitness value. After each iteration, the pheromone trails need to be updated based on the fitness of the ant’s solution. The pheromone update process consists of two steps. The first step is called the evaporation phase, in which the pheromone trails evaporate according to the following rule based on the works by Kong in [12,13]:

$$\begin{array}{c}{\tau }_{i,j}(t+1)\leftarrow \left(\rho \right){\tau }_{i,j}\left(t\right)\end{array}$$

(6)

where $\rho ϵ[0,1]$ is the evaporation parameter. t represents the iteration count, and t + 1 represents the next iteration. For the pheromone count in the next iteration, the current iteration pheromone count is multiplied by the evaporation coefficient. In the second step, the pheromone trails are updated to reinforce the paths associated with better solutions. The BACA keeps track of the current iteration’s best solution, denoted as $S^{ib}$, and the global best solution, denoted as $S^{gb}$, enabling continuous updates to the best solution and eventual return after the algorithm concludes. The second step is represented by

$$\begin{array}{c}{\tau }_{i,j}(t+1)\leftarrow {\tau }_{i,j}(t+1)+\rho \sum _{k=1}^m\Delta \tau \end{array}$$

(7)

where ${\sum }_{k=1}^m\Delta \tau$ is a parameter that represents the sum of the pheromone paths.

The update process involves the evaporation of previous pheromone trails and the addition of new pheromone paths, reinforcing better solutions. By using the fitness function and updating the pheromones after each iteration, the ants are exploring different combinations of activated sensor nodes that eventually result in a near-optimal solution.

In the fourth phase, after we have completed a specific number of iterations, the fitness function is used to find the solution with the highest fitness value. We initialize this as our current solution for the hill climbing (HC) and simulated annealing (SA) algorithms. We then use HC and SA to further explore the solution space and compare the effectiveness of coverage between the two. The process of these algorithms is further explained in Section 6. Finally, in the fifth phase, we apply termination criteria. The algorithm terminates once the established number of iterations or a certain amount of time is reached.

The structure of the BACA combined with SA can be represented by the flowchart shown in Figure 6.

The research methodology commences with the initialization of the parameters, establishing a framework for subsequent algorithm processes. The BACA is then deployed to construct an initial solution, where the foraging behavior of ants is emulated to strategically activate sensors. The fitness of this initial configuration is evaluated, and the optimal solution constructed by the BACA is used as the initial solution for the HC or SA algorithm. Should the BACA-HC or BACA-SA convergence indicate the attainment of an optimal solution, the system will end. Otherwise, a new set of ants is initialized, and the process is repeated. Additionally, the pseudo-code of the binary ant colony algorithm can be represented in Algorithm 1.

Algorithm 1: Binary Ant Colony Algorithm

6. Local Search Algorithms

To find the coverage problem in a WSN, using only the BACA has several disadvantages. For example, the exploration capability may be limited when dealing with complex or high-search spaces. Additionally, the algorithm relies on pheromone trails to guide the search, and if the initial trials are not well-informed, the BACA may struggle to find the optimal or near-optimal solution. As a result, pairing the BACA with a local search optimization algorithm is a more feasible solution. This also offers several advantages, such as an enhanced exploration of the search space, enhanced exploitation, and a refinement of solutions. This combination improves search efficiency, solution quality, and convergence speed, making it a more robust optimization solution for solving the coverage problem. Therefore, we explore two different local search algorithms that can be used to enhance the initial solution created by the BACA, known as hill climbing and simulated annealing.

6.1. Hill Climbing

Hill climbing is a straightforward local search algorithm that incrementally enhances a solution to a problem by making small iterative adjustments. The process begins with an initial solution, and then, it continually updates the solution to a neighboring one that demonstrates improvement over the current solution. This iterative refinement persists until no neighboring solution surpasses the current one, signifying the algorithm has reached a local optimum.

The following steps are involved in hill climbing:

• Initialize a solution. This initial solution is given by the BACA.
• Repeat the following steps until no better solution is found:
  • Generating a neighboring solution.
  • If the neighboring solution is better than the current solution, then update the current solution to the neighboring solution.

Algorithm 2 illustrates the hill climbing algorithm with the BACA as pseudo-code.

Algorithm 2: Binary Ant Colony Algorithm with Hill Climbing

A neighboring solution is a solution that is one small change away from the current solution. The way that neighboring solutions are generated depends on the problem being solved. For example, in the traveling salesman problem, a neighboring solution can be generated by swapping two cities in the tour.

Hill climbing employs various stopping criteria, such as a fixed number of iterations, a specified level of convergence, or a certain value of the objective function. Once any of these criteria are met, the algorithm concludes, providing the best solution it has found.

Hill climbing is favored for its simplicity and ease of implementation. Additionally, it exhibits relatively efficient performance by examining only a limited number of neighboring solutions during each iteration. However, one potential drawback of hill climbing is its vulnerability to becoming trapped in local optima. This occurs when the algorithm explores only neighboring solutions that outperform the current one. In situations where the current solution is already a local optimum, the algorithm may not be able to discover a better solution, hindering its ability to reach the global optimum.

6.2. Simulated Annealing

Simulated annealing is a powerful meta-heuristic optimization algorithm that draws inspiration from the annealing process used in metallurgy. In metallurgy, annealing involves heating a material to a high temperature and gradually cooling it down, thereby enhancing its properties. Similarly, simulated annealing utilizes this concept by iteratively exploring solution spaces to find optimal solutions. By mimicking the atom rearrangement in the cooling process, simulated annealing aims to converge toward a more orderly and improved state for the given problem.

Simulated annealing operates on a similar principle. The algorithm initiates the best solution constructed by the BACA to the problem and proceeds iteratively to enhance it. By introducing small modifications to the solution, the algorithm continuously refines its quality. Even if these alterations lead to a potentially worse solution, simulated annealing accepts them with a decreasing probability as the algorithm advances. This unique characteristic enables the algorithm to overcome local minima and thoroughly explore the solution space, promoting the discovery of more optimal solutions.

The following are the steps involved in simulated annealing:

• Initialize with a solution from BACA
• Repeat the following steps until a stopping criterion is met:
  • Make small changes to the solution.
  • Calculate the change in the objective function.
  • Accept the change with a probability that depends on the change in the objective function and the temperature.
  • Decrease the temperature.

Algorithm 3 illustrates the simulated annealing algorithm with the BACA as pseudo-code.

Algorithm 3: Binary Ant Colony Algorithm with Simulated Annealing

The acceptance probability uses an exponential function of the coverage difference and temperature. When the temperature is high early on, worse solutions have a decent chance of being accepted. As it decreases over iterations, worse solutions are less likely to be accepted. This allows thorough exploration early on, moving toward exploitation as the number of iterations increases. The temperature schedule and initial value require tuning for good performance. Temperature governs the likelihood of accepting worse solutions during the algorithm’s progression. At the outset, the temperature is set high, favoring the acceptance of inferior solutions. As the algorithm advances, the temperature gradually decreases, leading to a reduced probability of accepting worse solutions.

The stopping criterion in simulated annealing can be defined by a fixed number of iterations, a specific level of convergence, or a particular value of the objective function. Once the stopping criterion is satisfied, the algorithm concludes, returning the best solution discovered.

7. Performance Evaluation

7.1. Simulation Setup

In this section, we present the experimental results obtained by comparing two different simulations: binary ant colony algorithm with hill climbing (BACA-HC) and binary ant colony algorithm with simulated annealing (BACA-SA). The experiments were conducted to evaluate the performance of these algorithms in solving the sensor placement problem. Specifically, the two algorithms were systemically tested to discern their relative performance and determine which one demonstrated superior results in the problem of optimizing sensor placement and obtaining an optimal coverage of a 2D field. The implementation and evaluation of these algorithms were conducted using the Python programming language.

We conducted a series of tests with varying parameters to evaluate the performance of our system. Some parameters were kept constant across all tests. Specifically, we set the number of iterations for the BACA (binary ant colony algorithm), SA (simulated annealing), and hill climbing algorithms at 100 iterations each. This decision aimed to strike a balance between computational efficiency and thorough exploration of solution spaces. Furthermore, a consistent ant population of 100 ants was employed for all experiments, contributing to the reliability and consistency of our comparative analyses. The last parameter that was kept constant was the sensing range. A standardized sensing range of 4 units was maintained for the sensors throughout all tests. This consistency served as a foundational element in our experimental design, providing a constant baseline for comparison.

In order to explore different scenarios and assess the system under various conditions, we strategically adjusted other parameters across 3 distinct experiments, each representing a unique combination of these parameters. The parameters that were modified include the sensing area and the number of sensors deployed. These modifications allowed us to explore different search spaces and enabled a thorough examination of our system’s performance under different spatial and sensor density conditions. The three experiments can be described by the following:

Experiment 1: We conducted experiments in sensing fields with an area of 300 (20 units by 15 units) and a deployment of 12 sensors.

Experiment 2: For a larger sensing field with an area of 600 (30 units by 20 units), we deployed 22 sensors.

Experiment 3: To further investigate the system’s performance in larger environments, we conducted experiments in a sensing field of an area of 1000 (40 units by 25 units) with a total of 40 sensors.

To enhance the statistical reliability of our findings, each experiment underwent 100 repetitions. This approach provided a comprehensive view of algorithmic performance, contributing to a more thorough assessment of our results. The coverage percentages obtained for each iteration of the simulations were recorded and analyzed. The results are presented in the following figures and tables.

7.2. Simulation Results

For each hill climbing experiment, the simulation was executed for 100 iterations, each iteration comprising two phases: BACA for global exploration and hill climbing for local refinement. Throughout these iterations, the coverage of the monitored area by the deployed sensors was systematically evaluated. This coverage metric, expressed as a percentage, reflected the proportion of the total area effectively covered by the strategically placed sensors. The outcomes for each iteration were recorded in both string and array formats, offering a detailed depiction of the optimization process.

Iteration-wise coverage values were dynamically appended to the log string. This concise yet informative representation captured the evolving success of the optimization process. The coverage percentages for each iteration were systematically stored in an array. This structured data format provided a quantitative record of the simulation outcomes and facilitated statistical analysis.

For simulated annealing, the algorithm was employed to optimize the sensor placement for coverage maximization in a predefined area. The study conducted 100 iterations of the algorithm, each iteration involving the exploration of the solution space and adjustments to the sensor positions. The coverage results for each iteration were logged, providing a comprehensive understanding of the algorithm’s convergence behavior. The coverage was expressed as a percentage of the total area covered by the sensors.

During the 100 iterations of each, instances where the coverage reached 100 percent were recorded. The frequency of achieving complete coverage provided insights into the algorithm’s ability to find optimal solutions.

The convergence plots, generated through the visualization process, vividly illustrate the progressive enhancement in coverage over iterations. These plots serve as visual proof of the algorithm’s efficacy as it ascends toward optimal solutions.

In summary, the iterative optimization process, combining the BACA for global search and localized hill climbing or simulated annealing for refinement, yields promising results.

The results from the three experiments demonstrate that the BACA-HC approach outperformed the BACA-SA in achieving better field coverage.

In Experiment 1, the BACA-HC achieved an average coverage of 97.19%, while the BACA-SA had an average coverage of 86.04%. Figure 7 visually depicts the superior coverage of BACA-HC, and it highlights that the results produced by BACA-HC were closer in value to those by BACA-SA.

Moving on to Experiment 2, BACA-HC achieved an average coverage of 93.95%, surpassing BACA-SA’s average coverage of 85.36%. Figure 8 provides a clear comparison of the percent coverage for both algorithms in Experiment 2.

In Experiment 3, the trend continued, with BACA-HC maintaining its superiority, achieving an average coverage of 94.17%, while BACA-SA managed an average coverage of 87.93%. Figure 9 illustrates the percent coverage for both algorithms in Experiment 3.

The amalgamation of ant colony optimization and hill climbing strikes a balance between exploration and exploitation, offering a reliable and effective solution for the intricate sensor placement problem. This dual-strategy approach showcases the adaptability of the algorithms in navigating the optimization landscape, consistently converging toward high-quality solutions.

The consistent outperformance of BACA-HC across all three experiments suggests its robustness and effectiveness in ensuring better field coverage compared to BACA-SA.

7.3. Discussion

The experimental results present a comprehensive evaluation of two distinct simulations: binary ant colony algorithm with simulated annealing (BACA-SA) and binary ant colony algorithm with hill climbing (BACA-HC). Our primary objective was to assess the performance of these algorithms in solving the sensor placement problem. To ensure statistical significance, we conducted 100 repetitions of the experiments for each algorithm.

Initially, we established a set of common parameters for the BACA, SA, and hill climbing algorithms, with 100 iterations and 100 ants being consistent across all tests. We maintained a sensing range of four units for the sensors in all experiments. However, we introduced variability in other parameters to accommodate different scenarios, which led to three distinct experiments conducted in sensing fields of varying sizes: 300, 600, and 1000 units.

Surprisingly, the results revealed a remarkable trend that contradicted our initial assumption. The BACA-HC approach consistently outperformed the BACA-SA in achieving better field coverage across all three experiments.

The consistent outperformance of BACA-HC over BACA-SA, as showcased in our experimental results, has significant implications for the efficacy of these algorithms in solving the sensor placement problem. The incorporation of hill climbing within the binary ant colony optimization process appears to enhance the algorithm’s capability to explore the search space and discover better sensor configurations, leading to superior coverage results.

While the initial assumption posited BACA-SA as the preferred approach, the experimental evidence convincingly supports the advantage of BACA-HC in terms of achieving better field coverage. This unexpected outcome warrants a reevaluation of our initial assumptions and provides valuable insights for future research in the field of sensor placement optimization. Further investigations into the specific factors contributing to the performance disparities between the two algorithms can pave the way for optimizing both BACA-HC and BACA-SA in different applications and scenarios.

8. Conclusions

8.1. Summary

In this paper, a new approach to achieve coverage in a WSN using the binary ant colony algorithm and the simulated annealing algorithm is proposed. Initially, the BACA constructs a solution by leveraging probabilistic rules, including pheromone amount and heuristic information, to navigate through nodes effectively. As the ants traverse the network, they generate binary strings, each representing a possible solution to the problem of coverage. The pheromone trails are continuously updated after each iteration to promote the stronger pheromone paths while simultaneously evaporating the weaker ones. Subsequently, a fitness function was applied to find the best solution created by the BACA, which serves as an initial solution for the HC and SA algorithms. HC and SA then enhanced the solutions of the BACA by making small modifications, ultimately converging to a near-optimal solution. Through extensive simulations, we compared the effectiveness between HC and SA and observed that contrary to our initial theory, the HC consistently delivered the most optimal solution, ensuring nearly complete coverage of a field of interest.

8.2. Future Directions

While this paper presents a novel approach combining the BACA and SA for optimizing coverage and energy efficiency in WSNs, there remain several promising directions for future research in this area. These potential extensions and improvements can further enhance the performance and applicability of the proposed approach:

• Three-dimensional coverage optimization: The current approach focuses on optimizing coverage in a two-dimensional (2D) field. Extending the research to three-dimensional environments will be valuable, as many real-world scenarios, such as monitoring buildings or underground structures, require WSNs to operate in 3D spaces. Investigating how the BACA and HC/SA can be adapted or combined to tackle 3D coverage challenges will be a significant step forward.
• Dynamic deployment and mobility of nodes: In practical WSN deployments, sensor nodes may experience mobility or need to be dynamically deployed to adapt to changing environmental conditions. Exploring how the proposed approach can be extended to handle dynamic node deployment and mobility scenarios is crucial for achieving robust and adaptable WSNs.
• Heterogeneous sensor nodes: In many WSNs, sensor nodes may have varying capabilities and energy constraints. Researching how the proposed approach can be adapted to handle heterogeneous nodes will cater to diverse deployment scenarios and enable more versatile applications.