Wireless Mesh Networks For IEEE 802.11a/g

Real Wireless Mesh Networks For IEEE 802.11a/g

Short history:
In recent years, I needed to establish my own wireless mesh networks to evaluate one of my novel rate adaptation algorithms. I wanted to use all basic Roofnet components because they provide an efficient and systematic way to develop wireless mesh networks. Roofnet implements the Dynamic Source Routing (DSR) using the Click toolkit. However, the Roofnet project was getting old, implying that the Madwifi driver itself used in their development was out-of-date. So I decided to use a fairly recent version of Madwifi that provides mature features (e.g., virtual interfaces with a single wifi card) for my development of mesh networks. Soon, I realized that there were a lot of changes in the recent Madwifi driver compared to initial versions of it. As the Madwifi driver has evolved, the Click modules also have been even more enhanced. Moreover, the original implementation Roofnet was mainly focused on the IEEE 802.11b. What about 802.11a/g?

An idiosyncrasy of the IEEE 802.11a/g is that the clear channel assessment(CCA) range (also commonly called "physical carrier sensing" range) in the IEEE 802.11a/g PHY is at most the transmission range of data at 6 Mbps, regardless of the actual data rates. In contrast, the CCA range in the IEEE 802.11b PHY is approximately the double size of the transmission range. The same CCA range with the transmission range in the IEEE 802.11a/g causes a significant number of collisions in multihop ad hoc networks.

My strong interest in multirate adaptation schemes for IEEE802.11a/g-based multihop ad hoc networks led me to all these implementation stuff with real fun!!!

My implementations:
My implementation of mesh networks is largely based on the Roofnet project. I'm using the Click infrastructure to use DSR (Dynamic Source Routing) ad hoc routing, as in Roofnet. Since there are sophisticated correlations between the Madwifi driver and the Click modules. I had to modify a recent version of Madwifi so that it can be compatible with Click. Here, "compatible" means that the Madwifi driver is able to recognize RAW packets that are generated by Click, requiring special actions (including rate setup of my interest). I also needed to modify Click modules accordingly (An important connection between Madwifi and Click is based on the file of click/include/clicknet/wifi.h).

Testing:
Basically, I used the Emulab wireless testbed to implement and test all my components.
The environment I'm using for the current package is as follows:

1. Fedora Core 6
2. Linux 2.6.20.6
3. gcc version 4.1.1

Each Emulab wireless node has Netgear WAG311 802.11a/b/g cards that are based on the Atheros chipset (AR5212). I used my own modified version of the Madwifi-0.9.3 IEEE 802.11 driver.

I've successfully added my own multirate adaptation scheme, Reduced Packet Probing (RPP) to the current Click package. My current implementation of RPP scheme shows 20%~50% improvements in TCP throughput on several 3-hop ad hoc paths in the Emulab wireless testbed, compared to the default multirate adaptation scheme in Madwifi, SampleRate.

[1] How To Compile

Download my Madwifi and Click (as mentioned above, you need to have an associated Click package rather than the general Click)

Installation:

 For
click installation,

 $cd /usr/src

 $tar xzvf FC6_jun_click.tar.gz

 $mv FC6_click click

 $cd click

 $./configure --enable-wifi --enable-userlevel  

 $make install

 For Madwifi installation,

 $cd /usr/src

 $tar xzvf FC6_jun_madwifi.tar.gz

 $cd FC6_jun_madwifi

 $make

 $make install

 $cd /usr/src/click/conf/wifi

 $./jun_wifiswitch.pl -d 0 -m
adhoc -p a -c 58 -s sample

 Then, finally you need to setup a click config.

 $cd /usr/src/click/conf/wifi/

 $./gen_config_sample.sh 0 >
! jun_sample.click

 (you can also use other *.sh like gen_config_rppv2.sh)

$click jun_sample.click

[2] New features

Click configuration:

I have
my own click configuration that
removes srcr2 interface for simplicity.

You can find my graph-based click configuration (jun_rppv2.pdf)
which shows a Roofnet Click Configuration with my RPP Multirate
Adaptation Scheme. In this graph, elliptical gray modules annotated
with ":RPP" are nodes that implement RPP while rectangular modules are
original nodes in Roofnet.

New multirate adaptation scheme

In order to implement my RPP scheme, I added two important new click modules: WifiSplit and WifiMerge. These modules are responsible for splitting packets for a given size and merging packets into a single original packet. Since the IEEE 802.11 standards already provide a fragmentation scheme, I used the scheme in my RPP implementation that requires smaller packet transmissions.
If you want to use my RPP scheme, take the following steps.

$./gen_config_rppv2.sh 0 > ! jun_rppv2.click
$click jun_rppv2.click

New click modules added

The current Madwifi provides four different multirate adaptation algorithms. Among them, SampleRate is the default algorithm. I made a corresponding click module of the SampleRate in user-level. The newly created module is based on simple copy-and-paste from the source code in Madwifi. There are more rate-related modules, but I haven't tested yet thoroughly. However, my SampleRate click module presents exactly same behaviors with the Samplerate algorithm in the Madwifi in selecting a rate.

More details on how to add rate decision click modules

In order to analyze packet delivery information on a click module, the click module needs to get all information on how many transmissions have been done for a single packet transmission. For those who are interested in this approach in detail. Here is a short description.

[3] Known bugs and limitations

Known bugs

Rate fixing: Currently, my Madwifi allows users to fix a rate using iwconfig. However, once you fix a rate, you SHOULD ping to any neighbor nodes first using the original interfaces, e.g., ath0 of them, then you can ping safely to the srcr1's IP address of the neighbor nodes. Otherwise, the system will get crashed! This is caused mainly by the Madwifi driver problem regarding virtual interface handling. Although I know what needs to be done, I don't have extra time to resolve this problem now. So just be careful when you use a fixed rate rate. As long as you follow the given instructions, there won't be any serious problem.
Possibly more bugs because I haven't done any torture testing, but it has been stable even for very long experiments. Please, feel free to send emails when you find problems.

Limitations

All click implementation of my scheme is based "user-level click" rather than "kernel-level". Although the wifi-related click modules in kernel-level should be compatible with a specific Linux kernel, I found that some of kernel-level wifi click modules didn't work properly. Not only this problem, I had reasons for pursuing user-level click modules in developing my multirate algorithms. For anyone who is interested in this, here is my simple discussion.
My work is in progress. Some of relevant documentations in my source code may be incorrect. I will clean up them soon. Not only that, there is some temporary (or even garbage) code that I have to exclude eventually.