PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Indoor Localization and Radio Map Construction with Limited Deployment Load

Sameh Sorour, Yves Lostanlen, Shahrokh Valaee

arXiv:1310.3407v1cs.NIcs.LG

TL;DR

Fingerprinting makes RSS-based indoor localization costly to deploy because it requires extensive radio-map construction. The paper transfers spatial-correlation knowledge from source datasets to limited calibration fingerprints and unknown-location observations for direct localization and joint map construction. Tests in two indoor environments favor plan coordinates over simulated radio maps.

  • Problem

    Constructing a fingerprinted radio map is an exhaustive, expensive, and time-consuming bottleneck for RSS-based indoor localization, particularly in large environments.

    Source: §1 · p. 1

  • Method

    The scheme uses manifold alignment to transfer spatial-correlation knowledge from a source dataset to limited calibration fingerprints and unknown-location RSS observations for direct localization and map construction.

    Source: §1 · p. 2, §8 · pp. 11–12

  • Results

    Online tests in two indoor environments favor plan coordinates over simulated radio maps for localization results.

    Source: §8 · p. 12

  • Takeaways & Limitations

    Accumulating localized readings can jointly construct the radio map with limited calibration.

    Source: §8 · p. 12

    Manifold alignment requires stronger correlation among neighboring points in each dataset and a common lower-dimensional correlation between datasets.

    Source: §3 · p. 3

Abstract

from arXiv · show

One major bottleneck in the practical implementation of received signal strength (RSS) based indoor localization systems is the extensive deployment efforts required to construct the radio maps through fingerprinting. In this paper, we aim to design an indoor localization scheme that can be directly employed without building a full fingerprinted radio map of the indoor environment. By accumulating the information of localized RSSs, this scheme can also simultaneously construct the radio map with limited calibration. To design this scheme, we employ a source data set that possesses the same spatial correlation of the RSSs in the indoor environment under study. The knowledge of this data set is then transferred to a limited number of calibration fingerprints and one or several RSS observations with unknown locations, in order to perform direct localization of these observations using manifold alignment. We test two different source data sets, namely a simulated radio propagation map and the environments plan coordinates. For moving users, we exploit the correlation of their observations to improve the localization accuracy. The online testing in two indoor environments shows that the plan coordinates achieve better results than the simulated radio maps, and a negligible degradation with 70-85% reduction in calibration load.

1 INTRODUCTION

Fingerprinting makes RSS-based indoor localization costly to deploy, while prior approaches still rely on full radio maps or extensive calibration. This section proposes direct localization from limited fingerprints by transferring spatial correlation from a source dataset, with localized readings also contributing to radio-map construction.

1 INTRODUCTION

  • Full fingerprinting is an expensive, time-consuming deployment bottleneck, especially in large indoor environments.The paper also notes that radio maps can support wireless coverage, capacity, and radio-dimensioning work.Source: §1 · p. 1
  • Prior propagation-model approaches either performed unsatisfactorily or needed extensive calibration and post-processing to address model inaccuracies.Related approaches for temporal or device variation still required a complete deployment map, and some also needed dense calibration or extensive processing.Source: §1 · pp. 1–2
  • The proposed scheme directly localizes users from limited calibration without first building a full radio map, and accumulates localized readings to construct the map.It transfers spatial-correlation knowledge from a source dataset to calibration fingerprints and unknown-location RSS observations using manifold alignment.Source: §1 · p. 2
  • Simulated radio maps capture propagation effects but can have non-neighboring correlation outliers, while plan coordinates preserve physical neighborhoods but omit propagation effects.The paper tests both source datasets to examine which property matters more for accuracy.Source: §1 · p. 2
  • For walking users, jointly localizing successive RSS observations exploits their correlation, enforces neighborhood structure, and rejects localization outliers.This is intended to improve localization accuracy.Source: §1 · p. 2
  • The approach requires fewer fingerprints than full fingerprinting and can adapt to time, device, or floor-plan changes with limited recalibration or spatial-correlation updates.For time or device changes, the paper describes using a few new calibrations; after drastic floor-plan changes, it says the correlation function can be adapted and the system can re-operate in minutes.Source: §1 · p. 2

2 RELATED WORK

The discussed adaptation methods address changes in radio maps but retain requirements or limitations that distinguish them from direct localization. The paper contrasts its approach with methods that update maps for later use rather than localizing targets directly.

2 RELATED WORK

  • LANDMARK and LEASE adapt RSS offsets using reference sniffers but need an initial map and dense sniffers; LEMT uses fewer sniffers but requires extensive tree-building after sniffing periods.LEMT learns a relationship between the initial map and real-time readings, then uses nearest-neighbor localization.Source: §2 · p. 2
  • LeManCoR and LuMA transfer knowledge across times or devices but require a complete, accurate deployment map and produce maps for future localization rather than directly localizing targets.The paper also reports possible accuracy loss after large floor-plan changes or repeated updates.Source: §2 · p. 2

3 MANIFOLD ALIGNMENT

Manifold alignment transfers knowledge between source and destination data sets by mapping their shared structure into a lower-dimensional space. It preserves neighborhood relations while aligning paired points, with LLE supplying neighborhood weights.

3 MANIFOLD ALIGNMENT

  • Manifold alignment maps source and destination data sets with a common underlying manifold into a low-dimensional space to transfer knowledge.It requires stronger correlation among neighboring points in each data set and a common lower-dimensional correlation between them.Source: §3 · p. 3

3.1 Neighborhood Weights

  • LLE assigns weights to nearest neighbors so that the low-dimensional embedding preserves local structure and neighborhood correlation.Closer neighbors receive higher weights; non-neighbors receive zero weight.Source: §3.1 · p. 3

3.2 Manifold Alignment Formulation

  • The alignment objective preserves neighborhood relations in both data sets and penalizes discrepancies between paired points.Under a hard constraint that paired points share an embedding, the problem becomes an eigenvalue problem; the embedding uses eigenvectors for the smallest nonzero eigenvalues.Source: §3.2 · pp. 3–4

4 PROPOSED SOLUTION USING SIMULATED RADIO MAP

The simulated-radio-map approach transfers spatial correlations to limited calibration fingerprints and unknown-location RSS observations through manifold alignment. It supports direct localization, walking-user smoothing, device-side operation, and radio-map construction from accumulated observations.

4 PROPOSED SOLUTION USING SIMULATED RADIO MAP

  • The method aligns simulated radio-map correlations with limited calibration fingerprints and unknown-location RSS observations to localize users directly.Although simulated maps capture propagation effects, model inaccuracies can create similar RSS values at non-neighboring positions.Source: §4 · p. 4

4.1 Offline Deployment Phase

  • Deployment uses environment and access-point details to simulate RSS at grid points, then collects fingerprints at a limited number of calibration locations.The simulated map supplies source-set neighborhood weights; calibration locations are paired with their simulated positions.Source: §4.1 · p. 4

4.2 Server-based Online Localization Phase

  • For each online observation, the server finds its nearest calibration or simulated-position embedding and returns that position.The aligned embedding separates paired calibration rows, unpaired simulated positions, and user observations.Source: §4.2 · p. 5

4.3 Algorithm Modifications for Walking Users

  • Walking-user observations are linked as neighbors, and estimated outlier positions are replaced by the centroid of their immediate predecessor and successor positions.The method uses groups of subsequent RSS observations to smooth estimated positions.Source: §4.3 · p. 5

4.4 Device-based Online Localization Phase

  • Device-side localization requires a one-time download of Lx and calibration fingerprints, then runs with one RSS observation at a time.Its stated complexity is O(S^3 + C^3); device sensors can track movement between RSS localization runs and correct drift at interval beginnings.Source: §4.4 · pp. 5–6

4.5 Radio Map Construction

  • The server averages N accumulated readings at each position to estimate that position’s radio-map RSS.Observations are collected during casual walks after a few precise calibration measurements; construction ends when all positions have estimates.Source: §4.5 · p. 6

5 PROPOSED SOLUTION USING PLAN COOR-

The plan-coordinate variant transfers physical-neighborhood structure from floor-plan coordinates to calibration and online RSS measurements. It avoids simulated-radio-map inputs and requires fewer environment details.

DINATES

  • Plan coordinates encode physical neighborhood relations and require less environment detail than simulated maps, particularly access-point locations and heights.The approach transfers these coordinate relations to calibration and online observations for direct localization.Source: DINATES · p. 6

5.1 Offline Deployment Phase

  • Offline deployment derives a grid of plan coordinates from building CAD information and separates neighbors across very thick or metallic walls.This avoids access-point position data and radio-propagation simulations required by the simulated-map approach.Source: §5.1 · p. 6

5.2 Online Localization Phase

  • Online localization repeats x and y coordinate values into extended vectors to match calibration-fingerprint dimensions without changing distances.The remaining algorithm is unchanged, and device-based localization and walking-user modifications also apply.Source: §5.2 · p. 6

6 PERFORMANCE TESTING OF LOCALIZATION SOLUTIONS

Across both test environments, plan coordinates achieved lower localization error than the simulated radio maps. In Bahen Center, they kept degradation below 20% with 70% less calibration, while Siradel results also favored plan coordinates at 15–30% calibration effort.

6.1.2 Data Collection and Testing Setup

  • At Bahen Center, researchers deployed five Linksys APs and measured and simulated RSS at 219 grid points spaced 1 m apart; full measurements enabled tests across calibration subsets and observation counts.Mean localization errors were averaged over a large number of localization tests for each setup; calibration-fingerprint percentages were normalized against 219 grid points.Source: §6.1 · p. 7, Figure 4 · p. 7, §6.1.2 · p. 8

6.1.1 Generation of Simulated using Volcano Lab

  • The simulated-map tests used direct-path, one-reflection, two-reflection, and ray-tracing models; higher-fidelity estimates increased simulation complexity.The ray-tracing setup included four reflections and one diffraction.Source: §6.1.1 · p. 7

6.1.3 Effect of Neighborhood Size

  • With 25% calibration and 5% localization observations, 20–25 neighbors performed better than 10–15, while 35–50 neighbors degraded performance as neighborhoods became too loose.Small neighborhoods are more affected by outliers in weight computation; excessively large neighborhoods include points outside a point’s vicinity.Source: §6.1.3 · p. 8, Figure 5 · p. 8

6.1.4 Effect of Calibration Fingerprinting Load

  • In Bahen Center, plan coordinates kept degradation below 20% (0.4 m) with 70% less calibration and below 40% (0.8 m) with 80% less calibration, versus the full-calibration reference localizer.The reference localizer is identified as.Source: Figure 7 · p. 9, §6.1.4 · p. 9

6.1.5 Effect of Localization Observations

  • Increasing localization observations from 1 to 50 reduced error by less than 35 cm; walking users could be localized after 2–5 observations without waiting for a longer sequence.The authors report the change as insignificant for most indoor localization applications.Source: Figure 9 · p. 9, §6.1.5 · p. 10

6.1.4 Effect of Calibration Fingerprinting Load

  • At 15–30% calibration, walking-user mean error fell to 2.3–1.8 m in Bahen Center, and plan coordinates remained more accurate than the simulated maps.These results used 25 neighbors and 11 observations.Source: §6.1.4 · p. 9, Figure 8 · p. 9

6.2 Siradel Building

  • In Siradel, plan coordinates outperformed all simulated radio maps, with mean errors of 2.7–2.4 m for stationary users and 2.2–1.9 m for walking users at 15–30% calibration effort.The Siradel environment covered 40 m × 20 m, with four APs and 302 grid points.Source: §6.2 · p. 10

7 PERFORMANCE TESTING OF RADIO MAP CONSTRUCTION

The proposed algorithm estimates uncalibrated radio-map points from localized readings, with RMS error evaluated against a fully measured map. Plan coordinates outperform the simulated map, and fewer accumulated observations produce only small reported degradations.

7 PERFORMANCE TESTING OF RADIO MAP CONSTRUCTION

  • The algorithm stores localized readings at estimated positions and averages N readings per location to estimate RSS.RMS error is measured against the actual radio map from the full measurement collection.Source: §7 · p. 10
  • Plan coordinates had lower RMS error than the simulated map, while increasing calibration load from 10% to 50% reduced their RMS error by only about 1 dBm.The comparison used 20 accumulated observations per point.Source: §7 · pp. 10–11, Figure 13 · p. 11
  • 70% improvement over the simulated map was achieved with plan coordinates at 16% of the full calibration load.The comparison concerns the overall map, including calibrated and estimated points.Source: Figure 14 · p. 11, §7 · p. 11
  • Reducing observations per map point from 25 to 5 increased RMS error by only 0.5 dBm and reduced improvement over the simulated map by less than 2%.The reported effect was especially minor with plan coordinates; collecting fewer observations can reduce map-building time.Source: Figure 15 · p. 11, §7 · p. 11

8 CONCLUSION

The proposed scheme jointly performs indoor localization and radio-map construction with limited calibration, using source data that preserves spatial correlation. Online tests favor plan coordinates over simulated radio maps and report limited localization degradation with substantially reduced calibration.

8 CONCLUSION

  • With 70–80% less than full fingerprinting, localization error increased by only 0.4–0.8 m; plan coordinates performed better than simulated radio maps in two indoor environments.The scheme transfers source-data knowledge to limited calibration fingerprints and localization observations using manifold alignment.Source: §8 · p. 12
  • Accumulating localized readings also constructs a radio map: the scheme achieved 70% improvement over the simulated map with 16% of full calibration load.The tested correlation-preserving source data sets were plan coordinates and a simulated radio map.Source: §8 · pp. 11–12
  • For moving users, the scheme exploits correlation among reported observations to improve localization accuracy.Source: §8 · p. 12
  • Future work will explore unsupervised manifold alignment and combining plan coordinates with simulated maps, weighing possible gains against added complexity.Source: §8 · p. 12
Loading 1310.3407v1…