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.
All due respect
The crucial feature of the series is that the smaller the number, the more frequently it occurs; but over long enough spans of time, higher numbers will occur at least once. If the smallness of a number represents its priority — jackknifed trucks are 0, bad potholes are, say, 8 — then using the binary carry sequence to order data transmissions will ensure that high-priority data is broadcast more frequently, but not to the exclusion of low-priority data. Newport and Cornejo were able to mathematically prove that using the binary carry sequence optimizes the diffusion of information throughout the network.
T. J. Giuli, the technical expert on mobile computing at Ford Research and Advanced Engineering who’s testing Newport and Cornejo’s algorithm, says that disseminating data through networks of cars will be particularly useful in urban areas. The alternative, he explains, would be to download traffic data over the cellular network, as anyone with an iPhone might do today. “If more people are associated with the same cell base station, you kind of have to split the bandwidth among more and more people, so your effective bandwidth decreases,” Giuli says. With a network of wirelessly connected vehicles, on the other hand, “as the density of mobile-networking consumers increases, the bandwidth also increases.” At the same time, however, Giuli says that networked vehicles could also help propagate traffic information in rural areas where cell towers — and, for that matter, hovering helicopters and DOT sensors — are sparse.
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.
All due respect
The crucial feature of the series is that the smaller the number, the more frequently it occurs; but over long enough spans of time, higher numbers will occur at least once. If the smallness of a number represents its priority — jackknifed trucks are 0, bad potholes are, say, 8 — then using the binary carry sequence to order data transmissions will ensure that high-priority data is broadcast more frequently, but not to the exclusion of low-priority data. Newport and Cornejo were able to mathematically prove that using the binary carry sequence optimizes the diffusion of information throughout the network.
T. J. Giuli, the technical expert on mobile computing at Ford Research and Advanced Engineering who’s testing Newport and Cornejo’s algorithm, says that disseminating data through networks of cars will be particularly useful in urban areas. The alternative, he explains, would be to download traffic data over the cellular network, as anyone with an iPhone might do today. “If more people are associated with the same cell base station, you kind of have to split the bandwidth among more and more people, so your effective bandwidth decreases,” Giuli says. With a network of wirelessly connected vehicles, on the other hand, “as the density of mobile-networking consumers increases, the bandwidth also increases.” At the same time, however, Giuli says that networked vehicles could also help propagate traffic information in rural areas where cell towers — and, for that matter, hovering helicopters and DOT sensors — are sparse.
