PaperlayerView exact revision on arXiv

Source-linked AI summary

MetaLocalization: Reconfigurable Intelligent Surface Aided Multi-user Wireless Indoor Localization

Haobo Zhang, Hongliang Zhang, Boya Di, Kaigui Bian, Zhu Han, Lingyang Song

arXiv:2011.09323v3eess.SP

TL;DR

Indoor RSS localization is limited when neighboring locations have similar signal strengths, motivating RIS-aided multi-user localization. The paper formulates the coupled phase-shift and decision-function problem, derives the optimal decision function, and designs a PSO algorithm; simulations show substantially improved localization accuracy.

  • Problem

    Similar RSS values at neighboring indoor locations limit the localization accuracy of RSS-based techniques.

  • Method

    The paper coordinates an RIS-aided multi-user localization protocol, formulates joint optimization of the decision function and RIS phase shifts, derives the optimal decision function, and designs a PSO algorithm.

  • Results

    The proposed scheme can reduce localization error by at least 3 times compared with traditional RSS-based schemes.

  • Takeaways & Limitations

    RIS phase shifts can be optimized for RSS-based indoor localization, producing lower localization errors than traditional, random, and SOA schemes under the reported evaluations.

Abstract

from arXiv · show

The received signal strength (RSS) based technique is extensively utilized for localization in the indoor environments. Since the RSS values of neighboring locations may be similar, the localization accuracy of the RSS based technique is limited. To tackle this problem, in this paper, we propose to utilize reconfigurable intelligent surface (RIS) for the RSS based multi-user localization. As the RIS is able to customize the radio channels by adjusting the phase shifts of the signals reflected at the surface, the localization accuracy in the RIS aided scheme can be improved by choosing the proper phase shifts with significant differences of RSS values among adjacent locations. However, it is challenging to select the optimal phase shifts because the decision function for location estimation and the phase shifts are coupled. To tackle this challenge, we formulate the optimization problem for the RIS-aided localization, derive the optimal decision function, and design the phase shift optimization (PSO) algorithm to solve the formulated problem efficiently. Analysis of the proposed RIS aided technique is provided, and the effectiveness is validated through simulation.

I. INTRODUCTION

The paper addresses limited RSS-based indoor localization accuracy by using RIS-controlled reflections to create more distinguishable RSS distributions. It formulates the coupled localization design problem and proposes a protocol and PSO-based solution for multi-user localization.

  • RSS-based localization is widely used because RSS information can be extracted from widespread Wi-Fi-compatible devices without additional hardware requirements.
  • RIS elements electrically tune reflection phases, allowing the surrounding RSS distribution to be customized.
  • The proposed scheme uses RIS reflections to create larger RSS differences among locations, improving distinguishability compared with traditional RSS techniques.
  • The joint phase-shift problem is difficult because the decision function and RSS distribution are coupled, while discrete RIS states make the resulting integer program NP-hard.
  • The RIS-aided system coordinates an access point, RIS, and multiple users during the localization process.
  • The optimization minimizes weighted false-localization probabilities by jointly optimizing the decision function and RIS phase shifts.
  • The optimal decision function is derived, and a phase shift optimization algorithm selects RIS phase shifts for the localization-loss problem.
  • The proposed scheme is analyzed theoretically and its effectiveness is verified through simulations.

C. RSS Model

The RSS model represents received power as a direct line-of-sight component combined with RIS-reflected components and log-normal shadowing. RIS phase shifts therefore affect the modeled RSS distribution at each location.

  • Each user’s received signal contains one direct line-of-sight component and M RIS reflection components.
  • The m-th reflection component is the transmitted signal reflected from the m-th RIS element to the user.
  • The mean RSS depends on transmitted signal power, the direct LOS gain, RIS reflection-channel gains, and log-normal shadowing.
  • The shadowing term ξ represents multipath effects in non-line-of-sight paths and follows a Gaussian distribution N(0, σ^2).
  • The direct LOS gain incorporates antenna power gains and the AP-to-user distance for each block.
  • The reflection-channel gain depends on antenna gains, AP-to-RIS and RIS-to-user distances, and the reflection coefficient of each RIS element.
  • The model defines RSS at each block under a phase-shift vector c, with its probability distribution characterized by the RSS standard deviation σ.

III. RIS-AIDED MULTI-USER LOCALIZATION PROTOCOL

The localization protocol has coarse- and fine-grained phases. Users measure RSS and self-localize initially, while higher-precision requests trigger iterative AP-RIS-user cooperation with cycle-specific phase-shift optimization.

  • The protocol consists of coarse-grained and fine-grained localization phases.
  • Coarse-grained localization phase: Users requesting higher precision send localization information to the AP, and TDM assigns non-overlapping response slots for multiple users.
  • Coarse-grained localization phase: In the coarse-grained phase, users self-localize from measured RSS using a fixed phase-shift vector and its corresponding radio map.
  • Coarse-grained localization phase: Each coarse-grained cycle sequentially performs broadcast, RSS measurement, and response steps.
  • Fine-grained localization phase: The fine-grained phase runs for K cycles and terminates after sending the fine-grained localization results to users.
  • Fine-grained localization phase: At the beginning of each fine-grained cycle, the AP selects a phase-shift vector using RSS information collected in previous cycles.
  • Fine-grained localization phase: Fine-grained cycles broadcast the selected vector, measure average RSS, and return those averages to the AP for the next optimization.
  • Problem formulation: The optimization problems for both phases optimize the decision function and RIS phase-shift vector to improve localization accuracy.

B. Problem Formulation for the Fine-grained Localization Phase

The paper formulates fine-grained localization as an expected-loss minimization problem using cycle-dependent priors and decision functions. It then derives the optimal decision rule and replaces difficult loss integration with an approximation for algorithm design.

  • B. Problem Formulation for the Fine-grained Localization Phase: The fine-grained optimization problem is formulated separately for each cycle using the phase shifts, RSS observations, and cycle-dependent prior probabilities.
  • B. Problem Formulation for the Fine-grained Localization Phase: The decision function estimates whether user i is located in block n′ during cycle k, and final localization uses the decision function from cycle K.
  • B. Problem Formulation for the Fine-grained Localization Phase: The fine-grained constraints are analogous to the coarse-grained formulation.
  • B. Problem Formulation for the Fine-grained Localization Phase: Cycle-k prior probabilities represent beliefs about user locations based on radio maps and RSS values from previous cycles.
  • V. ALGORITHM DESIGN: The algorithm design treats the coarse-grained problem as a special case of the fine-grained problem and omits the cycle superscript for simplicity.
  • A. Decision Function: Given phase shifts, RSS, and prior probabilities, Proposition 1 derives the optimal decision function through decision regions R_i,n′.
  • A. Decision Function: The localization loss is expressed using the decision regions and RSS distribution, but irregular regions make the required integration difficult.
  • A. Decision Function: An approximated localization loss using the Gaussian Q function is introduced to enable more efficient solution of the original optimization problem.

B. Phase Shift Optimization Algorithm

The PSO method optimizes discrete RIS phase shifts by approximating localization loss and combining local-minimum search with global descent. Its formulation addresses the non-convex, integer nature of the phase-shift problem.

  • The phase-shift optimization problem minimizes the approximated localization loss under discrete phase-shift constraints.The unit-neighborhood formulation uses modulo operations and unit vectors to define nearby discrete phase-shift vectors.
  • The phase-shift problem is NP-hard because its objective is non-convex and it is formulated as an integer optimization problem.These properties make the problem more difficult than continuous optimization.
  • The PSO algorithm has initialization and global-search phases for finding effective RIS phase-shift vectors.Initialization generates local minima, while global search uses them to approach the global minimum of localization loss.
  • The LMVS procedure defines local minima through a unit neighborhood and iteratively selects the neighboring vector with minimum loss.The neighborhood is formed by changing one phase-shift component by one discrete step in either direction.
  • Global search sorts local minima by localization loss and uses them to approach the global minimum.The set of generated local minimum vectors is ordered by increasing localization loss before global search proceeds.

1) Initialization Phase:

The initialization phase uses LMVS to generate distinct local minima, then expands the candidate set through steepest-descent directions and repeated local search until the target size is reached.

  • Initialization Phase: LMVS obtains a local minimum phase-shift vector from an initial input using alternating optimization.It terminates when the current vector is a local minimum; otherwise, it moves to the neighboring vector with minimum positioning loss.
  • Initialization Phase: The PSO algorithm initializes a set C of Z_l distinct local minimum phase-shift vectors using LMVS and random inputs.The vectors are sorted in increasing order of localization loss.
  • Global Search Phase: Each global-search iteration computes descent ratios from the best vector, selects the maximum-ratio direction, and enumerates step sizes for a lower-loss candidate.The candidate is refined with LMVS before being considered for insertion into C.
  • Global Search Phase: New local minima are inserted into C when distinct; otherwise, LMVS is rerun with random input to generate an unseen vector.The set remains sorted according to approximated localization loss.
  • Global Search Phase: The iteration terminates when C contains more than Z_u phase-shift vectors, with Z_u > Z_l, and outputs the first vector in the sorted set.Because the set is sorted by localization loss, the first vector is the current lowest-loss candidate.

VI. PERFORMANCE ANALYSIS

The analysis establishes convergence, bounds computational complexity, and characterizes expected and realization-wise improvement in localization loss. It also shows that sufficiently large global-search budgets can approach global optimality.

  • Convergence: The LMVS algorithm converges because each non-terminal iteration decreases localization loss by at least ϵ, while the loss remains greater than zero.A local minimum is identified when no unit-neighborhood vector improves the loss by more than ϵ.
  • Convergence: The PSO algorithm is guaranteed to converge after (Z_u − Z_l + 1) iterations when each iteration converges and enough distinct phase-shift vectors exist.The paper uses C^M ≫ Z_u to argue that a new local minimum can be generated by random initialization.
  • Complexity: The LMVS algorithm has time complexity O(I^2MN^3), based on evaluating localization loss 2^M times per iteration.One phase-shift vector loss evaluation has complexity O(IN^2).
  • Optimality: The PSO optimality analysis gives E(l_a(c′)) < E(l_a(c_f)) < E(l_a(c′′)) in each global-search iteration.The steepest-descent candidate has lower expected approximated loss than the current best candidate, which is better than the random-input candidate.
  • Optimality: The best candidate’s expected loss decreases across iterations, while each realization is non-increasing and approaches global optimality when Z_u is sufficiently large.The realization-wise result follows from l_a(c_f,z+1) ≤ l_a(c_f,z).

D. Localization Performance

The analysis links localization error to RSS separability and system parameters, showing that RIS design can reduce error by enlarging RSS differences between locations.

  • The expected localization error is negatively related to RSS differences between blocks, so small differences degrade traditional RSS-based localization.
  • RIS integration can enlarge RSS differences between blocks and thereby reduce the expected localization error.
  • The maximum mean RSS occurs when RIS-reflected signals align with the line-of-sight signal, while the minimum can result from cancellation through phase adjustment.
  • In the coarse-grained phase, localization error increases with RSS standard deviation and distances among the AP, RIS, and users.
  • In the coarse-grained phase, localization error decreases as the number of RIS elements and element states increases.

2) Localization Performance of the Fine-grained Localization Phase:

The fine-grained phase focuses RSS differentiation on probable blocks and can progressively reduce localization error, while simulations show strong accuracy under the proposed scheme.

  • Fine-grained localization phase: When both blocks have substantial prior probability, minimizing their RSS difference reduces localization loss; negligible-prior blocks impose no RSS-difference requirement.
  • Fine-grained localization phase: Unlike coarse-grained localization, fine-grained localization increases RSS differences mainly among blocks with large prior probabilities.
  • Fine-grained localization phase: With randomly selected phase shifts and E(s_n) = µ_n, the expected localization error converges to zero as the number of fine-grained cycles increases.
  • Fine-grained localization phase: An accurate RSS model and sufficient cycles are necessary for convergence; model deviation from the actual RSS distribution prevents convergence to zero.
  • Simulation results: When σ = 4dB, the fine-grained proposed scheme achieves le = 0.0479m, more than 8 times smaller than SOCP-T’s le = 0.4381m.
  • Simulation results: The coarse-grained proposed scheme has localization accuracy comparable to the state-of-the-art RSS-based schemes.

B. Simulation for the coarse-grained localization phase

The simulations examine how localization accuracy, convergence, scalability, and runtime vary with distance, users, RIS size, cycles, and localization scheme. The proposed method reduces localization error but incurs implementation or computational trade-offs.

  • Distance and users: Localization error increases with RIS-to-SOI distance while remaining almost unchanged as the number of users increases in the coarse-grained phase.The phase shift vector is fixed in this phase, so users do not influence one another's localization processes.
  • RIS configuration: Localization error decreases as the number of RIS elements and phase-shift states increases, revealing a trade-off between RIS implementation cost and accuracy.More elements and states improve RSS-distribution customization, but increase implementation cost.
  • Convergence: Localization loss and error converge to zero across cycles, while the proposed scheme's error declines faster than the random phase-shift scheme's error.This supports using the approximated localization loss to evaluate localization error during optimization.
  • Fine-grained effects: Localization error increases with both the number of users and their distance from the RIS in the fine-grained phase.Simultaneously optimizing more users requires enlarging RSS differences across more blocks.
  • Fine-grained effects: Localization error increases with the number of blocks but decreases with the number of RIS elements in the fine-grained phase.A larger block range makes radio-environment customization more difficult.
  • Complexity and acceleration: The PSO simulation time grows roughly linearly with RIS elements and quadratically with the number of blocks, while typical indoor scale makes the original runtime extremely long.For a 10×10×3m3 environment with N = 37500 blocks, an acceleration method retains only Nmax blocks with the largest probabilities when calculating localization loss.
  • Runtime comparison: SOA schemes run in around 0.1s with localization errors of 1.7–1.9m, whereas random and proposed schemes take longer but achieve much smaller errors.The comparison uses the accelerated proposed scheme with Nmax = 5 in the typical indoor environment.

APPENDIX A PROOF OF PROPOSITION 1

The proof derives the optimal RSS-based decision rule by partitioning RSS values into decision regions and approximating the resulting localization loss under a high-SNR condition.

  • Loss formulation: The average localization loss is decomposed over users, blocks, RSS values, and decision regions.This formulation connects the decision function to the expected loss induced by RSS-based location estimates.
  • Optimal decision function: For a measured RSS si, the optimal decision selects the block with the minimum ηi,n′ value.The resulting rule minimizes the average localization loss.
  • Decision-region approximation: The proof approximates each decision region by partitioning the nonnegative RSS axis into N subsets.This replaces the original decision-region characterization with a simpler expression.
  • High-SNR approximation: Under high SNR, Gaussian likelihood terms associated with incorrect blocks can be neglected within the relevant RSS region.The approximation retains the dominant term involving the block's prior probability and RSS likelihood.
  • Loss approximation: Gaussian-distribution properties and a union-bound argument yield a tractable approximation of the localization loss.The derivation uses the RSS mean differences and common variance to simplify the relevant integrals.

APPENDIX C PROOF OF PROPOSITION 3

The proof analyzes phase-shift search and repeated fine-grained cycles, showing that iterative search improves expected localization loss and that increasing cycles drives expected loss toward zero.

  • Phase-shift search: The LMVS algorithm generates local-minimum phase-shift vectors with equal probability when initialized by random phase shifts.Their mean localization loss is denoted Ea.
  • Phase-shift search: In the first global-search iteration, selecting the best candidate and applying steepest descent produces a phase-shift vector with no greater localization loss.The selected candidate has expected loss below the initial mean Ea.
  • Global search: In later iterations, added candidates have expected loss no greater than Ea, so the mean loss of the candidate set remains bounded by Ea.The proof states E(Ez) ≤ Ea for iteration z.
  • Multiple cycles: With K cycles, the phase-shift matrix contains one phase-shift vector per cycle, and the expected error is analyzed over these jointly measured RSS values.The k-th row represents the phase-shift vector used in cycle k.
  • Asymptotic behavior: As K increases, the probability of correct decision approaches one and the expected localization loss converges to zero.The proof gives limiting probabilities one for the true block and zero for an incorrect block.
Loading 2011.09323v3…