Technical Disclosure
You can read the related story here - RSOC Post
Title: A classification approach exploiting the rectangular topology of a floor-plan to determine the location of a mobile user inside premises using only 2 access points.
Detail: This disclosure contains two related ideas. One is the concept that tries to reduce the problem complexity by exploiting the underlying problem domain and the other provides an associated implementation with a classification approach using ANN (Artificial Neural-Networks).
The known solutions to these problems make use of a minimum 3 access-points to determine the location using triangulation. These solutions exploit the fact that the Signal strengths from an access point vary radially, i.e., the signal strength along an imaginary circle of radius ‘r’ from the location of the access point (assumed as the focus or center) is constant, say SS(r1), and decreases as we go radially away from the focus. So, if three such access points (APs) are placed randomly, then since 3 different circles can uniquely determine a point in 2-d space, we can locate a test-user based on his relative signal strengths w.r.t those 3 APs. [Refer Fig. 1]
Figure 1. Case when APs are randomly placed (Triangulation).
We try to take advantage of the fact that majority of physical structures, like buildings, organizations, etc, are rectangular in shape (top-view). Now, it is a fact that there is a near complete loss of signal strength when there is an obstruction thicker than 3cm, which is minimum wall thickness in almost all concrete buildings into which such a system may be installed. In theory, the signal strengths from an access point always vary radially and are constant along the circumference of signal strength circles. So, if we place the access-point on a corner, those circles reduce to quadrants (1/4th of a circle), because the other 3/4 of the circle is cut-off by the test-area walls.
Thus, by placing two access points at two of the adjacent corners in such rectangular structures, the “signal-strength circles” can be reduced to “Signal-Strength Quadrants” as shown in the figure. And thus, we can locate the test-user at the intersection of those two quadrants because any point in the 2d-plane of the building or test-lab can be represented by the set of Signal Strengths from the two Access Points. [Refer Fig. 2]
Figure 2. Case when APs are places at the adjacent corners of a rectangular test area.
The figure above shows the access point placement at the two ‘adjacent’ corners. Now, this figure is meant to portray that, theoretically, in a rectangular test-area, there is a possible arrangement of 2 access points, which would yield a unique intersection of signal strengths and this can serve as a possible premise for any further implementation.
Now, this premise serves as a foundation to prove that an implementation based on this can lead to decent results since, theoretically, we can see that unique points exist for any signal strength pair (SS1, SS2).
In most existing work on the problem of location determination with ‘n’ APs, such a foundation is existent for n >=3, since triangulation comes into picture in those cases. But, that foundation isn’t obvious when n = 2 when triangulation won’t apply. Most papers describe training their algorithms for different access points (varying from 2 onwards), which is bound to give some results. But, in most cases those results aren’t considerable when we talk of 2 access points, case of a single access points being highly improbable to yield even remotely precise results.
Implementation: Let us assume that the floor plan of a test building installed with two APs is as shown in Fig. 2. The methodology for determining the location of any Wi-Fi enabled device inside the test premises can then be covered in following phases: -
Phase 1: A set of ‘n’ locations (brown dots) is selected in the building and training data is collected at each of those n points. For each point, a value tuple of the form [SS1, SS2, x, y, Location No], is inserted in the training database, where, SS1 = Signal Strength from AP1, SS2 is signal strength from AP2 & x, y is the abscissa and ordinate respectively considering rectangular coordinate system with reference at the left-bottom of the figure. Here, we may try and filter out null or negative signal strength values. So, we have a database that can later be queried to get the signal strength from each access point at each training position. This process is called data-collection phase and is fairly common in any of the ANN techniques. This data is later used to train the Neural-model as explained below.
Phase 2: In this phase, we try to build a mathematical model for the test area using neural networks. Consider an equation of the form below: -
C = W0 * S1 + W1 * S2 + W2, —————————- (I), where C is the Class, W0, W1, W2 are the constant weights (initially they are unknown) and S1, S2 are the variable signal strengths from the two access points. Here [W0, W1, W2] is called the weight matrix and F [S1, S2] is a representation for a function of S1 and S2.
The above equation is a starting assumption that we make in any neural-modeling approach. Now, from phase 1 above, we would have ‘n’ cases (1 for each test-location), where we know the Signal strengths (S1, S2) as well as the class (since we know the location of those 12 training points). So, using these 12 cases, we can try to obtain the value of the Weight matrix in Equation (I). This process is called training of a neural model and this may be thought of as being equivalent to solving 12 simultaneous equations to arrive at the values of 3 variables W0, W1 and W2.
After this training phase, we would get some values of [W0, W1, W2] which would satisfy all the ‘n’ points, i.e., given any signal strength pair (S1, S2), it would locate it properly in the correct class. Then we reason from the fact that since our model is trained enough to classify points in the lab in question, so given a signal strength value pair from any other point as well (different from those ‘n’ training points), it would still locate it correctly in the appropriate class. This approach essentially tries to find and exploit any pattern that is present in the signal strength distribution for this particular test-lab.
Now, we divide the floor plan into topological regular classes (rectangular, hexagonal, etc). Let me explain these models a bit in detail. Consider Fig. 3.
Figure 3. Basic classification model
As shown, let us assume that our first model (M1) is such that it classifies the test-floor into three classes (Class1, Class2 and Class3). Now, let us consider a test-point P. For this point, we would compute the signal strength tuple (SS1, SS2). Now, substituting these in the corresponding equation (like the one described in (I) above) for this model (M1), we will get a value for the Class, ‘C’. For this point, lets assume the class comes out as Class1 as shown in the figure. So, this way the floor-area in classes - Class2 and Class3 is eliminated and we can now focus on area under Class1.
Now, let us consider a second model (M2) being superimposed over M1, which is as shown in fig. 4.
Figure 4. Superimposed classification models
This model classifies the test-floor in a different way as shown by the class-names in red. So, by feeding the signal strength value pair for the test-point P, we would get the class as Class 3. So, our investigations can further reduce to the intersection of Class 3 of model 2 and Class 1 of model 1, i.e., essentially the shaded region. Going on applying 2-3 more models, we can pin point the location of the test-point (P) to a very narrow corridor within an acceptable error-margin.
So, the idea is to have these models, i.e., these equations (of form (I)) prepared in phase 2 and then just use the appropriate or all models for a test-point to narrow down its location. This overall approach was found to locate a test-user within a 3-meter error-margin in the average case with only 2 access points placed as indicated in Fig. 2.
You can view this on ip.com @ IPCOM000168722
Recent Comments