P B165 - Grafy a sítě 12. Plánování v telekomunikačních sítích Obsah přednášky • Optimalizace • Lokální prohledávání • Evoluční prohledávání • Stručný náhled na plánování mobilních sítí • Topologie pevné sítě • Alokace kanálů • Umístění základnových stanic • Shrnutí • Soustředíme se na optimalizaci 9 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í □ s 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í 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é 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 a 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 Lokální prohledávání - základní algoritmus O Nalezni nějaké (počáteční) řešení c a spočti jeho cenu f(c) Q Proveď mutaci c —> c' a spočti cenu ŕ(c') O Pokud ŕ(c') < f (c), nahraď řešení c řešením c' O 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é 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, nejen cenu Simulované žíhaní (Simulated Anneal • Zavádí teplotu T • Při vyšší teplotě je materiál „tvárný" a 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'))/r (F > 1 pro f(c>) < f{c)) » Vygeneruje náhodné číslo r e (0,1) • Pokud F > r, pak konfigurace c'je akceptována • Dodatečný „trik": teplota klesá s počtem iterací Simulované žíhaní - algoritmus O 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) O Proveď mutaci c —» c' a spočti cenu ŕ(c') O Pokud test(r(c/), f(c), T) platí, nahraď řešení c řešením c' (test je funkce popsaná výše) O Uprav teplotu T = qT O 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í • 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 • 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. a 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) • 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" Evoluční prohledávání - algoritmus O Inicializuj populaci vhodně zvolenými konfiguracemi. Spočti cenu každé konfigurace. O Vyber rodiče (několik párů, resp. n-tic) Q Použij rekombinaci a mutaci a vytvoř „děti" Q Začleň „děti" do populace O 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 Mobilní 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 dat Jen některé mají charakter grafových problémů opologie 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: Vn C, NODE.V^ rPOI_ E c} V7eZ_bts^bsc í_bsc^msc i_msc_ LINK s okrajovými podmínkami F, < C,, V/, 6 < 0.001 kde C^ODE je cena vrcholů typu n, Cľ01 je cena přípojného místa do veřejné sítě (Point of Interconnect), C;LINK je cena spoje / typu ^bts^bsc^ ^bsc^msc^ ^Msc ^ MSC a F/> Q reprezentují tok a kapacitu spoje / a 9 je pravděpodobnost nepřijetí volání. • 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+f kde / a j jsou celá čísla (A/ je tedy 1, 3,4, 7, ...) • Problémem je interference □ g ► < ^ ► Alokace kanálů • Podmínky alokace O Interference frekvencí mezi buňkami (buňky se stejným kanálem) Q Interference frekvencí na buňce (minimální spektrální vzdálenost kanálů) Q 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ů 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 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ů • Grafy velmi důležitou diskrétní konstrukcí matematiky i informatiky • Řada reálných problémů převeditelná na grafové problémy • Dobrá znalost alespoň základů teorie grafů pomůže • Znalost grafových algoritmů resp. problémů může pomoci při odhadu náročnosti řešení konkrétního praktického problému • Mapování na grafový problém může najít optimální řešení a Plánování jako grafový problém • Velmi významné optimalizace