Node Distribution Optimization in Positioning Sensor Networks through Memetic Algorithms in Urban Scenarios ^†

Abstract

Local Positioning Systems rely on ad-hoc node deployments which fit the environment characteristics in order to reduce system uncertainties. The obtainment of competitive results through these systems requires the solution of the Node Location Problem. This problem has been assigned as NP-Hard; therefore, a heuristic solution is recommended for addressing this complex problem. Genetic Algorithms (GA) have shown an excellent trade-off between diversification and intensification in the literature. However, in Non-Line-of-Sight environments in which there is not continuity in the fitness function evaluation among contiguous solutions, challenges arise for the GA. Consequently, in this paper, we introduce a Memetic Algorithm (MA) with a Local Search strategy for exploring the most different individuals of the population in search of improving the NLP results in urban scenarios for the first time. Results show that the MA proposed outperforms the GA optimization and attains an improvement of 6.51% in accuracy in the scenario proposed.

1. Introduction

Local Positioning Systems (LPS) have attracted high research interest in recent years [1]. Their interest relies on the proximity among target and architecture sensors reducing the uncertainties of the Global Navigation Satellite Systems (GNSS) for high-demanded accuracy applications such as precision farming, indoor navigation or automatic vehicle guidance.

LPS are categorized through the physical property measured for locating the target: time, phase, power, angle, frequency or combinations of them. Among these systems, time-based localization stands since they have the better trade-off among accuracy, robustness, availability, hardware implementation and costs. As a consequence, time-based local applications in precision contexts are the most extended in the literature [2].

There are different time-based configurations: Time of Arrival (TOA) [3], Time Difference of Arrival (TDOA) [4] or Asynchronous Time Difference of Arrival (A-TDOA) [5]. We have shown in our previous studies [6] that the synchronization effects have the most important relevance in the system uncertainties in LPS; thus, TDOA architectures are the most appropriate for local precision applications since these configurations are independent from the emission timestamp allowing the avoidance of the synchronism of the system clocks with the target. In this paper, we analyze the deployment of a synchronous TDOA architecture in urban scenarios for their extended use in the literature.

TDOA systems are based on the measurement of the relative time among the reception of a positioning signal in two different devices. Hyperboloid equations are generated as possible spatial target locations, and at least four equations (i.e., five sensors) are needed to mathematically solve the localization problem although the problem can be addressed with four sensors [7] through an optimized node distribution.

However, regardless of the architecture used, LPS are only applicable for precision applications under optimized sensor locations which reduce the system uncertainties and adapt to the characteristics of the environment in which they are deployed. Therefore, an ad-hoc sensor distribution must be achieved, and this requires the solution of the Node Location Problem (NLP), which is a combinatorial problem [8] that has been assigned as NP-Hard [9]. Due to the complexity of the NLP, a heuristic approach is required for achieving practical results. Dolphin swarm optimization [10], elephant herding optimization [11] or simulated annealing [12] have been used for the NLP but especially Genetic Algorithms (GA) [13] and Memetic Algorithms (MA) [14] stand due to their balanced exploration and intensification of the space of solutions.

These heuristic techniques for the NLP require an optimization function for determining the quality of every node distribution. In the localization field, the Cramèr-Rao Bound (CRB) is widespread [15,16] since it represents the minimum achievable error by any positioning algorithm applied for calculating the target location. This maximum likelihood indicator allows a characterization of the ranging [17,18] and clock errors [6] and it is not derivable in the entire coverage area of the LPS [19]; thus, the heuristic approach to the NLP is also recommended.

However, the application of an evolutionary optimization for the NLP is particularly complicated in Non-Line-of-Sight (NLOS) environments in which the evaluation of the adaptation of the individuals among contiguous solutions (e.g., solutions which vary minimally in the location of a unique sensor in one spatial coordinate) can vary profoundly due its dependency on the obstacle geometry and their obstruction of the link between a possible target location and an architecture sensor node.

As a consequence, we introduced in [14] an MA with a local search procedure for exploring potentially unfavored regions of the space of solutions, and in this paper, we applied the MA for the first time in an urban scenario in which the presence of buildings notably affects the traditional Genetic Algorithm performance on the NLP.

The remainder of the paper is organized as follows: we introduce the Cramèr-Rao Bound model for considering the clock and noise errors of the TDOA architecture in Section 2; we define the signal parameters of the optimization and the scenario of simulations in Section 3; we describe the MA in Section 4; the results are presented in Section 5, and the conclusions are discussed in Section 6.

2. Cramèr-Rao Bound for the TDOA Architecture

CRB is the most common metric for characterizing the quality of a node distribution in the localization field [15]. Its use is widespread since it provides the least achievable error by any positioning algorithm in a defined sensor distribution. In [15], a CRB matrix form was introduced that, in LPS, requires a heteroscedastic noise consideration [16] in the covariance matrix of the architecture at study since the positioning signal path notably varies among the architecture sensors:

$$J_{mn}={\left(\frac{\partial h\left(TS\right)}{\partial T{S}_m}\right)}^T{\mathit{R}}^{\mathbf{-}\mathbf{1}}\left(\mathit{T}\mathit{S}\right)\left(\frac{\partial h\left(TS\right)}{\partial T{S}_n}\right)+\frac{1}{2}tr\left({\mathit{R}}^{\mathbf{-}\mathbf{1}}\left(\mathit{T}\mathit{S}\right)\left(\frac{\partial R\left(TS\right)}{\partial T{S}_m}\right){\mathit{R}}^{\mathbf{-}\mathbf{1}}\left(\mathit{T}\mathit{S}\right)\left(\frac{\partial R\left(TS\right)}{\partial T{S}_n}\right)\right)$$

(1)

where J_mn represents the Fisher Information Matrix (FIM) element, whose inverse is the CRB; R is the covariance matrix of the system in which the uncertainties are characterized; h is the vector containing the information of the time measurements of the TDOA architecture; TS is the target sensor; and m and n are the spatial coordinates of the target sensor considered.

This covariance matrix must be modeled according to the system uncertainties: noise in Line-of-Sight (LOS) and NLOS environments [18] and clock errors [6]. In the TDOA architecture, the time measurements are correlated [20,21]; therefore, a complete characterization of the covariance matrix must be accomplished:

$$\begin{gathered} h_{TDO{A}_i}=\Vert TS-C{S}_i\Vert -\Vert TS-C{S}_j\Vert \\ i=1,\dots , N_{cs} j=1, \dots , N_{CS} i\ne j \end{gathered}$$

(2)

$$\begin{gathered} {\sigma }_{TDO{A}_{ij}}{}^2=\frac{c^2}{B^2\left(\frac{P_T}{P_n}\right)}PL\left(d_0\right){\left[{\left(\frac{d_{i_{LOS}}}{d_0}\right)}_{C{S}_i}+{\left(\frac{d_{i_{NLOS}}}{d_0}\right)}_{C{S}_i}{}^{\frac{n_{NLOS}}{n_{LOS}}}+\left(\frac{d_{j_{LOS}}}{d_0}\right)+{\left(\frac{d_{j_{NLOS}}}{d_0}\right)}^{\frac{n_{NLOS}}{n_{LOS}}}\right]}^{n_{LOS}} \\ +\frac{1}{l}{\displaystyle \sum }_{k=1}^l\left\{\left|T_i-floo{r}_{TR}\left(T_i+U_i-U_0+T_0\left({\eta }_i-{\eta }_0\right)+T_i{\eta }_i\right)\right|c^2\right\} \\ +\frac{1}{l}{\displaystyle \sum }_{k=1}^l\left\{\left|T_j-floo{r}_{TR}\left(T_j+U_j-U_0+T_0\left({\eta }_j-{\eta }_0\right)+T_j{\eta }_j\right)\right|c^2\right\} \end{gathered}$$

(3)

where $C{S}_i$ and $C{S}_j$ are the coordinator sensors in which the positioning signal is received for collecting a time measurement; $N_{CS}$ is the number of sensors in which the positioning signal is received from a determined TS location; $c$ is the speed of the radioelectric waves; $B$ is the signal bandwidth; $P_T$ is the signal transmission power; $P_N$ is the mean noise level; $PL\left(d_0\right)$ is the path-loss in the reference distance ($d_0$) from which the Log Normal path loss model of [17] is applied; $d_{i_{LOS}},d_{i_{NLOS}},d_{j_{LOS}}and{d}_{j_{NLOS}}$ are the distances from the TS to the $C{S}_i$ and $C{S}_j$ in LOS and NLOS conditions, respectively, calculated, through the algorithm introduced in [18]; $n_{LOS}$ and $n_{NLOS}$ are the path loss exponents in LOS and NLOS conditions; l is the number of iterations of the Monte Carlo simulation for estimating the clock uncertainties [6]; $T_i$ and $T_j$ are the total time of flight of the positioning signal from target to the $C{S}_i$ and $C{S}_j$ and $U_i$, $U_j$ and $U_0,$ and ${\eta }_i,{\eta }_j$and ${\eta }_0$ are the initial time offset and the drift of the $C{S}_i$, $C{S}_j$ and the reference clock for the system synchronization, respectively.

3. The Scenario of Simulations

In this paper, we deployed a terrestrial LPS TDOA architecture used for outdoor positioning. We define in

Table 1. The values of parameters in the urban scenario configuration.

Parameter	Magnitude	Units
Frequency of emission	5.465	GHz
Transmission power	1	W
Bandwidth	100	MHz
Receptor sensibility	−90	dBm
Mean noise power	−94	dBm
LOS path loss exponent	2.1 1
NLOS path loss exponent	4.1 2
Clock frequency	1	GHz
Frequency–drift	U{−15, 15}	ppm
Time–frequency product	1

^1,2 Path-loss exponents used in the Log-Normal model.

the signal and clock parameters of the TDOA architecture for the NLP optimization in urban scenarios.

These parameters established the framework of the study. The urban scenario is modeled in Figure 1. We defined two different regions for the optimization [13]: the Node Location Environment (NLE)—the possible locations for the architecture sensors—and the Target Location Environment (TLE)—the covered region for the navigation of the targets. These regions were discretized for preserving the representativity of the space of solutions achieving optimal time-effective results [18].

The optimization of the TDOA architecture node distribution in the presented scenario considers noise and clock errors, the path losses in NLOS and LOS environments and the effective coverage of the sensors.

4. Memetic Algorithm

The MA uses a GA combined with a local search procedure to obtain an optimized sensor distribution in the NLP problem. GA allows the exploration of the space of solutions through an evolutionary optimization process based on the genetic operators (crossover, selection and mutation).

The variables for this heuristic optimization are the Cartesian coordinates of the location of the architecture sensors of the TDOA architecture through a binary codification for facilitating the performance of the GA operators [13]. In this scenario, we consider an eleven-sensor optimization which has proved to reach the global coverage of every TLE point analyzed. The quality of each individual of the population was measured through a fitness function evaluation considering the Root Mean Square Error (RMSE), which was obtained through the trace of the CRB model [17]:

$$ff=1-{\left(\frac{\overline{RMSE}}{RMS{E}_{ref}}\right)}^2$$

(4)

where $RMSEref$ represents the maximum RMSE value for a TLE analyzed point, thus keeping the ff values in the interval [0, 1].

However, the solution of the NLP in Non-Line-of-Sight (NLOS) environments showed discontinuities in the analysis of the space of solutions. Therefore, we proposed an MA optimization [14] for exploring potentially unfavored regions in the evolutionary process through the application of a Variable-Neighborhood Descent (VND) LS to the most different regions obtained through the Hamming distance and the elite individuals of the population keeping the balance between diversification and intensification, respectively [14]. Due to this LS methodology, we searched for the most promising individuals within a limited solution environment, which may not be accessible through the evolutionary process and the GA’s operators.

Variable-Neighborhood Descent Local Search

The VND LS explores the neighborhood to obtain the best-adapted individual in a bounded region. In each iteration, 26 potential movements for each sensor were explored.

The analysis of the fitness in the VND algorithm was performed through a pseudo-fitness function. The pseudo function allows a reduction in the time complexity of each evaluation, and it is based on the exclusive analysis of the LOS/NLOS links of the positioning signal paths without considering the clock and the geometric uncertainties, since they remain practically constant in the neighborhood.

$$f{f}_{LS}=\frac{1}{{{\displaystyle \sum }}_{k=1}^T{{\displaystyle \sum }}_{i=1}^N\left[d_{iLOS}^{nLOS}+d_{iLOS}^{nLOS}\right]+{{\displaystyle \sum }}_{k=1}^T{{\displaystyle \sum }}_{j=1}^N\left[d_{jLOS}^{nLOS}+d_{jLOS}^{nLOS}\right]}$$

(5)

5. Results

The results obtained in this paper, verify that MA optimization allows the enhancement of the overall performance of the TDOA architecture and reduces the RMSE of the sensor distribution.

We present in

Table 2. Mean of the Root Mean Square Error (RMSE) in the TLE analyzed points in the scenario of simulations.

Number of Nodes	Genetic Algorithm	Memetic Algorithm
9	4.30	4.02

the accuracy results achieved by the MA in the TLE analyzed points showing the robustness of the architecture for its application in NLOS urban contexts.

Figure 2 shows the evolution of the fitness function of the MA optimization.

Finally, we represent in Figure 3 the optimal node configuration obtained through the MA optimization introduced in this manuscript.

6. Conclusions

Local Positioning Systems are attracting research interest for high-demand accuracy applications such as underwater localization or autonomous vehicle guidance. Their relevance relies on the ad-hoc deployment of sensors for reducing the uncertainties of the system operation. This requires the solution of the Node Location Problem which has been assigned as NP-Hard. Genetic Algorithms have shown an excellent adaptation for this problem for their balance between diversification and intensification, but they suffer in NLOS environments due to the discontinuity in the fitness function evaluation among continuous solutions. In this paper, we propose a Memetic Algorithm for dealing with these discontinuities in the evolutionary Node Location Problem of the TDOA architecture in an urban scenario for the first time. Results show an improvement in the Memetic Algorithm of 6.51% with regard to the Genetic Algorithm in the proposed scenario.