Localization of Wireless Terminals via Ising Energy Minimization

通过 Ising 能量最小化实现无线终端的本地化

• 批准号: 572861-2022
• 负责人: Valaee, ShahrokhS
• 金额: $ 12.75万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Alliance Grants
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=751730
• 关键词: Localization; Wireless; Terminals; via; Ising

This project aims to design a system that can estimate the position of a person in a smart environment with sub-meter accuracy. This research will use wireless channel state information (CSI), which is the temporal and spectral behaviour of the wireless channel, for location estimation. CSI is commonly used for effective communication, but unfortunately there is a non-negligible knowledge gap for the application of CSI in location estimation. An important step in our research will be the transformation of combinatorial programming problems into the Ising energy model, which is the building block for quantum bit (QUBIT) formulation in quantum computing. Using the concept of compressive sensing (CS), and by discretizing the observation space, the research will show that the localization problem can be transformed into an Ising energy minimization problem, and can be solved using the Markov Chain Monte Carlo (MCMC) method with Digital Annealer (DA). The proposed research creates a new methodology for solving NP-hard problems. The conventional approach to tackling NP-hard problems is by relaxation, were the integer program is approximated by a program that can be solved using conventional optimization programming methods. For example, an L0 norm in the objective function of an optimization problem is commonly replaced with L1 norm to create a convex program. It has been shown in the literature that this substitution frequently results in biased estimates. Our research creates a completely different approach. A main innovation in our approach is solving NP-hard problems directly, and without convex relaxation, by transforming the problem to a binary quadratic optimization (QUBO) problem. This is in sharp contrast to the existing literature and creates a great opportunity for developing new standards and methodologies. Our preliminary studies show that the proposed method removes the bias inherent in convex approximation and provides a more accurate solution to the localization problem.

该项目旨在设计一种能够在智能环境中以亚米级精度估计人的位置的系统。 本研究将使用无线信道状态信息（CSI）（即无线信道的时间和频谱行为）进行位置估计。 CSI 通常用于有效通信，但不幸的是，CSI 在位置估计中的应用存在不可忽视的知识差距。我们研究的一个重要步骤是将组合编程问题转化为伊辛能量模型，这是量子计算中量子比特（QUBIT）公式的构建块。 利用压缩感知（CS）的概念，通过对观测空间进行离散化，研究表明定位问题可以转化为伊辛能量最小化问题，并可以使用马尔可夫链蒙特卡罗（MCMC）方法来求解数字退火器 (DA)。所提出的研究创造了一种解决 NP 难题的新方法。 解决 NP 难题的传统方法是通过松弛，将整数程序近似为可以使用传统优化编程方法求解的程序。例如，优化问题的目标函数中的 L0 范数通常替换为 L1 范数以创建凸程序。文献表明，这种替代经常会导致估计有偏差。我们的研究创造了一种完全不同的方法。 我们方法的一个主要创新是通过将问题转换为二元二次优化（QUBO）问题来直接解决 NP 难题，并且无需凸松弛。 这与现有文献形成鲜明对比，并为开发新标准和方法创造了绝佳机会。我们的初步研究表明，所提出的方法消除了凸近似固有的偏差，并为定位问题提供了更准确的解决方案。