A Relaying Selection Scheme for Maximizing a Diamond Network's Throughput

In this demonstration, we present an implementation design of a TDMA protocol for the canonical diamond-topology network containing a source, two relays and a destination (single unicast session). Getting inspired by the established Lyapunov methodology, we propose an online strategy for the relay selection/scheduling problem. In contrast to other existing works, we implement this strategy inside the proposed TDMA protocol in order to operate over a CSMA enabled Wi-Fi infrastructure-less network. Our design is tailored to achieve the objectives of stabilizing the network and either maximizing throughput or minimizing the total power consumption. Our scheme has been implemented and tested thoroughly through experimentation in the NITOS wireless testbed by exploiting WiFi technology features. The results revealed significant increase in networking efficiency for throughput maximization.

Relay Selection Policy

The scheduling policy rule is educed by minimizing the bound on the Lyapunov drift expression (see related paper) with respect to network controller a(t). The solution follows simply, and the network controller indicates power efficient schedules by setting a(t) = 1 and selecting links SR1 and R2D for activation, when the drift expression is negative ([] < 0), otherwise it sets a(t) = 0 and activates links SR2 and R1D.

(a) 1st feasible action set, a(t) = 1. (b) 2nd feasible action set, a(t) = 0.

Figure 1: Relay Selection policy: Controller a(t) enables communication on particular links each time. Red doted lines indicate active schedules

Methodology

TDMA frame

We elaborate a network controller within the TDMA frame to solve a global optimization problem at each time slot in a centralized manner. In our formulation, we consider the class of scheduling policies that select concurrently a noninterfering subset of links.

Figure 2: A TDMA frame for the cooperative diamond network

CSMA protocol suppression

The considered diamond network of Fig. 1 consists of a source S, two relays R1, R2 and a destination D. In order to be able to assume that links are interference limited and impose the constraint that, at any time slot t, only one of the two sets of links (shown in (left-side) or (right-side)) can be activated, we need to operate the wireless network in different channels (Channels A and B) per hop and equip relays with two wireless interfaces, in order to avoid packet collisions. Thus, first hop links (S-->R1 or S -> R2) use channel A and second hop links (R1 --> D and R2 --> D) use channel B.

Moreover, considering the case where collisions might be occurred when packets from an active schedule (i.e. links SR1 and R2D) collide with packets from a previous active schedule (i.e. from link R1D) due to the inability of controlling the wireless card firmware, we face this obstacle by moving the queues and the storing of packets to the Sublayer 2.5, using Click Modular router. Moreover, we set the maximum length size (capacity in terms of number of packets) of the MAC layer queues of each node equals to one, so that to be able to suppress the inability of controlling packet transmissions from the MAC queue.

Contribution

We design and implement a TDMA access scheme for packet forwarding, which is backwards compatible with CSMA enabled commercial devices and it is also effectively applied upon Wi-Fi networks using off-the-shelf equipment.
We elaborate a centralized network controller in the TDMA frame to enforce scheduling and relay selection policies, relying on Lyapunov optimization.
We explore performance enhancements of throughput optimal scheduling by implementing centralized networking.
We seek to obtain desired tradeoffs between networking performance efficiency metrics, such as power consumption (or system throughput) vs. networking delay.
We evaluate the cooperative maximum throughput solution on the NITOS wireless testbed