Kavraki Lab

Wireless networking, especially in the form of wireless Ethernet (802.11b), is becoming a critical component of networking infrastructure. Wireless technology enables mobility which, in turn, creates a need for location-aware applications. The recent interest in location sensing for network applications and the growing need for large-scale commercial deployment of such systems has brought network researchers up against a fundamental and well-studied problem in the field of robotics: determination of physical position using uncertain sensors, which is usually referred to as localization.

Many mobile devices and many buildings, both commercial and residential, are already equipped with off-the-shelf 802.11b wireless Ethernet, a popular and inexpensive technology. For example, in the figure that follows you can see the map of the third floor of Duncan Hall (the building that hosts the Computer Science Department at Rice) that is equipped with wireless Ethernet. The big black circles show the location of the network base stations.

Most wireless Ethernet devices already measure signal strength of received packets as part of their standard operation and signal strength varies noticeably as the distance and obstacles between wireless nodes change. If a reliable localization system could be developed using only this technology, then many existing systems could be retrofitted in software and new systems could be deployed using readily available parts.

The development of efficient and accurate location-support systems for indoor environments, which would also have the potential sensors one has to work with. Indoor environments affect the propagation of wave signals in non-trivial ways, causing severe multi-path effects, dead-spots, noise and interference. These effects make it infeasible to construct a simple and accurate model of the signal’s propagation in the space. The following figure shows examples of signal strength measurements taken from the same position but corresponding to different base stations. A location support system has to overcome the high uncertainty due to the behavior of the indoor wireless channels but at the same time it should keep the cost and the complexity of large-scale deployment as small as possible.

We proposed a system that achieves robust indoor localization using only RF signal strength as measured by an IEEE 802.11b wireless Ethernet card communicating with standard base stations. Since the required equipment for a wireless Ethernet network is usually already present in the workspace, serving communication purposes, this reduces the cost of providing localization services in an indoor environment. This also reduces the complexity for the user of a mobile device who wishes to take advantage of this localization service. To achieve our goal, we have adapted standard approaches from robotics-based localization, notably the explicit manipulation of noise distributions and the modeling of position as a probability distribution.

Our method for localizing a mobile station is divided in two phases. Initially, there is a training phase, where a sensor map of the environment is built by sampling the space and gathering data at various predefined checkpoints of the indoor environment. Later, the operator of a mobile computer walks in the same workspace and the system locates and tracks the operator’s position. Our system currently assumes that the environment remains consistent from training to localization.

Using only off-the-shelf hardware, we achieve robust position estimation to within a meter in our experimental context (experiments took place in Duncan Hall) and after adequate training of our system. We can also coarsely determine our orientation and can track our position as we move.

Here you can find a video that demonstrates the localization results: Real time simulation of localization results. The blue line is the real position of the laptop as its user is walking in the corridor. The red crosses correspond to the result of the Bayesian inference. The black X marks correspond to the output of the sensor fusion with the Hidden Markov Model.