On mitigating the broadcast storm problem with directional antennas

On mitigating the broadcast storm problem with directional antennas, Chunyu Hu, Yifei Hong, Jennifer Hou, IEEE International Conference on Communications, 2003. ICC'03. Vol. 1, Issue , 11-15 May 2003 Page(s): 104 - 110.

This is a short, breezy read. It considers three schemes to reduce the broadcast storm problem: one is to not rebroadcast on the sector which receives the packet to be broadcast; the second is to identify some relay nodes in each sector and to have these rebroadcast, hoping that these relays are enough to cover all the nodes; the third is to pick the relay which maximizes the new coverage. This means that the scheme retransmits first in the sector for which there is a node which covers the most new ground (ie. its own coverage area minus the area covered by forwarding the broadcast to this node in this sector).

The three schemes are intuitively sounds, and bring some performance benefits when evaluated through QualNet simulations. J. Hou is principal investigator for J-Sim, a simulation environment to perform this kind of evaluation, I guess qualnet was not the perfect tool then (for one thing, it is a commercial tool, whereas JSim is freely available).

Inconsequential details: this paper is written using word, which makes the equations look funky. And there is a little mix-up: "This is termed as the broadcast storm in [20]" in the abstract, and "This is termed as the broadcast storm in [7]" in the intro. The abstract is correct.

Opportunities and Challenges in Mesh Networks Using Directional Anntenas

Opportunities and Challenges in Mesh Networks Using Directional Anntenas, Gupqing Li, Lily Yang, W. Steven Conner, Bahar Sadeghi, in Proc. of WiMesh 2005, Santa Clara, Sept. 2005.

This is an interesting survey. I am now debating whether or not I should attend/participate in conferences, since I attended this workshop. I even chaired a session. Yet, I have no recollection of this paper, despite the fact that it is actually a good and interesting survey of the use of directional antennas in mesh networks. [In my defense, I was tutorial chair of the conference associated with the workshop, IEEE SECON, and kinko's was supposed to have made the tutorial hand-out the Saturday before, which they failed to do. They said it would be ready at 6am on the Monday morning of the tutorials/WiMesh workshop, but it was not ready when I showed up: the binding machine had broken down. I had to pick up whatever they had printed out --which they wanted me to pay full price for it, despite it being useless!!!--, go down to Santa Clara to another kinko's where they did the binding just in time for the 9am tutorial start. At that point, I was rather frazzled. I hate kinko's].

It does a good job at presenting the most salient issues, providing the key reference, and giving accessible definitions and insights into the concepts. This is a good place to start if interested about directional antennas in mesh networks, a fact that I realize only after getting deep into the literature. My fault: with such a title, I should have put it on top of the pile.

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.

Ad Hoc Routing Using Directional Antennas

Ad Hoc Routing Using Directional Antennas, Romit Roy Choudhury, Nitin Vaidya. Technical Report.

I believe this technical paper is an early version of Performance of Ad Hoc Routing using Directional Antennas, Romit Roy Choudhury, Nitin Vaidya, Journal of Ad Hoc Networks - Elsevier Publishers, November, 2004. At least the ideas and most of the content seems similar enough that I will only read the tech report, not the journal paper.

Like the previous paper I wrote about (just below), this one modifies the MAC protocol to support directional antennas, by having omni-directional listening, and directional transmitting of CTS and RTS. It also considers the impact of the directional antenna on routing, namely the DSR protocol, and how to improve DSR to support directional antennas.

The key insight is that: directional antennas improve the performance a lot when the network is random and sparse, and when the directional transmission range is significantly longer than the omni transmission range. Basically, there is a great gain when the transmission beam is narrow and focused. In other set ups, the paper does not find a great gain from directional antenna, a rather counter-intuitive result.

The paper is mostly a performance evaluation using qualnet simulation. Also, the paper takes into account the sweeping time, ie. the delay in broadcast (for DSR) incurred by transmitting the broadcast packet sequentially over the different sector (ie. sweeping) over an omni-directional broadcast to all neighbors at the same time.

An interesting idea to reduce the sweeping time is to broadcast not to all neighbors, but only to those in a few sector opposite from the one receiving sector of the broadcast. I'm curious to see whether this would not yield to route requests which miss the destination (however, it is hard to miss it, since the neighbors of the destination are as good as the destination, and since many RREQs are redundant anyway).

Medium Access Control Protocols Using Directional Antennas in Ad Hoc Networks

Medium Access Control Protocols Using Directional Antennas in Ad Hoc Networks, Young-Bae Ko, Vinaychandra Shankarkumar, and Nitin Vaidya, in Proc. of IEEE Infocom 2000.

The second reviewer had me wondering if I usually write the full name or only the first initial. If you read the paper, see how his (her?) email handle is much more convenient.

The paper is a look into how to modify the 802.11 protocol to support directional antenna. Basically, due to deafness and blind terminal issues, you still need to send omni-directional control packets, but in some situation, you should send some that are directional, using only on antenna sector to transmit. First: you should always use directional antenna for the transmission. The paper details two schemes to use directional control messages.

The paper is relatively simple in its insights, but that's what you get for blazing a new trail, you have to get the low hanging fruits first. The directional MACs proposed in the paper (reasonably) assume that the location (in terms of which sector is best to use to transmit/receive to them) of the neighbors is known.

The two schemes are: 1-using directional RTS (so that you don't block nodes away from where you are transmitting); 2-using both ORTS and DRTS depending on the current status of the corresponding sector.

The performance evaluation is rather basic, using a 5x5 grid with some simple scenarios. I would have enjoyed a more realistic set-up. For instance, directional antenna performance is different on a grid, because nodes line up within a sector, so it artificially increase the interference. Also, I don't know if the baseline comparison is directional for 802.11 or not. It looks like what is being compared is:
-basic 802.11 with omni-directional antenna; and -proposed MAC with directional antenna. That is 2 parameters here (basic 802.11 vs proposed MAC, and omni vs. directional) in the simulation, while the results are used to quantify and discuss the impact of only the second parameter.

The interference level in the network for bare 802.11 would significantly decrease when using directional antenna without modifying the MAC, thus improving the performance. I don't see this explicit here. It would have been nice to quantify the impact of pure directional antennas, as there is an area of space where the interference of an on-going connection is strong enough to disturb another connection attempt nearby, but not strong enough for the nodes to successfully decode the MAC packets and update the NAV tables. For those, using a basic 802.11 with directional antennas and appropriate power control would go a long way improving performance.

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.

Predictive Caching Srategy for On-Demand Routing Protocols in Wireless Ad Hoc Networks

Predictive Caching Srategy for On-Demand Routing Protocols in Wireless Ad Hoc Networks Wenjing Lou and Yuguang Fang, in Wireless Networks 8, 671-79, 2002, Kluwer.

This to complete the 3 part series on caching (see two post below). It is a paper which suggests to use an adaptive value for the route time out based on the observed lifetime of the route. Updating the lifetime of the route allows for a finer granularity of the caching, and for better performance. It is light and easy reading, and the technical contribution is pretty simple. There is some performance analysis. I found it cited in some other paper, and the reference list inside has sent me looking for some other older papers I was not aware of (especially in the proactive vs. reactive discussion).

Caching Strategies in On-Demand Routing Protocols for Wireless Ad Hoc Ne

Caching Strategies in On-Demand Routing Protocols for Wireless Ad Hoc Networks, Yih-Chun Hu, David B. Johnson, in MOBICOM 2000, Boston, MA, pp. 231-42.

This paper proves that analytical modeling in ad-hoc network research is way overrated: there is not a single complicated mathematical equation. Even the study of correlation between different metrics seems to be done by observation rather than using sophisticated statistical tools. Yet, the paper does present a pretty compelling picture of different cache strategies. And rather than struggling to define an analytical model and then show it is valid, it cuts the middle-man and shows right away the impact of different parameters using extensive simulation.

The simulation is of course the main part: it is the CMU extension of the NS-2 simulator, which was designed by the group of this paper, and which was designed to produce results like this one. It is still the de facto standard for wireless mesh network simulation (it has been integrated in NS-2 distribution now) so this is as much part of the legacy of this group as the actual results presented in the paper.

The cache strategies studied are: unlimited cache size, or finite cache size with different sizes, or different ways of caching depending on who issues the node, or different ways of updating the cache (FIFO or not).

The paper finds a better value of the active time-out of the cached routes (the previous paper below would tell you it is velocity dependent, but here they seem to agree on a 5s value for most mobility models). It also shows that the larger cache study is not necessarily good, as it means more broken routes are being carried around, which leads to suboptimal performance.

I enjoyed the "omniscient expiration" concept (the strategy which keeps the route as long as it is valid), and will use it in a future paper.

The link to the monarch project: here.

Optimizing Route-Cache Lifetime in Ad Hoc Network.

Optimizing Route-Cache Lifetime in Ad Hoc Network, Ben Liang, Zygmunt Haas, IEEE Infocom 2003.

This paper deals with building a mathematical framework to analyze the performance of ad hoc network and the effectiveness of route cache. The mathematical framework is straightforward probabilistic analysis (same tools as queueing theory, I'd say), trying to find the residual lifetime of a link (or, rather, the Laplace transform of the distribution thereof) as well, then computing the probability that the link is still up, and thus that the cost (in terms of delay) of the route discovery process is nil, the probability that the link has timed out (therefore: cost=route discovery overhead) or the probability that the cost is that of using an entry corresponding to a broken link (cost=route repair).

The analytical result involves solving some polynomial equations and inverting the Laplace transform. A closed form expression is given for the case where the arrival process and the link breakage process are memoryless (both reasonable assumption, actually).

The result shows that the optimal route time-out is independent of the packet arrival process (which is actually quite obvious when you think about it: you should keep the route as long as the network topology is valid, which is independent of the packet arrivals).

The not-technical note: Ben Liang was TPC program co-chair for IEEE MASS'06. I believe that Ben's advisor and co-author here, Zygmunt Haas was TPC chair, with Jennifer Hou, if my memory is correct. Ben is now a faculty at UToronto, and as publication chair for the conference, I ended up interacting with him quite a bit. We actually got quite a few new features implemented in EDAS to support our needs (e-copyrights, or a way to export data to fit the proceedings CD processing company requirements, thanks to Henning's willingness and responsiveness). I feel I should have known about this paper then.