algoritmo di allocazione del canale

Question

Abbiamo un insieme di nodi di radio in stretta vicinanza l'uno all'altro e vorremmo assegnare le frequenze per loro per ridurre al minimo la sovrapposizione. Per ottenere una copertura completa della zona, canali radio devono essere tutto esaurito e quindi dovremo radio vicine che trasmettono sulla stessa frequenza.

I dati si riferiscono
5 Frequenze
343 radio
4158 bordi

Il mio attuale ipotesi migliore è di generare in modo casuale una popolazione di assegnazioni di frequenze e per scambiare le frequenze tra le radio fino a quando il punteggio migliore non migliora per 10 generazioni. Score è la somma di 1 / intervallo ^ 2 per le radio sulla stessa frequenza.

Ogni bordo è la distanza tra le radio, corretti per pareti e pavimenti. I bordi superiori 2 * la portata radio massima sono stati abbattuti dalla lista.

C'è un modo migliore?

Answer 1

Questo è fondamentalmente un problema grafico colorazione con una torsione. Piuttosto che tutte le colorazioni adeguate essere altrettanto buona, alcuni coloranti propri sono migliori di altri, come definito dal vostro algoritmo di punteggio.

Credo che il tuo approccio genetico è pratico e produrrà buoni (se non dimostrabilmente ottimale) soluzioni, ma mi sarebbe sicuramente suggerire a guardare un po 'di grafico-colorazione carte e vedere come essi sono applicabili. E 'molto probabile che otterrete alcune grandi idee per decidere come il vostro algoritmo dovrebbe prendere in considerazione le scelte disponibili.

Answer 2

Sono d'accordo che una simulazione sulla base di assegnazione iniziale casuale seguito da un po 'di ottimizzazione è un buon approccio, ma che stai descrivendo una procedura di ottimizzazione che non sembra ottimale, se ho capito bene (hai intenzione di scambiare le frequenze in modo casuale se ho letto bene). Ad ogni fase di ottimizzazione è possibile scegliere un miglioramento "ragionevole" prendendo una radio dal ciascun gruppo di frequenza e considerando l'5*4/2=10 possibili scambi di frequenze tra due di loro, e neanche scegliere il migliore, o (per esempio) una di quelle che ha delta positivo segnare, con probabilità proporzionali ai delta nei punteggi.

Nello spirito di "ricottura simulata", una volta che il punteggio complessivo sembra avere più o meno stabilizzata, si può decidere di passare per un piccolo numero di passi per "alta temperatura" (elevata casualità) dove basta scegliere il set 5 radio e scambiare tutti ad esempio con una permutazione circolare delle assegnazioni di frequenza - fanno un paio di volte poi andare alla parte "raffreddamento" di nuovo la procedura di cui al paragrafo precedente (che cerca di ottenere una simulazione economica di una discesa di massima pendenza; -).

Answer 3

Il mio pugnalata veloce al sarebbe quella di utilizzare un sottile piastra di spline (o forse un simile, intelligente tecnica algebra lineare) per adattare un aereo per la funzione di densità di frequenza. Il 'altitudine' media di ciascun piano (per frequenza) sarebbe poi dire se una frequenza è abusato (vale a dire quando è più alto rispetto agli altri); la pendenza sarebbe un'indicazione della distribuzione spaziale.