Conception de r seaux de capteurs sans fil l'aide de ... · PDF file2 Topologies et...

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