D-07S-05

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

• Dissertation A Proactive Routing Protocol for Multi-Channel Wireless Ad-hoc Networks by Unghee Lee (requires two radios at every node; one is used for control/routing information only and the other one for data/ack only). It says:

3.2.5.2 Independent Access [to several channels without reserving one channel/radio for control information]

A more complex control scheme for channel negotiation can allow simultaneous access to different channels by using multiple transceivers. This can increase the channel utilization. Although this scheme seems to be more practical and profitable, practical aspect and feasibility need to be examined in detail [28].

and

As discussed in Section 3.2.5, even though independent access seems to be practical and beneficial, this is beyond our current scope and remains a topic for future research.

That's what I would like to do :-)

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

• make use of these multiple channels by means of ("virtual") multiradio nodes like the WRAPBoards without excluding the common single radio nodes, i.e. utilise multiple radios (channels) whenever possible whithout requiring a node to have several radios

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. 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.

Ideas (brainstorming)

• use ETX (or?) for channel quality measures (consider other nodes not from our mesh in ISM band)
• node admin might be allowed to set some of his radios to a fixed channel
• proactive protocols have a "world view" of the network. This is nice because routes to nodes do not have to be found out on demand prior to sending data (which is slow) (the 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 like GPS coordinates of all nodes
• the idea is to piggyback channel assignment information with the HELLO or TOPOLOGY CONTROL (TC) messages of http://olsr.org and to have a distributed channel assign algorithm taking into account joining/leaving/movement of nodes
• switching channels can be done every x secs using libiw/iwconfig/wl
• both radios are used for data and control (routing) messages, no need to reserve one radio for control messages only
• 2 (or more) single radio nodes that are connected by an ethernet cable can form a "virtual multi-radio node"
• diff. cha. assignements can lead to different network topologies.

• previous work has a lot of constrains: does not consider other network, requires MAC, requires always several radios (how about channel assignment for just one radio?)

Deliverables

• Distributed channel assignment algorithm
• based on a proactive routing protocol (allows world view)
• using unmodified standard 801.11 MAC (only interacting with the MAC by switching the channel of one the available interfaces from time to time)

Project excecution plan

What's next (TODO)

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