Sharing Internet access in networks of cars via WiFi

A new algorithm lets networks of Wi-Fi-connected cars share a few expensive links to the Internet
July 6, 2012

Car WiFi network (credit: Christine Daniloff/MIT)

A new algorithm that would allow Wi-Fi-connected cars to share their Internet connections has been developed by engineers at MIT, Georgetown University, and the National University of Singapore (NUS)

Wi-Fi is coming to our cars. Ford Motor Co. has been equipping cars with Wi-Fi transmitters since 2010. According to an Agence France-Presse story last year, the company expects that by 2015, 80 percent of the cars it sells in North America will have Wi-Fi built in.

The same article cites a host of other manufacturers worldwide that either offer Wi-Fi in some high-end vehicles or belong to standards organizations that are trying to develop recommendations for automotive Wi-Fi.

Two Wi-Fi-equipped cars sitting at a stoplight could in theory exchange information free of charge, but if they wanted to send that information to the Internet, they’d have to use a paid service such as AT&T or Verizon via a 3G or 4G data connection.

Think of it as an extension of the mobile WiFi hotspot (like Verizon’s MiFi), but with users constantly autologging in and out at high speed.

The idea is to aggregate data from hundreds of cars in just a small handful of cars, 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. which cannot be determined in advance. But the new algorithm assigns the aggregators based on the fraction of the fleet that any one car will meet and other factors.

It will be interesting to see what mobile Internet service providers thinks of this idea. And then there are the obvious security questions (mobile packet sniffing, anyone?).

At the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, taking place this month in Portugal, researchers from MIT, Georgetown University ,and the National University of Singapore (NUS) will present the new algorithm.

Tethering at 60 mph: technical details

Alejandro Cornejo, a graduate student in electrical engineering and computer science at MIT and lead author on the paper, 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 — say, 1/x — 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. “We flip a coin for it,” Cornejo says.

Over time, however, “we bias the coin toss,” Cornejo explains. “Cars that have already aggregated a lot will start ‘winning’ more and more, and you get this chain reaction. The more people you meet, the more likely it is that people will feed their data to you.” The shift in probabilities is calculated relative to 1/x — the fraction of the fleet that any one car will meet.

The smaller the value of x, the smaller the number of cars required to aggregate the data from the rest of the fleet. But for realistic assumptions about urban traffic patterns, Cornejo says, 1,000 cars could see their data aggregated by only about five.

Realistically, it’s not a safe assumption that 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.

Weirdly, however, the researchers’ mathematical 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,” Cornejo says. “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.”