Bérengère Mathieu
email: berengere.mathieu@irit.fr

Alain Crouzil
email: alain.crouzil@irit.fr

Jean Baptiste Puel

ASARI: A New Adaptive Oversegmentation Method

Keywords: Graph-based oversegmentation, Superpixels, Local Ternary Patterns

Using superpixels instead of pixels has become a popular pre-processing step in computer vision. However, there are few adaptive methods able to automatically find the best comprise between boundary adherence and superpixel number. Moreover, no algorithm producing color and texture homogeneous superpixels keeps competitive execution time. In this article we suggest a new graph-based region merging method, called Adaptive Superpixel Algorithm with Rich Information (ASARI) to solve these two difficulties. We will show that ASARI achieves results similar to the state-of-the-art methods on the existing benchmarks and outperforms these methods when dealing with big images.

Introduction

The idea and definition of superpixel is given for the first time by Ren et al.,[START_REF] Ren | Learning a classification model for segmentation[END_REF]. The two authors describe a segmentation method including an oversegmentation pre-processing grouping pixels into small homogeneous and regular regions called superpixels. Currently, oversegmentation is an active research field, with steady publication of new methods [START_REF] Achanta | SLIC superpixels compared to state-of-the-art superpixel methods[END_REF][START_REF] Conrad | Contour-relaxed superpixels[END_REF][START_REF] Machairas | [END_REF]. Some examples of oversegmentation results are given in Fig. 1. A good oversegmentation method must satisfy five properties: validity (an oversegmentation must be an image partition into connected components), boundary adherence (superpixels must not overlap different objects of the image), conciseness (an oversegmentation must give as few superpixels as possible), simplicity (the number of neighbors of each superpixel must be as small as possible, to avoid a complex adjacency graph), efficiency (an oversegmentation algorithm must have an execution time as low as possible). We call adaptivity, the fact that an algorithm is able to find the best compromise between these two properties, reducing the number of superpixels in wide homogeneous regions and increasing it to segment correctly thin details.

Oversegmentation algorithms may be region-based [START_REF] Achanta | SLIC superpixels compared to state-of-the-art superpixel methods[END_REF][START_REF] Liu | Entropy rate superpixel segmentation[END_REF], when clustering pixels, or boundary-based [START_REF] Conrad | Contour-relaxed superpixels[END_REF][START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF], when focusing on edge evidence. The review of Stutz [START_REF] Stutz | Superpixel segmentation: an evaluation[END_REF] shows that five methods achieve similar results and outperform other algorithms: the Felzenszwalb et al. algorithm (FZ) [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF], Quick Shift (QS) [START_REF] Vedaldi | Quick shift and kernel methods for mode seeking[END_REF], Entropy Rate Superpixels (ERS) [START_REF] Liu | Entropy rate superpixel segmentation[END_REF], Simple Linear Iterative Clustering (SLIC) [START_REF] Achanta | SLIC superpixels compared to state-of-the-art superpixel methods[END_REF] and Contour Relaxed Superpixel [START_REF] Conrad | Contour-relaxed superpixels[END_REF]. The FZ [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] and ERS [START_REF] Liu | Entropy rate superpixel segmentation[END_REF] algorithms use a graphbased representation of the image G < V, E >, where V is the set of elements to be grouped (i.e. the pixels) and E, the set of edges linking pairs of neighboring elements. Each edge is weighted using a dissimilarity measure. FZ uses a predicate checking that the dissimilarity between elements along the boundary of two components is greater than the dissimilarity between neighboring elements within each of the two components, to produce a partition of G into K connected components corresponding to superpixels. ERS is a greedy algorithm selecting a subset A ⊂ E and removing these edges. The result is a partition of G, which maximizes an entropy rate. The QS method [START_REF] Vedaldi | Quick shift and kernel methods for mode seeking[END_REF] is a modification of the medoid-shift algorithm to efficiently find modes of a Parzen density estimate P . Color and location of each pixel are used as feature vectors that are clustered by linking each vector to its nearest neighbor which increases P . The SLIC method [START_REF] Achanta | SLIC superpixels compared to state-of-the-art superpixel methods[END_REF] is an adaptation of the k-means algorithm. Starting from an image oversegmentation into a regular grid, the average color and location features of each superpixel are computed. Then, each pixel is re-assigned to the most similar superpixel and the average features of superpixels are re-computed. The CRS algorithm [START_REF] Conrad | Contour-relaxed superpixels[END_REF] finds a partition S into superpixels, which has a high likelihood of having generated the observed image. Starting from an initial segmentation into rectangular superpixels, CRS maximizes the probability function by reallocating some boundary pixels to another superpixel. In our evaluation, we add to these five state-of-the-art methods, WP, a watershed transformation based algorithm recently suggested by Machairas et al. [START_REF] Machairas | [END_REF].

The main contribution of this article is a graph-based oversegmentation method (Sect. 2), called Adaptive Superpixel Algorithm with Rich Information (ASARI). As its name suggest, ASARI is able to adjust the size and the number of superpixels to fit the image complexity, partitioning uniform objects (like the sky) in a few large superpixels and producing a lot of thin superpixels to match with small details. In addition, ASARI groups pixels using both color and texture information, without dramatically increasing the computation time. The only oversegmentation algorithm using texture has been proposed by Ren et al. in [START_REF] Ren | Learning a classification model for segmentation[END_REF]. Unfortunately, its high execution time discouraged its usage in practical applications. Using Stutz benchmark [START_REF] Stutz | Superpixel segmentation: an evaluation[END_REF], we show in Sect. 3 that ASARI is competitive with the state-of-the-art methods. However, the benefit of this new algorithm is more significant on a new dataset, that we recently made available: Heterogeneous Size Image Dataset (HSID). Contrary to other oversegmentation evaluation datasets, HSID contains photographs having extremely different sizes (from some thousand to several millions of pixels) and a majority of big images. This leads us to an interesting application of ASARI, as a preprocessing step in the Superpixel Classification based Interactive Segmentation (SCIS) method [START_REF] Mathieu | Segmentation interactive pour l'annotation de photographies de paysages[END_REF].

ASARI: A Region Merging Algorithm

ASARI is a region-merging algorithm, following the approach of Salembier et al. [START_REF] Salembier | Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval[END_REF], which is still the base of successful works in image analysis [START_REF] Li | Region-based urban road extraction from VHR satellite images using binary partition tree[END_REF][START_REF] Xu | Connected filtering on tree-based shape-spaces[END_REF]. Let G 0 =< V 0 , E 0 > be a graph related to an image I, where V 0 is the set of vertices and E O the set of edges connecting them. Each vertex v i corresponds to a pixel or a small group of pixels and there is an edge (v i , v j ) between each pair of neighboring pixels or regions. A region merging algorithm with G 0 as input, produces a graph G K =< V K , E K >, where V K is a partition of V 0 into connected components and E K is a subset of E 0 . More concretely, some vertices of G 0 are merged and edges linking them are removed. Salembier et al. [START_REF] Salembier | Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval[END_REF] show that such an algorithm can be defined by a merging order (the order in which the edges are processed), a merging criterion (how to decide if an edge must be removed) and a region model (how to represent the union of two vertices).

Merging order -Merging order in the case of an oversegmentation algorithm must ensure that visually similar regions will be merged, while maintaining regions with reasonably similar areas. We associate to each vertex v i a variable ∆ i referring to the number of times v i has been previously selected. At the beginning of each iteration, the algorithm selects the vertex with the smallest ∆ i (when several vertices have the same ∆ i value, one is arbitrary chosen). ASARI merging order keeps among the set of edges linking v i to its neighbors, the one maximizing a similarity measure f sim . Whether v i and its most similar neighbor are merged or not1 , ∆ i is incremented.

Similarity measure -When designing ASARI, one of our objectives was to propose a similarity measure using both color and texture features and keeping reasonable execution times (a few seconds on a desktop computer, for images of size 3000 × 4000). So, we chose the Local Ternary Patterns (LTP) [START_REF] Tang | Topology preserved regular superpixel[END_REF] largely for their rapidity. The LTP of a pixel p is a pair of identifiers, (LT P N , LT P P ), corresponding to gray level variations of its 8-neighborhood. Let T = {g 0 , • • • , g 7 } be the set the gray levels of the 8 neighbors of p. The identifiers are given by:

LT P N (p) = 7 n=0 2 n δ(p -g n ) and LT P P (p) = 7 n=0 2 n δ(g n -p) ( 1
)
where δ is a threshold function, returning 1 if its input is greater than a threshold ω LT P , 0 otherwise. In the binary representation of LT P N and LT P P , digits equal to 0 correspond to neighbors with gray levels similar to the center gray level. So, pixels with a pair of LTP identifiers equals to (0, 0), have a neighborhood with similar gray levels. The ratio between the number of this kind of pixels and the total number of pixels in a region gives the probability for the region to be textured or not. If this probability is lower than a threshold ω tex , the region is textured. We assume that a similarity measure must give a low value when comparing a textured region to an untextured region. Let f c (i, j) be a colorbased similarity measure between regions v i and v j , f t (i, j) be a texture-based similarity measure, and h be a binary function, returning 1 for a textured region, 0 otherwise. The similarity function is the following:

f sim (i, j) =        f c (i, j) if h(i) + h(j) = 2 f t (i, j) + f c (i, j) 2 if h(i) + h(j) = 0 0 otherwise. (2)
Let c i be a vector containing the normalized average color of v i :

f c (i, j) = exp(- 1 N c ||c i -c j || 2 ) ( 3
)
where N c is the length of c i . Let t i be the concatenation of the normalized histograms of LT P N and of LT P P , for the region v i . We have:

f t (i, j) = exp(- 1 N t (t k i -t k j ) 2 t k i + t k j ) (4)
where N t is the number of strictly positive bins in t i or t j and the superscript k denotes the k-th element of the vector. Notice that f t is derived from the χ2 measure. Distinguishing between textured and untextured regions reduces the execution time of ASARI, the computation time for f c being significantly lower than for f t .

Merging criterion -A merging criterion g(i, j) must ensure both visual consistency and regularity of the region and can be expressed by the following boolean function:

g(i, j) = g sim (i, j) ∧ g reg (i, j) (5)
where g sim checks that similarity between the two regions is greater than a threshold ω sim and g reg verifies that the new region size is not disproportionate to the size of the other regions, using a threshold ω reg . So we have:

g sim (i, j) = f sim (i, j) > ω sim and g reg (i, j) = (φ(i)+φ(j)) < ω reg M M n=0 φ(n) (6)
where φ(i) is the number of pixels belonging to v i and M the number of regions.

The adaptive nature of ASARI results from g sim function, which stops merging in image parts containing small distinct details. The function g reg prevents a segmentation-like behavior and ensures that superpixel sizes remain much smaller than object areas. ASARI stops when any edge cannot be removed any more or when all vertices have been selected 10 times 2 .

Initialization -To produce V 0 , we use the SLIC algorithm [START_REF] Achanta | SLIC superpixels compared to state-of-the-art superpixel methods[END_REF], which has the two benefits of drastically reducing the number of initial regions and simplifying the use of the texture similarity measure, which requires at least one hundred of pixels to give a significant histogram. The drawback of this approach is to introduce two more parameters, ω min and ω comp , which must be designed to produce very small regions. Parameter ω min gives an average region size and parameter ω comp is the SLIC compactness parameter [START_REF] Achanta | SLIC superpixels compared to state-of-the-art superpixel methods[END_REF].

Parametrization -ASARI has 6 parameters: ω LT P , ω tex , ω sim , ω reg , ω min and ω comp . As these parameters impact different aspects of ASARI, sometime related to contradictory properties (like conciseness and boundary adherence), it is not simple to learn them at once. We processed in three steps, first with parameters linked to untextured region detection (ω LT P , ω tex ), then setting SLIC parameters (ω min , ω comp ) and finally focusing on thresholds for the merging criterion (ω sim , ω reg ). Parameters ω LT P = 19 and ω tex = 0.8 have been learned by solving an intermediary classification problem of small patches extracted both of Wikimedia Common3 images and Brodatz texture images4 , and then, classified into textured or untextured patches. The value of ω comp = 10 has been set following previous evaluation of SLIC [START_REF] Achanta | SLIC superpixels compared to state-of-the-art superpixel methods[END_REF]. The parameter ω min is the only one which must be set by the user. In all of our tests we use a value of 0.00015 × N , with N the number of pixels in the image. The value of ω reg = 4 is related to an assumption about region growing: in an ideal case, at each step, 4 regions will be merged, to maintain a grid structure. The value of parameter ω sim = 0.05 has been learned on Berkeley dataset, and chosen to allow a satisfactory compromise between conciseness and boundary adherence properties. Experimental results of Sect. 3 show that these parameters allow ASARI to achieve competitive results and that they do not require to be re-learned anymore when dealing with other datasets.

Experimental Results

We evaluated ASARI using both Stutz experimental design [START_REF] Stutz | Superpixel segmentation: an evaluation[END_REF] and a new benchmark, Heterogeneous Size Image Dataset (HSID) that we proposed recently 5 . Contrary to Stutz datasets, i.e. the 100 images of the Berkeley Segmentation Dataset6 (BSD) [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF] and the 400 images of the New York University7 (NYU) [START_REF] Silberman | Indoor segmentation and support inference from RGBD images[END_REF] which only contains small images of thousand pixels, HSID is made up of 100 Wikimedia Common photographs, with a majority having several millions of pixels. In addition, variations of image size are significantly more important in HSID than in BSD or NYU.

In Stutz review [START_REF] Stutz | Superpixel segmentation: an evaluation[END_REF], boundary adherence of evaluated methods is analyzed using two measures: the Undersegmentation Error (UE) and the Boundary Recall (BR). Let G be a ground truth segmentation for an image I, S be an oversegmentation of I, B G be the set of boundary pixels in G, B S be the set of boundary pixels in S and N be the number of pixels. The undersegmentation error gets for each object G i in G the set of superpixels required to cover it and counts the number of pixels leaking of G i . The boundary recall checks whether boundaries of superpixels contain boundaries in G:

U E(S, G) = 1 N G i ∈G S j ∩G i =∅ min(|S j ∩ G i |, |S j -G i |) and BR(S, G) = |B S ∩ B G | |B G | (7)
In fact, even for a human, it is sometimes difficult to know exactly whether a pixel belongs or not to a boundary, Stutz allows a distance of 0.0075 × diag (where diag is the image diagonal length) pixels between boundary points in G and in S.

Unfortunately these two measures are not suitable to evaluate boundary adherence on HSID. To put it in a nutshell, the average score of U E is not significant due to the important variations in foreground areas in HSID images and the Stutz threshold is not suitable for big images. So, we suggest a modification of BR using fuzzy set theory. From B G we define the fuzzy set

B * G∩S with membership function f G∩S (p i ) = exp(- d(p i -p ′ i ) 2 2σ 2
) where d(p ip j ) is the distance between p i and p j locations, and p ′ i = arg min p j ∈B S (d(p ip j )). The function f G∩S returns a value in the range [0, 1], a value of 1 meaning a perfect coincidence between an element in B G and an element in B S . Finally, we propose the fuzzy boundary recall measure

F BR(S, G) = 1 |B G | p∈B G f G∩S (p).
Comparison to the state-of-the-art methods -By design, ASARI satisfy validity property, the only requirement is that vertices in G 0 are connected components. Then, because only adjacent regions are merged, the resulting superpixels are always a partition of I into connected components. The average number of neighbors by superpixel equals to 6 on BSD, NYU and HSID dataset, that is similar to all state-of-the-art oversegmentation methods.

Table 1 compares the results of ASARI to those achieved by the methods QS [START_REF] Vedaldi | Quick shift and kernel methods for mode seeking[END_REF], FZ [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF], SLIC [START_REF] Achanta | SLIC superpixels compared to state-of-the-art superpixel methods[END_REF], ERS [START_REF] Liu | Entropy rate superpixel segmentation[END_REF] and CRS [START_REF] Conrad | Contour-relaxed superpixels[END_REF], in Stutz review [START_REF] Stutz | Superpixel segmentation: an evaluation[END_REF]. On BSD, U E and BR scores of ASARI are similar to those of the state-of-art methods, Table 1. Comparison between ASARI and the state-of-the-art oversegmentations methods reviewed by Stutz [START_REF] Stutz | Superpixel segmentation: an evaluation[END_REF]. K is the average number of superpixels and T the execution time in seconds. [START_REF] Stutz | Superpixel segmentation: an evaluation[END_REF] 0.60 1500 36 SLIC parameters of [START_REF] Achanta | SLIC superpixels compared to state-of-the-art superpixel methods[END_REF] 0.58 1648 3 FZ parameters of [START_REF] Mathieu | Segmentation interactive pour l'annotation de photographies de paysages[END_REF] 0.59 1596 10 QS parameters of [START_REF] Stutz | Superpixel segmentation: an evaluation[END_REF] 0.53 1676 97 (c) Scores achieve on HSID. with a lower average number of superpixels (about 100 superpixels below). The adaptive nature of ASARI allows it to increase the conciseness of the produced oversegmentation, with some images partitioned into about 500 superpixels. An example is given in Fig. 1a. On NYU, U E of ASARI slightly less good but BR is similar. The average number of superpixels is more important (about 300 superpixels above). Figure 1b shows that, despite these difficulties, ASARI keeps its ability to adapt. Table 1c shows that ASARI is the method providing the best compromise between boundary adherence and compactness properties on the HSID dataset. The gap is significant with WP (+10% on FBR, for a similar number of superpixels), CRS (+17% with 100 superpixels fewer), SLIC (+2% with 100 superpixels fewer) and QS(+10% with 200 superpixels fewer). The differences with FZ (+2% with a similar number of superpixels) and ERS (+1% with a similar number of superpixels) are less important, but execution times of ASARI are better (near to 2 times faster than FZ and more than 6 times faster than ERS). Figure 1c andd show some examples of ASARI results. In Fig. 1d, the use of texture information allows a clear separation between the foreground and the background, which have similar colors.

Practical application -Interactive segmentation is a semi-automatic segmentation process. The user chooses some pixels (named seeds) and indicates for each of them the element to which it belongs. Features of desired regions are deduced by analyzing these seeds. Usually, adding or removing some seeds can improve the produced result, allowing the user to get any desired segmentation results. Suggested in 2016, Superpixel Classification-based Interactive Segmentation (SCIS) [START_REF] Mathieu | Segmentation interactive pour l'annotation de photographies de paysages[END_REF] creates a segmentation of the image by learning features of superpixels labeled by the user and classifying the remaining superpixels. The image is first oversegmented using FZ, then the average color and the center of mass location of each superpixel are computed. The learning and classification steps are made using a Support Vector Machine (SVM). Currently, despite its promising result, SCIS is not suitable to segment a dataset like HSID. The oversegmentation step using FZ produces a lot of small superpixels, often misclassified by the SVM. The resulting segmentation is noisy and correcting these errors by adding seeds is tedious. An example of this problem is shown in Fig. 2. As shown in this figure, ASARI, by producing more larger superpixels, considerably reduces this noise. In addition, ASARI is faster than FZ.

Conclusion

The main contribution of this paper is the description and the evaluation of a new oversegmentation algorithm, ASARI, which is suitable for datasets with important variations on image sizes and image complexities. The adaptive nature of ASARI and the fact that ASARI creates color and texture homogeneous superpixels while keeping reasonable execution times, allow it to outperform the state-of-the-art methods in such dataset. On other dataset, ASARI obtains results greater or equal to the state-of-the-art methods. The trade-off between boundary adherence, conciseness and efficiency achieved by ASARI offers interesting perspectives. We show a example of ASARI application as a preprocessing step of SCIS method. An implementation of ASARI is available online8 .

Fig. 1 .

 1 Fig. 1. Results achieved by ASARI on BSD, NYU and HSID.

Fig. 2 .

 2 Fig. 2. SCIS with FZ and ASARI: a comparison.

The decision to merge or not v i and its most similar neighbor is related to the merging criterion.

Our experiments show that this number of iterations is sufficient to provide good results.

https://commons.wikimedia.org/wiki/Main Page.

http://www.ux.uis.no/ ∼ tranden/.

http://image.ensfea.fr/hsid/.

https://www2.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/.

http://cs.nyu.edu.

http://image.ensfea.fr/asari/.

The work of Bérengère Mathieu was partially supported by ANR-11-LABX-0040-CIMI within the program ANR-11-IDEX-0002-02.


Sami Mnasri
email: sami.mnasri@irit.fr

Nejah Nasri
email: nejah.nasri@isecs.rnu.tn

Adrien Van Den Bossche

Thierry Val
email: val@irit.fr

A Hybrid Ant-Genetic Algorithm to Solve a Real Deployment Problem: A Case Study with Experimental Validation

Keywords: 3D indoor redeployment, DL-IoT, Prototyping, Testbed, ACO, NSGA-III

In this paper, we investigate the problem of deploying 3D nodes in a wireless sensor network. The aim is to choose the ideal 3D locations to add new nodes to an initial configuration of nodes, while optimizing a set of objectives. In this regard, our study proposes a new hybrid algorithm which stems from the ant foraging behavior and the genetics. It is based on a recent variant of the genetic algorithms (NSGA-III) and the Ant Colony Optimization algorithm. The obtained numerical results and the simulations compared with experiments prove the effectiveness of the proposed approach.

localization is the most relevant factor in connection with the coverage. Localization is relevant if there is uncertainty about the nodes exact location. Indeed, in WSN, the information about location is crucial especially when there is an unusual event. In this case, the sensor node that detects this event needs to locate it and then reports the location of that event to the sink node.

Another concept is closely related to our problem, it is the IoT (Internet of Things). The IoT is a scenario in which entities (devices, people or robots) are connected and have a unique identifier for each. They are able to transfer data over the network without human or automatic intervention. These objects communicate using protocols such as the Bluetooth or the 802. [START_REF] Shen | A study of welding robot path planning application based on Genetic Ant Colony Hybrid Algorithm[END_REF].4 as it is the case in our experiments. WSN is the bridge which links the real world to the digital one. It is responsible for the hardware communication to convey the real world values detected by the wireless connected things (sensor nodes) to the Internet. While the IoT is responsible for data processing, manipulation and decision making. In our study we are interested in the DL-IoT (DeviceLayer-IoT) [START_REF] Van Den Bossche | OpenWiNo: an open hardware and software framework for fast-prototyping in the IoT[END_REF] which is a network of collection used to collect data from the sensors nodes disseminated in the network environment. Thus, our approach are valid for both WSN and IoT contexts.

For most deployment modellings, the problem of optimal placement of sensor nodes is proved to be NP-hard [START_REF] Cheng | Relay sensor placement in wireless sensor networks[END_REF]. Therefore, this problem cannot be solved by deterministic methods, even for little number of nodes. Thus, we propose a new hybrid algorithm based on NSGA-III [START_REF] Deb | An evolutionary many-objective optimization algorithm using referencepoint-based nondominated sorting approach, part I: solving problems with box constraints[END_REF] and ACO (Ant Colony Optimization) algorithm [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents[END_REF] to solve it.

Related Works, Main Motivations and Contributions

In [START_REF] Aval | A review on the implementation of multiobjective algorithms in wireless sensor network[END_REF][START_REF] Mnasri | An overview of the deployment paradigms in the wireless sensor networks[END_REF], the authors propose a state-of-the-art on multi-objective approaches resolving the 3D deployment problem. Various methodologies are proposed, among others, genetic algorithms (GAs) and particle swarms (PSO). Nevertheless, no comparison using simulations or experiments between these approaches is provided in these works. In [START_REF] Qu | Wireless sensor network deployment[END_REF], Qu et al. suggest a redeployment approach based on GA and PSO. The objective is to maximize the range of detection, and to minimize the number of mobile nodes and energy consumption. However, no mathematical modeling is given for the problem. Besides, no modifications are proposed for the tested algorithms. Also, only the 2D case is considered (not the 3D one). In [START_REF] Matsuo | BalloonNet: a deploying method for a three-dimensional wireless network surrounding a building[END_REF], Matsuo et al. propose a 3D deployment with a radio propagation model in disaster areas using on a hybrid algorithm based on genetic algorithm and local search. However, the behavior of the tested algorithms is not evaluated with known evaluation metrics such as Inverted Generational Distance (IGD) and Hypervolume (HV). In order to minimize the number of thermal sensors, the authors in [9] solve the problem of placing thermal sensors in the smart grid using a gappy proper orthogonal decomposition (GPOD-GA) algorithm. Nevertheless, the proposed approach allows only the optimization of a single objective and its evaluation is not based on metrics such as IGD and HV. In [START_REF] Sweidan | Coverage optimization in a terrain-aware wireless sensor network[END_REF], the authors propose three strategies to resolve the deployment in terrain-aware by maximizing the coverage and minimizing the mobility cost. These strategies are based on a normalized genetic algorithm (NGA), and artificial immune system (AIS) algorithm and a particle swarm optimization (PSO) algorithm.

On the other hand, their approaches suffer from a disadvantage that concerns the high execution time of AIS and NGA.

These approaches suffer from several shortcomings. Among others, the inadequacy and inefficiency in the case of many-objective problems and real-world ones, both known for their complexity. In this work, the suggested contributions mainly concern:

-The proposition of a new algorithm with a justified hybridization which benefits from the advantages of the two algorithms ACO and NSGA-III. -The performance of the proposed algorithm is compared with those of the ACO and NSGA-III algorithms using the HV metric, followed by a comparison between the simulation results and the real prototyping experiments. The interpretation of the obtained results is also provided. -The use of the empirical context and the real measurements constitute a validation of the findings of the authors of the original algorithms (ACO and NSGA-III) which are validated only by tests on theoretical problems (DTLZ and ZDT).

The rest of the paper is organized as follows: in Sect. 2, the related works and the main contributions are presented. In Sect. 3, the new hybridization scheme is detailed. In Sect. 4, the performance of the AcNSGAIII is evaluated using numerical results. In Sect. 5, the simulation tests are compared to the experiments. Finally, in Sect. 6, a conclusion and different perspectives are listed.

3 Adapting the ACO and GAs for the 3D Indoor Deployment Problem

NSGA-III Algorithm

NSGA-III [START_REF] Deb | An evolutionary many-objective optimization algorithm using referencepoint-based nondominated sorting approach, part I: solving problems with box constraints[END_REF] is a recent algorithm, proposed as an extension of NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF]. It uses a reference point based approach to solve many objective problems (MaOPs). NSGA-III use the same concept of weight vector generation in MOEA/D [START_REF] Zhang | MOEA/D: a multiobjective evolutionary algorithm based on decomposition[END_REF] to determine a set of reference points scattered over the objective space. At every generation of each solution, the values of the objective function are normalized to [0, 1]. Then, a reference point is associated with each solution based on its perpendicular distance to the reference line. Assigning a reference point to each solution ensures the uniform repartition of the reference points across the normalized hyper-plane. The generated offspring is combined with the parent to create a hybrid population. Afterwards, the hybrid population is divided into a set of non-domination levels according to a non-dominated sorting procedure. The next parents as composed of the solutions in the first level so on and so forth. A niche-preservation operator is used to select solutions in the last acceptable level where the solutions associated with a less crowded reference line are more likely to be to be selected. For the majority of test problems, NSGAIII which is proposed especially for many-objective optimization shows a superior performance compared to other methods such as MOEA/D and NSGA-II. Algorithm 1 illustrates the NSGA-III algorithm.

Ant Colony Optimization Algorithm

The ACO algorithm was introduced by [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents[END_REF] in order to resolve the problems of hard CO (combinatorial optimization). It is a bio-inspired approximate algorithm which aim to obtain good solutions with reasonable computational cost (time) when resolving CO problems. Moreover, it is a meta-heuristic which is considered as probabilistic and population-based. The ACO stems from the foraging behavior of the real ants. Indeed, the ants aim at finding the shortest path between its nest and the source of food. Instead of using visual information's, ants use a chemical substance named 'pheromone' which is left behind their trails. So, in the ACO, the artificial ants (called agents) imitate their natural counterparts in order to resolve the problems by finding the optimal solutions. The ACO algorithm is illustrated in Algorithm 2. Indeed, firstly, when the collection begins, the shortest route leading to food is not known. Thus, each ant pursues randomly a route and place pheromone. As the collection progress, ants continue putting the pheromone. As a consequence, all traveled routes contain this substance. Then, because the pheromone evaporates overtime, if an ant wants to travel, it chooses the route with the highest rate of pheromone, which corresponds to the shortest among all routes. Therefore, overtime, only one route will remain (the shortest one).

The Proposed AcNSGA-III: A Hybrid Framework for NSGA-III and Ant System

Despite its efficiency, the NSGA-III has some difficulties when solving mono-objective and two-objective optimization problems. These difficulties concern the low selection pressure that NSGA-III introduce to non-dominated solutions of a population when resolving two-objective problems. Moreover, they concern the small population size and the random selection process when resolving mono-objective problems [START_REF] Ibrahim | EliteNSGA-III: an improved evolutionary many-objective optimization algorithm[END_REF]. Also, the ACO algorithm has a main drawback which concerns the convergence into the local optima [START_REF] Sim | Ant colony optimization for routing and load-balancing: survey and new directions[END_REF]. Therefore, the idea is to propose a well-justified hybridization scheme using the two algorithms to take advantage of their strengths and to remedy their drawbacks. When hybridizing these two algorithms, most of the studies [START_REF] Shen | A study of welding robot path planning application based on Genetic Ant Colony Hybrid Algorithm[END_REF][START_REF] Huang | Improved CCN routing based on the combination of genetic algorithm and ant colony optimization[END_REF] use the standard and basic version of the genetic algorithm. Besides, most of these studies sequentially execute the two algorithms (the standard GA then the ACO or the opposite). Thus, the final solution of one of the two algorithms is the initial solution of the other. Although this basic scheme of integration enhances the ACO convergence rate, this latter remains converging excessively which makes the problem of local optimum unsolvable. In our study, we propose a platform where the two algorithms (NSGA-III and ACO) run at the same time and interact with the same population. Thus, the ant algorithm steps are injected into the implementation of the original NSGA-III with incorporation of several modifications of the original NSGA-III. Among these modifications, the initial population of the NSGAIII which becomes the population built by the ants in the initial phase of the ACO. It should be mentioned that this is first time NSGA-III and ACO are integrated into a hybrid platform. Moreover, this is the first platform using a hybrid genetic algorithm and ACO to resolve the problem of 3D indoor deployment of nodes. The proposed algorithm, called AcNSGA-III is illustrated in Algorithm 3. It is a hybrid ant-Genetic algorithm which performs an ACO optimal selection of nodes, a dynamic pheromone updating and a mutation strategy. It accelerates the global convergence in order to speed up the local search which allows finding faster the suitable solutions of the 3D deployment problem. The global search ability and the randomness of the genetic operators are guaranteed which ensure conducting the operation of the genetic operator into generating routes by the ants if the ACO converges quickly. This allows to the latter finding the closing conditions and exits. Finally, since there is a low probability that ants and the NSGAIII process produce the same individual in the same iteration: the individual is added to the population unless it does not exist into it.

The procedure Each_ant_builds_a_solution() allows to construct the candidate solutions using a model of pheromone which is a tunable probability of distribution over the space the solution. In our case a solution is a feasible repartition of nodes in the 3D space. The procedure Update_pheromone() allows the use of the candidate solutions to update the values of the pheromone in order to ensure moving towards future better solutions. As an optimization, the operation of these two procedures can be summarized and replaced by the algorithmic sequence illustrated in Algorithm 4.

this section, we present the parameters setting the algorithms and the using performance indicators. Different metrics can be used. In our case, although the Hypervolume (HV) [START_REF] While | A faster algorithm for calculating hypervolume[END_REF] is a metric with an expensive computational cost, it is recommended because it is useful when assessing real world problems without the need of a prior knowledge of the true Pareto-front. Furthermore, when resolving a particular problem, the parameters setting has a major influence on the algorithm behavior. The used parametres are as follows:

-The size of the population (NS): 300 (Thus, Npop = 150).

-The operators of reproduction: It would be best to perform a recombination operation using near parent solutions in the case of MaOPs. Therefore, a large distribution index SBX operator (simulated binary crossover) is used. The recombination probability is PrOx = 0.8 using a distribution index τ r = 45. The mutation probability using the bit-flip operator, is PrMt = 2 * 10 -3 using a distribution index τ m = 25. -The number of runs: in order to guarantee statistical confident results, each algorithm is executed 25 runs using a different initial population in each execution. -The constraints number: 5.

-The number of ants (NbA): 350 -The pheromone minimum threshold (MaxTP): 1 -The pheromone maximum threshold (MinTP): 15 -The pheromone exponent (ExP): 0.4 -The pheromone evaporation coefficient (EvP): 0.25 -The number of objectives and the termination condition (the maximum number of generations) are as shown in Table 1. For each instance, the best performance is demonstrated using shaded background.

The AcNGSA-III outperforms the ACO and the NGSA-III in the most of the instances which proves its efficiency. Another constatation is that the ACO is better than the NSGA-III for three objectives, while the latter one is better when the number of objectives is higher than three. This is is congruent with the observation of its authors [START_REF] Deb | An evolutionary many-objective optimization algorithm using referencepoint-based nondominated sorting approach, part I: solving problems with box constraints[END_REF] which asserts that the NSGAIII is dedicated to resolve many-objectives problems. Also, due to the increasing complexity of the problem when the number of objectives increases, for all algorithms, better HV values are obtained with smaller number of objectives.

Comparing Simulations and Experimentations

This section aims to provide a comparison between the simulation and the experimental tests of the 3D deployment scheme in indoor WSN while satisfying different objectives. We are interesting in testing the behavior the tested evolutionary optimization algorithms (ACO, NSGA-III) and the new suggested one (AcNSGA-III).

Simulation/Experiments Parameters and Working Environment

The algorithms are tested on an Intel core Intel Core i5-6600 K 3.5 GHz computer. Our model is based on the implementation of a 433 MHz physical layer, a non-coordinated CSMA/CA access method of the IEEE 802.15.4 protocol, and a routing layer based on the reactive AODV (Ad-hoc Distance Vector) protocol. The following parameters are considered in our simulations/experiments:

The following tools are used:

-OMNeT++ 4.6 [START_REF]The OMNeT platform[END_REF] a free C++ platform to simulate and develop network protocols.

-JMetal 4.5.2 [START_REF]The jMetal platform[END_REF] a java platform, which aims to develop and test different metaheuristics solving problems of multi-objective optimization. -OpenWiNo [START_REF] Van Den Bossche | OpenWiNo: an open hardware and software framework for fast-prototyping in the IoT[END_REF] an open tool for emulating IoT and WSN protocols. It is used for prototyping protocols (in different layers) and evaluating their performances. -Arduino 1.6.1 [START_REF]The Arduino platform[END_REF] an open software/hardware platform for modules prototyping, the WiNo nodes use it in transferring programs via serial links. -Teensyduino 1.2.1 an Arduino add-on to run sketches.

Experimental Validations

The same architecture (number and type of nodes) of the 3D deployment is used both for simulations and experiments. A constant number [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] of fixed nodes with known positions is used. Also, the number of nomad nodes to be added is fixed to three. Their positions are determined with the tested algorithms. Similarly for mobile nodes, only one node is used as a trigger for the first message. In simulations, the positions of the initially deployed fixed nodes are chosen according to the distribution law used by OMNet++ which tries to uniformly distribute nodes starting from the center of the region of interest. In experiments, these positions are chosen according to the applicative objectives of the users in the building. This may lead to the non-coverage of certain zones especially at the borders if the number of fixed nodes is too small. The execution scenario is as following: In simulations, an initial message is sent from the mobile node to a random destination d; once d is found by the routing protocol, d becomes the source and a new destination is selected… etc. This cycle is repeated until a stop condition is satisfied. Among others, a maximal time for simulations. In experiments, the mobile node moves in the building and sends messages to its neighbors (nodes). Concerning the connectivity of nodes, a connectivity matrix between nodes is established. This matrix is deducted from empirical results derived from our experiments. As a consequence, the same initial connectivity links of the experiments are used. Subsequently, in order to model the dynamism of the network in simulations, these connectivity links are set to perturbations which allows modifying the initial connectivity links. Theses perturbations concern the calculation of the RSSI rates between the nodes. Indeed, a matrix of RSSI rates extracted from experiments is used initially. Then, this matrix is set to a perturbation (±30 for each value) in order to have new connectivity relations between nodes each time. Figure 2 represents the distribution of the nodes according to the OMNet++ interface in the simulations. Nodes named initial-i represents the fixed nodes and nodes named nomad-i represents the nomad nodes. Since comparing two algorithms is only possible through the use of a statistical test and due to the stochastic nature of the tested evolutionary algorithms, it is necessary to perform any test over many executions to obtain a well based judgment concerning their performance. Thus, all average values in this section, are computed based on 25 executions of the algorithms. Figure 3 shows the 3D deployment scheme of the experiments. Red nodes are the fixed nodes. Blue ones are the added nomad nodes. Comparing the RSSI rates. In order to measure the localization, the RSSI metric is used since the used localization model is based on hybridization between the RSSI and the DVHop (Distance-VectorHop) localization protocol. Thus, the higher the RSSI, the better the localization is. A neighbor can be added to the neighborhood table of a node only if the RSSI value of the detected node is greater than a predefined threshold. The theoretical value of this threshold is set to 90. Initially, RSSI levels are based on our empirical experiments. Then, as mentioned before, in order to guarantee dynamism within the network, disruption of the value of RSSI is introduced via a random function. Figure 4 shows, for different number of objectives considered by the tested algorithms, the average of the RSSI rates measured for all the nodes in connection with (detected by/detecting) the mobile node. Comparing the FER rates. To measure coverage, we use the FER as a metric to assess the quality of links between nodes. Thus, the lower the FER, the better the coverage is.

Although the FER values are less variable than those of the RSSI, for each node's pair {node C, node i}, an average value extracted from four values is taken with an interval of 10 s between the four values. Initially, FER rates are based on our empirical experiments. Afterwards, to guarantee dynamism within the network, disruption of the FER values is introduced via a random function (±0.04 to ±0.2). Figure 5 shows the average FER rates measured for all nodes in connection with (detected by /detecting) the mobile node. Comparing the number of neighbors. In order to assess the network connectivity, the number of neighbors of the target (the mobile node) is measured. Figure 6 shows the average of the number of neighbors of the mobile node per objective. Comparing the energy consumption and the network lifetime. Figure 7 shows the variation of the energy level of the network according to the time. Indeed, for the different tested algorithms, according to the number of the fixed nodes, an average of the energy indicator of all nodes of the network is measured after adding nomad nodes.

Discussion and Interpretations

After comparing the simulations and the experiments, different interpretations can be considered:

-The obtained results (Figs. 4, 5, 6, 7 and 8) show conformity with the results of experimentation, notably with regard to the coverage and localization rates. This proves the accuracy of the models of simulation and the effectiveness of the proposed approach in different contexts. Indeed, our work represents a proof by experimentation and simulations of the observations which has been proved by the authors of the tested algorithms (NSGAIII for example) only by tests on instances of theoretical test problems. -In several cases, lower RSSI averages are recorded after adding the nomad nodes.

Despite this decrease indicating that the RSSI rates of the added nodes are lower than the RSSI values of the fixed nodes, the localization rate, the coverage rate and the number of neighbors are improved. Given the objectives set by our approach, this decrease in RSSI averages is understandable, since adding a node in a location ×1 so that it will be close to several nodes with a lower RSSI value will be better than adding it in a location ×2 with a higher RSSI value but smaller number of neighbors. -The error rates (FER) are more important in experiments then in simulations. This is due to the influence of the activities of persons in the building during experiments (for example opening and closing doors) which generates the perturbation of the signal. -By comparing the efficiency of the tested algorithms, as proved by numerical results (Sect. 4), the simulation/experimental results show that this efficiency is relative to the number of objectives to be optimized. Table 1 shows that for less than three objectives, the ACO is more efficient than NSGAIII, while the latter is more effective than ACO if the number of objectives exceeds three. This is explained by the fact that the ACO is dedicated for multi-objective problems, while the authors of NSGAIII propose this latter as an adaptation of the NSGAII for many-objective problems having more than three objectives. However, the AcNSGA-III has an almost stable behavior and is not influenced by the variation of the number of objectives.

Conclusion and Perspectives

In this paper, we proposed a hybrid algorithm called AcNSGA-III based on NSGA-III and ACO to resolve the problem of 3D indoor deployment in WSN. In order to prove the efficiency of the new algorithm, the performance of the above mentioned algorithms is assessed using the Hypervolume metric, then by simulations and experimental tests while considering five objectives. The proposed algorithm outperforms the traditional NSGA-III and ACO. Different improvements may be incorporated to our approach: We can further include the dynamic redeployment of nodes and the existence of obstacles in the 3D space while considering different other objectives, such as the network connectivity. Moreover, as a perspective, we seek to intensify the real deployed network by adding new nodes in order to investigate the influence of the network density on results. Also, the implementation of a more realistic energy model based on the management of the BO and SO values [START_REF] Farhad | A delay mitigation dynamic scheduling algorithm for the IEEE 802.15.4 based WPANs[END_REF] of the 802.15.4 CSMA/CA protocol.

Figure 1

 1 Figure 1 demonstrates the Teensy WiNo deployed nodes.

Fig. 1 .

 1 Fig. 1. The Teensy WiNo deployed nodes

Fig. 2 .Fig. 3 .

 23 Fig. 2. The simulation scenario

Fig. 4 .

 4 Fig. 4. Comparing the average RSSI rates

Fig. 5 .

 5 Fig. 5. Comparing the average FER rates

Fig. 6 .

 6 Fig. 6. Comparing the average number of neighbors

Fig. 7 .

 7 Fig. 7. Comparing the average energy consumption levels

Fig. 8 .

 8 Fig. 8. Comparing the lifetime

Table 1 .

 1 HV (Best, average and worst values)

	Obj Nbr Max nbr of generations ACO	NSGAIII AcNGSA-III
	3	1300	0.984682 0.902458 0.903168
			0.983561 0.901896 0.902375
			0.982327 0.898023 0.987653
	4	1800	0.885236 0.974685 0.976687
			0.884381 0.974233 0.975986
			0.884003 0.973612 0.975124
	5	2600	0.878847 0.972892 0.973382
			0.872324 0.972716 0.972899
			0.871456 0.972684 0.972633

The Problem of 3D Indoor Deployment of Nodes (in WSN)/Things (in IoT)The effectiveness of WSN (wireless sensor networks) is strongly influenced by the deployment process and the positioning of sensor nodes. In a WSN, deploying nodes is a strategy that aims to define the number of nodes, their positions and the network topology. A WSN is said to be three-dimensional if the variation in the height of the deployed sensors is not negligible with respect to the length and the width of the deployment zone. Indeed,

the 2D model loses its relevance for terrestrial networks, as for marine or airborne deployments, where the 2D model does not reflect the real topography of the zone. Many research challenges in three-dimensional spaces have not been explored yet as much as for two-dimensional networks. In this paper, we are interested in improving the initial deployment by adding a set of nodes in a deterministic way. Coverage is the most important objective to be met when deploying a WSN. It is an essential subject in the design of a WSN. Coverage is generally interpreted as how a network of sensors will supervise the area of interest. The increase of the number of nodes cannot always provide a total degree of coverage, and it is also costly to maintain high-density_networks. As a result, other methods need to be applied to avoid these problems and to improve coverage after the initial random deployment. The sensor DOI: 10.1007/978-3-319-67910-5_30


Kamel Haddadi
email: kamel.haddadi@univ-lille1.fr

Petr Polovodov

Didier Théron

Gilles Dambrine

Quantitative Error Analysis in Near-Field Scanning Microwave Microscopy

Keywords: near-field scanning microwave microscopy (NSMM), vector network analyzer (VNA), metal oxide semiconductor (MOS), vector calibration

Near-field scanning microwave microscopy (NSMM) has to face several issues for the establishment of traceable and quantitative data. In particular, at the nanoscale, the wavelength of operation in the microwave regime appears disproportionate compared to the size of the nano-object under investigation. Incidentally, the microwave characterization results in poor electrical sensitivity as the volume of the wave/material interaction is limited to a fraction of the wavelength. In addition, the definition of nanoscale microwave impedance standards requires accurate knowledge of the material and dimensional properties at such scale. In this effort, a quantitative error analysis performed on micrometric metal oxide semiconductor (MOS) structures is proposed. In particular, atomic force microscopy (AFM) image together with the magnitude and phase-shift images of the complex microwave reflection coefficient using a Keysight TM 's LS5600 AFM interfaced directly with a vector network analyzer, without electrical matching strategy, are performed around 9.5GHz. From a detailed analysis of the raw data, completed with a FEMbased electromagnetic modeling, quantitative capacitances extraction and system limitations are exemplary shown.

I. INTRODUCTION

The introduction of scanning microwave microscopy (SMM) tools have pioneered many applications, notably including mapping and quantitative measurement of the electrical properties of materials and devices at micro and nano scale [START_REF] Anlage | Principles of nearfield microwave microscopy[END_REF]- [START_REF]Scanning Microwave Impedance Microscopy (sMIM)[END_REF]. Basically, the scanning microwave microscope (SMM) consists of an atomic or scanning tunneling microscope combined with a vector network analyzer (VNA) [START_REF] Imtiaz | Near-Field Scanning Microwave Microscopy: An Emerging Research Tool for Nanoscale Metrology[END_REF]- [START_REF] Haenssler | Manipulating and characterizing with nanorobotics: In-situ SEM technique for centimeter and millimeter waves[END_REF]. The tip scans across the sample, emitting a microwave signal scattered by the material, altering its amplitude or/and phase properties.

The main difficulty of NSMM methods lies in the measurement traceability. Indeed, as such nanoscale, several sources of errors affect the measurement accuracy rendering the data interpretation and incidentally the establishment of quantitative results difficult [START_REF] Zhang | Microwave atomic force microscopy imaging for nanometer-scale electrical property characterization[END_REF]- [START_REF] Happy | Measurement techniques for RF nanoelectronic devices : new equipment to overcome the problems of impedance and scale mismatch[END_REF]. First, there is a natural mismatch between the size of nanodevices and the wavelength of operation in the order of the cm in the microwave regime. Consequently, the electrical sensitivity of the microwave signal of interest, i.e. the reflected wave at the tip/sample interface, is limited by many factors such as parasitic capacitance of the body cantilever, non-systematic errors inherent to the VNA (source phase noise, IQ receiver noise, limitation of the analog-to-digital conversion), environment variations (temperature, hygrometry). In addition, the probe tip deteriorates during scanning operation leading to noncontrolled electrical imaging resolution.

The objective of this work is to provide a detailed analysis of the factors impacting the measurement quality. A verification kit developed by Keysight TM and MC2-Technologies TM that consists of MOS capacitors is used for the experiments. This latter has found wide acceptance by the NSMM community and it thus constitutes an excellent test vehicle for further inter-comparison campaigns. In Section II, a measurement set-up using a direct connection between the AFM and the vector network analyzer is proposed to yield the intrinsic electrical sensitivity/accuracy. In addition, the capacitances verification kit is presented with a tentative FEM-based electromagnetic modeling. AFM and SMM imaging is discussed in Section III. The microwave images of the magnitude and phase-shift of the reflection coefficient are analyzed. A calibration modeling is proposed for the determination of the capacitance values using a modified Short─Open─Load (SOL) calibration method.

II. MATERIALS AND METHODS

The set-up of the NSMM consists of a Keysight TM LS5600 AFM interfaced with a Keysight TM PNA series network analyzer E8362B [START_REF] Dargent | An interferometric scanning microwave microscope and calibration method for sub-fF microwave measurements[END_REF].

The verfication kit used here was developed by Keysight TM and MC2-Technologies TM . It consists of MOS capacitors the values of which range from 0.1 fF to 4 fF. The MOS capacitors are composed of circular gold electrodes evaporated on silicon dioxide deposited on a P-type silicon substrate of resistivity 1-3 Ωcm. The calibration kit is depicted in Fig. 1. In order to vary the capacitances values, the diameter of the upper gold pad varies from 1 to 4 μm and the SiO2 thickness ranges from 50 to 300 nm with about 80 nm steps. The capacitance Cox is calculated from the areas of the gold pads A and the SiO2 thicknesses dox.

C ox = A ε ε rSi0 2 ox (2)
The silicon dioxide is assumed to have a relative dielectric constant of ε rSi0 2 = 3.9. The thickness and areas of the capacitors were estimated from the AFM topography measurements [Fig. 2(b)] to take into account any deviations in geometry induced by the fabrication process of the calibration kit. The measured thicknesses dox of the SiO2 layers were 41 nm, 127 nm, 220 nm, and 301 nm. The measured areas A were 1.4 μm 2 , 4.7 μm 2 , 9.0 μm 2 , and 15.6 μm 2 . The charge stored on the capacitor is distributed across a certain depth that adds the depletion series capacitance Cdepl in series to Cox. The capacitance was estimated to be proportional to the area A of the metallic electrode and inversely proportional to the depleted zone depth ddepl according to

C depl = A ε 0 ε rSi d depl (3) with A r depl qN Ψ d ε ε = 0 2
and where = 12 is the relative permittivity of the silicon bulk substrate, Ψ represents the interface band bending at the Si/SiO2 interface and is set to 200 mV, q is the charge of the electron (1.6  10 -19 C), NA is the doping level of the silicon bulk around 810 15 /cm -3 . From relations (1) to (3), we derive in TABLE I the theoretical capacitances data for respectively the smallest area of the gold pad (1.4 µm 2 ) and the largest one (15.6 µm 2 ). In particular, Cox is also calculated by finite element modeling using COMSOL TM to take into account the deviation from ideal capacitance induced by the fringing fields.

III. MEASUREMENTS

The measurements were performed around 9.95 GHz using a 25PT300A AFM tip from Rocky Mountain Nanotechnology TM . The RF power source is set to 0 dBm and the intermediate frequency bandwidth (IFBW) of the VNA is 100 Hz. The images were scanned over a 5050 μm 2 with 256 pixels at a scan rate of 0.625 line/s. In addition to the topography image (Fig. 2), the NSMM provides both magnitude and phase images of the complex reflection coefficient Γ. After data leveling using Gwyddion TM software, tilt effects are corrected. Topography images for the smallest capacitors are given in Fig. 3. Although the capacitors are located on the upper and lower parts of the verification kit (Fig. 1), good agreement in the measured topography is noticed. Furthermore, the thicknesses of the SiO2 are identical at the different Y-locations. Fig. 3. 1D topography X-scans for the smallest capacitors.

The microwave image of the magnitude of the reflection is given in Fig. 4(a). The raw data shows a linear drift only for the Y-direction. This latter is mainly attributed to the VNA measurement configuration that is resynchronized with the topography image line by line. Consequently, a step line correction is applied to resynchronize the data [Fig. 4(b)]. Same findings are obtained for the phase-shift image, i.e. phase-jumps in synchronization can be corrected (Fig. 5).

Second step was to verify a possible correlation of the signals fluctuations between topography and microwave data. As illustrated in Fig. 6, the 1D scan regarding the capacitor indicated non-correlated fluctuations between topography and microwave signals. Therefore, fluctuations on the microwave signals are mainly attributed to the source and receiver noises of the VNA. No matching strategy is considered in this study, resulting in relatively poor measurement sensitivity. Indeed, fluctuations in the microwave signals become predominant for the smallest capacitors.

Third step was to apply a vector calibration technique based on a modified SOL technique [START_REF] Dargent | An interferometric scanning microwave microscope and calibration method for sub-fF microwave measurements[END_REF]. To that end, three theoretical capacitance values, obtained from FEM simulation, are considered as capacitances standards to derive the capacitance values at the tip apex of the probe. To lower the measurement uncertainty, the measured capacitance values for each case are obtained as the average capacitance calculated on the whole capacitor surface (see inset of Fig. 7). The calibrated capacitances are given in Fig. 7 as a function of their theoretical counterparts. From these data, we demonstrate that capacitance values down to 500aF can be measured accurately without matching network between the VNA and the probe. To lower the measurement uncertainty, the microwave path should be kept as low less as possible. IV. CONCLUSION Atomic force microscopy (AFM) image together with the magnitude and phase-shift images of the complex microwave reflection coefficient using a KeysightTM's LS5600 AFM interfaced directly with a vector network analyzer, without electrical matching strategy, are performed around 9.5GHz. From a detailed analysis of the raw data, quantitative capacitances extraction indicates a limitation around 500aF. Above 500 aF, noise effects are predominant and must be reduced. Strategies to enhance the measurement accuracy will be discussed in the final version of the paper.

Fig. 1 .

 1 (a) RMN® SMM probe. (b) Verification kit based on scaled MOS capacitances. The impedance of the MOS structures measured at the tip apex of the probe is modeled by a series model consisting of an oxide capacitance Cox and a depletion capacitance Cdepl. Both capacitances can be described by the parallel plate capacitor formalism. The resulting capacitance CTOT is given by TOT ox depl ox depl . ⁄ (1)

Fig. 2 .

 2 Fig. 2. NSMM topography image in (a) 2D view and (b) 3D view.

Fig. 4 .Fig. 5 .

 45 Fig. 4. 3D Image of the magnitude of the complex reflection coefficient Γ (a) before and (b) after step line correction -F = 9.95GHz.

Fig. 6 .

 6 Fig. 6. 1D scan of a 2µm-wide capacitor. (a) Topography. (b) Magnitude and (c) Phase of the reflection coefficient Γ -F = 9.95GHz.

Fig. 7 .

 7 Fig. 7. Microwave capacitance as a function of the theoretical values -F = 9.95GHz. Two set of capacitances standards are considered.

TABLE I THEORETICAL

 I REFERENCES CAPACITANCES OF THE MOS

		A = 1.4 µm 2
	41 127 220 301	1.18/1.28 ⎯ 0.47 0.38/0.48 ⎯ 0.47 0.22/0.32 ⎯ 0.47 0.16/0.26 ⎯ 0.47	0.34 0.24 0.19 0.17
		A = 15.6 µm 2
	41 127 220 301	13.14/13.48 ⎯ 5.19 4. 24/4.58 ⎯ 5.19 2.45/2.79 ⎯ 5.19 1.79/2.13 ⎯ 5.19	3.74 2.43 1.81 1.51

CALIBRATION SAMPLE. dox (nm) Capacitances Cox, eq. (2) / Cox,COMSOL ⎯ Cdepl [fF] CTOT [fF]

ACKNOWLEDGMENT

This work is performed under EMPIR Planarcal project (http://www.planarcal.ptb.de). This work used the facilities within the EQPX ExCELSiOR (www.excelsior-ncc.eu) funded by the National Research Agency (ANR).


Sami Mnasri

Adrien Van Den Bossche

Nejah Nasri
email: nejah.nasri@isecs.rnu.tn

Thierry Val
email: val@irit.fr

The 3D redeployment of nodes in Wireless Sensor Networks with real testbed prototyping

Keywords: Testbed, Prototyping, 3D indoor deployment, DL-IoT, NSGA-III, Preference, Many-objective optimization

In wireless sensor networks (WSNs), prototyping systems facilitate the realization of real node deployment, enabling to test new algorithms, protocols, and networking solutions. This paper investigates the 3D indoor redeployment problem in WSNs by finding the positions where nodes should be added in order to improve an initial deployment while optimizing different objectives. For this purpose, an approach based on a recent evolutionary optimization algorithm (NSGA-III) is used. The latter algorithm is hybridized with a strategy of incorporating of the user preferences (PI-EMO-VF). The major contributions of this work are as follows: testing the NSGA-III efficiency in the case of real world problems, comparing it with another recent manyobjective algorithm (MOEA/DD), and incorporating the concept of preferences of users into NSGA-III. The real experiments performed on our testbeds indicate that the results given by the proposed algorithm are better than those given by other recent optimization algorithms such as MOEA/DD.

The problem of 3D indoor redeployment in WSNs

The redeployment of nodes in WSNs consists in identifying the number and positions of the nodes to be added to an initial configuration of nodes. It is a process that greatly influences the performance of a network. In this paper, we study the problem of redeploying nodes in three-dimensional spaces which represent the real topology of the RoI (region of interest) better than two-dimensional spaces. The improvement of the initial 3D indoor deployment is achieved by the addition of a set of nodes in a deterministic way while optimizing different objectives, such as localization, coverage, link quality, connectivity, or the lifetime of the network.

In fact, the recourse to use real experiments rather than simulations is due to the increasing simplicity of prototyping of communication devices and access to hardware. The major contribution of using real experiments than simulations is the realism of the obtained results. In this regard, the deployment of nodes with real prototyping that incorporates human experience is a more interesting to researchers than approaches which are based on theoretical assumptions, simulations or formal calculations. Indeed, the objective of our work is to finely represent the real world using real physical nodes (36 TeensyWiNo nodes). These nodes are deployed using our rapid prototyping platform. Details of the implementation of this platform are presented in the experimental section.

In order to obtain the best distribution of the nodes in the RoI, while satisfying the mentioned objectives, we propose an approach which is based on an evolutionary genetic optimization algorithm, the NSGA-III [START_REF] Deb | An evolutionary many-objective optimization algorithm using referencepoint-based nondominated sorting approach, part I: Solving problems with box constraints[END_REF]. Indeed, genetic algorithms (AGs), of which NSGA-III is a recent variant, are based on a set of individuals constituting the population. Each individual in this population has a genotype that encodes a candidate solution for a particular problem. After the determination of the initial population, a set of mechanisms such as recombination, mutation, and selection ensure the convergence of the population towards a better solution.

The rest of the paper is composed of the following sections: The new NSGA-III hybrid algorithm is detailed in Section 2. Then, our experiments on real testbeds are presented in Section 3. Finally, a conclusion and different perspectives are identified in Section 4.

A many-objective hybrid algorithm (PI-NSGAIII-VF) for the 3D indoor redeployment problem 2.1 The NSGA-III algorithm

NSGA-III is a new many-objective evolutionary optimization algorithm (MaOA) which is designed to solve many-objective problems (MaOPs). Based on the concept of reference points, NSGA-III is introduced as an extension of the NSGA-II algorithm [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] to resolve to problem of bad performance of the latter when the number of objectives exceeds three. As in the case of the MOEA/D algorithm [3], the NSGA-III is based on the concept of generating weight vectors to identify the reference points which are disseminated in the objective space.

In this regard, Algorithm 1 shows one generation of the NSGA-III algorithm. Indeed, for each generation of a solution, the values of the objective function are normalized to a binary value. Thereafter, each solution is associated with a reference point according to the perpendicular distance of each reference point to the reference line. This ensures having a uniform distribution of the reference points in the normalized hyper-plane. Therefore, a hybrid population composed of the parent and an offspring is obtained. Subsequently, this population is divided into a set of non-domination levels using a non-dominated sorting procedure. The solutions constituting the first level serve as the next parents so on and so forth. Next, the solutions of the last acceptable level are selected using a niche preservation operator. Finally, a maximum number of iterations serves as the termination condition of the algorithm. In the case of manyobjectives problems, NSGA-III has been shown to perform better than MOEA/D and NSGA-II for several theoretical test problems [START_REF] Deb | An evolutionary many-objective optimization algorithm using referencepoint-based nondominated sorting approach, part I: Solving problems with box constraints[END_REF]. Remain the NSGA-III test on a real problem, compare it with other many-objective algorithms like MOEA/DD and incorporate it with a user preference procedure.

While |-$|≤ ! "# do -$=-$+,. .=.+1 End While If |-$| = ! "# do Pt+1=St Else $+1= 1 1 l U F j j - =
Normalize ! using min and intercept points of each objective Associate each member of ! to a reference point

Choose "#$%-|#!+1| members from &' by niche preserving operator End if != !+1; End While

Incorporation of preferences

When solving a many-objective problem, MaOAs often provide a set of nondominated solutions that are close as possible to the Pareto front (PF). In the case of real-world problems, which are known by a large number of objectives, the size of the population and the number of needed solutions exponentially depend on this number of objectives [START_REF] Ishibuchi | Adaptation of Scalarizing Functions in MOEA/D: An Adaptive Scalarizing Function-Based Multiobjective Evolutionary Algorithm[END_REF]. On the other hand, the user, often called the decision-maker (DM), usually only needs a very small number of non-dominated solutions. Thus, it is preferable concentrate the search on a set of specific regions guided by the preferences of the user. Based on the integration time of the preferences, we can classify the preference procedures into three main classes [5]: A priori, interactive and a posteriori ones. The most relevant class is the second one, because it allows the progressive engagement of the preferences of the DM and the readjustment of its decisions as the algorithm generations evolve. Nevertheless, few research papers propose solutions for the interactive integration of the DM preferences. Our paper proposes a new hybridization scheme that incorporates NSGA-III into an interactive preference algorithm called PI-EMO-VF [START_REF] Deb | An Interactive Evolutionary Multi-Objective Optimization Method Based on Progressively Approximated Value Functions[END_REF] where the DM is asked to interactively integrate its preferences in order to guide the searches towards a specific subset of the PF. Indeed, incorporated into any evolutionary multi-objective optimization (EMO) algorithm, PI-EMO-VF is a generic procedure that uses an approximate value function which is progressively generated. Indeed, after each small number of generations (iterations) of the EMO algorithm used (NSGA-III in our case), a set of non-dominated uniformly distributed solutions is determined, and the DM proposes its preferences (in general, an information about the relationship between the solutions). The DM can either classify all solutions from the best to the worst, or provide partial preference information. The given information helps to construct an increasing polynomial value function which determines the stop condition. More details on the PI-EMO-VF procedure are given in [6].

Experiments with real prototyping

A testbed can be any platform that allows to test and experiment new network protocols, models, or technologies in order to prove its effectiveness in real-world environments. Indeed, formal analyzes and simulations cannot exactly reproduce the technical and physical characteristics of the real environments. Also, the current tendency is to experiment protocols and algorithms with real environments [START_REF] Mnasri | An Overview of the deployment paradigms in the Wireless Sensor Networks[END_REF]. Therefore, the experiments carried out on our testbeds allow reducing the gap between the theory and the practice in the WSN deployment problems.

Parameters of experiments

The following parameters were used in our experiments:

-

Description of the prototyping platform

In our experiments, the deployed nodes are TeensyWiNo ones. They are based on the WiNoRF22 nodes, and equipped with several types of sensors (pressure, temperature, acceleration, brightness, etc.). These WiNo nodes have the advantage of allowing the developer to access to low layers. Indeed, this facilitates control of the average access time and the sleep one, the restricted memory and the CPU time. This control is necessary in order to ensure compliance with the real-time constraints and the management of drastic energy-saving policies. Moreover, these nodes with their effective material energy features (several months of operation using two AAA batteries), allow hosting protocols with high temporal constraints. Fig. 1 illustrates an example of the deployed WiNo nodes.

Fig. 1. The used Teensy WiNo nodes

The compatibility of these nodes with the Arduino environment enables researchers to easily integrate software bricks (processing algorithms, prototyping solutions, etc.) and hardware ones (sensors, actuators, interaction devices, etc.) which enables the feedback from users.

Results

Conduct of the experiments. 30 fixed nodes are initially deployed in known positions that are chosen according to the application needs of the users. Six added nodes, having positions that are identified by the tested optimization algorithms. The experimental scenario is as follows: Initially, all nodes are flashed. Afterwards, they are sent the initial configuration parameters (transmission power, etc.). Then a randomly selected node sends a message to the other nodes of the network and records the RSSI (received signal strength indicator) and FER (frame error rate) measurements detected by these nodes and the received measurements (RSSI and FER) of the nodes receiving the signal. After a predefined waiting time, the sender ends the process. Afterwards, the transmitter is changed in such a way that each time a receiver node becomes a transmitter. These steps are repeated until 36 experiments (one send and 35 receptions in each experiment) are performed. The obtained values representing the relations between all the nodes are collected and recorded in two connectivity matrices (an RSSI matrix and an FER one). These two matrices give also information about the neighbors of each node. Indeed, we consider a node i as a neighbor to another node j if the following two conditions are satisfied: (a) The average of the transmitted RSSI between the two nodes (from i to j and vice versa) is higher than a predefined threshold (set to 100 in our experiments); and (b): The average FER value is less than a predefined threshold (set to 1/10 in our experiments).

To assess the impact of the new chosen positions of the added nodes on the performance of the network, this process is repeated several times (20 times in our experiments, given the variation of RSSI and FER rates and the stochastic nature of the evolutionary algorithms). The performance of the proposed algorithm (PI-NSGAIII-VF) is compared to the MOEA/DD [8] which is another recent competitive MaOA.

Evaluation of the RSSI rates. The evaluation of a set of the considered objectives in our study (such as localization, link quality, and connectivity) is achieved using the RSSI rate measurement. Indeed, in our experiments, the localization is based on a protocol that combines the RSSI rates and the Distance-VectorHop protocol. Therefore, the localization is proportionally dependent on the RSSI rate. Fig. 2 illustrates the average RSSI rate between each node and the other ones. The RSSI is represented by a value between 0 and 256, which is convertible to a dBm measure.

Fig. 2. Average rates of RSSI between nodes

Evaluation of FER rates. Similarly, the measurement of the FER rate is used to assess the coverage and the quality of link between nodes. Indeed, the coverage is proportionally dependent on the FER rate. Fig. 3 illustrates the average rate of FER between each node and the other ones.

Algorithm 1 :

 1 One generation of the NSGA-III Input: 0(Initial Population), ! "# (size of population), $ (iteration) = 0, %$&'( (Max iteration). Output : $ While $<%$&'( do Create Offspring )$ Mutation and recombination on )$ Set *$= $+)$ Apply non-dominated sorting on *$ and find ,1, ,2, … -$={}, .=1;

Fig. 3 .

 3 Fig. 3. Average rates of FER between nodes