Section: New Results

Self-deployment, localization and area coverage

Participants : Milan Erdelj, Xu Li, Enrico Natalizio, Nathalie Mitton, Tahiry Razafindralambo, David Simplot-Ryl, Isabelle Simplot-Ryl.

Deployment

First steps in order to perform any task, a network needs to be deployed and nodes need to discover each others. To the best of our knowledge, very few scenarios when robots self-deploy to afterwards themselves constitute the network nodes or drop off sensor nodes have been investigated so far and none of them ensure the network connectivity at every step. In [15] , we consider the self-deployment of wireless sensor networks. We present a mechanism which allows to preserve network connectivity during the deployment of mobile wireless sensors. Our algorithm is localized and is based on a subset of neighbors for motion decision. Our algorithm maintains a connected topology regardless of the direction chosen by each sensor. To preserve connectivity, the distance covered by the mobile nodes is constrained by the connectivity of the node to its neighbors in a connected subgraph like the relative neighborhood graph. We show the connectivity preservation property of our algorithm through analysis and present some simulation results on different deployment schemes such as full coverage, point of interest coverage or barrier coverage.

Another approach is the one proposed in [34] in which node placement is performed off-line with objective to optimize a criterion. Based on the specific application, different objectives can be taken into account such as energy consumption, throughput, delay, coverage, etc. Also many schemes have been proposed in order to optimize a specific quality of service (QoS) parameter. Power consumption is an essential issue in wireless multimedia sensor networks (WMSNs) due to the elevated processing capabilities requested by the video acquisition hardware installed on the generic sensor node. Hence, node placement scheme in WMSNs greatly impacts the overall network lifetime. [34] first proposes a suitable hardware architecture to implement a feasible WMS node based on off-the-shelf technology, then it evaluates the energy consumption obtained throughout a wise "energy-spaced" placement of the wireless nodes without affecting the video quality of multimedia traffic. In [4] , we propose to use a neural network as a controller for nodes mobility and a genetic algorithm for the training of the neural network through reinforcement learning. This kind of scheme is extremely adaptive, since it can be easily modified in order to consider different objectives and QoS parameters. In fact, it is sufficient to consider a different kind of input for the neural network to aim for a different objective. All things considered, we propose a new method for programming a WSRN and we show practically how the technique works, when the coverage of the network is the QoS parameter to optimize. Simulation results show the flexibility and effectiveness of this approach even when the application scenario changes (e.g., by introducing physical obstacles).

Coverage

The coverage of Points of Interest (PoI) is a classical requirement in mobile wireless sensor applications. Optimizing the sensors self-deployment over a PoI while maintaining the connectivity between the sensors and the sink is thus a fundamental issue. [22] addresses the problem of autonomous deployment of mobile sensors that need to cover a predefined PoI with a connectivity constraints and provides the solution to it using Relative Neighborhood Graphs (RNG)  [52] . Our deployment scheme minimizes the number of sensors used for connectivity thus increasing the number of monitoring sensors. Analytical results, simulation results and real implementation are provided to show the efficiency of our algorithm. To the best of our knowledge, only [21] both preserves the network connectivity and validates its proposition through experimentations with real wireless robots. This work has been extended to discovery and coverage of multi-point of interested in [21] . Indeed, the problems of multiple PoI coverage, environment exploration and data report are still solved separately and there are no works that combine the aforementioned problems into a single deployment scheme. In [21] , we present a novel approach for mobile sensor deployment, where we combine multiple PoI coverage with network connectivity preservation and environment exploration in order to capture the dynamics of the monitored area. We examine the performance of our scheme through extensive simulation campaigns.

As sensors are energy constrained devices, one challenge in wireless sensor networks (WSNs) is to guarantee coverage and meanwhile maximize network lifetime. In [7] , we leverage prediction to solve this challenging problem, by exploiting temporal-spatial correlations among sensory data. The basic idea lies in that a sensor node can be turned off safely when its sensory information can be inferred through some prediction methods, like Bayesian inference. We adopt the concept of entropy in information theory to evaluate the information uncertainty about the region of interest (RoI). We formulate the problem as a minimum weight submodular set cover problem, which is known to be NP hard. To address this problem, an efficient centralized truncated greedy algorithm (TGA) is proposed. We prove the performance guarantee of TGA in terms of the ratio of aggregate weight obtained by TGA to that by the optimal algorithm. Considering the decentralization nature of WSNs, we further present a distributed version of TGA, denoted as DTGA, which can obtain the same solution as TGA. The implementation issues such as network connectivity and communication cost are extensively discussed. We perform real data experiments as well as simulations to demonstrate the advantage of DTGA over the only existing competing algorithm and the impacts of different parameters associated with data correlations on the network lifetime.

Localization

In mobile-beacon assisted sensor localization, beacon mobility scheduling aims to determine the best beacon trajectory so that each sensor receives sufficient beacon signals with minimum delay. We propose a novel DeteRministic bEAcon Mobility Scheduling (DREAMS) algorithm [32] , [10] , without requiring any prior knowledge of the sensory field. In this algorithm, beacon trajectory is defined as the track of depth-first traversal (DFT) of the network graph, thus deterministic. The mobile beacon performs DFT under the instruction of nearby sensors on the fly. It moves from sensor to sensor in an intelligent heuristic manner according to RSS (Received Signal Strength)-based distance measurements. We prove that DREAMS guarantees full localization (every sensor is localized) when the measurements are noise-free. Then we suggest to apply node elimination and topology control (Local Minimum Spanning Tree) to shorten beacon tour and reduce delay. Through simulation we show that DREAMS guarantees full localization even with noisy distance measurements. We evaluate its performance on localization delay and communication overhead in comparison with a previously proposed static path based scheduling method.