# Optimal Data Collection Time in LoRa Networks--A Time-Slotted Approach
## 5 The Optimal Data Scheduling Problem  
In this section, we formulate the optimal data scheduling problem, that is the optimal arrangement of nodes' transmissions into slots and frames. This formulation does not take into account acknowledgements since (a) acknowledgments are optional, and (b) the size of the acknowledgements is dynamic and depends on the actual number of nodes and the number of received packets in the frame. Moreover, acknowledgements are natively supported by the frame structure of TS-LoRa in the SACK packet which can be easily added into the following formulation. Nevertheless, for fair compare reasons of the optimal solution with the Aloha (which considerably suffers for the downlink traffic [33]), we skip its formulation. The network is composed of a set of \(N\) nodes. Depending on the distance of a node \(i\) from the gateway, a set of possible SFs \(\mathcal{F}_{i}\) is required and is allocated during the registration of the node with the gateway. For example, if a node can reach the gateway with SF7, all higher SFs will also allow the node to reach the gateway and can be used for different transmissions of the node in the schedule. Each node \(i\) has an amount of data to transmit, denoted by \(pkt_{i}\). Each transmission of \(i\) can be scheduled using a SF \(f\) (\(f\in\mathcal{F}_{i}\)) with an associated payload \(payload_{f}\). Given \(f\) and \(payload_{f}\), we can calculate the packet transmission time \(T_{f}\)[34]. Let \(F=\{\mathcal{7},\,\ldots,\,12\}\) be the set of available spreading factors. To each SF \(f\in F\), we associate a set \(\mathcal{T}_{f}=\{t_{f}^{f},\,1\leq j\leq\Gamma\}\) of time slots starting at time \(j\), where \(\Gamma\) is the global  
Figure 3: Different slot and SF allocations of three transmissions with the same packet length and SF7: (a) no extra scheduling is performed. All nodes are serially placed in slots of the SF7 frame one after the other. This is a sub-optimal solution in terms of data collection time. (b) Node C is switched to SF8 frame. This is the optimal solution since it results to minimum data collection time. (c) Node B is switched to SF8 frame and Node C to SF9 frame. This is also a sub-optimal solution. upper limit in number of slots. These slots have duration \(T_{f}+2\tau\) for the given node's payload and SF, where \(\tau\) corresponds to the guard time. We associate a set of forbidden slots \(\chi_{t^{f}_{j}}\) to each slot \(t^{f}_{j}\). This set contains all the slots \(t^{f^{\prime\prime}}_{j}\) of the same SF (i.e., \(f^{\prime}=f\)), and of other SFs (i.e., \(f^{\prime}\
eq f\)) such that \(j\leq j^{\prime}\leq j+100T_{f}\), for 1% duty cycle. If a node uses \(t^{f}_{j}\) to transmit data, then the duty cycle restriction forbids the node to use any slot in \(\chi_{t^{f}_{j}}\). Apparently, this constraint can be eliminated when no radio duty cycle restrictions exist. Given the previous input parameters of the problem, we define the following set of binary variables:  
\[y^{i}_{t^{f}_{j}}=\left\{ \begin{array}{ll}1&\text{if node $i$ uses slot $t^{f}_{j}$},\\ 0&\text{otherwise}\end{array} \right.\]  
The linear program to optimally schedule bulk data transmissions is defined as follows:  
\[\min\bigg{(}\max_{f\in F,\ t^{f}_{j}\in\mathcal{T}_{f}}(j+\tau+T_{f})\sum_{i} y^{i}_{t^{f}_{j}}\bigg{)} \tag{6}\]  
subject to:  
\[\sum_{i\in N}y^{i}_{t^{f}_{j}}\leq 1,\ \forall f\in F,t^{f}_{j}\in\mathcal{T} _{f} \tag{7}\]  
\[\sum_{f\in\mathcal{F},\mathcal{F}_{i}}\sum_{t^{f}_{j}\in\mathcal{T}_{f}}y^{i}_ {t^{f}_{j}}=0,\ \forall i\in N \tag{8}\]  
\[\sum_{f\in\mathcal{F}_{i}}\sum_{t^{f}_{j}\in\mathcal{T}_{f}}payload_{f}y^{i}_ {t^{f}_{j}}\geq pkt_{i},\ \forall i\in N \tag{9}\]  
\[y^{i}_{t^{f}_{j}}+y^{i}_{t^{f}_{j}}\leq 1,\ \forall i\in N,f\in\mathcal{F}_{i},t^ {f}_{j}\in\mathcal{T}_{f},t^{f^{\prime\prime}}_{j}\in\chi_{t^{f}_{j}}. \tag{10}\]  
The objective function (6) seeks to minimise the length of the longest frame among all SFs.