Friday, March 16, 2007

A Topology Control Approach to Using Directional Antennas in Wireless Mesh Networks

A Topology Control Approach to Using Directional Antennas in Wireless Mesh Networks, Umesh Kumar, Himanshu Gupta, Samir Das, in Proc. of IEEE International Conference on Communications (ICC), 2006.

I read the paper as it was referenced in some other paper, and I have to say: I am shocked to discover it is an ICC paper. I attended ICC'06, I even presented a paper there, and this paper is much better than anything I have seen there at the time (including my own stuff, to which I am very partial). This paper is very cute.

The idea is simple: what if you assume that you want to make a network using directional antennas but you don't want to get into writing new MACs (which is a hard thing to do) but just want to use legacy off-the-shelf hardware? This paper presents a way to orient the antennas so as to cover not the whole area around the nodes, but only a fraction, so as to minimize interference.

The key is to pick the number of antennas and their orientation so as to keep the network connected (in the last resort, use a few omni-directional antennas). The algorithm to select which nodes to pick is a spanning tree building algorithm, but its application in this context is really cute and smart. The paper gives up on the total connectivity (some links might be unavailable here that would be in an omni-directional context) but the reduction of the interference more than makes up for it. Namely, pick k antenna with total covered angle k \theta, where k \theta is strictly less than 360 degrees.

This is very practical too, as most mesh network deployment don't really care for the maximal connectivity, but only care to find a good path to the internet gateway. So this is an elegant and economical solution.

The funny thing is that, despite reducing the number of paths in the network (more exactly, by putting a ceiling on the degree of the nodes), the shortest path is shorter here than for the omni-directional shortest path, due to the longer transmission range of the narrow beam antennas. Also, the PDR really kicks ass over the omni-directional set-up. The results are so impressive that really, this should have been an Infocom paper, not an ICC. I even checked for Turkish names in the author list as an explanation why they submitted to a conference in Istanbul.

No comments: