Assegnamento di canali in reti non cablate.

Si considerano reti senza fili in cui possono presentarsi interferenze causate dalla trasmissione simultanea di pacchetti da parte di due stazioni diverse, ma vicine, che usino la stessa frequenza per comunicare. Si è studiato il problema di assegnare le frequenze alle stazioni base delle reti non cablate così che siano evitate le interferenze fra stazioni adiacenti, sia rispettata la distanza di almeno $2$ per il riuso delle frequenze, e la soluzione utilizzi il minor numero possibile di frequenze. In particolare, rappresentate le frequenze con colori (per semplicità indicati con numeri interi), le stazioni base della rete con i vertici di un grafo, e posto un arco fra due vertici se le stazioni sono una nell'area di trasmissione dell'altra, il problema si modella come una colorazione, con il minimo numero di colori, di un grafo. Tale problema è NP-hard per generici grafi. Pertanto, sono state proposte soluzioni ottime per famiglie speciali di grafi, quali anelli, alberi, reti esagonali e reti cellulari, che ben si prestano a modellare reti senza fili. Generalizzando, dati il grafo che modella la rete, la distanza di riuso $t+1 \ge 2$, ed un vettore di separazione $[\delta_1, \delta_2, \ldots, \delta_{t}]$, il problema di allocare le frequenze consiste nell'assegnare ad ogni nodo $x$ del grafo un colore $f(x)$, tale che lo scarto tra $f(y)$ ed $f(x)$ non scenda sotto $\delta_i$ ogniqualvolta la distanza (numero minimo di archi) tra le stazioni $x$ ed $y$ è uguale a $i$, minimizzando il massimo colore usato. Una colorazione del grafo che soddisfi tale vettore di separazione ed usi il minimo numero di colori è una $L(\delta_1, \delta_2, \ldots, \delta_{t})$-colorazione ottima. In [A2], per reti modellate da alberi e da grafi di intervalli, sono presentate $L(\delta_1, \delta_2, \ldots, \delta_{t})$-colorazioni, ottenute basandosi sulla nozione di vertici 'strongly-simplicial' (cioè vertici che formano con i propri vicini, visitati in un ordine opportuno, un grafo completo). Gli algoritmi proposti forniscono $L(\delta_1, \delta_2, \ldots, \delta_{t})$-colorazioni $\alpha$-approssimate e richiedono tempo polinomiale nel numero dei vertici del grafo e nella distanza di riuso. La costante $\alpha$ di approssimazione dipende da $t$ e dal vettore di separazione. Inoltre, per grafi di intervallo unitari, è discusso un algoritmo che richiede tempo lineare nel numero di intervalli per calcolare una $3$-approssimazione di una $L(\delta_1, \delta_2)$-colorazione del grafo. In [A7], si presentano algoritmi efficienti per trovare $L(2,1)$-, $L(2,1,1)$- e $L(1,\ldots,1)$-colorazione ottime di una griglia esagonale. Una griglia esagonale modella una rete in una regione piana, senza barriere geografiche, dove le stazioni base sono posizionate seguendo una tesselazione regolare del piano. Tali griglie esagonali sono interessanti perché richiedono meno colori per soddisfare i vincoli di separazione di quelli richiesti da una griglia cellulare o quadrata con lo stesso numero di vertici. I lavori di rassegna [I3, I4] sommarizzano e riorganizzano questi e precedenti risultati nell'area dell'assegnamento di canali in reti non cablate.