FOR ALL SELF-DRIVING CAR NEWS CLICK HERE
Cars as traffic sensors
A new algorithm optimizes the dissemination of information about traffic and road conditions through networks of wirelessly connected cars.
Data about road and traffic conditions can come from radio stations’ helicopters, the Department of Transportation’s roadside sensors, or even, these days, updates from ordinary people with cell phones. But all of these approaches have limitations: Helicopters are costly to deploy and can observe only so many roads at once, and it could take a while for the effects of congestion to spread far enough that a road sensor will detect them.
MIT’s CarTel project is investigating how cars themselves could be used as ubiquitous, highly reliable mobile sensors. At the Association for Computing Machinery’s sixth annual Workshop on Foundations of Mobile Computing on Sept. 16, members of the CarTel team presented a new algorithm that would optimize the dissemination of data through a network of cars with wireless connections. Researchers at Ford are already testing the new algorithm for possible inclusion in future versions of Sync, the in-car communications and entertainment system developed by Ford and Microsoft.
For the last four years, CarTel, which is led by computer-science professor Hari Balakrishnan and associate professor Sam Madden, has been collecting data about the driving patterns of Boston-area taxicabs equipped with GPS receivers. On the basis of those data, the CarTel researchers have been developing algorithms for the collection and dissemination of information about the roadways. Once the algorithms have been evaluated and refined, the CarTel researchers plan to test them in an additional, real-world experiment involving networked vehicles. The new algorithm is among those that the group expects to test.
Ends at odds
Calvin Newport, a postdoc in Balakrishnan’s group, who developed the new algorithm together with Alejandro Cornejo, a grad student in Nancy Lynch’s Theory of Distributed Systems Group, says that previous work on diffusing information through networks of cars tended to assume that, over time, the network would always provide a sequence of connections that could relay data from any one car to any other. The problem is that the CarTel experiment suggests that that isn’t the case. On the other hand, it also demonstrates that two cars that do come within wireless-transmission range of each other will frequently remain near each other for long stretches of time — repeatedly hitting the same lights on the same stretch of road, for instance.
A good information-dissemination algorithm should thus ensure that two cars passing each other in opposite directions, with only a fleeting wireless connection, will exchange high-priority data — say, that a tractor trailer has jackknifed across three lanes of traffic on the nearby interstate. On the other hand, it should also ensure that two cars stuck at a light together, with plenty of time on their hands, exchange lower-priority data as well — like the location of a particularly nasty pothole.
Newport and Cornejo determined that the best way to meet both requirements was to take advantage of a sequence of numbers known as the binary carry sequence. Technically, each number in the binary carry sequence is the exponent of the highest power of two that will evenly divide the corresponding integer (where “evenly divide” means without a remainder). The integer 1, for instance, can be evenly divided by two to the zero power, or 1, while 2 can be evenly divided by two to the first power, or 2. But three can’t be evenly divided by either 2 or 4, so it, like 1, is divisible only by two to the zero power. The first three digits of the sequence are thus 0, 1, 0. The next nine, as it happens, are 2, 0, 1, 0, 3, 0, 1, 0, 2.
READ MORE
RSS Feed