1stLoc — Provisioning Location As a First-Class Citizen of Mobile OS

The content from Microsoft Research  Project 1stLoc

The proliferation of location-based services, applications, and social networks calls for the provisioning of location service as a first class system component. Such location service should have short response time (better instantly available), provide high location accuracy and work seamlessly across outdoor and indoor environments. To achieve these goals, we seek to push down the energy envelop and enable continuous localization in the background, to explore the infrastructure intelligently.

Travi-Navi: Self-deployable Indoor Navigation System

Technology Overview: we design Travi-Navi, a trace-driven vision-guided navigation system that enables a self-incentivized user to easily bootstrap and deploy her own indoor navigation services, without dependency on the availability of a comprehensive indoor localization system and even the availability of floor maps. Travi-Navi collects a rich set of sensor readings, records high quality images during the course of guider’s walk on navigation paths, and packs them into a navigation trace. In navigation, it tracks the follower to the navigation trace, alerts the user when derailed, and prompts text and visual instructions and also image tips. Travi-Navi also finds the shortcuts whenever possible. We encounter and solve several challenges including robust tracking, shortcut identification and high quality image capture during walking.

Application Scenarios: Many real-world scenarios, spanning businesses, social and personal desire, where users are self-motivated to build their own navigation system. E.g., for real world businesses, a shop owner may want to gather the path and navigation information to guide potential customers to her shop. In social gathering scenarios, an early arrived user may want to tell late comers the way to the gathering location. For individuals, it often happens that one may forget where the car is parked and want to trace back to the car.

Modellet: exploring locality-preserving models for WiFi environment

Technology Overview: we found and tackled the performance issues of existing localization approaches, both fingerprint-based and model-based, caused by the uneven data density of the location database and environmental diversities. Realizing that, in general, fingerprint-based approaches is more favorable under dense databases while model-based approaches work better for sparse training data, we propose Modellet that organically fuses information from both measured fingerprints and signal propagation models. Built upon the two new concepts namely, fingerprint-cloud and supporting set, Modellet is able to adapt the localization system to various data densities and environment conditions. With extensive evaluation, we showed that Modellet always achieves the best accuracy with a significant margin, up to 50% improvement. We also discussed and handled a few practical issues including the device diversity and merging virtual APs.

Epsilon: a visible light based localization system

Technology Overview: Witnessing the increasingly wide use of Light-emitting Diode (LED) lighting, we design Epsilon that leverages visible LED lights for accurate localization. In current design, we have chosen a model-based ranging and trilateration-based localization method. We identified and tackled several technique challenges. In particular, we establish and experimentally verify the optical channel model for localization. We adopt BFSK and channel hopping to enable reliable location beaconing from multiple, uncoordinated light sources over the shared optical medium. We handle realistic situations towards robust localization, for example, we exploit user involvement to resolve the ambiguity in case of insufficient LED anchors. Our evaluation results demonstrate that we can achieve sub-meter accuracy (at 90 percentile), which is a leapfrog to the main stream WiFi-based localization systems. As our ongoing work, we are investigating other approaches to use the lighting infrastructure for localization purpose. We also plan to design the protocols and turn lights into location beacons, as a competing solution to iBeacon.

Application scenarios: The pervasiveness of the lighting infrastructure makes Epsilon a good candidate for any indoor localization environments. Its unprecedented localization accuracy can enable new scenarios such as facilitate finding or navigation to the objects, physical analytics, and gesture-based interactions (if integrated into wearables), etc.

WheelLoc: Enabling Continuous Location Service on Mobile Phone for Outdoor Scenarios

We design and implement a continuous system location service – WheelLoc – on mobile phone for instantaneous, energy-efficient location provisioning for outdoor scenarios. Unlike previous localization efforts that try to directly obtain a point location fix, WheelLoc adopts a detoured approach: it seeks to capture a user mobility trace first and to obtain any point location by time- and speed-aware interpolation or extrapolation. Unlike previous work that explores an accuracy-energy tradeoff between sensors that are either energy efficient or costly, WheelLoc avoids expensive sensors completely andsolely relies on commonly available cheap sensors such as accelerometer and magnetometer. With a set of novel techniques and the leverage of publicly available road maps and cell tower information, WheelLoc is able to meet those requirements of a first class component. In particular, we study reliable and accurate capture of user mobility trace using only sensors on mobile phone for driving and cycling cases. We perform map-matching to fix captured traces to the map using a novel HMM model. Extensive experiment results confirmed the effectiveness of uLoc. It can return a location estimate within 40ms with an accuracy about 40 meters, consumes only 240mW energy, and effectively strikes a better energy-accuracy tradeoff than GPS duty-cycling.

* Joint work with my interns He Wang (now at Duke), Zhiyang Wang (now at UCLA) and colleague Fan Li (now at Pearson.com).

Walkie-Markie: Crowdsourcing-friendly Indoor Mapping and Localization System using Mobile Phones

Accurate and cheap indoor localization is one of the holygrails of mobile computing, as it is the key to enabling indoor location-based services. The problem has attracted significant interest in both academia and industry. One important element in indoor localization, which has so far been largely overlooked or just taken for granted (with assumptions), is the availability of the suitable indoor map, which associates any location to the physical layout inside the building. This is one of the major reason accounting for the ironic facts that so many algorithms were proposed but none become reality. Walkie-Markie (a.k.a FeetLoc) project seeks to attack this fundamental problem by enabling a crowdsourcing way of indoor mapping, including pathway mapping and also the automatic establishment of a radio map that can be readily used for localization. Walkie-Markie requires no prior knowledge of the building, except the mere existence of the WiFi infrastructure. We are working on how to further dismiss this assumption on the existence of the WiFi infrastructure.

* Joint work with my interns Zhuo Chen (now at CMU), Peichao Zhang (now at SJTU), and colleague Yongguang Zhang.

I/ODetector: A Generic Service for Indoor/Outdoor Detection

The location and context switching, especially the indoor/outdoor switching, provides essential and primitive information for upper layer mobile applications. We design and implement I/ODetector: a lightweight sensing service which runs on the mobile phone and detects the indoor/outdoor environment in a fast, accurate, and efficient manner. Constrained by the energy budget, I/ODetector primarily leverages lightweight sensing resources including light sensors, magnetism sensors, celltower signals, etc. I/ODetector is designed to work independently using on-board sensors and provide an instant indoor/outdoor detection. We do not need to fingerprint the environment to acquire a priori knowledge. Being such a generic and lightweight service component, I/ODetector greatly benefits many location-based context-aware applications. We explore some exampler applications such as energy saving for GPS and WiFi.

* Joint work with Dr. Mo Li (Nanyang Tech Univ, Singapore) and his team.
Jacky Shen

Jacky Shen

Chunshui Zhao

Chunshui Zhao

Feng Zhao

Feng Zhao


Comments are closed