Valeria Loscrì

Salvatore Guzzo Bonifacio

Nathalie Mitton

Simone Fiorenza

Valeria Loscrí

Associative Search Network for RSSI-based Target Localization in Unknown Environments

Keywords: ASN, Target Localization, RSSI

come   L'archive ouverte pluridisciplinaire

Introduction

In the recent years, research communities have focused and considered pervasive target localization [START_REF] Vempaty | Target Localization in Wireless Sensor Networks using Error Correcting Codes[END_REF] and cooperative target localization. Target localization can be also envisaged as a sub-problem of coverage of specific areas, where events of interest occur [START_REF] Loscrí | Performance Evaluation of Novel Distributed Coverage Techniques for Swarms of Flying Robots[END_REF], and where the correct and timely localization is mandatory. Among all the parameters that a wireless device (e.g. a robot) can measure, the Received Signal Strength Indicator (RSSI) is one of the most popular considered for target localization [START_REF] Gang | Sensor selection for target tracking in a wireless sensor network of bearing-only sensor[END_REF] [START_REF] Hamdoun | RSSI-based Localization Algorithms using Spatial Diversity in Wireless Sensor Networks[END_REF], above all in the context of Wireless Sensor Networks. Its popularity is due to different factors, such as it is always available between communicating devices, and it does not require extra-circuitry that would result in higher costs and energy consumption. Furthermore, the availability of the RSSI measure on all the devices, makes possible the implementation of a localization technique for heterogeneous nodes. This latter feature increases the potential scalability of this kind of approach, as envisaged in [START_REF] Zanca | Experimental comparison of RSSIbased localization algorithms for indoor wireless sensor networks[END_REF].

In this paper, we propose to exploit the RSSI parameter to localize a target in an unknown environment. The localization technique is based on an Associative Search Network (ASN) [START_REF] Barto | Associative Search Network: A Reinforcement Learning Associative Memory[END_REF] and is performed in indoor environments.

The network we implement on top of our robots is Hopfield-inspired [START_REF] Hopfield | Neural networks and physical systems with emergent collective computational abilities[END_REF] and we will show that it shares, with this type of system, the capability to converge towards stable states. By providing our robots with the learning capabilities, we make RSSI a viable solution for target localization. One of the main premises related with the system developed, is that the manipulation of the weights (in the weight matrix), that will constitute the basic for the direction decisions, is performed without any external oracle. This feature comes down to provide our devices with the possibility to dynamically adapt the weights without the intervention of an external central unit. In practice, the resulting system will be totally distributed and evolutionary by dynamically adapting its behavior to the external conditions. As a proof of concept of the proposed approach, we developed the whole ASN on Arduino-based mobile robots. These robotic platforms have been built from scratch and are totally reprogrammable. The brain of the robot is a mini-pc, where the algorithms have been implemented and run. Even if the robots are also able to communicate with each others, in this context, we have only used the communication paradigm to assign the task (i.e. the identity of the target to be localized). The Arduino module is mainly used to "transfer" the movement commands to the four wheels and to implement all the components related to the movement. In summary, the main contributions of the paper can be stated as follows:

-a new Received Signal Strength (RSSI)-based Associative Search Network (ASN) for target localization; -an ASN implementation on real hardware (Arduino-based robots) for evaluation purposes.

The rest of the paper is organized as follows. Section 3 browses the literature for the three macro topics tackled in this paper : a) Target Localization, b) Associative Search Networks and c) RSSI use in localization processes. In Section 4, we state the Associative Search Network problem (ASN) for target localization. Section 5 details our contribution. Section6 describes the scenario considered for evaluation purpose and the test-bed deployment. Section 7 gives the main features of the ASN implementation on robots. Finally, Section 8 concludes this work and explores future research paths.

The Associative Search Network Problem

In this section, we introduce the Associative Search Network Problem. We start by considering an Associative Search Network (ASN), that can be defined as a system where there is no outside process that suggests the correct association between a pattern with a key. Instead, for each key, the associative system searches for the pattern that minimizes a reinforcement signal (i.e. a payoff). The system is able to store, by the mean of an associative memory, the results of reinforcement feedback coming from the environment. In the ASN, is not considered at all the presence of a "oracle", that has to provide the pattern to be stored. This feature makes this system similar to an Hopfield-network [START_REF] Hopfield | Neural networks and physical systems with emergent collective computational abilities[END_REF]. Another important feature is that it does not require a priori knowledge about the best associations. ASN combines two learning methods that are usually considered separately. The first learning approach is based on a solution of a pattern recognition problem, by learning to respond to each key with the appropriate output pattern. The second type of learning, also used in the ASN, is based on stochastic automaton method to maximize a reinforcement signal or payoff [START_REF] Tsetlin | Automaton Theory and modeling of biological systems[END_REF] [START_REF] Narendra | Learning Automaton -A Survey[END_REF]. If we consider that the ASN interacts with an environment E, at each time unit t, E provides a context vector X(t) = (x 1 (t), x 2 (t), ..., x n (t)), where x i (t) is a positive real number and n is the number of inputs. E will also provide a payoff or reinforcement learning z(t). The ASN produces an output pattern y(t) = (y 1 (t), ....y m (t)), where m is the number of outputs, where each y i (t) ∈ {0, 1} and is received by E. In practice, the vector X(t) is to provide information about the environment to the ASN. Different contexts may require different actions from the ASN. As an example, we can consider a mobile device that is required to reach a specific target. The context is represented by an estimation of the distance. After a movement, a different context will require a different action, that could correspond to a request of changing direction (this is a different action required). The reinforcement signal is intended as a kind of evaluation of how much an action is appropriate in a certain context. A more appropriate formulation of the problem could be: let us assume that X(t) belongs to a finite set X = (X 1 , ...., X k ) of context vectors and let also assume that to each X α ∈ X corresponds a payoff or reinforcement function Z α . If E always evaluates an output vector in one time step and if X(t) = X α , then Z(t + 1) = Z α (Y (t)). This means that E provides a "training sequence" over X if it implements an infinite sequence of payoff functions and emits the corresponding sequence of context vectors X i1 , X i2 , ..., X il . Each X il ∈ X and each element of X occurs infinitely often. The termination condition of the associative search problem is solved when, after some finite portion of a training sequence, the ASN responds to each X α ∈ X with the output pattern Y α = (y α 1 , .....y α m ) which maximizes Z α . As outlined in [START_REF] Barto | Associative Search Network: A Reinforcement Learning Associative Memory[END_REF], the output vectors required from the system are only based on scalar feedback. Other mechanisms that are also able to solve similar problems, such as perceptrons based mechanisms [START_REF] Minsky | Perceptron: an introduction to computational geometry[END_REF], have some counterparts, e.g. they require a separate error feedback. The basic unit of an ASN is the adaptive element and in the simplest version, an ASN can be regarded as constituted by a single adaptive element. Let us indicate with x i , i = 1, ..., n the context input, z represents the payoff (or reinforcement signal) and y is the output. Every context input x i is associated with a weight w i (t) ∈ R. Let assume W (t) is the vector of weights at time t and s(t) is the weighted sum at time t of the contexts inputs. We obtain s(t) = n i=1 w i (t)x i (t) = W (t)X(t) and the output

y(t) is y(t) = sign(t) =      1 if s(t) + noise > 0, 0 if s(t) + noise = 0, -1 if s(t) + noise < 0. ( 1
)
where noise is a random variable with zero mean normal distribution. The element's output depends on the value s. If s is positive y(t) will be more likely 1, otherwise it will be more likely 0. The update of the weights is governed by the following equation, at each time step:

w i (t + 1) = w i (t) + c[z(t) -z(t -1)] [y(t -1) -y(t -2)]x i (t -1), i = 1, ..., n (2)
where c is a constant determining the learning rate. The more the value of n increases the more the accuracy increases too, but also the complexity will increase and, with it, the occupancy of the memory. In this equation, the response latency is considered equal to zero. It is worth noticing that, when the simplest ASN with only a single adaptive element is considered, the search of the optimal action is determined by two possible actions by the ASN. However, in a larger ASN (with more than 1 adaptive elements), the adaptive elements exploit their capability of operating in an effective way, with random payoff response characteristics. From 1, we can observe that the change of the payoff signal z is used by the adaptive element for determining weight changes. Of course, if the payoff (or reinforcement signal) changes at every time step and it does not vary smoothly over time, an adaptive element that implements the rules 1 and 2, is not capable to solve an associative search problem.

Related Work

The issue addressed in this paper is characterized by different properties, the target localization, the ASN and RSSI-based localization. Target Localization represents the main goal that the robot has to fulfill, the ASN is the main technique used in this work to reach the goal and the Received Strength Signal Indicator is the parameter used to obtain information from the surrounding environment. To the best of our knowledge, combining these three components is new. We thus briefly survey the literature for these three topics independently.

Target Localization A special category of target localization, named Anchor

Based considers a subset of nodes, placed in fixed coordinates, called Anchor Nodes. Through the exchange of messages among those nodes and a target, it is possible to estimate the position of the target inside the monitored area. Such a localization can have different purposes, like [START_REF] Priwgharm | Indoor Localization System using RSSI Measurement in Wireless Sensor Network based on ZigBee Standard[END_REF] where measured RSSI is used as parameter in maximum likelihood estimation algorithm. A more complex use of this technique can be found in [START_REF] Deshpande | Target Localization in Unknown Environments using Static Wireless Sensors and Mobile Robots[END_REF] where the RSSI is used to determine the position of a robot using a distributed algorithm and to direct it to follow a path. In [START_REF] Zhang | Range based target localization using a single mobile robot or multiple cooperative mobile robots[END_REF], the authors consider the target localization problem based on range measurement by considering a single mobile robot or several cooperating robots. Similarly to our approach, the authors consider that the robots do not have access to global knowledge about the environment. They do not know their current position, do not share a common sense of direction, etc. The robot is asked to estimate the relative coordinates of the target. Anyway, the approach they consider is totally different, since it is based on a specific filter.

In [START_REF] Dames | Cooperative Multi-Target Localization With Noisy Sensors[END_REF], the authors consider a set of mobile robots able to localize a set of unknown static targets within a known obstacle map. The robots use measurement Probability Hypothesis Density, or PHD, filter to collect the information for localization purpose. The authors do not make reference to RSSI as viable parameter to localize the targets. Moreover, the main difference is that the authors in [START_REF] Dames | Cooperative Multi-Target Localization With Noisy Sensors[END_REF] assume they know the obstacle map. In our case we introduce an explicit mechanism to detect and avoid the obstacles. The purpose is yet different and the aim is to use anchor nodes (if available), to help a robot in the localization process of an active target without a priori knowledge of the map, the geographic coordinates, etc. and without a oracle that manages the right weights associated with the weight matrix to compute the output.

Associative Search Network The Associative Search Network (ASN) has been introduced by Barto and Sutton [START_REF] Barto | Associative Search Network: A Reinforcement Learning Associative Memory[END_REF] as a learning process. The ASN interacts with an environment (E) receiving from it a feedback link. Through the analysis of this feedback and a reinforcement payoff signal the ASN is able to learn the best actions to perform in order to maximize the payoff function and reach a goal. This technique has been further analyzed in [START_REF] Bota | The Associative Search Network: Landmark Learning and Hill Climbing[END_REF], where the authors define a simulation environment to solve the practical problem called Hill Climbing. In the scenario depicted in this example a robot had to climb to the top of an hill where a tree is placed. The operation of the robot are assisted by the presence of some landmarks. Therein, the authors show how the presence of the landmarks and the use of ASN can improve the efficiency. The goal of our work was to replicate this scenario in a real environment, rather than a simulated one, to analyze the difference. We were mainly focused to identify the assumption that remains valid and the ones that is necessary to reduce when moving from a simulated scenario to a real one.

RSSI use in localization processes

The Received Signal Strength Indicator (RSSI) is often used as a parameter in target localization algorithms because of its relationship with the Path Loss Model, also known as Friis transmission equation [START_REF] Shaw | Radiometry and the Friis transmission equation[END_REF]. Thanks to this equation it is possible to calculate the power of a transmitted signal at a fixed distance d from the transmitter. It can be used as well to obtain the distance, from a transmission point, given the power of the received signal. The use of RSSI for distance estimation may present some drawbacks, especially for indoor localization, due to the presence of multi-path fading, shadowing and scattering which affects the transmitted signal as depicted in [START_REF] Heurtefeux | Is RSSI a Good Choice for Localization in Wireless Sensor Network?[END_REF]. Heurtefeux and Valois outline that the great popularity of localization protocols based on RSSI (in Wireless Sensor Networks) is mainly due to the fact that no extra hardware is required and the theory formulates the RSSI in terms of distance function, but the disadvantages can make its use for Localization Target purpose unfeasible. In [START_REF] Zhou | RSSI-based mobile robot navigation in grid-pattern wireless sensor network[END_REF], the authors show the effectiveness of a navigation technique based on RSSI. Similarly to our approach, the orientation adjustment and the motion tracking are performed through the help of other nodes (sensors nodes in their case). The main difference is that they consider sensors distributed in a grid pattern. We also make reference to landmarks that are arranged in the middle of the side of a rectangle, but our approach is able to dynamically adjust and learn about the landmarks even if they are arranged in different positions and are different in number.

Target localization problem statement

The main goal of this work is the target localization in an unknown environment, based on the Received Signal Strength Indicator (RSSI). We provide our robots with an ASN and formalize the Target Localization as an Associative Search Network problem. By the definition of the appropriate weights, the robot will move in a weighted space, instead of a physical space. This means that, the robots will perform a specific action based on the ASN implemented on them. We got inspiration from the work of Barto and Sutton [START_REF] Barto | Associative Search Network: A Reinforcement Learning Associative Memory[END_REF], where the authors show how a simple network could be used to model a learning approach based on reference points (landmarks). Specifically, the movement rules defined by Barto and Sutton, are based on distinct olfactory gradients (emitted by the reference points).

By considering a payoff function z, that is maximized when the robot reaches the objective and is decreasing while the distance (between the robot and the target) increases, it is possible to show that the robot is able to find the right path and reach the target. Of course, by providing the system only with the payoff function makes the movement of the robot less precise and the overall process longer. In our reference model, the network is constituted by 4 input units and 4 output units. The input unit i can assume the values N orth, South, East and W est, the context input x i (t) is the signal emitted by the correspondent reference point and y represents the output of the ASN system. Every input unit is completely connected to each output unit j, where j = N orth, South, East and W est. In this way, each input unit can "modulate" or adapt 4 connection weights w ji (t) in the connection matrix by following the equation 2. Each weight encodes a confidence degree in such a way that, when the robot is close to a reference/landmark point i, it should proceed towards the direction j, closer to the target.

The confidential degree s j (t) (in order to move in direction j) is computed as the sum of the products of the current weights and signals received by the reference points as

s j (t) = w 0j (t) + i w ji (t)x i (t), (3)
where w 0j (t) is a polarization term. The weights w 0j are updated as follows:

w 0j (t + 1) = f [w 0j (t) + c 0 (z(t) -z(t -1))y(t -1)], (4)
where

f (x) =      BOU N D if x > BOU N D, 0 if x < 0, x otherwise (5)
f bounds each w 0j to the interval [0, BOU N D]. c, c 0 and BOU N D are positive real numbers. The rule as defined in 5 is necessary to allow the ASN to correctly work also in the absence of landmark information. More details about values and impact of c, c 0 and BOU N D can be found in [START_REF] Barto | Associative Search Network: A Reinforcement Learning Associative Memory[END_REF].

In our specific case, if our robot is close to the reference point N orth, the output unit South will be activated and next the robot will head to South. Furthermore, if the robot is in the quadrant South -W est, the output units of N orth and East will be activated and the next step of the robot will be in the North-East direction. The robot has to learn the appropriate weights by implementing the rule as in Eq. 2. In this case, a connection weight w ji will change if and only if a movement towards direction j, i.e. (y j (t -1) > 0), is executed and the robot is close to a reference point i(x i (t -1) > 0). By considering z(t) as a measure of the closeness of the target, we can observe that w ji increases when z increases, yielding that direction j makes the robot to move towards the right direction. In this case, a movement j is likely to occur again. On the other hand, whether w ji decreases, the function z also decreases and the robot will move towards the wrong direction.

Our Target Localization Algorithm

This section details our Localization Algorithm, detailing the rules that drive the movement of the robot. The main goal for the robot is to "detect" the target (receive a signal strength with a sufficient level from the target) and to move to reach it without a priori knowledge about the environment.

In order to correctly move, the robot has to implement a behavioral logic, based on the input information it receives (e.g. the RSSI) and the elaboration of the inputs through the ASN.

The Localization Algorithm is split in two phases: the 1) ASN implementation Phase and the 2) Approaching Phase, as shown in Fig. 1. During both phases, an underlying obstacle avoidance process, detailed in the next section, is running.

We assume the target to be reached is always turned-on and that the robot is moving in the room where the target is. Based on these assumptions, our algorithm terminates when, based on the inputs received the robot estimates it has reached the target. The robot checks for the list of tasks and implements the first one. It enters the ASN Implementation Phase, which consists in receiving the "signals" from different devices and analyzing them. If the robot does not overhear its target, it moves forward for an arbitrary time ∆t (e.g 1 or 2 sec.) by following a Random Way Path (RWP) [START_REF] Hyytiä | Random waypoint model in n-dimensional space[END_REF]. It travels a prefixed distance, then it stops and checks for listening the devices. It repeats this process while it does not hear the target device.

Performance Evaluation

In this section, we describe the test-bed considered to assess the performances of the ASN-based target localization. First, we detail the entities considered to realize the proof-of-concept and then we describe the scenario.

The "Entities" involved

The reference scenario we implemented is characterized with heterogeneous items. Specifically we have: 1) The target node : TP-LINK Router Wireless N300; 2) 4 landmarks -1 NETGEAR Wireless Router MR314, 1 ALICE Gate2 Plus Wi-Fi and 2 notebooks HP 630 (hotspots); 3) Rovers (robots equipped with wheels to support mobility). We placed the two hotspots in the points W est and East of the area, the target in the centre of the area and at N orth and South we put the other routers. The reference scenario is represented by an area of 15m 2 (3 × 5m) as shown in Figure 2. The received power value has been obtained both from the anchor nodes (landmarks) and the target through the command Iwlist, that is available in the Linux platform as part of the wireless-tools library. Through this package, it is possible to have a set of commands to control the wireless devices based on the standard 802.11. The Iwlist command is used in combination with some parameters to better specify the data requested by a user. It details, for every detected network, a set of data related to the ESSID of the network, the quality of the signal, the transmission channel frequency, and the Received Signal Strength Indication (RSSI).

To the follow we detail each step of the algorithm as implemented in our Rover and shown in Figure 1.

Obstacle Check and Obstacle Avoidance Every robot runs an obstacle detection and avoidance based on ultrasound sensors. Once an obstacle is detected, the robot bypasses it. To do so, the robot scans the area on the right side with an angle α • . If the obstacle is still there, the robot scans the area with an angle 2 × α • on the left side. If the obstacle is still there, the robot moves backward, turns α • right again and resumes its previous movement (either in searching or approaching phase).

Localization Start If the robot does not detect any obstacle, it runs the Localization Phase, by acquiring the signal inputs. If the robot individuates the target ID among the signals received, it compares the RSSI value with a threshold value. If the signal RSSI results greater than a certain threshold, the robot estimates the target as reached, otherwise the robot enters the ASN-Localization algorithm.

ASN implementation phase This is the core of the algorithm. Based on the received input signals x 1 , x 2 , ..., x n , the ASN will output a specific action that corresponds to a specific direction towards which the robot will move. The output signals y 1 , y 2 , ..., y m will constitute the new RSSI values, deriving from the new position of the robot. The payoff z represents the closeness of the robot from the target.

Results

In order to evaluate the ASN technique proposed, we realized a proof-of-concept based on a testbed as described in 6.1 and a variable number of robots (ranging from 1 to 3). We build this Arduino platform from scratch and we equipped it with a mini-pc, that constitues the "brain" of our robot. We performed three types of experiments, every result is the average over more than 30 runs. The parameters we evaluated are the time needed to reach the target (Delay) and how close the robot is positioned from the target when the algorithm exits (Dist). Numerical results are reported in Table 1.

Characterization of our ASN-based Target Localization technique

In this section, we summarize the main features that characterize our ASN system and we discuss some derived properties. Our system is characterized as follows:

-The learning process is no central unit; -The weights are adjusted locally, they only depend on current variables (signal, position); -Weights do not depend on the difference between the desired output and the actual value of the system; -The transition process runs until the network has reached an equilibrium. In our case, it is achieved when the RSSI-estimated distance is smaller than a threshold value, the robot will not move and then RSSI are unchanged.

Let w ij be the weight value that connects the output of the i th context input with the j th output, W = w ij the weight matrix and Y = [y 1 , ..., y n ] T the output vector. W is symmetric (i.e. w ij = w ji ) and w ii = 0. We consider a discrete Hopfield network used as an auto-associative memory [START_REF] Hopfield | Neural networks and physical systems with emergent collective computational abilities[END_REF] for searching purpose. Based on the premises considered, the evaluation of the stability property of our system can be performed by considering the computational energy function E, which is defined in n-dimensional output space Y as:

∆E = E(x(t + 1)) -E(x(t)) = - 1 2 Y T W Y (6)
that is:

E = - 1 2 i j w ji x j (t + 1) - i w 0j (t)x i (t + 1) + 1 2 i j w ji x j (t) + i w 0j (t -1)x i (t) (7)
where w 0j is as defined in Eq. 3. In the theory of stability, if the structure of the matrix is as those defined for our weights matrix W , and the schedule, where only a unit of the network is updated at a time, namely asynchronous update, it is possible to show that the system converges to one stable state in finite time. The stability is proved by showing that the energy function always decreases as the state of the processing are changed one by one. Let us consider that the neuron input (context input), that just changes state at step t is neuron p. Therefore, x p (t + 1) is determined as:

x p (t + 1) =      1 if s(t) + noise > 0, x p (t) if s(t) + noise = 0, -1 if s(t) + noise < 0. (8)
It is worth recalling that X is the input pattern and Y is desired output pattern and in the case of auto-associative memory, we have X = Y , and the diagonal entries of the weights matrix W are set to 0, namely w ii = 0, with i = 1...n. If all the states of the network are to be updated at once (as in our case), then the next state of the system will be represented as: x(t + 1) = y(W T x(t)). When the exemplars are orthonormal and we have: y(x) = x and Y X T x r = i δ ir y i = y i , with r=1...n and δ ir is the kronecker delta, then we obtain:

y(W T x r ) = y(x r ) = x r (9)
that means that each stored pattern (or memory element) is a stable state of the network. Whether x p (t+1) is determined as 8, for all the other inputs (or context inputs), we have x i (t + 1) = x i (t) for i = p. Furthermore, we have w pp = 0, and:

∆E = -((x p (t + 1) -x p (t))( j w jp x j (t)) + w 0p (t)) (10) namely
, ∆E = -((x p (t + 1) -x p (t))s p (t) (11)
It is worth noticing that, if the value of x p remains the same, then x p (t+1) = x p (t) and the ∆E = 0. If they are not the same, either it will be x p (t) = -1 and x p (t + 1) = 1 due to the fact that s p (t) > 0, or x p (t) = 1 and x p (t + 1) = -1 due to the fact that s p (t) < 0. Whatever the case is, if x p (t + 1) = x p (t) it is in a direction for which ∆E < 0. Therefore, for this type of specific network (discrete Hopfield), we have ∆E < 0. Since the energy function decreases at each state (some fixed amount) and it is bounded, it reaches a minimum value in a finite number of state changes. This can be translated as a convergence to one stable state of the network in finite time. The type of schedule considered here is named asynchronous update, since only one unit at each time is updated. Where all the units are updated at once, namely the synchronous update, the convergence is not guaranteed, since it may result in a cycle of length two. Of course, some of the stored patterns may not be a stable state. In fact, we are dealing experiments with RSSI in indoor environments, and we experimented cases of components of multi-path that add in some points, resulting in higher values of the target signal. We also faced with some spurious stable states, that is different from the stored patterns. Based on the details we have given in the implementat Section, whether the initial state is set to one of the exemplar (the ASN implementation output says that the robot already reached the target, based on the input signals received), the robot remains there (it does not move). On the other hand, if the initial state is set to some arbitrary input, then the network converges to one of the stored memory elements, depending on the basin of attraction in which x(0) lies.

Conclusions

In this work we implemented an Associative Search Network on Arduino-based robots to perform target indoor localization tasks. As input signals, we considered the RSSI parameters for the inherent advantages that it has, such as no extra-hardware required and it is always available. These features can play a very important role when heterogeneous devices are considered and are asked to accomplish the target localization task. The realized ASN is Hopfield-network based, and this allowed us to characterize our system with some main and important features regarding stable states. Even if there are open issues related to the presence of spurious stable states (i.e. optimal states that are different form those stored), we showed that the system is effective and allows the robots to reach the target object. Moreover, the learning technique as implemented is not constrained neither with a specific number of landmarks nor with a specific position in the area, since the system evolves and learns by acquiring the external signals.

Fig. 1 . 4 :TargetFound then 5 :: else 9 : 1 : 2 :

 145912 Fig. 1. Flowchart reporting the steps of the behavior of a robot. Algorithm 1 Localization Algorithm • Local variables: TargetFound = TargetReached = FALSE; List List of tasks; RSSI-based target localization 1: while List = ∅ do 2: T ← POP(List) {Move to next task/target T in the list}

Fig. 2 .

 2 Fig. 2. Real scenario.

Table 1 .

 1 Results. Delays are in sec, distances in cm

	Robot 1	Robot 2	Robot 3
	Delay	Dist.	Delay	Dist.	Delay	Dist.
	61,6	26	-	-	-	-
	65,7	25,5	80,5	31,3	-	-
	69,6	26,5	82,2	33	93,4	39,7


Jean-Philippe Condomines

Murat Bronz

Gautier Hattenberger

Jean-Franc ¸ois Erdelyi

Experimental Wind Field Estimation and Aircraft Identification

The presented work is focusing on the wind estimation and airframe identification based on real flight experiments as part of the SkyScanner project. The overall objective of this project is to estimate the local wind field in order to study the formation of cumulus-type clouds with a fleet of autonomous mini-UAVs involving many aspects including flight control and energy harvesting. For this purpose, a small UAV has been equipped with airspeed and angle of attack sensors. Flight data are recorded on-board at high speed for post-analyses. An approach based on Unscented Kalman Filter (UKF) is proposed for nonlinear wind estimation. As a first result, wind updraft estimation is highlighted by exploiting recorded flight test data. In addition to this, a motor test bench has been developed in order to establish a model of the propulsion system from wind tunnel experiments. It will be combined with a classical aerodynamic model for airframe identification Preliminary flight results are presented.

INTRODUCTION

Small Unmanned Aerial Vehicle (UAV) are now widely used for atmospheric and meteorological researches [START_REF] Mayer | A "no-flowsensor" wind estimation algorithm for unmanned aerial systems[END_REF][START_REF] Rogers | Uavbased atmospheric tomography using large eddy simulation data[END_REF]. They can easily carry compact sensors, but when it comes to more important payloads like particles and aerosols detectors, the remaining available weight can be limited, unless a bigger airframe is chosen. An important parameter for atmospheric studies, but also for long endurance autonomous flights [START_REF] Cobano | Thermal detection and generation of collision-free trajectories for cooperative soaring uavs[END_REF], is the observation of the local wind field. Such information can be used for autonomous soaring for instance. The SkyScanner 1 project aims at studying and experimenting a fleet of coordinated Mini UAVs which adaptively samples cumulustype clouds. This is involving many aspects including flight control and energy harvesting. The main tackled challenges are a better understanding of the clouds micro-physics, small airframe optimization, and optimized fleet control.

The presented work, as part of the SkyScanner project, is focusing on the wind estimation and airframe identification based on real flight experiments. For this purpose, a small UAV has been equipped with airspeed and angle of attack sensors. Flight data are recorded on-board at high speed for post-analyses. Several solutions have been used for wind estimation [START_REF] Larrabee | Wind field estimation in uav formation flight[END_REF][START_REF] Cho | Wind estimation and airspeed calibration using a uav with a single-antenna gps receiver and pitot tube[END_REF][START_REF] Cho | Wind Estimation and Airspeed Calibration using a UAV with a Single-Antenna GPS Receiver and Pitot Tube[END_REF] and system identification [START_REF] Meng | Aerodynamic parameter estimation of an unmanned aerial vehicle based on extended kalman filter and its higher order approach[END_REF][START_REF] Hemakumara | Non-parametric uav system identification with dependent gaussian processes[END_REF]. The proposed solution will be based on Unscented Kalman Filter (UKF) [START_REF] Julier | New extension of the Kalman filter to nonlinear systems[END_REF][START_REF] Sarkka | On Unscented Kalman Filtering for State Estimation of Continuous-Time Nonlinear Systems[END_REF], widely used in its square-root version form [START_REF] Van Der Merwe | The square-root unscented kalman filter for state and parameter-estimation[END_REF][START_REF] Condomines | Nonlinear state estimation using an invariant unscented kalman filter[END_REF][START_REF] Condomines | Pi-Invariant Unscented Kalman Filter for sensor fusion[END_REF].

In addition to the flight data, a model of the propulsion system is required in order to evaluate the propulsive power of the plane based on the flight speed and the consumed electrical power directly measured on the battery. A motor test bench have been designed for this purpose, with an automatic recording sequence controlled by a computer.

In the sequel, first section presents the models and the problem formulation. Then, the theoretical basis of the estimation and identification algorithms are presented. The next section details the experimental setup and the instruments embedded on the UAV. To conclude, the final part gathers all the motor test bench and the experimental results obtained from the flights.

PROBLEM FORMULATION

Wind field

Small UAVs are very sensitive to relative high wind gusts because of their size, hence satisfying the real-life demands becomes difficult. In general wind speed is assumed to be a spatially and temporally varying vector field s.t.

w(x, y, z,t) =   w i x (x, y, z,t) w i y (x, y, z,t) w i z (x, y, z,t)  
where the superscript i denotes components expressed in the inertial frame. A small vehicle flying through this field is influenced by three components of the wind field and gradients of the wind field such that :

d dt w(x, y, z,t) =   ẇi x ẇi y ẇi z   =    ẇi ζ →x ẇi ζ →y ẇi ζ →z    + ∇w(x, y, z)   ẋ ẏ ż  (1)
where the subscript ζ denotes the time rate of change of wind velocity at the point (x, y, z). Three component ẋ, ẏ and ż represent the velocity of the vehicle with respect to inertial frame and ∇w(x, y, z) is the gradient of the wind field. Assuming a constant wind field as seen by the vehicle, the last term of Eq.1 becomes to zero, however this approximation is only applicable when vehicle velocity is large compared to the "point" rates of change of wind velocity (e.g, wing span is significantly larger than tail height, so vertical gradient of the lateral airmass velocity has negligible effect on roll rate). This paper considers the simultaneous nonlinear state estimation of aircraft body-axis velocity component and wind velocity component in the North-East-Down (NED) inertial reference frame using this assumption.

Vehicle Dynamics and Kinematics

In order to tackle a wide range of applications, various implementations of flight dynamics models, in terms of assumptions and numerical techniques, therefore exist. To overcome the difficulty for an UAV to derive a reliable representative aerodynamic model, they are commonly represented using a 6 Degrees of Freedom (DoF) kinematic model (3 DoF correspond to the translational motion (V N ,V E ,V D ) and the 3 remaining DoF to the rotational motion (ϕ, θ , ψ)). Assuming a flat non-rotating Earth the flying rigid body motion in turbulent conditions can be located at r with velocity v i having components V N ,V E ,V D in an inertial frame I, where xi , ŷi and ẑi define unit vector (see figure 1). Using a standard body-fixed coordinate frame with airmass-relative velocity v a having components u, v, w in the body xb , ŷb , ẑb directions, respectively, the acceleration of the aircraft in the inertial frame can be mathematically described s.t:

r = vi + ẇ Developing inertial velocity r = d dt v a + ω × v a + d dt w Hence d dt v a =   u v ẇ  -ω × v a - d dt w (2)
Using angular velocity ω = p q r T and aerodynamics forces X, Y, Z depending on functions of trust T, drag D and lift L expressed in the body x, y, z directions, the fundamental principle of dynamics now becomes :

  X Y Z   +   0 0 mg   = m     u v ẇ  -   0 -w v w 0 -u -v u 0     p q r   -   d dt w ix d dt w iy d dt w iz     (3)
In Eq.3, the latter quantity d dt w is expressed in the inertial frame and can be converted in the body frame through a Direction Cosine Matrix (DCM) R a i which is defined by successive rotation of the roll, pitch and yaw angles of the aircraft s.t :

R a i = (R i a ) T =   cθ cψ cθ sψ -sθ sϕsθ cψ -cϕsψ sϕsθ sψ + cϕcψ sϕcθ cϕsθ cψ + sϕsψ cϕsθ sψ -sϕcψ cϕcθ  
In the next sections, Galilean transformations will be made by using a standard quaternionial form, i.e, R a i • r = q -1 * r * q, R i a • r = q * r * q -1 . Note that symbol * corresponds to the quaternion product. Using the aforementioned standard quaternional form provides at the same time :

• a global parametrization;

• avoids the mathematical singularities inherent to Euler angles;

• and is convenient for calculations and simulations.

For more details about formulas used on quaternion in this paper, see Appendix A. Finally, the state dynamics for the body-axis velocity states are given by u

= X m -g sin θ -qw + rv -ẇix cos θ cos ψ -ẇiy cos θ sin ψ + ẇiz sin θ v = Y m -g sin ϕ cos θ + pw -ru -ẇix (sin ϕ sin θ cos ψ -cos ϕ sin ψ)
ẇiy (sin ϕ sin θ sin ψ + cos ϕ cos ψ)

-ẇiz sin ϕ cos θ ẇ = Z m -g cos ϕ cos θ + qu -pv -ẇix (cos ϕ sin θ cos ψ + sin ϕ sin ψ)
ẇiy (cos ϕ sin θ sin ψ -sin ϕ cos ψ)

ẇiz cos ϕ cos θ with ẇi(•) denotes the rate of change of a component of the wind velocity expressed in the inertial frame.

Aerodynamic and propulsion

Aerodynamic lift and drag forces in stability axes can be written as follow:

L = 1 2 .ρ.V 2 a .S ref C L (4) D = 1 2 .ρ.V 2 a .S ref C D (5)
with,

                   C L = C L0 +C Lα .α +C Lβ .β + 1 2V a    bC L p cC L q bC L r    .    p q r    + ∑ sfc C Lsfc .δ sfc C D = C D0 +C Dk .C 2 L + ∑ sfc C Dsfc .δ sfc ( 6
)
where α is the angle of attack, β the side-slip angle and δ sfc the elevator deflection. Since we are mostly interested in steady flight conditions, close to straight line without sideslip, and that the effect of the elevator on lift and drag forces is small, the equations can be reduced for performance analysis to:

L = 1 2 .ρ.V 2 a .S ref (C L0 +C Lα .α) (7)
D = 1 2 .ρ.V 2 a .S ref (C D0 +C Dk .C 2 L ) (8)
In steady level flight, the weight is equilibrated by the lift, and the drag by the thrust. As a first approximation, the thrust, or more precisely the propulsive power P (the product of the thrust T by the airspeed V a ) can be expressed as:

P = η.P elec (9)
where, P elec is the electrical power drown from the batteries and η is an efficiency coefficient, function of the advance ratio, the propeller and motor characteristics, the Reynolds number and the electrical efficiency of the global propulsive system.

A more complex propulsion model [START_REF] Drela | First-order dc electric motor model[END_REF], with a first order DC motor model, might be used in later studies in order to define an analytic description of η.

WIND FIELD ESTIMATION AND AIRCRAFT MODEL IDENTIFICATION

Wind field estimation

This problem considers simultaneous estimation of aircraft body-axis velocity (u, v, w) and wind velocity components (w ix , w iy , w iz ). Both process and measurement equations are not dependent on aerodynamic force described above. The estimation is performed through a fusion algorithm of low-cost inertial sensors used for UAV navigation [START_REF] Condomines | Nonlinear state estimation using an invariant unscented kalman filter[END_REF]. The navigation quality is limited by inertial sensors performance specifies by the size, power and cost constraints of the UAV. To recover navigation accuracy using low-cost aided-INS (Inertial Navigation System), it is necessary to use, if possible, additional instruments (e.g. magnetometers, barometer, which are used to improve the heading and position accuracies) and/or nonlinear estimation algorithms to improve the flight handling qualities of the aerial vehicle. The nonlinear state estimation makes use of 2 triaxial sensors plus both GPS and Pitot tube sensor units which deliver a total of 10 scalar measurement signals:

• 3 gyroscopes providing a measurement of the instantaneous angular velocity vector denoted by ω m ∈ R 3 s.t.

ω m = [p m , q m , r m ] T ;
• 3 accelerometers giving a measurement of the specific acceleration denoted by a m ∈ R 3 s.t. a m = [a mx , a my , a mz ] T ;

• 1 GPS unit measuring both position (not used) and velocity vectors denoted by y

V = v i ∈ R 3 s.t. vector v i = [V N ,V E ,V D ]
T is used in the observation equations;

• 1 pitot tube sensor providing a scalar measurement of the air data denoted by y Va .

All the sensors embedded are low-cost, and therefore have imperfections. The major error sources in the navigation system are due to: -all of the disturbances (noises) that affect all the instruments; -the potential incorrect navigation system initialization (e.g. on magnetometers or barometric sensor); -and the inadequacy between the real local Earth's gravity value and the one used for computation. The largest error is usually a bias instability (expressed respectively in deg/hr for gyros and µg for the accelerometers).

All these measurements are obviously corrupted by additive noises for which it appears reasonable to assimilate their stochastic properties to the ones of Gaussian processes. Their covariances have been identified in [START_REF] Murat | Development of an 18cm Micro Air Vehicle : QUARK[END_REF] from logged sensor data using the Allan variance method [START_REF] El-Sheimy | Analysis and Modeling of Inertial Sensors Using Allan Variance[END_REF]. Moreover, these errors correspond to the random nature of wind evolution necessary in Eq.2.

Using these values, the state space representation corresponding to M s can be described in a compact form such as:

ẋ = f (x, u)
and y = h(x, u)

where:

x = [u, v, w, w ix , w iy , w iz ] T , u = [ω T m , a T m ]
T and y = [y T V , y Va ] T are the state, input and output vectors respectively.

M s                                                      u = a mx -g sin θ + r m • v -q m • w v = a my + g cos θ sin ϕ + p m • w -r m • u ẇ = a mz + g cos θ sin ϕ + q m • u -p m • v ẇix = 0 (process) ẇiy = 0 ẇiz = 0    y V N y V E y V D    = q *    u v w    * q -1
(measurement)

y Va =    u v w    -q -1 *    w ix w iy w iz    * q
Obviously, to implement these equation in a discrete-time filter, a first order discretization is used [START_REF] Lewis | Optimal Control[END_REF].

x k = x k-1 + T s . f c (x k-1 , u k-1 ) + ν k y k = h(x k ) + µ k
where f is the discrete-time state transition, h is the nonlinear observation function which depend on DCM through quaternion and T s is the sampling time of the system. ν, µ are the zero-mean Gaussian process noise vectors with covariance matrix, Q, R. Using these relationships, the angle of attack and side-slip are calculated from the body axis velocity components by

α = tan -1 w u β = sin -1 v √ u 2 + v 2 + w 2
Since the measurement equation formulation contains nonlinear function, a nonlinear state estimation technique such as EKF [START_REF] Kalman | New Results in Linear Filtering and Prediction Theory[END_REF] or UKF is required. The SR-UKF (Square-Root UKF) was selected for this work due to its ease of implementation and outperforms relative to EKF. Identification of both This study uses flight data collected with a small UAV which is susceptible to perform some trajectories which leads to reduce maneuverability and so unobservability on two components of wind speed. Wind speed unobservability points out a particular behavior of UKF which is shown by a slow drift on state vector due to using sigmas-points for prediction and correction steps. Indeed, in case of strong nonlinearity, predictions are obtained by weighting the sigma-point predictions whose results differs from the direct calculation of the prediction from the estimated state (see figure 2). Firstly, effects can be observed in the calculation of the predicted state where the successive accumulation of these differences can lead to significant drifts, and secondly, in the correction of the state from the prediction measure. These effects can be eliminated by performing the calculation of prediction of the state and measures from the estimated average state, while retaining the sigma points for the calculation of covariance.

Aircraft model identification

The aircraft model identification is using the equation from section 2.3 during steady flight phases, when the airspeed is almost constant, thus the acceleration is zero. As a results, lift equals weight and thrust equals drag. Since the propulsion model was still under investigation at the time of the first flight experiments, the methodology have been adapted in order to estimate the drag. The procedure described in [START_REF] Edwards | Performance testing of rnr's sbxc using a piccolo autopilotd[END_REF] have been used. It consists of performing several gliding phases at different airspeed and angle of attack in order to estimate the drag from the glide flight path γ:

tan γ = - D L = - C D C L (10)
The identification of the lift coefficient is done using Eq. 7. For each flight phase, the airspeed V a and the angle of attack α are averaged. Then a linear regression is used to estimate the two parameters C L0 and C Lα .

In order to identify the drag coefficient, only the gliding phases are considered as stated above and equations 8 and 10 are used. Three parameters are then needed, the lift coefficient and the angle of attack that are already computed, and the flight path angle γ. Since this angle can't be directly measured, two methods have been evaluated. The first method is using an angle of attack installed on the UAV and the pitch angle θ estimated using the IMU sensor. With the kinematic relation θ = α + γ, the path angle is estimated by averaging over the complete phase. The second method is using the relation that the lift over drag ratio is also the ratio between the horizontal distance and altitude lost during a glide. The main constraint is that the experiment needs to be done with almost no wind so that the ground and aerodynamic flight paths are the same. After estimating the parameter γ, the drag coefficient is computed with Eq. 10, and second order polynomial regression is done between C D and α in order to estimate C D0 , C Dk .

Experimental results are presented in section 5.1 and they are showing a good correlation between the two methods.

For a futur work, the UKF estimation algorithm presented at the previous section will be applied for these parameters identification.

EXPERIMENTAL SETUP

UAV instrumentation

As mention above, a mini UAV has been equipped with several sensors in order to make in-flight measurements. The frame itself is a commercial foam plane Solius from Multiplex 2 , a 2.16 meter wingspan motorized glider. The autopilot is an Apogee 3 board using the Paparazzi system [START_REF] Brisset | The paparazzi solution[END_REF][START_REF] Hattenberger | Using the Paparazzi UAV System for Scientific Research[END_REF], which includes a SD card slot for high speed logging.

It would have been possible to connect all the required sensors to the main autopilot, but due to electrical problems with long cables, it has been decided to split the Data Acquisition System (referred as DAQ board) from the flight control (referred as AP board). Hence, a second Apogee board was used to record the sensors, which is possible since there is no feedback of the wind estimation to the flight control at this stage of the project. The DAQ board is already equipped with 3-axis gyroscopes and accelerometers, and a low resolution barometer. The INS filter [START_REF] Condomines | Pi-Invariant Unscented Kalman Filter for sensor fusion[END_REF] used to estimate the position and orientation of the plane also requires a magnetometer and a GPS, that have been externally mounted.

The SkyScanner project aims at studying the formation of clouds. The meteorological parameters will be measured using a dedicated board Meteo-Stick. This board has high resolution absolute pressure sensor, differential pressure sensor, temperature sensor and humidity sensor. For this study, only the differential pressure sensor was used connected to a Pitot tube in order to measure the airspeed of the plane.

The figure 3 is showing the final integration of the measurement system, with the DAQ and Meteo-Stick stacked, the GPS and the magnetometer at the back.

The main sensor addition is an angle of attack sensor, mounted on the wing close to the Pitot tube. This sensor is made of a US DIGITAL MA3-P12-125-B 4 angular sensor. It is an absolute position sensor using hall effect with 12-bit 2 http://www.multiplex-rc.de 3 http://wiki.paparazziuav.org/wiki/Apogee/v1.00 4 http://www.usdigital.com/products/encoders/absolute/rotary/shaft/ma3 Fig. 3: Integration of the data acquisition system in the nose of the UAV.

internal converter giving less than 0.09 • of resolution with a very low noise. The vane has been 3D-printed and mounted directly on the shaft of the sensor. The figure 4 shows the final integration of this two sensors on the wing. The piece holding them has also been made with a 3D printer. The final setup for the SkyScanner project will also include a current sensor in order to measure the electrical power drown by the motor that will be used in the aerodynamic and propulsion models, and some additional scientific sensors dedicated to the atmospheric research part, such as Liquid Water Content sensors, not directly related to the wind estimation.

Motor test bench

In order to integrate the propulsion model to the estimation process, it is necessary to establish the relation between the electrical current consumed by the motor, the rotation speed, the flight speed and the resulting propulsion forces and torque generated. Since it is not possible to embedded the necessary sensors to estimate this late parameters in flight, a motor test bench provides the propulsion model based on wind tunnel experiments.

The figure 5 shows the bench. Two force sensors are used to measure the propulsive force and the motor torque. The bench itself is an assembly of 3D-printed pieces and aluminum bars. In addition to the mechanical mounting of the motor and its propeller, an electronic board is required for the sensors' signal conditioning. Finally, a myRIO data acquisition board from National Instruments connects them to the lab computer. A graphical interface developed using LabView allows to control the motor PWM command and synchronize all the measurements, making the process almost fully automated (the wind tunnel speed is currently control by hand). The figure 6 presents the global architecture and wiring of the motor test bench.

Fig. 6: Overview of the motor test bench experimental setup.

EXPERIMENTAL RESULTS

Flight tests

A few flight tests using the experimental setup described in the previous section have already been conducted (see fig- Some preliminary results have been analyzed in order to aces the quality of the measurements, especially the angle of attack sensor since the Meteo-Sick sensors have already been validated in a previous project. The figure 8 shows the good correlation between the variation of the airspeed and the angle of attack (one increasing when the other decrease). Note that study uses angle of attack data collected with a constant offset which can be removed from raw data. airspeed following the same protocol than [START_REF] Edwards | Performance testing of rnr's sbxc using a piccolo autopilotd[END_REF]. The figure 10 is showing four of these flight phases extracted from the complete experimental flight. From the complete flight, four gliding phases and three cruise level flight phases have been selected for their stable airspeed and away from stall point. The figure 11 is a plot of the lift coefficient C L over the angle of attack α, using both cruise and gliding phases. Figure 12 shows the drag coefficient C D over α computed with the two methods as described section 3.2. Both methods are giving very similar results, which is validating the identification methodology.

The table 1 summarizes the estimated aerodynamic coefficients (with α in degree):

Motors analysis

The motor test bench have been placed in a wind tunnel and the parameters have been recorded at different airspeed from 0 (static thrust) up to 22 m/s. The resulting thrust versus RPM is shown on figure 13. We can see that the motor is generating a fair amount of static thrust (up to 10 N for a 1.5 kg plane) allowing easy take-off. But at higher speed, the motor is not generating positive thrust at low RPM (at 22 m/s it needs at least 80% of throttle) since the glider was not originally designed for high speed.

The main interest for improving the wind estimation and aircraft identification is to find a simple relation between the propulsive power and a measurable parameter. The figure 14 is showing this propulsive power versus the electrical power drown from the battery. This later value can be measured onboard from voltage and current sensors. As we can see, for the useful flight speeds from 10 to 15 m/s, their is a simple linear dependency of these two parameters. 6 CONCLUSION This article has presented the theoretical basis of a wind estimation algorithm based on Unscented Kalman Filter. Experimental flights have already been conducted in order to get real data. A foam glider have been equipped with airspeed and angle of attack sensors in addition to the traditional GPS+IMU units needed for the autonomous flight. The propulsion model have been identified using a motor test bench in a wind tunnel. Further developments will integrate this model to the aircraft aerodynamic identification process and to the wind estimation.

This work is only a first step in a larger project aiming at conducting atmospheric research using a fleet of cooperative UAVs. The estimation of the local wind field is therefore an important part of the project, but can be reused in many other applications such as long endurance flights based on autonomous soaring.

Fig. 1 :

 1 Fig. 1: Reference frames.

Fig. 2 :

 2 Fig. 2: Sigma point approach.

Fig. 4 :

 4 Fig. 4: Integration of the Pitot tube and the angle of attack sensor on the leading edge of the wing.

Fig. 5 :

 5 Fig. 5: Final version of motor test bench.

Fig. 7 :

 7 Fig. 7: Solius glider fully equipped for experimental flight.

Fig. 8 :

 8 Fig. 8: Comparison of the angle of attack (red, plain line) and the airspeed (green, dashed line).

Fig. 9 :

 9 Fig. 9: Estimation of a wind updraft (red) during a gliding phase with confidence bounds (green).

Fig. 10 :Tab. 1 :Fig. 11 :

 10111 Fig. 10: Different gliding flight path. C L0 C Lα 0.2831 0.04119 C D0 C Dk method 1 0.01848 0.2034 method 2 0.01839 0.1912

Fig. 12 :Fig. 13 :

 1213 Fig. 12: Drag coefficient versus squared lift coefficient, estimated with two different methods.

Fig. 14 :

 14 Fig. 14: Propulsive power versus electrical power input for useful flight speeds.

ACKNOWLEDGEMENTS

The SkyScanner project is founded by the RTRA-STAE foundation.

APPENDIX A: QUATERNIONS AND ROTATIONS An unit quaternion provide a convenient mathematical notation and a global parametrization for representing orientation and rotation of a rigid body in three dimensions. Indeed, for any unit quaternion q = q 0 + q = cos θ 2 + usin θ 2 and for any vector p ∈ R 3 the action of the operator q -1 * p * q = R q • p is associated to a rotation matrix R q ∈ S0(3) which is a rotation of the coordinate frame about axis u = q ||q|| through an angle θ . Note that a vector p ∈ R 3 can be viewed as a pure quaternion whose real part is zero 0 p . Thus, when the real part is a scalar denoted p 0 ∈ R the quaternion p is given as :


Nicola Roberto Zema
email: nicola.zema@unirc.it

Nathalie Mitton
email: nathalie.mitton@inria.fr

Giuseppe Ruggeri
email: giuseppe.ruggeri@unirc.it

A GPS-less on-demand mobile sink-assisted data collection in wireless sensor networks

Keywords: WSN, Controlled Mobility, GPS-less

The autonomous data collector is a role recently introduced to improve the performance of Wireless Sensor Networks. When a prompt response for data processing and offloading is necessary, i.e. in the case of event-driven networks, a mobile flying sink could be a good option for that role. In this paper, we introduce FreeFall, a distributed algorithm for the autonomous navigation of a mobile collector through a WSN for on-demand data offloading that does not rely on an absolute coordinate system. We show that, under fairly common circumstances, it is possible to set the trajectory of the mobile sink and fulfill the offloading requests without the needs of additional equipment installed on nodes. We show how our system is preferable over more classical routing solutions especially in the presence of localized generation of large amounts of information.

I. INTRODUCTION

The use of controlled mobility as a degree of freedom has been found as one of the most prominent methods to ease the energy consumption, increase the lifetime and enhance the performances in a wireless sensor network [START_REF] Gao | Efficient data collection in wireless sensor networks with path-constrained mobile sinks[END_REF]. For instance, sensors nodes around fixed data sinks deplete sooner their energy because of an increased traffic flow through them, and it is created an energy hole. This problem could be solved using a mobile collector [START_REF] Zema | Using location services to autonomously drive flying mobile sinks in wireless sensor networks[END_REF], [START_REF] Liang | Prolonging network lifetime via a controlled mobile sink in wireless sensor networks[END_REF]. In a WSN where data generation is linked to "events", there would be nodes where the generation rate increases whenever their sensors detect environmental changes [START_REF] Filipponi | Smart city: an event driven architecture for monitoring public spaces with heterogeneous sensors[END_REF], and suddenly an huge amount of data has to be rapidly offloaded to a sink. Again the use of a mobile collector has proven to be effective to improve the offloading process. In fact, by using the mobile collector, most of the transmission are carried on sigle hop connection. As an immediate consequence, the data offloading rate is increased and the energy consumption is reduced.

In [START_REF] Tunca | Distributed mobile sink routing for wireless sensor networks: A survey[END_REF] it has been shown that a good possibility for the implementation of a controlled mobility framework is when the network itself drives the sink trajectory in a completely distributed manner exploiting geographic and geometrical properties. In this paper, following these previous studies, we introduce FreeFall, a novel distributed GPS-less method for a mobile collector which trajectory is driven by the 'off-loading' requests issued by the network sensor nodes without the aid of a global positioning system installed in them. More in detail, according to the FreeFall approach the nodes interested to transmit their data explicitly advertise their position to a mobile sink. The mobile sink will be capable to set its own waypoints in order to reach the interested areas using only an inertial navigation system. To the best of our knowledge, the only strictly similar work in the literature is our previous Directed Movement approach, introduced in [START_REF] Zema | Using location services to autonomously drive flying mobile sinks in wireless sensor networks[END_REF], which relies on the same principles than FreeFall but which assumes that nodes are aware of their absolute geographical coordinates. The location discovery system used in FreeFall does not use complex and expensive absolute positioning system (GPS) nor direction finding devices. FreeFall has been evaluated through a simulation study where the performances of our system have been compared with significant related works. Our approach shows a decreased energy expenditure over more common solutions for data delivery and an improvement in the endto-end delay when the number of sources is limited.

II. MAIN ASSUMPTIONS

The main assumptions for our framework to be effective are:(i) the network is composed by static sensor nodes and a mobile sink (either a ground robot or a flying drone); (ii) it is dense enough to uniformly cover the whole sensing area given the capabilities of a general sensor networking device; (iii) each node is able to infer the relative position of its neighbors using an r-map [START_REF] Bejerano | Simple and efficient k-coverage verification without location information[END_REF]. The r-map is the implementation of a polar coordinate system specifying the relative location of the neighbors of a node from its point of view. Thanks to the implementation of a r-map, every node i sets its own reference originate axis, later referred as → x i . Through the relative positions of nodes inferred by the r-map, each node i is able to estimate in this reference system for every of its neighbor j both the angle α ij = → x i , → ij and the Euclidean distance d i ij between nodes i and j in the reference system of i. A detailed algorithm for the construction of an r-map is described in [START_REF] Bejerano | Simple and efficient k-coverage verification without location information[END_REF].

III. OUR CONTRIBUTION When a source s has to offload data, it needs to advertise the sink S. As the sink is mobile and s has no information about its mobility pattern, s is not able to reach it directly. It will thus send a request in the network using a source advertisement packet. Specifically we suppose that each advertisement packet is forwarded along two perpendicular directions as in [START_REF] Shi | Double-blind data discovery using double cross for large-scale wireless sensor networks with mobile sinks[END_REF]. Also the sink advertises its position by using a sink advertisement packet. Once again sink advertisement packets are forwarded along two perpendicular directions. Eventually, both source advertisement packet and sink advertisement packet reach a common node that will forward the request to the sink with a backtrace advertisement packet, as illustrated on Figure 1-b. More details about the aforementioned process will be given in the following sections, however, for the sake of clarity the following description is restricted to a single sending direction which forms an angle β with the reference axis → x i of the node i.

Neighbor of interest: Given a node i, a node j is said to be a Neighbour of Interest of node i in respect to the propagation angle β if |β-α i ij | < 90 • and d i ij ×cos(β-α i ij ) < ∆ width,i ; with ∆ width,i set as the communication range of the nodes. As an example, in Figure 1-a, the source node has three neighbors: N 1 , N 2 and N 3 but only N 1 and N 2 are selected as Neighbour of Interest since laying in the ∆ width -wide strip along the direction chosen by the source.

A. Source and sink advertisement packets

Let's assume a source s needs to offload data. First of all node s determines a random direction along which to send its request, identified by the angle β, then determines all its Neighbor of Interest in respect the same angle β and, finally a source advertisement packet is sent every ∆T s adv to the Neighbors of Interest. By properly selecting the Neighbor of Interest it is assured a source advertisement packet is forwarded following the direction which has been previously determined. The source advertisement packet contains the source node ID, the propagation angle β, the list of the forwarders, d trans (si) and d long (si). The meaning of source node ID, the propagation angle β is straightforward. The list of the forwarders is meant to contain the list of the nodes which have already forwarded the packet and it is used for the backtrace process. Of course when a packet is freshly generated this list is empty and it will be populated by the forwarders themselves. d trans (sj) and d long (sj) are the longitudinal and transversal distance between the last node j which processed the packet and the Source s which had generated the packet. More in details, the transverse distance is the distance between node j and its projection on the β axis. The longitudinal distance is the distance between the source and the projection of the node on the β axis. For instance, on Figure 1-a, the transverse distance of N 1 is D 1 and its longitudinal distance is D 2 . Again when a packet is freshly generated those distances are zero. Every time a packet is forwarded by a node j d trans (sj) and d long (sj) are updated accordingly. It should be noted that in very dense networks, where the list of Neighbors of Interest is long it could be important to properly prune that list in order to avoid jeopardizing the scalability of FreeFall. In this work the number of neighbors has randomly selected at each ∆T s adv and a smarter pruning strategy is left as a future work. From its side, the sink applies the same algorithm and issues a sink advertisement packet.

B. Advertisements processing

Upon receiving an advertisement packet a node j first it checks the forwarder list to ensure that the packet it is not a duplicate. If the packet is a duplicate it is discarded and no other action is taken. If it is not the case then node j checks for a matching advertisement, i.e. if the received packet is a source advertisement a corresponding sink advertisement is searched, if the received packet is a sink advertisement a corresponding source advertisement is searched for. If a matching is found a backtrace packet is generated and no other action is taken. If nothing is found in the buffers then node j forward the packets again. In order to do so node j has (i) to determine how the direction β relates to its own reference axis → x j . This can be (a) node-level detail.

(b) network-level detail.

C. Backtrace packet generation and forwarding

When it have both the source and sink advertisement packets, node j has already the estimated transverse and longitudinal distances to the source(s) (d j trans (sj) and d j long (sj)) and the sink(s) (d j trans (Sj) and d j long (Sj)). From them, it can estimate α j (sS) as following:

α j (sS) = β j (S)-β j (s)-arctan d j trans (sj) d j long (sj) -arctan d j trans (Sj) d j long (Sj)
Node j generates a backtrace packet with the sink Id, α j (sS), d j (jS), d j (js) . The backtrace packet is sent back following the reverse path of the sink advertisement.

D. Backtrace Packet reception at sink

The sink takes a decision about its movements every ∆ movement seconds. If one or more backtrace packets have been received during this interval each one of the will be prcessed as follows. Using the laws of sines and cosines the sink extrapolates the remaining angles and sides of the triangle whose vertexes are the original source, the mobile sink and the node which generated the backtrace packet . Hence the sink will be able to calculate the direction and the distance to travel for reaching the source as in Figure 1-b. In case of multiple sources, the node stores information about them and creates a distance-ranked list of way points using simple vectorial operations, closest first Just after the expiration of ∆t movement control the sink set its course to the first node in the list and, upon arrival, starts the data transfer procedure. While in the movement phase the sink will not receive any other packets but will resume the network operation upon arrival and store eventual new information. At the end of the data transfer it will move again to a new destination if present.

IV. RESULTS

We run a set of simulation under the WSNet environment [START_REF] Fraboulet | Worldsens: Development and prototyping tools for application specific wireless sensors networks[END_REF]. We set a topology of 600 nodes distributed uniformly on a 500m × 500m square area . Nodes use a single-channel, ricean faded, 2400MHz bpsk 802.15.4 compliant MAC and radio interfaces. The values of ∆t movement control is set as a 802.15.4 beacon-enabled time-slot and ∆T adv as the former multiplied by the network diameter. We compare FreeFall with (i) our previous GPS-driven approach [START_REF] Zema | Using location services to autonomously drive flying mobile sinks in wireless sensor networks[END_REF], where the nodes use the absolute position system to send the advertisement packets; (ii) the plain Greedy Geographical Routing (iii) a random mobility framework later referred as RandMob where the mobile sink will move randomly around the network and, if it gets into contact with a source, it will start the data offloading procedure. The signaling times are kept the same of the other mobility frameworks. Using FreeFall and GPS-driven, the sinks and the sources signal each other's presence and then the former will reach the selected positions to transfer the data. We are fist interested in the capability of our FreeFall to handle flows of multiple sizes. To this purpose, a source and a sink are set at the two opposite corners of the topology and a bursty, acked application is activated between them. Using the maximum capabilities, in terms of packets size and transmission rate possible for the 802.15.4 MAC, the source have to deliver to the network a stream of packets which sum is respectively of 0.25, 0.5, 1 and 1.5 MB, representing the application data. Each value is the result of a 30 simulative runs which outputs were processed with 95% confidence intervals and shown where applicable. According to [START_REF] Natalizio | Filming Sport Events with Mobile Camera Drones: Mathematical Modeling and Algorithms[END_REF] we set the maximum speed of the sink to 60km/h. Figure 2 displays the time difference, at the source, between the first data packet enqueuing (and the activation of the delivery systems) and the reception of the ack for the last packet. FreeFall shows a great reduction either versus the routed approach and the random mobility. It even outperforms the GPS-driven approach as ,geometrically, the latter configures a specific case of the former when the two corridors intersect at a right angle, maximizing the hop distance. Figure 3 shows the same evaluation in the case of multiple traffic flows with up to 4 source nodes that need to offload 1 MiB of application data. In terms of sheer traffic consumption, the Random Mobility is the best option but, as shown in the figures that the time necessary for complete the transfer up to four sources, is much higher and it represent the possibility of completely missing the source or the data.

V. CONCLUSIONS AND FUTURE WORKS

In this paper, we have introduced FreeFall, a completely distributed, practical signaling and movement protocols for a mobile sink to set a trajectory across the network and perform data collection in a dense Wireless Sensor Network in which nodes have to offload non-negligible amount data. Our system is remarkable because it does not use any absolute positioning system and can be employed without additional cost on the nodes and in all those environments where, for instance, GPS is not available. There are, however, some issues that we plan to address in our future research. A multi-sink variant should be investigated together with a framework to make them interoperate, efficiently schedule the source visitation order and the information buffering space needed to avoid starvation and improve fairness. FreeFall should implement an obstacle avoidance system that would make the packets route around coverage holes and also a careful tune of the parameters, an accurate evaluation of either the mobility inherent cost and the evaluation of a noisy r-map is needed.

Fig. 1 .

 1 Fig. 1. Working Scenario

Fig. 2 .

 2 Fig. 2. Time to end data transfer for different burst sizes.

Fig. 3 .

 3 Fig. 3. Time to end data transfer for different number of sources.

This work has been partially supported by European Union (EU), European Social Fund (ESF), Calabria Local Government and CPER CIA. This paper reflects the views only of the authors, and the EU, the ESF, Calabria Local Government and Inria cannot be held responsible for any use which may be made of the information contained therein.