Allocazione di dati a canali wireless multipli per trasmissioni in diffusione.

In [A3, A6, I1, I2, I5, C4, T1], si considera il problema di diffondere N dati, ciascuno caratterizzato da una sua popolarità, su K canali radio in modo da minimizzare il tempo medio di attesa degli utenti. Si assume di partizionare i dati fra i canali e di diffondere ciclicamente i dati assegnati a ciascun canale. Si forniscono in [A6] vari algoritmi di programmazione dinamica che trovano la soluzione ottima per questo problema. Se i dati hanno lunghezze identiche, si propone un algoritmo con complessità $O(NK log K)$, abbassando la complessità del migliore algoritmo precedentemente noto. Se, invece, le lunghezze dei dati non sono identiche, si dimostra che il problema è NP-arduo per $K=2$ e fortemente NP-arduo per $K$ arbitrario, fornendo per $K=2$ un algoritmo ottimo di complessità pseudo-polinomiale. Per $K$ qualsiasi, sono proposte in [A3, I5] varie euristiche, una delle quali trova velocemente soluzioni che si discostano al più del 2% da quelle ottime su istanze note nella letteratura. Tali euristiche sono generalizzate in [I1] al caso di canali soggetti ad errori di trasmissione non correggibili, modellati da una distribuzione geometrica. A seguito di una trasmissione errronea, l'utente scarta il dato corrotto e attende la prossima occorrenza dello stesso dato. Questo comportamento è ripetuto fino a che l'utente non riceve una copia integra del dato. Successivamente, in [I2, T1] è stato studiato il problema della diffusione di dati su canali soggetti a burst di errori, quali possono essere i canali wireless in presenza di fading. Il canale è modellato da una catena di Markov a due stati discreti, noto come modello semplificato di Gilbert-Elliot. In ciascun istante di tempo il canale può trovarsi o in uno stato buono nel quale trasmette corretamente o in uno stato cattivo nel quale è soggetto ad errori. I tempi medi di permanenza del canale nei due stati dipendono dalle probabilità di trovarsi e di transire fra gli stati. Anche per questo modello le euristiche proposte sono valutate sperimentalmente. Le soluzioni si comportano così bene in presenza di piccole, ma realistiche, probabilità di errore da far percepire all'utente un tempo medio di attesa confrontabile con quello che si otterrebbe se fossero utilizzati canali non soggetti ad errori.