-This paper presents a novel JADE add-on that enables the implementation of location-aware agents by interfacing an underlying ranging technology which provides accurate distance measures both indoor and outdoor. First, the paper motivates the work and it presents the features and the architecture of the add-on. Then, the paper provides a detailed description of the implemented localization algorithms and it validates them in an indoor scenario. The experimental results show that accurate indoor localization can be achieved and that the presented addon can be used to support location-aware agents with sufficient accuracy for targeted educational and ludic applications.
I. INTRODUCTION
The use of software agents on mobile devices dates back to first cellular telephone prototypes capable of running Java applications, and JADE was one of the first tools that enabled FIPA agents on devices that were then called Java-enabled phones [1]. We used to call them nomadic agents [2] at the time—to make a clear distinction with then popular mobile agents—and they were considered one of the most promising applications of agent technology. More recently, the porting of JADE to Android devices [3], and the widespread adoption of JADE and related technologies in crucial parts of largescale networks [4], revitalized the idea of having FIPA agents on mobile appliances to support large communities of users in their daily activities, which include both collaborative (see, e.g., [5], [6]) and competitive tasks (see, e.g., [7], [8]). Notably, the appliances of today offer much more resources than first Java-enabled phones, and the challenge of implementing agents for mobile devices is no longer about fitting complex software into constrained-resource devices; rather, it is about interfacing agents with the physical world they live in to ensure that user can be provided with contextualized services. This paper tackles the problem of interfacing agents with the physical world by presenting a novel software module which can be used to develop JADE agents that can sense the presence of nearby localization beacons or agents, both in outdoor and indoor scenarios. We prototyped such a module as a conventional JADE add-on which uses Ultra Wide Band (UWB) signals (see, e.g., [9]) to measure the distances between the appliance where the agent is running and target beacons or other appliances.
The acronym UWB was first used by the US Department
of Defense in late ’80s and it became popular after the
Federal Communications Commission allowed the unlicensed
use o
The use of UWB signals is particularly promising for high-precision localization because it ensures high ranging accuracy. As a matter of fact, due to their large bandwidth, UWB signals are characterized by very short duration pulses— usually in the order of one nanosecond—which guarantee accurate Time of Flight (ToF) estimation for signals traveling between nodes. This implies that the distance between a transmitter and a receiver can be accurately determined, yielding high ranging accuracy. At the opposite, pulses received via multiple paths using conventional narrow-band signals can easily overlap, causing wrong ToF estimates, hence wrong range estimates [11]. Besides their short pulses, UWB signals are also characterized by low duty cycle which leads to low energy consumption. Moreover, since UWB signals occupy a large portion of the spectrum, in order to avoid interference problems with other devices operating in the same frequency spectrum, UWB systems normally use lowpower transmissions. Finally, UWB signals are characterized by their capability of penetrating through obstacles thanks to the large frequency spectrum that characterizes them (which includes low-frequency components as well as high-frequency ones) [12]. Such a feature is particularly interesting in indoor environments where the presence of walls and objects can cause Non-Line-of-Sight (NLoS) effects between sensors.
Such unique aspects make UWB technology a good
candidate for accurate and low-power positioning systems. One
of the main drawbacks that caused the slow adoption of
UWB technology for accurate indoor localization was that
UWB transceivers were normally very expensive because of
the intrinsic challenges that their design and construction
involve, which also include high frequency logics for
measuring very short delay
This paper is organized as follows. Section II describes the architecture of the add-on and it details the implemented localization algorithms. Section III describes the experimental campaign that we performed to validate the usability of the proposed approach. Section IV concludes the paper. be found according to simple geometric considerations. As a matter of fact, the TN lies on each of the circumferences
M M M {Ci}i=1, centered in {si}i=1 with radii {ri}i=1 and, therefore, its coordinates satisfy the following system of equations (x − x1)2 + (y − y1)2 = r1
2 (x − xM )2 + (y − yM )2 = rM2 . (4)
DISTANCE- AND POSITION-AWARE JADE AGENTS The presented add-on for JADE uses the tools and techniques that JADE provides to integrate an underlying ranging technology, like UWB signaling, with the common agent loop. In details, it provides two customizable JADE behaviours that can be used to access the services of the add-on.
The first behaviour, called RangeChangeBehaviour, is in charge of connecting with the underlying ranging technology to measure the distances with targeted beacons or smart appliances. The behaviour can accommodate any ranging technology, provided that an implementation of a specific interface is available. In the presented prototype we opt for an implementation that we developed using BeSpoon APIs which acquires real-time information from the UWB transceiver installed in a spoonphone. The RangeChangeBehaviour is scheduled when an above-threshold change in the distances from selected beacons or smart appliances occurs, or when the agent decides to change the set of devices that it monitors. In details, the implemented prototype uses hardware-specific unique identifiers associated with transceivers that allow targeting beacons and smart appliances indifferently. This way the agent developer is free to track beacons and smart appliances with a single, generic mechanism.
The second behaviour that ships with the add-on is called LocationChangeBehaviour and it uses the first behaviour to acquire needed ranging information to inform an agent about its current location in a predefined reference frame. The behaviour can be configured to acquire needed information for performing localization from a set of beacons, commonly known as Anchor Nodes (ANs), and its main duty is to invoke a pluggable localization algorithm to estimate the location of the agent every time the distances from ANs change significantly. The developer is free to implement custom localization algorithms but the add-on contains two general-purpose algorithms that can be used if no additional information besides the distance from a fixed number of ANs is available. Such algorithms are discussed in details below.
For the sake of simplicity, the implemented localization algorithms currently consider only a bi-dimensional scenario, i.e., they assume that all the nodes lay on the same plane. The same algorithms can be extended to the case of a threedimensional scenario (e.g., see [13]). Both implemented localization algorithms are based on the ToF between some nodes with known positions, the ANs, and the Target Node (TN), whose position is to be estimated.
Denoting as M the number of ANs, we indicate the coordinates of the ANs as si = [xi, yi]T i ∈ {1, . . . , M }.
(1) The (unknown) TN position and its estimate are denoted as u = [x, y]T and uˆ = [xˆ, yˆ]T , respectively. Moreover, the true and the estimated distances between the i−th AN and the TN are denoted as ri , ||u − si|| = rˆi , ||uˆ − si|| = q q (u − si)T (u − si) (uˆ − si)T (uˆ − si) i ∈ {1, . . . , M } i ∈ {1, . . . , M }.
Observe that if the coordinates of the ANs and the true distances {ri}iM=1 are known, the true position of the TN can
Since the true distances are unknown, we can only rely on ˆ M their estimates {rˆi}iM=1. The circumferences {Ci}i=1 centered
M M in {si}i=1 with radii {rˆi}i=1 lead to the system of equations (x − x1)2 + (y − y1)2 = rˆ1
2 (x − xM )2 + (y − yM )2 = rˆM2 .
Obviously, due to the errors that affect the range estimates ˆ M {rˆi}iM=1, the circumferences {Ci}i=1 would hardly intersect in a unique point, hence proper localization algorithms need to be used. For such algorithms we assume that the errors M which affect the range measurements {rˆi}i=1 can be modeled as independent additive random variables {νi}iM=1, namely rˆi = ri + νi i ∈ {1, . . . , M }.
Let us define as ν the vector whose i−th element is νi and let us denote as Q its covariance matrix.
Many range-based localization algorithms have been proposed in the literature, and they can be broadly classified into passive and active [14]. Passive localization relies on the fact that wireless communications strongly depend on the environment and it is based on the analysis of the scattering caused by obstacles found along signal propagation and/or of the variance of a measured signal. Such analysis allows finding changes in the received signals that can be used to detect and locate targets [15].
In active techniques, instead, all nodes are equipped with sensors and with an electronic device which sends needed information to support a proper localization algorithm. Since all implemented algorithms follow in this category, we focus on range-based localization with active tags, which can be based on the ToF, the Angle of Arrival (AoA), or the Received Signal Strength (RSS) of the signals [10]. As explained in the introduction, we are mostly interested in ToF-based localization algorithms because are particularly well suited when dealing with UWB signaling. In details, if two synchronized nodes communicate, the node receiving the signal can determine the Time of Arrival (ToA) of the incoming signal from the timestamp of the sending node. If the nodes are not synchronized, Time Difference of Arrival (TDoA) techniques can be employed, which are based on the estimation of the difference between the arrival times of UWB signals traveling between the TN and ANs. A large number of ToF-based localization techniques have been proposed in the literature. Among them, it is worth mentioning iterative methods [16], graph-based methods [17], closed-form algorithms [18] and optimization methods [19]. Observe that the accuracy of some of such algorithms may strongly depend on the number of ANs [20] and on their topology [21].
In the following subsections, the two implemented localization algorithms are described in details, namely: the Circumference Intersection (CI) algorithm and the Two-Stage Maximum-Likelihood (TSML) algorithm. From now on, we assume that M = 3 ANs are used to locate the TN. A. Circumference Intersection (CI) algorithm
This subsection describes the CI localization algorithm, which is a very intuitive algorithm that can be considered as the basis of other more elaborate algorithms (see, e.g. [22]).
In order to better explain the CI algorithm, let us make a few geometric considerations on the considered problem. As already observed, the position of the TN coincides with the (unique) intersection of the three circumferences in (2). Since such circumferences are unknown, in order to find the TN position estimate uˆ = [xˆ, yˆ] it is necessary to consider proper localization approaches based on the set of equations (3). According to the CI algorithm, since the circumferences do not intersect in a single point, we intersect pairs of them.
More precisely, we define the following three sets—each of which contains two points—obtained by intersecting the three different pairs of circumferences
I1 = {p12, q12} I2 = {p13, q13} I3 = {p23, q23} , , ,
C1 ∩ Cˆ2 ˆ C1 ∩ Cˆ3 ˆ C2 ∩ Cˆ3. ˆ
We then choose a point from each of the three sets, namely p1 ∈ I1, p2 ∈ I2, and p3 ∈ I3, so that the three selected points are the nearest ones to each other. More precisely, since such points belong to circumference intersections, it can be shown that they can be chosen as ||p1 − p2|| ||p1 − p3|| = = minp∈I1,q∈I2 ||p − q|| minq∈I3 ||p1 − q||.
Given these three points, the TN position estimate is chosen as their baricenter.
We remark that the intersection between two circumferences can be empty. Assume, for instance, that in (5) the set I1 is empty, namely the circumferences Cˆ1 and Cˆ2 do not intersect. In this case, the two nearest points of Cˆ1 and Cˆ2 are found, and if their distance is below a given threshold, they are considered the two intersection points and the set I1 is redefined as the set containing such two points. Otherwise, the TN position estimate is found based on the remaining intersections, whenever possible.
B. Two-Stage Maximum-Likelihood (TSML) algorithm
This subsection describes a TSML method that uses ToA information, hence known as TSLM-ToA method [23]. Such method is a well-known localization algorithm, and it is particularly interesting because it was shown that it can attain the Cramer-Rao Lower Bound, which is a lower bound for the variance of an estimator [24]. A detailed derivation of this method can be found in [25].
The starting point of the TSML algorithm is once again the quadratic system (3), where we set M = 3 as in the case of the (10) (11) (12) (13) (14) (15) (16) (17) (18) Let us also introduce ω1 and h1 the vectors analogous to ωˆ1 and to hˆ1, respectively, where estimated quantities are substituted by true ones, namely
1 where Q is the covariance matrix of the ToA range measurements {ri}iM=1, B is a diagonal matrix whose elements are
M {ri}i=1, and the last equality follows from the fact that, from (4) and (13), ψ can be written as ψ1 = hˆ1 − h1 = 2B ν + ν ν ' 2B ν where denotes the entrywise product and the last approximation is obtained neglecting second order perturbations. With this choice of the weighting matrix one obtains that Cov[ωˆ1] = (G1T W 1 G1)−1.
CI algorithm. In order to solve it, a two-step approach based on Maximum-Likelihood (ML) technique can be considered. First, let us define as ai the Euclidean norm of the coordinate vector of the i−th AN, namely ai , ||si|| = q xi2 + yi2 i ∈ {1, . . . , 3}.
Moreover, let us introduce the new variable so that system (3) can be rewritten, in matrix notation, as where nˆ , ||uˆ||2 = xˆ2 + yˆ2
G1 ωˆ1 = hˆ1 x1 G1 = −2 ...
xˆ ωˆ1 = yˆ nˆ
x3 x ω1 = y n
While (12) might look like a linear system, it is not, since the third element of the solution vector ωˆ1 depends on the first two according to (11). The solution ωˆ1 of the system (12) can be determined through an ML approach. In particular, as suggested in [18], let us define the error vector Given a positive definite matrix W 1, the weighted Least Square (LS) solution of (12) that minimizes ψ1T W 1ψ1 is
ωˆ1 = (G1T W 1 G1)−1G1T W 1 hˆ1.
The simplest choice of the weighting matrix W 1 is the identity matrix. In [25] it is shown that the choice of W 1 which minimizes the variance of ωˆ1 is
W 1 , Cov[ψ1]−1 = (4B Q B)−1 (5) (6) (7) (8) (9) 1.2 1.1 7 6 5 4 2 1 0
The second stage of the algorithm is meant to take into account the dependence of nˆ on the other elements of the unknown vector in the system of equations (12) and it involves the solution of the system with [ωˆ1]j denoting the j−th component of ωˆ1. The linear system (19) can be solved, once again, through the ML technique. Defining the error vector ψ2 , hˆ2 − G ω 2 2 the weighted LS solution of (19) that minimizes the weighted norm of ψ2 with a positive definite matrix W 2 is ωˆ2 = (G2T W 2 G2)−1G2T W 2 hˆ2.
As considered to solve (12), the simplest choice of the weighting matrix W 2 is the identity matrix. In [25], it is shown that the choice of W 2 which minimizes the variance of ωˆ2 is
W 2 , Cov[ψ2]−1 = (4B2 Cov[ωˆ1] B2)−1 where B2 = diag(x, y, 0.5). Finally, the position estimate can be expressed as uˆ = U hp[ωˆ2]1, p[ωˆ2]2 iT where U = diag(sign(ωˆ1)).
III. EXPERIMENTAL SETUP AND RESULTS
This section shows localization results obtained with the two implemented algorithms, as described in the previous section, using a JADE agent running on a spoonphone used as TN. We use three localization beacons as ANs and we put them at three corners of a rectangular room whose sides measures (19) (20) (21) (22) (23) (24) 0.9 1 1.1 1.2 0.9 1 1.1 1.2 x [m] x [m] (a) (b) Fig. 2. The 1000 position estimates of TN1 obtained using: (a) the CI algorithm; and (b) the TSML algorithm. 3 m and 6 m. Using the same notation introduced in Section II, the ANs position in the experimental setup are denoted as s1 = [0, 0]T s2 = [3, 0]T s3 = [0, 6]T (25) where the coordinates are expressed in meters. In Fig. 1 the ANs positions are shown (blue stars) in the considered room.
Inside the same room, we consider three different TN positions, denoted as red stars in Fig. 1. First, we put the TN in the points whose coordinates, expressed in meters, are Observe that this point, denoted as TN1 in Fig. 1, is close to one of the corners of the room and close to AN1. The second TN position we consider is which corresponds to the point in the middle of the room, denoted as TN2 in Fig. 1. Finally, the coordinates of the last TN position, expressed in meters, are u1 = [1, 1]T . u2 = [1.5, 3]T u3 = [2, 5]T .
Observe that this point is symmetric of u1 with respect to the center of the room.
For each TN position {TNi}i3=1, we first acquire the three distance estimates between the TN and the three ANs and we use such distances to feed the two localization algorithms described in Section II. This process is iterated NI = 1000 times, thus obtaining 1000 position estimates for each of the two localization algorithms and for each TN position. For each iteration j ∈ {1, . . . , NI } we define the distance between the true TN position and its estimate in the j-th iteration as dj = ||uˆj − u|| where uˆj is the TN position estimate in the j-th iteration. (26) (27) (28) (29)
We can define the minimum, the maximum, and the average distance between the true TN position and its estimates as dmin = dmax = davg =
min j∈{1,...,NI }
max j∈{1,...,NI } 1 XNI dj .
NI j=1 dj dj (30) The performance of the localization algorithms is evaluated in terms of the values in (30).
Fig. 2 is relative to the position estimates of the target TN1 of Fig. 1. More precisely, Fig. 2 (a) shows the 1000 position estimates obtained using the CI algorithm and Fig. 2 (b) shows the 1000 position estimates obtained according to the TSML algorithm. A comparison between Fig. 2 (a) and Fig. 2 (b) shows that the CI algorithm performs slightly better that the TSML algorithm in terms of the distance between the true position and the estimated ones. As a matter of fact, from Table I it can be observed that while the average distance davg when using the CI algorithm is 5.7 cm, the value of davg obtained with the TSML algorithm is 7.2 cm. Analogous considerations hold when considering dmin and dmax. More precisely, the value of dmin relative to the CI algorithm is only 0.03 cm and it becomes 1.4 cm when using the TSML algorithm, while the values of dmax correspond to 12.2 cm and 13.8 cm, respectively.
Fig. 3 refers to the position estimates of the target TN2 of Fig. 1, corresponding to the case where the TN is in the middle of the room. The 1000 position estimates obtained using the CI algorithm are shown in Fig. 3 (a) while Fig. 2 (b) shows the 1000 position estimates obtained with the TSML algorithm. In this case, the performance of the two algorithms are similar, as also shown in Table I, which shows that the values of davg obtained with the CI and the TSML algorithms differ by only 2 mm. Observe that in this case the values of davg are greater than those obtained when considering TN1, meaning that the localization in the center of the room is less accurate. In particular, Table I shows that the distances between
Finally, Fig. 4 is relative to the position estimates of the target TN3 of Fig. 1 obtained: (a) using the CI algorithm; and (b) using the TSML algorithm. In this case, the average distance davg between the true TN position and its estimates is 11.5 cm when using the CI algorithm and 12.2 cm with the TSML algorithm, as shown in Table I. The performance of the two algorithms are similar also in terms of dmin and dmax. Observe that the values of dmax are greater than those obtained in the previous two TN positions. The values of dmin, instead, are greater than those relative to TN1 but they are smaller than those relative to TN2.
This paper presents a novel JADE add-on that enables the implementation of distance- and location-aware agents. Using this add-on an agent can measure the distance that separates the smart appliance that hosts it from target beacons and other smart appliances. Experimental results summarized in Table I show that the average error in locating the smart appliance in an empty room is less than 15 cm, which ensures sufficient accuracy for considered education and ludic applications.