We have a piece of embedded hardware that will sense 802.11 beacons, and we're using this to make a map of currently visible bssid -> signalStrength. Given this map, we would like to make a determination:
Is this likely to be a location I have been to before? If so, what is its ID?
If not, I should remember this location: generate a new ID. Now what should I store (and how should I store it) to make future determinations easier?
This is for an augmented-reality app/game. We will be using it to associate particular characters and events with "locations". The device does not have internet or cellular access, so using a geolocation service is out of consideration for the time being. (We don't really need to know where we are in reality, just be able to determine if we return there.)
It isn't crucial that it be extremely accurate, but it would be nice if it was tolerant to signal strength changes or the occasional missing beacon. It should be usable in relatively low numbers of access points (e.g. rural house with one wireless router) or many (wandering around a dense metropolis). In the case of a city, it should change location every few minutes of walking (continuously-overlapping signals make this a bit more tricky in naive code).
A reasonable number of false positives (match a location when we aren't actually there) is acceptable. The wrong character/event showing up just adds a bit of variety.
False negatives (no location match) are a bit more troublesome: this will tend to add a better-matching new location to the saved locations, masking the old one. While we will have additional logic to ensure locations that the device hasn't seen in a while will "orphan" any associated characters or events (if e.g. you move to a different country), we'd prefer not to mask and eventually orphan locations you do visit regularly.
Some technical complications:
signalStrength is returned as 1-4; presumably it's related to dB, but we are not sure exactly how; in my experiments it tends to stick to either 1 or 4, but occasionally we see numbers in between. (Tech docs on the hardware are sparse.)
The device completes a scan of one-quarter of the channel space every second; so it takes about 4-5 seconds to get a complete picture of what's around. The list isn't always complete. (We are making strides to fix this using some slight sampling period randomization, as recommended by the library docs. We're also investigating ways to increase the number of scans without killing our performance; the hardware/libs are poorly behaved when it comes to saturating the bus.)
We have only kilobytes to store our history.
We have a "working" impl now, but it is relatively naive, and flaky in the face of real-world Wi-Fi behavior. Rough pseudocode:
// recordLocation() -- only store strength 4 locations
m_savedLocations[g_nextId++] = filterForStrengthGE( m_currentAPs, 4 );
// determineLocation()
bestPoints = -inf;
foreach ( oldLoc in m_savedLocations ) {
points = 0.0;
foreach ( ap in m_currentAPs ) {
if ( oldLoc.has( ap ) ) {
switch ( ap.signalStrength ) {
case 3: points += 1.0; break;
case 4: points += 2.0; break;
}
}
}
points /= oldLoc.numAPs;
if ( points > bestPoints ) {
bestLoc = oldLoc;
bestPoints = points;
}
}
if ( bestLoc && bestPoints > 1.0 ) {
if ( bestPoints >= (2.0 - epsilon) ) {
// near-perfect match.
// update location with any new high-strength APs that have appeared
bestLoc.addAPs( filterForStrengthGE( m_currentAPs, 4 ) );
}
return bestLoc;
}
else {
return NO_MATCH;
}
We record a location currently only when we have NO_MATCH and the app determines it's time for a new event.
(The "near-perfect match" code above would appear to make it harder to match in the future... It's mostly to keep new powerful APs from being associated with other locations, but you'd think we'd need something to counter this if e.g. an AP doesn't show up in the next 10 times I match a location.)
I have a feeling that we're missing some things from set theory or graph theory that would assist in grouping/classification of this data, and perhaps providing a better "confidence level" on matches, and better robustness against missed beacons, signal strength changes, and the like. Also it would be useful to have a good method for mutating locations over time.
Any useful resources out there for this sort of thing? Simple and/or robust approaches we're missing?
