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

Authors: Joon-Woo Lee; Won Kim
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## 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.


---

## Body

## 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 Section2, 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 deployingM 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]:(1)
e
d
=
k
d
γ
+
c
,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 ofE
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 properM 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 Section2.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:(2)
μ
C
n
=
1
-
e
-
π
λ
1
,
σ
C
n
2
=
8
π
R
S
1
2
R
e
-
2
π
λ
1
∫
0
1
e
λ
1
B
x
-
1
x
d
x
-
π
λ
1
,where(3)
B
x
=
π
-
2
x
1
-
x
2
-
2
arcsin
⁡
x
,
0
≤
x
≤
1
0
,
x
≥
1and λ
1
=
N
R
S
1
2
/
R. In the case that R
→
∞, then σ
C
n
2
→
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:(4)
C
i
=
C
n
=
1
-
e
-
π
λ
1
.To determine the final coverageC
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:(5)
D
m
=
E
i
T
k
T
f
-
c
k
1
/
γ
.Figure 1
Example of HWSN deployed randomly over an area.Thus, if a node has no CH closer thanD
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:(6)
C
′
=
1
-
e
-
π
λ
′
,where λ
′
=
M
D
m
2
/
R.The boundary effect is negligible because the sensing range of a node is much smaller thanR, and the nodes and CHs are placed in R independently. Therefore, the final coverage of network is as follows:(7)
C
f
=
C
i
·
C
′
=
1
-
e
-
π
λ
1
1
-
e
-
π
λ
′
.


#### 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:(8)
C
C
H
=
1
-
e
-
π
λ
2
,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:(9)
C
i
=
1
-
e
-
π
λ
1
+
λ
2
.We can assumeR
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:(10)
C
f
=
C
n
C
′
+
C
C
H
-
C
n
C
C
H
.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,(11)
C
f
=
1
-
e
-
π
λ
2
+
e
-
π
λ
2
-
e
-
π
λ
′
1
-
e
-
π
λ
1
.


### 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 coverageC
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:(12)
min
⁡
N
,
M
f
N
,
M
=
N
H
n
+
M
H
C
H
(13)
subject  to
C
f
N
,
M
≥
C
g
,
N
>
0
,
M
>
0
.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:(14)
F
N
,
M
=
f
N
,
M
,
if
g
N
,
M
≥
0
,
N
>
0
,
M
>
0
f
m
a
x
+
g
N
,
M
,
otherwise
,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.


## 2.1. System Model

The proposed heterogeneous wireless sensor network (HWSN) is constructed by uniformly and randomly deployingM 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]:(1)
e
d
=
k
d
γ
+
c
,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 ofE
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 properM 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 Section2.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:(2)
μ
C
n
=
1
-
e
-
π
λ
1
,
σ
C
n
2
=
8
π
R
S
1
2
R
e
-
2
π
λ
1
∫
0
1
e
λ
1
B
x
-
1
x
d
x
-
π
λ
1
,where(3)
B
x
=
π
-
2
x
1
-
x
2
-
2
arcsin
⁡
x
,
0
≤
x
≤
1
0
,
x
≥
1and λ
1
=
N
R
S
1
2
/
R. In the case that R
→
∞, then σ
C
n
2
→
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:(4)
C
i
=
C
n
=
1
-
e
-
π
λ
1
.To determine the final coverageC
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:(5)
D
m
=
E
i
T
k
T
f
-
c
k
1
/
γ
.Figure 1
Example of HWSN deployed randomly over an area.Thus, if a node has no CH closer thanD
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:(6)
C
′
=
1
-
e
-
π
λ
′
,where λ
′
=
M
D
m
2
/
R.The boundary effect is negligible because the sensing range of a node is much smaller thanR, and the nodes and CHs are placed in R independently. Therefore, the final coverage of network is as follows:(7)
C
f
=
C
i
·
C
′
=
1
-
e
-
π
λ
1
1
-
e
-
π
λ
′
.


### 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:(8)
C
C
H
=
1
-
e
-
π
λ
2
,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:(9)
C
i
=
1
-
e
-
π
λ
1
+
λ
2
.We can assumeR
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:(10)
C
f
=
C
n
C
′
+
C
C
H
-
C
n
C
C
H
.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,(11)
C
f
=
1
-
e
-
π
λ
2
+
e
-
π
λ
2
-
e
-
π
λ
′
1
-
e
-
π
λ
1
.


## 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:(2)
μ
C
n
=
1
-
e
-
π
λ
1
,
σ
C
n
2
=
8
π
R
S
1
2
R
e
-
2
π
λ
1
∫
0
1
e
λ
1
B
x
-
1
x
d
x
-
π
λ
1
,where(3)
B
x
=
π
-
2
x
1
-
x
2
-
2
arcsin
⁡
x
,
0
≤
x
≤
1
0
,
x
≥
1and λ
1
=
N
R
S
1
2
/
R. In the case that R
→
∞, then σ
C
n
2
→
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:(4)
C
i
=
C
n
=
1
-
e
-
π
λ
1
.To determine the final coverageC
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:(5)
D
m
=
E
i
T
k
T
f
-
c
k
1
/
γ
.Figure 1
Example of HWSN deployed randomly over an area.Thus, if a node has no CH closer thanD
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:(6)
C
′
=
1
-
e
-
π
λ
′
,where λ
′
=
M
D
m
2
/
R.The boundary effect is negligible because the sensing range of a node is much smaller thanR, and the nodes and CHs are placed in R independently. Therefore, the final coverage of network is as follows:(7)
C
f
=
C
i
·
C
′
=
1
-
e
-
π
λ
1
1
-
e
-
π
λ
′
.


## 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:(8)
C
C
H
=
1
-
e
-
π
λ
2
,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:(9)
C
i
=
1
-
e
-
π
λ
1
+
λ
2
.We can assumeR
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:(10)
C
f
=
C
n
C
′
+
C
C
H
-
C
n
C
C
H
.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,(11)
C
f
=
1
-
e
-
π
λ
2
+
e
-
π
λ
2
-
e
-
π
λ
′
1
-
e
-
π
λ
1
.


## 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 coverageC
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:(12)
min
⁡
N
,
M
f
N
,
M
=
N
H
n
+
M
H
C
H
(13)
subject  to
C
f
N
,
M
≥
C
g
,
N
>
0
,
M
>
0
.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:(14)
F
N
,
M
=
f
N
,
M
,
if
g
N
,
M
≥
0
,
N
>
0
,
M
>
0
f
m
a
x
+
g
N
,
M
,
otherwise
,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 Section2.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:(15)
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
,where the parameters r
p and r
g are determined using a uniformly distributed random number within the range 0
1, 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: (16)
x
i
,
d
k
+
1
=
1
,
if
rand
⁡
<
S
v
i
,
d
k
+
1
0
,
otherwise
,where the function S
(
·
) 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: (17)
v
m
i
=
x
m
i
+
ϕ
m
i
x
m
i
-
x
k
i
,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: (18)
x
m
i
=
1
,
if
rand
⁡
<
S
v
m
i
0
,
otherwise
,where the function S
(
·
) 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 (binACOR) 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: (19)
G
i
x
=
∑
l
=
1
N
T
ω
l
g
l
i
x
=
∑
l
=
1
N
T
ω
l
1
σ
l
i
2
π
exp
⁡
-
x
-
μ
l
i
2
2
σ
l
i
2
,where (20)
ω
l
=
1
q
N
T
2
π
exp
⁡
-
l
-
1
2
2
q
2
N
T
2
,
μ
l
i
=
x
l
i
,
σ
l
i
=
ξ
∑
k
=
1
N
T
x
k
i
-
x
l
i
N
T
-
1
,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:(21)
x
l
i
=
1
,
if
rand
⁡
<
S
x
l
i
0
,
otherwise
,where the function S
(
·
) 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.


## 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:(15)
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
,where the parameters r
p and r
g are determined using a uniformly distributed random number within the range 0
1, 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: (16)
x
i
,
d
k
+
1
=
1
,
if
rand
⁡
<
S
v
i
,
d
k
+
1
0
,
otherwise
,where the function S
(
·
) 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: (17)
v
m
i
=
x
m
i
+
ϕ
m
i
x
m
i
-
x
k
i
,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: (18)
x
m
i
=
1
,
if
rand
⁡
<
S
v
m
i
0
,
otherwise
,where the function S
(
·
) 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 (binACOR) 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: (19)
G
i
x
=
∑
l
=
1
N
T
ω
l
g
l
i
x
=
∑
l
=
1
N
T
ω
l
1
σ
l
i
2
π
exp
⁡
-
x
-
μ
l
i
2
2
σ
l
i
2
,where (20)
ω
l
=
1
q
N
T
2
π
exp
⁡
-
l
-
1
2
2
q
2
N
T
2
,
μ
l
i
=
x
l
i
,
σ
l
i
=
ξ
∑
k
=
1
N
T
x
k
i
-
x
l
i
N
T
-
1
,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:(21)
x
l
i
=
1
,
if
rand
⁡
<
S
x
l
i
0
,
otherwise
,where the function S
(
·
) 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 Section2.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
×
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
binACOR
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
⁡
⁡)
1Table 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 sizeR [m2]
1000
×
1000 (square)
2.5
×
1
0
5 (circle)
500
×
500 (square)
5
×
1
0
5 (circle)
600
×
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.5Table3 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. Thep 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
binACOR
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, andb
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.



---

*Source: 690235-2015-08-13.xml*