<figure><img src="image_1.png" /></figure>

HAL
open science

# An Auction-based Assignment Method for LoRa Multi-Gateway Networks

Jen-Tse Chen, Megumi Kaneko, Alexandre Guitton

► To cite this version:

Jen-Tse Chen, Megumi Kaneko, Alexandre Guitton. An Auction-based Assignment Method for LoRa Multi-Gateway Networks. IEEE International Conference on Communications, IEEE, May 2023, Rome, Italy. hal-04077972

HAL Id: hal-04077972

https://hal.science/hal-04077972

Submitted on 21 Apr 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An Auction-based Assignment Method for LoRa
## Multi-Gateway Networks

Jen-Tse Chen*, Megumi Kaneko† IEEE Senior Member, Alexandre Guitton‡

* National Tsing Hua University, Hsinchu, Taiwan, † National Institute of Informatics, Tokyo, Japan

‡ Université Clermont-Auvergne, CNRS LIMOS, Clermont-Ferrand, France

Emails: *rzchen@gapp.nthu.edu.tw, †megkaneko@nii.ac.jp, ‡alexandre.guitton@uca.fr

**Abstract**—Long Range (LoRa) technology constitutes one of the major enablers of future Internet-of-Things (IoT) applications, such as monitoring of challenged environments and smart buildings. However, crucial issues in the context of multi-gateway LoRa networks have been overlooked. In particular, most existing methods did not consider the stringent constraint of limited number of demodulators at each gateway. Therefore, we devise a gateway selection method for uplink LoRa transmissions, where this limited availability of demodulators is fully considered. We propose an optimization approach based on the auction mechanism, where each IoT device is pre-assigned to a unique gateway, so as to maximize the total amount of demodulated transmissions without redundancy at the network server. Furthermore, a low complexity method is also designed, where devices are partitioned into groups and where auctions are parallelized. Numerical results show that the proposed methods largely outperform benchmark algorithms in terms of the network utility function and sum-rate, while approaching the upper bound performance. The proposed methods are particularly suited to cope with the inherent dynamics of mobile LoRa IoT networks, as highest gains are attained for demodulation latencies in the order of tens to hundreds of milliseconds.<fnref n="1" />

**Keywords:** LoRa, Multi-gateway, Optimization, Auction

## I. INTRODUCTION

As one of the major technologies for Low Power Wide Area Networks (LPWAN), LoRa plays a prominent role for enabling Internet-of-Things (IoT) applications for smart cities, intelligent transportation, and smart factories. LoRa-based networks are also envisioned to cope with the exponential surge of the amount of IoT data traffic of Beyond 5G (B5G) and 6G. LoRa allows flexible adaptation of transmission rates and distance ranges, even under low power. In LoRa, Chirp Spreading Spectrum (CSS) modulation is used, where chirps are encoded by Spreading Factors (SF). In the case of LoRaWAN, the basic MAC standard for LoRa, SFs vary from 7 to 12 [1], where a smaller SF entails higher data rate but smaller transmission range. The uplink packet transmissions from end-devices are first demodulated by one or more LoRa Gateways (GW), and then forwarded to a Network Server (NS) in the core network. This NS may also control LoRa parameters as well as LoRa packet scheduling in a centralized manner. Hence, LoRa networks are organized as a star-of-stars topology.

Several works have studied the optimization of LoRa resource allocation, in terms of channels, SFs and transmit powers. Among them, a joint SF and power allocation strategy was

<figure><img src="image_3.png" /><figcaption>Fig. 1. System Model: LoRa multi-gateway environment</figcaption></figure>

proposed in [2], where minimum device rates were maximized under imperfect SF orthogonality. In [3], an optimized power allocation scheme was designed for energy harvesting LoRa networks. However, most existing works have overlooked the primordial constraint of the limited number of demodulators at each GW. Indeed, current GW chips can only demodulate eight concurrent LoRa transmissions [4], which imposes a hard constraint on LoRa resource allocation strategies. Among the few works that tackled this constraint, the analysis in [5] showed its harmful impact on the average successful packet decoding rate, while [6] proposed to reuse demodulators for improving achievable rates and fairness. However, these works focused on a single GW network and cannot be readily applied to more complex and realistic multi-GW environments.

Therefore, in this work, we investigate the issue of device-to-GW assignment in a multi-GW LoRa network, where the constraint on the number of demodulators is fully taken into account. Unlike for single GW networks, a packet sent by an end-device is received by multiple GWs within its transmission range. Hence, the same packet may be demodulated by several GWs, resulting into redundant and useless packet receptions at the NS. Thus, without a proper GW selection method for each device, more demodulators may be wasted and the overall LoRa performance may be largely degraded. To cope with this issue, we propose to pre-assign a GW to each end-device, so as to maximize the total packet decoding rate over all end-devices' transmissions, subject to the constraint of demodulators. To solve this optimization problem, we design an auction-based GW selection approach [7] which is solved centrally at the NS. Additionally, to reduce the time complexity entailed by the sequential iterations of the auction algorithm, we also propose an end-device grouping method that enables parallelization, at the cost of performance. Furthermore, the proposed assignment optimization is suitable for a realistic LoRa environment,

<footnote n="1">¹This work was supported in part by the Grants-in-Aid for Scientific Research (Kakenhi 17K06453 and 20H00592) from the Ministry of Education, Science, Sports, and Culture of Japan and by the NII MoU Grant.</footnote>
as it accounts for both inter-SF and co-SF interferences, in the collision overlap time model [3]. Note that, while [8] proposes two heuristic approaches to increase the number of demodulated frames - one where each GW randomly ignores incoming frames (targeted for small SF), and one where each GW exchanges control messages with other GWs (targeted for large SF)-, the proposed method here enables to maximize the number of demodulated transmissions in a centralized manner.

The main contributions are summarized as follows:

1) We formulate the mathematical optimization problem that pre-assigns each device to a GW for maximizing the total number of demodulated signal transmissions, under the realistic constraints of the limited number of demodulators, and imperfect SF orthogonality.

2) By transforming the initial problem, we propose an auction-based GW pre-selection approach. To further improve its computation time efficiency, a group auction-based method is also designed.

3) Numerical evaluations show that the proposed methods largely outperform the conventional schemes, while achieving a close performance to the upper bound with unlimited demodulator capacity. In particular, highest gains are observed for demodulation latencies in the order of tens to hundreds of milliseconds, making the proposed methods particularly suitable for mobile LoRa IoT networks.

## II. SYSTEM MODEL

As shown in Fig. 1, we consider $N_G$ GWs in set $\mathcal{G}$ and $N_E$ end-devices in set $\mathcal{E}$, where devices are uniformly distributed around each GW with a circular coverage of radius $R$. Conventional distance-SF allocation is assumed, where the SF of each device is fixed based on its distance to the nearest GW [9]. The uplink SINR from device $i$ to GW $j$ is given as

$$ \gamma_{ij} = \frac{P_i^{\text{Tx}} g_{ij} r_{ij}^{-\alpha}}{\sum_{l=1, l \neq i}^{N_E} P_l^{\text{Tx}} g_{lj} r_{lj}^{-\alpha} E_{\tau}[h_{lj}(\tau_{il})] + \sigma^2}, \quad (1) $$

where $P_i^{\text{Tx}}$ is the transmit power, which is fixed for each SF as in Table I, $g_{ij}$ is the power of small-scale channel fading, modelled by an exponential random variable with mean one, $r_{ij}$ is the distance between device $i$ and GW $j$, $\alpha$ is the path loss exponent and $\sigma^2 = -174 + 10 \log BW \text{dBm}$ is the variance of the Additive White Gaussian Noise (AWGN) with bandwidth $BW = 125$ kHz. Moreover, the collision overlap time $h_{lj}(\tau_{il})$ between the desired signal from device $i$ and interference from device $l$ follows the model of [3]. Namely, the delay between signal and interference $\tau_{il}$ is modelled as a uniform random variable between 0 and $T_c$, where $T_c$ is the average packet duration weighted by each SF proportion. Denoting $T_{ij}$ as the packet duration of the desired signal and $T_{lj}$ as the packet duration of interference, the expected collision overlap time is (see Appendix A):

$$ E_{\tau}[h_{lj}(\tau_{il})] = \begin{cases} \frac{T_{lj}^2}{2T_{ij}T_c}, & T_{ij} > T_{lj}, \\ \frac{T_{ij}}{2T_c}, & T_{ij} \le T_{lj}. \end{cases} \quad (2) $$

The capture probability is given by the probability that SINR $\gamma_{ij}$ exceeds threshold $\Gamma_{ij}$, which varies with the SF as shown in

<table><caption>TABLE I
PROPERTIES GIVEN SPREADING FACTORS [5][9]</caption><thead><tr><th>Spreading Factor</th><th>Packet Duration [ms]</th><th>Threshold [dBm]</th><th>Bit Rate [kb/s]</th></tr></thead><tbody><tr><td>7</td><td>348.42</td><td>-6</td><td>5.47</td></tr><tr><td>8</td><td>614.91</td><td>-9</td><td>3.13</td></tr><tr><td>9</td><td>615.42</td><td>-12</td><td>1.76</td></tr><tr><td>10</td><td>616.45</td><td>-15</td><td>0.98</td></tr><tr><td>11</td><td>1314.82</td><td>-17.5</td><td>0.54</td></tr><tr><td>12</td><td>2465.79</td><td>-20</td><td>0.29</td></tr></tbody></table>

Table I. Based on the SINR in (1), the capture probability can be derived as follows by marginalizing over random variable $g_{ij}$ (details in Appendix B),

$$ \begin{aligned} P_{ij}^{\text{cap}} &= Pr(\gamma_{ij} > \Gamma_{ij}) \\ &= e^{-\frac{\Gamma_{ij}\sigma^2}{P_i^{\text{Tx}}r_{ij}^{-\alpha}}} \prod_{l=1, l \neq i}^{N_E} \frac{1}{\Gamma_{ij} \left(\frac{P_i^{\text{Tx}}}{P_i^{\text{Tx}}}\right) \left(\frac{r_{ij}}{r_{ij}}\right)^{-\alpha} h_{lj}(\tau_{il}) + 1} \end{aligned} \quad (3) $$

Furthermore, unlike most existing works, we assume that each GW has a limited number of demodulators $N_D$. Hence, only $N_D$ packets can be demodulated simultaneously. If there are no free demodulators upon arrival of a new packet, it will be discarded. We also assume as in previous works that all GWs are centrally controlled by the NS, which knows the positions and long-term channel SINRs of all end-devices (i.e., large-scale fading parameters that can be obtained with small overhead), based on which the allocation is determined.

Finally, each GW is assumed to be able to identify the device ID of each packet during preamble detection. This allows a GW to determine from each preamble whether the incoming packet belongs to its pre-assigned devices or not, i.e., if the packet should be demodulated or ignored. In practice, however, the device ID appears at the beginning of the payload, and not in the preamble. Our assumption is reasonable as it is indeed possible to identify a device with good accuracy, by relying on preamble features that are device-specific. Such features include the SF, the Carrier Frequency Offset (CFO) which is an imprecision of the transmitter's center frequency, the Sampling Time Offset (STO) which is an imprecision of the transmitter's clock that modifies the symbol duration [10], and small timing offsets due to device hardware imperfections [11]. For instance, such features are shown to be very efficient in identifying devices in various LoRa packet collision decoding methods as in [12]. A typical LoRa GW already detects the CFO and STO during each preamble, and uses them to correct frequency and time shifts that are specific to each device. However, a gateway is not able to decode a frame having a CFO whose absolute value is larger than 25% of the BW.

Let us give a numerical example showing that combined together, the features above can be used to identify each device with sufficient accuracy from the preamble. It can be reasonably assumed that the CFO is bounded by 25% of the bandwidth and that the GW can compute it with a 1%-margin, giving 51 distinguishable values of CFO. Similarly, it can be assumed that the STO is bounded by 5% and that the GW can compute it with a margin 0.1%-margin, giving 101 distinguishable values of STO. For the tiny hardware offsets, there are 10 distinguishable values [11]. If we also take into account the
channels used in Europe, fixed for each device during a period of time, there are 3 distinguishable values. Overall, each device has a configuration out of $51 \times 101 \times 10 \times 3 = 154530$. Using the Birthday Paradox problem [13], it can be computed that 126 devices can be identified with a 95% probability solely from their preambles. Note that if there are more devices in the network, it suffices to consider groups of devices with identical features, rather than individual devices, and run the proposed algorithms on these groups.

Note that correctly identifying devices requires a training period. However, even imperfect device identification is likely to improve the performance compared to letting the gateways capture only the strongest signals, which possibly correspond to the same frames. For sake of clarity, the impact of device detection errors is not modelled here, as we focus on the main problem of multi-GW assignment under demodulators' constraint. However, this assumption will be also made for the benchmark GW assignment method, ensuring a fair comparison. Nevertheless, the effect of imperfect ID detection will be fully modelled and evaluated in the extended work.

### III. PROBLEM FORMULATION

The considered optimization problem is formulated as maximizing the considered utility function $F(\mathbf{X})$, which expresses the average number of successfully demodulated device transmissions over all GWs, and $\mathbf{X} = (x_{ij})_{i \in \mathcal{E}, j \in \mathcal{G}}$ is the allocation matrix variable,

$$ \max_{\mathbf{X}} F(\mathbf{X}) = \max_{\mathbf{X}} \sum_{j=1}^{N_G} \sum_{i=1}^{N_E} x_{ij} a P_{ij}^{\text{cap}} \quad (4) $$

$$ \text{s.t. } C_1: \sum_{i=1}^{N_E} x_{ij} T_{ij} a P_{ij}^{\text{cap}} \le N_D T, \forall j \in \mathcal{G} \quad (4a) $$

$$ C_2: \sum_{j=1}^{N_G} x_{ij} = 1, \forall i \in \mathcal{E}. \quad (4b) $$

In Problem (4), $x_{ij}$ is the binary allocation variable, i.e., $x_{ij} = 1$ if device $i$ is assigned to GW $j$, and $x_{ij} = 0$ otherwise. Parameter $a$ is the transmission probability, i.e., the duty cycle. The capture probability between GW $j$ and device $i$ is given by (3). Constraint $C_1$ expresses the demodulators' constraint given a period of time $T$ at each GW $j$. Note that this constraint is expressed in time so as to reflect the dependency of a given packet's demodulation time to its SF. That is, the left hand side of $C_1$ gives the total incoming device transmissions to be demodulated within period $T$, where $x_{ij}T_{ij}$ is the payload duration of the desired signal from device $i$ at GW $j$, with a reception probability of $aP_{ij}^{\text{cap}}$. As $N_D$ is the number of demodulators at each GW, $N_D T$ gives the upper bound on the available demodulation time per GW. Note that $T$ is the period during which a given assignment solution is applied, and hence should not exceed tens or hundreds of milliseconds, given the inherent dynamics of wireless channel qualities, in particular in the case of mobile IoT applications. Finally, constraint $C_2$ imposes that transmissions of each device $i$ should be only demodulated by one GW, and discarded by GWs $j$ for which $x_{ij} = 0$. Thus, $C_2$ ensures that there are no redundant

demodulations, i.e., transmissions captured by multiple GWs should be only demodulated by one.

This is a binary allocation optimization problem with a Knapsack constraint, where each GW should compete to be assigned mutually exclusive sets of devices. This type of problem is known to be solved efficiently through the auction approach [7][14]. Therefore, we adopt this approach and propose the auction-based LoRa GW assignment algorithm next.

### IV. PROPOSED ALGORITHM

#### A. Proposed Auction-based GW Assignment

To exploit the auction-based approach where each GW bids for its preferred end-devices for solving Problem (4), we need to reformulate it as follows. Indeed, although constraint $C_1$ is separable among GWs, constraint $C_2$ is entangled among GWs, making it difficult to handle. By means of dual decomposition, the dual function $q(\mathbf{p})$ for constraint $C_2$ is defined as [14],

$$ q(\mathbf{p}) = \max_{\mathbf{X}} \sum_{j=1}^{N_G} \sum_{i=1}^{N_E} x_{ij} a P_{ij}^{\text{cap}} + \sum_{i=1}^{N_E} p_i (1 - \sum_{j=1}^{N_G} x_{ij}) \quad (5) $$

$$ \text{s.t. } C_1: \sum_{i=1}^{N_E} x_{ij} T_{ij} a P_{ij}^{\text{cap}} \le N_D T, \forall j \in \mathcal{G}, \quad (5a) $$

where $p_i$ is the dual variable corresponding to constraint $C_2$, giving the price of device $i$. The vector of prices is defined as $\mathbf{p} = [p_1, ..., p_i, ..., p_{N_E}]^T$, of size $N_E \times 1$. The dual optimization problem is hence written as,

$$ \min_{\mathbf{p}} \max_{\mathbf{X}} \sum_{j=1}^{N_G} \sum_{i=1}^{N_E} x_{ij} a P_{ij}^{\text{cap}} + \sum_{i=1}^{N_E} p_i (1 - \sum_{j=1}^{N_G} x_{ij}) \quad (6) $$

$$ \text{s.t. } C_1: \sum_{i=1}^{N_E} x_{ij} T_{ij} a P_{ij}^{\text{cap}} \le N_D T, \forall j \in \mathcal{G}. \quad (6a) $$

From the dual optimization problem (6), if the price vector $\mathbf{p}$ is fixed, its utility function will be maximized at each GW $j$ by solving for each vector $\mathbf{x}_j = [x_{1j}, ..., x_{N_E j}]^T$,

$$ \max_{\mathbf{x}_j} \sum_{i=1}^{N_E} x_{ij} (a P_{ij}^{\text{cap}} - p_i) \quad (7) $$

$$ \text{s.t. } C_1: \sum_{i=1}^{N_E} x_{ij} T_{ij} a P_{ij}^{\text{cap}} \le N_D T. \quad (7a) $$

In Problem (7), the payoff of each assignment is given by $aP_{ij}^{\text{cap}} - p_i$. To solve it, we propose the auction-based GW assignment method whose details are given in Algorithm 1. Initially, price $p_i$ and assignment $x_{ij}$ are set to zero. $N_I$ is the number of iterations required for convergence. In each iteration, there are three stages. In Stage 1, each GW bids for the devices with highest payoff. At iteration $k$, $v_{i'j}(k)$ and $v_{i''j}(k)$ are the highest payoff and the second highest payoff corresponding to devices $i'$ and $i''$, respectively. The bid $B_{ij}$ at iteration $k$ is defined as

$$ B_{i'j}(k) = p_{i'}(k) + v_{i'j}(k) - v_{i''j}(k) + \varepsilon, \quad (8) $$

where $0 < \varepsilon < 1$ is a bidding parameter which ensures that the price increases by at least $\varepsilon$ in each iteration. If $\varepsilon$ is larger, the algorithm converges faster but the objective value may be smaller. On the contrary, if $\varepsilon$ is smaller, the algorithm converges
**Algorithm 1** Auction Step of Proposed Algorithm

1: **Input:** $\mathcal{E}, \mathcal{G}, a, \delta_j, P_{ij}^{\text{cap}}, \forall (i, j) \in (\mathcal{E}, \mathcal{G})$

2: **Output:** $F, x_{ij}, \forall (i, j) \in (\mathcal{E}, \mathcal{G})$

3: **Initial:**

4: $p_i(1) = 0, \forall i$

5: $x_{ij} = 0, \forall i, j$

6: **for** $1 \le k \le N_I$, **do**

7: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\mathcal{E}$ is empty **then**

8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break

9: // Stage 1

10: **for** $j \in \mathcal{G}$ **do**

11: &nbsp;&nbsp;&nbsp;&nbsp;$v_{i'j}(k) = \max_i(aP_{ij}^{\text{cap}} - p_i(k))$

12: &nbsp;&nbsp;&nbsp;&nbsp;$v_{i''j}(k) = \max_{i \neq i'}(aP_{ij}^{\text{cap}} - p_i(k))$

13: &nbsp;&nbsp;&nbsp;&nbsp;$B_{i'j}(k) = p_{i'}(k) + v_{i'j}(k) - v_{i''j}(k) + \varepsilon$

14: // Stage 2

15: **for** $i \in \mathcal{E}$ **do**

16: &nbsp;&nbsp;&nbsp;&nbsp;$B_{ijmax} = \max_j B_{ij}$

17: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\sum_{i=1}^{N_E} x_{ijmax} T_{ijmax} a P_{ijmax} \le \delta_{jmax}$ **then**

18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$p_i(k+1) = B_{ijmax}$

19: // Stage 3

20: &nbsp;&nbsp;&nbsp;&nbsp;$F(k) = \sum_{j=1}^{N_G} \sum_{i=1}^{N_E} x_{ij} a P_{ij}^{\text{cap}}$

21: &nbsp;&nbsp;&nbsp;&nbsp;**if** $|F(k) - F(k-1)| < \eta$ ($0 < \eta \ll 1$), $k \ge 2$ **then**

22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$F = F(k)$

23: break

**Algorithm 2** Proposed Auction-based GW Assignment Algorithm: Prop. Auction Alg.

1: **Input:** $\mathcal{E}, \mathcal{G}, P_{ij}^{\text{cap}}, \forall (i, j) \in (\mathcal{E}, \mathcal{G})$

2: **Output:** $F, x_{ij}, \forall (i, j) \in (\mathcal{E}, \mathcal{G})$

3: $\sum_{j=1}^{N_G} x_{ij} = 0, \forall i$

4: $\delta_j = N_D T, \forall j$

5: $F = \text{Algorithm 1}(\mathcal{E}, \mathcal{G}, a, \delta_j, P_{ij}^{\text{cap}})$

slower but the objective value will be larger. In Stage 2, the bids of each device are compared and the GW with the highest bid, i.e., $j^*$ wins this auction round. Given constraint $C_1$, the assignment to GW $j^*$ is allowed only if $C_1$ is met, namely if the required total demodulation time is lower than threshold $\delta_j$ given as input. In Stage 3, $f(k)$, i.e., the objective value at iteration $k$, is updated. Finally, convergence is achieved if the difference of the objective value between two iterations is smaller than a given $\eta$, $0 < \eta \ll 1$.

Next, based on Algorithm 1, we now present the overview of the proposed algorithm in Algorithm 2. Given the knowledge of the devices' locations and large-scale channel fading parameters, the index set $\mathcal{E}$ of devices and capture probabilities $P_{ij}^{\text{cap}}$ can be determined at the NS. $\delta_j = N_D T$ is the upper bound threshold of each GW $j$, which comes as an input to Algorithm 1. Algorithm 2 finally outputs the final assignment solution and the overall utility function's value.

## B. Proposed Auction-based GW Assignment with Grouping

In the proposed algorithm, GWs only bid for one device at every iteration. However, if the number of candidate devices

**Algorithm 3** Proposed Auction-based Assignment Algorithm with Grouping: Prop. Grouped Alg.

1: **Input:** $\mathcal{E}_g(m), \mathcal{G}, p_g(m) = \frac{1}{M}, m \in [1, M], \delta_j, P_{ij}^{\text{cap}}, \forall (i, j) \in (\mathcal{E}, \mathcal{G})$

2: $\mathcal{E} = \cup_{g=1}^M \mathcal{E}_g(m)$

3: **Output:** $F, x_{ij}, \forall (i, j) \in (\mathcal{E}, \mathcal{G})$

4: $\sum_{i=1}^{N_G} x_{ij} = 0, \forall j$

5: $\delta_j = N_D T, \forall j$

6: **for** $1 \le m \le M$ **do**

7: &nbsp;&nbsp;&nbsp;&nbsp;$F_g(m) = \text{Algorithm 1}(\mathcal{E}_g(m), \mathcal{G}, a, \delta_j p_g(m), P_{ij}^{\text{cap}})$

8: $F = \sum_{m=1}^M F_g(m)$

is large, the algorithm will be inefficient, as it may require tremendous time until convergence. To improve efficiency, a grouped auction-based method is proposed, whose details are given in Algorithm 3. In this case, all devices are divided into groups, for which auctions are run in parallel. Though many different groups may be considered, we here consider the simplest grouping based on random partitioning. Namely, all devices in $\mathcal{E}$ are randomly divided into $M$ groups. The index set of devices in group $m$ is denoted $\mathcal{E}_g(m)$. Note that the upper bound $\delta_j$ of $C_1$ also needs to be divided for each group, in order to satisfy the overall constraint $C_1$. To do so, we define $p_g(m) = \frac{1}{M}$ as the upper bound coefficient for group $m$, such that constraint $C_1$ applied to each group $m$ becomes $\delta_j p_g(m) = \frac{N_D T}{M}$ (input at Line 7). This allows each GW to bid for devices in each group in parallel, thereby making the algorithm more time-efficient, but at the cost of network performance. However, even for a small value of $M$ the efficiency of this grouped auction-based method is demonstrated in the next section.

## V. NUMERICAL EVALUATION

### A. Simulation settings

$N_G = 2$ GWs and $N_E = 5000$ devices are assumed to be deployed with GWs' coverage radius of $R = 1$ km as in [5]. Channels are assumed to follow Rayleigh fading, and the path loss exponent is fixed to $\alpha = 3$. To emulate dense concurrent transmissions, the transmission probability or duty cycle is deliberately fixed to a large value of $a = 10\%$. The simulations were averaged over 1000 random realizations of device positions. The number of iterations in the proposed auction algorithms were fixed to $N_I = 100$, and the number of groups to $M = 2$.

### B. Benchmark Methods

The following major benchmarks are considered.

1) **Conventional No-Selection (Conv.-NS):** No GW selection is made but the constraint on demodulators $C_1$ is considered. Thus, if there is a free demodulator, the newly incoming packet will be demodulated, otherwise it is discarded. Hence, a packet may be demodulated by several GWs simultaneously. If so, only the maximum capture probability over all successful GWs, and corresponding transmissions will be accounted for in the overall utility function.
<figure><img src="image_4.png" /><figcaption>Fig. 2. Total number of demodulated signals over GWs, devices ($T = 0.2s$)</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 3. Sum Rate Performance ($T = 0.2s$)</figcaption></figure>

2) **Conventional Random-Selection (Conv.-RS):** Each device is randomly allocated to each GW, with an equal number of devices per GW. Hence, both the constraint on demodulators $C_1$ and the GW assignment constraint $C_2$ are satisfied. As explained in Section II, perfect device ID detection is assumed at GWs for this benchmark scheme, thereby ensuring a fair comparison to the proposed method. The imperfect device ID detection will be fully addressed in the extended work.

3) **Upper Bound:** This gives the ideal performance where the number of demodulators is infinite, i.e., all signals from all devices are demodulated by all GWs. As in *Conv.-NS*, if a packet is demodulated by multiple GWs, only its maximum capture probability will be included in the utility function.

## C. Simulation Results

Fig. 2 shows the performance of all algorithms in terms of the utility function $F(\mathbf{X})$ defined in Section III, namely the average number of successfully demodulated frames over all GWs and devices, as a function of the distance between the two GWs and for a given demodulation period of $T = 0.2s$, during which an assignment solution is fixed as explained in Section III. It is observed that both *Conv.-NS* and *Conv.-RS* are largely outperformed by *Prop. Auction* and *Prop. Grouped* algorithms, with a slight increase of the gain of both proposed methods with distance. Although the performance of *Prop. Grouped* is slightly degraded as compared to that of *Prop. Auction* due to the parallelization of auction iterations, it remains significantly better than both benchmarks, under all inter-GW distances. In addition, the upper bound performance increases with distance.

<figure><img src="image_6.png" /><figcaption>Fig. 4. Time complexity ($d = 1.4\text{km}$)</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 5. Utility function against available demodulation time ($d = 1.4\text{km}$)</figcaption></figure>

This is because the interference among GWs reduces with distance, thereby increasing capture probabilities at both GWs and hence, the overall utility function.

Next, Fig. 3 shows the performance of all algorithms in terms of sum-rate, according to inter-GW distance, where the rates for each SF are given in Table I. Although sum-rate was not directly optimized by our proposed algorithms, they offer clear benefits. Even under high interferences (i.e., small inter-GW distance), the proposed methods largely outperform both benchmarks, while limiting performance reduction as compared to the upper bound. Remarkably, the throughput reduction of *Prop. Auction* is within 15% of the ideal throughput of *Upper Bound*. Figures 2 and 3 illustrate the benefits of the proposed auction-based method against random selection (*Conv.-RS*), but also against the method without any GW selection (*Conv.-NS*).

As the computational complexity of proposed algorithms is difficult to analyze directly, instead, comparisons are made in terms of average running time duration. The time durations of the proposed method are evaluated in Fig. 4(a). As a typical GW detects the CFO and STO during each preamble in proposed and *Conv.-RS* algorithms, the comparison is fair even if CFO and STO detection are not considered in the time complexity. Note that it is only compared to *Conv.-RS* since other benchmarks do not perform any assignment. Over the whole time period $T \le 3s$, proposed methods show much lower time complexity than *Conv.-RS* because of a higher assignment efficiency, as they require less iterations in order to reach the upper bound of constraint $C_1$. Thus, their total execution time over all iterations becomes smaller, even though the complexity
per iteration is larger, owing to the auction bidding procedures as shown in Fig. 4(b). Also, Prop. Grouped algorithm further reduces time complexity thanks to parallel processing.

Finally, all algorithms are compared in terms of the average number of successfully demodulated transmissions (utility function), for a fixed inter-GW distance of 1.4 km but for varying demodulation periods $T$, where larger $T$ entails a looser constraint $C_1$. From Fig. 5, all algorithms except Conv.-RS tend to approach the upper bound as $T$ grows, since $C_1$ becomes less constraining, with a slightly slower convergence for Prop. Auction method. Conv.-RS already saturates at $T = 1$s and cannot reach Upper Bound due to the random assignment for enforcing constraint $C_2$, making it unable to exploit the multi-path diversity offered by the multi-GW environment. Given the inherent dynamics of wireless channels, especially in the case of mobile IoT devices, reasonable values of $T$ are in the order of tens or hundreds of milliseconds.

From all the above, both proposed methods outperform both benchmark schemes, jointly in terms of number of demodulated transmissions and sum-rate, with limited time complexity, over a large range of practical values of $T$.

## VI. CONCLUSION

We investigated the problem of gateway selection in a LoRa multi-gateway network, where, unlike most existing works, the constraint of limited number of demodulators was considered. The problem was mathematically formulated as an assignment problem with a Knapsack constraint. This enabled us to propose an auction-based algorithm for maximizing the average number of successfully demodulated device transmissions. To improve the convergence time, a device grouping method was also proposed. Numerical results illustrated the large performance gains of proposed methods against major benchmarks, both in terms of successfully demodulated signals and sum-rate, while the most substantial gains were achieved within demodulation delays suitable for mobile LoRa IoT applications.

In the future work, the proposed algorithms will be evaluated under more complex situations, including errors due to imperfect device identification. Additionally, the proposed approaches will be extended for distributed optimization.

## APPENDIX

### A. Derivation of collision overlap time

Assume $T_{ij}$ is the packet duration of desired signal and $T_{lj}$ is the packet duration of interference. For $T_{ij} > T_{lj}$,

$$h_{lj}(\tau_{il}) = \begin{cases} \frac{T_{lj}}{T_{ij}}, & 0 \le \tau_{il} < T_{ij} - T_{lj} \\ \frac{T_{ij} - \tau_{il}}{T_{ij}}, & T_{ij} - T_{lj} \le \tau_{il} < T_{ij} \\ 0, & \tau_{il} \ge T_{ij} \end{cases} \quad (9)$$

$$E_{\tau}[h_{lj}(\tau_{il})] = \int_{0}^{T_{ij}-T_{lj}} \frac{T_{lj}}{T_{ij}} \frac{1}{T_c} d\tau_{il} + \int_{T_{ij}-T_{lj}}^{T_{ij}} \frac{T_{ij}-\tau_{il}}{T_{ij}} \frac{1}{T_c} d\tau_{il} = \frac{T_{lj}^2}{2T_{ij}T_c} \quad (10)$$

$$\text{For } T_{ij} \le T_{lj}, \quad h_{lj}(\tau_{il}) = \begin{cases} \frac{T_{ij}-\tau_{il}}{T_{ij}}, & 0 \le \tau_{il} < T_{ij} \\ 0, & \tau_{il} \ge T_{ij} \end{cases} \quad (11)$$

$$E_{\tau}[h_{lj}(\tau_{il})] = \int_{0}^{T_{ij}} \frac{T_{ij}-\tau_{il}}{T_{ij}} \frac{1}{T_c} d\tau_{il} = \frac{T_{ij}}{2T_c} \quad (12)$$

### B. Derivation of capture probability

The capture probability expressed in Eq. (3) of Section II is derived as

$$\begin{aligned} & \mathrm{Pr} \left( \frac{P_i^{\mathrm{Tx}} g_{ij} r_{ij}^{-\alpha}}{\sum_{l=1, l \neq i}^{N_E} P_l^{\mathrm{Tx}} g_{lj} r_{lj}^{-\alpha} h_{lj}(\tau_{il}) + \sigma^2} > \Gamma_{ij} \right) \\ &= \int_0^\infty \dots \int_0^\infty \mathrm{Pr} \left( \frac{P_i^{\mathrm{Tx}} g_{ij} r_{ij}^{-\alpha}}{\sum_{l=1, l \neq i}^{N_E} P_l^{\mathrm{Tx}} g_{lj} r_{lj}^{-\alpha} h_{lj}(\tau_{il}) + \sigma^2} > \Gamma_{ij} \right. \\ & \qquad \left. |g_{1j} \dots g_{NEj}| p(g_{1j} \dots g_{NEj}) dg_{1j} \dots dg_{NEj} \right) \\ &= \int_0^\infty \dots \int_0^\infty \mathrm{Pr} \left( g_{ij} > \frac{\Gamma_{ij}}{P_i^{\mathrm{Tx}} r_{ij}^{-\alpha}} \left( \sum_{l=1, l \neq i}^{N_E} P_l^{\mathrm{Tx}} g_{lj} r_{lj}^{-\alpha} h_{lj}(\tau_{il}) + \sigma^2 \right) e^{-g_{1j}} \dots e^{-g_{NEj}} \right) dg_{1j} \dots dg_{NEj} \\ &= \int_0^\infty \dots \int_0^\infty e^{-\frac{\Gamma_{ij} \sigma^2}{P_i^{\mathrm{Tx}} r_{ij}^{-\alpha}}} \prod_{l=1, l \neq i}^{N_E} e^{-\Gamma_{ij} \left( \frac{P_l^{\mathrm{Tx}}}{P_i^{\mathrm{Tx}}} \right) \left( \frac{r_{lj}}{r_{ij}} \right)^{-\alpha} h_{lj}(\tau_{il})} dg_{1j} \dots dg_{NEj} \\ &= e^{-\frac{\Gamma_{ij} \sigma^2}{P_i^{\mathrm{Tx}} r_{ij}^{-\alpha}}} \prod_{l=1, l \neq i}^{N_E} \int_0^\infty e^{-(\Gamma_{ij} \left( \frac{P_l^{\mathrm{Tx}}}{P_i^{\mathrm{Tx}}} \right) \left( \frac{r_{lj}}{r_{ij}} \right)^{-\alpha} h_{lj}(\tau_{il}) + 1)} dg_{lj} \\ &= e^{-\frac{\Gamma_{ij} \sigma^2}{P_i^{\mathrm{Tx}} r_{ij}^{-\alpha}}} \prod_{l=1, l \neq i}^{N_E} \frac{1}{\Gamma_{ij} \left( \frac{P_l^{\mathrm{Tx}}}{P_i^{\mathrm{Tx}}} \right) \left( \frac{r_{lj}}{r_{ij}} \right)^{-\alpha} h_{lj}(\tau_{il}) + 1} \end{aligned}$$

## REFERENCES

[1] C. Gouraud and J. M. Gorce, “Dedicated Networks for IoT: PHY/MAC State of the Art and Challenges,” EAI Endorsed Trans. on IoT, vol. 1, no. 1, Oct. 2015.

[2] L. Amichi, M. Kaneko, E. H. Fukuda, N. E. Rachkidy, A. Guitton, “Joint Allocation Strategies of Power and Spreading Factors with Imperfect Orthogonality in LoRa Networks,” IEEE Trans. on Commun., vol. 68, no. 6, June 2020.

[3] F. Benkhelifa, Z. Qin, J. A. McCann, “User Fairness in Energy Harvesting-based LoRa Networks with Imperfect SF Orthogonality,” IEEE Trans. on Commun., vol. 69, no. 7, pp. 4319–4334, Mar. 2021.

[4] Semtech, “SX1301 - Digital Baseband Chip LoRaWAN Macro Gateways,” Wireless & Sensing Products, datasheet v.2.4, 06 2017.

[5] A. Guitton, M. Kaneko, “Improving LoRa Scalability by a Recursive Reuse of Demodulators.”

[6] R. B. Sorensen, N. Razmi, J. J. Nielsen, and P. Popovski, “Analysis of LoRaWAN Uplink with Multiple Demodulating Paths and Capture Effect,” in IEEE ICC, May 2019.

[7] D. P. Bertsekas, “The Auction Algorithm: A Distributed Relaxation Method for the Assignment Problem,” Annals of Operations Research, vol. 14, no. 1, pp. 105–123, Dec. 1988.

[8] A. Guitton and M. Kaneko, “Multi-gateway demodulation in LoRa,” in IEEE Globecom, Dec. 2022.

[9] A. Waret, M. Kaneko, A. Guitton, N. E. Rachkidy, “LoRa Throughput Analysis with Imperfect Spreading Factor Orthogonality,” IEEE Wireless Commun. Letters, vol. 8, no. 2, pp. 408–411, Apr. 2019.

[10] M. Xhonneux, O. Afisiadis, D. Bol, and J. Louveaux, “A Low-Complexity LoRa Synchronization Algorithm Robust to Sampling Time Offsets,” IEEE IoT Journal, vol. 9, no. 5, pp. 3756–3769, 2022.

[11] R. Eletreby, D. Zhang, S. Kumar, and O. Yagan, “Empowering Low-Power Wide Area Networks in Urban Settings,” in Proc. of ACM SIGCOMM, 2017, pp. 309–321.

[12] X. Xia, Y. Zheng, and T. Gu, “FTrack: Parallel Decoding for LoRa Transmissions,” IEEE/ACM Trans. on Networking, vol. 28, no. 6, pp. 2573–2586, Dec. 2020.

[13] M. C. Borja and J. Haigh, “The Birthday Problem,” Significance, The Royal Statistical Society, vol. 4, no. 3, pp. 124–127, Aug. 2007.

[14] L. Luo, N. Chakraborty, K. Sycara, “Provably Good Distributed Algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks,” IEEE Trans. Robot., vol. 31, no. 1, pp. 19–30, Feb. 2015.