# Multiobjective Optimization for a Wireless Ad Hoc Sensor Distribution on Shaped-Bounded Areas

Authors: Armando Céspedes-Mota; Gerardo Castañón; Alberto F. Martínez-Herrera; Leopoldo Eduardo Cárdenas-Barrón
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Resource efficiency in wireless ad hoc networks has become a widely studied NP-problem. This problem may be suboptimally solved by heuristic strategies, focusing on several features like the channel capacity, coverage area, and more. In this work, maximizing coverage area and minimizing energy consumption are suboptimally adjusted with the implementation of two of Storn/Price’s Multiobjective Differential Evolution (DE) algorithm versions. Additionally, their extended representations with the use ofrandom-
M parameter into the mutation operator were also evaluated. These versions optimize the initial random distribution of the nodes in different shaped areas, by keeping the connectivity of all the network nodes by using the Prim–Dijkstra algorithm. Moreover, the Hungarian algorithm is applied to find the minimum path distance between the initial and final node positions in order to arrange them at the end of the DE algorithm. A case base is analyzed theoretically to check how DE is able to find suboptimal solutions with certain accuracy. The results here computed show that the inclusion of random-
M and completion of the algorithm, where the area is pondered with 60% and the energy is pondered with 40%, lead to energy optimization and a total coverage area higher than 90%, by considering the best results on each scenario. Thus, this work shows that the aforementioned strategies are feasible to be applied on this problem with successful results. Finally, these results are compared against two typical bioinspired multiobjective algorithms, where the DE algorithm shows the best tradeoff.


---

## Body

## 1. Introduction

Nowadays, it is well known that the distribution of sensors in a wireless ad hoc sensor network (WAHSN) is a challenge in the research of wireless communications, because it is necessary to increase both lifetime and coverage area demand of the network. Furthermore, it is required to avoid a weak connectivity.A WAHSN contains a number of geographically dispersed mobile sensors. Each sensor node has wireless communication, collaborative signal processing, and network capabilities subject to some technical constraints. The mobile sensor nodes are free to move and self-organize in an arbitrary way while the communication is made via radio transceivers. Therefore, a WAHSN is able to determine the value of different parameters such as temperature and geographic coordinates of a given location, detect the occurrence of events, classify a detected object, and track an object. In consequence, it is necessary that the required data be disseminated to the proper end users [1, 2]. It is important to remark that wireless sensor networks (WSN) are a type of ad hoc network composed of a large number of sensor nodes, which are densely deployed either inside the sense perception area or very close to it. The nodes are not connected to each other. Basically, they are stationary or at most slowly moving [1]. In contrast, a mobile ad hoc network (MANET) is an autonomous collection of mobile users connected by one to one wireless links. The MANETs topology may change continuously in an unpredictably way over time. The mobile nodes in MANETs can renew, replace, or recharge their batteries or source of energy. Although WAHSNs, WSNs, and MANETs involve multihop communications, many end-to-end routing schemes proposed for MANETs are inappropriate for WAHSN and WSNs for the previously mentioned reasons [3]. Nevertheless, sensor distribution schemes between WAHSNs and MANETs can be compared. A key factor that distinguishes the WAHSNs from MANETs is that the end goal is detection and estimation of some events of interest and not just communication [1, 2].In spite of the fact that our work is applicable to WAHSNs, MANETs, and also WSNs under certain modifications, the analysis on WAHSNs due to some characteristics and resource constraints such as energy, coverage area, and connectivity optimization is made.Sensor distribution is one of the fundamental problems in WAHSNs and regularly has been suboptimally solved by heuristic strategies such as genetic algorithms, among several others as shown by [4–8]. It is worth mentioning that sensor distribution with minimum energy connectivity is an NP-complete problem [9–12]. In the literature, different strategies for wireless ad hoc and sensor networks related to topology control [2], node localization [13, 14], distributed coverage [15], and network lifetime [16] are described to provide solutions for sensor distribution, coverage area, and energy consumption problems. Additional related problems in wireless communication such as frequency allocation and interference have been also solved by bioinspired algorithms as it is reported in [17, 18] or in [19], where the authors show an efficient way of solving the minimum number of hops among nodes to be communicated.To optimize the sensor distribution, DE algorithm is used. DE is a very simple but very powerful stochastic global optimizer for a continuous search domain. It was proposed by [20] and represents a very complex evolution process. Cleverly using the differences between the populations, a simple but fast linear operator called differentiation is created, which makes DE unique. A survey of the applications of DE to different optimization problems shows that DE generally outperforms other evolutionary algorithms [21–23]. An updated reference with novel DE algorithm versions and additional applications are found at [24, 25]. DE exploits a population of potential solutions to effectively probe the search spaces. The algorithm is initialized with a population of random candidate solutions, which are conceptualized as individuals. In this work, an individual includes the coordinates of the sensor nodes (
x
,
y
) followed by its communication radii values. For each individual in the population, a descendant is created from three parents. One parent, called the main parent, is disturbed by the vector of the difference of the other two parents. If the descendant has a better performance as measured by the objective function, it replaces the individual; otherwise, the original individual is retained and is passed on to the next generation of the algorithm and the descendant is discarded. This process is repeated until it reaches the termination condition. For a complete theoretical analysis of the DE algorithm, the reader is referred to [20].Node distribution optimization in mobile sensor networks is presented in [26], where they analyze the sensor network coverage area and its coverage redundant area using DE. Moreover, the optimal power allocation in WSNs using DE is given in [27]. Also, in [28], DE is applied to maximize the lifetime of the WSNs using disjoint sets of sensors to cover a set of targets. However, it is important to mention that [26–28] do not consider ad hoc sensor networks. They use the DE algorithm only for WSNs. On the other hand, a DE based topology control mechanism in MANETs is presented in [29] to deploy the nodes with the maximum coverage area. Here, the topology control is managed with the use of a Markov chain model. A similar approach is followed in [30] to evaluate the node distribution, but now based on Voronoi regions for each node. However, [29, 30] do not consider optimization of energy consumption for maintaining the network connectivity and coverage area simultaneously in a multiobjective fitness function.The approach followed in [31] analyzed the coverage area of sensor networks, where the main goal is to maximize the coverage area in presence of obstacles such as walls. In [32] the same approach of maximizing the coverage area in the presence of obstacles is extended, including the energy consumed in the objective function. The redundant area is also considered in the objective function. In [33], an improved DEA version based on a best-optimal-solution sorting technique is compared with the classical DEA and the Nondominated Sorting Genetic Algorithm II (NSGA-II), showing that the first one has the best performance when computing the coverage area. Additionally, the number of nodes needed to obtain the maximum coverage area is diminished to determine the minimum feasible. In [34], the coverage area is optimized by using the improved versions of DEA such as the Self-Adaptive Differential Evolution (jDE) and the Adaptive Differential Evolution (JADE). As expected, the jDE and JADE have better performance than the classical DEA versions. In [35], DEA is applied for node position estimation in convex and nonconvex configurations.Other aspects of wireless sensor networks can be tackled by implementing other bioinspired algorithms. For instance, in [6], the coverage area is optimized with Particle Swarm Optimization (PSO). Coverage area and energy are considered in a multiobjective version of PSO as shown in [5], where the parameters are controlled with a clustering approach. For routing management, Ant Colony is implemented in [36] as well as in [8]. Routing is also solved by the Strength Pareto Evolutionary algorithm (SPEA2) as shown in [37]. Optimal path problem is treated in [38], where DEA is the best solution compared to the classical PSO and GA strategies. Node anchors can be deployed with bioinspired techniques as shown in [39] with Ant Colony. Such scenario is found when RFID readers are deployed to detect tags. In [40], a combination of GA and PSO is generated to do so.Additionally, in [41], two multiobjective algorithms are compared, the Multiobjective Simulated Annealing (MOSA) and NSGA-II. Such comparison is done to determine the algorithm that gives the best distribution output with fewer nodes. In [42], two algorithms are compared to solve WSN scenarios: SPEA2 and NSGA-II. The objective function includes the energy consumption, the coverage area, and the network reliability, where the energy component is analyzed against the elapsed time. For scenarios where the complexity is increased, SPEA2 is better than NSGA-II and vice versa. In [43] different WSN scenarios are tested, where NSGA-II and Learning Automata (LA) are combined to create a hybrid multiobjective algorithm. This hybrid version outperforms NSGA-II. The main goal is to minimize the number of active sensors that cover the maximum possible area and minimize the energy consumption while maintaining the network connectivity. In [44] the Multiobjective Evolution algorithm based on Decomposition (MOEA/D) and NSGA-II are compared to determine which is the best option to maximize the coverage area and minimize the energy consumption in WSN, where it is claimed that MOEA/D gives better results than NSGA-II. In [45], three optimization strategies are evaluated, the Multiobjective Particle Swarm Optimization (MOPSO), NSGA-II, and a proposed optimization denoted as Heuristic 3-Phases (H3P). H3P is formed by 3 steps: clustering, Pareto construction, and disassembly. The goal is to minimize the number of sensors when maximizing the number of targets to be detected, where H3P presents the best performance among the presented optimization strategies. In [46], NSGA-II is implemented and compared with MOEA/D to obtain the best routing combination by minimizing the energy consumption while detecting a large number of targets as possible, where it is shown that NSGA-II is better than MOEA/D. In [47], a discrete DEA version and NSGA-II are implemented to reach the best compromise among three goals: the delay of a packet from the origin to the destiny in the network, the packet delivery ratio, and the flow conservation. It is done to help the routing process with time efficiency, where it is shown that DEA outperforms NSGA-II. A detailed survey for more available techniques applied on WSN can be consulted in [48].Compared to the existing bioinspired techniques in the open literature [26, 32] and the method here presented, the followed approach is based on a simplified version of the MOEA/D techniques presented in [49], where a set of weights is assigned on each function to be optimized and the summation of them is equal to 1. Such variant is known asWeighted Sum Approach [49, 50]. For the sake of clarity, the method here implemented is denoted as Multiobjective Differential Evolution algorithm (MODEA).MODEA is applied to the optimization of network energy consumption to maintain the network connectivity and network coverage area in WAHSNs, following a convex model [35]. The algorithm makes sensor radius adjustments and assumes the mobility of the sensors in order optimize two objectives: maximizing the network coverage area and reducing network energy consumption. It is worth mentioning that consequently also the network lifetime is extended.Additionally, the proposed algorithm emphasizes the successful communication between sensors in a given neighborhood, with the use of the Prim–Dijkstra algorithm described by [51, 52]. If a tree is not created, the nodes distribution is discarded even when the network fulfills the rest of the restrictions regarding area, energy, and bounds on different shaped areas. Also, the Hungarian algorithm [53] is used to find the shortest distance between the initial and the final node positions. This information is important for the case of having mobile ad hoc sensors; each node knows where to move with the minimal distance.A summary of the employed techniques and the involved parameters is shown in Table1.Table 1
Summary of the references presented in Section1.
ID
Cite
Technique
Involved variables
DE
[26]
DE/rand/1
Coverage area, energy
[27]
DE/rand/1, DE/Best/1
Power allocation
[27]
DE/Curr-to-Best/1, DE/rand-to-best/1
Power allocation
[28]
DE/Best/1
Coverage area
[29]
DE/rand/1, Markov topology control
Coverage area
[30]
DE/rand/1, Voronoi topology control
Coverage area
[31]
DE/rand/1
Coverage area, redundant area
[32]
DE/rand/1 with randM
Coverage area, energy, redundant area
[33]
Classical and modified DE/rand/1, NSGA-II
Coverage area with node elimination
[34]
DE/Best/1, jDE, JADE
Coverage area
[35]
Modified DE/Curr-to-Best/1
Node position estimation
[47]
DEA and NSGA-II
Routing
Others
[5]
PSO
Energy and coverage area (by clustering)
[6]
PSO
Coverage area
[8]
Ant Colony
Routing
[36]
Ant Colony
Routing
[37]
SPEA2
Routing
[38]
DE, PSO, GA
Optimal path
[39]
Ant Colony
Node deployment (target coverage)
[40]
Combined GA and PSO
Node deployment (target coverage)
[41]
MOSA and NSGA-II
Node deployment
[42]
SPEA-2 and NSGA-II
Energy, coverage area
[43]
NSGA-II and LA
Energy, coverage area
[44]
MOEA/D and NSGA-II
Energy, coverage area
[45]
NSGA-II, MOPSO, H3P
Node deployment (target coverage)
[46]
NSGA-II
Node deployment (target coverage), routingThe rest of this paper is organized as follows: Section2 presents the methodology. Section 3 describes theoretical models to find the energy lower bound and coverage area’s upper bound. Section 4 develops and explains the MODEA for wireless ad hoc sensor distribution. Section 5 provides numerical results and a discussion. Finally, Section 6 gives the conclusions and some future research directions.


## 2. Description of the Method

### 2.1. Sensor Coverage Model

The coverage area of a sensor is the region within which the sensor is able to detect or analyze the sensing parameters. There exists a special interest in the sensor distribution for which communication with neighboring nodes is more energy efficient. Also, it is assumed that the coverage radius of each sensor helps to determine its communication link distance through minimum spanning tree to any of its neighbors, and it depends on the kind of sensors considered. Additionally, the sensor distribution on different shaped areas is considered. The main objective of the sensor coverage model is to achieve a balance between the maximum effective coverage area and the minimum communication sensor energy.According to [26], the node set on the target area m
×
n grid can be defined as(1)
N
=
N
1
,
N
2
,
…
,
N
z
,where z is the cardinality of N.The coverage range of a nodeN
i can be expressed as a circle centered at its coordinates (
x
i
,
y
i
) with sensing radius r
i. The (
x
i
,
y
i
) coordinates express the position of sensor nodes and the subindex i represents the sensor node index. A grid point P
(
x
,
y
) is covered by a sensor node i if and only if its distance to the center (
x
i
,
y
i
) of the circle (2) is not larger than the sensing radius r
i:(2)
d
N
i
,
P
=
x
-
x
i
2
+
y
-
y
i
2
.First of all, a binary detection model is considered. A random variableE
i is introduced to describe the event in which the sensor node i covers a given point P
(
x
,
y
). The probability of the event E
i, P
{
E
i
}, is equal to the coverage probability P
c
o
v
(
x
,
y
,
N
i
). This probability is a binary valued function such as(3)
P
c
o
v
x
,
y
,
N
i
=
1
if
x
-
x
i
2
+
y
-
y
i
2
≤
r
i
2
0
otherwise
.This model is applied in all cases in Section5. It is clear that a point should be evaluated against all the nodes present in the network; then(4)
S
x
,
y
=
∑
i
=
1
z
P
c
o
v
x
,
y
,
N
i
,where S
(
x
,
y
) is the number of times that the coordinate (
x
,
y
) is covered by the node set.Nevertheless, to obtain the proper covered area by the set of nodes, the functionR
(
x
,
y
) is computed to verify if the coordinate is covered at least once or if it is not covered at all N
i.(5)
R
x
,
y
=
1
S
x
,
y
≥
1
0
S
x
,
y
=
0
,and then the covered area is computed as(6)
A
c
o
v
=
∑
y
=
1
n
∑
x
=
1
m
R
x
,
y
m
×
n
.Equation (6) is implemented in our simulation by sweeping all the (
x
,
y
) points of the target area m
×
n. For different area configurations, this area is replaced by the bounded area of interest.


### 2.2. Energy Consumption

There are models for efficient energy consumption in MANETs [5], WAHSNs [10], WSNs [54], and many others. The energy consumption model used in this work is based in [55], this model is also used in [26]. In order to show the optimization process in coverage area and energy consumption, the total energy for maintaining the network connectivity is considered as the total energy consumption of the network.(7)
E
c
s
d
=
μ
∑
i
=
1
z
r
i
α
,where μ is the power per unit area in milliwatts per square meter (mW/m2), considering that the sensors are on the floor, r
i is the sensor radius of the node i in meters, and α
=
2 since the communication medium is the air (free space) [56]. In this paper, μ equals 0.005 (mW/m2). The path loss exponent α takes different values according the environment. For urban area cellular radio α
=
2.7
–
3.5, for shadowed urban cellular radio α
=
3
–
5, for in-building line-of-sight from 1.6 to 1.8, for obstructed in-building from 4 to 6, and for obstructed in factories from 2 to 2.3, the power per unit area changes in a 3D environment to mW/m2, [56].


## 2.1. Sensor Coverage Model

The coverage area of a sensor is the region within which the sensor is able to detect or analyze the sensing parameters. There exists a special interest in the sensor distribution for which communication with neighboring nodes is more energy efficient. Also, it is assumed that the coverage radius of each sensor helps to determine its communication link distance through minimum spanning tree to any of its neighbors, and it depends on the kind of sensors considered. Additionally, the sensor distribution on different shaped areas is considered. The main objective of the sensor coverage model is to achieve a balance between the maximum effective coverage area and the minimum communication sensor energy.According to [26], the node set on the target area m
×
n grid can be defined as(1)
N
=
N
1
,
N
2
,
…
,
N
z
,where z is the cardinality of N.The coverage range of a nodeN
i can be expressed as a circle centered at its coordinates (
x
i
,
y
i
) with sensing radius r
i. The (
x
i
,
y
i
) coordinates express the position of sensor nodes and the subindex i represents the sensor node index. A grid point P
(
x
,
y
) is covered by a sensor node i if and only if its distance to the center (
x
i
,
y
i
) of the circle (2) is not larger than the sensing radius r
i:(2)
d
N
i
,
P
=
x
-
x
i
2
+
y
-
y
i
2
.First of all, a binary detection model is considered. A random variableE
i is introduced to describe the event in which the sensor node i covers a given point P
(
x
,
y
). The probability of the event E
i, P
{
E
i
}, is equal to the coverage probability P
c
o
v
(
x
,
y
,
N
i
). This probability is a binary valued function such as(3)
P
c
o
v
x
,
y
,
N
i
=
1
if
x
-
x
i
2
+
y
-
y
i
2
≤
r
i
2
0
otherwise
.This model is applied in all cases in Section5. It is clear that a point should be evaluated against all the nodes present in the network; then(4)
S
x
,
y
=
∑
i
=
1
z
P
c
o
v
x
,
y
,
N
i
,where S
(
x
,
y
) is the number of times that the coordinate (
x
,
y
) is covered by the node set.Nevertheless, to obtain the proper covered area by the set of nodes, the functionR
(
x
,
y
) is computed to verify if the coordinate is covered at least once or if it is not covered at all N
i.(5)
R
x
,
y
=
1
S
x
,
y
≥
1
0
S
x
,
y
=
0
,and then the covered area is computed as(6)
A
c
o
v
=
∑
y
=
1
n
∑
x
=
1
m
R
x
,
y
m
×
n
.Equation (6) is implemented in our simulation by sweeping all the (
x
,
y
) points of the target area m
×
n. For different area configurations, this area is replaced by the bounded area of interest.


## 2.2. Energy Consumption

There are models for efficient energy consumption in MANETs [5], WAHSNs [10], WSNs [54], and many others. The energy consumption model used in this work is based in [55], this model is also used in [26]. In order to show the optimization process in coverage area and energy consumption, the total energy for maintaining the network connectivity is considered as the total energy consumption of the network.(7)
E
c
s
d
=
μ
∑
i
=
1
z
r
i
α
,where μ is the power per unit area in milliwatts per square meter (mW/m2), considering that the sensors are on the floor, r
i is the sensor radius of the node i in meters, and α
=
2 since the communication medium is the air (free space) [56]. In this paper, μ equals 0.005 (mW/m2). The path loss exponent α takes different values according the environment. For urban area cellular radio α
=
2.7
–
3.5, for shadowed urban cellular radio α
=
3
–
5, for in-building line-of-sight from 1.6 to 1.8, for obstructed in-building from 4 to 6, and for obstructed in factories from 2 to 2.3, the power per unit area changes in a 3D environment to mW/m2, [56].


## 3. Base Case: Ideal Distribution of 10 Nodes into a Squared Area

In this section, the methods to obtain the energy and coverage area bounds are presented. In order to find these lower and upper bounds, an example of 10 nodes distributed in an area of40
×
40 m2—see Figure 1—is considered. It is assumed that the sensors can have a transmitting radius between 6 and 8 meters. Details to compute these bounds are described in the following subsections.Figure 1
Node distribution to calculate upper bound.


### 3.1. Energy Lower Bound

The energy lower bound is easily calculated using (7) considering a radius of 6 meters and μ
=
0.005mW/m2. For instance, assuming 10 nodes, the lowest allowed value for energy is E
LB
=
(
0.005
)
(
10
)
(
6
2
)
=
1.8 mW.


### 3.2. Area Upper Bound

The sensor distribution shown in Figure1 is one among several that provides the nearest value to the maximum coverage area given by 10 nodes using a radius of 8 meters and including maximum three intersections of three circles. The main goal in proposing this case is their comparison to the suboptimal outputs derived of MODEA by having all the nodes’ radii equal to 8 meters. If these suboptimal solutions are near to this theoretical case, then the application of MODEA will be considered feasible. Figure 1 is used as the base case model to determine itstheoretical area upper bound.At the top corners of Figure1, the overlap of three circles is observed. Figure 2 shows the details of these three overlapped circles. The covered area of these three circles represents in this paper the coverage area of three overlapped wireless sensors. The set theory helps to determine the total area in a union of sets when some of the sets overlap. To obtain the covered area of the union of three overlapped circles, the inclusion/exclusion rule is used. This rule establishes that the area of the three circles is computed at the beginning. After that, all the intersection areas between two circles A
N
1
∩
N
2, A
N
1
∩
N
3, A
N
2
∩
N
3 are subtracted. At the end, the intersection area of the three circles A
N
1
∩
N
2
∩
N
3 is added [57, 58]. The equation of the area of the three circles is(8)
A
3
C
=
3
π
r
2
-
A
N
1
∩
N
2
-
A
N
1
∩
N
3
-
A
N
2
∩
N
3
+
⋯
+
A
N
1
∩
N
2
∩
N
3
,where A
N
1
∩
N
2
=
A
0
+
A
2, A
N
1
∩
N
3
=
A
0
+
A
3, A
N
2
∩
N
3
=
A
0
+
A
1 and A
N
1
∩
N
2
∩
N
3
=
A
0.Figure 2
Parameters involved in the intersection of three circles.This result is then used to determine the area of the base case model of 10 sensors. For this model, the area of 10 sensors is computed; then, the nine intersection areas between two circles similar to(
A
0
+
A
3
) and the two intersection areas between two circles similar to (
A
0
+
A
1
) are subtracted; and, finally, the two intersection areas of three circles are added.It is important to remark that for any finite number of overlapped circles, the covered area can be seen as a set of circles with intersections and is obtained by the use of the expression [57] as(9)
A
c
o
v
=
∑
i
=
1
z
A
N
i
-
∑
i
<
j
≤
z
z
A
N
i
∩
N
j
+
⋯
+
∑
i
<
j
<
k
≤
z
z
A
N
i
∩
N
j
∩
N
k
+
-
1
z
+
1
A
⋂
i
=
1
z
N
i
.According to [59], it is possible to preserve two communication links with an angle of 5
π
/
6 with the minimum power required, but it is valid for directional communication. For omnidirectional communication, it is not necessary. To obtain the maximum coverage area, it is well known that the hexagon configuration is the ideal distribution, where the angle presented on each vertex is equal to 2
π
/
3, but it is valid for circles with equal radius and where there is not a neighbor circle covering each node. Nevertheless, for our case, we have a set of circles with different radius and where each node is covered by at least a neighbor circle.Now, to find the total area of Figure1, first find the area of 10 independent circles A
10
C given by(10)
A
10
C
=
10
π
r
2
,and then use the intersection between two circles denoted as A
i
2
C, [60].(11)
A
i
2
C
=
2
r
2
arccos
⁡
d
2
r
-
1
2
d
4
r
2
-
d
2
,where d is the distance between the centers of the two circles. Assume r
1
=
r
2
=
r
3
=
r, d
12
=
d
13
=
r; therefore d
23
=
r
2. Observe that Figure 2 shows the variables of this equation where δ is the width of the intersection A
N
2
∩
N
3 and δ
=
2
r
-
D. Now assuming an intersection with d
=
r, the intersection area A
N
1
∩
N
2 (A
0 and A
2) or A
N
1
∩
N
3 (A
0 and A
3) [60],(12)
A
i
2
C
=
2
r
2
arccos
⁡
1
2
-
1
2
r
2
3
.The area of intersectionA
N
2
∩
N
3 (A
0 and A
1), denoted as A
i
2
C
′ is an intersection where d
=
d
23
=
r
2, [60],(13)
A
i
2
C
′
=
2
r
2
arccos
⁡
1
2
-
r
2
.Figure2 shows the intersection area between three circles denoted as A
0. This area is known as acircular triangle, which is a triangle with arc shaped sides (
c
1
,
c
2
,
c
3
). The area can be obtained using the radius and the length of the three arcs as shown in Figure 2. The area is given by the following equation [61]:(14)
A
0
=
1
4
κ
λ
ν
σ
+
⋯
+
∑
k
=
1
3
r
k
2
arcsin
⁡
c
k
2
r
k
-
c
k
4
4
r
k
2
-
c
k
2
,where κ
=
(
c
1
+
c
2
+
c
3
), λ
=
(
c
2
+
c
3
-
c
1
), ν
=
(
c
1
+
c
3
-
c
2
), σ
=
(
c
1
+
c
2
-
c
3
),(15)
c
1
2
=
2
r
2
-
d
2
2
+
2
r
4
-
3
r
2
d
2
2
+
d
4
4
-
⋯
-
d
r
2
-
d
2
4
-
d
r
2
2
-
d
2
4
,and c
1
=
c
2.The appendix shows how the equation forc
3 is obtained:(16)
c
3
=
-
r
2
+
r
3
2
.Therefore, the coverage area upper bound(
A
UB
) of ten wireless sensors as shown in Figure 1 is given by(17)
A
UB
=
A
10
C
-
9
A
i
2
C
-
2
A
i
2
C
′
+
2
A
0
.With the completion of this analysis, it is possible to obtain the coverage area upper bound, 1286.7 m2. In Section 5, the values obtained with the DE algorithm are compared to the bounds.


## 3.1. Energy Lower Bound

The energy lower bound is easily calculated using (7) considering a radius of 6 meters and μ
=
0.005mW/m2. For instance, assuming 10 nodes, the lowest allowed value for energy is E
LB
=
(
0.005
)
(
10
)
(
6
2
)
=
1.8 mW.


## 3.2. Area Upper Bound

The sensor distribution shown in Figure1 is one among several that provides the nearest value to the maximum coverage area given by 10 nodes using a radius of 8 meters and including maximum three intersections of three circles. The main goal in proposing this case is their comparison to the suboptimal outputs derived of MODEA by having all the nodes’ radii equal to 8 meters. If these suboptimal solutions are near to this theoretical case, then the application of MODEA will be considered feasible. Figure 1 is used as the base case model to determine itstheoretical area upper bound.At the top corners of Figure1, the overlap of three circles is observed. Figure 2 shows the details of these three overlapped circles. The covered area of these three circles represents in this paper the coverage area of three overlapped wireless sensors. The set theory helps to determine the total area in a union of sets when some of the sets overlap. To obtain the covered area of the union of three overlapped circles, the inclusion/exclusion rule is used. This rule establishes that the area of the three circles is computed at the beginning. After that, all the intersection areas between two circles A
N
1
∩
N
2, A
N
1
∩
N
3, A
N
2
∩
N
3 are subtracted. At the end, the intersection area of the three circles A
N
1
∩
N
2
∩
N
3 is added [57, 58]. The equation of the area of the three circles is(8)
A
3
C
=
3
π
r
2
-
A
N
1
∩
N
2
-
A
N
1
∩
N
3
-
A
N
2
∩
N
3
+
⋯
+
A
N
1
∩
N
2
∩
N
3
,where A
N
1
∩
N
2
=
A
0
+
A
2, A
N
1
∩
N
3
=
A
0
+
A
3, A
N
2
∩
N
3
=
A
0
+
A
1 and A
N
1
∩
N
2
∩
N
3
=
A
0.Figure 2
Parameters involved in the intersection of three circles.This result is then used to determine the area of the base case model of 10 sensors. For this model, the area of 10 sensors is computed; then, the nine intersection areas between two circles similar to(
A
0
+
A
3
) and the two intersection areas between two circles similar to (
A
0
+
A
1
) are subtracted; and, finally, the two intersection areas of three circles are added.It is important to remark that for any finite number of overlapped circles, the covered area can be seen as a set of circles with intersections and is obtained by the use of the expression [57] as(9)
A
c
o
v
=
∑
i
=
1
z
A
N
i
-
∑
i
<
j
≤
z
z
A
N
i
∩
N
j
+
⋯
+
∑
i
<
j
<
k
≤
z
z
A
N
i
∩
N
j
∩
N
k
+
-
1
z
+
1
A
⋂
i
=
1
z
N
i
.According to [59], it is possible to preserve two communication links with an angle of 5
π
/
6 with the minimum power required, but it is valid for directional communication. For omnidirectional communication, it is not necessary. To obtain the maximum coverage area, it is well known that the hexagon configuration is the ideal distribution, where the angle presented on each vertex is equal to 2
π
/
3, but it is valid for circles with equal radius and where there is not a neighbor circle covering each node. Nevertheless, for our case, we have a set of circles with different radius and where each node is covered by at least a neighbor circle.Now, to find the total area of Figure1, first find the area of 10 independent circles A
10
C given by(10)
A
10
C
=
10
π
r
2
,and then use the intersection between two circles denoted as A
i
2
C, [60].(11)
A
i
2
C
=
2
r
2
arccos
⁡
d
2
r
-
1
2
d
4
r
2
-
d
2
,where d is the distance between the centers of the two circles. Assume r
1
=
r
2
=
r
3
=
r, d
12
=
d
13
=
r; therefore d
23
=
r
2. Observe that Figure 2 shows the variables of this equation where δ is the width of the intersection A
N
2
∩
N
3 and δ
=
2
r
-
D. Now assuming an intersection with d
=
r, the intersection area A
N
1
∩
N
2 (A
0 and A
2) or A
N
1
∩
N
3 (A
0 and A
3) [60],(12)
A
i
2
C
=
2
r
2
arccos
⁡
1
2
-
1
2
r
2
3
.The area of intersectionA
N
2
∩
N
3 (A
0 and A
1), denoted as A
i
2
C
′ is an intersection where d
=
d
23
=
r
2, [60],(13)
A
i
2
C
′
=
2
r
2
arccos
⁡
1
2
-
r
2
.Figure2 shows the intersection area between three circles denoted as A
0. This area is known as acircular triangle, which is a triangle with arc shaped sides (
c
1
,
c
2
,
c
3
). The area can be obtained using the radius and the length of the three arcs as shown in Figure 2. The area is given by the following equation [61]:(14)
A
0
=
1
4
κ
λ
ν
σ
+
⋯
+
∑
k
=
1
3
r
k
2
arcsin
⁡
c
k
2
r
k
-
c
k
4
4
r
k
2
-
c
k
2
,where κ
=
(
c
1
+
c
2
+
c
3
), λ
=
(
c
2
+
c
3
-
c
1
), ν
=
(
c
1
+
c
3
-
c
2
), σ
=
(
c
1
+
c
2
-
c
3
),(15)
c
1
2
=
2
r
2
-
d
2
2
+
2
r
4
-
3
r
2
d
2
2
+
d
4
4
-
⋯
-
d
r
2
-
d
2
4
-
d
r
2
2
-
d
2
4
,and c
1
=
c
2.The appendix shows how the equation forc
3 is obtained:(16)
c
3
=
-
r
2
+
r
3
2
.Therefore, the coverage area upper bound(
A
UB
) of ten wireless sensors as shown in Figure 1 is given by(17)
A
UB
=
A
10
C
-
9
A
i
2
C
-
2
A
i
2
C
′
+
2
A
0
.With the completion of this analysis, it is possible to obtain the coverage area upper bound, 1286.7 m2. In Section 5, the values obtained with the DE algorithm are compared to the bounds.


## 4. The Multiobjective Differential Evolution Algorithm (MODEA) for Wireless Ad Hoc Sensor Distribution

It is well-know that the DE algorithm [20] begins with an initial population of individuals and then iterates to build new populations until a good solution is found. In DE an individual is a vector of the dimension of the problem D. The individuals characterize specific solutions to the problem under study. In this paper, the vector dimension contains the coordinates of the sensor nodes (
x
,
y
) followed by their radii values. Considering that there is not information with respect to the optimal solution, the initial population is built in random manner. DE makes repeated cycles of recombination and selection to move the population in the direction of the vicinity of a global optimum. Probability operators (crossing and mutation) are used to each individual in a population to create new individuals (children). The new individuals have some of the features of their ancestors. The ancestors are retained or removed by selection. The term generation is applied to designate the conversion of all individuals into new ones. In other words, to move from one population to another.The DE algorithm iterates for a limited number of generations,G. It is important to mention that DE has three key control parameters: the mutation constant M, which controls the mutation strength, the recombination constant C
r, and the population size N
p. The parameters M and C
r take values in the interval (
0
,
1
). During the course of the execution process, the user establishes the population size N
p. At each generation, all individuals in the population are evaluated in turn; in DE’s literature, the individual being evaluated is named the target vector. Three other individuals are randomly selected from the population and are mixed with each other: this operation is known as mutation and generates a mutant individual vector. The mutant individual vector is then mixed with the current target vector by an operator named recombination: the result of this recombination process is a vector named the trial vector.Finally, the selection operator is used. If the trial vector improves the objective function then it is accepted and replaces the current target vector in the new population that is being built. Else, it is rejected and the current target vector passes on to the next generation; in this situation the trial vector is not kept.The following is a description of the operators utilized in the DE algorithm that obtains the most promising region in the search space.


### 4.1. Objective Functions

In this research work, the DE algorithm seeks to achieve a balance between the maximal effective coverage rateA
c
o
v and the minimum sensor power communication f
2
(
x
)
=
E
c
s
d. To translate the network coverage rate into minimal functions, the opposite effect of the coverage rate is used. Thus, the network effective coverage rate is then defined by(18)
m
i
n
f
1
x
=
1
-
A
c
o
v
,and the minimum network energy communication is obtained by(19)
m
i
n
f
2
x
=
μ
∑
i
=
1
z
r
i
2
.The values ofmin
⁡
f
1
x and min
⁡
f
2
x are part of the fitness function for measuring the result. A linear combination of the objective functions transforms the original multiobjective function into a single-objective function as follows:(20)
m
i
n
∑
k
=
1
K
w
k
f
k
x
where
w
k
≥
0
;
∑
k
=
1
K
w
k
=
1
,where w
k are weight coefficients expressing the relative importance of each objective function and k is the number of objective functions that form the total objective function f.


### 4.2. The Fitness Function

The fitness function is given by(21)
f
x
=
w
1
f
1
x
+
w
2
n
2
f
2
x
,here w
1 and w
2 represent weight coefficients and n
2 is the normalization coefficient of f
2
(
x
). Note that f
1
(
x
) is already a normalized function (18) due to the fact that it takes only values between 0 to 1. To normalize the second term, it is necessary to use the following equation:(22)
n
2
=
1
μ
z
r
max
⁡
2
,where r
max
⁡ is the maximum sensor radius in meters (m).Considerw
2
=
1
-
w
1; therefore if w
1
=
1, w
2
=
0, then the fitness function optimizes the network effective coverage rate. Conversely if w
1
=
0, w
2
=
1, then the fitness function optimizes the energy consumption of signal detection. The normalized terms of (21) make it possible to get the same order of magnitude. The overall value of the fitness function is in the interval [
0,1
]. Obviously, the smaller the value of f
(
x
), the better the node location distribution and the lower the power communication consumption as well.


### 4.3. The Mutation Operator

For each target vectorx
i, i
=
1
,
…
,
N
p, the mutant individual m
i is created with the following equation [23]:(23)
m
i
=
x
r
1
+
M
x
r
2
-
x
r
3
,where x
r
1
,
x
r
2
,
x
r
3
∈
{
1
,
…
,
N
p
}: x
r
1
≠
x
r
2
≠
x
r
3
≠
x
i. Here, x
r
1, x
r
2, and x
r
3 are three random individuals from the population, mutually different and also different from the current target vector x
i, and M is a scaling factor named the mutation constant which must be M
>
0. The mutation operator is utilized to manage the magnitude of the difference between two individuals. This operator manages the tradeoff among exploitation and exploration on the search process. This operator is the one guiding the convergence of the algorithm. This version is known as DE/rand/1 version. Aside, there is another version like the one shown in [20, 22, 62](24)
m
i
=
x
best
+
M
x
r
1
-
x
r
1
,where the best vector among the population is chosen instead of obtaining it randomly. Expression stated in (24) is known as DE/best/1 [20, 22, 62].


### 4.4. The Recombination Operator

The recombination operator is applied to increment the diversity in the mutation process. This operator is the final step in the creation of the trial vector. To create the trial vector, the mutant individual is combined with the current target vector. In particular, for each componentj, where j
=
{
1,2
,
…
,
D
}, of the mutant individual, a random number rand in the interval [
0,1
] is selected. Then, the recombination constant C
r and rand are compared in order to check if rand
<
C
r. Equation (25) briefly shows that if the aforementioned condition is false, the jth element of the target vector is selected as the jth element of the trial vector. Otherwise the jth element of the mutant individual is selected as the jth element of the trial vector [23].(25)
t
i
,
j
=
m
i
,
j
if rand
<
C
r
∀
j
x
i
,
j
otherwise
.The reader is warned that a large value forC
r helps to avoid the cancelation of the mutation operation. Otherwise, C
r would become useless in its application on (25).


### 4.5. Application of the Prim–Dijkstra Algorithm

The nodes’ locations are validated considering the distance communication constraint. The communication range distance equal to the sensor coverage radius is used. To satisfy this constraint, the Prim–Dijkstra algorithm is applied [51]. The input to the algorithm is a root node from the set of nodes. This root node may act as the information concentrator and is chosen arbitrarily by the network designer. An external controller starts the algorithm and the algorithm takes action based on each actual position of all nodes. The Prim algorithm [63] determines the minimum spanning tree (MST) whereas the Dijkstra algorithm [64] obtains a star topology. Prim–Dijkstra [51, 52] uses the location of the sensor nodes and obtains a topology that is a mixture of MST and a star topology. As mentioned before, information about the shortest sensor mobility is determined with the Hungarian algorithm [53] finding the minimum distance between the initial and the final node positions.


### 4.6. The Selection Operator

The last step of the algorithm is the application of the selection operator, where the fitness computed with the trial vectort
i is compared to the fitness computed with the target vector x
i. In a simplified way, (26) summarizes the aforementioned statement, where t
i is chosen if its computed fitness is lower than the fitness computed on x
i and vice versa.(26)
pop
i
=
t
i
if
f
t
i
<
f
x
i
x
i
otherwise
.Here,pop
i is the population of the next generation that changes by accepting or rejecting new individuals. The global best individual is retained at the end of each generation, to keep track of the best solution obtained when DEA is executed.


### 4.7. TheRandom-
M Mutation Parameter

The parameterM is responsible for the exploration and exploitation of the solution spaces. To fix the problem of stagnation for small values of M, the random-
M parameter is added to (23). This parameter consists of a random number rand that multiplies the constant M at each evaluation, [22, 65]. Equation (27) shows how the main operator changes with this addition:(27)
m
i
=
x
r
1
+
rand
M
x
r
2
-
x
r
3
,where rand is a random number in the range of (
0
<
rand
<
1
) that changes during the evolution process. By multiplying M by rand, M modifies its value. In this way, rand helps DEA to have a strong reduction of stagnation. Thus, it is also possible to achieve an improved convergence speed, as presented in Section 5. The same approach may be applied to (24) as shown in(28)
m
i
=
x
best
+
rand
M
x
r
1
-
x
r
2
.


### 4.8. Pseudocode for MODEA in a WAHSN

Employing these considerations, here the pseudocode for the MODEA is presented. The algorithm takes the initial parameters of DE, performs the mutation and recombination, validates the coordinates(
x
,
y
) and the radius values, and, if necessary, updates the positions of some nodes. Thereafter, the links are created for each node, proceeding to form a tree, and in the case of nodes not connected to the tree, their positions and radii are updated. After a tree is obtained, the solution may be selected from the best trees generated, based on the best fitness value. The algorithm is considered and denoted asMODEA and also is summarized in pseudocode Algorithm 1. The details of the pseudocode are listed as follows:(1)
MODEA starts with the following parameters:M, C
r, N
p, G.
(2)
Each individual of population starts as follows:Pop
i
=
x
i
,
1
,
…
,
x
i
,
z; y
i
,
1
,
…
,
y
i
,
z; r
i
,
1
,
…
,
r
i
,
z and Pop
initial
=
Pop
1. Each r
i
,
j
=
r
max
⁡.
(3)
Validatet
i based on coordinates (
x
,
y
) and r for each member of t
i is performed according to the boundaries, r
max
⁡ and r
min
⁡. If r
>
r
max
⁡ or r
min
⁡
>
r, (30) is applied to regenerate r. If (
x
,
y
) are outside the boundaries, (
x
,
y
) are regenerated.
(4)
The Hungarian algorithm receivesPop
best (the best result obtained from final population at the end of MODEA) and Pop
initial to determine the final position (
e
) of the sensors regarding the initial positions (
i
).
(5)
The MST is formed by using central node(
cnode
=
5
), α
=
0, and the distance to generate a link between the nodes (
d
(
N
i
,
N
j
)
,
i
≠
j
) as (29)
d
N
i
,
N
j
=
x
j
-
x
i
2
+
y
j
-
y
i
2
.
Ifd
(
N
i
,
N
j
)
>
min
⁡
(
r
i
,
r
j
) or if there is a forbidden zone between the nodes, the link does not exist.
(6)
For each generationg
∈
{
1
,
…
,
G
}, all the individuals of population are updated according to selection operator.Algorithm 1:MODEA applied to WAHSN.
(1) procedure MODEA
(2) Set the control parameters for MODEA;
(3) Create initial population;
(4) Evaluate fitness, area and energy of each member;
(5)
for  g
=
1
t
o
G  do
(6)
for  i
=
1
t
o
N
p  do
(7) Select from Pop
i (see version: -R (Eq. (23)), -RM (Eq. (27)), -B (Eq. (24)), -BM (Eq. (28));
(8) Obtain mutation m
i (see previous chosen version);
(9) Apply recombination to obtain t
i (Eq. (25));
(10) Validate t
i according to preliminary bounds;
(11) Update (
x
,
y
) and radius (Eq. (30)) if needed;
(12)
while a tree is not obtained do
(13) Validate t
i;
(14) Update (
x
,
y
) and radius (Eq. (30)) if needed;
(15) Apply MST Prim-Dijkstra to array of links;
(16)
if some nodes are not connected then
(17) Update position and radius (Eq. (30)) of unlinked nodes;
(18)
else nodes are connected
(19) Tree has been built;
(20)
end if
(21)
end while
(22) Apply selection operator (Eq. (26));
(23)
end for
(24)  Pop
best solution is obtained for fitness, area and energy;
(25)
end for
(26) Apply Hungarian algorithm to Pop
best regarding to Pop
initial;
(27) end procedureFor simplification purposes, each MODEA version will be treated as follows for the next sections of this manuscript:MODEA rand (23) ↣ MODEA-R,
MODEA rand (withrandom-
M) (27) ↣ MODEA-RM,
MODEA best (24) ↣ MODEA-B,
MODEA best (withrandom-
M) (28) ↣ MODEA-BM.Figure3 shows the parameter s
c
a
l
e which scales the radius of the current node to separate it from the boundaries of the forbidden zone (see nodes N
1 and N
7 with their respective radii r
N
1 and r
N
7) and the limits of the area of interest. Even when N
3 and N
5 are close to each other, if there is a forbidden area between them, these nodes must use N
4 as the communication node. Throughout these restrictions, the nodes are separated while maintaining the MST. To separate the nodes from the main contour area (
L
×
H
), r
min
⁡ is used instead as a reference.Figure 3
Forbidden zone.The MODEA (all rand and best versions and their correspondingrandom-
M versions) adjusts the radius value according to its rules and the given restrictions. The algorithm uses (30) to generate the radius adjustment r
adj when validating t
i. In this algorithm, the radius of each population member starts at its maximum value; as a result, the average radius at the end of the generations is a value above the minimum radius.(30)
r
adj
=
r
min
⁡
+
rand
r
max
⁡
-
r
min
⁡
.


## 4.1. Objective Functions

In this research work, the DE algorithm seeks to achieve a balance between the maximal effective coverage rateA
c
o
v and the minimum sensor power communication f
2
(
x
)
=
E
c
s
d. To translate the network coverage rate into minimal functions, the opposite effect of the coverage rate is used. Thus, the network effective coverage rate is then defined by(18)
m
i
n
f
1
x
=
1
-
A
c
o
v
,and the minimum network energy communication is obtained by(19)
m
i
n
f
2
x
=
μ
∑
i
=
1
z
r
i
2
.The values ofmin
⁡
f
1
x and min
⁡
f
2
x are part of the fitness function for measuring the result. A linear combination of the objective functions transforms the original multiobjective function into a single-objective function as follows:(20)
m
i
n
∑
k
=
1
K
w
k
f
k
x
where
w
k
≥
0
;
∑
k
=
1
K
w
k
=
1
,where w
k are weight coefficients expressing the relative importance of each objective function and k is the number of objective functions that form the total objective function f.


## 4.2. The Fitness Function

The fitness function is given by(21)
f
x
=
w
1
f
1
x
+
w
2
n
2
f
2
x
,here w
1 and w
2 represent weight coefficients and n
2 is the normalization coefficient of f
2
(
x
). Note that f
1
(
x
) is already a normalized function (18) due to the fact that it takes only values between 0 to 1. To normalize the second term, it is necessary to use the following equation:(22)
n
2
=
1
μ
z
r
max
⁡
2
,where r
max
⁡ is the maximum sensor radius in meters (m).Considerw
2
=
1
-
w
1; therefore if w
1
=
1, w
2
=
0, then the fitness function optimizes the network effective coverage rate. Conversely if w
1
=
0, w
2
=
1, then the fitness function optimizes the energy consumption of signal detection. The normalized terms of (21) make it possible to get the same order of magnitude. The overall value of the fitness function is in the interval [
0,1
]. Obviously, the smaller the value of f
(
x
), the better the node location distribution and the lower the power communication consumption as well.


## 4.3. The Mutation Operator

For each target vectorx
i, i
=
1
,
…
,
N
p, the mutant individual m
i is created with the following equation [23]:(23)
m
i
=
x
r
1
+
M
x
r
2
-
x
r
3
,where x
r
1
,
x
r
2
,
x
r
3
∈
{
1
,
…
,
N
p
}: x
r
1
≠
x
r
2
≠
x
r
3
≠
x
i. Here, x
r
1, x
r
2, and x
r
3 are three random individuals from the population, mutually different and also different from the current target vector x
i, and M is a scaling factor named the mutation constant which must be M
>
0. The mutation operator is utilized to manage the magnitude of the difference between two individuals. This operator manages the tradeoff among exploitation and exploration on the search process. This operator is the one guiding the convergence of the algorithm. This version is known as DE/rand/1 version. Aside, there is another version like the one shown in [20, 22, 62](24)
m
i
=
x
best
+
M
x
r
1
-
x
r
1
,where the best vector among the population is chosen instead of obtaining it randomly. Expression stated in (24) is known as DE/best/1 [20, 22, 62].


## 4.4. The Recombination Operator

The recombination operator is applied to increment the diversity in the mutation process. This operator is the final step in the creation of the trial vector. To create the trial vector, the mutant individual is combined with the current target vector. In particular, for each componentj, where j
=
{
1,2
,
…
,
D
}, of the mutant individual, a random number rand in the interval [
0,1
] is selected. Then, the recombination constant C
r and rand are compared in order to check if rand
<
C
r. Equation (25) briefly shows that if the aforementioned condition is false, the jth element of the target vector is selected as the jth element of the trial vector. Otherwise the jth element of the mutant individual is selected as the jth element of the trial vector [23].(25)
t
i
,
j
=
m
i
,
j
if rand
<
C
r
∀
j
x
i
,
j
otherwise
.The reader is warned that a large value forC
r helps to avoid the cancelation of the mutation operation. Otherwise, C
r would become useless in its application on (25).


## 4.5. Application of the Prim–Dijkstra Algorithm

The nodes’ locations are validated considering the distance communication constraint. The communication range distance equal to the sensor coverage radius is used. To satisfy this constraint, the Prim–Dijkstra algorithm is applied [51]. The input to the algorithm is a root node from the set of nodes. This root node may act as the information concentrator and is chosen arbitrarily by the network designer. An external controller starts the algorithm and the algorithm takes action based on each actual position of all nodes. The Prim algorithm [63] determines the minimum spanning tree (MST) whereas the Dijkstra algorithm [64] obtains a star topology. Prim–Dijkstra [51, 52] uses the location of the sensor nodes and obtains a topology that is a mixture of MST and a star topology. As mentioned before, information about the shortest sensor mobility is determined with the Hungarian algorithm [53] finding the minimum distance between the initial and the final node positions.


## 4.6. The Selection Operator

The last step of the algorithm is the application of the selection operator, where the fitness computed with the trial vectort
i is compared to the fitness computed with the target vector x
i. In a simplified way, (26) summarizes the aforementioned statement, where t
i is chosen if its computed fitness is lower than the fitness computed on x
i and vice versa.(26)
pop
i
=
t
i
if
f
t
i
<
f
x
i
x
i
otherwise
.Here,pop
i is the population of the next generation that changes by accepting or rejecting new individuals. The global best individual is retained at the end of each generation, to keep track of the best solution obtained when DEA is executed.


## 4.7. TheRandom-
M Mutation Parameter

The parameterM is responsible for the exploration and exploitation of the solution spaces. To fix the problem of stagnation for small values of M, the random-
M parameter is added to (23). This parameter consists of a random number rand that multiplies the constant M at each evaluation, [22, 65]. Equation (27) shows how the main operator changes with this addition:(27)
m
i
=
x
r
1
+
rand
M
x
r
2
-
x
r
3
,where rand is a random number in the range of (
0
<
rand
<
1
) that changes during the evolution process. By multiplying M by rand, M modifies its value. In this way, rand helps DEA to have a strong reduction of stagnation. Thus, it is also possible to achieve an improved convergence speed, as presented in Section 5. The same approach may be applied to (24) as shown in(28)
m
i
=
x
best
+
rand
M
x
r
1
-
x
r
2
.


## 4.8. Pseudocode for MODEA in a WAHSN

Employing these considerations, here the pseudocode for the MODEA is presented. The algorithm takes the initial parameters of DE, performs the mutation and recombination, validates the coordinates(
x
,
y
) and the radius values, and, if necessary, updates the positions of some nodes. Thereafter, the links are created for each node, proceeding to form a tree, and in the case of nodes not connected to the tree, their positions and radii are updated. After a tree is obtained, the solution may be selected from the best trees generated, based on the best fitness value. The algorithm is considered and denoted asMODEA and also is summarized in pseudocode Algorithm 1. The details of the pseudocode are listed as follows:(1)
MODEA starts with the following parameters:M, C
r, N
p, G.
(2)
Each individual of population starts as follows:Pop
i
=
x
i
,
1
,
…
,
x
i
,
z; y
i
,
1
,
…
,
y
i
,
z; r
i
,
1
,
…
,
r
i
,
z and Pop
initial
=
Pop
1. Each r
i
,
j
=
r
max
⁡.
(3)
Validatet
i based on coordinates (
x
,
y
) and r for each member of t
i is performed according to the boundaries, r
max
⁡ and r
min
⁡. If r
>
r
max
⁡ or r
min
⁡
>
r, (30) is applied to regenerate r. If (
x
,
y
) are outside the boundaries, (
x
,
y
) are regenerated.
(4)
The Hungarian algorithm receivesPop
best (the best result obtained from final population at the end of MODEA) and Pop
initial to determine the final position (
e
) of the sensors regarding the initial positions (
i
).
(5)
The MST is formed by using central node(
cnode
=
5
), α
=
0, and the distance to generate a link between the nodes (
d
(
N
i
,
N
j
)
,
i
≠
j
) as (29)
d
N
i
,
N
j
=
x
j
-
x
i
2
+
y
j
-
y
i
2
.
Ifd
(
N
i
,
N
j
)
>
min
⁡
(
r
i
,
r
j
) or if there is a forbidden zone between the nodes, the link does not exist.
(6)
For each generationg
∈
{
1
,
…
,
G
}, all the individuals of population are updated according to selection operator.Algorithm 1:MODEA applied to WAHSN.
(1) procedure MODEA
(2) Set the control parameters for MODEA;
(3) Create initial population;
(4) Evaluate fitness, area and energy of each member;
(5)
for  g
=
1
t
o
G  do
(6)
for  i
=
1
t
o
N
p  do
(7) Select from Pop
i (see version: -R (Eq. (23)), -RM (Eq. (27)), -B (Eq. (24)), -BM (Eq. (28));
(8) Obtain mutation m
i (see previous chosen version);
(9) Apply recombination to obtain t
i (Eq. (25));
(10) Validate t
i according to preliminary bounds;
(11) Update (
x
,
y
) and radius (Eq. (30)) if needed;
(12)
while a tree is not obtained do
(13) Validate t
i;
(14) Update (
x
,
y
) and radius (Eq. (30)) if needed;
(15) Apply MST Prim-Dijkstra to array of links;
(16)
if some nodes are not connected then
(17) Update position and radius (Eq. (30)) of unlinked nodes;
(18)
else nodes are connected
(19) Tree has been built;
(20)
end if
(21)
end while
(22) Apply selection operator (Eq. (26));
(23)
end for
(24)  Pop
best solution is obtained for fitness, area and energy;
(25)
end for
(26) Apply Hungarian algorithm to Pop
best regarding to Pop
initial;
(27) end procedureFor simplification purposes, each MODEA version will be treated as follows for the next sections of this manuscript:MODEA rand (23) ↣ MODEA-R,
MODEA rand (withrandom-
M) (27) ↣ MODEA-RM,
MODEA best (24) ↣ MODEA-B,
MODEA best (withrandom-
M) (28) ↣ MODEA-BM.Figure3 shows the parameter s
c
a
l
e which scales the radius of the current node to separate it from the boundaries of the forbidden zone (see nodes N
1 and N
7 with their respective radii r
N
1 and r
N
7) and the limits of the area of interest. Even when N
3 and N
5 are close to each other, if there is a forbidden area between them, these nodes must use N
4 as the communication node. Throughout these restrictions, the nodes are separated while maintaining the MST. To separate the nodes from the main contour area (
L
×
H
), r
min
⁡ is used instead as a reference.Figure 3
Forbidden zone.The MODEA (all rand and best versions and their correspondingrandom-
M versions) adjusts the radius value according to its rules and the given restrictions. The algorithm uses (30) to generate the radius adjustment r
adj when validating t
i. In this algorithm, the radius of each population member starts at its maximum value; as a result, the average radius at the end of the generations is a value above the minimum radius.(30)
r
adj
=
r
min
⁡
+
rand
r
max
⁡
-
r
min
⁡
.


## 5. Numerical Results and Discussion

The methodology followed in this manuscript was based on the one presented in [26]. Nevertheless, the treatment of the scenarios and constraints here presented were stated by following the convex configurations [35]. Compared to [26] and other similar works [34], the main differences are that the center of a circle should be inside in at least one of its neighbor circles, where all the circle centers must display a connected graph. The detailed rules are described in Section 4.8. This approach was adopted before testing more elaborated bioinspired techniques for future works, in order to have a baseline and then to determine the feasibility of MODEA with stricter constraints. A previous successful approach with the use of nonconvex constraints and obstacles can be seen in [32]. In future works, such elaborated bioinspired techniques will be tested (more details are available in the Conclusion).The algorithm was implemented in MATLAB to optimize the distribution of sensors. The effective sensor radius was assigned betweenr
min
⁡
=
6 and r
max
⁡
=
8 meters, except themultiple-bounded case, where r
min
⁡
=
4 m, r
max
⁡
=
6 m. Different shaped-variant target zones were also tested. The same starting random node distribution was implemented on each scenario, with the purpose of having fair performance comparisons and the computation of the corresponding averages, that is, a unique starting node distribution for squared areas, a unique starting node distribution for polygons, etc., where it is clear that all the starting node distributions are not equal among the analyzed scenarios.The control parameters were set asM
=
0.8, N
P
=
35, and C
r
=
0.9, where M and C
r were assigned taking the best reported performance for both parameters in the open literature [62]. Figure 4 shows the results of the fitness function against the number of generations ofMODEA-R, MODEA-RM, MODEA-B, andMODEA-BM. These tests are the average of 50 independent tests on a squared area of 40 m × 40 m, G
=
1000, with the maximum possible radius; that is, r
min
⁡
=
r
max
⁡
=
8 m. Note thatMODEA-BM outperformsMODEA-R,MODEA-RM, andMODEA-B obtaining the lowest fitness values. In this specific case, a value of w
1
=
1.0 is used to obtain a result near to the area with 10 nodes computed in Section 3.Figure 4
Fitness versus generations.Comparing the averages obtained among the four versions of MODEA shown in Figure4, the authors of this manuscript decided to use MODEA-BM because the average obtained on all the 50 tested cases is the best. The best case for MODEA-BM among these 50 tests was obtained in the test 23
/
50, where the notation is denoted as n
u
m
t
e
s
t
/
n
u
m
f
u
l
l
t
e
s
t
s. This choice was taken even when there is a best result obtained with MODEA-B. Even so, the previous mentioned results are consistent with those presented in [34], where MODEA-B became the best possible option by considering the classical MODEA variants presented in [20, 22].Figure5 shows the initial position of 10 sensors randomly distributed. The sensor nodes are identified as N
1
,
N
2
,
…
,
N
10, and the circles are the sensor ranges of the sensor nodes. As explained before, this starting node distribution was implemented for all the MODEA versions for all the 50 tests applied on this squared scenario.Figure 5
Initial random distribution of10 sensor nodes.Figure6 shows the optimized sensor distribution using the initial sensor positions of Figure 5. Also, the wireless communication links between the nodes are shown. The presence of a link between two nodes in the network depends on the relative distance between them (lower than the minimum radius between two nodes).Figure 6
Optimized distribution of10 sensors.Figure7 shows the initial and final position of the sensors nodes, identified with the subindexes (
i
) and (
e
), respectively. Note that the final node positions are at the shortest distance from the initial node positions. For mobile sensors, this information about mobility is useful to globally minimize sensor path distance. A minimum distance matching algorithm after MODEA-BM is used to obtain the minimum global traveled distance between the initial and the final node positions through the Hungarian algorithm, [53].Figure 7
Shortest distance from initial (i) to final (e) node positions generated by the Hungarian algorithm.Table2 shows a summary of the results obtained using the lower energy and the upper area bound equations presented in Section 3. Also, the results obtained with the MODEA-BM are shown for comparison purposes (case 23/50). The results obtained with the use of MODEA-BM are within 99.05% of the theoretical bounds (1274.6 m2/1286.7 m2). With the use of the random-
M parameter, the MODEA-BM algorithm has a high convergence speed and stagnation is avoided, as shown in (27). The upper bounded area is 80.41% of the total area to be covered (1286.7 m2/1600 m2); the computed area with MODEA-BM is 1274.6 m2 which represents 79.66% of the total area to be covered (1274.6 m2/1600 m2).Table 2
Bounds: theoretical model (TM) and MODEA-BM results.
10 Nodes Bounds
Area TM (m
2)
Energy TM (mW)
Area (m
2) MODEA Best
Energy (mW) MODEA Best
Lower
113.09
1.8
-
1.8
Upper
1286.7
3.2
1274.6
3.2Now, in Figure8 an analysis of the weights w
1 and w
2 of (30) and how these values affect the optimization of energy and coverage area is presented for MODEA-BM. It was done by following the methodology presented in [65, 66]. Here, w
1 varies from 0 to 1 in increments of 0.1; meanwhile the value of w
2 varies from 1 to 0 so that w
2
=
1
-
w
1. The fixed radii curve (
∗
) shows the bounds comparison when the values of radii between r
max
⁡ and r
min
⁡ are equal. The variable radii curve (
▵
) shows the behavior of bounds comparison when the value of radii varies between r
min
⁡
=
6 m and r
max
⁡
=
8 m. Here, the observed trend is to maximize the coverage area; nevertheless the restrictions help to reduce the radii of the nodes. It was observed that values of w
1
=
0.6 and w
2
=
0.4 are able to produce results in which the covered area is maximized and, meanwhile, the energy is minimized. This is because those values are near to the case where r
min
⁡
=
r
max
⁡
=
7 m for the fixed scenario. The results presented here are the average of 50 independent tests of G
=
1000 for each point at each scenario. The tests to obtain the point w
1
=
1.0, w
2
=
0.0 were performed independently of those used to compute the output for Figure 6.Figure 8
Bounds comparison of10 nodes, varying w
1 and w
2.


### 5.1. Different Scenarios of Testing

Now the results of the algorithm MODEA-BM parameter applied to the sensor distribution problem in different shaped-bounded areas are presented. The number of nodes is obtained by incrementing the number of sensors depending on the coverage area. Usingw
1
=
0.6, w
2
=
0.4, and G
=
1000, MODEA-BM was able to find good sensor distributions. Formultiple-bounded case, G
=
2500. Restrictions were tuned and set to obtain a suboptimal result for each of the following scenarios. Figures 11–16 were obtained by MATLAB with the command i
n
p
o
l
y
g
o
n as described in the corresponding subsections. The best minimum fitness was considered for all the presented cases.


#### 5.1.1. Scenario 1. Ellipse

To form the ellipse area shown in Figure9, the parameters are h
A
=
h
B
=
25, k
A
=
k
B
=
25, r
A
=
15, r
B
=
25, a
A
=
0.8, a
B
=
1.0, b
A
=
0.6, b
B
=
0.9, where A is the inner ellipse and B is the external ellipse, displayed into an area of 50 m × 50 m. The corresponding equations are listed as follows:(31)
x
-
h
A
2
a
A
2
+
y
-
k
A
2
b
A
2
=
r
A
2
,
x
-
h
B
2
a
B
2
+
y
-
k
B
2
b
B
2
=
r
B
2
.Figure 9
Area formed with two ellipses.It is observed in Figure9 that the circles follow the contour of the given ellipses, maximizing the coverage area. The best minimum fitness was obtained for the test 9
/
50.Figure10 shows the total energy consumption of the best curved-bounded scenario. The covered area is more than 90
% while the energy is below 4 units. The fitness curve indicates how both parameters are evolving to be optimized. After 700 generations, the fitness curve becomes stable, maintaining the area/energy limit values also stable.Figure 10
Results for (a) fitness, area, and (b) energy consumption on the scenario with two ellipses.
(a)
(b)Figure 11
(a) Triangle and (b) pentagon scenarios, best output.
(a)
(b)Figure 12
(a) Triangle and (b) pentagon scenarios, fitness and area curve.
(a)
(b)Figure 13
(a) Triangle and (b) pentagon scenarios, energy curve.
(a)
(b)Figure 14
Irregular area outside an amorphous zone.Figure 15
(a) Area, fitness, and (b) energy curves for amorphous figure.
(a)
(b)Figure 16
Multiple figures scenario.The line resolution between two nodes was left as 0.01. The complete circle contour was considered to determine the separation of the boundaries. That is, the angles to compute the radius circle were set as 0 : 0.01 : 360.


#### 5.1.2. Regular Polygons, External Area

MODEA-BM is applied to the pentagon shown in Figure11(b) and also to the triangle shown in Figure 11(a). The figures here exposed are obtained using the expression L
T
=
linspace
0,2
π
,
points and the equations given below:(32)
x
=
A
cos
⁡
L
T
+
π
2
+
U
,
y
=
A
sin
⁡
L
T
+
π
2
+
V
,where points
=
4, A
=
15, U
=
20, V
=
18 in Figure 11(a) and points
=
6, A
=
10, U
=
V
=
20 in Figure 11(b). Vectors x and y define the vertices of the polygon. Both polygons are displayed into an area of 40 m × 40 m.Figure12 shows the area and fitness obtained for both scenarios. While for triangle the fitness converges before G
=
400, for pentagon the fitness delays to converge before G
=
900. For both cases, the coverage area is greater than 90
%.Figure13 shows the energy obtained for both scenarios. While for triangle the energy becomes stable after G
=
400 with 4 units, for the pentagon the energy holds the same after G
=
800 with 3.6 units.The best minimum fitness was obtained as41
/
50 for triangle and 45
/
50 for pentagon. To speed up the algorithm, each circle was sampled in angles as 0 : 45 : 360 to compute the radius. The line resolution between two nodes was left as 0.001 in order to detect forbidden crosses on the shaded area.


#### 5.1.3. Irregular External Area

In this scenario, MODEA-BM is applied to the irregular area shown in Figure14, which is obtained with (33)
x
=
2
H
x
2
y
=
2
H
y
2
+
1
,where the user can choose the values of vectors x and y to generate the irregular polygon of Figure 14. This scenario is presented to show how the algorithm is able to work with true irregular areas. Figure 14 is formed by two linked irregular polygons. The figure is displayed into an area of 40 m × 40 m.As shown in Figure14, the algorithm prevents that links of the MST from crossing the small polygon, also keeping a distance between the nodes and the entire polygon. With 17 nodes, it is possible to cover more than 90% of the amorphous figure (Figure 15(a)) while the energy is below 4 units (Figure 15(b)). The best minimum fitness was obtained as 10
/
50.To speed up the algorithm, each circle was sampled in angles as 0 : 90 : 360 to compute the radius. The line resolution between two nodes was left as 0.001 to check if a link crosses forbidden areas, specially the small triangle of the scenario.


#### 5.1.4. Multiple-Bounded Area

A multiple-bounded area is shown in Figure16 with a different radii values, r
min
⁡
=
4 m, r
max
⁡
=
6 m, for speeding up the computation of results. The number of tests here are equal to 20. All the polygons are displayed into an area of 40 m × 40 m. This case shows how the algorithm can be adapted to cover an area with multiple bounds (forbidden areas). These bounds represent a triangle, pentagon, star, and two rectangles. For instance, to get the star figure, the following parameters: v
=
12, t
=
(
-
1
/
4
:
1
/
v
:
3
/
4
)
∗
2
∗
π, r
1
=
10, r
2
=
5, p
=
(
0
:
v
), r
=
(
r
1
+
r
2
)
/
2
+
(
r
1
-
r
2
)
/
2
∗
(
-
1
)
p and (34) are used(34)
x
=
r
cos
⁡
t
+
25
,
y
=
r
sin
⁡
t
+
23.5
.Here, the algorithm is able to arrange the obtained MST as a contour to the given bounds, preventing MST links from crossing forbidden areas. This effect is seen in the case of the star, where the links of the nodes do not cross the peaks of the star. A similar effect is seen for the rectangles, where the nodes forming the circle go nearly in parallel with 24 nodes. This property is maintained even in the presence of the thinnest region that connects the star and the triangle, where there is no link that crosses it. Thus, it is possible to cover more than 90% of the area of Figure16 (see Figure 17(a)) with less than 3.5 units of energy (see Figure 17(b)).Figure 17
(a) Area, fitness, and (b) energy curves for multiple figures.
(a)
(b)The best minimum fitness was obtained as2
/
20. To speed up the algorithm, each circle was sampled in angles as 0 : 30 : 360 to compute the radius and the line between two nodes was sampled with 0.1 of resolution. When constructing the final MST, that line is sampled with 0.001 of resolution to detect if it crosses forbidden zones. The s
c
a
l
e parameter guarantees that all the cases do not have issues with the line resolution when finishing MODEA-BM.


#### 5.1.5. Summary of the Results

Table3 shows a summary of the average area results obtained from the different figures comparing them with the maximum area to be covered. The results obtained using MODEA-BM parameter are very close to the area to be covered. On each case, 50 tests were made to obtain their mean and standard deviation, except for the multiple case, where only 20 tests were done. The energy for all the cases remains below 4 units, while the coverage area is greater than 90
% for the best solutions obtained. The computation of the average and standard deviation on the area parameter shows that theirregular external area case remains greater than 90
% with the lowest standard deviation, which is consistent with the fitness value (
34.98
%
). In contrast, themultiple case shows the worst average (
77.35
%
) and the largest standard deviation (135.10) and also presents the largest fitness value (
46.17
%
) with the largest standard deviation (8.00). Even so, formultiple case, MODEA-BM is able to obtain results where the covered area is greater than 90
%.Table 3
Area to cover and area covered by MODEA-BM, plus energy consumption. Averages, standard deviation, and best cases, where BC means best case,μ
^ is the average, and σ is the standard deviation.
Figure Number
Data
Fitness Percent %
Fitnessσ
Area (m2) MODEA-BM
Area (m2) to cover
Area Percentage %
Areaσ
Energy (mW)
Energyσ
Scale parameter
Number of Nodes
Figure9
Stats(
μ
^
,
σ
)
42.25
5.04
1151.63
1427.72
80.66
124.16
3.67
0.19
0.500
15
BC9
/
50
36.00
-
1349.12
94.49
-
3.92
-
Figure11(a)
Stats(
μ
^
,
σ
)
37.30
1.97
1120.02
1306.40
85.73
59.75
3.67
0.13
0.500
16
BC41
/
50
34.36
-
1235.63
94.58
-
3.98
-
Figure11(b)
Stats(
μ
^
,
σ
)
39.76
4.66
1136.88
1362.71
83.42
103.41
3.57
0.18
0.200
15
BC45
/
50
34.86
-
1260.21
92.47
-
3.64
-
Figure14
Stats(
μ
^
,
σ
)
34.98
1.80
1159.72
1288.5
90.00
53.79
3.94
0.15
0.200
17
BC10
/
50
31.23
-
1235.06
95.85
-
3.90
-
Figure16
Stats(
μ
^
,
σ
)
46.17
8.00
871.15
1126.21
77.35
135.10
3.51
0.13
0.400
24
BC2
/
20
36.78
-
1029.67
91.42
-
3.41
-Table4 shows the comparison of the DEA here proposed to well-known multiobjective optimization algorithms such as NSGA-II and MOEA/D. The authors modified the generic versions of both algorithms, where the corresponding source codes are available in [67]. The default configuration parameters were left unmodified except N
p
=
35. Here, only the base case scenario was tested. For the sake of consistency and fairness, the same 50 tests were done for the following presented cases. For MODEA, the radii-variable coordinate obtained with w
1
=
0.6 and w
2
=
0.4 was included for the comparison (see Figure 8). For the other multiobjective algorithms, four different scenarios were tested. Here, g
1
(
x
) is the nonnormalized version of f
1
(
x
) and g
2
(
x
) is the nonnormalized energy version of f
2
(
x
). Additionally, A
max
⁡ is the area to be covered and E
max
⁡ is given by (22). These variants are described as follows:(i)
Version-I (V-I): the coordinates of the algorithm are tested without normalizing them. That means(35)
g
x
=
g
1
x
g
2
x
.
(ii)
Version-II (V-II): the coordinates of the algorithm are tested, but in a normalized way as(36)
g
x
=
g
1
x
A
max
⁡
g
2
x
E
max
⁡
.
(iii)
Version-III (V-III): each normalized coordinate is weighted by 0.5 as(37)
g
x
=
0.5
g
1
x
A
max
⁡
0.5
g
2
x
E
max
⁡
.
(iv)
Version-IV (V-IV): the normalized area(
g
1
(
x
)
) is weighted by 0.6. Meanwhile, the normalized energy (
g
2
(
x
)
) is weighted by 0.4 as(38)
g
x
=
0.6
g
1
x
A
max
⁡
0.4
g
2
x
E
max
⁡
.Table 4
Comparison of DEA algorithm with some known multiobjective algorithms. Average on 50 tests.
Algorithm
Area (m
2) mean
Energy (mW) mean
MODEA (ours) (w
1
=
0.6, w
2
=
0.4)
981.9858
2.5266
NSGA-II V-I
1028.5674
2.8120
NSGA-II V-II
667.3309
2.1155
NSGA-II V-III
721.3496
1.9494
NSGA-II V-IV
875.0040
2.3059
MOEA/D V-I
868.0113
2.9287
MOEA/D V-II
708.6827
1.9229
MOEA/D V-III
648.9909
2.0030
MOEA/D V-IV
809.0555
2.3831According to the results shown in Table4, MODEA presents the best average performance among all the cases, with exception of NSGA-II version V-I. NSGA-II V-I obtains a coverage area 4.53% larger than MODEA; however the energy is 10.15% larger. It is shown that MODEA is more efficient in terms of the energy consumption; meanwhile NSGA-II increases the coverage area but raises the energy consumption. The rest of the multiobjective algorithms versions do not reach a similar area to that obtained by MODEA.


## 5.1. Different Scenarios of Testing

Now the results of the algorithm MODEA-BM parameter applied to the sensor distribution problem in different shaped-bounded areas are presented. The number of nodes is obtained by incrementing the number of sensors depending on the coverage area. Usingw
1
=
0.6, w
2
=
0.4, and G
=
1000, MODEA-BM was able to find good sensor distributions. Formultiple-bounded case, G
=
2500. Restrictions were tuned and set to obtain a suboptimal result for each of the following scenarios. Figures 11–16 were obtained by MATLAB with the command i
n
p
o
l
y
g
o
n as described in the corresponding subsections. The best minimum fitness was considered for all the presented cases.


### 5.1.1. Scenario 1. Ellipse

To form the ellipse area shown in Figure9, the parameters are h
A
=
h
B
=
25, k
A
=
k
B
=
25, r
A
=
15, r
B
=
25, a
A
=
0.8, a
B
=
1.0, b
A
=
0.6, b
B
=
0.9, where A is the inner ellipse and B is the external ellipse, displayed into an area of 50 m × 50 m. The corresponding equations are listed as follows:(31)
x
-
h
A
2
a
A
2
+
y
-
k
A
2
b
A
2
=
r
A
2
,
x
-
h
B
2
a
B
2
+
y
-
k
B
2
b
B
2
=
r
B
2
.Figure 9
Area formed with two ellipses.It is observed in Figure9 that the circles follow the contour of the given ellipses, maximizing the coverage area. The best minimum fitness was obtained for the test 9
/
50.Figure10 shows the total energy consumption of the best curved-bounded scenario. The covered area is more than 90
% while the energy is below 4 units. The fitness curve indicates how both parameters are evolving to be optimized. After 700 generations, the fitness curve becomes stable, maintaining the area/energy limit values also stable.Figure 10
Results for (a) fitness, area, and (b) energy consumption on the scenario with two ellipses.
(a)
(b)Figure 11
(a) Triangle and (b) pentagon scenarios, best output.
(a)
(b)Figure 12
(a) Triangle and (b) pentagon scenarios, fitness and area curve.
(a)
(b)Figure 13
(a) Triangle and (b) pentagon scenarios, energy curve.
(a)
(b)Figure 14
Irregular area outside an amorphous zone.Figure 15
(a) Area, fitness, and (b) energy curves for amorphous figure.
(a)
(b)Figure 16
Multiple figures scenario.The line resolution between two nodes was left as 0.01. The complete circle contour was considered to determine the separation of the boundaries. That is, the angles to compute the radius circle were set as 0 : 0.01 : 360.


### 5.1.2. Regular Polygons, External Area

MODEA-BM is applied to the pentagon shown in Figure11(b) and also to the triangle shown in Figure 11(a). The figures here exposed are obtained using the expression L
T
=
linspace
0,2
π
,
points and the equations given below:(32)
x
=
A
cos
⁡
L
T
+
π
2
+
U
,
y
=
A
sin
⁡
L
T
+
π
2
+
V
,where points
=
4, A
=
15, U
=
20, V
=
18 in Figure 11(a) and points
=
6, A
=
10, U
=
V
=
20 in Figure 11(b). Vectors x and y define the vertices of the polygon. Both polygons are displayed into an area of 40 m × 40 m.Figure12 shows the area and fitness obtained for both scenarios. While for triangle the fitness converges before G
=
400, for pentagon the fitness delays to converge before G
=
900. For both cases, the coverage area is greater than 90
%.Figure13 shows the energy obtained for both scenarios. While for triangle the energy becomes stable after G
=
400 with 4 units, for the pentagon the energy holds the same after G
=
800 with 3.6 units.The best minimum fitness was obtained as41
/
50 for triangle and 45
/
50 for pentagon. To speed up the algorithm, each circle was sampled in angles as 0 : 45 : 360 to compute the radius. The line resolution between two nodes was left as 0.001 in order to detect forbidden crosses on the shaded area.


### 5.1.3. Irregular External Area

In this scenario, MODEA-BM is applied to the irregular area shown in Figure14, which is obtained with (33)
x
=
2
H
x
2
y
=
2
H
y
2
+
1
,where the user can choose the values of vectors x and y to generate the irregular polygon of Figure 14. This scenario is presented to show how the algorithm is able to work with true irregular areas. Figure 14 is formed by two linked irregular polygons. The figure is displayed into an area of 40 m × 40 m.As shown in Figure14, the algorithm prevents that links of the MST from crossing the small polygon, also keeping a distance between the nodes and the entire polygon. With 17 nodes, it is possible to cover more than 90% of the amorphous figure (Figure 15(a)) while the energy is below 4 units (Figure 15(b)). The best minimum fitness was obtained as 10
/
50.To speed up the algorithm, each circle was sampled in angles as 0 : 90 : 360 to compute the radius. The line resolution between two nodes was left as 0.001 to check if a link crosses forbidden areas, specially the small triangle of the scenario.


### 5.1.4. Multiple-Bounded Area

A multiple-bounded area is shown in Figure16 with a different radii values, r
min
⁡
=
4 m, r
max
⁡
=
6 m, for speeding up the computation of results. The number of tests here are equal to 20. All the polygons are displayed into an area of 40 m × 40 m. This case shows how the algorithm can be adapted to cover an area with multiple bounds (forbidden areas). These bounds represent a triangle, pentagon, star, and two rectangles. For instance, to get the star figure, the following parameters: v
=
12, t
=
(
-
1
/
4
:
1
/
v
:
3
/
4
)
∗
2
∗
π, r
1
=
10, r
2
=
5, p
=
(
0
:
v
), r
=
(
r
1
+
r
2
)
/
2
+
(
r
1
-
r
2
)
/
2
∗
(
-
1
)
p and (34) are used(34)
x
=
r
cos
⁡
t
+
25
,
y
=
r
sin
⁡
t
+
23.5
.Here, the algorithm is able to arrange the obtained MST as a contour to the given bounds, preventing MST links from crossing forbidden areas. This effect is seen in the case of the star, where the links of the nodes do not cross the peaks of the star. A similar effect is seen for the rectangles, where the nodes forming the circle go nearly in parallel with 24 nodes. This property is maintained even in the presence of the thinnest region that connects the star and the triangle, where there is no link that crosses it. Thus, it is possible to cover more than 90% of the area of Figure16 (see Figure 17(a)) with less than 3.5 units of energy (see Figure 17(b)).Figure 17
(a) Area, fitness, and (b) energy curves for multiple figures.
(a)
(b)The best minimum fitness was obtained as2
/
20. To speed up the algorithm, each circle was sampled in angles as 0 : 30 : 360 to compute the radius and the line between two nodes was sampled with 0.1 of resolution. When constructing the final MST, that line is sampled with 0.001 of resolution to detect if it crosses forbidden zones. The s
c
a
l
e parameter guarantees that all the cases do not have issues with the line resolution when finishing MODEA-BM.


### 5.1.5. Summary of the Results

Table3 shows a summary of the average area results obtained from the different figures comparing them with the maximum area to be covered. The results obtained using MODEA-BM parameter are very close to the area to be covered. On each case, 50 tests were made to obtain their mean and standard deviation, except for the multiple case, where only 20 tests were done. The energy for all the cases remains below 4 units, while the coverage area is greater than 90
% for the best solutions obtained. The computation of the average and standard deviation on the area parameter shows that theirregular external area case remains greater than 90
% with the lowest standard deviation, which is consistent with the fitness value (
34.98
%
). In contrast, themultiple case shows the worst average (
77.35
%
) and the largest standard deviation (135.10) and also presents the largest fitness value (
46.17
%
) with the largest standard deviation (8.00). Even so, formultiple case, MODEA-BM is able to obtain results where the covered area is greater than 90
%.Table 3
Area to cover and area covered by MODEA-BM, plus energy consumption. Averages, standard deviation, and best cases, where BC means best case,μ
^ is the average, and σ is the standard deviation.
Figure Number
Data
Fitness Percent %
Fitnessσ
Area (m2) MODEA-BM
Area (m2) to cover
Area Percentage %
Areaσ
Energy (mW)
Energyσ
Scale parameter
Number of Nodes
Figure9
Stats(
μ
^
,
σ
)
42.25
5.04
1151.63
1427.72
80.66
124.16
3.67
0.19
0.500
15
BC9
/
50
36.00
-
1349.12
94.49
-
3.92
-
Figure11(a)
Stats(
μ
^
,
σ
)
37.30
1.97
1120.02
1306.40
85.73
59.75
3.67
0.13
0.500
16
BC41
/
50
34.36
-
1235.63
94.58
-
3.98
-
Figure11(b)
Stats(
μ
^
,
σ
)
39.76
4.66
1136.88
1362.71
83.42
103.41
3.57
0.18
0.200
15
BC45
/
50
34.86
-
1260.21
92.47
-
3.64
-
Figure14
Stats(
μ
^
,
σ
)
34.98
1.80
1159.72
1288.5
90.00
53.79
3.94
0.15
0.200
17
BC10
/
50
31.23
-
1235.06
95.85
-
3.90
-
Figure16
Stats(
μ
^
,
σ
)
46.17
8.00
871.15
1126.21
77.35
135.10
3.51
0.13
0.400
24
BC2
/
20
36.78
-
1029.67
91.42
-
3.41
-Table4 shows the comparison of the DEA here proposed to well-known multiobjective optimization algorithms such as NSGA-II and MOEA/D. The authors modified the generic versions of both algorithms, where the corresponding source codes are available in [67]. The default configuration parameters were left unmodified except N
p
=
35. Here, only the base case scenario was tested. For the sake of consistency and fairness, the same 50 tests were done for the following presented cases. For MODEA, the radii-variable coordinate obtained with w
1
=
0.6 and w
2
=
0.4 was included for the comparison (see Figure 8). For the other multiobjective algorithms, four different scenarios were tested. Here, g
1
(
x
) is the nonnormalized version of f
1
(
x
) and g
2
(
x
) is the nonnormalized energy version of f
2
(
x
). Additionally, A
max
⁡ is the area to be covered and E
max
⁡ is given by (22). These variants are described as follows:(i)
Version-I (V-I): the coordinates of the algorithm are tested without normalizing them. That means(35)
g
x
=
g
1
x
g
2
x
.
(ii)
Version-II (V-II): the coordinates of the algorithm are tested, but in a normalized way as(36)
g
x
=
g
1
x
A
max
⁡
g
2
x
E
max
⁡
.
(iii)
Version-III (V-III): each normalized coordinate is weighted by 0.5 as(37)
g
x
=
0.5
g
1
x
A
max
⁡
0.5
g
2
x
E
max
⁡
.
(iv)
Version-IV (V-IV): the normalized area(
g
1
(
x
)
) is weighted by 0.6. Meanwhile, the normalized energy (
g
2
(
x
)
) is weighted by 0.4 as(38)
g
x
=
0.6
g
1
x
A
max
⁡
0.4
g
2
x
E
max
⁡
.Table 4
Comparison of DEA algorithm with some known multiobjective algorithms. Average on 50 tests.
Algorithm
Area (m
2) mean
Energy (mW) mean
MODEA (ours) (w
1
=
0.6, w
2
=
0.4)
981.9858
2.5266
NSGA-II V-I
1028.5674
2.8120
NSGA-II V-II
667.3309
2.1155
NSGA-II V-III
721.3496
1.9494
NSGA-II V-IV
875.0040
2.3059
MOEA/D V-I
868.0113
2.9287
MOEA/D V-II
708.6827
1.9229
MOEA/D V-III
648.9909
2.0030
MOEA/D V-IV
809.0555
2.3831According to the results shown in Table4, MODEA presents the best average performance among all the cases, with exception of NSGA-II version V-I. NSGA-II V-I obtains a coverage area 4.53% larger than MODEA; however the energy is 10.15% larger. It is shown that MODEA is more efficient in terms of the energy consumption; meanwhile NSGA-II increases the coverage area but raises the energy consumption. The rest of the multiobjective algorithms versions do not reach a similar area to that obtained by MODEA.


## 5.1.1. Scenario 1. Ellipse

To form the ellipse area shown in Figure9, the parameters are h
A
=
h
B
=
25, k
A
=
k
B
=
25, r
A
=
15, r
B
=
25, a
A
=
0.8, a
B
=
1.0, b
A
=
0.6, b
B
=
0.9, where A is the inner ellipse and B is the external ellipse, displayed into an area of 50 m × 50 m. The corresponding equations are listed as follows:(31)
x
-
h
A
2
a
A
2
+
y
-
k
A
2
b
A
2
=
r
A
2
,
x
-
h
B
2
a
B
2
+
y
-
k
B
2
b
B
2
=
r
B
2
.Figure 9
Area formed with two ellipses.It is observed in Figure9 that the circles follow the contour of the given ellipses, maximizing the coverage area. The best minimum fitness was obtained for the test 9
/
50.Figure10 shows the total energy consumption of the best curved-bounded scenario. The covered area is more than 90
% while the energy is below 4 units. The fitness curve indicates how both parameters are evolving to be optimized. After 700 generations, the fitness curve becomes stable, maintaining the area/energy limit values also stable.Figure 10
Results for (a) fitness, area, and (b) energy consumption on the scenario with two ellipses.
(a)
(b)Figure 11
(a) Triangle and (b) pentagon scenarios, best output.
(a)
(b)Figure 12
(a) Triangle and (b) pentagon scenarios, fitness and area curve.
(a)
(b)Figure 13
(a) Triangle and (b) pentagon scenarios, energy curve.
(a)
(b)Figure 14
Irregular area outside an amorphous zone.Figure 15
(a) Area, fitness, and (b) energy curves for amorphous figure.
(a)
(b)Figure 16
Multiple figures scenario.The line resolution between two nodes was left as 0.01. The complete circle contour was considered to determine the separation of the boundaries. That is, the angles to compute the radius circle were set as 0 : 0.01 : 360.


## 5.1.2. Regular Polygons, External Area

MODEA-BM is applied to the pentagon shown in Figure11(b) and also to the triangle shown in Figure 11(a). The figures here exposed are obtained using the expression L
T
=
linspace
0,2
π
,
points and the equations given below:(32)
x
=
A
cos
⁡
L
T
+
π
2
+
U
,
y
=
A
sin
⁡
L
T
+
π
2
+
V
,where points
=
4, A
=
15, U
=
20, V
=
18 in Figure 11(a) and points
=
6, A
=
10, U
=
V
=
20 in Figure 11(b). Vectors x and y define the vertices of the polygon. Both polygons are displayed into an area of 40 m × 40 m.Figure12 shows the area and fitness obtained for both scenarios. While for triangle the fitness converges before G
=
400, for pentagon the fitness delays to converge before G
=
900. For both cases, the coverage area is greater than 90
%.Figure13 shows the energy obtained for both scenarios. While for triangle the energy becomes stable after G
=
400 with 4 units, for the pentagon the energy holds the same after G
=
800 with 3.6 units.The best minimum fitness was obtained as41
/
50 for triangle and 45
/
50 for pentagon. To speed up the algorithm, each circle was sampled in angles as 0 : 45 : 360 to compute the radius. The line resolution between two nodes was left as 0.001 in order to detect forbidden crosses on the shaded area.


## 5.1.3. Irregular External Area

In this scenario, MODEA-BM is applied to the irregular area shown in Figure14, which is obtained with (33)
x
=
2
H
x
2
y
=
2
H
y
2
+
1
,where the user can choose the values of vectors x and y to generate the irregular polygon of Figure 14. This scenario is presented to show how the algorithm is able to work with true irregular areas. Figure 14 is formed by two linked irregular polygons. The figure is displayed into an area of 40 m × 40 m.As shown in Figure14, the algorithm prevents that links of the MST from crossing the small polygon, also keeping a distance between the nodes and the entire polygon. With 17 nodes, it is possible to cover more than 90% of the amorphous figure (Figure 15(a)) while the energy is below 4 units (Figure 15(b)). The best minimum fitness was obtained as 10
/
50.To speed up the algorithm, each circle was sampled in angles as 0 : 90 : 360 to compute the radius. The line resolution between two nodes was left as 0.001 to check if a link crosses forbidden areas, specially the small triangle of the scenario.


## 5.1.4. Multiple-Bounded Area

A multiple-bounded area is shown in Figure16 with a different radii values, r
min
⁡
=
4 m, r
max
⁡
=
6 m, for speeding up the computation of results. The number of tests here are equal to 20. All the polygons are displayed into an area of 40 m × 40 m. This case shows how the algorithm can be adapted to cover an area with multiple bounds (forbidden areas). These bounds represent a triangle, pentagon, star, and two rectangles. For instance, to get the star figure, the following parameters: v
=
12, t
=
(
-
1
/
4
:
1
/
v
:
3
/
4
)
∗
2
∗
π, r
1
=
10, r
2
=
5, p
=
(
0
:
v
), r
=
(
r
1
+
r
2
)
/
2
+
(
r
1
-
r
2
)
/
2
∗
(
-
1
)
p and (34) are used(34)
x
=
r
cos
⁡
t
+
25
,
y
=
r
sin
⁡
t
+
23.5
.Here, the algorithm is able to arrange the obtained MST as a contour to the given bounds, preventing MST links from crossing forbidden areas. This effect is seen in the case of the star, where the links of the nodes do not cross the peaks of the star. A similar effect is seen for the rectangles, where the nodes forming the circle go nearly in parallel with 24 nodes. This property is maintained even in the presence of the thinnest region that connects the star and the triangle, where there is no link that crosses it. Thus, it is possible to cover more than 90% of the area of Figure16 (see Figure 17(a)) with less than 3.5 units of energy (see Figure 17(b)).Figure 17
(a) Area, fitness, and (b) energy curves for multiple figures.
(a)
(b)The best minimum fitness was obtained as2
/
20. To speed up the algorithm, each circle was sampled in angles as 0 : 30 : 360 to compute the radius and the line between two nodes was sampled with 0.1 of resolution. When constructing the final MST, that line is sampled with 0.001 of resolution to detect if it crosses forbidden zones. The s
c
a
l
e parameter guarantees that all the cases do not have issues with the line resolution when finishing MODEA-BM.


## 5.1.5. Summary of the Results

Table3 shows a summary of the average area results obtained from the different figures comparing them with the maximum area to be covered. The results obtained using MODEA-BM parameter are very close to the area to be covered. On each case, 50 tests were made to obtain their mean and standard deviation, except for the multiple case, where only 20 tests were done. The energy for all the cases remains below 4 units, while the coverage area is greater than 90
% for the best solutions obtained. The computation of the average and standard deviation on the area parameter shows that theirregular external area case remains greater than 90
% with the lowest standard deviation, which is consistent with the fitness value (
34.98
%
). In contrast, themultiple case shows the worst average (
77.35
%
) and the largest standard deviation (135.10) and also presents the largest fitness value (
46.17
%
) with the largest standard deviation (8.00). Even so, formultiple case, MODEA-BM is able to obtain results where the covered area is greater than 90
%.Table 3
Area to cover and area covered by MODEA-BM, plus energy consumption. Averages, standard deviation, and best cases, where BC means best case,μ
^ is the average, and σ is the standard deviation.
Figure Number
Data
Fitness Percent %
Fitnessσ
Area (m2) MODEA-BM
Area (m2) to cover
Area Percentage %
Areaσ
Energy (mW)
Energyσ
Scale parameter
Number of Nodes
Figure9
Stats(
μ
^
,
σ
)
42.25
5.04
1151.63
1427.72
80.66
124.16
3.67
0.19
0.500
15
BC9
/
50
36.00
-
1349.12
94.49
-
3.92
-
Figure11(a)
Stats(
μ
^
,
σ
)
37.30
1.97
1120.02
1306.40
85.73
59.75
3.67
0.13
0.500
16
BC41
/
50
34.36
-
1235.63
94.58
-
3.98
-
Figure11(b)
Stats(
μ
^
,
σ
)
39.76
4.66
1136.88
1362.71
83.42
103.41
3.57
0.18
0.200
15
BC45
/
50
34.86
-
1260.21
92.47
-
3.64
-
Figure14
Stats(
μ
^
,
σ
)
34.98
1.80
1159.72
1288.5
90.00
53.79
3.94
0.15
0.200
17
BC10
/
50
31.23
-
1235.06
95.85
-
3.90
-
Figure16
Stats(
μ
^
,
σ
)
46.17
8.00
871.15
1126.21
77.35
135.10
3.51
0.13
0.400
24
BC2
/
20
36.78
-
1029.67
91.42
-
3.41
-Table4 shows the comparison of the DEA here proposed to well-known multiobjective optimization algorithms such as NSGA-II and MOEA/D. The authors modified the generic versions of both algorithms, where the corresponding source codes are available in [67]. The default configuration parameters were left unmodified except N
p
=
35. Here, only the base case scenario was tested. For the sake of consistency and fairness, the same 50 tests were done for the following presented cases. For MODEA, the radii-variable coordinate obtained with w
1
=
0.6 and w
2
=
0.4 was included for the comparison (see Figure 8). For the other multiobjective algorithms, four different scenarios were tested. Here, g
1
(
x
) is the nonnormalized version of f
1
(
x
) and g
2
(
x
) is the nonnormalized energy version of f
2
(
x
). Additionally, A
max
⁡ is the area to be covered and E
max
⁡ is given by (22). These variants are described as follows:(i)
Version-I (V-I): the coordinates of the algorithm are tested without normalizing them. That means(35)
g
x
=
g
1
x
g
2
x
.
(ii)
Version-II (V-II): the coordinates of the algorithm are tested, but in a normalized way as(36)
g
x
=
g
1
x
A
max
⁡
g
2
x
E
max
⁡
.
(iii)
Version-III (V-III): each normalized coordinate is weighted by 0.5 as(37)
g
x
=
0.5
g
1
x
A
max
⁡
0.5
g
2
x
E
max
⁡
.
(iv)
Version-IV (V-IV): the normalized area(
g
1
(
x
)
) is weighted by 0.6. Meanwhile, the normalized energy (
g
2
(
x
)
) is weighted by 0.4 as(38)
g
x
=
0.6
g
1
x
A
max
⁡
0.4
g
2
x
E
max
⁡
.Table 4
Comparison of DEA algorithm with some known multiobjective algorithms. Average on 50 tests.
Algorithm
Area (m
2) mean
Energy (mW) mean
MODEA (ours) (w
1
=
0.6, w
2
=
0.4)
981.9858
2.5266
NSGA-II V-I
1028.5674
2.8120
NSGA-II V-II
667.3309
2.1155
NSGA-II V-III
721.3496
1.9494
NSGA-II V-IV
875.0040
2.3059
MOEA/D V-I
868.0113
2.9287
MOEA/D V-II
708.6827
1.9229
MOEA/D V-III
648.9909
2.0030
MOEA/D V-IV
809.0555
2.3831According to the results shown in Table4, MODEA presents the best average performance among all the cases, with exception of NSGA-II version V-I. NSGA-II V-I obtains a coverage area 4.53% larger than MODEA; however the energy is 10.15% larger. It is shown that MODEA is more efficient in terms of the energy consumption; meanwhile NSGA-II increases the coverage area but raises the energy consumption. The rest of the multiobjective algorithms versions do not reach a similar area to that obtained by MODEA.


## 6. Conclusion

Firstly, a base case was thoroughly studied in a theoretical way to determine the minimum and maximum limits of that base configuration. This was done to show how MODEA is able to find a suboptimal solution near to its maximum theoretical configuration with great accuracy (99.05%). At the same time on the same base case, several feasible optimization strategies were tested with the use of MODEA, denoted as MODEA-R, MODEA-RM, MODEA-B, and MODEA-BM. It can be seen that the addition of therandom-
M parameter in Storn’s algorithm helps to converge toward the optimal solution quickly, particularly for MODEA-BM. For that reason, MODEA-BM was chosen to evaluate the rest of the cases here presented, i.e., different area shapes, either one shape or multiple shapes. Results obtained with 1000 iterations and w
1
=
0.6, w
2
=
0.4 showed that more than 90% of the targeted area is covered for the best outputs, except formultiple case. For a highly restricted scenarios likemultiple case, the best outputs showed that the suboptimal solution is reached in 2500 iterations, even when in general the low average (77.35%) shows that some of the cases do not reach the desired output. The MST was adapted to avoid crossing forbidden areas, creating feasible communication trees while optimizing the objective function. Nevertheless, the readers are warned that an adequate restriction tuning leads to a feasible solution, especially in cases where the area shapes are irregular, multiple, or a combination of both. Thus, MODEA-BM prevents the existence of nodes in forbidden areas, near these areas' borders, or near each other with a certain tolerance, thus maximizing the covered area and reducing energy consumption. MODEA-BM is complemented with the use of the Prim–Dijkstra algorithm to find on-the-fly the best possible MST for each population member. MODEA-BM is also complemented with the Hungarian algorithm at the end in order to find which movements should be performed to arrange the initial to the end node positions.As further work, the following lines of research can be done:(
1
) The application of the MODEA algorithm should be investigated in real indoor coverage areas considering wireless propagation effects such as shadowing, interference, obstacles, and multipath. Those restrictions shown by [17, 18] will complement the results presented in this work. (
2
) With some further adaptations, MODEA could be applied for guiding autonomous sensorial robots in an unexplored geographical area or (
3
) in search and rescue operations, where it is common to have different sensor nodes with different transmission rates, ranges, and sampling rates. (
4
) It would be interesting to compare MODEA against other well-known bioinspired algorithms such as Ant Colony Optimization or the latest MODEA versions found in the open literature (jDE [68], JADE [69], SADE [70], and the like [62]) and obtain similar results like those shown in [34]. (
5
) A simulation to evaluate MODEA should be done using random variables to generate irregular coverage areas and simultaneously determine its impact in forming links in an ad hoc network, reflected in the construction of routing tables.



---

*Source: 7873984-2018-06-03.xml*