Capitolo 3 Algoritmi sub-ottimi

3.1 Problema del controllo del carico in sistemi

distribuiti

Come già detto nel capitolo precedente rispetto agli algoritmi centralizzati in quelli distribuiti il problema del controllo del carico assume grande imporatnza.

Ci sono diversi approcci per la gestione dei casi unfeasible ed ognuno di questi è rivolto al conseguimento di un certo obiettivo.

Il principio dietro ad ogni tecnica è sempre lo stesso e consiste nel cambiamento dei vincoli secondo un certo criterio.

Agli atti pratici questo significa ridimensionare le esigenze degli utenti in termini di rate.

La differenza tra i vari metodi sta nel criterio con il quale vengono scelti gli utenti a cui ridurre il rate fino a far risultare l’allocazione possibile. Da notare che nei nostri algoritmi si è preso in considerazione la tratta in downlink e quindi con riduzione del rate ad un utente si intende che la BS relativa a quell’utente trasmetterà verso lo stesso un flusso dati a rate inferiore.

I due approcci principali sono:

*) Scelta degli utenti in modo da garantire la maggior equità di trattamento possibile.

*) Scelta degli utenti in modo tale da rendere il sistema feasible con il minimo rate loss e la minima potenza complessivamente impegnata.

L’approccio che si è seguito nell’implementazione degli algoritmi è il secondo appena citato.

Una sua descrizione molto dettagliata è rimandata ai paragrafi successivi.

3.2 Algoritmo iterativo parzialmente distribuito

La peculiarità fondamentale degli algoritmi distribuiti è la totale indipendenza delle celle nel decidere l’allocazione degli utenti al loro interno.

Ogni cella esegue le proprie allocazioni tenendo conto, in maniera indiretta, di come le risorse vengono assegnate nelle altre celle.

Attraverso la misura dell’interferenza, ogni utente, infatti, è sensibile all’interferenza globale prodotta da tutti gli altri utenti del sistema .

L’algoritmo che andremo a studiare cerca la convergenza dell’allocazione e delle potenze in modo iterativo.

Avremo cioè che le celle continueranno a risolvere il problema LP in modo ciclico tenendo conto dell’evoluzione dell’ISI in tutto il sistema. Nei casi migliori arriveremo ad una situazione stabile in cui nessuna cella modificherà più le sue allocazioni ma spesso, non verificandosi questa condizione, dovremo intervenire con tecniche di controllo del carico per arrivare alla convergenza del sistema.

Il controllo del carico, come già visto nei paragrafi precedenti, consiste nella riduzione delle richieste degli utenti in termini di rate.

Chiaramente le celle e gli utenti sulla quale intervenire non sono scelti in maniera casuale, ma secondo un criterio che ci possa portare ad avere la soluzione migliore possibile.

In realtà il solver che si è implementato non è puramente distribuito; questo perché vi è stato introdotto un controllo centralizzato della consistenza della soluzione.

3.2.1 Modello

Introducendo un’opportuna simbologia il problema originale di allocazione di risorse, affrontato nel capitolo precedente, può essere descritto sotto forma di un problema di ottimizzazione vincolata:

1 1 1 1

arg min

( ) ( )

( )

1,

1,...,

( )

( ),

1,...,

( )

P n b n

b n

n

N

b n

r k

k

K

b n

⋅

∑ ∑

≤ =

∑

=

=

∑

∈ [0,1]

⎧

⎪

⎪

⎪⎪

⎨

⎪

⎪

⎪

⎪⎩

Dove r(k) è il rate richiesto dal k-esimo utente, Pk(n) è la minima

potenza necessaria affinché il sistema possa supportare il rate r(k) sulla subcarrier n (potenza impegnata sul link tra l’utente k-esimo e la BS della sua cella di appartenenza) e bk(n) è un indicatore binario che

assume valore 1 se l’n-esima risorsa è assegnata al k-esimo link e zero altrimenti.

La variabile di uscita di questo sistema è proprio il vettore b contenente i valori di bk(n) per tutti i valori di k e di n; questo rappresenta il risultato

dell’allocazione secondo il sistema impostato (sistema 3.2.1).

La formulazione del problema è identica a quella vista nel sistema 2.5.1, l’unica differenza è la modalità con cui questo sistema viene risolto. Nel capitolo precedente si è osservato che nel caso di algoritmo di tipo centralizzato questo viene risolto tenendo conto di tutte le celle in una sola volta.

Nel caso degli algoritmi distribuiti, invece, il sistema viene risolto in maniera indipendente per ogni cella scomponendo quindi il problema principale in un determinato numero25 di sotto problemi di cardinalità inferiore.

Da queste considerazioni si evince che l’ottimalità della soluzione viene persa a favore di una complessità computazionale notevolmente ridotta.

3.2.2 Funzionamento generale

1: repeat

2: stableAll Å 0

3: for it Å 1,iterAll do

4: for cell Å 1,Ncells do

5: newAll(cell) Å allocate(cell) 6: newPow(cell) Å powCalc(cell) 7: if it ≠ iterAll then 8: oldAll(cell) Å newAll(cell) 9: oldPow(cell) Å newPow(cell) 10: else

11: diff = abs(oldPow(cell) – newPow(cell)) 12: if diff > coeff * newPow(cell) then

13: convFlag(cell) Å 1

14: end if

15: if cell = Ncells then

16: stabTotContr 17: if stabTotContrVar = 0 then 18: stableAll Å 1 19: else 20: reduceRate 21: end if 22: end if 23: end if 24: end for 25: end for 26: until stableAll = 0

Nell’algoritmo si ha un ciclo più esterno, gestito dalla variabile stableAll, che si conclude nel momento in cui si è trovata un’allocazione stabile per l’istanza corrente.

Soprattutto per efficienze spettrali elevate, questo processo può comportare un certo rate loss; infatti in molti casi, per trovare una soluzione feasible di un’istanza saremo costretti a modificare i vincoli del sistema riducendo le richieste degli utenti in termini di rate.

Nel ciclo più interno, che va dall’istruzione 3: alla 25: dello pseudo codice, si lavora per trovare una soluzione che ci soddisfi.

Indicando con N il numero di sottoportanti a disposizione e K il numero di utenti per cella, alla prima iterazione (it = 1) si risolve il problema di allocazione26, mediante LP, assegnando ad ogni utente r(k) sottoportanti. In conseguenza della natura distribuita dell’algoritmo si ha che ogni cella farà questa operazione in modo indipendente dalle altre.

La prima cella27 esegue la propria funzione allocate assegnando le risorse disponibili agli utenti al proprio interno; chiaramente alla prima iterazione l’interferenza dovuta alle altre celle sarà nulla.

La seconda cella fa la stessa cosa, ma stavolta tiene conto dell’interferenza prodotta dagli utenti nella prima cella.

Questo processo viene ripetuto per tutte le celle memorizzando in strutture opportune i risultati forniti dall’algoritmo.

Nelle iterazioni successive sono ripetute le stesse operazioni eseguite nella prima iterazione con la differenza che stavolta tutte le celle, compresa la prima, percepiscono già l’interferenza data dalle allocazioni effettuate da tutte le BS nell’iterazione precedente.

Di conseguenza sia le allocazioni sia le potenze impegnate dai singoli utenti cambieranno; ciò che si vuole è che con lo scorrere delle iterazioni le cose tendano a stabilizzarsi ma se questo non dovesse accadere, per far convergere le soluzioni, saremo costretti ad intervenire.

L’allocazione all’iterazione numero iterAll – 1 viene confrontata con l’allocazione all’iterazione numero iterAll , nel caso in cui le potenze si siano mantenute stabili si può asserire di aver trovato una soluzione consistente per l’istanza corrente; approfondiremo questo aspetto nel paragrafo successivo.

Se questo non dovesse accadere si dovrà togliere una sottoportante ad un determinato utente e ripetere il procedimento dall’inizio.

26 _{Funzione allocate.}

Il processo di riduzione del rate, appena citato, verrà ripetuto finché non sarà determinata una soluzione stabile del problema di allocazione di risorse.

3.2.3 Controllo di convergenza

Le istruzioni eseguite per il controllo di convergenza sono quelle che, nello pseudo-codice, vanno dalla 11: alla 14:.

L’algoritmo confronta, a livello di cella, le potenze risultanti nell’allocazione numero iterAll -1 con quelle ottenute nell’iterazione numero iterAll facendo uso di un parametro28.

La scelta del valore di questo coefficiente risulta critica per il funzionamento del sistema ed è quindi importante il suo corretto dimensionamento

Usando un valore troppo alto si ha un tempo di “convergenza” basso ma il rischio che si corre è quello di avere una “falsa convergenza” cioè, dal criterio prima illustrato, la situazione risulta stabile ma in realtà il sistema non ha trovato una soluzione feasible per l’istanza.

Utilizzando invece un valore troppo basso si evitano sicuramente le false convergenze ma per risolvere un’istanza si impiega molto più tempo rispetto a quelllo strettamente necessario.

Va specificato che le potenze messe a confronto per determinare la stabilità a livello cellulare sono quelle totalmente impegnate in ogni singola cella.

Definendo:

(

)

(

)

(

)

diff cell

=

oldPow cell newPow cell

−

con oldPow(cell) e newPow(cell) pari alle potenze totalmente impegnate nella cella cell rispettivamente nelle iterazioni iterAll – 1 ed iterAll, nel caso che il confronto prima illustrato dia esito negativo si ha:

(

)

diff coeff newPow cell

>

⋅

le celle per le quali questo si verifica sono dette “celle problematiche” . Gli utenti appartenenti alle suddette celle, nel caso in cui ce ne siano, sono i primi che vengono presi in considerazione per la procedura di riduzione del rate.

Chiaramente la presenza di anche una sola cella problematica è indice di una convergenza non raggiungibile con il livello attuale di capacità totale del sistema.

Questa verifica corrisponde all’istruzione 16: nello pseudo codice e l’esito di questo controllo si rispecchia nella variabile stabTotContrVar. In questi casi si procede alla riduzione del rate ad un determinato utente e si riparte dalla prima iterazione, cioè dall’istruzione 3: nello pseudo codice con it = 1.

Quello appena visto è il controllo di consistenza della soluzione a livello distribuito.

Come accennato nei paragrafi precedenti a questo controllo si è affiancato uno strumento di verifica centralizzato.

Il motivo di questa ulteriore funzione sta nelle peculiarità del solver implementato; infatti, l’algoritmo trova rapidamente soluzioni per le istanze ma questo tempo di convergenza basso può, in alcuni casi, indurre in errore il controllore distribuito.

Proprio per evitare di prendere in considerazione soluzioni inconsistenti si è introdotto una funzione ausiliaria centralizzata che interviene in queste particolari circostanze.

Questo tipo di controllo è lo stesso che viene utilizzato nell’algoritmo MA; quindi ai fini di evitare un’inutile ridondanza per la sua descrizione si rimanda ai paragrafi 3.3.3 e 3.3.4.

3.2.4 Procedura di riduzione del rate

Nel caso in cui il controllo di convergenza dia esito negativo per tutte le celle29 abbiamo trovato un’allocazione feasible che rispetta i nostri vincoli per l’istanza in analisi.

Nell’eventualità in cui ci sia anche una sola cella problematica si deve procedere al rilassamento dei vincoli imposti nel sistema 3.2.1..

Ciò che viene fatto in pratica è sintetizzabile in tre passi: *) Scelta di una cella.

*) Scelta di un utente all’interno di questa cella. *) Riduzione del rate all’utente selezionato.

La procedura dettagliata è invece riassumibile tramite il seguente pseudo codice:

1: outVar Å 0

2: for cell Å 1,NprobCell 3: minTermContr(cell) 4: end for

5: if NprobMinCell = 0 then 6: cellChoice1 7: else 8: cellChoice2 9: end if 10: repeat 11: powOrd(choiceCell) 12: userChoice 13: if nSub(choiceUser) = 1 then 14: userRemove(choiceUser) 15: else 16: outVar Å 1 17: end if 18: until outVar = 0 19: subCarRemoval(choiceUser)

Si definisce NprobCell il numero di celle problematiche nel sistema e

NprobMinCell il numero di celle problematiche che sono ai minimi termini.

Si definisce una cella ai minimi termini se tutti gli utenti al suo interno, nell’ultima iterazione, si sono visti allocare una sola sottoportante ciascuno.

Un utente che si vede allocare una sola sottoportante ha a disposizione il minimo rate diverso da zero possibile.

Si determinano30 quindi quante31 e quali sono le celle problematiche ai minimi termini.

Queste celle, non volendo disattivare completamente alcun utente, non possono subire ulteriori riduzioni di rate.

30 _{Funzione minTermContr.} 31 _N

Chiaramente, in modo plausibile per alte efficienze spettrali, si può verificare il caso in cui tutte le celle problematiche siano ai minimi termini32.

Nel caso in cui NprobMinCell = 0 si seleziona tra tutte le celle non ai minimi

termini quella che consuma la minor quantità di potenza33 (la chiamiamo choiceCell).

In caso contrario, si cerca la cella che consuma la maggiore quantità di potenza tra quelle problematiche che non sono ai minimi termini34.

Il problema che rimane è determinare all’interno della cella selezionata l’utente a cui ridurre il rate.

Per far questo si ordinano in modo decrescente le potenze impegnate dagli utenti della cella scelta35; l’utente scelto36 è quello che consuma la maggiore quantità di potenza (lo chiamiamo choiceUser).

Prima di procedere alla riduzione del rate si deve operare un controllo sull’utente selezionato; infatti, nel caso in cui l’utente choiceUser nell’ultima allocazione si sia visto assegnare una sola sottoportante (nSub(choiceUser) = 1) siamo costretti, per non disattivare alcun utente, ad operare una scelta diversa.

Ciò che si fa in questo caso è rimuovere dalla lista ordinata questo utente ed operare secondo il medesimo criterio di prima una nuova scelta; questo consiste, nello pseudo codice, a ripartire dall’istruzione 10:.

Questo processo viene ripetuto fino a che non si trova un utente che sia in grado di sostenere una riduzione di rate.

Una volta selezionato un user ciò che rimane da fare è implementare la riduzione del rate37 che consiste nel segnalare all’algoritmo che 32 _N probMinCell = 0. 33 _{Funzione choiceCell1.} 34 _{Funzione choiceCell2.} 35 _{Funzione powOrd.} 36 _{Funzione userChoice.} 37 _{Funzione subCarRemoval.}

all’utente choiceUser, alla successiva esecuzione dell’allocazione, si deve assegnare una sottoportante in meno.

Agli atti pratici questo consiste nel modificare le condizioni nel sistema 3.2.1 ovvero nel ridurre r(k) dove k = choiceUser.

Avendo operato un rilassamento dei vincoli nell’esecuzione successiva aumenterà la probabilità dell’algoritmo di trovare un’allocazione stabile per l’istanza corrente.

3.3 Algoritmo multi-assign

Il multi-assign è un algoritmo di tipo ibrido cioè né puramente distribuito, né puramente centralizzato e pur agendo in maniera diversa, presenta caratteristiche in comune con i solver fino ad ora presi in esame.

Questo algoritmo ricerca un’allocazione soft per un’istanza, cioè una soluzione feasible che non comporti riduzione del rate al alcun utente. Nei casi in cui questo sia possibile si cercano soluzioni sempre migliori andando ad analizzare la situazione interferenziale sulle varie sottoportanti; a partire da questa analisi si vanno quindi a scoraggiare degli utenti, scelti ad hoc, all’uso di determinate subcarrier.

In molti casi una soluzione soft non è ottenibile; quello che si fa in queste circostanze è andare a rimuovere utenti, con un determinato criterio, fino ad ottenere una soluzione feasible per l’istanza corrente. Una volta trovata una soluzione feasible, soft o hard che sia, l’MA esegue un controllo di consistenza simile a quello centralizzato che viene utilizzato nell’algoritmo iterativo parzialmente distribuito.

Vedremo i dettagli del funzionamento generale appena esposto nei paragrafi successivi.

3.3.1 Modello

Il problema risolto dal multi-assign è quello dell’allocazione di risorse; la formulazione del problema è, ad una prima analisi, molto simile alle formulazioni finora illustrate anche se, come vedremo, delle differenze sussistono.

Le maggiori divergenze con gli altri algoritmi sono però a livello di strategia post-allocazione cioè nel comportamento dell’algoritmo una volta che questo ha trovato una soluzione tramite LP.

In breve l’MA consiste nella risoluzione iterativa della versione “rilassata” di una formulazione ILP (Integer Linear Programming) del problema di allocazione ottenuta agendo sul vincolo relativo all’interferenza intercellulare rappresentato nella (2.2.10):

0 2 ,

( )

( , )

( )

P n

SNR k n

B N

G

n

=

⋅

⋅

Dove Pk(n) è la potenza minima che l’utente k, paartenente alla cella j,

deve vedere impegnata sulla sottoportante n per raggiungere, su quella stessa sottoportante, un rapporto segnale rumore pari a SNR(k,n), B è lo spazio nello spettro occupato da una sottobanda, N0 è la densità spettrale

di potenza di rumore e Gk(n) è il guadagno di canale tra l’utente k e la

BS della propria cella sulla sottoportante n.

La modifica nella (2.2.10) fa in modo che la formulazione originaria (sistema 2.3.1) del problema di allocazione di risorse possa essere decomposta in J problemi di minimo vincolato, dove J è il numero di celle del sistema.

La formulazione del problema per la cella j-esima è la seguente:

{ }

( )

( )

( )

( )

( )

min

( )

1,

0,

,

0,1

b n

n M

b n

k

k

n

k

n M

b n

P n

r

U

P

U

∈

∈

∑

⎧

⎪

⎪

⎪

_∑

_{≤ ∀}

⎪

⎪⎪

⎨

∑

≥

, ∀ ∈

⎪

⎪

_{≥ ∀ ∈}

⎪

⎪

∈

⎪

⎪⎩

Dove Uj = {u1, u2 ,… , uK} è l’insieme degli utenti della j-esima cella, bk(n) è una varibile che assume valore 1 se la sottoportante n-esima è

assegnata all’utente k-esimo e 0 altrimenti e r(k) = r è il rate richiesto dall’utente i.

Confrontando la (3.3.1) con la (2.2.10) si capisce in che modo si va ad agire sul vincolo relativo all’interferenza intercellulare; infatti, è ben visibile che nell’espressione della potenza della (3.3.1) non compare il termine relativo a questo fenomeno.

Questa formulazione è usata solo nella fase iniziale dell’algoritmo; infatti, per poter arrivare ad una soluzione significativa, è impossibile trascurare l’incidenza dell’interferenza.

Per questo motivo dopo una fase iniziale in cui questa viene trascurata la prendiamo in considerazione andando a modificare in maniera opportuna la matrice dei costi di allocazione che determina le assegnazioni eseguite dall’algoritmo.

Come già visto per l’algoritmo iterativo distribuito anche in questo caso, dato che ogni cella risolve il problema in modo autonomo, si perde l’ottimalità della soluzione a vantaggio di una complessità computazionale inferiore.

3.3.2 Funzionamento generale

9: for sub Å 1, subCarNumber do 10: powerAll(sub) 11: feasContr(sub) 12: end for 13: if feasVar = 1 then 14: userToDisc 15: else 16: newAllHard Å allocHard 17: end if 18: hardAllocContr 19: allQualContr(it)

20: if powerNewTot < powOldTot then 21: oldAllSoft Å newAllSoft

22: end if

23: changeAll(it) 24: end for

Come già anticipato in precedenza inizialmente ogni cella esegue l’allocazione secondo il sistema (3.3.2) cioè senza tenere conto dell’interferenza generata dalle altre celle38.

Successivamente, data la soluzione appena ottenuta, vengono calcolate le potenze realmente in gioco nel sistema39, cioè quelle impegnate nello stesso tenendo conto dell’interferenza mutua tra le varie celle.

Avendo a disposizione queste ultime si può verificare se la soluzione calcolata tramite allocNoInt è feasible cioè se è realmente implementabile.

Nel caso in cui su tutte le sottoportanti vi siano risultati consistenti40 allora abbiamo trovato una soluzione, che chiameremo soft, dell’istanza. In questa evenienza, si analizzano dettagliatamente i risultati ottenuti per raggiungere un miglioramento degli stessi nell’iterazione successiva41; in linea parallela, nonostante si sia trovata una soluzione soft, si provano a cancellare degli utenti secondo un determinato criterio ottenendo così un’allocazione hard per gli utenti nell’istanza corrente.

Se c’è invece almeno una sottoportante sulla quale la soluzione trovata risulta unfeasible allora si procede direttamente alla ricerca di un’allocazione hard, ottenuta grazie alla riduzione di rate ad un certo numero di utenti42.

38 _{Funzione allocNoInt.} 39 _{Funzione powerAll.} 40 _{Caso in cui feasVar = 1.} 41 _{Funzione userToDisc.} 42 _{Funzione allocHard.}

Arrivati a questo punto si verifica la qualità rispettivamente dell’allocazione hard43 e, nel caso sia a disposizione, dell’allocazione soft44.

Da notare che di solito allocazioni soft sono disponibili solamente per basse efficienze spettrali dove si riescono a trovare soluzioni feasible senza il bisogno di agire sui rate degli utenti.

Con verifica della qualità si intende il confronto dei risultati ottenuti con la migliore soluzione avuta fino all’iterazione corrente per l’istanza presa in analisi.

L’ultima operazione svolta nel corso di un’iterazione è la modifica della matrice dei costi tramite le informazioni elaborate dalle funzione userToDisc; questo permette di tenere conto dell’interferenza intercellulare, fenomeno che nelle fasi iniziali dell’esecuzione dall’algoritmo viene trascurato.

Questo processo è molto importante perché la matrice dei costi che si modifica viene utilizzata nell’esecuzione successiva dall’algoritmo LP per effettuare l’allocazione.

3.3.3 Calcolo delle potenze effettive

Come spiegato in precedenza, alla prima iterazione l’algoritmo deduce l’allocazione da una matrice dei costi costruita non tenendo conto dello stato di interferenza del sistema.

Successivamente si tiene conto di questo fenomeno modificando la matrice dei costi in maniera opportuna; di conseguenza anche la soluzione fornita dall’algoritmo sarà in generale diversa.

43 _{Funzione hardAllocContr.} 44 _{Funzione allQualContr.}

L’interazione con la matrice è di tipo empirico, quindi i valori in essa contenuti ad una certa iterazione non rispecchiano in modo esatto lo stato del sistema; perciò non è pensabile utilizzarla per calcolare le potenze effettivamente in gioco nello stesso.

Quello che si è fatto per raggiungere questo obiettivo è stato partire dalla (2.3.4) ed elaborarla per arrivare a derivare un’espressione che ci permettesse di calcolare le potenze di nostro interesse.

Partiamo dalla (2.3.4) scritta in forma estesa:

2 ( ) , 2 ( ) 0 , 1

( , )

( )

( )

( )

( )

SINR k n

P

n G

n

B N

P

n G

n

=

⋅

⋅ +

∑

⋅

Le variabili in questa espressione hanno il medesimo significato riportato nel capitolo 2.

La (3.3.3) è equivalente a: 2 2 _{( )} ( ) , , 0 1

( )

( )

( , ) (

( )

( )

)

P

n

G

n

SINR k n

P

n G

n

B N

⋅

=

⋅

_∑

⋅

+ ⋅

Per renderla più compatta definiamo PN come la potenza di rumore:

Prendendo in considerazione la sottoportante n e normalizzando questa potenza rispetto al guadagno tra la BS della cella j e l’utente, appartenente alla stessa, che fa uso di quella sottoportante si ottiene:

2 ,

( )

( )

P j

P

G

n

=



Riferendoci alla stessa subcarrier definiamo Z come la matrice dei guadagni normalizzata cioè Zi,j(n) è il guadagno tra la BS nella cella j ed

il mobile nella cella i normalizzato rispetto al guadagno tra la BS nella cella i ed il mobile nella stessa cella:

2 , , 2 ,

( )

( )

( )

G

n

Z

n

G n

=

Partendo dall’ipotesi che tutti gli utenti richiedano lo stesso rate si definisce:

SINR k n

( , )

=

γ

con:

γ

=

2

−

1

dove η rappresenta l’efficienza spettrale che gli utenti vogliono raggiungere.

La 3.3.4 può quindi essere riscritta: ( ) ₀ ( ) _, 1

( )

(

( )

( )

( ))

P

n

γ

P

n Z

n P j

= ⋅

_∑

⋅

+



l’equazione appena ottenuta può essere estesa in forma vettoriale così da includere in un’unica espressione tutti gli utenti del sistema che fanno uso di una determinata sottoportante:

P

= ⋅

γ

((

Z I P P

− ⋅ +

)



)

isolando il vettore delle potenze si ottiene:

( (1

I

⋅ +

γ

)

− ⋅ ⋅ = ⋅

γ

Z P

)

γ

P



1

α

γ

γ

=

+

si arriva infine al nostro obiettivo:

L’espressione appena ottenuta si ha per ogni sottoportante e la soluzione del sistema lineare che ne risulta ci fornisce le potenze realmente impegnate nel sistema tenendo conto dell’interferenza cellulare.

Del fatto che nella (3.3.14) si tiene conto di questo fenomeno si deduce intuitivamente osservando la forma della (3.3.3).

3.3.4 Analisi della consistenza della soluzione

Una volta calcolata la matrice dei guadagni normalizzata, avendo a disposizione la soluzione trovata dall’algoritmo, si può verificare la consistenza del sistema lineare da risolvere per trovare le potenze effettivamente impegnate nel sistema.

Per fare questo si sfrutta una preposizione (la cui dimostrazione si rimanda ad altri testi45):

Data una matrice dei guadagni Z stocastica non degenere con probabilità pari ad 1 abbiamo che il massimo rapporto segnale rumore raggiungibile da ogni utente è pari a γ, con:

1

1

γ

λ

=

−

Dove λ è il più grande autovalore della matrice Z.

Si può capire il funzionamento del controllo di consistenza analizzando il seguente pseudo-codice:

45 _{Jens Zander,”Performance of optimum transmitter power control in cellular radio systems”, IEEE}

1: for sub Å 1, subCarNumber do 2: eigenValues = eig(Z(sub)) 3: lambda(sub) = max(eigenValues) 4: gamma(sub) = 1/(lambda-1) 5: end for 6: sysContr

Da questo si capisce immediamente che, come già detto, abbiamo una matrice dei guadagni normalizzata per ogni sottoportante (le sottoportanti sono analizzate una alla volta).

La funzione eig calcola gli autovalori della matrice dei guadagni normalizzata relativa alla sottoportante sub.

Una volta calcolato per ogni sottoportante quale sia il massimo rapporto segnale rumore ottenibile (gamma(sub)) si passa alla fase di controllo della soluzione trovata.

Avendo dei SINR richiesti dagli utenti tutti uguali, come si può vede re nella (3.3.9), si esegue la seguente verifica per ogni sottoportante46:

gamma sub

(

)

≥

γ

Se la (3.3.16) non vale, anche per una sola sottoportante, il sistema risulta unfeasible; quello che si fa in questi casi è andare a studiare il problema a livello locale per poter cercare una soluzione valida nell’iterazione successiva.

3.3.5 Allocazione soft

Nel caso in cui il controllo descritto nel paragrafo precedente dia esito positivo, cioè il sistema risulti feasible, abbiamo a disposizione un’allocazione soft per l’istanza in analisi.

Quello che si fa in questa evenienza, a prescindere dall’iterazione corrente, è modificare, in modo opportuno, la matrice dei costi che verrà utilizzata dall’algoritmo per calcolare la soluzione nell’iterazione successiva.

Le modifiche sono fatte in modo da far rientrare l’interferenza intercellulare, parametro inizialmente trascurato, tra i fattori di notevole peso nella risoluzione del problema di allocazione.

Analizzando lo stato di interferenza del sistema quello che si fa è scegliere con un qualche criterio degli utenti e scoraggiarli dall’uso di determinate sottoportanti che risultano per loro critiche.

Lo scoraggiamento dell’utente k all’uso della sottoportante n consiste a livello pratico nell’aumento del costo della risorsa n per l’utente k, cioè nella moltiplicazione della relativa cella nella matrice dei costi per un coefficiente maggiore dell’unità.

La scelta degli utenti e delle sottoportanti sulla quale agire è un passo critico dell’algoritmo ed è implementato, nel nostro caso, dalla funzione userToDisc.

Vediamo come si opera la scelta delle sottoportanti su cui lavorare: 1: for sub Å 1, subCarNumber do

2: powSubNoInt(sub) Å powNoIntCalc(sub) 3: powSubInt(sub) Å powIntCalc(sub)

5: end for

6: powTotNoInt Å powTotNoIntCalc

10: if ((powSubInt(sub) > powThr)&&(interfIncrease > coeff2)) then 11: subAdd

12: end if 13: end for

Come si può notare quello che inizialmente viene fatto è memorizzare le potenze impegnate sulle varie sottoportanti sia tenendo conto dell’interferenza sia trascurandola.

La funzione interfIncreaseCalc restituisce un indice di interferenza per ogni sottoportante calcolato, fissando una sottoportante sub, come il rapporto tra la potenza complessivamente impegnata nel sistema calcolata tenendo conto dell’interferenza sulla sottoportante sub47 e quella calcolata trascurando l’interferenza sulla solita sottoportante48. Successivamente viene definita una soglia di potenza49calcolata come il rapporto tra la potenza totale impegnata nel sistema trascurando gli effetti dell’interferenza ed un certo coefficiente (coeff) maggiore dell’unità.

La scelta del valore di coeff risulta abbastanza critica infatti determina il numero di sottoportanti su cui ad ogni iterazione l’algoritmo va a lavorare (valore stabilito per via empirica).

47 _{powSubInt(sub).} 48 _{powSubNoInt(sub).} 49 _powThr.

Affinché una certa sottoportante venga aggiunta all’elenco delle sottoportanti su cui andare ad effettuare lo scoraggiamento di un utente50 si devono verificare due condizioni:

*) La potenza impegnata sulla sottoportante calcolata tenendo conto dell’interferenza deve superare la soglia stabilita.

*) L’indice di interferenza su quella sottoportante deve superare un certo valore prefissato (coeff2).

Il senso del secondo vincolo è quello di non andare a lavorare su sottoportanti su cui è impegnata molta potenza ma nelle qualii la situazione senza interferenza non differisce molto da quella con interferenza.

Questo perché le strategie utilizzate lavorano proprio su questo fenomeno e risulta inutile andare ad operare su sottoportanti in cui questo non incide in maniera sostanziosa.

La scelta del valore di coeff2 risulta abbastanza intuitiva e, rimanendo in determinati margini poco al di sopra dell’unità, non critica per il sistema. Una volta determinate le sottoportanti su cui lavorare rimane da decidere quali utenti scoraggiare.

La scelta progettuale che si è fatta è di scoraggiare un solo utente per ogni sottoportante; questa decisione nasce dalla volontà di modificare in maniera graduale lo stato del sistema, dato che con la dissuasione si va a modificare la matrice dei costi, in modo da poter tenere sotto controllo le reazioni dell’algoritmo ed evitare lo swapping di un gran numero di utenti in una sola volta.

Di seguito è riportato il processo seguito per ognuna delle sottoportanti selezionate:

1: userAllLoad

2: for user Å 1,userAllNumber do

3: partialSysSolve

4: newPowCalc(user)

5: end for

6: userToDelCalc

Inizialmente si caricano in strutture adeguate le potenze impegnate dai vari utenti sulla sottoportante in esame51.

Successivamente si rimuove un utente alla volta, tra gli userAllNumber52 allocati su quella sottoportante, e si calcolano le potenze impegnate dagli utenti rimanenti sulla sottoportante53 facendo ricorso ad un sistema lineare analogo a quello illustrato nel paragrafo 3.3.3 ma con una cardinalità inferiore54; la riduzione della cardinalità è dovuta al fatto che non si tiene conto, nel calcolo delle potenze, dell’utente eliminato.

Ovviamente queste potenze diminuiranno alla luce del fatto che gli utenti rimanenti non percepiranno più l’interferenza che veniva creata dall’utente a cui è stato ridotto il rate.

L’utente che si sceglie è quello che, una volta rimosso, comporta la massima diminuzione della potenza totale impegnata su quella sottoportante55.

Alla fine di questo processo avremo selezionato un utente per ognuna delle sottoportanti critiche; quello che rimane da fare è mettere in pratica la dissuasione.

Come già detto si ha a disposizione una matrice dei costi contenente il costo di allocazione di ogni utente su ogni sottoportante e, volendo che

51 _{Funzione userAllLoad.}

52 _{Pari al numero di celle del sistema.} 53 _{Funzione newPowCalc.}

54 _{Funzione partialSysSolve.} 55 _{Funzione userToDelCalc.}

l’algoritmo non trovi conveniente l’assegnamento di una certa sottoportante ad un certo utente, non rimane alto che aumentare il valore contenuto nella cella che rappresenta il costo relativo a quella particolare allocazione.

L’incremento del valore non è casuale, quello che si fa è moltiplicare il valore preesistente per un certo coefficiente maggiore dell’unità.

Per avere una maggiore sensibilità sulla gestione degli utenti si ha un coefficiente per ogni coppia utente-sottoportante.

Ogni volta che viene eseguita la procedura di scoraggiamento il coefficiente relativo viene utilizzato e successivamente aggiornato (aumentato).

3.3.6 Allocazione hard

Nel caso che non si sia trovata un’allocazione soft consistente si cerca una soluzione feasible del problema introducendo una certa percentuale di rate loss.

Se il sistema risulta unfeasible allora vorrà dire che su un numero di sottoportanti pari a subUnfeasNumber, sulle quali si lavorerà, l’allocazione trovata non è supportata.

Il procedimento che si segue è illustrato nel seguente pseudo-codice: 1: for sub Å 1, subUnfeasNumber do

2: repeat

3: userToDelChoice(sub)

4: rateReduce(sub)

5: partSysCalc(sub)

7: until subFeasVar(sub) = 0

8: end for

Per ognuna delle sottoportanti prese in considerazione si opera una riduzione del rate progressiva fin quando la soluzione trovata non risulta consistente.

Per prima cosa si seleziona l’utente da cancellare in modo analogo a come si opera nell’allocazione soft56.

Successivamente si rimuove l’utente da quella subcarrier57 e si calcola quali sono le nuove potenze impegnate dagli utenti rimanenti58.

Se operando un controllo sulla soluzione trovata dall’algoritmo per la sottoportante in analisi59 si vede che adesso è feasible allora si passa alla sottoportante successiva altrimenti si ripete il procedimento appena illustrato.

3.3.7 Qualità delle soluzioni

Per stabilire la qualità di un’allocazione, una volta trovata una soluzione consistente, si usano criteri diversi per i due diversi approcci60.

Per quanto riguarda l’approccio soft la verifica è banale infatti si tiene in memoria l’allocazione che comporta la minor potenza impegnata complessivamente nel sistema.

Per quanto riguarda l’allocazione hard le cose sono un po’ più articolate per la presenza di un fattore di qualità in più, il rate loss.

56 _{Funzione userToDelChoce.} 57 _{Funzione rateReduce.} 58 _{Funzione partSysCalc.} 59 _{Funzione subFeasContr.} 60 _{Soft e Hard.}

La scelta che si è operata è quella di memorizzare l’allocazione con il minor rate loss e, in caso di pari perdite per due allocazioni, quella che garantisce la minore potenza impegnata complessivamente nel sistema.

3.4 Algoritmo NF

Questo algoritmo presenta molte analogie con quello illustrato nel paragrafo 3.2; infatti, anche questo solver è parzialmente distribuito ed opera in maniera iterativa.

L’acronimo NF sta per near – far ed è strettamente correlato, come si capirà tra poco, con il principio di funzionamento di questo solver.

La strategia utilizzata in questo algoritmo è quella di individuare all’interno del sistema gli edge user, utenti che saranno classificati come far user e dare a loro priorità nell’allocazione rispetto agli atri utenti classificati come near user.

Questo privilegio consiste nel dare la possibilità agli utenti al bordo della cella, che teoricamente sono quelli più problematici dal punto di vista delle potenze impegnate, di scegliere le sottoportanti a loro più favorevoli lasciando le rimanenti agli altri.

Quello che fa quindi il solver è allocare ciclicamente tutti gli utenti lontani nelle varie celle e successivamente tutti i near user.

Questo processo viene ripetuto in maniera iterativa per un certo numero prefissato di volte; se si arriva ad una soluzione stabile, questa è la soluzione per l’istanza, altrimenti si procede alla riduzione del rate di un utente e si ricomincia.

3.4.1 Modello

A differenza degli algoritmi studiati in precedenza qui abbiamo due allocatori, uno per gli utenti lontani ed uno per gli utenti vicini.

Definiamo N pari al numero delle sottoportanti a disposizione, K come il numero di utenti all’interno di una cella, J come il numero di celle del sistema, Fj = {uf1, uf2, …, ufK1j} come l’insieme degli utenti lontani nella cella j, Nj = {un1, un2, …, unK2j} come l’insieme degli utenti vicini nella cella j, r(k) come il rate richiesto dal k-esimo utente, che in caso di singolo formato trasmissivo corrisponde al numero di sottoportanti da allocare allo stesso e bk(n) come l’indicatore binarip che assume valore 1

se l’n-esima risorsa è assegnata al k-esimo link e 0 altrimenti.

L’allocatore per utenti lontani risolve il seguente problema di ottimizzazione vincolata per ogni cella:

1 1 1

1,...,

1,...,

min

( )

( )

arg

( )

( ),

( ) 1,

( )

n

N

k

K

P n b n

b n

r k

b n

b n

=

=

⎧

_{∑ ∑}

_⋅

⎪

⎪

⎪

_∑

₌

⎪

⎨

⎪

≤

∑

⎪

⎪

⎪

∈ {0,1}

⎩

Mentre quello per gli utenti vicini risolve quest’altro problema, sempre per ogni cella:

1 1

1,...,

1,...,

min

( )

( )

arg

( )

( ),

( ) 1,

( )

n

N

k

K

P n b n

b n

r k

b n

b n

=

=

⎧

_{∑ ∑}

_⋅

⎪

⎪

⎪

_∑

₌

⎪

⎨

⎪

≤

∑

⎪

⎪

⎪

∈ {0,1}

⎩

Come si può vedere il (3.4.1) e il (3.4.2) sono pressochè identici, va notato però che nel terzo vincolo del (3.4.2) compare la variabile K e non K2; questo significa che mentre l’allocatore per gli utenti lontani

potrà scegliere in piena libertà per ogni cella le sottoportanti da allocare, l’allocatore per gli utenti vicini dovrà invece evitare di prendere in considerazione su ogni cella le sottoportanti già allocate.

Il comportamento del solver appena visto si traduce agli atti pratici in un privilegio per gli utenti che teoricamente sono i più svantaggiati.

3.4.2 Funzionamento generale

1: repeat

2: stableAll Å 0 3: distanceControl 4: for it Å 1, iterAll do

5: for cell Å 1,Ncells do

6: if farUserContr(cell) ~= 0 then

7: newAll(cell) Å allocFar(cell)

8: newPowFar(cell) Å powCalcFar(cell) 9: if it ~= iterAll then

10: oldAllPart(cell) Å newAllPart(cell)

11: oldPowFar(cell) Å newPowFar(cell)

12: end if

13: end if

14: end for

15: for cell Å 1,Ncells do

16: if nearUserContr(cell) ~= 0 then 17: newAll(cell) Å allocNear(cell) 18: newPowNear(cell) Å powCalcNear(cell) 19: if it ~= iterAll then 20: oldAll(cell) Å newAll(cell) 21: oldPowNear(cell) Å newPowNear(cell) 22: else 23: oldPow(cell) = … oldPowNear(cell) + oldPowFar(cell) 24: newPow(cell) = … newPowNear(cell) + newPowFar(cell)

25: diff = abs(oldPow(cell) – newPow(cell)) 26: if diff > coeff * newPow(cell) then

27: convFlag(cell) Å 1

28: end if

29: if cell = Ncells then

30: stabTotContr 31: if stabTotContrVar = 0 then 32: stableAll Å 1 33: else 34: reduceRate 35: end if 36: end if

37: end if

38: end if

39: end for

40: end for

41: until stableAll = 0

Anche in questo algoritmo si ha un ciclo più esterno, gestito dalla variabile stableAll, che si conclude nel momento in cui si è trovata un’allocazione stabile per l’istanza corrente.

La prima operazione che viene eseguita è la divisione per categoria geografica degli utenti61.

Successivamente, nel ciclo più interno, si lavora per un certo numero di iterazioni al fine di arrivare alla convergenza della soluzione; all’interno di ogni iterazione abbiamo due cicli completi sulle celle, uno per ogni allocatore.

Nel primo ciclo della prima iterazione abbiamo l’allocazione delle sottoportanti agli utenti lontani in ogni cella62; la prima cella fa le sue allocazioni senza percepire interferenza da parte dalle altre celle, la seconda esegue le proprie allocazioni tenendo conto dell’interferenza prodotta dagli utenti lontani nella prima cella e così via fino all’ultima cella.

Nel secondo ciclo della stessa iterazione vengono allocati gli utenti vicini in ogni cella63; la prima cella esegue le allocazioni tenendo conto delle sottoportanti che in quella cella sono state già assegnate agli utenti lontani nel primo ciclo e fa questo considerando l’interferenza prodotta dagli utenti lontani in tutte le altre celle, la seconda esegue l’allocazione con le medesime accortezze appena illustrate percependo però

61 _{Funzione distanceControl.} 62 _{Funzione allocFar.} 63 _{Funzione allocNear.}

l’interferenza prodotta anche dagli utenti vicini nella prima cella, il processo prosegue allo stesso modo fino all’ultima cella.

Nelle iterazioni successive le operazioni eseguite sono le stesse, l’unica diffrenza consiste nel fatto che tutte le celle percepiscono già l’interferenza prodotta da tutte le altre celle.

In conseguenza di questo avremo una certa evoluzione delle potenze impegnate nel sistema derivate dal solver; ciò che si auspica è che queste potenze con lo scorrere delle iterazioni si stabilizzino e convergano verso un certo valore.

Chiaramente per quanto riguarda la stabilità si sono inseriti dei margini; se le differenze di potenze impegnate nel sistema tra l’iterazione numero iterAll e l’iterazione numero iterAll – 1 rientrano in questi margini si può dire di aver trovato una soluzione per l’istanza corrente, altrimenti si deve intervinire con tecniche di riduzione del rate analoghe a quelle già viste nel paragrafo 3.2.4.

Anche in questo algoritmo la procedura appena illustata viene ripetuta fino a che non si trova una soluzione stabile per l’iterazione corrente.

3.4.3 Suddivisione degli utenti per categoria

Per poter eseguire questa operazione la prima cosa da fare è fissare una soglia che rappresenti la minima distanza tra un utente e la propria BS affinchè il primo possa essere considerato un utente vicino.

Una volta stabilita questa soglia non rimane altro che confrontarla con la distanza di ogni utente dalla propria BS ed effettuare la suddivisione. Questo limite può essere stabilito in maniera dinamica in ogni cella ed in ogni istanza oppure può essere fissato per tutte le celle e tutte le istanze.

Nel caso che si voglia una soglia dinamica il criterio da utilizzare è rappresentato dal numero di utenti che in una cella vogliamo considerare lontani.

Se ad esempio abbiamo quattro utenti per cella e vogliamo che la soglia sia determinata in modo da avere un utente lontano per cella, questa verrà fissata come un valore intermedio tra la massima e la terza più grande delle distanze degli utenti dalla BS della cella presa in esame. E’ inutile dire che questo passo è fondamentale per le prestazioni dell’algoritmo.

3.4.4 Controllo di convergenza e riduzione del rate

Nell’algoritmo NF queste importanti funzioni vengono eseguite in maniera analoga rispetto a quanto visto per il solver iterativo parzialmente distribuito.

Per quanto riguarda il controllo di convergenza si rimanda al metodo ibrida distribuito/centralizzato illustato nel paragrafo 3.2.3 mentre per la procedura di riduzione del rate si deve fare riferimento a quanto esposto nel paragrafo 3.2.4.

3.4.5 Difetti dell’algoritmo

L’algoritmo appena illustrato presenta problemi implementativi che ne riducono la versatilità in termini di gestione dei gradi di libertà a nostra disposizione.

Il primo problema è inerente la fase di allocazione degli utenti lontani nelle varie celle.

Supponiamo di avere 7 celle di cui 2 con almeno un utente lontano e di essere nel primo ciclo della seconda iterazione, ciò che si fa è resettare l’allocazione in quella cella ed eseguire le nuove assegnazioni per gli utenti lontani; nel fare questo si tiene conto dell’interferenza prodotta da tutti gli altri utenti del sistema.

Passando all’altra cella con almeno un utente lontano le operazioni che si fanno sono le medesime.

Anche in questo caso si resetta l’allocazione nella cella ma stavolta, nell’eseguire le nuove assegnazioni, non terremo conto dell’interferenza prodotta da tutti gli altri utenti del sistema, poiché nella prima cella presa in considerazione gli utenti vicini non sono stati ancora allocati dato che questo viene fatto all’interno del secondo ciclo.

Il secondo problema è invece inerente la fase di allocazione degli utenti vicini nelle varie celle.

Mettendoci nelle stesse ipotesi di prima a parte il fatto di essere chiaramente all’inizio del secondo ciclo, avremo che, andando ad eseguire l’allocazione degli utenti vicini in una cella, non terremo conto dell’interferenza generata dagli utenti vicini nelle due celle con almeno un utente lontano; questo problema persisterà finché questi utenti non verranno allocati.

Per capire la fisionomia del problema basta notare che per tenere conto degli utenti nelle cinque celle che hanno al loro interno solo utenti vicini si usa l’allocazione e le potenze calcolate nell’iterazione precedente, mentre per quanto riguarda le altre due celle questo non si può fare dato che la variabile che contiene l’allocazione è stata resettata.

Questi problemi sono causa di una minore velocità di convergenza dell’algoritmo ed in alcuni casi addirittura di una mancata convergenza. L’incidenza delle problematiche appena descritte può essere ridotta in modo notevole tramite delle accurate scelte progettuali, tuttavia questo

comporta una riduzione notevole dei gradi di libertà del progettista causata da una minore versatilità del solver.

Le contromosse in questione sono:

*) Utilizzare una soglia di distanza sufficientemente alta in modo che nel sistema non ci siano molte celle che abbiano al loro interno utenti classificabili come lontani.

Questo riduce di molto l’incidenza di entrambi i difetti dell’algoritmo ma, come si può ben capire, limita in maniera significativa le alternative a disposizione del progettista.

Un’altra controindicazione di questa soluzione sta nel fatto che si riduce l’impatto della strategia a suddivisione geografica avvicinando il solver ad un algoritmo del tipo studiato nel paragrafo 3.2.

*) Effettuare una reindicizzazione delle celle, riducendo l’arbitrarietà della posizione nella sequenza di allocazione di una cella.

Facendo questo nel secondo ciclo possiamo allocare prima gli utenti lontani nelle celle che hanno almeno un utente classificato come lontano in modo da ridurre l’incidenza del secondo problema descritto.

Nel caso in cui nel sistema ci sia una sola cella con almeno un utente lontano, con la reindicizzazione si elimina completamente il secondo problema descritto.

Si capisce che comunque nel caso che vi siano più celle di questo tipo questa soluzione riduce solamente in modo parziale l’impatto della problematica.

*) Non resettare completamente le allocazioni precedenti in una cella durante il primo ciclo.

Questa soluzione è applicabile solamente quando abbiamo una convergenza della soluzione quasi totale in tutte le celle che hanno almeno un utente lontano; infatti, questo processo non è ambiguo solamente se la nuova allocazione degli utenti lontani coincide con la precedente.

Inoltre le inevitabili oscillazioni delle assegnazioni nelle prime iterazioni non consentono l’evoluzione naturale della convergenza della soluzione condizionando in tal modo la stessa.

Le due problematiche appena viste sono tanto più dannose quanto più è alta l’efficienza spettrale richiesta dagli utenti, in fase di silìmulazione si sono riscontrate anomalie nel solver per valori superiori al 2 della grandezza stessa.

In fase di svolgimento della tesi si sono studiate soluzioni alternative ibride, che tengono conto sia della posizione degli utenti nella cella sia della condizione dal punto di vista dei guadagni degli stessi, di cui non è stato purtroppo possibile verificare il funzionamento.

La soluzione studiata in questo paragrafo rimane comunque un punto di vista innovativo sulle problematiche di allocazione di risorse e può rappresentare una utile overview sulle problematiche inerenti gli approcci basati sulla distanza.