A study of wireless localization problems

• Grant number: 13/25152-8
• Support Opportunities: Scholarships abroad - Research Internship - Master's degree
• Start date: February 01, 2014
• End date: April 30, 2014
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cid Carvalho de Souza
• Grantee: Bruno Espinosa Crepaldi
• Supervisor: Sándor P. Fekete
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Institution abroad: University of Technology Braunschweig, Germany
• Associated to the scholarship: 12/17608-9 - Wireless Localization Problem: a geometric and algorithmic study, BP.MS

Abstract

The Wireless Localization Problem is a variation of the classical art gallery problem, that deals with the placement of the smallest number of broadcasting antennas required to satisfy some property with respect to a given polygon. Each antenna that is installed must propagate a unique key within a certain specific angle of broadcast in a such a way that the set of keys received at any given point is sufficient to determine whether that point is inside or outside the polygon. To ascertain this localization property, a Boolean formula must be produced along with the placement of the antennas. This research internship at Technische Universität Braunschweig aims to deepen the investigation on the algorithms developed in the student's MSc dissertation and check the feasibility of extending the algorithm to tackle other variants. (AU)