Ministère de l’enseignement supérieur et de la recherche scientifique

Université Constantine 2

Faculté des Nouvelles Technologies de l’Information et de la Communication

Département d’Informatique Fondamentale et ses Applications

Thèse pour l’obtention du grade de Docteur en Sciences

Présentée et soutenue publiquement par :

Melle Samia Chelloug

Le 21 / 03 / 2013

Titre :

Optimisation d’énergie dans les algorithmes de routage pour

réseaux mobile
 

Directeur de thèse:

Pr. Mohammed Benmohammed

Jury :
Pr. Allaoua Chaoui Président Université Constantine 2

Pr. Mohammed Benmohammed Rapporteur Université Constantine 2

Dr. Salah Merniz Examinateur Université Constantine 2

Dr. Smain Maazouzi Membre Université de Skikda

Pr. Azzedine Bilami Membre Université de Batna

  Année universitaire 2012‐2013 
 

Remerciements 
 

J’exprime ma profonde gratitude à mon directeur de thèse Pr.

Mohammed Benmohammed pour ses conseils, sa disponibilité, son
écoute et ses encouragements.

J’adresse mes sincères remerciements aux membres du jury pour

m’avoir fait l’honneur de juger mon travail. Mes remerciements
s’adressent en particulier à Monsieur le Professeur Allaoua Chaoui,
pour avoir accepté d’être président du jury. Un grand merci à Monsieur
le Docteur Salah Merniz, Dr. Smail Mazouzi et Pr. Azzedine Bilami
pour avoir accepté de participer dans le jury.

Je souhaite aussi remercier Madame le Professeur Touraya Boumaza

(département d’électronique, Université de Constantine) pour son
soutien qui m’a permis de mener à terme mon travail de recherche.

Je remercie également [Link] Mohammed Soleymani (Université

Concordia, Canada) et Pr. Jean-Claude Konig (Université Montpellier
2, France) pour leurs invitations et leurs bonnes collaborations.

Je tiens également à remercier tous les auteurs qui m’ont assisté à

distance et m’ont clarifié divers aspects liés à leurs papiers.

Merci aux : Pr. Samia Bouhedja, Dr. Mounia Benyamina, Mme.

Afifa Benazouz, Mme. Nadia Boucheham, Melle Huda Sobhi, Melle
Dua Odeh, … Je n’oublierai jamais les moments passés ensemble.

Enfin, un merci particulier à [Link] Clara Moller pour ses

conseils judicieux et son aide précieuse.
 
 

 
 

Je dédie ce travail à mes très chers parents, mes frères et mes sœurs ; en
particulier Fatima-Zohra (Chargé de cours, Université Tebessa) pour
ses conseils consistants qui dépassent le nombre de pages de ce
manuscrit…
 

 
‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫ﻦ اﻟ ﱠﺮﺣِﻴ ِﻢ‬
‫ﺣ َﻤ ِ‬
‫ﺑﺴﻢ اﷲ اﻟ ﱠﺮ ْ‬

‫و ﻳﺴﺄﻟﻮﻧﻚ ﻋﻦ اﻟﺮوح ﻗﻞ اﻟﺮوح ﻣﻦ أﻣﺮي رﺑﻲ و ﻣﺎ أوﺗﻴﺘﻢ ﻣﻦ اﻟﻌﻠﻢ‬

‫إﻻ ﻗﻠﻴﻼ )اﻹﺳﺮاء‪(85:‬‬

‫‪ ‬‬

‫ﺻﺪق اﷲ اﻟﻌﻈﻴﻢ‬

‫‪ ‬‬
‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬
 Résumé

 
 

Les réseaux de capteurs constituent un nouveau thème de recherche offrant l’opportunité de

développer de nouvelles applications et posant ainsi le challenge de la conception d’objets autonomes.
Une des thématiques les plus intéressantes consiste à minimiser le temps d’achèvement nécessaire à la
transmission des paquets des données dans un réseau de capteurs contenant une seule source et une
seule destination et dont les liens sont soumis à des erreurs de transmission. Pour cela, le routage
opportuniste qui fonctionne avec le codage réseau linéaire aléatoire s’avère une idée intéressante. Le
routage opportuniste tire profit de la diffusion et le codage réseau linéaire aléatoire permet de
combiner les paquets avant de les envoyer évitant ainsi toute coordination entre les noeuds. D’autre
part, la récupération d’énergie représente le présent enjeu pour la prolongation de la durée de vie d’un
réseau de capteurs. Cette thèse concerne donc principalement la consommation énergétique dans les
algorithmes de routage pour les réseaux de capteurs. Une grande partie de ce travail a porté sur la
proposition d’un modèle pour la minimisation du temps d’achèvement nécessaire au décodage réseau
linéaire aléatoire dans un réseau de capteurs opérant sous l’hypothèse de récupération d’énergie et
exploitant l’idée de l’opportunisme pour acheminer les données. Pour parvenir à résoudre le modèle
proposé, F-Lipschitz a été utilisée. Cette méthode est adéquate aux modèles qui ne soient pas
convexes et assure l’existence d’une solution. De plus, le calcul par intervalles a été exploité pour
tenir compte de l’incertitude lors du calcul des dérivées. D’un point de vue avantage, cette
arithmétique assure que le résultat calculé se trouve toujours dans l’intervalle en sortie. Les résultats
de simulation ont été menés par Matlab et Omnet++ et représentent une évaluation du modèle en
termes de l’énergie, débit, et temps de terminaison. Ils suggèrent d’augmenter la densité réseau pour
diminuer la probabilité d’effacement. Associer des probabilités de réception aux noeuds capteurs et
prolonger la durée de vie sous routage opportuniste est une contribution connexe à la première. Dans
ce cadre, les métaheuristiques s’avèrent un outil puissant qui converge vers une solution optimale. Le
modèle considéré garantit une consommation énergétique uniforme entre les différents noeuds
capteurs. L’autre volet de cette thèse concerne le routage économe en énergie dans les réseaux de
capteurs mobiles où la prédiction peut être exploitée conjointement avec une approche de routage par
voisinage afin d’acheminer les données dans un réseau dense avec un bon taux d’acheminement.

Mots clefs : réseaux de capteurs, routage opportuniste, routage géographiques, énergie, codage réseau
linéaire aléatoire, récupération d’énergie, optimisation, F-Lipshitz, métaheuristiques, mobilité,
Omnet++.

 
 

Abstract

The new field of wireless sensor networks presents many opportunities and new challenges. One
particularly difficult aspect of wireless sensor networks is minimizing the completion time requires
for sending data packets in an end-to-end session network with lossy links. To enable data routing,
opportunistic routing together with random linear network coding can be used. Thus, opportunistic
routing takes advantage of broadcast transmission and mixing packets before sending them avoids any
coordination between nodes of the network. To allow extending the lifetime of wireless network
composed of a huge number of sensor nodes equipped by small batteries; a technique that harvests
ambient energy is assumed integrated. This thesis concentrates on energy efficient routing protocols
in sensor networks. It mainly proposes a framework for minimizing the completion time in a wireless
sensor network with energy harvesting under opportunistic routing and random linear network coding.
Traditional techniques are not suitable for solving the proposed model since it is non convex. So, F-
Lipschitz method was exploited and demonstrated the existence of a solution for the formulated
problem. To further address the uncertainty during calculation of derivates, interval arithmetic has
been used where the exact result is contained in the computed interval. Simulation results obtained by
Matlab and Omnet++ give an evaluation of the proposed scheme in term of energy, throughput and
completion time. They suggest to operate at high density to decrease the erasure probability. By
another hand, prolonging the lifetime of a sensor network is another contribution of this work. In this
context, sensor nodes are associated with reception probabilities such that uniform energy
consumption among the nodes is guaranteed. The model has been solved with the simulated annealing
and linear programming and yields to convergence.

The other part of this thesis concerns energy efficient routing in mobile sensor networks where the
prediction is used in conjunction with a neighborhood approach for routing data in a dense network.
The delivery rate is good and the localization errors acceptable.

Keywords: sensor networks, opportunistic routing, geographic routing, energy, random linear
network coding, energy harvesting, optimization, F-Lipshitz, Metaheuristics, mobility, Omnet++.

 
 ‫ﻣﻠﺨﺺ‬

‫‪ ‬‬

‫اﻟﺤﻘﻞ اﻟﺠﺪﻳﺪ ﻣﻦ ﺷﺒﻜﺎت اﻻﺳﺘﺸﻌﺎر اﻟﻼﺳﻠﻜﻴﺔ ﻳﻌﺮض اﻟﻌﺪﻳﺪ ﻣﻦ اﻟﻔﺮص واﻟﺘﺤﺪﻳﺎت اﻟﺠﺪﻳﺪة‪ .‬أﺣﺪ اﻟﺼﻌﻮﺑﺎت‬
‫ﻟﻠﺸﺒﻜﺎت اﻻﺳﺘﺸﻌﺎر اﻟﻼﺳﻠﻜﻴﺔ ﻳﻜﻤﻦ ﻓﻲ اﻟﺘﻘﻠﻴﻞ ﻣﻦ اﻟﻮﻗﺖ اﻟﻼزم ﻟﺤﻞ اﻟﺮﻣﺰ و إرﺳﺎل ﺣﺰم اﻟﺒﻴﺎﻧﺎت ﻓﻲ ﺷﺒﻜﺔ‬
‫ﺗﺘﻤﻴﺰ ﺑﻮﺻﻼت اﻟﻀﻴﺎع‪ ‬ﻣﻊ وﺟﻮد ﻣﻨﺒﻊ و ﺟﻬﺔ واﺣﺪة‪ .‬ﻟﺘﻤﻜﻴﻦ ﺗﻮﺟﻴﻪ اﻟﺒﻴﺎﻧﺎت‪ ،‬ﻳﻤﻜﻦ اﺳﺘﺨﺪام اﻟﺘﻮﺟﻴﻪ اﻻﻧﺘﻬﺎزي و‬
‫اﻟﺘﺮﻣﻴﺰ اﻟﺸﺒﻜﻲ اﻟﺨﻄﻲ اﻟﻌﺸﻮاﺋﻲ‪ .‬وهﻜﺬا‪ ،‬ﺗﻮﺟﻴﻪ اﻻﻧﺘﻬﺎزﻳﺔ ﻳﺴﺘﻔﻴﺪ ﻣﻦ ﺑﺚ اﻹرﺳﺎل واﻟﺨﻠﻂ ﻗﺒﻞ إرﺳﺎل اﻟﺒﻴﺎﻧﺎت‬
‫آﻲ ﻳﺘﺠﻨﺐ أي ﺗﻨﺴﻴﻖ ﺑﻴﻦ اﻟﻌﻘﺪ ﻓﻲ اﻟﺸﺒﻜﺔ‪ .‬ﻟﻠﺴﻤﺎح ﺑﺘﻤﺪﻳﺪ ﻋﻤﺮ ﺷﺒﻜﺔ ﻻﺳﻠﻜﻴﺔ ﻣﻜﻮﻧﺔ ﻣﻦ ﻋﺪد هﺎﺋﻞ ﻣﻦ اﻟﻌﻘﺪ‬
‫اﺳﺘﺸﻌﺎر ﻣﺠﻬﺰة ﺑﺒﻄﺎرﻳﺎت ﺻﻐﻴﺮة؛ وﺿﻌﻨﺎ إﻓﺘﺮاض إﺳﺘﺨﺪام ﺗﻘﻨﻴﺔ ﺗﺤﺼﻴﻞ اﻟﻄﺎﻗﺔ اﻟﻤﺤﻴﻄﺔ‪ .‬هﺬﻩ اﻷﻃﺮوﺣﺔ‬
‫ﺗﺮآﺰ ﻋﻠﻰ ﺑﺮوﺗﻮآﻮﻻت آﻔﺎءة اﻟﻄﺎﻗﺔ ﻓﻲ ﺷﺒﻜﺎت اﻻﺳﺘﺸﻌﺎرو ﺗﻘﺘﺮح أﺳﺎﺳﺎ إﻃﺎرا ﻟﺘﻘﻠﻴﻞ وﻗﺖ اآﺘﻤﺎل ﻓﻲ ﺷﺒﻜﺔ‬
‫اﺳﺘﺸﻌﺎر ﻻﺳﻠﻜﻴﺔ ﻣﻊ ﺣﺼﺎد اﻟﻄﺎﻗﺔ ﺗﺤﺖ ﺗﻮﺟﻴﻪ اﻻﻧﺘﻬﺎزﻳﺔ و اﻟﺘﺮﻣﻴﺰ اﻟﺸﺒﻜﻲ اﻟﺨﻄﻲ اﻟﻌﺸﻮاﺋﻲ‪ .‬اﻟﺘﻘﻨﻴﺎت اﻟﺘﻘﻠﻴﺪﻳﺔ‪ ‬‬
‫ﻟﻴﺴﺖ ﻣﻨﺎﺳﺒﺔ ﻟﺤﻞ ‪ ‬اﻟﻨﻤﻮذج اﻟﻤﻘﺘﺮح ‪ ‬ﻷﻧﻪ ‪ ‬ﻏﻴﺮ ‪ ‬ﻣﺤﺪب‪ .‬ﻟﺬﻟﻚ‪ ،‬ﺗﻢ اﺳﺘﻐﻼل ﻃﺮﻳﻘﺔ ‪ F‬ﻟﻴﺒﺸﻴﺘﺰ وأﺛﺒﺘﺖ وﺟﻮد ﺣﻞ‬
‫ﻟﻠﻤﺸﻜﻠﺔ اﻟﻤﺼﺎﻏﺔ‪ .‬و ﻟﻤﻌﺎﻟﺠﺔ ﻋﺪم اﻟﻴﻘﻴﻦ ﺧﻼل ﺣﺴﺎب اﻟﻤﺸﺘﻘﺎت‪ ،‬ﻗﻤﻨﺎ ﺑﺎﺳﺘﺨﺪام اﻟﺤﺴﺎب اﻟﻔﺎﺻﻞ ﺣﻴﺚ ﺗﺮد اﻟﻨﺘﻴﺠﺔ‬
‫اﻟﺪﻗﻴﻘﺔ ﻓﻲ اﻟﻤﺠﺎل اﻟﻤﺤﺴﻮب‪ .‬ﻧﺘﺎﺋﺞ اﻟﻤﺤﺎآﺎة اﻟﺘﻲ ﺣﺼﻞ ﻋﻠﻴﻬﺎ ﺑﻮاﺳﻄﺔ ﻣﻄﻠﺐ وأﻣﻨﻴﺖ ‪ + +‬ﺗﻌﻄﻲ ﺗﻘﻴﻴﻢ اﻟﺨﻄﺔ‬
‫اﻟﻤﻘﺘﺮﺣﺔ ﻣﻦ ﺣﻴﺚ اﻹﻧﺘﺎﺟﻴﺔ ‪،‬اﻟﻄﺎﻗﺔ ووﻗﺖ اﻻﻧﺘﻬﺎء‪ .‬هﺬﻩ اﻟﻨﺘﺎﺋﺞ ﺗﻮﺣﻲ ﻟﻠﻌﻤﻞ ﻓﻲ آﺜﺎﻓﺔ ﻋﺎﻟﻴﺔ ﻟﺘﻘﻠﻴﻞ اﺣﺘﻤﺎل‬
‫اﻟﻤﺤﻮ‪ .‬ﻣﻦ ﺟﻬﺔ أﺧﺮى‪ ،‬إﻃﺎﻟﺔ ﻋﻤﺮ ﺷﺒﻜﺔ اﻻﺳﺘﺸﻌﺎر هﻮ ﻣﺴﺎهﻤﺔ أﺧﺮى ﻓﻲ هﺬا اﻟﻌﻤﻞ‪ .‬ﻓﻲ هﺬا اﻟﺴﻴﺎق‪ ،‬ﺗﺘﻌﻠﻖ ﻋﻘﺪ‬
‫اﻻﺳﺘﺸﻌﺎر ﺑﺎﺣﺘﻤﺎﻻت اﺳﺘﻘﺒﺎل ﺑﺤﻴﺚ ﻳﺘﻢ ﺿﻤﺎن ﻣﻮﺣﺪة اﺳﺘﻬﻼك اﻟﻄﺎﻗﺔ ﺑﻴﻦ اﻟﻌﻘﺪ‪ .‬و ﻟﻘﺪ ﺣﻞ اﻟﻨﻤﻮذج ﺑﺎﺳﺘﺨﺪام‬
‫ﺳﻤﻠﻴﺘﺎد أﻧﺎﻟﻴﻦ واﻟﺒﺮﻣﺠﺔ اﻟﺨﻄﻴﺔ وأدى إﻟﻰ اﻟﺘﻘﺎرب‪  .‬‬

‫اﻟﺠﺰء اﻵﺧﺮ ﻣﻦ هﺬﻩ اﻟﺮﺳﺎﻟﺔ ﺗﻌﻠﻖ ﺑﻮﺿﻊ ﺧﻄﺔ ﻟﺘﻮﺟﻴﻪ اﻟﺒﻴﺎﻧﺎت ﻣﻊ ﻣﺮاﻋﺎة اﺳﺘﺨﺪام اﻟﻄﺎﻗﺔ ﻓﻲ ﺷﺒﻜﺎت اﻻﺳﺘﺸﻌﺎر‬
‫اﻟﻤﺤﻤﻮﻟﺔ ﺣﻴﺚ ﻳﺘﻢ اﺳﺘﺨﺪام اﻟﺘﻨﺒﺆ ﺑﺎﻟﺘﺰاﻣﻦ ﻟﺘﻮﺟﻴﻪ اﻟﺒﻴﺎﻧﺎت ﻓﻲ ﺷﺒﻜﺔ آﺜﻴﻔﺔ‪ .‬ﻣﻌﺪل اﻟﺘﺴﻠﻴﻢ ﺟﻴﺪ وأﺧﻄﺎء اﻟﺘﻤﺮآﺰ‬
‫ﻣﻘﺒﻮﻟﺔ‪  .‬‬

‫آﻠﻤﺎت اﻟﺒﺤﺚ‬

‫ﺷﺒﻜﺎت اﻹﺳﺘﺸﻌﺎر‪ ،‬اﻟﺘﻮﺟﻴﻪ اﻹﻧﺘﻬﺎزي‪ ،‬اﻟﺘﻮﺟﻴﻪ اﻟﺠﻴﻐﺮاﻓﻲ‪ ،‬اﻟﺘﺮﻣﻴﺰ اﻟﺸﺒﻜﻲ اﻟﺨﻄﻲ اﻟﻌﺸﻮاﺋﻲ‪ ،‬ﺗﺤﺼﻴﻞ اﻟﻄﺎﻗﺔ‪،‬‬
‫اﻟﺘﺤﺴﻴﻦ‪ F ،‬ﻟﻴﺒﺸﻴﺘﺰ ﻣﻴﺘﺎ أورﺳﺘﻴﻚ‪ ،‬اﻟﺘﻨﻘﻞ‪ ،‬أﻣﻨﻴﺖ ‪  + +‬‬

‫‪ ‬‬
‫‪ ‬‬

‫‪ ‬‬
 Table de matière

Introduction générale 8

Chapitre1 : Réseaux de capteurs

1. Introduction 10

2. Qu’est-ce qu’un capteur ? 10

3. Réseaux de capteurs 11

4. Composants d’un capteur 11

5. Plateformes des réseaux de capteurs 13

6. Réseaux de capteurs versus Manet 14

7. Challenge de réseaux de capteurs 14

8. Applications des réseaux de capteurs 15

9. Pile protocolaire d’un réseau de capteurs 16

10. Protocoles de routage dans les réseaux de capteurs 16

10-1. Inondation 17

10-2. Gossiping 17

10-3. Protocole Spin 17

10-4. Protocoles hiérarchiques 18

10-5. Protocoles géographiques 18

10-6. Techniques cross-layer 19

11. Pourquoi la récupération d’énergie dans les réseaux de capteurs ? 20

12. Architecture d’un nœud 20

13. Sources énergétiques 22

14. Gestion de l’énergie récupérée 23

15. Routage avec récupération d’énergie 24

16. Conclusion 24

Chapitre2 : Routage opportuniste et codage réseau

1
 

 
 1. Introduction 26

2. Définition d’un champ 26

3. Champs de Galois 27

4. Addition et multiplication dans GF (2m) 28

5. Codage réseau 29

[Link] du codage réseau 30

[Link]éorème du codage réseau 32

6. Codage réseau linéaire aléatoire 32

7. Pourquoi et c’est quoi le routage opportuniste ? 33

7-1. Métrique ETX 34

7-2. Protocole EXOR 34

8. Protocole MORE 35

8-1. Nombre de transmissions 36

8-2. Format des paquets 36

8-3. Test de l’indépendance linéaire 37

9. Protocole SOAR 38

10. Conclusion 39

Chapitre 3 : Optimisation F-Lipschitz

1. Introduction 41

2. Problème d’optimisation 41

3. Classification des problèmes d’optimisation 42

4. Méthodes de résolution 42

4-1. Méthodes par décomposition 43

5. Fonction Lipschitz 43

6. Problème d’optimisation F-Lipschitz 45

7. Problème canonique 47

8. Optimalité de la solution F-Lipschitz 49

  2
 
9. Calcul de la solution optimale 50

10. F-Lipschitz pour les réseaux de capteurs 51

11. Conclusion 52

Chapitre 4 : Contributions pour le routage opportuniste et géographique

1. Introduction 53

2. Contribution principale ‘Système de routage opportuniste avec récupération d’énergie’ 53

2-1. Travaux connexes 53

2-2. Système proposé 55

2-3. Temps de terminaison 56

2-4. Modèle d’optimisation 58

2-5. Formulation F-Lipschitz 63

2-6. Estimation de la probabilité d’effacement 65

2-7. Scénarios d’exécution 66

3. Contributions secondaires 68

3-1. Maximisation de la durée de vie d’un réseau de capteurs sous routage opportuniste 68

3-2. Localisation et routage géographique dans un réseau de capteurs statiques 69

3-2-1. Formulation du problème 70

4. Conclusion 74

Chapitre 5 : Résultats de simulation

1. Introduction 75

2. C’est quoi Omnet++ ? 75

3. Modélisation de la simulation Omnet++ 75

3-1. Composants 77

3-2. Messages et paquets 78

3-3. Configuration de la simulation 79

4. Résultats de simulation 79
 
3
 
 4-1. Résultats de la contribution principale 79

4-2. Evaluation de la consommation énergétique 82

4-3. Evaluation du débit 82

4-4. Evaluation du temps de terminaison 84

4-5. Impact du nombre des paquets 84

4-6. Résultat du système de la maximisation de la durée de vie 85

4-7. Résultats de localisation et de routage géographique 86

5. Conclusion 90

Conclusion générale et perspectives 92

Annexe : Calcul par intervalles 94

Références bibliographiques 97

  4
 Liste des figures
 

Chapitre 1 : Réseaux des capteurs

Figure 1. Principe de l’étalonnage 10

Figure 2. Architecture d’un réseau de capteurs 11

Figure 3. Architecture d’un nœud capteur 13

Figure 4. Pile protocolaire d’un réseau de capteurs 16

Figure 5. Principe du protocole SPIN 18

Figure 6. Principe du routage géographique 19

Figure 7. Zebra Net 21

Figure 8. Architecture d’un système de récupération d’énergie 21

Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

Figure 1.a. Routage vers R1 30

Figure 1.b. Routage vers R2 30

Figure 1.c. Multicast avec codage réseau 30

Figure 2.a. Echange de x1, x2 sans codage réseau 31

Figure 2.b. Echange de x1, x2 avec codage réseau 31

Figure 3.a. Envoi des données sans codage réseau 31

Figure 3.b. Envoi des données avec codage réseau 31

Figure 4.a. Taille de la coupe au niveau de D 32

Figure 4.b. Taille de la coupe au niveau de E,F 32

Figure 5. Principe du codage réseau linéaire aléatoire 33

Figure 6.a. Exemple d’un réseau 34

Figure 6.b. Métrique ETX de chaque chemin 34

Figure 7. Format d’un paquet MORE 37

Figure 8. Principe du protocole MORE 40

5
 

 
Chapitre 3 : Optimisation F-Lipschitz

Figure 1. Processus de décision 41

Figure 2. Optimalité au sens Pareto 50

Chapitre 4 : Contributions pour le routage opportuniste et géographique

Figure 1. Phases et quantités d’énergie récupérées 55

Figure 2. Principe du modèle proposé 57

Figure 3. Algorithme de Prim 61

Figure 4. Chaîne de Markov proposée pour le décodage 65

Figure 5. Figure 5. Principe de la résolution du modèle 66

Figure 6. Scénario 1 67

Figure 7. Scénario 2 67

Figure 8. Algorithme du recuit simulé pour le calcul des probabilités de réception 69

Figure 9. Prédiction des positions des nœuds capteurs 73

Chapitre5 : Résultats de simulation

Figure 1. Topologie des nœuds capteurs 81

Figure 2. Architecture d’un nœud capteurs 81

Figure 3. Consommation énergétique des deux scénarios 82

Figure 4. CDF du débit des deux scénarios 83

Figure 5. Temps de terminaison en fonction de la probabilité d’effacement 84

Figure 6. Effet de la densité et du nombre de paquets sur le deuxième scénario 85

Figure 7. Probabilité de réception moyenne versus le nombre d’itérations 86

Figure 8. Ordonnées prédites versus temps de simulation 88

Figure 9. Abscisses prédites versus temps de simulation 88

Figure 10. Impact du paramètre a’ sur le taux d’acheminement 89

Figure 11. Impact du paramètre a’ sur la consommation énergétique 90

  6
 
 Liste des tableaux
 

Chapitre 1 : Réseaux des capteurs

Tableau 1. Plateformes des réseaux de capteurs 14

Tableau 2. Sources d’énergie et leurs caractéristiques 22

Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

Tableau 1.a. Addition dans Z7 27

Tableau 1.b. Multiplication dans Z7 27

Tableau 2. Exemples de polynômes primitifs 28

Tableau 3.a. Représentation polynomiale 29

Tableau 3.b. Addition dans GF (23) 29

Chapitre 3 : Optimisation F-Lipschitz

Tableau 1. Notations et définitions 45

Chapitre 4 : Contributions pour le routage opportuniste et géographique

Tableau 1. Notations du modèle proposé 59

Tableau 2. Notations et définitions 68

Chapitre 5 : Résultats de simulation

Tableau 1. Paramètres de la simulation 80

Tableau 2. Paramètres de la simulation du routage géographique 87

Tableau 3. Meilleures valeurs du paramètre a’ 90

  7

 
 Introduction génèrale

La démultiplication massive des technologies sans fil a révolutionné les moyens de

communication depuis le début du vingt et unième siècle avec notamment l’apparition des
réseaux ad hoc. Alors que les hôtes dans un réseau ad hoc ont un intérêt propre, les réseaux
de capteurs amènent en supplément la possibilité d’acquérir et de communiquer les données
de manière locale. Il s’agit de nier le concept de miniaturisation à la notion de communication
pour couvrir une large palette d’applications. Dans un réseau de capteurs, une quantité
d’énergie considérable est consommée durant les communications sans fil (mode de
transmission et de réception). De plus, les batteries utilisées sont petites et leur remplacement
n’est pas toujours pratique. Deux alternatives existent : la première consiste à développer des
protocoles maximisant la durée de vie du réseau tout en spécifiant le critère de
fonctionnement du réseau. Cependant, l’enjeu actuel consiste à intégrer des systèmes de
récupération d’énergie dans chaque capteur afin de garantir une durée de vie infinie.
Evidemment, la quantité d’énergie récupérée dépend des caractéristiques de la source
employée. D’autres parts, divers travaux ont traité le problème du routage dans les réseaux de
capteurs où chaque capteur n’a aucune information a priori à propos du réseau auquel il
appartient. L’inconvénient majeur des protocoles de routage traditionnels ; entre autre le
routage géographique qui dépend de la localisation est qu’ils ne tiennent pas compte des
erreurs de transmission sans fil. Pour cela, le routage opportuniste exploite le concept de
diffusion qui caractérise les réseaux sans fil pour acheminer convenablement des paquets.
Au sens large, aucune route n’est établie a priori et les nœuds se mettent en mode de
réception si aucune transmission n’est prête ou autorisée. Les nœuds qui ont eu l’opportunité
de recevoir un paquet peuvent prendre le rôle de relais. Ce protocole a fait l’objet d’une
certaine fascination des chercheurs, qui ont intégré le codage réseau linéaire aléatoire au
routage opportuniste. Le focus ici est d’effectuer un routage décentralisé sans aucune
synchronisation. De sa part, le codage réseau linéaire aléatoire tire avantage des
caractéristiques des champs de Galois et offre ainsi un débit de transmission maximal.
Dans ce contexte, le temps de terminaison nécessaire au décodage des paquets reçus par une
ou plusieurs destinations est un problème d’optimisation essentiel. Les études réalisées sont
orientées autour des topologies constituées d’une seule source où les communications multi-
sauts ne sont pas nécessaires. Elles décrivent le processus de transmission et du décodage par
des chaînes de Markov discrètes.
Notre objectif principal dans cette thèse sera donc d’étudier ce problème dans un réseau de
capteurs pouvant récupérer l’énergie et acheminer les paquets par routage opportuniste et
codage réseau aléatoire tout en ayant la possibilité de changer les puissances de transmissions
associées aux capteurs. En d’autre terme, les contraintes liées à la couche réseau et physique
sont ainsi modélisées.
La formulation proposée nous a amenés à s’interroger sur une méthode de résolution qui soit
adéquate pour un modèle qui n’est pas convexe. En conséquence, une résolution centralisée
moyennant la méthode F-Lipschitz a été adoptée. La première étape consiste à vérifier si le
problème d’optimisation manipulé respecte la forme F-Lipschitz. Le cas, échant, un certain
 
8
 
nombre de conditions doit être vérifié avant de procéder à la transformation du problème en
question. Ensuite, le calcul de la solution optimale est obtenu moyennant le gradient des
contraintes du modèle et la projection des variables sur un domaine borné.
Une seconde question s’est posée lors du calcul des dérivées sachant que chaque capteur
opère selon des phases qui soient différentes celles utilisées par les autres capteurs. Pour cela,
nous avons jugé utile l’intégration du calcul par intervalles pour prendre en compte les
incertitudes présentes. L’idée du calcul par intervalles consiste à représenter chaque nombre
par un intervalle le contenant.
A côté de la contribution principale, deux contributions secondaires ont été mises en œuvre.
La première a consisté à étudier un système de routage opportuniste et de trouver la durée de
vie maximale assurant sa convergence moyennant une classe de métaheuristique appelée
‘recuit simulé ‘. Enfin, la dernière proposition a consisté à localiser des capteurs mobiles
selon une technique prédictive et d’exploiter les positions estimées lors d’un routage
géographique économe en énergie.

Cette thèse est organisée en cinq chapitres:

™ La première partie du premier chapitre intitulé ‘Réseaux de capteurs’ est consacrée à un

état de l’art sur les réseaux de capteurs. Des critiques ont porté sur les réseaux de capteurs
traditionnels et la seconde partie décrit donc la technologie de récupération d’énergie qui
permet d’atteindre une durée de vie approximativement infinie et de dépasser les
contraintes énergétiques.
™ Le deuxième chapitre est intitulé ‘Routage opportuniste et codage réseau linéaire
aléatoire’ présente essentiellement l’idée du protocole de routage opportuniste ‘MORE’
qui exploite conjointement la diversité spatiale et le codage réseau linéaire aléatoire. Les
champs de Galois constituent la partie introductive de ce chapitre puisque le codage
réseau linéaire aléatoire est basé sur ces champs infinis.
™ Le troisième chapitre est intitulé ‘Optimisation par F-Lipschitz ‘. Il est consacré à la
technique d’optimisation F-Lipschitz. Les avantages de cette méthode par rapport aux
méthodes d’optimisation existantes sont mis en œuvre et les conditions nécessaires pour
transformer un problème en un problème F-Lipschitz sont expliquées.
™ Le quatrième chapitre est intitulé ‘Contributions pour le routage opportuniste et
géographique’ contient nos contributions. Les modèles proposés ainsi que les scénarios de
simulation seront présentés au sein de ce chapitre.
™ Le cinquième chapitre est intitulé ‘Résultats de simulation’. Un aperçu du simulateur
Omnet++ est présenté. Les résultats de simulation obtenus tout au long de ce parcours de
recherche sont illustrés et expliqués.

Notons que ce manuscrit contient à la fin une annexe sur le calcul par intervalles.

  9

 
Chapitre 1 : Réseaux de capteurs

1. Introduction

Les technologies permettant la transmission sans fil des informations sont désormais d’usage
courant. Plus spécifiquement, l’avènement des réseaux de capteurs a révolutionné le monde. Il
s’agit d’unités miniaturisées dotées de capacités d’acquisition et de communication des
informations à une faible portée. Aux contraintes traditionnelles des réseaux ad hoc s’ajoutent
des limites très strictes : capacité de calcul, la mémoire et en particulier l’énergie. L’émergence
de ce champ d’étude impose une sévérité de divers problèmes et de nouveaux protocoles qui
soient efficaces en énergie sont requis. Le problème du routage est ainsi omniprésent dans les
réseaux de capteurs et c’est d’ailleurs un problème d’optimisation bi-objectifs : trouver le chemin
optimal et minimiser la consommation énergétique et/ou maximiser la durée de vie du réseau.
Depuis quelques années, l’accent a été mis sur la conception des capteurs autonomes pouvant
convertir l’énergie récupérée à partir de l’environnement externe afin de prolonger la durée de
vie du réseau.
L’objectif de ce chapitre est de dresser un état de l’art des réseaux de capteurs et la technologie
de récupération d’énergie.

2. Qu’est-ce qu’un capteur?

La surveillance des paramètres physiques, chimiques ou biologiques dans une chaîne de
mesure requiert souvent l’utilisation des capteurs. Par définition, un capteur est un dispositif qui
génère une image sous forme en général électrique, d’une grandeur physique. De manière plus
précise, un capteur peut être vue comme une boite noire qui accepte en entrée une mesurande
c’est à dire la quantité que l’on cherche à mesurer (m) et produit en sortie une grandeur
électrique notée S pouvant être une charge électrique, un courant, un différentiel de potentiel ou
une impédance. Autrement, dit, le rôle d’un capteur est de calculer S= F(m) [1]. Le principe de
base repose sur l’opération d’étalonnage. Sachant différentes valeurs m1, m2, …, mi, on relève les
signaux S1, S2, …, Si. Le rôle du capteur consiste donc à lire S lorsque m est inconnu [2].

Si

S?

mi m
Figure1. Principe de l’étalonnage

  10
Chapitre 1 : Réseaux de capteurs

Dans la littérature, on trouve souvent le terme capteur actif et passif. On parle de capteur passif
lorsque le signal généré S est une différence d’impédance et une source d’énergie est intégrée
pour le lire. En fonction des paramètres que l’on souhaite mesurer et contrôler, une multitude de
capteurs existent dans le marché industriel. Il s’agit des capteurs de température, position,
vitesse,… chacun ayant des caractéristiques de précision, rapidité et de sensibilité [3].

3. Réseaux de capteurs
Traditionnellement, l’emploi des capteurs était limité au prélèvement de la température,
l’humidité, la vitesse,… par la suite on a pensé à rajouter des capacités de communication en
ayant la possibilité d’accéder à distance aux grandeurs mesurées par les capteurs. L’idée consiste
donc à déployer des capteurs dans un champ. Un ou plusieurs nouds capteurs prennent le rôle de
source (entité qui fournit des informations). De plus, on a besoin d’une ou plusieurs stations de
base (entité où l’information est requise). Ça peut être un PDA ou un Gateway à un autre réseau
Internet, satellitaire, wifi, wimax… Dans ce contexte, un ou plusieurs utilisateurs peuvent avoir
accès aux informations collectées et acheminées par les capteurs qui assurent la double fonction
de collecte des données et celle du routage. En particulier, l’interaction avec l’environnement, le
traitement des informations et la communication de manière locale constituent les éléments clés
d’un réseau de capteurs [4].

Figure2. Architecture d’un reseau de capteurs.

4. Composantes d’un nœud capteur

L’architecture de base d’un nœud capteur est illustrée en figure 3 [4].

-Unité de capture : elle a été expliquée dans la section précédente. Pratiquement, chaque unité de
capture est caractérisée par trois rayons: un rayon de communication qui lui permet d’échanger

  11
Chapitre 1 : Réseaux de capteurs

des messages et des données avec les autres nœuds capteurs, un rayon d’interférence permettant
de détecter les collisions et un rayon plus large qui constitue le rayon de sensation. Ce dernier est
la portée assurant la détection des évènements. Les technologies matérielles offrent deux choix :
des valeurs fixes ou variables pour les trois rayons. Evidemment, des valeurs assez élevées pour
le rayon de communication et de sensation requièrent une puissance considérable.
-Contrôleur : collecte les données produites par les capteurs associés à un nœud et celles
envoyées par les nœuds capteurs voisins. Il assure également le traitement des données et la prise
de décision concernant leur envoi (quand est ce qu’il faudra envoyer et quand ?). Les réseaux de
capteurs déployés par les entreprises industrielles incluent des microcontrôleurs tels que : Intel(
32 bits RISC, Core, 206 MHZ) , Texas (16 bits RISC Core) et Atmel ( 8 bits et il est équipé par
différentes interfaces).
Trois motivations pour l’utilisation des microcontrôleurs dans le cadre des réseaux de capteurs
sont à mentionner :

™ Facilité de connexion avec les capteurs.

™ Faible consommation énergétique.

™ Possibilité de réduction de la consommation énergétique par la mise dans l’état de veille.

-Mémoire : les valeurs lues ainsi que les paquets reçus sont stockés dans la RAM tandis que
l’application du réseau de capteurs réside en ROM. Plus précisément, une EEPROM est requise
afin de servir pour la sauvegarde des données en cas où la RAM n’est pas suffisante.
-Communication : la plupart des réseaux de capteurs s’appuient sur les communications radio
fréquence (RF) puisqu’elles offrent un débit élevé et la distance de communication tolérée est
bonne. A cela s’ajoute le fait que les erreurs sont acceptables et qu’aucune ligne de visée n’est
requise. Pour cela, l’architecture d’un capteur intègre un émetteur/récepteur dont le rôle est de
convertir les trames de bits émises par le microcontrôleur en une onde radio. Il est à noter que le
problème des communications RF est qu’elles requièrent la modulation, le multiplexage, filtrage
et la démodulation des signaux. Ces opérations sont complexes et consomment de l’énergie.
-Source énergétique : la batterie constitue la source d’énergie la plus utilisée mais nous allons
voir au niveau de la deuxième partie de ce chapitre qu’actuellement les capteurs sont capables de
récupérer l’énergie à partir de l’environnement externe. Signalons que les batteries ont des
caractéristiques matérielles (capacité, taux de décharge,…) qu’il faudra prendre en considération.
Les capteurs, le microcontrôleur et l’émetteur/récepteur radio sont les composants qui
consomment une grande partie d’énergie. Les études réalisées confirment que
l’émetteur/récepteur consomme une très grande quantité d’énergie (lorsqu’il est en mode
transmission, réception ou en veille) par rapport aux capteurs et microcontrôleurs [5]. Plus
précisément, 62% de l’énergie est consommée par l’émetteur/récepteur radio d’une architecture
d’un réseau de capteurs typique lorsqu’il est en mode de transmission. Cependant, 19% de
l’énergie est consommée en mode de réception et le reste de l’énergie est consommé par le
microcontrôleur.

  12
Chapitre 1 : Réseaux de capteurs

Mémoire

Communication  Contrôleur Capteurs/actionners

Source énergétique

Figure3. Architecture d’un nœud capteur.

5. Plateformes des réseaux de capteurs

Diverses plateformes des réseaux de capteurs ont été conçues et peuvent être regroupées en
low-end et high-end. La première classe est caractérisée par des capacités limitées en termes de
traitement de l’information et celle de stockage. Dans ce cas, un nombre important de capteurs
doit être déployé [5]. D’un point de vue architectural, les plateformes de type ‘high-end’ sont
basées sur des composants plus performants. Le tableau 1 donne un aperçu des plateformes
existantes.
A l’issu de l’hétérogénéité des plateformes des réseaux de capteurs, des standards ont été
développés.
-IEEE 802.15.4 offre trois bandes de communication. La bande globale de 2.4 MHZ, la bande de
915 MHZ réservée à l’Amérique et celle de 868 MHZ réservée à l’Europe. Ce standard définit
les protocoles de la couche physique et la couche MAC (medium Access control). Il s’adapte
bien à des réseaux de topologie étoile, mesh, arbre et cluster. IEEE 802.15.4 permet des
communications à une distance de 10-100 m avec un débit de 20-250 Kbps.
-Zigbee est un second standard définit au-dessus du IEEE802.15.4 et spécifie les protocoles de la
couche réseau et application. Les dispositifs Zigbee nécessitent très peu d’énergie pour
fonctionner ; ce qui favorise l’utilisation de ce standard dans le cas des réseaux de capteurs.
Néanmoins, le débit offert par Zigbee est un point critique surtout si le réseau considéré est
dense. Au niveau de la couche réseau, le routage peut être direct si l’adresse réseau est connue ou
indirect (de manière hiérarchique) dans le cas contraire et ceci après une phase de découverte de
la route comme c’est le cas du protocole AODV ‘Ad hoc on demande distance vector’.

  13
Chapitre 1 : Réseaux de capteurs

Type Année Vitesse Mémoire RAM (Kb) Fréquence Débit de

CPU (MHZ) programmes (MHZ) transmission
(Kb) (Kbps)

Mica 2002 6 128 4 868 10/40

Mica2 2003 16 128 4 433/868/916 38.4Kbaud

Micaz 2004 16 128 4 2.4GHZ 250

TelosB/Tmote 2005 16 48 10 2.4GHZ 250

BTnode 2007 8 128 64 433-915 Varié

Stargate 2005 400 32Mb(SD) 64Mb (SD) 2.4GHZ varié

Tableau1. Plateformes des réseaux de capteurs.

6. Réseaux de capteurs versus Manet

Les réseaux de capteurs et les réseaux ad hoc représentent deux catégories des réseaux sans fil.
La communication sans fil, le fonctionnement sans avoir besoin d’une infrastructure pour la
gestion des échanges et la dépendance de la portée de communication aux capacités de
rayonnement et de la puissance choisie sont des points communs à eux. Les réseaux ad hoc sont
composés d’objets ayant un intérêt propre [6] et sont souvent utilisés directement par des êtres
humains (PDA, portables,…). Par exemple, dans un réseau de téléphonie, chaque hôte désire
joindre un correspondant ou accéder à des services. Les hôtes dans un réseau de capteurs sont
fréquemment déployées dans un environnement hostile, ont une application commune et sont
orientées vers la collecte des données. Elles sont peu mobiles par rapport aux hôtes dans un
réseau ad hoc. Un autre point concerne les capacités de calcul et d’énergie qui sont souvent
limitées dans les réseaux de capteurs. Enfin, il est à noter que les réseaux ad hoc opèrent à un
débit élevé en comparaison au débit utilisé dans les réseaux de capteurs [7].

7. Challenge des réseaux de capteurs

-Type de service : une fois déployé, un réseau de capteurs doit fournir des informations
significatives et ne doit pas se limiter au transport des bits de données comme dans le cas des
réseaux classiques [4].

  14
Chapitre 1 : Réseaux de capteurs

-Qualité de service : le délai des applications temps réel est un facteur crucial. La qualité du
service peut être atteinte en assurant un bon taux de délivrance des messages tout en garantissant
une meilleure qualité des informations mesurées et transportées [4].
-Tolérance aux fautes : ce paramètre est directement lié à l’aspect matériel et software. Divers
points sont à prendre en considération : épuisement de l’énergie des capteurs, interférences et des
capacités de calcul très limitées. La solution pratique consiste à faire un déploiement redondant
[4,5].
-Passage à l’échelle : lors de l’ajout de capteurs, le réseau est sensé fournir le même service [5].
-Durée de vie : la définition la plus connue de la durée de vie c’est l’intervalle de temps qui
sépare l’instant de déploiement de l’instant où le premier capteur épuise son énergie. Elle doit
être maximisée puisque le remplacement des batteries des capteurs n’est pas toujours pratique
[4].
Quelques mécanismes sont disponibles pour atteindre ces objectifs. On peut citer les
communications multi-sauts qui permettent de réduire la consommation énergétique, l’auto-
configuration des paramètres et la collaboration afin de bien décider sur l’apparition d’un
évènement [4].

8. Applications des réseaux de capteurs

Les caractéristiques des réseaux de capteurs leur permettent de couvrir une gamme importante
d’applications qui peuvent être orientées temps, évènements, requêtes ou hybrides. On parle
d’applications orientées temps si un instant précis est spécifié pour l’acquisition des données. La
deuxième classe concerne le cas d’envoi des données lorsqu’un évènement spécifique se
produise. Des fois, les nœuds capteurs ont besoin d’envoyer des données seulement si la station
de base le demande. Enfin, on peut envisager une application hybride dont le mode d’envoi des
données combine une ou deux stratégies de celles énoncées auparavant.
-Applications militaires : les réseaux de capteurs sont faciles à déployer et peuvent s’auto-
configurer [7]. De plus, la destruction d’un nœud dans un environnement hostile n’affecte pas les
autres. Ces caractéristiques favorisent l’utilisation des réseaux de capteurs pour la surveillance
des troupes, champs de bataille, guidage des missiles, détection d’attaques nucléaires,… Dans ce
cadre, SmartDust est un projet qui a été financé par DARPA où l’information est obtenue à partir
des mouvements des ennemies et la détection d’agents chimiques [5].
-Applications environnementales : il peut s’agir de la surveillance des animaux ou le suivi des
conditions de l’environnement (telles que la détection des altérations dans une structure d’un
bâtiment [7], la collecte des informations sismiques qui peuvent avoir lieu à côté des volcans en
s’appuyant sur des capteurs sismiques et acoustiques ou la détection des tempêtes de sable). Par
exemple, une recherche sur le microclimat des arbres géants a été menée en déployant un réseau
de capteurs. Les capteurs sont munis de petites stations météorologiques afin d’étudier les
variations microclimatiques suivants les régions d’une forêt.

  15
Chapitre 1 : Réseaux de capteurs

-Applications médicales : CodeBlue est un projet à l’université Harvard. Son objectif est le
déploiement des capteurs afin de surveiller la saturation de l’oxygène dans le sang, les activités
électriques et musculaires chez des patients tout en ayant la possibilité d’accéder à ces
informations à travers des PDA [5].

9. Pile protocolaire d’un réseau de capteurs

La figure suivante schématise les différentes couches de la pile protocolaire [5].

Application  Gestion  Gestion   Gestion  

Transport  de  de   des  

l’énergie  la mobilite  tâches 

Réseau 

Liaison 

Physique 

Figure 4. Pile protocolaire d’un réseau de capteurs.

-Couche physique : elle est responsable de la sélection de la fréquence, la détection des signaux
et la modulation.
-Couche liaison : effectue le multiplexage des données, détecte les frames et sert d’accès au
medium.
-Couche réseau : décide du routage des paquets en fonction des requêtes, évènements,…

-Couche transport : elle est requise lorsque le réseau est accessible à travers Internet ou un autre
réseau.
-Couche application : spécifie le code de l’application.

Les plans de gestion de l’énergie, de la mobilité et des tâches surveillent la puissance, le

mouvement et la distribution des tâches.

10. Protocoles de routage dans les réseaux de capteurs

  16
Chapitre 1 : Réseaux de capteurs

Acheminer des paquets des données d’une ou plusieurs sources vers une ou plusieurs
destinations est la tâche assurée par la couche réseau de la pile protocolaire. Cependant, diverses
contraintes liées aux réseaux de capteurs impliquent la conception de nouveaux protocoles de
routage qui diffèrent de ceux dédiés aux réseaux ad hoc. En effet, les protocoles de routage dans
les réseaux de capteurs doivent [5]:
-Etre basés sur un échange réduit de messages vue les contraintes énergétiques et celles de calcul
et de capacité mémoire.
-Supporter un nombre élevé de capteurs dont les adresses peuvent être inconnues lors du
déploiement.
-Etre robustes puisque tous les nœuds capteurs peuvent jouer le rôle de routeurs.

-Opérer dans des topologies qui soient même aléatoires.

Les techniques de routage présentées dans la littérature regroupent : l’inondation, routage

hiérarchique, géographique et cross-layer.

10-1. Inondation

L’idée de l’inondation est intéressante dans les réseaux de capteurs denses où il est impossible
d’affecter des adresses aux nœuds capteurs. Dans ce contexte, la source diffuse des paquets à ses
voisins et tout nœud qui reçoit ce paquet doit à son tour le diffuser à ses voisins. Ce processus se
répète jusqu’à ce que la destination puisse avoir les paquets de la source. Le problème de cette
technique est qu’elle nécessite des ressources de calcul importantes. En pratique, on peut penser
à contrôler l’opération de diffusion.

10-2. Gossiping

Un des problèmes de la diffusion est lié à la réception de la même copie du paquet par
plusieurs nœuds capteurs et à un moment donné, on peut observer diverses copies du même
paquet en train de circuler dans le réseau. Le gossiping a résolu ce problème en sélectionnant un
seul nœud pour relayer le paquet. De cette façon, la consommation énergétique sera faible en
comparaison à l’inondation.

10-3. SPIN

[Link] et al. [5] ont développé un protocole de routage dont le principe se base sur la diffusion
et la négociation. Ce protocole fonctionne comme suit : avant de procéder à l’envoie des
données, un nœud avertit ses voisins en transmettant un paquet ADV (advertise) qui contient des
meta-données. Le nœud qui s’intéresse répond par un message request (REQ). Enfin, le paquet
de données est envoyé. Un avantage de ce protocole est lorsqu’un nœud constate que sa batterie

  17
Chapitre 1 : Réseaux de capteurs

est au-dessous d’un certain seuil, il cesse de participer dans le protocole. Autrement dit, il ne
répond plus aux ADV reçus.

B B B

AD
C AD C RE C DATA 

A A A
AD

D AD D D

E E E

Figure 5. Principe du protocole SPIN.

Par exemple la figure ci-dessus montre les étapes du protocole SPIN. Dans cet exemple, seul le
nœud C est intéressé aux données.

10-4. Routage hiérarchique

Considérons un réseau de capteurs contenant plusieurs sources et adoptant l’inondation comme

technique de routage. Dans ce cas, les nœuds qui soient proches de la destination consomment
une énergie importante et leurs batteries peuvent être épuisées rapidement. Pour cela, on a pensé
à regrouper les nœuds capteurs en clusters ; chacun d’entre eux est dominé par un cluster-head.
Le problème majeur de cette technique est le manque de robustesse si les clusters heads tombent
en panne. Dans Leach [5], les cluster head sont sélectionnés de manière dynamique. Le protocole
opère en cycles. Dans chaque cycle, des cluster heads sont élus, les clusters sont formés et la
communication est établie entre eux.

[Link] géographique

Cette technique exploite les positions des capteurs obtenues soit par système GPS soit par
localisation. Des règles simples sont utilisées pour acheminer les paquets. L’inconvénient majeur
de cette technique concerne les erreurs de localisation. On trouve deux variantes pour le routage
géographique [9] :
-Routage par voisinage: les algorithmes de routage greedy basent leur raisonnement sur la
trajectoire à vol d’oiseau entre une source et une destination. Le principe consiste à acheminer le

  18
Chapitre 1 : Réseaux de capteurs

message par le biais du meilleur voisin qui soit proche de la destination en termes du progrès,
distance ou angle est sélectionné. Ce procédé est répété jusqu’à ce que la destination soit atteinte.
Par exemple, le voisin A minimise l’angle par contre B minimise le progrès et la distance.
L’efficacité de cette technique, en terme du taux d’acheminement des messages est liée à la
densité réseau. De plus, la consommation énergétique est une contrainte inhérente aux réseaux de
capteurs ; d’où l’idée d’envoyer les paquets réseau au voisin qui minimise la dépense
énergétique. Le travail présenté dans [10] traite conjointement deux problèmes complexes qui
sont étroitement liés et dont la résolution simultanée est fonction de diverses contraintes. Il s’agit
de localiser des capteurs mobiles et d’effectuer un routage géographique efficace en énergie.

-Routage par face : définit une forme géométrique afin d’éviter le problème des trous qui se pose
dans le routage greedy. Evidemment, la forme construite doit inclure l’ensemble des nœuds du
réseau. Lorsqu’un nœud capteur envoi un message à une destination, le message sera transmis le
long des faces de ce graphe qui intersectent la droite passant par la source et la destination. Un
problème de complexité de la construction du graphe est à prendre en compte.

A Dis(A,D) 

Prog(A,D)

S Prog(B,D) D

Dis(B,D) 
B

Figure6. Principe du routage géographique.

-CFG (greedy- face-greedy) : cette catégorie a été proposée afin de combiner les avantages des
de techniques citées plus haut. Le principe ici est de procéder par routage greedy et de basculer
au routage par face dès la présence d’un trou.

[Link] cross-layer

Les études récentes ont montré que l’intégration des fonctionnalités de deux ou trois couches
de la pile protocolaire permet de diminuer considérablement la consommation énergétique. La
tendance actuelle consiste à mettre en œuvre des protocoles de routage qui tiennent compte du

  19
Chapitre 1 : Réseaux de capteurs

fonctionnement de la couche MAC et/ou physique [5]. Par exemple, acheminer les paquets en
tenant compte du fait que les nœuds capteurs peuvent être mis en veille [6] constitue une
thématique de recherche très intéressante. De plus, l’influence des conditions du canal lors du
routage est un autre problème d’un intérêt important. I-F. Akyildiz et al. [5] ont conçus un
protocole avantageux d’un point de vue latence, énergie et complexité. Un seul module a été
défini tel que chaque nœud possédant des données diffuse un paquet spécial dans le but
d’indiquer à ses voisins qu’il possède un paquet. La décision de la participation d’un voisin
dépend de quatre paramètres : la puissance du signal reçu, la congestion, le dépassement de
capacité au niveau du buffer et l’énergie résiduelle. Ce protocole a été comparé à quelques
configurations s’appuyant sur le routage géographique et l’inondation et adoptant un protocole
MAC (SMAC, CSMA,…).

11. Pourquoi la récupération d’énergie dans les réseaux de capteurs ?

Par définition, la récupération d’énergie est le processus qui consiste à obtenir l’énergie à partir
de l’environnement externe (lumière solaire et artificielle, mouvements vibratoires, chaleur,
rayonnement électromagnétique,…) et de transformer cette énergie en une énergie électrique
directement exploitée par les nœuds capteurs [11]. Les premiers nœuds capteurs étaient munis de
petites batteries et la durée de vie est ainsi limitée. On a donc pensé à remplacer les petites
batteries par d’autres qui soient plus puissantes mais le coût et de la taille des capteurs étaient
deux paramètres à prendre en charge. D’autre part, quelques réflexions ont abordé les
problématiques liées aux réseaux de capteurs tout en spécifiant la maximisation de la durée de
vie comme fonction objective. Cependant, la durée de vie reste toujours limitée et bornée. Une
autre alternative a récemment émergé et consiste à intégrer un système de récupération d’énergie
dans chaque nœud capteur. Présentement, des solutions spécifiques pour quelques applications
existent mais aucun standard n’a été mis en œuvre. Citons par exemple, ZebraNet qui est un
réseau de capteurs mobiles où les capteurs sont équipés par un système GPS pour le suivi des
zèbres et leur habitat. Il est basé sur des cellules solaires. En d’autres termes, la récupération
d’énergie permet :
-maximiser la durée de vie du réseau.
-Des avantages économiques en évitant les coûts non négligeables de remplacement des
batteries.
-Avoir des capteurs autonomes.

12. Architecture d’un nœud

A côte des composants déjà cités en section 3, chaque nœud du réseau doit inclure un système
de récupération et de conversion de l’énergie. Dans ce cas, deux possibilités sont offertes.

  20
Chapitre 1 : Réseaux de capteurs

Figure 7. ZebraNet.

Système de  Système de  Capteur 

récupération  récupération 

Capteur 
Composant de  Composant de 
stockage  stockage secondaire 

Figure 8. Architectures d’un système de récupération d’énergie

Dans le premier cas illustré en figure 8, le système de récupération d’énergie alimente

directement le capteur qui soit opérationnel tant que l’énergie récupérée dépasse le minimum
requis pour son fonctionnement.
Dans le second cas, l’énergie récupérée est tout d’abord sauvegardée avant toute éventuelle
utilisation. Dans ce contexte, le composant de stockage peut être dupliqué pour servir de backup
en cas de problème de décharge. L’avantage majeur de cette architecture est que tout excès
d’énergie sera sauvegardé et exploité plus tard. Notons que le composant de stockage (buffer) a
généralement une capacité limitée et des mécanismes de gestion de l’énergie sont préconisés
[11].

  21
Chapitre 1 : Réseaux de capteurs

13. Sources énergétiques et technologies des batteries

Différentes sources d’énergie peuvent être exploitées et chacune possède ses propres
caractéristiques. De manière générale, les sources énergétiques peuvent être classées en [12]:
-Contrôlables ou non contrôlables : les sources d’énergie contrôlables fournissent l’énergie des
qu’elle soit requise. Cependant, les sources non contrôlables permettent de récupérer l’énergie
seulement si elle est disponible. Dans ce cas, un modèle de prédiction de l’énergie est nécessaire.
Si le modèle de prédiction est complexe on parle de source non contrôlable et imprédictible. Les
ondes radio fréquences sont partiellement contrôlables puisque la quantité d’énergie produite
n’est pas déterministe et elle dépend des caractéristiques de propagation.
-Ambiante : l’énergie ambiante est celle obtenue à partir de l’environnement externe. Une autre
catégorie représente l’énergie récupérée à partir du corps humain.

Source énergétique Caractéristiques

Solaire Ambiante, incontrôlable, prédictible

Vent Ambiante, incontrôlable, prédictible

RF Ambiante, partiellement contrôlable

Chaleur du corps et pression du sang Incontrôlable, imprédictible

Enfoncement d’un bouton Contrôlable

Vibrations dans un environnement indoor Ambiante, incontrôlable, imprédictible

Tableau 2. Sources énergétiques et leurs caractéristiques.

Chaque source énergétique adopte un mécanisme pour la conversion de l’énergie récupérée. On

peut citer [13]:

-Effet photovoltaïque : les cellules solaires exploitent l’effet photovoltaïque pour convertir la
lumière du soleil en une énergie électrique. Le composant principal de ces cellules est le
silicium. Dès que les cellules sont exposées au soleil, les électrons échappent du silicium puis un
flot est créé.
-Effet thermique : un voltage est créé en présence d’une différence d’énergie entre deux métaux
ou semi-conducteurs. Par exemple, ThermoLife est un petit générateur qui offre une puissance de

  22
Chapitre 1 : Réseaux de capteurs

10-100 MW pour une température de quelques Kelvins. ThermoLife a un diamètre de 1cm et

une hauteur de 1.4mm.
-Effet vibratoire : génère un potentiel électrique par conversion d’une énergie mécanique. Le
mécanisme piézoélectrique est une sous-catégorie qui tire profit des caractéristiques de quelques
matériaux dont les cristaux deviennent électriquement polarisés lorsqu’ils sont soumis à une
force mécanique. La chaussure générant de l’énergie pendant la marche et qui a été développée
par l’équipe MIT Media laboratory représente le prototype le plus marquant qui convertit
l’énergie mécanique en une énergie électrique.
Une fois l’énergie a été récupérée à partir d’une source, on a besoin de batteries rechargeables
présentant une bonne capacité, durée de recharge et vitesse de rechargement. Les batteries à base
du LI-ion constituent un bon choix technologiques.

14. Gestion de l’énergie récupérée

La thématique des réseaux de capteurs classiques concerne la minimisation de la

consommation énergétique ou la maximisation de la durée de vie du réseau. Dans les réseaux de
capteurs pouvant récupérer de l’énergie à partir de l’environnement externe, deux visions sont
possibles : traiter l’énergie récupérée comme un supplément et maximiser donc la durée de vie
ou bien trouver des mécanismes pour adapter la puissance de transmission en fonction de
l’énergie récoltée. Nous décrivons ci-dessous les règles nécessaires dans le dernier cas [12].

Considérons que la source énergétique fournit une puissance PS (t) et que la puissance
consommée est Pc (t) . Trois cas peuvent être distingués pour modéliser le comportement
d’un système de récupération de l’énergie.
-Aucun stockage de l’énergie : le système peut opérer à tout instant si :

Ps (t) ≥ Pc (t) ∀t (1)

-Buffer idéal :

Dans le cas d’un buffer idéal

t t
∫ Pc dt ≤ ∫ Ps dt + B 0 (2)
o o

Tel que B0 représente la quantité initiale d’énergie.

-Buffer non idéal :

t t t
B 0 + η ∫ [Ps - Pc ]+ dt - ∫ [Pc - Ps ]+ dt - ∫ Pleak dt ≤ B (3)
o 0 0

  23
Chapitre 1 : Réseaux de capteurs

B : Capacité du buffer.

η : Efficacité du chargement.

Pleak : Puissance de décharge.

⎧ x si x > 0
[x] + = ⎨ (4)
⎩ 0 si x <= 0

15. Routage avec récupération d’énergie

La récupération d’énergie est un domaine qui se trouve à l’intersection de l’électronique et

l’informatique. Cependant, la plupart des travaux s’intéressent à la fabrication de systèmes
autonomes qui soient aptes à récupérer et à convertir l’énergie.
La présente section donne un aperçu des travaux de recherche qui se sont focalisés à formuler et
à résoudre le problème du routage dans les réseaux de capteurs en considérant la récupération
d’énergie.
Dans [14], les auteurs ont proposé une formulation cross-layer qui inclut le routage et
l’ordonnancement où plusieurs stations de base sont présentes. Le système fonctionne selon des
slots de temps. Chaque nœud capteur peut être actif ou passif dans un slot. Dans l’état passif, un
nœud peut uniquement récupérer de l’énergie et ne participe pas dans les transmissions ou les
réceptions. La technique de routage adoptée est celle d’inondation limitée (muslticast). Divers
paramètres ont permis de conclure les performances de la solution proposée.
Dans [15], le routage considéré s’appuie sur une topologie arbre mais chaque capteur peut avoir
plusieurs parents afin de pouvoir sélectionner le meilleur chemin en termes de latence. Chaque
nœud contrôle l’énergie consommée par rapport à celle récupérée.
Quelques d’autres travaux ont abordé le routage opportuniste sous l’hypothèse de récupération
d’énergie. En fait, la première idée du routage opportuniste a été publiée en 2008 et constitue une
bonne solution pour dépasser quelques problèmes de la transmission sans fil. D’ailleurs, le
chapitre suivant de ce manuscrit va détailler le principe du routage opportuniste.

16. Conclusion

La consommation énergétique dû aux communications est à l’origine de divers problèmes dans

les réseaux de capteurs. Ainsi, plusieurs applications critiques ne tolèrent pas que des capteurs
déployés ne maintiennent pas leurs charges. La proposition de protocoles efficaces en énergie est
donc l’atout majeur dans les réseaux de capteurs. Plus précisément, les protocoles de la couche
réseau, Mac et physique doivent tenir en compte de :
-consommation énergétique.

  24
Chapitre 1 : Réseaux de capteurs

-Les capacités limitées en termes de calcul et de mémoire.

D’autre part, la technologie actuelle de récupération d’énergie permet d’augmenter les capacités
énergétiques des capteurs mais il est primordial de bien utiliser cette énergie vue les
caractéristiques des sources énergétiques.
Après cet état de l’art concernant les réseaux de capteurs et la récupération d’énergie, nous allons
se focaliser sur la couche réseau. En particulier, le routage opportuniste est une nouvelle idée qui
prend en compte les erreurs de transmission. Le routage opportuniste et le codage réseau linéaire
aléatoire feront donc l’objet du chapitre suivant.

  25
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

1. Introduction

Pour assurer des communications dans les réseaux sans fil, de nombreux protocoles de routage
existent et ont été suffisamment testés. Le problème crucial de ces protocoles et qu’ils ne
tiennent pas compte des erreurs de transmission. En exploitant la diversité spatiale et la
caractéristique de diffusion des réseaux sans fil, le routage opportuniste choisit le prochain voisin
en fonction des critères de proximité par rapport à la destination. Le protocole le plus connu
s’appelle MORE. Ce dernier tire profit des avantages du codage réseau aléatoire afin d’éviter la
coordination entre les nouds. Il opère sur les vecteurs de codes, ignore tout vecteur qui ne soit
pas innovant et code chaque nouvelle transmission. Ceci favorise son utilisation dans des réseaux
de capteurs ayant de faibles ressources énergétiques. Ce chapitre porte donc sur le routage
opportuniste et donne en parallèle un aperçu concernant les champs de Galois qui sont souvent
utilisés dans le codage réseau aléatoire.

2. Définition d’un champ

C’est une structure algébrique munie des opérations (+ ,- , * , /) et préservant les règles
connues. Plus spécifiquement, si F est un champ associé des opérations d’addition (+) et de
multiplication (.) alors [16]:

1‐ a + (b + c) = (a + b) + c //Associativité de l’addition

2‐ a + b = b + a //Commutativité

3‐ Il y a un élément 0 tel que ∀ a a + 0 = 0

4‐ ∀ a ∃ (-a) Tel que a + (-a) = 0

5‐ a.(b.c) = (a.b).c //Associativité de la multiplication

6‐ a.b = b.a //Commutativité de la multiplication

7‐ Il existe un élément 1 diffèrent de zéro tel que a.1 = a ∀ a

8‐ ∀ a ≠ 0, ∃ a −1 Tel que a.a -1 = 1

9‐ a.(b + c) = a.b + a.c //Distribution de la multiplication par rapport à l’addition

L’ensemble des réels et celui des complexes sont des exemples de champs.
La notation Z p réfère à l’ensemble des entiers {0,1,2,... , p − 1} en utilisant l’arithmétique modulo p .

Si p est premier alors Z p est un champ et toutes les propriétés énoncées ci-dessus sont vérifiées.

  26
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

Par exemple, les tables suivantes montrent l’opération d’addition et de multiplication dans le
champ Z 7 .  

+ 0 1 2 3 4 5 6 . 0 1 2 3 4 5 6

0 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0

1 1 2 3 4 5 6 0 1 0 1 2 3 4 5 6

2 2 3 4 5 6 0 1 2 0 2 4 6 1 3 5

3 3 4 5 6 0 1 2 3 0 3 6 2 5 1 4

4 4 5 6 0 1 2 3 4 0 4 1 5 2 6 3

5 5 6 0 1 2 3 4 5 0 5 3 1 6 4 2

6 6 0 1 2 3 4 5 6 0 6 5 4 3 2 1

Table1.a. Addition dans le champ Z7. Table1.b. Multiplication dans le champ Z7.

3. Champs de Galois

Sont très utilisés dans les opérations de codage et de cryptographie. Les propriétés
fondamentales des champs de Galois ont été découvertes par le mathématicien Français Galois.
Si p est premier alors GF(p m ) est composé des polynômes de degré (m − 1) définis dans le
champ Z p . La forme générale d’un polynôme est [17]:

⎧⎪a m −1x m −1 + ... + a1x1 + a 0 x 0

⎨ (1)
⎪⎩a i ∈ {0,1,...p − 1}

Dans la pratique on se limite souvent à p= 2 .

La construction d’un champ de Galois est obtenue à partir d’un polynôme primitif qui dépend de
m . Ainsi, la table suivante spécifie les polynômes primitifs pour m= 3,...,10

  27
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire
m P ( x)

3 1 + x + x3

4 1+ x + x4

5 1 + x2 + x5

6 1+ x + x6

7 1 + x3 + x7

8 1 + x 2 + x3 + x 4 + x8

9 1 + x4 + x9

10 1 + x 3 + x 10

Table2. Exemples de polynômes primitifs.

4. Addition et multiplication dans GF(2 m )

L’opération (p 1 + p 2 ) consiste à additionner les coefficients de p 1 et p 2 .

Pour la multiplication, le résultat peut être en dehors du champ et il est donc nécessaire de
considérer (p 1 .p 2 )modp .

Nous allons donc expliquer ces deux opérations à travers un exemple dans GF(2 3 ) dont la
représentation des polynômes est donnée en table 3.a et le résultat de l’addition est illustré en
table 3.b. Prenons par exemple l’addition de x 2 + x + 1 , x + 1 et x 2 + 1 ainsi que la multiplication
de ( x 2 + 1 ) et ( x 2 + x ). Ces opérations peuvent être effectuées comme suit [16]:

x2 + x +1 x2 + 1

0 + x +1 x2 + x

x2 + 0 +1

0 0 1 x3 + x

x4 + x2

  28
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

x4 + x3 + x2 + x 1 + x + x3

x4 + x2 + x

x3 x

Décimal Binaire Polynomiale + 0 1 2 3 4 5 6 7

0 000 0 0 0 1 2 3 4 5 6 7

1 001 1 1 1 0 3 2 5 4 7 6

2 010 x 2 2 3 0 1 6 7 4 5

3 011 x +1 3 3 2 1 0 7 6 5 4

4 100 x2 4 4 5 6 7 0 1 2 3

5 101 x2 +1 5 5 4 7 6 1 0 3 2

6 110 x2 + x 6 6 7 4 5 2 3 0 1

7 111 x2 + x +1 7 7 6 5 4 3 2 1 0

Table3. a. Représentation polynomiale. Table 3.b. Addition dans GF ( 2 3 ) .

5. Codage réseau

Le codage réseau est un nouveau paradigme qui a attiré l’attention des informaticiens et
électroniciens. L’idée principale consiste à permettre aux nœuds du réseau de traiter les paquets
reçus (effectuer une addition binaire) avant de les envoyer. Ceci permet d’accroitre
considérablement le débit des transmissions. Afin d’avoir une idée préliminaire à propos du
codage réseau, nous allons considérer le réseau illustré en figure 1 où les nœuds représentent des
terminaux et les liens représentent des canaux de transmission. Deux sources S1 , S 2 et deux
destinations R 1 , R 2 sont présentes. Le temps est divisé en slots et chaque canal peut envoyer
1bit/slot. La source S1 peut générer un seul bit/slot qui est dénoté par x 1 et la source S 2 peut
générer un seul bit/slot qui est dénoté par x 2 [18].

Si seul R 1 utilise le réseau, elle peut obtenir x 1 , x 2 à travers A − D et B − C − E − D .

  29
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

Pareil, si seul R 2 utilise le réseau, elle peut obtenir x1 , x 2 à travers B − C − E − F et B − F .

Le problème se pose dès que R 1 , R 2 s’intéressent en parallèle à obtenir x 1 , x 2 . Le codage

réseau a résolu ce problème en transmettant x 3 = x 1 + x 2 de cette manière R 1 reçoit ( x 1 , x 3 )
et R 2 reçoit ( x 2 , x 3 ) et chacun d’entre elles peut résoudre un système d’équations.

S1  S2  S1  S2  S1  S2 

A  B  A  B A B 

C  C C 

x1+x2

D  F  D  F C F 

R1 R2 R1 R2 R1 R2
E  E
E 

Figure 1. a. Routage vers R1. Figure 1.b. Routage vers R2. Figure 1.c. Multicast avec codage réseau.

5-1. Avantages du codage réseau

A côté de l’amélioration du débit de transmission qui a été montrée à travers l’exemple

introductif, deux avantages clés doivent être mentionnés [18].

-Minimisation des ressources énergétiques : soit le réseau ad hoc de la figure 2 où A et C veulent

échanger x 1 , x 2 en utilisant B comme relais. Le temps est divisé en slots et chaque équipement
peut transmettre ou recevoir dans un slot. Avec le codage réseau, B fait une seule transmission
contenant x 1 + x 2 au lieu d’en faire deux et ceci permet un gain énergétique important.

  30
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

-Sécurité : supposant qu’un nœud attaquant tente d’écouter les transmissions faites sur le chemin
A − B − D ou A − C − D . Avec le codage réseau, la présence d’un attaquant ne va pas dégrader les
performances du système en termes de sécurité puisqu’il est impossible de décoder n’importe
quelle partie des données.

A  x1 B  C A x1 B C

x1 x1 x2
A  B  C A B C

A  B  x2 C A x1 + x2 B x1+ x2 C

A  B  C
x2 x2

Figure2.a. Echange de x1 et x2 sans codage réseau. Figure 2.b. Echange de x1 et x2 avec codage réseau.

B  B
x1 x1 x1+x2 x1+x2

A  D D
A

x2 x2
C  C
x1+2x2 x1+2x2

Figure 3.a. Envoi des données sans codage réseau. Figure 3.b. Envoi des données avec codage réseau.

  31
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

5-2. Théorème du codage réseau

Soit G un graphe. Une coupe est une division des nœuds en deux sous-ensembles. Elle est
caractérisée par sa taille qui est le nombre de liens traversant la coupe. Le théorème du codage
réseau affirme que le débit observé au niveau de chaque nœud du réseau est égal à la valeur de la
coupe minimale entre la source et le nœud concerné. Ce débit peut être atteint par codage réseau
[19].

S
.
S

A B 

T w
C

E F 
D
Coupe= 3 coupe = 2 coupe =2

Figure 4.a. Taille de la coupe au niveau de D. Figure 4.b. Taille de la coupe au niveau de E et F.

6. Codage réseau linéaire aléatoire

L’un des problèmes du codage réseau est qu’il est difficile de l’utiliser dans des topologies
aléatoires, variables ou denses. Une autre réflexion a été proposée par [20] et consiste à effectuer
des combinaisons linéaires aléatoires des paquets dans un champ fini ; le plus souvent le champ
de Galois. Considérant n paquets M 1 , M 2 ,..., M n générés par une ou plusieurs sources. Chaque
paquet est associé à un vecteur de coefficients g = (g 1 , g 2 ,..., g n ) dans GF(p n ) . Chaque nœud choisit
les coefficients de façon indépendante et décentralisée. De plus, les paquets peuvent être
recombinés par les nœuds intermédiaires. La figure 4 montre que la source a diffusé un paquet
combiné (g 1 , X 1 ) .

g 1 Est le vecteur code.

  32
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

n
X1 = ∑ g i M i (2)
i =1

Le nœud C a procédé à une combinaison des deux paquets reçus et a diffusé (X ' , g ' ) tels que :

⎧ 2

⎪⎪ X' = ∑j=1
h jX j
(3)
⎨ 2
⎪ g' = ∑ h j g i j
⎪⎩ j=1

M 1 , M 2 ,..., M n

g 1 M 1 + g 2 M 2 + ...g n M n g 1 M 1 + g 2 M 2 + ...g n M n

A  B

h 1 (g 1 M 1
+ g 2M 2 + ...g n M n ) +
h 2 (g 1 M 1
+ g 2M 2 + ...g n M n )

E  F

Figure 5. Principe du codage réseau linéaire aléatoire.

7. Pourquoi et c’est quoi le routage opportuniste ?

C’est un nouveau mécanisme de routage dédié aux réseaux mesh dont le taux d’erreur de
transmission est considérable. Dans le routage traditionnel, on sélectionne le prochain voisin
avant la transmission mais ceci implique des problèmes de réception si les liaisons sont soumises
à des erreurs. Le routage opportuniste exploite la diffusion qui existe dans les réseaux sans fil tel

  33
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

que chaque nœud qui arrive à surprendre un paquet et soit proche de la destination est apte à
participer dans l’envoi des paquets reçus. La technique la plus récente du routage opportuniste
est basée sur le codage réseau telle que la source diffuse ses paquets et les routeurs créent une
combinaison linéaire aléatoire des paquets reçus. Enfin, la destination envoi un acquittement
suivant le chemin inverse en cas où tous les paquets ont été reçus [21].

0.49 1/0.49

S  1.1 R 1.1 1.1 D S 1/1.0 R 1/1.0 D

P1,P2 P1

Figure 6.a. Exemple d’un réseau. Figure 6.b. Métrique ETX de chaque chemin.

Dans l’exemple précèdent, on suppose que S a diffusé deux paquets P1, P2. R a reçu P1, P2 par
contre D a uniquement reçu P1. Dans ce cas, R n’a pas besoin de retransmettre P2 mais peut
directement envoyer P1 + P2 . Deux questions principales sont à noter :
-Combien de paquets faut-il envoyer de sorte à garantir qu’au moins un nœud puisse recevoir un
paquet ?

-Comment peut-on réduire la complexité des opérations d’additions et de multiplication ?

7-1Métrique ETX

Le raisonnement de base du routage opportuniste s’adapte bien à des réseaux sans fil soumis à
des phénomènes physiques entraînant des erreurs de transmission des bits même en absence des
collisions. La solution classique à ce problème s’appuie sur les retransmissions au niveau de la
couche liaison et l’envoi d’un acquittement une fois le décodage est réussi. Ce mécanisme est
inapproprié dans le cas où la diffusion est un principe de base. Pour cela, le routage opportuniste
adopte bien la métrique ETX ‘expected number of transmissions’ pour délivrer un message. En
fait, l’ETX est inversement proportionnelle au taux d’erreur. Par exemple le nombre de
transmissions attendu suivant le chemin (S-R-D) de la figure 4.b est égale a 1/1.0+1/1.0=2 .
Cependant, le nombre de transmissions attendu suivant le chemin (S-D) est 1/0.49=2.04 > 2 [22].

7-2 Protocol EXOR

  34
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

C’est le premier protocole de routage opportuniste et d’autres voies de réflexions ont été
conçues après sa mise en œuvre. EXOR dépend de la couche Mac et assure ainsi le routage et
l’ordonnancement des transmissions afin d’éviter les problèmes de collision. Partant de
l’exploitation du principe de la diffusion dans un réseau sans fil contenant une seule source et
une seule destination, ce protocole suit les étapes suivantes [23] :
-la source prépare un batch de paquets à diffuser. Elle doit également établir une liste de priorités
concernant les nœuds pouvant participer dans la transmission. La priorité est basée sur la
métrique ETX.

-La réception d’un paquet par un nœud n’appartenant pas à la liste des nœuds concernés par la
transmission provoque son ignorance. Dans le cas contraire, le paquet est stocké dans un buffer
et un ordonnancement est assuré. Le nœud le plus prioritaire est autorisé à transmettre en premier
et chaque nœud maintient un compteur qui lui permet d’estimer l’instant adéquat pour la
transmission. Si un paquet a été déjà transmis par un nœud prioritaire, les autres nœuds doivent
le supprimer de leurs espaces de stockage et donc la possibilité qu’un paquet soit retransmis
plusieurs fois est faible.
-Des que la destination reçois un pourcentage élevé (90%) des paquets du batch, un autre cycle
est déclenché.

8. Protocole MORE ’Mac independant and Opportunistic routing’

C’est un protocole pour les réseaux mesh statiques. Il est situé entre la couche IP et la 802.11.
Son principe peut être résumé par les opérations effectuées au sein de chaque nœud du réseau
[21].
-Source : divise le fichier à transmettre en batchs de K paquets et lorsque la 802.11 autorise
l’envoi des paquets, la source crée une combinaison linéaire aléatoire des K paquets et diffuse
P' = ∑ C i Pi tels que C i , i = 1 ... K représentent des coefficients aléatoires générés à partir d’un
i =1..k

champ de Galois. Chaque paquet envoyé contient l’IP de la source, la destination et la liste des
nœuds pouvant participer dans la transmission en s’appuyant sur l’estimation de la métrique
ETX.
-Nœuds intermédiaires : à la réception d’un paquet, le nœud concerné vérifie s’il appartient à la
liste des nœuds devant participer dans la transmission. Dans ce cas, la vérification du contenu du
paquet est exécutée. Il s’agit de tester si le paquet est innovant (porte une nouvelle information
ou non). Plus particulièrement, un paquet est innovant s’il est linéairement indépendant des
autres. Par la suite, si un nœud j a reçu des paquets de la forme P' = ∑ C ji Pi , il crée une
i

combinaison linéaire aléatoire de tous les paquets reçus P '' = ∑ R j P ' j .

j

-Destination : de même, la destination vérifie si les paquets reçus sont innovants et lorsque K
nouveaux paquets ont été reçus, le processus de décodage aura lieu par l’inversion de la matrice
des coefficients.

  35
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

⎛ P1 ⎞ ⎛ P1' ⎞
⎜ ⎟ ⎜ ⎟
−1 ⎜ ' ⎟
⎜ P2 ⎟ ⎛ C11 C12 . . . C1k ⎞ P
⎜. ⎟ ⎜ C ⎟ ⎜ 2 ⎟
C 22 . . . C 2k ⎟ ⎜. ⎟ (4)
⎜ ⎟ = ⎜ 21
⎜. ⎟ ⎜. . . ⎟ .⎜ ⎟
⎜ . ⎟ ⎜⎜ C ⎟ ⎜. ⎟
C k2 . . . C KK ⎟ ⎜ ⎟
⎜ ⎟ ⎝ k1 ⎠ .
⎜P ⎟ ⎜ ⎟
⎝ k⎠ ⎜P '⎟
⎝ k ⎠

A la fin, un acquittement est soumis à la source pour terminer le protocole.

8-1. Nombre de transmissions

L’heuristique utilisée par MORE est la suivante : le prochain voisin est celui qui soit proche de
la destination en termes du nombre de transmission attendu. i < j   Signifie que i est plus proche
de la destination par rapport à j [21]. Le nombre de paquets attendus au niveau du nœud j est
∑ Zi (1 − ε ij )  
i> j

Z i  : Nombre de transmissions faites par le nœud i.

ε i j : C’est le taux d’erreur sur le lien (i,j).

Plus précisément, chaque nœud maintient un compteur Cmp initialisé à 0 et il est incrémenté
suivant la formule (5) après chaque réception d’un paquet.

Zj
Cmp j = Cmp j +                                                         (5)
∑ Zi (1 − ε ij )
i> j

Si le compteur est positif, le nœud est autorisé à créer une nouvelle combinaison aléatoire des
paquets reçus et lors d’une réception, le compteur est décrémenté de 1.

8-2. Format des paquets

Les paquets manipulés par le protocole MORE sont de deux types : donnée ou acquittement
pour arrêter le processus de transmission. Chaque paquet contient donc un champ spécifiant son
type, l’adresse IP de la source et l’adresse IP de la destination. A cela s’ajoute l’identificateur du
flot généré et le numéro du batch auquel appartient le paquet. Dans le cas d’un paquet de
données, d’autres champs sont nécessaires : le vecteur des coefficients, le nombre des nœuds
concernés par la transmission, l’identificateur et le compteur de crédit associé à chacun d’entre
eux. Enfin, le résultat du codage réseau aléatoire est inséré [21].

  36
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

Type du paquet

IP de la source IP de la
destination

Id du flot

N° du batch

Vecteur des coefficients

Nombre de nœuds

Id1 Cmp1

Id2 Cmp2

Figure 7. Format d’un paquet MORE.

8-3. Test de l’indépendance linéaire

Informellement deux vecteurs V1 , V2 sont linéairement indépendants si toute combinaison

linéaire finie nulle de ces deux vecteurs a nécessairement tous ses coefficients nuls. Cela revient
à dire qu’aucun vecteur considéré n’est combinaison linéaire des autres. Prenons l’exemple des
vecteurs (2,−1,1), (1,0,1) et (3,−1,2) .  Nous constatons que (2,−1,1) + (1,0,1) = (3,−1,2) et les
trois vecteurs sont linéairement dépendants. Le test de l’indépendance linéaire est souvent mené
par l’algorithme Gauss-Jordan [24]. Soit M la matrice des coefficients. L’objectif de cet
algorithme est de maintenir une matrice triangulaire à la réception d’un nouveau paquet de
données contenant bien sûr un vecteur de codes. Evidemment, chaque vecteur reçu doit être
inséré dans la bonne ligne de la matrice M . Les transformations de l’algorithme Gauss-Jordan
peuvent être expliquées à travers l’exemple qui suit.
Si le premier vecteur reçu est (2 , - 1,1) la matrice M devient :

⎛ 1 1⎞ M(1)
M = ⎜1 - ⎟ tel que : M(1) =
⎝ 2 2⎠ 2

Le deuxième vecteur reçu (1 , 0,1) ne pourra pas être inséré en ligne 2. Par contre on peut
l’insérer en ligne 3 et matrice M devient :

  37
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

⎛ 1 1⎞
⎜1 - ⎟
⎜ 2 2⎟
M=⎜ ⎟ , tel que : M(3) = M(3) − M(1)
⎜ ⎟
⎜⎜ 0 1 1⎟
⎟
⎝ 2 2⎠

Le troisième vecteur reçu (-3 , 2,-1) peut être inséré en deuxième ligne. La matrice M a donc la
forme suivante :

⎛ 1 1⎞
⎜1 - ⎟
⎜ 2 2⎟
⎜ 1 1⎟
M = ⎜0 , tel que M(2) = M(2) + 3 * M(1)
⎜ 2 2 ⎟⎟
⎜0 1 1⎟
⎜ ⎟
⎝ 2 2⎠

⎛ 1 1⎞
⎜1 - ⎟
⎜ 2 2⎟
⎜ 1 1⎟
Reste à transformer la deuxième ligne. M = ⎜ 0 , tel que : M(3) = M(3) + M(2)
⎜ 2 2 ⎟⎟
⎜0 0 0⎟
⎜ ⎟
⎝ ⎠

Nous constatons que la matrice M contient une ligne nulle et le nouveau vecteur reçu n’est pas
linéairement indépendant des autres.
Enfin, la figure 6 explique les principales étapes du protocole MORE.

9. Protocole SOAR

Ce dernier a été présenté dans [25] afin de supporter des flots multiples. C’est un protocole de
routage proactif où chaque nœud maintient une table de routage contenant la destination, la route
sélectionnée par défaut et la liste des nœuds impliqués dans la participation. La sélection de la
route peut être basée sur la métrique ETX ou n’importe quelle autre métrique tout en tenant
compte de la priorité. A la différence de MORE, SOAR permet aux nœuds non sélectionnés et
qui soient proches de la route établie par défaut de participer dans la transmission afin de
minimiser des transmissions inutiles. Cependant, la source doit limiter le nombre de nœuds
concernés. En ce qui concerne les transmissions, SOAR procède de la même manière que le

  38
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

protocole TCP et le compteur de temps est calculé pour estimer l’instant de la prochaine
transmission.

10. Conclusion

L’exploitation de la diversité spatiale dans un environnement caractérisé par des erreurs de

transmission constitue l’idée clé du routage opportuniste. MORE est le protocole de routage
opportuniste le plus populaire. Ce dernier code chaque nouvelle transmission par le biais du
codage réseau aléatoire. Aucune synchronisation n’est nécessaire dans ce cas.
Le problème traité dans cette thèse est essentiellement basé sur le protocole MORE. Notre souci
est de reformuler ce protocole pour le cas de capteurs ayant des capacités de récupération
d’énergie à partir d’un environnement externe tout en minimisant le temps nécessaire pour
compléter l’application (terminer le décodage de tous les paquets envoyés). Le but donc du
chapitre qui suit est de présenter la technique d’optimisation utilisée avant de passer à la
description du système principal de cette thèse.

  39
Chapitre 2 : Routage opportuniste et codage réseau linéaire aléatoire

Emission Réception

Autoriser a ETX du noeud

transmettre et précèdent>ETX(i)
Cmpi>0?

Créer un paquet Incrémenter Cmpi

selon (5)

Source?
Paquet
innovant?

Cmpi Å Cmpi-1

Rejeter Stocker

Encoder

Destination et
Envoyer nombre des
paquets =K ?

Décoder

Figure 8. Principe du protocole MORE.

  40
Chapitre 3 : Optimisation F-Lipschitz

1. Introduction

Les applications potentielles de l’optimisation sont diverses. En particulier, les protocoles

spécifiques aux réseaux de capteurs définissent souvent une fonction objective à atteindre sous
un ensemble de contraintes. Cependant, la forme de la fonction objectif et l’ensemble des
contraintes peuvent être différentes d’un problème à un autre et il est toujours question de
chercher une méthode de résolution adéquate. Récemment, la méthode d’optimisation F-
Lipschitz a été proposée et cette dernière s’adapte bien aux réseaux de capteurs. Son avantage clé
est qu’elle peut être appliquée à un problème linéaire, non linéaire, convexe ou non. De plus, il
est également possible de calculer la solution de manière distribuée. L’existence de la solution
optimale est assurée par cette technique d’optimisation.
L’objectif de ce chapitre est de présenter en premier lieu l’optimisation de manière générale puis
de détailler la méthode F-Lipschitz.

2. Problème d’optimisation

Une prise de décision efficace requiert souvent un processus de formulation, modélisation et

d’optimisation du problème. Une première version du problème traité est spécifiée dans la
première étape. L’accent doit être mis sur les objectifs du problème ainsi que les facteurs qui le
caractérisent. La deuxième étape établie un modèle du problème considéré tout en s’appuyant sur
les modèles existants dans la littérature. La simplicité du modèle est un paramètre à prendre en
charge. La résolution du problème est la troisième étape qui vise à trouver une solution optimale
ou sous optimale en fonction des objectifs dressés lors de l’analyse des besoins. Ce processus
peut être itératif afin d’atteindre de bonnes performances [26].

Formulation Modélisation Optimisation Implémentation

Figure1. Processus de prise de décision.

Dans ce chapitre, on se focalise sur l’optimisation mais avant d’y aller plus loin il est nécessaire
de définir ce concept.

  41
Chapitre 3 : Optimisation F-Lipschitz

Définition

Soit cette fonction à valeurs réelles :

f(x) : F → R
x∈Rn (1)
C = {x ∈ F | g(x) ≤ 0, h(x) = 0}

L’objectif de l’optimisation est de déterminer x * ∈ F qui minimise f(x) tel que : f(x * ) ≤ f(x) ∀ x ∈ F

fDénote la fonction objective, F est l’ensemble des solutions admissibles et C est l’ensemble
des contraintes.

3. Classification des problèmes d’optimisation

Suivant la forme de f, g, h on obtient diverses classes parmi lesquelles on peut citer:

-Optimisation linéaire : dans ce cas, la fonction objective et les contraintes d’inégalités sont
linéaires.

-Optimisation convexe : la fonction objectif et les contraintes d’inégalité sont convexes. En fait,
la convexité est une propriété importante pour assurer l’existence et l’unicité de la solution.

Définition

Un ensemble C ⊂ R n est convexe si pour toute paire de points (x, y) ∈ C 2 le segment

[x, y] = (tx + (1 − t)y) , 0 ≤ t ≤ 1 est inclut dans C .

Définition

On dit qu’une fonction f est convexe si :

∀ (x, y) ∈ C 2 , ∀ t ∈ [0,1] f(tx + (1 − t)y) ≤ tf(x) + (1 − t)f(y) (2)

4. Méthodes de résolution

Résoudre un problème d’optimisation fait souvent appel aux méthodes itératives qui calculent
la solution optimale en procédant comme suit [26]:

x(k + 1) = f(x(k)), k = 0,1,..., n (3)

Où x(k) est un vecteur de dimension n.

  42
Chapitre 3 : Optimisation F-Lipschitz

Si cette séquence converge vers une limite x * et f est continue alors x * est un point fixe. La
convergence de ces méthodes peut être accélérée en exploitant le parallélisme. Un système
composé de n agents peut trouver la solution optimale selon l’équation suivante :

x i (k + 1) = f i (x 1 (k)...x n (k)), i = 0,1,..., n (4)

L’algorithme de la descente procède par une résolution itérative. Il est très utilisé pour
l’optimisation convexe. Cet algorithme fait décroître la fonction coût en appliquant des itérations
dans le sens contraire du gradient.

x(k + 1) = x(k) − γ ∇ F(x(k)) (5)

Le paramètre γ est très important pour la convergence de l’algorithme.

4-1. Méthodes par décomposition

L’idée consiste à diviser le problème en sous problèmes et de résoudre chacun d’entre eux.
Leurs solutions doivent être coordonnées pour aboutir à la solution optimale [26].

⎧ min f 1 (x1) + f 2 (x2)

⎪ (6)
⎨x 1 ∈ C1
⎪x ∈ C
⎩ 2 2

Par exemple, on introduisant une variable y qui sert d’interfaces entre les deux sous problèmes,
on transforme le problème (6) au problème (7) comme suit :

⎧ min f 1 (x 1 , y) (7)
⎨
⎩ min f 2 (x 2 , y)

Pour cela, on fixe une valeur pour y , on résout le problème puis on met à jour cette variable.

5. Fonction Lipschtiz

Avant de détailler la méthode F-Lipschtiz qui s’appuie sur les notations présentées dans le
tableau 1, il est nécessaire de définir une classe importante de fonctions nommées F-Lipschitiz.
Ces fonctions sont limitées dans leur manière d’évolution. Une fonction Lipschitz est une
fonction tel que tout segment reliant deux points du graphe d’une telle fonction aura une pente
qui soit inférieure à une certaine constante [27].

  43
Chapitre 3 : Optimisation F-Lipschitz

f :E → R
(8)
∀ (x, y) ∈ E 2 : f(x) - f(y) ≤ K. x − y

Soient deux métriques d X , d Y , une autre définition plus générale est comme suit :

d Y ( f(x) - f(y) ≤ K.d Y (x, y) (9)

Pour bien comprendre les fonctions Lipschitz ont peut par exemple penser à la fonction sin(x)
qui a comme dérivée cos( x ) . Cette dernière est toujours bornée par la valeur 1. L’exemple suivant
montre la vérification de la condition Lipschitz de manière plus détaillée.
Soit :

f(x, y) = xy 2 , x ≤ 1 et y ≤ 1 (10)

f(x, y2) − f(x, y 1 ) = xy 2 2 − xy 1 2 = x y 2 2 − y 1 2

= x y 2 + y1 y 2 − y1 (11)

= 1.2 y 2 - y 1

Notation Définition

R+ Ensemble des réels strictement positifs

. Valeur absolue d’un réel

. Norme d’une matrice

n
A 1 max n
i =1 ∑ aij
j =1

n
A ∞ max in=1 ∑ a i j
i =1

1 (1,1,...,1 ) T

D = [x 1min , x 1max ] * [x 2min , x 2max ] * ... * [x nmin , x nmax ] Vecteur des bornes des contraintes
- ∞ < x imin < x imax < ∞

  44
Chapitre 3 : Optimisation F-Lipschitz

⎧ x i , x i ∈ [min, max] Projection orthogonale par rapport à la

⎪ norme euclidienne
[x i ] D = ⎨ x i min , x i < x imin
⎪x
⎩ imax , xi > x imax

∇ Opérateur gradient

Si F(x) : R n → R n alors Gradient d’une fonction

∇F(x) = [∇F1 (x)...∇Fn (x)]

Tableau 1. Notations et définitions.

6. Problème d’optimisation F-Lipschitz

Un problème d’optimisation F-Lipschitz est de la forme [28]:

max f 0 (x)
x i ≤ f i (x) i = 1,..., l
x i = h i (x) i = l + 1,..., n
x∈D
D = [x 1min , x 1max ] * [x 2min , x 2max ] * ... * [x nmin , x nmax ] ⊂ R n
− ∞ < x imin < +∞ ∀ i = 1,... n
                                              (12)

Tels que :

f 0 (x) : D → R m m ≥1
f i (x) : D → R i = 1,..., l
h i (x) : D → R i = l + 1,..., n                                                                                                (13)

Les conditions suivantes doivent être vérifiées :

∇ f 0 (x) > 0
∇ F(x) < 1

(14.a)

Et :

  45
Chapitre 3 : Optimisation F-Lipschitz

∇ j Fi (x) ≥ 0 ∀ i, j
(14.b)

Ou :

f 0 (x) = c1 T x, c∈R +
∇ jFi(x) ≤ 0 ∀ i, j
∇ F(x) ∞ <= 1

(14.c)

Ou :
δ
∇ F(x) <
δ+Δ
∞

δ = min ix ∈D ∇ i f 0 (x)
Δ = max ix ∈D ∇ i f 0 (x)

(14.d)

Notons que :

⎡ f(x) ⎤
F(x) = ⎢ ⎥
⎣ h(x) ⎦
f(x) = [f 1 (x), f 2 (x),..., f l (x)] T
h(x) = [h l +1 (x), h l + 2 (x),..., h n (x)] T
                                                                                                        (15)                               

Un problème F-Lipschitiz peut avoir la forme centralisée ou distribuée. Dans ce cas, chaque
nœud est associé de sa variable de décision x i et la contrainte i appartient au nœud i. Il peut
s’agir également de problème d’optimisation mono ou multi-objectifs. C’est-à-dire la fonction
objectif peut être représentée par un vecteur. Le cas des variables manquantes dans la fonction
objectif n’est pas également un obstacle pour l’emploi de la méthode F-Lipschitz. Il est à noter
que la forme standard requiert une contrainte pour chaque variable. Soit le problème [30] :

max f 0 (x, z)
x ≤ f x (x, z)
⎡ x ⎤ ⎡ b x ⎤                                                                          (16)
⎢z ⎥ ≤ ⎢b ⎥
⎣ ⎦ ⎣ z⎦

  46
Chapitre 3 : Optimisation F-Lipschitz

La proposition 14 établie dans [30] nous permet d’utiliser cette transformation afin d’avoir un
nombre de variables qui soit égale au nombre de contraintes :

max f 0 (x, z)
x ≤ f x (x, z)
z ≤ f z (x, z) = b z                                                                    (17)

Exemple

Soit le problème F-Lipschitz suivant :

max(x 1 + 2x 2 )
⎧ x 1 ≤ 0.7 + ax 1 x 2
⎪ x2 ≤ 0.3(1 + x + x )
⎪⎪ 1 2
⎨0 ≤ x ≤ 1                                                                (18)
⎪
⎪0 p a p 1
⎪⎩ 2

On a :

⎡1 ⎤
∇ f 0 (x) = ⎢ ⎥ > 0
⎣2⎦
⎡ ax 0.3 ⎤                                                             (19)
∇ F(x) = ⎢ 2 ⎥ ≥ 0
⎣ ax 1 0.3 ⎦

1
∇ F(x) 1
= max( ax 2 + ax 1 , 0.3 + 0.3 ) < 1 pour x 1 = x 2 = 1 et a p
2
 

7. Problème canonique

Généralement, les problèmes d’optimisation ont la forme décrite par le système suivant [28]:

min g 0 (x)
S.t. g i (x) ≤ 0 i = 1,..., l
p i (x) = 0 i = l + 1,..., n
x ∈D                                                              (20)

  47
Chapitre 3 : Optimisation F-Lipschitz

Ce problème a la même solution optimale que le problème (12) et peut être transformé en un
problème F-Lipschitz comme suit :
max f 0 (x)
x i ≤ f i (x) i = 1,..., l
x i = h i (x) i = l + 1,..., n
x∈D

                                                 (21)     

Tels que :

f 0 (x) = − g 0 (x)
f i (x) = x i − γ i g i (x)
h i (x) = x i − μ i p i (x)
γ i > 0, μ i ∈ R

                                                             (22)

Le théorème (4.1) dans [28] établie les conditions nécessaires pour vérifier si le problème est F-
Lipschitiz. Ces conditions sont données par les équations suivantes.
∇ g 0 (x) < 0
∇ i G i (x) < 0 ∀ i                                                                                                                                           

(23.a)

Et :
∇ j G i (x) ≤ 0 ∀ j ≠ i

∇ i G i (x) f ∑ ∇ j G i (x) ∀ i
j≠i                                                                                                                      (23.b)

Ou :

g 0 (x) = − C1 T x, C ∈ R +
∇ j G i (x) ≥ 0 ∀ j ≠ i

∇ i G i (x) f ∑ ∇ i G j (x) ∀ i
j≠ i                                                                                                                    (23.c)                                   

Ou :

  48
Chapitre 3 : Optimisation F-Lipschitz

g0(x) ∈ R
δ
∇ i G i (x) f ∑ ∇ i G j (x) ∀ i
δ+Δ j≠ i                                                                                                       (23.d)

Exemple :

Soit le problème suivant :

-2
min x + 9y
3 x + 4 y 2 ≤ 12
3

5 x − 2 + 6 y − 2 x −1 ≤ 5
D = {10 − 10 ≤ x ≤ 1,10 − 10 ≤ y ≤ 1}

                                            (24)

Nous constatons que ∇ y de la deuxième contrainte n’est pas négative. Si on remplace t = y −1 ,

nous pouvons obtenir :
-2
min x + 9t -1
3 −2
3x + 4t ≤ 12
−2
5x + 6t x −1 ≤ 5
2

D = {10 −10 ≤ x ≤ 1 , 1 ≤ t ≤ 10 10 }

                                            (25)

8. Optimalité de la solution d’un problème F-Lipschitz

La solution d’un problème F-Lipschitz est une solution Pareto optimale. Ceci est énoncé à
travers le théorème suivant. Rappelons que x * est une solution Pareto optimale s’il n’existe pas x
tel que f 0 (x) ≥ f 0 (x * )

Par exemple, la solution C illustrée en figure est dominante par contre A et B sont dominées par
C.

  49
Chapitre 3 : Optimisation F-Lipschitz

Figure2. Optimalité au sens Pareto.

Théorème :

Soit un problème d’optimisation F-Lipschitz. Le problème admet une solution Pareto optimale
x * obtenue par l’ensemble des équations suivantes [29]:

⎧⎪ x i * = [f i (x * )] D , i = 1...l
⎨
⎪⎩ x i = h i (x * ) , i = l + 1...n                                                            (26) 

9. Calcul de la solution optimale

Le calcul de la solution d’un problème F-Lipschitz peut être mené selon l’une des approches
suivantes :
-approche centralisée : dans ce cas, on peut faire appel à la méthode itérative de Newton. La
solution est obtenue selon l’équation qui suit.
−1 D
x(k + 1) = [x(k) − β(I − ∇ F(x(k)) (x(k) − F(x(k)))]                                           (27) 

Evidemment, la convergence est assurée lorsque (I − ∇ F(x(k)) est inversible.

-Approche distribuée : un problème F-Lipschitz peut être également résolu par une approche
distribuée en utilisant un réseau, une grille de calcul ou un ensemble d’agents. Soit x 0 une
solution initiale et x i (k) le vecteur de décision du nœud i à l’instant k.   

  50
Chapitre 3 : Optimisation F-Lipschitz

x i (k) = [x 1 (τ 1 i (k), x 1 (τ 1 i (k),..., x 1 (τ 1 i (k)]

                                            (28)

τ ji (k) est le délai nécessaire pour que le noeud j prenne une décision et la fait communiquer au
nœud i.

Dans ce cas, les équations décrites par les équations qui suivent convergent vers une solution
optimale.

⎧x i (k + 1) = f i (x i (k)) D , i = 1...l
⎨                                                   (29)
⎩x i (k + 1) = h i (x i (k)) , i = l + 1...n

10. F-Lipchitz pour les réseaux de capteurs

Quelques exemples liés aux réseaux de capteurs ont été résolus dans [28]. Les exemples traités
montrent qu’il est possible de tirer profit de cette méthode pour résoudre des problèmes d’ordre
important. Considérons par exemple le problème de l’allocation de la puissance dans un réseau
constitue de n nœuds responsable de l’émission et n nœuds pour la réception. Chaque nœud i
possède une puissance de transmission Pi
  
Ce problème est formulé comme suit :

min 1T P

G ii Pi
≥ S min                                                                        (30)
σ i + ∑ G ik Pk
k ≠i
Pmin ≤ Pi ≤ Pmax

P Est le vecteur de puissance et représente le gain de transmission entre le nœud et le récepteur.

Ce problème peut être transformé en un problème F-Lipschitz par la transformation x i = − Pi

  51
Chapitre 3 : Optimisation F-Lipschitz

max 1 T x

G ii x i + S min (σ i − ∑ G ik x k ) ≤ 0
k ≠i                                                         (31)
- Pmax ≤ x i ≤ − P min

11. Conclusion

La convergence assurée par F-Lipschitz et la possibilité du calcul de la solution de manière

distribuée sont des points qui favorisent l’utilisation de cette technique dans le cadre des réseaux
de capteurs. Tout le fondement mathématique pour transformer un problème en un problème F-
Lipschitz a été établie dans [28, 29]. D’un point de vue avantage, cette méthode peut être
appliquée à des problèmes d’optimisation :
-Convexes ou non.

-Ayant même des variables manquantes dans la fonction objectif.

-Dont le nombre de contraintes peut être inférieur par rapport au nombre de variables.

L’inconvénient majeur qu’il faudra noter concerne la complexité de la vérification et la

transformation. L’objectif du prochain chapitre est de détailler notre système.

  52
Chapitre 4 : Contributions pour le routage opportuniste et géographique

1. Introduction

Le temps minimal nécessaire pour la terminaison d’une application est un problème

d’optimisation intéressant. En considérant un réseau de capteurs basé sur des communications
multi-sauts, une autre dimension s’ajoute au problème du temps de d’achèvement minimal
puisqu’il faudra tenir compte que la destination n’est pas capable d’avoir des données
directement à partir de la source. Notre système traite ce problème et adopte le routage
opportuniste comme mécanisme de transmission au niveau de la couche réseau. Afin d’échapper
un petit peu du problème des contraintes énergétiques, les nœuds capteurs sont supposés munis
de systèmes de récupération d’énergie. Mais ceci complique le routage opportuniste puisque
chaque transmission est soumise à la contrainte de rechargement des batteries des autres nœuds
du réseau. Une formulation du problème est proposée et deux variantes sont considérées : la
première suppose que la probabilité d’effacement des paquets sur chaque lien est connue à
l’avance tandis que la deuxième estime cette probabilité. La résolution est menée de manière
centralisée par le biais de la méthode F-Lipschitz et le calcul par intervalles. La méthode F-
Lipschitiz est appropriée vue que le domaine de variation des variables est borné. D’autres parts,
le calcul par intervalles est adéquat pour représenter les possibilités de quelques variables vue
que la phase de rechargement des batteries diffère d’un nœud capteur à un autre.
Une autre problématique étudiée dans ce chapitre concerne la maximisation de la durée de vie
sous routage opportuniste. Dans ce contexte, une métaheuristique simple a été exploitée pour
résoudre un modèle non linéaire. Cependant, le dernier système s’intéresse à la thématique de la
localisation des capteurs mobiles et du routage géographique sans tenir compte des erreurs de
transmission.

2. Contribution principale ‘Système de routage opportuniste avec récupération d’énergie’

2-1. Travaux annexes

Au travers les travaux de recherche liés aux réseaux de capteurs, différentes problématiques se
sont relevées. La maximisation de la durée de vie d’un réseau de capteurs a gagné une attention
particulière. Nous mentionnons que notre travail est étroitement basé sur les travaux suivants :
[31] Ont formulé le problème de la maximisation de la durée de vie sous l’hypothèse de
l’agrégation des données. Les positions des capteurs et celle de la station de base sont connues à
l’avance. Un algorithme polynomial a été proposé pour résoudre le problème considéré. Ce
dernier est linéaire.
[32] Ont traité le problème du routage par le biais du plus court chemin en considérant des
capteurs ayant des capacités pour adapter leurs puissances de transmission.
Le travail de la maximisation de la durée de vie le plus marquant est celui présenté dans [33].
Les auteurs ont proposé un framework qui tient compte des contraintes de la couche réseau,
MAC et physique. Le framework s’adapte bien à des transmissions orthogonales ou non et a été
évalué pour différentes topologies. Les performances en termes de la durée de vie sont
remarquables.

  53
Chapitre 4 : Contributions pour le routage opportuniste et géographique

[34] ont formulé le problème de la maximisation de la durée de vie dans le cas du routage
opportuniste et codage linéaire aléatoire. L’idée consiste à recevoir l’information selon une
certaine probabilité afin d’équilibrer la consommation énergétique entre les nœuds capteurs. Le
modèle proposé n’est pas convexe et tient seulement compte des contraintes de la couche réseau
(contraintes énergétiques, de conservation du flot et de la capacité calculée dans le cas du routage
opportuniste). Le standard IEEE802.11 (couche physique et MAC) a été intégré durant les
simulations.
[35] ont proposé d’utiliser le recuit simulé pour calculer les probabilités de réception dans le
modèle proposé dans [34]. Les résultats de simulation obtenus ont montré que le choix de la
solution voisine a une grande influence pour la convergence du système.
L’activation des liens est une technique ancienne qui assure des transmissions sans interférence.
Elle consiste à construire un graphe de conflit tel que chaque nœud représente un lien dans le
graphe original et un lien existe dans le graphe de conflit si et seulement si les transmissions
associées ne peuvent pas être activées en parallèle. La construction du graphe de conflit peut être
menée selon le modèle protocolaire qui est assez simple et imprécis. Une transmission est activée
dans ce cas si le récepteur se trouve dans le rayon de transmission de l’émetteur. Le modèle
physique permet d’activer une transmission une fois la puissance agrégée au récepteur plus le
bruit soit supérieur à un certain seuil. [Link] [36] a introduit le concept de la CTS ‘conservative
transmission set’ pour l’activation des nœuds (au lieu des liens) sous routage opportuniste. Il a
défini une CTS comme étant un ensemble de nœuds tel que tous (un) liens impliqués peuvent
être activés en parallèle. Le calcul de la CTS est un problème NP-complet et nous montrons dans
[37] notre contribution pour le calcul de la CTS. Supposons que l’ensemble CS des CTS a été
calculé, le modèle proposé dans [37] permet de maximiser la durée de vie en tenant compte de
l’activation des nœuds qui n’engendrent pas d’interférence tout en adoptant le routage
opportuniste comme moyen pour délivrer les paquets à leur destination. En effet, le calcul des
CTS procède en deux étapes. Nous calculons en premier pour chaque nœud du réseau l’ensemble
des nœuds qui peuvent transmettre avec lui. Pour cela, on trie les nœuds selon les valeurs
croissantes de la puissance reçue au niveau du récepteur et on commence par le nœud qui a la
plus petite contribution en termes de puissance. Ensuite, on fixe un seuil Bmax (le nombre
maximum de CTS) et on élimine les ensembles qui soient sous-ensembles des autres. Tant que le
rapport de l’agrégation des puissances bruit est supérieur au seuil fixe on continue l’etape1. Les
simulations réalisées ont considéré différentes densités et ont démontré les performances en
termes de la durée de vie.
[38, 39, 40] ont étudié l’effet de la probabilité d’effacement, l’énergie et la taille du champs de
Galois sur le temps de terminaison en s’intéressant à une seule source qui diffuse des paquets à
plusieurs destinations. Le processus de décodage a été modélisé par une chaîne de Markov. Les
auteurs se sont penchés sur la détermination du nombre optimal des paquets codés avant
d’attendre un acquittement. Rappelons qu’une chaîne de Markov est une chaîne sans mémoire.
Autrement dit, la prédiction de l’état actuel dépend uniquement de l’état précédent et non pas de
tous les états antécédents. Le comportement de la chaîne peut être visualisé en traçant un graphe
orienté contenant les états et la fonction de transition [41].
[42] ont présenté une étude intéressante qui porte sur le temps minimal de terminaison sous
l’hypothèse de récupération d’énergie et ont pu déduire la relation entre la puissance de
transmission à utiliser et la quantité d’énergie récupérée.

  54
Chapitre 4 : Contributions pour le routage opportuniste et géographique

2-2. Système proposé

On considère un réseau de capteurs contenant une seule source et une seule destination. Le
réseau est modélisé par un graphe G = ( N , ζ ) . N est l’ensemble des nœuds et ζ est l’ensemble des
liens. Le taux d’erreur sur chaque lien (i , j ) est dénoté ε ij . Le voisinage d’un nœud i est définie
par {
nb(i) = j ∈ / {}
i ε ij p 1 }.
La source a M paquets destinés à D . Chaque nœud capteur possède une file pour stocker les
données et un composant de stockage idéal pour conserver l’énergie récoltée. La capacité du
composant de stockage du nœud i est E max
i
. L’énergie initiale du nœud i est E 0i . Les instants de
récupération et les quantités d’énergie  correspondantes sont {S i1 , S i 2 ,... }, {E i1 , E i 2 ,... }.
k k
respectivement. La longueur d’une phase est égale à l i = S i − S i
k −1
avec S i 0 = 0

Ei0 Ei1 Ei2 Ei3 Eik

Si0 Si1 Si2 Si3 Sik

Figure1. Phases et quantités d’énergie récupérées.

L’énergie est récupérée au début de chaque phase. Pri k est la probabilité pour que le nœud
capteur i soit actif (en émission ou en réception) durant la phase k . À chaque instant, l’énergie
 
consommée doit être inférieure à celle récupérée [43].

Hypothèses :

- Les nœuds capteurs connaissent leurs positions (soit par GPS, soit par une technique
d’estimation).

- Les nœuds capteurs sont synchronisés et il y a un temps global.

- Les nœuds capteurs peuvent adapter leurs puissances de transmission.

Le schéma illustré en figure 2 donne un aperçu du modèle proposé, tandis que le tableau 1
explique toutes les notations utilisées par la suite.

  55
Chapitre 4 : Contributions pour le routage opportuniste et géographique

[Link] de terminaison

C’est le temps nécessaire pour décoder tous les paquets envoyés par la source. Le processus de
la transmission et du décodage peut être modélisé par une chaîne de Markov. Cette dernière
permet de modéliser l’évolution dynamique d’un système aléatoire. Les états de la chaîne varient
de M à 0 et chaque état dénote le nombre de paquets manquants afin de lancer l’opération
de décodage. Pour cela, nous considérons que la probabilité de transition durant la phase k   de
l’état Se i à l’état Se j ( Se i = Se j ) est décrite par l’équation qui suit :

k k k k k
Pi(Sei −>Sei ) = (((1− Prik ) + εiavg + (1− PRi ))Sei − ((1− Pri ) * εiavg * (1− PRi )))Sei
k
(1)

Cette expression traduit une disjonction entre les énoncés suivants :

- le nœud capteur i est en train de recharger sa batterie.
-Les liens associés à i ont subi un grand taux d’erreur.
- i est incapable de décoder des paquets reçus en parallèle.
  probabilité du décodage d’un paquet parmi
La TA paquets reçus est obtenue par l’équation (2)
   
[44].

−(2*PA−1−1)
k TA! − 2 −1                                       
PRi = 2 2 e (2)
(TA − 1)! γiavg
k

Cette expression est obtenue après le calcul de la PDF ‘probability density function’ du SNR
associé à chacun des paquets reçus.

Le nœud i passe de l’état Se i à l’état Se j ( Se i ≠ Se j ) suivant cette probabilité [43]:

nb ⎛ N ⎞
Pi(Sei −>Sej) = (1 − P(Sei −>Sei) ) * ∑ ⎜⎜ i ⎟⎟(P(M −>M−1) ) r * (1 − P(M −>M−1) ) Ni −r
k k k k (3)
r =1⎝ r ⎠

nb ⎛ N ⎞
Il est à mentionner que l’expression ∑ ⎜⎜ ⎟⎟(P(M − > M −1) k ) r * (1 − P(M − > M −1) k ) N i − r représente le fait
i

r =1⎝ r ⎠
qu’au moins un des voisins du nœud i a reçu au moins un paquet. De plus, le temps de
 

  56
Chapitre 4 : Contributions pour le routage opportuniste et géographique

Figure 2. Principe du modèle proposé.

  57
Chapitre 4 : Contributions pour le routage opportuniste et géographique

terminaison est soumis aux contraintes du routage opportuniste. Soient f ij k , f ji

k
les flots
envoyés et reçus durant la phase k .

Le flot et la capacité sont calculés par les équations suivantes :

k k k k
f ij = Z i α ij (1 − ε ij )Pr j
k k k k k
f ji = Z j α ji (1 − ε ij )Pr i PR i
k k k
x i S = Z i (1 − Π j∈S (1 − Pr j (1 − ε ij )))
                                                (4) 

A la réception d’un paquet, le nombre de transmissions moyen effectué par le nœud i est égale à :                           

k
k zi
ni = k k
∑ z l (1 − ε li )Pri
l
                                                        (5)       

2-.4. Modèle d’optimisation                           

      Soit Tp le temps nécessaire pour envoyer un paquet codé.

− (2 * PA −1−1)
k TA! − 2 −1
PR i = 2 2 e
(TA − 1)! γ iavg
k
(6)

Tel que :
g = log 2 (q) (7)

Notation Définition
Pr
k
Probabilité associée au noeud capteur i
Temps de terminaison
Ti
 

  58
Chapitre 4 : Contributions pour le routage opportuniste et géographique

d’être actif dans la phase k.

pi
k
Puissance utilisée par le noeud i durant la
phase k (puissance consommée pour la
transmission ou la réception)

Ei
k
Energie récupérée par le noeud i dans la
phase k.

Zi
k
Nombre de transmissions réalisées par le
noeud i durant la phase k.

nb i Nombre de voisins du noeud i.

q Taille du champ utilisé pour le codage

ri Débit utilisé par le nœud i

αi jk Probabilité de transmission associée au

noeud j durant la phase k.

Pi ( Sei − > Sej )

k
Probabilité de transition (associée au noeud
i) l’état Sei à l’état Sej durant la phase k

PR i
k
Probabilité associée au noeud i pour
couvrir un paquet durant la phase k.

γ iavg k SNR moyen associé au nœud i durant la

phase k

li
k
Temps consommé par le nœud i durant la
phase k

l ti
k
Temps consommé par le noeud i pour
recharger sa batterie durant la phase k.

η Bruit

ε iavg k Probabilité d’effacement moyenne associée

au nœud i durant la phase k

H La taille de l’en-tête d’un paquet

Table1. Notations du modèle.

  59
Chapitre 4 : Contributions pour le routage opportuniste et géographique

On peut maintenant formuler le problème de la minimisation du temps de terminaison sous

l’hypothèse de la récupération d’énergie et celle du routage opportuniste comme suit :

min T                                                                                                                                                             (8)

h
k k k k' k'
h'
k' k' k' k' (8.1)
∑ p i * (l i − l ti k ) * Z i + ∑ ∑ p j * (l j − l t j ) * Pri * z j * PR i
k =1 k' =1j∈ nb(i)

+
h h' h
h +1 k h +1 h' +1 h' +1 k' h' +1 h' +1 k
pi * (T - ∑ l i ) * Z i + ∑ Zj * pi (T − ∑ l j ) * Pri * PR i ≤ ∑ Ei
k =1 j∈ nb(i) k' =1 k =1

∀j ∈ nb(i) :
k
h +1
k k k
h +1 1 pi
∑ Zi * α i j * (1 − ε ij ) * Prj ≤ ∑ ( log(1 + ))
k =1 k =1 2 η (8.2)

k k k
h +1
∑ Z j * Tp ∑ Z j * Tp ∑ Z j * Tp
T ≤ ∑[(
j∈nb(D)
+
j∈nb(D)
+ ... +
j∈nb(D)
] + D1 (8.3)
k k k
k =1 PD(M−>M−1) PD(M−1−>M−2) PD(1−>0)

                                                                                 
1 j∈nb(S) 1
Z1 * (1 − Π (1 − Pr j * (1 − ε ij ))
− D1 ≤ − ( ) * nb hops (8.4)
r(S)

h' h
k' k' k' k' k
∑ ∑ α ji * (1 − ε i j ) * Pri * PR i * z j + (T - ∑ l i )
k' =1 j∈nb(i) k =1

h' +1 h' +1 h' +1 h' +1

+ ∑ α ji * (1 − ε i j ) * Pri * PR i *zj
j∈nb(i)

= (8.5)
h
k k k h +1 h +1 h +1
∑ ∑ α i j * (1 − ε i j ) * Pr j * Z i + ∑ α ji * (1 − ε i j ) * Pr j * Zi
k =1 j∈nb(i) j∈nb(i)

  60
Chapitre 4 : Contributions pour le routage opportuniste et géographique

k
∀i, k 0 ≤ Z i ≤ Z max
k
∀i, k 0 ≤ p i ≤ p max
k
∀i, k 0 ≤ Pri ≤ 1
k
∀i, k 0 ≤ PR i ≤ 1
k (8.6)
∀i, j, k 0 ≤ α i j ≤ 1
0 ≤ T ≤ Tmax
0 ≤ D 1 ≤ D max

La première contrainte exprime la conservation d’énergie, la deuxième est liée à la capacité au

niveau de la couche physique, la troisième décrit le processus de décodage et la quatrième
représente la conservation du flot. Le dernier système d’équations exprime le fait que toutes les
variables du modèle sont bornées. Revenons maintenant à l’équation (8.3) qui dépend de D1. En
fait, D1 est le délai après lequel au moins un des voisins de la destination a pu recevoir au moins
un paquet. Il est obtenu par la construction d’un arbre couvrant minimal tel que nb hop représente
sa longueur. L’algorithme de Prim [45] est un algorithme très connu en recherche opérationnelle
pour calculer un tel arbre. Son principe est comme suit :
S: source;

D: destination;

Dis(i,j) : distance entre le nœud i et le nœud j ;

Nb : le nombre de nœuds dans le réseau ;

Début

M= ∅;

A=S ;

M=M∪{A} ;

Tant que A ≠ D faire

Pour i = 1 : Nb

Si (i ∉{M}) et Dis(A,i) = min (Dis(A,j)) et j ∉ i alors

M= M∪{i} ;

A=i ;

Fin Si

Fin Pour

Fin Tant que

Figure3. Algorithme de Prim.

  61
Chapitre 4 : Contributions pour le routage opportuniste et géographique

Une question primordiale de notre modèle est la suivante :

-Comment peut-on calculer la puissance et la probabilité pour qu’un nœud soit actif durant la
phase associée à un autre ?

Nous avons pensé à exploiter le calcul par intervalles pour tenir compte de l’ensemble des
différentes possibilités. La probabilité est décrite par le système d’équations (9) tandis que la
puissance de transmission est décrite par le système (10).

Prj k = Π Prj k'

tel que : k est definie sur [Si-1 , Si]
k' est definie sur [S' j-1 , S' j ]
S' j-1 ≥ Si-1
S' j-1 ≤ Si
S' j ≤ Si
                                                   (9)

p j k = [min p j k' , max p j k' ]

tel que : k est definie sur [Si-1 , Si ]
k' est definie sur [S' j -1 , S' j ]
S' j-1 ≥ Si-1
S' j-1 ≤ Si
S' j ≤ Si
                                                               (10)

Soit un réseau qui contient deux nœuds capteurs. Les instants ainsi que les quantités d’énergie
récupérées sont comme suit :

0 mJ 10mJ 12mJ 9mJ

0s 2s 2.5s 2.9s

  62
Chapitre 4 : Contributions pour le routage opportuniste et géographique

0mJ 8mJ 7mJ 8mJ

0s 1.7s 2.3s 2.7s

Le modèle associé continent donc deux contraintes calculées selon l’équation 8.1, deux
contraintes calculées selon l’équation 8.2, une contrainte calculée selon 8.3, une autre contrainte
calculée selon 8.4, deux contraintes calculées selon 8.5 et d’autres contraintes calculées par 8.6.
En effet :

∂ C1
= (l 1 − l t 1 )P11
∂ Z 11

∂ C1
= (l 2 − lt 2 ) Pr11 PR 11 P21
∂ Z 12
Tel que :

[
P21 = P2min , P2max ] 2s
0 ²

∂ C3 2
= (1 − ε 12 )α 12
1
∏ Pr 2
k

∂ Z 11 k =0

2-5. Formulation F-Lipschitz

Il est clair que le modèle proposé n’est pas convexe à cause du produit des variables. On va
utiliser la méthode F-Lipschitz pour sa résolution vue que les variables sont bornées. Pour cela,
nous devons adopter ce changement de variable :

T1 = − T   (11)

max T1                                                                         (12)

  63
 Chapitre 4 : Contributions pour le routage opportuniste et géographique

h h'
1 1 k k k k' k' k' k' k' k'
Z i ≤ Z i - λ i ( ∑ p i * (l i − l ti k ) * Z i + ∑ ∑ p j * (l j − l t j ) * Pri * Z j * PR i
k =1 k'=1 j∈nb(i)

+ (12.1)
h h' h
h +1 k h +1 h' +1 h' +1 k' h' +1 h' +1 k
pi * (-T1 - ∑ l i ) * Z i + ∑ Zj * pi (−T1 − ∑ l j ) * Pri * PR i − ∑ Ei )
k =1 j∈nb(i) k'=1 k =1

                             

∀j ∈ nb(i) :
k
h +1 h +1
h +1
k k k
h +1 1 p
Zi ≤ Zi − λ i ( ∑ Z i * α i j * (1 − ε ij ) * Pr j − ∑ log(1 + i ))) (12.2)
k =1 k =1 2 η

k k k
 
h+1
∑ Z j * Tp ∑ Z j * Tp ∑ Z j * Tp
j∈nb(D) j∈nb(D) j∈nb(D)
− T1 ≤ −T1 − λ(−T1 − ∑[( k
+ k
+ ... + k
] + D1 )
k=1 PD(M−>M−1) PD(M−1−>M−2) PD(1−>0)
(12.3)

     

(12.4)
Z1 * (1 − Π j∈nb(S) (1 − Pr j * (1 − ε ij ))
1 1
− D1 ≤ − D1 − λ( − D1 + ( ) * nb hops )
r(S)

h' h
1 1 k' k' k' k' k
pi ≤ pi − μi ( ∑ ∑ α ji * (1− εi j ) * Pri * PRi * z j  + (-T1 - ∑ li ))
k'=1j∈nb(i) k=1

h'+1 h'+1 h'+1 h'+1

(12.5)
+ ∑ α ji * (1− εi j ) * Pri * PRi *zj
j∈nb(i)

−
h
k k k h+1 h+1 h+1
∑ ∑ αi j * (1− εi j ) * Prj * Zi + ∑ α ji * (1− εi j ) * Prj * Zi
k=1 j∈nb(i) j∈nb(i)

  64
Chapitre 4 : Contributions pour le routage opportuniste et géographique

∀ k = 2 : h Z ik = Z max
∀ k = 2 : h ∀ i = 1 : N Z i = Z max
k (12.6)
k
∀ k = 2 : h ∀ i = 1 : N p i = p max
h +1
∀i = 1 : N ∀i = 1 : N p i = p max
h +1
∀i = 1 : N ∀j = 1 : N α i j = α max
k
∀ k = 1 : h ∀ i = 1 : N ∀ j = 1 : N α i j = α max

Ce modèle remplie la condition (23.C) lorsque les valeurs des puissances utilisées sont
inférieures à 1 et les puissances associées sont considérables ou l’inverse.

2-6. Estimation de la probabilité d’effacement

Le second volet de notre travail a consisté à estimer la probabilité d’effacement au lieu de se

baser sur des valeurs aléatoires. Pour cela, la chaîne de Markov devient comme suit :

0’ Prik

Prik  Prik Prik

  M  M‐1  M‐2 M‐3 …    0 

k k k k k
Pi(M−>M) Pi(M-1−>M-1) Pi(M-2−>M-2) Pi(M-3−>M-3) Pi(0−>0)
                                                                                   
Figure 4. Chaîne de Markov proposée pour le décodage.

L’état 0’ correspond à un effacement d’un paquet. C’est un état absorbant de la chaîne de

Markov et sa valeur est obtenue par cette équation :

= (I − Q) −1 * r0
k
ε iavg
                                                                  (13)

Q : est la matrice de transition entre les états.

  65
Chapitre 4 : Contributions pour le routage opportuniste et géographique

r0 : est le vecteur de transition vers l’état 0’.

k k k k k
(14)
Pi(Sei −>Sei ) = (((1− Prik ) + εiavg + (1− PRi ))Sei − ((1− Pri ) * εiavg * (1− PRi )))Sei
k

Autrement dit, la probabilité d’effacement dépend de la valeur moyenne du SNR mais aussi de la
probabilité pour que le nœud concerné soit en état actif.
Pour cela, l’algorithme illustré en figure 5 est préconisé pour calculer la solution finale.

2-7. Scénarios d’exécution

Afin de mener des comparaisons, nous avons suivi la même idée présentée dans [34]. Deux
scénarios sont possibles:
-Dans le premier cas, lorsqu’un nœud diffuse un paquet seul le nœud actif qui minimise la
métrique ETX est susceptible de continuer la transmission.
-Dans le second cas, lors d’une diffusion tout nœud qui soit actif est susceptible de prendre le
rôle de relais.

K← 0

1. Générer une solution initiale x 0

 

2. Répéter

Estimer la probabilité d’effacement par (13)

Mise à jour de la solution par (chapitre3.27)

-Si x k +1 − x k ≥ ξ alors allez à l’étape 2

K← K+1

Jusqu’à convergence

Figure 5. Principe de la résolution du modèle.

  66
Chapitre 4 : Contributions pour le routage opportuniste et géographique

Ces deux scénarios sont schématisés en figure 6 et 7.

ETXA=1/0.5=2

A 
0.5
E
S  D 
0.4 ETXB=1/0.6=1.67
B 
0.6

F
ETXC=1/0.4=2.5
C

Figure 6. Scénario 1.

ETXA=1/0.5=2

A 
0.5
E
S  D 
0.4 ETXB=1/0.6=1.67
B 
0.6

F
ETXC=1/0.4=2.5
C

Figure 7. Scénario 2.

On suppose que seuls B et C sont actifs au moment où A fait sa diffusion. Dans le premier
scénario seul le nœud B sert de relais puisqu’il possède la valeur minimale en termes de la
métrique ETX. Dans le second cas, C peut continuer la diffusion.

  67
Chapitre 4 : Contributions pour le routage opportuniste et géographique

3. Contributions secondaires

3.1. Maximisation de la durée de vie d’un réseau de capteurs sous routage opportuniste

En face du coût de la technologie de la récupération d’énergie, la maximisation de la durée de

vie reste une thématique d’actualité. Pour cela, la maximisation de la durée de vie sous routage
opportuniste dans un réseau de capteurs statiques est une contribution secondaire de notre travail.
Les notations du modèle sont données en tableau 2.
Les contraintes du système sont comme suit :

max min i∈ N T i

^ ^
Ei Z i + Ei ∑ γ ki Z k ≤ E i
t r

k ∈O ( i )

Tr i + ∑ f ki ^ = ∑ f ij ^
k ∈O ( i ) j∈O ( i )
^ ^
∀ S ⊆ O (i ) ∑ f ij ≤ Z i (1 − ∏ (1 − γ ij (1 − ε i j )))
j∈O ( i ) j∈ S

(15)

Notation Définition
Ei Energie initiale du nœud
capteur i
Ei
t
Energie consommé par i pour
envoyer un seul paquet.
Ei
r
Energie consommé par i pour
recevoir un seul paquet.
fi j Flot du lien ( i , j )
ri Débit utilisé par i
Zi Nombre de transmissions
effectuées par i
T Durée de vie du réseau
Zi
^
Nombre de transmissions
effectuées par i durant T
fi j
^
Flot du lien ( i , j ) Durant T

Table2. Notations et définitions.

Ti =
Ei (16)
Ei * Z i + Ei * ∑ Z k * γ
t r
ki
k ∈O ( i )

  68
Chapitre 4 : Contributions pour le routage opportuniste et géographique

La première contrainte est celle de l’énergie, la seconde exprime la conservation de flot ; tandis
que la troisième est liée au routage opportuniste. Il est clair que le modèle proposé n’est pas
convexe. A la différence de [34], nous avons pensé à introduire une métaheuristique simple
‘recuit simulé’ [46] pour estimer les probabilités de réception de sorte que la solution finale sera
calculée par programmation linéaire ainsi que la métaheuristique impliquée. Le recuit simulé est
paramétré par la température et consiste à effectuer des mouvements dans un espace de
recherche. La figure 8 contient le schéma de la résolution.

3.2. Localisation et routage géographique dans un réseau de capteurs statiques

Connue comme étant l’un des problèmes considérables lors de la mise en œuvre d’un réseau de
capteurs, la localisation est nécessaire pour accomplir la tâche de surveillance d’une zone. Elle
est indispensable pour les réseaux de capteurs statiques et possède en même temps des
motivations fortes dans un réseau de capteurs mobiles. Le sujet de la localisation des capteurs
pour un routage géographique nous a amenés à proposer une contribution secondaire dans ce
travail de recherche. Informellement, la localisation consiste à affecter ou à déduire les
coordonnées des nœuds capteurs. Dans ce contexte, deux solutions existent. La solution
matérielle concerne l’équipement des capteurs par des GPS. L’inconvénient majeur de cette
technologie concerne sont coût important et l’énergie requise quant à la réception d’un signal.

Début

1. Choisir une solution aléatoire pour γ i j ∀ i, j

Répéter
2. Mise à jour de γ i j ∀ i, j
γ i j = γ i j ± rand () * η
'

3. Calculer la probabilité d’acceptation de γ i j ∀ i, j

⎧ ( −((γ i j ' ) − (γ i j ))
⎪exp
⎪ Tk
⎪ if ((γ 'i j −γ i j ) > 0
P (γ ij ' is asscepted ) = ⎨
⎪
⎪
⎪⎩1 if ((γ 'i j −γ i j ) ≤ 0

4. Résoudre (5) et calculer Z i , α ij ∀ i, j

Jusqu’à convergence
Fin

Figure 8. Algorithme du recuit simulé pour le calcul des probabilités de réception.

  69
Chapitre 4 : Contributions pour le routage opportuniste et géographique

Pour cela, il était nécessaire de réfléchir sur des solutions software permettant ainsi une
localisation propre. Divers critères peuvent être employés pour classer les approches de
localisation mises en place. La présence des capteurs équipés par des GPS (ancres) conduit
souvent à une localisation globale tandis que leur absence implique une localisation relative. La
mesure de la distance (ou l’angle) par rapport aux autres capteurs ou son estimation est
également un critère de classification des techniques de localisation. Dans un environnement
dynamique, la localisation est un problème ayant d’autres dimensions qu’il faudra prendre en
charge : les positions reçues peuvent être anciennes à cause de la mobilité des noeuds, la
localisation devient gourmande en terme de communication puisque chaque capteur doit de se
localiser et se re-localiser à chaque déplacement,…
De façon générale, les méthodes Monté-Carlo ont démontré leur efficacité pour localiser des
capteurs mobiles. Il s’agit de calculer la future position (éventuellement la vitesse et
l’accélération) sur la base des calculs déjà effectués. Il existe une variété de modèles de
prédiction ; dont l’application est fonction du modèle de mobilité. Signalons que les modèles de
prédiction de la trajectoire peuvent être de type déterministe, stochastique ou basés sur
l’historique. En cas où les mobiles suivent un mouvement uniforme, il est très recommandé de
faire appel à un modèle déterministe pouvant être du premier ou second ordre. Cependant, au cas
où le mouvement des mobiles est aléatoire, ont peut investiguer une approche stochastique ou
une approche basée sur l’historique passant par une phase d’apprentissage des motifs de
mobilité. Parmi les techniques stochastiques, on peut citer les filtres particulaires qui représentent
une variante des méthodes Monté Carlo séquentielles. Il s’agit d’estimer les paramètres
x k , k = 1,2,3,.. d’un problème en tenant compte des données observées y k , k = 1,2,3,.. Autrement
dit, un filtre particulaire cherche une estimation de la distribution a posteriori p (x k / y 0 ,... y k ) [47].
En effet, un ensemble de p particules pondérées par des poids w sont générées telle que
l’approximation de la distribution à posteriori est donnée par :

∑lp=1 wl f (xlk ) (17)

3-2-1. Formulation du problème

Classée comme étant une approche de type neighborhood-based routing, la contribution
proposée s’appuie sur l’idée suivante : à chaque instant, une prédiction de la trajectoire des
capteurs voisins d’une source est réalisée. Il s’agit de sélectionner le voisin qui se dirige vers la
station de base (celui qui forme un angle minimal avec la station de base) en tenant compte de
l’aspect énergétique. A ce stade, nous précisons que le modèle énergétique considéré est le
suivant :

⎧d a + c, d ≠ 0 et a ≥ 2
J (d ) = ⎨ (18)
⎩0, sinon

  70
Chapitre 4 : Contributions pour le routage opportuniste et géographique

Ce modèle traduit le fait que la dépense énergétique J(d) est fonction de la distance d’émission
en suivant une loi de puissance. Dans un objectif d’appliquer une simple méthode de prédiction,
nous nous sommes basés sur l’algorithme de filtrage particulaire présenté dans [47]. Il s’agit
d’un algorithme issu de la méthode Monté Carlo dont l’idée de base est celle de la génération des
nombres aléatoires. De façon générale, on définit N particules. Chaque particule x est un vecteur
ayant trois dimensions tels que :

x(0) : correspond à l’abscisse prédite.

x(1) : correspond à l’ordonnée prédite.

x(2) : correspond à la vitesse prédite.

La première étape consiste à faire une prédiction selon un modèle de mobilité. Le modèle de
mobilité utilisé est celui de Gauss-Markov. C’est un modèle dans lequel, chaque capteur choisit
une vitesse et une direction selon les équations (19) et (20) et réitère ce processus tout au long
de la simulation.

V n = (α * V n −1) + ((1 − α ) * μ1) + (1 − α ) * X 1

2
(19)

( )
dir n = (β * dir n −1) + ((1 − β ) * μ 2 ) + 1 − β * X 2
2
(20)

Tels que :

μ1 , μ 2 : correspondent respectivement à la vitesse et la direction moyenne.

X 1 , X 2 : sont deux variables aléatoires.

En passant par l’état de l’art concernant les modèles de mobilité, nous précisons qu’on a adopté
au départ un modèle de mobilité de type Random-Way point. Dans ce cas, un modèle de
prédiction déterministe du premier ordre est strictement adéquat. Cela nous a poussés pour se
baser sur un modèle de mobilité plus complexe. C’est le cas de Gauss-Markov. Bien sûr, la
prédiction effectuée est mise à jour après avoir réalisé une étape de mesure par rapport à trois
^
ancres. x Représente le résultat final.

  71
Chapitre 4 : Contributions pour le routage opportuniste et géographique

Formellement, le principe de la prédiction est comme suit :

1. Initialisation :

Générer N particules.

Pour j=1..N faire

w j = 1/ N

Fin pour

2. Prédiction :

Pour j=1..N faire

x j (0 ) = x j (0) + x j (2) * cos(dir )

x j (1) = x j (1) + x j (2) * sin (dir )

x j (2) = (α * x j (2)) + ((1 − α ) * μ1) + (1 − α ) * X 1

2

Fin pour

3. Mesure :

Soient v1 , v2 , v3 les puissances des signaux reçus à partir de trois ancres et d ki la distance séparant le
capteur k et l’ancre i tels que :

vi = ϕ − 10η log10 (d ki )² ;

ϕ  est une constante qui caractérise la puissance de transmission des ancres

h = v12 + v 22 + v32

Pour j=1..N faire

wj = wj * h

Fin pour

  72
Chapitre 4 : Contributions pour le routage opportuniste et géographique

Normalisation :

Pour j=1..N faire

wj = wj / ∑ wj

Fin pour

Mise à jour :

Pour j=1..N faire

^
x = ∑ Nj=1 x j * w j

Fin pour

Figure 9. Prédiction des positions des nœuds capteurs.

Suite à cette phase, vient le routage qui consiste à minimiser la fonction (21) où la variable
'
a attribue une priorité soit à l’angle et l’énergie, soit à l’angle et la vitesse.

a (α * E ) + (1 − a ) * ⎜α * ⎟
' ' ' ⎛ '1⎞
(21)
⎝ v⎠

Tels que:

α ' : L’angle obtenu par prédiction.

E : L’énergie.

v : Vitesse obtenue par prédiction.

  73
Chapitre 4 : Contributions pour le routage opportuniste et géographique

Supposons que s est la source, u le voisin choisis et t la station de base, le calcul de α ' peut être
mené selon cette équation :

d1 + d 2 − d 3
2 2 2
arccos α ' = (22)
2 d1 d 2

Enfin, il est à indiquer que les valeurs des termes (α ' * E ) et ⎜α ' * ⎟ ont été normalisées entre 0
⎛ 1⎞
⎝ v⎠
et 1.

4. Conclusion

Dans ce chapitre, nous avons présenté un système centralisé de routage opportuniste

fonctionnant sous l’hypothèse de récupération d’énergie. Plus particulièrement, le
fonctionnement de chaque nœud capteur procède en phases. Une quantité d’énergie peut être
récupérée au début de chaque phase puis le nœud capteur peut se mettre en mode actif selon une
certaine probabilité. Quelques contraintes ont été posées pour minimiser le temps nécessaire au
décodage des données. La méthode d’optimisation choisie est F-Lipschitz. Elle est adéquate aux
modèles qui ne soient pas convexes. De plus, les chaînes de Markov ont été exploitées pour
modéliser le processus de décodage. Deux systèmes ont été également étudiés : le premier
s’intéresse à la maximisation de la durée de vie en impliquant des probabilités de réception et en
proposant les métaheuristiques comme outil de résolution. Enfin, le routage dans les réseaux de
capteurs mobiles est un problème complexe. Pour cela, nous avons proposé de lancer un
processus de prédiction des positions des nœuds capteurs à des instants fixes qui conviennent au
modèle de mobilité et d’acheminer les paquets en tenant compte de la dépense énergétique.
Ceci termine donc le présent chapitre. Le chapitre suivant détaille l’implémentation de nos
systèmes. Les modèles liés au routage opportuniste ont été implémentés moyennant Matlab,
Omnet++ [48] et Intlab [49]. Matlab est approprié pour l’optimisation tandis que Intlab est une
boite à outils pour le calcul par intervalles. Les résultats obtenus par Matlab et Intlab constituent
l’entrée de la simulation réalisée par Omnet++. Le calcul sur les champs de Galois est réalisé par
le biais de [50]. L’outil Omnet++ sera présenté au niveau du chapitre 5 avant l’illustration des
résultats obtenus. Cependant, des exemples réalisés par Intlab sont illustrés en annexe. Omnet++
a été largement suffisant pour simuler le routage géographique.

  74
Chapitre 5 : Résultats de simulation

1. Introduction

Ce chapitre est réservé à l’explication de l’outil Omnet++ ainsi que les simulations réalisées
dans le cadre de cette thèse. Omnet++ est approprié aux réseaux sans fil et offre diverses
packages de méthodes. Il suffit de bien choisir les méthodes adéquates à une application. Le cas
échant, il faut modifier le code de ces méthodes ou développer de nouvelles procédures.
L’architecture des nœuds capteurs est facile à modéliser par le biais d’Omnet++. De plus, la
flexibilité de cet outil permet de rajouter ou supprimer n’importe quel composant de
l’architecture. L’objectif de nos simulations est de comparer le scénario 1 et 2 du chapitre 4 en
termes de la consommation énergétique, temps de terminaison, débit, probabilité d’effacement et
le nombre de paquets. Les résultats de simulation des contributions secondaires sont également
détaillés dans ce chapitre.

2. C’est quoi Omnet++?

Omnet++ est l’acronyme de ‘Objective Modular Tes-Bed in C++”. C’est un outil de

simulation permettant de tester des simulations d’évènements discrètes. Cet outil peut être utilisé
dans les cas suivants :
-Simulation des protocoles des réseaux informatiques y compris les réseaux sans fil.

-Simulation des architectures multiprocesseurs.

-Evaluation des systèmes complexes.

-Simulation du parallélisme dans quelques systèmes.

Omnet++ permet de créer l’interface de la simulation et d’écrire le code par le biais du langage
C++. Deux versions de l’outil Omnet++ existent. Une est opérationnelle sous Windows tandis
que la seconde est opérationnelle sous Linux. Omnet++ a été développé après l’apparition de
quelques outils notamment NS2 et OPNET. NS2 est approprié pour les protocoles TCP/IP, le
routage et la communication multicast dans les réseaux filaires. Son utilisation pour les réseaux
sans fil est très limitée. OPNET est un outil commercial pour la simulation de la communication.
Il comprend plusieurs processus basés sur des machines à états finis. Ces dernières sont aptes à
communiquer entre elles. A la différence d’OPNET, Omnet++ est un outil académique gratuit. Il
est basé sur la programmation modulaire qui offre une grande flexibilité.

3. Modélisation de la simulation Omnet++

L’élément de base de la simulation Omnet++ s’appelle un module. Un module peut être simple
ou composé. Un réseau est considéré comme un module composé des nœuds (chacun d’entre eux
est représenté par un module) et d’un canal de transmission. Si l’on souhaite simuler plusieurs
protocoles de la pile protocolaire, chaque nœud sera lui-même considéré comme un module
composé. L’hiérarchie des modules n’est pas limitée. L’envoi des messages est le mécanisme de

  75
Chapitre 5 : Résultats de simulation

communication entre les modules. Chaque message contient un certain nombre d’attributs. Les
modules peuvent posséder des interfaces (nommées portes dans Omnet++) pour l’envoi de
messages et peuvent avoir des paramètres (variables locales de type : string, numeric, boolean)
[48].
Le langage NED (Network Description) est utilisé pour créer l’interface de la simulation. Cet
exemple illustre la syntaxe NED.

Network Network

//commentaires

Node1: node;

Node2:node;

Connections:

[Link] < - - > {datarate=100Mbps ;} < - - > [Link] ;

Cet exemple déclare un réseau composé de deux nœuds appelés Node1 et Node2 qui sont une
instance du module node. Chacun des deux nœuds possède une interface nommée port et sont
connectés par une liaison symétrique pouvant véhiculer un débit de 100 Mbps.
On peut créer un canal de transmission qui encapsule le débit de 100Mbps. Ceci est utile afin
d’éviter de répéter le débit pour chaque transmission si le réseau est composé de plusieurs
nœuds.

Types:channel C extends [Link]

Datarate = 100Mbps;

Connections:

[Link] < - - > C < - - > [Link];

  76
Chapitre 5 : Résultats de simulation

Le module node peut avoir des paramètres, des portes. On peut également trouver des
connections et des sous-modules (en cas où il est compose). La syntaxe utilisée est la suivante :

Simple node Module node

{ {

Parameters: Parameters:

Int: destination; Int: destination;

Gates: Submodules:

Inout: port ; Routing: mod1;

} Physical:mod1;

Connections:

Routing .in1 < -- >Physical.in1;

Gates:

Inout: port;

La première déclaration correspond à un module simple et la seconde correspond à un module

composé. Dans ce cas, le module node est composé de deux sous modules ; chacun d’entre eux
est une instance de mod1 qui possède une porte in1.

3-1. Composants

Les modules et les canaux sont nommés composants et représentent une instance de la classe
appelée Ccomponent qui possède les méthodes suivantes :
Initialize() : invoquée après la création du réseau et fournit l’espace pour tout code
d’initialisation.

Finish() : appelée à la fin de l’exécution de la simulation et permet par exemple de récolter des
statistiques.

Handlemessage(cMessage *msg) invoquée avec le nom du message en paramètre et ceci lorsque

le module concerne reçoit un message.

Void Hellomod ::initialize()

  77
Chapitre 5 : Résultats de simulation

Ev<< “Hello world\n “ ;

Lors de l’initialisation, on affiche un simple message “hello world”.

Void Hellomod :: Handlemessage(cMessage *msg)

Delete (msg);

Tout message reçu est supprimé.

3-2. Messages et paquets

Les messages et les paquets peuvent être crées de la même façon. Il suffit d’utiliser le mot clé
message à la place de packet pour avoir un message.
Packet mypacket

Int source@;

Int des@

Int data;

Ils sont associés des mêmes méthodes énoncées auparavant. Cependant, les paquets ont des
méthodes supplémentaires. La plus importante est setBitLength (int 64 l ). De plus, les paquets
peuvent être encapsulés. Les méthodes usuelles sont :
Void setName (cosntChar *name) ;

Void getKind(short k) ;

setTimestamp(simtime_t t);

setSchedulingPriority(short p);

  78
Chapitre 5 : Résultats de simulation

L’envoi des messages et paquets peut être effectue par l’une des méthodes suivantes:

Send (cMessage *msg, cGate *gate) ;

cMessage *copy =msg->dup

for (int I = 0 ; I < n; i++)

Send (copy,’out’);

sendDelayed(cMessage *msg, double delay, cGate *gate)

La première méthode envoie le message à travers une porte. La deuxième diffuse le message à
travers toutes les portes associées au module et la troisième méthode permet d’envoyer le
message après un certain délai.

3-3. Configuration de la simulation

Peut être menée par le biais d’un fichier nomme [Link].

Ce fichier contient une section General qui précise le modèle à simuler et le temps de la
simulation. On peut également assigner des paramètres aux modules ou répéter la simulation
plusieurs fois.
L’exemple qui suit déclare que le modèle de la simulation est Fifo. Il contient 15 nœuds. Le
symbole ‘*’ signifie n’importe quel module dont le nom commence par host.

[General]

Network =Fifo

[Link]=15

[Link][*].length = 20

  79
Chapitre 5 : Résultats de simulation

4. Résultats de simulation

4-1. Résultats de la contribution principale

Cette section détaille les résultats de simulation obtenus. Nous considérons une topologie de 10
nœuds capteurs comme celle utilisée dans [34] où chaque liaison radio est caractérisée par un
taux fixe d’erreur. La manipulation des champs de Galois a été réalisée moyennant [50]. Les
nœuds peuvent récupérer des quantités d’énergie à des intervalles aléatoires prédis à l’avance et
leurs batteries sont supposées idéales. En effet, l’énergie solaire s’avère un exemple pratique
pour nos simulations. Les paramètres de la simulation sont comme suit :

Paramètre Valeur

p max 20mW

Z max 5

T max 15s

β 0.02

η 10-6

M 100

q 256

h 128 bits

D 1max 5s

E i0 10MJ

Tableau1. Paramètres de la simulation.

Nous précisons que nos simulations ont été réalisées sur la machine Plough du département EEC
(Université Concordia) sous Windows 7 Entreprise. La machine contient 8 processeurs Intel
Core 2.93Ghz et une Ram de 4 GB. Plus particulièrement, les nœuds capteurs simulés sont munis
d’une couche application, de codage réseau linéaire aléatoire, de routage opportuniste, d’accès
aléatoire au médium et une couche physique. A côte de ceci, une batterie est intégrée.

  80
Chapitre 5 : Résultats de simulation

Figure1. Topologie des nœuds capteurs.

Figure 2. Architecture d’un noeud capteur.

  81
Chapitre 5 : Résultats de simulation

4-1-1. Evaluation de la consommation énergétique

La comparaison de la consommation énergétique des deux scénarios déjà expliqués en chapitre

4 a constitué le premier volet de nos simulations. Dans la figure 3, la consommation énergétique
(transmissions et réceptions) mesurée en MJ de chaque nœud capteur est illustrée en barres.
Cette consommation est nécessaire au décodage de 100 paquets. En fait, 1 et la source et 10 est la
destination. Il est clair d’après la figure 3 que le scénario 2 résulte d’une consommation
énergétique uniforme par rapport au scénario 1 (Protocole MORE) puisque chaque nœud
capteur qui est dans l’état actif et qui arrive à recevoir correctement un paquet est susceptible
d’être relais [43].

‐Our scheme ‐More Protocol
MJ
500

400

300

200

100

0
1 2 3 4 5 6 7 8 9 10

Figure 3. Consommation énergétique des deux scénarios.

4-1. Evaluation du débit

L’évaluation suivante concerne le débit des deux scénarios mesuré en nombre de paquets reçus
par la destination par seconde. La CDF ‘Cumulative Distribution Function’ du débit après 20
exécutions est illustrée en figure 4 qui montre que le débit du premier scénario est inférieur à 280

  82
Chapitre 5 : Résultats de simulation

paquets/seconde avec une probabilité de 60%. Par contre, le débit du second scénario est
inférieur à 360 paquets/seconde pour la même probabilité ; ce qui résulte d’un gain de 22%.

CDF of the throughput  

Our scheme
MORE

0.8
CDF

0.6

0.4

0.2

0
200 220 240 260 280 300 320 340 360 380 400
Throughput (packets/s)

Figure 4. CDF du débit des deux scénarios.

Les statistiques concernant la CDF du débit des deux scénarios sont comme suit :

Scénario1  Scénario2   
     
     
     
     
 min: 2.019450000000000e+002   min: 3.484160000000000e+002 
 max: 3.436620000000000e+002   max: 3.978330000000000e+002 
 mean: 2.676452000000000e+002   mean: 3.656725000000000e+002 
 median: 2.674945000000000e+002   median: 3.614585000000000e+002 
 std: 50.220062540152639   std: 12.042599271358585 

  83
Chapitre 5 : Résultats de simulation

4-1-3. Evaluation du temps de terminaison

L’effet de la probabilité d’effacement sur le temps de terminaison a été également étudié. Pour
cela, nous avons considéré que la probabilité d’effacement est la même sur tous les liens. Les
courbes de bas en haut correspondent à un nombre de paquets égal à 10, 20 et 30 respectivement.
La figure 5 montre que la probabilité d’effacement ainsi que le nombre de paquets sont deux
paramètres importants. De plus, le temps de terminaison du scénario 2 est inférieur par rapport
au temps de terminaison du scénario 1. Ceci est directement lié au débit ; résultat qui a été
montré par l’évaluation précédente. Les barres qui apparaissent sur la figure représentent les
intervalles du temps de terminaison. Lorsqu’une barre est absente ceci implique que la valeur
inférieure de l’intervalle coïncide avec la valeur supérieure.

Completion time
6

4
Completion time

0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Erasure probability
 
Figure 5. Temps de terminaison des deux scénarios en fonction de la probabilié d’effacement. 

4-1-4. Impact du nombre des paquets

  84
Chapitre 5 : Résultats de simulation

Enfin, nous avons considéré le scenario2 tout en estimant la probabilité d’effacement. Dans
cette simulation, nous avons déployé 10 nœuds capteurs dans une zone de 600*600 et puis nous
avons augmenté le nombre de nœuds à 25. Autrement dit, on a augmenté la densité. La courbe en
vert correspond au déploiement de 25 capteurs tandis que la courbe en rose correspond au
déploiement de 10 nœuds capteurs. La figure 6 montre que l’accroissement de la densité permet
de réduire le temps de terminaison

Completion time under the average erasure probability 

6   

Completion time  ‐25 nodes

5 
‐10 nodes 

4 

3 

2 

1 

0   
10  20  30  40 50 60 70 80 90  100 
Number of data packets

Figure 6. Effet de la densité et du nombre de paquets sur le scénario 2.

4-2. Résultat du système de la maximisation de la durée de vie

Le modèle précédent a été testé par le biais de Matlab et Omnet++. Le standard 802.11 a été
utilisé dans ce cas. Pour plus de renseignements à propos du standard 802.11 qui est
généralement employé dans les communications sans fil, le lecteur peut se référer à [51]. Tous
les nœuds capteurs émettent à la même puissance de 10 mW dans la bande passante de 2.4 GHZ.
Ils ont une énergie initiale de 1000 Joule et dépensent 1 Joule pour chaque transmission ou
réception. La température initiale est 14000.

  85
Chapitre 5 : Résultats de simulation

L’impact du paramètre η sur la convergence a fait l’objet de la simulation présentée en figure 7.

Plus précisément, le critère d’arrêt de l’algorithme du recuit simulé dépend de la moyenne du
vecteur des probabilités de réception dont la convergence nécessite une petite valeur pour le
paramètreη. Autrement dit, la figure 7 démontre que la qualité de convergence de la solution
optimale dépend de la fonction de décroissance de la température.
 

0.464 n=0.2
n=0.02

0.462
Mean reception probability

0.46

0.458

0.456

0.454

0.452

0 50 100 150 200 250 300

Number of iterations
 

Figure 7. La probabilité de réception moyenne versus le nombre d’itérations.

4-3. Résultats de localisation et de routage géographique

Les simulations du système de localisation et routage géographique exposé en chapitre 4 ont

été menées moyennant OMNET++ et ont été réalisées au sein du laboratoire Lirmm (Montpellier
2, France). Notons qu’on a adopté une architecture très simple. Chaque capteur est muni de deux
couches : la première est responsable de la mobilité tandis que la seconde est responsable du
routage. Le tableau 2 illustre les valeurs des paramètres considérés. Il est à noter que le nombre
de particules est 50. On estime bien que ce nombre pourra être réellement supporté par des
capteurs ayant de faibles capacités. Les valeurs assignées à la constante c et a sont celles
proposées par les auteurs Rodoplu et Meng ayant déjà proposés le modèle énergétique de base.
Les autres valeurs des paramètres ont été assignées de façon expérimentale.
Nous signalons également que nous nos simulations sont basées sur les aspects suivants :

  86
Chapitre 5 : Résultats de simulation

¾ Un déploiement aléatoire des capteurs.

¾ Une diffusion périodique des messages Hello. Chaque message Hello contient l’identité
du capteur et son énergie.

¾ Un rayon démission égal à 60.

N 50

μ1 20

μ2 90

X 1, X 2 Normal (0 , 1)

ϕ 90

A 2

C 2*108

η 3

α , β 0,75

Tableau 2. Paramètres de simulation du routage géographique.

Les figures 8 et 9 illustrent respectivement le résultat de la prédiction des abscisses et des

ordonnées. La courbe en bleu correspond au résultat obtenu par le modèle de prédiction et la
courbe en rouge correspond au résultat exact associé au modèle de mobilité. Il est très clair qu’au
début de la simulation, l’écart entre les deux modèles est important. Cependant, la précision de
la prédiction s’améliore en fonction du temps d’exécution.

  87
Chapitre 5 : Résultats de simulation

400

300

Abssices

200

100

20 40 60
Temps de simulation

Figure 8. Abscisses prédites versus temps de simulation.

Vue les capacités limitées des capteurs, on a décidé de ne pas augmenter le nombre de particules
au delà de 50. Par contre, on a préféré lancer l’algorithme de routage après un certain temps
d’exécution de la phase de prédiction. Notons également que nous avons préféré de distinguer le
résultat de la prédiction des abscisses de celui des ordonnées. Cela revient au mouvement
aléatoire des capteurs dont la schématisation n’est pas lisible.

300
ordonnées

200

100

20 40 60
Temps de simulation

Figure 9. Ordonnées versus temps de simulation.

  88
Chapitre 5 : Résultats de simulation

Le taux d’acheminement des messages est l’un des paramètres importants lors de l’évaluation
d’un protocole de routage. En effet, les figures 10 et 11 représentent respectivement le taux de
délivrance des messages envoyés par les capteurs à une station de base et l’énergie moyenne
consommée pour acheminer ces messages. Chaque figure contient trois courbes obtenues en
faisant varier le nombre de capteurs. Chaque courbe correspond à l’évaluation de notre
contribution en fonction du paramètre a' .

La figure 10 montre que le choix de a' est déterminant puisque le taux de délivrance est
maximale lorsque la valeur de a' est importante. En augmentant a' , on favorise la sélection d’un
capteur voisin qui s’oriente vers la station de base. D’où l’utilité de la prédiction de la trajectoire
des capteurs afin d’augmenter la chance d’acheminement des messages. Notons également que
lorsque le nombre de capteurs augmente ; le taux d’acheminement se rapproche de 1. Cela
justifie bien le passage à l’échelle de notre contribution.

1,2

1
ta u x d 'a c h e m i n e m e n t

0,8
n=26
0,6 n=31
n=36
0,4

0,2

0
0 0,2 0,4 0,6 0,8 1
a'

Figure 10. Impact du paramètre a' sur le taux d’acheminement.

La figure 11 démontre que a' a un impact sur la consommation énergétique. Plus la valeur de a'
est importante, plus la probabilité de routage efficace en énergie augmente. Par contre, une
diminution de la valeur de a' fait augmenter la dépense énergétique puisque dans ce cas, la
sélection d’un capteur ne tient pas compte de sa position. Néanmoins, le modèle énergétique
utilisé croit de façon exponentielle en fonction de la distance.

  89
Chapitre 5 : Résultats de simulation

2,09E+08
2,08E+08
2,08E+08
2,07E+08 n=26

E n eg ie 2,07E+08 n=31
2,06E+08 n=36

2,06E+08
2,05E+08
2,05E+08
0 0,2 0,4 0,6 0,8 1
a'

Figure 11. Impact du paramètre a' sur la consommation énergétique.

Une analyse croisée de la figure 10 et 11 permet facilement de déduire la valeur optimale de a' . Il
s’agit de la valeur maximisant le taux d’acheminement des messages et minimisant la
consommation énergétique.

Nombre de capteurs a'

26 0,9

31 0,9

36 0,7

'
Tableau 3. Meilleures valeurs du paramètre a .

5. Conclusion

Les performances de notre système principal ont été étudiées. Notons que les résultats obtenus
dépendent des paramètres de la simulation et ont un grand impact sur la convergence de

  90
Chapitre 5 : Résultats de simulation

l’exécution. Fixer les nœuds relais en fonction de la métrique ETX n’est pas une bonne idée en
termes d’énergie, temps de terminaison et du débit surtout que les nouds capteurs basculent entre
l’état actif et passif. La dernière étape de nos simulations a exploité notre contribution pour
l’estimation de la probabilité d’effacement et elle a montré que dans ce cas la densité du réseau
joue un rôle important pour le décodage des paquets envoyés par la source. Notre résultat
secondaire démontre qu’il est possible d’avoir une solution hybride (exacte et approchée) pour
maximiser la durée de vie du réseau.
D’après les simulations réalisées sous Omnet++, le résultat de la prédiction est acceptable par
rapport au modèle de mobilité et ceci ci d’un point de vue erreur de localisation. De plus, le
modèle de prédiction employé s’avère très pratique pour quelques modèles de mobilité tel que
Gauss-Markov. Ainsi, le résultat du taux d’acheminement des messages est encourageant.
A l’issue de cette étude, plusieurs perspectives ont été dressées et seront présentées à la fin de
cette thèse.

  91
 

Conclusion génèrale et perspectives

L’objectif principal de cette thèse est de minimiser le temps d’achèvement nécessaire au

décodage des paquets envoyés par une source. La plus grande partie de notre travail a consisté à
proposer un système où la réception et le décodage des paquets sont modélisés par une chaîne de
Markov. Notre système tire profit des avantages du routage opportuniste avec codage réseau
linéaire aléatoire et fonctionne sous l’hypothèse de récupération d’énergie. La sortie de notre
système détermine la puissance, le nombre de transmissions ainsi que le flot durant chaque
phase. Au travers notre modélisation, une question pertinente concernant l’incertitude de la
puissance lors du calcul de la dérivée a été relevée. En conséquence, le calcul par intervalles
nous a aidés pour trouver une solution au problème rencontré. Le modèle proposé n’est pas
convexe et une autre question concernant le choix d’une méthode adéquate a été posée. La
méthode F-Lipschitz a assuré l’existence d’une solution optimale pour notre problème. Deux cas
ont été étudiés dans cette thèse. Le premier cas suppose une connaissance a priori de la
probabilité d’effacement. Dans ce contexte, deux scénarios ont été simulés. Le premier s’appuie
sur la métrique ETX tandis dans le second, chaque nœud qui soit actif et qui a pu recevoir un
paquet est susceptible de prendre le rôle de relais. Les résultats de simulation obtenus moyennant
Matlab et Omnet++ ont montré les performances du deuxième scénario en termes de la
consommation énergétique et du débit. D’autre part, les simulations menées ont montré que le
temps de terminaison dépend des probabilités d’effacement et du nombre des paquets. Dans le
deuxième cas, une autre chaîne de Markov a été conçue et nous a permis de dériver l’expression
de la probabilité d’effacement. Dans ce contexte, le temps de terminaison a été évalué en
fonction de la densité réseau dont l’augmentation implique un bon SNR lors de la réception.
Un autre résultat intéressant concerne la possibilité d’hybridation entre une méthode de
résolution exacte (programmation linéaire) et une métaheuristique (recuit simulé) pour la
maximisation de la durée de vie d’un réseau de capteurs adoptant le routage opportuniste et le
codage réseau linéaire aléatoire. Dans cette optique, la fonction de décroissance de la
température joue un rôle important pour la convergence du système.
Enfin, le dernier volet concerne la mobilité dans les réseaux de capteurs. Pour cela, une fonction
de routage géographique a été proposée et dépend de la prédiction. D’après les simulations
réalisées, nous précisons que la sélection du voisin dont la direction est plus proche de la
destination a donné des résultats encourageants d’un point de vue dépense énergétique et taux
d’acheminement en respectant le modèle de mobilité Gauss-Markov.

Au terme de ce cheminement, nous sommes à même de discuter les perspectives suivantes :

  92
 

-Le travail démarré dans cette thèse s’est limité à un système centralisé. Sa résolution de manière
distribuée tout en s’appuyant sur des règles simples est une thématique de recherche intéressante.
-Notre contribution dans cette thèse pourra être bien analysée en ayant un model réel pour la
récupération d’énergie (par exemple un modèle de récupération d’énergie solaire).
-L’évanouissement est un problème crucial dans les transmissions sans fil et sa prise en compte
nécessite une réflexion appropriée.
-Notre contribution doit être consolidée dans un certain nombre de directions, notamment la
réalisation d’une étude expérimentale.
-Le résultat de la localisation peut servir au système de routage opportuniste et l’étude de l’effet
des erreurs de location sur le système de routage géographique peut constituer une voie de
recherche intéressante.
-Les performances du routage opportunistes peuvent être évaluées dans un environnement
mobile.
-Enfin, une comparaison entre l’optimisation par métaheuristiques et F-Lipschitz est une
perspective importante qui découle de ce travail de thèse.

  93
Annexe : Calcul par intervalles

L’arithmétique par intervalles est un ensemble d’outils basé sur l’idée de manipuler des
intervalles comme une nouvelle classe de nombres réels. Tout nombre est représenté par un
intervalle le contenant et tout calcul fournit un intervalle qui encadre le résultat recherché.
L’avantage de l’arithmétique par intervalles est double : tenir compte des incertitudes sur les
données et pouvoir manipuler des quantités qui ne sont pas exactement représentables. Par
exemple π sera représenté par [3 .14 , 3 .15 ] . De cette façon, on est sûr que cet intervalle contient la
valeur exacte de π .  

Un intervalle sur R noté [ x ] est défini comme l’ensemble des nombres réels compris entre les
bornes inférieure x et supérieure x tel que [52] :

{
[ x] = [ x , x ] = x ∈ R \ x ≤ x ≤ x }. 
Le milieu, la largeur, le rayon et la magnitude sont quatre propriétés d’un intervalle et sont
définis comme suit :

x+x
mid(x) =
2
w(x) = x − x

w(x)
rad(x) =
2
mig(x) = min{(x), x ∈ x}

Les opérations arithmétiques et ensemblistes classiques définies pour les réels sont étendues aux
intervalles de cette manière [53]:

[x , x ] + [y , y ] = [ x + y , x + y ]
[x , x ] − [y , y ] = [ x - y , x - y ]
[ x , x ] * [ y , y ] = [ min ( x * y , x * y , x * y , x * y ), max( x * y , x * y , x * y , x * y ) ]
[ x , x ] ÷ [ y , y ] = [ min ( x ÷ y , x ÷ y , x ÷ y , x ÷ y ), max( x ÷ y , x ÷ y , x ÷ y , x ÷ y ) ] , 0 ∉ y

Les caractéristiques des intervalles ont permis d’introduire de nouvelles opérations :

[ x ] ∩ [ y ] = {x ∈ [x] et y ∈ [y]}
[ x ] ∪ [ y ] = {x ∈ [x] ou y ∈ [y]}
 
[ x ] \ [ y ] = {x ∈ [x] et y ∉ [y] }
[ x ] * [ y ] = { (x, y ) x ∈ [x] et y ∈ [y]}
Proj x (z ) = {x ∈ [ x ] ∃ y ∈ [ y ]et (x , y ) ∈ Z }

Le problème du calcul par intervalles est que certaines propriétés ne sont pas préservées. La
soustraction n’est pas la réciproque de l’addition et la division n’est pas la réciproque de la
multiplication. Une autre propriété perdue concerne la distributivité de la multiplication par
rapport à l’addition. Quelques travaux se sont concentrés sur l’adaptation du calcul par

  94
Annexe : Calcul par intervalles

intervalles afin de préserver les propriétés classiques du calcul sur les réels. Nous donnons ci-
dessous quelques exemples qui montrent la création des intervalles et leur manipulation par
Intlab [49].

>> x=infsup(5 , 9)

intval x =

[ 5.0000, 9.0000]

>> y = infsup(-2 , 7)

intval y =

[ -2.0000, 7.0000]

>> z= x + y

intval z =

[ 3.0000, 16.0000]

>> z= x- y

intval z =

[ -2.0000, 11.0000]

>> z=x*y

intval z =

[ -18.0000, 63.0000]

>> z=x/y

intval z =

+/-Inf

>> z=sqrt(x)

intval z =

[ 2.2360, 3.0000]

>> z=log(x)

  95
Annexe : Calcul par intervalles

intval z =

[ 1.6094, 2.1973]

>> z=exp(x)

intval z =

1.0e+003 *

[ 0.1484, 8.1031]

>> z1 = x+ y

intval z1 =

[ 3.0000, 16.0000]

>> z1-y

intval ans =

[ -4.0000, 18.0000]

>> q= infsup(5 , 7)

intval q =

[ 5.0000, 7.0000]

>> z=x*(y+ q)

intval z =

[ 15.0000, 126.0000]

>> z1= (x*y + x*q)

intval z1 =

[ 7.0000, 126.0000]

  96
 

Références bibliographiques

[1] K. Beydoune, ‘Conception d’un protocole de routage hiérarchique pour les réseaux de capteurs’,
Thèse de Doctorat, Université Franche Comte, 2009

[2] F. Lepoutre, ‘Capteurs, principes physiques’, CNAM Medias, 2001.

[3] [Link] , ‘Capteurs ‘

[Link]

[4] H. Karl, [Link], ‘Protocols And Architectures For Wireless Sensor Networks, ISBN 13-978-0-470-
09510 2,2007

[5] I-F. Akyildiz, M-C. Vuran, ‘Wireless Sensor Networks’ , ISBN 978-0-470-03601-3(H/B), 2010

[6] A. Gallais, ‘Ordonnancement d'Activité dans les Réseaux de Capteurs : l'Exemple de la Couverture de
surface’, Thèse de Doctorat, Université des Sciences et Technologies de Lille, June 2007.

[7] G. Chalhoub, ‘les reseaux de capteurs sans fil’, Workshop Réseaux et Télécommunication de l'IUT,
2010

[8] J. Kulik, W.R. Heinzelman, H. Balakrishnan: Negotiation–Based Protocols for Disseminating

Information in Wireless Sensor Networks. In: Wireless Networks, Vol 8, pp. 169-185, 2002

[9] C. Saad, ‘Quelques contributions dans les réseaux de capteurs’, Thèse de Doctorat, Université
d’Avignon et Des Pays de Vaucluse , 2008.

[10] S. Chelloug, M. Benmohammed, J-C. Konig, “Prédiction de la mobilité pour un routage

géographique efficace en énergie dans les réseaux de capteurs mobiles «, in the proceedings of the
JDIR’09, pp. 139-144, Belfort, France, 2009.

[11] S. Sudevalayam, P. Kulkarni, ‘Energy harvesting sensor nodes: Survey and implications.
Communications Surveys & Tutorials’ , pages 1–19, 2010.

[12] A. Kansal, J. Hsu, S. Zahedi,, M-B. Srivastava, ‘Power management in energy harvesting sensor
networks’, in ACM Trans. on Embedded Computing Sys., vol. 6, no. 4, pp. 32, ACM, New York, NY,
USA, December 2007

[13] C. Moser, ‘Power Management in Energy Harvesting Embedded Systems’, Phd Dissertation, SWISS
Federal Institute Of Technology, 2009

  97
 

[14] V. Joseph, V. Sharma , U. Mukherji, ‘Joint power control, scheduling and routing for Multihop
Energy harvesting Sensor Networks’, in 4th ACM International Workshop,PM2HW2N in MSWiM,
Spain, October 2009

[15] H. Kwon, D. Noh, J. Kim, J. Lee, D. Lee , H. Shin , ‘Low-Latency Routing for Energy-Harvesting
Sensor Networks’ , Springer Berlin, 2007, vol. Volume 4611, no. 978-3-540-73548-9.

[16] [Link]

[17] S. Dietler, ‘Implementation de codes de Reed-Solomon sur FPGA pour communications spatiales’,
projet de diplome, Hute Ecole d’ingenieur et de gestion du Canton de Vaud, 2006

[18] C. Fragouli, E. Soljanin , ‘Network Coding Fundamentals, in Foundations and Trends in

Networking’ , vol. Vol. 2, Issue 1, p. 1-133, 2007

[19] A. Mahmino, ‘Application du codage reseau aux architectures a garanties de qualitie de service’,
These de Doctorat, Universite de Toulouse, 2009
[20] T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros, J. Shi, B. Leong, “A Random Linear
Network Coding Approach to Multicast”, the IEEE Transactions on Information Theory.

[21] S. Chachulski, “Trading structure for randomness in wireless opportunistic routing’, Master’s thesis,
MIT, 2007.

[22] S. Chachulski, M. Jennings, S. Katti, and D. Katabi, “Trading structure for randomness in wireless
opportunistic routing,” in SIGCOMM’07, Kyoto, Japan, Aug. 2007

[23] S. Biswas, R. Morris, ’opportunistic multi-hop routing for wireless networks’, ACMSIG COMM’05

[24] [Link]

[25] E. Rozner, J. Seshadri, [Link], [Link], ‘SOAR: Simple Opportunistic Adaptive Routing Protocol
for Wireless Mesh Networks’ . IEEE Transactions on Mobile Computing 2009.

[26] T. El-Ghazali, Metaheuristics: from design to implementation, ISBN 978-0-470-27858-1

[27] [Link]

[28] C. Fischione, “Fast-Lipschitz optimization with wireless sensor networks applications”, IEEE
transactions on automatic control, vol 56, NO 10, pp. 2319-2331, October, 2011.

[29] C. Fischione, “F-Lipschitz optimization”, IR-EE-RT_2010:023, April, 2010.

[30] M. Jakobson, ‘‘On some extensions and performance of Fast-Lipschitz optimization’’, Master thesis,
Skotholm, 2011.

[31] K. Kalpakis, S. Tang, ‘’A Combinatorial Algorithm for the Maximum Lifetime Data Gathering with
Aggregation Problem in Sensor Networks’’. In the Proceedings of the 9th IEEE International Symposium
on a World of Wireless, Mobile and Multimedia Networks (WOWMOM 2008), pp. 1-8, Newport Beach,
CA, USA, June 23-26, 2008

  98
 

[32] J.H. Chang and L. Tassiulas, “Maximum lifetime routing in wireless sensor networks,” IEEE/ACM
Trans. Netw., vol. 12, no. 4, pp. 609–619, 2004.

[33] R. Madan, S. Cui, S. Lall, and A. Goldsmith, ‘‘Cross-Layer Design for Lifetime Maximization in
Interference-limited Wireless Sensor Networks’’, IEEE Transactions on Wireless Communications, Vol.
5, No. 11, pp. 3142-3152, November 2006

[34] M. Kaliszan and S. Stanczak , ‘‘Maximizing Lifetime in Wireless Sensor Networks under
Opportunistic Routing ’’ , 44th Asilomar Conference on Signals, Systems and Computers, Nov. 2010.

[35] S. Chelloug, M. Benmohammed, “Simulated annealing for maximizing the lifetime of

sensor networks under opportunistic routing” , in the proceedings of BWCCA, pp.14-20, Victoria,
Canada, November 2012.

[36] K. Zeng, ‘‘Opportunistic Routing in Multihop Wireless Networks: Capacity, Energy Efficiency, and
Security’’, Phd dissertation, Worcester Polytechnic Institute, 2008.

[37] S. Chelloug, M. Benmohammed , ‘Maximizing the Lifetime of Sensor Networks under Joint
Opportunistic Routing and Scheduling’ in the proceedings of World Academy of Science,
Engineering and Technology 69 2012, ISSN 2010-3778, pp. 1188- 1192, 2012.

[38] D. Lucani, M. Stojanovic , M. Médard, “Random Linear Network Coding for Time Division
Duplexing: When To Stop Talking And Start Listening," in Proc. INFOCOM 2009, Rio de Janeiro,
Brazil, Apr. 2009.

[39] D. Lucani, M. Medard, M. Stojanovic, “Random Linear Network Coding for Time Division
Duplexing: Field Size Considerations", in Proc. GLOBECOM 2009, Hawaii, USA, Dec. 2009

[40] D. Lucani, M. Medard, M. Stojanovic, “Random Linear Network Coding for Time Division
Duplexing: Energy Analysis," in Proc. ICC 2009, Dresden, Germany, Jun. 2009.

[41] M. Rousignol, “Processus stochastiques”, Master de mathématiques, Universite Paris-Est, 2008.

[42] J. Yang, [Link], “ Packet Optimal Scheduling in an Energy Harvesting communication system”,
IEEE transactions on communications, Vol.60, No. 1, January 2012.

[43] S. Chelloug, M. Benmohammed, “Minimizing the completion time in wireless sensor networks with
energy harvesting under opportunistic routing and random linear network coding”, The international
journal of research and reviews in wireless sensor networks (IJRRWSN), Vol. 2, N°. 2, June 2012, ISSN:
2047-0037, pp.93-101.

[44] [Link], I. Chatzigeorgiou, I-J. Wassell, "Randomly Select and Forward: Erasure Probability
Analysis of a Probabilistic Relay Channel Model," 2009 IEEE Information Theory Workshop (ITW 2009),
Taormina, Italy, Oct 2009

[45] Y. Wu, S. Fahmy, N-B. Shroff, "On the Construction of a Maximum-Lifetime Data Gathering Tree
in Sensor Networks: NP-Completeness and Approximation Algorithm," In Proceedings of IEEE
INFOCOM (the conference on computer communications), 9 pp., April 2008.

  99
 

[46] D. Bertsimas, J. Tsitsiklis, ‘‘Simulated Annealing’’, in the proceedings of statistical science, Vol. 8,
N° 1, pp. 10-15, 1993.
[47] L. Mihaylova, D. Angelova, S. Honary, D-R. Bull, C-N. Canagarajah, ‘Mobility tracking in cellular
Networks using particle filtering ‘ , IEEE transactions on wireless communications, Vol.6, N°.10, 2007.

[48] A. Vargas, ‚’Omnet++’

[Link]

[49] S. M-Rump‚’Intlab’

[Link]

[50] J.S-Plank
[Link]

[51] [Link] et al. ,’ Architecture Taxonomy for Control and Provisioning of Wireless Access Points
(CAPWAP)’

[Link]

[52] F. Mourad, H. Snoussi, F. Abdallah, C. Richard, ‘‘Localisation par intervalles basée sur les ancres et
les non-ancres dans les réseaux de capteurs mobiles’’. GRETSI 09, Dijon, France, 8-11 Sep., 2009.

[53] N. Revol, ‘‘Introduction à l’arithmétique par intervalles’’ , rapport de recherche, ISSN 0249-6399,
Université des sciences et technologies de Lille, 2001.

  100
 Nom du document :  Copie‐corrigée1 
Répertoire :  I: 
Modèle :  C:\Documents and Settings\user\Application 
Data\Microsoft\Modèles\[Link] 
Titre :  Ministère de l’enseignement supérieur et de la recherche 
scientifique 
Sujet :   
Auteur :    
Mots clés :   
Commentaires :   
Date de création :  06/04/2013 06:34:00 
N° de révision :  2 
Dernier enregistr. le :  06/04/2013 06:34:00 
Dernier enregistrement par :  pc 
Temps total d'édition :  2 Minutes 
Dernière impression sur :  06/04/2013 01:57:00 
Tel qu'à la dernière impression 
  Nombre de pages :  107 
  Nombre de mots :  26 276 (approx.) 
  Nombre de caractères :  144 524 (approx.)