D-07S-05: Difference between revisions

From
Jump to navigation Jump to search
(first ideas)
 
(25 intermediate revisions by the same user not shown)
Line 1: Line 1:
If you read this and find something strange, then please go on and either ''edit'' or leave a ''comment''.
=Using wireless mesh networks for Early Warning Systems=

= About =

Working title: Using wireless mesh networks for Early Warning Systems

Assigned to: Jens Nachtigall
Assigned to: Jens Nachtigall


Line 6: Line 11:
Expected Submission: December 2007
Expected Submission: December 2007


= Motivation (Aufhänger) =
==Problem Statement==
* Early Warning Systems needs real-time communication (the reactive DSR protocol cannot achieve this)
* using cheap COTS hardware (no or very limited access to the MAC layer, but it is fine to switch channels every x secs)
* 802.11b offers 3 non-overlapping channels, 802.11a even 12
* 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


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.
==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)
* increase throughput (to retrieve data, e.g. MiniSeed) and decrease latency (for EWS) by using non-overlapping channels, i.e. a node can receive and transmit at the same time by having its to wifi interfaces at different channels


= Problem Statement =
==Prior Art==
* several attempts to make use of the non-overlapping channels by proposing a different MAC layer (however, for COTS you usually do not have access to the MAC):
** [http://www.cs.berkeley.edu/~so/pubs/MSWiM_f05-mo.pdf Comparison of Multi-Channel MAC Protocols]
** [http://citeseer.ist.psu.edu/632582.html Multi-channel MAC with Dynamic Channel Selection for Ad Hoc Networks]
* Dissertation ''[http://scholar.lib.vt.edu/theses/available/etd-06262006-091312/unrestricted/ungheeLEEdissertation.pdf 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)


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.
==Key Ideas / Project Execution Plan ==

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

= Related work =

I manage [http://www.citeulike.org/user/nachtigall 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 [http://www.citeulike.org/user/nachtigall/tag/multichannelmac 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).
=== Using directional antennas ===

=== 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 [http://www.citeulike.org/user/nachtigall/tag/transmissionpower 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 [http://www.citeulike.org/user/nachtigall/tag/controlchannel 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).

== Similar solutions/approaches and there weaknesses ==

= My solution/approach (WiP) =


=== An image says more then 1000 words ===

[[Image:Idea-topo-initial.png|framed|center|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.]]

[[Image:Idea-topo-final.png|framed|center|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 [http://www.citeulike.org/user/nachtigall/article/486139 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
* 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))
* 2 (or more) single radio nodes that are connected by an ethernet cable can form a "virtual multi-radio node
* 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

== Improvements (why my concept is superior to others) ==


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


=== Done so far ===
==Project Log==
* getting an overview / reading papers


==TODO==
=== What's next (TODO) ===
* [07/2007] getting an overview / reading papers
* what kind of distributed channel assignment algorithms exist
* state own approach more precisely
* how do these work in case we have a world view (proactive protocol)

Latest revision as of 08:57, 28 July 2007

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

Using directional antennas

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

Similar solutions/approaches and there weaknesses

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

Improvements (why my concept is superior to others)

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

Done so far

What's next (TODO)

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