Grant: Alliance Grants
University of Toronto
$175,000.00
Localization of Wireless Terminals via Ising Energy Minimization
EF 2022-23
Résumé
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.
Programme
Alliance Grants
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
572861-2022
Name nom
Valaee, Shahrokh S
Department département
Electrical & Computer Engineering, Edward S. Rogers Sr. Department of
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2022
Award amount
175000
Program id
ALLRP
Program name en
Alliance Grants
Program name fr
Subventions Alliance
Group en
RESEARCH PARTNERSHIPS
Group fr
PARTENARIATS DE RECHERCHE
Committee code
96
Committee name en
RPP Internal Decision Cttee
Committee name fr
Cté de décision interne - PPR
Area of application code
804
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Communication systems and services (planning, organization, services)
Area of application fr
Systèmes et services de communications (planification, organisation et services)
Research subject code
2514
Research subject group en
Electrical and electronic engineering
Research subject group fr
Génie électrique et électronique
Research subject en
Digital signal processing
Research subject fr
Traitement des signaux numériques
Installment
inst:1
Partie
1
Nb partie
1
Application title
Localization of Wireless Terminals via Ising Energy Minimization
Application summary
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.