The applications of indoor positioning are many: indoor robots, inventory tracking, security, and location-finding, for instance. Currently, the main problem lies not with the need for applications, but with the implementation.
The challenge occurs precisely because of the tradeoff mentioned above. It is natural that a more accurate system should cost more than a less accurate one, or have some other disadvantage. GPS, for instance, cost hundreds of millions of dollars to develop, but is extremely accurate and flexible - it can be used anywhere on Earth. Various issues arise when designing a positioning system, such as clock synchronization, propagation delay timing, signal absorbtion, reflection and interference, and the challenge of creating custom hardware.
Petitioned by sailors and merchants, the English Parliament created the Longitude Act, which offered a large reward for the solution to the Longitude problem. Many solutions were offered, ranging from the mathematical (using astronomical tables2), to the absurd. One solution called for anchored ships to be positioned at set intervals throughout the ocean. On the hour, they would use cannons to propel fireworks high into the air. By timing the difference in the sound and sight of the fireworks, a ship could calculate her position from these ``beacons". Two such data points, from different ships, could determine distance through triangulation.
Of course, this solution was not adopted. In the end, the prize was won by a highly precise clock created by John Harrison3. Modern solutions for indoor positioning bear a resemblance to these methods, ranging from the brute-force ``cannon" approach to mathematical methods similar to the astronomer's tables and the accurate clock.
This method, though effective for room-level positioning, bears a resemblance to the ``cannon" method previously discussed (detecting a signal indicates that you are in the vicinity of a transmitter, but the propagation delay is not used to determine distance). Beacons must be placed in every room, and the user's receivers look for the signals they transmit. In addition, IR requires line-of-sight communication, because it has a high tendency to bounce off, and not penetrate, walls and ceilings. Because of this, it would be difficult to refine the Active Badge system for more accurate positioning, or for use in an environment with many obstacles.
While not as impractical as anchoring ships permanently at sea, this approach does not scale well, because every room and hallway needs a transmitter. As taught in many computer science and engineering classes, a brute-force solution is generally not the best because it wastes resources (such as time or money) compared to a better-planned strategy. Also, this brute-force method only yields room-level granularity. For these reasons, IR beacons were not chosen.
The GPS system is composed of a constellation of satellites in space, orbiting in precisely-known paths. Each satellite contains multiple $100,000 atomic clocks, each with sub-nanosecond precision. These satellites constantly transmit their current time, encoded in radio signals that propagate at the speed of light. Again, this is similar to the ``cannon" method, with beacons placed at known locations. By measuring the delay from when the signal was sent (encoded in the signal itself) and when it was received, the propagation delay of light can be determined. From this, the distance to a satellite can be determined - light travels about 1 foot per nanosecond. Because each satellite's exact position is known from the orbital table, multiple satellites can be used for triangulation. Four satellites are actually needed, because the ground GPS receiver does not contain an atomic clock of its own. Instead, the fourth measurement is used to determine the time skew that makes the data consistent. The true position can then be recalculated. Because the signals are travelling from space, they are understandably weak. Dense tree cover, much less a cement wall, will block the satellite's signal. Thus, in an indoor environment, GPS cannot be used.
Due to the speed of light, each nanosecond of delay is a foot of error. This is the reason for the incredibly precise atomic clocks, which justifies their great cost. However, this highlights the a major drawback with any propagation delay method - accurate clocks are an absolute necessity. A computer with a microsecond granularity will have an error of about 1000 feet.
GPS ``pseudolites" act as pseudo-satellites on the ground (hence the name). The pseudolites have their position accurately determined, and they send a GPS-like signal to clients. They do not have atomic clocks, but instead use phase differences, discussed later.
This amplified signal can be received indoors, and has even been used for centimeter-level accuracy[]. However, this solution is very expensive, and was used in open indoor environment, without obstacles. However, interfering walls and other objects can lead to the multipath problem. This occurs when a signal reflects and travels along multiple paths to the receiver. The receiver does not know which signal is correct, and the delayed signal may be preferred to the true one (it may overpower the original). This is a fundamental problem with non-line-of-sight methods.
GPS pseudolites, while promising, were much too complex and expensive to be developed in one semester by one individual. This involves specialized hardware and software - commercial outdoor pseudolites cost upwards of $10,000. Centimeter-level resolution indoors is excellent, but may not work with obstacles. A cheaper solution, with meter-level accuracy and the ability to work with obstacles, would be desirable. Before the military descrambled civilian GPS signals, they were only accurate to tens of meters; an accuracy on the order of meters is still useful. The pseudolite's cost, complexity, and unknown performance with obstacles overshadowed its extreme accuracy, and it was not selected.
This method uses the phase difference between two sinusoidal signals to determine position. Multiple transmitters emit sine waves of known frequencies, and the receiver notes how out of phase5 the signals are. Because the receiver will detect varying phase differences at separate locations, it can solve for its position.
As an example, suppose that the receiver always gets signal A at its maximum when signal B is at its minimum (assume A and B are of the same frequency). The maximum of a sine wave occurs at 90 degrees, and minimum at 270 degrees. Thus, the signals are 180 degrees out of phase. This means that the difference in position of the two signals is always half a wavelength (180 degrees). This knowledge can be used to plot a hyperbola of possible locations6, and the intersection of multiple hyperbolas can be used to determine the exact location. At a minimum, three transmitters are necessary (since only two transmitters will give an entire hyperbola of possible locations).
To avoid ambiguities, the wavelength is assumed to be on the order of hundreds of meters, so the receiver is always within one wavelength of both transmitters.
There are several advantages to this method. First, it does not require an atomic clock, because the phase difference, not the propagation delay, is being measured. In addition, the phase difference should remain constant at a single point. Unlike the GPS pseudolites, we are not trying to recreate the GPS signal, and can transmit it in any format that is convenient.
The disadvantage is that custom hardware and software must be built for the transmitter and receiver. Luckily, phase differences are fairly easily detected in hardware, and the electronics is available to do just that. The software is more complicated, but this approach was considered as a potential candidate.
To determine location, a user visits various locations and records the signal strength to various access points (APs) around the building (the APs are located throughout the building, and are what the user's wireless card connects to when transferring data). Every point, in theorym has a different profile of the signal strengths, due to its distance from the APs, intervening walls and furniture, etc. After creating a ``radio map" for each location of interest, the user can later visit a point and look up which prerecorded profile best matches the current signal strengths. Using this system, the group was able to get results of an average accuracy of 2-3 meters.
The research group also developed a system based on the raw signal strength itself, by trying to compensate for the attenuation introduced by various walls. With a blueprint of the building, the number of walls between any two points can be determined and the signal degradation can be accounted for. Indoor radio propagation is complex and not well understood, since radio waves can reflect or be absorbed, or suffer interference from nearby sources (microwave ovens, which operate at frequencies near the 2.4 GHz used by wireless networking cards, are a common source of noise). For these reasons, the modeling method was not as accurate as the ``radio map."
The advantages of profile method are numerous. First, it avoids the problem of timing by using tables for position finding (like the astronomer's tables in the Longitude problem). In addition, it uses cheap (less than $100), readily available wireless cards. Also, the infrastructure it uses (the wireless networking environment) is useful for transmitting any type of data. GPS signals, for instance, are really only useful for position finding and timing. The wireless network created by such a positioning system is potentially useful in any office for the Internet, file and print sharing, etc.
Also, the ``radio map" method avoids direct interpretation of the signals. Even if signals are weakened by walls and obstacles, it is acceptable because the weakened signal is recorded in the table. Presumably, upon revisiting the point, one will encounter that same, attenuated signal. Thus, all the multipath and interference problems become irrelevant, as they are automatically accounted for. The RADAR system was shown to work around walls in a real office building, while most other positioning systems were used in an open, indoor environment and were unproven in a realistic setting.
The main disadvantage for the researchers developing this system was the lack of appropriate software. Most software only recognized the wireless card as a traditional (wired) networking card. Signal strength information was not available, since it is meaningless in a wired environment. The researchers had to use the FreeBSD operating system, which allowed them to get signal strength information directly from the device driver (the low-level software that interacts with the card).
Despite this drawback, this positioning system was considered as a candidate because of the readily available hardware, demonstrated performance around obstacles, and usefulness beyond a positioning device.
Computer vision techniques involve determining position by carefully examining the environment. An example would be determining your location in a kitchen by noticing a sink below you, a refrigerator to your left, and a window directly ahead. Your altitude could be determine by the angle at which these objects appeared.
This method's main advantage is its lack of timing and synchronization issues, and errors associated with the propagation of electromagnetic signals (such as multipath or attenuation problems). However, the costly downside are the heavy computations required for the image processing. A portable positioning device is unlikely to be powerful enough to be useful, and even if the computations were offloaded to a central server, the problems would continue as the number of users grows.
High frequency sound waves, or ultrasonics, can be emitted and detected, and their signal strengths can used for triangulation. However, this method requires line-of-sight, as a hard object, such as a wall, can reflect the sound waves. It would not work for building-wide coverage except in a manner similar to the Active Badge system, with beacons in every room. As previously discussed, I chose to avoid brute-force methods.
Low-frequency magnetics are used in the motion-capture industry to determine position to centimeter-level accuracy. Beacons produce a slowly varying magnetic field 7of a known shape, which sensors use to determine position.
The major problem with the motion-capture version is the need for a cord attached to the user. This is a tremendous disadvantage, limiting the comfort, range, and inherent practicality of the system 8.
Researchers at Stanford[] have developed a wireless magnetic system, with centimeter-level accuracy. The method is quite robust, and still works despite interference from concrete cinder blocks, bricks, and garbage cans. However, this was tested in a relatively open indoor environment, with beacons about every 10 square feet. While this could be extended to building-wide coverage, the cost of doing so could be expensive, given the number of transmitters needed. This system was considered briefly, but ultimately neglected because of this reason.
The RF phase shift and wireless networking systems were the exception. Both stood out because they were extremely efficient, in the sense that they were relatively scalable and inexpensive solutions. I then decided to pursue the phase shift system, with the wireless networking approach as a backup. The phase shift system is advantageous because it does not require a pre-existing lookup table; positions can be calculated immediately.
I decided the remainder of the semester was not enough time to create and debug an entire phase positioning system. While more flexible than the wireless networking system, I thought it better to have a working, less flexible system than an incomplete, flexible one. In addition, I had more background in software; while I was extremely willing to learn the details necessary to create the custom hardware, acquiring this knowledge would have used much of the semester.
My contribution was the realization that a directional antenna could improve the quality of the signal profiles. Briefly, a directional antenna amplifies signals received from certain directions while decreasing it in others10 (described in more detail in the "Methodology" section).
The main goal of my approach was to create unique profiles at each location, because similarities in signal profiles would result in ambiguities when determining position. A directional antenna, ideally, should help to distinguish various positions.
In addition, both the strength and stability of the signal matters. If the signal is too weak it cannot be detected, and an extremely powerful but noisy signal can be useless. The profile at each point needs to be relatively constant as time progresses, so the user can make an accurate table lookup. A directional antenna that both amplifies and stabilizes the signal is ideal - the results of this search appear later.
Finally, the directional antenna must be of a reasonable size. In general, the size of an antenna is proportional to the wavelength of the signal it wishes to receive. A 2.4 GHz signal has a wavelength of about 12cm, and antennas of this size are not overly cumbersome. It was fortunate that 802.11b was allocated such a high-frequency slice of the spectrum by the FCC - had the frequency been in the megahertz range, the ideal antenna could have been tens or hundreds of meters long (obviously impractical for portable, indoor use). However, even the 12 cm size is too large for PCMCIA laptop cards, and so an external antenna is required.
record.pl: This script parses the logfile and pulls the signal data into tables, keeping running totals of the signal, noise, and SNR for each access point. It finally computes the average, and records this in a position file (the filename is specified as a command-line argument).
capture.pl: This script parses the logfile (as in record.pl), but now examines every position file in the current directory. It stores the relevant data in tables, and computes the Euclidean distance of the current vector to the current position file, recording the entries in a table. The results are sorted, and the top ten results are listed, along with their Euclidean distance from the corresponding position file.
This design is useful because profiles can be stored in various directories (indicating differing position data), and capture.pl can be placed in each folder. In addition, it is fairly modular because
I also learned MySQL to store the position information in a database. However, storing the values in individual text files was easier; it allowed locations to be added, removed, and examined very easily. The MySQL representation will be useful if the table must be accessed through the Internet (see the ``Follow up work" portion of the ``Discussion" section).
Further research yielded alternate designs, from a shortened version of the Pringles Yagi [] to a waveguide antenna based on a metal can []. I created both, and learned some of the antenna theory along the way. To my understanding, the waveguide (metal can) works by creating a standing wave13 inside the can, and sampling it at its maximum. Because a sine wave reaches its maximum at a quarter wavelength (90 degrees), the piece of metal that actually samples the signal is placed there (roughly 3cm from the rear of the antenna).
Various components, such as the connectors between the antenna and wireless card, had to be researched purchased online14. Once obtained, the antenna was soldered together.
Hardware:
Software:
The following test (Fig. ) sampled the signals every second for an extended period of time (about 45 minutes). The purpose was to determine the typical variation in a signal, as well as each antenna's effect on that variation. The wireless card, without an antenna, was used as a control.
| Antenna | Avg (1) | Std. Dev.(1) | Avg (2) | Std. Dev.(2) | Avg (3) | Std. Dev. (3) |
| None | 40.47 | 3.37 | 4.14 | 2.39 | 8.00 | 1.98 |
| Pringles Yagi | 41.49 | 4.14 | 11.08 | 1.76 | 16.69 | 1.25 |
| Can Waveguide | 44.24 | 1.28 | 14.53 | 2.40 | 12.84 | 1.17 |
Both antennas have amplified the signal (compared to no antenna), and the variation has been reduced as well. The twenty-second moving average (Fig. ) gives us more insight. Twenty seconds is a reasonable limit on the amount of time a user is willing to spend to determine his or her position. Because our program takes the average of the log (with a maximum length of about 20 seconds of data), the variability in the moving average is an indication of how accurate the system can be.
The can-waveguide appears to give the most stable signal, as can be seen from the charts (lowest standard deviation on average). It tends to boost the signal noticeably as well, while keeping it it with relatively little variation. The Pringles-Yagi seems to boost the signal, but at the expense of stability - notice how much the moving average varies.
Both antennas are an improvement of the internal antenna in the card, which has the lowest average and highest standard deviation in all cases.
This data supports the findings that the can-waveguide performs the best outdoors. The can was selected to perform positioning experiments.
Rather than making a grid of my own, I used to 1' by 1' tiles on the ground floor of the Computer Science building. Fortunately, the tiles vary in color, making it easier to keep track of the current position.
An issue with a directional antenna was the direction in which to point it. The only directions which anyone can find without a compass are up and down, with up being the likely standard, for obvious reasons. For performance comparisons, the ``forward" direction (front of the Computer Science building) was occasionally chosen.
When performing the experiment, I noticed that occasionally the first match would be off by a significant amount (8 feet or more), but the second match would be correct. In such cases, I kept a record of the "corrected" score as well, assuming the first result was invalid. The results are as follows:
| Orientation and Data | Average Error | Std. Dev. |
| Raw, Up | 3.43' (1.04m) | 3.60' (1.10m) |
| Corrected, Up | 0 | 0 |
| Raw, Forward | 3.43' (1.04m) | 6.29' (1.92m) |
| Corrected, Forward | 0.57' (0.17m) | 1.51' (0.46m) |
Overall, the scores are fairly good. Even the raw data has an accuracy on the order of a meter, which improves even more if the data corrected for the extreme points. The problem in practice is that the algorithm does not know the x, y coordinates of the entries in its table. Thus, it cannot tell if the first choice location is vastly different from the previous one, and likely to be incorrect.
Surprisingly, the directional antenna fared worse than the antenna pointing upwards on this test. I believe this is because the profiles appear similar for points along a line when using the directional antenna. My hypothesis is that the directional antenna boosts the signal coming parallel to the line, while suppressing those coming perpendicular to it. However, those perpendicular signals can server to differentiate points along the line. Without these unique features, the profiles appear similar, and the lookup is not as accurate.
In the Computer Science building, I mapped the colored tiles, and took position data on approximately 180 tiles nearby (including the mapped ones). As before, some points were wildly off, but the second choice was correct. The results of the experiment follow:
| Data | Mean | Std. Dev. | Median | Mode |
| Raw | 5.48' (1.67m) | 3.23' (0.99m) | 5.0' (1.53m) | 4.0' (1.22m) |
| Corrected | 4.3' (1.32m) | 2.67' (0.81m) | 4.0' (1.22m) | 2.0' (0.61m) |
Notice how many of the errors in the raw data move to less extreme values in the corrected version. This lowers the average, median, and mode, resulting in more accurate positioning. Again, this is a decision that only a human can make, since the current algorithm does not information about the relative position of entries in the table.
The signal-to-noise ratio is certainly affected by the orientation of the directional antenna. This is to be expected, since the antenna should strengthen the signal in some directions and attenuate it in others. Future implementations could take advantage of this.
The main disadvantages of the system is that every point must be mapped out beforehand. It took hours to set up and test the nearly 200 points when finding the error in unknown positions (a lot of time was spent recording points and examining their location data). There is not an obvious solution to this problem, except that the interface to the system can be improved. This will allow profiles to be taken with a single click, greatly decreasing the time necessary to map out a building.
The other disadvantage, which became apparent in some of the trials, was that multiple locations may have similar distances to a given profile. For example, the point (5,5) is equidistant from a profile of (0,5) and (5,0), even though the profiles are quite distinct. In addition, it is sometimes the case that the client logging utility will record the impossible signal strengths of 65,635, presumably from a division by zero error. With a value like this, nearly any profile could potentially match, since the distance vector becomes largely meaningless. Errors in the signal logging utility are a possibility as well, but must be watched for.
The phase of a signal can be altered by the delay introduced by intervening obstacles, as well as errors introduced by the multipath problem. Because the wireless networking solution does not depend on the absolute signal strength (or phase), it can avoid such problems.
In addition, the pre-existing hardware and software turned out to be a huge advantage. Why design an entirely new operating system and hardware when they are readily available? Wireless networking cards are easily bought, have been debugged, and use a well-defined interface (PCMCIA) to existing operating systems. The essence of the problem - constructing and searching the positioning tables - is the main piece left to implement, not the underlying plumbing.
The last, major advantage is the useful wireless network created by this system. Alternatively, an existing wireless network, such as the one in the Computer Science building at Princeton University, can be used with no changes. This advantage is large, since a wireless network is extremely useful in and of itself, without the added feature of indoor positioning.
Given these benefits and the my current hindsight, I am very satisfied with the choice of wireless networks as the foundation for the the indoor positioning system.
First, the antenna can be improved. While the can-waveguide did fairly well, a custom-made waveguide could boost the signal further. Commercial antennas comparable to the can-waveguide can cost over $100, so a home-built antenna is still an economical solution.
There are numerous improvements to the matching algorithm, some mentioned earlier in this paper. First, the user can attempt to ``sweep" the directional antenna in a circle, with the logging software recording the signal the entire time. Interpreting this signal will be tricky, because it is unlikely that the user will sweep exactly one revolution, or that it will be at a constant speed, etc. This is the main advantage of always having the user point the antenna üp". The direction is always consistent, and there are no ambiguities (even if it may not have the highest performance).
To improve on the current method, more statistics about the signals can be included in the profile. Rather than simply averaging the signal, the standard deviation, maximum, and minimum can be included. The client's software can then perform statistical tests to determine how likely it is that their profile matches another. In addition, a weighted average could be used, where the most-stable signals are weighed more heavily in the Euclidean distance calculation than those that vary. In addition, signals that appear to be erroneous, such as those having too high a maximum (such as 65,635) or having a zero standard deviation, can be filtered out.
The software can be improved as well. Currently, it is entirely text-based, and requires the user to actively take his or her position. A GUI (graphical user interface) that could provide real-time, constantly updated data would be useful. In addition, the position files are stored locally, on the client's machine. Instead, these files could be stored on a central server that the client can access and make queries. Because this system uses a wireless network, this functionality is automatically built-in. This allows for the ability to authenticate users, and provide some security information (such as noticing if a user's location is in a privileged zone).
Lastly, the system will ideally be transferred to a more portable system, such as a Palm Pilot. In this case, the computations could be offloaded to a central server. Because the computations are not that expensive, a single server could potentially handle many clients. The main challenge is finding a wireless card for a PDA that allows an external antenna17, and making an antenna small enough not to be noticed (perhaps one that folds), but large enough to be useful (remember that the wavelength at 2.4 GHz is roughly 12 cm).
So far, these are the major improvements I have come across, but working on the project is sure to bring others.
The underlying lesson that seemed to be that a relatively complex and useful system can be built from humble, pre-existing parts. The secret was finding where those parts were, and how to dig around for them. If I had to rebuild this system from scratch, it would not take long, but only because I have the gift of hindsight, i.e., knowing where to look, what to buy, and how to put it all together. The most time-consuming part of this project was the research required to gain that knowledge.
The original intent of this project was to create an indoor positioning system as an alternative to GPS. Through heavy research and building upon previous methods, I am happy to say that I have accomplished that goal.
<http://www.princeton.edu/~kazad/resources/cs/cs398.htm>
1Thanks to Prof. Wang for mentioning the similarities between this historical event and my project.
2Because the motion of certain stars and planets appears different from various points on the Earth, one could use a table to estimate his location given a certain celestial pattern.
3By knowing the time difference between your ship and a place of known longitude, such as London, one can determine distance. This difference can be determined by setting the ship's clock to noon when the sun is directly overhead, and keeping the watch on London time. The Earth rotates every 24 hours, so a time difference of 1 hour corresponds to a distance of 1/24 the Earth's circumference. One degree of longitude corresponds to roughly 68 miles, or a time difference of 4.5 minutes[].
4Ancient mariners used dead reckoning: they threw logs overboard while sailing. By seeing how fast the log receded from the advancing ship, the vessel's speed could be gauged. This test was performed hourly, and the distance travelled (speed multiplied by time), was added to the previous location in the direction of movement.
5The phase of the signal is an angle from 0 to 360 degrees (or 0 to 2p radians), and informally represents the ``starting point" of the sine wave.
6A hyperbola can be defined as all points on a plane satisfying the relationship AP - BP = K, where AP is the distance from A to P, BP is the distance from B to P, and K is a constant (the phase shift, represented as a distance). A and B are fixed points (the transmitters), separated by a fixed distance, and P is a point on the hyperbola (the receiver).
7On the order of tens or hundreds of Hz.
8Given the ability to be tethered, a low-cost, line-of-sight, centimeter-level positioning system could be created with a few anchored tape measures.
9New receivers can be added without changing the existing system or affecting the level of accuracy.
10The directional antenna used was passive (no power was added), and thus cannot increase the total energy of the signal.
11The signal and noise are both measured in dBm (decibels, with respect to a milliwatt). Because of this logarithmic scale, the ratio between two numbers is simply their difference.
12Thanks to Prof. Wang.
13A standing wave must be of a certain proper wavelength, such that a whole multiple of the wave fits inside the can. Our can is roughly 12cm long, or one wavelength.
14The connector inside the antenna is an ``N-connector", and is designed to handle microwave frequencies (up to roughly 11 GHz). The cable between the N-connector and the Lucent card is called a pigtail.
15If there are only two positions mapped, for instance, then any signal profile will match one or the other.
16There was not enough time to develop and test an algorithm that would allow the user to ``sweep" the directional antenna around in a circle to create a profile.
17If necessary, the card
can be opened and modified to allow an external antenna.