PL 
EnglishDomyślny
Українська📡 Bilansowanie obciążenia sieci komórkowej — kolorowanie grafu na żywo
Obserwuj, jak optymalizator kolorowania grafu przypisuje na nowo kanały częstotliwości między nakładającymi się wieżami komórkowymi, by wyeliminować zakłócenia, bilansując obciążenie w miarę zmian symulowanego ruchu połączeń w sieci.
O tej symulacji
Sieci komórkowe rozmieszczają wieże na tyle blisko siebie, że sąsiednie komórki się nakładają — a dowolne dwie nakładające się wieże nadające na tej samej częstotliwości będą zakłócać sobie nawzajem połączenia. Inżynierowie telekomunikacyjni rozwiązują to za pomocą kolorowania grafu: budują graf, w którym wieże są węzłami, a krawędź łączy dowolne dwie wieże, których zasięg się nakłada, a następnie przypisują każdemu węzłowi „kolor” (kanał częstotliwości) tak, by żadna krawędź nie łączyła dwóch węzłów tego samego koloru. Ta symulacja buduje ten graf zakłóceń z losowo rozrzuconego zbioru wież komórkowych i uruchamia DSATUR, prawdziwą zachłanną heurystykę kolorowania opartą na stopniu nasycenia, na żywo w przeglądarce, gdy symulowany ruch połączeń włącza i wyłącza wieże.
🔬 Co pokazuje
Wieże to węzły 3D umieszczone na płaszczyźnie gruntu; krawędzie oznaczają połączenia zakłóceń w obrębie konfigurowalnego promienia zakłóceń. Symulowane obciążenie ruchem połączeń każdej wieży oscyluje w czasie — gdy przekroczy próg obciążenia ruchem, wieża staje się aktywna i musi utrzymać kanał, który nie koliduje z żadnym aktywnym sąsiadem. Ponieważ wieże zachowują „lepki” dawny kanał z ostatniego okresu aktywności, ponowna aktywacja blisko nowych sąsiadów może stworzyć rzeczywisty, widoczny konflikt (migająca czerwona krawędź), dopóki solver go nie naprawi.
🎮 Jak korzystać
Dostosuj liczbę wież i promień zakłóceń, a następnie kliknij „Wygeneruj sieć ponownie”, aby odbudować graf zakłóceń. Przesuń obciążenie ruchem, aby zmienić, jak często wieże są aktywne, i użyj „Wymuś ponowne rozwiązanie teraz”, aby wywołać natychmiastową naprawę DSATUR, lub zostaw włączone „Automatyczne ponowne rozwiązanie”, aby obserwować automatyczne naprawianie konfliktów po krótkim opóźnieniu. Kliknij dowolną wieżę, aby zbadać jej kanał, obciążenie i liczbę sąsiadów.
💡 Czy wiesz, że?
Optymalne kolorowanie grafu jest NP-trudne, więc rzeczywiste planowanie częstotliwości (i ta symulacja) opiera się na heurystykach takich jak DSATUR zamiast przeszukiwania siłowego. DSATUR często zbliża się bardzo blisko prawdziwej minimalnej liczby kanałów — liczby chromatycznej — na realistycznych geometrycznych grafach zakłóceń, nigdy nie musząc próbować każdej możliwości.
Najczęściej zadawane pytania
Jaki algorytm przypisuje kanały częstotliwości?
Symulacja uruchamia DSATUR (stopień nasycenia), dobrze znaną zachłanną heurystykę kolorowania grafu. Wielokrotnie wybiera nieukolorowaną wieżę, której sąsiedzi obecnie używają najwięcej odrębnych kanałów (rozstrzygając remisy surowym stopniem), a następnie przypisuje jej najmniejszy numer kanału jeszcze nieużywany przez aktywnego sąsiada. Gdy ruch połączeń aktywuje lub dezaktywuje wieże, tylko wieże dotknięte konfliktem są przekolorowywane, pozostawiając resztę sieci nienaruszoną — realistyczna strategia przyrostowej naprawy zamiast pełnego przeplanowania co takt.
Dlaczego konflikty w ogóle się pojawiają, jeśli algorytm jest poprawny?
Każda wieża zachowuje „lepki” dawny kanał z ostatniego okresu aktywności, naśladując sposób, w jaki prawdziwe stacje bazowe zachowują ostatnio przypisany plan częstotliwości. Gdy wcześniej nieaktywna wieża ponownie się aktywuje blisko aktywnych sąsiadów, jej stary kanał może teraz kolidować z jednym z nich. Ta kolizja jest rzeczywistym, widocznym konfliktem, dopóki solver nie uruchomi swojego przebiegu naprawy.
Jak budowany jest graf zakłóceń?
Każda para wież, których odległość na płaszczyźnie gruntu jest mniejsza niż promień zakłóceń, jest połączona krawędzią, reprezentującą nakładające się komórki zasięgu, które powodowałyby zakłócenia współkanałowe, gdyby przypisano im tę samą częstotliwość. To jest graf, który musi zostać poprawnie pokolorowany: żadne dwie wieże połączone krawędzią nie mogą dzielić kanału, gdy obie aktywnie przenoszą ruch.
Co kontroluje suwak obciążenia ruchem?
Każda wieża ma niezależny symulowany przebieg ruchu połączeń. Suwak obciążenia przesuwa próg aktywacji, więc wyższa wartość oznacza, że wieże spędzają więcej swojego cyklu powyżej progu i są aktywne częściej — zwiększając, jak często zmienia się wzorzec zasięgu, a tym samym aktywny graf zakłóceń.
Czy DSATUR gwarantuje znalezienie minimalnej liczby kanałów?
Nie — optymalne kolorowanie grafu jest ogólnie NP-trudne, więc DSATUR jest heurystyką, a nie dokładnym solverem. W praktyce zwykle działa bardzo dobrze i często dorównuje lub zbliża się do liczby chromatycznej na generowanych tu geometrycznych grafach zakłóceń, ale nie gwarantuje optymalności na każdym losowym układzie.