In the last 10 years, the possibility of using wireless connections to deduce mobile devices’ locations has been a hot research topic in industry and academia. GPS systems frequently fail in large buildings, and even when they don’t, they’re not very precise. Firefighters tracking each other in a smoke-filled building, soldiers trying to determine each other’s position in urban environments, medical staff trying to locate equipment or each other in a busy hospital, and warehouse workers trying to find merchandise in an aisle of pallets stacked 20 feet high all need higher-resolution location information than GPS can provide.
Heavy hitters like Google, Intel and Nokia have all experimented with wireless localization, but MIT’s Wireless Communications and Network Sciences Group in the Laboratory for Information and Decision Systems (LIDS) is taking a more fundamental approach to the problem. The lab is developing a theoretical framework that explains just how accurate wireless location information can be, depending on network characteristics like interference and available bandwidth. But the theoretical results in turn point the way toward better algorithms.
Moe Win, a professor in the Department of Aeronautics and Astronautics, heads the group, which is based in LIDS. Win says that the group’s work was inspired by the work of Claude Shannon, who founded the field of information theory. In 1948, Shannon showed how to calculate the maximum rate at which data could be sent, error-free, over a communications channel, even in the presence of electrical or electromagnetic disruptions known as “noise.” Win’s group is trying to do something similar with location information. “Everything that we do, we try to approach in three steps,” Win says. “One is to try to understand ultimate limits: We just want to know, ‘What’s the best we can do?’ The second thing that we try to do is to design practical algorithms that approach these limits.” If mathematical analysis and computer simulations suggest that an algorithm is promising, Win says, “The third aspect is experimental verification.”
Strength in numbers
All three phases of the group’s work, however, rely on empirical data: Even the mathematical model that underlies the rest of the group’s work is based on measurements of wireless signals in realistic environments. In order to collect data reliable enough to underwrite such fine-grained theoretical analysis, Wesley Gifford, who just received his PhD as a member of Win’s group, developed a robotic system that can position a wireless transmitter with millimeter accuracy on a surface about the size of a Ping Pong table (see video). Gifford’s robot is built mostly from wood, since metal could interfere with the transmitter’s signal. Win's group has used the apparatus across the MIT campus to characterize extremely wideband wireless channels.
In a pair of papers appearing in October in the journal IEEE Transactions on Information Theory, Win and his students analyze networks in which wireless devices are working together to determine their locations. The researchers derive fundamental limits on the accuracy of the networks’ location information, even in harsh environments in which signals are bouncing off of obstacles and interfering with each other.
Among their insights is that networks of wireless devices can improve the precision of their location estimates if they share information about their imprecision. Traditionally, a device broadcasting information about its location would simply offer up its best guess. But if, instead, it sent a probability distribution — a range of possible positions and their likelihood — the entire network would perform better as a whole. The problem is that sending the probability distribution requires more power and causes more interference than simply sending a guess, so it degrades the network’s performance. Win’s group is currently working to understand the trade-off between broadcasting full-blown distributions and broadcasting sparser information about distributions.
All the angles
Wireless positioning systems can use a variety of strategies, Win explains. They might measure the received power of the signal; they might measure the time elapsed between the emission of a signal and its reception; or they might measure the angle at which the signal arrives. By quantifying the accuracy of the information provided by each of these approaches, Win’s group is explaining which should be practically exploited and how.
H. Vincent Poor, a wireless-communications researcher who’s also dean of Princeton University’s School of Engineering and Applied Science, says that the MIT researchers’ work is original in that it “exploits cooperation among low-cost wireless devices, rather than relying only on signals from fixed infrastructure, such as GPS systems.” In addition to theoretically characterizing the accuracy of localization system, he says, the researchers have “designed novel location-aware networks with sub-meter accuracy and high reliability.” Poor points out that the researchers’ algorithms will probably require further development before they’d be practical on larger networks, and the researchers are working on what Poor describes as “leaner” algorithms, so that they won’t consume too much power in cheap wireless devices with limited battery life. Nonetheless, he says, “I don't see any major obstacles for transferring their basic research to practical applications. In fact, their research was motivated by the real-world need for high-accuracy location-awareness.”