The Math Behind Prioritizing

When it comes to communication, there’s urgent and there’s everything else. When we listen to a lecture or read a textbook, we take notes. We don’t need to record every detail to get the important stuff. When we tell a friend about a movie, we don’t spend an entire 90 minutes recounting it; some details just don’t matter.

The problem is that machines aren’t very good at prioritizing information on their own. When it comes to things like communicating traffic conditions over a wireless network between cars, a major accident blocking all lanes isn’t more important than a temporarily reduced speed limit to the computer sending the information.

Fortunately, A team of MIT researchers called CarTel has provided a geek and chic solution to the problem; enter the binary carry sequence. For those interested in the math behind the magic, here are the basics. Feel free to skip the following details; you’ll still get the general idea :

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.

The important thing for prioritizing information is that the lower the number assigned to a piece of information, the more often it gets transmitted. For example, priority 0 information gets sent every other time; priority 1 is sent every three times, and so on.

Why is this important for using cars as traffic sensors? Well, conventional ways of solving the problem have assumed that all connections between any two cars are equally valuable. In real life, this would mean that the guy (car A) who’s been in front of you for the past 10 miles would get the same information transmitted in the same order as the guy (car B) that was within range for 2 seconds as he passed you going in the other direction.

If all information were equally urgent, this would be fine, but suppose you got to tell car B about the slow-moving bus he’s about to encounter, but not the speed trap  that could cost him hundreds of dollars? Fortunately, using the binary carry algorithm the most important stuff would get sent over and over, leaving the “nice-to-know” stuff for times when you’re stuck at a light next to each other.

Geeky? Sure. A beautiful and elegant solution for getting the right information out in time? Absolutely. The method is sure to see use in other areas. For now, though, Ford is testing the algorithm for possible use in its future cars. Take a look at the original article about using cars as traffic sensors from MIT.