Hackaday Prize Entry : Subterranean Positioning System

There are numerous instances where we need to know our location, but cannot do so due to GPS / GSM signals being unavailable and/or unreachable on our Smart Phones. [Blecky] is working on SubPos to solve this problem. It’s a WiFi-based positioning system that can be used where GPS can’t.

SubPos does not need expensive licensing, specialized hardware, laborious area profiling or reliance on data connectivity (connection to database/cellphone coverage). It works independently of, or alongside, GPS/Wi-Fi Positioning Systems (WPS)/Indoor Positioning Systems (IPS) as an additional positioning data source by exploiting hardware commonly available.

As long as SubPos nodes are populated, all a user wishing to determine their location underground or indoors needs to do is use a Wi-Fi receiver.  This can be useful in places such as metro lines, shopping malls, car parks, art galleries or conference centers – essentially anyplace GPS doesn’t penetrate. SubPos defines an accurate method for subterranean positioning in different environments by exploiting all the capabilities of Wi-Fi. SubPos Nodes or existing Wi-Fi access points are used to transmit encoded information in a standard Wi-Fi beacon frame which is then used for position triangulation.

The SubPos Nodes operate much like GPS satellites, except that instead of using precise timing to calculate distance between a transmitter and receiver, SubPos uses coded transmitter information as well as the client’s received signal strength. Watch a demo video after the break.

The 2015 Hackaday Prize is sponsored by:

48 thoughts on “Hackaday Prize Entry : Subterranean Positioning System

    1. The overall idea isn’t new, what is new is the transmission of “encoded information in a standard Wi-Fi beacon frame”. This is very similar to BLE beacon based location. I suspect trilateration (concentric circles) using WiFi RSSI is what is happening instead what the article suggests is triangulation (angle of arrival).

  1. Hasn’t indoor positioning with just radio signal strength proven inaccurate already because the obstacles and the orientation of antenna causes so much inteference and variation? And how does wifi signal penetrate rock?

    Sure this works in your living room without obstacles and in perfect installation ..

    1. Wrong! Obstacles are no issues. You can get rid of them using algorithms (in case of the obstacles which is one of the simplest issues to solve it’s just an exponential curve) to cleans the data. I do this every day, RTLS is my job and it works perfectly! I’m really glad that this guy is making it open source because I have never seen an open source one before! Penetrate Rock?! Why would you want to do that? This is for indoor positioning , no rocks!

      1. Maybe rocks as in the walls/floors of the building (not a cave!), but then I thought that you can have a set of transmitters per room, than per building.

      2. Mathematically you are correct, but the problem is that 99.9% of WiFi radios do not have precise or accurate enough signal strength information to do this.

        I would love to be proven wrong, but I would also love to see someone go make a better WiFi radio. Im definitely following this project for results.

        1. Yep you are right, most Wi-Fi receivers only give up to 1 decimal place of precision (if you are lucky), and they do provide a lot of variation. There are a few other techniques that the project is looking into to help overcome this, but currently the positioning gives you at least a few meters of accuracy, which for many applications is pretty decent (I’ll have another demo video up showing movement with motion estimation in the next 2-3 weeks).

          The point of the project is to first define basic positioning capabilities without database modelling/connectivity and it can be built on from there (you mention in another comment high precision SDR). Basically though, the system as it stands isn’t any worse than current Wi-Fi positioning techniques (and it’s arguably better as it’s easier to set up).

      3. Mahtool, which frequencies are you working with?

        Generally, I think we both agree that for microwaves in the 2.4 or 5 GHz bands, the typical indoor channel is dominated by multipath, so it’s typically Rayleigh (non-line of sight) or Rician (with a Line of Sight that dominates RX power). You usually can’t tell a priori which of both applies. Also, for places where you’d need mass navigation, fluctuation of the environment is an essential quality of your channel – which means you get fading.

        For WiFi you’d get symbol durations of microseconds, and frame durations of milliseconds — which means that your channel has fast fading relative to your possible equalization periods, which makes estimating RX strength hard! Now, luckily there’s very mature equalizers for OFDM as used in 802.11g and n, but these basically hide the signal strength variations from your receiver (which is the reason you hardly get a useful signal quality estimate from post-equalizer RX power alone).

        To estimate based on average pre-equalizer power, you’d have to be in a low-interference environment — which is absolutely the opposite of the ISM bands used here, hence my question about your frequencies.

    2. I think so, yes. I’ve yet to come to a solution for indoor positoning without a overlooking camera or a nifty setup for symbols that help the moving unit by positioning itself by triangulation of visual recognition of these symbols.

    1. Most Wi-Fi positioning systems have the same problem, but averaging functions help with this immensely (you generally move about while using a positioning system). You will see this in the Android API I will release shortly.

      The main benefit of SubPos however is that it is completely offline so you don’t need to connect to a database and send your positioning information to say Google or Apple.

    2. Biasing values based on your orientation, and position of transmitters in the room? If the application thinks the signal is low from a specific transmitter because it is behind you (and your phone is in-front of you), it can to a “+/-” thing on the values.

  2. I would really love to see them make this work, but I have tried this (as well as many others) and we have all found indoor tracking via WiFi or other 2.4 GHz signals to be extremely difficult with standard hardware. Basically, the RSSI info most WiFi receivers provides is not precise enough to overcome background noise, echos, reflections and obstructions.

    That being said, a custom WiFi radio or high-end SDR operating as a WiFi radio might offer some hope.

    My fingers are crossed for these guys to pull through.

  3. A bit off-topic but still about positioning so here goes: I want to detect the rfid implant chip in my cat. The chip is in the neck area I think. Any suggestions on an inexpensive shield/device that works with Raspi that can do that? Best case scenario something I can place in a box under a feed bowl. I’ve googled up a few rfid cat door tutorials but precise suggestions on shields/devices would help a lot.

    1. I am currently playing with beacon frame transmit timing and I am using a reasonably cheap TCXO with stability of about 2.5ppm to generate an accurate “clock” (basically the beacons will transmit at around every 100ms). The problem I am having is mostly with the Android SDK for the receiver, but I am still digging through it to see what I can get from that.

    1. It’s faster than traditional Wi-Fi positioning systems that rely on a database and accuracy is about the same at the moment. I’ll be adding some custom trickery into the firmware of the nodes to help with accuracy.

          1. You will get granular position data (through current testing it’s about 2 meters of error). I have a few techniques I am going to implement shortly to make this better, but you might have to wait a month or so to hear the results of that.

  4. The submitter is onto something.
    There are various companies out there that sell such system for hard rock underground mines. (Becker/Varis, Harline Solutions, etc…)
    Comments are right that rock blocks the AP signals and the nodes are usually battery powered, low signal strength and you just form a breadcrumb trail down the various drifts. Tie in to fibre at ramps and shafts and it’s pretty reliable.
    At worst if you don’t want to litter the entire mine with nodes you can hit key areas and at least know in which areas equipment/people were last known to be. A huge safety gain!

  5. Neat stuff. This reminds me of some R&D that I did several years ago for a former employer in the US.

    After the Upper Big Branch Mine Explosion, Congress pushed through the MINER II Act and suddenly they needed the ability to locate each of their underground employees (miners) to an accuracy of ~10 feet.

    Our first design used Wi-Fi routers running OpenWRT in explosion-proof boxes deployed throughout the test mine. The miners and pieces of equipment were all equipped with “beacon” devices (hermetically-sealed ARM Wi-Fi devices) that would periodically listen to the available APs, join the nearest/strongest and transmit basic telemetry (MAC address, battery voltage, etc).

    The listening function on the APs was basically promiscuous mode, so all nodes reported the MACs of any heard beacon device and the RSSI value. A program running on the reporting machine, required for compliance, would then show and log a triangulated position for the people in the Safety Department.

    Considering our budget, the beacons were pretty neat. We added a relay function where each beacon would relay (as part of the telemetry payload) the MACs and RSSI values for up to 64 others that it heard, just in case they weren’t being heard, periodically or on command for more frequent updates. We added an ACK check where they could up their transmit power if they hadn’t been able to associate with an AP or relay their telemetry through another after a given interval after LoS. We added an accelerometer to potentially detect falls/other injuries and a page function that would beep, vibrate and flash an array of LEDs when there was emergency or call-out. We were working on adding emergency buttons and coarse noise exposure detection when we stopped.

    We switched away from the in-house designed and constructed Wi-Fi beacons once the federal authorization to run the experimental devices in a potentially explosive environment expired. The problem wasn’t with the beacons themselves, as they were designed to be intrinsically safe (even used inductive charging). The problem was with the certification, or the impressive cost of certification.

    We quickly realized that it would be far more expensive to have our own devices federally certified (yes, that’s a thing with the Mine Safety and Health Administration), so we kept the basic architecture, but switched to UHF active RFID tags and different receivers which had already been certified, although they lacked the nicer functions like relay, remote command and noise monitoring. If you ever see cable or device with an MSHA number on it and wonder why it may cost more than a similar equivalent part without, the certification is probably to blame.

    I was rather proud of what we were doing. The men were potentially safer in the case of an incident and the tech was neat. We used a redundant dual ring SM fiber setup (two different cable routes around the mine with different entry/egress points, just as it should be) and media converters- I know, but you try finding a router with miniSFP and OpenWRT support. Primary links were carried in ridiculously expensive, reinforced aramid cables, but later changed to redundant armored copper links for the connections between nearby units. A backup wireless mesh failover option was also developed. It all worked great and then we switched to almost off-the-shelf UHF tags. Oh well.

    The thing I’m most sad about is that the company has since gone out of business and they wouldn’t let me open-source any of it. :(

    1. Data centers would be a tricky one due to all of the all metal racks around and reflection effects. But if your ceiling was high enough and you had enough lower powered nodes (1 every few meters) littered about, you should get some pretty reasonable results.

  6. This is a topic researched by many … simple in principal, but the simple RSSI way will not give you accurate info.
    Bluetooth 4 is supposed to be able to do angle detection by using 2 antennas. This coupled with Bluetooth beacons should be a bit better than Wifi.
    I thought about using esp’s for this as well, but when I checked the RSSI on my phone from one node, even with everything around it fixed, it was giving values continuously changing in a rather large range.

    1. Yep you are correct, but if you use averaging functions you can smooth this out quite nicely, the application in the video is averaging out these values to get a pretty accurate position. Additionally, Bluetooth unfortunately cannot give you the range Wi-Fi does, and one of the goals of this project was to be able to augment/modify exiting infrastructure as well.

      1. Since we are talking about “littering” with devices and modifying infrastructure bluetooth beacons could work if you place a lot of them everywhere…and have the advantage of being able to be battery powered for a while.

        Of course, the two are not mutually exclusive and would work better together.
        Now the question is, how do you easily program the location in the nodes when you “sprinkle” them if they are already inside with no access to GPS?

        1. There are two modes of operation, one is GPS decimal coords and the other is offset mapping in cm (from a zero point). You can use the offset mapping in your application to translate back to GPS coords if you want, or you can translate these coords before programming, ideally you would just use the offset coordinates directly (it depends on your application; say a map overlay with the 0,0 pixel being 0,0cm).

          To answer your question, the easy way to do this depending on the environment, is to walk around with a measuring wheel and a compass and program the offset value or coords as you go. Ideally you would just mark the locations first, go back and program them and then install them. Alternatively if you have maps of your building or structure you want to install them in, you just calculate the positions from that and program them and place them about.

          Old school, but effective :)

          1. just thinking about positioning in the building…if you could receive the signal on the outside, you could do reverse: knowing the gps position and moving around + signal from modules you can find the position of the modules.
            This is how google does it, by correlating with gps, when available.

        2. Oh you can use Bluetooth beacons too, but it’s harder to use the same method as SubPos (storing position in the device and passively monitoring it) to perform position trilateration. You would need a database to achieve this or connect to the Bluetooth devices to transfer information.

  7. I wonder if it’s gonna work on par with systems like Estimote. Their nodes (or in their parlance – beacons) are a little bit expensive to deploy en masse ($100 for a devkit of 3 pcs). And we know that almost always the cheaper wins if it’s good enough. I hope for the Chinese to come up with something affordable and “good enough”.

    I wonder if one could piggyback to lighting fixtures for power… or maybe use a solar cell there? That’s even more appealing. Anyway, consider this prior art, patent trolls ;-P

    1. The current bill of materials comes to about $8 AUD not including PCB (single component pricing). I am hoping to keep this under $15 AUD a node. You can just use an ESP8266 module by itself if you like though if you want really cheap. I am adding some extra magic to the nodes to make them easier to configure and to help with better accuracy though which should be worth the extra few dollars.

  8. How about doing a hybrid of the mine experiment and the way the cellular network does its location finding.
    I would put most of the “smarts” into the access point where it would use phased antennas to calculate direction and RSSI to calculate distance. That information would be sent back to a central processor that would translate it into a pseudo Lat and Long that would be sent back to the device to display on a map. Look at companies like Microtik, Ubiquity and others that are using bits of the technology to develop automatic hand offs for seamless wifi roaming.

  9. Back in the mid 70’s, a group of cavers did some experiments and found that frequencies in the AM broadcast band propagated well enough through the earth and into limestone caves to be useful for both voice communications and crude locating. The equipment was homebrew and fit into a small ammo can.

    I don’t remember where these guys were from at the moment. They came to a meeting of the Baltimore Grotto and gave a presentation on their experiments and equipment.

    The propagation of those frequencies through the earth isn’t surprising, as ELF (even lower) is still in use by the military for communicating with submerged submarines.

Leave a Reply

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