-The lack of techniques and tools to estimate the position of mobile devices with high accuracy and robustness is one of the major causes that limit the provision of advanced location-based services in indoor environments. An algorithm to enable mobile devices to estimate their positions in known indoor environments is discussed in this paper under the assumption that fixed network nodes are available at known locations. The discussed algorithm is designed to allow devices to estimate their positions by actively measuring the distances from visible fixed nodes. In order to reduce the errors introduced by the arrangement of the fixed nodes in the environment, the discussed algorithm transforms the localization problem into an optimization problem, which is then solved using interval arithmetic. Experimental results on the use of the discussed algorithm with distance estimates obtained using ultra-wide band are presented to assess the performance of the algorithm and to compare it with a reference alternative. Presented experimental results confirm that the discussed algorithm provides an increased level of robustness with respect to the considered reference alternative with no loss of accuracy. Index Terms-localization as optimization, indoor localization, ultra-wide band, software agents
The possibility of robustly associating an accurate position with a mobile device in an indoor environment has recently become a major feature needed to increase the level of personalization of services and applications offered to users (e.g., [1]–[3]). Robust and accurate indoor localization can be used, for example, to personalize and increase the interactivity of visits to art exhibitions by means of educational games (e.g., [4]), it can be used to support the automation of work in warehouses (e.g., [5]), and it can be used to extend the services of location-based social networks (e.g. [6]) to large indoor areas like shopping malls, train stations, and airports. Solutions to problems related to indoor localization can be found in recent literature (e.g., [7]–[9]), but the general problem of enabling a mobile device to accurately and robustly estimate its position in a known environment is still an open issue (e.g., [10], [11]) even if specific technologies like Ultra-Wide Band (UWB) (e.g., [12], [13]) are readily available.
Software agents are expected to play a relevant role in the delivery of mentioned services and applications (e.g., [14]) because agents are normally characterized as situated entities capable of exhibiting context-aware behaviors. With this respect, the position can be considered as just another context information that agents can use to bring about their goals. Therefore, the use of the position to enrich the behaviors of agents is expected to be simple and effective. This is the reason why the algorithm used to run the experiments documented in this paper was implemented as an extension of the localization add-on module (e.g. [15]) for JADE (e.g., [16]). The localization add-on module for JADE is responsible for providing timely information to agents regarding their positions using one of the available localization algorithms. Actually, the localization add-on module extends a JADE container (e.g., [16]) executed on a mobile device with the possibility of interfacing the sensors of the device to obtain the low-level information needed to apply the chosen localization algorithm. The estimated position of the device is then passed to interested agents hosted by the container so that they can use it to bring about their goals. Note that, besides available localization algorithms, additional algorithms like the one discussed in this paper can be easily integrated in the add-on module provided that they implement a specific Java interface.
The discussions in this paper are focused on the general problem of allowing a mobile device, denoted as Target Node (TN), to estimate its position inside an indoor environment with known geometry under the assumption that fixed network nodes, denoted as Anchor Nodes (ANs), are installed at known locations. One of the major assumption of this work is that mobile devices can actively measure the distances from the ANs installed in the environment using one of the available ranging technologies. An average error of 1 m in the estimation of positions is considered acceptable for targeted application scenarios, and experimental results discussed in Section V show that such an accuracy is feasible using the discussed localization algorithm when ranging information are obtained using UWB. With minor loss of generality, it is assumed that the considered indoor environment is composed of possibly overlapping rectangular cuboids, called boxes in this paper to follow a consolidated nomenclature. Under this assumption, it is possible to focus the hunt for TNs in the environment on the single boxes that compose the environment, and therefore the localization problem can be simplified by considering only box-shaped environments. Observe that the minimum bounding box containing the considered environment can be used if the environment cannot be split into boxes, but, in this case, estimated positions of TNs should be filtered accordingly. One of the problems that make indoor localization difficult is related to the fact that the positions of ANs in the environment strongly affect the accuracy of ordinary localization algorithms (e.g., [17], [18]), like the Two-Stage MaximumLikelihood (TSML) [19] algorithm discussed in Section V. In particular, a significant loss of the accuracy provided by such algorithms is normally observed when ANs are not positioned properly in the environment. Such a problematic characteristic of ordinary localization algorithms is critical for indoor environments because ANs are normally located near the ceilings of rooms, which is an arrangement that exacerbates the mentioned problem. The choice of installing all ANs at (roughly) the same height near the ceilings of rooms degrades the performance of ordinary localization algorithms because some of the matrices involved in computations become strongly illconditioned (e.g., [5], [20]). Unfortunately, the choice of the positions of ANs in indoor environments is often dictated by practical considerations intended, for example, to limit the interference caused by people and furniture, and to maximize coverage. Therefore, the positions of ANs cannot be changed just to limit the mentioned problem of ordinary localization algorithms. The remainder of this paper is devoted to study the robustness of an alternative algorithm in situations in which the accuracy of ordinary algorithm degrades sensibly. Experimental results presented in Section V show that the accuracy of the studied algorithm is acceptable even when the accuracy of the TSML algorithm, which is used as a point of reference, degrades sensibly.
This paper is organized as follows. Section II introduces adopted notation. Section III describes the adopted approach to localization. Section IV describes the discussed algorithm and briefly presents its characteristics. Section V reports the results of the experimental campaign performed to assess the robustness of the studied algorithm. Finally, Section VI concludes the paper.
II. NOTATION
This section summarizes the notation commonly used to study real functions of several real variables, as it is used to present the localization problem and the discussed algorithm in the following sections. The set of natural numbers, including zero, is denoted as N and the set of positive natural numbers is denoted as N+. Given n ∈ N+, a multi-index I ∈ Nn is defined as an n−tuple of natural numbers n
I = (i1, i2, . . . , in) = (ik)k=1.
Note that it is a common notation to use an uppercase letter to denote a multi-index and to use the same letter, but lowercase and with a subscript, to denote its components. The following notation is adopted to use a multi-index I ∈ Nn as an exponent for t ∈ Rn with t = (t1, t2, . . . , tn) = (tk)kn=1 n tI = Y tikk .
k=1
Note that it is a common notation to use a boldface letter
to denote an n−tuple of real numbers, and the same letter,
(
Given two multi-indices I ∈ Nn and J ∈ Nn, they can be compared using the following partial order
I ≤ J ⇐⇒ i1 ≤ j1 ∧ i2 ≤ j2 ∧ · · · ∧ in ≤ jn and they can also be added componentwise
I + J = (i1 + j1, i2 + j2, . . . , in + jn).
The following abbreviation is introduced for multi-indices H ∈ Nn, I ∈ Nn, and J ∈ Nn to express repeated sums X (·)
= H≤I≤J j1 X j2 X · · · jn
X (·).
i1=h1 i2=h2
in=hn
Note that H is omitted in (
The multi-index notation is particularly well-suited to study
polynomial functions. A polynomial function p : Rn 7→ R of
n ∈ N+ real variables with real coefficients can be written as
(
Observe that the localization algorithm discussed in this
paper works by studying the bounds of polynomial functions
over boxes. Hence, it is worth recalling the following notation
for intervals and boxes. A closed (real) interval from a ∈ R
to a ∈ R is denoted as
[a, a] = {x ∈ R : a ≤ x ≤ a},
(
Interval arithmetic (e.g., [21]) uses the introduced
notation to express computations whose arguments and results
are closed intervals. Given two nonempty closed intervals
A = [a, a] ⊂ R and C = [c, c] ⊂ R, they can be added
A + C = [a + c, a + c],
(
A · C = [min{a c, a c, a c, a c}, max{a c, a c, a c, a c}]. (
j=1
Using the introduced notation, which is typical of interval
arithmetic, a polynomial function p : Rn 7→ R of n ∈ N+
real variables with real coefficients can be extended to work
on boxes. If the function is expressed as in (
X[aI ]BI , I≤L where the notation for singleton intervals is used to treat the coefficients of the polynomial function as closed intervals. Observe that it is easy to prove that the result of the evaluation of p(B) is a closed interval that includes the range of p over box B (e.g. [21]).
in previous works (e.g., [5], [20]) with the aim of reducing
the loss of accuracy that characterizes ordinary algorithms
for critical arrangements of the ANs, as briefly recalled in
Section I. The localization as optimization approach is based
on the possibility of rewriting any localization problem into a
related optimization problem, which can then be solved using
one of the algorithms documented in the vast literature on
optimization. Observe that many of the optimization
algorithms available in the literature still have problems related
to ill-conditioned matrices. Therefore, specific attention must
be paid to the choice of a proper optimization algorithm in
order to guarantee that the reformulation of the localization
problem in terms of an optimization problem would lead to
high accuracy in scenarios where the arrangements of ANs is
critical. This is the reason why, among the large number of
optimization algorithms, the use of Particle Swarm Optimization
(PSO) [22] was chosen for initial experiments. Experimental
results (e.g., [5], [20]) showed that the use of PSO to
implement localization as optimization proved to be effective in
solving the loss of accuracy caused by critical arrangements
of ANs. Unfortunately, PSO has two severe issues that limits
its applicability to solve practical localization problems. First,
just like all other general optimization algorithms, PSO does
not guarantee that global extrema of studied functions are
computed in finite time. Second, the performance of the PSO
algorithm depends on a set of parameters whose optimal
values can be determined only by simulating the behavior
of the algorithm in the considered environment. Therefore,
alternatives to the use of PSO to implement localization as
optimization are under experimentation. Among them, the
(
A set of m ≥ 4 ANs is positioned at fixed and known locations in the considered indoor environment. The position of the i−th AN is denoted as ai ∈ R3 with 1 ≤ i ≤ m. The true position of the TN is denoted as t ∈ R3, and the true distance between the TN and the i−th AN is
ri = ||t − ai||.
Note that (
Note that (
a⊺ A = a...⊺2 .
m The geometry of the problem suggests that the position of the TN can be found by intersecting m spheres, the i−th of which is centered at ai and has radius ri The localization problem is the problem of finding estimates of the position of the TN provided that the distances between the TN and each AN are estimated using one of the available ranging technologies. The estimated position of the TN is denoted as ˜t ∈ R3, while the estimated distance between the TN and the i−th AN is
r˜i = ||˜t − ai||.
Therefore, the estimated position ˜t of the TN is expected to
satisfy the following system of nonlinear equations, which is
obtained by exchanging the true values with their
corresponding estimated values in (
2 ||t − a2||2 = r2
2 . .
. 2 ||t − am||2 = rm ||˜t − a1||2 = r˜1
2 ||˜t − a2||2 = r˜2
2
2
||˜t − am||2 = r˜m
Many localization algorithms (e.g., [18]) perform algebraic
manipulations of matrices whose entries depend on the
positions of the TN and of the ANs. The matrices involved
in such computations can become ill-conditioned in critical
situations, and this represents one of the inherent problems
of such algorithms. For example, it is evident from (
If (
The Polynomial Optimization using Subdivision Trees (POST) algorithmic framework is introduced in an upcoming paper as an effective means to support the localization as optimization approach described in previous section. The POST framework is completed with a suitable method to compute lower and upper bounds of polynomial functions to obtain an algorithm to solve the minimization problems derived from localization problems. In this paper, the instantiation of the POST framework that uses interval arithmetic to compute lower and upper bounds of polynomial functions over boxes, normally called POSTI algorithm, is described. The experimental results presented in Section V were obtained using an implementation of the POSTI algorithm integrated within the localization add-on module for JADE recalled in Section I.
The POSTI algorithm uses classic results from the literature
on interval arithmetic (e.g., [21]) to compute lower and upper
bounds of a given polynomial function over a given box. Then,
the POSTI algorithm uses such bounds to drive an ordinary
subdivision method to solve the minimization problem at hand.
In detail, the POSTI algorithm is based on the possibility of
rewriting a localization problem into a related optimization
problem that aims at finding a global minimum of the
localization cost function f defined in (
Note that the accuracy of the POSTI algorithm does not depend on the positions of the TN or of the ANs, and therefore it can be used when the accuracy of ordinary algorithms, like the TSML algorithm, degrades sensibly. In addition, note that experimental results discussed in Section V show that the POSTI algorithm ensures an accuracy of localization comparable to the accuracy of the TSML algorithm when the arrangement of ANs is not critical. The comparison with the TSML algorithm is particularly relevant because the TSML algorithm is an accepted reference to assess the performance of localization algorithms. Actually, the TSML algorithm is particularly relevant in the context of localization because it is proved [23] that it can attain the Crame´r-Rao lower bound [24] for the position estimator.
The literature on nonlinear programming proposes several
algorithms to minimize a polynomial function. When the
minimum is searched in a box, as in the scenarios considered
in this paper, most of the minimization algorithms make use
of the properties of the Bernstein polynomial basis (e.g., [25]
for a comprehensive review of the subject and a historical
retrospective). Actually, well-known properties of the Bernstein
polynomial basis can be used to compute lower and upper
bounds of a polynomial function over a given box, and such
bounds can be used to drive the subdivision of the box using
a branch-and-bound approach in search for a global minimum
(e.g., [26]). In particular, for each subdivision, the so called
Bernstein coefficients are computed on the two resulting
subboxes, and such coefficients are used to obtain the needed
lower and upper bounds of the polynomial function for the two
sub-boxes. Unfortunately, such an approach is problematic in
terms of computational cost when the polynomial function to
minimize is obtained from a localization problem because of
the number n = 3 of variables and because of multi-degree
L = (
Classic results from the literature on interval arithmetic can
be used to compute lower and upper bounds for a given
polynomial function over a given box instead of using the bounds
provided by Bernstein coefficients. The bounds obtained from
the application of interval arithmetic are typically less strict
than the bounds obtained using Bernstein coefficients, but the
needed computation cost for n = 3 variables and multi-degree
L = (
Proposition 1: Given a polynomial function p : Rn 7→ R of
n ∈ N+ variables with multi-degree L ∈ Nn
(
In order to test the applicability of the POSTI algorithm for indoor localization, an experimental campaign was performed in an indoor environment, as discussed in this section. Results were obtained using a commercial Android smartphone equipped with the necessary hardware and software to communicate with UWB tags and to derive distance estimates from the time of flight of UWB signals. The smartphone used for experiments was a SpoonPhone, produced by BeSpoon (www.bespoon.com), which is, to the best of our knowledge, the only commercial smartphone equipped with a dedicated programming interface to easily estimate the distance between the smartphone and a paired UWB tag. In the considered experiments, four UWB tags were used as active ANs and distance acquisition was performed by the SpoonPhone, which was used as TN. The collected distance estimates were then processed according to the POSTI algorithm to obtain estimates of the position of the TN. In order to compare the performance of the POSTI algorithm with that of a known and appreciated algorithm, the distance estimates passed to the implementation of the POSTI algorithm were also passed to the implementation of the TSML algorithm that is readily available in the localization add-on module for JADE.
The indoor environment used to perform reported experiments is a 4 m wide, 10 m long, and 3 m tall corridor. All obstacles were removed from the corridor during experiments to guarantee that all ANs were in line of sight with the TN, and to reduce errors caused by multipath interference. Four different scenarios were considered, which correspond to different configurations of the ANs. For each scenario, twelve different positions of the TN were considered. Such positions are shown as red dots in Fig. 1, which also shows a schematization of the considered environment. Three different heights for the TN were considered, i.e., 3 m (near the ceiling), 1.5 m, and 0 m (near the floor). The four positions of the TN near the ceiling of the corridor are associated in Fig. 1 with 3 numbers from 1 to 4, and their coordinates are expressed in meters in the coordinate system shown in the figure as
The four positions of the TN whose heights are all equal to 1.5 m are associated with numbers from 5 to 8, and their coordinates are expressed in meters in the considered coordinate system shown in Fig. 1 as
The four positions of the TN near the floor are associated with numbers from 9 to 12, and their coordinates are expressed in meters in the coordinate system shown in the figure as where t is the true position of the TN and ˜t is the estimated position of the TN. Since four different scenarios corresponding to four different arrangements of the ANs were studied, and since experimental results were derived in correspondence of twelve positions of the TN for each scenario, a total of 48 experimental configurations were considered. For each considered experimental configuration, r = 100 estimates of the distance between the TN and each AN were acquired, and such estimates were used to derive r position estimates using the POSTI algorithm. Then, r position estimates were also derived by processing the same distance estimates with the TSML algorithm. Finally, the average and the standard deviation of the Euclidean norm of e over the r acquisitions obtained using the POSTI algorithm, denoted as eP and σP , were computed together with the corresponding values, denoted as eT and σT , obtained using the TSML algorithm.
In the first scenario, the four ANs are placed at the same
height near the ceiling of the considered environment. Using
the coordinate system shown in Fig. 1, the positions of the
ANs have the following coordinates expressed in meters
a1 = (
As discussed in Section I, the fact that all ANs share the same height is problematic for ordinary algorithms, and the TSML algorithm is actually inapplicable in this scenario. For this reason, only the accuracy of the POSTI algorithm can be evaluated. Table I shows the results related to the accuracy of the POSTI algorithm using the values eP and σP defined above for the r = 100 experiments and for each one of the twelve positions of the TN shown. Observe that values of eP vary from 0.249 m to 0.730 m. Therefore, it can be concluded that the accuracy of localization is compatible with the intended applications discussed in Section I. The values of standard deviations are also compatible with practical applications because they vary from 0.07 m to 0.411 m.
In the second scenario, the height of two of the four ANs is reduced with respect to the previous scenario. Using the coordinate system shown in Fig. 1, the positions of the ANs have the following coordinates expressed in meters a1 = (0, 0, 2.5) a3 = (0, 10, 2.5) Results show that the accuracy of the POSTI algorithm is similar to the accuracy measured in the first scenario. As a matter of fact, the values of eP vary between 0.246 m and 0.793 m, and the values of σP vary between 0.092 m and 0.580 m. The similarity between the results obtained in the two scenarios is not surprising because the position of the ANs did not change significantly.
Table II also shows the results related to the accuracy of the TSML algorithm, expressed in terms of eT and σT . Observe that such results are affected by significant errors in correspondence of some positions of the TN. In detail, the value of the average error eT is larger than 2 m when the TN was positioned in t3 and t9, and it is larger than 1 m when the TN was positioned in t5, t10, t11, and t12. Moreover, for 8 positions out of 12, the value of σT is larger than 1 m and it is often larger than 2 m, which emphasizes the inaccuracy of position estimates obtained with the TSML algorithm for the studied arrangement of ANs. From obtained results it can be concluded that the performance of the POSTI algorithm is good in this scenario, while the TSML algorithm leads to very inaccurate position estimates.
As observed in the previous scenario, the reduction of the height of two ANs by 0.5 m is not sufficient to obtain accurate position estimates with the TSML algorithm. For this reason, in this scenario the height of two ANs is further reduced with respect to the previous scenario and it equals 1.5 m. Hence, using the coordinate system shown in Fig. 1, the positions of the ANs have the following coordinates expressed in meters a1 = (0, 0, 1.5) a3 = (0, 10, 1.5)
Observe that the new height of the two relocated ANs may not be sufficient to guarantee visibility in practical applications because of the possible presence of obstacles. However, in the considered scenario, the corridor is empty and, therefore, visibility is guaranteed just like in previous scenarios.
Table III shows the accuracy of the algorithms in terms of eP and σP (evaluated using the POSTI algorithm), and of eT and σT (evaluated using the TSML algorithm). All values are computed using r = 100 repetitions of the experiments for each one of the twelve positions of the TN shown in Fig. 1. Results show that the accuracy of the POSTI algorithm is similar to the accuracy measured in the first and in the second scenarios. Actually, the values of eP vary between 0.287 m and 0.557 m, and the values of σP vary between 0.064 m and 0.474 m. The results obtained in the considered scenarios are not surprising because the accuracy of the POSTI algorithm is expected to be independent from the position of ANs.
Table III also shows the results related to the accuracy of the TSML algorithm, expressed in terms of eT and σT . In this scenario, results obtained with the TSML algorithm are sufficiently accurate for many applications. As a matter of fact, the values of the average error eT vary between 0.196 m and 0.896 m, and the values of the standard deviation σT vary between 0.098 m and 0.923 m. A comparison between the values of the average errors eP obtained with the POSTI algorithm and the values of the average errors eT obtained with the TSML algorithm shows that the characteristics of the two algorithms are comparable in this scenario. Analogous considerations can be derived from the values of the standard deviation σP obtained with the POSTI algorithm and the value of the standard deviation σT obtained with the TSML algorithm, even though the values of σP are actually lower than the corresponding values of σT for 9 out of the 12 positions of the TN.
In this scenario, the height of the two relocated ANs is
further reduced and they are placed near the floor of the
corridor while the other two ANs are still at their original
positions. Using the coordinate system shown in Fig. 1, the
positions of the ANs are expressed in meters as
a1 = (0, 0, 0)
a3 = (
As in the previous scenario, the new height of the two relocated ANs may not be sufficient to guarantee visibility in practical applications because of the presence of obstacles.
Table IV shows the accuracy of the algorithms in terms of eP and σP (evaluated using the POSTI algorithm), and of
Table IV
EXPERIMENTAL RESULTS IN SCENARIO 4 eT and σT (evaluated using the TSML algorithm). All values are computed using r = 100 repetitions of the experiments for each one of the twelve positions of the TN shown in Fig. 1. Results show that the accuracy of the POSTI algorithm is similar to the accuracy measured in the first, second, and third scenarios. As a matter of fact, the values of eP vary between 0.218 m and 0.483 m, and values of σP vary between 0.065 m and 0.420 m. Such results are in agreement with those obtained in previous scenarios, which is not surprising, since the accuracy of the POSTI algorithm is expected to be independent from the position of ANs.
Table IV also shows the accuracy of the TSML algorithm using the quantities defined previously for the r = 100 repetitions of experiments and for the twelve positions of the TN shown in Fig. 1. In this case, the accuracy obtained with the TSML algorithm is similar to the accuracy obtained in the third scenario. Actually, the values of the average error eT vary between 0.257 m and 0.878 m, and the values of the standard deviation σT vary between 0.103 m and 0.589 m, which ensures an accuracy of localization compatible with intended applications discussed in Section I. As for the previous scenarios, the results reported in Table IV show that the performance of the two algorithms are similar in this case.
The POSTI algorithm is discussed in this paper as a viable opportunity to support the localization as optimization approach (e.g., [5], [20]). The POSTI algorithm is based on consolidated results from the literature on nonlinear programming, and it relies on a subdivision method to search for the position of the TN in the considered indoor environment, which is assumed to be composed of possibly overlapping rectangular cuboids. According to the current implementation of the algorithm, the TN can actively obtain estimates of the distances from ANs using UWB. An alternative implementation of the algorithm that uses WiFi signaling to obtain distance estimates was experimented, but the accurate and robust distance estimates that UWB provides ensures far better localization performance and such an implementation is not discussed in this paper. One of the most relevant characteristics of the POSTI algorithm is that it provides a level of accuracy that is independent from the position of the ANs in the environment. This is not true for other localization algorithms, like the TSML algorithm, whose performance significantly degrades when problematic arrangements of ANs are used. Experimental results shown in the last part of this paper confirm that the POSTI algorithm leads to accurate position estimates in all considered scenarios, independently from the positions of ANs. Actually, the average localization errors and the corresponding standard deviations are independent from the considered position of the TN and from the adopted arrangement of ANs. At the opposite, significant localization errors are produced by the TSML algorithm when ANs are installed in critical arrangements. In detail, presented experimental results show that the POSTI algorithm outperforms the TSML algorithm in terms of average localization error and corresponding standard deviation when considering scenarios where all the ANs are almost coplanar. Such a result is particularly significant because the TSML algorithm is often used as a reference for the assessment of the performance of localization algorithms because it is well known [23] that it can attain the Crame´r-Rao lower bound [24] for the position estimator.
Finally, it is worth noting that the critical arrangements of the ANs that make the use of the TSML impractical are those in which all the ANs are located at (roughly) the same height. Unfortunately, this is one of the most common arrangements in indoor environments, where all the ANs are typically placed at the same height close to the ceilings of rooms to ensure a good line-of-sight coverage. According to such considerations, the use of the POSTI algorithm for robust and accurate localization seems a valid opportunity for envisaged applications of indoor localization, which demands that practical considerations regarding the line-of-sight coverage of environments are seriously taken into consideration.