Incha Djibrilla
email: djibrilla.adamou@u-psud.fr

Alexandre Adamou

Véronique Mouradian

Vèque

A Bio-Inspired Deployment Method for Data Collection Networks in Wide White Areas

Wide white areas are defined as large regions with very little to no infrastructure. For example, deserts and large forest areas fall in this category. Many strategic phenomena and activities take place in these areas (e.g. mining, environmental monitoring) which necessitate data collection and analysis. In this context, we propose a network deployment scheme which aims at efficiently linking sparse points of interest in a very wide white area. The goal of the method is to minimize the cost of the deployment while providing a fault tolerant network. The proposed method is based on an algorithm which mimics the evolution of a type of mold called physarum. Our deployment problem is close to a Minimum Steiner Tree (MST) problem known to be NP-hard, we thus compare our results to a heuristic of MST.

I. INTRODUCTION

The lack of telecommunication infrastructures in sparsely populated regions results in large unconnected zones called white areas. Whites areas are often wide regions with harsh climate, difficult access and little to no communication infrastructure. However, in these areas, strategic human activities are being carried out. For instance, we can cite sandstorm monitoring, bushfire alert, mining area monitoring, highway and pipeline monitoring. All these applications have in common the need for data collection and analysis.

In this work, we are interested in the deployment of data collection networks, such as Wireless Sensor Networks (WSN) [START_REF] Akyildiz | A survey on sensor networks[END_REF] and Low Power WAN [START_REF] Augustin | A study of lora: Long range & low power networks for the internet of things[END_REF] in wide white areas. The goal is to link points or areas of interest to a data collection center. We aim at efficiently deploying sensor and relay nodes such that all areas of interest are covered, the network is connected and properly dimensioned to handle the data traffic.

As in [START_REF] Misra | Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements[END_REF], we consider a set of potential relay nodes distributed on the map of the considered region. The relays can be randomly placed on the map [START_REF] Younis | Strategies and techniques for node placement in wireless sensor networks: A survey[END_REF], [START_REF] Liding | Modeling wireless sensor networks using random graph theory[END_REF] or form a grid [START_REF] Zhu | Relay node placement algorithm based on grid in wireless sensor network[END_REF]. Our goal is to chose a subset of relays to connect the areas of interest with the data collection center. These chosen relays are then to be deployed on the ground to form the network. We thus aim at minimizing the number of used relays and links. This problem is equivalent to finding the Minimum Steiner Tree (MST) covering all the points of interest and using a subset of the relays [START_REF] Misra | Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements[END_REF]. The MST problem is proven to be NP-hard [START_REF] Suomela | Computational complexity of relay placement in sensor networks[END_REF], [START_REF] Vob | Steiner's problem in graphs: heuristic methods[END_REF]. It is thus not applicable to scenarios with a large number of potential relay nodes. Moreover, it provides no fault tolerance due to its minimal property: any node or link failure results in a disconnected network. This aspect is problematic because WSNs and LPWANs are known to be error-prone [START_REF] Akyildiz | A survey on sensor networks[END_REF]. Moreover, fault-tolerance is an essential characteristic in harsh environments such as wide white areas where network maintenance is either very difficult or impossible.

In this paper, we study the application of a heuristic to deploy a network in wide white areas by selecting nodes among a potential relay set. This heuristic mimics the behavior of physarum mold [START_REF] Tero | A mathematical model for adaptive transport network in path finding by true slime mold[END_REF], [START_REF] Nakagaki | Smart network solutions in an amoeboid organism[END_REF]. As detailed in section III, this mold is able to construct a material efficient, yet resilient, network linking food sources.

The main contributions of this work are:

• the adaptation of the physarum algorithm [START_REF] Tero | A mathematical model for adaptive transport network in path finding by true slime mold[END_REF] to data collection network deployment; • the application of the algorithm to wide white area scenarios; • the tuning of the algorithm to obtain a good trade off between deployment cost and fault-tolerance. The remainder of the paper is organized as follows. Section II gives a survey of literature. Section III introduces the physarum algorithm, and presents how to adapt it to network deployment. In Section IV, we present the algorithm evaluation setup and results. Finally, conclusions and discussions are provided in Section V.

II. RELATED WORK

In this section we review data collection network deployment schemes of the literature. They fall into two main categories: random and deterministic deployment methods.

Many random deployment schemes have been proposed in the literature. In [START_REF] Younis | Strategies and techniques for node placement in wireless sensor networks: A survey[END_REF], a survey is provided. Most of the presented schemes aim at covering completely and reliably a given area [START_REF] Ishizuka | Performance study of node placement in sensor networks[END_REF]. Different node probability distributions are studied, they are non-homogeneous point processes in most cases [START_REF] Younis | Strategies and techniques for node placement in wireless sensor networks: A survey[END_REF], [START_REF] Hsu | Optimized random deployment of energy harvesting sensors for field reconstruction in analog and digital forwarding systems[END_REF]. In [START_REF] Hsu | Optimized random deployment of energy harvesting sensors for field reconstruction in analog and digital forwarding systems[END_REF] a random deployment scheme is proposed for covering an area while taking into account the dynamic of the sensed physical parameter. Nevertheless, these works focus on the coverage of the full area instead of selected points of interest in a wide area. Moreover, whereas random deployment where nodes are scattered from the air can seem practical for very wide areas, deterministic methods such as grid based placement requires O(log N ) times fewer sensors than random deployments [START_REF] Kumar | On k-coverage in a mostly sleeping sensor network[END_REF] where N is the number of sensors deployed in the random scheme.

Deterministic deployments have been increasingly applied in WSN applications [START_REF] Damuut | A survey of deterministic vs. nondeterministic node placement schemes in wsns[END_REF]. Examples include Pipenet [START_REF] Stoianov | Pipenet: A wireless sensor network for pipeline monitoring[END_REF] or SimpliMote [START_REF] Ali | Simplimote: A wireless sensor network monitoring platform for oil and gas pipelines[END_REF] for pipelines monitoring; A Line in the Sand [START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF]: a dense and distributed WSN for intrusion detection and targets tracking; ATMS [START_REF] Schoeneman | Authenticated tracking and monitoring system (atms) tracking shipments from an australian uranium mine[END_REF]: an Authenticated Tracking and Monitoring System where a WSN combines both terrestrial and satellite links to secure uranium shipments from Australian uranium mines to Europe. In [START_REF] Bai | Deploying wireless sensors to achieve both coverage and connectivity[END_REF] and [START_REF] Yun | Optimal deployment patterns for full coverage and k-connectivity (k¡=6) wireless sensor networks[END_REF], studies of deployment patterns to achieve full coverage and kconnectivity (with k ≤ 6) are presented. Nevertheless, in this case as well, these works focus on the coverage of the full area instead of selected points of interest in a wide area. More recent works such as [START_REF] Boubrima | Optimal wsn deployment models for air pollution monitoring[END_REF] focus on deployments for a specific application but still aim at covering the whole area.

In [START_REF] Misra | Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements[END_REF], the authors treat the problem of optimal placement of relays on candidate locations in order to connect sensors to the sink in WSNs. They show that this problem is similar to the MST and thus NP-hard. They propose to use known heuristics to solve this MST problem. The problem treated in [START_REF] Misra | Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements[END_REF] is similar to our problem, but we use a different approach which is suited for wide white areas. We compare our results to a heuristic which solves MST.

Most of the works presented in this section aim at deploying a network for covering a target area, which is often rather small. In our work, we consider the case where there are few points of interest sparsely distributed in a very large area. The number of potential relay is thus very high. We present a new approach of deployment based on the growth of the physarum mold which we describe in the next section.

III. BIO-INSPIRED NETWORK DEPLOYMENT

In this section, we first present the background on physarum, then we present the physarum algorithm and its adaptation to network deployment.

A. Physiological concept of physarum growth

Physarum is a large, single celled amoeboid organism that forages to join irregularly distributed food sources [START_REF] Tero | Rules for biologically inspired adaptive network design[END_REF] and transforms them into nutrients. Fig. 1a shows an example of physarum connecting 36 food sources. To explain this natural network creation and optimization process, let us consider an initial physarum body placed in the space with 2 food sources (Fig. 2a). It growths toward all foods, once found it exploits them into nutrient which are conveyed through links. This leads to the creation of a fully connected network with lot of tube cross-connect points (pentagons in Fig. 2b). Finally, when there is no food anymore, it is able to optimize its body resources by deleting some unnecessary links and cross-connect points (Fig. 2c).

We are interested in physarum resource optimization mechanism, which we explain in the next subsection.

B. Physarum network optimization model

Mathematically, the network of tubes of the physarum is described as a graph [START_REF] Tero | A mathematical model for adaptive transport network in path finding by true slime mold[END_REF]. The vertices represent tubes connexion points (food sources or simple joining points) while edges represent the tubes themselves which allow fluid propagation in the physarum body [START_REF] Tero | Rules for biologically inspired adaptive network design[END_REF]. The physarum algorithm described in this section mimics the optimal resource exploitation part of the physarum behavior. The goal of the algorithm is thus to reproduce the capacity of physarum to prune edges and vertices of the network in order to keep only the most efficient (in terms of resources and resilience) connexion graph between food sources. The initial graph might thus contain many vertices which are not food sources. The algorithm convergence properties are investigated in [START_REF] Kentaro | Convergence properties for the physarum solver[END_REF]. It converges with an exponential rate. Moreover, it perfoms an output graph computation with a complexity in O(N 3 ) [START_REF] Xiaoge Zhang | Advances in Physarum Machines: Sensing and Computing with Slime Mould[END_REF], N being the size of the input graph.

As shown in Fig. 1b, to each node is associated an initial flow I i and a pressure P i (i = 1, 2, 3 in this example). The initial flow is the amount of nutrient obtained by food transformation. For food sources we thus have I i = 0 and for other connexion points I i = 0. In the algorithm, food sources are actually alternatively considered as sources or sinks of a nutrient flow as will be clarified further. The pressure P i is a variable for which we solve at each iteration of the algorithm. An edge connecting node N i to N j has a distance L ij and a width D ij which can change during the network evolution process. D ij is initialized to D 0 . Finally, Q ij is the flow [START_REF] Tero | A mathematical model for adaptive transport network in path finding by true slime mold[END_REF] traveling through the edge (i, j). It is defined as:

Q ij = D ij L ij (P i -P j ). ( 1
)
The algorithm is iterative. At each iteration, two steps are performed: (1) solving a set of equations for the variables P i , (2) update the edges parameters.

The first step consists of solving the following equations (equivalent to Kirchhoff's circuit law):

i Q ij = 0 j = s, t i Q is + I 0 = 0, i Q it -I 0 = 0, (2)
with j = s, t for source and sink nodes respectively, and I 0 the absolute value of the initial flow for source and sink nodes. Equations ( 2) form a linear system whose associated matrix is sparse. It can be solved by Incomplete Cholesky Conjugate Gradient (standard ICCG) method [START_REF] Kershaw | The incomplete cholesky-conjugate gradient method for the iterative solution of systems of linear equations[END_REF]. In the original algorithm [START_REF] Tero | A mathematical model for adaptive transport network in path finding by true slime mold[END_REF], only one sink and one source are considered. In subsequent works [START_REF] Tero | Rules for biologically inspired adaptive network design[END_REF], [START_REF] Nakagaki | Smart network solutions in an amoeboid organism[END_REF], more sources and sinks are considered by sequentially selecting every possible pairs of nodes with I 0 = 0. At each iteration a sink and a source are chosen among the food sources. The sink is chosen according to a uniform law. The source selection follows a specific probability mass function defined as:

p(S = j) = d γ ij k =j d γ kj , (3)
with d ij the geographical distance between N i the sink and N j , and γ a parameter. After the resolution of (2), the Q ij are recomputed with the obtained values of P i according to Equation (1). The second step is to update the edges to adapt them to the newly computed flow. Indeed, the link width D ij changes over time according to a flow adaptation function [START_REF] Tero | Physarum solver: A biologically inspired method of road-network navigation[END_REF]. The algorithm uses a discretized flow adaptation equation:

D n+1 ij -D n ij δ t = f (|Q n ij |) -D n+1 ij , (4)
where f is an increasing function with f (0) = 0, (D ij tends to decline if there is no flow in the edge but is augmented when the flow increases), n is the iteration

f (Q) = a|Q| µ 1 + a|Q| µ , (5)
with µ and a positive parameters [START_REF] Brummitt | A mathematical study of physarum polycephalum[END_REF]. The algorithm stops when the difference D n+1 ij -D n ij is less than a predefined threshold. The output of the algorithm consists in the D ij for each link. Then, to obtain the optimized network, it suffice to remove all links with D ij = 0 (or close to 0) and remove all the disconnected nodes. Table I summarizes all the notations.

In the next subsection, we show how to adapt this algorithm to solve the data collection network deployment problem in wide white areas.

C. Deploying wireless networks using the physarum algorithm

Previous works [START_REF] Tero | Rules for biologically inspired adaptive network design[END_REF], [START_REF] Zhang | Route selection for emergency logistics management: A bio-inspired algorithm[END_REF], [START_REF] Tero | Physarum solver: A biologically inspired method of road-network navigation[END_REF] have considered the physarum algorithm to model transportation networks. To the best of our knowledge this is the first work which considers applying the physarum algorithm to wireless network deployment.

We assume that the edges and vertices of the physarum graph respectively model the wireless data links and the network nodes. The input graph consists in all the potential relay nodes, all the points of interest and the data collection center. To build this graph, we consider a map of the area with all the points of interest. Then we add the potential relay nodes. This can be done either deterministically using a grid pattern or randomly. In this work, we chose to place potential relays randomly (uniform distribution) as detailed in Section IV-A. The next step is to add links to this initial graph. In order to do that, we consider the radio range of the nodes. We link every pair of nodes (relay or point of interest) which are in communication range.

We then initialize the node and edge variables of the algorithm. We consider that D ij is proportional to the rate capacity of a link (as it is the case for the physarum where the flow Q ij is proportional to D ij ). D ij is the output of the algorithm. The initial value of D ij , D 0 has a very small impact on the output, actually, it is even chosen randomly in [START_REF] Tero | A mathematical model for adaptive transport network in path finding by true slime mold[END_REF]. L ij is the geographical distance between the nodes N i and N j . In our case, each point of interest i is modeled as a food source with I i = I 0 , if it is set as a source, or I i = -I 0 , if it is set as a sink. The impact of the value of I 0 and µ (Equation ( 5)) on the characteristics of the deployed network is investigated in Section IV-C.

During step (1) of each iteration, we define the pmf of the random variable S representing the sink to be chosen:

p(S = k) = 1 K+W if k is a point of interest, W K+W
if k is a the destination, ( 6) with K the number of points of interest and W the weight of the data center (destination). The source is then chosen according to Equation (3). The algorithm not only outputs the topology of the network to be deployed, but also the D ij which gives an indication on how to dimension each link.

In the next section, we evaluate the algorithm and we show that it is able to compute efficient and fault-tolerant data collection network deployments in wide white areas with a huge number of potential relays.

IV. ALGORITHM EVALUATION

A. Considered scenarios

In this section, we define the scenarios we consider to evaluate the network deployment physarum algorithm.

We use a 180x180 km 2 zone where 16 points of interest are placed arbitrarily (they are chosen randomly and kept for all the experimentations). The data collection center is positioned at the center of the area. The potential nodes are placed randomly (uniformly). We make their number N varying from 500 to 5000. We consider a radio range R c varying from 5 to 30 km. This corresponds to the realistic ranges of LPWAN radios such as LoRa [START_REF] Goursaud | Dedicated networks for iot : Phy / mac state of the art and challenges[END_REF]. The larger the R c is, the more the initial graph is connected. Fig. 3a shows an example of an initial graph with 1500 potential relay nodes and their communication range R c equals to 15 km. Initial values of D ij are set to 1. We then make the values of the physarum algorithm parameters vary in order to tune them. We use the algorithm described in Section III, parameters and their ranges are summarized in Table II

B. Performance metrics

The performance metrics we analyze on the output network deployment are the connectivity, the total length of the links, the number of relays, and the fault tolerance.

The connectivity is a boolean variable C equals to 1 if there exists at least one path between the data collection center and all the points of interest, otherwise it equals to 0. The network total length (T L) is measured in kilometers. T L is the sum of all the links length in the output network. The number of relay nodes (RN ) is the number of nodes used in order to connect all the points of interest to the data collection center. Finally, the fault tolerance (F T n ) of the network is defined as the probability that the network remains connected even if an accidental failure occurs at n random links (or node) of the network. It is expressed as:

F T n = ξ -ξ * ξ , (7)
where ξ = |E| n is the total number of ways to choose

C. Reference algorithm for comparison

As mentioned in Section I, our deployment problem is very similar to a MST problem. MST is NP-hard, we thus compare our heuristic to another heuristic of MST called CHINS [START_REF] Vob | Steiner's problem in graphs: heuristic methods[END_REF] for CHeapest INSertion. For comparison aim, we define two cost functions as T L/T L M ST and RN/RN M ST respectively for T L and RN cost index, T L M ST and RN M ST are the obtained M ST total length and relay nodes respectively.

In the next subsection, we comment our results.

D. Results

In this section, we investigate the impact of the values of the initial parameters on the results of the algorithm. We especially focus on the trade-off between faulttolerance and deployment cost (total length and number of nodes).

Fig. 3b depicts an example of an output for the input graph of 3000 points. The following parameters I 0 = 1, δ t = 0.5, µ = 2 are used. The width of the edges represents the final D ij . The output network has 62 relay nodes (red points) and its total length is 611.26 km. It is close to the optimal MST (Fig. 3c) which contains 60 relays. For this example, the algorithm converges in less than 4 minutes on a modern computer (Intel i7 with 8G of RAM).

I 0 and µ have an important impact on the output graph. Some values (I 0 , µ) = {(1.9, 0.7), (1.8, 0.6)} can even produce disconnected output networks. In our scenarios, we observe that for µ > 2 and I 0 ≥ 1 the algorithm always converges and the output is close to a steiner tree. Therefore, if the goal is to dimension a very optimized resource network such as in Fig. 3b, I 0 = 1 and µ = {2, 3, 4, 5} are appropriate values. I 0 is the parameter that has the most impact on the faulttolerance of the network. For example, in Fig. 3d we obtain a resilient network using the following parameters I 0 = 5, µ = 1.8. In the remainder of this section, we investigate the trade off between cost and fault tolerance for different values of I 0 and µ. We compare the cost of the physarum algorithm with the CHINS-MST algorithm. As can be observed in Fig. 3c, the CHINS-MST does not provide the width of the edges. We consider the cost functions (RN/RN M ST ) and (T L/T L M ST ). In Fig. 4a, the cost function is plotted against I 0 for µ = 1.2, 1.9. We observe that the cost increases with I 0 . In fact, we observe in the obtained graph (for instance Fig. 3d), that the physarum algorithm creates more alternative routes when I 0 increases.

In Figs. 4c and4d, we observe the trade off between cost and fault tolerance F T 1 for different µ and I 0 In these curves, each point of the plot represents the mean of 100 executions of the algorithm for a given value of I 0 which is written as a label next to the point. 16 points of interest and N = 3000 relays with R c = 15 km are considered (similar results are obtained when N and R c vary). Only connected (C = 1) output graphs are kept. These graphs allow to tune µ and I 0 in order to obtain a target trade off between cost and fault tolerance. Networks with a higher fault tolerance are more expensive to deploy. The network designer can choose according to his budget and the reliability requirements of the application.

V. CONCLUSION

In this work we consider the problem of data collection network deployment in wide white areas. The goal is to deploy a network linking sparse points of interest which minimizes the amount of resources while providing a level of fault tolerance. The problem of resource minimization corresponds to the MST problem which is NP-hard. We propose to use a heuristic inspired from the behavior of the physarum mold. We present the model and detail how it can be applied to network deployment in wide white areas. We then study the performance of the algorithm on different scenarios in order to tune its parameters. Finally, we compare the performance of the physarum algorithm with an heuristic solving MST. We find that the physarum algorithm is able to find trade offs between cost and fault tolerance on very large considered areas while converging within minutes on a recent computer. Moreover, the physarum algorithms gives an indication on the capacity that should be allocated to each link by providing the width of the selected edges. In the future, we plan to use this indication in order to route the data flows in the network.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Physarum network.

  . The convergence criteria is set as the time where D ij stops changing for all links: D n+1 ij -D n ij = 0. D + ij and D - ij are respectively present and previous values of D ij and n the iteration index. The scenarios are generated on Matlab 2016b.

Fig. 3 :

 3 Fig. 3: Structure depending of the parameters.

2 Fig. 4 :

 24 Fig. 4: Performances analysis.

TABLE I :

 I Model parameters index, and δ t is the time step. In[START_REF] Tero | Flow-network adaptation in physarum amoebae[END_REF], the following function f is proposed:

TABLE II :

 II Evaluation parameters n links among the |E| of the output network, and ξ * is the number of configurations where we remove n links and the network ends up disconnected.