PB165 – Grafy a sítě 12. Optimalizace, plánování v bezdrátových sítích PB165 – Grafy a sítě Obsah přednášky Optimalizace Lokální prohledávání Evoluční prohledávání Stručný náhled na plánování bezdrátových sítí Topologie pevné sítě Alokace kanálů Umístění základnových stanic Shrnutí PB165 – Grafy a sítě Úvod Soustředíme se na optimalizaci Zpravidla kombinatorické problémy Nejvhodnější topologie privátní datové sítě Rozložení základnových stanic pro GSM sítě Rozdělení frekvencí u bezdrátových sítí Nejlepší topologie ,,poslední míle‘‘ Co mají společné Diskrétní kombinatorické problémy Patří mezi NP-těžké úlohy Používáme heuristická řešení PB165 – Grafy a sítě Heuristiky Přibližná řešení NP-těžkých problémů Prohledávání Lokální prohledávání a jeho varianty Evoluční prohledávání Standardní techniky Lineární programování Dynamické programování atd. Proč heuristiky Použití snazší (intuitivnější) Větší šance najít alespoň nějaké řešení PB165 – Grafy a sítě Heuristiky vs. klasické metody Není možné rozhodnout, které techniky jsou lepší Empirické pozorování (Corne et al. Telecommunications Optimization., John Wiley, 2000): Expertovi na heuristiky vychází lépe řešení pomocí heuristik Expertovi na standardní techniky operačního výzkumu vychází lépe tyto techniky Závěr: Nejlepší je použít techniku, které dobře rozumíte A tady je výhoda heuristik, protože jsou snáze pochopitelné PB165 – Grafy a sítě Lokální prohledávání Řešíme problém, pro který existuje mnoho řešení Jednotlivá řešení neznáme, ale umíme je generovat Hledáme řešení splňující nějaké podmínky Triviální (brute force) přístup: vygenerujeme všechna řešení a vybereme to ,,správné‘‘ Velikost prostoru toto řešení neumožňuje Optimalizace Hledáme řešení, které minimalizuje cenu (cost function) Lokální prohledávání: Začne s nějakým řešením a to ,,zlepšuje‘‘ prohledáváním jeho okolí Potřebuje definovat to ,,okolí‘‘ Malá změna stavu Přidání či ubrání vrcholu nebo hrany Posun hrany Příslušnou operaci nazýváme mutace PB165 – Grafy a sítě Lokální prohledávání – základní algoritmus 1 Nalezni nějaké (počáteční) řešení c a spočti jeho cenu f (c) 2 Proveď mutaci c → c a spočti cenu f (c ) 3 Pokud f (c ) ≤ f (c), nahraď řešení c řešením c 4 Je-li splněno kritérium ukončení, skonči, jinak se vrať na bod 2 V podstatě se jedná o slézání z kopce V literatuře se často setkáte s pojmem hillclimbing, tedy ,,stoupání do kopce‘‘. V takovém případě se snažíme f (c) maximalizovat. Důležitý je výběr počátečního řešení Nelze očekávat, že ze špatného řešení se rychle najde dobré PB165 – Grafy a sítě Uváznutí Lokální prohledávání může ,,uváznout‘‘ Nalezeno lokální minimum Z něj se nelze dostat bez porušení pravidla striktního ne-zhoršování ceny Dva často používané přístupy Simulované žíhání: s určitou pravděpodobností akceptujeme i horší řešení Tabu prohledávání: Zohledňuje typ mutace, ne jen cenu PB165 – Grafy a sítě Simulované žíhání (Simulated Annealing) Zavádí teplotu T Při vyšší teplotě je materiál ,,tvárný‘‘ Vyšší teplota – vyšší pravděpodobnost akceptace horšího řešení Spočte funkci F(f (c), f (c ), T), např. e(f (c)−f (c ))/T (F > 1 pro f (c ) < f (c)) Vygeneruje náhodné číslo r ∈ (0, 1) Pokud F > r, pak konfigurace c je akceptována Dodatečný ,,trik‘‘: teplota klesá s počtem iterací PB165 – Grafy a sítě Simulované žíhání – algoritmus 1 Nalezni nějaké (počáteční) řešení c a spočti jeho cenu f (c); nastav teplotu T a parametr chlazení q (0 < q < 1) 2 Proveď mutaci c → c a spočti cenu f (c ) 3 Pokud test(f (c ), f (c), T) platí, nahraď řešení c řešením c (test je funkce popsaná výše) 4 Uprav teplotu T = qT 5 Je-li splněno kritérium ukončení, skonči, jinak se vrať na bod 2 Na počátku vyhledávání se akceptují i výrazně horší řešení PB165 – Grafy a sítě Tabu prohledávání Pamatuje si předchozí změny Zavádí tabu (tedy zakázané) změny Např. vrchol, jehož hrany se změnily v posledních krocích, nesmí být už měněn Vybere nejlepší z povolených změn Což nemusí být absolutně nejlepší konfigurace Podstatný výběr kritérií, podle nichž se zařazuje do zakázaných (tabu) seznamů Otázka zkušenosti uživatele této heuristiky PB165 – Grafy a sítě Společné vlastnosti Důležitá reprezentace a operátor mutace Topologie sítě jako seznam dvoubodových spojení, alternativně jako bitový seznam existujících vs. možných spojení atd. Aplikace dodatečné znalosti Např. v počítačové síti nechceme izolované vrcholy Vyloučíme je tedy vždy z uvažování (mutace vedoucí k rozpadu sítě neakceptujeme) Redundance – akceptujeme jen uzly se stupněm alespoň 2 Složitější – např. požadavek existence kostry (garantuje spojitost a může být použito přímo při aplikaci operátoru mutace) Znalost ceny (resp. funkce jejího výpočtu) může rovněž přímo ovlivňovat operátor mutace Aplikace algoritmů na nalezení kostry s minimální cenou a následně již jen přidáváme hrany k této kostře (i odpovídající reprezentace) PB165 – Grafy a sítě Evoluční prohledávání Při hledání nové ,,mutace‘‘ nepoužíváme jen jednoho předka, ale celou populaci Prohledáváme paralelně několik okolí Provádíme rekombinaci Rekombinace Dva nebo více ,,rodičů‘‘ Vhodnou operací se spojí jejich vlastnosti (např. každá část sítě je od jiného ,,rodiče‘‘) Výsledek se nazývá rekombinant (na rozdíl od mutanta) Cílem rekombinace je opět překonat lokální optimum – rekombinace vybere vzdálenou konfiguraci, která dědí pro dvou ,,dobrých rodičích‘‘ Crossover Máme stav popsán lineárním vektorem Výsledná konfigurace náhodný výběr hodnot z ,,rodičovských‘‘ konfigurací (vektorů) Rekombinant (,,dítě‘‘) se může i o 50 % lišit od kteréhokoliv ,,rodiče‘‘ PB165 – Grafy a sítě Evoluční prohledávání – algoritmus 1 Inicializuj populaci vhodně zvolenými konfiguracemi. Spočti cenu každé konfigurace. 2 Vyber rodiče (několik párů, resp. n-tic) 3 Použij rekombinaci a mutaci a vytvoř ,,děti‘‘ 4 Začleň ,,děti‘‘ do populace 5 Pokud je dosaženo kritéria ukončení, skonči, jinak přejdi na bod 2 Algoritmus má velmi mnoho stupňů volnosti Výběr rodičů je zpravidla dán jejich cenou (nicméně je vhodný i určitý náhodný prvek) Je možné se omezit jen na rekombinace nebo rekombinace a mutace; mutují se ,,rodiče‘‘, jen zřídka ,,děti‘‘ Začlenění ,,dětí‘‘ do populace Udržení ,,genové‘‘ diverzity PB165 – Grafy a sítě Bezdrátové sítě – přehled optimalizačních problémů Návrh topologie pevné sítě Přiřazení kanálů (frekvencí) Umístění základnových stanic Správa mobility Správa volání Detekce uživatelů v CDMA sítích TDMA alokace slotů Ekvalizace (vyrovnání) dat (toků) Většinu z nich lze transformovat na grafové problémy PB165 – Grafy a sítě Topologie pevné sítě pro mobilní operátory Hierarchie prvků mobilní sítě Mobilní stanice (MS) komunikují bezdrátově se základnovými stanicemi (BTS). Ty jsou kontrolovány řídícími stanicemi (BSC), které jsou sdruženy pod přepínací stanice (MSC). Samotné přepínací stanice pak tvoří páteř mobilní sítě, protože odpovídají autentizaci, účetnictví, údržbu databází apod. Vidíme, že většina sítě je fixní (bezdrátové spojení je nezbytné jen pro kontakt MS s BTS) Návrh topologie s minimální cenou souvisí s nalezením minimální kostry Příklad ceny: f = ∀n CNODE n + ∀p CPOI p + ∀l∈LBTS→BSC,LBSC→MSC,LMSC→MSC CLINK l s okrajovými podmínkami Fl ≤ Cl , ∀l, θ ≤ 0.001 kde CNODE n je cena vrcholů typu n, CPOI p je cena přípojného místa do veřejné sítě (Point of Interconnect), CLINK l je cena spoje l typu LBTS→BSC , LBSC→MSC , LMSC → MSC a Fl , Cl reprezentují tok a kapacitu spoje l a θ je pravděpodobnost nepřijetí volání. PB165 – Grafy a sítě Alokace kanálů (frekvencí) K dispozici je pouze velmi omezený počet kanálů/frekvencí Základní idea mobilní sítě: znovupoužití frekvencí v geograficky oddělených částech sítě Buňka – část sítě s množinou přidělených frekvencí Celé spektrum je přiděleno clusteru buněk Buňky zpravidla hexagonální (pokrytí plochy) Geometrie omezuje počet buněk v clusteru N = i2 + ij + j2 kde i a j jsou celá čísla (N je tedy 1, 3, 4, 7, . . .) Problémem je interference PB165 – Grafy a sítě Alokace kanálů II Podmínky alokace 1 Interference frekvencí mezi buňkami (buňky se stejným kanálem) 2 Interference frekvencí na buňce (minimální spektrální vzdálenost kanálů) 3 Požadavky buňky na počet kanálů Problém přidělení kanálů je ekvivalentní zobecněnému problému barvení grafů Podvarianty: pevné a dynamické přidělení kanálů Jiná možná formulace: Minimum Interference Frequency Assignment Problem (MI-FAP) Převeditelné na zevšeobecněné nalezení maximálního k-řezu na hranově ohodnoceném grafu (k je počet dostupných frekvencí) PB165 – Grafy a sítě Umístění základnových stanic Pokrytí terénu signálem při minimalizaci počtu základnových stanic Problém velmi podobný nalezení minimální dominující množiny grafu Definice Dominující množina grafu je taková množina jeho vrcholů, že všechny ostatní vrcholy jsou spojeny s alespoň jedním vrcholem dominující množiny PB165 – Grafy a sítě CDMA sítě Kvalita signálu je v síti 3. generace závislá na ostatní probíhající komunikaci Plánování frekvencí a rozmístění stanic je třeba řešit současně Problém plánování UMTS sítě lze formulovat následovně Máme množiny S = {1, . . . , m} možných umístění stanic, množinu I = {1, . . . , n} testovacích bodů, kde ui je požadovaný počet aktivních spojení v bodě i, útlumovou matici G a snažíme se najít podmnožinu S kde umístit základnové stanice a současně definovat jejich konfiguraci (jako je např. rozměry, směrování a výkon antén). Lze přesně zformulovat jako problém celočíselného programování, řešitelný přibližně Tabu search metodami PB165 – Grafy a sítě Shrnutí Mnoho problémů návrhu sítě má charakter optimalizace grafově vyjádřeného problému Optimalizace je zpravidla NP-těžký problém, řešený heuristicky Populární heuristiky využívají lokální nebo evoluční prohledávání Negarantují nalezení globálního optima Na druhé straně mohou poskytnout cenné informace o stavovém prostoru možných řešení A nalezená řešení zpravidla akceptovatelná Příklady problémů plánování mobilní sítě jako optimalizace grafově orientovaných problémů PB165 – Grafy a sítě