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存在不可忽略的知识差距。我们研究中的重要一步是将组合编程问题转换为Ising Energy模型，这是量子计算中量子位（Qubit）公式的构件。 使用压缩传感（CS）的概念，并通过离散观察空间，研究将表明可以将本地化问题转化为Ising Energy最小化问题，并可以使用Markov Chain Monte Carlo（MCMC）方法与数字退火器（DA）一起解决。拟议的研究创建了一种解决NP硬性问题的新方法。 解决NP硬性问题的常规方法是放松，如果整数程序是通过可以使用常规优化编程方法来解决的程序近似的。例如，优化问题的目标函数中的L0规范通常被L1规范替换为创建凸面程序。在文献中已经表明，这种替代通常会导致估计偏差。我们的研究创造了一种完全不同的方法。 我们方法中的一个主要创新是直接解决NP - 硬性问题，而没有凸出放松，将问题转换为二进制二次优化（QUBO）问题。 这与现有文献形成鲜明对比，并为制定新的标准和方法创造了绝佳的机会。我们的初步研究表明，该提出的方法消除了凸近似中固有的偏差，并为定位问题提供了更准确的解决方案。