GNU Radio Implementation of MALIN: "Multi-Armed bandits Learning for Internet-of-things Network"

The monitoring of large scale systems, such as smart grids and smart cities, requires the development of networks dedicated to Internet-of-Things (IoT) applications. For instance, Low Power Wide Area Networks (LPWAN) [17], as LoRaWAN or SigFox, are nowadays deployed in unlicensed bands to handle a large number of objects transmitting a few packets per day or week. In order to reduce the energy consumption of end-devices, these networks rely on pure ALOHA-based Medium Access (MAC) protocols.

One of the challenges in the design of MAC solutions for the IoT is to design solutions which improve the performance of the network and reduce the Packet Loss Ratio (PLR), without reducing the end-devices battery life. In particular, many IoT standards operate in unlicensed bands, that is why we have to find solutions that do not increase the PLR due to the interference caused by other standards and networks which share the same band, without coordination. As this interfering traffic is generated by different standards and networks, it cannot be controlled, and it is not evenly distributed in the different channels.

Multi-Armed Bandit (MAB) algorithms [8] have been recently proposed as a solution to improve the performance of IoT networks and in particular in LPWAN [7, 3]. In this paper, we describe the way we implemented a demo where we evaluate MAB algorithms [8], used in combination with a pure ALOHA-based protocol (such as the ones employed in LPWAN). This demonstration is the first implementation which aims at assessing the potential gain of MAB learning algorithms in IoT scenarios. Following our recent work [6], we propose to model this problem as Non-Stationary¹ MAB. We suggest to use low-cost algorithms, focusing on two well-known algorithms: a frequentist one (${UCB}_1$) and a Bayesian one (TS). We consider the Upper-Confidence Bound (${UCB}_1$) [2], and the Thompson Sampling (TS) algorithms [19]. Both algorithms have already been applied with success in the context of wireless decision making, both empirically for Opportunistic Spectrum Access [11], and more recently for multi-users Cognitive Radio problems [4] with a more theoretical approach.

We use a TestBed designed in 2017 by our team SCEE [5], containing different USRP boards [21], controlled by a single laptop using GNU Radio [9], and where the intelligence of each object corresponds to a learning algorithm, implemented as a GNU Radio block [10] and written in Python or C++.

In our demo, we consider a simple wireless network, consisting of one gateway (radio access point), and a certain interfering background traffic, assumed to be stationary (i.i.d.), which is generated by end-devices communicating in other networks. Some dynamic intelligent objects (end-user or autonomous objects) try to communicate with the gateway, with a low-overhead protocol. This communication can be done in different channels which are also shared by devices using other networks. Once the gateway receives a packet transmitted by a dynamic device in one channel, it transmits back to it an acknowledgement in the same channel, after a fixed-time delay, as it is done in the LoRaWAN standard. This ACK allows the device to learn about the channel quality and thus, to use learning algorithms for the purpose of best channel selection.

In this demo, we can generate scenarios with different parameters (number of channels, interfering traffic, etc) in order to evaluate the performance of learning in various settings. Moreover, we compare the performance of learning with that of the random uniform access to channels, which is the current state-of-the-art of commercial LPWAN solutions. This allows to check that in case of uniform traffic, when there is nothing to learn, the intelligent objects at least do not reduce their successful communication rate in comparison to the naive objects. This also shows that in case of non-uniform stationary traffic, the MAB learning algorithms indeed help to increase the global efficiency of the network by improving the success rate of the intelligent objects.

The rest of this paper is organized as follows. The system model is introduced in Section 2. In Section 3, we describe more formally both the ${UCB}_1$ and the TS algorithms. Our implementation is presented in Section 4, and results are given in Section 5.

We consider the system model presented in Figure 1, where a set of object sends uplink packets to the network gateway, in the $433.5MHz$ ISM band. The communication between IoT devices and this gateway is done through a simple pure ALOHA-based protocol where devices transmit uplink packets of fixed duration whenever they want. The devices can transmit their packets in $K\ge 1$ channels (e.g., $K=4$). In the case where the gateway receives an uplink in one channel, it transmits an acknowledgement to the end-device in the same channel, after a fixed delay (of $1$ s).

These communications operate in unlicensed ISM bands and, consequently, suffer from interference generated by uncoordinated neighboring networks. This interfering traffic is uncontrolled, and can be unevenly distributed over the $K$ different channels.

We consider the network from the point of view of one end-user. Every times the end-user has to communicate with the gateway, it has to choose one channel (at each transmission $t\ge 1,t\in N$), denoted as $C\left(t\right)=k\in \{1,\dots ,K\}$. Then, the end-users starts waiting in this channel $C\left(t\right)$ for an acknowledgement sent by the gateway. Before sending another message (i.e., at time $t+1$), the end-user knows if it received or not this ACK message. For this reason, selecting channel (or arm) $k$ at time $t$ yields a (random) feedback, called a reward, $r_k\left(t\right)\in \{0,1\}$, being $0$ if no ACK was received before the next message, or $1$ if ACK was successfully received. The goal of the end-user is to minimize its packet loss ratio, or equivalently, it is to maximize its cumulative reward, $r_{1\dots T}:={\sum }_{t=1}^T{r}_{C\left(t\right)}\left(t\right),$ as it is usually done in MAB problems [19, 18, 13].

This problem is a special case of the so-called “stochastic” MAB, where the sequence of rewards drawn from a given arm $k$ is assumed to be i.i.d., under some distribution ${\nu }_k$, that has a mean ${\mu }_k$. Several types of reward distributions have been considered in the literature, for example distributions that belong to a one-dimensional exponential family (e.g., Gaussian, Exponential, Poisson or Bernoulli distributions).

Rewards are binary in our model, and so we consider only Bernoulli distributions, in which $r_k\left(t\right)\sim Bern\left({\mu }_k\right)$, that is, $r_k\left(t\right)\in \{0,1\}$ and $P\left(r_k\right(t)=1)={\mu }_k\in [0,1]$. Contrary to many previous work done in the CR field (e.g., Opportunistic Spectrum Access), the reward $r_k\left(t\right)$ does not come from a sensing phase before sending the $t$-th message, as it would do for any “listen-before-talk” model. Rewards come from receiving an acknowledgement from the gateway, between the $t$-th and $t+1$-th messages.

The problem parameters ${\mu }_1,\dots ,{\mu }_K$ are of course unknown to the end-users, so to maximize its cumulated reward, it must learn the distributions of the channels, in order to be able to progressively focus on the best arm (i.e., the arm with largest mean). This requires to tackle the so-called exploration-exploitation dilemma: a player has to try all arms a sufficient number of times to get a robust estimate of their qualities, while not selecting the worst arms too many times.

Before discussing the relevance of a MAB model for our IoT application, we present two bandit algorithms, ${UCB}_1$ and Thompson Sampling, which are both known to be efficient for stationary i.i.d. rewards and are shown to be useful in our setting (in Sec. V).

In this section, we present our implementation of MAB algorithms in our model of IoT networks. We first describe the simplified physical layer of this demo, then we present our GNU Radio implementation.

We compare the two algorithms described in Section III-A against a uniform access algorithm, that uniformly selects its channel at random. Three objects are compared by their mean successful communication rates, on a horizon of $2000$ communication slots, and were using three algorithms: uniform random access (in cyan), Thompson Sampling (in green) and ${UCB}_1$ (in red). Figure 4 shows the results averaged on $10$ repetitions using the same conditions. Each experiment takes about half a day, as we make objects generate one message every $5$ seconds, in order to artificially speed up the process and with no loss of generality. Learning can be useful only when there is a large enough difference between “good” and “bad” channels, Each object was learning to access $4$ different non-overlapping channels, that we chose to have occupancy rates of $[15\%,10\%,2\%,1\%]$. When facing the same stationary background traffic, we see that the learning objects are both very quickly more efficient than the naive uniform object. We obtain an improvement in terms of successful communication rate from $40\%$ to about $60\%$ in only $100$ communications (about $16min$), and up-to $80\%$ in only $400$ communications. In stationary environments, both the TS and ${UCB}_1$ algorithms are very efficient and converge quickly, resulting in a very strong decrease in collisions and failed communication slots. ${UCB}_1$ is faster to learn but eventually TS gives a (slightly) better average performance.

Similar results are obtained for overlapping channels, when dynamic devices are learning in the presence of multiple devices, all using the same learning algorithm. Empirical results confirm the simulations presented in our paper [6, Fig.3]. Such results are very encouraging, and illustrate well the various strong possibilities of MAB learning applied to IoT networks.

We presented in this article a demonstration, by specifying the system model and explaining the two MAB algorithms used in practice. We gave all the necessary details on both the PHY and the MAC layer, as well as details on the User Interface developed for the demo. Results obtained in practice were discussed, to highlight the interest of using learning algorithms for radio online optimization problem, and especially multi-armed bandit learning algorithms. By using such low-cost algorithms, we demonstrated empirically that a dynamically reconfigurable object can learn on its own to favor a certain channel, if the environment traffic is not uniform between the $K$ different channels.

Possible future extensions of this work include: considering more dynamic objects (e.g., $100$), implementing a real-world IoT communication protocol (like the LoRaWAN standard), and studying the interference in case of other gateways located nearby. We are also interested in studying the possible gain of using a learning step when the transmission model follows ALOHA-like retransmissions.