MIT Turns Wi-Fi into Indoor GPS | Hacker News Reader

MIT Turns Wi-Fi into Indoor GPS

spectrum.ieee.org

194 pointswallflower42 comments

> Although Chronos can run on existing Wi-Fi devices using just an app (or a firmware upgrade for an access point), each device has to undergo a one-time distance calibration.

I worked at at an indoor location-systems startup once. The real fun part of the system was integrating wifi-based location with streaming video from fixed-mount cameras to pinpoint location even better. But let me tell your right off: wifi calibration of the sort they're talking about can be incredibly obnoxious (think "carefully rolling a laptop in a cart at a constant speed around a space, in a grid", which could easily be completed in an hour or two if you are really good at it, but might take a day or two to get right if you aren't.) Sure, this is all fine if you want to calibrate one or two indoor spaces for your automated drones, especially if you've already got APs deployed in a location-friendly mode (i.e. more around the perimeter and less around the center, with antenna orientation to match), but don't expect to see it in a corner store near you anytime soon.

Now, if you can talk about automating the calibration you'll do quite well.

Are Wifi signals even stable enough over time for this to make sense? I thought their signal strength changes and adapts, sometimes even hopping channels automatically.

APs in the 5 Ghz band can hop channels automatically (IEEE N and AC) but APs in the 2.4 Ghz band (IEEE abgn) are locked to the channel they start on. Modern routers automatically choose the "clearest" channel when they start up, but they can't change the channel without user intervention. Once the channel changes all the clients would need to rediscover the network and redo the handshake, i.e they would disconnect and maybe reconnect automatically but maybe not.

They seem to be taking over control of the transmitter, not using ambient WiFi data. So they're really a beacon system. There are lots of those; here's MoteTrack, from Harvard.[1] There's a commercial one, Estimote.[2]

The WiFi industry is working on a standard, called the Fine Timing Measurement protocol, which is now part of IEEE 802.11.[3][4] That provides 100ps resolution timestamps in WiFi packets. That takes care of the RF layer, and provides resolution to about 3cm. (Real world accuracy won't be that good.)

As with GPS, you need at least four fixed stations to get a fix, and preferably line of sight to five, so you can compute the error. You might get that in a big room such as a convention center or gym. If you need it in a house, you'd probably need some additional nodes that are mostly for location, not passing data traffic.

There's no technical problem doing this; it just hasn't been valuable enough to be deployed widely yet. It will probably be a free feature in fixed WiFi nodes soon.

[1] http://www.eecs.harvard.edu/~konrad/projects/motetrack/moteT... [2] http://estimote.com/indoor/ [3] http://www.wi-fi.org/beacon/rolf-de-vegt/never-lost-indoors-... [4] http://www.ieee802.org/1/files/public/docs2014/asbt-kbstanto...

100ps resolution timestamps? That's crazy impressive. I wonder how they accomplished that. It seems unlikely that there is a 10GHz clock that they're using to timestamp asynchronous events, but who knows.

My reference is the fact that 1588 systems usually get into the <25ns RMS offset realm.

This might not even make sense, but maybe they're talking about using the recovered clock from the incoming signal? Something like synchronous Ethernet?

The link posted doesn't go in to much detail, but I'd like to learn more.

They transmit on multiple frequencies. The signals on every frequency will have its own phase offset between the sender and receiver. Think of it as constructive / destructive interference patterns which varies across space, except they have a method where they measure across time multiple times.

At certain multiples of a distance, with synchronized clocks, you'll have offset X between channel Y and Z (on channel Y you may be perfectly phase synchronized, but Z is half the phase off).

Measuring the offsets for multiple sets of frequencies allows you to calculate multiple sets of possible distances, to then figure out which exact distance it is that repeats among all of the calculated distance multiples (like 1, 2, 3; 0.5, 2, 4; 1.5, 2, 3 - the number 2 occurs everywhere).

If for example you're perfectly in phase on 10 frequencies, the distance between you must be a must be a specific shared multiple of the wavelengths of all the frequencies. Least common denominator.

Also, there could be multiple paths (signals bouncing off walls in multiple ways).

Wonder if you could use a Roomba-like robot to do this?

I experimented with position-tracking on a Roomba 780 a couple of weeks ago. I found that its sensors were far too imprecise to get any sort of reliable position. I think the Roomba 980 might work, but it costs > 900 USD.

tl;dr: maybe, but only the very expensive models

I guess you could easily strap a smartphone or laptop to the Roomba to do the actual position tracking.

How much "drift" do you guys have to deal with when using consumer electronics? I don't imagine the calibration being too difficult or numerous these days. Wi-Fi these days is cheap and of high quality.

Very cool. They are using Time Difference of Arrival analysis[1], the fact that most devices have two or more antennas, and clever software to get 10-80 cm accuracy at a good enough frequency to be used as a positional reference in a quadcopter, see the paper[2] for more info

Existing indoor positioning systems such as Bluetooth LE beacons and WiFi triangulation[3] only use the RSSI value and trigonometry to figure out the position. This method is slow (5Hz or so) and the resolution of the RSSI is bad unless you sample it directly, eg with SDR (which incidentally, is what my dissertation is about!)

[1] https://en.wikipedia.org/wiki/Multilateration#Principle

[2] https://www.usenix.org/system/files/conference/nsdi16/nsdi16...

[3] https://www.qualcomm.com/products/izat (unfortunately there are no public 'specs' I can find...)

Point of note: Multilateration (link [1] above) is the real name for the process that ordinary people casually call "triangulation" when they're talking about wifi location. It's not actually triangulation (which determines location based on the angle) but it's based on circles (or spheres, I guess - based on the distance).

For those interested, I'm working on an open-source project for doing this at home: https://github.com/schollz/find

My solution basically uses the RSSI values for generating classifiers for each room. It works well enough to replace motion sensors.

Is this looking at the rssi of all networks seen, or playing with the device you're on? Does this work for iPhones?

Yes, it looks at the RSSI of all networks seen, generates distributions of the RSSI signals, and then leverages those distributions using some naive machine learning to classify the location.

It does not work for iPhones. Unfortunately, Apple keeps the WiFi scanning in a "private" api which would require jailbreaking because, as far as I know, use of those apis won't get past the app-store review.

So, for now it only works on Android and on laptops/single-board computers using a Python script (links to app and script in Github).

Why not just have the iPhone app act as a Bluetooth LE beacon? You can do that without jailbreaking, and BLE signals are in the 2.5GHz band.

As I understand it, the technique used is to create a map of the room by listening and recording all RSSI from all stations and training classifiers. Then the app listen to all stations, input the RSSIs, and the classifiers give you back a location in the room. So the iPhone is supposed to just passively listen, not emit any signal – but apparently you can't access all RSSIs values of your surrounding stations via public APIs on iOS.

In any case, it's a clever way to map the room by its spectrum landscape :-)

Thanks for that explanation. Makes sense.

Any chance of getting it to work natively on android as a standalone library without cordova? Being able to integrate a library over Gradle into an existing app would be really really nice.

That's a good idea! I'll look into it.

If you are interested, we are doing something similar at http://www.smartertime.com with an automated learning and update phase. It gives a "one click and forget" location system. All algorithms run on the phone, and the user only has to tell the app things like "this is my kitchen".

Its amazing how everything MIT touches, they make sure its in the HN title. Good branding I guess.

Anyone with inside knowledge know if this is something that will actually make it to market. They are talking about commercializing supposedly, according to the article, but I would be surprised if this isn't something that just gets incorporated into ios and android if it actually is as good as they claim. Its not like (i)beacons managed to truly become an apple owned thing.

Not taking anything away from this very novel work, but MIT definitely has a well oiled PR apparatus to publicize their research. This is a good thing from the perspective of science advocacy and outreach. But it is less good from the perspective of other researchers working in similar areas whose work can get eclipsed this way.

This is definitely a deceptive practice. Claiming this was developed by MIT is kind of like claiming that the theory of relativity was developed by the Swiss patent office. MIT is just the place where the researchers were working. To add insult to injury, the names of the researchers are withheld until the 6th (!) paragraph of the article.

Thats not an accurate analogy at all. These researchers presumably utilized MIT resources extensively while being paid by MIT specifically to conduct research in addition to other duties. Without MIT or a similar host institution their ability to conduct research such as this would have been severely constrained.

In fairness a better title would be "MIT researchers turn Wi-Fi...", and it would definitely have been good to mention the researchers' names earlier.

The startup world is similarly situated.

Those who are good at getting their voices heard triumph in "unfair ways," except those who don't misunderstand the totality necessary to have good work shine.

Can confirm, MIT people love to mention MIT.

If they can prove it works at scale this tech instantly eliminates the usefulness of beacons.

Wifi has always been the obvious solution to indoor location (lower power than GPS / works indoors / piggybacks on installed hardware / somewhat "open") but fidelity was too low.

Hence the rise of beacons.

Beacons IMO are the least elegant solution to the problem of indoor location because they require (a) a whole separate location framework (b) requires vendors / stores to install & maintain hardware to drive coverage (c) are owned by the OS.

I've been watching this game unfold for years - Apple bought WifiSLAM in 2013 to improve indoor location / wifi (1), and then bought "super accurate GPS" firm coherent NAV last year. (2)

There are also several startups attempting to use sensor data + geomagnetic or inertial navigation to solve this problem. (3)

If these guys actually got Wifi working, and figure out a way around the callibration problem, they in one fell swoop solved one of the major barriers to the hyper-localized advertising / consumer tracking that we've been promised (threatened with?) for years.

(1) http://www.theguardian.com/technology/2013/mar/25/apple-buys...

(2) http://blogs.wsj.com/digits/2015/05/17/apple-buys-gps-firm-c...

(3) http://www.navisens.com/, GiPStech.com, http://www.PathSense.com, https://www.indooratlas.com/

> Hence the rise of beacons.

Good riddance. So far beacons are widely used for just one thing - spamming peoples' phones with ads in stores. We've been promised indoor location accurate to 5cm; I haven't seen anyone deliver it yet.

Beacons with full AR will be marvelous (for as long as the end user is in control of the experience).

Eh? There are a lot of legit medical uses in automation of senior care, etc. There are products out there based on beacons.

Beacons are used in the Brooklyn Museum to give you more info about your favorite exhibits.

We had this problem at a previous job - how to locate a piece of medical equipment so that a nurse can quickly get it when needed (they get moved around and their locations typically aren't communicated at shift change). Ordinary WiFi wasn't good enough - it had roughly 1.2 meter accuracy, which given that radio waves can pass thru a wall, couldn't tell you if the device was in room 201 or the adjacent 203. Which is a problem when seconds counted.

The fact that they can do this with just a firmware update is excellent news. Hopefully they'll license it to some of the big commercial access point vendors (Cisco, etc).

It seems that the advance here is not that WiFi can be used as an alternative to GPS, but that sweeping multiple frequencies allows for high precision timing measurements (hence the name "Chronos"). I suspect the same could be done with cellular frequencies on a much larger scale with similar improvements in accuracy. I am curious how the precision scales with more channels and lower frequencies.

Edit: Apparently exploiting the phase change of a signal has been used to improve the accuracy of GPS in a similar ways [0]. The dual radio angle calculation seems to be a more novel advancement.

[0] https://en.m.wikipedia.org/wiki/Real_Time_Kinematic

Accurate Wi-Fi based indoor location positioning already exists, though with different pros and cons. For example, the following system still works reliably when walking around, but may be a bit less accurate. And it requires no calibration https://www.youtube.com/watch?v=foVqKLE4Mpk

That demo is based on the new 802.11mc standard. Surprisingly, this new standard isn't mentioned in the paper. So no comparison between this and their system...

This is the same tech Prof. Katabi demoed to President Obama. She demonstrated using the tech to detect pulse rate if I recall correctly.

Here's a link: http://news.mit.edu/2015/president-obama-meets-mit-entrepren...

Very cool. But does this work if the device is actually trying to use its wifi connection for data? I'd assume that rapidly hopping between all the channels would interfere with the normal duties of the wifi card.

I think that if a device hops in the 2.4 GHz band it loses the connection to the AP and it goes offline. So this location system will be useful to locate carts in a shop but not customer's phones connected to that shop free WiFi. And even if the customer is not connected to the AP and the phone still has the WiFi on (extremely common), I think you need an app to do that. Furthermore I expect this to impact on battery quite a bit.

I was in a giant mall yesterday where I knew what I wanted, from which outlets but with little idea where those outlets were. Indoor turn by turn navigation would have saved me 30+ mins.

Which the mall would not like, so they won't be helping you out here.

depends on the mall. i just found out one mall in my city have an automated direction on the directory machine itself. not true turn-by-turn, but helps a lot rather then guessing the places of escalator on the maps and whatnot.

Reply on news.ycombinator.com