Models and algorithms for the maximum parallel transmissions problem in wireless networks

The scheduling of transmissions in a wireless network can be performed through an optimization approach. However, when the physical interference model is considered, such approach may lead to numerical difficulties due to the Signal-to-Interference-plus-Noise-Ratio (SINR) value. The problem that is considered in this work is a subproblem of most of the scheduling problems and is called Maximum Parallel Transmissions (MPT) problem. Its objective is to maximize the number of simultaneous transmissions over a wireless network, under the physical SINR interference model. In the formulation of MPT, it is possible to express the SINR constraints as knapsack constraints. The latter ones can be subsequently reduced to cover inequalities. We proposed a technique to aggregate the cover inequalities according to a clustering of the network under consideration. Moreover, we improved an existing heuristic approach for the MPT problem. We considered different versions of the MPT problem. In the preliminary version we maximized the number of simultaneous transmissions, while transmitting powers are fixed. Then, we generalized the problem by associating a weight to each potential transmission, aiming at maximizing the total weight. Finally, we extended the model in order to permit nodes choose the transmitting power within a finite set of power levels. We solved each version of the problem through an algorithm that iteratively solves the optimization problem, and that separates cover inequalities in their aggregated form at each iteration. Some tests were performed in order to find the best settings of such algorithm.

Un approccio adottato nella risoluzione di problemi di scheduling su reti wireless si basa su modelli di ottimizzazione. Quando però si considera il modello di interferenza fisico, tale approccio può portare a problemi numerici dovuti al valore del rapporto tra segnale e interferenza-rumore (Signal-to-Interference-plus-Noise-Ratio). Il problema considerato in questo lavoro è un sottoproblema di gran parte dei problemi di scheduling su reti wireless, ed è detto Maximum Parallel Transmissions problem (MPT). L’obiettivo è quello di trovare il numero massimo di trasmissioni simultanee che possono essere attive in una rete wireless, secondo il modello di interferenza fisico. La formulazione di tale problema permette di esprimere i vincoli di SINR come vincoli di zaino. Questi ultimi possono essere successivamente ridotti a disuguaglianze di cover. Abbiamo proposto una tecnica per aggregare le disuguaglianze di cover tramite una clusterizzazione della rete considerata. Inoltre, abbiamo migliorato un approccio euristico esistente per il problema MPT. Abbiamo considerato diverse versioni del problema MPT. Nella prima versione si massimizza il numero di trasmissioni simultanee con potenze trasmissive fissate. Successivamente abbiamo generalizzato il problema aggiungendo dei pesi alle possibili trasmissioni, massimizzando così il peso totale. Infine, abbiamo esteso il modello in modo tale da permettere ai nodi di scegliere la potenza trasmissiva in un dato insieme di possibilità. Ogni versione del problema è stata risolta tramite un algoritmo che risolve il problema di ottimizzazione e che, ad ogni iterazione, separa le disuguaglianze di cover nella forma aggregata. Diversi test sono stati eseguiti per ricavare le impostazioni migliori di tale algoritmo.