Upper-Confidence Bound for Frequency Selection in IoT Networks with Retransmissions

Nowadays, the Internet of Things (IoT) is considered a promising technology that will support the communications among a large number of devices, as it has become evident with the increasing demand of smart grids and smart cities projects. Nevertheless, the development of IoT networks also require the redesign of the entire paradigm of the legacy technology, since new research aspects such as the lower power consumption and low signaling need to be considered.

In this context, the LPWAN [15] technology has been conceived for providing the aforementioned features. For instance, LoRaWAN and SigFox technologies have been adopted in the monitoring of large scale systems (e.g., smart grids), where a large number of devices compete for the transmission of their packets, in unlicensed ISM bands (e.g., $433.5$ MHz in Europe). Then, the improvement of the network performance in these unlicensed bands require to conceive novel MAC mechanisms.

One important concern in the MAC design is to reduce the Packet Loss Ratio (PLR) due to the interference caused by the collisions among the devices within the network and those following different standards. In fact, the number of collisions increases as more devices without coordination share the same band. Hence, novel access mechanisms considering the collisions need to be addressed to avoid degrading the network performance, while at the same time targeting features of IoT networks.

In this regard, Multi-Arm Bandit (MAB) algorithms [9] have been recently proposed as a solution and in particular in LPWA networks [8, 4, 7]. For instance in [7], the non-stationarity introduced by the presence of more than one intelligent object is addressed by MAB algorithms. In that work, low-cost algorithms following two well-known approaches, such as the Upper-Confidence Bound ($UCB$) [2], and the Thompson Sampling (TS) algorithms [16] have reported good results. Other recent directions include theoretical analysis of application of MAB algorithms for slotted wireless protocols in a decentralized manner, see [5] and references therein, but in this work we focus on a more programmatic approach.

The aim of this paper is to assess the performance of MAB algorithms [9], used for frequency selection in IoT networks. In particular, and compared to the literature, we focus on the impact of the retransmissions on the performance of learning algorithms. Indeed, in the case where learning algorithms are used for frequency selection, IoT devices tend to focus on a single channel, which increases the probability of having several successive collisions. The contributions of this paper can be summarized as follows:

• We first propose a closed form approximation for the probability of having a second collision after a collision has occurred in one channel,

• Then, we introduce several heuristics so as to cope with retransmissions,

• We finally conduct simulations in order to compare the performance of the proposed heuristics with the naive uniform random approach and the simple UCB strategy (non aware of retransmissions).

Finally, our proposal is applied in a decentralized manner, and with a low complexity that do not require any modification on network side, and it could be applied with a very low extra cost in real embedded hardware. Implementation of the model and our proposals on real hardware [18] is left as a future work.

The rest of the paper is organized as follows: first the system model is introduced in Section II. Section IV describes more formally the MAB learning algorithms. Our contributions mainly consist in heuristics, presented in Section V, while numerical results are presented in Section VI. Conclusions are given in Section VII.

We suppose an IoT network made of one gateway (i.e., base station), and of a large number of end-devices that regularly send short data packets to the gateway. The base station listens to a fixed set of $K$ channels ($K>1$), in which devices can transmit their packets. As in [8], we suppose that the network is made of two types of devices:

• We have a set of static end-devices. These devices are low-cost devices and are only able to use one channels. They use the same gateway as others. However, as we consider an IoT standard which operates in unlicensed bands, it could be considered that they communicate with another gateway or are using another standard, without changing much the model and our conclusion.

• We also have dynamic devices which have the possibility to use all the $K$ available channels.

The IoT network considered here is a slotted ALOHA protocol [1], where each device has a probability $p>0$ to transmit a packet in a slot (first transmission). In case of collision, a device retransmits this packet after a random waiting time, uniformly distributed in $\left[\right[0;m-1\left]\right]$, where $m\in N^{\ast }$ is the length of the back-off interval. We denote by $M_t\in N^{\ast }$ the maximum number of transmissions for each packet. We assume that, in the case where more than two devices are transmitting a packet in the same slot, all the packets are lost and must be retransmitted.

With such assumptions, we can model the behavior of end-devices using the Markov chain [14] of Figure 1.

We consider $K>1$ orthogonal radio channels (also called arms) of different characteristics, being unknown to the device. The radio protocol is slotted in both time and frequency, meaning that at each time step $t\in N$, the device, tries to communicate in a channel $C\left(t\right)\in \{1,\dots ,K\}$. In our model, the device chooses one channel $k$ at a time, and use it to communicate, and waits for the gateway to send back an acknowledgement (Ack).

In the stochastic model considered in this paper, after choosing the arm $k$, receiving an acknowledgement provides a reward $r_k\left(t\right)$, randomly drawn from a certain distribution depending on the arm index. Rewards are assumed to be bounded in $[0,1]$, and generally they follow one-parameter exponential families (a well-known example being any family of Gaussian distributions with a fixed variance). We present our algorithm by restricting to Bernoulli distributions² for sake of simplicity, meaning that arm $k$ has a parameter ${\mu }_k\in [0,1]$ and rewards are drawn from $B\left({\mu }_k\right)$, $r_k\left(t\right)\sim B\left({\mu }_k\right)$, which can be simply interpreted by the device: it is $1$ if the channel $k$ is not used by any other device during the time slot $t$, and is $0$ otherwise.

We can justify why the proposed approach is interesting.

Before presenting different ways to incorporate the retransmissions, we present a classical bandit algorithm as a base building block. We chose to restrict to the $UCB$ algorithm [3], which is known to be efficient for stationary i.i.d. rewards while being simple to present, and being simple enough to be implemented in practice for embedded hardware. In this section, let us consider one device, which tries to learn how to reduce its PLR while accessing the network, without taking into account the retransmission aspect of our model. More details on this simpler variant can be found in previous work [7] and more theoretical details are given, e.g., in [9, 5].

Machine learning algorithms, and especially the MAB framework, has been used in simpler cognitive radio models before, starting from [12] and more recently in [7, 8], for instance. The novelty of our approach relies on the proposed heuristics that try to take into account the retransmission aspect of our model.

In our model, any dynamic object knows when it is retransmitting or sending for the first time, but using the unmodified $UCB$ algorithm for decision making (i.e., channel selection) in both cases do not use this information. As usual in reinforcement learning, a natural question is to evaluate whether using this additional contextual information can improve the performance of the learning policy.

We present in this Section some heuristics, that use this information in various ways. They vary only in their way to select channels for retransmissions, and all retransmissions are dealt with similarly (no distinction is done between the first retransmission and the next $M_t-1$ ones). All the following algorithms follow the same pattern as Algorithm 1.

We simulate our network in order to compare the proposed heuristics. The simulated network uses similar values of the ALOHA model as the one used for Figure 2: $\forall t,M_t=5$, $m=10$, and $p={10}^{-3}$. We consider $K=4$ channels (like for the LoRa standard), a number of time slots $1000000$, which is large enough to observe convergence of all learning algorithms. Moreover the results are averaged on $10$ independent runs of the random simulation. We consider a total number of devices of $N=2000$, and a non-uniform repartition of static devices of $40\%,30\%,20\%,10\%$ in the $4$ channels.

We present in Figure 3 the results of this numerical simulation. The $x$ axis corresponds to the number of communications of a device, and it corresponds to the number of learning step, while the $y$ axis corresponds to the successful transmission rate, in percentage.

We verify that each proposal is indeed learning, as its successful transmission rate is rapidly increasing (or equivalently, its PLR is decreasing). All plots show a pattern typical of MAB algorithms when applied to this kind of problem: a fast learning phase in the beginning of the experiment and a “plateau” showing the convergence of the algorithm to a stable strategy.

All heuristics outperform the naive random uniform approach, which is not included to reduce clutter in the plot. The random approach has a successful transmission rate of about $7\%$, constant in time as no learning is involved, and for instance the best heuristic attains a performance up-to $4$ times better, at about $30\%$. Observing such a strong improvement in terms of successful transmission rate is a very strong advocate of using simple MAB learning algorithm.

The conclusions we can draw from this simulation are twofold. First of all, a simple sanity check is that all the proposed heuristics do not reduce performance when compared to the naive approach. But most importantly, we observe three groups of heuristics. The less efficient one is the $K+1$ $UCB$, and this makes sense as having more learning algorithm needs more for each of them to learn. The more efficient one is the simple $UCB$ procedure, and this was quite surprising. All the other heuristics perform very much similarly.