D-07S-05

If you read this and find something strange, then please go on and either edit or leave a comment.

About

Working title: Using wireless mesh networks for Early Warning Systems

Assigned to: Jens Nachtigall

Advisor: Kai Köhne

Expected Submission: December 2007

Motivation (Aufhänger)

In computer networking it is always disirable to minimize latency and increase throughput. This is especially the case for Early Warning Systems that need real-time communication (which reactive source routing protocols cannot achieve due to the latency added by on-demand route discovery), whereas increasing the network's goodput is important for sensor data retrieval (e.g. MiniSeed).

There are several ways to achieve this. But since the EDIM and SAFER prototypes will based on two-radio-802.11 nodes (WRAPBoards), it is an interesting and challenging task to increase the network's goodput and responsiveness by using non-overlapping channels for the two radios on each node.

Problem Statement

802.11b offers three non-overlapping channels and 802.11a even twelve. However, with the 802.11 MAC layer these are not utilisised. Rather, the wireless mesh network is usually on one common channel (or sometimes manually partioned into several channel collision domains). This only allows for one transmission whithin an interference range, which is about twice or three times as big as the communication range.

The idea is to split the collision domain and therefore allow several simultanous transmissions in a neighbourhood by setting the multiple radios to different non-overlapping channels. Also by using two radios on one node we can receive and send data simultanously (xxx: Does this decrease latency / and break with "goodput is reduced by halve at each hop" rule of thumb, or doesn't it due to store-and-forward?) This should be done using commercial off-the-shelf hardware, where we do have no or a very limited access to the MAC layer.

Related work

Other solutions/approaches and their weaknesses (and strengths)

Multichannel MAC layer

There are several proposals on how to change the standard 802.11 MAC layer to support multi-channel networks.

See MultiChannelMAC tag on citeulike

Weaknesses

While this might be the best approach in theory my idea is to use cheap COTS hardware. These are equipped with the standard 802.11 MAC layer. The manufacturer usually does only allow some finegrained adjustments to MAC layer settings like RTS/CTS threshold. However, radical changes to the MAC are not allowed either due to FCC regulations or commercial reasons (closed source).

Moreover most (xxx: which?) proposals of these multi-channel MAC layers operate on a packet-by-packet basis or do at least switch the channel very often. However, todays commodity 802.11 interfaces have a too long channel switching times to make this solution feasable (xxx: source?).

One common control channel

The Idea is to assign one radio statically to one known channel. This channel is for control information only. The other radios are assigned and re-assigned from time to time, and are used as data only channels.

See ControlChannel tag on citeulike

Weaknesses

The problem is that we need to one dedicated control channel: We either waste capacity in case the data channels of the other radios are fully utilized (mainly if there are only a few additional data radios), or the dedicated control channel becomes the bottleneck (mainly if there are many additional radios on the node).

My solution/approach (WiP)

An image says more then 1000 words

At the beginning we have such a situation: All kind of nodes with and without several interfaces. The question is how to arrange such a setting in a distributed way so that latency is low and throughput high.

One possible arrangement (not the best) could be this. This has to assigned based on the view each node has. And the layout has to be rearragned as nodes join, move and leave the mesh network or the channel quality changes (maybe measured by ETX).

Challenge

To divide the collision domain one has to set the nodes' radios to different channels. However, this also means that nodes become deaf towards other nodes. Different channel assignements can lead to different network topologies. In the worst case (if one, for instance, simply assigns the least used channel to an interface) the network topology changes that way that nodes cannot communicate with each other anymore. The challenge is to find the right mixture between splitting the collision domain using different channels while avoiding disconnections between parts of the net. Also one has to avoid too frequent channel assignments and take care of channel assignment and route flappings.

Ideas (brainstorming)

• other concepts do not consider the actual channel quality (e.g. the hyacinth project uses raw channel capacity divided by load and interference): we must have some measurements of the link quality amonst different channels (consider other interference in ISM band / using something like ETX?)
• do not require a fixed number (in other works often 2) of radios. Rather, also single radio nodes, i.e. utilise multiple radios (channels) whenever possible whithout requiring a node to have several radios
• both radios are used for data and control (routing) messages, no need to reserve one radio for control messages only
• admin might be allowed to set some of his radios to a fixed channel (because she has superior knowledge of the surrounding / due to some requirements)
• proactive protocols have a "world view" of the network. This is nice because routes to nodes do not have to be discovered on demand prior to sending data (which is slow). Also, a proactive routing protocol could also not only flood link state information but also other information every node with a certain hop distance (adjustable by TTL) should know. An approach could be to piggyback channel assignment information with the HELLO or TOPOLOGY CONTROL (link state) messages (e.g. by extending http://olsr.org). These information could be the ingredients to a distributed channel assign algorithm
• channel assigment algorithm takes into account joining/leaving/movement of nodes
• require only system level software (user space should be fine), switching channels can be done every x secs using libiw/iwconfig/proprietary tool, no changes to 802.11 MAC
• 2 (or more) single radio nodes can be connected by a short ethernet cable to form a "virtual multi-radio node" (xxx: how do we exclude tunnels or very long ethernet cables?)
• most traffic is gateway to nodes. So the most loaded links are those near to the gateway nodes (or a special purpose server in the mesh). So if the gateway nodes are the root of a tree, one needs to form a fat tree in terms of how much interference is allowed (higher priority to links nearer to the root/gateway).

Deliverables

• Distributed channel assignment algorithm
• based on a proactive routing protocol (allows world view, but maybe partly view is sufficient)
• implementation and tests

Project excecution plan

What's next (TODO)

• [07/2007] getting an overview / reading papers
• state own approach more precisely