Location Patterning (Pattern Recognition) Techniques

Location patterning refers to a technique that is based on the sampling and recording of radio signal behavior patterns in specific environments. Technically speaking, a location patterning solution does not require specialized hardware in either the mobile device or the receiving sensor (although at least one well-known location patterning-based RTLS requires proprietary RFID tags and software on each client device to enable "client-side" reporting of RSSI to its location positioning server). Location patterning may be implemented totally in software, which can reduce complexity and cost significantly compared to angulation or purely time-based lateration systems.

Location patterning techniques fundamentally assume the following:

•That each potential device location ideally possesses a distinctly unique RF "signature". The closer to reality this assumption is, the better the performance of the location patterning solution.

•That each floor or subsection possesses unique signal propagation characteristics. Despite all efforts at identical equipment placement, no two floors, buildings, or campuses are truly identical from the perspective of a pattern recognition RTLS solution.

Although most commercially location patterning solutions typically base such signatures on received signal strength (RSSI), pattern recognition can be extended to include ToA, AoA or TDoA-based RF signatures as well. Deployment of patterning-based positioning systems can typically be divided into two phases:

•Calibration phase

•Operation phase

During the operational phase, solutions based on location patterning rely on the ability to "match" the reported RF signature of a tracked device against the database of RF signatures amassed during the calibration phase. Because the database of recorded RF signatures is meant to be compiled during a representative period in the operation of the site, variations such as attenuation from walls and other objects can be directly accounted for during the calibration phase.

Calibration Phase

During the calibration phase, data is accumulated by performing a walk-around of the target environment with a mobile device and allowing multiple receiving sensors (access points in the case of 802.11 WLANs) to sample the signal strength of the mobile device (this refers to a "network-side" implementation of location patterning).

A graphical representation of the area to be calibrated is typically overlaid with a set of grid points or notations to guide the operator in determining precisely where sample data should be acquired. At each sample location, the array (or location vector) of RSS values associated with the calibration device is recorded into a database known as a radio map or training set. The size of the vector for this sample location is determined by the number of receiving stations that can detect the mobile device. Figure 2-6 provides a simplified illustration of this approach, showing two sample points and how their respective location vectors might be formed from detected client RSSI.

Figure 2-6 Location Patterning Calibration

Because of fading and other phenomena, the observed signal strength of a mobile device at a particular location is not static but is seen to vary over time. As a result, calibration phase software typically records many samples of signal strength for a mobile device during the actual sampling process. Depending on technique, the actual vector array element recorded may account for this variation via one or more creative approaches. A popular, simple-to-implement method is to represent the array element associated with any specific receiver as the mean signal strength of all measurements of that mobile device made by that receiver sensor for the reported sample coordinates. The location vector therefore becomes a vector array of mean signal strength elements as shown in the following equation, where x and y represent the reported coordinates of the sample and r represents the reported RSSI:

Operational Phase

In the operational phase, a group of receiving sensors provide signal strength measurements pertaining to a tracked mobile device (network-side reporting implementation) and forwards that information to a location tracking server. The location server uses a complex positioning algorithm and the radio map database to estimate the location of the mobile device. The server then reports the location estimate to the location client application requesting the positioning information.

Location patterning positioning algorithms can be classified into three basic groups:

•Deterministic algorithms attempt to find minimum statistical signal distance between a detected RSSI location vector and the location vectors of the various calibration sample points. This may or may not be equal to the minimum physical distance between the actual device physical location and the recorded location of the calibration sample. The sample point with the minimum statistical signal distance between itself and the detected location vector is generally regarded as the best raw location estimate contained in the calibration database. Examples of deterministic algorithms are those based on the computation of Euclidean, Manhattan, or Mahalanobis distances.

•Probabilistic algorithms use probability inferences to determine the likelihood of a particular location given that a particular location vector array has already been detected. The calibration database itself is considered as an a priori conditional probability distribution by the algorithm to determine the likelihood of a particular location occurrence. Examples of such approaches include those using Bayesian probability inferences.

•Other techniques go outside the boundaries of deterministic and probabilistic approaches. One such approach involves the assumption that location patterning is far too complex to be analyzed mathematically and requires the application of non-linear discriminant functions for classification (neural networks). Another technique, known as support vector modeling or SVM, is based on risk minimization and combines statistics, machine learning, and the principles of neural networks.

To gain insight into how such location patterning algorithms operate, we can examine a simple example that demonstrates the use of a deterministic algorithm, which in this case will be the Euclidean distance. As stated earlier, deterministic algorithms compute the minimum statistical signal distance, which may or may not be equal to the minimum physical distance between the actual device physical location and the recorded location of the calibration sample.

For example, assume two access points X and Y and a mobile device Z. Access point X reports mobile device Z with an RSS sample of x1. Almost simultaneously, access point Y reports mobile device Z with an RSS sample of y1. These two RSS reports can be represented as location vector of (x1,y1).Assume that during the calibration phase, a large population of location vectors of the format F(x2,y2) were populated into the location server calibration database, where F represents the actual physical coordinates of the recorded location.

The location server can calculate the Euclidean distance d between the currently reported location vector (x1,y1) and each location vector in the calibration radio map as follows:

The physical coordinates F associated with the database location vector possessing the minimum Euclidean distance from the reported location vector of the mobile device is generally regarded as being the correct estimate of the position of the mobile device.

In a similar fashion to RSS lateration solutions, real-time location systems using location patterning typically allow vendors to make good use of existing wireless infrastructure. This can often be an advantage over AoA, ToA, and TDoA approaches, depending on the particular implementation. Location patterning solutions are capable of providing very good performance in indoor environments, with a minimum of three reporting receivers required to be in range of mobile devices at all times. Increased accuracy and performance (often well in excess of 5 meters accuracy) is possible when six to ten receivers are in range of the mobile device.

Location patterning applications perform well when there are sufficient array entries per location vector to allow individual locations to be readily distinguishable by the positioning application. However, this requirement can also contribute to some less-than-desirable deployment characteristics. With location patterning, achieving high performance levels typically requires not only higher numbers of receivers (or access points for 802.11) but also much tighter spacing. In large areas where it is possible for clients to move about almost anywhere, calibration times can be quite long. For this reason, some commercial implementations of location patterning allow the user to segment the target location environment into areas where client movement is likely and those where client movement is possible but significantly less likely, as well as areas where client location is impossible (such as within the thick walls of a tunnel, for example, or suspended within the open air space of an indoor building atrium). The amount of calibration as well as computational resources allocated to these two classes of areas is adjusted by the positioning application according to the relative probability of a client being located there.

The radio maps or calibration databases used by pattern recognition positioning engines tend to be very specific to the areas used in their creation, with little opportunity for re-use. The likelihood is very low that any two areas, no matter how identical they may seem in construction and layout, will yield identical calibration data sets. Because of this, it is not possible to use the same calibration data set for multiple floors of a high-rise office building when using a location patterning solution. This is because despite their similarity, the probability that the location vectors collected at the same positions on each floor being identical is significantly low.

All other variables being equal, location patterning accuracy is typically at its zenith immediately after a calibration. At that time, the information is current and indicative of conditions within the environment. As time progresses and changes occur that affect RF propagation, accuracy can be expected to degrade in accordance with the level of environmental change. For example, in an active logistics shipping and receiving area such as a large scale cross-docking facility, accuracy degradation of 20 percent can reasonably be expected in a thirty day period. Because calibration data maps degrade over time, if a high degree of consistent accuracy is necessary, location patterning solutions require periodic re-verification and possible re-calibration. For example, it is not unreasonable to expect to re-verify calibration data accuracy quarterly and to plan for a complete re-calibration semi-annually.