Information-theoretic bounds for mobile ad hoc networks routing protocols

Information-theoretic bounds for mobile ad hoc networks routing protocols, Nianjun Zhou, Alhussein Abouzeid, Lecture Notes in Computer Science: Information Networking, vol. 2662, pp. 651-61, October 2003.

This paper is a bit frustrating. I am still looking around how much information to store for routing in ad hoc network (I guess the trilogy of posts below is not over). Anyhow, I found a version of this paper, which is probably a pre-draft or the submitted version, or whatnot, but not the final version (which is being a paying wall at Springer).

So it is not as polished as I'd like to fully enjoy the paper. For instance, it computes some lower bounds on the amount of information required to keep a proactive routing protocol updated. It is fine, but it should be explained: why is a lower bound enough? What good does it do to us?

First, the argument is combinatorial, and based on dividing the network into relays and regular nodes. The number of information is computed based on how many nodes are required to divide the nodes in different groups,and for each group, how to elect a leader.

But it is a lower bound, so it does not tell you the amount of information that is indeed required. It does not say how tight the bound is. So it says: well, at least you need this much, which at least tells you that the performance is as least as good as with the bound. So the bound can be used to tell you the best case performance, but the version I have does not make the point. For instance, if the bounds gives a bad performance, then the system will be worst, so it might be useful to know.

It makes, on the other hand, comparisons between two lower bounds: "Clearly, a large amount of saving is achieved with prediction". But that is not true: the difference in the bounds is meaningful only if the actual quantity is close to the bound. Here we don't know. It is most likely true that prediction saves a lot, but you cannot deduct this by the bounds. If I give 0 as a lower bound of the predictive case, then my amount of saving increases even more, but I did not get a better result!

Anyhow, the combinatorial method is interesting, and the bound could be useful, if used in the right context.