35
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

Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

Embed Size (px)

Citation preview

Page 1: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 2: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 3: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 4: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 5: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 6: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 7: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 8: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 9: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

Applications

Surveillance environnementale

Moniteur d'inventaire

Industrie

Militaires

Domotique

Médicale

4/31 31

Page 10: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

Topologies et organisation dans le réseau

de capteurs sans fil

Choix des topologies

5/31 31

Page 11: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

Topologies et organisation dans le réseau

de capteurs sans fil

Station de base

Choix des topologies

Plate

6/31 31

Page 12: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 13: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 14: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 15: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 16: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 17: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 18: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 19: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 20: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

Structures combinatoires et réseau sans fil

G=(V,E)

CDS WCDS

E(S)S

[S,V\S]

WCIS

15/31 31

Page 21: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

Comparaison ensembliste

DS

WCDS

MIS

IS

G=(V,E) ; S = une partie de

P(V)

P(V)

16/31 31

Page 22: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 23: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 24: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 25: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 26: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 27: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 28: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 29: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 30: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

WCIS sur la grille (10*10)

: Capteur.

: Source.

25/31 31

Page 31: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

WCIS sur la grille (10*10)

: Relais.

: Esclave.

: Maitre.

: Source.

Clusters= 37

Esclaves =19

^

26/31 31

Page 32: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

WCIS sur la grille (10*10)

: Relais.

: Esclave.

: Maitre.

: Source.

Clusters= 34

Esclaves =26

^

27/31 31

Page 33: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

WCIS sur la grille (10*10)

: Relais.

: Esclave.

: Maitre.

: Source.

Clusters= 33

Esclaves =25

^

28/31 31

Page 34: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

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

Page 35: Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et organisation dans le réseau de capteurs sans ... 5 Poursuivre sur des problèmes de routage

MERCI POUR VOTRE ATTENTION

30/31 31