Transcript MSR tech talk

Location Based Services
Lenin Ravindranath, Microsoft Research India
Motivation


Location is a key element of user context
Mobile devices a natural conduit for location based
services



Location -> GPS



They are ubiquitous
Have many sensors sensors
GPS based devices are not common
GPS is power hungry
Many apps care about relative location


relative to landmarks
relative to people
Scenario
Demo!
Aspects

Location Determination


Neighborhood Discovery


spatial and temporal
Communication



need relative location
push vs. pull
with or without Internet access
Service model

stateful vs. stateless
Overview

Beacon-Stuffing


Neighborcast



WiFiAds
People Near Me
Neighborhood GPS
Landmark based Services




Post-its in the air
Ads, comments and reviews
Location and Neighborhood based reminders, profiles
Social networking
Beacon-Stuffing
WiFi Beaconing Protocol
Access Point
Network Name
SSID: NYCWireless
Beacon Packets
Network Name
SSID: T-Mobile
Connected
Networks Found
Connected
Beacon-Stuffing

Stuff beacon packets with information





Unused fields in beacons (Beacon Information Element)
Stripe across multiple beacons, if needed
Clients receive beacons even when they are not
connected to any network
Clients receive beacons from other networks even when
they are connected to a particular network
Send dynamic information
WiFiAds – Location sensitive Ads
CoffeeDay
close to me..
Hmm!
WiFi Beacon
Coffee Day
Drink of the day is Hot Chocolate
Client running our software
I love Hot
Choc! Go to
CoffeeDay 
AdCenter AP
at CoffeeDay
Within 250 m of CoffeeDay
Beacon-Stuffing Summary

No absolute location required

Clients near the broadcasting AP gets the information

Push model of information delivery
No connectivity required
Stateless

Published in HotMobile 2007




Joint work with Ranveer Chandra, Jitu Padhye, Alec Wolman
Techfest 2007 Demo
Overview

Beacon-Stuffing


Neighborcast



WiFiAds
Buddies Near Me
Neighborhood GPS
Landmark based Services




Post-its in the air
Ads, comments and reviews
Location and Neighborhood based reminders, profiles
Social networking
Neighborcast

Goal: communication among nearby nodes


2 nodes are nearby if they hear a common AP
Nearby nodes can be on different frequency channels
LAN/Internet
Neighborcast

Solution: Leverage multicast techniques

Mapping from AP BSSID to multicast group address


Client joins group of every AP around it


BSSIDs correspond to AP’s MAC ID, and is globally unique
APs it hears as part of its scanning process
Clients frequently publish info on group of associated AP

Infrequently publishes info on other groups it is subscribed to
Neighborcast
LAN/Internet
00:0A:80:12:34:55
00:0B:80:12:34:56
00:0C:80:12:34:57
Multicast group for BSSID 00:0B:80:12:24:56
Implementing Neighborcast

3 approaches:




IP Multicast
Application Level Multicast (ALM)
Pub-sub using RSS feeds
Tradeoffs: overhead, scalability, ease of deployment
Neighborcast using IP Multicast

Map AP’s BSSID to IP multicast group address



BSSID (6 bytes): <Manufacturer’s prefix>:XX:XX:XX:XX
IP multicast address (4 bytes): <224 – 239>:XX:XX:XX
Our mapping approach:


228.XX.XX.XX, where XX:XX:XX is last 3 bytes of BSSID
Example: 00:17:95:81:CA:30 will be 228.129.202.48


Since 0x81 = 129, 0xCA = 202, 0x30 = 48
Might have collisions! Probably not in same subnet…
Neighborcast using IP Multicast

Neighborcast using IP multicast:




Pros:



Every client maps AP’s BSSID to IP multicast address
Joins multicast group of all BSSIDs it hears
Publishes info of multicast group of AP it is associated with
No need for special infrastructure/server
Approach is scalable since all traffic is local
Cons:

Limited deployment of IP multicast, only in edge networks
Buddies Near Me




Each client joins Neighborcast group of all APs around
it
It announces its presence (along with signal strengths)
to its Neighborcast group
Learns of nearby buddies
Can also estimate “nearness”

Signal strength
Neighborhood GPS

Dynamically help neighbors leverage GPS data from
other phones
Cloud/Server
GPS
computed-location
Neighborcast Summary

No absolute location required

Two clients are nearby if they hear a same AP

Neighborcast forms IP overlay among nearby nodes
Client needs to be connected
Stateless

Published in HotMobile 2008




Joint work with Ranveer Chandra, Jitu Padhye
Techfest 2008 Demo
Overview

Beacon-Stuffing


Neighborcast



WiFiAds
People Near Me
Neighborhood GPS
Landmark based Services




Post-its in the air
Ads, comments and reviews
Location and Neighborhood based reminders, profiles
Social networking
Location as Landmarks

For many apps absolute
location (GPS) is not
required

Location as perceived by a
user

Landmarks


Access Points BSSID
GSM Tower ID
GSM Tower
Access Point
Information tagged with Landmarks

Users publish information

Landmark Tagged Information



Automatically tag information published with landmarks
Pictures, Videos, Blogs, Ads
Users search for information

Landmark based Search

Query information based on landmarks
Landmark based services
GSM Tower GSM1
Tower ID: XX1
Server
Search
(query, AP BSSID, GSM ID)
Access Point AP1
BSSID: 00:11:22:33:44:55
Publish
(info, AP BSSID, GSM ID)
Post-its in the air
Post-its in the air





Scan for landmarks
Post (tagged with landmarks)
Search (giving landmarks)
Retrieve post-its in the air
Challenges
 What if a landmark moves?


Move posts to Neighborhood
How to find the neighborhood?

Radio map
Radio Map


Periodically clients report Access Points and GSM towers seen
Build a graph




Nodes are APs/GSM Towers
Edge between two nodes if they are reported together
Node weights and Edge Weights
Delete nodes and edges based on their weights
Wi
Fi
Wi
Fi
Wi
Fi
GSM
Wi
Fi
Wi
Fi
Wi
Fi
Wi
Fi
GSM
Wi
Fi
Wi
Fi
Wi
Fi
Wi
Fi
Wi
Fi
Wi
Fi
Wi
Fi
Buddies Near Me
GSM
GSM
WiFi
WiFi
WiFi
WiFi
WiFi
WiFi
WiFi
Buddies who were here

You are visiting a new place



Need to know information and past experience of people
Find friends who visited this place in the past
Find them online

Ask queries
Location Sensitive Search

Search for Coffee


Gives nearby Coffee shops info
Search results ranked based on nearness
Comments and Reviews


Read others reviews
Post comments
Reminders in the air

Location based reminders


Post reminders in the air
Remind me when I cross this place next time



Remind me to buy milk when I am near the market
Remind me office work only when I am in the office
Neighborhood based reminders

Remind me when one or more friends are nearby at a location

Remind me to give Prashanth Rs 100 when he comes nearby
Other Applications




Location based profiles
Location based games, Game pairing
Dating service
Enhanced presence
Landmark based services Summary

No absolute location required

Leverage Landmarks and Neighborhoods

Client needs to be connected
Stateful
Number of applications

Submitted to Ubicomp 2008




Joint work with Mohit Gupta, Prashanth Mohan
Thinkweek paper (Brooks was here.. So was Red)
Benefits
•
Does not depend on GPS
•
•
•
•
•
Lesser power
Works inside buildings, malls
No regular war driving necessary (as is in the case of
WiFi, GSM triangulation)
Readily deployable
No operator support required
Questions
Code in the air



Post code in the air
Devices crossing that location will execute them
Harnessing other devices

Example


Monitor temperature at a place continuously
Post the following code in the air
use sensor(themometer)
temp = themometer.getTemperature()
send(temp, “http://leninr/tempService”)