Dimitrios Zorbas
email: dimitrios.zormpas@tyndall.ie

Christelle Caillouet
email: christelle.caillouet@univ-cotedazur.fr

Abdelfadeel Khaled

Dirk Hassan
email: k.hassan@cs.ucc.ie

Pesch

Khaled Q Abdelfadeel

Dirk Pesch
email: d.pesch@cs.ucc.ie.

Fast Data Collection in LoRa Networks: a Time-Slotted Approach

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

LoRa is a widely used long range communication technology for the Internet of Things (IoT). It uses a proprietary spread spectrum modulation currently owned by Semtech [START_REF]LoRa Modulation Basics[END_REF]. It can trade data rate with coverage using multiple Spreading Factors (SF) which typically range from 7 to 12. Depending on the SF value, the channel bandwidth (BW) as well as other modulation characteristics, LoRa can achieve a data rate of up to approximately 22kbps. The higher the SF and the lower the channel bandwidth, the lower the data rate and, thus, the longer the transmission time. Moreover, parallel transmissions performed on different SFs but on the same channel can be simultaneously decoded by the gateway. LoRa mainly uses license-free sub-gigahertz radio frequency bands (e.g., EU868, US915 [START_REF]LoRa Modulation Basics[END_REF]) that are imposed to radio duty cycle regulations. For example, in EU the nodes are allowed to transmit up to 1% of the time. However, LoRa chips for the 2.4GHz band have recently been announced by Semtech. All those characteristics in addition to its resistance to potential external interference make LoRa an easy-to-use wireless data collection solution in agriculture, environmental monitoring, and smart-city applications [START_REF] Haxhibeqiri | A Survey of LoRaWAN for IoT: From Technology to Application[END_REF].

The current LoRa-based protocol, called LoRaWAN, provides registration, security, and acknowledgement services for LoRa-enabled IoT devices [START_REF]LoRaWAN™[END_REF]. A LoRaWAN architecture consists of (a) a core -usually wired -network which implements mechanisms to provide the above mentioned services, (b) one or more gateways, and (c) the IoT devices (end-nodes). The end-nodes can reach the gateway(s) in a single hop. In order to achieve high energy-efficiency and low implementation complexity, LoRaWAN does not perform any specific medium access policy for uplink transmissions. In fact, a Pure Aloha transmission policy is adopted [START_REF] Abramson | THE ALOHA SYSTEM: another alternative for computer communications[END_REF]. To increase the probability of packet delivery, multiple gateways can be deployed at different areas. However, it has been shown that LoRaWAN presents a high number of collisions and decreased performance in presence of high number of nodes [START_REF] Bor | Do LoRa Low-Power Wide-Area Networks Scale?[END_REF][START_REF] Georgiou | Low Power Wide Area Network Analysis: Can LoRa Scale[END_REF], especially for confirmed traffic [START_REF] Capuzzo | Confirmed Traffic in LoRaWAN: Pitfalls and Countermeasures[END_REF].

However, a common problem that occurs in rural areas, as well as in specific deployments such as in mines [START_REF] Zhang | An integrated environment monitoring system for underground coal mines-Wireless sensor network subsystem with multi-parameter monitoring[END_REF] and in forests [START_REF] Aslan | A framework for use of wireless sensor networks in forest fire detection and monitoring[END_REF], is the lack of a seamless power source to allow the installation of multiple gateways as well as their interconnection with a core network infrastructure. Even in the case where solar-powered gateways are employed, their availability depends on the weather conditions, thus, the seamless operation cannot always be guaranteed. In this paper, we assume such a scenario, where the gateway is not available at all times but it can be turned on periodically to carry out the data collection. The problem of gateway unavailability also appears in low orbit LoRa satellites [START_REF] Qu | LEO satellite constellation for Internet of Things[END_REF].

Since a satellite gateway can provide coverage to only a part of earth's surface at every time, only a few nodes can successfully upload data in real time.

Since many typical applications in agriculture or in environmental monitoring are not time-critical, a solution to the gateway unavailability problem is to allow sensing nodes to buffer their data in on-board storage and transmit it in bulk when the gateway becomes available. Since the bulk data collection may have to be achieved as fast as possible, nodes tend to transmit their packets with a high rate, which may saturate the channel. In this case, an Aloha-based approach fails to achieve a high delivery ratio due to high number of collisions. However, in the use cases under consideration, we assume that data traffic is somewhat predictable and, thus, efficient scheduling of transmissions in time slots without significant overhead can be achieved in order to reduce or eliminate collisions and reduce the data collection time.

Nevertheless, the problem under consideration requires a computation and dissemination of the schedule. Both schedule computation and dissemination are two very challenging problems because (a) the schedule has to be as efficient as possible in terms of data collection time, (b) as compact as possible in terms of size, and (c) to be transmitted to the nodes as quickly as possible over low-rate and duty cycle-restricted radios.

In our previous work [START_REF] Zorbas | Offline Scheduling Algorithms for Time-Slotted LoRa-based Bulk Data Transmission[END_REF], we investigated the gains of using two centralised scheduling algorithms when the number of nodes and their transmission settings (e.g., reliable SFs) are known. The proposed algorithms assign SFs and allocate time slots for transmissions, aiming at generating collision-free schedules with the minimum possible data collection time. The missing parts of that work were that (a) no theoretical background of the Aloha-based data collection methods was provided. (b) The proposed heuristics did not provide any performance guarantees while there was no comparison with the optimal solution even for small-scale scenarios. Moreover, (c) it neglected the assessment of the transmission of the schedule to nodes which constitutes one of the major problems in LoRa networks scheduling. Finally, (d) the solutions were not experimentally validated. Hence, in this paper, we extend our previous work to add the following contributions:

(1) We describe the weaknesses of an Aloha MAC for efficient bulk data collection and we formulate the problem of finding the minimum transmission rate to achieve a certain success probability of packet delivery for each node.

This transmission rate provides the lower bound of the bulk data collection time in Aloha approaches.

(2) We formulate and solve the optimal time-slotted scheduling problem that minimises the data collection time in LoRa-based networks.

(3) We implement a prototype of the proposed approach in a proof-of-concept to assess the practicality and performance of the schedule dissemination time and the ability of the nodes to compute the schedule with their own resources.

The rest of the paper is organised as follows: Section 2 surveys recent related works. Section 3 introduces the bulk data collection problem and describes the limitations of the Aloha MAC in this context. In Section 4, we present preliminary information regarding time-slotted communications and in Section 5 we formulate the optimal scheduling optimisation problem. Section 6 presents theoretical and simulation results, while Section 7 describes how a proof of concept was realised along with experimental results from the testbed. Finally, Section 8 concludes the paper and presents ideas for future directions.

RELATED RESEARCH

The bulk data transmission problem has been investigated in the literature in the context of opportunistic or delay tolerant networks [START_REF] Pelusi | Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[END_REF]. Different types of communication protocols have been used, from IEEE802.11 [START_REF] Li | Block-switched Networks: A New Paradigm for Wireless Transport[END_REF] to IEEE802.15.4 [START_REF] Kim | Flush: A Reliable Bulk Transport Protocol for Multihop Wireless Networks[END_REF] and RFIDs [START_REF] Gummeson | Flit: A bulk transmission protocol for RFID-scale sensors[END_REF]. In contrast to those technologies, our work focuses on the data collection from devices placed in large geographical areas, thus, a long range protocol such as LoRa is required. Supporting bulk data transmissions over LoRa-based networks is constrained by various limitations and unique characteristics (e.g. duty cycle, multiple pseudo-orthogonal spreading factors, etc.) that do not apply to other conventional networking solutions.

We have recently studied the bulk data collection problem in LoRa-based networks from different perspectives [START_REF] Abdelfadeel | 𝐹 𝑅𝐸𝐸-Fine-Grained Scheduling for Reliable and Energy-Efficient Data Collection in LoRaWAN[END_REF][START_REF] Zorbas | Offline Scheduling Algorithms for Time-Slotted LoRa-based Bulk Data Transmission[END_REF][START_REF] Zorbas | Fast and Reliable LoRa-based Data Transmissions[END_REF][START_REF] Zorbas | Autonomous Collision-Free Scheduling for LoRa-based Industrial Internet of Things[END_REF]. In [START_REF] Abdelfadeel | 𝐹 𝑅𝐸𝐸-Fine-Grained Scheduling for Reliable and Energy-Efficient Data Collection in LoRaWAN[END_REF][START_REF] Zorbas | Offline Scheduling Algorithms for Time-Slotted LoRa-based Bulk Data Transmission[END_REF], heuristic approaches were proposed to compute the time-slotted schedule with online and offline schemes, respectively. The offline approach assumes that a set of information such as the number of devices and their SFs is known in advance by the gateway. In contrast, in the online approach [START_REF] Abdelfadeel | 𝐹 𝑅𝐸𝐸-Fine-Grained Scheduling for Reliable and Energy-Efficient Data Collection in LoRaWAN[END_REF], only partial knowledge is assumed, allowing this approach to adapt to dynamic changes such as frequent topology changes. Nevertheless, this comes at the expense of higher energy consumption and longer data collection time than the offline approach. Both approaches are centralized, where the schedule is computed at the gateway and disseminated to the end devices. An alternative approach was proposed for Industrial IoT deployments [START_REF] Zorbas | Autonomous Collision-Free Scheduling for LoRa-based Industrial Internet of Things[END_REF], where the authors investigated a decentralized approach, where end devices can autonomously compute their schedule by receiving the minimum possible information from the gateway. This work was designed to meet specific industrial network criteria, such as fast joining times, low power consumption, and low overhead. However, the schedule length tends to increase substantially as the number of devices increases, which greatly increases the data collection time. Finally, the problem of collecting data using LoRaWAN over a single channel was examined [START_REF] Zorbas | Fast and Reliable LoRa-based Data Transmissions[END_REF]. In this work, optimal SF assignments are proposed so that the average probability of successful packet delivery is maximized. However, this approach is still Aloha-based and does not eliminate collisions.

Unlike the previous works, in this paper, we present the complete picture of the bulk data collection problem, we formulate and solve the optimal scheduling problem to minimize the data collection time considering collision-free scheduling and allocation of SFs, and we study practical implementation aspects such as the schedule transmission.

We rely on a time-slotted MAC approach to enable efficient bulk data transmissions in LoRa-based networks. In the literature, similar MAC approaches have been considered as they typically offer higher reliability than Pure Aloha [START_REF] Beltramelli | LoRa beyond ALOHA: An Investigation of Alternative Random Access Protocols[END_REF].

In [START_REF] Gao | A Multichannel Low-Power Wide-Area Network With High-Accuracy Synchronization Ability for Machine Vibration Monitoring[END_REF][START_REF] Lee | A Scheduling Algorithm for Improving Scalability of LoRaWAN[END_REF][START_REF] Reynders | Improving Reliability and Scalability of LoRaWANs Through Lightweight Scheduling[END_REF], various time-slotted MAC strategies are used to mitigate the collisions in dense LoRa/LoRaWAN networks and, thus, improve their scalability. Similar MAC strategies are also considered in [START_REF] Bonafini | Exploiting localization systems for LoRaWAN transmission scheduling in industrial applications[END_REF][START_REF] Lam Hoang | A Real-Time LoRa Protocol for Industrial Monitoring and Control Systems[END_REF][START_REF] Leonardi | Industrial LoRa: A novel medium access strategy for LoRa in industry 4.0 applications[END_REF][START_REF] Rizzi | Using LoRa for industrial wireless networks[END_REF] to meet the requirements of soft real-time industrial applications. In [START_REF] Abrardo | A multi-hop LoRa linear sensor network for the monitoring of underground environments: the case of the Medieval Aqueducts in Siena, Italy[END_REF][START_REF] Ebi | Synchronous LoRa Mesh Network to Monitor Processes in Underground Infrastructure[END_REF][START_REF] Dinh | Multi-Hop LoRa Network Protocol with Minimized Latency[END_REF], time slots are used to enable low-power multi-hop communications in LoRa-based networks to extend the coverage in harsh environments like underground deployments. In addition to that, the Time Slotted Channel Hoping mechanism of the IEEE802.15.4e standard is employed to enable LoRa-based mesh networking [START_REF] Haubro | TSCH-over-LoRA: Long Range and Reliable IPv6 Multi-hop Networks for the Internet of Things[END_REF]. Unlike the profound advantages of the aforementioned time-slotted solutions in terms of reduced packet collisions, they can barely be used for bulk data collection because of the absence of a scheduler to allocate slots to the nodes or because they follow a slotted-Aloha approach which does not eliminate collisions. Since in bulk data collection, the nodes tend to use a high data rate to quickly expedite all transmissions, non collision-free approaches may suffer for long data collection times.

THE PROBLEM OF BULK DATA COLLECTION

In this section, we describe some general requirements to achieve bulk data collection and we present a theoretical uplink analysis of an Aloha-based LoRa MAC to show that the average data collection time increases exponentially with the number of nodes.

Requirements

In order to achieve bulk data collection, as the gateway cannot be available at all times, a mechanism to (almost) simultaneously wake up the nodes once the gateway becomes available must exist. A simple way to achieve that is to schedule the data collection process at predefined times. Apparently, due to the clock drift of the nodes, some of them will wake up earlier than others. Taking into account experimental data from our previous work [START_REF] Zorbas | TS-LoRa: Time-slotted LoRaWAN for the Industrial Internet of Things[END_REF], the maximum clock drift does not exceed 100ppm, which is translated to a few seconds of time assuming that the data collection is executed once per day. However, having in mind that the data collection may take several hours to be completed (see experimental results in Section 6), the waking up waiting cost is negligible compared to the duration of the data collection. The gateway can initiate the data collection process after this short period of time. In the case of non-coordinated transmissions, such as in an Aloha approach, this can happen by simply sending an initialisation packet. However, if the transmissions are time-synchronised, the gateway needs to compute the schedule and send it to the nodes before starting the data collection. As we already mentioned, the computation and the transmission of the schedule are two critical operations that may considerably affect the reliability of the system as well as the data collection time. These two operations are the two main research subjects of the current paper.

Moreover, since the gateway is expected to be online for multiple hours per day, new nodes can periodically wake up and register in the gateway. If the gateway is not present at that time, the node can return to sleep mode and wake up at a future time to try to register again. Since a gateway system consists of multiple transceivers and the registration takes place at a different frequency, registrations do not affect the data collection process. As a consequence, even if a joining node tries to register during the data collection phase, the latter would not be interrupted/interfered by the registration activity. Registrations can also get accelerated by considering a similar to LoRaWAN's personalised activation (ABP). In this case, the gateway is aware of the new nodes while the corresponding DevAddr as well as the security keys can be stored in the devices.

Data Collection Using a Pure & Slotted Aloha MAC

In this subsection, we formulate a data collection time minimisation problem, as a function of the minimum required transmission rate and a given success probability of delivery. We show that reliable bulk data collection in Aloha (Pure and Slotted) cannot be achieved in a short amount of time even for a low number of nodes.

At this point, we define a set of notations that are needed for the rest of the text. These notations as well as their meaning are summarised in Table 1.

Aloha-based MAC protocols, such as the LoRaWAN, do not apply any mechanism to regulate packet transmissions. Indeed, each node transmits its packets whenever data are available and the duty cycle is obeyed. In this case, some of the packets are delivered while others are lost due to collisions. Specifically, the collision rate depends on this transmission rate. For example, allowing the nodes to transmit in sparse intervals decreases the collisions but prolongs the data collection time. Assuming that all nodes transmit the same amount of packets 𝑝𝑘𝑡, the average data collection time is then equal to 𝑝𝑘𝑡/𝜃 , where 𝜃 is the packet transmission rate. In order to model an Aloha MAC behaviour for the bulk data collection scenario, we assume that all nodes' packets are equal in length and their transmissions follow a Poisson distribution with intensity 𝜃 packets/sec. Assuming the best-case scenario of no inter-SF collisions, transmissions only collide when they overlap in SF, time, and power [START_REF] Bor | Do LoRa Low-Power Wide-Area Networks Scale?[END_REF]. Given the analysis provided in [START_REF] Zorbas | Fast and Reliable LoRa-based Data Transmissions[END_REF], if a node at distance 𝑥 from the gateway transmits a packet with SF 𝑓 , the transmission will be successful if it does not overlap with any other packets in the network having the same SF within the transmission time 𝑇 𝑓 . Alternatively, due to the capture effect, the packet can be decoded if the received power of other packets with the same SF is less than the current one by at least 𝑃 thld . As shown in Figure 1, considering a log-distance path loss model, the potential interfering nodes are those whose distance from the gateway is below 𝑥𝑅

with 𝑅 = 10 𝑃 thld 10𝛾 > 1 [34],
where 𝛾 is the path loss exponent. Consequently, given a uniform distribution of nodes with SF 𝑓 , the number of potential interfering nodes is

𝑁 𝑓 𝜋 (min(𝑅𝑥,𝑑)) 2 𝜋𝑑 2
, where 𝑁 𝑓 is the number of nodes with SF 𝑓 and 𝑑 is the range of the deployment for the given SF. The probability of successful delivery 𝑃 𝑓 (𝑥) is that within a vulnerability period with duration 2𝑇 𝑓 , none of those potential interfering nodes starts a transmission. Hence, we have:

𝑃 𝑓 (𝑥) = 𝑒 -2𝑇 𝑓 𝜃 𝑁 𝑓 (min(𝑥𝑅, 𝑑)) 2 𝑑 2 . ( 1
)
The shorter the distance 𝑥 to the gateway, the higher the probability 𝑃 𝑓 (𝑥) of success delivery due to less interferers.

The worst case situation appears for nodes that are on the border of the deployment range (i.e., 𝑥 → 𝑑). In this case, all nodes with the same SF are potential interferers and the minimum success probability 𝑃 𝑚𝑖𝑛 𝑓 is then equal to

𝑃 𝑚𝑖𝑛 𝑓 = 𝑒 -2𝑇 𝑓 𝜃 𝑁 𝑓 .
As the transmission rate of the nodes decreases, the success probability increases, but so does the data collection time. This means that there is a certain (maximum) transmission rate 𝜃 𝑚𝑎𝑥 that satisfies a minimum success probability for all the nodes in the network. The question that arises is how long is the data collection time given this rate and the desired minimum allowed success probability?

In order to answer this question, we formulate the following optimisation problem:

max 𝜃, (2)
𝑠𝑢𝑏 𝑗𝑒𝑐𝑡 𝑡𝑜 :

𝑝𝑘𝑡 𝑘=𝜌 𝑝𝑘𝑡 𝑘 𝑃 𝑚𝑖𝑛 𝑓 𝑘 1 -𝑃 𝑚𝑖𝑛 𝑓 𝑝𝑘𝑡 -𝑘 ≥ 𝑃 𝑔𝑖𝑣𝑒𝑛 , (3)
𝑃 𝑚𝑖𝑛 𝑓 = 𝑒 -2𝑇 𝑓 𝜃 𝑁 𝑓 , (4)
𝜃𝑇 𝑓 ≤ 𝐶. (5)
Constraint (3) requires that the probability of "at least 𝜌 packets (i.e., 𝜌 ∈ N * , 𝜌 ≤ 𝑝𝑘𝑡) are successfully delivered" is greater than or equal to a given value 𝑃 𝑔𝑖𝑣𝑒𝑛 , and 𝑝𝑘𝑡𝑁 𝑓 is large enough. Constraint [START_REF] Beltramelli | LoRa beyond ALOHA: An Investigation of Alternative Random Access Protocols[END_REF] guarantees that the duty cycle constraint 𝐶 is not exceeded (if there is no duty cycle restriction then 𝐶 = 1, e.g., in 2.4GHz LoRa). We must note that in presence of a slotted-Aloha protocol, the vulnerability period reduces from 2𝑇 𝑓 to 𝑇 𝑓 . Thus, Constraint (4) can be modified accordingly.

The solution of the optimisation problem gives the theoretical upper bound for the transmission rate (i.e., 𝜃 𝑚𝑎𝑥 ) and, hence, the lower bound for the required data collection time. The example of Figure 2 depicts the theoretical data collection time for a scenario with 100 to 1000 nodes and a minimum transmission success probability of 0.9. All nodes use a 100-byte packet size, transmit 100 packets, and reach the gateway with SF7. We can observe that the data collection may take several hours even for low node numbers. This is because the data collection time depends on the packet rate 𝜃 which is computed by solving the aforementioned optimization problem. As the number of nodes increases, the number of collisions increase as well. That means that 𝜃 has to be increased considerably in order to make transmissions sparser and, thus, reduce the number of collisions. It is obvious from this analysis that an Aloha MAC (Pure or Slotted) cannot achieve a reliable bulk data collection in a reasonable period of time. We should mention that optimally assigning SFs such that the probability of delivery is maximised, can alleviate the problem of collisions [START_REF] Zorbas | Fast and Reliable LoRa-based Data Transmissions[END_REF]. However, even in this case the data collection time remains very long.

TOWARDS TIME-SLOTTED LORA COMMUNICATIONS

In this section, we briefly describe the proposed time-slotted LoRa architecture consisting of frames, time slots, and a schedule.

Time slots, frames, and synchronisation

The current work uses the same frame design as TS-LoRa [START_REF] Zorbas | TS-LoRa: Time-slotted LoRaWAN for the Industrial Internet of Things[END_REF]. TS-LoRa is a time-slotted protocol for industrial IoT using LoRa as the physical layer. According to TS-LoRa, the time is divided into repeated frames where each frame consists of a number of time slots. Each time slot accommodates the transmission of one node. Assuming packets of equal size and the fact that the transmission time increases with higher SFs, the length of the time slots is the same only for packets transmitted with the same SF. This allows TS-LoRa to have 6 parallel frames where each frame accommodates transmissions of nodes using the same SF. The frames have a minimum allowed size as this is dictated by the radio duty cycle rules, however, additional slots can be added and expand the frame size in order to accommodate more transmissions per frame. Apparently, the longer the frame, the sparser the transmission rate, and thus, the data collection time.

As with all synchronised protocols, the nodes need to be periodically synchronised by the gateway according to a global clock. In order to accommodate the nodes' clock drift over time, guard times are added between successive time slots to ensure that adjacent transmissions do not overlap. Assuming the propagation delay negligible, the guard time depends on the crystal clock accuracy and on how often the gateway communicates with the nodes to synchronise their clocks. In TS-LoRa, this is performed using a novel mechanism called "SACK" (Synchronisation and ACKnowledgmemts) which merges sync and (optional) ack data into a single downlink packet. The frame size and the guard time are adjusted automatically according to the number of registered nodes. An example of the frame structure is given in Figure 3a.

Detailed information of the time-slotted operation and the synchronisation can be found in [START_REF] Zorbas | TS-LoRa: Time-slotted LoRaWAN for the Industrial Internet of Things[END_REF] and [START_REF] Zorbas | Design Considerations for Time-Slotted LoRa(WAN)[END_REF].

The schedule

We call schedule a series of frames containing transmissions (slots) from all the nodes in the network. Nodes' transmission(s) are accommodated in one or more slots. TS-LoRa does not perform any scheduling since the nodes are serially placed into slots as soon as they register with the gateway using the minimum (energy-wise) possible SF. In our current problem, we can still follow the same rationale but this is not enough. This strategy could lead to long data collection times since some frames might be overcrowded. For example, if many nodes are placed close to the gateway, all of them would most likely use SF7 resulting to a large number of slots in that specific frame (See Figure 3a). To tackle that issue, scheduling is performed to find a better arrangement of nodes to slots (other than the serial one) so as to minimise the data collection time without violating duty cycle regulations (whenever they are applied).

Assuming that nodes typically have more than one packet to send, transmissions from each particular node have a minimum periodicity limited by the duty cycle regulations as it is already mentioned. The time slots in between this periodicity can, therefore, be used to schedule transmissions from other nodes. In general, if the airtime (i.e., transmission time) for a SF is 𝑇 𝑓 and the duty cycle is 1%, the minimum period of time between two successive transmissions of the same node is 𝑇 𝑓 • 100 and approximately 𝑁 𝑓 = 99𝑇 𝑓 𝑇 𝑓 +2𝜏 transmissions from other nodes with the same SF can be scheduled in the meantime, where 𝜏 is the guard time at the beginning and at the end of a slot. If more nodes need to be assigned, the frame for SF 𝑓 is extended. Moreover, a scheduler follows always a simple rule. A node (or transmission) is allocated to the frame that leads to the earliest completion of the data collection. Figure 3 illustrates such an example of allocation using three nodes with two transmissions each. The optimal solution is to schedule Node C transmissions to a frame with a higher SF since this results in a shorter data collection time (See Figure 3b). If the scheduler allocates each node transmissions to a different frame, this may result to a sub-optimal solution (See Figure 3c). Optimal data collection time Fig. 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.

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 [START_REF] Morné Marais | A Survey on the Viability of Confirmed Traffic in a LoRaWAN[END_REF]), we skip its formulation. The network is composed of a set of 𝑁 nodes. Depending on the distance of a node 𝑖 from the gateway, a set of possible SFs F 𝑖 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 𝑖 has an amount of data to transmit, denoted by 𝑝𝑘𝑡 𝑖 . Each transmission of 𝑖 can be scheduled using a SF 𝑓 (𝑓 ∈ F 𝑖 ) with an associated payload 𝑝𝑎𝑦𝑙𝑜𝑎𝑑 𝑓 . Given 𝑓 and 𝑝𝑎𝑦𝑙𝑜𝑎𝑑 𝑓 , we can calculate the packet transmission time 𝑇 𝑓 [START_REF]LoRa Modem Design Guide[END_REF].

Let 𝐹 = {7, . . . , 12} be the set of available spreading factors. To each SF 𝑓 ∈ 𝐹 , we associate a set T 𝑓 = {𝑡 𝑓 𝑗 , 1 ≤ 𝑗 ≤ Γ} of time slots starting at time 𝑗, where Γ is the global upper limit in number of slots. These slots have duration 𝑇 𝑓 + 2𝜏 for the given node's payload and SF, where 𝜏 corresponds to the guard time.

We associate a set of forbidden slots 𝜒 . 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:

𝑦 𝑖 𝑡 𝑓 𝑗 = 1 if node 𝑖 uses slot 𝑡 𝑓 𝑗 , 0 otherwise
The linear program to optimally schedule bulk data transmissions is defined as follows:

min max 𝑓 ∈𝐹, 𝑡 𝑓 𝑗 ∈T 𝑓 ( 𝑗 + 𝜏 + 𝑇 𝑓 ) 𝑖 𝑦 𝑖 𝑡 𝑓 𝑗 (6)
𝑠𝑢𝑏 𝑗𝑒𝑐𝑡 𝑡𝑜 :

𝑖 ∈𝑁 𝑦 𝑖 𝑡 𝑓 𝑗 ≤ 1, ∀𝑓 ∈ 𝐹, 𝑡 𝑓 𝑗 ∈ T 𝑓 ( 7
)
𝑓 ∈𝐹 \F 𝑖 𝑡 𝑓 𝑗 ∈T 𝑓 𝑦 𝑖 𝑡 𝑓 𝑗 = 0, ∀𝑖 ∈ 𝑁 (8) 𝑓 ∈ F 𝑖 𝑡 𝑓 𝑗 ∈T 𝑓 𝑝𝑎𝑦𝑙𝑜𝑎𝑑 𝑓 𝑦 𝑖 𝑡 𝑓 𝑗 ≥ 𝑝𝑘𝑡 𝑖 , ∀𝑖 ∈ 𝑁 (9)
𝑦 𝑖 𝑡 𝑓 𝑗 + 𝑦 𝑖 𝑡 ′𝑓 ′ 𝑗 ′ ≤ 1, ∀𝑖 ∈ 𝑁 , 𝑓 ∈ F 𝑖 , 𝑡 𝑓 𝑗 ∈ T 𝑓 , 𝑡 ′𝑓 ′ 𝑗 ′ ∈ 𝜒 𝑡 𝑓 𝑗 . ( 10
)
The objective function [START_REF] Bonafini | Exploiting localization systems for LoRaWAN transmission scheduling in industrial applications[END_REF] seeks to minimise the length of the longest frame among all SFs. The end of the frame occurs at time 𝑗 + 𝜏 + 𝑇 𝑓 because the last transmission starts at 𝑗 + 𝜏 and lasts for 𝑇 𝑓 amount of time. To determine which slot is the last one used, we need to multiply 𝑗 + 𝜏 + 𝑇 𝑓 with the sum over all variables 𝑦 𝑖 𝑡 𝑓 𝑗

. Indeed, there can be only one node using a slot, so this sum is either 0 (the slot is not used) or 1 (the slot is used by one node). Thus, the result of max

𝑓 ∈𝐹, 𝑡 𝑓 𝑗 ∈𝑇 𝑓 ( 𝑗 + 𝜏 + 𝑇 𝑓 ) 𝑖 𝑦 𝑖 𝑡 𝑓 𝑗
gives the time ( 𝑗 + 𝜏 + 𝑇 𝑓 ) of the longest frame. To get a linear equation removing the maximum function, we add the following set of constraints:

( 𝑗 + 𝜏 + 𝑇 𝑓 ) 𝑖 𝑦 𝑖 𝑡 𝑓 𝑗 ≤ 𝜁 , ∀𝑓 ∈ 𝐹, 𝑡 𝑓 𝑗 ∈ T 𝑓 , (11)
where 𝜁 is a continuous variable whose purpose is to keep track of the maximum frame length, which is what we want to minimise in our problem.

Summarising, constraint [START_REF] Bor | Do LoRa Low-Power Wide-Area Networks Scale?[END_REF] verifies that at most one node can use a slot. Constraint (8) forbids a node to use non-permitted SFs. Constraint [START_REF] Ebi | Synchronous LoRa Mesh Network to Monitor Processes in Underground Infrastructure[END_REF] ensures that all nodes get to send their total amount of data. Finally, constraint [START_REF] Gao | A Multichannel Low-Power Wide-Area Network With High-Accuracy Synchronization Ability for Machine Vibration Monitoring[END_REF] verifies the duty cycle restrictions using sets 𝜒 𝑡 𝑓 𝑗 defined above. This last constraint can be eliminated in the case of LoRa operating in the 2.4GHz ISM band where no radio duty cycle restrictions exist [START_REF] Polak | Performance analysis of LoRa in the 2.4 GHz ISM band: coexistence issues with Wi-Fi[END_REF].

The hardness of the model stems from the fact that a very large range of slots for all 6 SFs (or 8 for 2.4GHz LoRa) is evaluated for each possible transmission. This results in a very long sequence of possible iterations. The problem can be alleviated by setting a maximum frame length Γ per SF which is translated to a maximum number of slots to be evaluated. However, we need to define how this value is chosen. For example, allowing too many slots in each frame increases dramatically the number of binary variables of our model (recall that there is a single 𝑦 variable per node and per slot). On the contrary, if we do not reserve enough slots for each SF, especially for SF7 which is the most utilised spreading factor, the linear program can still find a solution with the given slots. In this case, the schedule will be optimal only for the given settings but not globally optimal. Since most of the transmissions are accommodated in the SF7 frame, the value of Γ is selected through a trial and error method so that the frame of SF7 is large enough to find the optimal schedule.

Nevertheless, the linear program still requires to test a high number of variables per transmission, upper-bounded by 𝑁 Γ|𝐹 |, which may limit the practicality of the computational solution to low node numbers only. For deployments with many nodes, time-efficient heuristics such as Light and Global can be used [START_REF] Zorbas | Offline Scheduling Algorithms for Time-Slotted LoRa-based Bulk Data Transmission[END_REF]. The two heuristics differ in the way they handle transmissions and how they divide the schedule into frames. The first algorithm, called Light, schedules only the first transmission for each node and repeats that in subsequent frames. The second approach, called Global, computes the schedule for all transmissions and, as a consequence, produces a sequence of frames that may differ to each other. As a result, Global can compute more efficient schedules than Light in terms of data collection time, however, this comes at the expense of a higher computation cost, a larger schedule size, and a higher implementation complexity.

EVALUATION & DISCUSSION OF THE RESULTS

In this section, simulation and experiments are conducted to evaluate the performance of the optimization model as well as practical issues regarding time-slotted communications in LoRa networks. Due to the high complexity of the model, the LP solver was not able to solve solutions with more than 50 nodes. As a consequence, we divided the simulation results in two sections. Section 6.2 is dedicated to the comparison with the optimal with 10-50 nodes, and Section 6.3 is dedicated to scenarios with a higher number of nodes (100-1000).

Simulation Setup

We consider a square deployment area with a side of 1000 meters length and a variable number of nodes that are randomly and uniformly scattered. We also consider a path-loss model that corresponds to a smart city scenario where the signal attenuates fast [START_REF] Bor | Do LoRa Low-Power Wide-Area Networks Scale?[END_REF]. We compare the performance of the time-slotted scheduling heuristics, Light and Global [START_REF] Zorbas | Offline Scheduling Algorithms for Time-Slotted LoRa-based Bulk Data Transmission[END_REF], with a Pure Aloha-based approach (denotes the standard LoRaWAN), with a Slotted-Aloha one, as well as with the optimal scheduling solution of Section 5 (for 10 to 50 nodes). For fair comparison (in the case of confirmed transmissions the Aloha approach presents a very high number of collisions), the uplink transmissions are unconfirmed, so no re-transmissions occur (however some experiments with confirmed transmissions are shown in Section 7). In the Aloha-based approaches, the nodes use the minimum reliable SF that allows them to reach the gateway, which actually demonstrates the standard Adaptive Data Rate (ADR) mechanism of LoRaWAN. We allow the nodes to periodically send data with the optimal rate 𝜃 𝑚𝑎𝑥 as derived by solving the optimisation problem in Eq. (2-5) for both Pure and Slotted-Aloha cases. This optimization problem is solved using exhausting search as with [START_REF] Zorbas | Fast and Reliable LoRa-based Data Transmissions[END_REF]. In this way, we guarantee a packet delivery ratio of at least 90% for all nodes in the network. In Pure Aloha, each node transmits at a constant rate which may vary for a few seconds from transmission to transmission in order to avoid repeated collisions. In Slotted-Aloha, each node chooses randomly a slot to transmit; this slots changes at every transmission also to avoid repeated collisions. In collision-free approaches (i.e., scheduled ones), the maximum allowed data rate as this is dictated by the duty cycle rules and the scheduler is followed.

All scheduling algorithms are implemented in the Perl programming language1 , taking into account the path-loss and fading of the signal and the capture effect at the gateway. The Aloha-based approaches are implemented on a LoRaWAN simulator2 whose effectiveness and correctness have been verified by experiments [START_REF] Zorbas | Fast and Reliable LoRa-based Data Transmissions[END_REF]. The simulator has been adapted to the needs of the bulk data collection and inherits the following capabilities and features from the initial simulator:

• Multiple half-duplex gateways

• 1% radio duty cycle for uplink transmissions

• 1 or 10% radio duty cycle for downlink transmissions

• Two receive windows (RX1, RX2) for ACKs and commands

• Non-orthogonal SF transmissions

• Capture effect

• Path-loss signal attenuation model

• Multiple channels (however a single channel was used in this paper)

• Collision handling for both uplink+downlink transmissions

• Node energy consumption calculation (uplink+downlink)

Table 2 shows the values used for the simulation parameters.

The linear program was implemented in the Java programming language and solved using the IBM CPLEX solver 12.8 on an Intel Core i7-5500U CPU, 2.40 GHz, 32 Gb RAM computer running the Linux Fedora operating system. The sensitivity of the solver's optimality gap has been set to 1𝑒 -7 to have enough precision to detect the optimal schedule length. Due to the complexity of the model, we have computed the optimal schedule only for network sizes between 10 to 50 nodes for fixed and variable node buffered data sizes. For the rest of the simulations, we vary the number of nodes from 100 to 1000 and we measure the data collection time, the packet delivery ratio (PDR), and the energy consumption of the nodes. We generate 50 instances per simulation run and the average results are presented along with the 95% confidence intervals.

The evaluation was conducted considering fixed as well as variable buffered data sizes. In the first use case, all nodes have the same amount of data to transmit (∼10KB), which represents the buffered data per certain period of time from a periodic data generation application. This use case is a typical scenario in precision agriculture or environmental monitoring applications where the nodes periodically wake up, take a measurement, and then return to sleep mode. In the second use case, the nodes have a different amount of data to deliver whose size varies between 200 and 18K bytes (i.e., 2 to 180 transmissions). This use case represents data generation that is triggered by an event whose detection wakes up nodes to capture the event.

We would also like to stress that for the sake of simplicity as well as of energy efficiency all the packet sizes of all SFs are fixed and large enough. As it has been shown [START_REF] Abdelfadeel | 𝐹 𝑅𝐸𝐸-Fine-Grained Scheduling for Reliable and Energy-Efficient Data Collection in LoRaWAN[END_REF], it is more energy efficient to use large packet sizes for all SFs to perform the data collection. This is due to the increased overhead that small packet sizes cause at the MAC layer, thus, delaying the data collection process and increasing energy consumption. On the other hand, in a network with high error rate, very large packet size would cause a high loss of data or high energy cost in case of re-transmissions.

Hence, in this work a packet size in the midpoint between the lowest (8B) and the highest (255B) packet size is chosen.

Scheduling Comparison with the Optimal

In this subsection, we compare the pure algorithmic performance of the scheduling approaches, without considering network requirements such as sync packets. We compare the performance between two heuristics, Light and Global, and the optimum solution as it is computed by solving the optimisation problem defined in Section 5. As we can observe from Figure 4a, both heuristics achieve identical performance to the optimum in terms of data collection time for all node populations. Moreover, this performance is achieved with a very small computation time which does not exceed 1.7ms for Light and 9.9ms for Global (see Figure 4b). On the contrary, due to the increased range of binary values of some parameters, such as the number of slots, the solver may require multiple hours to find the optimal solution.

We repeat the comparison using variable data sizes randomly assigned to the nodes in the range [200-18K] Bytes.

This performance evaluation is depicted in Figure 4c,d. The results reveal that for the tested scenarios the two heuristics perform only up to 3% worse compared to the optimal solution. As it was expected Global achieves a slightly better transmissions to different -and eventually more efficient -frames, since it schedules only the first transmission. Finally, similarly to the fixed data size scenario, the transmission schedules are calculated in a very short time.

Comparison with Other Approaches

6.3.1 Fixed Data Sizes. Simulation results with node numbers from 100 to 1000 are presented in Figure 5. The results do not include the schedule transmission overhead, however, this is almost negligible compared to the total values. The overhead varies from 3 to 7% (worst case) of the total data collection time and energy consumption. As we can observe, the impact of the collision-free transmissions in the data collection time is obvious. The performance in terms of data collection time is at least 10 times higher using an Aloha MAC approach such as LoRaWAN. Slotted-Aloha performs better, however, still far from the collision-free method.

In our simulations, all the approaches achieved a packet delivery ratio over 90% while the collision-free ones exceeded 95%. The Aloha approaches achieved those PDR values only at the expense of much longer data collection times. This

shows the superiority of collision-free time-slotted communications as the number of nodes increases. Moreover, the scheduling of transmissions over different slots and SFs leads to much lower data collection time compared to TS-LoRa (non-scheduling approach). The improvement seems to be higher when the number of nodes increases. However, in terms of energy consumption, this action causes an increased trend in energy cost. This happens due to two reasons.

Firstly, as the number of nodes increases, more and more nodes are switched to higher SFs. Higher SFs cause longer transmission times and, thus, higher energy consumption. Secondly, the nodes periodically turn on their radio to receive the sync packet from the gateway, increasing the average consumption during a round. Comparing TS-LoRa with the Pure Aloha MAC performance, we can see that the synchronisation overhead causes about 15% higher energy consumption (see Figure 5b). However, as we showed in one of our recent studies [START_REF] Zorbas | TS-LoRa: Time-slotted LoRaWAN for the Industrial Internet of Things[END_REF], the synchronisation cost is much lower than that caused by re-transmissions in an Aloha-based protocol.

Variable Data Sizes.

In the last set of simulations (see Figure 6), we focus on the comparison between the synchronous approaches in a variable data size scenario. In this scenario, 500 nodes are used where the data size of each node is randomly allocated from [10000 -𝑋, 10000 + 𝑋 ] bytes, where 𝑋 = [1000..8000]. The Aloha approaches are not included in this study for presentation purposes due their very high data collection times. Global's advantage is obvious due to its capability to fill the empty slots left by nodes that finish transmissions earlier than nodes with more transmissions. Light schedules nodes' activities based on the first transmission without considering the amount of data per node. As a consequence, nodes that complete sooner leave empty and never again used slots. TS-LoRa provides no SF re-assignment resulting in very high frame sizes. The performance gap increases with higher data variance since

Global finds more options to fill empty slots. We can see that Global's performance is almost independent of the data variance, while Light's and TS-LoRa's ones present an increasing trend. In terms of energy consumption, the difference between TS-LoRa and the scheduling approaches is about 45%. All the approaches have the same synchronisation cost per frame but the scheduling approaches spend more energy due to the higher average SF.

PROOF OF CONCEPT & EXPERIMENTAL RESULTS

System setup & procedure

In order to verify our approach also in experiments with real node deployments, we created a proof-of-concept implementation consisting of 10 nodes located across two adjacent, multi-floor buildings. Independent, co-located LoRaWAN networks also existed in the area. The top view with indicative node positions is illustrated in Figure 7. The gateway is located at the first floor on the edge of the upper-hand building. The maximum (reliable) indoor range that was achieved with SF7 was approximately 60m using typical 2dBi antennas for both the nodes and the gateway. This low range is justified by the presence of multiple concrete and stone walls which cause a very strong signal attenuation.

The purpose of the experiments is not to show the superiority of the scheduling approaches over the rest of the methods since this would require a network of at least 100 nodes along with very high financial and time resources. Thus, we limit the purpose of the experiments to assess the following practical issues:

(1) to assess the feasibility of using time-slotted scheduling algorithms under real conditions,

(2) to assess the downlink transmission time of the schedule,

(3) to assess the feasibility of computing the schedule on the nodes instead of computing it centrally on the gateway and then disseminating it to the nodes, and

(4) to assess confirmed transmissions.

LoRa-enabled devices from Pycom where used for the purpose of the experiments. For experimental efficiency, an amount of data was already generated and loaded onto the nodes' storage module. Each node position was initially evaluated for its connectivity requirements in terms of transmit power and SF. We did this test manually, however

LoRaWAN's ADR mechanism can be used to automatically calculate and adjust the SF according to the latest conditions 3 .

Table 3 summarises the experimental parameters and their corresponding values.

The entire process of computing the schedule, communicating it to the nodes, and receiving the data is illustrated in Figure 8. Moreover, an overview of the network architecture is presented in Figure 9. We used a Raspberry Pi (here representing the network server) to compute the schedule. The Raspberry Pi can also optionally send additional information related to the experimental process, such as the guard time, the synchronisation rate, and the channel bandwidth. A gateway is responsible for registering nodes to the network, while another gateway is used for data collection. A third gateway can optionally be used for statistic collection in case of confirmed transmissions (i.e., the nodes can send out data about the ack rate). All the gateways communicate with the Raspberry Pi via secure WiFi links.

The data gateway receives the schedule and forwards it to the nodes. To do so, the nodes must have their radio on and listen to a specific channel, BW, and SF. These settings are and do not change throughout the process, thus, they can be flashed into the nodes during their setup by a system administrator. In the experiments, we used the highest SF in the network so that all nodes regardless of their SF can receive the schedule. An alternative approach would be to send the schedule multiple times based on the available SFs in the network. However, this would require additional setup time and probably to a waste of energy for the nodes, unless multiple LoRa gateways were used (one gateway for each available SF). We run each experiment 10 times and the average results are presented along with the minimum and the maximum values. We measure the schedule transmission time, the data collection time, the active radio time, and the packet delivery ratio for the 10-node testbed.

Data transmissions are performed in the allocated time slots using the assigned SFs as computed by the scheduler.

The nodes have their radio off during the rest of the period, however, they periodically need to turn on their radio to receive synchronisation packets from the gateway. The synchronisation is achieved using an additional slot at the end of a frame as it was presented in Section 4.1. The reader can find more information about this mechanism in [START_REF] Zorbas | TS-LoRa: Time-slotted LoRaWAN for the Industrial Internet of Things[END_REF].

Transmission of the schedule

Here, we present experimental results related to the transmission of the schedule. This includes an evaluation of the capability of the gateway to efficiently compute and encode the schedule. No physical presence of the nodes themselves is required. As a consequence, we can experiment with more than 10 nodes.

In Light, the schedule consists of a set of tuples indicating the node id, the SF, and the slot number (i.e., [id, sf, slot]). For example, in our 10-node deployment this results in a 70-Byte schedule. Some extra bytes are added to indicate the gateway id, the guard time, and the sync packet rate. 78 Bytes are sent in total. In terms of transmission time this translates to 35ms with SF7 or 698ms with SF12.

Global uses a more sophisticated data encoding to represent the repetition of the frames in the schedule. Recall that in Global all the packets are scheduled, thus, a collection of frames is generated. A straightforward solution would be to include the node ids, their SFs, and their slots for all the computed frames in the schedule. However, this solution does not scale because the number of bytes increases linearly with the number of transmissions. On the contrary, since a big range of successive transmissions is scheduled on the same SF and slot, one way to reduce the total number of bytes is to use a run-length encoding data compression algorithm. For example, in our testbed, only the last transmission of one node is relocated to SF8. Thus, all the previous transmissions can be indicated using a single tuple. The general encoding pattern of a node's transmissions is the following: [id first_frame_sf last_frame_sf sf slot, start_frame_sf' end_frame_sf' sf' slot', ...]. In our experiments, the total schedule length with Global is 154 Bytes. In terms of transmission time this translates to 6.3ms and 1.23s with SF7 and SF12, respectively. Every node that receives the schedule, decodes the data and calculates the frame length for its assigned SF. In Global, this must be done for all the assigned SFs which incurs additional coding effort. The schedule transmission is followed by a very short init packet which actually initiates the data collection process. In the Aloha-based approach, the schedule transmission is omitted, thus, only the init packet is used. Table 4 illustrates the total theoretical schedule transmission time for different node populations using SF7. We examine the scenario where the schedule is sent based on an ideal setup where no duty cycle restrictions are imposed as well as when the duty cycle rules are followed. We should note that the first case occurs when transmissions are sent in non-restricted bands (e.g., 2.4GHz LoRa). We can observe that, in the first case, the transmission of the schedule is quite fast for up to 100 nodes. Light scales very well with less than 4 seconds transmission time for 1000 nodes. On the contrary, as the number of nodes increases, Global's schedule becomes very long and, thus, difficult to be transmitted in a reasonable period of time, especially when the duty cycle rules have to be followed. This is because each node's transmissions may jump from one SF to another causing many non-periodic slot allocations in successive frames.

Letting the nodes know these SF jumps, requires extra bytes and, thus, more time.

To overcome the scalability issue of Global, we follow an alternative approach [START_REF] Zorbas | Offline Scheduling Algorithms for Time-Slotted LoRa-based Bulk Data Transmission[END_REF]. We disengage the computation of the schedule from the gateway (network server) and we move this process to the nodes. In this way, we transmit only the list of nodes and their minimum SFs, and we let the nodes compute the schedule. Since this list is usually multiple times shorter in size than the schedule, it can be transmitted in a shorter amount of time. It should be noted that this action leads to a trade-off between processing and communication time. In order to evaluate this trade-off, we implement Global on our testbed devices. Due to the limited memory resources (only 4MB), the nodes compute the entire schedule but they generate a list of transmissions (i.e. slots and SFs) only for their own id. The input transmission time, as well as the schedule computation time, are displayed in Table 5. The results show an up to 78% improvement in total transmission time in the case without duty cycle restrictions and an over 800% improvement when the duty cycle rules are followed. We also need to stress here that the energy consumption in processing mode is comparable to the receiving cost (i.e., ∼50mA), so the nodes do not spend more energy compared to when the schedule was transmitted by the gateway.

Confirmed vs Non-confirmed traffic

Finally, in the last experiment, we assess the behaviour of the approaches when re-transmissions can occur. For the needs of these experiments, we also developed approaches that allow re-transmissions of packets in order to capture the effect of acknowledgments in the data collection time and in other measurements. All the nodes transmit 100 unique packets, while maximum 3 retransmissions per packet are allowed before the packet gets dropped. For the time-slotted approaches (i.e., Slotted-Aloha, Light, Global, and TS-LoRa) the acknowledgments are sent in groups during the SACK packet. The periodicity of the SACK packet is communicated to the nodes at the beginning of the process. In the Pure Aloha approach, acknowledgements are sent similarly to LoRaWAN, using two receive windows. nodes, all collision-free approaches presented identical results. Thus, the label "CF" refers to all these approaches, while the label "CF-ACK" refers to their confirmed version. Moreover, we must mention that the two heuristic scheduling approaches were able to generate optimal schedules. The results reveal that in terms of data collection time, there is a 10% overhead due to synchronisation compared to the optimal solution. This overhead is apparently higher in case of re-transmissions. The two Aloha approaches present the highest overhead due to higher number of collisions and, thus, more time is required because of the re-transmissions. As it was expected, the PDR is very high for the collision-free approaches and ranges from 98 to 99.8%. Because no intra-network collisions occur, some packets were lost due to the path-loss effects and the presence of external interference. Slotted-Aloha performs close enough in confirmed traffic. This is because in our implementation acknowledgements are sent straight away after the reception of packet (unlike LoRaWAN where 1 or 2 seconds delay is imposed). Finally, as it was expected, the slotted approaches exhibit a higher energy cost compared to Pure Aloha without acknowledgements but they present a better performance than Aloha in the case of confirmed transmissions. The reason that this occurs is that in the frame structure of TS-LoRa (which is also followed by Light and Global), the acknowledgements are sent in groups at the end of the slot. This minimizes the number of bytes received by the nodes and, thus, their energy consumption.

CONCLUSIONS & FUTURE DIRECTIONS

In this work, we studied the problem of bulk data collections in LoRa-based networks for situations where a gateway is not available to receive data at all times due to the lack of a permanent power source or the lack of coverage (e.g., in satellite IoT systems). We showed that traditional Aloha-based networks suffer from very long data collection times in order to achieve a satisfactory data delivery ratio. Here, we explored the possibility of using collision-free time-slotted LoRa communications together with SF and slot scheduling to accelerate the data collection. We mathematically formulated and solved the corresponding scheduling problem of finding the best SF and slot allocations that optimise the data collection time. The comparison with heuristics for small data sets showed only a slight performance gap in data collection time compared to the optimum approach. We implemented our methods using real deployments and we examined critical components of the bulk data collection such as the transmission of the schedule. Despite the duty cycle and power limitations, the results demonstrated the significant advantage of using the proposed synchronous approaches to achieve fast data collection especially with hundreds of nodes.

For future work, we intend to investigate the possibility of using medium sensing techniques for data offloading in dense node situations and see their effect on the data collection time. More specifically, we intend to assess the use of the Channel Activity Detection (CAD) mechanism of LoRa transceivers in scenarios where a high packet rate is required, and also develop a feedback and re-transmission mechanism for those scenarios. Another interesting problem to explore is the transmission of the schedule using multiple gateways. We are planning to design an approach to divide the schedule in multiple pieces and transmit it to the nodes over different channels and SFs in order to accelerate the process and increase the levels of scalability -but also of energy efficiency -in large-scale networks. Finally, an open problem remains the development of a payload-agnostic time-slotted algorithm for data collection purposes.

Fig. 2 .

 2 Fig. 2. Theoretical average data collection time (𝑝𝑘𝑡 /𝜃 ) of an Aloha and Slotted-Aloha LoRa MAC for different node populations, 𝑝𝑘𝑡 =100, and 100 Bytes packet size. At least 90% packet success rate of all the nodes is guaranteed.

  no schedulining (b) optimal scheduling (c) sub-optimal scheduling

  𝑡 𝑓 𝑗 to each slot 𝑡 𝑓 𝑗 . This set contains all the slots 𝑡 ′𝑓 ′ 𝑗 ′ of the same SF (i.e. 𝑓 ′ = 𝑓 ), and of other SFs (i.e. 𝑓 ′ ≠ 𝑓 ) such that 𝑗 ≤ 𝑗 ′ ≤ 𝑗 + 100𝑇 𝑓 , for 1% duty cycle. If a node uses 𝑡 𝑓 𝑗 to transmit data, then the duty cycle restriction forbids the node to use any slot in 𝜒 𝑡 𝑓 𝑗

Fig. 4 .

 4 Fig.[START_REF] Aslan | A framework for use of wireless sensor networks in forest fire detection and monitoring[END_REF]. Comparison with the optimal for a scenario with fixed data size (upper) and variable data size (lower).

Fig. 5 .

 5 Fig. 5. Data collection time and energy consumption for a scenario with fixed data size.

Fig. 6 .

 6 Fig. 6. Data collection time and energy consumption for variable data sizes.

Fig. 7 .

 7 Fig. 7. Positions of the nodes and the gateway in the 4-floor building.

Fig. 9 .

 9 Fig. 9. Network architecture of the experiments.

Fig. 10 .

 10 Fig.10. Experiment with 10 nodes: Data collection time, Packet Delivery Ratio, and active radio time with and without retransmissions (CF: Collision-Free approaches, S-Aloha: Slotted-Aloha, -ACK: the corresponding approach with retransmissions).

Table 1 .

 1 Notations and their meaning

	Notations	Meaning
	𝑓	Spreading Factor (SF) value
	𝑁 𝑓	Number of nodes with SF 𝑓
	𝑇 𝑓	Transmission time with SF 𝑓
	𝑝𝑎𝑦𝑙𝑜𝑎𝑑 𝑓	Payload size per SF 𝑓
	𝜃	Packet data rate
	𝐿 𝑝𝑙 (), 𝑑 0 , 𝛾 , 𝜎 Path-loss model parameters
	𝑃 𝑚𝑖𝑛 𝑓	Minimum success probability for SF 𝑓
	𝑃 𝑔𝑖𝑣𝑒𝑛	Minimum required success probability
	𝐶	Radio duty cycle constraint (0-1)
	𝐹	Set of available SFs
	F 𝑖	Set of possible SFs per node 𝑖
	𝑝𝑘𝑡 𝑖	Number of transmit packets per node 𝑖
	𝜏	Guard time length
	Γ	Upper limit in number of slots in a frame
	T 𝑓	Number of slots in frame for SF 𝑓
		x	xR d
	Fig. 1. Interfering zone (dark colour) of a node located at distance 𝑥 from the gateway placed at the center of the disk (intra-SF
	interference).

Table 2 .

 2 Simulation Parameters

	Parameter	Value
	Nodes	100 -1000
	(comparison with the model)	10 -50
	Terrain side	1000 m
	Gateway coordinates	[500, 500] m
	Channel bandwidth (BW)	500 KHz
	Preamble Symbols	8
	Coding Rate	4/5
	Payload size	100 Bytes
	Buffered Data per node	10000 Bytes (unless specified)
	(comparison with the model)	1000 Bytes or 500 -1500
	Path Loss model (see [7])	𝐿 𝑝𝑙 (𝑑 0 ) = 95dB (experimental)
		𝑑 0 = 40m, 𝛾 = 2.08, 𝜎 = 3.57
	Guard time (𝜏)	10ms for up to 50 nodes,
		40 ms otherwise
	Receiver Sensitivities	[-116, -119, -122, -125,
	(per SF for BW500)	-128, -129] dBm
	Tx power & consumption	14 dBm, 75 mA [32]
	Rx consumption	45 mA [32]
	Aloha transmission rate (𝜃 𝑚𝑎𝑥 ) derived from Eq.(2-5)
	Radio duty cycle (𝐶)	≤1%

Table 3 .

 3 Experimental parameters

	Parameter		Value
	Nodes		10
	Channel bandwidth		500 KHz
	Preamble Symbols		8
	Coding Rate		4/5
	Schedule size		78 Bytes (Light)
			156 Bytes (Global)
	Packet size		100 Bytes (98 Bytes for data+
			2 Bytes overhead)
	Sync packet size		8 Bytes
	Data per node		9800 Bytes
	Guard time		15 ms
	Tx power (nodes)		14 dBm
	Pure+Slotted Aloha packet rate ∼13.5pkt/min with SF7
			(duty cycle bounded)
	Max retransmissions		up to 3
	Radio duty cycle (nodes)		≤1%
	Radio duty cycle (gateway)	≤10%
	Wait for user-initiated start command		aggregate data and forward it to the base
			yes
	Compute the schedule	Has the expected data collection time reached?	receive data from the nodes
			no
	send the		forward the	send the
	schedule to		schedule to	synchronisation
	the gateway		the nodes	packet
	Fig. 8. Experimental procedure of Base/Gateway.

Table 4 .

 4 Schedule transmission times following or not following the duty cycle rules (seconds).

	Nodes	No Duty Cycle Light Global Light Duty Cycle Global
	10	0.035 0.063	0.035	0.063
	100	0.389 1.362	29.3	126.64
	500	1.85	223.31 175.32 >1000
	1000	3.796 490.03 370.01 >1000

Table 5 .

 5 Schedule computation time by the nodes and transmission time of the input using Global (seconds).

	Nodes	Input (No Duty Cycle) (Duty Cycle) Input	Processing
	10	0.027	0.027	0.77
	100	0.29	19.56	8.49
	500	1.17	107.1	47.36
	1000	2.34	223.98	108.03

The code is available at https://github.com/deltazita/offline-lora

LoRaWAN simulator https://github.com/deltazita/LoRaWAN-SIM

The embedded code of the gateway and the nodes is available at https://github.com/deltazita/offline-lora and at https://github.com/deltazita/ts-lora

ACKNOWLEDGMENTS

This publication has emanated from research conducted with the financial support of Science Foundation Ireland (SFI) and is co-funded under the European Regional Development Fund under Grant Number 13/RC/2077, the CONFIRM fund under Grant Number 16/RC/3918, and the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 713567.


Olivier Aumage

Paul Carpenter

Siegfried Benkner

Processing in Memory: the Tipping Point 1 Task-Based Performance Portability in HPC Maximising long-term investments in a fast evolving, complex and heterogeneous HPC landscape White Paper

Key insights

• Porting applications is difficult and must be successful in a short time. HPC hardware evolves quickly and supercomputers have a fast turnover. On the other hand, HPC applications have a long lifetime. Usage practices are themselves evolving towards more complex and dynamic scenarios, involving simulation, code coupling, (in-situ) analysis and visualisation, interactive computing, urgent computing, and malleability.

• Applications should therefore be expressed in a way that facilitates performance portability, as agnostic as possible (and no more) of the architectural particularities. The advantages are more rapid porting to new platforms and the flexibility to adapt to new application scenarios. One of the hardest aspects to address is the need to build trust among developers that the underlying software layers can extract full performance from a performance-portable codebase rather than relying on hand optimisation.

• Task-based programming models allow HPC programmers to express applications and workflows in such a performance portable way. As global optimisation and coordination is needed across all levels of the software stack, task-based models identify pieces of work to be done, thereby providing a clean abstraction for the programmer to reason about the program. The runtime layer should handle parallel scheduling, overlapping of computation and communication, data placement and transfers, resiliency, load balancing and dynamic resource sharing among applications.

Introduction

As HPC hardware continues to evolve and diversify and workloads become more dynamic and complex, applications need to be expressed in a way that facilitates high performance across a range of hardware and situations. The main application code should be platform-independent, malleable and asynchronous with an open, clean, stable and dependable interface between the higher levels of the application, library or programming model and the kernels and software layers tuned for the machine. The platform-independent part should avoid direct references to specific resources and their availability, and instead provide the information needed to optimise behaviour. This paper summarises how task abstraction, which first appeared in the 1990s and is already mainstream in HPC, should be the basis for a composable and dynamic performance-portable interface. It outlines the innovations that are required in the programming model and runtime layers, and highlights the need for a greater degree of trust among application developers in the ability of the underlying software layers to extract full performance. These steps will help realise the vision for performance portability across current and future architectures and problems.

• Open standardisation is one of the best ways to drive adoption. HPC application developers require a commitment to long-term maintenance, support and high performance across platforms. There is a vibrant ecosystem of programming model research in Europe adopting various approaches, the most successful of which should be standardised.

Key recommendations

• The community should promote best practices in application porting:

-Promote greater trust in the ability of lower-level software layers to extract full performance, rather than displaying "impressive" optimisation tricks. -Confine adaptation efforts to short kernels, while preserving the global application structure, favouring composability. -Separate the concerns of experts in distinct fields to let them jointly contribute to the optimisation effort in a coordinated, interference-free manner, from application domain, to algorithm, to programming model, to runtime, to platform.

• Research in task-based programming models and runtimes should:

-Improve efficiency and extend scope of runtime resource management decisions. -Support new platforms/hardware, e.g. FPGAs, PIM, and usage models, e.g. malleability.

-Enable cooperation of task-based models with existing HPC components, such as compilers, job schedulers, application deployment managers, MPI, etc. -Develop a portfolio of tools around task-based models, such as performance analysis, verification and debugging frameworks.

• Europe should make the most of its vibrant ecosystem of programming model research:

-Continue to foster various approaches motivated by and evaluated using large-scale applications.

Shortening application deployment and optimisation efforts on complex, heterogeneous, high turnover HPC supercomputers

Supercomputer platforms, such as those in PRACE Tier-0, are at the current state of the art in computer hardware technology, and as such, have short production lifetimes, at most 5 to 10 years. New machines must therefore deliver scientific and industrial results right upon entering production. At the same time, the technology race is leading to increasingly complex, heterogeneous, diverse computing hardware as vendors devise new solutions to deliver ever higher performance, making the software adaptation effort challenging. This evolution can be seen in the diversity of technical solutions, with and without accelerators, of various kinds, and with diverse and heterogeneous memory systems, in the most powerful systems at the Top500 and Green500 rankings. For instance, Top500 #1 Fugaku uses Fujitsu's ARM derived A64FX processors, #2 Summit and #3 Sierra systems combine IBM's Power9 processors with NVidia Volta GV100 GPUs, #4 TaihuLight is built on Sunway SW26010 many-core processors, etc.

Application development is usually expensive and time consuming, and this is especially true in HPC, where applications tend to have long lifetimes to capitalise on developer investment and embody domain expertise that has grown over time. It is essential that the application's architecture is stable and that all its prerequisites have long-term availability, maintenance and high performance across current and future target platforms. Applications are also becoming more diverse and complex as new users and science fields come to HPC. For example, scientific simulations now often need to be tightly coupled with AI-based data analytics in an efficient way.

Task-based runtime systems perfectly cope with such evolving hardware and software. Since there is little time for software developers to port and tune applications specifically for new platforms, applications need to be expressed in a way that facilitates high performance across a range of hardware and situations. As much as possible, the majority of the application code should not be dependent on specific resources or their availability, so that, in a simple example, instead of dividing up the work by the number of cores and/or devices the application should use an abstraction like a task-loop or parallel for. Resilience, load balancing and data placement should also be handled at lower software layers. This requires a greater degree of trust in the ability of the underlying software layers to extract high performance, and a larger focus on long-term maintainability, portability and performance rather than (impressive) short-term performance tricks.

Task-based programming models allow developers to write applications in a way that preserves such stability by confining the adaptation effort mostly on select kernel routines that can be encapsulated into tasks with known inputs and outputs.

The same task abstraction can be used to build libraries and domain-specific languages that can in turn be used by the application. Once standardised, the application developers can rely on wide support.

Tasks as an abstraction for programming first appeared in 1995 [START_REF] Blumofe | Cilk: an efficient multithreaded runtime system[END_REF], and became mainstream in HPC programming with the publication of OpenMP 3.0 in 2008 [OpenMP3]. Since then, OpenMP's support for tasks has been incrementally refined, to support dependencies, task-loops and reductions, amongst other things, with European research in programming models at the forefront of this innovation.

As task-based programming models are reaching maturity, research effort should now focus on (a) improving and extending the scope of delegated management decisions, (b) developing an interoperable portfolio of tools around taskbased models, (c) extending the cooperation and composability of task-based models with existing components and programming models, and (d) supporting new platforms and architectures, such as FPGAs and Processing in Memory (PIM).

Usual HPC application design practices

HPC applications are most commonly built around variants of the Bulk-Synchronous Parallelism (BSP) model, alternating phases of intra-node computations with phases of inter-node exchanges, separated by synchronisation operations, either using explicit message passing communications with MPI or abstracted through Partitioned Global Address Space (PGAS) approaches. The same BSP pattern is also commonly used at the node level to exploit multiprocessors and cores, either through MPI again, using multiple processes per node, or through OpenMP, using multiple threads in a fork/join manner.

In the same way, synchronous kernel offloads to accelerators or GPUs using NVIDIA CUDA, OpenCL, or through OpenMP/OpenACC constructs, can also be seen as declinations of BSP.

Fig. 1: Illustration of a heterogeneous computing node equipped with a multicore CPU, a GPU-based accelerator board equipped with its own embedded memory and reconfigurable FPGA device.

However, the prominent issue with this BSP approach is the difficulty in ensuring a proper load balancing and coordination across these multiple levels, and the resulting amount of processing unit cycles wasted in synchronisation operations. Using non-blocking programming techniques may help to reduce the amount of wasted cycles. Yet, this makes the burden even higher for the application programmer, for instance to decide which pairs of operations can safely be overlapped, or to determine which amount of CPU computation balances some GPU kernel offload. Factoring in additional sources of complexity and imbalances, such as instruction set variants, cache hierarchies, non-uniform memory access (NUMA) architectures, specialised memory areas with distinct performance patterns (HBM/MCDRAM, NVM), or reconfigurable FPGA computing devices (see Fig. 1), for instance, the effort required for hand-tuning an application on a given architecture becomes largely impractical by itself, and much of the investment becomes irrelevant or counterproductive on a different architecture. Moreover, the performance variability across multiple runs due to the interplay of multiple factors such as frequency scaling, thermal throttling, and general system noise defeats the most careful static execution planning.

Moreover, the entanglement of the application algorithms with unrelated synchronisation, load balancing and more generally with parallelism management operations makes the resulting code difficult to read, to maintain and to evolve. Single-source programming models such as SYCL or Intel's DPC++, and to some extent OpenACC and OpenMP, attempt to address these issues by providing HPC programmers with a means to potentially target diverse hardware computing resources from a unique source code. In the short term, this may indeed be convenient. However, those programmers then become dependent on the availability of the right compiler to target a given combination of CPUs, accelerators, and other kinds of computing devices. Their immediate burden is lightened, but their control is reduced in the process. In addition, this hinders the ability to combine multiple programming models within the same application. A change of approach is needed, which goes beyond simply expressing bulk parallelism in the form of tasks, such as, for example, by converting "parallel for" loops into task-loops. It is necessary to exploit nested tasks, with the possibility of expressing offloading at multiple levels if needed.

Programming for performance portability

Performance portability designates a property of applicative codes to maximise efficiency across a broad range of hardware platforms, while minimising the specific adaptation effort required on each platform. Programming for performance portability requires a software design approach that isolates core application algorithms, i.e. long-term pieces of code persistent across platforms, from kernels, i.e. short-term code tuned for specific hardware. Moreover, machine-dependent work management should not be reinvented for the application and tangled up with it, but delegated to dedicated runtime systems.

Principles of task-based parallel programming

Parallel programming is a matter of assigning pieces of work to workers. Parallel programming models can be classified in three broad classes, whether they let programmers primarily focus on managing entire processes, such as with MPI, focus on managing workers, named "threads", within such processes in the case of thread-based parallel programming models, or focus on expressing the pieces of work to be done, named "tasks", in the case of task-based models. The common idea of task-based parallel programming models is to let the application programmer define elementary blocks of source codes, e.g. "pieces of work", as individual tasks, and then express the application core algorithms in terms of sequences of those tasks.

A task-based programming model typically works together with an execution model supplied by a runtime system. The application submits execution requests for tasks in sequences to the runtime system, oftentimes inheriting understood sequential semantics from the original program, while the runtime system executes the tasks in the background on the available processing units in parallel, using some scheduling algorithm. Additional directives and constraints let the application core express semantic information and hints such as relationships among tasks or relationships between tasks and pieces of data, to guide the parallel execution process.

Task-based execution models

Task work requests are collected and executed in the background by a runtime system. The runtime system is therefore in charge of driving the execution of the application tasks while efficiently exploiting the available hardware resources.

Fig. 2: Illustration of the way the abstract representation of an application given by the task graph can be used by a runtime system to map tasks on available, possibly heterogeneous platforms. Tasks can be dynamically mapped to appropriate processing units using scheduling algorithms. Data consistency between devices can be enforced using data dependence edges. Prefetch operations can be triggered automatically to overlap data transfers with computation.

The semantics information constituted from the flow of submitted tasks and their dependencies is commonly referred to as the task graph. This task graph synthesises the application structure in a conceptual object that can be exploited by the runtime system in many ways to perform operations on behalf of the application programmer, beyond the parallel execution of tasks, see Fig. 2. The task graph may be hierarchical, with nested tasks, in order to control the maximum degree of parallelism, and inherent synchronisation and contention, managed at a time. Data dependence edges in the task graph, for instance, let the runtime system infer when to trigger data transfers between computing nodes, as well as inside nodes between memory spaces (main memory, specialised memory, device-embedded memory).

Computation/communication overlap and data prefetches can be handled transparently, in the process, to minimise idle times. The runtime system can even eliminate redundant data transfers using data replication and caching techniques. Other examples include using task graph information to enable dynamic resource management, malleable jobs, fault tolerance enforcement, to guide checkpointing and recovery operations, or deciding when to page data to disk and when to fetch it back in out-of-core execution scenarios on large datasets, for instance.

Thanks to their flexibility, task-based models can co-exist alongside other common HPC models, including other taskbased models. This enables scenarios such as the incremental transformation of legacy codes into task-enabled codes for languages such as C, C++ and Fortran, the composition of multiple models such as tasks with MPI, the coupling of multiple codes, and even the active interoperability between models, as demonstrated in H2020 Project INTERTWinE [H2020INTW].

Properties of task-based programming models

Task-based programming models invite programmers to express applications in terms of elementary tasks and dependence relationships. This semantically rich abstract representation enables runtime systems to handle the resource management and load balancing duty on behalf of programmers. Furthermore, the clear separation of the stable machine-independent application structure from well identified machine dependent task routines greatly simplifies porting efforts. The resulting performance portability ensures a quick short term return on investment on new platforms, while preserving long term software development investment.

Using a task-based model, programmers focus on decomposing their programs into tasks, while delegating it to the runtime system to decide how tasks are mapped to the available execution units of a parallel system and how data is managed across the memory hierarchy. This change in mentality from managing processes or threads of execution to describing the work to be done is in some ways similar to the move from assembler to Fortran/C or the move to structured programming. In all cases, application development is easier, safer and more efficient for human programmers and application analysis and optimisation is easier, safer and more effective for tools.

Fig. 3: Overview of the task-based programming approach. An application submits tasks to a runtime system in charge of executing them on the available resources, thanks to the property of management delegation. Task implementations can be supplied through multiple means ranging from custom routines to kernels from highly optimised vendor libraries, thanks to the property of separation of concerns. Hardware-specific device drivers bring the property of performance portability.

Task-based models facilitate performance portability [Dokulil16, Agullo17, Garcia20] by enforcing a clear separation between the task submission side of an application, to be kept largely unchanged across platforms, and the architecturespecific code concentrated in variants of the task kernel routines for CPUs, GPUs, FPGAs, PIM, and so on. The load balancing work over available computing units is handled by the runtime system scheduler. Task-based models also naturally bring the property of separation of concerns as a key added benefit, especially in HPC. Fig. 3 presents an overview of the task-based programming approach and illustrates these properties.

Indeed, the application core algorithm designers, task kernels designers, task scheduling algorithm designers, runtime systems designers can be distinct persons, experts in their own domain, contributing to the same application in a safe and efficient manner, thanks to the proper isolation of each specific concern. In particular, the popularity of highly optimised routines from vendor-specific linear algebra libraries such as Intel MKL or NVIDIA CUBLAS show the interest of a portability strategy concentrated on kernels.

Task-based models inherently increase application robustness as well. Using task relationship information with other tasks and with pieces of data, low-level concerns such as task synchronisation and data consistency management can be handled transparently. Further, task routines abiding by the functional programming concept of a pure function, that is, with no hidden internal side effects or dependencies, can be scheduled under a deadlock-free guarantee in any constraints-compliant order. Tasks can also have known side effects and dependencies, as required for deadlock-free interoperability with other programming models or APIs, such as MPI.

In some specific application cases, simpler abstractions may be more convenient and effective than tasks. Examples of such high level layers include data-flow programming models, stencil-oriented models, or skeleton programming models, for instance (see Fig. 3). These models may however be offered as high level programming layers on top of task-based programming environments, to get the benefit of an increased case-specific abstraction, while preserving the performance portability and ecosystem integration properties of task-based models.

Task-based parallelism initiatives in Europe

OCR-Vx

The OCR-Vx asynchronous, task-based runtime system [OCRVx] developed at the University of Vienna, Austria, is based on the Open Community Runtime specification [OCRspec] proposed in the context of the US XStack (Exascale Software Stack) initiative. The central idea of OCR is to decouple a program's computations and data from the actual execution units and memory locations of a parallel system, based on the concepts of event-driven tasks and data blocks. To support dynamic program adaptation and facilitate fault tolerance, both tasks and data blocks are relocatable. OCR-Vx has been implemented in C++ for shared and distributed-memory systems.

Recommendations for 2024-2025

Best practices

The community should promote best practices in application porting. Application developers should be encouraged to trust low-level software layers to extract performance from declarative information. Adaptation efforts should focus on short kernels within a stable application structure. As applications are getting ready for the exascale transition, now is also the time to encourage long term-oriented, performance-portable programming using task-based models, for instance, with the help of PRACE and national supercomputing entities.

Research in task-based programming models

Research in task-based programming models should continue to improve and extend low-level resource management and data locality decisions through more expressive abstractions and compiler/runtime intelligence. New platforms and hardware, such as FPGAs and PIM, provide important new challenges, often benefiting from the re-evaluation of previous ideas in the new context. Similarly, the programming model support layers should be extended to support new usage models such as malleability, for which the tasking model provides a natural way for the program to react to changing resource availability. In addition to supporting tasking within a node, as hybrid MPI+X, we should continue investigating tasking programming models across nodes. In complex applications, programming model interoperability and composition are important, as is interoperability with other components such as the job scheduler, for which standardisation will be important, perhaps via PMIx. The task graph information and separation of concerns bring the opportunity for more accurate performance analysis and debugging tools. In addition, the HPC ecosystem should be ready to incorporate ideas from other fields that face similar problems, e.g. in cloud computing.

Ecosystem and standardisation

There is a vibrant ecosystem of programming model research in Europe, and now is the time to increase the TRL and make them ready for production use in exascale supercomputers using large-scale applications. Since long-term software development depends on the stability of all prerequisites, including stable and supported implementations of the programming models, the most successful approaches should be incorporated into open standards. Tremendous progress has been achieved and a broad consensus has been reached, especially through the OpenMP initiative. It may not be possible to incorporate everything into OpenMP, but open standardisation is one of the best ways to enable programming model uptake and portability across vendors.

Conclusions

This white paper has reviewed the case for task-based performance portability and identified what is needed to drive greater adoption. We discuss why the task abstraction provides a clean, stable and dependable interface between the machine-independent application programmer, library or domain-specific language implementation and the machinedependent software layers. We also outline the academic and industrial research needed to realise the vision of performance portability across current and future architectures and problems.

  Overall, such common HPC application design techniques therefore suffer from significant issues to keep up with a fast evolving supercomputing landscape. Task-based programming models such as StarPU [Agullo17] (Inria, France), OmpSs [Duran11] (BSC, Spain), OCR-Vx [Dokulil16] (University of Vienna, Austria) and DuctTeip [Zafari19] (University of Uppsala, Sweden), developed in Europe, as well as non-European initiatives such as HPX [Kaiser14], Legion [Bauer12], OCR [OCRspec], PaRSEC [Hoque17], to name a few, all define a clear software design path to address these issues.

  StarPUThe StarPU runtime system[StarPU,[START_REF] Agullo | Achieving High Performance on Supercomputers with a Sequential Task-based Programming Model[END_REF] is developed in Bordeaux, France at Inria and the LaBRI laboratory. A key characteristic of StarPU is its performance model-based heterogeneous scheduling ability on computing nodes equipped with accelerators. It can be programmed either directly, as in the FLUSEPA code from Airbus [Flusepa], through libraries such as the Chameleon [Chameleon] (dense) and PaStiX [PaStiX] (sparse) linear algebra solvers, or from higher level programming models such as OpenMP and SkePU.OmpSs is the parallel programming model from Barcelona Supercomputing Center, which is part of a 10+ years' investment in programming model research[Duran11, Perez17]. It provides annotations to a sequential program with a single address space/namespace which is able to execute in parallel through the runtime computation of task dependencies. OmpSs has been the forerunner for tasking in OpenMP 3.0 and task dependencies in OpenMP 4.0, and many improvements in subsequent versions of OpenMP, such as reductions, commutative, concurrent, task-loops were the result of research on OmpSs. The latest version, OmpSs2, is supported by the Mercurium source-to-source compiler and Nanos6 runtime system.

	OmpSs

This work was supported by the Spanish Government (contract PID2019-107255GB), Generalitat de Catalunya (contract 2014-SGR-1051), and the European Union's Horizon 2020 research and innovation programme under grant agreements No 955606 (DEEP-SEA) and No 754337 (EuroEXA). Paul Carpenter holds the Ramon y Cajal fellowship under contracts RYC2018-025628-I of the Ministry of Economy and Competitiveness of Spain. This work was supported by the French Government (contract ANR-19-CE46-0009), Région Nouvelle Aquitaine (contract 018-1R50119) and the European Union's Horizon 2020 research and innovation programme under grant agreements No 671602 (INTERTWinE) and No 801015 (EXA2PRO). This work was supported by the Austrian Science Fund grant P29783.

Authors:

Olivier Aumage is a full time researcher at Inria in Bordeaux since 2003; his main research topics include parallel runtime systems, programming models and languages for high performance computing applications.

Paul Carpenter is a Senior Researcher at Barcelona Supercomputing Center since 2011. His research interests include performance-portable parallel programming models, system software and energy-efficient architectures.

Siegfried Benkner is a professor of Computer Science at the University of Vienna where he focuses on research in programming models, languages compilers, runtime systems, and tools for high performance computing.


David Eschbach

Laurent Schmitt

Arthur Zimmermann

Quentin Lejeune

Evaluating a

come

1932-1977: Canalization

Ten dams were built on a French lateral artificial canal. The former main channel became by-passed (Old Rhine).

Engineering works of the Upper Rhine River

1. Diachronic analysis of old maps (since 1828) and aerial photos (since 1949) 2. Historical analysis of water and groundwater levels 3. Geomorphological and sedimentological studies of the Bauerngrundwasser on 7 transects (leveling, bathymetry, lidar, laser granulometry of 31 samples, magnetic susceptibility, Passega method).

Morphodynamics was active at the beginning of the 19 th century (high lateral mobility, many lateral braiding and anastomosing channels...). The current channel of the Bauerngrundwasser was the main talweg of the Rhine (180 years ago). The narrowing after the beginning of the engineering works is more than 100m.

The Rhine palaeo-channel before correction has been gradually filled with sand and silt deposits (maximum thickness of 1.60m; Fig. 4). Passega analysis revels low energy during fine sediment deposition (Fig. 5).

Pre-and post-restoration scientific monitoring:

-interdisciplinary monitoring (vegetation, macroinvertebrates, water and sediment quality...); -hydrological monitoring (hydrogeology, hydraulics, gauging, GW-SW exchanges...); -geomorphological monitoring (PIT tags, erosion chains, transverse and longitudinal profile, laserscanning, high resolution aerial photos...); Hydraulic modeling incorporating bedload transport and morphological evolution in order to provide to the managers long-term managment scenarii; Development of a simplified but fonctional monitoring protocol for a long-term survey. Bravard and Peiry, 1999) Integrated in the RAMSAR area of the Upper Rhine, the Rohrschollen island exhibits a high biodiversity. This artificial island results of many engineering works which impacted typical habitats and biocenoses. The LIFE+ project "Restauration de la dynamique des habitats alluviaux rhénans sur l'île du Rohrschollen", managed by the City of Strasbourg, plans to restore the hydromorphological and ecological functionality of the hydrosystem (dynamic floods, bedload, channel mobility, surface water-groundwater exchanges, renewal of pioneer ecosystems…) making this project one of the most ambitious for the French side.

David Eschbach (1) , Laurent Schmitt (1) , Arthur Zimmermann (1) , Quentin Lejeune (1) , Pascal Finaud-Guyot (2) Evaluating a functional hydromorphological restoration of a lateral channel of the Upper Rhine (France): first results and implications of the temporal trajectory to restoration Surrounded by an upstream diversion dam and a downstream agricultural dam, the Rohrschollen island is flooded only when Q > 2800m 3 .s -1 . Furthermore, the water velocity is extremely low. During low flow periods, a minimum flow of 15m 3 .s -1 feeds the Old Rhine. The Bauerngrundwasser anastomosing channel is extremely stable (no lateral dynamics, deposition of fine sediments, standing water aquatic communities...).

The Rohrschollen island and the Bauerngrundwasser anastomosing channel

III. Methods

III. Methods

IV. Results

IV. Results

Perspectives concerning the whole monitoring program

Perspectives concerning the whole monitoring program

References References

Conclusion Conclusion

Potential future lateral erosion (arrows, Fig. 6) will mostly introduce into the channel of the Bauerngrundwasser fine sediments which constitute a limiting factor for the development of aquatic biocenoses. Bedload transport and lateral mobility, who increase alluvial biodiversity will essentially occure along the new upstream channel. This study reveals the importance of taking into account past temporal trajectories (hydrosystem are palimpsests!) in order to increase the efficiency and sustainability of restoration projects.

The Bauerngrundwasser will be reconnected to the Rhine thanks a new upstream connection channel (800m; Fig. 1). When the discharge of the Rhine is higher at 1500m 3 .s -1 a maximum of 80m 3 .s -1 can been injected in the anastomosing channel. The goal is to induce morphodynamics in the channel and dynamic floods in the island.

Principles of the restoration

II. Objectives of the poster

II. Objectives of the poster

Characterise the temporal trajectory of the hydrosystem in order to improve the understanding of the current fonctionning, identify the type of sediments (texture) which will be introduced in the channel by lateral erosion and give long-term evolution tendancies of sediment transport and morphodynamics.

RS: homogeneous suspension deposits

QR: graduated suspension deposits

  Rectification and stabilization of a single main channel. A flooding area is maintained between two dikes.

Fig 5 -

 5 Fig 5 -Passega image (C/M relation;Bravard and Peiry, 1999)

( 1 )

 1 Fig 1 -Location of the Upper Rhine, the Rohrschollen island and the Bauerngrundwasser channel (adapted by Schmitt, 2010)

Fig 3 -

 3 Fig 3 -Transverse profile nr 2 with topographic survey and sedimentological coring Fig 4 -Five sedimentological logs according to color and texture (location Fig. 6)

  Fig 3

T2Funding:

  European community (LIFE+), Agence de l'eau Rhin-Meuse, Département du Bas-Rhin, DREAL Alsace, Région Alsace, Electricité de France, Ville de Strasbourg