Michaël Clément

Mickaël Garnier

Camille Kurtz

Laurent Wendling

Color Object Recognition Based on Spatial Relations between Image Layers

Keywords: Object Recognition, Spatial Relations, Force Histograms, Mean Shift Segmentation, Shape Matching

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

Object recognition from color images is an important topic in image analysis that has been largely studied in various imaging domains. The object recognition task is generally performed in three steps [START_REF] Andreopoulos | 50 Years of object recognition: Directions forward[END_REF]: (1) extraction of salient regions using a segmentation algorithm; (2) description of these regions with quantitative features modeling different types of information (e.g., color, texture or shape); (3) recognition of the objects of interest by classifying the characterized regions. A limit of this approach is that these different types of features (and their combinations) are sometimes not discriminant enough to successfully describe the content of complex objects, in particular when they are represented by color images.

For the last decades, the spatial disposition of objects in a scene (or between object subparts) has received much attention in the domain of image analysis [START_REF] Santosh | Symbol recognition using spatial relations[END_REF][START_REF] Morales-González | Simple object recognition based on spatial relations and visual features represented using irregular pyramids[END_REF]. Moreover, it has been stated that structural relations between image components are fundamental in the human perception of image similarity. Therefore, the spatial relations between the regions composing an object can be considered as im-portant features to recognize the nature of the object itself. However, as far as we know they are rarely used for color object recognition.

Literature about spatial relations for image analysis can be structured in two main categories: qualitative and quantitative approaches. Qualitative approaches use symbolic relations such as positioning (left, right, below, etc.) or topological relations (inside, outside, etc.) [START_REF] Egenhofer | A formal definition of binary topological relationships[END_REF][START_REF] Inglada | Qualitative spatial reasoning for high-resolution remote sensing image analysis[END_REF]. When dealing with complex objects, it is necessary to capture a precise description of their different structuring patterns, and to characterize both large-scale and low-scale directional relations. Besides, depending on the content meaning, these patterns may be represented by unconnected subsets of pixels. Therefore, in our context the spatial relations cannot be summarized in a symbolic manner. Quantitative approaches gather methods that precisely describe the relative positions between objects. Fuzzy quantitative methods are popular in different application domains such as spatial reasoning in medical images [START_REF] Bloch | Directional relative position between objects in image processing: A comparison between fuzzy approaches[END_REF][START_REF] Bloch | Fuzzy spatial relationships for image processing and interpretation: A review[END_REF] or handwritten symbol recognition [START_REF] Delaye | Fuzzy relative positioning templates for symbol recognition[END_REF]. These methods produce a fuzzy landscape per considered potential direction, but combining them in order to capture the omnidirectional spa-tial organization of possibly sparse objects is not obvious. Another quantitative strategy is based on the model of force histograms [START_REF] Matsakis | A new way to represent the relative position between areal objects[END_REF], thereafter noted F-Histograms. This model handles sparse object descriptions and summarizes their relative position in a single histogram. Basically, an F-Histogram between two objects is a circular distribution measuring their relative attraction along every desired directions.

Based on this model, the authors of [START_REF] Garnier | Object description based on spatial relations between levelsets[END_REF] proposed a new object descriptor called F-Histogram Decomposition (FHD). The key idea of this descriptor is to encode the pairwise spatial relations between disjoint layers of pixels composing an object using F-Histograms. This work led to encouraging results, showing the interest of considering an homogeneous representation of directional spatial relations for object description. However, this approach has been proposed only for gray-level images, and the decomposition strategy does not consider the content of the image to create the layers, but "hard" pixel layers based on pre-defined image intensity values. Consequently, this approach cannot straightforwardly deal with complex color images.

In this article, we present an extension of this approach for the recognition of complex objects in color images. The contributions of this article are twofold. First, we propose an extension of the FHD descriptor for color textured images by considering a robust object decomposition strategy. This "content-based" decomposition strategy relies on a combination of the Mean Shift segmentation algorithm coupled to the K-Means clustering algorithm enabling to extract binary image layers supposed to represent relevant object subparts. Second, we present different strategies for the comparison and matching of FHD descriptors. Given two objects to be compared, the idea is to align the different image layers based on various types of information (i.e., luminance, shape), before comparing their corresponding F-Histograms. These matchings, which involve F-Histogram matrix reorganizations, enable to enhance FHD comparisons supported by dissimilarity computations in the context of color images. These contributions allow for robust structured object recognition from complex images. This article is organized as follows. Sec. 2 introduces our method for color object description based on spatial relations between image layers. Sec. 3 describes the experimental validations carried out with this method on two color image datasets. Conclusions and perspectives will be found in Sec. 4.

METHODOLOGY

First, we briefly recall the F-Histograms model (Sec. 2.1). Afterwards, we present our strategy for the decomposition of color objects into structural layers (Sec. 2.2). Then, the FHD object descriptor for color images is presented (Sec. 2.3). Finally, we propose different matching strategies for the efficient comparison of such FHD descriptors (Sec. 2.4).

Force Histograms Background

An F-Histogram allows to assess the directional spatial relations between two binary objects [START_REF] Matsakis | A new way to represent the relative position between areal objects[END_REF]. It relies on the definition of a force of attraction between points. Given two points located at a distance d from each other, their force of attraction is defined by ϕ r (d) = 1 d r where r characterizes the kind of force processed. When r = 0, all points are treated with equal importance (constant force), whereas when r = 2, more importance is given to closer points (gravitational force). Instead of directly studying all pairs of points between the two objects, the force of attraction between two segments is considered. Let I and J be two segments on a line of angle θ, D θ IJ the distance between them and |.| the segment length. The force of attraction f r of I with regard to J is given by:

f r (I, J) = |I|+D θ IJ +|J| D θ IJ +|J| |J| 0 ϕ r (u -v) dv du. ( 1
)
Given two binary objects A and B, a θ-oriented line in the image forms two sets of segments belonging to each object: C A = ∪{I i } i=1..n and C B = ∪{J j } j=1..m (see Fig. 1). The mutual attraction between these segments is defined as:

F(θ, C A , C B ) = ∑ I∈C A ∑ J∈C B f r (I, J).
(2)

Then, the set of all θ-oriented parallel lines C θ going through the whole image, gives us the global attraction F AB (θ) between A and B along a direction θ. Finally, the F-Histogram F AB is obtained by computing F AB onto a set of angles θ ∈ [-π, +π], summarizing the relative position of A and B. By axiomatic definitions of the function F, the following properties, useful to characterize similar patterns, can be verified [START_REF] Matsakis | A new way to represent the relative position between areal objects[END_REF]: translation invariance as objects are processed independently of their location in the image, symmetry considering opposite directions, scale invariance if the histograms are normalized and rotation invariance (after circular shifts), because the approach is isotropic.

Decomposition into Image Layers

In order to capture the inner spatial relations structuring an object, we first have to decompose it into distinct subparts. To this end, we use a decomposition strategy based on a segmentation algorithm. However, in our context, the subparts of the object can be composed of disconnected sets of pixels. Consequently, we couple our segmentation strategy to a clustering algorithm enabling to reconstruct the different structural image layers of the object.

Color Image Segmentation

Color image segmentation is still an open research issue and no generic robust algorithm exists yet. In this work, we choose to employ the Mean Shift algorithm [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF] which has been successfully used during the last decade for both the classification and the segmentation of textured color images. The Mean Shift segmentation algorithm performs as follows. Let I be an input color image (see Fig. 2 (a)).

For a given pixel of I, this algorithm builds a set of neighboring pixels within a given spatial radius h s and color range h r . The spatial and color center of this set is then computed and the algorithm iterates with this new spatial and color center. A third parameter M allows to define the minimum size of the regions to be kept after segmentation. The Mean Shift segmentation algorithm produces a set of R non-overlapping segments S i modeling a partition of I, and exposing homogeneous color properties (see Fig. 2 (b)).

Color Image Layers Reconstruction

Resulting from the Mean Shift segmentation, a structural subpart of the object can be disconnected in different segments (e.g., see the orange parts on the butterfly wings in Fig. 2 (b)). Thus, our goal is to reconnect the segments sharing similar color intensity values into the same structural layers. Consequently, we apply the classical K-Means clustering algorithm on the R image segments S i issued from the Mean Shift segmentation, to automatically reconstruct the structural layers of the object. The K-Means algorithm has been used with N seeds to produce N clusters of segments sharing similar color properties in the RGB space. These clusters of segments model the N structural layers C i of the object (see Fig. 2 (c)). Note that any clustering algorithm could be used.

F-Histogram Decomposition

Once the object has been decomposed into N structural layers, we then compute an F-Histogram between every pair of layers (C i ,C j ) according to the strategy proposed in [START_REF] Garnier | Object description based on spatial relations between levelsets[END_REF]. The color F-Histogram Decomposition (FHD) of an object depicted in an image I is thus the set defined as:

F C i C i r ∀i∈{1..N} shape ∪ F C i C j r ∀(i, j)∈{1..N} 2 , j>i spatial relations . (3)
These F-Histograms can be represented as a matrix (see Fig. 3) encoding N shape descriptors (when i = j), and N(N -1)/2 spatial relations descriptors between pairwise layers (when i > j). An F-Histogram computed on a layer with itself induces a natural overlapping, only allowing to use a constant force of attraction (i.e., r = 0). In this study, for comparability and normalization purposes, we also use a constant force for spatial relations F-Histograms, resulting in an homogeneous descriptor.

As a consequence of F-Histograms properties, FHD descriptors are naturally translation invariant and symmetric. Depending on the application requirements, scale invariance is obtained by normalizing the F-Histograms, and rotation invariance can be pursued by estimating their mode or by minimizing the distance between shifted FHD descriptors.

Comparison of FHD Descriptors

Comparing FHD descriptors can be done by evaluating the dissimilarity between the two matrices of F-Histograms, using a distance metric. Based on the results of [START_REF] Garnier | Object description based on spatial relations between levelsets[END_REF], we use the χ 2 distance to compare pairwise F-Histograms. Given two F-Histograms F A and F B computed along θ max directions, the χ 2 distance between them is defined as:

d χ 2 (F A , F B ) = θ max ∑ i=0 (F A (i) -F B (i)) 2 F A (i) + F B (i) . ( 4
)
As noted before, the FHD descriptor includes both shape descriptions (on the diagonal) and pairwise spatial relations (on the upper triangle). The semantic meaning of these descriptions being different, we can split the overall distance metric into two distinct parts, that is, for two FHD descriptors Q and T :

D(Q,T ) = αD shape (Q, T ) + (1 -α)D spatial (Q, T ),
(5) where the distance between shapes and the distance between spatial relations are respectively defined as:

D shape (Q, T ) = 1 N N ∑ i=1 d χ 2 F C i C i Q , F C i C i T , (6)
D spatial (Q, T ) = 2 N(N -1) N ∑ i=1 N ∑ j=i+1 d χ 2 F C i C j Q , F C i C j T , (7)
and with α ∈ [0, 1] balancing the weight given to shape descriptions compared to spatial relations. In the experimental section of this paper, we study the influence of this parameter on the retrieval results. This approach for comparing FHD descriptors is only relevant if the underlying image layers structuring the two objects are correctly aligned in the two matrices. On the contrary, if the underlying image layers are misaligned (see Fig. 5), the induced FHD descriptors will lead lead to meaningless pairwise comparisons. This case is particularly likely to occur since we are dealing with color images, given that there is no natural order between image layers associated with intensity values in the RGB space.

C 1 C 2 C 3 C 1 C 2 C 3 Object A Object B
Figure 5: Illustration of a typical case where similar objects described with FHD descriptors can be incorrectly compared due to a misalignment of their structural layers.

Therefore, before applying the pairwise dissimilarity measure described above, it seems crucial to employ a matching strategy between the structural layers of the objects. Finding such a matching between two FHD descriptors is a combinatorial problem (for N layers, there exists N! possible matchings), but the complexity of it can be effectively reduced by making assumptions on the underlying image layers. Thereafter, we propose different matching strategies based on specific alignments of the image layers. In our approach, FHD descriptors are computed only once, and the matching step only requires reorganizations of the F-Histograms matrices.

Color-based matching This matching strategy is based on the assumption that corresponding layers in the two objects will be similar in terms of colorimetry. To this effect, the image layers of each FHD descriptor are sorted according to the luminance value of the pixels composing the clusters issued from the decomposition step. An illustration of the color-based matching strategy is shown in Fig. 4 (a). This strategy being based on the decomposition step only, it can be applied prior to the computation of the descriptors. Therefore, no dynamic reorganization is required and the corresponding F-Histograms in the two descriptors can be compared in a simple pairwise manner.

C 3 C 2 C 1 C 2 C 1 C 3 C 1 C 2 C 3 C 1 C 2 C 3 (a)
Shape-based matching Another approach when comparing two FHD descriptors is to assume that the corresponding layers in the two objects will be similar in terms of shape. Fig. 4 (b) illustrates the principle of this matching strategy: each layer is matched with the one presenting the closest shape F-Histogram. To apply this strategy, we can assimilate it to an optimization problem where the goal is to minimize the overall distance D shape (Q, T ) between shape F-Histograms in two FHD descriptors Q and T . The exact solution requires the enumeration of the N! matching possibilities and can be considered as an optimal matching (from an optimization point of view). It is obviously not suitable for FHD descriptors of arbitrary number of layers. An approximate solution consists in matching the layers sequentially in a greedy manner. That is, for each layer of Q, we pick the closest layer of T in terms of distance between their shape F-Histograms.

From an algorithmic point of view, this only requires a quadratic computational time, and can be considered as a good compromise. These shape-based matching strategies (optimal and greedy) require a dynamic reorganization of the F-Histogram matrices during the comparison process.

The choice of a matching strategy is strongly application dependent, and each strategy presents its downsides and benefits. While the color-based strategy is simple and can be considered as a preprocessing step, it will fail if the color is not a discriminative feature (e.g., if two objects have a similar structure but different colors). On the other hand, the idea of matching the layers according to their shape is more relevant, but with a higher computational complexity and an increased sensibility to noise.

EXPERIMENTS

We involved the presented framework in object recognition and retrieval tasks from color images.

Datasets

We used two datasets of color images: a collection of butterfly images and a collection of motorbike images. Samples of these datasets are shown in Fig. 6. As we focus on the proposition of a new descriptor for object recognition, we choose to validate this approach on specific datasets where the objects are depicted on an homogeneous background, avoiding any object detection issues.

The Peale dataset is a subset of the Peale collection1 and is composed of 318 color butterfly images grouped in 28 classes according to their species, each class containing a variable number of butterflies. Butterflies are a typical case where inner spatial relations are a distinguishing feature making the wings patterns a direct link with the species. The same database limited to grayscale images was previously used in [START_REF] Garnier | Object description based on spatial relations between levelsets[END_REF] to introduce FHD descriptors and to assess the descriptive strength of the spatial relations.

The Motorbikes dataset is a subset of a collection of various motorcycles from the side made available by Caltech2 . Our subset is composed of 265 motorbikes images with an homogeneous background. As for the butterflies, motorbikes are an interesting case where the shape and spatial disposition of the wheels, body and engine parts are discriminative features. We manually labeled the motorbikes into five categories: cross, cruiser, moped, sport and standard.

Protocol and Setup

For each dataset, object recognition is performed using the nearest neighbor strategy. The label of the closest image in the feature space spanned by FHDs is assigned to the object to be recognized. We used a leave-one-out cross validation strategy, that is, for each test image, the remaining of the dataset serves as training data. The quality of the results is then evaluated using classical quality indexes: the global recognition rate R , and the class-by-class F-Measure F1.

The robustness of our approach with regard to the decomposition step has been evaluated by studying the influence of the Mean Shift parameters (h s , h r and M), as well as the number of clusters N used for K-Means, producing different scales and levels of object decompositions, and resulting in FHD descriptors of different sizes. The minimum size of the regions has been set to M = 100, and the spatial bandwidth has also been set to h s = 8 (neighborhood of 17 × 17 pixels, see [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF]), according to the average size of the images in the datasets. For global evaluation, we assigned an equal weight (α = 0.5 in Eq. 5) to shapes and spatial relations. The influence of this parameter is also studied in a class-by-class manner. Besides, all F-Histograms are computed along 180 directions, regularly spanning the [0, 2π[ interval.

Results

Influence of the decomposition step Tab. 1 presents the recognition rates obtained on the two datasets for different object decomposition methods. The first row presents the results obtained by considering the original version of FHDs applied on graylevel images using quantized level-sets [START_REF] Garnier | Object description based on spatial relations between levelsets[END_REF]. The remaining rows show the results obtained by considering our extension of FHDs for color images. We observe that our extension performs better than the original gray-levels version. This confirms our hypothesis that considering a content-based decomposition strategy yields more relevant image layers. Besides, according to the different Mean Shift results, we can deduce that for these two specific datasets, it is more suitable to adopt an oversegmentation strategy.

Influence of the matching strategy Tab. 2 presents the recognition rates for the different matching strate- gies on the two datasets. The first row shows the results obtained with the color-based matching strategy while the remaining rows present the results obtained with the shape-based matching strategies (greedy and optimal). On the Peale dataset, we can observe that the color-based strategy performs globally better than the shape-based ones for all values of N. This may be due to the fact that for most species of butterflies, the color of each layer is one of the most discriminative feature. On the contrary, on the Motorbikes dataset the best scores are mostly obtained with the optimal shape-based strategy. These results confirm that the shape-based strategy is more adapted to recognize objects where color is less discriminative. On this dataset, the greedy version of the shape-based matching produces comparable results to the optimal one, but with a much lower computational cost. Fig. 7 also present the class-by-class F 1 scores obtained for the different matchings on the Motorbikes dataset, showing notably that the greedy strategy does not always perform worse than the optimal one.

Influence of the α parameter We also studied the impact of the parameter α representing the weight given to shapes compared to spatial relations (see Eq. 5). Instead of setting α = 0.5 as in the previous experiments, we evaluated the best local weights for each class of the dataset. We exhaustively computed the class-by-class recognition results for varying values of α ∈ [0, 1] with a step of 0.02. For each class i, we record the α i values leading to the best local recognition rate for this specific class. Fig. 8 presents the result of this study on the Peale dataset. This figure highlights the idea that depending on the class, spatial relations or shape descriptions can be more or less discriminant features. Among the 28 classes of this dataset, about one third is more oriented towards spatial information, another third towards shape information, and the rest is balanced between both.

Qualitative evaluation Fig. 9 shows some representative object retrieval results. Color-based matching was used on the Peale dataset (with N = 3), while shape-based matching was used on the Motorbikes dataset (with N = 4). Comparative study We compared the results obtained in this study to the ones obtained with the GFD [START_REF] Zhang | Shape-based image retrieval using Generic Fourier Descriptor[END_REF] and dSIFT [START_REF] Bosch | Scene classification via pLSA[END_REF] descriptors with the same experimental protocol. The GFD is derived by applying two-dimensional Fourier transform on a polar-raster sampled image. Note that GFDs exclusively encode shape information. The computation of GFDs requires to set the radial and the angular resolutions (R and T ). In our experiments, GFDs are computed with R = 4 and T = 9, thus giving a signature of 36 bins. Dense SIFTs are extracted with a step of 16 pixels and at two scales,

DISCUSSION

This article has introduced a novel approach for object recognition in color images. The main originality of this approach lies in the extension of an object descriptor using both shape and relative spatial information about the subparts of the object to be recognized. These subparts are obtained by considering a content-based decomposition relying on the combination of an image segmentation algorithm and a clustering algorithm. This decomposition strategy makes it possible to deal with the problem raised by the textural properties of the objects in color images. Experimental validations on two datasets have shown that describing objects with such shape and spatial relations features between structural image layers yields interesting recognition results. Our work presents some limitations. From a methodological point of view, the image decomposition approach could be affected by the clustering step, which is based on color information. For instance, if different subparts of an object share the same color, it will lead to inconsistent image decompositions. In addition, the number of resulting clusters has to be set a priori and can be not adapted to the described object. From an applicative point of view, the datasets used were relatively small and present high intra-class variance making it difficult to accurately evaluate the behavior of our method.

In the future, we plan to enhance the FHD descriptor by considering a multi-layer strategy where the number of layers extracted per image may be automatically adapted depending on the image content. We also plan to involve this framework into biomedical object recognition tasks where the object of interest can be mixed up with the background.

Figure 1 :

 1 Figure 1: The force of attraction between A and B along the direction θ is the integral sum of forces computed on longitudinal cuts (C A ,C B ).

  Query image I. (b) Mean Shift segmentation. (c) Reconstruction with K-Means.

Figure 2 :

 2 Figure 2: Illustration of the color image decomposition into structural layers.

Figure 3 :

 3 Figure 3: Force Histogram Decomposition (FHD) of an object. An F-Histogram is computed between every pair of layers (C i ,C j ) issued from the image decomposition step.

Figure 4 :

 4 Figure 4: Illustration of the two proposed FHD matching strategies.

Figure 6 :

 6 Figure 6: Samples from the Peale and the Motorbikes datasets: butterfly from different species and motorbikes from different categories.

Figure 7 :

 7 Figure 7: Class-by-class F 1 scores obtained for the three matching strategies on the Motorbikes dataset.

Figure 8 :

 8 Figure 8: Best α weights obtained for each class of the Peale dataset (with N = 3). Classes are sorted by increasing values of α. Lower values indicate a stronger weight on spatial relations, while higher values indicate a stronger weight on shape descriptions.

Figure 9 :

 9 Figure 9: Retrieval results for the Peale and the Motorbikes datasets. Query images are depicted in the left column. Dissimilarity rankings go from lowest (left) to highest (right).

Table 1 :

 1 Evolution of the recognition rate R for different decomposition methods, by varying the number of layers N.

				R (Peale)				R (Motorbikes)
	Decomposition / N	2	3	4	5	6	2	3	4	5	6
	Grayscale level-sets	26.1	30.7	31.9	37.4	40.8	65.2	59.1	58.1	55.6	63.1
	Mean Shift (h r = 4)	42.8	45.0	44.0	42.8	45.0	69.8	70.9	63.8	63.8	63.0
	Mean Shift (h r = 8)	47.5	35.8	42.1	38.4	35.5	67.2	64.9	63.0	54.0	54.3
	Mean Shift (h r = 12)	39.9	32.4	36.2	31.1	25.2	65.3	63.4	67.2	67.2	66.0

Table 2 :

 2 Evolution of the recognition rate R for the different matching strategies, by varying the number of layers N.

				R (Peale)				R (Motorbikes)
	Matching strategy / N	2	3	4	5	6	2	3	4	5	6
	Color-based	42.8	45.0	44.0	42.8	45.0	69.8	70.9	63.8	63.8	63.0
	Greedy shape-based	41.2	45.0	34.3	34.3	30.8	67.9	64.9	62.6	54.0	54.3
	Optimal shape-based	42.1	40.6	39.3	35.2	33.0	69.8	66.8	64.2	67.2	66.0

Table 3 :

 3 Recognition rates R for dSIFT, GFD and FHD. For each keypoint of the query image, the matching algorithm searches for the best keypoint in the target image. If the resulting match gives a good contrast, this point vote goes to the target image. The finally matched image is the one with the highest votes. Tab. 3 presents the recognition rates obtained with these two methods, compared to the best results obtained with FHD descriptors. The results obtained with both GFDs and dSIFTs are slightly lower than the ones obtained with the proposed color FHD descriptors, showing that FHDs are more suited to recognize complex structured objects where spatial organization is a discriminative feature.

		GFD dSIFT FHD
	Peale	28.6	43.4	47.5
	Motorbikes 65.7	50.9	70.9
	4 and 8, giving both local information and a more global one.

http://clade.ansp.org/entomology

http://vision.caltech.edu/archive.html

ACKNOWLEDGEMENTS

This work was sponsored by the French National Research Agency project SPIRIT #11-JCJC-008-01.


Kévin Huguenin

Anne-Marie Kermarrec

Eric Fleury

Route in Mobile WSN and Get Self-Deployment for Free

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction & Background

Consider a troop of human agents deployed in a region to accomplish a mission and assisted by a set of networked mobile devices, whose mobility is controlled (as opposed to mobility imposed by the entity on which they are embedded). An agent may order a mobile device close to him to perform an action at a given location of the region. Note that the action can eventually be performed by any node of the system. This is achieved by routing to this specific point. To perform routing a node can either (i) perform the action itself if possible, (ii) forward the request to another node or (iii) move. Such systems have numerous applications, a typical one being a situation where a military unit secures a sensible zone with the help of mobile sensors able to move, detects enemies (sensors) and raises the alarm. Another possible application is the case of a brigade of firefighters with mobile air-pressurized water autonomous fire extinguisher. It enables robots to be deployed in a zone where human cannot be yet. Once the robots have secured this zone (say extinguish the fire), the robots can then self-deploy to monitor the zone.

Similarly to traditional static sensor networks, the coverage of the region and the connectivity of the system reflect the quality of the deployment. Even though any point can be reached irrespective of the deployment by having nodes move, the movements incur delays. A routing algorithm must be evaluated against two metrics: reactivity in a dynamic scenario (when the troop progresses in the region, referred as the transient state) and self-deployment in a stable scenario (when the troop secures the zone inside which it is deployed, referred as the steady state).

The aforementioned applications require a routing algorithm capable of leveraging the node's communication and sensing capacities as well as the nodes's mobility to fulfill a request from a user, at any position. On one hand, a large amount of research has been devoted to finding deployments that ensures the connected coverage of a region of interest (ROI), thus leading to the design of optimal configurations [START_REF] Bai | Deploying wireless sensors to achieve both coverage and connectivity[END_REF]. Although self-deployment techniques allow us to autonomously reach such configurations by the mean of robotic sensors [START_REF] Jarvis | Connectivity-guaranteed and obstacleadaptive deployment schemes for mobile sensor networks[END_REF], they require an a-priori knowledge of the ROI at each node and are therefore not able to deal with evolving region and dynamic sensor relocation. Moreover, a traditional static (i.e. which does not leverage the node mobility) routing algorithm may not be able to cope with disconnected network or sensing node outside of the network scope. In [START_REF] Butler | Controlling mobile sensors for monitoring events with coverage constraints[END_REF], Butler and Rus considered a similar application. Assuming that sensors are notified of events occurring in their environment, Butler and Rus proposed an efficient decentralized self-deployment algorithm making the nodes converge reactively in the most interesting portions of the region while still ensuring full coverage. Yet powerful, this algorithms may not match our applicative context since (i) it requires an underlying protocol to advertise to the nodes the location of relevant events and (ii) it does not address the problem of routing in this context.

On the other hand, a lot of research on routing in disconnected networks and Delay Tolerant Networking [4] (DTN) in Mobile Ad-Hoc Network [START_REF] Mauve | A Survey on Position-Based Routing in Mobile Ad-Hoc Networks[END_REF] (MANET) have been conducted. That led to the design of efficient routing algorithms and powerful mobile computing systems, such as Car-Tel [START_REF] Hull | Cartel: a distributed mobile sensor computing system[END_REF]. Yet, except from message ferrying approaches -which exploit mobile nodes with uncontrolled but predictable mobility [START_REF] Zhao | A message ferrying approach for data delivery in sparse mobile ad hoc networks[END_REF][START_REF] Zhao | Controlling the mobility of multiple data transport ferries in a delay-tolerant network[END_REF], and MORA [START_REF] Burns | Mora routing and capacity building in disruption-tolerant networks[END_REF] -a motion planning based routing algorithm -which exploits the controlled mobility of a small set of autonomous agents; these algorithms cope with the node uncontrolled mobility rather than leveraging it for routing purposes.

To the best of our knowledge, the two research topics of mobile routing and self-deployment have been mostly studied independently. Our claim is that using a routing algorithm leveraging the node mobility allows to cope with dynamic ROI, inefficient deployment of the nodes and under-dimensioning (i.e. the number of sensors is not sufficient to coverage the ROI in a connected way). In addition, it provides self-deployment for free in steady state.

Our contribution is two-fold. First we present Grasp, a simple routing algorithm acting only with local knowledge of the network and no knowledge of the ROI (i.e., the nodes do not know its size, its shape or its borders) and prove that beyond its simplicity Grasp ensures both sensing request fullfilment with probability one regardless of the network configuration, and a convergence toward connected-coverage of the ROI with a required number of node close to the optimal in steady state. Then we investigate the properties required for a generic mobile routing algorithm to provide self-deployment. We demonstrate by considering practical matters that Grasp may be used in a real-environment. We focus on 2D ROIs. The analysis of 1D shows that Grasp is optimal, details are provided in [START_REF] Huguenin | Route in Mobile WSN and Get Self-Deployment for Free[END_REF].

The rest of the paper is organized as follow: Section 2 presents the design rationale behind Grasp along with the detailed algorithm. Section 3 provides a theoretical analysis of Grasp with respect to the self-deployment properties. Section 4 presents experimental results obtained through computer simulations that match the theoretical analysis. This section also gives a performance analysis of Grasp with respect to (i) its efficiency in terms of routing delays and energy, and (ii) its impact on the network topology in terms of self-deployment. Sections 5 tackles the practicality of Grasp by suggesting an algorithm to handle concurrent message routing and a sleep-wakeup scheme leveraging the network geometry resulting from Grasp to increase the system lifetime. Finally, we provide in Section 6 a list of perspectives and on-going work to increase Grasp performance.

GRASP: A Routing Algorithm for Mobile WSNs

As stated in the introduction, neither traditional routing algorithms nor selfdeployment techniques can be used for the targeted applications. In this section we present Grasp, a routing algorithm leveraging the node mobility to cope with dynamic ROIs and sparse or non-homogeneous deployments.

System model

We consider a network of mobile entities with wireless communication capabilities deployed in an obstacle-free region. We assume a disc model for sensing (i.e., a node is able to sample its environment up to a distance r s from its current position) and symmetric reliable communication links. In the sequel we denote by routing the action of making any node fulfill a sampling request, i.e., sense at a given location in the ROI, emitted at a given node in the network. We further assume that nodes are able to orientate and localize themselves inside the ROI by the use of a compass and a localization system such as a GPS or a distributed location algorithm [START_REF] Kwon | Resilient localization for sensor networks in outdoor environments[END_REF]. In addition, we assume that they also know their neighbors' coordinates, using for instance periodic beacons.

Design rationale

The design rationale behind Grasp can be explained through the analogy with a soccer game. In a game, a set of mobile intelligent entities, namely the players, are deployed on a rectangle area, the pitch, and collaborate in order to deliver a packet, the ball, at a given position, the goal. To succeed, the players can either run or pass the ball to a team-mate provided that the distance between them is not too large. Obviously, passing the ball to a team-mate is less tiring than running to put the ball in the goal. In this context, the energy constraint is that the players must keep the ability to move until the end of the game. On one hand, the players must pass the ball as often as possible so as to save their energy, but on the other hand, at some point, a player's reachable team-mates may all be in worst position than himself to reach the goal. Two questions arise: assuming a limited view of the game and limited passing capabilities, (i) "to which of its reachable team-mates should a player pass the ball?", and (ii) "when should a player move instead of passing?" Following this analogy, we propose a simple geographic routing algorithm leveraging nodes mobility to transparently cross holes in the topology. Nodes act greedily for both forwarding and moving: the distance between the current position and the destination should always be decreasing. If the destination lies in the sensing disc of the node in charge of the request (i.e., its distance to the destination is lower than r s ), the node fulfills the request itself. If not, it can either forward the message or move as follow:

Forward: using local information on its neighbors' position, which is updated by means of periodic beacons, the node in charge of the message picks the closest node, and closer than itself, to the destination -if any -and forwards. Move: otherwise, the node starts moving in straight line toward the destination until it can either forward the message to a node closer than itself to the destination or sense itself at the destination. The node stops and performs the adequate action.

Algorithm 1 gives a detailed pseudo-code version of Grasp. Figures 1(a)-1(c) illustrate the way Grasp deals with routing holes as compared to traditional static geographical routing algorithms [START_REF] Fang | Locating and bypassing routing holes in sensor networks[END_REF] (such as GPSR [START_REF] Karp | GPSR: greedy perimeter stateless routing for wireless networks[END_REF]) and Figure 1(d) shows a sample path -combining both forwarding and moving -used by Grasp to deliver a message in a sparse 2D mobile WSN.

d (x, x dest ) end if
The strengths of the algorithm described above are its simplicity and the resulting characteristics. First, no assumption is made on the radio communication model. More specifically, the traditional unit disc model is not assumed and the communication range is not explicitly used by the algorithm. Actions are only based on a pure localized and distributed information built from periodic beacons advertising the identifier and the position of a node.

The second important characteristic relates to the deployment: Grasp acts with zero knowledge on the ROI. Grasp is purely distributed and decentralized. Its ultimate goal is to allow an action to be performed at any location of the ROI. The deployment of the nodes is not explicitly controlled by the geographical shape of the ROI but by the application requirements. If an agent needs an intervention at specific positions, it sends requests toward these positions. Nodes route requests and thus potentially move in order to satisfy them. The deployment of the nodes is dynamic and self adapts to the shape and to any potential evolution of the ROI.

Assuming no packet loss and no node failure Grasp provides sampling request fullfilment with probability one, regardless of the number of sensors: at each step the distance between the node in charge of the message and the destination is reduced either by moving toward the destination or by forwarding the message to a closer node. Therefore, Grasp outperforms traditional geographic routing as it takes benefit of the nodes mobility to overcome dead-end routes. On the other hand, Grasp transparently increases the coverage by automatically filling routing holes. Intuitively, a node is required to move when the area between itself and the destination does not contain any other node. Therefore, moving toward the destination fills the routing hole. More concretely, Grasp offers a spreading property in the sense that, in addition to filling routing holes, when making a node move, it may not get closer to any other node than a given distance called repulsion radius, close to the communication radius (a closed form expression of the radius is given in Section 3.1). Moreover, the deployment of nodes is on demand. Such a reactive behavior does not require any specific hole detection or a pre-deployment computation phase. In addition, all properties of Grasp hold with evolving, in shape and size, regions of interest without explicitly requiring to be aware of such changes.

Note that we do not establish one rigid path from one node to another: routing a packet from the same source node to the same destination may require some nodes to move. This is not a burden as most of the targeted applications require to send an order without expecting an answer right away. For instance, the ultimate goal of our example application is to have any node check at a given location and raise an alarm if required but not to send back any specific piece of information.

Theoretical analysis

In this section, we present a theoretical analysis of our routing protocol for mobile WSN with respect to self-deployment.

We denote by an stable deployment a network configuration in which any point of the ROI can be reached (by forwarding and then sensing), without requiring any node to move, while using the greedy routing algorithm presented in Section 2. Due to the greedy nature of the forwarding algorithm, such a configuration should provide full greedy-connectivity. Our analysis considers the case where the sensing radius r s is equal to the communication range r c . We make assumption on the disk model only to derive analytical results. Note that relaxing the assumption r s = r c = R impacts on the optimal configuration but the general sketch of the proofs still holds. The purpose of this paper is not to study exhaustively all the possible ratio values between r s and r c but to present a formal framework for Grasp. We prove that Grasp converges, to a sub-optimal stable configuration (i.e. a stable configuration using the 1.5 times the minimum number of nodes) provided that the number of nodes is sufficient.

Background

A recent study by of Iyengar et al. [START_REF] Iyengar | Low-coordination topologies for redundancy in sensor networks[END_REF] explores the problem of the optimal deployment of a static WSN ensuring a connected-coverage of a region (i.e., full coverage with full connectivity) focusing on the case r s = r c = R. Using geometric considerations, they derive a lower-bound on the optimal node density to cover a zone in a connected way and they propose a strip-based configuration which tightly approaches the bound. In addition the strip-based configuration is asymptotically optimal. This configuration is composed of horizontal connected strips spaced by 1 + √ 3/2 R. This way, any two nodes on the same line can communicate. On the other hand, a vertical strip of nodes connects the horizontal strips together ensuring the full connectivity of the network. However, a greedy geographic algorithm may not be able to reach any point of the ROI. In their work, Iyengar et al. considered full connectivity which characterizes a configuration where there exists a path between any two nodes. However, our work focuses on network deployment where a greedy geographic algorithm can find a path between any two nodes. The full greedy connectivity can be formalized as follow: for any destination point of the ROI, any node x 0 in the network can communicate with a node x 1 closer to the destination than x 0 . Based on this definition, it can be proved [START_REF] Huguenin | Route in Mobile WSN and Get Self-Deployment for Free[END_REF] that the hexagonal lattice (see Figure 2(b)) is the optimal deployment ensuring both full greedy-connectivity and the required density of sensors to cover the area using this mesh is 4 √ 3/9R 2 . In addition this configuration ensures full coverage of the ROI provided that the sensing radius is greater or equal to the communication radius.

Proof of convergence

A first evidence is that nodes can not get closer from each other than a given characteristic distance δ called the repulsion radius. Consider a node x 0 moving toward a point of the ROI x dest . Node x 0 crosses the communication disc of a node x 1 if its distance to the destination when it enters in x 1 's communication disc is smaller than the distance between x 1 and x dest . That is, using the notations in Figure 3(a):

y ≥ R 2 -δ 2 + y 2 -δ 2 .

This inequality holds for any y

≤ R / 2 1 -(δ/R) 2 . The condition y > R implies δ > √ 3 2 • R.
Therefore, even if a node x 0 may cross the R-disc centered on a node x 1 when traveling toward its destination x dest , the distance between x 0 and x 1 stays always larger than

√ 3 2 • R.
We denote by repulsion radius this minimum distance. Note that the repulsion radius is smaller than the communication radius. One may thus model all nodes by physical soft balls of radius ranging from

√ 3 2 R 2 to R 2 .
Based on the physical model analogy, running Grasp on a mobile WSN can be thought of as packing a set of balls inside a given frame [START_REF] Lubachevsky | Spontaneous patterns in disk packings[END_REF]. As one may recall, the intrinsic action of Grasp on mobile nodes is rather to push them than to pack them. Each couple (x 1 , x 2 ) of two adjacent balls (d(x 1 , x 2 ) ≤ R) presents two attraction sites (see Figure 3(b).) An attraction site is a place where the probability to move, in order to sample a location behind the line x 1 x 2 , is null. Note that such a position also minimizes the size of the associated Voronoï region (the set of destinations making a node located at this position move to fulfill a sampling request.) If a ball x 0 is not located in an attraction site, in other words, if it is not adjacent to both x 1 and x 2 but only to one of them (x 2 without loss of generality) then for each sampling location behind the line x 1 x 2 , it has a strictly positive probability to move. More precisely, if the sampling location is located on the left of the median of [x 0 x 2 ] and behind the line x 1 x 2 , the probability to move is non null (related to the hatched area on Figure 3(c).) Moreover, moving toward a sampling location inside this area pushes the node closer to the attraction site and the ball x 0 then touches x 1 . During the process, additional nodes may also arrive and stick to one another. Eventually, all nodes will converge to an attraction site with no more possibility to escape. Such final configuration is the well-known stable triangular lattice. Note that we do not claim that only triangular tiles can be formed but rather that they are the most likely to be formed. More specifically, hexagonal tiles allow greedy routing (as shown in the previous paragraph) and require less nodes but they are not stable. Effectively, small deviations on the nodes' position in an hexagonal tile may lead to a reconfiguration of the tile into a triangular-like tile: a node routing toward the opposite node in the hexagon would move and stop near the center of the hexagon forming equilateral triangles.

Simulation results

In this section we present the results of computer simulations and show that they closely match the theoretical analysis conducted.

Experimental setup

In order to stretch the self-deployment capabilities of Grasp, sensor nodes are deployed uniformly at random in a restricted area of the ROI. The considered region is a square folded into a torus shape (note that we use a toric ROI for the sake of simplicity, using a square ROI only causes minor changes on the geometric deployment pattern near the borders.) It requires 500 nodes to be connected-covered, with respect to the expressions of optimal density given in Section 3. In order to assess the threshold beyond which Grasp converges, we consider several values of ρ = N/N opt , close to 1.5. This enables us to study the behavior of Grasp under slight under or over-dimensioning in the number of nodes. The results can be used to evaluate the impact of failures on the deployment. The system dynamic is controlled, via Grasp, by message emission. We use a constant message emission rate λ, uniform amongst the nodes. Thus, during one time unit λ • N messages are routed from a randomly chosen node drawn from a uniform distribution on the full set of nodes to a destination drawn from a uniform distribution on the entire ROI. For the sake of simplicity, we consider the routing of one message at a time, the case of concurrent routing being tackled in Section 5.1. In this context, we evaluate Grasp's behavior and convergence properties along the following metrics:

× x 1 x 0 x dest δ R y (a) x 1 x 2 (b) x 1 x 2 x 0 (c)
Average distance covered per node to deliver a message d: this metric reflects the uniformity of the node deployment and thus the distance between the current configuration and the optimal deployment. An optimal deployment being a network configuration where any point of the ROI can be reached without moving, d should decrease to zero as time tends to infinity (assuming a constant emission rate λ) provided that the number of nodes is sufficient. In addition, assuming that a move is much more time-consuming than a wireless transmission, this metric reflects (i) the global mechanical (i.e., the movement) energy consumption of the system and (ii) the average delivery delay.

Distribution of the average distance covered by a node to deliver a message p D : this metric brings additional information on the network load. More specifically, it reflects how the mechanical energy consumption is distributed amongst the nodes. The probability density function of d in a stable configuration is an impulse, located at zero.

Probability that at least one node moves to deliver a message p m : the order of magnitude of the delivery delay is dependent on whether the messages are delivered using only wireless communication or by moving to cross routing holes, regardless of the distance covered. Thus, p m is a good indicator of the system quality of service provided by the system, dual to d.

Evaluation

We present simulation results obtained by averaging over 25 runs of Monte-Carlo simulations. In each configuration, the metrics are computed by running 20 × N independent simulations. For instance, d is evaluated by averaging the distance covered by a nodes to deliver 20 × N random messages. Evolution of the network topology Figure 4 depicts the evolution over time of the network topology. To match our theoretical analysis, we consider in this experiment 1.5 times the number of nodes required for an optimal deployment with the minimum number of nodes. We observe that starting from a localized initial deployment over the ROI, Grasp converges to a stable deployment (i.e., connected-coverage). Figure 4(a) shows that the first stages of the deployment spread the nodes inside the entire ROI. Figures 4(b)-4(d) illustrate the aggregation process and the final configuration described in Section 3.1.

Average distance covered Figure 5(a) depicts the evolution of the average distance covered by node to deliver a message d. We consider a network with a number of nodes equal to ρ = 1, 1.25, 1.5 and 1.75 times the optimal. As expected from Section 3.1, d tends to a non-null limit for ρ < 1.5 and to zero otherwise. This matches the theoretical results, since the triangular lattice formed by Grasp requires 1.5 the minimum number of nodes to ensure greedy connectedcoverage. Yet after 20 iterations, d ≈ 4.10 -4 R (when ρ = 1.5 and 2.10 -4 R when ρ = 1.75) which is negligible: for a radius of 100m, each node would be expected to move on average of 4cm. Note that using only 17% (1.75/1.5) more nodes than needed reduces the average distance covered by a node by 50%.

Network load Figure 5(b) depicts the distribution of distances that nodes need to cover to deliver a packet after 20 time units. When the number of nodes is sufficient for Grasp to converge (i.e., ρ ≥ 1.5), the curves are decreasing and show that convergence is in progress. The high fraction of nodes which never move (up to 30% for ρ = 1.5) together with the shape of the histogram reflects the existence of large greedy-connected components with low redundancy inside each of them: the nodes inside the greedy connected components never move and the ones on their border moves to ensure connectivity between the components. The fact that the distance covered by the node is very low (at max 1% of the communication radius for ρ = 1.5) implies that the components are spatially extended, reflecting a low redundancy (with respect to the initial deployment where most of the nodes never move but where the ones that move cover on average 1/4th of the ROI.) When the number of nodes is not sufficient for Grasp to converge (i.e. ρ < 1.5), the network load has a bell-shape with a maximum at d = 25.10 -5 R (for ρ = 1), a heavy tail for the large values and a non-negligible fraction of still nodes (15% for ρ = 1.) Therefore the network load in terms of distance covered is well balanced between the nodes. Thus the energy needed for routing is evenly shared between a large fraction of the nodes resulting in an extended lifetime of the system. Probability to move Figure 5(b) presents the probability that at least one node moves to deliver a message for a number of nodes sufficient for Grasp to converge. With the minimum number of nodes (ρ = 1.5), p m decreases quickly to 20% and then converges slowly to zero. For slightly higher values of ρ, the first decreasing stage is drastically speeded-up: p m ≈ 2% after less than 20 iterations.

Summary

Simulations confirmed the theoretical results presented in Section 3. Grasp requires only 1.5 the minimum requested number of nodes to converge resulting in a triangular lattice deployment. Not only do we believe that this is a reasonable bound but this increased number of nodes is leveraged in several ways. First, the triangular lattice provides, over the other regular lattices (including the hexagonal optimal deployment), an increased resilience to failure as each node is provided with two potential neighbors in any direction. Second, as we will explain in Section 5.2, the fact that the triangular lattice is a subgraph of the hexagonal one can be exploited by a clever sleep-wakeup scheme to increase the lifetime of the system of 50%, fully justifying the 1.5 number of nodes over the minimum.

Considering practical matters

Most of the results presented above are of theoretical nature, yet we believe that Grasp can be efficient in practice. So far, we have assumed that only one routing operation was processed at a time, Section 5.1 provides an algorithm to handle concurrent routing operations as this will happen in practice. Second, Section 5.2 provides a sleep-wakeup scheme which improves the system lifetime.

Handling concurrent routing

So far, only one sensing request at a time was considered. This simplifying assumption allowed us to derive formal proof of convergence of the network topology but might be restrictive. In this section, we consider concurrent routing operations. Grasp should keep ensuring that (i) routing operations eventually succeed and (ii) two nodes should not get closer to each other than a fixed repulsion radius. We propose a set of modifications to Grasp so that such properties are still ensured and discuss their efficiency with respect to delays and distance covered.

Priority queue We assume that each node maintains a queue of messages ordered by priority. To each message is associated a Time from Emission (TFE), updated every time a message is inserted or extracted from the priority queue. The message with the highest TFE being the head. The node movement is driven by the message being processed, namely the queue's head. Note that the number of older messages than a given message is finite and decreasing. This ensures that the delivery of messages is eventually guaranteed regardless of the heuristic chosen to forward the message.

Opportunistic forwarding

The simplest forwarding heuristic is to choose a static node to forward to. A less conservative heuristic is to forward a message to a node which is closer to the destination and, if moving, gets closer to the destination. To this end, nodes exchange their speed vector, piggybacked in beacons and fully characterized by the node's position and the destination of the current message being processed. A third heuristic, ensuring the repulsion radius between any pair of nodes, consists in considering the case of two moving nodes running into each other. Under this heuristic, two nodes getting in contact should be repulsed from one another, in analogy to the billiard model [START_REF] Lubachevsky | Spontaneous patterns in disk packings[END_REF]. To this end, the two nodes exchange their positions and their current head (destination and age). The node the closest to the destination of the oldest head takes over all the messages and start processing them. The second node merely stops. This ensures that the two nodes are moving away from one another.

Sleep-wakeup

As proved in Section 3 and demonstrated in Section 4, a network of more than 1.5 the optimal number of nodes running Grasp converges to a triangular like lattice. Interestingly enough, the triangular lattice is a subgraph of the optimal hexagonal one. Based on this remark, we propose a simple but yet powerful sleep-wakeup scheme leveraging the network topology to increase the system lifetime. The triangular lattice (Figure 6(a)) is the union of three hexagonal lattices (Figures 6(b)-(d)), each node of the triangular lattice belonging to exactly two of them. Our sleep-wakeup scheme can be described as follow:

Clustering: the first step is to detect the triangular lattice-based components, the sleep-wake up algorithm being executed independently in each one of them. We assume that each node maintains the identifier of the component it belongs to. A node is able to determine if it is located at the center of an hexagonal tile using its neighbor's coordinates. A node at the center of an hexagonal tile sets its component identifier to its own identifier and forwards it to its neighbors forming the hexagonal tile. Otherwise, the component identifier remains unset. Upon reception of such a message, a node updates its component identifier if it is still unset or lower than the one received. Only nodes located at the center of an hexagonal tile forward it to hexagonal tile vertices. Otherwise, the message is ignored. Eventually, the nodes inside a triangular-lattice based component share the same component identifier. The node whose identifier is the one of the component is the natural leader of the component. This clustering task is periodically executed.

Sleep-wake up periods: each triangular component of the network alternates between three hexagonal configurations in a round-robin manner. The leader (node L in Figure 6) is in charge of spreading the sleep messages to the centers of the hexagonal tiles of the current configuration. The effect of a sleep message is to put in sleep mode the node receiving it for a given period of time. Leveraging the geometry of the network, the spreading of sleep messages can be done optimally with respect to the number of packets sent. For the sake of readability, the leader L is reported in the three figures as a reference point. In each configuration, one third of the nodes are asleep and the communication graph is an hexagonal lattice.

Consider a system with the minimum required number of nodes deployed on an hexagonal lattice and assume that each node has a lifetime of one time unit, the system lifetime being also one time unit. Now, consider a system of 1.5N opt nodes using the sleep-wakeup scheme presented above. Setting its working period (the time length during which the system stays in each of the three configurations) to 0.25 time unit, the global system lifetime is extended to 1.5 time units (i.e. six periods). Effectively, each node is asleep two periods out of six yielding a total number of awake periods of four, that is one time unit. In other words, the additional number of nodes over the optimal, namely 1.5, is fully leveraged by increasing the lifetime of the system up to 1.5.

Conclusions & future work

In this paper, we considered a network of mobile wireless sensors. Their mobility being controlled, we proposed Grasp, a novel and simple stateless algorithm which leverages nodes mobility to route sensing requests. Grasp transparently adapts to evolving region of interest, with respect to size or shape, without requiring to be explicitly aware of such changes. Our algorithm is independent from the communication medium and uses very simple forwarding and motion planning techniques. Thus it is directly applicable to any low capabilities wireless network. Assuming a disc model for communications and a random choice of the sensing locations inside the region of interest, we proved that a network running Grasp converges to a configuration ensuring greedy-connected coverage of the region. In that sense, the simplest routing algorithm leveraging nodes mobility provides the network with self-deployment properties for free. The number of nodes required to ensure convergence is 1.5 the optimal. Our simulation results matched our theoretical analysis. Finally, we provided Grasp with an ad-hoc sleep-wakeup scheme extending the system lifetime up to 50% without jeopardizing the greedy connected-coverage. This fully justifies the overhead factor to the optimal number of nodes. We also tackled concurrent requests routing. We plan to investigate these two tracks and evaluate Grasp behavior using a more realistic model for wireless communications.

Fig. 1 .

 1 Fig. 1. Illustration of a routing hole in a WSN. (a) Node x0 is closer to the destination x dest than its neighbors making greedy routing fail. (b) Face-based routing algorithms route along the edges bordering the void while (c) Grasp leverages the node mobility to move toward the destination until greedy forwarding is possible. (d) Sample path using Grasp. Dashed lines denote greedy forwarding and solid lines and arrows denote respectively hole circumventing and moving.

Figure 2

 2 (a) depicts the strip-based deployment. In [1], Bai et al. extended those results by proving the asymptotic optimality of the strip-based deployment pattern for any r c /r s < √ 3 (not only r c = r s ).

  (a) Strip deployment (b) Hexagonal deployment.

Fig. 2 .

 2 Fig.2. Node deployments ensuring (a) asymptotically optimal connected-coverage and (b) optimal greedy connected-coverage.

Fig. 3 . 3 2

 33 Fig. 3. Repulsion radius and attraction sites: (a) two nodes running Grasp cannot get closer than δ = √ 3 2 R ; (b) the two points which forms, together with x1 and x2, an equilateral triangle are attraction sites where a node does not need to move to route a message behind the line (x1x2). (c) Routing toward a destination in the hatched area forces x0 to move. Plain lines delimit the Voronoï region associated to the nodes.

Fig. 4 .

 4 Fig. 4. Evolution of the network topology over time. A hundred nodes are initially uniformly deployed on a small area (1/100th) of a 2D toric ROI. The message emission rate is set to λ = 10. The plain lines represent the communication graph. For the sake of simplicity, edges between border vertices are not represented. Note the existence of an hexagonal tile and a few square tiles in the communication graph.

Fig. 5 .

 5 Fig. 5. Evaluation of Grasp in a 2D toric ROI: (a) average distance covered per node (relatively to R) as a function of time (λ = 1) ; (b) load distribution in the systems with respect to the average distance to be covered by a node to deliver a message (relatively to R) ; and (c) the probability that Grasp uses mobility to deliver a message as a function of time (λ = 10).

L

Fig. 6 .

 6 Fig.6. Sleep-Wakeup scheme: (a) nodes inside a triangular lattice adopt in a cyclic manner three sleep-wakeup policies (b),(c) and (d). For the sake of readability, the leader L is reported in the three figures as a reference point. In each configuration, one third of the nodes are asleep and the communication graph is an hexagonal lattice.

  Algorithm 1 Grasp: A routing algorithm for mobile WSN Input: upon reception of a sampling request (for position x dest ) at node x0 while d (x0, x dest ) > rs and / ∃x ∈ neighborhood (x0) | d (x, x dest ) < d (x, x0) move toward x dest end while if d (x0, x dest ) ≤ rs then sample x dest else {exists a node in x0's neighborhood closer to x dest than x0} forward to argmin

x∈neighborhood(x 0 )


Xuan Truong Nguyen

Virginie Griseri

Laurent Berquez

In-Situ Space Charge Measurements on Dielectrics during Electronic Irradiation by PEA

come

In-Situ Space Charge Measurements on Dielectrics during Electronic Irradiation by PEA X.T. Nguyen, V. Griseri Abstract-Material used is space environment are submitted to a large amount of charged particles. This work is focused on the effect of electrons on PolytetraFluoroEthylene (PTFE) that is commonly found in satellites pieces of equipment. To study the behavior of electrons during and post-irradiation we are mainly using the Pulse Electro Acoustic (PEA) technique in an open configuration. Measurements are performed between two periods of irradiation under vacuum. The space charge profiles obtained are analyzed to understand materials charging phenomena. In the present work we focus our studies on a discharge phenomenon that occurs as soon as the surface potential reaches a threshold value.

I. INTRODUCTION

Polymeric materials are commonly used in spacecraft arrangements because they offer appropriate thermal properties [START_REF] Griseri | Behavior of dielectric in a charging space environment and related anomalies in fight[END_REF]. However due to their dielectric nature they can store charges such as electrons that are present in space environment. The accumulation of charges is possible up to a critical level above which electrostatic discharge occurs. To prevent such violent and disturbing phenomena many studies on those materials are realized in laboratories. In our case we are studying the behavior of electrons post-irradiation by measuring the space charge distribution by the Pulse Electro-Acoustic (PEA) device. In the present work we focus our attention on low energy electrons and discharges phenomena that are occurring at regular intervals during irradiation.

II. EXPERIMENTAL SET-UP

A. The Irradiation Chamber: MATSPACE

The irradiation chamber MATSPACE has been developed in the laboratory a few years ago [START_REF] Griseri | Charge build-up and transport in electron beam irradiated polymers in a new irradiation chamber[END_REF]. It is equipped with a thermionic electron gun. The energy of these electrons can be controlled in the range [10 -100 keV]. The flux of the beam reaching the target is obtained by measuring the current collected with a Faraday cage arrangement connected to a picoampermeter. The electrons beam can be focused or spread thanks to an electromagnetic lens. The larger area that can be covered by the beam is of about 10 cm diameter. Therefore, all the detection pieces of equipment must be located in this area in order to perform various measurements under the same conditions.

B. The Pulse Electro Acoustic Set-up

The PEA device is based on the non-contact model [START_REF] Maeno | Open-PEA system for space charge measurement in dielectrics under irradiation[END_REF][START_REF] Perrin | Measurement of internal chargedistribution in dielectric using the pulsed electro-acoustic method in non-contact Mode[END_REF]. The sample is glued on the bottom electrode to get a good contact and allows the transmission of the acoustic signal. The top electrode is positioned in front of the irradiated electrode between two periods of irradiation to perform measurements. The electrode is located a few millimeters above the surface

III. EXPERIMENTAL RESULTS AND DISCUSSION

A. The Experimental Protocol

In the present case, PolytetraFluroEthylene (PTFE) samples have been studied. 198 and 225 m thick samples from two sheets have been selected for each experiment. The irradiation and measurement alternation was repeated several times. In the first set of experiment PEA measurements were realized after 2 minutes of irradiation and after 30 s for the second set. In each case, the electron energy was fixed to 30 keV and the flux of the beam was of about 1 nA/cm 2 .

B. Space charge profile analysis

Before recording space charge profile by PEA on irradiated materials it was necessary to record a reference signal. To do so the sample was glued on the back electrode and coated on the opposite surface. A polarization voltage of 1 kV was applied to the sample thanks the metallization whereas the pulse probe voltage of 900 V was brought by the contactless electrode. Due to the air gap between the sample and the electrode the pulse voltage reaching the sample is reduced to 43 V but it remains large enough to get a proper reference signal (Fig. 1). The sample thickness of the reference specimen was of about 198 m. After the first two minutes irradiation the first PEA space charge profile was recorded. The signal after deconvolution is reported in figure 2. A negative peak due to the injected electrons is detected near the irradiated surface whereas a positive peak of induced charges is detected on the back electrode. Due to the sample arrangement the acoustic signal due to the injected electrons is double in amplitude [START_REF] Wadamori | Proposal of numerical analysis model of acoustic wave propagation and generation on PEA method[END_REF]. As expected, the amplitude of the peaks is increasing with the irradiation time. It is noteworthy that the peak of induced charges is really narrow compared to the peak due to the injected electrons. This is due to the properties of PTFE that induce attenuation and dispersion of the acoustic waves in the bulk. In this paper no treatments have been applied to counterbalance these effects. After 8 min irradiation the signal amplitude decays drastically (Fig. 3). In this case a positive peak appears at the interface sample vacuum. Due to the acoustic wave total reflection at that interface a negative peaks appears at 223 m. This peak must not be considered. The extraction of negative charges from the sample was suspected to occur in the vacuum direction. This measurements show that the departure of negative charges near the surface is compensated by the presence of positive entities.

The irradiation procedure alternated with PEA measurements was carried on. Results are reported in figure 4 and5. As before the space charge profile starts to grow-up to a certain extend then decays suddenly. In the charge profile recorded at 12 min and 16 min no positive peaks appear at the irradiated surface. We can expect that even if positive charges are present at the interface they might not be distinguished from negative charges as in the previous cases (after 8 min irradiation) as only the mean charge is observed. Furthermore after charge extraction if the irradiation is continued the positive charges are rapidly recombined with injected electrons and cannot be detected (Fig 45).We must notice that charging and discharging phenomena occur in less than 4 min irradiation in this case. Between 18 and 26 min the electron injection is continued (Fig. 6) and a new discharge is observed for 28 min irradiation (Fig. 3). To get a better understanding of the discharge phenomena the surface potential reached after irradiation was estimated from PEA results by a double integration of the charge density profiles. In figure 7 it can be seen that the potential is decreasing linearly with the irradiation time. The charging slope is changing slightly between two period of discharge. A threshold above which negative charges are extracted seems to be highlighted. Above 16 kV negative charges are suddenly extracted and positive charges appear. To observe positive charges the measurements must be taken in a short interval. In fact, as already mentioned, between 10 and 12 min or 15 and 16 min a negative charge extraction had probably occurred and the charging initiated again. This graph shows also that another discharge had occurred between 16 and 18 min as a small voltage decay is observed. At last, above 32 min irradiation discharges seems to appear in each 2 min interval of electron injection. To determine the mechanism responsible for the charge extraction a new set of experiment was performed. In that case, a tiny change was introduced in the set-up configuration. The PEA bottom electrode was raised above the grounded sample holder for about 1 mm. The aim was to take away the irradiated sample surface from a ground metallic surface. Furthermore the small camera attached on the lateral irradiation chamber window was switched on during irradiation. Space charge profiles obtained look similar to the one recorded and described just before (Fig. 8). In the present case the irradiation time between two measurements was reduced to 30 s to be able to follow the charging discharge process. Surprisingly the first discharge phenomenon occurred after only two minutes of irradiation. In this part of the experiment the electron beam flux was slightly higher than 1 nA/cm 2 and was at the origin of the faster charging process. At that stage, thanks to the camera, we noticed the apparition of a flash at the sample surface that was long enough (in the order of 1 s) to be observed on the recorded film. This observation confirms that the charge extraction occurred from the sample to vacuum and not through the bulk. The space charge profile (Fig. 9) indicates that after 2 min a part of the electron have been replaced by positive charges at the sample surface. The same procedure was continued and the same observation repeated (Fig. 10, 11, 12). As the lighting flash was observed just at the end of the 3 min 30 s irradiation the observed positive peak on the PEA profile was of the highest in amplitude we get (Fig. 9). After the next two discharges (7 min 30 s and 12 min 30 s) electron storage has started again as we cannot detect any positive charges on the profile but only two negative peaks in the irradiated area.

If we analyze the evolution of the surface potential (Fig. 13) we can see that once again there is a linear decrease versus the irradiation time. In the present case the potential reached before discharge occurs seems to be slightly higher than in the previous set of experiment. The maximum value recorded was around 28 kV before discharge. As the sample is irradiated on the whole surface and as the discharge occurs in vacuum surface we suspect that there is a discharge toward the grounded metallic sample holder plate through the sample. When the critical voltage value is reached electrons are extracted to the surrounding grounded area. As we increased the distance between the sample surface and the ground the voltage can goes up slightly before breakdown. This means that discharges occur at the sample boundary. The use of broader specimen is not appropriate to prevent such bypass in our case as the entire sample is irradiated. Another solution consists in leaving more space between the sample and the ground or to use a mask to protect the sample hedge during electron injection. IV. CONCLUSIONS In this work space charge measurements by PEA in the open configuration on PTFE irradiated sample have been realized. It has been shown that when electrons are injected near the surface the surface potential grows quickly. The risk of discharges through the specimen edge occurs as soon as a critical value, that depend on the distance between the surface and the ground, is reached. Positive charges appear at the sample surface. To prevent such unwanted phenomena, the best solution would consist in protecting the sample edge from the irradiation with a mask during bombardment or insulate the sample for the surrounding grounded area by increasing the distances.

Fig. 1 .

 1 Fig. 1. PEA charge density signal recorded on a PTFE 198 m thick and used as reference in an open configuration. The sample is submitted to 1 kV polarization voltage and 900 V pulse voltage. The electric field and potential are calculated from the charge density profile

2013Fig. 2 .

 2 Fig. 2. In-situ PEA space charge profile recorded after various irradiation period [2-6 min] with a 30 keV electron beam energy on a PTFE sample 198 m thick.

Fig. 3 .

 3 Fig. 3. In-situ PEA space charge profile recorded after various irradiation period [8-28-36 min] with a 30 keV electron beam energy on a PTFE sample 198 m thick.

Fig. 4 .Fig. 5 .

 45 Fig. 4. In-situ PEA space charge profile recorded after various irradiation period [10-12 min] with a 30 keV electron beam energy on a PTFE sample 198 m thick.

Fig. 6 .Fig. 7 .

 67 Fig. 6. In-situ PEA space charge profile recorded after various irradiation period [18-26 min] with a 30 keV electron beam energy on a PTFE sample 198 m thick.

Fig. 8 .

 8 Fig.8. In-situ PEA space charge profile recorded after irradiation from 30 s to 1 min 30 s with a 30 keV electron beam energy on a PTFE sample 225 m thick.

Fig. 9 .

 9 Fig.9. In-situ PEA space charge profile recorded after discharge phenomena between two period of irradiation under a 30 keV electron beam energy on a PTFE sample 225 m thick.

Fig. 10 .

 10 Fig. 10. In-situ PEA space charge profile recorded after irradiation from 2 min 30 s to 3 min 30 s with a 30 keV electron beam energy on a PTFE sample 225 m thick.

Fig. 11 .

 11 Fig. 11. In-situ PEA space charge profile recorded after irradiation from 4 min 30 s to 7 min with a 30 keV electron beam energy on a PTFE sample 225 m thick.

Fig. 12 .Fig. 13 .

 1213 Fig. 12. In-situ PEA space charge profile recorded after irradiation from 8 min 30 s to 11 min 30 s with a 30 keV electron beam energy on a PTFE sample 225 m thick.

  , L. Berquez

	Université de Toulouse, UPS, CNRS, INPT; LAPLACE (Laboratoire Plasma et Conversion d'Energie)
	118 route de Narbonne, F-31062 Toulouse Cedex 9, France