Soumaya Zirari
email: soumaya.zirari@univ-fcomte.fr

Philippe Canalda
email: philippe.canalda@univ-fcomte.fr

François Spies
email: francois.spies@univ-fcomte.fr

WiFi GPS based Combined positioning Algorithm

Keywords: component, positioning, GPS, GSM, WiFi, combination, hybridisation. I

If nowadays, positioning becomes more and more accurate, and covers better and better a territory (indoor and outdoor), it remains territories where traditional (and basic) positioning system (GPS, gsm or WiFi) and hybrid ones (GPSgsm, GPS-WiFi, GPS-WiFi-gsm, ...) are insufficient and requires research investment treating combined positioning. In this paper we propose a GPS-WiFi combined positioning algorithm, based on trilateration technique. Real experiments and other simulation are conduced and demonstrate accuracy gains, even where various criteria dilution of precision (GPS dop's criteria, or ours WiFi geometrical and signal attenuation's dop proposal, or hybrid dop one's) indicate all the disruption of positioning service. A testbed scenario issued from a real urban campus environment validates not only our GPS-WiFi combined positioning algorithm but also an implementation of pertinent positioning techniques and dop's criteria. This work constitutes a further step to better position everywhere and to ensure continuity of a positioning service.

INTRODUCTION

Position location capabilities have become increasingly important to wireless handset manufacturers and users. New location-based applications emerged including entertainment, fleet management, commerce, safety and systems applications. The main requirement for all those new services is to provide a high accuracy independently of the environment.

The democratization of wireless and mobile networks leads to new positioning services in close environment while the emergence of new GNSS generation tends to improve the accuracy in rural and suburban areas.

Traditionally, the user position is estimated through the trilateration of at least three measured distances from fully three emitters. The distances are measured using different methods such TDOA that determines the mobile position by measuring the relative time of arrival of signals transmitted by three base stations at the handset, or the signal transmitted by a mobile at three base stations, TOA that is based on the intersection of the distance circles (the distances are calculated trough the travel time of a radio signal from a single transmitter to a remote single receiver) or AOA that allows determining the propagation direction of the signal depending on the applications and the positioning system.

In the sequel we present, first two among principal systems of positioning, the GPS system and the WiFi's one. Second we introduce new approach based on hybridization and then combination to better improve the positioning service offer. Third our contributions are described composed of an WiFi-GPS based combined positioning algorithm and a demonstrator based on innovative dilution of precision criteria that simulates and emulates real scenario of positioning only handled by such combined positioning proposal. Fourth and finally, we analyse and conclude the results obtained and laid the groundwork for future work to tackle.

II. GLOBAL POSITIONING SYSTEM

The Global Positioning System [START_REF][END_REF] is a passive Global Navigation Satellite System maintained by the DoD (Department of Defence) of the United State. The GPS is the result of the merging of two independent programs that were begun in the early 1960's : the US Navy's TIMATION Program [15] and the US Air Force's 621B Project [16]. The first US pronouncement regarding civil use of GPS came in 1983. Its primary mission is to provide passive, real-time, 3-D positioning navigation and velocity data for land, air, and sea-based applications operating anywhere in the world. The target position is measured through a range of measurements which consists in measured distances between the receiver antenna and four to ten satellites in view, and the position is determined from the adjusted intersections of the range vectors that is equivalent to trilateration solution in terrestrial surveying. These measured distances are determined by the GPS receiver by precisely measuring the time it takes a coded signal to travel from the satellites to the receiver antenna.

The fact that the user may be in environments poorly covered or not covered at all (indoor, urban canyons, etc.) makes the satellite signals reception difficult. This constraint have an important impact on the accuracy, the Quality Of Service and the service continuity that ensure that positioning can be realised in an agreed time scale and respond to a satisfactory level of service availability.

III. 802.11

The RADAR system [START_REF] Bahl | RADAR : An inbuilding RF-based user location and tracking system[END_REF] is a positioning system implementing a location service using the information obtained from already existing 802.11 WiFi network. RADAR is based on Radio Frequency (RF) signal strength. In fact, RADAR uses the received signal strength indicator (RSSI) as an indicator of the distance between an AP and a receiver. This approach allows the consumer to use the positioning service without any purchase of any specialized equipment.

Based on RADAR, Ekahau emerged. Ekahau [START_REF] Roos | A Probabilistic Approach to WLAN User Location Estimation[END_REF] Real Time Location Systems (RTLS) is a fully automated system dedicated to continually monitoring the location of assets or personnel on a campus area. Ekahau RTLS is a Wi-Fi-based location tracking solution which offers 3 to 5 meters resolution using six enterprise Wi-Fi APs. It delivers information to authorized users via the corporate network through application software or application programming interfaces in real-time. RTLS typically consists of tags, reference devices for locating tags, data network, server software and end-user application software. Ekahau RTLS uses existing Wi-Fi (802.11a/b/g/n) standard access points as the reference devices for tag location and as the data network.

Other Wi-Fi positioning system is the FBCM Friis Based Calibrated Model that adapts the Friis formula which is well suited to homogeneous environments, in order to provide a better accuracy when the user is in heterogeneous environments. The FBCM [START_REF] Lassabe | A friisbased calibrated model for WiFi terminals positioning[END_REF] based on the signal strength attenuation model is dedicated to a specific building. The friis propagation model is calibrated and modified in such a way to better follow the Wi-Fi equipment mobility inside a building.

Those systems among others can be precise only if at least four Access Points (APs) are visible, which is not always the case.

IV. HYBRID POSITIONING SYSTEMS

Hybrid Positioning Systems (HPS) consists in switching from one position delivered by a system to another position delivered by another system, and a position which is likely more accurate.

Skyhook Wireless developed a HPS called XPS combining the benefits of GPS, Cell Tower triangulation and Wi-Fi Positioning. The system delivers a range accuracy of 10m-20m whether indoors or outdoors, in the country or downtown [12].

Another HPS is Navizon that is a positioning system allowing the user to get its positioning information thanks to Wi-Fi and Cell Tower signals. In order to know the exact location of each Wi-Fi APs and cell towers, they need to be mapped by users with GPS enabled devices. In fact, Navizon's users with GPS enabled devices help the Navizon industry to "map the wireless landscape».

The idea of Navizon is fairly simple. The Navizon users who have GPS enabled phones, or a standalone GPS device map the location of Cell towers and Wi-Fi Access Points wherever they go, so that other users who do not have GPS will be able to use Navizon system independently of GPS.

As we can conclude, hybridization appears to be a good candidate to overcome the shortcomings of self-positioning systems but still the problem remains when no enough satellite transmitters or APs are visible, or available, to calculate the position.

V. COMBINED POSITIONING SYSTEMS

The main problem of the majority of the positioning systems is that not always fully three emitters are visible with strong signals and clear line of sight. Thus, manufacturers such as QUALCOMM developed the gpsOne [5,[START_REF]Hybrid Position Location Technology White Paper. gpsOne Overview[END_REF] solution for CDMA networks to address the need for accurate commercial-grade, high-availability position location technology. Traditionally, there have been two methods for providing wireless position location information, network-based solutions where the network provides to the mobile its position estimation and handsetbased solutions where a mobile node discovers its own position using some precise mechanism. GpsOne merges the two solutions and provides a chipset that triangulate measurement from cellular networks and GPS in order to estimate the user position. Other solutions proposed in [START_REF]Correcting GPS position in a hybrid navigation system[END_REF] combine the GPS and Dead-Reckoning Navigation Systems to improve accuracy for vehicle positioning or Verizon Wireless [7] which merges the advantages of both GPS and cellular networks.

The combination offers the opportunity to address the various shortcomings that knows the positioning. Now we must think to combine different positioning systems if we are to improve the accuracy, process continuity of service or even improve the quality of service

VI. CONTRIBUTION

In this paper, we propose a combined positioning system that combines 802.11 and GPS to calculate the location. Actually, Access point have become increasingly spreading. In dense areas, different obstacles make difficult the interception of four strong signals to solve the four unknowns (x, y, z, t) in a GPS positioning problem. Where x, y and z are the user coordinates and t is the time difference between the GPS receiver and the satellite. We propose to complement the GPS equation system using pseudorange measurements with Signal Strength measurements from 802.11 network. In fact the aim of our proposition is if the number of visible satellites is less than four satellites, we complete the set of the equations (which is less than four equations) with equations obtained from the Wi-Fi positioning system.

We need at least four GPS equations from four different satellites. The distance between the satellite i and the user is:

(1)

Where  X i ,Y i , Z i  are the satellite i coordinates and  X u ,Y u , Z u ,  t u  are the four unknowns.

Concerning the AP equations we need at least three equations from three APs in order to estimate the user position. In fact, 3 equations are required when positioning one user outdoor, on the ground. When positoning indoor requires determining altitude, we add another equation.

N-Dimension require N+1-equations.

(

) 2
Where  X c ,i ,Y c ,i , Z c , i  are the AP i coordinates. In case we have only three visible satellites, the goal of our work is that the positioning may be without any interruption. Indeed, we complete the set of GPS equations by AP equations. In the case of three visible satellites we need supplementary AP equation. So the set of equations become as following:

(3)

We don't introduce the  t u in the AP equations because we consider that d i was obtained through Signal Strength measurements. Indeed, we don't take into account the difference time between the AP and the user. The algorithm of the combined position system based on GPS and Wi-Fi.

We initiate our algorithm with tracking signals from both AP and GPS satellites. If the number of visible satellites is less than four or the number of visible AP is less than four then we combine them so that the number of visible AP and satellites is more than four. The accuracy depends on the combinations of measurements from satellites and APs (see Figure 3). This leads us to thinking: Why not switch configuration/combination to another while having a goal to achieve maximum accuracy? What is the indicator that allowed us to choose the configuration/combination ideal for a situation "s" at time "t"?

In our case, the more appropriate formulation of this GDOP that can help us to choose the best configuration of our combined position system at the time "t" in the situation "s" is the following:

(4)
The GDOP is:

(5) VII. SIMULATION This section presents some results from our proposal simulations. Performance of the position estimation technology was tested with different number of satellites in view and different number of Access Points in view.

The GPS measurements were combined with forward link measurements from at least one access point in situations where the number of satellites visible was not enough to compute a location.

The algorithm of our simulation follows the steps bellow:

1 we use the Kepler parameters for ideal circular orbits from the matrix in gpskep.mat and maintain as global variables with GpsSoft (1996)

2 We generate a path that consists of straight segments joined by constant-radius turns.

3 Generate matrix of positions of satellites which are [START_REF] Hofmann-Wellenhof | 5gpsOneTM: a hybrid position location system[END_REF] We generate the visible satellites to the user at location usrxyz.

5 We generate the visible Access Points to the user at location usrxyz.

6 We generate a vector of 'measured' pseudoranges and accumulated delta ranges (i.e., integrated Doppler) to all visible satellites.

7 We generate a vector of 'measured' distances and accumulated delta ranges (i.e., integrated Doppler) to all visible Access Points.

8 We compute position from satellite and Access Points positions, pseudoranges and distances via ordinary least squares.

The following curves present simulation results from each scenario.

VIII. ANALYSIS

After analyzing the various curves presented in the previous section, we conclude that the accuracy is best according to the various combinations of measurements from satellites and APs.

When we compare combined positionning system based on GPS and cellular networks with our proposition that combines GPS and Wi-Fi networks, we conclude that the accuracy of our proposition stay always under a threshold of 100 meter. This quality guaranty to the user the knowledge of an approximate location even if the condition deplorable. The Table 1. Shows that the estimated position with gpsOne can reach 345 meters in poor conditions such as only one satellite in view when, with the same conditions noted proposal remains below the 100 meter. This accuracy is sufficient in the case of application that seeks only indicate eg restaurants are near the user.

IX. CONCLUSION

The simulation done, shows that the accuracy is less than 100 meter in the case of having two satellites and two Access Points in view instead of 253 meter [5] using gpsOne. The simulations shows also that when the number of satellites is equal to four or above, and when the angle of the satellites perception is unsatisfactory (satellites more or less aligned), a combined solution can make the positioning accuracy of about 5m, even environments poorly covered or not covered at all (indoor, urban canyons, etc.). Indeed, regardless of the environment, the user continues to have a position even if the accuracy exceeds one meter.

The main idea of our system is based on the principle of providing an idea about the location of the user at any time (even if the accuracy is not of the order of a meter) rather than the absence of any clue to the position.

Figure 1 .

 1 Figure 1. To estimate the user position we need at least four visible emitters from at leat one positioning system

Figure 2 .

 2 Figure 2.The algorithm of the combined position system based on GPS and Wi-Fi.

Figure 3 .

 3 Figure 3. The accuracy depends on the configuration of the combined position system

Figure 4 .

 4 Figure 4. All satellites in view. The user is in an open environment. The selective availability is activated. Mean error =36.4022 m. The mean error is equal to 25m when we use additional APs

Figure 6 .

 6 Figure 6. The true and the estimated trajectory with four aligned satellites and two APs. The selective availability is disabled..

Figure 7 .

 7 Figure 7. The true and the estimated trajectory with only one aligned satellites and visible APs. The selective availability is disabled.

TABLE I .

 I RESULTS COMPARISON

		GpsOne	Our proposal
	Four satellites	18 meter	19 meter
	Three satellites	35 meter	80 meter
	Two satellites	253 méter	78 meter
	One satellites	345 meter	95 meter


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

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

Towards an Optimal Positioning of Multiple Mobile Sinks in WSNs for Buildings

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

The need for wireless sensor networks is rapidly growing in a wide range of applications specially for buildings automation. In such networks, a large number of sensors with limited energy supply are in charge of relaying the sensed data hop by hop to the nearest sink. The sensors closest to the sinks deplete their energy much faster than distant nodes because they carry heavy traffic which causes prematurely the end of the network lifetime. Employing mobile sinks can alleviate this problem by distributing the high traffic load among the sensors and increase the network lifetime. In this work, we aim to find the best way to relocate sinks inside buildings by determining their optimal locations and the duration of their sojourn time. Therefore, we propose an Integer Linear Program 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. We evaluated the performance of our approach by simulation and compared it with others schemes. The results show that our solution extends significantly the network lifetime and balances notably the energy consumption among the nodes.

Introduction

Recent years have witnessed an increasing need for wireless sensor networks (WSNs) in a wide range of applications specially for buildings automation. In fact, the WSNs can be used as a way to reduce the waste of energy inside buildings by reporting essential information from the indoor environment allowing, for instance, to turn off the unnecessary electric appliances in the rooms. Nevertheless, wireless sensor networks deployment inside buildings is a very challenging problem [START_REF] Tourancheau | Multiple mobile sinks positioning in wireless sensor networks for buildings[END_REF]. Such networks are composed of low cost tiny devices with sensing, data processing and communication capabilities. These sensors have a short operational life because they are equipped with a limited number of batteries supplying energy. Moreover, it is usually impractical and even impossible to replace or recharge them. The sensors, which are densely deployed in the area of interest, measure and monitor their indoor environment (temperature, humidity, light, sound, etc.,) and collaborate to forward these measurements towards the nearest resource-rich collector, referred to as the sink node. The sensor nodes which are far away from the sink use multi-hops communication. This mean of communication makes the sensors near the sinks deplete their energy much faster than distant nodes because they carry the packets of sensors located farther away in addition to their own packets. Therefore, what is known as a hole appears around the sinks and makes distant nodes unreachable and unable to send their data. Consequently, the network lifetime ends prematurely.

More and more efforts have been done recently to improve the lifetime of WSNs. Many communication protocols have been proposed including among others topology control [START_REF] Pan | Topology control for wireless sensor networks[END_REF] [START_REF] Li | Topology control in heterogeneous wireless networks: Problems and solutions[END_REF], routing [START_REF] Sankar | Maximum lifetime routing in wireless ad-hoc networks[END_REF] [START_REF] Fodor | Efficient routing to mobile sinks in wireless sensor networks[END_REF] and clustering [START_REF] Younis | Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach[END_REF]. However, further improvement can be achieved if we relocate the sinks in order to change over time the nodes located close to them. Thus, this can solve the energy hole problem and guarantee balanced energy consumption among the 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 optimally the network lifetime. To answer these questions, we propose an Integer Linear Program (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 [START_REF] Gandham | Energy efficient schemes for wireless sensor networks with multiple mobile base stations[END_REF] [START_REF] Alsalih | Placement of multiple mobile base stations in wireless sensor networks[END_REF].

The contribution of our work concerns not only the definition of an ILP which determines the optimal locations of multiple mobile sinks but also shows 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 3 sinks in a network with hundred sensors is almost 230 % in our experiments. Such results can provide useful guidelines for real wireless sensor network deployment.

The rest of this paper is organized as follows. In Section 2, we review the previously proposed approaches to solve the energy hole problem and extend the network lifetime in WSNs. Section 3 describes the system model including the major assumptions. Section 4 presents the formulation of our proposed ILP for multiple mobile sinks. Section 5 evaluates the performance of the proposed solution and presents the experimental results. Section 6 concludes the paper.

Related Work

In order to improve the network lifetime of WSNs, many researchers looked for approaches that help to solve the energy hole problem. Several solutions proposed to place more sensor nodes around the sink [START_REF] Wu | Avoiding energy holes in wireless sensor networks with nonuniform node distribution[END_REF][10] [START_REF] Lian | Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[END_REF]. This solution is called nonuniform node distribution and consists in adding nodes to the areas with heavier traffic in order to create different node densities. However, these solutions are not always feasible in practice and result in unbalanced sensing coverage over different regions of the network.

Another way of optimizing the network lifetime is to use multiple sinks instead of one in order to decrease the average of packets that has to pass through the nodes close to the sinks. The location of these sinks has a great influence on the network lifetime. For this reason, many works focused on the optimal placement of multiple static sinks in WSNs. The majority of the sinks placement problem formulations are NP-complete depending on the assumptions and network model. Therefore to reduce this complexity, approximation algorithms were used [START_REF] Bogdanov | Power-aware base station positioning for sensor networks[END_REF] and heuristics were adopted to reduce the energy dissipation at each node [START_REF] Oyman | Multiple sink network design problem in large scale wireless sensor networks[END_REF]. In [START_REF] Kim | Optimal multi-sink positioning and energy-efficient routing in wireless sensor networks[END_REF], the problem was formulated by a linear programming model to find the optimal positions of static sinks and the optimal traffic flow rate of routing paths in WSNs.

Most of the optimal multi-sinks positioning approaches described previously contribute to increase the network lifetime. Nevertheless, it was 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 achieves further improvements in network lifetime by distributing the load of the nodes close to the sink. Furthermore, the sink mobility has many other advantages. In fact, it can improve the connectivity of the isolated sensors and may guarantee the sink security in case of malicious attacks.

The majority of related works studied the mobility of a single sink [START_REF] Luo | Joint mobility and routing for lifetime elongation in wireless sensor networks[END_REF][16] [17][18][19] [START_REF] Bi | Moving schemes for mobile sinks in wireless sensor networks[END_REF]. But, very few researches focused on the mobility of 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 with several sinks by dividing it into several clusters. Each sink can only move in its cluster.

There are basically three categories of sink mobility. Mobile sink may move in a fixed path [START_REF] Luo | Joint mobility and routing for lifetime elongation in wireless sensor networks[END_REF], may take a random path [START_REF] Shah | Data mules: Modeling a three-tier architecture for sparse sensor networks[END_REF] or may move in optimal locations in terms of network lifetime and energy consumption.

The authors of the paper [START_REF] Luo | Joint mobility and routing for lifetime elongation in wireless sensor networks[END_REF] suggested that the sink moves on the periphery of the network to gather the data of the sensors deployed within a circle. The authors of [START_REF] Shah | Data mules: Modeling a three-tier architecture for sparse sensor networks[END_REF] proposed to use "Data Mules" which move randomly on the sensor field and collect data from the nodes.

An often used way to determine the locations of mobile sinks in the third category is to develop an algorithm. Some proposed algorithms make a moving decision of sinks 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.

Some others algorithms find the locations of mobile sinks by solving a mathematical model [23][24]. In [START_REF] Vincze | Deploying multiple sinks in multi-hop wireless sensor networks[END_REF], the algorithm minimizes the average distances between sensors and nearest 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 that the difference between the maximum and the minimum residual energy of nodes is minimized.

To find the optimal locations of mobile sinks, some proposals formulated the problem as an Integer Linear Program ILP. In [START_REF] Alsalih | Placement of multiple mobile base stations in wireless sensor networks[END_REF], the proposed ILP maximizes the minimum residual energy over all nodes. In [START_REF] Gandham | Energy efficient schemes for wireless sensor networks with multiple mobile base stations[END_REF], the proposed ILP minimizes the energy consumed at each node.

Most of proposed approaches to determine the locations of multiple mobile sinks in WSNs are centered on energy minimization. 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 for instance.

System Model

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

Network Model

-All sensors are statically placed in a bi-dimensional grid of same size cells constructed from the building plan as shown in Figure 1. -All sensors have a limited initial energy supply and a fixed transmission range equal to the distance between two nodes (i.e, cell size). -Each sensor regularly generates the same amount of data. -The number of sinks is fixed and known beforehand.

-The sinks can be located only in feasible sites where they are connected to power supply and the Internet.

Routing and Path Selection

The sensor nodes which are not co-located with any sinks inside the grid send their generated data hop by hop to the nearest sink. 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] Maniezzo | Energetic trade-off between computing and communication resource in multimedia surveillance sensor network[END_REF]. Therefore, the power expended to transmit a L 1 -bit/s to a distance d is: 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 T x = L 1 γ 1 + L 1 γ 2 d β (1)
P R x = L 2 α ( 2
)
where α is the energy consumption factor indicating the power consumed per bit at receiver circuit. Thus, the total energy consumed by 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 T (J/bit) is the energy consumption coefficient for transmitting one bit. -e R (J/bit) is the energy consumption coefficient for receiving one bit. -g r (bit/s) is the rate at which data packets are generated.

-r 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 sensor 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) k1∈F k2∈F ... km∈F T l k 1 k 2 ...km p k 1 k 2 ...k m i ≤ e 0 , i ∈ S (5)
l k 1 k 2 ...km ≥ 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] Fodor | Efficient routing to mobile sinks 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 ...km 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 our model, the energy consumption coefficient for transmitting a bit denoted by e T and the energy consumption coefficient for receiving a bit denoted by e R are constant:

e T = γ 1 + γ 2 d β (8) e R = α (9)
From the equation (3), the total power consumed at a sensor node is:

P total = e T L 1 + e R L 2 (10)
Therefore, the p k i is calculated as follows [START_REF] Wang | Exploiting sink mobility for maximizing sensor networks lifetime[END_REF]:

p k i = e R j:i∈N k j r k ji + e T j∈N k i r k ij , i ∈ S, k ∈ F, i = k (11)
p k i = e T g r , i ∈ S, k ∈ F, i = k ( 12
)
At each node, the total of outgoing packets is equal to the total incoming packets plus the data packets generated [START_REF] Wang | Exploiting sink mobility for maximizing sensor networks lifetime[END_REF]:

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

p k i = e R j:i∈N k j r k ji +e T ( j:i∈N k j r k ji +g r ), i ∈ S, k ∈ F, i = k (14)

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 sensor 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 ( 15
) k∈Fj T l k p k i ≤ e 0 , i ∈ S j ( 16
)
l k ≥ 0, k ∈ F j ( 17
)
The lifetime of network, which is the time until the first sensor dies, is determined by the following equation:

Z = min j (Z j ) (18)

Simulation and Results

To evaluate the performance of the proposed ILP, we built a simulator in Java environment with variable number of sensors and sinks deployed on different grid sizes.

In order to determine the network lifetime and the optimal locations of sinks, we solved the proposed ILP with CPLEX[26] version 11.2. The calculation of the power consumed by the sensor node when the nearest sink is located at a 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 the energy found in two Alkaline batteries AA of 1.5V usually 2600mAh i.e., e o = 28080 J. We also chose the energy consumption coefficient for transmitting and receiving one bit the same as vendorspecified 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 efficient to have technicians relocating sinks in buildings very often. The rate g r at which data packets are generated is equal to 1 bit/s which is typical sampling rate for HVAC parameter control added the network layer encapsulations. Notice that real microcontrollers 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 get a deeper understanding of the efficiency of sinks mobility according to our proposed ILP solution, we investigated the network lifetime, the pattern of the distribution of the sinks sojourn times at the different nodes, the energy consumption and the residual energy at each node. Furthermore, we made a comparative study with four other schemes.

Thus, the following schemes were implemented:

1) Static: Static sinks placed at their optimal locations using the equation ( 19) 2) Periphery: Sinks moving in the periphery of the network 3) Random: Sinks moving randomly 4) Cluster: Sinks moving separately in different clusters according to ILP solution 5) ILP: Sinks moving in the entire network according to ILP solution

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 ( 19
)
where

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

Network lifetime

We compared the network lifetime of our proposed ILP with the schemes described above by making a set of experiments. These experiments aim to study the effect of increasing, the number of sinks, the network size, the sinks sojourn times and the number of feasible sites, on the network lifetime.

In the first part of this section, we assume that all the sensor nodes are feasible sites. Figure 3 shows that in all the schemes and independently of the size of the network, the network lifetime increases notably when the number of sinks increases. Since the load traffic is distributed among a higher number of sinks, the nodes near the sinks forward less packets which leads to the reduction of energy consumption and lifetime improvement.

However in the Static scheme, the network lifetime is clearly shorter than in the other schemes with mobile sinks because nodes around the static sinks have to spend more energy to relay the packets of nodes farther away which leads them to drain their energy faster. Moreover, the first sensor dies relatively quickly in Periphery, Random and Cluster schemes comparing to the ILP scheme which manages to place optimally the sinks in the whole network.

The lifetime improvement percentages obtained in a 10x10 grid by deploying 3 mobile sinks according to the ILP solution are 68 % against 3 mobile sinks moving randomly, 99 % against 3 mobile sinks moving separately in different clusters, 100 % against 3 mobile sinks moving in the periphery and 230 % against 3 static sinks.

Figure 4 shows that the network lifetime decreases considerably when the network size increases. This is explained by the fact that there are more data traffics. 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. We investigated the network lifetime with different sinks sojourn times (see Table 1). The number of sinks was fixed to 3 and the number of sensors to 100. For Random, Periphery, Cluster and ILP schemes, the table shows that when the sojourn time of the sinks 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. In the following, the sinks can move only on the feasible sites of Figure 5. Each node in the 10x10 grid is localized with its identifier number. The nodes in cells colored in gray are chosen as feasible sites.

We varied the number of feasible sites from 10 to 52 as shown in Figure 6. The number of sinks was fixed to 3, the number of sensors to 100 and the period sojourn time to 30 days. We notice that the network lifetime improves considerably when the number of feasible sites increases. In fact, the more the number of sites is, the more the sinks to efficient locations move which leads to longer lifetime. Nevertheless, the choice of the feasible sites positions has a great influence on the network lifetime.

The Sinks Sojourn Times

We studied the pattern of the distribution of the sinks sojourn times at the different nodes. All the nodes of the grid can be feasible sites. Figures 7,[START_REF] Alsalih | Placement of multiple mobile base stations in wireless sensor networks[END_REF] The optimal sinks locations obtained for static sinks are the nodes which are almost at minimum distance i.e., number of hops to all other nodes. In Random scheme, the sinks sojourn time is variably distributed among all the nodes of the network. In the Periphery scheme, it is fairly distributed among the nodes in the perimeter of the network. For the Cluster scheme, the grid 10x10 was divided in 3 clusters 3x10, 3x10 and 4x10 in which the sinks move separately. We notice that the sink sojourns most of the times at the corners and the central grid area of its cluster. In the ILP scheme where the sinks move in the entire network, the same pattern is obtained, the sinks sojourn most of the times at the corners and the central grid area as shown in Figure 11.

Independently of the size of the network and the number of the sinks as shown in Figure 12 and 13, the optimal locations of the sinks according to ILP solution are the four corners of the grid, then the central grid area. The sojourn of the sinks at the central grid area can be explained as follows. If one of the sinks is located in the center of the grid it will have four neighbors within the transmission range. Contrarily, if it is located in the perimeter or the corner, it will have respectively three and two neighbors. Obviously, the more neighbors within the transmission range the sink has, the better the traffic load balanced among nodes is and the higher lifetime is. However, independently of where the sinks are located, the sensors in the corners drain less energy on forwarding packets than the sensors in the center which are always along a routing path to reach the sinks. For this reason, the sinks sojourn more at the nodes in the corners than the nodes in the central grid area in order to consume the residual energy of the "rich" sensors.

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 14(a 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 near the sinks 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 14(a), we observe that higher percentage of energy consumption is concentrated around three nodes in the grid which are the locations of the static sinks whereas the other 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 Figure 15(a).

In the Cluster scheme as shown in the Figure 16, the energy consumption is only balanced among the nodes of every cluster and not in the whole network. This is because of the restriction of sinks mobility to theirs clusters.

Figure 17(a) shows that Random scheme results in a better However, ILP scheme balances almost perfectly the energy consumption among the nodes. In fact, the majority of the nodes depleted their energy at the same time except the four corners as shown in Figure 18(a).

The distribution of the residual energy at each sensor node in 10x10 grid with 3 mobiles sinks was also studied (see Figures 14(b With static sinks, the majority of sensors have more residual energy at the end of network lifetime than the schemes with mobile sinks which have their initial energies more depleted at the lifetime end.

For the ILP scheme, sensor nodes have less residual energy 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 Cluster scheme, the movement of the sinks is restricted to their own clusters. So, this approach prevents to have global view of the entire network.

The ILP scheme results in a better distribution of residual energy among the nodes compared to Cluster, Periphery, Random and Static schemes. The results show that the percentages of the residual energy that remain unused at the network lifetime end for Static, Periphery, Random, Cluster and ILP schemes are respectively 71 %, 45 %, 31 %, 31 %, 3 %. Moreover, the number of sensors which have more than 50 % of their initial energies left at lifetime end is 80, 36, 20, 27 and 4 respectively for Static, Periphery, Random, Cluster and ILP schemes It is remarkable in the ILP scheme, as shown in the Figure 18(b), that the sensor nodes in the corners have higher energy at the end of network lifetime than the others nodes. This can be explained by the fact that they do not drain their energy in forwarding neighbor's data in addition to their own data.

Moreover, we observe that at the end of network lifetime the distribution of residual energy in the grid is more balanced among the nodes when the number of sinks increases (See Figure 19). The use of more sinks results in the reduction of the average path length between the sensors and sinks thus enabling to achieve less traffic load to the nodes and increased network lifetime. These results are interesting since they are not pure theory. We tried to approach realistic buildings deployment parameters in our assumptions and especially with sinks that can not move frequently.

Conclusion and future Work

In this paper, we have explored the problem of positioning multiple mobile sinks in wireless sensor networks inside buildings, in order to avoid the energy hole problem and 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, mobile sinks moving in the periphery of the network, mobile sinks moving randomly and mobile sinks moving separately in different clusters was made. Relocating sinks with our solution and using realistic parameters assumptions results in the sensor 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 network with hundred sensors are almost 99 % against 3 mobile sinks moving separately in different clusters and almost 230 % 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 in the central grid area and in the corners. This corresponds to very interesting feasible sites in buildings because the sinks can be easily relocated in the corridors which are often in the center of the buildings and provided with power and Internet access.

The weakness of the proposed approach is the scalability problem in networks with thousands of sensors due to the high ILP resolution complexity. In order to adopt this solution in a large scale wireless sensor network with more than hundreds of sensors, the network might be divided in several sensor sub-networks which will be deployed in the each part of the building. More than one sink can then be placed inside each zone to collect the information of the in-door environment. To implement the solution in a real environment and apply the model in real time conditions, technicians will be in charge of relocating the mobile sinks in the open areas of the buildings after long periods (i.e., months).

In our future work, we intend to improve the proposed ILP by including parameters and constraints that model more realistic requirements of an indoor environment (e.g., collisions) and take into account the energy consumption of sensing and data processing. We envisage also to introduce optimization in data routing by considering relevant metrics like latency, control overhead.

Figure 1 .

 1 Figure 1. 10x10 Grid of cells with 100 sensors

Figure 2 .

 2 Figure 2. Path selection

Figure 3 .

 3 Figure 3. The network lifetime

Figure 4 .

 4 Figure 4. The network lifetime in different network size

Figure 5 .Figure 6 .

 56 Figure 5. The network with different number of feasible sites

  , 9, 10, and 11 show the sojourn times of three sinks in 10x10 grid for respectively Static, Periphery, Random, Cluster and ILP schemes.

Figure 7 .Figure 8 .Figure 9 .

 789 Figure 7. Sinks sojourn times at the different nodes of 10x10 grid network with Static scheme

Figure 10 .Figure 11 .

 1011 Figure 10. Sinks sojourn times at the different nodes of 10x10 grid network with Cluster scheme

Figure 12 .

 12 Figure 12. ILP sinks sojourn times at the different nodes of 8x8 grid network

  ), 15(a), 17(a), 16(a) and 18(a). A light color means a higher percentage of energy consumption.

Figure 14 .

 14 Figure 14. Static scheme in 10x10 grid network

Figure 15 .

 15 Figure 15. Periphery scheme in 10x10 grid network

Figure 16 .Figure 17 .

 1617 Figure 16. Cluster scheme in 10x10 grid network

Figure 18 .

 18 Figure 18. ILP scheme in 10x10 grid network

  ), 15(b), 17(b), 16(b) and 18(b)).

Figure 19 .

 19 Figure 19. Residual energy distribution of ILP scheme in 5x5 grid network with increasing number of sinks

Table 1 .

 1 The network lifetime (periods) with different sinks sojourn times

	Sinks sojourn times (days)	ILP	Cluster Periphery Random
	10	7774	3900	3892	4686
	20	7773	3899	3892	4661
	30	7772	3899	3891	4595
	40	7771	3898	3891	4558
	50	7770	3898	3891	4540
	60	7769	3897	3890	4510


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

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

Sinks Mobility Strategy in IPv6-based WSNs for Network Lifetime Improvement

Keywords: IPv6 based-WSNs, RPL, Mobile sinks, Network lifetime

This paper investigates the sinks mobility in IPv6based wireless sensors networks and specially in the new IETF proposed protocol RPL (Routing Protocol for Low power and Lossy Networks). We also show that even the mobility of sinks is not an explicit design criteria, the use of mobile sinks improves the network lifetime. In this work, we propose a new distributed and weighted moving strategy for sinks in RPL. We compared our proposed mobility approach with different others strategies. The results show that our proposed mobility approach notably balances the network load which leads to a significant network lifetime gain in large scale network.

I. INTRODUCTION

Recently, significant studies have been made to enable the convergence of sensor networks with IP world and the connectivity of the smart objects to Internet. In fact, The standardization of IEEE 802.15.4 [1] provided devices with low cost, low power, low data rate and low bandwidth. The IETF Working Group 6LoWPAN (IPv6 over Low power Wireless Personal Area Networks) proposed the RFC 4944 [START_REF] Montenegro | Transmission of IPv6 packets over IEEE 802.15.4 networks[END_REF] to enable IPv6 packets to be carried over IEEE 802.15.4. The IETF Working Group ROLL (Routing Over Low power and Lossy networks) is currently designing a routing protocol named RPL [START_REF] Winter | RPL: IPv6 routing protocol for low power and lossy networks[END_REF] (IPv6 Routing Protocol for Low power and lossy networks). This protocol targets IPv6-based wireless sensor networks with thousands of sensors and supports a variety of applications including industrial, urban, commercial, home buildings, etc. RPL builds and maintains Directed Acyclic Graphs (DAGs) topologies rooted towards one or many sinks (DAG ROOTs). The data transmitted by the sensors follow only the DAG links.

Designing a routing protocol for multi-hop IP-based WSNs and specially those that are characterized by many-to-one traffic patterns is a very challenging problem. In fact, such networks are formed by a large number of tiny batteryoperated sensors which have a limited and non-renewable energy supply. Furthermore, the sensors behave at the same time as source nodes by generating data to be transmitted to the sinks and as relay nodes by forwarding the data of nodes farther away. Thus, the sensors near the sinks are more likely to use up their energy much faster than distant nodes because they carry heavy traffic. Therefore, the hot spot problem occurs and thus prevents farther nodes to relay their data to the sinks. Consequently, areas of the network are left completely unmonitored and the network lifetime ends prematurely. Although the sinks mobility in RPL is not an explicit design criteria, moving the sinks even infrequently can mitigate this hot-spot problem and increase the network lifetime. Nevertheless, the mobility requires careful handling to limit the overhead of the topology management and ensure that the increased control traffic can not reduce the energy saving obtained by sinks mobility.

The sinks mobility exists in many realistic applications. An example for this can be sensors deployed inside buildings where they are expected to operate for several years without replacing or recharging their batteries. In this case, it may be preferable to simply relocate the sinks or virtually moving them by switching them on or off.

In this paper, we propose a distributed and weighted strategy which improves the performance of RPL in terms of network lifetime by moving the sinks towards the leaf nodes. The simulation results demonstrate that by introducing the sinks mobility in RPL according to our proposed approach, the energy consumption is more balanced among the sensors which leads to a significant increase of network lifetime. To the best of our knowledge, our work is the first to investigate the sinks mobility in RPL for IPv6-based wireless sensor networks.

The rest of this paper is organized as follows. In Section 2, a related work on sinks mobility in WSNs is reviewed. In Section 3, the network model including the major assumptions is described. In Section 4, a brief presentation of RPL protocol is provided. Section 5 discusses the integration of sinks mobility in RPL and explains our proposed moving strategy to improve the network lifetime. Section 6 evaluates the performance of the proposed approach and presents the simulation results. Section 7 concludes the paper.

II. RELATED WORK

The lifetime of WSNs can be extended by moving the sinks. Several sink mobility strategies exist in the literature and can be classified into three categories. Mobile sink may move in a fixed path [START_REF] Luo | Joint mobility and routing for lifetime elongation in wireless sensor networks[END_REF], may take a random path [START_REF] Shah | Data mules: Modeling a three-tier architecture for sparse sensor networks[END_REF] or may move in optimal locations in terms of network lifetime or energy conservation. Most of works based on sink mobility suggest to move a single sink to improve the network lifetime [START_REF] Wang | Exploiting sink mobility for maximizing sensor networks lifetime[END_REF][7] [START_REF] Akkaya | Sink repositioning for enhanced performance in wireless sensor networks[END_REF]. But, few studies focused on the mobility of multiple sinks. To find the optimal placement of multiple mobile sinks, some works formulated 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][10] [START_REF] Saad | Towards an optimal positioning of multiple mobile sinks in WSNs 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 LP based solutions is that they are centralized and hard to compute in networks with thousands of sensors due to their high resolution complexity. Another way to determine the positions of mobile sinks in the third category is to use algorithms. In [START_REF] Vincze | Deploying multiple sinks in multi-hop wireless sensor networks[END_REF], the algorithm, based on iterative clustering, minimizes the distance 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 that the difference between the maximum and the minimum residual energy of nodes is minimized. In [START_REF] Saad | Towards an efficient positioning of mobile sinks in wireless sensor networks inside buildings[END_REF], the algorithm moves the sinks towards the distant nodes which have the highest number of hops to reach the nearest sink. Other algorithms 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][17], the sinks move towards the zones of nodes with highest residual energy.

The majority of proposed moving strategies are centralized or assume the availability of global information (i.e, residual energy, the location of all sensors). The knowledge of all network parameters is energy-consuming because it needs to be collected which leads to non scalability of these strategies in large scale networks. Contrary to previous works, this paper is aimed to focus on a totally distributed and autonomous strategy without an explicit global network knowledge in large scale IPv6-based WSNs using RPL as protocol.

III. NETWORK MODEL

We consider a wireless sensor network composed of static sensor nodes and mobile sinks. We made the following assumptions for the network model.

-We assume N sensors distributed in a bi-dimensional grid network. -The 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). -The sinks are moving in the network (really or virtually) from one node to another one. -The sinks stay at a certain position for at least a certain duration of time. At the end of this duration, they can change their locations. -A time-driven sampling application of data collection is considered -Each sensor regularly generates the same amount of data and no aggregation of data is made. -The network lifetime is defined as the time until the first sensor dies (i.e, it uses up its residual energy). Despite the fact that there are many definitions of the network lifetime, the most used is this one because the death of a node is soon followed by the death of its neighbors. -Since the energy spent in the communication is the most dominant, only the energy consumption for transmitting and receiving data were considered.

-The protocol used by the sensors to transmit their data to the sinks is the routing protocol RPL.

IV. RPL: IPV6 ROUTING PROTOCOL FOR LOW POWER AND LOSSY NETWORKS

RPL [START_REF] Winter | RPL: IPv6 routing protocol for low power and lossy networks[END_REF] is a routing protocol designed for low power and lossy networks and targets IPv6 based wireless sensor networks with thousands of constrained resources nodes. The basic idea of RPL is that the nodes organize themselves by forming a Destination Oriented DAGs (DODAGs) rooted towards one sink (DAG ROOT) identified by an unique identifier DODAGID. The DODAGs are optimized according to an objective function identified by an Objective Code Point (OCP) which indicates the constraints and the metrics in use (e.g, hop count, latency, expected transmission count, energy). Each node is assigned a rank which determines its relative position in the DODAG. RPL constructs and maintains the upwards routes of the DODAGs by the transmission of DODAG Information Object (DIO) messages. DIO messages contains several information (e.g., RPL INSTANCE, DODAGID, RANK, DODAGVersion-Number). The transmission of DIO messages by a node is regulated by a trickle timer [START_REF] Levis | The trickle algorithm[END_REF] to suppress redundant control messages. Each node monitors DIO messages of its neighbors before to join a DODAG. Then, it selects a DODAG parent set from its neighbors according to the cost they advertise and eventually computes its own RANK. Destination Advertisement Object (DAO) messages are aimed to maintain downward routes and they are only used for applications that require point-to-multipoint and point-to-point traffic. Sending a packet to the DAG ROOT consists in selecting the preferred parent with lower rank. To repair the topology of the DODAG and allow nodes to join a new position, the DODAG ROOT increments the DODAGVersionNumber to create a new DODAGVersion. This operation is called global DAG repair.

V. SINKS MOBILITY IN RPL

The main goal of our work is to focus on how to integrate sinks mobility in RPL to improve the lifetime of IPv6-based WSNs characterized by many-to-one traffic patterns. Random sink mobility is not possible in practice and may threaten the network lifetime. The fixed path mobility lacks of flexibility. Autonomous mobility when the sinks take decision according the circumstances at that time is more beneficial to balancing energy. That is why, we focus on a totally distributed and autonomous moving strategy of sinks in RPL.

The lifetime T of a sensor node depends on the energy available at the sensor (e 0 ) and the energy consumption of the node at each time (e c ) [START_REF] Wang | Using mobile relays to prolong the lifetime of wireless sensor networks[END_REF].

T = e 0 e c ( 1
)
e c = f i (e T + e R ) (2)
Where f i is the average number of packets flowing out from the sensor node i, e T and e R are respectively the unit of energy consumption for transmitting and receiving one packet in each time. This means that the more the sensor has available energy, the longer its lifetime is.

Furthermore to extend the network lifetime, the energy consumption of the whole network should be minimized. In multi-hop networks, the less the number of hops between the sensor and the sink is, the less the energy consumption is. In fact, the energy cost of transmitting a packet to the sink (E pkt ) is linearly proportional to the number of hops the packet has to travel denoted here as h [START_REF] Vincze | Deploying multiple sinks in multi-hop wireless sensor networks[END_REF]. Let E 1 be the energy cost to send a packet in 1-hop distance.

E pkt ∼ h E 1 (3)
Therefore to increase the lifetime, the number of hops between the sensors and the sink should be reduced. However, the number of hops depends on the routing protocol, the sensor nodes configuration, density and the sinks positions. The manipulation of the sensors density and configuration is not always possible. Therefore one way to reduce the number of hops without changing the protocol is to optimize the configuration of sinks by moving them. In addition to the sensor energy and the number of hops, the number of neighbors is another parameter influencing the network lifetime. In fact, the more the sinks have neighbors, the more the traffic load is balanced among nodes and the longer network lifetime is.

Our proposed moving strategy (RPL Weight) relies on these three parameters which are locally available at each sensor node. Notice that in RPL each node can determine its number of hops to reach the sink from the DIO messages advertised by its parents. Let h k i be the number of hops from sensor node i to its DAG ROOT at position k, e i be the residual energy of sensor node i and b i be the number of its 1-hop neighbors. For each leaf node of the DODAG, we define a weight w i which is a function of the parameters h k i , e i and b i .

w i = f (h k i e i b i ) (4)
The exact calculation of the weight is as follows.

w i = βh k i e i + γb i (5)
β and γ are coefficients of normalization. They are introduced to mitigate the effect of scale since the units of measurement are different.

Moving the sinks really or virtually in RPL involves a change of the address assigned to the sink node (i.e., DODAGID). Therefore, such mobility can be seen as the case of having many DAG INSTANCEs containing different DAG ROOTs. In order to make the sinks mobility possible in RPL, we define the period T instance which is the period of creation of a new instance and corresponds to the moment when the sinks are allowed to move in a new position among the nodes.

The period T instance is a multiple of the period of the DAG repair denoted here as T version to mitigate the overhead of the control messages generated by the sinks mobility.

T instance = p T version p ∈ N * (6)
Where p is the instance period multiplier. The process of sinks relocation needs three phases: 1) During the T instance period, each node monitors the RANKs advertised by its neighbors belonging to the same DODAG. When, it does not hear a node with the rank higher than itself, it considers itself as a leaf node. 2) Before the end of T instance , each leaf node sends Data packet by piggybacking its weight w i . 3) At the beginning of a new T instance , each DAGROOT determines the leaf node with highest weight and move there.

VI. SIMULATION RESULTS Simulations were performed on the WSnet simulator [20].

A basic version of RPL with three mobile sinks was implemented. The Chipcon radio CC1100 with 250 kbps data rate and the IEEE 802.15.4 MAC and PHY layer specifications were used. The current consumption values in transmit and receive mode were respectively chosen equal to 16.9 mA and 16.4 mA [21]. The sensor transmission range r was fixed to 10 m. All the data packets generated by the sensors were of size 127 bytes and were destined to the DAG ROOTs. The packets were sent every one minute according to a Constant Bit Rate (CBR). The hop count was used as a metric to build the DODAGs. The trickle time interval for emitting DIO messages was initially fixed to 1 second and then changed exponentially over the simulation time as specified in [START_REF] Levis | The trickle algorithm[END_REF]. Since the traffic supported in the application is convergecast to the sink, only upwards routes were considered and the DAO messages advertisement was configured to be entirely disabled.

To show the benefit of sinks mobility, we evaluated the performance of RPL by making a comparative study with different mobility strategies:

1) RPL Static 2) RPL Random 3) RPL Energy 4) RPL Weight 5) RPL ILP In strategy (1), the sinks are static. In strategy (2), the sinks are moving randomly among the sensor nodes. In strategy (3), the sinks are moving towards the nodes with the highest energy. The strategy (4) is our proposed approach as presented in Section V. The sinks are moving towards the leaf node with the highest weight. In strategy (5), the sinks are moving according to the optimal solution computed with an Integer Linear Program detailed in [START_REF] Saad | Towards an optimal positioning of multiple mobile sinks in WSNs for buildings[END_REF]. This latter strategy will be used only in small networks because its is hard to apply it in large scale network due to the high resolution complexity.

In the following sections, we focus on the performance of RPL with mobile sinks by analyzing the network lifetime, the residual energy and the amount of control messages.

A. The network lifetime

We simulated RPL and observed the effect of sinks mobility on the network lifetime.

Table I shows the percentage of the lifetime gap of the moving strategies with respect to the optimal solution computed by the ILP in small scale networks. Our proposed strategy RPL Weight achieves the closest network lifetime to the optimum comparing to other strategies. The gap of our proposed approach is about 22% and 25.5% respectively in networks with 16 and 25 nodes. This gap can be considered as acceptable since the proposed mobility strategy is totally distributed and does not need a global information of all sensor nodes. This straightforwardly proves that using mobile sinks is more beneficial in large scale networks. It is also observable that the lifetime gain obtained by our proposed strategy is better than the other strategies independently of the size of the network. Moreover, the lifetime improvement induced by our approach is about 24% in network with 1600 nodes.

Figure 2 displays the lifetime improvement achieved by the moving strategies with respect to RPL Static strategy for different values of initial energy of the sensors in network with 1600 nodes. As expected, the lifetime gain is always higher than the others approaches and varies between 23 to 25 %.

Figure 3 shows the effect of increasing the period T instance and varying the period of DAG repair on network lifetime of the two strategies RPL Weight and RPL Static. When the period T instance increases, the network lifetime of RPL weight decreases slightly. This can be explained by the fact that long sojourn time of sinks at certain locations causes less sinks Fig. 2. Lifetime improvement with different initial energies of sensors movements. So, the sensors near the sinks consume more energy which leads to shorter lifetime. We notice also that short periods of DAG repair have an influence on network lifetime because they generate higher rate of control packets which minimizes the network lifetime. The percentage of energy left unused at the end of network lifetime in mobile sinks strategies is notably lower than in the case of static sinks. This is due to the fact that the sinks mobility changes the nodes acting as relays frequently and leads to balanced energy consumption among nodes. Nevertheless, our proposed strategy results in the best distribution of the available energy on the sensors since it leaves the smallest amount of unused energy at the end of network lifetime.

C. The packets overhead

In the Figure 5, we analyzed the amount of data packets transmitted (including forwarded data packets) and the ICMPv6 control packets (DIO messages) transmitted by each node. When the sinks are static, the nodes near the sinks (e.g, node id 778) have more data traffic than others nodes because they have to transmit their own data in addition to data of nodes farther away. Concerning leaf nodes (e.g, node id 1401), the amount of data packets transmitted is smaller than that of nodes in the middle or close to the sink. This is because they do not have to act as forwarding nodes. By moving the sinks according to our weighted approach, the nodes playing the role of relay nodes change and the data traffic becomes more balanced among the nodes. As shown in the Figure 5, the majority of nodes have a comparable amount of data packets transmission. Moreover, the control overhead is very small in comparison to data packets. It is also not highly increased in spite of the mobility of sinks. This can be explained by the fact that the sinks move only during the periods of DAG repair. In this paper, we investigated the sinks mobility in the new protocol RPL. We also proposed an autonomous and distributed moving strategy to extend the lifetime of large scale IPv6-based WSNs. Our proposed approach moves the sinks towards the nodes with the highest weight. This weight is a function of three parameters influencing the network lifetime: residual energy, number of neighbors and number of hops. This approach does not need a global knowledge and prevents from collecting information from all the sensors since it uses only leaf nodes of the DODAGs. Furthermore, to mitigate the overhead of the control messages, the sinks are allowed to change their location only during periods of global DAG repair. We evaluated the performance of our proposed strategy by simulation in networks with thousands of sensors and compared it with others strategies. The results show that it extends significantly the network lifetime. The gain achieved in a network with 1600 sensors and 3 mobile sinks is about 24% with the respect to the static strategy. Nonetheless, longer network lifetime can be achieved in RPL if the overhead of DIO messages were less important and better controlled by well choosing the parameters of the trickle timer.

In our future work, we intend to improve the weight function and implement RPL with mobile sinks in real-life deployment topologies. We would like also to study its performance with different traffic patterns using a variety of metrics in DAG construction and mechanisms of DAG repair.

Fig. 1 .

 1 Fig. 1. Lifetime improvement with different network sizes

Fig. 3 .

 3 Fig. 3. Lifetime with different periods of T instance

Fig. 4 .

 4 Fig. 4. Residual energy at network lifetime end

Fig. 5 .

 5 Fig. 5. Packets transmitted : Control packets and Data packets (including forwarded data)

  The rank increases down et decreases up. RPL is based on the concept of DAG INSTANCE which is a set of multiple DODAGs. A node can be a member of multiple DAG INSTANCEs but can belong to at most one DODAG per DAG INSTANCE.

TABLE I NETWORK

 I LIFETIME GAP RELATIVELY COMPARED TO ILP SOLUTION

	Strategy	4x4 sensors 5x5 sensors
	RPL Static	44.46 %	45.20 %
	RPL Energy	31.80 %	34.69 %
	RPL Random	28.75 %	33.26 %
	RPL Weight	22.00 %	25.50 %