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

Enrico Natalizio
email: enrico.natalizio@hds.utc.fr

Michael Poss
email: michael.poss@hds.utc.fr

Giuseppe Ruggeri
email: giuseppe.ruggeri@unirc.it

Antonella Molinaro
email: antonella.molinaro@unirc.it

Healing wireless sensor networks from malicious epidemic diffusion

Keywords: Controlled mobility, Wireless Sensor Network, Malware Removal

Leveraging the concept of controlled node mobility in this paper we develop an algorithm for tracking and controlling proximity malware propagation in Wireless Sensor Networks (WSN). Our proposal aims at: (i) notifying the nodes of malware propagation, (ii) leading a flying robot along a path in the WSN that guarantees the minimum recovery time to (iii) heal the infected nodes. We formulate the targeted curing problem as a binary integer problem and determine the optimal solution by a central solver. We use the analytical result as a benchmark to evaluate the recovery time of the proposed solution. The achieved results show a satisfactory performance in terms of tracking the presence of an ongoing epidemic and healing the nodes.

I. INTRODUCTION

Proximity malware propagation consists in malicious code injection and diffusion in a wireless distributed network [START_REF] La Polla | A survey on security for mobile devices[END_REF], [START_REF] Wang | Modeling the propagation of worms in networks: A survey[END_REF]. This has recently become a serious security threat also in Wireless Sensor Networks (WSNs) [START_REF] Sun | Worm propagation dynamics in wireless sensor networks[END_REF]. Traditionally, sensor nodes were conceived as resource-constrained devices whose behaviour was essentially determined by hard-wired algorithms. This made them naturally immune to malwares. Today, instead, advanced sensing applications exploit more complex sensor devices, whose capabilities are very similar to those of smartphones and microcomputers [START_REF] Akyildiz | Wireless multimedia sensor networks: A survey[END_REF]. For example, a sensor network used for video-surveillance applications shares the typical constraints of a WSN (in terms of energy and deployment in inaccessible fields) but it also requires additional complexity to be capable to handle a video stream and transmit it to a remote destination. The additional complexity required from WSNs to satisfy new applications requirements translates in more complex operating systems and communication protocols, which, in turn, expose the network to security risks. In recent past, several proximity malwares have been detected that use Bluetooth (e.g., Cabir [START_REF]Symbos cabir[END_REF]) and WiFi (e.g., iKee [START_REF]Ios ikee[END_REF]) connections to spread among mobile devices. Furthermore, the feasibility of full-scale attacks on networks that rely on short range communications, like WSNs, has been demonstrated [START_REF] Shengjun | Modeling the spread of worm epidemics in wireless sensor networks[END_REF]. Several defense mechanisms have been proposed to face proximity malware in WSNs [START_REF] Wang | Reaction-diffusion modeling of malware propagation in mobile wireless sensor networks[END_REF], [START_REF] Sun | Self-propagating malpackets in wireless sensor networks: Dynamics and defense implications[END_REF]. However, so far, the proposed solutions for curing infected nodes have relied on the network infrastructure or a human intervention to deliver the patches and securing the remote access. Unfortunately, these features are not commonly available in the majority of WNS deployments [START_REF] Li | Cpmc: An efficient proximity malware coping scheme in smartphone-based mobile networks[END_REF]- [START_REF] Nadji | Automated remote repair for mobile malware[END_REF].

In this paper, our main contributions, listed below, aim at fulfilling this lack:

1) We propose to leverage a diffusion mechanism to inoculate a cure to infected nodes (i.e. provide a method to restore the nodes to an original healthy state). The diffusion of the cure is performed by a flying robot (which we will refer to as searcher in the following), which is capable of autonomously move within the network and deliver node maintenance. 2) We develop a counter-epidemic algorithm that (i) notifies the nodes of the malware spreading, (ii) drives the searcher through the network to prevent and hinder the diffusion of a malicious epidemic and (iii) heals the infected nodes.

3) We propose a mathematical model for the Targeted

Curing Problem (TCP) to determine the best trajectory for the searcher to cure infected nodes and contain the epidemic outbreak. Specifically, the model outputs the lowest delay needed to inoculate a cure by using a counter-epidemic diffusion scheme. We use the model to benchmark the behavior of our proposed approach.

For the purpose of our scenario in Section II we introduce the background research on the subject, followed by our set of working prerequisites in Section III. Our main contribution is presented in Section IV and V, where we first describe our scenario and main proposal, and after we propose a mathematical formulation of the same problem. In Section VI we present our simulative and numerical results while the Section VII concludes our proposal.

II. RELATED WORK

Our work is mainly related to three research topics: the epidemics diffusion and network immunization, the identification of outbreaks, and the path determination for the searcher's movement. In the following subsections, we will discuss the three topics separately.

A. Epidemics diffusion and network immunization

The research on networks epidemics and immunization, with reference to WSN, is recently becoming a popular topic among the networking research community [START_REF] Wang | Reaction-diffusion modeling of malware propagation in mobile wireless sensor networks[END_REF], [START_REF] Tang | A modified epidemic model for virus spread control in wireless sensor networks[END_REF]. The most common strategy to limit the effects of an epidemic is to render a part of population immune [START_REF] Sander | Percolation on heterogeneous networks as a model for epidemics[END_REF] by means of some vaccine. However, a highly viral computer epidemic needs almost 100% immunization to produce an appreciable effect, and a random immunization strategy could lead to intolerable delays [START_REF] Eguíluz | Epidemic Threshold in Structured Scale-Free Networks[END_REF]. In the case of a WSN, it is more effective to upload on the infected node a new non protected part of the operating system that would restore the node functionalities and cure the node [START_REF] Brown | Software updating in wireless sensor networks: A survey and lacunae[END_REF]. We will adopt this solution as part of our curing algorithm. Generally, the abovementioned strategies are tailored for epidemic prevention, whereas we aim at controlling epidemic diffusion.

B. Intrusion detection systems for outbreak identification

Often, in a wireless environment, the outbreak identification is associated with the node failure identification [START_REF] La Polla | A survey on security for mobile devices[END_REF], [START_REF] Shabtai | Intrusion detection for mobile devices using the knowledge-based, temporal abstraction method[END_REF]. However, the presence of an unwanted epidemic could not be generally seen as a node failure. In fact, an infection does not necessarily hinder basic node functionalities [START_REF] Wang | Understanding the spreading patterns of mobile phone viruses[END_REF]. Furthermore, a malware might be programmed to spread through the network without disabling nodes functionalities in order to maximize the attack impact on the network [START_REF] Khouzani | Maximum damage malware attack in mobile wireless networks[END_REF]. In the mentioned cases, Intrusion Detection Systems (IDS) have been proposed [START_REF] Shabtai | Intrusion detection for mobile devices using the knowledge-based, temporal abstraction method[END_REF], [START_REF] Gao | Modeling and restraining mobile virus propagation[END_REF]. In this paper we specifically refer to host-based Intrusion Detection Systems that, when present on mobile devices, are capable of identifying the presence of malware monitoring continuously a set of relevant parameters and applying several different information extraction techniques to the data gathered. Collecting information on runtime code, resources and network usage, IDSs are capable to detect the anomalous behaviors of nodes caused by malwares without the need of signature databases.

By following the taxonomy presented in [START_REF] Mian | A survey of service discovery protocols in multihop mobile ad hoc networks[END_REF], our algorithm can be classified as a part of the Service Discovery Protocol (SDP) that uses a passive form of search. More specifically, our algorithm can be considered from a SDP's perspective as a service in the network that keeps track of the ongoing epidemics and informs the searcher about the malicious nodes when queried.

C. Search and pursuit

Traditionally search and pursuit games have been addressed for the definition of strategies that maximize the performance of a searcher entity against a worst-case adversary. In these games, one or more searchers try to find and capture one or more evaders. If we consider the epidemic as an evader, we can apply search and pursuit methodologies to find the best trajectories for the searcher to move in order to cure and immunize the network. The existing solutions focus on the searcher's motion planning to find worst-case bounds on its performance. Following the taxonomy presented in [START_REF] Chung | Search and pursuit-evasion in mobile robotics[END_REF] our algorithm would be deployed in a discrete, finite and scale-free graph [START_REF] Pastor-Satorras | Epidemic Spreading in Scale-Free Networks[END_REF]. Furthermore, our algorithm runs on a speed-constrained single searcher, whose sensor model uses imperfect detection with finite range. There are different works where this class of systems is approached [START_REF] Vieira | Scalable and practical pursuit-evasion with networked robots[END_REF], [START_REF] Lavalle | Finding an unpredictable target in a workspace with obstacles[END_REF], however the particular set of conditions on which our proposal is dependent has not been treated in literature.

III. MAIN ASSUMPTIONS

In this Section we describe the main assumptions on which our work is based, and we give some details regarding the epidemic dynamics and the network model. We suppose that sensors have an operating system, computational and communication resources that make them capable to perform advanced applications [START_REF] Akyildiz | Wireless multimedia sensor networks: A survey[END_REF]. Furthermore, we assume that:

• no infrastructured access to an external network is provided, and the sensors communicate only over short-range radio links; • the proximity malware is self-contained in a software package that is injected into a set of sensors (the initial malicious spreaders) and spreads across the network by exploiting the short-range wireless communication capabilities of sensor nodes [START_REF]Symbos cabir[END_REF], [START_REF]Ios ikee[END_REF]; • when the malware infects a node, it shuts down its communication capabilities, except those useful to keep spreading [START_REF] Khouzani | Maximum damage malware attack in mobile wireless networks[END_REF]; • after a certain time that a node has been in contact with an infected neighbor, it will accept to receive the software package containing the malware; • an IDS, as those mentioned in Section II-B, is put in place in the WSN to detect the presence of the malware [START_REF] La Polla | A survey on security for mobile devices[END_REF]; • when a malware outbreak is detected by the IDS, a searcher is sent on the infected node to install a software package containing the cure that can safely eradicate the infection; • the cure is always a clean image of the operating system that is re-uploded on the infected node, regardless of the type of malware that has infected it; • a flying robot is used as the searcher in order to consider any kind of WSN deployment, even in harsh and remote scenarios; • all the messages between the infected nodes and the searcher are directly embedded in Layer 2 (L2) frames, because L2 primitives are usually implemented by the network interface card (NIC) hardware. Therefore, they can be considered reliable even if the functioning of the node is heavily compromised; • it is supposed that the geographical localization of nodes is available in form of predefined coordinates or through the presence of a GPS system into them. • a secure interface on the sensors is available to guarantee low level access to the wireless interface [START_REF] Schmidt | On the deployment of mobile trusted modules[END_REF], as explained in the following. Concerning the last assumption, the secure access could be granted by an operating system that supports protected memory for kernel operations [START_REF] Schmidt | On the deployment of mobile trusted modules[END_REF]. Furthermore, several works presented the possibility of a secure boot of a node after the retrieval of a new part of the operating system [START_REF] Grossschadl | Reassessing the tcg specifications for trusted computing in mobile and embedded systems[END_REF], [START_REF] Aciicmez | A trusted mobile phone prototype[END_REF], as also specified by the guidelines of Trusted Computing [START_REF] Tcg | Tpm main part 1 design principles[END_REF]. Thus, we also assume that sensors are able to replace a part or the whole operating system by downloading some software modules that, in our approach, will be transferred via wireless interface as described in Section IV.

IV. DISTRIBUTED CURING ALGORITHM

Our idea is to begin to inoculate the cure in the region with the highest density of infected nodes. In our work the density perceived by a node is intended as the number of reachable neighbors versus the node's sensing range. If we consider that all the nodes are of the same kind, we can just use the total number of neighbors as an indication of the density of a circular area of which the node is the center. Our Distributed Curing Algorithm (DCA) can be split in two concurrent processes. The first process is the Alerting Process, where the nodes exchange information about the diffusion of an epidemic. This process is carried out by the infected nodes themselves [START_REF] Shabtai | Intrusion detection for mobile devices using the knowledge-based, temporal abstraction method[END_REF]. The second process, carried out by the searcher, is the Healing Process which can be split in two phases that are continuously reiterated: (i) the positioning phase where the searcher, aware of the epidemic, moves towards it and (ii) the curing phase where the searcher node cures the infected ones. After those phases the algorithm cycles and starts again with phase (i).

A. The Alerting Process

The responsible of the alerting process at each node is the IDS (see Section III). When the IDS detects that some malware is compromising the functioning of the node, it starts to send an SOS message every ∆t SOS intervals by using the node's short range interface. As explained in Section III, SOS messages are directly embedded into L2 frames.

Each SOS message contains:

• Sender id (SiD): A 32 bit label which uniquely identifies the node that generated the message.

B. The Healing Process

During the Positioning phase, phase (i), a searcher is constantly patrolling the area where the nodes are deployed; it constantly monitors its short range interface looking for SOS message. If one of such messages is received the searcher moves toward the point indicated in SP. If more than one SOS message are received the searcher moves toward the point indicated in SP of the message with the highest nKIN. For further reference, we name the movement scheme as CIPS, (Critical Infection Point Seeker).

During the Curing phase, phase (ii), the cure is actually inoculated to infected nodes. The inoculation consists in an interaction between the searcher and the IDS of an infected node. The first transmits a clean image of the operating system to the nodes. This copy is used by the IDS to overwrite the infected one. When the replacement is completed the infected node is rebooted as a healed node. All the communication between the searcher and the infected nodes are carried out through L2 messages for the reasons outlined in Section III. Each message from the searcher to the nodes is signed so that it can be recognized as genuine by the secure routines of the infected nodes [START_REF] Schmidt | On the deployment of mobile trusted modules[END_REF]. When the searcher arrives at the target starts to advertise itself to the infected nodes by issuing a "Hello" message every ∆t Hello seconds. The "Hello" message contains an identifier of the searcher and the security signature. These informations are extracted and stored by the receiving nodes.

The image of the operating system stored by the searcher is fragmented in chunks, we assume that each chunk has a size that allows transmitting it in a single L2 frame. This size strongly depends on which L2 technology is used. Chunks are cached by the nodes so they can be shared between many infected nodes that are downloading the image. The download of the entire code is performed through the broadcasting of two message types, the Interest and the Data. An Interest is used to request a specific chunk. Once an infected node receives a "Hello" message from a searcher it starts the downloading procedure which has the form of an "Interest/Data" messages exchange. When the searcher (or any infected node) receives an Interest, it broadcasts the correspondent chunk within a Data message. The Interest-Data exchange continues until the entire image is downloaded. In case of a message loss, the Interest is transmitted again. In order to reduce the collision probability arising from multiple simultaneous transmissions (e.g., in the presence of two or more infected nodes that can reply to the same Interest), each node I waits a random defer time T D before transmitting the Data. During T D , I monitors the channel to detect the same transmission performed by other nodes. Finally, if no node has issued the Data, I sends the packet.

When the download is complete the searcher returns in phase (i) and starts again to search for SOS messages.

V. MATHEMATICAL FORMULATION

The Targeted Curing Problem (TCP) consists in determining the positions that a searcher should successively cover to We propose a mathematical formulation of the TCP that is capable of providing an optimal solution. However, the mathematical formulation is not directly applicable to real cases, because it requires the complete a-priori knowledge of the network and nodes' characteristics, as well as the complete description of the diffusion dynamics. Hence, in Section VI, we will use the results of the mathematical model as a benchmark for our distributed algorithm.

We provide a mathematical programming formulation for the problem, which involves only linear constraints and binary variables. First, we characterize the states and the transitions among them. Then, we will define the parameters used in the model, the optimization variables and their role. Finally, we will detail the objective function and the model constraints.

States and transitions

In order to characterize the different states in which each node can be, we use the diagram of Fig. 1. In a given time, a node can be in one of the following states: 1) Uninfected 2) Getting Infected 3) (Infected and) Malicious 4) Getting Cured 5) Cured

In Table I we describe the transitions between each couple of states as in Fig. 1. The time intervals used in the Table will be explained in the next subsection.

Parameters

In the following list, we introduce all the parameters used in the mathematical model. node at which the cure is inserted The parameter T m (time to move) is the smallest time unit considered in this work. Hence, we consider it as the unitary time unit for the model and the distributed algorithm. The parameter T t (time to transfer) can vary within the range between 3 and 5 T m , by following a uniform distribution among the nodes. The parameter T a (time to access) is the time needed to the searcher to access the secured part of the compromised node, after the searcher verified that the security key has been successfully received, its value is set to 2 T m . We tested the system and made a preliminary time parameters tuning by using the ns-2 simulator.

As we devised the use of a flying robot as searcher node, there is a physical path between any pair of nodes with the time needed for the searcher to travel this distance being d ij . The wireless links used for the model are taken from an adjacency matrix that represents the topologies used in the simulative approach.

Variables

We classify the optimization variables in two groups. The first group contains the variables of the problem, which describe the current state of each node of the network at each time period and the movement of the cure, while the second group contains conditional variables that are used to simplify the model.

State and decision variables x t si equal to 1 iif node i is in state s ∈ {1, 3, 5} at the beginning of period t x pt si equal to 1 iif node i is in state s ∈ {2, 4} for p time units at the beginning of period t y t i equal to 1 iif node i carries the cure at the beginning of period t z t ij equal to 1 iif the cure is starting to travel from i to j at the beginning of period t Conditional variables Y t i equal to 1 iif node i is connected to the cure M t i equal to 1 iif node i is connected to at least a node in state 3 and not to the cure C t i equal to 1 iif node i is connected to at least a node in state 1, 2 or to the cure S t i equal to 1 iif node i is not connected to nodes in states 3 and not connected to the cure X t equal to 1 iif at least one node is infecting or malicious at the beginning of period t

Objective function and constraints

The objective function aims at minimizing the time period at which the infection is extinguished (no malicious or infected nodes left):

min t∈T X t .
The constraints of the problem can be classified in different groups. The constraints in Equation ( 1), ensure that conditional variables take the correct values. while the constraints in Equation ( 2) translate mathematically the state transitions introduced in Fig. 1. These constraints are non-linear. However, because all involved variables are binary, we can use a well-known technique to linearize the products. Namely, each product of binary variables var 1 var 2 in the constraints above can be replaced by a new real variable prod that satisfies the following constraints: prod ≤ var 1 prod ≤ var 2 prod ≥ var 1 + var 2 -1.

Y t i ≥ y t i i ∈ N, t ∈ T Y t i ≥ y t j ij ∈ E, t ∈ T Y t i ≤ y t i + ij∈E y t j i ∈ N, t ∈ T M t i ≥ x t 3j -y t i - ij ∈E y t j ij ∈ E, t ∈ T M t i ≤ ij∈E x t 3j t ∈ T M t i ≤ 1 -y t i - ij∈E y t j t ∈ T C t i ≥ x t 1j ij ∈ E, t ∈ T C t i ≥ x pt 2j ij ∈ E, t ∈ T, p = 0, . . . , d j -1 C t i ≥ x t 5j ij ∈ E, t ∈ T C t i ≥ y t i i ∈ N, t ∈ T C t i ≥ y t j ij ∈ E, t ∈ T C t i ≤ y t i + ij∈E (y t j + x t 1j + x t 5j + di-1 p=0 x pt 2j ) t ∈ T S t i ≤ 1 -y t i i ∈ N, t ∈ T S t i ≤ 1 -y t j ij ∈ E, t ∈ T S t i ≤ 1 -x t 3j ij ∈ E, t ∈ T S t i ≥ 1 - ij∈E (y t j + x t 3j ) -y t i t ∈ T X t ≥ i∈N x t 2i + x t 3i 2|N | t ∈ T (1)
x t 1i = x t-1 1i S t-1 i i ∈ N, t ∈ T * x t 1i = x t-1 1i i ∈ N, t ∈ T \T * x 0t 2i = x 0t-1 2i S t-1 i i ∈ N, t ∈ T \T * x 0t 2i = x 0t-1 2i S t-1 i + x t-1 1i M t-1 i i ∈ N, t ∈ T * x pt 2i = x pt-1 2i S t-1 i + x p-1t-1 2i M t-1 i p = 1, . . . , d i -1, i ∈ N, t ∈ T x t 3i = x t-1 3i + x di-1t-1 2i M t-1 i i ∈ N, t ∈ T \T * x t 3i = x t-1 3i (1 -Y t-1 i ) + x di-1t-1 2i M t-1 i i ∈ N, t ∈ T * x 0t 4i = x 0t-1 4i (1 -Y t-1 i ) i ∈ N, t ∈ T \T * x 0t 4i = x 0t-1 4i (1 -Y t-1 i ) + x t-1 3i Y t-1 i i ∈ N, t ∈ T * x pt 4i = x pt-1 4i (1 -C t-1 i ) + x p-1t-1 4i C t-1 i p = 1, . . . , d i -1, i ∈ N, t ∈ T x t 5i = x t-1 5i + x di-1t-1 4i C t-1 i i ∈ N, t ∈ T \T * x t 5i = x t-1 5i + (x t-1 1i + di-1 i=0 x pt-1 2i )Y t-1 i + x di-1t-1 4i C t-1 i i ∈ N, t ∈ T * (2)
For simplicity, we avoid rewriting the linearized constraints. We describe next the cure movement.

y t i = 0 i ∈ N, t ≤ t * -1 y t * i * = 1 y t * i = 0 i ∈ N \i * y t i = ij∈Ec z t-dij ji + y t-1 i - ij∈Ec z t-1 ij t ∈ T ij∈Ec z t ij ≤ y t i ij ∈ E c , t ∈ T
Finally, the following constraints characterize the initial conditions of the system, and enforce that all optimization variables be {0, 1}-valued.

x 0 1i = 1 i ∈ N \N * x 0 3i = 1 i ∈ N * x 0 1i + x 0 3i + x 0 5i + di-1 p=0 (x p0 2i + x p0 4i ) = 1 i ∈ N Y, M, C, S, X, x, y, z ∈ {0, 1}

VI. PERFORMANCE EVALUATION

In this section we compare the movement scheme computed in our algorithm, CIPS, to two other schemes. All three schemes present a common curing phase, i.e. the one described in section IV, but differs on the movement path of the searcher through the WSN.

The first alternative is to let the searcher move according to Random Way Point model (RWP). This approach represents a simple yet effective approach, where no effort is made to optimize the movements. In the following we will refer to it as the RWP approach. The second alternative consists in letting the searcher move according to the pattern determined by the analytical model defined in Section V. The latter requires the complete a-priori knowledge of the network and nodes' characteristics as well as the complete description of the diffusion dynamics. Nonetheless, it allows us to have an upper bound on the performance of our proposal. In the following we will refer to it as the MM (Mathematical Model) approach. We have implemented RWP and CIPS in the ns-2 [START_REF]Network Simulator-ns (version 2)[END_REF] simulator, while the MM has been coded in the FICO Xpress Suite and Mosel language [START_REF]Fico xpress optimization suite[END_REF].

The reference simulated scenario is 160 m x 160 m square area. Inside this area a variable number of nodes is placed according to a regular grid pattern. The number of nodes in the grid can vary as it follows [START_REF] Lavalle | Finding an unpredictable target in a workspace with obstacles[END_REF]49,64,81,100]. Hence, the distances between the nodes varies accordingly, specifically they are respectively [START_REF]Data Sheet available on line[END_REF][START_REF] Pastor-Satorras | Epidemic Spreading in Scale-Free Networks[END_REF][START_REF] Gao | Modeling and restraining mobile virus propagation[END_REF][START_REF] Wang | Understanding the spreading patterns of mobile phone viruses[END_REF][START_REF] Brown | Software updating in wireless sensor networks: A survey and lacunae[END_REF] m.

All the nodes are equipped with a single IEEE 802.11 interface and a Ricean fading model takes into account the multi-path effects due to various obstacles. As shown in Table II, Physical and MAC parameters are based on IEEE 802.11g and transmission power and receiver sensitivity figures are taken from data-sheets of devices available on the market [START_REF]Data Sheet available on line[END_REF]. It is worth to note that the maximum distance considered in our grid (32 m) is equal to the maximum achievable distance to have a reliable transmission in Table II. The searcher and the first set of infected node are initially placed at random positions within the grid using a uniform distribution. Once the simulation starts, the searcher moves according to the mobility pattern computed by the RWP, CIPS or MM approach. The searcher speed is set according to the literature in this field [START_REF] Natalizio | Two families of algorithms to film sport events with flying robots[END_REF].

A. Result with 25 nodes

The first simulation set was carried out considering a network of only 25 sensors. This reduced number of sensors was chosen due to the complexity of the mathematical model. Although this number is quite small the results obtained give a clear idea of how CIPS relates with the other two. In the next section we will evaluate how the CIPS and the RWP schemes scale with the number of nodes.

Our main objective is to evaluate the evolution and the steady state number of infect nodes to understand if the system is capable to recover a network from an expanding infection.

In Fig. 2 the percentage of infected nodes versus time is shown.

The MM approach is the best in preventing the epidemic diffusion and is the quickest in extinguish the infection. The RWP scheme presents the lowest performance in terms of both diffusion of the infection and recovery time. The CIPS scheme suffers a high percentage of infected nodes at the infection peak (i.e. when the malware affects the maximum number of nodes). This number is close to the one obtained with RWP. This is due to the high latency associate with the Alerting Process. However, in spite of this initial latency, CIPS quickly Tables III reports the following metrics: (i) the distance traveled by the searcher until 90% of nodes are healed, (ii) the peak infection, i.e. the maximum number of nodes which are infected at the same time, (iii) the time at which the peak is reached, and (iv) the time to settle (TTS), i.e. the time needed to heal 90% of the nodes.

Table III confirms the trend formerly described. The MM approach is successful in both limiting the malware diffusion and quickly healing the network, while the CIPS approach suffers from the finite amount of time required to get the information about the network. Nonetheless, the CIPS approach far outperforms the RWP approach.

The distance traveled by the searcher is a metric of particular interest. A shorter traveled distance implies a lower amount of energy consumed by the searcher. The CIPS approach requires the searcher to travel about 0.27 times the distance required by the RWP approach and about 2.55 times the distance required by the MM approach.

The infection peak gives a measure of how the malware is able to make the network inoperative. A high infection peak means that only few nodes continue to properly function. Unfortunately the CIPS approach has the same peak as the RWP approach. However, the CIPS approach presents a TTS much shorter than the RWP approach and very close to that of the MM approach. This means that, due to the accurate movement pattern computed by CIPS, the aimed cure inoculation is effective for a faster network recovery.

B. Result varying the number of nodes

The high computational load and complexity of the mathematical approach did not allow us to determine a solution for grids containing more than 25 nodes. For this reason, for a higher number of nodes we used only the CIPS and the RWP schemes for comparison.

In Table IV, if we consider the distance traveled by the searcher, it can be observed a different trend between the two compared approaches. The traveled distance roughly increases with the number of nodes when the CIPS approach is considered, whereas it is roughly decreasing when the RWP scheme is considered. This is due to the fact that the CIPS approach leads to a movement scheme that is closely related to the network topology. When the number of nodes increases the searcher is forced to prolong its journey to cover the higher number of infected nodes in remote areas. Vice versa, for the RWP movement scheme, when the number of nodes increases, the probability that such an erratic movement produces a positive effect is raised as it travels less distance for curing the same percentage of nodes.

In Fig. 3, we present the percentages of infect nodes versus time for greater number of nodes, specifically for 49 (3a), 64 (3b) and 100 (3c) nodes. These results confirm the trend already found previously. The CIPS approach has a lower peak value and a faster TTS in respect to the RWP approach. We can also notice that a more congested topology affects the performance of the approach. For 25 nodes the infection peak for CIPS and RWP is the same. However, as the number of nodes increases, the CIPS approach obtains a lower infection peak. This is due to the fact that the CIPS approach achieves a quickly delivery of the cure, where it is most needed. The effectiveness of the proposed approach is also confirmed by the shorter TTS.

VII. CONCLUSIONS AND FUTURE WORKS

In this paper we addressed the issue of facing a malware spreading in a Wireless Sensor Network. Using the concepts of controlled mobility and information diffusion we defined an algorithm (i) to notify the spreading of the malware, (ii) to lead an autonomous flying robot, which can cure infected nodes, along a path in the sensor network and (iii) to heal the infected nodes. To benchmark the proposed algorithm we developed a mathematical model which defines the best path to be followed by the flying robot to cure the infected nodes in the shortest time. Using the results obtained from the mathematical model as the upper bound and the ones from the application of random waypoint movement as the lower, we have assessed the satisfactory performance of the proposed algorithm. A larger and more comprehensive mathematical model is expected as the most immediate step in order to provide more generalized solutions which can be applied in real scenarios followed by a tuning study of the proposed autonomic approach.

Fig. 1 :

 1 Fig. 1: Nodes states

Fig. 2 :

 2 Fig. 2: Percentage of infected elements for the 25-nodes scenario.

  This is the number of infected nodes in the sensing range of the sending node. A sending node can infer this number by hearing to SOS message coming from other nodes in a reference time interval ∆t observ = 2∆t SOS If no other SOS message are received then this field is set to one.Every node, both infected and not, participates in rebroadcasting the SOS messages. A node which receives a SOS message waits for ∆t observ seconds before to rebroadcast it. If more than one SOS messages are received only the one with the highest nKIN is retransmitted. Obviously, local nKIN is considered also in the ranking.

• Sender position (SP): The GPS position of the node which generates the message. Since in our scenario the nodes are stationary this information can be stored in the secure memory at time of node installation. The GPS position is coded through a 64 bit long field.

• The number of known infected nodes (nKIN):

TABLE I :

 I State transitions

		Transition States Happens when
				a node in state 1 will switch to state
		A	1⇒2	2 if it has been connected for Ta time units to any number of nodes
				in state 3
				a node in state 2 will switch to state
		B	2⇒3	3 if any number of nodes in state 3 have been connected to it for, at
				least, Tt time units
				a node in state 3 will switch to state
		C	3⇒4	4 if it has been connected for Ta
				time units to the searcher
				a node in state 4 will switch to state
		D	4⇒5	5 if any number of nodes in state 1 or 2 or the searcher are connected
				to it for, at least, Tt time units
				a node in state 2 will switch to state
		E	2⇒5	5 if it has been connected for Ta
				time units to the searcher
				a node in state 1 will switch to state
		F	1⇒5	5 if it has been connected for Ta
				time units to the searcher
		Data
	T	set of time units
	T * set of even time units
	T m time interval for the searcher to choose a new direction
	T t	time needed for a node to download a curing or
		malicious module
	T a	time needed for the searcher to access the secured part
		of a node
	N	node set
	S	possible states for each node
	E	wireless links, bidirected
	E c physical path, bidirected
	d e	length of edge e in time units
	d i	transition duration of node i in time units
	d ij time needed by the searcher to travel from i to j
		Initial conditions
	N * subset of nodes where the infection starts
	t *	time unit at which the cure is inserted
	i *

TABLE II :

 II 802.11g Simulation Parameters.

	PHY Parameter		Value		MAC Parameter Value
	Frequency			2.4 GHz		SlotTime			9 µs
	Receive Sensitivity	-86 dBm		SIFS			16 µs
	Transmission Power 18 dBm		Preamble Length	96 bit
	Max distance		32 m
						Infection Dynamics, 25-nodes Grid
		60 70								RWP CIPS MM
	Percentage of Infected Nodes	20 30 40 50
		10
		0	0	50	100	150	200	250	300	350	400
							Time

TABLE III :

 III 25-nodes Simulation Performances Comparison. The recovery time of CIPS is about 70s greater than the time needed by the MM and about 180s lower than the time needed by RWP. Consequently, the time spent by CIPS to gather information from the network is well repaid by the better functioning of the movement scheme.

	Scheme	Distance [m]	Peak [%]	Peak Time [s]	TTS [s]
	RWP	3510	64	101	261
	CIPS	959	64	96	161
	MM	376	40	81	121
	heals the network.

ACKNOWLEDGMENT

This work has been partially supported by: a)the STEM-Net, PRIN-National Italian Project # H21J11000050001, financed by the Italian Ministry of University and Research, and b) by the Labex MS2T,which is funded by the French Government, through the program "Investments for the future", managed by the National Agency for Research (Reference ANR-11-IDEX-0004-02). The research of Nicola Roberto Zema is partially supported by European Union (EU), European Social Fund (ESF) and Calabria Local Goverment.


Valeria Loscrí

Enrico Natalizio
email: enrico.natalizio@hds.utc.fr

Francesca Guerriero
email: guerriero@unical.it

Nathalie Mitton

Efficient Coverage for Grid-Based Mobile Wireless Sensor Networks

In this paper we propose a new coverage technique for mobile wireless sensor networks in which the sensors are arranged in a square grid. Our technique is totally distributed and based only on local information. We show how this extremely simple technique is able to reach good performance in terms of coverage even when sensor fields with different features are considered. Specifically, we focus on sensor fields with and without obstacles for different densities of nodes. We show the effectiveness of the proposed technique by comparing it with the results obtained by an optimization model and two coverage algorithms, based on a genetic approach and virtual forces, respectively. Results of simulations show how, in the worst case, the coverage obtained by our scheme is 14% smaller than the coverage obtained with the optimization model. When the size of the field increases the searching space of our scheme increases too and we obtain a better performance in terms of coverage. In fact, for larger sensor fields, both with obstacles and without obstacles, our scheme outperforms the other two algorithms.

I. INTRODUCTION

In distributed Wireless Sensor Networks (WSNs), design of the placement of sensors devices in the sensor field is a very important issue. Efficient sensor placement strategies allow to minimize cost and reach a high level of accuracy [START_REF] Chakrabarty | Grid coverage for surveillance and target location in distributed sensor networks[END_REF]. In the art gallery problem, cameras are deployed such that the whole gallery is thief-proof [START_REF] O'rourke | Art Gallery Theorems and Algorithms[END_REF], [START_REF] Hoffmann | The art gallery theorem for polygons with holes[END_REF]. A wireless sensor network must achieve the specified coverage level of the application so that the quality of service provided by the wireless sensor network can be guaranteed. The coverage is considered a critical issue that has been the focus of many research activities with different associated issues, such as presence of obstalce, coverage of specific areas, etc. In [START_REF] Sh | An Approximate Approach for Area Coverage in Wireless Sensor Networks[END_REF], authors introduce the concept of transparent obstacle, that is a specific zone where a node cannot be deployed, but the signal is allowed to pass. Their proposal consists in the reduction of the original coverage problem in a discrete approach named Minimum Geometric Disk Cover with Candidate position (MGDCCP) and they present a polynomial-time approximation scheme instead of directly considering the MGDCCP, that is proved to be NP-hard. Some other approaches consider the coverage problem in combination with Particle Swarm Optimization (PSO) and Differential Evolution [START_REF] Maleki | A new Approach for Area Coverage Problem in Wireless Sensor Networks with Hybrid Particle Swarm Optimization and Differential Evolution Algorithms[END_REF], by considering as primary QoS parameter the reduction of the energy consumption. Many sensor deployment algorithms attempt to fully cover a sensor field by using the minimum number of sensors or by minimizing the cost associated to the nodes. In [START_REF] Chang | Obstacleresistant deployment algorithms for wireless sensor networks[END_REF] authors propose a method to deploy sensors to provide full coverage of a sensor field in presence of obstacles. In [START_REF] Gallais | Localized sensor area coverage with low communication overhead[END_REF] authors propose a distributed algorithm in order to activate a subset of sensors to fully cover the entire sensor field all at once. In [START_REF] Simplot-Ryl | Localized sensor area coverage with low communication overhead[END_REF] authors try to ensure that each point in a sensor field is covered by at least k sensors. In order to cover the field in an effective way, they select a subset of sensors for ensuring k-coverage and k -connectivity. Some coverage techniques consider the components in the sensor field such as sensors, obstacles or preferential fields as virtual forces sources and try to balance virtual forces through the deployment of the devices [START_REF] Heo | An intelligent deployment and clustering algorithm for a distributed mobile sensor network[END_REF] and [START_REF] Howard | Mobile sensor network deployment using potential fields: A distributed, scalable solution to the area coverage problem[END_REF]. In [START_REF] Zou | A distributed coverage-and connectivitycentric technique for selecting active nodes in wireless sensor networks[END_REF] authors propose CCAN that selects a connected dominating set in a dense wireless sensor network such that the coverage probabilities of the given points (e.g. specific targets) are larger than a given parameter. In many applications, some specific areas need to have a larger coverage than others, in this case the problem is that of deploying a wireless sensor network to fully cover these areas as well as not leaving uncovered the rest of the field. In [START_REF] Ke | Constructing a wireless sensor network to fully cover critical grids by deploying minimum sensors on grid points is np-complete[END_REF] authors consider the problem of deploying a wireless sensor network to fully cover critical grids of equilateral triangles by deploying the minimum number of sensors on grid points and they show that this problem is NP-Complete. In the circle covering problem, usually homogeneous circles are used to fully cover equilateral triangles [START_REF] Nurmela | Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles[END_REF], rectangle [START_REF] Melissen | Covering a rectangle with six and seven circles[END_REF], and squares [START_REF] Nurmela | Covering a square with up to 30 equal circles[END_REF]. The circle covering problem is different from the covering problem considered in this paper since the circles are independent and can be moved anywhere. Moreover, we have to consider the constraint of connectivity, so the potential available position in the sensor field are limited. Usually a sensor field is divided into square grids [START_REF] Chakrabarty | Grid coverage for surveillance and target location in distributed sensor networks[END_REF], [START_REF] Shen | Grid scan: a simple and effective approach for coverage problem in wireless sensor networks[END_REF] and in [START_REF] Ke | The critical-square-grid coverage problem in wireless sensor networks is np-complete[END_REF] the problem of deploying the minimum number of sensors on grid points to construct a wireless sensor network fully covering critical square grids is considered and authors show that this problem is NP-Complete. Several of the mentioned schemes consider sensors equipped with mobility capability. In this paper we focus on the deployment of mobile sensor nodes on a grid sensor field where a certain number of obstacles can limit transmission and mobility capabilities of the nodes. The objective of our study is to design a simple heuristic able in a totally distributed way to improve the coverage of the mobile sensor network by using local information only.

In order to show the effectiveness of the proposed technique we introduce an optimization model that is able to find the best position for a sensor node in terms of coverage and two algorithmic approaches: a centralized technique based on a genetic algorithm and a virtual forces based approach. Simulation results show how our technique is able to produce a coverage that is close to the optimization model, and when the size of the field increases it overcomes the virtual forces technique for both the scenarios, with and without obstacles.

In Section II we consider square grids. In Section III we present the optimization model used as a benchmark. In Section IV we present the details of the simple heuristic we propose and we present two comparison centralized approaches: the former based on a genetic approach and the latter based on the Virtual Forces concept. Moreover, we explain the results in Section V and finally, we conclude the paper and consider a discussion of future research in Section VI. In the Appendices, we introduce the concept of Zone of Interest (ZoI), that is a specific zone in the field that requires a larger coverage by the sensor network, and we show how our mathematical model and heuristic can be easily extended in order to consider different ZoI in the field. For space reasons, we have omitted the results of this variant of the heuristic that we will present in an extended version of the work.

II. SQUARE GRID NETWORKS

A wireless sensor network is said grid-based if it consists of a (potentially unbounded) number of identical sensors arranged in a square grid. A cell can be occupied by at most one sensor node. Classically, if a sensor has a maximum transmission range said t r , then each node is able to communicate with all nodes within the circle of radius t r in a direct way. In a grid-based network we need to model the connectivity among nodes in a different way, i.e. using a Lee sphere of appropriate radius [START_REF] Golomb | Perfect codes in the lee metric and the packing of polyominoes[END_REF]. Let the length of the sides of the squares of our grid be of unitary length. The distance among the squares in the grid can be measured in terms of Manhattan metric, that is the distance between two squares is the sum of the horizontal and vertical distances between the centers of the squares. With "horizontal" and "vertical" we indicate the two perpendicular directions parallel to the sides of the squares in the grid. Definition 1. A Lee sphere of radius r centered at a given square consists of the set of squares that lie at Manhattan distance at most r from that square as shown in Fig. 1.

This approximation facilitates the representation of the coverage in the grid-based networks. In this paper we refer to the Lee sphere of radius 2 as shown in Fig. 1(b). In practice, all the points that are within the squares are considered covered by a node at the center of the Lee sphere.

In the rest of the paper we will refer to the farthest frame of cells around the sensor node as exterior frame and to the closest as interior frame. Also we will take account of the possibility to have a physical obstruction in the cells of the grid, we will refer to this obstruction that occupies either part or the whole cell as an obstacle.

III. THE OPTIMIZATION MODELS

In this section, we present different formulations for the problem under consideration, defined in such a way to handle

A. Field without obstacles

The first mathematical formulation whose aim is to deploy the sensors in a field without obstacles such that the coverage is maximized is given in what follows:

max h/d i=1 w/d j=1 δ ij (1) r -(i -x k ) 2 + (j -y k ) 2 ≥ M (φ ijk -1), ∀i, j, k (2)
δ ij ≤ n k=1 φ ijk , ∀i, j (3)
M δ ij ≥ n k=1 φ ijk , ∀i, j (4)
0 ≤ x k ≤ h/d , 0 ≤ y k ≤ w/d , ∀k (5)
x k , y k integer, ∀k

φ ijk binary, ∀i, j, k

δ ij binary, ∀i, j (7)
The objective function in (1) maximizes the number of locations covered by at least one sensor. Conditions (2) state that if the euclidean distance between the sensor k and the location (i, j) is lower than or equal to the coverage radius r than the variable φ ijk takes the value one, otherwise it is set to zero. Constraints (3) and ( 4) are logical constraints and ensure that the indicator variable δ ij takes on a value of one if the location (i, j) is covered by at least one sensor and zero otherwise. Finally, conditions ( 5)-( 8) represent the variable domain constraints. The mathematical formulation reported above is an integer nonlinear programming model, where the nonlinearity is confined to the constraints [START_REF] Batalin | Spreading out: A local approach to multi-robot coverage[END_REF].

In order to derive an integer linear model, the euclidean distance has been replaced by the following expression:

d x ik + d y jk -0.5min(d x ik , d y jk ), where d x ik = |i -x k | and d y jk = |j -y k |.
This approximation, introduced in [START_REF] Paeth | Graphics Gems V, Chapter II[END_REF], overestimates distance and yields error in interval 0% to 12%.

To eliminate the terms with the absolute value, we introduce the additional constraints reported below ([3]):

d x ik ≥ i -x k ∀i, k (9)
d x ik ≥ -i + x k ∀i, k (10)
d y jk ≥ j -y k ∀j, k (11)
d y jk ≥ -j + y k ∀j, k (12)
Thus, constraints (2) are replaced by the following conditions:

r -d x ik -d y jk + 0.5 min ijk ≥ M (φ ijk -1), ∀i, j, k (13)
where the variables min ijk , ∀i, j, k take the minimum value between d x ik and d y jk . Consequently, the following constraints need to be satisfied:

min ijk ≤ d x ik ∀i, j, k (14)
min ijk ≤ d y jk ∀i, j, k (15)
The proposed integer linear model (referred in the rest of the paper as no-obstacles optimization model NObOM) optimizes the function (1) subject to constraints ( 9)-( 15) and ( 3)-( 8).

B. Field with obstacles

It is worth observing that the mathematical formulation reported above can be easily extended to handle the specific situation in which some obstacles are present in the sensor field. In this particular case, it is sufficient to impose that the locations occupied by the obstacles cannot be considered as feasible positions where the sensors can be localized.

Let OBS = {( ĩ, j) | ĩ ≥ 1 and ĩ ≤ h/d and j ≥ 1 and j ≤ w /h } be the set of the positions in which the obstacles are located, the mathematical formulation of the problem in which the obstacles are considered (referred in the rest of the paper as obstacles optimization model ObOM), is obtained by replacing in the model reported above the constraints (5) with the following conditions:

0 ≤ x k ≤ h/d , 0 ≤ y k ≤ w/d , (x k , y k ) ∈ OBS ∀k (16)

IV. DISTRIBUTED ALGORITHM

In this section we present the details of the coverage map assisted technique. It is worth noting that this technique is totally distributed and based on local information only. The proposed algorithm is based on a local coverage grid map as depicted in green shaded cells in Fig. 2. The letters call a cell, the number represents their coverage degree. For instance, the upper right cell is cell a and has a coverage degree of zero. We assume that the transmission range is larger than the sensing range so that every node is able to communicate with nodes in its local coverage grid map. Thus, a node can exploit information that come from nodes placed within the exterior frame. In any case, the coverage will be computed by considering the Lee sphere model as shown in Fig. 1 (b). Each node, by communicating with its neighbors, is able to calculate the local map needed to compute the movement to improve the coverage. In Fig. 2, the Lee sphere of cell ac is represented by the grey-dashed cells, the bue-shaded cells are the cells occupied by nodes, while the number in each white cell is the number of nodes that cover that cell. Henceforth, we will refer to this number as the coverage degree of a cell.

Definition 1 (Coverage degree). The coverage degree of a cell represents the number of nodes that are in the neighborhood of this cell and can "sense" it. In our case, a node covers a cell if it lays in the Lee sphere of this cell. The basic idea of the algorithm is to base nodes movement on the information transmitted by the nodes placed in the cells of the exterior frame of the local map, i.e. in cells k, m, n, l, o, s, aa, ai, aq, ar, as, at, au, am and ae for a node in cell ac. Specifically, we individuate 8 possible directions of coverage degree computation and movement: North (N), North-East(NE), East (E), South-East (SE), South (S), South-West (SW), West(W), North-West (NW). In Fig. 2 the North and the South-East borders of cell ac are highlighted by a black border. North border is composed of cells k, m, n, l and o. south-east border is composed by cells ae, am, au, at and as. The algorithm sums up the coverage degree obtained on each border and makes the node move according to the highest difference between geographically opposite borders, as explained in the following 4 steps: STEP 1: Local Coverage Map Construction. The construction of the local coverage map is performed by each node using position information provided by neighboring nodes. This information can be regularly sent by using classical HELLO messages that contain the position of the sensor. It is important to notice here that sensors may have different coverage capabilities. In this case, the HELLO messages may also contain the identification of the covered cells. In this work we assume homogeneous capabilities of coverage and leave this issue as a future work. Of course, wireless environment is unreliable and it can happen that some information is missed, but the frequency of message exchange is such that the impact of some missed information can be neglected. The inclusion in HELLO messages is also possible, since the amount of additional information considered (e.g. the overhead of the protocol) is really minimal. This step allows every node to set up of a n × n matrix later referred as map, where n is the radius of Lee sphere. If x, y is the position of the current node, map(x -i, y -j) with i, j ∈ [0...n] is the coverage degree of cell at position x -i, j -i. For instance on Fig. 2, in the local map of node ac in position 5, 4, we have map(4, 4) = 1. STEP 2: Coverage Degree Computation. The coverage degree computation is performed at each node by summing up the coverage degree of nodes belonging to the same border. For example in Fig. 2 the North border coverage degree of node in ac is 2 + 2 + 3 + 2 + 2 = 11 and the South-East border coverage degree is 1 + 0 + 0 + 1 + 1 = 3. STEP 3: Direction Computation. In order to increase and balance the coverage provided by our algorithm, each sensor decides its movement direction depending on the difference of coverage measured on geographically opposite borders. Specifically, we compute the difference between the North and South borders, East and West borders, North-East and South-West border and North-West and South-East borders. Based on these differences, the sensors will move along the appropriate axis by choosing the highest absolute differential value. STEP 4: Movement. Upon the computation of the axis is completed, nodes decide their movement by choosing the lowest coverage density along the chosen axis and move in that direction. In case of equality, a random direction is chosen between candidates except if all 8 directions have the same degree. In this latter step, the algorithm terminates.

The details of the algorithm are given in the following pseudo-code. It is important to notice here that the algorithm is constantly, at a regular interval, run on each sensor. Moreover, we also add the termination condition to avoid oscillation. The termination condition holds whether there is equality between gradients on borders or if the current position has already been visited during the four previous steps except the last one. Indeed, our algorithms accepts that a node may take a bad decision once. We verified experimentally that four previous steps is enough to ensure the convergence of the algorithm.

It is worth noticing that the simple heuristic proposed in this work is a kind of greedy technique. This implies that in every iteration each node tries to reach its better solution that does not correspond to the global optimal. This kind of approach could imply the generation of loop that we will avoid by storing the last "four" positions of each node. We dealt simulations with different number of positions in order to make a kind of sensitivity analysis. Specifically, we perform tests by considering the last 3, 4, 5 and 6 positions, and we noticed that from 3 to 4 we could obtain different performance in terms of positioning, but from 4 to 5 and also 6, results were the same with the only difference that the greater the number of positions "stored"to be considered, the greater the number of iterations and for that we considered to store the last 4 positions. If a node occupies a position already occupied in the last iterations, it will stop moving again and the total algorithm will globally stop when all the nodes stopped. One important property of our algorithm is that it uses only local information. This makes it scalable and gives it the possibility to easily manage the obstacle avoidance. Indeed, obstacles can be easily taken into account for the movement decision by artificially setting the coverage degree value of the cell that they occupy to -∞ to induce a movement toward the obstacle or to +∞ to induce a movement against the obstacle. We will refer to this value as obstacle avoidance. The same parameter is used also to consider the border of the field. 1: Stop movement if (x(t), y(t)) == (x(t -2), y(t -2))or(x(t), y(t)) == (x(t -3), y(t -3))or(x(t), y(t)) == (x(t -4), y(t -4)) or all directions have the same coverage degree.

Algorithm 1 Coverage Map based Movement Algorithm

V. PERFORMANCE EVALUATIONS

In this section, we evaluate the performance of the proposed heuristic by comparing it with the optimization model presented in Section III and two algorithms that use a centralized genetic approach and a virtual forces based approach, respectively. All the techniques considered in this paper have been adapted to use the grid-based model described in Section II as far as the sensing model is concerned. As already outlined, we consider Lee sphere of radius 2.

For the performance assessment, we consider three increasing sensor field sizes and a variable density of nodes in the grid in order to evaluate the scalability of the simulated schemes. Also we present two simulation campaigns for sensor fields with and without obstacles. In this case we fix the number of node and make the percentage of obstacles in the field grow in order to show the effect of limiting factors on nodes' transmission and mobility.

A. Other Coverage Techniques

In the following we present the most important details of two algorithms taken from the literature that will be uses in the comparison with our scheme. In Table I we reported the values of the most important parameters used from these two schemes as well as our heuristic. 1) Genetic Algorithm: This technique is taken from [START_REF] Costanzo | Nodes self-deployment for coverage maximization in mobile robot networks using an evolving neural network[END_REF] and adapted to fit our grid-based coverage problem. The genetic algorithm is used as an optimization method in order to find the optimal solution by reducing the solution space through the evolutionary approach. A particular placement is coded as a member of a population by the sequence of x and y coordinates of all sensors in the grid as illustrated in Fig. 3.

Fig. 3: Placement coded in a chromosome

The objective of the optimization problem is formalized as the minimization of uncovered cells, consequentially, the fitness function used for the evolution of the population is:

f = # total cells -# covered cells (17)
This function takes a given placement and the positions of obstacles (if any) in the grid as input, and it gives a fitness value that represents the number of holes in the grid as output. Substantially, the population evolves through the genetic algorithm using the fitness function as the supervisor of the evolution process. The steps of the algorithm are:

1) random initialization of a population; 2) ranking of population members according to the fitness function; 3) selection, mutation and crossover of best members of the population; 4) repeat from point (1) until termination condition (maximum number of generations) is satisfied.

We tuned the algorithm by running some preliminary simulations in order to achieve the best results for the coverage. Firstly, a number of experiments were conducted to determine appropriate population size, size ranging from 100 to 1000 individuals. we obtained best performance in correspondence of 500. We also considered several simulations with different crossover methodologies, and we selected a crossover fraction equal to 0.8. Similarly, a Gaussian mutation methodology with scale and shrink factor equal to 1 was found as the best value in terms of performance. The values used for the mentioned parameters in the simulations are reported in Table I.

2) Virtual Forces Algorithm (VFA): VFA is a well-known technique used for deployment in mobile wireless sensor networks. It achieves good performance in terms of coverage by starting from a random placement, and by using a weighted combination of repulsive and attractive forces based on mutual distances among nodes. The main advantage of this approach is its flexibility to adapt to different scenarios also in presence of obstacle. The drawbacks regard the difficulty to tune opportunely some parameters that depend on the particular scenario and the fact that performance of VFA are strictly related to the tuning of the parameters for the specific scenario. We adapt the algorithm proposed in [START_REF] Batalin | Spreading out: A local approach to multi-robot coverage[END_REF] to fit assumptions and properties used in this work and obtain the best performance related to the specific scenarios considered. The values used for VFA in the simulations are reported in Table I.

B. Results

As already said, results show two simulation campaigns, which consider sensor grid with and without obstacles.

1) Field with no obstacles: Fig. 4 plots the coverage achieved by the mathematical model and the three algorithms for the three different grid sizes, when the number of nodes in the grid varies and no obstacles are present on the sensor field. We can see that for small grid size the coverage achieved by our technique is the worst, whereas for the intermediate size, it overcomes the results obtained by the VF algorithm. Furthermore, when we compare the coverage obtained with our technique and the virtual forces approach, we can observe how the heuristic outperforms the virtual force technique for the biggest size of the grid. This result is encouraging because it implies that our heuristic is scalable. The improved performance is related to an increased movement space. In practice, with the 15 × 15 grid, the heuristic can exploit more information. These considerations are confirmed by considering also a 25 × 25 grid, as shown in 4 (c). It is worth noticing that for a 25 × 25 sensor field size we reported results of neither the Optimization Model (NObOM) nor the Genetic Algorithm (GA). The reason is that when the size of the grid and the number of nodes increase, the number of potential solutions to be evaluated increases too and both approaches are extremely inefficient and time-consuming.

2) Field with obstacles: Fig. 5 plots the coverage achieved by the mathematical model and the three algorithms for the three different grid sizes, when the percentage of obstacles in the field varies. Specifically, we consider a number of obstacles ranging from 0 to 20 % in respect of the total number of cells in the field. In this case the coverage is computed by eliminating the squares occupied by the obstacles.

Fig 5 shows the results of the 4 techniques when a certain percentage of obstacles is present in the grid. The Optimization Model (ObOM) and the genetic approach are able to reach the maximum achievable coverage. This is due to the fact that both of them are based on global information and know perfectly the positions already occupied by obstacles. In this case we can observe as the perfromance of the heuristic outperform the Virtual Force Algorithm when we consider the increased size of the network (cases 15x15 and 25x25), and more specifically, the distance in terms of coverage improves when the network size increases.

VI. CONCLUSION

We proposed a new heuristic technique to opportunistically move sensor devices in order to accomplish different coverage requests. This heuristic is extremely flexible, adaptive and works in a distributed fashion. Based on local information it is able to "capture" the situation in the surrounding and nodes move in a greedy fashion by trying to cover the lesser covered zones. The surrounding information can both represent the information of how much a close point is covered and how much a node needs to be covered. This latter point allows to introduce the concept of "more interesting zone", that is a zone that for many reasons needs to be highly monitored. The heuristic can easily be implemented in simple sensor devices, because does not require much computation resources. In order to evaluate the effectiveness of this simple technique we considered three coverage approaches: an optimization model that gives the optimal solution in terms of coverage, a genetic based approach that works in a centralized way and a virtual forces based technique. We show that our approach allows to reach results close to those of the optimization model and the genetic approach and in certain scenarios, when the size of the sensor field increases, our scheme is able to outperform the virtual based approach. Moreover, we introduced some obstacles in the sensor field in order to understand if our approach is able to adapt the movement of nodes in an effective way when obstacles are present. Results are encouraging also in this specific condition.

APPENDIX

In the following appendices we present the preliminary study we performed by introducing the concept of Zone of Interest (ZoI). In a realistic field covered by mobile wireless sensors, it could happen that some regions of the field are "more" interesting than others. Hence some regions need to be monitored more precisely. We assume that a higher precision in sensing the area is given by a higher number of nodes that monitor it. Specifically, we show this situation in Fig. 6, where we the degree of interest of a specific cell in the grid is represented by the intensity of the filling color. The darker the color, the higher is the interest in monitoring that specific cell, and consequently more nodes are needed in the area.

In order to deal with this new concept, we present an extended version of both the mathematical model presented in Section III and the heuristic presented in Section IV.

MATHEMATICAL MODEL FOR FIELD WITH ZOI

In some applications, there are the needs to guarantee that some zones (the so-called Zones of Interest) are covered up to a certain degree. In what follows, we present three different formulations to represent the sensor deployment problem with zones of interests.

It is important to observe that both NObOM and ObOM can be easily extended to handle this specific situation. However, for the sake of simplicity, in what follows, we assume that the field is free of obstacles and thus NObOM can be used as basic optimization model.

In the first formulation (referred in the sequel as ZoI-Min), it is assumed that for each location (i, j), i = 1, . . . , h/d , j = 1, . . . , w/h , the minimum number of sensor cover ij that have to cover (i, j) is given. Thus, the aim is to find a sensor placement such that the number of locations covered by at least one sensor is maximized and the coverage constraints of the regions of interest are satisfied.

The related mathematical formulation is obtained by adding to NObOM n k=1 φ ijk ≥ cover i,j , ∀i, j. An alternative way to address the problem of cover ZoI is to maximize the number of sensors that cover these zones, by ensuring that each location is covered by at least one sensor. In this second formulation (denoted as ZoI-Max), let ZOI be the set of locations corresponding to the zone of interests, the objective function to be maximized assumes that : n k=1 ( ĩ, j)∈ZOI φ ĩj k subject to constraints (3)-( 15) and the condition reported in:

h/d i=1 w/d j=1 δ ij ≥ γ where γ is set to h/d × w/d ,
if each location has to be covered by at least one sensor. It is important to observe that it is possible to carry out a sensitive analysis on the value of the parameter γ in order to find the best trade-off between maximizing the number of sensors to cover ZOI and ensuring an acceptable coverage for the remaining locations.

ZoI-Max can be easily extended to ensure that each location belonging to ZOI is covered by exactly the same number of sensors. The corresponding optimization model (denoted in the sequel as ZoI-Eq ) is obtained by adding to ZoI-Max The degree of interest of a certain region of the sensor field can be defined in different ways, i.e. we can explicitly declare the number of nodes needed to cover a specific point/zone such as in the Optimization Model (ZoI-Min) defined above, or we can simply define a certain degree of interest through a weight associated to the zone. This second approach coincides with our basic heuristic (Basic-Heuristic in the following) proposed in Section IV and by the variants ZoI-Max and ZoI-Eq of the mathematical model NObOM. In practice, we associate a certain "weight" to a specific area. The weight represents the interest to cover the zone without explicitly associating a specific number of sensor. We will refer to the extension of the Basic-Heuristic as Ext-Heuristic (Extended-Heuristic). Specifically, in the Ext-Heuristic we take into account the information about the exterior frame as in the Basi-Heuristic but also the information contained in the interior frame. This extension is necessary when different degrees of interest are taken into account, since an increased necessity to cover a certain zone could not be captured by only considering the exterior frame. Specifically, we apply the same principle of the Basic-Heuristic and we calculate the total coverage degree of a frame. In this case, nodes will move towards the zone with smaller coverage. In practice, let us consider the field as shown in Fig. 2 and focus on the gray node ac inside the blue square, with the Basic-Heuristic we only take into account the external frame and we make the difference between each couple. This difference gives us the axis along which the current node has to move, whereas the direction will be determined by considering the smallest value of the weights. In our extended version, we also take into account the contribution of the weights of the interior frame by applying the same concept of the Basic-Heuristic. The largest difference between the opposite borders will determine the axis and direction of movement.

In Fig. 7 we show the coverage situation with the presence of ZoI placed at location [START_REF] Bokareva | Wireless sensor networks for battlefield surveillance[END_REF][START_REF] Bokareva | Wireless sensor networks for battlefield surveillance[END_REF] and [START_REF] Maleki | A new Approach for Area Coverage Problem in Wireless Sensor Networks with Hybrid Particle Swarm Optimization and Differential Evolution Algorithms[END_REF][START_REF] Maleki | A new Approach for Area Coverage Problem in Wireless Sensor Networks with Hybrid Particle Swarm Optimization and Differential Evolution Algorithms[END_REF] of the sensor field. The figure shows the results before running the heuristic (a) and after the heuristic completed its work (b). We can observe that the effect of the heuristic is to produce a more uniform distribution of nodes in the field but also an increased coverage for the specific ZoIs. A more quantitative evaluation will be presented in an extended version of the paper.

Fig. 1 :

 1 Fig. 1: Lee spheres of radius 1 (a) and 2 (b).

Fig. 2 :

 2 Fig. 2: Coverage grid example, the blue cells indicate the presence of a sensor in the cell. The letters call a cell, the number represents their coverage degree. The dash grey cells represent the Lee sphere of node in cell ac. North and South-East borders are highlighted in black.

1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 :

 12345678 Get current position (GPS or any other localization system) (x, y); 2: Every HelloFrequency seconds; Broadcast an HELLO message m with id, (x, y); 3: Upon reception of an HELLO message, update coverage map; Part II -Coverage Degree Computation: 1: Cn = x+r j=x-r map(y + r, j); Ce = y+r i=y-r map(i, x + r); Cs = x+r j=x-r map(y -r, j); Cw = y+r i=y-r map(i, x -r); Cne = x+r j=x map(y + r, j) + y i=y+r map(i, x + r); Cse = x+r j=x map(y -r, j) + y i=y-r map(i, x + r); Csw = x j=x-r map(y -r, j) + y i=y-r map(i, x -r); Cnw = x j=x-r map(y + r, j) + y+r i=y map(i, x -r); Part III -Direction Computation: 1: S N = (Cn -Cs) * (Cn -Cs); 2: E W = (Cw -Ce) * (Cw -Ce); 3: N E SW = (Csw -Cne) * (Csw -Cne); 4: N W SE = (Cse -Cnw) * (Cse -Cnw); 5: DIR = max(S N, E W, N E SW, N W SE) 6: in case of tie choose a random direction between winners Part IV -Movement:

Fig. 4 :

 4 Fig. 4: Percentage of coverage when the grid size is 10 × 10 (a) 15 × 15 (b) and 25 × 25 (c).

Fig. 5 :

 5 Fig. 5: Percentage of coverage when the grid size is 10 × 10 (a) 15 × 15 (b) and 25 × 25 (c) and obstacles are considered.

  k , ∀( ĩ, j) and ( ī , j ) ∈ ZOI, ( ĩ , j ) = ( ī , j )HEURISTIC EXTENSION FOR ZONE OF INTEREST

Fig. 6 :

 6 Fig. 6: An interesting zone (point) in the sensor field. The different degrees of gray correspond to different degrees of interest.

Fig. 7 :

 7 Fig. 7: Coverage before (a) and after (b) the heuristic.

•

  Local variables: current position of node (x, y); coverage radius r; coverage degree East Ce; West Cw; North Cn; South Cs; North-East Cne; North-West Cnw; South-East Cse; South-West Csw;

	Part I -Local Coverage Map Construction:

TABLE I :

 I Simulation Parameters

	Searching Space	10×10, 15×15, 25×25 cells
	# nodes	26, 38, 120
	Coverage radius (r)	2 m
	Transmission radius	(2 × r) m
	Cell size	1x1 m 2
	Obstacle Avoidance Factor (Heuristic)	0
	Attractive Force (VFA)	0.01
	Repulsive Force (VFA)	1000
	Threshold Distance (VFA)	(2 × r) m
	Forces Exclusion Threshold (VFA)	4 × r m
	# Generations (GA)	2000
	Population Size (GA)	500
	Crossover Fraction (GA)	0.8
	Mutation Factor (GA)	1
	Confidence Interval	95 %

ACKNOWLEDGMENT This work has been carried out in the framework of the Labex MS2T, which is funded by the French Government, through the program Investments for the future, managed by the National Agency for Research (Reference ANR-11-IDEX-0004-02).