{"id":170514,"date":"2010-08-11T02:51:18","date_gmt":"2010-08-11T02:51:18","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/project\/ez-localization\/"},"modified":"2023-07-05T12:44:51","modified_gmt":"2023-07-05T19:44:51","slug":"ez-localization","status":"publish","type":"msr-project","link":"https:\/\/www.microsoft.com\/en-us\/research\/project\/ez-localization\/","title":{"rendered":"EZ Localization"},"content":{"rendered":"<p><span id=\"0e79009b-a50c-4fe2-8f1b-10c3f1e6c6b3\" class=\"ImageBlock fn\"><img decoding=\"async\" id=\"Image0e79009b-a50c-4fe2-8f1b-10c3f1e6c6b3\" title=\" \" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2016\/02\/ez-graphic1.bmp\" alt=\" \" \/><\/span><\/p>\n\t\t\t<div class=\"moray-accordion\" data-show=\"false\">\n\t\t\t\t\t\t\t<div class=\"clearfix\">\n\t\t\t\t\t<div\n\t\t\t\t\t\tclass=\"btn-group align-items-center mb-g float-sm-right\"\n\t\t\t\t\t\trole=\"group\"\n\t\t\t\t\t\tdata-mount=\"collapse-controls\"\n\t\t\t\t\t\tdata-bi-aN=\"accordion-collapse-controls\"\n\t\t\t\t\t\tdata-target=\"#accordion-1\">\n\t\t\t\t\t\t<button class=\"btn btn-link m-0\" aria-disabled=\"false\" aria-pressed=\"false\" data-action=\"expand\" type=\"button\" data-bi-cN=\"Expand all\">Expand all<\/button>\n\t\t\t\t\t\t<span aria-hidden=\"true\"> | <\/span>\n\t\t\t\t\t\t<button class=\"btn btn-link m-0\" aria-disabled=\"false\" aria-pressed=\"false\" data-action=\"collapse\" type=\"button\" data-bi-cN=\"Collapse all\">Collapse all<\/button>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<ul class=\"accordion\" id=\"accordion-1\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t<li class=\"m-0\">\n\t\t\t<h4 class=\"accordion-header\">\n\t\t\t\t<button\n\t\t\t\t\tclass=\"btn btn-collapse m-0\"\n\t\t\t\t\ttype=\"button\"\n\t\t\t\t\tdata-mount=\"collapse\"\n\t\t\t\t\tdata-target=\"#collapse-2\"\n\t\t\t\t\taria-expanded=\"false\"\n\t\t\t\t\taria-controls=\"collapse-2\">\n\t\tWhat is EZ Localization?\t\t\t\t<\/button>\n\t\t\t<\/h4>\n\t\t\t<div class=\"collapse\" id=\"collapse-2\">\n\t\t\t\t<div class=\"accordion-body\">\n\t\t\t\t\t\t\t\t\t\t<p>Several applications today leverage location information available to mobile devices to provide a rich set of services.\u00a0EZ 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.<\/p>\n<p>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.\u00a0EZ 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.).<\/p>\n<p>This allows for the possibility where a\u00a0EZ 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.<\/p>\n\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/li>\n\t\t\t\t\t\t<li class=\"m-0\">\n\t\t\t<h4 class=\"accordion-header\">\n\t\t\t\t<button\n\t\t\t\t\tclass=\"btn btn-collapse m-0\"\n\t\t\t\t\ttype=\"button\"\n\t\t\t\t\tdata-mount=\"collapse\"\n\t\t\t\t\tdata-target=\"#collapse-3\"\n\t\t\t\t\taria-expanded=\"false\"\n\t\t\t\t\taria-controls=\"collapse-3\">\n\t\tHow does EZ Work?\t\t\t\t<\/button>\n\t\t\t<\/h4>\n\t\t\t<div class=\"collapse\" id=\"collapse-3\">\n\t\t\t\t<div class=\"accordion-body\">\n\t\t\t\t\t\t\t\t\t\t<p>EZ\u00a0consists of two software components. First, a\u00a0EZ Frontend component residing on the mobile phone that is responsible data acquisition using mobile devices. Second, a computation intensive\u00a0EZ Backend that resides in the cloud and is responsible for building an RF model and for providing location information upon being queried.<\/p>\n<p><strong>Data Acquisition Using Mobile Devices:<\/strong> 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\u00a0EZ 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.<\/p>\n<p><strong>Model Building Using Computational Resorces in the Cloud:<\/strong> The\u00a0EZ Backend receives reports from various mobile devices in the indoor space. Initially the\u00a0EZ Backend has no model of the RF environment of the indoor space in question. As more and more mobile users running\u00a0EZ 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\u00a0EZ 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 &#8220;useful&#8221; 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.<\/p>\n<p><b>Location Queries <\/b>are sent from the\u00a0EZ Frontend and comprise of a scan report. Using the constructed RF model, the\u00a0EZ Backend computes the location of the mobile device and answers the query.<\/p>\n\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/li>\n\t\t\t\t\t\t<li class=\"m-0\">\n\t\t\t<h4 class=\"accordion-header\">\n\t\t\t\t<button\n\t\t\t\t\tclass=\"btn btn-collapse m-0\"\n\t\t\t\t\ttype=\"button\"\n\t\t\t\t\tdata-mount=\"collapse\"\n\t\t\t\t\tdata-target=\"#collapse-4\"\n\t\t\t\t\taria-expanded=\"false\"\n\t\t\t\t\taria-controls=\"collapse-4\">\n\t\tIntuition Behind the EZ Algorithm\t\t\t\t<\/button>\n\t\t\t<\/h4>\n\t\t\t<div class=\"collapse\" id=\"collapse-4\">\n\t\t\t\t<div class=\"accordion-body\">\n\t\t\t\t\t\t\t\t\t\t<p>The key intuition that\u00a0EZ 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.\u00a0EZ models these constraints and then uses them to determine the model and the unknown locations simultaneoulsy.<\/p>\n<p><span id=\"45ded8a6-d519-4b38-a625-eeadc6402ba9\" class=\"ImageBlock fn\"><img decoding=\"async\" id=\"Image45ded8a6-d519-4b38-a625-eeadc6402ba9\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2016\/02\/ez-rigidity4.jpg\" \/><span id=\"ImageCaption45ded8a6-d519-4b38-a625-eeadc6402ba9\" class=\"ImageCaptionCoreCss ImageCaption\"><\/span><\/span><\/p>\n<p>To provide intuition into the working of EZ\u00a0we 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.<\/p>\n<p>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,<\/p>\n<p><span id=\"ea74a0c2-b383-454a-933c-735cdb85b1d0\" class=\"ImageBlock fn\"><img decoding=\"async\" id=\"Imageea74a0c2-b383-454a-933c-735cdb85b1d0\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2016\/02\/ez-pathlosseqn.bmp\" \/><\/span><\/p>\n<p>In (1) <strong><em>p<sub>ij<\/sub><\/em><\/strong> is the recevied RSS at the j<sup>th<\/sup> mobile user from the ith AP, <strong><em>P<sub>i<\/sub><\/em><\/strong> is the transmit power of the i<sup>th<\/sup> AP,\u00a0<strong><em>c<sub>i<\/sub><\/em><\/strong> is the vectorial location of the i<sup>th<\/sup> AP, <strong><em>x<sub>j<\/sub><\/em><\/strong> is the vectorial location of the j<sup>th<\/sup> mobile user,<span id=\"5e208787-d23a-4b6e-9ba2-49a423d15e30\" class=\"ImageBlock fn\"><img decoding=\"async\" id=\"Image5e208787-d23a-4b6e-9ba2-49a423d15e30\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2016\/02\/ez-gammai.bmp\" \/><\/span> is the path loss constant in the vicinity of the i AP, and <strong><em>G<sub>j<\/sub><\/em><\/strong> is the gain of the j<sup>th<\/sup> mobile recevier.<\/p>\n<p>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.<\/p>\n<p>Solving these equations, however, is non-trivial and we have developed a specialzed genetic algorithm to solve them.<\/p>\n\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/li>\n\t\t\t\t\t\t\t\t\t<\/ul>\n\t\t<\/div>\n\t\t\n","protected":false},"excerpt":{"rendered":"","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"research-area":[13547],"msr-locale":[268875],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-170514","msr-project","type-msr-project","status-publish","hentry","msr-research-area-systems-and-networking","msr-locale-en_us","msr-archive-status-active"],"msr_project_start":"2010-08-11","related-publications":[159970,162971],"related-downloads":[],"related-videos":[],"related-groups":[],"related-events":[],"related-opportunities":[],"related-posts":[],"related-articles":[],"tab-content":[],"slides":[],"related-researchers":[{"type":"user_nicename","display_name":"Krishna Chintalapudi","user_id":32577,"people_section":"Related people","alias":"krchinta"},{"type":"user_nicename","display_name":"Venkat Padmanabhan","user_id":33180,"people_section":"Related people","alias":"padmanab"}],"msr_research_lab":[199562],"msr_impact_theme":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170514"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-project"}],"version-history":[{"count":2,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170514\/revisions"}],"predecessor-version":[{"id":953823,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170514\/revisions\/953823"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=170514"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=170514"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=170514"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=170514"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=170514"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}