2
Indice
Indice ... 2
Indice delle figure ... 4
1. Introduzione ... 6
2. Formulazione del problema ... 12
2.1 Vincoli sulla topologia logica... 12
2.2 Capacità effettiva ... 15
2.3 Vincoli di interferenza ... 16
2.3.1 Physical Interference Model ... 16
2.3.2 Protocol Interference Model ... 25
2.3.3 Implementazione dei modelli interferenziali logici ... 32
2.3.4 Implementazione dei modelli interferenziali fisici ... 35
2.4 Routing ... 36
2.5 Bilancio di flusso ... 37
2.6 Funzione obiettivo ... 38
2.7 Vincolo sul numero di hop ... 39
2.8 Problema di ottimizzazione ... 39
3. Analisi dei risultati dell’algoritmo centralizzato ... 43
3.1 Topologia a catena con gateway ... 43
3.2 Topologia a catena con gateway e raggio di trasmissione di 2 hop ... 46
3.3 Topologia mesh con gateway ... 52
3.4 Analisi del SIR γ di soglia ... 59
3.5 Brevi conclusioni sul confronto tra physical e protocol model ... 62
3.6 Analisi delle tempistiche ... 64
4. Estensione dell’algoritmo per un ambiente distribuito ... 67
4.1 Introduzione al metodo Greedy ... 67
4.2 Ragionamento sul vincolo di routing distribuito ... 69
4.3 Vincolo distribuito sul numero di interfacce ... 71
4.4 Vincolo distribuito sulle interferenze ... 71
4.5 Funzione obiettivo distribuita ... 72
4.6 Schema di base dell’algoritmo distribuito ... 74
4.7 Introduzione ai protocolli di Ranking ... 77
4.7.1 Protocollo di Ranking Link-based ... 78
4.7.2 Formalizzazione del protocollo Link-based in C-Like ... 79
4.7.3 Ragionamenti finali sul Link-Based protocol ... 80
4.8 Altri protocolli di ranking ... 81
4.8.1 Protocollo traffic-based ... 82
4.8.2 Protocollo sink-tree based ... 82
4.8.3 Protocollo core-based ... 83
4.8.4 Protocollo di ranking Traffic & Link-based ... 84
5. Analisi dei risultati dell’algoritmo distribuito ... 85
5.1 Topologia a catena con gateway ... 86
5.2 Topologia a griglia con gateway ... 88
5.2.1 Topologia a griglia con 4 nodi ... 89
5.2.2 Topologia a griglia con 6 nodi ... 94
5.2.3 Topologia a griglia con 9 nodi ... 95
3
5.2.5 Riepilogo della topologia grid... 99
5.3 Analisi delle tempistiche ... 100
5.4 Caso critico ... 101
6. Lavori futuri ... 104
6.1 Reti multi-gateway ... 104
6.2 Scheduling physical model ... 105
6.3 Tagli notevoli ... 106
6.4 Multipath ... 108
Conclusioni ... 109
7. Abbreviazioni e acronimi ... 110
8. Bibliografia ... 111
Appendice A . Scheduling physical model ... 114
4
Indice delle figure
Figura 1 - Esempi di WMN... 6
Figura 2 - Infrastructure/Backbone WMN ... 7
Figura 3 - WMN con 6 router, 5 canali e 3 interfacce per router. Il numero su ogni link indica il canale utilizzato. ... 13
Figura 4 - Interfaccia i condivisa sul nodo k ... 18
Figura 5 - Nodo interferente nel modello interferenziale fisico ... 18
Figura 6 - Trasmissioni simultanee ... 21
Figura 7 - Trasmissioni simultanee ... 22
Figura 8 - Trasmissioni simultanee ... 23
Figura 9 - Trasmissioni simultaneee ... 24
Figura 10 - Introduzione al Protocol model ... 26
Figura 11 - Esempio Protocol model ... 27
Figura 12 - Esempio 11Protocol model ... 30
Figura 13 - Area di sensibilità del 16Protocol model ... 31
Figura 14 - Esempio 16Protocol model ... 32
Figura 15 - Topologia di riferimento per l'esempio di calcolo delle interferenze ... 32
Figura 16 - Calcolo interferenti del link (4,7) nell'11Protocol model ... 33
Figura 17 - Calcolo interferenti del link (4,7) nel 16Protocol model ... 34
Figura 18 - Topologia a catena con gateway ... 43
Figura 19 - Topologia a catena C=3 I=2 ... 44
Figura 20 - Soluzione particolare della catena con N = 5 (generalizzabile) ... 45
Figura 21 - Topologia 2x a catena ... 46
Figura 22 – Risultati della topologia 2x a catena con C=3 e I=2 ... 47
Figura 23 - Physical model su topologia 2x a catena con N = 5 ... 48
Figura 24 - 16Protocol sulla topologia 2x a catena con N = 5 ... 49
Figura 25 - 11Protocol sulla topologia 2x a catena con N = 5 ... 49
Figura 26 - 11Protocol sulla topologia 2x a catena con N = 8 ... 50
Figura 27 - 16Protocol sulla topologia 2x a catena con N = 8 ... 50
Figura 28 - 11Protocol sulla topologia 2x a catena con N = 10 ... 51
Figura 29 - 16Protocol sulla topologia 2x a catena con N = 10 ... 51
Figura 30 - Topologia mesh con N = 4 ... 52
Figura 31 - Topologia mesh con N = 5 ... 53
Figura 32 - Topologia mesh con N = 6 ... 53
Figura 33 – Risultati della topologia mesh con gateway ... 54
Figura 34 - Protocol model della topologia mesh con N = 4 ... 54
Figura 35 – Physical model della topologia mesh con N = 4 ... 55
Figura 36 – Protocol model della topologia mesh con N = 5 ... 56
Figura 37 – Physical model della topologia mesh con N = 5 ... 56
Figura 38 - Protocol model della topologia mesh con N = 6 ... 57
Figura 39 - Physical model della topologia mesh con N = 6 ... 57
Figura 40 - Risultati della variazione soglia su topologia mesh ... 59
Figura 41 - Soluzione della mesh con γ = 8 e N = 5 ... 60
Figura 42 - Soluzione della mesh con γ = 3.5 e N = 5 ... 60
Figura 43 - Soluzione della mesh con γ = 8 e N = 4 ... 60
Figura 44 - Soluzione della mesh con γ = 3.5 e N = 4 ... 60
Figura 45 - Soluzione della mesh con γ = 0.5 e N = 6 ... 61
5
Figura 47 - Topologia a griglia con N = 6 ... 62
Figura 48 - Soluzione della griglia con il 16protocol model ... 62
Figura 49 - Soluzione della griglia con il physical model e γ = 3.5... 63
Figura 50 - Tempistiche della topologia a catena 2x ... 65
Figura 51 - Tempistiche della topologia mesh ... 65
Figura 52 - Vincolo sul routing distribuito - Caso del multipath ottimo ... 70
Figura 53 - Funzione obiettivo di vicinato ... 72
Figura 54 - Topologia di riferimento per i ranking protocols ... 77
Figura 55 - Esempio sul Link-based ranking protocol ... 78
Figura 56 - Esempio sul secondo modello di Link-Based ranking protocol ... 81
Figura 57 - Esempio sul Sink-tree ranking protocol ... 83
Figura 58 - Esempio sul Core-based ranking protocol ... 83
Figura 59 - Esempio sul Traffic and Link-based ranking protocol ... 84
Figura 60 - Prestazioni del distribuito nella topologia a catena ... 86
Figura 61 - Topologia a griglia con N = 6 ... 88
Figura 62 - Topologia a griglia con N = 4 ... 88
Figura 63 - Topologia a griglia con N = 9 ... 88
Figura 64 - Topologia a griglia con N = 16 ... 89
Figura 65 - Soluzione centralizzata della topologia grid con N = 4 ... 90
Figura 66 - Soluzione distribuita della topologia grid con N = 4 ... 90
Figura 67 - Soluzione distribuita migliorata della topologia grid con N = 4 ... 93
Figura 68 - Soluzione centralizzata della topologia grid con N = 6 ... 94
Figura 69 - Soluzione distribuita della topologia grid con N = 6 ... 95
Figura 70 - Soluzione centralizzata della topologia grid con N = 9 ... 95
Figura 71 - Soluzione distribuita della topologia grid con N = 9 ... 96
Figura 72 - Soluzione centralizzata della topologia grid con N = 16 ... 97
Figura 73 - Soluzione distribuita della topologia grid con N = 16 ... 98
Figura 74 - Prestazioni del distribuito nella topologia a griglia ... 99
Figura 75 - Analisi delle tempistiche dell'algoritmo distribuito nella topologia grid ... 100
Figura 76 - Soluzione centralizzata nel caso critico grid 5x5 ... 102
Figura 77 - Esempio di topologia multi-gateway... 104
Figura 78 - Esempio di taglio sulla topologia grid con N = 16 ... 106
Figura 79 - Esempio di taglio sulla topologia grid con N = 25 ... 107
Figura 80 – Esempio di Branching 1° step ... 117
