New algorithm to allow Wi-Fi connected cars to share Internet connections
05 July 2012
At the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing this month in Portugal, researchers from MIT, Georgetown University and the National University of Singapore (NUS) will present a new algorithm that would allow Wi-Fi-connected cars to share their Internet connections.
In this setting, we’re assuming that Wi-Fi is cheap, but 3G is expensive.
—Alejandro Cornejo, lead author on the paper
The general approach behind the algorithm is to aggregate data from hundreds of cars in just a small handful, which then upload it to the Internet. The problem, of course, is that the layout of a network of cars is constantly changing in unpredictable ways. Ideally, the aggregators would be those cars that come into contact with the largest number of other cars, but they can’t be identified in advance.
| “In general, the ability to have cheap computers and cheap sensors means that we can generate a huge amount of data about our environment. Unfortunately, what’s not cheap is communications.” —Prof. John Heidemann, Univ. of Southern California Information Sciences Institute |
Cornejo, Georgetown’s Calvin Newport and NUS’s Seth Gilbert—all three of whom did or are doing their doctoral work in Nancy Lynch’s group at MIT’s Computer Science and Artificial Intelligence Laboratory—began by considering the case in which every car in a fleet of cars will reliably come into contact with some fraction of the rest of the fleet in a fixed period of time. In the researchers’ scheme, when two cars draw within range of each other, only one of them conveys data to the other; the selection of transmitter and receiver is random.
Over time, however, cars that have already aggregated a lot will increasingly “win the coin toss”. The shift in probabilities is calculated relative to the fraction of the fleet that any one car will meet.
For realistic assumptions about urban traffic patterns, Cornejo says, 1,000 cars could see their data aggregated by only about five.
Not every car will come in contact with a consistent fraction of the others: A given car might end up collecting some other cars’ data and then disappearing into a private garage. But the researchers were able to show that, if the network of cars can be envisioned as a series of dense clusters with only sparse connections between them, the algorithm will still work well.
However, analysis shows that if the network is a series of dense clusters with slightly more connections between them, aggregation is impossible.
There’s this paradox of connectivity where if you have these isolated clusters, which are well-connected, then we can guarantee that there will be aggregation in the clusters. But if the clusters are well connected, but they’re not isolated, then we can show that it’s impossible to aggregate. It’s not only our algorithm that fails; you can’t do it.
—Alejandro Cornejo
Comments