Localization of Wireless Terminals via Ising Energy Minimization

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

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.