A great variety of Indoor Positioning Systems (IPSs) have been developed with di erent technologies and algorithms. In the context of ngerprinting (FP) applications, the reduction of quantization levels in the Received Signal Strength Indicator (RSSI) till to its binary representation has been recently proposed for addressing one of the common drawbacks of FP, i.e. the large data size and consequently the large search space and computational load. In this paper, the binary ngerprinting technique is completed by the use of guard or uncertainty regions on the edges between the zones in which the area of interest is partitioned. This simple solution is shown to be e ective for recovering the performance gap between binary ngerprinting and ngerprinting with full complexity. In addition, we introduce also an alternative design of the cells in the area of interest in order to address better the errors due to uctuations of the RSSI measure in a real deployment.
In [
In the context of low complexity FP systems, this paper considers the design
presented in [
The remainder of this work is organized as follow: Sect. 2 describes the network scenario and, in Sect. 3, the binary version of FP is brie y revised. Then Sect. 4 introduces the ternary representation with the guard spaces and Sect. 5 the optimized cell design. Finally, Sect. 6 is dedicated to the numerical results and their analysis. 2
We consider an asynchronous sensor network containing a number of target devices over a limited rectangular area on a single oor, with two-dimensional coordinates (x; y).
In the area, there are NB xed nodes called beacons with known positions PiBS = fxi; yig; fi = 1; 2; :::; NBg. A uniform grid is de ned over the two-dimensional area and any estimate of a target location is limited to the points on this grid. The grid of points has resolution , over which the RSSI measures are stored for recovering the target locations.
Assuming that grid spacing results in Kx points along the x coordinate and Ky along the y coordinate, we have KT = Kx Ky positions in the area. Any position can be represented by a 2-tuple with label (x; y) where x and y represent the 2D coordinates on the oor plane. Therefore, the coordinates (x; y)i denote the i-th FP signature location.
The most common model adopted for the real RSSIs, recorded and stored during the o -line phase, responds to log-normal shadowing, i.e.
RSSI(d) = A L0 10 log10(d=d0) + LSH (1)
where A is a constant, given by the transmitted power and the antenna gains,
L0 is the average propagation loss at the reference distance d0 (usually 1 m),
is the Path Loss Exponent (PLE), d is the distance between transmitter and
receiver and LSH N (0; S2H ) is the log-normal uctuation mainly due to
obstacles in the environment. In this work, the values of the shadowing LSH
in a given area are assumed correlated according to the parameter dSH , which
separates independent shadowing samples in the space. Then, according to the
relative position between a grid point and a beacon, the values of L0 and
depend also on the Line of Sight (LoS) or Non LoS (NLoS) conditions. In fact,
each RSSI measured by the target during the online phase is a ected by an
additional variance measure, which depends on the environment changes, device
orientation and di erent device responses. The RSSI variance is probably the
most relevant issue in RSSI-based IPSs and some countermeasures are suggested
in [
RSSIMEAS(d) = RSSI(d) + W; (2) where W
N (0; W2 ).
The key point of BFP is the reduction of the quantization levels of the RSSI
up to the binary state. Considering beacons with low cost and small size, NB
can be large and W2 higher. As discussed in [
R = NB l ologg22(K(LT)) = logN2(BKT ) if L = 2: (3) Through the quantization of the RSSI with one bit, the RSSI will have 2 levels and the beacons will have a coverage obviously divided into two zones, according to a threshold RSSIREF , as in
ri = 01 iOf tRhSerSwIimseea:sured RSSIREF (4)
Therefore, the binary design of quantized ngerprinting can be driven by
concepts taken from error correcting codes theory an the optimal schemes for 2 2
and 4 4 cells have been presented in [
To deal with this weakness, in this paper, we propose an additional region
denominated uncertainty region around the boundaries separating the cells (as
shown in Fig. 1). In the proposed approach, whenever an on-line measurement
falls in the uncertainty region, the algorithm assigns a neutral value to di
erentiate from the other two cases. In the interpretation of BFP as an error correcting
code [
The novel ternary labeling is now de ned, for the measure coming from the i-th beacon, as 8> 1 < >: 0 ri =
Otherwise =2 =2 (5) where is the size of the uncertainty region, in dB, around the threshold RSSIREF;i and the neutral value is conventionally identi ed by the 0. In Fig. 1, the di erences between binary labeling and ternary labeling are shown.
The target position is estimated as follow { in presence of neutral values, the corresponding positions in the binary label would not be considered in the search of the candidates in the binary radio map. { When there are Nm multiple Hamming distances (this event clearly becomes more likely in presence of one or more neutral values), the position estimated is computed as Fig. 2: Binary labeling 2 1 2 for a typical, realistic RSSI scenario.
1 PT arget =
Nm i2Am
X Ci =
X (xi; yi) Nm i2Am (6) where Am is the set of FP signatures with minimum Hamming distance from the measured binary one and Ci = (xi; yi) are the coordinates of the corresponding cells centers. 5
Another weakness in the spatial labeling proposed and analyzed in [
If we apply the RSSIREF;i in the area, the actual partitioning of the space
according to (4) will be di erent from the ideal one, as in the example reported
in Fig. 2. Therefore, the nal performance incorporates the error induced by the
misalignment between the ideal and the real binary map of the area. In this
paper, we will call this design strategy, used also in [
In this section, numerical evaluation of the proposed technique are carried out
using MATLAB simulations. The performance results are compared between
Nearest-Neighbors (NN) based FP and BFP techniques with the use of the
uncertainty region and for the two design strategies, FCD or OCD. The system
parameters are summarized in Table 1, unless otherwise stated. The performance
is measured in a uniform grid of points with resolution 0:25 m. In the 2 2 cells
layout, Fig. 3a shows how the Root Mean Square Error (RMSE) changes as a
function of the uncertainty region size in the FCD and OCD cases; the best
value of becomes larger for high values of the measures error ( W 4 dB),
where aso OCD and FCD show the highest performance gap. For the sake of
completeness, we report also the spatial distribution of the error for the OCD
case, corresponding to Fig. 2: this picture clearly shows that the border regions
are the main sources of error. It is also necessary to notice that the error for
conventional FP with in nite number of bits in the measure is close to the
values of BFP with = 0 since with just 2 beacons the gain e ect guaranteed
by the Euclidean distance, instead of the Hamming one of the BFP, is negligible.
More interestingly, moving to the 4 4 cells layout as described in [
4 layout in the FCD (continuous lines) and OCD (dashed . 5a we can show the dependance of the performance also w.r.t. the measurement error parameter
W ; the ternary option with = 2 dB performs better than the original BFP and recovers most of the performance gap with FP at any value of W . The optimal size of the uncertainty region around 2
W increases as can be expected. Finally Fig. 5b shows how the RMSE varies with the side of the square area as a function of
In the last decade, the increase of demand of location based services has generated a strong interest in the
eld of positioning systems. Designing an IPS is a di cult task, which is generally faced by combining di erent technologies and methods; for techniques such as
ngerprinting, there are still some issues to be addressed from a theoretical and practical point of view. This paper enhances several aspects of the Binary FP algorithm, in particular including an uncertainty region to cope with the
uctuating RSSI values on the cell borders and the design of the cells in presence of realistic RSSI distributions. Simulation results show the bene t of the proposed modi cations compared to BFP without an increase of the computational or memory load.
As a future work, we aim at validating the proposed solutions with experimental data, and to prove the bene ts of the BFP technique with uncertainty regions in terms of computational e ciency against the state of the art.