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通常用于有效的通信，但不幸的是，CSI在位置估计中的应用存在一个不可忽视的知识缺口。我们研究的重要一步将是将组合规划问题转化为伊辛能量模型，该模型是量子计算中量子比特(QUBIT)公式的基础。利用压缩感知(CS)的概念，通过对观测空间的离散化，研究表明定位问题可以转化为Ising能量最小化问题，并可以使用马尔可夫链蒙特卡罗(MCMC)方法和数字退火器(DA)来求解。所提出的研究为解决NP-Hard问题创造了一种新的方法。解决NP-Hard问题的传统方法是松弛法，其中整数规划由可以使用传统优化编程方法求解的程序来近似。例如，优化问题的目标函数中的L0范数通常用L1范数来代替，从而产生一个凸规划。文献中已经表明，这种替代经常导致有偏见的估计。我们的研究创造了一种完全不同的方法。我们方法的一个主要创新是通过将问题转化为二次二次优化(QUBO)问题来直接求解NP-Hard问题，而不是凸松弛问题。这与现有文献形成了鲜明的对比，并为开发新的标准和方法创造了巨大的机会。我们的初步研究表明，该方法消除了凸近似所固有的偏差，并为定位问题提供了更准确的解决方案。