Today you can easily find your way to, say, the nearest Starbucks in a strange city, thanks to a cascade of events that began a little more than 30 years ago, when a Soviet Sukhoi interceptor flying high over the Sea of Japan fired off two heat-seeking missiles. The long-term result: You now have no trouble locating a cappuccino.
Of course, you’re not finding that coffee by the heat it gives off. You are most likely guided to it in missile-like fashion by the GPS receiver in your smartphone or on your dashboard. That ubiquitous piece of consumer technology works—indeed exists—only because the U.S. Department of Defense allowed civilian use of its satellite-based positioning system. That wasn’t the original plan. The Global Positioning System was supposed to be exclusively for soldiers, sailors, and airmen, until President Ronald Reagan ordered a sudden change in policy in response to the deaths of 269 people aboard a Korean airliner that veered into Soviet territory on 1 September 1983. Believing it to be a military aircraft on a spying mission, Soviet air defense forces shot it down.
The Department of Defense dutifully carried out Reagan’s instructions to make GPS signals available for civilian uses, but it hedged at first, adding random timing errors to the satellite signals accessible to nonmilitary GPS units so they could determine locations to no better than 100 meters. Then in 2000, after President Bill Clinton ordered this purposeful degradation to be stopped, the error circle shrank to 10 meters or so. All of a sudden, GPS became extremely valuable for vehicle and even pedestrian navigation.
Your Smartphone Docent: Wifarer, based in Victoria, B.C., Canada, produces smartphone apps for indoor positioning based on Wi-Fi signals. One of the company’s custom apps guides visitors around the Royal BC Museum (also in Victoria), helping them find their way and understand the exhibits.Photo: Royal BC Museum
Those shifts in U.S. policy, along with the plummeting cost of GPS chip sets and the proliferation of smartphones, ended up putting formidable satellite-navigation capabilities in almost everyone’s pocket. The rub is that radio signals coming from distant satellites can’t help where the view of the sky is obstructed, which makes navigating in narrow canyons, urban or otherwise, tough going. And these high-frequency signals bounce around so much when they hit metal that getting a good GPS fix indoors usually proves impossible.
It’s a huge problem, one that radio engineers are keen to solve. They’ve been pursuing a host of different strategies to help us find our way about indoors and also to track movable assets—hospital equipment, specialty tools on the factory floor, mobile robots, livestock, you name it. Here are the technical underpinnings of the leading possibilities, along with some educated guesses as to how they will pan out.
“Indoor navigation is very, very tricky,” says Kaveh Pahlavan, a professor of electrical and computer engineering at Worcester Polytechnic Institute, in Massachusetts. As director of the Center for Wireless Information Network Studies, he has closely followed the various radio-based positioning methods that have emerged over the years and watched how these technologies have shaken out. Often, he notes, progress isn’t just a function of technical promise. Business realities regularly trump that. “The fact is, what industry selects is important,” he says. “Today, Wi-Fi localization is the most popular.”
Boston-based Skyhook Wireless, which Pahlavan advises on technical matters, is one of many companies offering positioning based on Wi-Fi (and cellular signals and GPS, where those are also available). The company maintains a huge database of the often-changing geographic locations of Wi-Fi access points by hiring an army of “wardrivers”—people who drive around while recording Wi-Fi signals and GPS positions. A user with a handset running one of the Skyhook-enabled apps can then apply the company’s various proprietary algorithms to gauge position based on which of the mapped access points are within range and how strong the received signals are. The beauty of this approach is that it requires no additional infrastructure, and any Wi-Fi–equipped phone, tablet, or laptop can be used without modification. That’s why the original iPhone and iPod Touch models (which lacked GPS receivers) used Skyhook for position estimation.
How good are the position fixes? Skyhook’s tests show typical indoor accuracies of 3 to 10 meters. That’s better than GPS manages outdoors, but it still could easily misidentify the room you’re in or the floor you’re on. Accuracies can be improved, though, by adding more access points and carefully charting the radio environment within a building of interest. That’s what Wifarer, for example, of Victoria, B.C., Canada, does to produce site-specific Android and iOS apps for displaying position-dependent information. Impressively, its app users were able to pinpoint their locations to within about a meter and a half, on average, at the Royal BC Museum, where the company rolled out its system last year.
Being able to fix indoor positions to within a couple of meters is great for finding your way around museums, airports, convention centers, or malls, but it’s not adequate for many other situations. Imagine that you’re designing a mail-delivery robot. A location error of just 2 meters will have it, and you, bouncing off the walls. And the Wi-Fi strategy doesn’t work at all for first responders—say, firefighters trapped inside a burning building. [See “The Way Through the Flames,” IEEE Spectrum, September 2013.] If you’re willing to install radio equipment designed specifically with positioning in mind, though, there’s no shortage of options.
Map: Google; Wi-Fi Locations: wigle.net
Beacons of Opportunity
Google began providing Android users with navigational aids at certain popular indoor locales two years ago. One of the first locations to be electronically charted in this way was the Mall of America, located in Bloomington, Minn. As the most visited shopping mall in the United States, the Mall of America receives more than 40 million visitors each year, many of whom no doubt get lost wandering in its cavernous interior.
GPS signals don’t work well in such settings, and positions calculated using transmissions from cell towers would be awkwardly imprecise. As a consequence, the location-finding abilities of Google Maps depend heavily on broadcasts from the mall’s many Wi-Fi access points.
Google’s Wi-Fi database is proprietary, but WiGLE (Wi-Fi Geographic Location Engine), which contains data on more than 100 million access points, provides some sense of where they can be found.
WiGLE locations for Wi-Fi access points at the Mall of America [shown in the panels at right] could be significantly off, and in any event they’re not particularly up to date. So please note that this illustration should not be used for navigation.
One company offering help with that is Q-Track, based in Huntsville, Ala., which claims its indoor radiolocation system can provide submeter accuracy. It uses frequencies of about 1 megahertz, which is considerably lower than Wi-Fi. Why? “You want to have a signal that can get through a messy propagation environment,” says Hans Schantz, cofounder of Q-Track. Low frequencies can more easily penetrate the many barriers found indoors. They diffract less around obstacles, and they don’t fall prey to the multipath phenomenon, whereby the different waves caroming around inside a building interfere with one another.
Q-Track’s system differs from Wi-Fi localization in another fundamental way: It doesn’t use signal strength to gauge the distance between transmitter and receiver. Nor does it measure the time it takes the signal to travel from transmitter to receiver, as GPS does. Instead, it cleverly exploits the fact that at frequencies of a megahertz or so, and at building-size distances (say, up to 100 meters), the receiver operates in what radio engineers call the near field of the transmitter.
In this special zone, the emanations from a radio antenna are rather peculiar. The electric and magnetic fields do not rise and fall in lockstep, for example, as is normally the case with radio waves. And the difference in their timing (their relative phase) is, conveniently enough, a function of the distance from the transmitting antenna.
Q-Track uses the distance-dependent difference in phase, as well as other features found only in the near field, to calculate the location of a transmitter tag with respect to fixed receivers. Those receivers are fitted with antennas that can separately measure electric and magnetic fields. Outdoors, the system is accurate to 15 centimeters, but indoors, the structural elements of a building produce errors of as much as several meters. But by mapping out the site’s radio environment first, says Schantz, the system can locate one of its tags indoors to within 40 cm.
Although that might seem as precise as you’d ever need, applications like robot navigation demand even better. Also, Q-Track’s receiving equipment is bulky, and its tags are power hungry. Even with rechargeable lithium-ion batteries, they last at most a few weeks. So while the system works well in some settings, it’s hard to see it going into countless key fobs, cellphones, RFID tags, and wireless access points, which is what would be required for indoor positioning to become truly ubiquitous.
Mobile Robot Finder: Researchers are studying ultrawideband location systems for mobile robots, hoping to overcome the degradation in accuracy that arises when the signals do not follow line-of-sight paths.Photo: Alexander Feldman
One company hoping to overcome those hurdles is DecaWave, a Dublin-based fabless semiconductor manufacturer that has just released a wireless-networking chip designed to provide extremely precise indoor locations. It uses very brief bursts of radio energy, akin to those emitted by some radars, and can measure the time it takes these pulses to travel between radios to a fraction of a nanosecond, allowing distances to be determined to better than 10 cm. The brevity of the emitted pulses ensures that multipath interference won’t cause problems, because the reflected pulses are well separated in time from those taking the direct path between transmitter and receiver. It also means that the transmissions have a very large spectral bandwidth—about 500 MHz wide for DecaWave’s new product—which is why its chip belongs to a category of radio technology called ultrawideband.
Transmitting in short bursts harks back to the earliest days of radio, when the pulsating signals from primitive spark-gap transmitters splayed energy all over the spectrum, conveying a little bit of information while creating a great deal of electromagnetic havoc. Radio’s first regulatory authorities, eager to impose some order, put a stop to this flagrant waste of bandwidth a century ago. The operative paradigm since then has been to divvy up the frequency spectrum into narrow slices allotted to this or that application, with companies often paying handsomely for their radio privileges. So finding a suitable 500-MHz chunk over which to operate in today’s crowded spectrum might seem a practical impossibility.
In fact, it’s not. If power levels are kept low enough, ultrawideband transmissions, being so thinly spread out in frequency, can share the airwaves with conventional radio services without causing interference. Those services have long had to cope with the incidental energy given off by electric motors, automobile ignition systems, and all sorts of digital gadgets that aren’t intended to transmit radio waves. Low-power ultrawideband transmissions are no more menacing, which is why radio authorities around the world are now embracing this technology. As with many paradigm shifts, though, it’s been a long time coming.
The U. S. Federal Communications Commission first moved to allow ultrawideband radio back in 1998, when it was being promoted for short-range, high-speed data links. Spectrum users howled in protest, claiming it would interfere with their equipment. The agency has since systematically reviewed and pretty much discounted these objections, but ultrawideband long lacked industry standardization, so it struggled to gain traction.
DecaWave is counting on an ultrawideband version of the IEEE 802.15.4 standard used in ZigBee low-power wireless networks to propel it forward. That version incorporates ideas that DecaWave’s cofounder and chief technology officer, Michael McLaughlin, brought to the table in the mid-2000s. The resulting 802.15.4a standard, first ratified in 2007, includes provisions for both sending data and measuring distance precisely.
DecaWave isn’t the only company betting on ultrawideband radio for indoor positioning, but it’s the only one staking its fortunes on the development and mass marketing of a low-cost transceiver chip, one that’s small enough and cheap enough for cellphone and access-point manufacturers to adopt without a lot of fuss. “When we started the company, we said we wanted to be the next Qualcomm,” says Ciaran Connell, DecaWave’s cofounder and chief executive officer. “We got laughed at so much, we started saying we wanted to be the next Cambridge Silicon Radio. People seemed to accept that.”
Should DecaWave’s chips one day make it into everyone’s phones and access points, it would remove a big barrier—the hassle and expense of having to install in countless buildings radio equipment specifically designed to enable indoor positioning.
Despite the promise of DecaWave’s newly released ultrawideband chip—and the existence of earlier ultrawideband location equipment from companies such as Berlin-based Nanotron, Time Domain of Huntsville, Ala., and Zebra Technologies of Lincolnshire, Ill.—Pahlavan remains skeptical. “Indoor geolocation doesn’t yet have a good solution, including ultrawideband,” he says. He bases this view, in part, on a bit of history.
After the battle of Mogadishu, in Somalia, in 1993 (a debacle that was the basis for the book and film Black Hawk Down), it became abundantly clear that soldiers needed something better than GPS to find their way around during combat in urban settings. The following year, the U.S. Defense Advanced Research Projects Agency began work on what was known as the Small Unit Operations Situational Awareness System [PDF]. That sparked a great deal of interest in ultrawideband radio, which in principle could provide soldiers with both low-power, hard-to-jam communications and precision positioning capabilities. The U.S. government poured many millions into this program, yet the ideal positioning system never emerged.
The fundamental problem, according to Pahlavan, is that ultrawideband signals can get blocked too easily. In the various indoor environments he and his students have tested, this happens, on average, 40 percent of the time [PDF]. So it’s impossible for an ultrawideband receiver to determine whether the first pulse it detects followed a straight-line path from the transmitter or bounced off one or more surfaces first. The latter would, of course, throw off the calculated position.
In a study of an ultrawideband location [PDF] system conducted at the University of Bologna’s WiLab, in Italy, researchers found that the absence of signals following a direct path (or the delay that straight-line signals experience as they pass through thick masonry walls) can easily create errors of a meter or two. That’s similar to what Time Domain and Honeywell found in testing an ultrawideband positioning system meant for emergency responders [PDF], which proved good to about a meter. While that level of precision is just fine for most applications, it’s not much better than what can be achieved with systems using measurements of Wi-Fi signal strength. So it’s unclear whether ultrawideband location systems will catch on for anything other than line-of-sight applications or for those rare indoor settings where Wi-Fi signals aren’t present and you have to set up radio beacons anyway.
If not ultrawideband, then what? “Nobody knows the solution,” says Pahlavan. “People are waiting for the holy grail.” His best guess is that mass-market indoor positioning will continue to improve slowly, using hybrid schemes that take advantage of every radio source available: Wi-Fi in particular but also cellular signals, Bluetooth, television broadcasts, even ultrawideband sources, if these become commonplace.
And these hybrid positioning systems need not be restricted to using radio. They’ll probably incorporate measurements from the accelerometers and gyroscopes found in smartphones to add inertial navigation to the mix—a strategy both Qualcomm and Apple have shown interest in of late. (This past March, Apple purchased the Stanford University spin-off WiFiSLAM, which is working on ways to squeeze precise indoor navigation out of ordinary smartphones.) Pressure sensors will also be used to establish height above ground, and at least one company—IndoorAtlas, based in Oulu, Finland—thinks that a smartphone’s magnetometer measurements could help reveal positions indoors. “Indoor geolocation is a multidisciplinary thing,” says Pahlavan.
So don’t bet on a single silver-bullet technology to solve the problem of indoor navigation. Instead, expect a lot of belt-and-suspenders activity, with mobile units sensing their surroundings in every way possible, uploading the results to location-calculating engines in the cloud, and getting their positions continually reported back. And all this real-time indoor positioning won’t be reserved just for people and their phones—the Internet of Things will no doubt have location-finding abilities as well. That mug of coffee you’re seeking will soon have nowhere left to hide.
This article originally appeared in print as “You Are Here.”