# Range-Based Positioning with Self-Adapting Fireworks Algorithm for Wireless Sensor Networks

Authors: Meigen Huang; Bin Yu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Positioning is the basic function of wireless sensor networks (WSN). At present, range-based positioning is a common method to obtain the position of a node, but its accuracy has encountered a bottleneck. The fundamental reason is that it ignores the ranging information between blind nodes. Therefore, based on the design of the positioning optimization factor to adjust the weight of the ranging information between the blind nodes, the positioning model of minimizing the error is established. On the basis of designing the blind node positioning matrix, the multiblind node localization problem is transformed into a single-objective optimization task, and the model also supports two-dimensional and three-dimensional positioning. In order to solve the model efficiently, we added a self-adaptive function that matches the positioning requirements for the explosion search mechanism of the fireworks algorithm (FWA) and then proposed a self-adaptive FWA (SA-FWA). The experimental results on the real ranging dataset show that the model has higher accuracy than other methods and achieves the current optimal positioning error, which is 1.88 m for received signal strength data and 1.02 m for time of arrival information, respectively.


---

## Body

## 1. Introduction

With the rapid development of the Internet of Things (IoT), wireless sensor networks (WSN) have been widely deployed, such as traffic flow sensing, target tracking and positioning, forest fire warning, and mine gas and drinking water monitoring [1–4]. In turn, these applications have also become important drivers of WSN’s growth.Positioning is the basic function of WSN [5]. Location services in WSN usually include node and target positioning [6]. The former means that the node obtains its own location through a certain method, while the latter refers to acquiring the position of the target outside the network. This paper focuses on the node positioning. Sensor information usually needs to be associated with location; otherwise, it may significantly reduce its actual value, such as forest fire alarm locations and water pollution pipelines [7].According to the reference information, the localization can be divided into range-free and range-based positioning [8]. However, the above two still have some similarities in the positioning process. First, the anchor node (known in position) publishes its own location (obtained by means of GPS or presets). Then, the blind node (the location is unknown) acquires the distance representation relationship with the anchor node. Note that the relationship can be either ranging information such as RSSI or nonranging information such as hops. Finally, the blind node calculates its own location according to certain conversion rules.Range-free positioning is an indirect type of estimated positioning [9]. Typical algorithms include DV-hop [10] and APIT [11]. The advantage of range-free positioning is that there is no need to deploy auxiliary hardware, so it has a lower cost. However, the drawback is that the positioning accuracy is usually lower. This also makes it impossible to apply to scenes that require a high-precision location.The advantages and disadvantages of range-based positioning are exactly the opposite of range-free positioning [12]. According to ranging information, classical range-based positioning algorithms include RSSI [13], time of arrival (TOA) [14], time difference of arrival (TDOA) [15], and angle of arrival (AOA) [16]. The distance conversion in TOA and TDOA algorithms is based on signal propagation time, so it requires specialized high-precision (nanosecond) time measurement hardware. In the AOA algorithms, the multiantenna array could measure the angle of arrival. Because RSSI could be directly measured without additional hardware, it becomes the most common range-based positioning method. However, the challenge is that its representation of distance is susceptible to signal propagation environments such as scattering and diffraction [17].Therefore, improving the accuracy of range-based positioning is crucial for WSN with high-precision location requirements. In the early research, based on the triangulation, the maximum-likelihood localization [18] improved the positioning accuracy from the spatial point of view by increasing the number of anchor nodes. From the perspective of time, the idea of cyclic positioning [19] could also effectively reduce the error by obtaining the ranging information multiple times, but it increases the energy consumption of the node. By measuring the internode RSSI and TOA data in the office environment (published as a public dataset), [20] derives the node location based on the Cramér-Rao bound and the maximum-likelihood estimators.In recent years, scholars have tended to improve the positioning accuracy by perfecting the position estimation methods. On the basis of centralized positioning, [21] uses the particle swarm optimization (PSO) to design a target positioning scheme suitable for high mobile environments in MANETs. Although it is assisted by mobile robots, the joint swarm intelligence algorithm and centralized positioning idea could achieve a perfect balance between energy consumption and precision improvement. Through the comprehensive application of RSSI and link quality indicator (LQI), [22] designed an artificial neural network (ANN) model based on Bayesian regularization and gradient descent, which is used to solve the problem of indoor mobile node location. For outdoor moving targets, [23] proposed a hybrid PSO-ANN algorithm, which proved that, compared with the traditional methods, the swarm intelligence algorithm has significant advantages in optimizing position estimation. Under the assumption that the measurement error distribution is unknown, [24] transforms the positioning problem into a nonconvex optimization problem and designs a distributed iterative method, but the accuracy still needs to be improved.In terms of swarm intelligence algorithms, the fireworks algorithm (FWA) designs an explosion search mechanism based on the proximity similarity and adjusts its global and local search ability through information exchange and resource allocation between sparks [25]. Positioning satisfies the proximity similarity, and the location optimization process is in line with the explosion search mechanism. And this is our motivation to introduce the FWA into position estimation process.In summary, although a large number of location optimization algorithms have been proposed, the current positioning accuracy is still unsatisfactory. The fundamental reason is that it ignores the ranging information between blind nodes. Therefore, in this paper, a mathematical model is built to minimize the positioning error for WSN by making full use of ranging information between all sensor nodes. To enhance the adaptability of explosion search mechanism, the self-adapting FWA (SA-FWA) is designed and used to solve the above model. In addition, we prove that the proposed algorithm eventually converges to the global optimal solution.The rest of the paper is organized as follows: Section2 establishes the mathematical model for node localization, and Section 3 solves the model with SA-FWA. The convergence of the algorithm is analyzed in Section 4. Section 5 designs the experiment and analyzes the results. Finally, Section 6 summarizes the paper.


## 2. Model Building

For ease of explanation, the positioning area is denoted asD. By characterizing the node position as a vector, the sensor node set is defined as C=c⟶kk=1,2,…,mc, c⟶k=ck1,ck2,…,ckv is the k-th sensor node, mc is the number of sensor nodes, and v is the coordinate dimension. In practical applications, v is usually taken as 2 or 3, corresponding to a two-dimensional plane and a three-dimensional space. Similarly, the anchor node set is denoted as A=a⟶ii=1,2,…,ma, a⟶i=ai1,ai2,…,aiv is the i-th anchor node and ma is the number of anchor nodes; the blind node set is defined as B=b⟶jj=1,2,…,mb, b⟶j=bj1,bj2,…,bjv is the j-th blind node and mb is the number of blind nodes. In the positioning system, the sensor node is either an anchor node or a blind node, so C=A∪B and A∩B=∅.Based on the above definitions, the ranging matrix is given as shown in Definition1.Definition 1.
The matrix of the measuring distance between all sensor nodes is called ranging matrix and is defined asM, as shown in (1)M=drc⟶k1,c⟶k2mc×mc,where dr is the measuring distance between nodes c⟶k1 and c⟶k2, 1≤k1≤mc, 1≤k2≤mc, and k1∈N,k2∈N. If k1=k2, drc⟶k1,c⟶k2=0, and if k1 and k2 are not adjacent, then drc⟶k1,c⟶k2 is infinite.
It is necessary to note that the ranging matrix only collects the measuring distance between the sensor nodes and does not limit the distance indication, such as signal path loss and signal propagation time. In extreme cases, neighbor relationships between nodes could also be roughly regarded as distance indications.
In the distance conversion, we give the treatment methods for common ranging information. For the RSSI, the log-distance path loss model is used, as shown in equation (2). For the TOA or TDOA, it is calculated as equation (3). One has(2)drb⟶j,c⟶k=d0×10RSSId0−RSSIb⟶j,c⟶k+Xσ/10q,(3)drb⟶j,c⟶k=tb⟶j,c⟶k×vtb⟶j,c⟶k.
In equation (2), RSSIb⟶j,c⟶k represents RSSI between b⟶j and c⟶k; RSSId0 denotes RSSI at reference distance d0 (usually 1 m); q is the path loss exponent, indicating the rate at which the signal propagation loss increases along the path with the distance, and the value is related to the environment in which the network is located; Xσ∼N0,1 characterizes environmental Gaussian noise.
In equation (3), tb⟶j,c⟶k represents the measuring time between b⟶j and c⟶k, and vtb⟶j,c⟶k is the signal transmission speed between nodes.
Improving the positioning accuracy means reducing the positioning error, and the concept of positioning error in this paper is shown in Definition2.Definition 2.
The difference of the measuring distance inM and the real geographic distance between neighboring nodes is called positioning error, denoted as d, and the calculation is shown as follows:(4)db⟶j,c⟶k=dgb⟶j,c⟶k−drb⟶j,c⟶k.
Nodec⟶k is located in the neighbor domain of node b⟶j. dg is the geographic distance between nodes and is characterized by Euclidean distance, as shown in (5)dgb⟶j,c⟶k=∑l=1vbjl−ckl2.
On this basis, considering the ranging information between blind nodes, the positioning mathematical model is established with the aim of minimizing the positioning error, shown as follows:(6)minfB=∑j=1mb∑k=1mcα×db⟶j,c⟶ks.t.drb⟶j,c⟶k≤Rα=1−βc⟶k∈Aβc⟶k∈Bβ∈0,1.
The model objective function is designed to minimize the sum of the positioning errors of all nodes. In the constraints,R is the node communication radius, so drb⟶j,c⟶k≤R limits b⟶j and c⟶k as neighbor nodes.
β is the optimization factor, which characterizes the sensitivity of the positioning error in the model to the ranging information between the sensor nodes, and its value has a great influence on the positioning accuracy. Generally, the larger the value of β, the greater the contribution of the ranging information between blind nodes to the positioning result, or the one between the blind node and the anchor node is more obvious. Note that β=0 means that the ranging information between blind nodes is ignored. Therefore, by properly adjusting β, the model can be adapted to a variety of application environments.


## 3. Range-Based Positioning with SA-FWA

The fitness function and operations are the foundation of FWA. In this section, on the basis of FWA, the SA-FWA is designed. First, the fitness function is first designed in combination with the location characteristics. Second, the operators are improved to enhance the adaptive search performance of FWA. Finally, the positioning process of applying SA-FWA to solve the model is given.


### 3.1. Fitness Function

Multinode positioning is essentially a multiobjective optimization problem. Therefore, we turn it into a single-objective optimization by constructing a blind node positioning matrix. Based on the matrix, the evolutionary elements in the SA-FWA are constructed, as shown in Definition3.Definition 3.
Fireworks, explosion, and mutation sparks are collectively referred to as evolutionary elements, denoted asE, and characterized by the blind node positioning matrix; namely, E=b⟶1;b⟶2;…;b⟶mb=bjlmb×v, l=1,2,…,v.
Obviously,E is a mb×v matrix, the row vector is the blind node, and its element is the node coordinate dimension (generally 2 or 3 dimensions).
Combined with the positioning model, the design of the fitness function for single-objective optimization can be expressed by(7)minfE=∑j1=1mb∑j2=1mbβ×db⟶j1,b⟶j2+∑j1=1mb∑i=1ma1−β×db⟶j1,a⟶is.t.b⟶j1,b⟶j2∈E;E∈Ddrb⟶j1,b⟶j2≠∅;drb⟶j1,a⟶i≠∅β∈0,1.
Note thatdb⟶j1,b⟶j2=dgb⟶j1,b⟶j2−drb⟶j1,b⟶j2 and db⟶j1,a⟶i=dgb⟶j1,a⟶i−drb⟶j1,a⟶i. In the constraints, drb⟶j1,b⟶j2≠∅;drb⟶j1,a⟶i≠∅ indicates that both blind node b⟶j2 and anchor node a⟶i should be neighbors of node b⟶j1, and b⟶j1,b⟶j2∈E;E∈D means that b⟶j1 and b⟶j2 need to be located in D.


### 3.2. Operators

The operators include self-adapting explosion (SE) operator, self-adapting mutation (SM) operator, and selection strategy, which together affect the search performance of SA-FWA.


#### 3.2.1. SE Operator

The SE operator is a concrete implementation of the explosion search mechanism. High-quality fireworks (small fitness values) could get more resources, and explosions in a small area generate a lot of sparks, which is convenient for local search. Conversely, low-quality fireworks (large fitness values) produce a small number of sparks (with less resources) in a large area, which facilitates the global search.Definition 4.
The operation of the fireworks adaptively generating explosion sparks is called SE operator and is defined asΦ:E⟶E+λ⟶AEθ⟶.
The SE operator is shifted by a polar coordinate system, andθ⟶ and λ⟶AE are polar angle matrix and polar radius matrix, respectively. θ⟶=θ⟶1,θ⟶2,…,θ⟶mbT, the j-th polar angle vector θ⟶j=cosθj1,sinθj1cosθj2,…,sinθj1sinθj2,…,sinθjv−1cosθjv, and θjl=rand0,2π. The random matrix λ⟶=λv×mb; λ=rand0,1. AEr is the explosion radius and is calculated by the fitness function, as shown in (8)AEr=Rω×fEr−fmin+ε∑r=1nfEr−fmin+ε.
fmin=minfE⟶, E⟶=Err=1,2,…,n is the fireworks swarm, n is the size of E⟶, ε is the machine precision, to avoid the operation of zero division, and ω is the self-adapting search factor that improves the search performance of the algorithm and can be obtained by (9)ω=ωmin+ωmax−ωminγ+ε.
In order to improve the adaptive search performance of the algorithm, the designedγ represents the evolution efficiency of SA-FWA, and γ≥1. At the same time, ωmax and ωmin are the maximum and minimum values of ω, respectively. Obviously, ω∈ωmin,ωmax, ω∝γ−1. Therefore, when the algorithm evolves faster, ω could effectively speed up the global search and vice versa quickly improve the local search accuracy.
According to the SE operator, fireworks could produce a specified number of sparks within the explosion radius, and the number of explosion sparks generated by ther-th fireworks Er can be expressed by (10)SEr=ω×mb×fmax−fEr+ε∑r=1nfmax−fEr+ε.
It is necessary to explain thatfmax=maxfE⟶.
SinceSEr is supposed to be an integer and the fireworks with a large (small) fitness value should be prevented from generating too little (much) sparks, SEr is corrected to S⌢Er, as shown in (11)S⌢Er=ceilh×ω×mb,SEr<h×ω×mb,roundSEr,SEr≥h×ω×mb,0<h<1.


#### 3.2.2. SM Operator

As a supplement to the SE operator, the SM operator could enhance the diversity of the fireworks swarm and prevent the algorithm from falling into local optimum. Therefore, the principle of mutation is that the smaller the fitness value of fireworks, the larger the mutation radius and the more the mutation sparks.Definition 5.
The operation of the fireworks adaptively generating mutation sparks is called SM operator and is defined asΓ:E⟶E+AE′e⟶.
The SM operator is shifted by a rectangular coordinate system. The Gaussian mutation matrixe⟶=e×roundrand0,1mb×v, e∼N1,1; AE′ is the mutation radius and is derived from the fitness function, as shown in (12)AEr′=R×fmax−fEr+ε∑r=1nfmax−fEr+ε.
According to SM operator, the fireworks could generate a specified number of sparks within the mutation radius. The number of mutation sparksSEr′ generated by Er can be expressed by (13)SEr′=δ×ω×mb×fmax−fEr+ε∑r=1nfmax−fEr+ε=δSEr.
δ∈0,1 is the mutation coefficient, which is used in conjunction with ω for the adjustment of SEr′. Similarly, it is corrected as SEr′⌢Er=ceilSEr′. Note that, to prevent SA-FWA from falling into local optimum when enhancing the adaptive search performance, ω only acts on the number of mutation sparks without affecting the mutation radius.
It should be noted that the sparks produced by the above operators may exceed the feasible domainD. Therefore, when the l-th coordinate dimension bjl is out of bounds, bjl is remapped into D by (14)bjl⟶bminl+bjl%bmaxl−bminl,where bmaxl and bminl are the maximum and minimum values of the l-th dimension in domain D and “%” is the modulo operator.


#### 3.2.3. Selection Strategy

After the sparks are generated, some excellent elements will be evolved into the next generation of fireworks swarm. According to the elite strategy, the elite corresponding tofmin in the evolutionary elements set K will evolve. Then, the remaining n−1 elements are generated using a roulette strategy. In order to enhance the evolutionary effect, the probability of being selected in roulette is determined by the degree of element crowding, and the probability pEr can be expressed by equation (15). Obviously, the denser the elements, the smaller the probability. One has(15)pEr=∑b⟶r∈Kdgb⟶r,b⟶s∑b⟶r∈K∑b⟶s∈Kdgb⟶r,b⟶s.


### 3.3. Positioning Process

Figure1 shows the process of range-based positioning with SA-FWA, including three phases of parameter acquisition, model solution, and result output.Figure 1
The process of range-based positioning with SA-FWA.The parameter acquisition phase includes the anchor node coordinates collection and the internode ranging information acquisition.The evolutionary efficiency of SA-FWA is closely related to swarm initialization. Therefore, we design three initialization strategies in the model solution phase, namely, random, dock, and trilateration strategy.(1)
Random strategy: the position of the initial population is randomly generated in the feasible region.(2)
Dock strategy: this strategy randomly selects the location of the neighbor anchor node as the initial coordinates for the blind node. If there is no neighbor anchor node, the blind node randomly stops at a neighbor blind node that completes initialization.(3)
Trilateration strategy: the blind node selects the three anchor nodes closest to itself and performs the traditional triangulation method to obtain an accurate initialization position. It is necessary to clarify that the closest requirement is to increase the reference value of the anchor node, while limiting the three anchor nodes is to minimize the computational overhead.Obviously, the complexity of the three strategies increases in turn, but the convergence speed of the algorithm decreases successively. The specific choice of strategy is related to the actual needs of positioning.Considering the energy efficiency and timeliness, the algorithm termination condition is set to the maximum number of iterationsw or the fitness value of elite evolutionary individual satisfies the same number of consecutive g times.In the result output phase, the positioning matrix of elite evolutionary individual generated by SA-FWA is parsed into the coordinates of each blind node, and the positioning optimization is completed.


## 3.1. Fitness Function

Multinode positioning is essentially a multiobjective optimization problem. Therefore, we turn it into a single-objective optimization by constructing a blind node positioning matrix. Based on the matrix, the evolutionary elements in the SA-FWA are constructed, as shown in Definition3.Definition 3.
Fireworks, explosion, and mutation sparks are collectively referred to as evolutionary elements, denoted asE, and characterized by the blind node positioning matrix; namely, E=b⟶1;b⟶2;…;b⟶mb=bjlmb×v, l=1,2,…,v.
Obviously,E is a mb×v matrix, the row vector is the blind node, and its element is the node coordinate dimension (generally 2 or 3 dimensions).
Combined with the positioning model, the design of the fitness function for single-objective optimization can be expressed by(7)minfE=∑j1=1mb∑j2=1mbβ×db⟶j1,b⟶j2+∑j1=1mb∑i=1ma1−β×db⟶j1,a⟶is.t.b⟶j1,b⟶j2∈E;E∈Ddrb⟶j1,b⟶j2≠∅;drb⟶j1,a⟶i≠∅β∈0,1.
Note thatdb⟶j1,b⟶j2=dgb⟶j1,b⟶j2−drb⟶j1,b⟶j2 and db⟶j1,a⟶i=dgb⟶j1,a⟶i−drb⟶j1,a⟶i. In the constraints, drb⟶j1,b⟶j2≠∅;drb⟶j1,a⟶i≠∅ indicates that both blind node b⟶j2 and anchor node a⟶i should be neighbors of node b⟶j1, and b⟶j1,b⟶j2∈E;E∈D means that b⟶j1 and b⟶j2 need to be located in D.


## 3.2. Operators

The operators include self-adapting explosion (SE) operator, self-adapting mutation (SM) operator, and selection strategy, which together affect the search performance of SA-FWA.


### 3.2.1. SE Operator

The SE operator is a concrete implementation of the explosion search mechanism. High-quality fireworks (small fitness values) could get more resources, and explosions in a small area generate a lot of sparks, which is convenient for local search. Conversely, low-quality fireworks (large fitness values) produce a small number of sparks (with less resources) in a large area, which facilitates the global search.Definition 4.
The operation of the fireworks adaptively generating explosion sparks is called SE operator and is defined asΦ:E⟶E+λ⟶AEθ⟶.
The SE operator is shifted by a polar coordinate system, andθ⟶ and λ⟶AE are polar angle matrix and polar radius matrix, respectively. θ⟶=θ⟶1,θ⟶2,…,θ⟶mbT, the j-th polar angle vector θ⟶j=cosθj1,sinθj1cosθj2,…,sinθj1sinθj2,…,sinθjv−1cosθjv, and θjl=rand0,2π. The random matrix λ⟶=λv×mb; λ=rand0,1. AEr is the explosion radius and is calculated by the fitness function, as shown in (8)AEr=Rω×fEr−fmin+ε∑r=1nfEr−fmin+ε.
fmin=minfE⟶, E⟶=Err=1,2,…,n is the fireworks swarm, n is the size of E⟶, ε is the machine precision, to avoid the operation of zero division, and ω is the self-adapting search factor that improves the search performance of the algorithm and can be obtained by (9)ω=ωmin+ωmax−ωminγ+ε.
In order to improve the adaptive search performance of the algorithm, the designedγ represents the evolution efficiency of SA-FWA, and γ≥1. At the same time, ωmax and ωmin are the maximum and minimum values of ω, respectively. Obviously, ω∈ωmin,ωmax, ω∝γ−1. Therefore, when the algorithm evolves faster, ω could effectively speed up the global search and vice versa quickly improve the local search accuracy.
According to the SE operator, fireworks could produce a specified number of sparks within the explosion radius, and the number of explosion sparks generated by ther-th fireworks Er can be expressed by (10)SEr=ω×mb×fmax−fEr+ε∑r=1nfmax−fEr+ε.
It is necessary to explain thatfmax=maxfE⟶.
SinceSEr is supposed to be an integer and the fireworks with a large (small) fitness value should be prevented from generating too little (much) sparks, SEr is corrected to S⌢Er, as shown in (11)S⌢Er=ceilh×ω×mb,SEr<h×ω×mb,roundSEr,SEr≥h×ω×mb,0<h<1.


### 3.2.2. SM Operator

As a supplement to the SE operator, the SM operator could enhance the diversity of the fireworks swarm and prevent the algorithm from falling into local optimum. Therefore, the principle of mutation is that the smaller the fitness value of fireworks, the larger the mutation radius and the more the mutation sparks.Definition 5.
The operation of the fireworks adaptively generating mutation sparks is called SM operator and is defined asΓ:E⟶E+AE′e⟶.
The SM operator is shifted by a rectangular coordinate system. The Gaussian mutation matrixe⟶=e×roundrand0,1mb×v, e∼N1,1; AE′ is the mutation radius and is derived from the fitness function, as shown in (12)AEr′=R×fmax−fEr+ε∑r=1nfmax−fEr+ε.
According to SM operator, the fireworks could generate a specified number of sparks within the mutation radius. The number of mutation sparksSEr′ generated by Er can be expressed by (13)SEr′=δ×ω×mb×fmax−fEr+ε∑r=1nfmax−fEr+ε=δSEr.
δ∈0,1 is the mutation coefficient, which is used in conjunction with ω for the adjustment of SEr′. Similarly, it is corrected as SEr′⌢Er=ceilSEr′. Note that, to prevent SA-FWA from falling into local optimum when enhancing the adaptive search performance, ω only acts on the number of mutation sparks without affecting the mutation radius.
It should be noted that the sparks produced by the above operators may exceed the feasible domainD. Therefore, when the l-th coordinate dimension bjl is out of bounds, bjl is remapped into D by (14)bjl⟶bminl+bjl%bmaxl−bminl,where bmaxl and bminl are the maximum and minimum values of the l-th dimension in domain D and “%” is the modulo operator.


### 3.2.3. Selection Strategy

After the sparks are generated, some excellent elements will be evolved into the next generation of fireworks swarm. According to the elite strategy, the elite corresponding tofmin in the evolutionary elements set K will evolve. Then, the remaining n−1 elements are generated using a roulette strategy. In order to enhance the evolutionary effect, the probability of being selected in roulette is determined by the degree of element crowding, and the probability pEr can be expressed by equation (15). Obviously, the denser the elements, the smaller the probability. One has(15)pEr=∑b⟶r∈Kdgb⟶r,b⟶s∑b⟶r∈K∑b⟶s∈Kdgb⟶r,b⟶s.


## 3.2.1. SE Operator

The SE operator is a concrete implementation of the explosion search mechanism. High-quality fireworks (small fitness values) could get more resources, and explosions in a small area generate a lot of sparks, which is convenient for local search. Conversely, low-quality fireworks (large fitness values) produce a small number of sparks (with less resources) in a large area, which facilitates the global search.Definition 4.
The operation of the fireworks adaptively generating explosion sparks is called SE operator and is defined asΦ:E⟶E+λ⟶AEθ⟶.
The SE operator is shifted by a polar coordinate system, andθ⟶ and λ⟶AE are polar angle matrix and polar radius matrix, respectively. θ⟶=θ⟶1,θ⟶2,…,θ⟶mbT, the j-th polar angle vector θ⟶j=cosθj1,sinθj1cosθj2,…,sinθj1sinθj2,…,sinθjv−1cosθjv, and θjl=rand0,2π. The random matrix λ⟶=λv×mb; λ=rand0,1. AEr is the explosion radius and is calculated by the fitness function, as shown in (8)AEr=Rω×fEr−fmin+ε∑r=1nfEr−fmin+ε.
fmin=minfE⟶, E⟶=Err=1,2,…,n is the fireworks swarm, n is the size of E⟶, ε is the machine precision, to avoid the operation of zero division, and ω is the self-adapting search factor that improves the search performance of the algorithm and can be obtained by (9)ω=ωmin+ωmax−ωminγ+ε.
In order to improve the adaptive search performance of the algorithm, the designedγ represents the evolution efficiency of SA-FWA, and γ≥1. At the same time, ωmax and ωmin are the maximum and minimum values of ω, respectively. Obviously, ω∈ωmin,ωmax, ω∝γ−1. Therefore, when the algorithm evolves faster, ω could effectively speed up the global search and vice versa quickly improve the local search accuracy.
According to the SE operator, fireworks could produce a specified number of sparks within the explosion radius, and the number of explosion sparks generated by ther-th fireworks Er can be expressed by (10)SEr=ω×mb×fmax−fEr+ε∑r=1nfmax−fEr+ε.
It is necessary to explain thatfmax=maxfE⟶.
SinceSEr is supposed to be an integer and the fireworks with a large (small) fitness value should be prevented from generating too little (much) sparks, SEr is corrected to S⌢Er, as shown in (11)S⌢Er=ceilh×ω×mb,SEr<h×ω×mb,roundSEr,SEr≥h×ω×mb,0<h<1.


## 3.2.2. SM Operator

As a supplement to the SE operator, the SM operator could enhance the diversity of the fireworks swarm and prevent the algorithm from falling into local optimum. Therefore, the principle of mutation is that the smaller the fitness value of fireworks, the larger the mutation radius and the more the mutation sparks.Definition 5.
The operation of the fireworks adaptively generating mutation sparks is called SM operator and is defined asΓ:E⟶E+AE′e⟶.
The SM operator is shifted by a rectangular coordinate system. The Gaussian mutation matrixe⟶=e×roundrand0,1mb×v, e∼N1,1; AE′ is the mutation radius and is derived from the fitness function, as shown in (12)AEr′=R×fmax−fEr+ε∑r=1nfmax−fEr+ε.
According to SM operator, the fireworks could generate a specified number of sparks within the mutation radius. The number of mutation sparksSEr′ generated by Er can be expressed by (13)SEr′=δ×ω×mb×fmax−fEr+ε∑r=1nfmax−fEr+ε=δSEr.
δ∈0,1 is the mutation coefficient, which is used in conjunction with ω for the adjustment of SEr′. Similarly, it is corrected as SEr′⌢Er=ceilSEr′. Note that, to prevent SA-FWA from falling into local optimum when enhancing the adaptive search performance, ω only acts on the number of mutation sparks without affecting the mutation radius.
It should be noted that the sparks produced by the above operators may exceed the feasible domainD. Therefore, when the l-th coordinate dimension bjl is out of bounds, bjl is remapped into D by (14)bjl⟶bminl+bjl%bmaxl−bminl,where bmaxl and bminl are the maximum and minimum values of the l-th dimension in domain D and “%” is the modulo operator.


## 3.2.3. Selection Strategy

After the sparks are generated, some excellent elements will be evolved into the next generation of fireworks swarm. According to the elite strategy, the elite corresponding tofmin in the evolutionary elements set K will evolve. Then, the remaining n−1 elements are generated using a roulette strategy. In order to enhance the evolutionary effect, the probability of being selected in roulette is determined by the degree of element crowding, and the probability pEr can be expressed by equation (15). Obviously, the denser the elements, the smaller the probability. One has(15)pEr=∑b⟶r∈Kdgb⟶r,b⟶s∑b⟶r∈K∑b⟶s∈Kdgb⟶r,b⟶s.


## 3.3. Positioning Process

Figure1 shows the process of range-based positioning with SA-FWA, including three phases of parameter acquisition, model solution, and result output.Figure 1
The process of range-based positioning with SA-FWA.The parameter acquisition phase includes the anchor node coordinates collection and the internode ranging information acquisition.The evolutionary efficiency of SA-FWA is closely related to swarm initialization. Therefore, we design three initialization strategies in the model solution phase, namely, random, dock, and trilateration strategy.(1)
Random strategy: the position of the initial population is randomly generated in the feasible region.(2)
Dock strategy: this strategy randomly selects the location of the neighbor anchor node as the initial coordinates for the blind node. If there is no neighbor anchor node, the blind node randomly stops at a neighbor blind node that completes initialization.(3)
Trilateration strategy: the blind node selects the three anchor nodes closest to itself and performs the traditional triangulation method to obtain an accurate initialization position. It is necessary to clarify that the closest requirement is to increase the reference value of the anchor node, while limiting the three anchor nodes is to minimize the computational overhead.Obviously, the complexity of the three strategies increases in turn, but the convergence speed of the algorithm decreases successively. The specific choice of strategy is related to the actual needs of positioning.Considering the energy efficiency and timeliness, the algorithm termination condition is set to the maximum number of iterationsw or the fitness value of elite evolutionary individual satisfies the same number of consecutive g times.In the result output phase, the positioning matrix of elite evolutionary individual generated by SA-FWA is parsed into the coordinates of each blind node, and the positioning optimization is completed.


## 4. Algorithm Convergence Analysis

According to the evolutionary algorithm theory [26], when SA-FWA satisfies the following two conditions, it will eventually converge to the global optimal solution and has nothing to do with the initial fireworks swarm.Condition 1.
The reachable probability between any two elements in the fireworks swarm is greater than 0.Condition 2.
The iterative evolution of the fireworks swarm is monotonous.
According to the positioning characteristics and fitness function, the global optimal solution of SA-FWA means that the positioning result is consistent with the ranging information as much as possible, rather than the true position of the node (RSSI and TOA may have acquisition errors).Theorem 1.
SA-FWA converges to the global optimal solution.Proof.
The key to the evolution of SA-FWA lies in the operator design, namely, SE operator, SM operator, and selection strategy. Therefore, the proposition is equivalent to proving that the above operators satisfy Conditions1 and 2.
For Condition1, in the evolution of each round, the feasible solution space of each element (blind node) is a circular area C with the node as the center and the communication radius R as the radius, as shown in Figure 2.
Based on the value of self-adapting search factorω , C could be divided into two parts: a circular area R/ω with a radius C1 and an annular area C2 with an inner diameter and an outer diameter of R/ω and R, respectively. According to the explosion radius AEr and the mutation radius AEr′, there are both explosion and mutation sparks in C1, and only mutation sparks may occur in C2. Therefore, in combination with the number of explosion and mutation sparks, the element reachable probability in C1 and C2 is shown in equation (16) and equation (17), respectively:(16)PC1=ω2×S⌢Er+S⌢Er′/ω2πR2,(17)PC2=S⌢Er′πR2×1−1ω2.
Combining the above two formulas, we can see thatPC1>PC2>0, so Condition 1 is satisfied.
For Condition2, the elite strategy in the selection strategy operation ensures that the optimal individual is evolved to the next generation. The rest of the individuals are based on the roulette strategy, and the probability of being selected is related to the degree of element crowding. Therefore, after each iteration of the algorithm, the next generation of optimal individuals either is the best one in the previous generation or has a smaller fitness value than it. As a result, the evolutionary results of the fireworks swarm are monotonic; that is, Condition 2 is satisfied.
In summary, SA-FWA satisfies the above two conditions and converges to the global optimal solution. Q.E.D.Figure 2
Feasible solution analysis.


## 5. Experiment and Result Analysis

To validate the performance of the proposed model and algorithm, this experiment is based on the open real dataset [20] and stimulated by MATLAB 2012a platform. The dataset collects RSSI and TOA data between 44 sensor nodes that are interconnected in the office environment. Therefore, the RSSI and TOA data are used, respectively, to conduct the experiment, and the influence of the value of positioning optimization factor β on the accuracy is analyzed. At the same time, by setting the node communication radius to limit the neighbor relationship, the model performance is further tested from the perspective of the intensity of ranging information.


### 5.1. Experimental Deployment

With the release of the dataset, the Cramér-Rao bounds of the positioning accuracy (0.76 m for the RSSI and 0.69 m for the TOA) were also given [20]. Based on the relaxation transform, [24] turned the positioning into a convex optimization problem and gave a distributed solution algorithm. Therefore, referring to the experimental settings of [20, 24], the sensor nodes no. 3, no. 10, no. 35, and no. 44 are selected as anchor nodes from the dataset, and all remaining sensor nodes are blind nodes. So ma=4 and mb=40. For ease of explanation, the positioning area D is set to a rectangular area with vertex coordinates of −5,−2, −5,14, 10,−2, and 10,14, respectively. In addition, the average positioning error is denoted as d¯ and is represented by the value of root mean square (RMS), as shown in equation (18). In addition, γ is characterized by the change of the elite fitness value, as shown in equation (19). t is the iteration number and t≥2. The values of other related parameters of the algorithm are shown in Table 1. One has(18)d¯=∑Ed2mb,(19)γ=fmint−1−fmint+1.Table 1
The relevant parameters and values.
ParameterValueR30 md01 mRSSId0−37.47 dBmg10v2δ0.30ωmax10h0.20n5q2.30vt299792458 m/sw350β0,1ε10−6ωmin1


### 5.2. Experimental Result

According to the deployment, the positioning experiments were performed based on the RSSI and TOA ranging information. The key to improving the positioning accuracy of the model is to introduce the ranging information between blind nodes. Considering the evolutionary efficiency of SA-FWA, swarm initialization uses the trilateration strategy.Therefore, the experimental results of the evolution ofd¯ with the number of iterations t under different β are shown in Figure 3, where (a) and (b) are the results for RSSI and TOA cases, respectively. For each β, the experiment was performed 10 times independently, and the final result was taken as the one closest to the mean of d¯.Figure 3
The experimental results ofd¯. (a) RSSI. (b) TOA.
(a)(b)In Figure3, for the RSSI and TOA cases, d¯ shows a decreasing trend in all β and finally ends at different values when the fitness value is the same for 10 consecutive times. Note that the occasional rise in the d¯ lies in the measurement error of the ranging information between the nodes.In Figure3(a), when the beta is 0.3, 0.5, and 0.7, d¯ converges to 2.06 m, 1.88 m, and 2.01 m, respectively, all of which are significantly better than the average positioning error of 2.18 m obtained in [20]. For the TOA case (Figure 3(b)), d¯ converges to 1.22 m, 1.02 m, and 1.19 m under the same conditions, which are better than the 1.23 m and 1.87 m given in [20, 24]. The experimental results are shown in Table 2.Table 2
The comparative results ofd¯.
SchemesRSSI (m)TOA (m)β=0.32.061.22β=0.51.881.02β=0.72.011.19[20]2.181.23[24]—1.87It can be seen from Table2 that d¯ is optimal when β=0.5. At this time, the positioning model is sensitive to the ranging parameters among all sensor nodes, which is consistent with the inconsistency of the nodes in the original dataset. To further verify the contribution of the ranging information between blind nodes to the proposed model, the experimental results of β=0.0 are given in Figure 3. This case is equivalent to the traditional positioning idea that does not consider the ranging parameters between blind nodes at all. At this time, the values of d¯ under the RSSI and TOA data are 3.07 m and 1.79 m, respectively. Moreover, the result is significantly inferior to the case of β>0.0. When β=0.0, the algorithm is less efficient. When the iteration reaches 164 times for the RSSI and 31 times for the TOA, the fitness value is no longer reduced. Therefore, the introduction of ranging information between blind nodes has a greater improvement in the performance of the positioning model.In order to visualize the algorithm results and analyze the blind node positioning error, the positioning results withβ=0.5 are shown in Figure 4, in which T (true) and E (estimated) represent the true position (given by the dataset) and the estimated location (given by the SA-FWA) of the node, respectively.Figure 4
The positioning result atβ=0.5. (a) RSSI. (b) TOA.
(a)(b)The positioning error in Figure4(a) shows that 90% of nodes d<3.0m, 70% of nodes d<2.0m, and 30% of nodes d<1.0m. The three sensor nodes with the smallest positioning error are no. 34 (d=0.19m), no. 25 (d=0.41m), and no. 14 (d=0.53m), and the three sensor nodes with the largest positioning error are no. 4 (d=4.08m), no. 1 (d=3.94m), and no. 37 (d=3.21m).Similarly, in Figure4(b), 100% of nodes d<3.0m, 97.5% of nodes d<2.0m, and 60% of nodes d<1.0m. The three nodes with the smallest positioning error are no. 9 (d=0.12m), no. 7 (d=0.29m), and no. 29 (d=0.29m), and the three nodes with the largest positioning error are no. 4 (d=2.08m), no. 39 (d=1.79m), and no. 24 (d=1.76m).From the above analysis, it can be found that TOA is significantly better than RSSI in distance characterization. However, the positioning error of blind node no. 4 in different ranging information is very prominent, and the result of this node is not ideal in [20]. Therefore, we boldly speculate that the collection of RSSI and TOA data associated with this node may be blocked by office walls or other objects, with large data acquisition errors.Finally, in order to test the dependence of the model on the node’s available ranging information, we simulate the variation of the ranging information between nodes by changing the node communication radiusR. Let R be 15 m, 20 m, 25 m, and 30 m, respectively, and the results of d¯ with β=0.5 are given as shown in Table 3.Table 3
The results ofd¯ with β=0.5.
R (m)d¯ (RSSI) (m)d¯ (TOA) (m)154.651.32203.211.14252.531.07301.881.02Obviously, the largerR is, the smaller d¯ is. This shows that the more the ranging information between sensor nodes, the better the performance of the positioning model, which is the reason for introducing the ranging information between blind nodes to improve the positioning accuracy. When R is small, the node has fewer neighbor nodes, so the ranging information between nodes is not dense enough. In addition, R will also affect the explosion and mutation radius of SA-FWA, which has a negative impact on the positioning results.


## 5.1. Experimental Deployment

With the release of the dataset, the Cramér-Rao bounds of the positioning accuracy (0.76 m for the RSSI and 0.69 m for the TOA) were also given [20]. Based on the relaxation transform, [24] turned the positioning into a convex optimization problem and gave a distributed solution algorithm. Therefore, referring to the experimental settings of [20, 24], the sensor nodes no. 3, no. 10, no. 35, and no. 44 are selected as anchor nodes from the dataset, and all remaining sensor nodes are blind nodes. So ma=4 and mb=40. For ease of explanation, the positioning area D is set to a rectangular area with vertex coordinates of −5,−2, −5,14, 10,−2, and 10,14, respectively. In addition, the average positioning error is denoted as d¯ and is represented by the value of root mean square (RMS), as shown in equation (18). In addition, γ is characterized by the change of the elite fitness value, as shown in equation (19). t is the iteration number and t≥2. The values of other related parameters of the algorithm are shown in Table 1. One has(18)d¯=∑Ed2mb,(19)γ=fmint−1−fmint+1.Table 1
The relevant parameters and values.
ParameterValueR30 md01 mRSSId0−37.47 dBmg10v2δ0.30ωmax10h0.20n5q2.30vt299792458 m/sw350β0,1ε10−6ωmin1


## 5.2. Experimental Result

According to the deployment, the positioning experiments were performed based on the RSSI and TOA ranging information. The key to improving the positioning accuracy of the model is to introduce the ranging information between blind nodes. Considering the evolutionary efficiency of SA-FWA, swarm initialization uses the trilateration strategy.Therefore, the experimental results of the evolution ofd¯ with the number of iterations t under different β are shown in Figure 3, where (a) and (b) are the results for RSSI and TOA cases, respectively. For each β, the experiment was performed 10 times independently, and the final result was taken as the one closest to the mean of d¯.Figure 3
The experimental results ofd¯. (a) RSSI. (b) TOA.
(a)(b)In Figure3, for the RSSI and TOA cases, d¯ shows a decreasing trend in all β and finally ends at different values when the fitness value is the same for 10 consecutive times. Note that the occasional rise in the d¯ lies in the measurement error of the ranging information between the nodes.In Figure3(a), when the beta is 0.3, 0.5, and 0.7, d¯ converges to 2.06 m, 1.88 m, and 2.01 m, respectively, all of which are significantly better than the average positioning error of 2.18 m obtained in [20]. For the TOA case (Figure 3(b)), d¯ converges to 1.22 m, 1.02 m, and 1.19 m under the same conditions, which are better than the 1.23 m and 1.87 m given in [20, 24]. The experimental results are shown in Table 2.Table 2
The comparative results ofd¯.
SchemesRSSI (m)TOA (m)β=0.32.061.22β=0.51.881.02β=0.72.011.19[20]2.181.23[24]—1.87It can be seen from Table2 that d¯ is optimal when β=0.5. At this time, the positioning model is sensitive to the ranging parameters among all sensor nodes, which is consistent with the inconsistency of the nodes in the original dataset. To further verify the contribution of the ranging information between blind nodes to the proposed model, the experimental results of β=0.0 are given in Figure 3. This case is equivalent to the traditional positioning idea that does not consider the ranging parameters between blind nodes at all. At this time, the values of d¯ under the RSSI and TOA data are 3.07 m and 1.79 m, respectively. Moreover, the result is significantly inferior to the case of β>0.0. When β=0.0, the algorithm is less efficient. When the iteration reaches 164 times for the RSSI and 31 times for the TOA, the fitness value is no longer reduced. Therefore, the introduction of ranging information between blind nodes has a greater improvement in the performance of the positioning model.In order to visualize the algorithm results and analyze the blind node positioning error, the positioning results withβ=0.5 are shown in Figure 4, in which T (true) and E (estimated) represent the true position (given by the dataset) and the estimated location (given by the SA-FWA) of the node, respectively.Figure 4
The positioning result atβ=0.5. (a) RSSI. (b) TOA.
(a)(b)The positioning error in Figure4(a) shows that 90% of nodes d<3.0m, 70% of nodes d<2.0m, and 30% of nodes d<1.0m. The three sensor nodes with the smallest positioning error are no. 34 (d=0.19m), no. 25 (d=0.41m), and no. 14 (d=0.53m), and the three sensor nodes with the largest positioning error are no. 4 (d=4.08m), no. 1 (d=3.94m), and no. 37 (d=3.21m).Similarly, in Figure4(b), 100% of nodes d<3.0m, 97.5% of nodes d<2.0m, and 60% of nodes d<1.0m. The three nodes with the smallest positioning error are no. 9 (d=0.12m), no. 7 (d=0.29m), and no. 29 (d=0.29m), and the three nodes with the largest positioning error are no. 4 (d=2.08m), no. 39 (d=1.79m), and no. 24 (d=1.76m).From the above analysis, it can be found that TOA is significantly better than RSSI in distance characterization. However, the positioning error of blind node no. 4 in different ranging information is very prominent, and the result of this node is not ideal in [20]. Therefore, we boldly speculate that the collection of RSSI and TOA data associated with this node may be blocked by office walls or other objects, with large data acquisition errors.Finally, in order to test the dependence of the model on the node’s available ranging information, we simulate the variation of the ranging information between nodes by changing the node communication radiusR. Let R be 15 m, 20 m, 25 m, and 30 m, respectively, and the results of d¯ with β=0.5 are given as shown in Table 3.Table 3
The results ofd¯ with β=0.5.
R (m)d¯ (RSSI) (m)d¯ (TOA) (m)154.651.32203.211.14252.531.07301.881.02Obviously, the largerR is, the smaller d¯ is. This shows that the more the ranging information between sensor nodes, the better the performance of the positioning model, which is the reason for introducing the ranging information between blind nodes to improve the positioning accuracy. When R is small, the node has fewer neighbor nodes, so the ranging information between nodes is not dense enough. In addition, R will also affect the explosion and mutation radius of SA-FWA, which has a negative impact on the positioning results.


## 6. Conclusions

Range-based positioning still faces major challenges in WSN with high-precision location requirements. In response to this, we established a mathematical model to minimize the positioning error by making full use of the ranging information between all sensor nodes. At the same time, the positioning optimization factor is designed to adjust the sensitivity of the model to the ranging information between blind nodes. Considering the similarity between the positioning optimization process and the explosion search mechanism, we use the FWA to solve the model. By the way, we improved the self-adaptive search performance of FWA, thus achieving a win-win situation between positioning accuracy and operation time. It is necessary to explain that, due to the design of the blind node positioning matrix, the model supports two-dimensional and three-dimensional positioning. At the same time, the convergence of the algorithm is analyzed. Finally, the average positioning errors of 1.88 m for RSSI and 1.02 m for TOA are achieved by experimenting with the real ranging dataset. In addition, the simulation results of the proportional change of the ranging information indicate that considering the ranging information between blind nodes is the key to the performance improvement of the model.It is necessary to clarify that the above accuracy is the optimal value currently achieved on the dataset but still has not reached the ideal state. The root cause is that the dataset is collected from a real indoor office environment that is greatly blocked by walls and staff, and the ranging data collection error is large. However, this is consistent with the actual application environment of WSN, and the zero error acquisition is unrealistic.



---

*Source: 9286438-2020-08-20.xml*