Roberto Morabito
email: roberto.morabito@ericsson.com

Riccardo Petrolo
email: riccardo.petrolo@inria.fr

Valeria Loscrì
email: valeria.loscri@inria.fr

Nathalie Mitton
email: nathalie.mitton@inria.fr

Demo: Design of a Virtualized Smart Car Platform

In this demonstration, we present a system that combines the use of Single-Board Computer with the lightweight characteristics of container virtualization technologies for the deployment of a Smart Car platform. Our approach allows the definition of an architecture that exploits the flexibility of containers in terms of dynamic service allocation even on embedded systems. The whole is combined with the design of an inner orchestrator that acts as manager for the scheduling of different virtualized instances according to specific levels of application priorities. We practically show how this integrated environment can facilitate the development of functional and versatile car On Board Units, even on top of constrained Single-Board Computer with several applications instantiated.

Introduction and Motivation

Modern vehicles are equipped with electronic systems that are becoming very sophisticated day by day. The functionalities provided by these platforms are several and vary from engine control, predictive diagnostics, driving assistance, and infotainment. However, with the increasing number of functionalities, computing and communication resources, that have to be handled by the On Board Unit (OBU), is constantly growing [START_REF] Lim | Challenges in a future ip/ethernet-based in-car network for real-time applications[END_REF]. OBUs are embedded systems with limited hardware resources and a critical software design that makes also a simple update procedure a not trivial operation. These constraints are combined with the typical software lifetime, which is much shorter than the lifetime of mechanical and technological components.

Bearing all these points in mind, we have identified in the use of lightweight virtualization technologies a suitable mechanism, which allows to design an OBU that can satisfy several requirements in terms of efficient software and hardware resources management.

In particular, container-based virtualization technologies -such as Docker1 -can bring the advantage of fast allocation and flexibility in managing different services. This is reflected in an easier OBU programmability -also for what concerns updating process, deployment of new software, and management of parallel processes-and in a clever way to deal with the limited OBU hardware resources. This last aspect represents the main novelty respect previous works like Carberry 2 , in which no applications allocation mechanism was considered in order to deal with the limited computational resources of Single-Board Computer.

System Design

The architecture of our prototype is depicted in Figure 1. The platform has been designed to meet specific software and hardware requirements. Below, we discuss our implementation choices from the hardware, software, and architecture point of view.

Hardware and Software setup. We use the Single-Board Computer Raspberry Pi (RPi) as hardware platform for the deployment of our system. Two key aspects have led us to the choice of the RPi platform. First, the possibility to easily integrate the platform in the vehicle without impacting the car design, thanks to the small RPi size. Second, the RPi capability on efficiently managing virtualized applications by means of container technologies. From this point of view, in [START_REF] Morabito | A performance evaluation of container technologies on internet of things devices[END_REF], authors demonstrated how the introduction of lightweight virtualization in devices with low computational resources introduces a negligible impact in terms of performance overhead. The OBD-II standard [START_REF]2004 Road Vehicles -Diagnostics on Controller Area Networks (CAN)[END_REF] interface is directly connected to the RPi and it is used to read data coming from the vehicle, allowing to monitor the current operating status of a vehicle, and to identify malfunctioning in the vehicle itself. OBD interface provides two types of data: real-time vehicle data and several Diagnostic Trouble Codes (DTCs). From the software perspective, as base Operating System, we use the image provided by Hypriot that is running Raspbian Jessie with Linux kernel 4.4.10. The Hypriot image provide a lightweight environment optimised for the execution of Docker container technologies, by also offering dedicated tools for container orchestration.

Architecture description. At the application level, our architecture entails three main components: (i) a set of virtu- alized applications tagged with different priority levels; (ii) an OBD container in charge of receiving and handling data from the vehicle; and (iii) the Orchestrator that has the task of monitoring the resources used by the entire system and by each virtualized application. We defined four application/service types: (i) Critical priority applications are characterized by the highest level of priority (e.g., firmware update/restore applications, or demanding control data); (ii) High priority applications, which include e.g., driver assistance, camera data; (iii) Moderate priority applications consist e.g., of tools provided by auto insurance companies, which offer reduced premiums if OBD-II vehicle data loggers are installed; (iv) Low priority applications include Entertainment/Multimedia contents streamed by an internal and/or external device. In defining the priorities, we refer to the application requirements defined by authors in [START_REF] Lim | Challenges in a future ip/ethernet-based in-car network for real-time applications[END_REF]. A key role is played by the orchestrator, which instantiates the execution of a virtualized application over another in line with the different priority levels. Furthermore, it deals with the limited computation capabilities of the RPi, by opportunistically scheduling the running applications also according to the available hardware resources.

Application Scenario

We analyze the case of an anomalous car gas emission detected by the OBD. We suppose that with this particular vehicle issue, the platform has to react with the instantiation of an application characterised by High priority. We also assume that, prior to the anomaly detection, two applications characterized by lower priority level, e.g. Moderate and Low, are simultaneously running in the platform. According to our design, the platform has to guarantee the execution of a specific application that can somehow help on solving and/or tracing the vehicle behaviour during the critical status. This will be possible thanks to the dynamic allocation of a container dedicated to this purpose. In practice, as soon as the orchestrator -which constantly receives data from the OBD-detects the anomaly, it executes the activation of another virtualized application dedicated to the execution of a particular task (Fig. 2). Referring to this example, a database is initialized in order to record all the parameters associated to the evaporative (EVAP) emission system. Moreover, considering that the execution of this task has an higher priority compared to the applications that were already running, the concurrent instances with lower priority will be paused to make available all the hardware resources to the application marked by High priority. This example shows how the versatility given by the use of containers enlarges the potentialities of the OBU platform in terms of backup functionality, and capacity of running-dedicated applications at given times, and efficient hardware resources management. Another important aspect coming from the example is the flexibilty of our architecture in the RPi harware performance optimization. Indeed, the definition of different priorities, together with the dynamic management of containers, is also useful to schedule which application takes priority when the hardware resources are kept busy -can not be neglected that the number of applications that can simultaneously run on top of the RPi has an upper-bound.

Demo

The demo will show the details of our proposal, by demonstrating all the architecture concepts defined in the previous sections. We show in practice how the orchestrator can cleverly manage the virtualized running instances. In particular, we refer to specific application scenarios in which the orchestrator has to deal with potential vehicle issues and it has to adequately respond in order to ensure a fast and dedicated counter-response to that specific issue. At the same time, the orchestrator will efficiently deal with the platform performance by providing all the necessary resources to favourite the higher-priority applications.

Conclusions

We have designed and implemented an embedded allin-one device for Smart Car applications. We have shown how emerging virtualization technologies can be employed to build a flexible and versatile OBU platform and demonstrated that our architecture can be efficiently embedded in credit card-sized Single-Board Computers, such as Raspberry Pi.

Figure 1 .

 1 Figure 1. Overview of the system components: the RPi 3 supports the software allocation of virtualised instances, which are in turn characterised by different priority levels defined according to specific requirements.

Figure 2 .

 2 Figure 2. Example of application scenario. Lower priority applications are paused once that the orchestrator detects a critical status in the vehicle. An application with backup functionalities is launched in order to record specific vehicle values involved in the anomaly.

https://www.docker.com

http://www.carberry.it

Acknowledgments

This work is partially supported by CPER DATA, the FP7 VITAL, and by the FP7 Marie Curie METRICS.


Mouna Rekik

Nathalie Mitton

Zied Chtourou

GRACO: a geographic GReedy routing with an ACO based void handling technique

Geographic routing has gained much attention as a basic routing primitive in wireless sensor networks due to its memory-less, scalability, efficiency and low overhead features. Greedy forwarding is the simplest geographic routing scheme, it uses the distance as a forwarding criterion. Nevertheless, it may suffer from communication holes, where no next hop candidate is closer to the destination than the node currently holding the packet. For this purpose, a void handling technique is needed to recover from the void problem and successfully deliver data packets if a path does exist between source and destination nodes. Many approaches have been reported to solve this issue at the expense of extra processing and or overhead. This paper proposes GRACO, an efficient geographic routing protocol with a novel void recovery strategy based on ant colony optimization (ACO). GRACO is able to adaptively adjust the forwarding mechanism to avoid the blocking situation and effectively deliver data packets. Compared to GFG, one of the best performing geographic routing protocols, simulation results demonstrate that GRACO can successfully find shorter routing paths with higher delivery rate, less control packet overhead and shorter end-to-end delay.

Introduction

Wireless sensor networks (WSN) consist of a large number of densely deployed sensors that have communication, computing, and sensing capacities [START_REF] Akyildiz | A survey on sensor networks[END_REF]. Although sensors have power and memory constraints, they are multi-functional with sensing, wireless communication, computation capabilities and low-cost devices. For these reasons, WSNs are widely used in many fields as military surveillance, disaster prediction, and environment monitor [START_REF] Akyildiz | A survey on sensor networks[END_REF]. WSNs require efficient routing protocols that adapt to the unpredictable and highly dynamic 1 environment. The network topology may change dynamically due to node mobility, node failure and various physical properties related to the propagation channel (e.g., obstructions, noise, and power limitations) [START_REF] Dvir | Power-aware recovery for geographic routing[END_REF].

Geographic routing [START_REF] Mitton | Position-Based Routing in Wireless Ad Hoc and Sensor Networks[END_REF] is an attractive routing technique for large scale wireless sensor networks due to its low overhead, high scalability and memory-less features. Unlike topology-based routing, it uses only local information about the geographic location of nodes to determine, at each step, the next node to forward the packet. Greedy geographic routing schemes consist of forwarding data packets closer to the destination at each step of the routing process. This can lead to data packets stuck in situations where the current node fails to find a node closer to the destination than itself. These situations are later referred as the void problem. Hence, geographic routing algorithms usually combine a greedy forwarding strategy with a recovery mechanism to solve the void problem. Several recovery strategies have been proposed in the literature, face routing is the most prominent and effective one since it was proven to guarantee data delivery. However, it relies on assumption of a planar graph which is not always achievable in realistic wireless networks and may generate long detours.

In this paper, we present GRACO a new geographic routing protocol that combines a modified greedy forwarding (GR) phase and an Ant-Colony-Optimization (ACO)-based recovery strategy. The main contribution of this paper is a geographic routing that dynamically avoids holes and creates multiples paths around them. The ACO-based recovery phase will use ants to discover alternative paths if greedy is not possible. The ant packets are sent around the void searching for route to a closer node than the stuck node to destination, then the protocol can switch back to greedy mode until the destination or a new void. GRACO greedy forwarding is assisted by pheromone trails from previous recovery phases, which will prevent to return to the same stuck node.

The remainder of this paper is as follows. Section 2 discusses the most relevant related work in geographic routing, recovery techniques and ACO based routing. Section 4 presents GRACO. Section 7 analyzes simulation results where CRACO and GFG routing are compared. Finally, Section 9 concludes this work.

Related work

This section browses the different concepts of the literature relative to GRACO.

Geographic routing

Geographic routing [START_REF] Mitton | Position-Based Routing in Wireless Ad Hoc and Sensor Networks[END_REF] is a routing concept that exploits geographic information instead of topological connectivity. It is localized, since only local information such as the geographic position of the current node holding a packet and of its one-hop neighbors in addition to the one of the destination are needed to make routing decision. Thus, there is no need to transmit routing messages to establish complete routes or update their states. Nodes do not have to store routing table or write additional information in the packets either. Hence, the low-overhead, localized and memory-less features make the geographic routing a simple and scalable routing concept.

A geographic forwarding strategy defines the next hop to which forward the packet using only geographic information. Several variants of geographic forwarding strategies have been proposed based on the way to exploit geographic information to forward a packet toward destination. Greedy [START_REF] Finn | Routing and addressing problems in large metropolitan-scale internetworks[END_REF], Most Forward Within Radius (MFR) [START_REF] Takagi | Optimal transmission ranges for randomly distributed packet radio terminals[END_REF], Nearest with Forward Progress (NFP) [START_REF] Hou | Transmission range control in multihop packet radio networks[END_REF] and Compass [START_REF] Kranakis | Compass routing on geometric networks[END_REF] are the most famous geographic forwarding strategies, they differ in the way to exploit geographic information to forward a packet toward destination: the geographic distance, the largest projection, the shortest hop or the angle respectively. Greedy [START_REF] Finn | Routing and addressing problems in large metropolitan-scale internetworks[END_REF] forwards the message to the neighbor that minimizes the Euclidean distance to the destination in each step [START_REF] Mitton | Position-Based Routing in Wireless Ad Hoc and Sensor Networks[END_REF]. Geographic Greedy forwarding is loop free. Indeed, at each step, the message has to move toward the destination and thus can not loop by going through a node it has already visited [START_REF] Mitton | Position-Based Routing in Wireless Ad Hoc and Sensor Networks[END_REF]. However, Greedy forwarding may not always be possible if all neighboring nodes are further away from the destination than the sender itself. This problem is called communication void, local maximum phenomenon or local minimum phenomenon. It is caused by deployment holes where the forwarding process is blocked at a node called stuck node. The occurrence of hole can be caused by many factors, such as sparse deployment, physical obstacles, node failures, communication jamming, power exhaustion, and animus interference [START_REF] Jiang | An information model for geographic greedy forwarding in wireless ad-hoc sensor networks[END_REF]. An alternative mode called recovery mode is then needed to Figure 1: The stuck node has no positive progress neighbors to D. Although a path to D exists, the stuck node can not progress the packet using GF. guarantee delivery otherwise the packet has to be discarded and the delivery fails.

Recovery techniques

Solving the problem of communication voids in geographic routing in WSN is the subject of considerable research, many studies have been focusing on this topic and different solutions have been proposed. The existing void handling strategies can be classified into six categories [START_REF] Dazhi | A survey of void handling techniques for geographic routing in wireless networks[END_REF][START_REF] Sanavullah | An efficient void handling technique for geographic routing in [MANET: A survey[END_REF][START_REF] Parvin | A survey on void handling techniques for geographic routing in vanet network[END_REF] : flooding-based, planargraph-based, geometric, cost-based, heuristic, and hybrid.

Intuitively, the simplest recovery technique is flooding, initiated at the stuck node and executed afterwards at all node receiving the stuck packet for the first time. Original flooding and other advanced flooding-based techniques have been proposed to recover from the communication void in geographic routing . These techniques will certainly enable stuck packet to reach the destination if at least a path exists, however, they are inefficient in terms of resource utilization.

Planar graph based recovery techniques rely on a planarization process and a planar graph traversal algorithm. The planarization process consists of creating a plane sub-graph of the network graph where no edges intersect each other. Face routing [START_REF] Bose | Routing with guaranteed delivery in ad hoc wireless networks[END_REF] was used as the basic planar graph transversal algorithm in planar-graph based void handling techniques. In fact, it is the first geographic routing algorithm to guarantee message delivery without flooding [START_REF] Mitton | Position-Based Routing in Wireless Ad Hoc and Sensor Networks[END_REF]. Face routing is applied on a planar graph of the network graph. The plane graph divides the plane into faces. The line segment between the source node and the destination node intersects some faces then, the packets will be forwarded along the boundaries of these faces. Although face routing guarantees delivery, it is energy-consuming since it may generate long detours and makes the packets follow a succession of short edges [START_REF] Gouvy | Greedy Routing Recovery Using Controlled Mobility in Wireless Sensor Networks[END_REF]. Given the advantages of greedy forwarding, it has been combined with face routing in order to reduce the global energy consumption. Indeed, when the greedy fails to forward a packet, face routing is used as a recovery mechanism. Afterwards, several routing algorithms using the combination greedy face routing were proposed [START_REF] Mitton | Position-Based Routing in Wireless Ad Hoc and Sensor Networks[END_REF][14] such as Greedy-Face-Greedy (GFG) [START_REF] Bose | Routing with guaranteed delivery in ad hoc wireless networks[END_REF], Greedy Perimeter Stateless (GPSR) [START_REF] Karp | Gpsr: Greedy perimeter stateless routing for wireless networks[END_REF], Greedy Other Adaptive Face Routing (GOAFR+) [START_REF] Kuhn | Geometric adhoc routing: Of theory and practice[END_REF]. Planar graph based void handling techniques depends on building and maintaining the planar graph which causes significant overhead especially in the case of large scale networks. Besides, techniques from this class usually create long detours to overcome the void inducing extra costs in terms of delay, overhead and energy consumption to deliver the data.

In geometric void handling techniques, the basic idea is the use of the geometric characteristics to identify void regions. This category includes void prevention solutions, such as the techniques proposed in [START_REF] Tsvietkov | A novel method of locating voids in MANET structure[END_REF][START_REF] Senouci | Detecting boundary nodes in wsn[END_REF][START_REF] Yang | Hole detection and shape-free representation and double landmarks based geographic routing in wireless sensor networks[END_REF][START_REF] Fan | An efficient bypassing void routing algorithm for wireless sensor network[END_REF][START_REF] Zhang | A bypassing void routing combining of geographic and virtual coordinate information for wsn[END_REF][START_REF] Yu | Hole plastic scheme for geographic routing in wireless sensor networks[END_REF][START_REF] Fei | Improving routing efficiency through intermediate target based geographic routing[END_REF], where holes are discovered in advance for the future use of routing to avoid holes. These solutions usually start by a network discovering phase to detect the boundary nodes and identify the voids and a forwarding mechanism that exclude nodes located on the voids borders from routing process. This is accomplished by spreading information about voids to record the state of the network, and sending feedback, which clearly increases the overhead and causes energy exhaustion especially for the nodes located on holes boundaries. Besides, nodes need much greater resources such as memory storage compared to other void handling techniques in order to record the discovered voids information, especially when holes have a very large boundary.

In cost-based void handling strategies a cost value will be assigned to all nodes in the network depending of the destination and then forwarding packets from a node with a higher cost towards a node with a lower cost. The definition of cost parameter depends of the protocol. The performance of cost-based voidhandling techniques depends on the number of destinations, the number of void nodes, and network dynamics [START_REF] Dazhi | A survey of void handling techniques for geographic routing in wireless networks[END_REF]. Techniques from this category works well in static wireless networks with moderate number of void nodes with a limited number of destination nodes under a relatively small network. Otherwise, the recovery phase will generate hight overhead due to cost adjustment process and the maintenance around void regions.

Heuristic void handling techniques consists of exploiting some additional resources or using some inherent properties of network topology and some geographic properties of void areas [START_REF] Dazhi | A survey of void handling techniques for geographic routing in wireless networks[END_REF] such as using alternative existing communication media in the network, or gradually increasing stuck node's transmission power to search for a positive progress neighbor, or passive participation by not participating in the routing process while the node is enable to find positive progress neighbors, etc. However, these techniques are not always effective, or even possible.

Hybrid void-handling techniques, such as the one proposed in [START_REF] Denardin | A geographic routing hybrid approach for void resolution in wireless sensor networks[END_REF], combine at least two void-handling techniques together to handle voids more effectively and more efficiently. Usually, this combination increases the complexity of the void handling technique compared to others from different category.

All the above cited recovery techniques work well in static networks. Any change in void localization, such in dynamic networks, will require maintenance process with extra processing, overhead and delay. To overcome these drawbacks, we propose an efficient recovery technique for greedy forwarding based on ant colony optimization. The proposed routing algorithm is a geographic routing that is able to adaptively adjust the forwarding mechanism to avoid the holes, create one or multiple paths around them and effectively deliver data packets.

Ant colony Optimization

Ant colony optimization (ACO) is a bio-inspired approach from ants foraging behavior. Real ants are able to find the shortest path between their nest and a food source without any visible, central or active coordination mechanisms. Ants drop pheromones, a natural chemical substance, on the path. The path optimization is achieved by exploiting the pheromone quantity deposited. Then, ants select a path based on the pheromone concentration deposited on the set of paths found. The higher the concentration of pheromone on a path, the greater the probability to select it. This indirect communication mechanism is called stigmergy. In addition to that, real ants show an impressive behavior when encountering obstacles on their way. Actually, they are able not only to avoid obstacles, but also to find a shortest path around them.

ACO based approaches are very effectively applied to NP-hard problems and result in good optimization. Networking field is one of the many domains that have investigated ACO-approaches to design multi-objective and multi-constraint routing protocols and solve issues like mobility, path optimization, resource utilization and energy awareness. ACO was mainly proposed by Dorigo [START_REF] Dorigo | The ant colony optimization meta-heuristic[END_REF] [START_REF] Dorigo | The ant colony optimization metaheuristic: Algorithms, applications, and advances[END_REF], and it was widely used to solve network data routing problems. Many routing protocols based on ACO meta-heuristic were proposed in the literature [START_REF] Zungeru | Classical and swarm intelligence based routing protocols for wireless sensor networks: A survey and comparison[END_REF][29] [START_REF] Sutariya | A survey of ant colony based routing algorithms for MANET[END_REF] [START_REF] Huang | Swarm intelligence-inspired adaptive routing construction in wsn[END_REF]. ARA (Ant Colony Routing Algorithm) [START_REF] Gunes | Ara-the ant-colony based routing algorithm for MANETs[END_REF] the first ACO-based routing algorithm aims to reduce routing overhead and most of the existing ACO based routing techniques in WSN and mobile ad-hoc networks are derived from this algorithm [START_REF] Shirkande | ACO based routing algorithms for adhoc network (WSN, MANETs): A survey[END_REF]. ACO based routing uses two types of agents, forward ant packets and backward ant packets. The first type of ants is used to discover paths toward destination and the second one aims to drop pheromone trails on the established path between the source node and the destination node.

[34], [START_REF] Sutariya | A survey of ant colony based routing algorithms for MANET[END_REF] and [START_REF] Shirkande | ACO based routing algorithms for adhoc network (WSN, MANETs): A survey[END_REF] provide comparative studies of ACO based routing algorithm. Although ACO-based routing algorithms solve many problems such as multiconstraints and multiobjective routing, in addition to path optimization, these algorithms usually produce high overhead, since, in order to converge to an optimized solution, they need a colony-like behavior, i.e. a huge number of ant-like packets.

In this paper, we introduce GRACO, a geographic routing algorithm that combines a modified greedy forwarding and a recovery technique based on ACO. It is the first algorithm that uses ACO to assist greedy forwarding. It allows to circonvince voids and provides multi-paths around them.

Notations and system models

We assume that all nodes are aware of their location through an hardware device such as GPS or any other location mean. We model the wireless sensor network as a directed graph G=(V,E), composed of a finite set V of sensors, called also nodes, and a finite set E of links. A wireless link exists between nodes U and v (the link U v ∈ E) if U and v are within transmission range of each other, i.e. |U v| <= R , where |U v| represents the Euclidean distance between U and v. The directed link from a node U to a node v is denoted -→ U v. The physical set of nodes which are in transmission range of node U is denoted N (U ) and called the neighborhood of node U ,

N (U ) = {v ∈ V such as |U v| ≤ R}. We denote |N (U )| the cardinality of N (U ), |N (U )| is the number of neighbors of U . We also define N D (U ) the subset of N (U ) in which each node is nearer from node D than U itself, i.e. N D (U ) = {v ∈ N (U ) such as |vD| ≤ |U D|}.
In the following, we call "current node" the node trying to route a packet and we use N extN ode to refer to the next hop in the path of a packet. We denote C(A, r) the circle C of radius r and centered at A. For two nodes A and B, the circle C(A, |AB|) is the circle of radius |AB| and centered at A.

Algorithm 1 GRACO(U) -Run at each node U upon reception of a message

M (U, D) 1: if U=D then 2:
EXIT # U is the final destination of M . The routing has succeeded. end if 8: end if

GRACO

GRACO overview

GReedy with ACO-based recovery routing protocol (GRACO) is a geographic routing algorithm that combines two modes : a greedy mode and an ACObased recovery mode triggered when greedy mode fails. Algorithm 1 depicts the GRACO behavior. In GRACO, a data packet is first routed using a modified greedy routing that accounts for the pheromone trails. If a pheromone trail exists for a given destination, it is used to select the next node. Otherwise, the next hop is selected using plain greedy forwarding strategy. However, if the packet reaches a stuck node (a node that has no neighbor closer to the destination that itself neither pheromone trails), the node launches an ACObased recovery and sends some exploratory ants (Fant) to find a path. The stuck node waits for a backward ant (Bant) to come back, if so, a path is established and data packets can be sent. The data packet will be routed using the same strategy as the Fant until arriving to the unstuck node, and then switch to greedy forwarding again until its destination or another stuck node, in which case, the same mechanism applies again. Both steps are now detailed in the following sections.

Ph-assisted greedy forwarding

The greedy mode of GRACO consists of a variant of the plain greedy forwarding (GF). Plain GF is enhanced with the use of pheromone trails from older recoveries detailed in section 5. Consider a node S that wants to send a data packet to D. Before applying GF, S checks whether it has recorded pheromone trails to D in order to avoid returning to the same stuck node. If so, that means the greedy failed to progress a previous data packet during a previous attempt for the same destination D and a recovery mode was been launched. For that reason, S will use these pheromone trails to send the packet instead of the GF. Otherwise, If there is no pheromone trail for D, S proceeds by using the greedy method.

The example presented in Fig. 2 explains the ph-assisted greedy forwarding. In Fig. 2a, S sends a first data packet to D, the packet is forwarded using plain greedy until it arrives to the stuck node N 5 , thus, as shown in Fig. 2b, a recovery phrase is triggred in N 5 , several paths are found, and pheromone trails are dropped on the nodes belonging to these paths. The first data packet is, then, relaunched from N 5 using one of the paths found, as presented in Fig. 2c. In Fig. 2d, S sends a second data packet to D, the packet is routed using plain greedy forwarding until arriving to N 4 where it finds pheromones to D, then it uses a pheromone based forwarding which helps the packet to avoid the stuck node N 5 . Thus, GRACO's greedy mode is a Ph-assisted greedy forwarding. The Ph-assisted greedy forwarding phase is summarized in Algorithm 2.

ACO based Recovery

Similarly to other ACO based algorithms, the ACO recovery uses two types of ants to solve a problem : Fants (Forward-ants) to discover the environment, and Bants (Backward-ants) to "mark" the solutions found. In addition, GRACO relies on a concept of zones, which plays an important role, that we introduce in the following.

Zones

Using the concept of zones [START_REF] Kamali | Posant: A position based ant colony routing algorithm for mobile ad-hoc networks[END_REF], a node divides its neighborhood into 4 zones based on its position and the position of D. Consider a destination node D, each node U partitions its neighbors into two main zones: the positive progress zone, later called zone 1 , and a negative progress zone. As shown in Fig. 3, zone 1 is represented by the intersection of the two circles C 1 (U, R) and C 2 (D, |DU |). It gathers nodes in N D (U ). Then, the negative progress zone is then partitioned into 3 sub-zones: zone 2 , zone 3 and zone 4 . Let α be the positive progress angle and β the negative progress angle, as presented in Fig. 4, α is the angle

( --→ U B, -→ U A)
where A and B are the points of intersection of two circles

C 1 (U, R) and C 2 (D, |DU |), and β = 2Π -α. For a node v ∈ N (U ), θ is the angle ( --→ U D, -→ U v). Node v belongs to : -zone 2 if α 2 < θ ≤ α 2 + β 3 -zone 4 if α 2 + β 3 < θ ≤ α 2 + 2. β 3 -zone 3 if α 2 + 2. β 3 < θ ≤ α 2 + β

Pheromone initialization

Before starting a route establishment phase to a destination D, the amount of pheromone deposited on the links must be initialized. Each node U that has no pheromone to D and needs to forward a Fant toward D, assigns a pheromone trail to each of its outgoing links for D, i.e., an initial pheromone value φ 0j is assigned for each neighbor v in N (U ) as j ∈ {1, 2, 3, 4} and zone j being the zone in which node v lies, knowing that φ 01 ≥ φ 0 2 (= φ 03 ) ≥ φ 04 . The motivation is that, in most cases, shortest paths pass through the neighbors whose directions are closer to the direction of the destination. Thus, the initial pheromone values being bigger as the zone is closer to the destination, direction will favor ants to choose these zones. As a result, this phase leads to a fast convergence to a shortest path most of the time. The ACO-based recovery strategy assumes that each node maintains a PhTable, a table of pheromone values assigned to its outgoing links for different destinations. Whenever a node receives a packet for a specific destination D, it searches in its PhTable for pheromone for D. If such pheromone trail exists, it will be used to choose the next hop. Otherwise, a pheromone initialization process is launched. The pheromone initialization process attributes pheromone trails to all the outgoing links of a node. However, the not updated pheromone trails will be evaporated as the time passes. If a link is unused, the pheromone level on it should be completely evaporated by the end, thus, the corresponding PHTable entry is deleted. In this way, the pheromone evaporation process minimises the amount of data stored in the nodes.

Route establishment

The route establishment phase is accomplished using two types of ants: the Fant and the Bant. The main role of the Fant is to explore the neighborhood in order to find an alternative path. To do so, it drops on its way, a pheromone track to the stuck node to be later used by the Bant. The Bant establishes the route to the destination found by the Fant by dropping pheromone trails when it goes back to the stuck node. Fant and Bant are small packets, they only carry their ID, information about stuck node, destination, previous node and the hop count.

The route establishment starts at the stuck node K. In each zone, K selects the neighbor with the best progress to the destination. The Fant will be considered and forwarded only by the 3 selected neighbors. The IDs of the selected neighbors are stored in the diffused Fant. Whenever a neighbor receives the Fant, it checks whether it is in the list of the selected neighbors, if not it ignores the packet . In the example presented in Fig. 5, the stuck node selects 3 neighbors, N 1 ,N 3 and N 5 , each one is the the closest to destination in its zone.

The recovery phase triggered by the stuck node in summarized in Algorithm 3.

Whenever a node U receives a Fant, it checks whether it is closer to the destination than the Stuck node K or not. If so (|U D| < |KD|), U sends back a Bant, the recovery can end and the greedy step resumes. Otherwise, U forwards the Fant. Similar to other ACO routing algorithms [START_REF] Shirkande | ACO based routing algorithms for adhoc network (WSN, MANETs): A survey[END_REF], a node forwards a Fant to the next node using a stochastic decision based on the values of pheromone trails to select the next hop. Suppose that a Fant is currently residing in node U. U has k neighbors v 1 , v 2 , ..., v k . We will note Φ i the amount of pheromone assigned to v i (or the link --→ U v i ). The neighbors of U will be partitioned into 4 zones. Consider Φ zonei is the maximum pheromone amount assigned to the neighbors of zone i , Φ zonei = max {Φ j \ v j ∈ zone i }. In order to forward a Fant, Send(F AN T (K, D), N extN ode) # to send the Fant to N extN ode 12: end if first of all, U selects a zone with probability P zonei :

P zonei = Φ zonei 4 j=1 Φ zonej (1)
U chooses a node v i in this selected zone with probability P i :

P i = Φ i |N (D)| j=1 Φ j (2)
Using the concept of zones, the ants are not completely blind, as in the usual ACO based algorithms, they will be attracted, but not forced, to the right direction. Besides the PHTable mentioned before, each node maintains also a back routing table, the BRTable, to store information that will be used later by Bants to go back to the stuck node. Whenever a Fant arrives to a node from one of its neighbors, an entry is added to the BRTable. Fig. 6 shows an example of a Fant F trying to bypass a void. F is launched at the stuck node, and forwarded to N 1 , N 2 , N 3 until reaching unstuck node N 4 . To summarize, Algorithm 4 shows the forwarding strategy of the Fant until it arrives to an unstuck node, a node closer than the stuck node to the destination. When a Fant reaches an unstuck node N , a Bant is sent back to the stuck node. An unstuck node is a node closer to destination than the stuck node. After adding an entry to the BRTable, N extracts the information from the Fant, creates a Bant and destroys the Fant. Subsequently, N sends the Bant to the stuck node K. The role of the Bant is to drop pheromone on the path Send(BAN T (K, D), N extN ode) # to send the Bant to N extN ode 7: end if found in order to establish a track from K to N. Unlike the traditional ACObased algorithm, the Bant will not necessarily return to the stuck node using the same path of the correspondent Fant, but it will use the pheromone dropped by other Fants that used at least one node of its path. In the example presented in Fig. 7, the Fants find two valid paths to an unstuck node, the first one presented in green is a 4-hop-length path and the second one in pink is a 16-hop-length path. A Bant, in this example, chooses to use the green path to go back to K since it is the shortest path to K. On its way back to the stuck node, the Bant updates pheromone trails in the PHTables. Consider a Bant arrives to node A from node B, it will update pheromone track of the link --→ AB in the PHTable of A :

Φ--→ AB = Φ B = Φ B + ∆Φ where ∆Φ is the amount of pheromone added to reinforce the path to D, this value depends on the quality of the path. Algorithm. 5 sums up the Bant forwarding.

In order to improve the performance of GRACO, the stuck node is able to relaunch the recovery phase n times, where 0 n n max , if it does not receive any Bant in a certain interval of time. ACO algorithms are based on the balance between two processes : intensification ( deposition of pheromone) and diversification (evaporation). The evaporation rule is used to reduce the effect of old pheromone. Thus, for each node U , the pheromone trail of its neighbor v i is evaporated periodically using formula [START_REF] Akyildiz | A survey on sensor networks[END_REF].

Φ i = Φ i * (1 -α) ( 3
)
where α is the pheromone evaporation rate, 0 < α < 1.

Multiple recoveries for the same destination

In its way to the destination, a packet may face different voids in a single path, for that reason, in such cases, the recovery mode will be launched several times. In order to reduce the effect of old recoveries, the pheromone added to a PHTable will be marked by the rank of the recovery launched. A Fant will use only the pheromone of its recovery to decide where to go next. A Bant returning to mark a good path, will remove old pheromone trails found in its way. Thus, a node that received ants from different recoveries, will have, at the end, only recent recovery pheromones in its PHTable . Fig. 8 shows an example of multiple recoveries launched in the way from a source S to a destination D. Fig. 8a presents the first recovery mode launched, the ants find during this phase two paths to unstuck nodes. The data packet will then choose one of these paths. If the data packet uses the pink path, it reaches another stuck node, a second recovery mode is then launched. The new Fant will use only its pheromone, otherwise, it cannot go out of the stuck node since the pheromone dropped on the pink path are stronger than the initial trails of the second recovery. The second recovery ants will find the blue as shown in Fig. 8b. Since the second recovery finds a good path to an unstuck node, the first recovery pheromones are no longer useful. The new Bant deletes older pheromone traces and adds the new one. The next time the source node S decides to send a packet to D, this latter will be forwarded using greedy forwarding until node N and then pheromone forwarding, as presented in Fig. 8c.

Loop management

In the route establishment phase, a Fant may run into a loop. We prevent this situation using a simple process to detect and manage a loop. The first time a node detects a Fant in a loop, it assigns a loop flag to the packet and returns it back to the previous node. Each node that receives a Fant with a loop flag, tries to get out from this loop by sending it to another node then the one it came from. If it is not possible, the node sends the Fant back to the previous node in its path, using BRtable. And so on until the Fant goes out from the loop, the loop flag is removed. In the case where the Fant returns back to the node that first detected a loop, the Fant is cancelled. Consider the example of a Fant F1 that enters in the loop ABC as shown in the Fig. 9a. F1 loop management process is presented in Fig. 9, and described in the following steps :

1. Node A receives F1, it recognizes duplicate receptions of F1 based on a memorized entry previously added by the same ant. Since A is the first node to detect F1 in loop, it assigns a loop flag to F1. A does not add any information about the duplicated ant in the BRTable. Then, it sends the packet back to the previous node C.

2. C receives F1 and recognizes that F1 is in loop based on the loop flag, C deactivates the link to the previous node (A) and tries to send F1 out of the loop. Since A is no more considered (the link is deactivated) and B exists in the BRTable of C (that means F1 already passed from B), C couldn't get F1 out of the loop, it decides then to return the ant to the previous node (B). C sends F1 to B and deletes B from its BRTable. N extN ode ← V 12: end if of the loop. Since C is no more considered (the link is deactivated) and A exists in the BRTable of B (that means F1 already passed from B), B couldn't get F1 out of the loop, it decides then to return the ant to the previous node (A). B sends F1 to A and deletes the entry of F1 from the BRTable.

4.

A receives F1 for the second time, it deactivates the link to the previous node (B) and kills the ant F1.

By deactivating the links that lead to loop, the next ants will not come to the same situation again. Similarly, deleting entries from BRTable will prevent Bants to loop in their way back.

The loop management process is described in Algorithm 6 and Fig. 10 .

Simulations and results

In order to evaluate the performance of the GRACO algorithm, we simulated its functioning under the WSNet simulator [START_REF] Fraboulet | Worldsens: Development and prototyping tools for application specific wireless sensors networks[END_REF]. WSNet is an efficient eventdriven simulator dedicated to WSN, which has been extensively evaluated and compared [START_REF] Ben Hamida | On the complexity of an accurate and precise performance evaluation of wireless networks using simulations[END_REF].

For a fair performances evaluation, we choose to compare our results against GFG routing algorithm [START_REF] Bose | Routing with guaranteed delivery in ad hoc wireless networks[END_REF]. GFG is an efficient geographical routing protocol for wireless sensor networks that combines the greedy forwarding with face routing as a recovery mode, it has been proven to guarantee data delivery for arbitrary connected planar graphs [START_REF] Frey | On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks[END_REF] with low complexity added in terms of routing overhead and additional latency of the recovery mode compared to other geographic routing protocols [39] [9]. To the best of our knowledge, all more recent geographic protocols that are able to efficiently encounter voids and guarantee data delivery with better performances, are only variants of GFG. protocols were proposed to improve the performance of GFG by modifying some initial assumptions, such as using adjustable transmission range [START_REF] Hamouda | Energy-aware georouting with guaranteed delivery in wireless sensor networks with obstacles[END_REF], which is not relevant are our case. To the best of our knowledge, to date, GFG remains the best geographic routing protocol that guarantees the delivery and considers the same initial assumptions that we do. We evaluated two versions of GRACO, the first one tries to minimize routing overhead while maintaining good performance level, indeed, for a single recovery step, if no Bant is back to the stuck node within an interval of time T = 1ms, it is allowed to relaunch another set of 3 ants only once, n max is then set to 1. The second variant of GRACO focuses on guaranteeing the delivery, the stuck node will then send a set of 3 ants periodically as long as no Bant is back. We note GRACO V 1 where n max = 1 and GRACO V 2 where n max → ∞.

We generate random topologies in a 300m × 300m region with 250 to 900 nodes and R = 25m. Each combination of topology and algorithm is run 50 times, which ensures a 95% confidence interval. To evaluate the impact of voids on the performance of each routing protocol, each topology contains necessarily void zones with different diameters and shapes. In each topology we choose a set of 10 pairs of (source, destination) in such a way that there is always at least one void to be handled during the routing process.

The performance of GRACO is mainly measured based on data packet transmission delay, delivery rate and the routing path length (in terms of hop count) in order to measure the robustness and effectiveness of the routing protocol against voids. Besides, we measure the global data delivery cost including recovery cost. The simulation results of GRACO and GFG are given with 95% confidence intervals.

We compared the performances of GRACO and GFG in two steps. We started by simulating the performance of GRACO V1, GRACO V2 and GFG with an ideal MAC layer, thus no collision is simulated. The choice of using an IdealMac was made to isolate the impact of routing algorithms only. In a second step, we compared the functioning of GRACO V2 and GFG with more realistic MAC layer, the IEEE 802.15.4 mac. We choose to simulate only GRACO V2 since it performs a better delivery rate than GRACO V1 with reasonable cost.

Data delivery cost

We measure data delivery cost as the total number of packets sent in the network to deliver data from a source to a destination, including routing and recovery control packets.

Fig. 11a presents the data delivery cost varying with the number of data packets sent for an Idealmac layer. The cost of GRACO V2 is clearly higher than GRACO V1 since the number of ants used in GRACO V2 is bigger than GRACO V1. At the beginning, GFG seems to use less packets to deliver the data than GRACO, but when the number of data packets sent increases, the cost on GFG increases fast. GRACO V1 uses less cost starting the second data packet sent. However, GRACO V2 becomes cheaper than GFG in the 10th data packet sent between same source and same destination.

Simulations run on IEEE 802.15.4 show similar results. As shown in Fig. 12a, the total cost of GFG is less than the one of GRACO V2 in the beginning, but starting from the 4th data packet sent, the cost of GFG becomes much higher than GRACO V2's one.

The simulations proved that the more data packets are sent between the same source and destination, the cheaper become GRACO comparing to GFG. These results are explained by the fact that the number of packets sent during the recovery phase in GRACO is bigger than GFG in one recovery mode. However, when the number of data packets sent between the same source and the same destination increases, GRACO becomes cheaper than GFG since GRACO launches the recovery mode only when the first data packet is sent, the next ones will use the routes already found. As for GFG, it launches the recovery mode every time a data packet is sent. Thus, the cost on GRACO for multiple packets between the same source and destination is the same as for only one packet, in contrary with GFG, the cost used to deliver multiple data packet will be the cost of sending one packet multiplied by the number of data packets sent. In Fig. 11b and Fig. 12b, it can be seen that the cost per packet decreases when the number of data packets increases. On the other hand, the cost of GFG to deliver a single packet remains constant.

Hop count

Fig. 13 displays the average length of the paths generated by GRACO and GFG for different network densities. The path length is defined as the number of hops followed by the data packet to travel from its source to its destination.

The simulations show that GRACO creates shorter paths than the ones established by GFG. GFG may generate extremely long paths in some cases [START_REF] Seada | Modeling and analyzing the correctness of geographic face routing under realistic conditions[END_REF] especially in low density networks as shown in Fig. 13. In the other hand, the ACO and the zone concept used in GRACO helps the algorithm create shorter paths than the one created by GFG.

In order to bring out the multipath feature of the recovery strategy used in GRACO, we count the number of paths found by each routing protocol. As presented in Fig. 14, GFG uses the same path in all iterations, however, GRACO is able to find multiple paths if possible. The few cases, that GRACO finds only one path in all iterations is where it is the only path possible.

End-to-end delay

The end-to-end delay accounts for the duration from the time a packet is ready for the transmission at the original source until it is received and decoded correctly at its final destination. In case of a set of data packets, it represents the delay between the source sends the first data packet and the destination receives the last one. Sources and destinations are randomly chosen in a way they are in different sides of a void to trigger recovery process.

Fig. 15 and Fig. 16 depict the end-to-end delay depending on the number of data packets sent with Ideal MAC layer and 802.15.4 MAC layer.

We can see that GRACO delivers data packets in shorter end-to-end delays than GFG. Actually, data packets will be delivered faster using GRACO, as it generates shorter paths than GFG. Furthermore, when the number of data packets sent increases, the delay gap between GFG and GRACO becomes larger. Indeed, when sending several packets from a source to the same destination, GRACO launches the recovery only once, when the first data packet attempts to bypass the void, the next ones will use the pheromone trails dropped on the paths found during the previous recovery phase and will directly follow a short path to the destination. At the contrary, GFG launches its recovery mode every time a data packet has to bypass the void. Thus, GRACO delivers the data packets faster than GFG.

Packet delivery rate

Packet delivery rate (PDR) is the ratio of data packets successfully received by their destinations to all data packets sent by the sources.

P DR = number of data packets received number of data packets sent Fig. 17 plots the data delivery rate of GRACO V1, GRACO V2 and GFG simulated with an ideal MAC layer. It shows that both of GFG and GRACO V2 deliver all packets sent successfully. In the other hand, GRACO V1 performs a delivery rate in the worst case around 92% . Thus, GRACO V2 guarantees delivery with an extra cost compared to GRACO V1, however, it remains cheaper than GFG in terms of end-to-end delay and the routing cost specially when the number the data packets sent increases .

GRACO V1 suffers from packet loss in some rare cases where Fants get lost in the network specially in multiple voids cases, due to the random factor in the stochastic decision to choose next hop. Even when the first data packet reaches its destination, the following data packets will suffer from the impact of these pheromone trails, which explains the fact that the delivery rate of the first data packet is always higher than multiple data packets. However, the effect of these pheromone trails will be reduced with the time as a result of pheromone evaporation. Indeed, the pheromone evaporation process is an important factor in ACO meta-heuristic, called the diversification factor, it helps to eliminate pheromone trails that may misguide ants and then to adapt to the dynamic nature of the environment. At the end the bad pheromone trails will be totally evaporated and new paths will be found. This depends of the evaporation factor and the intensity of the pheromone deposited. For that reason, we can see, in Fig. 17 that the delivery rate starts to increase again when the number of data packets grows.

Fig. 18 shows the data delivery rate varying with the number of data packets sent with an IEEE 802.15.4 MAC layer. Due to packet collisions measured using the IEEE 802.15.4 MAC layer, the data delivery rate of GFG and GRACO degrades. However, the delivery rate of GFG is affected more than GRACO V2; the GFG delivers less than 80% of the data, while GRACO V2 delivers up to 90% of the data.

This can be explained by the fact that the number of control packets used by GFG is bigger than GRACO which has a significant impact on the performance of the routing process with IEEE 802.15.4 MAC layer.

Discussion on memory overhead

GRACO is not a memory-less routing algorithm. Indeed, as explained in Section 2.3, the ACO-based recovery is accomplished using pheromone trails, these trails will be memorized in PHTables within the nodes on recovery paths. A PH-Table of a node memorizes the pheromone trails on its outgoing links. If a node belongs to several recovery paths for different destinations, it keeps pheromone trails for each of these destinations.

All pheromone trails evaporate periodically, the non-updated pheromone will be deleted faster than the updated ones, thus, a node will have only updated pheromone.

In addition to PHTables, each node in a recovery path stores a BRtable to help Bants to go back to the stuck node. Every entry in a BRTAble will be deleted after an interval of time that we fixed.

To ensure the loop management process, each node stores the IDs of the received Fants in order to recognize the duplicated ones. The node will delete these IDs after a time interval equal to the time-to-live of the Fant.

Hence, unlike GFG, GRACO is not memory-less routing protocol. In fact, nodes of recovery paths store local information about pheromone trails to their outgoing links, back routing information and Fant IDs for loop management process. However, these information are volatile, and will be deleted after a while, since they are only useful for a short time.

The time interval to delete stored data is a recurring problem of cache memory, and is left out of the scope in this paper. In the other hand, simulation results show that GRCAO outperforms GFG in terms of data routing cost, endto-end delay, data delivery rate and the length of generated paths. Besides, the proposed recovery strategy creates multiple path around the void.

Conclusion

In this paper, we presented GRACO, a new geographic routing protocol able to handle the void problem with very low added complexity. It combines a pheromone assisted greedy forwarding phase and an ACO-based recovery phase to efficiently avoid holes and recover from local minima. The proposed routing protocol is fully localized, distributed, scalable, and does not require any graph structure. Nodes, that are part of recovery paths, need to store local information about pheromone trails, back routing and loop management. However, all this information is stored for a short time, the evaporation factor reduces the pheromone information, and other stored information will be deleted when not useful anymore.

Besides the efficient hole avoidance, simulation results show that both GRACO V1 and GRACO V2 deliver data packets faster and cheaper in terms of data delivery cost and hop count compared to GFG routing protocol. GRACO V1 provides a high delivery rate with a minmum cost, in the other hand, GRACO V2 guarantees delivery with an extra-cost in term of end-to-end-delay and data delivery cost that remains lower that GFG's guaranteed delivery cost. Simulation results with 802.15.4 MAC layer show that GRACO outperforms GFG in terms of end-to-end delay, data delivery cost and data delivery rate.

As future work, we intend to propose GRACO as a routing solution for Smart Grid Neighborhood Area Netowrk (NAN). Smart grid is the next generation of electrical power grid. It integrates information and communication technologies (ICT) to allow for reliable and sustainable electric power delivery and to integrate renewable energies. There is no smart grid for all, every energy grid will develop its own applications and services. Therefore, many services and concepts related to smart grid such as Virtual Power Plant (VPP) [START_REF] Rekik | Performance and applicability of a new geographic routing protocol for virtual power plants[END_REF] [START_REF] Rekik | A scalable geographic routing protocol for virtual power plant communications[END_REF] and distributed energy and storage integration into the grid [START_REF] Rekik | Geographic routing protocol for peer-to-peer smart grid neighborhood area network[END_REF] are expected to require partial or fully distributed control and the ICT deployed in parallel to the electrical grid should be scalable and should not introduce additional constraints to the smart grid development. For this purpose, we plan to study and analyze the applications supported by NAN in order to define NAN communication requirements, and to implement an extension of GRACO that takes account of the QoS required.

(

  a) First Packet sent from S to D : greedy forwarding phase (b) First Packet sent from S to D : recovery phase (c) First Packet sent from S to D (d) Second Packet sent from S to D : ph-assisted greedy forwarding

Figure 2 :

 2 Figure 2: Ph-assisted greedy forwarding

Algorithm 2 : else 4 :

 24 Ph assisted greedy(U,D) -Run at each node U upon reception of a message M (U, D) 1: if existP h(U, D) = true then 2: N extN ode ← getN extN odeP H(U, D) # There already exists a pheromone trail to D 3if N D (U ) = ∅ then 5: N extN ode ← N st ||U D| -|N D|| = max v∈N D (U ) ||U D| -|vD|| # tradiend if 10: Send(M(N extN ode,D)) # to send the message to N extN ode

Figure 3 :

 3 Figure 3: Different zones of U for the destination node D

Figure 4 :

 4 Figure 4: Illustration of α, β and θ

Figure 5 :Algorithm 3 5 :

 535 Figure 5: Fant is considered by the closest node in each zone.

Algorithm 4 4 :

 44 Forward Fant(F AN T (K, D)) -Run at each node U upon reception of a Fant for D issued by stuck node K 1: update BRT able(U ) 2: if |U D| < |KD| then 3: # Node U allows a progress compared to the stuck node and can stop the recovery, U sends a Bant to K BAN T (K, D) ← Create Bant(F AN T (K, D)) # Node U creates a Bant to send it back to K in order to drop pheromone to D 5: F orward Bant(BAN T (K, D)) ode ← getN extN odeP H(U, D) 11:

Algorithm 5 2 : 3 :else 5 :

 5235 Forward Bant(BAN T (K, D)) -Run at each node U upon reception of a Bant destined for K 1: update P Htable(U, D) # the Bant updates pheromone trails in the node U for the destination D if U = K then Ph assisted greedy(U,D) # Send the data packet 4: N extN ode ← getN extN odeBRtable(U, D) 6:

3 .Algorithm 6 1 :then 2 : 3 :then 4 :

 361234 B receives F1 and recognizes that F1 is in loop based on the loop flag, B deactivates the link to the previous node (C) and it tries to send F1 out Loop Management(V,D) -Run at each node U upon reception of a Fant for D coming from node V if Loop F lag = 1 delete ph phtable(V,D) # delete ph phtable(V,D) deletes the ph trail to neighbor V for destination D in PHTable of the current node U if |N (U )| > 1 N extN ode ← getN extN odeP H(U, D)

  (a) Step1: Fant F 1 reaches N 1 , N 1 is not closer than the stuck node (b) Step2: N 1 forwards F 1 to N 2 , N 1 chooses zone 2 using formula (1) then selects N 2 according to Equation (2).(c) Step3: N 2 receives F 1 , N 2 is not closer than the stuck node to the destination.(d) Step4: N 2 forwards F 1 to N 3 , N 2 chooses zone 1 using Eq. (1) then selects N 3 according to Eq. (2).(e) Step5: N 3 receives F 1 , N 3 is not closer than the stuck node to the destination (f) Step6: N 3 forwards F 1 to N 4 , N 3 chooses zone 1 using Eq. (1) then selects N 4 according to Eq. (2).

  (g) Step7: N 4 receives F 1 , N 4 is closer than the stuck node to the destination, N 4 sends a Bant to the stuck node to mark the path found.

Figure 6 :

 6 Figure 6: An example of a Fant searching for a path around a void

Figure 7 :

 7 Figure 7: Bant returns to the stuck node

Figure 8

 8 Figure 8: Multiple recoveries

Figure 11 :

 11 Figure 11: Data cost -Ideal MAC Layer

Figure 12 :

 12 Figure 12: Data cost -802.15.4 MAC Layer

Figure 15 :

 15 Figure 15: end-to-end delay varying with the number of data packets sent -Ideal MAC Layer

Figure 16 :Figure 17 :Figure 18 :

 161718 Figure 16: end-to-end delay varying with the number of data packets sent -802.15.4 MAC Layer

Table 1 :

 1 Simulation parameters

	These


Adib Tavakoli

Christophe Blanc

Hossein Ftouni

Kunal J Lulla

Andrew D Fefferman

Eddy Collin

Olivier Bourgeois

Universality of Thermal Transport in Amorphous Nanowires at Low Temperatures

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

the phenomenological TLS model even though its microscopic explanation is still elusive. Here, by scaling down to the nanometer scale amorphous systems much below the bulk phonon-TLS mean free path, we probed the robustness of that model in restricted geometry systems. Using very sensitive thermal conductance measurements, we demonstrate that the temperature dependence of the thermal conductance of silicon nitride nanostructures remains mostly quadratic independently of the nanowire section. It is not following the cubic power law in temperature as expected in a Casimir-Ziman regime of boundary limited thermal transport. This shows a thermal transport counter intuitively dominated by phonon-TLS interactions and not by phonon-boundary scattering in the nanowires. This could be ascribed to an unexpected high density of TLS on the surfaces which still dominates the phonon diffusion processes at low temperatures and explains why the universal quadratic temperature dependence of thermal conductance still holds for amorphous nanowires.

their physical structures at the microscopic level. However, at low temperatures, the behavior of the thermal properties of almost all amorphous materials are thought to be universal [1]. These common features include a nearly linear specific heat and a nearly quadratic thermal conductivity in temperature below few Kelvin. As thermal transport is concerned, this universality is not only qualitative but also quantitative, indeed the thermal conductivity of all amorphous materials lies within a factor of twenty in the same order of magnitude called the glassy range [2,3]. Despite much theoretical efforts, this universality remains poorly understood and its true microscopic origin is still elusive. Nowadays, the most accepted model is based on the presence of tunneling two level systems (TLS) involving tunneling between different equilibrium positions of an atom or group of atoms [4][5][6]. The scatterings of the phonon on these tunneling sites is assumed to be at the origin of the quadratic variation of thermal conductance in temperature. The phonon heat transport is then characterized by the phonon-TLS mean free path (the distance between two inelastic collisions written down MFP) which is on the order of few hundreds of micrometers.

Phillips suggested that TLS are likely to form in materials with an open structure and low coordination regions, and are unlikely in highly dense amorphous systems [4]. Recent experiments give indication of the correlation between the low density regions, the presence of nanovoids and the presence of TLS [7,8]. In the opposite case the different experiments based on hydrogenated Si [9], and ultrastable glasses [10,[START_REF] Perez-Castaneda | Proc. Natl. Acad. Sci[END_REF] have shown a significant reduction of the TLS density and a tendency to be more crystal-like [10][START_REF] Perez-Castaneda | Proc. Natl. Acad. Sci[END_REF][START_REF] Liu | [END_REF]. These results support Phillips original suggestion. Understanding the origin of these localized excitations (or TLS) is one of the most challenging problem of modern condensed matter physics at low temperature. Indeed, many questions have been raised concerning their existence [13], their fundamental origins [14], their possible role in the decoherence of quantum entangled states in Josephson quantum bit [15,16], or their noise producing aspects in superconducting resonator [17]. Probing the phonon-TLS scattering through the measurement of the phonon-TLS MFP in low dimensional samples (membranes, nanowires) can bring significant new insights for the understanding of thermal transport in amorphous materials at the nanoscale. phonon mean free path is set by the phonon-phonon interaction leading to the well known cubic power law in temperature of the thermal conductivity (κ(T ) ∝ T 3 ). This MFP can be very long at low temperature because the phonon-phonon interactions become less probable. This leads to boundary scattering limited transport called the Casimir-Ziman regime where phonon scattering only appears on the edges of the materials [18][START_REF] Ziman | Electrons and Phonons[END_REF][START_REF] Berman | [END_REF]. It has been shown

recently that, at the nanoscale, the thermal transport in a single crystal silicon nanowires belongs to this regime. Thermal conductance having variation in temperature very close to the expected cubic power law has been found [21][22][23][24].

Then, the low temperature thermal transport in amorphous materials (bulk or very thick film) departs strongly from its single crystal counterparts by its universal quadratic thermal conductivity [1]. This quadratic variation is the distinctive picture of glassy materials, the bulk phonon MFP being limited by the phonon-TLS inelastic interactions which lies in the range of 20µm< Λ bulk ph-T LS < 200µm, at 1 K [1,[4][5][6]25]. The present experiments, done on glassy systems of restricted geometries, are putting in competition the Casimir-Ziman regime where phonons are essentially scattered by the boundaries (characterized by a thermal conductance cubic in temperature) and the amorphous regime where phonons are scattered by TLS. The main objective of this work is then to probe phonon transport in spatially confined systems at the nanoscale, i.e. below the characteristic length set by the bulk phonon-TLS MFP in amorphous materials Λ bulk ph-T LS . This should yield crucial insights on the location and maybe on the origin of the TLS in glasses.

Here, we carried out very sensitive thermal conductance measurements on silicon nitride nanostructures at low temperatures. The samples have various dimensions from millimeter membrane to micro and nanowires, where the sizes are purposely much smaller than the bulk phonon MFP in amorphous materials (set by the phonon-TLS interactions). As silicon nitride is known to be a fully amorphous materials, widely used for its exceptional mechanical and thermal properties [26][27][28][29][30][31][32], it is one of the best materials to study the competition between phonon boundary scattering and phonon-TLS interactions play a significant role in the thermal transport.

The low temperature thermal properties of Si 3 N 4 have been already studied by different groups without considering the possible contribution of TLS to the phonon scattering [30,[33][34][35]; however, a little later the problem has been raised by two theoretical works [36][37][38][39].

The present experiments will allow the probing of 1-the phonon-TLS interaction down to the nanometer scale and 2-its effect on the power law of the variation of thermal conductance versus temperature. Unexpectedly, as the Casimir-Ziman regime should be observed in nanowires through the T 3 behavior of κ(T ), a robust T 2 is observed, showing that even in restricted geometry, the phonon-TLS scattering is still governing the heat transport.

The thermal conductance measurements have been performed on 100 nm thick mechanically suspended stoichiometric Si 3 N 4 structures from the millimeter scale (membrane) to the nanometer scale (nanowire) in order to cross the characteristic length given by Λ bulk ph-T LS (see Fig. 1). Various 3ω methods adapted to each geometry have been used; these different techniques have been already explained elsewhere [40][41][42]. All thermal measurements are done using a niobium nitride (NbN) thermometry very sensitive over a broad temperature range (from 0.1 K to 330 K) [43]. The thermal conductance of the micro and nanowires are measured using the longitudinal 3ω technique where the heat flow is along the NbN transducer (see Fig. 1a). Concerning the membrane, 3ω-Volklein geometry is used, in this technique the heat flow is perpendicular to the transducer since this one is deposited in the center of the membrane (along the long side, see Fig. 1b). Four geometries of suspended structures have been used for that purpose; all the dimensions of samples are summarized in Table I.

In Fig. 2 (a) the thermal conductance of the nanowire, the microwires and the membrane is shown in a log-log plot. The first point that needs to be highlighted is the similar quadratic temperature behavior for all the different samples with a thermal conductance proportional to T 1.5 to T 2 . It is in agreement with the universal behavior of glasses T 1.8 , but far from the cubic behavior expected for the Casimir-Ziman regime [1,2]. Quantitatively, the conductance of the nanowire is almost two orders of magnitude below the conductance of the narrow microwire, and six orders of magnitude below the conductance of the membrane. This is the consequence of several concomitant effects: the reduction of the geometry (boundary scattering) and the reduction of the phonon MFP due to phonon-TLS interaction that both limit the heat transport.

In order to go deeper in the discussion and compare the dimensional reduction and TLS effects on phonon scattering on the thermal transport, one needs to report on thermal conductance normalized to length and widths [44]. This is done by calculating the thermal conductivity κ through the regular expression κ = KL tw , where K is the measured thermal conductance, t the thickness of the materials and w the width. This is shown in Fig. 2 (b) where, for the same amorphous materials Si 3 N 4 , the thermal conductivities vary significantly from one geometry to the other, decreasing when the section of the heat conductor decreases. This is illustrating the fact that the phonon transport is limited by boundary scatterings at low temperature, the so-called Casimir-Ziman regime of heat transport [18,[START_REF] Ziman | Electrons and Phonons[END_REF].

Deciphering the intrinsic mechanisms responsible for the heat transport implies obtaining the most relevant parameter: the phonon mean free path. In order to extract that crucial physical parameter from our measurements, one uses the phenomenological approach developed by Pohl, Liu and Thompson [1] to interpret the thermal conductivity data obtained on bulk amorphous materials. The authors combine the well known kinetic relation κ = 1 3 c D v s Λ ph perfectly valid at low temperature (as long as ballistic transport is not involved) along with the fact that the thermal conductivity κ is proportional to the square of the temperature as illustrated in Fig. 3 (a):

κ(T ) = ζ 0 T 2 = 1 3 c D v s Λ ph (1)
where ζ 0 is a phenomenological proportionality factor equal to the thermal conductivity κ at 1 K; c D is the volumetric specific heat of the phonons carrying heat; v s is the average speed of sound, which is 9900 m/s in silicon nitride; and Λ ph is the phonon MPF independent of dimensions. ζ 0 can be estimated through the TLS model, however this is not required for the determination of the phonon MFP, indeed ζ 0 = κ T =1 K , then directly extracted from the experiments.

One important fact should be clarified in this approach; one needs to know the specific heat c D related to phonons that are carrying heat. This should not be mixed up with the experimental specific heat of amorphous materials mostly dominated by the tunneling states [1]. By using the Debye model for estimating c D , very good agreement is obtained between experiments and calculations for temperatures down to 1 K as demonstrated by Pohl et al. [2,45]. Similarly here we use the regular Debye expression at low temperature as the input for the specific heat:

c D = 2 5 k 4 B 3 π 2 v 3 s T 3 (2)
When combining Eq. 1 and Eq. 2 the phonon MFP can then be expressed by:

Λ ph = 15 3 v 2 s 2π 2 k 4 B • κ(T ) T 3 (3)
One can see in Eq. 3 that the MFP is given, not only by the temperature and the speed of sound, but also by the thermal conductivity as function of temperature. So, by measuring thermal conductivity one can have a direct experimental determination of the MFP as a function of the different sections of heat conductors. In our analysis, as shown in Fig. 3 (a),

we have first checked that the proportionality κ ∝ T 2 is still valid even at the nanometer scale. Then, we have extracted the phonon MFP using Eq. 3; the results are presented in Fig. 3 (b).

Two different limits are observed for the phonon MFP depending on the size of the samples. The first concerns the large systems (membrane and large microwire) for which the MFP lies in the glassy limit given by the grey area Fig. 3 (b). This glassy range is defined as the minimum or maximum MFP experimentally obtained on bulk amorphous materials.

So concerning the large samples, we can conclude that the thermal transport is similar to what happens in bulk materials. On the other hand, for the small section samples, smaller phonon MFP's are clearly observed as if they were set by the interaction with the surfaces as expected in the Casimir-Ziman regime. The increase of MFP in narrow microwire and nanowire at low temperature is interpreted as the signature of specular reflections of phonons on the wire boundaries. When specular reflections are involved in the thermal transport, the temperature variation of the MFP is generally well described in the framework of the Berman Foster Ziman (BFZ) model of phonon boundary scattering using the sole physical roughness of the surfaces as a fitting parameter [START_REF] Berman | [END_REF].

The phonon scattering on the boundaries may have two possible origins, either from the actual asperity (physical roughness) of the nanowires or due to the presence of TLS on the surface. We will then calculate an effective roughness η ef f of the nanowire from the experimental phonon MFP variation with temperature and compare it to the roughness estimated from the scanning electron microscopy image (SEM). That effective roughness will be representative of all the phonon scattering processes: scattering on boundaries characterized by the actual physical roughness (asperity) and the scattering of phonon on TLS.

To obtain the effective roughness for the nanostructures, we first extract the probability of specular reflection p(λ, η) = exp (-16π 3 η 2 /λ 2 ) where η is the roughness of the nanowire's edges, and λ is the dominant phonon wavelength. To do that, we equal the experimental MFP to the MFP calculated from the BFZ model [START_REF] Berman | [END_REF]:

Λ ph = 1 + p exp (λ, η) 1 -p exp (λ, η) Λ Cas (4)
Λ Cas = 1.12 √ w × t is the Casimir MFP, where w × t is the section of the nanosystems.

So the experimental probability of specular reflection can be obtained from Eq. 4 through:

p exp = Λ ph -Λ Cas Λ ph + Λ Cas (5)
Λ ph is the experimental MFP as calculated through Eq. 3 from the thermal conductance.

The experimental probability of specular reflection for narrow microwire and nanowire is illustrated in Fig. 4 as extracted from Eq. 5, in comparison with theoretical fits for different roughness. The fits help us to estimate this effective roughness η ef f that can be compared to the mean roughness obtained from the SEM characterization of the nanowire. The roughness that fits the experimental probability of specular reflection is of the order of η ef f ∼ = 9 nm three times bigger than the one evaluated by SEM observation which is about η ∼ = 3 ± 1 nm (see inset of Fig. 4). This excess of roughness is attributed to TLS that act on the surfaces as an artificial roughness; meaning that phonon-surface TLS scattering dominates the heat transport. This is indeed fully consistent with the quadratic temperature variation of the thermal conductance [46].

To conclude, we show that for amorphous nanowires the temperature variation of the thermal conductance is still quadratic; even if it would have been expected that in restricted geometry the behavior of thermal conductance would be cubic like in the Casimir-Ziman regime (boundary scattering limit). This is ascribed to the presence of a strong density of phonon scattering centers located on the surface as seen in the study of the effective roughness obtained from the phonon mean free path. A possible high density of TLS can explain this observation which is in good agreement with the quadratic variation of κ(T ).

Actually, the TLS are expected to form in nanovoids or low density regions which are sensitive to preparation methods (temperature growth and thickness) of the materials [7][8][9][10]. This means that, especially for thin films, the presence of voids in volume is less probable than on the surfaces. Consequently, the TLS may indeed be concentrated on the surfaces in agreement with our experimental observations [8].

Both results (quadraticity and phonon MFP) show the robustness of the universality of thermal transport in amorphous materials even down to the nanometer scale. The high density of TLS may have significant consequences for dissipation processes and decoherence phenomena in quantum nanoelectromechanical systems (NEMS) made out of amorphous SiN [26,47,48]. Further experimental proofs of the high density of TLS on the surface could be obtained by specific heat measurements on low dimensional amorphous systems like very thin membranes at very low temperature or by nano-electromechanical measurement at very low temperature (below 10 mK). An abnormal high TLS density would be revealed by an anomalously high surface specific heat.

FIG. 1 .

 1 FIG. 1. Pictures and schematic representations of the various Si 3 N 4 suspended structures. The red arrows represent the heat flux, the blue arrows, the dimensions of these samples. (a) Suspended silicon nitride nanowire measured with the longitudinal 3 ω method [40] (the microwires are not shown) and (b) experimental configuration of the silicon nitride membrane measured using the planar 3 ω-Volklein method [41, 42]. The blue layer represents the niobium nitride (NbN), the thin film transducer used for the thermal measurements.

FIG. 2 .

 2 FIG. 2. (a) the thermal conductance of the membrane (black), the large microwire (dark green), the narrow microwire (green), and the nanowire (light green) is shown in a log-log plot. The overall temperature behavior of the thermal conductance of all these samples is quite similar. (b) effective thermal conductivities calculated as a base for comparison of phonon thermal transport between the different geometries. As the dimensions are reduced, the thermal conductivities decrease. The glassy range is represented by the grey area in the plot.

FIG. 4 .

 4 FIG. 4. Extracted probability of specular reflection for the nanowire (light green) and the narrow microwire (dark green) in comparison to the theoretical fit from Ziman approach using Eq. 5 with different roughness. The hatched area shows a purely diffusive regime known as the Casimir regime where the MFP becomes equal to the diameter of the nanostructure. In inset, an SEM picture of the SiN nanowire edge is shown. The actual roughness is much smaller than 9 nm.

We thank the micro and nanofabrication facilities of Institut Néel CNRS: the Pole Capteurs Thermométriques et Calorimétrie (E. André, P. Lachkar, G. Moiroux and J.-L. Garden) and Nanofab (T. Crozes, S. Dufresnes, B. Fernandez, T. Fournier, G. Julié and J.-F. Motte) for their advices in the preparation of the samples. OB and EC acknowledges the financial support from the ANR project QNM Grant No. 040401, the European projects MicroKelvin EUFRP7 Grant No. 228464 and OB from MERGING Grant No. 309150.

Indeed, since the phonon MFP changes with the reduction of size in the case of nanostructured samples, the absolute value of thermal conductivity is not a relevant parameter.

[45] P.D. Vu, J.R. Olson, and R.O. Pohl, J. Low Temp. Phys. 113, 123 (1998).

[46] We did not do the same data treatment to the two largest samples (microwire and membrane) because they belong to the quasi-bulk limit for which the Berman Foster Ziman model may not fully apply.

[47] M. Defoort, K.J. Lulla, C. Blanc