# Optimization of the Distribution and Localization of Wireless Sensor Networks Based on Differential Evolution Approach

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

---

## Abstract

Location information for wireless sensor nodes is needed in most of the routing protocols for distributed sensor networks to determine the distance between two particular nodes in order to estimate the energy consumption. Differential evolution obtains a suboptimal solution based on three features included in the objective function: area, energy, and redundancy. The use of obstacles is considered to check how these barriers affect the behavior of the whole solution. The obstacles are considered like new restrictions aside of the typical restrictions of area boundaries and the overlap minimization. At each generation, the best element is tested to check whether the node distribution is able to create a minimum spanning tree and then to arrange the nodes using the smallest distance from the initial position to the suboptimal end position based on the Hungarian algorithm. This work presents results for different scenarios delimited by walls and testing whether it is possible to obtain a suboptimal solution with inner obstacles. Also, a case with an area delimited by a star shape is presented showing that the algorithm is able to fill the whole area, even if such area is delimited for the peaks of the star.


---

## Body

## 1. Introduction

It is well-known that location is a fundamental problem in wireless sensor networks (WSN) and it is essential based on either the distance or the connectivity among the nodes in the wireless sensor network. It is necessary to truthfully localize the sensors 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. Sensors usually have low energy consumption, network self-organization, collaborative signal processing, and querying abilities. In consequence, it is crucial that the required data be disseminated and localized to the proper end users [1, 2].A WSN is comprised of a large number of sensor nodes, which are densely positioned into a given area. Basically, they are a set of almost-static nodes and the nodes are not connected to each other. Their distribution inside a given area with minimum energy connectivity is an NP-complete problem [3–6].For applications like automatic location, tracking, and guidance, the well-known global positioning system (GPS) is a space-based navigation system that provides location any time and is widely used. One way to acquire location information of sensor nodes is to equip each sensor with a GPS, but, in practice, in sensor networks with a large number of sensor nodes, only a limited portion of sensors are equipped with a GPS calledanchors in the literature [7, 8]. An example of location-based protocol is presented by [9], it maintains a minimum energy communication network for wireless networks using low power GPS, and also it helps to calculate a minimum-power topology for mobile and stationary nodes by the use of a sink or concentrator node. Moreover, topology optimization finds the best network topology under certain constraints assuming that nodes must maintain communication to at least one neighbor [10].Localization algorithms usually assume that sensors are distributed in regular areas without cavities or obstacles, but outdoor deployment of wireless sensor networks is very different. To solve this problem a reliable anchor-based localization technique is proposed by [7] in which the localization error due to the irregular deployment areas is reduced. Locating sensors in irregular areas is also analyzed by [8]; the problem is formulated as a constrained least-penalty problem. The effects ofanchors density, range error, and communication range on localization performances are analyzed. Nonconvex deployment areas such as C-shaped and S-shaped topologies are used. Moreover, in [11] the authors focused on the area coverage problem in a nonconvex region, as the region of interest limited by the existence of obstacles, administrative boundaries, or geographical conditions. The authors apply the discrete particle swarm optimization (PSO) algorithm with the use of a grid system to discretize the region of interest.WSN deployment consists in determining the positions for sensor nodes in order to obtain the desire coverage, localization, connectivity, and energy efficiency. Available PSO solutions for the deployment problem are analyzed centrally on a base station to determine positions of the sensor nodes, the mobile nodes, or base stations as described in [12–14]. A node localization approach using PSO is described in [15–17].On the other hand, flocking is the event or singularity in which a large number of agents (sensors) with limited environmental information and simple rules are organized into a coordinated motion and are widely used in many control areas including mobile sensor networks. Flocking of multiagents with virtual leader is presented in [18], in which the sensors in a network can be moved by using the improved algorithm. However, coordinated control of multiagent systems with leaders points to making all agents reach a coordinated motion with leaders. The case with multiple leaders is named containment control, in which every control input of agents is subject to saturation owing to its upper and lower limits in multiagent systems. This case is cleverly described in [19], focused on switching networks. The containment control with periodically intermittent communication and input saturation is deeply analyzed by [20] in which the authors design both state feedback and output feedback containment control protocols with intermittent input saturation via low gain feedback. This technique achieves a practical semiglobal containment of such agents on fixed networks.There are some existing results in the literature that analyze the wireless sensors distribution in the three-dimensional space such as in [21–23]. These scenarios analyze the distribution of the sensor networks under certain conditions that are not considered in this research work. The three-dimensional sensor distribution is out of the scope of this research paper but is considered as a future work. For instance, to extend this research paper to the three-dimensional case, it is necessary to consider new objective functions, new scenarios with regular and irregular areas, and new upper and lower bounds; also, instead of computing the coverage area, it will be necessary to compute the involved volume and this requires more computational time to obtain results with low granularity.In this research work, to optimize the distribution and location of sensor nodes, the Differential Evolution Algorithm (DEA) is applied. This technique has been successfully applied on different problems due to its simplicity of use [24–26]. Its taxonomy is in the category of bioinspired techniques. For each cycle denoted as generation, DEA uses a set of potential random solutions in a given search space, called individuals. In this research paper, an individual contains the information of the coordinates of the sensor nodes (x,y) and their communication radii values. For each individual in the population, a descendant is generated from three parents. One parent, called the main parent, is disturbed by the vector of differences of the other two parents. In the case of the descendant having a better performance according to the objective function, it substitutes the individual, else the original individual is retained and is passed on to the next generation of the algorithm and the descendant is eliminated. This process is repeated till it attains the stop condition. The readers are referred to [24] for a complete theoretical analysis of the DE algorithm.Early work to solve the node distribution optimizing area and energy based on Differential Evolution Algorithm is presented in authors of [27]. But they only consider a typical square area without obstacles and the work lacks information about the energy consumption and the mobility of the sensor nodes; also, the localization of sensors is not analyzed. Extended cases for irregular areas are shown by [28], in which the interference rate is included and how much nodes are turned on at same time. In [29], the problem is divided in uniformity (node spreading) and connectivity (node clustering) regarding the area; the energy is analyzed by dividing the problem in operational consumed energy and data-exchange consumed energy.Differential evolutions with heuristic algorithms for nonconvex optimization on sensor network localization are analyzed in [30]; here, the connections and disconnections constraints are considered by the authors. Also, the connectivity-based localization problem is analyzed as an optimization problem with both convex and nonconvex constraints. In [31], the minimization equation of WSN localization error problem and an approach of differential evolution for minimization of localization error in WSN are studied considering that sensor node localization is the ability of an individual node to determine the location information. There are also surveys related to localization in wireless sensor network described in [32, 33].Compared to the previous listed works, here, the contributions are focused on building and establishing communication links even in the presence of obstacles or very restricted boundaries. DEA is used to optimize the distribution and as a consequence the location of the sensor nodes to minimize the overlap by using an extra function as shown by [28]. The main difference with [28] is that the overlap considered as the interference is also managed in terms of restrictions to minimize the overlap very quickly. It also applies for [29]. Besides, an extra parameter called random-M is used in the mutation operator to avoid the stagnation of DEA as suggested in [25].In this research work, the results are presented for two area boundaries: inner star and a typical square room. But, instead of having an empty square room, the room includes subdivisions called walls, which will act as obstacles regarding the signal propagation, showing the optimization of the fitness function formed by the area coverage rate, the energy consumption, and an additional parameter that is related to the overlap among the nodes: the redundancy. For the used configurations, the initial node positions are randomly assigned. For the inner star, a minimum spanning tree (MST) is used at the end of each generation to check the connectivity of the nodes. For the scenarios with obstacles, such verification is performed for each individual of the population. At the end of each generation, the Hungarian algorithm [34] is used to find the shortest distance from their initial to the final location. In all scenarios here presented, the algorithm determines the initial and the final location of the sensor nodes. Each sensor node is located with respect to any of each other following the branches of the minimum spanning tree. The distance between nodes is also calculated by adding the respective distances of the branches among them.The rest of this paper is organized as follows. Section2 describes the methodology. Section 3 presents the DEA and minimum spanning tree algorithms for wireless sensor networks distribution and location. Section 4 summarizes the pseudocode applied on DEA. Section 5 presents the numerical results and a discussion. Finally, Section 6 presents some conclusions.


## 2. Description of the Method

### 2.1. Sensor Coverage Model

There is a particular interest in the sensor distribution and location where communication with neighboring nodes is more energy efficient. Also, a particular interest in the sensor distribution and location on irregular areas is considered. The main purpose of the sensor coverage model is to obtain a balance among the maximum effective coverage area, the minimum communication sensor energy, and reducing overlap.The node set on the target areaAt is given by(1)N=N1,N2,…,Nz,and here z is the cardinality of N.The coverage range of a nodeNi is defined as a circle centered at its coordinates (xi,yi) with sensing radius ri. (xi,yi) coordinates define the position of sensor nodes and the subindex i is the sensor node index. A grid point (x,y) is covered by a sensor node i if and only if its distance to the center (xi,yi) of the circle is not larger than the sensing radius ri.A random variableIi is defined in order to describe the event that the sensor node N covers a given point (x,y). Then, the probability of event Ii, given by P{Ii}, is equal to the coverage probability Pcov(x,y,Ni). This probability is a binary valued function which is expressed as(2)Pcovx,y,Ni=1ifx-xi2+y-yi2≤ri20otherwise,where a point (x,y) is covered by a sensor node Ni if and only if its distance to the center (xi,yi) is less than or equal to the sensing radius ri. It is obvious that a point must be evaluated against all the nodes in the network; thus(3)Sx,y=∑i=1zPcovx,y,Ni,and here S(x,y) represents the number of times that the coordinate (x,y) is covered by the node set.However, to find the proper covered area by the set of nodes, the functionR(x,y) is calculated to check if the coordinate is covered at least once or if it is not covered at all Ni; (4)Rx,y=1Sx,y≥10Sx,y=0.The covered area is calculated as(5)AcovN=∑y=1n∑x=1mRx,yAt.Equation (5) is applied in our simulation by sweeping all (x,y) points of the target area m×n. For different area configurations, this area is replaced by the bounded area of interest. Now, f1(x) is expressed as(6)f1x=1-AcovN.


### 2.2. Redundant Area

The uncovered nonnormalized area is computed as(7)Azeros=At1-AcovN.The redundant area is computed as(8)Redx,y=1Sx,y>10Sx,y=0,1,which verify if a coordinate is covered by more than one node. As a result,(9)AredN=∑y=1n∑x=1mRedx,yAt-Azeros,where Acov(N) is the area covered by the nodes, Ared(N) is the redundant area, and Azeros(N) is the area not covered by the nodes. Now, f2(x) is defined as(10)f2x=AredN.The functionf2(x) is equivalent to the one given by [28].


### 2.3. Energy Consumption

There exist several models for wireless networks efficient energy consumption; for example, see [6, 35, 36], among others. In this paper, the total energy consumption in maintaining the network connectivity is given by(11)Ecst=μ∑i=1zriα,and here μ is the node sensing parameter in milliwatts per square meter (mW/m2) and ri is the sensor radius of Ni in meters (m), and α=2 since our communication medium is the air [37]. In this research work μ=0.005 (mW/m2) is used. Now, f3(x) is expressed as(12)f3x=EcstN.Nevertheless, to normalize f3(x), it is needed to use a constant which considers the maximum value that f3(x) may obtain. Then, the possible maximum value is used in its inverse form as(13)n3=1μzrmax2,and here rmax is the maximum sensor radius in meters (m).


### 2.4. Wall Behavior Analysis

To simplify the analysis of the obstacles, it has adopted on-off criterion to compute the area coverage in the same way that a channel is modelled with the well-known binary symmetric channel model [38], by omitting existing effects such as signal propagation through barriers or obstacles. A similar approach is used in [28]. Figure 1 shows how the MST should be formed. Additionally, it also shows how the area can be treated and computed if a wall crosses the area coverage of a given node. It can see that N4 is used to connect N3 and N5 to prevent the wall. That means a link should not cross a wall. About the computed area coverage, dark areas in N1 and N5 are not computed because they are not located aside from the center of the area coverage; that is, they are located at the other side of the wall. Such restriction is considered to compute the area coverage in order to give feedback on this research work.Figure 1
Wall analysis to compute area coverage and to form a MST.


## 2.1. Sensor Coverage Model

There is a particular interest in the sensor distribution and location where communication with neighboring nodes is more energy efficient. Also, a particular interest in the sensor distribution and location on irregular areas is considered. The main purpose of the sensor coverage model is to obtain a balance among the maximum effective coverage area, the minimum communication sensor energy, and reducing overlap.The node set on the target areaAt is given by(1)N=N1,N2,…,Nz,and here z is the cardinality of N.The coverage range of a nodeNi is defined as a circle centered at its coordinates (xi,yi) with sensing radius ri. (xi,yi) coordinates define the position of sensor nodes and the subindex i is the sensor node index. A grid point (x,y) is covered by a sensor node i if and only if its distance to the center (xi,yi) of the circle is not larger than the sensing radius ri.A random variableIi is defined in order to describe the event that the sensor node N covers a given point (x,y). Then, the probability of event Ii, given by P{Ii}, is equal to the coverage probability Pcov(x,y,Ni). This probability is a binary valued function which is expressed as(2)Pcovx,y,Ni=1ifx-xi2+y-yi2≤ri20otherwise,where a point (x,y) is covered by a sensor node Ni if and only if its distance to the center (xi,yi) is less than or equal to the sensing radius ri. It is obvious that a point must be evaluated against all the nodes in the network; thus(3)Sx,y=∑i=1zPcovx,y,Ni,and here S(x,y) represents the number of times that the coordinate (x,y) is covered by the node set.However, to find the proper covered area by the set of nodes, the functionR(x,y) is calculated to check if the coordinate is covered at least once or if it is not covered at all Ni; (4)Rx,y=1Sx,y≥10Sx,y=0.The covered area is calculated as(5)AcovN=∑y=1n∑x=1mRx,yAt.Equation (5) is applied in our simulation by sweeping all (x,y) points of the target area m×n. For different area configurations, this area is replaced by the bounded area of interest. Now, f1(x) is expressed as(6)f1x=1-AcovN.


## 2.2. Redundant Area

The uncovered nonnormalized area is computed as(7)Azeros=At1-AcovN.The redundant area is computed as(8)Redx,y=1Sx,y>10Sx,y=0,1,which verify if a coordinate is covered by more than one node. As a result,(9)AredN=∑y=1n∑x=1mRedx,yAt-Azeros,where Acov(N) is the area covered by the nodes, Ared(N) is the redundant area, and Azeros(N) is the area not covered by the nodes. Now, f2(x) is defined as(10)f2x=AredN.The functionf2(x) is equivalent to the one given by [28].


## 2.3. Energy Consumption

There exist several models for wireless networks efficient energy consumption; for example, see [6, 35, 36], among others. In this paper, the total energy consumption in maintaining the network connectivity is given by(11)Ecst=μ∑i=1zriα,and here μ is the node sensing parameter in milliwatts per square meter (mW/m2) and ri is the sensor radius of Ni in meters (m), and α=2 since our communication medium is the air [37]. In this research work μ=0.005 (mW/m2) is used. Now, f3(x) is expressed as(12)f3x=EcstN.Nevertheless, to normalize f3(x), it is needed to use a constant which considers the maximum value that f3(x) may obtain. Then, the possible maximum value is used in its inverse form as(13)n3=1μzrmax2,and here rmax is the maximum sensor radius in meters (m).


## 2.4. Wall Behavior Analysis

To simplify the analysis of the obstacles, it has adopted on-off criterion to compute the area coverage in the same way that a channel is modelled with the well-known binary symmetric channel model [38], by omitting existing effects such as signal propagation through barriers or obstacles. A similar approach is used in [28]. Figure 1 shows how the MST should be formed. Additionally, it also shows how the area can be treated and computed if a wall crosses the area coverage of a given node. It can see that N4 is used to connect N3 and N5 to prevent the wall. That means a link should not cross a wall. About the computed area coverage, dark areas in N1 and N5 are not computed because they are not located aside from the center of the area coverage; that is, they are located at the other side of the wall. Such restriction is considered to compute the area coverage in order to give feedback on this research work.Figure 1
Wall analysis to compute area coverage and to form a MST.


## 3. The Differential Evolution Algorithm

The DEA generates a set ofNp individuals, each one of dimension D. Particulary for this problem, the dimension D includes the coordinates (xi,yi) and the radii (ri) of the sensor nodes in the same vector (xi,yi,ri). Each individual is a potential solution of the problem, generated randomly but bounded by the constraints of the problem to solve. To perform its duties, the algorithm tunes the solutions with the following constants: the mutation constant (M), the recombination constant (Cr), and the population size (Np) which are defined by the user, where 0≤M≤1 and 0≤Cr≤1. Given G generations (cycles), operations like mutation, recombination, and selection are applied to each individual to obtain new and improved individuals that should be able to substitute the old ones. If it is successful, each time a generation is executed, a better suboptimal solution is obtained, which is near to the global optimal solution. The following is a description of the operators used in the DE algorithm that finds the most promising region in the search space.


### 3.1. Objective Functions

In this paper, the DE algorithm seeks to obtain a balance among the maximal effective coverage rate, the minimum sensor power communication, and the overlap. To convert the network coverage rate into minimal functions the opposite effect of the coverage rate is applied. Therefore, the network effective coverage rate is expressed by(14)Minf1x=1-AcovN,the redundant area is determined by(15)Minf2x=AredN,and the minimum network energy communication is determined by(16)Minf3x=EcstN.The values ofMin⁡f1(x), Min⁡f2(x), and Min⁡f3(x) are part of the fitness function for measuring the result. A linear combination of the objective functions converts the original multiobjective function into a single-objective function as follows:(17)Min∑k=1Kwkfkx,wherewk≥0;∑k=1Kwk=1,and here wk are weight coefficients expressing the relative importance of each objective function and k is the number of objective functions that the total objective function f(x) has.


### 3.2. The Fitness Function

The scenario where DEA is to be applied is limited by the area boundaries and the small amount of energy for each node. Additionally, it is important, aside from the optimization of the area coverage and the energy, to improve the separation among the nodes by adding an extra function which helps to prevent the overlap. Then, the fitness function is defined by(18)fx=w1f1x+w2f2x+w3n3f3x,where w1, w2, and w3 are weight coefficients and n3 is the normalization coefficient of f3(x). These values are chosen in such a way that the whole objective function is in the interval [0,1] and w1+w2+w3=1. If the value is minimal, it means that a good combination of maximum area, minimum energy, and minimum overlap is achieved.


### 3.3. The Mutation Operator

Letxr1,xr2,xr3∈{1,…,Np}: xr1≠xr2≠xr3≠xi. xr1, xr2, and xr3, different from the current target vector xi, and M is a scaling factor named as the mutation constant, which must satisfy M>0. For each target vector xi, i=1,…,Np, the mutant individual mi is created using (19) [25]:(19)mi=xr1+Mxr2-xr3,where the mutation operator is used to control the magnitude of the difference between two individuals, and it has a strong influence into the convergence of DEA.


### 3.4. The Recombination Operator

Letti be the trial vector, rand a uniform random number in the interval [0,1], and Cr the recombination constant. To obtain the trial vector from the mutation vector and the target vector, (20) holds. Consider(20)ti,j=mi,jifrand<Cr∀jxi,jotherwise.As it is known, each individual is formed forD components in the way that j={1,2,…,D}. If rand≤Cr, then the jth element of the mutation vector is chosen to be the jth component of the trial vector; otherwise, the jth of the trial vector is selected instead. The recombination operator helps to increase the diversity in the mutation process, so an adequate assignment will lead to obtaining accurate solutions [25].


### 3.5. The Selection Operator

LetPopi be the vector population of the next generation. To obtain it, the selection operation checks that(21)Popi=tiiffti<fxixiotherwise.Iff(ti)<f(xi), it means that the trial vector is a better individual than the target vector, thus being accepted as the new individual [25]. From these improved individuals either ti or xi, the best solution is registered until DEA finishes its duties.


### 3.6. The Random-M Mutation Parameter

Letrand be a random number in the range of (0<rand<1) that changes during the evolution process. Then, (22) is a modified version of (19) and shows how the main operator changes with this addition:(22)mi=xr1+rand∗Mxr2-xr3.By multiplyingM by rand, randomly increment or decrement its value. This permits the algorithm to get benefits from both a high convergence speed and a strong reduction of the probability of stagnation. After introducing rand, a significant improvement was perceived in the convergence of the algorithm. About other successful results, readers can read [25, 39].


## 3.1. Objective Functions

In this paper, the DE algorithm seeks to obtain a balance among the maximal effective coverage rate, the minimum sensor power communication, and the overlap. To convert the network coverage rate into minimal functions the opposite effect of the coverage rate is applied. Therefore, the network effective coverage rate is expressed by(14)Minf1x=1-AcovN,the redundant area is determined by(15)Minf2x=AredN,and the minimum network energy communication is determined by(16)Minf3x=EcstN.The values ofMin⁡f1(x), Min⁡f2(x), and Min⁡f3(x) are part of the fitness function for measuring the result. A linear combination of the objective functions converts the original multiobjective function into a single-objective function as follows:(17)Min∑k=1Kwkfkx,wherewk≥0;∑k=1Kwk=1,and here wk are weight coefficients expressing the relative importance of each objective function and k is the number of objective functions that the total objective function f(x) has.


## 3.2. The Fitness Function

The scenario where DEA is to be applied is limited by the area boundaries and the small amount of energy for each node. Additionally, it is important, aside from the optimization of the area coverage and the energy, to improve the separation among the nodes by adding an extra function which helps to prevent the overlap. Then, the fitness function is defined by(18)fx=w1f1x+w2f2x+w3n3f3x,where w1, w2, and w3 are weight coefficients and n3 is the normalization coefficient of f3(x). These values are chosen in such a way that the whole objective function is in the interval [0,1] and w1+w2+w3=1. If the value is minimal, it means that a good combination of maximum area, minimum energy, and minimum overlap is achieved.


## 3.3. The Mutation Operator

Letxr1,xr2,xr3∈{1,…,Np}: xr1≠xr2≠xr3≠xi. xr1, xr2, and xr3, different from the current target vector xi, and M is a scaling factor named as the mutation constant, which must satisfy M>0. For each target vector xi, i=1,…,Np, the mutant individual mi is created using (19) [25]:(19)mi=xr1+Mxr2-xr3,where the mutation operator is used to control the magnitude of the difference between two individuals, and it has a strong influence into the convergence of DEA.


## 3.4. The Recombination Operator

Letti be the trial vector, rand a uniform random number in the interval [0,1], and Cr the recombination constant. To obtain the trial vector from the mutation vector and the target vector, (20) holds. Consider(20)ti,j=mi,jifrand<Cr∀jxi,jotherwise.As it is known, each individual is formed forD components in the way that j={1,2,…,D}. If rand≤Cr, then the jth element of the mutation vector is chosen to be the jth component of the trial vector; otherwise, the jth of the trial vector is selected instead. The recombination operator helps to increase the diversity in the mutation process, so an adequate assignment will lead to obtaining accurate solutions [25].


## 3.5. The Selection Operator

LetPopi be the vector population of the next generation. To obtain it, the selection operation checks that(21)Popi=tiiffti<fxixiotherwise.Iff(ti)<f(xi), it means that the trial vector is a better individual than the target vector, thus being accepted as the new individual [25]. From these improved individuals either ti or xi, the best solution is registered until DEA finishes its duties.


## 3.6. The Random-M Mutation Parameter

Letrand be a random number in the range of (0<rand<1) that changes during the evolution process. Then, (22) is a modified version of (19) and shows how the main operator changes with this addition:(22)mi=xr1+rand∗Mxr2-xr3.By multiplyingM by rand, randomly increment or decrement its value. This permits the algorithm to get benefits from both a high convergence speed and a strong reduction of the probability of stagnation. After introducing rand, a significant improvement was perceived in the convergence of the algorithm. About other successful results, readers can read [25, 39].


## 4. Pseudocode for DEA in a WSN

As explained in Section3 DEA is tuned with M, Cr, and Np, and the number of generations is given by G. The complete population set is stored at Pop. Each individual is formed by Popi=xi,1,…,xi,z;yi,1,…,yi,z;ri,1,…,ri,z, where each member belongs to each Ni formed by a triad (xi,yi,ri), (xi,yi) being random coordinates. To start with DEA, it is necessary to consider an initial population Pinitial, where Pinitial=Pop1 for the sake of simplicity. Remembering the steps followed by DEA, three different individuals xr1, xr2, xr3 are obtained. Here, these individuals are obtained from Pop, where xr1, xr2, xr3 are equivalent to having xr1,j, yr2,j, rr1,j.The validation process ofti is based on the triad (xi,yi,ri) regarding the boundaries, rmax and rmin (or the smallest radio available in the node set rnmin). If r>rmax, (23) is applied to regenerate r as(23)radj=rmin+w1∗rand2+12∗rmax-rmin.On the other hand, if(x,y) are outside the boundaries, (x,y) coordinates are regenerated. One goal is to reduce the overlap of these nodes on each population member, and then in this way better energy and area combinations will be obtained. A distance among the nodes should be maintained to prevent excessive separations and this condition is controlled by the largest radius of the involved nodes multiplied by a parameter scale, typically rmax. The easiest way is to check the triad (xi,yi,ri) of Ni regarding to its neighbors. A strategy to prevent wasting area is to move (xi,yi) away from the boundaries. This is also controlled by scale that multiplies ri. In this work, wall scenarios are included, and it is important to note that it is possible that an area coverage of Ni can be cut out when it is crossing a wall. Then, the effective area coverage will be identified in the side where (xi,yi) is located. Additionally, to check if the obtained area covers enough surface, Ath is used as the minimum percentage acceptable area. Here, the parameter scale can be treated as fixed scale or variable scale=scale+delta.The Prim algorithm [40] obtains the minimum spanning tree (MST) while the Dijkstra algorithm [41] gives a star topology. Prim-Dijkstra [42] uses the location of the sensor nodes and determines a topology that is a mixture of both MST and a star topology. In this research work, the MST is formed by using arbitrarily a central node (cnode=5) and the maximum distance to generate a link (ri+rj, i≠j). If d(Ni,Nj)>ri+rj, the link does not exist. To satisfy this constraint the Prim-Dijkstra algorithm [42] is used. Prim-Dijsktra will perform its duties when each link of the MST does not cross forbidden zones, boundaries, or walls; otherwise the nodes that do not fulfill these restrictions will not be neighbors of Ni.The objective function launches the area, the energy, and the redundancy aside from the fitness. As it has been described through this work, the minimum fitness indicates that efficient combination of area usage, energy, and redundancy has been obtained.Finally, the initial and final location of sensor nodes are given byPopinitial and Popbest, respectively. The Hungarian Algorithm [34] helps to find the minimal distance that a node will move away to the ending location from its original location. It receives Popbest and Popinitial to determine the final location of the sensors with respect to the initial location. By using (xi,yi), the Hungarian Algorithm uses a matrix of distances, where each distance is calculated by using the initial coordinates with respect to the final coordinates. The initial coordinate of a node is evaluated against all the final coordinates, to obtain the desired minimum distances. Then, the solution with the minimum distance in which each node goes from the initial to the final position is chosen. In this work, in scenarios with walls, the distance from one node to any other one is through the branches of the MST preventing crossing any wall or obstacle. Algorithm 1 summarizes the behavior of DEA.Algorithm 1:DEA applied to WSN.
procedure DEA
Set the control parameters
Create Pop
Evaluate fitness, area, energy, redundancy
Start generations counters=0
Repeat until stop conditions are completed:
(tree is built ands>G) or
(tree is built and area coverage ≥Ath)
for  i=1  to  Np  do
Select from Pop
Mutation mi,  equation (19);
Recombination ti,  equation (20);
Validate ti.
Update (x,y,r) if needed;
De-overlap ti, update (x,y) if needed;
Selection, equation (21)
end for
Popbest fitness, area, energy and redundancy
Apply Hungarian algorithm toPopbest versus Popinitial.
Apply Prim-Dijkstra(cnode,α) to array of links;
if Some nodes are not connected to the tree then
Continue;
else nodes are connected
Tree has been build.
end if
s=s+1
scale = scale + delta (Variable option untilG)
End repeat
return  Popbest, Fitness, Area, Energy, redundancy
end procedure


## 5. Numerical Results and Discussion

The algorithm is implemented in machines with the following characteristics:MATLAB R2013a.Windows 7 Enterprise 2009, service pack 1.Processor: Intel (R) Xeon (R) CPU.W3690 @ 3.47 GHz 3.46 GHz.Installed memory (RAM): 8.00 GB.System type: 64-bit operating system.For the inner star scenario, the effective sensor radius is between3.5 and 8 meters, and, the weights are w1=3∗0.90/4, w2=0.90/4, and w3=0.10. Here, two different strategies were tested. In the first one, the value for scale is fixed to 0.7000, while in the second one scale is increased in steps of 0.0070.For the wall scenarios, the effective sensor radius of the sensor nodes is between6 and 8 meters and the target areas are 80 (m) × 80 (m). DEA was tested based on the increment of scale in steps of 0.008 units when each generation is executed, thus controlling the separation among nodes instead of spreading them immediately and also helping with the speed of the algorithm. Here, w1=3∗0.8/4, w2=0.8/4, and w3=0.2. If the node coverage area is crossed by a wall, the region of the coverage area that does not contain the center of the node should not be considered in the computation of the area because the wall reduces the signal propagation. For simplification purposes in the calculation of the area coverage on each node, a criteria on-off is adopted. If the center is behind a wall, the area crossed by a wall is not considered.As it was explained in the previous section, the algorithm stops when the number of established generations is reached and the tree is formed, or a threshold area is reached and the tree is formed. The sensor nodes are identified asN1,N2,…,Ni,…,Nz, and the circles show their sensor range. The values of M=0.8, Np=35, and Cr=0.2 are used.For all, the inner star and wall scenarios, 40 tests were computed using both variable and fixed criteria. The percentage of covered area, energy consumption in maintaining the network connectivity, redundant area, and radii values are determined and analyzed. Also, the execution time for each test is determined. Increasing the number of sensor nodes, the noncovered areas of all scenarios can be solved. The initial and final location of sensor nodes can be obtained.


### 5.1. Inner Bounded Star

The set of Figure2 show the final distribution obtained with fixed and variable criteria, when DEA is applied. The initial positions of the nodes are randomly set, without forming a tree. The star is delimited by the following parameters: s=12, p=(0:s), r1=40, r2=20, t=(-1/4:1/s:3/4)∗2∗π, r=(r1+r2)/2+(r1-r2)/2∗(-1)p, and(24)xv=r∗cos⁡t+40,yv=r∗sin⁡t+40,where xv and yv are used in the Matlab command inpolygon (inpolygon(x,y,xv,yv)) and (x,y) are the coordinates of the point to be tested whether it is inside the figure or not.Figure 2
Examples of final distribution inner star, (a) fixed criterion, (b) variable criterion.
(a)
(b)Testing the fixed criterion, the final distribution fits the inner star as it can be seen in Figure2(a), the smallest nodes appear as connector between the nodes with larger area, and sometimes they appear at peaks of the star. Additionally, the nodes are distributed regarding the overlaps, showing that the algorithm tries to arrange the smallest nodes into the peaks or at least to arrange these nodes with an average area coverage. It is noted that the tree is formed successfully. Also, the results of the variable criterion (Figure 2(b)) show that the nodes are distributed; nevertheless the overlap is increased.Table1 shows examples of fixed and variable criteria with 30 nodes and effective area of 2399.9200 m2 under the scenario shown in Figure 2. It can be seen that both cases converge to 100 generations. Even when the fixed case presents better metrics than the variable one, the time spent to compute the solution is larger (fixed case has 889.1790 (s) while variable case has 546.9349 (s)). To state and prove this trend, it is needed to perform more tests.Table 1
Results for inner star. Tests # 24, 30 nodes.
Criteria
Area%
Energy (mW)
Radii  (m)
Redundancy%
Time (s)
Gen.
Variable
91.83
6.1192
6.2856
48.37
546.9349
100
Fixed
93.33
5.3197
5.8639
37.19
889.1790
100Table2 shows the results using 30 nodes and an effective area of 2399.9200 m2 for the tests numbers 31/40 and 35/40 of the 40 tests under the scenario shown in Figure 2; the mean and variance values of time, radii, percentage of redundancy, energy, and the covered area of the network were obtained. Here, both fixed and variable criteria are compared under the same conditions. The results are the average of these tests using 100 generations. The variable criterion is faster than the fixed one in 1.6527 times. It can be explained because the separation among the nodes (scale parameter) is relaxed for the variable criteria at most of the generations, even when the fixed criterion has a better solution than the variable one (which is reflected in the area coverage 89.66% versus 88.90%, energy 5.0037 (mW) versus 5.3347 (mW), and overlap 34.39% versus 40.94%).Table 2
Inner star. Mean and variance results, variable and fixed criteria.
Test
Variable
Fixed
Gen.
Success test/40
35/40
31/40
100
Mean time (s)
544.8065
900.4085
100
Mean redundant (%)
40.94
34.39
100
Mean radii (m)
5.8493
5.6670
100
Mean energy (mW)
5.3347
5.0037
100
Mean area (%)
88.90
89.66
100
Var time
6.6988
117.3945
100
Var redundant
0.0016
0.0019
100
Var radii
0.0330
0.0294
100
Var energy
0.0955
0.0877
100
Var area
2.3411e − 004
2.6960e − 004
100For the next scenarios one will choose the variable criterion due to its high speed and low variance in terms of area coverage and time execution in the search of the solution space. The solution here obtained with the variable criterion is as good as the fixed one. Adequate tuned parameters and weights will help the variable criteria to be near the fixed one.It is important to note that Figure2(a) shows only the optimized location of the sensor nodes. The initial random location and the final optimized location of sensor nodes in Figure 2(a) in terms of (x,y) coordinates are shown in Table 3.Table 3
Inner star, fixed criterion. Initial and final location of sensors nodes.
Node
X
i
n
i
t
i
a
l (m)
Y
i
n
i
t
i
a
l (m)
X
f
i
n
a
l (m)
Y
f
i
n
a
l (m)
N
1
38.9
45.8
39.7
52.8
N
2
14.2
58.7
18.3
52.5
N
3
42.8
73.4
39.8
70.5
N
4
60.9
49.0
60.6
52.7
N
5
54.2
40.1
58.7
33.1
N
6
40.4
40.6
42.6
43.1
N
7
60.4
58.2
66.6
55.3
N
8
41.6
62.8
40.7
64.4
N
9
43.8
13.1
40.6
12.0
N
10
52.4
51.8
52.7
48.2
N
11
28.8
39.2
28.7
38.3
N
12
28.4
36.0
23.6
35.4
N
13
15.3
47.1
21.8
45.3
N
14
28.0
26.5
19.8
26.7
N
15
47.1
57.7
47.8
56.1
N
16
27.5
24.1
33.0
23.3
N
17
41.7
29.0
40.9
29.2
N
18
18.0
49.0
34.9
49.8
N
19
37.9
19.5
40.6
20.3
N
20
19.8
51.4
27.2
51.5
N
21
58.3
43.8
58.9
45.2
N
22
9.5
25.3
11.4
24.7
N
23
31.9
35.7
36.2
34.2
N
24
27.1
28.1
25.6
29.4
N
25
46.8
28.9
52.8
28.5
N
26
41.2
21.9
46.8
26.8
N
27
29.7
28.2
44.9
34.1
N
28
25.8
54.2
35.2
56.8
N
29
48.2
49.9
50.4
38.4
N
30
57.3
39.0
65.6
26.5Now, four sets of walls are analyzed. The results were obtained using 100 generations for the first, second, and fourth set of walls and 120 generations for the third set of walls in the DEA.


### 5.2. First Set of Walls

The set of walls shown in Figure3 can be constructed by setting the walls through the coordinates xa=56:80, ya=40, xb=50, yb=0:24, xc=30, yc=0:24, xd=0:24, yd=40, xe=30, ye=56:80, and xf=50, yf=56:80. The distribution of the nodes is affected by the position of the walls. It is also noted that the final tree avoids crossing the walls, accomplishing the restriction of not crossing any obstacle. Some nodes lost their area coverage because of the walls; nevertheless other nodes can compensate that effect by covering the affected area. It is important to note that the distances between the walls and nodes 28 and 59 are 70 (cm) and 120 (cm), respectively. The circles are arranged far from the area boundary.Figure 3
Final distribution of nodes for the first set of walls.Table4 shows the results obtained in the test number 5 of the 40 tests under the scenario shown in Figure 3. The covered area is greater than 92%, the energy is 16.8013 (mW), and the redundancy is lower than 53%.Table 4
Results for the first set of walls, test # 5.
Criteria
Area%
Energy (mW)
Radii  (m)
Redundancy%
Time  (s)
Gen.
Variable
92.18
16.8013
7.1866
52.24
1226.3465
100


### 5.3. Second Set of Walls

The wall shown in Figure4 can be constructed by setting the wall through the coordinates xa=1:60, ya=45. It can be seen that the MST goes around the wall and the nodes are arranged away from the boundaries.Figure 4
Final distribution of nodes for the second set of walls.Table5 shows the obtained parameters with the test number 24 of the 40 tests under the scenario shown in Figure 4. The area is greater than 93%, the energy is 16.8589 (mW), and the redundancy is lower than 52%.Table 5
Results for the second set of walls, test # 24.
Criteria
Area%
Energy  (mW)
Radii  (m)
Redundancy%
Time  (s)
Gen.
Variable
93.87
16.8589
7.1981
51.32
1498.9526
100


### 5.4. Third Set of Walls

Case three was configured asxa=30, ya=11:70, xb=50, and yb=11:70, which seems as a set of parallel walls, shown in Figure 5. It can be seen that the tree goes around the wall and the nodes are arranged away from the boundaries. Here, also, it is important to note that the distances between the walls and nodes 53 and 65 are 80 (cm) and 70 (cm), respectively.Figure 5
Final distribution of nodes for the third set of walls.Table6 shows the obtained parameters with the test number 38 of the 40 tests under the scenario shown in Figure 5. The area is greater than 92%, the energy is 16.5964 (mW), and the redundancy is lower than 51%. Here, a case is presented where the number of generations is larger compared to the established one, 120 generations instead of 100 generations. As it can be shown through this paper, sometimes the algorithm needs more generations to obtain a tree.Table 6
Results for the third set of walls, test 38.
Criteria
Area%
Energy  (mW)
Radii  (m)
Redundancy%
Time (s)
Gen.
Variable
92.88
16.5964
7.1421
50.69
1739.6244
120


### 5.5. Fourth Set of Walls

Case four was configured asxa=1:25, ya=40, xb=76:80, yb=40, and xc=40, yc=26:75 which seems as a divided corridors inside a room, shown in Figure 6. It can be seen that the tree goes around the wall and the nodes are arranged away from the boundaries.Figure 6
Final distribution of nodes for the fourth set of walls.Table7 shows the obtained parameters with case 38 of the 40 tests under the scenario shown in Figure 6. The area is greater than 93%, the energy is 16.7526 (mW), and the redundancy is lower than 52%.Table 7
Results for the fourth set of walls, test 38.
Criteria
Area%
Energy  (mW)
Radii  (m)
Redundancy%
Time  (s)
Gen.
Variable
93.19
16.7526
7.1761
51.99
1480.5491
100It is important to remember that, to locate one sensor respect any other one, it is simple through the branches of the MST. For example, the distance between sensor nodesN7 and N20, in Figure 6, is not the euclidian distance between them. It is necessary to follow the route N7→N38→N62→N19→N39→N16→N20 and add each distance to obtain the total distance between sensor nodes N7 and N20.


### 5.6. Summary

Table8 shows a comparison summary of the parameters obtained with DEA such as the generation number in which the sensors configuration was obtained, the area covered, the energy average of the network, and the degree of overlap. The same 40 tests were done for each case, using 100 generations. The area average is larger than 93% with an energy average less than 16.85 (mW) and the redundancy average less than 54%. However, as it can be shown in Table 8, the covered area is quite similar in all cases. The rest of the nodes near the wall are compensated with the nodes at the other side of the wall.Table 8
Mean and variance results for the four set of walls, with 65 nodes and effective area of 6400.0000 (m2).
Case
Case1
Case2
Case3
Case4
Success test/40
34/40
40/40
36/40
39/40
Mean time (s)
1228.6005
1417.2937
1531.0622
1515.7459
Mean redundant (%)
50.13
53.05
50.50
51.40
Mean radii (m)
7.1963
7.1891
7.1879
7.1858
Mean energy (mW)
16.8495
16.8144
16.8092
16.7988
Mean area (%)
92.25
93.83
93.24
93.41
Var time
4.4281
1187.1325
1735.6760
1129.1838
Var redundant
1.7137e − 004
1.2889e − 004
1.8643e − 004
1.7708e − 004
Var radii
9.4720e − 004
4.4480e − 004
9.6199e − 004
6.5851e − 004
Var energy
0.0213
0.0097
0.0210
0.0143
Var area
3.2485e − 005
1.9754e − 005
2.9491e − 005
3.6057e − 005


## 5.1. Inner Bounded Star

The set of Figure2 show the final distribution obtained with fixed and variable criteria, when DEA is applied. The initial positions of the nodes are randomly set, without forming a tree. The star is delimited by the following parameters: s=12, p=(0:s), r1=40, r2=20, t=(-1/4:1/s:3/4)∗2∗π, r=(r1+r2)/2+(r1-r2)/2∗(-1)p, and(24)xv=r∗cos⁡t+40,yv=r∗sin⁡t+40,where xv and yv are used in the Matlab command inpolygon (inpolygon(x,y,xv,yv)) and (x,y) are the coordinates of the point to be tested whether it is inside the figure or not.Figure 2
Examples of final distribution inner star, (a) fixed criterion, (b) variable criterion.
(a)
(b)Testing the fixed criterion, the final distribution fits the inner star as it can be seen in Figure2(a), the smallest nodes appear as connector between the nodes with larger area, and sometimes they appear at peaks of the star. Additionally, the nodes are distributed regarding the overlaps, showing that the algorithm tries to arrange the smallest nodes into the peaks or at least to arrange these nodes with an average area coverage. It is noted that the tree is formed successfully. Also, the results of the variable criterion (Figure 2(b)) show that the nodes are distributed; nevertheless the overlap is increased.Table1 shows examples of fixed and variable criteria with 30 nodes and effective area of 2399.9200 m2 under the scenario shown in Figure 2. It can be seen that both cases converge to 100 generations. Even when the fixed case presents better metrics than the variable one, the time spent to compute the solution is larger (fixed case has 889.1790 (s) while variable case has 546.9349 (s)). To state and prove this trend, it is needed to perform more tests.Table 1
Results for inner star. Tests # 24, 30 nodes.
Criteria
Area%
Energy (mW)
Radii  (m)
Redundancy%
Time (s)
Gen.
Variable
91.83
6.1192
6.2856
48.37
546.9349
100
Fixed
93.33
5.3197
5.8639
37.19
889.1790
100Table2 shows the results using 30 nodes and an effective area of 2399.9200 m2 for the tests numbers 31/40 and 35/40 of the 40 tests under the scenario shown in Figure 2; the mean and variance values of time, radii, percentage of redundancy, energy, and the covered area of the network were obtained. Here, both fixed and variable criteria are compared under the same conditions. The results are the average of these tests using 100 generations. The variable criterion is faster than the fixed one in 1.6527 times. It can be explained because the separation among the nodes (scale parameter) is relaxed for the variable criteria at most of the generations, even when the fixed criterion has a better solution than the variable one (which is reflected in the area coverage 89.66% versus 88.90%, energy 5.0037 (mW) versus 5.3347 (mW), and overlap 34.39% versus 40.94%).Table 2
Inner star. Mean and variance results, variable and fixed criteria.
Test
Variable
Fixed
Gen.
Success test/40
35/40
31/40
100
Mean time (s)
544.8065
900.4085
100
Mean redundant (%)
40.94
34.39
100
Mean radii (m)
5.8493
5.6670
100
Mean energy (mW)
5.3347
5.0037
100
Mean area (%)
88.90
89.66
100
Var time
6.6988
117.3945
100
Var redundant
0.0016
0.0019
100
Var radii
0.0330
0.0294
100
Var energy
0.0955
0.0877
100
Var area
2.3411e − 004
2.6960e − 004
100For the next scenarios one will choose the variable criterion due to its high speed and low variance in terms of area coverage and time execution in the search of the solution space. The solution here obtained with the variable criterion is as good as the fixed one. Adequate tuned parameters and weights will help the variable criteria to be near the fixed one.It is important to note that Figure2(a) shows only the optimized location of the sensor nodes. The initial random location and the final optimized location of sensor nodes in Figure 2(a) in terms of (x,y) coordinates are shown in Table 3.Table 3
Inner star, fixed criterion. Initial and final location of sensors nodes.
Node
X
i
n
i
t
i
a
l (m)
Y
i
n
i
t
i
a
l (m)
X
f
i
n
a
l (m)
Y
f
i
n
a
l (m)
N
1
38.9
45.8
39.7
52.8
N
2
14.2
58.7
18.3
52.5
N
3
42.8
73.4
39.8
70.5
N
4
60.9
49.0
60.6
52.7
N
5
54.2
40.1
58.7
33.1
N
6
40.4
40.6
42.6
43.1
N
7
60.4
58.2
66.6
55.3
N
8
41.6
62.8
40.7
64.4
N
9
43.8
13.1
40.6
12.0
N
10
52.4
51.8
52.7
48.2
N
11
28.8
39.2
28.7
38.3
N
12
28.4
36.0
23.6
35.4
N
13
15.3
47.1
21.8
45.3
N
14
28.0
26.5
19.8
26.7
N
15
47.1
57.7
47.8
56.1
N
16
27.5
24.1
33.0
23.3
N
17
41.7
29.0
40.9
29.2
N
18
18.0
49.0
34.9
49.8
N
19
37.9
19.5
40.6
20.3
N
20
19.8
51.4
27.2
51.5
N
21
58.3
43.8
58.9
45.2
N
22
9.5
25.3
11.4
24.7
N
23
31.9
35.7
36.2
34.2
N
24
27.1
28.1
25.6
29.4
N
25
46.8
28.9
52.8
28.5
N
26
41.2
21.9
46.8
26.8
N
27
29.7
28.2
44.9
34.1
N
28
25.8
54.2
35.2
56.8
N
29
48.2
49.9
50.4
38.4
N
30
57.3
39.0
65.6
26.5Now, four sets of walls are analyzed. The results were obtained using 100 generations for the first, second, and fourth set of walls and 120 generations for the third set of walls in the DEA.


## 5.2. First Set of Walls

The set of walls shown in Figure3 can be constructed by setting the walls through the coordinates xa=56:80, ya=40, xb=50, yb=0:24, xc=30, yc=0:24, xd=0:24, yd=40, xe=30, ye=56:80, and xf=50, yf=56:80. The distribution of the nodes is affected by the position of the walls. It is also noted that the final tree avoids crossing the walls, accomplishing the restriction of not crossing any obstacle. Some nodes lost their area coverage because of the walls; nevertheless other nodes can compensate that effect by covering the affected area. It is important to note that the distances between the walls and nodes 28 and 59 are 70 (cm) and 120 (cm), respectively. The circles are arranged far from the area boundary.Figure 3
Final distribution of nodes for the first set of walls.Table4 shows the results obtained in the test number 5 of the 40 tests under the scenario shown in Figure 3. The covered area is greater than 92%, the energy is 16.8013 (mW), and the redundancy is lower than 53%.Table 4
Results for the first set of walls, test # 5.
Criteria
Area%
Energy (mW)
Radii  (m)
Redundancy%
Time  (s)
Gen.
Variable
92.18
16.8013
7.1866
52.24
1226.3465
100


## 5.3. Second Set of Walls

The wall shown in Figure4 can be constructed by setting the wall through the coordinates xa=1:60, ya=45. It can be seen that the MST goes around the wall and the nodes are arranged away from the boundaries.Figure 4
Final distribution of nodes for the second set of walls.Table5 shows the obtained parameters with the test number 24 of the 40 tests under the scenario shown in Figure 4. The area is greater than 93%, the energy is 16.8589 (mW), and the redundancy is lower than 52%.Table 5
Results for the second set of walls, test # 24.
Criteria
Area%
Energy  (mW)
Radii  (m)
Redundancy%
Time  (s)
Gen.
Variable
93.87
16.8589
7.1981
51.32
1498.9526
100


## 5.4. Third Set of Walls

Case three was configured asxa=30, ya=11:70, xb=50, and yb=11:70, which seems as a set of parallel walls, shown in Figure 5. It can be seen that the tree goes around the wall and the nodes are arranged away from the boundaries. Here, also, it is important to note that the distances between the walls and nodes 53 and 65 are 80 (cm) and 70 (cm), respectively.Figure 5
Final distribution of nodes for the third set of walls.Table6 shows the obtained parameters with the test number 38 of the 40 tests under the scenario shown in Figure 5. The area is greater than 92%, the energy is 16.5964 (mW), and the redundancy is lower than 51%. Here, a case is presented where the number of generations is larger compared to the established one, 120 generations instead of 100 generations. As it can be shown through this paper, sometimes the algorithm needs more generations to obtain a tree.Table 6
Results for the third set of walls, test 38.
Criteria
Area%
Energy  (mW)
Radii  (m)
Redundancy%
Time (s)
Gen.
Variable
92.88
16.5964
7.1421
50.69
1739.6244
120


## 5.5. Fourth Set of Walls

Case four was configured asxa=1:25, ya=40, xb=76:80, yb=40, and xc=40, yc=26:75 which seems as a divided corridors inside a room, shown in Figure 6. It can be seen that the tree goes around the wall and the nodes are arranged away from the boundaries.Figure 6
Final distribution of nodes for the fourth set of walls.Table7 shows the obtained parameters with case 38 of the 40 tests under the scenario shown in Figure 6. The area is greater than 93%, the energy is 16.7526 (mW), and the redundancy is lower than 52%.Table 7
Results for the fourth set of walls, test 38.
Criteria
Area%
Energy  (mW)
Radii  (m)
Redundancy%
Time  (s)
Gen.
Variable
93.19
16.7526
7.1761
51.99
1480.5491
100It is important to remember that, to locate one sensor respect any other one, it is simple through the branches of the MST. For example, the distance between sensor nodesN7 and N20, in Figure 6, is not the euclidian distance between them. It is necessary to follow the route N7→N38→N62→N19→N39→N16→N20 and add each distance to obtain the total distance between sensor nodes N7 and N20.


## 5.6. Summary

Table8 shows a comparison summary of the parameters obtained with DEA such as the generation number in which the sensors configuration was obtained, the area covered, the energy average of the network, and the degree of overlap. The same 40 tests were done for each case, using 100 generations. The area average is larger than 93% with an energy average less than 16.85 (mW) and the redundancy average less than 54%. However, as it can be shown in Table 8, the covered area is quite similar in all cases. The rest of the nodes near the wall are compensated with the nodes at the other side of the wall.Table 8
Mean and variance results for the four set of walls, with 65 nodes and effective area of 6400.0000 (m2).
Case
Case1
Case2
Case3
Case4
Success test/40
34/40
40/40
36/40
39/40
Mean time (s)
1228.6005
1417.2937
1531.0622
1515.7459
Mean redundant (%)
50.13
53.05
50.50
51.40
Mean radii (m)
7.1963
7.1891
7.1879
7.1858
Mean energy (mW)
16.8495
16.8144
16.8092
16.7988
Mean area (%)
92.25
93.83
93.24
93.41
Var time
4.4281
1187.1325
1735.6760
1129.1838
Var redundant
1.7137e − 004
1.2889e − 004
1.8643e − 004
1.7708e − 004
Var radii
9.4720e − 004
4.4480e − 004
9.6199e − 004
6.5851e − 004
Var energy
0.0213
0.0097
0.0210
0.0143
Var area
3.2485e − 005
1.9754e − 005
2.9491e − 005
3.6057e − 005


## 6. Conclusions

This research work shows the feasibility to apply the DEA in presence of obstacles or strict restrictions. Results obtained with the inner star show that the circles can be arranged even into the peaks of the star by using either large or small circles. Results could be improved if more restrictions are included, for instance, the area management on the peaks, where the smallest circle can be placed instead of the largest circles. Even so, the results seem promising.With respect to the presented cases with obstacles, the construction of the trees and the distribution and location of the nodes are feasible. The trees avoid crossing the obstacles and the circles have a separation among them and regarding the area boundaries. This is shown because the area obtained is greater than 90% for all the cases with a maximum overlap of 51%. The presented results can be improved if a restriction regarding the obstacles is adopted moving the circles away of the barriers, obtaining more useful area for each circle. Nonetheless, the DEA minimizes the wasted area by putting the neighbor nodes of the circle that lose its area coverage. This work is the initial step to study the distribution of sensor nodes in presence of obstacles, represented in this work as a set of given walls. An accurate modelling regarding the signal propagation and a larger separation among the nodes could also improve the results presented in this research work. As further work it is recommended to implement the flocking of multiagents with virtual leader technic described in Section1 in order to move the sensors in the network considering the position and velocity of the centre of mass of all sensors (agents). Also, it is important to implement the case with multiple leaders (containment control) focused on both switching networks and fixed networks described in Section 1, in which the input signals of sensors may be saturated in practice.



---

*Source: 7918581-2016-03-09.xml*