EZ Localization

Several applications today leverage location information available to mobile devices to provide a rich set of services. EZ is a technique that can be used to localize users inside indoor enviroments where GPS signals do not penetrate (e.g., large malls, office buildings etc.), by leveraging the presence of already existing WiFi Access points in the indoor environment.

Several prior research efforts have focused on leveraging the near-ubiquity of WiFi for indoor localization. However, the need for a significant degree of pre-deployment effort remains a key challenge. For example, war-driving based techniques require measuring the received signal strengths (RSS) at several known locations and constructing a database. EZ localizes users without requiring any pre-deployment mapping or explicit measurement effort and without any prior knowledge of the WiFi access points (their locations, transmit powers, etc.).

This allows for the possibility where a EZ localization server in the cloud provides indoor localization services to a mall in the US or in Dubai, without ever contacting the mall authorities or relying on any explicit input from the mall goers.

EZ consists of two software components. First, a EZ Frontend component residing on the mobile phone that is responsible data acquisition using mobile devices. Second, a computation intensive EZ Backend that resides in the cloud and is responsible for building an RF model and for providing location information upon being queried.

Data Acquisition Using Mobile Devices: The EZ Frontend is a piece of software that can be downloaded and installed on a mobile device. As the users go about their normal activity in the indoor space, oblivious to them, the software periodically scans the access points (APs) in view and sends a WiFi scan report to the EZ backend residing in the cloud. A report comprises the list of APs and the corresponding Received Signal Strength (RSS) measurements. As the users walk around the indoor space, reports are generated from several different but unknown locations for each mobile device. Occasionally, a mobile device will also obtain a GPS lock, say at the entrance or near a window, or in the immediate vicinity of the indoor space and report the GPS coordinates at these locations as well.

Model Building Using Computational Resorces in the Cloud: The EZ Backend receives reports from various mobile devices in the indoor space. Initially the EZ Backend has no model of the RF environment of the indoor space in question. As more and more mobile users running EZ software on their mobile phones enter and move about in the indoor space, the SLAM Backed keeps accumulating reports from them. After accumulating enough reports, it then uses the EZ Algorithm to construct an RF environment model of the indoor space based on the reports. A pre-filtering stage is extremely crucial to cull out a “useful” subset of data from the deluge of reports from the large number of participating mobile phones and to segment the raw data reported from different indoor spaces.

Location Queries are sent from the EZ Frontend and comprise of a scan report. Using the constructed RF model, the EZ Backend computes the location of the mobile device and answers the query.

The key intuition that EZ uses is that all of the observations reported to the server, even those from unknown locations, are constrained by the underlying physics of wireless propagation. EZ models these constraints and then uses them to determine the model and the unknown locations simultaneoulsy.

To provide intuition into the working of EZ we start with a simple example. Say there are two users (M1,M2) and two APs (AP1,AP2) and somehow we know all the four AP-user distances as shown in Figure 1. Based on this information, several different quadrilaterals can be constructed, with locations of the APs and users as the vertices as depicted in Scenarios I-A and I-B. In other words realization of the relative locations (modulo translation, rotation, and reflection) of the APs and users is not unique. However, it can be proved that if there were three APs and three mobile users, there can only be a unique realization for the relative locations of the APs and the users (Scenario II). This demonstrates that given enough distance contraints between APs and mobile users one can uniquely determine their locations in a relative sense.

In practice, however, distances between APs and mobile users can only be inferred through received signal strength (RSS). A popular model that relates distance to RSS is given by,

In (1) p_ij is the recevied RSS at the j^th mobile user from the ith AP, P_i is the transmit power of the i^th AP, c_i is the vectorial location of the i^th AP, x_j is the vectorial location of the j^th mobile user, is the path loss constant in the vicinity of the i AP, and G_j is the gain of the j^th mobile recevier.

For each RSS observation we obtain one equation of the form (1). Since a large number of observations can be collected from different locations (some known locations but mostly unknown locations) for each user as they move about, eventually we will have enough equations (i.e., constraints) to solve for all the variables.

Solving these equations, however, is non-trivial and we have developed a specialzed genetic algorithm to solve them.