For most of the 20th century, the paradigm of wireless communication was a radio station with a single high-power transmitter. As long as you were within 20 miles or so of the transmitter, you could pick up the station.
With the advent of cell phones, however, and even more so with Wi-Fi, the paradigm became a large number of scattered transmitters with limited range. When a user moves out of one transmitter’s range and into another’s, the network has to perform a “handoff.” And as anyone who’s lost a cell-phone call in a moving car or lost a Wi-Fi connection while walking to the bus stop can attest, handoffs don’t always happen as they should.
Most new phones, however, have built-in motion sensors — GPS receivers, accelerometers and, increasingly, gyros. At the Eighth Usenix Symposium on Networked Systems Design and Implementation, which took place in Boston in March, MIT researchers presented a set of new communications protocols that use information about a portable device’s movement to improve handoffs. In experiments on MIT’s campus-wide Wi-Fi network, the researchers discovered that their protocols could often, for users moving around, improve network throughput (the amount of information that devices could send and receive in a given period) by about 50 percent.
The MIT researchers — graduate student Lenin Ravindranath, Professor Hari Balakrishnan, Associate Professor Sam Madden, and postdoctoral associate Calvin Newport, all of the Computer Science and Artificial Intelligence Laboratory — used motion detection to improve four distinct communications protocols. One governs the smart phone’s selection of the nearest transmitter. “Let’s say you get off at the train station and start walking toward your office,” Balakrishnan says. “What happens today is that your phone immediately connects to the Wi-Fi access point with the strongest signal. But by the time it’s finished doing that, you’ve walked on, so the best access point has changed. And that keeps happening.”
By contrast, Balakrishnan explains, the new protocol selects an access point on the basis of the user’s inferred trajectory. “We connect you off the bat to an access point that has this trade-off between how long you’re likely to be connected to it and the throughput you’re going to get,” he says. In their experiments, the MIT researchers found that, with one version of their protocol, a moving cell phone would have to switch transmitters 40 percent less frequently than it would with existing protocols. A variation of the protocol improved throughput by about 30 percent.
Perfect fit
Another of the protocols governs a phone’s selection of bit rate, or the rate at which it sends and receives information. Bit rate needs to be tailored to the bandwidth available: try to send too much data over a weak connection and much of it will be lost; but solving that problem by keeping the bit rate low can end up squandering data capacity.
When a device is in motion, the available bandwidth is constantly fluctuating, so selecting a bit rate becomes more difficult. Because a device using the MIT protocol knows when it’s in motion, it also knows when to be more careful in choosing a bit rate. In the researchers’ experiments, the gains in throughput from bit rate selection varied between 20 percent and 70 percent but consistently hovered around 50 percent.
A third protocol governs the behavior of the wireless base stations rather than the devices that connect to them. Ordinarily, a base station knows that a device has broken contact only after a long enough silence. In the meantime, the base station might try to send the same data to the device over and over, waiting forlornly for acknowledgment and wasting time and power. But with information about the device’s trajectory, the base station can make an educated guess about when it will lose contact.
Since Balakrishnan and Madden are two of the three primary investigators on MIT’s CarTel project, which seeks to use information technology to make driving safer and more efficient, the fourth protocol uses motion data to determine routing procedures for networks of wirelessly connected cars, whose relative positions are constantly changing.
“If you asked me which problems in the paper were the ones where I saw the shortest-term benefit to lots of users,” says Brad Karp, head of the Networks Research Group at University College London’s Computer Science Department, “it’s the automatic bit rate adaptation and, as a second choice, access point selection.” Karp emphasizes that the great advantage of the researchers’ approach is that it relies on hardware that comes standard in most smart phones. He says that other experimental protocols — including one developed by Balakrishnan’s group — offer similar improvements in throughput, but that they generally require more intrusive modification of existing network infrastructure.
Balakrishnan adds that he and his colleagues have identified at least another half-dozen communications protocols that could benefit from information about device movement. “What we are really hoping is that this opens up a really exciting direction for work in the community,” he says. “Other people will come up with more creative ideas, now that you know that you can get these sensor hints in a fairly robust way.”
With the advent of cell phones, however, and even more so with Wi-Fi, the paradigm became a large number of scattered transmitters with limited range. When a user moves out of one transmitter’s range and into another’s, the network has to perform a “handoff.” And as anyone who’s lost a cell-phone call in a moving car or lost a Wi-Fi connection while walking to the bus stop can attest, handoffs don’t always happen as they should.
Most new phones, however, have built-in motion sensors — GPS receivers, accelerometers and, increasingly, gyros. At the Eighth Usenix Symposium on Networked Systems Design and Implementation, which took place in Boston in March, MIT researchers presented a set of new communications protocols that use information about a portable device’s movement to improve handoffs. In experiments on MIT’s campus-wide Wi-Fi network, the researchers discovered that their protocols could often, for users moving around, improve network throughput (the amount of information that devices could send and receive in a given period) by about 50 percent.
The MIT researchers — graduate student Lenin Ravindranath, Professor Hari Balakrishnan, Associate Professor Sam Madden, and postdoctoral associate Calvin Newport, all of the Computer Science and Artificial Intelligence Laboratory — used motion detection to improve four distinct communications protocols. One governs the smart phone’s selection of the nearest transmitter. “Let’s say you get off at the train station and start walking toward your office,” Balakrishnan says. “What happens today is that your phone immediately connects to the Wi-Fi access point with the strongest signal. But by the time it’s finished doing that, you’ve walked on, so the best access point has changed. And that keeps happening.”
By contrast, Balakrishnan explains, the new protocol selects an access point on the basis of the user’s inferred trajectory. “We connect you off the bat to an access point that has this trade-off between how long you’re likely to be connected to it and the throughput you’re going to get,” he says. In their experiments, the MIT researchers found that, with one version of their protocol, a moving cell phone would have to switch transmitters 40 percent less frequently than it would with existing protocols. A variation of the protocol improved throughput by about 30 percent.
Perfect fit
Another of the protocols governs a phone’s selection of bit rate, or the rate at which it sends and receives information. Bit rate needs to be tailored to the bandwidth available: try to send too much data over a weak connection and much of it will be lost; but solving that problem by keeping the bit rate low can end up squandering data capacity.
When a device is in motion, the available bandwidth is constantly fluctuating, so selecting a bit rate becomes more difficult. Because a device using the MIT protocol knows when it’s in motion, it also knows when to be more careful in choosing a bit rate. In the researchers’ experiments, the gains in throughput from bit rate selection varied between 20 percent and 70 percent but consistently hovered around 50 percent.
A third protocol governs the behavior of the wireless base stations rather than the devices that connect to them. Ordinarily, a base station knows that a device has broken contact only after a long enough silence. In the meantime, the base station might try to send the same data to the device over and over, waiting forlornly for acknowledgment and wasting time and power. But with information about the device’s trajectory, the base station can make an educated guess about when it will lose contact.
Since Balakrishnan and Madden are two of the three primary investigators on MIT’s CarTel project, which seeks to use information technology to make driving safer and more efficient, the fourth protocol uses motion data to determine routing procedures for networks of wirelessly connected cars, whose relative positions are constantly changing.
“If you asked me which problems in the paper were the ones where I saw the shortest-term benefit to lots of users,” says Brad Karp, head of the Networks Research Group at University College London’s Computer Science Department, “it’s the automatic bit rate adaptation and, as a second choice, access point selection.” Karp emphasizes that the great advantage of the researchers’ approach is that it relies on hardware that comes standard in most smart phones. He says that other experimental protocols — including one developed by Balakrishnan’s group — offer similar improvements in throughput, but that they generally require more intrusive modification of existing network infrastructure.
Balakrishnan adds that he and his colleagues have identified at least another half-dozen communications protocols that could benefit from information about device movement. “What we are really hoping is that this opens up a really exciting direction for work in the community,” he says. “Other people will come up with more creative ideas, now that you know that you can get these sensor hints in a fairly robust way.”
