ftw!

¶ motor vehicle based routing Posted 21 years, 7 months ago on May 18, 2004
Sometime in the not too distant future, I predict that cars will come standard with some sort of short range (<100 meters) wireless communication device. Embedding such a device into vehicles would open up a whole new class of communication opportunities and problems to be solved. Let's engage in a bit of mental masturbation and imagine what we might do.

First, assume that every vehicle has some sort of globally unique identifier, like a MAC address and RSA public/private key. Second, assume that every vehicle has some way of rougly determining its geographic location (e.g. GPS coordinates).

We can model the system as an undirected graph, where each vehicle is a node and edges join vehicles that are in direct communications range with each other. Let N denote the set of all nodes/vehicles, and E denote the set of all edges. Furthermore, each vehicle has some attributes like location, destination, and velocity.

Here are a couple interesting problems that we might be able to solve.

Given this system, is it possible to efficiently route a message from an arbitrary vehicle v₁ to another vehicle v₂? In other words, if I'm driving my subaru impreza (v₁) somewhere in boston, and sonic is driving his bmw z3 (v₂) out in santa barbara, and there exists a path from v₁ to v₂, can I mock sonic's mom by routing a message solely through other vehicles?
Given this system, is it possible to collect and distribute traffic information such that vehicles can issue queries about the status of traffic in a certain area? If I'm driving from boston to providence and I-93S is closed because some semi jack-knifed and cars are backed up for miles, can my car automatically warn me and find a better route?

Academically, question #1 is more interesting. That's hard core mobile routing, but traditional mobile routing algorithms like DSR and DSDV don't scale well enough to be practical. I wonder if you could use distributed hash tables. Presumably, if you knew where the recipient is, you could take advantage of geographic information and route based on location. Something like broadcast to a geographic radius. If you had no idea where the recipient is, though, I'm stumped.

You might ask, why bother with #1? If I have a cell phone and sonic has a cell phone, why not just make a damn phone call? The main benefit is decentralization. Bam, you've just taken out the middleman and I no longer need to pay x cents a minute to talk to sonic. Of course, the latency will probably never be good enough for audio, but we can always hope.

Question #2 isn't as technically interesting, but is probably more useful. Not technically interesting because it's basically a special case of #1. The basic assumption is that a vehicle has some idea of the traffic level in its location, and can transmit that information. An inquiring vehicle need only transmit a message to any vehicle in the location of interest, and a query/response can be established.

No comments, be the first!

Comments disabled until the spammers go away. I hope you comment spammers all die horrible deaths and are forced to delete endless streams of comment spam in your days in purgatory.