Electronic – How does k-nearest neighbor apply to wireless network positioning

wireless

I'm trying to gain some insight into the variety of positioning algorithms for wireless networks. Apparently there are three categories of algorithms: distance estimation, scene analysis and proximity.

As far as I understand, distance estimation algorithms use certain metrics (e.g. signal strength or signal propagation time) from multiple sources to determine the location of the target. The proximity technique assumes that the target has the location of the receiver from which it is getting the strongest signal.

That leaves scene analysis. The document offers a brief explanation of the k-nearest neighbor algorithm but that didn't do it for me. I looked up the algorithm on Wikipedia but I don't have a clear view as to how this applies to wireless positioning.

How is k-nearest neighbor used as a wireless network positioning algorithm and what makes it different from distance estimation techniques?

Best Answer

The problem with proximity is it only takes the location information from one receiver so it is difficult to give a very precise location of the device itself. The only way to increase accuracy with sticking with this method is to add more nodes that measure the devices. The nice thing about this method is it works well in indoor environments where you have a lot of objects that can be in your way and cause difficulties estimating the location of a device using distance estimation.

The problem with distance estimation is it assumes the world is flat with no object to block signals or cause multipath, just like I talked about with the proximity method. If this truly were the case, distance estimation could be very precise with its measurements, but the world isn't this nice to us.

So along comes scene analysis. This is essentially distance estimation, but attempts to overcome the issues that pure distance estimations has. In order to do this you have to train the system what is actually happening in the real world. So you stick devices at known locations and record the results as if you were doing distance estimation. The more points that you do this for, the better you can teach a system to know precisely where a device is.

The way that these data points are used can vary based off of use, but they are pretty much always used in some sort of neural network. For your case it appears as though they are using k-nearest neighbor. Essentially what it is doing is taking the data that is received, comparing it directly with all of the known sample points you collected, and saying the location is the same as the location of a known sample data point. More advanced systems can predict location based off of actually calculating the distance between multiple sample points.

I have never actually seen k-nearest neighbor before, so this is somewhat of a guess as to how it is being applied here, but I hope I was able to provide some insight as to what the issues where with distance analysis that are attempting to be overcome with scene analysis.