This is a project writeup of some experiments in building a WiFi-based locational positioning system around my apartment. AirTags and equivalent products do use similar principals but are not wifi-based.
Mapping the Area
Positioning starts with mapping. You need to know where you are in the space.
I have a Roborock robot vacuum that's mapped my apartment. Unfortunately, without using Valetudo, I can't actually download any rich mapping data. The only available source is the map in the app of which I can take a screen capture. Starting with that app map screenshot, a little processing in GIMP removed the no-go zones, room bounds, and small objects that created obstructions in the map. I kept many of the obstructions as they provide useful "geographical features" for larger spaces. Applying low brightness and high contrast filters creates a clean map.
→
The good thing about this map is that it is a highly accurate representation of the actual floor plan. Other tools like mobile apps that do augmented-reality mapping where you point your camera and place a point at the corner of each wall have higher error and need human correction afterwards. Furthermore, pixels on this map are directly proportional to physical distances, making it really easy to do a transformation between the map space and the physical space.
Building a Baseline
With a map on hand, it's time to build a layer on top of the map with the signal strength of the surrounding wifi networks. The signal layer is used to trilaterate the position of our device. In principal, data from a single wifi network would yield a circle of possible locations; two networks yields two points; and three networks yields a single point.
The below images shows signal data for three network. The points indicate sample locations. The gradient shows the interpolated signal strength. The first two -- red and green -- are controlled Wifi. The third -- blue -- is not. The signal strength is measured is decibels (although negated so the value is positive), meaning that a lower value is a higher signal strength.
The signal maps above were generated with the code below. Interestingly, scipy's libraries for interpolations only interpolate in the interior space between points. It doesn't extrapolate data outside the outer hull.
import numpy as np
import scipy as sp
import pandas as pd
import matplotlib.pyplot as plt
import imageio
map_positions = {
"green_origin": (174, 78),
"red_origin": (18, 175), # also bottom_left
"bottom_right_bottom": (142, 177),
"bottom_right_right": (183, 123),
"upper_left": (18, 11),
"upper_right": (183, 11),
}
house_map_img = imageio.imread('map.png')
house_map = np.asarray(house_map_img)
data = pd.read_csv("data.csv")
# data is read from a CSV with 3 columns: {SSID, Location, Strength}
def show_for_ssid(filter_ssid):
values_raw = sorted(
[
tuple(r) for r in
data[data["SSID"]==filter_ssid]
.filter(items=["Location", "Strength"])
.to_numpy()
],
key=lambda x: map_positions[x[0]]
)
points = list(map(lambda x: map_positions[x[0]], values_raw))
values = list(map(lambda x: x[1], values_raw))
interp = sp.interpolate.CloughTocher2DInterpolator(
points,
values,
fill_value=0
)
X_orig = np.linspace(0, house_map.shape[0], house_map.shape[0])
Y_orig = np.linspace(0, house_map.shape[1], house_map.shape[1])
X, Y = np.meshgrid(X_orig, Y_orig)
Z = interp(X, Y)
plt.matshow(Z, cmap=cm)
plt.plot(*list(zip(*points)), "ok")
plt.colorbar(shrink=0.8)
plt.show()
return X, Y, Z
X, Y, Z1 = show_for_ssid("RED", plt.cm.Reds)
_, _, Z2 = show_for_ssid("GREEN", plt.cm.Greens)
_, _, Z3 = show_for_ssid("BLUE", plt.cm.Blues)
Preparing for Trilateration
With the data collected, the question becomes: can this data be to trilaterate location? Unfortunately, the answer is "Yes, but...".
The obvious way to calculate location is to treat signal strength as a proxy for distance. Then use the three "distances" to construct the "three circles" and find the single intersecting point (or with the least amount of error if there is no single shared point between all three).
This doesn't work here because signal strength is actually non-linear. It can't be used 'in-place' of distance, and would need to be converted to actual distance. That isn't so difficult since there is enough data to build a gradient.
The other (big) problem with this method is that not all the wifi base station locations are known a priori. The data collected comes from two controlled base stations (red, green) and one uncontrolled base station (blue).
An alternative that doesn't require either a linear distance function (although it would benefit from it) or base station locations known a priori is to find the position that most closely matches the interpolated gradient of the signals with.
Before implementing this, it's important to verify that there is enough "signal" in the signal to clearly distinguish pixels. There are a lot of ways to calculate this like with a statistical pixel comparison or calculating the gradient's derivative to find flat or unchanging spots. The former probably has the benefit of being a global measure of similarity and the latter, a local one.
I opted to do neither -- instead doing, for simplicity, a manual human verification of a visualization. The three gradients are used as the individual RGB layers of an image. Any "flat" spots in the signal gradient with lots of similarity without change (which corresponds to the derivative) are likely very similar. The below image shows the RGB combination of the three signal layers above.
The gradient hotspots seems to be focused around the points, but that may not be a bad thing as points selected for data capture were chosen (not very scientifically) because they would be unique samples. This is acceptable for a basic test run. Although in a future iteration of this project, it might be interesting to do some outlier detection to test the integrity of the data.
Trilateration
With the signal gradient covering the entire space and confirmation that we have enough uniqueness across the space to identify specific points, we can trilaterate by running a simple "classification" task that finds the point closest in signal to a sample signal.
def trilateralate(sample_data):
def norm_data(Z):
return (Z - 20) / (100 - 20)
map_shape = Z3.shape
Z = np.stack((Z1, Z2, Z3), axis=2)
point_matrix = np.repeat([[point_data]], map_shape[0], axis=0)
point_matrix = np.repeat(point_matrix, map_shape[1], axis=1)
diff = np.absolute(norm_data(Z) - norm_data(point_matrix))
diff_sum = np.sum(diff, axis=2)
diff_min_point = np.where(diff_sum == np.min(diff_sum))
return diff_min_point
Results
The images below show the results for several samples. The red dot represents the ground truth and the black dot represents the trilaterated result. The left image is the placement on the same RGB heatmap seen above. The right image is the diff between the RGB heatmap and the current point, from which the minimum point is found.
There is a high error, but the general region that the signal trilaterates to is correct. The appropriate room could be identified and even the right general area of the room, but there could be no meaningful precision with the high error rate.
Conclusion
I'll consider this phase of the project done. Trilateraion works. Although, there are many areas to improve. A few I have in mind:
- More data to build a better gradient. And more efficient ways to passively collect the ground-truth signal data.
- Multi-device experiments. I have no idea how well this carries over to other devices (beyond the two controlled signal sources and my phone).
- More than 3 signals used in "regression" and "classification" pieces. I'd expect better precision, but the strength of other signals would be lower so that may not be the case.
- Collecting many samples for a good statistics of signal error and trilateration error. It could also inform the quality of the gradient and improve the precision.
- Easier data collection -- there's no app that provide direct-to-json formats for labeling. I'd need to DIY an android application for this.