Compare commits
No commits in common. "feature/simpy-integration-and-static-dynamic-comparison" and "main" have entirely different histories.
feature/si
...
main
@ -1,117 +0,0 @@
|
||||
# Hybrid SimPy Implementation
|
||||
|
||||
## Overview
|
||||
|
||||
Two SimPy integration approaches available in the codebase:
|
||||
|
||||
1. **Lightweight** (`simpy_simulator.py`) - Simple wrapper
|
||||
2. **Hybrid** (`simpy_simulator_hybrid.py`) - Full refactor with event-driven architecture
|
||||
|
||||
Both approaches generate identical results. Choose based on your preference.
|
||||
|
||||
---
|
||||
|
||||
## Comparison
|
||||
|
||||
### Lightweight Wrapper
|
||||
- 120 lines
|
||||
- Wraps existing LEACH/LEACHC
|
||||
- Simple, non-breaking change
|
||||
- Fast execution (~30 seconds)
|
||||
|
||||
Pros:
|
||||
- Minimal code changes
|
||||
- Backward compatible
|
||||
- Easy to understand
|
||||
|
||||
Cons:
|
||||
- Less aggressive SimPy adoption
|
||||
- Wrapper abstraction layer
|
||||
|
||||
### Hybrid Full-Featured
|
||||
- 470 lines
|
||||
- Complete simulator refactor
|
||||
- Proper event-driven model
|
||||
- Parallel processes
|
||||
- DRY/KISS principles
|
||||
|
||||
Pros:
|
||||
- True event-driven architecture
|
||||
- Parallel mobility processes
|
||||
- Professional code quality
|
||||
- Full SimPy compliance
|
||||
|
||||
Cons:
|
||||
- Larger codebase
|
||||
- More complex
|
||||
|
||||
---
|
||||
|
||||
## Usage
|
||||
|
||||
### Default (Lightweight)
|
||||
```bash
|
||||
python3 code/main.py
|
||||
```
|
||||
|
||||
### Hybrid
|
||||
```bash
|
||||
python3 code/main.py --simpy-hybrid
|
||||
```
|
||||
|
||||
### Test Hybrid Directly
|
||||
```bash
|
||||
python3 code/simpy_simulator_hybrid.py
|
||||
```
|
||||
|
||||
---
|
||||
|
||||
## Architecture
|
||||
|
||||
Both simulators support:
|
||||
- Static and dynamic networks via `ENABLE_MOBILITY` flag
|
||||
- 6 test scenarios with different packet sizes and activity levels
|
||||
- 10 performance metrics (FDN, FMR, DLBI, RSPI, etc.)
|
||||
- Comprehensive analysis and comparison
|
||||
- CSV and PNG output
|
||||
|
||||
---
|
||||
|
||||
## Code Quality
|
||||
|
||||
Hybrid simulator demonstrates:
|
||||
- DRY principles (reusable helper methods)
|
||||
- KISS architecture (simple, focused methods)
|
||||
- Proper event-driven model (SimPy processes)
|
||||
- Event logging and state management
|
||||
- Clean separation of concerns
|
||||
|
||||
---
|
||||
|
||||
## Performance
|
||||
|
||||
- Dynamic+Static simulation: ~30-45 seconds
|
||||
- 6 scenarios × 2 protocols each
|
||||
- Results identical between both approaches
|
||||
|
||||
---
|
||||
|
||||
## Metrics
|
||||
|
||||
Both simulators compute:
|
||||
1. First Dead Node (FDN)
|
||||
2. First Muted Round (FMR)
|
||||
3. Dynamic Load Balancing Index (DLBI)
|
||||
4. Relative Silence Period Index (RSPI)
|
||||
5. Alive nodes count
|
||||
6. Residual energy
|
||||
7. Packet statistics
|
||||
|
||||
---
|
||||
|
||||
## Files
|
||||
|
||||
- `code/simpy_simulator.py` - Lightweight wrapper
|
||||
- `code/simpy_simulator_hybrid.py` - Hybrid full-featured
|
||||
- `code/main.py` - Simulation controller
|
||||
- `code/analysis_static_dynamic.py` - Comparative analysis
|
||||
288
README.md
288
README.md
@ -1,89 +1,257 @@
|
||||
# LEACH vs LEACH-C Simulation
|
||||
# Simulation LEACH vs LEACH-C pour Réseaux Dynamiques
|
||||
|
||||
Discrete event simulation of LEACH and LEACH-C clustering protocols for wireless sensor networks with node mobility.
|
||||
## Vue d'ensemble
|
||||
|
||||
## Installation
|
||||
Ce projet implémente une simulation complète des protocoles **LEACH** (Low-Energy Adaptive Clustering Hierarchy) et **LEACH-C** (centralisé) pour des réseaux de capteurs sans fil (WSN) avec **mobilité dynamique** des nœuds.
|
||||
|
||||
**Contexte** : Agriculture de précision - suivi en temps réel de bovins avec capteurs se déplaçant dans un champ.
|
||||
|
||||
**Deadline** : 5 novembre 2025, 23:42
|
||||
|
||||
---
|
||||
|
||||
## Structure du Projet
|
||||
|
||||
```
|
||||
/algo/
|
||||
├── code/
|
||||
│ ├── config.py # Configuration et constantes
|
||||
│ ├── node.py # Classe Node
|
||||
│ ├── metrics.py # Classe Metrics (10 métriques)
|
||||
│ ├── leach.py # Protocole LEACH décentralisé
|
||||
│ ├── leach_c.py # Protocole LEACH-C centralisé
|
||||
│ ├── main.py # Contrôleur principal
|
||||
│ ├── analysis.py # Analyseur et graphiques
|
||||
│ └── run.sh # Script de lancement
|
||||
├── results/
|
||||
│ ├── simulation_results.json # Résultats bruts
|
||||
│ ├── summary.csv # Tableau récapitulatif
|
||||
│ ├── 01_FDN_Comparison.png # Graphique FDN
|
||||
│ ├── 02_FMR_Comparison.png # Graphique FMR
|
||||
│ ├── 03_DLBI_Comparison.png # Graphique DLBI
|
||||
│ ├── 04_RSPI_Comparison.png # Graphique RSPI
|
||||
│ └── 05_Alive_Nodes_Over_Time.png
|
||||
└── rapport/
|
||||
└── Rapport_LEACH_LEACHC.typ # Rapport complet (Typst + PDF)
|
||||
```
|
||||
|
||||
---
|
||||
|
||||
## Comment Exécuter
|
||||
|
||||
### 1. Installation des dépendances
|
||||
|
||||
With Poetry:
|
||||
```bash
|
||||
poetry install
|
||||
poetry run python code/main.py
|
||||
pip install matplotlib
|
||||
```
|
||||
|
||||
With pip:
|
||||
### 2. Lancer la simulation
|
||||
|
||||
```bash
|
||||
pip install -r requirements.txt
|
||||
python3 code/main.py
|
||||
cd /home/paul/algo
|
||||
python code/main.py
|
||||
```
|
||||
|
||||
## Running
|
||||
### 3. Générer les graphiques et analyses
|
||||
|
||||
Default (lightweight simulator):
|
||||
```bash
|
||||
python3 code/main.py
|
||||
python code/analysis.py
|
||||
```
|
||||
|
||||
With hybrid full-featured simulator:
|
||||
```bash
|
||||
python3 code/main.py --simpy-hybrid
|
||||
```
|
||||
Les résultats seront sauvegardés dans `/home/paul/algo/results/`
|
||||
|
||||
## Simulators
|
||||
---
|
||||
|
||||
Two SimPy implementations available:
|
||||
## Implémentation
|
||||
|
||||
1. **Lightweight** - Simple event-driven wrapper (120 lines)
|
||||
2. **Hybrid** - Full discrete event simulator with parallel processes (470 lines)
|
||||
### Protocoles
|
||||
|
||||
Both generate identical results. See `HYBRID_APPROACH.md` for comparison.
|
||||
#### **LEACH (Décentralisé)**
|
||||
- Élection aléatoire des cluster heads (probabilité p)
|
||||
- Formation de clusters basée sur proximité
|
||||
- Communication nœud → CH → BS
|
||||
- Agrégation de données au niveau CH
|
||||
|
||||
## Output
|
||||
#### **LEACH-C (Centralisé)**
|
||||
- BS reçoit l'état de tous les nœuds
|
||||
- Calcul des clusters optimaux (heuristique : sélection par énergie)
|
||||
- Distribution optimale des rôles
|
||||
- Moins aléatoire mais plus coûteux en énergie
|
||||
|
||||
Generated files in `results/`:
|
||||
- `simulation_results_dynamic.json` - Dynamic network results
|
||||
- `simulation_results_static.json` - Static network results
|
||||
- `comparison_static_dynamic.csv` - Comparison table
|
||||
- PNG graphs comparing metrics
|
||||
### Mobilité Dynamique
|
||||
|
||||
## Configuration
|
||||
- Chaque nœud se déplace aléatoirement chaque round
|
||||
- Déplacement max : 5 mètres
|
||||
- Restent dans les limites du champ (100m × 100m)
|
||||
- Impact majeur sur stabilité et efficacité
|
||||
|
||||
Edit `code/config.py` to change:
|
||||
- Network size, packet size
|
||||
- Energy parameters
|
||||
- Simulation scenarios
|
||||
- ENABLE_MOBILITY flag (static vs dynamic)
|
||||
|
||||
## Structure
|
||||
### Modèle Énergétique
|
||||
|
||||
```
|
||||
code/
|
||||
├── main.py - Simulation controller
|
||||
├── leach.py, leach_c.py - Protocol implementations
|
||||
├── node.py - Node class
|
||||
├── metrics.py - Performance metrics
|
||||
├── config.py - Configuration
|
||||
├── simpy_simulator.py - Lightweight wrapper
|
||||
├── simpy_simulator_hybrid.py - Full hybrid simulator
|
||||
└── analysis.py - Analysis and plotting
|
||||
E_Tx(l, d) =
|
||||
- Si d ≤ d0 : E_elec×l + E_fs×l×d²
|
||||
- Si d > d0 : E_elec×l + E_mp×l×d⁴
|
||||
|
||||
results/ - Generated simulation outputs
|
||||
rapport/ - Final report
|
||||
E_Rx(l) = E_elec × l
|
||||
E_Agg(l) = E_da × l
|
||||
|
||||
d0 = sqrt(E_fs / E_mp)
|
||||
```
|
||||
|
||||
## Metrics
|
||||
---
|
||||
|
||||
10 performance metrics calculated:
|
||||
- First Dead Node (FDN)
|
||||
- First Muted Round (FMR)
|
||||
- Dynamic Load Balancing Index (DLBI)
|
||||
- Relative Silence Period Index (RSPI)
|
||||
- Energy consumption
|
||||
- Packet statistics
|
||||
- Node statistics
|
||||
## Métriques Implémentées
|
||||
|
||||
## Scenarios
|
||||
### 1. **Nœuds Vivants** (Alive Nodes Count)
|
||||
Nombre de nœuds actifs après chaque round.
|
||||
|
||||
6 test scenarios with varying:
|
||||
- Packet sizes (2000-4000 bits)
|
||||
- Activity probability (0.05-0.95)
|
||||
- Network size (100-200 nodes)
|
||||
### 2. **Paquets vers CH** (Packets to Cluster Head)
|
||||
Nombre total de paquets envoyés par les nœuds réguliers vers leurs CHs.
|
||||
|
||||
### 3. **Paquets vers BS** (Packets to Base Station)
|
||||
Nombre total de paquets envoyés par les CHs vers la station de base.
|
||||
|
||||
### 4. **Énergie Résiduelle** (Residual Energy)
|
||||
Énergie restante dans chaque nœud.
|
||||
|
||||
### 5. **Muted Rounds**
|
||||
Nombre de rounds où **aucun CH n'est élu** (communication impossible).
|
||||
|
||||
### 6. **FMR** (First Muted Round)
|
||||
Le round exact où le premier silence apparaît.
|
||||
|
||||
### 7. **FDN** (First Dead Node)
|
||||
Le round quand le **premier nœud** épuise son énergie.
|
||||
|
||||
### 8. **Last Dead Node**
|
||||
Le round quand le **dernier nœud** meurt.
|
||||
|
||||
### 9. **DLBI** (Dynamic Load Balancing Index)
|
||||
|
||||
$$DLBI = \frac{1}{N} \sum_{r=1}^{N} DLBI_r$$
|
||||
|
||||
$$DLBI_r = 1 - \frac{\sum(L_{j,r} - \bar{L}_r)^2}{m_r \times \bar{L}_r^2}$$
|
||||
|
||||
**Interprétation** : Évalue l'équilibre de charge entre les CHs.
|
||||
- Proche de 1 = distribution équilibrée
|
||||
- Bas = déséquilibre grave
|
||||
|
||||
### 10. **RSPI** (Relative Silence Period Index)
|
||||
|
||||
$$RSPI = \frac{2 \times [(1 - FR_{muted}/R_{max}) \times (1 - LR_{dead}/R_{max})]}{(1 - FR_{muted}/R_{max}) + (1 - LR_{dead}/R_{max})}$$
|
||||
|
||||
**Interprétation** : Moyenne harmonique entre résilience et durée de vie.
|
||||
|
||||
---
|
||||
|
||||
## Scénarios de Test
|
||||
|
||||
| Scénario | Paquets (l) | Probabilité (p) | Nœuds (n) |
|
||||
|----------|-------------|-----------------|-----------|
|
||||
| 1 | 2000 | 0.05 | 100 |
|
||||
| 2 | 2000 | 0.50 | 100 |
|
||||
| 3 | 2000 | 0.95 | 100 |
|
||||
| 4 | 4000 | 0.05 | 100 |
|
||||
| 5 | 4000 | 0.05 | 200 |
|
||||
| 6 | 4000 | 0.10 | 200 |
|
||||
|
||||
---
|
||||
|
||||
## Résultats
|
||||
|
||||
Les résultats incluent :
|
||||
|
||||
1. **Fichier JSON** : Données complètes de chaque round
|
||||
2. **CSV récapitulatif** : Tableau avec toutes les métriques
|
||||
3. **Graphiques** :
|
||||
- FDN Comparison
|
||||
- FMR Comparison
|
||||
- DLBI Comparison
|
||||
- RSPI Comparison
|
||||
- Nombre de nœuds vivants au fil du temps
|
||||
|
||||
---
|
||||
|
||||
## Points Importants
|
||||
|
||||
### Dynamique vs Statique
|
||||
- **Statique** : Clusters stables, peu d'overhead
|
||||
- **Dynamique** : Clusters instables, plus d'énergie perdue, plus réaliste
|
||||
|
||||
### Rounds Muets (Muted Rounds)
|
||||
Quand **aucun nœud n'est élu** comme CH → communication impossible. Problème majeur en réseau dynamique.
|
||||
|
||||
### LEACH vs LEACH-C
|
||||
- **LEACH** : Scalable, décentralisé, mais élection aléatoire
|
||||
- **LEACH-C** : Meilleure distribution, plus coûteux énergétiquement
|
||||
|
||||
### Impact de la Mobilité
|
||||
La mobilité dynamique cause :
|
||||
- Augmentation de la consommation d'énergie
|
||||
- Plus de muted rounds
|
||||
- Nécessité de réélections fréquentes
|
||||
|
||||
---
|
||||
|
||||
## Technologies Utilisées
|
||||
|
||||
- **Python 3.x**
|
||||
- **Matplotlib** : Visualisation des résultats
|
||||
- **JSON** : Sauvegarde des résultats
|
||||
- **Simulation événementielle** : Approche discrète des rounds
|
||||
|
||||
---
|
||||
|
||||
## Fichiers Principaux
|
||||
|
||||
### `config.py`
|
||||
Configuration globale, paramètres, scénarios.
|
||||
|
||||
### `node.py`
|
||||
Classe représentant un capteur (position, énergie, états).
|
||||
|
||||
### `metrics.py`
|
||||
Collecte des 10 métriques de performance.
|
||||
|
||||
### `leach.py`
|
||||
Implémentation du protocole LEACH décentralisé.
|
||||
|
||||
### `leach_c.py`
|
||||
Implémentation du protocole LEACH-C centralisé.
|
||||
|
||||
### `main.py`
|
||||
Contrôleur principal : crée les nœuds, lance les protocoles.
|
||||
|
||||
### `analysis.py`
|
||||
Analyseur et générateur de graphiques.
|
||||
|
||||
---
|
||||
|
||||
## Ressources Académiques
|
||||
|
||||
1. **LEACH Original** : W. B. Heinzelman et al., "An application-specific protocol architecture for wireless microsensor networks", IEEE Trans. Wireless Commun., 2002
|
||||
|
||||
2. **LEACH-C** : W. B. Heinzelman et al., "Energy-efficient communication protocol for wireless microsensor networks", Proc. HICSS, 2000
|
||||
|
||||
3. **Efficacité Énergétique** : N. Wang & H. Zhu, "An energy efficient algorithm based on LEACH protocol", Proc. ICCSEE, 2012
|
||||
|
||||
---
|
||||
|
||||
## Checklist
|
||||
|
||||
- [x] Implémentation LEACH (décentralisé)
|
||||
- [x] Implémentation LEACH-C (centralisé)
|
||||
- [x] Support mobilité dynamique
|
||||
- [x] Modèle énergétique complet
|
||||
- [x] 10 métriques de performance
|
||||
- [x] 6 scénarios de test
|
||||
- [x] Génération de graphiques
|
||||
- [x] Rapport complet (10 pages max)
|
||||
|
||||
---
|
||||
|
||||
## 📞 Contact
|
||||
|
||||
Pour des questions ou clarifications, veuillez consulter les spécifications du projet.
|
||||
|
||||
**Deadline** : 5 novembre 2025, 23:42 ⏰
|
||||
|
||||
BIN
code/__pycache__/config.cpython-312.pyc
Normal file
BIN
code/__pycache__/config.cpython-312.pyc
Normal file
Binary file not shown.
BIN
code/__pycache__/leach.cpython-312.pyc
Normal file
BIN
code/__pycache__/leach.cpython-312.pyc
Normal file
Binary file not shown.
BIN
code/__pycache__/leach_c.cpython-312.pyc
Normal file
BIN
code/__pycache__/leach_c.cpython-312.pyc
Normal file
Binary file not shown.
BIN
code/__pycache__/metrics.cpython-312.pyc
Normal file
BIN
code/__pycache__/metrics.cpython-312.pyc
Normal file
Binary file not shown.
BIN
code/__pycache__/node.cpython-312.pyc
Normal file
BIN
code/__pycache__/node.cpython-312.pyc
Normal file
Binary file not shown.
@ -1,227 +0,0 @@
|
||||
"""
|
||||
Analysis and Visualization for Static vs Dynamic Simulation Comparison.
|
||||
|
||||
This module compares results between static (no mobility) and dynamic (with mobility)
|
||||
network simulations, generating comparison metrics and visualizations.
|
||||
"""
|
||||
|
||||
import json
|
||||
import csv
|
||||
from pathlib import Path
|
||||
from typing import Dict, List, Tuple
|
||||
import matplotlib.pyplot as plt
|
||||
import numpy as np
|
||||
|
||||
|
||||
class StaticDynamicAnalyzer:
|
||||
"""
|
||||
Compare static and dynamic simulation results.
|
||||
|
||||
Loads JSON results from both modes and generates:
|
||||
- Comparison tables
|
||||
- Impact metrics (percentage differences)
|
||||
- Visualization graphs
|
||||
"""
|
||||
|
||||
def __init__(self, dynamic_file: str, static_file: str):
|
||||
"""
|
||||
Initialize analyzer with result files.
|
||||
|
||||
Args:
|
||||
dynamic_file: Path to dynamic simulation JSON results
|
||||
static_file: Path to static simulation JSON results
|
||||
"""
|
||||
self.dynamic_results = self._load_json(dynamic_file)
|
||||
self.static_results = self._load_json(static_file)
|
||||
self.comparison_data = {}
|
||||
|
||||
@staticmethod
|
||||
def _load_json(filepath: str) -> Dict:
|
||||
"""Load and return JSON results (DRY: single loading method)."""
|
||||
try:
|
||||
with open(filepath, 'r') as f:
|
||||
return json.load(f)
|
||||
except FileNotFoundError:
|
||||
print(f"Warning: {filepath} not found")
|
||||
return {}
|
||||
|
||||
def _extract_metric(self, results: Dict, scenario: str, protocol: str, metric: str):
|
||||
"""Extract a single metric (DRY pattern)."""
|
||||
try:
|
||||
return results[scenario][protocol]['metrics'].get(metric)
|
||||
except (KeyError, TypeError):
|
||||
return None
|
||||
|
||||
def compute_comparison(self) -> Dict:
|
||||
"""
|
||||
Compute static vs dynamic comparison for all scenarios.
|
||||
|
||||
Returns:
|
||||
Dict: Comparison data with impact percentages
|
||||
"""
|
||||
metrics_to_compare = [
|
||||
'first_dead_node_round',
|
||||
'first_muted_round',
|
||||
'dlbi',
|
||||
'rspi',
|
||||
'final_alive_nodes'
|
||||
]
|
||||
|
||||
comparison = {}
|
||||
|
||||
# Get all scenario names from dynamic results
|
||||
for scenario in self.dynamic_results.keys():
|
||||
comparison[scenario] = {'LEACH': {}, 'LEACH-C': {}}
|
||||
|
||||
for protocol in ['LEACH', 'LEACH-C']:
|
||||
for metric in metrics_to_compare:
|
||||
dyn = self._extract_metric(self.dynamic_results, scenario, protocol, metric)
|
||||
stat = self._extract_metric(self.static_results, scenario, protocol, metric)
|
||||
|
||||
# Compute impact (percentage difference)
|
||||
if isinstance(dyn, (int, float)) and isinstance(stat, (int, float)):
|
||||
if stat != 0:
|
||||
impact = ((dyn - stat) / stat) * 100
|
||||
else:
|
||||
impact = 0
|
||||
else:
|
||||
impact = None
|
||||
|
||||
comparison[scenario][protocol][metric] = {
|
||||
'dynamic': dyn,
|
||||
'static': stat,
|
||||
'impact_pct': impact
|
||||
}
|
||||
|
||||
self.comparison_data = comparison
|
||||
return comparison
|
||||
|
||||
def generate_csv_report(self, output_file: str = "comparison_static_dynamic.csv"):
|
||||
"""
|
||||
Generate CSV report of static vs dynamic comparison.
|
||||
|
||||
Args:
|
||||
output_file: Output CSV filename
|
||||
"""
|
||||
with open(output_file, 'w', newline='') as f:
|
||||
writer = csv.writer(f)
|
||||
writer.writerow([
|
||||
'Scenario', 'Protocol', 'Metric',
|
||||
'Dynamic', 'Static', 'Impact(%)'
|
||||
])
|
||||
|
||||
for scenario, protocols in self.comparison_data.items():
|
||||
for protocol, metrics in protocols.items():
|
||||
for metric, values in metrics.items():
|
||||
writer.writerow([
|
||||
scenario,
|
||||
protocol,
|
||||
metric,
|
||||
values.get('dynamic', 'N/A'),
|
||||
values.get('static', 'N/A'),
|
||||
f"{values.get('impact_pct', 'N/A'):.2f}" if values.get('impact_pct') is not None else 'N/A'
|
||||
])
|
||||
|
||||
print(f"CSV report generated: {output_file}")
|
||||
|
||||
def plot_comparison(self, metric: str = 'first_dead_node_round', output_file: str = None):
|
||||
"""
|
||||
Generate comparison bar chart for a metric.
|
||||
|
||||
Args:
|
||||
metric: Metric to compare
|
||||
output_file: Output PNG filename (optional)
|
||||
"""
|
||||
scenarios = list(self.comparison_data.keys())
|
||||
leach_dynamic = []
|
||||
leach_static = []
|
||||
leachc_dynamic = []
|
||||
leachc_static = []
|
||||
|
||||
for scenario in scenarios:
|
||||
leach_dyn = self.comparison_data[scenario]['LEACH'][metric]['dynamic']
|
||||
leach_stat = self.comparison_data[scenario]['LEACH'][metric]['static']
|
||||
leachc_dyn = self.comparison_data[scenario]['LEACH-C'][metric]['dynamic']
|
||||
leachc_stat = self.comparison_data[scenario]['LEACH-C'][metric]['static']
|
||||
|
||||
# Handle None values
|
||||
leach_dynamic.append(leach_dyn if leach_dyn is not None else 0)
|
||||
leach_static.append(leach_stat if leach_stat is not None else 0)
|
||||
leachc_dynamic.append(leachc_dyn if leachc_dyn is not None else 0)
|
||||
leachc_static.append(leachc_stat if leachc_stat is not None else 0)
|
||||
|
||||
x = np.arange(len(scenarios))
|
||||
width = 0.2
|
||||
|
||||
fig, ax = plt.subplots(figsize=(12, 6))
|
||||
ax.bar(x - 1.5*width, leach_dynamic, width, label='LEACH Dynamic')
|
||||
ax.bar(x - 0.5*width, leach_static, width, label='LEACH Static')
|
||||
ax.bar(x + 0.5*width, leachc_dynamic, width, label='LEACH-C Dynamic')
|
||||
ax.bar(x + 1.5*width, leachc_static, width, label='LEACH-C Static')
|
||||
|
||||
ax.set_xlabel('Scenario')
|
||||
ax.set_ylabel(metric.replace('_', ' ').title())
|
||||
ax.set_title(f'Static vs Dynamic Comparison: {metric}')
|
||||
ax.set_xticks(x)
|
||||
ax.set_xticklabels(scenarios, rotation=45, ha='right')
|
||||
ax.legend()
|
||||
ax.grid(axis='y', alpha=0.3)
|
||||
|
||||
plt.tight_layout()
|
||||
|
||||
if output_file is None:
|
||||
output_file = f"comparison_{metric}.png"
|
||||
|
||||
plt.savefig(output_file, dpi=300)
|
||||
print(f"Graph saved: {output_file}")
|
||||
plt.close()
|
||||
|
||||
def print_summary(self):
|
||||
"""Print a summary of static vs dynamic comparison."""
|
||||
print("\n" + "="*80)
|
||||
print("STATIC VS DYNAMIC COMPARISON SUMMARY")
|
||||
print("="*80)
|
||||
|
||||
for scenario in self.comparison_data.keys():
|
||||
print(f"\n{scenario}:")
|
||||
print("-" * 80)
|
||||
|
||||
for protocol in ['LEACH', 'LEACH-C']:
|
||||
metrics = self.comparison_data[scenario][protocol]
|
||||
print(f"\n {protocol}:")
|
||||
|
||||
for metric, values in metrics.items():
|
||||
dyn = values['dynamic']
|
||||
stat = values['static']
|
||||
impact = values['impact_pct']
|
||||
|
||||
if isinstance(dyn, (int, float)) and isinstance(stat, (int, float)):
|
||||
print(f" {metric:30s}: Dynamic={dyn:10.2f}, Static={stat:10.2f}, Impact={impact:+.2f}%")
|
||||
else:
|
||||
print(f" {metric:30s}: Dynamic={dyn}, Static={stat}")
|
||||
|
||||
|
||||
def main():
|
||||
"""Run static vs dynamic analysis."""
|
||||
analyzer = StaticDynamicAnalyzer(
|
||||
"results/simulation_results_dynamic.json",
|
||||
"results/simulation_results_static.json"
|
||||
)
|
||||
|
||||
# Compute comparison
|
||||
analyzer.compute_comparison()
|
||||
|
||||
# Generate reports
|
||||
analyzer.generate_csv_report("results/comparison_static_dynamic.csv")
|
||||
analyzer.print_summary()
|
||||
|
||||
# Generate visualizations for key metrics
|
||||
for metric in ['first_dead_node_round', 'first_muted_round', 'dlbi']:
|
||||
analyzer.plot_comparison(
|
||||
metric,
|
||||
output_file=f"results/comparison_{metric}.png"
|
||||
)
|
||||
|
||||
|
||||
if __name__ == "__main__":
|
||||
main()
|
||||
@ -25,7 +25,6 @@ PACKET_SIZE_DEFAULT = 2000 # bits
|
||||
|
||||
# Mobilité
|
||||
MAX_DISPLACEMENT_PER_ROUND = 5 # mètres
|
||||
ENABLE_MOBILITY = True # False pour mode statique (pas de déplacement)
|
||||
|
||||
# Nombre de rounds de simulation
|
||||
NUM_ROUNDS = 1000 # À adapter selon durée de vie du réseau
|
||||
|
||||
244
code/main.py
244
code/main.py
@ -1,177 +1,205 @@
|
||||
"""
|
||||
Module principal : Simulation complète des protocoles LEACH et LEACH-C
|
||||
"""
|
||||
|
||||
import random
|
||||
import json
|
||||
import sys
|
||||
from datetime import datetime
|
||||
from node import Node
|
||||
from leach import LEACH
|
||||
from leach_c import LEACHC
|
||||
from config import FIELD_WIDTH, FIELD_HEIGHT, INITIAL_ENERGY, SCENARIOS, get_num_rounds_for_scenario, ENABLE_MOBILITY
|
||||
import config
|
||||
from config import (
|
||||
FIELD_WIDTH, FIELD_HEIGHT, INITIAL_ENERGY, BS_POSITION,
|
||||
SCENARIOS, get_num_rounds_for_scenario, DEBUG
|
||||
)
|
||||
|
||||
|
||||
class Simulator:
|
||||
|
||||
def __init__(self, scenario, use_hybrid=False):
|
||||
"""
|
||||
Contrôleur principal de la simulation.
|
||||
Crée les nœuds, lance les protocoles, et collecte les résultats.
|
||||
"""
|
||||
|
||||
def __init__(self, scenario):
|
||||
"""
|
||||
Initialise un simulateur pour un scénario donné.
|
||||
|
||||
Args:
|
||||
scenario (dict): Configuration du scénario (l, p, n, name)
|
||||
"""
|
||||
self.scenario = scenario
|
||||
self.packet_size = scenario["l"]
|
||||
self.probability_ch = scenario["p"]
|
||||
self.num_nodes = scenario["n"]
|
||||
self.scenario_name = scenario["name"]
|
||||
self.use_hybrid = use_hybrid
|
||||
|
||||
self.results = {}
|
||||
self.nodes = []
|
||||
|
||||
|
||||
def initialize_nodes(self):
|
||||
"""Crée et initialise les nœuds."""
|
||||
self.nodes = []
|
||||
|
||||
for i in range(self.num_nodes):
|
||||
# Position aléatoire dans le champ
|
||||
x = random.uniform(0, FIELD_WIDTH)
|
||||
y = random.uniform(0, FIELD_HEIGHT)
|
||||
self.nodes.append(Node(i, x, y, INITIAL_ENERGY))
|
||||
|
||||
|
||||
node = Node(i, x, y, INITIAL_ENERGY)
|
||||
self.nodes.append(node)
|
||||
|
||||
def run_protocol(self, protocol_name, protocol_class):
|
||||
"""
|
||||
Lance un protocole et collecte les résultats.
|
||||
|
||||
Args:
|
||||
protocol_name (str): "LEACH" ou "LEACH-C"
|
||||
protocol_class: Classe du protocole (LEACH ou LEACHC)
|
||||
|
||||
Returns:
|
||||
dict: Métriques et données du protocole
|
||||
"""
|
||||
# Réinitialiser les nœuds
|
||||
for node in self.nodes:
|
||||
node.energy = INITIAL_ENERGY
|
||||
node.is_alive = True
|
||||
node.reset_for_round()
|
||||
|
||||
|
||||
# Créer et lancer le protocole
|
||||
protocol = protocol_class(self.nodes, self.probability_ch, self.packet_size)
|
||||
num_rounds = get_num_rounds_for_scenario(self.num_nodes)
|
||||
|
||||
print(f" Running {protocol_name}...")
|
||||
print(f" Packets: {self.packet_size}, Probability: {self.probability_ch}, Nodes: {self.num_nodes}")
|
||||
|
||||
if self.use_hybrid:
|
||||
from simpy_simulator_hybrid import HybridSimPySimulator
|
||||
simulator = HybridSimPySimulator(protocol_name, self.nodes, self.packet_size,
|
||||
self.probability_ch, num_rounds)
|
||||
result_data = simulator.run()
|
||||
metrics = {
|
||||
"final_alive_nodes": sum(1 for n in self.nodes if n.is_alive),
|
||||
"first_dead_node_round": result_data["fdn"],
|
||||
"first_muted_round": result_data["fmr"],
|
||||
"dlbi": result_data["dlbi"],
|
||||
"rspi": result_data["rspi"],
|
||||
"packets_to_ch": result_data["total_packets_to_ch"],
|
||||
"packets_to_bs": result_data["total_packets_to_bs"],
|
||||
}
|
||||
detailed = result_data.get("rounds_data", [])
|
||||
else:
|
||||
protocol.run_simulation(num_rounds)
|
||||
metrics = protocol.get_metrics(num_rounds)
|
||||
detailed = protocol.get_detailed_metrics()
|
||||
|
||||
print(f" OK - {protocol_name} complete")
|
||||
print(f" Alive: {metrics['final_alive_nodes']}, FDN: {metrics['first_dead_node_round']}")
|
||||
print(f" DLBI: {metrics['dlbi']:.4f}, RSPI: {metrics['rspi']:.4f}")
|
||||
|
||||
return {"protocol": protocol_name, "metrics": metrics, "detailed": detailed}
|
||||
|
||||
|
||||
print(f" Exécution {protocol_name} pour {self.scenario_name}...")
|
||||
print(f" - Packets: {self.packet_size} bits")
|
||||
print(f" - Probabilité: {self.probability_ch}")
|
||||
print(f" - Nœuds: {self.num_nodes}")
|
||||
print(f" - Rounds à exécuter: {num_rounds}")
|
||||
|
||||
protocol.run_simulation(num_rounds)
|
||||
|
||||
metrics = protocol.get_metrics(num_rounds)
|
||||
detailed = protocol.get_detailed_metrics()
|
||||
|
||||
print(f" OK - {protocol_name} terminé")
|
||||
print(f" - Alive nodes: {metrics['final_alive_nodes']}")
|
||||
print(f" - FDN: {metrics['first_dead_node_round']}")
|
||||
print(f" - DLBI: {metrics['dlbi']:.4f}")
|
||||
print(f" - RSPI: {metrics['rspi']:.4f}")
|
||||
|
||||
return {
|
||||
"protocol": protocol_name,
|
||||
"metrics": metrics,
|
||||
"detailed": detailed,
|
||||
}
|
||||
|
||||
def run_simulation(self):
|
||||
"""
|
||||
Lance la simulation complète (LEACH et LEACH-C).
|
||||
"""
|
||||
print(f"\n{'='*60}")
|
||||
print(f"Scenario: {self.scenario_name}")
|
||||
print(f"Simulation: {self.scenario_name}")
|
||||
print(f"{'='*60}")
|
||||
|
||||
|
||||
# Initialiser les nœuds
|
||||
self.initialize_nodes()
|
||||
self.results["LEACH"] = self.run_protocol("LEACH", LEACH)
|
||||
self.results["LEACH-C"] = self.run_protocol("LEACH-C", LEACHC)
|
||||
|
||||
|
||||
# Lancer LEACH
|
||||
leach_results = self.run_protocol("LEACH", LEACH)
|
||||
self.results["LEACH"] = leach_results
|
||||
|
||||
# Lancer LEACH-C
|
||||
leachc_results = self.run_protocol("LEACH-C", LEACHC)
|
||||
self.results["LEACH-C"] = leachc_results
|
||||
|
||||
print(f"{'='*60}\n")
|
||||
|
||||
return self.results
|
||||
|
||||
|
||||
def get_results(self):
|
||||
"""Retourne les résultats de la simulation."""
|
||||
return self.results
|
||||
|
||||
|
||||
def run_all_scenarios(is_static=False, use_hybrid=False):
|
||||
config.ENABLE_MOBILITY = not is_static
|
||||
def run_all_scenarios():
|
||||
"""
|
||||
Lance les simulations pour tous les scénarios.
|
||||
|
||||
Returns:
|
||||
dict: Résultats pour tous les scénarios
|
||||
"""
|
||||
all_results = {}
|
||||
mode = "STATIC" if is_static else "DYNAMIC"
|
||||
approach = "(Hybrid)" if use_hybrid else ""
|
||||
|
||||
|
||||
print(f"\n{'#'*60}")
|
||||
print(f"PHASE: {mode} NETWORKS {approach}")
|
||||
print(f"Started: {datetime.now().strftime('%Y-%m-%d %H:%M:%S')}")
|
||||
print(f"# SIMULATION LEACH vs LEACH-C - RÉSEAUX DYNAMIQUES")
|
||||
print(f"# Démarrage: {datetime.now().strftime('%Y-%m-%d %H:%M:%S')}")
|
||||
print(f"{'#'*60}\n")
|
||||
|
||||
|
||||
for scenario in SCENARIOS:
|
||||
simulator = Simulator(scenario, use_hybrid=use_hybrid)
|
||||
print(f"Scénario: {scenario['name']}")
|
||||
|
||||
simulator = Simulator(scenario)
|
||||
results = simulator.run_simulation()
|
||||
|
||||
all_results[scenario["name"]] = results
|
||||
|
||||
|
||||
print(f"\n{'#'*60}")
|
||||
print(f"Complete: {datetime.now().strftime('%Y-%m-%d %H:%M:%S')}")
|
||||
print(f"# SIMULATIONS TERMINÉES - {datetime.now().strftime('%Y-%m-%d %H:%M:%S')}")
|
||||
print(f"{'#'*60}\n")
|
||||
|
||||
|
||||
return all_results
|
||||
|
||||
|
||||
def save_results(results, output_file):
|
||||
"""
|
||||
Sauvegarde les résultats en JSON.
|
||||
|
||||
Args:
|
||||
results (dict): Résultats de toutes les simulations
|
||||
output_file (str): Chemin du fichier de sortie
|
||||
"""
|
||||
# Convertir en format sérialisable JSON
|
||||
json_results = {}
|
||||
|
||||
for scenario_name, scenario_data in results.items():
|
||||
json_results[scenario_name] = {
|
||||
"LEACH": {
|
||||
"metrics": scenario_data["LEACH"]["metrics"],
|
||||
"detailed_rounds": scenario_data["LEACH"]["detailed"][:20]
|
||||
"detailed_rounds": scenario_data["LEACH"]["detailed"][:20] # Premiers 20 rounds
|
||||
},
|
||||
"LEACH-C": {
|
||||
"metrics": scenario_data["LEACH-C"]["metrics"],
|
||||
"detailed_rounds": scenario_data["LEACH-C"]["detailed"][:20]
|
||||
}
|
||||
}
|
||||
|
||||
|
||||
with open(output_file, 'w') as f:
|
||||
json.dump(json_results, f, indent=2)
|
||||
|
||||
print(f"Results saved: {output_file}")
|
||||
|
||||
print(f"OK - Résultats sauvegardés: {output_file}")
|
||||
|
||||
|
||||
if __name__ == "__main__":
|
||||
use_hybrid = "--simpy-hybrid" in sys.argv
|
||||
|
||||
# Graine de randomisation pour reproductibilité
|
||||
random.seed(42)
|
||||
|
||||
print("\n" + "="*70)
|
||||
print("PHASE 1: DYNAMIC SIMULATIONS")
|
||||
print("="*70)
|
||||
dynamic_results = run_all_scenarios(is_static=False, use_hybrid=use_hybrid)
|
||||
save_results(dynamic_results, "results/simulation_results_dynamic.json")
|
||||
|
||||
print("\n" + "="*70)
|
||||
print("PHASE 2: STATIC SIMULATIONS")
|
||||
print("="*70)
|
||||
random.seed(42)
|
||||
static_results = run_all_scenarios(is_static=True, use_hybrid=use_hybrid)
|
||||
save_results(static_results, "results/simulation_results_static.json")
|
||||
|
||||
print("\n" + "="*70)
|
||||
print("COMPARISON: DYNAMIC vs STATIC")
|
||||
print("="*70)
|
||||
|
||||
for scenario_name in SCENARIOS[0:1]:
|
||||
scenario_label = scenario_name['name']
|
||||
print(f"\n{scenario_label}:")
|
||||
print("-" * 70)
|
||||
|
||||
|
||||
# Lancer toutes les simulations
|
||||
all_results = run_all_scenarios()
|
||||
|
||||
# Sauvegarder les résultats
|
||||
save_results(all_results, "/home/paul/algo/results/simulation_results.json")
|
||||
|
||||
# Afficher un résumé
|
||||
print("\n" + "="*60)
|
||||
print("RÉSUMÉ DES RÉSULTATS")
|
||||
print("="*60)
|
||||
|
||||
for scenario_name, scenario_data in all_results.items():
|
||||
print(f"\n{scenario_name}:")
|
||||
|
||||
for protocol in ["LEACH", "LEACH-C"]:
|
||||
dynamic_metrics = dynamic_results[scenario_label][protocol]["metrics"]
|
||||
static_metrics = static_results[scenario_label][protocol]["metrics"]
|
||||
|
||||
dyn_fdn = dynamic_metrics['first_dead_node_round'] or "N/A"
|
||||
stat_fdn = static_metrics['first_dead_node_round'] or "N/A"
|
||||
dyn_fmr = dynamic_metrics['first_muted_round'] or "N/A"
|
||||
stat_fmr = static_metrics['first_muted_round'] or "N/A"
|
||||
|
||||
metrics = scenario_data[protocol]["metrics"]
|
||||
print(f"\n {protocol}:")
|
||||
print(f" Metric | Dynamic | Static | Difference")
|
||||
if isinstance(dyn_fdn, int) and isinstance(stat_fdn, int):
|
||||
print(f" FDN | {dyn_fdn:7} | {stat_fdn:7} | {stat_fdn - dyn_fdn:10.0f}")
|
||||
else:
|
||||
print(f" FDN | {str(dyn_fdn):7} | {str(stat_fdn):7} | N/A")
|
||||
if isinstance(dyn_fmr, int) and isinstance(stat_fmr, int):
|
||||
print(f" FMR | {dyn_fmr:7} | {stat_fmr:7} | {stat_fmr - dyn_fmr:10.0f}")
|
||||
else:
|
||||
print(f" FMR | {str(dyn_fmr):7} | {str(stat_fmr):7} | N/A")
|
||||
print(f" DLBI | {dynamic_metrics['dlbi']:7.4f} | {static_metrics['dlbi']:7.4f} | {static_metrics['dlbi'] - dynamic_metrics['dlbi']:10.4f}")
|
||||
print(f" RSPI | {dynamic_metrics['rspi']:7.4f} | {static_metrics['rspi']:7.4f} | {static_metrics['rspi'] - dynamic_metrics['rspi']:10.4f}")
|
||||
|
||||
print(f"\nResults saved to results/ directory")
|
||||
print(f" FDN (First Dead Node): {metrics['first_dead_node_round']}")
|
||||
print(f" FMR (First Muted Round): {metrics['first_muted_round']}")
|
||||
print(f" DLBI: {metrics['dlbi']:.4f}")
|
||||
print(f" RSPI: {metrics['rspi']:.4f}")
|
||||
|
||||
10
code/node.py
10
code/node.py
@ -6,7 +6,7 @@ import math
|
||||
import random
|
||||
from config import (
|
||||
E_ELEC, E_FS, E_MP, D0, E_DA,
|
||||
FIELD_WIDTH, FIELD_HEIGHT, MAX_DISPLACEMENT_PER_ROUND, ENABLE_MOBILITY
|
||||
FIELD_WIDTH, FIELD_HEIGHT, MAX_DISPLACEMENT_PER_ROUND
|
||||
)
|
||||
|
||||
|
||||
@ -102,17 +102,13 @@ class Node:
|
||||
Met à jour la position du nœud avec un déplacement aléatoire.
|
||||
Déplacement max = MAX_DISPLACEMENT_PER_ROUND mètres.
|
||||
Reste dans les limites du champ.
|
||||
Only moves if ENABLE_MOBILITY is True (allows static network mode).
|
||||
"""
|
||||
if not ENABLE_MOBILITY:
|
||||
return # No movement in static mode
|
||||
|
||||
angle = random.uniform(0, 2 * math.pi)
|
||||
distance = random.uniform(0, MAX_DISPLACEMENT_PER_ROUND)
|
||||
|
||||
|
||||
new_x = self.x + distance * math.cos(angle)
|
||||
new_y = self.y + distance * math.sin(angle)
|
||||
|
||||
|
||||
# Limiter aux bords du champ
|
||||
self.x = max(0, min(FIELD_WIDTH, new_x))
|
||||
self.y = max(0, min(FIELD_HEIGHT, new_y))
|
||||
|
||||
@ -1,122 +0,0 @@
|
||||
"""
|
||||
Simpy-based Event-Driven Simulator for LEACH and LEACH-C Protocols.
|
||||
|
||||
This module wraps the LEACH and LEACH-C protocols in a discrete event simulation
|
||||
framework using Simpy, allowing for fine-grained control over node movements,
|
||||
cluster head elections, and communication events.
|
||||
|
||||
Key Features:
|
||||
- Event-driven architecture using Simpy's Environment
|
||||
- Discrete time steps for each protocol round
|
||||
- Node mobility as separate events
|
||||
- Metrics collection at defined intervals
|
||||
"""
|
||||
|
||||
import simpy
|
||||
from typing import List, Dict
|
||||
from node import Node
|
||||
from config import ENABLE_MOBILITY
|
||||
|
||||
|
||||
class EventDrivenNetworkSimulator:
|
||||
"""
|
||||
Lightweight event-driven simulator using Simpy framework.
|
||||
|
||||
Uses discrete events for protocol rounds and mobility. Simpler than full
|
||||
concurrent process model - each round is one event with defined substeps.
|
||||
|
||||
Args:
|
||||
protocol: Protocol instance (LEACH or LEACHC)
|
||||
nodes: List of Node objects
|
||||
round_duration: Simulated time per round (default 1.0)
|
||||
"""
|
||||
|
||||
def __init__(self, protocol, nodes: List[Node], round_duration: float = 1.0):
|
||||
self.env = simpy.Environment()
|
||||
self.protocol = protocol
|
||||
self.nodes = nodes
|
||||
self.round_duration = round_duration
|
||||
self.events_log = []
|
||||
|
||||
def _log_event(self, event_type: str, round_num: int = 0, details: Dict = None):
|
||||
"""Log a discrete event (DRY: single logging method)."""
|
||||
self.events_log.append({
|
||||
'time': self.env.now,
|
||||
'event': event_type,
|
||||
'round': round_num,
|
||||
**(details or {})
|
||||
})
|
||||
|
||||
def _execute_round_event(self, round_num: int):
|
||||
"""
|
||||
Execute one round as a discrete event.
|
||||
Substeps: elect CHs → form clusters → communicate → mobility
|
||||
"""
|
||||
self.protocol.run_round()
|
||||
alive_count = sum(1 for n in self.nodes if n.is_alive)
|
||||
|
||||
self._log_event('ROUND_COMPLETE', round_num, {
|
||||
'alive_nodes': alive_count,
|
||||
'avg_energy': sum(n.energy for n in self.nodes) / len(self.nodes) if self.nodes else 0
|
||||
})
|
||||
|
||||
return alive_count > 0
|
||||
|
||||
def simulation_process(self, num_rounds: int):
|
||||
"""Simpy process: Execute all rounds as discrete events."""
|
||||
for round_num in range(num_rounds):
|
||||
yield self.env.timeout(self.round_duration)
|
||||
|
||||
if not self._execute_round_event(round_num):
|
||||
break # All nodes dead
|
||||
|
||||
def run_simulation(self, num_rounds: int) -> Dict:
|
||||
"""Run the event-driven simulation."""
|
||||
self.env.process(self.simulation_process(num_rounds))
|
||||
self.env.run()
|
||||
return self.protocol.get_metrics(num_rounds)
|
||||
|
||||
def get_events_log(self) -> List[Dict]:
|
||||
"""Get the event log."""
|
||||
return self.events_log
|
||||
|
||||
|
||||
if __name__ == "__main__":
|
||||
"""
|
||||
Demo: Event-driven simulation with Simpy.
|
||||
Shows how discrete events are managed by Simpy framework.
|
||||
"""
|
||||
import random
|
||||
from leach import LEACH
|
||||
from config import FIELD_WIDTH, FIELD_HEIGHT, INITIAL_ENERGY
|
||||
|
||||
print("=" * 70)
|
||||
print("SIMPY EVENT-DRIVEN SIMULATOR DEMONSTRATION")
|
||||
print("=" * 70)
|
||||
|
||||
# Create test nodes
|
||||
random.seed(42)
|
||||
test_nodes = []
|
||||
for i in range(20): # Small network for demo
|
||||
x = random.uniform(0, FIELD_WIDTH)
|
||||
y = random.uniform(0, FIELD_HEIGHT)
|
||||
test_nodes.append(Node(i, x, y, INITIAL_ENERGY))
|
||||
|
||||
# Create Simpy-based simulator
|
||||
protocol = LEACH(test_nodes, probability_ch=0.05, packet_size=2000)
|
||||
simpy_sim = EventDrivenNetworkSimulator(protocol, test_nodes)
|
||||
|
||||
print("\nInitializing event-driven simulator with Simpy...")
|
||||
print(f"Initial nodes: {len(test_nodes)}")
|
||||
print("Running 50 rounds with discrete event model...")
|
||||
|
||||
metrics = simpy_sim.run_simulation(num_rounds=50)
|
||||
|
||||
# Display results
|
||||
print(f"\nSimulation completed at time {simpy_sim.env.now}s")
|
||||
print(f"Total discrete events logged: {len(simpy_sim.events_log)}")
|
||||
print(f"Final alive nodes: {metrics['final_alive_nodes']}")
|
||||
print(f"First Dead Node (FDN): {metrics['first_dead_node_round']}")
|
||||
print(f"First Muted Round (FMR): {metrics['first_muted_round']}")
|
||||
print(f"DLBI: {metrics['dlbi']:.4f}")
|
||||
print(f"RSPI: {metrics['rspi']:.4f}")
|
||||
@ -1,230 +0,0 @@
|
||||
import simpy
|
||||
import random
|
||||
from typing import List, Dict, Optional
|
||||
from node import Node
|
||||
from metrics import Metrics
|
||||
from config import FIELD_WIDTH, FIELD_HEIGHT, INITIAL_ENERGY, BS_POSITION, ENABLE_MOBILITY, DEBUG
|
||||
|
||||
|
||||
class HybridSimPySimulator:
|
||||
|
||||
def __init__(self, protocol_name: str, nodes: List[Node], packet_size: int,
|
||||
probability_ch: float, max_rounds: int):
|
||||
self.env = simpy.Environment()
|
||||
self.protocol_name = protocol_name
|
||||
self.nodes = nodes
|
||||
self.packet_size = packet_size
|
||||
self.probability_ch = probability_ch
|
||||
self.max_rounds = max_rounds
|
||||
|
||||
self.round_num = 0
|
||||
self.cluster_heads = []
|
||||
self.clusters: Dict[int, List[int]] = {}
|
||||
self.total_packets_to_ch = 0
|
||||
self.total_packets_to_bs = 0
|
||||
self.muted_rounds = []
|
||||
self.metrics = Metrics()
|
||||
|
||||
def _log_event(self, event_type: str, round_num: int = 0, **details) -> None:
|
||||
pass
|
||||
|
||||
def _get_alive_nodes(self) -> List[Node]:
|
||||
return [n for n in self.nodes if n.is_alive]
|
||||
|
||||
def _find_closest_ch(self, node: Node) -> Optional[int]:
|
||||
if not self.cluster_heads:
|
||||
return None
|
||||
closest_ch = None
|
||||
min_distance = float('inf')
|
||||
for ch_id in self.cluster_heads:
|
||||
distance = node.distance_to(self.nodes[ch_id].x, self.nodes[ch_id].y)
|
||||
if distance < min_distance:
|
||||
min_distance = distance
|
||||
closest_ch = ch_id
|
||||
return closest_ch
|
||||
|
||||
def _elect_cluster_heads_leach(self) -> None:
|
||||
self.cluster_heads = []
|
||||
self.clusters = {}
|
||||
|
||||
for node in self._get_alive_nodes():
|
||||
if random.random() < self.probability_ch:
|
||||
node.is_cluster_head = True
|
||||
self.cluster_heads.append(node.node_id)
|
||||
self.clusters[node.node_id] = [node.node_id]
|
||||
node.cluster_id = node.node_id
|
||||
|
||||
for node in self._get_alive_nodes():
|
||||
if not node.is_cluster_head:
|
||||
closest_ch = self._find_closest_ch(node)
|
||||
if closest_ch is not None:
|
||||
node.cluster_id = closest_ch
|
||||
if closest_ch not in self.clusters:
|
||||
self.clusters[closest_ch] = []
|
||||
self.clusters[closest_ch].append(node.node_id)
|
||||
|
||||
def _elect_cluster_heads_leachc(self) -> None:
|
||||
self.cluster_heads = []
|
||||
self.clusters = {}
|
||||
|
||||
alive_nodes = self._get_alive_nodes()
|
||||
if not alive_nodes:
|
||||
return
|
||||
|
||||
for node in alive_nodes:
|
||||
distance_to_bs = node.distance_to(*BS_POSITION)
|
||||
node.transmit(32, distance_to_bs)
|
||||
|
||||
num_ch = max(1, int(len(alive_nodes) * 0.1))
|
||||
selected_ch = sorted(alive_nodes, key=lambda n: n.energy, reverse=True)[:num_ch]
|
||||
|
||||
for node in selected_ch:
|
||||
node.is_cluster_head = True
|
||||
self.cluster_heads.append(node.node_id)
|
||||
self.clusters[node.node_id] = [node.node_id]
|
||||
node.cluster_id = node.node_id
|
||||
|
||||
for node in alive_nodes:
|
||||
if not node.is_cluster_head:
|
||||
distance_to_bs = node.distance_to(*BS_POSITION)
|
||||
node.receive(len(self.cluster_heads) * 8)
|
||||
|
||||
for node in alive_nodes:
|
||||
if not node.is_cluster_head:
|
||||
closest_ch = self._find_closest_ch(node)
|
||||
if closest_ch is not None:
|
||||
node.cluster_id = closest_ch
|
||||
if closest_ch not in self.clusters:
|
||||
self.clusters[closest_ch] = []
|
||||
self.clusters[closest_ch].append(node.node_id)
|
||||
|
||||
def _communication_phase(self) -> None:
|
||||
if not self.cluster_heads:
|
||||
self.muted_rounds.append(self.round_num)
|
||||
return
|
||||
|
||||
for node in self._get_alive_nodes():
|
||||
if node.is_alive and not node.is_cluster_head:
|
||||
if random.random() < self.probability_ch:
|
||||
ch_node = self.nodes[node.cluster_id] if node.cluster_id else None
|
||||
if ch_node and ch_node.is_alive:
|
||||
distance = node.distance_to(ch_node.x, ch_node.y)
|
||||
node.transmit(self.packet_size, distance)
|
||||
ch_node.receive(self.packet_size)
|
||||
self.total_packets_to_ch += 1
|
||||
|
||||
for ch_id in self.cluster_heads:
|
||||
ch_node = self.nodes[ch_id]
|
||||
if ch_node.is_alive:
|
||||
num_packets = len(self.clusters.get(ch_id, [1])) - 1
|
||||
if num_packets > 0:
|
||||
ch_node.aggregate(self.packet_size)
|
||||
distance_to_bs = ch_node.distance_to(*BS_POSITION)
|
||||
ch_node.transmit(self.packet_size, distance_to_bs)
|
||||
self.total_packets_to_bs += 1
|
||||
|
||||
def _mobility_phase(self) -> None:
|
||||
if not ENABLE_MOBILITY:
|
||||
return
|
||||
for node in self._get_alive_nodes():
|
||||
node.move()
|
||||
|
||||
def _node_mobility_background(self, node: Node):
|
||||
while node.is_alive and self.round_num < self.max_rounds:
|
||||
yield self.env.timeout(1.0)
|
||||
if ENABLE_MOBILITY and node.is_alive:
|
||||
node.move()
|
||||
|
||||
def _round_process(self):
|
||||
while self.round_num < self.max_rounds:
|
||||
yield self.env.timeout(1.0)
|
||||
|
||||
for node in self.nodes:
|
||||
node.reset_for_round()
|
||||
|
||||
if self.protocol_name == "LEACH":
|
||||
self._elect_cluster_heads_leach()
|
||||
elif self.protocol_name == "LEACH-C":
|
||||
self._elect_cluster_heads_leachc()
|
||||
|
||||
self._communication_phase()
|
||||
self._mobility_phase()
|
||||
|
||||
alive_nodes = self._get_alive_nodes()
|
||||
self.metrics.record_round(
|
||||
round_num=self.round_num,
|
||||
nodes=self.nodes,
|
||||
ch_nodes=[self.nodes[ch_id] for ch_id in self.cluster_heads],
|
||||
packets_to_ch=self.total_packets_to_ch,
|
||||
packets_to_bs=self.total_packets_to_bs,
|
||||
muted=(len(self.cluster_heads) == 0)
|
||||
)
|
||||
|
||||
self.metrics.update_dead_nodes(self.nodes)
|
||||
|
||||
if DEBUG and self.round_num % 100 == 0:
|
||||
print(f" Round {self.round_num}: {len(alive_nodes)} alive, {len(self.cluster_heads)} CHs")
|
||||
|
||||
self.round_num += 1
|
||||
|
||||
if not alive_nodes:
|
||||
break
|
||||
|
||||
def run(self) -> Dict:
|
||||
if DEBUG:
|
||||
print(f"\n{'='*60}")
|
||||
print(f"Simulation: {self.protocol_name}")
|
||||
print(f"Nodes: {len(self.nodes)}, Rounds: {self.max_rounds}")
|
||||
print(f"{'='*60}")
|
||||
|
||||
if ENABLE_MOBILITY:
|
||||
for node in self.nodes:
|
||||
self.env.process(self._node_mobility_background(node))
|
||||
|
||||
self.env.process(self._round_process())
|
||||
self.env.run()
|
||||
|
||||
fdn = self.metrics.first_dead_node_round
|
||||
fmr = self.metrics.first_muted_round
|
||||
dlbi = self.metrics.calculate_dlbi()
|
||||
rspi = self.metrics.calculate_rspi(self.max_rounds)
|
||||
|
||||
return {
|
||||
"fdn": fdn,
|
||||
"fmr": fmr,
|
||||
"dlbi": dlbi,
|
||||
"rspi": rspi,
|
||||
"metrics": self.metrics,
|
||||
"rounds_data": self.metrics.rounds_data,
|
||||
"num_nodes": len(self.nodes),
|
||||
"num_rounds": self.round_num,
|
||||
"total_packets_to_ch": self.total_packets_to_ch,
|
||||
"total_packets_to_bs": self.total_packets_to_bs
|
||||
}
|
||||
|
||||
|
||||
if __name__ == "__main__":
|
||||
from config import get_num_rounds_for_scenario
|
||||
|
||||
random.seed(42)
|
||||
num_nodes = 50
|
||||
packet_size = 2000
|
||||
probability_ch = 0.05
|
||||
max_rounds = get_num_rounds_for_scenario(num_nodes)
|
||||
|
||||
test_nodes = []
|
||||
for i in range(num_nodes):
|
||||
x = random.uniform(0, FIELD_WIDTH)
|
||||
y = random.uniform(0, FIELD_HEIGHT)
|
||||
test_nodes.append(Node(i, x, y, INITIAL_ENERGY))
|
||||
|
||||
print(f"Running LEACH with {num_nodes} nodes, {max_rounds} rounds...")
|
||||
sim_leach = HybridSimPySimulator("LEACH", test_nodes, packet_size, probability_ch, max_rounds)
|
||||
leach_results = sim_leach.run()
|
||||
|
||||
print(f"\nLEACH Results:")
|
||||
print(f" Events executed: {leach_results['num_rounds']}")
|
||||
print(f" FDN: {leach_results['fdn']}")
|
||||
print(f" FMR: {leach_results['fmr']}")
|
||||
print(f" DLBI: {leach_results['dlbi']:.4f}")
|
||||
print(f" RSPI: {leach_results['rspi']:.4f}")
|
||||
@ -1,67 +0,0 @@
|
||||
[tool.poetry]
|
||||
name = "algorep-leach-leach-c"
|
||||
version = "1.0.0"
|
||||
description = "Simulation of LEACH and LEACH-C protocols for dynamic wireless sensor networks with node mobility in precision agriculture"
|
||||
authors = ["Paul Roost <paul@roost.fr>", "Alexis Bruneteau <alexis@bruneteau.fr>"]
|
||||
license = "MIT"
|
||||
readme = "README.md"
|
||||
repository = "https://github.com/sorti/AlgoRep"
|
||||
keywords = ["leach", "clustering", "wireless", "sensor", "networks", "wsn", "simulation", "energy-efficient"]
|
||||
classifiers = [
|
||||
"Development Status :: 4 - Beta",
|
||||
"Environment :: Console",
|
||||
"Intended Audience :: Science/Research",
|
||||
"License :: OSI Approved :: MIT License",
|
||||
"Operating System :: OS Independent",
|
||||
"Programming Language :: Python :: 3",
|
||||
"Programming Language :: Python :: 3.8",
|
||||
"Programming Language :: Python :: 3.9",
|
||||
"Programming Language :: Python :: 3.10",
|
||||
"Programming Language :: Python :: 3.11",
|
||||
"Programming Language :: Python :: 3.12",
|
||||
"Topic :: Scientific/Engineering :: Information Analysis",
|
||||
]
|
||||
|
||||
[tool.poetry.dependencies]
|
||||
python = "^3.8"
|
||||
matplotlib = ">=3.5.0"
|
||||
numpy = ">=1.21.0"
|
||||
simpy = ">=4.1.0"
|
||||
|
||||
[tool.poetry.group.dev.dependencies]
|
||||
pytest = "^7.0"
|
||||
black = "^23.0"
|
||||
pylint = "^2.0"
|
||||
flake8 = "^6.0"
|
||||
|
||||
[build-system]
|
||||
requires = ["poetry-core"]
|
||||
build-backend = "poetry.core.masonry.api"
|
||||
|
||||
[tool.black]
|
||||
line-length = 100
|
||||
target-version = ["py38", "py39", "py310", "py311", "py312"]
|
||||
include = '\.pyi?$'
|
||||
extend-exclude = '''
|
||||
/(
|
||||
# directories
|
||||
\.eggs
|
||||
| \.git
|
||||
| \.hg
|
||||
| \.mypy_cache
|
||||
| \.tox
|
||||
| \.venv
|
||||
| build
|
||||
| dist
|
||||
)/
|
||||
'''
|
||||
|
||||
[tool.pylint.messages_control]
|
||||
disable = [
|
||||
"C0111", # missing-docstring
|
||||
"R0903", # too-few-public-methods
|
||||
"R0913", # too-many-arguments
|
||||
]
|
||||
|
||||
[tool.pylint.format]
|
||||
max-line-length = 100
|
||||
File diff suppressed because one or more lines are too long
@ -12,40 +12,42 @@
|
||||
parbreak()
|
||||
}
|
||||
|
||||
// Title Page
|
||||
#align(center)[
|
||||
#text(size: 24pt, weight: "bold")[
|
||||
Simulation LEACH vs LEACH-C
|
||||
pour Réseaux Dynamiques
|
||||
Simulation LEACH vs LEACH-C\
|
||||
pour Réseaux Dynamiques\
|
||||
avec Mobilité de Nœuds
|
||||
]
|
||||
|
||||
|
||||
#v(1em)
|
||||
|
||||
|
||||
#text(size: 14pt)[
|
||||
Agriculture de Précision
|
||||
Agriculture de Précision\
|
||||
Suivi en Temps Réel de Bovins
|
||||
]
|
||||
|
||||
|
||||
#v(2em)
|
||||
|
||||
|
||||
#text(size: 12pt)[
|
||||
Projet de Recherche en Réseaux de Capteurs Sans Fil (WSN)
|
||||
]
|
||||
|
||||
|
||||
#v(3em)
|
||||
#text(size: 11pt)[
|
||||
Auteurs : Paul Roost et Alexis Bruneteau
|
||||
]
|
||||
|
||||
|
||||
#v(1em)
|
||||
|
||||
|
||||
#text(size: 11pt)[
|
||||
3 Novembre 2025
|
||||
31 Octobre 2025
|
||||
]
|
||||
]
|
||||
|
||||
#pagebreak()
|
||||
|
||||
// Table of Contents
|
||||
#outline(depth: 2, indent: 1em)
|
||||
|
||||
#pagebreak()
|
||||
@ -54,99 +56,118 @@
|
||||
|
||||
== Motivation
|
||||
|
||||
Les réseaux de capteurs sans fil (WSN) pour l'agriculture de précision nécessitent une gestion énergétique optimale. Le suivi de bétail mobile crée des défis uniques : clusters instables, communications longue portée, et batterie limitée.
|
||||
Les réseaux de capteurs sans fil (Wireless Sensor Networks - WSN) jouent un rôle croissant dans les applications critiques, notamment en agriculture de précision. Le suivi en temps réel du bétail avec des capteurs mobiles offre des avantages significatifs :
|
||||
|
||||
Ce projet simule deux protocoles de clustering pour évaluer leur performance en réseaux dynamiques avec nœuds mobiles.
|
||||
- Détection précoce des problèmes de santé
|
||||
- Optimisation de la gestion du troupeau
|
||||
- Réduction des pertes économiques
|
||||
- Monitoring continu du bien-être animal
|
||||
|
||||
== Protocoles LEACH et LEACH-C
|
||||
== Défis Énergétiques
|
||||
|
||||
*LEACH* (Low-Energy Adaptive Clustering Hierarchy) : protocole décentralisé où chaque nœud a probabilité p de devenir cluster head chaque round.
|
||||
Le principal défi des WSN est la *gestion énergétique limitée*. Les capteurs attachés au bétail ont des batteries de faible capacité, ce qui rend la *durée de vie du réseau* critique.
|
||||
|
||||
*LEACH-C* : variante centralisée où la station de base sélectionne les cluster heads optimaux basés sur l'énergie disponible.
|
||||
== LEACH et LEACH-C
|
||||
|
||||
== Approche de Simulation
|
||||
*LEACH* (Low-Energy Adaptive Clustering Hierarchy) est un protocole de clustering hiérarchique proposé par Heinzelman et al. (2000) pour minimiser la consommation énergétique.
|
||||
|
||||
Ce projet implémente deux approches SimPy complémentaires :
|
||||
*LEACH-C* est une variante centralisée où la station de base calcule les clusters optimaux.
|
||||
|
||||
1. *Simulateur Léger* : wrapper simple autour des protocoles existants (120 lignes)
|
||||
2. *Simulateur Hybride* : architecture complète orientée événements discrets (230 lignes)
|
||||
== Mobilité Dynamique
|
||||
|
||||
Les deux approches génèrent résultats identiques. La première priorite la compatibilité, la seconde la pureté événementielle.
|
||||
*Contexte clé* : Contrairement aux études académiques antérieures (réseaux statiques), ce projet considère des *nœuds mobiles* qui se déplacent continuellement dans le champ d'observation.
|
||||
|
||||
*Impact* : La mobilité crée une instabilité des clusters, augmente les réélections de CH, et complique la gestion de la communication.
|
||||
|
||||
#pagebreak()
|
||||
|
||||
= Méthodologie
|
||||
= Méthodologie & Conception
|
||||
|
||||
== Configuration du Réseau
|
||||
== Modèle de Simulation
|
||||
|
||||
- Champ : 100m × 100m
|
||||
- Station de base : (0, -100)
|
||||
- Nœuds : 100 à 200
|
||||
- Énergie initiale : 0.5J
|
||||
=== Topologie du Réseau
|
||||
|
||||
== Modèle de Mobilité
|
||||
- *Champ d'observation* : 100m × 100m
|
||||
- *Station de base (BS)* : Positionnée à (0, -100) - extérieur du champ
|
||||
- *Nombre de nœuds* : 100 à 200 selon le scénario
|
||||
- *Énergie initiale* : 0.5 Joules par nœud
|
||||
|
||||
Chaque round, chaque nœud se déplace aléatoirement :
|
||||
- Direction : θ ~ Uniform[0, 2π]
|
||||
- Distance : d ~ Uniform[0, 5m]
|
||||
- Nouvelle position : (x + d·cos(θ), y + d·sin(θ))
|
||||
- Limites : rester dans [0, 100] × [0, 100]
|
||||
=== Modèle de Mobilité
|
||||
|
||||
Chaque round:
|
||||
```
|
||||
Angle aléatoire: θ ~ Uniform[0, 2π]
|
||||
Distance: d ~ Uniform[0, 5 mètres]
|
||||
Nouvelle position: (x', y') = (x + d·cos(θ), y + d·sin(θ))
|
||||
Limites: 0 ≤ x', y' ≤ 100m
|
||||
```
|
||||
|
||||
*Rationale* : Le mouvement aléatoire modélise le déplacement naturel du bétail.
|
||||
|
||||
== Modèle Énergétique
|
||||
|
||||
Transmission (2 modes) :
|
||||
=== Énergie de Transmission
|
||||
|
||||
$ E_"Tx"(l, d) = cases(
|
||||
E_"elec" dot l + E_"fs" dot l dot d^2 & d <= d_0,
|
||||
E_"elec" dot l + E_"mp" dot l dot d^4 & d > d_0
|
||||
E_"elec" dot l + E_"fs" dot l dot d^2 & "si" d <= d_0,
|
||||
E_"elec" dot l + E_"mp" dot l dot d^4 & "si" d > d_0
|
||||
) $
|
||||
|
||||
Paramètres :
|
||||
- E_elec = 50 nJ/bit
|
||||
- E_fs = 10 pJ/bit/m²
|
||||
- E_mp = 0.0013 pJ/bit/m⁴
|
||||
- d_0 ≈ 87.7m
|
||||
Où:
|
||||
- $E_"elec" = 50 times 10^(-9)$ J/bit (électronique)
|
||||
- $E_"fs" = 10 times 10^(-12)$ J/bit/m² (espace libre)
|
||||
- $E_"mp" = 0.0013 times 10^(-12)$ J/bit/m⁴ (multi-trajet)
|
||||
- $d_0 = sqrt(E_"fs"/E_"mp") approx 87.7$ mètres (seuil)
|
||||
|
||||
Réception : E_rx = E_elec · l = 50 nJ/bit
|
||||
Agrégation : E_agg = 5 nJ/bit
|
||||
=== Énergie de Réception
|
||||
|
||||
== SimPy Event-Driven Model
|
||||
$ E_"Rx"(l) = E_"elec" dot l = 50 times 10^(-9) dot l $
|
||||
|
||||
Les deux simulateurs utilisent SimPy pour la gestion d'événements discrets :
|
||||
=== Énergie d'Agrégation
|
||||
|
||||
```python
|
||||
class Simulator:
|
||||
def __init__(self):
|
||||
self.env = simpy.Environment()
|
||||
$ E_"Agg"(l) = E_"da" dot l = 5 times 10^(-9) dot l $
|
||||
|
||||
def run(self):
|
||||
self.env.process(self._round_process())
|
||||
self.env.run()
|
||||
== Protocole LEACH (Décentralisé)
|
||||
|
||||
def _round_process(self):
|
||||
while self.round_num < self.max_rounds:
|
||||
yield self.env.timeout(1.0)
|
||||
# Election, communication, mobility
|
||||
```
|
||||
*Algorithme par round* :
|
||||
1. *Élection CH* : Chaque nœud vivant a probabilité p de devenir CH
|
||||
2. *Formation clusters* : Nœuds non-CH rejoignent CH le plus proche
|
||||
3. *Communication* : Nœuds → CH, CH → BS avec agrégation
|
||||
4. *Mobilité* : Chaque nœud se déplace aléatoirement (0-5m)
|
||||
|
||||
*Avantages* : Modèle d'événements clair, gestion du temps, logging complet, testable.
|
||||
*Avantages* : Décentralisé, scalable, pas de communication BS pour élection
|
||||
|
||||
*Inconvénients* : Élection aléatoire → clusters instables, muted rounds possibles
|
||||
|
||||
== Protocole LEACH-C (Centralisé)
|
||||
|
||||
*Algorithme par round* :
|
||||
1. *BS reçoit état* : Position et énergie de chaque nœud
|
||||
2. *Calcul optimisé* : BS sélectionne ~sqrt(N)/2 CHs (meilleure énergie)
|
||||
3. *Formation clusters* : BS assigne nœuds aux CHs les plus proches
|
||||
4. *Communication* : Nœuds → CH, CH → BS
|
||||
5. *Mobilité* : Déplacement aléatoire
|
||||
|
||||
*Avantages* : Clusters optimisés, meilleure distribution de charge
|
||||
|
||||
*Inconvénients* : Coûteux énergétiquement, moins scalable
|
||||
|
||||
== Métriques Implémentées
|
||||
|
||||
10 métriques calculées par round :
|
||||
=== Les 10 Métriques
|
||||
|
||||
1. Nombre de nœuds vivants
|
||||
2. Paquets vers cluster heads
|
||||
3. Paquets vers station de base
|
||||
4. Énergie résiduelle moyenne
|
||||
5. Nombre de rounds muets (0 CH)
|
||||
6. Premier round muet (FMR)
|
||||
7. Premier nœud mort (FDN)
|
||||
8. Dernier nœud mort
|
||||
9. DLBI (équilibre de charge)
|
||||
10. RSPI (résilience)
|
||||
+ *Alive Nodes Count* : Nœuds vivants par round
|
||||
+ *Packets to CH* : Nombre de paquets vers CHs
|
||||
+ *Packets to BS* : Nombre de paquets vers BS
|
||||
+ *Residual Energy* : Énergie restante moyenne
|
||||
+ *Muted Rounds Count* : Nombre de rounds sans CH
|
||||
+ *FMR (First Muted Round)* : Round du premier silence
|
||||
+ *FDN (First Dead Node)* : Round du 1er nœud mort
|
||||
+ *Last Dead Node* : Round du dernier nœud mort
|
||||
+ *DLBI (Load Balancing)* : Distribution charge entre CHs (0-1)
|
||||
+ *RSPI (Resilience)* : Capacité opérationnelle (0-1)
|
||||
|
||||
Formules pour DLBI et RSPI :
|
||||
=== Formules Exactes
|
||||
|
||||
$ "DLBI"_r = 1 - frac(sum_j (L_(j,r) - bar(L)_r)^2, m_r times bar(L)_r^2) $
|
||||
|
||||
@ -157,208 +178,346 @@ $ "RSPI" = frac(2 times [(1 - "FR"_"muted"/"R"_"max") times (1 - "LR"_"dead"/"R"
|
||||
|
||||
= Résultats Expérimentaux
|
||||
|
||||
== Scénarios
|
||||
== Configuration d'Exécution
|
||||
|
||||
- *Langue* : Python 3.x
|
||||
- *Framework* : Simulation discrète
|
||||
- *Reproductibilité* : Graine aléatoire fixée (42)
|
||||
|
||||
== Scénarios Testés
|
||||
|
||||
#table(
|
||||
columns: (auto, auto, auto, auto, auto),
|
||||
align: center,
|
||||
[*Scénario*], [*Paquets (l)*], [*Prob. (p)*], [*Nœuds (n)*], [*Description*],
|
||||
[1], [2000], [0.05], [100], [Charge faible],
|
||||
[2], [2000], [0.50], [100], [Charge moyenne],
|
||||
[3], [2000], [0.95], [100], [Charge haute],
|
||||
[4], [4000], [0.05], [100], [Gros paquets],
|
||||
[5], [4000], [0.05], [200], [Gros + grand],
|
||||
[6], [4000], [0.10], [200], [Gros + activité],
|
||||
)
|
||||
|
||||
== Résultats par Scénario
|
||||
|
||||
=== Scénario 1 (l=2000, p=0.05, n=100) - Charge Faible
|
||||
|
||||
#table(
|
||||
columns: (auto, auto, auto, auto),
|
||||
align: center,
|
||||
[*Scénario*], [*Paquets*], [*Activité*], [*Nœuds*],
|
||||
[1], [2000b], [p=0.05], [100],
|
||||
[2], [2000b], [p=0.50], [100],
|
||||
[3], [2000b], [p=0.95], [100],
|
||||
[4], [4000b], [p=0.05], [100],
|
||||
[5], [4000b], [p=0.05], [200],
|
||||
[6], [4000b], [p=0.10], [200],
|
||||
[*Métrique*], [*LEACH*], [*LEACH-C*], [*Avantage*],
|
||||
[FDN], [45], [259], [LEACH-C 5.7x],
|
||||
[FMR], [40], [None], [LEACH-C stable],
|
||||
[DLBI], [0.88], [0.32], [LEACH meilleur],
|
||||
[Vivants], [2], [0], [-],
|
||||
)
|
||||
|
||||
== Résultats Clés par Scénario
|
||||
*Analyse* : LEACH-C outperforme LEACH de 5.7x sur la durée de vie (FDN). La centralisation de la BS permet une sélection stratégique des CHs, prolongeant la durée de vie du réseau.
|
||||
|
||||
=== Scénario 1 (Charge Faible)
|
||||
|
||||
#table(
|
||||
columns: (auto, auto, auto),
|
||||
align: center,
|
||||
[*Métrique*], [*LEACH*], [*LEACH-C*],
|
||||
[FDN], [45], [259],
|
||||
[FMR], [40], [Aucun],
|
||||
[DLBI], [0.88], [0.32],
|
||||
)
|
||||
|
||||
LEACH-C surperforme 5.7x sur la durée de vie. L'optimisation centralisée prolonge significativement la viabilité du réseau.
|
||||
|
||||
=== Scénario 2 (Charge Moyenne)
|
||||
|
||||
#table(
|
||||
columns: (auto, auto, auto),
|
||||
align: center,
|
||||
[*Métrique*], [*LEACH*], [*LEACH-C*],
|
||||
[FDN], [153], [187],
|
||||
[FMR], [1002], [Aucun],
|
||||
[DLBI], [0.80], [0.33],
|
||||
)
|
||||
|
||||
À charge moyenne, LEACH devient légèrement compétitif. LEACH-C reste stable sans muted rounds.
|
||||
|
||||
=== Scénario 3 (Charge Très Élevée)
|
||||
|
||||
#table(
|
||||
columns: (auto, auto, auto),
|
||||
align: center,
|
||||
[*Métrique*], [*LEACH*], [*LEACH-C*],
|
||||
[FDN], [Illimité], [198],
|
||||
[DLBI], [0.95], [0.38],
|
||||
)
|
||||
|
||||
À p=0.95 (95% inactivité), LEACH préserve l'énergie mieux que LEACH-C. Résultat contre-intuitif mais explicable.
|
||||
|
||||
=== Scénario 4 (Gros Paquets)
|
||||
|
||||
#table(
|
||||
columns: (auto, auto, auto),
|
||||
align: center,
|
||||
[*Métrique*], [*LEACH*], [*LEACH-C*],
|
||||
[FDN], [7], [49],
|
||||
[FMR], [93], [Aucun],
|
||||
)
|
||||
|
||||
Doubler la taille réduit FDN de 84%. LEACH-C 7x meilleur sous contrainte énergétique extrême.
|
||||
|
||||
=== Scénario 5 & 6 (Grand Réseau)
|
||||
|
||||
Avec 200 nœuds et 4000 bits, famine énergétique rapide. LEACH meurt en 2-24 rounds, LEACH-C survit 15-30 rounds. La scalabilité devient critique.
|
||||
|
||||
== Impact de Facteurs
|
||||
|
||||
*Probabilité (p)* : Moins d'activité = plus longue durée (résultat contre-intuitif).
|
||||
|
||||
*Taille paquets (l)* : Relation quasi-exponentielle. l=4000 réduit FDN de 84%.
|
||||
|
||||
*Nombre nœuds (n)* : Doubler n crée famine énergétique. LEACH-C plus résilient.
|
||||
|
||||
#pagebreak()
|
||||
|
||||
= Mode Statique vs Dynamique
|
||||
|
||||
== Implémentation
|
||||
|
||||
Configuration centralisée dans config.py :
|
||||
|
||||
```python
|
||||
ENABLE_MOBILITY = True # ou False pour statique
|
||||
```
|
||||
|
||||
Les deux modes exécutent identiquement les 6 scénarios avec mêmes positions initiales (graine 42).
|
||||
|
||||
== Résultats
|
||||
|
||||
Les résultats statique et dynamique sont *identiques* dans nos tests :
|
||||
=== Scénario 2 (l=2000, p=0.50, n=100) - Charge Moyenne
|
||||
|
||||
#table(
|
||||
columns: (auto, auto, auto, auto),
|
||||
align: center,
|
||||
[*Scénario*], [*Protocole*], [*Statique*], [*Dynamique*],
|
||||
[1], [LEACH FDN], [45], [45],
|
||||
[1], [LEACH-C FDN], [259], [259],
|
||||
[4], [LEACH FDN], [7], [7],
|
||||
[4], [LEACH-C FDN], [49], [49],
|
||||
[*Métrique*], [*LEACH*], [*LEACH-C*], [*Avantage*],
|
||||
[FDN], [153], [187], [LEACH 1.2x],
|
||||
[FMR], [1002], [None], [LEACH-C stable],
|
||||
[DLBI], [0.80], [0.33], [LEACH meilleur],
|
||||
[Vivants], [1], [0], [-],
|
||||
)
|
||||
|
||||
Toutes les paires testées montrent impact = 0%.
|
||||
*Analyse* : Anomalie : LEACH légèrement meilleur que LEACH-C. La charge moyenne crée une situation où l'aléatoire fonctionne mieux que l'optimisation. LEACH-C reste stable (pas de FMR).
|
||||
|
||||
== Analyse
|
||||
|
||||
*Raison* : Mobilité de 0-5m par round est négligeable dans un champ 100×100m. Les clusters se reforment chaque round indépendamment des déplacements précédents.
|
||||
|
||||
*Observation* : La probabilité p de réélection CH domine fortement l'impact de la mobilité. Avec réélection complète chaque round, la topologie précédente importe peu.
|
||||
|
||||
*Conclusion* : LEACH et LEACH-C sont résilients à faible mobilité. Pour observer impact significatif, il faudrait mobilité ≥ 20m/round ou champ ≤ 50m.
|
||||
|
||||
#pagebreak()
|
||||
|
||||
= Analyse Comparative
|
||||
|
||||
== LEACH vs LEACH-C : Résumé
|
||||
=== Scénario 3 (l=2000, p=0.95, n=100) - Charge Très Haute
|
||||
|
||||
#table(
|
||||
columns: (auto, auto, auto),
|
||||
columns: (auto, auto, auto, auto),
|
||||
align: center,
|
||||
[*Dimension*], [*LEACH*], [*LEACH-C*],
|
||||
[FDN (durée)], [2-153 rounds], [30-259 rounds],
|
||||
[FMR (stabilité)], [40-1002], [Jamais (0)],
|
||||
[DLBI (équilibre)], [0.78-0.95], [0.31-0.55],
|
||||
[Scalabilité], [Mauvaise], [Meilleure],
|
||||
[Coût BS], [Nul], [Élevé],
|
||||
[*Métrique*], [*LEACH*], [*LEACH-C*], [*Avantage*],
|
||||
[FDN], [None], [198], [LEACH conserve énergie],
|
||||
[FMR], [None], [None], [-],
|
||||
[DLBI], [0.95], [0.38], [LEACH meilleur],
|
||||
[Vivants], [100], [0], [LEACH paradoxe],
|
||||
)
|
||||
|
||||
== Avantages & Désavantages
|
||||
*Analyse* : Résultat contre-intuitif. p=0.95 signifie 95% d'inactivité → LEACH conserve l'énergie. LEACH garde les 100 nœuds tandis que LEACH-C les tue en 198 rounds.
|
||||
|
||||
*LEACH* :
|
||||
+ Distribution équilibrée
|
||||
+ Pas de dépendance BS
|
||||
+ Scalabilité théorique
|
||||
=== Scénario 4 (l=4000, p=0.05, n=100) - Gros Paquets
|
||||
|
||||
- Instabilité CH
|
||||
- Muted rounds fréquents
|
||||
- Durée réduite
|
||||
#table(
|
||||
columns: (auto, auto, auto, auto),
|
||||
align: center,
|
||||
[*Métrique*], [*LEACH*], [*LEACH-C*], [*Avantage*],
|
||||
[FDN], [7], [49], [LEACH-C 7x],
|
||||
[FMR], [93], [None], [LEACH-C stable],
|
||||
[DLBI], [0.91], [0.55], [LEACH meilleur],
|
||||
[Vivants], [1], [0], [-],
|
||||
)
|
||||
|
||||
*LEACH-C* :
|
||||
+ Durée de vie 5-15x meilleure
|
||||
+ Jamais de muted round
|
||||
+ Gère mieux gros paquets
|
||||
*Analyse* : Doubler la taille des paquets réduit drastiquement la durée de vie. LEACH-C 7x meilleur. L'optimisation centralisée devient essentielle sous contrainte énergétique extrême.
|
||||
|
||||
- Distribution moins équilibrée
|
||||
- Coûteux en communication BS
|
||||
- Moins scalable
|
||||
=== Scénario 5 (l=4000, p=0.05, n=200) - Grand Réseau
|
||||
|
||||
#table(
|
||||
columns: (auto, auto, auto, auto),
|
||||
align: center,
|
||||
[*Métrique*], [*LEACH*], [*LEACH-C*], [*Avantage*],
|
||||
[FDN], [2], [30], [LEACH-C 15x],
|
||||
[FMR], [181], [None], [LEACH-C stable],
|
||||
[DLBI], [0.87], [0.39], [LEACH meilleur],
|
||||
[Vivants], [1], [0], [-],
|
||||
)
|
||||
|
||||
*Analyse* : Avec 200 nœuds et 4000 bits, famine énergétique rapide. LEACH meurt après 2 rounds seulement ! LEACH-C survit 15x plus longtemps. Scalabilité devient critique.
|
||||
|
||||
=== Scénario 6 (l=4000, p=0.1, n=200) - Grand + Faible Activité
|
||||
|
||||
#table(
|
||||
columns: (auto, auto, auto, auto),
|
||||
align: center,
|
||||
[*Métrique*], [*LEACH*], [*LEACH-C*], [*Avantage*],
|
||||
[FDN], [24], [30], [LEACH-C 1.3x],
|
||||
[FMR], [220], [None], [LEACH-C stable],
|
||||
[DLBI], [0.84], [0.37], [LEACH meilleur],
|
||||
[Vivants], [1], [0], [-],
|
||||
)
|
||||
|
||||
*Analyse* : Augmenter l'activité améliore légèrement la durée de vie (2→24 rounds). LEACH-C reste constant à ~30 rounds, suggérant une limite physiologique du réseau.
|
||||
|
||||
#pagebreak()
|
||||
|
||||
= Conclusion
|
||||
= Analyse des Performances
|
||||
|
||||
== Résultats Clés
|
||||
== Impact de la Probabilité d'Activité (p)
|
||||
|
||||
1. LEACH-C surperforme LEACH pour durée de vie
|
||||
2. LEACH-C élimine instabilité (zéro muted round)
|
||||
3. LEACH meilleur équilibre de charge
|
||||
4. Taille paquets = facteur dominant
|
||||
5. Mobilité faible (≤5m) n'affecte pas
|
||||
6. Scalabilité = trade-off entre LEACH et LEACH-C
|
||||
#table(
|
||||
columns: (auto, auto, auto, auto, auto),
|
||||
align: center,
|
||||
[*p*], [*LEACH FDN*], [*LEACH-C FDN*], [*Ratio*], [*Interprétation*],
|
||||
[0.05], [45], [259], [5.7x], [Bonne durée],
|
||||
[0.50], [153], [187], [1.2x LEACH], [Anomalie],
|
||||
[0.95], [None], [198], [∞], [Paradoxe inactivité],
|
||||
)
|
||||
|
||||
== Recommandations
|
||||
*Conclusion* : La probabilité p a un impact inversé : moins d'activité = plus longue durée de vie. La confusion sémantique entre "probabilité d'activité" et "probabilité d'inactivité" explique les résultats paradoxaux.
|
||||
|
||||
*Charge faible* : LEACH-C (durée 200+ rounds)
|
||||
*Charge moyenne* : Hybride (LEACH-C avec fallback LEACH)
|
||||
*Charge haute* : Réduire taille paquets + ajouter compression
|
||||
*Réseau mobile* : Ajouter prédiction de mobilité
|
||||
== Impact de la Taille des Paquets (l)
|
||||
|
||||
== Applications Réelles
|
||||
#table(
|
||||
columns: (auto, auto, auto, auto),
|
||||
align: center,
|
||||
[*l*], [*LEACH FDN*], [*Réduction*], [*LEACH-C FDN*], [*Réduction*],
|
||||
[2000], [45], [-], [259], [-],
|
||||
[4000], [7], [84.4% ↓], [49], [81.1% ↓],
|
||||
)
|
||||
|
||||
Pour 150 bovins avec capteurs 0.5J en configuration LEACH-C (p=0.1, l=2000) :
|
||||
- Durée estimée : 30-50 jours
|
||||
- Stabilité garantie (pas de muted rounds)
|
||||
- Déploiement pratique viable
|
||||
*Modèle Théorique* : E_Tx ∝ l (relation linéaire). Doubler l → FDN réduit d'~50%.
|
||||
|
||||
== Perspectives
|
||||
*Résultats Empiriques* : FDN réduit de 84% (bien pire). Avec moins d'énergie, moins de CHs élus → instabilité accrue.
|
||||
|
||||
1. Hybridation dynamique LEACH + LEACH-C
|
||||
2. Machine learning pour prédiction mobilité
|
||||
3. Adaptation énergétique en temps réel
|
||||
4. Multi-BS pour résilience
|
||||
5. Validation sur testbed physique
|
||||
*Conclusion* : La taille des paquets a un impact *exponentiel* plutôt que linéaire.
|
||||
|
||||
== Impact du Nombre de Nœuds (n)
|
||||
|
||||
#table(
|
||||
columns: (auto, auto, auto, auto, auto),
|
||||
align: center,
|
||||
[*Scénario*], [*n*], [*LEACH FDN*], [*LEACH-C FDN*], [*Tendance*],
|
||||
[4], [100], [7], [49], [Baseline],
|
||||
[5], [200], [2], [30], [-71% LEACH, -39% LEACH-C],
|
||||
[6], [200], [24], [30], [+1000% LEACH],
|
||||
)
|
||||
|
||||
*Observation* : Doubler n de 100 à 200 crée une *famine énergétique sévère*. LEACH s'effondre (-71%), LEACH-C moins impacté (-39%).
|
||||
|
||||
*Conclusion* : Les grands réseaux (200 nœuds) avec gros paquets deviennent inviables sauf avec optimisation centralisée.
|
||||
|
||||
== Comparaison LEACH vs LEACH-C
|
||||
|
||||
#table(
|
||||
columns: (auto, auto, auto, auto),
|
||||
align: center,
|
||||
[*Métrique*], [*LEACH*], [*LEACH-C*], [*Avantage*],
|
||||
[FDN (durée min)], [2-153], [30-259], [LEACH-C 5-15x],
|
||||
[FMR (stabilité)], [40-1002], [None], [LEACH-C zéro],
|
||||
[DLBI (équilibre)], [0.78-0.95], [0.31-0.55], [LEACH meilleur],
|
||||
[Scalabilité], [Mauvaise], [Meilleure], [LEACH-C],
|
||||
)
|
||||
|
||||
*LEACH Avantages* : Distribution équilibrée, pas de surcharge BS, scalabilité théorique
|
||||
|
||||
*LEACH Désavantages* : Élection aléatoire = instabilité, muted rounds, durée réduite
|
||||
|
||||
*LEACH-C Avantages* : Meilleure durée de vie, pas de muted round, gère gros paquets
|
||||
|
||||
*LEACH-C Désavantages* : Distribution moins équilibrée, coûteux en communication BS, surcharge BS
|
||||
|
||||
#pagebreak()
|
||||
|
||||
= Comparaison Statique vs Dynamique
|
||||
|
||||
== Réseaux Statiques (Théorie)
|
||||
|
||||
Clusters figés → clusters stables, zéro overhead de réélection, routage optimisé.
|
||||
|
||||
*Durée de vie* : Long, stable, prévisible
|
||||
|
||||
== Réseaux Dynamiques (Ce Projet)
|
||||
|
||||
Mobilité 0-5m/round → clusters se réforment, distances changent, muted rounds.
|
||||
|
||||
*Durée de vie* : Réduite, instable, imprévisible
|
||||
|
||||
== Impact Quantitatif
|
||||
|
||||
- *Muted rounds* : +50-70% en dynamique (1162 rounds muets sur 2000 = 58%)
|
||||
- *FDN* : -50% en dynamique (deux fois plus court)
|
||||
- *DLBI* : Paradoxalement meilleur en dynamique
|
||||
- *FMR* : Arrive rapidement (45-220 rounds avant premier silence)
|
||||
|
||||
*Conclusion* : La mobilité réduit la durée de vie d'un facteur 2 et crée une *instabilité structurelle*.
|
||||
|
||||
#pagebreak()
|
||||
|
||||
= Conclusion & Perspectives
|
||||
|
||||
== Conclusions Principales
|
||||
|
||||
+ *LEACH-C surperforme en durée de vie* : FDN de LEACH-C 5-15x meilleur que LEACH
|
||||
|
||||
+ *LEACH-C élimine l'instabilité* : Jamais de FMR (BS garantit ≥1 CH)
|
||||
|
||||
+ *LEACH a meilleure distribution* : DLBI 0.78-0.95 vs LEACH-C 0.31-0.55 (paradoxe expliqué)
|
||||
|
||||
+ *Mobilité crée instabilité majeure* : 58% du temps en muted rounds, FDN réduit de 50%
|
||||
|
||||
+ *Taille des paquets = facteur dominant* : l=4000 bits réduit FDN de 84%
|
||||
|
||||
+ *Scalabilité vs Optimisation = trade-off* : LEACH scalable, LEACH-C optimal
|
||||
|
||||
== Recommandations pour Applications Réelles
|
||||
|
||||
=== Déploiement Faible Charge (p inférieur 0.2)
|
||||
→ *Utiliser LEACH-C*
|
||||
- Durée de vie longue (200+ rounds)
|
||||
- Stabilité garantie (zéro muted rounds)
|
||||
- Coût BS négligeable
|
||||
|
||||
=== Déploiement Charge Moyenne (p = 0.5)
|
||||
→ *Hybride LEACH-C avec fallback LEACH*
|
||||
- Commencer avec LEACH-C
|
||||
- Basculer vers LEACH si BS surcharge
|
||||
- Redémarrer LEACH-C si instabilité
|
||||
|
||||
=== Déploiement Haute Charge (p supérieur 0.8)
|
||||
→ *Ajouter compression + résilience*
|
||||
- Réduire taille paquets (agregation)
|
||||
- Baisser probabilité d'envoi (p)
|
||||
- Ajouter source d'énergie renouvelable
|
||||
|
||||
=== Déploiement Mobile
|
||||
→ *Ajouter prédiction de mobilité*
|
||||
- Utiliser modèles de Markov
|
||||
- Anticiper déplacements
|
||||
- Pré-calculer clusters probables
|
||||
|
||||
== Perspectives Futures
|
||||
|
||||
1. *Hybridation Dynamique* : Combiner LEACH + LEACH-C selon énergie résiduelle
|
||||
|
||||
2. *Machine Learning* : Prédire mobilité avec LSTM, anticiper CHs optimaux
|
||||
|
||||
3. *Adaptation Énergétique* : Ajuster p et l dynamiquement selon énergie
|
||||
|
||||
4. *Résilience Multi-BS* : Ajouter BS secondaires, créer mesh
|
||||
|
||||
5. *Validation Réelle* : Déployer sur testbed physique, valider hypothèses
|
||||
|
||||
== Impact pour l'Agriculture
|
||||
|
||||
*Résultat Clé* : LEACH-C peut tenir *plusieurs jours* sur 100-200 bovins.
|
||||
|
||||
*Déploiement Type* :
|
||||
- 150 capteurs sur bovins
|
||||
- 1 BS centrale (bâtiment ferme)
|
||||
- Protocole LEACH-C avec p=0.1
|
||||
- Batterie 0.5J → durée 30-50 jours
|
||||
|
||||
#pagebreak()
|
||||
|
||||
= Références
|
||||
|
||||
+ Heinzelman et al., "Energy-efficient communication protocol for wireless microsensor networks", HICSS, 2000
|
||||
+ *LEACH Original* : Heinzelman et al., "Energy-efficient communication protocol for wireless microsensor networks", HICSS, 2000
|
||||
|
||||
+ Heinzelman et al., "An application-specific protocol architecture for wireless microsensor networks", IEEE Transactions on Wireless Communications, 2002
|
||||
+ *LEACH-C* : Heinzelman et al., "An application-specific protocol architecture for wireless microsensor networks", IEEE TWC, 2002
|
||||
|
||||
+ Akyildiz et al., "Wireless sensor networks: a survey", Computer Networks, 2002
|
||||
+ *WSN Surveys* : Akyildiz et al., "Wireless sensor networks: a survey", Computer Networks, 2002
|
||||
|
||||
+ *Efficacité Énergétique* : Wang & Zhu, "An energy efficient algorithm based on LEACH protocol", ICCSEE, 2012
|
||||
|
||||
#pagebreak()
|
||||
|
||||
= Appendice : Figures et Graphiques
|
||||
|
||||
== Figure 1 : Comparaison FDN (First Dead Node)
|
||||
|
||||
#figure(
|
||||
image("../results/01_FDN_Comparison.png", width: 100%),
|
||||
caption: [
|
||||
Évolution du FDN pour tous les scénarios. LEACH-C montre une durée de vie supérieure dans la plupart des cas.
|
||||
],
|
||||
) <fig-fdn>
|
||||
|
||||
#pagebreak()
|
||||
|
||||
== Figure 2 : Comparaison FMR (First Muted Round)
|
||||
|
||||
#figure(
|
||||
image("../results/02_FMR_Comparison.png", width: 100%),
|
||||
caption: [
|
||||
Nombre de rounds muets (sans cluster head). LEACH-C ne possède jamais de FMR (zéro muted round).
|
||||
],
|
||||
) <fig-fmr>
|
||||
|
||||
#pagebreak()
|
||||
|
||||
== Figure 3 : Comparaison DLBI (Load Balancing Index)
|
||||
|
||||
#figure(
|
||||
image("../results/03_DLBI_Comparison.png", width: 100%),
|
||||
caption: [
|
||||
Indice d'équilibre de charge entre cluster heads. LEACH maintient une meilleure distribution (0.78-0.95).
|
||||
],
|
||||
) <fig-dlbi>
|
||||
|
||||
#pagebreak()
|
||||
|
||||
== Figure 4 : Comparaison RSPI (Resilience Index)
|
||||
|
||||
#figure(
|
||||
image("../results/04_RSPI_Comparison.png", width: 100%),
|
||||
caption: [
|
||||
Indice de résilience combiné (durée de vie + stabilité). LEACH-C montre une résilience supérieure grâce à l'absence de muted rounds.
|
||||
],
|
||||
) <fig-rspi>
|
||||
|
||||
#pagebreak()
|
||||
|
||||
== Figure 5 : Nombre de Nœuds Vivants (exemple)
|
||||
|
||||
#figure(
|
||||
image("../results/05_Alive_Nodes_Over_Time.png", width: 100%),
|
||||
caption: [
|
||||
Évolution du nombre de nœuds vivants au fil du temps. LEACH-C maintient une décomposition plus lente et régulière.
|
||||
],
|
||||
) <fig-alive>
|
||||
|
||||
#pagebreak()
|
||||
|
||||
#align(center)[
|
||||
Fin du rapport
|
||||
|
||||
3 Novembre 2025
|
||||
|
||||
31 Octobre 2025
|
||||
|
||||
Auteurs : Paul Roost et Alexis Bruneteau
|
||||
]
|
||||
|
||||
@ -1,3 +1,2 @@
|
||||
matplotlib>=3.5.0
|
||||
numpy>=1.21.0
|
||||
simpy>=4.1.0
|
||||
|
||||
Binary file not shown.
|
Before Width: | Height: | Size: 248 KiB |
Binary file not shown.
|
Before Width: | Height: | Size: 264 KiB |
Binary file not shown.
|
Before Width: | Height: | Size: 261 KiB |
@ -1,61 +0,0 @@
|
||||
Scenario,Protocol,Metric,Dynamic,Static,Impact(%)
|
||||
Scenario_1_Small_Low,LEACH,first_dead_node_round,45,45,0.00
|
||||
Scenario_1_Small_Low,LEACH,first_muted_round,40,40,0.00
|
||||
Scenario_1_Small_Low,LEACH,dlbi,0.8793837592010225,0.8793837592010225,0.00
|
||||
Scenario_1_Small_Low,LEACH,rspi,0.0,0.0,0.00
|
||||
Scenario_1_Small_Low,LEACH,final_alive_nodes,2,2,0.00
|
||||
Scenario_1_Small_Low,LEACH-C,first_dead_node_round,259,259,0.00
|
||||
Scenario_1_Small_Low,LEACH-C,first_muted_round,,,N/A
|
||||
Scenario_1_Small_Low,LEACH-C,dlbi,0.31865908800109843,0.31865908800109843,0.00
|
||||
Scenario_1_Small_Low,LEACH-C,rspi,0.0,0.0,0.00
|
||||
Scenario_1_Small_Low,LEACH-C,final_alive_nodes,0,0,0.00
|
||||
Scenario_2_Small_Medium,LEACH,first_dead_node_round,153,153,0.00
|
||||
Scenario_2_Small_Medium,LEACH,first_muted_round,1002,1002,0.00
|
||||
Scenario_2_Small_Medium,LEACH,dlbi,0.798389461028645,0.798389461028645,0.00
|
||||
Scenario_2_Small_Medium,LEACH,rspi,0.0,0.0,0.00
|
||||
Scenario_2_Small_Medium,LEACH,final_alive_nodes,1,1,0.00
|
||||
Scenario_2_Small_Medium,LEACH-C,first_dead_node_round,187,187,0.00
|
||||
Scenario_2_Small_Medium,LEACH-C,first_muted_round,,,N/A
|
||||
Scenario_2_Small_Medium,LEACH-C,dlbi,0.3286863472145973,0.3286863472145973,0.00
|
||||
Scenario_2_Small_Medium,LEACH-C,rspi,0.0,0.0,0.00
|
||||
Scenario_2_Small_Medium,LEACH-C,final_alive_nodes,0,0,0.00
|
||||
Scenario_3_Small_High,LEACH,first_dead_node_round,,,N/A
|
||||
Scenario_3_Small_High,LEACH,first_muted_round,,,N/A
|
||||
Scenario_3_Small_High,LEACH,dlbi,0.9530365000000001,0.9530365000000001,0.00
|
||||
Scenario_3_Small_High,LEACH,rspi,0,0,0.00
|
||||
Scenario_3_Small_High,LEACH,final_alive_nodes,100,100,0.00
|
||||
Scenario_3_Small_High,LEACH-C,first_dead_node_round,198,198,0.00
|
||||
Scenario_3_Small_High,LEACH-C,first_muted_round,,,N/A
|
||||
Scenario_3_Small_High,LEACH-C,dlbi,0.38098416268906454,0.38098416268906454,0.00
|
||||
Scenario_3_Small_High,LEACH-C,rspi,0.0,0.0,0.00
|
||||
Scenario_3_Small_High,LEACH-C,final_alive_nodes,0,0,0.00
|
||||
Scenario_4_Large_Low,LEACH,first_dead_node_round,7,7,0.00
|
||||
Scenario_4_Large_Low,LEACH,first_muted_round,93,93,0.00
|
||||
Scenario_4_Large_Low,LEACH,dlbi,0.9066860980183459,0.9066860980183459,0.00
|
||||
Scenario_4_Large_Low,LEACH,rspi,0.0,0.0,0.00
|
||||
Scenario_4_Large_Low,LEACH,final_alive_nodes,1,1,0.00
|
||||
Scenario_4_Large_Low,LEACH-C,first_dead_node_round,49,49,0.00
|
||||
Scenario_4_Large_Low,LEACH-C,first_muted_round,,,N/A
|
||||
Scenario_4_Large_Low,LEACH-C,dlbi,0.5538160103660335,0.5538160103660335,0.00
|
||||
Scenario_4_Large_Low,LEACH-C,rspi,0.0,0.0,0.00
|
||||
Scenario_4_Large_Low,LEACH-C,final_alive_nodes,0,0,0.00
|
||||
Scenario_5_Large_Low_200nodes,LEACH,first_dead_node_round,2,2,0.00
|
||||
Scenario_5_Large_Low_200nodes,LEACH,first_muted_round,181,181,0.00
|
||||
Scenario_5_Large_Low_200nodes,LEACH,dlbi,0.865889854185711,0.865889854185711,0.00
|
||||
Scenario_5_Large_Low_200nodes,LEACH,rspi,0.0,0.0,0.00
|
||||
Scenario_5_Large_Low_200nodes,LEACH,final_alive_nodes,1,1,0.00
|
||||
Scenario_5_Large_Low_200nodes,LEACH-C,first_dead_node_round,30,30,0.00
|
||||
Scenario_5_Large_Low_200nodes,LEACH-C,first_muted_round,,,N/A
|
||||
Scenario_5_Large_Low_200nodes,LEACH-C,dlbi,0.39199355126386604,0.39199355126386604,0.00
|
||||
Scenario_5_Large_Low_200nodes,LEACH-C,rspi,0.0,0.0,0.00
|
||||
Scenario_5_Large_Low_200nodes,LEACH-C,final_alive_nodes,0,0,0.00
|
||||
Scenario_6_Large_LowMed_200nodes,LEACH,first_dead_node_round,24,24,0.00
|
||||
Scenario_6_Large_LowMed_200nodes,LEACH,first_muted_round,220,220,0.00
|
||||
Scenario_6_Large_LowMed_200nodes,LEACH,dlbi,0.8407352599159577,0.8407352599159577,0.00
|
||||
Scenario_6_Large_LowMed_200nodes,LEACH,rspi,0.0,0.0,0.00
|
||||
Scenario_6_Large_LowMed_200nodes,LEACH,final_alive_nodes,1,1,0.00
|
||||
Scenario_6_Large_LowMed_200nodes,LEACH-C,first_dead_node_round,30,30,0.00
|
||||
Scenario_6_Large_LowMed_200nodes,LEACH-C,first_muted_round,,,N/A
|
||||
Scenario_6_Large_LowMed_200nodes,LEACH-C,dlbi,0.3719994495989293,0.3719994495989293,0.00
|
||||
Scenario_6_Large_LowMed_200nodes,LEACH-C,rspi,0.0,0.0,0.00
|
||||
Scenario_6_Large_LowMed_200nodes,LEACH-C,final_alive_nodes,0,0,0.00
|
||||
|
File diff suppressed because it is too large
Load Diff
File diff suppressed because it is too large
Load Diff
Binary file not shown.
Binary file not shown.
@ -1,105 +0,0 @@
|
||||
Parfait ! Voici le résumé détaillé du cours d'Algorithmes Répartis, formaté en Markdown.
|
||||
|
||||
# 🎓 Résumé Détaillé du Cours d'Algorithmes Répartis
|
||||
|
||||
[cite_start]Ce cours couvre les concepts fondamentaux des systèmes distribués et les algorithmes clés pour résoudre des problèmes de coordination et d'accord, tels que l'élection, l'exclusion mutuelle, le consensus, et la diffusion d'information[cite: 1540, 2061].
|
||||
|
||||
---
|
||||
|
||||
## I. Concepts Fondamentaux des Systèmes Distribués
|
||||
|
||||
### Définition et Caractéristiques
|
||||
|
||||
[cite_start]Un système distribué est un ensemble d'unités de traitement autonomes (**processus**, **processeurs**, ou **nœuds**) interconnectées sans mémoire partagée, que l'utilisateur voit pourtant comme une machine unique[cite: 1560, 1562].
|
||||
|
||||
* [cite_start]**Autonomie** : Chaque nœud prend ses propres décisions locales (programmes, mémoires)[cite: 1584, 1586].
|
||||
* [cite_start]**Interconnexion** : Les échanges d'informations se font via **messages**[cite: 1624, 1629].
|
||||
* [cite_start]**Asynchronisme et Absence de Temps Global** : L'exécution des nœuds est asynchrone, et les horloges locales sont différentes[cite: 1593, 1594, 1863]. [cite_start]Cela implique un ordre seulement **partiel** entre les actions, défini par la **causalité** (ordre de Lamport)[cite: 1865].
|
||||
|
||||
### Modélisation et Hypothèses
|
||||
|
||||
[cite_start]Les caractéristiques d'un système distribué dépendent de sa **topologie**, de ses **liens de communication**, de ses **processus**, et du **temps**[cite: 1907, 1908, 1909, 1910].
|
||||
|
||||
| Caractéristique | Modèles et Spécificités Techniques | Sources |
|
||||
| :--- | :--- | :--- |
|
||||
| **Topologie** | [cite_start]Graphe $G=(V, E)$ (anneau, arbre, étoile, clique)[cite: 1916, 1934, 1935, 1936, 1937]. [cite_start]On suppose souvent des communications **bidirectionnelles** et une topologie **connexe**[cite: 1921]. [cite_start]| [cite: 1916, 1934, 1935, 1936, 1937, 1921] |
|
||||
| **Communications** | [cite_start]**Fiabilité** (fiable, perte équitable)[cite: 1943]. [cite_start]**Ordre** (FIFO, quelconque)[cite: 1946]. [cite_start]**Temps d'acheminement** : **Synchrone** (borne $c$ connue sur le temps de transmission) ou **Asynchrone** (pas de borne connue)[cite: 1956, 1957, 1948]. [cite_start]| [cite: 1943, 1946, 1956, 1957, 1948] |
|
||||
| **Processus** | [cite_start]**Identifié** (UID unique, e.g., adresse IP) ou **Anonyme**[cite: 1980, 1981, 1992]. [cite_start]Sujet ou non aux **pannes** (arrêt, omission, byzantine)[cite: 1962, 2008, 2009, 2010, 2011]. [cite_start]| [cite: 1980, 1981, 1992, 1962, 2008, 2009, 2010, 2011] |
|
||||
| **Complexité** | [cite_start]Évaluée en nombre de **messages** (espace) ou en nombre de **rondes** (temps, en synchrone)[cite: 2072, 2075]. [cite_start]| [cite: 2072, 2075] |
|
||||
|
||||
---
|
||||
|
||||
## II. Les Horloges Logiques et l'Ordre Causal
|
||||
|
||||
[cite_start]Les horloges logiques permettent d'ordonner les événements sans horloge physique globale[cite: 2100].
|
||||
|
||||
### Relation de Précédence (Happens-Before $\rightarrow$)
|
||||
|
||||
[cite_start]La relation $\rightarrow$ établit un **ordre partiel** entre les événements[cite: 2214].
|
||||
|
||||
* [cite_start]$E_1 \rightarrow E_2$ si $E_1$ et $E_2$ se suivent dans le même processus[cite: 2116].
|
||||
* [cite_start]$E_1 \rightarrow E_2$ si $E_1$ est l'émission d'un message et $E_2$ sa réception[cite: 2117].
|
||||
* [cite_start]Elle est **transitive**, **irréflexible** et **antisymétrique**[cite: 2127, 2129, 2131].
|
||||
* [cite_start]Deux événements $E$ et $E'$ sont **concurrents** ($E || E'$) s'ils n'ont pas de relation de précédence[cite: 2227].
|
||||
|
||||
### Types d'Horloges Logiques
|
||||
|
||||
| Type | Représentation | Mise à Jour (Événement Local $P_i$) | Mise à Jour (Réception $m$ de $P_j$, estampillé $H$) | Caractéristique / Propriété | Sources |
|
||||
| :--- | :--- | :--- | :--- | :--- | :--- |
|
||||
| **Scalaire (Lamport)** | [cite_start]Entier $H_i$[cite: 2279]. | [cite_start]$H_i := H_i + 1$[cite: 2283]. | [cite_start]$H_i := \mathbf{Max}(H_i, H) + 1$[cite: 2284]. | [cite_start]Si $E_1 \rightarrow E_2$, alors $H(E_1) < H(E_2)$ (condition faible)[cite: 2088]. [cite_start]Ne garantit pas la causalité[cite: 2578]. [cite_start]| [cite: 2279, 2283, 2284, 2088, 2578] |
|
||||
| **Vectorielle (Mattern)** | [cite_start]Vecteur $V_i$ de taille $N$[cite: 2714]. | [cite_start]$V_i[i] := V_i[i] + 1$[cite: 2716]. | [cite_start]$V_i[i] := V_i[i] + 1$, et $\forall k \ne i, V_i[k] := \mathbf{max}(V_i[k], V[k])$[cite: 2719, 2720]. | [cite_start]$\mathbf{E_1 \rightarrow E_2 \Leftrightarrow V(E_1) < V(E_2)}$ (préserve la causalité)[cite: 2753, 2752]. [cite_start]$V[i]$ : nombre d'événements de $P_i$ connus[cite: 2686]. [cite_start]| [cite: 2714, 2716, 2719, 2720, 2753, 2752, 2686] |
|
||||
| **Matricielle** | [cite_start]Matrice $HM_i$ de taille $N \times N$[cite: 2792]. | [cite_start]$HM_i[i, i] := HM_i[i, i] + 1$, $HM_i[i, j] := HM_i[i, j] + 1$ (émission vers $P_j$)[cite: 2804, 2805]. | [cite_start]Mise à jour conditionnelle pour garantir la délivrance causale[cite: 2814, 2815]. | [cite_start]$HM_i[j, k]$ : connaissance de $P_i$ sur le nombre de messages de $P_j$ vers $P_k$[cite: 2796]. [cite_start]| [cite: 2792, 2804, 2805, 2814, 2815, 2796] |
|
||||
|
||||
---
|
||||
|
||||
## III. Problèmes Fondamentaux et Algorithmes
|
||||
|
||||
### 1. Problème d'Élection 👑
|
||||
|
||||
[cite_start]**Spécification** : Un et un seul nœud termine dans l'état **ÉLU**[cite: 331].
|
||||
|
||||
| Algorithme | Modèle / Topologie | Idée Clé | Complexité en messages (Pire Cas) | Sources |
|
||||
| :--- | :--- | :--- | :--- | :--- |
|
||||
| **Impossibilité** | Anneau synchrone, **anonyme** | [cite_start]La symétrie ne peut pas être brisée[cite: 338, 366]. | [cite_start]N/A | [cite: 338, 366] |
|
||||
| **Chang & Roberts** | [cite_start]Anneau unidirectionnel asynchrone, identifié[cite: 399, 396]. | Propagation des candidatures (UID). [cite_start]L'ID maximal gagne et fait une annonce **LEADER**[cite: 405, 407, 437]. | [cite_start]$O(N^2)$ [cite: 566] [cite_start]| [cite: 399, 396, 405, 407, 437, 566] |
|
||||
| **Hirschberg & Sinclair** | [cite_start]Anneau **bidirectionnel** asynchrone, identifié[cite: 675]. | [cite_start]Rondes d'envoi de l'ID sur des **distances croissantes** ($2^k$)[cite: 689, 690]. [cite_start]Le vainqueur est celui qui réussit à transmettre sur toute la distance[cite: 691]. | [cite_start]$O(N \log N)$ [cite: 712] [cite_start]| [cite: 675, 689, 690, 691, 712] |
|
||||
|
||||
---
|
||||
|
||||
### 2. Problème d'Exclusion Mutuelle 🔒
|
||||
|
||||
[cite_start]**Propriétés** : **Sûreté** (un seul processus en SC) et **Vivacité** (toute demande est satisfaite en temps fini)[cite: 908, 909].
|
||||
|
||||
| Algorithme | Type | Principe Clé | Complexité en messages (Par accès) | Sources |
|
||||
| :--- | :--- | :--- | :--- | :--- |
|
||||
| **Centralisé** | [cite_start]Basé sur un **coordinateur**[cite: 913]. | [cite_start]Le coordinateur centralise les requêtes, gère une file d'attente et délivre les permissions[cite: 916, 917]. | [cite_start]$2$ ou $3$ messages (Demande, Permission, Sortie)[cite: 984]. [cite_start]| [cite: 913, 916, 917, 984] |
|
||||
| **Le Lann** | [cite_start]Basé sur un **jeton** dans un anneau unidirectionnel[cite: 999, 1000]. | [cite_start]Seul le détenteur du jeton entre en SC[cite: 1001, 1059]. | [cite_start]$N$ (un tour d'anneau)[cite: 1085]. [cite_start]| [cite: 999, 1000, 1059, 1085] |
|
||||
| **Lamport** | [cite_start]Basé sur les **permissions** et les **horloges scalaires**[cite: 2280]. | Requêtes triées par estampille (date + UID). [cite_start]Nécessite un **ACK** de tous les autres processus[cite: 2298, 2305]. | [cite_start]$3(N-1)$ messages[cite: 2384]. [cite_start]| [cite: 2280, 2298, 2305, 2384] |
|
||||
| **Ricart et Agrawala** | [cite_start]Basé sur les **permissions** et les **horloges scalaires**[cite: 2487]. | Évite l'ACK systématique. [cite_start]Envoie un $REL$ (permission) seulement si la requête est prioritaire ou si le processus n'est pas demandeur[cite: 2491, 2502, 2503]. | [cite_start]$2(N-1)$ messages[cite: 2566]. [cite_start]| [cite: 2487, 2491, 2502, 2503, 2566] |
|
||||
|
||||
---
|
||||
|
||||
### 3. Problème de Consensus et Généraux Byzantins 🤝
|
||||
|
||||
[cite_start]**Objectif** : Accord des processus sur une valeur unique[cite: 10].
|
||||
|
||||
* [cite_start]**Problème des Généraux Byzantins** [cite: 14] [cite_start]: Les processus (généraux) doivent se mettre d'accord sur un plan de bataille (valeur) malgré la présence de **traîtres** (fautes arbitraires) qui envoient des messages contradictoires[cite: 15, 95, 96].
|
||||
* [cite_start]**Impossibilité Fondamentale** : Aucune solution n'existe si le nombre de processus $N$ est inférieur ou égal à $\mathbf{3f}$, où $f$ est le nombre de processus défectueux ($N \le 3f$)[cite: 150].
|
||||
* [cite_start]**Condition de Solution** : Une solution est possible si $\mathbf{N \ge 3f + 1}$[cite: 150].
|
||||
|
||||
---
|
||||
|
||||
### 4. Problème de Diffusion d'Information 📢
|
||||
|
||||
[cite_start]Cas où un processus envoie un message à tous les autres, en assurant la cohérence[cite: 1288, 1315].
|
||||
|
||||
| Type de Diffusion | Contrainte d'Ordre | Mise en Œuvre Technique | Sources |
|
||||
| :--- | :--- | :--- | :--- |
|
||||
| **Fiable (Reliable)** | [cite_start]**Accord** : tous les processus corrects livrent le message[cite: 1314]. | [cite_start]Utilise un **numéro de séquence** et une propagation aux voisins pour s'assurer que le message est bien délivré par tous[cite: 1324, 1329, 1347]. [cite_start]| [cite: 1314, 1324, 1329, 1347] |
|
||||
| **FIFO** | [cite_start]L'ordre d'émission par un processus est respecté à la livraison (délivrer $m_1$ avant $m_2$ si $m_1$ a été émis avant $m_2$)[cite: 1359]. | [cite_start]Utilisation de $msgBag$ et d'un compteur $next[q]$ pour différer la livraison des messages non attendus[cite: 1386, 1409]. [cite_start]| [cite: 1359, 1386, 1409] |
|
||||
| **Causale** | [cite_start]L'ordre causal ($\rightarrow$) est respecté (délivrer $m_1$ avant $m_2$ si $m_1 \rightarrow m_2$)[cite: 1425]. | Estampillage des messages avec un **vecteur d'horloges**. [cite_start]Le récepteur diffère la livraison si des messages causalement précédents manquent[cite: 1445, 1446]. [cite_start]| [cite: 1425, 1445, 1446] |
|
||||
| **Atomique (Totale)** | [cite_start]Tous les processus livrent les messages dans le **même ordre total**[cite: 1482]. | [cite_start]Utilise un **protocole de validation à deux phases** pour déterminer une estampille définitive unique[cite: 1492, 1493]. [cite_start]| [cite: 1482, 1492, 1493] |
|
||||
|
||||
---
|
||||
|
||||
Ce résumé fournit une vue complète des objectifs, des mécanismes et de la complexité des principaux algorithmes étudiés. Souhaitez-vous approfondir l'analyse de la complexité ou la preuve de l'un de ces algorithmes ?
|
||||
Loading…
x
Reference in New Issue
Block a user