Dichotomy: A Practical Architecture for Multi-channel IEEE 802.11 Multi-hop Networks

This project focuses on exploiting channel diversity to mitigate the interference, so as to improve the overall throughput of wireless multi-hop networks (WMN). We specifically consider the case in which most of nodes in a WMN are equipped with single transceiver. This assumption has much practical value since current devices are typically equipped with only one single half-duplex 802.11 radio interface.

We propose a new practical multi-channel architecture for single radio WMNs that performs channel scheduling at link level, while eliminating two most important constraints existed in previous solutions: tight clock synchronization and large channel switching overhead. Moreover, many of these solutions requires changing the underlying MAC behavior, but our scheme can be easily implemented as software modules on top of existing IEEE 802.11 MAC over commercial off-the-shelf  hardware.

Our proposed architecture is called Dichotomy. The core idea is to strategically divide the nodes in the network into two subsets. One subset of nodes (named anchors) is assigned fixed working channels, while the other nodes (named hoppers) keep hopping among channels of neighboring anchors. Communications are enforced to occur only between anchor-hopper pairs or anchor-anchor pairs if they are assigned on the same channel. Since only one node between two communication parties is allowed to dynamically change channels, it does not require clock synchronization among neighboring nodes. We further develop a localized and distributed algorithm that dynamically selects anchors and coordinates the working channels of anchors in such a way that the interference in the network is minimized. Our evaluation demonstrates that although Dichotomy restricts anchors work on almost fixed channels, it is able to exploit multi-channel capability effectively.

We have implemented the Dichotomy architecture on Windows platform with commercial 802.11 wireless interface cards. We deploy and evaluate our implementation in a wireless multi-hop test-bed in our building. We further implement Dichotomy in NS2 and conduct large-scale simulation studies. Our experience shows that Dichotomy architecture yields great improvement in network throughput compared to single channel 802.11, and achieves better or comparable performance compared to those solutions that require complex global time synchronization in the network.

 

Overview

Kun Tan

Researcher

Wireless and Networking Group

Dichotomy is implemented as a thin shim layer between IP layer and traditional MAC layer. It provides a virtual network interface to the IP layer as a normal Ethernet interface while hiding detailed operation on multiple channels. It adds functionalities on both data plane and control plane.

In the data plane, it contains two functional modules:

1. Per-neighbor FIFO queues and priority queue. Each neighbor is identified with its unique MAC address. Since neighbors of a node may locate on different channels, packets to each neighbor should be scheduled individually. The priority queue prioritizes the transmission of signaling packets.

2. Traffic gate. This module regulates the outgoing packets. It actually controls how many packets are allowed to be buffered at the MAC layer. This module is critical to implement fast channel switch in COTS 802.11 NIC.

In the control plane, it contains four major modules:

1. Isochronous Channel Switching. This module cooperates with the Traffic Gate to implement fast channel switching with a delay of 570us.

2. Beaconing and Discovery. This module handles the task of learning about one-hop neighbors of a node. It employs a beaconing mechanism that allows nodes to discover one another.

3. Channel scheduler. This module determines the channel on which a hopper would work on in the next time slot. It also coordinates anchors and hoppers by exchanging small signaling packets.

4. Packet scheduler. It defines how packets are scheduled to be sent when a hopper switches to the channel assigned to an anchor.

Architecture