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 ( ${b i n A C O}_{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 ${b i n A C O}_{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, ${A C O}_{R}$ [17]. The details of the ${b i n A C O}_{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 $R$ with a large size $‖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{matrix} e (d) = k d^{γ} + c, \end{matrix}

(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_{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_{2}}$ .

One objective of this paper is to find proper M and N so that any arbitrary point in area $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 $R$ by N nodes are as follows:

\begin{matrix} μ_{C_{n}} = 1 - e^{- π λ_{1}}, \\ σ_{C_{n}}^{2} = \frac{8 π R_{S_{1}}^{2}}{‖R‖} e^{- 2 π λ_{1}} (\int_{0}^{1} (e^{λ_{1} B (x)} - 1) x d x - π λ_{1}), \end{matrix}

(2)

where

\begin{matrix} B (x) = \{\begin{cases} π - 2 x \sqrt{1 - x^{2}} - 2 \arcsin (x), & 0 \leq x \leq 1 \\ 0, & x \geq 1 \end{cases} \end{matrix}

(3)

and

λ_{1} = N R_{S_{1}}^{2} / ‖R‖

. In the case that

‖R‖ \to \infty

, then

σ_{C_{n}}^{2} \to 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{matrix} C_{i} = C_{n} = 1 - e^{- π λ_{1}} . \end{matrix}

(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{matrix} D_{m} = {(\frac{E_{i} T}{k T_{f}} - \frac{c}{k})}^{1 / γ} . \end{matrix}

(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{matrix} C^{'} = 1 - e^{- π λ^{'}}, \end{matrix}

(6)

where

λ^{'} = M D_{m}^{2} / ‖R‖

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

\begin{matrix} C_{f} = C_{i} \cdot C^{'} = (1 - e^{- π λ_{1}}) (1 - e^{- π λ^{'}}) . \end{matrix}

(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{matrix} C_{C H} = 1 - e^{- π λ_{2}}, \end{matrix}

(8)

where

λ_{2} = M R_{S_{2}}^{2} / ‖R‖

. At the beginning, an arbitrary point in

R

is either covered by CHs or nodes, and at this time, the initial coverage probability is as follows:

\begin{matrix} C_{i} = 1 - e^{- π (λ_{1} + λ_{2})} . \end{matrix}

(9)

We can assume $R_{S_{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 $R$ will either be covered by survival nodes, CHs, or both. The final coverage probability is as follows:

\begin{matrix} C_{f} = C_{n} C^{'} + C_{C H} - C_{n} C_{C H} . \end{matrix}

(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_{2}} < D_{m}

, all nodes that are located in the range covered by CHs have survived until

T_{f}

. Therefore,

\begin{matrix} C_{f} = 1 - e^{- π λ_{2}} + (e^{- π λ_{2}} - e^{- π λ^{'}}) (1 - e^{- π λ_{1}}) . \end{matrix}

(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_{C H}$ for their implementation, such that $H_{n} < H_{C H}$ . Hence, the problem minimizing the network cost is as follows:

\begin{matrix} \min_{N, M} f (N, M) = N H_{n} + M H_{C H} \end{matrix}

(12)

\begin{matrix} subject  to C_{f} (N, M) \geq C_{g}, N > 0, M > 0 . \end{matrix}

(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 (N, M) \\ = \{\begin{cases} f (N, M), & if g (N, M) \geq 0, N > 0, M > 0 \\ f_{m a x} + |g (N, M)|, & otherwise, \end{cases} \end{array}

(14)

where

F (N, M)

is the fitness function and the value

f_{m a 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} - 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 ${b i n A C O}_{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 ${b i n A C O}_{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, ${A C O}_{R}$ [17]. The details of the ${b i n A C O}_{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_{b e s t}$ , and the best position of the particles so far, $g_{b e s 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}{l} v_{i, d} (k + 1) & = w v_{i, d} (k) + φ_{p} r_{p} (p_{i, d} (k) - x_{i, d} (k)) \\ + φ_{g} r_{g} (g_{d} (k) - x_{i, d} (k)), \end{array}

(15)

where the parameters

r_{p}

and

r_{g}

are determined using a uniformly distributed random number within the range

[\begin{bmatrix} 0 & 1 \end{bmatrix}]

, that is,

r_{p}, r_{g} ~ U (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

φ_{p}

and

φ_{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

{0,1}

. From the probability

v_{i, d}

, the next coordinate of

x_{i, d}

is determined as follows:

\begin{matrix} x_{i, d} (k + 1) = \{\begin{cases} 1, & if rand () < S (v_{i, d} (k + 1)) \\ 0, & otherwise, \end{cases} \end{matrix}

(16)

where the function

S (\cdot)

is a sigmoid limiting transformation and

rand ()

is a quasi-random number selected from a uniform distribution with a range

[0,1]

. Likewise, the continuous version of the PSO limited

v_{i, d}

by the user parameter

V_{m a x}

; also in the binPSO,

V_{m a x}

is retained; that is,

|v_{i, d}| < V_{m a 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 $0$ or bit $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{matrix} v_{m}^{i} = x_{m}^{i} + ϕ_{m}^{i} (x_{m}^{i} - x_{k}^{i}), \end{matrix}

(17)

where the parameter

ϕ_{m}^{i}

is a uniform random number within the range

[- a, a]

, that is,

ϕ_{m}^{i} ~ U (0,1)

, where

a = 1

in general. From the value

v_{m}^{i}

calculated from (17), the next coordinate

x_{m}^{i}

is determined as follows:

\begin{matrix} x_{m}^{i} = \{\begin{cases} 1, & if rand () < S (v_{m}^{i}) \\ 0, & otherwise, \end{cases} \end{matrix}

(18)

where the function

S (\cdot)

is a sigmoid limiting transformation and

rand ()

is a quasi-random number selected from a uniform distribution with a range

[0,1]

. Likewise, the binPSO limited

v_{i, d}

by the user parameter

V_{m a x}

; also in the binABC,

V_{m a x}

is used; that is,

|v_{m}^{i}| < V_{m a x}

3.3. Binary Ant Colony Optimization (binACO $_{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 ${A C O}_{R}$ [17], was proposed without any major conceptual change to the original ACO. In this paper, a binary version of the ${A C O}_{R}$ algorithm, ${b i n A C O}_{R}$ , is proposed by combining the above ${A C O}_{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 ${A C O}_{R}$ , each component $x_{l}^{i}$ is determined by sampling from the following Gaussian kernel for ith dimension:

\begin{array}{l} G^{i} (x) & = \sum_{l = 1}^{N_{T}} ω_{l} g_{l}^{i} (x) \\ = \sum_{l = 1}^{N_{T}} ω_{l} \frac{1}{σ_{l}^{i} \sqrt{2 π}} \exp (- \frac{{(x - μ_{l}^{i})}^{2}}{2 {σ_{l}^{i}}^{2}}), \end{array}

(19)

where

\begin{matrix} ω_{l} = \frac{1}{q N_{T} \sqrt{2 π}} \exp (- \frac{{(l - 1)}^{2}}{2 q^{2} {N_{T}}^{2}}), \\ μ_{l}^{i} = x_{l}^{i}, \\ σ_{l}^{i} = ξ \sum_{k = 1}^{N_{T}} \frac{|x_{k}^{i} - x_{l}^{i}|}{N_{T} - 1}, \end{matrix}

(20)

and

N_{T}

is the size of the archive T that stores and keeps the best

N_{T}

solutions found by previous moving ants in the

{A C O}_{R}

. From each value

x_{l}^{i}

selected from (19), the next coordinate of

x_{l}^{i}

is determined as follows:

\begin{matrix} x_{l}^{i} = \{\begin{cases} 1, & if rand () < S (x_{l}^{i}) \\ 0, & otherwise, \end{cases} \end{matrix}

(21)

where the function

S (\cdot)

is a sigmoid limiting transformation and

rand ()

is a quasi-random number selected from a uniform distribution with a range

[0,1]

. Likewise, the binPSO limited

v_{i, d}

by the user parameter

V_{m a x}

; also in the

{b i n A C O}_{R}

V_{m a x}

is used; that is,

|x_{l}^{i}| < V_{m a 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, $M a x N F E s = 1 0^{6}$ . The parameters related to the consumed energy for the transmission of a data packet were set for all simulations as follows: $k = 1 0^{- 7}$ , $c = 5 \times 1 0^{- 5}$ , $γ = 2$ , $T = 1$ , and $E_{i} = 3 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 ( $φ_{p}$ )	1.49445
	Coefficient of social term ( $φ_{g}$ )	1.49445
	Maximum velocity ( $V_{\max}$ )	1

binABC [16]	Number of employed bees ( $N_{B}$ )	50
	$l i m i t$ or abandonment criteria ( $N_{L}$ )	100
	Maximum velocity ( $V_{\max}$ )	1

binACO $_{R}$	Archive size ( $N_{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_{1}}$ ) and CH ( $R_{S_{2}}$ ), and cost for each node ( $H_{n}$ ) and each CH ( $H_{CH}$ ).

Parameters	Scenario 1	Scenario 2	Scenario 3	Scenario 4	Scenario 5
Area size $‖R‖$ [m²]	$1000 \times 1000$ (square)	$2.5 \times 1 0^{5}$ (circle)	$500 \times 500$ (square)	$5 \times 1 0^{5}$ (circle)	$600 \times 600$ (square)
$C_{g}$	0.80	0.85	0.90	0.80	0.85
$T_{f}$ [hour]	6000	4000	3000	4000	5000
$R_{S_{1}}$ [m]	10	7	3	5	6
$R_{S_{2}}$ [m]	15	10	6	20	15
$H_{n}$	0.1	0.5	0.1	0.3	0.2
$H_{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 ${b i n A C O}_{R}$ first proposed in this paper shows the second best performance, demonstrating an improvement in performance over the binABC algorithm. Additionally, the ${b i n A C O}_{R}$ finds near-optimal solutions that are the same as those found by the binPSO. However, the ${b i n A C O}_{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 $_{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 [ $1$ ]	5080	236	746.6 [ $3$ ]	4896	257	744.2 [ $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 [ $1$ ]	—	—	746.7 [ $3$ ]	—	—	744.4 [ $2$ ]	—	—
	S.D.	0.0935	—	—	1.8687	—	—	0.5816	—	—
	p value	—	—	—	$4.51 E - 11 (+)$	—	—	$7.16 E - 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 [ $1$ ]	2966	68	1633 [ $3$ ]	2914	88	1620.5 [ $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 [ $1$ ]	—	—	1639.7 [ $3$ ]	—	—	1621.6 [ $2$ ]	—	—
	S.D.	0.0913	—	—	14.2106	—	—	2.3721	—	—
	p value	—	—	—	$6.83 E - 11 (+)$	—	—	$2.45 E - 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 [ $1$ ]	16380	995	3164.8 [ $3$ ]	16288	1024	3136.2 [ $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 [ $1$ ]	—	—	3176.2 [ $3$ ]	—	—	3139.2 [ $2$ ]	—	—
	S.D.	0.6539	—	—	30.2756	—	—	8.6116	—	—
	p value	—	—	—	$3.00 E - 11 (+)$	—	—	$2.11 E - 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 [ $1$ ]	7522	171	3113.7 [ $3$ ]	7179	192	3112.3 [ $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 [ $1$ ]	—	—	3114.2 [ $3$ ]	—	—	3112.5 [ $2$ ]	—	—
	S.D.	0.1613	—	—	2.0573	—	—	0.9191	—	—
	p value	—	—	—	$1.24 E - 08 (+)$	—	—	$1.46 E - 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 [ $1$ ]	5199	138	1247.6 [ $3$ ]	5248	132	1247.3 [ $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 [ $1$ ]	—	—	1247.5 [ $3$ ]	—	—	1247.4 [ $2$ ]	—	—
	S.D.	0.1377	—	—	0.3281	—	—	0.6698	—	—
	p value	—	—	—	$1.70 E - 13 (+)$	—	—	$1.13 E - 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 ${b i n A C O}_{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 ${b i n A C O}_{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.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT, and Future Planning (Grant no. 2010-0023035).

References

Heinzelman

W. B.

Chandrakasan

A. P.

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks

IEEE Transactions on Wireless Communications 2002 1 4 660 670

10.1109/twc.2002.804190

2-s2.0-33646589837

Lee

J.-W.

Choi

B.-S.

Lee

J.-J.

Energy-efficient coverage of wireless sensor networks using ant colony optimization with three types of pheromones

IEEE Transactions on Industrial Informatics 2011 7 3 419 427

10.1109/tii.2011.2158836

2-s2.0-80051780804

Lee

J.-W.

Lee

J.-J.

Ant-colony-based scheduling algorithm for energy-efficient coverage of WSN

IEEE Sensors Journal 2012 12 10 3036 3046

10.1109/JSEN.2012.2208742

2-s2.0-84865213757

Noori

Ardakani

Design of heterogeneous sensor networks with lifetime and coverage considerations

IEEE Wireless Communications Letters 2012 1 3 193 196

10.1109/wcl.2012.031512.120063

2-s2.0-84863009668

Saleem

Ullah

Farooq

BeeSensor: an energy-efficient and scalable routing protocol for wireless sensor networks

Information Sciences 2012 200 38 56

10.1016/j.ins.2012.02.024

2-s2.0-84860310986

Lee

J.-W.

Lee

J.-Y.

Lee

J.-J.

Jenga-inspired optimization algorithm for energy-efficient coverage of unstructured WSNs

IEEE Wireless Communications Letters 2013 2 1 34 37

10.1109/wcl.2012.100912.120648

2-s2.0-84874986280

Lee

J.-W.

Lee

J.-J.

Design of efficient Heterogeneous Wireless Sensor Networks optimized by discrete Particle Swarm Optimization

Proceedings of the 44th IEEE International Symposium on Robotics (ISR ′13)

October 2013

Seoul, Republic of Korea

1 5

10.1109/isr.2013.6695690

2-s2.0-84893213859

Sahoo

R. R.

Singh

Sahoo

B. M.

Majumder

Ray

Sarkar

S. K.

A light weight trust based secure and energy efficient clustering in wireless sensor network: honey bee mating intelligence approach

Procedia Technology 2013 10 515 523

Kuila

Gupta

S. K.

Jana

P. K.

A novel evolutionary approach for load balanced clustering problem for wireless sensor networks

Swarm and Evolutionary Computation 2013 12 48 56

10.1016/j.swevo.2013.04.002

2-s2.0-84887117287

10.

Halder

Bit

S. D.

Enhancement of wireless sensor network lifetime by deploying heterogeneous nodes

Journal of Network and Computer Applications 2014 38 1 106 124

10.1016/j.jnca.2013.03.008

2-s2.0-84897610673

11.

Liu

Ant colony optimization with greedy migration mechanism for node deployment in wireless sensor networks

Journal of Network and Computer Applications 2014 39 1 310 318

10.1016/j.jnca.2013.07.010

2-s2.0-84893750316

12.

Kuila

Jana

P. K.

Energy efficient clustering and routing algorithms for wireless sensor networks: particle swarm optimization approach

Engineering Applications of Artificial Intelligence 2014 33 127 140

10.1016/j.engappai.2014.04.009

2-s2.0-84901705924

13.

Tao

Huang

Yan

Zhou

SA-PSO based optimizing reader deployment in large-scale RFID Systems

Journal of Network and Computer Applications 2015 52 90 100

10.1016/j.jnca.2015.02.011

14.

Zhu

Y.-H.

W.-D.

Pan

Tang

Y.-P.

An energy-efficient data gathering algorithm to prolong lifetime of wireless sensor networks

Computer Communications 2010 33 5 639 647

10.1016/j.comcom.2009.11.008

2-s2.0-74849093345

15.

Kennedy

Eberhart

R. C.

A discrete binary version of the particle swarm algorithm

Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics

October 1997

Orlando, Fla, USA

IEEE

4104 4108

10.1109/ICSMC.1997.637339

2-s2.0-0031352450

16.

Pampara

Engelbrecht

A. P.

Binary artificial bee colony optimization

Proceedings of the IEEE Symposium On Swarm Intelligence

April 2011

Paris, France

1 8

10.1109/sis.2011.5952562

17.

Socha

Dorigo

Ant colony optimization for continuous domains

European Journal of Operational Research 2008 185 3 1155 1173

10.1016/j.ejor.2006.06.046

MR2361750

ZBL1146.90537

2-s2.0-34848884200

18.

Hall

Introduction to the Theory of Coverage Processes 1988

Queensland, Australia

John Wiley & Sons

Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics

10.1016/0167-0115(88)90159-0

MR973404

19.

Olfati-Saber

Sandell

N. F.

Distributed tracking in sensor networks with limited sensing range

American Control Conference

June 2008

Seattle, Wash, USA

3157 3162

10.1109/acc.2008.4586978

2-s2.0-52449100954

20.

Deb

An efficient constraint handling method for genetic algorithms

Computer Methods in Applied Mechanics and Engineering 2000 186 2–4 311 338

10.1016/s0045-7825(99)00389-8

2-s2.0-0033729054

21.

Kennedy

Eberhart

R. C.

Particle swarm optimization

Proceedings of the IEEE International Conference on Neural Networks

December 1995

Perth, Australia

1942 1948

2-s2.0-0029535737

22.

Karaboga

Basturk

A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm

Journal of Global Optimization 2007 39 3 459 471

10.1007/s10898-007-9149-x

MR2346178

2-s2.0-35148821762

23.

Dorigo

Maniezzo

Colorni

Ant system: optimization by a colony of cooperating agents

IEEE Transactions on Systems, Man, and Cybernetics Part B 1996 26 1 29 41

10.1109/3477.484436

2-s2.0-0030082551

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

Abstract

1. Introduction

2. Randomly Deployed Heterogeneous WSN Design

2.1. System Model

2.2. Coverage Analysis

2.2.1. Case Sensed by Only Nodes

2.2.2. Case Sensed by CHs and Nodes

2.3. Heterogeneous WSN Design

3. Binary Optimization Algorithms Based on Swarm Intelligence

3.1. Binary Particle Swarm Optimization (binPSO) Algorithm

3.2. Binary Artificial Bee Colony (binABC) Algorithm

3.3. Binary Ant Colony Optimization (binACO R ) Algorithm

4. Simulation Results and Discussions

5. Conclusions

Footnotes

Conflict of Interests

Acknowledgment

References

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