View
219
Download
0
Category
Preview:
Citation preview
Maximisation de la duree de vie des reseaux de capteurs
sans fil heterogenes
A. Rossi⋆, A. Raiconi†, R. Cerulli†, M. Gentili†, M. Sevaux⋆
⋆ Universite de Bretagne-Sud, Lab-STICC, Lorient, France
andre.rossi,marc.sevaux@univ-ubs.fr
† Universita di Salerno - Dipartimento di Matematica, Salerno, Italia
araiconi,raffaele,mgentili@unisa.it
27 fevrier 2014
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 1 / 15
Plan
1 Motivations
2 Illustration of a group
3 Directional sensor units
4 Mathematical model
5 Global strategy of the column generation algorithm
6 Preliminary results
7 Conclusion
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 2 / 15
Motivations
Multiphysics requirements
Fire detection ⇒ light, temperature and smoke Water quality ⇒ pH, temperature, chemical and biological measures Mental stress detection ⇒ heartbeat, respiratory frequency
Embedded system technology allows for multiphysic sensor nodes A sensor node is equipped with a single battery, and multiple sensor
units operating on that battery
In this work we consider the joint use of three types of sensor nodes Sensor nodes in N1 are equipped with a omnidirectional sensor unit Sensor nodes in N2 are equipped with a directional sensor unit Sensor nodes in N12 are equipped with an omnidirectional and a
directional sensor unit
Objective: Maximize the network lifetime
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 3 / 15
Classical approach
A group is a set of sensors such that: For all targets, there exist an omnidirectional sensor unit and a
directional sensor unit in the group that can cover it
Group j is used tj units of time (tj is a decision variable)
The network lifetime is
c∑
j=1
tj
Enumerating all the groups is generally unpracticable (andunnecessary) ⇒ Column generation
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 4 / 15
Directional sensor units
Each sensor has a given sensing angle ϕ
Each active sensor has a working direction θ in [0, 2π)
0
π
9
π
4
5π8
7π8
16π9
15π8
1
2
3
4
5
6si
A finite set of directions is sufficient (at most one per target)
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 6 / 15
Directional sensor units
Each sensor has a given sensing angle ϕ
Each active sensor has a working direction θ in [0, 2π)
0
π
9
π
4
5π8
7π8
16π9
15π8
1
2
3
4
5
6si
A finite set of directions is sufficient (at most one per target)
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 6 / 15
Directional sensor units
Each sensor has a given sensing angle ϕ
Each active sensor has a working direction θ in [0, 2π)
0
π
9
π
4
5π8
7π8
16π9
15π8
1
2
3
4
5
6si
A finite set of directions is sufficient (at most one per target)
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 6 / 15
Directional sensor units
Each sensor has a given sensing angle ϕ
Each active sensor has a working direction θ in [0, 2π)
0
π
9
π
4
5π8
7π8
16π9
15π8
1
2
3
4
5
6si
A finite set of directions is sufficient (at most one per target)
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 6 / 15
Directional sensor units
Each sensor has a given sensing angle ϕ
Each active sensor has a working direction θ in [0, 2π)
0
π
9
π
4
5π8
7π8
16π9
15π8
1
2
3
4
5
6si
A finite set of directions is sufficient (at most one per target)
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 6 / 15
Directional sensor units
Each sensor has a given sensing angle ϕ
Each active sensor has a working direction θ in [0, 2π)
0
π
9
π
4
5π8
7π8
16π9
15π8
1
2
3
4
5
6si
A finite set of directions is sufficient (at most one per target)
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 6 / 15
Directional sensor units
A normalized direction is associated with each target
1
2
3
4
5
6si
Non-normalized direction
A (normalized) direction is dominated if the targets it covers are aproper subset of the targets covered by another direction
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 7 / 15
Directional sensor units
A normalized direction is associated with each target
1
2
3
4
5
6si
Non-normalized direction
A (normalized) direction is dominated if the targets it covers are aproper subset of the targets covered by another direction
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 7 / 15
Directional sensor units
A normalized direction is associated with each target
1
2
3
4
5
6si
1
2
3
4
5
6si
Non-normalized direction Normalized direction
A (normalized) direction is dominated if the targets it covers are aproper subset of the targets covered by another direction
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 7 / 15
Directional sensor units
A normalized direction is associated with each target
1
2
3
4
5
6si
1
2
3
4
5
6si
Non-normalized direction Normalized direction
A (normalized) direction is dominated if the targets it covers are aproper subset of the targets covered by another direction
1
2
3
4
5
6si
Dominated direction
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 7 / 15
Directional sensor units
A normalized direction is associated with each target
1
2
3
4
5
6si
1
2
3
4
5
6si
Non-normalized direction Normalized direction
A (normalized) direction is dominated if the targets it covers are aproper subset of the targets covered by another direction
1
2
3
4
5
6si
1
2
3
4
5
6si
Dominated direction Non-dominated direction
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 7 / 15
Group encoding
Sensor nodes in N1 are equipped with an omnidirectional sensor unit
1
Sensor nodes in N2 are equipped with a single directional sensor unit
or0
0
1
0
Sensor nodes in N12 have both sensor units
or or0
0
1
0
1
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 8 / 15
Group encoding
Power consumption of node i ∈ N1 (omnidirectional sensor) p1xi ,j where p1 is the power consumption of an omnidirectional sensor
Power consumption of node i ∈ N2 (directional sensor)
p2
σi∑
q=1
xgi+q,j with
σi∑
q=1
xgi+q,j ≤ 1
where p2 is the power consumption of a directional sensor
Power consumption of node i ∈ N12 (omnidirectional and directionalsensor)
p1xgi+1 + p2
σi∑
q=2
xgi+q,j with
σi∑
q=2
xgi+q,j ≤ 1
Where σi is the number of modes under which node i can be used
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 9 / 15
Mathematical model
Maximizec
∑
j=1
tj (1)
c∑
j=1
σi∑
q=1
pgi+qxgi+q,j
tj ≤ bi ∀i ∈ 1, . . . , n [πi ] (2)
tj ≥ 0 ∀j ∈ 1, . . . , c (3)
Maximize 1−
n∑
i=1
σi∑
q=1
pgi+qxgi+q,c+1
πi (4)
1 ≤∑
i∈C1k
xi ,c+1 ∀k ∈ 1, . . . ,m (5)
1 ≤∑
i∈C2k
xi ,c+1 ∀k ∈ 1, . . . ,m (6)
xi ,c+1 ∈ 0, 1 ∀i ∈ 1, . . . , gn + σn (7)
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 10 / 15
Global strategy of the column generation algorithm
The subproblem is a difficult problem to be solved repeatedly
A memetic algorithm is used for generating multiple groups at eachiteration
It is faster than solving the ILP formulation of the subproblem
When no profitable group is found, the ILP is solved as a last resortmethod
This is a hybrid exact approach
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 11 / 15
Global strategy of the column generation algorithm
Start
Master problem
Subproblem with MA
Attractive groupfound?
Subproblem with ILP
Attractive groupfound?
End
No
No
No
Yes
Yes
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 12 / 15
Preliminary results
n1 n2 n12 m R1 R2 ϕ LT CPU
30 30 60 24 100 150 π
2 14.0333 5.6530 30 60 24 100 150 π
4 13.8617 23.1830 30 60 39 100 150 π
2 10.77 1.9130 30 60 39 100 150 π
4 10.77 19.54
40 40 40 24 100 150 π
2 11.48 1.540 40 40 24 100 150 π
4 11.48 6.340 40 40 39 100 150 π
2 10.71 1.8440 40 40 39 100 150 π
4 10.71 3.58
80 80 80 48 100 150 π
2 7.25 1.5180 80 80 48 100 150 π
4 7.25 2.7680 80 80 79 100 150 π
2 9.94 3.6380 80 80 79 100 150 π
4 9.94 6.02
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 13 / 15
Preliminary results
The memetic algorithm accelerates convergence significantly
Except when n1 = 30, the lifetime in our instances is limited by theomnidirectional coverage requirement
Problem is more difficult to solve when ϕ is small
For very large networks, the proposed approach can be turned into aheuristic by stopping when the memetic algorithm does not find anyprofitable group
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 14 / 15
Conclusion and future works
Sensor nodes with multiple nodes can be handled efficiently
Work is still under progress
More than 2 sensor units
Consumption profiles
Adjustable sensing/communication ranges
Partial coverage
Multi-hop communication
Rossi et. al. (UBS) Reseaux de capteurs heterogenes 27 fevrier 2014 15 / 15
Recommended