MCRP

Multi-Channel Routing Fundamentals

(Ronald Kluth, 2006-05-29)

Motivation

The performance of wireless ad-hoc networks degrades as the number of users increases. One major reason for that is the sharing of a single channel.

Furthermore, single-transceiver devices can only listen on one channel at a time, and so most protocols are designed to work in a one-channel environment.

However, standards like IEEE 802.11 provide multiple non-overlapping channels, which would allow for simultaneous communication without interference.

So the logical consequence is to develop a routing protocol on the network layer level that can utilize multiple channels.

Assumptions

For the development of the protocol a very practical set of assumptions is used, which is supported by almost every available hardware today:

1. Each node is equipped with a single transceiver.
2. Each node can switch channels (with a delay of ≤ 80 μs).
3. IEEE 802.11 as MAC protocol remains unchanged.
4. The network layer can determine the proper channel and when to switch.

Definitions

Flow: A flow is an established connection between a source-destination pair.

Route: A route is a path from source to destination in which each node knows the next hop and it knows on which channel to transmit packets to the next hop.

Scenario 1

Requirements

The Routing protocol must perform channel assignment, route discovery, and route maintenance.

Channel Assignment Approaches

Channels can be assigned in two ways, either to nodes or to flows. First, assignment to nodes is evaluated:

Nodes are assigned channels regardless of traffic patterns and do not switch their listening channel to participate in a flow. After establishing a route, nodes switch channels to that of the receiver whenever they send packages. The advantage of this approach is that route establishment and channel assignment are separated and hence simpler to execute.

The Problem of this approach is a performance degradation due to deafness, which happens when two nodes are on different channels and cannot communicate. In this approach it can occur when a node switches its channel for sending and another is trying to communicate with it on its normal listening channel.

Assigning channels to flows means that all nodes in a route use a common channel. Thus, channel assignment must be coupled with route establishment. This concept works well with on-demand routing as nodes do not need to switch channels when transmitting packages, which avoids deafness.

However, other difficulties arise with this concept. Intersecting flows would require all involved nodes to use the same channel, and additional intersecting flows would require node-disjoint flows on different channels to switch to the same channel.

Two issues need to be addressed to work around these problems. Some specific nodes must be able to switch channels and the deafness problem must be avoided.

Scenario 2a Scenario 2b

Constraints

Certain constraints will be imposed to tackle the deafness problem and increase performance of the protocol.

To avoid deafness, two consecutive nodes on a path are not allowed to switch channels. When a node switches channels, it must notify its neighbors on a path.

To improve performance two more constraints are introduced. A node can only switch between a small number of channels, in this case two, even though more channels are available. Nodes may not switch channels too frequently, such as per-packet.

Scenario 3

Multi-Channel Routing Protocol - MCRP

Let us now turn to the actual multi-channel routing protocol. MCRP is an on-demand routing protocol similar to the Ad-hoc On-demand Distance Vector (AODV) protocol, which however only uses a single channel.

In order to ensure good performance, MCRP guarantees that a route from source to destination will be established, if one can be found in a single channel network with the same topology.

For the protocol to work efficiently it assigns one channel to all nodes in a flow but allows channel-switching nodes, except for two consecutive nodes in a flow. To manage this channel switching constraint, we need to introduce the concept of node states. The four feasible states are:

free:

The node is not involved in a flow and can freely switch to other channels.

locked:

The node is part of a flow on a certain channel.

switching:

The node is involved in multiple flows on different channels.

hard-locked:

The node has a flow on a certain channel and cannot be made a switching node because one of its neighbors is a switching node.

Scenario 2b

MCRP - Route Discovery

MCRP is a reactive routing protocol. When a source node wants to establish a route to a given destination, it broadcasts a Route Request (RREQ) on all used channels in rotation. All receiving nodes also forward the RREQ on all channels and add their own operating channel in the forwarded RREQ. The reverse path to source is set up while forwarding RREQs.

Route Entry (Pic)

Finally, upon receiving the RREQ, the destination node picks the channel and route to use for communication and sends a Route Reply (RREP). Intermediate nodes on the path drop RREP packets if a node would have to enter an infeasible state.

Obviously, this could create the problem that all routes might be dropped even though paths from source to destination exist. To avoid that, a “force” mechanism can be used.

If no conflicts occur, nodes on the return path simply switch channels and node states according to the following pattern:

free:

The node becomes locked and switches to the selected channel.

locked:

If the node is locked on a different channel, it becomes a switching node, otherwise nothing happens.

switching:

If one of the node’s operating channels is the selected channel, nothing changes, else the RREP gets dropped due to the channel limit.

hard-locked:

If the node is locked on the selected channel, nothing changes, otherwise the RREP gets dropped, because this node cannot become a switching node.

Force Mechanism

When destination receives RREQ(s) but all routes are infeasible, the protocol must avoid a connection failure since there is a source-destination path. Destination therefore sets the “force” flag in RREP. Nodes receiving RREP with “force” channel x must switch to that channel. This mechanism guarantees that a route can be found if a path exists. The following changes occur in the node states:

free:

The node becomes locked on channel x.

locked or hard-locked:

If the node is locked on a different channel, send RERR to flows on the other channel, otherwise stay in channel x. The node state remains unchanged.

switching:

If the node is locked on different channels, choose one and send RERR for those flows. Replace that channel with channel x as operating channel. The node state remains unchanged.

Locked nodes are not allowed to change state to avoid two consecutive switching nodes. When “force” is used, at least one flow loses the route. Its source needs to perform route discovery again, but to avoid oscillation of nodes caused by two forced flows, “forced” nodes temporarily do not accept another RREP with force-flag set.

Scenario 4

Channel Selection

Allowing channel switching for certain nodes opens up more route choices. The protocol selects the route and channel with the goal of balancing the load between available channels. Obviously, information on channel load needs to be collected, and this is achieved by sending HELLO messages on all channels, which is explained in detail later.

The node choosing the flow’s channel needs to satisfy two goals when choosing a channel. First, no node on the path should go into an infeasible state. All channels meeting this requirement are called feasible channels. Second, the feasible channel with the lowest load should be selected for channel load balancing.

To implement the channel selection, RREQs contain a channel table and a flow table.

Channel Table (Pic)

As the RREQs are forwarded, each node updates the channel table according to the following rules, depending on node states:

free:

The node makes no changes in the table.

locked:

The node increments chi if it is currently operating on channel i.

switching:

The node increments chm and chn if it is switching between channels m and n.

hard-locked:

The node increments chi by two if it is operating on channel i.

Scenario 4

Flow Table Fc - number of flows on channel c

The best channel could be determined by a different metric as well, but in this case the flow table is used to determine the interference level of each channel used in the path. The flow table contains the number of flows on a channel. Each node has its own flow table, and there is another flow table being sent in the RREQs.

Each node transmits HELLO messages periodically, which contain the node’s channel and its flow state. In this way, all nodes build their own flow table by recording the number of flows on each channel for themselves and their neighbors.

The RREQ flow table is updated as the packet is forwarded according to the following condition:

If Fc(node) > Fc(rreq) then update Fc(rreq) := Fc(node)

Scenario 4

Channel Selection Algorithm

The channel selection algorithm first checks route feasibility. A route is considered infeasible if it would produce consecutive switching nodes or if more than two channels would have to be assigned to a node.

The test is done with the channel table. If multiple channels have values ≥ 2 or more than two channels have values ≥ 1, the route is either dropped or used with “force.”

If the route is feasible, the channel is selected according to the channel table. If a channel has value ≥ 2, the channel has to be selected, or if two channels have value 1, one of these channels with minimum interference is selected. Finally, if only one channel has value 1 and all others 0, then select any channel with minimum interference level. (The interference level on a channel is determined by use of the flow table.)

Scenario 4

Delayed Reply

MCRP makes use of delayed reply, meaning it waits for more than one RREQ to arrive. When destination first receives a RREQ, it sets a timer and waits. Intermediate nodes forward RREQs after the first one only if the route is feasible and has lower path interference level. If the destination node receives multiple RREQs it chooses one where the selected channel has minimum interference level.

Forwarding & Channel Switching

All nodes in a flow share a common channel, but communication with a switching node requires buffering and signal messages. Hence, switching nodes send LEAVE / JOIN messages to neighbors on the respective operating channels. Neighbors then set the ‘active’ flag in route entries accordingly to 0 or 1 and in case of absence from the channel they need to buffer packets till they receive a JOIN from the switching node. Packets in the buffer are then sent with higher priority.

The duration a switching node stays in a channel should be handled intelligently according to traffic load, however MCRP uses a fixed duration of 50 ms.

Route Maintenance

Routes are maintained with the use of timers, which are refreshed each time the route is used. When a route is considered to be stale it is deleted from the routing table. In case the MAC layer finds broken links, RERRs are sent. Nodes have a precursor list on the path and an RERR is only transmitted when a node has a precursor for the broken route. When routes are removed, node states can change as follows:

locked, hard-locked, switching:

If all of a node’s routes are removed, it becomes a free node.

hard-locked:

If all routes with a switching node as next hop are removed, the node becomes a locked node.

switching:

If all routes in one channel are removed, it becomes a locked node.

Performance Simulations

Simulation parameters

• Simulator: ns-2
• Metric: throughput over all flows
• MCRP with 2,3,4 channels + AODV for comparison
• Network area: 1000m x 1000m
• Random node distribution
• Node transmission range of about 250m
• Channel bit rate 11Mbps

Performance Simulation 1

In this simulation, a varied number of flows was applied. One can see that MCRP can sometimes improve throughput by factor 4 with 4 channels. On average, overhead and flow-level channel allocation prevent a factor of k (the number of channels). Compared to AODV, contention is better distributed over the channels and the collision rate is thus reduced, which is why MCRP can sometimes achieve more than k times the throughput of AODV with k channels.

Performance Simulation 2

In this simulation the traffic of each of the 10 flows was varied from 32Kbps to 4096Kbps. With low traffic AODV performes slightly better as there is less overhead, but with increased traffic MCRP shows a dramatic improvement over AODV.

Performance Simulation 3

Here, 10 different scenarios with 50 randomly placed nodes were simulated. In most scenarios the improvement over AODV is a little less than factor k, but sometimes it can be more than factor k due to fewer collisions as a result of channel distribution.

Conclusion

The simulations were chosen somewhat optimistically, with many nodes on a small area, which naturally offers a lot of route choices.

Some points of the protocol still need to be tweaked, such as the metrics for route selection and clever channel switching.

However, it has been shown that even with standard equipment a dramatic improvement in network throughput is possible by utilizing multiple channels.