Robust Geo-Routing on Embeddings of Dynamic Wireless Networks

Robust Geo-Routing on Embeddings of Dynamic Wireless Networks, Dominique Tschopp, Suhas Diggavi, Matthias Grossglauser, Jörg Widmer, in Proc. of IEEE Infocom 2007, Anchorage, May 2007.

This (and if I get to it, the next few posts) is a paper whose Infocom talk I attended, and I made a note to get to the paper and read it. I have to say that the subject of embeddings of virtual coordinates to allow for routing in ad hoc networks is a much more traveled area than I would have suspected.

The idea of the paper is to build some embedding based on the distance of a few beacons and the graph distance between a node and the beacon. Basically, if I get it right, the nodes receive some beacons with a hop count h and a position p for the sender of the beacon. It infers a virtual position based on h and p. The embedding has a higher dimensionality (even though beacons are in the plane). The beaconing is probabilistic, as the system is dynamic and getting a random beacon from the set of beacon nodes evens out the chance that some beacons gets in a degenerated situation. The virtual coordinates are averaged over a local neighborhood to ensure consistency.

Based on the embedding, one can perform geographic routing on the virtual coordinates. The proposed algorithm is described and evaluated through simulation (no analysis, which looks like it would be extremely complex). The performance of the proposed Probabilistic Beaconing (PB) is much better than all the stuff they compare it with (mostly Beacon Vector Routing, NoGeo and greedy routing on the real coordinates).

Paper is not that easy to read, I have to admit. I blame the 9p limit, which forces authors to condense their stuff beyond readability.