July 7, 2012
Algorithm Helps Network Cars With Wi-Fi
Lee Rannals for redOrbit.com - Your Universe Online
Before the future has even had a chance to play out, researchers are already trying to improve Wi-Fi in cars.Several companies are starting to incorporate W-Fi in their new vehicles, and Ford Motor Co. expects that by 2015, 80 percent of the cars it sells in North America will have Wi-Fi built in, according to an Agence France-Presse article.
Owners of Wi-Fi-equipped vehicles would need to pay for an Internet connection in order to surf the web. However, a team of scientists have developed an algorithm that could save passengers a little money.
Researchers from MIT, Georgetown University and the National University of Singapore have created a method for cars to share an Internet connection, similar to how computers at a home share a connection through their router.
“In this setting, we´re assuming that Wi-Fi is cheap, but 3G is expensive,” said Alejandro Cornejo, a graduate student in electrical engineering and computer science at MIT and lead author on the paper.
The problem between finding cars that have hot spots is that a network of cars is constantly changing in unpredictable ways, which is different than having a router with multiple computers at home. So, the researchers began to consider the case in which every car in a fleet of cars will reliably come into contact with a fraction of the rest of the fleet in a fixed period of time.
Under the researchers' algorithm, when two cars draw within range of each other, only one of them conveys data to the other, and the selection of the transmitter and receiver is random. However, Cornejo says they created a bias coin toss for it.
"Cars that have already aggregated a lot will start ℠winning´ more and more, and you get this chain reaction," Cornejo said. "The more people you meet, the more likely it is that people will feed their data to you."
The shift in probabilities of cars is calculated relative to 1/x, which is the fraction of the fleet that any one car will meet.
The smaller the value of x means the smaller the number of cars required to aggregate the data from the rest of the fleet. Cornejo said that for a realistic assumption, 1,000 cars could see their data aggregated by only five.
Realistically, it is not safe to assume that every car will come into contact with a consistent fraction of the others. However, the researchers were able to show that if the network of cars can be envisioned as a series of dense clusters, the algorithm still works well.
The team's 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 said. “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.”
“In general, the ability to have cheap computers and cheap sensors means that we can generate a huge amount of data about our environment,” John Heidemann, a research professor at the University of Southern California´s Information Sciences Institute, said. “Unfortunately, what´s not cheap is communications.”
He said the real advantage of aggregation is that it enables the removal of redundancies in data collected by different sources. He believes that networks of vehicles could partake of those advantages as well.
“If you were trying to analyze vehicle traffic, there´s probably 10,000 cars on the Los Angeles Freeway that know that there´s a traffic jam. You don´t need every one of them to tell you that,” he said.
The team will present their paper about the algorithm at the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing this month in Portugal.