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. For instance, one can adjust the transmission power (on which wireless connectivity, interference range and link quality depend), the frequency channel selection; or fine-grain how paths are chosen by the routing mechanism. There are many algorithm for an automatic selection of the best path between two communicating nodes (i.e. routing), but channel selection is mainly still done manually. The EDIM and SAFER prototypes will be based on two-radio-802.11 nodes (WRAPBoards). Therefore, it is an interesting and challenging task to look for ways on how to use non-overlapping channels for the two radios on each node to increase the network's goodput and responsiveness.

Problem Statement

802.11b offers three non-overlapping channels and 802.11a even twelve. However, the 802.11 MAC layer does not utilisise them. 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 due to contention for the shared wireless channel. The interference range 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 / Does this break with the "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

I manage my literature on citeulike. So summeries and notes on referenced work can be found there.

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? http://www.citeulike.org/user/nachtigall/article/361101).

Adjusting transmission power

One can also change the transmission power at each node to control the connectivity between nodes (and therefore topology) as well as the interference range.

See TransmissionPower tag on citeulike

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 have one extra radio for a 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).

Assumptions

• all nodes are static, i.e. no mobility, but the addition and failure of nodes might occur
• the network layout is setup for long term
• all nodes have 2 wireless radios
• all nodes have the exact time (needed anyway for sensors, via GPS)
• at least 3 (802.11b) orthogonal channels
• knows its position via GPS (is this really always the case?)

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 (channel diversity) while avoiding disconnections between parts of the net (node connectivity). 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?)
• interference can be classified as inter-flow (within own path), intra-flow interference (other path) (after Tang et al.), but there is also interference from external sources (ISM)
• 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 (e.g. clients per dhcp on that channel))
• proactive protocols have a "world view" of the network (xxx: but only of the topology, which is dependend on the channel assignent, and not of the physical setup of nodes). 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 some other special purpose node in the mesh), these are the bottleneck links of the network. 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). Nodes farther away from a gateway is assigned a lower priority in channel choosing. (xxx: still consider client-to-client (node-to-node) traffic)
• load on a link might be measured by how many nodes use this link to reach a gateway
• only multi-radio nodes can initiate channel switch and only if channel depency is small

Deliverables

• Distributed channel assignment algorithm
• based on a proactive routing protocol (allows world view, but maybe partly view is sufficient)
• implementation and tests (e.g. compare to homogeneous, random and identical channel assignment)

Project excecution plan

What's next (TODO)

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