Upload
vuonghanh
View
219
Download
2
Embed Size (px)
Citation preview
Conception de réseaux de capteurs sans
fil à l’aide
de structures combinatoires.
Djelloul Mameri Fatiha Bendali Jean Mailfert
Université Blaise Pascal. Laboratoire LIMOS, UMR 6158 CNRS.
Comité de thèse 23 Juin 2011 au LAMSADE, Université Paris
Dauphine.1/31 31
Plan de travail
1 Introduction
2 Topologies et organisation dans le réseau de capteurs sans fil
3 Structures combinatoires sur les réseaux de capteurs
4 Résultats théoriques sur le WCIS
5 Heuristique pour le problème du MWCIS
6 Perspectives
2/31 31
Plan de travail
1 Introduction
2 Topologies et organisation dans le réseau de capteurs sans fil
3 Structures combinatoires sur les réseaux de capteurs
4 Résultats théoriques sur le WCIS
5 Heuristique pour le problème du MWCIS
6 Perspectives
2/31 31
Plan de travail
1 Introduction
2 Topologies et organisation dans le réseau de capteurs sans fil
3 Structures combinatoires sur les réseaux de capteurs
4 Résultats théoriques sur le WCIS
5 Heuristique pour le problème du MWCIS
6 Perspectives
2/31 31
Plan de travail
1 Introduction
2 Topologies et organisation dans le réseau de capteurs sans fil
3 Structures combinatoires sur les réseaux de capteurs
4 Résultats théoriques sur le WCIS
5 Heuristique pour le problème du MWCIS
6 Perspectives
2/31 31
Plan de travail
1 Introduction
2 Topologies et organisation dans le réseau de capteurs sans fil
3 Structures combinatoires sur les réseaux de capteurs
4 Résultats théoriques sur le WCIS
5 Heuristique pour le problème du MWCIS
6 Perspectives
2/31 31
Plan de travail
1 Introduction
2 Topologies et organisation dans le réseau de capteurs sans fil
3 Structures combinatoires sur les réseaux de capteurs
4 Résultats théoriques sur le WCIS
5 Heuristique pour le problème du MWCIS
6 Perspectives
2/31 31
Réseau de capteurs
(Station de base): source
Capteur
Evénement
• Capteurs/traitement de données physiques ⇒ Mémoire et capacitéde calcul limitées.
• Transmission sans fil ⇒ Faible portée radio.
• Energie (batterie) ⇒ Energie limitée.
3/31 31
Applications
Surveillance environnementale
Moniteur d'inventaire
Industrie
Militaires
Domotique
Médicale
4/31 31
Topologies et organisation dans le réseau
de capteurs sans fil
Choix des topologies
5/31 31
Topologies et organisation dans le réseau
de capteurs sans fil
Station de base
Choix des topologies
Plate
6/31 31
Topologies et organisation dans le réseau
de capteurs sans fil
Hiérarchique
Station de base
Choix des topologies
Plate
Station de base
Cluster 1 Cluster 2
7/31 31
Modélisation de la communication entre
deux capteurs
Puissance nécessaire pour une transmission d’un nœud i à un nœud j
C(i , j) = α.d(i , j)β + γ (1)
Où d(i , j) est la distance entre i et j ; α > 0; γ ≥ 0; β ∈ [2, 5].
ji
P(i)
P(j)
d(i,j)
8/31 31
Modélisation de la communication entre
deux capteurs
Puissance nécessaire pour une transmission d’un nœud i à un nœud j
C(i , j) = α.d(i , j)β + γ (2)
Où d(i , j) est la distance entre i et j ; α > 0; γ ≥ 0; β ∈ [2, 5].
ji
P(i)
P(j)
d(i,j)
ji
Echange bidirectionnel entre i et j
C(i,j)<= min{P(i),P(j)}ssi
ji
9/31 31
Structures combinatoires et réseau sans fil
Définition: Ensemble dominant (DS)
G = (V , E ); S ⊂ V .
• S est un ensemble dominant de G si ∀v ∈ V \S, ∃u ∈ S tel que(u, v) ∈ E .
G=(V,E) S
DS
10/31 31
Structures combinatoires et réseau sans fil
Définition: Ensemble dominant connexe (CDS)
G = (V , E ).
• Un ensemble dominant S de G est connexe si le grapheGS = (S, E (S)) est connexe.
E(S)G=(V,E) S
CDS
11/31 31
Structures combinatoires et réseau sans fil
Définition: Ensemble dominant faiblement connexe (WCDS)
G = (V , E ).
• Un ensemble dominant S de G est faiblement connexe si le grapheGS = (V , E (S) ∪ [S, V \S]) est connexe.
E(S)
[S,V\S]
G=(V,E) S
WCDS
12/31 31
Structures combinatoires et réseau sans fil
Définition: Indépendant (IS) et indépendant maximal (MIS)
G = (V , E ); S ⊂ V .
1 S est un indépendant de G si aucune arête de E ne relie deuxsommets de S.
2 Un indépendant S de G est maximal si aucun indépendant de G nele contient strictement.
MIS
[S,V\S]SG=(V,E)
13/31 31
Structures combinatoires et réseau sans fil
Définition: Indépendant faiblement connexe (WCIS)
• Un indépendant S de G est faiblement connexe si le grapheGS = (V , [S, V \S]) est connexe.
S
[S,V\S]
MISG =(V,[S,V\S]) non connexe G =(V,[S,V\S]) connexe
WCIS
SS
14/31 31
Structures combinatoires et réseau sans fil
G=(V,E)
CDS WCDS
E(S)S
[S,V\S]
WCIS
15/31 31
Comparaison ensembliste
DS
WCDS
MIS
IS
G=(V,E) ; S = une partie de
P(V)
P(V)
16/31 31
Motivations pour la structure WCIS
WCIS transformé en CDS
Li. Yingshu, M.T Thai, W. Feng, C.W. Yi, P.J Wan and D.Z. Du, Ongreedy construction of connected dominating sets in wireless networks,Wireless Communications and mobile computing, (2005) 5:927-932.
WCIS transformé en CDS
M. Min, C.X. Huang, S. C.-H. Huang, W. Wu, H. Du, and X. Jia,Improving construction of connected dominating set with Steiner tree inwireless sensor networks, Journal of Global Optimization, (2006) 35:111-119.
17/31 31
Problème de décision associé au MWCISP
Problème : (WCISD)
Instance : G = (V , E ) un graphe non orienté connexe et k un
entier;
Question : G contient-il un WCIS de taille au plus k ?
Théorème
WCISD est NP-Complet.
Preuve
MISD�WCISD.
18/31 31
Problème de décision associé au s-MWCISP
Problème : (s-WCISD)
Instance : G = (V , E ) un graphe non orienté connexe, s ∈ V
et k un entier;
Question : G contient-il un s-WCIS de taille au plus k ?
Théorème
s-WCISD est NP-Complet.
Preuve
MISD�s-MISD et s-MISD�s-WCISD.
19/31 31
Complexité de WCISD dans des classes de
graphes particulières
Classe de graphes MDS MMIS MWCIS
co-graphes∗ P P P
Arbres P P P
Graphe biparti NPc NPc P
Graphe de comparabilité NPc NPc NPc
Split graphe NPc P P
(W): Tout MIS de G est un WCIS de G .
∗.Lemme
Soit G = (V , E ) un graphe non orienté connexe. G et tout sous-grapheconnexe induit par V
′
⊂ V , vérifient (W ) si et seulement si G est sansP4.
20/31 31
Approximabilité du WCIS minimum
Théorème
Il n’existe pas d’algorithme d’approximation polynomial A pour leMWCISP tel que :
|A(G)| ≤ n1−ε|MWCIS(G)| ∀0 < ε < 1.
1 Résultat négatif : @ε : |A(G)| ≤ n1−ε |MMIS(G)|
Magnús M. Halldórsson. Approximating the minimum maximalindependence number. Information processing Letters Elsevier,
46:169-172, 1993.
21/31 31
Approximabilité du WCIS minimum
Preuve. (Par l’absurde).
u
u
u
u1
1
n
n
'
'
G
G'
Figure: Le graphe G et son transformé G′
.
Lemme
|MMIS(G)| ≤ |MWCIS(G′
)| ≤ |MMIS(G)| + 1.
22/31 31
Bornes sur le WCIS
Lemme
Soit G = (V , E ) un graphe non orienté connexe. Soient ∆ le degrémaximum de G et MWCIS(G) le WCIS minimum de G .
•|V |−1
∆≤ |S|
• |S| ≤ (∆ − 1)|MWCIS(G)| + 1
Où S est le WCIS obtenu par l’algorithme glouton.
|V | = ∆2 + 1, |MWCIS(G)| = ∆, |V |−1
∆= ∆2+1−1
∆= ∆.
23/31 31
Heuristique pour le problème du MWCIS
• Entrées: G = (V , E ), s= source.
• Sorties: Gglo = (V , [S, V \S]), S = Aglo(G).
SN(S) N(N(S))
source
Liste Candidats
24/31 31
WCIS sur la grille (10*10)
: Capteur.
: Source.
25/31 31
WCIS sur la grille (10*10)
: Relais.
: Esclave.
: Maitre.
: Source.
Clusters= 37
Esclaves =19
^
26/31 31
WCIS sur la grille (10*10)
: Relais.
: Esclave.
: Maitre.
: Source.
Clusters= 34
Esclaves =26
^
27/31 31
WCIS sur la grille (10*10)
: Relais.
: Esclave.
: Maitre.
: Source.
Clusters= 33
Esclaves =25
^
28/31 31
PERSPECTIVES
1 Affiner les résultats de complexité dans des classes particulières degraphes telles que les graphes géométriques.
2 Proposer un algorithme exact (énumératif) pour le problèmeMWCIS.
3 Etudier le polyèdre pour le problème du MWCIS.
4 Collaborer avec l’équipe SMIR LIMOS dirigée par M. Kun-MeanHou pour valider les topologies obtenues.
5 Poursuivre sur des problèmes de routage.
29/31 31
MERCI POUR VOTRE ATTENTION
30/31 31