1 Introduction

Initial deployments of wireless sensor networks (WSN) were completed by the military, for reconnaissance and surveillance [1]. Examples of other possible applications of WSN’s are: forest fire prevention, volcano eruption study [8], health data monitoring [9], civil engineering [7] and others.

The energy for collecting data and its transmission comes from the battery of a node. One of the WSN nodes has special role. It is a High Energy Communication Node (HECN), which collects data from across the network and transmits it to the “main computer” to be processed. The sensors transmit their data to the HECN, either directly or via hops, using closest sensors as communication relays. The WSN can have large numbers of nodes and the problem can be very complex. Thus, one of the best choice is to apply some metaheuristic method.

The problem of designing a WSN is multi-objective, with two objective functions. These are (1) minimize the energy consumption of the nodes in the network, and (2) minimize the number of nodes. The full coverage of the network and connectivity are considered as constraints. In our work we propose a multi-objective ant colony optimization (ACO).

In the past, [15] solved an instance of the WSN layout using a multi-objective genetic algorithm. In their formulation, a fixed number of sensors had to be placed in order to maximize the coverage. However, in some applications the most important is the network energy. In this context, in [4] an ACO algorithm was proposed, but it is applicable to a special case when the sensors are antennas and the work concerns only energy minimization. In [20] an evolutionary algorithm was applied to this variant of the problem. In [6] several evolutionary algorithms to solve the problem were proposed. Finally, in [5] a genetic algorithm, which achieves similar solutions as the algorithms in [6] was studied, but tested only on small test problems.

In this paper we study the influence of the number of ants to the algorithm performance and quality of the achieved solutions. The computational resources, which the algorithm needs, are not negligible. The computational resources depends on the size of the solved problem and on the number of ants. Our aim in this work is to find a minimal number of ants which allow the algorithm to find good solution. Moreover, the recently proposed approach InterCriteria Analisys (ICrA) is applied for further investigation of the influence of the ants number on ACO algorithm.

ICrA, proposed by [13], is a recently developed approach for evaluation of multiple objects against multiple criteria and thus discovering existing correlations between the criteria themselves. It is based on the apparatus of the index matrices (IMs) [10], and the intuitionistic fuzzy sets [11] and can be applied to decision making in different areas of knowledge [16,17,18,19].

2 Theoretical Background

2.1 Multi-objective ACO for WSN Layout

We apply multi-objective ACO to solve the WSN problem. The ACO algorithm uses a colony of artificial ants that behave as cooperating agents. With the help of the pheromone and the heuristic information they try to construct better solutions and to find the optimal ones. The pheromone corresponds to the global memory of the ants and the heuristic information is a some preliminary knowledge of the problem. The problem is represented by a graph and the solution is represented by a path in the graph or by tree in the graph. Ants start from random nodes and construct feasible solutions. When all ants construct their solution the pheromone is updated. The new, added, pheromone depends to the quality of the solution. The elements of the graph, which belong to better solutions will receive more pheromone and will be more desirable in the next iteration.

In our implementation, we use the MAX-MIN Ant System (MMAS) which is one of the most successful ant approaches originally presented in [2].

In our case, the graph of the problem is represented by a square grid. The nodes of the graph are enumerated. The ants will deposit their pheromone on the nodes of the grid. We will deposit the sensors on the nodes of the grid too. The solution is represented by tree. An ant starts to create a solution starting from random node, which communicates with the HECN. Construction of the heuristic information is a crucial point in the ant algorithms. Our heuristic information is a product of three values (Eq. 1).

$$\begin{aligned} \eta _{ij}(t)= s_{ij}l_{ij}(1-b_{ij}), \end{aligned}$$
(1)

where \(s_{ij}\) is the number of the new points (nodes of the graph) which the new sensor will cover, and which are not covered by other sensors, and

$$\begin{aligned} l_{ij}=\left\{ \begin{array}{ll} 1 &{} \text{ if } \text{ communication } \text{ exists }\,; \\[4pt] 0 &{} \text{ if } \text{ there } \text{ is } \text{ not } \text{ communication }\,. \end{array} \right. \end{aligned}$$
(2)

Here, \(b_{ij}\) is the solution matrix and the matrix element \(b_{ij}=1\) when there is sensor on this position otherwise \(b_{ij}=0\). With \(s_{ij}\) we try to increase the number of points covered by one sensor and thus to decrease the number of sensors we need. With \(l_{ij}\) we guarantee that all sensors will be connected. With \(b_{ij}\) we guarantee that maximum one sensor will be mapped on the same point. The search stops when transition probability \(p_{ij}=0\) for all values of i and j. It means that there are no more free positions, or that all area is fully covered.

At the end of every iteration the quantity of the pheromone is updated. The pheromone trail update rule is given by:

$$\begin{aligned} \tau _{ij}\leftarrow \rho \tau _{ij}+\varDelta \tau _{ij}, \end{aligned}$$
(3)
$$\varDelta \tau _{ij} =\left\{ \begin{array}{ll} 1/F(k) &{} \text {if }\ (i,j)\in \{\text {non-dominated solution constructed by ant } k\}, \\ 0 &{} \text {otherwise}\,. \end{array} \right. $$

We decrease the pheromone with a parameter \(\rho \in [0,1]\). This parameter models evaporation in the nature and decreases the influence of old information on the search process. After that, we add the new pheromone, which is proportional to the value of the fitness function. The fitness function is constructed as follows:

$$\begin{aligned} F(k)=\frac{f_1(k)}{\max _i f_1(i)}+\frac{f_2(k)}{\max _i f_2(i)} \end{aligned}$$
(4)

Where \(f_1(k)\) is the number of sensors proposed by the k-th ant and \(f_2(k)\) is the energy of the solution of the k-th ant. These are also the objective functions of the WSN layout problem. We normalize the values of two objective functions with their maximal achieved values from the first iteration.

2.2 InterCriteria Analysis

InterCriteria analysis, based on the apparatuses of Index Matrices (IM) [10] and Intuitionistic Fuzzy Sets (IFS) [12], is given in details in [13].

In order to find the agreement between two criteria, the vectors of all internal comparisons for each criterion are constructed, which elements fulfill one of the three relations R,  \(\overline{R}\) and \(\tilde{R}.\) The nature of the relations is chosen such that for a fixed criterion C and any ordered pair \(\langle x,y\rangle \in C^*(O)\):

$$\langle x,y\rangle \in R \Leftrightarrow \langle y,x \rangle \in \overline{R} , \langle x,y\rangle \in \tilde{R} \Leftrightarrow \langle x,y\rangle \notin (R\cup \overline{R}), R \cup \overline{R} \cup \tilde{R} = C^*(O).$$

When comparing two criteria the degree of “agreement” (\(\mu _{C,C^{\prime }}\)) is usually determined as the number of matching components of the respective vectors. The degree of “disagreement” (\(\nu _{C,C^{\prime }}\)) is usually the number of components of opposing signs in the two vectors. From the way of computation it is obvious that \(\mu _{C,C^{\prime }}= \mu _{C^{\prime },C}\) and \(\nu _{C,C^{\prime }}= \nu _{C^{\prime },C}.\) Moreover, \(\langle \mu _{C,C^{\prime }},\nu _{C,C^{\prime }}\rangle \) is an Intuitionistic Fuzzy Pair.

There may be some pairs \(\langle \mu _{C,C^{\prime }},\nu _{C,C^{\prime }}\rangle \), for which the sum \(\mu _{C,C^{\prime }}+\nu _{C,C^{\prime }}\) is less than 1. The difference

$$\begin{aligned} \pi _{C,C^{\prime }} = 1 -\mu _{C,C^{\prime }} -\nu _{C,C^{\prime }} \end{aligned}$$
(5)

is considered as a degree of “uncertainty”.

3 Experimental Results

3.1 ACO Application on Various Sizes of Problem

We have implemented software, which realizes our ant algorithm. Our software can solve the problem at any rectangular area, the communication and the coverage radius can be different and can have any positive value. We can have regions in the area. The program was written in C language, and the tests were run on computer with an Intel Pentium 2.8 GHz processor. In our tests we use an example where the area is square. The coverage and communication radii cover 30 points. The HECN is fixed in the centre of the area. For the tests we have used areas with three sizes: \(350\times 350\) points, \(500\times 500\) points, and \(700\times 700\) points.

In our previous work [3], we showed that our ant algorithm outperforms the existing algorithms for this problem. There, after several runs of the algorithm we were able to specify the most appropriate values of its parameters: \(\alpha =\beta = 1\), \(\rho = 0.5\), \(\tau _0=0.5\). We study the influence of the number of ants on the quality of the solutions. We fixed the number of the iterations to be 60 (about 3 h per ant) and the number of ants to have following values \(\{1, 2 ,3, 4, 5, 6, 7, 8, 9, 10 \}\).

Table 1. Approximate Pareto fronts, example \(350\times 350\)
Full size table
Table 2. Approximate Pareto fronts, example \(500\times 500\)
Full size table
Table 3. Approximate Pareto fronts, example \(700\times 700\)
Full size table

We run our ACO algorithm 30 times for each number of ants. We extract the Pareto front from the solutions of these 30 runs. In Tables 1, 2, and 3 we show the achieved non dominated solutions (approximate Pareto fronts) for case \(350\times 350\), \(500\times 500\), and \(700\times 700\), respectively.

The left column represents the number of sensors and in other columns we present the energy corresponding to this number of sensors and the number of ants. Analyzing the Table 1 (case \(350\times 350\)) we observe that the best algorithm performance in the case \(350\times 350\) is achieved by 7 ants, more ants leads to more computational time. From Table 2 (case \(500\times 500\)) we observe that the approximate Pareto front achieved by 6 ants dominates others. Analyzing the Table 3 (case \(700\times 700\)) we observe that the approximate Pareto front achieved by 6 ants again dominates others. In all discussed cases the approximate Pareto fronts achieved by 6 and 7 ants outperform others. Thus it is the best number of ants for our sensor layout problem.

3.2 ICrA Results

In case of size \(350\times 350\), in order to apply the ICrA the IM based on the results presented in Table 1 is constructed. The cross-platform software for ICrA approach, ICrAData, is used [14]. After the application of ICrA the following IM of values of degrees of “agreement” \(\mu _{C,C^{\prime }}\) are obtained (Table 4). In the table, as well as in the Tables 5 and 6, in bold are the estimations that show high correlation between the considered ACO algorithms.

Table 4. Obtained degrees of “agreement” \(\mu _{C,C^{\prime }}\) - problem size \(350\times 350\)
Full size table

In case of size \(500\times 500\) again IM based on the results presented in Table 2 is constructed. The obtained degrees of “agreement” are as presented in Table 5.

Table 5. Obtained degrees of “agreement" \(\mu _{C,C^{\prime }}\) – problem size \(500\times 500\)
Full size table

In case of size \(700\times 700\) the IM based on the results presented in Table 3 is constructed. The obtained degrees of “agreement” are as presented in Table 6.

Table 6. Obtained degrees of “agreement” \(\mu _{C,C^{\prime }}\) – problem size \(700\times 700\)
Full size table

Based on the ICrA outcomes it is shown that the ACO algorithms with very close number of ants (e.g. \(ACO_1\) and \(ACO_2\), \(ACO_3\) and \(ACO_4\) or \(ACO_7\) and \(ACO_8\)) perform in similar way. The high correlation between such pairs is preserved regardless the problem size. Such relation is obvious. According to the results in Table 4 (case \(350\times 350\)) very high correlation is observed for the \(ACO_9\) and \(ACO_1\), \(ACO_2\), \(ACO_3\). These relations are not observed in the other two cases. In case of problem size \(350\times 350\) the existing many very high correlations are explained with the fact the most of the considered ACO algorithms can solve the problem with good solution quality. Whereas, in the case of size \(500\times 500\) or \(700\times 700\) only few ACO algorithms perform very well. So, if we considered results in case of larger problem sizes, the ICrA results show that the number of ans has the significant influence on the obtained results.

4 Conclusion

In this paper we have studied the influence of the number of ants on the performance of the ACO algorithm, applied to the wireless sensor network. Smaller number of ants leads to the shorter running time and minimizes memory use, which is important for complex/large cases. We varied the number of ants, while fixing the number of iterations. Furthermore, we included the concept of an Extended front, as an additional tool to compare approximate Pareto fronts that do not dominate each other. The best approximate Pareto front and the best performance were achieved when the number of ants was equal to 6 in the cases \(700\times 700\) and \(500\times 500\), and 7 in the case \(350\times 350\). The results are analysed based on ICrA, too. The analysis confirms considerable influence of the ants number on the quality of the decision, especially in the case of bigger problem sizes.