UK 
EnglishТипова
Polski📡 Балансувальник навантаження стільникової мережі — розфарбування графа наживо
Спостерігайте, як оптимізатор розфарбування графа перепризначає частотні канали між стільниковими вежами, що перекриваються, усуваючи інтерференцію і балансуючи навантаження, коли симульований трафік дзвінків змінюється по всій мережі.
Про цю симуляцію
Стільникові мережі розміщують вежі настільки близько одна до одної, що сусідні зони покриття перекриваються — і будь-які дві вежі, що транслюють на одній частоті, заважатимуть дзвінкам одна одної. Телеком-інженери вирішують це за допомогою розфарбування графа: будується граф, де вежі — вершини, а ребро з’єднує будь-які дві вежі з перекриттям покриття, після чого кожній вершині присвоюється «колір» (частотний канал) так, щоб жодне ребро не з’єднувало дві однаково пофарбовані вершини. Ця симуляція будує такий граф інтерференції з випадково розкиданого набору стільникових веж і запускає DSATUR — справжню жадібну евристику розфарбування за ступенем насичення — прямо в браузері, поки симульований трафік дзвінків вмикає й вимикає вежі.
🔬 Що показано
Вежі — це 3D-вершини, розташовані на площині землі; ребра позначають зв’язки інтерференції в межах налаштовуваного радіуса. Навантаження симульованого трафіку кожної вежі коливається з часом — коли воно перетинає поріг навантаження, вежа активується і повинна утримувати канал, що не конфліктує з жодним активним сусідом. Оскільки вежі зберігають «липкий» застарілий канал з моменту останньої активності, повторна активація поблизу нових сусідів може створити реальний, видимий конфлікт (миготливе червоне ребро), доки розв’язувач його не виправить.
🎮 Як користуватись
Налаштуйте кількість веж і радіус інтерференції, потім натисніть «Перегенерувати мережу», щоб перебудувати граф інтерференції. Пересувайте повзунок навантаження трафіку, щоб змінити, як часто вежі активні, і використовуйте «Форсувати перерозв’язання» для негайного виправлення DSATUR, або залиште «Авто-перерозв’язання» увімкненим, щоб побачити автоматичне виправлення конфліктів із невеликою затримкою. Клацніть на будь-яку вежу, щоб переглянути її канал, навантаження та кількість сусідів.
💡 Чи знали ви?
Оптимальне розфарбування графа є NP-складною задачею, тож реальне планування частот (і ця симуляція) покладається на евристики, такі як DSATUR, а не на повний перебір. DSATUR часто наближається дуже близько до справжньої мінімальної кількості каналів — хроматичного числа — на реалістичних геометричних графах інтерференції, ніколи не перебираючи всі можливості.
Часті питання
Який алгоритм призначає частотні канали?
Симуляція запускає DSATUR (ступінь насичення) — добре відому жадібну евристику розфарбування графів. Вона повторно вибирає непофарбовану вежу, чиї сусіди наразі використовують найбільше різних каналів (розриваючи нічию за звичайним ступенем), а потім присвоює їй найменший номер каналу, ще не використаний жодним активним сусідом. Коли трафік дзвінків активує або деактивує вежі, перефарбовуються лише вежі, що торкаються конфлікту, залишаючи решту мережі незмінною.
Чому конфлікти взагалі виникають, якщо алгоритм коректний?
Кожна вежа зберігає «липкий» застарілий канал з моменту останньої активності, імітуючи те, як реальні базові станції зберігають свій останній призначений частотний план. Коли раніше неактивна вежа знову активується поблизу активних сусідів, її старий канал може тепер конфліктувати з одним із них — справжній, видимий конфлікт, доки не спрацює процедура виправлення розв’язувача.
Як будується граф інтерференції?
Кожна пара веж, відстань між якими на площині землі менша за радіус інтерференції, з’єднується ребром, що представляє зони покриття, які перекриваються і викликали б спільноканальну інтерференцію при призначенні однакової частоти.
Що контролює повзунок навантаження трафіку?
Кожна вежа має незалежну симульовану хвилю трафіку дзвінків. Повзунок навантаження зсуває поріг активації, тож вище значення означає, що вежі проводять більшу частину циклу вище порога і активні частіше — це збільшує частоту зміни патерну покриття, а отже й активного графа інтерференції.
Чи гарантовано DSATUR знаходить мінімальну кількість каналів?
Ні — оптимальне розфарбування графа загалом є NP-складним, тож DSATUR — це евристика, а не точний розв’язувач. На практиці вона зазвичай працює дуже добре і часто збігається або наближається до хроматичного числа на геометричних графах інтерференції, що генеруються тут, але не гарантується оптимальність для кожного випадкового розташування.