Hackaday Prize Best Product: WiFi Location Services

GPS-based location services will be around with us forever. If you’re in the outback, in the middle of the ocean, or even just in a neighborhood that doesn’t have good cell coverage, there’s no better way to figure out where you are than GPS. Using satellites orbiting thousands of miles above the Earth as a location service is an idea that breaks down at some very inopportune times. If you’re in a parking garage, you’re not using GPS to find your car. If you’re in a shopping mall, the best way to find your way to a store is still a map. Anyone every tried to use GPS and Google Maps in the hotel/casino labyrinth that is the Las Vegas strip?

[Blecky]’s entry for the Best Product competition of the Hackaday Prize aims to solve this problem. It’s an indoor location service using only cheap WiFi modules called SubPos. With just a few ESP8266 modules, [Blecky] can set up a WiFi positioning system, accurate to half a meter, that can be used wherever GPS isn’t.

The idea for a GPS-less positioning system came to [Blecky] after a caving expedition and finding navigation though subterranean structures was difficult without the aid of cell coverage and GPS. This got [Blecky] thinking what would be required to build a positioning service in a subterranian environment.

1679491438515290398
A SubPos node, equipped with an ESP8266 WiFi module

The answer to this question came in the form of a cheap WiFi module. Each of the SubPos nodes are encoded with the GPS coordinates of where they’re placed. By transmitting this location through the WiFi Beacon Frame, along with the transmitted power, any cell phone can use three or more nodes to determine its true location, down to a few centimeters. All of this is done without connecting to a specific WiFi network; it’s a complete hack of the WiFi standard to allow positioning data.

The most shallow comparison to an existing geolocation system would be a WiFi positioning system (WPS), but there are several key differences. In WPS, the WiFi APs don’t transmit their own location; the AP is simply cross-referenced with GPS coordinates in a database. Secondly, APs do not transmit their own transmit power – important if you’re using RSSI to determine how far you are from an Access Point.

The best comparison to an indoor location service comes from a new Decawave module that sets up ‘base stations’ and figures out a sensor’s location based on time of flight. This, however, requires additional radios for each device receiving location data. SubPos only requires WiFi, and you don’t even need to connect to an AP to get this location data; everything is broadcast as a beacon frame, and every device with WiFi detects a SubPos node automatically.

As an entry to the Hackaday Prize Best Product competition, there is an inevitable consideration as to how this product will be marketed. The applications for businesses are obvious; shopping malls could easily build a smartphone app showing a user exactly where in the mall they are, and provide directions to The Gap or one of the dozens of GameStops in the building. Because the SubPos nodes also work in 3D space, parking garage owners could set up a dozen or so SubPos nodes to direct you to your exact parking spot. Disney, I’m sure, would pay through the nose to get this technology in their parks.

Already [Blecky] is in talks with one company that would like to license his technology, but he’s not focused only on the high-dollar business accounts. He already has a product that needs manufacturing, and if he wins the Best Product competition, he will be working on something for the hacker/homebrew market. The price point [Blecky] sees is around $15 a node. The economics of this work with the ESP WiFi module, but [Blecky] is also looking at alternative chip sets that would allow for more than just RSSI position finding; an improved version of the SubPos node not based on the ESP-8266 could bring time of flight into the mix, providing better position accuracy while still being cheaper to manufacture than the current ESP-based solution.

[Blecky] has a great project on his hands here, and something we will, undoubtedly, see more of in the future. The idea of using WiFi beacon frames to transmit location data, and received signal strength to suss out a position is groundbreaking and applicable to everything from spelunking to finding your car in a parking garage. Since the SubPos system isn’t tied to any specific hardware, this could even be implemented in commercial routers, giving any device with WiFi true location data, inside or out. It’s also one of the top ten finalists for the Hackaday Prize Best Product competition, and like the others, it’s the cream of the crop.

The 2015 Hackaday Prize is sponsored by:

34 thoughts on “Hackaday Prize Best Product: WiFi Location Services

  1. Huh. I just spent about three hours last week with a client figuring out how to do this same type of thing for conference settings, using strictly software. The *biggest* hurdle was getting iOS/Android/Windows/etc. to talk to each other. #nailedit

  2. A problem may be, that if a sender is covered by something the reciver will get a lower power level.
    Now imagine in a mall, where every where something sends in the 2.4Ghz range, im not that optimistic that there wont be interference.
    But maybe Blecky worked that long out ago..

  3. excuse me, but I’m **highly** sceptical of this one. WiFi is used in indoor scenarios (which coincides with loss of GPS reception, yes).

    Indoor scenarios are mainly described by the fact that the dominant path from TX to RX is **not** line-of-sight, but a complex multipath environment, so that destructive and constructive interference from different paths really really doesn’t even remotely correlate well with TX-RX distance. It’s a nice demo that this works in an empty parking garage — but it simply won’t somewhere where you’d actually need it, e.g. in a place that’s full of parallel, metal cars, or in a shopping mall, or in a storage facility with rows of metal cupboards, or in an office building, or in fact anywhere, where line of sight isn’t, by far, the dominant mode of communication.

    There’s extensive, even standardized models, for indoor propagation, and they **all** predict that; subpos simply ignores the fact. Won’t work.

    1. It is the simplest solution anyone can think of, it has been tried many times and researched and tested. It if were to work well enough in real life, we would have it already in the phone. But wait….it already is there. I have used it many times….accuracy can vary a lot.

      At home i tried to do some localization inside the house for a vacuum robot using the RSSI of all the wireless networks around. I got discouraged the moment it started to survey just one place and realized how much everything varied.

      I am betting on things like Decaware being introduced in phones, since they use time rather than signal strength. Now if only somebody could implement the same thing over GSM frequencies….

      1. It definitely does vary a lot in small spaces, but I am looking to implement time of flight in this as well with a specialised receiver to help mitigate this (with controlled beacon frame timing). While time of flight in this instance won’t work well, if at all, in smartphones (due to the inaccessibility of low level firmware), it will still work for these devices too while just giving you courser positioning.

        I’m not doing anything special on the positioning front (other than what’s already been done), SubPos was just designed as a backwards compatible alternative to Google’s Wi-Fi location services but in a dataless form (you raise the point of having to put Decawave in phones, which would be awesome IMO, but difficult at best). Every other system on the market requires the transfer of data host-side (even the Decawave requires this as part of its protocol to the surrounding beacons), SubPos however is one way only.

        1. I like the idea of one way, but it is clear why Google is doing it this way: it’s automatic, you just correlate the gps and Wi-Fi data.
          Time of flight over wifi could do better, but i am not sure if you can get anything reasonable using only 2.4Ghz clock. Dl
          There was a gesture detection paper based on Doppler effect hut that can only give you the speed, not position.

  4. “Each of the SubPos nodes are encoded with the GPS coordinates of where they’re placed. ”
    I don’t understand how you can take GPS coordinates in a subterranian environment. If you can, you don’t need this system.

    1. I am guessing that it uses known landmarks in caves that are referenced to above ground structures, such as well pipes, cave entrances, and then use accurate survey equipment for secondary/tertiary landmarks/monuments.

  5. I would assume that the modules needs to be calibrated or have their power measured. I wonder how good the power calibration for each of the cheapo ESP8266 modules are – i.e. over temperature variations/over time/over voltage. Voltage variation is easy – just need a stable power source.

  6. After the obligatory “why didn’t I think of this before?” moment, I realized that there are too many reflections, obstructions and signal-speed-altering media inside a building for this approach to deliver the promised centimeter accuracy.
    Maybe using a few transmitters to determine the coordinates in clear locations (entrances, along the mail mall) and using the phone’s accelerometers for inertial navigation the rest of the time… somehow avoiding the inherent accumulation of errors due to double integration.

  7. @blecky – Very well thought out project. But how about a positioning system that uses NO radio signal at all?

    The USN has been using just such a system with it’s submarines. The system keeps a breadcrumb track of where the sub is underwater all the time and uses no RF signal whatsoever EXCEPT to initialize the system at the base station (where they started from on surface). They use accelerometers to measure velocity in the direction of travel, a laser-gyroscope to track directional change (horizontal and vertical or azimuth and elevation angle), or a Hall Effect magnetic compass as geomagnetic force is ever present even underwater or in an underground cave or mall but can only track azimuth not elevation. However, gyros are much more accurate and can even extrapolate what floor you are on in a building or a underground mall based on a known topological map of said structure. The navigation algorithms are based on a navigation technique known as “dead reckoning”.

    Another innovative non-emission (RF) in-building navigation technique but could use massive databases is QR-Code labels or RF-Id tags. Technically RF-Id tags are emission based though. This idea involves mounting several large QR-Code labels at strategic locations at the mall that either have a database map lookup code or the actual positioning location spelled out in QR-code language which is read into your smartphone via a QR-Code app and your camera. The later requires NO external database to correlate code numbers to map location as it is just spelled out to you right there in QR-Code language. Like “You are at the northeast corner of the Sears store on 2nd floor next to The Asian Nail Salon. Map reference: AA112”. The map reference could bring up a pre-stored Cartesian calibrated multi-level map of the mall.

    The database method would feed the the QR-Codes serial number to a external database via Wi-Fi and likewise bring up the same map. The RF-Id tag idea would be based on the same thing but no camera would need to be pointed at the tag. However, you would need an RF-Id transceiver to interrogate the RF-Id tag. Smartphones don’t have them just yet. However, they do have cameras, accelerometers, rudimentary inclinometers, and some sort of directional compass reading method.

    As a hardware project using a Arduino: The MPU-6050 is a commonly used chip that combines a MEMS gyroscope and a MEMS accelerometer. Here is a mom (i.e. Debra) who exploited that using an Arduino Uno: http://www.geekmomprojects.com/gyroscopes-and-accelerometers-on-a-chip/

    eot

    SOTB

      1. @tekkieneet – Very insightful. That is true! Furthermore, in case of RF problems (multi-path rejection, man-made interference, etc.) the QR-Code method which spells out positional information locally could actually contain paragraphs and paragraphs of informative data about where you happen to be at that moment. Not sure what the text limit is on a QR-Code. And the intrinsic limitation of lack of images on QR-Code data, a workaround could be the image-to-text converter that converts any monochromatic image to text characters. I’ve seen some pretty good resolution text-images. A rudimentary map of sorts code be QR encoded. This method would even work in a military/government/defcont external-radio-free SCIF (Sensitive Compartmented Information Facility). I would put the QR-Code in a glass frame (up high) to prevent intentional or unintentional vandalism like coffee spills, graffiti, peer-to-peer quick notes, etc. Windex will restore the image nicely. You would not use your smartphone flash to prevent glass glare, so ambient light is required. Not a problem in a mall but problematic for a natural unexplored cave.

        1. QR Code text limits are as follows: Numbers only: 7089 numeric characters. Alphanumeric 4296. 8-Bit Binary: 2953.
          So that’s about 3Kb in data. I like the image to text routine. You can exploit image to ascii text at this web site: http://picascii.com/

          Play around with that. You can make some really incredible ASCII pictures of things. However, words are hard to read. So just don’t program words on your maps only extra large map references or may be just “You are here” label.

  8. It seems to me that a marauder’s map would be a simpler solution–presumably, no beacons are needed. However, if you see a problem with this, please don’t shatter my world view.

  9. WiFi is already useless in many places. Great idea to destroy it further by putting more transmitters.

    How bad is it? In NYC I know buildings where you can’t tether cell to a laptop few inches away due to interference from all access points in the area. Long range high power enterprise APs you say? Forget about it. That works to about 6ft. Everyone around is using them and this is the result.

    The biggest fault goes to…. cable company. Thank you TimeWarner for polluting public space with your useless WiFi network. Not only they install modems with WiFi noise generator enabled by default. They will also install powerfull Rucus APs right next to it to build their public network that is still crap, because a lot of APs are in locations where they are useless generators of noise, not something that can be used by the public.

    1. @johnnyk126 – I generally agree. However, COX Wi-Fi never ceases to amaze me. I still can’t figure out how I am able to maintain a contiguous node to node Wi-Fi connection in a Cox dedicated geographical region. And Cox is nationwide (mostly). The thing that burns me is the new reciprocal cable company agreements to allow intra-company logons from any wi-fi AP node. That defeats any semblance of anonymity. Now they know who you are without a ISP IP address search as you have to use your own home cable TV credentials. Keeps you honest I guess. That’s why I love my EDGE (GPRS) connection. I’d love to try Google’s new WiMax system but it appears to be only in special markets in USA.

      The problem with EDGE connections is that you can loose connectivity (or time-out) when the cell site is at capacity. You can usually tell that when you see everybody heads down walking and texting, video chatting, phone calls, etc. I think that is illegal in NYC. You can not walk and text (or read a book while walking) as you might walk into oncoming traffic or fall into a subway tracks or a manhole. You also can’t harassingly stare at (aka oogle-eye) pretty women either (only in New York)!.

      What we need as a new invention is what I call IR-Wi-Fi. That would be Internet-connected 360° Infra-red transceivers mounted above a payphone or lamppost pointing downward at a seating area. They’d use omnidirectional LEDs and sun-shielded photo-diodes with Fresnel lens. The users would have clusters of park benches or picnic tables with free multi-outlet electrical outlets. These would be in a circle around the IR-Wi-Fi transceivers. You’d probably need an outboard hardware device on a tripod aimed up at the AP node, The bandwidth would be enormous, Many defense contractors (and DARPA) and foreign countries are R&D’ing this idea right now. They want to use geostationary satellites. My idea would just be strategically placed kiosks around a city or mall.

      Here is a screen capture from the movie The Objective (2008) time-stamp 31:39 in where Agent Keynes is using just such a laser comm system in Afghanistan to phone home as it where: http://oi60.tinypic.com/rw6k53.jpg – film’s adviser was Nick Teta ex-USN Seal.

      Someone please invent this! (LOL)

  10. One has to wonder how anyone in the human race managed to get from point A to point B before the advent of electronic mapping/locating systems. It seems that we have almost completely forgotten how to use an inexpensive, simple, and reliable device: a paper map.

    1. @DainBramage – True point…

      I saw something at a Kohl’s department store the other day that knock my socks off! Little tiny E-Paper price label tags that are connected to wi-fi for constant price updating. It uses a LiPo battery. E-Paper to me is so spooky. Looks just like paper but can instantly change in front of your eyes. I would have loved to reverse-engineer the Kohl’s tag but I might get caught (bwah hah hah hah). I have a Kindle with E-paper – how fascinating.

      I’ve got an ancient communication system for you that was ahead of it’s time. I think it was ancient Greece before Christ (BC). One battle group would be stationed near a mountain top and needed to know which battle order to carry out next from command. The two stations would have a calibrated water jug or urn full of water. It would have a cork in the drain at the bottom. A float was positioned on top of the water. Inside the jug was coded markings that meant something to both of them. When the command station lit a fire (or smoke during day) and flashed it with a blanket (or they used a polished mirror with the sun during day, they would flash it and it meant “ATTENTION! Are you ready for your 1st command?” you’d flash back reply “Yes!”, then the next flash was “pull the cork now!. The water levels would drain out simultaneously at the same rate. Then the next flash was “put the cork back in now!. Then systematically reload water to the proper level for next message.

      The result was a pre-packaged message based on where the float positioned itself next to the pre-arranged code word. A very slow system but highly effective for moderately long range (line of sight) communication thousands of years ago. Could only work over the horizon if multiple stations were deployed. But that would be an abysmally slow message and the enemy would have already attacked, moved on, or something.

      Then there was the ancient BC Chinese strange compass that used no magnetic compass at all (created by Duke of Zhou in 1st century BC). It was a mechanical dead-reckoning system that used differential gears and such. It was a horse drawn carriage that had a man-doll always pointing south. As it traversed the countryside the gears would constantly oriented the doll pointing in the same direction for many hundreds of miles. There was some error due to pot holes and rough terrain making the wheels cause drift error. But it generally worked if you kinda’ sorta’ already knew the route and used the sun, moon, and stars to corroborate the doll’s pointing finger.

      Then there was the Viking Sun Stone (feldspar, with a red or gold color – exploiting polarized sunlight). Overcast days did not prevent them from solar navigating long past land fall. Erik the Red and Lief Erickson may have actually discovered North America long before Columbus using one.

      I guess the moral to this story: Always think externally to your paradigms. (Or always think outside the box).

      eot

      SOTB

  11. RSSI based location is quite useless because it works only at free space. When you try make something real world solution with it it just does not work because noise and blocking objects. Yes you can use it at football station to locate things but no you cannot use it at warehouse, shopping malls etc.

  12. “The best comparison to an indoor location service comes from a new Decawave module that sets up ‘base stations’ and figures out a sensor’s location based on time of flight. This, however, requires additional radios for each device receiving location data. SubPos only requires WiFi, and you don’t even need to connect to an AP to get this location data; everything is broadcast as a beacon frame, and every device with WiFi detects a SubPos node automatically”

    Decawave requires 3 base station, those 3 base stations can serve as anchors for an unlimited number of “tags”. You say “additional radios for each device receiving location data” then “SubPos only requires WiFi, “. Do you somehow believe that adding a radio transceiver operating with wifi frequency and protocol is NOT adding additional radios for each device receiving location data?

    Other than the ubiquity of wifi I fail to understand where this has any advantage, Im not downing the achievement, its a great project, I just think that at the very least the words spoken about decawave are poorly formed, IF Benchoff understands decawaves tek then his writing does a disservice to that fact,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.