Leila Ben Saad
email: leila.ben.saad@ens-lyon.fr

Bernard Tourancheau
email: bernard.tourancheau@ens-lyon.fr

Multiple Mobile Sinks Positioning in Wireless Sensor Networks for Buildings

Keywords: Wireless Sensor Networks, Sinks positioning, Mobile sinks, Network lifetime, Integer Linear Programming

Real deployment of wireless sensor networks inside buildings is a very challenging. In fact, in such networks, a large number of small sensor devices suffer from limited energy supply. These sensors have to observe and monitor their in-door environment, and then to report the data collected to a nearest information collector, referred to as the sink node. Sensor nodes which are far away from the sink relay their data via multiple hops to reach the sink. This way of communication makes the sensors near the sink deplete their energy much faster than distant nodes because they carry heavier traffic. So what is known as a hole appears around the sink and prevents distant nodes to send their data. Consequently the network lifetime ends prematurely. One efficient solution for this problem is to relocate sinks. In this work, we aim to find the best way to relocate sinks by determining their optimal locations and the duration of their sojourn time. So, we propose an Integer Linear Programming for multiple mobile sinks which directly maximizes the network lifetime instead of minimizing the energy consumption or maximizing the residual energy, which is what was done in previous solutions. Simulations results show that with our solution, the network lifetime is extended and the energy depletion is more balanced among the nodes. We also show that relocating mobile sinks inside a whole network is more efficient than relocating mobile sinks inside different clusters and we can achieve almost 52 % network lifetime improvement in our experiments.

Introduction

The need for Wireless Sensor Networks (WSNs) is rapidly growing in a wide range of applications specially for buildings automation. Such networks are composed of inexpensive and small nodes with sensing, data processing and communication capabilities. These sensors have a short operational life because they are equipped with limited batteries supplied energies which are usually impractical and even impossible to replace or recharge. These sensors are densely deployed in a region of interest and collaborate to forward the data collected towards a nearest information collector, referred to as the sink node. The sensor nodes which are far away from the sink use a multi-hop connections. This way of communication makes the sensors near the sink deplete their energy much faster than distant nodes because they carry heavier traffic. So what is known as a hole appears around the sink and prevents distant nodes to send their data. Consequently, the network lifetime ends prematurely. One efficient solution for this problem is to relocate sinks in order to guarantee balanced energy consumption among nodes. In this work, our purpose is to determine where to place multiple sinks inside buildings, how long they have to stay in certain locations and where to move them to extend the network lifetime. To answer these questions, we propose an Integer Linear Programming (ILP) for multiple mobile sinks whose objective function directly maximizes the network lifetime instead of minimizing the energy consumption or maximizing the residual energy, which is what was done in previous solutions. The contribution of our work concerns not only the definition of an ILP which determines the optimal locations of multiple mobile sinks but also show that relocating mobile sinks inside a whole network is more efficient than relocating mobile sinks inside different clusters. Simulation results show that with our proposed solution, the network lifetime is extended and the energy consumption is more balanced among the nodes. Moreover, the lifetime improvement that can be achieved when relocating sinks in the entire network is almost 52 % in our experiments. Such results can provide useful guidelines for real sensor network deployment.

The paper is organized as follow. In Section 2, we review the previously proposed solutions for the WSNs lifetime extension. Section 3 describes the system model. Section 4 presents the formulation of our proposed ILP for multiple mobile sinks. Section 5 shows the experimental results. Section 6 concludes the paper.

Related Work

In order to solve the problem of energy hole, many researchers look for approaches that help to extend the network lifetime. Some solutions propose to place more sensors nodes around the sink [START_REF] Wang | On lifetime-oriented device provisioning in heterogeneous wireless sensor networks: approaches and challenges[END_REF], [START_REF] Wu | On the energy hole problem of nonuniform node distribution in wireless sensor networks[END_REF]. However, these solutions are not always feasible in practice and result in unbalanced sensing coverage over different regions of the network. Another proposed solution is to deploy multiple static sinks in order to distribute load among the nodes [START_REF] Kim | Optimal multi-sink positioning and energy-efficient routing in wireless sensor networks[END_REF], [START_REF] Oyman | Multiple sink network design problem in large scale wireless sensor networks[END_REF]. But, it has been proved in [START_REF] Luo | Joint mobility and routing for lifetime elongation in wireless sensor networks[END_REF] that using a mobile sink is more efficient than a static one and thus helps to increase the network lifetime. Most of published works treat the problem of relocating a single sink [START_REF] Luo | Joint mobility and routing for lifetime elongation in wireless sensor networks[END_REF], [START_REF] Akkaya | Sink repositioning for enhanced performance in wireless sensor networks[END_REF], [START_REF] Wang | Employing mobile sink in event-driven wireless sensor networks[END_REF], [START_REF] Wang | Exploiting sink mobility for maximizing sensor networks lifetime[END_REF]. But, very few research focused on relocating multiple sinks. In [START_REF] Wang | Employing mobile sink in event-driven wireless sensor networks[END_REF], the solution of repositioning a single sink is extended to a network including several sinks by organizing it into several clusters. In [START_REF] Friedmann | Efficient multi-sink relocation in wireless sensor network[END_REF], the authors propose a multi-sinks movement approach based on a local search algorithm. Some research efforts have focused on approaches that maximize the residual energy as in [START_REF] Alsalih | Placement of multiple mobile base stations in wireless sensor networks[END_REF], [START_REF] Azad | Mobile base stations placement and energy aware routing in wireless sensor networks[END_REF], or minimize the average distances between sensors and closest sinks as in [START_REF] Vincze | Deploying multiple sinks in multi-hop wireless sensor networks[END_REF], to determine the optimal locations of mobile sinks. The first work that addressed the problem of positioning multiple mobile sinks is presented in [START_REF] Gandham | Energy efficient schemes for wireless sensor networks with multiple mobile base stations[END_REF]. The authors propose an ILP which determines the optimal locations of mobile sinks by minimizing the energy consumed at each node. In our work, a different formulation of the problem is proposed, where the ILP proposed directly maximizes the network lifetime instead of minimizing the energy consumption or maximizing the residual energy. To us, this is closer to the need of sensors deployment in building monitoring.

System Model

In order to deploy sensors and sinks inside buildings, we made the following assumptions for the system model. All sensors are stationary and located in a grid of same size cells constructed from the building plan as shown in Figure 1. They all have a limited initial energy supply and a fixed transmission range equal to the distance between two nodes. Each sensor generates regularly the same amount of data. The sinks whose number is fixed and known a priori, can be located only in feasible sites where they get power and internet. They keep moving in the grid from feasible site to another one until the first sensor dies. The sinks should stay at a feasible site for at least a certain duration of time. At the end of this duration, they may stay or change of location. The traveling time of sinks between feasible sites is considered negligible for analytical simplicity.

Network Model

Routing and Path Selection

The sensor nodes which aren't co-located with any sinks inside the grid, relay their generated data via multiple hops to reach the nearest sink. The sinks can be located only in feasible sites where they get power and network. They keep moving in the grid from feasible site to another one until the first sensor dies. When a sensor node is located in the same horizontal or vertical line of the nearest sink position, there is only one shortest path between the two nodes. Otherwise, there are multiple shortest paths. In our routing protocol like in [START_REF] Wang | Exploiting sink mobility for maximizing sensor networks lifetime[END_REF], we route "per dimension". We consider only the two paths along the perimeter of the rectangle, i.e., paths 1 and 2 in Figure 2. These two routes are considered equivalent.

Power Consumption

To calculate the power consumption, we consider the same realistic model as in [START_REF] Wang | Exploiting sink mobility for maximizing sensor networks lifetime[END_REF]. Therefore, the power expended to transmit a L 1 -bit/s packet to a distance d is:

P T x = L 1 γ 1 + L 1 γ 2 d β (1)
where γ 1 is the energy consumption factor indicating the power consumed per bit by the sensor to activate transceiver circuitry, γ 2 is the energy consumption factor indicating the power consumed per bit by the transmit amplifier to achieve an acceptable energy per bit over noise spectral density and β is the path loss exponent. The power expended to receive L 2 -bit/s in the same radio model is:

P Rx = L 2 α ( 2
)
where α is the energy consumption factor indicating the power consumed per bit at receiver circuit. Thus, the total energy consumed at a sensor node per time unit is:

P total = P T x + P R x = L 1 (γ 1 + γ 2 d β ) + L 2 α (3)

Integer Linear Programming Formulation

The WSN is represented by the graph G(V, E), where V = S ∪ F and E ⊆ V × V . S represents the set of sensors nodes, F represents the set of feasible sites and E represents the set of wireless links. We distinguish two scenarios with mobile sinks. The first one is when there are multiple sinks moving in the entire network. The second one is when there are multiple sinks moving separately inside different clusters.

Mobile sinks moving in the entire network

The parameters and variables used to describe the problem are the following:

• Parameters -m is the number of sinks.

-T (s) is the minimum duration of common time units for which the sink should stay at a certain feasible site. -e 0 (J) is the initial energy of each sensor.

-e (J/bit) is the energy consumption coefficient for transmitting or receiving one bit. -r (bit/s) is the rate at which data packets are generated. -f k ij (bit/s) is the data transmission rate from node i to node j where the nearest sink stays at node k.

-N k i is the set of i's neighbors whose their nearest sink is at node k.

-p k 1 k 2 ..k m i (J/s) is the power consumed in sending and receiving data by sensor node i when the first sink is located at node k 1 , the second sink is located at node k 2 etc. and the m-th sink is located at node k m . -p k i (J/s) is the power consumed in sending and receiving data by senor node i when the nearest sink is located at node k, k ∈ F .

• Variables -Z (s) is the network lifetime.

-

l k 1 k 2 .
.km is an integer variable which represents the number of times when the first sink is located at node k 1 , the second sink is located at node k 2 etc. and the m-th sink is located at node k m for a duration of time T .

k 1 ∈ F , k 2 ∈ F and k m ∈ F . max Z = k 1 ∈F k 2 ∈F .. k m ∈F T l k 1 k 2 ..k m (4) k 1 ∈F k 2 ∈F
..

k m ∈F T l k 1 k 2 ..k m p k 1 k 2 ..km i ≤ e 0 , i ∈ S (5) l k 1 k 2 ..k m ≥ 0, k 1 ∈ F, k 2 ∈ F, .., k m ∈ F (6)
The equation ( 4) maximizes the network lifetime and determines the sojourn times of all sinks at feasible sites. The equation [START_REF] Luo | Joint mobility and routing for lifetime elongation in wireless sensor networks[END_REF] assures that the energy consumed in receiving and transmitting data by each sensor node doesn't exceed its initial energy. This energy is computed when the first sink is located at node k 1 , the second sink is located at node k 2 etc. and the m-th sink is located at node k m .

The power p k 1 k 2 ..k m i is computed as following:

p k 1 k 2 ..k m i = p k i ( 7
)
where k=N earestSink(k 1 , k 2 , .., k m , i), N earestSink is a function which returns the nearest sink node to sensor node i. This sink node is determined by choosing the shortest path as presented in Section 3.2.

In the real world, the energy spent for receiving data exceeds the energy spent for transmitting data. In our model as in [START_REF] Wang | Exploiting sink mobility for maximizing sensor networks lifetime[END_REF], we assume that the energy consumed when transmitting a bit is constant and equal to energy consumed when receiving a bit, here denoted by e (J/bit) i.e., γ 1 + γ 2 d β ≈ α =e. Thus, we obtain:

P total = e(L 1 + L 2 ) (8)
So, in our model the p k i is calculated as following [START_REF] Wang | Exploiting sink mobility for maximizing sensor networks lifetime[END_REF]:

p k i = e( j∈N k i f k ij + j:i∈N k j f k ji ), i ∈ S, k ∈ F and i = k (9) p k i = er, i ∈ S, k ∈ F and i = k ( 10
)
At each node, the total of outgoing packets is equal to the total incoming packets plus the data packets generated:

j:i∈N k j f k ji + r = j∈N k i f k ij , i ∈ S, k ∈ F ( 11
)
Using the two equations ( 9) and ( 11), we obtain:

p k i = e(2 j:i∈N k j f k ji + r), i ∈ S, k ∈ F and i = k (12)

Mobile sinks moving separately in clusters

In this section, we formulate an ILP for a network divided in different clusters. The movement of the sinks is restricted to their cluster.

The variables and parameters that differ from section 4.1: -Z j (s) is the network lifetime of the cluster j, j ∈ {1, 2, .., m} -l k is an integer variable which represents the number of times when the sink is located at node k, k ∈ F j for a duration of time T .

-p k i (J/s) is the power consumed in sending and receiving data by senor node i when the sink is located at node k, k ∈ F j . -F j is the set of feasible sites of cluster j, j ∈ {1, 2, .., m} and F = ∪ F j . -S j is the set of sensor nodes of cluster j, j ∈ {1, 2, .., m} and S = ∪ S j . For each cluster j, j ∈ {1, 2, ..m}

max Z j = k∈F j T l k (13) k∈Fj T l k p k i ≤ e 0 , i ∈ S j ( 14
)
l k ≥ 0, k ∈ F j ( 15
)
The lifetime of network which is the time until the first sensor dies is determined by the following equation.

Z = min j (Z j ) (16)

Simulation and Results

We simulated a sensor network of 50 nodes distributed in a 5x10 grid. We considered 3 sinks moving in 25 chosen feasible sites. We also simulated the same network with the same number of nodes and feasible sites but divided in 3 predefined clusters (5x3), (5x3) and (5x4) in which 3 sinks move separately as shown in the Figure 3. Each node in the grid is localized with its coordinates (x,y) where x is the column position and y is the row position. The results show that the network lifetime improvement is 31 % when the sinks move in the entire network. In order to determine the network lifetime and the optimal location of sinks, we solved the proposed ILP with GLPK solver version 4.34 [START_REF]GLPK[END_REF]. The calculation of the power consumed by senor node when the nearest sink is located at certain node (p k i ) was made by a program written in Java. The values of parameter variables were chosen according to the following realistic assumptions. The initial energy at each node was chosen equal to energy found in two Alkaline batteries AA of 1.5V and 2600mAh i.e., e o = 28080 J. We also chose the energy consumption coefficient for transmitting and receiving one bit the same as vendor-specified values for the Chipcon CC2420 [START_REF] Chipcon | [END_REF] where E T x = 0.225 10 -6 J/bit and E Rx = 0.2625 10 -6 J/bit. We assume that e = E T x = E Rx = 0.2625 10 -6 J/bit. We fixed the minimum duration of sojourn time T of the sinks to 30 days (T = 2592000 s) because it is economically not easy for technicians to relocate sinks in buildings very often. The rate r at which data packets are generated is equal to 1 bit/s. Notice that real micro-controllers stop running when the battery voltage is below a threshold. This depends on the micro-controllers and can not be taken into account here.

To get deeper understanding of the efficiency of the sinks mobility in the entire network, we simulated sensor networks with different grid sizes and number of sinks. We investigated the network lifetime, the pattern of the distribution of the sinks sojourn times at the different nodes and the residual energy at each node. We assumed the same number of feasible sites as sensor nodes. We considered the three following cases in order to make a comparative study.

1) Stationary sinks.

2) Mobile sinks moving in different clusters 3) Mobile sinks moving in the entire network

To compute the network lifetime and the optimal locations of stationary sinks, we used the following equation [START_REF] Wang | Exploiting sink mobility for maximizing sensor networks lifetime[END_REF]:

Z = max k {min i ( e 0 p k i )}, k ∈ F, i ∈ S ( 17
)
where

k = N earestSink(k 1 , k 2 , .., k m , i), k 1 ∈ F, k 2 ∈ F, .., k m ∈ F.

Network lifetime

To study the network lifetime, we run our ILP with an increasing number of sensor nodes and sinks. Then, we compared the network lifetime for each of the cases above. the first sensor dies relatively quickly when the sinks are statics or moving in different clusters comparing to when the sinks are moving in the whole network. In the case of static sinks, the network lifetime is clearly shorter than mobile sinks because nodes around sinks have to spend more energy to relay packets for important number of nodes which leads them to drain their energy faster. The lifetime improvement ratios obtained in 6x6 grid by deploying 3 mobile sinks in the entire network are 52 % against 3 mobile sinks moving separately in different clusters and 102 % against 3 static sinks.

Figure 5 shows that when the network size is bigger the network lifetime is shorter for all of the cases. This is explained by the fact that there is more data traffic. Hence, sensors which are near the sinks must retransmit a higher number of packets from their higher number of neighbors which leads to faster energy depletion.

The Sinks Sojourn Times

We investigated the pattern of the distribution of the sinks sojourn times at the different nodes with different number of sinks. Without loss of generality, we considered 5x5 grid. Independently of the size of the network, we observe that for all the cases, the sinks sojourn most of times at the nodes which are at minimum distance i.e., number of hops to all other nodes.

The optimal sinks locations obtained for static sinks are the nodes with the coordinates (2,3) and (4,3) when there are 2 sinks in the network and the nodes with coordinates (3,2), (2,4) and (4,4) when there are 3 sinks in the network (see Figure 6). The grid 5x5 was divided in different predefined clusters in which the sinks move separately. The sojourn times of sinks at the different nodes of clusters are shown in Figure 7. We notice that each sink sojourns most of times at the central grid area and/or the corners of its cluster. For the case of sinks moving in the entire network, the sinks sojourn most of the times at the central grid area as shown in Figure 8. For the case of 2 sinks in the network, the two locations in which the sinks stay the most of times are the nodes with coordinates (4,2) and [START_REF] Wu | On the energy hole problem of nonuniform node distribution in wireless sensor networks[END_REF][START_REF] Oyman | Multiple sink network design problem in large scale wireless sensor networks[END_REF]. For the case of 3 sinks in the network, the three locations in which the sinks stay the most of times are the nodes with coordinates (2,2), (4,2) and (4,4).

Residual energy

We investigated the residual energy at each sensor node at the end of network lifetime for different number of sinks. Without loss of generality, we considered a 5x5 grid. We compared between the three different cases above. It is remarkable in the Figures 9, 10 and 11 that the energy consumption is highly variable and depends on the sinks locations for all the cases. The nodes which aren't along any routing path to reach the sink have relatively higher energies compared to most of the others, because they don't have as nodes closest to the sinks to receive and relay all other neighbors data in addition to their own data. This, leads them to consume less energy. The same remark is made In general, we observe that at the end of network lifetime the distribution of residual energy in the grid is more balanced and the energy is more consumed among the nodes when the number of sinks increases. With static sinks, the majority of sensors have more residual energy at the end of network lifetime than in the cases with mobile sinks which have their initial energies almost completely depleted at the same time. In fact, in 5x5 grid as shown in the Figures 9, 10 and 11, the rate of the energy remained unused at the network lifetime end is 50 % for 3 static sinks, 23 % for 3 mobile sinks in different clusters and 7 % for 3 mobile sinks in the entire network. Moreover, the numbers of sensors which have more than 50 % of their initial energy remained unused is 19 for the case of 3 static sinks, 10 with 3 mobile sinks moving separately in clusters and 0 for the case of mobile sinks moving in the whole network. For the case of sinks moving in the whole network, sensor nodes have their energy more consumed among the nodes than in the case of sinks moving in clusters. This is due to the fact that the mobility of sinks in the whole network changes the nodes acting as relays frequently and leads to balanced energy consumption among nodes. While, in the third case, the movement of the sinks is restricted to their own clusters. So, this approach prevents to have global view of the entire network.

These results are interesting since they aren't pure theory because we tried to approach realistic buildings deployment in our assumptions and especially with sinks that can't move frequently.

Conclusion

In this paper, we have explored the problem of positioning mobile sinks in wireless sensor networks inside buildings, to avoid the energy hole problem and to extend the network lifetime, which is really needed in practice. As a solution, we have proposed an ILP which directly maximizes the network lifetime instead of minimizing the energy consumption or maximizing the residual energy, which is what was done in previous solutions. The proposed ILP determines the best way to relocate sinks by giving their optimal locations and the duration of their sojourn time. A comparative study of the proposed solution with static sinks and mobile sinks moving separately in clusters was made. Relocating sinks with our solution and using realistic parameters assumptions results in the network lifetime extension and the energy consumption more balanced among the nodes. The lifetime improvements achieved in our experiments by deploying 3 mobile sinks in the entire network are almost 52 % against 3 mobile sinks moving separately in different clusters and almost 102 % against 3 static sinks. The study of the pattern of the distribution of the sinks at different locations showed that the sinks sojourn most of times at the nodes which are at minimum number of hops to all other nodes specially in the central grid area. This corresponds to very interesting feasible sites in buildings corridors.

In our future work, a real deployment of multiple sinks according to our proposed solution in a sensor network inside buildings is envisaged. We intend to study not only the lifetime, the pattern of the distribution of the sinks at different locations and the residual energy but also the performance of the network for this configuration such as latency, bandwidth and data delivery ratio.

Figure 1 .

 1 Figure 1. Grid of cells with sensors

Figure 2 .

 2 Figure 2. Path selection

  (a) The entire network (b) Network divided in clusters

Figure 3 .

 3 Figure 3. Each grid cell has a sensor. The feasible sites are colored. The 3 clusters (5x3), (5x3) and (5x4) are by space

Figure 4 .

 4 Figure 4. The network lifetime in 6x6 grid

Figure 5 .

 5 Figure 5. The network lifetime in different network grids

Figure 6 .

 6 Figure 6. Static sinks sojourn times at the different nodes

Figure 7 .

 7 Figure 7. Mobile sinks sojourn times at different clusters nodes. The clusters are separated double lines

Figure 8 .

 8 Figure 8. Mobile sinks sojourn times at the different nodes in the entire network

Figure 9 .Figure 10 .

 910 Figure 9. Residual Energy at the end of the network lifetime of 5x5 grid with static sinks

Figure 11 .

 11 Figure 11. Residual Energy at the end of the network lifetime of the 5x5 grid with mobile sinks


Stratégie de Placement des Puits Mobiles dans les Réseaux de Capteurs sans Fil pour Bâtiments

Leila Ben Saad, Bernard Tourancheau LIP UMR 5668 of CNRS-ENS Lyon-INRIA-UCB Lyon Lyon, France {Leila.Ben.Saad, Bernard.Tourancheau}@ens-lyon.fr Abstract-Le besoin des réseaux de capteurs sans fil croit très rapidement dans un large éventail d'applications industrielles. Parmi celles-ci se trouve l'observation, le suivi des données physiques et l'automatisation des bâtiments. Dans ces réseaux, un grand nombre de capteurs transmettent via multi sauts les données collectées vers le puits le plus proche. Les capteurs qui sont proches des puits épuisent leurs réserves d'énergie beaucoup plus rapidement que les capteurs distants car ils ont une charge de trafic très importante. Ceci est d û au fait qu'ils transmettent leurs propres données ainsi que les données des capteurs éloignés provoquant ainsi prématurément la fin de la durée de vie du réseau. Le déplacement périodique des puits permet de résoudre ce problème en distribuant la charge du trafic entre les capteurs et améliorer ainsi la durée de vie du réseau. Dans ce travail, nous proposons un nouvel algorithme qui détermine le positionnement de plusieurs puits mobiles dans un réseau large échelle afin d'augmenter la durée de vie du réseau. Son principe se base sur le déplacement régulier des puits vers les capteurs distants qui ont le plus grand nombre de sauts à faire pour atteindre le puits le plus proche. Nous avons évalué les performances de notre solution par des simulations et comparé avec d'autres stratégies. Les résultats montrent que notre solution améliore considérablement la durée de vie du réseau et équilibre notablement la consommation d'énergie entre les noeuds. Ces résultats sont très utiles pour le déploiement réel de réseaux de capteurs sans fil au sein des bâtiments.

Index Terms-Réseaux de capteurs sans fil, positionnement des puits, puits mobiles, durée de vie du réseau.

I. INTRODUCTION

Wireless Sensor Networks (WSNs) deployment inside buildings is a very challenging problem. In fact, such networks are formed by a large number of tiny battery-operated sensors which have a limited and non-renewable energy supply because it is usually impractical and even impossible to replace or recharge their batteries. The sensors near the sink are more likely to use up their energy much faster than distant nodes because they carry heavier workloads due to forwarding the data of nodes farther away as well as their own data. Therefore, they become hotspots. The hotspot problem prevents farther nodes to relay their data to the sinks. Consequently, the network lifetime ends prematurely.

More and more efforts have been done recently to improve the lifetime of WSNs. Many communications protocols have been proposed including among others topology control [START_REF] Pan | Topology control for wireless sensor networks[END_REF][2], routing [3][4] and clustering [START_REF] Younis | Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach[END_REF] etc. However, further improvement can be achieved if we relocate the sinks in order to change over time the nodes located close to them.

In order to solve the hotspot problem, many researchers propose to place more sensor nodes around the sink [START_REF] Wu | On the energy hole problem of nonuniform node distribution in wireless sensor networks[END_REF] [START_REF]Avoiding energy holes in wireless sensor networks with nonuniform node distribution[END_REF]. However, these solutions are not always feasible in practice and result in unbalanced sensing coverage over different regions of the network. Another proposed solution is to make multiple fixed sinks cooperate with each other to lighten the load and distribute it among the nodes [8][9].

Most of published works suggest to move a single sink to improve the network lifetime [10][11][12][13] [START_REF] Bi | Moving schemes for mobile sinks in wireless sensor networks[END_REF]. But, very few studies focused on the mobility of multiple sinks. Some proposed algorithms find the locations of mobile sinks by solving a mathematical model [START_REF] Vincze | Deploying multiple sinks in multi-hop wireless sensor networks[END_REF] [START_REF] Azad | Mobile base stations placement and energy aware routing in wireless sensor networks[END_REF]. In [START_REF] Vincze | Deploying multiple sinks in multi-hop wireless sensor networks[END_REF], the algorithm minimizes the average distances between sensors and closest sinks. In [START_REF] Azad | Mobile base stations placement and energy aware routing in wireless sensor networks[END_REF], the algorithm selects the locations of sinks in the periphery of the network in such way the difference between the maximum and the minimum residual energy of nodes is minimized. To find the optimal placement of mobile sinks, some researches formulate the problem as an Integer Linear Program ILP [START_REF] Gandham | Energy efficient schemes for wireless sensor networks with multiple mobile base stations[END_REF][18] [START_REF] Saad | Multiple mobile sinks positioning in wireless sensor networks for buildings[END_REF] or Linear Program LP [START_REF] Basagni | Moving multiple sinks through wireless sensor networks for lifetime maximization[END_REF]. However, the drawback of the LP and ILP based solutions is that they are hard to compute in networks with thousands of sensors due to their high resolution complexity.

Some other works make a moving decision according to the complete knowledge of the energy distribution of the sensors. In [START_REF] Marta | Improved sensor network lifetime with multiple mobile sinks[END_REF], the sinks move towards the nodes that have the highest residual energy. But, this strategy requires that the sensors send periodically to the sink additional information about their energy level to allow the sink to found out the nodes which have the highest energy. By doing so, a lot of energy will be wasted.

In this work, our purpose is to determine where to place multiple sinks inside buildings, how long they have to stay in certain locations and where to move them to extend the network lifetime. To answer these questions, we propose a new scalable multi-sink heuristic algorithm (Hop) which regularly moves the sinks towards the distant nodes which have lower load contrary to nodes near the sinks. This approach scales to thousands of nodes and prevents from sending additional information about the energy level of each sensor which is what was done in previous solutions. Simulation results demonstrate that by relocating the mobile sinks according to our proposed algorithm, the energy consumption is balanced among the sensors which lead to significant increase of the network lifetime.

The rest of this paper is organized as follows. In Section 2, we describe the network model including the major assumptions. Section 3 presents our proposed multi-sink heuristic algorithm. Section 4 evaluates the performance of the proposed approach and presents the simulation results. Section 5 concludes the paper.

II. NETWORK MODEL

In order to deploy sensors and sinks inside buildings, we made the following assumptions for the network model.

-We assume N sensors statically placed in a bidimensional grid (LxL) of same size cells constructed from the building plan as shown in the Figure 1. The purpose of the multi-sink heuristic algorithm is to find the best way to move the sinks in order to improve the lifetime of large scale sensor networks. Our approach is based on number of hops and consists in relocating periodically the sinks towards the distant nodes. The difference between our strategy and what was already proposed is that there is no need for the sensors to drain their energy in sending additional information about their energy level. Each sink knows its own position, others sinks positions and the locations of all the sensors. Therefore, from the number of hops to reach the nearest sink, it is possible to guess which sensors are distant and may have more residual energy.

The algorithm begins with an initialization phase where the sinks are placed at their optimal locations in terms of hop counts. Then, for each sensor, the number of hops to reach the nearest sink is computed. Next, the nodes are sorted with decreasing number of hops in order to determine the distant nodes from the sinks. Afterwards, the first sink will be relocated at the farthest node. The second sink will be relocated at the following distant node but respecting the condition that the number of hops between the two new locations must be upper than minimum number of hops min hop . The third sink is relocated with the same manner in such way the distance between the three new positions of sinks is upper than min hop . The remaining sinks are relocated with the same way. All the chosen positions of sinks at each period are saved in a list. In the case that the selected positions of sinks where already chosen in previous periods, the algorithm chooses as the first sink location a node which has not been chosen before and determines the locations of the other sinks. If all sensor nodes where already visited by the sinks, the chosen list is emptied. The same operations are repeated at the beginning of each new period T.

The pseudocode of the algorithm is shown in the Figure 3.

The algorithm is implemented in a distributed manner. In the sense that it does not determine the sinks locations based on the knowledge of the global network parameters. But, each sink has to know only the initial starting locations of sensors and sinks. Throughout the network lifetime, each sink is able to compute autonomously its next position and move there.

To have a better idea about the algorithm, an example of a network with 100 sensors and 3 mobile sinks is provided. The sinks locations pattern obtained by the execution of our Multi-Sink Heuristic Algorithm (Hop) 1: place the M sinks at optimal starting locations in LxL grid 2: add starting locations of the sinks to chosen list 3:

min hop = L -1, M = 2 [2(L -1)/(M -

IV. SIMULATION RESULTS

To analyze the performances of our proposed algorithm, we built a simulator in Java environment with variable number of sensors and sinks deployed on different grid sizes.

To compute the energy consumption, we used the same model described in [START_REF] Saad | Multiple mobile sinks positioning in wireless sensor networks for buildings[END_REF]. We chose realistic parameter assumptions for the network. The initial energy at each node is equal to energy found in two Alkaline batteries AA of 1.5V usually 2600mAh i.e., e o = 28080 J. The energy consumption coefficient for transmitting and receiving one bit was chosen the same as vendor-specified values for the Chipcon CC2420 [START_REF] Chipcon | [END_REF] where e T = 0.225 10 -6 J/bit and e R = 0.2625 10 -6 J/bit. We fixed the minimum duration of sojourn time T of the sinks to 30 days because it is economically not easy for technicians to relocate sinks in buildings very often. The sensor transmission range is r = 10 m. The rate at which data packets are generated is g r = 1 bit/s. Notice that real micro-controllers stop running when the battery voltage is below a given threshold. This depends on the micro-controllers and can not be taken into account here.

To show the efficiency of our proposed scheme, we evaluated its performance by making a comparative study with four other schemes.

Thus, the following schemes were implemented : 1) Static: Static sinks placed in optimal locations [START_REF] Saad | Multiple mobile sinks positioning in wireless sensor networks for buildings[END_REF] 2) Periphery: Sinks moving in the periphery of the network 3) Random: Sinks moving randomly 4) Hop: Sinks moving according to our algorithm 5) Opt: Sinks moving according to ILP solution [START_REF] Saad | Multiple mobile sinks positioning in wireless sensor networks for buildings[END_REF] In the following sections, the network lifetime, the energy consumption and the residual energy at each sensor are investigated.

A. The network lifetime

We evaluated the network lifetime of the five schemes on networks of 100 sensors with increasing number of mobile sinks. Figure 5 shows that the Opt scheme performs better than the others schemes because it selects the optimal locations of Fig. 6. Network lifetime with increasing number of sinks sinks and their optimal sojourn times. But, the problem with Opt is that it is based on Integer Linear Program which can handle only small scale networks. All the remaining schemes are scalable but the Hop scheme is the best of them because it achieves longer lifetime. The lifetime improvements achieved by Hop in 10x10 grid network with 3 mobile sinks are almost 38 % against Random, 64 % against Periphery and almost 170 % against Static. The gap between Hop and Opt in network lifetime is about 18 %.

We investigated the network lifetime of Static, Random, Periphery and Hop schemes in a large scale network with 2500 sensors on 50x50 grid. We varied the number of sinks from 2 to 10.

Figure 6 shows that all schemes improve the network lifetime when the number of sinks increases. Because, using more sinks reduces the average path length between the sensors and sinks and enables to achieve less traffic load to the nodes which extends the network lifetime. Nevertheless, the Hop scheme leads to longer network lifetime than all other schemes. In a network with 2500 sensors and 10 sinks, Hop achieves 29 % of lifetime improvement than when 10 sinks are moving randomly, 42 % than when 10 sinks are moving on the periphery, and 1014 % than when 10 sinks are static. We studied the network lifetime with different sinks sojourn times (see Figure 7). The number of sinks was fixed to 10 and the number of sensors 2500. The results indicate that when the the sinks sojourn time increases the network lifetime decreases slowly. In fact, the longer the sojourn time is, the less the sinks movements are which lead to shorter lifetime.

We varied the network size from 10x10 to 50x50 sensors. The number of sinks was fixed to 10 and the sojourn time T to 30 days. We noticed as shown in the Figure 8 that the network lifetime decreases considerably when the network size increases. In fact, the sensors near the sinks must retransmit a higher number of packets from their higher number of neighbors which leads to higher energy consumption.

B. The energy distribution

We analyzed the impact of the five schemes on the energy consumption at lifetime end in a network with 3 mobile sinks and 100 sensors. The distribution of energy consumption when the first sensor dies is depicted in Figures 9,[START_REF] Wang | Employing mobile sink in event-driven wireless sensor networks[END_REF][START_REF] Wang | Exploiting sink mobility for maximizing sensor networks lifetime[END_REF]12 and 13. A light color means a higher percentage of energy consumption.

It is remarkable in all the figures that the energy consumption is highly variable and depends on the sinks locations. We notice that the nodes closest the sinks locations have relatively higher energy consumption compared to most of the others because they have to receive and relay all other neighbors data in addition to their own data. This leads them to consume more energy. In Figure 9, we observe that higher percentage of energy consumption is concentrated around three nodes in the grid which are the locations of the sinks whereas the others sensors have a lower amount of energy consumption (dark color).

When the sinks move on the periphery of the network the highest energy consumption occurs in nodes closest to the boundary of the network while the others nodes specially in the center consume less energy as seen in the Figure 10. Opt scheme balances almost perfectly the energy consumption among the nodes. In fact, the majority of the nodes deplete their energy at the same time except the four nodes in the corners as shown in the Figure 13. However, this scheme is restricted only to small scale networks.

The distribution of the residual energy at each sensor node in 10x10 grid with 3 mobile sinks was also studied (see Figures 14,[START_REF] Vincze | Deploying multiple sinks in multi-hop wireless sensor networks[END_REF][START_REF] Azad | Mobile base stations placement and energy aware routing in wireless sensor networks[END_REF]17 and 18).

The results show that the percentages of the residual energy that remained unused at the network lifetime end are 71 %, The two schemes Opt and Hop result in a better distribution of residual energy compared to Periphery, Random and Static. Nevertheless, Opt can be efficient only for small networks contrary of Hop which can scale to thousands of sensors.

We analyzed the impact of the scalable schemes Static, Periphery, Random and Hop on the energy consumption at lifetime end in a large scale network with 4 mobile sinks and 2500 sensors. The results are similar to what was found in small network with 100 sensors. Hop balances better the energy consumption among the nodes than the other schemes because it leads to a higher number of sensors with very small amount of energy left unused (see the Figure 19). V. CONCLUSION In this paper, we have proposed an efficient solution to extend the lifetime of large scale WSNs. The proposed heuristic algorithm regularly moves the sinks towards the distant nodes. This approach, based on number of hops, prevents from sending additional information about the energy level of each sensor. We evaluated the performance of our algorithm by simulation in a network with thousands of sensors and compared it with others schemes: Static, Periphery, Random and Opt. The results show that it extends significantly the lifetime of the network and balances notably the energy consumption among the nodes. Our solution is very simple and useful for wireless sensor network deployment inside buildings because it is scalable and achieves 1014 % lifetime improvement when we deploy 10 mobile sinks instead of 10 static ones in a network with 2500 sensors.

In our future work, we intend to study the management of multiple sinks moving according to our proposed solution in a 6lowpan-based wireless sensor networks for buildings. We would like to focus on how IPv6 mechanisms could support efficiently sinks periodic mobility.

Fig. 1 .

 1 Fig. 1. 10x10 grid of cells with sensors in office building (L=10) -All sensors have a limited initial energy e 0 (J) and a fixed transmission range r (m) equal to the distance between two nodes (i.e, cell size). -A time-driven application is considered where each sensor regularly generates the same amount of data g r (bit/s). -M sinks keep moving in the grid from one node to another one until the network lifetime end. -The network lifetime is defined as the time until the first sensor dies (i.e, it uses up its residual energy). -The sinks should stay at a certain location for at least a duration of time T (sojourn time). At the end of this duration, they can change their locations. -The traveling time of sinks between sensor nodes is considered negligible for analytical simplicity. -The sensor nodes which are not co-located with any sinks inside the grid, relay their generated data via multiple hops to reach the nearest sink using the shortest path routing protocol. -In our routing protocol, we consider only the two paths along the perimeter of the rectangle, i.e., paths 1 and 2 in Figure 2. These two routes are considered equivalent. -An ideal MAC layer with no collisions and retransmissions is assumed. -Only the energy consumption for communication is considered. Let e T (J/bit) be the energy consumption coefficient for transmitting one bit and e R (J/bit) be the energy consumption coefficient for receiving one bit.

Fig. 2 .

 2 Fig. 2. Path selection

Fig. 3 .Fig. 4 .

 34 Fig. 3. Hop algorithm

Fig. 5 .

 5 Fig. 5. Network lifetime with 100 sensors (10x10 grid)

Fig. 7 .

 7 Fig. 7. Network lifetime with different sinks sojourn times

Fig. 8 .

 8 Fig. 8. Network lifetime with increasing network size

Fig. 9 .

 9 Fig. 9. Energy consumption with Static scheme

Fig. 11 .

 11 Fig. 11. Energy consumption with Random scheme Figure 11 shows that the energy consumption of Random scheme is more balanced among the nodes than Periphery and Static schemes.

Fig. 12 .

 12 Fig. 12. Energy consumption with Hop scheme Figure 12 shows that Hop scheme results in a better balancing of energy consumption than Periphery, Static and Random schemes. In fact, we notice a larger area with light color.

Fig. 13 .

 13 Fig. 13. Energy consumption with Opt scheme

Fig. 14 .

 14 Fig. 14. Residual energy with Static scheme

Fig. 19 .

 19 Fig. 19. Energy consumption in 50x50 grid network

  1)], M >= 3 4: while new period T do 5: for i = 1 to N do 6: nearest K = nearest sink for sensor node i 7: n hop = number of hops between node i and nearest K 8: add (node i , n hop ) to node list 9: end for 10: sort nodes of node list in decreasing order of n hop 11: p 1 = select first node of node list in the sorted order 12: add p 1 to select list 13: for i = 2 to M do 14: p i = select next node from node list having minimum number of hops with nodes in select list >= min hop 15: add p i to select list 16: end for 17: if nodes from select list not in chosen list then 18: add nodes from select list to chosen

list 19: else 20: empty select list 21: p 1 = select not chosen node from node list 22: go to line 12 23: end if 24: if chosen list contains all nodes then 25: empty chosen list 26: end if 27: for i = 1 to M do 28: move sink i to node p i from select list 29: end for 30: end while


Alejandro Arbelaez
email: alejandro.arbelaez@inria.fr

Youssef Hamadi
email: youssefh@microsoft.com

Improving Parallel Local Search for SAT

Keywords: local search, SAT solving, parallelism

In this work, our objective is to study the impact of knowledge sharing on the performance of portfolio-based parallel local search algorithms. Our work is motivated by the demonstrated importance of clause-sharing in the performance of complete parallel SAT solvers. Unlike complete solvers, state-of-the-art local search algorithms for SAT are not able to generate redundant clauses during their execution. In our settings, each member of the portfolio shares its best configuration (i.e., one which minimizes conflicting clauses) in a common structure. At each restart point, instead of classically generating a random configuration to start with, each algorithm aggregates the shared knowledge to carefully craft a new starting point. We present several aggregation strategies and evaluate them on a large set of problems.

Introduction

Complete parallel solvers for the propositional satisfiability problem have received significant attention recently. These solvers can be divided into two main categories the classical divide-and-conquer model and the portfolio-based approach. The first one, typically divides the search space into several sub-spaces while the second one lets algorithms compete on the original formula [START_REF] Hamadi | ManySAT: A Parallel SAT Solver[END_REF]. Both take advantage of the modern SAT solving architecture [START_REF] Moskewicz | Chaff: Engineering an Efficient SAT Solver[END_REF], to exchange the conflict-clauses generated in the system and improve the overall performance.

This push towards parallelism in complete SAT solvers has been motivated by their practical applicability. Indeed, many domains, from software verification to computational biology and automated planning rely on their performance. On the contrary, since local search techniques only outperform complete ones on random SAT instances, their parallelizing has not received much attention so far. The main contribution on the parallelization of local search algorithms for SAT solving basically executes a portfolio of independent algorithms which compete without any communication between them. In our settings, each member of the portfolio shares its best configuration (i.e., one which minimizes the number of conflicting clauses) in a common structure. At each restart point, instead of classically generating a random configuration to start with, each algorithm aggregates the shared knowledge to carefully craft a new starting point. We present several aggregation strategies and evaluate them on a large set of instances.

This paper is organized as follows: background material is presented in section 2. Section 3 describes previous work on parallel SAT and cooperative algorithms. Section 4 presents our methodology and our aggregation strategies, section 5 evaluates them, and section 6 presents some concluding remarks and future directions of research.

Background

The Propositional Satisfiability Problem

The Propositional Satisfiability Problem (SAT) can be represented by a pair V, C where, V indicates a set of boolean variables and C a set of clauses representing a propositional conjunctive-normal form (CNF).

Solving a SAT problem involves finding a solution i.e., a truth assignment for each variable such that all clauses are satisfied, or demonstrating that no such assignment can be found. If a solution exist the problem is stated as satisfied and unsatisfied otherwise. Currently, there are two well established techniques for solving SAT problems, complete and incomplete techniques [START_REF] Bordeaux | Propositional Satisfiability and Constraint Programming: A Comparative Survey[END_REF], the former is developed on top of the DPLL algorithm. It combines a tree-based search with constraint propagation, conflict-clause learning, and intelligent backtracking while the latter is based on local search algorithms to quickly find a truth assignment for a given satisfiable instance [START_REF] Hoos | Local Search Algorithms for SAT: An Empirical Evaluation[END_REF].

Local Search for SAT

Algorithm 1 describes a traditional local search algorithm for SAT solving, it starts with a random truth assignment for each variable in the formula F (initialconfiguration line 2), and the key point of local search algorithms is depicted in lines [START_REF] Bordeaux | Propositional Satisfiability and Constraint Programming: A Comparative Survey[END_REF][START_REF] Hoos | Local Search Algorithms for SAT: An Empirical Evaluation[END_REF][START_REF] Selman | A New Method for Solving Hard Satisfiability Problems[END_REF][START_REF] Selman | Noise Strategies for Improving Local Search[END_REF][START_REF] Mcallester | Evidence for Invariants in Local Search[END_REF][START_REF] Li | Diversification and Determinism in Local Search for Satisfiability[END_REF][START_REF] Hutter | Scaling and Probabilistic Smoothing: Efficient Dynamic Local Search for SAT[END_REF] here the algorithm flips the most appropriate variable candidate until a solution is found or a given number of flips is reached (MaxFlips), after this process the algorithm restarts itself with a new (fresh) random configuration.

As one may expect, a critical part of the algorithm is the variable selection function (select-variable) which indicates the next variable to be flipped in the current iteration of the algorithm. Broadly speaking, there are two main categories of variable selection functions, the first one motivated by the GSAT algorithm [START_REF] Selman | A New Method for Solving Hard Satisfiability Problems[END_REF] is based on the following score function:

score(x) = make(x) -break(x)
Intuitively make(x) indicates the number of clauses that are currently satisfied but flipping x become unsatisfied, and break(x) indicates the number of clauses that are unsatisfied but flipping x become satisfied. In this way, local search algorithms select the variable with minimal score value (preferably with negative value), because flipping this variable would most likely increase the chances of solving the instance.

The second category of variable selection functions is the Walksat-based one [START_REF] Selman | Noise Strategies for Improving Local Search[END_REF] which includes a diversification strategy in order to avoid local minimums, this extension selects, at random, an unsatisfied clause and then picks a variable from that clause. The variable that is generally picked will result in the fewest previously satisfied clauses becoming unsatisfied, with some probability of picking one of the variables at random. A := initial-configuration(F).

3:

for flip := 1 to Max-Flips do 4:

if A satisfies F then 5:

return A 6: end if 7:

x := select-variable(A) 8:

A := A with x flipped 9:

end for 10: end for 11: return 'No solution found'

Refinements

This section briefly reviews the main characteristics of state-of-the-art local search solvers for SAT solving. As pointed out above these algorithms are developed to deal with the variable selection function and are mainly devoted to avoid getting trapped in a local minima. This way, the following list describes several well-known mechanisms for selecting the most appropriate variable to flip at a given state of the search.

-Novelty [START_REF] Mcallester | Evidence for Invariants in Local Search[END_REF] firstly selects an unsatisfied clause c and from c selects the best v best and second best v 2best variable candidates, if v best is not the latest flipped variable in c then Novelty flips this variable, otherwise v 2best is flipped with a given probability p and v best with probability 1p. Important extensions to this algorithm can be found in Novelty+, Novelty++ and Novelty+p. -G 2 WSAT [8] (G2) uses a list of promising decreasing variables to determine the next variable to be flipped and if the list of decreasing variables is empty the algorithm uses Novelty++ as a backup heuristic. G 2 WSAT+p (G2+p) uses a similar strategy that G 2 WSAT however in this case the backup solver is Novelty+p. -Scaling and Probabilistic Smoothing (SAPS) [START_REF] Hutter | Scaling and Probabilistic Smoothing: Efficient Dynamic Local Search for SAT[END_REF] implements a multiplicative increase rule to dynamically modify the penalty for unsatisfied clauses and with a given probability P smooth this penalty value is adjusted according to a given smoothing factor ρ.

-Pure Additive Weighting Scheme (PAWS) [START_REF] Thornton | Additive versus Multiplicative Clause Weighting for SAT[END_REF] implements an additive increase rule to dynamically modify the penalty for unsatisfied clauses and if a given clause penalty has been changed a given number of times this penalty value is adjusted. -Reactive SAPS (RSAPS) [START_REF] Hutter | Scaling and Probabilistic Smoothing: Efficient Dynamic Local Search for SAT[END_REF] extends SAPS by adding an automatic tuning mechanism to identify suitable values for the smoothing factor ρ. -Adaptive Novelty+ (AN+) [START_REF] Hoos | An Adaptive Noise Mechanism for WalkSAT[END_REF] uses an adaptive mechanism to properly tune the noise parameter of Walksat-like algorithms (e.g, Novelty+) -Adaptive G 2 WSAT (AG2) [START_REF] Li | Combining Adaptive Noise and Look-Ahead in Local Search[END_REF] aims to integrate an adaptive noise mechanism into the G 2 WSAT algorithm. Similarly, Adaptive G 2 WSAT+p (AG2+p) also uses an adaptive noise mechanism into the G 2 WSAT+p algorithm.

Previous Work

In this section, we review the most important contributions devoted to parallel SAT solving and cooperative algorithms.

Complete Methods for Parallel SAT

GrADSAT [START_REF] Chrabakh | GridSAT: A System for Solving Satisfiability Problems Using a Computational Grid[END_REF] is a parallel SAT solver based on the zChaff solver and equipped with a master-slave architecture in which the problem space is divided into subspaces, these sub-spaces are solved by independent zChaff clients and learnt clauses whose size (i.e., number of literals) is less or equal to a given limit are exchanged between clients. The technique organizes load-balancing through a work stealing technique which allows the master to push work to idle clients. Unlike other parallel solvers for SAT which divide the initial problem space into sub-spaces, ManySAT [START_REF] Hamadi | ManySAT: A Parallel SAT Solver[END_REF] is a portfolio-based parallel solver where independent DPLL algorithms are launched in parallel to solve a given problem instance. Each algorithm in the portfolio implements a different and complementary restart strategy, polarity heuristic and learning scheme. In addition, the first version of the algorithm exchanges learnt clauses whose size is less or equal to a given limit. It is worth mentioning that ManySAT won the 2008 SAT Race, the 2009 SAT Competition and was placed second in the 2010 SAT Race (all these in the parallel track). Interestingly all the algorithms successfully qualified in the 2010 parallel track were based on a Portfolio architecture.

In [START_REF] Zhang | Parallel Execution of Stochastic Search Procedures on Reduced SAT Instances[END_REF] the authors proposed a hybrid algorithm which starts with a traditional DPLL algorithm to divide the problem space into sub-spaces. Each sub-space is then allocated to a given local search algorithm (Walksat).

Incomplete Methods for Parallel SAT

PGSAT [START_REF] Roli | Criticality and Parallelism in Structured SAT Instances[END_REF] is a parallel version of the GSAT algorithm. The entire set of variables is randomly divided into τ subsets and allocated to different processors. In this way at each iteration, if no global solution has been obtained, the i th processor uses the GSAT score function (see section 2) to select and flip the best variable for the i th subset. Another contribution to this parallelization architecture is described in [START_REF] Roli | Random Walk and Parallelism in Local Search[END_REF] where the authors aim to combine PGSAT and random walk, therefore at each iteration, with a given probability wp an unsatisfiable clause c is selected and a random variable from c is flipped and with probability 1-wp. PGSAT is used to flip τ variables in parallel at a cost of reconciling partial configurations to test if a solution has been found. gNovelty+ (v.2) [START_REF] Pham | Solver description[END_REF], belongs to the portfolio approach, this algorithm executes n independent copies of the gNovelty+ (v.2) algorithm in parallel, until at least one of them finds a solution or a given timeout is reached. This algorithm was the only parallel local search solver presented in the random category of the 2009 SAT Competition 4In [START_REF] Kroc | Integrating Systematic and Local Search Paradigms: A New Strategy for MaxSAT[END_REF], Kroc et al., studied the application of a parallel hybrid algorithm to deal with the max-SAT problem. This algorithm combines a complete solver (minisat) and an incomplete one (Walksat). Broadly speaking both solvers are launched in parallel and minisat is used to guide Walksat to promising regions of the search space by means of suggesting values for the selected variables.

Cooperative Algorithms

In [START_REF] Hogg | Solving the Really Hard Problems with Cooperative Search[END_REF] a set of algorithms running in parallel exchange hints (i.e., partial valid solutions) to solve hard graph coloring instances. To this end, they share a blackboard where they can write a hint with a given probability q and read a hint with a given probability p.

In [START_REF] Silva | Asynchronous Cooperative Local Search for the Office-Space-Allocation Problem[END_REF] the authors studied a sequential cooperative algorithm to deal with the office-space-allocation problem. In this paper cooperation takes place when a given algorithm is not able to improve its own best solution, at this point a cooperative mechanism is used to explore suitable partial solutions stored by individual heuristics. This algorithm is also equipped with a diversification strategy to explore different regions of the search space.

Although Averaging in Previous Near Solutions [START_REF] Selman | Domain-Independent Extensions to GSAT: Solving Large Structured Satisfiability Problems[END_REF] is not a cooperative algorithm by itself, this method is used to determine the initial configuration for the i th restart in the GSAT algorithm. Broadly speaking, the initial configuration is computed by performing a bitwise average between variables of the best solution found during the previous restart (restart i-1 ) and two restarts before (restart i-2 ). That is, variables with same values in both configurations are reused, and the extra set of variables are initialized with random values. Since overtime, configurations with a few conflicting clauses tend to become similar, all the variables are randomly initialized after a given number of restarts.

Knowledge Sharing in Parallel Local Search for SAT

Our objective is to extend a parallel portfolio of state-of-the-art local search solvers for SAT with knowledge sharing or cooperation. Each algorithm is going to share with others the best configuration it has found so far with its respective cost (number of unsatisfied clauses) in a shared pair M, C .

M =      X 11 X 12 . . . X 1n X 21 X 22 . . . X 2n . . . . . . . . . . . . X c1 X c2 . . . X cn      C = [C 1 , C 2 , . . . , C c ]
Where n indicates the total number of variables of the problem and c indicates the number of local search algorithms in the portfolio. In the following we are associating local search algorithms and processing cores. Each element X ji in the matrix indicates the i th variable of the best configuration found so far by the j th core. Similarly, the j th element in C indicates the cost for the respective configuration in M .

These best configurations can be exploited by each local search to build a new initial configuration. In the following, we propose seven strategies to determine the initial configuration (cf. function initial-configuration in algorithm 1).

Using Best Known Configurations

In this section, we propose three methods to build the new initial configuration init by aggregating best known configurations. In this way, we define init i for all the variables X i , i ∈ [1..n] as follows:

1. Agree: if there exists a value v such that v=X ji for all j ∈ [1..c] then init i =v, otherwise a random value is used.

Weighting Best Known Configurations

In contrast with our previous methods where all best known solutions are treated equally important, the methods proposed in this section use a weighting mechanism to consider the cost of best known configurations. The computation of the initial configuration init uses one of the following two weighting systems: Ranking and Normalized Performance, where values from better configurations are most likely to be used.

Ranking This method sorts the configurations of the shared matrix from worst to best according to their cost. The worst ranked one gets weight of 1 (i.e., RankW 1 =1), and the best ranked c (i.e., RankW c =c).

Normalized Performance This method assigns weights (N ormW ) considering a normalized value of the number of unsatisfied clauses of the configuration:

N ormW j = |C| -C j |C|
Using the previous two weighting mechanisms, we define the following four extra methods to determine initial configurations.

To this end, we define Φ(val, W eight) = k∈{j|Xji=val} W eight k .

1. Majority RankW : if there exists two values v and v ′ such that Φ(v, RankW ) > Φ(v ′ , RankW ) then init i =v, otherwise a random value is used. 2. Majority NormalizedW : if there exists two values v and v ′ such that Φ(v, N ormW ) > Φ(v ′ , N ormW ) then init i =v, otherwise a random value is used. 3. Prob RankW : init i =1 with probability P Rones = Rones Rones+Rzeros and init i =0 with probability 1-P Rones , where Rones=Φ(1, RankW ) and Rzeros=Φ(0, RankW ). 4. Prob NormalizedW : init i =1 with probability P N ones = N ones N ones+N zeros and init i =0 with probability 1-P N ones , where N ones=Φ(1, N ormW ) and N zeros=Φ(0, N ormW )

Restart Policy

As mentioned earlier on, shared knowledge is exploited when a given algorithm is restarted. At this point the current working configuration of a given algorithm is re-initialized according to a given aggregation strategy. However, it is important to restrict cooperation since it adds overheads and more importantly tend to generate similar configurations. In this context, we propose a new restart policy to avoid re-initializing the working configuration again and again. This new policy re-initializes the working configuration for a given restart (i.e., every MaxFlips) if and only if, performance improvements in best known solutions have been observed during the latest restart window. This new restart policy is formally described in the following definition, where we assume that bc ki is the cost of the best known configuration for a given algorithm i up to the (k -1) th restart.

Definition 1 At a given restart k for a given algorithm i the working configuration is reinitialized iff there exists an algorithm q such that bc kq = bc (k-1)q and q = i.

Experiments

Experimental Settings

We conducted experiments using instances from the RANDOM category of the 2009 SAT competition. Since state-of-the-art local search solvers are unable to solve UNSAT instances, we filtered out these instances. We also removed instances whose status was reported as UNKNOWN in the competition. This way, we collected 359 satisfiable instances.

We decided to build our parallel portfolio on UBCSAT-1.1, a well known local search library which provides efficient implementation of the latest local search for SAT algorithms [START_REF] Tompkins | UBCSAT: An Implementation and Experimentation Environment for SLS algorithms for SAT and MAX-SAT[END_REF]. We did preliminary experiments to extract from this library the 8 algorithms which perform best on our set of problems. From that, we defined the following three baseline portfolio constructions where algorithms are independent searches without cooperation. The first one pcores-PAWS uses p copies of the best single algorithm (PAWS), the second portfolio 4cores-No sharing uses the best subset of 4 algorithms (PAWS, G2+p, AG2, AG2+p) and the last one 8cores-No sharing uses all the 8 algorithms (PAWS, G2+p, AG2, AG2+p, G2, SAPS, RSAPS, AN+). All the algorithms were used with their default parameters, and without any restart. Indeed these techniques are equipped with important diversification strategies and usually perform better when the restart flag is switched off (i.e., MaxFlips=∞).

On the other hand, the previous knowledge aggregation mechanisms were built on top of a portfolio with 4 algorithms (same algorithms as 4cores-No sharing) and a portfolio with 8 algorithms (same algorithms as 8cores-No sharing). There, we used the modified restart policy described in section 4.3 with M axF lips set to 10 6 .

All tests were conducted on a cluster of 8 Linux Mandriva machines with 8 GB of RAM and two quad-core (8 cores) 2.33 Ghz Intel Processors. In all the experiments, we used a timeout of 5 minutes (300 seconds) for each algorithm in the portfolio, so that for each experiment the total CPU time was set to c × 300 seconds, where c indicates the number of algorithms in the portfolio.

We executed each instance 10 times (each time with a different random seed) and reported two metrics, the Penalized Average Runtime (PAR) [START_REF] Hutter | Tradeoffs in the Empirical Evaluation of Competing Algorithm Designs[END_REF] which computes the average runtime overall instances, but where unsolved instances are considered as 10× the cutoff time, and the runtime for each instance which is calculated as the median across the 10 runs. Overall, our experiments for these 359 SAT instances took 187 days of CPU time.

Practical Performances with 4 Cores

Fig. 1 shows the results of each aggregation strategy using a portfolio with 4 cores, comparatively to the 4 cores baseline portfolios. The x-axis gives the number of problems solved and the y-axis presents the cumulated runtime.

As expected, the portfolio with the top 4 best algorithms (4cores-No Sharing) performs better (309) that the one with 4 copies of the best algorithms (4cores-PAWS ) (275).

The performance of the portfolios with knowledge sharing is quite good. Overall, it seems that adding a weighting mechanism can often hurt the performance of the underlying aggregation strategy. Among the weighting options, it seems that the Normalized Performance performs better. The best portfolio A detailed examination of 4cores-Prob and 4cores-No Sharing is presented in Figs. 2 and3. These Figures show, respectively, a runtime and a best configuration cost comparison. In both figures, points below (resp. above) the diagonal line indicate that 4cores-Prob performs better (resp. worse) than 4cores-No Sharing. In the runtime comparison, we observe that easy instances are correlated as they require few steps to be solved, and for the remaining set of instances 4cores-Prob usually exhibits a better performance. On the other hand, the second figure shows that when the instances are not solved, the median cost of the best configuration (number of unsatisfied clauses) found by 4cores-Prob is usually better than for 4cores-No Sharing. Notice that some points are overlapped because the two strategies reported the same cost.

All the experiments using 4 cores are summarized in Table 1, reporting for each portfolio the number of solved instances (#solved), the median time across all instances (median time), the Penalized Average Runtime (PAR) and the total number of instances that timed out in all the 10 runs (never solved). These results confirm that sharing best known configurations outperforms independent searches, for instance 4cores-Prob and 4cores-Prob NormalizedW solved respectively 20 and 17 more instances than 4cores-No Sharing and all the cooperative strategies (except 4cores-Majority RankW ) exhibit better PAR. Interestingly, 4cores-PAWS exhibited the best median runtime overall the experiments with 4 cores, this fact suggests that PAWS by itself is able to quickly solve an important number of instances. Moreover, only 2 instances timeout in all the 10 runs for 4cores-Agree and 4cores-Prob NormalizedW against 7 for 4cores-No Sharing. Notice that this

Practical Performances with 8 Cores

We now move on to portfolios with 8 cores. The results of these experiments are depicted in Fig. 4 indicating the total number of solved instances within a given amount of time. As in previous experiments, we report the results of baseline portfolios 8cores-No Sharing and 8cores-PAWS, and in this case we focus the experiments on Prob and Prob NormalizedW (the best two strategies using 4 cores). We can observe that the cooperative portfolios largely outperform the non-cooperative ones.

Table 2 summarizes these results, and once again it includes the best individual algorithm running in a single core. We can remark that 8cores-Prob and 8cores-Prob NormalizedW solve respectively 24 and 16 more instances than 8cores-No Sharing. Furthermore, it shows that knowledge sharing portfolios are faster than individual searches, with a PAR of 3743.63 seconds for 8cores-No Sharing against respectively 2247.97 for 8cores-Prob and 2295.99 for 8cores-Prob NormalizedW . Finally, it is also important to note that only 1 instance Extensive experimental results presented in this paper show that Prob (4 and 8 cores) exhibited the overall best performance. We attribute this to the fact that the probability component of this method balances the exploitation of best solutions found so far with the exploration of other values for the variables, helping in this way, to diversify the new starting configuration.

Hardware Impact

In this section, we wanted to assess the inherent slowdown caused by increased cache, and bus contingency when more processing cores are used at the same time. To this end we decided to run our PAWS baseline portfolio where each independent algorithm uses the same random seed on respectively 1, 4 and 8 cores. Since all the algorithms are executing the same search, this experiment measures the slowdown caused by hardware limitations. The results are presented in Fig. 5.

The first case executes a single copy of PAWS with a timeout of 300 seconds, the second case executes 4 parallel copies of PAWS with a timeout of 1200 seconds (4 × 300) and the third case executes 8 parallel copies of PAWS with a timeout of 2400 seconds (8 × 300). Finally, we estimate the runtime of each instance as the median across 10 runs (each time with the same seed) divided by the number of cores. In this figure, it can be observed that the performance overhead is almost not distinguishable between 1 and 4 cores (red points). However, the overhead between 1 and 8 cores is important for difficult instances (black points).

In this work, our objective was to integrate knowledge sharing strategies in parallel local search for SAT. We were motivated by the recent developments in parallel DPLL solvers. We decided to restrict the information shared to the best configuration found so far by the algorithms in a portfolio. From that we defined several simple knowledge aggregation strategies along a specific lazy restart policy which creates a new initial configuration when a fix cutoff is meet and when the quality of the shared information has been improved.

Extensive experiments were done on a large number of instances coming from the latest SAT competition. They showed that adding the proposed sharing policies improves the performance of a parallel portfolio, this improvement is exhibited in both number of solved instances and the Penalized Average Runtime (PAR). It is also reflected in the best configuration cost of problems which could not be solved within the time limit.

We believe that our work represents a very first step in the incorporation of knowledge sharing strategies in parallel local search for SAT. Further work will investigate the use of additional information to exchange, for instance: tabu-list, the age and score of a variable, information on local minima, etc. It should also investigate the best way to integrate this extra knowledge in the course of a given algorithm. As said earlier, state-of-the-art local search perform better when they do not restart. Incorporating extra information without forcing the algorithm to restart is likely to be important.

Algorithm 1

 1 Local Search For SAT (CNF formula F, Max-Flips, Max-Tries) 1: for try := 1 to Max-Tries do 2:

2 .

 2 Majority: if there exists two values v and v ′ such that |{X ji = v|j ∈ [1..c]}| > |{X ji = v ′ |j ∈ [1..c]}| then init i =v, otherwise a random value is used. 3. Prob: init i =1 with probability p ones = ones c and init i =0 with probability 1p ones , where ones = |{X ji = 1|j ∈ [1..c]}|.

Fig. 1 .

 1 Fig. 1. Number of solved instances using 4 cores in a given amount of time

Fig. 2 .Fig. 3 .

 23 Fig. 2. Runtime comparison, each point indicates the runtime to solve a given instance using 4cores-Prob (y-axis) and 4cores-No Sharing (x-axis)

Fig. 4 .

 4 Fig. 4. Number of solved instances using 8 cores in a given amount of time

Fig. 5 .

 5 Fig. 5. Runtime comparison using parallel local search portfolios made of respectively 1, 4, and 8 identical copies of PAWS (same random seed). Red points indicate the performance of 4 cores vs 1 core. Black points indicate the performance of 8 cores vs 1 core, points above the blue line indicate that 1 core is faster

Table 1 .

 1 Table also includes 1core-PAWS, the best sequential local search on this set of problems. The PAR score for 1core-PAWS is lower than the other values of the table because this portfolio uses only 1 algorithm, therefore the timeout is only 300 seconds, while 4 cores portfolios use a timeout of 1200 seconds. Overall evaluation using 4 cores

	Strategy	#solved median time PAR never solved
	1core-PAWS	249	1.76	911.17	71
	4cores-PAWS	275	1.63	2915.19	61
	4cores-No Sharing	309	2.19	1901.00	7
	4cores-Agree	321	2.54	1431.33	2
	4cores-Majority	313	2.53	1724.94	11
	4cores-Prob	329	2.51	1257.93	4
	4cores-Majority RankW	304	2.47	1930.61	11
	4cores-Majority NormalizedW 314	2.48	1807.42	9
	4cores-Prob RankW	316	2.53	1621.33	7
	4cores-Prob NormalizedW	326	2.50	1261.82	2

Table 2 .

 2 Overall evaluation using 8 cores

	Strategy	#solved median time PAR never solved
	1core-PAWS	249	1.76	911.17	71
	8cores-PAWS	286	2.00	5213.84	56
	8cores-No Sharing	311	2.33	3743.63	8
	8cores-Prob	335	2.45	2247.97	2
	8cores-Prob NormalizedW 327	2.47	2295.99	1

http://www.satcompetition.org/2009/

Acknowledgements

We would like to thank Said Jabbour and Ibrahim Abdoulahi for helpful discussions about parallel SAT solving and the anonymous reviewers for their comments which helped to improve this paper.