Introduction

Context-aware computing is an emerging computing paradigm that exploits information about the user context to provide improved services. There are many applications that provide context-aware services based on the location of the user, such as telephone follow me, which forwards phone calls to the user's current location, everywhere printing, which chooses the nearest printer for mobile users, and intelligent tourist, which offers help information based on a tourist's location.

Many positioning systems designed to determine or track a user's location have been proposed over the years. Those systems fall into three categories: global location systems, wide-area location systems based on cellular networks, and indoor location systems.

A typical global location system is the Global Positioning System (GPS) [1], which receives signals from multiple satellites and employs a triangulation process to determine physical locations with an accuracy of approximately 10 m. However, GPS is inefficient for indoor use or in urban areas where high buildings shield the satellite signals.

Several cellular-network-based wide-area location systems have been proposed in recent years [2]. The technological methods of location determination involve measuring the signal strength, the angle of signal arrival, and/or the time difference of signal arrival. However, the accuracy of wide-area location systems is highly limited by the cell size. Moreover, the effectiveness of systems for an indoor environment is also limited by the multiple reflections suffered by the radio frequency (RF) signal.

For an indoor environment, several systems based on various technologies such as infrared (IR) [3], ultrasound [4], video surveillance [5], and radio signal [6, 7] are emerging. Among these systems, radio-signal-based approaches—more specifically, the wireless local-area network (WLAN) (IEEE 802.11b, also named Wi-Fi) radio-signal-based positioning system—have drawn great attention in recent years [8, 9]. A WLAN-based positioning system has distinct advantages over all other systems. First, it is an economical solution because the WLAN network usually exists already as part of the communications infrastructure. For a notebook computer, personal digital assistant (PDA), or other mobile devices equipped with WLAN capability, the positioning system can be implemented simply in software—generally in middleware or at the application level. This software-based location system significantly reduces cost with respect to dedicated architectures. Second, the WLAN-based positioning system covers a large area compared with other types of indoor positioning systems. The WLAN-based positioning system may work in a large building or even across many buildings. Third, it is a stable system owing to its robust RF signal propagation. Video- or IR-based location systems are subject to restrictions, such as line-of-sight limitations or poor performance with fluorescent lighting or in direct sunlight.

In this innovative WLAN-based indoor positioning technology, the signal distribution of access points is collected to train a position-determination model. The training phase is followed by the working phase, during which the mobile device observes the WLAN signals and applies the position-determination model to calculate a position. To reduce the complexity of the training phase, a model-based signal propagation training scheme is proposed in which the signal distribution is trained from a few collected samples. To improve the accuracy of the location system, a tracking-assistant positioning algorithm is introduced in which the position determination relies on both collected signal strength and knowledge of space topology.

We have set up the WLAN-based positioning system in the IBM China Research Laboratory and have used experiments to evaluate the performance of our system. The results of these experiments indicate that our system achieves a 2-m accuracy with a 90% probability for static position determination. For a walking mobile device, a 5-m accuracy with a 90% probability is achieved.

WLAN signal propagation analysis

Generally, the WLAN-based positioning system relies on the collecting of WLAN signals to train the signal-distribution map, thus applying a position-determination model that can be used to determine the location of mobile devices. The WLAN signals appear in an irregular pattern, since the propagation of signals is heavily affected by multipath effects, dead spots, noise, and interference in an indoor environment. Therefore, creating an efficient and accurate positioning system for indoor environments is a challenging task. In this section, we discuss the setting up of a test bed to measure and analyze the characteristics of WLAN wave signal propagation in indoor environments, providing the basis for the location algorithm we propose in the next section.

The layout of the test bed for WLAN signal analysis is shown in Figure 1(a). The test bed has a dimension of 35 × 40 meters, an area covering 1400 m². It includes a hall, a reception area, a classroom, and several smaller rooms. Five WLAN access points (APs), AP_1,2,···,5, are mounted on the roof of the area, as shown in Figure 1(a). The access points are of the Cisco Aironet** 340/350 type, and each one is equipped with two antennas with 2.2-dBi gain. They operate in the 2.4-GHz band. For a typical indoor environment, the cover range of an access point is about 90 m at 1 Mb/s and 30 m at 11 Mb/s.

To study the WLAN signal propagation, we use an IBM ThinkPad* T20 notebook equipped with a Cisco Aironet 340 series WLAN adapter to capture the signal. We wrote an application to scan access points and collect the received signal strength indication (RSSI) from each access point. The collected signal strength is reported in units of negative decibel-meters (-dBm).

In the testing area, nearly 100 positions are chosen to perform scanning operations. For each position, 300 scanning operations are performed for each orientation. Moreover, we also vary the scan interval and scanning number for some special positions to obtain long-term characteristics of signal propagation. The analysis of the collected samples is reported in Figure 1(b).

Figure 1

Figure 1(b) plots the contour of signal strength from access point AP₁ in the testing area. As shown in Figure 1(a), AP₁ is mounted on the roof above the reception area, where the signal is very strong. It is seen that signal strength at the position below AP₁ may approach 30 to
35 -dBm. As the distance between the measuring position and AP₁ increases, the signal is attenuated. However, the signal is attenuated at different rates in different directions. For example, the signal is gradually attenuated on the line-of-sight from AP₁ to the demo room, at the lower right of Figure 1(b). On the other hand, the meeting room, at the upper left of Figure 1(b), is only 6 m away from AP₁, but the signal strength is greatly attenuated because there are two walls absorbing the signal wave. Generally, the signal propagation in an indoor environment is subject to the reflections, diffraction, and scattering of the radio waves caused by the structures within the building. The transmitted signal reaches the receiver via multiple paths, causing fluctuations in the received signal envelope and phase. Hence, the received signal exhibits a distorted version. Moreover, the complex environment causes severe multipath effects, dead spots, noise, and interference. It is thus not feasible to build a simple or a formed signal propagation model for an indoor environment.

We choose a certain position, Point 1, as indicated in Figure 1(a), to study the signal distribution from multiple access points. For each access point, we collect 300 samples with a 2-second interval. Figure 2 shows the signal strength distribution of AP₁ and AP₂. As shown, the gathered signal from different access points exhibits different characteristics. Since Point 1 is very near AP₁, the signal strength from AP₁ is rather high, and the average signal strength approaches 54.6 -dBm. Of all 300 samples from AP₁, 32% fall within the range of 55 to 60 -dBm, and 90% of the samples fall within the range of 45 to 65 -dBm. However, there are still some weaker samples, and the weakest is only 72 -dBm. Since many factors affect signal propagation (number of people in environment, doors opening and closing, and so on), there are some cases in which the signal can be greatly attenuated even when the measuring position is quite near the access point. The weaker samples reflect this phenomenon. However, most of the samples exhibit similar strength, and the analysis indicates that the standard deviation of signal strength at one position is about 3 to 10 -dBm.

Figure 2

We also studied the effects of measuring device orientation on the signal strength. At Point 2, as marked in Figure 1(a), we collected samples in four orientations. The results, reported in Figure 3, indicate that there is a correlation between orientation and measured signal strength. The notebook and measuring person have a remarkable effect on the signal propagation. Typically, there was a variation of about 5 to 10 -dBm among the different orientations. This motivated us to treat different orientations of one location as different logical positions in a positioning system.

Figure 3

To study the long-term characteristics of signal propagation, we performed multiple sample collections during a two-week period under different conditions. The conditions included different times of day, such as morning/noon/night and office hours/nonoffice hours. Then we used all of the samples to study the statistical characteristics of long-term signal propagation. Figure 4 shows the probability distribution of signal strength from AP₁ at Point 1, which includes 3000 samples. As shown in Figure 4, the long-term characteristics of signal propagation are very similar to the short-term characteristics shown in Figure 2, except that there is a heavy “tail” in the long-term figure. Since more samples are collected in the long-term analysis, a greater number of weaker samples are detected in the collection procedure, which results in the heavy tail.

Figure 4

WLAN-based positioning system

In WLAN-based positioning systems, the mobile device generally makes use of the signal emitted from access points as the input for a positioning algorithm to determine a location. In this section, we present a position-determination model to reflect the correlation between the observed signal and position knowledge.

Let the set L = {l₁, l₂, ..., l_n} denote the preselected positions (also called marking positions) in a certain area, and set A = {a₁, a₂, ..., a_m} denote the access points in the area. For each marking position, l_i, the signal strength s (0  s  100) as detected from a_j follows a probability distribution p_i^j(s), where

For an unknown location x, suppose that the observed signal is O = {o₁, o₂, ..., o_m}, where o_j represents the signal strength detected from access point a_j. We then assign a probability
P(l_i | O) for each position l_i under observation O. Therefore, the position-determination problem is to find a position, l_i, at which the probability P(l_i | O) is maximized.

Mathematically, the probability P(l_i | O) can be represented as

	(1)

where P(O | l_i) is the conditional probability of obtaining observation O at position l_i; P(O) is a normalizing constant; and P(l_i) is the prior probability of position l_i being the correct position, which can be set as a constant or obtained from some prior knowledge.

Generally, the conditional probability P(O | l_i), which represents the O being observed at position l_i, can be represented as

	(2)

From Equations (1) and (2), it is clear that the probability distribution p_i^j(s) and the prior probability P(l_i) dominate the position calculation and are critical to the accuracy of the location system. Our WLAN-based location system is built on the basis of this position-determination model. Since the model relies on preobtained knowledge, such as p_i^j(s) and P(l_i), the system works in two phases: the training phase and the working phase.

In the training phase, a suite of samples is collected to create the marking position set L. Generally, the marking positions should be carefully selected so that they are evenly distributed over the whole area. Moreover, as mentioned above in the section on signal propagation analysis, the orientation also has an effect on signal strength. Thus, the four orientations of each physical position are considered as four marking positions in the set L. For each marking position, signal scanning operations are performed to collect a number of signal observations. The collected signals are used to build the signal probability distribution p_i^j(s). As mentioned above, p_i^j(s) exhibits a remarkable impact on the accuracy of the positioning system, so training the probability distribution from collected signals should be done very carefully. In general, to train a well-shaped probability distribution requires a large number of signals, resulting in a heavy burden for signal collection. To achieve a tradeoff between training output and training burden, we propose a model-based training scheme, discussed in the next subsection.

In the working phase, the mobile device detects a signal from each access point and uses the position-determination model to calculate a position in real time. However, because of the variable nature of signal propagation in indoor environments, it is hard to eliminate the position-determination error if only the signal-distribution probability is used in the determination procedure. To improve the accuracy of the positioning system, we introduce the knowledge of area topology in our model and propose a tracking-assistant positioning algorithm, discussed in a later section.

Our WLAN-based positioning system relies on the knowledge obtained in the training phase. A good training procedure should possess two features: an accurate signal probability distribution obtained through the training and a training procedure that is not too complex. These two objectives, however, are often in conflict. To obtain an accurate signal probability distribution requires a large number of samples, resulting in a heavy burden on the training procedure. To trade off these two objectives, we propose a model-based signal-distribution training scheme.

Recall the two signal distributions obtained from the short-term and long-term analyses,
Figure 2(a) and Figure 4, respectively. We find that the two distributions have some similar characteristics, such as average value. This indicates that some important distribution characteristics can be obtained in the short-term signal-collection procedure. However, it can also be seen that the shape of the long-term distribution is smoother than that of the short-term distribution. Moreover, the long-term distribution has a heavy tail because more weak samples are detected during the long-term data collection. Motivated by these analyses, we propose a model-based signal-distribution training scheme. The scheme is composed of three steps:

• Step 1: At each position K, scanning operations are performed to collect the signal from each detectable access point. Suppose that at position l_i, the K scanned observations are O_k(k = 1, 2, ..., K), where O_k = {o₁^k, o₂^k, ..., o_j^k, ..., o_M^k}, and o_j^k represents the signal strength of the access point a_j in the kth scanning operation. Generally, this is a short-term signal-collection procedure.
• Step 2: To smooth the shape of the probability distribution, which is generated from the limited scanning operations in Step 1, we design a shaping filter to obtain the shaped probability distribution

  

  where

  

  is a normalized factor and is a control parameter.   Normally, is chosen as 2.0.

• Step 3: The heavy-tailed characteristic of the signal probability distribution cannot be revealed by a short-term signal-collection procedure. Therefore, a tailing filter is applied to the probability distribution trained from Step 2:

  

    where

  

    The signal strength threshold s₀ satisfies

  

, ß,

In the working phase, the location system deploys a position-determination model to calculate position. As indicated in Equation (1), the probability P(l_i | O) is also affected by the probability
P(l_i), the prior probability of x being l_i according to certain prior knowledge. In this section, we propose a tracking-assistant positioning algorithm that relies upon topological knowledge to obtain the P(l_i).

The indoor positioning system serves context-aware applications such as guide systems and tracking systems, in which the movement of a mobile device is subject to the topology in a certain area. For example, the mobile device cannot skip from one position to another that is far away from its prior position. Furthermore, a mobile device cannot travel between two positions in a short time if two positions are divided by a wall. The discipline of movement motivates us to introduce topological knowledge into a positioning system to enhance positioning accuracy.

Supposing that the k determined positions prior to a new location x are L_k^P, L _k-1^P, ..., L₁^P, there is a high probability that x is near the prior positions. Thus, we define a tracking probability
P(l_i | L_k^P, L_k-1^P, ..., L₁^P) for each marking position l_i in set L,

where dist(l_i, L_j^P) represents the distance between position l_i and position L_j^P. Here D is a constant representing the maximum distance between positions. Note that D is used only to normalize the tracking probability. The method used to choose the value of D does not affect the final position-determination procedure. Since the movement of a mobile device follows the given topology, the tracking probability of position l_i represents the feasibility of the mobile device being moved to position l_i after a prior moving trace (L_k^P, L_k-1^P, ..., L₁^P). In an extreme case, such as k = 1, we have P(l_i | L_k^P, L_k-1^P, ..., L₁^P) = P(l_i | L₁^P) = dist^-1(l_i, L₁^P). Therefore, the tracking probability is reversely proportional to the distance between the latest determined position L₁^P and position l_i. Obviously, the longer the distance, the lower is the probability of the mobile device being moved to position l_i from position L₁^P; the shorter the distance, the higher the probability. Since the mobile device cannot move a long distance in a very short time, the tracking probability P(l_i | L_k^P, L_k-1^P, ..., L₁^P) can be used as the P(l_i) defined in Equation (1).

Note that the distance between two positions can be obtained from some prior knowledge, such as the physical distance between two positions. Considering the complexity of indoor environments, we use a weighted graph (vertex, edge), G(V, E), to represent the position topology. We put all marking positions from set L into set V and assign edge e to each position pair as e(l_m l_n) if the physical distance between positions l_m and l_n is shorter than a threshold distance and there is a direct way to connect two positions in physical space. We also set the weight for edge e as the physical distance between two positions. Therefore, for any position pair l_i and l_j, we define the distance dist(l_i, l_j) as the length of the shortest path between two positions in graph G(V, E).

To be specific, deploying the simple tracking probability as P(l_i) in Equation (1) may introduce a risk of imprecision for the system because of error propagation. Recall that the definition of tracking probability is subject to a series of prior determined positions. If there is some error during the determination process, it will be propagated and will affect the precision of later calculations, which further affects the accuracy of the positioning system. To avoid error propagation, we must introduce an error-detection mechanism. In our system, the state machine is introduced for this reason.

We define the state-of-location algorithm and categorize the state into tracking states T = {T₁, T₂, ..., T_n} and nontracking states N = {N₁, N₂, ..., N_m}. The states in T represent that the positioning system should deploy the tracking probability in the determination process, while the states in N mean that there is a risk associated with using tracking probability. Transference between states is triggered by two events: p when an error position calculation has occurred, and q when there is no error. For each position-determination process, an event is generated to trigger the transference of the state according to the rule defined in Figure 5. Since the algorithm determines whether or not to use tracking probability according to the state, the risk of error propagation is avoided while the accuracy of the positioning system is maintained by the use of tracking probability.

Figure 5

Experiments and evaluation

To study the performance of the WLAN-based indoor positioning system, we conducted a number of experiments. The performance of the positioning system was measured using the metric error distance, defined as the spatial distance between the original position and the position calculated by the positioning system.

We conducted two sets of experiments. In the first, we randomly chose a number of positions in the area and placed mobile devices at the positions to evaluate the positioning system. For many applications, such as telephone follow me and everywhere printing, there is not much movement. The mobile device remains in one position for a rather long period of time before moving to another position. The most important consideration for such applications is the accuracy of the positioning system, so we call these experimental scenarios position testing. The second set of experiments is called trace testing. For these, the mobile devices are walked through the testing area at a certain speed. These experiments test for applications such as guiding systems.

Figure 6(a) shows the cumulative error distance distribution of the position testing. In the experiment, we vary the number of tracking states, n, and the number of nontracking states, m. Note that, if we set n = 0, our positioning system withdraws to the traditional system in which topological knowledge is not considered. As shown in the figure, the accuracy of the WLAN-based positioning system with the tracking-assistant algorithm is higher than without the tracking-assistant algorithm. More specifically, when we set n = 7 and m = 2, we achieve the best performance. With a 90% probability, the error distance is within 2 m. With a 95% probability, the error distance is within 4 m. Since the tracking-assistant positioning algorithm adopts the topological knowledge of the testing area, the determined position seldom jumps far away from the original position, and thus accuracy is maintained.

Figure 6(b) shows the cumulative error distance distribution of the trace testing. In the experiment, we also vary the number of tracking states, n, and the number of nontracking states, m. As shown in the figure, the accuracy of the WLAN-based positioning system with the tracking-assistant algorithm is greater than without the tracking-assistant algorithm. When we set n = 7 and m = 2, the best performance is achieved. With a 90% probability, the error distance is within 5 m. With a 95% probability, the error distance is within 7 m. Note that because the movement of mobile devices also results in changing the original reference positions in the determination procedure, the accuracy of trace testing is not as good as that of position testing.

Figure 6

Recall that in the training phase, the workload is determined by both the number of marking positions and the number of scanning operations for each position. However, reducing the training workload and improving system accuracy is a tradeoff problem. We have conducted experiments in which we varied the scanning number for each position and applied different training schemes to obtain the signal distribution. Those trained signal distributions are used in the same determination model to study the effect of different training workloads and different training schemes on the performance of the positioning system. The histogram scheme, which is a well-known scheme proposed by Myllymaki et al. [9], is used in the experiment for comparison with our model-based signal-distribution training scheme.

As shown in Figure 7, it is clear that for both training schemes, the more scanning operations performed, the better the performance. However, compared with the histogram scheme [9], our training scheme requires fewer scanning operations. We also find that when the scanning number in our scheme approaches 100, the accuracy of the location system is not remarkably improved by further increasing the number of scanning operations. This indicates that there is a threshold workload for the training scheme. Setting the number of scans to the threshold is a good tradeoff between the complexity of the training process and the accuracy of the positioning system.

Figure 7

We also varied the number of access points in the test area to study how access points affect system performance. As shown in Figure 8, it is obvious that system accuracy is greatly affected by the number of access points. In the scenario in which there are only one or two access points, the accuracy of the positioning system is rather low. In general, to achieve an acceptable accuracy, it is better to add more access points in the area. Practically speaking, our results indicate that for each position in the area covered by the WLAN signal, there should be at least three or four access points.

Figure 8

Related work

Several WLAN-based indoor positioning systems have been built in recent years. The RADAR system [8] proposed a nearest-neighbor method to determine position, and a signal propagation model was proposed to describe the rule of signal propagation. Myllymaki et al. [9] introduced a probability approach to estimate user location. Battiti et al. [10] presented a neural network model for a positioning system. Smailagic et al. [11] studied the table-based method of determination. In [12], Myllymaki and Tirri also introduced a tracking-assistant positioning system, and tracking techniques are also used by the Ekahau** [13] system.

Our work differs from these efforts. First, we propose a model-based signal propagation distribution training scheme which is a tradeoff between system accuracy and the training workload. This scheme effectively reduces the complexity of the training procedure. Second, we propose a tracking-assistant positioning algorithm in which a state machine is used to adaptively transfer between tracking and nontracking status to achieve more accurate performance. The knowledge of area topology introduced into our position-determination model results in a remarkable improvement in the accuracy of our indoor positioning system.

Conclusions and future work

In this paper, a WLAN-based indoor positioning technology is presented. A position-determination model was built to represent the correlation between WLAN signal distribution and physical positions. Therefore, the system is divided into two phases: the training phase, in which sample signals are collected to train the model, and the working phase, in which the model is applied to determine the location of mobile devices. To reduce the complexity of the training procedure, a model-based signal propagation training scheme is proposed to reduce the workload while maintaining the accuracy of signal distribution. To improve the accuracy of the location system, a tracking-assistant positioning algorithm is proposed that uses topological knowledge to assist the position determination. We have set up a positioning system in the IBM China Research Laboratory, and our experiments indicate that the positioning system achieves a 2-m accuracy with 90% probability for static position determination scenarios. For a moving mobile device, a 5-m accuracy with 90% probability is achieved.

We are now further evaluating our system under various circumstances, such as whether and how multiple mobile devices affect one another. Moreover, we have begun building several location-aware applications, such as telephone follow me and everywhere printing, based on the WLAN positioning system. In the near future, we also plan to apply our determination technology to other positioning systems, such as those based on radio frequency identification.

^*Trademark or registered trademark of International Business Machines Corporation.
^**Trademark or registered trademark of Cisco Systems, Incorporated or Ekahau, Incorporated.

References