Design of Randomly Deployed Heterogeneous Wireless Sensor Networks by Algorithms Based on Swarm Intelligence

Abstract

This paper reports the design of a randomly deployed heterogeneous wireless sensor network (HWSN) with two types of nodes: a powerful node and an ordinary node. Powerful nodes, such as Cluster Heads (CHs), communicate directly to the data sink of the network, and ordinary nodes sense the desired information and transmit the processed data to powerful nodes. The heterogeneity of HWSNs improves the networks lifetime and coverage. This paper focuses on the design of a random network among HWSNs. In the design of a random HWSN, this paper uses algorithms based on the binary-valued versions of swarm intelligence, such as Particle Swarm Optimization (PSO), Artificial Bee Colony (ABC), and Ant Colony Optimization (ACO). The design is then considered to be an optimization problem of how many powerful and ordinary nodes will combine to minimize the network cost, while guaranteeing a desired coverage during a given period. Simulation results show the performance of each algorithm for solving the defined optimization problem.

1. Introduction

A heterogeneous wireless sensor network (HWSN) consists of more than two types of devices (or sensor nodes) to improve the network's lifetime, coverage, and scalability. The HWSNs lifetime can be effectively prolonged [1], especially for cases when powerful nodes that play a role as Cluster Heads (CHs) exist in a relatively large HWSN.

This paper focuses on the effective design of WSNs constructed by randomly deploying sensors, thus solving the optimization problem of how many powerful and ordinary nodes will combine to minimize the network cost while guaranteeing a desired coverage during a given period. Almost all of the sensors used in randomly deployed WSNs are constrained by their energy use because they have an embedded battery. Therefore, in studies on randomly deployed WSNs, the issue of how to effectively establish and efficiently manage the WSNs is very important and has been actively studied [2–13]. In particular, the researches of approaching this problem with metaheuristics have increased in recent years [2, 3, 5–14].

In previous research [4], the authors had simplified this design problem by assuming that only ordinary nodes sense the area to solve the problem through the mathematical analysis. Our previous paper [7] designed the HWSN with nodes and CHs that are able to sense information by defining the constrained integer optimization problem, converting it to the unconstrained problem and solving this problem using the discrete binary version of the PSO algorithm known as the Discrete PSO (DPSO) algorithm [15]. In this study, we solve this optimization problem with more realistic and efficient approaches at the expense of an increase in complexity by applying other metaheuristic methods based on swarm intelligence, such as binary Artificial Bee Colony (binABC) [16] and binary Ant Colony Optimization ( ${\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ ), which are the binary-valued versions corresponding to their original algorithms as well as the DPSO algorithm (hereafter renamed as binary PSO (binPSO)). Notably, the ${\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ is first proposed in this paper. This algorithm is implemented by combining the binary concepts from the binPSO and the binABC with the ACO algorithm for continuous domains, ${\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ [17]. The details of the ${\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ are introduced in Section 3.3.

The remainder of this paper is organized as follows. In Section 2, we define the sensor system model and provide its coverage analysis. This section also defines the integer optimization problem with some constraints for the design of HWSN and briefly introduces Deb's method that converts a constrained optimization problem to an unconstrained one and converts the defined problem to the unconstrained integer optimization as in [7]. In Section 3, the binary-valued optimization algorithms based on swarm intelligence are introduced. In Section 4, we show the comparative results between algorithms obtained from the simulation, designing several HWSNs. We then conclude this paper in Section 5.

2. Randomly Deployed Heterogeneous WSN Design

2.1. System Model

The proposed heterogeneous wireless sensor network (HWSN) is constructed by uniformly and randomly deploying M powerful nodes (hereafter CHs) and N ordinary nodes (hereafter nodes) over a large area $\mathbb{R}$ with a large size $‖\mathbb{R}‖$ because sensor clustering is usually used in relatively large WSNs. In the HWSN, the CHs communicate directly with the data sink of the network, and the nodes sense the desired information and transmit the processed data to powerful nodes. After each node collects the desired information, it directly transmits the data to its closest CH every T hours (i.e., single-hop network). CHs then forward all data received to the sink of the HWSN. At this time, all CHs and nodes consume energy for the transmission of a data packet, and this is modified as follows [1]:

$$\begin{array}{cc}& e\left(d\right)=k{d}^{\gamma }+c,\end{array}$$

(1)

where k is the loss coefficient and c represents the overhead energy for a packet transmission. Additionally, d and γ denote the transmission distance and the path loss exponent, respectively.

For nodes and CHs, we assume that nodes have an initial energy of $E_i$ Joules and a sensing range of $R_{S_{\mathrm{1}}}$ meters. CHs are not restricted by energy limitations. They also may or may not carry out a sensing task, and they have a sensing range of $R_{S_{\mathrm{2}}}$ .

One objective of this paper is to find proper M and N so that any arbitrary point in area $\mathbb{R}$ can be covered with at least probability $C_g$ (i.e., guaranteed coverage) during time $T_f$ (the network lifetime).

2.2. Coverage Analysis

Like in [4], we first find an initial coverage in terms of the number of nodes in a HWSN deployed randomly over the area from coverage theory [18]. Then, we transform the survival and lifetime of nodes during $T_f$ into a coverage problem in terms of the density of the CHs affecting survival nodes after $T_f$ . From the two results above, we are able to lead the final coverage $C_f$ of the HWSN after $T_f$ . This procedure is possible because we can state that a node has covered an area only when the transmission of the data to its closest CH after performing a sensing task is completed.

We will consider two cases: in the first case, only nodes sense the area; and in the second case, CHs also sense the area. The latter case is more realistic and effective than the former. Finally, with these results, we establish the network design in Section 2.3 as an integer program to minimize the network cost while keeping the desired network coverage over a desired period.

2.2.1. Case Sensed by Only Nodes

For the first case above, from the results of coverage process theory [18], the mean and variance of the probability $C_n$ of covering an arbitrary point in $\mathbb{R}$ by N nodes are as follows:

$$\begin{array}{cc}& {\mu }_{C_n}=\mathrm{1}-e^{-\pi {\lambda }_{\mathrm{1}}},\\ {\sigma }_{C_n}^{\mathrm{2}}=\frac{\mathrm{8}\pi R_{S_{\mathrm{1}}}^{\mathrm{2}}}{‖\mathbb{R}‖}{e}^{-\mathrm{2}\pi {\lambda }_{\mathrm{1}}}\left({{\displaystyle \int }}_{\mathrm{0}}^{\mathrm{1}}\left(e^{{\lambda }_{\mathrm{1}}B\left(x\right)}-\mathrm{1}\right)x\hspace{0.17em}\text{d}x-\pi {\lambda }_{\mathrm{1}}\right),\end{array}$$

(2)

where

$$\begin{array}{cc}& B\left(x\right)=\left\{\begin{array}{cc}\pi -\mathrm{2}x\sqrt{\mathrm{1}-x^{\mathrm{2}}}-\mathrm{2}\arcsin \left(x\right),\hfill & \mathrm{0}\le x\le \mathrm{1}\hfill \\ 0,\hfill & x\ge \mathrm{1}\hfill \end{array}\right.\end{array}$$

(3)

and ${\lambda }_{\mathrm{1}}=N{R}_{S_{\mathrm{1}}}^{\mathrm{2}}/‖\mathbb{R}‖$ . In the case that $‖\mathbb{R}‖\to \infty$ , then ${\sigma }_{C_n}^{\mathrm{2}}\to \mathrm{0}$ . Therefore, the initial coverage $C_i$ of N nodes deployed randomly over a large area is the following deterministic value because its variance tends to 0:

$$\begin{array}{cc}& C_i=C_n=\mathrm{1}-e^{-\pi {\lambda }_{\mathrm{1}}}.\end{array}$$

(4)

To determine the final coverage $C_f$ , we have to find the number of dead nodes after $T_f$ . Suppose $E_c$ represents the energy consumed by a node during $T_f$ . This is then equal to the consumed energy per packet of transmission multiplied by the number of packets sent to CH. If the sensor has performed its tasks of sensing and transmitting, then $E_c<E_i$ . From (1), we can yield the maximum distance between a node and a CH, allowing the node to perform its tasks up to $T_f$ , as shown in Figure 1, which is determined as follows:

$$\begin{array}{cc}& D_m={\left(\frac{E_{i}T}{k{T}_f}-\frac{c}{k}\right)}^{\mathrm{1}/\gamma }.\end{array}$$

(5)

Figure 1

Example of HWSN deployed randomly over an area.

Thus, if a node has no CH closer than $D_m$ , the node will die before reaching $T_f$ . The number of operating and survival nodes after $T_f$ , therefore, is related to the area covered by M disks with the radius $D_m$ and the center at CHs positions. Like finding the initial coverage of nodes from coverage process theory, we can find the probability that a certain node is close enough to a CH and survives until $T_f$ . It is represented as follows:

$$\begin{array}{cc}& C^{\prime }=\mathrm{1}-e^{-\pi {\lambda }^{\prime }},\end{array}$$

(6)

where ${\lambda }^{\prime }=M{D}_m^{\mathrm{2}}/‖\mathbb{R}‖$ .

The boundary effect is negligible because the sensing range of a node is much smaller than $‖\mathbb{R}‖$ , and the nodes and CHs are placed in $\mathbb{R}$ independently. Therefore, the final coverage of network is as follows:

$$\begin{array}{cc}& C_f=C_i·C^{\prime }=\left(\mathrm{1}-e^{-\pi {\lambda }_{\mathrm{1}}}\right)\left(\mathrm{1}-e^{-\pi {\lambda }^{\prime }}\right).\end{array}$$

(7)

2.2.2. Case Sensed by CHs and Nodes

In the more practical case where CHs also sense the area, we can determine the probability of covering an arbitrary point by CHs in a similar fashion to the first case as follows:

$$\begin{array}{cc}& C_{\mathrm{C}\mathrm{H}}=\mathrm{1}-e^{-\pi {\lambda }_{\mathrm{2}}},\end{array}$$

(8)

where ${\lambda }_{\mathrm{2}}=M{R}_{S_2}^2/‖\mathbb{R}‖$ . At the beginning, an arbitrary point in $\mathbb{R}$ is either covered by CHs or nodes, and at this time, the initial coverage probability is as follows:

$$\begin{array}{cc}& C_i=\mathrm{1}-e^{-\pi \left({\lambda }_{\mathrm{1}}+{\lambda }_{\mathrm{2}}\right)}.\end{array}$$

(9)

We can assume $R_{S_{\mathrm{2}}}<D_m$ because the sensors range for communication is usually greater than that its range for sensing [19]. When the end of the desired period $T_f$ is reached, a point in $\mathbb{R}$ will either be covered by survival nodes, CHs, or both. The final coverage probability is as follows:

$$\begin{array}{cc}& C_f=C_n{C}^{\prime }+C_{\mathrm{C}\mathrm{H}}-C_n{C}_{\mathrm{C}\mathrm{H}}.\end{array}$$

(10)

The first and second terms are the coverage probabilities of only survival nodes and CH, respectively. The third term represents coverage by nodes and CHs simultaneously, which is allowed because given that $R_{S_{\mathrm{2}}}<D_m$ , all nodes that are located in the range covered by CHs have survived until $T_f$ . Therefore,

$$\begin{array}{cc}& C_f=\mathrm{1}-e^{-\pi {\lambda }_{\mathrm{2}}}+\left(e^{-\pi {\lambda }_{\mathrm{2}}}-e^{-\pi {\lambda }^{\prime }}\right)\left(\mathrm{1}-e^{-\pi {\lambda }_{\mathrm{1}}}\right).\end{array}$$

(11)

2.3. Heterogeneous WSN Design

This section provides a nonlinear integer optimization problem derived from the above coverage analysis with which we can predict the final network coverage with known parameters as a method to design a randomly deployed HWSN.

In previous research [4], the authors had simplified this design problem by assuming that only nodes sense the area to solve it through the mathematical analysis. This paper, however, is going to solve this optimization problem with more realistic approaches at the expense of increased complexity by applying optimization algorithms based on swarm intelligence. As in our previous work [7], we also consider the second case above because the case where CHs with rich energy resources also sense the area is efficient and effective in practical use.

We formulate the optimization problem to minimize the implementation cost while keeping at least guaranteed coverage $C_g$ during the desired network lifetime $T_f$ by adjusting the number of nodes and CHs. For this purpose, we assume that each node costs $H_n$ and each CH costs $H_{\mathrm{C}\mathrm{H}}$ for their implementation, such that $H_n<H_{\mathrm{C}\mathrm{H}}$ . Hence, the problem minimizing the network cost is as follows:

$$\begin{array}{cc}& \underset{N,M}{\min }\hspace{1em}f\left(N,M\right)=N{H}_n+M{H}_{\mathrm{C}\mathrm{H}}\end{array}$$

(12)

$$\begin{array}{cc}& \text{subject\hspace{0.17em}\hspace{0.17em}to}\hspace{1em}{C}_f\left(N,M\right)\ge C_g,N>\mathrm{0},\hspace{0.17em}\hspace{0.17em}M>\mathrm{0}.\end{array}$$

(13)

In (13), $C_f$ can be defined according to (7) or (11) according to the cases mentioned above.

As in [7], we can apply the binPSO algorithm to the above problem by first converting this constrained optimization problem into an unconstrained problem using the method of handling constraints. There are many methods for accomplishing this task: the penalty function method, the Lagrange multiplier method, the gradient projection method, and so forth. However, these methods are unfavorable because they require proper values for their control parameters to achieve satisfactory performance. So, like in [7], we apply Deb's method [20] based on the penalty function approach, which does not require any penalty parameter. The details about this method can be found in [20].

By Deb's method, the former problem is converted as follows:

$$\begin{array}{l}F\left(N,M\right)\\ =\left\{\begin{array}{ll}f\left(N,M\right),\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}g\left(N,M\right)\ge \mathrm{0},\hspace{0.17em}\hspace{0.17em}N>\mathrm{0},\hspace{0.17em}\hspace{0.17em}M>\mathrm{0}\hfill \\ f_{\mathrm{m}\mathrm{a}\mathrm{x}}+\left|g\left(N,M\right)\right|,\hfill & \text{otherwise},\hfill \end{array}\right.\end{array}$$

(14)

where $F(N,M)$ is the fitness function and the value $f_{\mathrm{m}\mathrm{a}\mathrm{x}}$ is the objective function value of the worst feasible solution of the solution candidates found by an algorithm. Additionally, $g(N,M)=C_f(N,M)/C_g-\mathrm{1}$ , which is a normalized constraint.

3. Binary Optimization Algorithms Based on Swarm Intelligence

As defined in Section 2.3, the HWSN design becomes an integer optimization problem with an integer-valued solution. To solve this problem, we use several optimization algorithms based on swarm intelligence, such as PSO, ABC, and ACO, because the more practical problem is more difficult to solve via mathematical analysis. However, the original forms of these algorithms are ill-suited to the integer optimization problem because these algorithms were first proposed to solve continuous-valued problems (by PSO [21] or ABC [22]) or combinatorial problems (by ACO [23]). Hence, we use the binary versions of each algorithm, that is, binPSO [15], binABC [16], and ${\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ . In other words, we first find binary-valued solutions using binary algorithms and then convert these to integer-valued solutions. Then, we evaluate these converted solutions with the objective function of the above integer optimization problem. Notably, the ${\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ is first proposed in this paper. This algorithm is implemented by combining the binary concepts from the binPSO and the binABC with the ACO algorithm for continuous domains, ${\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ [17]. The details of the ${\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ are introduced in Section 3.3.

3.1. Binary Particle Swarm Optimization (binPSO) Algorithm

The Particle Swarm Optimization (PSO) algorithm is an optimization algorithm inspired by the movement of schools of fish and flocks of birds. In the PSO algorithm, a particle's position is a candidate solution for the given optimization problem and the particles, or swarm, are iteratively moved in the search space of an optimization problem according to information about each particle's previous best position, $p_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}$ , and the best position of the particles so far, $g_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}$ .

Most variants based on the first PSO [21] have operated with continuous values in continuous search space, where the particles’ trajectories are determined by changes in position across some number of dimensions of the problem. In the binary version of the PSO algorithm (i.e., binPSO [15]), trajectories are defined as changes with the probability of whether the particle's coordinate will take on a zero or one value. In the binPSO, although the velocity $v_{i,d}$ represents the probability of the coordinate $x_{i,d}$ taking the value 1 (unlike in the continuous version of the PSO), the formula remains unchanged as follows:

$$\begin{array}{ll}{v}_{i,d}\left(k+\mathrm{1}\right)& =w{v}_{i,d}\left(k\right)+{\phi }_p{r}_p\left(p_{i,d}\left(k\right)-x_{i,d}\left(k\right)\right)\\ & +{\phi }_g{r}_g\left(g_d\left(k\right)-x_{i,d}\left(k\right)\right),\end{array}$$

(15)

where the parameters $r_p$ and $r_g$ are determined using a uniformly distributed random number within the range $\left[\begin{array}{cc}\mathrm{0}& \mathrm{1}\end{array}\right]$ , that is, $r_p,r_g~U(\mathrm{0,1})$ . In the first part of (15), the inertia weight w represents the degree of the momentum of the particles. The second term is the “cognition component,” which represents the independent behavior of the particle itself. The final term is the “social component,” which represents the interaction between the particles. The constants ${\phi }_p$ and ${\phi }_g$ determine the relative influence of the cognition and social components. In (15), unlike the continuous version, the values of $x_{i,d}$ , $p_{i,d}$ , and $g_d$ are only integers in $\{\mathrm{0,1}\}$ . From the probability $v_{i,d}$ , the next coordinate of $x_{i,d}$ is determined as follows:

$$\begin{array}{cc}& x_{i,d}\left(k+\mathrm{1}\right)=\left\{\begin{array}{cc}1,\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}\mathrm{rand}\left(\right)<S\left(v_{i,d}\left(k+\mathrm{1}\right)\right)\hfill \\ 0,\hfill & \text{otherwise},\hfill \end{array}\right.\end{array}$$

(16)

where the function $S(·)$ is a sigmoid limiting transformation and $\mathrm{rand}\left(\right)$ is a quasi-random number selected from a uniform distribution with a range $[\mathrm{0,1}]$ . Likewise, the continuous version of the PSO limited $v_{i,d}$ by the user parameter $V_{\mathrm{m}\mathrm{a}\mathrm{x}}$ ; also in the binPSO, $V_{\mathrm{m}\mathrm{a}\mathrm{x}}$ is retained; that is, $\left|v_{i,d}\right|<V_{\mathrm{m}\mathrm{a}\mathrm{x}}$ , and the smaller value allows a higher mutation rate.

3.2. Binary Artificial Bee Colony (binABC) Algorithm

The Artificial Bee Colony (ABC) algorithm is a population-based and stochastic optimization algorithm inspired by the intelligent foraging behavior of honeybees. In the ABC algorithm, artificial bees search for rich artificial food sources, that is, good solutions for a given optimization problem. The artificial bee colony consists of three groups of bees: employed bees associated with specific food sources that exploit their food sources, onlooker bees that watch the dance of employed bees within the hive to select a food source and help the employed bees find richer food sources, and scout bees that search food sources randomly. Likewise, their cooperative and iterative behaviors find the optimal solution to a given problem.

Most of the variants based on the original ABC [22] operate with continuous values in the continuous search space like the PSO. In contrast, the binary ABC algorithm (binABC [16]) finds a binary-valued solution in the binary-valued search space. The binABC borrows concepts from the binPSO. As mentioned above, in the binPSO, each component of the velocity vector, $v_{i,d}$ , is used to compute the probability that the corresponding component of the solution vector is bit $\mathrm{0}$ or bit $\mathrm{1}$ . In a similar way, the binABC uses each component of the neighbor food source position, $v_m^i$ , to calculate the probability of the coordinate $x_m^i$ taking the value 1. Unlike in the continuous version of the ABC, the formula remains unchanged as follows:

$$\begin{array}{cc}& v_m^i=x_m^i+{\varphi }_m^i\left(x_m^i-x_k^i\right),\end{array}$$

(17)

where the parameter ${\varphi }_m^i$ is a uniform random number within the range $[-a,a]$ , that is, ${\varphi }_m^i~U(\mathrm{0,1})$ , where $a=\mathrm{1}$ in general. From the value $v_m^i$ calculated from (17), the next coordinate $x_m^i$ is determined as follows:

$$\begin{array}{cc}& x_m^i=\left\{\begin{array}{cc}\mathrm{1},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}\mathrm{rand}\left(\right)<S\left(v_m^i\right)\hfill \\ \mathrm{0},\hfill & \text{otherwise},\hfill \end{array}\right.\end{array}$$

(18)

where the function $S(·)$ is a sigmoid limiting transformation and $\mathrm{rand}\left(\right)$ is a quasi-random number selected from a uniform distribution with a range $[\mathrm{0,1}]$ . Likewise, the binPSO limited $v_{i,d}$ by the user parameter $V_{\mathrm{m}\mathrm{a}\mathrm{x}}$ ; also in the binABC, $V_{\mathrm{m}\mathrm{a}\mathrm{x}}$ is used; that is, $\left|v_m^i\right|<V_{\mathrm{m}\mathrm{a}\mathrm{x}}$ .

3.3. Binary Ant Colony Optimization (binACO ${}_{\mathbb{R}}$ ) Algorithm

The Ant Colony Optimization (ACO) algorithm is a metaheuristic based on the foraging behavior of real ants. While moving, real ants that find food deposit pheromones on the way to their nests. The other ants then follow these deposited pheromones. Although pheromones evaporate as time passes, they open up new possibilities as ants can choose to follow a path heavily laden with pheromones. In this way, ants can search for the shortest path from their nest to a food source with only pheromone information. In ACO algorithm, a set of virtual ants searches for optimal solutions to a given optimization problem in the search space.

The first ACO algorithm [23] was proposed to solve a Traveling Salesman Problem (TSP) that is a representative combinatorial problem of finding the shortest path that traverses all cities exactly once and then returns to the starting city. Since then, the ACO for continuous domains, called ${\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ [17], was proposed without any major conceptual change to the original ACO. In this paper, a binary version of the ${\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ algorithm, ${\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ , is proposed by combining the above ${\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ for continuous domains with the binary concepts from the binPSO, as in the binABC. In other words, each component $x_l^i$ is used to compute the probability of the next coordinate taking the value 1. In the ${\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ , each component $x_l^i$ is determined by sampling from the following Gaussian kernel for ith dimension:

$$\begin{array}{ll}{G}^i\left(x\right)& =\sum _{l=\mathrm{1}}^{N_{\mathbf{T}}}{\omega }_l{g}_l^i\left(x\right)\\ & =\sum _{l=\mathrm{1}}^{N_{\mathbf{T}}}{\omega }_l\frac{\mathrm{1}}{{\sigma }_l^i\sqrt{\mathrm{2}\pi }}\exp \left(-\frac{{\left(x-{\mu }_l^i\right)}^{\mathrm{2}}}{\mathrm{2}{{\sigma }_l^i}^{\mathrm{2}}}\right),\end{array}$$

(19)

where

$$\begin{array}{cc}& {\omega }_l=\frac{\mathrm{1}}{q{N}_{\mathbf{T}}\sqrt{\mathrm{2}\pi }}\exp \left(-\frac{{\left(l-\mathrm{1}\right)}^{\mathrm{2}}}{\mathrm{2}{q}^{\mathrm{2}}{N_{\mathbf{T}}}^{\mathrm{2}}}\right),\\ {\mu }_l^i=x_l^i,\\ {\sigma }_l^i=\xi {{\displaystyle \sum }}_{k=\mathrm{1}}^{N_{\mathbf{T}}}\frac{\left|x_k^i-x_l^i\right|}{N_{\mathbf{T}}-\mathrm{1}},\end{array}$$

(20)

and $N_{\mathbf{T}}$ is the size of the archive T that stores and keeps the best $N_{\mathbf{T}}$ solutions found by previous moving ants in the ${\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ . From each value $x_l^i$ selected from (19), the next coordinate of $x_l^i$ is determined as follows:

$$\begin{array}{cc}& x_l^i=\left\{\begin{array}{cc}\mathrm{1},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}\mathrm{rand}\left(\right)<S\left(x_l^i\right)\hfill \\ \mathrm{0},\hfill & \text{otherwise},\hfill \end{array}\right.\end{array}$$

(21)

where the function $S(·)$ is a sigmoid limiting transformation and $\mathrm{rand}\left(\right)$ is a quasi-random number selected from a uniform distribution with a range $[\mathrm{0,1}]$ . Likewise, the binPSO limited $v_{i,d}$ by the user parameter $V_{\mathrm{m}\mathrm{a}\mathrm{x}}$ ; also in the ${\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ , $V_{\mathrm{m}\mathrm{a}\mathrm{x}}$ is used; that is, $\left|x_l^i\right|<V_{\mathrm{m}\mathrm{a}\mathrm{x}}$ .

4. Simulation Results and Discussions

In this section, we solve several HWSN design problems with the second sensing condition from Section 2.2.2 using the above three binary optimization algorithms and compare their performances. The simulation was implemented in MATLAB on a PC running Windows 8.1, with an Intel Core i3 CPU 540 operating at 3.07 GHz and 4 GB of RAM. The parameters used for each algorithm are shown in Table 1. The termination criterion of all algorithms in all of the scenarios is reaching the maximum number of the evaluation, $MaxNFEs=\mathrm{1}{\mathrm{0}}^{\mathrm{6}}$ . The parameters related to the consumed energy for the transmission of a data packet were set for all simulations as follows: $k=\mathrm{1}{\mathrm{0}}^{-\mathrm{7}}$ , $c=\mathrm{5}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{5}}$ , $\gamma =\mathrm{2}$ , $T=\mathrm{1}$ , and $E_i=\mathrm{3}\hspace{0.17em}\mathrm{J}$ . For each scenario in the simulation, the parameters for the environment and the desired HWSN were set as shown in Table 2. All scenarios were performed 30 times for statistics.

Table 1

Parameter setting for each algorithm in the simulation.

Algorithm	Parameter	Value
binPSO [15]	Number of particles ( $$N_P$$ )	20
	Weight for previous velocity (w)	0.729
	Coefficient of cognition term ( $${\phi }_p$$ )	1.49445
	Coefficient of social term ( $${\phi }_g$$ )	1.49445
	Maximum velocity ( $$V_{\max }$$ )	1
binABC [16]	Number of employed bees ( $$N_B$$ )	50
	$$limit$$ or abandonment criteria ( $$N_L$$ )	100
	Maximum velocity ( $$V_{\max }$$ )	1
binACO $${}_{\mathbb{R}}$$	Archive size ( $$N_{\mathbf{T}}$$ )	10
	Number of ants used in an iteration ( $$N_A$$ )	50
	Speed of convergence (ξ)	0.85
	Locality of search process (q)	0.1
	Maximum velocity ( $$V_{\max }$$ )	1

Table 2

Parameter setting for the environment and the desired HWSN in each scenario: least guaranteed coverage ( $$C_g$$ ), desired network lifetime ( $$T_f$$ ), sensing range of node ( $$R_{S_{\mathrm{1}}}$$ ) and CH ( $$R_{S_{\mathrm{2}}}$$ ), and cost for each node ( $$H_n$$ ) and each CH ( $$H_{\text{CH}}$$ ).

Parameters	Scenario 1	Scenario 2	Scenario 3	Scenario 4	Scenario 5
Area size $$‖\mathbb{R}‖$$ [m2]	$$\mathrm{1000}\times \mathrm{1000}$$ (square)	$$\mathrm{2.5}\times \mathrm{1}{\mathrm{0}}^{\mathrm{5}}$$ (circle)	$$\mathrm{500}\times \mathrm{500}$$ (square)	$$\mathrm{5}\times \mathrm{1}{\mathrm{0}}^{\mathrm{5}}$$ (circle)	$$\mathrm{600}\times \mathrm{600}$$ (square)
$$C_g$$	0.80	0.85	0.90	0.80	0.85
$$T_f$$ [hour]	6000	4000	3000	4000	5000
$$R_{S_{\mathrm{1}}}$$ [m]	10	7	3	5	6
$$R_{S_{\mathrm{2}}}$$ [m]	15	10	6	20	15
$$H_n$$	0.1	0.5	0.1	0.3	0.2
$$H_{\text{CH}}$$	1	2	1.5	5	1.5

Table 3 shows the statistical results of the simulations with CH and node sensing in five different environments, and Figure 2 is the boxplot of three algorithms for each scenario. In all scenarios, the binPSO algorithm shows the best performance among the three binary optimization algorithms. The binPSO obtains near-optimal solutions with similar costs in all scenarios. As a statistical significance test, the two-sample t-test was conducted between the binPSO and the others. The significance sign “(+)” in the table means that the binPSO is significantly better, the sign “(~)” means no significant difference, and the sign “(—)” means significantly worse. The results of the t-test also showed that the binPSO is significantly better than the other algorithms. The ${\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ first proposed in this paper shows the second best performance, demonstrating an improvement in performance over the binABC algorithm. Additionally, the ${\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ finds near-optimal solutions that are the same as those found by the binPSO. However, the ${\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ requires more exploration to achieve the same performance as the binPSO.

Table 3

Simulation results with sensing of CHs and nodes in five different environments: the listed values are the statistics of the costs of five scenarios for each algorithm for the 30 runs. Q1 and Q3 are the 25th and 75th percentiles, respectively. For median and mean values, the numbers in square brackets indicate the rankings of the three algorithms. The p values are the results of the two-sample t-test between the binPSO which has the best performance among three algorithms and the others for each scenario. The significance sign “(+)” means that the binPSO is significantly better, the sign “(~)” means no significant difference, and the sign “(—)” means significantly worse.

Scenarios		binPSO			binABC			binACO $${}_{\mathbb{R}}$$
		Cost	N	M	Cost	N	M	Cost	N	M
1	Best	743.9	5089	235	744	5080	236	743.9	5089	235
	Q1	743.9	5049	239	744.7	5147	230	744	5070	237
	Median	744 [ $$\mathit{1}$$ ]	5080	236	746.6 [ $$\mathit{3}$$ ]	4896	257	744.2 [ $$\mathit{2}$$ ]	5113	233
	Q3	744	5060	238	748	4880	260	744.5	5005	244
	Worst	744.3	5123	232	750.4	4864	264	746.3	5083	238
	Mean	744.0 [ $$\mathit{1}$$ ]	—	—	746.7 [ $$\mathit{3}$$ ]	—	—	744.4 [ $$\mathit{2}$$ ]	—	—
	S.D.	0.0935	—	—	1.8687	—	—	0.5816	—	—
	p value	—	—	—	$$\mathit{4.51}E-\mathit{11}(+)$$	—	—	$$\mathit{7.16}E-\mathit{05}(+)$$	—	—
2	Best	1619	2974	66	1620	2976	66	1619	2974	66
	Q1	1619	2970	67	1629	2914	86	1619.5	2975	66
	Median	1619 [ $$\mathit{1}$$ ]	2966	68	1633 [ $$\mathit{3}$$ ]	2914	88	1620.5 [ $$\mathit{2}$$ ]	2969	68
	Q3	1619	2958	70	1648	3072	56	1623	2990	64
	Worst	1619.5	2951	72	1664	3072	64	1627.5	2931	81
	Mean	1619 [ $$\mathit{1}$$ ]	—	—	1639.7 [ $$\mathit{3}$$ ]	—	—	1621.6 [ $$\mathit{2}$$ ]	—	—
	S.D.	0.0913	—	—	14.2106	—	—	2.3721	—	—
	p value	—	—	—	$$\mathit{6.83}E-\mathit{11}(+)$$	—	—	$$\mathit{2.45}E-\mathit{07}(+)$$	—	—
3	Best	3130.5	16380	995	3137.1	16356	1001	3130.5	16380	995
	Q1	3130.5	16380	995	3150	16320	1012	3132.2	16382	996
	Median	3130.5 [ $$\mathit{1}$$ ]	16380	995	3164.8 [ $$\mathit{3}$$ ]	16288	1024	3136.2 [ $$\mathit{2}$$ ]	16362	1000
	Q3	3130.8	16383	995	3197.6	16136	1056	3142	16360	1004
	Worst	3133	16375	997	3244.8	16128	1088	3164	16280	1024
	Mean	3130.9 [ $$\mathit{1}$$ ]	—	—	3176.2 [ $$\mathit{3}$$ ]	—	—	3139.2 [ $$\mathit{2}$$ ]	—	—
	S.D.	0.6539	—	—	30.2756	—	—	8.6116	—	—
	p value	—	—	—	$$\mathit{3.00}E-\mathit{11}(+)$$	—	—	$$\mathit{2.11}E-\mathit{06}(+)$$	—	—
4	Best	3111.5	7605	166	3111.8	7706	160	3111.5	7605	166
	Q1	3111.6	7672	162	3112.4	7808	154	3111.9	7723	159
	Median	3111.6 [ $$\mathit{1}$$ ]	7522	171	3113.7 [ $$\mathit{3}$$ ]	7179	192	3112.3 [ $$\mathit{2}$$ ]	7691	161
	Q3	3111.7	7489	173	3115.2	7184	192	3112.5	7525	171
	Worst	3112.1	7757	157	3121.2	8204	132	3115.4	7968	145
	Mean	3111.7 [ $$\mathit{1}$$ ]	—	—	3114.2 [ $$\mathit{3}$$ ]	—	—	3112.5 [ $$\mathit{2}$$ ]	—	—
	S.D.	0.1613	—	—	2.0573	—	—	0.9191	—	—
	p value	—	—	—	$$\mathit{1.24}E-\mathit{08}(+)$$	—	—	$$\mathit{1.46}E-\mathit{05}(+)$$	—	—
5	Best	1246.8	5229	134	1247	5200	138	1246.8	5214	136
	Q1	1246.8	5229	134	1247.2	5216	136	1247.1	5268	129
	Median	1246.8 [ $$\mathit{1}$$ ]	5199	138	1247.6 [ $$\mathit{3}$$ ]	5248	132	1247.3 [ $$\mathit{2}$$ ]	5209	137
	Q3	1247	5260	130	1247.6	5248	132	1247.7	5196	139
	Worst	1247.3	5284	127	1248.2	5221	136	1250.2	5081	156
	Mean	1246.9 [ $$\mathit{1}$$ ]	—	—	1247.5 [ $$\mathit{3}$$ ]	—	—	1247.4 [ $$\mathit{2}$$ ]	—	—
	S.D.	0.1377	—	—	0.3281	—	—	0.6698	—	—
	p value	—	—	—	$$\mathit{1.70}E-\mathit{13}(+)$$	—	—	$$\mathit{1.13}E-\mathit{05}(+)$$	—	—

Figure 2

Boxplot of three algorithms for each scenario.

5. Conclusions

In this paper, we designed a heterogeneous wireless sensor network (HWSN) with nodes and CHs that are all able to sense information. We accomplished this by defining the constrained integer optimization problem, converting it to the unconstrained problem and solving this problem using the binary optimization algorithms based on swarm intelligence, namely, binPSO, binABC, and ${\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ . We then compared the performance of each algorithm by applying them to real problems. From the simulation results, the binPSO algorithm outperformed the others based on swarm intelligence, showing relatively consistent solutions every time for each test case. The ${\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{A}\mathrm{C}\mathrm{O}}_{\mathbb{R}}$ , which was first proposed in this paper, needed to improve the exploration ability, though its performance was better than that of the binABC algorithm.