Jean-Antoine Seon

Redwan Dahmouche

Michaël Gauthier

Enhance in-Hand Dexterous Micro-Manipulation by Exploiting Adhesion Forces

Keywords: Dexterous Manipulation, Micro/Nano Robots, Grasping, Manipulation Planning, Path Planning for Manipulators

Micro-manipulation plays a key role in the development of complex and assembled micro-systems. However, current micro-manipulation solutions are often limited to small rotation amplitudes and to simple shaped objects (such as cubes). Our approach consists in developing in-hand micro-manipulation techniques using dexterous micro-hands to manipulate arbitrary shaped objects and to perform large rotations. This paper focuses on the trajectory generation of a dexterous micro-hand to achieve automated repositioning by taking advantage of adhesion forces. The results on the generated trajectories show that adhesion forces can be exploited to enhance the manipulation possibilities. Moreover, experiments show that planed rotations are performed at more than 95% using an open loop control. Dexterous micro-manipulation is a promising way to perform complex manipulation tasks in micro-scale.

I. INTRODUCTION

Dexterous manipulation has been an active field of research in macro-scale for decades [START_REF] Okamura | An overview of dexterous manipulation[END_REF]. Indeed, the grasping and manipulation planning problems have been explicitly formalized [START_REF] Li | On motion planning for dexterous manipulation. i) the problem formulation[END_REF] and various approaches to perform dexterous manipulation have been studied such as rolling [START_REF] Bicchi | Dexterous manipulation through rolling[END_REF], sliding [START_REF] Brock | Enhancing the dexterity of robot hand using controlled slip[END_REF] and finger gaiting [START_REF] Han | Dexterous manipulation by rolling and finger gaiting[END_REF]. However, it has not been largely investigated in micro-manipulations which is usually limited to simple pick and place operations for simple objects [START_REF] Xie | Three-dimensional automated micromanipulation using a nanotip gripper with multi-feedback[END_REF] [7] [START_REF] Feddema | Micro-assembly planning with van der waals force[END_REF] [9] [START_REF] Cappelleri | Automated assembly for mesoscale parts[END_REF]. We show in this paper that in-hand dexterous micro-manipulation is a promising way to control the rotation of micro-objects for micro-systems assembly.

In robotics, rotations can be obtained in two ways. The first one, which is the most common industrial solution, consists in using a basic tweezer placed on a robot which rotates the carried gripper. Thus, this approach uses simple gripper, such as a parallel jaw gripper, and the accuracy is limited by the backlash and the eccentricity in the robot's joints. The second way consists in using a dexterous hand to perform in-hand rotation [START_REF] Zhou | Automatic dextrous microhandling based on a 6-dof microgripper[END_REF] [START_REF] Inoue | Micro hand with two rotational fingers and manipulation of small objects by teleoperation[END_REF] [13] [14] [15]. This method, which requires more elaborated gripper, can be very versatile as a single "hand" can manipulate a large range of objects. The microhand fingers can be mounted on simple translation actuators with high repeatability. In this case, the accuracy is dependent on the contact between the fingers and the object surface.

Both approaches have different performances in microscale. Indeed, backlash and eccentricity (typically around 10µm [START_REF] Tan | Characterization and compensation of xy micropositioning robots using vision and pseudo-periodic encoded patterns[END_REF]) might be comparable to the object dimensions

The authors are with FEMTO-ST Institute, AS2M department, Univ Bourgogne Franche-Comté, CNRS, 24 rue Savary, 25000 Besanc ¸on, France.

ja.seon@femto-st.fr, redwan.dahmouche@femto-st.fr, michael.gauthier@femto-st.fr (typically around 1µm to 100µm). Consequently, in the first way, the accuracy is highly disturbed by backlash and eccentricity in the robot joints. Thus, this paper focuses on the second way proposing to perform micro-object rotation using in-hand dexterous manipulation.

Dexterous manipulation in micro-scale is different from the macro-manipulation since gravitational and inertial forces are dominated by the surface forces such as van der Waals, electrostatic and capillary forces [START_REF] Fearing | Survey of sticking effects for micro parts handling[END_REF]. These attractive forces change the manipulation paradigm as the objects stick to both the manipulating fingers and the substrate. Thus planning finger trajectory for effective dexterous manipulation in microscale is significantly different from macro-scale.

Two main approaches might be considered to take into account these particularities. The first one consists in modifying the contact properties to reduce adhesion forces by varying environmental parameters such as humidity and temperature [START_REF] Savia | Contact micromanipulation survey of strategies[END_REF] or by controlling the surface roughness [START_REF] Arai | Integrated micro end effector for dexterous micromanipulation[END_REF]. These methods are used to get as close as possibleto macro-scale manipulation. The second one consists in developing new strategies taking into account these adhesion forces. Indeed, it has been shown that taking advantage of these forces can enhance the gripping strategies [START_REF] Corney | A study of capillary forces as a gripping principle[END_REF]. Moreover, even if the adhesion phenomena is not fully predictable, creating sticky fingers is possible using nanostructuration [START_REF] Dejeu | Adhesion control for micro and nano manipulation[END_REF] or chemical functionalization [START_REF] Cot | Modeling of electrostatic forces induced by chemical surface functionalisation for microrobotics applications[END_REF].

In this paper we propose to exploit these adhesion forces, to enhance the stability and the strategies of micro-manipulation. The main contribution of this paper is the development of the first trajectory planner for in-hand dexterous micromanipulation that takes into account adhesion forces. Original fingers' trajectories are proposed and the benefit of exploiting adhesion forces is demonstrated. The content of this paper has been partially mentioned in a previous conference paper [START_REF] Seon | Finger Trajectory Generation for Planar Dexterous Micro-Manipulation[END_REF]. This article presents a more detailed methodology and trajectories validated experimentally considering different conditions of use.

The next section gives an overview of the related work in automatic dexterous micro-manipulation while Section III gives a general formalization of this problem. Section IV details our methodology to compute stable grasps and generate trajectories. Finally, Section V presents several trajectories for in-hand manipulation with sticky fingers which are compared to classical non-sticky finger trajectories.

II. RELATED WORK

One of the first works on dexterous micro-manipulation was conducted by Thompson and Fearing on the orthotweezers [START_REF] Thompson | Automating microassembly with orthotweezers and force sensing[END_REF]. In this system, two orthogonal fingers were Fig. 1: Illustration of an automatic 180 • rotation performed using 3 fingers on our manipulation setup [START_REF] Brazey | Experimental validation of in-hand planar orientation and translation at microscale[END_REF].

used to manipulate micro-blocks (200µm×200µm×100µm). The manipulation process was performed using manipulation primitives such as grasp the object, rotate along z-axis, etc. Since a two fingers hand has limited dexterity, a static external block was used to achieve a two axis rotation.

In 2006, Zhou et al. developed a 6 degrees of freedom (DOF) manipulator able to perform automatic in-hand manipulation [START_REF] Zhou | Automatic dextrous microhandling based on a 6-dof microgripper[END_REF]. The manipulator used only two fingers to manipulate micro-blocks (300µm×300µm×100µm). Similarly, Wason et al. have worked on automated micro-assembly using three probes [START_REF] Wason | Automated multiprobe microassembly using vision feedback[END_REF]. Two of them were used to grasp the object while the last probe was passive and was used to generate out of plane rotations for polygonal objects. In these methods, fingers' rolling on the object during the rotation was neglected and no finger gaiting was used which limits the rotation amplitude.

In 2015, Zhan et al. developed a planar micro-gripper able to accurately control the orientation of optical fibers [START_REF] Zhang | Monolithically integrated two-axis microgripper for polarization maintaining in optical fiber assembly[END_REF]. This micro-manipulator was composed of two jaws designed specifically to rotate optical fibers over 90 • . This micromanipulation is performed thanks to the rolling of the optical fiber when the two jaws translate. However, this setup is limited to cylindrical shaped objects and the rotation is limited because of the number of jaws.

Recently, Brazey et al. have developed a dexterous micromanipulation system able to perform large rotations of microobjects [START_REF] Brazey | Experimental validation of in-hand planar orientation and translation at microscale[END_REF]. The setup is composed of three fingers having two degrees of freedom each. Fig. 1 shows a 180 • rotation of a 200µm micro-square. The manipulation process is fully automated and is based on trajectories generated using manipulation primitives.

Beyond the current dexterous micro-manipulation approaches, the proposed method developed in this paper is not limited to squared objects. Indeed, arbitrary shapes are considered and the rolling constraint of the fingers during the object rotation is explicitly taken into account. Furthermore, the sticky forces that may exist in the micro-scale are taken into account in the finger path planning.

III. MODELING AND BACKGROUND

This section formalizes the grasping and in-hand manipulation problem in micro-scale and emphasizes the contact modeling differences with the macro-scale.

A. Grasping Forces

Let us consider the general case of six DOF manipulation using N fingers. In order to manipulate the object, fingers must apply a grasping force on the object's surface. This action can be modeled in three ways: i) punctual and frictionless contact, ii) punctual and frictional contact, iii) soft contact. We assume that, in micro-scale, the applied forces can be modeled using the punctual frictional model. and thus using the Coulomb law. This means that, no slippage happens as far as the applied force lies in a three dimensions cone:

f 2 t 1 + f 2 t 2 ≤ µ f n (1)
where f t 1 and f t 2 are tangential components of the force, f n is the normal component and µ is the friction coefficient.

f n f c f po

Non-sticky contact

Sticky contact

f t
Friction cone limits Friction cone limits

f c f n f t
Fig. 2: Impact of pull-off force on the friction cone.

In the case of micro-manipulation, this contact law is slightly modified. Indeed, adhesion acts as an attractive force ( f po ) between the finger and the manipulated object. This force, called pull-off force, represents the force required to detach the finger from the object. In presence of this force, the Coulomb law can be rewritten as follows:

f 2 t 1 + f 2 t 2 ≤ µ( f n + f po ) (2)
The effect of this attractive force on the slippage limit condition is that the friction cone is shifted as depicted in Fig. 2. In addition, contrary to the macro-scale, where only positive grasping forces can be applied (push the object), in micro-scale, it is possible to apply negative forces (pull the object) as long as the force lies in the modified friction cone.

B. Equilibrium

During all the manipulation process, the object must be in equilibrium. A N fingers grasp is in static equilibrium if and only if the following equation is satisfied:

-w ext = G. f c = N ∑ i=1 w c i (3)
where w ext is the external wrench (force and torque) applied to the object, the matrix G ∈ ℜ 6×3N is called the grasp matrix [START_REF] Bicchi | On the closure properties of robotic grasping[END_REF] which depends on the contact positions, f c ∈ ℜ 3N is the vector containing the N grasping forces and w c i ∈ ℜ 6 is the i th grasping wrench. Given a set of contact points, the equilibrium problem consists in finding a set of grasping forces f c which verify equation (3) and the non-slippage constraint defined by [START_REF] Li | On motion planning for dexterous manipulation. i) the problem formulation[END_REF]. This problem can be rewritten using the limits of the friction cones. Indeed, the grasping wrench w c i applied at the i th contact point is a linear combination of wrenches that approximate the cone:

   w c i = ∑ j α i, j .w l j ,i + β i .w po i α i, j ≥ 0 1 ≥ β i ≥ 0 (4)
where w l j ,i is one wrench that approximate the i th friction cone, w po i is the wrench induced by pull-off forces (sticking effect), and α i, j and β i are coefficients that must be positive to stay inside the friction cone. Note that in macro-manipulation, w po i = 0. Then, the equilibrium problem of an N fingers grasp (3) can be rewritten as a function of the N friction cones wrenches:

     -w ext = ∑ N i=1 w c i = ∑ N i=1 ∑ j α i, j .w l j ,i + β i .w po i α i, j ≥ 0 1 ≥ β i ≥ 0 (5)
Thus, the equilibrium problem is equivalent to finding a set of positive coefficients (α i, j , β i ) (not all of them null) verifying the previous equation. The equilibrium property can be characterized using the convex hull formed by the friction cones wrenches (w l j ,i ). Indeed, it has been proven in [START_REF] Ponce | On computing three-finger force-closure grasp of polygonal objects[END_REF] that, without external perturbation and any adhesion forces, if this convex hull contains the origin of the wrench space, then a solution to the equilibrium problem exists (as depicted in Fig. 3). In fact, the grasp can exert all the wrenches that lie inside the convex hull. When the pull-off forces exist, the convex hull is formed by the friction cones wrenches (w l j ,i ) and the adhesion wrenches (w po i ).

Since inertial forces of micro-objects are negligible, the manipulation process is a succession of static equilibrium states that are verified along the manipulation trajectory.

f x f y m z w l 1 ,1 w l 1 ,2 w l 1 ,3 w l 2 ,3 w l 2 ,1 w l 2 ,2
Fig. 3: Representation of a convex hull formed by three nonsticky fingers for a planar problem (six wrenches with three coordinates). The origin is included in this envelop thus the grasp is stable.

C. Pull-off Forces and Finger Gaiting

During finger gaiting (i.e. detaching a finger from the object and eventually repositioning it), the pull-off force between the fingers and the object has an important impact. Indeed, when re-grasping, the finger pull the object with a measured value w po . This pull-off force may disturb the grasping equilibrium. In other words, the remaining grasping fingers must compensate for the pull-off force caused by the removed finger to guarantee the object's stability. This can be formalized as follows:

-w ext -w po = G. f c = N-1 ∑ i=1 w c i , (6)
where w po is the wrench induced by the release of the N th contact. Considering ( 6), the re-grasping problem consists in finding positive (α i, j , β i ) verifying the following equation:

     -w ext -w po = ∑ N-1 i=1 w c i = ∑ N-1 i=1 ∑ j α i, j .w l j ,i + β i .w po i α i, j ≥ 0 1 ≥ β i ≥ 0 (7)
Similarly to the equilibrium problem, it is possible to use the convex hull formed by the N -1 remaining fingers to test if the grasp is stable during finger gaiting. In this case, if the external perturbation (-w ext -w po ) is included in the hull, then the grasp is stable.

The next section introduces a trajectory planer for dexterous manipulation which fulfills the constraints ( 5) and ( 7)

IV. MANIPULATION PLANNING

We assume that the manipulation is performed using cylindrical fingers and that the geometry of the object is known, meaning that the object's surface is represented by a discrete regular sampling. We propose to generate the finger trajectories based on a two steps method. Given an object shape and the number of fingers of the manipulation system, the first step of the trajectory generation consists in computing the set of all stable grasps and admissible finger gaiting configurations. This step can be achieved off-line and is done only once for a given object. The second step consists in navigating between these configurations to define a path from the initial configuration to the desired one. The maps representing the set of equilibrium grasps during the different steps of the manipulation process are obtained by testing, for every grasping configuration, if the convex hull formed by the friction cones wrenches (w l i, j and w po i ) contains the zero wrench. When external perturbations are considered, the existence of a solution, (α i, j ,β i ) respecting ( 5), consists in testing if the convex hull contains the external wrench. Thus, the equilibrium map, corresponding to the stable N-fingers grasps, can be formalized as:

A. Equilibrium and Re-Grasping Maps

M N = c = (c 1 , .., c N ) ∈ ℜ (3×N) | (8)
-w ext ∈ Convhull(w l 1 ,1 , ..., w l j ,N , w po 1 , ...,

w po N ) ,
where c is a vector containing the contact coordinates on the object surface and Convhull(w l 1 ,1 , ..., w l j ,N , w po 1 , ..., w po N ) represents the convex hull. Fig. 4 depicts the M 2 map in the case of a cylindrical object without external forces (w ext = 0). We chose to use the curvilinear abscissa as coordinates of the contact point in order to better illustrate the maps. The colored areas on the left figure represent the equilibrium configurations for a two fingers grasp, without any pull-off forces. Since permuting the two contact points leads to the same grasp, the equilibrium map shows a symmetry axis. Physically, the strip's width depends on the angular aperture of the friction cone.

In finger gaiting, to guarantee that a given finger i can be pulled-off from the object without disturbing the grasp, we ensure that the resulting wrench w po i , induced by the pulloff force f po i , is included in the convex hull formed by the friction cones' wrenches of the N -1 remaining contacts. The re-grasping map, corresponding to the detachment of the i th finger in an N-fingers grasp, can be formalized as follows:

D N i = c = (c 1 , .., c i , .., c N ) ∈ ℜ (3×N | (c 1 , .., c i-1 , c i+1 , (9)
..,

c N ) ∈ M N-1 , -w ext -w po,i ∈ Convhull(w l 1 ,1 , .., w l j ,i-1 ,
w l j ,i+1 , .., w l j ,N , w po 1 , .., w po i-1 , w po i+1 , .., w po N ) .

Similarly to the equilibrium maps, permuting the contact points leads to the same grasp thus the re-grasping map corresponding to the detachment of a finger are simply noted D N with N ≥ 2.

Fig. 5 (left) shows all the re-grasping configurations for an assigned location of the removed contact in the case of a three fingers grasp (fingers are sticky). For instance, in the configuration represented in Fig. 5 (right), removing finger 3 would disturb the grasp's equilibrium. In addition, when the pull-off force between the object and the substrate is not negligible, we have to consider a third set of grasps that represents the initial grasps enabling to detach the object from the substrate (resist to the external wrench w po,sub induced by the substrate) and stably pick-up the object. This can be formalized as follows:

I N = c = (c 1 , .., c N ) ∈ ℜ (3×N) | (c 1 , .., c N ) ∈ M N , (10)
-w extw po,sub ∈ Convhull w l 1,1 , ..., w l N, j , w po 1 , ..., w po N .

These I N maps are very similar to the previous maps but are just used to select the admissible initial grasp when the substrate is sticky.

B. Planning Object Rotation

1) Representation: Considering a discrete regular representation of the object, all the equilibrium maps M k (1 < k < N) can be seen as a graph where every equilibrium position is a node. The goal is to navigate inside and between the maps to reach the desired object pose. In fact, navigating through a M k map describes the manipulation of the object with rolling contacts whereas navigating between two maps (M k and M k±1 ) characterizes re-grasping. In this case, the regrasping maps D k are also part of the graph. Each node in D k is specifically used to link two adjacent sets (M k and M k-1 ) when a finger is removed. Conversely, as adhesion does not perturb the grasp when adding a finger, the link from M k to M k+1 is systematically established.

2) Navigation Constraints: Three constraints must be taken into account when navigating inside and between the maps. The first one is the rolling constraint and thus the navigation in the M k maps. Indeed, in order to manipulate an object with N fingers considering rolling without sliding, all the fingers must roll the same distance and in the same direction on the object surface. Consequently, the rolling constraint induces a unique available path in a M k map (depending on the radius of the fingers). Thus, each node in M k has a maximum of two neighbors in the same map. As an example, we consider the map and the grasp depicted in Fig4. The grasp corresponds to the element M 2 (160, 65) in which the fingers have the same radius. Thus, the neighbors of this grasp are M 2 (160 + δ, 65 + δ) and M 2 (160δ, 65δ) (with δ representing the step of the discrete representation). Indeed, for a clockwise rotation the next grasp will be M 2 (160δ, 65δ) otherwise the next grasp will be M 2 (160 + δ, 65 + δ).

The second constraint is related to removing a finger. In this case, a node A in M k is linked to a maximum of k elements in M k-1 corresponding to the possible removal of each of the k fingers. For instance, when changing from a three fingers grasp to a two fingers grasp, a maximum of three neighbors are possible. However, this link is established only if the finger can be removed meaning that node A is in D k . In other words,

a node A in M k is linked to a node B in M k-1 if and only if A is included in D k and if the k -1 fingers used in B are also used in A.
The last constraint deals with adding a finger. To switch from M k to M k+1 , it is required that the k fingers used to form the grasp in M k are also used in the grasp with k + 1 fingers (obviously at the same position on the object surface).

The collisions between the fingers are also tested in order to guarantee that the generated trajectory is reachable by the manipulator. In addition, the fingers cannot have two contact points or more with the object's surface. Thus, depending on the object geometry and on the finger radius, some nodes in M k and D k are discarded. Moreover, in the case of polygonal objects, we consider that the fingers cannot be positioned on the vertices.

3) Trajectory Generation: This operation consists in navigating in the generated maps using the A * algorithm. This heuristic graph search algorithm provides a complete and optimal path between the initial and the goal node. A * has been used in micro-manipulation [START_REF] Wu | Force and motion analysis for automated cell transportation with optical tweezers[END_REF] and also in micro-assembly [START_REF] Cappelleri | Caging micromanipulation for automated microassembly[END_REF] but, based on our knowledge, it has never been used for planning in-hand micro-manipulations. We chose to implement an A * algorithm for our trajectory planner in order to obtain optimal manipulation trajectories.

4) Algorithm Characteristics: An important parameter of the graph search is the cost function used to characterize the distance between two nodes. Considering the way we can navigate through the graph, we define three cost functions corresponding to the three possible actions (rolling, placing a finger on the object, removing a finger).

For the first case (rolling), the cost function is defined as the rolling distance needed to go from the current node to the next one. This distance is the arc length between two adjacent positions on the object surface and is noted L roll .

As the fingers might be compliant, the fingers base displacement achieved by the actuator to detach the object from the object depends of the finger stiffness, its length and its radius. The cost, C r , for detaching a finger from the object corresponds to the minimal distance applied by the actuator to guarantee that the finger is detached from the object.

For the last action (adding a finger), the cost, C a , corresponds to an approximation of the distance between the last position of the finger and the new one. This value represents an approximation of the distance required to put in contact the finger with the object.

Moreover, the A * algorithm requires defining an admissible heuristic. The heuristic is defined as the remaining rotation from the current node to the desired one. Moreover, as rolling is used to rotate the object, the heuristic can be defined as a distance. Indeed, considering that the finger used for the manipulation has a radius r d and that rot is the rotation amplitude in radians, the heuristic will be d rot = r d .rot at the initial node. Obviously this heuristic never overestimates the distance to the goal so it is an admissible heuristic for the considered costs.

C. Planning Finger Gaiting

Planning fingers trajectories during finger gaiting can be achieved using the same algorithm presented above (A * ). Indeed, in this case, the nodes correspond to the spatial coordinates and the algorithm must find a path between the initial finger position and the new desired position by avoiding collisions with the object and the other fingers.

1) Displacement Process: Three displacement processes are considered: (i) remove a finger, (ii) place a finger and (iii) change the contact position of a finger.

As depicted in Fig. 6, the release of a finger must be divided into two phases. The first one, which is the most critical, consists in precisely detach the finger from the object. Considering that P c is the coordinates of the finger when it is in contact with the object, the first step consists in moving from P c to a new position P a,c which corresponds to a position where the finger is clearly detached from the object. Thus, we arbitrarily chose to locate this new position at a distance of 2 × r d along the normal of the contact point (P a,c = P c -2 × r d -→ N c where -→ N c is the normal to the object at the contact point). Obviously, this position depends on the finger's characteristics such as stiffness and length. The second phase consists in reaching the initial position P 0 by moving freely in the space.

Similarly, placing a finger is divided into two phases. The first step consists in moving freely in the space from P 0 to a position near the new contact P a,c . Then, the second step, consists in moving along the contact's normal to precisely place the finger on the object.

In order to change the contact position, the finger must be detached from the current contact position P c 1 by moving to P a,c 1 . Then the finger moves freely from P a,c 1 to a position near the new contact P a,c 2 . Finally, the finger is placed on the object by moving from P a,c 2 to the contact position P c 2 . Fig. 6: Illustration of the three displacement process used for a finger gaiting step. Left images describe the initial state while right images represent the final state and an example of trajectory. The depicted trajectories are not the optimal trajectories.

2) Algorithm Characteristics: For these trajectories, there is only one cost function linked to the displacement of the finger in the space. Thus this displacement is evaluated by using the Euclidean distance between two points.

Moreover, the heuristic is chosen as the Euclidean distance between the current position and the goal position. Again, this heuristic never overestimates the distance to the goal so it is an admissible heuristic for the considered cost function.

V. RESULTS

The methodology presented in the previous section has been implemented and tested to generate trajectories for planar manipulation. In fact, in micro-assembly, most of the objects made using micro-fabrication techniques are planar. The results presented in this section are thus applicable in microassembly.

The results below present trajectories for two types of objects (arbitrary shaped and polygonal) and in two different conditions of manipulation (with and without sticky fingers). Note that every initial grasp is taken randomly in the set of admissible initial grasps. Furthermore, different finger's bases are tested to highlight the fact that our algorithm is suitable for several planar manipulation setups.

Moreover, the translation of the object is simply performed by the translation of all the fingers which does not affect the stability of the grasp. Thus, we will focus in this study on the rotations.

A. Sticky Fingers

These simulations focus on illustrating the trajectory generation when considering sticky fingers. We consider the manipulation with a three fingers hand where each finger can translate in the plan. This means that all the possible grasps and in-hand manipulation are represented by three maps: M 1 , M 2 , M 3 . Two maps (D 2 and D 3 ) are used for re-grasping and finger gaiting.

In these study cases, we consider the following cost functions: C a = 150µm, C a r = 8µm and C r = 10µm.

1) Arbitrary Shaped Object: Fig. 7 illustrates the computed trajectory for a 132 • rotation using fingers with a radius of 5µm. By choosing a suitable substrate material the pull-off force between the object and the substrate can be neglected. The pull-off force between fingers and the object and the friction coefficient are respectively estimated at 0.6µN and 0.3. The weight of the object is neglected which means that the external wrench is null (w ext = 0). In this setup, we consider that the fingers are attached to a rectangular moving base.

Fig. 7a represents the initial grasping configuration used to pick-up the object while Fig. 7b to Fig. 7f show the rotation. As depicted in Fig. 7e, the top finger is removed to avoid multiple contact between the object and the finger. This manipulation sequence, which is stable thanks to the adhesion, cannot be reproduced without adhesion (see Fig. 7b for example).

2) Polygonal Object: The generated trajectories for a polygonal object are described in Fig. 8. This 206 • rotation has been done considering finger with a radius of 5µm, a negligible pull-off force between the object and the substrate and a pull-off force between the object and the fingers of 1.5µN. The friction coefficient is again taken constant (0.26) and the object's weight is again neglected. In this setup, we consider that the fingers are attached to triangular base as shown in Fig. 1. In this case, the manipulation process requires no finger gaiting steps. Thanks to adhesion properties, this high rotation amplitude can be performed using only two fingers. Obviously, these manipulation trajectories are not stable without using sticky fingers.

B. Non-sticky Fingers

In order to illustrate the impact of adhesion on the fingers' trajectories, we consider the same simulation but without any pull-off forces ( f po ) between fingers and the object.

1) Arbitrary Shaped Object: Fig. 9 illustrates the computed trajectory for a 132 2) Polygonal Object: As in the previous case, a 206 • rotation of the polygonal object is performed (see Fig. 10). As with the arbitrary object, the manipulation without sticky finger is slower than the manipulation with sticky fingers. Indeed, some finger repositioning occurs as depicted in Fig. 10c

C. Impact of Adhesion Forces on Manipulation 1) Impact of the presence of adhesion forces:

The differences between the trajectories with and without sticky fingers are due to the stabilizing effect of the adhesion forces. Fig. 11 shows this effect on the M 2 map of the arbitrary shaped object presented in Fig. 7 and Fig. 9. The blue and yellow areas correspond respectively to the M 2 maps with and without the stickiness effect. As predicted, the stability area is significantly larger when pull-off forces are considered. This means that there are more options to manipulate the object in presence of adhesion forces.

Moreover, Fig. 12 represents similar results for a re-grasping map in D 3 . It can be seen that, without adhesion, 100% of the equilibrium nodes in M 2 (yellow part in Fig. 11) are stable re-grasping nodes in D 3 (yellow part in Fig. 12). Conversely, with sticky fingers, the admissible re-grasping nodes (blue part in Fig. 12) represent only around 18% of the equilibrium nodes (blue part in Fig. 11). This difference is due to the fact that adhesion which acts as a stabilizing force acts also as a disturbing force when a finger is detached from the object. The (two) remaining fingers must resist to this force which is not possible in all the equilibrium grasps. andg). In the first step the re-grasping is done to pass through the friction cone's limits while for the others the re-grasping is done to avoid vertices. Fig. 10: Images sequence describing the trajectory generated by the planner for a 206 • rotation with non-sticky fingers on a polygonal object: a) represents the initial grasping configuration while b), d), f) represent the rotation steps. Two finger gaiting steps occur in c) and e). In the first case the re-grasping is done to pass through the friction cone's limits while for the second case, the re-grasping is done to avoid the vertex.

2) Impact of the strength of adhesion forces: The presence of adhesion has a strong impact on the trajectories and on the maps but it is important to also evaluate the impact of its strength. Indeed, in the previous examples, various adhesion forces have been used (0.6 µN in Fig. 7 and1.5µN in Fig. 8).

In fact, whether for an adhesion value of 0.5µN, 5µN or 10µN, the maps (equilibrium and re-grasping) are identical as long as the adhesion strength is predominant over the external wrenches. This means that the value of this parameter will have no impact on the stable grasps (maps) and thus on the generated trajectories. For the remaining of this paper, we assume that the external forces are always negligible compared to adhesion forces. More details on this topic can be found in [START_REF] Seon | On the Contribution of Adhesion and Friction in Planning Dexterous in-Hand Micromanipulation[END_REF].

D. Sticky Fingers vs Non-Sticky Fingers

The previous trajectories seem to be more efficient when adhesion forces are exploited. Indeed, on the arbitrary shaped object and on the polygon, the trajectories require less finger gaiting steps and also less displacements of the fingers. A statistical analysis has been done to confirm that manipulation exploiting adhesion forces are better. Trajectories were generated with and without sticky fingers for the two objects presented above and with the same simulation parameters. In every test, the initial grasping configuration is chosen randomly in the admissible initial grasps using two fingers. Moreover, note that with random initial grasp, it is possible that the algorithm does not converge to the desired rotation.

We chose to consider two values to evaluate the performance. The first one is the cost of the computed trajectory based on the cost function described in the previous section. This value estimates the distance traveled by the fingers during the manipulation and is equivalent to the trajectories' 1) Arbitrary Shaped Object: Fig. 13 shows the statistical results for the arbitrary shaped object. For each rotation amplitude (45 • , 90 • , 135 • , 180 • ), fifty rotations were generated. It can be seen that, whatever the rotation, the trajectories generated with sticky fingers have an average cost lower than the one generated with non-sticky fingers. This means that less finger gaiting steps are required and that the manipulation process is faster when taking advantage of adhesion forces. Indeed, with sticky fingers, the manipulation of this object is around 40% faster.

In the case of non-sticky finger, the convergence rate varies from 66% to 90% with the highest percentage for the lowest rotation amplitudes. This low convergence rate can be explained by the fact that the hand has only three fingers. Indeed, the re-grasping can occur if and only if two of the three fingers can grasp the object which is very dependent on the object's shape. The convergence rate increase to 95% in the case of sticky fingers. Therefore, it appears simpler to find an admissible trajectory when adhesion is considered.

2) Polygonal Object: Similar tests have been performed on the polygonal object and the statistical results are depicted in Fig. 14. Once again when using sticky fingers, the manipulation is about 35% faster.

Moreover, the convergence rate varies from 68% to 84% for non-sticky fingers whereas the convergence rate is always higher than 90% with sticky fingers.

E. Proof of Concept at Millimeter Scale

In order to validate this new manipulation strategies, the proposed trajectories exploiting adhesion forces have been tested experimentally. A typical trajectory that does not exploit adhesion forces can be viewed in Fig. 1. Fig. 15: Photography of the experimental set-up. On this setup, each finger can be attached on a triangular base or on a rectangular base.

1) Experimental Set-up:

The experimental set-up (Fig. 15) consists of three cylindrical fingers of 1mm diameter made of steel, each one mounted on a 2 Degrees of Freedom translation table. Each table is actuated using 2 Smaract R SLC-1730 piezoelectric actuators with a repeatability of 1.5µm. The scene is observed using two high resolution (2560 2018 pixels) cameras from JAI R .

The manipulated objects are made of acrylic and have the following dimensions: 6mm long and 4mm tall for the object depicted in Fig. 16 and 4mm long and 4.5mm tall for the object depicted in Fig. 18.

As this experimental setup is at millimeter scale, so adhesion forces are not predominant. Thus to exhibit the behavior that is encountered in micro-scale, a polymer was deposited on the fingers to enhance the adhesion forces. It generates a behavior which is not identical to the micro-scale behavior but almost similar. Moreover, in the Section V-C, we highlight that the adhesion strength has no impact on the stable grasps and finger gaiting configurations. Thus, even if this polymer does not accurately mimic the micro-world, it is sufficient to fall back to micro-scale specificity where adhesion forces are predominant over other external forces.

The trajectories being generated in the object frame and executed without feedback, the manipulation system must be well calibrated. Thus the homography between the camera frame, the object frame and the actuators frame are computed. Thanks to these homography matrices the computed trajectory for each finger is converted in the actuators frame and executed.

2) Experimental Validation: The trajectories presented previously have been tested on the experimental set-up. Fig. 16 represents an images sequence which shows the achievement of the 132 • rotation for the arbitrary shaped object. It can be seen that this manipulation process is successfully executed. The reference trajectory and the real one obtained using the ESM visual tracking algorithm [START_REF] Benhimane | Homography-based 2d visual tracking and servoing[END_REF] are shown in Fig. 17. It can be noticed that the angle of the manipulated object reaches 129.64 • which represents an error of 1.79%. We can see from the same figure the evolution of the position of the manipulated object during the manipulation. The experiment has been reproduced with the polygonal object. The experimental results are displayed in Fig. 18. Again, it can be seen that the desired motion is successfully achieved thanks to the sticky fingers. The differences between the computed trajectory and the real one are shown in Fig. 19.

The rotation angle of the manipulated object reached in this case 199.25 • resulting in an error of 3.6%

In both cases, the errors can be explained by the fact that the finger and the object characteristics (dimension, stiffness, ect.) are not perfectly known. Nevertheless, these errors can be reduced using a classical visual feedback control.

Moreover, it is interesting to note that the trajectories used to moved the object depicted in Fig. 18 were generated for a planar object (as depicted in Fig. 8). However, the real object have a shape similar to the LEGO's shape (a square with a cylinder on the top). This means that it is possible to manipulate more complex objects as far as the contact points have the same profile.

VI. DISCUSSION

A. Trajectory optimization

In the trajectories presented above, the initial grasp was selected randomly among all the possible stable grasps. This means that the optimization performed by the planner is constrained by this initial choice which is unlikely the most optimal. Although, it is theoretically possible to generate the manipulation trajectories for all the possible grasps and select the best one. However, the additional computation time has to be shorter than the time saved in the optimal trajectory execution, which is not the case yet. To do so, the generation time of the initial grasp and manipulation trajectories has to be optimized.

B. Planar manipulation

The problem of dexterous manipulation using adhesion forces has been formalized. However, the algorithm was developed and the data were generated for planar manipulation. One possible approach to extend the proposed method to 3D manipulation is to perform successive 2D rotations. In this case, the fingers shape has to be modified (sphere, probes, etc...) since cylinders would not be suitable. If the contacts rolling is not negligible as it was the case in this paper then the nonholonomic constraint has to be taken into account.

C. Adhesion forces and friction coefficient

The proposed approach relies on three assumptions: the existence of adhesion forces, an estimation of the adhesion strength and an estimation of the friction coefficient.

As shown in [START_REF] Seon | On the Contribution of Adhesion and Friction in Planning Dexterous in-Hand Micromanipulation[END_REF], as long as the adhesion force is predominant compared to external forces, finger trajectories are identical whatever the adhesion strength is.

Moreover, it is well admitted by the micro-manipulation and micro-assembly community that adhesion forces exist and are predominant in the micro-scale. The trend for the last two decades was to try to get rid of these forces. Since our new paradigm was to take advantage of these forces, if these forces are not strong enough to be exploited, specific chemical treatments can be applied to enhance the adhesion forces [START_REF] Cot | Modeling of electrostatic forces induced by chemical surface functionalisation for microrobotics applications[END_REF]. Thus, the uncertainty on adhesion forces can be handle by making sure that they are the predominant forces. In addition, it is also possible to plan the trajectories considering a worst case scenario: the rotation are planed considering that each finger is sticky and the re-grasping are planned considering that only the removed finger is sticky. This will force the algorithm to only use a subset of the D maps.

Another precaution can be taken regarding the friction coefficient. Indeed, in this paper various friction coefficient have been used (0.3 and 0.26). In fact, we chose to take these values to be sure that we never overestimate the friction coefficient. Indeed, never overestimating the friction coefficient ensures that the algorithm will never use a re-grasping node that may lead to instability. We have measured a friction coefficient around 0.7 between the object (made of acrylic) and the fingers (made of steel). Thus the chosen values are acceptable.

D. Releasing task

In this paper, we have not studied the releasing task of the micro-objects. In fact, previous works in the literature tried to solve this issue. One interesting way to perform this releasing task is to use the dynamics of the micro-manipulator to overcome the adhesion forces [33] [34]. However, in most industrial micro-assembly tasks, the manipulated object is inserted, welded or glued with another part [START_REF] Gauthier | Industrial Tools for Micromanipulation[END_REF]. In these cases, the adhesion forces between the two parts is higher than the adhesion between the fingers and the object meaning that the releasing can be done easily.

E. Macro-manipulation

Even if the context of this study was micro-manipulation and micro-assembly, it is possible to imagine extending these results to macro-manipulation. Indeed, the benefit of using sticky finger is independent from the manipulation scale. Thus, considering robotic hands with suction effect at the fingertips may improve the dexterity of the hand. Incidentally, this was a winning strategy during the Amazon Picking Challenge at ICRA 2015.

F. Industrial applications

The potential applications of this micro-manipulation approach are very large. Indeed, micro-manipulation techniques and more particularly dexterous micro-manipulation can find applications in various fields such as scientific instrumentation and manufacturing [START_REF] Gauthier | Industrial Tools for Micromanipulation[END_REF]. For example several applications in the watch industry require to precisely orientate micro parts to achieve the watch assembly. This is also useful in optics to assemble complex MOEMS (micro-opto-electro-mechanical systems) [START_REF] Rabenorosoa | Precise motion control of a piezoelectric microgripper for microspectrometer assembly[END_REF] or optical fibers [START_REF] Zhang | Monolithically integrated two-axis microgripper for polarization maintaining in optical fiber assembly[END_REF]. Moreover, some other applications can be found in the NOEMS (nano-opto-electromechanical systems) assembly and manipulation [START_REF] Shi | Recent advances in nanorobotic manipulation inside scanning electron microscopes[END_REF].

VII. CONCLUSION

In this paper, a trajectory planner for dexterous micromanipulation was presented. This planner is based on an A * graph search algorithm in order to generate optimal and complete trajectories that take into account the specificity of the micro-scale: the adhesion forces that predominate over gravitational and inertial forces.

The trajectories were validated experimentally and in simulation considering different conditions of use (sticky and non-sticky fingers) and on various object shapes (arbitrary and polygonal shape). These results show that in-hand micromanipulation using adhesion forces can significantly enhance dexterous in-hand manipulation. Thus original trajectories can be generated and executed with a relatively low error.

The next steps of this work will involve the validation of these new trajectories on an experimental micro-manipulation setup (Fig. 1). In addition, the current planner will be improved to automatically select the initial grasp to generate globally optimal dexterous in-hand manipulation trajectories and will be extended to non-planar objects. Visual feedback control will also be considered to compensate for the manipulation errors. Furthermore, taking into account the temporal aspect of the finger placement (especially during the initial grasp) will be investigated as well as different model of the contact finger-object.

Fig. 4 :

 4 Fig. 4: Representation of the set M 2 for a 2D object, without considering adhesion (non-sticky behavior, ∀i, w po i = 0).

Fig. 5 :

 5 Fig. 5: Right: representation of the set D 3 for an assigned location of the removed contact (curvilinear abscissa of finger 3: 80µm) considering adhesion (sticky behavior, ∀i, w po i = 0). Left: example of a configuration outside D 3 in which finger 3 cannot be removed.

Fig. 7 :

 7 Fig. 7: Images sequence describing the trajectory generated by the planner for a 132 • rotation with sticky fingers: a) represents the initial grasping configuration while b) to f) represent the rotation steps. A finger gaiting step occurs in e) to avoid multiple contact between the object and the finger.

  • rotation. Contrarily to the sticky case which required only one finger gaiting step, this rotation required three finger gaiting steps. Indeed, Fig 9c shows the first one where the right finger is added because the two other fingers have reach the limits of the friction cones. Then in Fig 9e the left finger is repositioned to avoid the vertices. Finally, in Fig 9g, the top finger is also removed to avoid the vertices. Thus, without sticky fingers, the same manipulation requires more steps to be achieved.

Fig. 8 :

 8 Fig. 8: Images sequence describing the trajectory generated by the planner for a 206 • rotation with sticky fingers on a polygonal object: a) represents the initial grasp. b) to f) show the rotation steps.

Fig. 9 :

 9 Fig.9: Images sequence describing the trajectory generated by the planner for a 132 • rotation with non-sticky fingers on an arbitrary shaped object: a) represents the initial grasping configuration while b), d), f) and h) represent the rotation steps. Three finger gaiting steps occur in c), e) and g). In the first step the re-grasping is done to pass through the friction cone's limits while for the others the re-grasping is done to avoid vertices.

Fig. 11 :

 11 Fig. 11: Representation of the set M 2 (equilibrium map) with and without pull-off forces on the tested object. Blue and yellow areas correspond respectively to the M 2 maps with and without sticky fingers.

Fig. 12 :

 12 Fig. 12: Representation of the set D 3 with and without pulloff forces on the arbitrary shaped object. Blue and yellow areas correspond respectively to the D 3 maps with and without sticky fingers.

Fig. 13 :

 13 Fig. 13: Chart representing the distribution of the average cost value for the arbitrary shaped object with and without sticky fingers. For each rotation amplitude and each case fifty rotations were generated. The cost value estimates the distance traveled by the fingers during the manipulation.

Fig. 14 :

 14 Fig. 14: Chart representing the distribution of the average cost value for the polygonal object with and without sticky fingers. For each rotation amplitude and each case fifty rotations were generated. The cost value estimates the distance traveled by the fingers during the manipulation.

Fig. 16 :

 16 Fig. 16: Image sequence captured during the experimental validation of a 132 • rotation: a) represents the initial grasping configuration while b) to f) represent the rotation steps. A finger gaiting step occurs in e) to avoid a multiple contact configuration between the object and the finger. Fingers are highlighted by the red circles.

Fig. 17 :

 17 Fig. 17: Representation of the position and orientation of the manipulated object during the experimental validation of the 132 • rotation. Left graphics compare the reference trajectory with the executed one. Right graphics show the various errors during the process.

Fig. 18 :

 18 Fig. 18: Image sequence captured during the experimental validation of a 206 • rotation: a) represents the initial grasping configuration while b) to f) represent the rotation steps. Fingers are highlighted by the red circles.

Fig. 19 :

 19 Fig. 19: Representation of the position and orientation of the manipulated object during the experimental validation of the 206 • rotation. Left graphics compare the reference trajectory with the executed one. Right graphics show the various errors during the process.

ACKNOWLEDGMENT This work was supported by ACTION, the French ANR Labex no. "ANR-11-LABX-01-01" (http://www.labex-action.fr), by the Equipex ROBOTEX project (contract "ANR-10-EQPX-44-01") and by the Conseil Régional de Franche-Comté.


Lina Aliouat
email: lina.aliouat@univ-fcomte.fr

Hakim Mabed
email: hmabed@femto-st.fr

Julien Bourgeois
email: julien.bourgeois@femto-st.fr

Flexible Multipoint-to-Multipoint Routing Protocol in Ultra-Dense Nanonetworks

Keywords: Terahertz nanonetwork, dense network, routing protocol, multipointto-multipoint routing

New applications in the field of radio networks require a high concentration of micro-machines (micro-robots, sensors/actuators) in a small space. Those devices are characterized by a high volatility and limited computing, storage and energy capabilities. Traditional routing approaches in ad hoc networks are unusable due to a significant amount of additional control traffic and a lack of robustness regarding the instability of the nodes. In this paper, we present an original, efficient and intuitive distributed routing protocol in ultra-dense terahertz networks, called Multipoint-to-Multipoint Routing Protocol (M2MRP), which is an emanation of electrostatic physics.

A complexity analysis is performed to compare the M2MRP protocol with classical methods. Our study shows that the proposed protocol takes advantage of the nodes density to define a robust routing policy with a moderate additional traffic control. In addition, routing paths are adapted gradually and continuously according to the nodes location (mobility), availability (failures), congestion and energy level.

Simulations show that the M2MRP routing protocol significantly outperforms the well-known routing protocols for dense networks both in terms of the number of exchanged messages and of success rate, making this routing protocol the most suitable for systems such as swarm micro-robots, programmable matter and ultra-dense sensor networks.

INTRODUCTION

During the last few years, there have been important advances in the field of radio devices manufacturing, both in terms of miniaturization (Micro-electro-mechanical systems (MEMS) and antennas) and cost reduction. These advances have opened the way to the design of systems where hundreds of thousands of radio nodes can co-exist in a reduced space. Foreseen applications include robotics swarms, programmable matter [START_REF] Mabed | Towards programmable material: Flexible distributed algorithm for modular robots shape-shifting[END_REF], massive multi-core processing [START_REF] Petrov | Terahertz band intrachip communications: Can wireless links scale modern x86 cpus?[END_REF], Wireless NanoSensor Network (WNSN) [START_REF] Upadhayay | Application of wireless nano sensor networks for wild lives[END_REF] and Wireless Body Access Network (WBAN) [START_REF] Negra | Wireless body area networks: Applications and technologies[END_REF]. In such systems, network densification helps increasing the accuracy of extracted information and efficiently covering an area.

Due to the limited energy capacity of the nodes and their high density, the radio range of each node is reduced. A communication between two distant nodes is then relayed by intermediate nodes.

The routing problem in ad hoc network is widely covered by the literature. Mainly, the classical routing approaches could be classified into proactive and reactive protocols [START_REF] Abdulghani | Overview of wireless mesh networks[END_REF]. In proactive protocols (OLSR [START_REF] Thomas Heide Clausen | Optimized link state routing protocol (olsr)[END_REF], Babel [START_REF] Garcia-Lunes-Aceves | Loop-free routing using diffusing computations[END_REF], DREAM [START_REF] Chlamtac | A distance routing effect algorithm for mobility (dream)[END_REF] and DSDV [START_REF] Narra | Destination-sequenced distance vector (dsdv) routing protocol implementation in ns-3[END_REF] ), each node computes and stores in advance the optimal paths or just the next node in this path, towards one, several or all nodes. These approaches suffer of lack of responsiveness in case of nodes failure requiring the path recalculation. In reactive protocols, such as AODV [START_REF] Singh | A survey: Ad-hoc on demand distance vector (aodv) protocol[END_REF], ABR[? ] and DSR[? ], the path followed by the communication data is computed in real-time by exchanging route requests (flooding mechanism), which leads to additional latency and additional control traffic. The flooding impact is accentuated by the high density of the network.

Recent few works on routing use the analogy between dense wireless network and physical phenomena such as the interaction of charged particles in electrostatics [START_REF] Kalantari | Routing in wireless ad hoc networks by analogy to electrostatic theory[END_REF] or molecules interaction in fluid substance [START_REF] Zhao | Performance analysis of fluid dynamics model based routing for sensor networks[END_REF]. Major of these works model the problem as a global optimization problem and assume the presence of a central unit with a global knowledge on the network state. Wei et al. [START_REF] Zhao | Performance analysis of fluid dynamics model based routing for sensor networks[END_REF] present a distributed routing protocol based of fluid dynamics. However, the protocol assumes that each node knows its coordinates and is able to determine the relative positions and distances of its neighbors.

In all the works cited above, a path or a route designates a list of nodes that defines a succession of Point-to-Point links. Due to the node volatility in ultra dense nanonetwork context, proactive point-to-point based routes are irrelevant, which means that only reactive approaches could be considered with point-to-point based routes.

New routing paradigm was proposed in [START_REF] Tsioliaridou | Corona: A coordinate and routing system for nanonetworks[END_REF] and [START_REF] Tsioliaridou | Stateless linear-path routing for 3d nanonetworks[END_REF]. These approaches are based on multipoint-to-multipoint paths and offer a more reliable connection especially under the high volatility context of nanonetworks. The data are transmitted from the source node to the destination node by crossing successive areas. At each hop, all the nodes of the current area re-transmit the packet to the next area and so on until the packet reaches the area containing the destination node. The successive areas passed through by the packet correspond to those located on the direct line between the source and the destination nodes. Therefore the protocol is not adapted to the case where the network nodes form a non-convex shape (see Figure 1).

CONTRIBUTIONS

In this paper, we propose a proactive multipoint-to-multipoint routing protocol (M2MRP) for ultra-dense nanonetworks with volatile nodes. The density of the network is exploited in order to increase the communication reliability. Packet routing follows a sequence of multi-point to multi-point links (see Figure 1), which offers a better protection against packet lost.

Unlike direct line routing protocols [START_REF] Tsioliaridou | Stateless linear-path routing for 3d nanonetworks[END_REF], the M2MRP uses adaptation mechanisms that allow to continuously adjust the circulation flows of data according to network deployment (mobility), nodes availability (curative adaptation) and energy state (preventive adaptation). This way, the adequacy of a node to serve as a relay point varies over time according to its energy state and the state of its neighboring nodes.

Additionally, unlike other methods, M2MRP uses the Terahertz beam steering technology [START_REF] Babakhani | A 77-ghz phased-array transceiver with on-chip antennas in silicon: Receiver and antennas[END_REF] to improve the spatial coverage of the nodes (the node radiates in a specific direction corresponding to the targeted reception nodes) leading to a more efficient use of energy, a better interference control and a reduction of short multiple reception loops (reception of the same packet several times). M2MRP allows every node to determine the best reception and transmission directions that optimize the circulation flow of traffic from any node to the sink nodes. Therefore, the flooding effect and the cumulative interferences are significantly reduced.

Every original received packet (received from a node situated in the reception direction) is just sent in the transmission direction without checking the sender or the destination identity. Finally, M2MRP protocol leads to an efficient use of wake-up receiver technology [START_REF] Demirkol | Wake-up receivers for wireless sensor networks: Benefits and challenges[END_REF], since the energy generated by transmitters is steered in one direction to activate only a part of the physical neighbors corresponding to the next hop nodes. This procedure provides a low-latency communication environment when nodes are activated just in time to receive a packet and to re-transmit it.

ROUTING PROBLEM DESCRIPTION 3.1 Multiple sinks problem

Routing problem in ad hoc networks with multiple sources and multiple destinations is a very frequent problem [START_REF] Ciciriello | Efficient routing from multiple sources to multiple sinks in wireless sensor networks[END_REF][START_REF] Viswanatha | On optimum communication cost for joint compression and dispersive information routing[END_REF]. This problem is particularly relevant in wireless nanosensor networks and nanonetworks. We consider here the case where source nodes can be any node in the network and sink nodes are particular nodes acting as gateways to the data processing unit. Sink nodes are particular because they are assumed not to be impacted by the volatility phenomena that affects ordinary nodes.

We assume that the ad hoc nanonetworks are sufficiently dense to allow an intensive coverage of the deployment area. This density is due to the miniaturization technologies such as graphene antenna [START_REF] Hadeel Elayan | On graphene-based thz plasmonic nano-antennas[END_REF] and MEMS components [START_REF] Veikko Lindroos | Handbook of Silicon Based MEMS Materials and Technologies[END_REF]. Terahertz band is then envisaged as an adequate radio environment to support communications between sub-millimeter devices.

Access protocol in terahertz nanonetwork

TS-OOK/PHLAME [START_REF] Capdevila | Phlame: A physical layer aware mac protocol for electromagnetic nanonetworks[END_REF] is one of the most promising Terahertz access protocol. TS-OOK/PHLAME is a pulse-based modulation protocol where every communication is encoded by a sequence of 0/1 symbols transmitted at regular intervals called Time symbol. The 1 symbol is sent as a electromagnetic pulse of a duration Tp (arround 100 femtosec) while a 0 symbol corresponds to a silence. The symbol rate (interval between two consecutive symbols) is notified by the sender during the communication announcement over the control channel.

The control channel is a carrier-less logical channel associated with the constant symbol rate Ts 0 . The receiver node listens to the control channel and extracts any sequence of symbols with a Ts 0 interval, in order to detect an announcement packet with an indication about the symbol rate of the data communication, Ts. Listening to the control channel costs in terms of energy and memory because detecting an announcement requires the storage and the processing of the received symbols. Therefore, the use of wake-up receivers [START_REF] Demirkol | Wake-up receivers for wireless sensor networks: Benefits and challenges[END_REF] is necessary in order to optimize the announcement detection procedure. A wake-up receiver is a radio technology providing a radio-on-demand connection where the nodes are activated just in time to receive the data.

The Multipoint-to-Multipoint Routing Protocol (M2MRP)

Under a context of high nodes volatility, the proactive point-topoint model is unreliable, i.e. with a high packet lost rate. While reactive protocols based on flooding processes lead to a high redundancy, interference and high energy consumption level as well as a high latency. The idea of the M2MRP protocol is to build a data circulation pattern that defines the paths followed by the date from any ordinary node to one of the sink nodes (see Figure 2). The circulation pattern of the traffic is modeled with a distributed data structure that locally associates with every ordinary node, two steering directions one for receiving and another one for sending data. At this stage of the work, we simply consider that the reception and transmission directions are opposite. To compute these lines of circulation flow, we were inspired by the electrostatic physics to determine how the nodes compute the best transmission direction (and not the best next hop node) to reach one of the sink nodes. Three main principles govern the behavior of the M2MRP protocol:

• the attractiveness effect: every node attracts all nodes within a given range. • the distance effect: the attraction level of a given node n on another one is proportional to the received signal power from the node n. • the attractiveness vector of a given node is the result of the attractiveness vectors of its direct neighbors and corresponds to the transmission direction of the node (i.e. the node's antenna radiates in this direction). The third principal means that the attractiveness vector of a given node is computed starting from the attractiveness vectors of its direct neighbors. Therefore, the attractiveness of each node impacts the attractiveness of farther nodes by the effect of intermediate nodes. The distributed propagation process leads to the formation of the circulation flow lines defining the data circulation paths from ordinary nodes to the sink nodes.

More formally, let N be a nanonetwork composed of a set of ordinary nodes, O and a set of sink nodes, S. Each node involves a directional antenna that can be steered in a direction d ∈ D with a fixed opening angle α. The M2MRP protocol proceeds by periodic updates of the circulation flows to reflect the evolution of nodes state: availability and energy level. In asynchronous way, each node proceeds per cycles (See Figure 3) called routing cycle. The routing cycle duration is 10 12 × Tp = 100ms and is subdivided into 1000 data cycles of a duration 10 9 × Tp = 0.1ms. The last data cycle is dedicated to the routing update procedure and forms the listening cycle. During the listening cycle, each ordinary node, o ∈ O, captures the control packets sent by the neighboring nodes (the antenna is used in omnidirectional mode). The control packets are particular packets with a specific signature and contain the attractiveness vector of the transmitter node and its energy level. The signal power of the received control packets and the attractiveness vectors of all neighbors are processed in order to determine the main sending Every 100ms, an ordinary node o updates its attractiveness vector using the received control packets during the listening cycle (0.1ms). Let V (o) the set of neighboring nodes of o. We notice pow (v, o) the power of the received signal from the node v at the node o. If o receives different control packets from the same neighbor v with different antenna directions, the strongest signal is then selected.

pow (v, o) = max-→ d ∈D pow (v, - → d , o) (1)
Let ---→ d (v) be the attractiveness vector of the node v sent in the last control packet of the node v.

The attractiveness vector of the node o can then be updated according to the expression 2. It should be noted that attractiveness vectors are normalized.

---→ d (o) = v ∈V (o) ---→ d (v) * pow (v, o) ---→ d (o) = ---→ d (o)/ ∥ ---→ d (o) ∥ (2)
However, equation 2 presents an important drawback because the weighted sum of neighbors attractiveness vectors may lead to an attractiveness vector oriented to low dense or even empty area as shown in the figure 4. The transmitted data sent from the node may not reach the sink nodes.

To overcome this problem, we propose another expression of the attractiveness computation, where the transmission direction or attractiveness vector, ---→ d (o), is computed by each node o as follow:

---→ d (o) = -→ d * ; ∀ - → d : P (o, -→ d * ) ≥ P (o, - → d )
with :

P (o, - → d ) = v ∈V (o) pow (v, o) × cos ( - → d , ---→ d (v)) × E (v) (3)
Where E (v) designates the current energy level of the neighboring node v and -→ d corresponds to the normalized vector which the direction d belongs to the set D.

The equation 3 guarantees that the resulting direction computed by the node o is the best regarding the concentration of the next hop nodes and their distance from the node o. The introduction of the energy level of the nodes gives a natural and efficient way

COMPLEXITY STUDY

In this section, we analyze a set of the major routing methods used in the literature. For this purpose, many criteria are considered:

Require: self : the node it self Ensure: ------→ d (sel f ) 1: while True do 2:
if the beginning of one of the |D| last packet cycles of the current data cycle then In Table 1, we give a comparison of the 5 studied methods according to the 7 criteria listed above. From the table, we deduce that the OLSR approach is very demanding for memory capacity (|V | 2 ), where |V | is the average number of neighbors. On the contrary, AODV presents a good memory complexity (|S | where S is the set of sinks) but since AODV is a reactive approach (on demand), the construction of the optimal path could take time (up to |E| messages where |E| is the number of pairs of neighbor nodes). In addition, AODV is a point-to-point approach, which represents a low reliability condition.

The naive broadcast approach guarantees the fastest transmission of data to the sink nodes but the number of sent and received messages is significant and leads to a high amount of energy consumption and a high interference level. The multi-relay approaches (M2MRP and SLR) generate less exchanged messages than the flooding methods. However, SLR method uses the coordinates of the source and sink nodes to determine the relay nodes (nodes in the zones crossed by the direct line between the source and destination nodes). Consequently, the efficiency of SLR approach depends on the average density of a zone Z (average number of nodes in one zone) and the geographical distance between the source and the destination nodes, r . Dense zones can lead to high level of exchanged messages while blank zones can lead to communication failures (see Figure 1, left part). Finally, M2MRP protocol is the only protocol that does not check the source of the message nor its final destination before relaying it, which represents a gain of time and energy.

M2MRP protocol is a distributed, robust and scalable protocol with a constant memory complexity on each node. Indeed, the at-

tractiveness vector of o, ---→ d (o)
, is obtained by computing, on each direction d ∈ D, the sum of the projections of neighboring attractiveness vectors and then to select the best direction (See Equation 3). Therefore, there is no need to store the attractiveness vectors of all the neighbors before computing the attractiveness vector. The time complexity for the calculation of the attractiveness vector of a given node is linearly correlated to the number of its neighboring nodes. In ultra dense nanonetworks, it is possible to vary the radio coverage range in order to adapt the number of considered neighbors. The amount of data diffused by each node at every data cycle (0.1ms) is too small making possible the continuous updating of the attractiveness vectors. Furthermore, the bad reception of the control packet of a given neighbor does not have enormous impact on the computed attractiveness vector.

TESTS AND RESULTS

Simulations and scenarios

For our experiments, we only compared the methods that meet the reliability criteria, thus node-to-node routing are ignored. In addition and regarding to its spatial complexity, the standard OLSR approach is considered not suitable for ultra dense nanonetworks. Therefore, three multiple relays to multiple relay protocols are compared: naive broadcast method, SLR and M2MRP. We run each protocol over 14 scenarios depicting two network topologies: the square topology and the bow tie topology (see Figure 5). In the square topology, the nodes of the network are uniformly distributed, while in bow tie topology the network forms a non convex shape similar to a bow tie.

All simulations are made by assuming a deployment zone of 100cm × 100cm and a radio coverage range of 20cm. We tested two versions of the M2MRP protocol using two different antenna radiation angles: 60 • and 120 • while the reception angle is fixed to 120 • and is at the opposite direction of the transmission direction defined by the attractiveness vector. The received power is computed as a function of the distance between the sender and the receiver nodes and decreases as the square of the distance between the nodes.

Visual results of M2MRP

In Figure 6, we display an example of the circulation flows produced by the M2MRP protocol on two different scenarios with two different topologies. Figure 6 shows that the data circulation flows fit well with nodes distribution. In particular, in the bow tie topology, the routes use the junction area to connect the left and the right parts of the network.

Energy level and congestion processing

As shown in equation 3, the energy level is a determinant factor of the attractiveness of a given node. When an area of the network is overloaded, energy level of its nodes becomes lower. Equation 3provides a solution to reduce the congestion over the concerned areas. The effect of energy level on the construction of the circulation flows is given in Figure 7. On the left, the shadowed square represents nodes where the energy level is much lower than the remaining network. On the right, the shadowed square contains nodes with ordinary energy level. We observe that, on the left, the circulation flows avoid the square area and route data traffic differently toward the sink nodes.

The adaptation of the distributed routing protocol to the nodes state evolution is of course not instantaneous but the propagation of the local information remains fairly fast due to the frequency of local updates (every 100ms). For instance, the distance of any two nodes is less than 10 hops, the attractiveness vector of a given node takes into account all the updates (energy and availability changes) occurred on the network in the last second.

Performance analysis

To assess the efficiency of Multipoint-to-Multipoint Routing Protocol (M2MRP), several densities of network are tested: 100, 200, 300, 400, 500, 750 and 1000 nodes. For each topology, the scenario with N nodes is composed of the same nodes (same coordinates) than the scenario with M (M < N ) nodes and N -M additional nodes. In addition, the simulated traffic (source of packets) is the same over all scenarios with the same topology. This way, we guarantee that protocols are tested under the same conditions and we can observe the effect of densification on the performances of the methods. The 14 scenarios use 3 sink nodes corresponding to the 10th, 20th and 30th nodes. To facilitate the reproduction of these scenarios, readers can use the Microsoft Excel VBA source code presented in: https://cloud.femto-st.fr/nextcloud/index.php/s/KwGaNaQndyPC7zf and just set the number of nodes. The choice of the Microsoft Excel VBA environment is justified by the need for rapid prototyping, accessible and ease of use environment where the interrelationships with the other networking layers (MAC and modulation protocols) are momentarily ignored. We give in https://cloud.femtost.fr/nextcloud/index.php/s/YACPHYXHf5Fftqr the source file of including the simulator of the different compared methods.

For every scenario, we evaluate the average number of exchanged messages needed for one hundred randomly selected nodes (sources) to send their data to a sink as well as the corresponding success rate (number of times where the sent packet reaches at least one sink). We compared the results of M2MRP with the massive broadcast and SLR methods. Results of Table 2 show that M2MRP and SLR reduce significantly the number of exchanged messages compared to the naive broadcast approach. In M2MRP, the reduction of the number of sent messages is improved when the transmission angle is reduced (60 • in place of 120 • ). It should be mentioned that the number of sent messages in the flooding approach is equal to the number of nodes minus the number of sink nodes under the assumption that all nodes are reachable. The performance of M2MRP and SLR are equivalent on the square topology scenarios in terms of the number of sent messages. However, when the density of the network is low, M2MRP presents a better reliability. M2MRP protocol outperforms by far the SLR method on the bow tie topology scenarios. Indeed, whatever the density of the network is, the SLR approach fails to exceed 80% of success rate, while M2MRP succeeds 91% of times even with 100 nodes. The results of the Table 2, show clearly the efficiency of our approach.

CONCLUSION AND PERSPECTIVES

In this paper we presented a new and efficient Multipoint-to-Multipoint Routing Protocol (M2MRP) for ultra-dense volatile nanonetworks. This protocol provides a powerful and scalable distributed procedure to dynamically and continuously compute the best transmission and reception directions of each node.

M2MRP protocol presents a natural way to express how the energy availability, congestion, radio quality and communication reliability should be taken into account for determining data routing paths over the network.

The simulation results are very encouraging and show great adaptability against network distribution and the comparison with SLR shows that M2MRP is clearly more efficient especially when the network topology presents non-convex parts.

The M2MRP protocol is implemented in AnyLogic Simulator and the source file can be found at: https://cloud.femto-st.fr/nextcloud/index.php/s/34WEmRWa8KB22G3 However the achieved simulations merits closer examination in a multilayer network simulator . Our current works include the implementation of the M2MRP protocol over Network Simulator NS3.

Furthermore, more tests need to be conducted in order to assess the performance of the protocol under different volatility situations and with a more realistic modeling of energy consumption. In addition, the protocol can be improved to reduce even more the

Figure 1 :

 1 Figure1: Comparison between direct line multipoint-tomultipoint approach (left) and M2MRP protocol (right). The surrounded node is a sink and the dark one is the source. The direct line approach fails to route the message until the sink node, whereas M2MRP approach succeeds.

Figure 2 :

 2 Figure 2: Data circulation pattern. Only the main transmission directions are depicted. The reception direction is either omni-directional or the opposite of the transmission direction.

  direction, ---→ d (o), of the node o. Ordinary communication cycles are subdivided into 1000 data packet cycles. The 1000 -|D| first packets are used to eventually send data packets in the main direction ---→ d (o) of the node. During the last |D| data packet cycles, the node sends |D| control packets each one in a different direction d ∈ D. Therefore, during the listening cycle, the node is ensured to detect all the control packets of its available neighbors in all directions.

Figure 3 :

 3 Figure 3: Routing cycle: every 100ms, the node recomputes its attractiveness vector (the transmission direction).

Figure 4 :

 4 Figure 4: Attractiveness vector obtained with equation 2: the reference node is surrounded by 6 neighbors with a sufficiently strong signal. The reference node computes the weighted sum (regarding the signal power) of the neighbors attractiveness vectors. In the example, the obtained vector is then badly oriented.

•

  packet containing ------→ d (sel f ) in one of the directions d ∈ D if during the last data cycle of the current routing cycle then 6: listen to all directions and compute the new ------→ d (sel f ) according to the received control packets (eq. 3) The spatial complexity of the protocol corresponds to the amount of stored data necessary for the protocol operation. • The routing efficiency corresponds to the time needed for transmitting the data from the source node to one of the sink nodes. This criteria allows to appreciate the quality of the routing path. • The communication complexity corresponds to the number of sent messages required to broadcast one message from a source node. This number gives an idea about the global amount of energy consumed. • Number of received messages that corresponds to the number of received messages by all nodes but not necessarily resent. The number of received messages impacts on the amount of generated interference. • Number of control messages corresponds to the number of exchanged messages before selecting the routing path. • The need for checking the source and the final destination nodes of the received messages allows to appreciate the additional delay and energy consumption required by the protocol.

Figure 5 :

 5 Figure 5: The two studied scenario topologies.

Figure 6 :

 6 Figure 6: Data circulation patterns obtained for two scenarios with two different topologies.

Method 1 :

 1 Complexity comparison of 5 major routing approaches. |N | is the number of nodes, |S | is the number of sinks, |D| is the number of antenna directions, r is the number of zones between the source and the destination nodes, Z is the size of a zone and |E| is the number of pairs of neighbors.

Figure 7 :

 7 Figure 7: Energy effect: The yellow square is an area with low energy nodes (on the left). The introduction of the energy allows to divert data flows from this area.

Table 2 :

 2 Complexity comparison of routing approaches according to the number of messages sent and the success rate. amount of exchanged messages, for example by delaying the retransmission of received packets and wait to see if other nodes, that have received the packet, transmit it.

				square topology					bow tie topology
	#nodes	100	200	300	400	500	750	1000	100	200	300	400	500	750	1000
	M2MRP(120•)	7,9	16,3	27,3	37,1	49,3	81,9 108,3	6,3	15	24,9	34,1	46,7	73,9 109,6
		93% 100% 100% 100% 100% 100% 100% 98% 100% 100% 100% 100% 100% 100%
	M2MRP(60•)	5	8,1	15,2	18,1	24,2	38	50,9	3,7	7,2	11,7	15,4	19,4	30,1	44,2
		76%	97%	99%	99% 100% 100% 100% 91%	94%	94%	96%	96%	96%	96%
	Flooding	95,1 193,1 294	393	497	739	997	94,1	195 291,1 393	497 724,6 987
		100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100%
	SLR	6,7	14,8	22,9	30,3	39,1	59,7	79,2	12,7	24,8	38,7	41,4	52	76,6	102
		79%	96% 100% 100% 100% 100% 100% 78%	78%	78%	79%	79%	79%	79%