{'fraction_non_alphanumeric': 0.02663458152365301, 'fraction_numerical': 0.007054818640685526, 'mean_word_length': 4.799251191286589, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Routing Strategies for LoRaWAN Multi-hop Networks: A Survey and an SDN-based Solution for Smart Water Grid

Low PowerWide Area Networks (LPWANs) are becoming the most suitable communication technologies in the Internet of Things (IoT) applications due to their low power consumption, long communication range and low cost. Currently, Long Range Wide Area Network (LoRaWAN) is one of the most popular LPWANs. Because it offers the possibility to build private networks with an open standard, LoRaWAN is the most deployed LPWAN solution. However, LoRaWAN supports only one-hop communication, that is, the end-devices are connected directly to the gateways. Since LoRa links can be kilometers long, its signals may undergo interference with other radio signals or encounter obstacles such as buildings, trees. In urban areas, to ensure that indoor LoRa devices can successfully transfer data back to remote gateways (GWs), a dense deployment of GWs is required. Unfortunately, the deployment of many GWs increases the network cost. Multi-hop communication can be exploited to increase LoRaWAN network coverage and packet delivery ratio (PDR) without deploying additional GWs. Therefore, in order to improve LoRaWAN performance, different routing approaches have been recently proposed aiming to create LoRaWAN multi-hop networks where some devices can play the role of relay nodes. However, in some use cases like SmartWater Grid (SWG), where nodes are buried underground inside the pipelines, the use of some SWG devices as relay nodes is not efficient in terms of energy consumption. In this paper, we first provide an in-depth survey on different routing protocols proposed for LoRaWAN multi-hop networks followed by a useful comparison between these approaches. Then, to enable efficient peer-2-peer (P2P) communication between end-devices in SWG, we propose a routing protocol based on Software Defined Networking (SDN) where some specific nodes called Relay Nodes (RNs) relay data from leakages detection nodes. In the case where a sensor detects a leak, a signal is sent to shut off the water valve automatically through our routing approach. Through simulations under LoRaSim, our proposed solution outperforms the standard single-hop network in terms of energy consumption and packet error rate. A range of issues, problems are provided and some research directions are suggested.

include low devices cost, and the possibility to build a private network.

A. PROBLEM STATEMENT AND MOTIVATION
Typically, LoRaWAN supports only one-hop communication between the end-devices and the gateways. As we have shown in our previous work [2], in optimal conditions, one LoRa gateway can manage thousands of end devices. In that case, all these devices will send their data packets through an individual link to the gateway. This situation may overload gateway capacity. For instance, In the SWG scenario, smart water meters are installed in customers' homes or offices in order to communicate in near-real-time, the water consumption data to the water utilities. In that case, each smart water meter must have a LoRa module in order to provide LoRa communication. Thousands of these water meters are located in buildings. Although LoRaWAN allows parallel transmissions, the traffic will disrupt communications. In the default specification of LoRaWAN, the star topology is adopted while the use of neighbor devices to relay data is not allowed. However, as LoRaWAN achieves very long transmission range, every device can obviously have different neighbors within its transmission range. These neighbor nodes can play the role of relay devices to forward data packets of other devices that are not able to communicate directly with the gateway or achieve poor communication with the gateway. Additionally, in LoRaWAN technology, to achieve long communications range, the higher SFs are used which increases the Time on Air (ToA) and therefore increases the energy consumption. Moreover, due to electromagnetic interference [7] coming from other wireless networks (such as ZigBee, Wi-Fi, etc.) or obstacles (such as mountains, trees, buildings, hills in remote monitoring, tall crops, and underground vaults), LoRaWAN long-distance links may undergo packet losses. The mentioned obstacles create non-line-of-sight conditions that increase considerably the packet losses. The idea to deploy more LoRaWAN gateways in order to avoid packet losses and also increase the network coverage is not a suitable solution mainly due to three reasons: (1) gateways usually require AC mains power which is not possible in remote areas, (2) The deployment, management, and internet access costs will be very high with the increased number of gateways (3) the suitable places where the gateways will be deployed is also a challenge. Therefore, the use of star topology in current IoT scenarios under-utilizes the available network resources which can be efficiently exploited in order to increase the network coverage, decrease the energy consumption and therefore improve the packet delivery ratio.
To cope with the above-mentioned issues, recently, the LoRaWAN multi-hop communications have attracted researchers' attention and some mechanisms have been proposed to enhance LoRaWAN performance, exploit efficiently network resources, and better utilize the nodes. More specifically, different routing approaches have been proposed by researchers to enable multi-hop communications in LoRaWAN where nodes near the gateway relay data of nodes far from the gateway. Each routing approach is designed to deal with a specific problem of the standard LoRaWAN protocol. Typically, three important issues are addressed by the current routing approaches proposed for LoRaWAN multi-hop networks: (1) Minimize energy consumption, (2) Extend network coverage, and (3) Minimize network latency. In section IV (FIGURE 2), we provide a classification of current routing approaches in terms of these three issues while TABLE 1, 2, 3, 4 summarize their features.

B. LORAWAN PROTOCOL REQUIREMENTS IN MULTI-HOP NETWORKS
One critical issue of multi-hop LoRa is related to the management of the duty cycles. The awaking intervals of relay nodes must be considered during the design of any routing approach because let relay nodes in active mode as a normal gateway is not efficient in terms of the entire network lifetime. Therefore, each routing approach surveyed in this paper is evaluated in terms of the duty cycle metric. Routing approaches that schedule periodic awaking intervals and enable relay nodes to transmit their aggregated traffic while guaranteeing the duty-cycle constraint are more preferred.
Additionally, as LoRaWAN operates in license-free subgigahertz radio frequency bands like EU433 (433.05-434.79 MHz) and EU863-870 (863-870/873 MHz) in Europe, each routing mechanism must adhere to this duty cycle restriction. For instance, in EU regulation, LoRaWAN defines the following sub-bands and their duty cycle: Moreover, in its header, the LoRaWAN packet has at least 13 bytes while, depending on the region, the payload varies between 59 and 230 bytes. Thus, this places a severe constraint on the data that can be contained in the LoRaWAN packet headers and still leave a great space for the application payload.
Also, there is a constraint on the receive windows. Indeed, either in class A, B, or C, every node after transmission must open two receive windows for downlink data coming from the network server. For large-scale networks, the routing process may take too long. The response from the server will come very late and the receive windows will be closed by the end device increasing the packet losses.
Therefore, to operate correctly, any routing approach must fulfill the above-mentioned requirements of LoRaWAN protocol in order to be considered in real deployment.
However, enable some nodes to relay data from other nodes far from the gateway is feasible in some scenarios but is difficult to be employed on some devices like SWG nodes powered by batteries and buried underground inside the pipelines where the radio penetration is very harsh. These nodes are deployed along pipelines for events detection (leakages) [8]. The use of some SWG devices to relay data is not advantageous in terms of energy consumption as these nodes are powered by batteries whose replenishment and recharging are infeasible. This special case is considered in this paper and a routing approach is proposed to enable efficient P2P communication while minimizing the energy consumption and extending the network coverage.

C. CONTRIBUTIONS AND PAPER ORGANIZATION
In this paper, our contribution is twofold: • We first provide an in-depth study on routing strategies proposed in the literature to enable multi-hop communications in LoRaWAN networks. We categorize these approaches into clustering and concurrent routingbased approaches, IPv6-based approaches, and Ad-Hoc multi-hop communication approaches. We also provide a significant comparison between these approaches by considering several features. Additionally, we highlight the technical problem that each routing approach is conceived to deal with. Moreover, we mention how each routing strategy manages the duty cycle of RNs and enddevices. • We propose a hierarchical clustering routing approach based on SDN by using SWG as a use case. In our approach, instead of using some SWG devices as relay nodes, we propose to deploy some low-cost and energy-efficient relay nodes (RNs) which will relay data between remote nodes and the main gateway. These RNs are running on batteries, they do not need to be connected to the Internet. They have equipped with a LoRa module to provide LoRa communications and have only one task, relay data between SWG nodes and the main gateway. We consider that these RNs are deployed in optimal places and the SWG nodes need to discover their presence. We propose an algorithm to enable RNs discovery and assign to each node, a specific RN. During data communication, each RN forwards only the data of its children. To enable efficient peer-2peer (P2P) communication in SWG (especially shut off smart valve via signal coming from a sensor in the case of a leak), we propose to add the SDN controller functionalities to the LoRaWAN network server to dictates the entire network.
In the following section, we discuss the related work while section III provides an overview of LoRaWAN technology. Section IV discusses the routing strategies proposed for LoRaWAN multi-hop networks while section V presents our SDN-based solution to enable P2P communication without involving the gateway. Section VI provides the simulations results of our proposed SDN-based solution while section VII discusses the research findings. In section VIII, we provide a range of challenges, issues and give some research directions to follow. The paper is concluded in section IX.

II. RELATED WORK
In the literature, according to our best knowledge, only two papers have conducted a survey on routing strategies proposed for LoRaWAN multi-hop networks. Researchers are actively proposing some novel mechanisms to enable routing in LoRaWAN multi-hop networks. Our goal is to first provide a survey on routing strategies proposed by other researchers and then present our solution by considering the SWG use case.
Very recently, Osorio et al. [9] conducted a survey on routing strategies proposed for LoRaWAN networks. The authors grouped these strategies into tree topology and flooding approaches. They discussed for each group, different mechanisms proposed by researchers to enable multi-hop communications in LoRaWAN networks. The authors also highlighted some challenges and issues that must be addressed in LoRaWAN multi-hop networks. However, the work of Osorio et al. [9] is not comprehensive, several recent routing approaches proposed for LoRaWAN multi-hop networks are missed. Additionally, they considered only tree and flooding approaches while ad-hoc multi-hop communication approaches have been not mentioned. In contrast to Osorio et al. [9], we categorize the current routing strategies into Clustering and Concurrent Transmissions based approaches, IPv6-based approaches, and Ad-Hoc Multi-Hop Communication approaches.
The last paper is proposed by Corim et al. [10]. In their paper, Cotrim et al. provided a review of the state-of-theart multi-hop proposals for LoRaWAN mesh networks. They also carried out a comparative analysis and classification, considering technical characteristics, intermediate devices function, and network topologies. Typically, in LoRaWAN multi-hop networks, a data packet send by an end-node will be forwarded by the intermediate nodes until it reaches a gateway (s) connected to a Network Server. In that case, the intermediate nodes can simply relay data from other nodes or perform complex routing mechanisms. The authors of [10] discussed both approaches that employ intermediate nodes as simple relay devices and approaches where relay nodes perform complex routing processes. However, the authors mainly focused on LoRaWAN mesh networks. We considered in this paper, both mesh, tree, and flooding strategies by adopting our own classification. In addition to our proposed SDN-based solution, our paper combines both the work of Corim et al. [10] and Osorio et al. [9]. Besides that, we discuss some critical metrics that any routing approach must consider in multi-hop LoRa which are mainly, the management of the duty cycles, reception windows of nodes, duty cycle restriction, payload. These metrics are not considered by the two above survey papers. Our goal is to extend the state-of-the-art by filling some gaps in the previously mentioned research papers.
We first provide an in-depth survey on routing strategies proposed for LoRaWAN multi-hop networks. Then, we propose an SDN-based solution to enable P2P communication without involving the gateway in SWG applications. It is VOLUME 4, 2016 worth mentioning that in contrast to the above two surveys, our paper is more comprehensive.

III. LORAWAN TECHNOLOGY
LoRaWAN technology consists of LoRa physical layer and LoRaWAN network protocol. LoRa is a wireless modulation technique used to create long range communications. Semtech is the proprietary of this radio technology. Lo-RaWAN is an open-source protocol developed by LoRa Alliance. It defines the communication protocol and the network architecture. In what follows, we describe separately LoRa modulation and LoRaWAN protocol.

A. LORA MODULATION
LoRa [11] is a physical layer which is patented by Semtech and is based on Chirp Spread Spectrum (CSS). CSS enables high receiver sensitivity. LoRa spread spectrum modulation scheme provides high link budget, allowing long-range communications at very low power consumption. LoRa physical layer also uses forward error correction codes to increase the robustness against noise.
LoRa operates in unlicensed bands (868 MHz in Europe, 915 MHz in US and 433 MHz in Asia). In EU, LoRa can operate in two sub-bands. One sub-band at 868 MHz and another at 867MHz. The first sub-band offers three 125 KHz LoRa channels while the second sub-band offers five 125 kHz LoRa channels. A LoRa gateway should be able to listen to all channels at the same time. LoRa implements six orthogonal Spreading Factors (SF7 to SF12) within a fixed channel bandwidth. Depending on the SF, the data rates vary from 300 bps to 50 kbps in Europe and 900 bps to 100 kbps in US [12].
LoRa transceivers (end-devices and gateways) have typically the five following parameters to configure [13] • Bandwidth (BW): One of the following three BW can be selected: 125 kHz, 250 kHz and 500 kHz. The larger the bandwidth is, the more the data rate, the more air time, and the lesser the sensitivity. In LoRaWAN technology, every connected device must be activated either through over-the-air activation (OTAA) mechanism or activation by personalization (ABP) [8]. In any case, according to the specification of LoRaWAN standard, nodes and gateways only communicate directly (star-of-stars topology), that is, nodes use only one hop to reach one or more gateways. Therefore, no routing scheme is provided by Semtech. As mentioned above, because LoRa links can be kilometers long, its signals can encounter obstacles such trees or buildings. Therefore, to mitigate these issues and improve LoRaWAN performance for IoT applications, different studies proposed routing approaches to create multi-hop communications. Routing approaches allow data packets to traverse the network from the source node to the destination node via several hops.
In FIGURE. 1, we present an example of a LoRaWAN network with different use cases such as smart agriculture, smart grid, smart transportation, smart home and so forth. In this figure, we show two gateways at the center of circles which relay seamlessly information between the end-devices and the LoRaWAN network server. We also show one impor-  tant feature of LoRaWAN technology: A message send by an end-device (the smoke detector in our example) is received by all gateways located within its communication range. All the redundant information will be filtered by the LoRaWAN network server.

IV. REVIEW OF ROUTING APPROACHES PROPOSED FOR LORAWAN MULTI-HOP NETWORKS
We categorize the routing strategies proposed for LoRaWAN multi-hop networks into Clustering and Concurrent Transmissions based approaches, IPv6-based approaches, and Ad-Hoc Multi-Hop Communication approaches. Additionally, as each approach is designed to address a specific problem of LoRaWAN network, we also highlight the problem solve by each approach in FIGURE 2. In what follows, we review the approaches proposed to enable multi-hop communications in LoRaWAN networks for each group. For each routing approach investigated in this paper, we check its features to ensure that it fulfills the requirements provide in section I-B.

A. CLUSTERING AND CONCURRENT TRANSMISSIONS (CCT) BASED APPROACHES
LoRaBlink, proposed by Bor et al. [14], was the first proposal that includes several points, such as multi-hop communi-cations. LoRaBlink was proposed to provide low latency, reliable, and energy-efficient multi-hop communications in LoRa networks. It integrates MAC and routing in a single simple protocol. The proposed approach is divided into a beacon period for synchronization and a data period. The gateway which is connected to the network server initiates the entire network operation by sending a beacon. The direct nodes that can hear the gateway receive the beacon and use the flooding approach to transmit concurrently their own beacons. By exploiting the capture effect of the concurrent transmissions of LoRa, at least one beacon will be received by the other nodes that can not hear the gateway. The next nodes will perform the same process and increment the hop count by one. When a node receives a beacon, it checks if its hop count to the gateway is lesser than the hop count includes in the beacon message. If it is the case, the message will be discarded. After the beacon period, a node that has data selects a slot and broadcasts it. This message is flooded until it reaches the gateway. Nodes that receive the message check if their hop count to the gateway is lower than the source node hop count to the gateway. Only nodes with a lower hop count to the gateway will relay the message and send an Acknowledgment (ACK) to the source node. When VOLUME 4, 2016 the gateway finally receives the message after several hops, it replies with an ACK. The ACK is also flooded concurrently until it reaches the previously source node that sent the data. Although the proposed LoRaBlink is simple, it is not efficient in large-scale networks due to several collisions. Additionally, the protocol is not efficient in terms of energy consumption. Duty Cycle restriction: Duty cycle restriction was considered in the proposed approach. Time Synchronization: It is ensured through flooding beacon approach. During Beacon and data transmission period even though a node has no data to transmit, it must be in listening mode which is not advantage in terms of energy consumption.
Receive windows of nodes: Not specify (NS) in which class devices are working Payload: 10 bytes per node A tree routing method called synchronous LoRa mesh is proposed by Ebi et al. [15]. In synchronous LoRa mesh, the network is partitioned into sub-networks and each subnetwork has a Root Node and a set of Sensor Nodes (SNs). Both Root Node and SNs are battery-powered and thus have energy-constraint. SNs not only transmit their own data but also forward data packets of other SNs to the Root Node. Each Root Node compresses data received from all its connected SNs into a single LoRaWAN packet and transmits it to the gateway. Contrary to not listen before talking known as aloha adopted in LoRaWAN, in the proposed protocol, a communication cycle is created using Time Division Multiple Access (TDMA) in which each Root Node assigns time slots to its connected SNs to listen. The communication cycle consists of a synchronization phase where a certain time slot is allocated, a network joining and approve phase, a data transmission phase, either up-or downlink communication. After data transmission period, a certain time slots are assigned to Root Nodes to communicate with the gateway. Finally, the cycle is completed by a so-called guard period in which all nodes are inactive. The guard phase ensures adherence to the required LoRaWAN duty cycle restriction. Duty Cycle restriction: The so-called guard period enables adherence to duty cycle restriction. Time Synchronization: It is ensured through beacon flooding approach initiated by Root Nodes. Receive windows of nodes: Not specify in which class devices are working Payload: 51 bytes per communication cycle for a relay node of 5 children meaning 10.2 bytes for every LoRa node to transmit. However, the protocol uses the fixed Spreading Factor (especially SF9). Parallel transmissions are not possible due to the used of fixed SF. Additionally, given a maximum payload (for example 51 bytes for DR0), the number of SNs a single Root Node is able to manage will be very low because the final data compressed by the Root Node will not exceed this maximal payload.
Lee and Ke [16] proposed a tree routing protocol called LoRa mesh which is a wireless mesh network based on LoRa PHY. In the proposed solution, the tree rooted is created at the LoRa GW which holds a data structure storing the list of nodes joined to its network. Initially, the gateway broadcasts, every 60 seconds, beacons inviting nodes to join its network. LoRa node that can hear the beacon may join the GW network by sending a JOIN message and then set the gateway as its parent. Once the gateway has at least one child node, it stops broadcasting beacons and starts gathering data. When this gateway child sends data, these data packets become beacons for other nodes located far from the gateway and cannot hear its beacons. Nodes that are far from the gateway will receive data sent by the gateway children as beacons and can then join the gateway network by sending a JOIN message and add the gateway children as their parents. When these new nodes send data, the packets sent will become beacons for other nodes. These new ones can join the network by sending a JOIN message adding the previous nodes as their parents. The process iterates until the network is completely constructed. Nodes join a network of their choice by using the Received Signal Strength Indicator (RSSI) and hop count to the GW. The gateway will finally have a complete list of nodes in the network. According to the authors' simulations, the proposed routing protocol solves some transmission issues between nodes while enhancing network reliability. Duty Cycle restriction: The duty cycle restriction was considered. Time Synchronization: No synchronization is considered in the proposed routing scheme between parent nodes and sensor data nodes. Authors used Beacon message to construct the network topology. This solution is not efficient for battery-powered nodes as nodes need to work in class C.
Receive windows of nodes: Nodes are working in class C. Payload: 20 bytes However, the authors do not consider the downlink communication scenario. Zhu et al. [17] proposed a Tree-Based SF assignment strategy called SF Clustering Algorithm (TSCA) to improve the capacity of mesh networks in LoRa. The entire network is sub-divided into sub-trees and all nodes of each sub-tree use a specific SF to send data packets. TSCA supposes that the root node (gateway) can communicate with its 1-hop relay nodes by using all SFs (SF7-SF12) in parallel. Initially, the TSCA algorithm first builds a well-connected network in which all nodes of the network use SF7 and secondly initializes five empty trees (one for each of the remaining SF, SF8, SF9, SF10, SF11, and SF12). Then, TSCA uses the Bottom-up Breadth-First Searching algorithm (BBFS) to extract nodes from the initial tree with SF7 and the Topdown Breadth-First-Search (TBFS) algorithm to insert the extracted nodes on the suitable trees. The proposed approach aims to minimize the number of hops and the delay. The nodes insertion is done in such a way that the airtime balance among trees is achieved. As higher SFs means more airtime, sub-trees with higher SFs will have fewer hops compared to others with smaller SFs. Through simulations and an experimental deployment, the authors: (1) ensured the connectivity of all sub-trees (2) achieved short airtime of each sub-tree by reducing the hop count and (3) balanced the traffic loads between all sub-networks. Duty Cycle restriction: The duty cycle restriction was respected. Time Synchronization: No synchronization is considered. Receive windows of nodes: Not specify. Payload: Not specify Paul [18] presented a clustering-based routing approach for LoRaWAN networks. The proposed approach considers a LoRa gateway and partitions the network into several clusters. A cluster in the protocol is a set of nodes that have the same number of a hop count to the gateway. The protocol starts with the formation of clusters based on the distance of nodes to the central gateway. Virtual rings are deployed around the gateway following a linear or non-linear distance spreading model and each node of the network is associated with its closest virtual ring. Nodes in a lower ring forward data of nodes of a ring above them. In other words, the nodes in a lower ring act as parents of nodes in the upper ring. A similar routing approach is proposed in [19]. Duty Cycle restriction: No duty cycle restriction is considered in the simulations. Time Synchronization: It is ensured through TDMA. Receive windows of nodes: Not specify. Payload: Not specify Duong and Kim [20] considered a linear network and proposed a simple routing protocol to improve LoRa network coverage. The protocol consists of the network initialization period where the linear network is constructed and a data transmission period. The gateway starts forming the network topology by broadcasting a Request Init Message (REQ) containing the maximum depth of the network and the passed time set to one. Every node after receiving the REQ message prepares its own REQ including the maximum depth of the network and increments the passed time by one. Then, it sends the packet to its next grade node. Nodes use the passed time to calculate the remaining time to go to the data collection period. Each node also sends a Feed-Back (FB) message to its parent after receiving the REQ message. Every node except the leaf node performs overhearing to ensure that the next grade node has successfully received the REQ message. The process is repeated until the network initialization period finishes. At the end of network construction, every node knows exactly when to go to the data collection period through passed time previously initiated by the gateway. After network construction period, the data are sent in pipeline fashion. The leaf node starts the data operation period by sending data to its parent. By using the passed time and the maximum depth of the network, each node calculates the wake-up time to receive data of its child. The authors proposed an algorithm to enable nodes to calculate the wakeup time. When a node wake-ups, it first turn on in receiving mode to receive data of its child, aggregates the received data with its own data, and then sends it to its parent node. Duty Cycle restriction: No duty cycle restriction is considered. This will be an issue because the authors stated in their paper that, nodes will re-transmit data in the case of failure but however didn't respect the duty cycle restriction of LoRaWAN protocol. Time Synchronization: It is ensured through the passed time and maximum depth of the network include in the REQ message. Every node knows exactly when to wake up to receive data of its child node, aggregates it with its own data, and sends it to its parent. Receive windows of nodes: Not specify. Payload: Not specify However, the proposed approach presents high latency even though it achieves high reliability. Additionally, the proposed method is only used for linear network. The similar work is proposed in [21].
Farooq [22] proposed a tree multi-hop uplink communication scheme based on hierarchical clustering to extend the LoRaWAN network's coverage. The proposed scheme uses lightweight gateways as relay nodes instead of using some sensor data nodes to relay data. The method consists of layers formation and lightweight gateways discovery, the clusters formation, and data transmission periods. The root gateway initiates the gateways discovery by broadcasting a gateways discovery message G DIS . Lightweight gateways that can hear the root gateway receive the G DIS , store the root gateway's ID and reply with a gateway reply message G RES . These gateways add the root gateway as their direct parent. The main gateway will add them as its child gateways by using information store in the reply G RES message. Then, the child gateways of the root gateway broadcast again the G DIS after replacing the root gateway ID by theirs. The process repeats until all the network lightweight gateways are discovered. The clusters formation in the proposed approach consists of assigning only one lightweight gateway to each LoRa device. After layers formation and lightweight gateways discovery, each lightweight gateway broadcasts periodically a HELLO message to inform its existence to all LoRa nodes located within its communication range. Each node will join the gateway with the best RSSI value. During data transmission period, each gateway will only forward the data packet of its children. Although the proposed method extend the network's coverage, many lightweight gateways need to be deployed which increases the network cost. Additionally, no information is provided regarding the number of devices each lightweight gateway will manage. The downlink communication is not also taken into account in the proposed solution. Duty Cycle restriction: No duty cycle restriction is considered.   [15] Lee and Ke [16] Zhu et al. [17] Paul. [18] Sergio et al. [19] Duong and Kim. [20] Farroq. [21] Liao et al. [22] Minimized latency Mai and Kim [23] Lopez et al. [24] Barrachina et al. [25] Energy efficiency Communication range Abrardo and Pozzebon [30] Dias and Grilo [28] Energy efficiency Sartori et al. [26] Haubro et al. [27] Communication range Ludell et al. [31] Anedda et al. [32] Kim et al. [33] Dwijaksara et al.
[34] In the proposed approach, no routing table is needed. The protocol uses bus topology and nodes that receive a packet for the first time must immediately re-transmit it. In contrast to conventional link-layer protocols that try to avoid packet collisions, concurrent transmission embraces the synchronized packet collisions that happen when multiple relay nodes re-transmit the packet received at the same time. By removing complicated collision avoidance mechanisms that result in long latency, a packet can be flooded quickly across the network through relay nodes. The nodes are synchronized by the gateway through Time Division Multiple Access (TDMA) protocol by assigning a dedicated timing slot to each node in order to enable her/him to transmit its data. Each node plays the role of initiator or transmitter in its timing slot and becomes a relay node in other slots. To improve the proposed flooding approach, instead of immediate re-transmission as it is the case in conventional concurrent transmission, the authors employed a small timing offset during the re-transmission time, and the results have shown a better receiving performance. In addition to simulations, the authors also performed field tests by deploying nodes in different buildings. Duty Cycle restriction: The duty cycle restriction was considered.
Time Synchronization: The nodes are well synchronized by the gateway through TDMA and save energy during the sleep mode.
Receive windows of nodes: Not specify. Payload: Not specify However, parallel transmissions are prohibited in the proposed approach. Just one node can transmit at a time in the network which completely ignore the benefits of LoRaWAN protocol. The advantages of this method are its simplicity and reliability. Additionally, no knowledge is required about the topology of the network.
Mai and Kim [24] presented a Time Division Multiple Access (TDMA) scheme to minimize latency in LoRa multihop networks. The proposed solution consists of a network tree construction period, the uplink transmission period, and the downlink transmission period. The network tree construction consists of N cycles and each cycle contains four timeslots discussed as follows. The gateway initializes the tree construction by sending an INIT message in the network. Nodes that receive the INIT message from the gateway compete to send a JOIN message to the gateway. The node that wins the competition will send its JOIN message to the gateway and the loser must wait until the next cycle. When the gateway receives the JOIN message from a LoRa node, it adds this node as its child node. The gateway will then assign a timeslot and channel to this LoRa node to communicate with him during data transmission. This VOLUME 4, 2016 assignment is sent to the LoRa node in the form of a CON (confirmation) message. After receiving the CON message, the LoRa node will broadcast an ADV (advertisement) message to inform its neighbor nodes of its cell assignment. Then, it sends an INIT message to its neighbor nodes. The neighbor nodes will also compete to send a JOIN message and the node which wins will send the JOIN message to the LoRa node that previously sent the INIT message and adds him/her as its parent. The process iterates until the network tree construction completion. The authors proposed a packet collision avoidance mechanism based on channel activity detection (CAD) to void collisions as JOIN packets can collide (two nodes can send the JOIN message at the same time using the same LoRa parameters configurations). Methods for time-slot and channel assignment and parent choice are also proposed. During the uplink period, parent nodes aggregate data received from its child nodes and send it to the gateway or its parent node using the time slot and channel that have been assigned to them during the tree construction period. During the downlink period, each node uses the same channel and time slot in reverse order. Although the proposed scheme has shown its feasibility in terms of latency and reliability, energy consumption remains the critical metric as nodes operating on batteries play the role of relay nodes. Duty Cycle restriction: The duty cycle restriction was considered. Time Synchronization: It is ensured through TDMA. Receive windows of nodes: Not specify. Payload: Not specify Barrachina et al. [26] presented a simple Reinforce Learning approach based on epsilon-greedy to enable high reliability and low power consumption in LPWAN networks. In the proposed approach, nodes closer to the gateway act as relay nodes. Duty Cycle restriction: The duty cycle restriction was considered. Time Synchronization: TDMA. Receive windows of nodes: Not specify. Payload: 43 bytes. The proposed learning method achieves low energy consumption but high latency.

B. IPV6-BASED APPROACHES
Sartori et al. [27] proposed a tree routing solution aiming to select the routing path with the minimum airtime. By selecting the routing path that has the lowest ToA, the network lifetime will be extended. The proposed solution is based on the Routing Protocol for Low-power Lossy Network (RPL). RPL is a routing protocol used in Low-power Lossy Networks (LLNs) to find multi-hop routes in order to reach every destination within a LLN. RPL creates a tree called Destination Oriented Directed Acyclic Graph where nodes play one of the following roles: root, parent or leaf. In RPL, the route selection is performed through the Distance Vector protocol where an objective function defines how nodes select parents. To implement RPL for LoRaWAN network, the authors introduced a new Medium Acces Controller protocol called RPL+LoRA MAC (RLMAC). A process for neighbors discovery and SF selection was also proposed. An objective function was proposed to minimize the total time on air. RPL provides routing paths in both upward and downward direction, and downlink communication can be possible. Duty cycle restriction: The duty cycle was imposed to 1%. Time synchronization: There is no time synchronization which will lead to packets collision. Receive windows of nodes: Not specify. Payload: Not specify However, one limitation of the proposal is that LoRa gateway can only listen to one sub-channel at a time.
Haubro et al. [28] demonstrated through Time Slotted Channel Hopping (TSCH) over LoRa physical layer, the possibility to enable an IPv6 network over LoRa. However, the TSCH-over-LoRa protocol introduces high overhead due to the use of 6LoWPAN protocol stack that adds significant overhead in terms of headers and control packets. This limits the already limited bandwidth. Duty cycle restriction: The duty cycle was imposed to 1%. Time synchronization: It is ensured through Enhanced Beacons period. Receive windows of nodes: Not specify. Payload: 100 bytes per RN

C. AD-HOC MULTI-HOP COMMUNICATION APPROACHES
Dias and Grilo [29] presented the protocol specification and detailed description of a prototype proposed for LoRaWAN multi-hop networks. They especially considered only the uplink communication. The proposed prototype is a simplified version of Destination-Sequence Distance Vector (DSDV) which is a proactive distance-vector protocol originally proposed by Perkins and Bhagwat in 1994 [35] for Mobile Ad Hoc Networks. The prototype classifies nodes into leaf nodes (LNs) and relay nodes or routing nodes (RNs). The LNs are energy-constrained nodes whereas the RNs are nonenergy constrained. While LNs do not take part in the routing processes, each RN stores a routing table with the following information: A list of destinations, the metric to reach each destination, the next hop in the path, the sequence number issued by the destination, and a time stamp to detect stale entries. A destination here corresponds to gateways as only uplink communication is considered by the authors. The gateways periodically broadcast beacons in the network. After receiving a beacon from a gateway, each RN updates its routing table and transmits a full dump as soon as possible. RNs that did not receive the beacon, receive the full dump from neighbor RNs, update then their routing tables and transmit also their full dump. The LNs after constructing a LoRaWAN packet, append a routing overhead to the packet and forward it within the multi-hop extension. Once a RN receives the packet, it removes the routing overhead so that the packet  will be received at the application server-side as being sent by the LN. As each RN stores all the possible destinations, the packet will be sent to the destination (gateway) with the smallest number of hops. After receiving the packet, the gateway just forwards it to the LoRaWAN network server. Duty cycle restriction: The duty cycle was imposed to 1%. Time synchronization: The time synchronization is ensured through a beacon packet.
Receive windows of nodes: Not specify. Payload: 20 bytes per LN However, the prototype does not consider the downlink communication which is its main limitation.
Abrardo and Pozzebon [30] reported that the transmission range of LoRa technology in underground communication is limited to a maximum of 200 m. In such a condition, the traditional star-of-star topology of LoRa networks is not feasible. Therefore, they proposed a synchronization linear LoRa multi-hop communication protocol to monitor the ancient underground water distribution systems in Siena, Italy. Every LoRa node in the proposed Linear Sensor Network must only receive and transmit messages of its direct neighbor nodes. The protocol is divided into three phases: a Synch (synchronization) phase to establish the schedule for transmission and reception, a Data period to collect data, and a Sleep period to save energy. Initially, in order to establish the schedule for transmission and reception, the gateway sends a Synch message that is flooded through the linear network. The Synch message includes the elapsed time (ET) which is the number of Synch packets transmitted in the chain and is initialized to zero by the gateway. The direct neighbor of the gateway receives the Synch message, increments the ET by one, forwards the message to the next node, and switches to the low power listening to overhear the re-transmission which will be considered implicitly as an ACK. The process iterates until the Synch message reaches the last node of the linear network. After transmitting the Sych message, switching to low power listening mode, each data source node sleeps for a short period of time, wake-ups and transmits the data packet. The data will be flooded until it reaches the gateway. Duty cycle restriction: The duty cycle was imposed to 1%. Time synchronization: The synchronization among nodes is fulfilled by dividing the time into three periods, namely, Synch, Data and Sleep as it is in other synchronous protocols. Receive windows of nodes: Not specify. Payload: 51 bytes per node However, the use of sensor nodes as relay nodes in underground conditions is not beneficial in terms of energy consumption.
Ludell et al. [31] combined Wireless Mesh Protocol (HWMP) and Ad hoc On-Demand Distance Vector (AODV) and proposed a lightweight routing approach for LoRa. The protocol uses lightweight nano-gateways, that do not fully implement LoRaWAN, to relay data between end devices and the main gateway connected to the network server. The authors justified the use of the nano-gateways by the fact that in remote areas where the internet connection is not available, these nano-gateways will forward the collected data to the main gateway, connected to the internet, through LoRa communication. In the proposed protocol, HWMP is used to forward packet through the nano-gateways if a route is already established between the end devices and the network server; otherwise, through existing AODV routing, a path with minimum number of hop is constructed. The proposed protocol is transparent to both end devices and network server. Duty cycle restriction: The duty cycle was imposed to 1%.  In the proposed e2McH, the routes are constructed based on three metrics: The energy consumption, the residual battery life, and the traffic rate. The main principle of the proposed solution is to find among the neighbors of each LoRa node, the one with the lowest distance to the gateway. For each LoRa node LN, the algorithm computes the distance d i between this node and the LoRa gateway. Then, a set of nodes are determined as the neighbors of this LN based on euclidean distance. The algorithm computes the distance d j between each neighbor of LN and the gateway. The neighbor with the lowest distance is chosen as the best neighbor and will relay data of this LN during data communication.
The proposed routing solution is very simple and simulation results have shown an enhancement of 15% in energy consumption compared to the single-hop LoRaWAN. However, the problem with this solution is that some nodes will still be chosen as the best neighbors. Therefore, they will continuously play the role of relay nodes and will quickly deplete their energy.
Duty cycle restriction: The duty cycle was not respected in the simulations. Time synchronization: No synchronization protocol was used.
Receive windows of nodes: Class C devices. Payload: Not specify The downlink communication was not taken into account by the authors. The solution is not efficient in terms of energy consumption as nodes stay in listen mode all the time.
Kim et al. [33] designed a routing approach to enable multi-hop in LoRaWAN network by considering some intermediate gateways (called hopping gateways) as relay devices. The data collected by LoRa end-devices are sent to the hopping gateways. These gateways can perform one or multihops to reach their parent gateways. The data packet traverse the multi-hop network until it reaches the main gateway connected to the network server. Duty cycle restriction: The duty cycle was not respected as no implementation is provided by authors. Time synchronization: It is ensured through Global Positioning System (GPS) Receive windows of nodes: Not specify. Payload: Not specify. Using multiple intermediate gateways to relay data will increase considerably the network cost.
Dwijaksara et al. [34] proposed a multi-hop Gatewayto-Gateway (G2G) communication protocol which includes both routing protocol and channel access scheme for Lo-RaWAN networks. Initially, to discover a route from an intermediate gateway to the main gateway which is connected directly to the LoRaWAN network server, the intermediate gateway initiates a route request message. The route request message is broadcasted by the intermediate gateway. Then, the message is flooded in the network so that, it can reach the main gateway. Therefore, each gateway in the network maintains a list of its direct neighbor gateways. When the main gateway receives a route request message, it reply by sending a route reply message to the original sender gateway. The route reply message is transmitted to the originator by using the path discover in reverse form and during the route reply message forwarding, each intermediate gateway stores the information of the discovered route. The end devices work as in the case of the single-hop network. Duty cycle restriction: The duty cycle was respected during the implementations. Lopez et al. [25] proposed an ad-hoc cross-layer multihop protocol for LoRa to provide low transmission power consumption and extend the network coverage by using sensor nodes as relay devices. On one hand, the gateway after installation is either in received mode (uplink messages) or sending mode (periodically broadcasting a beacon message or sending ACK message for uplink messages received).
It uses the uplink message received to update the network topology, specifically discovering its direct neighbors. On the other hand, the end devices after deployment turn on in receive mode to receive at least one data packet and join the network. After joining, the nodes announce periodically their information through the Beacon message controlled by a timeout for network topology construction. Once the network is fully constructed, every node first opens a window to receive data from its child. If the data is received, the node puts it into a queue and sends an ACK message to its child. Otherwise, if the timeout of the window expires, the node goes into sleep mode to save energy and schedules a wakeup time. Duty cycle restriction: The proposed ad-hoc cross-layer protocol respected the duty cycle restriction of LoRaWAN. Time synchronization: The Beacon message is used for time synchronization.
Receive windows of nodes: Not specify. Payload: 100 bytes per RN.
We summarize in TABLE 5, the four requirements that routing approaches must take into account and provide in TABLE 6, an overall comparison of routing strategies studied in this paper by considering their category, PDR obtained during protocol validation, topology considered and the test type or validation type.

V. LORAWAN MULTI-HOP SDN-BASED SOLUTION FOR SMART WATER GRID
Smart water grid (SWG) is an emerging infrastructure that integrates Information and Communication Technologies into traditional water distribution systems. The smart metering devices and sensor nodes for leakages and burst detection are deployed into the water grid for data collection and reporting. These smart devices are often located in harsh environments such as underground inside the pipelines, cold, under extreme heat where the radio signal penetration is very difficult. The use of conventional cellular networks or existing mature short-range data networking solutions is not suitable due to the high energy consumption of cellular networks and the limited communication range of short-range communication technologies. Due to their low power consumption, long communication range, and excellent radio penetration [8], Low power wide area networks (LPWANs) are suitable communication technologies for SWG applications. Many LPWAN solutions such as LoRaWAN, SigFox, NB-IoT, etc. exist on the market but among them, LoRaWAN is the most mature and used in both research and industrial communities. However, as mentioned earlier, it adopts a star communication topology where nodes communicate directly with one or more gateways. As reported by [30], LoRaWAN achieves only 500 m underground due to obstacles. The star topology is therefore inappropriate in the context of leakages detection which is one important motivation towards SWG. In leakage detection scenarios, nodes are deployed underground inside the pipelines. In such conditions, the only way to power them is the use of non-replaceable and non-rechargeable batteries  Bor et al. [14] CCT-based P 80% Flooding Ebi et al. [15] CCT-based P 99% Flooding Lee and Ke [16] CCT-based P 99.9% Tree Zhu et al. [17] CCT-based P 85% Tree Paul [18] CCT-based Simulation(S) NS Tree Duong and Kim [20] CCT-based P 80% Flooding Farooq [22] CCT-based P NS Tree Liao et al. [23] CCT-based P NS Flooding Mai and Kim [24] CCT-based P 90% Flooding Barrachina et al. [26] CCT-based P 95% Tree Sartori et al. [27] IPV6-based P 96% Tree Haubro et al. [28] IPV6-based P 90% Tree Dias and Grilo [29] ad-hoc-based P 98% Flooding Abrardo and Pozzebon [30] ad-hoc-based P 95% Tree Ludell et al. [31] ad-hoc-based Proof-ofconcept NS Flooding Anedda et al. [32] ad-hoc-based S NS Tree Kim et al. [33] ad-hoc-based Theorical analysis 90% Flooding Dwijaksara et al. [34] ad-hoc-based S NS Flooding Lopez et al. [25] ad-hoc-based S 86% Tree [8]. Therefore, SWG can not deal with most of routing protocols reviewed previously as sensor data nodes are involved in the routing process. Small leakages detection nodes installed underground inside the pipelines can not perform all the routing tasks and still be alive for a long period of time.
The use of energy harvesting techniques is infeasible in this situation due to the absence of energy harvesting sources such as sun. We propose in this paper a LoRaWAN multi-hop communication protocol where we consider some specific relay nodes (RNs) to relay data between the SWG enddevices and the main gateway connected to the LoRaWAN network server. We assume that these RNs are deployed optimally in strategic positions. Therefore, SWG devices need to discover them. We propose an algorithm for RNs discovery. More specifically, one motivation of employing IoT concept in the water distribution systems is to shut off automatically the smart valve in the case of leak presence to decrease both economic and resources losses. A sensor or a set of sensors will collaborate between them and in the case of a leak, a signal can be sent to shut off the valve without involving human or control center intervention which is a kind of peer-to-peer communication. We called it P2P communication in this paper because the communication does not involve the presence of the main gateway connected to the network server. To be specific, currently, in LoRaWAN networks, according to our best knowledge, this kind of communication involves the participation of the gateway and the network server which results in high latency and additional energy consumption. To enable P2P communication without involving the gateway, we introduce in our proposal the SDN controller functionalities for flow tables setting up. In the case of a leak, by finding the highest priority match at each RN, a signal will be sent easily to the corresponding smart valve for shutting off. For simple uplink data coming from the monitoring environment, we introduce a fog server where the LoRaWAN network server is located to process the incoming data after having been received. The processing of data at the fog server will improve the network latency and at the same time protect the privacy of data in contrast to traditional cloud-based solutions where all SWG devices measurements are transmitted to cloud service for processing and permanent storage. In what follows, we provide an overview of the SDN concept follow by some changes to make on LoRaWAN devices in order to enable this LoRaWAN-SDN integration.

A. OVERVIEW OF SOFTWARE-DEFINED NETWORKING (SDN)
SDN is a networking paradigm that decouples network traffic as control plane and data plane. In SDN, the task of forwarding devices, such as routers and switches, is to just forward packet according to policies (rules) located in each device. These policies or rules are created by an SDN controller and are sent to forwarding devices. The SDN controller is the control logic dictating the entire network behavior. An illustrative architecture of SDN is shown in FIGURE3. As shows in this figure, SDN has a three layers architecture. From bottom to top, the architecture consists of infrastructure layer (or data plane) where all forwarding devices are located, the control layer where one or more SDN controller(s) are deployed, and the application layer. New functionalities such as programmability, security, and assisting network configuration are added by the application layer. Compared to traditional distributed approaches, SDN networking paradigm offers many benefits. First, with Secondly, SDN provides a centralized controller to the network. This controller has global knowledge of the whole network and is able to control the network infrastructure in a vendor-independent manner. The forwarding devices simply accept rules from the controller without understanding, and this results in direct control, programmable, orchestrate, and manage network resources. Therefore, a lot of workforce and resources are saved. Additionally, with a SDN controller, routing decisions can be taken easily and flexibly. SDN is also used to maintain session continuity and connectivity and to ensure mobility management [36]. The deployment of SDN requires a standardized communication protocol between the Control Plane and Data Plane (South-bound Interface). The most used South-bound Interface is OpenFlow [37] shows in FIGURE. 4. Other Southbound Interfaces such as ForCES [38] and SoftRouter [39] also decouple as well Control Plane from Data Plane. Open-Flow installs in switches, flow table entries via OpenFlow controller and enables these switches to forward packets according to entries rules. The SDN controller is responsible for decision making regarding adding, deleting, and modifying the flow rules through OpenFlow protocol. Through the OpenFlow protocol, the SDN controller controls and manages all forwarding devices located at the infrastructure layer (Data Plane). While the SDN controller interacts with the Data Plane via OpenFlow protocol, it also communicates with the application layer located at the upper layer via VOLUME 4, 2016 northbound interfaces which makes the management of the network very easy because applications operating on the application layer do not worry about the details of the data plane.

B. CONSIDERATIONS OF INTEGRATING SDN IN LORAWAN MULTI-HOP NETWORKS
It was remarked that LoRaWAN outperforms NB-IoT and SigFox [41] in terms of SDN integration. Traditionally, the following three parts are used in a LoRaWAN communication: • End-nodes -Gateways: the communication in this part is achieved using LoRa modulation or Frequency Shift Keying (FSK). • Gateways -Network server: the gateways use IP standard connections to send data to the network server. • Network server -Application servers: This communication is achieved through IP standard connections.
By considering the OpenFlow protocol, SDN based on this protocol can be deployed in any network by using traditional TCP/IP stack [42]. When integrating SDN in the LoRaWAN protocol, several considerations need to be taken into account: • OpenFlow support: The network devices especially the routing devices such as LoRa gateways and relay nodes (RNs) must support OpenFlow protocol. • Network server modifications: In LoRaWAN-SDN integration, the most suitable way to incorporate the SDN controller functionalities in the network is to add to the LoRaWAN network server the features of the SDN controller. This assumption has been already validated in [41]. As most applications will require the cooperation of SDN controller and LoRaWAN network server, integrating the functionalities of SDN controller and those of LoRaWAN network server in the same place will increase the performance of the system. • LoRaWAN gateway application modifications: Each LoRa gateway or RN must implement the OpenFlow software switch.
• Modification of gateway message processing: Typically, in the LoRaWAN networks, gateways encapsulate data packets received into IP packets and forward them to IP network servers. In the case of LoRaWAN-SDN integration, as each gateway will implement OpenFlow software switch, the encapsulated message must be sent through this software switch, and depending on the SDN policies, the message can be processed or discarded by the network server.

C. ARCHITECTURE OF THE PROPOSED SOLUTION
As shows in FIGURE. 5, our proposed solution consists of a data plane layer where the forwarding devices such as the main gateway and RNs are located. The SWG end devices are also located in this layer. The control plane layer is at the middle of the architecture where the LoRaWAN network server plays the role of SDN controller. At the same location, we introduce a fog server to process with low latency the incoming data. The LoRaWAN network server uses OpenFlow protocol to communicate with the main gateway which is connected to RNs that relay data from SWG devices. The Lo-RaWAN network server as an SDN controller will install via OpenFlow protocol, flow table entries on the main gateway and RNs deployed in data plane layer in order to enable them to forward packets according to entries rules. The LoRaWAN network server is responsible for decision-making regarding adding, deleting, and modifying the flow rules through Open-Flow protocol. It will manage easily through the OpenFlow protocol, all forwarding devices located at the data Plane layer. LoRaWAN network server also communicates with the smart water management servers located at the upper layer via northbound interfaces which makes the management of the network very easy.

D. PROTOCOL OPERATION
We detail in this part the workflow of our proposed protocol.

1) Relay Nodes Discovery and Layers Formation
Once RNs are optimally deployed, a mechanism is required to form different layers and enable SWG devices to discover the presence of these RNs. We clarify the following assumptions: (1) Each RN is a simple low cost node equipped with only LoRa module to provide LoRa communication, The addressing scheme standardized in LoRaWAN is used in this paper, that is, the main gateway and RNs have 3-bytes network identifier (ID) each one, and each SWG device in the network is assigned to 4-bytes address. In the LoRaWAN frame header, there is a reserved MessageType called proprietary reserved for future use. We use this field to encode our messages, (3) RNs do not need internet connection, only the main gateway need the Internet connection to communicate with the LoRaWAN network server. Our protocol is a hierarchical clustering-based approach and therefore starts with RNs discovery and layers formation, initiated by the SDN controller which is the LoRaWAN network server. For the sake of simplicity, we offload the SDN controller task to the main gateway. Initially, the SDN controller (main gateway) prepares a beacon message for RNs discovery and layers formation. The format of this message is shown in FIGURE. 6 (a). It contains the message type (M_type) field, 1 byte, to indicate the type of the message which is set to 0x00, the transmitting device ID TD_id field, 3 bytes, which contains the ID of the main gateway, the hop count (Nb_hop), 1 byte, initialize to zero, the layer ID field (L_id ), 1 byte, which is also initialize to zero and the passed time (Pass_time), 1 byte, initialize to one. Then, the message is broadcasted to discover the direct neighbors of the main gateway which are the RNs of layer 0 (L0 in FIGURE 5). The RNs that hear the main gateway receive the beacon message and prepare two messages, one as a response to the main gateway and another to discover the RNs at layer 1. The response message (FIGURE. 6(b)) contains: The message type field set to 0x01, a 3-bytes transmitting RN ID field TD_id, and a 3-bytes receiver RN field which contains the ID of the main gateway. In the beacon packet, the RNs of layer zero increment the Pass_time by one, the L_id by one, the Nb_hop by one, replace the TD_id by their IDs and broadcast to discover the RNs at layer 1. The main gateway will add the RNs of layer zero as its children and the later will add the main gateway as their parent. Upon receiving the beacon message, the RNs at layer 1 will perform the same as the layer zero RNs did, and the process iterates until the end of RNs discovery and layers formation. At the end of RNs discovery and layers formation, each RN will have a list of parent nodes that contains a set of IDs of RNs towards the main gateway and a list containing its children' IDs. The RNs discovery and layers formation starting at the main gateway is depicted in Algorithm 1. After RNs discovery and layers formation, each SWG device must be assigned to either a RN of its own layer, its bottom, or its upper layer for data transmission. For this purpose, VOLUME 4, 2016

RNs
Smart water grid node Smart water management servers Fog Layer  If at least one of the above conditions is fulfilled, the SWG device can join a RN network by sending a join reply message. The reply message (FIGURE. 6(d)) called JOIN_req contains a 1-byte M_type sets to 0x03, a 4-bytes SrcD_addr (device address) and a 3-bytes RD_id. The RN may confirm with a join confirmed message (FIGURE. 6(e)) called CON containing a 1-byte M_type sets to 0x04, a 3bytes TD_id field, a 4-bytes DeD_addr field and a 1-byte remaining time (T_remain) to go to data operation period. Equation 1 computes the time remain to go to data collection period.
T _remain = T _Init−(P ass_time * T _slot+T oA_CON Where T_Init is the total time for RNs discovery, layers formation, and network joining set enough to complete these three tasks. T_slot denotes the time slot which is long enough to be greater than the ToA of both beacon message and response message of network discovery and layers formation. ToA_CON is the ToA of CON message. The above equation enables the node to know when its corresponding RN is active to receive data. As we mentioned earlier, the JOIN message is not only used by the end devices but also enables each RN to discover its direct neighbors. Therefore, after the joining process, each RN will hold the data structure presented in Data Struct 1.  TABLE 8 to choose suitable SF by considering the power received from the RN that the device wants to join. Our protocol operates in a cycle manner in order to keep synchronization between end devices and RNs. Therefore, RNs can ask a device at any time to increase or decrease its SF to avoid collision in the network and save also energy (similar to ADR algorithm of the standard LoRaWAN).

3) Flow Tables Set up
For networks based on SDN, in order to decouple control plane from data plane, the SDN controller set ups flow tables at each forwarding devices. This task is offloaded to the main gateway in this paper. To perform this task, the main gateway need to know the neighbors of each RN. Therefore, after network joining process, each RN will have a list of all its neighbors as he/she will receive a JOIN message from them. Each RN will prepare a message for the main gateway. We called this message Net_construct (FIGURE. 6(f)). It will help the SDN controller to construct the network topology. The message contains a 1-byte M_type field set to 0x04, a 3bytes TD_id field which contains the ID of the sender RN, a 3-bytes NeD_id field which contains the ID of the next RN towards the main gateway, a 3-bytes RD_id field which contains the ID of the main gateway and a variable length of IDs which are the IDs of the RN' neighbors ( Neigh-bors_RNs_id). Each RN will prepare, replace each field with its corresponding value and send it using paths discover during RNs discovery and layers formation. After one or more hops, the message will reach the main gateway. The main gateway will have all information about the neighbor of each RN and can then set up flow tables. To set up flow tables for each RN, we define another control message called Flow_table (FIGURE. 6(g)). The message contains the following fields: a 1-byte M_type field set to 0x05, a 1-byte control byte (Crt_byte), a 3-bytes RD_id field which contains the receiver device ID, a 3bytes TD_id field, a 3-bytes next RN ID (NeD_id) towards the receiver and a list of tuples which are the destinations reachable and next RN IDs towards the destinations. Each tuple has a size of 6 bytes. If all tuples can not fit in a single Flow_table packet, the main gateway will set the most important bit in Crt_byte to indicate that there are some pending entries. In each flow table the main gateway sets the following information: Destination (RD_id, which is the ID of the destination RN) and the next RN ID towards the destination (NeD_id). It is worth mentioning that the number of tuples in the list of destinations reachable and next RN IDs is equal to one less the number of RNs including the main gateway. The main gateway will set up the flow table for each RN and send it. Each Flow_table message, considered as the first downlink message from the main gateway to the forwarding devices, will be sent to the corresponding RNs using paths already discover during RNs discovery and layers formation. Therefore, as control information flow using the paths discover previously during RNs discovery and layers formation, and data will be forwarded using the flow tables set by the main gateway, this exactly separates the control plane from the data plane.

4) Data Transmission
After all the above processes are completed, the SWG devices can generate periodically or event-based (presence of a leak) data and transmit it. Recall that each device must communicate with one RN. We define a last message type called PACKET (FIGURE. 6(h)) which contains the following fields: 1-byte M_type field set to 0x06 , a 3-bytes TD_id field, a 4-bytes source device address SrcD_addr field, a 3-bytes RD_id 3 bytes field, a 4-bytes destination device address DeD_addr, a 3-bytes NeD_id field, and a 1-byte Crl_byte field. We target a P2P communication but the uplink and downlink communication are discussed in this paper.
• Uplink: Whenever a SWG device (sensor for leakage detection or smart water meter) has data to transmit to the network server, it prepares the PACKET message with: PACKET.M_type = 0x06; PACKET.TD_id = ID of the device's RN; PACKET.SrcD_addr = address of a SWG device; PACKET.RD_id = ID of the MG; PACKET.DeD_addr = address of the network server; PACKET.NeD_id = ID of the device's RN; PACKET.Crt_byte = 0x80 if the message will be processed by the RNs, 0x00 otherwise. Then, the device sends the message to its RN. As the RN stores all destinations and the next hop towards the destinations, by using RD_id, it will find the destination and just forward the packet to the next hop towards the destination. The message reaches the main gateway after one or several hops. The main gateway receives the message and examines the RD_id, it matches. Then, the message will be sent to the network server. • Downlink: Whenever the network server has a message to a specific end device, it prepares the message and send it to the main gateway. The main gateway upon receiving the message, evaluates the packet and finds the highest priority match by using its flow table. The message is simply forward to the corresponding RN. Note that the Crt_byte field contains 0x80 as all RNs on the path need to process the incoming packet. An ordinary LoRa end node process a data if the Crt_byte field is equal to 0x00. Therefore, upon receiving the message, the destination RN changes the Crt_byte field value to 0x00 and sends it to the corresponding device. • P2P communication: The goal of this routing approach is to enable a P2P communication between leakage detection nodes and the smart valve in the case of a leak without involving neither the main gateway nor the network server. As IoT enables the communication between actuators and sensor data nodes, this solution will help water utilities to save resources. Therefore, when a leakage detection node has data to send to a water valve, it prepares the PACKET message with its corresponding values and transmits it to its RN. The RN checks RD_id field, if it matches its ID, it simply changes Crt_byte value to 0x00 and transmits it to the smart valve to be shut off. If it doesn't match, the RN searches in its flow table to find the highest priority match. The destination will be certainly found, the RN will extract the NeD_id towards the destination in its flow table, insert it in the appropriate field, and forward the packet. The process will be iterated until the shutting off of the valve. By forwarding data using the flow tables set up by the main gateway and send to the RNs, the control plane is well separated from the data plane.

5) Our Protocol Requirements
In order to enable the protocol to operate well, time synchronization is required between RNs and SWG devices. Time synchronization enables RNs to sleep and wake up so that they can save energy. Our devices are working in class A, after a transmission, they open two receive windows respectively at 1 s, and 2 s for a downlink. The devices transmit randomly on one of the 868.1, 868.3, 868.5 MHz of EU regulation channels respecting the duty cycle of 1%. They change randomly the transmission channel after each transmission. To enable parallel transmissions, the RNs listen to these three channels during the data operation period. The main gateway operates as a normal LoRaWAN gateway and must be in listening mode once installed. However, the RNs are running on batteries as LoRa devices and need to sleep sometimes to save energy. The most important issue in LoRaWAN multi-hop networks is how to manage the duty cycle of the network to avoid packet losses. The RNs must wake up at an optimal period to receive data from the nodes. The Pass_time includes in the beacon message enables sensor nodes to know when their corresponding RNs are ready to receive data from them. By using Equation 1, each node estimates when the RN can receive data. During the data operation period, all RNs are active so that data can be routed easily to the destination.
To ensure that every node data is sent to the network server, in the star-of-star LoRaWAN networks, when a device sends data, this message is received by all gateways located within its communication range and these redundant information will be filtered by the network server. However, in both our solution and routing approaches survey in this paper, this advantage of LoRaWAN is not possible. Therefore, to be aware that data is successfully received by the receiver, data are sent in this paper as confirmed messages. In the confirmed messages, RNs include the next cycle start, set by the main gateway to enable synchronization. By doing so, all cycles are synchronized and both RNs and SWG devices sleep and wake up to save energy.

E. PROTOCOL VALIDATION
To validate our proposed protocol, we used LoRaSim, a discrete event simulator implemented by Bor et al. [14]. LoRaSim allows the deployment of nodes around one or more gateways. The simulator does not support the multihop communication. Therefore, we provided some additional implementations in order to evaluate our protocol. LoRaSim uses log-distance path loss model which is one of its advantage because log-distance path loss is widely used to model wireless channels. The simulator enables us to evaluate the packet extraction rate and the total energy consumption of a LoRaWAN network.

1) Simulation Model of Our Protocol in LoRaSim
As mentioned earlier, LoRaSim adopts the star topology of the traditional LoRaWAN network. It does't include multihop features. Therefore, efforts have been made to simulate mult-hop behavior in this simulator. LoRaSim has three important features: node, characterized by TP, CF, SF, BW, CR, B, where B is the packet payload, gateway and path loss based on log-distance. LoRaSim does not implement RN in its current version. LoRaSim supposes that all nodes are deployed in a layer. As we deal in this paper with multiple layers, minor changes are required. We first consider that the gateway model implemented in LoRaSim can act as RN in our simulations. Then, we divided the single circle of LoRaSim into multiple circles. Each circle represents a layer. We deployed at each circle 3 gateways to represent RNs. By doing so, the network is built with RNs at different layers. We applied our RNs discovery and layers formation algorithm to discover the RNs.
For SDN point of view, our current implementation considers the gateway of the first layer (L0) as the SDN controller or main gateway. He/She is responsible for setting up flow tables for RNs. More specifically, flow tables are just simple set of rules: Destination (RD_id, which is the ID of the destination RN) and the next RN ID towards the destination (NeD_id).

2) Simulation Parameters and Results
The gateway is able to demodulate, for a given CF, multiple signals with different SFs and BW combinations.
The performance of our proposed protocol is compared with the standard single hop LoRa network which uses star topology. In our simulations, we used, for both our solution and single hop network, a fixed payload size of 32 byte. This payload is chosen according to the state-of-the-art, especially [2] which stated that, in a smart water grid application, a payload of 32 byte is enough to carry the water consumption data. In the single hop network, the simulation parameters are: TP = 14 dBm which the default value, 868. The results of our simulations are presented in FIGURE. 7 and 8. We first evaluated our solution in terms of packet error rate (PER). LoRaSim provides a model to evaluate this metric.

P ER =
packets not successf ully received T otal number of packets send The results of P ER with varying number of nodes are shown in FIGURE.7. It is clearly showed that our solution gives the best outputs when comparing with the standard single-hop network. The higher P ER of the standard single hop is mainly due to collisions. As the single hop network uses in our simulations random SFs, collisions are frequent. The nodes in our proposed solution use optimal SFs, tuned by the RNs during data operation period. Therefore, the ToA is low which decreases collisions and energy consumption. Another important conclusion drawn is that LoRaWAN networks are sensitive in terms of nodes as the increase in the number of nodes increases the P ER in both our solution and the single-hop network. This result reveals an idea on the scalability of LoRa multi-hop networks. This situation has been already confirmed by the routing approaches discussed in this paper. Until now, the maximum number of nodes supported by the current multi-hop implementations using hardware is 36 according to [17]. 8 evaluates our proposal in terms of total network energy consumption as the energy consumption model is available in LoRaSim. FIGURE. 8 shows that the increase in the number of nodes increases the network energy consumption. For the single-hop network, the higher energy consumption is due to the use of the higher SFs. The higher the SF, the higher the ToA, and therefore, the higher the energy consumption. Our proposal outperforms the singlehop in terms of energy consumption due to the use of suitable SFs and easy data forwarding through SDN flow tables.

VI. FINDINGS
As presented in TABLE 1, TABLE 2, TABLE 3, and TA-BLE 4, the existing approaches proposed to enable multi-hop communications in LoRaWAN have shown prospective applications and their performance were verified with different experimental settings.
The above comparison tables clearly showed that most existing approaches are based on clustering and concurrent transmissions. Also, most papers rely on tree topology. Additionally, for validation type (column 4 in TABLE 1, line  4 in TABLE 3, and line 4 in TABLE 4), authors opted for hardware to validate their proposals. Therefore, using real implementations indicates that the technology is mature and readily available. It also implies that researchers are highly motivated and are engaged to enhance the performance of LoRaWAN technology.
The second point that the above tables suggest is the number of nodes and hops in the network. In TABLE 1 at column  5, line 5 in TABLE 3, and line 5 in TABLE 4, the maximum number of nodes support by real implementations is 36 in the proposal of [17]. The same authors achieved the maximum number of hop to 24. These metrics provide an idea on the scalability of LoRaWAN multi-hop networks. Obviously, this is not sufficient in large scale IoT applications.
Also, our survey results have revealed that the final data send to the main gateway connected to the network server is data aggregated by RNs. In most cases according to our survey, each sensor node transmits only a payload with a size equal to 10.2 bytes on average which is very low for some IoT scenarios. Additionally, as most researchers have validated their routing approaches through real implementations, the duty cycle restriction was imposed according to the region regulation. Our survey has also revealed that the received windows of devices are not mentioned in most proposals. Moreover, Synch, Data and Sleep periods are used for time synchronization between RNs and end-devices.

VII. CHALLENGES, ISSUES AND RESEARCH DIRECTIONS IN LORAWAN MULTI-HOP NETWORKS
Although routing approaches are available to enable multihop in LoRaWAN networks, some challenges and issues still need to address. In this section, we discuss some challenges and issues and provide a range of research directions that researchers can follow.

A. ENERGY CONSUMPTION
As the end-devices in IoT applications are powered by batteries whose recharging or replenishment is almost impossible, it becomes crucial to consider the energy consumption metric during the design and the implementation of any routing communication protocol. In the above discussed routing approaches proposed for LoRaWAN multi-hops networks, some nodes are used to relay data from other devices in addition to their own data. These relay nodes are supposed to stay in operation mode all the time. The lifetime of these nodes will be reduced quickly and therefore decrease the entire network lifetime.
In the future, parent rotation scheme can be adopted in order to spread energy use via different devices. In addition, energy saving schemes need to be implemented. For clustering approaches, Low Energy Adaptive Clustering Hierarchy algorithm can be exploited to balance energy consumption between nodes in the same cluster [43].

B. SECURITY AND PRIVACY
Security and privacy are not yet considered in all the routing approaches proposed until now. A fake gateway can listen to information transmitted by the devices and therefore takes advantage of the entire network topology. In this case, user private information will be discovered. This malicious gateway can send fake information to the network server and therefore disturb the network communication. Blockchain technology [44] can bring some solutions to security and privacy problems but an in-depth investigation is required. 22 VOLUME 4, 2016 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/ACCESS.2021.3135080, IEEE Access

C. SCALABILITY
As we discussed in the findings section, network scalability is not yet considered in existing routing approaches. This metric is very important in IoT applications that require thousands of connected devices. As LoRaWAN was originally proposed for IoT use cases, innovative approaches are required to improve the scalability in LoRaWAN multi-hop networks.

D. EXPLOITING LORAWAN FEATURES
Most of the routing approaches proposed to enable multihops in LoRaWAN do not exploit fully the advantages of LoRaWAN technology. For example, in the work proposed by Sartori et al. [27], the LoRa gateway can only listen to one sub-channel at a time while in the LoRaWAN specification, the gateway can demodulate data packets from different subchannels simultaneously, giving the possibility to LoRaWAN devices to transmit messages at any time, on whatever subchannel. Until now, few papers discussed whether devices are working in class A, B, or C. The ADR algorithm of the LoRaWAN network is not yet considered. In the future, all advantages provided by the LoRaWAN specification need to be considered. Most papers use fixed LoRaWAN parameters configuration which increases collisions. Sophisticated approaches are needed to consider as many LoRa settings as possible at a time. The downlink communication is not considered in many papers discussed in this work. One viable solution for downlink communication is to group multiple acknowledgments in a single short slot because in LPWAN solutions, in general, the downlink communications are rare. This will better control the duty cycle resources.
The current routing solutions do not consider the roaming mechanism where devices can move interoperably between multiple networks.

VIII. CONCLUSION
The paper has provide an in-depth investigation of routing approaches proposed in the literature to enable multi-hop communications in LoRaWAN networks. We have categorized these routing strategies into three groups such as clustering and concurrent transmissions-based approaches, Pv6based approaches, and Ad-Hoc multi-hop communication approaches. For each group, we discussed recent routing approaches proposed in the literature and provided a useful comparison between these approaches. Based on this comparison, it has been remarked that most researchers validated their proposals through real-world implementation and scalability will be an important issue in LoRaWAN multi-hop networks as the number of nodes and hops reported are low.
We considered a SWG as a use case and introduced the SDN controller functionalities at the LoRaWAN network server to enable P2P communications specifically in the case of a leak. Our proposed method outperforms the standard single hop network in terms of packet error rate and total energy consumption.
Additionally, we provided a range of open issues to address and suggested some research directions.
In the future, our proposed solution requires some improvements. The number of nodes each RN is able to manage is not evaluated and will be therefore considered. As most routing approaches opted for real implementation, a test-bed will be performed in order to show the feasibility of our approach.

IX. ACKNOWLEDGEMENTS
This work co-funded by FEDER -PT2020 partnership agreement under the project UID/EEA/50008/2019